9. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein for training classifiers for video categories, actions of the instructions comprising: storing a set of categories as a graph of category nodes, each node corresponding to one of the categories; accessing a first set of training items comprising media items of a first content type, each media item authoritatively labeled as representing one or more of the categories; accessing a second set of unlabeled media items not authoritatively labeled; automatically labeling ones of the unlabeled media items responsive to an observed relationship between ones of the labeled media items and ones of the second set, thereby producing a supplemental set of training items, the supplemental set of training items comprising a plurality of subsets, each subset identified using a different technique, and wherein each of a plurality of the categories has, for each of the plurality of subsets, at least one associated initial classifier trained from the subset; forming a training set comprising the first set and the supplemental set; for each of a plurality of the categories, training an initial classifier for the category based at least in part on the media items of the first set and on the media items of the supplemental set, the initial classifier when applied to a media item producing a score measuring how strongly the media item represents the category associated with the initial classifier, thereby producing a set of initial classifiers; producing a plurality of scores by applying the initial classifiers to the media items of the first set of training items; and training, for each of the plurality of categories, a unified classifier based at least in part on the plurality of scores, the unified classifier when applied to a video producing a score representing how strongly the video represents the category associated with the unified classifier, wherein the training uses a graph-based statistical learning algorithm that relates the scores associated with neighboring nodes of the category graph.
9. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein for training classifiers for video categories, actions of the instructions comprising: storing a set of categories as a graph of category nodes, each node corresponding to one of the categories; accessing a first set of training items comprising media items of a first content type, each media item authoritatively labeled as representing one or more of the categories; accessing a second set of unlabeled media items not authoritatively labeled; automatically labeling ones of the unlabeled media items responsive to an observed relationship between ones of the labeled media items and ones of the second set, thereby producing a supplemental set of training items, the supplemental set of training items comprising a plurality of subsets, each subset identified using a different technique, and wherein each of a plurality of the categories has, for each of the plurality of subsets, at least one associated initial classifier trained from the subset; forming a training set comprising the first set and the supplemental set; for each of a plurality of the categories, training an initial classifier for the category based at least in part on the media items of the first set and on the media items of the supplemental set, the initial classifier when applied to a media item producing a score measuring how strongly the media item represents the category associated with the initial classifier, thereby producing a set of initial classifiers; producing a plurality of scores by applying the initial classifiers to the media items of the first set of training items; and training, for each of the plurality of categories, a unified classifier based at least in part on the plurality of scores, the unified classifier when applied to a video producing a score representing how strongly the video represents the category associated with the unified classifier, wherein the training uses a graph-based statistical learning algorithm that relates the scores associated with neighboring nodes of the category graph. 19. The non-transitory computer-readable storage medium of claim 9 , the actions further comprising: applying the unified classifiers to a first video, thereby obtaining a plurality of scores, each score associated with a category of the set of categories; responsive at least in part to determining that a first one of the scores is greater than a first threshold, automatically labeling the video with the category associated with the first score.