Caracterización combinatoria del aprendizaje exacto con consultas de membresía

Editar: como no he recibido ninguna respuesta / comentario en una semana, me gustaría agregar que estoy feliz de escuchar algo sobre el problema. No trabajo en el área, así que aunque sea una simple observación, puede que no lo sepa. ¡Incluso un comentario como "Trabajo en el área, pero no he visto una caracterización como esta" sería útil!

Antecedentes:

Existen varios modelos de aprendizaje bien estudiados en la teoría del aprendizaje (p. Ej., Aprendizaje PAC, aprendizaje en línea, aprendizaje exacto con consultas de membresía / equivalencia).

Por ejemplo, en el aprendizaje PAC, la complejidad de la muestra de una clase de concepto tiene una buena caracterización combinatoria en términos de la dimensión VC de la clase. Entonces, si queremos aprender una clase con precisión y confianza constantes, esto se puede hacer con muestras , donde d es la dimensión VC. (Tenga en cuenta que estamos hablando de la complejidad de la muestra, no de la complejidad del tiempo). También hay una caracterización más refinada en términos de precisión y confianza. Del mismo modo, el modelo de aprendizaje en línea con errores tiene una buena caracterización combinatoria.$\Theta(d)$$d$

Pregunta:

Quiero saber si se conoce un resultado similar para el modelo de aprendizaje exacto con consultas de membresía. El modelo se define de la siguiente manera: tenemos acceso a un cuadro negro que en la entrada le da f ( x ) . Sabemos f viene de alguna clase de concepto C . Queremos determinar f con la menor cantidad de consultas posible.$x$$f(x)$$f$$C$$f$

¿Existe un parámetro combinatorio de una clase de concepto que caracterice el número de consultas necesarias para aprender un concepto en el modelo de aprendizaje exacto con consultas de membresía?$C$

Lo que yo sé:

La mejor caracterización que he encontrado está en este artículo de Servedio y Gortler , usando un parámetro que atribuyen a Bshouty, Cleve, Gavaldà, Kannan y Tamon . Definen un parámetro combinatorio llamado , donde C es la clase de concepto, que tiene las siguientes propiedades. (Deje que Q C sea ​​el número óptimo de consultas necesarias para aprender C en este modelo).$\gamma^C$$C$$Q_C$$C$

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

Esta caracterización es casi estricta. Sin embargo, podría haber una brecha cuadrática entre los límites superior e inferior. Por ejemplo si , entonces el límite inferior es Ω ( k ) , pero el límite superior es O ( k 2 ) . (También creo que esta brecha es alcanzable, es decir, existe una clase de concepto para la cual los límites inferiores son Ω ( k ) , pero el límite superior es O ( k 2 ) .)$1/\gamma^C = \log |C| = k$$\Omega(k)$$O(k^2)$$\Omega(k)$$O(k^2)$

Para llevar a casa el punto del ejemplo de alce anónimo, considere la clase de concepto que consiste en funciones que generan 1 en solo un punto en {0,1} ^ n. La clase es de tamaño 2 ^ n, y se necesitan 2 ^ n consultas en el peor de los casos. Eche un vistazo a la Dimensión de enseñanza en el peor de los casos (Goldman & Schapire) que proporciona algo similar a lo que está buscando.

No sé de tal caracterización. Sin embargo, vale la pena señalar que para casi cualquier clase de concepto, uno necesita consultar todos los puntos. Para ver esto, considere la clase de concepto que consiste en todos los vectores booleanos n-dimensionales con peso de Hamming 1. Esta clase de concepto obviamente requiere n consultas para aprender, que es igual a su cardinalidad. Probablemente pueda generalizar esta observación para obtener que casi cualquier clase de concepto también requiere realizar todas las consultas.

Sospecharía que dada una clase de concepto C como entrada, es NP-difícil determinar la complejidad de aprender exactamente la clase de concepto con consultas de membresía, o incluso aproximarla para decir una constante. Esto daría alguna indicación de que no existe una caracterización combinatoria "buena". Si desea probar un resultado de dureza NP así, pero intente y fracase, no dude en publicar aquí y veré si puedo resolverlo (tengo algunas ideas).

Aunque otros han señalado la respuesta. Pensé que podría hacerlo autónomo y mostrar por qué la dimensión de enseñanza es la respuesta.

$C$$X$$S\subseteq X$$f$$f$$C$$S$

$\mathcal{T}(f)$$f$$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$$f$$_{min}(f)$$\mathcal{T}(f)$$(C)=$$_{f\in C}$$(f,C)$$C$

$f$$(f,C)$$_{min}(f)$$(C)$$f$