仮説集合の複雑度#

VC次元#

VC次元 (VC dimension) は仮説集合の複雑度の指標の一つ。 主に2値判別問題の仮説集合に用いられるが、多値判別問題や回帰問題に拡張することも可能。 名前の由来は理論の創始者であるVapnikとChervonenkisから。

2値判別のための仮説集合を H とする。 仮説 hH は、入力空間 X から |Y|=2 であるようなラベル集合 Y への関数とする。 入力の集合 {x1,,xn}X に対して、Yn の部分集合

{(h(x1),,h(xn))YnhH}

の要素数を

ΠH(x1,,xn)=|{(h(x1),,h(xn))YnhH}|

とおく(英語だとGrowth Functionと呼ばれる様子)。

定義より

ΠH(x1,,xn)2n

である。

入力の数nが増えていけばラベル付のパターンが豊富となり、等式ΠH(x1,,xn)=2nが成立しにくくなると考えられる。その境界となるデータ数nHのVC次元と呼ぶ。

数式的には、HのVC次元VCdim(H)

VCdim(H):=max{nN| maxx1,,xnXΠH(x1,,xn)=2n}

と定義される。また、任意の nN に対して x1,,xnX が存在して ΠH(x1,,xn)=2n が成り立つときは VCdim(H)= と定義する。

VC次元は言葉で説明すると「仮説集合Hのもとで、ラベルのすべての組み合わせを網羅できる(どんなラベル付けにも対応可能な仮説が存在する)データ数の最大値」となる。

例:step function#

1直線上に並ぶ点で、step functionのようにラベルが変化する(positive raysと呼ばれる?)なら、1つの点で分離できる。

Hh:R{0,1}なる関数、具体的には h(x)=1(xa) をすべて含むとする。

n個のデータ点を2つの領域に分類するとき、n+1個のパターンがある。

Growth functionはΠH(x1,,xn)=n+1となり、n=0,1のときのみΠH(x1,,xn)=2nなので、VCdim(H)=1となる。

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=[5, 1.5])

x = np.arange(0, 10)
a = 4.5
y = 1 * (x >= a)
ax.arrow(-1, 0, x.max() + 2, 0, head_width=0.1, head_length=0.3, fc='black', ec='black')
for y_ in [0, 1]:
    idx = y_ == y
    ax.scatter(x[idx], np.zeros_like(x[idx]), label=f"h(x)={y_}")

ax.scatter(a, 0, marker="s", color="red")
ax.text(a, 0.2, "a", color="red", ha="center")

ax.legend()
ax.set(ylim=(-0.5, 1.5), yticks=[], yticklabels=[], xticks=[], xticklabels=[], title="positive rays")
fig.show()
../../_images/20d5f0a4a37f92a71d138f35bf6e900f261700182cb0624cdddb0e4049aacbfc.png

例:intervals#

1直線上で、ある区間だけy=1、他がy=0となる場合。

Growth functionは

ΠH(x1,,xn)=(n+12)+1=12n2+12n+1

となり、n=0,1,2のときのみΠH(x1,,xn)=2nなので、VCdim(H)=2となる。

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=[5, 1.5])
x = np.arange(0, 10)
a, b = [1.5, 7.5]
y = 1 * (a <= x) * (x < b)
ax.arrow(-1, 0, x.max() + 2, 0, head_width=0.1, head_length=0.3, fc='black', ec='black')
for y_ in [0, 1]:
    idx = y_ == y
    ax.scatter(x[idx], np.zeros_like(x[idx]), label=f"h(x)={y_}")

ax.scatter(a, 0, marker="s", color="red")
ax.text(a, 0.2, "a", color="red", ha="center")
ax.scatter(b, 0, marker="s", color="red")
ax.text(b, 0.2, "b", color="red", ha="center")

ax.legend()
ax.set(ylim=(-0.5, 1.5), yticks=[], yticklabels=[], xticks=[], xticklabels=[], title="positive intervals")

fig.show()
../../_images/79f90bff2995f75f4c41c2db55c04c4b6cb00710e4017fbfecb81e6e56f182dd.png

例:3点#

一直線上にない3点までなら、1つの直線でグループを2つに分けられる。4点になると分けられないものが出てくる(線形分離不可能問題)

VC次元の意味と例 - 具体例で学ぶ数学

サウアーの補題#

HのVC次元をdとおくと、dnならΠH(x1,,xn)は高々d次の多項式オーダーO(nd)となる。

サウアーの補題(Sauer’s lemma)

2 値ラベルに値をとる仮説集合 H の VC 次元が d のとき、 nd に対して

maxx1,,xnXΠH(x1,,xn)(end)d

が成り立つ。 ここで e はネイピア数 (2.718)である。

VC次元と予測誤差の関係#

定理

2 値ラベルに値をとる仮説集合 H{h:X{+1,1}} の VC次元を d< とする。 学習データ (X1,Y1),,(Xn,Yn) は独立に同一の分布に従うとする。損失として 01 損失を用いると、nd のとき、学習データの分布のもとで 1δ 以上の確率で

suphH|R(h)R^(h)|22dnlogend+log(2/δ)2n

が成り立つ。

この定理の証明にはラデマッハ複雑度による一様大数の法則が用いられる。

学習データS={(X1,Y1),,(Xn,Yn)}が観測されたとき、経験判別誤差R^(h)の最小化で得られる仮説をhSとする。簡単のため、ベイズ規則h0Hに含まれるとする。このとき

R^(hS)R^(h0)R(h0)R(hS)

が常に成り立つ。そして以下が成り立つ

(以下は金森(2015)のp.22の式展開を想像で補ったりしたもの)

R^(hS)R^(h0)R^(hS)+R(hS)R^(h0)+R(hS)R(hS)R^(h0)+R(hS)R^(hS)R(hS)R(h0)R(h0)+R^(h0)+R(hS)R^(hS)R(hS)R(h0)+|R^(h0)R(h0)|+suphH|R(hS)R^(hS)|(supR(hS)R(h0)+2suphH|R(hS)R^(hS)|(h0H)R(hS)R(h0)+42dnlogend+log(2/δ)2n()

確率オーダーで表現すると

R(hS)R(h0)+Op(log(n/d)n/d)

となり、予測誤差はデータ数とVC次元の比n/dと関連していることがわかる。

PAC学習との関係#

VC次元は、PAC学習の理論を仮説集合が有限でない場合にも拡張する際に登場する指標らしい(VC次元の意味と例 - 具体例で学ぶ数学

参考#