The teaching complexity of erasing pattern languages with bounded variable frequency.

Ziyuan GaoarXiv 2019 · OpenReview

TL;DR

This paper investigates how limiting the "variable frequency" (how many times a variable appears in a pattern) affects the complexity of teaching pattern languages. The authors show that this restriction significantly simplifies learning, making previously unlearnable pattern classes learnable and providing tighter bounds on the number of examples needed.

What Problem Does This Paper Address?

Pattern languages are a powerful way to describe sets of strings, but they come with significant computational challenges. Problems like checking if a string belongs to a pattern language (membership) or if two patterns generate the same language (equivalence) are often computationally hard (NP-complete or even undecidable). In machine learning, the general class of pattern languages is considered unlearnable. To make progress, researchers focus on restricted subclasses of patterns. This paper specifically examines the impact of bounding the variable frequency – the maximum number of times any single variable appears in a pattern – on the complexity of learning these languages. The goal is to understand how this specific restriction influences the minimum number of examples required to uniquely identify a pattern within a given class, using formal teaching-learning models.

Methods

The paper delves into two formal models of cooperative teaching-learning: the Teaching Dimension (TD) model and the Preference-Based Teaching (PBT) model. In these models, a "teacher" provides examples to a "learner" to help it identify a target pattern from a specific class. The "teaching complexity" is the minimum number of examples needed. The authors analyze various subclasses of patterns, particularly focusing on:

  • Simple Block-Regular Patterns: Patterns of the form $X_1a_1X_2a_2...X_na_n$, where $X_i$ are distinct variables and $a_i$ are constants.
  • m-Quasi-Regular Patterns: Patterns where every variable appears exactly $m$ times.
  • m-Regular Patterns: Patterns where every variable appears at most $m$ times.

They introduce specific constructions of "negative examples" (strings that do not belong to the target pattern) and analyze how these examples help distinguish between patterns with different variable frequencies. They also leverage existing results on graph coloring and word equations to establish bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of pattern languages rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Variable Frequency is Key: The paper strongly suggests that bounding the variable frequency is a crucial factor in simplifying the learnability of pattern languages. It directly impacts how many examples are needed to distinguish patterns.
  • Finite Distinguishability: Even for complex pattern classes, bounding variable frequency often leads to finite distinguishability, meaning a finite set of examples is sufficient to uniquely identify a pattern. This is a significant step towards learnability.
  • TD vs. PBTD: The paper compares the teaching complexity under two models (TD and PBTD). While related, they can yield different bounds, and the paper explores how variable frequency affects both.
  • Alphabet Size Matters: The complexity of learning can depend not only on the pattern structure but also on the size of the alphabet (the number of distinct constant symbols).
  • Subclasses are Learnable: While general pattern languages are unlearnable, specific subclasses with bounded variable frequency are shown to be learnable in the limit and have finite teaching dimensions.

Key Results

  • Simple Block-Regular Patterns: The teaching complexity (both TD and PBTD) for this class is shown to be very low (e.g., TD=2, PBTD=1), especially when compared to larger classes.
  • m-Quasi-Regular and m-Regular Patterns: For these classes, the paper establishes bounds on teaching complexity that depend on $m$ (the variable frequency bound) and the alphabet size. For instance, for unary alphabets, PBTD is linear in $m$.
  • Finite TD for Many Classes: For several restricted classes (simple block-regular, m-quasi-regular, m-regular non-cross patterns), it's proven that every pattern within the class is finitely distinguishable, meaning a finite teaching set exists.
  • Lower Bounds: The paper provides lower bounds for teaching complexity, showing that certain classes require a number of examples that grows with $m$ or the pattern length, especially for finite alphabets.

Limitations and Future Work

  • Exact Bounds for m-Regular Patterns: While the paper shows that many m-regular patterns are finitely distinguishable, determining the exact teaching dimension for all such patterns, especially over finite alphabets of size at least 2, remains an open problem.
  • Tightness of Bounds: For some results, particularly concerning the TD of m-regular patterns over finite alphabets, the paper notes that the derived bounds might not be tight and suggests further investigation.
  • Generalizability of Methods: The paper uses specific constructions and proof techniques. Exploring whether these methods can be generalized to other pattern classes or learning models would be a natural next step.
  • Undecidability of Distinguishability: The paper touches upon the difficulty of determining distinguishability for certain pattern classes, hinting at connections to undecidable problems in formal language theory, which could be a direction for future research.

Summary updated

Abstract

Patterns provide a concise, syntactic way of describing a set of strings, but their expressive power comes at a price: a number of fundamental decision problems concerning (erasing) pattern languages, such as the membership problem and inclusion problem, are known to be NP-complete or even undecidable, while the decidability of the equivalence problem is still open; in learning theory, the class of pattern languages is unlearnable in models such as the distribution-free (PAC) framework (if $\mathcal{P}/poly \neq \mathcal{NP}/poly$). Much work on the algorithmic learning of pattern languages has thus focussed on interesting subclasses of patterns for which positive learnability results may be achieved. A natural restriction on a pattern is a bound on its variable frequency -- the maximum number $m$ such that some variable occurs exactly $m$ times in the pattern. This paper examines the effect of limiting the variable frequency of all patterns belonging to a class $\Pi$ on the worst-case minimum number of labelled examples needed to uniquely identify any pattern of $\Pi$ in cooperative teaching-learning models. Two such models, the teaching dimension model as well as the preference-based teaching model, will be considered.
BibTeX
@misc{gao2019teaching,
  author = {Ziyuan Gao},
  title = {{The teaching complexity of erasing pattern languages with bounded variable frequency.}},
  year = {2019},
  eprint = {1905.07737},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.07737},
}
Figure