有限仮説集合がPAC学習可能であることの証明

hiden-cubist.hateblo.jp

以前の記事で、有限仮説集合と実現可能性を仮定した場合、十分に訓練データが多ければ経験損失最小化によって近似的に期待損失を小さくできることを示しました。今回はこれを一般化したPAC学習について述べた後、実現可能性の仮定を外すことを考えます。

PAC学習可能
一様収束
Hoeffdingの不等式
有限仮説集合はPAC学習可能
まとめ
参考文献

PAC学習可能

仮説集合 $\mathcal{H}$ がPAC学習可能であるとは、以下の条件を満たす関数 $m_\mathcal{H}:(0,1)^2 \to \mathbb{N}$ と学習アルゴリズム $A$ が存在することを言います。任意の $\epsilon,\delta \in (0,1)$ と分布 $\mathcal{D}$ に対して、 $m \geq m_\mathcal{H}(\epsilon, \delta)$ の $\mathcal{D}$ から生成された独立なサンプルを取れば、アルゴリズム $A$ は少なくとも確率 $1-\delta$ で、

$L_\mathcal{D}(h) \leq \min_{h' \in \mathcal{H}} L_\mathcal{D}(h')+\epsilon\\ where \quad L_\mathcal{D}(h)=\mathbb{E}_{z \sim D}[l(h,z)]\\$

を満たす仮説 $h\in\mathcal{H}$ を返す。

すなわち、十分に多くのデータを取れば任意の確率、精度で期待損失が最小値に近い仮説を得ることができるということです。以前の記事と異なるのは、実現可能性を仮定していないため不等式の右辺の第一項が0とは限らないこと、また損失関数が

$l_{0-1}(h, (x,y))=\mathbb{1}[h(x)\neq y]\\ l_{sq}(h, (x,y))=(h(x)-y)^2\\$

などに一般化されていることです。この定義を用いると、以前の記事の結論から有限仮説集合は実現可能性の仮定のもとでPAC学習可能であると言えます。しかし、実現可能性を仮定しなくても実はPAC学習可能であることが示せます。以降の節ではいくつか準備をした後にこれを証明していきましょう。

一様収束

仮説集合 $\mathcal{H}$ が一様収束であるとは、以下の条件を満たす関数 $m_\mathcal{H}^{UC}:(0,1)^2 \to \mathbb{N}$ が存在することを言います。任意の $\epsilon,\delta \in (0,1)$ と分布 $\mathcal{D}$ に対して、 $m \geq m_\mathcal{H}^{UC}(\epsilon, \delta)$ の $\mathcal{D}$ から生成された独立なサンプルを取れば、少なくとも確率 $1-\delta$ で、

$\forall h \in \mathcal{H}, \quad |L_S(h)-L_{\mathcal{D}}(h)| \leq \epsilon\\$

である。

この式にはPAC学習の定義に出てきた期待損失から求まる $\min_{h' \in \mathcal{H}} L_\mathcal{D}(h')$ が出てこないため、証明で役立ちます。

Hoeffdingの不等式

PAC学習の証明に必要なHoeffdingの不等式を述べておきます。 $\theta_1,\dots,\theta_m$ を独立な確率変数、 $\mathbb{E}[\theta_i]=\mu$ 、 $\mathbb{P}[a \leq \theta_i \leq b]=1$ のとき、

$\displaystyle \mathbb{P}[|\frac{1}{m}\sum_{i=1}^{m}\theta_i - \mu| > \epsilon] \\ \leq 2 \exp(-2m\epsilon^2/(b-a)^2)\\$

となる。

この証明については省略します。（今後追記するかもしれません）

有限仮説集合はPAC学習可能

いよいよここからが本題です。有限仮説集合がPAC学習可能であることを示すために、

$\mathcal{D}^m (\{S: L_\mathcal{D}(h_S) - L_\mathcal{D}(h^*) > \epsilon\})\\ where \quad h^* = \arg\min_{h' \in \mathcal{H}} L_\mathcal{D}(h')\\$

の上限を考えます。まず、一様収束

$\displaystyle\forall h \in \mathcal{H}, \quad |L_S(h)-L_{\mathcal{D}}(h)| \leq \frac{\epsilon}{2}\\$

ならば、

$\displaystyle\forall h \in \mathcal{H}, \\ L_{\mathcal{D}}(h_S) \leq L_{S}(h_S)+\frac{\epsilon}{2}\\ \displaystyle\leq L_{S}(h)+\frac{\epsilon}{2} \leq L_{D}(h)+\frac{\epsilon}{2}+\frac{\epsilon}{2}\\ = L_{D}(h)+\epsilon\\ \therefore \quad L_\mathcal{D}(h_S) - L_\mathcal{D}(h^*) \leq \epsilon\\$

であることから、

$\mathcal{D}^m (\{S: L_\mathcal{D}(h_S) - L_\mathcal{D}(h^*) > \epsilon\})\\ \displaystyle\leq \mathcal{D}^m (\{S: \exists h \in \mathcal{H}, |L_S(h)-L_{\mathcal{D}}(h)| > \frac{\epsilon}{2}\})\\ \displaystyle \leq \sum_{h \in \mathcal{H}} \mathcal{D}^m (\{S: \in \mathcal{H}, |L_S(h)-L_{\mathcal{D}}(h)| > \frac{\epsilon}{2}\})\\ \displaystyle \leq \sum_{h \in \mathcal{H}} 2 \exp(-2m{(\frac{\epsilon}{2})}^2) \quad \cdots(1)\\ \displaystyle \leq 2 |\mathcal{H}| \exp(-2m{(\frac{\epsilon}{2})}^2)\\$