Distributed control of uncertain systems using superpositions of linear operators

Control in the natural environment is difficult in part because of uncertainty in the effect of actions. Uncertainty can be due to added motor or sensory noise, unmodeled dynamics, or quantization of sensory feedback. Biological systems are faced with further difficulties, since control must be performed by networks of cooperating neurons and neural subsystems. Here, we propose a new mathematical framework for modeling and simulation of distributed control systems operating in an uncertain environment. Stochastic differential operators can be derived from the stochastic differential equation describing a system, and they map the current state density into the differential of the state density. Unlike discrete-time Markov update operators, stochastic differential operators combine linearly for a large class of linear and nonlinear systems, and therefore the combined effects of multiple controllable and uncontrollable subsystems can be predicted. Design using these operators yields systems whose statistical behavior can be specified throughout state-space. The relationship to Bayesian estimation and discrete-time Markov processes is described.     

Structured transfer function matrices and integer matrices: the computation of the generic McMillan degree and infinite zero structure

The computation of the McMillan degree and structure at infinity of a transfer function model is considered for the family of early design models, referred to as Structured Transfer Function (STF) matrices. Such transfer functions have certain elements fixed to zero, some elements being constant and other elements expressing some identified dominant dynamics of the system. For the family of large dimension STF matrices the computation of the generic McMillan degree and structure at infinity are considered using genericity arguments which lead to optimization problems of integer matrices. A novel approach is introduced here that uses the notion of “irreducibility” of integer matrices, which is developed as the equivalent of irreducibility (properness) of polynomial matrices. This new notion provides the means for exploiting the structure of integer matrices and enables the termination of searching processes in a reduced number of steps, thus leading to an efficient new algorithm for the computation of the generic value of the McMillan degree and the structure at infinity of STFs. Links are made to standard optimization problems and to graph theory. The formulation of the optimization algorithm in terms of bipartite graphs offers better results and reduces the computational effort.     

A unified approach to Markov decision problems and performance sensitivity analysis with discounted and average criteria: multichain cases

We propose a unified framework to Markov decision problems and performance sensitivity analysis for multichain Markov processes with both discounted and average-cost performance criteria. With the fundamental concept of performance potentials, we derive both performance-gradient and performance-difference formulas, which play the central role in performance optimization. The standard policy iteration algorithms for both discounted- and average-reward MDPs can be established using the performance-difference formulas in a simple and intuitive way; and the performance-gradient formulas together with stochastic approximation may lead to new optimization schemes. This sensitivity-based point of view of performance optimization provides some insights that link perturbation analysis, Markov decision processes, and reinforcement learning together. The research is an extension of the previous work on ergodic Markov chains (Cao, Automatica 36 (2000) 771).     

Characterising trader manipulation in a limit-order driven market

Use of trading strategies to mislead other market participants, commonly termed trade-based market manipulation, has been identified as a major problem faced by present day stock markets. Although some mathematical models of trade-based market manipulation have been previously developed, this work presents a framework for manipulation in the context of a realistic computational model of a limit-order market. The Maslov limit order market model is extended to introduce manipulators and technical traders. We show that “pump and dump” manipulation is not possible with traditional Maslov (liquidity) traders. The presence of technical traders, however, makes profitable manipulation possible. When exploiting the behaviour of technical traders, manipulators can wait some time after their buying phase before selling, in order to profit. Moreover, if technical traders believe that there is an information asymmetry between buy and sell actions, the manipulator effort required to perform a “pump and dump” is comparatively low, and a manipulator can generate profits even by selling immediately after raising the price.     

图像隐写分析中小波系数相关性的研究与应用*

提出了一种针对空域图像隐写的盲检测方法。利用互信息分析秘密信息嵌入对图像小波系数在尺度方向和空间方向相关性的影响,使用马尔可夫模型挖掘小波系数层内和层间相关性,提取转移概率矩阵作为特征。针对LSB匹配和随机调制隐写算法的实验表明,此方法能有效检测未经JPEG压缩过的含密图像,相比现有空域盲检测方法,对低嵌入率含密图像的正确检测率提高约8%14% 。     

遗传算法的平均收敛速度及其估计

给出了独立于表示的变异算子和交叉算子的数学描述, 建立了遗传算法种群的精确马尔可夫链模型, 导出了种群中最佳个体的马尔可夫链及其随机矩阵, 将遗传算法的平均收敛速度定义为最佳个体转移至吸收态的平均吸收时间的数学期望, 提出了应用最佳个体的随机矩阵估计遗传算法平均收敛速度的理论方法和计算步骤.     

Statistical probabilistic model checking with a focus on time-bounded properties

Probabilistic verification of continuous-time stochastic processes has received increasing attention in the model-checking community in the past five years, with a clear focus on developing numerical solution methods for model checking of continuous-time Markov chains. Numerical techniques tend to scale poorly with an increase in the size of the model (the “state space explosion problem”), however, and are feasible only for restricted classes of stochastic discrete-event systems. We present a statistical approach to probabilistic model checking, employing hypothesis testing and discrete-event simulation. Since we rely on statistical hypothesis testing, we cannot guarantee that the verification result is correct, but we can at least bound the probability of generating an incorrect answer to a verification problem.     

Detecting anomalous patterns in time-series data using sparse hierarchically parameterized transition matrices

Anomaly detection in time-series data is a relevant problem in many fields such as stochastic data analysis, quality assurance, and predictive modeling. Markov models are an effective tool for time-series data analysis. Previous approaches utilizing Markov models incorporate transition matrices (TMs) at varying dimensionalities and resolutions. Other analysis methods treat TMs as vectors for comparison using search algorithms such as the nearest neighbors comparison algorithm, or use TMs to calculate the probability of discrete subsets of time-series data. We propose an analysis method that treats the elements of a TM as random variables, parameterizing them hierarchically. This approach creates a metric for determining the “normalcy” of a TM generated from a subset of time-series data. The advantages of this novel approach are discussed in terms of computational efficiency, accuracy of anomaly detection, and robustness when analyzing sparse data. Unlike previous approaches, this algorithm is developed with the expectation of sparse TMs. Accounting for this sparseness significantly improves the detection accuracy of the proposed method. Detection rates in a variety of time-series data types range from (97 % TPR, 2.1 % FPR) to (100 % TPR, <0.1 % FPR) with very small sample sizes (20–40 samples) in data with sparse transition probability matrices.     

Evolution of condensed subgroup of political participation based on mobile phone

In this paper, a comprehensive numerical study that investigates the evolutionary process of condensed subgroup in political participation based on mobile phone was carried out, putting forward the conception of “condensed subgroup cardinality” considering that it is a finite Markov chain. Then a mathematical model was constructed which allows us to depict the evolutionary process of condensed subgroup and analyze a public media forum based on mobile phone with accuracy. The numerical result demonstrates the usability of this model in predicting the evolutionary process of virtual condensed subgroup based on mobile phone. Analyses on the evolutionary mechanism of condensed subgroup were also given and finally a preliminary stochastic differential equation was advanced to describe it.     

Coalgebraic semantics for timed processes

We give a coalgebraic formulation of timed processes and their operational semantics. We model time by a monoid called a “time domain”, and we model processes by “timed transition systems”, which amount to partial monoid actions of the time domain or, equivalently, coalgebras for an “evolution comonad” generated by the time domain. All our examples of time domains satisfy a partial closure property, yielding a distributive law of a monad for total monoid actions over the evolution comonad, and hence a distributive law of the evolution comonad over a dual comonad for total monoid actions. We show that the induced coalgebras are exactly timed transition systems with delay operators. We then integrate our coalgebraic formulation of time qua timed transition systems into Turi and Plotkin’s formulation of structural operational semantics in terms of distributive laws. We combine timing with action via the more general study of the combination of two arbitrary sorts of behaviour whose operational semantics may interact. We give a modular account of the operational semantics for a combination induced by that of each of its components. Our study necessitates the investigation of products of comonads. In particular, we characterise when a monad lifts to the category of coalgebras for a product comonad, providing constructions with which one can readily calculate.     

Numerical Modeling of Dependent Credit Rating Transitions with Asynchronously Moving Industries

Two models of dependent credit rating migrations governed by industry-specific Markovian matrices, are considered. Caused by macroeconomic factors, positive and negative unobserved tendencies, encoded as values “1” or “0” of the corresponding variables, modify the transition probabilities and render the evolutions dependent. They are neither synchronized across industry sectors, nor over credit classes: an upswing in some of them can coexist with a decline of the rest. The models are tested on Standard and Poor’s data. MATLAB optimization software and maximum likelihood estimators are used. Obtained distributions of the hidden variables demonstrate that the considered industries migrate asynchronously trough credit classes. Since downgrading probabilities are less affected by the unobserved tendencies, estimated by Monte-Carlo simulations distributions of defaults, exhibit lighter, than for the known coupling models, tails for schemes with asynchronously moving industries. Moreover, the lightest tails were obtained in the case of industry-specific transition matrices.     

PH-graphs for analyzing shortest path problems with correlated traveling times

This paper presents a new approach to model weighted graphs with correlated weights at the edges. Such models are important to describe many real world problems like routing in computer networks or finding shortest paths in traffic models under realistic assumptions. Edge weights are modeled by phase type distributions (PHDs), a versatile class of distributions based on continuous time Markov chains (CTMCs). Correlations between edge weights are introduced by adding dependencies between the PHDs of adjacent edges using transfer matrices. The new model class, denoted as PH graphs (PHGs), allows one to formulate many shortest path problems as the computation of an optimal policy in a continuous time Markov decision process (CTMDP). The basic model class is defined, methods to parameterize the required PHDs and transfer matrices based on measured data are introduced and the formulation of basic shortest path problems as solutions of CTMDPs with the corresponding solution algorithms are also provided. Numerical examples for some typical stochastic shortest path problems demonstrate the usability of the new approach.     

Stochastic process semantics for dynamical grammars

We define a class of probabilistic models in terms of an operator algebra of stochastic processes, and a representation for this class in terms of stochastic parameterized grammars. A syntactic specification of a grammar is formally mapped to semantics given in terms of a ring of operators, so that composition of grammars corresponds to operator addition or multiplication. The operators are generators for the time-evolution of stochastic processes. The dynamical evolution occurs in continuous time but is related to a corresponding discrete-time dynamics. An expansion of the exponential of such time-evolution operators can be used to derive a variety of simulation algorithms. Within this modeling framework one can express data clustering models, logic programs, ordinary and stochastic differential equations, branching processes, graph grammars, and stochastic chemical reaction kinetics. The mathematical formulation connects these apparently distant fields to one another and to mathematical methods from quantum field theory and operator algebra. Such broad expressiveness makes the framework particularly suitable for applications in machine learning and multiscale scientific modeling.      

On Detectability and Observability of Discrete‐Time Stochastic Markov Jump Systems with State‐Dependent Noise

This paper mainly studies the notions of detectability and observability for discrete‐time stochastic Markov jump systems with state‐dependent noise. Two concepts, called “W‐detectability” and “W‐observability,” for such systems are introduced, and are shown to coincide with the other concepts on detectability and observability reported recently in literature. Moreover, some criteria and interesting properties for both W‐detectability and W‐observability are obtained.     

A memory based differential evolution algorithm for unconstrained optimization

In optimization, the performance of differential evolution (DE) and their hybrid versions exist in the literature is highly affected by the inappropriate choice of its operators like mutation and crossover. In general practice, during simulation DE does not employ any strategy of memorizing the so-far-best results obtained in the initial part of the previous generation. In this paper, a new “Memory based DE (MBDE)” presented where two “swarm operators” have been introduced. These operators based on the pBEST and gBEST mechanism of particle swarm optimization. The proposed MBDE is employed to solve 12 basic, 25 CEC 2005, and 30 CEC 2014 unconstrained benchmark functions. In order to further test its efficacy, five different test system of model order reduction (MOR) problem for single-input and single-output system are solved by MBDE. The results of MBDE are compared with state-of-the-art algorithms that also solved those problems. Numerical, statistical, and graphical analysis reveals the competency of the proposed MBDE.     

Stochastic learning and optimization—A sensitivity-based approach

We introduce a sensitivity-based view to the area of learning and optimization of stochastic dynamic systems. We show that this sensitivity-based view provides a unified framework for many different disciplines in this area, including perturbation analysis, Markov decision processes, reinforcement learning, identification and adaptive control, and singular stochastic control; and that this unified framework applies to both the discrete event dynamic systems and continuous-time continuous-state systems. Many results in these disciplines can be simply derived and intuitively explained by using two performance sensitivity formulas. In addition, we show that this sensitivity-based view leads to new results and opens up new directions for future research. For example, the n th bias optimality of Markov processes has been established and the event-based optimization may be developed; this approach has computational and other advantages over the state-based approaches.     

Stuttering for Abstract Probabilistic Automata

Probabilistic Automata (PAs) are a widely-recognized mathematical framework for the specification and analysis of systems with non-deterministic and stochastic behaviors. In a series of recent papers, we proposed Abstract Probabilistic Automata (APAs), a new abstraction framework for representing possibly infinite sets of PAs. We have developed a complete abstraction theory for APAs, and also proposed the first specification theory for them. APAs support both satisfaction and refinement operators, together with classical stepwise design operators.One of the major drawbacks of APAs is that the formalism cannot capture PAs with hidden actions – such actions are however necessary to describe behaviors that shall not be visible to a third party. In this paper, we revisit and extend the theory of APAs to such context. Our first main result takes the form of proposal for a new probabilistic satisfaction relation that captures several definitions of PAs with hidden actions. Our second main contribution is to revisit all the operations and properties defined on APAs for such notions of PAs. Finally, we also establish the first link between stochastic modal logic and APAs, hence linking an automata-based specification theory to a logical one.     

A new disk-based technique for solving the largeness problem of stochastic modeling formalisms

Stochastic modeling formalisms such as stochastic Petri nets, generalized stochastic Petri nets, and stochastic reward nets can be used to model and evaluate the dynamic behavior of realistic computer systems. Once we translate the stochastic system model to the underlying corresponding Markov Chain (MC), the developed MC grows wildly to several hundred thousands states. This problem is known as the largeness problem. To tolerate the largeness problem of Markov models, several iterative and direct methods have been proposed in the literature. Although the iterative methods provide a feasible solution for most realistic systems, a major problem appears when these methods fail to reach a solution. Unfortunately, the direct method represents an undesirable numerical technique for tolerating large matrices due to the fill-in problem. In order to solve such problem, in this paper, we develop a disk-based segmentation (DBS) technique based on modifying the Gauss Elimination (GE) technique. The proposed technique has the capability of solving the consequences of the fill-in problem without making assumptions about the underlying structure of the Markov processes of the developed model. The DBS technique splits the matrix into a number of vertical segments and uses the hard disk to store these segments. Using the DBS technique, we can greatly reduce the memory required as compared to that of the GE technique. To minimize the increase in the solution time due to the disk accessing processes, the DBS utilizes a clever management technique for such processes. The effectiveness of the DBS technique has been demonstrated by applying it to a realistic model for the Kanban manufacturing system.