Abstract
We give a universal kernel that renders all the regular languages linearly separable. We are not able to compute this kernel efficiently and conjecture that it is intractable, but we do have an efficient $\epsilon$-approximation.
Introduction
The problem of learning a Deterministic Finite Automaton (DFA) from labeled examples is a cornerstone of computational learning theory. Traditionally, this is approached as a search for the smallest DFA consistent with the data—a task known to be NP-complete and difficult to even approximate. This paper explores a powerful alternative: kernel methods. By embedding strings into a high-dimensional space, can we use Support Vector Machines (SVMs) to find a separating hyperplane for any regular language? The author answers this in the affirmative by constructing a "universal kernel" for the class of regular languages.
The Theoretical Framework: Linear Separability of Countable Concepts
The paper begins with a broad theoretical result: any countable set of concepts over a countable space can be made linearly separable. This is achieved through a canonical embedding that maps instances and concepts into a Hilbert space. To ensure this embedding is not merely a mathematical curiosity but a computationally grounded tool, the author introduces "size functions" (such as string length or the number of states in an automaton). These functions weight the embedding, ensuring that the resulting vectors have finite support and the kernel remains well-defined and computationally meaningful.
The Universal Kernel for Regular Languages
Applying this general theory to the specific domain of regular languages, the author defines a kernel $K(x, y)$ based on the behavior of finite automata. Specifically, the kernel counts the number of $n$-state DFAs that accept both string $x$ and string $y$.
If we consider the set of all possible DFAs, a language $L$ is regular if and only if there exists some DFA that recognizes it. By weighting these automata according to their complexity (size), the author constructs a feature space where every regular language corresponds to a linear decision boundary. This implies that a single fixed embedding is theoretically sufficient to learn any regular language using standard convex optimization tools.
Overcoming Computational Intractability
A significant hurdle in this approach is the sheer number of possible DFAs. The number of $n$-state DFAs grows super-exponentially, making the exact calculation of $K(x, y)$ likely #P-complete. To address this, the paper proposes a Monte Carlo approximation.
The efficiency of this approximation relies on the "stability" of the kernel. In Theorem 5.1, the author proves that for any two strings, the probability that a randomly sampled $n$-state DFA accepts both is bounded between 1/4 and 1/2. This prevents the kernel values from vanishing or becoming too small to measure, ensuring that a relatively small number of samples can provide a high-confidence $\epsilon$-approximation. Specifically, the author demonstrates that $m = 12\epsilon^{-2} \log(2/\alpha)$ samples are sufficient to achieve an $\epsilon$-approximation with confidence $1-\alpha$.
Key Results and Insights
The primary contribution is Theorem 3.1, which establishes the linear separability of countable concept classes under finite-support embeddings. For the specific case of regular languages, the paper proves that any language $L$ can be represented as a weighted sum of kernel evaluations:
$$L = \{x \in \Sigma^* : \sum \alpha_i K(s_i, x) > 0\}$$
This result effectively bridges the gap between the discrete world of automata and the continuous world of kernel-based learning, suggesting that we do not need a different feature set for every target language.
Limitations and Future Directions
While the existence of a universal kernel is a major theoretical milestone, several practical challenges remain:
- Computational Intractability: The exact kernel remains computationally out of reach, necessitating reliance on approximations.
- Model Extraction: While an SVM can find a separating hyperplane in this kernel space, the paper does not provide a method to "extract" a human-readable DFA from the resulting hyperplane.
- Generalization and Margins: The efficiency of learning depends on the "margin"—the distance between the classes in the feature space. How this margin scales as the target automaton grows in size remains an open question for future research.
Conclusion
This work provides a rigorous mathematical foundation for learning regular languages through kernel methods. By proving that universality is possible and providing an efficient approximation scheme, the author opens new avenues for applying high-margin classifiers to classical problems in formal language theory.
Summary updated