- 2:00 pm on Wednesday, June 19, 2013
- 4:00 pm on Wednesday, June 19, 2013
- 15 Saint Mary's Street, Rm 105
TITLE: Decision-Making For Complex Systems with Uncertainty: Markov Decision Processes and Network Anomaly Detection
ABSTRACT: Decision-making for systems with uncertainty is very challenging. We consider two types of decision-making problems. One is Markov Decision Process (MDP). The other is Anomaly Detection for Network Traffic.
MDP and Dynamic Programming (DP) are general frameworks for sequential decision-making under uncertainty. It is well known that dynamic programming suffers from the so-called “curse of dimensionality”. Besides, in many cases with large uncertainty, transition probability is not explicitly available, in which case we must resort to Approximate Dynamic Programming (ADP) techniques. Actor-critic method is a promising type of ADP. This thesis will focus on the methods with the actor-critic structure which optimizes some Randomized Stationary Policy (RSP) using policy gradient estimation.
Our first contribution is to introduce the the method of Least Squares Temporal Difference (LSTD) to the critic, which is known to have better convergence rate than both TD(1) and TD(\lambda). Second, to improve the performance of actor-critic methods for ill-conditioned problems, we propose the Hessian Actor-Critic (HAC) method. Although each iteration takes more computation, HAC outperforms LSTD actor-critic for ill-conditioned problems by reaching the optimal point with less iteration number. We evaluate our methods with a problem of finding a control policy for robot under an uncertain environment to maximize the probability of reaching some states while avoiding some other states.
System Anomaly Detection is another important type of decision-making problems under certainty. This thesis focuses on the anomaly detection of Network System. Two types of network system are considered.
First, we present four stochastic and deterministic methods to anomaly detection of stationary network whose uncertainty can be characterized
by a stationary model. Our methods cover most of the common techniques in the anomaly detection field, including Statistical Hypothesis Tests (SHT),
Support Vector Machines (SVM) and clustering analysis. We evaluate all methods in a simulated network that consists of nominal data, three flow-level
anomalies and one packet-level attack. Through analyzing the results, we point out the advantages and disadvantages of each method and conclude that combining the results of the individual methods can yield improved anomaly detection results.
Second, for the dynamic network whose uncertainty is not stationary, we propose two robust stochastic methods. We first formulate a binary composite hypothesis testing problem for evaluating whether a sequence of observation comes from a family of Probabilities Laws (PL). Then two robust methods, one is model-free and one is model-based, are proposed to solve this problem. The two methods are applied to anomaly detection in dynamic
network systems. We take three steps to estimate the underlying family of PLs in the dynamic network. First, two types of PLs are suggested to characterize the non-stationarity of the network. Then each feature is inspected separately to get rough estimation of PLs, which usually generates a lot of redundancy.
Later, an Integer Programming (IP) problem is formulated to select a refined set of PLs by analyzing reference data. The simulation results show that the
robust methods have significant advantages over vanilla methods in the anomaly detection of dynamic network systems.
COMMITTEE: Advisor: Ioannis Paschalidis, SE/ECE; Christos Cassandras, SE/ECE; David Starobinski, SE/ECE; Mark Crovella, SE/CAS, Computer Science