Muestras características

Concepto en el aprendizaje automático

Las muestras características son un concepto en el campo de la inferencia gramatical , relacionado con el aprendizaje pasivo . En el aprendizaje pasivo, a un algoritmo de inferencia se le da un conjunto de pares de cadenas y etiquetas , y devuelve una representación que es consistente con . Las muestras características consideran el escenario en el que el objetivo no es solo encontrar una representación consistente con , sino encontrar una representación que reconozca un idioma de destino específico. ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

Una muestra característica del lenguaje es un conjunto de pares de la forma donde: ${\displaystyle L}$ ${\displaystyle (s,l(s))}$

1. ${\displaystyle l(s)=1}$Si y sólo si ${\displaystyle s\in L}$
2. ${\displaystyle l(s)=-1}$Si y sólo si ${\displaystyle s\notin L}$

Dada la muestra característica , la salida de es una representación , por ejemplo un autómata, que reconoce . ${\displaystyle S}$ ${\displaystyle I}$ ${\displaystyle R}$ ${\displaystyle L}$

Definición formal

El paradigma de aprendizaje asociado a las muestras características

Hay tres entidades en el paradigma de aprendizaje conectadas a muestras características: el adversario, el profesor y el algoritmo de inferencia.

Dada una clase de lenguajes y una clase de representaciones para los lenguajes , el paradigma es el siguiente: ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathbb {R} }$

• El adversario selecciona un idioma y se lo comunica al profesor. ${\displaystyle A}$ ${\displaystyle L\in \mathbb {C} }$
• Luego, el profesor calcula un conjunto de cadenas y las etiqueta correctamente según , tratando de asegurarse de que el algoritmo de inferencia calcule ${\displaystyle T}$ ${\displaystyle L}$ ${\displaystyle L}$
• El adversario puede añadir palabras correctamente etiquetadas al conjunto para confundir al algoritmo de inferencia.
• El algoritmo de inferencia obtiene la muestra y calcula una representación consistente con la muestra. ${\displaystyle I}$ ${\displaystyle R\in \mathbb {R} }$

El objetivo es que cuando el algoritmo de inferencia recibe una muestra característica de un idioma , o una muestra que subsume una muestra característica de , devuelva una representación que reconozca exactamente el idioma . ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

Muestra

La muestra es un conjunto de pares de la forma tal que ${\displaystyle S}$ ${\displaystyle (s,l(s))}$ ${\displaystyle l(s)\in \{-1,1\}}$

Muestra consistente con un idioma

Decimos que una muestra es consistente con el lenguaje si para cada par en : ${\displaystyle S}$ ${\displaystyle L}$ ${\displaystyle (s,l(s))}$ ${\displaystyle S}$

1. ${\displaystyle l(s)=1{\text{ if and only if }}s\in L}$
2. ${\displaystyle l(s)=-1{\text{ if and only if }}s\notin L}$

Muestra característica

Dado un algoritmo de inferencia y un lenguaje , una muestra que es consistente con se denomina muestra característica de si : ${\displaystyle I}$ ${\displaystyle L}$ ${\displaystyle S}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle I}$

• ${\displaystyle I}$La salida de es una representación que reconoce . ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle L}$
• Para cada muestra que es consistente con y también cumple , la salida de es una representación que reconoce . ${\displaystyle D}$ ${\displaystyle L}$ ${\displaystyle S\subseteq D}$ ${\displaystyle I}$ ${\displaystyle D}$ ${\displaystyle R}$ ${\displaystyle L}$

Se dice que una clase de lenguas tiene muestras características si cada una tiene una muestra característica. ${\displaystyle \mathbb {C} }$ ${\displaystyle L\in \mathbb {C} }$

Teoremas relacionados

Teorema

Si la equivalencia es indecidible para una clase de cardinalidad mayor que 1, entonces no tiene muestras características. ^[1] ${\textstyle \mathbb {C} }$ ${\textstyle \Sigma }$ ${\textstyle \mathbb {C} }$

Prueba

Dada una clase de representaciones tales que la equivalencia es indecidible, para cada polinomio y cada , existen dos representaciones y de tamaños acotados por , que reconocen diferentes lenguajes pero son inseparables por cualquier cadena de tamaño acotado por . Suponiendo que este no es el caso, podemos decidir si y son equivalentes simulando su ejecución en todas las cadenas de tamaño menor que , contradiciendo el supuesto de que la equivalencia es indecidible. ${\textstyle \mathbb {C} }$ ${\displaystyle p(x)}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle n}$ ${\displaystyle p(n)}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle p(n)}$

Teorema

Si es una muestra característica de y también es consistente con , entonces cada muestra característica de , es inconsistente con . ^[1] ${\displaystyle S_{1}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$

Prueba

Dada una clase que tiene muestras características, sean y representaciones que reconocen y respectivamente. Bajo el supuesto de que existe una muestra característica para , que también es consistente con , asumiremos falsamente que existe una muestra característica para , que es consistente con . Por la definición de muestra característica, el algoritmo de inferencia debe devolver una representación que reconozca el lenguaje si se le da una muestra que subsume la muestra característica en sí. Pero para la muestra , la respuesta del algoritmo de inferencia necesita reconocer tanto y , en contradicción. ${\textstyle \mathbb {C} }$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle S_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle S_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle I}$ ${\displaystyle S_{1}\cup S_{2}}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$

Teorema

Si una clase se puede aprender polinomialmente mediante consultas basadas en ejemplos, se puede aprender con muestras características. ^[2]

Clases caracterizables polinómicamente

Lenguajes regulares

La prueba de que los DFA se pueden aprender usando muestras características se basa en el hecho de que cada lenguaje regular tiene un número finito de clases de equivalencia con respecto a la relación de congruencia correcta (donde para si y solo si ). Nótese que si , no son congruentes con respecto a , existe una cadena tal que pero o viceversa, esta cadena se llama sufijo separador. ^[3] ${\displaystyle \sim _{L}}$ ${\displaystyle x\sim _{L}y}$ ${\displaystyle x,y\in \Sigma ^{*}}$ ${\displaystyle \forall z\in \Sigma ^{*}:xz\in L\leftrightarrow yz\in L}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \sim _{L}}$ ${\displaystyle z}$ ${\displaystyle xz\in L}$ ${\displaystyle yz\notin L}$

Construcción de una muestra característica

La construcción de una muestra característica para un idioma por parte del profesor se realiza de la siguiente manera. En primer lugar, al ejecutar una búsqueda en profundidad en un autómata determinista que reconoce , a partir de su estado inicial, obtenemos un conjunto cerrado de sufijos de palabras, , ordenados en orden shortlex. A partir del hecho anterior, sabemos que para cada dos estados en el autómata, existe un sufijo separador que separa entre cada dos cadenas que la serie de en ellas termina en los respectivos estados. Nos referimos al conjunto de sufijos separadores como . El conjunto etiquetado (muestra) de palabras que el profesor le da al adversario es donde es la etiqueta correcta de (ya sea que esté en o no). Podemos suponer que . ${\displaystyle L}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle W}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle \{(w,l(w))|w\in W\cdot S\cup W\cdot \Sigma \cdot S\}}$ ${\displaystyle l(w)}$ ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle \epsilon \in S}$

Construcción de un autómata determinista

Dada la muestra del adversario , la construcción del autómata por el algoritmo de inferencia comienza con la definición de y , que son el conjunto de prefijos y sufijos de respectivamente. Ahora el algoritmo construye una matriz donde los elementos de función son las filas, ordenadas por el orden shortlex, y los elementos de función son las columnas, ordenadas por el orden shortlex. A continuación, las celdas de la matriz se rellenan de la siguiente manera para el prefijo y el sufijo : ${\displaystyle W}$ ${\displaystyle I}$ ${\displaystyle P={\text{prefix}}(W)}$ ${\displaystyle S={\text{suffix}}(W)}$ ${\displaystyle W}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle p_{i}}$ ${\displaystyle s_{j}}$

1. Si ${\displaystyle p_{i}s_{j}\in W\rightarrow M_{ij}=l(p_{i}s_{j})}$
2. demás, ${\displaystyle M_{ij}=0}$

Ahora, decimos que las filas y son distinguibles si existe un índice tal que . La siguiente etapa del algoritmo de inferencia es construir el conjunto de filas distinguibles en , inicializando con e iterando desde la primera fila de hacia abajo y haciendo lo siguiente para la fila : ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle j}$ ${\displaystyle M_{ij}=-1\times M_{tj}}$ ${\displaystyle Q}$ ${\displaystyle M}$ ${\displaystyle Q}$ ${\displaystyle \epsilon }$ ${\displaystyle M}$ ${\displaystyle r_{i}}$

1. Si es distinguible de todos los elementos en , agréguelo a ${\displaystyle r_{i}}$ ${\displaystyle Q}$ ${\displaystyle Q}$
2. De lo contrario, páselo a la siguiente fila.

De la manera en que el profesor construyó la muestra que le pasó al adversario, sabemos que para cada y cada , la fila existe en , y de la construcción de , existe una fila tal que y son indistinguibles. El autómata de salida se definirá de la siguiente manera: ${\displaystyle s\in Q}$ ${\displaystyle \sigma \in \Sigma }$ ${\displaystyle s\sigma }$ ${\displaystyle M}$ ${\displaystyle Q}$ ${\displaystyle s'\in Q}$ ${\displaystyle s'}$ ${\displaystyle s\sigma }$

• El conjunto de estados es . ${\displaystyle Q}$
• El estado inicial es el estado correspondiente a la fila . ${\displaystyle \epsilon \in Q}$
• Los estados de aceptación son el conjunto . ${\displaystyle \{s\in Q|{\text{ }}l(s)=1\}}$
• Se definirá la función de transiciones , donde es el elemento en que es indistinguible de . ${\displaystyle \delta (s,\sigma )=s'}$ ${\displaystyle s'}$ ${\displaystyle Q}$ ${\displaystyle s\sigma }$

Otras clases caracterizables polinomialmente

• Clase de lenguajes reconocibles por autómatas de multiplicidad ^[4]
• Clase de lenguajes reconocibles por autómatas de árbol ^[5]
• Clase de lenguajes reconocibles por autómatas de árboles de multiplicidad ^[6]
• Clase de lenguajes reconocibles por los autómatas reticulares completamente ordenados ^[7]
• Clase de lenguajes reconocibles por autómatas de un solo contador visible ^[8]
• Clase de lenguajes regulares omega completamente informativos ^{[9] [10]}

Clases caracterizables no polinomialmente

Existen algunas clases que no tienen muestras características de tamaño polinómico. Por ejemplo, a partir del primer teorema del segmento Teoremas relacionados, se ha demostrado que las siguientes clases de lenguajes no tienen muestras características de tamaño polinómico:

• ${\displaystyle \mathbb {CFG} }$- La clase de gramáticas libres de contexto Lenguajes con cardinalidad mayor que ^[1] ${\displaystyle \Sigma }$ ${\displaystyle 1}$
• ${\displaystyle \mathbb {LING} }$- La clase de lenguajes de gramática lineal con cardinalidad mayor que ^[1] ${\displaystyle \Sigma }$ ${\displaystyle 1}$
• ${\displaystyle \mathbb {SDG} }$- La clase de gramáticas deterministas simples Lenguajes ^[1]
• ${\displaystyle \mathbb {NFA} }$- La clase de autómatas finitos no deterministas Lenguajes ^[1]

Relaciones con otros paradigmas de aprendizaje

Las clases de representaciones que tienen muestras características se relacionan con los siguientes paradigmas de aprendizaje:

Clase de idiomas semi-poli enseñables

Una clase de representación es semi-poli- enseñable si existen 3 polinomios , un profesor y un algoritmo de inferencia , de manera que para cualquier adversario se cumple lo siguiente: ^[2] ${\displaystyle \mathbb {C} }$ ${\displaystyle T/L}$ ${\displaystyle p,q,r}$ ${\displaystyle T}$ ${\displaystyle I}$ ${\displaystyle A}$

• ${\displaystyle A}$Selecciona una representación de tamaño de ${\displaystyle R}$ ${\displaystyle n}$ ${\displaystyle \mathbb {C} }$
• ${\displaystyle T}$calcula una muestra que es consistente con el lenguaje que reconoce, de tamaño limitado por y las cadenas en la muestra limitadas por longitud ${\displaystyle R}$ ${\displaystyle p(n)}$ ${\displaystyle q(n)}$
• ${\displaystyle A}$agrega cadenas etiquetadas correctamente a la muestra calculada por , lo que hace que la nueva muestra tenga un tamaño ${\displaystyle T}$ ${\displaystyle m}$
• ${\displaystyle I}$luego calcula una representación equivalente a en un tiempo limitado por ${\displaystyle R}$ ${\displaystyle r(m)}$

La clase de lenguajes en la que existe un algoritmo polinomial que, dada una muestra, devuelve una representación consistente con la muestra se denomina consistencia fácil .

Lenguajes caracterizables polinomialmente

Dada una clase de representación y un conjunto de algoritmos de identificación para , es polinomialmente caracterizable para si alguna tiene una muestra característica de tamaño polinomial del tamaño de , , que para cada , la salida de en es . ${\displaystyle \mathbb {R} }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle R\in \mathbb {R} }$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle I\in {\mathcal {I}}}$ ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle R}$

Relaciones entre los paradigmas

Teorema

Una clase de consistencia fácil tiene muestras características si y sólo si es enseñable de manera semi-polivalente. ^[1] ${\displaystyle \mathbb {C} }$ ${\displaystyle T/L}$

Prueba

Suponiendo que tiene muestras características, entonces para cada representación , su muestra característica contiene las condiciones para la muestra calculada por el profesor, y la salida de en cada muestra es tal que es equivalente a la de la definición de muestra característica. ${\displaystyle \mathbb {C} }$ ${\displaystyle R\in \mathbb {C} }$ ${\displaystyle S}$ ${\displaystyle I}$ ${\displaystyle S'}$ ${\displaystyle S\subseteq S'}$ ${\displaystyle R}$

Suponiendo que es semi-poli enseñable, entonces para cada representación , la muestra calculada por el profesor es una muestra característica para . ${\displaystyle \mathbb {C} }$ ${\displaystyle T/L}$ ${\displaystyle R\in \mathbb {C} }$ ${\displaystyle S}$ ${\displaystyle R}$

Teorema

Si tiene una muestra característica, entonces es caracterizable polinomialmente. ^[1] ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathbb {C} }$

Prueba

Suponiendo falsamente que no es polinomialmente caracterizable, existen dos representaciones no equivalentes , con muestras características y respectivamente. A partir de la definición de muestras características, cualquier algoritmo de inferencia debe inferir de la muestra una representación compatible con y , en contradicción. ${\displaystyle \mathbb {C} }$ ${\displaystyle R_{1},R_{2}\in \mathbb {C} }$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle I}$ ${\displaystyle S_{1}\cup S_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$

Véase también

• Inducción gramatical
• Aprendizaje pasivo
• Inducción de lenguajes regulares
• Autómata finito determinista

Referencias

1. De La Higuera, Colin (1997). "[No se encontró título]". Aprendizaje automático . 27 (2): 125–138. doi :10.1023/A:1007353007695.
2. Goldman, Sally A.; Mathias, H. David (abril de 1996). "Enseñar a un alumno más inteligente". Revista de Ciencias de la Computación y de Sistemas . 52 (2): 255–267. doi :10.1006/jcss.1996.0020. ISSN  0022-0000.
3. Oncina, J.; García, P. (enero de 1992), Inferir lenguajes regulares en tiempo de actualización polinomial, Series in Machine Perception and Artificial Intelligence, vol. 1, WORLD SCIENTIFIC, pp. 49–61, doi :10.1142/9789812797902_0004, ISBN 978-981-02-0881-3, consultado el 21 de mayo de 2024
4. Beimel, Amós; Bergadano, Francesco; Bshouty, Nader H.; Kushilevitz, Eyal; Varricchio, Stefano (mayo de 2000). "Funciones de aprendizaje representadas como autómatas de multiplicidad". Revista de la ACM . 47 (3): 506–530. doi :10.1145/337244.337257. ISSN  0004-5411.
5. Burago, Andrey (1994). "Aprendizaje de gramáticas estructuralmente reversibles e independientes del contexto a partir de consultas y contraejemplos en tiempo polinomial". Actas de la séptima conferencia anual sobre teoría del aprendizaje computacional - COLT '94 . Nueva York, Nueva York, EE. UU.: ACM Press. pp. 140–146. doi :10.1145/180139.181075. ISBN 0-89791-655-7.
6. Habrard, Amaury; Oncina, Jose (2006), Sakakibara, Yasubumi; Kobayashi, Satoshi; Sato, Kengo; Nishino, Tetsuro (eds.), "Aprendizaje de autómatas de árboles de multiplicidad", Grammatical Inference: Algorithms and Applications , vol. 4201, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 268–280, doi :10.1007/11872436_22, ISBN 978-3-540-45264-5, consultado el 20 de mayo de 2024
7. Fisman, Dana; Saadon, Sagi (2022), "Aprendizaje y caracterización de autómatas reticulares completamente ordenados", Tecnología automatizada para verificación y análisis , Cham: Springer International Publishing, págs. 266–282, doi :10.1007/978-3-031-19992-9_17, ISBN 978-3-031-19991-2, consultado el 20 de mayo de 2024
8. Berman, Piotr; Roos, Robert (octubre de 1987). "Aprendizaje de lenguajes de un solo contador en tiempo polinomial". 28.º Simposio anual sobre fundamentos de la informática (SFCS 1987) . IEEE. págs. 61–67. doi :10.1109/sfcs.1987.36. ISBN. 0-8186-0807-2.
9. Angluin, Dana; Fisman, Dana (2022), Construcción de muestras características concisas para aceptores de lenguajes regulares omega, arXiv : 2209.09336 , doi :10.1007/978-3-319-11662-4_10
10. Angluin, Dana; Fisman, Dana; Shoval, Yaara (2020), "Identificación polinomial de autómatas $$\omega $$", Herramientas y algoritmos para la construcción y análisis de sistemas , Cham: Springer International Publishing, págs. 325–343, doi : 10.1007/978-3-030-45237-7_20 , ISBN 978-3-030-45236-0