22.9. Наивный байесовский классификатор¶
В предыдущих разделах мы изучили теорию вероятностей и случайные величины. Чтобы применить эту теорию на практике, введём классификатор наивного Байеса. Он использует лишь базовые вероятностные принципы, позволяющие нам выполнять классификацию цифр.
Обучение — это по сути процесс принятия допущений. Чтобы классифицировать новый пример данных, который мы ранее не встречали, нам необходимо выдвинуть предположения о том, какие примеры данных похожи друг на друга. Наивный байесовский классификатор — популярный и удивительно понятный алгоритм — предполагает, что все признаки независимы друг от друга, чтобы упростить вычисления. В этом разделе мы применим эту модель для распознавания символов на изображениях.
%matplotlib inline
import math
import torch
import torchvision
from d2l import torch as d2l
d2l.use_svg_display()
22.9.1. Распознавание оптических символов¶
MNIST (LeCun et al., 1998) — один из наиболее часто используемых наборов данных. Он содержит 60 000 изображений для обучения и 10 000 изображений для проверки. Каждое изображение содержит рукописную цифру от 0 до 9. Задача заключается в классификации каждого изображения на соответствующую цифру.
Gluon предоставляет класс MNIST в модуле data.vision для
автоматической загрузки набора данных из Интернета. В дальнейшем Gluon
будет использовать уже загруженную локальную копию. Мы указываем,
запрашиваем ли мы обучающую выборку или тестовую выборку, устанавливая
значение параметра train в True или False соответственно.
Каждое изображение является черно-белым, его ширина и высота равны
\(28\), а форма — (\(28\),\(28\),\(1\)). Мы
используем пользовательское преобразование для удаления последнего
измерения канала. Кроме того, набор данных представляет каждый пиксель в
виде беззнакового целого числа \(8\)-битной разрядности. Мы квантуем
их в бинарные признаки, чтобы упростить задачу.
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)
Мы можем получить доступ к конкретному примеру, который содержит изображение и соответствующую метку.
image, label = mnist_train[2]
image.shape, label
Наш пример, сохранённый в переменной image, соответствует
изображению высотой и шириной \(28\) пикселей.
image.shape, image.dtype
Наш код хранит метку каждого изображения в виде скаляра. Его тип — целое число \(32\)-битной разрядности.
label, type(label)
Мы также можем одновременно обрабатывать несколько примеров.
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
Давайте визуализируем эти примеры.
d2l.show_images(images, 2, 9);
22.9.2. Вероятностная модель для классификации¶
В задаче классификации мы сопоставляем пример категории. В данном случае примером является полутоновое \(28\times 28\) изображение, а категорией — цифра. (Более подробное объяснение см. в Section 4.1.) Одним из естественных способов формулировки задачи классификации является вероятностный вопрос: какова наиболее вероятная метка при заданных признаках (то есть пикселях изображения)? Обозначим через \(\mathbf x\in\mathbb R^d\) признаки примера, а через \(y\in\mathbb R\) — метку. В нашем случае признаками выступают пиксели изображения; мы можем преобразовать изображение размерности \(2\) в вектор так, чтобы выполнялось условие \(d=28^2=784\), а метками являются цифры. Вероятность метки при заданных признаках равна \(p(y \mid \mathbf{x})\). Если мы способны вычислить эти вероятности, которые в нашем примере соответствуют \(p(y \mid \mathbf{x})\) для \(y=0, \ldots,9\), то классификатор выдаст предсказание \(\hat{y}\), определяемое следующим выражением:
К сожалению, это требует оценки \(p(y \mid \mathbf{x})\) для каждого значения \(\mathbf{x} = x_1, ..., x_d\). Предположим, что каждый признак может принимать одно из \(2\) значений. Например, признак \(x_1 = 1\) может означать, что слово apple встречается в данном документе, а \(x_1 = 0\) — что оно не встречается. Если бы у нас было \(30\) таких бинарных признаков, это означало бы, что нам нужно быть готовыми классифицировать любое из \(2^{30}\) (более 1 миллиарда!) возможных значений входного вектора \(\mathbf{x}\).
Более того, где здесь обучение? Если нам нужно видеть каждый возможный пример, чтобы предсказать соответствующую метку, то мы не столько учимся распознавать закономерности, сколько запоминаем набор данных.
22.9.3. Наивный байесовский классификатор¶
К счастью, вводя некоторые предположения о условной независимости, мы можем добавить индуктивное смещение и построить модель, способную обобщать на основе сравнительно небольшого набора обучающих примеров. Для начала воспользуемся теоремой Байеса, чтобы выразить классификатор в виде
Обратите внимание, что знаменатель является нормирующим членом \(p(\mathbf{x})\), который не зависит от значения метки \(y\). Следовательно, нам достаточно сравнивать числитель при различных значениях \(y\). Даже если бы вычисление знаменателя оказалось неразрешимой задачей, мы могли бы обойтись без него, при условии, что числитель можно вычислить. К счастью, даже если бы мы захотели восстановить нормирующую константу, мы бы смогли это сделать. Мы всегда можем восстановить нормирующий член, поскольку \(\sum_y p(y \mid \mathbf{x}) = 1\).
Теперь сосредоточимся на \(p( \mathbf{x} \mid y)\). Используя цепное правило вероятности, мы можем выразить величину \(p( \mathbf{x} \mid y)\) как
Само по себе это выражение не позволяет нам продвинуться дальше. Нам по-прежнему необходимо оценить примерно \(2^d\) параметров. Однако, если мы предположим, что признаки условно независимы друг от друга при заданной метке, то ситуация значительно улучшается, так как этот член упрощается до \(\prod_i p(x_i \mid y)\), что дает нам предсказатель
If we can estimate \(p(x_i=1 \mid y)\) for every \(i\) and \(y\), and save its value in \(P_{xy}[i, y]\), here \(P_{xy}\) is a \(d\times n\) matrix with \(n\) being the number of classes and \(y\in\{1, \ldots, n\}\), then we can also use this to estimate \(p(x_i = 0 \mid y)\), i.e.,
Кроме того, мы оцениваем \(p(y)\) для каждого \(y\) и сохраняем его в \(P_y[y]\), где \(P_y\) — это вектор длины \(n\). Затем для любого нового примера \(\mathbf t = (t_1, t_2, \ldots, t_d)\) мы можем вычислить
для любого \(y\). Таким образом, наше предположение о условной независимости снизило сложность нашей модели с экспоненциальной зависимости от числа признаков \(\mathcal{O}(2^dn)\) до линейной, что \(\mathcal{O}(dn)\).
22.9.4. Обучение¶
Проблема заключается в том, что мы не знаем \(P_{xy}\) и \(P_y\). Поэтому нам необходимо сначала оценить их значения, используя имеющиеся обучающие данные. Это и есть обучение модели. Оценка \(P_y\) не представляет особой сложности. Поскольку мы имеем дело только с \(10\) классами, мы можем подсчитать количество вхождений \(n_y\) для каждой из цифр и разделить это число на общий объём данных \(n\). Например, если цифра 8 встречается \(n_8 = 5,800\) раз, а общее количество изображений равно \(n = 60,000\), то оценка вероятности составит \(p(y=8) = 0.0967\).
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
Теперь перейдем к чуть более сложным вещам \(P_{xy}\). Поскольку мы выбрали черно-белые изображения, \(p(x_i \mid y)\) обозначает вероятность того, что пиксель \(i\) будет активен для класса \(y\). Как и раньше, мы можем подсчитать количество раз \(n_{iy}\), когда происходит событие, и разделить его на общее число случаев \(y\), то есть \(n_y\). Однако есть одна небольшая проблема: некоторые пиксели могут никогда не быть черными (например, в хорошо обрезанных изображениях угловые пиксели всегда могут быть белыми). Удобный способ для статистиков решить эту проблему — добавить псевдосчетчики ко всем наблюдениям. Таким образом, вместо \(n_{iy}\) мы используем \(n_{iy}+1\), а вместо \(n_y\) — \(n_{y}+2\) (поскольку пиксель \(i\) может принимать только два возможных значения — он может быть либо черным, либо белым). Этот метод также называется сглаживанием Лапласа. Он может показаться произвольным, однако его можно обосновать с байесовской точки зрения, используя модель бета-биномиального распределения.
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);
Визуализируя эти \(10\times 28\times 28\) вероятности (для каждого пикселя и каждого класса), мы можем получить усреднённые изображения цифр.
Теперь мы можем использовать (22.9.6) для предсказания нового изображения. При заданном \(\mathbf x\) следующая функция вычисляет \(p(\mathbf x \mid y)p(y)\) для каждого \(y\).
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)
Это пошло ужасно не так! Чтобы понять почему, давайте посмотрим на вероятности для каждого пикселя. Обычно это числа между \(0.001\) и \(1\). Мы перемножаем \(784\) таких чисел. В этот момент стоит упомянуть, что мы вычисляем эти значения на компьютере, а значит, с ограниченным диапазоном для экспоненты. Что происходит, так это то, что мы сталкиваемся с числовой недодетекцией, то есть перемножение всех этих малых чисел приводит к ещё меньшим значениям, пока они не округлятся до нуля. Мы обсуждали это как теоретическую проблему в Section 22.7, но здесь мы ясно видим это явление на практике.
Как обсуждалось в том разделе, мы решаем эту проблему, используя тот факт, что \(\log a b = \log a + \log b\), то есть переходим к суммированию логарифмов. Даже если оба значения \(a\) и \(b\) малы, значения логарифмов должны находиться в корректном диапазоне.
a = 0.1
print('underflow:', a**784)
print('logarithm is normal:', 784*math.log(a))
Поскольку логарифм — возрастающая функция, мы можем переписать (22.9.6) в виде
Мы можем реализовать следующую стабильную версию:
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
Теперь мы можем проверить, верно ли предсказание.
py.argmax(dim=0) == label
Если теперь предсказать несколько примеров из проверочной выборки, можно увидеть, что байесовский классификатор работает довольно хорошо.
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]);
Наконец, вычислим общую точность классификатора.
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
Современные глубокие сети достигают уровня ошибок менее \(0.01\). Относительно низкая производительность обусловлена неверными статистическими предположениями, заложенными в модель: мы предположили, что каждый пиксель генерируется независимо от других, завися только от метки. Это явно не соответствует тому, как люди пишут цифры, и это ошибочное предположение привело к провалу нашего чрезмерно наивного (байесовского) классификатора.
22.9.5. Итог¶
Используя правило Байеса, классификатор можно построить, предполагая, что все наблюдаемые признаки независимы.
Этот классификатор можно обучить на наборе данных, подсчитывая количество вхождений комбинаций меток и значений пикселей.
Этот классификатор на протяжении десятилетий был золотым стандартом для таких задач, как обнаружение спама.
22.9.6. Упражнения¶
Рассмотрим набор данных \([[0,0], [0,1], [1,0], [1,1]]\), метки которого определяются как исключающее ИЛИ (XOR) двух элементов \([0,1,1,0]\). Каковы вероятности для наивного байесовского классификатора, обученного на этом наборе данных? Успешно ли он классифицирует эти точки? Если нет, какие допущения нарушены?
Предположим, что мы не использовали сглаживание Лапласа при оценке вероятностей, и во время тестирования поступил пример, содержащий значение, которое никогда не встречалось в обучающих данных. Что выведет модель?
Наивный байесовский классификатор является конкретным примером байесовской сети, в которой зависимости случайных величин закодированы с помощью графовой структуры. Хотя полная теория выходит за рамки данного раздела (полные детали см. в Koller and Friedman (2009)), объясните, почему явное разрешение зависимости между двумя входными переменными в модели XOR позволяет создать успешный классификатор.