A Neural-Symbolic Cognitive Agent for Online Learning and Reasoning

Introduction

The effective integration of automated learning and cognitive reasoning in real-world applications is a difficult task [Valiant, 2003]. Usually, most applications deal with large amounts of data observed in the real-world containing errors, missing values and inconsistencies. Even in controlled environments, like training simulators, integrated learning and reasoning is not very successful [Sandercock, 2004; Heuvelink, 2009]. Although the use of training simulators simplifies the data and knowledge acquisition, it is still very difficult to construct a cognitive model of an (intelligent) agent that is able to deal with the many complex relations in the observed data. When it comes to the assessment and training of high-order cognitive abilities (e.g. leadership, tactical manoeuvring, safe driving, etc.) training is still guided or done by human experts [Bosch and Riemersma, 2004]. The reason is that expert behaviour on high-level cognition is too complex to model, elicit and represent in an automated system. There can be many temporal relations between low and high-order aspects of a training task. Human behaviour is often non-deterministic and subjective (i.e. biased by personal experience and other factors like stress or fatigue) and what is known is often described vaguely and limited to explicit (i.e. "explainable") behaviour.

Several attempts have been made to tackle these problems. For instance [Fernlund et al., 2006] describes a number of systems that use machine learning to learn the complex relations from observation of experts and trainees during task execution. Although these systems are successful in learning and generalization, they lack the expressive power of logic-based (symbolic) systems and are therefore difficult to understand and validate [Smith and Kosslyn, 2006]. Alternatively, one could add probabilistic reasoning to logicbased systems [Heuvelink, 2009]. These systems perform better in expressing their internal knowledge as they are logic based and are able to deal with inconsistencies in the data because they reason with probabilities. Unfortunately, when it comes to knowledge representation and modelling these systems still require either statistical analysis of large amounts of data or knowledge representation by hand. Therefore, both approaches are time expensive and are not appropriate for use in real-time applications, which demand online learning and reasoning.

In this paper, we present a new cognitive agent model that is able to: (i) perform learning of complex temporal relations from uncertain observations, (ii) reason probabilistically about the knowledge that has been learned, and (iii) represent the agent's knowledge in a logic-based format for validation purposes. This is achieved by taking advantage of neural learning to perform robust learning and adaptation, and symbolic knowledge to represent qualitative reasoning. In addition, the model is validated in a training simulator employed in real-world scenarios, illustrating the effective use of the approach. The results show that the agent model is able to learn to perform automated driver assessment from observation of real-time simulation data and assessments by driving instructors and that this knowledge can be extracted in the form of temporal logic rules.

Preliminaries

The construction of effective cognitive agent models is a long standing research endeavour in artificial intelligence, cognitive science, and multi-agent systems [Valiant, 2003; Wooldridge, 2009]. One of the main challenges toward achieving such models is the provision of integrated cognitive abilities, such as learning, reasoning and knowledge representation. Recently, cognitive computational models based on artificial neural networks have integrated inductive learning and deductive reasoning, see e.g. [Garcez et al., 2009; Lehmann et al., 2010]. In such models, neural networks are used to learn and reason about (an agent's) knowledge about the world, represented by symbolic logic. In order to do so, algorithms map logical theories (or knowledge about the world) T into a neural network N which computes the logical consequences of T. This provides also a learning system in the network that can be trained by examples using T as background knowledge. In agents endowed with neural computation, induction is typically seen as the process of changing the weights of a network in ways that reflect the statistical properties of a dataset, allowing for generalizations over unseen examples. In the same setting, deduction is the neural computation of output values as a response to input values (stimuli from the environment) given a particular set of weights. Such network computations have been shown equivalent to a range of temporal logic formalisms [Lamb et al., 2007]. Based on this approach the agent architecture of our model can be seen as a Neural Symbolic Cognitive Agent (NSCA). In our model, the agent architecture uses temporal logic as theory T and a Restricted Boltzmann Machine (RBM) as neural network N. A RBM is a partially connected neural network with two layers, a visible V and a hidden layer H, and symmetric connections W between these layers [Smolensky, 1986].

A RBM defines a probability distribution P(V=v,H=h) over pairs of vectors v and h encoded in these layers, where v encodes the input data in binary or real values and h encodes the posterior probability P(H|v). Such a network can be used to infer or reconstruct complete data vectors based on incomplete or inconsistent input data and therefore implement an auto-associative memory. It does so by combining the posterior probability distributions generated by each unit in the hidden layer with a conditional probability distribution for each unit in the visible layer. Each hidden unit constrains a different subset of the dimensions in the high-dimensional data presented at the visible layer and is therefore called an expert on some feature in the input data. Together, the hidden units form a so-called "Products of Experts" model that constrains all the dimensions in the input data.

A RBM has no connections between visible and other visible or hidden and other hidden units, making the experts conditionally independent. This restriction makes it possible to infer the posterior probabilities for each expert in parallel and train the network very effectively using Contrastive Divergence [Hinton, 2002]. This makes the learning and inference of a RBM very fast and therefore a suitable candidate for N in our agent architecture.

The Cognitive Model and Agent Architecture

Figure 1 presents the Neural-Symbolic Cognitive Agent (NSCA) architecture of our cognitive model. This model is able to encode domain knowledge in the form of temporal logic rules as hypotheses in a RBM, learn new hypotheses from observed data, reason with these hypotheses and extract new rules from these hypotheses in temporal logic form to update the domain knowledge.

The NSCA uses a Recurrent Temporal Restricted Boltzmann Machine (RTRBM) that encodes the temporal rules in the form of hypotheses about beliefs and previously-applied rules. This is possible due to recurrent connections between hidden unit activations at time t and the activations at time t-1, see [Sutskever et al., 2008]. Based on the Bayesian inference mechanism of the RTRBM each hidden unit Hj represents a hypothesis about a specific rule Rj that calculates the posterior probability that the rule implies a certain relation in the beliefs b being observed in the visible layer V, given the previously applied rules r t-1 (i.e. P(R|B=b,R t1 =r t-1 )). From these hypotheses the RTRBM selects the most applicable rules r using random Gaussian sampling of the posterior probability distribution (i.e. r ~ P(R|B=b,R t-1 =r t-1 )) and calculates the conditional probability or likelihood of all beliefs given the selected rules are applied (i.e. P(B|R=r)). The difference between the observed and inferred beliefs can be used by the NSCA to train the RTRBM (i.e. update its weights) in order to improve the hypotheses about the observed data. There the RTRBM uses a combination of Contrastive Divergence and backpropagation through time, see [Sutskever et al., 2008].

In the spirit of BDI agents [Bratman, 1999], the observed data (e.g. simulation data, human assessments) is encoded as beliefs and the difference between the observed and inferred beliefs are the actual implications or intentions of the agent on its environment (e.g. adapting the assessment scores in the training simulator). The value of a belief represents either the probability of the occurrence of some event or state in the environment (e.g. Raining=true), or a real value (e.g. Speed=31.5). In other words, the NSCA deals with both binary and continuous data, by using a continuous stochastic visible layer [Chen and Murray, 2003]. As will become clear in our experiments, this improves the agent's ability to model asymmetric data, which in turn is very useful since measured data coming from a simulator is often asymmetric (e.g. training tasks typically take place in a restricted region of the simulated world).

Due to the stochastic nature of the sigmoid activation functions used in our model, the beliefs can be regarded as fuzzy sets with a Gaussian membership function. This allows us to represent vague concepts like fast and slow, as well as approximations of learned values, which is useful when reasoning with implicit and subjective knowledge [Sun, 1994].

future traffic is approaching from the right

((Speed > 0) ∃ HeadingIntersection) S (DistanceIntersec(3)

tion < x) → ApproachingIntersection

meaning: if the car is moving and heading towards an intersection since it has been deemed close to the intersection, then the car is approaching the intersection.

Assessment:

ApproachingIntersection ∃ (DistanceIntersection = 0) ∃ (ApproachingTraffic = right) ∃ (Speed = 0) → (Evaluation = good) (4)

meaning: If the car is approaching an intersection and arrives at the intersection when traffic is coming from the right and stops then the trainee gets a good evaluation.

Rule 4 is an example of an uncertain notion that is highly subjective (the distance x at which a person is regarded as approaching an intersection is dependent on the situation and personal experience). When this rule is encoded in a RTRBM, it becomes possible to learn a more objective value for x based on the observed behaviour of different people in various scenarios. This exemplifies our main objective at combining reasoning and learning.

In our model, the temporal logic rules are represented by setting the weights W and W' (see Figure 1) in the RTRBM. Therefore the rules need to be translated to a form that relates only to the immediately previous time step (denoted by the temporal operator ●). A transformation algorithm for this is described in [Lamb et al., 2007]. Then we can encode any rule as a stochastic relation between the hidden unit that represents the rule, the visible units that represent the beliefs and the previous hidden unit activations that represent the applied rules in the previous time step. For example, the rule αSβ can be translated to the following rules: β → αSβ and α ∃ ●(αSβ)

Temporal Knowledge Representation

To represent domain knowledge in terms of beliefs and previously-applied rules we use the cognitive temporal logic described in [Lamb et al., 2007]. This logic contains several modal operators that extend classical modal logic with a notion of past and future. To express beliefs on continuous variables we extend this logic with the use of equality and inequality formulas (e.g. Speed<30, Raining=true). As an example let us take the task depicted in Figure 2. In this task, a trainee drives on an urban road and approaches an intersection. In this scenario the trainee has to apply the yield-to-the-right-rule. Using our extended temporal logic, we can describe rules about the conditions, scenario and assessment related to this task. In rules 1 to 4 below, ◊A denotes "A is true sometime in the future" and ASB denotes "A has been true since the occurrence of B".

ApproachingIntersection ∃ ◊(ApproachingTraffic = right) (2) meaning: the car is approaching an intersection and sometime in the

→ αSβ, where α and β are modelled by visible units, αSβ by a hidden unit and ●(αSβ) is modelled by a recurrent connection to the same hidden unit. [Pinkas, 1995] shows how to map these logic-based propositions into the energy function of a symmetric network and how to deal with uncertainty by introducing a notion of confidence, called "penalty". We have adapted those algorithms to temporal logic and the RTRBM and show how to encode temporal logic rules in RTRBM and how to extract revised rules from a trained RTRBM.

Rule Extraction Algorithm

Step 1: Finding maximum likelihood. In order to extract the temporal rules from the RTRBM, we need to find the states of the visible units (V) and hidden units (H) that lower the total energy in its energy function. This means finding the states that maximize the likelihood of each rule. These states form the local minima (stable states) in the energy function and depend on the weights encoded in the RTRBM. Using the RTRBM's inference mechanism we can find these states by sampling the belief states from the conditional probability distribution calculated for each rule at a time, given only that rule is selected (i.e., H (j) =1˄ H (x≠j) =0). More formally, for each hidden unit H (j) we create a rule Rj and for each visible unit V (i) a belief Bi for which the conditional probabilities of the beliefs and previously applied rules R t-1 j (associated with the hidden unit activations at time t-1 denoted by Ht-1 (j) ) are defined by:

For each rule Rj, the value of each belief in the belief base, denoted as a vector bj is set to P(B|Rj) (denoted by ← in Eq. 8) and the value of each previously applied rules, denoted as r t-1 j is sampled (using a random Gaussian sampling) from P(R t-1 |Rj) (this is denoted by ~ in Eq. 9).

Step 2. Generating a rule. When we have calculated the belief and previous rule states that maximize the likelihood of each rule, we can construct a temporal logic formula Ψ with temporal modalities using the following equations (where k is the number of beliefs, m the number of rules and wij is the weight of the connection between V (i) and H (j) ):

The propositions on beliefs, denoted by φj (i) , are calculated using Eq. 11 and depend on the weight wij of the connection between the hidden unit H (j) that represents rule Rj and visible unit V (i) that represents belief Bi. A negative weight between V (i) and H (j) will increase the probability of Rj when we decrease the value of Bi. So all values for belief Bi less or equal to bj(i) will increase the probability of rule Rj. The inverse applies to a positive weight. When the weight is zero a belief has no influence on the rule and can be left out.

The propositions on previously applied rules, denoted by ρj (i) , are calculated using Eq. 12 and use the temporal operator ●. By applying the transformation algorithm in [Lamb et al., 2007] the generated rules can be further simplified for readability.

In the spirit of [Pinkas, 1995] and [Lee, 1997] we also calculate a confidence level cj for each rule that denotes the probability that rule Rj is actually implied by the state defined in bj and r t-1 j (see Eq. 13).

Rule Encoding Algorithm

The knowledge extraction algorithm above shows that temporal logic rules can be extracted from RTRBM reasonably efficiently. Encoding these rules is the dual of the extraction algorithm.

Step 1. Encoding a rule. For each rule defined by Eq. 10:

1. Add a hidden unit H (j) to the RTRBM to represent Rj.
2. For each belief Bi in the rule, add a visible unit V (i) .
3. Randomize the weights connecting V (i) with H (j) .

Step 2. Setting the weights. For each rule calculate the weights that maximize the likelihood of the beliefs Bj and previously applied rules R t-1 j:

1. For each hidden unit H (j) , calculate its activation h (j) using the inference algorithm in [Sutskever et al., 2008].
2. Set the value of hidden unit H (j) to 1 and the other hidden units H (x≠j) to 0.
3. Infer the conditional probabilities of beliefs b' and previously applied rules r ' given the current weights using eqs. 8 and 9.
4. Minimize the difference by minimizing the contrastive divergence between, resp., h (j) , b' and r ' and the values for cj, Bj and R t-1 j as defined by rule Rj.

Experiments and Results

The cognitive model has been developed as part of a three year research project on assessment in driving simulators, carried out by TNO in cooperation with the Dutch licensing authority (CBR), Research Centre for Examination and Certification (RCEC), Rozendom Technologies, and ANWB driving schools. The NSCA is implemented using a multi-agent platform for Virtual Instruction [de Penning et al., 2008] and was used for an experiment on one of the ANWB driving simulators. In this experiment 5 students participated in a driving test consisting of 5 test scenarios each. For each attempt all data from the simulator (i.e. 43 measurements, like relative positions and orientations of all traffic, speed, gear, and rpm of the student's car) and assessments scores (0-100) on several driving skills (i.e. vehicle control, economic driving, traffic flow, social-, and safe driving) that were provided by 3 driving instructors during the attempts were observed by the NSCA in real-time. The results in figures 3 and 4 show that the NSCA was able to learn from these observations and infer assessment scores that are similar to those of the driving instructors. For readability, the figures only show the actual (i.e. given by the instructor) and inferred beliefs (i.e. calculated by the NSCA) on assessment scores, but in fact the NSCA reconstructs beliefs over all aspects, including the expected position and orientation of other vehicles. This generative property of the RTRBM enables the NSCA to deal with uncertainty and missing data related to the observed beliefs based on the encoded rules. Also, the difference between actual and inferred beliefs can be translated into intentions to change a simulation in order to adapt to the student's level of expertise (i.e. adaptive training).

Assessment Data Eqs. 14 and 15 show some examples of learned hypotheses on temporal relations between observations, that were extracted from the NSCA. These rules imply relations on beliefs and previously- applied rules with a certain probability (i.e. confidence). In case of driving assessment, the implications are the assessment scores that are inferred from observed behaviour in a driving simulator. For readability we left out the beliefs that have insignificant impact on the truth-value of the rules based on the normalized weights of the beliefs in the rules.

0.72: R47 ↔ car_Spatial_Orientation_Psi >= 0.062 ∃ car_Spatial_WorldLocation_Y >= -2701220 ∃ car_Spatial_WorldLocation_Z >= 1632605 ∃ cy-clist_Spatial_Orientation_Psi <= -0.088 ∃ cy-clist_Spatial_WorldLocation_X <= -163262 ∃ cy-clist_Spatial_WorldLocation_Z <= 1598489 ∃ my-car_BrakeDepression <= 49.5 ∃ mycar_EmergencyLight = false ∃ mycar_Gear >= 2 ∃ mycar_HighBeam = false ∃ mycar_ParkingBrake = false ∃ mycar_RightIndicator = false ∃ objectives_flow_score >= 50.56101934052543 ∃ ●R3 ∃ ●R4 ∃ ●R6 ∃ ●R8 ∃ ●R9 ∃ ●R11 ∃ ●R13 ∃ ●R16 ∃ ●R23 ∃ ●R24 ∃ ●R25 ∃ ●R28 ∃ ●R42 (14) 0.78: R13 ↔ car_Spatial_Orientation_Phi <= -0.031 ∃ car_Spatial_WorldLocation_Y >= -2702291 ∃ cy-clist_Spatial_Orientation_Phi >= 0.085 ∃ cy-clist_Spatial_WorldLocation_X <= -164763 ∃ my-car_BrakeDepression <= 49.2 ∃ mycar_EmergencyLight = false ∃ mycar_FuelConsumption >= 0.0045 ∃ mycar_Gear >= 1 ∃ mycar_HighBeam = false ∃ mycar_SteeringAngleVelocity >= -57.5 ∃ objectives_flow_score <= 49.78478771808131 ∃ objectives_safe_score <= 49.55145948925322 ∃ ●R1 ∃ ●R4 ∃ ●R6 ∃ ●R7 ∃ ●R8 ∃ ●R10 ∃ ●R11 ∃ ●R12 ∃ ●R17 ∃ ●R21 ∃ ●R25 ∃ ●R28 ∃ ●R34 ∃ ●R44 (15)

The rules in eq. 14 and 15 are the result of a small experiment and require further validation by experts, but one can see plausible effects that certain beliefs have on the outcome of the assessment scores. For example, when the gear in rule R47 is in position 2 or higher we can conjecture that this facilitates better traffic flow. And when the steering angle velocity in rule R13 is very high (i.e. the student's steering must have been very rough), one can imagine lower assessment scores on safe driving. More experiments with larger populations of students and instructors have been planned for this year for which we expect further improvement of the learned knowledge on driving assessment.

Conclusions and Future Work

The cognitive model and agent architecture presented in this paper offer an effective approach that integrates symbolic reasoning and neural learning in a unified model. This approach allows the agent to learn rules about observed data in complex, real-world environments (e.g. expert behaviour for training and assessment in simulators). Learned behaviour can be extracted to update existing domain knowledge for validation, reporting and feedback. Furthermore the approach allows domain knowledge to be encoded in the model and deals with uncertainty in real-world data. Results described in this paper show that the agent is able to learn new hypotheses from observations and extract them into a temporal logic formula. Although initial results are promising, the model requires further validation by driving experts. More experiments are planned on ANWB driving simulators. This will allow further validation of the model in an operational setting with many scenarios, a large trainee population and multiple assessments by driving instructors. In parallel, the system will also be tested in other simulation domains, like jetfighter pilot training and for strategic command and control training. Other future work includes research on using Deep Boltzmann Machines [Salakhutdinov and Hinton, 2009] to find higher-level rules and the application of an RTRBM to facilitate adaptive training. In summary, we believe that our work provides an integrated model for knowledge representation, learning and reasoning which may indeed lead to realistic computational cognitive agent models, thus answering the challenges put forward in [Valiant, 2003; Wooldridge, 2009].