Algoritma untuk mengoptimalkan pohon keputusan

Latar Belakang

Sebuah pohon keputusan biner $T$ adalah pohon berakar di mana setiap node internal (dan akar) diberi label oleh indeks $j \in \{1,..., n\}$ sedemikian sehingga tidak ada jalur dari root ke daun mengulangi indeks, daun diberi label oleh output di $\{A,B\}$ , dan setiap tepi diberi label oleh $0$ untuk anak kiri dan $1$ untuk anak kanan. Untuk menerapkan pohon ke input $x$ :

1. Mulai dari root
2. Jika Anda siap, Anda mengeluarkan label daun $A$ atau $B$ dan berakhir
3. Baca label $j$ dari simpul Anda saat ini, jika $x_j = 0$ kemudian pindah ke anak kiri dan jika $x_j = 1$ kemudian pindah ke anak kanan.
4. lompat ke langkah (2)

Pohon ini digunakan sebagai cara untuk mengevaluasi fungsi, khususnya kami katakan pohon $T$ merupakan fungsi jumlah $f$ jika untuk setiap $x \in \{0,1\}^n$ kita memiliki $T(x) = f(x)$ . Kompleksitas kueri suatu pohon adalah kedalamannya, dan kompleksitas kueri suatu fungsi adalah kedalaman pohon terkecil yang mewakilinya.

Masalah

Diberikan pohon keputusan biner T output pohon keputusan biner T 'dari kedalaman minimal sehingga T dan T' mewakili fungsi yang sama.

Pertanyaan

Apa algoritma yang paling dikenal untuk ini? Apakah ada batas bawah yang diketahui? Bagaimana jika kita tahu bahwa $\text{depth}(T') = O(\log \text{depth}(T))$ ? Bagaimana jika kita hanya membutuhkan $T'$ kira-kira kedalaman minimal?

Pendekatan naif

Pendekatan naif diberikan untuk secara rekursif menghitung semua pohon keputusan biner dari kedalaman d - 1 saat uji coba jika mereka mengevaluasi hal yang sama seperti T . Ini sepertinya membutuhkan O ( d 2 n n $d = \text{depth}(T)$$d - 1$$T$langkah-langkah (dengan asumsi bahwa diperlukanlangkah-langkahduntuk memeriksa apaT(x)mengevaluasi untuk untuk sewenang-wenangx). Apakah ada pendekatan yang lebih baik?$O(\frac{d 2^n n!}{(n - d)!})$$d$$T(x)$$x$

Motivasi

Pertanyaan ini dimotivasi oleh pertanyaan sebelumnya tentang pertukaran antara kompleksitas kueri dan kompleksitas waktu . Secara khusus, tujuannya adalah untuk mengikat pemisahan waktu untuk fungsi total. Kita dapat membuat pohon dari algoritma waktu optimal dengan runtime t , dan kemudian kami ingin mengubahnya menjadi pohon T ′ untuk algoritme optimal kueri. Sayangnya, jika t ∈ O ( n ! / ( N - d ) ! ) (Dan sering d ∈ Θ ( n $T$$t$$T'$$t \in O(n!/(n - d)!)$$d \in \Theta(n)$) bottleneck adalah konversi. Alangkah baiknya jika kita bisa mengganti oleh sesuatu seperti 2 d .$n!/(n - d)!$$2^d$

Saya punya 3 jawaban, semuanya memberikan hasil kekerasan yang agak berbeda.

Biarkan menjadi beberapa fungsi.$f: \{0,1\}^n \rightarrow \{0,1\}$

jawaban 1

Mengingat pohon keputusan komputasi f dan angka, itu adalah NP-sulit untuk mengatakan jika ada pohon keputusan T ' komputasi f ukuran paling nomor itu. $T$$f$$T'$$f$( Zantema dan Bodlaender '00 )

Jawaban 2

Diberikan pohon keputusan komputasi f , NP sulit untuk memperkirakan pohon keputusan keputusan terkecil f untuk setiap faktor konstan. $T$$f$$f$( Sieling '08 )

Jawaban 3

Biarkan menjadi ukuran terkecil pohon keputusan komputasi f . Diberikan pohon keputusan T menghitung f , dengan asumsi N P ⊊ D T I M E ( 2 n ϵ ) untuk beberapa ϵ < 1 , seseorang tidak dapat menemukan pohon keputusan yang setara T ′ dari ukuran s k untuk setiap k ≥ 0 .$s$$f$$T$$f$$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$T'$$s^k$$k \ge 0$

Saya pikir jawaban yang lebih kuat ini (mengandalkan asumsi yang lebih lemah) dapat dibuat dari hasil yang diketahui dalam teori pembelajaran algoritma Occam untuk pohon keputusan, melalui argumen berikut:

1. Apakah mungkin untuk menemukan pohon keputusan pada variabel dalam waktu n log s , di mana s adalah pohon keputusan terkecil yang konsisten dengan contoh yang berasal dari distribusi (model PAC). ( Blum '92 ) $n$$n^{\log s}$$s$
2. Dengan asumsi untuk beberapa ε < 1 , kita tidak bisa PAC belajar ukuran s pohon keputusan berdasarkan ukuran s k pohon keputusan untuk setiap k ≥ 0 . ( Alekhnovich et al. '07 )$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$s$$s^k$$k \ge 0$

Kedua hasil ini tampaknya menyiratkan hasil kekerasan untuk masalah Anda. Di satu sisi (1), kita dapat menemukan pohon keputusan besar; di sisi lain (2), kita seharusnya tidak dapat menguranginya untuk mendapatkan yang "kecil" yang setara, dengan ukuran , bahkan ketika ada yang memiliki ukuran s .$s^k$$s$