Probabilistic Ranking for Natural Language Understanding

Patent metadata

Field	Value
Publication number	US-2017193387-A1
Application number	US-201615291325-A
Country	US
Kind code	A1
Filing date	Oct 12, 2016
Priority date	Dec 31, 2015
Publication date	Jul 6, 2017
Grant date	—

Abstract

Aspects of the disclosure are directed to natural language processing or natural language understanding and may include a determination of a probabilistic or probability-based ranking of potential results. For example, natural language input may be received such as speech or text. Natural language processing may be performed to determine one or more potential results for the input. A pairwise classifier may be used to determine a score for element pairs in the potential results. Based on the scores, probabilities for the element pairs may be determined. Based on the probabilities for the element pairs, further probabilities may be determined such as by estimating the probability that a current result is the top rank or best choice. Based on the estimated probabilities that the current result is the top rank or best choice, a ranking may be determined, which may form the basis for natural language understanding output.

First claim

1 . A method comprising:
receiving natural language input; determining a list of potential results based on the natural language input; determining, using a pairwise classifier, scores for element pairs determined from the list of potential results, each score being indicative of a relationship between two elements of the corresponding element pair; determining, based on the scores for the element pairs, one or more pairwise probabilities for the elements pairs; determining, based on the one or more pairwise probabilities for the element pairs, an approximation of a probability that each result in the list of potential results is to be the top ranked result among the list of potential results, resulting in top-rank probability approximations; determining, based on the top-rank probability approximations, a ranking of the potential results; and after determining the ranking of the potential results, transmitting natural language understanding output responsive to the natural language input.

2 . The method of claim 1 , further comprising:
determining a potential ranking for the potential results; analyzing the potential ranking to determine whether a risk of a cycle occurring is acceptable or unacceptable; and based on determining whether the risk of the cycle occurring is acceptable or unacceptable, selecting between processing the ranking of the potential results as the natural language understanding output or performing a different algorithm for determining the natural language understanding output.

3 . The method of claim 2 , further comprising:
performing the different algorithm for determining the natural language understanding output, wherein performing the different algorithm includes determining a ranking using a classifier different from the pairwise classifier and/or generating a request for additional input from a user.

4 . The method of claim 2 , further comprising:
processing the ranking of the potential results as the natural language understanding output.

5 . The method of claim 2 , wherein determining whether at least one of the potential rankings is invalid results in an identification of invalid rankings, and wherein the method further comprises:
determining an estimation of a probability that each of the invalid rankings will occur, resulting in invalid ranking probability estimates; and summing the invalid ranking probability estimates with each other, resulting in a sum of the invalid ranking probability estimates; wherein selecting between processing the ranking of the potential results as the natural language understanding output or performing a different algorithm for determining the natural language understanding output is conditioned upon a comparison of the risk of the cycle occurring and a threshold.

6 . The method of claim 5 , further comprising:
determining an additional ranking based on a classifier different from the pairwise classifier; applying weights to the ranking of the potential results and the additional ranking, wherein at least one of the weights is based on the risk of the cycle occurring; and based on the weights, the ranking of potential results and the additional ranking, determining a final ranking for use as the natural language output.

7 . The method of claim 1 , wherein determining, based on the pairwise probability estimates for the element pairs, the estimation of the probability that each result in the list of potential results is to be the top ranked result among the list of potential results comprises:
determining, for each probability that a result in the list of potential results is to be the top ranked result among the list of potential results, initial values for an upper bound and a lower bound, resulting in an upper bound and a lower bound for a first probability that a first result in the list of potential results is to be the top ranked result among the list of potential results and one or more other upper bounds and lower bounds for one or more other probabilities that one or more other results in the list of potential results is to be the top ranked result among the list of potential results; and iteratively restricting a range between the upper bound and the lower bound for the first probability by applying a constraint inferred from ranges of the other upper bounds and the lower bounds.

8 . An apparatus comprising:
one or more processors; and memory storing executable instructions that, when executed by the one or more processors, cause the apparatus to:
receive natural language input;
determine a list of potential results based on the natural language input;
determine, using a pairwise classifier, scores for element pairs determined from the list of potential results, each score being indicative of a relationship between two elements of the corresponding element pair;
determine, based on the scores for the element pairs, one or more pairwise probabilities for the elements pairs;
determine, based on the one or more pairwise probabilities for the element pairs, an approximation of a probability that each result in the list of potential results is to be the top ranked result among the list of potential results, resulting in top-rank probability approximations;
determine, based on the top-rank probability approximations, a ranking of the potential results; and
after determining the ranking of the potential results, transmit natural language understanding output responsive to the natural language input.

9 . The apparatus of claim 8 , wherein the executable instructions, when executed by the one or more processors, cause the apparatus to:
determine a potential ranking for the potential results; analyze the potential ranking to determine whether a risk of a cycle occurring is acceptable or unacceptable; and based on determining whether the risk of the cycle occurring is acceptable or unacceptable, select between processing the ranking of the potential results as the natural language understanding output or performing a different algorithm for determining the natural language understanding output.

10 . The apparatus of claim 9 , wherein the executable instructions, when executed by the one or more processors, cause the apparatus to:
perform the different algorithm for determining the natural language understanding output, wherein performing the different algorithm includes determining a ranking using a classifier different from the pairwise classifier and/or generating a request for additional input from a user.

11 . The apparatus of claim 9 , wherein the executable instructions, when executed by the one or more processors, cause the apparatus to:
process the ranking of the potential results as the natural language understanding output.

12 . The apparatus of claim 9 , wherein causing the apparatus to determine whether at least one of the potential rankings is invalid results in an identification of invalid rankings, and wherein the executable instructions, when executed by the one or more processors, cause the apparatus to:
determine an estimation of a probability that each of the invalid rankings will occur, resulting in invalid ranking probability estimates; and sum the invalid ranking probability estimates with each other, resulting in a sum of the invalid ranking probability estimates; wherein causing the apparatus to select between processing the ranking of the potential results as the natural language understanding output or performing a different algorithm for determining the natural language understanding output is conditioned upon a comparison of the risk of the cycle occurring and a threshold.

13 . The apparatus of claim 12 ,

Assignees

• Nuance Communications Inc

Inventors

• Lavallee Jean-Francois

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F40/40

  Processing or translation of natural language (natural language analysis G06F40/20; semantic analysis G06F40/30) · CPC title

• G06F16/3329 Primary

  Natural language query formulation · CPC title

• G06F17/28

  Physics · mapped topic

• G06N7/005 Primary

  Physics · mapped topic