FlexSCAPE: Data Driven Hypothesis Testing and Generation System

• US 20110231356A1
• Filed: 07/01/2010
• Published: 09/22/2011
• Est. Priority Date: 07/01/2009
• Status: Abandoned Application

• Current Assignee: Quantum Leap Research, Inc.
• Original Assignee: Quantum Leap Research, Inc.
• Inventors: Askren, Jay Dee, Thomas, Mani, Jean, Eric N., Wang, Jijun, Faulkner, Eli T., Hample, David Louis, Vaidyanathan, Akhileswar Ganesh, Boehmler, Albert Josef, McGowan, Michael Thomas, Frazer, Durban A.
• Application Number:
  US12/829,241
• Publication Number:
  US 20110231356A1
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

The present invention relates to a method for generating hypotheses automatically from graphical models built directly from data. The method of the present invention links three key scientific concepts to enable hypothesis generation from data driven hypothesis-models: including the use of information theory based measures to identify informative feature subsets within the data; the automatic generation of graphical models from the informative data subsets identified from step one; and the application of optimization methods to graphical models to enable hypothesis generation. The integration of these three concepts can enable scalable approaches to hypothesis generation from large, complex data environments. The use of graphical models as the model representation can allow prior knowledge to be effectively integrated into the modeling environment.

Claims

1. In a computer system, having one or more processors or virtual machines, each processor comprising at least one core, one or more memory units, one or more input devices and one or more output devices, optionally a network, and optionally shared memory supporting communication among the processors, a method for automatically generating and testing a hypothesis from a data set comprising the steps of:

(a) selecting at least one informative combination of interacting features from a data set from the one or more memory units using a mutual information measure of the feature combination as the evaluation criterion;

(b) building at least one graphical model from at least one informative combination of interacting features;

(c) generating a hypothesis from at least one graphical model by optimizing a statistical measure associated with at least one state of at least one feature wherein the hypothesis is defined by at least one state associated with at least one feature from the data set; and

(d) testing at least one hypothesis generated from substep (c) from at least one graphical model.

2. The method of claim 1 wherein the mutual information measure in step (a) is at least one selected from the group consisting of:

mutual information, conditional mutual information, multi-variate mutual information, absolute mutual information and normalized mutual information.

3. The method of claim 1 wherein the graphical model in step (b) is at least one selected from the group consisting of:

any graphical model representing probabilistic relationships, a Bayesian network, a Naï

ve Bayesian network, a directed acyclic graph, a graphical Gaussian model, a Markov network, Partially Observable Markov Decision Process model, a Hidden Markov model, and a partially observable Markov decision process.

4. The method of claim 1 wherein the building at least one graphical model in step (b) can be performed by learning the model from the data.

5. The method of claim 1 wherein the building at least one graphical model in step (b) can be performed manually.

6. The method of claim 1 wherein the optimization method in step (c) is at least one selected from the group consisting of:

active set methods, ant colony optimization, arc-consistency enforcement, A-star, barrier functions, Boolean satisfiability, breadth-first search, Broyden-Fletcher-Goldfarb-Shannon algorithm, concave programming, cone programming, constraint ordering, constraint propagation, constraint sampling, differential evolution, direct search methods, evolutionary algorithms, exhaustive enumeration, expectation maximization, general conjugate-directional methods, generalized reduced gradient, generate and test, genetic algorithms, grid-wise enumeration, hardest-constraint-first, heuristic unidirectional minimization, heuristic uni-variate, integer programming, iterative repair algorithms, iterative-deepening-a-star, linear programming, mixed integer programming, model reduction, model partitioning, multivariate search, Nelder-Mead algorithm, node-consistency enforcement, particle swarm optimization, path-consistency enforcement, penalty functions, Polak-Ribiere algorithm, primal/dual linear programming, pseudo-Boltzmann search, pure random sampling, quadratic programming, quasi-Newton methods, relaxation techniques, semi-definite optimization, depth-first search, sequential linear programming, sequential quadratic programming, sequential uni-variate search, simple adaptive statistical search, simulated annealing, tabu search, trust region methods, uni-variate search, variable ordering, and zoomed enumeration.

7. The method of claim 1 wherein the statistical measure in step (c) is at least one selected from the group consisting of:

posterior probability, likelihood, and generalized Bayes factor.

8. The method of claim 1 wherein the hypothesis generation in step (c) can occur with at least one feature in a defined state.

9. The method of claim 1 wherein the testing of a hypothesis in step (d) can be performed using an inference technique on the graphical model.

10. The method of claim 1 wherein the graphical model in step (b) can be a dynamical graphical model that encodes a temporal component.

11. The method of claim 1 wherein the step of selecting at least one informative combination of features from the data set in step (a) for a temporal data set further comprises the step of:

expanding each feature at a reference time point into a list of (feature, time offset) feature pairs wherein each (feature, time offset) feature pair encodes a feature state at a particular time offset from the reference time point.

12. The method of claim 11 wherein the time offset can refer to a time earlier than the reference time point.

13. The method of claim 11 wherein the time offset can refer to a time later than the reference time point.

14. The method of claim 1 wherein the step of building a graphical model in step (b) for the case of a dynamical graphical model further comprises the steps of:

(a) Sorting the (feature, time offset) feature pairs such that the earlier time offsets occur before the later time offsets in the sorted list; and

(b) Building a graphical model that preserves the temporal order in the sorted list.

15. The method of claim 1 wherein the data set can be derived from a database environment.

16. The method of claim 1 wherein the data set can be derived from a streaming data environment.

17. The method of claim 1 wherein the data set can be derived from a simulation environment.

18. The method of claim 1 wherein the testing of a hypothesis in step (d) can be used to forecast future behavior of at least one financial market as a basis for developing a trading strategy.

19. The method of claim 1 wherein the step of generating a hypothesis in step (c) can be used to identify an optimal health treatment strategy for a patient.

20. The method of claim 1 wherein the step of generating a hypothesis in step (c) can be used to identify an optimal manufacturing process control strategy.