Multiple Kernel Learning for Heterogeneous Anomaly Detection: Algorithm and Aviation Safety Case Study

Multiple Kernel Learning for Heterogeneous Anomaly

∗

Detection: Algorithm and Aviation Safety Case Study

Santanu Das Bryan L. Matthews

UARC, UCSC SGT Inc.

NASA Ames Research Center NASA Ames Research Center Moffett Field, CA 94035 Moffett Field, CA 94035

Santanu.Das − 1@nasa.gov Bryan.L.Matthews@nasa.gov

Ashok N. Srivastava Nikunj C. Oza

NASA Ames Research Center NASA Ames Research Center Moffett Field, CA 94035 Moffett Field, CA 94035

Ashok.Srivastava@nasa.gov Nikunj.C.Oza@nasa.gov

ABSTRACT serviceability; H.2.4 [ Systems ]: Data Translation; H.2.5

[ Heterogeneous Databases ]: Discrete databases; H.4.2 The world-wide aviation system is one of the most complex [ Types of Systems ]: Decision Support dynamical systems ever developed and is generating data at an extremely rapid rate. Most modern commercial aircraft record several hundred flight parameters including informa-

General Terms

tion from the guidance, navigation, and control systems, the Systems health management, measurement, human factors, avionics and propulsion systems, and the pilot inputs into data analysis the aircraft. These parameters may be continuous measure- ments or binary or categorical measurements recorded in one

Keywords

second intervals for the duration of the flight. Currently, most approaches to aviation safety are reactive, meaning aeronautics, anomaly detection, prediction, prognostics that they are designed to react to an aviation safety inci- dent or accident. In this paper, we discuss a novel approach

1. INTRODUCTION

based on the theory of multiple kernel learning to detect po- On January 31, 2000, a McDonnell Douglas MD-83 was tential safety anomalies in very large data bases of discrete enroute from Puerto Vallarta, Mexico to Seattle Washing- and continuous data from world-wide operations of commer- ton when it experienced a catastrophic failure resulting in cial fleets. We pose a general anomaly detection problem the death of 89 passengers and flight personnel as it dived which includes both discrete and continuous data streams, from about 18000 feet into the Pacific Ocean. Analysis of where we assume that the discrete streams have a causal data from the Flight Data Recorder (FDR) and the wreck- influence on the continuous streams. We also assume that age indicated that the probable cause of the accident was atypical sequence of events in the discrete streams can lead ”a loss of airplane pitch control resulting from the in-flight to off-nominal system performance. We discuss the appli- failure of the horizontal stabilizer trim system jackscrew as- cation domain, novel algorithms, and also discuss results on sembly’s acme nut threads. The thread failure was caused real-world data sets. Our algorithm uncovers operationally by excessive wear resulting from Alaska Airlines’ insufficient significant events in high dimensional data streams in the lubrication of the jackscrew assembly.” [3] The precursors to aviation industry which are not detectable using state of this accident and other accidents due to mechanical issues the art methods.

and human factors are often evident in large data sets from Flight Data Recorders as well as textual reports written by

Categories and Subject Descriptors

the flight crew and other persons involved in flight opera- C.4 [ Performance of Systems ]: Reliability, availability, tions. Indeed, an informal study at NASA of FDR data from similar aircraft showed that a multivariate query on ∗ A full version of this paper is available as at certain parameters in the FDR could uncover aircraft with https://dashlink.arc.nasa.gov/topic/multiple- similar mechanical problems.

kernel-learning-based-heterogeneous-algorithm/ Boeing recently completed a comprehensive statistical sur- vey of commercial aircraft accidents worldwide [18] which shows a dramatic drop in the accident rate, the fatal ac- cident rate, and also the hull-loss accident rate as shown in Figure 1. These advances have been due to a signifi- Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are cant investment in near-term technologies to improve air- not made or distributed for profit or commercial advantage and that copies craft safety. However, assuming that air traffic continues to bear this notice and the full citation on the first page. To copy otherwise, to grow at a modest rate of only 3% per year, over the next republish, to post on servers or to redistribute to lists, requires prior specific two decades that will lead to nearly doubling the air traffic permission and/or a fee.

within the US. The increased density of operations, com- Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.

Figure 1: This figure from Boeing’s Statistical Summary of Figure 2: This figure shows our overall approach to address- Commercial Jet Accidents in 2007 shows that the fatality ing safety issues in the aviation system. The automatic iden- rate of accidents in the United States has dropped signif- tification and causal analysis of hazards from continuous and icantly over the past five decades. However, as air traffic discrete data streams is the subject of this paper [ ? ].

continues to grow, it is essential to develop techniques to re- veal precursors to safety incidents and accidents from large flight data bases.

This paper addresses the problem of detecting anomalies in high-dimensional, multivariate data streams containing both discrete and continuous channels. We assume that we are given data from a data generating process that can be bined with increased demands on service and availability of functionally described by the following equations: aircraft can lead to a significant number of aviation accidents even with the current extremely low accident rate.

∗ h = Γ( h ) (1) t t − 1 In 2007, NASA established an archive that contains data ∗ ∗ x = Ψ( x , h , u ) (2) from flight data recorders from most of the major carriers t t t − 1 t in the US. The archive, known as the Distributed National y = Ω( x ) (3) t t FOQA (Flight Operations Quality Assurance) Archive (DNFA) contains over two million flights today and covers over 10 We assume that the function Γ determining the evolution of the hidden system state h is unknown. We also assume that major carriers. Typical FOQA parameters consist of both t continuous and discrete (categorical) data from the avionics, the function Ψ, which governs the evolution of the continu- ous state vector is also unknown. We assume that the vector propulsion system, control surfaces, landing gear, the cock- ∗ pit switch positions, and other critical systems. These data x is an N dimensional state vector, and x is its history t − 1 ∗ for the last D time steps: x = [ x , x , ..., x ].

sets can have up to 500 parameters and are sampled at 1 t − D t − D +1 t − 1 t − 1 Hz. For a moderate sized fleet that operates 1000 flights per The quantity u is the observed system input, and y is the t t observed system output which can contain discrete, cate- day, these FOQA data sets become very large. Due to pro- gorical, and continuous features. We assume that the entire prietary and legal issues, these data are not shared between airlines or directly with the government. Thus, in the DNFA data that is available, covering both inputs and outputs is given by the set ( U , Y ).

architecture, each carrier has its own data repository, and a primary requirement of the DNFA is that the data from In real-world flight operations, the pilot inputs U are de- termined by standard-operating procedure: for a given air- multiple carriers not be centralized. Data in the DNFA is anonymized so that flight numbers and marks identifying port, aircraft, weather conditions, instructions from air traf- fic control, and other contextual elements of the flight, the pilots and crew are removed. In this paper, we discuss the problem of detecting anomalies in FOQA data that may flight procedures are well determined. However, while we can assume that all pilots are attempting to follow the stan- be indicative of safety issues due to mechanical or human factors issues. We present the results of our anomaly detec- dard operating procedures, some may deviate from these ′ procedures which could lead to a different input sequence U , tion algorithms on real FOQA data from a regional carrier.

This work is part of a comprehensive plan within the NASA resulting in a different set of observed flight characteristics ′ ′ Y . The evolution of Y over time will necessarily be differ- Integrated ViIVHM project to analyze numerical data from ent than that of the nominal case. This does not imply that DNFA and text reports from DNAA to assess health of large ′ ′ commercial fleets of aircraft. the pair U , Y is an unsafe flight– it is simply not typically observed. Our goal in this paper is to develop algorithms that can detect if the discrete pilot inputs U , combined with

2. BACKGROUND

the observation vector Y are nominal or off nominal and to

diagnose the reason why such a potential anomalous event been found to outperform SVMs that only use one of the was so designated. kernels [9].

MKL appears to be a promising way to satisfy our re- quirement of incorporating both discrete and continuous se-

2.1 Current State-Of-The-Art Algorithms on

quences in anomaly detection. We use the kernel anomaly

Anomaly Detection

detection method known as one-class Support Vector Ma- Data-driven anomaly detection is an active area of re- chines (SVMs) [17, 15]. We incorporate a kernel over dis- search (see [6] for a detailed survey). For example, there crete sequences which is based on the normalized Longest are many anomaly detection methods that identify anoma- Common Subsequence (nLCS) measure used in SequenceM- lies in the vector space. However SequenceMiner [4] is the iner and a kernel over continuous sequences that makes use only algorithm that can analyze discrete sequences. Prelim- of the Symbolic Aggregate approXimation (SAX) [14] repre- inary experiments with SequenceMiner on data from com- sentation. We demonstrate that this Multiple Kernel Anomaly mercial aviation indicate that it is able to find examples of Detection (MKAD) algorithm outperforms Orca and Se- mode confusion, in which a pilot loses track of auto pilot quenceMiner at finding operationally significant anomalies mode changes and therefore effects anomalous switching be- in aviation safety data. To our knowledge, MKAD has never havior in order to determine the auto pilot mode. Because been used with sequences or within one-class SVM prior to cockpit switch behavior is represented mostly by sequences our very recent poster which shows preliminary results of an of discrete switches, SequenceMiner is a natural algorithm earlier version of our algorithm on synthetic data only [8].

for finding anomalies in such sequences. Soem details on Se- quenceMiner will be provided in Section ?? .Other anomaly

3. ALGORITHM

detection methods, such as Orca [2] and the Inductive Mon- itoring System (IMS) [11], find anomalies in multivariate We first give a brief but general description of multiple continuous data. Both Orca and IMS are distance-based kernel learning based detection technique. Then we describe anomaly detection methods, in that they use a metric re- the two kernels that we use within our model.

lated to distance, such as the average Euclidean distance

3.1 Multiple Kernel Learning based Detection

to its k-nearest neighbors, to assess the anomalousness of a point. Clearly, the greater the value of this metric, the As mentioned earlier one of the major advantage of kernel based methods compared to other techniques is their ability more anomalous a data point is. In principle, one could use Orca and IMS with heterogeneous data—data containing to combine information from multiple data sources. The way this improved knowledge about the problem can be incor- both discrete and continuous variables. However, in IMS the discrete variables’ contributions to the Euclidean dis- porated in the core optimization problem is very simple yet meaningful. The resultant kernel K can be a convex com- tance may not reflect their true importance, and finding the appropriate way to incorporate distances in the discrete and bination of all kernels computed over multiple features i.e.

∑ ∑ n n ˆ continuous spaces into a common metric is a problem with K ( ~ x , ~ x ) = η k ( ~ x , ~ x ), with η ≥ 0 and η = 1.

i j i p i j i i p =1 i =1 th no clear solution. Additionally, Orca and IMS do not learn ˆ Here k ( ~ x , ~ x ) represents the p kernel computed, and η p i j the sequential dependencies between points in the training to weight individual kernels. Here we take advantage of data. Here we would like to identify an anomaly detection the multiple kernel learning approach to incorporate more method that incorporates both continuous and discrete se- knowledge in the decision process so that we can achieve an quences and is able to identify anomalies within each sepa- improvement in detecting anomalies in complex heteroge- rately but also across the two types of data.

neous systems that involves various data sources and data Kernel methods [16] have been used for many different structures. Since we are interested in anomaly detection we types of data with various types of features such as graphs [12] have used the classical One-class SVMs [15] as our core algo- and multiple feature types in computer vision such as color [7], rithm. One-class SVM is a semi-supervised learning method shape, texture [19], and graphs based on image segmen- that finds a set of outliers using a decision boundary. Below tations [9]. Kernel functions map pairs of objects to the we will provide a brief description of some of the properties similarity between those objects, with a value of 1 indi- of the mapping function and talk a bit on the optimization cating maximum similarity and 0 indicating no similarity.

problem of One-class SVM.

Therefore, subject to Mercer’s conditions [5], one can de- One-class SVMs constructs an optimal hyperplane in the vise a kernel function measuring similarity among objects high dimensional feature space by maximizing the margin of any type and incorporate this into kernel methods for between the origin and the hyperplane. This is done by classification, regression, or anomaly detection. This flexi- solving an optimization problem [15]. The dual form of the bility to incorporate kernel functions of different types moti- optimization can be written as, vates the question of whether multiple such kernel functions can be incorporated simultaneously. This question brought ∑ about the field of Multiple Kernel Learning (MKL) [1, 13]. minimize Q = α α k ( x , x ) i j i j i,j MKL replaces individual kernel functions with combinations ∑ of kernel functions, thereby allowing the kernel method to subject to 0 ≤ α ≤ , α = 1 , ρ ≥ 0 , ν ∈ [0 , 1] (4) i i use multiple kernels simultaneously. MKL was initially used ℓν i with multiple copies of the same kernel function with differ- ent hyperparameter settings. However, MKL has been found where α is Lagrange multiplier, ν is a user specified param- i most effective in cases where the different kernel functions eter that defines the upper bound on the training error, and use different attributes, such as in computer vision where also the lower bound on the fraction of training points that SVMs that use a convex combination of kernels using mul- are support vectors, ρ is a bias term and k is the kernel ma- tiple feature sets such as color, shape, and texture, have trix. Once this problem is solved at least νℓ training points with non-zero Lagrangian multipliers ( ~ α ) are obtained and these points { x : i ∈ [ ℓ ] , α > 0 } are called support vectors.

i i ⌊ n/w ⌋ b ∑ The selected points can be marginal I = { i : 0 < α < 1 } m i ¯ ~ x = ⌊ n/w ⌋ ~ x . (8) iab iak and non-marginal I = { i : α = 1 } support vectors.

nm i k = ⌊ n/w ⌋ ( b − 1)+1 Once ~ α is obtained, SVMs compute the following decision where ~ x is the k th time point in the a th variable of ~ x .

function. iak i Then, for each variable, we fit a normal distribution to all ∑ ∑ the training data, choose a number of bins c , and then find a f ( ~ x ) = sign ( α k ( ~ x , ~ x ) + k ( ~ x , ~ x ) − ρ ) j i i j i j equiprobable bins with breakpoints β , β , . . . , β such a, 1 a, 2 a,c − 1 a i ∈I i ∈I m nm that the area under the normal density function for x ≤ β , a, 1 (5) x ∈ [ β , β ] for all k ∈ { 1 , 2 , . . . , c − 2 } , and for a,k a,k +1 a x ≥ β are each 1 /c . We assign each bin a discrete a,c − 1 a a If the decision function predicts a negative label for a given ¯ label (e.g., letters A, B, C, etc.). We replace ~ x with the iab test point x j , then it is classified as an outlier. Test examples corresponding discrete label.

with positive labels are classified normal.

So ~ x and ~ x started off having v continuous variables and i j n time points per variable, and are replaced by a new ma-

3.2 Building Kernel

trix that still has v variables but has w discrete symbols per In this research our kernel takes the form of, variable representing the means of that variable in the w consecutive time windows. The advantages of implementing SAX are that both the time and amplitude discretization k ( ~ x , ~ x ) = ηK ( ~ x , ~ x ) + (1 − η ) K ( ~ x , ~ x ) (6) i j d i j c i j result in reduction of the noise content and as well as di- where K is a kernel over discrete sequences, K is a kernel d c mensionality of the data. The distance between the SAX over discretizedd continuous time series, and η is used to representations of ~ x and ~ x is simply the nLCS length as i j weight the two kernels (in this paper, we always use η = 0 . 5).

shown above in equation (7). Looking at empirical formula- We have tion of the similarity measure and how the above kernels are constructed it is pretty strightforward to understand that | LCS ( ~ x , ~ x ) | i j both K and K are symmetric positive semi-definite matri- d c K ( ~ x , ~ x ) = √ , (7) d i j ces.

l l ~ x ~ x i j where l is the number of symbols in sequence ~ x . Given ~ x

3.3 Baseline Algorithms

two sequences X and Z , Z is a subsequence of X if re- Both Orca and SequenceMiner have been chosen as the moving some symbols from X produces Z . Z is a common baseline algorithms. To the author’s knowledge, besides subsequence of sequences ~ x and ~ x if Z is a subsequence i j Orca no other anomaly detection algorithm exists that can of both ~ x and ~ x . The longest such subsequence of ~ x and i j i handle both discrete and continuous data streams. Orca ~ x is called the longest common subsequence (LCS) and is j [2] is a K-nearest neighbor approach outlier detection algo- denoted by LCS ( ~ x , ~ x ) and | LCS ( ~ x , ~ x ) | is length. LCS i j i j rithm with a modified pruning technique. For continuous is a useful metric for measuring similarity between discrete data, Orca takes a nominal reference data set and calcu- sequences for two reasons. First, it is not restricted to a lates the nearest neighbors’ using Euclidean distance to all location-based one-to-one match—the LCS can be located test points in the original vector space. For binary data within different parts of the two original sequences. Second, points the Hamminging distance is used. Each data point the LCS length has an optimal substructure property which is scored independently and therefore anomalies in the tem- is the foundation of a well-known dynamic programming al- poral domain are undetectable. SequenceMiner computes gorithm. In particular, the algorithm builds up a table L outliers by comparing a set of sequences using the normal- such that entry L ( i, j ) is the length of the LCS of the first ized longest common subsequence as the similarity metric.

i symbols in ~ x and the first j symbols in ~ x . Entry L ( i, j ) i j Sequences that are similar are clustered together. Outliers only depends on entries of L for lower values of i and j .

are sequences that have a very low similarity values with the Details on the Hunt-Szymanski algorithm which we used to clusters medoid. Since sequenceMiner takes into account the calculate LCS can be found in [10].

order it has the ability to identify anomalies in the temporal The continuous kernel K ( ~ x , ~ x ) is inversely proportional c i j domain, however it is unable to handle continuous data and to the distance between the SAX representations [14] of ~ x i therefore does not have the ability to detect anomalies in and ~ x . Briefly, ~ x and ~ x are first divided into some number j i j continuous parameters. Both the baseline algorithms have w bins along the time axis. That is, if both vectors have their codes open sourced and can be obtained from the fol- v variables for n consecutive time points each, then they lowing links are divided into w consecutive bins with all v variables and To test the robustness of the MKAD method synthetic of mostly equal time length (all but the last one contain data was generated with various types of seeded faults, al- ⌊ n/w ⌋ consecutive time steps and the last bin contains the lowing the algorithm to demonstrate its ability to detect remainder). The mean value of each variable in each frame each anomaly and for comparison against the existing state- ¯ is then calculated. So, for example, ~ x is the mean of the iab of-the-art algorithms. Finally the MKAD method was com- values in the b th time interval of the a th variable of ~ x , i pared with the combined performance of Orca and SequenceM- In all equations related to the discrete and continuous ker- iner.

nels, we assume that the discrete and continuous parts of the data points ~ x and ~ x are selected. To reduce notational https://dashlink.arc.nasa.gov/algorithm/orca/ and i j clutter, we will not include operators to select the discrete https://dashlink.arc.nasa.gov/algorithm/sequenceminer- or continuous parts of the data points. algorithm/ Table 1: The table represents the summary of the perfor-

3.4 Synthetic data sets

mance of all three algorithms in detecting the faults in the To simulate an aircraft system it was assumed that the synthetic data for each fault category. A total of 12 faults pilot inputs (the discrete switches) are used to influence the have been randomly injected, out of which 3 are continuous measured continuous output parameters. Therefore the data and 9 are discrete. Clearly MKAD was the only algorithm parameters were generated with this in mind. Ten binary to detect all fault types.

parameters were generated with three fundamental behav- iors: random flipping, constant throughout, and deliberate Algorithms Correct detection switching. One parameter was set to randomly switch be- (of faults) tween 0 and 1, while two parameters never changed states.

Discrete Continuous For the deliberate switching six channels would hold a value Orca 0 100% at their initial state and change to the alternate state when SequenceMiner 89% 0 a separate channel toggled 0 to 1.

MKAD method 100% 100% With the binary parameters generated, the underling sys- tem state can be used to generate continuous data. To con- struct the continuous data, each continuous parameter was Fault type II: The second kind of fault involves extra switch- assigned a set of binary parameters as input variables. A ing where sequence of switching that were not expected set of Gaussian distributions defined for each possible bi- did occur, such as landing gear retracted after being nary state corresponding to the continuous parameter. For deployed on final approach.

example: if a given continuous parameter was dependent on 2 binary parameters 4 distributions would be generated, if Fault type III: The final kind of discrete fault describes out 3 binary parameters, 8 distributions and so forth (see fig- of order switch sequence. A typical example is landing ure 3). At each time step the continuous parameters would gear deployed before initial flaps when the aircraft was draw from its defined distribution for the given state of the below flaps limit.

binary parameters. This method allows the continuous pa- rameters to vary directly with the state of the binary inputs Fault type IV: Apart from all the above three, abnormal and therefore have the desired relationship assumed for this patterns (independent of discrete variables) were in- problem.

jected in arbitrary continuous channels. Such an anomaly may occur with high bank angles or rate of descent be- low 1,000 ft.

After the data was generated some preprocessing steps are required before the algorithm can be implemented. The details of the preprocessing steps have been discussed in a later section. Here we propose to conduct a proof- of-concept study that demonstrates the feasibility of using the proposed MKAD algorithm in detecting variety of anomalies those injected in the synthetic data set.

Table 1 shows the summary of the outcomes. Since the actual fault injection incidents are known, we are able to evaluate the performance of all algorithms in detecting those faults. Out of twelve injected faults, Orca was able to find the three continuous anomalies. Even though Orca can handle both discrete (binary) variables and continuous vari- ables, the algorithm is unable to detect sequential anoma- lies where the time information is embedded in some form.

Figure 3: The figure demonstrates a sample distribution for SequenceMiner, using 1- σ threshold calculated from the ref- a single continuous parameter that is dependent on 2 binary erence set, was able to detect most of the discrete anomalies parameters.

and clearly missed all the continuous anomalies. Whereas the MKAD technique stands out accross all the algorithms This method was repeated for each flight in the data set.

since it was able to identify all twelve fault types (both dis- A total of 4000 flights were synthesized (2000 for training crete and continuous).

and 2000 for testing) . Each flight is 1500 sample points long. Four different fault types, three examples of each, 3.5 Real World Analysis on FOQA Data were injected into randomly chosen flights. bodydetails The real world data set chosen for analysis is from a re- gional carrier in the U.S. who is part of the DNFA. All air- Fault type I: The first type of fault involves missing switches craft analyze were of the same fleet and type (narrow body and this implies that sequences of switching that was jet), with a subset of flights that landed on the same run- expected at a given stage did not occur. For example, way at a single airport for an entire year, resulting in ap- such an event takes place when flaps not extended to proximately 3500 total flights. Each flight consists of 160 normal full deployment at landing.

parameters sampled at 1 Hz with the average flight length 4 approximately 1:45 hours.

The synthesized data set can be downloaded from https://dashlink.arc.nasa.gov/topic/multiple-kernel- 3.5.1 Data Preparation learning-based-heterogeneous-algorithm/ Data analysis was focused on the portion of the flight be- sequences are generated (Figure 4) the discrete kernel is tween 10,0000 ft. Mean Sea Level (MSL) to landing, using computed pairwise across for all possible flight combinations the deployment of the thrust reversers as a means to deter- in the training set. For the continuous data, each time se- mine touchdown. To account for parameters that recorded ries was SAX transformed using the technique described bad data, such as noisy sensors or sensor values reaching in Section 3.2. In the original version of SAX, the z-score cut-off value or unreasonable data values, a conservative normalization is an integral part of the algorithm. However data quality filter was applied to all 3500 flights, return- in this research, we normalized each time series (only once) ing approximately 2500 ”cleaned” flights. Since the filtering before it is SAX transformed. We are able to maintain con- was conservative, to insure that significant anomalies were sistency in choosing the alphabet size for both reference and not removed, some flights that partially contained bad data test sets. It is worth mentioning that the window size was were not eliminated from the data set. An aggressive data also kept fixed through out the analysis. The window size quality filter was applied to the remaining set of flights to de- and alphabet size were both set to 10. Once the SAX repre- termine a nominal set for training (returning approximately sentations are obtained, another kernel is computed pairwise 500). For parameter selection a domain expert provided a across for all possible flight combinations. Each element of list of 39 relevant continuous parameters that were extracted this kernel is the average of the pairwise comparison across for analysis. The flap position parameter was continuously the parameters of any two flights. In the optimization, we recorded, however is categorical in nature. Using input from have set the ν parameter of one-class SVMs to 0 . 1. For the domain expert and statistics from the data the flap pa- testing, the support vectors are used to calculate the pair- rameter was discretizedd into 3 states. These 3 binary state wise similarity between all testing flights. The discrete and variables were combined with landing gear and ground spoil- continuous kernels for test data were generated in a similar ers for sequence analysis. fashion as the training.

The working data set consists of approximately 2500 flights 3.5.3 Result Summary with varying lengths and each of these flights are multidi- mensional heterogeneous time series. For continuous data, The MKAD method reported a total of 227 anomalous the mean and standard deviation are calculated for each pa- flights and assigned an appropriate anomaly score to each rameter across all training flights. These statistics are then of these flights. A simple post-processing method is used used in both training and testing to z-score normalize each to rank the anomalous flights and decompose the anomaly parameter and flight to maintain consistency.

score of individual flight in terms of discrete (parameters) and continuous (parameters) contributions. This results in 3.5.2 Experimental Details three distinct categories, a list of flights with anomalies in ei- When using Orca to analyze the flights, the z-score nor- ther discrete parameters or continuous parameters or in both malized temporal features of all the flights corrosponding to (i.e. heterogeneous). The MKAD algorithm detected 19 dis- the training set were concatenated. The test set was gen- crete, 94 continuous and 114 heterogeneous anomalies. We erated by concatenating all the test flights. The discrete have observed that the majority of the top ranking anomalies inputs to Orca are in standard binary format and the num- belong to the heterogeneous category. Some of these hetero- ber of nearest neighbors were set to the default value (k=5). geneous anomalies have distinct discrete-continuous interac- For SequenceMiner the binary states (of the discrete vari- tions i.e. a sequence of unexpected events in the discrete ables) were translated into state transitions where only the parameters results in some abnormal effects in the continu- bit changes (switching) were logged as a sequence of transi- ous variables or a series of abnormal event in the continuous tions. Figure 4 represents a snapshot of ten such flights rep- parameters prompts some necessary changes in the states resenting sequential data. The SequenceMiner model builds of the discrete variables. We will elaborate on this using clusters in the sequence space and the number of clusters examples in the analysis section.

were determined to be 3 for this analysis. This is because 3.5.4 Statistically Significant Anomaly we observed three distinct clusters in the reference set.

Using the feedback from the domain expert we identified a good number of anomalous flights which are operationally significant while the majority are statistically significant.

Most of the flights in the list of discrete anomalies and some from the heterogeneous category were identified anomalous because they fall outside the distribution of (most) observed values. This does not necessarily mean that the detected anomaly is operationally significant. Table 2 represents a typical distribution of the deployment of landing gears as a function of flap settings. According to the domain expert there is nothing unusual in deploying the landing gear before ◦ flap-1 setting (10 ). In fact it is acceptable if the pilot slows down the aircraft by deploying the landing gear while tran- Figure 4: This figure represents a snapshot of a typical se- siting from cruise to descent. Such an example was picked quences generated from the binary input. Each sequence up as a statistically significant anomaly due to the fact that represents an unique flight. Examples of similar sequence it is a low occurance event. For similiar reason, we have (Flight 5 and Flight 6) and dissimilar sequence (Flight 7 observed a number of anomalous flights with either flap-1 and Flight 9) are shown.

The source code of SAX can be obtained from the authors’ For the multiple kernel heterogeneous algorithm, once the website at http://www.cs.ucr.edu/ eamonn/SAX.htm.

Table 2: The table (top) shows the details on how landing gears are deployed as a function of flap settings. The second part of the table provides statistics on the typical settings of flaps during the landing phase. The numbers in each cell represents the percentage of flights that fall under that particular category. This information helps explaining why some of the statistically significant anomalies are detected by the MKAD algorithms.

Gear ordering Before Between Between ◦ ◦ ◦ ◦ ◦ flaps 10 flaps 10 − 20 flaps 20 − 45 % of flights 1% 78% 21% ◦ ◦ Flaps setting Flaps 10 above Flaps 10 below No full flaps deployed 10k feet 10k feet + full flaps at landing % of flights 2% 96% 2% setting before 10 , 000 ft of altitude and/or full-flap not at tional lift that can make it hard for the pilot maintain the all deployed during landing. Table 2 provides the statistics aircraft’s course, and therefore the pilot may not have de- of various flap settings as a function of altitude. The other ployed full-flaps because of these environmental conditions.

important category of anomalies which resulted from this The fourth anomalous flight is an abnormal approach and analysis are clusters of flights with a common set of bad data the only one identified as a continuous anomaly (refer Figure sources (bad sensors) having common tail numbers which is 8). The flight shows high control column and fuel flow fluc- a valuable maintenance information. tuations beginning slightly before 10 miles to landing, which coincides with the altitude fluctuations. The domain expert said this is an interesting flight since the pilot had abnormal 3.5.5 Operationally Significant Anomaly: Analysis altitude deflections and was under glide slope, however the In this section we will present some examples identified pilot was still able to line up on glide slope at 5 miles to as operationally significant by a domain expert. The first landing, which is required to maintain a stable approach.

anomalous flight is a go-around (where the pilot aborted the landing, climbed, circled around, and landed) and is classi- fied by the algorithm as a heterogeneous anomaly. The top anomalous continuous parameters are plotted in Figure 5.

All continuous parameters show abnormally high deflections during the maneuver. The anomalies found in the discrete sequence confirmed the maneuver by identifying the extra switching due to the pilot retracting the landing gear and flaps during the climb and redeploying for landing on the second approach.

The second anomalous flight is also identified as hetero- geneous anomaly with unusually high air speed when com- pared to a set of reference flights. Figure 6 shows the rela- tionship between air speed and altitude with the air speed remaining high at 2500 ft MSL. The anomaly identified in the sequence indicates the landing gear was deployed before the flaps. The domain expert said that this ordering may not be unusual but the pilot could be using the landing gear to bleed off air speed, which is evident after the landing Figure 5: Top anomalous parameters associated with a go- gear is deployed. This behavior demonstrates an interac- around. The top left plot shows the control column and tion between the continuous and sequential variables, i.e.

wheel positions associated with the maneuver. The top right due to the aircraft’s high speed at a low altitude the pilot plot shows high fuel flow consumption related to the climb.

was prompted to deploy the landing gear, which in return The bottom left plot shows the high acceleration in the lon- resulted in a delayed effect in a lower air speed.

gitudinal direction. The bottom right plot shows the 3 di- The third anomalous flight is also identified as a hetero- mensional track of the aircraft (the go-around maneuver is geneous anomaly with indications of gusty winds. The top denoted by the dotted lines) contributing parameters are plotted in Figure 7, with the exception of wind speed, since it was not analyzed by the algorithm. The domain expert saw the large swings in drift 3.5.6 Discussions angle and concluded that there may have been high winds.

The wind speed plot shows that there were indeed high gusts It is important to note that the combined anomaly lists of up to 70 mph during the approach, which is also apparent from Orca and SequenceMiner were able to detect some but in the control column/wheel and lateral accelerations. The not all of the 4 anomalies just discussed. For the go-around anomaly identified in the discrete sequence was that flaps and air speed anomalies SequenceMiner is able to detect the fully deployed at 45 degrees was not present at landing. The anomalies, however Orca did not. Both the anomalies have domain expert said that landing with flaps set at 20 degrees components that are sequential in nature (the go-around is considered an approved landing flaps setting for this par- having additional flaps and landing gear switches, and the ticular aircraft and may not indicate an anomaly, however air speed anomaly deploying the landing gear early to bleed during high cross wind conditions full flaps provide addi- off speed) and, therefore it upholds that SequenceMiner de-

Figure 8: Top anomalous parameters associated with the abnormal approach anomaly. The top left plot shows the Figure 6: For the high airspeed anomaly the top anomalous high control column position. The top right plot shows the parameter (airspeed) is plotted against altitude. The speed large swings in fuel flow activity. The bottom plot shows limit threshold at 10,000 ft. is denoted by the dashed line the altitude vs. the distance to landing with the glide slope at 250 knots.

and glide slope deviation superimposed.

as an outlier, resulting in 72 anomalous flights.

Table 3 shows the overlap between the baseline algorithms and MKAD. As expected Orca performs well at detecting mostly the continuous anomalies found by MKAD, while Se- quenceMiner identifies anomalies related to discrete and/or heterogeneous anomalies found by MKAD. However MKAD still finds a significant number of anomalies that the com- bined baseline set does not detect. From the proof of con- cept study we have observed these limitations of Orca and SequenceMiner in identifying anomalies which are respec- tively discrete and continuous in nature. This is due to the fundamental nature of the baseline algorithms. However the MKAD is able to compress and appropriately combine the information from both discrete and continuous domain, to detect anomalies. This has also been reflected in the analy- sis of the real world data set, where the baseline algorithms Figure 7: Top anomalous parameters associated with the missed some of the operationally significant anomalies de- gusty wind anomaly. The top left plot shows the control tected by MKAD.

column and wheel positions. The top right plot shows the high drift angle. The bottom left plot shows high lateral (side-to-side) accelerations. The bottom right plot shows

4. CONCLUSIONS

the wind speed gusts.

The current state-of-the-art algorithms have both strengths and short comings in detecting a variety of anomalous con- ditions, as discussed in the detection of the 4 real world tects the anomaly while Orca, who treats all points indepen- anomalous flights. The MKAD method aims to combine dently, did not. In the case of the gusty winds and abnormal both strengths into a single approach to allow for detection approach anomalies, both Orca and SequenceMiner were un- of a variety of anomalies. This is not to say the proposed al- able to detect these anomalies.

gorithm is able to find all possible anomalies in the data, but Baseline results were obtained by running Orca, SequenceM- rather that it is robust enough to find a significant overlap iner and compared with those obtained from MKAD method with the current state-of-the-art methods while also detect- on the FOQA data set described above. It has been ob- ing additional operationally significant anomalies in hetero- served that the average flight length is approximately 1500 geneous data sources. Other approaches such as exceedance sample points in this data set. Based on this information queries can be very efficient in detecting specific anomalies, we allowed Orca to report back the same number of sample however the goal is not to continue to find anomalies that points ( ≈ 350 , 000) which is equivalent to those 227 flights are already being studied, but to develop a novel method identified by MKAD. Any flight that had less than 15 sam- that ” ..answers some of the questions what we didn’t think ple points labeled anomalous which is approximately 1% of to ask.. ” while analyzing FOQA data set.

the average flight length and this resulted in 674 outliers reported by Orca. For SequenceMiner we have calculated

5. ACKNOWLEDGMENTS

a 2 − sigma threshold from the reference set and considered any sequence that was above that threshold in the test set This project was supported by the NASA Aviation Safety

Table 3: In this table we compare the detection performance of Orca, SequenceMiner and the MKAD algorithm on aviation safety data set. The objective is to show the statistics of overlapping anomalous flights which fall under either discrete, continuous and heterogeneous categories. Total number of anomalous flights detected by each algorithms are also reported.

The results of the MKAD algorithm is also compared with the combined outcome of Orca and SequenceMinier.

Algorithms Overlap of anomalous flights (with MKAD) Discrete Continuous Heterogeneous Orca 21% 59% 34% SequenceMiner 30% 0% 54% Combined Orca and SequenceMiner 58% 59% 67% MKAD method 19 94 114 Program, Integrated Vehicle Health Management Project. and M. Jordan. Learning the kernel matrix with The authors would like to thank Robert Lawrence for his semidefinite programming. Journal of Machine invaluable domain expertise and Dr. Irv Statler for his in- Learning Research , 5:27–72, 2004.

sightful discussions.

[14] P. Patel, E. Keogh, J. Lin, and S. Lonardi. Mining motifs in massive time series databases. In International Conference on Data Mining , 2002.

6. REFERENCES

[15] B. Sch¨ olkopf, J. C. Platt, J. C. Shawe-Taylor, A. J.

[1] F. Bach, G. Lanckriet, and M. Jordan. Multiple kernel Smola, and R. C. Williamson. Estimating the support learning, conic duality, and the smo algorithm. In of a high-dimensional distribution. Neural International Conference on Machine Learning , 2004.

Computation , 13(7):1443–1471, 2001.

[2] S. D. Bay and M. Schwabacher. Mining distance-based [16] B. Sch¨ olkopf and A. Smola. Learning with Kernels .

outliers in near linear time with randomization and a MIT Press, 2002.

simple pruning rule. Proceedings of The Ninth ACM [17] D. M. Tax and R. P. Duin. Support vector domain SIGKDD International Conference on Knowledge description. Pattern Recognition Letters , Discovery and Data Mining , 2003.

20(1113):1191–1199, 1999.

[3] N. T. S. Board. Loss of control and impact with [18] A. S. Team. Statistical summary of commercial jet pacific ocean alaska airlines flight 261. 2002.

airplane accidents. Technical report, Boeing [4] S. Budalakoti, A. N. Srivastava, and M. E. Otey.

Commercial Airplanes, 2007.

Anomaly detection and diagnosis algorithms for [19] H. Zhang, A. Berg, M. Maire, and J. Malik. Svm-knn: discrete symbol sequences with applications to airline Discriminative nearest neighbor classification for safety. IEEE Transactions on Systems, Man, and visual category recognition. In Computer Vision and Cybernetics, Part C: Applications and Reviews , Pattern Recognition , pages 2126–2136, 2006.

39(1):101–113, 2008.

[5] C. J. C. Burges. A tutorial on support vector machines for pattern recognition. DMKD , 2:121–167, 1998.

[6] V. Chandola, A. Banerjee, and V. Kumar. Anomaly detection: A survey. ACM Computing Surveys , 2009.

[7] O. Chapelle and P. Haffner. Support vector machines for histogram-based classification. IEEE Transactions on Neural Networks , 10(5):1055–1064, 1999.

[8] S. Das, B. Matthews, K. Bhaduri, N. Oza, and A. Srivastava. Detecting anomalies in multivariate data sets with switching sequences and continuous streams. In NIPS 2009 Workshop: Understanding Multiple Kernel Learning Methods , 2009.

[9] Z. Harchaoui and F. Bach. Image classification with segmentation graph kernels. In Computer Vision and Pattern Recognition , pages 1–8, 2007.

[10] J. Hunt and T. Szymanski. A fast algorithm for computing longest common subsequences.

Communications of the ACM , 1977.

[11] D. L. Iverson. Inductive system health monitoring.

Proceedings of the 2004 International Conference on Artificial Intelligence (IC-AI’04), CSREA Press, Las Vegas, NV , 2004.

[12] H. Kashima, K. Tsuda, and A. Inokuchi. Kernels for graphs. Kernel Methods in Computational Biology , 39(1):101–113, 2004.

[13] G. Lanckriet, N. Cristianini, L. E. Ghaoui, P. Bartlett,