An online support vector machine for abnormal events detectionIntroductionSV novelty detectionOutline of the paperOn-line novelty detectionAdiabatic changes to solutionVectors entering and leaving the margin setAlgorithmDiscussionExperimental validation of the online algorithmConclusionAlgorithms for abnormality detectionOnline abnormality detectionRobust online abnormality detectionDiscussionAbout online novelty detectionParameter tuningKernel designOther online algorithmsPerformance assessment with synthetic dataComparison of OAD and ROAD on a toy exampleSimulation resultsFirst real exampleSecond real exampleConclusionReferencesSignal Processing ] (]]]]) ]]]–]]]An online support vector machine for abnormal events detectionManuel Davya,,1, Fre´de´ric Desobryb,1, Arthur Grettonc,1, Christian DoncarlidaLaboratoire d’Automatique, Ge´nie Informatique et Signal, UMR CNRS 8146, Ecole Centrale de Lille, BP 48,59651 Villeneuve d’Ascq cedex, FrancebSignal Processing group, Department of Engineering, University of Cambridge, Trumpington Street, Cambridge CB2 1PZ, UKcMax Planck Institut fu¨r biologische Kybernetik, Tuebingen, GermanydInstitut de Recherche en Cyberne´tique de Nantes, UMR CNRS 6597, 1 rue de la Noe¨, BP 92101, 44321 Nantes Cedex 3, FranceReceived 13 March 2003; received in revised form 24 March 2005; accepted 27 September 2005AbstractThe ability to detect online abnormal events in signals is essential in many real-world signal processing applications.Previous algorithms require an explicit signal statistical model, and interpret abnormal events as statistical model abruptchanges. Corresponding implementation relies on maximum likelihood or on Bayes estimation theory with generallyexcellent performance. However, there are numerous cases where a robust and tractable model cannot be obtained, andmodel-free approaches need to be considered. In this paper, we investigate a machine learning, descriptor-based approachthat does not require an explicit descriptors statistical model, based on support vector novelty detection. A sequentialoptimization algorithm is introduced. Theoretical considerations as well as simulations on real signals demonstrate itspractical efficiency.r 2005 Elsevier B.V. All rights reserved.Keywords: Abnormality detection; Support vector machines; Sequential optimization; Gearbox fault detection; Audio thump detection1. IntroductionOnline anomaly detection in signals or systems isa general framework which includes many specia-lized applications such as industrial monitoring(motor fault detection [1,2], gas turbine monitoring[3], etc.) or audio restoration [4]. Among the manypossible approaches, some rely on an explicit signalmodel together with probabilistic assumptions.These techniques are usually extremely powerfulinsofar as an accurate and tractable model exists. Inthis paper, we consider another class of approachesin which no signal model is required. Some signalfeatures (also referred to as descriptors or vectors)are extracted from the signal and processedsequentially. Techniques based on such descriptorsare useful when a good signal model cannot befound. More precisely, consider vectors2xt(t ¼ 1; 2; ...) taking values in X. At time t, theproblem we propose to solve is that of decidingARTICLE IN PRESSwww.elsevier.com/locate/sigpro0165-1684/$ - see front matter r 2005 Elsevier B.V. All rights reserved.doi:10.1016/j.sigpro.2005.09.027Corresponding author. Tel.: +33 320 676 013;fax: +33 320 335 418.E-mail addresses: [email protected] (M. Davy),[email protected] (F. Desobry), [email protected](A. Gretton), [email protected](C. Doncarli).1The first three authors are in alphabetical order.2We assume at this step that these descriptors are convenientlyextracted from the signal of interest, and that they carry relevantinformation for abnormal events detection.between hypothesesH0: xt0p0; t0¼ t0; ...; t, (1)H1: xt0p0; t0¼ t0; ...; t  1andxtfp0, (2)where p0is a probability density function (pdf) in Xw.r.t. Lebesgue measure, denoted m. The symbol (resp. f) stands for ‘‘distributed according to’’ (resp.‘‘not distributed according to’’). A general solutionconsists of finding a decision region R such thatZRp0ðxÞ dx ¼ 1  r with mðRÞ minimum, (3)where 0prp1 is a given rate of true positives (i.e., H1decided whereas H1is true). The decision function f isbuilt as f ðxÞX0iffx 2 R , and the decision rule isf ðxÞ wH0H10. (4)Depending on the amount of available priorinformation, there are different approaches toestimate R. The following cases are often met inapplications: The pdf p0is known and R ¼fx 2 X s.t.p0ðxÞ4Zrg. In this case, f ðxÞ¼p0ðxÞZrwhereZris a threshold. In practice, tuning Zraccordingto r may be difficult. Mo reover, p0is generallyunknown in applications. The pdf p0is unknown but its shape is given (e.g.,Gaussian). The distribution parameters (e.g.,mean and covariance matrix) are unknown. Atraining set x ¼fx1; ...; xmg is the used so as tolearn the parameters. The previous detection rulecan be applied. This approach is efficient only ifthe number of training samples is large enough,when compared to the dimension of X [5]. The pdf p0is unknown. Its shape is estimatedfrom the training set using Parzen wind ows [5] orusing any other density estimation technique [6].Here, again, tuning Zris a problem. Moreover,the Parzen windows approach does not allow thatsome abnormal vectors may be in the training set. The pdf p0is unknown. The shape of R is directlyestimated from a training set that may containabnormal vectors. There is no threshold to tune(more precisely, a threshold is automaticallytuned for a given r).The last item in the above list is the scenario weinvestigate in this paper, using kernel-based techni-ques. Kernel-based techniques [7–11] form a generalclass of algorithms that fulfill our requirements.First, they do not require the definition of anexplicit statistical model p0for xt(t ¼ 1; 2; ...).Second, they provide computationally efficientdecision functions whose good properties areestablished theoret ically [7,8,10,12] and practi-cally [10,13–15]. Third, kernels enable process-ing of very-large dimensional vectors (in fact, theyare almost insensitive to the dimension of thevectors), and to non-numeric data such as textstrings, DNA sequences, etc. The approach wepropose in this paper is based on a specific kernelprocedure: