Learning category classifiers for a video corpus

• US 8,819,024 B1
• Filed: 11/19/2010
• Issued: 08/26/2014
• Est. Priority Date: 11/19/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Toderici, George, Aradhye, Hrishikesh, Pasca, Alexandru Marius, Sbaiz, Luciano, Yagnik, Jay
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US12/950,955
• Time in Patent Office: 1,376 Days
• Field of Search: None
• US Class Current: 707/740
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• 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 learns classifiers for categories by combining data from a category-instance repository comprising relationships between categories and more specific instances of those categories with a set of video classifiers for different concepts. The category-instance repository is derived from the domain of textual documents, such as web pages, and the concept classifiers are derived from the domain of video. Taken together, the category-instance repository and the concept classifiers provide sufficient data for obtaining accurate classifiers for categories that encompass other lower-level concepts, where the categories and their classifiers may not be obtainable solely from the video domain.

Claims

1. A computer-implemented method for determining category classifiers applicable to videos of a digital video repository, the method comprising:

accessing a category-instance repository comprising relationships between categories and instances of categories, the category-instance repository derived from a corpus of documents comprising textual portions, the derivation comprising computing strengths for relationships between categories and instances based at least in part on frequencies of co-occurrence of the categories and instances over the corpus of documents;

accessing a set of video concept classifiers derived from the videos and associated with concepts derived from textual metadata of the videos of the digital video repository;

computing consistency scores for a plurality of the categories based at least in part on scores obtained from video concept classifiers associated with concepts corresponding to the instances of the plurality of categories;

selectively removing categories of the category-instance repository based at least in part on whether the computed consistency scores indicate a threshold level of inconsistency; and

determining, for each category of a plurality of the categories not removed, a category classifier based at least in part on the video concept classifiers of concepts associated with the category, the determined category classifier when applied to a video producing a score indicating whether the video represents the category for which the category classifier was determined.

2. The computer-implemented method of claim 1, further comprising removing instances of categories, responsive to the instances not corresponding to any of the concepts.

3. The computer-implemented method of claim 1, wherein the consistency scores are median average deviation (MAD) scores computed from the scores obtained from the video concept classifiers.

4. The computer-implemented method of claim 1, wherein the selectively removing the categories comprises:

computing, for each of a plurality of the instances, a set of top categories for the instance; and

removing a category responsive at least in part to there being fewer than some minimum threshold number of instances for which the category is in the instance'"'"'s set of top categories or there being more than some maximum threshold number of instances for which the category is in the instance'"'"'s set of top categories.

5. The computer-implemented method of claim 1, wherein the accessing the category-instance repository comprises:

storing a set of textual patterns indicating a category-instance relationship between a portion of text corresponding to a category and a portion of text corresponding to an instance;

applying the textual patterns over the corpus of documents, thereby identifying a set of category-instance relationships;

and

retaining, as the categories and instances of the category-instance repository, the categories and instances having relationships with computed strengths of at least some predetermined threshold value.

6. The computer-implemented method of claim 5, wherein computing a strength for a category-instance relationship comprises:

computing a number of distinct patterns for which there was a relationship of the category and the instance over the corpus of documents.

7. The computer-implemented method of claim 1, further comprising:

applying one of the determined category classifiers to one of the videos, thereby obtaining a score; and

responsive to the obtained score indicating that the video represents the category, adding a textual representation of the category to the textual metadata of the one of the videos.

8. The computer-implemented method of claim 1, wherein the accessing the set of video concept classifiers comprises:

storing a set of concepts derived from textual metadata of the videos;

initializing a set of candidate classifiers, each candidate classifier associated with one of the concepts corresponding to the video concept classifiers;

extracting features from the videos, including a set of training features from a training set of the videos and a set of validation features from a validation set of the videos;

iteratively learning accurate classifiers by iteratively performing the steps of;

training the candidate classifiers based at least in part on the set of training features;

determining which of the trained candidate classifiers accurately classify videos, based at least in part on application of the trained candidate classifiers to the set of validation features;

applying the candidate classifiers determined to be accurate to ones of the features, thereby obtaining a set of scores, and

adding the set of scores to the set of training features; and

storing, as the video concept classifiers, the candidate classifiers determined to be accurate.

9. A non-transitory computer-readable storage medium having executable computer program instructions embodied therein for determining category classifiers applicable to digital media items of a digital media repository, actions of the computer program instructions comprising:

accessing a category-instance repository comprising relationships between categories and instances of categories, the category-instance repository derived from a corpus of documents comprising textual portions, the derivation comprising computing strengths for relationships between categories and instances based at least in part on frequencies of co-occurrence of the categories and instances over the corpus of documents;

accessing a set of media item concept classifiers derived from the media items and associated with concepts derived from textual metadata of the digital media items in the digital media repository;

computing consistency scores for a plurality of the categories based at least in part on scores obtained from media item concept classifiers associated with concepts corresponding to the instances of the plurality of categories;

selectively removing the categories of the category-instance repository based at least in part whether the computed consistency scores indicate a threshold level of inconsistency; and

determining, for each category of a plurality of the categories not removed, a category classifier based at least in part on the media item concept classifiers of concepts associated with the category, the determined category classifier when applied to a media item producing a score indicating whether the media item represents the category for which the category classifier was determined.

10. The non-transitory computer-readable storage medium of claim 9, wherein the consistency scores are median average deviation (MAD) scores computed from the concept scores.

11. The non-transitory computer-readable storage medium of claim 9, wherein the selectively removing the categories comprises:

computing, for each of a plurality of the instances, a set of top categories for the instance; and

removing a category responsive at least in part to there being fewer than some minimum threshold number of instances for which the category is in the instance'"'"'s set of top categories or there being more than some maximum threshold number of instances for which the category is in the instance'"'"'s set of top categories.

12. The non-transitory computer-readable storage medium of claim 9, wherein the accessing the category-instance repository comprises:

storing a set of textual patterns indicating a category-instance relationship between a portion of text corresponding to a category and a portion of text corresponding to an instance;

applying the textual patterns over the corpus of documents, thereby identifying a set of category-instance relationships;

and

retaining, as the categories and instances of the category-instance repository, the categories and instances having relationships with computed strengths of at least some predetermined threshold value.

13. The non-transitory computer-readable storage medium of claim 12, wherein computing a strength for a category-instance relationship comprises:

computing a number of distinct patterns for which there was a relationship of the category and the instance over the corpus of documents.

14. The non-transitory computer-readable storage medium of claim 9, the actions of the computer program instructions further comprising:

applying one of the determined category classifiers to one of the media items, thereby obtaining a score; and

responsive to the obtained score indicating that the media item represents the category, adding a textual representation of the category to the textual metadata of the one of the media items.

15. The non-transitory computer-readable storage medium of claim 9, wherein the accessing the set of media item concept classifiers comprises:

storing a set of concepts derived from textual metadata of the media items;

initializing a set of candidate classifiers, each candidate classifier associated with one of the concepts corresponding to the media item concept classifiers;

extracting features from the media items, including a set of training features from a training set of the media items and a set of validation features from a validation set of the media items;

iteratively learning accurate classifiers by iteratively performing the steps of;

training the candidate classifiers based at least in part on the set of training features;

determining which of the trained candidate classifiers accurately classify media items, based at least in part on application of the trained candidate classifiers to the set of validation features;

applying the candidate classifiers determined to be accurate to ones of the features, thereby obtaining a set of scores, and

adding the set of scores to the set of training features; and

storing, as the media item concept classifiers, the candidate classifiers determined to be accurate.

16. A computer system for determining category classifiers applicable to videos of a digital video repository, the system comprising:

a computer processor; and

a computer program executable by the computer processor and performing actions comprising;

creating a category-instance repository comprising relationships between categories and instances of categories, the creating comprising;

applying textual patterns over a corpus of documents comprising textual portions, and

computing strengths for category-instance relationships based at least in part on frequencies of co-occurrence of the categories and instances;

training a set of video concept classifiers on the videos and on textual metadata associated with the videos, each of a plurality of the classifiers corresponding to a concept derived from the textual metadata;

removing instances of categories, responsive to the instances not corresponding to any of the concepts;

filtering the categories of the category-instance repository based on the concepts associated with the video concept classifiers to remove categories that are not likely to be accurately recognized in videos;

removing inconsistent categories by;

identifying, as video concept classifiers associated with a category, video concept classifiers of concepts with labels corresponding to labels of the instances of the category;

applying the video concept classifiers associated with the category to a video, thereby obtaining concept scores;

computing a consistency score for the category based at least in part on the concept scores; and

removing the category responsive to the computed consistency score indicating some threshold level of inconsistency; and

determining, for each of a plurality of the categories, a category classifier based at least in part on the video concept classifiers of concepts associated with the category.

17. The system of claim 16, the actions further comprising:

applying one of the determined category classifiers to one of the videos, thereby obtaining a score; and

responsive to the obtained score indicating that the video represents the category, adding a textual representation of the category to the textual metadata of the video.

18. A computer-implemented method comprising:

accessing a category-instance repository comprising relationships between categories and instances of categories, the category-instance repository derived from a corpus of documents comprising textual portions, the derivation comprising computing strengths for relationships between categories and instances based at least in part on frequencies of co-occurrence of the categories and instances over the corpus of documents;

accessing a set of media item concept classifiers derived from media items and associated with concepts derived from textual metadata of the media items;

computing consistency scores for a plurality of the categories based at least in part on scores obtained from media item concept classifiers associated with concepts corresponding to the instances of the plurality of categories;

selectively removing the categories of the category-instance repository based at least in part whether the computed consistency scores indicate a threshold level of inconsistency; and

determining, for each category of a plurality of the categories not removed, a category classifier based at least in part on the media item concept classifiers associated with concepts that are associated with the category, the determined category classifier when applied to a media item producing a score indicating whether the media item represents the category for which the category classifier was determined.

19. The computer-implemented method of claim 18, further comprising identifying the concepts that are associated with a category by identifying concepts that correspond to the instances of the category.