Enhanced artificial intelligence language

• US 8,321,371 B2
• Filed: 12/04/2007
• Issued: 11/27/2012
• Est. Priority Date: 03/04/2003
• Status: Active Grant

• Current Assignee: Kurzweil Technologies, Inc.
• Original Assignee: Kurzweil Technologies, Inc.
• Inventors: Bridges, Matthew, Kurzweil, Raymond C.
• Primary Examiner(s): FERNANDEZ RIVAS, OMAR F
• Application Number:
  US11/949,883
• Publication Number:
  US 20080218473A1
• Time in Patent Office: 1,820 Days
• Field of Search: None
• US Class Current: 706/62
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

A method of determining an appropriate response to an input includes linking a plurality of attributes to a plurality of response templates using a plurality of Boolean expressions. Each attribute is associated with a set of patterns. Each pattern within the set of patterns is equivalent. The method also includes determining an appropriate response template from the plurality of response templates based on the input.

Claims

1. A computer implemented method of determining an appropriate response to an input, comprising:

linking by a computer system a plurality of attributes to a plurality of response templates using a plurality of Boolean expressions, each attribute associated with a set of patterns, with each pattern within the set of patterns being equivalent;

receiving by the computer the input; and

determining by the computer system an appropriate response template for the received input, the appropriate response template selected from the plurality of response templates based on the input, by;

determining by the computer system matches of the input to patterns;

ranking by the computer system the patterns; and

selecting by the computer the corresponding response template based on the ranked patterns.

2. The method of claim 1, wherein determining comprises:

performing an initialization by the computer.

3. The method of claim 2 wherein linking the plurality of attributes to the plurality of response templates comprises:

forming by the computer system a megacategory, with the megacategory linking a combination of attributes to one of the plurality of response templates using one of the plurality of Boolean expressions.

4. The method claim 2 wherein linking the plurality of attributes to the plurality of response templates comprises:

forming by the computer system a megacategory, with the megacategory linking one attribute to one of the plurality of response templates.

5. The method of claim 3 wherein the combination of attributes using one of the plurality of Boolean expressions comprises:

a name for each attribute in the combination; and

an operator Boolean expression.

6. The method of claim 5 wherein the operator is an AND operator.

7. The method of claim 3 wherein the megacategory comprises:

a hierarchy of levels in matching the megacategory to the input.

8. The method of claim 3, further comprising:

grouping a plurality of megacategories into a topic having a topic name; and

adding a topic variable to one of the plurality of response templates.

9. The method of claim 8, further comprising:

comparing by the computer a megacategory to the input when the topic name matches the topic variable.

10. The method of claim 1 wherein being equivalent comprises being semantically equivalent.

11. The method of claim 1, further comprising:

storing in computer storage the plurality of attributes and the plurality of response templates.

12. The method of claim 3, wherein performing an initialization comprises:

converting an AIML category having one pattern and one response template to an equivalent combination of one attribute and one megacategory, the one megacategory comprising the one response template; and

storing the equivalent combination.

13. The method of claim 3 wherein performing an initialization comprises:

expanding the patterns;

arranging the patterns in alphabetical order;

assigning a specificity rank to each pattern; and

adding each pattern to an attribute trie.

14. The method of claim 13 wherein performing an initialization comprises:

expanding “

that”

patterns;

arranging “

that”

patterns alphabetically;

assigning a specificity rank to each “

that”

pattern; and

adding each “

that”

pattern to a “

that”

trie.

15. The method of claim 14 wherein performing an initialization comprises:

expanding megacategories into conjunctions;

ordering the conjunctions alphabetically; and

adding each megacategory to a megacategory trie.

16. The method of claim 15, wherein determining an appropriate response template comprises:

dividing the input into word segments;

traversing the attribute trie with the input to determine matching attributes;

traversing the “

that”

trie to determine matching “

that”

patterns from a previous output;

traversing the megacategory trie with matching attributes patterns and matching “

that”

patterns to determine matching megacategories.

17. The method of claim 16 wherein traversing the attribute trie comprises:

assigning a variable to each pattern; and

setting the variable to true for each pattern that matches a portion of the input.

18. The method of claim 16, further comprising:

if one megacategory matches, selecting a response template corresponding to the one megacategory.

19. The method of claim 16, further comprising:

if more than one megacategory matches, selecting a response template corresponding to a megacategory having the highest summed specificity rank from the set of patterns.

20. The method of claim 19, further comprising:

if more than one megacategory has the highest summed specificity rank, selecting a megacategory having a pattern having the single highest specificity rank.

21. The method of claim 16, further comprising:

if no megacategories match, adding matched attributes from a last user input to the current matched attributes; and

determining a matching megacategory.

22. The method of claim 1, further comprising:

executing the appropriate response template.

23. The method of claim 3, wherein the megacategory comprises a “

that”

tag containing a pattern that is syntactically equivalent to patterns within attributes.

24. An article comprising a machine readable storage device that stores executable instructions for determining an appropriate response to an input, the instructions causing a processor to:

link a plurality of attributes to a plurality of response templates using a plurality of Boolean expressions, each attribute associated with a set of patterns, each pattern within the set of patterns being equivalent;

receive the input; and

determine an appropriate response template for the received input, the appropriate response template selected from the plurality of response templates based on the input, by instructions to;

determine matches of the input to patterns;

rank the patterns; and

select the corresponding response template based on the ranked patterns .

25. The article of claim 24, wherein instructions causing a machine to determine comprises:

performing an initialization.

26. The article of claim 25 wherein instructions causing a machine to link the plurality of attributes to the plurality of response templates comprises instructions to:

form a megacategory, with the megacategory linking a combination of attributes to one of the plurality of response templates using one of the plurality of Boolean expressions.

27. The article of claim 24 wherein being equivalent comprises being semantically equivalent.

28. The article of claim 24, further comprising instructions causing a machine to:

store the plurality of attributes and the plurality of response templates.

29. The article of claim 26, wherein instructions to perform an initialization comprise instructions to:

convert an AIML category having one pattern and one response template to an equivalent combination of one attribute and one megacategory, the one megacategory comprising the one response template; and

store the equivalent combination.

30. The article of claim 26 wherein instructions to perform an initialization comprises instructions to:

expand the patterns;

arrange the patterns in alphabetical order;

assign a specificity rank to each pattern; and

add each pattern to an attribute trie.

31. The article of claim 30 wherein instructions to perform an initialization comprises instructions to:

expand “

that”

patterns;

arrange “

that”

patterns alphabetically;

assign a specificity rank to each “

that”

pattern; and

add each “

that”

pattern to a “

that”

trie.

32. The article of claim 31 wherein instructions to perform an initialization comprises instructions to:

expand megacategories into conjunctions;

order the conjunctions alphabetically; and

add each megacategory to a megacategory trie.

33. The article of claim 32, wherein instructions causing a machine to determine an appropriate response template comprises instructions to:

divide the input into word segments;

traverse the attribute trie with the input to determine matching attributes;

traverse the “

that”

trie to determine matching “

that”

patterns from a previous output; and

traverse the megacategory trie with matching attributes patterns and matching “

that”

patterns to determine matching megacategories.

34. The article of claim 33 wherein instructions to traverse the attribute trie comprises instructions to:

assign a variable to each pattern; and

set the variable to true for each pattern that matches a portion of the input.

35. The article of claim 33, further comprising instructions causing a machine to:

determine that one megacategory matches, and when there is a determined match,

select a response template corresponding to the one megacategory.

36. The article of claim 33, further comprising instructions causing a machine to:

determine that more than one megacategory matches, and when there are determined matches,

select a response template corresponding to a megacategory having the highest summed specificity rank from the set of patterns.

37. The article of claim 36, further comprising instructions causing a machine to:

determine that more than one megacategory has the highest summed specificity rank,

select a megacategory having a pattern having the single highest specificity rank.

38. The article of claim 33, further comprising instructions causing a machine to:

determine that no megacategories match,

add matched attributes from a last user input to the current matched attributes; and

determine a matching megacategory.

39. The article of claim 24, further comprising instructions causing a machine to:

execute the appropriate response template.

40. An apparatus comprising:

a memory that stores executable instructions for determining an appropriate response to an input; and

a processor that executes the instructions to;

link a plurality of attributes to a plurality of response templates using a plurality of Boolean expressions, each attribute associated with a set of patterns, with each pattern within the set of patterns being equivalent;

receive the input; and

determine an appropriate response template for the received input, the appropriate response template selected from the plurality of response templates based on the input, by instructions to;

determine matches of the input to patterns;

rank the patterns; and

select the corresponding response template based on the ranked patterns.

41. The apparatus of claim 40, wherein instructions to determine comprise instructions to:

perform an initialization.

42. The apparatus of claim 41 wherein instructions to link the plurality of attributes to the plurality of response templates comprises instructions to:

form a megacategory, with the megacategory linking a combination of attributes to one of the plurality of response templates using one of the plurality of Boolean expressions.

43. The apparatus of claim 40 wherein being equivalent comprises being semantically equivalent.

44. The apparatus of claim 40, further comprising instructions to:

store the plurality of attributes and the plurality of response templates.

45. The apparatus of claim 42, wherein instructions to perform an initialization comprise instructions to:

convert an AIML category having one pattern and one response template to an equivalent combination of one attribute and one megacategory, the one megacategory comprising the one response template; and

store the equivalent combination.

46. The apparatus of claim 42 wherein instructions to perform an initialization comprise instructions to:

expand the patterns;

arrange the patterns in alphabetical order;

assign a specificity rank to each pattern; and

add each pattern to an attribute trie.

47. The apparatus of claim 46 wherein instructions to perform an initialization comprise instructions to:

expand “

that”

patterns;

arrange “

that”

patterns alphabetically;

assign a specificity rank to each “

that”

pattern; and

add each “

that”

pattern to a “

that”

trie.

48. The apparatus of claim 47 wherein instructions to perform an initialization comprise instructions to:

expand megacategories into conjunctions;

order the conjunctions alphabetically; and

add each megacategory to a megacategory trie.

49. The apparatus of claim 48, wherein instructions to determine an appropriate response template comprise instructions to:

divide the input into word segments;

traverse the attribute trie with the input to determine matching attributes;

traverse the “

that”

trie to determine matching “

that”

patterns from a previous output; and

traverse the megacategory trie with matching attributes patterns and matching “

that”

patterns to determine matching megacategories.

50. The apparatus of claim 49 wherein instructions to traverse the attribute trie comprise instructions to:

assign a variable to each pattern; and

set the variable to true for each pattern that matches a portion of the input.

51. The apparatus of claim 49, further comprising instructions to:

determine that one megacategory matches, and when there is a determined match, select a response template corresponding to the one megacategory.

52. The apparatus of claim 49, further comprising instructions to:

determine that more than one megacategory matches, and when there are determined matches,

select a response template corresponding to a megacategory having the highest summed specificity rank from the set of patterns.

53. The apparatus of claim 52, further comprising instructions to:

determine that more than one megacategory has the highest summed specificity rank, select a megacategory having a pattern having the single highest specificity rank.

54. The apparatus of claim 49, further comprising instructions to:

determine that no megacategories match, add matched attributes from a last user input to the current matched attributes; and

determine a matching megacategory.

55. The apparatus of claim 40, further comprising instructions to:

execute the appropriate response template.