Study on the Combination of Probabilistic and Boolean IR Models for WWW Documents Retrieval
Masaharu YOSHIOKA Makoto HARAGUCHI Hokkaido University{yoshioka,makoto}@db-ei.eng.hokudai.ac.jp

BackgroundIndex

z Requirement for IR system with large scale text dataz Different IR models
z A probabilistic modelzThe user may not select query term appropriately.
z A Boolean modelzThe user must select query term appropriately.
zA Boolean query formula is expressive but is very
difficult to construct appropriate one.

z Word and phrasal index
z Use ChaSen as morphological analyzer and select noun (noun,unknown, symbol) for word index
z Phrasal index: a pair of adjacent noun terms
zWe use prefixes, postfixes, and numbers in addition to words
that are used for word index
z Database engine: Generic Engine for Transposable Association (GETA)

Objective

道路
交通法
について

ChaSenInput:z Evaluate following IR systems.
z our IR system, which is based on the probabilistic IR model.
z our method for combining probabilistic and Boolean IR models
for clarifying queries.

道路交通法について

Word index 道路, 交通nounnoun
noun-prefixpostpositional particle

Phrasal index !c道路交通, !c交通法

IR System (Probabilistic IR Model)
An Example of Index Extractionz Modified version of OKAPIz Use BM25 formula to calculate each document score(k1 + 1)tf (k3 + 1)qtf
K + tfk3 + qtf
T ∈Q(r + 0.5) /( R − r + 0.5)w(1) = log(n − r + 0.5) /( N − n − R + r + 0.5)

Relevance Feedback∑ w(1)z Pseudo-relevance feedback
z Use top 5 ranked documents of initial retrieval are used as
relevant documents.
z Reject documents with small number of terms in it.
z Query expansionz Use terms in relevant documents as query termsz Max: 300 terms
Rz Rocchio-type feedback

z Term weighting for phrasal terms
z Document score may differ according to the dictionary entry
情報処理→ Word 情報処理
情報科学→ Word 情報, 科学 Phrase !c情報科学∑ qtf iqtf = α * qtf 0 + (1 − α ) * i =1R

qtf = c * qtf cz Discount score for phrasal index

Characteristics of Two IR Models
Assumption of user

Selected Documents

Readability

A probabilistic model

The user may have difficulties toselect appropriate query terms,Documents that do not contain apart of query terms may select as
higher relevant ones.

Difficulties to understandappropriateness of query

A Boolean model

The user can select appropriate
query terms.

Documents that do not satisfy aBoolean formula is not selected

The user can easily understand why
the IR system selects the documents

Reconstruction of a Boolean Query Formulaz Relax an initial Boolean query formula to include given relevant
documents as relevant onez Use terms that exists in all relevant documents and also exists
in an initial query as a candidate to construct a relaxed Boolean
query formulaz Use an initial query for “or” formula

Use initial query for “or” formula
Initial query: (A and B and (C or D))

A and (C or D)

Relevant documents
A, C, E

A, C, D, E

A and C

A, B, C, E

Select candidate terms
1

Combination of Two IR Models

β × w(1) ×0.9
0.8
0.7
0.6
Precisionz Two approachz Use a Boolean IR model first and calculate score of each
retrieved document by using a probabilistic modelz Use a probabilistic IR model first and apply penalty for
documents that do not satisfy a Boolean query formula
zPenalty is calculated by using term importance in BM25

0.5
0.4
0.3

(k3 + 1)qtf
k3 + qtf

β : parameter

zPenalty is calculated for each “and” elementzFor “or” formula, use penalty of a term that has highest
one among them.

0.2
0.1
00

0.1

0.2

0.3

0.4

no0.5
RecallBoolean Construction

0.6

0.7

0.8

0.91

Original

R-P Graph for Different Boolean Query

10.9Conclusion

0.80.7Precision

0.6
0.5
0.4
0.3
0.2

0.1
000.1

0.2

0.3

0.4

no0.5
Recallβ= 0.20.6

β= 1.00.7

β= 2.0R-P Graph for Different β

0.8

0.91z A proposal of our IR system based on a probabilistic IR modelz We confirm the system has better performance in NTCIR-4 submission.
z This system may be good enough to use as a benchmark system.
z A proposal of a combination of two IR models
z User defined Boolean query is not precise enough to retrieve all
relevant documentsz Relaxing an initial Boolean query formula by using relevant documents
improve quality of a Boolean query formulaz Penalty calculation by using a Boolean query formula improves retrieval
performance