Methods for discovering causal knowledge from observational data have been a persistent topic of AI research for several decades. Essentially all of this work focuses on knowledge representations for propositional domains. In this paper, we present several key algorithmic and theoretical innovations that extend causal discovery to relational domains. We provide strong evidence that effective learning of causal models is enhanced by relational representations. We present an algorithm, relational PC, that learns causal dependencies in a state-of-the-art relational representation, and we identify the key representational and algorithmic innovations that make the algorithm possible. Finally, we prove the algorithm's theoretical correctness and demonstrate its effectiveness on synthetic and real data sets.

Researchers in the social and behavioral sciences routinely rely on quasi-experimental designs to discover knowledge from large data-bases. Quasi-experimental designs (QEDs) exploit fortuitous circumstances in non-experimental data to identify situations (sometimes called "natural experiments") that provide the equivalent of experimental control and randomization. QEDs allow researchers in domains as diverse as sociology, medicine, and marketing to draw reliable inferences about causal dependencies from non-experimental data. Unfortunately, identifying and exploiting QEDs has remained a painstaking manual activity, requiring researchers to scour available databases and apply substantial knowledge of statistics. However, recent advances in the expressiveness of databases, and increases in their size and complexity, provide the necessary conditions to automatically identify QEDs. In this paper, we describe the first system to discover knowledge by applying quasi-experimental designs that were identified automatically. We demonstrate that QEDs can be identified in a traditional database schema and that such identification requires only a small number of extensions to that schema, knowledge about quasi-experimental design encoded in first-order logic, and a theorem-proving engine. We describe several key innovations necessary to enable this system, including methods for automatically constructing appropriate experimental units and for creating aggregate variables on those units. We show that applying the resulting designs can identify important causal dependencies in real domains, and we provide examples from academic publishing, movie making and marketing, and peer-production systems. Finally, we discuss the integration of QEDs with other approaches to causal discovery, including joint modeling and directed experimentation.

Commercial datasets are often large, relational, and dynamic. They contain many records of people, places, things, events and their interactions over time. Such datasets are rarely structured appropriately for knowledge discovery, and they often contain variables whose meanings change across different subsets of the data. We describe how these challenges were addressed in a collaborative analysis project undertaken by the University of Massachusetts Amherst and the National Association of Securities Dealers(NASD). We describe several methods for data pre-processing that we applied to transform a large, dynamic, and relational dataset describing nearly the entirety of the U.S. securities industry, and we show how these methods made the dataset suitable for learning statistical relational models. To better utilize social structure, we first applied known consolidation and link formation techniques to associate individuals with branch office locations. In addition, we developed an innovative technique to infer professional associations by exploiting dynamic employment histories. Finally, we applied normalization techniques to create a suitable class label that adjusts for spatial, temporal, and other heterogeneity within the data. We show how these pre-processing techniques combine to provide the necessary foundation for learning high-performing statistical models of fraudulent activity.

The term formal method refers to the use of techniques from formal logic and discrete math in the specification, design, and construction of computer systems and software. These techniques enable the formalization of software for development and testing so that it may be verified and validated in a more thorough way. Although not specifically identified in the literature as a verification and validation (V&V) formal method technique, neural network rule extraction fits the basic definition by using techniques from formal logic to formalize neural network software so that it may be examined more completely. This paper identifies several areas where rule extraction can be an effective tool for the V&V of neural networks.

Automated generation of test cases is a prerequisite for fast testing. Whereas the research in automated test data generation addressed the creation of individual test points, test trajectory generation has attracted limited attention. In simple terms, a test trajectory is defined as a series of data points, with each (possibly multidimensional) point relying upon the value(s) of previous point(s). Many embedded systems use data trajectories as inputs, including closed-loop process controllers, robotic manipulators, nuclear monitoring systems, and flight control systems. For these systems, testers can either handcraft test trajectories, use input trajectories from older versions of the system or, perhaps, collect test data in a high fidelity system simulator. While these are valid approaches, they are expensive and time-consuming, especially if the assessment goals require many tests. We developed a framework for expanding a small, conventionally developed set of test trajectories into a large set suitable, for example, for system safety assurance. Statistical regression is the core of this framework. The regression analysis builds a relationship between controllable independent variables and closely correlated dependent variables, which represent test trajectories. By perturbing the independent variables, new test trajectories are generated automatically. Our approach has been applied in the safety assessment of a fault tolerant flight control system. Linear regression, multiple linear regression, and autoregressive techniques are compared. The performance metrics include the speed of test generation and the percentage of "acceptable" trajectories, measured by the domain specific reasonableness checks.

Automated generation of test cases is a prerequisite for fast testing. Whereas the research has addressed the creation of individual test points, test trajectory generation has attracted limited attention. In simple terms, a test trajectory is defined as a series of data points, with each (possibly multidimensional) point relying upon the value(s) of previous point(s). Software systems that use data trajectories as inputs include closed-loop process controllers. For these systems, software testers can either handcraft test trajectories, use input trajectories from older versions of the system or, perhaps, collect test data in a high fidelity system simulator. While these are valid approaches, they are expensive and time-consuming, especially if the assessment goals require substantial number of tests. We propose a framework for expanding a small, conventionally developed set of test trajectories into a large set suitable, for example, for system safety assurance. In the core of this framework is statistical regression analysis. The regression analysis builds a relationship between controllable independent variables and closely correlated dependent variables, which represent test trajectories. By perturbing the independent variables, new test trajectories can be generated automatically. Automated test trajectory generation has been applied in the safety assessment of a fault tolerant flight control system. We compare the performance of simple linear regression, multiple linear regression and autoregressive techniques.