학습이론 - Hoeffding's inequality

보통 확률론에서, Hoeffing's inequality는 upper bound를 제공하고, 이는 독립적인 랜덤 변수들의 합이 랜덤 변수들의 기대값에서부터 일정량이상 벗어날 확률을 구하는 것이다. 여기서 랜덤 변수들에 대한 제약조건이 하나 붙는데, 이는 일반 independent random variable이 아닌, bounded independent random variables이므로, 각 변수들은 $$a_i \leq X_i \leq b_i$$로 특정 범위 내에서 랜덤 변수들임을 의미한다.

 

가정

---

$$X_1,X_2,...X_n$$ 은 독립적인 랜덤 변수들이고 $$(a_i \leq X_i \leq b_i)$$를 만족한다. 또한 범위

$$(a_i \leq X_i \leq b_i)$$에 존재하는 모든 X들은 convex하다.

$$S_n = X_1+X_2+...X_n$$로 가정한다.

위의 가정을 가지고, 아래 Hoeffing's inequality를 표기한다면 다음과 같다.Hoeffing's inequality

---

$$P(S_n - E[S_n] \geq t) \leq exp \left(-\frac{2t^2}{\sum_{i=1}^{n}(b_i-a_i)^2} \right)$$

여기서 (s,t>0)임을 유의하자.

exponential의 내부를 최소화시키는 값 s로 생성된 bound는 가장 좋은 값이다. 이는 2차함수의 convex한 점을 찾아야하는 것이므로, $$\left(-st+ \frac{1}{8}s^2\sum_{i=1}^{n}(b_i-a_i)^2\right)$$를 2차함수로 변형 후 한다. $$ a = \sum_{i=1}^{n}(b_i-a_i)^2 , b = 8t $$ 와 같은 가정을 두고, 2차함수를 생성한다.

$$a(s^2 -\frac{bs}{a}) =a(s^2 - \frac{bs}{a}+ \frac{b^2}{4a^2} -\frac{b^2}{4a^2}) \
=a(s- \frac{b}{2a})^2- \frac{b^2}{4a}$$

수업에서는 딥러닝 모델의 학습과정과 연관시키기 위해서 한가지 가정이 더 추가되는데, $\hat{e}r_z(h) =P{(x,y) \in \mathbb{Z} : h(x) \neq y}$ 이는 x가 입력으로 들어왔고, h가 딥러닝 모델일 때, 정답 y를 예측을 실패할 때의 수치를 계산하는 것이다. Sample error라고 부르며 다음과 같이 정의한다.이는 큰수의 법칙에 의해 다음을 만족한다. (큰수의 법칙에 대해서는 추후 다른 포스트에서 다룰 예정임.)
$$\hat{e}r_z(h) \rightarrow^{P}_{m->\infty} er_p(h)$$

이는 sample dimension의 크기를 무한대로 확장시켰을때, 가장 이상적인 Sample error에 수렴하게 된다는 것을 의미한다. (h는 hypothesis로 딥러닝 모델이 추론한 결과를 말하는 것임)

해서 위의 Hoeffing's inequality의 확률 값에 대해 $\hat{e}r_z(h)$를 대입한다면, 다음과 같이 표기할 수 있다.
$$P^m{\hat{e}r_z(h) - er_p(h)|\geq \gamma } \leq 2exp(-2\gamma^2m)$$
여기서 $\gamma$는 우리가 이상적인 샘플의 추론의 값과 우리가 예측하는 모델의 추론의 범위를 줄이고자하는 확률적인 스레셔홀드역할을 한다고 볼수 있고 m의 경우는 샘플의 크기를 의미한다. 즉, 많은 샘플을 가질 수록 $\gamma$의 값을 더 작게 잡을 수 있는 것이다.

Hoeffding's inequliaty의 정리

---

$$E[e^{\lambda(X-E(X))}] \leq exp\left(\frac{1}{8}\lambda^2(b-a)^2 \right)$$ 을 만족하는 Hoeffding ineuqality가 있다고 가정하자.

$$a \leq X \leq b$$를 만족할 때, 다음을 만족한다. $$a \leq E(X) \leq b \rightarrow a- E(X) \leq X- E(X) \leq b- E(X) $$

이는 만약 E(X)가 a든 b든 $E(e^0) = 1$로 나올 것이다. 이 두가지의 경우에서 Hoeffding 정리가 참인것을 확인할 수 있다.

위의 성질을 이용하여 각점들의 차이에 대한 x축과 y축의 비율을 다음과 같이 표현할 수 있다.

$$\frac{(b-x)e^{\lambda(b-E(X))}+(X-a)e^{\lambda(b-E(X))}}{x-a+b-x}$$

이는 다음과 같이 전개할 수 있다.

마지막에 1/8이 upper bound에 걸리게 되는데 이는 tailer expantion 으로 구해질수 있다.

Tailer expantion for 1/8

---

위의 전개식에서 exp를 떼는 작업을 하고 이를 g라는 하나의 함수로 두자.

$$
e^{-\theta v}(1-\theta+\theta e^{v}) \leq e^{\frac{1}{8}v^2} \
e^{-\theta v +log(1-\theta+\theta e^{v})} \leq e^{\frac{1}{8}v^2} \
g(v) = -\theta v +log(1-\theta+\theta e^{v}) \leq \frac{1}{8}v^2
$$

추출된 g에 대해 tailer expantion을 적용g한다.

$$g(v) = g(0)+g'(0)(v-0)+\frac{1}{2}g''(0)(v-0)^2+ \frac{1}{n!}g^{'n}(v-o)^n$$

인데, w라는 값을 하나 더 추가해서 뒤에꺼 퉁친다고 하고, 2차까지만 적용한다. $(0<w<v)$

$$g(v) = g(0)+g'(0)(v-0)+\frac{1}{2}g''(w)(v-0)^2$$

각 값에 대한 것을 정리하면

$$
g(0) = 0 \
g'(0)=0 \
g'(v)=-\theta + \frac{\theta e^v}{1-\theta+\theta e ^v}
$$
이 된다.

이를 위의 식에 적용한다면, w빼고 전부 소거되므로

$$g(v) = \frac{1}{2} g''(w)v^2$$

여기서 $$g'(v)=-\theta + \frac{\theta e^v}{1-\theta+\theta e^v}$$를 이용하여 $$g''(v)$$를 구한다면,
$$g''(v) = \frac{\theta e^v(1-\theta)}{(1-\theta+\theta e^v)^2}$$
이 된다.

이는
$$
\frac{\theta e^v(1-\theta)}{(1-\theta+\theta e^v)^2} =\frac{\theta e^v}{(1-\theta+\theta e^v)}\frac{(1-\theta)}{(1-\theta+\theta e^v)}
$$

$$\therefore \frac{1}{4} \geq p(1-p) $$
로 정리된다 여기서
*1/4보다 작은 이유는 p(1-p)의 값이 $$p-p^2$$가 되는데, 이식은 2차함수로 concave하다는 점이 있고 이 concave한 값의 max값이 1/4이기 때문이다.

$$-(p-\frac{1}{2})^2 +\frac{1}{4} \therefore p= \frac{1}{2}$$

이 max 값인 1/4이 tailer expantion의 g''(w)에 들어가서 1/8이 되는 것이고 0과 v사이에 있는 g''(w)는 1/4보다 적다는 것이 증명된다.