Quelle est la dimension VC d'un arbre de décision?

Quelle est la dimension VC d'un arbre de décision avec k divisions en deux dimensions? Disons que le modèle est CART et que les seules divisions autorisées sont parallèles aux axes.

Donc, pour une division, nous pouvons commander 3 points dans un triangle , puis pour tout étiquetage des points, nous pourrions obtenir une prédiction parfaite (c'est-à-dire: des points brisés)

Mais qu'en est-il de 2 divisions ou de tout k général?

Je ne suis pas sûr que ce soit une question avec une réponse simple, et je ne pense pas non plus que ce soit une question qui doive même être posée au sujet des arbres de décision.

Consultez Aslan et al. , Calcul de la dimension VC des arbres (2009). Ils abordent ce problème en effectuant une recherche exhaustive dans de petits arbres, puis en fournissant une formule approximative et récursive pour estimer la dimension VC sur des arbres plus grands. Ils utilisent ensuite cette formule dans le cadre d'un algorithme d'élagage. S'il y avait eu une réponse fermée à votre question, je suis sûr qu'ils l'auraient fournie. Ils ont ressenti le besoin d'itérer leur chemin à travers des arbres même assez petits.

$d$$2^d$$2^d$$d$$2^d$$2^d$réponses. Mais personne ne correspond à des arbres complets. En règle générale, vous suréquipez puis taillez à nouveau en utilisant la validation croisée. Ce que vous obtenez à la fin est un arbre plus petit et plus simple, mais votre ensemble d'hypothèses est toujours grand. Aslan et al. essayer d'estimer la dimension VC des familles d'arbres isomorphes. Chaque famille est un ensemble d'hypothèses avec sa propre dimension VC.

$d=3$$(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$$x1$$x2$

La solution de force brute d'Aslan semble fonctionner assez bien, mais ce qu'ils obtiennent n'est pas vraiment la dimension VC des algorithmes que les gens utilisent, car ils reposent sur l'élagage et la validation croisée. Il est difficile de dire ce qu'est réellement l'espace d'hypothèse, car en principe, nous commençons avec un nombre bouleversant d'arbres possibles, puis nous élaguons vers quelque chose de plus raisonnable. Même si quelqu'un commence par un choix a priori de ne pas aller au-delà de deux couches, par exemple, il peut encore être nécessaire de tailler l'arbre. Et nous n'avons pas vraiment besoin de la dimension VC, car la validation croisée recherche directement l'erreur hors échantillon.

Pour être juste envers Aslan et al., Ils n'utilisent pas la dimension VC pour caractériser leur espace d'hypothèses. Ils calculent la dimension VC des branches et utilisent cette quantité pour déterminer si la branche doit être coupée. À chaque étape, ils utilisent la dimension VC de la configuration spécifique de la branche considérée. Ils ne regardent pas la dimension VC du problème dans son ensemble.

Si vos variables sont continues et que la réponse dépend de l'atteinte d'un seuil, alors un arbre de décision crée essentiellement un tas de perceptrons, donc la dimension VC serait probablement plus grande que cela (car vous devez estimer le point de coupure pour effectuer la séparation) . Si la réponse dépend de façon monotone d'une réponse continue, CART la découpera en plusieurs étapes, essayant de recréer un modèle de régression. Je n'utiliserais pas d'arbres dans ce cas - éventuellement gam ou régression.