An influence diagram is a widely-used graphical model for representing and solving problems of sequential decision making under imperfect information. A closely-related model for the same class of problems is a partially observable Markov decision process (POMDP). This dissertation leverages the relationship between these two models to develop improved algorithms for solving influence diagrams. The primary contribution is to generalize two classic dynamic programming algorithms for solving influence diagrams, Arc Reversal and Variable Elimination, by integrating them with a dynamic programming technique originally developed for solving POMDPs. This generalization relaxes constraints on the ordering of the steps of these algorithms in a way that dramatically improves scalability, especially in solving complex, multi-stage decision problems. A secondary contribution is the adoption of a more compact and intuitive representation of the solution of an influence diagram, called a strategy. Instead of representing a strategy as a table or as a tree, a strategy is represented as an acyclic graph, which can be exponentially more compact, making the strategy easier to interpret and understand.

Many real world AI applications involve reasoning on both continuous and discrete variables, while requiring some level of symbolic reasoning that can provide guarantees on the system's behaviour. Unfortunately, most of the existing probabilistic models do not efficiently support hard constraints or they are limited to purely discrete or continuous scenarios. Weighted Model Integration (WMI) is a recent and general formalism that enables probabilistic modeling and inference in hybrid structured domains. A difference of WMI-based inference algorithms with respect to most alternatives is that probabilities are computed inside a structured support involving both logical and algebraic relationships between variables. While some progress has been made in the last years and the topic is increasingly gaining interest from the community, research in this area is at an early stage. These aspects motivate the study of hybrid and symbolic probabilistic models and the development of scalable inference procedures and effective learning algorithms in these domains. This PhD Thesis embodies my effort in studying scalable reasoning and learning techniques in the context of WMI.

While stochastic optimal control, together with associate formulations like Reinforcement Learning, provides a formal approach to, amongst other, motor control, it remains computationally challenging for most practical problems. This thesis is concerned with the study of relations between stochastic optimal control and probabilistic inference. Such dualities { exempli ed by the classical Kalman Duality between the Linear-Quadratic-Gaussian control problem and the filtering problem in Linear-Gaussian dynamical systems { make it possible to exploit advances made within the separate fields. In this context, the emphasis in this work lies with utilisation of approximate inference methods for the control problem. Rather then concentrating on special cases which yield analytical inference problems, we propose a novel interpretation of stochastic optimal control in the general case in terms of minimisation of certain Kullback-Leibler divergences. Although these minimisations remain analytically intractable, we show that natural relaxations of the exact dual lead to new practical approaches. We introduce two particular general iterative methods ψ-Learning, which has global convergence guarantees and provides a unifying perspective on several previously proposed algorithms, and Posterior Policy Iteration, which allows direct application of inference methods. From these, practical algorithms for Reinforcement Learning, based on a Monte Carlo approximation to ψ-Learning, and model based stochastic optimal control, using a variational approximation of posterior policy iteration, are derived. In order to overcome the inherent limitations of parametric variational approximations, we furthermore introduce a new approach for none parametric approximate stochastic optimal control based on a reproducing kernel Hilbert space embedding of the control problem. Finally, we address the general problem of temporal optimisation, i.e., joint optimisation of controls and temporal aspects, e.g., duration, of the task. Specifically, we introduce a formulation of temporal optimisation based on a generalised form of the finite horizon problem. Importantly, we show that the generalised problem has a dual finite horizon problem of the standard form, thus bringing temporal optimisation within the reach of most commonly used algorithms. Throughout, problems from the area of motor control of robotic systems are used to evaluate the proposed methods and demonstrate their practical utility.

Recently numerous emerging applications, ranging from on-line financial transactions, RFID based supply chain management, traffic monitoring to real-time object monitoring, generate high-volume event streams. To meet the needs of processing event data streams in real-time, Complex Event Processing technology (CEP) has been developed with the focus on detecting occurrences of particular composite patterns of events. By analyzing and constructing several real-world CEP applications, we found that CEP needs to be extended with advanced services beyond detecting pattern queries. We summarize these emerging needs in three orthogonal directions. First, for applications which require access to both streaming and stored data, we need to provide a clear semantics and efficient schedulers in the face of concurrent access and failures. Second, when a CEP system is deployed in a sensitive environment such as health care, we wish to mitigate possible privacy leaks. Third, when input events do not carry the identification of the object being monitored, we need to infer the probabilistic identification of events before feed them to a CEP engine. Therefore this dissertation discusses the construction of a framework for extending CEP to support these critical services. First, existing CEP technology is limited in its capability of reacting to opportunities and risks detected by pattern queries. We propose to tackle this unsolved problem by embedding active rule support within the CEP engine. The main challenge is to handle interactions between queries and reactions to queries in the high-volume stream execution. We hence introduce a novel stream-oriented transactional model along with a family of stream transaction scheduling algorithms that ensure the correctness of concurrent stream execution. And then we demonstrate the proposed technology by applying it to a real-world healthcare system and evaluate the stream transaction scheduling algorithms extensively using real-world workload. Second, we are the first to study the privacy implications of CEP systems. Specifically we consider how to suppress events on a stream to reduce the disclosure of sensitive patterns, while ensuring that nonsensitive patterns continue to be reported by the CEP engine. We formally define the problem of utility-maximizing event suppression for privacy preservation. We then design a suite of real-time solutions that eliminate private pattern matches while maximizing the overall utility. Our first solution optimally solves the problem at the event-type level. The second solution, at event-instance level, further optimizes the event-type level solution by exploiting runtime event distributions using advanced pattern match cardinality estimation techniques. Our experimental evaluation over both real-world and synthetic event streams shows that our algorithms are effective in maximizing utility yet still efficient enough to offer near real time system responsiveness. Third, we observe that in many real-world object monitoring applications where the CEP technology is adopted, not all sensed events carry the identification of the object whose action they report on, so called €œnon-ID-ed€� events. Such non-ID-ed events prevent us from performing object-based analytics, such as tracking, alerting and pattern matching. We propose a probabilistic inference framework to tackle this problem by inferring the missing object identification associated with an event. Specifically, as a foundation we design a time-varying graphic model to capture correspondences between sensed events and objects. Upon this model, we elaborate how to adapt the state-of-the-art Forward-backward inference algorithm to continuously infer probabilistic identifications for non-ID-ed events. More important, we propose a suite of strategies for optimizing the performance of inference. Our experimental results, using large-volume streams of a real-world health care application, demonstrate the accuracy, efficiency, and scalability of the proposed technology.

The past twenty years have seen a successful formalization of the idea that perception is a form of probabilistic inference. Bayesian Decision Theory (BDT) provides a neat mathematical framework for describing how an ideal observer and actor should interpret incoming sensory stimuli and act in the face of uncertainty. The predictions of BDT, however, crucially depend on the observer’s internal models, represented in the Bayesian framework by priors, likelihoods, and the loss function. Arguably, only in the simplest scenarios (e.g., with a few Gaussian variables) we can expect a real observer’s internal representations to perfectly match the true statistics of the task at hand, and to conform to exact Bayesian computations, but how humans systematically deviate from BDT in more complex cases is yet to be understood. In this thesis we theoretically and experimentally investigate how people represent and perform probabilistic inference with complex (beyond Gaussian) one-dimensional distributions of stimuli in the context of sensorimotor decision making. The goal is to reconstruct the observers’ internal representations and details of their decision-making process from the behavioural data – by employing Bayesian inference to uncover properties of a system, the ideal observer, that is believed to perform Bayesian inference itself. This “inverse problem” is not unique: in principle, distinct Bayesian observer models can produce very similar behaviours. We circumvented this issue by means of experimental constraints and independent validation of the results. To understand how people represent complex distributions of stimuli in the specific domain of time perception, we conducted a series of psychophysical experiments where participants were asked to reproduce the time interval between a mouse click and a flash, drawn from a session-dependent distribution of intervals. We found that participants could learn smooth approximations of the non-Gaussian experimental distributions, but seemed to have trouble with learning some complex statistical features such as bimodality. To investigate whether this difficulty arose from learning complex distributions or computing with them, we conducted a target estimation experiment in which “priors” where explicitly displayed on screen and therefore did not need to be learnt. Lack of difference in performance between the Gaussian and bimodal conditions in this task suggests that acquiring a bimodal prior, rather than computing with it, is the major difficulty. Model comparison on a large number of Bayesian observer models, representing different assumptions about the noise sources and details of the decision process, revealed a further source of variability in decision making that was modelled as a “stochastic posterior”. Finally, prompted by a secondary finding of the previous experiment, we tested the effect of decision uncertainty on the capacity of the participants to correct for added perturbations in the visual feedback in a centre of mass estimation task. Participants almost completely compensated for the injected error in low uncertainty trials, but only partially so in the high uncertainty ones, even when allowed sufficient time to adjust their response. Surprisingly, though, their overall performance was not significantly affected. This finding is consistent with the behaviour of a Bayesian observer with an additional term in the loss function that represents “effort” – a component of optimal control usually thought to be negligible in sensorimotor estimation tasks. Together, these studies provide new insight into the capacity and limitations people have in learning and performing probabilistic inference with distributions beyond Gaussian. This work also introduces several tools and techniques that can help in the systematic exploration of suboptimal behaviour. Developing a language to describe suboptimality, mismatching representations and approximate inference, as opposed to optimality and exact inference, is a fundamental step to link behavioural studies to actual neural computations.

Probability theory provides a mathematically rigorous yet conceptually flexible calculus of uncertainty, allowing the construction of complex hierarchical models for real-world inference tasks. Unfortunately, exact inference in probabilistic models is often computationally expensive or even intractable. A close inspection in such situations often reveals that computational bottlenecks are confined to certain aspects of the model, which can be circumvented by approximations without having to sacrifice the model's interesting aspects. The conceptual framework of graphical models provides an elegant means of representing probabilistic models and deriving both exact and approximate inference algorithms in terms of local computations. This makes graphical models an ideal aid in the development of generalizable approximations. This thesis contains a brief introduction to approximate inference in graphical models (Chapter 2), followed by three extensive case studies in which approximate inference algorithms are developed for challenging applied inference problems. Chapter 3 derives the first probabilistic game tree search algorithm. Chapter 4 provides a novel expressive model for inference in psychometric questionnaires. Chapter 5 develops a model for the topics of large corpora of text documents, conditional on document metadata, with a focus on computational speed. In each case, graphical models help in two important ways: They first provide important structural insight into the problem; and then suggest practical approximations to the exact probabilistic solution.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第22586号 / 情博第723号 / 新制||情||124(附属図書館) / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 田中 利幸, 教授 石井 信, 教授 下平 英寿 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

This dissertation proposes an iterative confidence passing (ICP) approach for parameter estimation. The dissertation describes three different algorithms that follow from this ICP approach. These three variations of the ICP approach are applied to (a) macrodiversity and user cooperation diversity reception problems, (b) the co-operative multipoint MIMO reception problem (pertinent to the LTE Advanced system scenarios), and (c) the satellite beamforming problem. The first two of these three applications are some of the significant open DSP research problems that are currently being actively pursued in academia and industry. This dissertation demonstrates a significant performance improvement that the proposed ICP approach delivers compared to the existing known techniques. The proposed ICP approach jointly estimates (and, thereby, separates) two sets of unknown parameters from the receiver measurements. For applications (a) and (b) mentioned above, one set of unknowns is comprised of the discrete-valued information-bearing transmitted symbols in a multi-channel communication system, and the other set of unknown parameters is formed by the coefficients of a Rayleigh or Rician fading channel. Application (a) is for interference-free, cooperative or macro, transmit or receive, diversity scenarios. Application (b) is for MIMO systems with interference-rich reception. Finally, application (c) is for an interference-free spacecraft array calibration system model in which both the sets of unknowns are complex continuous valued variables whose magnitude follows the Rician distribution. The algorithm described here is the outcome of an investigation for solving a difficult channel estimation problem. The difficulty of the estimation problem arises because (i) the channel of interest is intermittently observed, and (ii) the partially observed information is not directly of the channel of interest; it has dependency on another unknown and uncorrelated set of complex-valued random variables. The proposed ICP algorithmic approach for solving the above estimation problems is based on an iterative application of the Weighted Least Squares (WLS) method. The main novelty of the proposed algorithm is a back and forth exchange of the confidence or the belief values in the WLS estimates of the unknown parameters during the algorithm iterations. The confidence values of the previously obtained estimates are used to derive the estimation weights at the next iteration, which generates an improved estimate with a greater confidence. This method of iterative confidence (or belief) passing causes a bootstrapping convergence to the parameter estimates. Besides the ICP approach, several alternatives are considered to solve the above problems (a, b and c). Results of the performance simulation of the alternative methods show that the ICP algorithm outperforms all the other candidate approaches. Performance benefit is significant when the measurements (and the initial seed estimates) have non-uniform quality, e.g., when many of the measurements are either non-usable (e.g., due to shadowing or blockage) or are missing (e.g., due to instrument failures). / Ph. D.

<p>Bounded rationality is the study of how human cognition with limited capacity is adapted to handle the complex information structures in the environment. This thesis argues that in order to understand the bounded rationality of decision processes, it is necessary to develop decision theories that are computational process models based upon basic cognitive and perceptual mechanisms. The main goal of this thesis is to show that models of perceptual categorization based on the storage of exemplars and retrieval of similar exemplars whenever a new object is encountered (D. L. Medin & M. M. Schaffer, 1978), can be an important contribution to theories of decision making. Study I proposed, PROBEX (PROBabilities from Exemplars), a model for inferences from generic knowledge. It is a “lazy” algorithm that presumes no pre-computed abstractions. In a computer simulation it was found to be a powerful decision strategy, and it was possible to fit the model to human data in a psychologically plausible way. Study II was a theoretical investigation that found that PROBEX was very robust in conditions where the decision maker has very little information, and that it worked well even under the worst circumstances. Study III empirically tested if humans can learn to use exemplar based or one reason decision making strategies (G. Gigerenzer, P. Todd, & the ABC Research Group, 1999) where it is appropriate in a two-alternative choice task. Experiment 1 used cue structure and presentation format as independent variables, and participants easily used one reason strategies if the decision task presented the information as normal text. The participants were only able to use exemplars if they were presented as short strings of letters. Experiment 2 failed to accelerate learning of exemplar use during the decision phase, by prior exposure to exemplars in a similar task. In conclusion, this thesis supports that there are at least two modes of decision making, which are boundedly rational if they are used in the appropriate context. Exemplar strategies may, contrary to study II, only be used late in learning, and the conditions for learning need to be investigated further.</p>

Bounded rationality is the study of how human cognition with limited capacity is adapted to handle the complex information structures in the environment. This thesis argues that in order to understand the bounded rationality of decision processes, it is necessary to develop decision theories that are computational process models based upon basic cognitive and perceptual mechanisms. The main goal of this thesis is to show that models of perceptual categorization based on the storage of exemplars and retrieval of similar exemplars whenever a new object is encountered (D. L. Medin &amp; M. M. Schaffer, 1978), can be an important contribution to theories of decision making. Study I proposed, PROBEX (PROBabilities from Exemplars), a model for inferences from generic knowledge. It is a “lazy” algorithm that presumes no pre-computed abstractions. In a computer simulation it was found to be a powerful decision strategy, and it was possible to fit the model to human data in a psychologically plausible way. Study II was a theoretical investigation that found that PROBEX was very robust in conditions where the decision maker has very little information, and that it worked well even under the worst circumstances. Study III empirically tested if humans can learn to use exemplar based or one reason decision making strategies (G. Gigerenzer, P. Todd, &amp; the ABC Research Group, 1999) where it is appropriate in a two-alternative choice task. Experiment 1 used cue structure and presentation format as independent variables, and participants easily used one reason strategies if the decision task presented the information as normal text. The participants were only able to use exemplars if they were presented as short strings of letters. Experiment 2 failed to accelerate learning of exemplar use during the decision phase, by prior exposure to exemplars in a similar task. In conclusion, this thesis supports that there are at least two modes of decision making, which are boundedly rational if they are used in the appropriate context. Exemplar strategies may, contrary to study II, only be used late in learning, and the conditions for learning need to be investigated further.