Patent Publication Number: US-8533134-B1

Title: Graph-based fusion for video classification

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The application claims the benefit of Provisional Application No. 61/262,125, filed on Nov. 17, 2009, which is incorporated herein by reference. 
    
    
     BACKGROUND 
     1. Field of Art 
     The present invention generally relates to the field of digital video, and more specifically, to methods of generating accurate classifiers for identifying categories of a video. 
     2. Background of the Invention 
     Video hosting services, such as YOUTUBE™, have become an increasingly popular way of sharing and viewing digital videos, with users contributing tens of millions of videos each year. Accurate categorization of a video is of great value in such systems, permitting users to search for videos corresponding to given categories, and the video hosting service to more accurately match videos with relevant advertising, and the like. 
     However, the descriptive metadata information provided by the user who contributes a video often does not result in the correct categorization of the video. For example, for a set of predetermined categories including categories such as “Sports,” “Basketball,” “Tennis,” and the like, a video entitled with the name of a tennis player featured in the video would not in itself directly permit the video to be properly categorized as “Tennis” or “Sports.” 
     Machine learning algorithms can be employed to train a classifier function for a given category (e.g., “Tennis”) that, when applied to features of a video (such as metadata of the video), outputs a measure of the relevance of the video to the category. Then, the trained classifier function for a given category can be applied to a video and the resulting measure of relevance used to determine whether the video is within that category. However, to train a classifier function for a category, most learning algorithms employ supervised learning, which requires as input a training set of videos known a priori to be representative of the category. Further, supervised learning tends to produce more accurate classifier functions when trained on a larger training set, and/or a training set with features that are more useful for categorization purposes. A training set useful for supervised learning can be produced by humans viewing videos and manually categorizing them into different categories, but manual categorization is time-consuming due to the need to watch the entire video, or at least a significant representative portion thereof. Nor can humans efficiently view and label a sufficiently large sample of videos in a video hosting service where tens of thousands of videos are being uploaded every day. Thus, there are typically few pre-categorized videos available for training purposes, and the classifier functions trained using these small training sets are therefore not as effective as could be desired in categorizing the large number of videos that have not already been manually categorized. 
     Additionally, some conventional algorithms that train classifier functions for various categories assume that the categories are independent of each other. When the categories do in fact have some relationship, such as being “parent” or “child” categories to each other, this assumption of category independence fails to capture relationship information that could provide additional accuracy to the trained classifier functions. 
     SUMMARY 
     A classifier training system trains a classifier functions (hereinafter simply “classifiers”) for categorizing videos representing different categories of a category graph. The classifiers are referred to as unified classifiers in that they unify the outputs of a number of separate initial classifiers trained from multiple disparate subsets of a training set of media items. Each unified classifier thus unites different types of training information within a single classifier. The training of a unified classifier takes into account inter-category relationships, which enhances training accuracy. 
     More specifically, the classifier training system begins with some set of pre-determined categories arranged in a graph indicating relationships between categories, wherein nodes in the graph represent categories, and edges between nodes represent relationships between categories. For example, the category graph could include a node for the category “Tennis” with an edge to a node for the parent category “Sports.” The classifier training system further begins with a training set of media items from which the unified classifier is trained. The media items can include—in addition to videos—other types of content, such as web pages and other textual documents, images, sound files, and the like. The training set comprises a first subset of videos, each of which has been previously authoritatively labeled (e.g., by a human expert) as representing one or more of the categories. The classifier training system also begins with one or more other subsets of media items, each set of which can be of a different content type (e.g., web pages rather than videos) or obtained in a different manner (e.g., videos that are automatically inferred to be in the same categories as one of the videos of the first subset because they were “co-watched” along with the first video). 
     For each category, there are multiple initial classifiers, each of which outputs a value indicating whether a given media item represents the initial classifier&#39;s category. The initial classifiers are trained from combinations of the first subset of videos with the other subsets of media items. For example, for each category there could be (1) an initial classifier trained from the textual features of the videos of the first subset and of videos co-watched with the videos of the first subset, and (2) another initial classifier trained from the audiovisual features of these same two subsets. The training of the initial classifiers may be performed by the classifier training system itself, or it may be performed by another system, with the initial classifiers being provided as input to the classifier training system. 
     The initial classifiers for each category are then applied to each media item in the training set to generate scores representing whether (or how strongly) the media item represents the associated categories. For a given media item, these scores—e.g., Boolean or scalar values—form a feature vector describing characteristics of the media items to which they correspond. For example, a given media item there would have a feature vector of M*K scores, one for each of the K categories and the M initial classifiers per category. Thus, features from subsets of the media items with potentially different characteristics are combined within a single feature vector. 
     The scores computed from the initial classifiers as applied to the media items of the training set are provided as input for a fusion process that trains the unified classifiers, one per category. The fusion process learns classifier parameters of a probabilistic graph-based algorithm based on the known category labels of the media items of the training set, on the computed scores, and on the relationships between the categories of the category graph. In one embodiment, the fusion process relates the scores associated with neighboring nodes of the category graph as part of its computations, thus taking into account the inter-category relationships. 
     Once the classifier parameters have been learned as part of the training of the unified classifiers, the unified classifiers can then be applied to an arbitrary video, each unified classifier producing as its output a score for each of the categories that indicates how strongly the video represents that category. 
     In one embodiment, the classifier training system is not limited to learning unified classifiers for digital videos, specifically, but rather can learn unified classifiers for any media object for which meaningful features can be extracted, including images, presentations, text documents, audio files, and the like. 
     The features and advantages described in the specification are not all inclusive and, in particular, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram of a video hosting service in which classifier training can be employed, according to one embodiment. 
         FIG. 2  illustrates the various components of the classifier training subsystem of  FIG. 1 , according to one embodiment. 
         FIG. 3  is a data flow diagram representing the relationships and derivations of the various types of data analyzed and/or produced by the training subsystem, according to one embodiment. 
         FIG. 4  is a data flow diagram representing the inputs and outputs of processes for training and for applying a unified classifier, respectively, according to one embodiment. 
     
    
    
     The figures depict embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein. 
     DETAILED DESCRIPTION 
     System Architecture 
       FIG. 1  is a block diagram of a video hosting service  100  in which classifier training can be employed, according to one embodiment. The video hosting service  100  represents a system such as that of YOUTUBE™ that stores and provides videos to users via client devices  135 . The video hosting service  100  communicates with a plurality of content providers  130  and client devices  135  via a network  140  to facilitate sharing of video content between users. The video hosting service  100  can additionally obtain data from various external websites  125 . The video data from the content providers  130 , and (optionally) the web page or other data from the websites  125 , serves as input data for classifier training performed by the video hosting service  100 . Note that for the sake of clarity  FIG. 1  depicts only one instance of website  125 , content provider  130  and client device  135 , though there could be any number of each. 
     Generally, a user of the content provider device  130  provides video content to the video hosting service  100  and a (usually different) user uses a client device  135  (also referred to simply as “client”) to view that content. In practice, content provider devices  130  may also be used to view content. Additionally, a particular content provider device  130  may be operated by the same entity that operates the video hosting service  100 . 
     The user of the content provider device  130  performs various content provider functions. Content provider functions may include, for example, uploading a video to the video hosting service  100 , editing a video stored by the video hosting service  100 , editing metadata information about a video, or editing content provider preferences associated with a video. 
     A client device  135  is a computing device that executes client software, e.g., a web browser or built-in client application, to connect to the video hosting service  100  via a network  140  and to display videos. The client device  135  might be, for example, a personal computer, a personal digital assistant, a cellular, mobile, or smart phone, a television “set-top box,” or a laptop computer. In some embodiments, the client  135  includes an embedded video player such as, for example, the FLASH player from Adobe Systems, Inc. or any other player adapted for the video file formats used in the video hosting service  100 . 
     Note that the terms “client” and “content provider” as used herein may refer to software providing client and content providing functionality, to hardware devices on which the software executes, or to the entities operating the software and/or hardware, as is apparent from the context in which the terms are used. 
     The website  125  comprises one or more web pages accessible to the video hosting service  100  via the network  140 . The web pages comprise, for example, textual content such as HTML. The website may make available additional types of media content, such as general textual documents, presentations, audio files, image files, and the like. 
     The network  140  is typically the Internet, but may be any network, including but not limited to a LAN, a MAN, a WAN, a mobile wired or wireless network, a private network, or a virtual private network. 
     The video hosting service  100  operates on the video data from the content providers  130  (and, optionally, from the website  125 ) when training video classifiers. The video hosting service includes a front end interface  102 , a video serving module  104 , a video search module  106 , an upload server  108 , and a video repository  116 . Other conventional features, such as firewalls, load balancers, authentication servers, application servers, failover servers, site management tools, and so forth are not shown so as to more clearly illustrate the features of the video hosting service  100 . One example of a suitable service  100  is the YOUTUBE™ website, found at www.youtube.com. Other video hosting sites are known, as well, and can be adapted to operate according to the teachings disclosed herein. 
     In this description, the term “module” refers to computational logic for providing the specified functionality. A module can be implemented in hardware, firmware, and/or software. It will be understood that the named modules described herein represent one embodiment of the present invention, and other embodiments may include other modules. In addition, other embodiments may lack modules described herein and/or distribute the described functionality among the modules in a different manner. Additionally, the functionalities attributed to more than one module can be incorporated into a single module. Where the modules described herein are implemented as software, the module can be implemented as a standalone program, but can also be implemented through other means, for example as part of a larger program, as a plurality of separate programs, or as one or more statically or dynamically linked libraries. In any of these software implementations, the modules are stored on the computer readable persistent storage devices of the service  100 , loaded into memory, and executed by the one or more processors of the service&#39;s computers. The foregoing further applies to components described herein as “servers.” 
     The upload server  108  of the video hosting service  100  receives video content from a content provider  130 . Received content is stored in the video repository  116 . In response to requests from clients  135 , a video serving module  104  provides video data from the video repository  116  to the clients. Clients  135  may also search for videos of interest stored in the video repository  116  using a video search module  106 , such as by entering textual queries containing keywords of interest. The front end interface  102  provides the interface between client  135  and the various components of the video hosting service  100 . 
     The video repository  116  contains a set of videos  117  submitted by content providers  130 . The video repository  116  can contain any number of videos  117 , such as tens of thousands or hundreds of millions. Each of the videos  117  has a unique video identifier that distinguishes it from each of the other videos, such as a textual name (e.g., the string “a91qrx8”), an integer, or any other way of uniquely naming a video. The videos  117  can be packaged in various containers such as AVI, MP4, or MOV, and can be encoded using video codecs such as MPEG-2, MPEG-4, H.264, and the like. In addition to their audiovisual content, the videos  117  further have associated metadata  117 A, e.g., textual metadata such as a title, description, and/or tags provided by a content provider  130  who uploaded the video. 
     The video hosting service  100  further comprises a classifier training subsystem  119  that trains an accurate video classifier for a predetermined set of categories, even in the absence of a large number of labeled videos to use as training examples. The trained classifier can then be applied to a given video to determine which of the categories the video represents. In one embodiment, the classifier training subsystem  119  is part of the video hosting service  100 , as depicted in  FIG. 1 . In another embodiment, the classifier training subsystem  119  is separate from the video hosting service  100 , receiving input from it and providing output to it. The classifier training subsystem  119  is described in greater detail in  FIG. 2 . 
     The service  100  may be implemented using a single computer, or a network of computers, including cloud-based computer implementations. The computers are preferably server class computers including one or more high-performance CPUs and 1 G or more of main memory, as well as 500 Gb to 2 Tb of computer readable, persistent storage, and running an operating system such as LINUX or variants thereof. The operations of the service  100  as described herein can be controlled through either hardware or through computer programs installed in computer storage and executed by the processors of such servers to perform the functions described herein. The service  100  includes other hardware elements necessary for the operations described here, including network interfaces and protocols, input devices for data entry, and output devices for display, printing, or other presentations of data. 
       FIG. 2  illustrates the various components of the classifier training subsystem  119 , according to one embodiment. The classifier training subsystem  119  trains classifiers based in part on a set of categories and on a set of videos that have been previously authoritatively labeled by an authoritative source as representing one or more of the categories. As part of the training process, a module of the classifier training subsystem  119  further identifies additional training sample items, possibly of different media types, for each of the categories in addition to the labeled videos. The different media types for these training items may include—in addition to videos—textual documents such as web pages, audio, and images. Each of the additional samples is identified using one of a set of different techniques, such as identifying co-played videos or identifying web pages authoritatively labeled as representing a particular category. By supplementing the manually labeled videos with these additional training items, possibly including different media types, a training set of significant size can be created even where the manually labeled videos themselves are relatively few in number, thus increasing the accuracy of the trained classifiers. The combination of the labeled videos and the additional training sample items of different media types then serves as a supplemental training set that is provided as input to a classifier training algorithm. The various modules of the classifier training subsystem  119  process the supplemental training set, thereby training initial classifiers that can automatically categorize videos with a certain degree of accuracy. Output of the classifiers is then combined to train unified classifiers with still higher degrees of accuracy. The training of the unified classifiers is done using a graph algorithm that takes into account the structure of the category graph, including the relationships between neighboring categories (e.g., parent or child categories) in the graph. 
     More specifically, the classifier training subsystem  119  stores a predefined category set  205  representing different possible categories that a video could represent, such as “Sports,” “Tennis,” “Gymnastics,” “Arts &amp; Entertainment,” “Movies,” “TV &amp; Video,” and the like. The various categories of the category set  205  have some relationship with one or more other categories in the set, such that the set can be represented as a category graph, each node of the graph being a category, and edges between the nodes representing some relationship between the categories represented by the nodes connected by the edge. In one embodiment, the category set  205  is more specifically a taxonomy in which the categories of the graph are arranged hierarchically as a tree, with categories being more general parents and/or more specialized children of other categories. For instance, referring to the example categories above, “Sports” could be a top-level parent category with child categories “Tennis” and “Gymnastics,” and “Arts &amp; Entertainment” could be another top-level category with child categories “Movies” and “TV &amp; Video.” The child categories may in turn have their own child categories. In general, the taxonomy may have any number of levels of depth. In another embodiment, the category set  205  is non-hierarchical, with the nodes of the graph arbitrarily connected. 
     A category can be represented in various manners as would be appreciated by one of skill in the art, such as a textual label (e.g., the string “Sports”) and an associated unique shorthand numerical identifier (e.g., 1). A video can be said to represent a category if the video contains some semantically understandable representation of the category within the video content itself. For example, a video represents a category “Tennis” if (for instance) there are scenes of a tennis match within the visual content of the video. A video can represent many different categories (e.g., both “Sports” and “News”), but users typically are interested in what may be considered the most salient category for the video. 
     In one embodiment, in order to permit training of classifiers of sufficient accuracy, each of the categories has associated with it some minimum number of training sample items. That is, although there may initially have been some large number of potential categories, the final category set  205  will include only the potential categories that have the minimum number of associated training items. 
     The classifier training subsystem  119  further comprises a training set  220  containing various content items, such as videos and web pages, that can be associated with various ones of the categories. The content items are labeled—either explicitly or implicitly—with one or more of the categories from the category set  205 . The content items, along with their labels, are then used to train classifiers for the various categories with which the content items are associated. 
     The training set  220  comprises a set of authoritatively labeled videos  224 , previously authoritatively labeled as representing one or more categories from the category set  205 . In one embodiment, the videos are manually labeled by one or more human experts trained in the meaning and use of the category set  205 ; this involves the human expert viewing a representative portion of each video and then specifying which categories the video represents based on the portion viewed. In another embodiment, the authoritative labeling is performed by a labeling algorithm that categorizes videos with a high degree of accuracy. In another embodiment, a hybrid approach is used in which videos are initially categorized by a labeling algorithm, with subsequent human review and validation of some (or all) of the labels. In embodiments in which the category set  205  is represented as a taxonomy tree, in which case there will be categories that are leaf nodes of the tree, a video is labeled with the most applicable leaf node category in the taxonomy. For example, a video about tennis is labeled “Tennis,” not “Sports”; the fact that the video also more generally represents sports can be inferred from the fact that “Tennis” is a child category of “Sports” in the taxonomy tree. In one embodiment, the videos which are authoritatively labeled represent a subset of the video repository  116  that was determined to be particularly popular, such as the videos most frequently viewed over a particular recent time period. Thus, in order for a category to have a threshold number associated training items in this embodiment, it must first have a sufficient number of popular videos, and then a minimum number of these popular videos must be authoritatively labeled. In other embodiments, the videos need not meet any popularity criterion prior to being labeled. 
     Authoritatively labeling a video, particularly when done by a human expert who watches a representative portion of the video, is time-consuming, and thus it can be slow and costly to label enough videos  224  for performing adequate classifier training. Thus, the training set  220  also beneficially comprises a set of supplemental training items  245  that can be labeled with less effort, albeit possibly with less certainty. These supplemental training items can then be combined with the authoritatively labeled videos to form a larger training set. The supplemental training set preferably includes both similar media items (e.g., other videos) as well as other types of media items (e.g., web pages, images). 
     Specifically, in the embodiment depicted in  FIG. 2 , the supplemental training items repository  245  comprises subsets of videos  246  and  247  automatically labeled based on observed relationships, and a subset of web pages  248  authoritatively labeled in a manner similar to that by which the authoritatively labeled videos  224  were labeled. It is appreciated, however, that these particular sets of items are merely representative of one embodiment, and that the supplemental training items repository  245  need not contain items of those same content types, or items labeled using the same techniques, and many contain different numbers of subsets than the three depicted in  FIG. 2 . 
     The co-watched videos  246  of the supplemental training set  245  are automatically labeled based on observed relationships with the authoritatively labeled videos  224  resulting from user actions. That is, for a given one of the authoritatively labeled videos  224 , the videos that are played directly before or after it, or within some set time period of it (e.g., 20 minutes), by the same user are considered “co-watched” and are assumed to represent the same category or categories as those of the authoritatively labeled video. Each of the labels of the given authoritatively labeled video are then copied to its co-watched videos  246 . In one embodiment, in order to reduce the number of co-watched videos  246  that are not truly representative of the same category, only videos with co-watch counts greater than a threshold (e.g., 100) are added to the co-watched videos  246 . The number of non-representative co-watched videos  246  may also be reduced through use of additional techniques, such as computing a degree of similarity between keywords or other metadata of the authoritatively labeled video and the co-watched videos  246  and removing co-watched videos lacking some minimum degree of similarity. 
     The searched videos  247  of the supplemental training set  245  are automatically labeled based on the results of video search engines, such as those of YOUTUBE™. That is, each category label is provided as input to a video search engine, and a set of videos is identified as a result. (E.g., the category label “Tennis” is entered, and the video search engine provides a set of videos determined to represent tennis.) The category is then applied as a label to each of the videos in the search result set. In one embodiment, a maximum of 5,000 such videos is labeled for each category, including the videos found to be representative of child categories. (E.g., videos for “Tennis” are included among the videos associated with “Sports.”) Using the video search engine itself to obtain videos associated with the categories considerably speeds up the creation of a robust training set, and leverages the categorization knowledge that is embedded within the video search engine. 
     The authoritatively labeled text documents  248  of the supplemental training set  245  contain primarily textual content, and in one embodiment comprise web pages from various web sites. In other embodiments, the text documents  248  additionally and/or alternatively comprise other types of documents with significant textual content, such as word processing files, pure text files, and the like. The text documents  248  may contain non-textual elements, such as backgrounds, images, etc., in addition to their purely textual portions. The text documents  248  are labeled in the same manner as the authoritatively labeled videos  224 . That is, a human expert (for example) examines a text document, such as a web page, and labels it with the label of one or more of the categories of the category set  205 . However, since a textual document such as a web page can typically be analyzed much more quickly than a video, which must be watched for some not insignificant period of time before it can be classified, the authoritatively labeled web pages  248  can be labeled with far less cost and effort and can thus include a far greater number of items. In one embodiment, the text documents are tentatively labeled by an automated process, such as a computer program that assigns the tentative labels based on metadata keywords, and the human experts review the tentative labels, accepting or rejecting them as appropriate. 
     Thus, the training set  220  includes content items obtained using different techniques, such as manual labeling, automatic identification of co-watched videos, and execution of queries on a video search engine. Additionally, the content items may be of different content types, such as video and text, which have different content properties—that is, videos have both audiovisual content and also textual content (e.g., associated textual metadata), whereas text documents have only textual content. 
     The various items of the training set  220  need not be equally distributed amongst the various categories of the category set  205 . Rather, different categories may have different numbers of corresponding items. In one embodiment, categories lacking some threshold number of items—e.g., at least 50 authoritatively labeled videos  224 —are discarded for purposes of future classifier training. Thus, for example, although the category set  205  might originally have a thousand distinct categories, only a small number of categories (e.g., 30) might have a sufficient number of associated training items  220  to be included in the classifier training. 
     The labeling of the various training items  220  can be implemented in various manners in different embodiments. For example, each content item can be associated with some representation of the one or more categories that it represents, e.g., via a list of the shorthand numerical identifiers for the various categories. Alternatively, the association could be reversed, with each category being associated with identifiers of the associated content items, such as video identifiers, URLs of web pages or other textual documents, and the like. The associations may be stored in any type of data structure that makes access and analysis of the labels efficient. The labels can be stored with the metadata of each item  220 , or in a separate table, array, index, tree, or other structure. 
     It is appreciated that the content of the training set  220  need not wholly or even partially be physically present within the classifier training subsystem  119  of the video hosting service  100 . For example, in one embodiment one or more of the authoritatively labeled videos  224  and the supplemental training items  245  are stored on computing systems remote from the video hosting service  100 , and the classifier training subsystem  119  accesses them from their remote locations. For example, the authoritatively labeled text documents  248  may be stored remotely on websites  125  from which they originate, with the training set  220  only including a reference such as an URL pointing to the text documents  248  and labels corresponding to categories of the category set  205  that the text documents represent. The various videos  224 ,  246 ,  247  could likewise be stored remotely. 
     The classifier training subsystem  119  further comprises a classifier repository  240  containing the classifiers learned based on the content items of the training items repository  220 . Specifically, the classifier repository  240  comprises initial classifiers  241  that result from training on combinations of the authoritatively labeled videos  224  with each of the supplemental training items  245 , such as the combination of the authoritatively labeled videos  224  and the co-watched videos  246 , and the combination of the authoritatively labeled videos  224  and the authoritatively labeled text documents  248 . The classifier repository  240  additionally comprises unified classifiers  242  that result from application of a graph-based fusion algorithm to the results of the various initial classifiers  241 . Thus, the initial classifiers  241  represent preliminary classifiers that are used to produce the final, more effective unified classifiers  242 . Each of the initial classifiers  241  is associated with one of the categories in the category set  205  and, when applied to a video, provides a measure of how strongly the video represents that category. For example, an initial classifier  241  for the category “Tennis” provides a score measuring how strongly a given video represents the sport of tennis, e.g., based on the audiovisual content of the video and/or its textual metadata  117 A. In one embodiment, a classifier produces Boolean scores representing whether or not a given video represents the category of the classifier; in another embodiment, a classifier produces a real number scalar (e.g., ranging from 0.0 to 1.0) representing how strongly (e.g., a measure of likelihood or probability) the video represents the categories, and numbers greater than some threshold can be considered to mean that the video represents the category. 
     The classifier training subsystem  119  further comprises a classifier training module  230  that analyzes the content items in the training set  220  and trains the set of unified classifiers  242  that can be used to automatically categorize videos. 
     Specifically, the classifier training module  230  comprises a data supplementation module  231  that identifies certain ones of the supplemental training items  245  and adds them to the training set  220 . For example, in one embodiment the data supplementation module  231  examines an access log of the video hosting service  100  to determine which videos were co-watched, and compares these videos to the authoritatively labeled videos  224  to identify the set of co-watched videos  246 . Similarly, the data supplementation module  231  performs queries of the video search module  106  using each category label of the category set  205  to identify the searched videos  247 . 
     The classifier training module  230  further comprises a partitioning module  232  that partitions the labeled content items of the training items repository  220 —that is, the authoritatively labeled videos  224  and supplemental training items  245 —into positive and negative training subsets based on their labels. (As previously noted, the co-watched videos  246  and the searched videos  247  inherit the labels of the authoritatively labeled videos  224  to which they are related.) Thus, for each content item in the set of training items  220 , and for each category in the category set  205 , the partitioning module  232  partitions the training items into some positive subset of items representing the category and some negative subset of items not representing the category. In an embodiment in which the category set  205  is structured as a hierarchical taxonomy, the documents representing the category are defined to be the documents labeled as representing either the category or one of its descendant categories (i.e., any child subcategory of the category, or any subcategories of a subcategory, etc.). The documents not representing the category are then derivatively defined to be the documents not in the positive subset. 
     Thus, referring to the above category examples, the partitioning module  232  could partition the training items  220  into a positive subset of content items representing “Sports” and a negative subset of documents not representing “Sports,” a positive subset representing “Tennis” and a negative subset not representing “Tennis,” and so forth, for each category in the category set  205 . These training subsets can then be used by an initial classifier training module  234  to train the initial classifiers  241 , as described below. 
     The classifier training module  230  further comprises a feature extraction module  233  that extracts relevant features from the various training items  220 , an initial classifier training module  234  that trains a number of initial classifiers  241  for the various categories within the category set  205  using the features extracted by the feature extraction module  233 , and a fusion module  235  that trains the unified classifiers  242  based in part on values produced by the initial classifiers  241 . These modules are now described in further detail. 
     The feature extraction module  233  extracts features from the content items of the training items repository  220 , the features serving as descriptive representations of their respective content items for use in learning category classifiers. The types of features differ based on the type of the content item from which they are extracted. For example, in the case of text documents from the authoritatively labeled text documents  248 , the feature extraction module  233  extracts textual features from the contents of the documents. In one embodiment, the textual features that are extracted are weighted text clusters obtained from Noisy-Or Bayesian networks. (For more details, see, for example,  Learning Bayesian Networks  by R. E. Neapolitan, Prentice Hall, 2003, which is hereby incorporated by reference.) These same textual features can also be extracted from the textual metadata of the videos  224 ,  247 ,  248  (e.g., from the title, description, and keywords associated with a video), although their descriptive power tends to be less than in the case of the labeled text documents  248 , given the lesser amount of text in video metadata compared to that in a text document. 
     The feature extraction module  233  additionally extracts various features from video content of the videos  224 ,  247 ,  248 . For example, in one embodiment the types of features include:
         A color histogram computed using hue and saturation in HSV color space;   Color motion defined as the cosine distance of color histograms between two consecutive frames;   Skin color features;   Edge features using edges detected by a Canny edge detector in regions of interest;   Line features using lines detected by a probabilistic Hough Transform;   A histogram of local features using Laplacian-of-Gaussian (LoG) and SIFT (Scale Invariant Feature Transform);   A histogram of textons;   Entropy features for each frame using a normalized intensity histogram and entropy differences for multiple frames;   Facial features such as a number of faces, or the size and aspect ratio of largest face region, with faces being detected by an extension of the AdaBoost classifier;   Shot boundary detection based features using differences of color histograms from consecutive frames;   Audio features such as audio volume and 32-bin spectrogram in a fixed time frame centered at the corresponding video frame; and   “Adult” content features based on a boosting-based classifier in addition to frame-based adult-content features.       

     Audio and visual features are extracted in the same time interval. Then, a 1 D Haar wavelet decomposition is applied to the extracted features at 8 scales. Instead of using the wavelet coefficients directly, the maximum, minimum, mean and variance of the wavelet coefficients are used the features in each scale. This multi-scale feature extraction is applied to all of the audio and video content features, except the histogram of local features. 
     It is appreciated that numerous types of data could be extracted as features of a text document or a video, according to techniques known to one of skill in the art, and the above-described features are merely illustrative of the techniques of one embodiment. 
     The initial classifier training module  234  trains the various initial classifiers for each category of the category set  205 . Different initial classifiers are trained based on the different combinations of the authoritatively labeled videos  224  with the various subsets of the supplemental training items  245 . For example, in the embodiment depicted in  FIG. 2 , in which the supplemental training items  245  comprise a subset of co-watched videos  246 , a subset of searched videos  247 , and a subset of authoritatively labeled text documents  248 , initial classifiers are trained for the three combinations of the authoritatively labeled videos  224  with each of these three subset. Further, for each combination, classifiers may be learned based on the types of features obtainable from the combination. For example, the two combinations of the videos  224  with the videos  246  and  247  each support both audiovisual features and text features, since videos have both audiovisual content and textual metadata, and thus both audiovisual and textual classifiers  241  are trained. In contrast, the combination of the videos  224  with the text documents  248  supports only textual features, since the text documents  248  lack audiovisual content, and thus only textual classifiers are trained. Thus, in the embodiment of  FIG. 2 , five distinct classifiers are trained for each analyzed category: (1) an audiovisual classifier and (2) a textual classifier trained from the combination of the authoritatively labeled videos  224  with the co-watched videos  246 ; an (3) audiovisual classifier and a (4) textual classifier trained from the combination of the authoritatively labeled videos  224  with the searched videos  247 ; and a (5) textual classifier (only) trained from the combination of the authoritatively labeled videos  224  with the authoritatively labeled text documents  248 . Thus, in this embodiment each of the K categories has 5 distinct classifiers associated with it, and so there are 5K distinct classifiers in total. As noted, in one embodiment classifiers are trained only for categories having a sufficient number of associated training items, e.g., at least 50 authoritatively labeled videos  224 . 
     More specifically, for each analyzed category of the category set  205 , the initial classifier training module  234  provides the features extracted by the feature extraction module  233  from the positive and negative training subsets produced by the partitioning module  232  as input to a training algorithm. In one embodiment, the AdaBoost training algorithm is used for training the classifiers  241  based on audiovisual features from video content, and the SVM algorithm is used for training the classifiers based on textual features (i.e. the textual features extracted the textual metadata of videos  224  and from the content of text documents  248 ) where there are 10,000 or fewer content items for training, and the LibLinear algorithm where there are more than 10,000 content items. 
     With the various initial classifiers  241  trained, a fusion module  235  then trains the unified classifiers  242  based (in part) on the combined outputs of the classifiers. The training of the unified classifiers takes into account relationships between neighboring categories in the category graph, and also combines training items from different sources and possibly different content domains (e.g., video, text, audio). The unified classifiers  242  may then be applied to an arbitrary video (or, in other embodiments, to another type of media item of interest), producing as output a score for each of the categories of the category set  205 , the scores measuring how strongly the video represents that category. Further details on the fusion module  235  are provided below with respect to  FIGS. 3A and 3B . 
     The classifier training subsystem  119  optionally comprises a video classification module  250  that applies the initial classifiers  241  and the unified classifiers  242  produced by the classifier training module  230  to determine categories of the category set  205  that are applicable to a given video. Discussion of the use of the video classification module  250  is provided below. 
     Overall Process 
       FIG. 3  illustrates the relationships between the various modules described above, and data processing involved in the process of deriving the unified classifiers  242 , according to one embodiment. 
     The process begins with the authoritatively-labeled videos  224 , each of which has been authoritatively labeled as representing one or more categories of the category set  205 . The supplemental training items  245  are then added to the authoritatively labeled videos  224 , thereby forming the training set  220 . In one embodiment (depicted in  FIG. 3 ), the supplemental training items  245  include co-played videos  246 , searched videos  247 , and authoritatively labeled web pages  248 , as described above with respect to  FIG. 2 . Video items  246  and  247  inherit the same category labels as the authoritatively labeled videos  224  to which they are related; the authoritatively labeled web pages  248  are independently labeled, such as by human experts or labeling algorithms. 
     Specifically, the authoritatively labeled videos  224  are combined  305  with each of the sets of supplemental training items  246 - 248 . For example, assuming there are N 1  authoritatively labeled videos  224  and N 2  co-played videos  246 , they are combined into a first combined set having N 1 +N 2  items. For each category of the category set  205 , appropriate features are then extracted  310  from the media items of each of the combined sets that represent the category, and an initial classifier  241  is trained  315  based on those features. Features are said to be appropriate for a combined set if they are of a type obtainable from both the authoritatively labeled videos  224  and the other set of supplemental training items  245  in the combination. For example, since both the authoritatively labeled videos  224  and the co-played videos  246  are videos having both textual features (e.g., from textual metadata) and audiovisual features, both a text classifier and an audiovisual classifier are trained for the combination of videos  224  and  246 . Thus, in the embodiment of  FIG. 3 , there are—for every category—five distinct initial classifiers: textual and audiovisual classifiers trained from features of the combination of videos  224  and  246 ; textual and audiovisual classifiers trained from features of the combination of videos  224  and  247 ; and a textual classifier trained from features of the combination of videos  224  and web pages  248 . 
     Each of the initial classifiers  241  is then applied  320  to score each of the media items in the training set  220 . The set of scores of the various media items, along with the corresponding labels, are provided as input to the fusion module  235 , which fuses the data together, training  325  a single unified classifier  242  for each of the categories  205 . More specifically, the training  325  results in learning of model parameters, as described in more detail below with respect to  FIG. 4 . These parameters can then be used in conjunction with the other input data to infer the categories represented by an arbitrary video  320 , as described in more detail below with respect to  FIG. 4 . 
     It is appreciated that the steps of  FIG. 3  need not be performed in the exact order described. For example, the feature extraction  310  could be performed before the subsets of the training set  220  are combined, and the combination could combine only the extracted feature vectors. Similarly, the features need not be extracted  310  from all the combinations of the training set  220  before training  315  is performed; rather, extraction and training could be performed for one combination at a time, before proceeding to the next combination. Similarly, some of the steps could occur partially or entirely in parallel on different processing units (e.g., different machines, different processors of a single machine, or different cores of a single processor). 
     It is further appreciated that the unified classifiers  242  need not apply solely to digital videos, but in different embodiments applies to different types of media items, such as audio files, image files, textual files such as web pages, and the like. The process for training the unified classifier  242  in these embodiments is analogous to that disclosed above for training the unified classifiers  242  to categorize videos. That is, with the exception of possibly using different types or numbers of subsets within the training set  220  and extracting different types of feature vectors for different types of media items, the process is fundamentally the same in all such embodiments. 
     Unified Classifier Training and Application 
       FIG. 4  is a data flow diagram representing the inputs and outputs of processes for training and for applying the unified classifiers  242 , respectively, according to one embodiment. 
     As noted, the unified classifiers  242  of  FIG. 2  are trained by the fusion module  235 . The fusion module  235  applies the initial classifiers  241  to each of the media items in the set of training items  220 . For each media item, the classifiers  241  produce a set of M*K scores, where there are K categories and M distinct classifiers per category. The set of scores is linearized to form a feature vector for the media item. Then, graph-based statistical methods of a fusion algorithm are applied to these feature vectors, to the known category labels of the media items of the training items  220 , and to the graph of the category set  205  to calculate parameter values used in the unified classifiers  242 . More detail on the fusion algorithm is now provided. 
     In one embodiment the fusion algorithm uses a Conditional Random Field/Discriminative Random Field (CRF/DRF). A CRF/DRF is a graph with a set of nodes S and edges E. The probability of a random variable x (called the “label occurrence”) co-occurring with a property y (called the “observation”), p(x|y), is calculated as follows: 
                     p   ⁡     (     x   ❘   y     )       =       1   Z     ⁢     exp   (         ∑     i   ∈   S       ⁢       A   i     ⁡     (       x   i     ❘   y     )         +       ∑     i   ∈   S       ⁢       ∑     j   ∈     N   i         ⁢       I   ij     ⁡     (       x   i     ,     x   j     ,   y     )             )               [   1   ]               
where, for purposes of video classification, S is the category graph of the category set  205 , each node i in S represents one of the categories in S (e.g., “Tennis” or “Arts &amp; Entertainment”) x i  and x i  are binary label occurrence variables for the i th  and i th  nodes in S indicating whether an input video represents the categories of i th  and j th  nodes, y is a set of observations y i , each y i  being the score resulting from applying the i th  initial classifier to the input video, and Z is a normalizing constant mapping the result to the range [0.0, 1.0]. The indices i and j thus enumerate over the set of nodes in S. A i  and I ij  are referred to as the association potential and the interaction potential, respectively, and are defined as follows:
 
                         A   i     ⁡     (       x   i     ,   y     )       =     log   ⁢     1     1   +     exp   ⁡     (       -     x   i       ⁢     ω   i   T     ⁢       h   i     ⁡     (   y   )         )               ,           [   2   ]               
and
 
 I   ij ( x   i   ,x   j   ,y )= x   i   x   j   v   T μ ij ( y ), jεN   i ,  [3]
 
where w i   T  and v T  are parameters tending to maximize A i  and I ij , h i  is the set of classifier scores and their quadratic combinations, is a pairwise feature vector for category nodes i and j, and N i  denotes the neighbor nodes of i (e.g., its parent and/or child nodes).
 
     In one embodiment, there is a distinct w i   T  parameter value for each node i, and thus the parameter w is non-homogeneous. This training of a potentially different w value for each category node increases the number of parameters needed for the model, but this is computationally feasible where the number of categories is not overly large. For example, this is the case where only a modest number of potential categories have an adequate number of associated authoritatively labeled videos  224 . Making w non-homogenous beneficially increases the flexibility of the model, thereby allowing the model to better simulate real-world data. 
     Note that the association potential A i  is a function only of node i, whereas interaction potential I ij  is a function of both node i and its neighbor nodes j. Thus, conceptually, A i  contributes to the decision of the label occurrences to apply to a node i locally, without considering label occurrences of neighboring nodes, and I ij  regulates the label occurrences of node i by performing data dependent smoothing of labels on the neighboring nodes, which serves to take into account inter-category relationships. Specifically, I ij  relates the scores associated with neighboring nodes of the graph by computing the product x i *x j , as described further below. 
     A CRF/DRF as defined above thus may be applied to the problem of assigning category labels to videos or other media items.  FIG. 4  represents the inputs and outputs for the training of the unified classifiers  242  by the fusion module  235  using CRF/DRF, operating a fusion algorithm in a training mode  400 A, according to one embodiment. The training performed by the fusion algorithm in training mode  400 A takes as input the category set  205 , each category of which represents one of the nodes i in the set S of the CRF/DRF graph. Further, the neighbors N i  of each node i can be determined from the graph. In one embodiment in which the category set  205  is represented as a tree, the neighbors N i  may include both child and parent nodes, both of which are treated equivalently by the algorithm. In another embodiment, child and parent neighbors are treated differently. The training further takes as input the set of observations y and the set of label occurrences x, which are derived from the media items of the training set  220 . Here, the observations y are the score feature vectors obtained by applying the initial classifiers  241  to the media items of the training set, and h i  and μ ij  are a direct result of the values of y. In particular, each label occurrence value x i  of x is expressed as +1 or −1, based on whether it indicates that the respective media item does, or does not, represent the category corresponding to node i. 
     As noted, the interaction potential of equation [3] takes into account inter-category relationships. Specifically, the label occurrences x i  and x j  of neighboring nodes i and j are multiplied when computing the interaction potential, and using the values +1 and −1 for the label occurrences has the effect of producing a negative product when “neighbor” concepts have different label occurrences, thereby reducing the interaction potential. This penalizes parameter values that lead neighbor concepts to have different label occurrences for the same video, which is a desired result, since parent and child concepts are expected to represent the same concepts with higher probability than non-neighboring concepts. 
     Further, the authoritative labels of the media items act as the label occurrences x that represent the categories applicable to the media items; that is, each category label that has been authoritatively applied to a training set item causes the label occurrence x i  for the item to be +1, and the label occurrences for the category labels not authoritatively applied are −1. Assuming that there are N media items in the training set  220 , K categories in the category set  205 , and M different classifiers per category, then there are K*N label occurrences in x (one label per category), and M*K*N scores in observations y (M scores for each of the K categories, for each of the N media items). 
     Thus, the CRF/DRF expressed by equation [1] above, as applied to the problem of video categorization, quantifies the probability that a particular video or other media item represents given categories (corresponding to label occurrences x), given that the initial classifiers  241  when applied to that video produce a particular set of scores (observation y). 
     Note that—with respect to the training items  220 —the variables S, N i , x, y, h i  and μ ij  of equations [1]-[3] are all known or can be easily calculated. Thus, only the parameters w i   T  and v T  remain unknown. To calculate these parameters, the fusion module  235  applies statistical methods to find the parameter values that maximize the probability expressed by equation [1], given the other variables with known values. In one embodiment, maximum likelihood estimation (MLE) is used in combination with belief propagation (BP), as would be known to one of skill in the art in the field of statistics. With the parameters w i   T  and v T  of the unified classifiers  242  calculated based on the representative media items of the training set  220  (for which the label occurrences x are already known), the unified classifiers can be applied to categorize videos.  FIG. 4  further represents the inputs and outputs for the application of the unified classifiers  242  when the fusion algorithm is operating in inference mode  400 B to categorize a video  420 , according to one embodiment. As before, node set S and the neighbor nodes N i  are known, as are the initial classifiers  241 , and the score observations y can be obtained by applying the initial classifiers  241  to the appropriate feature vectors extracted from the video  420 . (For example, textual feature vectors are extracted from metadata of the video and provided as input to the initial classifiers  241  that were trained based on textual features, and audiovisual features are likewise extracted and provided as input to initial classifiers  241  that were trained on audiovisual features.) However, at this point the parameters w i   T  and v T  are now known, and the category labels x remain to be calculated. 
     Thus, the categories S (including neighbors for each node i), the observations y, and the parameters w i   T  and v T  act as input for the CRF/DRF algorithm. The output, x, is a set of label occurrences, one for each category of the category set  205 , each label occurrence representing whether the video  420  is of the corresponding category. In inference mode  400 B, the fusion algorithm infers whether the video  420  represents the various categories  205 , given the properties of the video represented by the scores of the observation y. In one embodiment, the inference mode  400 B uses a maximum posterior marginal (MPM) algorithm with belief propagation (BP) to determine the category label occurrences x by maximizing the conditional probability p(x|y), given y and the other known input. 
     The above-described techniques have a number of properties that are particularly useful for performing video recognition in conjunction with a graph of categories. For example, the inclusion of the scores from the different types of initial classifiers  241  for a category  205  within the single observation y integrates different types of data within a single classifier, thereby allowing the use of training items  220  obtained in different ways and/or having different types of data. Further, the use of the graph algorithms, and in particular the interaction potentials that examine the interplays of neighboring category nodes, takes into account the parent-child relationships of the various categories, thereby capturing additional information and resulting in a more accurate classifier. 
     Uses of the Trained Classifiers 
     After the training process is complete, the unified classifiers  242  can, when applied to a video (e.g., by the video classification module  250 ), produce a score for every category of the set of categories  205 . The unified classifiers  242  may then be applied to categorize videos  117  from the video repository  116  that do not already have authoritatively applied category labels. The unified classifiers  242  are provided, as input, with the same type of information that was used to train them—that is, feature vectors of classifier scores. Thus, for each category  205  and for each of the initial classifiers  241 —e.g., the five initial classifiers of the example of FIG.  3 —the initial classifiers  241  are applied to the input video, producing a feature vector of scores. This feature vector of scores is then provided to each of the unified classifiers  242  as depicted in  FIG. 4 , and the set of category scores is produced as output. In one embodiment, the video is assigned a category label for each category for which the associated unified classifier  242  produces a score above some threshold level indicating sufficient certainty that the video is indeed representative of the category. 
     In another embodiment, only the top-scoring C categories are used to label the video, for some integer C. In one embodiment, if the category set  205  is a taxonomy tree, a video is not assigned a label with a general parent category having a child sub-category that also applies. For example, if the classifiers for both the “Sports” category and its “Tennis” child category output scores for a given video above the threshold level, the video would be labeled with “Tennis” but not with “Sports,” since the latter can be inferred from the former. In another embodiment, any category for which the associated unified classifier  242  produces a score for a video above some threshold level has its label assigned to the video, regardless of its parent/child relationships with other categories. 
     The category labels assigned to a video can then be used in various ways by users of the video hosting service  100 . For example, the labels of the determined categories can be viewed along with other metadata of a video, e.g., appearing as video tags for the video when viewed in a web-based user interface of a video sharing site. The labels can also be used to browse videos of a particular type, such as showing all videos that were assigned labels of a chosen category, such as “Tennis.” The category can be chosen in various ways, such as by direct user selection of a category. Alternatively, the category can be chosen by user selection of a document from which the category can be inferred, such as by application of the initial classifiers to a textual document, by application of the unified classifier to a video, or the like, thus implementing “show videos like this document” functionality. Similarly, they can be integrated into more sophisticated search functionality as one input, such as a search for videos of a particular category and having other additional attributes, such as particular text in their titles, a creation date within a given timeframe, or the like. The possible uses of the assigned category label are numerous, and are not limited to these specific examples. 
     The present invention has been described in particular detail with respect to one possible embodiment. Those of skill in the art will appreciate that the invention may be practiced in other embodiments. First, the particular naming of the components and variables, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component. 
     Some portions of above description present the features of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or by functional names, without loss of generality. 
     Unless specifically stated otherwise as apparent from the above discussion, it is appreciated that throughout the description, discussions utilizing terms such as “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices. 
     Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems. 
     The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored on a computer readable medium that can be accessed by the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of computer-readable storage medium suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability. 
     The algorithms and operations presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will be apparent to those of skill in the art, along with equivalent variations. In addition, the present invention is not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references to specific languages are provided for invention of enablement and best mode of the present invention. 
     The present invention is well suited to a wide variety of computer network systems over numerous topologies. Within this field, the configuration and management of large networks comprise storage devices and computers that are communicatively coupled to dissimilar computers and storage devices over a network, such as the Internet. 
     Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.