Enhancing Text Similarity Measures for Short Segments
This research explores improving similarity measures for short text segments, essential for various applications such as query suggestions, keyword expansion in online ads, and web search ranking. Challenges like non-overlapping segments and ambiguous terms are addressed, with contributions including web-relevance similarity measures and learning similarity functions for better user preference alignment.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Improving Similarity Measures for Short Segments of Text Scott Wen-tau Yih & Chris Meek Microsoft Research
Query Suggestion query mariners How similar are they? mariners vs. seattle mariners mariners vs. 1st mariner bank
Keyword Expansion for Online Ads Chocolate Cigarettes How similar are they? chocolate cigarettes vs. cigarettes chocolate cigarettes vs. chocolate cigars chocolate cigarettes vs. old fashioned candy Candy cigarettes Chocolate candy Chocolate cigars Old fashioned candy Nostalgic candy Novelty candy
Measuring Similarity Goal: create a similarity function fsim: (String1,String2) R Rank suggestions Fix String1 as q; vary String2 as s1 , s2 , , sk Whether the function is symmetric is not important For query suggestion fsim(q,s) fsim( mariners , seattle mariners ) = 0.9 fsim( mariners , 1st mariner bank ) = 0.6
Enabling Useful Applications Web search Ranking query suggestions Segmenting web sessions using query logs Online advertising Suggesting alternative keywords to advertisers Matching similar keywords to show ads Document writing Providing alternative phrasing Correcting spelling errors
Challenges Short text segments may not overlap Microsoft Research vs. MSR 0 cosine score Ambiguous terms Bill Gates vs. Utility Bill taxi runway vs. taxi Text segments may rarely co-occur in corpus Hyatt Vancouver vs. Haytt Vancover 1 page Longer query Fewer pages 0.5 cosine score 0.7 cosine score
Our Contributions Web-relevance similarity measure Represent the input text segments as real-valued term vectors using Web documents Improve term weighting scheme based on relevant keyword extraction Learning similarity measure Fit user preference for the application better Compare learning similarity function vs. learning ranking function
Outline Introduction Problem, Applications, Challenges Our Methods Web-relevance similarity function Combine similarity measures using learning Learning similarity function Learning ranking function Experiments on query suggestion
Web-relevanceSimilarity Measure Query expansion of x using a search engine Let Dn(x) be the set of top n documents Build a term vector vi for each document di Dn(x) Elements are scores representing the relevancy of the words in document di C(x) = 1 n vi /||vi|| (L2-normalized, centroid) QE(x) = C(x) / ||C(x)|| (L2-normalized) Similarity score is simply the inner product fsim (q,s) = QE(q) QE(s)
Web-kernel Similarity Relevancy = TF IDF [Sahami&Heilman 06] Why TF IDF? High TF: important or relevant to the document High DF: stopwords or words in template blocks Crude estimate of the importance of the word Can we do better than TF IDF?
Web-relevance Similarity Relevancy = Prob(relevance | wj,di) Keyword extraction can judge the importance of the words more accurately! Assign relevancy scores (probabilities) to words/phrases Machine Learning model learned by logistic regression Use more than 10 categories of features Query-log frequency High-DF words may be popular queries The position of the word in the document The format, hyperlink, etc. [Yih et al. WWW-06]
Learning Similarity Similarity measures should depend on application q= Seattle Mariners s1= Seattle s2= Seattle Mariners Ticket Let human subjects decide what s similar Parametric similarity function fsim(q,s|w) Learn the parameter (weights) from data Use Machine Learning to combine multiple base similarity measures
Base Similarity Measures Surface matching methods Suppose Q and S are the sets of words in a given pair of query q and suggestion s Matching Dice 2|Q S|/(|Q|+|S|) Jaccard |Q S|/|Q S| Overlap |Q S|/min(|Q|,|S|) Cosine |Q S|/sqrt(|Q| |S|) Corpus-based methods Web-relevance, Web-kernel, KL-divergence |Q S|
Learning Similarity Function Data pairs of query and suggestion (qi,sj) Label: Relevance judgment (rel=1 or rel=0) Features: Scores on (qi,sj) provided by multiple base similarity measures We combine them using logistic regression z = w1 Cosine(q,s) + w2 Dice(q,s) + w3 Matching(q,s) + w4 Web-relevance(q,s) + w5 KL-divergence(q,s) + fsim(q,s|w) = Prob(rel|q,s;w) = exp(z)/(1+exp(z))
Learning Ranking Function We compare suggestions sj Data tuples of a query q and suggestions sj, sk Label: [sim(q,sj) > sim(q,sk)] or[sim(q,sj) < sim(q,sk)] Features: Scores on pairs (q,sj) and (q,sk) provided by multiple base similarity measures Learn a probabilistic model using logistic regression Prob([sim(q,sj) > sim(q,sk)] | q,sj,sk;w) ,sk to the same query q
Experiments Data: Query suggestion dataset [Metzler et al. 07] Query shell oil credit card shell oil credit card texaco credit card tarrant county college fresno city college tarrant county college dallas county schools Suggestion shell gas cards Label Excellent Fair Bad Good |Q| = 122, |(Q,S)| = 4852; {Ex,Good} vs. {Fair,Bad} Results 10-fold cross-validation Evaluation metrics: AUC and Precision@k
AUC Scores 0.606 12 0.617 11 0.626 10 0.627 9 0.627 8 7 0.664 6 0.691 5 0.703 4 3 0.735 2 0.739 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Precision@3 0.389 12 0.444 11 0.456 10 0.456 9 0.456 8 7 0.436 6 0.483 5 0.508 4 3 0.556 2 0.569 1 0 0.1 0.2 0.3 0.4 0.5 0.6
Conclusions Web-relevance New term-weighting scheme from keyword extraction Outperform existing methods on query suggestion Learning similarity Fit the application better suggestion ranking Learning similarity function vs. learning ranking function Future work Experiment with alternative combination methods Explore other probabilistic models for similarity Apply our similarity measures to different tasks
