Two problem solving strategies, forward chaining and backward chaining, were compared to see how they affect students' learning of geometry theorem proving with construction. It has been claimed that backward chaining is inappropriate for novice students due to its complexity. On the other hand, forward chaining may not be appropriate either for this particular task because it can explode combinatorially. In order to determine which strategy accelerates learning the most, an intelligent tutoring system was developed. It is unique in two ways: (1) It has a fine grained cognitive model of proof-writing, which captured both observable and unobservable inference steps. This allows the tutor to provide elaborate scaffolding. (2) Depending on the student's competence, the tutor provides a variety of scaffolding from showing precise steps to just prompting students for a next step. In other words, the students could learn proof-writing through both worked-out examples (by observing a model of proof-writing generated by the tutor) and problem solving (by writing proofs by themselves). 52 students were randomly assigned to one of the tutoring systems. They solved 11 geometry proof problems with and without construction with the aid from the intelligent tutor. The results show that (1) the students who learned forward chaining showed better performance on proof-writing than those who learned backward chaining, (2) both forward and backward chaining conditions wrote wrong proofs equally frequently, (3) both forward and backward chaining conditions seldom wrote redundant or wrong statements when they wrote correct proofs, (4) the major reason for the difficulty in applying backward chaining lay in the assertion of premises as unjustified propositions (i.e., subgoaling). These results provide theoretical implications for the design of tutoring systems for problem solving.

A novel decision-theoretic architecture for intelligent tutoring systems, DT Tutor (DT), was fleshed out into a complete ITS and evaluated. DT uses a dynamic decision network to probabilistically look ahead to anticipate how its tutorial actions will influence the student and other aspects of the tutorial state. It weighs its preferences regarding multiple competing objectives by the probabilities that they will occur and then selects the tutorial action with maximum expected utility. The evaluation was conducted in two phases. First, logs were recorded from interactions of students with a Random Tutor (RT) that was identical to DT except that it selected randomly from relevant tutorial actions. The logs were used to learn many of DTs key probabilities for its model of the tutorial state. Second, the logs were replayed to record the actions that DT and a Fixed-Policy Tutor (FT) would select for a large sample of scenarios. FT was identical to DT except that it selected tutorial actions by emulating the fixed policies of Cognitive Tutors, which are theoretically based, widely used, and highly effective. The possible action selections for each scenario were rated by a panel of judges who were skilled human tutors. The main hypotheses tested were that DTs action selections would be rated higher than FTs and higher than RTs. This was the first comparison of a decision-theoretic tutor with a non-trivial competitor. DT was rated higher than FT overall and for all subsets of scenarios except help requests, for which it was rated equally. DT was also rated much higher than RT. The judges preferred that the tutors provide proactive help and the study design permitted this information to be put to use right away to develop and evaluate enhanced versions of DT and FT. The enhanced versions of DT and FT were rated about equally and higher than non-enhanced DT except on help requests. The variability of the actions selected by both non-enhanced and enhanced versions of DT demonstrated more sensitivity to the tutorial state than the actions selected by non-enhanced and enhanced versions of FT.

The rapid advance of distance learning and networking technology has enabled universities and corporations to reach out and educate students across time and space barriers. This technology supports structured, on-line learning activities, and provides facilities for assessment and collaboration. Structured collaboration, in the classroom, has proven itself a successful and uniquely powerful learning method. Online collaborative learners, however, do not enjoy the same benefits as face-to-face learners because the technology provides no guidance or direction during online discussion sessions. Integrating intelligent facilitation agents into collaborative distance learning environments may help bring the benefits of the supportive classroom closer to distance learners. In this dissertation, I describe a new approach to analyzing and supporting online peer interaction. The approach applies Hidden Markov Models, and Multidimensional Scaling with a threshold-based clustering method, to analyze and assess sequences of coded on-line student interaction. These analysis techniques were used to train a system to dynamically recognize when and why students may be experiencing breakdowns while sharing knowledge and learning from each other. I focus on knowledge sharing interaction because students bring a great deal of specialized knowledge and experiences to the group, and how they share and assimilate this knowledge shapes the collaboration and learning processes. The results of this research could be used to dynamically inform and assist an intelligent instructional agent in facilitating knowledge sharing interaction, and helping to improve the quality of online learning interaction.

This thesis raises objections to the use of causal reasoning with equilibrium models. I consider two operators that are used to transform models: the {em Do} operator for modeling manipulation and the {em Equilibration} operator for modeling a system that has achieved equilibrium. I introduce a property of a causal model called the {em EMC Property} that is true iff the {em Do} operator commutes with the {em Equilibration} operator. I prove that not all models obey the EMC property, and I demonstrate empirically that when inferring a causal model from data, the learned model will not support causal reasoning if the EMC property is not obeyed. I find sufficient conditions for models to violate and not to violate the EMC property. In addition, I show that there exists a class of models that violate EMC and possess a set of variables whose manipulation will cause an instability in the system. All dynamic models in this class possess feedback, although I do not prove that feedback is a necessary or a sufficient condition for EMC violation. I define the {em Structural Stability Principle} which provides a necessary graphical criterion for stability in causal models. I will argue that the models in this class are quite common given typical assumptions about causal relations.

This dissertation studies how the mechanism-based view of causality can assist in construction and utilization of causal models for decision support. The mechanism-based view of causality is based on the theory of causal ordering, proposed by Simon [53], which explicates causal asymmetries among variables in a self-contained set of simultaneous structural equations. I extend the theory of causal ordering to explicate causal relations in under-constrained sets of structural equations. Considering under constrained models as intermediate representations of one's understanding of decision problems, I demonstrate that a model construction process can be viewed as the process of assembling mechanisms from under-constrained models into self-contained causal models. I formalize the reversibility property of a mechanism to support changes in structure in causal models containing reversible mechanisms. I introduce algorithms for deliberating atomic actions when one considers manipulating a variable or releasing a mechanism to achieve a decision objective. In addition, I introduce the concept of search for opportunities which amounts to both identifying the set of policy variables and computing their optimal setting for a decision objective. Search for opportunities presents decision makers with a list of ranked interventions based on the value of intervention computation. I implement an interactive system called ImaGeNIe that supports mechanism-based model construction and utilization. I conduct subject experiments and find that ImaGeNIe can effectively assist users in constructing causal models for causal reasoning.

This work introduces the Bayesian local causal discovery framework, a method for discovering unconfounded causal relationships from observational data. It addresses the hypothesis that causal discovery using local search methods will outperform causal discovery algorithms that employ global search in the context of large datasets and limited computational resources. Several Bayesian local causal discovery (BLCD) algorithms are described and results presented comparing them with two well-known global causal discovery algorithms PC and FCI, and a global Bayesian network learning algorithm, the optimal reinsertion (OR) algorithm which was post-processed to identify relationships that under assumptions are causal. Methodologically, this research formalizes the task of causal discovery from observational data using a Bayesian approach and local search. It specifically investigates the so called Y structure in causal discovery and classifies the various types of Y structures present in the data generating networks. It identifies the Y structures in the Alarm, Hailfinder, Barley, Pathfinder and Munin networks and categorizes them. A proof of the convergence of the BLCD algorithm based on the identification of Y structures, is also provided. Principled methods of combining global and local causal discovery algorithms to improve upon the performance of the individual algorithms are discussed. In particular, a post-processing method for identifying plausible causal relationships from the output of global Bayesian network learning algorithms is described, thereby extending them to be causal discovery algorithms. In an experimental evaluation, simulated data from synthetic causal Bayesian networks representing five different domains, as well as a real-world medical dataset, were used. Causal discovery performance was measured using precision and recall. Sometimes the local methods performed better than the global methods, and sometimes they did not (both in terms of precision/recall and in terms of computation time). When all the datasets were considered in aggregate, the local methods (BLCD and BLCDpk) had higher precision. The general performance of the BLCD class of algorithms was comparable to the global search algorithms, implying that the local search algorithms will have good performance on very large datasets when the global methods fail to scale up. The limitations of this research and directions for future research are also discussed.

Bayesian networks (BNs) offer a compact, intuitive, and efficient graphical representation of uncertain relationships among the variables in a domain and have proven their value in many disciplines over the last two decades. However, two challenges become increasingly critical in practical applications of Bayesian networks. First, real models are reaching the size of hundreds or even thousands of nodes. Second, some decision problems are more naturally represented by hybrid models which contain mixtures of discrete and continuous variables and may represent linear or nonlinear equations and arbitrary probability distributions. Both challenges make building Bayesian network models and reasoning with them more and more difficult. In this dissertation, I address the challenges by developing representational and computational solutions based on importance sampling. I First develop a more solid understanding of the properties of importance sampling in the context of Bayesian networks. Then, I address a fundamental question of importance sampling in Bayesian networks, the representation of the importance function. I derive an exact representation for the optimal importance function and propose an approximation strategy for the representation when it is too complex. Based on these theoretical analysis, I propose a suite of importance sampling-based algorithms for (hybrid) Bayesian networks. I believe the new algorithms significantly extend the efficiency, applicability, and scalability of approximate inference methods for Bayesian networks. The ultimate goal of this research is to help users to solve difficult reasoning problems emerging from complex decision problems in the most general settings.

This study compared the relative utility of an intelligent tutoring system that uses procedure-based hints to a version that uses worked-out examples. The system, Andes, taught college level physics. In order to test which strategy produced better gains in competence, two versions of Andes were used: one offered participants graded hints and the other offered annotated, worked-out examples in response to their help requests. We found that providing examples was at least as effective as the hint sequences and was more efficient in terms of the number of problems it took to obtain the same level of mastery.

Efficient representations and solutions for large structured decision problems with continuous and discrete variables are among the important challenges faced by the designers of automated decision support systems. In this work, we describe a novel hybrid factored Markov decision process (MDP) model that allows for a compact representation of these problems, and a hybrid approximate linear programming (HALP) framework that permits their efficient solutions. The central idea of HALP is to approximate the optimal value function of an MDP by a linear combination of basis functions and optimize its weights by linear programming. We study both theoretical and practical aspects of this approach, and demonstrate its scale-up potential on several hybrid optimization problems.

As a compact graphical framework for representation of multivariate probability distributions, Bayesian networks are widely used for efficient reasoning under uncertainty in a variety of applications, from medical diagnosis to computer troubleshooting and airplane fault isolation. However, construction of Bayesian networks is often considered the main difficulty when applying this framework to real-world problems. In real world domains, Bayesian networks are often built by knowledge engineering approach. Unfortunately, eliciting knowledge from domain experts is a very time-consuming process, and could result in poor-quality graphical models when not performed carefully. Over the last decade, the research focus is shifting more towards learning Bayesian networks from data, especially with increasing volumes of data available in various applications, such as biomedical, internet, and e-business, among others. Aiming at solving the bottle-neck problem of building Bayesian network models, this research work focuses on elicitation, evaluation and learning Bayesian networks. Specifically, the contribution of this dissertation involves the research in the following five areas: a) graphical user interface tools for efficient elicitation and navigation of probability distributions, b) systematic and objective evaluation of elicitation schemes for probabilistic models, c) valid evaluation of performance robustness, i.e., sensitivity, of Bayesian networks, d) the sensitivity inequivalent characteristic of Markov equivalent networks, and the appropriateness of using sensitivity for model selection in learning Bayesian networks, e) selective refinement for learning probability parameters of Bayesian networks from limited data with availability of expert knowledge. In addition, an efficient algorithm for fast sensitivity analysis is developed based on relevance reasoning technique. The implemented algorithm runs very fast and makes d) and e) more affordable for real domain practice.