Learning automata with help.

Abstract

Analitzem i proposem diverses versions millorades d’algorismes existents d'aprenentatge d’autòmats finits deterministes. Les nostres millores pertanyen a la categoria d'aprenentatge amb ajuda, amb l'objectiu d'accelerar o influir en la qualitat del procés d'aprenentatge. Una part considerable del nostre treball es basa en un enfocament pràctic; per a cada algorisme que tractem, hi ha resultats comparatius obtinguts després de la implementació i posada a prova dels processos d'aprenentatge en conjunts d'autòmats generats aleatòriament. Després de fer un gran nombre d’experiments, presentem gràfics i dades numèriques amb els resultats comparats que hem obtingut.

Estudiem algorismes pertanyents a dos models diferents d'aprenentatge: actiu i passiu. Un augment del nombre de símbols de sortida permet un nombre reduït de preguntes; una orientació al llarg del procés d'aprenentatge dóna una única resposta per a diverses preguntes; la millora de l'estructura d'aprenentatge permet una millor exploració de l'entorn d'aprenentatge.

En el marc de l'aprenentatge actiu, un algorisme d'aprenentatge amb preguntes modificades i amb un etiquetatge útil no trivial és capaç d'aprendre autòmats sense contraexemples.

Es revisen les preguntes de correcció definint-les com un tipus particular d'etiquetatge. Introduïm correccions minimals, maximals i a l'atzar.

Un algorisme clàssic aprèn autòmats típics amb recorreguts aleatòries dins del marc d'aprenentatge passiu en línia. Per l'algorisme original, no podem estimar el nombre d'assaigs necessaris per aprendre completament un autòmat per alguns casos. Afegint transicions inverses al graf subjacent de l'autòmat, el recorregut aleatori actúa com un recorregut aleatori en un graf no dirigit. L'avantatge és que, per a aquests grafs, hi ha un límit superior polinòmic per al temps de cobertura. El nou algorisme és encara un algorisme eficient amb un límit superior polinòmic pel nombre d'errors per defecte i el nombre d'assaigs.

Analizamos y proponemos varias versiones mejoradas de los algoritmos de aprendizaje existentes para autómatas finitos deterministas. Nuestras mejoras pertenecen a la categoría de aprendizaje com ayuda, con el objetivo de acelerar, o influir sobre la calidad del proceso de aprendizaje. Una parte considerable de nuestro trabajo se basa en un enfoque práctico; para cada algoritmo que se presenta, existen resultados comparativos obtenidos después de la implementación y puesta a prueba de los procesos de aprendizaje en conjuntos de autómatas generados aleatoriamente. Después de muchos experimentos, presentamos gráficos y datos numéricos con los resultados comparados que hemos obtenido .

Estudiamos algoritmos pertenecientes a dos modelos diferentes de aprendizaje: activo y pasivo. Un aumento del número de símbolos de salida permite un número reducido de consultas; una orientación parcial a lo largo del camino de aprendizaje da los resultados de varias consultas como uno solo; la mejora de la estructura de aprendizaje permite una mejor exploración del entorno de aprendizaje.

En el marco del aprendizaje activo, un algoritmo de aprendizaje com consulta modificada y dotado de un etiquetado de ayuda no trivial es capaz de aprender autómatas sin contraejemplos.

Se revisan las consultas de corrección definiéndolas como tipos particulares de etiquetado. Introducimos correcciones minimales, maximales y al azar.

Un algoritmo clásico aprende autómatas típicos de recorridos aleatorios en el marco del aprendizaje pasivo en línea. Para el algoritmo original, no podemos estimar el número de intentos necesarios para aprender completamente el autómata para algunos casos. Añadiendo transiciones inversas al grafo subyacente del autómata, el recorrido aleatorio actúa como un recorrido aleatorio en un grafo no dirigido. La ventaja es que, para estos grafos, existe un límite superior polinómico para el tiempo de cobertura. El nuevo algoritmo es todavía un algoritmo eficiente con límites superiores polinómicos para el número de errores por defecto y el número de intentos.

We analyze and propose several enhanced versions of existing learning algorithms for deterministic finite automata. Our improvements belong to the category of helpful learning, aiming to speed up, or to influence the quality of the learning process. A considerable part of our work is based on a practical approach; for each algorithm we discuss, there are comparative results, obtained after the implementation and testing of the learning processes on sets of randomly generated automata. After extended experiments, we present graphs and numerical data with the comparative results that we obtained.

We study algorithms belonging to two different learning models: active and passive. An increased number of output symbols allows a reduced number of queries; some partial guidance along the learning path gives the results of several queries as a single one; enhancing the learning structure permits a better exploration of the learning environment.

In the active learning framework, a modified query learning algorithm benefiting by a nontrivial helpful labeling is able to learn automata without counterexamples.

We review the correction queries defining them as particular types of labeling. We introduce minimal corrections, maximal corrections, and random corrections.

A classic algorithm learns typical automata from random walks in the online passive learning framework. For the original algorithm, we cannot estimate the number of trials needed to learn completely a target automaton for some cases. Adding inverse transitions to the underlying graph of the target automaton, the random walk acts as a random walk on an undirected graph. The advantage is, that for such graphs, there exists a polynomial upper bound for the cover time. The new algorithm is still an efficient algorithm with a polynomial upper bound for the number of default mistakes and the number of trials.