No free lunch theorem

Universal algorithm이 있을까? Learning task란 sample $\{(\mathbf{x}_i,y_i ) \}_{i=1}^n$들을 generate하는 어떤 unkown distribution $\mathcal{D}$가 있을 때, $L_{\mathcal{D}}(h)$가 낮아지는 predictor $h$를 찾는 것이다. No free lunch theroem은 어떠한 learner에 대해서도 learnable하지 않은 distribution이 있다는 것을 보여준다.

Theroem 1. [No free lunch theorem, [1]]
Let \(A\) be any learning algorithm for the task of binary classification with respect to \(0-1\) loss over a domain \( \mathcal{X} \). Let the size of training set \( m \leq \frac{|\mathcal{X}|}{2} \). Then, there exists a distribution \( \mathcal{D}^m \) over \( \mathcal{X}^m \times \{0,1\} \) such that

1. There exists a function $f: \mathcal{X} \to\{0,1\} $ with $ L_{\mathcal{D}}(f) =0 $.
2. With probability of at least \(\frac{1}{7} \) over the choice of \( \mathcal{S} \sim \mathcal{D}^m \), we have \( L_{\mathcal{D}}(A( \mathcal{S} ))\geq\frac{1}{8} \).

Proof)

$ | \mathcal{C}|=2m$인 $\mathcal{X}$의 subset $C$를 생각한다. $m$개의 sample만 가지고는 $C$를 learn 할 수 없다는 것을 보일 것이다.

이 때 가능한 label의 갯수는 $2^{2m}$이다. 각각의 labeling function을 $f_1,f_2,\dots,f_{2^{2m}}$으로 정의한다. 그리고 $\mathcal{D}_i, 1 \leq i \leq 2^{2m}$을 $f_i$가 맞출 수 있는 정답을 uniform 분포로 만드는 distribution으로 정의한다.

$C$의 subset 중에서 가능한 $m$개의 training sample 갯수는 $(2m)^m$이고,$S_i =\{\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_m} \},\;1\leq i\leq (2m)^m$으로 정의한다. 또한 $S^j_i:=\{(\mathbf{x}_{i_1},f_j(\mathbf{x}_{i_1}),\dots, (\mathbf{x}_{i_m},f_j(\mathbf{x}_{i_m}))\}$.

따라서 $\mathcal{D}_i, 1 \leq i \leq 2^{2m}$에 의해 sample들이 만들어지면, $\{S^i_j\}_{j=1}^{(2m)^m} $ 중에 uniform한 분포로 sample들이 얻어진다. 따라서 $D_i$에 대한 expected true risk는 다음과 같이 구할 수 있다:

$$\mathbb{E}_{S\sim\mathcal{D}^m_i}[L_{\mathcal{D}_i}(A(S))]=\frac{1}{(2m)^m} \sum^{(2m)^m}_{j=1}L_{\mathcal{D}_i}(A(S^i_j))$$

max operator가 average operator보다 작다는 것을 활용하면 다음과 같은 부등식을 얻을 수 있다:

\begin{align*}
 \max_{i \in [2^m] } \mathbb{E}_{S\sim \mathcal{D}^m_i} \left[ L_{\mathcal{D}_i} (A(S)) \right] \geq & \frac{1}{2^m} \sum^{2^m}_{i=1} \frac{1}{(2m)^m} \sum^{(2m)^m}_{j=1} L_{\mathcal{D}_i} (A(S^i_j) ) \\
 \geq & \min_{j \in [(2m)^m] } \frac{1}{2^m} \sum^{2^m}_{i=1} L_{\mathcal{D}_i} ( A(S^i_j) ).
\end{align*}

즉, 우리는 나쁜 sample을 찾을 것이다. 이를 위해 $C\setminus S_j$를 고려한다. 즉, training시에 보지못한 나머지 sample들에 나쁜 sampled이 있는 것이다:

\begin{align*}
\frac{1}{T} \sum^T_{i=1} L_{\mathcal{D}_i} (A(S^i_j)) \geq & \frac{1}{2^{2m}} \sum^{2^{2m}}_{i=1}  \frac{1}{2| C\setminus S_j|} \sum_{x\in C\setminus S_j} \mathbf{1} \{ A(S^i_j) (x) \neq f_i (x) \}\\
\geq & \frac{1}{2} \min_{x\in C\setminus S_j} \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} \mathbf{1} \{ A(S^i_j) (x) \neq f_i (x) \}\\ =&\frac{1}{4}.
\end{align*}

Q.E.D.

따라서 prior knowledge가 없다면 , ERM predictor도 특정 learning task에 대해서 실패할 수 있다.

Example. $\mathcal{X}$가 infinite domain set이고 $\mathcal{H}$가 $\mathcal{X}\to\{0,1\}$인 모든 function들의 class라면 $\mathcal{H}$는 PAC learnable 하지 않다. 

Proof)  PAC-learnable하다고 가정하면, $\epsilon<1/8$ 그리고 $\delta <1/7$에 대해 sample $m$이 존재한다. 하지만 $2m<\infty$이므로, 1/7보다 큰 확률로 $L_{\mathcal{D}}(A(S))>1/8$인 distribution $\mathcal{D}$가 존재한다.

Q.E.D.

그렇다면 Hypothesis를 어떻게 정해야될까? Hypothesis를 너무 크게 잡으면 위의 예제에서 알 수 있듯이 PAC-learnable하지 않다.

$L_{\mathcal{D}}=\min_{h\in\mathcal{H}} L_{\mathcal{D}}(h)+L_{\mathcal{D}}(h_S) -\min_{h\in\mathcal{H}}L_{\mathcal{D}}(h)$

$\mathcal{H}$가 크면 Approximation error인 $\min_{h\in\mathcal{H}} L_{\mathcal{D}}(h)$가 줄어들지만 Estimation error인 $L_{\mathcal{D}}(h_S) -\min_{h\in\mathcal{H}}L_{\mathcal{D}}(h)$가 늘어날 것이다.

하지만 $\mathcal{X}$와 $\mathcal{H}$가 infinite한 경우에도 ERM rule이 PAC learnable 한 경우가 있다.

Example ( Threshold function in $\mathbb{R}$, [1] ) 

우선 Hypothesis class를 $\mathcal{H}:=\{ h_a : h_a(x)=\mathbf{1}[x\leq a], a\in \mathbb{R} \}$로 정의한다. Realizability assumption 아래 $L_{\mathcal{D}}(h_{a^*})=0$이라고 하고 $\mathbb{P}[x\in (a_0,a^*)]=\mathbb{P}[x\in (a^*,a_1)]=\epsilon$인 $a_0,a_1$을 생각한다. 

Training sample의 minimum과 maximum value가 각각 $b_0$와 $b_1$이라고 한다면 ERM rule에 의해 $b_S \in (b_0,b_1)$이 threshold로 선택된다. 이 때 $ L_{\mathcal{D}}(h_{b_S})\leq\epsilon$ 이기 위해서는 $(b_0,b_1) \subset (a_0,a_1)$이여야된다.

즉, $\mathbb{P}_{S\sim\mathcal{D}^m}(b_0<a_0 \wedge b_1 > a_1)<\delta$임을 보이면 된다. 

 

References

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