Markov Properties and Factorization of Possibility Distributions

Markov properties and factorization are powerful tools allowing the expression of multidimensional probability distributions by means of low-dimensional ones. As multidimensional possibilistic models have been studied for several years, the demand for analogous tools in possibility theory seems quite natural. This paper is intended to be a promotion of De Cooman's measure-theoretic approach to possibility theory, as this approach allows us to find analogies to many important results obtained in a probabilistic framework.First we recall our definition of conditional possibilistic independence, parameterized by a continuous t-norm, and its properties. Then we introduce Markov properties, based on this conditional independence notion, and factorization of possibility distributions (again parameterized by a continuous t-norm) and we find the relationships between them. Our results are accompanied by a number of counterexamples, which show that the assumptions of particular theorems are substantial.     

Degrees of conditional (in)dependence: A framework for approximate Bayesian networks and examples related to the rough set-based feature selection

Bayesian networks provide the means for representing probabilistic conditional independence. Conditional independence is widely considered also beyond the theory of probability, with linkages to, e.g. the database multi-valued dependencies, and at a higher abstraction level of semi-graphoid models. The rough set framework for data analysis is related to the topics of conditional independence via the notion of a decision reduct, to be considered within a wider domain of the feature selection. Given probabilistic version of decision reducts equivalent to the data-based Markov boundaries, the studies were also conducted for other criteria of the rough-set-based feature selection, e.g. those corresponding to the multi-valued dependencies. In this paper, we investigate the degrees of approximate conditional dependence, which could be a topic corresponding to the well-known notions such as conditional mutual information and polymatroid functions, however, with many practically useful approximate conditional independence models unmanageable within the information theoretic framework. The major paper’s contribution lays in extending the means for understanding the degrees of approximate conditional dependence, with appropriately generalized semi-graphoid properties formulated and with the mathematical soundness of the Bayesian network-like representation of the approximate conditional independence statements thoroughly proved. As an additional contribution, we provide a case study of the approximate conditional independence model, which would not be manageable without the above-mentioned extensions.     

The role of coherence for handling probabilistic evaluations and independence

This paper deals with coherent conditional probability able to manage uncertainty, partial knowledge and conditional independence, overcoming the critical situations presented by the classic independence definition. When a probability is not complete (i.e. it is defined on an arbitrary set of conditional events) the conditional independence statements are not necessarily automatically induced by the values of the assessment, so given a set of independence statements its compatibility with the numerical values (conditional probability) need to be checked. This problem related to the compatibility of independence statements and conditional probability assessment is studied and a procedure for checking the compatibility is proposed.     

Learning first-order probabilistic models with combining rules

Many real-world domains exhibit rich relational structure and stochasticity and motivate the development of models that combine predicate logic with probabilities. These models describe probabilistic influences between attributes of objects that are related to each other through known domain relationships. To keep these models succinct, each such influence is considered independent of others, which is called the assumption of “independence of causal influences” (ICI). In this paper, we describe a language that consists of quantified conditional influence statements and captures most relational probabilistic models based on directed graphs. The influences due to different statements are combined using a set of combining rules such as Noisy-OR. We motivate and introduce multi-level combining rules, where the lower level rules combine the influences due to different ground instances of the same statement, and the upper level rules combine the influences due to different statements. We present algorithms and empirical results for parameter learning in the presence of such combining rules. Specifically, we derive and implement algorithms based on gradient descent and expectation maximization for different combining rules and evaluate them on synthetic data and on a real-world task. The results demonstrate that the algorithms are able to learn both the conditional probability distributions of the influence statements and the parameters of the combining rules.     

Diagnosing behavioral differences between business process models: An approach based on event structures

Companies operating in multiple markets or segments often need to manage multiple variants of the same business process. Such multiplicity may stem for example from distinct products, different types of customers or regulatory differences across countries in which the companies operate. During the management of these processes, analysts need to compare models of multiple process variants in order to identify opportunities for standardization or to understand performance differences across variants. To support this comparison, this paper proposes a technique for diagnosing behavioral differences between process models. Given two process models, it determines if they are behaviorally equivalent, and if not, it describes their differences in terms of behavioral relations – like causal dependencies or conflicts – that hold in one model but not in the other. The technique is based on a translation from process models to event structures, a formalism that describes the behavior as a collection of events (task instances) connected by binary behavioral relations. A naïve version of this translation suffers from two limitations. First, it produces redundant difference statements because an event structure describing a process may contain unnecessary event duplications. Second, this translation is not directly applicable to process models with cycles as the corresponding event structure is infinite. To tackle the first issue, the paper proposes a technique for reducing the number of events in an event structure while preserving the behavior. For the second issue, relying on the theory of complete unfolding prefixes, the paper shows how to construct a finite prefix of the unfolding of a possibly cyclic process model where all possible causes of every activity is represented. Additionally, activities that can occur multiple times in an execution of the process are distinguished from those that can occur at most once. The finite prefix thus enables the diagnosis of behavioral differences in terms of activity repetition and causal relations that hold in one model but not in the other. The method is implemented as a prototype that takes as input process models in the Business Process Model and Notation (BPMN) and produces difference statements in natural language. Differences can also be graphically overlaid on the process models.     

Mining and visualising ordinal data with non-parametric continuous BBNs

Data mining is the process of extracting and analysing information from large databases. Graphical models are a suitable framework for probabilistic modelling. A Bayesian Belief Net (BBN) is a probabilistic graphical model, which represents joint distributions in an intuitive and efficient way. It encodes the probability density (or mass) function of a set of variables by specifying a number of conditional independence statements in the form of a directed acyclic graph. Specifying the structure of the model is one of the most important design choices in graphical modelling. Notwithstanding their potential, there are only a limited number of applications of graphical models on very complex and large databases. A method for mining ordinal multivariate data using non-parametric BBNs is presented. The main advantage of this method is that it can handle a large number of continuous variables, without making any assumptions about their marginal distributions, in a very fast manner. Once the BBN is learned from data, it can be further used for prediction. This approach allows for rapid conditionalisation, which is a very important feature of a BBN from a user’s standpoint.     

LEARNING STRUCTURED BAYESIAN NETWORKS: COMBINING ABSTRACTION HIERARCHIES AND TREE-STRUCTURED CONDITIONAL PROBABILITY TABLES

Context-specific independence representations, such as tree-structured conditional probability distributions, capture local independence relationships among the random variables in a Bayesian network (BN). Local independence relationships among the random variables can also be captured by using attribute-value hierarchies to find an appropriate abstraction level for the values used to describe the conditional probability distributions. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. In this paper, we introduce Tree-Abstraction-Based Search (TABS), an approach for learning a data distribution by inducing the graph structure and parameters of a BN from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. To construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. We present empirical results for three real-world domains, finding that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.     

Decomposition of Multidimensional Distributions Represented by Perfect Sequences

In contrast to most other ways used to represent multidimensional probability distributions, which are based on graphical Markov modelling (i.e., dependence structure of distributions is represented by graphs), the described approach is rather procedural. Here, we describe a process by which a multidimensional distribution can be composed from a generating sequence – a sequence of low-dimensional distributions. This paper gives a brief introduction to this compositional approach and reports two new theorems that are necessary for designing computational procedures within this apparatus. The first concerns computation of marginal distributions, the other gives instructions for decomposing a multidimensional model into two lower-dimensional ones.     

Speech Recognition Using Augmented Conditional Random Fields

Acoustic modeling based on hidden Markov models (HMMs) is employed by state-of-the-art stochastic speech recognition systems. Although HMMs are a natural choice to warp the time axis and model the temporal phenomena in the speech signal, their conditional independence properties limit their ability to model spectral phenomena well. In this paper, a new acoustic modeling paradigm based on augmented conditional random fields (ACRFs) is investigated and developed. This paradigm addresses some limitations of HMMs while maintaining many of the aspects which have made them successful. In particular, the acoustic modeling problem is reformulated in a data driven, sparse, augmented space to increase discrimination. Acoustic context modeling is explicitly integrated to handle the sequential phenomena of the speech signal. We present an efficient framework for estimating these models that ensures scalability and generality. In the TIMIT phone recognition task, a phone error rate of 23.0% was recorded on the full test set, a significant improvement over comparable HMM-based systems.     

On learning multicategory classification with sample queries

Consider the pattern recognition problem of learning multicategory classification from a labeled sample, for instance, the problem of learning character recognition where a category corresponds to an alphanumeric letter. The classical theory of pattern recognition assumes labeled examples appear according to the unknown underlying pattern-class conditional probability distributions where the pattern classes are picked randomly according to their a priori probabilities. In this paper we pose the following question: Can the learning accuracy be improved if labeled examples are independently randomly drawn according to the underlying class conditional probability distributions but the pattern classes are chosen not necessarily according to their a priori probabilities? We answer this in the affirmative by showing that there exists a tuning of the sub-sample proportions which minimizes a loss criterion. The tuning is relative to the intrinsic complexity of the Bayes-classifier. As this complexity depends on the underlying probability distributions which are assumed to be unknown, we provide an algorithm which learns the proportions in an on-line manner utilizing sample querying which asymptotically minimizes the criterion. In practice, this algorithm may be used to boost the performance of existing learning classification algorithms by apportioning better sub-sample proportions.     

Dual Stochastic Dominance and Quantile Risk Measures

Following the seminal work by Markowitz, the portfolio selection problem is usually modeled as a bicriteria optimization problem where a reasonable trade–off between expected rate of return and risk is sought. In the classical Markowitz model, the risk is measured with variance. Several other risk measures have been later considered thus creating the entire family of mean–risk (Markowitz type) models. In this paper, we analyze mean–risk models using quantiles and tail characteristics of the distribution. Value at risk (VAR), defined as the maximum loss at a specified confidence level, is a widely used quantile risk measure. The corresponding second order quantile measure, called the worst conditional expectation or Tail VAR, represents the mean shortfall at a specified confidence level. It has more attractive theoretical properties and it leads to LP solvable portfolio optimization models in the case of discrete random variables, i.e., in the case of returns defined by their realizations under the specified scenarios. We show that the mean–risk models using the worst conditional expectation or some of its extensions are in harmony with the stochastic dominance order. For this purpose, we exploit duality relations of convex analysis to develop the quantile model of stochastic dominance for general distributions.     

Structure of the high-order Boltzmann machine from independencemaps

In this paper we consider the determination of the structure of the high-order Boltzmann machine (HOBM), a stochastic recurrent network for approximating probability distributions. We obtain the structure of the HOBM, the hypergraph of connections, from conditional independences of the probability distribution to model. We assume that an expert provides these conditional independences and from them we build independence maps, Markov and Bayesian networks, which represent conditional independences through undirected graphs and directed acyclic graphs respectively. From these independence maps we construct the HOBM hypergraph. The central aim of this paper is to obtain a minimal hypergraph. Given that different orderings of the variables provide in general different Bayesian networks, we define their intersection hypergraph. We prove that the intersection hypergraph of all the Bayesian networks (N!) of the distribution is contained by the hypergraph of the Markov network, it is more simple, and we give a procedure to determine a subset of the Bayesian networks that verifies this property. We also prove that the Markov network graph establishes a minimum connectivity for the hypergraphs from Bayesian networks.     

Quantum inferring acausal structures and the Monty Hall problem

This paper presents a quantum version of the Monty Hall problem based upon the quantum inferring acausal structures, which can be identified with generalization of Bayesian networks. Considered structures are expressed in formalism of quantum information theory, where density operators are identified with quantum generalization of probability distributions. Conditional relations between quantum counterpart of random variables are described by quantum conditional operators. Presented quantum inferring structures are used to construct a model inspired by scenario of well-known Monty Hall game, where we show the differences between classical and quantum Bayesian reasoning.     

On the Sequential Accumulation of Evidence

In this paper, we introduce a method for sequentially accumulating evidence as it pertains to an active observer seeking to identify an object in a known environment. We develop a probabilistic framework, based on a generalized inverse theory, where assertions are represented by conditional probability density functions. This leads to a sequential recognition strategy in which evidence is accumulated over successive viewpoints using Bayesian chaining until a definitive assertion can be made. To illustrate the theory we show how the characteristics of belief distributions can be exploited in a model-based recognition problem, where the task is to identify an unknown model from a database of known objects on the basis of parameter estimates. We illustrate the robustness of the algorithm through recognition experiments in two very different contexts: (1) a highly structured recognition context where 3-D parametric models can be estimated directly from range data, (2) a complex environment, where the relationship between the data and the model is learned through an appearance-based strategy. Specifically, the flow fields computed through the object's motion are used as structural signatures for recognition.     

扩展时段时序逻辑的模型、一致性和推理

给出了扩展时段时序逻辑的时间Petri网（TPN）模型构造方法，在构造模型的同时对时序关系进行一致性检验，在模型的基础上提出了一种时序关系推理算法，这种推理算法基于TPN模型的性质及基本不等式规则，可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系，这种推广理算法的优势在于利用了TNP模型的分析技术，减小了推理的时间复杂度比单纯利用不等式规则的推理更直观，也更简单，是一种有效的方法，最后，对扩展时段时序逻辑的TPN模型进行了扩充，增强了其模型和分析的能力。     

New results for Constraint Markov Chains

This paper studies compositional reasoning theories for stochastic systems. A specification theory combines notions of specification and implementation with satisfaction and refinement relations, and a set of operators that together support stepwise design. One of the first behavioral specification theories introduced for stochastic systems is the one of Interval Markov Chains (IMCs), which are Markov Chains whose probability distributions are replaced by a conjunction of intervals. In this paper, we show that IMCs are not closed under conjunction, which gives a formal proof of a conjecture made in several recent works.In order to leverage this problem, we suggested to work with Constraint Markov Chains (CMCs) that is another specification theory where intervals are replaced with general constraints. Contrary to IMCs, one can show that CMCs enjoy the closure properties of a specification theory. In addition, we propose aggressive abstraction procedures for CMCs. Such abstractions can be used either to combat the state-space explosion problem, or to simplify complex constraints. In particular, one can show that, under some assumptions, the behavior of any CMC can be abstracted by an IMC.Finally, we propose an algorithm for counter-example generation, in case a refinement of two CMCs does not hold. We present a tool that implements our results. Implementing CMCs is a complex process and relies on recent advances made in decision procedures for theory of reals.     

Learning symmetric causal independence models

Causal independence modelling is a well-known method for reducing the size of probability tables, simplifying the probabilistic inference and explaining the underlying mechanisms in Bayesian networks. Recently, a generalization of the widely-used noisy OR and noisy AND models, causal independence models based on symmetric Boolean functions, was proposed. In this paper, we study the problem of learning the parameters in these models, further referred to as symmetric causal independence models. We present a computationally efficient EM algorithm to learn parameters in symmetric causal independence models, where the computational scheme of the Poisson binomial distribution is used to compute the conditional probabilities in the E-step. We study computational complexity and convergence of the developed algorithm. The presented EM algorithm allows us to assess the practical usefulness of symmetric causal independence models. In the assessment, the models are applied to a classification task; they perform competitively with state-of-the-art classifiers.     

Asymmetric decomposability and persegram representation in coherent conditional probability theory

In this paper we introduce an asymmetric counterpart of decomposable independence models, motivated by stochastic cs-independence in the context of coherent conditional probability which is generally not symmetric. We provide a full algebraic characterization of this class of models and we show they are completely representable by means of persegrams. Finally, decomposition of a coherent conditional probability according to a persegram is presented.     

随机Petri网模型的精化设计

随机Petri网的模型技术有多种不同的方法.简单地使用模型技术去模拟复杂的系统,势必造成状态空间的爆炸,而无法分析系统性能.模型精化技术可以开发出紧凑的模型,暴露出原模型中子模型的独立性和相互依存关系,为模型的分解求解奠定基础.该文以多服务器多队列系统模型的精化设计为例,展示利用变迁可实施谓词和随机开关进行模型精化的方法.文章还讨论了多服务器多任务系统的调度、选择控制方案,并提供了这些方案的随机Petri网模型.