Method for Indexing for Retrieving Documents Using Particles

• US 20090216740A1
• Filed: 02/25/2008
• Published: 08/27/2009
• Est. Priority Date: 02/25/2008
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Gouvea, Evandro B., Harsham, Bret A., Schmidt-Nielsen, Bent, Ramakrishnan, Bhiksha, Weinberg, Garrett
• Granted Patent: US 8,229,921 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3343 using phonetics
• CPC Class Codes: G10L 15/26 Speech to text systems G10L15/08 takes precedence

Abstract

An information retrieval system stores and retrieves documents using particles and a particle-based language model A set of particles for a collection of documents in a particular language is constructed from training documents such that a perplexity of the particle-based language model is substantially lower than the perplexity of a word-based language model constructed from the same training documents. The documents can then be converted to document particle graphs from which particle-based keys are extracted to form an index to the documents. Users can then retrieve relevant documents using queries also in the form of particle graphs.

Claims

1. A computer implemented method for indexing and retrieving documents in a database, comprising:

the steps of;

converting each document in a collection of documents to a document particle graph, the document graph including particles selected from a set of the particles;

extracting, for each document, a set of document keys from the corresponding particle graph;

storing the document keys for each document in an index to a database storing the collection of documents;

converting a query to a query particle graph including a set of query particles, the query graph including particles selected from the set of the particles;

extracting a set of query keys from, the query particle graph;

retrieving relevant documents from the database according to the query keys and the document keys stored in the index; and

outputting the relevant documents to a user.

2. The method of claim 1, in which the set of particles is substantially larger than a number of phonemes in a language of the documents, and substantially smaller than a number of words in the language.

3. The method of claim 1, in which a particular particle traverses word boundaries.

4. The method of claim 1, in which the document and the query are a form of text words.

5. The method of claim 1, in which the document is in a form of text words, and the query is in a form of spoken words.

6. The method of claim 1, in which the document and the query are a form of spoken words.

7. The method of claim 1, in which the document is in a form of spoken words, and the query is in a form of text words.

8. The method of claim 1, in which the query is spoken and the query particle graph is a lattice representing alternate sequential groupings of sound sequences in the spoken query.

9. The method of claim 1, in which the set of particles represent all possible sound sequences that can occur in any query.

10. The method of claim 1, in which the set of particles is derived from a pronunciation of any sequence of words from the document.

11. The method, of claim 1, in which the set of particles identifies the key in any document that the document from other documents.

12. The method of claim 1, in which the document particle graph and the query particle graph are normalized by a spelling-to-pronunciation mechanism.

13. The method of claim 1, in which the particles in the set of particles are acoustically distinct and self-contained.

14. The method of claim 1, in which a predictability of the occurrence of particles must be high.

15. The method of claim 1, in which each particle has a distinctive acoustic structure that distinguish the particle from all other particles, and has a relatively low acoustic variability between different instances of the same particle.

16. The method of claim 1, in which a predictability of an occurrence of a particular particle is relatively high.

17. The method of claim 1m in which the particle set is determined manually.

18. The method of claim 1, in which the particle set is determined heuristically.

19. The method of claim 1, further comprising:

constructing the particle set and a simultaneously optimized particle-based language model using training documents, and in which a perplexity of the particle-based language model is substantially lower than the perplexity of a word-based language model constructed from the same training documents.

20. The method of claim 19, in which the particle set applies expectation maximization to an objective function, and where the objective function considers any combination of:

a size of the set of particles;

errors in representing all documents in a document training set and a query training set;

a retrieval accuracy of using the particle set;

an entropy of a statistical models that represent the set of particles; and

a particle-level language model derived from the documents and the queries in the training sets.

21. The method of claim 1, in which each word in each document is first converted to a phonetic graph that represents all the possible pronunciations of the word, and then converting the phonetic graph to the document particle set.

22. The method of claim 1, further comprising;

rank ordering the relevant documents.

23. The method of claim 20, in which the perplexity of the particle-based language model is at least ten times lower the perplexity of the word-based language model.

24. An information retrieval system, comprising:

means for converting each document in a collection of documents to a document particle graph, the document graph, the document graph including particles selected from a set of the particles;

means for extracting, for each document, a set of document keys from the corresponding particle graph;

means for storing the document keys for each document in an index to a database storing the collection of documents;

means for converting a query to query particle graph including a set of query particles, the query graph including particles selected from the set of the particles;

means for extracting a set of query keys from the query particle graph;

means for retrieving relevant documents from the database according to the query keys and the document keys stored in the index; and

means for outputting the relevant documents to a user.

25. A computer implemented method for indexing and retrieving documents in a database, comprising the steps of:

constructing a particle set from training documents using a particle-based language model, in which a perplexity of the particle-based language model is substantially lower than the perplexity of a word-based language model constructed from the same training documents;

converting each document in a collection of documents to a document particle graph, the document graph including particles selected from the set of the particles;

extracting, for each document, a set of document keys from the corresponding particle graph to form an index to the document; and

retrieving, by a user, relevant documents using queries in a form of a query particle graph and keys extracted from the query particle graph.

26. An information retrieval system, comprising;

a database storing a collection of documents;

an index to the database, in which entries in the index are in the form of particles, in which the particles are selected from a set of particles constructed, from training documents using a particle-based language model, and in which a perplexity of the particle-based language model is substantially lower than the perplexity of a word-based language model constructed from the same training;

documents; and

means for accessing the documents by a user via the index using the particles.