Hybrid classifier for assigning natural language processing (NLP) inputs to domains in real-time

• US 10,120,861 B2
• Filed: 08/17/2016
• Issued: 11/06/2018
• Est. Priority Date: 08/17/2016
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Scally, Jonathan R., Cassimatis, Nicholas L., Caneba, Richard, Govindarajulu, Naveen Sundar
• Primary Examiner(s): Spooner, Lamont
• Application Number:
  US15/239,219
• Publication Number:
  US 20180052823A1
• Time in Patent Office: 811 Days
• Field of Search: 704 1, 704 9, 704 10
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Systems and methods for domain classification in natural language processing based on domains are disclosed. The method includes generating a trigram corpus for the purpose of classification based on a trigram analysis of a domain model containing a hierarchical ontology and semantic construction that maps patterns of semantic tokens to syntactic patterns. An input string is parsed within each domain, tokenized in each domain. The resulting trigrams for the input text in each domain are looked up in the corresponding trigram corpus to determine the relevancy of each domain to the input text. The input string is thus classified based on the relevancy determination. The systems and methods avoids having to rely on existing annotated domain corpora for classification and allows for fast regeneration of the classifier when domain models are under frequent update and development.

Claims

1. A method for classifying an input query within multiple domains for natural language processing, the method comprising generating trigram corpora, each trigram corpus for a domain, comprising:

defining a query model for the domain comprising at least an ontology having a set of semantic tokens organized in hierarchical levels, and a set of domain-specific semantic constructions each including one or more of the semantic tokens linked by one of a set of predefined grammatical relations;

obtaining an expanded set of semantic constructions as a semantic corpus for the domain by replacing at least one of the semantic tokens of at least one of the semantic constructions of the query model with corresponding semantic tokens at a lower hierarchical level in the ontology of the query model;

performing a trigram analysis on the semantic corpus to obtain the trigram corpus for the domain comprising entries each corresponding to a trigram of three-token sequence appearing in the semantic corpus, each entry comprising;

a three-token sequence having a first, second and third semantic token; and

a corresponding trigram probability representing a relative probability that the third semantic token appearing in the semantic corpus given the first and the second semantic tokens;

obtaining an input query text from a remote device via a network connection;

determining normalized relevance scores for the input query text corresponding to the multiple domains based on the input query text, query models of the multiple domains and the trigram corpora of the multiple domains;

ordering the normalized relevance scores for the input query text with respect to the multiple domains;

classifying the input query text according to the ordering; and

transmitting, to the remote device, a communication comprising the input query text based upon the classifying.

2. The method of claim 1, wherein obtaining the expanded set of semantic constructions as the semantic corpus for the domain comprises:

determining effective leaf levels of the ontology;

for a semantic construction of the set of domain-specific semantic constructions, identifying sets of effective leaf level semantic tokens, each set comprising effective leaf level tokens below a corresponding semantic token in the semantic construction in the hierarchical levels; and

expanding the set of domain-specific semantic constructions into the semantic corpus by replacing each semantic token in the set of domain-specific semantic constructions with any of the corresponding identified effective leaf level semantic tokens.

3. The method of claim 2, wherein the ontology further comprises a set of customized tokens and a symbolic token representing any unknown linguistic element.

4. The method of claim 3, wherein the set of customized tokens comprising tokens representing one or more of time, date, and location.

5. The method of claim 1, wherein each expanded semantic construction in the semantic corpus for the domain further include two preceding symbolic start tokens and an appending symbolic end token.

6. The method of claim 1, wherein the trigram probability for each trigram entry in the trigram corpus is obtained with further consideration of a backoff factor accounting for other possible trigrams of the domain unobserved in the semantic corpus by weighting them on their bigram and unigram frequency.

7. The method of claim 1, wherein determining the normalized relevance scores for the input query text corresponding to the multiple domains comprises, for a domain of the multiple domains:

sequencing the input query text into at least one sequence of substrings;

tokenizing the at least one sequence of substrings into a set of token sequences comprising at least one token sequence with respect to the domain based on the ontology of the query model for the domain;

obtaining a set of normalized relevance measures with respect to the domain, each normalized relevance measures corresponding to one token sequence of the set of token sequences of the domain based on trigrams appearing in the one token sequence and the trigram corpus of the domain; and

determining, as one of the normalized relevance scores for the input query text corresponding to the multiple domains, a normalized relevance score with respect to the domain for the input query text based on the set of normalized relevance measures with respect to the domain.

8. The method of claim 7, wherein tokenizing the at least one sequence of substrings into a set of token sequences comprises:

removing known substrings having no semantic content in the domain to obtain a redacted at least one sequence of substrings;

obtaining the set of token sequences from the at least one sequence of substrings by replacing each substring with a matching semantic token from the ontology; and

replacing each substring having no matching semantic tokens from the ontology with a predefined unknown token.

9. The method of claim 8, wherein each token sequence of the set of token sequences is further preceded with two symbolic start tokens and appended with one symbolic end token.

10. The method of claim 8, wherein obtaining one of the set of normalized relevance measures with respect to the domain corresponding to one token sequence of the set of token sequences comprises:

obtaining a set of trigrams contained in the one token sequence;

identifying entries in the trigram corpus of the domain matching each trigram in the set of trigrams contained in the one token sequence;

obtaining a set of trigram probabilities in the trigram corpus corresponding to the identified trigram entries;

determining a relevance measure of the one token sequence with respect to the domain based on the set of trigram probabilities; and

normalizing the relevance measure of the one token sequence to obtain the one of the set of normalized relevance measures with respect to the domain for the one token sequence of the set of token sequences.

11. The method of claim 10, wherein determining the relevance measure of the one token sequence with respect to the domain comprises multiplying together each of the trigram probability in the set of trigram probabilities.

12. The method of claim 10, wherein normalizing the relevance measure of the one token sequence to obtain the one of the set of normalized relevance measures comprises:

obtaining a number of tokens in the one token sequence that are not unknown token; and

obtaining the one of the set of normalized relevance measures based on the number.

13. The method of claim 7, wherein determining the normalized relevance measure with respect to the domain for the input query text comprises determining as the normalized relevance measure for the input query text a maximum relevance measure among the set of normalized relevance measures with respect to the domain each corresponding to one token sequence of the set of token sequences.

14. The method of claim 7, wherein determining the normalized relevance measure with respect to the domain for the input query text comprises determining as the normalized relevance measure for the input query text an average relevance measure among the set of normalized relevance measures with respect to the domain each corresponding to one token sequence of the set of token sequences.

15. A domain classification system for domain based natural language processing, comprising:

memory storing;

query models each for a domain of a set of domains and comprising at least an ontology having a set of semantic tokens organized in hierarchical levels, and a set of domain-specific semantic constructions each including one or more of the semantic tokens linked by one of a set of predefined grammatical relations;

trigram corpora, each corpus for a domain of the set of domains and each having entries comprising;

trigrams obtained based on the query model of the domain, each trigram having a first, second and third semantic token; and

corresponding trigram probabilities each representing a relative probability that the third semantic token appearing in the trigrams given the first and the second sematic tokens; and

computer executable instructions; and

a processor in communication with the memory, and when executing the instructions, configured to implement software components comprising;

a receiving component configured to receive an input text from a remote device via a network connection;

a set of domain relevance analyzer components corresponding to the set of domains configured to determine relevance scores for the input text with respect to the set of domains based on tokenized sequences of the input text corresponding to the set of domains, the query models, and the trigram corpora;

a classifier component configured to classify the input text among the set of domains based on the relevance scores with respect to the set of domains for the input text; and

a component configured to transmit, to the remote device, a communication comprising the input text based upon the classifying.

16. The domain classification system of claim 15, wherein the processor, when executing the instructions, is further configured to implement software components comprising:

a semantic construction expander component configured to obtain one expanded set of semantic constructions as semantic corpus for each domain by replacing at least one of the semantic tokens of at least one of the semantic constructions of the query model of the domain with corresponding semantic tokens at a lower hierarchical level in the ontology of the query model of the domain; and

a trigram generator component configured to generate the trigram corpora by;

generating the trigrams for each domain based on the expanded set of semantic constructions for the domain; and

obtaining the trigram probabilities corresponding to the trigrams for each domain.

17. The domain classification system of claim 15, wherein the set of domain relevance analyzer components further comprises:

a set of input sequencer components for the input text corresponding to the set of domains and each configured for one domain to sequence the input text into sequences of substrings; and

a set of tokenizer components corresponding to the set of domains for determining the tokenized sequences for the input text, each configured to tokenize the sequences of substrings for one domain based on the query model of the one domain.

18. A computer readable medium storing computer executable instructions that when executed by a processor cause the processor to perform a method for classifying an input query within multiple domains for natural language processing, the method comprising generating trigram corpora, each trigram corpus for a domain, comprising:

defining a query model for the domain comprising at least an ontology having a set of semantic tokens organized in hierarchical levels, and a set of domain-specific semantic constructions each including one or more of the semantic tokens linked by one of a set of predefined grammatical relations;

obtaining an expanded set of semantic constructions as a semantic corpus for the domain by replacing at least one of the semantic tokens of at least one of the semantic constructions of the query model with corresponding semantic tokens at a lower hierarchical level in the ontology of the query model;

performing a trigram analysis on the semantic corpus to obtain the trigram corpus for the domain comprising entries each corresponding to a trigram of three-token sequence appearing in the semantic corpus, each entry comprising;

a three-token sequence having a first, second and third semantic token; and

a corresponding trigram probability representing a relative probability associated with the third semantic token appearing in the semantic corpus given the first and the second semantic tokens;

obtaining an input query text from a remote device via a network connection;

determining normalized relevance scores for the input query text corresponding to the multiple domains based on the input query text, query models of the multiple domains and the trigram corpora of the multiple domains;

ordering the normalized relevance scores for the input query text with respect to the multiple domains;

classifying the input query text according to the ordering; and

transmitting, to the remote device, a communication comprising the input query text based upon the classifying.

19. The computer readable medium of claim 18, wherein each expanded semantic construction in the semantic corpus for the domain further include two preceding symbolic start tokens and an appending symbolic end token.

20. The computer readable medium of claim 18, wherein the ontology further comprises a set of customized tokens and a symbolic token representing any unknown linguistic element.