Генеративный и дискриминативный подходы к обучению
Классификационные модели, которые мы рассматривали в предыдущих параграфах, нацелены непосредственно на оценку $P(Y \vert X)$. Такие модели называются дискриминативными. К ним относится, например, логистическая регрессия: она предлагает оценку $ \hat P(y=1 \vert x) = \sigma(w^Tx) $. В процессе обучения дискриминативные модели подбирают разделяющую поверность (гиперплоскость в случае логистической регрессии). Новые объекты дискриминативная модель классифицирует в зависимости от того, по какую сторону от разделяющей поверности они лежат. Например, обучившись на изображениях домашних кошек (y=0) и рысей (y=1), дискриминативная модель будет определять, новое изображение больше похоже на кошку или на рысь. При этом, если на вход такой модели дать изображение собаки (объект класса, которого не было в обучении, выброс), дискриминативная модель заведомо не сможет обнаружить, что это и не кошка, и не рысь, и отнесёт такой объект к одному из ''знакомых'' ей классов.
В этом параграфе мы поговорим о другой группе моделей, которые нацелены на оценку $P(X, Y) = P(X \vert Y)P(Y)$. Такая модель описала бы, как обычно выглядят кошки, как они могут выглядеть, а каких кошек точно не бывает. Так же она описала бы и рысей. Она также определила бы по обучающим данным, насколько изображения кошек встречаются чаще, чем изображения рысей, т.е. оценила бы $P(Y)$. Если модель позволила точно оценить распределение $P(X \vert Y)$, с её помощью можно генерировать объекты из этого условного распределения, в нашем примере -- изображения кошек и рысей соответственно. А вместе распределение $P(X, Y)$ дало бы нам возможность генерировать изображения и кошек, и рысей, причём именно в той пропорции, в которой они встречаются в реальном мире. Поэтому модели, оценивающие $P(X, Y)$, называют генеративными. Ещё одно достоинство генеративных моделей -- их способность находить выбросы в данных: объект $x$ можно считать выбросом, если $P(x \vert y)$ мало для каждого класса $y$.
Заметим, что находить выбросы с помощью генеративной модели можно и когда класс всего один (т.е. никакие метки классов не доступны). Такая задача называется одноклассовой классификацией. Например, если у нас есть не размеченный датасет с аудиозаписями речи людей, то, обучив на нём генеративную модель, оценивающую в данном случае $P(X \vert Y)=P(X)$, мы сможем для нового аудио $x$ определить, похоже ли оно на аудиозапись человеческой речи (значение $P(x)$ велико), или это что-то другое: синтезированная речь, посторонний шум и т.п. ($P(x)$ мало). Тем не менее, если мы знаем, что "выбросы", с которыми модели предстоит сталкиваться, -- как правило, синтезированная речь, то, дополнив датасет вторым классов, состоящим из синтезированной речи и смоделировав также распределение этого класса, мы можем существенно увеличить качество детектирования таких выбросов.
Чтобы использовать генеративную модель для классификации, необходимо выразить $P(Y \vert X)$ через $P(X \vert Y)$ и $P(Y)$. Сделать это позволяет формула Байеса:
$$ P(y \vert x) = \frac{P(x, y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} $$
Классификация в генеративных моделях осуществляется с помощью байесовского классификатора:
$$a(x) = \arg\max\limits_{y\in Y} P(y \vert x) = \arg\max\limits_{y\in Y} \frac{P(y)P(x \vert y)}{\sum\limits_{y'\in Y} P(y')P(x \vert y')} = \arg\max\limits_{y\in Y} P(y)P(x \vert y)$$
Оценить $P(Y)$, как правило, несложно. Для этого используют частотные оценки, полученные обучающей выборке:
$$\hat P(Y=y) = \frac{\#(Y=y)}{N} \label{eq:class_proba_estimation} \tag{1}$$
Отметим ещё раз, что использование генеративного подхода позволяет внедрять в модель априорные знания о $P(y)$. Это не очень впечатляет, когда речь идёт о бинарной классификации, но всё меняется, если рассмотреть задачу ASR (автоматического распознавания речи), в которой по записи голоса восстанавливается произносимый текст. Таргетами здесь могут быть любые предложения или даже более развёрнутые тексты. При этом размеченных данных (запись, текст) обычно намного меньше, чем доступных текстов, и обученная на большом чисто текстовом корпусе языковая модель, которая будет оценивать вероятность того или иного предложения, может стать большим подспорьем, позволив из нескольких фонетически корректных наборов слов выбрать тот, который в большей степени похож на настоящее предложение.
Но как смоделировать распределение $P(X, Y)$? Пространство всех возможных функций распределения $P(X, Y)$ бесконечномерно, из-за чего оценить произвольное распределение с помощью конечной выборки невозможно. Поэтому перед оценкой $P(X, Y)$ на это распределение накладывают дополнительные ограничения. Некоторые простые примеры таких ограничений мы рассмотрим в следующих разделах.
Gaussian discriminant analysis
Модель гауссовского (или квадратичного) дискриминантного анализа (GDA) строится в предположении, что распределение объектов каждого класса $y$ подчиняется многомерному нормальному закону со средним $\mu_y$ и ковариационной матрицей $\Sigma_y$:
$$p(x \vert y) = \frac{1}{(2\pi)^{n/2} \vert \Sigma_y \vert ^{1/2}}\exp\left(-\frac{1}{2}(x-\mu_y)^T\Sigma_y^{-1} (x-\mu_y)\right) \label{eq:multivariate_normal}$$
Тогда функция правдоподобия $$\mathcal L(P(Y), \mu, \Sigma) = \prod_{i=1}^N p(x_i \vert y_i; \mu_{y_i}, \Sigma_{y_i})P(y_i)$$ достигает максимума при
$$ \hat\mu_y = \frac{\sum\limits_{i=1}^N{x_i\unicode{x1D7D9}_{y_i=y}}}{\sum\limits_{i=1}^N\unicode{x1D7D9}_{y_i=y}},\hspace{5mm} \hat\Sigma_y = \frac{\sum\limits_{i=1}^N{(x_i - \hat\mu_{y})(x_i - \hat\mu_{y})^T \unicode{x1D7D9}_{y_i=y}}}{\sum\limits_{i=1}^N\unicode{x1D7D9}_{y_i=y}} $$
И $\hat P(Y)$, представленной выше см. выражение $(1)$.
Рассмотрим, как выглядит разделяющая поверхность в модели GDA. На поверхности, разделяющей классы $y_i$ и $y_j$ выполняется
$$P(y_i \vert x)=P(y_j \vert x) \Leftrightarrow$$ $$p(x \vert y_i)P(y_i) = p(x \vert y_j)P(y_j)\Leftrightarrow$$ $$\log p(x \vert y_i) + \log P(y_i) - \log p(x \vert y_j) - \log P(y_j) = 0\Leftrightarrow$$
\begin{equation} -\frac{1}{2}(x-\mu_{y_i})^T\Sigma_{y_i}^{-1} (x-\mu_{y_i})-\log (2\pi)^{n/2}|\Sigma_{y_i}|^{1/2} + \log P(y_i) + \frac{1}{2}(x-\mu_{y_j})^T\Sigma_{y_j}^{-1} (x-\mu_{y_j}) + \log (2\pi)^{n/2}|\Sigma_{y_j}|^{1/2} - \log P(y_j) = 0 \label{eq:GDA_boundary} \tag{2} \end{equation}
Поскольку левая часть уравнения $ (2) $ квадратична по $x$, разделяющая поверность между двумя классами будет представлять из себя гиперповерность порядка 2. Пример разделяющей поверхности многоклассовой модели GDA приведён на рис.
Плотность классов и разделяющая поверхность в многоклассовой модели LDA см. рисунок.
Linear Discriminant Analysis
В выражении $ (2) $ член второго порядка $x^T (\Sigma_{y_j}^{-1} - \Sigma_{y_i}^{-1})x$ зануляется при $\Sigma_{y_i}=\Sigma_{y_j}$. Таким образом, если дополнительно предположить, что все классы имеют общую ковариационную матрицу $\Sigma$, разделяющая поверхность между любыми двумя классами будет линейной (см. рисунок). Поэтому такая модель называется линейным дискриминантным анализом (LDA).
На этапе обучения единственное отличие модели LDA от GDA состоит в оценке ковариационной матрицы: $$\hat \Sigma = \frac{1}{N}\sum\limits_{i=1}^N{(x_i - \hat\mu_{y_i})(x_i - \hat\mu_{y_i})^T}$$
Заметим, что в модели GDA для каждого класса требовалось оценить порядка $d^2$ параметров. Это может привести к переобучению в случае, если размерность пространства признаков велика, а некоторые классы представлены в обучающей выборке малым количеством объектов. В LDA для каждого класса требуется оценить лишь порядка $d$ параметров (значение $P(y)$ и элементы вектора $\mu_y$), и ещё $d^2$ общих для всех классов параметров (элементы матрицы $\Sigma$). Таким образом, основное преимущество модели LDA перед GDA -- её меньшая склонность к переобучению, недостаток -- линейная разделяющая поверхность.
Метод наивного байеса
Предположим, что признаки $X$ объектов каждого класса $y$ -- независимые случайные величины:
$$\forall y\in Y \hspace{2mm} \forall U, V: U\sqcup V = {1, ... d}, \hspace{2mm} \forall x^u\subset \mathbb R^{|U|}, x^v\subset \mathbb R^{|V|}$$
$$P(X^U\in x^u, X^V\in x^v|Y=y) = P(X^U\in x^u|Y=y)P(X^V\in x^u|Y=y).$$
В таком случае говорят, что величины $X$ условно независимы отностиельно $Y$. Тогда справедливо
\begin{equation}\label{eq:cond_independent} P(X \vert Y) = P(X^1, X^2, ..., X^d \vert Y) = P(X^1 \vert Y)P(X^2, ..., X^d \vert Y) = ... = P(X^1 \vert Y)P(X^2 \vert Y)...P(X^d \vert Y) \tag{3} \end{equation}
То есть для того, чтобы оценить плотность многомерного распределения $P(X \vert Y)$ достаточно оценить плотности одномерных распределений $P(X^i \vert Y)$, см. рисунок.
На рисунке приведён пример условно независимых относительно $Y$ случайных величин $X^1, X^2$. Для оценки плотности двумерных распределений объектов классов достаточно оценить плотности маргинальных распределений, изображённые графиками вдоль осей.
Рассмотрим пример. Пусть решается задача классификации отзывов об интернет-магазине на 2 категории: $Y=0$ -- отрицательный отзыв, клиент остался не доволен, и $Y=1$ -- положительный отзыв. Пусть признак $X^w$ равен 1, если слово $w$ присутствует в отзыве, и 0 иначе. Тогда условие $ (3) $ означает, что, в частности, наличие или отсутствие слова ''дозвониться'' в отрицательном отзыве не влияет на вероятность наличия в этом отзыве слова ''телефон''.
На практике в процессе feature engineering почти всегда создаётся много похожих признаков, и условно независимые признаки можно встретить очень редко. Поэтому генеративную модель, построенную в предположении условия $ (3) $, называют наивным байесовским классификатором (Naive Bayes classifier, NB).
Обучение модели NB заключается в оценке распределений $P(Y)$ и $P(X^i \vert Y)$. Для $P(Y)$ можно использовать частотную оценку $ (1) $. $P(X^i \vert y)$ -- одномерное распределение. Рассмотрим несколько способов оценки одномерного распределения.
Оценка одномерного распределения
Пусть мы хотим оценить одномерное распределение $P(X)$.
Если распределение $P(X)$ дискретное, требуется оценить его функцию массы, т.е. вероятность того, что величина $X$ примет значение $x_j$. Метод максимума правдоподобия приводит к частотной оценке:
$$ \hat P(X = x_j) = \frac{\#(X = x_j)}{N} \tag{4} $$
Где $N$ -- размер выборки, по которой оцениватеся распределение $X$ (количество объектов класса $y$ в случае оценки плотности класса $y$).
При этом может оказаться, что некоторое значение $x_j$ ни разу не встречается в обучающей выборке. Например, в случае классификации отзывов методом Наивного Байеса, слово ''амбивалентно'' не встретилось ни в одном положительном отзыве, но встретилось в отрицательных. Тогда использование оценки приведёт к тому, что все отзывы с этим словом будут определяться NB как отрицательные с вероятностью 1. Чтобы избежать принятия таких радикальных решений при недостатке статистики, используют сглаживание Лапласа:
$$\hat P(X = x_j) = \frac{\#(X = x_j) + \alpha}{N + m\alpha},$$
где $m$ -- количество различных значений, принимаемых случайной величиной $X$, $\alpha$ -- гиперпараметр.
Для оценки плотности $p$ абсолютно непрерывного распределения в точке $a$ можно разделить количество объектов обучающей выборки в окрестности точки $a$ на размер этой окрестности:
$$\hat p(a) = \frac{\sum\limits_{j}\unicode{x1D7D9}_{a - h < X_j < a + h}}{2h} = \frac{\sum\limits_{j}\unicode{x1D7D9}_{-h < X_j - a < h}}{2h}.$$
Обычно объекты, лежащие дальше от точки $a$, учитывают с меньшим весом. Таким образом, оценка плотности приобретает вид
$$\hat p(a) = \frac{\sum\limits_{j}K_h(X_j - a)}{2h},$$
где функция $K_h$, называемая ядром, обычно имеет носитель $(-h, h)$ (см. рисунок). Такой способ оценки плотности называют непарамерическим.
Результат оценки плотности с разными ядрами. Использованы изображения из:
При параметрической оценке плотности предполагают, что искомое распределение лежит в параметризованном классе, и подбирают значения параметров при помощи метода максимума правдоподобия. Например, предположим, что искомое распределение нормальное. Тогда функция его плотности имеет вид
$$p(x) = \frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$$
Таким образом, чтобы оценить плотность $p(x)$, достаточно оценить параметры $\mu, \sigma$. Метод максимума правдоподобия в этом случае даст такие оценки:
$\hat\mu = \overline X$ -- выборочное среднее, $\hat\sigma = \sqrt{\frac{1}{N}\sum_{j=1}^N (X_j - \overline X)}$ -- выборочное стандартное отклонение.
Если в модели NB распределения всех признаков объектов каждого класса нормальные, оценив параметры этих распределений, мы сможем каждый класс $y$ описать нормальным распределением со средним $\mu_p$ и диагональной ковариационной матрицей, значения на диагонали которой обозначим $\sigma_p$. Таким образом, полученная модель (Gaussian Naive Bayes, GNB) эквивалентна модели GDA с дополнительным ограничением на диагональность ковариационных матриц.
Наивный байесовский подход и логистическая регрессия
Предположим теперь, что в модели GNB класса всего 2, причём соответствующие им ковариационные матрицы совпадают, как это было в модели LDA. Таким образом $\sigma_0 = \sigma_1 = \sigma$.
Посмотрим, как будет выглядеть $P(Y \vert X)$ в этом случае. По теореме Байеса имеем
$$P(Y=1 \vert X) = \frac{P(Y = 1)P(X \vert Y = 1)}{P(Y = 1)P(X \vert Y = 1) + P(Y = 0)P(X \vert Y = 0)}$$
Разделим числитель и знаменатель полученного выражения на числитель:
$$P(Y=1 \vert X) = \frac{1}{1 + \frac{P(Y = 0)P(X \vert Y = 0)}{P(Y = 1)P(X \vert Y = 1)}} = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)P(X \vert Y=0)}{P(Y=1)P(X \vert Y=1)}\right)}$$
Из условной независимости $X^i$ относительно $Y$ получаем
\begin{equation}\label{eq:posterior} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)}\right)} \tag{5} \end{equation}
Перепишем сумму в знаменателе, воспользовавшись формулой плотности нормального распределения
$$\sum\limits_{i=1}^d \ln\frac{P(X^i \vert Y=0)}{P(X^i \vert Y=1)} = \sum\limits_{i=1}^d \ln\frac{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{0,i})^2}{2\sigma_i^2}\right)}{\frac{1}{\sqrt{2\pi\sigma_i^2}}\exp \left(\frac{-(X^i - \mu_{1,i})^2}{2\sigma_i^2}\right)} $$
$$= \sum\limits_{i=1}^d \frac{\left(X^i - \mu_{1, i}\right)^2 - \left(X^i - \mu_{0, i}\right)^2}{2\sigma_i^2}= \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)$$
Подставляя это выражение в формулу $ (5) $, получаем
$$P(Y=1 \vert X) = \frac{1}{1 + \exp\left(\ln\frac{P(Y=0)}{P(Y=1)} + \sum\limits_{i=1}^d \left(\frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2}X^i + \frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}\right)\right)}$$
Таким образом, $P(Y=1 \vert X)$ представляется в GNB с общей ковариационной матрицей в таком же виде, как в модели логистической регрессии:
\begin{equation} \label{eq:logreg} P(Y=1 \vert X) = \frac{1}{1 + \exp\left(w_0 + \sum\limits_{i=1}^d w_i X^i\right)} \tag{6} \end{equation}
где в случае GNB
$$w_0 = \ln\frac{P(Y=1)}{P(Y=0)} +\sum\limits_{i=1}^d\frac{\mu_{1, i} ^ 2 - \mu_{0, i} ^ 2}{2\sigma_i^2}, \quad w_i = \frac{\mu_{0, i} - \mu_{1, i}}{\sigma_i^2} \hspace{1cm} i=1, \dots, l$$
Однако это не значит, что модели эквивалентны: модель логистической регрессии накладывает менее строгие ограничения на распределение $P(X, Y)$, чем GNB. Так, $X^i$ могут не являться условно независимыми относительно $Y$, а распределения $P(X \vert Y=y)$ могут не удовлетворять нормальному закону, но $P(y \vert X)$ может при этом всё равно представляться в виде $ (6) $. В этом случае использование метода логистической регрессии предпочтительнее. С другой стороны, если есть основания полагать, что требования GNB выполняются, то от GNB можно ожидать более высокого качества классификации по сравнению с логистической регрессией.