.. _sec_naive_bayes: Наивный байесовский классификатор ================================= В предыдущих разделах мы изучили теорию вероятностей и случайные величины. Чтобы применить эту теорию на практике, введём классификатор наивного Байеса. Он использует лишь базовые вероятностные принципы, позволяющие нам выполнять классификацию цифр. Обучение — это по сути процесс принятия допущений. Чтобы классифицировать новый пример данных, который мы ранее не встречали, нам необходимо выдвинуть предположения о том, какие примеры данных похожи друг на друга. Наивный байесовский классификатор — популярный и удивительно понятный алгоритм — предполагает, что все признаки независимы друг от друга, чтобы упростить вычисления. В этом разделе мы применим эту модель для распознавания символов на изображениях. .. raw:: latex \diilbookstyleinputcell .. code:: python %matplotlib inline import math import torch import torchvision from d2l import torch as d2l d2l.use_svg_display() Распознавание оптических символов --------------------------------- MNIST :cite:`LeCun.Bottou.Bengio.ea.1998` — один из наиболее часто используемых наборов данных. Он содержит 60 000 изображений для обучения и 10 000 изображений для проверки. Каждое изображение содержит рукописную цифру от 0 до 9. Задача заключается в классификации каждого изображения на соответствующую цифру. Gluon предоставляет класс ``MNIST`` в модуле ``data.vision`` для автоматической загрузки набора данных из Интернета. В дальнейшем Gluon будет использовать уже загруженную локальную копию. Мы указываем, запрашиваем ли мы обучающую выборку или тестовую выборку, устанавливая значение параметра ``train`` в ``True`` или ``False`` соответственно. Каждое изображение является черно-белым, его ширина и высота равны :math:`28`, а форма — (:math:`28`,\ :math:`28`,\ :math:`1`). Мы используем пользовательское преобразование для удаления последнего измерения канала. Кроме того, набор данных представляет каждый пиксель в виде беззнакового целого числа :math:`8`-битной разрядности. Мы квантуем их в бинарные признаки, чтобы упростить задачу. .. raw:: latex \diilbookstyleinputcell .. code:: python data_transform = torchvision.transforms.Compose([ torchvision.transforms.ToTensor(), lambda x: torch.floor(x * 255 / 128).squeeze(dim=0) ]) mnist_train = torchvision.datasets.MNIST( root='./temp', train=True, transform=data_transform, download=True) mnist_test = torchvision.datasets.MNIST( root='./temp', train=False, transform=data_transform, download=True) Мы можем получить доступ к конкретному примеру, который содержит изображение и соответствующую метку. .. raw:: latex \diilbookstyleinputcell .. code:: python image, label = mnist_train[2] image.shape, label Наш пример, сохранённый в переменной ``image``, соответствует изображению высотой и шириной :math:`28` пикселей. .. raw:: latex \diilbookstyleinputcell .. code:: python image.shape, image.dtype Наш код хранит метку каждого изображения в виде скаляра. Его тип — целое число :math:`32`-битной разрядности. .. raw:: latex \diilbookstyleinputcell .. code:: python label, type(label) Мы также можем одновременно обрабатывать несколько примеров. .. raw:: latex \diilbookstyleinputcell .. code:: python images = torch.stack([mnist_train[i][0] for i in range(10, 38)], dim=0) labels = torch.tensor([mnist_train[i][1] for i in range(10, 38)]) images.shape, labels.shape Давайте визуализируем эти примеры. .. raw:: latex \diilbookstyleinputcell .. code:: python d2l.show_images(images, 2, 9); Вероятностная модель для классификации -------------------------------------- В задаче классификации мы сопоставляем пример категории. В данном случае примером является полутоновое :math:`28\times 28` изображение, а категорией — цифра. (Более подробное объяснение см. в :numref:`sec_softmax`.) Одним из естественных способов формулировки задачи классификации является вероятностный вопрос: какова наиболее вероятная метка при заданных признаках (то есть пикселях изображения)? Обозначим через :math:`\mathbf x\in\mathbb R^d` признаки примера, а через :math:`y\in\mathbb R` — метку. В нашем случае признаками выступают пиксели изображения; мы можем преобразовать изображение размерности :math:`2` в вектор так, чтобы выполнялось условие :math:`d=28^2=784`, а метками являются цифры. Вероятность метки при заданных признаках равна :math:`p(y \mid \mathbf{x})`. Если мы способны вычислить эти вероятности, которые в нашем примере соответствуют :math:`p(y \mid \mathbf{x})` для :math:`y=0, \ldots,9`, то классификатор выдаст предсказание :math:`\hat{y}`, определяемое следующим выражением: .. math:: \hat{y} = \mathrm{argmax} \> p(y \mid \mathbf{x}). К сожалению, это требует оценки :math:`p(y \mid \mathbf{x})` для каждого значения :math:`\mathbf{x} = x_1, ..., x_d`. Предположим, что каждый признак может принимать одно из :math:`2` значений. Например, признак :math:`x_1 = 1` может означать, что слово apple встречается в данном документе, а :math:`x_1 = 0` — что оно не встречается. Если бы у нас было :math:`30` таких бинарных признаков, это означало бы, что нам нужно быть готовыми классифицировать любое из :math:`2^{30}` (более 1 миллиарда!) возможных значений входного вектора :math:`\mathbf{x}`. Более того, где здесь обучение? Если нам нужно видеть каждый возможный пример, чтобы предсказать соответствующую метку, то мы не столько учимся распознавать закономерности, сколько запоминаем набор данных. Наивный байесовский классификатор --------------------------------- К счастью, вводя некоторые предположения о условной независимости, мы можем добавить индуктивное смещение и построить модель, способную обобщать на основе сравнительно небольшого набора обучающих примеров. Для начала воспользуемся теоремой Байеса, чтобы выразить классификатор в виде .. math:: \hat{y} = \mathrm{argmax}_y \> p(y \mid \mathbf{x}) = \mathrm{argmax}_y \> \frac{p( \mathbf{x} \mid y) p(y)}{p(\mathbf{x})}. Обратите внимание, что знаменатель является нормирующим членом :math:`p(\mathbf{x})`, который не зависит от значения метки :math:`y`. Следовательно, нам достаточно сравнивать числитель при различных значениях :math:`y`. Даже если бы вычисление знаменателя оказалось неразрешимой задачей, мы могли бы обойтись без него, при условии, что числитель можно вычислить. К счастью, даже если бы мы захотели восстановить нормирующую константу, мы бы смогли это сделать. Мы всегда можем восстановить нормирующий член, поскольку :math:`\sum_y p(y \mid \mathbf{x}) = 1`. Теперь сосредоточимся на :math:`p( \mathbf{x} \mid y)`. Используя цепное правило вероятности, мы можем выразить величину :math:`p( \mathbf{x} \mid y)` как .. math:: p(x_1 \mid y) \cdot p(x_2 \mid x_1, y) \cdot ... \cdot p( x_d \mid x_1, ..., x_{d-1}, y). Само по себе это выражение не позволяет нам продвинуться дальше. Нам по-прежнему необходимо оценить примерно :math:`2^d` параметров. Однако, если мы предположим, что *признаки условно независимы друг от друга при заданной метке*, то ситуация значительно улучшается, так как этот член упрощается до :math:`\prod_i p(x_i \mid y)`, что дает нам предсказатель .. math:: \hat{y} = \mathrm{argmax}_y \> \prod_{i=1}^d p(x_i \mid y) p(y). If we can estimate :math:`p(x_i=1 \mid y)` for every :math:`i` and :math:`y`, and save its value in :math:`P_{xy}[i, y]`, here :math:`P_{xy}` is a :math:`d\times n` matrix with :math:`n` being the number of classes and :math:`y\in\{1, \ldots, n\}`, then we can also use this to estimate :math:`p(x_i = 0 \mid y)`, i.e., .. math:: p(x_i = t_i \mid y) = \begin{cases} P_{xy}[i, y] & \textrm{for } t_i=1 ;\\ 1 - P_{xy}[i, y] & \textrm{for } t_i = 0 . \end{cases} Кроме того, мы оцениваем :math:`p(y)` для каждого :math:`y` и сохраняем его в :math:`P_y[y]`, где :math:`P_y` — это вектор длины :math:`n`. Затем для любого нового примера :math:`\mathbf t = (t_1, t_2, \ldots, t_d)` мы можем вычислить .. math:: \begin{aligned}\hat{y} &= \mathrm{argmax}_ y \ p(y)\prod_{i=1}^d p(x_t = t_i \mid y) \\ &= \mathrm{argmax}_y \ P_y[y]\prod_{i=1}^d \ P_{xy}[i, y]^{t_i}\, \left(1 - P_{xy}[i, y]\right)^{1-t_i}\end{aligned} :label: eq_naive_bayes_estimation для любого :math:`y`. Таким образом, наше предположение о условной независимости снизило сложность нашей модели с экспоненциальной зависимости от числа признаков :math:`\mathcal{O}(2^dn)` до линейной, что :math:`\mathcal{O}(dn)`. Обучение -------- Проблема заключается в том, что мы не знаем :math:`P_{xy}` и :math:`P_y`. Поэтому нам необходимо сначала оценить их значения, используя имеющиеся обучающие данные. Это и есть *обучение* модели. Оценка :math:`P_y` не представляет особой сложности. Поскольку мы имеем дело только с :math:`10` классами, мы можем подсчитать количество вхождений :math:`n_y` для каждой из цифр и разделить это число на общий объём данных :math:`n`. Например, если цифра 8 встречается :math:`n_8 = 5,800` раз, а общее количество изображений равно :math:`n = 60,000`, то оценка вероятности составит :math:`p(y=8) = 0.0967`. .. raw:: latex \diilbookstyleinputcell .. code:: python X = torch.stack([mnist_train[i][0] for i in range(len(mnist_train))], dim=0) Y = torch.tensor([mnist_train[i][1] for i in range(len(mnist_train))]) n_y = torch.zeros(10) for y in range(10): n_y[y] = (Y == y).sum() P_y = n_y / n_y.sum() P_y Теперь перейдем к чуть более сложным вещам :math:`P_{xy}`. Поскольку мы выбрали черно-белые изображения, :math:`p(x_i \mid y)` обозначает вероятность того, что пиксель :math:`i` будет активен для класса :math:`y`. Как и раньше, мы можем подсчитать количество раз :math:`n_{iy}`, когда происходит событие, и разделить его на общее число случаев :math:`y`, то есть :math:`n_y`. Однако есть одна небольшая проблема: некоторые пиксели могут никогда не быть черными (например, в хорошо обрезанных изображениях угловые пиксели всегда могут быть белыми). Удобный способ для статистиков решить эту проблему — добавить псевдосчетчики ко всем наблюдениям. Таким образом, вместо :math:`n_{iy}` мы используем :math:`n_{iy}+1`, а вместо :math:`n_y` — :math:`n_{y}+2` (поскольку пиксель :math:`i` может принимать только два возможных значения — он может быть либо черным, либо белым). Этот метод также называется *сглаживанием Лапласа*. Он может показаться произвольным, однако его можно обосновать с байесовской точки зрения, используя модель бета-биномиального распределения. .. raw:: latex \diilbookstyleinputcell .. code:: python n_x = torch.zeros((10, 28, 28)) for y in range(10): n_x[y] = torch.tensor(X.numpy()[Y.numpy() == y].sum(axis=0)) P_xy = (n_x + 1) / (n_y + 2).reshape(10, 1, 1) d2l.show_images(P_xy, 2, 5); Визуализируя эти :math:`10\times 28\times 28` вероятности (для каждого пикселя и каждого класса), мы можем получить усреднённые изображения цифр. Теперь мы можем использовать :eq:`eq_naive_bayes_estimation` для предсказания нового изображения. При заданном :math:`\mathbf x` следующая функция вычисляет :math:`p(\mathbf x \mid y)p(y)` для каждого :math:`y`. .. raw:: latex \diilbookstyleinputcell .. code:: python def bayes_pred(x): x = x.unsqueeze(0) # (28, 28) -> (1, 28, 28) p_xy = P_xy * x + (1 - P_xy)*(1 - x) p_xy = p_xy.reshape(10, -1).prod(dim=1) # p(x|y) return p_xy * P_y image, label = mnist_test[0] bayes_pred(image) Это пошло ужасно не так! Чтобы понять почему, давайте посмотрим на вероятности для каждого пикселя. Обычно это числа между :math:`0.001` и :math:`1`. Мы перемножаем :math:`784` таких чисел. В этот момент стоит упомянуть, что мы вычисляем эти значения на компьютере, а значит, с ограниченным диапазоном для экспоненты. Что происходит, так это то, что мы сталкиваемся с *числовой недодетекцией*, то есть перемножение всех этих малых чисел приводит к ещё меньшим значениям, пока они не округлятся до нуля. Мы обсуждали это как теоретическую проблему в :numref:`sec_maximum_likelihood`, но здесь мы ясно видим это явление на практике. Как обсуждалось в том разделе, мы решаем эту проблему, используя тот факт, что :math:`\log a b = \log a + \log b`, то есть переходим к суммированию логарифмов. Даже если оба значения :math:`a` и :math:`b` малы, значения логарифмов должны находиться в корректном диапазоне. .. raw:: latex \diilbookstyleinputcell .. code:: python a = 0.1 print('underflow:', a**784) print('logarithm is normal:', 784*math.log(a)) Поскольку логарифм — возрастающая функция, мы можем переписать :eq:`eq_naive_bayes_estimation` в виде .. math:: \hat{y} = \mathrm{argmax}_y \ \log P_y[y] + \sum_{i=1}^d \Big[t_i\log P_{xy}[x_i, y] + (1-t_i) \log (1 - P_{xy}[x_i, y]) \Big]. Мы можем реализовать следующую стабильную версию: .. raw:: latex \diilbookstyleinputcell .. code:: python log_P_xy = torch.log(P_xy) log_P_xy_neg = torch.log(1 - P_xy) log_P_y = torch.log(P_y) def bayes_pred_stable(x): x = x.unsqueeze(0) # (28, 28) -> (1, 28, 28) p_xy = log_P_xy * x + log_P_xy_neg * (1 - x) p_xy = p_xy.reshape(10, -1).sum(axis=1) # p(x|y) return p_xy + log_P_y py = bayes_pred_stable(image) py Теперь мы можем проверить, верно ли предсказание. .. raw:: latex \diilbookstyleinputcell .. code:: python py.argmax(dim=0) == label Если теперь предсказать несколько примеров из проверочной выборки, можно увидеть, что байесовский классификатор работает довольно хорошо. .. raw:: latex \diilbookstyleinputcell .. code:: python def predict(X): return [bayes_pred_stable(x).argmax(dim=0).type(torch.int32).item() for x in X] X = torch.stack([mnist_test[i][0] for i in range(18)], dim=0) y = torch.tensor([mnist_test[i][1] for i in range(18)]) preds = predict(X) d2l.show_images(X, 2, 9, titles=[str(d) for d in preds]); Наконец, вычислим общую точность классификатора. .. raw:: latex \diilbookstyleinputcell .. code:: python X = torch.stack([mnist_test[i][0] for i in range(len(mnist_test))], dim=0) y = torch.tensor([mnist_test[i][1] for i in range(len(mnist_test))]) preds = torch.tensor(predict(X), dtype=torch.int32) float((preds == y).sum()) / len(y) # Validation accuracy Современные глубокие сети достигают уровня ошибок менее :math:`0.01`. Относительно низкая производительность обусловлена неверными статистическими предположениями, заложенными в модель: мы предположили, что каждый пиксель генерируется *независимо* от других, завися только от метки. Это явно не соответствует тому, как люди пишут цифры, и это ошибочное предположение привело к провалу нашего чрезмерно наивного (байесовского) классификатора. Итог ---- - Используя правило Байеса, классификатор можно построить, предполагая, что все наблюдаемые признаки независимы. - Этот классификатор можно обучить на наборе данных, подсчитывая количество вхождений комбинаций меток и значений пикселей. - Этот классификатор на протяжении десятилетий был золотым стандартом для таких задач, как обнаружение спама. Упражнения ---------- 1. Рассмотрим набор данных :math:`[[0,0], [0,1], [1,0], [1,1]]`, метки которого определяются как исключающее ИЛИ (XOR) двух элементов :math:`[0,1,1,0]`. Каковы вероятности для наивного байесовского классификатора, обученного на этом наборе данных? Успешно ли он классифицирует эти точки? Если нет, какие допущения нарушены? 2. Предположим, что мы не использовали сглаживание Лапласа при оценке вероятностей, и во время тестирования поступил пример, содержащий значение, которое никогда не встречалось в обучающих данных. Что выведет модель? 3. Наивный байесовский классификатор является конкретным примером байесовской сети, в которой зависимости случайных величин закодированы с помощью графовой структуры. Хотя полная теория выходит за рамки данного раздела (полные детали см. в :cite:t:`Koller.Friedman.2009`), объясните, почему явное разрешение зависимости между двумя входными переменными в модели XOR позволяет создать успешный классификатор. `Обсуждения `__