Mathieu’s log

Semi-supervised Naive Bayes in Python

Expectation-Maximization

The Expectation-Maximization (EM) algorithm is a popular algorithm in statistics and machine learning to estimate the parameters of a model that depends on latent variables. (A latent variable is a variable that is not expressed in the dataset and thus that you can’t directly count. For example, in pLSA, the document topics z are latent variables.) EM is very intuitive. It works by pretending that we know what we’re looking for: the model parameters. First, we make an initial guess, which can be either random or “our best bet”. Then, in the E-step, we use our current model parameters to estimate some “measures”, the ones we would have used to compute the parameters, had they been available to us. In the M-step, we use these measures to compute the model parameters. The beauty of EM is that by iteratively repeating these two steps, the algorithm will provably converge to a local maximum for the likelihood that the model generated the data.

Naive Bayes trained with EM

In their paper “Semi-supervised Text Classification Using EM”, Nigam et al. describe how to use EM to train a Naive Bayes classifier in a semi-supervised fashion, that is with both labeled and unlabeled data. The algorithm is very intuitive:

Train a classifier with your labeled data
While the model likelihood increases:
- E-step: Use your current classifier to find P(c|x) for all classes c and all unlabeled examples x. These can be thought as probabilistic/fractional labels.
- M-step: Train your classifier with the union of your labeled and probabilistically-labeled data.

The hope is that using (abundantly available) unlabeled data, in addition to (labor-intensive) labeled data, improves the quality of the classifier.

Code

I made a simple implementation of it in Python + Numpy. The code is fairly optimized.

$ git clone http://www.mblondel.org/code/seminb.git

web interface

Implementation details

Here are implementation details that were not mentioned in the original paper and that I found necessary to get a correct implementation.

Naive Bayes is called naive because of the (obviously wrong) assumption that words are conditionally independent given the class:

$P(x_i|c_j) = \prod_{t}^V P(w_t|c_j)^{x_{it}}$

However, since the vocabulary size V can be pretty big and the probabilities P(w|c) can be pretty small, P(x|c) can quickly exceed the precision of the computer and become zero. The solution is to perform the computations in the log domain:

$\log P(x_i|c_j) = \sum_{t}^V x_{it} \log P(w_t|c_j)$

To turn around P(x|c), we use Bayes’rule:

$P(y_i=c_j|x_i) = \frac{P(c_j)P(x_i|c_j)}{P(x_i)} = \frac{P(c_j)P(x_i|c_j)}{\sum_k P(c_k)P(x_i|c_k)}$

By posing $z_j = \log P(c_j) + \log P(x_i|c_j)$ , we get:

$P(y_i=c_j|x_i) = \frac{e^{z_j}}{\sum_k e^{z_k}}$

This is the softmax function. However, we are back to our initial problem because, since the $z_j$ are likely to tend to -inf, the exponentials are likely to in turn underflow. The trick is to multiply the numerator and denominator by the same constant $e^{-m}$ :

$P(y_i=c_j|x_i) = \frac{e^{z_j-m}}{\sum_k e^{z_k-m}}$

Setting m to $max_j~z_j$ , the $z_j-m$ values will get closer to zero. The rationale for this is that computation of the exponential overflows earlier and is less precise for big values (positive or negative) than for small values.

This trick will improve the situation quite a lot but in case this is not enough:

$P(y_i=c_j|x_i) = \begin{cases} 0, & \mbox{if } z_j - m \le t \\ \frac{e^{z_j-m}}{\sum_{\{k~:~z_k-m > t\}} e^{z_k-m}}, & \mbox{otherwise} \end{cases}$

This sets the exponentials to zero when $e^{z_j-m} \le e^t$ . For t=-10, this is 0.000045. Equivalently this corresponds to setting the exponentials to zero when $e^{z_j} \le e^{t+m}$ . Since both t and and m are negative, this shows that subtracting the maximum m, as explained before, does help improving the precision.

Reference

Kamal Nigam, Andrew McCallum and Tom Mitchell. Semi-supervised Text Classification Using EM. In Chapelle, O., Zien, A., and Scholkopf, B. (Eds.) Semi-Supervised Learning. MIT Press: Boston. 2006.

This entry was posted on Monday, June 21st, 2010 at 6:47 pm and is filed under In English, Machine Learning. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.