Extremely large class set for support vector machine (SVM) classification For a problem where I have tens of thousands of different classes, wouldn't it be very inefficient to use the typical multiclass methods? If I were to do one vs all, wouldn't that mean that I have would have to run through every individual classes before determining if a new set of data belongs to a certain class? That would be computationally very slow.
Is there a way to get around this? Should I even use SVM's when it gets to such a size?
 A: I would use the DAGSVM approach, which constructs a tree of pairwise classifiers.  If you have only 100 patterns per class, but tens of thousands of classes, a lot of the pairwise classifiers will have no training data and hence not every possible pairwise classifier will need to be constructed.
However, more importantly, it is hard to consider a problem with such a large number of classes, where the classification is not in some sense hierarchical.  A better approach would be to first construct a classifier to classify each pattern into broad categories (representing a set of related classes) and then iteratively refine patterns withing each broad category to identify the finer distinctions between classes.
A: Have a look a Vowpal Wabbit. It's an implementation of Stochasic Gradient Decent, which is very efficient for large scale datasets. If you choose the right parameters it can mimic a SVM (hinge-loss). It also includes a reduction called Error-Correcting Tournaments, which is quite efficient for multiple classes.
A: There are classification models that are inherently multiclass, without error-correcting codes or one-vs-rest. Some popular ones are Neural Networks, Linear Discriminant Analysis, Random Forests, Naive Bayes and kNN. The training time usually goes up a little, but it's far more efficient than one-vs-rest classification. There's a multiclass formulation of structural SVM, that worth mentioning. Though I haven't used it myself.
