Abstract:
A method and apparatus for calculating a score for word selection, which may be used to preprocess sets of words prior to a dimensionality reduction process, employs information about relationships between words themselves (such as synonym relationships) or relationships between items with which the words are associated (such as products in a catalog). In some embodiments, the relationships are also community based; i.e., the relationships are established by a community of users. The relationships may be references to two or more word sets in which the word of interest is common. In one embodiment, the word sets are descriptions of products in an online catalog, the community is the group of people who view the catalog, and the relationships used for calculating the score for a particular word of interest are coreferences (e.g., viewing or purchasing) of pairs of products for which the catalog descriptions both include the particular word.

Description:
FIELD 
       [0001]    The present disclosure concerns an improved word filtering technique which may be used to filter a document set prior to a dimensionality-reduction process. 
       BACKGROUND 
       [0002]    Statistical techniques for dimensionality-reduction, such as independent component analysis (ICA), have been shown to be effective in embedding large sets of documents in low-dimensional spaces both for classification and for similarity-based retrieval. These dimensionality-reduction techniques have been applied to retail product catalog “understanding,” where the unstructured text items can include such information as product name and description. 
         [0003]    One standard technique for improving the performance of such dimensionality-reduction methods is to preprocess the set of words associated with each item. Preprocessing (also sometimes known as normalization) is typically accomplished by first removing very common words (e.g., “an”, “the”, etc.), and then applying techniques such as stemming (i.e., removing suffixes and prefixes from words to expose common root forms) or truncation, and/or down-selection to a “relevant” subset of the vocabulary. Down-selection is also known as word filtering or word selection. It should be understood that some or all of the aforementioned preprocessing techniques (common word removal, stemming, truncation, and word filtering) may be used in any particular application. After word selection, each document in the set (e.g., each product description in a catalog) is converted into a vector of counts. The vectors are combined into a matrix of descriptions and counts that is then reduced using some dimensionality reduction scheme such as ICA. 
         [0004]    Traditional statistical methods for word selection use catalog-based relevance measures, such as removing all words appearing in most or few of the items. An alternate approach to word selection is described herein. 
       SUMMARY 
       [0005]    Alternate approaches to word selection are described in further detail herein. These approaches differ from traditional statistical methods in one or both of two ways: 
         [0006]    1. They are relational. That is, the information used is about relationships, such as relationships between product pairs or descriptions of pairs of products, not word occurrence in individual products; and 
         [0007]    2. They are community-based. That is, the information is about product coreference (e.g., co-view or co-buy) by visitors to a website on which the catalog is hosted. Thus, the filter incorporates the community view of product relatedness into the dimensionality reduction process. 
         [0008]    Testing has shown that this approach outperforms any of the more sophisticated (but non-relational, not community-driven) methods traditionally used. The use of relational information is, in general, transformative, and widely applicable wherever traditional non-relational, purely catalog-based, methods have been used in the past (e.g., search). 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  is a set of receiver operating characteristic curves showing experimental results for various embodiments. 
           [0010]      FIG. 2  is a set of receiver operating characteristic curves showing experimental results for various alternative embodiments. 
           [0011]      FIG. 3  is a block diagram of a system according for calculating word scores and performing a word selection process according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    In the following detailed description, a plurality of specific details, such as particular constants used in various equations and types of coreference data, are set forth in order to provide a thorough understanding of the preferred embodiments discussed below. The details discussed in connection with the preferred embodiments should not be understood to limit the present invention. Furthermore, for ease of understanding, certain method steps are delineated as separate steps; however, these steps should not be construed as necessarily distinct nor order dependent in their performance. 
         [0013]    The word selection techniques described herein can be used with a wide variety of document sets that are to be embedded into low dimensional spaces, whether for classification or similarity-based retrieval. These word selection techniques may be used to preprocess a document set for a wide variety of dimensionality-reduction techniques, including but not limited to ICA, PCA (principal component analysis), and SVD (singular value decomposition). It should be understood that the current invention covers word selection techniques that are relational, including community-based and other forms of relational techniques such as semantic-based (e.g., use of synonym/antonym information) methods and methods in which relationship in indicated by information found in a catalog (e.g., common manufacturer. 
         [0014]    The word selection techniques described herein are believed to be particularly applicable to the retail catalog environment and particularly the web hosted retail catalog environment and therefore will be discussed primarily in that context herein. However, the invention should not be understood to be so limited and may be used with a wide variety of documents in both electronic (web based and other) and hard copy forms. 
         [0015]    One embodiment of relational word selection uses product-to-product relations from a coreference record to determine what words in product descriptions help to explain the existence and strength of the coreference. The coreference record is a record of the pairwise coreference frequency of items. Coreference may be measured, for example, with respect to web user sessions (e.g., how may times a user of a web based catalog who viewed or bought one item of a pair also viewed or bought the second item of a pair in the same web session) or any other independent source of term coreference. 
         [0016]    In some embodiments, the coreference record is maintained as an N×N array, where N is the number of products in the catalog. In other embodiments, the coreference record is maintained as five disjoint maximal weighted spanning trees rather than the full N×N array. The storage requirements for the five disjoint maximal weighted spanning trees grows linearly rather than quadratically. The maximal weighted spanning trees are created by processing the raw reference stream (e.g., the session logs in a web catalog embodiment) and reducing down to the spanning tree representation whenever the coreference table size exceeds a threshold. Each entry in the record (whether array or tree) is a weight. In some embodiments, the weight represents a count of coreferences, such as a count of the number of visitors in the sample who referenced both products. The count may be accumulated over a specific time period. In some embodiments, the coreference weights are decayed based on their age and then new coreference weights are added to the decayed values to obtain the new coreference weights. In other embodiments, the count may be accumulated over a specific total number of users who visit the catalog. In yet other embodiments, the weight represents a fraction of viewers who reference the product pair. 
         [0017]    Below is a description of one embodiment applicable to a web catalog environment. The constants in the equations below were derived empirically. 
       DEFINITIONS 
       [0000]    
       
         
           
             n w : Number of unique words in a catalog (across all products) after stemming or truncation 
             n p : Number of products in a catalog 
             c i : Number of times word i appears in the catalog (across all products) 
             w i : Number of products in which word i appears 
             B i : sum across all products of coreference weights when word i appears in the catalog entry for both coreferenced products 
             S i : sum across all products of coreference weights when word i appears in the catalog entry for one coreferenced product 
           
         
       
     
         [0024]    Coreference weights are &gt;=0. 
         [0025]    Using the above definitions, words are scored based on two derived values: 
         [0026]    L i =(B i +0.1)/(S i +3.0) 
         [0000]    
       
         
           
             
               I 
               i 
             
             = 
             
               2 
               * 
               
                 
                   p 
                   
                     1 
                     - 
                     p 
                   
                 
               
             
           
         
       
     
         [0027]    where p=w i /n p    
         [0028]    The word score of word i is then 
         [0029]    Score i : 1e 5 *L i *I i *f i    
         [0030]    where 
         [0031]    f i =max[√{square root over (B i )}*(L i −0.2)] 
         [0032]    The number of words used is limited to the top scoring N words, where 
         [0033]    N=max[min[300, n w ], 25*√{square root over (n p )}] 
         [0034]    The score function is constructed to favor words that are likely to appear in a given product (through I i ) and are correlated with coreferences (through L i , which is the ratio of (1) the sum over all products of the coreference weights of product pairs in which the word appears in the catalog entry for both products to (2) the sum over all products of the coreference weights of product pairs in which the word appears in only one product of the pair). The score function strongly penalizes words that tend to only appear in one side of a coreference. In this way, words that “explain” strong coreferences are chosen for use in the recommendation model. 
         [0035]    Exemplary Implementation 1 
         [0036]    Implementation of the embodiment described above will be discussed relative to a simplified retail catalog and coreference data set for the purposes of illustration. In this example, the retail clothing catalog includes three products: A, B and C. The description in the catalog for product A includes the words shirt, long, sleeve, plaid. The description in the catalog for product B includes the words shirt, short, sleeve, stripe. The catalog description for product C includes the words pants, cuff, stripe. 
         [0037]    There is product coreference data corresponding to ten user web sessions. In session 1, the user looked at viewed only products A and B. In session 2, the user viewed products B and C. In session 3, the user viewed only product B. In session 4, the user viewed products A and B and C. In session 5, the user viewed products B and C. In sessions 6, 7, and 8, the user viewed products B and C. In session 9, the user viewed only product C. In session 10, the user viewed products A, B and C. 
         [0038]    The number of words n w =8 (shirt, long, sleeve, stripe, short, plaid, pants, cuff) and the number of products n p =3 (products A, B and C). The number of times each of these words appears in the catalog, c i , is as follows: C shirt =2; c long =1; C sleeve =2; c stripe =2, c short =1; c plaid =1; c pant =1; c cuff =1. The number of products in which each word appears, w i , is as follows: w shirt =2; w long =1; w sleeve =2; w stripe =2, w short =1; w plaid =1; w pants =1; w cuff =1. The array of coreference weights (the count of the number of users who referenced each product in the pair) is constructed as follows: 
         [0000]    
       
         
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 A 
                 B 
                 C 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 A 
                 x 
                 3 
                 2 
               
               
                   
                 B 
                 3 
                 x 
                 7 
               
               
                   
                 C 
                 2 
                 7 
                 x 
               
               
                   
                   
               
             
          
         
       
     
         [0039]    The coreference array above is symmetric—it includes redundant information in that the row, column entries are the same as the column, row entries (i.e., the entry for column A, row C is the same as row A, column C). This is because no information concerning the direction of the coreference (i.e., which product was viewed first) is maintained. Those of skill in the art will recognize that storing the redundant information is not necessary and more efficient storage schemes are well known in the art. 
         [0040]    Next, the values of B and S for each of the words is calculated. B shirt =sum across all products of coref weights when word i appears in the catalog entry for both coreferenced products=3. This is because the word “shirt” appears in product A and product B, therefore the AB coreference is the only coreference when the word “shirt” appears in both coreferenced products, so from the array the AB coreference weight is 3. B long  is 0 because the word “long” never appears in both coreferenced products for any coreference pair. Similarly, B short , B plaid , B pants  and B cuff  are all also 0. B sleeve  is 3 because “sleeve” appears in both products A and B in the product AB coreference. Finally, B stripe =7 because the word “stripe” appears twice in only the product BC coreference. 
         [0041]    The value of S for the word “shirt” (S shirt )=sum across all products of coreference weights when word i appears in the catalog entry for one coreferenced product=9 because “shirt” appears in only once in the AC and BC coreferences, which have weights of 2 and 7, respectively. S long =5 because the word “long” appears only in product A, the coreferences involving product A are the AB and AC coreferences, the AB coreference weight is 3 and the AC coreference weight is 2. 
         [0042]    S sleeve =9 for the same reasons as S shirt . S stripe =5 because “stripe” appears in products B and C and therefore appears once in the AB and AC coreferences which have weights 3 and 2. S short =10 because “short” appears in only product B, the AB coreference weight is 3 and the BC coreference weight is 7. S plaid  is 5 because “plaid” only appears in product A, therefore the coreferences in which “plaid” appears once are AB and AC which have weights of 3 and 2. S pants =9 because “pants” occurs only in product C, the AC coreference weight is 2 and the BC coreference weight is 7. S cuff  is also 9 because, like “pants”, “cuff” occurs only in product C. 
         [0043]    Using the values for w i , B i  and S i  calculated above, the values of L i , I i  and f i  are calculated as follows: 
         [0000]        L   shirt =(3+0.1)/(9+3.0)=0.258  I   shirt =2*sqrt[(2/3)/(1−(2/3)]=2.828
 
         [0000]        L   long =(0+0.1)(5+3.0)=0.013  I   long =2*sqrt[(1/3)/(1−(1/3)]=2.222
 
         [0000]        L   sleeve =(3+0.1)/(9+3.0)=0.258  I   sleeve =2*sqrt[(2/3)/(1−(2/3)]=2.828
 
         [0000]        L   stripe =(7+0.1)/(5+3.0)=0.888  I   stripe =2*sqrt[(2/3)/(1−(2/3)]=2.828
 
         [0000]        L   short =(0.0+0.1)/(10+3.0)=0.008  I   short =2*sqrt[(1/3)/(1−(1/3)]=2.222
 
         [0000]        L   plaid =(0.0+0.1)/(5+3.0)=0.013  I   plaid =2*sqrt[(1/3)/(1−(1/3)]=2.222
 
         [0000]        L   pants =(0.0+0.1)/(9+3.0)=0.008  I   pants =2*sqrt[(1/3)/(1−(1/3)]=2.222
 
         [0000]        L   cuff =(0.0+0.1)/(9+3.0)=0.008  I   cuff =2*sqrt[(1/3)/(1−(1/3)]=2.222
 
         [0000]        f   shirt =max[0, sqrt(3)*(0.258−0.2)]=0.100
 
         [0000]        f   long =max[0, sqrt(0)*(0.013−0.2)]=0
 
         [0000]        f   sleeve =max[0, sqrt(3)*(0.258−0.2)]=0.100
 
         [0000]        f   stripe =max[0, sqrt(7)*(0.888−0.2)]=1.820
 
         [0000]        f   short =max[0, sqrt(0)*(0.008−0.2)]=0
 
         [0000]        f   plaid =max[0, sqrt(0)*(0.0125−0.2)]=0
 
         [0000]        f   pants =max[0, sqrt(0)*(0.008−0.2)]=0
 
         [0000]        f   cuff =max[0, sqrt(0)*(0.008−0.2)=0
 
         [0044]    Next, the scores for each word are calculated: 
         [0000]      Score shirt =1 e 5*0.258*2.828*0.100=7296 
         [0000]      Score long =1 e 5*0.013*2.222*0=0 
         [0000]      Score sleeve =1 e 5*0.258*2.828*0.100=7296 
         [0000]      Score stripe =1 e 5*0.888*2.828*1.820=457050 
         [0000]      Score short =1 e 5*0.008*2.222*0=0 
         [0000]      Score plaid =1 e 5*0.013*2.222*0=0 
         [0000]      Score pants =1 e 5*0.008*2.222*0=0 
         [0000]      Score cuff =1 e 5*0.008*2.222*0=0 
         [0045]    In this simplified example, the highest scoring words were stripe, sleeve and shirt. Thus, these words would be selected. Normally, there will be many more entries in the catalog and many more words for each entry. Therefore, as discussed above, some predetermined number of the top-scoring words may be selected in such embodiments, or a threshold score may be used to make the selection. 
       Experiment 1 
       [0046]    In this experiment, the effects of coreference-based word selection on checkout prediction were determined. Various word normalization (Porter stemming, wordNet normalization, truncation) methods were also examined both with and without coreference-based word selection. 
         [0047]    The prediction model assumes that there is an interaction between the ICA values of products viewed and purchased in a session, and that this interaction ultimately affects the odds of a checkout in the session. Structurally, the model is held constant. Parameters are relearned for each ICA representation. The model is trained using one or five days of data and is tested using the following day&#39;s data. 
         [0048]    Performance is evaluated by how well the model was able to predict the odds of a checkout given viewed products in a session. The evaluation metric is the area under the ROC (receiver operating characteristic) curve (AUC). Descriptions of the various normalization methods (with and without coreference-based word selection) and AUC values appear below in Table 1.  FIG. 1  shows the ROC curves  101 - 107  from which the AUC values were computed. 
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Model name 
                 Description 
                 AUC 
               
               
                   
               
             
             
               
                 pr 
                 Current implementation 
                 0.719 
               
               
                   
                 (Porter stemming + coreference selection) 
               
               
                 wn_coref 
                 WordNet normalization + coreference selection 
                 0.671 
               
               
                 wn_coref_5 day 
                 Same as wn_coref, but using 5 days of training 
                 0.650 
               
               
                   
                 data 
               
               
                 trunc_coref 
                 Words truncated to first 4 characters + 
                 0.621 
               
               
                   
                 coreference selection 
               
               
                 wn 
                 WordNet normalization only 
                 0.546 
               
               
                 rand 
                 Random Gaussian values for each product 
                 0.511 
               
               
                 trunk 
                 Words truncated to first 4 characters only 
                 0.508 
               
               
                   
               
             
          
         
       
     
         [0049]    The results set forth above in Table 1 illustrate that exploiting product-product relations when selecting words can improve checkout prediction performance much more than resorting to more sophisticated word normalization schemes. 
         [0050]    Exemplary Implementation 2 
         [0051]    The above shows that the use of community-derived relational information for word selection significantly improves the predictive capability of dimensionality reduction. However, for many product-to-product coreferences, a word may appear in one product&#39;s description but not in the other&#39;s. For example, this might occur due to use of synonyms in the available text, or due to available text emphasizing different aspects of the relevant products. Both products, however, might be connected via coreference to a third product that may contain words from each of the two original products. We can view this as applying a one-step transitive inference across the coreference relation. Below is a method for extending the current coreference-based word selection method to include relations deeper inside the coreference record. The specific method described below can be seen as an instance of a more general n-step inference over the coreference relation. 
         [0052]    Additional definitions: 
         [0053]    Let A and B be the products in a coreference.
       N i : The geometrical mean coreference count between A and B&#39;s common neighbors containing word i. A common neighbor is a product C that is a coreferent of both A and B. Note that this can occur even if A and B are not themselves coreferent, if the set of sessions that reference both A and C is disjoint from the set that reference both B and C.
 
Then adjust the definition of L i  above to be:
       
 
         [0055]    L i =(B i +√{square root over (N i )}+0.1)/(S i +3.0) 
         [0000]    The scoring function now favors words that appear in products that coreference the products in the current coreference. 
       Experiment 2 
       [0056]    We replicated Experiment 1, this time examining how the addition coreference data described above affected the predictive abilities of the ICA representation in the model. Table 2 below summarizes the results.  FIG. 2  is another plot of the ROC curves  201 - 203  and  205 - 209  used to calculate the AUC values in Table 2. 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                 Model name 
                 Description 
                 AUC 
               
               
                   
               
             
             
               
                 trunc_coref2 
                 Words truncated to first 4 characters + 2nd-order 
                 0.7853 
               
               
                   
                 CoRef 
               
               
                 pr 
                 Current implementation (Porter stemming + 
                 0.7188 
               
               
                   
                 coreference selection) 
               
               
                 wn_coref2 
                 WordNet normalization + 2nd-order CoRef 
                 0.7185 
               
               
                 wn_coref 
                 WordNet normalization + CoRef 
                 0.6707 
               
               
                 trunc_coref 
                 Words truncated to first 4 characters + CoRef 
                 0.6206 
               
               
                 wn 
                 WordNet normalization only 
                 0.5462 
               
               
                 rand 
                 Random Gaussian values for each product 
                 0.5114 
               
               
                 trunc 
                 Words truncated to first 4 characters only 
                 0.5084 
               
               
                   
               
             
          
         
       
     
         [0057]    These results demonstrate even further improvement from the incorporation of relational information for word selection. 
         [0058]    An exemplary system  300  on which the methods described above may be practiced is illustrated in  FIG. 3 . A web server  310  serves an electronic catalog to a plurality of end user PCs  320   a - n  via the Internet  330 . The web server  310  reports each user session and each product reference (which may be product purchases, product, views or any other type of reference such as placement of the product into a shopping cart) to a filtering processor  340 . The filtering processor  340  may be a separate physical device such as a stand alone computer, or may be implemented on the server  310 . The filtering processor  340  maintains a coreference (including calculation of coreference weights) and calculates word scores for words in the online catalog served by the web server  310 . The scores may be calculated once or may be recalculated from time to time. In some embodiments, the filtering processor  340  simply reports the scores to the web server  310 , and the web server  310  uses the scores to select words from the catalog as input to a dimensionality reduction scheme such as ICA and uses the dimensionality reduction results to select products for display to the consumer as suggested additional items in which the consumer may be interested. In other embodiments, the filtering processor  340  itself performs the word selection step based on the word scores and then performs a dimensionality reduction process and recommends one or more products for display with one or more items in the online catalog. 
         [0059]    It will be apparent to those of skill in the art that numerous variations in addition to those discussed above are also possible. Therefore, while the invention has been described with respect to certain specific embodiments of methods and devices for performing word selection, it will be appreciated that many modifications and changes may be made by those skilled in the art without departing from the spirit of the invention. It is intended therefore, by the appended claims to cover all such modifications and changes as fall within the true spirit and scope of the invention. 
         [0060]    Furthermore, the purpose of the Abstract is to enable the U.S. Patent and Trademark Office and the public generally, and especially the scientists, engineers and practitioners in the art who are not familiar with patent or legal terms or phraseology, to determine quickly from a cursory inspection the nature and essence of the technical disclosure of the application. The Abstract is not intended to be limiting as to the scope of the present invention in any way.