$ N $の多項式分類器のクラスのVC次元

Question

私はこの文 "Machine Learning：理論からアルゴリズムへのもの" < / a>

一般的な考え方は次のとおりです。

インスタンスドメインが $ x=mathbb r $ であるバイナリ分類問題を考える。

$ n \ in \ mathbb n $ $ h_n $ を多項式のクラスにする学位 $ n $ の分類すなわち、 $ h_n $ は、 $ h（x）= agoyname {sign}のすべてのClassiferのセットです。 P（x））$ 。ここで、 $ p \ colon \ mathbb r \ to \ mathbb r $ は、 $ n $ 。

$ h_n $ のVCディメンションは $ n + 1 $ です。

Answer 1

学位 $ n $ の多項式は、 $ n $ roots、そのため、 $ n $ 時間の標識を変更できます。したがって、 $ n $ の多項式はありません+ - + -...または - + - + ...の長さ $ n + 2 $ 。これは、VCディメンションが $ n + 1 $ です。

一方、 $ n + 1 $ $（x_1、y_1）の任意のセットの場合LDOTS、（x_ {n + 1}、y_ {n + 1}）$ 、 $ n $ の多項式がそれらを補間します。ラグランジュ補間式によって与えられる。 $ y_i=pm 1 $ を使用すると、 の $ nのセットを簡単に表示できます。 +1 $ 点は粉々になっています。したがって、VCディメンションは正確に $ n + 1 $ です。