Patent Publication Number: US-11645479-B1

Title: Method for AI language self-improvement agent using language modeling and tree search techniques

Description:
REFERENCE TO RELATED APPLICATION 
     The present application is related as a continuation-in-part to U.S. Provisional Patent No. 62/931,815, filed Nov. 7, 2019, entitled “A Practical Method for Creating a Self-Improving Agent Using Language Modeling and Tree Search,” and invented by Kino Coursey. 
    
    
     TECHNICAL FIELD OF THE INVENTION 
     The present invention relates to artificial intelligence in language applications and in particular to machines programed to use artificial intelligence to simulate agents for interacting and communicating with humans. 
     BACKGROUND OF THE INVENTION 
     Prior art speech recognition and speech synthesis computing has been provided by recognizing and responding to a list of predetermined prompts. Speech generated in response to speech recognition under various situations is substantially more complex than speech generated in response to the predetermined prompts. In the field of language generation, language models trained on large databases, such as OpenA1 GPT-2 and GPT-3 have produced near human quality output. In other fields such as AI board games, tree search-based playing of board games has resulted in systems such as AlphaZero developing high performance in a mostly self-taught manner through repeated self-play and logging of self-play games. Logging of self-play games creates self-play logs which are later used for tree search queries and predicting expected outcomes of various game moves in selecting the moves having the highest probability of game success. The prior art has not provided a highly successful virtual agent for language interactions which utilizes self-play learning to generate conversation logs from tree search processes in determining language utterances. 
     SUMMARY OF THE INVENTION 
     A novel method for AI language self-improvement agent using language modeling and tree search techniques is disclosed for a virtual agent exchanging textual discussion with users and other simulated virtual agents. The method includes the steps of receiving a current situational description, wherein the current situational description includes natural language user input, properties regarding the qualities of the virtual agent, and indicia regarding subject matter context of a present conversation. The qualities of the virtual agent include temperament and textual tendencies. The indicia regarding subject matter context include textual logs from recent conversational exchanges. The current situational description includes audio, visual, and tactile inputs collected proximate to the virtual agent. The method utilizes a database of one or more language models, conversation logs storing text from prior textual exchanges, and reference conversations utilized for training according to the one or more language models. The method is comprised of steps for executing instructions for a combination of self-play engines for training of the language model with self-play and external interaction engines for communicating with one or more external users or external virtual agents. The method further includes instructional sets for self-moving modules for advancing the method of external agents/users communicating with the virtual agent via a combination of textual exchanges and one or more audio, visual or tactile inputs into the virtual agent. The method preferably utilizes tree search processes, such as Monte Carlo Tree Search (“MCTS”) processes, in combination with the one or more language models to provide the tree search techniques outputting textual responses to said current situation description, and wherein said virtual agent responds with textual expression to verbal input in combination with the audio, visual, tactile, and other sensory inputs. 
     A method is disclosed for embedding language models such as GPT-2 or GPT-3 within a tree search framework, allowing the benefits of both methods to be realized, and to provide additional benefits from their mutual interaction. The agent can select its utterance or action based on the projected expected outcome. The language model provides both “move generation” and “evaluation” functions for the search process. The search process simulates multiple viewpoints conducting a virtual conversation based on the language models used. The interaction between viewpoints is a deliberation process and is inspectable, allowing explanation of outcome. Self-play/Self-talk allows the system to generate self-play logs which are used to train future versions of the language model. Self-play logs are used to train the language models and “compile” overall system performance into the language model, improving both the move generation and evaluation process. Language models can generate many plausible responses, but can lack a way of selecting the “best” response versus the “most probable” response. The tree search process selects the “best” response leading to the highest average expected outcome based on sample-based projections of the future. Goal directed self-filtering is also provided in selecting appropriate choices. 
    
    
     
       DESCRIPTION OF THE DRAWINGS 
       For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following description taken in conjunction with the accompanying Drawings in which  FIGS.  1  through  17    show various aspects for a method for AI language self-improvement agent using language modeling and tree search techniques according to the present disclosure, as set forth below: 
         FIG.  1    is a flow chart depicting the method for AI language self-improvement agent using language modeling and tree search techniques according to the present disclosure; 
         FIG.  2    is a block diagram depicting the overall architecture of a system implementing the AI language methods according to the present disclosure; 
         FIG.  3    is a flow chart depicting a process for generating a contextual description; 
         FIG.  4    is a flow chart depicting an abstracted tree search process utilizing contextual descriptions; 
         FIG.  5    is a schematic diagram depicting different layers of a Monte Carlo Tree Search Process; 
         FIG.  6    is a flow chart depicting a move generation process using language models; 
         FIG.  7    is a flow chart depicting an evaluation process using language models; 
         FIG.  8    is a flow chart depicting steps for evaluation generation; 
         FIG.  9    is a flow chart depicting evaluation utilizing a basic sentiment analysis; 
         FIG.  10    is a flow chart depicting evaluation using goal oriented analysis; 
         FIG.  11    is a flow chart which depicts merging multiple analyses into a weighted evaluation; 
         FIG.  12    is a schematic diagram depicting an apparatus for self-learning through application of a self-play feedback loop; 
         FIG.  13    is a schematic diagram depicting an apparatus for interlocking training and self-play processes; 
         FIG.  14    is a schematic diagram depicting a design for an agent for generating linguistic responses to verbal and situational inputs; 
         FIG.  15    is a flow chart depicting a training process required for a broad coverage agent; 
         FIG.  16    is a schematic diagram for providing an informational funnel to construct Immediate Situational Descriptions; and 
         FIG.  17    is a block diagram for generating and selecting content using entropy density and a fractional knapsack model. 
     
    
    
     DESCRIPTION OF THE INVENTION 
       FIG.  1    is a flow chart depicting a method for an AI language self-improvement virtual agent using language modeling and tree search techniques. Two interlocking processes are shown that together implement a method for generating natural language output and initiating actions through a deliberative process and a method of improved operation through both supervised and unsupervised learning. The deliberative interaction process is started in Step  12  and receives situational input from either internal or external sources in Step  001 . Such description may include user input expressed in natural language optionally combined with sensory or situational input expressed also in natural language. In Step  002 , the situational input is merged with background information to create a contextual description. The goal of the contextual description is to provide a summary of all relevant information relevant to a deliberation process other than the immediate situational input. In Step  003 , a deliberative search process uses the contextual description to produce a range of possible actions and to assign values to each possible action. This search process uses language models  008  to both produce plausible continuations and to provide evaluative information. The output of this process is a list of possible actions along with their score or value. The result of the search process  003  will produce a data structure that encodes the expected values of each possible action under consideration. In Step  004 , the list of possible actions and their evaluations are extracted from the search data structure. In Step  005 , the optimal action is extracted from the list of actions and their evaluations. Usually, this selects either the maximum or minimum action based on the evaluation used; however, other criteria may be used and the value of each action may be a multi-dimensional vector instead of a unitary value, in which case a weighted selection process may be employed. In some cases, the action selected may not be optimal from a numeric view but may be selected to meet some other criteria such as variety or behavioral loop prevention. In Step  007 , the action selected in Step  005  is implemented through interpretation as either a user interaction, animation action or as a system internal action. The output of Step  007  becomes part of the history of an interactions log that is used to make up the immediate situational input of Step  001 . 
     In Step  006 , the situational input and optionally contextual description is recorded along with the selected output of Step  005  into an interaction log  009 . The interaction log is used by the unsupervised learning process system in Step  011 . Once initiated in Step  14 , the language model training process  011  generates the language models  008  from reference material  010  used for supervised training and interaction logs  009  for unsupervised learning. Reference material  010  may be provided by manually selected material, by curated material, or by automated collection methods, such as topic focused collection, quality focused web collection, and text mining. During the search process in Step  003 , numerous simulated interactions may be generated, and these simulated interactions may form additional training material for unsupervised learning of both generative and evaluative language models or classifiers used in the system. 
       FIG.  2    is a block diagram depicting the overall architecture of a system implementing the AI language methods according to the present disclosure, and represents additional details for the process of both deliberative search and learning represented in  FIG.  1   . An object  100  represents the human or universe interacting through the user interface  101 . The external user interface  101  is the primary demarcation of the system and the outside world. The external user interface  101  collects any relevant information such as the user&#39;s  100  utterances, sense impressions from sensors  103  or parameters useful to control the search process or to provide context. The combination of processes  100  and  101  correspond to Step  001  in  FIG.  1   . The user interface  101  provides a packet of information to the system in the form of a contextual description packet  102 . This packet  102  includes information for the search settings, background information from sensors  103  to provide a description of the “scene” being imagined, the conversational history of the dialog or actions between the system and the human user  100 , and conversational prompts given to the language model. A portion of packet  102  provides the search setting used by the MCTS processor  106 . The other portion of packet  102  provides the conversational context and scene description which are passed to the contractual prompt generator  104  which generates the initial contextual prompt given to the MCTS processor  106  and is applied at the initial node or root of the MCTS processor  106 . This is required to provide a description that fits within the processing capacity of any language model being used. The combination of processes  102  and  104  correspond to Step  002  in  FIG.  1   . 
     The search process  106  uses the information provided by the root node generation process  104  and search settings from packet  102  to conduct a search for an action with the highest expected future reward from the set of possible initial actions  107 , using best response extraction process  120 . The search process  106  in the initial embodiment uses Monte Carlo Tree Search or MCTS. MCTS requires that the state description encapsulated by each search node provide four functions: “getPossibleAction( )” returning a list of actions (conversational or otherwise) that can be taken from that state, “takeAction(action)” which returns the new state from taking that action; “isTerminal Q” which reports if a state is a terminal or leaf state; and “getRewards( )” which returns the evaluation for that state (if it is terminal). 
     The “isTerminal( )” expression in a report is true if the node is a leaf in the tree and requires evaluation, and “getRewards( )” which is given if the node returns an evaluation value (the expected reward) for the state if the state is terminal. While depth of node is used in the disclosure for illustrative clarity, other criteria may be used to determine the true value of “isTerminal( )”, such as detecting a projected end of conversation, session or communication. Given the four functions defined for a given domain, the MCTS algorithm will return the best initial action by simulating a “game” of carrying out actions and examining the rewards of the eventual outcomes. This process is currently the most successful method used by AI&#39;s that play games with complete information like Chess and Go and incomplete information like bridge, poker and Starcraft. MCTS automatically balances its search process between exploration of new move possibilities with exploitation of known successful paths. As a search method the family of MCTS algorithms are actively being researched and developed. 
     One insight of the current invention is that three of the four functions can make use of recent advances in broad coverage language models  110  to provide move generation  108  from contextual descriptions of an ongoing conversation or interaction and also to provide part of the necessary evaluation function required by the “getRewards” function of MCTS  106 . In particular, by prompting the language model with the initial start (or prompt) of an evaluation phrase such as “I feel . . . ”, “I believe . . . ,” or any phrase that would normally lead to the statement of an ego-centric opinion on the state of the situation at that point in the dialog, an evaluative statement will be generated. 
     Another insight is that this linguistic/symbolic evaluative statement generated by the language model can be converted into a numeric value by application of a sentiment analysis (or other linguistic classification) function, which returns a numeric positive or negative value for a given statement. MCTS uses these evaluations of the leaves of the search tree to generate an expected average value for each possible initial action. Another feature of MCTS is that it can function as an “anytime” algorithm, which means the longer it runs, the better the estimated values, but at any time (e.g., due to time constraints) one can stop the process and receive plausible estimates for the best initial action. Process  120  extracts the highest ranked response from the MCTS search, along with other trace or log information. Process  120  corresponds to Step  004 . This information is sent to the system response trace module  122  which will send the selected response to either the user or the self-play module  124 , and to the conversational logs  116 , for self-play-based learning. 
     Language model  110  corresponds to Language model  008  shown in  FIG.  1   . The MCTS processor  106  fills the role of Step  003  shown in  FIG.  1   . Optionally, a System Intent Processor (SIP)  130  may be included, to translate and interpret the utterances and control statements generated by the system into computational, retrieval or control actions. SIP processing may occur on either or both sides of the external user interface  101 . The system intent processor is like giving the system its own Siri™ or Alexa™ type device. The SIP  130  turns the English output of the system (which may be a goal or direct command) into an action. The SIP  130  is a separate module that listens to the overall system output and executes requests it recognizes. Multiple methods exist for implementing such intent processors. The user interface  101  and the System Intent Processor  130  correspond to the Step  007  shown in  FIG.  1   . The language model or models  110  used by  108  and  106  may be either statically fixed or continuously trained by a Language Model Training Processor (LMTP)  112 . LMPT  112  can either accept training material from a corpus of reference conversations or examples of language usage  114 , or from the conversational logs  116 . The conversational logs  116  record the best system response given each input from the human  100 , the self-play module  124  or other dynamic sources  118  such as internet search and extraction. The Language Model Training Processor  112  corresponds to the Step  011  which is shown in  FIG.  1   . Storage  116  corresponds to Step  009  and storage  114  corresponds to Step  010 . Information from the search analysis process in Step  120  can be used to create records to seed the self-play module  124  with start points stored in a start point data base/knowledge base (DB/KB)  126  or other stores for future exploratory conversations. The self-play module provides all the information required for the context packet  102  to continue exploration of possible continuations of conversations. An interface to the start point KB/DB  126  can be provided to insert new exportation points from external sources such as human users. 
     The use of LMTP  112  from source referencing conversations stored in data files  114  and conversational logs stored in data files  114  improve the operation of the language model  110  as both a move generator and evaluation generation model. In some uses of language model  110 , the search process of  106  may be too expensive in terms of time. The LMTP process in fact causes the language model to lossily summarize, compress and compile the information derived from the tree search. As such, the trained language model  110  can be used for non-search applications on remote servers  128 , where simple input/output operation of an enhanced language model is desired. Non-search applications for remote servers  128  may be realized through transfer learning, by training a simpler language model on the system output. The primary function for the system as a whole is analogous to the operation of the self-teaching game system AlphaZero/MuZero, except that instead of operating in a zero sum game space like Chess or Go, the space the described system operates within is the space of dialog, conversation and interaction (both virtual and embodied). 
       FIG.  3    is a flow chart depicting a process for generating a contextual description. Input information is accepted which describes the current situation and global context from various sources, in natural language form, background information, and a log of recent history, which may be empty when the process begins. Most language modeling processes developed to date either return an estimated probability for tokens by utilizing a flat probability or one which in some way is conditional upon a sequence of tokens over a window of some maximum depth. The goal of the contextual description generation process is to ensure tha tthe information most relevant to language model generation process is selected and fits within the processing window of the language model. The context generation process must rank all available information to ensure the most salient information to the current situation (and any problem posed) is presented in a package to the deliberation process and that it fits within any processing constraints of other modules. 
     The process begins with Step  200 . In step  202  a summary is created of the most relevant information from recent history of the interaction stream. The summary captures the “gist” of the current situation. By way of a non-limiting example, in some implementations the Textrank text processing method maybe used to provide summarization of the collection of recent text being summarized. Other automated methods are known where a language model may be used to produce summarizations of text. Given that current State of the Art language models using the transformer neural model utilize an internal model of attention, it is useful for an attention-based summarization system to be employed. Textrank implements a simulation of where attention would be focused over a graph of nodes representing a corpus of text. Also, just as Pagerank has topic focused variants, Textrank can be modified to provide topic focused summarization. The primary benefit of using Textrank is the ability to provide extractive summarization over arbitrarily large historical logs. 
     The process then proceeds from Step  202  to Step  204  and begins to determine key word queries from the then current summary of the interaction stream determined in Step  202 . The process proceeds from Step  204  to Steps  206 - 210 . In Step  206  the current interaction stream is queried for relevant content to the queries. In Step  208  the history of a respective agent developing the conversation is queried for relevant content. Similarly, in Step  210  the background information database is queried for content relevant to the keywords determined in Step  204 . The process then proceeds from Steps  206 ,  208  and  210  in parallel to Step  212  in which the results of the respective queries are merged. In Step  212  the query results are combined, ranked and sorted. By way of a non-limiting example, in some implementations TD-IDF based text retrieval methods may be used to query each background data source. 
     Then in Step  214  the results from the summary of the information stream from Step  202  is merged with the summary from Step  212  to provide current situational input from multiple relevant information sources. It is via this merge process in Steps  212  and  214  that information most directly relevant and associated with the current input from the recent conversations is made available to the context description. The merged output of Step  214  provides a final contextual description that fits the constraints of downstream processing elements. One such typical constraint is that the total length of the contextual description must be less than some maximum, usually determined by the processing capacity of language modeling technology or method. For example, current implementations of GPT-2 and GPT-3 have processing windows of generally less than 2048 tokens. The final merging process would select the highest-ranking set of collected information that fits within the 2048 tokens. A simple greedy sort and merge process is employed, though other methods such as evolutionary or other search methods may also be utilized, and is detailed later in  FIG.  17   . The task of delivering the highest value product in a fixed sized carrier maps to the mathematical area known as packing problems in the field of combinatorial optimization. In particular we wish to maximize the relevant information presented to our language model for analysis and use the work done on the fractional knapsack problem; since while in the general case the optimization problem is NP-complete, the fractional variant admits a good polynomial time greedy approximations. Also, dynamic programming and genetic programming methods exist which may be of use for larger scale or different variants (possibly multi-modal problems), and may be relevant when the option set is continuously or asynchronously updated and an “anytime” update capability is desired. 
       FIG.  4    is a flow chart depicting an abstracted tree search process (of which MCTS is a variant) which utilizes the contextual descriptions in a deliberative search process to render and select a next action. or utterance for speech, based on the projected expected outcomes as determined by the search process. The text generation search process is provided by simulating an “internal dialog,” through a self-talk virtual imagination process. The process begins with Step  300 . In Step  302  the contextual description of Step  214  of  FIG.  3    and the root node of the search process are added to the process queue, along with a set of parameters for the search configuration. The search configuration will include a selection of one more language models on which the self-talk virtual conversation occurs. The search configuration would include everything necessary to define the initial search condition, the parameters of the search process, and the evaluation criteria and termination of search criteria. While defaults may be used, custom parameters may be specified for each and include information to define the initial node, any search constraints (the maximum resources to use in terms of time, memory, nodes to be processed, evaluation method to be used, expansion rate at each level, etc.), models used other than the defaults for generation and evaluation and information that might influence either (such as custom prompts), and response generation parameters (length of response generated, sampling parameters such as temperature, cutoff probability, etc.). The contextual description may include information regarding the selected personality and motivation of the virtual agent being simulated, as well as selected parameters and perceived parameters regarding the personality and motivation of the other various participants to the conversation exchange. For example, the virtual agent may be defined as being helpful, cheery and talkative. Such adjectives will influence the language model generation profile, which in turn influences the sentiment of text associated with the given character. Similarly, the projected and perceived traits of personality and motivation of the other various participants will also affect the simulated paths of the self-talk imagination process rendered by the search process. These assigned traits of the virtual agent and those of the participants may also be included in the search configuration. The initial parameters from Step  302  are input into Step  303  and the process queue is executed. The results of the execute process queue of Step  303  are then input into Step  304 . Step  304  determines whether the termination criteria has been met; and if so, the process proceeds to Step  318  in which an options list is extracted from the current search results and in Step  320  the simulation will end. 
     If in Step  304  a determination is made whether the search criteria has been reached. The search termination criteria will that require at least one evaluation to have been performed and that some specified resource has been exhausted. Typically the exhausted resource may be real wall clock time expended, a number of node expansions, a lack of diversity in options (indicating total search space exploration), or convergence of the values assigned to the top level nodes. MCTS has the properties of being able to incorporate any of the above criteria into its termination condition. If a determination is made in Step  304  that the search criteria has not been reached, the process proceeds to Step  306 , and the next node is selected for adding to the process queue. Next the process proceeds to Step  308 , and a determination is made of whether the node requires evaluation. If a determination is made in Step  308 , that the evaluation is not required for the selected node, then the process proceeds to Step  310  and a move generator is implemented to create one or more successor nodes. Then in Step  312  successor nodes are added to the process queue and the process proceeds to Step  303  to process the nodes in the process queue, and then after Step  303  the process returns to the search termination criteria evaluation in Step  304 . If instead in Step  308  a determination is made that the node selected in Step  306  requires further evaluation, the process proceeds to Step  314  and a “generate evaluation method” is applied to the node. The process then proceeds to Step  316  and the values of the “generate evaluation method” are applied to the ancestor nodes of the node selected in Step  306 . The process then returns to the process Step  303  and continues. 
     The search process uses a move generation method  310  to propose new actions that are then used to create new contextual descriptions by appending the proposed actions to the existing contextual description, changing the prompted actor variable as required. This describes a state space search, where the state is defined by an actual series of events and utterances and the simulated set of events and utterances are used to reach a certain point in time. The simulated events or utterances are generated by the language models predicting the logical continuation of the sequence used to reach a given state. 
     Each node in the state space search consists of a context description that contains the sequence used to reach the state represented by that node. Each node also contains ancestor node information where the ultimate ancestor node is the root node of the search tree and the root node defines the initial input to the search process. Each node contains information on the action that was taken to transition from the ancestor to the current node. This is the output of the language model that is appended to the ancestor node contents to generate the current node. Each node contains an evaluation value, indicating either the final evaluation of a leaf node in the search process or the estimated reward value of the descendent nodes. Each node contains a value signifying the distance which that node is located from the root node, along with visitation frequency information. This information allows depth constraints to be placed on the search process and the expected reward to be computed. 
     The move generation Step  310  is implemented and expands upon a node&#39;s context description and generates a new node with a new context description by using the node generation process and appending the output generated by the language model, when the distance of the expanded node from the root is less than some threshold or when some other node expansion criteria is met. Changing the prompt used to generate a node expansion may be fixed (implementing say verbal taking turns) or left at the discretion of the language model. 
     The search process may be implemented with the described node data structure and a queue to hold lists of nodes to be processed. The simulation Steps continue until some termination criteria is met in Step  304 , such as expiration of time or exhausting some resource. If the termination condition does not hold then a node is selected from the processing queue for expansion Step  306 . The content of the node is examined, and based on depth (or other criteria), a determination of if the node qualifies as a leaf node and requires evaluation or is an interior node and requires expansion. If the node requires expansion, then the afore described node generator step Step  310  is applied to generate one or more new nodes, each with parent/ancestor being the current node that was being examined. Each of the new nodes is inserted into the process queue  312  and control is returned to Step  304 . If, however, Step  308  determines that the node is a leaf and requires evaluation, then a separate “evaluation prompt” is used in Step  314 . The evaluative prompt is a prompt to the language model to summarize the situation described by the contextual description of a node in a way that is easy to evaluate using either sentiment analysis or other language classification methods. Once evaluations are made in Step  314  and Step  316 , values are propagated back through each of the linked ancestor nodes to update each ancestor node value. 
     Once the search termination criteria is reached, the search process returns in Step  318  an option list consisting of the language model derived actions that lead to the immediate descendant nodes of the root node, along with each of their expected long-term values as estimated by the simulation process of each action. Ultimately the agent will use the option list generated to select the next action either deterministically or probabilistically. By way of a non-limiting example, the afore mentioned search process in some implementations may use Monte Carlo Tree Search to implement the optimal action search process in  FIG.  4   . 
     With regard to Step  306 , it is known that various criteria used to select the next node to process produces various search behaviors (depth-first search, breath-first search, best-first search, A* search, MCTS search). The data structure of the node is modified to contain such data as to make the desired search behavior possible, notably (but not necessarily limited to) the nodes distance from the root, estimates of the average value of child nodes, and estimates of the value for leaf nodes. Optionally, any heuristic value of distance from some goal state may be included; however, the estimate of average descendant value may be used as a proxy. 
     With regard to Step  316 , different propagation behavior results in the emergent property of different overt behaviors. In typical planning for two interacting agents, each agent may choose to minimize or maximize its expected return. This determines the style of conversational game being played and behavior observed. The following “TABLE I” lists by way of example, Evaluation Propagation Policies and a corresponding Behavioral Descriptions: 
     
       
         
           
               
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Evaluation Propagation Policy 
                 Behavioral Description 
               
               
                   
                   
               
             
            
               
                   
                 Maximizing the sentiment of all actors 
                 Win-Win Optimist 
               
               
                   
                 Maximizing the sentiment of the user 
                 Comedic/Entertaining/ 
               
               
                   
                 (while ignoring itself) 
                 Subservient 
               
               
                   
                 Maximizing the sentiment of system 
                 Narcissistic/Self-centered 
               
               
                   
                 outputs (while ignoring the user) 
                   
               
               
                   
                 Maximizing system sentiment and 
                 Sadist 
               
               
                   
                 minimizing user sentiment 
                   
               
               
                   
                 Maximizing user sentiment and 
                 Masochist 
               
               
                   
                 minimizing system sentiment 
               
               
                   
                   
               
            
           
         
       
     
     The evaluative prompt used in Step  314  need not be limited to just the one actor prompt but can be prefixed with material to influence the evaluation given. This ranges from suggestions to select from a range of evaluation options (“How was the experience: Good, Neutral, Bad? Daxine:′ I believe the experience was [EOP]”), to prompts to generate a more open ended scene description (“As the scene closed [EOP]”). 
       FIG.  5    is a schematic diagram depicting different layers of an interchange MCTS processor  338 . The MCTS processor  338  conducts a search based on the description of the individual state, the move generator and the evaluation function. The process of generating the initial description used in the root is performed by module  340 . The MCTS processor  338  generates multiple levels N,  1  through Level  0  of the search tree to determine the best response to input. For illustration it is assumed that the MCTS processor  338  is instructed to generate searches of depth N from the initial root node. A typical MCTS may be used without a fixed search horizon. The MCTS processor  338  generates the first layer of Level N−1, and the best response extractor process  342  returns the highest-ranking node, or some selection based on the relative ranking of the nodes in level N−1. As in the normal MCTS process, a number of nodes are generated for one or more additional levels labeled as levels  344  using the language model to create the search tree out to some search horizon, which has the terminal level  348  (“Level  0 ”). At the pre-terminal level  346  (“Level  1 ”), the evaluation prompt is used for the nodes of  346  to generate the evaluation terminal nodes of  348 . The generated nodes of level  348  (“Level  0 ”) thus contain the text or other information which is converted to a numeric value through a symbolic to numeric conversion process. In the illustration that conversion is done using a sentiment analysis process. For instance, assuming the system is simulating a character named Bob, the evaluation prompt might be:
         Bob: “I feel[EOP]”
 
where “[EOP]” represents the end-of-prompt and is where the language model would insert its continuation.
       

     The Language Model (LM) is prompted to complete the evaluation sentence, based on the total context provided for that node. The text values are then converted to a positive or negative numeric value by the sentiment analysis process, (or any other leaf evaluation process) and the value is propagated back up the tree to update the level N−1 node values. 
       FIG.  6    is a flow chart depicting a move generation process using language models and describes a method of querying one or more language models or knowledge sources, such as using a search tree process, such as with an MCTS processor, to provide the equivalent of “move generation” or node expansion required by the search process. The move generation process begins in Step  400 . The language model or knowledge source is presented with a contextual description and is prompted to generate a continuation as output. In Step  402  a prompt is presented which identifies the agent by name or role, (i.e. “John: ‘”, or “Doctor: ’”, etc.) and is in a format matching the actor identified responses in the language model training data  404 . In Step  406  the language generation prompt is preformed and formatted and input to Step  408 . In Step  408  the output may optionally be truncated if a change in actor is detected in the generated output, such that the output of the entire process contains only one valid conversational or interaction “move”. 
     Optionally, the response may be generated by rule-based, retrieval-based or other sequence-based generation methods (e.g. chatbot technology, question-answer engine, etc.). The operation of language models can be substituted with rule-based, retrieval based and language model-based continuation or response generation methods. The initial set of options at the root can also be generated by other means, including but not limited to rule-based, retrieval-based or language model based. Also, a fixed set of options may be included or appended to the existing list, such as “unknown” or recognized sets of standard operations (e.g. via user intent detection methods). 
       FIG.  7    is a flow chart depicting an evaluation process using language models and outlines the Steps required to query a language model or knowledge source for a situational evaluation as required in Step  314  of  FIG.  4   .  FIG.  7    describes a method of querying one or more language models or knowledge sources to provide the equivalent of an “evaluation” function. The situational evaluation process begins in Step  500  and then proceeds to Step  502 . In Step  502  the language model is presented with a contextual description and is then prompted in such a way that the language model will generate an evaluative output to Step  504 . The prompt identifies the evaluative agent by name or role in Step  502  and is in a format matching actor identified responses in the content the language model has been trained upon. In Step  504  the name of virtual agent for evaluation is included. In Step  506  the prompt is formatted to match the identified responses of the simulated actor or agent in the language model used for training. In Steps  508  initiation of an evaluative statement or language use is included. In Step  510  returned text is analyzed to generate one or more values representing evaluation of the contextual description. An example might be “John: ‘I feel [EOP]”, where “[EOP]” represents the end-of-prompt. In such a case the language model would generate a continuation such as “satisfied with the outcome” or “sad about what happened”. 
     The output of such a generation Step is linguistic or abstract in nature and must be converted into a comparative value. The text returned is analyzed to generate one of more numeric values representing the relative evaluation of either the final evaluative statement or the entire contextual description thus generated. The evaluation process in the initial implementation utilizes sentiment analysis applied to the evaluative statement. Subsequent versions utilize sentiment analysis to train a backoff language classifier since, during processing, a large volume of content is generated and processed. However, the rule-based sentiment analysis system may not return a score in all cases. Examples of text that generate high sentiments scores with high confidence are used to train in an unsupervised way a backoff language classifier. The backoff classifier is used to provide low value estimates when the rule-based system can provide none. However, the language model-based classifier may be used as a generic programmable substitute for the evaluation process and may be trained on both the output of sentiment analysis or statement certainty and modality. 
       FIG.  8    is a flow chart depicting steps for evaluating the relative evaluation of the contextual description and expands on Step  510  in  FIG.  7   . The analysis begins in Step  600  and then proceeds to Step  602 . In Step  602  the text is analyzed using basic sentiment analysis and then proceeds to Step  604 . In Step  604  the text is analyzed using goal oriented analysis and then the process proceeds to Step  606 . In Step  608  sentiment analysis of Step  602  and the goal oriented analysis of Step  604  are merged together into a weighted evaluation. 
       FIG.  9    is a flow chart depicting evaluation utilizing a basic sentiment analysis which expands upon on Step  62  of  FIG.  8   . The process begins with Step  700  to perform a simple rule based sentiment analysis upon a segment of text to indicate the total polarity of the text ranging from −1 to +1. The text is input to Step  702  which then tokenizes the text into a list of words and recognized phrases, creating a list of tokens. The lexicon contains a valence value (−1 to +1) for each word in the recognized vocabulary. In Step  704  the valence value of each token is looked up in a valence lexicon or a valence table. The valence values are then input to Step  706  in which the overall sum of the valences is computed as the sum of the valence of each token in the sentence. The process then proceeds to Step  708  and a normalized score is computed for the text being analyzed using the following equation:
 
NORMALIZED_SCORE=SUM S /sqrt(SUM S *SUM S )+ALPHA
 
where ALPHA=15 and is the approximate max value expected. In Step  710 , the NORMALIZED_SCORE is clipped, so as to remain in the range (−1, +1). In  712  the NORMALIZED_SCORE is returned. The results of the Steps of  700 - 710  result in the general positivity and negativity being returned for a given statement expressed in text, relative to the values placed in the valence lexicon. By way of a non-limiting example, in some implementations a rule-based analysis like a VADER analysis, or another sentiment analysis method may be utilized.
 
       FIG.  10    is a flow chart depicting evaluation utilizing a goal oriented analysis and expands on Step  604  of  FIG.  8   . The analysis details various methods to analyze the returned text to generate one or more-values representing relative evaluation scores of the contextual description based on a basic goal-oriented analysis. In such an analysis the purpose is to return a value that indicates relative distance from some goal state (factuality, agreement, statement of ground truth, etc.). Various analysis methods may be employed individually and independently or in conjunction and in parallel. The process begins in Step  800  and then proceeds to Step  802 . In step  802  the process receives a textual description to be evaluated and is passed to one or more subprocesses that perform text comparison. The process will then proceed in three parallel paths to Step  804 , Step  810  and Step  814 , respectively. In a first parallel path beginning with Step  804  the text is converted into a vector representation which is passed in parallel to Step  806  and Step  808 . In Step  806  the distance between that vector and a relatively small set of reference vectors, and the nearest distance is returned. Here, vector refers to vectors encoding semantic information and numerous methods are known to generate them (word2vec, sent2vec, doc2vec, GLoVE, word vector embeddings used by various language models, random projections, etc.) A small reference set may be derived from a small set of initial target statements input at the start of the processing. The output of Step  806  is output to Step  818 . In Step  808  the vector is used as a query to a larger vector database, which may represent longer-term goals or evaluations, and then output to Step  818 . By way of a non-limiting example, in some implementations Approximate Nearest Neighbor search methods may be used in determining the most relevant vector-based match from a database or reference set. The second parallel path begins from Step  802  and moves to Step  810 , and in Step  810  text based matches are found in a goal reference database. The matches found in Step  810  are input to Step  812  in which the matches are selected or merged, and then output to Step  818 . Text-based queries may be applied to a database of reference sets of the form (text→value) or (vector→value). The output of the database query is ranked and merged into an output set. By way of a non-limiting example, in some implementations a language model may be trained to receive a goal statement and a textual description to be tested and that evaluative model would return an evaluative response for the value of the text test relative to the goal text with an interpretation process similar to that for sentiment evaluation employed. (i.e. v=sentiment (eval_model (goal statement, input))). 
     In the third parallel path moving from Step  802  to Step  814 . In Step  814  a goal evaluation trained language model is used to find text based matches which are input into Step  816 . In Step  816  the matches from Step  814  are converted using sentiment analysis methods. In Step  814 , a traditional text classification system is employed where such a system utilized simple features, such as character and word n-grams and simple linguistic features. Text classification methods based on naïve bayes, perceptron, support vector machines, k-nearest neighbor, TF-IDF and others may be employed. In Step  818  the output of the various analysis methods are merged into a final weighted evaluation score and returned in Step  820 . 
       FIG.  11    is a flow chart which depicts merging multiple analyses into a weighted evaluation and expands on Step  818  of  FIG.  10    by detailing a simple method for converting multiple candidate results from multiple sources into a single weighted output value base on the similarity or distance metric provided by each. The process begins with Step  900  and the proceeds to Step  902  in which the list of matches with values and metrics are input. The metrics used are preferably either distance or similarity based. In Step  904  a determination is made of whether the metric is distance based or similarity based. If in Step  904  it is determined that the matched condition is distance based, the process proceeds from Step  904  to Step  906 . In Step  906  the distance based metrics are converted into similarity based values in Step  906  and Step  908 . In Step  906  the maximum distance for a candidate match is determined and input into Step  908 . In Step  908  for every candidate a similarity value is determined. The two determinations for Steps  906  and  908  are shown in the equations below: 
                                                For Step 906:   maxDistance=max    i    distance[i]              For Step 908:   similarity[i]=maxDistance-distance[i]                        
The similarity values of Step  904  and the similarity values determined in Step  906  and Step  908  are input into Step  910 , and an average similarity value is determined. In Step  912  a weighted similarity value is determined for each match, and then in Step  914  a combined weighted estimated similarity value is computed.
 
     Given K value estimates in value[ ] and the positive value array similarity [ ] the following are computations performed in Steps  910 ,  912  and  914 : 
                     For   ⁢         Step   ⁢                ⁢   910   :         SimSum     =       ∑     i   =   0     K           similarity   [   i   ]                     For   ⁢         Step   ⁢         912   :           weightedSimilarity   [   i   ]       =       similarity   [   i   ]     /   SimSum                   For   ⁢         Step   ⁢                ⁢   914   :        estimatedValue     =         ∑     i   =   0     k             weightedSimilarity   [   i   ]     ⋆     value   [   i   ]         K                 
In Step  916  the combined, or merged, weighted similarity value is returned to Step  8 l 8  of  FIG.  10   .
 
       FIG.  12    is a schematic diagram depicting an apparatus for self-learning through application of a self-play feedback loop. The “Replay Buffer”  900  is the memory of conversation logs  902  (corresponding to conversation logs  116   FIG.  2   ) and special training logs provided by reference conversations  904  (corresponding to conversation logs  114  in  FIG.  2   ). The replay buffer  900  preferably includes both the human sourced corpora and the self-play logs. The “Shared Storage”  908  is the set of generated models  910  (corresponding to the language model  110  of  FIG.  2   ). It contains any fine-tuned language model networks trained on the sum total of the Replay Buffer  900 . One or more Self-Play engines  912  (corresponding to self-play engine  124  in  FIG.  2   ), takes the latest language model image  910  from “Shared Storage”  908  and generates new conversation logs  902 . It may do this using a special “interesting prompt list” provided by the start point data  126  of  FIG.  2   , where different prompts are used, or it can use unconditional prompting. The output of each self-play engine run goes to its own section in the Replay Buffer  900 . 
     The Trainer process  906  (corresponding to the language model training process  112  in  FIG.  2   ) does a scan of the text in the Replay Buffer to create a training corpus, trains the language model training process  112  of  FIG.  2    (Transformer-based, probabilistic, RNN or otherwise), and generates new language models  910  which are model images kept in Shared Storage  908 . In addition to the internal self-play engines  912  additional External Interaction Engines  914  may be included which encapsulate systems that use the language models  910  to interact with the external world, and generate additional conversational logs  902 . There may be one or more self-pay engines  912  and External Interaction Engines  914  existing and running in parallel in a given system. 
       FIG.  13    is a schematic diagram depicting an apparatus for interlocking training and self-play processes. A trainer process loop  1000  loads its initial parameters on startup  1010  and generates a reference corpus from the relevant Replay buffer set  1012 , then trains the language model for N Steps  1014 , writes the resulting updated language model out  1016  as a new reference model in the shared image file  1006 . A determination  1018  is made as to whether a new corpus for training is generated  1012  or the existing corpus is used to continue to update the existing model  1014 . The training process  1014  which is stated as being for N steps, can be any of the standard criteria such as N-steps, T amount of wall clock time, reduction in measure error past a threshold, etc. A number of restart criteria  1018  can be specified. One criteria could be based on a fixed number of iterations. Another criteria would be on the amount of new content added to the Replay Buffer  1004 . It may also restart the process after every T-time units. Also Step  1014  may terminate early based on time or change in the replay buffer contents. 
     The Self-play engines use a similar processing loop  1002 . First, they load their initial parameters  1020  and then load the latest shared image  1022  provided by the Training Process  1000 . Each Self-play engine simulates a number of interactions  1024 , recording each as a trace file stored in the Replay Buffer  1026 , 1004 . Each replay engine then determines if the model it is using is “stale” relative to available models  1028  and, if so, loads the new language model  1022 ; otherwise, it continues to generate new examples using the existing model  1024 . By having the Trainer and Self-Play engines implemented as independent processes provides a number of benefits. The interoperation of the two roles are “near embarrassingly parallel”, since other than the startup either role can continue to generate useful work without requiring blocking synchronization from the other. They can provide the option of running continuously and asynchronously. They can operate on a single system or run on multiple independent networked processors or computers either centrally located or widely distributed. Such an arrangement provides the benefits of natural flexibility, scalability and redundancy. 
     Fortunately, the self-play process requires less processing power than training to generate content and its task can be performed by an individual processor much more modest than Trainer. The Trainer on the other hand benefits from being a central process with maximal processing power or efficiency (a GPU/TPU system). The pool of self-play engines can be implemented locally on one system or on a cluster of multiple computers of different processing power. A cluster of self-play engines may be either tightly coupled or loosely coupled and widely distributed. 
     Ideally, it is desirable to have a simple, easy to configure system where one can simply add self-play engines to a virtual network and they start producing input to the Replay Buffer  1004 . This can also be implemented as a Grid computing model, where during initialization  1020  and model testing  1028  each remote self-play engine would retrieve a URL for the current best available language model. It starts producing output, compresses and uploads the result to an Replay Buffer implemented through an internet cloud based repository. CloudTurbine provides an example of implementation of a distributed system using a cloud-based file-sharing communication model, (such as Dropbox or Amazon S3). Dedicated network file-storage infrastructure of course may also used. 
     Another modification is to have individual Trainer processes sub-sample the entire Replay Buffer, so the training set it uses is representative but does not require the use of the whole buffer. This can allow faster cycling of the training loop  1000  since the corpus construction phase can be substantial as time passes and the Replay Buffer  1004  increases in size. One can also have a sliding window or exponential decay weighting for the sampling process, such that older data is given lesser weight than new data. Such a system would also allow a core set of data in the Replay Buffer to be given a fixed constant priority. Such a preference weighting could be used to give direct experience from external sources  914  a preferential weighting over self-play  912  generated traces. 
       FIG.  14    is a schematic diagram depicting a design of an agent for generating linguistic responses to verbal and situational input and illustrates the use of the deliberative process with a simulated agent. User x 01  corresponds to user  100  in  FIG.  1   . Simulated agent x 02  may be physically embodied, virtually simulated in virtual reality or augmented reality, or wholly exist in an abstract simulated state. User x 01  provides inputs to simulated agent x 02 , which x 02  captures and encodes via processes in x 03 , to create the current situational input represented by x 04 . X 04  provides information to x 05  to select information to form the context description from relevant background knowledge and recent history. Process x 04 , x 05  and x 06  corresponds to Step  002  in  FIG.  1   , and Steps  102  and  104  in  FIG.  2   . X 07  is the deliberative search process and corresponds to Step  003  and processor  106 . X 08  is the action extraction and selection process and corresponds to Step  005 . X 09  corresponds to the short- and long-term experience memories. X 10  translates the action selected by x 08 , and executes them either as verbal actions, animations or virtual operations (i.e. web search, directed calculation, control operations, etc.). X 10  corresponds to  007 . The primary purpose of the system is to allow the simulated agent x 02  to exhibit more intelligent behavior through simulation and evaluation of the near-term consequences, through the use of a situational descriptions (optionally encoded as natural language) using collected experience and knowledge (especially collected and encoded in natural language). 
       FIG.  15    is a flow chart depicting a training process required for a broad coverage agent using predictive language models. Some embodiments utilize one or more trained generative or predictive language models which are trained on one or more data sources. Such data sources need to include examples of producing next-Steps actions, responses and evaluative statements in the target domain (which may be very broad). As such the corpus of training material will determine the performance of the overall system, both by its selection of initial options and actions, the plausibility of the continuations used in node expansion, and the eventual evaluation statements prompted at the leaves of the search process. It is thus recommended that for broad coverage applications (general chatbot, personal companion, etc.) that Steps y 02 , y 04 , y 06 , and y 08  be employed. 
     Optionally, y 10  may be employed where the system operates in an internal feed back loop to generate simulated conversation logs which are used as additional training material. Self-play provides additional material to reinforce the initial option generation function to produce output more likely to lead to positive outcomes. Unsupervised self-play combined with state space search has shown excellent results in games requiring human interaction. 
       FIG.  16    is a schematic diagram for providing an informational funnel to construct Immediate Situational Descriptions and details the informational funnel, from external sensors to immediate situational description. Simple modifications of the context description provided to a language model can produce very different results. During normal operation in chatbot mode the interaction is presented to variants of OpenAI&#39;s GPT system in what we refer to as “screenplay format”, consisting of lines with the speaker&#39;s name and what they said. A normal input prompt contains the back and forth conversation log followed by the bot name and an open quotation mark, asking the system to generate what the bot is expected to say. The conversational log format is what is collected from users and what is collected from both internet and textual sources. Part of the training dataset for a general chatbot includes movie and tv transcripts. However, we also include normal text, fiction (from various sources, lengths and formats), and a corpus of novels from various genres of literature (action, romance, sci-fi, adult, etc.). 
     While conversations with the system has good quality, when employed with an embodied agent the output generated lack a certain situational responsiveness. This was to be expected, given the information of only the words spoken between actors. A slot for an immediate situational description was placed between the human actor spoken line and the prompt for bot&#39;s response. This situational description corresponds to what would be immediately sensed by an embodied agent, such as “She could see him looking at her”, “She could feel his touch” or “She was in a happy mood.” Such situational descriptions added between the actor&#39;s lines significantly improved the output and responsiveness, even though the system was not trained on text in that format. The additional input helps the system interpret the prior input and conditionalizes the generated output. 
     Having this slot provides a way for placing non-verbalized sensing and motivational information to influence response generation. In the embodied agent use case, this additional information slot provides for the inclusion of simple mappings from sensor input and user descriptions. The flow outlined below is similar to Baar&#39;s Global Workspace attentional funnel. 
     Z 00  corresponds to the sensory input of the simulated agent x 02 , and contains inputs from different sense modalities (audio, visual, tactile, kinematics, etc.). In addition, z 02  contains input from various non-symbolic emotional simulations while z 04  contains input from various motivational simulations. Information from these sources may be collected in z 08  (which corresponds to x 03 ), which acts as a sensory buffer, and encapsulates both the verbal and non-verbal description of the systems state. In addition, other language processors (z 06 ) may be in employed and operate in parallel. The various sensory inputs in z 08  are translated into verbal equivalents and merged with any inputs from z 06  to form a complete list of linguistic descriptions and translations that describe the immediate situation at some time T (z 10 ). This list is priority sorted and merged into a final Immediate Situational Description (ISD) at z 12  which forms the input to x 04  and part of the scene description of step  102  in  FIG.  1   . 
     Normally the interaction log presented to the language model is in screenplay format. The ISD is inserted between the actors lines to provide necessary contextual annotations to include information that is not captured by the normal dialog exchange. 
       FIG.  17    is a block diagram for generating and selecting content using entropy density and a fractional knapsack model. A key requirement for utilizing language models with fixed window processing constraints is selecting the most important or relevant information elements for the system to process. This task can be mapped into a modified fractional knapsack problem where the goal is to maximize the information contained in a fixed size processing window. This is an integral concept for  002 ,  204 , and z 10 -z 12 . The selection process w 00  accepts a list of strings and a total capacity in w 02 . For each string in the list of strings accepted, it creates an element that contains the length, entropy, entropy density and string index for future reference. In information theory, entropy represents the “surprise” or information content of some event E. This is usually represented as the negative log of the probability of an event. In this case the probability is of a word&#39;s occurrence relative to some natural language corpus. To map into a fractional knapsack formulation, the concept of entropy density is created, where the average entropy of each token in each string is estimated. This allows the information content of each string to be compared and the greedy algorithm to be applied in w 06  and w 08 . It is noted that w 08  varies from the standard algorithm to admit whole strings. One can admit the standard algorithm if one is allowed to simplify, summarize or otherwise modify the final string selected by the standard algorithm in such a way that it meets the final fractional assignment requirements. 
     Once w 08  completes, the results and final value are returned in w 10 . The list returned are indexes of the original string list passed that should be included in the processing window. The sorting operation of w 06  may be modified to either sort in ascending or descending order. If ascending order is used then the lowest entropy strings are selected first and the most probable events are attended to. Likewise, if the descending order is used, then the most improbable and individually informative events are included. This allows the effects of attentional low and high pass filtering to be realized through symbolic means. 
     Also, the sources of information accepted by w 02  may be heterogeneous and only require the ability to estimate the probability of each element under consideration (in the example, text). The method may be applied to text from multiple languages and events of multiple modalities that can have their entropies measured. The probability may be estimated via uni-gram, bi-gram, n-gram, other language models or any method that can return a probability for each string and thus estimate the entropy. Metrics other than entropy density may also be used. Also, the knapsack planner can be applied recursively over subsets of relevant information. For instance, a certain capacity may be reserved for certain information types in a global context description. Given a list of pending goals or unknown variables, the relative value of the acquiring each may be specified and the most important combination presented, each using a portion of its own reserved capacity. Any capacity that may be unused may be passed on as extra capacity for other slots in the global context description. 
     Msc Notes Re Knapsack 
     Primary problem addressed:
         for chatbot applications language models generate inappropriate responses   for chatbot applications language models being insensitive to the consequences of their output   for embodied agents (real/virtual) having language models responding to sensory input, emotional and motivational simulations   for language models to control various aspects of embodied agents and associated systems   Dynamic real-time unsupervised training of evaluation classifier   External specification of evaluator by providing training of a evaluation classifier   Using the trained classifier as a backup to the primary classifier and to provide gradient information   Using language models for summary generation   Match of attention between textrank and gpt/transformers
           Translation of sensing into NL and immediate description   Dynamic specification of the formula used in the evaluation process   
               

     Information packet between user facing front-end and backend specifying [classifiers used, eval function, profiles, roles, etc.] 
     Specification of prompt and expansion factor at each tree level 
     Definition of language model to include transformers, rnn, markov models, rule-based, info retreieval and any means of generating a response sequence to an input sequence. 
     Using the principles of evaluation but with single threads, i.e. NON-tree search but N-single extensions with evaluation applied to the end of each 
     Use of GA process in selecting best subset of text for the processing window. In fact we can see it as a Fractional knapsack problem where:
         weight=length of text,   capacity=window size   value=priority/info content       

     In our description one can view a language model to be a blackbox that generates a response sequence to an input sequence. There are many methods that can be used to fill that role, using n-grams, rules and patterns, probability networks (markov models), information retrieval systems (TF-IDF,LSA), and neural nets (rnn&#39;s, LSTM&#39;s, transformers). While implemented with large scale trained generative pre-trained models like GPT, the architecture still can be implemented with any of the other methods. 
     In normal operation, the GPU system can generate a long continuation for each prompt. The test system normally generates batches of 4 continuations at a time until it produces enough to meet the limit specified for a given node (say generate 16 possibilities). Each time it produces a continuation, it generates a little bit more (say it is told to generate 64 words), and the extra is trimmed down to make one complete response. This makes the system behave as required for normal tree search. 
     However, one can request the system produce enough content to reach the normal leaf node (say 256 words). In this case you can break the content produced into turns and apply the evaluation to the content of the leaf. This is the equivalent of looking at just one possible future for each option, versus looking at a branching tree of futures for each option. The benefit of course is each N options require N generation Steps, instead of N*level1*level2* . . . * level_max generation Steps. This allows the system to be more responsive without having to give up the future projection ability. 
     One can also truncate the generation of content in the middle levels, as long as the content generated is sufficient to “sketch the outline of future development”. In some cases it is sufficient to just detect the fact that an argument will ensue, not the full details of the argument. By specifying a truncated generation process, one can speed up the overall search response. 
     Through the use of iterated search one can use smaller/simpler models. The system internal dialog simulation allows it to predict negative outcomes and give preference to responses that lead to positive outcomes. 
     Information passed from the front end to the processing system to generate a response may include:
         Maximum depth and expansion at each level specified   Specify the evaluation function by selection or by formula to be interpreted   Prompt to be used at each level   Literal prompt   Default back and forth prompt   Use of rule based, information retrieval or 1m based generation   Option to let a rule based system evaluate the next generation Step   Additional sensory information or summary of sensory information in the form of NL text   Interpretation of NL text to generate actions including animation       

     In a practical application the linguistic actions may be specified, along with linguistic descriptions of their outcome:
         User: It is dark in here.   System: House, turn living room light to maximum.   Living Room light is at maximum. The Living room is very bright.   User: Ah, much better.       

     The goal-oriented evaluation processor may be trained on material annotated from sources to indicate the achievement of some goal in some interactive session. For instance, achieving some outcome a user may desire, such a solving some problem or performing some service. For instance, achieving some customer service objective (problem resolution, sales, persuasion, etc.) Labeling of such material may be achieved through explicit means (direct confirmation of resolution) or implicit means (user not complaining about problem over some time period). In situations with long or continuous interaction histories, persistent changes in user sentiment may detected and used as a reinforcement signal. 
     The present invention provides advantages of a simulated virtual agent which responds with textual expression to textual input from external user and external virtual agents in combination with the audio, visual, and tactile inputs. The textual expression from the virtual agent being generated by processes utilizing one or more language models, self-moving modules, and both current and prior conversation logs with self-learning reference conversations in combination with MCTS processes and self-learning techniques. Selection of the virtual agent&#39;s textual responses including simulated sentiment analysis and goal oriented analysis to assign values which are weighted, normalized, and merged in selecting textual responses through internal self-discussion tree search techniques. 
     Although the preferred embodiment has been described in detail, it should be understood that various changes, substitutions and alterations can be made therein without departing from the spirit and scope of the invention as defined by the appended claims.