代写代考 COMP90073 Security Analytics

Anomaly Detection Using Support Vector Machines
COMP90073 Security Analytics
, CIS Semester 2, 2021

• ReviewofSVM
• SupportVectorDataDescription(SVDD)
• One-classSupportVectorMachine(OCSVM) • RecentdevelopmentsofOCSVM/SVDD
COMP90073 Security Analytics © University of Melbourne 2021

SVM – Revision
Classification rule
Training objective
COMP90073 Security Analytics © University of Melbourne 2021

Large Margin Classifiers – Revision
• Findhyperplanemaximisesthemargin=>B1isbetterthanB2
• Margin:sumofshortestdistancesfromtheplanestothepositive/negative samples
Support Vectors
COMP90073 Security Analytics © University of Melbourne 2021

Solving the Optimization Problem – Revision
Primal problem: solve for w and b
min!” 𝑤” s.t. 𝑦#𝑤$𝜙𝑥# +𝑏≥1,∀𝑖=1,…,𝑛
Equivalent dual problem formulation: solve for α1…αL: Lagrange multipliers for each data point
max4𝛼# −244𝛼#𝛼( 𝑦#𝑦( 𝐾(𝑥#,𝑥()
4𝛼#𝑦# =0 #&!
More convenient to solve
COMP90073 Security Analytics © University of Melbourne 2021

Soft Margin Classification – Revision
• Slack variables ξi can be added to allow misclassification of difficult or noisy examples, resulting margin called soft.
1) min 𝑤 %+𝐶)𝜉&
𝑦&𝑤*𝜙𝑥& +𝑏≥1−𝜉&,∀𝑖=1,…,𝑛 𝜉& ≥ 0, ∀ 𝑖 = 1, … , 𝑛
COMP90073 Security Analytics © University of Melbourne 2021

Anomaly Detection using SVM
• Assumption:All(ormajorityof) training examples belong to the normal (positive) class.
• Objective:identifyanomaliesby modeling normal pattern
– SupportVectorData Description (SVDD) [1]
– One-classSupportVector Machine (OCSVM) [2]
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD) [1]
• Findtheminimalcircumscribinghyperballinhigh- dimensional space encompass (almost) all the observations.
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
• Findtheminimalcircumscribinghyperballinhigh- dimensional space encompass (almost) all the observations.
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
• Findtheminimalcircumscribinghyperballinhigh- dimensional space encompass (almost) all the observations
Support Vector
Anomaly/noise
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
• Findtheminimalcircumscribinghyperballinhigh- dimensional space encompass (almost) all the
Support Vector
observations
) min 𝑅% + 𝐶 ) 𝜉&
𝜙𝑥& −a%≤𝑅%+𝜉&,∀𝑖=1,…,𝑛
𝜉& ≥ 0, ∀ 𝑖 = 1, … , 𝑛
– 𝑅:Reduceoftheball
– 𝜉:Slackvariable
– a:Centeroftheball
– 𝜙(.):non-linearfunction
Anomaly/noise
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
Lagrangian form:
𝐿a,𝑅,𝝃,𝜶,𝜸 =𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
where, 𝛾& ≥ 0 and 𝛼& ≥ 0 are Lagrange multipliers.
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
Lagrangian form:
𝐿a,𝑅,𝝃,𝜶,𝜸 =𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
where, 𝛾& ≥ 0 and 𝛼& ≥ 0 are Lagrange multipliers.
Set the derivatives with respect to the primal variables 𝑅, a, 𝝃 equal to zero, we get
• ,- =? ,$!
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
Lagrangian form:
𝐿a,𝑅,𝝃,𝜶,𝜸 =𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
where, 𝛾& ≥ 0 and 𝛼& ≥ 0 are Lagrange multipliers.
Set the derivatives with respect to the primal variables 𝑅, a, 𝝃 equal to zero, we get
•,-=2𝑅−2𝑅∑) 𝛼=0 ,+ &'( &
• ,- =? ,$!
∑) 𝛼=1 &'( &
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
Lagrangian form:
𝐿a,𝑅,𝝃,𝜶,𝜸 =𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
where, 𝛾& ≥ 0 and 𝛼& ≥ 0 are Lagrange multipliers.
Set the derivatives with respect to the primal variables 𝑅, a, 𝝃 equal to zero, we get
•,-=2𝑅−2𝑅∑) 𝛼=0 ,+ &'( &
•,-=2a∑) 𝛼−2∑) 𝛼𝜙𝑥 =0 ,a &'( & &'( & &
• ,- =? ,$!
∑) 𝛼=1 &'( &
a=∑) 𝛼𝜙(𝑥) &'( & &
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
Lagrangian form:
𝐿a,𝑅,𝝃,𝜶,𝜸 =𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
where, 𝛾& ≥ 0 and 𝛼& ≥ 0 are Lagrange multipliers.
Set the derivatives with respect to the primal variables 𝑅, a, 𝝃 equal to zero, we get
•,-=2𝑅−2𝑅∑) 𝛼=0 ,+ &'( &
•,-=2a∑) 𝛼−2∑) 𝛼𝜙𝑥 =0 ,a &'( & &'( & &
• ,-=𝐶−𝛼&−𝛾&=0 ,$!
∑) 𝛼=1 &'( &
a=∑) 𝛼𝜙(𝑥) &'( & &
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
𝐿 a,𝑅,𝝃,𝜶,𝜸 )))
=𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
∑) 𝛼=1 &'( &
a=∑) 𝛼𝜙(𝑥) &'(& &
𝐶 = 𝛼& + 𝛾&
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
𝐿 a,𝑅,𝝃,𝜶,𝜸 )))
=𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
= 𝑅% + 𝐶 ) 𝜉&
+)𝛼&𝑘 𝑥&,𝑥& −2)𝛼&𝜙 𝑥& *a+a*a)𝛼& −𝑅%)𝛼& −)(𝛼&+𝛾&)𝜉&
&'( &'( &'(
∑) 𝛼=1 &'( &
a=∑) 𝛼𝜙(𝑥) &'(& &
𝐶 = 𝛼& + 𝛾&
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
𝐿 a,𝑅,𝝃,𝜶,𝜸 )))
=𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
= 𝑅% + 𝐶 ) 𝜉&
+)𝛼&𝑘 𝑥&,𝑥& −2)𝛼&𝜙 𝑥& *a+a*a)𝛼& −𝑅%)𝛼& −)(𝛼&+𝛾&)𝜉&
&'( &'( &'(
=a! =1=1=C ∑) 𝛼=1
a=∑) 𝛼𝜙(𝑥) &'(& &
𝐶 = 𝛼& + 𝛾&
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
𝐿 a,𝑅,𝝃,𝜶,𝜸 )))
=𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
= 𝑅% + 𝐶 ) 𝜉&
+)𝛼&𝑘 𝑥&,𝑥& −2)𝛼&𝜙 𝑥& *a+a*a)𝛼& −𝑅%)𝛼& −)(𝛼&+𝛾&)𝜉&
=)𝛼&𝑘𝑥&,𝑥& −a*a &'(
∑) 𝛼=1 &'( &
a=∑) 𝛼𝜙(𝑥) &'(& &
𝐶 = 𝛼& + 𝛾&
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
𝐿 a,𝑅,𝝃,𝜶,𝜸 )))
=𝑅%+𝐶)𝜉&−)𝛼& 𝑅%+𝜉&− 𝜙𝑥& −a* 𝜙𝑥& −a −)𝛾&𝜉& &'( &'( &'(
= 𝑅% + 𝐶 ) 𝜉&
+)𝛼&𝑘 𝑥&,𝑥& −2)𝛼&𝜙 𝑥& *a+a*a)𝛼& −𝑅%)𝛼& −)(𝛼&+𝛾&)𝜉&
&'( &'( &'(
=)𝛼&𝑘𝑥&,𝑥& −a*a &'( ))
∑) 𝛼=1 &'( &
=)𝛼&𝑘 𝑥&,𝑥& −))𝛼&𝛼.𝑘(𝑥&,𝑥.)
&'( &'( .'(
a=∑) 𝛼𝜙(𝑥) &'(& &
𝐶 = 𝛼& + 𝛾&
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
)) argmax)𝛼&𝑘 𝑥&,𝑥& −))𝛼&𝛼.𝑘(𝑥&,𝑥.)
0≤𝛼≤𝐶, ∑)𝛼=1 & &'( &
Support Vector
Anomaly/noise
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
)) argmax)𝛼&𝑘 𝑥&,𝑥& −))𝛼&𝛼.𝑘(𝑥&,𝑥.)
0≤𝛼≤𝐶, ∑)𝛼=1
Support Vector
a R 𝜉” Anomaly/noise
• 𝜙𝑥& −a%<𝑅%→𝛼&=0 • 𝜙𝑥& −a%=𝑅%→0<𝛼&<𝐶 • 𝜙𝑥& −a%>𝑅%→𝛼&=𝐶
COMP90073 Security Analytics © University of Melbourne 2021

Support Vector Data Description (SVDD)
•a=∑) 𝛼𝜙(𝑥) &'(& &
• 𝑅% = 𝜙 𝑥& −a %,where,𝑥& aresupportvectorswith0<𝛼& <𝐶 ))) 𝑅% =𝑘 𝑥&,𝑥& −2)𝛼.𝑘 𝑥&,𝑥. +))𝛼&𝛼.𝑘(𝑥&,𝑥.) &'( &'( &'( COMP90073 Security Analytics © University of Melbourne 2021 Support Vector Data Description (SVDD) •a=∑) 𝛼𝜙(𝑥) &'(& & • 𝑅% = 𝜙 𝑥& −a %,where,𝑥& aresupportvectorswith0<𝛼& <𝐶 ))) 𝑅% =𝑘 𝑥&,𝑥& −2)𝛼.𝑘 𝑥&,𝑥. +))𝛼&𝛼.𝑘(𝑥&,𝑥.) &'( &'( &'( • Newsample𝑧isidentifiedasnormalif ))) 𝑧−a%=𝑧.𝑧−2)𝛼.𝑧.𝑥& +))𝛼&𝛼.𝑥&.𝑥. ≤𝑅% &'( &'( &'( COMP90073 Security Analytics © University of Melbourne 2021 One-class Support Vector Machine (OCSVM) [2] • Mapinputdataintoahighdimensionalfeaturespace • Iterativelyfindsthemaximalmargininthehyperplanewhichbestseparatesthe training data from the origin • Decisionboundary 𝑤⋅𝜙𝑥& −𝜌=0 • Formulatetheoptimizationproblemsoitreturnspositiveforasmanyofthe N training examples as possible. COMP90073 Security Analytics © University of Melbourne 2021 OCSVM Intuition COMP90073 Security Analytics © University of Melbourne 2021 • Solvequadraticproblem min 𝑤 + )𝜉&−𝜌 !,$!,0 2 𝜈𝑛 &'( 𝑤⋅𝜙 𝑥& ≥𝜌−𝜉&,∀𝑖=1,...,𝑛 𝜉& ≥ 0, ∀ 𝑖 = 1, ... , 𝑛 – Apriorprobabilitythatadatapointinthetrainingsetisananomaly. – Regulatesthetrade-offbetweenfalsepositivesandfalsenegativesinthis – Duetotheimportanceof𝜈,OCSVMisoftenreferredtoas𝜈-SVM COMP90073 Security Analytics © University of Melbourne 2021 One-class Support Vector Machine (OCSVM) • Theproblemcanbesimplifiedto argmin))𝛼&𝛼.𝑘(𝑥&,𝑥.) s.t. 0≤𝛼≤( ∑) 𝛼=1 &3) &'(& COMP90073 Security Analytics © University of Melbourne 2021 One-class Support Vector Machine (OCSVM) • Theproblemcanbesimplifiedto argmin))𝛼&𝛼.𝑘(𝑥&,𝑥.) s.t. 0≤𝛼≤(, ∑)𝛼=1 &3) &'(& • SoftmarginSVMforbinaryclassification: ))) argmin))𝛼&𝛼. 𝑦&𝑦. 𝑘 𝑥&,𝑥. −)𝛼& / &'( .'( &'( s.t. 𝛼≥0,∑)𝛼𝑦=0 & &'( & & COMP90073 Security Analytics © University of Melbourne 2021 One-class Support Vector Machine (OCSVM) • Theproblemcanbesimplifiedto •𝑤=∑) 𝛼𝜙(𝑥) &'(& & argmin))𝛼&𝛼.𝑘(𝑥&,𝑥.) s.t. 0≤𝛼≤(, ∑)𝛼=1 &3) &'(& COMP90073 Security Analytics © University of Melbourne 2021 One-class Support Vector Machine (OCSVM) • Anomalyscorefornewsample𝑧: –𝑆𝑐𝑜𝑟𝑒𝑧=∑) 𝛼𝑘(𝑥,𝑧)−𝜌 &'(& & – 𝑆𝑐𝑜𝑟𝑒 𝑧 < 0: Anomaly – 𝑆𝑐𝑜𝑟𝑒 𝑧 ≥ 0: Normal • Forespecialcaseof(invariant)kernels,e.g.,Gaussian,SVDD≅OCSVM COMP90073 Security Analytics © University of Melbourne 2021 Deep SVDD [4] Figure: Deep SVDD learns a neural network transformation 𝜙(⋅; 𝒲) with weights 𝒲 from input space 𝒳 ⊆ R4 to output space F ⊆ R5 that attempts to map most of the data network representations into a hypersphere characterized by centre 𝑐 and radius 𝑅 of minimum volume. Mappings of normal examples fall within, whereas mappings of anomalies fall outside the hypersphere. COMP90073 Security Analytics © University of Melbourne 2021 Hybrid Deep-1SVM [5] Figure: Deep model (AE) is trained to extract features that are relatively invariant to irrelevant variations in the input, so that the one-class SVM (1SVM) can effectively separate the normal data from anomalies in the learned feature space, using linear kernel. COMP90073 Security Analytics © University of Melbourne 2021 Deep Learning and One-class SVM based Anomalous Crowd Detection [6] Figure: Original video and foreground video sequence are taken as the input of two branches of channel, then movement tracks are extracted to produce continuous motion maps. Training and testing on a hybrid deep learning model SDAE-DBN-PSVM, then follows to achieve anomalous event detection COMP90073 Security Analytics © University of Melbourne 2021 • WhatisSVDD? • HowtoderivedualformulationofSVDD? • HowtoextendSVMtoOCSVM? Next: Autoencoders and their applications COMP90073 Security Analytics © University of Melbourne 2021 References 1. .J. Tax, .W. Duin, “Support Vector Data Description”, Machine Learning, 2004. 2. ̈lkopf, . Platt, -Taylor, . Smola and . Williamson “Estimating the Support of a High-Dimensional Distribution”. Neural Computation, 2001. 3. . Aggarwal,“Outlier Analysis”, Springer, 2016. Chapter 3 4. , , , , Siddiqui, , ̈ller, and . "Deep one-class classification." In International Conference on Machine Learning (ICML), pp. 4393-4402. 2018. 5. , , , and . "High-dimensional and large-scale anomaly detection using a linear one-class SVM with deep learning." Pattern Recognition 58 (2016): 121-134. COMP90073 Security Analytics © University of Melbourne 2021 References 6. , , . Erfani, and . "Deep Learning and One-class SVM based Anomalous Crowd Detection." In IEEE International Joint Conference on Neural Networks (IJCNN), pp. 1-8., 2019. COMP90073 Security Analytics © University of Melbourne 2021 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts