Генеративные методы классификации

Два подхода к классификации

До этого момента мы рассматривали классификацию преимущественно с дискриминативной точки зрения. Дискриминативные модели (discriminative models) стремятся напрямую найти границы между классами, настраивая дискриминантные функции $\{g_y(\boldsymbol{x})\}_y$ или оценивая условную вероятность $p(y|\boldsymbol{x})$, чтобы по ним настроить разделяющую поверхность в пространстве признаков.

Однако существует принципиально иной путь — генеративные модели (generative models), представляющие собой разновидность вероятностых моделей, в которых мы

• явно моделируем плотность распределения признаков для каждого класса $p(\boldsymbol{x}|y=c)$;

• учитываем, насколько часто в целом тот или иной класс встречается через его априорную вероятность $p(y=c)$.

В генеративном подходе настраиваемыми параметрами выступают априорные распределения классов $p(y=c)$ и параметры модельного распределения $p(\boldsymbol{x}|y=c)$, которые оцениваются методом максимального правдоподобия.

Метод называется генеративным, потому что, построив такую модель, мы можем генерировать новые объекты $(\boldsymbol{x},y)$:

$$(\boldsymbol{x},y)\sim P(\boldsymbol{x},y)=P(y)P(\boldsymbol{x}|y)$$

по следующей процедуре:

1. сэмплируем класс объекта $y\sim\text{Categorical}\{p(y=1,...y=C)\}$;

2. сэмплируем сам объект из модельного распределения $\boldsymbol{x}\sim p(\boldsymbol{x}|y=c)$.

Правило построения прогнозов

Генеративные модели, будучи вероятностными моделями, прогнозируют класс по принципу максимальной вероятности:

$$\hat{y} = \arg\max_c p(y=c|\boldsymbol{x}),$$

что по определению условной вероятности эквивалентно переписываются в следующем виде:

$$\hat{y} = \arg\max_c \frac{p(\boldsymbol{x}|y=c) p(y=c)}{p(\boldsymbol{x})}$$

Так как знаменатель $P(\boldsymbol{x})$ одинаков для всех классов, он не влияет на результат, и его можно отбросить:

$$\hat{y} = \arg\max_c \{ P(\boldsymbol{x}|y=c) p(y=c) \}$$

Эквивалентно можно искать максимум не самой вероятности, а её логарифма:

$$\hat{y} = \arg\max_c \{ \log ( P(\boldsymbol{x}|y=c) p(y=c)) \} = \arg\max_c \{ \log ( P(\boldsymbol{x}|y=c)+\log p(y=c) \}$$

Таким образом, дискриминантными функциями в генеративных моделях являются

$$g_c(\boldsymbol{x}) = \ln p(\boldsymbol{x}|y=c) + \ln p(y=c), \quad c=1,2,...C$$

Настройка генеративных моделей

Для обучения генеративной модели необходимо оценить набор её параметров $\boldsymbol{\Theta}$. В него входят априорные вероятности классов $\pi_c = p(y=c)$ и параметры плотностей распределения объектов внутри каждого класса $\boldsymbol{\theta}_c$ (например, вектора средних и ковариационные матрицы):

$$\boldsymbol{\Theta} = \left\{ \{\pi_c\}_{c=1}^C, \{\boldsymbol{\theta}_c\}_{c=1}^C \right\}$$

Настройка параметров осуществляется через максимизацию логарифма правдоподобия совместного распределения признаков и меток классов обучающей выборки. Данный подход называется метод максимального правдоподобия (Maximum Likelihood Estimation, MLE). Оптимизационная задача в общем виде записывается следующим образом:

$$\mathcal{L}(\boldsymbol{\Theta}) = \sum_{n=1}^N \ln p(\boldsymbol{x}_n, y_n | \boldsymbol{\Theta}) \to \max_{\boldsymbol{\Theta}}$$

Используя определение совместной вероятности $p(\boldsymbol{x}_n, y_n) = p(\boldsymbol{x}_n | y_n, \boldsymbol{\theta}_{y_n}) \cdot \pi_{y_n}$, логарифм правдоподобия можно разложить на две составляющие:

$$\mathcal{L}(\boldsymbol{\Theta}) = \sum_{n=1}^N \ln p(\boldsymbol{x}_n | y_n, \boldsymbol{\theta}_{y_n}) + \sum_{n=1}^N \ln \pi_{y_n} \to \max_{\{\pi_c\}, \{\boldsymbol{\theta}_c\}}$$

При этом на априорные вероятности накладывается ограничение $\sum_{c=1}^C \pi_c = 1$. Решение этой задачи для $\pi_c$ даёт естественную оценку доли объектов каждого класса в выборке:

$$\pi_c = \frac{N_c}{N},$$

где $N_c$ — количество объектов класса $c$.

Независимость настройки

Из формулы оптимизационной задачи видно, что параметры каждого класса $\boldsymbol{\theta}_c$ настраиваются независимо друг от друга. Для каждого класса $c$ решается своя подзадача оптимизации:

$$\sum_{n: y_n=c} \ln p(\boldsymbol{x}_n | \boldsymbol{\theta}_c) \to \max_{\boldsymbol{\theta}_c}$$

Параметры правдоподобия

Выбор конкретного вида распределения $p(\boldsymbol{x} | y=c, \boldsymbol{\theta}_c)$ определяет сложность и гибкость модели.

• Если признаки внутри класса распределены по многомерному нормальному закону, то параметрами $\boldsymbol{\theta}_c$ будут выступать вектор среднего $\boldsymbol{\mu}_c$ и ковариационная матрица $\Sigma_c$.

• Если признаки считаются независимыми при условии класса, мы получаем наивный байесовский классификатор (Naive Bayes), где параметры оцениваются для каждого признака $\boldsymbol{x}^i$ отдельно, что упрощает обучение модели.

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

Сравнение подходов

Выбор между генеративным и дискриминативным подходами зависит от объема данных и решаемой задачи.

Преимущества генеративных моделей

1. Работа с пропусками: они позволяют классифицировать объекты, у которых часть признаков $\boldsymbol{x}^i$ отсутствует, путем интегрирования по распределению пропущенных признаков.
2. Детекция аномалий: если значение $p(\boldsymbol{x})$ очень мало для всех классов, мы можем сделать вывод, что объект является выбросом (outlier), и обрабатывать его отдельно.
3. Эффективность на малых данных: они сходятся к лучшему решению, чем дискриминативные, если предположение о виде распределения $p(\boldsymbol{x}|y=c)$ оказалось близким к истинному.

Риск неверной модели

Если же наше предположение о виде распределения $p(\boldsymbol{x}|y=c)$ окажется далёким от истинного, генеративная модель будет давать смещённый прогноз даже для больших выборок!

Преимущества дискриминативных моделей

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