How can I perform multi-label classification if many labels are missing? I have a large set of documents, usually 500-2,000 words each, and for several different labels, there are about 20-100 samples with those labels, and hundreds to millions more that should be labeled but do not have that label. Over time, I expect new labels to be created and new documents to be added to the data set, although relatively few old labels added to any documents. It is possible that some documents will have many labels or possibly no labels. It is also possible for a label to be a subclass of another label, though not manually indicated.

I have a keyword tagging system in place that utilizes TF-IDF metrics to extract ngrams from the documents, which is my current feature set from them.

My initial thought is to use Naive Bayes classifiers (one for each label) and perform ROC analysis to see how well it classifies the category. However, if, say, 5% of the data should actually be labeled with Label A, and the amount of data supplied with Label A amounts to 1% of the data, then I would expect an ideal false discovery rate of 80%. On top of that, since the prior distribution is unknown, dealing with this issue is even more difficult.

Another idea I had is to use the vectors of word/ngram counts and look at the distribution of the cosine similarities of the documents within the sample and use a simple one-sided significance test with p-values to determine if they are similar enough. This relies heavily on the idea that the ngram vectors for each label are dissimilar enough to consider this form of hypothesis testing. A big problem with this is that I am heavily relying on the assumption that similarity is a highly discriminative metric, and because labels can be extremely unbalanced (by up to 5 orders of magnitude), I may need to employ additional methods, such as limiting the number of labels (perhaps by only taking the top N labels by p-value).

The training portion of the algorithm does not need to be extremely fast, but the labeling portion should be very quick once the document is parsed/tokenized.

There is a greater penalty for mislabeling a document than leaving it unlabeled, but future, human-feedback data may be provided to indicate incorrect labels. I will not have access to anything of the sort in the meantime, though.
This is called Automatic Document/Text Categorization (a lecture note on this). There're some approaches you can take, such as ATC with semi-supervised learning or building one-vs-all classifier and labeling a new test sample with a new label when all classifiers reject it. This was discussed here as well.