{"id":865,"date":"2016-01-11T11:45:07","date_gmt":"2016-01-11T10:45:07","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=865"},"modified":"2016-02-19T14:00:44","modified_gmt":"2016-02-19T13:00:44","slug":"7-learning-automata","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/7-learning-automata","title":{"rendered":"7. Learning automata"},"content":{"rendered":"

This lecture is about learning regular languages (of finite words). All automata here are deterministic finite automata. The setup is that there are two parties: Learner and Teacher. Teacher knows a regular language. Learner wants to learn this language, and pursues this goal by asking\u00a0two types of queries to the Teacher:<\/p>\n

\u2022 Membership<\/strong>.\u00a0<\/em>In a membership query, Learner gives\u00a0a word, and the Teacher says whether or not Teacher’s language contains that word.<\/p>\n

\u2022\u00a0Equivalence.\u00a0<\/strong>In an equivalence query, Learner gives regular language, represented by an automaton, and Teacher replies whether or not\u00a0the Teacher’s and Learner’s languages are equal. If yes, the protocol is finished. If no, Teacher gives a counterexample, i.e. a word where the Teacher’s and Learner’s languages disagree.<\/p>\n

Membership queries on their own can never be enough to ascertain the language \u2013 there are infinitely many regular languages that match any finite set of membership queries. On the other hand, given enough time, equivalence queries alone are sufficient: \u00a0Learner can\u00a0enumerate all regular languages, and ask equivalence queries until the correct language is reached, without ever using membership queries. The lecture is about a more practical solution, which was found by Dana Angluin. Angluin’s algorithm is a protocol where\u00a0Learner learns Teacher’s language in a number of queries that is polynomial in:<\/p>\n

\u2022 the minimal automaton\u00a0of Teacher’s language;
\n\u2022 the size of Teacher’s counterexamples.<\/p>\n

If Teacher provides counterexamples of minimal size, then the second parameter above is superfluous, i.e. the number of queries will be polynomial in the minimal\u00a0automaton\u00a0of Teacher’s language. As mentioned above, we only talk about deterministic automata, and therefore the minimal automaton refers to the minimal deterministic automaton.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

State words and test words.<\/b><\/p>\n

Suppose that Teacher’s language is \"L \subseteq \Sigma^*\". We assume that the alphabet is known to both parties, but the language is only known to Teacher. At each step of the algorithm, Learner will store an approximation of the minimal automaton of \"L\", as described by two sets of words:<\/p>\n

\u2022 a set \"Q \subseteq \Sigma^*\" of\u00a0state\u00a0<\/em>words, closed under prefixes;
\n\u2022 a set \"T \subseteq \Sigma^*\" of\u00a0test\u00a0<\/em>words, closed under suffixes.<\/p>\n

The idea is that the state words are all distinct with respect to Myhill-Nerode equivalence for Teacher’s language, and the test words are sufficient to prove this. This idea is formalised in the following definitions.<\/p>\n

Correctness and completeness.\u00a0<\/strong>If \"T\" is a set of test words, we say that words\u00a0\"v,w \in \Sigma^*\" are \"T\"-equivalent if <\/p>\n

  <\/span>   <\/span>\"\[wu \in L \quad\mbox{iff} \quad vu \in L \qquad \mbox{for every $u \in T$}\]\"<\/p>\n

\u00a0This is an equivalence relation, which is coarser or equal to the Myhill-Nerode equivalence relation of Teacher’s language. In terms of \"T\"-equivalence we define the following properties of sets \"Q,T \subseteq \Sigma^*\" that will be used in the algorithm:<\/p>\n

\u2022 correctness<\/strong>: no two distinct words in \"Q\" are \"T\"-equivalent;
\n\u2022 completeness<\/strong>: for every \"q \in Q\" and \"a \in \Sigma\", there is some \"p \in Q\" that is \"T\"-equivalent to \"qa\".<\/p>\n

If \"(Q,T)\" is\u00a0correct and complete, then we can define an automaton as follows. The states are \"Q\", the initial state being the empty word. When the automaton is in state \"q \in Q\" and reads a letter \"a\", it goes to the state \"p\" described in the completeness property; this state is unique by the correctness property. The accepting states are those states that are in Teacher’s language.<\/p>\n

<\/b>Fact 1.\u00a0<\/strong>If \"(Q,T)\" is\u00a0correct but not complete, then using a polynomial number of membership queries, Learner can find some \"P \supseteq Q\" such that \"(P,T)\" is correct and complete.<\/p>\n

Proof.\u00a0<\/strong>If \"q \in Q\" and \"a \in \Sigma\" are such that no word in \"Q\" is \"T\"-equivalent to \"qa\", then \"qa\" can be added to \"Q\". The membership\u00a0queries are used to test what is \"T\"-equivalent to \"qa\". \"\Box\"<\/p>\n

 <\/p>\n

\n

The algorithm<\/strong><\/p>\n

We are now ready to describe the\u00a0algorithm.<\/p>\n

1. \"Q=T= \set{\epsilon}\"<\/p>\n

2. Invariant: \"(Q,T)\" is correct, not necessarily complete.<\/p>\n

3. Apply Fact 1, and enlarge \"Q\", making\u00a0\"(Q,T)\"\u00a0correct and complete.<\/p>\n

4. Compute the automaton for \"(Q,T)\" and ask an equivalence query for\u00a0it.<\/p>\n

5. If the answer is yes, then the algorithm terminates with success.<\/p>\n

6. If the answer is no, then add the counterexample and its suffixes to \"T\".<\/p>\n

7. Goto 2.<\/p>\n

 <\/p>\n

Note that if \"(Q,T)\" is correct, then all words in \"Q\" correspond to different states in the minimal automaton (for Teacher’s language). Furthermore, if the size of \"Q\" reaches the size of the minimal automaton, then \"Q\" represents all states of the minimal automaton, and the transition function in the automaton for \"(Q,T)\" is the same as the transition function in the minimal automaton. Therefore, if\u00a0\"Q\" reaches the size of the minimal automaton, the equivalence query in step 4 has a positive result.<\/p>\n

To prove that the algorithm terminates, we show in Fact 2\u00a0below that after step 6, \"(Q,T)\" is no longer complete. This will mean that step 3 will necessarily enlarge \"Q\", and therefore the number of times we do “Goto 2” will be bounded by the size of the minimal automaton.<\/p>\n

Fact 2. \u00a0<\/strong>After step 6, \"(Q,T)\" is no longer complete.<\/p>\n

Proof.\u00a0<\/strong>Let \"(Q,T)\" be the pair in step 4, and let \"a_1 \cdots a_n\" be the counterexample, which witnesses that the automaton for \"(Q,T)\" does not recognise Teacher’s language. Define \"T'\" to be \"T\" plus all suffixes of the counterexample, and suppose toward a contradiction that \"(Q,T')\" is complete. It is not difficult to see that the automata for \"(Q,T)\" and \"(Q,T')\" are the same.\u00a0Define \"q_i\" to be the state of either of these automata after reading \"a_1 \cdots a_i\". \u00a0By construction, the state \"q_{i}\" is a word which is \"T'\"-equivalent to \"q_{i-1} a_i\", and since \"a_{i+1} \cdots a_n \in T'\", it follows that\u00a0<\/p>\n

  <\/span>   <\/span>\"\[q_{i-1} a_{i} \cdots a_n \in L \qquad \mbox{iff} \qquad q_{i} a_{i+1} \cdots a_n \in L.\]\"<\/p>\n

Since \"q_0\" is the empty word, the above and induction imply that<\/p>\n

  <\/span>   <\/span>\"\[a_1 \cdots a_n \in L \qquad \mbox{iff} \qquad q_n \in L\]\"<\/p>\n

which means that the automaton gives the correct answer to the counterexample, a \u00a0contradiction. (Thank you Marcin Smulewicz for helping me with this proof!) \"\Box\"<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

This lecture is about learning regular languages (of finite words). All automata here are deterministic finite automata. The setup is that there are two parties: Learner and Teacher. Teacher knows a regular language. Learner wants to learn this language, and pursues this goal by asking\u00a0two types of queries to the Teacher: \u2022 Membership.\u00a0In a membership […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":535,"menu_order":7,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-865","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/865"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=865"}],"version-history":[{"count":63,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/865\/revisions"}],"predecessor-version":[{"id":1036,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/865\/revisions\/1036"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/535"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=865"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}