A tag learning module trains video classifiers associated with a stored set of tags derived from textual metadata of a plurality of videos, the training based on features extracted from training videos. Each of the tag classifiers is comprised of a plurality of subtag classifiers relating to latent subtags within the tag. The latent subtags can be initialized by clustering cowatch information relating to the videos for a tag. After initialization to identify subtag groups, a subtag classifier can be trained on features extracted from each subtag group. Iterative training of the subtag classifiers can be accomplished by identifying the latent subtags of a training set using the subtag classifiers, then iteratively improving the subtag classifiers by training each subtag classifier with the videos designated as conforming closest to that subtag.