The projected research is aimed at enhancing the practicability of decision making under uncertainty and thereby advance its application in modern decision-support systems.
Recent advances in decision making under uncertainty have resulted in various powerful formalisms for representing uncertainty and for capturing decision problems. International research efforts focus on the Bayesian belief-network and influence-diagram formalisms. As these formalisms are central to the current research proposal, they are briefly reviewed.
A Bayesian belief network is a concise representation of a joint probability distribution on a set of statistical variables, consisting of a directed acyclic graph and an associated set of probabilities. Each node in a belief network's digraph represents a statistical variable. The arcs represent the influential relationships among the represented variables. Absence of an arc between two variables means that these variables do not influence each other directly and, hence, are (conditionally) independent. Since the influential relationships among the statistical variables typically are probabilistic in nature, several conditional probabilities are associated with the network's digraph to capture the strengths of these relationships. For each variable, the probabilities of its values are specified, conditional upon the various possible combinations of values for its immediate predecessors in the digraph. These probabilities with each other suffice to uniquely define a joint probability distribution that respects the independences that are portrayed by the network's digraph. A Bayesian belief network thus enables the computation of any probability of interest that pertains to its variables.
The formalism of influence diagrams is tailored to the representation of decision problems. It provides for capturing the various possible decisions that are at a decision maker's disposal and the desirability of the uncertain consequences of these decisions, in addition to a joint probability distribution on the set of statistical variables involved. An influence diagram, like a Bayesian belief network, consists of a directed acyclic graph and an associated set of numbers. The digraph includes three different types of node, modeling variables with different roles in the represented decision problem. The nodes represent statistical variables, decision variables, that is, variables that represent the various decision alternatives that are at a decision maker's disposal, and variables that capture the desirability of the consequences that may arise from decision sequences. The numerical part of an influence diagram associates a set of conditional probabilities with each statistical variable; in addition, it specifies for each scenario composed of a decision sequence and a combination of possible consequences, a utility expressing the desirability of the scenario to the decision maker. An influence diagram uniquely represents a decision problem. A solution to the represented problem is a sequence of decisions that maximises expected desirability of consequences.
The various formalisms for representing uncertainty and for structuring decision problems have a firm mathematical basis in statistics and decision theory, and allow for explicitly capturing knowledge and experience from domain experts. In the sequel, the phrase decision-theoretic network will be used when referring to Bayesian belief networks, influence diagrams, and other graphical representations of domain knowledge that are tailored to problems in which uncertainty is predominant.
The use of decision-theoretic networks in real-life decision-support systems requires suitable algorithms for reasoning. Over the last decennium, various algorithms have been developed for computing probabilities of interest and for computing optimal decisions from a decision-theoretic network. These algorithms have a worst-case complexity that is exponential in the number of variables involved. As the problem of probabilistic inference is already known to be NP-hard, it is not expected that polynomial reasoning algorithms will be found. The runtime complexity of the algorithms is determined to a large extent by the topological properties of a network's digraph: informally speaking, the sparser the digraph, the more efficient the various algorithms behave. Experience shows that reasoning with a decision-theoretic network is quite practicable for up to one hundred variables, but for larger networks quickly becomes infeasible. The computational complexity of reasoning has been an important research theme ever since the introduction of decision-theoretic networks.
For several years, research in the field of decision making under uncertainty has focused on the development of powerful formalisms and on the design of associated algorithms. Only recently has attention been extended to include the application of decision-theoretic networks in real-life problem domains. Decision-theoretic networks are currently being developed for various different problems. Most notably, applications are being realised in the medical domain, and concern diagnosis, prognostic assessment, and treatment planning. For example, decision-theoretic networks have been developed for the diagnosis of breast cancer, for prognosis of congenital heart disease, and for patient-specific insulin adjustment.
Decision-theoretic networks are most suitable for addressing problems in domains that are scientific in nature. Their application is not restricted to the medical domain. Other potential applications are weather forecasting, simulating the effects of climatological changes, and predicting prices on the stock market. As experience with decision-theoretic networks in real-life application domains is beginning to grow, evidence is building up that these networks tend to outperform more traditional statistical models because they allow for capturing more knowledge subtleties from a domain than statistical models generally do; moreover, decision-theoretic networks tend to outperform classical expert systems as a consequence of their firm mathematical basis. To further advance their application, however, methodologies and techniques for constructing decision-theoretic networks and for using them in a decision-support context are called for.
The field of decision making under uncertainty has attracted a thriving research community. The United States of America host large research groups at many universities, ranging from the University of California, Los Angeles, to Carnegie Mellon University, Pittsburgh. Also, various private companies, ranging from Microsoft to Knowledge Industries, have research groups addressing decision making under uncertainty. The largest research group in the field in Europe is the renowned decision-support systems group at Aalborg University, Denmark. Other, smaller groups in Europe are located, for example, in the United Kingdom, in Spain, and in the Netherlands; among these, the Dutch group, hosted by Utrecht University, is one of the smallest. Publications in the field are found in statistics, decision-theoretic, and computer-science conferences and journals. The well-known specialist conference on Uncertainty in Artificial Intelligence, with proceedings published by Morgan Kaufmann publishers, has an internationally acknowledged high standard.
In the following sections, the current research by the applicant as well as the projected research are summarised for each of the three themes.
To provide for evaluating research results and as a source for further inspiration, a small number of projects in which decision-theoretic networks are constructed for different types of problem will be undertaken.
A decision-theoretic network for a real-life problem is usually constructed with the help of one or more domain experts. For this non-trivial task hardly any supporting methodologies or techniques are available. Experience shows that, although it may require considerable effort, constructing the digraph of a decision-theoretic network is quite doable. In fact, as it has parallels to designing a domain model for a more traditional knowledge-based system, to some extent well-known knowledge-engineering techniques can be employed. Assessing all conditional probabilities and utilities required, unfortunately, often turns out to be a far harder task, not in the least because it tends to be much more time-consuming.
Although for most application domains abundant probabilistic information is available from literature or from statistical data, this information is seldom directly amenable to encoding in a decision-theoretic network. The majority of the probabilities required will therefore have to be assessed by domain experts. The problems encountered upon eliciting judgemental probabilities from experts are widely known; an expert's assessments may reflect various biases and may not be properly calibrated. Although in the field of decision analysis various elicitation techniques have been designed to avert these problems to at least some extent, the large number of probabilities that are typically required for a decision-theoretic network prohibits the use of these rather time-consuming techniques. The assessment of utilities is usually found to be an even harder task than probability assessment. Often, utilities have to be associated with scenarios with which the assessor is not acquainted. Moreover, evaluating the calibration of utility assessments is very difficult. To support acquisition of probabilities and utilities for decision-theoretic networks, supplementary techniques are required that allow for the elicitation of thousands of numbers in reasonable time.
Research by the applicant, jointly with her two Ph.D. students, so far has resulted in a procedure for probability acquisition for Bayesian belief networks. The procedure builds upon the idea of stepwise refinement. It sets out with the elicitation of initial, probably highly inaccurate, assessments for all conditional probabilities required for a network under construction. For this purpose, a new elicitation method has been designed, jointly with a senior researcher from the Psychological Laboratory of Utrecht University, that exploits the ideas of presenting conditional probabilities as fragments of text and of providing a scale for marking assessments with both numerical and verbal anchors. Starting with thus obtained initial assessments, a sensitivity analysis of the belief network under construction is performed to yield insight into the possible effects of the inaccuracies involved. The basic idea is to systematically vary every single assessment over a plausible interval and study the effects on the network's output. Some conditional probabilities are likely to show a considerable impact, while others will hardly reveal any influence. For the less influential probabilities, the initial assessments may suffice. For the more influential ones, however, refinement may be worthwhile. To obtain a more accurate assessment for these probabilities, elaborate elicitation techniques can be employed. Iteratively performing sensitivity analyses and refining probability assessments is pursued until satisfactory behaviour of the network is obtained, or until the costs of further elicitation outweigh the benefits of higher accuracy or until higher accuracy can no longer be attained due to lack of knowledge.
When performed straightforwardly, sensitivity analysis of a Bayesian belief network requires too much computational effort to be of any practical use. The applicant, with one of her Ph.D. students, has shown that the computational burden involved can be reduced considerably by exploiting the probabilistic relationships among the variables that are represented in a belief network. These relationships allow for distinguishing between conditional probabilities that may influence the network's output and those that cannot. In addition, these relationships induce simple mathematical functions describing the network's output as a fraction of two linear functions in a conditional probability under study. Based upon these properties, an efficient algorithm for sensitivity analysis has been designed. The significance of an efficient algorithm for sensitivity analysis of Bayesian belief networks has been internationally acknowledged; the algorithm is currently being incorporated in the well-known commercially available HUGIN shell.
For the next five years, the applicant proposes to pursue and extend current research concerning methodologies and techniques for supporting the construction of decision-theoretic networks with domain experts. Although some further work will be done on the design of methods for probability and utility assessment, the focus of the projected research will be on techniques for investigating robustness of a network's output:
Key publications addressing the construction of decision-theoretic networks with domain experts are:
Constructing a Bayesian belief network for a real-life problem with the help of domain experts is a non-trivial and time-consuming task. For various application domains, data that have been collected and maintained over numerous years of every-day problem solving constitute an additional source of information that can be exploited for a network's construction. Such data contains highly valuable information about the statistical variables in the domain under study and the relationships among them, be it implicitly. The basic idea is to distill this information from the data and exploit it for constructing a network's digraph and subsequently assessing the conditional probabilities required. Constructing Bayesian belief networks from data as a research theme is receiving considerable attention in the field of decision making under uncertainty, taking major contributions from statistics.
The applicant has not been actively involved in research pertaining to the construction of Bayesian belief networks from data so far, that is, otherwise than through one Ph.D. student and various M.Sc. projects. Application-oriented projects with M.Sc. students have revealed that, upon constructing a Bayesian belief network from real-life data with existing techniques, a network results that, although closely fitting the data, may not properly reflect domain knowledge. Domain experts have been found hesitant to use such networks in practice.
Based upon her experience with constructing decision-theoretic networks with domain experts, the applicant acknowledges that, for advancing their application in modern decision-support systems, algorithms for automated construction are indispensable. She therefore proposes to initiate research on the design of methodologies and techniques for constructing decision-theoretic networks from data. More specifically, she proposes for the next five years to focus research attention on:
Key publications addressing the construction of Bayesian belief networks from data are:
The construction of a decision-theoretic network for a real-life problem with the help of domain experts typically sets out with the construction of the network's digraph. As the assessment of the probabilities and utilities required is a far harder task, it is performed only when the digraph is considered robust. The resulting decision-theoretic network is evaluated extensively with the experts involved and using available real-life data. Upon such an evaluation, not seldom new insights are gained in the domain experts' problem-solving behaviour that lead to adaptations of the network's digraph; consequently, often new probability and utility assessments are required. Methodologies and techniques that provide for studying a decision-theoretic network's reasoning behaviour prior to the assessment of probabilities and utilities currently are not available.
Current research of the applicant focuses on the design of methodologies and techniques for studying reasoning behaviour of a decision-theoretic network without numbers. As the formalism of qualitative probabilistic networks is central to this research, it is briefly reviewed.
Qualitative probabilistic networks have been introduced in the early 1990s as qualitative abstractions of Bayesian belief networks, to circumvent the need of probability assessment. Like a Bayesian belief network, a qualitative probabilistic network encodes statistical variables and the probabilistic relationships among them in a directed acyclic graph. The relationships between the variables are described by qualitative signs rather than by conditional probabilities. Associated with an arc, such a sign indicates the direction of shift in the probability distribution for the variable at the head of the arc induced by a shift in the distribution for the variable at the arc's tail. Reasoning with a qualitative probabilistic network amounts to computing signs for nodes of interest and requires much less computational effort than reasoning with a fully quantified network. For computing signs from a qualitative network, an elegant algorithm is available that has a worst-case complexity that is polynomial in the number of variables involved.
Qualitative probabilistic networks summarise the relationships among their variables by qualitative signs without any indication of strength and as a consequence have less expressive power than their numerical counterparts. They do not provide for modelling the intricacies involved in weighing conflicting influences and, hence, do not provide for resolving trade-offs. Reasoning with a qualitative probabilistic network for a real-life application, therefore, quite often leads to non-conclusive results. Considered a major drawback, this property generally prohibits application of qualitative probabilistic networks in real-life problem domains.
Research by the applicant, with one of her Ph.D. students, so far has focused on the formalism of qualitative probabilistic networks and has resulted in two enhancements, to provide for trade-off resolution and to allow for qualitative decision making.
Non-conclusive results in reasoning with a qualitative probabilistic network can be averted to at least some extent by providing for a finer level of representation detail. Building upon this observation, an enhanced qualitative-network formalism has been designed that provides for distinguishing between strong and weak influences among variables. Trade-off resolution is based upon the idea that strong influences dominate over conflicting weak influences. Associated with the enhanced formalism, an efficient reasoning algorithm has been designed.
Qualitative influence diagrams have been introduced as qualitative abstractions of influence diagrams to provide for qualitative decision making. A qualitative influence diagram, like its numerical counterpart, comprises a directed acyclic graph encoding the influential relationships among the variables involved in a decision problem. Instead of conditional probabilities, qualitative signs are specified indicating influences on probability; instead of utilities, a qualitative influence diagram specifies signs that capture influences on utility. Reasoning with a qualitative diagram amounts to computing signs for decision variables that indicate how a shift in choice of decision influences expected utility. An efficient algorithm has been designed for this purpose.
For the next five years, the applicant proposes to pursue and extend current research concerning qualitative networks and their use in studying reasoning behaviour of decision-theoretic networks:
Key publications addressing qualitative probabilistic networks are:
For several years, research in the field of decision making under uncertainty has focused on the design of powerful formalisms and associated algorithms. Only recently has attention been extended to include the development of decision-theoretic networks for real-life problems. While experience is increasing, it is becoming more and more evident that constructing a decision-theoretic network for a complex real-life problem is a non-trivial and time-consuming task; simultaneously, evidence is building up that these networks have the potential to advance the quality of modern decision support.
Since halfway through the 1990s, the applicant has been actively involved in the construction of a large influence diagram for a complex medical decision problem in oncology with experts from the Netherlands Cancer Institute.
The Antoni van Leeuwenhoekhuis, hosting the Netherlands Cancer Institute, is specialised in the treatment of cancer patients. In the hospital, some hundred patients yearly receive treatment for oesophageal carcinoma. These patients currently are assigned to a therapy by means of a standard protocol, involving a small number of variables. Based upon this protocol, 80% of the patients show a more or less favourable response to the therapy instilled. In the context of a larger project aimed at the development of a more fine-grained protocol with a higher favourable response rate, an influence diagram is being developed for patient-specific therapy selection for oesophageal carcinoma. The diagram is destined for use in the Antoni van Leeuwenhoekhuis.
While establishing the presence of an oesophageal carcinoma in a patient is relatively easy, the selection of an appropriate therapy is a far harder task. In the Antoni van Leeuwenhoekhuis, various different therapeutic alternatives are available, ranging from surgical removal of the oesophagus to radiotherapy and positioning of a prosthesis. The effects aimed at by instilling a therapy include removal or reduction of the patient's primary tumour and an improved passage of food through the oesophagus. The therapeutic alternatives available differ in the extent to which these effects can be attained. Instillation of a therapy further is expected to be accompanied not just by beneficial effects but also by various complications; these complications can be very serious and may even lead to death. The effects and complications to be expected from the various therapeutic alternatives depend on the characteristics of a patient's carcinoma, on the depth of invasion of the primary tumour into the oesophageal wall and neighbouring structures, and on the extent of the carcinoma's metastases. The possible effects and complications require careful balancing before a therapy is decided upon.
The oesophagus influence diagram currently includes over seventy statistical variables. Of these, some forty variables pertain to the characteristics of an oesophageal carcinoma, to the depth of invasion, and to the extent of metastases; these variables with each other provide for assessment of the stage of the cancer. The remaining variables model the possible effects and complications of the various therapies available. For the diagram, several thousands of probabilities have been elicited from two experts in oncology. The assessment of the utilities required is not completed as yet; a research fund application for studying and eliciting patient preferences is under review at ZON. The oesophagus influence diagram currently is one of the larger real-life decision-theoretic networks under study.
Recently, the applicant has initiated a joint research project with the Netherlands Institute for the Study of Criminality and Law Enforcement, financially supported by TNO. In this project, a decision-theoretic network will be developed for predicting relocation of vandalism and violence upon police management decisions.
The development of an influence diagram for a complex real-life medical problem over the years has inspired much of the applicant's current research focused on the design of methodologies and techniques for constructing decision-theoretic networks with domain experts. To advance their application in modern decision-support systems, more experience with building decision-theoretic networks for various types of domain need be acquired. For the next five years, the applicant therefore will emphasise development of real-life applications:
To the knowledge of the applicant, hardly any publications are available that discuss extensively evaluated decision-theoretic networks for real-life problems. Various publications, however, discuss initial results from ongoing research.
A Bayesian belief network is generally used for probabilistic inference, that is, for computing probabilities pertaining to its variables. Several different algorithms have been designed for this purpose. These algorithms typically build upon a supporting architecture. The most well-known of these algorithms builds upon a tree of cliques that is constructed from a belief network's digraph after triangulation. Another basic algorithm builds upon a cutset of vertices that serves to break the loops in the digraph. The different underlying architectures give rise to different complexity properties of the two algorithms: while the latter algorithm is exponential in the number of vertices in the loop cutset employed, the computational complexity of the former algorithm relates exponentially to the numbers of vertices in the cliques in the clique tree used in inference. The problems of finding for a Bayesian belief network an optimal tree of cliques or an optimal loop cutset are known to be NP-hard. Heuristic algorithms have been designed to compute supporting architectures that are expected to be `good'. The problem of probabilistic inference in a belief network without any topological restrictions in itself is also known to be NP-hard. Similar complexity considerations hold with regard to decision-theoretic networks in general.
Experience with decision-theoretic networks in various different problem domains is beginning to reveal that, while the basic reasoning algorithms perform well for networks with up to one hundred variables, they do not scale up to networks with several hundreds of variables. To extend the range of decision-theoretic networks in which reasoning is feasible, more efficient algorithms are called for.
The applicant has recently begun to focus attention on the issue of complexity for the various algorithms available for reasoning with a Bayesian belief network. The main purpose of these research efforts is to arrive at more efficient algorithms.
By comparing the underlying architectures, the worst-case complexity of the two basic algorithms for probabilistic inference with a Bayesian belief network have been studied. Jointly with a senior researcher in the field of graph algorithms from the Department of Computer Science of Utrecht University, it has been shown that the clique-tree algorithm has at most the same computational complexity as the algorithm that builds upon a loop cutset for a network's digraph. This result acknowledges the former to be the most viable algorithm at present.
An initial investigation of the runtime complexity of the loop-cutset algorithm has resulted in the design of a method for dynamically reducing the digraph of a Bayesian belief network. During reasoning with a belief network, evidence is entered and processed, providing additional information about the represented joint probability distribution in a specific context. In particular, new independences may have come to hold given the available evidence that can be exploited in further reasoning. Experiments on randomly generated networks have indicated that thus exploiting the dynamics of reasoning can considerably reduce the computational burden involved.
For the next five years, the applicant proposes to extend current research efforts concerning the design of more efficient algorithms for reasoning with a decision-theoretic network:
Research results that provide for optimising runtime complexity of reasoning will be evaluated by means of experiments on both real-life and randomly generated decision-theoretic networks.
Key publications addressing the computational complexity of algorithms for probabilistic inference and for computing supporting architectures are:
Many decision problems, including time-critical management problems in medicine, require reasoning about time-evolving processes. Decision-theoretic networks have not been designed to explicitly model such time-evolving processes and require extension for this purpose. The issue of modeling time is currently attracting considerable attention. Research results so far build upon time-sliced decision-theoretic networks, in which reasoning is performed over a sequence of interrelated separate networks. Each of these separate networks captures a time-stamped snapshot of the domain process that is being modeled. The evolution of time is represented by means of transition probabilities between the separate networks. Within the field of time-sliced decision-theoretic networks, modeling partially observable Markov decision processes currently appears to be the most fruitful, as a consequence of their underlying simplifying assumptions. Reasoning with a time-sliced network is much more involving than reasoning with a single decision-theoretic network. The computational complexity of associated reasoning algorithms is an issue of major concern.
The applicant has not been actively involved in research pertaining to modeling and reasoning about time-evolving processes, that is, otherwise than through a small number of M.Sc. projects.
Building upon her experience with modeling real-life problem domains, the applicant acknowledges that the ability to deal with time-evolving processes will significantly enhance the applicability of decision-theoretic networks. She proposes to initiate research to this end:
Key publications addressing time-sliced decision-theoretic networks, and networks for partially observable Markov decision processes in particular, are:
For the three experienced researchers in the projected research group, the applicant seeks
As the applicant wishes to give priority to strengthening current research, introduction of expertise from the field of intelligent data analysis is provisioned in the course of two years.
As detailed in the previous sections, the applicant proposes to undertake the construction of decision-theoretic networks for various different real-life application domains. To arrive at fully operational decision-support systems, an elaborate software environment is indispensable. This environment should provide not just various formalisms and associated reasoning algorithms, but also tools for the (automated) construction and evaluation of decision-theoretic networks. In addition, software is required to support experimental evaluation of research results pertaining to the runtime complexity of reasoning with a decision-theoretic network. A scientific programmer is requested to support the projected research group in this respect.
