A classifier training system trains unified classifiers for categorizing videos representing different categories of a category graph. The unified classifiers unify the outputs of a number of separate initial classifiers trained from disparate subsets of a training set of media items. The training process divides the training set into a number of bags, and applies a boosting algorithm to the bags, thus enhancing the accuracy of the unified classifiers.