Abstract:
Techniques are disclosed for combining natural language generation with query retrieval for context appropriate query recommendation. For example, a computer-implemented method for generating a recommended query for a conversation system in response to an original user query, wherein at least a portion of the original user query is not understandable to a query interpretation process, includes the following steps. Recommendation results are computed, in response to the original user query, using a natural language generation-based recommendation process. Recommendation results are computed, in response to the original user query, using a retrieval-based recommendation process. A recommended query is generated based on consideration of at least a portion of the natural language generation-based recommendation results and at least a portion of the retrieval-based recommendation results.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention generally relates to a method for query recommendation in conversation systems and, more particularly, to a hybrid method that combines natural language generation with query retrieval for context appropriate query recommendation. 
       BACKGROUND OF THE INVENTION 
       [0002]    Conversation systems allow users to interact with computer systems. In order to assist the user with such interaction, some conversation systems employ query recommendation. Existing approaches for query recommendation in conversation systems include tutorials or context-sensitive help. 
         [0003]    Tutorials are often too brief to cover all valid input requests. Existing approaches for context-sensitive help also have limitations. 
         [0004]    For example, finite state machine-based approaches do not scale well. Depending on the granularity of the predicted classes, a decision tree-based help system may be too coarse to provide guidance on the exact wording for each problematic user request. In addition, depending on the coverage of the query corpus used in retrieval-based query recommendation systems, the most relevant pre-stored examples may not be close enough to the current user query to be useful. 
         [0005]    Accordingly, it would be desirable for a query recommendation technique to be able to provide scalable, fine-grained, context-sensitive help on the exact wording of a user query. 
       SUMMARY OF THE INVENTION 
       [0006]    Principles of the invention provide a hybrid method that combines natural language generation with query retrieval for context appropriate query recommendation. 
         [0007]    For example, in one aspect of the invention, a computer-implemented method for generating a recommended query for a conversation system in response to an original user query, wherein at least a portion of the original user query is not understandable to a query interpretation process, includes the following steps. Recommendation results are computed, in response to the original user query, using a natural language generation-based recommendation process. Recommendation results are computed, in response to the original user query, using a retrieval-based recommendation process. A recommended query is generated based on consideration of at least a portion of the natural language generation-based recommendation results and at least a portion of the retrieval-based recommendation results. 
         [0008]    The natural language generation-based recommendation result computing step may include selecting content for use in generating the recommended query. The content selection step may include extracting one or more features from at least one of the original user query and interpretation results generated by the query interpretation process, wherein the one or more extracted features characterize a current interpretation problem associated with the original user query. The content selection step may further include, based on the one or more extracted features, determining and applying one or more rules for use in revising at least a portion of the original user query to generate semantic content for use in generating the recommended query. 
         [0009]    Further, the natural language generation-based recommendation result computing step may further include, based on the semantic content, generating a grammatically-appropriate sentence which forms the recommended query. The grammatically-appropriate sentence generating step may further include retrieving one or more of words, phrases and sentence segments from at least one of the original user query and a query corpus to convey the semantic content for the recommended query. 
         [0010]    The retrieval-based recommendation result computing step may include computing one or more similarity scores based on the original user query and one or more example queries from a query corpus. The one or more similarity scores may include one or more of a surface similarity score, a semantic similarity score, and a context similarity score. The one or more similarity scores may be used to identify one or more of the example queries from the query corpus to be included as part of the retrieval-based recommendation results. 
         [0011]    These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1  is a diagram illustrating implementation of a hybrid query recommendation method in a conversation system, according to an embodiment of the invention. 
           [0013]      FIG. 2  is a diagram illustrating a query recommendation system, according to an embodiment of the invention. 
           [0014]      FIG. 3  is a diagram illustrating a natural language generation (NLG)-based recommendation process using knowledge sources such as ontology and query corpus, according to an embodiment of the invention. 
           [0015]      FIG. 4  is a diagram illustrating a retrieval-based recommendation process using knowledge sources such as query corpus, according to an embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0016]    Principles of the invention provide a hybrid query recommendation framework that facilitates robust natural language interaction for systems with imperfect interpretation. When receiving a problematic user query that can not be understood by the natural language interpreter of a conversation system, the method dynamically recommends valid queries that are most relevant to the current user request. Based on the recommendations, the user can revise his request accordingly so that the next round of conversation will be more successful. 
         [0017]    More particularly, as will be explained in detail below, an exemplary embodiment of the invention provides a hybrid query recommendation framework which combines natural language generation with query retrieval to improve the robustness of query understanding. That is, such framework may help users recover from a conversation system&#39;s input interpretation problem. 
         [0018]    Further, exemplary embodiments of the invention not only take into consideration the robustness of the recommendation system, but also its scalability so that it is feasible for non-trivial conversation applications. 
         [0019]    Still further, another exemplary embodiment of the invention provides accurate and context-sensitive recommendations that help users revise problematic queries so that the revised queries have a better chance to be understood by the system. 
         [0020]    Accordingly, principles of the invention provide a hybrid query recommendation framework that is executable within a multimodal conversation application. An example of a particular multimodal conversation application is in the real-estate domain in which potential home buyers interact with the system using multiple modalities, such as speech and gesture, to request residential real-estate information. The hybrid query recommendation framework executing within the application takes a problematic user query, associated system interpretation results, and the current conversation context as input and formulates query recommendations that are most relevant to the current user query. 
         [0021]    It is to be understood that while an example conversation system domain is given as a real-estate application, principles of the invention are not limited to any particular domain or conversation system architecture. 
         [0022]    Referring now to  FIG. 1 , a hybrid query recommendation method is shown being implemented within the capabilities of computing resources. The method is shown as module  103  within a domain  100 . The domain can be any one of a multitude of environments that accept requests for information. The domain example used throughout this description is that of the real-estate domain. In the real-estate domain, a user can query a system for information regarding specific houses, towns or schools. 
         [0023]    The user request is then sent to an interpretation engine  101  for analysis. If the interpretation engine can understood the user query without any problem, the interpretation result is sent to the backend  102  for further processing. If the interpretation engine  101  has a problem understanding the input query, recommendation engine  103  is activated and it suggests a set of alternative queries to guide the user to revise his original query. 
         [0024]    The domain  100  is typically implemented within a central processing unit. It interfaces with external data entry  104  and data output  105  elements through a network  108 . The network may be any one of several types of connectivity including, but not limited to, a local area network, a wide area network such as, but not limited to, connectivity through the Internet. 
         [0025]    The data entry  104  may include, but not be limited to, a keyboard, a voice recognition device, a mouse, a touch sensitive screen, or other such devices. The data output  105  element may include, but not be limited to, a computer screen, a printer, a video display, monitor, or other such devices. Likewise, the system for performing the method, software or firmware containing the instruction set for performing the method can be processed within a central processing unit or other computer resource. 
         [0026]    Recommendation engine  103  produces the solutions based on examples in a query corpus  106  which is stored either within the domain  100  or, as shown in  FIG. 1 , in a separate storage medium and/or database. The recommendation engine  103  may also use additional data sources such as ontology  107 . Both the query corpus  106  and domain ontology are accessed through a communication link  109 . The communication link  109  may be a local area or wide area network. The communication link  109  may also be a direct connection such as a bus internal to the domain  100 . By accessing the query corpus  106  to formulate the solution, the recommended queries can demonstrate desired properties, such as scalability and robustness. 
         [0027]    For the real-estate domain example, a user would submit a request about a particular house, town or school through the data entry  104  element. The interpretation engine  101  will analyze the request. If the interpretation engine  101  can understand the user request without any problem, the interpretation results will be sent to the backend  102  for data retrieval and data presentation. If the interpretation engine  101  has a problem understanding the user request or part of the user request, the query recommendation engine  103  is called to suggest valid alternative queries. These alternative queries are sent to the user through the data output element  105 . After receiving recommended queries, the user will revise his original request or submit a new request. 
         [0028]    Note that elements shown in subsequent figures having the same reference numeral as shown in  FIG. 1  have the same or similar functions as described above. 
         [0029]    Referring now to  FIG. 2 , details of recommendation engine  103  are shown. More particularly,  FIG. 2  illustrates a hybrid query recommendation engine. 
         [0030]    As shown, there are two independent recommenders in the recommendation engine: a natural language generation (NLG)-based recommender  201  and a retrieval-based recommender  202 . The NLG-based recommender  201  takes the interpretation results from the interpretation engine  101  as its input. In addition, recommender  201  also uses resources such as the query corpus  106  and ontology  107  as its knowledge base. Its output is a set of ranked query recommendations. 
         [0031]    Similarly, the retrieval-based recommender  202  produces a separate set of recommendations based on the interpretation results as well as the examples in the query corpus  106 . Since each recommender produces a set of recommendations independently, both sets of recommendations are sent to the merger  203  to form the final recommendations. One embodiment of a method for query merging selects the final recommendations proportionally from the candidates produced by each recommender. 
         [0032]    We now refer to  FIG. 3  for details on NLG-based recommender  201 . Once a problematic user request is detected by interpretation engine  101 , the user query and the interpretation results are sent to the NLG-based recommender for analysis. In the NLG-based recommender, the content selector  303  decides the content for each recommendation. The sentence generator  304  forms a grammatical sentence to convey the content in each recommendation. One embodiment of a content selection method uses a classification-based machine learning approach to categorize the current interpretation problem and decide proper content revision operators. Another embodiment of the method may use manually crafted content selection rules to suggest the content of alternative queries. 
         [0033]      FIG. 3  shows a classification-based content selection approach. Using this method, the feature extractor  301  automatically derives a set of syntactic, semantic and surface features from the input query. Table 1 lists typical features extracted from an input query “Show houses in GOOD school districts” in which “good” is an unknown word to the system. 
         [0000]    
       
         
               
             
               
               
               
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 FEATURES EXTRACTED FOR CONTENT SELECTION 
               
             
          
           
               
                 No 
                 Name 
                 Definition 
                 Example 
               
               
                   
               
             
          
           
               
                 1 
                 Element Syntactic Relation 
                 The relationship between the problem element and the element anchor 
                 Modifier-Head 
               
               
                 2 
                 Problem Element POS 
                 The POS of the problem element 
                 Adjective 
               
               
                 3 
                 Problem Element Role 
                 The role played by the problem element in its relationship with its anchor 
                 Modifier 
               
               
                 4 
                 Problem Element 
                 Further classification for WOI words. For OOV words, always assign “other” 
                 Quality 
               
               
                   
                 Classification 
               
               
                 5 
                 Anchor Element POS 
                 The POS for the anchor element 
                 NP 
               
               
                 6 
                 Anchor Element Role 
                 The role played by the anchor element in its relationship with the problem 
                 Head 
               
               
                   
                   
                 element 
               
               
                 7 
                 Anchor Element type 
                 The semantic type associated with the anchor element 
                 Known-Concept 
               
               
                 8 
                 Problem Segment Syntactic 
                 The syntactic relation between the problem and the anchor segment 
                 Modifier-Head 
               
               
                   
                 Relation 
               
               
                 9 
                 Problem Segment POS 
                 The POS for the problem segment 
                 NP 
               
               
                 10 
                 Problem Segment Role 
                 The role played by the problem segment in its relationship with its anchor 
                 Modifier 
               
               
                 11 
                 Anchor Segment POS 
                 The POS for the Anchor Segment 
                 Noun 
               
               
                 12 
                 Anchor Segment Role 
                 The role played by the anchor segment in its relationship with the problem 
                 Head 
               
               
                   
                   
                 segment 
               
               
                 13 
                 Anchor Segment Type 
                 The semantic type associated with the anchor segment 
                 Known-Concept 
               
               
                   
               
             
          
         
       
     
         [0034]    Based on the feature vector extracted by the feature extractor  301  as well as the training examples in a problematic query corpus  305  (part of query corpus  106 ), the classifier  302  selects one or more content revision operators (or rules), indicating proper ways to revise the original user query to form the semantics of a recommendation. Table 2 lists the most common content revision operators designed for structured information-seeking applications. The operators are defined based on domain independent concepts such as objects, attributes, constraints, and operators specified in Standard Query Language (SQL). 
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 CONTENT REVISION OPERATORS 
               
             
          
           
               
                 Name 
                 Description 
                 Example 
               
               
                   
               
               
                 Op-Constraint- 
                 Replace an un-interpretable word with constraints that 
                 Replace “good” in “good school district” with all the quality- 
               
               
                 Ontology 
                 are compatible with the word and the ontology 
                 related school district constraints 
               
               
                 Op-Constraint- 
                 Replace an un-interpretable word with constraints that 
                 Replace “low” in “Houses with low tax” with a constraint 
               
               
                 Attribute 
                 are compatible with the current attribute 
                 on the house attribute AnnualTax 
               
               
                 Op-Attribute- 
                 Replace an un-interpretable word with attributes that 
                 Replace “size” in “the size of the house” with an attribute 
               
               
                 Ontology 
                 are compatible with the ontology 
                 of house that is compatible with size e.g., square footage. 
               
               
                 Op-Operator- 
                 Replace un-interpretable word with a known operator 
                 Replace “save” in “save the houses” with a known 
               
               
                 Ontology 
                   
                 operator “show” 
               
               
                   
               
             
          
         
       
     
         [0035]    After receiving the content revision operators from the classifier  302 , the content selector  303  applies each content revision operator to the interpretation result of the current user query one by one and formulates the semantic representation of alternative queries. 
         [0036]    Ontology  107  is used by the content selector  303  as follows. As mentioned above, input to the content selector is a set of content revision operators. For example, if the user query is “show xxx of houses in Pleasantville” and if one of the content revision operators selected by the classifier  302  is OpAttributeOntology, the content selector will replace xxx with a house attribute. To do this, it sends an inquiry to ontology  107  to retrieve all the possible house attributes and generate one recommendation for each house attribute. Some generated recommendations are as follows: “show the price of the house,” “show the age of the house,” “show the school district of the house,” etc. 
         [0037]    Given the semantics for each recommended query, the sentence generator  304  produces a grammatical sentence to convey the semantics in a recommendation. One embodiment of the sentence generator uses cases-based reasoning and rule-based adaptation to formulate grammatical sentences. Another embodiment of the sentence generator uses template-based approach to generate fluent sentences based on sentence templates. Another embodiment of the sentence generator produces fluent sentence based on English grammar. 
         [0038]      FIG. 3  illustrates a preferred embodiment in which the system uses a cascade model in case-based sentence generation. In the cascade model, the sentence generator  304  first retrieves words, phrases and sentence segments that can convey some of the content in a recommendation from the current user query. Then, the sentence generator retrieves words, phrases and sentence segments from the legal query corpus  306  (part of query corpus  106 ) to convey the rest of the content in a recommendation. Finally, the system applies adaptation rules to combine all the words, phrases and sentence segments to form a fluent and grammatical sentence. 
         [0039]    It is to be understood that the NLG-based recommender may also employ known natural language generation techniques, by way of example only, techniques described in Shimei Pan and James Shaw, “SEGUE: A Hybrid Case-Based Surface Natural Language Generator,” Proceedings of the Third International Conference of Natural Language Generation, pages 130-140, Brockenhurst, UK, July 2004. 
         [0040]      FIG. 4  presents details on retrieval-based recommender  202 . For each query example in the query corpus  106 , the system first computes its surface similarity to the current user query (module  401 ). One embodiment of a method for computing surface similarity is based on the String Edit Distance. Another embodiment of a method for computing surface similarity is based on the number of overlapping content words. Another embodiment of a method for computing surface similarity is based on the cosine measure. 
         [0041]    The system also computes semantic similarity (module  402 ) based on the interpretation results produced by the interpretation engine  101 . One embodiment of a method for computing semantic similarity is based on semantic graph matching. Another embodiment of a method for computing semantic similarity is based on the number of overlapping nodes in the semantic graph. 
         [0042]    In addition, the system also computes context similarity (module  403 ). One embodiment of a method for computing context similarity is based on the Euclidian distance between two context feature vectors. 
         [0043]    Next, a combined similarity score is computed based on a linear combination of each individual similarity score (module  404 ). 
         [0044]    Finally, the combined score is used to rank all the examples in the query corpus  106  and the ones with the highest combined similarity score (module  405 ) are considered for suggested to the user. 
         [0045]    Advantageously, as illustratively described herein, principles of the invention provide a method for a hybrid query recommendation framework that combines natural language generation-based recommendations with retrieval-based results to facilitate robust natural language interaction for conversation systems with imperfect interpretation. When receiving a problematic user query, the recommendation system dynamically recommends valid queries that are most relevant to the current user request so that the user can revise his request accordingly. Comparing with existing methods, our approach offers several major advantages, for example: improving query recommendation quality and system scalability by dynamically composing new queries for recommendation, and combining NLG-based recommendations with retrieval-based results to improve robustness. 
         [0046]    Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be made by one skilled in the art without departing from the scope or spirit of the invention.