Алгоритм оптимизации деревьев решений

Фон

Бинарное дерево решений представляет собой корневое дерево , где каждый внутренний узел (и корень) помечен индекс J ∈ { 1 , . , , , n } , так что путь от корня к листу не повторяет индекс, листья помечаются выходами в { A , B } , а каждое ребро помечается 0 для левого потомка и 1 для правого потомка. Чтобы применить дерево к входу x :$T$$j \in \{1,..., n\}$$\{A,B\}$$0$$1$$x$

1. Начать с корня
2. если вы находитесь на листе, вы выводите метку листа или B и завершаете$A$$B$
3. Прочитайте метку $j$ вашего текущего узла, если $x_j = 0$ затем перейдите к левому потомку, а если $x_j = 1$ то перейдите к правому потомку.
4. перейти к шагу (2)

Дерево используется как способ оценки функций, в частности, мы говорим, что дерево $T$ представляет полную функцию $f$ если для каждого $x \in \{0,1\}^n$ мы имеем $T(x) = f(x)$ . Сложность запроса дерева - это его глубина, а сложность запроса функции - это глубина самого маленького дерева, которое его представляет.

проблема

Для заданного двоичного дерева решений T выведите двоичное дерево решений T 'минимальной глубины, чтобы T и T' представляли одну и ту же функцию.

Вопрос

Каков самый известный алгоритм для этого? Известны ли нижние границы? Что если мы знаем, что ? А что, если мы требуем, чтобы T ′ был приблизительно минимальной глубины?$\text{depth}(T') = O(\log \text{depth}(T))$$T'$

Наивный подход

Наивный подход дается рекурсивно перечислить все бинарные деревья решений глубинной г - 1 при тестировании , если они оценивают одно и то же , как Т . Кажется, для этого требуется O ( d 2 n n $d = \text{depth}(T)$$d - 1$$T$шагов (при условии, что требуетсяdшагов, чтобы проверить, чтоT(x)оценивает для произвольногоx). Есть ли лучший подход?$O(\frac{d 2^n n!}{(n - d)!})$$d$$T(x)$$x$

мотивация

Этот вопрос мотивирован предыдущим вопросом о компромиссе между сложностью запроса и сложностью времени . В частности, цель состоит в том, чтобы ограничить временное разделение для всех функций. Мы можем создать дерево из алгоритма, оптимального по времени, со временем выполнения t , а затем мы хотим преобразовать его в дерево T ′ для алгоритма, оптимального для запроса. К сожалению, если t ∈ O ( n ! / ( N - d ) ! ) (И часто d ∈ Θ ( n $T$$t$$T'$$t \in O(n!/(n - d)!)$$d \in \Theta(n)$) узким местом является конверсия. Было бы неплохо , если бы мы могли бы заменить чем-то вроде 2 д .$n!/(n - d)!$$2^d$

У меня есть 3 ответа, все дают несколько разные результаты твердости.

Пусть - некоторая функция.$f: \{0,1\}^n \rightarrow \{0,1\}$

Ответ 1

Учитывая решение дерева вычислительное п и число, это NP-трудно сказать , если существует дерево решений Т ' вычислительное п размером не более этого числа. $T$$f$$T'$$f$( Zantema and Bodlaender '00 )

Ответ 2

Учитывая дерево решений вычисляющее f , NP трудно приблизить наименьшее вычисление дерева решений f к любому постоянному коэффициенту. $T$$f$$f$( Sieling '08 )

Ответ 3

Пусть будет размером наименьшего дерева решений, вычисляющего f . Учитывая дерево решений T, вычисляющее f , предполагая, что N P ⊊ D T I M E ( 2 n ϵ ) для некоторого ϵ < 1 , невозможно найти эквивалентное дерево решений T ′ размера s k для любого k ≥ 0 .$s$$f$$T$$f$$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$T'$$s^k$$k \ge 0$

Я думаю, что этот более сильный ответ (опираясь на более слабое предположение) может быть получен из известных результатов теории обучения алгоритмов Оккама для деревьев решений с помощью следующего аргумента:

1. Можно ли найти дерево решений по переменным за время n log s , где s - это наименьшее дерево решений, согласующееся с примерами из распределения (модель PAC). ( Blum '92 ) $n$$n^{\log s}$$s$
2. Предполагая, что для некоторого ϵ < 1 , мы не можем PAC выучить деревья решений размера s по деревьям решений размера s k для любого k ≥ 0 . ( Алехнович и др. '07 )$NP \subsetneq DTIME(2^{n^\epsilon})$$\epsilon < 1$$s$$s^k$$k \ge 0$

Эти два результата, по-видимому, подразумевают результат твердости вашей проблемы. С одной стороны (1) мы можем найти большое дерево решений; с другой стороны (2), мы не должны быть в состоянии минимизировать его, чтобы получить эквивалентный «маленький», размера , даже если существует размер s .$s^k$$s$