Veröffentlichungen - niflheim.de

Abstract: We determine the complexity of learning problems for unary regular languages. We begin by investigating the minimum consistent dfa (resp. nfa) problem which is known not to be approximable within any polynomial, unless P = NP. For the case of unary dfa's, we exhibit an efficient algorithm. On the other hand, we show the intractability of the unary minimum consistent nfa problem but provide an efficient quadratic approximation for its optimization version.

The VC dimension for the class of languages accepted by unary dfa's with at most n states is computed as n + log n ± Θ(log log n), which (together with the efficient solution for the consistency problem) yields an efficient PAC learning algorithm for this class. We also show that there are no efficient PAC learning algorithms for the class of languages accepted by unary nfa's with at most n states, unless every problem in NP is solvable by a quasipolynomial time Monte-Carlo algorithm. Here we assume that nfa's with few states serve as hypotheses.

In the context of learning with equivalence queries, we consider the number of counterexamples required to learn a unary regular language that is accepted by a dfa with at most n states. When submitting dfa's with at most n^d states (d ≤ n) as queries, we show the upper bound O(n² ⁄ d) and the lower bound Ω((n² ln d) ⁄ (d (ln n)²)). If only prime cycle lengths ≤ n are allowed as queries, we prove that Θ(n² ⁄ ln n) counterxamples are necessary and sufficient.

Zusammenfassung: Wir untersuchen das algorithmische Lernen regulärer unärer Sprachen. Dabei heißt eine reguläre Sprache genau dann unär, wenn sie über einem Alphabet mit nur einem Buchstaben erklärt ist.Zuerst werden die bekannten Lernmodelle des PAC-Lernens und des Lernens mit Äquivalenz- und Elementfragen und wichtige bekannte Ergebnisse, insbesondere zum Lernen regulärer Sprachen, vorgestellt.

Für das für das PAC-Lernen wichtige Konsistenzproblem der regulären unären Sprachen wird ein Algorithmus angegeben, der in Zeit O(n × |S|) den mit der Beispielsmenge S minimalen konsistenten DFA berechnet, wobei n die Anzahl der Zustände des minimalen DFA für die zu lernende Sprache L ist. Außerdem werden eine obere und eine untere Schranke für die VC-Dimension der regulären unären Sprachen angengeben. Sei L_n die Menge der von einem DFA mit n Zuständen akzeptierten regulären unären Sprachen. Dann gilt VC(L_n) ≥ n − 1 + ⌊ log n ⁄ ln n + 1 ⌋ und VC(L_n) ≤ n + log n für n ≥ 5.

Weiter wird nachgewiesen, dass die regulären unären Sprachen, im Gegensatz zu den regulären Sprachen, mit Äquivalenz- oder Elementfragen alleine lernbar sind.

Für das Lernen mit Äquivalenzfragen wird eine obere Schranke von O(n²) Fragen gezeigt, wobei n die Anzahl der Zustände des minimalen DFA der zu lernenden Sprache L ist. Für das Lernen der Konzeptklasse L_n durch die Hypothesenklasse der unären deterministischen endlichen Automaten mit primer Zykluslänge wird eine untere Schranke von Ω(n² ⁄ ln n) Fragen bestimmt.

Für das Lernen mit Elementfragen wird eine obere Schranke von 2n − 1 Fragen bei bekanntem n gegeben. Wird dem Lernalgorithmus zusätzlich gestattet eine abgeschwächte Äquivalenzfrage zu stellen, eine Frage, die ihm beantwortet ob seine Hypothese äquivalent zu der zu lernenden Sprache L ist, aber kein Gegenbeispiel liefert, dann ergibt sich für das Lernen der regulären unären Sprachen eine obere Schranke von 2n Elementfragen und n abgeschwächten Äquivalenzfragen.