EXEMPLAR-BASED NATURAL LANGUAGE PROCESSING

• US 20150347393A1
• Filed: 09/30/2014
• Published: 12/03/2015
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: GRUBER, Thomas R., FUTRELL, Richard L.
• Granted Patent: US 9,430,463 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Systems and processes for exemplar-based natural language processing are provided. In one example process, a first text phrase can be received. It can be determined whether editing the first text phrase to match a second text phrase requires one or more of inserting, deleting, and substituting a word of the first text phrase. In response to determining that editing the first text phrase to match the second text phrase requires one or more of inserting, deleting, and substituting a word of the first text phrase, one or more of an insertion cost, a deletion cost, and a substitution cost can be determined. A semantic edit distance between the first text phrase and the second text phrase in a semantic space can be determined based on one or more of the insertion cost, the deletion cost, and the substitution cost.

Claims

1. A method for processing natural language comprising:

at an electronic device;

receiving a first text phrase;

determining whether editing the first text phrase to match a second text phrase requires one or more of;

inserting a first word into the first text phrase, wherein the second text phrase includes the first word;

deleting a second word from the first text phrase;

wherein the first text phrase includes the second word; and

substituting a third word of the first text phrase with a fourth word, wherein the second text phrase includes the fourth word;

in response to determining that editing the first text phrase to match the second text phrase requires one or more of inserting the first word into the first text phrase, deleting the second word from the first text phrase, and substituting the third word of the first text phrase with the fourth word, determining one or more of;

an insertion cost associated with inserting the first word into the first text phrase;

a deletion cost associated with deleting the second word from the first text phrase; and

a substitution cost associated with substituting the third word of the first text phrase with the fourth word; and

determining, based on the one or more of the insertion cost, the deletion cost, and the substitution cost, a semantic edit distance between the first text phrase and the second text phrase in a semantic space, wherein a degree of semantic similarity between the first text phrase and the second text phrase is based on the semantic edit distance.

2. The method according to claim 1, further comprising:

determining, based on the degree of semantic similarity between the first text phrase and the second text phrase, a first intent associated with the first text phrase; and

performing, based on the first intent, a task associated with the first text phrase.

3. The method according to claim 1, wherein:

the insertion cost associated with inserting the first word into the first text phrase is determined in response to determining that editing the first text phrase to match the second text phrase requires inserting the first word into the first text phrase; and

the insertion cost is determined based on a first predetermined semantic cost and a salience of the first word.

4. The method according to claim 1, wherein:

the deletion cost associated with deleting the second word from the first text phrase is determined in response to determining that editing the first text phrase to match the second text phrase requires deleting the second word from the first text phrase; and

the deletion cost is determined based on a second predetermined semantic cost and a salience of the second word.

5. The method according to claim 1, wherein:

the substitution cost associated with substituting the third word of the first text phrase with the fourth word is determined in response to determining that editing the first text phrase to match the second text phrase requires substituting the third word of the first text phrase with the fourth word; and

the substitution cost is determined based on a salience of the third word, a salience of the fourth word, a semantic similarity between the third word and the fourth word in the semantic space, a first predetermined semantic cost, and a second predetermined semantic cost.

6. The method according to claim 1, wherein:

the insertion cost is determined based on a first predetermined semantic cost and a salience of the first word;

the deletion cost is determined based on a second predetermined semantic cost and a salience of the second word; and

the first predetermined semantic cost is higher than the second predetermined semantic cost.

7. The method according to claim 1, wherein:

the insertion cost is determined based on a first predetermined semantic cost and a salience of the first word;

the deletion cost is determined based on a second predetermined semantic cost and a salience of the second word; and

the substitution cost is determined based on a salience of the third word, a salience of the fourth word, a semantic similarity between the third word and the fourth word in the semantic space, the first predetermined semantic cost, and the second predetermined semantic cost.

8. The method according to claim 7, wherein:

the salience of the first word is based on a frequency of occurrence of the first word in a first corpus;

the salience of the second word is based on a frequency of occurrence of the second word in the first corpus;

the salience of the third word is based on a frequency of occurrence of the third word in the first corpus; and

the salience of the fourth word is based on a frequency of occurrence of the fourth word in the first corpus.

9. The method according to claim 8, wherein the first corpus comprises a plurality of categories that includes a plurality of text phrases, and wherein:

the salience of the first word is based on a proportion of the plurality of categories that include the first word;

the salience of the second word is based on a proportion of the plurality of categories that include the second word;

the salience of the third word is based on a proportion of the plurality of categories that include the third word; and

the salience of the fourth word is based on a proportion of the plurality of categories that include the fourth word.

10. The method according to claim 7, wherein:

the salience of the first word is based on a normalized entropy of the first word in a second corpus;

the salience of the second word is based on a normalized entropy of the second word in the second corpus;

the salience of the third word is based on a normalized entropy of the third word in the second corpus; and

the salience of the fourth word is based on a normalized entropy of the fourth word in the second corpus.

11. The method according to claim 7, wherein:

the salience of the first word is based on whether a first predetermined list of sensitive words includes the first word;

the salience of the second word is based on whether a second predetermined list of sensitive words includes the second word;

the salience of the third word is based on whether a third predetermined list of sensitive words includes the third word; and

the salience of the fourth word is based on whether a fourth predetermined list of sensitive words includes the fourth word.

12. The method according to claim 1, further comprising:

determining a centroid distance between a centroid position of the first text phrase in the semantic space and a centroid position of the second text phrase in the semantic space, wherein the degree of semantic similarity between the first text phrase and the second text phrase is based on the centroid distance.

13. The method according to claim 12, wherein the centroid position of the first text phrase is determined based on a semantic position of one or more words of the first text phrase in the semantic space and the centroid position of the second text phrase is determined based on a semantic position of one or more words of the second text phrase in the semantic space.

14. The method according to claim 12, wherein the centroid position of the first text phrase is determined based on a salience of one or more words of the first text phrase and the centroid position of the second text phrase is determined based on a salience of one or more words of the second text phrase.

15. The method according to claim 12, wherein the degree of semantic similarity is based on a linear combination of the semantic edit distance and the centroid distance.

16. The method according to claim 1, wherein the degree of semantic similarity is based on whether the first text phrase includes a fifth word that the second text phrase does not include and whether a predetermined list of keywords includes the fifth word.

17. The method according to claim 1, wherein the semantic space is derived from a second corpus that includes a plurality of text phrases, and wherein each text phrase of the plurality of text phrases includes less than 150 characters.

18. A method for processing natural language comprising:

at an electronic device;

receiving a first text phrase;

determining one or more word-level differences of the first text phrase with respect to a second text phrase, wherein the one or more word-level differences include one or more of;

a first word-level difference comprising the second text phrase including a first word that does not correspond to any word of the first text phrase;

a second word-level difference comprising the first text phrase including a second word that does not correspond to any word of the second text phrase; and

a third word-level difference comprising the first text phrase including a third word that is different from a corresponding fourth word of the second text phrase; and

determining a total semantic cost associated with the one or more word-level differences based on one or more of;

a salience of the first word;

a salience of the second word;

a salience of the third word;

a salience of the fourth word; and

a semantic similarity between the third word and the fourth word in a semantic space;

wherein a degree of semantic similarity between the first text phrase and the second text phrase is based on the total semantic cost.

19. The method according to claim 18, further comprising:

determining, based on the degree of semantic similarity between the first text phrase and the second text phrase, a first intent associated with the first text phrase; and

performing, based on the first intent, a task associated with the first text phrase.

20. A non-transitory computer-readable storage medium comprising computer-executable instructions for causing a processor to:

receive a first text phrase;

determine whether editing the first text phrase to match a second text phrase requires one or more of;

insert a first word into the first text phrase, wherein the second text phrase includes the first word;

delete a second word from the first text phrase;

wherein the first text phrase includes the second word; and

substitute a third word of the first text phrase with a fourth word, wherein the second text phrase includes the fourth word;

in response to determining that editing the first text phrase to match the second text phrase requires one or more of inserting the first word into the first text phrase, deleting the second word from the first text phrase, and substituting the third word of the first text phrase with the fourth word, determining one or more of;

an insertion cost associated with inserting the first word into the first text phrase;

a deletion cost associated with deleting the second word from the first text phrase; and

a substitution cost associated with substituting the third word of the first text phrase with the fourth word; and

determine, based on the one or more of the insertion cost, the deletion cost, and the substitution cost, a semantic edit distance between the first text phrase and the second text phrase in a semantic space, wherein a degree of semantic similarity between the first text phrase and the second text phrase is based on the semantic edit distance.

21. An electronic device comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more program are stored in the memory and configured of be executed by the one or more processors, the one or more programs including instructions for;

receiving a first text phrase;

determining whether editing the first text phrase to match a second text phrase requires one or more of;

inserting a first word into the first text phrase, wherein the second text phrase includes the first word;

deleting a second word from the first text phrase;

wherein the first text phrase includes the second word; and

substituting a third word of the first text phrase with a fourth word, wherein the second text phrase includes the fourth word;

in response to determining that editing the first text phrase to match the second text phrase requires one or more of inserting the first word into the first text phrase, deleting the second word from the first text phrase, and substituting the third word of the first text phrase with the fourth word, determining one or more of;

an insertion cost associated with inserting the first word into the first text phrase;

a deletion cost associated with deleting the second word from the first text phrase; and

a substitution cost associated with substituting the third word of the first text phrase with the fourth word; and

determining, based on the one or more of the insertion cost, the deletion cost, and the substitution cost, a semantic edit distance between the first text phrase and the second text phrase in a semantic space, wherein a degree of semantic similarity between the first text phrase and the second text phrase is based on the semantic edit distance.