Efficiently representing word sense probabilities

• US 8,280,721 B2
• Filed: 08/29/2008
• Issued: 10/02/2012
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Snow, Rion, Thione, Giovanni Lorenzo, Waterman, Scott A., Walters, Chad, Converse, Timothy
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sirjani, Fariba
• Application Number:
  US12/200,999
• Publication Number:
  US 20090094019A1
• Time in Patent Office: 1,495 Days
• Field of Search: 704/1, 704/7, 704/9, 704/10, 704/270
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

Word sense probabilities are compressed for storage in a semantic index. Each word sense for a word is mapped to one of a number of “buckets” by assigning a bucket score to the word sense. A scoring function is utilized to assign the bucket scores that maximizes the entropy of the assigned bucket scores. Once the bucket scores have been assigned to the word senses, the bucket scores are stored in the semantic index. The bucket scores stored in the semantic index may be utilized to prune one or more of the word senses prior to construction of the semantic index. The bucket scores may also be utilized to prune and rank the word senses at the time a query is performed using the semantic index.

Claims

1. A computer-implemented method for efficiently representing word sense probabilities, the method comprising performing computer-implemented operations for:

identifying by way of a computer one or more word senses associated with a word;

obtaining by way of the computer a word sense probability associated with each of the word senses;

mapping each word sense to exactly one of a plurality of N-bit binary numbers by generating a monotonic mapping between the word sense probabilities and the N-bit binary numbers by way of the computer, the N-bit binary numbers mapped to each word sense based upon the word sense probability and whereby approximately equal percentages of the word sense probabilities are associated with each N-bit binary number; and

storing the N-bit binary number mapped to each word sense in a semantic index by way of the computer.

2. The method of claim 1, further comprising utilizing the N-bit binary numbers stored in the semantic index to prune one or more of the word senses prior to construction of the semantic index.

3. The method of claim 1, further comprising utilizing the N-bit binary numbers stored in the semantic index to rank the word senses when a query is performed.

4. The method of claim 1, further comprising utilizing the N-bit binary numbers stored in the semantic index to prune one or more of the word senses when a query is performed.

5. A computer storage medium that is not a signal having computer executable instructions stored thereon which, when executed by a computer, cause the computer to:

store a semantic index;

identify one or more word senses associated with a word;

obtain a word sense probability for each of the word senses;

map each word sense to exactly one of a plurality of N-bit binary numbers by assigning an N-bit binary number to the word sense based upon the word sense probability such that a monotonic mapping exists between the word sense probabilities and the N-bit binary numbers, whereby approximately equal percentages of the word sense probabilities are associated with each of the plurality of N-bit numbers; and

to

store the N-bit binary number assigned to each word sense probability in the semantic index.

6. The computer storage medium of claim 5, wherein each word sense probability identifies a probability that an associated word refers to a corresponding word sense.

7. The computer storage medium of claim 6, comprising further computer executable instructions which, when executed by the computer, will cause the computer to utilize the N-bit binary numbers stored in the semantic index to prune one or more of the word senses prior to construction of the semantic index.

8. The computer storage medium of claim 7, comprising further computer executable instructions which, when executed by the computer, will cause the computer to utilize the N-bit binary numbers stored in the semantic index to rank the word senses when a query is performed.

9. The computer storage medium of claim 8, comprising further computer executable instructions which, when executed by the computer, will cause the computer to utilize the N-bit binary numbers stored in the semantic index to prune one or more of the word senses at the time a query is performed.

10. A computing system for efficiently representing word sense probabilities, the computing system comprising:

a central processing unit;

a memory; and

a mass storage device coupled to the central processing unit storing a semantic index and program code that is executable by the central processing unit and which, when executed by the central processing unit, will cause the computing system to identify one or more word senses associated with a word, to obtain a word sense probability for each of the word senses, to create a mapping between each word sense and one of a plurality of N-bit binary numbers by assigning exactly one of the plurality of N-bit binary numbers to each word sense such that word senses having greater word sense probabilities are assigned greater N-bit binary numbers than word senses having lesser word sense probabilities and such that approximately equal percentages of the word sense probabilities are associated with each of the plurality of N-bit binary numbers, to store the N-bit binary number assigned to each word sense probability in the semantic index, and to utilize the N-bit binary numbers stored in the semantic index to prune one or more of the word senses prior to construction of the semantic index, to prune one or more of the word senses at the time a query is performed, or to rank the word senses when a query is performed.