Classifier and Technique to use for large number of categories 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 .
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!