Off the shelf tool for multi-label classification I have a data set that has 10k documents, each of which is mapped to one and only one of 4k categories. This forms my training set. 
My requirement is that when a new, unseen document comes in, I need to be able to identify all the categories (from among the 4k categories) to which it belongs. 
What is the best way to go about doing this? My problem conforms to what's generally known as multi-label classification in the literature, and I see plenty of papers, but no readily available software. I was hoping to know if anyone is aware of any off-the-shelf tools that would do this task.
Thanks in advance.
Update 1: Based on some comments below I am updating my question. Although I have   4k categories and only 10k documents, the distribution of these documents into categories is highly skewed - in other words, there are a small number of categories that have most of the training documents. I am OK with retaining categories that have sufficient training data, and throwing away the other categories if need be. The bigger problem is identifying all the categories of unseen document. 
 A: As @mbq suggests, a battery of binary classifiers is a good place to start.  Ridge regression classifiers work pretty well on text classification problems (choose the ridge parameter via leave-one-out cross-validation.  If training time is not an issue, also use the bootstrap as a further protection against over-fitting; the committee of boostrap classifiers can be amalgamated into one, so it doesn't have a computational cost at runtime).
However, as there are 4K classes and only 10K samples, it will probably be necessary to look at the hierarchy of classes and try to predict whether the page fits into broad categories first.
A: About multilabel classification, the baseline (but usually quite good) approach is just to make a battery of binary classifiers, each trained to recognize one class versus all other, use them all on each sample and combine their answers.
This is trivial to implement, so almost any tool will do.
However, you have other problem -- an ultrapoor training set. 10k samples in 4k classes gives 2-3 examples per class -- this is almost nothing; I can at most imagine some embarrassing 1-NN method in this setting.
A: Try using R.  You can use the factor data type to store what you are calling each document's "label."
Before you use any predictive functions, you'll have to calculate some quantitative attributes about each document.  This is going to depend on the nature of your problem, but check out the Natural Language Processing section on CRAN for help with this step.
Once you've converted your documents into a dataframe with one row per document, and variables representing that document's classification, as well as covariates describing the document's content and metadata, you can start building predictive models.  You might start with linear discriminant analysis.
With 4k classes and over 10k documents, I think it is going to be difficult to develop a good classifier.  See if any of the authors you've been reading have written packages for R.
A: One of my homework assignments this semester was exactly to do his (well, not exactly, most of it was already implemented and we had to do some improvements and experimentation).
You can read the details here.
Anyway, whatever method you choose to use, I suggest to take a look at Weka.
 Most probably the classifier you are looking for is already implemented there.
A: In general, you'll need to specify what make each category unique to be able to choose which classifier to use. In a silly example, if categories are based on the size of the document... you got the idea.
One good classifier that I used in this task was using the Normalized Compression Distance (NCD). It measures how close two documents are using compressors like ZIP. 
For example: you have a document D and you have 10 categories C1, C2... C10. In each category you have one example document: C1a in category C1, C2a in category C2...
To verify the document D, you'll concatenate it with C1a and compress, then concatenate D with C2a and compress, and so on. By doing some calculation, you'll end up have NCD measures. Them you attribute it to the category that gave you the minimum NCD value.
The good point is that I'll end up my master degree in two weeks, using NCD as authorship attribution. Got correct attributions > 95% when dealing with 20 classes, > 55% when dealing with 100 classes, all of portuguese documents from newspapers. The bad point is that it's written in portuguese...
A: I haven't used them yet, but Mulan and Meka are multi-label addons for Weka.  Meka seems more off the shelf, and includes support for Mulan.
