#1 커널기반 학습 이론적 배경 (Shatter, VC demention, 구조적 위험 최소화 접근법)

# Support Vector Machine

# Support Vector Regression

# Linear

# Hard Margine

---

Shatter 

위의 그림은 2차원 공간에서 n=3이고 파란색이 Positive(+1), 흰색이 Negative(-1) 라고 할 때, 선이 분류 경계면(함수 F)이고 3개의 Point는 어떤 조합의 Binary Classification이든 생성될 수 있다.

즉, 함수 F는 n개의 Point를 Shatter할 수 있다 -> 함수 F에 의해 n개의 Point는 임의의 +1 또는 -1을 Target Value로 하는 분류 경계면의 생성이 가능하다.

 

선형 분류기는 d차원에서 (d+2)개의 점을 shatter하는 것이 가능한가? NO

n차원에서 d개의 점을 shatter할 수 있고, d+1개의 점도 shatter할 수 있지만 d+2개의 점을 shatter하는 것은 불가능하다.

ec) 2차원에서 3개의 점을 shatter할 수 있지만 4개의 점을 shatter하지 못한다.

 

 

원점을 지나는 원형분류기(원 안에 있으면 파란색, 밖에 있으면 빨간색으로 분류)는 2차원에서 2개의 점도 Shatter할 수 없음

 

 

"원점을 지나는" 조건을 삭제할 경우 원 형태의 분류 경계면은 2차원에서 3개의 점을 shatter할 수 있다.

위의 분류 경계면은 2차원에서 4개의 점을 Shatter할 수 있는가? NO

분류 경계면을 원이 아닌 타원으로 바꾸면 2차원에서 4개의 점을 Shatter할 수 있는가? Yes

 

---

VC dimention

어떤 함수(함수 or 분류기)의 Capacity를 측정하는 지표

함수 H에 의해 최대로 shattered 될 수 있는 Points의 수 = VC dimention

 

 - 위의 예시에서 선형 분류기의 VC dimention은 2차원에서 3

- 원점을 중심으로 하는 원 분류기의 VC dimention은 2차원에서 1

- 원점 위치의 제약이 없는 원 분류기의 VC dimention은 2차원에서 3

 

---

구조적 위험 최소화 접근법 (Structural Risk Minimization)

 

- 예측 모델의 정확도가 높다고 해서 반드시 좋은 것은 아님

- 동일한 정확도라면 상대적으로 복잡도가 낮은 모델이 선호되어야 함

 

 

- 인공신경망, 의사결정나무, 선형/로지스틱 회귀분석은 경험적 위험만을 최소화하는 것을 목적으로 함

 

      * 딥러닝의 가중치에 L2-norm 또는 L1-norm 형태의 페널티를 부여하는 것은 모델의 구조적 복잡도를 낮추기 위한 일환

 

n이 커지면 구조적 위험 낮아짐

h가 커지면 구조적 위험 높아짐

 

 

모델의 복잡도가 높으면 Trainning data에 대한 empirical error는 낮아지지만,  Test data가 Over fitting 될 가능성이 높아짐

 

하지만 Deep Learning에서는 꼭 그렇지는 않다.