Papers We Love NYC | Learning Rules: What can math tell us about language

Papers We Love, Espresso AI, Authentic and Antithesis are pleased to present the October edition of PwL.

Papers We Love is a community of programmers who love reading and discussing computer science papers.

What was the last paper within the realm of computing you read and loved? What did it inspire you to build or tinker with? Come share the ideas in an awesome academic or research paper with fellow engineers, programmers, and paper-readers. Lead a session and show off code you wrote that implements these ideas, or just give us the lowdown on the paper. Otherwise, just come, listen, learn, and discuss.

Speaker: Abed Qaddoumi

More about Abed: Abed Qaddoumi is a PhD student in Linguistics at Stony Brook University, affiliated with the Institute for Advanced Computational Science. His research sits at the intersection of computation, language, and cognition: how computers can learn and represent the patterns underlying human language, drawing on grammatical inference, formal-language theory, and neural networks. He focuses on modeling phonological and morphological patterns, particularly in Arabic, using finite-state machines to represent permissible sequences of sounds and morphemes, analyze their formal properties, and study how these patterns can be learned from examples. Before Stony Brook, Abed earned an MS in Computer Science from NYU and worked on climate modeling at a finance startup. In a previous life, he worked for Doctors Without Borders and scooped ice cream at Ben & Jerry's. More at [abdulrahimq.github.io and Google Scholar.

Paper: https://www.sciencedirect.com/science/article/pii/S0019995867911655

Title: Learning Rules: What can math tell us about language?

Main Paper: Gold, Language Identification in the Limit (1967)

Supporting Papers: Kleinberg & Mullainathan, Language Generation in the Limit (2024)

Outline: Algebra can explain some social structures. The Cashinahua kinship relationships mirror the symmetries of a square. Can we discover similar mathematical structures in human language? This talk shows that some sound patterns can be described using algebra, logic, automata, and formal languages.

The talk follows three questions

1. What structure does language have? Starting with social relationships, we connect algebraic structures to automata and formal languages, then look at examples from phonology. Along the way, we'll see how regular and subregular descriptions help specify what information a linguistic pattern requires.

1. Can humans learn language rules from examples? We'll review Gold's 1967 paper, which formalizes the question. A learner receives examples and makes successive guesses, eventually settling on a correct grammar. Gold's negative result shows that no learner can guarantee this for the entire class of regular languages from arbitrary positive presentations alone. We'll see why, then explain how restrictions on the hypothesis space and changes in the available evidence can make learning possible.

1. Must we identify a language to generate from it? Kleinberg and Mullainathan changed the task. Instead of identifying valid strings, the learner has to produce valid strings that have not appeared in the input. In their formal setting, generation can succeed even for language families where identification cannot. We'll examine what this means for the success of language models, and when a model produces valid new language, what we can say about the linguistic structure it has learned.

6:30pm - Doors

7:00pm - Speaker begins

PwL curate a repository of papers and places to find them. Contributions welcome via PR.

Join the PWL Discord and hop into the #nyc channel: https://discord.gg/B7aHhwBb8r

Papers We Love has a Code of Conduct. Be good to each other and to the PWL community.