Non-uniform learnability

이번 목차는 다음과 같습니다.

1. Non-uniform learnability

2. Strutural risk minimization

1. Non-uniform learnability

Definition 1 (Non-uniformly learnable, [1])
A hypothesis class \( \mathcal{H} \) is non-uniformly learnable if there exist a learning algorithm, \(A \), and a function \( m^{\text{NUL}}_{\mathcal{H}} : (0,1)^2 \times\mathcal{H} \to\mathcal{N} \) such that for every \( \epsilon ,\delta \in (0,1) \), and for every \( h \in \mathcal{H} \), for every distribution \( \mathcal{D} \), with probability at least \( 1- \delta \) , over the choice of \( S \sim \mathcal{D}^m \) we have
\begin{align*}
 L_{\mathcal{D}} ( A(S)) \leq L_{\mathcal{D}} (h) + \epsilon .
\end{align*}

 

Theorem A hypothesis class $\mathcal{H}$ of binary classifiers is non-uniformly learnable if and only if it is a countable union of agnostic PAC learnable hypothesis classes.

Proof. $\mathcal{H}$가 non-uniform하면 agnostic PAC learnable hypothesis class로 표현될 수 있다는 것을 먼저 보이겠다. 우선 다음이 성립하는 것을 알 수 있다:

$$\mathcal{H}=\cup_{n\in\mathbb{N}}\{h\in\mathcal{H}:m^{\text{NUL}}_{\mathcal{H}}(1/8,1/7,h)\leq n\}$$

$\mathcal{H}_n$이 agnostic PAC learnable하지 않다고 가정하자. 즉 $\mathcal{H}_n$의 VC dimension이 infinite하므로 $2m$ 사이즈의 set $C$를 shatter 할 수 있다. 따라서 no free lunch theorem에 의해 어떤 learner $A$에 대해서도 $L_{D^{2m}}(A(S))>1/8$인 $S$가 존재한다. 하지만 non-uniform learnability에 의해, $L_{D^{2m}}(A(S))<L_{D^{2m}}(h^{\prime})+1/8$인 learner $A$가 존재하므로 이는 모순이다.

2. Strutural risk minimization

먼저 몇가지 정의를 define한다:

$$\epsilon_n(m,\delta)=\min\{\epsilon\in (0,1):m^{\text{UC}}_{\mathcal{H}_n}(\epsilon,\delta)\leq m\}$$

이는 sample 갯수와 confindence level이 주어졌을 때, uniform convergence property가 성립할 수 있는 lowest error를 의미한다.

SRM의 목표는 다음과 같다:

Theroem. Let $\mathcal{H}=\cup_{n\in\mathbb{N}}\mathcal{H}_n$ and $\mathcal{H}_n$ satisfies uniform convergence property. For every $\delta \in (0,1)$, and distribution $\mathcal{D}$, with probabilty of at least $1-\delta$ over the choice of $S\sim \mathcal{D}^m$, the following holds for every $n\in\mathbb{N}$ and $h\in\mathcal{H}_n$:

$$|L_{\mathcal{D}}(h)-L_S(h)|\leq\epsilon_n (m,w(n)\delta)$$

Proof

$$\mathbb{P}(\exists{h}\in\mathcal{H}_n:|L_{\mathcal{D}}(h)-L_S(h)| > \epsilon_n(m,w(n)\delta))\leq w(n)\delta$$.

따라서

$$\mathbb{P}(\exists{h}\in\mathcal{H}:|L_{\mathcal{D}}(h)-L_S(h)| > \epsilon_n(m,w(n)\delta))\leq \sum_{n\in\mathbb{N}} \mathbb{P}(\exists{h}\in\mathcal{H}_n:|L_{\mathcal{D}}(h)-L_S(h)| \epsilon_n(m,w(n)\delta))\leq \delta$$

Theorem 

$$m^{\text{NUL}}_{\mathcal{H}}(\epsilon,\delta,h)\leq m^{\text{UC}}_{\mathcal{H}_n(h)}\left(\frac{\epsilon}{2},w(n)\delta \right)$$

Proof

With probability at least $1-\delta$ we have

$$L_{\mathcal{D}}(A(S))\leq L_S(h)+\epsilon_{n(h)}(m,w(n(h))\delta)$$

References

[1] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.