La peor cantidad de preguntas necesarias para aprender un predicado monótono sobre un poset

Considere un poset finito sobre elementos, y un predicado monotónico desconocido sobre (es decir, para cualquier , , si y luego ) . Puedo evaluar proporcionando un nodo y descubriendo si P (x) se mantiene o no. Mi objetivo es determinar exactamente el conjunto de nodos x \ en X de forma tal que P (x) se mantenga, utilizando tan pocas evaluaciones de P$(X, \leq)$$n$$P$$X$$x$$y \in X$$P(x)$$x \leq y$$P(y)$$P$$x \in X$$P(x)$$x \in X$$P(x)$$P$como sea posible. (Puedo elegir mis consultas dependiendo de la respuesta de todas las consultas anteriores, no estoy obligado a planificar todas las consultas por adelantado).

Una estrategia $S$ sobre $(X, \leq)$ es una función que me dice, en función de las consultas que ejecuté hasta ahora y sus respuestas, qué nodo consultar y que garantiza eso en cualquier predicado $P$ , siguiendo la estrategia , Alcanzaré un estado en el que sé el valor de $P$ en todos los nodos. El tiempo de ejecución $r(S, P)$ de $S$ en un predicado $P$ es el número de consultas requeridas para conocer el valor de $P$ en todos los nodos. El peor tiempo de ejecución de $S$ es $wr(S) = \max_P r(S, P)$ . Una estrategia óptima $S'$ es tal que $wr(S') = \min_S wr(S)$ .

Mi pregunta es la siguiente: dado como entrada el poset $(X, \leq)$ , ¿cómo puedo determinar el peor tiempo de ejecución de las estrategias óptimas?

[Está claro que para un poset vacío se necesitarán $n$ consultas (necesitamos preguntar sobre cada nodo individual), y que para un orden total alrededor de $\lceil \log_2 n \rceil$ se necesitarán consultas (haciendo una búsqueda binaria para encontrar la frontera). Un resultado más general es el siguiente límite inferior teórico de la información: el número de opciones posibles para el predicado $P$ es el número $N_X$ de antichains de $(X, \leq)$ (porque hay un mapeo uno a uno entre predicados monotónicos y antichains interpretados como los elementos máximos de $P$ ), por lo tanto, dado que cada consulta nos da un poco de información, necesitaremos al menos $\lceil \log_2 N_X \rceil$consultas, sumando los dos casos anteriores. ¿Es estrictamente limitado o son algunos posets cuya estructura es tal que el aprendizaje puede requerir asintóticamente más consultas que el número de antichains?]

Esta no es una respuesta completa, pero es demasiado larga para ser un comentario.

Creo que encontré un ejemplo para el cual el enlace no está ajustado.$\lceil \log_2 N_X \rceil$

Considere el siguiente poset. El conjunto de bases es , y es más pequeño que para todo . Los otros pares son incomparables. (El diagrama de Hasse es de ciclos).a i b j i , j ∈ { 1 , 2 } $X=\{a_1, a_2, b_1, b_2\}$$a_i$$b_j$$i,j\in\{1,2\}$$4$

Permítanme identificar las propiedades monótonas con los trastornos del poset. Este poset tiene siete problemas: , , , , , , , y este poset tiene siete antichains ya que las antichains están en correspondencia uno a uno con los trastornos. Entonces, para este poset.{ b 1 } { b 2 } { b 1 , b 2 } { a 1 , b 1 , b 2 } { a 2 , b 1 , b 2 } { a 1 , a 2 , b 1 , b 2 } ⌈ log 2 N X ⌉ = ⌈ log 2 7 $\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$$\{a_1,a_2,b_1,b_2\}$$\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$

Ahora, por argumento adversario, mostraré que cualquier estrategia necesita al menos cuatro consultas (por lo que necesita consultar todos los elementos). Arreglemos una estrategia arbitraria.

Si la estrategia primero consulta , el adversario responde " no se cumple". Luego, nos quedan cinco posibilidades: , , , , . Por lo tanto, para determinar cuál es el caso, necesitamos al menos consultas más. En total, necesitamos cuatro consultas. El mismo argumento se aplica si la primera consulta es . P ( a 1 ) ∅ { b 1 } { b 2 } { b 1 , b 2 } { a 2 , b 1 , b 2 } ⌈ log 2 5 ⌉ = 3 a $a_1$$P(a_1)$$\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_2,b_1,b_2\}$$\lceil \log_2 5\rceil = 3$$a_2$

Si la estrategia primero consulta , entonces el adversario responde " espera". Luego, nos quedan cinco posibilidades: , , , , . Por lo tanto, necesitamos al menos tres consultas más como antes. En total, necesitamos cuatro consultas. El mismo argumento se aplica cuando la primera consulta es . P ( b 1 ) { b 1 } { b 1 , b 2 } { a 1 , b 1 , b 2 } { a 2 , b 1 , b 2 } { a 1 , a 2 , b 1 , b 2 } b $b_1$$P(b_1)$$\{b_1\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$$\{a_1,a_2,b_1,b_2\}$$b_2$

Si tomamos copias paralelas de este poset, entonces tiene antichains, y por lo tanto el límite propuesto es . Pero, dado que cada una de las copias necesita cuatro consultas, necesitamos al menos consultas.7 k ⌈ log 2 7 k ⌉ = 3 k 4 $k$$7^k$$\lceil \log_2 7^k \rceil = 3k$$4k$

Probablemente, hay un poset más grande con una brecha más grande. Pero este argumento solo puede mejorar el coeficiente.

Aquí, el problema parece ser una situación en la que ninguna consulta divide el espacio de búsqueda de manera uniforme. En tal caso, el adversario puede obligar a la mitad más grande a permanecer.

En su artículo, Cada Poset tiene un Elemento Central , Linial y Saks muestran (Teorema 1) que el número de consultas requeridas para resolver el problema de identificación ideal en un poset es como máximo , donde y es el número de ideales de . Lo que ellos llaman un "ideal" es en realidad un conjunto más bajo y hay una correspondencia obvia entre los predicados monótonos y el conjunto más bajo de los puntos en los que no se mantienen, además de su "problema de identificación" es identificar mediante consultas nodos al igual que en mi configuración, por lo que creo que están lidiando con el problema que me interesa y queK 0 log 2 i ( X ) K 0 = 1 / ( 2 - log 2 ( 1 + log 2 5 ) ) i ( X ) X i ( X ) = N $X$$K_0 \log_2 i(X)$$K_0 = 1/(2 - \log_2(1 + \log_2 5))$$i(X)$$X$$i(X) = N_X$.

Entonces, de acuerdo con su resultado, el límite inferior teórico de la información está ajustado a una constante multiplicativa relativamente pequeña. Entonces, esto básicamente resuelve la cuestión del número de preguntas requeridas, en función de y hasta una constante multiplicativa: está entre y .log 2 N X K 0 log 2 N $N_X$$\log_2 N_X$$K_0 \log_2 N_X$

Linial y Saks citan una comunicación personal de Shearer para decir que existen órdenes conocidas para las cuales podemos probar un límite inferior de para algunos que es un poco menos que (esto está en el espíritu de la respuesta de Yoshio Okamoto este enfoque por un valor menor de ).K 1 K 0 K $K_1 \log_2 N_X$$K_1$$K_0$$K_1$

Sin embargo, esto no responde completamente a mi pregunta de calcular el número de preguntas requeridas de , dado que calcular de es # P-completo , tengo la sensación de que hay pocas esperanzas. (Los comentarios sobre este punto son bienvenidos). Aún así, este resultado de Linial y Saks es esclarecedor.N X X$X$$N_X$$X$

Para el n-cubo booleano (o, de manera equivalente, para el poset ( 2 S , ⊆ ) de todos los subconjuntos de un conjunto de elementos n), la respuesta viene dada por los teoremas de Korobkov y Hansel (desde 1963 y 1966, respectivamente). El teorema de Hansel [1] establece que una función booleana monótona desconocida (es decir, un predicado monótono desconocido en este poset) puede aprenderse mediante un algoritmo determinista que hace como máximo consultas (es decir, preguntar$(\{0, 1\}^n, \leq)$$(2^S, \subseteq)$ ϕ(n)ϕ(n)-$\phi(n) = \binom{n}{\lfloor n/2 \rfloor} + \binom{n}{\lfloor n/2 \rfloor + 1}$$\phi(n)$preguntas en el peor de los casos). Este algoritmo coincide con el límite inferior del teorema de Korobkov [2], que dice que las consultas no son suficientes. (Por lo tanto, el algoritmo de Hansel es óptimo en el peor de los casos). Un algoritmo en ambas declaraciones se entiende como un árbol de decisión determinista.$\phi(n) - 1$

El logaritmo del número de antichains en es asintóticamente igual a , por lo que hay una brecha de factor constante entre y el rendimiento óptimo del algoritmo para este poset.($(\{0, 1\}^n, \le)$ logNXϕ(n)∼2 ($\binom{n}{\lfloor n/2 \rfloor} \sim 2^n / \sqrt{\pi n / 2}$$\log N_X$$\phi(n) \sim 2 \binom{n}{\lfloor n/2 \rfloor}$

Desafortunadamente, no he podido encontrar un buen tratamiento del algoritmo de Hansel en inglés disponible en la web. Se basa en un lema que divide el cubo cadenas con propiedades especiales. Se puede encontrar alguna descripción en [3]. Para el límite inferior, no conozco ninguna referencia a una descripción en inglés.$\phi(n)$

Como estoy familiarizado con estos resultados, puedo publicar una descripción en arXiv, si el tratamiento en el documento de Kovalerchuk no es suficiente.

Si no me equivoco mucho, ha habido intentos de generalizar el enfoque de Hansel, al menos al poset , donde es una cadena , aunque no puedo dar ninguna referencia de inmediato. Para el caso booleano, las personas también han investigado nociones de complejidad distintas del peor de los casos para este problema.( E k , ≤ ) 0 < 1 < … < k - $(E_k^n, \le)$$(E_k, \le)$$0 < 1 < \ldots < k - 1$

[1] G. Hansel, Sur le nombre des fonctions booléennes monotones de n variables. CR Acad. Sci. París, 262 (20), 1088-1090 (1966)

[2] VK Korobkov. Estimación del número de funciones monotónicas del álgebra de la lógica y de la complejidad del algoritmo para encontrar el conjunto resolvente para una función monotónica arbitraria del álgebra de la lógica. Matemáticas soviéticas. Doklady 4, 753-756 (1963) (traducción del ruso)

[3] B. Kovalerchuk, E. Triantaphyllou, AS Deshpande, E. Vityaev. Aprendizaje interactivo de funciones booleanas monótonas. Ciencias de la información 94 (1), 87-118 (1996) ( enlace )

[ NOTA: El siguiente argumento no parece funcionar, pero lo dejo aquí para que otros no cometan el mismo error / en caso de que alguien pueda solucionarlo. El problema es que un límite inferior exponencial en el aprendizaje / identificación de una función monótona, como se muestra a continuación, no necesariamente contradice un algoritmo polinomial incremental para el problema. Y es lo último lo que equivale a verificar la dualidad mutua de dos funciones monótonas en el tiempo poli.]

$\log N_X$$\log N_X$$X$$X$$\{1,...,n\}$$\subseteq$$M$$X$$\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$$\log N_X$$X$$\binom{n-1}{n/2} \approx 2^n$$2^n$

$2^n$

[1] Liviu Ilinca y Jeff Kahn. Contando antichains máximos y conjuntos independientes . arXiv: 1202.4427