Ranking Methods for Query Relaxationin Book Search

Momo Kyozuka and Keishi Tajima
Kyoto University, Japan

Background1• Book search situation• Users only have vague memories of the stories• Queries may include wrong keywords

a boy makes paints with blue seeds Searchflowers

Approach2

Problem• Make new queries by removing wrong keywords
a boy makes paints with blue seeds

Search→ Cannot know which words are wrong

Solution• Use every subset as a new query• Rank according to reliability of the subsets

a boy makes paints with blueSearchProposed method

3
Generate all subset queries
blue

seed

makepaintblue

seed

a boy

paintblueseed…

paint…

a boy makes paints withblue seeds.

make…

a boy

…

A sentence query from a user
In the book,seed

Concatenate results

Rank subset queries
based on reliability ofquery words
1a boy

2

a boy

paint

3

a boy

paintblue…

…

…

paintblue

seed

seed
…

31

makeseed

Result of query 1
1. Book 1
2. Book 2
3. Book 3
Result of query 2
1. Book 4
2. Book 5
3. Book 6
Result of query 3
1. Book 7
2. Book 8…

Hypothesis

4

Reliability of each word depends on its semantic role
• Collect sentence queries from users• Parse dependencies of the sentence query and classify words
into four roles
Classify query words

A sentence query from a user
In the book,a boy makes paints withblue seeds.

Semantic roles• Subject• Predicate• Object• Others

a boy

makes

paintssubject

predicateobjectblueseeds

othersobjectData used in our experiments• 37 sentence queries by users• collected from Yahoo! Chiebukuro (a Japanese popular QA site)• question and answer data
• Q : users asked for titles of books based on vague memories• A : questioners found that the answer books were correct
Question

AnswerComment from questioner

I am searching for a bookthat I read when I was achild. In the book, a boy
makes paints with blueseeds.

It may be wrong, but I think
the book is “Real Sky-Blue”.
You can see the design ofthe book in this web page.

I checked the web page andI found that the book is what
I was searching for.
Thank you very much.

• Correct descriptions of target books• collected from the database of National Diet Library of Japan (NDL)

5

Which semantic role is more reliable?
Sentence query• Examine whether each word in thesentence queries also appears in the
database description• Calculate the ratio of the appearing
words in both descriptions for each of
the four roles• Use each ratio as the probability thata query word in each class also
appears in the correct description of
the target bookmakes

paintssubject predicate

object

a boy

blue

seeds

othersobject6

database description

A boy … He makes
paints with wild blue
flowers …

classin user
descriptionin database
description

ratio

subject

43

190.442predicate6230.048

object55

300.545

others34

150.441

The reliability of predicate is lowest

Ranking queries• Proposed method : Probability Ranking Principle (PRP)• Classify query words according to their reliability• Rank queries by their reliability• Baseline 1 : Number of Words method• Rank queries by number of included words• Baseline 2 : TF-IDF• Rank queries by the cosine similarity to the original query in thedescending order7

Probability Ranking Principle (PRP)

e.g.
a boy

paintsseeds

subject

objectobject8

Probability Ranking Principle (PRP)

Book 1a boy paints seeds

SearchNumber of Search Result: 5Book 2
Book 3
Book 4
Book 59Baseline 1: Number of Words method

10• Rank the queries by the number of included words in thedescending order
1

a boy

2

a boy

3

paintsmakes
makes

paints

4

a boy

makes

paints

5

a boy

makes

paints

6

a boy

7

makes

…

…

makes

paints

15

a boy

makes

paints

blue

seeds

blue

seeds
seeds

• Queries composed
4 words• Ranked randomly

blueblueseeds

blue

seeds
…

…
a boy

seeds

…

…
14

blue

seeds
blue

• Queries composed
3 words• Ranked randomlyBaseline 2 : TF-IDF

11a boymakes

paints

blue

seeds

Original

11

111

Subset10101

Experiment• Generate queries with data mentioned in the preliminary
experiment• Question and answer pairs collected in the Japanese QA site

• Use the NDL search engine to execute generated queries• Compare results by Mean Reciprocal Rank (MRR)
and distribution of the rank of target books• Number of Words method has a random factor• the average of 10 runs

12

Result (1)

13

• MRR
PRP

Number of Words

TF-IDF

0.157

0.164

0.121

→ PRP was• better than TF-IDF• worse than Number of Words method

Result (2)14• Distribution of the rank of target books
PRP

Number of Words

TF-IDF

Some queriesranked target
books very low

0〜60000

0〜120000over→ PRP is more stable than Number of Words method0〜60000

Discussion• A query has more words• the probability that the correct description includes all query words
becomes low• The result of this query may not contain the target book

• A query has less words• The number of search results becomes larger• The average rank of the target book becomes lower→ PRP can control this trade-off appropriately

15

Conclusion• Our method consists of two parts
1. Ranking subsets of the original sentence query• Classify words in a subset query into 4 semantic roles• Use reliability of each query word for ranking queries

2. Concatenating the results of subset queries• Conduct an experiment to compare ranking methods• PRP was better than TF-IDF in MRR• PRP was more stable than Number of Words method

16