Algorytm optymalizacji drzew decyzyjnych

tło

Binarne drzewo decyzja $T$ jest zakorzenione drzewo gdzie każdy węzeł wewnętrzny (i korzeń) jest oznaczony przez indeks w $j \in \{1,..., n\}$ taki sposób, że żadna ścieżka od korzenia do liścia nie powtarza indeksu, liście są oznaczone wyjściami w $\{A,B\}$ , a każda krawędź jest oznaczona przez $0$ dla lewego dziecka i $1$ dla prawego dziecka. Aby zastosować drzewo do wejścia $x$ :

1. Zacznij od katalogu głównego
2. jeśli jesteś przy liściu, wyprowadzasz etykietę liścia $A$ lub $B$ i kończysz
3. Przeczytaj etykietę bieżącego węzła, jeśli x j = 0, to przejdź do lewego dziecka, a jeśli x j = 1, przejdź do prawego dziecka.$j$$x_j = 0$$x_j = 1$
4. przejdź do kroku (2)

Drzewo jest używane jako sposób oceny funkcji, w szczególności mówimy, że drzewo reprezentuje całkowitą funkcję f, jeśli dla każdego x ∈ { 0 , 1 } n mamy T ( x ) = f ( x ) . Złożoność zapytania drzewa jest jego głębokością, a złożoność zapytania funkcji to głębokość najmniejszego drzewa, które ją reprezentuje.$T$$f$$x \in \{0,1\}^n$$T(x) = f(x)$

Problem

Dane binarne drzewo decyzyjne T generuje binarne drzewo decyzyjne T 'o minimalnej głębokości, tak że T i T' reprezentują tę samą funkcję.

Pytanie

Jaki jest najbardziej znany algorytm? Czy znane są jakieś dolne granice? Co jeśli wiemy, że ? A jeśli wymagamy tylko, aby T ′ miała w przybliżeniu minimalną głębokość?$\text{depth}(T') = O(\log \text{depth}(T))$$T'$

Naiwne podejście

Naiwne podejście jest podana , aby wyliczyć wszystkie rekursywnie binarne drzewa decyzyjne o głębokości d - 1 podczas testowania, jeśli oceniać na samo jak T . Wydaje się, że wymaga to O ( d 2 n n $d = \text{depth}(T)$$d - 1$$T$kroki (przy założeniu, że potrzebadkroków, aby sprawdzić, coT(x)ocenia dla dowolnegox). Czy istnieje lepsze podejście?$O(\frac{d 2^n n!}{(n - d)!})$$d$$T(x)$$x$

Motywacja

To pytanie jest motywowane przez poprzednie pytanie dotyczące kompromisu między złożonością zapytania a złożonością czasową . W szczególności celem jest ograniczenie separacji czasowej dla wszystkich funkcji. Możemy stworzyć drzewo z algorytmu czasu optymalnego z czasem wykonania t , a następnie chcielibyśmy przekonwertować go na drzewo T ' dla algorytmu optymalnego dla zapytania. Niestety, jeśli t ∈ O ( n ! / ( N - d ) ! ) (I często d ∈ Θ ( n $T$$t$$T'$$t \in O(n!/(n - d)!)$$d \in \Theta(n)$) wąskim gardłem jest konwersja. Byłoby miło, gdybyśmy mogli zastąpić przez coś jak 2 d .$n!/(n - d)!$$2^d$

Mam 3 odpowiedzi, wszystkie dające nieco inne wyniki twardości.

Niech będzie jakąś funkcją.$f: \{0,1\}^n \rightarrow \{0,1\}$

odpowiedź 1

Biorąc pod uwagę, drzewa decyzyjnego obliczeniową F i numer, jest NP-trudno powiedzieć, czy istnieje drzewo decyzyjne T ' obliczeniowej f wielkości co najwyżej tej liczby. $T$$f$$T'$$f$( Zantema and Bodlaender '00 )

Odpowiedź 2

Biorąc pod uwagę drzewo decyzyjne obliczające f , NP jest trudne do przybliżenia najmniejszego drzewa decyzyjnego obliczającego f do dowolnego stałego współczynnika. $T$$f$$f$( Sieling '08 )

Odpowiedź 3

Niech będzie wielkość najmniejszego drzewa decyzyjnego obliczeniowej f . Biorąc pod uwagę drzewo decyzyjne T obliczające f , zakładając, że N P ⊊ D T I M E ( 2 n ϵ ) dla niektórych ϵ < 1 , nie można znaleźć równoważnego drzewa decyzyjnego T ′ o rozmiarze s k dla dowolnego k ≥ 0 .$s$$f$$T$$f$$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$T'$$s^k$$k \ge 0$

Myślę, że tej silniejszej odpowiedzi (opartej na słabszym założeniu) można uzyskać na podstawie znanych wyników w teorii uczenia się algorytmów Occama dla drzew decyzyjnych za pomocą następującego argumentu:

1. Czy można znaleźć drzewo decyzyjne zmiennych w czasie n log s , gdzie s jest najmniejszym drzewem decyzyjnym zgodnym z przykładami pochodzącymi z rozkładu (model PAC). ( Blum '92 ) $n$$n^{\log s}$$s$
2. Przy założeniu, że przez pewien ε < 1 , nie można dowiedzieć się, PAC WIELKOŚĆ s drzewa decyzyjne według rozmiaru s k drzew decyzyjnych dla każdego k ≥ 0 . ( Alekhnovich i in. '07 )$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$s$$s^k$$k \ge 0$

Te dwa wyniki wydają się sugerować wynik twardości dla twojego problemu. Z jednej strony (1) możemy znaleźć duże drzewo decyzyjne; Z drugiej strony (2), nie powinny być w stanie zminimalizować je, aby uzyskać równoważną jeden „mały”, o wymiarach , nawet jeśli taka istnieje od wielkości s .$s^k$$s$