Classifier and Technique to use for large number of categories

Question

I am designing a scikit learn classifier for a sequence labelling task which has 5000+ categories and training data is at least 80 million and may grow upto an additional 100 million each year. I have already tried with all the categories but it generates classifiers in the order of 100s of GBs binary file. So I think that having one classifier for each category would be helpful and would also help me to fine tune features for each category thereby improving accuracy, but this means 5k+ classifiers for each of these categories. So how to handle this large data requirements and which incremental classifiers to use for this case , considering the fact that I will keep on getting additional training data as well as may discover new categories?

The number of features are about 100+ and due to the sequence labelling task contiguous sequence of training samples share same features values. The feature values are mostly text based and most are categorical with long text based values with large cardinality i.e many features may have huge number of possible values.

The available RAM IS 32gb with 8 core CPU. On a small scale I tried Multinomial NB and linear SGD with sparse matrices which are extremely sparse. Used the scikit learns Dictvectorizer to vectorize the feature dictionary. Also will pandas dataframes help to optimize the overall configuration?

Due to the scale of data involved I have only used about 20% of the data. And the features itself are 56GB of data from the 500MB input data. For the restricted training data, The precision too is very low does not reach above 12% with a very low recall too(1-2%). Have gone through vowpal wabbit and found the SEARN task but it seems that it is now no longer available in the latest version .

Answer 1

As a complement to Jérémie Clos' and AN6U5's answers, there are at least two methods helping to cope with a large number of classes:

• use a hierarchy, like hierarchical softmax. Instead of having a flat list of categories, one builds a tree of them, then on each node predicts if the correct category is on the left or on the right branch.
• do not classify directly, but first learn an embedding into a lower-dimensional space, where instances of the same class should have close representations. A famous example for this is FaceNet (the use case is face recognition) : they embed the image of a face into a 128 dimensional byte vector. The algorithm to learn this embedding is triplet loss (I've heard of magnet loss as well). Then when presented with a new request, compute its representation (a small vector), and look for the closest vectors in the trainset. This is similar to kNN, or to label embedding if each instance belongs to several classes: "Our method consists in embedding high-dimensional sparse labels onto a lower-dimensional dense sphere of unit-normed vectors, and treating the classification problem as a cosine proximity regression problem on this sphere."

The work of http://manikvarma.org/index.html might be relevant to your problem as well.

Alos of potential use: http://jmlr.org/papers/volume15/gupta14a/gupta14a.pdf .

Answer 2

This sounds like a pretty gnarly problem, so a lot of finesse will be needed to solve it. @Jérémie Clos has some good points, but I wanted to add some more general thoughts...

With the size of your problem, you might want to think about a scalable framework like Mahout or H2O rather than scikit-learn, which is an awesome shared memory library, but does have scalability limitations.

With a categorical feature with cardinality of 5000 and 80 million training cases, a uniform distribution will only give you 16,000 training cases for each positive result. However, the distribution probably isn't uniform. I suggest that you eliminate the least common categories until you have thrown out 5% of the data and assess the cardinality of the remaining 95%. This may give you a better clue about how to proceed i.e. what percent of the cardinality remains?

Most multiclass classification algorithms are just lots of binary classifiers that are combined to produce a composite result, so will essentially do the work for you of splitting up the problem, binarizing the data (aka one-hot encoding), and training the classifiers, so you may not need to explicitly perform this splitting step. Two exceptions to this, i.e. classifiers that can handle the multi-class problem intrinsically are decision trees and random forests (Mahout version). I would try both of these and hold them as benchmarks moving forward.

In terms of handling the addition of categories as data is added to the system, you will have to retrain sometimes. This is sometimes referred to as the stability-plasticity dilemma. The best way to handle this is probably only to make predictions on categories that comprise some threshold of the data and throw out the rest as outlier categories that are not powered well enough to predict on e.g. similar to the sanity check I suggest above.

Hope this helps!

Answer 3

So how to handle this large data requirements and which incremental classifiers to use for this case , considering the fact that I will keep on getting additional training data as well as may discover new categories?

I am not familiar with the task you are solving, but have you considered a lazy distance-based learner like k-nn and its variations? It could handle an arbitrary number of categories, learn incrementally and you could keep your model small-ish by using one of the case base maintenance algorithms out there. As for learning new categories, you could use an outlier detection algorithm to see when a new test example doesn't fit in its category (i.e. when it significantly reduces its intra-class consistency).