Automatic generation of domain models for virtual personal assistants

• US 9,886,950 B2
• Filed: 09/08/2014
• Issued: 02/06/2018
• Est. Priority Date: 09/08/2013
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Karov, Yael, Levy, Eran, Brosh-Lipstein, Sari
• Primary Examiner(s): Sirjani, Fariba
• Application Number:
  US14/479,949
• Publication Number:
  US 20150073798A1
• Time in Patent Office: 1,247 Days
• Field of Search: None
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

Technologies for automatic domain model generation include a computing device that accesses an n-gram index of a web corpus. The computing device generates a semantic graph of the web corpus for a relevant domain using the n-gram index. The semantic graph includes one or more related entities that are related to a seed entity. The computing device performs similarity discovery to identify and rank contextual synonyms within the domain. The computing device maintains a domain model including intents representing actions in the domain and slots representing parameters of actions or entities in the domain. The computing device performs intent discovery to discover intents and intent patterns by analyzing the web corpus using the semantic graph. The computing device performs slot discovery to discover slots, slot patterns, and slot values by analyzing the web corpus using the semantic graph. Other embodiments are described and claimed.

Claims

1. A computing device for domain model creation, the computing device comprising:

a web corpus module to access an n-gram index of a web corpus, wherein the web corpus includes a plurality of entities, wherein the n-gram index is indicative of a plurality of n-grams, wherein each n-gram comprises a predetermined number n of consecutive entities in the web corpus, and wherein the n-gram index is further indicative of a plurality of entities of each n-gram and a frequency of each n-gram;

a semantic graph module to generate a semantic graph of the web corpus using the n-gram index of the web corpus, wherein the semantic graph is rooted by a predefined seed entity and includes a first plurality of related entities, wherein each of the first plurality of related entities is grammatically related to the seed entity and each of the first plurality of related entities is included in a corresponding n-gram of the web corpus that also includes the seed entity, and wherein to generate the semantic graph comprises to;

retrieve a first plurality of n-grams from the web corpus using the n-gram index, wherein each of the first plurality of n-grams includes the seed entity;

tag each entity of the first plurality of n-grams for part-of-speech; and

identify a grammatical relationship between the seed entity and each of the first plurality of related entities in response to tagging of each entity, wherein each of the first plurality of related entities is included in the first plurality of n-grams;

a similarity discovery module to analyze the web corpus using the semantic graph to identify and rank contextual synonyms for entities within a domain, wherein the semantic graph is further expanded using the ranked contextual synonyms;

an intent discovery module to analyze the web corpus using the semantic graph to identify intents and intent patterns in the domain, wherein each intent is associated with a domain action, and each intent pattern matches query features and a corresponding intent; and

a slot discovery module to analyze the web corpus using the semantic graph to identify slots, slot patterns, and slot values in the domain, wherein each slot is associated with a parameter of an intent or an entity, each slot pattern matches query features and a corresponding slot, and each slot value is associated with an entity.

2. The computing device of claim 1, wherein to generate the semantic graph comprises to:

score each of the first plurality of related entities.

3. The computing device of claim 2, wherein to score each of the first plurality of related entities comprises to:

determine a first number of n-grams in the first plurality of n-grams;

determine a second number of n-grams in the first plurality of n-grams that each include a related entity of the first plurality of related entities; and

determine a web relation frequency as a function of a frequency of the second number of n-grams in the first number of n-grams.

4. The computing device of claim 2, wherein to score each of the first plurality of related entities comprises to calculate an indicative segment frequency in the web corpus and a normalized indicative segment frequency in the web corpus for the corresponding related entity.

5. The computing device of claim 4, wherein to calculate the indicative segment frequency and the normalized indicative segment frequency comprises to:

identify a plurality of segments including the corresponding related entity, wherein each segment comprises a shortest part of an n-gram of the first plurality of n-grams that includes the seed entity and the corresponding related entity; and

identify a most common segment of the plurality of segments as the indicative segment of the corresponding related entity.

6. The computing device of claim 5, wherein to calculate the normalized indicative segment frequency comprises to:

determine a probable frequency of occurrence in the web corpus of the entities of the indicative segment of the corresponding related entity; and

divide the indicative segment frequency of the corresponding related entity by the probable frequency of occurrence.

7. The computing device of claim 1, wherein to analyze the web corpus using the semantic graph to identify and rank contextual synonyms for entities within the domain comprises to:

select related entities of the first plurality of related entities having a highest indicative segment normalized frequency as anchor entities;

retrieve anchor n-grams from the web corpus, wherein each anchor n-gram includes the seed entity and an anchor entity;

replace the seed entity of each anchor n-gram with a placeholder;

retrieve candidate n-grams from the web corpus, wherein each candidate n-gram matches an anchor n-gram;

identify entities of the candidate n-grams matching the placeholder of the corresponding anchor n-gram as similarity candidates; and

score each of the similarity candidates based on similarity to the seed entity.

8. The computing device of claim 7, wherein to score each of the similarity candidates comprises to:

generate a contextual similarity score for the corresponding similarity candidate based on contextual features;

generate a linguistic similarity score for the corresponding similarity candidate based on linguistic features; and

determine a similarity score for the corresponding similarity candidate as a function of the corresponding contextual similarity score and the corresponding linguistic similarity score.

9. The computing device of claim 1, further comprising a domain model module to add the intents, intent patterns, slots, slot patterns, and slot values to a domain model, wherein the domain model includes known intents, intent patters, slots, and slot patterns associated with the domain and an ontology including known slot values associated with the domain.

10. The computing device of claim 9, wherein to analyze the web corpus using the semantic graph to identify the intents and the intent patterns in the domain comprises to:

score a first plurality of verbs of the first plurality of related entities of the semantic graph by a number of group unique n-grams and an indicative segment normalized frequency of the corresponding verb;

identify one or more unknown verbs of the first plurality of verbs, wherein each of the unknown verbs does not match an intent pattern of the domain model;

determine a similarity score for each pair of an unknown verb and a verb of the intent patterns of the domain model;

identify one or more similar verbs of the unknown verbs as a function of the corresponding similarity score for the unknown verb and the verb of the intent patterns of the domain model;

generate, for each similar verb of the one or more similar verbs, a new intent pattern for the intent of the corresponding intent pattern of the domain model;

cluster one or more remaining verbs of the unknown verbs to generate clusters of remaining verbs, wherein each of the remaining verbs is not a similar verb;

generate, for each cluster of remaining verbs, an intent; and

generate, for each remaining verb of the clusters of remaining verbs, an intent pattern associated with the intent for the corresponding cluster of remaining verbs.

11. The computing device of claim 9, wherein to analyze the web corpus using the semantic graph to identify the slot values in the domain comprises to:

score a first plurality of modifiers of the first plurality of related entities of the semantic graph by a number of group unique n-grams and an indicative segment normalized frequency;

identify one or more known modifiers of the first plurality of modifiers, wherein each of the known modifiers matches a slot pattern of the domain model;

identify one or more unknown slot values of the known modifiers, wherein each of the unknown slot values does not match a slot value of the ontology of the domain model; and

add the one or more unknown slot values to the ontology of the domain model.

12. The computing device of claim 11, wherein to analyze the web corpus using the semantic graph to identify the slots, the slot patterns, and the slot values in the domain comprises to:

identify one or more unknown modifiers of the first plurality of modifiers, wherein each of the unknown modifiers does not match a slot pattern of the domain model;

identify one or more first unknown modifiers of the unknown modifiers, wherein each of the first unknown modifiers includes a slot value matching a slot value of the ontology of the domain model;

generate, for each of the first unknown modifiers, a new slot pattern for the slot of the corresponding slot value;

identify one or more second unknown modifiers of the unknown modifiers, wherein each of the second unknown modifiers is not a first unknown modifier;

determine a similarity score for each pair of a second unknown modifier and a slot value of the ontology;

identify one or more similar modifiers of the second unknown modifiers as a function of the corresponding similarity score for the second unknown modifier and the slot value of the ontology;

generate, for each similar modifier, a new slot pattern for the slot of the corresponding slot value of the ontology;

add, for each similar modifier, a new slot value of the corresponding similar modifier to the ontology;

cluster one or more remaining modifiers of the second unknown modifiers to generate clusters of remaining modifiers, wherein each of the remaining modifiers is not a similar modifier;

generate, for each cluster of remaining modifiers, a slot;

generate, for each remaining modifier of the clusters of remaining modifiers, a slot pattern associated with the slot for the corresponding cluster of remaining modifiers; and

add, for each remaining modifier of the cluster of remaining modifiers, a slot value of the corresponding remaining modifier to the ontology.

13. A method for domain model creation, the method comprising:

generating, by a computing device, a semantic graph of a web corpus using an n-gram index of the web corpus, wherein the web corpus includes a plurality of entities, wherein the n-gram index is indicative of a plurality of n-grams, wherein each n-gram comprises a predetermined number n of consecutive entities in the web corpus, and wherein the n-gram index is further indicative of a plurality of entities of each n-gram and a frequency of each n-gram, and wherein the semantic graph is rooted by a predefined seed entity and includes a first plurality of related entities, wherein each of the first plurality of related entities is grammatically related to the seed entity and each of the first plurality of related entities is included in a corresponding n-gram of the web corpus that also includes the seed entity, wherein generating the semantic graph comprises;

retrieving a first plurality of n-grams from the web corpus using the n-gram index, wherein each of the first plurality of n-grams includes the seed entity;

tagging each entity of the first plurality of n-grams for part-of-speech; and

identifying a grammatical relationship between the seed entity and each of the first plurality of related entities in response to tagging each entity, wherein each of the first plurality of related entities is included in the first plurality of n-grams;

analyzing, by the computing device, the web corpus using the semantic graph to identify and rank contextual synonyms for entities within a domain, wherein the semantic graph is further expanded using the ranked contextual synonyms;

analyzing, by the computing device, the web corpus using the semantic graph to identify intents and intent patterns in the domain, wherein each intent is associated with a domain action, and each intent pattern matches query features and a corresponding intent; and

analyzing, by the computing device, the web corpus using the semantic graph to identify slots, slot patterns, and slot values in the domain, wherein each slot is associated with a parameter of an intent or an entity, each slot pattern matches query features and a corresponding slot, and each slot value is associated with an entity.

14. The method of claim 13, wherein generating the semantic graph comprises:

scoring each of the first plurality of related entities.

15. The method of claim 13, wherein analyzing the web corpus using the semantic graph to identify and rank contextual synonyms for entities within the domain comprises:

selecting related entities of the first plurality of related entities having a highest indicative segment normalized frequency as anchor entities;

retrieving anchor n-grams from the web corpus, wherein each anchor n-gram includes the seed entity and an anchor entity;

replacing the seed entity of each anchor n-gram with a placeholder;

retrieving candidate n-grams from the web corpus, wherein each candidate n-gram matches an anchor n-gram;

identifying entities of the candidate n-grams matching the placeholder of the corresponding anchor n-gram as similarity candidates; and

scoring each of the similarity candidates based on similarity to the seed entity.

16. The method of claim 15, wherein scoring each of the similarity candidates comprises:

generating a contextual similarity score for the corresponding similarity candidate based on contextual features;

generating a linguistic similarity score for the corresponding similarity candidate based on linguistic features; and

determining a similarity score for the corresponding similarity candidate as a function of the corresponding contextual similarity score and the corresponding linguistic similarity score.

17. The method of claim 13, further comprising adding, by the computing device, the intents, intent patterns, slots, slot patterns, and slot values to a domain model, wherein the domain model includes known intents, intent patters, slots, and slot patterns associated with the domain and an ontology including known slot values associated with the domain.

18. The method of claim 17, wherein analyzing the web corpus using the semantic graph to identify the intents and the intent patterns in the domain comprises:

scoring a first plurality of verbs of the first plurality of related entities of the semantic graph by a number of group unique n-grams and an indicative segment normalized frequency of the corresponding verb;

identifying one or more unknown verbs of the first plurality of verbs, wherein each of the unknown verbs does not match an intent pattern of the domain model;

determining a similarity score for each pair of an unknown verb and a verb of the intent patterns of the domain model;

identifying one or more similar verbs of the unknown verbs as a function of the corresponding similarity score for the unknown verb and the verb of the intent patterns of the domain model;

generating, for each similar verb of the one or more similar verbs, a new intent pattern for the intent of the corresponding intent pattern of the domain model;

clustering one or more remaining verbs of the unknown verbs to generate clusters of remaining verbs, wherein each of the remaining verbs is not a similar verb;

generating, for each cluster of remaining verbs, an intent; and

generating, for each remaining verb of the clusters of remaining verbs, an intent pattern associated with the intent for the corresponding cluster of remaining verbs.

19. One or more non-transitory, computer-readable storage media comprising a plurality of instructions that in response to being executed cause a computing device to:

generate a semantic graph of a web corpus using an n-gram index of the web corpus, wherein the web corpus includes a plurality of entities, wherein the n-gram index is indicative of a plurality of n-grams, wherein each n-gram comprises a predetermined number n of consecutive entities in the web corpus, and wherein the n-gram index is indicative of a plurality of entities of each n-gram and a frequency of each n-gram, and wherein the semantic graph is rooted by a predefined seed entity and includes a first plurality of related entities, wherein each of the first plurality of related entities is grammatically related to the seed entity and each of the first plurality of related entities is included in a corresponding n-gram of the web corpus that also includes the seed entity, wherein to generate the semantic graph comprises to;

retrieve a first plurality of n-grams from the web corpus using the n-gram index, wherein each of the first plurality of n-grams includes the seed entity;

tag each entity of the first plurality of n-grams for part-of-speech; and

identify a grammatical relationship between the seed entity and each of the first plurality of related entities in response to tagging each entity, wherein each of the first plurality of related entities is included in the first plurality of n-grams;

analyze the web corpus using the semantic graph to identify and rank contextual synonyms for entities within a domain, wherein the semantic graph is further expanded using the ranked contextual synonyms;

analyze the web corpus using the semantic graph to identify intents and intent patterns in the domain, wherein each intent is associated with a domain action, and each intent pattern matches query features and a corresponding intent; and

analyze the web corpus using the semantic graph to identify slots, slot patterns, and slot values in the domain, wherein each slot is associated with a parameter of an intent or an entity, each slot pattern matches query features and a corresponding slot, and each slot value is associated with an entity.

20. The one or more non-transitory, computer-readable storage media of claim 19, wherein to generate the semantic graph comprises to:

score each of the first plurality of related entities.

21. The one or more non-transitory, computer-readable storage media of claim 19, wherein to analyze the web corpus using the semantic graph to identify and rank contextual synonyms for entities within the domain comprises to:

select related entities of the first plurality of related entities having a highest indicative segment normalized frequency as anchor entities;

retrieve anchor n-grams from the web corpus, wherein each anchor n-gram includes the seed entity and an anchor entity;

replace the seed entity of each anchor n-gram with a placeholder;

retrieve candidate n-grams from the web corpus, wherein each candidate n-gram matches an anchor n-gram;

identify entities of the candidate n-grams matching the placeholder of the corresponding anchor n-gram as similarity candidates; and

score each of the similarity candidates based on similarity to the seed entity.

22. The one or more non-transitory, computer-readable storage media of claim 21, wherein to score each of the similarity candidates comprises to:

generate a contextual similarity score for the corresponding similarity candidate based on contextual features;

generate a linguistic similarity score for the corresponding similarity candidate based on linguistic features; and

determine a similarity score for the corresponding similarity candidate as a function of the corresponding contextual similarity score and the corresponding linguistic similarity score.

23. The one or more non-transitory, computer-readable storage media of claim 19, further comprising a plurality of instructions that in response to being executed cause the computing device to add the intents, intent patterns, slots, slot patterns, and slot values to a domain model, wherein the domain model includes known intents, intent patters, slots, and slot patterns associated with the domain and an ontology including known slot values associated with the domain.

24. The one or more non-transitory, computer-readable storage media of claim 23, wherein to analyze the web corpus using the semantic graph to identify the intents and the intent patterns in the domain comprises to:

score a first plurality of verbs of the first plurality of related entities of the semantic graph by a number of group unique n-grams and an indicative segment normalized frequency of the corresponding verb;

identify one or more unknown verbs of the first plurality of verbs, wherein each of the unknown verbs does not match an intent pattern of the domain model;

determine a similarity score for each pair of an unknown verb and a verb of the intent patterns of the domain model;

identify one or more similar verbs of the unknown verbs as a function of the corresponding similarity score for the unknown verb and the verb of the intent patterns of the domain model;

generate, for each similar verb of the one or more similar verbs, a new intent pattern for the intent of the corresponding intent pattern of the domain model;

cluster one or more remaining verbs of the unknown verbs to generate clusters of remaining verbs, wherein each of the remaining verbs is not a similar verb;

generate, for each cluster of remaining verbs, an intent; and

generate, for each remaining verb of the clusters of remaining verbs, an intent pattern associated with the intent for the corresponding cluster of remaining verbs.

25. The one or more non-transitory, computer-readable storage media of claim 23, wherein to analyze the web corpus using the semantic graph to identify the slots, the slot patterns, and the slot values in the domain comprises to:

score a first plurality of modifiers of the first plurality of related entities of the semantic graph by a number of group unique n-grams and an indicative segment normalized frequency;

identify one or more known modifiers of the first plurality of modifiers, wherein each of the known modifiers matches a slot pattern of the domain model;

identify one or more unknown slot values of the known modifiers, wherein each of the unknown slot values does not match a slot value of the ontology of the domain model;

add the one or more unknown slot values to the ontology of the domain model;

identify one or more unknown modifiers of the first plurality of modifiers, wherein each of the unknown modifiers does not match a slot pattern of the domain model;

identify one or more first unknown modifiers of the unknown modifiers, wherein each of the first unknown modifiers includes a slot value matching a slot value of the ontology of the domain model;

generate, for each of the first unknown modifiers, a new slot pattern for the slot of the corresponding slot value;

identify one or more second unknown modifiers of the unknown modifiers, wherein each of the second unknown modifiers is not a first unknown modifier;

determine a similarity score for each pair of a second unknown modifier and a slot value of the ontology;

identify one or more similar modifiers of the second unknown modifiers as a function of the corresponding similarity score for the second unknown modifier and the slot value of the ontology;

generate, for each similar modifier, a new slot pattern for the slot of the corresponding slot value of the ontology;

add, for each similar modifier, a new slot value of the corresponding similar modifier to the ontology;

cluster one or more remaining modifiers of the second unknown modifiers to generate clusters of remaining modifiers, wherein each of the remaining modifiers is not a similar modifier;

generate, for each cluster of remaining modifiers, a slot;

generate, for each remaining modifier of the clusters of remaining modifiers, a slot pattern associated with the slot for the corresponding cluster of remaining modifiers; and

add, for each remaining modifier of the cluster of remaining modifiers, a slot value of the corresponding remaining modifier to the ontology.