Patent Abstract:
A computer based software system and method for semantically processing a user entered natural language request to identify and store linguistic subject-action-object (SAO) structures, using such structures as key words/phrases to search local and web-based databases for downloading candidate natural language documents, semantically processing candidate document texts into candidate document SAO structures, and selecting and storing only relevant documents whose SAO structures include a match with a stored request SAO structure. Further features include analyzing relationships among relevant document SAO structures and creating new SAO structures based on such relationships that may yield new knowledge concepts and ideas for display to the user and generating and displaying natural language summaries based on the relevant document SAO structures.

Full Description:
REFERENCE TO PRIORITY APPLICATION  
       [0001]    This application claims the benefit of U.S. Provisional Application No. 60/099,641, filed Sep. 9, 1998.  
     
    
     
       BACKGROUND  
         [0002]    The present invention relates to computer based natural language processing systems and more particularly to computer based systems and methods of processing natural language text to identify Subject, Action, Object triplets and relationships between such triplets, storing this data and processing this data to semantically analyze, select, summarize, store, and display candidate documents containing specific content or subject matter.  
           [0003]    Computer based document search processors are known to perform key word searches for publications on the Internet and World Wide Web. Today, information owners and service providers are adapting their databases to individual tastes and requirements. For example, Boston based Agents, Inc. offers over the Web personalized newsletters for music fans such that classical music lovers are blocked from receiving Rap music advertisements and vice-versa. KD, Inc. of Hong Kong has developed a system that takes into consideration words similar by sense while searching the Web. Today, the user can download 10,000 papers from the Web by typing the word “Screen”. The search system designed by KD, Inc. asks the user whether he/she is seeking papers related to Computer Screen, TV Screen or Window Screen. In this case, the number of unrelated papers will be drastically reduced.  
           [0004]    Software based search processors are able to remember requests of a single user and to conduct personalized non-stop searches on the Web. So, when a user wakes up in the morning, he/she finds references and abstracts of several new Web papers related to his/her area of interest. In 1997, practically all fundamental technical publications, journals, magazines, as well as patents of all industrial countries became available on the Web, i.e., available in electronic format.  
           [0005]    Although key word searching the Web affords the user great value, it also has created and will continue to create substantial problems adversely affecting this value. Specifically, because of the enormous amount of information available on the Web, key word search processors produce too much downloaded information, the vast majority of which is irrelevant or immaterial to the information the user wants. Many users simply give up in frustration when presented with several hundred articles in response to what the user considered a request for only those few articles related to a specific request.  
           [0006]    This problem is also experienced in the technical fields of science and engineering, particularly since there is a growing number of libraries, government patent offices, universities, government research centers, and others adding vast amounts of technical and scientific information for Web access. Engineers, scientists, and doctors are overwhelmed with too many articles, papers. patents and general information on the topic of interest to them. In addition, the user presently has only two choices when examining a downloaded article to determine its relevance to the users project. He/she can either read the authors abstract and/or scan various sections of the full article to determine whether or not to save or print-out that specific document. Since the author&#39;s abstract is not comprehensive, it often omits the reference to the specific subject matter of interest to he user or treats this subject matter in an incomprehensive manner. Thus, scanning the abstract and scanning the full article may have little value and require an inordinate amount of user time.  
           [0007]    Various attempts purport to increase the recall and precision of the selection such as U.S. Pat. Nos. 5,774,833 and 5,794,050 incorporated herein by reference, however, these methods simply rely on key word or phrase searching with various techniques of selection based on variations of the key words, or purported understanding of textual phrases. These prior methods may improve recall but tend to require too much physical and mental effort and time to determine why the document was selected and what is the pertinent part. This results from the entire document or abstract being presented without summary or concept generation.  
         SUMMARY OF EXEMPLARY EMBODIMENT OF PRESENT INVENTION  
         [0008]    A computer based software system and method according to the principles of the present invention solves the foregoing problems and has the ability to perform a non-stop search of all databases on the Web or other network for key words and to semantically process candidate documents for specific knowledge concepts, such as technological functions or specific physical effects, so that only the very few prioritized or a single document meeting the search criteria is presented or identified to the user.  
           [0009]    Further, the computer based software system in accordance with the principles of the present invention captures these highly relevant documents and creates a compressed, short summary of the precise technical physical aspects designated by the search criteria.  
           [0010]    Another aspect of the present invention includes using the semantic analysis results of the selected documents to create new ideas of knowledge concepts. The system does this by analyzing the subject, action, and object triplets mentioned in the documents, identifying cause and effect triplet relationships, and re-organizing these triplet representations into new and/or different profiles of such elements. As further described below, some of these reorganized sets of relationships among these elements may comprise new concepts never before thought of by anyone.  
           [0011]    According to an aspect of the present invention, the method and apparatus begins with the user entering natural language text related to the task, concept, or subject matter for which the user desires to acquire publications or documents. The system analyzes this request text and automatically tags each word with a code that indicates the type of word it is. Once all words in the request are tagged, the system performs a semantic analysis that, in one example, includes determining and storing the verb groups within the first sentence of the request, then determining and storing the noun groups within that sentence of the request. This process is repeated for all sentences in the request.  
           [0012]    Next, the system parses each request sentence with an hierarchical algorithm into a coded framework (tree) which is substantially indicative of the sense of the sentence. The system includes databases of various types to aid in generating the coded framework, such as grammar rules, parsing rules, dictionary synonyms, and the like. Once parsed, sentence codes are stored, the system identifies Subject-Action-Object (SAO) extractions within each sentence and stores them. A sentence can have one, two, or a plurality of SAO extractions as seen in the detailed description below. Each extraction is normalized into a SAO structure by processing extractions according to certain rules described below. Accordingly, the result of the semantic analysis routine performed on the request test is a series of SAO structures (triplets) indicative of the content of the request. These request SAO structures are applied to (1) a comparative module for comparing the SAO structures of candidate documents as described below and (2) a search request and key word generator that identifies key words and key combinations of words, and synonyms thereof, for searching the Web internet, intranet, and/or local databases for candidate documents. Any suitable search engine, e.g. Alta Vista™, can be used to identify, select, and download candidate documents based on the generated key words.  
           [0013]    It should be understood that, as mentioned above, key word searching produces an over-abundance of candidate documents. However, according to the principles of the present invention, the system performs substantially the same semantic analysis on each candidate document as performed on the user input search request. That is, the system generates an SAO structure(s) for each sentence of each candidate document and forward them to the comparative Unit where the request SAO structures are compared to the candidate document SAP structures. Those few candidate documents having SAO structures that substantially match the request SAO structure profile are placed into a retrieved document Unit where they are ranked in order of relevance. The system then summarizes the essence of each retrieved document by synthesizing those SAO structures of the document that match the request SAO structures and stores this summary for user display or printout. Users can later read the summary and decide to display or print out or delete the entire retrieved document and its SAO&#39;s.  
           [0014]    As stated above, the SAO structures for each sentence for each retrieved document are stored in the system according to the present invention. According to the knowledge creativity aspect of the present invention, the system analyzes all these stored structures, identifies where common or equivalent subjects and objects exist and reorganizes, generates, synthesizes, new SAO structures or new strings (relationships) or SAO structures for user&#39;s consideration. Some of these new structures or strings may by unique and comprise new solutions to problems related to the user&#39;s requested subject matter. For example, if two structures S1-A1-O1 and S2-A2-O2 are stored, and the present system recognizes that S2 is equivalent to or the synonym for or has some other stored relation to O1 then it will generate and store for the user&#39;s access a summary of S1-A1-S2-A2-O2. Of if the system stores an association between S1 and A2 it can generated S1-A1/A2-O1 to suggest improvement of O1 toward desired results.  
           [0015]    Other and further advantages and benefits shall become apparent with the following detailed description when taken in view of the appended drawings, in which:  
       
    
    
     DRAWING DESCRIPTION  
       [0016]    [0016]FIG. 1 is a pictorial representation of one exemplary embodiment of the system according to the principles of the present invention.  
         [0017]    [0017]FIG. 2 is a schematic representation of the main architectural elements of the system according to the present invention.  
         [0018]    [0018]FIG. 3 is a schematic representation of the method according to the principles of the present invention.  
         [0019]    [0019]FIG. 4 is a schematic representation of Unit  16  of FIG. 2.  
         [0020]    [0020]FIG. 5 is a schematic representation of Unit  20  of FIG. 2.  
         [0021]    [0021]FIG. 6 is a schematic representation of Unite  22  of FIG. 2.  
         [0022]    [0022]FIG. 7 is a typical example of the user request text entered by use.  
         [0023]    [0023]FIG. 8 is a tagged and coded representation version of text of FIG. 7.  
         [0024]    [0024]FIG. 9 is an identification of verb groups of the text of FIG. 8.  
         [0025]    [0025]FIG. 10 is an identification of noun groups of the coded text of FIG. 8.  
         [0026]    [0026]FIG. 11 is a representation of parsed hierarchy coded text of FIG. 8.  
         [0027]    [0027]FIG. 12 is a representation of SAO extraction of the text of FIG. 7.  
         [0028]    [0028]FIG. 13 is a representation of SAO structures of the extraction of FIG. 12.  
     
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS  
       [0029]    One exemplary embodiment of a semantic processing system according to the principles of the present invention includes:  
         [0030]    A CPU  12  that could comprise a general purpose personal computer or networked server or minicomputer with standard user input and output driver such as keyboard  14 , mouse  16 , scanner  19 , CD reader  17 , and printer  18 . System  10  also includes standard communication ports  21  to LANs, WANs, and/or public or private switched networks to the Web.  
         [0031]    With reference to FIGS.  1 - 6 , the semantic procession system  10  includes a temporary storage or database  12  for receiving and storing documents downloaded from the Web or local area network generated as a user request text with use of keyboard  14  or one of the other input devices. User can type the request, examples disclosed below, or enter full documents into DB  12  and designate the document as user&#39;s request. System  10  further includes semantic processor  14  for receiving the entire text of each document and includes a Subject-Action-Object (SAO) analyzer Unit  16  that tags each word of each sentence with a code type (such as Markov chain theory code). Unit  16  then identifies each verb group and noun group, (described below) within each sentence and parses and normalizes each sentence into SAO structures that represent the sense of the sentence. Unit  16  applies its output to DB of SAO structures  18 . SAO processor Unit  20  stores the request SAO structures and receives the SAO structures of each sentence of each document stored in Unit  18 . Unit  20  compares the document SAO&#39;s to the request SAO&#39;s and deletes out those documents with no matches. The SAO structures of matched documents are stored back in Unit  18  or some other storage facility. In addition, Unit  20  analyzes SAO structures within a single document or with those of one or more other relevant documents, searches for relationships among S-A-O&#39;s and generates new SAO structures for user consideration. These new structures are stored in Unit  18  or some other storage facility in the system.  
         [0032]    Unit  14  further includes natural language Unit  22  that receives SAO structures in table form and synthesizes structures in to natural language form, i.e. sentences.  
         [0033]    Unite  14  also includes keyword Unit  24  for receiving SAO structures and extracts key words and phrases from them and acquires their synonyms for use as additional key words/phrases.  
         [0034]    Database Units  26 ,  28 , and  30  receive the outputs from Unit  14 , generally as shown, for storing the natural language summaries of selected SAO structures as described below and the key words/phrases that form user request sent to search engines through port  21 .  
         [0035]    Unit  16  includes document pre-formatter  32  that receives full text of documents from Unit  12  and converts the text and other contents to a standard plain text format. Text coder  34  analyzes each word of each sentence of text and tags a code to every word which code designates the word type, see FIG. 8. Various databases designated  44  in FIG. 4 are available to aid the Units of Unit  16 . Following tagging, recognizer Unit  36  identifies the verb groups (FIG. 9) and the noun groups of each sentence (FIG. 10). Sentence parser  38  then parses each sentence into a hierarchical coded form that represents the sense of the sentence. FIG. 11 S-A-O extractor  40  organizes the SAO&#39;s of each sentence into extracted table format (FIG. 12). Then normalizer  42  normalizes the extractions into SAO structures as described above (FIG. 13).  
         [0036]    SAO processor  20  includes three main Units. Comparative Unit  46  receives SAO structures from database  18 . One set of these structures originates from the user request text described above and other sets originate from the candidate documents. Unit  46  then compares these two sets looking for matches between SAO structures of these two sets. If no match results then the candidate document and associated SAO&#39;s are deleted. If a match is identified then the document is marked relevant and ranked and stored in Unit  12  and its SAO structures stored in Unit  18 . Unit  46  then compares all candidate documents in sequence and in the same way as described.  
         [0037]    Unit  20  also includes the SAO structure reorganizing Unit  48  to synthesize new SAO structures from different documents on the same matter and combines them into the new structure, as described above, and applies them to Unit  18 .  
         [0038]    Filtering Unit  50  analyzes every SAO structure of each document and blocks or deletes those not relevant to the SAO structures of the request.  
         [0039]    Reference  52  designates some of the databases available to aid sub-units of Unit  20 .  
         [0040]    SAO synthesizer Unit  22  (FIG. 6) includes a Subject detector  54  for detecting the content of the subject for each received SAO structure. If S is detected then the SAO is fed to Unit  56  in which the tree structure of the verb group(s) is restored to natural language using grammar, semantic, speech patterns, and synonyms rules database  66 . Synthesizer  58  does the same for subject noun groups and synthesizer  60  does the same for object noun groups. Combiner  68  then organizes and combines these groups into a natural language sentence.  
         [0041]    If S was not detected by Unit  54 , the SAO structures are processed by synthesizer  62  to restore the verb group in passive form. Synthesizer  64  processes the object noun group for a passive sentence and combiner  70  to organize and combine the groups into a natural language sentence.  
         [0042]    If SAO structures received by Unit  54  bear new structure markings, then combiners  68  and  70  apply their output to Unit  28  and if they were marked existing SAO structure, then units  68 ,  70  apply output to Unit  26 . See FIG. 3.  
         [0043]    The salient steps to the method according to the principles of the present invention are shown in FIG. 3, where the number in the parenthesis refer to the Units of FIG. 2 where the process steps take place. A session begins with the user inputting a natural language request which could be customized with the use of the keyboard or would be a natural language document entered via one of the input devices shown in FIG. 1. A typical user generates customized request as shown in FIG. 7, System  10  Unit  14 , then by first tagging each word with a type code (See FIG. 8) then identifying the verb groups of each sentence (FIG. 9) and noun groups of each sentence (FIG. 10) then processing each sentence into an hierarchical tree (FIG. 11) and then extracting the SAO extractions where all extracted words are the originals of the request (FIG. 12).  
         [0044]    Then the method normalizes these words (modifies) each as each action is changed to its infinitive form. Thus, “is isolated” FIG. 12 is changed to “ISOLATE”, the word “to” being understood (FIG. 13). It should be understood that not all attributes of the subject, action and objects appearing in FIG. 11 are shown in FIGS. 12 and 13, but the system know the full attributes associated with the SAO elements and these attributes are part of the SAO structure. Also, note in FIG. 13, no subject is listed for the last action because is indicated pursuant to the planning rules. This absence does not affect the reliability of the overall method because all sentences of the candidate documents the include an A-O of Isolate-slides will be considered a matter regardless of the subject. The normalized SAO&#39;s are called herein as SAO structures. These users request SAO structures are stored and applied in tow following steps (i) synthesis of key word/phrases of user request; (ii) a comparative analysis of SAP structure of each sentence of each candidate documents as described below.  
         [0045]    The request SAO structure key words/phrases are stored and sent to a standard search engine to search for candidate documents in local databases, LANs and/or the Web. Alta Vista™, Yahoo™, or other typical search engines could be used. The engine, using the request SAO structure key words/phrases identifies candidate documents and stores them (full text) for system  10  analysis. Next the SAO analysis as described above for the search request is repeated for each sentence of each candidate document so that SAO structures are generated and stored as indicated in FIG. 3. In addition, the SAO structures of each document are used in the comparative steps where the request SAO structures are compared with the candidate document SAO structures. If no match is found then the documents and related SAO structures are deleted from the system. If one or more matches are found then the document and related structures are marked relevant and its relevancy marked for example on a scale of 1.0 to 100. The full relevant document text is permanently stored (although it can later be deleted by user if desired) for display or print-out as user desires. Relevant SAO structures are also marked relevant and permanently stored.  
         [0046]    Next System  10  filters out the least relevant SAO structures and uses the matched SAO structures of each relevant document to synthesize into natural language summary sentence(s) the matched SAO structures and the page number where the complete sentence associated with the matched SAO structures and the page number where the complete sentence associated with the matched SAO structure appears. This summary is stored and available for user&#39;s display or print-out as desired.  
         [0047]    Filtered relevant SAO structures of relevant document(s) are analyzed to identify relationships among the subjects, actions, and objects among all relevant structures. Then SAO structures are processed to reorganize them into new SAO structures for storage and synthesis into natural language new sentence(s). The new sentences may and probably some of them will express or summarize new ideas, concepts and thoughts for users to consider. The new sentences are stored for user display or pint-out.  
         [0048]    For example, if  
         [0049]    S 1 -A 1 -O 1    
         [0050]    S 2 -A 2 -O 2    
         [0051]    S 3 -A 3 -O 3    
         [0052]    and S 1  is the same as or a synonym of O 3 , then S 3 -A 3 -S 1 -A 1 -O 1  is synthesized into a new sentence and stored.  
         [0053]    Accordingly, the method and apparatus according to the present invention provides use automatically with a set of new ideas directly relating to user&#39;s requested area of interest some of which ideas are probably new and suggest possible new solutions to user&#39;s problems under consideration and/or the specific documents and summaries of pertinent parts of specific documents related directly to user&#39;s request.  
         [0054]    Although mention has been made herein of application of the present system and method to the engineering, scientific and medical fields, the application thereof is not limited thereto. The present invention has utility for historians, philosophers, theology, poetry, the arts or any field where written language is used.  
         [0055]    It will be understood that various enhancements and changes can be made to the example embodiments herein disclosed without departing from the spirit and scope of the present invention.

Technology Classification (CPC): 8