Learning guarantees for finite hypothesis sets

What is the task?

• ラベル付けされた標本 \(S\) を用いて、概念 \(c\) に関して汎化誤差が小さい仮説 \(h∈\mathcal{H}\) を選択すること

Definition 2.1 (Generalization error)

ターゲット概念 \(c\in \mathcal{C}\) とターゲット分布 \(\mathcal{D}\) が与えられたときの、仮説 \(h \in \mathcal{H}\) の汎化誤差は次のように定義される。ここで \(1_{\omega}\) はイベント \(\omega\) の指示関数。

\[ R(h) = Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] = \mathbb{E}_{x \sim \mathcal{D}}[1_{h(x) \neq c(x)}] \tag{2.1} \]

• この定義と他の関連する定義のために、関数 \(\mathcal{H}\) とターゲット概念 \(c\) は可測でなければならない (可測でない時というのはかなり病的な状況)

• 仮説の汎化誤差は、分布 \(\mathcal{D}\) とターゲット概念 \(c\) の両方が未知であるため、学習者が直接知ることはできない

• しかし、学習者はラベル付けされた標本 \(S\) 上で仮説の経験誤差を測定することができる

Definition 2.2 (Empirical error)

仮説\(h \in \mathcal{H}\)、ターゲット概念 \(c\in \mathcal{C}\) 、標本 \(S = (x1, ... , xm)\) が与えられると、仮説 \(h\) の経験誤差は以下で定義される。

\[ \hat{R_S}(h) = \frac{1}{m}\sum^{m}_{i = 1}1_{h(x) \neq c(x)} \tag{2.2} \]

• \(h \in \mathcal{H}\) の経験誤差は標本 \(S\) における \(h\) の平均誤差

• 汎化誤差は分布 \(D\) に基づくその期待誤差

• i.i.d.標本 \(S\) に基づく経験誤差の期待値は汎化誤差に等しい (経験誤差は汎化誤差の不偏推定量)

\[ \mathbb{E}_{S \sim \mathcal{D}^m}[\hat{R_S}(h)] = R(h) \tag{2.3} \]

proof

Definition 2.3 (PAC-learning)

• 学習アルゴリズム \(\mathcal{A}\) が存在する、つまり以下の2点が成り立っている時、概念クラス \(\mathcal{C}\) は PAC学習可能(PAC-learnable) である

  • 固定多項式に対するサンプル \(S\) のサンプルサイズ \(m = poly(1/\epsilon, 1/\delta)\) (多項式オーダーで増加)

  • 任意のターゲット概念 \(c \in \mathcal{C}\) , \(\epsilon > 0\) , \(\delta > 0\) およびすべての分布 \(\mathcal{D}\) について、

\[ Pr_{S \sim \mathcal{D}^m}[R(h_S) \leq \epsilon] \geq 1 - \delta \tag{2.4} \]

Remarks

• PAC フレームワークはdistribution-free モデル (分布の仮定なし)

• 誤差を定義するために使用される学習サンプルとテスト例は、同一の分布 \(\mathcal{D}\) に従う

• パラメータ \(\delta > 0\) は信頼度 \(1 - \delta\) を、 \(\epsilon > 0\) は精度 \(1 - \epsilon\) を求めるために使用

• 概念クラス \(\mathcal{C}\) はアルゴリズムにとって既知であるが、ターゲット概念 \(c \in \mathcal{C}\) は未知であることに注意

Theorem 2.5 (Learning bound — finite H, consistent case)

• \(\mathcal{H}\) を \(\mathcal{X}\) から \(\mathcal{Y}(\{0,1\})\) に写像する関数の有限集合とする

• \(\mathcal{A}\) は、任意のターゲット概念 \(c \in \mathcal{H}\) とi.i.d.標本 \(S\) に対して、
  一致する仮説 \(h_S\) (\(\hat{R}_S(h_S) = 0\)) を返すアルゴリズムとする

• 任意の \(\delta > 0\) に対して、少なくとも \(1-\delta\) の確率で

\[ R(h_S) \leq \frac{1}{m}(log|\mathcal{H}| + log \frac{1}{\delta}) \tag{2.9} \]

proof

Example 2.6 (Conjunction of Boolean literals)

Boolean : true or falseの型 (java?)
literals: 定数値

以下では、Boolean literalsを「ブール値」と訳す

• 最大n個のブール値 \(x_1, ... , x_n\) の論理積の概念クラス \(\mathcal{C}_n\) を学習することを考える

  • ブール値は、変数 \(x_i\) 、またはその否定 \(\bar{x}_i\) のいずれか (\(i ∈[n]\),つまり\(i = 1,_{\cdots},n\))

• 例1）n = 4

  • 論理積 \(x_1∧ \bar{x}_2∧ x_4\) があり、ここで \(\bar{x}_2\) はブール値 \(x_2\) の否定を表す

  • (1, 0, 0, 1) はこの概念の正の例

  • (1, 0, 0, 0) はこの概念の負の例

• 例2）n = 4

  • 正の例 (1, 0, 1, 0) は、ターゲット概念が定数値 \(\bar{x}_1\) と \(\bar{x}_3\) を含むことができず、
    定数値 \(x_2\) と \(x_4\) を含むことができないことを意味する

  • 対照的に、負の例 (例えば (1,0,0,0) ) はそのnビットのうちの
    どのビットが正しくないかがわからないため、情報量が少なくなる

• よって一致する仮説を見つけるための簡単なアルゴリズムは、正の例に基づいており、
  次のように構成されています。

  • 各正の例 \((b_1, ... , b_n)\) と \(i∈[n]\) について、
    \(b_i=1\) ならば、 \(x_i\) は概念クラスの可能性のある定数値とされ、
    \(b_i=0\) ならば、 \(x_i\) は除外される

  • 除外されていないすべての定数値の論理積は、ターゲット概念と一致する仮説となる

Example Figure2.4

• 以下の図2.4は、学習サンプルの例と、n = 6の場合の一致する仮説を示している

• 図2.4 (n = 6のとき)

  • 表の最初の6行は学習例

  • 最後の列 (7列目) に \(+\) または \(-\) のラベル

  • 最後の行 (7行目) は、すべての正の例 (7列目が \(+\) ) に対して、 \(i\) 列目の要素が全て0 (or 1) であれば、
    \(i∈[6]\) にそれぞれ0 (or 1) が入る

  • また、正の例において、0 と 1 の両方が \(i\) 番目の要素として現れる場合 (図中の赤枠) には、
    最後の行に “?” が入る

  • この学習サンプルについて、一致するアルゴリズムによって返される仮説は、 \(\bar{x}_1∧ x_2∧ x_5∧ x_6\)

Algorithm

• 各ブール値は正に含まれていても、否定されていても、含まれていなくてもよいので、
  \(|\mathcal{H}| =|\mathcal{C}n| = 3^n\) となる

• 一致する仮説の標本複雑度限界 (式2.8) に当てはめると、任意の \(\epsilon > 0\) および \(\delta > 0\) において、
  以下のような標本複雑度限界が得られる

\[ m \geq \frac{1}{\epsilon}\bigl( (log3)n \:+\: log\frac{1}{\delta} \bigr) \tag{2.10} \]

• したがって，最大n個のブール値の論理積のクラスはPAC-learnableである

  • (2.10) を満たすならば、仮説 \(h_S\) は任意の \(\epsilon,\delta > 0\) に対して、
    \(Pr_{S \sim D^m}[R(h_s) \leq \epsilon] \geq 1 - \delta\) を満たす。

  • さらにサンプルサイズ \(m\) のオーダーは多項式より遅い

• \(δ = 0.02、\epsilon = 0.1、n = 10\)の場合、境界は\(m \geq 149\)となる

  • 少なくとも149個の例のラベル付きサンプルでこの境界は、
    少なくとも98% (\(1-0.02\)) の信頼度で90% (\(1-0.1\)) の精度を保証

Corollary 2.10

Corollary: ある主張（典型的には定理）の系（けい、英: corollary）とは、その（既知の）主張から
「直ちに」証明される主張をいう (Wikipediaより引用)

• \(\epsilon>0\) とすると、任意の仮説 \(h : X → \{0, 1\}\) に対して，次の不等式が成立する

\[ Pr_{S \sim D^m}[\hat{R}_S(h)-R(h) \geq \epsilon] \leq exp(-2m\epsilon^2) \tag{2.14} \]

\[ Pr_{S \sim D^m}[\hat{R}_S(h)-R(h) \leq -\epsilon] \leq exp(-2m\epsilon^2) \tag{2.15} \]

• これらの不等式を組み合わせると

\[ Pr_{S \sim D^m}[|\hat{R}_S(h)-R(h)| \geq \epsilon] \leq 2exp(-2m\epsilon^2) \tag{2.16} \]

proof (Corollary 2.10)

• この結果は定理D.2からすぐに従う(?)

Corollary 2.11 (Generalization bound — single hypothesis)

系 2.11 (一般化限界　単一仮説)

• 仮説 \(h\) を\(X → {0, 1}\) とすると、任意の \(δ＞0\) に対して、以下の不等式が少なくとも \(1 - δ\) の確率で成り立つ

\[ R(h) \leq \hat{R}_S(h) \:+\: \sqrt{\frac{log2/\delta}{2m}} \tag{2.17} \]

proof (Corollary 2.11)

• 保科先生の板書 (2020/10/28 追記)

  

Example 2.12 (Tossing a coin)

• 偏ったコインを投げて、確率 \(p\) で表が出るとする

  • 我々の仮説 : 常に裏を推測するものとする

• 真の誤差確率は \(R(h) = p\) 、経験誤差確率は \(\hat{R}_S(h) = \hat{p}\)

  • ここで \(\hat{p}\) はi.i.dに抽出された学習サンプルに基づいた、表が出る経験的な確率

• このように，系2.11は，少なくとも \(1 - δ\) の確率で，以下を保証する

\[ |p-\hat{p}| \leq \sqrt{\frac{log2/\delta}{2m}} \tag{2.18} \]

• したがって、 \(δ＝0.02\) とし、大きさ \(m=500\) の標本を用いた場合、98％以上の確率で、
  次のような近似が保証される

\[ |p-\hat{p}| \leq \sqrt{\frac{log2(10)}{1000}} \approx 0.048 \tag{2.19} \]

problem

• 学習アルゴリズムが標本 \(S\) で学習するときに返される仮説 \(h_S\) の汎化誤差を抑える (バウンドする) ために、
  系2.11を容易に適用できるだろうか？

  → \(h_S\) は固定された仮説 (fixed hypothesis) ではなく、
  抽出された訓練標本 \(S\) に依存する確率変数であるため、系2.11を容易に適用できない

• 経験誤差の期待値が汎化誤差（式 (2.3)）である固定された (fixed) 仮説の場合とは異なり、
  汎化誤差 \(R(h_S)\) は確率変数であり、一般的に定数である期待値 \(\mathbb{E}[\hat{R}_S(h_S)]\) とは異なることにも注意

  →したがって、一致する場合の証明と同様に一様収束限界、すなわちすべての仮説 \(h∈\mathcal{H}\) に対して
  高い確率で保持される境界を導出する必要がある

Theorem 2.13 (Learning bound — finite H, inconsistent case)

• \(\mathcal{H}\) を有限仮説集合とする

• すると、任意の \(δ＞0\) について、少なくとも \(1 -δ\) の確率で、次の不等式が成立

\[ \forall h \in \mathcal{H},\; R(h) \leq \hat{R}_S(h) \: + \: \sqrt{\frac{log|\mathcal{H}|\: + \: log2/\delta}{2m}} \tag{2.20} \]

proof(Theorem 2.13)

Remarks

• このように、ある有限の仮説集合 \(\mathcal{H}\) について、高い確率で (whp : with high probability)

\[ \forall h \in \mathcal{H},\;R(h) \leq \hat{R}_S(h) \: + \: O\sqrt{\frac{log_2|\mathcal{H}|}{m}} \]

• この境界は経験誤差の低減と仮説集合の大きさの制御との間のトレードオフを求めることを示唆

  • 仮説集合を大きくする ( \(m\) を大きくする) と第2項でペナルティを受けるが、
    第1項である経験誤差の低減に役立つ可能性がある

  • 一方で経験誤差が同じである場合、より小さな仮説集合 (小さい \(m\) ) を使うことを示唆

→ Occam’s Razor principle (オッカムの剃刀の原理) の例

Occam’s Razor principle

「Plurality should not be posited without necessity」 (必要以上に多くを仮定すべきではない)

「the simplest explanation is best」(最も単純な説明が最善である) とも言い換えられる

• 今回の文脈では、「他のすべてのものが等しいと、より単純な（より小さい）仮説集合がより良い」