5- SVM

• e.g. training data may include attacks… (we dont know, otherwise we would have labeled data…)

• => accomodate outliers in training data…

• has parameter v -> represents percentage of outliers in training data

• -> model ignores the v percent of data that are most anomaloius (with respect to the rest of the training data)

• => thus can learn model for “normal” even from tainted training data…

• divides n-dimensional space

• -> in 2-dimensions: gerade…

• => can be used to separate datapoints in n-dimensional feature space…

• on same side

• -> have same sign…

• given: linearily separable data set x_i with corresponding labels y_i

• => find hyperplane that all training samples lie on the correct side…

• how to find parameters of hyperplane?

• uniqueness: are there other solutions (i.e. other parameters)

• why should this be optimal? (as there are other possiblitieis if not unique…)

• find hyperplane with sampels on “correct” side

• -> such that two-norm of w is minimized

=> SVM hard margin

• instead of minimizing two norm of w

• -> 1/2 * squared two norm of w

• => can be solved via quadratic programming…

=> results in w,b which determine the SVM

=> SVM(x) -> sgn(w*x+b)

-> optimality?

• maximize distanece of hyperplane to dataplanes

• -> minimize two norm of w

• => but as max distance

• the length of an vector

• data can no be linearily separated

• -> use hinge loss

• -> sum over i

• (max(0,1 - y_i(w*x_i-b))

• solve arg min on w,b

• for some constant lambda with

• arg min [

  • 1/n (where n is amount of data samples)

  • sum over i = 1 to n (

    • max(

      • 0

      • 1-y_i(w*x_i-b)

    • )

  • )

• ]

• +

• lambda * ||w||^2

  
  

• trades off “margin size” and “placing x_i on correct side””

• -> balances bias and variance

• project in higher dimensional space

• -> where it may be linearily separable

• => using a feature map

• -> there exists lots of different featuere maps… (e.g. (x1, x2, (x1^2 + x2^2))

• -> e.g. linear, polynomiyal, RBF

• a function

• φ : R^J → R^K

• where J < K

• k(x_i, x_j)

• =

• dit product (φ(x_i), φ(x_j))

• k_rbf (x_i, x_j)

• =

• e^( −γ ||x_i - x_j||^2)

• with γ > 0

• points on the inside have label +1

• points on the outside have -1

• => construct hyper plane between data and origin (i.e [0,0…,0])

• due to definition of y = 1, the term shortens to sth

• -> can result in unwanted properties (loss = 0 regardeless fo hyperplane…)

• => have to introduce -b to loss…

=> have closer look at math properties of this stuff…

• supervised learning technique for both regression and classification

• can also be used for unsupervised anomaly detection

• -> single hyperparameter k, number of neighbors

• classify new point (x,y) based on neighborhood

• -> namely its k nearest neighbors

  • compute distancec to all other points

  • select k nearest instances

  • determine class by majority vote

• => no training phase…