Modelo de árbol de decisión

Los árboles de decisión a menudo se emplean para comprender los algoritmos de ordenamiento y otros problemas similares; esto fue hecho por primera vez por Ford y Johnson.^[1]

Por ejemplo, muchos algoritmos de ordenamiento son ordenamientos por comparación, lo que significa que solo obtienen información sobre una secuencia de entrada. ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ a través de comparaciones locales: probando si ${\displaystyle x_{i}<x_{j}}$, ${\displaystyle x_{i}=x_{j}}$, o ${\displaystyle x_{i}>x_{j}}$ . Suponiendo que los elementos a clasificar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es ${\displaystyle x_{i}>x_{j}}$ ?

Estos algoritmos se pueden modelar como árboles de decisión binarios, donde las consultas son comparaciones: un nodo interno corresponde a una consulta y los hijos del nodo corresponden a la siguiente consulta cuando la respuesta a la pregunta es sí o no. Para los nodos hoja, el resultado corresponde a una permutación ${\displaystyle \pi }$ que describe cómo se codificó la secuencia de entrada de la lista completa de elementos ordenados. (El inverso de esta permutación, ${\displaystyle \pi ^{-1}}$, reordena la secuencia de entrada. )

Se puede mostrar que los ordenamientos de comparación deben usar ${\displaystyle \Omega (n\log(n))}$ comparaciones a través de un argumento simple: para que un algoritmo sea correcto, debe poder generar todas las permutaciones posibles de ${\displaystyle n}$ elementos; de lo contrario, el algoritmo fallaría para esa permutación particular como entrada. Entonces, su árbol de decisión correspondiente debe tener al menos tantas hojas como permutaciones, es decir, ${\displaystyle n!}$ hojas. Cualquier árbol binario con al menos ${\displaystyle n!}$ hojas tendrá una profundidad de al menos ${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$, por lo que este es un límite inferior en el tiempo de ejecución de un algoritmo de ordenamiento por comparación. En este caso, la existencia de numerosos algoritmos de ordenamiento por comparación que tienen esta complejidad de tiempo, como ordenamiento por mezcla (mergesort) y heapsort, demuestra que la cuota es rígida.^{[2] : 91}

Este argumento no utiliza nada acerca del tipo de consulta, por lo que, de hecho, demuestra una cuota inferior para cualquier algoritmo de ordenamiento que pueda modelarse como un árbol de decisión binario. En esencia, esta es una reformulación del argumento en teoría de la información de que un algoritmo de clasificación correcto debe aprender al menos ${\displaystyle \log _{2}(n!)}$ bits de información sobre la secuencia de entrada. Como resultado, esto también funciona para árboles de decisión aleatorios.

Otras cuotas inferiores para el modelo de árbol de decisión utilizan que la consulta es una comparación. Por ejemplo, considera la tarea de usar solo comparaciones para encontrar el número más pequeño entre ${\displaystyle n}$ números. Antes de que se pueda determinar el número más pequeño, todos los números excepto el más pequeño deben "perder" (comparar mayor) en al menos una comparación. Entonces, se necesita al menos ${\displaystyle n-1}$ comparaciones para encontrar el mínimo. (El argumento teórico de la información aquí solo da una cuota inferior de ${\displaystyle \log(n)}$ . ) Un argumento similar funciona para las cuotas inferiores generales para calcular estadísticos de orden .^{[2] : 214}

Los árboles de decisión lineales generalizan los árboles de decisión de comparación anteriores para computar funciones que toman vectores reales ${\displaystyle x\in \mathbb {R} ^{n}}$ como entradas. Las pruebas en árboles de decisión lineales son funciones lineales: para una elección particular de números reales ${\displaystyle a_{0},\dots ,a_{n}}$, emite el signo de ${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$ . (Los algoritmos en este modelo solo pueden depender del signo de la salida. ) Los árboles de comparación son árboles de decisión lineales, porque la comparación entre ${\displaystyle x_{i}}$ y ${\displaystyle x_{j}}$ corresponde a la función lineal ${\displaystyle x_{i}-x_{j}}$ . Por su definición, los árboles de decisión lineales solo pueden especificar funciones ${\displaystyle f}$ cuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios.

Los árboles de decisión algebraicos son una generalización de los árboles de decisión lineales que permiten que las funciones de prueba sean polinomios de grado ${\displaystyle d}$ . Geométricamente, el espacio se divide en conjuntos semialgebráicos (una generalización del hiperplano).

Estos modelos de árboles de decisión, definidos por Rabin^[3] y Reingold,^[4] se utilizan a menudo para demostrar cuotas inferiores en geometría computacional .^[5] Por ejemplo, Ben-Or demostró que la unicidad de los elementos (la tarea de calcular ${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$, dónde ${\displaystyle f(x)}$ es 0 si y solo si existen coordenadas distintas ${\displaystyle i,j}$ tal que ${\displaystyle x_{i}=x_{j}}$ ) requiere un árbol de decisión algebraico de profundidad ${\displaystyle \Omega (n\log(n))}$ .^[6] Esto fue mostrado por primera vez para los modelos de decisión lineal por Dobkin y Lipton.^[7] También muestran una cuota inferior de ${\displaystyle n^{2}}$ para árboles de decisión lineales en el problema de la mochila, generalizado a árboles de decisión algebraicos por Steele y Yao.^[8]

Para árboles de decisión Booleana, la tarea es calcular el valor de una función booleana de ${\displaystyle n}$ bits ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ para una entrada ${\displaystyle x\in \{0,1\}^{n}}$ . Las consultas corresponden a leer un bit de la entrada, ${\displaystyle x_{i}}$, y la salida es ${\displaystyle f(x)}$ . Cada consulta puede depender de las consultas anteriores. Son muchos los tipos de modelos computacionales que utilizan árboles de decisión que se podrían considerar, admitiendo múltiples nociones de complejidad, denominadas medidas de complejidad .

Si la salida de un árbol de decisión es ${\displaystyle f(x)}$, para todos ${\displaystyle x\in \{0,1\}^{n}}$, se dice que el árbol de decisión "calcula" ${\displaystyle f}$ . La profundidad de un árbol es el número máximo de consultas que pueden ocurrir antes de que se alcance una hoja y se obtenga un resultado. ${\displaystyle D(f)}$, la complejidad del árbol de decisión determinista de ${\displaystyle f}$ es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan ${\displaystyle f}$ .

Una forma de definir un árbol de decisión aleatorio es agregando nodos adicionales al árbol, cada uno controlado por una probabilidad ${\displaystyle p_{i}}$ . Otra definición equivalente lo construye como una distribución sobre árboles de decisión deterministas. Con base en esta segunda definición, la complejidad del árbol aleatorio se define como la mayor profundidad entre todos los árboles en el soporte de la distribución subyacente. ${\displaystyle R_{2}(f)}$ se define como la complejidad del árbol de decisión aleatorio de menor profundidad cuyo resultado es ${\displaystyle f(x)}$ con probabilidad al menos ${\displaystyle 2/3}$ para todos ${\displaystyle x\in \{0,1\}^{n}}$ (es decir, con error de dos colas acotado).

${\displaystyle R_{2}(f)}$ se conoce como la complejidad del árbol de decisión aleatorio de Monte Carlo, porque se permite que el resultado sea incorrecto con un error de dos colas acotado. La complejidad del árbol de decisión de Las Vegas ${\displaystyle R_{0}(f)}$ mide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, tiene cero errores). También hay una versión de error acotado unilateral que se denota por ${\displaystyle R_{1}(f)}$ .

La complejidad del árbol de decisión no determinista de una función se conoce más comúnmente como la complejidad del certificado de esa función. Mide la cantidad de bits de entrada que un algoritmo no determinista necesitaría consultar para evaluar la función con certeza.

Formalmente, la complejidad del certificado de ${\displaystyle f}$ a ${\displaystyle x}$ es el tamaño del subconjunto más pequeño de índices ${\displaystyle S\subset [n]}$ tal que, por todo ${\displaystyle y\in \{0,1\}^{n}}$, si ${\displaystyle y_{i}=x_{i}}$ para todos ${\displaystyle i\in S}$, después ${\displaystyle f(y)=f(x)}$ . La complejidad del certificado de ${\displaystyle f}$ es la complejidad máxima del certificado sobre todos ${\displaystyle x}$ . La noción análoga en la que solo se requiere que el verificador sea correcto con 2/3 de probabilidad se denota ${\displaystyle RC(f)}$ .

La complejidad del árbol de decisión cuántico ${\displaystyle Q_{2}(f)}$ es la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado ${\displaystyle f(x)}$ con probabilidad al menos ${\displaystyle 2/3}$ para todo ${\displaystyle x\in \{0,1\}^{n}}$ . Otra cantidad, denominada ${\displaystyle Q_{E}(f)}$, está definida como la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado ${\displaystyle f(x)}$ con probabilidad 1 en todos los casos (es decir, calcula ${\displaystyle f}$ exactamente). ${\displaystyle Q_{2}(f)}$ y ${\displaystyle Q_{E}(f)}$ se conocen más comúnmente como complejidades de consulta cuántica, porque la definición directa de un árbol de decisión cuántica es más complicada que en el caso clásico. Similar al caso aleatorio, definimos ${\displaystyle Q_{0}(f)}$ y ${\displaystyle Q_{1}(f)}$ .

Estas nociones suelen estar acotadas por las nociones de grado y grado aproximado. El grado de ${\displaystyle f}$, denotado ${\displaystyle \deg(f)}$, es el grado más pequeño de cualquier polinomio ${\displaystyle p}$ que satisface ${\displaystyle f(x)=p(x)}$ para toda ${\displaystyle x\in \{0,1\}^{n}}$ . El grado aproximado de ${\displaystyle f}$, denotado ${\displaystyle {\widetilde {\deg }}(f)}$, es el grado más pequeño de cualquier polinomio ${\displaystyle p}$ que satisface ${\displaystyle p(x)\in [0,1/3]}$ cuando ${\displaystyle f(x)=0}$ y ${\displaystyle p(x)\in [2/3,1]}$ cuando ${\displaystyle f(x)=1}$ .

Beals et al. estableció que ${\displaystyle Q_{0}(f)\geq {\frac {\deg(f)}{2}}}$ y ${\displaystyle Q_{2}(f)\geq {\frac {{\widetilde {\deg }}(f)}{2}}}$ .^[9]