Qual é a dimensão VC de uma árvore de decisão?

Qual é a dimensão VC de uma árvore de decisão com k divide em duas dimensões? Digamos que o modelo é CART e as únicas divisões permitidas são paralelas aos eixos.

Portanto, para uma divisão, podemos ordenar 3 pontos em um triângulo e, para qualquer identificação dos pontos, podemos obter uma previsão perfeita (ou seja: pontos quebrados)

Mas e quanto a 2 divisões, ou qualquer k geral?

Não tenho certeza se essa é uma pergunta com uma resposta simples, nem acredito que seja uma pergunta que precise ser feita sobre árvores de decisão.

Consulte Aslan et al. , Calculando a VC-Dimensão das Árvores (2009). Eles solucionam esse problema fazendo uma pesquisa exaustiva em árvores pequenas e fornecendo uma fórmula recursiva aproximada para estimar a dimensão VC em árvores maiores. Eles então usam essa fórmula como parte de um algoritmo de poda. Se houvesse uma resposta em formato fechado para sua pergunta, tenho certeza de que eles a forneceriam. Eles sentiram a necessidade de percorrer o caminho através de árvores pequenas.

Meus dois centavos valem. Não tenho certeza se é significativo falar sobre a dimensão VC para três decisões. Considere um resposta dimensional, onde cada item é um resultado binário. Essa é a situação considerada por Aslan et al. Existem possíveis resultados neste espaço de amostra e possíveis padrões de resposta. Se eu construir uma árvore completa, com níveis de d e folhas de 2 d , então eu posso quebrar qualquer padrão de 2 d$d$$2^d$$2^d$$d$$2^d$$2^d$respostas. Mas ninguém se encaixa em árvores completas. Normalmente, você superajusta e volta a usar a validação cruzada. O que você obtém no final é uma árvore menor e mais simples, mas seu conjunto de hipóteses ainda é grande. Aslan et al. tente estimar a dimensão VC de famílias de árvores isomórficas. Cada família é uma hipótese definida com sua própria dimensão de VC.

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

A solução de força bruta de Aslan parece funcionar razoavelmente bem, mas o que eles obtêm não é realmente a dimensão VC dos algoritmos que as pessoas usam, pois eles se baseiam em poda e validação cruzada. É difícil dizer qual é realmente o espaço da hipótese, já que, em princípio, começamos com um número esmagador de árvores possíveis, mas depois podamos algo mais razoável. Mesmo que alguém comece com uma escolha a priori de não ir além de duas camadas, digamos, ainda pode haver uma necessidade de podar a árvore. E realmente não precisamos da dimensão VC, pois a validação cruzada ocorre diretamente após o erro fora da amostra.

Para ser justo com Aslan et al., Eles não usam a dimensão VC para caracterizar seu espaço de hipóteses. Eles calculam a dimensão VC de ramificações e usam essa quantidade para determinar se a ramificação deve ser cortada. Em cada estágio, eles usam a dimensão VC da configuração específica da ramificação em consideração. Eles não olham para a dimensão VC do problema como um todo.

Se suas variáveis ​​são contínuas e a resposta depende de atingir um limite, uma árvore de decisão está basicamente criando um monte de perceptrons, portanto a dimensão VC provavelmente será maior que isso (já que você precisa estimar o ponto de corte para fazer a divisão) . Se a resposta depender monotonicamente de uma resposta contínua, o CART a dividirá em várias etapas, tentando recriar um modelo de regressão. Eu não usaria árvores nesse caso - possivelmente gam ou regressão.