Automatic query refinement

• US 6,941,297 B2
• Filed: 07/31/2002
• Issued: 09/06/2005
• Est. Priority Date: 07/31/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Carmel, David, Farchi, Eitan, Petruschka, Yael
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/210,826
• Publication Number:
  US 20040034632A1
• Time in Patent Office: 1,133 Days
• Field of Search: 707/3, 707/5, 707/7, 342/22, 705/26
• US Class Current: 707/765
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method for Automatic Query Refinement, the method including extracting at least one lexical affinity from at least one document in a search result set of documents, the set resulting from the application of a first query to a document search engine, adding the lexical affinity to the first query, thereby forming a new query, and applying the new query to the document search engine, resulting in a new search result set.

Claims

1. A computer-implemented method for Automatic Query Refinement, the method comprising:

extracting at least one lexical affinity from at least one document in a first search result set of documents D, said set resulting from the application of a first query q to a document search engine;

adding said lexical affinity to said first query, thereby forming a second query; and

applying said second query to said document search engine, resulting in a second search result set.

2. A method according to claim 1 wherein said extracting step comprises extracting a plurality of lexical affinities from said document, and further comprising:

determining the information gain lG(l) of each of said plurality of lexical affinities; and

selecting at least one of said plurality of lexical affinities having the greatest information gain, and wherein said adding step comprises adding said selected lexical affinities.

3. A method according to claim 1 wherein said extracting step comprises extracting said lexical affinity such that said lexical affinity includes exactly one of the terms of said first query.

4. A method according to claim 2 wherein said determining step comprises:

calculating a relevance probability p(D) of said set of documents D to said first query q, wherein p(D) is the probability that a document chosen randomly from D is relevant to q;

calculating an entropy value H(D) of said set D; and

calculating said information gain IG(l) as $\mathrm{IG}<br><br>\left(l\right)=H<br><br>\left(D\right)-\left[\frac{<br><br>D^{+}<br><br>}{<br><br>D<br><br>}<br><br>H<br><br>\left(D^{+}\right)+\frac{<br><br>D^{-}<br><br>}{<br><br>D<br><br>}<br><br>H<br><br>\left(D^{-}\right)\right]$

where l represents said lexical affinity, D⁺ is a target subset of documents of D containing l, and D⁻

is the complement of D⁺.

5. A method according to claim 4 wherein said step of calculating said entropy value H(D) comprises calculating said entropy value as

H(D)=−

p(D) log(p(D))−

(1−

p(D)) log(1−

p(D)).

6. A method according to claim 4 wherein said step of calculating said relevance probability p(V) comprises:

calculating an expectation E(X) of the number X of relevant documents in said first search result set of n documents; and

estimating pa) as $\hat{p}<br><br>\left(D\right)=\frac{E<br><br>\left(X\right)}{n}=\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left(p_i\right)}{n},$

where for said n documents {d₁ . . . d_n} and said first query q, p_i is the probability that document d₁ is relevant to query q.

7. A method according to claim 6 wherein said step of calculating said expectation comprises:

defining an independent variable x_i for each document d₁ representing the relevance of d₁, wherein x_i is set to 1 with probability p_i and to 0 with probability (1−

p_i), and wherein x_i is a binomial independent variable with expectation E(x_i)=p_i and variance Var(x_i)=p_i (1−

p_i); and

calculating E(X) as $E<br><br>\left(X\right)=E<br><br>\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>x_i\right)=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>E<br><br>\left(x_i\right)=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>p_i$

where $X=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>x_i.$

8. A method according to claim 6 and further comprising:

preparing a virtual document from said first query;

determining a search engine score s_max for said virtual document within the context of said first query;

determining a search engine score s_i for each document in said first search results set; and

calculating said relevance probability of each document as p_i=s_i/s_max.

9. A computer-implemented system for Automatic Query Refinement, the system comprising:

means for extracting at least one lexical affinity from at least one document in a first search result set of documents D, said set resulting from the application of a first query q to a document search engine;

means for adding said lexical affinity to said first query, thereby forming a second query; and

means for applying said second query to said document search engine, resulting in a second search result set.

10. A system according to claim 9 wherein said means for extracting comprises means for extracting a plurality of lexical affinities from said document, and wherein the system further comprises:

means for determining the information gain IG(l) of each of said plurality of lexical affinities; and

means for selecting at least one of said plurality of lexical affinities having the greatest information gain, and wherein said means for adding comprises means for adding said selected lexical affinities.

11. A system according to claim 9 wherein said means for extracting comprises means for extracting said lexical affinity such that said lexical affinity includes exactly one of the terms of said first query.

12. A system according to claim 10 wherein said means for determining comprises:

means for calculating a relevance probability p(D) of said set of documents D to said first query q, wherein p(D) is the probability that a document chosen randomly from D is relevant to q;

means for calculating an entropy value H(D) of said set D; and

means for calculating said information gain IG(l) as $\mathrm{IG}<br><br>\left(l\right)=H<br><br>\left(D\right)-\left[\frac{<br><br>D^{+}<br><br>}{<br><br>D<br><br>}<br><br>H<br><br>\left(D^{+}\right)+\frac{<br><br>D^{-}<br><br>}{<br><br>D<br><br>}<br><br>H<br><br>\left(D^{-}\right)\right]$

where l represents said lexical affinity, D⁺ is a target subset of documents of D containing l, and D⁻

is the complement of D⁺.

13. A system according to claim 12 wherein said means for calculating said entropy value H(D) comprises means for calculating said entropy value as

H(D)=−

p(D) log(p(D))−

(1−

p(D)) log(1−

p(D)).

14. A system according to claim 12 wherein said means for calculating said relevance probability p(D) comprises:

means for calculating an expectation E(X) of the number X of relevant documents in said first search result set of n documents; and

means for estimating p(D) as $\hat{p}<br><br>\left(D\right)=\frac{E<br><br>\left(X\right)}{n}=\frac{\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left(p_i\right)}{n},$

where for said n documents {d₁ . . . d_n} and said first query q, p_i is the probability that document d₁ is relevant to query q.

15. A system according to claim 14 wherein said means for calculating said expectation comprises:

means for defining an independent variable x_i for each document d₁ representing the relevance of d₁, wherein x_i is set to 1 with probability p_i and to 0 with probability (1−

p_i), and wherein x_i is a binomial independent variable with expectation E(x_i)=p_i and variance Var(x_i)=(1−

p_i); and

means for calculating E(X) as $E<br><br>\left(X\right)=E<br><br>\left(\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i\right)=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>E<br><br>\left(x_i\right)=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>p_i$

where $X=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i.$

16. A system according to claim 14 and further comprising:

means for preparing a virtual document from said first query;

means for determining a search engine score s_max for said virtual document within the context of said first query;

means for determining a search engine score s_i for each document in said first search results set; and

means for calculating said relevance probability of each document as p_i=S_i/s_max.

17. A computer-implemented program embodied on a computer-readable medium, the computer program comprising:

a first code segment operative to extract at least one lexical affinity from at least one document in a first search result set of documents, said set resulting from the application of a first query to a document search engine;

a second code segment operative to add said lexical affinity to said first query, thereby forming a second query; and

a third code segment operative to apply said second query to said document search engine, resulting in a second search result set.