Transcript ppt

A Webbased Kernel Function for
Measuring the Similarity of
Short Text Snippets
Mehran Sahami
Timothy D. Heilman
Introduction
Wish to determine how similar two
short text snippets are.
 High degree of semantic similarity

United Nations Secretary General vs
Kofi Annan
 AI vs Articial Intelligence


Share terms

graphical models vs
graphical interface
5%
Related Work
Query expansion techniques
 Other means of determining query
similarity
 Set overlap (intersection)
 SVM for text classification

Latent Semantic Kernels (LSK)
 Semantic Proximity Matrix


Cross-lingual techniques
10%
A New Similarity Function

x represent a short text snippet
(query) to a search engine S
 R (x ) be the set of n retrieved
documents d1 , d 2 ,..., d n
 Compute the TFIDF term vector vi for
each document di  R(x)
 Truncate each vector vi to include its
m highest weighted term
15%
Normalize

Let C (x ) be the centroid of the L2
normalized vector vi
C ( x) 

n
1
n

i 1
vi
vi 2
Let QE(x) be the L2 normalization of the
centroid C(x)
C ( x)
QE ( x) 
C ( x)
2
20%
Kernel Function
K ( x, y )  QE ( x)  QE ( y )
25%
Initial Results with Kernel

Three genres of text snippet matching
Acronyms
 Individuals and their positions
 Multi-faceted terms

30%
Acronyms
Text1
Text2 Kernel
Cosine
Set
Overlap
Support vector machine
SVM
0.812 0.0
0.110
Portable document format
PDF
0.732 0.0
0.060
Artificial intelligence
AI
0.831 0.0
0.255
Artificial insemination
AI
0.391 0.0
0.000
term frequency inverse
document frequency
tf idf
0.831 0.0
0.125
term frequency inverse
document frequency
tfidf
0.507 0.0
0.060
35%
Individuals and their positions
40%
Multi-faceted terms
45%
Related Query Suggestion
Kernel function K (u, qi ) for qi  Q
 u is any newly issued user query


A repository Q of approximately 116 million
popular user queries issued in 2003,
determined by sampling anonymized web
search logs from the Google search engine
50%
Algorithm





Given user query u and list of matched
queries from repository
Output list Z of queries to suggest
Initialize suggestion list Z  
Sort kernel scores K (u,q i ) in descending
order to produce an ordered list L  (q1 , q2 ,..., qk )
of corresponding queries qi
MAX is set to the maximum number of
suggestions
55%
Post-Filter
|q| denotes the number of terms in query q
60%
Evaluation of
Query Suggestion System
1.
2.
3.
4.
5.
suggestion is totally off topic.
suggestion is not as good as original
query.
suggestion is basically same as original
query.
suggestion is potentially better than
original query.
suggestion is fantastic - should suggest
this query since it might help a user find
what they're looking for if they issued it
instead of the original query.
65%
Evaluations
Original
Query
california
lottery
Suggested Queries
Kernel
Score
Human
Rating
california lotto home
0.812
3
winning lotto numbers in california
0.792
5
california lottery super lotto plus
0.778
3
0.832
3
0.822
4
valentines day greeting cards
0.758
4
I love you valentine
0.736
2
new valentine one
0.671
1
valentines 2003 valentine's day
day
valentine day card
70%
Average ratings at
various kernel thresholds
75%
Average ratings versus average
number of query suggestions
80%
Application in QA
K("Who shot Abraham Lincoln", "John
Wilkes Booth") = 0.730
 K("Who shot Abraham Lincoln",
"Abraham Lincoln") = 0.597

85%
Conclusion
A new kernel function for measuring
the semantic similarity between pairs
of short text snippets
 The first is improvement in the
generation of query expansions with
the goal of improving the match score
for the kernel function

Term Weighting Scheme

The weight wi , j associated with the
term ti in document d j is defined to
be : w  tf  log( N )
i, j
i, j
dfi
Where tfi , j is the frequency of ti in d j
 N is the total number of ducuments ,
and dfi is the total number of
documents that contain ti

Lp Norm


Given by:
Most common cases
P=1 ,This is the L1 norm, which is also
called Manhattan distance
 P=2 ,This is the L2 norm, which is also
called the Euclidean distance
 P= , This is the L norm, also called the
infinity norm or the Chebyshev norm
