Dimensione VC della classe di classificatori polinomiali di grado $ N $

Question

Ho trovato Questa dichiarazione a pagina 85 del libro "Comprensione dell'apprendimento della macchina: dalla teoria agli algoritmi" < / a>

L'idea generale è la seguente:

Considerare un problema di classificazione binario con il dominio di istanza è $ x=mathbb r $ .

per ogni $ n \ in \ mathbbn n $ Let $ h_n $ Sii la classe di polinomio Classi fi in grado di laurea $ N $ ; vale a dire, $ h_n $ è il set di tutti gli classi di classi del modulo $ h (x)=operatorname {sign} ( p (x)) $ , dove $ p \ colon \ mathbbb r \ to \ mathbbl r $ è un polinomio di laurea $ N $ .

Dimostra che la dimensione VC della classe $ h_n $ è $ n + 1 $ .

Answer 1

L'idea è che un polinomio di grado $ N $ ha al massimo $ n $ radici, E così può cambiare i segni alla maggior parte dei $ N $ volte. Pertanto nessun polinomio di grado $ N $ può formare un modello alternato + - + -... o - + - + ... di lunghezza $ N + 2 $ . Ciò dimostra che la dimensione VC è al massimo $ N + 1 $ .

D'altra parte, per qualsiasi set di $ N + 1 $ coppie $ (x_1, y_1), \ Ldots, (x_ {n + 1}, y_ {n + 1}) $ , c'è un polinomio di laurea $ N $ che li interpola, Dato dalla formula di interpolazione LaGrange. Usando $ Y_I=PM 1 $ , puoi facilmente mostrare che qualsiasi set di $ n +1 $ punti è distrutto. Pertanto la dimensione VC è esattamente $ N + 1 $ .