суббота, 3 декабря 2011 г.

Overfitting и Underfitting

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

Общая идея

Допустим, у нас есть выборка из 5-ти элементов. И на основании их нужно построить интерполяцию, позволяющую предсказать значения в точках, отличных от известных. Например мы будем использовать нижеописанную выборку, и попробуем найти 3 функции (простая линейная, средней сложности парабола, и функция 4-й степени, проходящая через все 5 точек):

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

Вторая функция на рассматриваемом участке легла хорошо, с малой погрешностью, и не через все точки.

Третья функция точно проходит через все точки, но ужасно работает вне рассматриваемых точек.

Получается, что сложность, которая нужна в поставленной задаче имеет какой-то наиболее эффективный участок. Линейная функция имеет малую точность, и недостаток этой сложности и есть Underfitting. Результат плохо работает по сравнению с большей сложностью.

Третья функция имеет слишком высокую сложность — Overfitting. Она слишком хорошо работает на обученных примерах и ужасно работает на примерах, которые находятся вне обучения.

Если рассмотреть то же самое явление на плоскости (что возможно более наглядно), то оно имеет вид:

Идея в понятиях

Если мы очень жестко определяем понятие, то рискуем нарваться на Overfitting. Если определение слишком слабое, то можем получить Underfitting.

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

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

Иногда въедливость вида «было названы примеры только A,B,C и D, а значит, никаких E, даже если оно очень похоже!» является результатом такого вот Overfitting'a. Или слишком сильное обобщение — результат Underfitting'a («мне разрешили есть сыр, а это молочный продукт, поэтому мне можно пить молоко, и даже есть молочный шоколад!»).

Если мы хотим уменьшить вероятность ошибки при выборе положительного результата, то мы можем взять понятие, которое имеет свойство большего Overfitting'a. Если хотим более наверняка захватывать все искомые понятия, то лучше взять более сильное по Underfitting. Например, если мы смотрим на неопознанный летающий объект, и при этом это может быть как свой, так и чужой, то в боевой обстановке может быть более рационально сбивать все, что более-менее похоже на врага, а если мирное время, то лучше сбивать только если это известно более утвердительно, так как лучше снизить риск сбить гражданский объект.