Введение

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

Мотивация

Рассмотрим такую задачу. У нас есть яблоки двух классов — вкусные и не вкусные, 1 и 0. Яблоки обладают признаками — цветом и размером. Цвет изменятся непрерывно от 0 до 1, т.е. 0 -полностью зеленое яблоко, 1 — полностью красное. Размер может меняться аналогично, 0 — яблоко маленькое, 1 — большое. Мы хотели бы разработать алгоритм, который бы получал на вход цвет и размер, а на выходе отдавал класс яблока — вкусное оно или нет. Весьма желательно, чтобы число ошибок при этом было чем меньше тем лучше. При этом мы обладаем конечным списком, в котором указаны исторические данные о цвете, размере и классе яблок. Как бы мы могли решать такую задачу?

Логический подход

Решая нашу задачу, первый метод, который возможно придет на ум, может быть такой: давайте вручную составим правила типа if-else и в зависимост�� от значений цвета и размера будем присваивать яблоку определенный класс. Т.е. у нас есть предпосылки — это цвет и размер, и есть следствие — вкус яблока. Вполне разумно, когда признаков немного и можно на глаз оценить пороги для сравнения. Но может случится так, что придумать четкие условия не получится, и из данных не очевидно какие пороги брать, да и число признаков может увеличиваться в перспективе. А что делать, если в нашем списке с историческими данными, мы обнаружили два яблока с одинаковыми цветом и размером, но одно помечено как вкусное, а другое нет? Таким образом наш первый метод не настолько гибкий и масштабируемый, как нам бы хотелось.

Обозначения

Введем следующую нотацию. Будем обозначать $i$ -ое яблоко как $x_i$ . В свою очередь каждый $x_i$ состоит из двух чисел — цвета и размера. Этот факт мы будем обозначать парой чисел: $x_i = (color,size)$ . Класс каждого $i$ -го яблока мы обозначим как $y_i$ . Список с историческими данными обозначим буквой $S$ , длина этого списка равна $N$ . $i$ -ый элемент этого списка есть значение признаков яблока и его класс. Т.е. $S = \{(x_1,y_1), \dots ,(x_N,y_N)\} = \{((color,size)_1,y_1), \dots ,((color,size)_N,y_N)\}$ . Так же будем называть $S$ выборкой. Большими буквами $X$ и $Y$ мы обозначим переменные, которые могут принимать значения конкретного признака и класса. Веедем новое понятие — решающее правило $a(x)$ есть функция, которая принимает на вход значение цвета и размера $x$ , а на выходе возвращает метку класса: $a:X\rightarrow Y$

Вероятностный подход

Развивая идею логического метода с предпосылками и следствиями, зададим себе вопрос — а какова вероятность того, что $m$ -ое яблоко, которое не принадлежит нашей выборке $S$ будет вкусное, при условии измеренных значений цвета и размера? В нотации теории вероятностей этот вопрос можно записать так:

$p(Y=1|X=x_m) = ?$

В этом выражении можно интерпретировать $X$ как посылку, $Y$ как следствие, но переход от посылки к следствию будет подчинятся вероятностным законам, а не логическим. Т.е. вместо таблицы истинности с булевскими значениями 0 и 1 для класса, будут значения вероятности, которые принимают значения от 0 до 1. Применим формулу Байеса и получим следующее выражение:

$p(Y=1|X=x_m) = \frac{p(X=x_m | Y=1)p(Y=1)}{p(X=x_m)}$

Рассмотрим правую часть этого выражения более подробно. Множитель $p(Y=1)$ называется априорной вероятностью и означает вероятность встретить вкусное яблоко среди всех возможных яблок. Априорная вероятность встретить невкусное яблоко есть $p(Y=0) = 1 -p(Y=1)$ . Эта вероятность может отражать наше личное знание о том, как распределены вкусные и невкусные яблоки в природе. Например, по нашему прошлому опыту мы знаем, что 80% всех яблок — вкусные. Или мы можем оценить это значение просто посчитав долю вкусных яблок в нашем списке с историческими данными S. Следующий множитель — $p(X=x_m | Y=1)$ показывает, насколько вероятно получить конкретное значение цвета и размера $x_m$ для яблока класса 1. Это выражение так же называется функцией правдоподобия и может иметь вид какого-нибудь конкретного распределения, например, нормального. Знаменатель $p(X=x_m)$ мы используем в качестве нормировочной константы, что бы искомая вероятность $p(Y=1|X=x_m)$ изменялась в пределах от 0 до 1. Нашей конечной целью является не поиск вероятностей, а поиск решающего правила, которое бы сразу давало нам класс. Конечный вид решающего правила зависит от того, какие значения и параметры нам известны. Например, мы можем знать только значения априорной вероятности, а остальные значения оценить невозможно. Тогда решающее правило будет такое — ставить всем яблокам значение того класса, для которого априорная вероятность наибольшая. Т.е. если мы знаем, что 80% яблок в природе вкусные, то каждому яблоку ставим класс 1. Тогда наша ошибка составит 20%. Если же мы к тому же можем оценить значения функции правдоподобия $p(X=x_m | Y=1)$, то можем и найти значение искомой вероятности $p(Y=1|X=x_m)$ по формуле Байеса, как написано сверху. Решающее правило здесь будет таким: поставить метку того класса, для которого вероятность $p(Y=1|X=x_m)$ максимальна:

$a(x_m) = 1, если \ p(Y=1|X=x_m) > p(Y=0|X=x_m),$

$a(x_m) = 0, если \ p(Y=1|X=x_m) < p(Y=0|X=x_m)$

Это правило назовем Байесовским классификатором. Поскольку мы имеем дело с вероятностями, то даже большое значение вероятности $p(Y=1|X=x_m)$ не дает гарантий, что ��блоко $x_m$ не принадлежит к классу 0. Оценим вероятность ошибки на яблоке $x_m$ следующим образом: если решающее правило вернуло значение класса равное 1, то вероятность ошибиться будет $p(Y=0|X=x_m)$ и наоборот:

$p(error|x_m) = p(Y=0|X=x_m), если \ a(x_m) = 1,$

$p(error|x_m) = p(Y=1|X=x_m), если \ a(x_m) = 0$

Нас интересует вероятность ошибки классификатора не только на данном конкретном примере, но и вообще для всех возможных яблок:

$p(error) = \int{p(error|x)p(x)dx}$

Это выражение является математическим ожидаем ошибки $p(error|x)$ . Итак, решая исходную проблему мы пришли к байесовскому классификатору, но какие у него есть недостатки? Главная проблема — оценить из данных условную вероятность $p(X=x_m | Y=1)$ . В нашем случае мы представляем объект парой чисел — цвет и размер, но в более сложных задачах размерность признаков может быть в разы выше и для оценки вероятности многомерной случайной величины может не хватить числа наблюдений из нашего списка с историческими данными. Далее мы попробуем обобщить наше понятие ошибки классификатора, а так же посмотрим, можно ли подобрать какой-либо другой классификатор для решения проблемы.

Потери от ошибок классификатора

Предположим, что у нас уже есть какое-либо решающее правило $a(x)$ . Тогда оно может совершить два типа ошибок — первый, это причислить объект к классу 0, у которого реальный класс 1 и наоборот, причислить объект к классу 1, у которого реальный класс 0. В некоторых задачах бывает важно различать эти случаи. Например, мы страдаем больше от того, что яблоко, помеченное как вкусное, оказалось невкусным и наоборот. Степень нашего дискомфорта от обманутых ожиданий мы формализуем в понятии $\it потеря.$ Более обще — у нас есть функция потерь, которая возвращает число для каждой ошибки классификатора. Пусть $\alpha$ — реальная метка класса. Тогда функция потерь $\lambda(\alpha_i|a(x))$ возвращает величину потерь для реальной метки класса $\alpha_i$ и значения нашего решающего правила $a(x)$ . Пример применения этой функции — берем из яблоко с известным классом $\alpha$ , передаем яблоко на вход нашему решающему правилу $a(x)$ , получаем оценку класса от решающего правила, если значения $a(x)$ и $\alpha$ совпали, то считаем что классификатор не ошибся и потерь нет, если значения не совпадают, то величину потерь скажет наша функция $\lambda(\alpha_i|a(x)).$

Условный и байесовский риск

Теперь, когда у нас есть функция потерь и мы знаем, сколько мы теряем от неправильной классификации объекта $x$ , было бы неплохо понять, сколько мы теряем в среднем, на многих объектах. Если мы знаем величину $p(Y=1|X=x_m)$ — вероятность того, что $m$ -ое яблоко будет вкусное, при условии измеренных значений цвета и размера, а так же реальное значение класса(например возьмем яблоко из выборки S, см. в начале статьи), то можем ввести понятие условного риска. Условный риск есть средняя величина потерь на объекте $x$ для решающего правила $a(x)$ :

В нашем случае бинарной классификации когда $a(x) = 1$ получается:

Когда a(x) =0

Чтобы посчитать средние потери на всех возможных объектах, вводится понятие байесовского риска, который является математическим ожиданием условного риска:

$R(a(x)) = \int{R(a(x)|x)p(x)dx}$

Выше мы описывали решающее правило, которое относит объект к тому классу, который имеет наибольшее значение вероятности $p(Y|X).$ Такое правило доставляет минимум нашим средним потерям(байесовскому риску), поэтому Байесовский классификатор является оптимальным с точки зрения введенного нами функционала риска. Это значит, что Байесовский классификатор имеет наименьшую возможную ошибку классификации.

Некоторые типовые функции потерь

Одной из наиболее частовстречающихся функций потерь является симметричная функция, когда потери от первого и второго типов ошибок равнозначны. Например, функция потерь 1-0 (zero-one loss) определяется так:

$\lambda(\alpha = 1|a(x) = 0) = 1$

$\lambda(\alpha = 0|a(x) = 1) = 1$

$\lambda(\alpha = 1|a(x) = 1) = 0$

$\lambda(\alpha = 0|a(x) = 0) = 0$

Тогда условный риск для a(x) = 1 будет просто значением вероятности получить класс 0 на объектке $x$ :

$R(a(x) = 1|x) = 1*p(Y=0|X=x) + 0*p(Y=1|X=x) = p(Y=0|X=x)$

Аналогично для a(x) = 0:

$R(a(x) = 0|x) = p(Y=1|X=x)$

Функция потерь 1-0 принимает значение 1, есл�� классификатор делает ошибку на объекте и 0 если не делает. Теперь сделаем так, чтобы значение на ошибке равнялось не 1, а другой функции Q, зависящей от решающего правила и реальной метки класса:

$\lambda(\alpha = 0|a(x) = 1) = Q(\alpha = 0 , a(x) = 1)$

$\lambda(\alpha = 1|a(x) = 0) = Q(\alpha = 1, a(x) = 0)$

$\lambda(\alpha = 1|a(x) = 1) = 0$

$\lambda(\alpha = 0|a(x) = 0) = 0$

Тогда условный риск можно записать так:

$R(a(x) = 0|x) = Q(\alpha = 1, a(x) = 0) p(Y=1|X=x)$

$R(a(x) = 1|x) = Q(\alpha = 0, a(x) = 1) p(Y=0|X=x)$

Замечания по нотации

Предыдущий текст был написан согласно нотации, принятой в книге Дуды и Харта. В оригинальной книге В.Н. Вапника рассматривался такой процесс: природа выбирает объект согласно распределению $p(x)$, а затем ставит ему метку класса согласно условному распределению $p(y|x)$. Тогда риск(матожидание потерь) определяется как

$R = \int{L(y,a(x))p(x,y)dxdy}$

Где $a(x)$ — функция, которой мы пытаемся аппроксимировать неизвестную зависимость, $L(y,a(x))$ — функция потерь для реального значения $y$ и значения нашей функции $a(x)$ . Эта нотации более наглядна для того чтобы ввести следущее понятие — эмпирический риск.

Эмпирический риск

На данном этапе мы уже выяснили, что логический метод нам не подходит, потому что он недостаточно гибкий, а байесовский классификатор мы не можем использовать, когда признаков много, а данных для обучения ограниченное число и мы не сможем восстановить вероятность $p(X|Y)$ . Так же нам известно, что байесовский классификатор обладает наименьшей возможной ошибкой классификации. Раз уж мы не можем использовать байесовский классификатор, давайте возьмем что-нибудь по проще. Давайте зафиксируем некоторое параметрическое семейство функций H и будем подбирать классификатор из этого семейства.

Пример: пусть $H$ множество всех функций вида

$h(x) = \sum_{i}^{n}{w_ix_i}$

Все функции этого множества будут отличаться друг от друга только коэффициентами $w$ Когда мы выбрали такое семейство, мы предположили, что в координатах цвет-размер между точками класса 1 и точками класса 0 можно провести прямую линию с коэффициентами $w$ таким образом, что точки с разными классами находятся по разные стороны от прямой. Известно, что у прямой такого вида вектор коэффициентов $w$ является нормалью к прямой. Теперь делаем так — берем наше яблоко, меряем у него цвет и размер и наносим точку с полученными координатами на график в осях цвет-размер. Далее меряем угол между этой точкой и вектором $w$. Замечаем, что наша точка может лежать либо по одну, либо по другую сторону от прямой. Тогда угол между $w$ и точкой будет либо острый, либо тупой, а скалярное произведение либо положительное, либо отрицательное. Отсюда вытекает решающее правило:

$a(x) = sign(\sum_{i}^{n}{w_ix_i})$

После того как мы зафиксировали класс функций $Н$, возникает вопрос — как выбрать из него функцию с нужными коэффициентами? Ответ — давайте выберем ту функцию, которая доставляет минимум нашему байесовскому риску $R()$. Опять проблема — чтобы посчитать значения байесовского риска, нужно знать распределение $p(x,y)$, а оно нам не дано, и восстановиь его не всегда возможно. Другая идея — минимизировать риск не на всех возможных объектах, а только на выборке. Т.е. минимизировать функцию:

$R_{emp} = \frac{1}{N} \sum_{i}^{N}{L(y_i, a(x_i))}$

Эта функция и называется эмпирическим риском. Следующий вопрос — почему мы решили, что минимизируя эмпирический риск, мы при этом так же минимизируем байесовский риск? Напомню, что наша задача практическая — допустить как можно меньше ошибок классификации. Чем меньше ошибок, тем меньше байесовский риск. Обоснование о сходимости эмпирического риска к байесовскому с ростом объема данных было получено в 70-е годы двумя учеными — В. Н. Вапником и А. Я. Червоненкисом.

Гарантии сходимости. Простейший случай

Итак, мы пришли к тому, что байесовский классификатор дает наименьшую возможною ошибку, но обучить его в большинстве случаев мы не можем и ошибку(риск) посчитать мы тоже не в силах. Однако, мы можем посчитать приближение к байесовскокому риску, которое называется эмпирический риск, а зная эмпирический риск подобрать такую аппроксимирующую функцию, которая бы минимизировала эмпирический риск. Давайте рассмотрим простейшую ситуацию, когда минимизация эмпирического риска дает классификатор, так же минимизирующий байесовский риск. Для простейшего случая нам придется сделать предположение, которое редко выполняется на практике, но которое в дальнейшем можно будет ослабить. Зафиксируем конечный класс функций $H = \{h:X\rightarrow Y\}$ из которого мы будем выбирать наш классификатор и предположим, что настоящая функция, которую использует природа для разметки наших яблок на вкусы находится в этом конечном множестве гипотез: $f\in H$ . Так же у нас есть выборка $S$ , полученная из распределения $D$ над объектами $x$ . Все объекты выборки считаем одинаково независимо распределенными(iid). Тогда будет верна следующая

Теорема

Выбирая функцию из класса $H$ с помощью минимизации эмпирического риска мы гарант��рованно найдем такую $h\in H$ , что она имеет небольшое значение байесовского риска если выборка, на которой мы производим минимизацию имеет достаточный размер.

Что значит «небольшое значение» и «достаточный размер» см. в литературе ниже.

Идея доказательства

По условию теоремы мы получаем выборку $S$ из распределения $D$ , т.е. процесс выбора объектов из природы случаен. Каждый раз, когда мы собираем выборку она будет из того же распределения, но сами объекты в ней могут быть различны. Главная идея доказательства состоит в том, что мы можем получить такую неудачную выборку $S$ , что алгоритм, который мы выберем с помощью минимизации эмпирического риска на данной выборке будет плохо минимизировать байесовский риск но при этом хорошо минимизировать эмпирический риск, но вероятность получить такую выборку мала и ростом размера выборки эта вероятность падает. Подобные теоремы существуют и для более реалистичных предположений, но здесь мы не будем их рассматривать.

Практические результаты

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

$R_{emp} = \frac{1}{N} \sum_{i}^{N}{L(y, a(x))}$

И подставляем разные функции потерь, в зависимости от решаемой задачи. Для линейной регрессии:

$L(y, a(x)) = (y-a(x))^2$

Для логистической регресии:

$L(y, a(x)) = log(1+exp[-y*a(x)])$

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

Заключение

Многие методы обучения с учителем можно рассматривать в том числе как частные случаи теории, разработанной В. Н. Вапником и А. Я. Червоненкисом. Эта теория дает гарантии относительно ошибки на тестовой выборке при условии достаточного размера обучающей выборки и некоторых требований к пространству гипотез, в котором мы ищем наш алгоритм.

Используемая литература

The Nature of Statistical Learning Theory, Vladimir N. Vapnik
Pattern Classification, 2nd Edition, Richard O. Duda, Peter E. Hart, David G. Stork
Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David

P.S. Просьба писать в личку обо всех неточностях и опечатках

P.P.S. Большое спасибо авторам этой статьи за TeX-редактор

Распознавание образов. Начала теории