Algoritmo para optimizar árboles de decisión

16

Antecedentes

Un árbol de decisión binario es un árbol enraizado donde cada nodo interno (y raíz) está etiquetado por un índice modo que ninguna ruta de raíz a hoja repita un índice, las hojas están etiquetados por salidas en , y cada borde está etiquetado por para el hijo izquierdo y para el hijo derecho. Para aplicar un árbol a una entrada :j { 1 , . . . , n } { A , B } 0 1 xTj{1,...,n}{A,B}01x

  1. Comience en la raíz
  2. si está en la hoja, imprime la etiqueta de la hoja A o B y termina
  3. Lea la etiqueta j de su nodo actual, si xj=0 0 luego muévase al hijo izquierdo y si xj=1 luego muévase al hijo derecho.
  4. saltar al paso (2)

El árbol se usa como una forma de evaluar funciones, en particular decimos que un árbol T representa una función total F si para cada x{0,1}norte tenemos T(x)=f(x) . La complejidad de la consulta de un árbol es su profundidad, y la complejidad de la consulta de una función es la profundidad del árbol más pequeño que lo representa.


Problema

Dado un árbol de decisión binario T, sale un árbol de decisión binario T 'de profundidad mínima de tal manera que T y T' representan la misma función.

Pregunta

¿Cuál es el algoritmo más conocido para esto? ¿Se conocen límites inferiores? ¿Qué pasa si sabemos que la depth(T)=O(logdepth(T)) ? ¿Qué pasa si solo requerimos que T tenga aproximadamente una profundidad mínima?


Enfoque ingenuo

El enfoque ingenuo se da para enumerar de forma recursiva todos los árboles de decisión binarios de profundidad d - 1 mientras se prueba si se evalúan a lo mismo que t . Esto parece requerir O ( d 2 n n !d=depth(T)d1Tpasos (suponiendo que se necesitandpasos para verificar quéT(x)evalúa para unaxarbitraria). ¿Hay un mejor enfoque?O(d2nn!(nd)!)dT(x)x

Motivación

Esta pregunta está motivada por una pregunta previa sobre el equilibrio entre la complejidad de la consulta y la complejidad del tiempo . En particular, el objetivo es limitar la separación de tiempo para las funciones totales. Podemos hacer un árbol partir de un algoritmo de tiempo óptimo con tiempo de ejecución t , y luego nos gustaría convertirlo en un árbol T ' para un algoritmo de consulta óptimo. Desafortunadamente, si t O ( n ! / ( N - d ) ! ) (Y a menudo d Θ ( n )TtTtO(n!/(nd)!)dΘ(n)) el cuello de botella es la conversión. ¡Sería bueno si pudiéramos reemplazar por algo como 2 d .n!/(nd)!2d

Artem Kaznatcheev
fuente
Encontrar el árbol de decisión óptimo es NP-completo. Me enseñaron que en las clases de Teoría de la decisión y Minería de datos, sin embargo, se basaban en notas y no conozco el documento original que introdujo el resultado.
chazisop
@chazisop genial, gracias. No es obvio para mí que encontrar el árbol de decisión óptimo está en NP, pero lo pensaré / buscaré un poco más. A veces, conocer el enunciado del teorema está a medio camino de demostrarlo: D.
Artem Kaznatcheev
Creo que la primera referencia para esto es: Límites más bajos en las listas y árboles de decisiones de aprendizaje. (Hancock et al. 1994) cs.uwaterloo.ca/~mli/dl.ps
Lev Reyzin
1
La prueba de que encontrar el árbol de decisión óptimo es un problema de NP completo fue dada por Laurent Hyafil y Ronald L. Rivest en La construcción de árboles de decisión binarios óptimos es NP-complete (1976). referencia: aquí
antoine

Respuestas:

16

Tengo 3 respuestas, todas dando resultados de dureza algo diferentes.

Sea alguna función.f:{0,1}n{0,1}

respuesta 1

Dado un árbol de decisión calcula fy un número, es NP-difícil saber si existe un árbol de decisión T 'que computa f de tamaño como máximo ese número. TfTf( Zantema y Bodlaender '00 )

Respuesta 2

Dado un árbol de decisión computa f , es NP difícil aproximar el árbol de decisión más pequeño que computa f a cualquier factor constante. Tff( Sieling '08 )

Respuesta 3

Sea el tamaño del árbol de decisión más pequeño que computa f . Dado un árbol de decisión T que calcula f , suponiendo N P D T I M E ( 2 n ϵ ) para algunos ϵ < 1 , no se puede encontrar un árbol de decisión equivalente T ' de tamaño s k para cualquier k 0 .sfTfNPDTIME(2nϵ)ϵ<1Tskk0

Creo que esta respuesta más sólida (que se basa en una suposición más débil) puede hacerse a partir de resultados conocidos en la teoría del aprendizaje de algoritmos de Occam para árboles de decisión, a través del siguiente argumento:

  1. ¿Es posible encontrar un árbol de decisión en variables en el tiempo n log s , donde s es el árbol de decisión más pequeño consistente con ejemplos provenientes de una distribución (modelo PAC). ( Blum '92 ) nnlogss
  2. Suponiendo por alguna ε < 1 , no podemos PAC aprender de tamaño s árboles de decisión según el tamaño s k árboles de decisión para cualquier k 0 . ( Alekhnovich et al. '07 )NPDTIME(2nϵ)ϵ<1sskk0

Estos dos resultados parecen implicar un resultado de dureza para su problema. Por un lado (1), podemos encontrar un gran árbol de decisión; por otro lado (2), no deberíamos poder minimizarlo para obtener un equivalente "pequeño", de tamaño , incluso cuando exista uno de tamaño s .sks

Lev Reyzin
fuente
(Encontré su respuesta de esta respuesta , que se publicó hace menos de una hora).Parece que " " se puede reemplazar con "positivo ϵ , ya que al disminuir ϵ, el lado derecho de la contención es más pequeño .ϵ<1ϵϵ Además, ¿en qué parte del documento se muestra 2.?
Vea el punto # 2 en el resumen aquí: investigcher.watson.ibm.com/researcher/files/us-vitaly/…
Lev Reyzin
(viniendo de la misma respuesta que Ricky Demer) ¿podría detallar un poco más cómo obtener la "respuesta 3" de los puntos 1. y 2.? No estoy muy familiarizado con el aprendizaje de la teoría y me resulta difícil conectar las partes ...
Marc
Este problema de coherencia y capacidad de aprendizaje están estrechamente relacionados a través de la maquinilla de afeitar de Occam. La idea es que si puede encontrar una función consistente de un conjunto pequeño, puede tener éxito en el aprendizaje PAC. Por lo tanto, un resultado de dureza de aprendizaje implica un resultado de "dureza de consistencia". No estoy seguro de cuánto más puedo explicar en un comentario ...
Lev Reyzin
Por lo que yo entiendo, el algoritmo evocado para 1. no se ejecuta a tiempo que sería necesario para contradecir a 2. (el resultado preciso en el artículo si lo obtuve correctamente) dice que no existe un algoritmo de aprendizaje polytime para árboles de decisión). Por lo tanto, puede haber un problema con su argumentación. Poly(n,s)
Marc