Abstract:
Selecting a grammar for use in a machine question-answering system, such as a Natural Language Understanding System, can be difficult for non-experts in such grammars. A tool, according to an example embodiment, can compare annotations of sample sentences, performed correctly by a human, the annotations having intents and mentions, against annotations performed by multiple grammars. Each grammar can be scored, and the system can select the best scored grammar for the user. In one embodiment, a method of selecting a grammar includes comparing manually-generated annotations against machine-generated annotations as a function of a given grammar among multiple grammars. The method can further include applying scores to the machine-generated annotations that are a function of weightings of the intents and mentions. The method can additionally include recommending whether to employ the given grammar based on the scores.

Description:
RELATED APPLICATION 
       [0001]    This Application is related to “Initializing A Workspace For Building A Natural Language Understanding System” by Jeffrey N. Marcus, attorney docket number 4765.1033-000, filed on the same day as this Application to a common assignee. The foregoing application is hereby incorporated by reference in its entirety. 
       BACKGROUND 
       [0002]    A system can provide non-expert designers an environment for building models (e.g. rules, classifiers, etc.) to perform Natural Language Understanding (NLU) processing. The system can build a project that includes a “concept ontology,” which describes the concepts that the NLU system needs to understand, such as “ticketing” or “directions.” These concepts are considered “intents,” which are the user&#39;s goal for the machine interaction. Typically, such a project is built by the user examining statistics of grammars and based on manual analysis, deciding which intents and mentions best fit the project. 
       SUMMARY 
       [0003]    Definitions: 
         [0004]    Intent—An end user&#39;s basic goal for a machine interaction. The intent label is chosen from a finite set, by a human annotator, that best matches this goal. For example, in a technical support application, an input of “my printer is not working, I need help” might be labeled with an intent of “Printer Problem.” 
         [0005]    Out-of-domain intent—A caller&#39;s intent that does not match any of the available intents in the finite set. 
         [0006]    Mention—a piece of information the natural language application uses to complete the action indicated by the intent. For example, in the sentence “I want to travel to Phoenix May 28”, the intent can be “Flight” and mentions can be “Date=May 28” and “Destination=Phoenix.” 
         [0007]    Sentence Annotation—a set of intent and mention labels determined by a human annotator for a sentence. 
         [0008]    Test set—A set of sentences along with their annotations used to evaluate competing models. 
         [0009]    Semantic confidence threshold—a designer-set parameter indicating a minimum score for the application to accept a given sentence. In the application, each sentence spoken by the end user is assigned a semantic confidence score. Confidences above the threshold are accepted (e.g., processed by the application by offering to reserve a flight for the city and date requested) or rejected, with the user typically being informed that the system did not understand him and optionally being asked to repeat the sentence. 
         [0010]    In one embodiment, the system of the present invention can additionally include intents and mentions in its concept ontology. The sentence annotations having both intents and mentions allows the system to provide more accurate grammar recommendations than using intents or mentions alone. 
         [0011]    Sentences entered into the system by speech or by typing can be annotated within the tool, where a process of annotating decomposes a sentence into its component concepts. For example, annotations can indicate that in “January 24 at 2PM.” “January 24” is a date and “2PM” is a time. The system automatically generates a model based on the data. 
         [0012]    The system typically repeats this process by correcting annotations, adding more data, and generating new models. Also, the system can set configuration parameters, such as confidence thresholds. Thus, the system typically creates several versions. The NLU designer wants to use the “best” model in his application. However, choosing the “best” model is a complex problem even for an expert and difficult for a non-expert. In one embodiment, the present invention includes a system and corresponding method for ranking models against each other to provide a designer a reasonable choice of models and giving the designer an indication of the overall effectiveness of the resultant model. 
         [0013]    The designer can adjust the system&#39;s parameters in some embodiments to optimize usability, such as success rate and/or time spent completing a task. 
         [0014]    In one embodiment, a method of selecting a grammar from among multiple grammars includes comparing manually-generated annotations, including intents and mentions, corresponding to a set of sentences against machine-generated annotations. The comparing can be a function of a given grammar among multiple grammars. The machine-generated annotations also include intents and mentions corresponding to the set of sentences. The method can further include applying scores to the machine-generated annotations. The scores can be a function of weightings of the intents and mentions. The method can additionally include recommending whether to employ the given grammar based on the scores. 
         [0015]    Applying the scores to the machine-generated annotations can include applying a respective intra-sentence score to each of the intents and mentions of the machine-generated annotations based on the comparison of the manually-generated annotations and the machine-generated annotations. Applying the scores to the machine-generated annotations can further include applying an inter-sentence score to the grammar based on the respective intra-sentence scores of each of the intents and mentions of the machine-generated annotations of the grammar. An intra-sentence score can be a score applied to an annotation within the sentence, such as an intent or mention. An intra-sentence score can be a score applied to a sentence as a whole, for example, based on intra-sentence scores applied to the annotations within the sentence. 
         [0016]    The method can further include parsing, by the machine, each of the set of sentences to generate the machine-generated annotations. 
         [0017]    The method can additionally include adjusting weightings of intents and mentions by performing a statistical regression model of the weightings to optimize a measurement of the end user&#39;s experience. An example of a measurement of the end user&#39;s experience is the probability of successfully completing a task penalized by how long task completion takes. 
         [0018]    Applying the scores to the machine-generated annotations can further include applying multiple scores, where each of the scores is based on a grammar employing a respective confidence threshold. Applying the scores to the machine-generated annotations can further include averaging the plurality of scores over a range of respective confidence thresholds. 
         [0019]    In one embodiment, a system for selecting a grammar from among multiple grammars can include a comparison module configured to compare manually-generated annotations including a set of sentences against machine-generated annotations. The comparing can be a function of a given grammar among multiple grammars. The machine-generated annotations can include intents and mentions corresponding to the set of sentences. The system further includes a scoring module configured to apply scores to the machine-generated annotation. The scores can be a function of weightings of the intents and mentions. The system further includes a recommendation module configured to recommend whether to employ the grammar based on the scores. 
         [0020]    In one embodiment, a non-transitory computer-readable medium is configured to store instructions for selecting a grammar from among multiple grammars. The instructions, when loaded and executed by a processor, can cause the processor to compare manually-generated annotations including intents and mentions corresponding to a set of sentences to machine-generated annotations. The scores can be a function of a given grammar among multiple grammars. The machine-generated annotations can include intents and mentions corresponding to the set of sentences. The instructions can further cause the processor to apply scores to the machine-generated annotations. The scores can be a function of weightings of the intents and mentions. The instructions can further recommend whether to employ the given grammar based on the scores. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    The foregoing will be apparent from the following more particular description of example embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating embodiments of the present invention. 
           [0022]      FIG. 1  is a block diagram illustrating an example embodiment of the present invention. 
           [0023]      FIG. 2  is a block diagram illustrating an example embodiment of the present invention. 
           [0024]      FIG. 3A  is a table illustrating an example embodiment of comparing a manual annotation to a machine-generated annotation and generating a score thereof. 
           [0025]      FIG. 3B  is a table illustrating an example embodiment of a manual annotation compared to a machine-generated annotation and generating a score thereof. 
           [0026]      FIG. 3C  is a table illustrating an example embodiment of a manual annotation compared to a machine-generated annotation and generating a score therein. 
           [0027]      FIG. 4  is a flow diagram illustrating an example embodiment of the present invention. 
           [0028]      FIG. 5  is a network diagram that illustrates a computer network or similar digital processing environment in which embodiments of the present invention may be implemented. 
           [0029]      FIG. 6  is a block diagram of an example internal structure of a computer (e.g., client processor/device or server computers) in the computer system of  FIG. 5 . 
       
    
    
     DETAILED DESCRIPTION 
       [0030]    A description of example embodiments of the invention follows. 
         [0031]      FIG. 1  is a block diagram  100  illustrating an example embodiment of the present invention. An annotating user  102  annotates a set of sample sentences  106  on a manual annotation system  104 . The manual annotation system  104  can be a computer or other user device. The annotating user  102  annotates the set of sample sentences  106  by identifying intents and mentions in the sample sentences. An intent is the basic goal of the interaction of the sample sentence. A mention is a piece of information needed to complete the action indicated by the intent. In the example embodiment illustrated by  FIG. 1 , an example sample sentence  108  states “I want to fly from Montreal to Boston.” The annotating user  102  identifies the intent of the sample sentence  108  as “buy ticket.” The annotating user  102  further identifies mentions in the sample sentence  108  of a “from city” being Montreal and a “to city” being Boston. The annotating user  102  enters these intents and mentions into the manual annotation system  104  to be associated with the sample sentence  108 . The annotating user  102  can continue to annotate other sentences of the set of sample sentences  106 . 
         [0032]    As the annotating user  102  annotates more sentences on the manual annotation system  104 , the set of sample sentences  106  can be checked against these additional manually annotated sentences. The manual annotation system  104  then sends manually-generated annotations  126  to a recommendation system  118 . The sample sentence  108  and set of sample sentences  106  can be entered via text entry, speech-to-text or other speech/voice recognition technology, or other method. 
         [0033]    A machine parser  112  also receives the sample sentence  108  of the set of sample sentences  106 . The machine parser  112  also receives a grammar  110 . The machine parser  112 , based on the grammar  110 , annotates the sample sentence  108 . The machine parser  112  generates an annotation  114  that includes intents and mentions  116 . In this example, the machine parser  112 , based on the grammar  110 , generates an annotation  114  that includes intents and mentions  116  indicating an intent of travel and a “to city” of Boston but without a “from city” of Montreal. Such an omission of the “from city,” or any other mention or intent, is considered a deletion. The annotation  114  is therefore incomplete and indicates that the grammar  110  is not ideal for the particular application of the set of sample sentences  106 . 
         [0034]    The recommendation system  118  receives the annotation  114  and compares the annotation  114  to the manually-generated annotations  126  for the sample sentence  108 . Based on the comparison, the recommendation system  118  issues a recommendation whether to use the grammar  120 . A recommendation presentation system  124  receives the recommendation  120  and delivers the recommendation to a recommendation seeking user  122 . The recommendation presentation system  124  can be either the same machine as or a separate machine from the manual annotation system  104 . The recommendation seeking user  122  can therefore determine whether to employ the particular grammar  110  or to use a different grammar. 
         [0035]      FIG. 2  is a block diagram  200  illustrating an example embodiment of the present invention. A sample sentence  208  is forwarded to a manual annotator  202  and a parser  212 . The manual annotator  202  can be an annotating user  102  as described in  FIG. 1 . The manual annotator  202  generates manually-generated annotations  226  that include intents and mentions. The manual annotator  202  sends the manually-generated annotations  226  to a comparison module  252 . 
         [0036]    The parser  212  receives the sample sentence  208  and also receives grammars  210   a - n  of a queue of grammars  210 . For each grammar  210   a - n  of the queue of grammars  210 , the parser  212  generates annotations  226   a - n . Each of these annotations corresponds to a particular grammar  210   a - n . The parser  212  sends each of the annotations  226   a - n  to the comparison module  252 . 
         [0037]    The comparison module  252 , for each of the grammars  210   a - n , generates a comparison of manually-generated annotations to the machine-generated annotations  262  and forwards the comparison  262  to a scoring module  254 . The scoring module  254  generates scores of the annotations  264  and sends the scores  264  to a recommendation module  256 . The recommendation module generates a recommendation  266  whether to add the grammar to a candidate grammar list based on the scores  264 . The candidate grammar list is later presented to the user, who then can select one grammar for use in the NLU project. 
         [0038]      FIG. 3A  is a block diagram  300  illustrating an example embodiment of comparing a manual annotation  304  to a machine-generated annotation  306  and generating a score  308  thereof. The table  300  indicates an expected annotation type  302  for each expected intent and mention of the manual annotation  304  and machine-generated annotation  306 . In this example, the expected annotation type is an intent  310 , a “from city”  312 , and a “to city”  314 . The manual annotation  304  has an intent  310  of “buy ticket,” a mention of “from city”  312  of Montreal, and a mention of “to city”  314  of Boston. The manual annotation  304  is the correct annotation interpretation of the sample sentence. The machine-generated annotation  306 , in this example for this sample sentence, has an intent  310  of “buy ticket,” a mention of “from city”  312  being a deletion, where the grammar did not detect the from city, and a mention of “to city”  314  of Boston. In comparing the manual annotation  304  and machine-generated annotation  306 , computing the correct intent is given a score of 0.5, deleting mention of “from city”  312  has a score of 0.1 and correctly detecting the mention of “to city”  314  has a score  308  of 0.3. The scores described above can be weighted either by rules indicating scores for matches, non-matches, deletions, or etc., or by a statistical regression method. 
         [0039]      FIG. 3B  is a table  330  illustrating an example embodiment of a manual annotation  334  compared to a machine-generated annotation  336  and generating a score  338  thereof. In comparing the manual annotation  334  to the machine-generated annotation  336 , computing the correct intent is given a score of 0.5, correctly detecting the “from city”  342  of Montreal is given a score of 0.3, and incorrectly detecting the “to city” of Boston as Boise is given a score of 0.0. 
         [0040]      FIG. 3C  is a table  360  illustrating an example embodiment of a manual annotation  364  compared to a machine-generated annotation  366  and generating a score  368  therein. In comparing the manual annotation  364  to the machine-generated annotation  366 , computing the incorrect intent of “cooking” is given a score of 0.0, while correctly detecting the “from city”  372  as Montreal is given a score of 0.3 and correctly detecting the “to city”  374  as Boston is also given a score of 0.3. 
         [0041]      FIG. 4  is a flow diagram  400  illustrating an example embodiment of the present invention. The method begins by first loading manually-generated annotations of a sample sentence ( 402 ). The process then loads machine-generated annotations based on a given grammar ( 404 ). Then, the process compares intents and mentions of manually-generated annotations to intents and mentions from machine-generated annotations ( 406 ). Then the system applies scores to machine-generated annotations as a function of the intents and mentions ( 408 ). Then the system determines whether to add the given grammar to a list of grammars to recommend to the user. ( 410 ) The determination is based on the score assigned to the given grammar. The system then determines whether there are more grammars to test ( 412 ). If more grammars are available, the system load the machine-generated annotations based on the loaded given grammar ( 404 ). Otherwise, the system presents the recommendations to the user ( 414 ). Upon presentation to the user, user can select one grammar to use for the NLU project. 
         [0042]      FIG. 5  illustrates a computer network or similar digital processing environment in which embodiments of the present invention may be implemented. 
         [0043]    Client computer(s)/devices  50  and server computer(s)  60  provide processing, storage, and input/output devices executing application programs and the like. The client computer(s)/devices  50  can also be linked through communications network  70  to other computing devices, including other client devices/processes  50  and server computer(s)  60 . The communications network  70  can be part of a remote access network, a global network (e.g., the Internet), a worldwide collection of computers, local area or wide area networks, and gateways that currently use respective protocols (TCP/IP, Bluetooth®, etc.) to communicate with one another. Other electronic device/computer network architectures are suitable. 
         [0044]      FIG. 6  is a diagram of an example internal structure of a computer (e.g., client processor/device  50  or server computers  60 ) in the computer system of  FIG. 5 . Each computer  50 ,  60  contains a system bus  79 , where a bus is a set of hardware lines used for data transfer among the components of a computer or processing system. The system bus  79  is essentially a shared conduit that connects different elements of a computer system (e.g., processor, disk storage, memory, input/output ports, network ports, etc.) that enables the transfer of information between the elements. Attached to the system bus  79  is an I/O device interface  82  for connecting various input and output devices (e.g., keyboard, mouse, displays, printers, speakers, etc.) to the computer  50 ,  60 . A network interface  86  allows the computer to connect to various other devices attached to a network (e.g., network  70  of  FIG. 5 ). Memory  90  provides volatile storage for computer software instructions  92  and data  94  used to implement an embodiment of the present invention (e.g., structure generation module, computation module, and combination module code detailed above). Disk storage  95  provides non-volatile storage for computer software instructions  92  and data  94  used to implement an embodiment of the present invention. A central processor unit  84  is also attached to the system bus  79  and provides for the execution of computer instructions. 
         [0045]    In one embodiment, the processor routines  92  and data  94  are a computer program product (generally referenced  92 ), including a non-transitory computer-readable medium (e.g., a removable storage medium such as one or more DVD-ROM&#39;s, CD-ROM&#39;s, diskettes, tapes, etc.) that provides at least a portion of the software instructions for the invention system. The computer program product  92  can be installed by any suitable software installation procedure, as is well known in the art. In another embodiment, at least a portion of the software instructions may also be downloaded over a cable communication and/or wireless connection. In other embodiments, the invention programs are a computer program propagated signal product embodied on a propagated signal on a propagation medium (e.g., a radio wave, an infrared wave, a laser wave, a sound wave, or an electrical wave propagated over a global network such as the Internet, or other network(s)). Such carrier medium or signals may be employed to provide at least a portion of the software instructions for the present invention routines/program  92 . 
         [0046]    In alternative embodiments, the propagated signal is an analog carrier wave or digital signal carried on the propagated medium. For example, the propagated signal may be a digitized signal propagated over a global network (e.g., the Internet), a telecommunications network, or other network. In one embodiment, the propagated signal is a signal that is transmitted over the propagation medium over a period of time, such as the instructions for a software application sent in packets over a network over a period of milliseconds, seconds, minutes, or longer. 
         [0047]    While this invention has been particularly shown and described with references to example embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.