VC次元

AICが尤度と期待平均尤度との差から導出されたのに対し、サンプルについての 経験損失と真の分布についての期待損失の差をPAC学習の枠組から評価して得 られたVC(Vapnik-Chervonenkis)次元を用いて評価する方法がある (Vapnik(1982))。

ここで仮にモデルのVC次元が$d$であるとする。これから汎化性の評価として Vapnikの一様収束の理論からサンプルから得られる経験損失$I_{emp}$と真の 期待損失$I$の推定の差がVC次元$d$によって書ける。

$$I < I_{emp} + \sqrt{ \frac{d(\log 2m/d + 1) - \log \eta}{m} }$$

($\eta$はPAC学習における最大許容誤差、$m$はサンプル数)

このVC次元により階層型ニューラルネットワークの汎化性の評価も行われてい る(Baum,Haussler(1989))

またVapnikはモデルを構造化し、経験損失ではなく上式の右辺を最小化するよ うな基準によってモデル選択を行う方法(Structual Risk Minimization)を提 唱している。

しかしモデルのVC次元を厳密に求めることは特殊な場合を除いて実際にはそれ ほど容易ではないため、簡単な近似や推定値を用いることになる。またVC次元 は学習法やモデルによらない評価である一方、非常に粗い最悪評価になってい るためより実際的にはよりタイトな評価である実効VC次元などの拡張が有効で ある。