Педро Домингос - Верховный алгоритм

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

Точность на данных, которые алгоритм еще не видел, — настолько строгий критерий, что многие научные теории его не проходят. От этого они не становятся бесполезными, ведь наука — это не только предсказания, но и объяснение и понимание, однако в итоге, если модели не делают точных прогнозов на новых данных, нельзя быть уверенным, что лежащие в основе явления по-настоящему поняты и объяснены. А для машинного обучения тестирование на скрытых данных незаменимо, потому что это единственный способ определить, случилось ли с обучающимся алгоритмом переобучение.

Но и точность на тестовой выборке не гарантия от ошибок. Согласно легенде, один из ранних простых обучающихся алгоритмов со стопроцентной точностью отличал танки и в обучающей, и в тестовой выборке, каждая из которых состояла из 100 изображений. Удивительно или подозрительно? Оказалось, что все картинки с танками были светлее, и это все, что увидел обучающийся алгоритм. В наши дни выборки данных крупнее, но качество сбора данных не обязательно лучше, по­этому нельзя терять бдительность. Реалистичная эмпирическая оценка сыграла важную роль в превращении машинного обучения из молодой дисциплины в зрелую науку. До конца 1980-х исследователи каждого из «племен» в основном верили собственным аргументам, исходили из того, что их парадигма фундаментально лучше, и мало общались с другими лагерями. Затем символисты, например Рэй Муни и Джуд Шавлик, начали систематически сравнивать разные алгоритмы на тех же наборах данных, и — вот сюрприз! — оказалось, что однозначного победителя нет. Сегодня соперничество продолжается, но перекрестное опыление встречается гораздо чаще. Общие экспериментальные стандарты и большой банк наборов данных, поддерживаемый группой машинного обучения в Калифорнийском университете в Ирвайне, творят чудеса и толкают науку вперед. Как мы увидим, лучшие шансы создать универсальный обучающийся алгоритм — у синтеза идей из разных парадигм.

Конечно, мало уметь выявить переобучение: прежде всего надо научить­ся его избегать. Это означает вовремя остановить даже потенциально превосходную подгонку под данные. Один из методов — применение тестов статистической значимости для проверки того, что схемы, которые мы видим, действительно существуют. Например, и правило, включающее 300 положительных примеров против 100 отрицательных, и правило, включающее три положительных примера против одного отрицательного, на обучающих данных точны в 75 процентах, однако первое правило почти наверняка лучше, чем бросок монетки, в то время как второе — нет, поскольку четыре броска «правильной» монетки легко могут дать три орла. Если в какой-то момент при составлении правила не получается найти условия, которые значительно улучшили бы его точность, нужно просто остановиться, даже если оно все еще охватывает некоторые отрицательные примеры. Точность правила на обучающей выборке окажется меньше, но, вероятно, оно будет более точным обобщением, а именно это нас на самом деле интересует.

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

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

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