Не-наивный байесовский классификатор в машинном обучении

Не-наивный байесовский классификатор

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение с учителем на языке Python».

В этой статье мы обсудим не-наивный байесовский классификатор, использовав эту возможность, чтобы получить более глубокое представление о работе наивного байесовского классификатора.

А также мы изучим LDA и QDA анализы, генеративные и дискриминативные модели.

Напомню, что наивным байесовский классификатор называется потому, что каждый из входных признаков является независимым. В случае же не-наивного байесовского классификатора входные признаки не являются независимыми. Возникает вопрос: как тогда вычислить p(X|C)?

На самом деле это весьма дискуссионный вопрос, и решать его можно по своему усмотрению. К примеру, если использовать полную ковариационную матрицу вместо диагональной (которой мы пользовались в случае наивного байесовского классификатора), то получится не-наивный байесовский классификатор. Почему так, мы обсудим позже. Можно воспользоваться и более сложной моделью, такой как скрытая марковская модель, которая обсуждалась в моём курсе по скрытым марковским моделям. Можно применить даже более сложные модели вроде собственной байесовской сети, которая выходит за рамки данного курса. Но, по сути, нужно точно смоделировать, как каждая переменная взаимодействует с другими и с каким распределением, а правильность своих предположений можно проверить, сравнивания точность моделей.

Выводы же таковы: моделировать вероятность p(X|C) можно на своё усмотрение, причём с любой степенью сложности.

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

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

Но здесь есть одно исключение: гауссово распределение. Если две переменные имеют гауссово распределение и их ковариация равна нулю, то они независимы. Напомню, что ковариационная матрица – это просто попарные ковариации каждого из Xi и Xj, где i и j пробегают значения от 1 до D. Поэтому каждый элемент, расположенный на диагонали, – это просто обычная дисперсия для данной размерности, а каждый внедиагональный ij-й элемент – это ковариация между двумя признаками Xi и Xj. Следовательно, если все внедиагональные элементы равны нулю, то мы имеем случай наивного байесовского классификатора, поскольку каждую размерность можно разделить на отдельный гауссиан и перемножить их. Если же внедиагональные элементы не равны нулю, то мы вынуждены применить общий метод решения, требующий нахождения обратной матрицы и детерминанта ковариационной матрицы с использованием более общего алгоритма.

К счастью,  поскольку мы воспользуемся функцией logpdf библиотеки Scipy, нам не потребуется вносить много изменений в алгоритм: данная функция принимает в качестве аргумента как единичную скалярную дисперсию или диагональную ковариацию, так и полную ковариационную матрицу. Так что нет нужды беспокоиться о том, как это реализовать, хотя, если у вас есть такое желание, можете попробовать. К сожалению, если вы всё же решитесь сделать это сами в Python, работать всё будет намного медленнее, поскольку библиотека Scipy специально оптимизирована для более быстрых вычислений такого рода. Если у вас есть в этом сомнения, рекомендую в качестве упражнения написать собственную программу для вычисления логарифма плотности распределения вероятностей и сравнить скорость работы.

И последнее замечание. Как правило, не-наивный байесовский классификатор так не называют; обычно применяется просто название «байесовский классификатор». В более общем случае – байесовская модель, которая может быть как классификатором, так и регрессией.

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

Теперь мы пройдёмся по основным изменениям в коде для не-наивного байесовского классификатора применительно к базе MNIST и посмотрим на результат. Как вы увидите, он работает куда лучше, чем «наивная» версия. Соответствующий файл для этого занятия называется bayes.py.

Первое отличие – в функции fit мы вычисляем и сохраняем ковариацию вместо дисперсии. Заметьте, что в библиотеке Numpy уже имеется для этого функция, но вначале мы должны транспонировать X, чтобы оно получило размерность DxD; в противном случае Numpy неправильно поймёт задачу и результат получится размерности NxN:

                ‘mean’: current_x.mean(axis=0),

                ‘cov’: np.cov(current_x.T) + np.eye(D)*smoothing,

Маленькая детать: Numpy использует не сглаженную версию ковариации и делит на N-1, а не на N.

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

        for c, g in self.gaussians.iteritems():

            mean, cov = g[‘mean’], g[‘cov’]

            P[:,c] = mvn.logpdf(X, mean=mean, cov=cov) + np.log(self.priors)

        return np.argmax(P, axis=1)

Запустим и посмотрим, насколько улучшился результат.

Линейный (LDA) и квадратичный (QDA) дискриминантный анализ

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

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

Назовём наши два класса классом 0 и классом 1. Напомню, что правило для решения, что данные относятся к классу 1, состоит в том, что вероятность их принадлежности к классу 1 выше, чем вероятность их принадлежности к классу 0:

Напомню также, что мы можем переписать это неравенство, используя теорему Байеса:

Напомню также, что мы можем переписать это неравенство, используя теорему Байеса:

Мы можем сократить p(X), поскольку эта величина встречается в обоих частях неравенства, получим:

Если данное утверждение истинно, то наш прогноз – класс 1, в противном случае – класс 0.

Идя далее, включим наши выражения для каждого распределения вероятностей:

Обозначим вероятность класса 1 через α, а вероятность класса 0 – через (1 – α), тогда два вероятностных распределения будут гауссианами с параметрами μ1, Σ1 и μ0, Σ0:

Следующее – взять логарифмы обеих частей неравенства. Почему знак «больше» остаётся при этом верным? Как вы могли слышать от меня ранее, тут всё нормально, поскольку логарифмическая функция является монотонно возрастающей. Поскольку я не хочу перегружать этот курс математикой, объясню понятнее. Возьмём два числа, например, 2 > 1. Теперь возьмём логарифм обоих частей этого неравенства. Получим, что соотношение осталось неизменным: по-прежнему 0,693 > 0. Проверьте это на любой другой паре чисел, и вы увидите, что соотношение не меняется – число слева всё равно больше числа справа.

И это замечательно, поскольку позволяет нам избавиться от экспоненты. Обозначив, кроме того, логарифм коэффициентов гауссовых распределений через K1 и Ko, получим:

Как видите, всё становится гораздо проще.

Затем мы можем перенести всё в левую часть, так что правая часть будет просто нулём:

Далее раскроем скобки при умножении:

Тут мы можем провернуть один фокус путём приведения подобных слагаемых μ1TΣ1-1x и xTΣ1-1μ1, поскольку

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

Далее мы можем упростить выражение, использовав вышеописанное правило и раскрыв скобки:

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

Далее мы можем упростить выражение, использовав вышеописанное правило и раскрыв скобки:

И наконец, мы можем сгруппировать члены:

Как видим, выражение состоит из трёх частей. Первая – где x появляется дважды – называется квадратичным членом. Далее часть, где x появляется однажды, – это так называемый линейный член. Третья часть – где x не появляется вовсе – называется постоянным членом.

Итак, в результате мы пришли к многомерному квадратному уравнению. Это и есть наше правило прогнозирования: мы подставляем x в данное уравнение, и если оно больше нуля, то выбирается класс 1; если же оно оказывается меньше нуля, то выбирается класс 0. Поскольку это квадратное уравнение, то всё это называется квадратичным дискриминантным анализом.

Самое лучшее здесь – реализация. В обычном байесовском классификаторе мы были вынуждены вычислять плотность распределения вероятностей, применяя соответствующую функцию библиотеки, что требовало использования определителя матрицы, нахождения обратной матрицы и так далее. В данном же случае можно просто определить параметры через μ0, Σ0, μ1, Σ1 и α, после чего уже к ним не возвращаться. Можно заняться квадратным уравнением напрямую, что, разумеется, гораздо быстрее с точки зрения вычислений:

Разумеется, A, w и B определяются следующим образом:

Разумеется, A, w и B определяются следующим образом:

Как только мы это сделаем, нам больше не придётся находить никаких обратных матриц для последующих прогнозов.

Обратите внимание, что будет, если Σ1 = Σ0. Это значит, что оба класса имеют одинаковую ковариацию, квадратичный член исчезает, а остаются лишь линейный и постоянный члены. Это называется линейным дискриминантным анализом, или LDA.

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

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

В заключение мы подробнее поговорим о генеративных и дискриминативных классификаторах.

Обратите внимание, что во всех классификаторах, работа которых основана на вероятностях, прогноз делался из апостериорной вероятности p(C|X). Классификаторы, моделирующие такое распределение напрямую, такие как логистическая регрессия, называются дискриминативными классификаторами. Это связано с тем обстоятельством, что, учитывая входные данные, они пытаются научиться различать два класса. Если вы изучали мой курс по логистической регрессии, то видели, что мы использовали гиперплоскость для нахождения различия между классами: всё, что по одну сторону от гиперплоскости, – синее, всё, что по другую сторону, – красное. Классификаторы вроде метода k-ближайших соседей также относятся к дискриминативным, поскольку они «учатся» напрямую различать классы, учитывая входные данные.

Генеративные классификаторы работают на противоположном принципе. Они всё так же позволяют различать классы, используя теорему Байеса, но главным в их работе является вычисление p(X|C). При этом предполагается, что каждый класс обладает своей структурой и, следовательно, своим распределением X. Другими словами, каждый класс представляет из себя нечто вроде «машины по производству данных», причём каждая такая «машина» производит данные по-своему. Поскольку эти «машины» производят (генерируют) данные, то отсюда и название – генеративные классификаторы.

Генеративные модели вполне удовлетворительны с теоретической точки зрения, поскольку они основаны на законах вероятностей. Каждая переменная моделируется напрямую, и мы можем изменить свою модель p(X|C), если она неверна или выдаёт недостаточно хорошие результаты. Преимуществом такого подхода является то, что мы точно знаем, как каждая переменная влияет на результат, что бывает весьма полезно, когда при работе с клиентами они просят объяснить модель с точки зрения входных переменных.

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

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Комментариев: 2
  1. Николай

    Хорошие материалы, но теория дается не очень связанными кусками и много опечаток (текст похож на машинный перевод). В итоге, разобраться сложно, что же имеется в виду. Например, “не сглаженную версию ковариации” имеется в виду “несмещенную оценку ковариации”.

    1. adminCraft

      Добрый день, Николай.

      Большое спасибо за замечание – мы обязательно исправим эти ошибки чтобы ещё улучшить уроки курса.

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: