# Berkeley CS 182 - Inductive and statistical learning of formal grammars (28 pages)

Previewing pages*1, 2, 3, 26, 27, 28*of 28 page document

**View the full content.**## Inductive and statistical learning of formal grammars

Previewing pages
*1, 2, 3, 26, 27, 28*
of
actual document.

**View the full content.**View Full Document

## Inductive and statistical learning of formal grammars

0 0 31 views

- Pages:
- 28
- School:
- University of California, Berkeley
- Course:
- Cs 182 - Neural Basis of Thought and Language

**Unformatted text preview:**

Inductive and statistical learning of formal grammars Pierre Dupont pdupont info ucl ac be Typeset by FoilTEX 2002 Grammar Induction Outline Grammar induction definition Learning paradigms DFA learning from positive and negative examples RPNI algorithm Probabilistic DFA learning Application to a natural language task Links with Markov models Smoothing issues Related problems and future work Pierre Dupont 1 2002 Grammar Induction Machine Learning Goal to give the learning ability to a machine Design programs the performance of which improves over time Inductive learning is a particular instance of machine learning Goal to find a general law from examples Subproblem of theoretical computer science artificial intelligence or pattern recognition Pierre Dupont 2 2002 Grammar Induction Grammar Induction or Grammatical Inference Grammar induction is a particular case of inductive learning The general law is represented by a formal grammar or an equivalent machine The set of examples known as positive sample is usually made of strings or sequences over a specific alphabet A negative sample i e a set of strings not belonging to the target language can sometimes help the induction process Data aaabbb ab Pierre Dupont Induction Grammar S aSb S 3 2002 Grammar Induction Examples Natural language sentence Speech Chronological series Successive actions of a WEB user Successive moves during a chess game A musical piece A program A form characterized by a chain code A biological sequence DNA proteins Pierre Dupont 4 2002 Grammar Induction Pattern Recognition 16 3 4cont 3 8cont 15 14 13 12 8dC 3 2 4 5 11 1 0 6 7 10 9 8 7 6 5 4 3 2 1 0 2 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 8dC 000077766676666555545444443211000710112344543311001234454311 Pierre Dupont 5 2002 Grammar Induction Chromosome classification Centromere grey dens derivative grey density Chromosome 2a 90 80 70 60 50 40 30 0 100 200 300 400 500 600 0 100 200 300 position along median axis 400 500 600 6 4 2 0 2 4 6 CDFDCBBBBBBBA bcdc DGFB bccb cffc CCC cdb BCB dfdcb String of Primitives Pierre Dupont 6 2002 Grammar Induction A modeling hypothesis G0 Generation Data Induction Grammar G Find G as close as possible to G0 The induction process does not prove the existence of G0 It is a modeling hypothesis Pierre Dupont 7 2002 Grammar Induction Grammar induction definition Learning paradigms DFA learning from positive and negative examples RPNI algorithm Probabilistic DFA learning Application to a natural language task Links with Markov models Smoothing issues Related problems and future work Pierre Dupont 8 2002 Grammar Induction Learning paradigms How to characterize learning which concept classes can or cannot be learned what is a good example is it possible to learn in polynomial time Pierre Dupont 9 2002 Grammar Induction Identification in the limit G0 Generation Data Induction Grammar d1 d2 G1 G2 dn G convergence in finite time to G G is a representation of L G0 exact learning Pierre Dupont 10 2002 Grammar Induction PAC Learning G0 Generation Data Induction Grammar d1 d2 G1 G2 dn G convergence to G G is close enough to G0 with high probability Probably Approximately Correct learning polynomial time complexity Pierre Dupont 11 2002 Grammar Induction Identification in the limit good and bad news The bad one Theorem 1 No superfinite class of languages is identifiable in the limit from positive data only The good one Theorem 2 Any admissible class of languages is identifiable in the limit from positive and negative data Pierre Dupont 13 2002 Grammar Induction Other learnability results Identification in the limit in polynomial time DFAs cannot be efficiently identified in the limit unless we can ask equivalence and membership queries to an oracle PAC learning DFAs are not PAC learnable under some cryptographic limitation assumption unless we can ask membership queries to an oracle Pierre Dupont 14 2002 Grammar Induction PAC learning with simple examples i e examples drawn according to the conditional Solomonoff Levin distribution Pc x c2 K x c K x c denotes the Kolmogorov complexity of x given a representation c of the concept to be learned regular languages are PACS learnable with positive examples only but Kolmogorov complexity is not computable Pierre Dupont 15 2002 Grammar Induction Cognitive relevance of learning paradigms A largely unsolved question Learning paradigms seem irrelevant to model human learning Gold s identification in the limit framework has been criticized as children seem to learn natural language without negative examples All learning models assume a known representation class Some learnability results are based on enumeration Pierre Dupont 16 2002 Grammar Induction However learning models show that an oracle can help some examples are useless others are good characteristic samples typical examples learning well is learning efficiently example frequency matters good examples are simple examples cognitive economy Pierre Dupont 17 2002 Grammar Induction Grammar induction definition Learning paradigms DFA learning from positive and negative examples RPNI algorithm Probabilistic DFA learning Application to a natural language task Links with Markov models Smoothing issues Related problems and future work Pierre Dupont 18 2002 Grammar Induction Regular Inference from Positive and Negative Data Additional hypothesis the underlying theory is a regular grammar or equivalently a finite state automaton Property 1 Any regular language has a canonical automaton A L which is deterministic and minimal minimal DFA Example L ba a b 0 Pierre Dupont b 1 a a 2 19 2002 Grammar Induction A few definitions Definition 1 A positive sample S is structurally complete with respect to an automaton A if when generating S from A every transition of A is used at least one every final state is used as accepting state of at least one string b Example ba baa baba Pierre Dupont 0 b 1 a a 2 20 2002 Grammar Induction Merging is fun a A 1 0 a a A 2 0 1 b 1 a b 2 a 0 2 b b 1 2 a 0 2 a 1 b a 0 1 2 Merging definition of a partition on the set of states Example 0 1 2 If A2 A1 then L A1 L A2 merging states generalize language Pierre Dupont 21 2002 Grammar Induction A theorem The positive data can be represented by a prefix tree acceptor PTA a a 0 Example aa abba baa 1 b 2 b a 3 4 5 b a 6 a 8 7 Theorem 3 If the positive sample is structurally complete with respect to a canonical automaton A L0 then there exists a partition of the state set of P T A such that P T A

View Full Document