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

На практике анализ по Вэлианту обычно дает очень пессимистичные результаты и требует больше данных, чем есть в наличии. Как же решить, верить ли обучающемуся алгоритму? Все просто: не верьте, пока не проверите результаты на данных, которые обучающийся алгоритм не видел. Если схемы, выдвинутые им в качестве гипотезы, окажутся верны и для новых данных, можно быть уверенным, что они реальные. В противном случае вы будете знать, что имело место переобучение. Это просто применение научного метода к машинному обучению: новой теории мало объяснить прошлый опыт (такую состряпать несложно) — она должна также делать новые предсказания, а принимают ее только после того, как предсказания были экспериментально подтверждены. (И даже тогда лишь предварительно, потому что будущие данные по-прежнему могут ее фальсифицировать.)

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

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

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

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