Верховный алгоритм

Но и это еще не все. Если я попробую одно правило и оно окажется в 75 процентах точным на 400 примерах, я, вероятно, ему поверю. Но если я перепробую миллион правил и лучшее будет точным в 75 процентах из 400 примеров, я, вероятно, ему не поверю, потому что это вполне могло произойти случайно. Это та же проблема, с которой вы сталкиваетесь при выборе паевого фонда. Фонд «Ясновидец» десять лет подряд был лидером рынка. Ух ты! Наверное, у них гениальный управляющий! Или нет? Если у вас есть возможность выбирать из тысячи фондов, велик шанс, что десять лет лидером будет даже такой фонд, которым тайно управляют бросающие дротики мартышки. Научная литература тоже страдает от этой проблемы. Тесты статистической значимости — золотой стандарт при допуске результатов исследований к публикации, но, если эффект ищет несколько коллективов, а находит его только один, есть вероятность, что произошла ошибка, хотя по солид­ной на вид статье этого никак не определить. Одним из решений была бы публикация и положительных, и отрицательных результатов, чтобы читатель знал обо всех неудачных попытках, но такой подход не прижился. В машинном обучении можно отслеживать, сколько правил было испробовано, и соответствующим образом подбирать тесты значимости, однако тогда появляется тенденция выбрасывать много хороших правил, а не только плохих. Метод немного лучше — признать, что некоторые ложные гипотезы неизбежно прокрадутся, и держать их количество под контролем, отбрасывая гипотезы с низкой значимостью и тестируя оставленные на дальнейших данных.

Еще один популярный подход — отдавать предпочтение более простым гипотезам. Алгоритм «разделяй и властвуй» косвенно предпочитает простые правила, потому что условия перестают прибавляться к правилу, как только оно охватывает только положительные примеры, и перестает добавлять правила, как только все положительные примеры охвачены. Тем не менее для борьбы с переобучением нужно более сильное предпочтение простым правилам, которое остановит добавление условий еще до того, как будут охвачены все негативные примеры. Например, можно вычитать из точности штрафные очки, пропорциональные длине правила, и использовать это как средство оценки.

Предпочтение более простым гипотезам широко известно как бритва Оккама48, однако в контексте машинного обучения этот принцип немного обманчив. «Не множить сущее без необходимости», как часто перефразируют бритву, означает только то, что нужно выбирать самую простую теорию, которая подходит к данным. Оккам, наверное, пришел бы в недоумение от мысли, что нам надо отдавать предпочтение теории, которая не идеально подходит к доказательствам, только на том основании, что она более качественно обобщает. Простые теории предпочтительнее не потому, что они обязательно точнее, а потому, что они означают меньшую когнитивную нагрузку (для нас) и меньшие вычислительные затраты (для наших алгоритмов). Более того, даже самые замысловатые модели — обычно лишь существенное упрощение реальности. Из теоремы о бесплатных обедах мы знаем, что даже в случае теорий, идеально подходящих к данным, нет гарантии, что простейшая обобщает лучше всего, а на практике одни из лучших обучающихся алго­ритмов — например, бустинг и метод опорных векторов — извлекают на первый взгляд необоснованно сложные модели. (Мы посмотрим, почему они работают, в главах 7 и 9.)

Если точность обучающегося алгоритма в тестовой выборке разо­чаровы­вает, надо диагностировать проблему: дело в слепоте или галлюцинациях? В машинном обучении для этих проблем существуют специальные термины: смещение и дисперсия. Часы, которые постоянно опаздывают на час, имеют большое смещение, но низкую дисперсию. Если часы беспорядочно идут то быстро, то медленно, но в среднем показывают правильное время, дисперсия высокая, но смещение низкое. Представьте, что вы сидите в баре с друзьями, выпиваете и играете в дартс. Вы втайне от них годами тренируетесь, добились мастерства, и все дротики попадают прямо в яблочко. У вас низкое смещение и низкая дисперсия, что показано в нижнем левом углу этой диаграммы:

Ваш друг Бен тоже очень хорош, но сегодня вечером немного перебрал. Его дротиками утыкана вся мишень, но тем не менее он громко заявляет, что в среднем попал в десятку. (Может быть, ему надо было посвятить себя статистике.) Это случай низкого смещения и высокой дисперсии, показанный в правом нижнем углу. Подруга Бена Эшли попадает стабильно, но у нее есть склонность метить слишком высоко и вправо. Дисперсия у нее низкая, а смещение высокое (левый верхний угол). Коди никогда до этого не играл в дартс. Он попадает куда угодно, только не в центр. У него и высокое смещение, и высокая дисперсия (вверху справа).