VC-Dimension der Klasse der Polynomklassifizierer von Grad $ n $

Question

Ich stieß auf diese Anweisung auf Seite 85 des Buches "Machine verstehen Lernen: von Theorie bis Algorithmen" < / a>

Die allgemeine Idee ist wie folgt:

Betrachten Sie ein binäres Klassifizierungsproblem mit der Instanzdomäne, die $ X=MathBB R $ ist.

für jeden $ n \ in \ mathbb n $ let $ h_n $ Sei die Klasse der Polynome Klassifiziere des Grades $ n $ ; $ h_n $ ist der Satz aller Klassifizierungen des Formulars $ h (x)=operatorName {sign} ( p (x)) $ , wobei $ p \ colon \ mathbb r \ to \ mathbb r $ ein Polynom von Grad $ n $ .

Beweisen Sie, dass die VC-Dimension von $ h_n $ $ n + 1 $ ist. .

Answer 1

Die Idee ist, dass ein Polynom von Grad $ n $ höchstens $ n $ Wurzeln, Und so kann man Zeichen in den meisten $ n $ mal wechseln. Daher kann kein Polynom von Grad $ N $ ein alternierendes Muster + - + -... oder - + - + ... von Länge $ n + 2 $ . Dies zeigt, dass die VC-Dimension höchstens $ n + 1 $ ist.

Auf der anderen Seite, für jeden Satz von $ n + 1 $ Paare $ (x_1, y_1), \ LDOTs, (x_ {n + 1}, y_ {n + 1}) $ , es gibt ein Polynom von Grad $ N $ , das sie interpoliert, gegeben von der Lagrange Interpolationsformel. Verwenden von $ y_i=pm 1 $ , können Sie problemlos so zeigen, dass Y Set von $ N +1 $ punkte ist erschüttert. Daher ist die VC-Dimension genau $ n + 1 $ .