Pre-meeting comment - Dhananjay

Related paper - Ultraconservative Online Algorithms for Multiclass Problems.
Koby Crammar and Yoram Singer, JMLR 2003

The paper proposes a class of algorithms for multiclass classification. The intuition is to maintain one prototype vector per class. Given an input instance, the algorithm computes a similarity score. The instance is assigned the class with the highest similarity. The prototypes are iteratively developed as a part of training. These algorithms are classified as ultraconservative algorithms in the sense that only those prototypes are updated for which the similarity scores are greater than the correct label.

Briefly, for each instance that is incorrectly classified, an error set consisting of labels for which the similarity score is greater than the correct instance is constructed. Each prototype (corresponding to the label in the error set) is reduced by a factor of the input instance. This is equivalent of taking this prototype vector away (more dissimilar) from the input vector. The prototype of the correct label is aligned more towards the input vector by adding the instance. All the factors are chosen such that they add up to 0.

Using this setup, the authors go on to show a class of additive algorithms and multiplicative algorithms. For each step, an optimization problem is constructed such that the norm of the prototype vector matrix is minimized. The variables are the factors by which the prototype vectors are adjusted.