Information Retrieval Cycle
Source
Selection Resource
Query
Formulation Query
Search Results
Selection Documents
System discovery
Vocabulary discovery
Concept discovery
Document discovery Examination Information
source reselection
Delivery
IR Model - Boolean model
• Each document or query is treated as a “bag” of words or terms.
• A weight wij > 0 is associated with each term t of document D
• Boolean Queries are queries using AND, OR and NOT to join query terms
• Is precise: document matches condition or not (exact match)
• Simplest IR model
• Use cases - Email, library catalog, Mac OS X Spotlight
• Weaknesses
• Users must learn Boolean logic
• Boolean logic insufficient to capture the richness of language
• No control over size of result set: either too many hits or none
• When do you stop reading? All documents in the result set are considered
“equally good”
• What about partial matches? Documents that “don’t quite match”2 the query
IR Model - Vector Space Model
• Retrieve documents based on how close the document is to the query
• Documents are also treated as a “bag” of words or terms.
• Each document is represented as a vector.
N
• However, the term weights are no longer 0 or 1. wi , j tf i , j log
ni
• Each term weight is computed based on some
wi , j weight assigned to term i in document j
• variations of TF or TF-IDF scheme.
• Term weights consist of two components tf i, j number of occurrence of term i in document j
• Term frequency : Local: how important is the term in
this document? N number of documents in entire collection
• Inverse document frequency : Global: how important is
the term in the collection? ni number of documents with term i
• Terms that appear often in a document should
get high weights
• Terms that appear in many documents should get
low weights
Retrieval in vector space model
Relevance of di to q: Cosine similarity (the
cosine of the angle between the two vectors)
commonly used in text clustering
Sim ( D, Q) (ai * bi )
Dot product
(a * b ) i i
Sim ( D, Q) i
Cosine
ai * bi
2 2
i i
2 (ai * bi )
Dice Sim ( D, Q) i
ai bi
2 2
i i
Jaccard (a * b ) i i
Sim ( D, Q) i
a b (a * b )
2 2 4
i i i i
i i i
An Example
• A document space is defined by three • In similarity matching (cosine):
terms:
• q=(1, 1, 0)
• hardware, software, users
• the vocabulary
• S(q, A1)=0.71,
• S(q, A2)=0.71,
• A set of documents are defined as:
• S(q, A3)=0,
• A1=(1, 0, 0), A2=(0, 1, 0), A3=(0, 0, 1)
• A4=(1, 1, 0), A5=(1, 0, 1), A6=(0, 1, 1)
• S(q, A4)=1,
• A7=(1, 1, 1) A8=(1, 0, 1). A9=(0, 1, 1) • S(q, A5)=0.5,
• If the Query is “hardware and software” • S(q, A6)=0.5,
• S(q, A7)=0.82,
• what documents should be retrieved?
• S(q, A8)=0.5,
• S(q, A9)=0.5
• In Boolean query matching: • Document retrieved set (with ranking)=
• document A4, A7 will be retrieved (“AND”) • {A4, A7, A1, A2, A5, A6, A8, A9}
• retrieved: A1, A2, A4, A5, A6, A7, A8, A9 5
(“OR”)
Vector Space Model: A Running Example
A Running Example
7
A Running Example
8
A Running Example
• Step 6 – Create an indexing file
This is a data mine
mining course. This is a data mining course ID word doc freq
coursex1, datax1, minex1
1 course 1
2 data 2
study mine text 3 interest 1
We are studying We are studying text mining Text mining is
text mining. Text a subfieldmine
of data mining 4 mine 3
mining is a
subfield of data
mine 5 study 1
mining. 6 subfield 1
datax1, minex3, studyx1, subfieldx1, textx2 7 text 2
Mining text is mine interest
Mining text is interesting and I am
interesting, and I interested in it interest
am interested in
it.
interestx2, minex1, textx1
9
A Running Example
• Step 7 – Create the vector space model
This is a data mine
This is a data mining course
mining course. document
ID word
frequency
coursex1, datax1, minex1
(1, 1, 0, 1, 0, 0, 0) 1 course 1
2 data 2
We are studying
study mine textmine
We are studying text mining Text mining is 3 interest 1
text mining. Text a subfield of data mining 4 mine 3
mining is a mine 5 study 1
subfield of data
datax1, minex3, studyx1, subfieldx1, textx2
mining. 6 subfield 1
(0, 1, 0, 3, 1, 1, 2) 7 text 2
Mining text is
mine interest
Mining text is interesting and I am
interesting, and I interested in it
am interested in
it.
interest
interestx2, minex1, textx1
10
(0, 0, 2, 1, 0, 0, 1)
A Running Example
• Step 8 – Compute the inverse document frequency
total documents
IDF ( word ) log
document frequency
This is a data
mining course. document
ID word IDF
frequency
(1, 1, 0, 1, 0, 0, 0)
1 course 1 0.477
2 data 2 0.176
3 interest 1 0.477
We are studying 4 mine 3 0
text mining. Text
5 study 1 0.477
mining is a
subfield of data
(0, 1, 0, 3, 1, 1, 2) 6 subfield 1 0.477
mining. 7 text 2 0.176
Mining text is
interesting, and I
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
11
A Running Example
• Step 9 – Compute the weights of the words
w( word i ) TF ( word i ) IDF ( word i )
This is a data TF ( word i ) number of times word i appears in the document
mining course.
(1, 1, 0, 1, 0, 0, 0) document
ID word IDF
(0.477, 0.176, 0, 0, 0, 0, 0) frequency
1 course 1 0.477
2 data 2 0.176
We are studying
text mining. Text 3 interest 1 0.477
mining is a
subfield of data
(0, 1, 0, 2, 1, 1, 2) 4 mine 3 0
mining. (0, 0.176, 0, 0, 0.477, 0.477, 0.352)5 study 1 0.477
6 subfield 1 0.477
7 text 2 0.176
Mining text is
interesting, and I
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
(0, 0, 0.954, 0, 0, 0, 0.176)
12
P. 12
A Running Example
• Step 10 – Normalize all documents to unit length
w( word i )
w( word i )
This is a data w2 ( word1 ) w2 ( word 2 ) w2 ( word n )
mining course.
(1, 1, 0, 1, 0, 0, 0) ID word
document
frequency IDF
(0.938, 0.346, 0, 0, 0, 0, 0)
1 course 1 0.477
2 data 2 0.176
We are studying
3 interest 1 0.477
text mining. Text
mining is a 4 mine 3 0
subfield of data
(0, 1, 0, 3, 1, 1, 2)
5 study 1 0.477
mining.
(0, 0.225 0, 0, 0.611, 0.611, 0.450) 6 subfield 1 0.477
Mining text is 7 text 2 0.176
interesting, and I
am interested in (0, 0, 2, 1, 0, 0, 1)
it.
(0, 0, 0.983, 0, 0, 0, 0.181)
13
A few notes on BM25
• Okapi BM25 (BM is an abbreviation of best matching) is a ranking function
used by search engines to estimate the relevance of documents to a given
search query.
• BM25 is a bag-of-words retrieval function that ranks a set of documents based
on the query terms appearing in each document, regardless of their proximity
within the document.
• It is based on the probabilistic retrieval framework
The more words in common with
query, the better.
BM25 continuedRepetitions of query words is good
Squashing function-first
word occurrence is most
important
Common words less important
[Link]
•N: Total number of documents in the collection
•avgdl: Average document length in the
collection (here, avgdl = 4)
•D(w): Number of documents containing the N=6 avgdl=4
word w
•idf(w): Inverse document frequency of word w,
calculated as:
IDF(w) = Log((N – N(w) + b)/(N(w) + b))
IDF(w) = Log((6 – N(w) + .5)/(N(w) + .5))
•dl(D): Length of document D
BM25(Q,D1) = Sum of all matching terms calculates using : (D1(w)*(1+k)/(D1(w)+ k((1-b)+ (b*dl(D1)/avgdl))))* log(idf(w))
•Query Q = "a c h" , Document D1 = "abcbd"
•D1(a) = 1, D1(c) = 1, D1(h) = 0 (since "h" is not in D1) , dl(D1) = 5 (length of D1)
BM25(Q,D1)= (1*(1+1)/(1+1*(.5+(.5-5)/4)))*log(4.5/2.5) + (1*(1+1)/(1+1*(.5+(.5-5)/4)))* log(4.5/2.5)
•Query Q = "a c h" , Document D6 = “bghh"
•D1(a) = 0, D1(c) = 0, D1(h) = 2, dl(D6) = 5 (length of D6)
BM25(Q,D6)= (2*(1+1)/(2+1*(.5+(.5-5)/4)))*log(5.5/1.5)
k1, k2 and K are parameters whose values are set empirically & dl is doc length
BM25 Example:
• Query with two terms, “president lincoln”, (qf = 1)
• No relevance information (r and R are zero)
• N = 500,000 documents
• “president” occurs in 40,000 documents (n1 = 40, 000)
• “lincoln” occurs in 300 documents (n2 = 300)
• “president” occurs 15 times in doc (f1 = 15)
• “lincoln” occurs 25 times (f2 = 25)
• document length is 90% of the average length (dl/avdl = .9)
• k1 = 1.2, b = 0.75, and k2 = 100
• K = 1.2 · (0.25 + 0.75 · 0.9) = 1.11
BM25 Example
PAGE RANK ALGORITHM
Example problems
[Link] IR system returns 12 relevant documents and 10 irrelevant
documents. There are a total of 25 relevant documents in the
collection. What is the precision of the system on this search and what
is the recall.
Precision = (Number of relevant items retrieved) / (Total number of
retrieved items)
Recall = (Number of relevant items retrieved) / (Total number of
relevant items)
Precision = 12 / 22
Recall = 12 / 25