Порождающие модели, LDA и QDA

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

Два вида ириса как два облака

Возьмём знаменитую таблицу ирисов и оставим два вида, которые действительно трудно различить: versicolor и virginica, по $50$ цветков каждого. Признаков два — длина и ширина лепестка. Средние получаются такими:

$$\mu_{\text{versicolor}}=(4{,}26;\,1{,}33),\qquad \mu_{\text{virginica}}=(5{,}55;\,2{,}03).$$

Дискриминативный подход спросил бы сразу: где провести черту? Порождающий задаёт другой вопрос — как выглядит облако каждого вида. Для класса $k$ мы задаём плотность $p(x\mid y=k)$ и априорную вероятность $P(y=k)=\pi_k$. После измерения цветка правило Байеса переворачивает историю:

$$P(y=k\mid x)= \frac{p(x\mid y=k)\,\pi_k} {\sum_j p(x\mid y=j)\,\pi_j}.$$

Знаменатель одинаков для всех $k$, поэтому побеждает класс с наибольшим числителем. Удобнее сравнивать логарифмы: граница между классами $a$ и $b$ — это множество точек, где

$$\log p(x\mid y=a)+\log\pi_a = \log p(x\mid y=b)+\log\pi_b.$$

Из этой одной строки вырастает весь урок. Слева и справа стоят два слагаемых: «насколько признаки похожи на класс» и «насколько класс вообще част». Меняя предположение о форме плотности, мы получаем LDA, QDA или naive Bayes. Меняя $\pi_k$, мы двигаем границу, не трогая ни одной точки. Сама формула — это урок 42, просто записанный для непрерывных признаков.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Развилка: описывать мир или сразу отвечать

У двух подходов разная валюта. Дискриминативная модель тратит всю выразительность на границу и ничего не знает про то, как устроены признаки. Порождающая тратит её на описание облаков — и получает бонусы, которые границе недоступны: маргинализацию пропусков, генерацию новых объектов, обнаружение аномалий (объект, лежащий далеко от всех классов, имеет маленькую $p(x)$), пересчёт под другой prior.

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

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

Оценка параметров: правдоподобие снова даёт средние

Откуда берутся $\mu_k$ и $\Sigma_k$? Из того же принципа максимума правдоподобия, что и в уроке 45. Логарифм правдоподобия выборки разбивается на независимые куски по классам:

$$\ell(\theta)=\sum_{i=1}^{n}\Big[\log\pi_{y_i}+\log p(x_i\mid y_i)\Big],$$

и максимум по $\mu_k$ достигается на выборочном среднем класса

$$\widehat\mu_k=\frac1{n_k}\sum_{i:\,y_i=k}x_i,$$

а максимум по $\pi_k$ — на выборочной частоте $\widehat\pi_k=n_k/n$. Для ковариаций QDA берёт внутриклассовые матрицы, а LDA — их взвешенное среднее, объединённую (pooled) оценку:

$$\widehat\Sigma=\frac{\sum_k (n_k-1)\widehat\Sigma_k}{n-K}.$$

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

LDA: одна общая форма разброса

Linear Discriminant Analysis делает самое экономное предположение:

$$x\mid y=k\sim N(\mu_k,\Sigma),$$

средние разные, а матрица разброса общая. Подставим логарифм нормальной плотности

$$\log p(x\mid y=k)= -\tfrac12(x-\mu_k)^\top\Sigma^{-1}(x-\mu_k) -\tfrac12\log\det\Sigma-\tfrac d2\log 2\pi$$

и раскроем скобки. Член $-\tfrac12x^\top\Sigma^{-1}x$ не зависит от $k$ и при сравнении классов сокращается, как и константы. Остаётся линейная дискриминантная функция

$$\delta_k(x)= x^\top\Sigma^{-1}\mu_k -\tfrac12\mu_k^\top\Sigma^{-1}\mu_k +\log\pi_k .$$

Граница между двумя классами — множество $\{\delta_a(x)=\delta_b(x)\}$, то есть гиперплоскость. Вот её явный вид:

$$(\mu_a-\mu_b)^\top\Sigma^{-1}x =\tfrac12(\mu_a-\mu_b)^\top\Sigma^{-1}(\mu_a+\mu_b) -\log\frac{\pi_a}{\pi_b}.$$

Направление нормали к границе — не $\mu_a-\mu_b$, а $\Sigma^{-1}(\mu_a-\mu_b)$. Ковариация выступает метрикой: отличие вдоль шумного направления весит меньше, чем такое же евклидово отличие вдоль стабильного. Тот же приём «поделить на разброс» мы видели в уроке 38, когда искали главные оси.

QDA: каждому классу своя геометрия

Quadratic Discriminant Analysis отпускает ограничение:

$$x\mid y=k\sim N(\mu_k,\Sigma_k).$$

Теперь член $-\tfrac12x^\top\Sigma_k^{-1}x$ зависит от класса и не сокращается, а к сравнению добавляется разность логарифмов определителей:

$$\delta_k(x)= -\tfrac12(x-\mu_k)^\top\Sigma_k^{-1}(x-\mu_k) -\tfrac12\log\det\Sigma_k+\log\pi_k .$$

Граница становится квадрикой — параболой, гиперболой или эллипсом. Модель способна описать компактный класс внутри рассеянного или два облака с разной ориентацией. На наших ирисах разброс virginica заметно больше: отношение определителей ковариаций равно $6{,}26$, то есть «площадь» облака virginica примерно в шесть раз больше. Неудивительно, что QDA на тех же точках даёт $97\%$ против $94\%$ у LDA, а на честном разбиении $60/40$ — $97{,}5\%$ против $95{,}0\%$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Когда гибкость становится обузой

Проверим этот счёт на реальных данных. Возьмём таблицу диагностики рака груди из sklearn ($30$ признаков), обучим на маленькой выборке из $60$ объектов и проверим на оставшихся $509$. Будем добавлять признаки по одному и смотреть, что происходит с точностью на тесте.

При пяти признаках QDA впереди: $93{,}5\%$ против $90{,}8\%$ у LDA — данные действительно не устроены с общей ковариацией, и гибкость окупается. Но при всех тридцати признаках QDA обваливается до $62{,}7\%$, тогда как LDA держит $88{,}8\%$. Причина не в том, что QDA «хуже», а в том, что при $d=30$ она просит $930$ ковариационных параметров, имея примерно $30$ объектов на класс. Матрицы почти вырождены, и модель начинает верить случайным направлениям. Заметьте, чему именно равны эти $62{,}7\%$: это в точности доля частого класса в тесте. QDA не просто ошибается чаще — она перестаёт различать классы и отвечает одинаково на всех $509$ объектах.

Компромисс лечит болезнь. Стягивание ковариаций к сферической матрице,

$$\widetilde\Sigma_k=(1-\gamma)\widehat\Sigma_k+\gamma\,\sigma^2 I ,$$

при $\gamma=0{,}5$ даёт $93{,}7\%$ — лучший результат из трёх. Это та же идея регуляризации, что и в уроке 51: чуть-чуть сместить оценку, чтобы резко уменьшить её разброс.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лаборатория эллипсов

Порядок опытов такой. Сначала не трогайте ползунки формы: облака почти одинаковы, и все три модели дают близкие границы — но QDA при этом оценивает десять параметров вместо семи, то есть платит за гибкость, которой не пользуется. Затем растяните и поверните красный класс: прямая LDA перестаёт справляться, а дуга QDA огибает вытянутое облако. Переключитесь на naive Bayes — его эллипсы принудительно выпрямляются по осям, и на повёрнутом облаке он проигрывает обоим соседям. Наконец, не двигая ни одной точки, уменьшите prior редкого класса до нескольких процентов: красная область сжимается, доля пойманных объектов редкого класса падает. Данные не изменились — изменилось представление о том, как часто такой класс вообще встречается.

Prior двигает границу, не трогая точек

Разберём этот эффект в самом прозрачном виде — на модельном одномерном примере (данных здесь нет, только две нормальные плотности, зато всё считается до конца). Пусть для обычного класса $X\mid Y=0\sim N(0,1)$, а для редкого $X\mid Y=1\sim N(2,1)$. Логарифм отношения плотностей линеен:

$$\log\frac{p(x\mid1)}{p(x\mid0)}=2x-2 .$$

При равных prior граница $P(Y=1\mid x)=1/2$ проходит через $x=1$. Пусть теперь редкий класс встречается лишь в $2\%$ случаев. К логарифму отношения правдоподобий добавляется

$$\log\frac{0{,}02}{0{,}98}\approx-3{,}89,$$

и граница уезжает вправо:

$$x_*=1-\tfrac12\log\frac{0{,}02}{0{,}98}\approx2{,}95 .$$

Наблюдение $x=2$ лежит ровно в центре редкого класса, но апостериорная вероятность для него — всего $13{,}1\%$ вместо $88{,}1\%$ при равных prior. Похожий сигнал слишком часто возникает среди гораздо более многочисленных обычных объектов. Это ровно ошибка прокурора из урока 43, только записанная плотностями.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Практический вывод жёсткий. Если модель обучали на искусственно сбалансированной таблице, а в реальности редкий класс составляет $2\%$, то граница $x=1$ поймает $84{,}1\%$ редких объектов, но лишь $9{,}8\%$ её тревог окажутся верными — меньше каждой десятой. Сдвиг границы к $x_*=2{,}95$ поднимает долю верных тревог до $68{,}6\%$ ценой падения полноты до $17{,}2\%$. Это не улучшение и не ухудшение модели: это выбор точки на кривой компромисса, и делать его должен тот, кто знает цену ошибок.

Naive Bayes: смелая независимость

Для текста с тысячами признаков полная ковариация безнадёжна: матрицу $3000\times3000$ по нескольким тысячам писем не оценить. Naive Bayes делает предположение, которое заведомо неверно, но спасает счёт:

$$p(x\mid y=k)=\prod_{j=1}^{d}p(x_j\mid y=k).$$

Для счётчиков слов берут мультиномиальную модель со сглаживанием из урока 48, и решающая функция превращается в сумму вкладов слов:

$$\log\frac{P(y=\text{спам}\mid x)}{P(y=\text{ham}\mid x)} =\log\frac{\pi_{\text{спам}}}{\pi_{\text{ham}}} +\sum_j x_j\log\frac{\theta_{j,\text{спам}}}{\theta_{j,\text{ham}}} .$$

Проверим на настоящем корпусе SMS Spam Collection: $5574$ сообщения, из них $13{,}4\%$ спама, словарь после отсечения редких слов — $3236$ слов, тест $1673$ сообщения. Наивный Байес даёт $98{,}6\%$ верных ответов, точность на спаме $95{,}9\%$, полноту $93{,}3\%$. Логистическая регрессия на тех же признаках — $97{,}9\%$. Модель, чьё главное предположение очевидно ложно (слова «машинное» и «обучение» приходят вместе), обыгрывает аккуратную дискриминативную модель.

Ранжирует хорошо, вероятности врёт

А теперь посмотрим не на решение, а на число, которое модель выдаёт вместе с ним. У наивного Байеса $89{,}4\%$ ответов лежат вне интервала $[0{,}01;\,0{,}99]$ — он почти всегда абсолютно уверен. У логистической регрессии таких ответов $66{,}8\%$. Середина шкалы у наивного Байеса практически пуста: в диапазоне «сомневаюсь» почти нет писем.

Причина прямо в формуле произведения. Если два признака дублируют друг друга, их вклады складываются дважды. Для двух нормальных признаков с корреляцией $\rho=0{,}9$ верная модель даёт в точке $x_1=x_2=0{,}5$ апостериорную вероятность $74{,}1\%$, а наивная — $88{,}1\%$: одно и то же свидетельство засчитано дважды. В тексте, где слова идут устойчивыми оборотами, такой пересчёт происходит десятки раз, и log-odds раздуваются.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Порождающая модель умеет работать с пропусками

Вот бонус, ради которого стоит описывать облака. Если у объекта не измерен один признак, порождающая модель не обязана ничего выдумывать — она интегрирует неизвестную координату:

$$p(x_{\text{obs}}\mid y=k)= \int p(x_{\text{obs}},x_{\text{miss}}\mid y=k)\,dx_{\text{miss}} .$$

Для многомерной нормали интеграл берётся руками: маргинальное распределение наблюдаемых координат — снова нормальное, с соответствующим куском среднего и соответствующим блоком ковариации:

$$x_{\text{obs}}\mid y=k\sim N\big(\mu_k^{\text{obs}},\,\Sigma_k^{\text{obs,obs}}\big).$$

Никакой подстановки среднего, никакого «заполним нулём» — просто честное взвешивание всех возможных значений пропущенной координаты.

Проверим на ирисах, насколько это важно. Возьмём цветок с длиной лепестка $5{,}0$ и шириной $1{,}5$ см. По двум признакам модель уверенно говорит versicolor: вероятность virginica всего $20{,}2\%$. Забудем ширину — остаётся только длина, граница по ней проходит в $4{,}91$ см, и наш цветок оказывается справа от неё: вероятность virginica $61{,}4\%$. Приговор поменялся на противоположный. Всего таких переворотов среди ста цветков — $10$, а точность падает с $94{,}0\%$ до $92{,}0\%$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Однако сам механизм пропуска нельзя игнорировать. Если лаборатория реже назначает дорогой анализ здоровым пациентам, то факт отсутствия значения — это улика. Формула маргинализации молча предполагает, что пропуск не зависит от класса при известных наблюдаемых признаках. Если это не так, надо моделировать индикатор измерения $m$ как ещё один признак:

$$p(x_{\text{obs}},m\mid y=k)= p(m\mid y=k)\,p(x_{\text{obs}}\mid m,y=k).$$

Связь с логистической регрессией

Есть удивительный факт: для двух нормальных классов с общей ковариацией логарифм отношения апостериорных вероятностей строго линеен по $x$:

$$\log\frac{P(y=1\mid x)}{P(y=0\mid x)} =w^\top x+b,\qquad w=\Sigma^{-1}(\mu_1-\mu_0).$$

То есть

$$P(y=1\mid x)=\sigma(w^\top x+b),$$

в точности форма логистической регрессии из урока 53. Две модели дают один и тот же класс решающих функций и различаются лишь способом подбора параметров. LDA оценивает $\mu_k,\Sigma,\pi_k$ по правдоподобию совместного распределения $p(x,y)$; логистическая регрессия максимизирует условное правдоподобие $P(y\mid x)$ и вообще не описывает $p(x)$.

Отсюда честный компромисс. Если нормальная история близка к правде, LDA использует дополнительную структуру и на малых выборках выигрывает: она берёт информацию из расположения признаков, а не только из меток. Если история неверна — тяжёлые хвосты, категориальные признаки, смеси, — LDA тратит силы на описание того, что ей не нужно, и логистическая регрессия оказывается устойчивее. Выбор делают по диагностике и честной проверке на отложенных данных (урок 32), а не по ярлыкам «классический» и «современный».

Ченцов: решающие правила как геометрия

Порождающий подход — часть общей теории статистических решений, и здесь уместно вспомнить Николая Николаевича Ченцова (1930–1992), математика из Института прикладной математики. В 1962 году он предложил проекционные оценки плотности: неизвестную $p(x)$ раскладывают по ортогональной системе функций и оценивают конечное число коэффициентов

$$\widehat p(x)=\sum_{j=1}^{m}\widehat c_j\varphi_j(x),\qquad \widehat c_j=\frac1n\sum_{i=1}^{n}\varphi_j(x_i),$$

— прямой ответ на вопрос «как оценивать $p(x\mid y=k)$, не предполагая нормальности». Число $m$ здесь играет роль сложности модели ровно так же, как степень полинома в уроке 50. А в монографии «Статистические решающие правила и оптимальные выводы» (1972) Ченцов показал, что семейство распределений естественно рассматривать как многообразие, на котором есть единственная (с точностью до множителя) метрика, не меняющаяся при разумных преобразованиях данных, — информационная метрика Фишера.

Для нас это не абстракция. Возьмём семейство $N(\mu,\Sigma)$ с фиксированной $\Sigma$ и параметром $\mu$: матрица информации Фишера равна ровно $\Sigma^{-1}$, а расстояние по метрике Ченцова—Фишера между $N(\mu_a,\Sigma)$ и $N(\mu_b,\Sigma)$ — это в точности $d_M(\mu_a,\mu_b)$. Та же формула, которой мы меряли близость точки к центру класса. Когда мы делим отклонение на разброс, мы не подгоняем формулу под удобство, а пользуемся единственной метрикой, которую не портит замена признаков. Теорема Ченцова объясняет, почему все разумные способы измерять различие распределений приводят в одну и ту же точку.

Матрица цен: от вероятности к действию

Даже идеально откалиброванная вероятность ещё не решение. Выбирают действие $a$ с минимальным условным риском

$$R(a\mid x)=\sum_k c(a,k)\,P(y=k\mid x),$$

где $c(a,k)$ — цена действия $a$, когда истина есть $k$. Для двух действий «тревога» и «молчание» с ценами $c_{\text{FP}}$ и $c_{\text{FN}}$ сравнение рисков даёт порог

$$P(y=1\mid x)>\frac{c_{\text{FP}}}{c_{\text{FP}}+c_{\text{FN}}} .$$

Если пропуск больного в двадцать раз дороже ложной тревоги, порог равен $1/21\approx0{,}048$ — далеко не $0{,}5$. Получается ясное разделение труда: плотности описывают форму классов, prior описывает популяцию, матрица цен задаёт действие. Каждый из трёх кусков ошибается по-своему и чинится отдельно; подробно риск разбирается в уроке 57.

Что проверять на практике

Соберём чек-лист порождающего классификатора. Первое: откуда взялись $\pi_k$ — из естественной выборки или из дизайна сбора данных. Второе: похожи ли облака на эллипсы; если признаки скошены, помогает логарифмирование или ранговое преобразование — до подгонки, а не после. Третье: хватает ли объектов на ковариации; правило грубое, но полезное — на каждый класс нужны хотя бы десятки объектов на каждый признак, иначе стягивание обязательно. Четвёртое: отдельно измерить качество решений (точность, полнота) и качество вероятностей (кривая калибровки, логарифмическая потеря). Пятое: если данные приходят с пропусками, выяснить, как они возникают, а не только чем их заполнить. И последнее — помнить, что за пределами области, где облака поддержаны данными, любая плотность экстраполирует, а значит, нужна отдельная карта неопределённости.

Итог

Порождающий классификатор описывает, как класс порождает признаки, и добавляет частоту классов; правило Байеса превращает это описание в ответ. LDA с общей ковариацией даёт линейную границу и метрику Махаланобиса, QDA с отдельными матрицами — квадратичную границу и куда более дорогой счёт параметров, naive Bayes заменяет совместную плотность произведением и выживает там, где признаков тысячи. Сильная сторона подхода — содержательная модель мира: пропуски, аномалии, смена prior обрабатываются одной формулой. Слабая — та же самая модель: если история про облака неверна, ошибка уходит в вероятности, даже когда решения остаются правильными.

Задачи