Cluster-based video classification

• US 8,954,358 B1
• Filed: 11/03/2011
• Issued: 02/10/2015
• Est. Priority Date: 11/03/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhang, John, Leung, Thomas, Song, Yang
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US13/288,874
• Time in Patent Office: 1,195 Days
• Field of Search: 706/12, 382/225
• US Class Current: 706/12
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data
• CPC Class Codes: G06V 10/84 using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49

Abstract

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 takes into account the relationships that exist between the various categories of the category graph by relating scores associated with related categories, thus enhancing the accuracy of the unified classifiers.

Claims

1. A method, executed by a computer system, of training a classifier for a video category, the method comprising:

accessing a training set of items for a category, the training set comprising a first set of videos labeled with the category;

accessing a second set of unlabeled videos not labeled with the category;

forming a cluster for the category, the cluster comprising labeled videos from the training set;

generating a supplemental training set for the category, the supplemental training set comprising the first set of videos labeled with the category and a subset of the second set of unlabeled videos not labeled with the category, generating the supplemental training set comprising;

adding to the cluster unlabeled videos from the second set that have been co-watched with one or more labeled videos in the cluster by adding the unlabeled videos to nodes of a graph representing the cluster for the category, the nodes having edges connecting with nodes of videos that are co-watched with the added unlabeled videos and the edges having weights based on the co-watch relationships;

determining cluster scores for the unlabeled videos added to the cluster responsive to the weights of the edges, the cluster scores representing likelihoods that the unlabeled videos belong to the category and propagated from the labeled videos to the unlabeled videos; and

pruning by removing an unlabeled video from the cluster if the cluster score of the unlabeled video is outside a threshold;

training a classifier for the category using the supplemental training set for the category; and

storing the classifier.

2. The method of claim 1, wherein generating the supplemental training set comprises iteratively performing the adding, determining, and pruning steps on different subsets of the second set of unlabeled videos.

3. The method of claim 1, wherein the cluster score of a video is influenced by a count of how many other videos in the cluster have been co-watched with the video.

4. The method of claim 1, wherein training the classifier comprises applying an initial classifier for the category to a video in the supplemental training set to generate a score that measures how strongly the video represents the category.

5. The method of claim 1, wherein the cluster score of a video is influenced by a number of times the video was co-watched with other videos in the cluster, and the cluster scores of the other videos in the cluster that have been co-watched with the video.

6. The method of claim 1, wherein generating the supplemental training set further comprises:

providing a label for the category as a query to a video search engine;

receiving videos from the video search engine in response to the query;

labeling the received videos with the label provided to the video search engine; and

adding the labeled received videos to the training set of items for the category.

7. The method of claim 1, wherein the supplemental training set for the category comprises a plurality of subsets of videos, each subset identified using a different technique.

8. The method of claim 1, wherein the training set further comprises a set of textual documents authoritatively labeled as representing the category.

9. The method of claim 1, wherein at least a portion of the first set of labeled videos are authoritatively labeled by a human category expert.

10. The method of claim 1, further comprising:

applying the classifier to an unlabeled video not within the supplemental training set to produce a score, the score associated with the category; and

responsive at least in part to determining that the score is greater than a first threshold, automatically labeling the video not within the supplemental training set with the category.

11. The method of claim 1, wherein the cluster score for a node representing an unlabeled video is determined responsive to a sum of weights of incident edges to the node.

12. A system for training a classifier for a video category, the system comprising:

a non-transitory computer-readable storage medium having executable computer program instructions embodied therein; and

a computer processor, the computer processor configured to execute the computer program instructions to;

access a training set of items for a category, the training set comprising a first set of videos labeled with the category;

access a second set of unlabeled videos not labeled with the category;

form a cluster for the category, the cluster comprising labeled videos from the training set;

generate a supplemental training set for the category, the supplemental training set comprising the first set of videos labeled with the category and a subset of the second set of unlabeled videos not labeled with the category, generating the supplemental training set comprising;

adding to the cluster unlabeled videos from the second set that have been co-watched with one or more labeled videos in the cluster by adding the unlabeled videos to nodes of a graph representing the cluster for the category, the nodes having edges connecting with nodes of videos that are co-watched with the added unlabeled videos and the edges having weights based on the co-watch relationships;

determining cluster scores for the unlabeled videos added to the cluster responsive to the weights of the edges, the cluster scores representing likelihoods that the unlabeled videos belong to the category and propagated from the labeled videos to the unlabeled videos; and

pruning by removing an unlabeled video from the cluster if the cluster score of the unlabeled video is outside a threshold;

train a classifier for the category using the supplemental training set for the category; and

store the classifier.

13. The system of claim 12, wherein generating the supplemental training set comprises iteratively performing the adding, determining, and pruning steps on different subsets of the second set of unlabeled videos.

14. The system of claim 12, wherein the cluster score of a video is influenced by a count of how many other videos in the cluster have been co-watched with the video.

15. The system of claim 12, wherein training the classifier comprises applying an initial classifier for the category to a video in the supplemental training set to generate a score that measures how strongly the video represents the category.

16. The system of claim 12, wherein the cluster score of a video is influenced by a number of times the video was co-watched with other videos in the cluster, and the cluster scores of the other videos in the cluster that have been co-watched with the video.

17. The system of claim 12, wherein generating the supplemental training set further comprises:

providing a label for the category as a query to a video search engine;

receiving videos from the video search engine in response to the query;

labeling the received videos with the label provided to the video search engine; and

adding the labeled received videos to the training set of items for the category.

18. The system of claim 12, wherein the supplemental training set for the category comprises a plurality of subsets of videos, each subset identified using a different technique.

19. The system of claim 12, wherein the training set further comprises a set of textual documents authoritatively labeled as representing the category.

20. The system of claim 12, wherein at least a portion of the first set of labeled videos are authoritatively labeled by a human category expert.

21. The system of claim 12, the computer processor further configured to:

apply the classifier to an unlabeled video not within the supplemental training set to produce a score, the score associated with the category; and

responsive at least in part to determining that the score is greater than a first threshold, automatically label the video not within the supplemental training set with the category.

22. The system of claim 12, wherein the cluster score for a node representing an unlabeled video is determined responsive to a sum of weights of incident edges to the node.

23. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein for training a classifier for a video category, actions of the computer program instructions comprising:

accessing a training set of items for a category, the training set comprising a first set of videos labeled with the category;

accessing a second set of unlabeled videos not labeled with the category;

forming a cluster for the category, the cluster comprising labeled videos from the training set;

generating a supplemental training set for the category, the supplemental training set comprising the first set of videos labeled with the category and a subset of the second set of unlabeled videos not labeled with the category, generating the supplemental training set comprising;

adding to the cluster unlabeled videos from the second set that have been co-watched with one or more labeled videos in the cluster by adding the unlabeled videos to nodes of a graph representing the cluster for the category, the nodes having edges connecting with nodes of videos that are co-watched with the added unlabeled videos and the edges having weights based on the co-watch relationships;

determining cluster scores for the unlabeled videos added to the cluster responsive to the weights of the edges, the cluster scores representing likelihoods that the unlabeled videos belong to the category and propagated from the labeled videos to the unlabeled videos; and

pruning by removing an unlabeled video from the cluster if the cluster score of the unlabeled video is outside a threshold;

training a classifier for the category using the supplemental training set for the category; and

storing the classifier.

24. The non-transitory computer-readable storage medium of claim 23, wherein generating the supplemental training set comprises iteratively performing the adding, determining, and pruning steps on different subsets of the second set of unlabeled videos.

25. The non-transitory computer-readable storage medium of claim 23, wherein the cluster score of a video is influenced by a count of how many other videos in the cluster have been co-watched with the video.

26. The non-transitory computer-readable storage medium of claim 23, wherein training the classifier comprises applying an initial classifier for the category to a video in the supplemental training set to generate a score that measures how strongly the video represents the category.

27. The non-transitory computer-readable storage medium of claim 23, wherein the cluster score of a video is influenced by a number of times the video was co-watched with other videos in the cluster, and the cluster scores of the other videos in the cluster that have been co-watched with the video.

28. The non-transitory computer-readable storage medium of claim 23, wherein generating the supplemental training set further comprises:

providing a label for the category as a query to a video search engine;

receiving videos from the video search engine in response to the query;

labeling the received videos with the label provided to the video search engine; and

adding the labeled received videos to the training set of items for the category.

29. The non-transitory computer-readable storage medium of claim 23, wherein the supplemental training set for the category comprises a plurality of subsets of videos, each subset identified using a different technique.

30. The non-transitory computer-readable storage medium of claim 23, wherein the training set further comprises a set of textual documents authoritatively labeled as representing the category.

31. The non-transitory computer-readable storage medium of claim 23, wherein at least a portion of the first set of labeled videos are authoritatively labeled by a human category expert.

32. The non-transitory computer-readable storage medium of claim 23, further comprising:

applying the classifier to an unlabeled video not within the supplemental training set to produce a score, the score associated with the category; and

responsive at least in part to determining that the score is greater than a first threshold, automatically labeling the video not within the supplemental training set with the category.

33. The non-transitory computer-readable storage medium of claim 23, wherein the cluster score for a node representing an unlabeled video is determined responsive to a sum of weights of incident edges to the node.