# Theoretical justification for bag of words

Bag of words and visual bag of words are successful machine learning approaches. Does anyone know of a theoretical justification for why / when they work?

What I am trying to explain is the good performance on image classification tasks. Why does a 'fingerprint' of low level image features (Eg sift) allow discrimination between object classes and generalisation to new images.

So the explanation I think I am after perhaps deals with the statistics of SIFT features.

Is it even true that it is good performance, or are the images collected (Eg imagenet) stereotypical, so that training and test set are more related than real world images as might be gathered by a robot exploring its environment.

• Is your question about SIFT features specifically, or Bag of Words models in general? Performance of BoW models depends mainly on the quality of the dictionary and how discriminative the visual words in the dictionary are. – Sobi Dec 20 '15 at 23:11

You can think of bag of words (BoW) model as a generative model that generates visual words by drawing i.i.d. samples from a multinomial distribution.

# Generative interpretation of BoW models

Consider a (visual) vocabulary of size $K$. Let $v = \{v_1, \dots, v_K\}$ denote the categorical distribution defined over these $K$ possible outcomes so that $v_k$ denotes the probability that a sample from the bag is from the $k$-th visual word. The probability that we observe $b_k$ elements from the $k$-th word in a bag of size $|b| = \sum_{k=1}^K b_k$ is computed from a multinomial distribution with parameters $v$ as follows: $$p(b \mid v) = \frac{|b|!}{b_1! \times b_2! \times \dots \times b_K!}\prod_{k=1}^K v_k^{b_k} \tag{1}$$

# Training BoWs using MLE vs. regularized log linear models

Note that $\log\left( p(b \mid v) \right) = \sum_{k=1}^K b_k \log(v_k) = w \cdot b$ where $w = \log(v)$, and finding the maximum likelihood estimate of the parameters $v$ on a set of $n$ training bags $B = \{b^{(1)}, b^{(2)}, \dots, b^{(n)}\}$ is equivalent to training a regularized BoW model $w$ on $B$: \begin{align} v^* &= \arg\max_v p(B | v) \\ &= \arg\max_v \sum_{i=1}^n \log\left( p(b^{(i)} \mid v) \right) \\ &= \arg\max_v \sum_{i=1}^n \log(v) \cdot b^{(i)} \tag{2} \\ w^* &= \arg\max_w \sum_{i=1}^n w \cdot b^{(i)} - \lambda ||w||^2 \tag{3} \end{align} where $\lambda$ in $(3)$ is a hyperparameter that should be tuned to make $\sum_{k=1}^K e^{w_k} = 1$, thereby, making $v_1 = e^{w_1}, \dots, v_k = e^{w_K}$ a probability distribution.

# References

For more details, see Section 3.1 in Reconfigurable Models for Scene Recognition, CVPR 2012.

• I have clarified the question to explain what I find puzzling:high level image classification based on a fingerprint of low level features – seanv507 Dec 20 '15 at 22:55

I would say that it is like creating a signature, it works because there is enough data in the dictionary to summarise the different parts in the incoming images.

When you create the dictionary, first you take interest point descriptors from the training set and then cluster them. This clusters are what is called dictionary. For each of your categories, you create, with the dictionary, a histogram of occurrences of visual words(your clustered descriptors or dictionary) using the training data. Then, you do this last step with the incoming test image, and you compare the distance between different histograms representing your class and the new image histogram.

It will not work, 1. If the SIFT key points are poor. For instance in some medical images. (Not many textures, edges in the image...) 2. If the dictionary does not represent what is going to be classified later.