Query Learning Bounds for Advice and Nominal Automata

Let $X$ be a set (the instance space). A concept is a function $C:X\to\{0,1\}$, and a concept class $\mathcal{C}$ on $X$ is a nonempty set of concepts. We note that a concept is sometimes equivalently defined as a subset of $X$, but for our purposes it will be easier to work with functions. Fix a concept $C\in\mathcal{C}$, which we call the target, and another concept class $\mathcal{H}\supseteq\mathcal{C}$, which we call the hypothesis class. An equivalence query (EQ) consists of a hypothesis $H\in\mathcal{H}$, to which the oracle answers yes if $H=C$, or with a counterexample $x\in X$ for which $H(x)\neq C(x)$. A membership query (MQ) consists of an element $x\in X$, to which the oracle responds with the value of $C(x)$. The learning procedure proceeds interactively in rounds: in each round, the learner poses a query to the oracle, and the oracle responds with the corresponding answer. The learner is allowed to choose queries based on the responses to previous queries, and succeeds if they submit the target as an equivalence query. In EQ-learning, the learner is only allowed to submit equivalence queries, while in (EQ+MQ)-learning, the learner can use both equivalence and membership queries.

A significant stream of prior work studied bounds for the query complexity of $\mathcal{C}$ with hypotheses from $\mathcal{H}$ in terms of combinatorial complexity measures of $\mathcal{C}$ and $\mathcal{H}$ [14, 3, 8, 13]. These bounds are formulated in terms of the Littlestone dimension, consistency dimension, and strong consistency dimension (also known as the dual Helly number), which we define now.

A binary element tree is a complete binary tree whose internal nodes are labeled by elements of $X$. A binary element tree $T$ is shattered by $\mathcal{C}$ if there is a way to label all the leaves of $T$ with elements of $\mathcal{C}$ such that the following condition holds: given a leaf node labeled by $A\in\mathcal{C}$, for each internal node above $A$ labeled by $x\in X$, $A(x)=1$ if and only if the (unique) path from the root to $A$ goes through the left child of $x$.

An example of a (labelled) binary element tree of height 2 is given below, where $x_{0},x_{1},x_{2}\in X$, and $C_{0},C_{1},C_{2},C_{3}\in\mathcal{C}$:

This tree is shattered exactly when $C_{0}(x_{0})=C_{0}(x_{1})=1$, $C_{1}(x_{0})=1$ but $C_{1}(x_{1})=0$, $C_{2}(x_{0})=0$ but $C_{2}(x_{2})=1$, and $C_{3}(x_{0})=C_{3}(x_{2})=0$.

We now define consistency dimension. For the following bulleted definitions, let $A,B$ be partial functions from $X$ to $\{0,1\}$.

• •

  $\operatorname{dom}(A)$ denotes domain of $A$.

• •

  The size of $A$ refers to the cardinality of $\operatorname{dom}(A)$.

• •

  For a set $Y\subseteq\operatorname{dom}(A)$, the restriction of $A$ to $Y$ is the partial function $A|_{Y}$ defined by $A|_{Y}(x)=A(x)$ for $x\in Y$ and undefined outside of $Y$.

• •

  We say that $B$ extends $A$ if $\operatorname{dom}(A)\subseteq\operatorname{dom}(B)$ and $B|_{\operatorname{dom}(A)}=A$. On the other hand, we say that $A$ is a restriction of $B$.

• •

  Given a concept class $\mathcal{C}$, $A$ is $n$-consistent with $\mathcal{C}$ if every size $n$ restriction of $A$ has an extension in $\mathcal{C}$. Otherwise, $A$ is $n$-inconsistent.

It is often easier to work concretely with the contrapositive characterization of consistency dimension. Our proofs of bounds on consistency dimension will go through this direction.

In this subsection, we set notation and terminology for deterministic finite automata and regular languages, and briefly review the Myhill-Nerode theorem.

As is typical, $\Sigma^{*}$ will denote the set of finite strings over $\Sigma$. Given an input string $x=x_{1}x_{2}\cdots x_{n}\in\Sigma^{*}$, and a DFA $M$, define the run of $M$ on $x$ to be the sequence of states $\alpha_{0},\ldots,\alpha_{n}\in Q$ such that $\alpha_{0}=q_{0}$, and for $1\leq i\leq n$, we have that $\delta(\alpha_{i-1},x_{i})=\alpha_{i}$. A string $x\in\Sigma^{*}$ is accepted by $M$ if the last state appearing in the run of $M$ on $x$ is in $F$. A language is a function $L:\Sigma^{*}\to\{0,1\}$. We note that languages are often defined as subsets of $\Sigma^{*}$, but here we use functions in order to align with our definition of a concept. A language is recognized by a DFA $M$ if $M$ accepts a string $x$ if and only if $x\in L$. We say that a language $L$ is regular if it is recognized by some DFA.

The Myhill-Nerode theorem provides a useful syntactic characterization of regular languages. Given a language $L:\Sigma^{*}\to\{0,1\}$, define an equivalence relation $\equiv_{L}$ on $\Sigma^{*}$ as follows: for strings $x,y\in\Sigma^{*}$, we say that $x\equiv_{L}y$ iff $L(xz)=L(yz)$ for all $z\in\Sigma^{*}$.

In this subsection, we give an introduction to automata with advice. For a more comprehensive overview, see [15].

Given an input string $x=x_{1}x_{2}\cdots x_{n}\in\Sigma^{*}$ and advice DFA $M$, define the run of $M$ on $x$ to be the sequence of states $\alpha_{0},\ldots,\alpha_{n}\in Q$ such that $\alpha_{0}=q_{0}$, and for $1\leq i\leq n$, we have that $\delta(\alpha_{i-1},x_{i},A_{i})=\alpha_{i}$. A string $x\in\Sigma^{*}$ is accepted by $M$ if the last state appearing in the run of $M$ on $x$ is in $F$. A language $L$ is recognized by an advice DFA $M$ if $M$ accepts a string $x$ if and only if $x\in L$. We say that a language $L$ is regular with advice if it is recognized by some advice DFA.

Advice DFAs extend classical DFAs with the addition of the (infinite) advice string $A$ (which is fixed beforehand as part of the automaton). The advice string is read in parallel with the input string; i.e., when $M$ reads the $n^{\text{th}}$ character of the input, it also has access to the $n^{\text{th}}$ character of the advice when deciding which transition to make. One way to think about the advice string is that it allows the transition function to vary at each step of the computation (although at a fixed step $i$, the transition behavior is the same regardless of the input string).

Advice DFAs satisfy a Myhill-Nerode characterization, under a variant of the $\equiv_{L}$ relation. Define an equivalence relation $\equiv_{L,m}$ on $\Sigma^{m}$ by $x\equiv_{L,m}y$ iff $xz\in L\iff yz\in L$ for all $z\in\Sigma^{*}$. Notice that $\equiv_{L,m}$ is simply $\equiv_{L}$ restricted to strings of length $m$.

In general, the bound of $2n$ states in the second item is tight. A example witnesing this is given in Appendix 0.A.1. Also, note that this statement is more precise than the original version in [15]; in particular, the relationship between the number of states and the number of $\equiv_{L,m}$-classes does not appear in the original theorem. However, this relationship is easily derived from its proof.

For the remainder of the section, fix $k\in\mathbb{N}$ and let $\Sigma$ be an alphabet of size $k$. We will not fix the advice alphabet $\Gamma$; however, notice that if we are constructing an automaton with at most $n$ states, we may take $\Gamma$ to have size $n^{nk}$, since the advice string can be thought of as coding the transition function at a given step, and there are $n^{nk}$ functions from $Q\times\Sigma\to Q$ (possible transition functions).

Note that the language consisting of the finite prefixes of any $\omega$-word $A$ is regular with advice $A$, and each of these languages is distinct, so there are uncountably many languages that are regular with advice. Thus we cannot have any finitary representation of arbitrary languages that are regular with advice. Hence, we consider the case where we restrict to strings of bounded length. Let $\mathcal{L}^{\text{adv}}_{k}(n,m)$ denote the set

and let $\mathcal{E}_{k}(n,m)$ denote the set

By Theorem 3.1, $\mathcal{L}^{\text{adv}}_{k}(n,m)\subseteq\mathcal{E}_{k}(n,m)\subseteq\mathcal{L}^{\text{adv}}_{k}(2n,m)$ for any $n,m\in\mathbb{N}$. Because of this, it is more convenient to compute the query complexity of $\mathcal{L}^{\text{adv}}_{k}(n,m)$ with queries $\mathcal{L}^{\text{adv}}_{k}(2n,m)$.

Combining Propositions 1 and 2 with Theorem 2.1(1), we obtain:

In this subsection, we give an introduction to nominal automata. For a more comprehensive treatment, see [5].

As mentioned in the introduction, one must leverage some underlying structure to properly generalize automata theory to infinite alphabets. For example, consider the alphabet $A=\mathbb{N}$, and define $L:A^{*}\to\{0,1\}$ by $L(w)=1$ if and only if $w=aa$ for some $a\in A$. An equivalently defined language over a finite alphabet is easily seen to be regular, and so we expect this example to be “regular” as well. We can draw an infinite automaton that recognizes $L$ in the following way:

Notice that in some cases, we have combined infinitely many transitions into a single arrow—here, we assume that we are able to compare whether or not two data values are equal, and so are leveraging a form of symmetry. We can further condense this representation into an actually finite diagram:

We can compress the distinct states for each character from $A$ into a single “state” because it is enough to be able to compare whether or not the first and second characters read are equal or not. In order to formalize this intuition, we use the notion of nominal sets. Note: we do not work in the most general setting of [5], and instead only focus on what they call the equality symmetry. However, it is reasonable to expect that our results can generalize to other well-behaved symmetries.

Given a set $A$, let $\operatorname{Sym}(A)$ denote the group of permutations on $A$, i.e., the set of bijections from $A$ to $A$ with the operation of function composition. For the rest of the paper, let $G$ denote $\operatorname{Sym}(\mathbb{N})$ Given a set $X$, a (left) action of $G$ on $X$ is an operation $\cdot:G\times X\to X$ such that:

1. 1.

   for all $x\in X$, $e\cdot x=x$, where $e$ is the identity function on $\mathbb{N}$, and

2. 2.

   for all $\pi,\pi^{\prime}\in G$ and $x\in X$, $(\pi\circ\pi^{\prime})\cdot x=\pi\cdot(\pi^{\prime}\cdot x)$.

An equivalent characterization of an element having least support is that the intersection of any two finite supports of $x$ also supports $x$.

In the literature on nominal sets, this is simply referred to as the dimension of $X$. However, in order to prevent confusion with other notions of dimension used in this paper, we will use the term nominal dimension.

By 1, elements in the same orbit have the same size of least support, so orbit-finite nominal sets have finite nominal dimension.

For $i=1,\ldots,n$, let $X_{i}$ be a set with an action of $G$ on $X_{i}$. The pointwise action of $G$ on $\prod_{i=1}^{n}X_{i}$ is the action given by $\pi\cdot(x_{1},\ldots,x_{n})=(\pi\cdot x_{1},\ldots,\pi\cdot x_{n})$.

The following lemmas demonstrate how equivariant functions behave nicely with orbits and supports.

We will work extensively with quotients by equivariant equivalence relations, so we state some important general facts about them. Recall that if $R$ is an equivalence relation on $X$, $X/R$ denotes the set of equivalence classes of $R$, and is called the quotient of $X$ by $R$.

A proof of 6 is given in Appendix 0.B.1.

We are now ready to define nominal DFAs and state the nominal Myhill-Nerode theorem. Fix an orbit-finite nominal set $A$, which we will call the $G$-alphabet. The action of $G$ on $A$ naturally extends to $A^{*}$: given a string $w\in A^{*}$, $\pi\cdot w$ is the string obtained by letting $\pi$ act on each individual character of $w$.

As a shorthand, we say that a nominal DFA $M$ has $n$ orbits or nominal dimension $k$ when the state set has $n$ orbits or nominal dimension $k$.

Given an input string $x=x_{1}x_{2}\cdots x_{n}\in A^{*}$, define the run of $M$ on $x$ to be the sequence of states $\alpha_{0},\ldots,\alpha_{n}\in Q$ such that $\alpha_{0}=q_{0}$, and for $1\leq i\leq n$, we have that $\delta(\alpha_{i-1},x_{i})=\alpha_{i}$. A string $x\in\Sigma^{*}$ is accepted by $M$ if the last state appearing in the run of $M$ on $x$ is in $F$. We say that a langauge $L$ is recognized by a nominal DFA $M$ if $M$ accepts a string $x$ if and only if $x\in L$. As noted in [5, Definition 3.1], the language recognized by a nominal DFA must be a $G$-language. We say that a $G$-language $L$ is nominal regular if it is recognized by some nominal DFA.

Let $L$ be a $G$-language, and define the usual relation $\equiv_{L}$ on $A^{*}$ by: $x\equiv_{L}y$ if and only if for all $z\in A^{*}$, we have $L(xz)=L(yz)$. This relation is equivariant (see [5, Lemma 3.4]), and hence by 4, $A^{*}/\equiv_{L}$ is a nominal set. We will write $[x]_{L}$ to denote the $\equiv_{L}$-equivalence class of a string $x\in A^{*}$.

Note that this statement is more precise than the original version in [5]; in particular, the conditions on the number of orbits and the nominal dimension do not appear in the original theorem. However, these conditions are easily derived from its proof. For completeness, a proof of the correspondence between the number of orbits and the nominal dimension is given in Appendix 0.B.2.

To prove bounds on the Littlestone dimension of nominal automata, we wish to bound the number of possible nominal automata. Since automata involve transition functions, we will need to understand products of nominal sets. Nominality is easily seen to be preserved under Cartesian products:

On the other hand, in the most general setting, products of orbit-finite nominal sets need not be orbit-finite [5, Example 2.5]. However, in our context of $\operatorname{Sym}(\mathbb{N})$, products of orbit-finite sets are known to be orbit-finite [5, Section 10]. We will need an explicit bound on the number of orbits of products of orbit-finite sets, which is the purpose of the following discussion.

For a natural number $k$, define $\mathbb{N}^{(k)}:=\{(a_{1},\ldots,a_{k})\mid a_{i}\neq a_{j}\text{ for }i\neq j\}$. $\mathbb{N}^{(k)}$ is a single-orbit nominal set when equipped with the pointwise action of $G$.

4 is stated but not proven in [16]. For completeness, we include a proof in Appendix 0.B.3. In light of 4, we can find bounds on the number of orbits of a product of nominal sets by bounding the value of $f_{\mathbb{N}}$. We do so for the case $n=2$:

The proof of 5 is given in Appendix 0.B.4. 5 will help us to calculate an explicit upper bound on the Littlestone dimension of nominal automata later, but we can first use it to substantiate a comment from the introduction about previously known query bounds.

The bound in [16, Corollary 1] involves a $f_{\mathbb{N}}(p(n+m),pn(k+k\log k+1))$ factor, where $n$ is the number of orbits of the state set of the target automaton, $k$ is the nominal dimension of the target automaton, $p$ is the nominal dimension of the alphabet, and $m$ is the length of the longest counterexample. Notice that $f_{\mathbb{N}}$ is non-decreasing in all coordinates. Therefore, $f_{\mathbb{N}}(p(n+m),pn(k+k\log k+1))$ is lower bounded by both $f_{\mathbb{N}}(pn,pnk)$ and $f_{\mathbb{N}}(m,nk)$. Applying the lower bounds from 5 yields the following:

We are now at a point where we can calculate a bound on the number of possible nominal DFAs and hence bound the Littlestone dimension. First, we state a general result on the number of single-orbit nominal sets:

The proof of 6 is given in Appendix 0.B.5. We note that it is a completely general result about nominal sets and may be of independent interest. For us, it will allow us to bound the number of possible state sets.

Now, we count the number of possible transition behaviors. Fix an input alphabet $A$, where $A$ has $\ell$ orbits and nominal dimension $p$.

The proof of 9 is given in Appendix 0.B.6

Let $\mathcal{L}^{\text{nom}}_{A}(n,k)$ denote the set of $G$-languages over $A$ recognized by a nominal DFA with at most $n$ orbits and nominal dimension at most $k$.

It remains to bound the consistency dimension. To do this, we need to show that if $L$ is a language that is not recognized by a nominal DFA with at most $n$ orbits and nominal dimension at most $k$, then there is a set of strings $B$ of bounded size such that the restriction of $L$ to $B$ cannot be extended to any $G$-language recognized by such a nominal DFA. By the nominal Myhill-Nerode theorem, $L$ not being recognized by a nominal DFA with at most $n$ orbits and nominal dimension at most $k$ is equivalent to $A^{*}/\equiv_{L}$ either having greater than $n$ orbits or having nominal dimension greater than $k$. We first address the case where $A^{*}/\equiv_{L}$ has large nominal dimension.

The proof of this lemma is given in Appendix 0.B.7.