🏷️sec_naive_bayes
Throughout the previous sections, we learned about the theory of probability and random variables. To put this theory to work, let us introduce the naive Bayes classifier. This uses nothing but probabilistic fundamentals to allow us to perform classification of digits.
Learning is all about making assumptions. If we want to classify a new data example that we have never seen before we have to make some assumptions about which data examples are similar to each other. The naive Bayes classifier, a popular and remarkably clear algorithm, assumes all features are independent from each other to simplify the computation. In this section, we will apply this model to recognize characters in images.
%matplotlib inline
from d2l import mxnet as d2l
import math
from mxnet import gluon, np, npx
npx.set_np()
d2l.use_svg_display()
#@tab pytorch
%matplotlib inline
from d2l import torch as d2l
import math
import torch
import torchvision
d2l.use_svg_display()
#@tab tensorflow
%matplotlib inline
from d2l import tensorflow as d2l
import math
import tensorflow as tf
d2l.use_svg_display()
MNIST :cite:LeCun.Bottou.Bengio.ea.1998
is one of widely used datasets. It contains 60,000 images for training and 10,000 images for validation. Each image contains a handwritten digit from 0 to 9. The task is classifying each image into the corresponding digit.
Gluon provides a MNIST
class in the data.vision
module to
automatically retrieve the dataset from the Internet.
Subsequently, Gluon will use the already-downloaded local copy.
We specify whether we are requesting the training set or the test set
by setting the value of the parameter train
to True
or False
, respectively.
Each image is a grayscale image with both width and height of
def transform(data, label):
return np.floor(data.astype('float32') / 128).squeeze(axis=-1), label
mnist_train = gluon.data.vision.MNIST(train=True, transform=transform)
mnist_test = gluon.data.vision.MNIST(train=False, transform=transform)
#@tab pytorch
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)
#@tab tensorflow
((train_images, train_labels), (
test_images, test_labels)) = tf.keras.datasets.mnist.load_data()
# Original pixel values of MNIST range from 0-255 (as the digits are stored as
# uint8). For this section, pixel values that are greater than 128 (in the
# original image) are converted to 1 and values that are less than 128 are
# converted to 0. See section 18.9.2 and 18.9.3 for why
train_images = tf.floor(tf.constant(train_images / 128, dtype = tf.float32))
test_images = tf.floor(tf.constant(test_images / 128, dtype = tf.float32))
train_labels = tf.constant(train_labels, dtype = tf.int32)
test_labels = tf.constant(test_labels, dtype = tf.int32)
We can access a particular example, which contains the image and the corresponding label.
image, label = mnist_train[2]
image.shape, label
#@tab pytorch
image, label = mnist_train[2]
image.shape, label
#@tab tensorflow
image, label = train_images[2], train_labels[2]
image.shape, label.numpy()
Our example, stored here in the variable image
, corresponds to an image with a height and width of
#@tab all
image.shape, image.dtype
Our code stores the label of each image as a scalar. Its type is a
label, type(label), label.dtype
#@tab pytorch
label, type(label)
#@tab tensorflow
label.numpy(), label.dtype
We can also access multiple examples at the same time.
images, labels = mnist_train[10:38]
images.shape, labels.shape
#@tab pytorch
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
#@tab tensorflow
images = tf.stack([train_images[i] for i in range(10, 38)], axis=0)
labels = tf.constant([train_labels[i].numpy() for i in range(10, 38)])
images.shape, labels.shape
Let us visualize these examples.
#@tab all
d2l.show_images(images, 2, 9);
In a classification task, we map an example into a category. Here an example is a grayscale sec_softmax
for a more detailed explanation.)
One natural way to express the classification task is via the probabilistic question: what is the most likely label given the features (i.e., image pixels)? Denote by
Unfortunately, this requires that we estimate
Moreover, where is the learning? If we need to see every single possible example in order to predict the corresponding label then we are not really learning a pattern but just memorizing the dataset.
Fortunately, by making some assumptions about conditional independence, we can introduce some inductive bias and build a model capable of generalizing from a comparatively modest selection of training examples. To begin, let us use Bayes theorem, to express the classifier as
Note that the denominator is the normalizing term
Now, let us focus on
By itself, this expression does not get us any further. We still must estimate roughly
$$\hat{y} = \mathrm{argmax}y > \prod{i=1}^d p(x_i \mid y) p(y).$$
If we can estimate
In addition, we estimate
$$\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}$$
:eqlabel:eq_naive_bayes_estimation
for any
The problem now is that we do not know
X, Y = mnist_train[:] # All training examples
n_y = np.zeros((10))
for y in range(10):
n_y[y] = (Y == y).sum()
P_y = n_y / n_y.sum()
P_y
#@tab pytorch
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
#@tab tensorflow
X = train_images
Y = train_labels
n_y = tf.Variable(tf.zeros(10))
for y in range(10):
n_y[y].assign(tf.reduce_sum(tf.cast(Y == y, tf.float32)))
P_y = n_y / tf.reduce_sum(n_y)
P_y
Now on to slightly more difficult things
n_x = np.zeros((10, 28, 28))
for y in range(10):
n_x[y] = np.array(X.asnumpy()[Y.asnumpy() == y].sum(axis=0))
P_xy = (n_x + 1) / (n_y + 1).reshape(10, 1, 1)
d2l.show_images(P_xy, 2, 5);
#@tab pytorch
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 + 1).reshape(10, 1, 1)
d2l.show_images(P_xy, 2, 5);
#@tab tensorflow
n_x = tf.Variable(tf.zeros((10, 28, 28)))
for y in range(10):
n_x[y].assign(tf.cast(tf.reduce_sum(
X.numpy()[Y.numpy() == y], axis=0), tf.float32))
P_xy = (n_x + 1) / tf.reshape((n_y + 1), (10, 1, 1))
d2l.show_images(P_xy, 2, 5);
By visualizing these
Now we can use :eqref:eq_naive_bayes_estimation
to predict a new image. Given
def bayes_pred(x):
x = np.expand_dims(x, axis=0) # (28, 28) -> (1, 28, 28)
p_xy = P_xy * x + (1 - P_xy)*(1 - x)
p_xy = p_xy.reshape(10, -1).prod(axis=1) # p(x|y)
return np.array(p_xy) * P_y
image, label = mnist_test[0]
bayes_pred(image)
#@tab pytorch
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)
#@tab tensorflow
def bayes_pred(x):
x = tf.expand_dims(x, axis=0) # (28, 28) -> (1, 28, 28)
p_xy = P_xy * x + (1 - P_xy)*(1 - x)
p_xy = tf.math.reduce_prod(tf.reshape(p_xy, (10, -1)), axis=1) # p(x|y)
return p_xy * P_y
image, label = train_images[0], train_labels[0]
bayes_pred(image)
This went horribly wrong! To find out why, let us look at the per pixel probabilities. They are typically numbers between sec_maximum_likelihood
, but we see the phenomena clearly here in practice.
As discussed in that section, we fix this by use the fact that
a = 0.1
print('underflow:', a**784)
print('logarithm is normal:', 784*math.log(a))
#@tab pytorch
a = 0.1
print('underflow:', a**784)
print('logarithm is normal:', 784*math.log(a))
#@tab tensorflow
a = 0.1
print('underflow:', a**784)
print('logarithm is normal:', 784*tf.math.log(a).numpy())
Since the logarithm is an increasing function, we can rewrite :eqref:eq_naive_bayes_estimation
as
$$ \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].$$
We can implement the following stable version:
log_P_xy = np.log(P_xy)
log_P_xy_neg = np.log(1 - P_xy)
log_P_y = np.log(P_y)
def bayes_pred_stable(x):
x = np.expand_dims(x, axis=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
#@tab pytorch
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
#@tab tensorflow
log_P_xy = tf.math.log(P_xy)
log_P_xy_neg = tf.math.log(1 - P_xy)
log_P_y = tf.math.log(P_y)
def bayes_pred_stable(x):
x = tf.expand_dims(x, axis=0) # (28, 28) -> (1, 28, 28)
p_xy = log_P_xy * x + log_P_xy_neg * (1 - x)
p_xy = tf.math.reduce_sum(tf.reshape(p_xy, (10, -1)), axis=1) # p(x|y)
return p_xy + log_P_y
py = bayes_pred_stable(image)
py
We may now check if the prediction is correct.
# Convert label which is a scalar tensor of int32 dtype to a Python scalar
# integer for comparison
py.argmax(axis=0) == int(label)
#@tab pytorch
py.argmax(dim=0) == label
#@tab tensorflow
tf.argmax(py, axis=0, output_type = tf.int32) == label
If we now predict a few validation examples, we can see the Bayes classifier works pretty well.
def predict(X):
return [bayes_pred_stable(x).argmax(axis=0).astype(np.int32) for x in X]
X, y = mnist_test[:18]
preds = predict(X)
d2l.show_images(X, 2, 9, titles=[str(d) for d in preds]);
#@tab pytorch
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]);
#@tab tensorflow
def predict(X):
return [tf.argmax(
bayes_pred_stable(x), axis=0, output_type = tf.int32).numpy()
for x in X]
X = tf.stack([train_images[i] for i in range(10, 38)], axis=0)
y = tf.constant([train_labels[i].numpy() for i in range(10, 38)])
preds = predict(X)
d2l.show_images(X, 2, 9, titles=[str(d) for d in preds]);
Finally, let us compute the overall accuracy of the classifier.
X, y = mnist_test[:]
preds = np.array(predict(X), dtype=np.int32)
float((preds == y).sum()) / len(y) # Validation accuracy
#@tab pytorch
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
#@tab tensorflow
X = test_images
y = test_labels
preds = tf.constant(predict(X), dtype=tf.int32)
# Validation accuracy
tf.reduce_sum(tf.cast(preds == y, tf.float32)).numpy() / len(y)
Modern deep networks achieve error rates of less than
- Using Bayes' rule, a classifier can be made by assuming all observed features are independent.
- This classifier can be trained on a dataset by counting the number of occurrences of combinations of labels and pixel values.
- This classifier was the gold standard for decades for tasks such as spam detection.
- Consider the dataset
$[[0,0], [0,1], [1,0], [1,1]]$ with labels given by the XOR of the two elements$[0,1,1,0]$ . What are the probabilities for a Naive Bayes classifier built on this dataset. Does it successfully classify our points? If not, what assumptions are violated? - Suppose that we did not use Laplace smoothing when estimating probabilities and a data example arrived at testing time which contained a value never observed in training. What would the model output?
- The naive Bayes classifier is a specific example of a Bayesian network, where the dependence of random variables are encoded with a graph structure. While the full theory is beyond the scope of this section (see :cite:
Koller.Friedman.2009
for full details), explain why allowing explicit dependence between the two input variables in the XOR model allows for the creation of a successful classifier.
:begin_tab:mxnet
Discussions
:end_tab:
:begin_tab:pytorch
Discussions
:end_tab:
:begin_tab:tensorflow
Discussions
:end_tab: