будут дальше от новых точек.
Добавим новые обучающие точки. Линия, то есть многочлен первой степени, практически не меняет положения: ее ошибка обучения практически идентична той, что получена с семью точками. С другой стороны, ошибка обучения для многочлена четвертой степени увеличивается, потому что он больше не может проходить близко ко всем точкам. Но по мере того, как волны его графика сглаживаются, он будет лучше работать с тестовым набором дополнительных оценок.
Какие уроки можно извлечь из всего этого, чтобы выбрать наиболее эффективную систему на основе количества обучающих примеров?
Вернемся к рисунку 4.11. Слева от линии более эффективна малая модель, поскольку ее ошибка проверки меньше. Поэтому, если у вас мало данных, лучше использовать именно ее. Справа от линии лучше большая модель. Если у вас много данных, лучше использовать большую модель. Когда количество примеров превышает некоторое пороговое значение, кривая больше не может пройти через все точки, и модель становится способной к интерполяции, поэтому при каждом количестве примеров мы должны искать компромисс для выбора модели. Другими словами, для того чтобы система обнаружила структуру, лежащую в основе данных, она должна выйти за рамки своей способности выучить все примеры «наизусть» без «понимания». А для этого системе необходимо показать достаточно много примеров, чтобы она начала делать ошибки.
Рис. 4.12. «Недообучение» и «переобучение»
Для того же количества обучающих данных ошибка обучения уменьшается по мере использования более сложных моделей. Но зато ошибка на проверочном наборе проходит минимум и возрастает. Это возрастание известно как «переобучение»: машина узнает слишком много деталей из обучающих примеров и теряет общий аспект характера задачи, которую вы пытаетесь выполнить. Она начинает учить наизусть, вместо того чтобы пытаться придумывать правила. Нижняя точка этой кривой указывает на прицип выбора модели.
Для заданного количества обучающих примеров чем больше емкость модели, тем меньше ошибка обучения. В то же время, чем больше емкость модели, тем больше разница между ошибкой проверки и ошибкой обучения. Таким образом, существует оптимальная емкость, являющаяся лучшим компромиссом между этими двумя состояниями, что дает наименьшую ошибку проверки.
Представьте себе многочлен бесконечной степени, с огромной способностью к обучению: ошибка обучения всегда равна 0; сколько бы оценок он ни получил, многочлен может пройти через все точки. Но он никогда не сможет обобщить. Многочлен выучит все наизусть, как плохой ученик учится без понимания. Учитель повторяет ему таблицу умножения, и тот, вместо того чтобы знать, как умножать, запоминает результаты.
Теорема о том, что «бесплатного обеда не бывает» резюмирует это правило следующим образом: обучающаяся машина, способная обучаться всему, на самом деле вообще не может ничему научиться. Дело в том, что ей понадобится неоправданно большое количество обучающих примеров, чтобы перестать перебирать все точки и начать находить основное правило, то есть обобщать. Аналогично, люди с прекрасной памятью часто менее склонны к самостоятельному выявлению правил и закономерностей.
Чтобы обучить машину с определенным набором данных, необходимо найти баланс между двумя ограничениями:
1. Нужно, чтобы модель была достаточно мощной (в ней было бы достаточно «кнопок» для настройки), чтобы она смогла выучить весь обучающий набор, то есть достаточно близко подойти ко всем точкам.
2. Но модель должна быть не слишком мощной, чтобы она не пыталась точно пройти через все точки, делая слишком много «волн» и скрывая общую закономерность за частными вариантами – это бы сделало ее неспособной верно интерполировать.
Формула Вапника предполагает три концепции:
1. Ошибка обучения, или эмпирическая ошибка. Это производительность системы на наборе примеров, на котором она была обучена.
2. Ошибка теста, то есть производительность системы по дополнительным точкам, которые она не «видела» во время обучения. Если у нас есть бесконечное количество точек, мы получаем хорошую оценку ошибки, которую система могла бы выдавать в реальной ситуации.
3. Емкость модели, то есть мера количества функций, которые модель может выполнять при изменении параметров всех возможных конфигураций. Эта способность называется измерением Вапника-Червоненкиса.
Формула Вапника записывается так:
Etest < Etrain + k * h/(p ** alfa)
где
Etest: ошибка теста
Etrain: ошибка обучения
k: постоянная
h: размерность Вапника-Червоненкиса («сложность», или «емкость» модели) p: количество обучающих примеров
alfa: константа от 1/2 до 1 в зависимости от характера проблемы.
Эта формула позволяет объяснить закономерности, показанные на рисунках 4.11 и 4.12.
Головокружительные булевы функции
Теоретически существует огромное количество функций, в том числе очень простых, которые могут обрабатывать входные примеры. Но, как мы только что видели, слишком мощная машина, способная применить в качестве модели любую функцию, не может правильно обобщать, если не дать ей достаточно большое количество примеров обучения. В результате, если есть только разумное количество примеров, машина должна иметь ограничения и быть приспособленной к изучению соотношений (иногда говорят «представлений») входа-выхода. Однако эти ограничения в основном связаны с архитектурой модели.
Рис. 4.13. Функциональное пространство.
Набор функций, представляемых (то есть вычислимых или аппроксимируемых) моделью, – это небольшое подмножество пространства всех возможных функций. Данное подмножество во многом определяется архитектурой модели. Модель большой емкости может представлять больший набор функций, чем модель меньшей емкости.
Рис. 4.14. Таблица булевых функций
Булева функция принимает n-е количество входных битов и производит 1 выходной бит. Двухбитная булева функция может быть задана с помощью четырехстрочной таблицы, которая дает выходное значение (0 или 1) для каждой из 4 входных конфигураций (0 0), (0 1), (1 0) и (1 1). Таким образом, для этих 4 входных конфигураций существует 16 возможных выходных конфигураций (2 ** 4), то есть 16 возможных функций по 2 бита, каждая из которых представлена последовательностью из 4 бит. Каждый дополнительный входной бит удваивает количество строк в таблице. В общем, для n-битной функции существует 2 ** n входных конфигураций и 2 ** (2 ** n) возможных булевых функции.
Таким образом, машина должна иметь априорную структуру, которая позволяет ей изучать полезные функции на нескольких примерах. Но из-за такой структуры машина сможет отображать только очень небольшое подмножество всех возможных функций.
Чтобы убедиться в этом, давайте возьмем случай двоичной функции, называемой «булевой функцией»[49], вход которой состоит из последовательности 0 и 1. Выход равен 0 или 1. Булевы функции интересны тем, что они имеют конечное количество входов и могут быть вычислены. Булева функция используется для операций между двоичными переменными. Каждое значение имеет определенную роль. 0 и 1 не взаимозаменяемы. Итак, (0,1) отличается от (1,0).
Примеры возможных функций
Возьмем колонку № 8 на рис. 4.14.
