Linear Separators

• Data를 분리할 linear hyperplane 찾기 (decision boundary, 결정 경계)

• One Possible Solution

$w^T$ : $\theta$ , $b : w_0$

• Another Possible Solution

• Other Possible Solution

---

💡 그렇다면 어떤 linear separator가 가장 적합할까? (optimal)

---

💡 B1, B2 중에 어떤 게 더 좋을까?

⇒ B1이 더 좋음!!
⇒ How do you define better? → defined the margin

• margin이 적으면 적을수록 성능↓

---

점과 선 사이의 거리

• 점 $(x_1, y_1)$과 선 $ax+by+c=0$

  $d = \frac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}}$

• 점 $(x_1, y_1, z_1)$과 평면 $ax+by+cz+d=0$

  $d = \frac{|ax_1+by_1+cz_1+d|}{\sqrt{a^2+b^2+c^2}}$

---

Margin

• Distance from example x to the seperator is

  $r = \frac{w^Tx+b}{||w||}$

• margin이 가장 큰 hyperplane 선택

• 가장 가까운 hyperplane ⇒ support vector

• separator의 Margin ρ는 classes 사이의 separation의 width 값

---

Maximum Margin Classification

• Margin을 최대화하는 것은 직관에 따라 좋으며, 아마 거의 정확한(PAC, probably approximately correct) 이론

• 오직 support vector만 중요하며 다른 training examples는 무시해도 됨
  ⇒ support vector 2개만 남겨놓고 나머지는 버림

---

💡 Linear separable 하지 못한 예시는?

⇒ 대표적인 예 : XOR 문제

---

Linear SVMs Mathematically

• 모든 data의 거리(functional margin)가 적어도 1이라고 가정
• 적어도 하나의 data가 1과 같다고 가정

• 제약 조건 (training set {($x_i, y_i$)})

  $w^Tx+b≥ 1$     if $y_i = 1$
  $w^Tx+b≤ -1$   if $y_i = -1$

• 주어진 data를 학습하는 것은 w를 찾는 것과 같음 ❗
  ⇒ margin이 가장 큰 w를 찾아야 함
  단, 제약 조건을 만족해야 함

• Margin ρ

  $ρ = \frac{2}{||w||}$

---

💡 최적화 문제
최적화 문제는 보통 최소화하는 문제이지만 우리는 margin을 최대화하는 게 목적임
⇒ 원래 margin에 역수를 취해서, $\frac{||w||}{2}$가 최소가 되도록 하는 ||w||를 찾기
(단, 제약조건을 만족하면서)

• margin "$ρ = \frac{2}{||w||}$" 최대화 = "$Φ(w) = \frac{1}{2}w^Tw$"를 최소화

• 제약조건 $y_i(w^Tx + b) ≥ 1$
  ⇒ 앞선 2개의 제약조건을 하나의 수식으로 표현함

---

• $\frac{1}{2}w^Tw$는 Quadratic function (2차 함수)
  $y_i(w^Tx + b) ≥ 1$는 Linear (선형)

📌 Quadratic programming

• 목적함수가 이차 함수이며, 제약조건이 선형일 때 최적화하는 문제
• Lagrange multiplier(라그랑주 승수법)을 사용하여 해결할 수 있음

---

Constrained Optimization

📌 Equality constraints - Lagrange multiplier

• $f(x_1, x_2, ..., x_d)$에 대한 제약조건 $g_i(x) = 0$, $i = 1, 2, ..., p$
  ⇒ 제약조건이 여러 개(p개)일 수도 있음!

• 라그랑주 승수법

1. Lagrangian 정의

   $L(x, \lambda) = f(x) + \sum_{i=1}^{p}\lambda_ig_i(x)$

⇒ $\lambda_i$는 dummy variable(가변수)로 Lagrange multiplier
⇒ 모든 constraint에 대해서 $\lambda$ 를 곱하고 더하며, constraint가 n개 있으면 $\lambda$도 n개 있음!

2. 미분 수행

   $\frac{∂L}{∂x_i} = 0$, $∀i = 1, 2, ..., d$
   $\frac{∂L}{∂x_i} = 0$, $∀i = 1, 2, ..., p$

⇒ d : x 개수
⇒ p : constraint 개수

---

📝 Example

• $f(x,y) = x +2y$를 최소화

• constraint : $x^2+y^2-4=0$

---

1. Lagrangian 정의

   $L(x, y, \lambda) = x + 2y + \lambda(x^2+y^2-4)$

2. 미분 수행

   $\frac{∂L}{∂x} = 1 + 2\lambda x = 0$
   $\frac{∂L}{∂y} = 1 + 2\lambda y = 0$
   $\frac{∂L}{∂\lambda} = x^2+y^2 - 4 = 0$

3. 결과
   

---

📌 Inequality constraints - KKT

• $f(x_1, x_2, ..., x_d)$에 대한 제약조건 $h_i(x) ≤ 0$, $i = 1, 2, ..., q$

• Lagrangian

  $L = f(x) + \sum_{i=1}^{1}\lambda_ih_i(x)$

• 다음과 같은 제약조건을 만족해야함 (Karush-Kuhn-Tucker 조건 (KKT))

  $\frac{∂L}{∂x_i} = 0$, $∀i = 1, 2, ..., d$
  $h_i(x) ≤ 0$, $∀i = 1, 2, ..., q$
  $\lambda_i ≥ 0$, $∀i = 1, 2, ..., q$
  $\lambda_ih_i(x) = 0$, $∀i = 1, 2, ..., q$

• KKT 조건을 직접 푸는 건 어려움

---

📝 Example

• $f(x,y) =(x-1)^2+(y-3)^2$ 를 최소화

• constraint : $x+y≤2$, and $y≥x$
  ⇒ $x+y-2≤0, x-y≤0$

---

1. Lagrangian 정의

   $L = (x-1)^2+(y-3)^2+\lambda_1(x+y-2)+\lambda_2(x-y)$

2. KKT 제약조건

   $\frac{∂L}{∂x} = 2(x-1)+\lambda_1+\lambda_2 = 0$
   $\frac{∂L}{∂y} = 2(y-3)+\lambda_1-\lambda_2 = 0$
   $\lambda_1(x+y-2) = 0$
   $\lambda_2(x-y)=0$
   $\lambda_1≥0, \lambda_2≥0, x+y≤2, y≥x$

---

💡 Case 1: $\lambda_1=0, \lambda_2=0$

$2(x-1)=0$
$2(y-3)=0$

• x = 1, y= 3이므로 제약조건 $x+y≤2$ 만족 X

---

💡 Case 2: $\lambda_1=0, \lambda_2≠0$

$x-y=0$
$2(x-1)+\lambda_2=0$
$2(y-3)-\lambda_2 =0$

• x = 2, y = 2, λ_2 = -2이므로 제약조건 $\lambda_2≥0, x+y≤2$ 만족 X

---

💡 Case 3: $\lambda_1≠0, \lambda_2=0$

$x+y-2=0$
$2(x-1)+\lambda_1=0$
$-2(x+1)+\lambda_1 =0$

• x = 0, y = 2, λ_1 = 2이므로 제약조건 만족 ❗

---

💡 Case 4: $\lambda_1≠0, \lambda_2≠0$

$x+y-2=0$
$x-y=0$
$2(x-1)+\lambda_1+\lambda_2=0$
$2(y-3)+\lambda_1-\lambda_2 =0$

• x = 1, y = 1, λ_1 = 2, λ_2 = -2이므로 제약조건 만족 X

---

• 그러므로 정답은 x = 0, y = 2

---

Cont'd

💡 그럼 이제 우리한테 주어진 문제를 풀어보자!

1. Lagrangian 정의
   

2. Karush-Kuhn-Tucker (KKT) conditions
   

• dual problem
  

---

• $w = \sum\lambda_iy_ix_i$, $b = y_k-w^Tx_k$

• λ의 대부분이 0 값을 가지며, λ가 0이 아닌 데이터들이 support vector가 됨!

• 새로운 data $f(x)=\sum\lambda_iy_i{x_i}^Tx+b$

• ${x_i}^Tx_j$ 중요 ❗