Algoritmo para otimizar árvores de decisão

fundo

Uma árvore de decisão binária é uma árvore com raiz onde cada nó interno (e raiz) é marcado por um índice j ∈ { 1 , . . . , n } de modo que nenhum caminho da raiz para a folha repita um índice, as folhas são rotuladas pelas saídas em { A , B } e cada borda é rotulada por 0 para o filho esquerdo e 1 para o filho direito. Para aplicar uma árvore a uma entrada x :$T$$j \in \{1,..., n\}$$\{A,B\}$$0$$1$$x$

1. Comece pela raiz
2. se você estiver na folha, você imprime o rótulo da folha ou B e termina$A$$B$
3. Leia o rótulo do seu nó atual, se x j = 0 , mova para o filho esquerdo e se x j = 1 , mova para o filho direito.$j$$x_j = 0$$x_j = 1$
4. pule para o passo (2)

A árvore é usada como uma maneira de avaliar funções, em particular, dizemos que uma árvore representa uma função total f se para cada x ∈ { 0 , 1 } n tivermos T ( x ) = f ( x ) . A complexidade da consulta de uma árvore é sua profundidade, e a complexidade da consulta de uma função é a profundidade da menor árvore que a representa.$T$$f$$x \in \{0,1\}^n$$T(x) = f(x)$

Problema

Dada uma árvore de decisão binária, T produz uma árvore de decisão binária T 'de profundidade mínima, de modo que T e T' representam a mesma função.

Questão

Qual é o algoritmo mais conhecido para isso? Existem limites inferiores conhecidos? E se soubermos que a ? E se exigirmos apenas que T ' tenha profundidade aproximadamente mínima?$\text{depth}(T') = O(\log \text{depth}(T))$$T'$

Abordagem ingênua

A abordagem ingênua é dado recursivamente enumerar todas as árvores de decisão binárias de profundidade d - 1 ao testar se eles avaliam a mesma coisa que T . Isso parece exigir O ( d 2 n n $d = \text{depth}(T)$$d - 1$$T$etapas (assumindo que são necessáriasdetapas para verificar o queT(x)avalia para umxarbitrário). Existe uma abordagem melhor?$O(\frac{d 2^n n!}{(n - d)!})$$d$$T(x)$$x$

Motivação

Essa pergunta é motivada por uma pergunta anterior sobre a troca entre complexidade de consulta e complexidade de tempo . Em particular, o objetivo é limitar a separação de tempo para o total de funções. Podemos fazer uma árvore partir de um algoritmo ideal de tempo com tempo de execução t e, em seguida, gostaríamos de convertê-la em uma árvore T ' para um algoritmo ideal de consulta. Infelizmente, se t ∈ O ( n ! / ( N - d ) ! ) (E frequentemente d ∈ Θ ( n $T$$t$$T'$$t \in O(n!/(n - d)!)$$d \in \Theta(n)$) o gargalo é a conversão. Seria bom se pudéssemos substituir por algo como 2 d .$n!/(n - d)!$$2^d$

Eu tenho 3 respostas, todas dando resultados de dureza um pouco diferentes.

Seja alguma função.$f: \{0,1\}^n \rightarrow \{0,1\}$

resposta 1

Dada uma árvore de decisão computando f e um número, é NP difícil dizer se existe uma árvore de decisão T ' computando f de tamanho no máximo esse número. $T$$f$$T'$$f$( Zantema e Bodlaender '00 )

Resposta 2

Dada uma árvore de decisão computando f , é NP difícil aproximar a menor árvore de decisão computando f a qualquer fator constante. $T$$f$$f$( Sieling '08 )

Resposta 3

Deixe ser o tamanho da menor árvore de decisão de computação f . Dada uma árvore de decisão T computada f , assumindo N P ⊊ D T I M E ( 2 n ϵ ) para alguns ϵ < 1 , não é possível encontrar uma árvore de decisão equivalente T ′ do tamanho s k para qualquer k ≥ 0 .$s$$f$$T$$f$$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$T'$$s^k$$k \ge 0$

Penso que esta resposta mais forte (baseada em uma suposição mais fraca) pode ser feita a partir de resultados conhecidos na teoria de aprendizagem dos algoritmos Occam para árvores de decisão, através do seguinte argumento:

1. É possível encontrar uma árvore de decisão em variáveis ​​no tempo n log s , onde s é a menor árvore de decisão consistente com exemplos provenientes de uma distribuição (modelo PAC). ( Blum '92 ) $n$$n^{\log s}$$s$
2. Assumindo para alguns ε < 1 , que não pode PAC aprender tamanho s árvores de decisão por tamanho s k árvores de decisão para qualquer k ≥ 0 . ( Alekhnovich et al. '07 )$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$s$$s^k$$k \ge 0$

Esses dois resultados parecem implicar um resultado de dureza para o seu problema. Por um lado (1), podemos encontrar uma grande árvore de decisão; por outro lado (2), não poderíamos minimizá-lo para obter um equivalente "pequeno", do tamanho , mesmo quando existe um tamanho s .$s^k$$s$