Open Access
Chin, Shin Choong
Graduate Program:
Electrical Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
October 05, 2004
Committee Members:
  • Shashi Phoha, Committee Chair
  • Jeffrey Scott Mayer, Committee Chair
  • Asok Ray, Committee Member
  • Constantino Manuel Lagoa, Committee Member
  • John Metzner, Committee Member
  • Natarajan Gautam, Committee Member
  • pattern recognition
  • signal processing
  • anomaly detection
Large-scale engineering systems, having complexity comparable to that of biological systems, have emerged with the maturity of advanced theories in control, communications, and computation. Much of the complexities are often not apparent as they are hidden in the laboratory environment as well as in the real-life scenarios of normal operating conditions. Anomalies in complex systems may often manifest themselves under appropriate excitation from certain exogenous stimuli. These anomalies may be benign or malignant as their impact on the system may vary with mission objectives and operating conditions. Major catastrophic failures in complex engineering systems can often be averted if incipient faults are detected sufficiently in advance by observing small anomalies in the dynamical behavior. The dissertation presents a novel approach to anomaly detection in complex systems based on the fundamental principles of Systems Sciences, Language Theory, and Computational Mechanics. The goal of the research is to detect anomalies to mitigate failures in complex dynamical systems as well as to enhance their performance and availability. However, solely based on the fundamental principles of physics, accurate and computationally tractable modelling of complex system dynamics is often infeasible. One may have to rely on semi-empirical models whose parameters can be identified using time series data generated from sensors and (possibly) additional sources of information such as operation history of the process. Accordingly, decision and control laws are to be formulated based on such semi-empirical models along with real-time data by monitoring these systems. The technical approach presented in the dissertation focuses on quantitative detection of the qualitative features of anomalies in complex systems. The proposed anomaly detection methodology utilizes the concepts of Symbolic Dynamics which are a part of dynamical systems theory and Computational Mechanics. Symbolic Dynamics qualitatively describes dynamical systems behavior in terms of sequences of symbols. Computational Mechanics provides a tool for pattern recognition in these symbol sequences. This dissertation proposes a new, computationally simpler, alternative approach to Crutchfield's epsilon machine for representing the pattern in a symbolic process. The proposed tool is called the D-Markov machine, which is motivated from the perspective of anomaly detection. Anomalies due to small faults, such as deviations of system parameters from their nominal values, are detected by identifying variations of patterns in symbol sequences. Time series data, observed under selected stimuli and/or self-excitation, are used to generate the symbol sequences. The problem of anomaly detection, addressed in this dissertation, belongs to the class of non-linear non-autonomous dynamical systems in which anomalies occur at a slow time-scale while the inferences are made based on the time-series observation of selected system variable(s) at the fast time-scale. The proposed procedure of anomaly detection relies on two-time-scale analysis of the stationary response of the dynamical system. To possibly facilitate small change detection in system parameters, the system may be excited with a priori known stimuli and discovering anomaly patterns, if any, from the resulting responses at the fast time scale. The proposed anomaly detection methodology is separated into two parts: (i) Forward problem; and (ii) Inverse problem. The objective in the forward problem is to learn, in an off-line setting, how the grammar underlying the system dynamics changes as the system parameters change. In contrast, the inverse problem is that of inferring the system parameters based on the on-line observations of the observed stationary behavior. The feasible range of damage parameter estimates can be narrowed down from the intersection of the information generated from responses under several stimuli chosen in the forward problem.