Lecture 9 - Approx/Estimation Error & ERM | Stanford CS229: Machine Learning (Autumn 2018)
주요내용
- Setup/ Assumptions
- Bias Variance Trade-off
- Approx/Estimation Error
- ERM: Empirical Risk Minimizer
- Uniform Convergence
- VC Dimensions
Setup/ Assumptions
모델을 개발하는데 기본적인 가정사항에 대해서 알아봅시다.
1. Data Distribution D. (x, y) ~ D (Train, Test)
데이터는 특정 분포(D)를 가지고 훈련 데이터와 테스트 데이터는 동일한 분포 (D)로 나온다는 가정입니다.
2. Independent Samples
데이터들은 특정분포를 갖지만 어떤 값이 들어올지는 모르는 랜덤 변수이고 이를 학습 알고리즘(Estimator)에서 받아서 학습된 추정치인 h^ 또는 θ^을 만들어 냅니다.
Bias Variance
Data view에서 바라본 Bias / Variance는 지난 시간에 봤던 것과 같이 아래 그림과 같습니다. 3개의 모델이 있다고 가정한 것이고 Underfit, Just Right, Overfit 된 모델을 선으로 그린 그림입니다.
파라메타 관점에서 바라본 Bias/Variance는 아래 그림과 같습니다. 왼쪽 그래프 A, C는 낮은 Variance를 가지고 있으며(점들이 모여있습니다.), 오른쪽의 B, D는 높은 Variance를 가지고 있습니다(점들이 왼쪽보다 퍼져있습니다). 위의 A, B 그래프는 높은 Bias를 가지고 있으며(중앙의 별과 점들의 중앙이 멀리 있습니다.), 아래 C, D는 낮은 Bias를 가지고 있습니다(별과 점들의 중앙이 가까이 있습니다). 가운데 별은 정답(영역) 입니다. 그래프의 점들은 한번 훈련이 됬을때의 θ1, θ2의 값에 의해 그려진 것입니다.
훈련 데이터의 양이 많아지면 점들의 간격이 줄어듭니다. Variance 가 작아집니다.
다시 말하면 훈련 데이터 수(m)가 무한대로 많아 진다면 Variance[θ^]이 0에 가까워 집니다. 그리고 훈련 데이터가 많아지면 추정값인 θ^(세타헷)이 실제값인 θ*(세타스타)에 가까워 집니다. 모든 데이터를 가지고 훈련해서 θ^을 통해 추정하면 θ*와 같은 값이 됩니다. (이론적으로 그렇다는 것이고 실제로 모든 데이터를 훈련할 수 없는게 현실이고 그리고 가능하다고 해서 그말은 모델을 만들 필요가 없다는 의미 없습니다. 그래서 위에서 말한 것처럼 같은 값으로 가까워진다는 표현이 더 좋은 것 같습니다.)
Fighting Variance
그래서 Variance를 줄이는 방법에는 여러가지가 있습니다. 먼저 훈련 데이터수를 늘리는 것입니다. 두번째는 정규화(Regularization)를 하는 것입니다. 그래서 점들을 모이게 만드는 것입니다.
Approx/Estimation Error
가설공간에 제일 가능한 가설(g)과 제일 좋은 가설들의 집합(h*), 데이터로부터 학습된 가설/파라메타(h^) 을 표시하면 아래와 같습니다. 여러번 훈련해서 여러개의 h^이 나올 수 있고 이것을 묶은 것이 H(타원) 입니다. 그래서 학습된 파라메타(h^)와 정답(g: ground truth) 의 차이 인 에러가 발생하게됩니다. ℇ(h)는 Risk error / Generalization error(정규에러)라고 불립니다. 하나의 파라메타 샘플(s)에 대한 에러 ℇ^s(h) 는 Empirical Risk로 불립니다. 이 것은 아래와 같이 모든 h(xi)와 yi가 틀린 경우 확률을 평균한 것 입니다. 리우며 이것은 데이터 x 값이 주어졌을 때 의 에러를 말합니다.
ℇ(g) 는 Bayes Error 또는 제거가 불가능한 에러(Irreducible Error)라고 불립니다. 훈련데이터에서 다른 x 값에 같은 y 값을 갖는 경우가 그예입니다. Approximation Error, Estimation Error, Irreducible Error 등을 알수 있습니다.
가설 공간에 에러를 표시해 보면 아래와 같습니다.
Fighting Bias
바이어스를 줄이는 방법은 H를 크게 / 넓게 만드는 것입니다. 또는 아예 다른 알고리즘을 사용하는 것도 좋은 시도가 될 수 있겠습니다.
ERM: Empirical Risk Minimizer
ERM은 러닝 알고리즘 중 하나 입니다.
Uniform Convergence 균등 수렴
(1)번은 모집단의 h를 가지고 예측에러와 실제에러를 비교하는 방법이고, (2)번은 모델의 h^을 통해 발생한 에러와 모집단의 정답 h*을 이용했을때의 에러를 비교하는 것입니다. 위의 (1),(2) 번을 각각 비교하기 위해 다음 이미지에 있는 툴 1,2를 이용합니다.
두번째 툴은 Hoeffding's Idea 입니다.
이것을 그래프로 그려보면 아래와 같습니다. 하나의 셈플로 에러를 측정한 임피리컬 에러(파란색 점선)와 정규화된 에러(E(h)) ( 검정색 실선)을 볼 수 있고, hi라는 특정 샘플(hi)에서 두선의 에러 차이를 보면 아래와 같이 표시될 수 있습니다. 이러한 임피리컬 에러들을 정규화 에러선으로 변환시키는 방법중 하나가 Uniform Convergence 균등수렴 방법입니다.
균등수렴과 Hoeffding 방법을 이용하면 아래와 같이 전체 가설에 대해서 공식을 만들 수 있습니다.
이러한 공식을 사용하는 방법은 아래와 같이 2가지를 고정하고 다른 값을 찾는 방법입니다. 두 변수를 0보다 크다고 가정하고 m 사이즈를 구했네요.
위 그래프를 공식으로 표시해 보면 아래와 같습니다.(중간부터 아래쪽)
VC(Vapnic-Chervonenkis) Dimension
