[ML] Lec 2. Supervised Learning

Supervised Class Learning

Supervised Learning은 주어진 sample data로부터 특정 class를 학습하는것. 예시로 두 parameter에 대한 학습일때 특정 class를 하나의 사각형으로 생각할 수 있다.

Hypothesis Class($H$)

$h(x) = 1$ if h classifies x as positivie
$h(x) = 0$ if h classifies x as negative
Error of $h \in H$ on $X$:
$E(h|X)=\sum1(h(x^t)\ne r^t)$

Version Space

$S$ : most specific hypothesis, 가장 안전한 가정
$G$ : most general hypothesis, 가장 관대한 가정
$S$와 $G$ 사이의 모든 $h \in H$ 는 consistent하고 version space를 만들어낸다.

Margin

$h$의 $S$와 $G$ 사이에서의 간격. margin이 가장 큰 hypothesis를 선택하는 것이 좋다.

VC(Vapnik-Chervonenkis) Dimension

N개의 point를 labeling하는 경우의 수는 $2^N$이다.
$h \in H$가 모든 point에 대해 consistent하면 $H$가 $N$을 shatter(나눈다)고 할 수 있다.

VC($H$)=$N$

PAC learning

최소 $1-\delta$ 의 확률로 최대 $\epsilon$ 의 오류를 가질 조건은 몇(N)개의 training example이 필요한가? 에 대한 것.

1. 상하좌우로 4개의 strip이 있을떄
2. 하나의 strip에서 오류가 생길 확률은 $1-\epsilon /4$ 이다.
3. N개의 instance가 하나의 strip에서 오류가 생길 확률은 $(1-\epsilon /4)^N$ 이다.
4. N개의 instance가 4개중 하나의 strip이라도 놓칠 확률은 $4(1-\epsilon /4)^N$ 이다.

   $4(1-\epsilon /4)^N \le \delta$
   $(1-x)\le e^{-x}$
   $4e^{- \epsilon {N/4}} \le \delta$
   $N\ge (4/\epsilon) log(4/\delta)$

Noise and Model Complexity

항상 간단한 model을 추구해라(occam’s razor)

• 사용하기 쉽고
• 학습시키기 쉽고
• 해석하기 쉽고
• 일반화가 잘되기 때문

여러개의 class가 존재할 경우
dataset $X = {x^t,r^t}^N_{t=1}$ where $r^t$ is label for $x^t$
위 그래프를 보면 class에 속하는 $H$가 존재하고 그 외의 공간에서는 reject된다.

Regression

dataset $X = {x^t,r^t}^N_{t=1}$ where $r^t \in R$ and $r^t=f(x^t)+\epsilon$
이때 추정한 함수(estimator)를 $g(x)$라 한다.
estimator의 오차 $E(g|X) = \frac{1}{N} \sum_{t=1}^N[r^t-g(x^t)]^2$ 이며 $g(x)$를 $w_1x + w_0$로 가정(inductive bias)하면 오차는 $E(w_1,w_0|X) = \frac{1}{N} \sum_{t=1}^N[r^t-(w_1x^t+w_0)]^2$ 이다.

model selection & generalization

아는게 없기 때문에 $H$에 대한 추정이 필요하다. 이를 inductive bias라 한다.

• generalization: 학습된 모델이 새로운 데이터에 얼마나 잘 수행할 것인가에 대한 것.
• overfitting: $H$가 class $C$나 function $f$보다 복잡한 경우
• underfitting: $H$가 class $C$나 function $f$보다 간단한 경우

Trade-off

• $H$의 복잡도, $c(H)$
• training set의 크기, $N$
• 일반화 오류, $E$ 이 세 요소간에 tradeoff가 존재하는데

  $N$이 커질수록, $E$는 감소한다 $c(H)$가 너무 작거나 너무 크면 $E$가 크다

Cross-Validation

일반화 오류(generalization error)를 줄이기 위해 dataset을 training, test, validation set으로 나누어 사용하는 방식

What is learning?

1. Model $g(x|\theta)$
2. Loss function
   $E(\theta|X) = \sum_tL(r^t,g(x^t|\theta))$
3. Optimization
   $\theta^* = arg \min_\theta E(\theta|X)$