> For the complete documentation index, see [llms.txt](https://ykkim.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ykkim.gitbook.io/wiki/machine-learning/lecture-notes/svm-introduction/svm.md).

# SVM concept

## Reference

### Youtube Lecture

{% embed url="<https://www.youtube.com/watch?v=efR1C6CvhmE>" %}

### Margin

For classification, the shortest distance between the observation and the threshold

### Example 1: Without outlier, 1D data

**Maximum Marginal Classifier**

It is using the threshold to give the largest margin to make classification.

If the margin is halfway between the two end-point observations of red, green, then the margin is the larget.

If the threshold is moved to left or right, the margin becomes smaller.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-cfc1c93e0e825804621a7410b3abc01a9f185d88%2Fimage.png?alt=media)

### Example 2: With outliers, 1D data

If there is an outlier and if misclassifcation of outlier is NOT allowed. then, the Maximum Margin Classifier would NOT classify new observation properly.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-cd8ba247736f16aefcf5b95518b02c40746c9bad%2Fimage%20\(368\).png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-f4b8a66f7ecd06eb4a63e9e2aaedfe601a31bda2%2Fimage.png?alt=media)

**Maximum Margin Classifier** is very sensitive to outliers in the training data

* **Solution:** Allow misclassification

If the threshold is halfway, it allows misclassification. But it can classify new observation more sensibly.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-c09cbaa6af09c87e45b4c4f84c1552531703b8d2%2Fimage.png?alt=media)

New observation will be classify as obese, and makes sense for it is more closer to most obese observations.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-78f4214af21213d33e9b812bb5091b65bcc6f21c%2Fimage.png?alt=media)

### **Soft Margin**

Distance between the observations and threshold, with misclassification.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-4d0f315505fbb6a71174f08481ade9418b67813a%2Fimage.png?alt=media)

How to choose a better **Soft margin**? use cross validation that counts number of misclassification/correct classification to allow in the Soft margin.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-14b397fa0ddf870b991d38702fb9536175ef4b37%2Fimage.png?alt=media)

## **Soft Margin Classifier (Support Vector Classifier)**

Using soft margins to find the best threshold to classify.

**Support Vectors:** Observations on the edge and within the soft margin

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-3f92fff8a4852a5d62499c9704ff4adf814166b2%2Fimage.png?alt=media)

***

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-1fc955312cb1883170883d497e19957c590dd225%2Fimage.png?alt=media)

### **1D, 2D, 3D Support Vector Classifier**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-2514fe387c05e2ba61512cda42a1c9eec1bccbd7%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-8c3f62add08b7c3289cd7df6c7e02e4e5710b9b1%2Fimage.png?alt=media)

The data within the soft margin is misclassified in this example. Use **Cross Validation** to determine that allowing this misclassification results in better classification

For 3D, a plane is used for Support Vector Classifier. For 4D or higher, SVC is a **hyperplane.**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-99fb5b285a40e4a8582cc0177463d9153a60c72a%2Fimage.png?alt=media)

## Support Vector Machine

SVC may not work for certain data without changing the dimensions. Example:

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-cd9cb7b55200661dae07e83f0f77fda6087648e1%2Fimage.png?alt=media)

**Support Vector Machine** can solve this limitation as shown in the following example.

Lets transform the data 1D to 2D ( y=Dosage^2 )

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-ca826b2e1c894524c446b26c0e79b6b571bb9d22%2Fimage.png?alt=media)

Then, it can classify new observation as

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-645a1e9055783a0d772c974efeb190a20abc3838%2Fimage%20\(398\).png?alt=media)

### **Support Vector Machine Concept**

(1) With Low Dimension Data, it may not divide nicely. Then, (2) Move the data into a higher dimension by Kernel function. (3) Find a SVC that separates the higher dimension data

**Question: Which functions to use to make the data into a higher dimension? x^2? x^3?**

Use **Kernel Functions** to systematically find SVC.

Commonly used Kernels

* Polynomial kernel with degree d (d= (Point) d=2 (line), d=3(plane) etc)
* Radial Basis Function (RBF)

Example. Polynomial kernel with d=3

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-e6eb2b754ccc4f07c02fff112412b81ae65ff681%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-060c8722f509ebeef245ba7c8007449b92870b8a%2Fimage.png?alt=media)

### Radial Basis Function (RBF)

Under construction

## Kernel Trick

Kernel functions only calculate the relationships between every pair of points as if they are in the higher dimensions. They actually **do not** do transformation. This trick is known as Kernel Trick.

The Kernel Trick reduces the computation required for **SVM** by avoiding the math that transforms the data from low to high dimension.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-e6871732f488b7cc12712414d0e5d4ac2a376e8a%2Fimage.png?alt=media)

## Polynomial Kernel

An example: $$(ab+r)^d$$

Polynomial kernel computes relationship between pairs of observation(a, b). The parameter *r, d* are determined by cross\*\*-\*\*validation.

* **a,b** are the two observations we want to calculate the high dimensional relationship for
* **r** determines the polynomial coefficient
* **d** is degree of polynomial

> Kernel Trick은 새로운 고차원 공간 H 로 직접 매핑하지 않고, Kernel 함수를 이용하여 H 공간의 내적( dot product)를 얻는 방법임.
>
> H 공간에서 연산이 내적으로 표현되어야 하는 조건이 있음

### **Example: r=0.5, d=2**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-80b54d79444ef14f8eb5b75724bd978998351858%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-1f6fe84a91763abb25d195b1af93426d1aca36f9%2Fimage.png?alt=media)

### **Example: r=1, d=2**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-2224e1fc513956534c36b0e9761d4af7b5265317%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-908947f77a0db795f2dfb91e4918279c6a453f41%2Fimage.png?alt=media)

Using Polynomial kernel, 1D observation a or b is converted to 2D (ignoring z-axis coordinate).

Applying Polynomial kernel is also equivalent to Dot Product between each pair of points.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-224b4e5806a349265c5ced6ec421e757a309a25a%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-c93ebae6eb49a4876227ea2ab6e6b33ca681052b%2Fimage.png?alt=media)

For observation a=9, b=14, the dot product results will give a value of the high-dimension relationship, without actually transforming into a high dimension.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-aac90660a667f68610158561e006c61b325e554a%2Fimage.png?alt=media)

## Radial kernel

Another popular kernel is Radial Basis Kernel.

$$
e^{- \gamma (a-b)^2}
$$

RBF finds SVC in **infinite** dimension, it is hard to visualize the process.

It behaves like a Weighted Nearest Neighbor model. Near observations has more influence than further away observations

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-e92495b818a0e629a2938827e36141d8a406e95d%2Fimage.png?alt=media)

How the Radial Kernel determines how much influence each observation in the **Training Dataset on classifying new observation?** $$e^{- \gamma (a-b)^2}$$

The square function of the difference between a and b with a scale of gamma.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-458bc24fa4d8012d2386a33c6c59ac474d71e7a0%2Fimage.png?alt=media)

### Example: close observations

### a=2.5, b=4 which are two observations that are close to each other.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-08daaac2b4e7cef1e53d9b2b43bb5f631749a844%2Fimage.png?alt=media)

### Example: relative far observations

**a=2.5, b=16**

A number very close zero if the observation points are far from each other.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-9ac34eaed67d7368b63a9f75c9359129377d44e6%2Fimage.png?alt=media)

***

**We get the high-dimension relationship by plug in the values into the Radial Kernel**

***

### **Intuition**

Lets start from **Polynomial kernel** with r=0.

***

**If r=0, d=d,** $$(ab+r)^d=(ab)^d=(a^d) \cdot (b^d)$$

*It shifts the data on the original axis(in the original dimension), WITHOUT making it in a higher dimension.*

For example, when r=0, d=2, (ab+0)^2=(ab)^2.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-8166fcccf4877ea4c97299e569b0710d2fe2ec30%2Fimage.png?alt=media)

***

We can use **Polynomial Kernel with r=0** to explain **Radial Function.**

Lets add polynomial kernels with r=0, but with d increasing with each term.

For adding two terms with d=1 and d=2:

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-6de4d3f2d96d4e730214933c5bd12a50735965c1%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-95aa70001dc2c0e2c3ed47c94f9e58ec9a23e391%2Fimage.png?alt=media)

The terms can be kept adding, with r=0 and d=1 to INF dimension.

Then, it gives a polynomial with infinite number of dimensions.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-a71ed52b6e57c506b53d7ef8c4cf5815327b7f4a%2Fimage.png?alt=media)

**Lets go back to Radial Function.**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-ba9c73452054ca6e8e2785784500009d7d575be8%2Fimage%20\(416\)%20\(1\)%20\(1\).png?alt=media)

The term e^(ab) can be written in Taylor Series that is in terms of Polynomial Kernel with r=0 and d=0 to INF.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-43d9d50d72ac4c8dca0c280e7f20015b625ff557%2Fimage.png?alt=media)

The dot product of e^{ab} is

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-660cd0ec5947cae2b4b938764ed738381ac87ef7%2Fimage.png?alt=media)

Thus, the Radial Kernel becomes

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-3a5fc65d39f4128a0a1d938b2b1d576a3ae8519f%2Fimage.png?alt=media)

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-e189cbe361a3bb01132ec9452837e490b2cbb2ac%2Fimage.png?alt=media)

***

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-c823d0a08718a40435d4c165a23f35c6eeddf397%2Fimage.png?alt=media)

The Radial Kernel is equal to a Dot Product that has coordinates for an infinite number of dimension.

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-d06b311ff2c66a39efbb5315f0ac656a0483c873%2Fimage.png?alt=media)

Thus, the value plugged in the Radial Kernel is the relationship between the two observations in **infinite -dimension.**

![](https://3698175758-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MAwtzMy_pbrChIExFtN%2Fuploads%2Fgit-blob-197c29cc514cbd27cba2222f70e1f6ee977e197f%2Fimage.png?alt=media)