Notation

discrete prediction:

continuous prediction:

• 
  • Think of the sign as the label
  • Think of the abs value as the confidence

Loss functions

• zero-one loss: 1 iff the answer is correct
• hinge loss: -- i.e., if the answer is right, then 0; otherwise, the magnitude of f(x).
• exponential loss
• log loss
• etc.

Framework

• initialize classifier
• for each round t
  • recieve input instance
  • output prediciton
  • get feedback
  • compute loss
  • update prediction rule

goal:

• minimize cumulative loss

Linear classifiers

Define features and weights:

constrain:

prediction:

(Discussion of SVM-type stuff -- margins, etc.)

Why online learing?

• Fast
• Memory efficient - process one example at a time
• Simple to implement
• Formal guarantees – Mistake bounds
• Online to Batch conversions
• No statistical assumptions
• Adaptive
• but.. Not as good as a well designed batch algorithms

Update rules: we want an algorithm that maps .

Using a weight-based model, we're mapping from

(discussion of some simple update rules -- perceptron, etc)

Perceptron is basically minimizing the zero-one loss; but we can design variants that minimize other loss functions.

Problems with perceptron:

• Margin of examples is ignored by update
• Same update for separable case and inseparable case

Passive-Agressive Approach

• minimize a loss function (maximize margin)
• basic algorithm does not work in inseperable case
• Enforce a minimal non-zero margin after the update (cf perceptron, which does not guarantee margin after approach)
• In particular :
  • If the , then do nothing
  • If the , update such that the margin after the update is enforced to be 1.

Define a dual space, to be the space of weight vectors. I.e., a given point in this "version space" identifies a single classifier.

For a given training sample, we can determine the subspace of this dual space that will classify it correctly. I.e., the set of all models that get that sample correct will be in that region. (We can enforce a margin of 1 by finding the subspace of this dual space that identifies the sample correctly with a margin of at least one.)

So we start with a point in the version space. Then, for each new training sample, we find the line $`1 le y_t(w_t cdot x_t$`, which seperates the space into classifier models that classify the training sample with an acceptable margin, and those that don't. For each new training sample, we project onto this line.

Agressive step update:

such that

This can be solved analytically. If the constraint is already satisfied, then the solution is trivial: stay where we are. If the constraint is not satisfied, then we choose the closest point that does satisfy it. I.e., make the minimal change to the model that will allow us to get the right solution with an acceptable margin.

Comparing PA with perceptron: in both cases we have: . For the perceptron, is basically the zero-one loss function. For the PA, is proportional to the hinge loss function (it's scaled by ).

So there appears to be a tight connection between the algorithm update and the loss function we're optimizing on.

Complex Learning Tasks

• binary classification
• n-way classification, no ordering or relation
• n-way classification, ordered (eg rate movies 1-5)
• n-way classification, hierarchical relations between labels
• n-way classification, complex tree relation between labels
• multi-class classification (either as ranking output, or set output)
• sequence classification (eg np chunking)
• sentence compression -- deleting selected words
• alignment
• complex structure outputs -- eg parse trees, feature structures, dependency parsing

For these tasks..

• how do we want to evaluate? what's a good loss function?

Challenges:

• we can't just eliminate the wrong answer
• structure over labels
• non-trivial loss functions
• complex input/output relation
• non-trivial output values
• interactions between different sub-decisions
• wide range of features

conventional approach: treat it as a labelling problem. I.e., we're mapping an input sequence to an output sequence , where we might have a many-to-one relation between x's and y's. (This isn't general enough for all the problems we want to do, but it's a start.)

Outline of a Solution

We need:

• a quantitative evaluation of predictions. I.e., a loss function. This will be application dependent.
• a class of models. I.e., a set of labeling functions. This generalizes linear classification.
• A learning algorithm. We'll look at extending both the perceptron and the passive-aggressive algorithms.