PAC による汎化能力の評価

学習アルゴリズムは多くの場合，何らかの損失関数を最小化する問題として 定式化されるが，実際に最小化できるものは学習サンプルだけから計算される 損失関数のサンプル平均(経験損失)である． 汎化能力を期待するなら，未知のサンプル を含めたすべてのサンプルに対する損失関数の期待値 (期待損失)を最小にしてほしいわけだが，それは未知だからできない． 従って，経験損失と期待損失の差が汎化能力を測る際の基本となる． これは PAC に限らずみな同じである． サンプルを生成する分布を $P(\mbox{\boldmath$x$},y)$ とし， パラメータ $\mbox{\boldmath$\alpha$}$ をもつ学習機械がサンプル $(\mbox{\boldmath$x$}_i, y_i)$ を処理した ときの損失関数を $r(\mbox{\boldmath$x$}_i,y_i; \mbox{\boldmath$\alpha$})$ とする． このとき経験損失はサンプル集合を $\cal D$ として

$$R_{\rm emp}(\mbox{\boldmath$\alpha$}; {\cal D}) = {1\over ... ...{r=1}^n r(\mbox{\boldmath$x$}_i,y_i; \mbox{\boldmath$\alpha$})$$

であり，これを最小化するパラメータを $\hat{\mbox{\boldmath$\alpha$}}$ とする． 一方，期待損失は

$$R(\mbox{\boldmath$\alpha$}) = \int r(\mbox{\boldmath$x$},y; \mbox{\boldmath$\alpha$}) dP(\mbox{\boldmath$x$},y)$$

であり，これを最小化するパラメータを $\mbox{\boldmath$\alpha$}^*$ とする． 学習によって得られるパラメータが最適なパラメータに比べてどれだけ損を しているかは，

$$C_1 = R(\hat{\mbox{\boldmath$\alpha$}}) - R(\mbox{\boldmath$\alpha$}^*)$$

で評価できる． ただしここで問題となるのは， この値が未知の分布 $P(\mbox{\boldmath$x$},y)$ に依存していることである． さらに，サンプルはその未知の分布に従う確率変数だから， $R(\hat{\mbox{\boldmath$\alpha$}})$は サンプルに従って動く確率変数である．

確率変数 $C_1$ を特徴づけるものはいくつか考えられるが，AIC などの情報量 規準では「期待値」，PAC では「信頼区間」を考えるという違いがある． ここではそのうち PAC についてより詳しく述べる．

分布が未知の状況下では $C_1$ の信頼区間を正確に求めることは難しい． そこで，PAC ではさらにその信頼区間の上限をいくつかの不等式を用いて導く． その概略を順を追って説明しよう．

• $C_1 < C_2(\hat{\mbox{\boldmath$\alpha$}})+C_2(\mbox{\boldmath$\alpha$}^*)$. ただし， $C_2(\mbox{\boldmath$\alpha$})=\vert R(\mbox{\boldmath$\alpha$})- R_{\rm emp}(\mbox{\boldmath$\alpha$}; {\cal D})\vert$
• $C_2(\hat{\mbox{\boldmath$\alpha$}})+C_2(\mbox{\boldmath$\alpha$}^*) < 2\sup_{\mbox{\boldmath$\alpha$}} C_2(\mbox{\boldmath$\alpha$})$.
• $\mbox{Pr}[\sup_{\mbox{\boldmath$\alpha$}} C_2(\mbox{\boldmath$\alpha$}) >\epsil... ...{Pr}[\sup_{\mbox{\boldmath$\alpha$}} C_3(\mbox{\boldmath$\alpha$}) >\epsilon/2]$. ここで， $C_3(\mbox{\boldmath$\alpha$})$ は $n$ 個のサンプルの損失を 二つの異なるサンプルセット ${\cal D}_1$ と ${\cal D}_2$ に対して測った ものの差 $C_3(\mbox{\boldmath$\alpha$})= \vert R_{\rm emp}(\mbox{\boldmath$\alpha$}; {\cal D}_1)-R_{\rm emp}(\mbox{\boldmath$\alpha$}; {\cal D}_2)\vert$ である．
• $\mbox{Pr}[\sup_{\mbox{\boldmath$\alpha$}} C_3(\mbox{\boldmath$\alpha$}) > \epsi... ...alpha$}\in {\cal A}(2n)} \mbox{Pr}[ C_3(\mbox{\boldmath$\alpha$}) > \epsilon/2]$. ここで，集合 ${\cal A}(2n)$ は合計 $2n$ 個の サンプルに対して $C_3(\mbox{\boldmath$\alpha$})$ が異なる値を取るすべての $\mbox{\boldmath$\alpha$}$ の集合である．

これにより，個々の $\mbox{\boldmath$\alpha$}$ についての区間確率の和として $C_1$ の信頼区間 が押さえられた． さらに 個々の区間確率が $\mbox{\boldmath$\alpha$}$ によらない 値 $Q$ で押さえられれば，単に $C_1 \le \vert{\cal A}(2n)\vert Q$ という結果になる． $Q$ の評価式は Hoeffding の不等式

$$\mbox{Pr}[{1\over n} \sum_{i=1}^n X_i - \mbox{E}[X_i] > \epsilon] < \exp(-{2n\epsilon^2\over(b-a)^2}),$$ (5)

などを用いて証明できるが(ただし 確率変数 $X_i\in[a,b]$)， McDiarmid の不等式を用いると少しだけタイトな上限が得られる． 結果として， $C_2(\mbox{\boldmath$\alpha$})$ に関する不等式 (信頼区間 $1-\delta$)

$$R(\mbox{\boldmath$\alpha$}) \le R_{\rm emp}(\mbox{\boldmath... ...\over n} (\log(\vert{\cal A}(2n)\vert)+\log({4\over\delta}))}$$

として得られる．

残る問題は $\vert\cal A\vert$ をどう評価すればよいかということであるが， 代表的なものとして，VC 次元を用いた評価がある． 一般に VC 次元が 大きいほど $\vert\cal A\vert$ のサイズの上限が大きくなる．

SVM との関連で言うと，サンプルの特徴ベクトルが半径 $D$ の超球に含まれているとき， マージンの大きさ $\gamma$ をもつ超平面クラスの VC 次元は $\min\{D^2\gamma^2,h\}$ に比例した値で上から押さえられる ($h$ は特徴空間の次元)． 従って，マージンの大きなクラスほど汎化能力の高い 識別器であり，特徴空間の次元とは無関係で「次元の呪い」から逃れられる． ただし，実はこの推論には落とし穴があり，学習によって得られたマージン というのはサンプルに依存したもので，想定した関数クラスというわけではない． この問題を克服するために，厳密には luckiness という枠組みに拡張する必要がある[11]．

以下，PAC や SVM の汎化能力に関係し重要と思われる事項をいくつかまとめておく．

• SVM の leave-one-out エラーの上限を導くことができ，それは サポートベクタの数で押さえられる． 従って，サポートベクタの数が 小さければ小さいほど leave-one-out エラーは汎化能力を測る一つの規準だか らサポートベクタの数が小さいほど汎化能力は高い．
• 容易に想像できるように PAC の上限は何段階にもわたる不等式 評価をしているためかなり甘い． そのため，PAC の上限はモデル選択などには使えないという評価が強い． それでも SVM が次元の呪いを受けないことを示せたように，理論的な価値は 高い． オリジナルの PAC 式の上限をタイトにしていくという方向の他に， ここでは二つの新しい指標による期待損失の信頼区間の上限評価について 紹介する． 一つはデータ圧縮という考え方を(MDL とは異なるやり方で)用いて学習 アルゴリズムの複雑さを評価するもの[9]で， もう一つはロバスト性に関係する指標を用いたものである[6]． いずれも従来 VC 次元ではできなかったタイトな上限を導く可能性を もっている．