US2005228778A1PendingUtilityA1
System and method for retrieving documents based on mixture models
Est. expiryApr 5, 2024(expired)· nominal 20-yr term from priority
Inventors:Michael P. Perrone
G06F 16/334
47
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A system and method implemented by a computer for performing query based electronic document retrieval implementing a Markov process model adapted for determining a relationship or relevance between documents. The system ranks documents for retrieval based on their relevance measure. The model calculates the measure of relevance that a document from a given database is relevant to a given query. The method learns the Markov models mixture coefficients from the document database so as to maximize the relevance measure of the documents being retrieved. The method requires only that a similarity measure, D(d,d′), between two documents be specified. Any existing method may be used for generating a model that is at least as good as the chosen similarity measure.
Claims
exact text as granted — not AI-modified1 . A method of implementing a computer for retrieving documents in a database comprising a plurality of electronic documents, said method comprising the steps of:
a) receiving a query document, b) applying a Markov Process for calculating a relevance measure of each document in said database to the query document; and c) outputting results of those database documents most relevant to the query document from said applied Markov process.
2 . The method of implementing a computer as claimed in claim 1 , wherein said step b) of implementing a Markov Process includes a step of: determining a state-to-state Markov Transition matrix having elements, whereby the measure of a document, d, being relevant at time t is equal to the Markov transition matrix multiplied by the probability of a document being relevant at time t−1, wherein the measure of a document being relevant to a query document is a function of time.
3 . The method of implementing a computer as claimed in claim 2 , wherein for any time t, the additional step of obtaining a different set of relevance measures for each said documents, said method including determining a best mixture of those relevance measures at each time step.
4 . The method of implementing a computer as claimed in claim 3 , wherein said step of determining a best mixture of those relevance measures at each time step comprises:
calculating a set of weighted averages, a relevance measure being multiplied by a weight and then summed according to the following: P ( d | q ) = ∑ t , d ′ P ( d | d ′ , t ) P ( t | q ) P ( d ′ | t = 0 , q ) where p(d|q) is the probability that document d is relevant to given query q independent of time, P(t|q) is a mixture coefficient representing the probability that a t th time step is relevant to a query document q, P(d′|d, t) is the probability of document state d transition to a state d′ as dictated by said Markov Transition matrix at t th time step, and, P(d′|t=0, q) is the initial state of document relevance.
5 . The method of implementing a computer as claimed in claim 4 , wherein the Markov Transition matrix is defined as
T
(
d
|
d
′
)
=
ⅇ
-
β
D
(
d
,
d
′
)
∑
d
′
ⅇ
-
β
D
(
d
,
d
′
)
where, where β is a tuning parameter, and D(q,d) is a distance function measuring the relevance between d and d′ and comprises a value between 0 and 1.
6 . The method of implementing a computer as claimed in claim 5 , further including the step of: providing a similarity relevance measure between two documents d, d′ for said distance function D.
7 . The method of implementing a computer as claimed in claim 6 , wherein the similarity relevance measure includes one of: implementing a Maximum Likelihood estimate, or a Minimum Square Error estimate, or like cost minimization estimate.
8 . The method of implementing a computer as claimed in claim 6 , further including the steps of learning the Markov models mixture coefficients from the document database so as to maximize the relevance measure of the documents being retrieved.
9 . The method of implementing a computer as claimed in claim 5 , further including the step of training the parameters of the system.
10 . The method of implementing a computer as claimed in claim 5 , further including the step adapting system parameters in real time.
11 . The method of implementing a computer as claimed in claim 4 , further including the step of applying document pre-processing to remove noise content from the document for improving document retrieval performance.
12 . The method of implementing a computer as claimed in claim 4 , wherein said step of determining a best mixture of those relevance measures further includes the step of reducing said Markov Transition matrix into a sparse matrix by removing all element values below a threshold; and, implementing a sparse matrix method to accelerate the determination.
13 . A system for retrieving documents in a database comprising a plurality of electronic documents, said method system comprising:
means for receiving a query document, means implementing a Markov Process for calculating the relevance measure of each document in said database to the query document; and means for outputting results of those database documents most relevant to the query document resulting from said applied Markov process.
14 . The system as claimed in claim 13 , wherein said means for implementing a Markov Process includes functionality adapted to: determine a state-to-state Markov Transition matrix having elements, whereby the measure of a document, d, being relevant at time t is equal to the Markov transition matrix multiplied by the probability of a document being relevant at time t−1, wherein the measure of a document being relevant to a query document is a function of time.
15 . The system as claimed in claim 14 , wherein said means for implementing a Markov Process includes functionality adapted to: obtain, for any time t, a different set of relevance measures for each said documents, and determine a best mixture of those relevance measures at each time step.
16 . The system as claimed in claim 15 , wherein said means for implementing a Markov Process for determining a best mixture of those relevance measures at each time step further includes functionality adapted to: calculate a set of weighted averages, a relevance measure being multiplied by a weight and then summed according to the following:
P
(
d
|
q
)
=
∑
t
,
d
′
P
(
d
|
d
′
,
t
)
P
(
t
|
q
)
P
(
d
′
|
t
=
0
,
q
)
where p(d|q) is the probability that document d is relevant to given query q independent of time, P(t|q) is a mixture coefficient representing the probability that a t th time step is relevant to a query document q, P(d′|d, t) is the probability of document state d transition to a state d′ as dictated by said Markov Transition matrix at t th time step, and, P(d′|t=0, q) is the initial state of document relevance.
17 . The system as claimed in claim 16 , wherein said Markov Transition matrix is defined as
T
(
d
|
d
′
)
=
ⅇ
-
β
D
(
d
,
d
′
)
∑
d
′
ⅇ
-
β
D
(
d
,
d
′
)
where, where β is a tuning parameter, and D(q,d) is a distance function measuring the relevance between d and d′ and comprises a value between 0 and 1.
18 . The system as claimed in claim 17 , further including means for providing a similarity relevance measure between two documents d, d′ for said distance function D.
19 . The system as claimed in claim 18 , wherein the similarity relevance measure includes one of: implementing a Maximum Likelihood estimate, or a Minimum Square Error estimate, or like cost minimization estimate.
20 . The system as claimed in claim 18 , wherein said means for implementing a Markov Process includes functionality adapted to: learn the Markov models mixture coefficients from the document database so as to maximize the relevance measure of the documents being retrieved.
21 . The system as claimed in claim 17 , further including: means for training the parameters of the system.
22 . The system as claimed in claim 17 , further including: means for adapting system parameters in real time.
23 . The system as claimed in claim 13 , further including means for applying document pre-processing to remove noise content from the document for improving document retrieval performance.
24 . The system as claimed in claim 16 , wherein said means for implementing a Markov Process further comprises means for reducing said Markov Transition matrix into a sparse matrix by removing all element values below a threshold; and, means for implementing a sparse matrix method to accelerate the determination of said best mixture of those relevance measures.
25 . A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for retrieving documents in a database comprising a plurality of electronic documents, said method step comprising:
a) receiving a query document, b) applying a Markov Process for calculating the relevance measure of each document in said database to the query document; and c) outputting results of those database documents most relevant to the query document from said applied Markov process.
26 . The program storage device readable by a machine as claimed in claim 25 , wherein said method step b) of implementing a Markov Process includes a step of: determining a state-to-state Markov Transition matrix having elements, whereby the relevance measure of a document, d, being relevant at time t is equal to the Markov transition matrix multiplied by the probability of a document being relevant at time t−1, wherein the measure of a document being relevant to a query document is a function of time.
27 . The program storage device readable by a machine as claimed in claim 26 , wherein for any time t, the step of obtaining a different set of relevance measures for each said documents, said method steps further including a step of determining a best mixture of those relevance measures at each time step.
28 . The program storage device readable by a machine as claimed in claim 27 , wherein said step of determining a best mixture of those relevance measures at each time step comprises: calculating a set of weighted averages, a relevance measure being multiplied by a weight and then summed according to the following:
P
(
d
|
q
)
=
∑
t
,
d
′
P
(
d
|
d
′
,
t
)
P
(
t
|
q
)
P
(
d
′
|
t
=
0
,
q
)
where p(d|q) is the probability that document d is relevant to given query q independent of time, P(t|q) is a mixture coefficient representing the probability that a t th time step is relevant to a query document q, P(d′|d, t) is the probability of document state d transition to a state d′ as dictated by said Markov Transition matrix at t′ time step, and, P(d′|t=0, q) is the initial state of document relevance.
29 . The program storage device readable by a machine as claimed in claim 28 , wherein the e Markov Transition matrix is defined as
T
(
d
|
d
′
)
=
ⅇ
-
β
D
(
d
,
d
′
)
∑
d
′
ⅇ
-
β
D
(
d
,
d
′
)
where, where β is a turing parameter, and D(q,d) is a distance function measuring the relevance between d and d′ and comprises a value between 0 and 1.
30 . The program storage device readable by-a machine as claimed in claim 29 , further including the step of: providing a similarity relevance measure between two documents d, d′ for said distance function D.
31 . The program storage device readable by a machine as claimed in claim 30 , wherein the similarity measure includes one of implementing a Maximum Likelihood estimate, or a Minimum Square Error estimate, or like cost minimization estimate.
32 . The program storage device readable by a machine as claimed in claim 30 , further including the steps of learning the Markov models mixture coefficients from the document database so as to maximize the relevance measure of the documents being retrieved.
33 . The program storage device readable by a machine as claimed in claim 28 , wherein said step of determining a best mixture of those relevance measures further includes the step of reducing said Markov Transition matrix into a sparse matrix by removing all element values below a threshold; and, implementing a sparse matrix method to accelerate the determination.Join the waitlist — get patent alerts
Track US2005228778A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.