14 Vector Space Classification

Question 1

Vector space classification

Answer 1

Goal: To develop a different representation for TC, the vector space model from chapter 6. Different from the rep used in last chapter where the doc rep in Naive Bayes was a sequence of terms or a binary vector.

Question 2

Contiguity hypothesis

Answer 2

Document in the same class form a contigous regin and regions of different classes do not overlap.

Question 3

Prototype

Answer 3

A centroid in the Rocchio classifier.

Question 4

Decision boundary

Answer 4

Boundaries to separate the classes. To classify a new document, we deter- mine the region it occurs in and assign it the class of that region.

Question 5

Multimodal class

Answer 5

A class with several logical clusters.

Question 6

k nearest neighbour/kNN classification

Answer 6

A classifier who determines the decision boundary locally. For 1NN we assign each doc to the class of its closes neighbour. For kNN we assign each doc to the majority class of its k closest neighbours where k is a parameter. The rationale of kNN classification is that, based on the contiguity hypohothesis, we expect a test doc d to have the same label as the training docs located in the local region surrounding d.

Question 7

Memory based learning/instance-based learning

Answer 7

kNN is an example of this. We do not perform any estimation of parameters. kNN simply memorizes all examples in the training set and then compares the test doc to them.

Question 8

Bayes error rate

Answer 8

A measure of the quality of a learning method. The average error rate of classifiers learned by it for a particular problem.

Question 9

Bias-variance tradeoff

Answer 9

There is a tradeoff when selecting a classifier that produces good classifiers across sets (small variance) and that can learn classification problems with very difficult decision boundaries (small bias).

Bias
Bias is large if the learning method produces classifiers that are consistently wrong. Bias is small if:

1. The classifiers are consistently right
2. Different training sets cause errors on different documents
3. Different training sets cause positive and negative errors on the same docs, but that average out close to 0.

Linear method like Rocchio and NB have high bias for nonlinear problems Nonlinear methods like kNN have a low bias, because the decision boundaries are variable, depending on the distribution of docs in the training set, learned decision boundaries can vary greatly.

Variance
Is the variation of the prediction of learned classifiers. Is large if different give rise to very different classifiers. It is small if the training set has a minor effect on the classification decision the classifier makes, be they correct or incorrect. Variance measures how inconsistent the dections are, not wheter they are correct or incorrect.