## Document classification - Task: Automatically assign documents to categories - Applications - Spam detection - Email sorting - Detect sexually explicit content - Domain-specific search (e.g., Google Scholar) - Language detection - Information filtering / standing queries - Formal - Document space `$ X $` - Set of classes `$ C=\{c_1,...,c_r\} $` - Set of training pairs `$ D\subseteq X\times C $` - Task: Find function `$ f:X\rightarrow C $` - Evaluate using a test set ### Naïve Bayes - Idea: Estimate (train) probabilities from test set - Bayesian network - Directed acyclic graph - Nodes: Observable variables/events - Edges: Conditions between events - Observation: Probabilities don't sum up to one - Reason: Statistical independence does not hold in data - Therefore: Naïve Bayes is heuristic - Optimization: Only use positive events (term-occurrence not lack of terms) ![](images/bayes.png) #### Classification - Occurrence/lack of terms in documents are events - Find probability of class membership - `$ P(C\mid t_1,...,t_n) = P(C\mid d) $` - Use Bayes' theorem - `$ P(C\mid t_1,...,t_n) = \frac{P(C)}{P(t_1,...,t_n)} P(t_1,...,t_n\mid C) $` - Assume statistical independence - `$ P(C\mid t_1,...,t_n) = \frac{P(C)}{\Pi_{i=1}^n P(t_i)} \Pi_{i=1}^n P(t_i\mid C) $` - Assign document to class with highest probability #### Problem: Data sparseness - Solution: Smoothing 1. Laplace smoothing (add `$ 1 $` to each term count) 2. Weight `$ P(t_i\mid C) $` and `$ P(t_i) = \frac{df(t_i)}{N} $` - e.g., `$ P(t_i\mid C) = \lambda P(t_i\mid C) + (1-\lambda)P(t_i) $` #### Extensions - Use number of occurrences - Better/advanced smoothing - No independence assumption - Use more than two classes - Use discriminative terms ### Rocchio - Model: Vector space model - Identify class by its centroid - Assume classes are spheres - Contiguity hypothesis - *Documents from same class form contiguous regions and different classes do not overlap* - Classification: - Assign document to class with the nearest centroid - i.e., 1-NN with centroids as data points - Use *Voronoi tessellation* for visualization ### k-Nearest neighbors - Model: Vector space model - Identify class by its documents - Classification: - Assign document to *majority* class of its k closest neighbors - Bias-variance tradeoff - Underfitting: High k - Overfitting: Low k - Option: Weight votes - Use cosine similarity - `$ score(C) = \sum_{x\in NN_k(d), class(x)=C} sim(d, x) $` ### Support Vector Machine - Assumptions - Binary classification (-1, 1) - Vector space model - Task: Find *linear* classifier - Idea: Maximize margin of classifier #### Maximum margin classifier - Motivation - Intuitive design - Robust against errors - Theoretical arguments - Empirical arguments - Formalization - `$ n $` training examples - Training set `$ T=\{(x_i, y_i)\mid x_i\in \mathbb{R}^d, y_i\in\{-1,1\}\} $` - Steps - Formalization of the hyperplane - Why does a perfect separating hyperplane exist? - How to compute this perfect separating hyperplane? ##### Hyperplane - Normal vector `$ w\in \mathbb{R}^d $` - Shift from origin `$ b\in \mathbb{R} $` - `$ w*u+b=0, u\in \mathbb{R}^d $` - `$ w*x_i + b > 0 \Rightarrow y_i=1 $` - `$ w*x_i + b < 0 \Rightarrow y_i=-1 $` - Data points: `$ y_i(w*x_i + b) - 1 \geq 0 $` ##### Existence of a perfect hyperplane - Idea: If there is a separating hyperplane, move the perfect one in the middle of the two boundary hyperplanes - Corollary: If there is a separating hyperplane `$ (w,b) $` there is always a hyperplane `$ (w'',b'') $` such that - `$ (w'',b'') $` is valid - `$ (w,b) $` and `$ (w'',b'') $` have equal margin widths - Bounding hyperplanes of `$ (w'',b'') $` are shifted away by one - Proof 1. Assumption: There is *some* separating hyperplane `$ wx+b=0 $` 2. Move plane into center - `$ b' = b+\frac{r_--r_+}{2} $` - `$ wx+b+\frac{r_--r_+}{2}=0 $` - It has equal shift constants `$ r_- = r_+ $` 3. Normalize hyperplane - `$ w'' = \frac{w}{r_-} + \frac{b'}{r_-}) $` - It has shift constants `$ r_- = r_+ = 1 $` ##### Computation / Duality - Goal: Maximize margin - Distance of plane to center: `$ d=\frac{|b|}{||w||} $` - Margin width 1. `$ \frac{|b|+1-(|b|-1)}{||w||}=\frac{2}{||w||} $` 1. `$ (x_+-x_-)*\frac{w}{||w||}=\frac{2}{||w||} $` - Minimize `$ \frac{1}{2} ||w||^2 $` - Standard form for quadratic programming - Constraint: `$ y_i(w*x_i+b)-1\geq 0 $` (every data point is classified correctly) - Use Lagrange multipliers - Maximize `$ \max_{\alpha\in\mathbb{R}^n} \sum_{i} \alpha_i-\frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j x_i x_j $` - If `$ \alpha_i > 0 $`, `$ x_i $` is support vector - Classification function: `$ f(x) = sgn(\sum_i \alpha_i y_i x_i*x + b) $` - Observation: Computation depends on scalar product #### Soft margin classifier - Idea: - Assumption that data would be linearly separable does not hold - Allow errors/noise - Each misclassification gets an error - Minimize total classification error - Optimization problem - `$ \frac{1}{2} ||w||^2 + C*(\beta_1+...+\beta_n) $` - Constraints: - `$ \beta_i\geq 0 $` - `$ y_i(w*x_i+b)\geq -\beta_i $` - `$ C\geq \alpha_i \geq 0 $` - `$ \sum_i \alpha_i y_i = 0 $` #### Multiple class classifier - SVM handles two classes - One-versus-all - One-versus-one (one SVM per class pair) - Multiclass SVM (complicated) #### Non-linear SVM - Problem: Not all data is linearly separable (not noise) - Idea: Transform data into higher-dimensional space - Observation: Classification and training function use scalar product of vectors - *Kernel trick* - Transform function `$ h: \mathbb{R}^d \rightarrow \mathbb{R}^{d'} $` - Kernel is function that computes the scalar product of two vectors efficiently - e.g. polynomial kernel `$ k(x,y)=(1+x+y)^2 $` - Applications - Speech recognition - Predict protein structures - Beast cancer prognosis - Stock forecast ![](images/kerneltrick.png) #### SVM in information retrieval ##### Text classification - Automatic assignment of topics - Application to small and medium-sized document collections ##### Learning to rank - Training set consists of pairs of documents `$ (d_i, d_j) $` such that `$ d_i $` is preferred to `$ d_j $` - Task: - Find ranking function that assigns a numerical score `$ s(d) $` to each document - `$ d_i \text{is preferred to} d_j \Rightarrow s(d_i) > s(d_j) $` - Straightforward: - `$ s(d) = w*d $` (linear ranking) - Use SVM to train - Constraint: `$ w * (d_i - d_j) -1 \geq 0 $` - How to get training data? - Joachims (2002) - If user clicks on result `$ k $` and not on result `$ k-1 $`, result `$ k $` is preferred to result `$ k-1 $` - Workflow 1. Compute initial results 2. Collect user clicks 3. Learn ranking function 4. Use ranking function in retrieval process ### Boosting - Meta-algorithms: Blueprint for the combination of classification algorithms - Idea: Combine weak learners to get a strong learner - *Weak learner*: Slightly better than random guessing - Approaches: - Majority vote - Adaptive boosting #### Majority vote - Approach 1. Train each base classifier indepently 2. Use majority vote of all classifiers for new document - Problem: Individual strengths are ignored - Solution: Allow expert votes (adaptive boosting) #### Adaptive boosting - Approach 1. Train first base classifier 2. Identify errors (misclassified documents) 3. Assign high weight to errors/low weight to correct ones 4. Train next base classifier on weighted training set 5. Return to (2) - Assign *importance weight* to each base classifier - High importance if low-weight-objects are misclassified - Low importance if high-weight-objects are misclassified - Classification: Use weighted majority vote - Tuning: Balance weights (importance + individual) - Majority should be right very often - Advantage - Focus on *hard* training objects (expert vote) ### Bias-Variance tradeoff - *Bias*: Degree of not accounting specific characteristics of the training set - *Variance*: Variance of the classifier over different training sets drawn from the *true* data points - Learning error = *Bias* + *Variance* - Overfitting: Low bias, high variance - Underfitting: High bias, low variance - Strategies to avoid overfitting - Cross-validation (split data set, use classifier with best performance on test set) - Regularization (add penalty for complex models, e.g., low polynomial degree; e.g., soft margin SVM) ![](images/overfitting.png)