Cooperation Methods in Bayesian Decision Making with Multiple Participants

Jan Kracík

Institute of Information Theory and Automation of the ASCR, Department of Adaptive Systems

Introduction

Bayesian Decision Making, Fully Probabilistic Design

The Bayesian theory represents a normative approach to the decision making under uncertainty. In practical applications a design of an optimal decision strategy is based on the following components:

• Probabilistic parametric model, which is used for modelling of a system behavior in dependence of selected decisions, past states of the system, and an unknown parameter.
• Prior probability distribution of the unknown parameter, which represents partial knowledge about the system.
• Objectives of the decision making are characterized in terms of a utility function, which assigns a scalar valued measure of utility to all possible consequences of the decisions.

Alternatively, the decision strategy can be designed using the, so-called, fully probabilistic design (FPD). Within the FPD, the objectives of the decision making are described by an ideal probability density function (pdf). The optimal decision strategy is then designed as a randomized one for which the Kullback-Leibler divergence of the joint pdf (given by the parametric model, decision strategy, and prior pdf) and the ideal pdf is minimal. The main asset of the FPD is that it has an explicit solution.

Motivation

In practice the applicability of the Bayesian decision making is restricted by an extent of the given task. It is partially caused by the computational complexity, that grows quickly with increasing dimension of the task. There is also another, rather conceptual, reason: In large tasks it is often difficult to express the probabilistic model and objectives in a proper form. Instead, knowledge about the system and objectives are frequently available piecewise, i.e., separately for different parts of the system. Moreover, these parts can arbitrarily overlap. Then, it can easily happen that for some parts of the system there are several inconsistent objectives and knowledge pieces available.

The need for a feasible solution of large tasks led to the idea of a distributed decision making with multiple Bayesian decision makers (participants). This task was solved in the Department of Adaptive Systems in the Institute of Information Theory and Automation of the ASCR within the project BADDYR (Bayesian Adaptive Distributed Decision Making) to the solution of which the presented thesis partially contributed. The staring point of the approach followed in the BADDYR project is that a group of Bayesian decision makers acts in a given system, whereas:

• each participant deals with only a part of the system (environment);
• the environments of individual participants may arbitrarily overlap;
• parametric models of the environments, prior pdfs, as well as objectives of individual participants need not be consistent in any way.

However, the inconsistency of the objectives and states of knowledge of the individual participants causes that if the participants act independently, as if they were the only decision makers in their environments, then the decision making can easily became inefficient. A common reason of this inefficiency is that the participants receive information about the objectives and knowledge of other participants only indirectly through the observed data. Such an information exchange is slow and thus ineffective. It is expected that the group decision making becomes more efficient if the participants are provided with cooperation means which allow them to communicate directly and to exploit the acquired information. As a distributed solution is aimed at, the communication cannot be realized centrally via a common facilitator but must be performed directly between the participants. The communication is meaningful only between participants with, at least partially, overlapping environments. A pair of such participants is called neighbours.

The aim of the phd thesis is to design methods which allow the neighbours to share information on knowledge and objectives and use it to enhance the efficiency of the group decision making.

The main part of the thesis consists of three chapters:

1. Multiple Participant Decision Making
2. Global Objective Setting
3. Bayesian Knowledge Merging

Multiple Participant Decision Making

In this chapter the problem of Bayesian decision with multiple participants is formally introduced. Each participant is supposed to have:

• parametric model of its environment,
• prior pdf of the unknown parameter,
• ideal pdf on its environment

Although our primary aim is the multiple participant decision making in a distributed form, it comes out that some kind of a centralized decision making task, called here a global task, must be inevitably considered. The global task serves as a criterion which enables to compare the tuples of decision strategies of the individual participants. However, the participants themselves do not provide enough information on which the global task could be constructed. For this purpose it is necessary to adopt additional assumptions, according to which, e.g., the sources of knowledge inconsistency could be modelled. Due to a large number of possible approaches to the construction of the global task their systematic classification is out of the scope of this work. Instead, we attempt to outline a formulation of a single specific case, on which the possibilities for the cooperation are illustrated. Moreover, this particular case allows to reveal some bottlenecks faced in the multiple participant decision making.

The main results acquired in this chapter are as follows:

• It is pointed out that any normative distributed multiple participant decision making induces certain kind of a global decision making task.
• It is illustrated that the participants themselves do not provide enough information for the global task to be constructed as a Bayesian one. For this purpose it would be necessary to model relations among knowledge pieces of individual participants (measure of their overlapping, etc.). Nevertheless, such kind of information cannot be acquired from the participants themselves.
• The special case in which the prior pdfs are in a conjugate form enables to represent the knowledge of individual participants as sets of data. This approach allows to combine the participants' knowledge in a natural way, even if the participants employ different parametric models. We believe that this special case may serve as a suitable starting point for a treatment of more general ones.

Global Objective Setting

In this chapter a method is proposed which enables to establish the global objective so that it is in some sense close to the objectives of the individual participants. Namely, it is supposed that the participants employ the fully probabilistic design. In such case, the objectives of the participants (local objectives) are represented by ideal pdfs on their environments. The global ideal pdf is then selected as the one which minimizes a weighted sum of the Kullback-Leibler divergences of the local ideal pdfs and the corresponding marginals of the searched global one. The weights in the sum represent optional parameters - the higher a particular weight is the closer to the objectives of the corresponding participant the global objectives are.

The most important results of this chapter are as follows:

• A necessary condition for a joint pdf to be a minimizer of the weighted sum of the Kullback-Leibler divergences is proposed.
• It is proved that under an additional assumption the necessary condition is also a sufficient one.
• The equation representing the necessary condition cannot be solved analytically. On that account, an iterative algorithm for an approximate solution of the minimization task is proposed. Its convergence to the minimizing pdf is proved.
• For discrete random variables the iterative algorithm can be easily implemented. In case of continuous random variables the algorithm cannot be directly implemented because of an intractable form of the pdfs approximating the searched global ideal pdf. To overcome this difficulty, a generalized EM algorithm is introduced, which can be used for approximation of a given pdf by a probabilistic mixture. Combining the two algorithms we get an algorithm which allows to find an approximate global ideal pdf in a form of a finite Gaussian mixture.

Bayesian Knowledge Merging

In the last chapter a method is proposed which allows a Bayesian decision maker to exploit an information in a form of a joint pdf of data and use it for updating its prior pdf. In a special case in which the information has a form of an empirical pdf from a data sample the proposed method leads to the same result as exploitation of the data themselves. In multiple participant decision making this method can be used as an approximate, but practically feasible, means for knowledge sharing between neighbours, even in case that that they use different parametric models. Its practical feasibility stems from the fact that for a parametric model from an exponential family and a conjugate prior pdf the updated prior pdf remains in a conjugate form. It is illustrated that under some assumptions on the parametric models of the communicating participants the proposed method is able to provide accurate knowledge sharing.

Conclusions

The main contributions of the thesis can be summarized as follows:

• The presented case study allows a better understanding of the bottlenecks faced in the Bayesian decision making with multiple participants.
• A feasible and theoretically supported algorithmic solution for the minimization of the weighted sum of the Kullback-Leibler divergences of given marginal pdfs and corresponding marginals of the searched pdf has been reached for both discrete and continuous random variables. The proposed algorithms allow to find common objectives of the participants employing the fully probabilistic design.
• A method has been proposed which allows a Bayesian decision maker to exploit an information represented by a joint pdf of data to update its prior pdf. In the multiple participant decision making this method provides a practically feasible means for knowledge sharing between neighbours, even if they use different parametric models of their environments.

• The proposed generalization of the EM algorithm provides a means for approximation of complex pdfs by finite probabilistic mixtures.
• The method for knowledge sharing between participants can be used for exploiting expert information in a form of a joint pdf of data.

The thesis possesses also several open problems:

• In the current state of development, the formulation of the multiple participant decision making is still insufficient. The basic assumptions, e.g., the assumption on limited computational resources, as well as the requirements related to the form of the global task must be specified in more details.
• A design of a distributed form of the multiple participant decision making is still open. The methods proposed in the thesis provide rather technical means for communication of the participants but a design of particular communication strategies, according to which the participants decide when, with whom, and what to communicate, remains unsolved.