Переобучение - откуда есть пошло

[tac]

Говоря о перцептроне Розенблатта, мы скатились, казалось бы к фундаментальной проблеме, которая на самом деле к перцептрону Розенблатта относится лишь косвенно. В результате дискуссий было предложено взять за определение термина, то что прочно закрепилось как в русском языке как переобучение, а в английском как overfit, определение из книги Mitchell, T. M. (1997). Machine Learning.

Цитата:

Definition: Given a hypothesis space $H$, a hypothesis $h \in H$ is said to overlit the training data if there exists some alternative hypothesis $h' \in H$, such that $h$ has smaller error than $h'$ over the training examples, but $h'$ has a smaller error than $h$ over the entire distribution of instances.

Важно, что читая эту книгу мы можем проследить как это понятие, постепенно от "Бритвы Оккама" применяемого при построении деревьев решений методом ID3 (Quinlan J., (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.) начали применять и к методу обратного распространения (далее просто backprop), понимая под этим некое переобучение.

В этом первом посте, хочу уделить внимание как небольшой предыстории о возникновении термина, так и тому, что из-за обиходного/разговорного употребления оно имеет очень не точный перевод на русский. Изначально под эти термином понималось разговорное понятие "подгонка".

Вот что пишет Дипсик о том, откуда взялся термин (сокращенно и выбрано мной):

Цитата:

Идея переобучения (overfitting) медленно кристаллизовалась в работах многих учёных, её корни лежат в области статистики, а не машинного обучения, которое сформировалось значительно позже. Владимир Вапник (Vladimir Vapnik) и Алексей Червоненкис (Alexey Chervonenkis) в 1970-х годах разработали строгую математическую теорию емкости моделей и обобщающей способности. Их работы дали теоретическое обоснование почему сложные модели (с высокой емкостью) склонны к переобучению на малых данных.

Мы конечно же посмотрим позже, что там у Вапника, но прежде просто прочитаем, что пишет Митчел, перед тем как дать свое определение в рамках алгоритма ID3.

Цитата:

We will say that a hypothesis overfits the training examples if some other hypothesis that fits the training examples less well actually performs better over the entire distribution of instances (i.e., including instances beyond the training set).

попробуем перевести

Цитата:

Мы будем говорить, что гипотеза превосходит обучающие примеры, если другая гипотеза, которая хуже соответствует обучающим примерам, на самом деле работает лучше во всем распределении примеров (т. е. включая примеры за пределами обучающего набора).

слова превосходит и соответствует, могут показаться не точными, но на самом деле они лучше всего отражают смысл. fit - это по сути и есть "подходить по размеру", в нашем контексте мы сказали бы точно описывает, но вот прямого аналога "переописывает" у нас нет, не по русски звучит.

Под гипотезой в контексте понимается, дерево решений построенное методом ID3 на всех обучающих примерах, которая и должна по сути описывать "примеры за пределами обучающего набора". Это то, что можно более точно назвать "моделью прогнозирования". Но проблема возникает, когда эта модель прогнозирования построена в не соответствии с Бритвой Оккама, а алгоритм ID3 предпочитает наиболее короткие деревья. Но никто не знает, справедлива ли вообще Бритва Оккама, не факт что самое короткое и экономное описание более правильно. Но даже если справедливо, то Митчел говорит, что можно просто построить разные деревья решений, которые формально будут соответствовать Бритве Оккама, но все равно по разному будут прогнозировать. И вот в этом контексте он и вводит выше приведенное определение.

Чтобы более естественно, дальше понимать о чем идет речь, переформулируем эти слова Митчела

Цитата:

Мы будем говорить, что модель прогнозирования переобучена на обучающих примерах, если существует другая модель прогнозирования, которая хуже соответствует обучающим примерам, но на самом деле работает лучше во всем распределении примеров (т. е. включая примеры за пределами обучающего набора).

заметим, что тут не идет речь о тестовой выборке, а идет речь о ВСЕМ пространстве возможных примеров.

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

Очевидных ответов у нас два:
1. Или причина в том, что сам алгоритм плохо строит прогнозируемую модель
2. Или причина в том, что обучающие примеры не репрезентативны по отношению ко ВСЕМ примерам за пределами обучающего набора

И у нас возникает вопрос: как отличить первый случай от второго.

[dsge]

Буквально в каждом современном учебнике по МЛ приводится избитый пример, где генерируются 10 данных полиномом 3-го порядка плюс шум, а подгоняеются эти данные полиномами 9-го порядка. На картинках хорошо видно поведение полиномов высокого порядка вне выборки.

[realeugene]

1. Пространство всех возможных примеров часто несчётно, а обучающая выборка всегда конечна, так что это определение бесполезно без уточнений, как сравнивать качества гипотезы на этих множествах?

2. Допустим, у нас есть соответствующие функционалы качества гипотез. Почти наверное любой алгоритм, вычисляющий гипотезу с максимальным качеством на обучающей выборке, промахнётся мимо глобального максимума функционала качества на всём пространстве примеров. Так что согласно этому определению, оверфиттинг неизбежен, а определение без уточнений в своём строгом формальном смысле бесполезно.

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

Цитата:

Paraskavedekatriaphobia1 (fear of Friday the 13th) , and superstitions in general, are perhaps the most illustrious cases of the human ability to overfit. Unfortunate events are memorable, and given a few such memorable events, it is natural to try and find an explanation.

"Learning From Data. A short course.", Yaser S. Abu-Mostafa и другие, 2012 https://amlbook.com/

[ozheredov]

realeugene в сообщении #1708763 писал(а):

Paraskavedekatriaphobia1 (fear of Friday the 13th)

Примером оверфита является способность видеть лица в рисунке обоев (само стремление оклеивать стены обоями с рисунком является примером андерфита).

[tac]

realeugene в сообщении #1708763 писал(а):

Пространство всех возможных примеров часто несчётно

Нейронные сети решают сугубо конечные задачи. Например, задачи классификации, где число признаков и классов конечно. Поэтому полный перебор вполне возможен (DeepBlue, LLM - тому пример). Но для построения теории вполне можно использовать тестовые задачи (назовем их полными), например, задачу четности на определенном количестве бит. Всегда можно посчитать четно ли количество бит среди скажем среди 16 бит, или нет. А за обучающую выборку взять случайных 50%, 40%, 30% от полного набора.

[realeugene]

tac в сообщении #1708775 писал(а):

Нейронные сети решают сугубо конечные задачи. Например, задачи классификации, где число признаков и классов конечно.

Когда признак представим плавающим или достаточно большим целым числом пространство признаков можно считать континуальным.

[tac]

realeugene в сообщении #1708763 писал(а):

Почти наверное любой алгоритм, вычисляющий гипотезу с максимальным качеством на обучающей выборке, промахнётся мимо глобального максимума функционала качества на всём пространстве примеров.

Никто не ожидает 100% точности от алгоритма, который не обучался на полном переборе. Но если допустить, как пишет Вапник

Цитата:

В пределе, наилучшим отображение будет таким, когда все точки, относящиеся к одному классу в исходном пространстве, перейдут в одну точку (а разные классы, естественно, в разные классы). При таком отображении задача обучения совсем вырождается, так как для обучения достаточно показать по одному представителю каждого класса.

соответственно это является "идеальной мечтой", но построение "некого" как он называет спрямляющего пространства, позволяет решать вопрос об обобщении не прибегая к полному перебору.

-- Пн ноя 10, 2025 02:57:46 --

realeugene в сообщении #1708779 писал(а):

Когда признак представим плавающим или достаточно большим целым числом пространство признаков можно считать континуальным.

Равно и наоборот, любую непрерывную величину мы можем разбить на действительно важные понятия "нечеткой логики" (рост малый, средний, высокий, женщина/мужчина, мокро, сухо ).

[realeugene]

tac в сообщении #1708780 писал(а):

Равно и наоборот, любую непрерывную величину мы можем разбить на действительно важные понятия "нечеткой логики" (рост малый, средний, высокий, женщина/мужчина, мокро, сухо ).

И упрёмся в классическую задачу ручной генерации адекватных признаков по входным данным.

-- 10.11.2025, 02:10 --

tac в сообщении #1708780 писал(а):

соответственно это является "идеальной мечтой", но построение "некого" как он называет спрямляющего пространства, позволяет решать вопрос об обобщении не прибегая к полному перебору.

Никто не мешает и вручную эвристики писать, вместо машинного обучения. Только это прошлый век.

[tac]

realeugene в сообщении #1708783 писал(а):

Никто не мешает и вручную эвристики писать, вместо машинного обучения.

Зачем в ручную, просто детерминированные, а не непрерывные.

[ozheredov]

realeugene в сообщении #1708783 писал(а):

И упрёмся в классическую задачу ручной генерации адекватных признаков по входным данным.

Границы ищутся автоматически. Баловался придумыванием метода оптимизации границ в рамках своего алгоритма генерации решающий деревьев, это работало. В частности, на задаче Kaggle Titanic железко бодро определяло возраст согласия ниже которого человек, скорее всего, считался ребёнком и это влияло на вероятность выживания, поскольку его без особых препятствий пропускали на шлюпку.

[realeugene]

ozheredov в сообщении #1708786 писал(а):

Границы ищутся автоматически.

Чтобы автоматически выделять границы вам нужен некоторый функционал качества гипотез на исходном непрерывном распределении. Вопрос был об этом, причём, в контексте попытки формального определения переобучения из Митчела, которое мне представляется неполной, а значит, в качестве формального определения бессмысленной. Требуются какие-то интуитивные неформальные домысливания.

Замечу также, что обсуждаемый функционал из определения Митчела посчитать на практике обычно невозможно, так как само распределение не известно. Его оценивают с большим или меньшим успехом по тестовой выборке. Со своими шумами и рисками не заметить переобучение.

[mihaild]

realeugene в сообщении #1708763 писал(а):

Почти наверное любой алгоритм, вычисляющий гипотезу с максимальным качеством на обучающей выборке, промахнётся мимо глобального максимума функционала качества на всём пространстве примеров

Почти всегда, когда говорят о переобучении, рассматривают небольшое пространство гипотез. Например, если у нас итеративный алгоритм построения деревьев - то деревья, получающиеся на каждом шаге.

realeugene в сообщении #1708801 писал(а):

Замечу также, что обсуждаемый функционал из определения Митчела посчитать на практике обычно невозможно, так как само распределение не известно

Опять же, как правило, в этой области говорят, что общее распределение - это обучающая и тестовая выборки, а не реальный мир.
В связи с чем возникает такой эффект, как "переобучение под валидейт", когда, подбирая параметры с помощью валидации на тестовой выборке, мы по сути учим мета-алгоритм на ней. И если у нас есть еще какая-то выборка, то с её учетом уже этот мета-алгоритм может переобучиться.

Вся идея с "более простые модели предпочтительнее" основана на очень простом соображении. Более сложных моделей много. Поэтому для выбора из них нужно больше данных. В частности, угадать гипотезу из множества разных сложных гипотез, которые точно описывают обучающие данные, можно только чисто случайно. А вот если у нас есть множество сравнительно простых гипотез, гипотезы из которого могут хорошо описать сравнительно немного вариантов данных, но в нём случайно нашлась гипотеза, которая конкретно наши данные описывает хорошо - это уже интересно.
С байесианской точки зрения это описывается как низкая априорная вероятность сложных гипотез (как минимум у большинства сложных гипотез априорная вероятность низкая, просто потому, что их много; ну и, как правило, нет оснований считать какие-то из них выделенными). Соответственно если у нас есть простая гипотеза, хорошо описывающая данные - её апостериорная вероятность выше, чем у более сложной, даже если сложная описывает данные чуть лучше.

[realeugene]

mihaild в сообщении #1708816 писал(а):

Почти всегда, когда говорят о переобучении, рассматривают небольшое пространство гипотез.

Дегко проверить гуглением, что про оверфиттинг пишут и в контексте глубокого обучения. Пространство гипотез огромно. И чем больше пространство гипотез - тем легче нарваться на оверфиттинг, когда обучающих данных недостаточно чтобы покрыть пространство примеров достаточно плотно.

mihaild в сообщении #1708816 писал(а):

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

Ввиду наличия под рукой только выборок. Но интересно поведение системы именно в реальном мире. И не только машинного обучения. И в обсуждаемом определении упоминается всё (вероятностное) пространство возможных примеров, а не выборки из него.

Кстати есть же и более-менее формализованные теории регуляризации как выбирать достаточные тестовые выборки и достаточные пространства гипотез. В них вообще могут рассматриваться пространства гипотез с различным числом параметров, и более сложные гипотезы штрафуются. Байесовский подход, как я понимаю, требует какого-то априорного знания про пространство гипотез.

Проблема с тестовыми выборками в том, что чем больше гипотез по ним уже валидировали - тем сильнее они из тестовых превращаются в обучающие. В идеале нужно их каждый раз выкидывать и формировать новую чистую тестовую выборку.

[mihaild]

realeugene в сообщении #1708820 писал(а):

Дегко проверить гуглением, что про оверфиттинг пишут и в контексте глубокого обучения. Пространство гипотез огромно

Нет, когда рисуют график переобучения - на нём только модели, которые были в ходе обучения (что логично, откуда еще брать веса?). Пространство гипотез при этом - не все возможные веса, а только реально посещенные градиентным спуском.

realeugene в сообщении #1708820 писал(а):

И в обсуждаемом определении упоминается всё (вероятностное) пространство возможных примеров, а не выборки из него.

Никто не запрещает рассмотреть в качестве пространства возможных примеров нашу выборку (с равномерным распределением).

realeugene в сообщении #1708820 писал(а):

Байесовский подход, как я понимаю, требует какого-то априорного знания про пространство гипотез

Любой подход этого требует. Только байесовский требует этого в явном виде, а другие заметают под ковер. Опять сошлюсь на мой любимый текст Everything that works works because it's bayesian. Собственно утверждается, что SGD соответствует каким-то "хорошим" приорам (что не очень полезное утверждение, потому что понятно, что он соответствует каким-то приорам, а какие конкретно их свойства важны - непонятно).

[realeugene]

mihaild в сообщении #1708821 писал(а):

Нет, когда рисуют график переобучения

Это всё ещё вероятностный критерий, пытающийся предсказать качество модели на будущих данных.

-- 10.11.2025, 15:29 --

mihaild в сообщении #1708821 писал(а):

Никто не запрещает рассмотреть в качестве пространства возможных примеров нашу выборку (с равномерным распределением).

Только это уже искусственно суженная задача. Практическая польза от любого обучения - работающие модели реального мира. Именно они в результате приносят деньги.

Методы качественного сбора данных - отдельная наука. Физиков этому учат специально.