$A$: Алгоритм.
$T$: Задача машинного обучения.
$E$: Обучающая выборка.
$P$: Критерий качества.
$\vec{x}_i$: $i$-ый экземпляр данных.
$y_i$: Ненаблюдаемая величина для $i$-го экземпляра данных.
$\hat{y}_i$: Оценка ненаблюдаемой величины для $i$-го экземпляра данных (метка, label, класс).
$\vec{x}_i(n)$: $n$-ый элемент, $i$-го экземпляра данных (экземпляр данных - вектор, элемент экземпляра - число либо качественный признак).
$p\left(y_i=k|\vec{x_i}\right)$: Условная вероятность ненаблюдаемой величины для наблюдаемого вектора признаков.

Общая постановка задачи машинного обучения

Будем говорить, что алгоритм $A$ решает задачу машинного обучения $T$ на основании опыта $E$ в смысле критерия качества $P$, если с ростом количества опыта $E$ качество $P$ решения задачи $T$ растет [Goodfellow].

Среди наиболее распространенных задач $T$ машинного обучения можно выделить следующие:

Классификация.
Регрессия.
Кластеризация (оценка функции распределения).

Под опытом $E$ в большинстве случаев понимается набор данных (dataset) определяющий для каждого экземпляра данных набор признаков. В случае обучения с учителем каждому экземпляру данных ставится в соответсвие метка (label, target). В случае обучения без учителя метка не задается. Для некоторых алгоритмов вместо фиксированного набора данных используется принцип взаимодействия алгоритма обучения с окружающей средой (reinforcement learning).

Выбор критерия качества $P$ определяется видом задачи $T$. Для задачи классификации $P$ может быть определено как вероятность (не)правильной классификации. Для регрессии в качестве критерия $P$ часто используется дисперсия ошибки предсказания.

Важным отличием задачи машинного обучения от задачи оптимизации является требование обеспечения заданного качества $P$ для данных на которых обучение не проводилось. Для проверки этого требования набор данных $E$ разделяют на обучающую выборку $E_{train}$ (training dataset), на которых проводят обучение алгоритма, и тестовые данные $E_{test}$ (test dataset), которые при обучении не используются. Если алгоритм $A$ демонстрирует высокое качество $P_{Train}$ на тренировочном наборе данных и низкое качество $P_{Test}$ на тестовом наборе данных, то говорят о переобучении алгоритма $A$. Способность алгоритма $A$ достигать одинакового качества на тестовых и тренировочных данных называется генерализацией.

Примеры вопросов.

Приведите примеры задач машинного обучения.
Что означает термин переобучение?
Что означает термин генерализация?

Список литературы.

Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение. ДМК Пресс. 2017

Задача классификации.

Задача классификации состоит в предсказании ненаблюдаемой дискретной величины $y_i$, обозначающей номер класса, на основании наблюдаемого $i$-го набора признаков $\vec{x}_i$. В качестве критерия качества классификации $P_{class}$ будем использовать частоту ошибочной классификации [ISL1]: \begin{equation} P_{class}=\frac{1}{n}\sum\limits_{i=1}^{n}I\left(y_i-\hat{y}_i\right) \label{pclass} \end{equation} Здесь $\hat{y}_i$ - предсказанный класс для $i$-го набора признаков. ${y}_i$ - класс для которого был получен набор признаков. $I$ - индикаторная функция равная нулю для нулевого аргумента, либо 1 для всех остальных значений.

Байесовский классификатор.

Можно доказать, что для минимизации критерия (\ref{pclass}) следует выбирать такой номер класса $k$, для которого условная вероятность $p_k=p\left(y_i=k|\vec{x_i}\right)$ была бы максимальной среди всех условных вероятностей $p_k, k\in 1\ldots K$ для наблюдаемого вектора $\vec{x_i}$ [ISL1]. Такой алгоритм классификации называется байесовским классификатором.

На практике оценивать $p\left(y_i=k|\vec{x_i}\right)$ по обучающей выборке неудобно [Coursera1]. Вместо этого оценивают $p\left(\vec{x_i}|y_i=k\right)$. Затем, пользуясь формулой Байеса, получают вероятность $p_k$. \begin{equation} p\left(y_i=k|\vec{x_i}\right) = \frac{p\left(\vec{x_i}|y_i=k\right)p(y_i=k)}{p(\vec{x_i})} \label{Bayes1} \end{equation} Вероятность $p(y_i=k)$ называют априорной или доопытной, так как она известна до получения вектора $\vec{x_i}$. Условную вероятность $p\left(y_i=k|\vec{x_i}\right)$ называют апостериорной или постопытной, так как она уточняет априорное значение $p(y_i=k)$ после получения вектора признаков $\vec{x_i}$.

Примеры вопросов.

Что означает термин априорная вероятность?
Что означает термин апостериорная вероятность?

Список литературы.

Задача.

Рассмотрим набор данных $E$ состоящий из случайных векторов $\vec{x_i}$, $i\in 1\ldots n$ \begin{equation} \vec{x_i} = \begin{pmatrix} x_{1}(i) \\ x_{2}(i) \\ \ldots \\ x_{D}(i) \end{pmatrix} \label{RandomVector2} \end{equation} распределение которых задано с помощью многомерной гауссовой плотности: \begin{equation} p(\vec{x_i},k)=\frac{1}{(2\pi)^\frac{D}{2}|\Sigma_k|^\frac{1}{2}}\exp\left[-\frac{1}{2}\left(\vec{x}-\vec{\mu_k}\right)^T\Sigma_k^{-1}\left(\vec{x}-\vec{\mu_k}\right)\right] \label{vgauss} \end{equation} Каждому вектору $\vec{x_i}$ поставлено в соответствие целое число (метка, label, target) $k\in 1,\ldots K$, обозначающее номер класса, которое определяет вектор математического ожидания $\mu_k$ и корреляционную матрицу $\Sigma_k$ для $k$-го класса. Необходимо реализовать байесовский классификатор для такого набора данных. Априорную вероятность принадлежности вектора $\vec{x_i}$ к классу $k$ считать одинаковой для всех классов $p(y_i=k)=\frac{1}{K}$. Количество классов $K=2$.

Решение.

Условная вероятность \begin{equation} p_k\left(y_i=k|\vec{x_i}\right) = \frac{p_i\left(\vec{x_i}|y_i=k\right)p(y_i=k)}{p(\vec{x_i})} = \frac{p\left(\vec{x_i},k\right)\frac{1}{K}}{\sum\limits_{m=1}^{K}p(\vec{x_i},m)} \label{BayesExs1} \end{equation} Знаменатель в (\ref{BayesExs1}) не зависит от номера класса $k$. Числитель домноженный на общий для всех классов коэффициент $(2\pi)^\frac{D}{2}$ после логарифмирования: \begin{equation} \phi_k(\vec{x_i})=\ln\left((2\pi)^\frac{D}{2}p(\vec{x_i},k)\right)=-\frac{1}{2}\left(\vec{x}-\vec{\mu_k}\right)^T\Sigma_k^{-1}\left(\vec{x}-\vec{\mu_k}\right)-\frac{1}{2}\ln |\Sigma_k| \label{LogNum1} \end{equation} Логарифм является монотонной функцией, поэтому выражение (\ref{LogNum1}) можно использовать вместо (\ref{BayesExs1}) для классификации. Процедура байесовской классификации вектора $\vec{x_i}$ в этом случае сводится к выбору такого класса $k^*$, для которого значение функции $\phi_{k^*}(\vec{x_i})$ будет максимальным среди всех остальных $\phi_{k}(\vec{x_i})$ $\forall k\neq k^*$. \begin{equation} k^* = \arg_k\max_{k\in 1\ldots K}\left(\phi_k(\vec{x_i})\right) \label{Fisher1} \end{equation} Раскрывая скобки в выражении (\ref{LogNum1}) и пренебрегая общим множителем $\frac{1}{2}$, получаем:

\begin{equation} \phi_k(\vec{x_i})= -\vec{x_i}^T\Sigma_k^{-1}\vec{x_i} + \vec{x_i}^T\Sigma_k^{-1}\vec{\mu_k} + \vec{\mu_k}^T\Sigma_k^{-1}\vec{x_i} - \vec{\mu_k}^T\Sigma_k^{-1}\vec{\mu_k} - \ln |\Sigma_k| \label{Fisher2} \end{equation} Рассмотрим двумерный случай $D=2$. Введем следующие обозначения: \begin{equation} \vec{x_i} = \begin{pmatrix} x_{1}(i) \\ x_{2}(i) \\ \end{pmatrix} \label{RandomVector_x} \end{equation} \begin{equation} \vec{\mu_k} = \begin{pmatrix} \mu_1(k) \\ \mu_2(k) \\ \end{pmatrix} \label{Vector_mu} \end{equation} \begin{equation} \Sigma_k^{-1} = \begin{pmatrix} s_{11}(k) & s_{12}(k) \\ s_{21}(k) & s_{22}(k) \\ \end{pmatrix} \label{matrix_s1} \end{equation} Подставляя (\ref{RandomVector_x}),(\ref{Vector_mu}) и (\ref{matrix_s1}) в (\ref{Fisher2}), получим: \begin{equation} \begin{aligned} \phi_k(\vec{x_i}) &= -s_{11}(k)x_{1}^2(i)-(s_{12}(k)+s_{21}(k))x_{1}(i)x_{2}(i)-s_{22}(k)x_{2}^2(i) \\ &+ 2(s_{11}(k)\mu_1(k)+s_{12}(k)\mu_2(k))x_{1}(i) + 2(s_{21}(k)\mu_1(k)+s_{22}(k)\mu_2(k))x_{2}(i)\\ &-s_{11}(k)\mu_{1}^2(k)-(s_{12}(k)+s_{21}(k))\mu_{1}(k)\mu_{2}(k)-s_{22}(k)\mu_{2}^2(k) - \ln |\Sigma_k| \end{aligned} \label{Fisher3} \end{equation} После построчной группировки подобных слагаемых: \begin{equation} \begin{aligned} \phi_k(\vec{x_i}) = &- \left[ s_{11}(k) \right] \times x_{1}^2(i) \\ &- \left[ (s_{12}(k)+s_{21}(k)) \right] \times x_{1}(i)x_{2}(i) \\ &- \left[ s_{22}(k) \right] \times x_{2}^2(i) \\ &+ \left[ 2(s_{11}(k)\mu_1(k)+s_{12}(k)\mu_2(k)) \right] \times x_{1}(i) \\ &+ \left[ 2(s_{21}(k)\mu_1(k)+s_{22}(k)\mu_2(k)) \right] \times x_{2}(i) \\ &- \left[ s_{11}(k)\mu_{1}^2(k)-(s_{12}(k)+s_{21}(k))\mu_{1}(k)\mu_{2}(k)-s_{22}(k)\mu_{2}^2(k) - \ln |\Sigma_k| \right] \end{aligned} \label{Fisher4} \end{equation} Классифицирующая функция $\phi_k(\vec{x_i})$ определяется билинейной формой от вектора $\vec{x_i}$ плюс некоторая константа, зависящая от номера класса.

Пример реализации байесовского классификатора на тестовой выборке для двух классов с гауссовым распределением.

Пример байесовской классификации двумерных гауссовых случайных векторов.

Список литературы.

Метод максимального правдоподобия определяет способ оценки вектора неизвестных параметров $\vec{\theta}$ на основе набора наблюдений (выборки) $\vec{x_i}$, $i\in 1\ldots n$, в предположении что наблюдения независимы и каждое наблюдение подчиняется распределению $p(\vec{x_i},\vec{\theta})$. В качестве оценки максимального правдоподобия принимается значение максимизирующее вероятность наблюдения такой выборки. В предположении, что элементы выборки независимы, вероятность наблюдения конкретной выборки: \begin{equation} L(\vec{x_1},\ldots \vec{x_n},\vec{\theta}) = \prod_{i=1}^{n}p(\vec{x_i},\vec{\theta}) \label{Likelihood1} \end{equation} Функция $L(\vec{x},\vec{\theta})$ называется функцией правдоподобия. Логарифмическая функция правдоподобия: \begin{equation} \ln L(\vec{x},\vec{\theta}) = \ln \prod_{i=1}^{n}p(\vec{x_i},\vec{\theta}) = \sum_{i=1}^{n}\ln p(\vec{x_i},\vec{\theta}) \label{LogLikelihood1} \end{equation}

Пример

Оценить математическое ожидание гауссовой случайной величины методом максимального правдоподобия. Функция правдоподобия: \begin{equation} L(x_1,\ldots x_n,\mu) = \prod_{i=1}^{n}\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x_i-\mu)^2}{2\sigma^2}\right) \label{Likelihood2} \end{equation} Логарифмическая функция правдоподобия: \begin{equation} \ln L(x_1,\ldots x_n,\mu) = n \ln \left(\frac{1}{\sigma\sqrt{2\pi}}\right) \sum_{i=1}^{n} \left(-\frac{(x_i-\mu)^2}{2\sigma^2}\right) \label{LogLikelihood2} \end{equation} Максимум логарифмического правдоподобия достигается в точке где производная по $\mu$ равна 0. \begin{equation} \frac{\partial \ln L(x_1,\ldots x_n,\mu)}{\partial \mu} = n \ln \left(\frac{1}{\sigma\sqrt{2\pi}}\right) \sum_{i=1}^{n} \frac{\partial \left(-\frac{(x_i-\mu)^2}{2\sigma^2}\right)}{\partial \mu} = \frac{n}{\sigma^2}\ln \left(\frac{1}{\sigma\sqrt{2\pi}}\right) \sum_{i=1}^{n} (x_i-\mu) \label{DLogLikelihood2} \end{equation} Необходимое условие максимума логарифмической функции правдоподобия: \begin{equation} \sum_{i=1}^{n} (x_i-\mu) = \sum_{i=1}^{n}x_i - \sum_{i=1}^{n}\mu = \sum_{i=1}^{n}x_i - n\mu = 0 \label{MaxCondition1} \end{equation} Оценка маскимального правдоподобия для математического ожидания гауссовой величины: \begin{equation} \hat{\mu}_{ML}=\frac{1}{n}\sum_{i=1}^{n}x_i \label{MaxLogMu} \end{equation}

Оценки максимального правдоподобия обладают важными свойствами: несмещенностью, состоятельностью и эффективностью. Несмещенность означает, что с ростом объема выборки оценка $\hat{\theta}$ стремится к истинному значению $\theta$. \begin{equation} \lim_{n\rightarrow \infty} \hat{\theta}_{ML} = \theta \label{UnbiasedML1} \end{equation} Под состоятельностью оценки понимается уменьшение дисперсии оценки (величины ошибки) с ростом объема выборки: \begin{equation} \lim_{n\rightarrow \infty} \mathrm{var} \left[\hat{\theta}_{ML}\right] = 0 \label{VarianceML1} \end{equation}

Оценка называется эффективной если среди всех других оценок для заданных значений смещения и объема выборки данная оценка демонстрирует наименьшую дисперсию ошибки. Доказать это свойство можно с помощью критерия Крамера-Рао [Chernova1].

Примеры вопросов.

Что означает термин функция правдоподобия?
Какими свойствами обладает оценка максимального правдоподобия?

Список литературы.

В некоторых случаях построить эффективную математическую модель классификации по обучающей выборке не удается. В таком случае могут помочь алгоритмы классификации, использующие обучающую выборку напрямую. Примером такого алгоритма является метод k-ближайших соседей. Суть метода заключается в том, что при поступлении входного вектора признаков алгоритм находит k ближайших к этому вектору векторов из обучающей выборки. При этом подразумевается наличие метрики в пространстве признаков. В самом простом случае это может быть, например, евклидова метрика: \begin{equation} d_e(\vec{x_i},\vec{x_j})=\sqrt{\sum\limits_{n=1}^{N}(x_i(n)-x_j(n))^2} \label{EuclidianMetric} \end{equation} Алгоритм относит входной вектор к такому классу для которого количество ближайших выбранных соседей максимально.

Иллюстрация метода k-ближайших соседей (Colab для картинки).

На приведенном выше изображении входной вектор обозначен красным, элементы обучающей выборки, относящиеся к первому классу отмечены зеленым цветом, ко второму классу - синим цветом. Окружность содержит 10 ближайших соседей. В данном случае входной вектор будет отнесен к первому классу так как количество зеленых ближайших соседей равно 8, а количество синих ближайших соседей равно 2.

Вспомним, что байесовский классификатор использует апостериорное распределение: \begin{equation} p\left(y_i=k|\vec{x_i}\right) = \frac{p\left(\vec{x_i}|y_i=k\right)p(y_i=k)}{p(\vec{x_i})} \label{Bayes1_2} \end{equation} Попробуем применить классификатор (\ref{Bayes1_2}) к задаче фильтрации СПАМ сообщений. Для этого будем использовать обучающую выборку SMS Spam Collection Dataset, расположенную на ресурсе Kaggle.Com.

Выборка содержит SMS сообщения двух типов - SPAM (нежелательные сообщения) и HAM (нормальные, легитимные сообщения).

#	label	message	length
0	ham	Go until jurong point, crazy.. Available only ...	111
1	ham	Ok lar... Joking wif u oni...	29
2	spam	Free entry in 2 a wkly comp to win FA Cup fina...	155
3	ham	U dun say so early hor... U c already then say...	49
4	ham	Nah I don't think he goes to usf, he lives aro...	61

На первом этапе следует провести анализ выборки и определить наиболее часто встречающиеся слова. Из этого набора слов следует удалить заведомо не информационные: междометия, знаки пунктуации и т.п.. Затем необходимо среди часто встречающихся слов отобрать те что бдут использованы в качестве обучающих признаков. Предположим, мы отобрали таким образом N слов. Классификационный вектор $\vec{x_i}$ в каждой своей позиции будет содержать число $1$, если соответсвующее слово встретилось в сообщении, и $0$ если такого слова нет в сообщении.

Для реализации байесовского классификатора необходимо оценить условную плотность $p\left(\vec{x_i}|y_i=k\right)$. Если, например, количество слов $N=10$, то количество вариантов вектора признаков уже $2^{10}=1024$, что слишком много, так как в данном случае вся выборка содержит немногим более 5000 сообщений. Получается, что даже при равномерном распределении на один вариант вектора приходится только пять сообщений.

Для устранения подобных ограничений в наивном байесовском подходе предполагается, что компоненты классификационного вектора независимы. Т.е. в нашем примере появление глагола to do предполагается никак не связанным с появлением, например, местоимения he/she. Такой подход радикально упрощает оценку $p\left(\vec{x_i}|y_i=k\right)$, так как в этом случае \begin{equation} p\left(\vec{x_i}|y_i=k\right)=\prod\limits_{n=1}^{N}p\left(\vec{x_i(n)}|y_i=k\right) \label{Bayes1_3} \end{equation}

Список литературы.

Спам-фильтры и наивный байесовский классификатор. - Coursera. Машинное обучение и анализ данных.

Линейный классификатор может быть реализован с помощью функции вида: \begin{equation} \psi_k(\vec{x}) = \vec{c_k}^T\vec{x_i}+c_{0,k} = \left[ \vec{c_k}^T:c_{0,k} \right] \begin{bmatrix} \vec{x_i} \\ 1 \end{bmatrix} \label{LDA1} \end{equation} Классификатор относит вектор $\vec{x_i}$ к такому классу $\hat{y_i}=k$, для которого значение $\psi_k(\vec{x})$ максимально. Логично рассматривать $\psi_k(\vec{x})$ как аппроксимацию условной вероятности $p\left(y_i=k|\vec{x_i}\right)$. В качестве критерия качества можно использовать долю неправильных ответов: \begin{equation} P(\vec{c_1},\vec{c_2}\ldots \vec{c_K}) = \frac{1}{n}\sum\limits_{i=1}^n I\left[ \arg \left( \max_{k \in 1,2\ldots K} \left(\psi_k(\vec{x}_i)\right) \right) \ne y_i\right] \label{LDAP1} \end{equation} Критерий (\ref{LDAP1}) достигает минимума, если $\psi_k(\vec{x})=p\left(y_i=k|\vec{x_i}\right)$. Рассмотрим свойства функции $\psi_k(\vec{x})$. Пусть количество классов $K=2$ и размерность признакового пространства $D=2$. В этом случае достаточно использовать одну классифицирующую функцию $\psi_1(\vec{x})$. В качестве критерия качества будем использовать средний квадрат отклонения: \begin{equation} P(\vec{c}) = \frac{1}{n}\sum\limits_{i=1}^n \left(\psi_1(\vec{x_i})-y_i\right)^2 \label{LDAP2_Fisher} \end{equation} Для $\vec{x_i}$ относящихся к первому классу примем $y_i=1$, для элементов $\vec{x_i}$ второго класса будем использовать $y_i=0$. При классификации будем использовать критерий $\psi_1(\vec{x})>0.5$. Такой классификатор называется линейным классификатором Фишера.

Вместо выбора максимального из двух значений $\psi_1(\vec{x_i})$ и $\psi_2(\vec{x_i})$ будем анализировать знак разности: \begin{equation} \bar{\psi}(\vec{x}) = \psi_2(\vec{x_i}) - \psi_1(\vec{x_i})\ = (\vec{c_2}-\vec{c_1})^T\vec{x_i}+(c_{0,2}-c_{0,1}) = \vec{c}^T\vec{x_i}+c_{0} \label{LDA2} \end{equation} Уравнение \ref{LDA2} определяет прямую на плоскости образованной координатами признаков $x_1$, $x_2$. Точки, лежащие выше прямой классификатор относит к первому классу, точки по другую сторону - ко второму. Расстояние от точки до разделяющей прямой можно определить с помощью проекции: \begin{equation} d = \frac{\vec{c}^T\vec{x_i}}{\left|\vec{c}\right|} \label{Distance1} \end{equation} При правильной классификации, т.е. если выход классификатора указывает на тот же класс к которому принадлежит вектор, расстояние от точки до прямой можно рассматривать как меру уверенности классификатора. Оступом (margin) при линейной классификации называется выражение вида: \begin{equation} M_i = y_i\cdot\frac{\vec{c}^T\vec{x_i}}{\left|\vec{c}\right|} \label{Margin1} \end{equation}

При этом значения $M_i>0$ соответсвуют правильным решениям и характеризуют степень уверенности. Отрицательные значения $M_i<0$ соответсвуют ошибочным решениям классификатора. Большие по модулю отрицательные значения могут указывать на точки с аномальным расположением, либо на несоответствие используемой модели рассматриваемому набору данных. Отступ можно определить только для обучающей выборки, когда $y_i$ известен.

Список литературы.

Типичные трудности при сборе и подготовке данных для обучения - ограниченный объем выборки и аномальные данные. Рассмотрим несколько вариантов размеров выборки и влиние на результат обучения линейного классификатора нескольких аномальных точек. В первом примере количество точек вы выборке равно $10000$. Также в выборке присутствуют несколько аномальных желтых точек. При большом размере выборки эти точки практически не оказывают влияния на границу линейного классификатора.

Линейный классификатор на большой выборке с выбитыми точками.

Теперь рассмотрим результат обучения линейного классификатора на выборке объемом $100$ точек на каждый класс.

Линейный классификатор на ограниченной выборке с выбитыми точками.

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

В случае линейного классификатора основная причина переобучения состоит в коррелированности компонентов входного вектора. В этом случае матрица $X^TX$ становится плохо обусловленной и как следствие метод наименьших квадратов порождает большие по модулю коэффициенты модели. Для предотвращения этого эффекта к основному критерию линейного классификатора (\ref{LDAP2_Fisher}) добавляется дополнительное условие в виде ограничения на величину коэффициентов: \begin{equation} P(\vec{c})_{L2} = \frac{1}{n}\sum\limits_{i=1}^n \left(\psi_1(\vec{x_i})-y_i\right)^2 + \alpha\vec{c}^T\vec{c} \label{Reg_L2_Criteria} \end{equation} Можно показать, что для минимизации (\ref{Reg_L2_Criteria}) вместо решения системы нормальных уравнений в виде: \begin{equation} c=(X^TX)^{-1}X^Tb \label{LS_Equations} \end{equation} Следует использовать уравнение вида: \begin{equation} c=(X^TX+I\alpha)^{-1}X^Tb \label{LS_Equations_L2} \end{equation} Этот метод регуляризации называют $L2$-регуляризацией, регуляризацией по Тихонову либо гребневой (Ridge) регрессией. После применения регуляризации с параметром $\alpha=200$ к рассмотренному в лекции 7 примеру с объемом выборки 100 точек на класс, получим:

Результат $L2$-регуляризации линейного классификатора.

Можно заметить, что классификатор перестал реагировать на аномальные точки второго класса.

Список литературы.

Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение. ДМК Пресс. 2017

Если критерий $P(\mathbf{c})$ задан аналитически вместе со своими частными производными первого порядка, то для оценки параметров модели (классификатора) можно предложить пошаговый алгоритм. Перед запуском алгоритма задаются начальным (произвольным) набором параметров модели $\mathbf{c}(0)$. Далее на каждом $i$-ом шаге алгоритма вычисляют градиент критерия \begin{equation} \nabla \mathbf{P}(i)=\left(\frac{\partial P\left(\mathbf{c}(i)\right)}{\partial c_1},\frac{\partial P(\mathbf{c}(i))}{\partial c_2}\ldots \frac{\partial P(\mathbf{c}(i))}{\partial c_D}\right)\tag{35} \end{equation} И обновляют значения коэффициентов модели: \begin{equation} \mathbf{с}(i+1) = \mathbf{c}(i) - \alpha \nabla \mathbf{P}(i)\tag{36} \end{equation} Этот метод называют алгоритмом наискорейшего спуска (Steepest Descent Algorithm) либо методом градиентного спуска (Gradient Descent Algorithm - GDA). Здесь $\alpha$ - параметр алгоритма, определяющий скорость спуска к решению.

Если критерий $P$ является квадратичным, как было в случае линейного классификатора в предыдущих лекциях, то решение существует и решение единственно, ему соответствует экстремальная точка $\nabla P=\mathbf{0}$. Такая задача называется выпуклой (convex).

В более общем случае экстремальная точка $\nabla P=\mathbf{0}$ не обязательно соответсвует минимуму критерия $P$, более того, таких точек может быть много вплоть до бесконечного количества. Оптимальное решение может быть в этом случае получено только перебором всех таких точек и сравнением величины критерия в этих точках. Такая задача называется невыпуклой (non-convex).

Пример использования GDA.

Список литературы.

Отступ $M_i>0$ является произвольным по модулю числом, что вызывает очевидные трудности при его интерпретации (насколько отступ 1E10 надежнее чем 1E8). Гораздо удобнее использовать в качестве выхода классификатора оценку вероятности $p$ в диапазоне от 0 до 1. Рассмотрим так называемое отношение правдоподобия для задачи бинарной классификации (на два класса). \begin{equation} LLR = \ln\frac{p}{1-p} \label{LLR1} \end{equation} где $p=p(y_i=1|\vec{x_i})$-вероятность принадлежности вектора $\vec{x_i}$ первому классу, а $(1-p)=p(y_i=2|\vec{x_i})$- вероятность принадлежности второму классу. Логарифм является монотонной функцией, поэтому для случая $LLR>0$ классификатор относит вектор $\vec{x_i}$ к первому классу, а в случае $LLR<0$ - ко второму. Т.е. LLR имеет похожие на отступ свойтсва и будет логичным вместо аппроксимации вероятности аппроксимировать значение LLR с помощью линейного классификатора, чтобы затем пересчитать отступ в вероятность следующим образом: \begin{equation} \begin{aligned} M = LLR = \ln\frac{p}{1-p} \\ e^{M} = \frac{p}{1-p} \\ e^{M}\left(1-p\right)= p\\ e^{M} = p\left(1+e^{M}\right)\\ p = \frac{e^{M}}{1+e^{M}}=\frac{1}{1+e^{-M}} \end{aligned} \label{LLRtoProb1} \end{equation} Если теперь вместо отступа подставить выход линейного классификатора, получим модель логистической регрессии: \begin{equation} \hat{p}(\vec{x};\vec{c}) = \frac{1}{1+e^{-\bar{\psi}(\vec{x})}}= \frac{1}{1+e^{-\left(\vec{c}^T\vec{x_i}+c_{0}\right)}} \label{LogReg} \end{equation} Для поиска вектора коэффициентов $\vec{c}$ воспользуемся методом оптимизации по стохастическому градиенту (LMS). В качестве критерия оптимизации будем использовать критерий максимального правдоподобия: \begin{equation} Q(\vec{c}) = \prod_{i=1}^{n}\left(\hat{p}(\vec{x};\vec{c})\right)^{p_i}\left(1-\hat{p}(\vec{x};\vec{c})\right)^{1-p_i} \\ \label{LogRegMLCriteria} \end{equation} После логарифмирования: \begin{equation} \begin{aligned} L(\vec{c}) = \log Q(\vec{c})=\sum_{i=1}^{n}\left(p_i\log (\hat{p}(\vec{x};\vec{c})) + (1-p_i)\log (1-\hat{p}(\vec{x};\vec{c}))\right) \end{aligned} \label{LogRegMLToCrossEntropy} \end{equation} Выражение (\ref{LogRegMLToCrossEntropy}) определяет кросс-энтропию между истинным распределением $p(\vec{x})$ и его оценкой на основе логистической регрессии $\hat{p}(\vec{x};\vec{c})$. Чем больше значение кросс-энтропии тем ближе распределение $\hat{p}(\vec{x};\vec{c})$ к желаемому $p(\vec{x})$.

Т.е. решается задача максимизации \begin{equation} \vec{c}^* = \arg\max L(\vec{c})= \arg\max Q(\vec{c}) \end{equation} Уравнение адаптации коэффициентов: \begin{equation} \vec{c}(k+1) = \vec{c}(k) + \alpha \nabla (L(\vec{c}(k))) \end{equation} Компоненты вектора градиента: \begin{equation} \frac{\partial L}{\partial c_d} = \frac{\partial}{\partial c_d}\sum_{i=1}^{n}\left(p_i\log (\hat{p}(\vec{x};\vec{c})) + (1-p_i)\log (1-\hat{p}(\vec{x};\vec{c}))\right) \end{equation} Уравнение адаптации коэффициентов: \begin{equation} \mathbf{c}(k+1) = \mathbf{c}(k) + \alpha(y_i-\frac{1}{1+e^{c(k)^Tx_i}})x_i \end{equation}

Список литературы.

Andrew Ng - Stanford CS229 Lecture notes. стр.16 - Logistic regression.

Метод опорных векторов (Support Vector Machine, SVM) является простым, но достаточно мощным инструментом бинарной классификации (на два класса). Основное достоинство - способность обрабатывать большие выборки и формировать компактные модели. Для пояснения SVM обратимся к уравнению линейного классификатора: \begin{equation} \mathbf{c}\mathbf{x}+b=0 \label{SVM_direct_model} \end{equation}

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

Классификация с максимальным отступом. Figure script.

Если домножить урвнение (44) слева и справа на любое число, то это никак не изменит расположение границы (черная прямая на картинке). Таким образом, у нас есть свобода выбора масштаба коэффициентов уравнения. Тогда для уравнений синей линии (верхней границы) и красной линии (нижней границы) выберем масштаб таким образом, чтобы выполнялось: $\mathbf{c}\mathbf{x}+b=1$ для верхней границы и $\mathbf{c}\mathbf{x}+b=-1$ для нижней. При такой нормировке ширина границы (расстояние между красной и синей линией): \begin{equation} W=\frac{\mathbf{c}}{||\mathbf{c}||}\left(\mathbf{x}_+-\mathbf{x}_-\right)=\frac{2}{||\mathbf{c}||} \end{equation}

Можно предположить, что среди всех возможных положений границы линейного классификатора предпочтительным является вариант с наибольшей шириной границы $W$. Тогда для модели SVM (\ref{SVM_direct_model}) можем определить критерий оптимизации в виде: \begin{equation} P(\mathbf{c})=\max_{\mathbf{c}}W=\max_{\mathbf{c}}\frac{2}{||\mathbf{c}||} \end{equation} Или эквивалентно: \begin{equation} P(\mathbf{c})=\min_{\mathbf{c}}||\mathbf{c}||^2 \end{equation} В этом случае получаем задачу с квадратичным критерием оптимизации с линейными ограничениями: \begin{align*} \min_{\mathbf{c}}||\mathbf{c}||^2 \\ y_i\left(\mathbf{c}^T\mathbf{x_i}+b\right)\ge 1 \end{align*} В такой постановке задача является слишком жесткой, т.е. небольшое количество аномальных точек находящихся вблизи границы могут сильно влиять на общий результат (переобучение). Для ослабления ограничений с целью регуляризации введем дополнительный общий действительный параметр $C$ и переменные $\xi_i$ для каждой точки в обучающей выборке следующим образом: \begin{equation} \min_{\mathbf{c},\xi_i}||\mathbf{c}||^2+C\sum\limits_{i=0}^{n-1}\xi_i \\ y_i\left(\mathbf{c}^T\mathbf{x_i}+b\right)\ge 1-\xi_i \label{direct_SVM_problem} \end{equation} Здесь каждому вектору признаков $\mathbf{x_i}$ и желаемому выходу $y_i$ добавляется неотрицательный параметр $\xi_i$, который позволяет отдельным точкам нарушать границу классификатора. Нарушители платят штраф в виде довеска к критерию $C\sum\limits_{i=0}^{n-1}\xi_i$. Чем больше параметр тем больше штраф за нарушения. Поэтому в случае $С=\infty$ получаем жесткую границу. В случае малого $С$ получаем широкую границу и большое количество нарушителей. По мере увеличения $С$ граница сужается, а количество нарушителей снижается. Выражение (\ref{direct_SVM_problem}) определяет прямую задачу SVM.

Задача (\ref{direct_SVM_problem}) является квадратичной задачей с линейными ограничениями, эта задача выпуклой оптимизации, после применения регуляризации (подбор $C$) решение существует и оно единственно.

Список литературы.

A. Zisserman. C19 Machine Learning Hilary 2015 Lecture 2: The SVM classifier

Переход к двойственной задаче SVM базируется на теореме представлений (формулируется в разных вариантах по-разному, например, теорема Риса для Гильбертовых пространств, для нас более интересен случай [Schölkopf et. al]) Двойственная задача формулируется в виде: \begin{equation} \max_{\alpha_i\ge 0}\sum\limits_{i=0}^{n-1}\alpha_i-\sum\limits_{j=0}^{n-1}\sum\limits_{k=0}^{n-1}\alpha_j\alpha_k y_j y_k(\mathbf{x}_j^T\mathbf{x}_k) \\ 0\le \alpha_i \le C, \forall i \\ \sum\limits_{i=0}^{n-1} \alpha_i y_i = 0 \label{dual_SVM_problem} \end{equation} Обе постановки (\ref{direct_SVM_problem}) и (\ref{dual_SVM_problem}) эквивалентны. При этом двойственная постановка определяет уравнение классификации в виде: \begin{equation} f(\mathbf{x})\sum\limits_{i=0}^{n-1}\alpha_i y_i(\mathbf{x}_i^T\mathbf{x}) \label{dual_svm_classifier} \end{equation} Может показаться, что уравнение (\ref{dual_svm_classifier}) использует всю обучающую выборку для анализа каждого входного вектора $\mathbf{x}$. На практике большинство коэффициентов $\alpha_i$ равны нулю, и лишь небольшая часть отлична от нуля. Вектора $\mathbf{x}_i$, соответсвующие ненулевым коэффициентам $\alpha_i$ являются опорными векторами.

Список литературы.

Рассмотрим пример обучающей выборки:

Пример линейно неразделимой обучающей выборки.

Данная выборка не может быть полностью разделена линейным классификатором. При этом замена переменных: \begin{equation} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \rightarrow \begin{pmatrix} x_1^2 \\ x_2^2 \\ x_1 x_2 \end{pmatrix} \end{equation} Позволяет перейти к трехмерному представлению вектора признаков:

Переход к трехмерному признаковому пространстсву.

Переход к пространству более высокой размерности позволяет использовать линейный классификатор для линейно неразделимой выборки в пространстве исходной размерности.

Введем общее обозначение для перехода к новому пространству признаков. Для каждого исходного вектора признаков будем применять преобразование: \begin{equation} \tilde{\mathbf{x}} = \Phi(\mathbf{x}) \end{equation} При этом классификатор в двойственной постановке: \begin{equation} f(\mathbf{x})=\sum\limits_{i=0}^{n-1}\alpha_i y_i(\Phi(\mathbf{x}_i)^T\Phi(\mathbf{x})) \end{equation} Ядро SVM вводится путем обобщения понятия скалярного произведения: \begin{equation} k(\mathbf{x}_i,\mathbf{x})=\Phi(\mathbf{x}_i)^T\Phi(\mathbf{x}) \end{equation} И переходу к понятию ядра как функции от двух векторов, например: \begin{equation} k(\mathbf{x},\mathbf{z})= x_1^2z_1^2 + x_2^2z_2^2+x_1z_1 \end{equation} Основные типы ядер, часто применяемые на практике: Линейное ядро: \begin{equation} k(\mathbf{x},\mathbf{x'})= \mathbf{x}^T\mathbf{x'} \end{equation} Полиномиальное ядро: \begin{equation} k(\mathbf{x},\mathbf{x'})= \left(1+\mathbf{x}^T\mathbf{x'}\right)^d \end{equation} Гауссово ядро (радиальная базисная функция, RBF (radial basis function)): \begin{equation} k(\mathbf{x},\mathbf{x'})= \exp\left(\frac{||\mathbf{x}-\mathbf{x'}||^2}{2\sigma^2}\right) \end{equation}

Список литературы.

Lecture 3: SVM dual, kernels and regression.

Список литературы.

Lecture 3: SVM dual, kernels and regression.