输入为Markov序列时的多用户检测算法

考虑当用户序列存在时间相关性时的多用户检测，并假设这种相关性可以用Markov链描述，在传统的线性最大似然检测器中嵌入一个隐Markov模型估计过程。因为输入序列是Markov链，检测器的输出可以看成是被噪声污染的Markov序列，Markov模型估计子用于估计用户序列及其转移概率，而估计得到的用户序列用来更新检测器的估计。因此，检测器和用户序列可以通过迭代的方式求解。仿真结果显示本文算法能充分利用信道输入的时间相关性．效果优于传统的最大似然线性检测器。     

A note on the attractor-property of infinite-state Markov chains

In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n>0 is less than n−Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor.     

Host-based intrusion detection using dynamic and static behavioral models

Intrusion detection has emerged as an important approach to network security. In this paper, we adopt an anomaly detection approach by detecting possible intrusions based on program or user profiles built from normal usage data. In particular, program profiles based on Unix system calls and user profiles based on Unix shell commands are modeled using two different types of behavioral models for data mining. The dynamic modeling approach is based on hidden Markov models (HMM) and the principle of maximum likelihood, while the static modeling approach is based on event occurrence frequency distributions and the principle of minimum cross entropy. The novelty detection approach is adopted to estimate the model parameters using normal training data only, as opposed to the classification approach which has to use both normal and intrusion data for training. To determine whether or not a certain behavior is similar enough to the normal model and hence should be classified as normal, we use a scheme that can be justified from the perspective of hypothesis testing. Our experimental results show that the dynamic modeling approach is better than the static modeling approach for the system call datasets, while the dynamic modeling approach is worse for the shell command datasets. Moreover, the static modeling approach is similar in performance to instance-based learning reported previously by others for the same shell command database but with much higher computational and storage requirements than our method.     

An Empirical Study of Two Approaches to Sequence Learning for Anomaly Detection

This paper introduces the computer security domain of anomaly detection and formulates it as a machine learning task on temporal sequence data. In this domain, the goal is to develop a model or profile of the normal working state of a system user and to detect anomalous conditions as long-term deviations from the expected behavior patterns. We introduce two approaches to this problem: one employing instance-based learning (IBL) and the other using hidden Markov models (HMMs). Though not suitable for a comprehensive security solution, both approaches achieve anomaly identification performance sufficient for a low-level focus of attention detector in a multitier security system. Further, we evaluate model scaling techniques for the two approaches: two clustering techniques for the IBL approach and variation of the number of hidden states for the HMM approach. We find that over both model classes and a wide range of model scales, there is no significant difference in performance at recognizing the profiled user. We take this invariance as evidence that, in this security domain, limited memory models (e.g., fixed-length instances or low-order Markov models) can learn only part of the user identity information in which we're interested and that substantially different models will be necessary if dramatic improvements in user-based anomaly detection are to be achieved.     

HMM-Based Concept Learning for a Mobile Robot

We are developing an intelligent robot and attempting to teach it language. While there are many aspects of this research, for the purposes here the most important are the following ideas. Language is primarily based on semantics, not syntax, which is still the focus in speech recognition research these days. To truly learn meaning, a language engine cannot simply be a computer program running on a desktop computer analyzing speech. It must be part of a more general, embodied intelligent system, one capable of using associative learning to form concepts from the perception of experiences in the world, and further capable of manipulating those concepts symbolically. In this paper, we present a general cascade model for learning concepts, and explore the use of hidden Markov models (HMMs) as part of the cascade model. HMMs are capable of automatically learning and extracting the underlying structure of continuous-valued inputs and representing that structure in the states of the model. These states can then be treated as symbolic representations of the inputs. We show how a cascade of HMMs can be embedded in a small mobile robot and used to find correlations among sensory inputs to learn a set of symbolic concepts, which are used for decision making and could eventually be manipulated linguistically     

Hidden Markov models for the stimulus-response relationships of multistate neural systems

Given recent experimental results suggesting that neural circuits may evolve through multiple firing states, we develop a framework for estimating state-dependent neural response properties from spike train data. We modify the traditional hidden Markov model (HMM) framework to incorporate stimulus-driven, non-Poisson point-process observations. For maximal flexibility, we allow external, time-varying stimuli and the neurons' own spike histories to drive both the spiking behavior in each state and the transitioning behavior between states. We employ an appropriately modified expectation-maximization algorithm to estimate the model parameters. The expectation step is solved by the standard forward-backward algorithm for HMMs. The maximization step reduces to a set of separable concave optimization problems if the model is restricted slightly. We first test our algorithm on simulated data and are able to fully recover the parameters used to generate the data and accurately recapitulate the sequence of hidden states. We then apply our algorithm to a recently published data set in which the observed neuronal ensembles displayed multistate behavior and show that inclusion of spike history information significantly improves the fit of the model. Additionally, we show that a simple reformulation of the state space of the underlying Markov chain allows us to implement a hybrid half-multistate, half-histogram model that may be more appropriate for capturing the complexity of certain data sets than either a simple HMM or a simple peristimulus time histogram model alone.     

A generalization of the 0-1 principle for sorting

The traditional zero-one principle for sorting networks states that “if a network with n input lines sorts alln² binary sequences into nondecreasing order, then it will sort any arbitrary sequence of n numbers into nondecreasing order”. We generalize this to the situation when a network sorts almost all binary sequences and relate it to the behavior of the sorting network on arbitrary inputs. We also present an application to mesh sorting.     

Monte Carlo TD(λ)-methods for the optimal control of discrete-time Markovian jump linear systems

In this paper, we present an iterative technique based on Monte Carlo simulations for deriving the optimal control of the infinite horizon linear regulator problem of discrete-time Markovian jump linear systems for the case in which the transition probability matrix of the Markov chain is not known. We trace a parallel with the theory of TD(λ) algorithms for Markovian decision processes to develop a TD(λ) like algorithm for the optimal control associated to the maximal solution of a set of coupled algebraic Riccati equations (CARE). It is assumed that either there is a sample of past observations of the Markov chain that can be used for the iterative algorithm, or it can be generated through a computer program. Our proofs rely on the spectral radius of the closed loop operators associated to the mean square stability of the system being less than 1.     

A non-equilibrium analysis and control framework for active queue management

We present a non-equilibrium analysis and control approach for the Active Queue Management (AQM) problem in communication networks. Using simplified fluid models, we carry out a bifurcation study of the complex dynamic queue behavior to show that non-equilibrium methods are essential for analysis and optimization in the AQM problem. We investigate an ergodic theoretic framework for stochastic modeling of the non-equilibrium behavior in deterministic models and use it to identify parameters of a fluid model from packet level simulations. For computational tractability, we use set-oriented numerical methods to construct finite-dimensional Markov models, including control Markov chains and hidden Markov models. Subsequently, we develop and analyze an example AQM algorithm using a Markov Decision Process (MDP) based control framework. The control scheme developed is optimal with respect to a reward function, defined over the queue size and aggregate flow rate. We implement and simulate our illustrative AQM algorithm in the ns-2 network simulator. The results obtained confirm the theoretical analysis and exhibit promising performance when compared with well-known alternative schemes under persistent non-equilibrium queue behavior.     

Mixed Memory Markov Models: Decomposing Complex Stochastic Processes as Mixtures of Simpler Ones

We study Markov models whose state spaces arise from the Cartesian product of two or more discrete random variables. We show how to parameterize the transition matrices of these models as a convex combination—or mixture—of simpler dynamical models. The parameters in these models admit a simple probabilistic interpretation and can be fitted iteratively by an Expectation-Maximization (EM) procedure. We derive a set of generalized Baum-Welch updates for factorial hidden Markov models that make use of this parameterization. We also describe a simple iterative procedure for approximately computing the statistics of the hidden states. Throughout, we give examples where mixed memory models provide a useful representation of complex stochastic processes.     

基于函数型数据时间序列建模的单传感器日常行为识别

在基于惯性传感器的人体行为识别中,传统算法常忽略行为的周期性与时序性,对提取特征的滑动窗口大小也有相应要求.文中基于单个腰部传感器分析人体日常行为,提出面向周期行为的函数型数据分析方法和隐马尔可夫模型结合的行为识别算法.首先,使用函数型数据分析方法,拟合周期性日常行为的动作捕捉数据,提取拟合后的单个周期数据.然后基于此周期时间序列数据建立描述各个日常行为过程的隐马尔可夫模型.最后,使用最大似然估计判别行为,得到识别结果.该算法通过单个腰部传感器即可快速有效地识别8种日常行为,在基于用户依赖策略和用户独立策略时识别率较高.     

Non-stationary fuzzy Markov chain

This paper deals with a recent statistical model based on fuzzy Markov random chains for image segmentation, in the context of stationary and non-stationary data. On one hand, fuzzy scheme takes into account discrete and continuous classes through the modeling of hidden data imprecision and on the other hand, Markovian Bayesian scheme models the uncertainty on the observed data. A non-stationary fuzzy Markov chain model is proposed in an unsupervised way, based on a recent Markov triplet approach. The method is compared with the stationary fuzzy Markovian chain model. Both stationary and non-stationary methods are enriched with a parameterized joint density, which governs the attractiveness of the neighbored states. Segmentation task is processed with Bayesian tools, such as the well known MPM (Mode of Posterior Marginals) criterion. To validate both models, we perform and compare the segmentation on synthetic images and raw optical patterns which present diffuse structures.     

Development of head detection and tracking systems for visual surveillance

This paper proposes a technique for the detection of head nod and shake gestures based on eye tracking and head motion decision. The eye tracking step is divided into face detection and eye location. Here, we apply a motion segmentation algorithm that examines differences in moving people’s faces. This system utilizes a Hidden Markov Model-based head detection module that carries out complete detection in the input images, followed by the eye tracking module that refines the search based on a candidate list provided by the preprocessing module. The novelty of this paper is derived from differences in real-time input images, preprocessing to remove noises (morphological operators and so on), detecting edge lines and restoration, finding the face area, and cutting the head candidate. Moreover, we adopt a K-means algorithm for finding the head region. Real-time eye tracking extracts the location of eyes from the detected face region and is performed at close to a pair of eyes. After eye tracking, the coordinates of the detected eyes are transformed into a normalized vector of x-coordinate and y-coordinate. Head nod and shake detector uses three hidden Markov models (HMMs). HMM representation of the head detection can estimate the underlying HMM states from a sequence of face images. Head nod and shake can be detected by three HMMs that are adapted by a directional vector. The directional vector represents the direction of the head movement. The vector is HMMs for determining neutral as well as head nod and shake. These techniques are implemented on images, and notable success is notified.     

A constraint-based querying system for exploratory pattern discovery

In this article we present ConQueSt, a constraint-based querying system able to support the intrinsically exploratory (i.e., human-guided, interactive and iterative) nature of pattern discovery. Following the inductive database vision, our framework provides users with an expressive constraint-based query language, which allows the discovery process to be effectively driven toward potentially interesting patterns. Such constraints are also exploited to reduce the cost of pattern mining computation. ConQueSt is a comprehensive mining system that can access real-world relational databases from which to extract data. Through the interaction with a friendly graphical user interface (GUI), the user can define complex mining queries by means of few clicks. After a pre-processing step, mining queries are answered by an efficient and robust pattern mining engine which entails the state-of-the-art of data and search space reduction techniques. Resulting patterns are then presented to the user in a pattern browsing window, and possibly stored back in the underlying database as relations.     

hsmm — An R package for analyzing hidden semi-Markov models

Hidden semi-Markov models are a generalization of the well-known hidden Markov model. They allow for a greater flexibility of sojourn time distributions, which implicitly follow a geometric distribution in the case of a hidden Markov chain. The aim of this paper is to describe hsmm, a new software package for the statistical computing environment R. This package allows for the simulation and maximum likelihood estimation of hidden semi-Markov models. The implemented Expectation Maximization algorithm assumes that the time spent in the last visited state is subject to right-censoring. It is therefore not subject to the common limitation that the last visited state terminates at the last observation. Additionally, hsmm permits the user to make inferences about the underlying state sequence via the Viterbi algorithm and smoothing probabilities.     

Evaluation of session-based recommendation algorithms

Recommender systems help users find relevant items of interest, for example on e-commerce or media streaming sites. Most academic research is concerned with approaches that personalize the recommendations according to long-term user profiles. In many real-world applications, however, such long-term profiles often do not exist and recommendations therefore have to be made solely based on the observed behavior of a user during an ongoing session. Given the high practical relevance of the problem, an increased interest in this problem can be observed in recent years, leading to a number of proposals for session-based recommendation algorithms that typically aim to predict the user’s immediate next actions. In this work, we present the results of an in-depth performance comparison of a number of such algorithms, using a variety of datasets and evaluation measures. Our comparison includes the most recent approaches based on recurrent neural networks like gru4rec, factorized Markov model approaches such as fism or fossil, as well as simpler methods based, e.g., on nearest neighbor schemes. Our experiments reveal that algorithms of this latter class, despite their sometimes almost trivial nature, often perform equally well or significantly better than today’s more complex approaches based on deep neural networks. Our results therefore suggest that there is substantial room for improvement regarding the development of more sophisticated session-based recommendation algorithms.     

Labeling Q-learning in hidden state environments

Recently,reinforcement learning (RL) methods have been used for learning problems in environments with embedded hidden states. However, conventional RL methods have been limited to handlingMarkov decision process problems. In order to overcome hidden states, several algorithms were proposed, but these need an extreme amount of memory of past sequences which represent historical state transitions. The aim of this work was to extend our previously proposed algorithm for hidden states in an environment, calledlabeling Q-learning (LQ-learning), which reinforces incompletely observed perception by labeling. In LQ-learning, the agent has a perception structure which consists of pairs of observations and labels. From these pairs, the agent can distinguish more exactly hidden states which look the same but are actually different each other. Labeling is carried out by labeling functions. Numerous labeling functions can be considered, but here we introduce some labeling functions based on the sequence of only the last and the current observations. This extended LQ-learning is applied to grid-world problems which have hidden states. The results of these simulations show the availability of LQ-learning. This work was presented in part at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15–17, 2001     

Two-way unary automata versus logarithmic space

We show that if L=NL (the classical logarithmic space classes), then each unary 2nfa (a two-way nondeterministic finite automaton) can be converted into an equivalent 2dfa (a deterministic two-way automaton), keeping the number of states polynomial. (Unlike other results of this kind, here the deterministic simulation is valid for inputs of all lengths, not only polynomially long ones.) This shows a connection between the standard logarithmic space complexity and the state complexity of two-way unary automata: it indicates that L could be separated from NL by proving a superpolynomial gap, in the number of states, for the conversion from unary 2nfas to 2dfa. Moreover, without any unproven assumptions, we show that each n-state unary 2nfa can be simulated by an equivalent 2ufa (an unambiguous 2nfa) with a polynomial number of states.