Переобучение возникает, когда у вас слишком много гипотез и недостаточно данных, чтобы их различить. Проблема в том, что даже в простых конъюнктивных обучающихся алгоритмах число гипотез растет экспоненциально с числом атрибутов. Экспоненциальный рост — страшная сила. Бактерия E. coli может делиться надвое примерно каждые 15 минут. Если бы у нее было достаточно питательных веществ, она бы за день разрослась в бактериальную массу размером с нашу планету. Когда количество элементов, необходимых алгоритму для работы, растет в геометрической прогрессии с увеличением размера вводных данных, информатики называют это комбинаторным взрывом и бегут в укрытие. В машинном обучении количество возможных частных случаев какого-либо понятия — экспоненциальная функция числа атрибутов: если атрибуты булевы, с каждым новым атрибутом число возможных частных случаев удваивается, каждый случай расширяется для «да» или «нет» этого атрибута. В свою очередь, число возможных понятий — это экспоненциальная функция числа возможных частных случаев: поскольку понятие отмечает каждый случай как положительный или отрицательный, добавление частного случая удваивает число возможных понятий. В результате число понятий — это экспоненциальная функция экспоненциальной функции числа атрибутов! Другими словами, машинное обучение — комбинаторный взрыв комбинаторных взрывов. Может, лучше просто сдаться и не тратить времени на такую безнадежную проблему?
К счастью, при обучении получается «отрубить голову» одной из экспонент и оставить только «обычную» единичную неразрешимую экспоненциальную проблему. Представьте, что у вас полная сумка листочков с определениями понятий и вы достаете наугад одно из них, чтобы посмотреть, насколько хорошо оно подходит к данным. Вероятность, что плохое определение подойдет всей тысяче примеров в ваших данных, не больше, чем ситуация, когда монетка тысячу раз подряд падает орлом вверх. «У стула четыре ноги, и он красный, либо у него есть сиденье, но нет ножек», вероятно, подойдет к некоторым, но не ко всем стульям, которые вы видели, а также подойдет к некоторым, но не ко всем другим предметам. Поэтому, если случайное определение корректно подходит к тысяче примеров, крайне маловероятно, что оно неправильное. По крайней мере, оно достаточно близко к истине. А если определение согласуется с миллионом примеров, оно практически наверняка верно, иначе почему оно подходит ко всем этим примерам?
Конечно, реальный алгоритм машинного обучения не просто берет из мешка одно произвольное определение: он пробует их целую охапку, и отбор не происходит произвольным образом. Чем больше определений пробует алгоритм, тем больше вероятность, что одно из них подойдет ко всем примерам хотя бы случайно. Если сделать миллион повторений по тысяче бросков монетки, практически наверняка хотя бы одно повторение даст все орлы, а миллион — это достаточно скромное число гипотез для рассмотрения: оно примерно соответствует числу возможных конъюнктивных понятий, если у примеров всего 13 атрибутов. (Обратите внимание, что вам не надо явно пробовать понятия одно за другим. Если лучшие, которые вы нашли с использованием конъюнктивного обучающегося алгоритма, подходят ко всем примерам, результат будет тот же самый.)
Итого: обучение — гонка между количеством данных, имеющихся в вашем распоряжении, и количеством рассматриваемых вами гипотез. Увеличение объема данных экспоненциально уменьшает количество прошедших проверку гипотез, но, если гипотез изначально много, в конце все равно может остаться некоторое количество плохих. Есть золотое правило: если обучающийся алгоритм учитывает только экспоненциальное число гипотез (например, все возможные конъюнктивные понятия), то экспоненциальный выигрыш от данных решает проблему, и все в порядке, при условии, что у вас множество примеров и не очень много атрибутов. С другой стороны, если алгоритм рассматривает дважды экспоненциальное число (например, все возможные наборы правил), тогда данные отменяют только одну из экспонент, и трудности остаются. Можно даже заранее решить, сколько примеров понадобится, чтобы быть достаточно уверенным, что выбранная обучающимся алгоритмом гипотеза очень близка к истинной, при условии, что к ней подходят все данные. Другими словами, чтобы гипотеза была, вероятно, приблизительно правильной. За изобретение этого типа анализа гарвардский ученый Лесли Вэлиант получил премию Тьюринга — Нобелевскую премию по информатике. Его книга на эту тему называется Probably Approximately Correct («Возможно, приблизительно верно»).
Точность, которой можно доверять
На практике анализ по Вэлианту обычно дает очень пессимистичные результаты и требует больше данных, чем есть в наличии. Как же решить, верить ли обучающемуся алгоритму? Все просто: не верьте, пока не проверите результаты на данных, которые обучающийся алгоритм не видел. Если схемы, выдвинутые им в качестве гипотезы, окажутся верны и для новых данных, можно быть уверенным, что они реальные. В противном случае вы будете знать, что имело место переобучение. Это просто применение научного метода к машинному обучению: новой теории мало объяснить прошлый опыт (такую состряпать несложно) — она должна также делать новые предсказания, а принимают ее только после того, как предсказания были экспериментально подтверждены. (И даже тогда лишь предварительно, потому что будущие данные по-прежнему могут ее фальсифицировать.)
Общая теория относительности Эйнштейна стала общепринятой, только когда Артур Эддингтон эмпирически подтвердил, что Солнце отклоняет свет далеких звезд. Но вам не надо ждать, пока поступят новые данные, чтобы решить, можно ли доверять алгоритму машинного обучения. Лучше взять все данные, которые у вас есть, и произвольно разделить их на обучающее множество, которое вы дадите алгоритму, и тестовое множество, которое надо cпрятать от него и использовать для верификации точности. Точность на скрытых данных — золотой стандарт в машинном обучении. Можно написать статью о том, какой прекрасный новый обучающийся алгоритм вы придумали, но, если на скрытых данных он значительно не превосходит уже имеющиеся, статью никто не опубликует.
Точность на данных, которые алгоритм еще не видел, — настолько строгий критерий, что многие научные теории его не проходят. От этого они не становятся бесполезными, ведь наука — это не только предсказания, но и объяснение и понимание, однако в итоге, если модели не делают точных прогнозов на новых данных, нельзя быть уверенным, что лежащие в основе явления по-настоящему поняты и объяснены. А для машинного обучения тестирование на скрытых данных незаменимо, потому что это единственный способ определить, случилось ли с обучающимся алгоритмом переобучение.
Но и точность на тестовой выборке не гарантия от ошибок. Согласно легенде, один из ранних простых обучающихся алгоритмов со стопроцентной точностью отличал танки и в обучающей, и в тестовой выборке, каждая из которых состояла из 100 изображений. Удивительно или подозрительно? Оказалось, что все картинки с танками были светлее, и это все, что увидел обучающийся алгоритм. В наши дни выборки данных крупнее, но качество сбора данных не обязательно лучше, поэтому нельзя терять бдительность. Реалистичная эмпирическая оценка сыграла важную роль в превращении машинного обучения из молодой дисциплины в зрелую науку. До конца 1980-х исследователи каждого из «племен» в основном верили собственным аргументам, исходили из того, что их парадигма фундаментально лучше, и мало общались с другими лагерями. Затем символисты, например Рэй Муни и Джуд Шавлик, начали систематически сравнивать разные алгоритмы на тех же наборах данных, и — вот сюрприз! — оказалось, что однозначного победителя нет. Сегодня соперничество продолжается, но перекрестное опыление встречается гораздо чаще. Общие экспериментальные стандарты и большой банк наборов данных, поддерживаемый группой машинного обучения в Калифорнийском университете в Ирвайне, творят чудеса и толкают науку вперед. Как мы увидим, лучшие
