Learning Probabilistic Automata and Markov Chains via Queries

We investigate the problem of learning probabilistic automata and Markov chains via queries in the teacher-student learning model. Probabilistic automata and Markov chains are probabilistic extensions of finite state automata and have similar structures. We discuss some natural oracles associated with probabilistic automata and Markov chains. We present polynomial-time algorithms for learning probabilistic automata and Markov Chains using these oracles.     

基于Markov链的ERIM系统智能体协作研究

从系统角度出发在对ERIM(企业风险集成管理)系统各要素进行扼要分析的基础上,引入人工智能(Agent)理论将系统的各个要素看作是许多依据状态进行分类的不同的单一Agent的集合,给出了三种这些Agent之间的协作方式;运用Markov链来描述这些单一Agent之间的动态变迁的协作机制,依据Bayes法则确定转移概率,由此可为ERIM的多智能体系统提供一个形式化的数学框架和处理工具。     

Entropy-Based Markov Chains for Multisensor Fusion

This paper proposes an entropy based Markov chain (EMC) fusion technique and demonstrates its applications in multisensor fusion. Self-entropy and conditional entropy, which measure how uncertain a sensor is about its own observation and joint observations respectively, are adopted. We use Markov chain as an observation combination process because of two major reasons: (a) the consensus output is a linear combination of the weighted local observations; and (b) the weight is the transition probability assigned by one sensor to another sensor. Experimental results show that the proposed approach can reduce the measurement uncertainty by aggregating multiple observations. The major benefits of this approach are: (a) single observation distributions and joint observation distributions between any two sensors are represented in polynomial form; (b) the consensus output is the linear combination of the weighted observations; and (c) the approach suppresses noisy and unreliable observations in the combination process.     

基于马尔科夫链自适应能力任务分派系统设计

当分布式系统中各处理结点相互完全独立,并且在对其他结点的状态不是很了解情况下,利用组合数学和随机过程的方法提出一种机制,该机制能使各结点在没有全局管理者的参与下,仅根据系统运行的反馈决定下一步的任务,从而使整个系统的任务分配达到最优。该方法能很好地处理最普遍的任务分派问题。     

用马尔科夫链对Linux进程行为的异常检测

用马尔科夫链对序列数据进行分析时,其预报准确率对于序列演变的异常与否相当敏感,而Linux进程可由一系列的系统调用序列来表征。据此,该文用马尔科夫链对Linux进程的系统调用序列进行行为模式提取并作异常检测。同时,还考虑了序列的顺序关系,使得模式有了合理的解释。     

Finite dimensional predictors for hidden Markov chains

A continuous time Markov chain is observed in Gaussian noise. Finite dimensional normalized and unnormalized (Zakai) predictors are obtained for the state of the chain, for the number of jumps from one state to another and for the occupation time in any state.     

Towards a Formal Semantics for UML/MARTE State Machines Based on Hierarchical Timed Automata

UML is a widely-used,general purpose modeling language.But its lack of a rigorous semantics forbids the thorough analysis of designed solution,and thus precludes the discovery of significant problems at design time.To bridge the gap,the paper investigates the underlying semantics of UML state machine diagrams,along with the time-related modeling elements of MARTE,the profile for modeling and analysis of real-time embedded systems,and proposes a formal operational semantics based on extended hierarchical timed automata.The approach is exemplified on a simple example taken from the automotive domain.Verification is accomplished by translating designed models into the input language of the UPPAAL model checker.     

A Markov chain model for dynamic binary search tree behaviour

We present a Markov chain model for the analysis of the behaviour of binary search trees (BSTs) under the dynamic conditions of insertions and deletions. The model is based on a data structure called a lineage tree, which provides a compact representation of different BST structures while still retaining enough information to model the effect of insertions and deletions and to compute average path length and tree height. Different lineages in the lineage tree correspond to states in the Markov chain. Transition probabilities are based on the number of BST structures corresponding to each lineage. The model is based on a similar lineage tree model developed for B-trees. The BST model is not intended for practical computations, but rather as a demonstration of the generalizability of the lineage tree approach for modeling data structures such as B-trees, B*-trees, B⁺-trees, BSTs, etc.     

Computing the Nash Bargaining Solution for Multiple Players in Discrete-Time Markov Chains Games

Abstract

This paper presents a novel method for computing the Nash bargaining equilibrium for finite, ergodic and controllable Markov chains games. To solve the bargaining process we first set the disagreement point as the Nash equilibrium of the problem, then to find the new agreement point we follow the bargaining model presented by Nash. We exemplify the game formulation in terms of nonlinear programing equations implementing the Lagrange principle. For ensuring the convergence of the game to an equilibrium point we employ the Tikhonov’s regularization method. For solving the bargaining problem we make use of the extraproximal optimization approach. Finally, we validate the proposed method by a numerical example for a three-person bargaining situation.     

基于迹语义的网络安全协议形式化分析

形式化方法是提高软件系统,特别是safety-critical系统的安全性与可靠性的重要手段.本文提出了一种新的简单的迹语义,用于刻画协议部分安全性质,即只针对协议规约的单个主体,此技术支持协议设计者对安全性质进行形式化规约.运用此技术和模型检测器SPIN找到了两种针对TMN协议的攻击,证明了此方法的实用性,可方便地用于其它网络安全协议验证.     

基于马尔科夫链的民族地区毒品犯罪预测研究

毒品的非法生产、需求以及贩运呈现出一种巨大规模的上升趋势,特别是边疆少数民族地区的毒品犯罪问题更加引人关注。针对此问题,大多是从社会学的角度进行研究,提出了采用马尔科夫链的方法,对边疆少数民族地区收集的犯罪数据进行统计分析、建模。实验结果表明,预测毒品犯罪案件数与实际发生的毒品犯罪案件数相比,达到了96．52％的预测准确率。结论是,通过马尔科夫链来进行民族地区的毒品犯罪预测研究,可获得更加合理、准确的预测结果,具有更高的有效性和实用性。     

相似时间序列挖掘方法

马尔可夫状态转移矩阵描述了随机过程的动态特性，而时间序列可以认为是这一动态特性的外在体现，将二者有效地结合起来为相似时间序列挖掘提供了一种有效的新方法。     

Modeling alternatives for fuzzy Markov chain-based classification of multitemporal remote sensing data

In this work, we investigate the application of modeling alternatives regarding fuzzy Markov chain-based, multitemporal, cascade classification of remote sensing data. From a theoretical viewpoint, alternative designs for the fuzzy Markov chain-based model are formally presented. From a pragmatic perspective, experimental results are discussed and analyzed, providing a deeper understanding of the virtues and odds of multitemporal remote sensing data classification based on fuzzy Markov chains. We claim that the key components of the fuzzy Markov chain-based, multitemporal classification model with respect to its alternative designs are the t-norm and s-norm operators, and the fuzzy aggregation function. The main objective of this paper is to investigate how a particular design may affect the classification performance. In addition, this paper aims at assessing the impact of the monotemporal classifiers’ accuracies on the quality of the multitemporal classification outcome, according to the selected design alternatives. In conclusion, this paper presents design guidelines for both the developer of image analysis systems and the designer of classification methods based on fuzzy Markov chains.     

Quasi-Monte Carlo methods for Markov chains with continuous multi-dimensional state space

We describe a quasi-Monte Carlo method for the simulation of discrete time Markov chains with continuous multi-dimensional state space. The method simulates copies of the chain in parallel. At each step the copies are reordered according to their successive coordinates. We prove the convergence of the method when the number of copies increases. We illustrate the method with numerical examples where the simulation accuracy is improved by large factors compared with Monte Carlo simulation.     

A note on exponential stability of the nonlinear filter for denumerable Markov chains

Asymptotic stability of the optimal filter with respect to its initial conditions is investigated in this paper. Under the assumption that the observation function is one to one and the observation noise is sufficiently small, it is shown that exponential stability of the nonlinear filter holds for a large class of denumerable Markov chains, including all finite Markov chains. Throughout this paper, ergodicity of the signal process is not assumed.     

Conditional probability Markov chain simulation based reliability analysis method for nonnormal variables

Based on fast Markov chain simulation for generating the samples distributed in failure region and saddlepoint approximation(SA) technique,an efficient reliability analysis method is presented to evaluate the small failure probability of non-linear limit state function(LSF) with non-normal variables.In the presented method,the failure probability of the non-linear LSF is transformed into a product of the failure probability of the introduced linear LSF and a feature ratio factor.The introduced linear LSF wh...     

基于最优功率控制和马尔可夫链优化的异构无线网络

为了提高异构无线网络的资源利用率以及网络吞吐量,提出一种基于最优功率控制和马尔可夫链优化的异构无线网络,通过建立异构网络模型对异构网络的业务负载情况进行分析,采用有限容量下的最优功率控制方法来使业务能够选择合适的接入网络,并采用基于马尔可夫链来进行网络吞吐量优化,在对不同形式的网络进行速率分配时,采用了多权重优化进行求解最优解,可以降低网络的阻塞情况,提高网络的利用效率.实验仿真结果及分析表明,该算法在提高网络吞吐量、减少网络利用效率上具有较好的效果.     

一种基于多智能体的企业供应链系统开发平台研究

将多主体技术应用于供应链系统的开发,提出了一种基于多智能体的供应链系统结构,设计实现了基于多智能主体的企业供应链系统开发平台MA-SCSP。在对供应链主体的结构进行模块化的基础上,就系统实现的核心问题——主体计划库的设计提出了一种实用的有限状态自动机模板结构,并给出了计划库的语法定义,支持平台用户对实际系统的快速开发。     

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models

Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.     

Hidden Markov random field models for TCA image analysis

Tooth Cementum Annulation (TCA) is an age estimation method carried out on thin cross sections of the root of mammalian teeth. Age is computed by adding the tooth eruption age to the count of annual incremental lines which are called tooth rings and appear in the cementum band. The number of rings is computed from an intensity (gray scale) image of the cementum band, by estimating the average ring width and then dividing the area of the cementum band by this estimate. The ring width is estimated by modelling the image by a hidden Markov random field, where intensities are assumed to be pixelwise conditionally independent and normally distributed, given a Markov random field of hidden binary labels, representing the“true scene”. To incorporate image macro-features (the long-range dependence among intensities and the quasi-periodicity in the placement of tooth rings), the label random field is defined by an energy function that depends on a parametric Gabor filter, convolved with the true scene. The filter parameter represents the unknown of main interest, i.e. the average width of the rings. The model is estimated through an EM algorithm, relying on the mean field approximation of the hidden label distribution and allows to predict the locations of the rings in the image.