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||} \)
      2. \( (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