Abstract:
Product images are used in conjunction with textual descriptions to improve classifications of product offerings. By combining cues from both text and image descriptions associated with products, implementations enhance both the precision and recall of product description classifications within the context of web-based commerce search. Several implementations are directed to improving those areas where text-only approaches are most unreliable. For example, several implementations use image signals to complement text classifiers and improve overall product classification in situations where brief textual product descriptions use vocabulary that overlaps with multiple diverse categories. Other implementations are directed to using text and images “training sets” to improve automated classifiers including text-only classifiers. Certain implementations are also directed to learning a number of three-way image classifiers focused only on “confusing categories” of the text signals to improve upon those specific areas where text-only classification is weakest.

Description:
BACKGROUND 
       [0001]    It has become common for users of computers connected to the World Wide Web (the “web”) to employ web browsers and search engines to locate web pages (or “documents”) having specific content of interest to them (the users). A web-based commercial search engine may index tens of billions of web documents maintained by computers all over the world. Users of the computers compose queries, and the search engine identifies documents that match the queries to the extent that such documents include key words from the queries (known as the search results or result set). 
         [0002]    Product classification in web-based “commerce search” involves associating categories to products offered by a large number of merchants. The categorized offers are used in many scenarios including product taxonomy browsing and matching merchant offers to products in a catalog-type view. These product offers typically comprise a short textual description of the product plus an image depicting that product. Traditional approaches to classifying such offers are focused on learning a good classifier based on the textual descriptions of the products, and deriving good classifiers—having a high degree of both precision and recall—for each available product is foundational to the provision of a high quality shopping experience. 
         [0003]    However, classifiers derived exclusively from textual inputs can sometimes suffer from several shortcomings in the text upon which they rely—namely overlapping text, undescriptive text, and vocabulary usage discrepancies. 
       SUMMARY 
       [0004]    Product images are used in conjunction with the textual descriptions to improve classifications of product offerings. By combining cues from both text and image descriptions associated with products, implementations enhance both the precision and recall of product description classifications within the context of web-based commerce search. Several implementations are directed to improving those areas where text-only approaches are most unreliable. For example, several implementations use image signals to complement text classifiers and improve overall product classification in situations where brief textual product descriptions use vocabulary that overlaps with multiple diverse categories. Other implementations are directed to using text and images “training sets” to improve automated classifiers including text-only classifiers. Certain implementations are also directed to learning a number of three-way image classifiers focused only on “confusing categories” of the text signals to improve upon those specific areas where text-only classification is weakest. 
         [0005]    Several implementations are directed to a method comprising inferring a first distribution on a set of training data using a text classifier, inferring a second distribution on the set of training data using an image classifier, and concatenating the first distribution and the second distribution. Several alternate implementations are directed to a method comprising identifying a set of confusion pairs for a first set of training data; training a first plurality of image classifiers on a first set of training data wherein each image classifier corresponds to each confusion pair from among the set of confusion pairs; training a second plurality of image classifiers on the first set of training data wherein each image classifier corresponds to each background category from among a plurality of background categories; inferring a first plurality of distributions for the first plurality of image classifiers on a second set of training data; inferring a second plurality of distributions for the second plurality of image classifiers on the second set of training data; and concatenating each distribution from among the first plurality of distributions with a corresponding distribution from among the second plurality of distributions together with a third distribution produced by a text classifier. 
         [0006]    This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    To facilitate an understanding of and for the purpose of illustrating the present disclosure and various implementations, exemplary features and implementations are disclosed in, and are better understood when read in conjunction with, the accompanying drawings—it being understood, however, that the present disclosure is not limited to the specific methods, precise arrangements, and instrumentalities disclosed. Similar reference characters denote similar elements throughout the several views. In the drawings: 
           [0008]      FIG. 1  is an illustration of a search engine in an exemplary network environment in which the numerous implementations disclosed herein may be utilized; 
           [0009]      FIG. 2  is an illustration of two exemplary product offerings as they might be presented to a potential customer via the search engine of  FIG. 1 ; 
           [0010]      FIG. 3  is a process flow diagram for an exemplary method of probabilistic fusion (PF) utilized by several implementations disclosed herein; 
           [0011]      FIG. 4  is a process flow diagram for an exemplary method of confusion driven probabilistic fusion (CDPF) utilized by several implementations disclosed herein; and 
           [0012]      FIG. 5  shows an exemplary computing environment. 
       
    
    
     DETAILED DESCRIPTION 
       [0013]      FIG. 1  is an illustration of a search engine  140  in an exemplary network environment  100  in which the numerous implementations disclosed herein may be utilized. The environment  100  includes one or more client computers  110  and one or more server computers  120  (generally “hosts”) connected to each other by a network  130 , for example, the Internet, a wide area network (WAN), or a local area network (LAN). The network  130  provides access to services such as the World Wide Web (the “web”)  131 . An example computing device is described with respect to  FIG. 5 . 
         [0014]    The web  131  allows the client computers  110  to access documents  121  containing text or multimedia and maintained and served by the server computers  120 . Typically, this is done with a web browser application program  114  executing on the client computers  110 . The location of each of the documents  121  may be indicated by an associated uniform resource locator (URL)  122  that is entered into the web browser application program  114  to access the document (and thus the document and the URL for that document may be used interchangeably herein without loss of generality). Many of the documents may include hyperlinks  123  to other documents  121  (with each hyperlink in the form of a URL to its corresponding document). 
         [0015]    In order to help users locate content of interest, a search engine  140  may maintain an index  141  of documents in a memory, for example, disk storage, random access memory (RAM), or a database. In response to a query  111 , the search engine  140  returns a result set  112  that satisfies the terms (e.g., the keywords) of the query  111 . To provide a high-quality user experience, search engines order search results using a ranking function that, based on the query  111  and for each document in the search result set  112 , produces a score indicating how well the document matches the query  111 . The ranking process may be implemented as part of a ranking engine  142  within the search engine  140 . 
         [0016]    With regard to web-based commerce, online shopping sites (such as those offered by major search engine providers) target a rich and diverse set of products, and foundational to their success is to provide users with the ability to browse products offerings organized according to the product taxonomy of search engines—and thus automatic classification of product offers under such a taxonomy is widely utilized. 
         [0017]      FIG. 2  is an illustration of two exemplary product offerings  202  and  212  as they might be presented to a potential customer via the search engine  140  of  FIG. 1 . The first product offering  202  pertains to a laptop and is presented in both text  204  and an image  206 . The second product offering  212  pertains to a battery and is also presented in both text  214  and an image  216 . 
         [0018]    While existing approaches to product classification rely purely on the textual description of the products, these text-only based classifiers face several challenges. For example, many categories in a taxonomy may have products that are interrelated, and thus the textual descriptions of their products may overlap in vocabulary usage. Thus, perfectly valid textual descriptions for two completely different products—such as a laptop (“Acer TravelMate 4062LCI with battery”) and a battery (“Acer TravelMate 4062LCI battery”) shown in FIG.  2 —might pertain to entirely different searches (from a consumer&#39;s perspective) and yet differ in just one word (and even a taxonomically irrelevant word as in this case). 
         [0019]    Another challenge to good text-based classification is the prevalence of short, undescriptive text for a product offering. While product offers typically come from merchants seeking referrals from the online shopping websites, these websites typically have little or no control over the product description provided by the merchants and, in many cases the descriptions provided by the merchants are brief or incomplete. In some instances, a product description from a merchant may just include a model number such as “P43A” which, if the automated classifier is unaware of this model number, is insufficient to correctly classify the product. 
         [0020]    Yet another challenge inherent to text-based classification stems from discrepancies (or variations) in vocabulary usage. While product classifiers in the e-commerce search setting may be trained using labeled data prepared by a small pool of human labelers, the product offers needing classification may come from a very large number (e.g., thousands) of ever-changing merchants who may differ in their vocabulary and style in describing the products they offer. Therefore, given the enormity of the taxonomy, effectively capturing all variations in the product descriptions using reasonable amounts of human-derived training data is unlikely. Consequently, there will often be mismatches between the vocabulary used to train a classifier and the vocabulary used in the offers to be categorized by the learned classifier. This may be particularly true for new emerging products where the vocabulary around the product is emerging as well. 
         [0021]    As shown in  FIG. 2 , almost all products in an e-commerce site have an associated image of the product in addition to text—which is not surprising since merchants have long realized that users shop visually and are more attracted to products they can see for themselves. It is these images that can be used to provide additional clues that, when used in conjunction with the available text, are able to improve the classification for such products (including products that are often unsuccessfully classified by text-only classifiers). Thus, while the textual descriptions shown in the product offerings in  FIG. 2  were nearly the same for the two products  202  and  212  (except for the word “with”), the images are detectably different. Therefore, even if the textual descriptions are uninformative, their associated images contain discernable clues that various implementations herein utilize to form better classifiers. 
         [0022]    To this end, various implementations disclosed herein are directed to combining classifiers (text and image) to improve classification. Certain such implementations use combined classifiers for a subset of categories in which the text classifiers are ineffective (and thus can be referred to as “confusion driven” classifiers). These implementations may utilize a set of labeled instances, comprising both text and image features, and a base classifier that provides probabilistic predictions over categories. 
         [0023]    For several implementations, combining varied feature sets in some common subspace shared by the feature sets may be used to provide more robustness to the combination. In other words, separate classifiers that are trained independently for each feature set can be used to provide more robust classifications when the outputs from these independent classifiers (in the same feature space of probability in predictions) are then combined for the next higher level of abstraction. This process is referred to herein as “probabilistic fusion” (PF). 
         [0024]      FIG. 3  is a process flow diagram for an exemplary method  300  of PF utilized by several implementations disclosed herein. Referring to  FIG. 3 , the method  300  begins at  310  by splitting a collection of training data into two parts (a first portion and a second portion). At  314 , a text classifier is trained on the text features using the instances comprising the first portion of the training data. Then, at  316  infer for each instance in the second portion of the training data a distribution over the categories using the text classifier trained in  314 . 
         [0025]    Separately, at  318 , an image classifier is similarly trained on the image features using the instances in the first portion, and then at  320  infer for each instance in the second portion of the training data a distribution over the categories using the image classifier trained in  318 . It should be noted that the training ( 314  and  318 ) and inference ( 316  and  320 ) operations may be conducted in serial staring with either the text ( 314  and  316 ) or image ( 318  and  320 ) operations, or these training operation threads may be conducted in parallel as shown in  FIG. 3 . 
         [0026]    At  322 , the two probability distributions (for the text and for the image) are concatenated to create a multi-dimensional feature vector of probabilities (i.e., a new multi-dimensional feature set, or MDFS) with portions that effectively capture the uncertainty in category prediction for the text and image classifiers, respectively. Then, at  324 , another classifier is learned using this multi-dimensional feature set where this third classifier learns the relative importance in the probabilistic prediction of the two base classifiers trained separately on text and image features—and thus this third classifier (constituting a “single large multi-way classifier”) effectively learns to predict labels using both types of features (text and image). 
         [0027]    While combined text-and-image classifiers can provide relatively good classifications in all instances, a text-based classifier does provide reasonably good performance in most instances, and in those instances the need for a combined text-and-image classifier may be de minimis. For this reason, several implementations may be directed to the use of a combined text-and-image classifier for only those specific instances where a text classifier is inadequate. In other words, since images play a beneficial role in only those categories where the text-based classifier gets “confused,” it may be sufficient to systematically leverage image signals for only these categories. This high-value variation of probabilistic fusion (PF) is hence referred to herein as “confusion-driven probabilistic fusion” (CDPF). 
         [0028]      FIG. 4  is a process flow diagram for an exemplary method  400  of CDPF utilized by several other implementations disclosed herein. Referring to  FIG. 4 , the method  400  begins at  410  by splitting a collection of training data into two parts (a first portion and a second portion). At  414 , a text classifier is trained on the text features using the instances comprising the first portion of the training data. Then, at  416 , an inference is made for each instance in the second portion of the training data a distribution over the categories using the text classifier trained in  414 . 
         [0029]    Separately, at  430 , the top n confusing pairs of categories for a classifier are identified again using the first portion of the training data and again using the text classifier trained at  414 . Then, at  418 , the system learns a separate image classifier for each pair of confusing pairs (CPs) from among the n confusing pairs (i.e., learn n confusing pair image classifiers). At  420 , each image classifier is then used to infer, for an instance corresponding to its confusing pair in the second portion of the training data, a distribution over the categories (a total of n times). In addition, a plurality of “background categories” (BC) consisting of all categories other than the pair already under consideration, are learned at  432  (i.e., learn n background category image classifiers) and distributed at  434  (a total of n times) to form separate third classifiers in order to account for the possibility that the true class of classifiers might be different from the categories in the confusing pairs. It should be noted that, similar to  FIG. 3 , parallel operations of  FIG. 4  may be executed serially in varying order as well as in parallel as illustrated. Moreover, various implementations disclosed herein, including those illustrated in  FIGS. 3 and 4 , might be implemented by combining two signals from sources other than text and images such as from, for example, waveforms and textual transcripts, and such alternative implementations are explicitly anticipated by the disclosures made herein. 
         [0030]    At  422 , the method  400  concatenates the text probabilities distribution with each confusion pair image probability distribution and its corresponding background category image probability distribution to create multiple three-dimensional feature vectors of probabilities (i.e., multiple new three-dimensional feature sets, or 3DFSs) collectively forming a multi-3D feature set having portions that effectively capture the uncertainty in category prediction for the text and image classifiers, respectively. Then, at  424 , another classifier uses this multi-3D feature set to learn the relative importance in the probabilistic prediction of the multiple classifiers trained separately on text/confusion pair/background categories features—and thus this third classifier effectively learns to predict labels with special regard to confusing pairs. 
         [0031]    For certain implementations disclosed herein, unlabeled data in the form of merchant offerings may be used to improve the supervised classifiers trained using the techniques described above. For example, some implementations may use the semi-supervised learning strategy known as “self training” to exploit unlabeled data. As will be appreciated by a skilled artisan, self training works in iterations where an existing classifier is used to automatically label unlabeled data, and then instances classified as high confidence are added back to the labeled data to train the classifier in the next iteration. Thus, such implementations—both as the self-trained versions of the probabilistic fusion (PF++) classifier and the confusion driven probabilistic fusion (CDPF++) classifier—allow the label of an automatically labeled instance to change in subsequent iterations in order to make recovery from a misclassification possible. In addition, some implementations may also use a self-trained version of the text classifier in order to evaluate whether large amounts of text-only unlabeled data make the image signal irrelevant. Alternatively, other implementation may use co-training algorithms known to skilled artisans and shown to work for a variety of multi-view problems in computer vision and other domains. Co-training is used to learn separate classifiers, infer labels for the unlabeled examples, and then add these examples to training sets used to retrain the classifiers. In addition, the text and images “training sets” disclosed herein for PF and CDPF can be used to improve automated classifiers including text-only classifiers as well as text-and-image classifiers. For example, at block  324  of  FIG. 3  or block  424  of  FIG. 4 , such an implementation might instead “learn new classifier on the MDFS for predicting labels on text features only”, for example (respectively). Such approaches might be useful when images are not available, to avoid the expense of image feature extraction, or to improve efficiency or latency or both, for example. 
         [0032]    Visual features may comprise global image features that capture the global image structure in a low dimensional space. As such, the global features may be computed for each image as follows: (1) responses of steerable pyramid filters tuned to 6 different orientations and 5 scales are computed; (2) each image is divided into 4×4 local grids; and (3) the mean value of the magnitude of these local features is averaged over those grids. This approach enables the capture of global image properties while maintaining only a limited amount of spatial information. The resulting 4×4×30 vector may then be used as a visual feature representation of the image for the various implementations disclosed herein. 
         [0033]      FIG. 5  shows an exemplary computing environment in which example implementations and aspects may be implemented. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality. Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers (PCs), server computers, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, network personal computers, minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like. 
         [0034]    Computer-executable instructions, such as program modules, being executed by a computer may be used. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices. 
         [0035]    With reference to  FIG. 5 , an exemplary system for implementing aspects described herein includes a computing device, such as computing device  500 . In its most basic configuration, computing device  500  typically includes at least one processing unit  502  and memory  504 . Depending on the exact configuration and type of computing device, memory  504  may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated in  FIG. 5  by dashed line  506 . 
         [0036]    Computing device  500  may have additional features/functionality. For example, computing device  500  may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in  FIG. 5  by removable storage  508  and non-removable storage  510 . 
         [0037]    Computing device  500  typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by device  500  and includes both volatile and non-volatile media, removable and non-removable media. 
         [0038]    Computer storage media include volatile and non-volatile, and removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory  504 , removable storage  508 , and non-removable storage  510  are all examples of computer storage media. Computer storage media include, but are not limited to, RAM, ROM, electrically erasable program read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device  500 . Any such computer storage media may be part of computing device  500 . 
         [0039]    Computing device  500  may contain communications connection(s)  512  that allow the device to communicate with other devices. Computing device  500  may also have input device(s)  514  such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)  516  such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here. 
         [0040]    It should be understood that the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. Thus, the methods and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium where, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter. 
         [0041]    Although exemplary implementations may refer to utilizing aspects of the presently disclosed subject matter in the context of one or more stand-alone computer systems, the subject matter is not so limited, but rather may be implemented in connection with any computing environment, such as a network or distributed computing environment. Still further, aspects of the presently disclosed subject matter may be implemented in or across a plurality of processing chips or devices, and storage may similarly be affected across a plurality of devices. Such devices might include personal computers, network servers, and handheld devices, for example. 
         [0042]    Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.