Error bounds of optimization algorithms for semi-Markov decision processes

Cao's work shows that, by defining an α-dependent equivalent infinitesimal generator A _α, a semi-Markov decision process (SMDP) with both average- and discounted-cost criteria can be treated as an α-equivalent Markov decision process (MDP), and the performance potential theory can also be developed for SMDPs. In this work, we focus on establishing error bounds for potential and A _α-based iterative optimization methods. First, we introduce an α-uniformized Markov chain (UMC) for a SMDP via A _α and a uniformized parameter, and show their relations. Especially, we obtain that their performance potentials, as solutions of corresponding Poisson equations, are proportional, so that the studies of a SMDP and the α-UMC based on potentials are unified. Using these relations, we derive the error bounds for a potential-based policy-iteration algorithm and a value-iteration algorithm, respectively, when there exist various calculation errors. The obtained results can be applied directly to the special models, i.e., continuous-time MDPs and Markov chains, and can be extended to some simulation-based optimization methods such as reinforcement learning and neuro-dynamic programming, where estimation errors or approximation errors are common cases. Finally, we give an application example on the look-ahead control of a conveyor-serviced production station (CSPS), and show the corresponding error bounds.     

The optimal robust control policy for uncertain semi-Markov control processes

The optimization problems of Markov control processes (MCPs) with exact knowledge of system parameters, in the form of transition probabilities or infinitesimal transition rates, can be solved by using the concept of Markov performance potential which plays an important role in the sensitivity analysis of MCPs. In this paper, by using an equivalent infinitesimal generator, we first introduce a definition of discounted Poisson equations for semi-Markov control processes (SMCPs), which is similar to that for MCPs, and the performance potentials of SMCPs are defined as solution of the equation. Some related optimization techniques based on performance potentials for MCPs may be extended to the optimization of SMCPs if the system parameters are known with certainty. Unfortunately, exact values of the distributions of the sojourn times at some states or the transition probabilities of the embedded Markov chain for a large-scale SMCP are generally difficult or impossible to obtain, which leads to the uncertainty of the semi-Markov kernel, and thereby to the uncertainty of equivalent infinitesimal transition rates. Similar to the optimization of uncertain MCPs, a potential-based policy iteration method is proposed in this work to search for the optimal robust control policy for SMCPs with uncertain infinitesimal transition rates that are represented as compact sets. In addition, convergence of the algorithm is discussed.     

Iterative convergence of passage-time densities in semi-Markov performance models

Passage-time densities are important for the detailed performance analysis of distributed computer and communicating systems. We provide a proof and demonstration of a practical iterative algorithm for extracting complete passage-time densities from expressive semi-Markov systems. We end by showing its application to a distributed web-server cluster model of 15.9 million states.     

Fluid computation of passage-time distributions in large Markov models

Recent developments in the analysis of large Markov models facilitate the fast approximation of transient characteristics of the underlying stochastic process. Fluid analysis makes it possible to consider previously intractable models whose underlying discrete state space grows exponentially as model components are added. In this work, we show how fluid-approximation techniques may be used to extract passage-time measures from performance models. We focus on two types of passage measure: passage times involving individual components, as well as passage times which capture the time taken for a population of components to evolve.Specifically, we show that for models of sufficient scale, global passage-time distributions can be well approximated by a deterministic fluid-derived passage-time measure. Where models are not of sufficient scale, we are able to generate upper and lower approximations for the entire cumulative distribution function of these passage-time random variables, using moment-based techniques. Additionally, we show that, for passage-time measures involving individual components, the cumulative distribution function can be directly approximated by fluid techniques.Finally, using the GPA tool, we take advantage of the rapid fluid computation of passage times to show how a multi-class client-server system can be optimised to satisfy multiple service level agreements.     

半Markov决策过程折扣模型与平均模型之间的关系

首先分别在折扣代价与平均代价性能准则下,讨论了一类半M arkov决策问题.基于性能势方法,导出了由最优平稳策略所满足的最优性方程.然后讨论了两种模型之间的关系,表明了平均模型的有关结论,可以通过对折扣模型相应结论取折扣因子趋于零时的极限来得到.     

An aggregation heuristic for large scale p-median problem

The p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity.In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a “core” heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities.     

On a family of multivariate copulas for aggregation processes

We introduce a family of multivariate copulas - a special type of n-ary aggregation operations - depending on a univariate function. This family is used in the construction of a special aggregation operation that satisfies a Lipschitz condition. Several examples are provided and some statistical properties are studied.     

Minimum-risk training for semi-Markov conditional random fields with application to handwritten Chinese/Japanese text recognition

Semi-Markov conditional random fields (semi-CRFs) are usually trained with maximum a posteriori (MAP) criterion which adopts the 0/1 cost for measuring the loss of misclassification. In this paper, based on our previous work on handwritten Chinese/Japanese text recognition (HCTR) using semi-CRFs, we propose an alternative parameter learning method by minimizing the risk on the training set, which has unequal misclassification costs depending on the hypothesis and the ground-truth. Based on this framework, three non-uniform cost functions are compared with the conventional 0/1 cost, and training data selection is incorporated to reduce the computational complexity. In experiments of online handwriting recognition on databases CASIA-OLHWDB and TUAT Kondate, we compared the performances of the proposed method with several widely used learning criteria, including conditional log-likelihood (CLL), softmax-margin (SMM), minimum classification error (MCE), large-margin MCE (LM-MCE) and max-margin (MM). On the test set (online handwritten texts) of ICDAR 2011 Chinese handwriting recognition competition, the proposed method outperforms the best system in competition.     

SMDP基于性能势的神经元动态规划

An alpha-uniformized Markov chain is defined by the concept of equivalent infinitesimal generator for a semi-Markov decision process (SMDP) with both average- and discounted-criteria. According to the relations of their performance measures and performance potentials, the optimization of an SMDP can be realized by simulating the chain. For the critic model of neuro-dynamic programming (NDP), a neuro-policy iteration (NPI) algorithm is presented, and the performance error bound is shown as there are approximate error and improvement error in each iteration step. The obtained results may be extended to Markov systems, and have much applicability. Finally, a numerical example is provided.     

Maximum likelihood estimation for generalized semi-markov processes

Parametric statistical inference for generalized semi-Markov processes is addressed. This class of processes encompasses a large number of real-world discrete-event stochastic systems. Because of its properties (e.g., consistency, asymptotic normality, etc.), maximum likelihood estimation is considered here. Under reasonable conditions on the process, we show that a maximum likelihood estimator exists, and that it converges to the true parameter at ratet ^–1/2, wheret is the length of the observation period. A related estimator, which is typically easier to compute, is also introduced. We show that the use of this estimator results in no loss of statistical efficiency. It is also shown that the estimation problem does decouple into separate subproblems when the process' transition probabilities and event distributions depend on different parameters.     

半Markov过程基于性能势的灵敏度分析和性能优化

基于性能势的方法 ,研究了一类半Markov过程 (SMP)的性能灵敏度分析和平均费用下的性能优化问题 .将SMP转化为与之等价的离散时间Markov链 (DTMC) ,利用DTMC的性能势 ,对SMP进行灵敏度分析和性能优化 ,得到了SMP基于DTMC性能势的灵敏度分析公式和最优性方程 .最后给出了一个数值例子以表明该方法的应用 .     

A time aggregation approach to Markov decision processes

We propose a time aggregation approach for the solution of infinite horizon average cost Markov decision processes via policy iteration. In this approach, policy update is only carried out when the process visits a subset of the state space. As in state aggregation, this approach leads to a reduced state space, which may lead to a substantial reduction in computational and storage requirements, especially for problems with certain structural properties. However, in contrast to state aggregation, which generally results in an approximate model due to the loss of Markov property, time aggregation suffers no loss of accuracy, because the Markov property is preserved. Single sample path-based estimation algorithms are developed that allow the time aggregation approach to be implemented on-line for practical systems. Some numerical and simulation examples are presented to illustrate the ideas and potential computational savings.     

Redundancy-aware SOAP messages compression and aggregation for enhanced performance

Many organizations around the world have started to adopt Web services as well as server farms and clouds hosted by large enterprise and data centers for various applications. Web Services offer several advantages over other communication technologies. However, they have high latency and often suffer from congestion and bottlenecks due to the massive load generated by web service requests from large numbers of end users. SOAP (Simple Object Access Protocol) is the basic XML-based communication protocol of Web services. XML is a verbose encoding language in comparison with other technologies such CORBA and RMI. In this paper, two new redundancy-aware SOAP Web message aggregation models - Two-bit and One-bit XML status tree - are proposed to enable the Web servers to aggregate SOAP responses and send them back as one compact aggregated message in order to reduce the required bandwidth, latency, and improve the overall performance of Web services. XML message compressibility, the Jaccard based clustering technique, and the vector space model are three similarity measurements that are proposed to cluster SOAP messages as groups based on their similarity degree. The clustering based similarity measurements enable the aggregation techniques to potentially reduce the required network traffic by minimizing the overall size of the messages. The experiments show significant performance for both aggregation techniques achieving compression ratios as high as 25 for aggregated SOAP messages.     

Data envelopment analysis for weight derivation and aggregation in the analytic hierarchy process

Data envelopment analysis (DEA) is proposed in this paper to generate local weights of alternatives from pair-wise comparison judgment matrices used in the analytic hierarchy process (AHP). The underlying assumption behind the approach is explained, and some salient features are explored. It is proved that DEA correctly estimates the true weights when applied to a consistent matrix formed using a known set of weights. DEA is further proposed to aggregate the local weights of alternatives in terms of different criteria to compute final weights. It is proved further that the proposed approach, called DEAHP in this paper, does not suffer from rank reversal when an irrelevant alternative(s) is added or removed.     

A semi-Markov decision process-based joint call admission control for inter-RAT cell re-selection in next generation wireless networks

In the next generation wireless networks (NGWNs), where different radio access technologies (RAT) will coexist and work in collaboration to provide ubiquitous access, a mechanism called Joint Call Admission Control (JCAC) will play an important role by deciding whether or not an incoming service request will be accepted according to an admission constraint as well as determining in which RAT (among the available) it will be connected. In this paper, we propose an optimal JCAC for inter-RAT cell re-selection problem also referred to as initial RAT selection in co-located wireless networks, which supports both real-time services and non-real-time services. To properly meet the JCAC goals, we propose a cost function that weigh two criteria: the blocking cost function, which takes into account the priority of each service class in each RAT, and the alternative acceptance cost, which reflects the multiplicity of RATs working in a collaborative fashion, mandatory in NGWN. We use the framework of Semi-Markov Decision Process (SMDP) to formulate the optimization problem and the value iteration algorithm to compute the optimal policy. Our model still takes into consideration the ratio between the radius of the co-located RATs and shows how it may impact on optimal initial RAT selection. Numerical results, supported by an analysis of the structure of the optimal policy, show that the proposed optimal JCAC selects for real-time service class the biggest RAT and for non-real-time service class the smallest one. This optimal JCAC policy is ratified by the current trend in the design of NGWN and also follows the 3rd Generation Partnership Project (3GPP) expectations.     

基于隐半马尔可夫模型的SWIM应用层DDoS攻击的检测方法

针对广域信息管理（SWIM）系统受到应用层分布式拒绝服务（DDoS）攻击的问题，提出了一种基于隐半马尔可夫模型（HSMM）的SWIM应用层DDoS攻击的检测方法。首先采用改进后的前向后向算法，利用HSMM建立动态异常检测模型动态地追踪正常SWIM用户的浏览行为；然后通过学习和预测正常SWIM用户行为得出正常检测区间；最后选取访问包的大小和请求时间间隔为特征进行建模，并训练模型进行异常检测。实验结果表明，所提方法在攻击1和攻击2情况下检测率分别为99.95%和91.89%，与快速前向后向算法构建的HSMM相比，检测率提升了0.9%。测试结果表明所提方法可以有效地检测SWIM系统应用层DDoS攻击。     

Dual-PISA: An index for aggregation operations on time series data

Aggregation operations play an essential role in time series database management. As the number of data increases, it is difficult for current solutions, such as summary table and MapReduce-based methods to respond to such queries with low latency. Other approaches, such as segment tree-based methods, have a poor insertion performance when the data size exceeds the available memory. This paper proposes a Persistent Index for Segmented Aggregations (PISA), which has fast insertion performance and low latency for aggregation queries. PISA uses a forest to overcome the performance disadvantage of insertion in traditional segment trees. By defining two kinds of tags, namely code number and serial number, we propose an algorithm to accelerate queries by avoiding unnecessary reading data on disk. Additionally, we extend it to Dual-PISA to tolerate a range of unordered data, which is very important in the real world. Dual-PISA is stored on disk and is hugely memory-efficient — only takes a few hundred bytes of memory for billions of data points. Dual-PISA can be easily implemented on both traditional databases and NoSQL systems. It handles aggregation queries within milliseconds on a commodity server, for a time range that contains tens of billions of data points.     

Latent variable MPC for trajectory tracking in batch processes

A novel multivariate empirical model predictive control strategy (LV-MPC) for trajectory tracking and disturbance rejection for batch processes is presented. The strategy is based on dynamic principal component analysis (PCA) models of the batch process. The solution to the control problem is computed in the low dimensional latent variable space of the PCA model. The trajectories of all variables over the future horizon are then computed from the latent variable solution of the controller. The excellent control performance and the modest closed-loop data requirements for identification are illustrated for the temperature tracking in simulations of an emulsion polymerization process, an exothermic chemical reaction system and for MIMO temperature and pressure tracking in a nylon polymerization autoclave.     

Spatial aggregation: Data model and implementation

Data aggregation in Geographic Information Systems (GIS) is a desirable feature, only marginally present in commercial systems nowadays, mostly through ad hoc solutions. We address this problem introducing a formal model that integrates, in a natural way, geographic data and non-spatial information contained in a data warehouse external to the GIS. This approach allows both aggregation of geometric components and aggregation of measures associated to those components, defined in GIS fact tables. We define the notion of geometric aggregation, a general framework for aggregate queries in a GIS setting. Although general enough to express a wide range of (aggregate) queries, some of these queries can be hard to compute in a real-world GIS environment because they involve computing an integral over a certain area. Thus, we identify the class of summable queries, which can be efficiently evaluated replacing this integral with a sum of functions of geometric objects. Integration of GIS and OLAP (On Line Analytical Processing) is supported also through a language, GISOLAP-QL. We present an implementation, denoted Piet, which supports four kinds of queries: standard GIS, standard OLAP, geometric aggregation (like “total population in states with more than three airports”), and integrated GIS-OLAP queries (“total sales by product in cities crossed by a river”, also allowing navigation of the results). Further, Piet implements a novel query processing technique: first, a process called subpolygonization decomposes each thematic layer in a GIS, into open convex polygons; then, another process (the overlay precomputation) computes and stores in a database the overlay of those layers for later use by a query processor. Experimental evaluation showed that for a wide class of geometric queries, overlay precomputation outperforms R-tree-based techniques, suggesting that it can be an alternative for GIS query processing.     

二元语义信息集结算子的性质分析

研究语言评价信患处理中有关二元语义集结算子的性质。首先描述了二元语义信患集结的有序加权平均(T-OWA)算子，并提出一种有序加权几何(T-OWG)算子；然后分析了T-OWA算子和T-OWG算子所具有的性质。该研究结果丰富了二元语义集结算子的分析方法。