65;6203;1c # Course Information

**Course:** TThu 15:00-16:20, Frey Hall 326

**Instructor:** Jeffrey Heinz, jeffrey.heinz@stonybrook.edu

**Office Hours:** M 13:00-14:00, W 11:00-13:00, SBS N237

- Jeff concludes the course.

- Kenneth presents on Lambert 2021.

- Jeff presents on learning stochastic stringsets.
- For those interested here is Halmos on writing

- Logan presents on Nowak et al. 2022.
- For next Tuesday Nov 22 please read Jardine et al 2014 (Salam and Adil presenting)

- Yola presents on Rawski and Heinz’s response to Pater.
- Gillian presents on Dunbar’s response to Pater.
- For Tuesday please read Nowak et al. 2002 (Logan presenting)

- Rita presents on Pater 2019
- For those interested, here is Kodner and Khalifa 2022 which discusses the past tense debate in the context of the 2022 SIGMORPHON shared task on modeling inflection.

- Jack presented on on extracting automata from recurrent neural networks (Weiss et al. 2018).
- For next Tuesday, please read the following (Rita, Yola, and Gillian presenting next Tue and Thu)
- Generative linguistics and neural networks at 60 Pater 2019
- Response by Dunbar The implementational mapping problem
- Response by Rawski and Heinz No free lunch

- In case you are interested, here is the whole issue

- Han presented on string extension learning (Heinz 2010). Slides are here.
- For those interested, this 2012 paper presents a deeper analysis of the lattice structure of string-extension learnable hypothesis spaces, and shows that many other classes of languages languages that are identifiable in the limit (including the zero reversible languages) have this lattice structure. It also characterizes which of these classes are also PAC learnable.

- For Tuesday, please read Weiss et al. 2018 on extracting automata from recurrent neural networks Weiss et al. 2018 (Jack presenting).

- Nick presented on distributional learning (Clark and Eyraud 2007). The slides are here.
- For Thu Oct 27 read string extension learning Heinz 2010 (Han presenting)
- For those interested:
- Here is (Clark 2013) which builds on the prior work of the subsitutable language learning algorithm to remove much (all?) of the ambiguity in the derivations. Consequently, syntactic structures are learned. For example, he basically recovers the syntactic structure underlying propositional logic. And here is Clark and Yoshinaka’s 2016 review of several extensions to the distributional learning framework since 2007.
- Here are slides from my talk on investigating the generalization powers of NNs on regular languages at the “All Things Language and Computation” series last Friday.

- We concluded the handout on identification in the limit.
- We discussed RPNI from de la Higuera’s slides.
- ALERGIA and OSTIA adapt these ideas to learn probability distributions over sigma star and string-to-string functions from positive examples only.
- flexfringe implements RPNI and ALERGIA and many variants paper.
- For more details read de la Higuera (2010) Grammatical Inference.

- We continued our study of identification in the limit paradigms.
- Reminder that project proposals are to be approved by November 1. Please talk to me if you need help coming up with a good project.
- Here is the schedule we developed over the next several weeks.
- Tue Oct 25: Nick on distributional learning Clark and Eyraud 2007
- Thu Oct 27: Han on string extension learning Heinz 2010
- Tue Nov 01: Jack on extracting automata from recurrent neural networks Weiss et al. 2018
- Thu Nov 3 - Tue Nov 8: Rita, Gillian, Yola
- Generative linguistics and neural networks at 60 Pater 2019
- Response by Dunbar The implementational mapping problem
- Response by Rawski and Heinz No free lunch
- The whole issue

- Thu Nov 10: Logan on evolution and learnability Komorova et al. 2002
- Thu Nov 15: Salam on learning classes of DFTs Jardine et al 2014
- Thu Nov 17: Kenneth on learning TSL Lambert 2021
- Adil, TBD

- Eric presented and led discussion on Heinz 2010 “Learning Long-distance Phonotactics”.
- Jeff finished going over the last several slides from his what does learning mean talk, which emphasized how deterministic finite state machines define a parameterized concept class, and whether the concepts are formal (boolean) languages, stochastic languages, or string-to-string functions – so whether the parameter values are boolean, reals, or strings – the learning of these classes is conducted similarly. Papers exist which make these connections explicit for DFA more generally and k-SL and k-SP classes in particular.
- For next Tuesday, review the first 10 pages (up to 4.7) of the notes on identification in the limit. (We have already discussed up to 4.5 on Oct 06).
- Also for those who are enrolled and have not yet presented yet, please think about which papers you would be interested in presenting over the next few weeks as I would like to schedule. Feel free to get in touch if you need pointers.

- Fall break

- We began our study of identification in the limit.
- Read Heinz 2010 for next Thursday. Eric will present.

- Class canceled.

- We discussed the rest of Chapter 5 of Valiant 2013.
- Jeff presented his talk what does learning mean

- Sarah presents on Lignos and Yang 2016.
- Read the rest of Valiant 2013 chapter 5 and write answers to these questions and send them to me jeffrey.heinz@stonybrook.edu.

- Class cancelled. Try to check out the learning talks on Friday at this workshop

- Magda presented on Angluin and Laird’s 1988 paper “Learning from Noisy Examples.”

- John presents on the VC dimension. (Slides)

- We went over this handout that reviewed the proof that the tightest-fit rectangle algorithm pac-learns the class of axis-aligned rectangles and the proof that the elimination algoritm pac-learns the class of monomials.
- For Thursday, read sections 1, 2 and 3 of chapter 3 KV94 on the VC dimension.

- We reviewed the preliminary definition of PAC learnability.
- We discussed and explained the PAC learnability of axis-aligned rectangles.
- We discussed the modified definition of PAC learnability which takes into account the size of the representation of the concepts.
- We established a plan for the next several classes
- Tue Sep 13: Jeff on PAC learning monomials (1.3 in KV94)
- Thu Sep 15: John on the VC dimension (3.1, 3.2, 3.3 in KV94 and theorems 3.3,3.4)
- Tue Sep 20: Magda on Learning from Noisy Examples, up to 2.3
- Thu Sep 22: Class canceled because of this workshop At least see the learning talks from 4:30pm on Fri Sep 23!
- Tue Sep 27: Sarah on Morphology and Language Acquisition

- We went over HW03.
- We discussed up to 5.7 in Valiant 2013.
- We defined PAC learning formally.

- We finished the handout on enumerability and computability.
- We discussed the first part of chapter 5 of Valiant 2013 “Probably Approximately Correct”.
- For next time
- Write answers to these questions and send them to me jeffrey.heinz@stonybrook.edu. Show and explain your work.
- Read up to 5.7 of Valiant 2013 “Probably Approximately Correct”

- We finished the handout on enumerability and computability.
- We discussed the first part of chapter 5 of Valiant 2013 “Probably Approximately Correct”.
- For next time
- Write answers to these questions and send them to me jeffrey.heinz@stonybrook.edu. Show and explain your work.
- Read up to 5.7 of Valiant 2013 “Probably Approximately Correct”

- We discussed chapter 3 of Valiant 2013.
- We explained enumerability and why there are too few grammars.
- For next time
- Read chapter 4 and up to 5.5 of Valiant 2013 “Probably Approximately Correct”
- Here are the footnotes, glossary and index of Valiant 2013 “Probably Approximately Correct”

- We discussed chapters 1 and 2 of Valiant 2013.
- We finished discussing language learning on planet Verorez.
- For next time
- Read chapter 3 of Valiant 2013 “Probably Approximately Correct”
- Write answers to these questions and send them to me jeffrey.heinz@stonybrook.edu. Remember, conciseness is a virtue.

- We went over the syllabus.
- We studied language learning on planet Verorez.
- For next time
- Read chapters 1 and 2 of Valiant 2013 “Probably Approximately Correct”
- Write answers to these questions and send them to me jeffrey.heinz@stonybrook.edu. Remember, conciseness is a virtue.