Compiling influence diagrams

This paper examines a class of algorithms for “compiling” influence diagrams into a set of simple decision rules. These decision rules define simple-to-execute, complete, consistent, and near-optimal decision procedures. These compilation algorithms can be used to derive decision procedures for manually solving time constrained decision problems     

Sensitivity analysis in influence diagrams

The influence diagram framework serves as a powerful modeling tool for symmetric decision problems with a single decision maker. However, one of the main difficulties when representing decision problems using influence diagrams is eliciting the utilities and the probabilities. This makes it desirable to be able to investigate: 1) how sensitive the solution is to variations in some utility or probability parameter, and 2) how robust the solution is to joint variations over a set of parameters. In this paper, we propose a general algorithm for performing these types of analysis.     

Enterprise architecture analysis with extended influence diagrams

The discipline of enterprise architecture advocates the use of models to support decision-making on enterprise-wide information system issues. In order to provide such support, enterprise architecture models should be amenable to analyses of various properties, as e.g. the level of enterprise information security. This paper proposes the use of a formal language to support such analysis. Such a language needs to be able to represent causal relations between, and definitions of, various concepts as well as uncertainty with respect to both concepts and relations. To support decision making properly, the language must also allow the representation of goals and decision alternatives. This paper evaluates a number of languages with respect to these requirements, and selects influence diagrams for further consideration. The influence diagrams are then extended to fully satisfy the requirements. The syntax and semantics of the extended influence diagrams are detailed in the paper, and their use is demonstrated in an example.     

Optimal control problems over large time intervals

The paper focuses on problems of optimal control over a large time interval with end states prescribed. For a wide class of systems and performance indices, an approximate solution is characterized by piecing together two solutions for two infinite time problems. These solutions exhibit similar transient behaviour.     

A factorization approach to evaluating simultaneous influence diagrams

Evaluating an influence diagram (ID) is a challenging problem because its complexity increases exponentially in the number of decision nodes in the diagram. In this paper, we examine the problem for a special class of IDs where multiple decisions must be made simultaneously. We describe a brief theory that factorizes out the computations common to all policies in evaluating them. Our evaluation approach conducts these computations once and uses them across all policies. We identify the ID structures for which the approach can achieve savings. We show that the approach can be used to efficiently recompute the optimal policy of an ID when its structure or parameters change. Finally, we demonstrate the superior performance of the approach by simulation studies and a military planning example.     

Toward data-driven solutions to interactive dynamic influence diagrams

Knowledge and Information Systems - With the availability of significant amount of data, data-driven decision making becomes an alternative way for solving complex multiagent decision problems....     

Complexity results and algorithms for possibilistic influence diagrams

In this article we present the framework of Possibilistic Influence Diagrams (PID), which allows to model in a compact form problems of sequential decision making under uncertainty, when only ordinal data on transitions likelihood or preferences are available. The graphical part of a PID is exactly the same as that of usual influence diagrams, however the semantics differ. Transition likelihoods are expressed as possibility distributions and rewards are here considered as satisfaction degrees. Expected utility is then replaced by anyone of the two possibilistic qualitative utility criteria (optimistic and pessimistic) for evaluating strategies in a PID. We then describe decision tree-based methods for evaluating PID and computing optimal strategies and we study the computational complexity of PID optimisation problems for both cases. Finally, we propose a dedicated variable elimination algorithm that can be applied to both optimistic and pessimistic cases for solving PID.     

Diagnostic reasoning and medical decision-making with fuzzy influence diagrams

Influence diagrams have been widely used as knowledge bases in medical informatics and many applied domains. In conventional influence diagrams, the numerical models of uncertainty are probability distributions associated with chance nodes and value tables for value nodes. However, when incomplete knowledge or linguistic vagueness is involved in the reasoning systems, the suitability of probability distributions is questioned. This study intends to propose an alternative numerical model for influence diagrams, possibility distributions, which extend influence diagrams into fuzzy influence diagrams. In fuzzy influence diagrams, each chance node and value node is associated with a possibility distribution which expresses the uncertain features of the node. This study also develops a simulation algorithm and a fuzzy programming model for diagnosis and optimal decision in medical settings.     

Repetitive learning control of nonlinear systems over finite intervals

Iterative learning control requires initial repositioning, while the time functions to be learned should be of periodicity in repetitive control. However, there are cases in practice where the time-varying unknowns are not periodic but repetitive, and repetitive learning control is applicable with avoidance of initial repositioning. In this paper, repetitive learning control designs are presented for a broader class of nonlinear systems over finite intervals. The Freeman formula is modified and used for sta...     

Explanation of Bayesian networks and influence diagrams in Elvira.

Bayesian networks (BNs) and influence diagrams (IDs) are probabilistic graphical models that are widely used for building diagnosis- and decision-support expert systems. Explanation of both the model and the reasoning is important for debugging these models, alleviating users' reluctance to accept their advice, and using them as tutoring systems. This paper describes some explanation options for BNs and IDs that have been implemented in Elvira and how they have been used for building medical models and teaching probabilistic reasoning to pre- and postgraduate students.     

Personalizing influence diagrams: applying online learning strategies to dialogue management

We consider the problem of adapting the parameters of an influence diagram in an online fashion for real-time personalization. This problem is important when we use the influence diagram repeatedly to make decisions and we are uncertain about its parameters. We describe learning algorithms to solve this problem. In particular, we show how to modify various explore-versus-exploit strategies that are known to work well for Markov decision processes to the more general influence-diagram model. As an illustration, we describe how our techniques for online personalization allow a voice-enabled browser to adapt to a particular speaker for spoken dialogue management. We evaluate all the explore-versus-exploit strategies in this domain.     

定性影响图及其决策算法改进研究

影响图这项图形决策技术是解决现实决策问题的有效手段之一.但是,需要获取大量概率和效用值成为了其应用的主要障碍.当事物的依赖关系或者相关参数值无法精确描述时,如何利用非精确的信息进行推理已成为提高影响图决策效率的关键问题.为了在一定程度上克服这种障碍,定性贝叶斯网络及其相关算法被提出并得到发展.本文在分析定性影响图相关理论的基础上,对定性影响图决策推理算法进行了有效改进.     

基于概率模型的数据流预测查询算法

挖掘在线数据流的变化趋势并预测未来时间窗口上的可能值,可以为许多时间敏感的应用提供重要决策支持.通过将数量可能无限的流数据元素映射到离散的且数量有限的流数据状态空间,不断变化的流数据变化趋势可以模拟成连续的流数据状态变化的过程,进而在很小的时间与空间代价下,数据流状态变迁的趋势动态存储在状态变迁图中.通过分析状态变迁图中的流数据变迁的统计规律,数据流上未来时刻的可能值可以应用马尔可夫模型在线连续预测.     

Adaptive diagrams: Handing control over to the learner to manage split-attention online

Based on cognitive load theory, it is well known that when studying a diagram that includes explanatory text, optimal learning occurs when the text is physically positioned close to the diagram as it eliminates the need for learners to split their attention between the two sources of information. What is not known is the effect on learning when learners manage split-attention for themselves when presented with a separated diagram and explanatory text. This study focuses on this new research direction by examining how learners can self-manage cognitive load through the physical manipulation of digital materials. Physical manipulation refers to moving text objects in digital materials to connect related pieces of textual information to a diagram, thus adapting the diagram to reduce split-attention. Fifty-two university students participated in one of two experiments. Experiment 1 (N = 34) investigated whether learners who were guided to self-manage split-attention by moving text objects on a screen displaying instructional material with evident split-attention were able to reduce split-attention and thus outperform learners who were provided split-source materials. Experiment 2 (N = 18) collected verbal think-aloud protocols to uncover the students' learning processes with the materials. Results confirmed the split-attention effect thus replicating this effect in a digital domain. Furthermore, whilst the self-managed condition did not significantly outperform the split-attention condition, the added task for learners to move text boxes to relevant aspects of the diagram did not have an adverse effect on learning, as the self-managed condition performed as well as (and for a recall task slightly better than) the split-attention condition. The verbal protocols highlighted that in order for learners to successfully self-manage split-attention training and guidance needs to be more extensive and explicit. Implications for further research for this new research direction in cognitive load theory are discussed.     

由序列图合成状态图

序列图和状态图对于描述和理解面向对象软件系统有着极其重要的作用。符合UML标准的序列图和状态图存在信息重叠，根据序列图提供的信息可以合成状态图。给出了在Rational Rose中由序列图合成状态图工具的实现。     

Design of generalized discrete-time H ∞-optimal control over finite and infinite intervals

For the discrete linear nonstationary plants, the state or output feedbacks were designed for which the generalized H _∞-norm of a closed-loop system characterizing the joint effect of initial state and external perturbation on the controlled output and terminal state takes on the minimal value.     

Fundamentals of SIGLA,an interval computing system over the completed set of intervals

The SIGLA System has been designed to obtain an Interval Computing System working with the whole surrounding structure of the standard interval setI (R) (see [9]), that is, the lattice completion ofI (R) with the ordinary algebraic operations extended onto it. A statistical component associating intervals to Bounded Fuzzy Distributions is added. Rounding semantics onI ^* (R) is considered, and bounding theorems directing programming are given. Improper intervals are shown to mean “control-band-like variables”, in contrast to the classical “autonomous random variables” represented by proper intervals. An outline of the SIGLA language is given.     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有：考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

Set space diagrams

This paper introduces set space diagrams and defines their formal syntax and semantics. Conventional region based diagrams, like Euler circles and Venn diagrams, represent sets and their intersections by means of overlapping regions. By contrast, set space diagrams provide a certain layout that avoids overlapping geometrical entities. This enables the representation of a good deal of sets without getting diagrams which are cluttered due to overlapping regions. In particular, these diagrams can be employed for illustration purposes, e.g., for showing the laws of Boolean algebras. Additionally, cardinalities are represented and can be easily compared; inferences can be drawn to derive unknown cardinalities from a given knowledge base. The soundness of set space diagrams is shown with respect to their set-theoretic interpretation.     

Extension of numerical quadrature formulae to cater for end point singular behaviours over finite intervals

The N-point Gaussian quadrature method is generalised to cater for various possible singular behaviours at the end points of the interval of integration at the expense of being algebraically exact for a polynomial of lower order than usual. Weights and abscissae are chosen to exactly integrate an integrand which is the sum of the singular functions and an arbitrary polynomial. This allows us to cater for several different end-point singularities in the same quadrature formula and in this way differs from published quadratures where a singular behaviour is incorporated in a weight function that multiplies an arbitrary polynomial. We present tables of weights and abscissae that cater for (i) logarithmic end point singularities and (ii) logarithmic plus inverse square root singular behaviours. Also a 10-point quadrature is presented that exactly caters for log(x), x^-1/4,x^-1/2,x^-3/4 singular behaviours and is recommended for programmable calculator use. Finally a brief comparison study of the various (10-point) quadratures herein considered is made.