Representation of orthography in a continuous vector space

• US 7,353,164 B1
• Filed: 09/13/2002
• Issued: 04/01/2008
• Est. Priority Date: 09/13/2002
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bellegarda, Jerome R.
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Assistant Examiner(s): Ng; Eunice
• Application Number:
  US10/242,849
• Time in Patent Office: 2,027 Days
• Field of Search: 704 1- 10
• US Class Current: 704/1
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G10L 15/187 Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams

Abstract

An orthographic anchor for each word in a dictionary is created in an orthographic space by mapping the words and a set of letter patterns characteristic of the words into the orthographic space. In one aspect the orthographic anchors are row or column vectors resulting from a decomposition of a matrix of feature vectors created by the mapping. In another aspect, a pronunciation for an input word is modeled based on a set of candidate phoneme strings that have pronunciations close to the input word in the orthographic space.

Claims

1. A computerized method comprising:

mapping words in a dictionary and a set of letter patterns that are characteristic of the words into an orthographic space to create orthographic anchors, each orthographic anchor corresponding to a word in the dictionary, wherein the mapping comprises;

creating a matrix of feature vectors from the letter patterns and the words;

decomposing the matrix into row vectors and column vectors; and

selecting vectors from one of the row vectors and column vectors as the orthographic anchors.

2. The computerized method of claim 1, wherein selecting vectors comprises:

scaling the vectors by a singular values of a diagonal matrix used in the decomposition.

3. The computerized method of claim 1, wherein decomposing the matrix (W) comprises performing a singular value decomposition

W=USV^T

where N is the number of letter patterns, M is the number of words in the dictionary, U is a N×

R left singular matrix containing the row vectors u_i with 1≦

i≦

N, S is a R×

R diagonal matrix of singular values s₁≧

s₂≧

. . . ≧

s_R>

0, V^[[T]] is a M×

R right singular matrix containing the column vectors v_j with 1≦

j≦

M, R<

<

M, N is the order of the decomposition, and ^T denotes matrix transposition.

4. The computerized method of claim 1 further comprising:

weighting each entry w_ij in the matrix (W) to reflect the extent to which each letter pattern t_i appeared in each word w_j using

$w_{\mathrm{ij}}=\left(1-{\mathrm{\varepsilon <br><br>}}_i\right)<br><br>\frac{c_{i,j}}{n_j}$

where c_i,j is the number of times t_i occurs in word w_j, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in words of the dictionary.

5. The computerized method of claim 1 further comprising:

determining which letter patterns are members of the set based on the words in the dictionary.

6. The computerized method of claim 1, wherein the dictionary comprises an association between words and word characteristics.

7. The computerized method of claim 1 further comprising:

determining a characteristic of an input word based on closeness between the orthographic anchors and a representation of the word in the orthographic space.

8. The computerized method of claim 7, wherein the characteristic is selected from the group consisting of word family, declination class, and pronunciation.

9. The computerized method of claim 7 further comprising:

creating a representation of the input word in the orthographic space.

10. A machine-readable medium having instructions to cause a machine to perform a method comprising:

mapping words in a dictionary and a set of letter patterns that are characteristic of the words into an orthographic space to create orthographic anchors, each orthographic anchor corresponding to a word in the dictionary, wherein the mapping comprises;

creating a matrix of feature vectors from the letter patterns and the words;

decomposing the matrix into row vectors and column vectors; and

selecting vectors from one of the row vectors and column vectors as the orthographic anchors.

11. The machine-readable medium of claim 10, wherein selecting vectors comprises:

scaling the vectors by a singular values of a diagonal matrix used in the decomposition.

12. The machine-readable medium of claim 10, wherein decomposing the matrix (W) comprises performing a singular value decomposition

W=USV^T

where N is the number of letter patterns, M is the number of words in the dictionary, U is a N×

R left singular matrix containing the row vectors u_i with 1≦

i≦

N, S is a R×

R diagonal matrix of singular values s₁≧

s₂≧

. . . ≧

s_R>

0, V^[[T]] is a M×

R right singular matrix containing the column vectors v_j with 1≦

j≦

M, R<

<

M, N is the order of the decomposition, and ^T denotes matrix transposition.

13. The machine-readable medium of claim 10, wherein the method further comprises:

weighting each entry w_ij in the matrix (W) to reflect the extent to which each letter pattern t_i appeared in each word w_j using

$w_{\mathrm{ij}}=\left(1-{\mathrm{\varepsilon <br><br>}}_i\right)<br><br>\frac{c_{i,j}}{n_j}$

where c_i,j is the number of times t_i occurs in word w_j, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in words of the dictionary.

14. The machine-readable medium of claim 10, wherein the method further comprises:

determining which letter patterns are members of the set based on the words in the dictionary.

15. The machine-readable medium of claim 10, wherein the dictionary comprises an association between words and word characteristics.

16. The machine-readable medium of claim 10, wherein the method further comprises:

determining a characteristic of an input word based on closeness between the orthographic anchors and a representation of the word in the orthographic space.

17. The machine-readable medium of claim 16, wherein the characteristic is selected from the group consisting of word family, declination class, and pronunciation.

18. The machine-readable medium of claim 16, wherein the method further comprises:

creating a representation of the input word in the orthographic space.

19. A system comprising:

a processing unit coupled to a memory through a bus; and

an orthographic anchor process executed from the memory by the processing unit to cause the processing unit to map words in a dictionary and a set of letter patterns that are characteristic of the words into an orthographic space to create orthographic anchors, each orthographic anchor corresponding to a word in the dictionary, wherein the orthographic anchor process further causes the processing unit, when mapping words, to create a matrix of feature vectors from the letter patterns and the words, decompose the matrix into row vectors and column vectors, and select vectors from one of the row vectors and column vectors as the orthographic anchors.

20. The system of claim 19, wherein the orthographic anchor process further causes the processing unit, when selecting vectors to scale the vectors by a singular values of a diagonal matrix used in the decomposition.

21. The system of claim 19, wherein the orthographic anchor process further causes the processing unit, when decomposing the matrix (W), to perform a singular value decomposition

W=USV^T

where N is the number of letter patterns, M is the number of words in the dictionary, U is a N×

R left singular matrix contain the row vectors u_i with 1≦

i≦

N, S is a R×

R diagonal matrix of singular values s₁≧

s₂≧

. . . ≧

s_R>

0, V^[[T]] is a M×

R right singular matrix contain the column vectors v_j with 1≦

j≦

M, R<

<

M, N is the order of the decomposition, and ^T denotes matrix transposition.

22. The system of claim 19, wherein the orthographic anchor process further causes the processing unit to weight each entry w_ij in the matrix (W) to reflect the extent to which each letter pattern t_i appeared in each word w_j using

$w_{\mathrm{ij}}=(1-{\varepsilon }_{}$

i ) ⁢

c i , j n j

where c_i,j is the number of times t_i occurs in word w_j, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in words of the dictionary.

23. The system of claim 19, wherein the orthographic anchor process further causes the processing unit to determine which letter patterns are members of the set based on the words in the dictionary.

24. The system of claim 19, wherein the dictionary comprises an association between words and word characteristics.

25. The system of claim 19 further comprising an analysis process executed from the memory by the processing unit to cause the processing unit to determine a characteristic of an input word based on closeness between the orthographic anchors and a representation of the word in the orthographic space.

26. The system of claim 25, wherein the characteristic is selected from the group consisting of word family, declination class, and pronunciation.

27. The system of claim 25, wherein the analysis process further causes the processing unit to create a representation of the input word in the orthographic space.

28. An apparatus comprising:

means for receiving a dictionary; and

means for mapping words in the dictionary and a set of letter patterns that are characteristic of the words into an orthographic space to create orthographic anchors, each orthographic anchor corresponding to a word in the dictionary, wherein the means for mapping comprises;

means for creating a matrix of feature vectors from the letter patterns and the words; and

means for decomposing the matrix into row vectors and column vectors, vectors from one of the row vectors and the column vectors being selected as the orthographic anchors.

29. The apparatus of claim 28, wherein the means for mapping further comprises:

means for scaling the vectors by a singular values of a diagonal matrix used in the decomposition.

30. The apparatus of claim 28, wherein the means for decomposing the matrix (W) performs a singular value decomposition

W=USV^T

where N is the number of letter patterns, M is the number of words in the dictionary, U is a N×

R left singular matrix containing the row vectors u_i with 1≦

i≦

N, S is a R×

R diagonal matrix of singular values s₁≧

s₂≧

. . . ≧

s_R>

0, V^[[T]] is a M×

R right singular matrix containing the column vectors v_j with 1≦

j≦

M, R<

<

M, N is the order of the decomposition, and ^T denotes matrix transposition.

31. The apparatus of claim 28 further comprising:

means for weighting each entry w_ij in the matrix (W) to reflect the extent to which each letter pattern t_i appeared in each word w_j using

$w_{\mathrm{ij}}=\left(1-{\mathrm{\varepsilon <br><br>}}_i\right)<br><br>\frac{c_{i,j}}{n_j}$

where c_i,j is the number of times t_i occurs in word w_j, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in words of the dictionary.

32. The apparatus of claim 28 further comprising:

means for determining which letter patterns are members of the set based on the words in the dictionary.

33. The apparatus of claim 28 wherein the dictionary comprises an association between words and word characteristics.

34. The apparatus of claim 28 further comprising:

means for determining a characteristic of an input word based on closeness between the orthographic anchors and a representation of the word in the orthographic space.

35. The apparatus of claim 34, wherein the characteristic is selected from the group consisting of word family, declination class, and pronunciation.

36. The apparatus of claim 34 further comprising:

means for creating a representation of the input word in the orthographic space.