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

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

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

В этой статье мы обсудим известнейший наивный байесовский классификатор. Он куда более опирается на вероятности, нежели метод k-ближайших соседей, и может оказаться весьма мощным инструментом.

Впрочем, мы намеренно сделаем классификатор не столь мощным – отсюда и название «наивный».

Вначале обсудим наивную байесовскую модель на примере.

Предположим, мы хотим спрогнозировать, является ли пришедшее электронное письмо спамом, исходя из встречающихся в письме слов. Общее количество возможных слов в языке колоссально, поэтому предположим, что мы рассматриваем конкретно слова «бесплатно», «препарат» и «деньги». Вначале рассмотрим слово «деньги». Идея в том, чтобы смоделировать вероятности p(«деньги»|спам) и p(«деньги»|не спам). Как же нам вычислить эти вероятности?

Хороший вопрос.

Дискретный вероятности, подобные этой, сводятся к подсчёту и легко вычисляются (по крайней мере, я на это надеюсь). К примеру, вероятность p(«деньги»|спам) равна числу спамовых сообщений, содержащих слово «деньги», делённому на число всех спамовых сообщений. То же самое относится к вероятности p(«деньги»|не спам).

Итак, почему же наивный байесовский классификатор называют наивным? Рассмотрим вероятность p(«наличность»|спам). Коррелирует ли она с вероятностью p(«деньги»|спам) или от неё независима? Ответ: вероятно, очень коррелирует. Но наивный байесовский классификатор делает предположение, что ни один из входных признаков не коррелирует друг с другом и все они независимы.

Следующий вопрос: почему наивный байесовский классификатор является байесовским? Задумаемся, что нам действительно нужно? Нам же не нужно моделировать вероятности. Нам нужно сделать прогноз, в частности, узнать вероятность спама с учётом входящих в документ слов. Обратите внимание, что это ровно противоположно тому, что мы только что рассматривали, то есть p(слова|спам). И это замечательно, потому что в связи с этим мы можем использовать теорему Байеса. Следовательно,

При этом мы решаем, спам перед нами или нет, сравнивая вероятности p(спам|слова) и p(не спам|слова). Другими словами, мы берём argmax этих двух вероятностей. Обратите внимание, что вероятность p(слова) не зависит от того, спам это или нет, а это значит, что мы можем удалить её из уравнения и рассматривать только числитель. Другими словами, нам нужно найти

где C в данном случае равен спаму или не спаму.

p(C) называется априорной вероятностью и, вновь-таки, её можно найти путём подсчёта. К примеру, если в нашем наборе данных есть 10 электронных писем со спамом и 20 без спама, то p(спам) равно 1/3, а p(не спам) равно 2/3. p(X|C) называется правдоподобностью, а p(C|X) называется апостериорной вероятностью.

Итак, как же смоделировать p(X|C)? Не забывайте, что наивный байесовский классификатор – это когда все слова данного класса являются независимыми. Когда же у нас есть независимые вероятности, это значит, что мы можем просто перемножить все индивидуальные вероятности между собой для получения совместной вероятности. Таким образом, p(слова|C) равно p(«деньги»|C), умноженному на p(«наличность»|C) и так далее. Это же мы можем записать в виде произведения:

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

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

В нашем коде мы вновь обратимся к базе данных MNIST. Интересно, что нам не нужно обрабатывать каждый отдельный пиксель как дискретное распределение по 256 различным значениям. На самом деле нам, вероятно, лучше рассматривать их как непрерывное распределение, поскольку и в физической реальности мы воспринимаем интенсивность света как непрерывную величину. Вопрос только в том, какое непрерывное распределение использовать? Мы могли бы применить распределение, определённое в промежутке от 0 до 1, но вместо этого используем гауссово распределение. Любой, кто изучал курс теории вероятностей, должен быть с ним знаком:

где μ – среднее значение, а σ2 – дисперсия.

Напомню, что существует также и многомерное гауссово распределение, где x и μ являются векторами, а вместо скалярной дисперсии используется ковариационная матрица:

где μ – среднее значение, а σ2 – дисперсия.

Напомню, что существует также и многомерное гауссово распределение, где x и μ являются векторами, а вместо скалярной дисперсии используется ковариационная матрица:

Это позволит нам использовать функцию библиотеки Scipy, которая позволяет одновременно вычислять эту величину для нескольких входных векторов. Это куда лучше, чем вычисления вручную, поскольку библиотека Scipy оптимизирована для быстрого выполнения таких вычислений, а как вы знаете, их реализация в «чистом» Python будет очень медленной.

Мы и далее оптимизируем наш код. Во-первых, в действительности нам не нужна полная ковариационная матрица, поскольку все размерности будут считаться независимыми, несмотря на то, что, очевидно, это не так. С точки зрения многомерного гауссового распределения это значит, что все внедиагональные элементы ковариационной матрицы равны нулю. А это означает, что вместо ковариационной матрицы размерностью DxD нам нужны лишь D различных дисперсий единичной размерности. Это называется эллиптической ковариацией с привязкой по осям координат и значительно ускоряет вычисления, поскольку нам не требуется находить матрицу, обратную ковариационной. Напомню, чтобы найти матрицу, обратную диагональной, нам требуется лишь поделить единицу на все её отдельные значения. К счастью, функция библиотеки Scipy позволяет нам вставить в ковариационную матрицу размерности DxD вектор размерности D.

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

И последнее улучшение, о котором необходимо упомянуть, прежде чем переходить к коду, – это сглаживание. Иногда при попытке найти матрицу, обратную ковариационной, мы сталкиваемся с так называемой проблемой вырожденной ковариации. Это матричный эквивалент деления на нуль. Чтобы этого не происходило, мы добавляем единичную матрицу, умноженную на некое малое число вроде 10-3, к первоначальной ковариационной матрице. Это добавляет числовую стабильность нашему алгоритму.

Это вся необходимая теория, чтобы знать, как реализовать данный алгоритм. Рассмотрим теперь псевдокод. В функции fit нам нужно вычислить среднее значение и ковариацию для каждого класса. Среднее значение и ковариация – это всё, что нужно, чтобы полностью представить гауссово распределение – то, что называется «достаточной статистикой». Не забывайте, что здесь нам нужно вычислить и априорные вероятности:

    def fit(X, Y):

        dict_of_gaussians = {}

        priors = {}

        for c in classes:

            Xc = X[corresponding Y == c]

            mu, var = среднее и диагональная ковариация Xc

            dict_of_gaussians = { ‘mu’: mu, ‘var’: var }

            priors = len(Xc) / len(X)

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

    def predict(X):

        predictions = [], max_posterior = -inf, best_class = None

        for x in X:

            for c in classes:

                mu, var = dict_of_gaussians

                posterior = log_pdf(x, mu, var) + log(priors)

                if posterior > max_posterior

                max_posterior = posterior

                best_class = c

            predictions.append(best_class)

        return predictions

Наивный байесовский классификатор. Вручную выполненный пример

Сейчас мы вручную выполним пример наивного байесовского алгоритма, вновь-таки воспользовавшись случаем с определителем спама. Чтобы быть в состоянии уместить данные на слайде, мы рассмотрим лишь три слова: «деньги», «бесплатно» и «препараты».

Итак, у нас есть набор данных, показывающих, появляется ли в сообщениях каждое из этих слов и является ли каждый из случаев спамом (см. слайд). Но перед тем как перейти к следующему слайду, я прошу вас самостоятельно рассчитать все необходимые вероятности. Вы должны знать, какие нам нужны вероятности, чтобы вычислить апостериорную вероятность p(C|X). Не забывайте, что нам не нужна вероятность p(X), поскольку она убирается из всех выражений, а нужным является лишь значение функции argmax.

Итак, нам необходимы следующие вероятности: p(деньги|спам), p(не деньги|спам), p(деньги|не спам), p(не деньги|не спам); то же самое касается слов «бесплатно» и «препараты». Они равны 3/5, 2/5 и так далее. Поставьте видео на паузу и удостоверьтесь, что ваш ответ верен.

Рассмотрим теперь пример вычислений для классификации спамового сообщения. Предположим, электронное письмо содержит слово «деньги», но не содержит слов «бесплатно» и «препараты». Является ли оно спамом? Для этого нам надо вычислить вероятности p(спам|деньги, не бесплатно, не препараты) и p(не спам|деньги, не бесплатно, не препараты). Вначале попробуйте посчитать самостоятельно и сравните с правильным ответом на следующем слайде.

Обе эти вероятности можно рассчитывать по отдельности, поскольку они независимы. Итак, p(спам|деньги, не бесплатно, не препараты) = 0,012, а p(не спам|деньги, не бесплатно, не препараты) = 0,16. Обратите внимание, что здесь мы не делили на p(X), поэтому это не истинные вероятности. Как видим, апостериорная вероятность того, что это не спам, выше, а значит, мы классифицируем это как не спам.

Обратите внимание, что вероятности, в точности равные нулю, могут стать проблемой, поскольку всё, что будет на них умножаться, также даст лишь нуль. В итоге может получиться лишь ряд нулей. Как с этим справиться? Иногда можно воспользоваться так называемым приплюсовывающим сглаживанием, также именуемым лапласовым, когда вместо чистого подсчёта мы добавляем единицу в числителе и V в знаменателе:

где V – размер словаря Xi или, другими словами, все возможные значения Xi. Это гарантирует корректность вероятности, поскольку их сумма всегда равна 1.

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

Итак, начнём с импортов. Импортируем библиотеку Numpy, с файла util.py импортируем функцию get_data, уже знакомую вам по методу k-ближайших соседей, а также функцию datetime из одноименной библиотеки, чтобы иметь возможность фиксировать затраченное время. Вы также можете попробовать (что я настоятельно рекумендую) функцию norm из библиотеки Scipy.stats, которая применяется для одномерных гауссовых распределений, чтобы сравнить скорость работы. Или же можно воспользоваться функцией multivariate_normal.

import numpy as np

from util import get_data

from datetime import datetime

from scipy.stats import norm

from scipy.stats import multivariate_normal as mvn

Создадим класс NaiveBayes и начнём с функции fit, установив значение сглаживания по умолчанию 10-3:

class NaiveBayes(object):

    def fit(self, X, Y, smoothing=1e-2):

        self.gaussians = dict()

        self.priors = dict()

        labels = set(Y)

        for c in labels:

            current_x = X[Y == c]

            self.gaussians = {

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

                ‘var’: current_x.var(axis=0) + smoothing,

            }

            self.priors = float(len(Y[Y == c])) / len(Y)

Следующее – функция score. Она использует ещё не написанную функцию predict и выглядит в точности так же, как и в случае метода k-ближайших соседей.

    def score(self, X, Y):

        P = self.predict(X)

        return np.mean(P == Y)

Далее функция predict:

    def predict(self, X):

        N, D = X.shape

        K = len(self.gaussians)

        P = np.zeros((N, K))

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

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

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

        return np.argmax(P, axis=1)

Переходим к функции main. Используем 10000 примеров, что значительно больше, чем в методе k-ближайших соседей. Как видите, наивный байесовский классификатор может обработать значительно больше данных, чем метод k-ближайших соседей. В качестве учебного набора используем половину от всех данных.

if __name__ == ‘__main__’:

    X, Y = get_data(10000)

    Ntrain = len(Y) / 2

    Xtrain, Ytrain = X[:Ntrain], Y[:Ntrain]

    Xtest, Ytest = X[Ntrain:], Y[Ntrain:]

    model = NaiveBayes()

    t0 = datetime.now()

    model.fit(Xtrain, Ytrain)

    print “Training time:”, (datetime.now() – t0)

    t0 = datetime.now()

    print “Train accuracy:”, model.score(Xtrain, Ytrain)

    print “Time to compute train accuracy:”, (datetime.now() – t0), “Train size:”, len(Ytrain)

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

    t0 = datetime.now()

    print “Test accuracy:”, model.score(Xtest, Ytest)

    print “Time to compute test accuracy:”, (datetime.now() – t0), “Test size:”, len(Ytest)

Посмотрим, что получилось.

где V – размер словаря Xi или, другими словами, все возможные значения Xi. Это гарантирует корректность вероятности, поскольку их сумма всегда равна 1.

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

Итак, начнём с импортов. Импортируем библиотеку Numpy, с файла util.py импортируем функцию get_data, уже знакомую вам по методу k-ближайших соседей, а также функцию datetime из одноименной библиотеки, чтобы иметь возможность фиксировать затраченное время. Вы также можете попробовать (что я настоятельно рекумендую) функцию norm из библиотеки Scipy.stats, которая применяется для одномерных гауссовых распределений, чтобы сравнить скорость работы. Или же можно воспользоваться функцией multivariate_normal.

import numpy as np

from util import get_data

from datetime import datetime

from scipy.stats import norm

from scipy.stats import multivariate_normal as mvn

Создадим класс NaiveBayes и начнём с функции fit, установив значение сглаживания по умолчанию 10-3:

class NaiveBayes(object):

    def fit(self, X, Y, smoothing=1e-2):

        self.gaussians = dict()

        self.priors = dict()

        labels = set(Y)

        for c in labels:

            current_x = X[Y == c]

            self.gaussians = {

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

                ‘var’: current_x.var(axis=0) + smoothing,

            }

            self.priors = float(len(Y[Y == c])) / len(Y)

Следующее – функция score. Она использует ещё не написанную функцию predict и выглядит в точности так же, как и в случае метода k-ближайших соседей.

    def score(self, X, Y):

        P = self.predict(X)

        return np.mean(P == Y)

Далее функция predict:

    def predict(self, X):

        N, D = X.shape

        K = len(self.gaussians)

        P = np.zeros((N, K))

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

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

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

        return np.argmax(P, axis=1)

Переходим к функции main. Используем 10000 примеров, что значительно больше, чем в методе k-ближайших соседей. Как видите, наивный байесовский классификатор может обработать значительно больше данных, чем метод k-ближайших соседей. В качестве учебного набора используем половину от всех данных.

if __name__ == ‘__main__’:

    X, Y = get_data(10000)

    Ntrain = len(Y) / 2

    Xtrain, Ytrain = X[:Ntrain], Y[:Ntrain]

    Xtest, Ytest = X[Ntrain:], Y[Ntrain:]

    model = NaiveBayes()

    t0 = datetime.now()

    model.fit(Xtrain, Ytrain)

    print “Training time:”, (datetime.now() – t0)

    t0 = datetime.now()

    print “Train accuracy:”, model.score(Xtrain, Ytrain)

    print “Time to compute train accuracy:”, (datetime.now() – t0), “Train size:”, len(Ytrain)

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

    t0 = datetime.now()

    print “Test accuracy:”, model.score(Xtest, Ytest)

    print “Time to compute test accuracy:”, (datetime.now() – t0), “Test size:”, len(Ytest)

Посмотрим, что получилось.

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

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