Each document is a vector, one component for each term (= word).
Normally normalize vectors to unit length.
How can we do classification in this space?
For training documents in each category, compute a prototype vector by summing the vectors of the training documents in the category.
Assign test documents to the category with the closest prototype vector based on cosine similarity.
Where Dc is the set of all documents that belong to class c and v(d) is the vector space representation of d.
Note that centroid will in general not be a unit vector even when the inputs are unit vectors.
Forms a simple generalization of the examples in each class (a prototype).
Prototype vector does not need to be averaged or otherwise normalized for length since cosine similarity is insensitive to vector length.
Classification is based on similarity to class prototypes.
Does not guarantee classifications are consistent with the given training data.
Prototype models have problems with polymorphic (disjunctive) categories.
Learning is just storing the representations of the training examples in D.
Compute similarity between x and all examples in D.
Assign x the category of the most similar example in D.
Does not explicitly compute a generalization or category prototypes.
In particular, asymptotic error rate is 0 if Bayes rate is 0.
Assume: query point coincides with a training point.
Noise (i.e., an error) in the category label of a single training example.
More robust alternative is to find the k most-similar examples and return the majority category of these k examples.
Value of k is typically odd to avoid ties; 3 and 5 are most common.
Nearest neighbor method depends on a similarity (or distance) metric.
Simplest for continuous m-dimensional instance space is Euclidean distance.
Simplest for m-dimensional binary instance space is Hamming distance (number of feature values that differ).
For text, cosine similarity of tf.idf weighted vectors is typically most effective.
Nearest Neighbor tends to handle polymorphic categories better than Rocchio/NB.
But determining k nearest neighbors is the same as determining the k best retrievals using the test document as a query to a database of training documents.
Use standard vector space inverted index methods to find the k nearest neighbors.
Testing Time: O(B|Vt|) where B is the average number of training documents in which a test-document word appears.
In general, lots of possible solutions for a,b,c.
Lots of possible solutions for a,b,c.
Which points should influence optimality?
For separable problems, there is an infinite number of separating hyperplanes. Which one do you choose?
What to do for non-separable problems?
Classifiers more powerful than linear often don’t perform better on text problems. Why?
Decide class C if the odds is greater than 1, i.e., if the log odds is greater than 0.
Pictures like the one at right are absolutely misleading!
Classes are independent of each other.
A document can belong to 0, 1, or >1 classes.
Is there a learning method that is optimal for all text classification problems?
No, because there is a tradeoff between bias and variance.
How much training data is available?
How noisy is the data?
How stable is the problem over time?
For an unstable problem, it’s better to use a simple and robust classifier.