4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sobi
    Dec 20, 2015 at 23:11

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I have clarified the question to explain what I find puzzling:high level image classification based on a fingerprint of low level features $\endgroup$
    – seanv507
    Dec 20, 2015 at 22:55
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.