💬 NLP

From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages

This paper proves that all standard subregular language classes are linearly separable via their deciding predicates, thereby establishing their finite observability and learnability with simple linear models, a finding validated by both synthetic and real-world morphological experiments.

Original authors: Katsuhiko Hayashi, Hidetaka Kamigaito

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Katsuhiko Hayashi, Hidetaka Kamigaito

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to speak like a human. You have a massive dictionary of words and rules, but the robot is overwhelmed. It doesn't know where to start. Is there a simple way to tell the robot, "Here is a rule for how words should look," without giving it a million complex instructions?

This paper answers yes. The authors, Katsuhiko Hayashi and Hidetaka Kamigaito, discovered that the rules governing how languages work (specifically the "subregular" rules that handle things like spelling, sounds, and word endings) are actually much simpler than we thought. They are like Lego bricks that can be sorted into neat, separate piles using a very simple machine.

Here is the breakdown of their discovery using everyday analogies:

1. The Problem: The "Black Box" of Language

For a long time, linguists and computer scientists have argued about how complex language is. Some say it's like a super-complex maze that requires a genius-level brain (like a deep neural network) to navigate. Others say it's simpler.

The authors focus on a specific group of language rules called Subregular Languages. Think of these as the "traffic laws" of language. They aren't the laws of physics (which are super complex); they are the simple rules like "Don't drive on the sidewalk" or "Stop at a red light."

Examples: "You can't have three 's' sounds in a row," or "If a word starts with 're-', it usually ends with a vowel."

2. The Big Idea: "Finite Observability"

The paper introduces a concept called Finite Observability.

The Analogy: The Detective's Checklist
Imagine you are a detective trying to solve a crime. You don't need to know the suspect's entire life story, their DNA, or what they had for breakfast. You only need to check a short, fixed list of clues (e.g., "Was the suspect at the scene?" "Did they have a weapon?").

The authors prove that for these specific language rules, you only need a finite checklist of "clues" (predicates) to decide if a word is valid or not.

Clue 1: Does the word contain the sound "ng"?
Clue 2: Does it start with a capital letter?
Clue 3: Does it have the suffix "-ness"?

If you know the answers to these few questions, you know the answer to the big question: "Is this a valid word?" You don't need to look at the whole word; you just need the checklist.

3. The Magic Trick: Linear Separability

Once you have that checklist, the paper proves something amazing: You can draw a straight line to separate the "Good" words from the "Bad" words.

The Analogy: Sorting Fruit
Imagine you have a basket of fruit. Some are apples (valid words), and some are oranges (invalid words).

The Old Way: You might try to build a complex, curvy, twisting wall to separate them, thinking the shapes are too weird to sort simply.
The New Way: The authors show that if you look at the fruit through the right lens (the checklist of clues), you can just draw one straight line on a table. Everything on the left is an apple; everything on the right is an orange.

In math terms, this is called Linear Separability. It means you don't need a super-complex AI to learn these rules. A simple, straight-line calculator (like a basic linear model) can learn them perfectly.

4. Why This Matters

This is a huge deal for two reasons:

Simplicity: It proves that the "traffic laws" of language are simple enough that a basic machine can learn them instantly. We don't need to overcomplicate things with massive, black-box AI models to understand basic grammar and spelling.
Interpretability: Because the model is just looking at a simple checklist, we can actually see what it learned.
- Real-world test: The authors tested this on English words. The simple model didn't just guess right; it learned rules that real linguists recognize, like "The suffix '-ly' usually goes at the end of a word." It's like the robot didn't just memorize the answer; it understood the logic.

5. The Catch (The "But...")

The paper also includes a "Counterexample" section. They admit: "This only works for the simple rules."
If you try to use this checklist for every possible rule in the universe (including very complex, infinite patterns), the checklist would have to be infinite, and the straight line wouldn't work. But for the specific, common rules that make up most of our daily speech and writing? The checklist works perfectly.

Summary

Think of this paper as finding a universal key for a specific set of locks.

The Locks: The rules of how we string sounds and letters together (phonology and morphology).
The Key: A simple list of "yes/no" questions (predicates).
The Result: If you ask the right questions, you can separate valid words from invalid ones with a single, straight line.

This means we can build language tools that are fast, simple, and easy to understand, rather than massive, confusing black boxes. It's a reminder that sometimes, the most powerful way to understand complex human behavior is to look for the simple, straight lines hidden underneath.

1. Problem Statement

The paper addresses a gap between Formal Language Theory and Statistical Learning Theory regarding natural language structure.

Context: It is well-established that many natural language phenomena (phonology, morphology, syntax) fall within the subregular hierarchy (classes strictly contained within regular languages, such as Strictly Local, Strictly Piecewise, etc.). These classes are known to be learnable.
The Gap: While algebraic and logical characterizations of subregular languages exist, there is a lack of a geometric perspective explaining why they are learnable. Specifically, it has not been rigorously proven that these classes are linearly separable in finite-dimensional feature spaces.
Goal: The authors aim to prove that standard subregular language classes are finitely observable, which implies they are linearly separable. This would allow the direct application of statistical learning guarantees (e.g., VC dimension, perceptron bounds) to natural language modeling.

2. Methodology

The authors introduce a framework based on predicates and finite observability to bridge the gap.

A. Core Definitions

Predicates: Boolean-valued functions $p: \Sigma^* \to \{0, 1\}$ that detect finite properties of a string (e.g., presence of a substring, subsequence, or thresholded count).
Finite Observability: A language class $\mathcal{C}$ is finitely observable if there exists a finite set of predicates $P = \{p_1, \dots, p_n\}$ such that membership in any language $L \in \mathcal{C}$ depends only on the truth vector $(p_1(x), \dots, p_n(x))$ .
Minterm Linearization: The authors construct a feature map $\Phi(x)$ based on minterms. For a truth vector $r(x) \in \{0, 1\}^n$ , the minterm indicator $\mu_a(x)$ is 1 if $r(x) = a$ and 0 otherwise. This maps the string into a $2^n$ -dimensional Boolean space where each dimension corresponds to a unique combination of predicate outcomes.

B. Theoretical Proof

Main Theorem: The paper proves that Finite Observability $\implies$ Linear Separability.
- If a language is finitely observable, its membership is determined by a subset $S_L \subseteq \{0, 1\}^n$ of truth vectors.
- Using the minterm feature map, the authors construct a hyperplane that separates the minterms in $S_L$ from those outside it.
- Result: The separating hyperplane achieves a functional margin of at least $1/2$ .
Learning Consequences: Because the feature vectors are one-hot with unit norm, the geometric margin is bounded. This implies:
- Perceptron Bound: The number of mistakes is bounded by $4|S_L|^2$ .
- VC Dimension: The VC dimension of the hypothesis space is at most $2n$ , ensuring generalization.

C. Practical Implementation

While the theoretical minterm embedding is exponential in the number of predicates, the authors note that for standard subregular classes, low-dimensional predicate features (e.g., raw presence/absence of $k$ -grams or subsequences) are sufficient to achieve separation without the exponential blowup.

D. Counterexample (Limits)

The paper includes a proof (Theorem 4.1) showing that not all regular languages are finitely observable. By fixing a finite set of predicates, one can only distinguish $2^n$ equivalence classes. However, regular languages can require arbitrarily many right-congruence classes (e.g., modulo counting). Thus, the full class of regular languages cannot be linearly separated by a fixed finite predicate set, highlighting the specific power of the subregular restriction.

3. Key Contributions

Definition of Finite Observability: A new property ensuring language membership depends on a finite set of primitive observations.
Proof of Linear Separability: A rigorous proof that all standard subregular classes (SL, SP, LT, PT, LTT, TSL) are finitely observable and therefore linearly separable in appropriate Boolean feature spaces.
Unification of Theories: The work connects algebraic language theory with statistical learning theory, providing a geometric foundation for why subregular languages are learnable.
Empirical Validation: Demonstrated that linear models trained on these features achieve perfect separation on synthetic data and recover linguistically meaningful constraints on real data.

4. Experimental Results

A. Synthetic Experiments

The authors tested Strictly Local (SL), Strictly Piecewise (SP), and Locally Threshold Testable (LTT) languages.

Noise-Free Conditions: Logistic regression models achieved 100% accuracy, confirming the theoretical guarantee of perfect linear separability.
Noise Sensitivity: As label noise increased, accuracy decreased smoothly, demonstrating robustness.
Sample Size: Performance converged rapidly to 100% as training data increased, validating the finite observability hypothesis.

B. Real-Data Experiments (English Morphology)

Using the MorphoLex-en database, the authors modeled English derivational morphology (affix sequences).

Setup: Positive examples were well-formed affix sequences; negatives were perturbed (permuted or substituted).
Features: Used Piecewise Testable (PT) and Locally Threshold Testable (LTT) predicates.
Performance: Logistic regression achieved >85% accuracy and 86% F1 score.
Interpretability: The learned weights aligned with linguistic constraints. For example, the model heavily weighted boundary-sensitive predicates (e.g., suffixes like -ly or -ness at the end of words) and specific prefix-suffix interactions, mirroring known morphological rules.
Margin Analysis: The distribution of classification margins was heavily skewed toward positive values, indicating that most data points lie clearly on the correct side of the decision boundary.

5. Significance and Implications

Theoretical Foundation: The paper provides a rigorous justification for using simple linear models (like logistic regression or linear SVMs) to model natural language. It suggests that the "complexity" of natural language is often an illusion caused by looking at the wrong feature space; in the correct subregular feature space, the structure is simple and linearly separable.
Interpretability: Unlike deep neural networks (RNNs/Transformers) which are often black boxes, this approach offers interpretable models. The features correspond directly to linguistic constraints (e.g., "forbidden 3-grams" or "vowel harmony").
Efficiency: It demonstrates that computationally lightweight models are theoretically sufficient for capturing the core structural constraints of natural language, challenging the necessity of massive, high-capacity neural networks for these specific tasks.
Future Directions: The authors suggest investigating whether larger language families admit similar observability properties and whether the effective capacity of neural models in practice aligns more closely with subregular structures than their theoretical upper bounds.

In summary, the paper establishes that subregular languages are inherently simple to learn because they are finitely observable and linearly separable, offering a bridge between formal linguistics and modern statistical learning.