Intelligent Information Retrieval: Text Document Categorization & Classification Tasks

Text/Document Categorization Part I CSC 575 Intelligent Information Retrieval

Text Categorization Assigning documents to a fixed set of categories Special case of classification in machine learning Applications: Web pages / documents Recommending Automatic bookmarking Yahoo-like directories Micro-blogs / Social Media Recommending posts Categorizing items based on social tags News articles Personalized news recommendation Email messages Routing / Folderizing Spam filtering 2 Intelligent Information Retrieval

Classification Task Given: A description of an instance, x X, where X is the instance language or feature space. Typically, x is a row in a table with the instance/feature space described in terms of features or attributes. A fixed set of class or category labels: C={c1, c2, cn} Classification task is to determine: The class/category of x: c(x) C, where c(x) is a function whose domain is X and whose range is C. 3

Learning for Classification Training examples: Instance x X, paired with its correct class label c(x): <x, c(x)> for an unknown classification function, c. Given a set of training examples, D: Find a hypothesized classification function, h(x), such that: h(x) = c(x), for all training instances (i.e., for all <x, c(x)> in D). This is called consistency. 4

Example of Classification Learning Instance language: <size, color, shape> size {small, medium, large} color {red, blue, green} shape {square, circle, triangle} C = {positive, negative} D: Example Size Color Shape Category 1 small red circle positive 2 large red circle positive 3 small red triangle negative 4 large blue circle negative Hypotheses? circle positive? red positive? 5

Issues to Consider in Supervised Learning Many hypotheses can be consistent with the training data Classification accuracy (% of instances classified correctly). Measured on independent test data Efficiency Issues: Training time (efficiency of training algorithm) Testing time (efficiency of subsequent classification) Bias-Variance Trade-Off High-bias/low-variance means model is too simple to fit the training data (under-fitting) High-variance/low-bias (model too complex; fits nuances of training data well, but won t generalize well on test data (over-fitting) 6

Learning for Text Categorization Common algorithms for text/document categorization: Nearest Neighbor (case based) Relevance Feedback (Rocchio) Bayesian (na ve) Neural networks Support Vector Machines (SVM) 7 Intelligent Information Retrieval

Nearest-Neighbor Learning Algorithm Learning is just storing the representations of the training examples in D. Testing instance x: Compute similarity between x and all examples in D. Assign x the category of the k most similar example in D. Also called: Memory-based reasoning Lazy learning 8 Intelligent Information Retrieval

Similarity Metrics 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. 9 Intelligent Information Retrieval

K Nearest Neighbor for Text Training: For each each training example <x, c(x)> D Compute the corresponding TF-IDF vector, dx, for document x Test instance y: Compute TF-IDF vector d for document y For each <x, c(x)> D Let sx = cosSim(d, dx) Sort examples, x, in D by decreasing value of sx Let N be the first k examples in D. (get most similar neighbors) Return the majority class of examples in N 10 Intelligent Information Retrieval

Nearest Neighbor with Inverted Index 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 VSR 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. Therefore, overall classification is O(Lt + B|Vt|) Typically B << |D| 11 Intelligent Information Retrieval

KNN for Document Categorization T1 2 0 4 0 0 1 2 3 T2 0 2 0 1 0 1 1 1 T3 4 4 1 0 2 0 3 0 T4 3 0 3 2 0 2 4 4 T5 0 2 0 0 0 0 0 1 T6 1 3 1 0 4 1 2 0 T7 0 0 0 1 0 1 0 2 T8 2 0 1 0 0 3 2 1 Cat Cat1 Cat1 Cat2 Cat1 Cat1 Cat2 Cat2 ? DOC1 DOC2 DOC3 DOC4 DOC5 DOC6 DOC7 DOC8 12

KNN for Document Categorization Using Cosine Similarity to find K=3 neighbors: T1 2 0 4 0 0 1 2 3 T2 0 2 0 1 0 1 1 1 T3 4 4 1 0 2 0 3 0 T4 3 0 3 2 0 2 4 4 T5 0 2 0 0 0 0 0 1 T6 1 3 1 0 4 1 2 0 T7 0 0 0 1 0 1 0 2 T8 2 0 1 0 0 3 2 1 Norm 5.83 5.74 5.29 2.45 4.47 4.12 6.16 5.66 Sim(D8,Di) 0.61 0.12 0.84 0.79 0.00 0.73 0.72 DOC1 DOC2 DOC3 DOC4 DOC5 DOC6 DOC7 DOC8 = (D8 D7) / (Norm(D8).Norm(D7) = (3x2+1x1+0x3+4x4+1x0+0x2+2x0+1x2) / (5.66 x 6.16) = 25 / 34.87 = 0.72 E.g.: Sim(D8,D7) 13

KNN for Document Categorization T1 T2 T3 T4 T5 T6 T7 T8 DOC1 2 0 4 DOC2 0 2 4 DOC3 4 0 1 DOC4 0 1 0 DOC5 0 0 2 DOC6 1 1 0 DOC7 2 1 3 DOC8 3 1 0 Cat Cat1 Cat1 Cat2 Cat1 Cat1 Cat2 Cat2 5.66 Sim(D8,Di) 0.61 0.12 0.84 0.79 0.00 0.73 0.72 3 0 3 2 0 2 4 4 0 2 0 0 0 0 0 1 1 3 1 0 4 1 2 0 0 0 0 1 0 1 0 2 2 0 1 0 0 3 2 1 Simple voting: Cat for DOC 8 = Cat2 with confidence 2/3 = 0.67 Weighted voting: Cat for DOC 8 = Cat2 Confidence: (0.84 + 0.73) / (0.84 + 0.79 + 0.73) = 0.66 14

Using Relevance Feedback (Rocchio) Relevance feedback methods can be adapted for text categorization. Use standard TF/IDF weighted vectors to represent text documents (typicaly normalized by maximum term frequency). For 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. 15 Intelligent Information Retrieval

Rocchio Text Categorization Algorithm (Training) Assume the set of categories is {c1, c2, cn} For i from 1 to n let pi= <0, 0, ,0> (init. prototype vectors) For each training example <x, c(x)> D Let d be the TF/IDF term vector for doc x Let i = j: (cj = c(x)) (sum all the document vectors in ci to get pi) Let pi = pi + d 16 Intelligent Information Retrieval

Rocchio Text Categorization Algorithm (Test) Given test document x Let d be the TF/IDF term vector for x Let m = 2 (init.maximum cosSim) For i from 1 to n: (compute similarity to prototype vector) Let s = cosSim(d, pi) if s > m let m = s let r = ci (update most similar class prototype) Return class r 17 Intelligent Information Retrieval

Rocchio Properties Does not guarantee a consistent hypothesis. 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. 18 Intelligent Information Retrieval

Rocchio-Based Categorization - Example t1 2 0 1 1 0 1 0 1 3 1 t2 1 3 0 0 1 2 1 1 0 0 t3 0 1 2 1 0 0 0 0 1 1 t4 1 0 0 2 1 0 2 1 1 0 t5 0 0 2 0 0 2 0 0 1 1 Spam no no yes yes yes no yes yes no yes For simplicity, in this example we will use raw term frequencies (normally full TFxIDF weights should be used). D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 Norm Cos Sim with New Doc Prototype: "no" Prototype: "yes" 6 6 2 2 3 9.434 0.673 4 3 4 6 3 9.274 0.809 New Doc 1 0 0 1 1 1.732 So, the new document/email should it be classified as spam = yes because it is more similar to the prototype for the yes category. 19 Intelligent Information Retrieval

Next: Part II Bayesian Classification CSC 575 Intelligent Information Retrieval