공부를 하다보니 Rademacher complexity 라는 용어가 나왔다. 평소같으면 그냥 지나쳐도 되지만 논문에서 핵심 내용이었기 때문에 한번 쓱 조사해봤다. 다행히도 Rademacher complexity에 대해 잘 정의한 책이 있어 이해하는데 도움이 되었다. 개꿀딱이었다.
Empirical Rademacher complexity
Rademacher complexity에는 Rademacher complexity이 있고 Empirical Rademacher complexity이 있습니다. Empirical Rademacher complexity를 정의한 후에 Rademacher complexity 정의하오니 Empirical Rademacher complexity에 대해 알아봅시다. 어떤 space $\mathcal{Z}$이 있습니다. 그리고 $\mathcal{G} = \left\{ g | g : \mathcal{Z} \to [a,b] \right\}$이 있습니다. $\mathcal{Z}$에서 sampling된 $S=\left\{z_1,z_2,…,z_m\right\}$이 있습니다. $\sigma_1,…,\sigma_m$는 1 또는 -1 값을 갖는 i.i.d random variable 이라고 할 때 Empirical Rademacher complexity을 아래와 같이 정의합니다.
$$\hat{\mathcal{R}}_S(\mathcal{G}) = E_{\sigma} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m \sigma_i g(z_i) \right]$$
expectation 이 $\sigma_1,\sigma_2,..,\sigma_m$에만 걸려있다는 의미로 $E_{\sigma}$를 사용하였다.
정의자체는 어려운 정의가 아니다. 근데 의미는 잘 모르겠다. Empirical Rademacher complexity 를 이용해 함수의 표현력을 측정한다는데 무슨의미인지는 아직도 모르겠음.
출처
Mohri et al. “Foundations of Machine Learning “