Abstract:
A method for retrieving documents in a knowledge database is disclosed in which a natural language query question is mapped to a plurality of equivalent strings. Both relevancies in meaning and in wording pattern are taken into account in ranking the equivalent strings by introducing respective weight factors. A document coupled to the top ranked equivalent string is retrieved and displayed to the questioner.

Description:
TECHNICAL FIELD 
     This invention relates to information retrieval technologies, and more particularly to a method for retrieving documents by intelligently matching a query string to one or more pre-stored strings. A novel ranking method is employed for said intelligent matching. 
     BACKGROUND OF THE INVENTION 
     Frequently Asked Questions (“FAQs”) are commonly presented by customers to a company. Due to the high repetition of FAQs, standard answers are usually pre-stored in a database retrievable by a query inputted into the system. A customer may present the question by dialing into the IVR system of the company, or may input the query at the website of the company. 
     Natural language queries are more acceptable to common customers as no special searching rules are required to be understood. A questioner can simply input a question (a query string) in natural language into the retrieval system and receive the prestored, correct answer. This is implemented by a mapping technique used inside the retrieval system. Specifically, a group of sample questions are pre-stored in the database, each with a corresponding answer. Upon receiving a query in natural language format, the system intelligently maps, by using a relatively complex, artificial intelligence algorithm, the query question to a pre-stored sample question which is coupled to an answer. 
     Due to the casual use of words in a natural language query string, it is important to improve the technique in successfully mapping the query string to a sample string. At present, natural language processing techniques are able to detect equivalent strings (strings that have the essentially the same meaning as the query string). They may detect the equivalent strings that are worded very differently from the query string and reject strings that are worded similar to the query string but have a different meaning. Usually more than one equivalent string is mapped to the same query string and ranked by meaning. An answer coupled to the top ranked equivalent string (i.e., that which has a meaning closest to the input string) will be retrieved and displayed to the questioner. 
     However, there is no technique to further distinguish equivalent strings from each other if they have the same ranking in meaning. Furthermore, the ranking among equivalent strings relies solely on either correlation in meaning or correlation in wording pattern, neither of which may be accurate enough and both of which have their limitations. 
     Therefore, there exists a need for improved techniques for the retrieval system to map the query strings and the prestored strings more accurately. 
     SUMMARY OF THE INVENTION 
     In the novel method of the present invention, both meaning and wording pattern are taken into consideration in ranking equivalent strings. Separate modules are utilized, a first for matching the meaning of an input string to prestored questions, and a second and independently operating module for matching word patterns of an input string to a prestored string. When plural strings are deemed to have an equivalent meaning, the word pattern of each is examined and the word pattern closest to a prestored word pattern is utilized. 
     In a preferred embodiment, correlation in meaning and correlation in wording pattern are weighted with different factors to obtain a combined correlation for each equivalent string, and the ranking is implemented based on the combined correlation thus obtained. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and further features and advantages of the present invention may be appreciated from the detailed description of preferred embodiments with reference to the accompanying drawings, in which: 
     FIG. 1 is a schematic illustration of an FAQ retrieval system; 
     FIG. 2 is an embodiment of the present invention; an. 
     FIG. 3 is another embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A typical FAQs retrieval system is schematically shown in FIG.  1 . Database  3  comprises a question source  4  and an answer source  5 . Sample questions are pre-stored in the question source  4  and each of the sample questions is coupled to one of the standard answers that is prestored in the answer source  5 . 
     The natural language query questions are input at a natural language interface  1  which transmits the query to a natural language processor  2 . The questions may be received via text over a data network, or via an audio signal over a data network or a telephone network. If the questions are received via an audio signal, then a speech recognition algorithm, many of which are commercially available, should be employed. 
     The natural language processor  2  runs to detect equivalent questions from the question source  4 . These equivalent questions are ranked by their correlation in meaning to the query question input at the interface  1 . Usually only the answer coupled to the top ranked equivalent question is retrieved and displayed to the user by a proper displaying means such as a monitor or printer. The system may also retrieve answers to some other equivalent questions other than the top ranked one, if necessary. 
     Natural language processors and recognition programs are available widely, and the details of how such programs are implemented are not critical to the present invention. In the present invention however, the output of such programs is not directly used, but instead is combined with a signal that measures the degree of correlation between the wording of an input string and that of potential matches. 
     Sometimes there may be more than one top ranked equivalent questions are detected. In such a situation, correlation in wording pattern may be taken into account to rank the equivalent questions, as shown in FIG.  2 . 
     In FIG. 2, equivalent Questions  30  and  42  are found to have the same correlation in meaning to the query question. To further differentiate them, a step is introduced in which the wording pattern is also taken into consideration. For example, if the query question is “When can I get the payment?”, the Question  30  is “How can I receive my money”, and the Question  42  is “When can I receive the payment”, finally the Question  42  is ranked over the Question  30  because of its higher correlation in wording pattern. 
     The wording pattern may comprise many factors. For example, the system may check how many words are used in both the query question and the equivalent question. Usually the words to be considered will not consider words such as the articles “a”, “the” and the connectives such as “because”, “therefore”, etc. Moreover, the words will be considered in a stemmed form. For example, the words “paying”, “payment”, “pay” will all be considered as “pay”. 
     A more complicated embodiment is shown in FIG.  3 . In this embodiment, both correlation in meaning and correlation in wording pattern are taken into account in determining ranks for all the equivalent questions. 
     Presumably, a query question results in four equivalent questions Q 30 , Q 42 , Q 48  and Q 56  that are highest ranked ones from the correlation in meaning. The system generates a first correlation value or score for meaning, and a second correlation value or score for wording pattern. 
     Conceptually, the A scores (i.e., A 1 -A 4 ) measure the correlation in meaning while the B scores (i.e., B 1 -B 4 ) measure the correlation in wording pattern. These two score series, however, may not have a same weight in ranking the equivalent questions. In some situations correlation in meaning may be more important than correlation in wording pattern, while in other situations correlation in wording pattern may be more important. 
     Having this in mind, a weighing system is introduced to compare the relevant importance of the two scores. In particular, a weight factor X is introduced for A scores and a weight factor Y is introduced for B scores. The relative importance of the relevancies in meaning and in wording pattern is quantified by weight factors X and Y. After being weighed, correlation algorithm is made on the two score series to get final combined scores “C 1 ”, “C 2 ”, “C 3 ”, and “C 4 ” respectively, which reflect both relevancies in meaning and wording pattern as well as their relative importance. Finally the equivalent questions are ranked in accordance with these final combined C scores. Thus, the ranking results are more accurate. Factions that may be taken into account include number of words, length of the string, etc. 
     Usually an answer coupled to the top ranked sample question is retrieved and displayed to the questioner. 
     As an alternative, the system may first display one or more highest ranked equivalent questions to the questioner who may select one among them to retrieve the answer. This, however, may sometimes be inconvenient to the questioner by introducing an additional step and the questioner has to read through several questions before he can determine which is the best. This may be impractical if the query interaction is implemented over a telephone. Nonetheless, the user can be prompted to select one of several questions as they are read. 
     In a preferred embodiment, the weight factors X and Y may be changeable by a questioner so as to fine tune the weight factors X and Y. This is advantageous as a questioner is able to interact with the system. If the questioner is not satisfied with a query result, he may change the weight factors X and/or Y to try for a better hit without changing his query question. 
     For example, if a query question uses more distinguishable keywords, the questioner may increase the weight factor Y so that the final ranking scores will rely more on the correlation in wording pattern than correlation in meaning. If the words used in a query question is less distinguishable, a higher weight factor X may produce a better result. 
     In the past, the correlation between a query question and the equivalent questions cannot be changed unless the questioner changes the query question. Therefore, in order to get a better hit, the questioner had to try many query questions until he got the right answer. With the present invention, it is much more convenient if the questioner may adjust the ranking by only changing the weight factors. 
     Though the above takes a FAQs answer retrieval system as an exemplary embodiment, it will be appreciated that the present invention is also applicable in other document or information retrieval systems and that modifications and variations will be possible to those with ordinary skill in the art without departing from the spirit of the invention. The scope of the invention is therefore intended to be solely defined in the claims.