Introduction

• Quick Supervised Learning Overview
• Premise/Purpose of Semi-Supervised Learning
• Overview of Problems Addressed
• Approach 1: Function Optimization [Yarowski, 1995]
• Approach 2: Co-Training [Blum/Mitchell, 1998]
• Approach 3: Spectral Graph Partitioning [Joachims, 2003]
• Conclusions

Supervised Learning

Given a labeled set of empirical observations:

• Goal: Come up with a model that approximates a process that generated the data
• Purpose: Apply the model to new problems
  • Interpolation
  • Extrapolation
  • Classification
• Evaluation: Partition known observations into training/testing sets
• Premise: A model that fits the training observations and evaluates well might behave like the underlying process on previously unseen data.
• Value Proposition: Automate the task of the underlying process.

Supervised Learning

Examples

• Let's say we have a sample of data points
• 

Supervised Learning

Examples

• Can we generate a model that fits?
• 

Supervised Learning

Examples

• ...then use it to interpolate between known data points
• 

Supervised Learning

Examples

• ...or extrapolate beyond our observations
• 

Supervised Learning

Examples

• When we classify, our model separates data into spacial partitions
• 

Supervised Learning

Examples

• ...which are then used to classify new observations
• 

Supervised Learning

Classification

• Classification requires labelled classes
• Like a discrete finite dimension in the data
• Learner's job is to indentify class boundaries
• Classifier's job is to then apply the class boundaries

Overview of Problems Addressed

Word Sense Disambiguation

Text Classification

Word Sense Disambiguation

Problem Characterization

• Given a word
  • Java
• ...and a known set of meanings for that word
  • {ProgLang, Island, Coffee, Song, PlaceInSouthDakota}
• Determine the meaning of that word
  • "I want a cup of Java" => Coffee
  • "Al Hirt performed Java" => Song
  • "We flew into Java" => Island or PlaceInSouthDakota
  • "Bad Little Java" => ???
• Think of this as a classification problem: Senses are classes

Word Sense Disambiguation

Linguistic Ambiguity Subproblems:

• Polysemes: Terms with multiple related meanings
  • "I'm making a deposit at the bank."
  • "You can bank on that."
• Homonyms: Unrelated meanings, different pronunciation and/or spelling
  • "We went fishing off the river bank."
• Text processing: homographs: different words/meanings, same spelling
  • "desert" (dry place) vs. "desert" (to abandon)
• Speech processing: homophones: different words/meanings, same pronunciation
  • "desert" (to abandon) vs. "dessert"
  • "waste" vs. "waist"
  • "mean" (not nice) vs. "mean" (average)

Overview of Problems Addressed

Text Classification

• From a known set of classes for a given document
• Determine the class of that document
• Example: Positive or Negative review of a movie?
• Can be hierarchical as well:
• Example: Where in DMOZ does this web page belong?
• Some classifiers admit failure to classify, particularly when spatial boundaries are not hyperplanes but hyperpolygons classifying points "inside".
• Typically relies on local lexical cues (TFIDF, cosine, etc.), so bag-of-words vectors are frequently used.
• How this is cast as a learning problem?

Introducing Semi-Supervised Learning

Motivation behind Semi-Supervised Learning

• Labelled data is expensive
• Unlabelled data is cheap(er)
• Can we improve upon supervised learning by bolstering with unlabelled data?

Yarowski Method

NLP Task: Word Sense Disambiguation

Motivating Observations

1. Contextual cues (nearby words) provide helpful clues
   • Term: "Plant"
   • "...keep a manufacturing plant profitable..."
   • "...keep a perennial plant watered..."
2. Uses tend to be consistent within a single discourse
   • "Special Report: Plants of the Midwest"
3. Polysemes are still a problem; plant/N and plant/VT are obviously correlated
4. 1. above should trump 2.
5. 1. and 2. together typically over-determine the sense of a word.

Yarowski Method

NLP Task: Word Sense Disambiguation

One-Sense-Per-Discourse Hypothesis

• Accuracy: Percentage of time when term occurs more than once in a discourse, that the word refers to the same meaning.
• Applicability: How often the term occurs more than once in a discourse.

Word	Senses	Accuracy	Applicability
plant	living/factory	99.8	72.8
tank	vehicle/container	99.6	50.5
poach	steal/boil	100	44.4
palm	tree/hand	99.8	38.5
axes	grid/tools	100	35.5
sake	benefit/drink	100	33.7
bass	fish/music	100	58.8
space	volume/outer	99.2	67.7
motion	legal/physical	99.9	49.8
crane	bird/machine	100	49.1
Average		99.8	50.1

Word Sense Disambiguation

One-Sense-Per-Collocation Hypothesis

Consider the following decision list:

For A. plant (species) vs. B. plant (manufacturing):

Can you classify the meanings?

1. plant growth
• => A
2. car (within +/-k words)
• => B
3. plant height
• => A
4. union (within +/-k words)
• => B
5. equipment (within +/-k words)
• => B
6. assembly plant
• => B
7. nuclear plant
• => B
8. flower (within +/-k words)
• => A
9. job (within +/-k words)
• => B
10. fruit (within +/-k words)
• => A
11. plant species
• => A

Yarowski Method

NLP Task: Word Sense Disambiguation

Algorithm

1. Store contexts of all examples of a given polysemous word in an untagged training set.
2. For each possible sense, select a small number of representative training examples. Those not selected are called the residual
3. 1. Train a supervised learner on this subset.
   2. Apply the learned classifier to the sample set, and store those points that are classified above a confidence threshold.
   3. Optionially apply the one-sense-per-discourse constraint to filter/augment.
   4. Repeat all of Step 3.
4. Stop when model converges (residual set stabilizes).

Yarowski Method

NLP Task: Word Sense Disambiguation

Algorithm Progression

1. 
2. 
3. 

Blum & Mitchell Method

NLP Task: Text Classification

Motivating Observations

1. Redundant representations/views provide multiple feature spaces
   • Lexical Content of a web page
   • Lexical Content of links to a web page
2. Can we utilize multiple learners focusing on separate feature spaces of the same data to bootstrap one another?
3. Algorithm: Repeat the following procedure
   1. Train two classifiers, one per view, on training data
   2. Add strongly-classified unlabelled data from each classifier to training data for other classifier.
   3. Stop when both classify the same unlabelled data equally well (by some statistically significant stopping criteria)
4. The idea is that the two classifiers will vary in the confidence with which they classify individual data points
5. We can use this variation to make the classifiers bootstrap one another to grow the training data from unlabelled points.

Joachims Method

NLP Task: Text Classification

Transductive Learning: Slightly different learning paradigm

1. Reasoning directly from observed training cases to test cases
2. Cluster the unlabelled data (a la unsupervised)
3. Use the clusters to reason about classes in labelled data
4. Intermediate model of underlying process (function) skipped
5. Motivation: Solve your specific problem, not a more general one.

Joachims Method

NLP Task: Text Classification

Understanding the generalized framework

1. Leave-one-out error: Cross Validation using a single datum for model validation.
2. Tells us how well the model generalizes across all possible known data.
3. To devise a Semi-Supervised Scheme:
   • Train a learner on training data
   • Augment with unlabelled data that retains minimal leave-one-out error
   • Thus, we have a property/metric for deciding what unlabelled data to utilize
   • Should improve self-consistency of overall learner over time, without sacrificing
   • Underlying Assumption (Caveat): Training data is highly self-consistent and generalizes well. Highly sensitive to training data, since minutiae will be magnified.

Joachims Method

Graph conceptualization of our data

1. Nodes are data points
2. Edges are similarities
3. A is the adjacency matrix given by:
4. Goal: Find largest y for y^TAy
5. At solution y*:
   • Let G^- be the set of nodes where y_i=-1
   • Let G⁺ be the set of nodes where y_i=1
   • cut(G⁺,G^-) = Sum of all edge weights across the cut.
6. Amounts to s-t mincut, where we are minimizing the sum of the edge weights cut through

Joachims Method

Spectral Graph Transducer (SGT)

1. Compute diagonal degree matrix B s.t. (b_ii) = Sum_j A_ij
2. Compute Laplacian L = B - A (or normalized Laplacian L = B^-1(B-A)
3. Compute the smallest 2 to d+1 eigenvalues and eigenvectors of L; store them in D and V, respectively
4. To normalize the spectrum of the graph, replace eigenvals in D with a monotonically increasing function (e.g., D_ii = i²
5. For each new training set:
   

Joachims Method

Evaluation

Task	SGT	kNN	TSVM	SVM
Optdigits	83.4	62.4	61.5	61.6
Reuters	57	46.7	51.5	49.1
Isolet	55.4	47.4	-	46.3
Adult	54.5	46	47.3	46.2
Ionosphere	79.6	76.7	80.6	80.6