Apparatus and method for learning and reasoning for systems with temporal and non-temporal variables

[0001] The invention relates generally to the fields of machine learning, machine reasoning, and machine intelligence.

[0002] Various models have been proposed to perform reasoning with spatiotemporal data, including Bayesian networks and neural networks. Bayesian networks provide a well-established way to represent causal relationships using a structure. But they are typically designed by humans with expertise in the problem domain, and can suffer from human error, ideologies, preconceived notions, and prejudices. The use of Bayesian networks can therefore produce inaccurate and incomplete representations of the problem domain.

[0003] Bayesian networks also tend to require extensive human involvement through design and training. This can make them very expensive to implement. Dynamic Bayesian belief networks, such as such as Hidden Markov Models, have also been proposed (see, e.g., “An introduction to hidden Markov models,” by L. R. Rabiner and B. H. Juang, IEEE ASSP Mag., pp 4-16, June 1986.). But their development is even more complex, and is still fundamentally based on human effort.

[0004] Neural networks are computational systems that use interconnected modeled neurons, which may mimic cognitive or biological functions. These networks can be trained to process information for different types of problems. But they tend to exhibit “black box” characteristics, and the structure of the selected model generally cannot be used for causal analysis.

[0005] In one general aspect, the invention features a method of deriving information about behavior of a target system. The method includes accessing one or more temporal variables for the target system, providing an identifier node at the top of a hierarchy of a tree-structured belief network, and assigning a different sub-tree in the network to each of the accessed temporal variables. The method also includes accessing evidence data, and deriving information about the behavior of the target system for the evidence data based on the tree-structured belief network.

[0006] In preferred embodiments, the method can further include steps of accessing one or more static variables and assigning child nodes in the network to the accessed static variables. The step of deriving can include extracting a model of the target system from the network, and setting evidence data in the model. The method can further include the step of acquiring the evidence data from a computing apparatus input device. The method can further include the step of acquiring the evidence data from sensors. The step of extracting a model can employ a learning process to extract a Bayesian model from the network. The step of extracting a model can employ an expectation-maximization process. The step of assigning different sub-trees can assign nodes in the different sub-trees based on required temporal resolution, available data resolution, and computational limitations. The step of assigning different sub-trees can assign nodes in the different sub-trees automatically. The method can further include the step of adding arcs from the root node to the static nodes and to top-level ones of the dynamic nodes. The step of assigning different sub-trees in the network to the plurality of temporal variables can assign the variables in a temporal hierarchy at multiple time slices. The temporal variables can be organized such that samples at instants of time are represented by nodes. The temporal variables can be organized such that aggregate functions are represented at higher-level nodes. The aggregate functions can include at least one of: mean, maxima, and minima. Data used to develop the network can be discretized. The step of deriving can derive information about likely outcomes for the target system. The step of deriving can derive information about causes of target system behavior. The steps of accessing, providing, assigning, and deriving can be performed at least in part by computing apparatus, wherein the tree-structured belief network is stored in storage associated with the computing apparatus, and further including the step of presenting results of the step of deriving to a user on an output interface of the computing apparatus. The target system can be a physical system with the information derived for the target system being used to make changes to the physical system. The steps of providing and assigning can be completely automatic. The step of accessing can provide accesses a plurality of temporal variables and the step of providing can provide a plurality of sub-trees for the accessed temporal variables, with each sub-tree corresponding to one of the accessed temporal variables.

[0007] In another general aspect, the invention features a method of deriving information about the behavior of a target system that includes receiving a model of the target system that is based on a tree-structured belief network in which an identifier node is provided at the top of a hierarchy of the belief network, and a different sub-tree in the network assigned to each of one or more temporal variables. The method also includes the steps of accessing evidence data, and deriving information about the behavior of the target system for the evidence data based on the model.

[0008] In a further general aspect, the invention features a method of deriving information about the behavior of a target system that includes accessing one or more temporal variables for the target system, providing an identifier node at the top of a hierarchy of a tree-structured belief network, assigning a different sub-tree in the network to each of the temporal variables accessed in the step of accessing, and extracting a model of the target system from the network. In preferred embodiments, the step of extracting a model can employ a learning process to extract a Bayesian model from the network.

[0009] In another general aspect, the invention features a system for deriving information about behavior of a target system. The system includes a system interface, machine-readable storage for a tree-structured belief network, and tree-structured belief network interaction logic, which is operative to interact with the system interface and a tree-structured belief network stored in the machine-readable storage. The tree-structured belief network includes an identifier node at the top of a hierarchy of the tree-structured belief network, and a different sub-tree in the network assigned to each of one or more temporal variables.

[0010] In a further general aspect, the invention features a system for deriving information about behavior of a target system that includes means for interacting with the system, means for storing a tree-structured belief network, and means for interacting with the system interface and a tree-structured belief network stored in the machine-readable storage. The tree-structured belief network includes an identifier node at the top of a hierarchy of the tree-structured belief network, and a different sub-tree in the network assigned to each of one or more temporal variables.

[0011] In another general aspect, the invention features a memory for storing data for access by computing apparatus. The memory includes an identifier node at the top of a hierarchy of the tree-structured belief network, and a different sub-tree in the network assigned to each of one or more temporal variables.

[0012] Modeling systems according to the invention can provide enhanced learning and reasoning for target systems with temporal and non-temporal variables. By providing a network that includes temporal variable sub-trees, these systems can capture temporality inherently and elegantly. This can result in a model that can be more true to the target system, and therefore permit more accurate and precise learning and reasoning capabilities. This can be a significant improvement over many types of prior art approaches, such as simple Bayesian networks and neural networks, which tend not to handle temporal data very well.

[0013] Systems according to the invention can also provide models that are simpler to develop, work with, and comprehend. Capturing temporal and spatial patterns in a single model can make the model easy to develop, and in some cases, the model can simply emerge from data about the problem to be modeled. The hierarchical organization of models produced by the system also tends to make them easy to work with and understand.

[0022] Referring to FIG. 1, an illustrative modeling system according to the invention can include a system interface 12, reasoning and/or learning logic 14, and network storage 16. The system interface can be a user interface that allows system designers and/or end users access to the system, such as through a keyboard/pointing device and a display. It can also include data communication logic that allows evidence data or model elements to be communicated to the system. And it may communicate with sensors to obtain readings to be processed by the system.

[0023] Generally, the reasoning/learning logic 12 uses a model of a target system stored in the network 14 to derive information about the target system. The modeling system can derive information about sounds, images, moving images, electromagnetic signals, chemical data, biological data, economic data, or any other suitable type of input for a target system. Examples of the many possible applications of the system include enhanced Natural Language Processing (NLP), Natural Language Understanding (NLU), pattern recognition, noise filtering, financial market analysis, cost analysis and projections, optimal resource and deliverable quota allocation, real time decision support for automatic system controls, risk identification systems, prospecting (e.g., oil), threat profiling, supply chain management, clinical decision-making, drug development, as well as clinical trial design, management and analysis. The system can also be applied to networks, such as the internet, for tasks such as malware detection, searching, and load balancing. The system can also be applied to knowledge extraction from information in various forms and from various sources with applications in search using cell phones, search using internet and organizational knowledge management and applications for quick extraction of relevant knowledge from such systems.

[0024] The various parts of the system can be implemented using dedicated hardware, a specially programmed general-purpose computer, or a combination of both. In the example presented below, the system is implemented using Microsoft Windows®-based computers. But other software platforms could of course also be supported, such as Linux® or Unix® platforms.

[0025] Referring to FIG. 2, use of the system involves the creation of a specialized belief network that processes data in a tree-shaped hierarchy representing spatiotemporal data input at the lowest layer. This model allows the system to infer a hierarchy of causes from data and use the causes to make predictions about likely outcomes. The network can be developed manually, automatically, or semi-automatically.

[0026] Development of the network begins with the enumeration of parameters (step 22) from a design data set 24 for the target system. If the parameters contain temporal data (step 26) a decision is made on the temporal resolution of the system by selecting a set of time units, such as hours or seconds (step 28). A design choice for a temporal hierarchy is then made (step 32), and the data are discretized into bins (step 30). These steps are repeated until all of the data have been processed.

[0027] A tree-shaped hierarchical model 50 is then developed (step 34), and nodes are mapped into discretized data (step 36). An expectation maximization (parameter learning) process is then applied by a learning application to the discretized data (step 38), and a hierarchical Bayesian model is output (step 40). This model can then be used to derive information about the behavior of the target system, such as predictions about its future behavior or the causes of given behaviors. Expectation maximization is described, for example in “Maximum likelihood from incomplete data via the EM algorithm,” by Arthur Dempster, Nan Laird, and Donald Rubin, Journal of the Royal Statistical Society, Series B, 39(1):1-38, 1977, which is herein incorporated be reference.

[0028] Table 1 shows an illustrative example of a spatiotemporal data set consisting of three static parameters and two dynamic parameters. The static fields are fields that do not vary over time, or vary negligibly over time. The dynamic fields are fields that are measured at different instances of time.

[0029]

	TABLE 1
	Dynamic Fields
	Static Fields		Dynamic	Dynamic
ID	Field-1	Field-2	Field-3	Date	Time	Field-1	Field-2
1	Value	Value	Value	d1	T1	Value − t1	Value − t1
1	Value	Value	Value	d1	T2	Value − t2	Value − t2
		.			.
		.			.
1	Value	Value	Value	d1	tn	Value − tn	Value − tn
2	Value	Value	Value	d1	T1	Value − t1	Value − t2
2	Value	Value	Value	d1	T2	Value − t2	Value − t2
		.			.
		.			.
2	Value	Value	Value	d1	tn	Value − tn	Value − tn
3	Value	Value	Value	d1	T1	Value − t1	Value − tn
3	Value	Value	Value	d1	T2	Value − t2	Value − tn
		.			.	.
		.			.	.
3	Value	Value	Value	d1	tn	Value − tn	Value − tn
		.				.
		.				.
N	Value	Value	Value	d1	T1	Value − tn	Value − tn
N	Value	Value	Value	d1	T2	Value − t1	Value − tn
N	Value	Value	Value	d1	T3	Value − t2	Value − tn
		.			.	.
		.			.	.
N	Value	Value	Value	d1	tn	Value − tn	Value − tn

[0030] Referring to FIG. 3, for each of the dynamic parameters, a sub-tree 50 similar to the one shown is created. This sub-tree shows a hierarchy of sequences (sequences of sequences) from decades to seconds. The hierarchy could be expanded to higher order sequences e.g. centuries or decades or lower order sequences e.g. milliseconds, or nanoseconds. The sequences also do not need to correspond to exact units, as presented below in connection with Example 1.

[0031] Depending on the availability of data, the values in the higher order time slices could be defined by one of the following aggregate functions:

• • [0032] the maxima of the parameter across the time-slice (decade, year, month, . . . ),
  • [0033] the mean of the parameter across the time-slice (decade, year, month, . . . ), or
  • [0034] the minima of the parameter across the time-slice (decade, year, month, . . . ).
    Similarly, for lower order time-slices the values could be one of the following disaggregating functions:
  • [0035] the maxima of the parameter across the time-slice (decade, year, month, . . . ) divided by the number of intervals
  • [0036] the mean of the parameter across the time-slice (decade, year, month, . . . ) divided by the number of intervals, or
  • [0037] the minima of the parameter across the time-slice (decade, year, month, . . . ) divided by the number of intervals.
    The design decisions for the sub-tree are made based on available data, computational power available, and resolution of inference needed.

[0038] Referring to FIG. 4, an overall network 60 includes an identifier 62 as a root node. Child nodes 64A . . . 64N depending from the root node are assigned to static variables. And sub-trees 50A . . . 50N are assigned to data for the temporal variables.

[0039] Referring to FIG. 5, the system is also capable of learning in an unsupervised or semi-supervised mode. Once the data is arranged into a temporal hierarchy as described above, with the identifier node at the top and the various discrete temporal dimensions (sequences and sequences of sequences). An unsupervised learning process, such as Naïve Bayesian Learning, is applied to the data generate a hierarchical model with arcs from the ID node to the static and the dynamic elements. Näive Bayesian Learning is described in more detail in “Machine Learning,” by Tom Mitchell, McGraw Hill, 1997 (Ch. 6), which is herein incorporated by reference.

[0040] In the unsupervised and semi-supervised cases, the designer has much less control in the design of the network, such as its hierarchy and level of resolution. This approach can yield an almost entirely automated mechanism of learning, which can take as input the data arranged in the form described above and generate a model with minimal supervision. Embodiments of this type may be useful for applications where exceedingly complex datasets exist which cannot be easily analyzed by human analysts, or where domain knowledge is sparse and therefore the designer cannot conceive of an a priori hierarchy.

[0041] Referring to FIG. 6, once the model is trained it is available for querying. The system performs the querying process by setting evidence in the network from partial inputs and observing the resultant a posteriori distribution at the other nodes. The model is first loaded into the program and the evidence data is discretized in a similar fashion as the training model. The evidence is then set to the trained model at the appropriate nodes. Once the evidence is set, the beliefs are propagated across the network to calculate the posterior beliefs using an process such as Pearl Belief Propagation. Pearl Belief Propagation is described in “Probabilistic Reasoning in Intelligent Systems,” by Judea Pearl, Morgan-Kaufman Publishers, SanFrancisco, Calif., 1988, which is herein incorporated by reference.

[0042] Once the beliefs are propagated, the target nodes could be a selection or all of the nodes for which evidence has not been set. The maximum a posteriori (MAP) state of the target nodes is the state for which the posterior probability is highest. In cases where a continuous value for inference is needed, the weighted average of the states' values is calculated, weighted by the posterior probabilities of each state. An individual state value is generally the mean of the lowest and highest values in the interval. However, the designer can manually estimate the individual state values.

[0043] The following table illustrates how this might work a node with 4 states that measure temperature:

[0044]

	State	State Value	Posterior Probability
	T0_10	5	0.004
	T10_12	11	0.016
	T12_20	16	0.485
	T20_30	25	0.495

The exact inference value would Be
Inference=5×0.004+11×0.016+16×0.485+25×0.495=20.331

[0045] Referring to FIGS. 2 and 7, a specific illustrative implementation will now be described. This implementation is a weather forecasting system that is based on weather data consisting of two dynamic or temporal parameters, namely, temperature (expressed in degrees Fahrenheit) and relative humidity (expressed as a percentage). The data also includes one static or time invariant parameter, namely altitude (expressed in feet above sea level). The dynamic parameters were measured for three consecutive days at six hour intervals. The training data are shown in Table 2.

[0046]

TABLE 2
				Relative
Location	Date	Time	Temperature(F.)	Humidity(%)	Altitude (ft)
Boston, MA	Jan. 01, 2004	0:00	14.3	81	140
Boston, MA	Jan. 01, 2004	6:00	23.9	61	140
Boston, MA	Jan. 01, 2004	12:00	27.2	77	140
Boston, MA	Jan. 01, 2004	18:00	22.1	70	140
Boston, MA	Jan. 02, 2004	0:00	11.9	75	140
Boston, MA	Jan. 02, 2004	6:00	22.1	80	140
Boston, MA	Jan. 02, 2004	12:00	28.8	82	140
Boston, MA	Jan. 02, 2004	18:00	23.4	89	140
Nashua, NH	Jan. 01, 2004	0:00	18.3	81	150
Nashua, NH	Jan. 01, 2004	6:00	19.9	61	150
Nashua, NH	Jan. 01, 2004	12:00	21.2	77	150
Nashua, NH	Jan. 01, 2004	18:00	22.4	70	150
Nashua, NH	Jan. 02, 2004	0:00	19.9	75	150
Nashua, NH	Jan. 02, 2004	6:00	14.1	80	150
Nashua, NH	Jan. 02, 2004	12:00	21.8	82	150
Nashua, NH	Jan. 02, 2004	18:00	23.4	89	150

[0047] Development of the network begins with the enumeration of static and dynamic parameters (step 22) from the data set shown in Table 2. Because temporal data is present (step 26), a spatiotemporal model needs to be constructed. A decision is then made on the temporal resolution of the system by selecting a six-hour time interval (step 28). A design choice for a two-level temporal hierarchy is then made (step 32).

[0048] The continuous data for all the parameters was discretized into 4 bins (step 30). The model of discretization was the uniform counts method, which distributes the records to the bins as evenly as possible. The steps are repeated until all of the data have been processed.

[0049] A tree-shaped hierarchical model 50′ is then developed (step 34), and nodes are mapped into discretized data (step 36). The higher level nodes TD1 (Temperature Day 1), TD2 (Temperature day 2), HD1 (Humidity Day 1) and HD2 (Humidity Day 2) to the aggregate (mean) of the temperatures for the day. The aggregate values are also discretized. An expectation maximization (parameter learning) process is then applied by a learning application to the discretized data (step 38), and a hierarchical Bayesian model is output to a file (step 40).

[0050] The learning process is now complete and the network can be used for inferencing, to derive information about the behavior of the target system, such as predictions of future weather. The inferencing process involves loading the saved network into program memory, and applying evidence data, such as the data listed in Table 3.

[0051]

				Relative
Location	Date	Time	Temperature(F.)	Humidity(%)	Altitude (ft)
Nashua, NH	Jan. 01, 2005	10:00		77	144
Nashua, NH	Jan. 01, 2005	18:00	22.0

The first record is set to node HD1 I2 and altitude is set to the altitude node since the measured quantity is for relative humidity for Day 1 and in the second 6-hourly time interval. Next, the observed temperature for record 2 is set as evidence to node TD2 I3 since it is for Day 2 and the 3rd 6-hourly time interval. The target nodes are the complement of the evidence nodes in the network i.e. TD1, TD2, Altitude, HD1 I1, HD1 I3, HD1 I4, TD1 I1, TD1 I2 and TD1 I4. If exact inference is needed a weighted average for all the output states weighted by, the a posteriori probability is calculated. Otherwise, the maximum a posteriori state is displayed.

[0052] The training and inferencing code for this example was implemented using a single Windows®-based platform. Its core code was written in C++, and .NET/C# (C-Sharp) and Python were used for its application layer. But it is also contemplated that different parts of the system could be performed on different computers. For example, model development could take place on a first system, and the inferencing could be performed on an end-user system, such as a mobile terminal or a controller.

[0053] The present invention has now been described in connection with a number of specific embodiments thereof. However, numerous modifications which are contemplated as falling within the scope of the present invention should now be apparent to those skilled in the art. It is therefore intended that the scope of the present invention be limited only by the scope of the claims appended hereto. In addition, the order of presentation of the claims should not be construed to limit the scope of any particular term in the claims.