Límites inferiores para aprender en la consulta de membresía y el modelo de contraejemplo

Dana Angluin ( 1987 ; pdf ) define un modelo de aprendizaje con consultas de membresía y consultas teóricas (contraejemplos de una función propuesta). Ella muestra que un lenguaje regular que está representado por un DFA mínimo de estados se puede aprender en tiempo polinómico (donde las funciones propuestas son DFA) con O ( m n 2 ) consultas de membresía y como máximo n - 1 consultas de teoría ( m es el tamaño del contraejemplo más grande proporcionado por el tutor). Desafortunadamente, ella no discute los límites inferiores.$n$$O(mn^2)$$n−1$$m$

Podemos generalizar ligeramente el modelo asumiendo un tutor mágico que pueda verificar la igualdad entre funciones arbitrarias y proporcionar contraejemplos si son diferentes. Luego podemos preguntar qué tan difícil es aprender clases más grandes que los idiomas normales. Estoy interesado en esta generalización y la restricción original a los idiomas regulares.

¿Hay algún límite inferior conocido en el número de consultas en el modelo de membresía y contraejemplo?

Estoy interesado en límites más bajos en el número de consultas de membresía, consultas teóricas o compensaciones entre los dos. Estoy interesado en los límites inferiores para cualquier clase de funciones, incluso para clases más complicadas que los lenguajes normales.

Si no hay límites inferiores: ¿Existen barreras conocidas para probar los límites inferiores de la consulta en este modelo?

Preguntas relacionadas

¿Hay mejoras en el algoritmo de Dana Angluin para aprender conjuntos regulares?

$NP \neq coNP$

$O(n)$$O(n^2+ n \log m)$

Una forma fácil de obtener límites inferiores es la teoría de la información. Puede averiguar cuántos objetivos distintos hay y cuántos bits le proporciona una consulta, etc. Estos límites superiores se acercan pero no están allí. También hay cuestiones en las que uno debe pensar acerca de cómo llegan los "contraejemplos" al alumno. Un contraejemplo bien elegido puede dar mucha información.

Actualización de la discusión anterior : Angluin y Dohrn aborda la cuestión de aprendizaje con ejemplos contrarios al azar en un artículo reciente .