11institutetext: University of California, Berkeley CA 94720, USA 11email:
<EMAIL_ADDRESS>

# Modularity in Query-Based Concept Learning

Benjamin Caulfield  Sanjit A. Seshia

###### Abstract

We define and study the problem of modular concept learning, that is, learning
a concept that is a cross product of component concepts. If an element’s
membership in a concept depends solely on it’s membership in the components,
learning the concept as a whole can be reduced to learning the components. We
analyze this problem with respect to different types of oracle interfaces,
defining different sets of queries. If a given oracle interface cannot answer
questions about the components, learning can be difficult, even when the
components are easy to learn with the same type of oracle queries. While
learning from superset queries is easy, learning from membership, equivalence,
or subset queries is harder. However, we show that these problems become
tractable when oracles are given a positive example and are allowed to ask
membership queries.

###### Keywords:

Inductive Synthesis, Query-Based Learning, Modularity

##  1 Introduction

Inductive synthesis or inductive learning is the synthesis of programs
(concepts) from examples or other observations. Inductive synthesis has found
application in formal methods, program analysis, software engineering, and
related areas, for problems such as invariant generation (e.g. [1]), program
synthesis (e.g., [2]), and compositional reasoning (e.g. [3]). Most inductive
synthesis follows the query-based learning model, where the learner is allowed
to make queries about the target concept to an oracle. Using the correct set
of oracles can result in the polynomial time learnability of otherwise
unlearnable sets [4]. Using queries for software analysis is becoming
increasingly popular (e.g., [5, 6]). The special nature of query-based
learning for formal synthesis, where a program is automatically generated to
fit a high-level specification through interaction with oracles, has also been
formalized [7].

In spite of this progress, most algorithms for inductive learning/synthesis
are monolithic; that is, even if the concept (program) is made up of
components, the algorithms seek to learn the entire concept from interaction
with an oracle. In contrast, in this paper, we study the setting of modular
concept learning, where a learning problem is analyzed by breaking it into
independent components. If an element’s membership in a concept depends solely
on its membership in the components that make up the concept, learning the
concept as a whole can be reduced to learning the components. We study
concepts that are the Cartesian products (i.e., cross-products) of their
component concepts. Such concept arise in several applications: (i) in
invariant generation, an invariant that is the conjunction of other component
invariants; (ii) in compositional reasoning, an automaton that is the product
of individual automata encapsulating different aspects of an environment
model, and (iii) in program synthesis, a product program whose state space is
the product of the state spaces of individual component programs. Modular
concept learning can improve the efficiency of learning since the complexity
of several query-based learning algorithms depends on the size of the concept
(e.g. automaton) to be learned, and, as is well known, this can grow
exponentially with the number of components. Besides improving efficiency of
learning, from a software engineering perspective, modular concept learning
also has the advantage of reuse of component learning algorithms.

We will focus on the oracle queries given in Table 1 and show several results,
including both upper and lower bounds. We show learning cross-products from
superset queries is no more difficult than learning each individual concept.
Learning cross-products from equivalence queries or subset queries is
intractable, while learning from just membership queries is polynomial, though
somewhat expensive. We show that when a learning algorithm is allowed to make
membership queries and is give a single positive example, previously
intractable problems become tractable. We show that learning the disjoint
unions of sets is easy. Finally, we discuss the computational complexity of
PAC-learning and show how it can be improved when membership queries are
allowed.

Query Name | Symbol | Complexity |  Oracle Definition
---|---|---|---
Single Positive Query | $\emph{1}Pos$ |  $\\#$1$Pos(c)$ |  Return a fixed $x\in c^{*}$
Positive Query | $Pos$ | $\\#Pos(c)$ |  Return an $x\in c^{*}$ that has not yet been given as a positive example (if one exists)
Membership Query | Mem | $\\#\emph{Mem}(c)$ |  Given string $s$, return true iff $s\in c^{*}$
Equivalence Query | EQ | $\\#\emph{EQ}(c)$ |  Given $c\in C$, return true if $c=c^{*}$ otherwise return $x\in(c\backslash c^{*})\cup(c^{*}\backslash c)$
Subset Query | Sub | $\\#\emph{Sub}(c)$ |  Given $c\in C$, return ‘true’ if $c\subseteq c^{*}$ otherwise return some $x\in c\backslash c^{*}$
Superset Query | Sup | $\\#\emph{Sup}(c)$ |  Given $c\in C$, return ‘true’ if $c\supseteq c^{*}$ otherwise return some $x\in c^{*}\backslash c$
Example Query | $\emph{EX}_{\mathcal{D}}$ | $\\#\emph{EX}(c,\mathcal{D})$ |  Samples $x$ from $\mathcal{D}$ and returns $x$ with a label indicating whether $x\in c^{*}$.
Table 1: Types of queries studied in this paper.

###  1.1 A Motivating Example

⬇

int x = ??;

int y = ??;

int a = f(x);

int b = g(y);

$\Phi=\phi_{1}(a)\wedge\phi_{2}(b)$

$x$$y$•$(x_{1},y_{1})$•$(x_{2},y_{2})$

Figure 1: A simple partial program to be synthesized to satisfy a
specification $\Phi$ (left) and the correct set of initial values for $x$ and
$y$ (right).

To illustrate the learning problem, consider the sketching problem given in
Figure 1. Say we wanted to find the set of possible initial values for $x$ and
$y$ that can replace the $??$ values so that the program satisfies $\Phi$.

Looking at the structure of this program and specification, we can see that
the correctness of these two variables are independent of each other. Correct
$x$ values are correct independent of $y$ and vice-versa. Therefore, the set
of settings will be the cross product of the acceptable settings for each
variable. If an oracle can answer queries about correct $x$ or $y$ values
separately, then the oracle can simply learn the acceptable values separately
and take their Cartesian product.

If the correct values form intervals, the correct settings will look something
like the rectangle shown in Figure 1. An algorithm for learning this rectangle
can try to simulate learning algorithms for each interval by acting as the
oracle for each sublearner. For example, if both sublearners need a positive
example, the learner can query the oracle for a positive example. Given the
example $(x_{1},y_{1})$ as shown in the figure, the learner can then pass
$x_{1}$ and $y_{1}$ to the sublearners as positive examples. However, this
does not apply to negative examples, such as $(x_{2},y_{2})$ in the figure. In
this example, $x_{2}$ is in its target interval, but $y_{2}$ is not. The
learner has no way of knowing which subconcept a negative element fails on.
Handling negative counterexamples is one of the main challenges of this paper.

##  2 Notation

In the following proofs, we assume we are given concept classes
$C_{1},C_{2},\dots,C_{k}$ defined over sets $X_{1}$, $X_{2}$, …, $X_{k}$. Each
$c^{*}_{i}$ in each $C_{i}$ is learnable from algorithm $A_{i}$ (called
_sublearners_) using queries to an oracle that can answer any queries in a set
$Q$. This set $Q$ contains the available types of queries and is a subset of
the queries shown in Table 1. For example, if $Q:=\\{\emph{Mem},\emph{EQ}\\}$,
then each $A_{i}$ can make membership and equivalence queries to its
corresponding oracle.

For each query $q\in Q$, we say algorithm $A_{i}$ makes $\\#q_{i}$ (or
$\\#q_{i}(c^{*}_{i})$) many $q$ queries to the oracle in order to learn
concept $c^{*}_{i}$, dropping the index $i$ when necessary . We replace the
term $\\#q$ with a more specific term when the type of query is specified. For
example, an algorithm $A$ might make $\\#\emph{Mem}$ many membership queries
to learn $c$.

Unless otherwise stated, we will assume any index $i$ or $j$ ranges over the
set $\\{1\dots k\\}$. We write $\prod S_{i}$ or $S_{1}\times\dots\times S_{k}$
to refer to the $k$-ary Cartesian product (i.e., cross-product) of sets
$S_{i}$. We use $S^{k}$ to refer to $\prod_{i=1}^{k}S$.

We use vector notation $\vec{x}$ to refer to a vector of elements
$(x_{1},\dots,x_{k})$, $\vec{x}[i]$ to refer to $x_{i}$, and
$\vec{x}[i\leftarrow x^{\prime}_{i}]$ to refer to $\vec{x}$ with
$x^{\prime}_{i}$ replacing value $x_{i}$ at position $i$. We define
${{\boxtimes}}^{k}_{i=1}C_{i}:=\\{\prod c_{i}\mid c_{i}\in
C_{i},i\in\\{1,\dots,k\\}\\}$. We write $\vec{c}$ or $\prod c_{i}$ for any
element of ${{\boxtimes}}^{k}_{i=1}C_{i}$ and will often denote $\vec{c}$ by
$(c_{1},\dots,c_{k})$ in place of $\prod c_{i}$. The target concept will be
represented as $c^{*}$ or $\prod c^{*}_{i}$ which equals
$(c^{*}_{1},\dots,c^{*}_{k})$.

The results below answer the following question:

> For different sets of queries $Q$, what is the bound on the number of
> queries to learn a concept in ${{\boxtimes}}C_{i}$ as a function of each
> $\\#q_{i}$ for each $q\in Q$?

The proofs in this paper make use of the following simple observation:

###### Observation 1

For sets $S_{1},S_{2},\dots,S_{k}$ and $T_{1},T_{2},\dots,T_{k}$, assume
$\prod S_{i}\neq\emptyset$. Then $\prod S_{i}\subseteq\prod T_{i}$ if and only
if $S_{i}\subseteq T_{i}$, for all $i$.

##  3 Simple Lower Bounds

This section introduces some fairly simple lower bounds. We will start with a
lower-bound on learnability from positive examples.

###### Proposition 1

There exist concepts $C_{1}$ and $C_{2}$ that are each learnable from
constantly many positive queries, such that $C_{1}\times C_{2}$ is not
learnable from any number of positive queries.

###### Proof

Let $C_{1}:=\\{\\{a\\},\\{a,b\\}\\}$ and set
$C_{2}:=\\{\mathbb{N},\mathbb{Z}\backslash\mathbb{N}\\}$. To learn the set in
$C_{1}$, pose two positive queries to the oracle, and return $\\{a,b\\}$ if
and only if both $a$ and $b$ are given as positive examples. To learn $C_{2}$,
pose one positive query to the oracle and return $\mathbb{N}$ if and only if
the positive example is in $\mathbb{N}$. An adversarial oracle for
$C_{1}\times C_{2}$ could give positive examples only in the set
$\\{a\\}\times\mathbb{N}$. Each new example is technically distinct from
previous examples, but there is no way to distinguish between the sets
$\\{a\\}\times\mathbb{N}$ and $\\{a,b\\}\times\mathbb{N}$ from these examples.

Now we will show lower bounds on learnability from EQ, Sub, and Mem. We will
see later that this lower bound is tight when learning from membership
queries, but not equivalence or subset queries.

###### Proposition 2

There exists a concept $C$ that is learnable from $\\#q$ many queries posed to
$Q\subseteq\\{\emph{Mem},\emph{EQ},\emph{Sub}\\}$ such that learning $C^{k}$
requires $(\\#q)^{k}$ many queries.

###### Proof

Let $C:=\\{\\{j\\}\mid j\in\\{0\dots m\\}\\}$.

We can learn $C$ in $m$ membership, subset, or equivalence queries by querying
$j\in c^{*}$, $\\{j\\}\subseteq c^{*}$, or $\\{j\\}=c^{*}$, respectively.

However, a learning algorithm for $C^{k}$ requires more than $m^{k}$ queries.
To see this, note that $C^{k}$ contains all singletons in a space of size
$(m+1)^{k}$.

So for each subset query $\\{x\\}\subseteq c^{*}$, if $\\{j\\}\neq c^{*}$, the
oracle will return $j$ as a counterexample, giving no new information.
Likewise, for each equivalence query $\\{j\\}=c^{*}$, if $\\{j\\}\neq c^{*}$,
the oracle can return $j$ as a counterexample. Therefore, any learning
algorithm must query $x\in c^{*}$, $\\{x\\}\subseteq c^{*}$, or
$\\{x\\}=c^{*}$ for $(m+1)^{k}-1$ values of $x$.

##  4 Learning From Superset Queries

This section introduces arguably the simplest positive result of the paper:
when using superset queries, learning cross-products of concepts is as easy as
learning the individual concepts.

Like all positive results in this paper, this is accomplished by algorithm
that takes an oracle for the cross-product concept $\prod c_{i}^{*}$ and
simulates the learning process for each sublearner $A_{i}$ by acting as an
oracle for each such sublearner.

###### Proposition 3

If $Q=\\{\emph{Sup}\\}$, then there is an algorithm that learns any concept
$\prod c^{*}_{i}\in\prod C_{i}$ in $\sum\\#\emph{Sup}(c^{*}_{i})$ queries.

###### Proof

Algorithm 1 learns ${{\boxtimes}}C_{i}$ by simulating the learning of each
$A_{i}$ on its respective class $C_{i}$. The algorithm asks each $A_{i}$ for
superset queries $S_{i}\supseteq c_{i}^{*}$, queries the product $\prod S_{i}$
to the oracle, and then uses the answer to answer at least one query to some
$A_{i}$. Since at least one $A_{i}$ receives an answer for each oracle query,
at most $\sum\\#\emph{Sup}(c^{*}_{i})$ queries must be made in total.

We will now show that each oracle query results in at least one answer to an
$A_{i}$ query (and that the answer is correct). The oracle first checks if the
target concept is empty and stops if so. If no concept class contains the
empty concept, this check can be skipped. At each step, the algorithm poses
query $\prod S_{i}$ to the oracle. If the oracle returns ’yes’ (meaning $\prod
S_{i}\supseteq\prod c^{*}_{i}$), then $S_{i}\supseteq c_{i}^{*}$ for each $i$
by Observation 1, so the oracle answers ’yes’ to each $A_{i}$. If the oracle
returns ’no’, it will give a counterexample
$\vec{x}=(x_{1},\dots,x_{k})\in\prod c^{*}_{i}\backslash\prod S_{i}$. There
must be at least one $x_{i}\not\in S_{i}$ (otherwise, $\vec{x}$ would be in
$\prod S_{i}$). So the algorithm checks $x_{j}\in S_{j}$ for all $x_{j}$ until
an $x_{i}\not\in S_{i}$ is found. Since $\vec{x}\in\prod c^{*}_{i}$, we know
$x_{i}\in c_{i}^{*}$, so $x_{i}\in c_{i}^{*}\backslash S_{i}$, so the oracle
can pass $x_{i}$ as a counterexample to $A_{i}$.

Note that once $A_{i}$ has output a correct hypothesis $c_{i}$, $S_{i}$ will
always equal $c_{i}$, so counterexamples must be taken from some $j\neq i$.

Result: Learn $\prod C_{i}$ from Superset Queries

if  _$\emptyset\in C_{i}$ for some $i$_ then

Query $\emptyset\supseteq\prod c^{*}_{i}$;

if  _$\emptyset\supseteq\prod c^{*}_{i}$_ then

return _$\emptyset$_

for  _$i=1\dots k$_ do

Set $S_{i}$ to initial subset query from $A_{i}$

while  _Some $A_{i}$ has not completed_ do

Query $\prod S_{i}$ to oracle;

if  _$\prod S_{i}\supseteq c^{*}$ _ then

Answer $S_{i}\supseteq c_{i}^{*}$ to each $A_{i}$;

Update each $S_{i}$ to new query;

else

Get counterexample $\vec{x}=(x_{1},\dots,x_{k})$ for  _i = 1 …k_ do

if  _$x_{i}\not\in S_{i}$_ then

Pass counterexample $x_{i}$ to $A_{i}$;

Update $S_{i}$ to new query;

for  _i = 1 …k_ do

if  _$A_{i}$ outputs $c_{i}$_ then

Set $S_{i}:=c_{i}$;

return _$\prod c_{i}$_ ;

Algorithm 1 Algorithm for learning from Subset Queries

##  5 Learning From Membership Queries and One Positive Example

Ideally, learning the cross-product of concepts should be about as easy as
learning all the individual concepts. The last section showed this is not the
case when learning with equivalence, subset, or membership queries. However,
when the learner is given a single positive example and allowed to make
membership queries, the number of queries becomes tractable. This is due to
the following simple observation.

###### Observation 2

Fix sets $S_{1},S_{2},\dots,S_{k}$, points $x_{1},x_{2},\dots,x_{k}$ and an
index $i$. If $x_{j}\in S_{j}$ for all $j\neq i$, then
$(x_{1},x_{2},\dots,x_{k})\in\prod S_{i}$ if and only if $x_{i}\in S_{i}$.

So, given a positive example $\vec{p}$, we can see that $\vec{p}[j\leftarrow
x_{j}]\in\prod c^{*}_{i}$ if and only if $x_{j}\in c^{*}_{j}$. This fact is
used to learn using subset or equivalence queries with the addition of
membership queries and a positive example. The algorithm is fairly similar for
equivalence and subset queries, and is shown as a single algorithm in
Algorithm 2.

###### Proposition 4

If $Q\in\\{\\{\emph{Sub}\\},\\{\emph{EQ}\\}\\}$ and a single positive example
$\vec{p}\in\prod c^{*}_{i}$ is given, then $\prod c^{*}_{i}$ is learnable in
$\sum\\#q_{i}$ queries from $Q$ (i.e., subset or equivalence queries) and
$k\cdot\sum\\#q_{i}$ membership queries.

###### Proof

The learning process for either subset or equivalence queries is described in
Algorithm 2, with differences marked in comments. In either case, once the
correct $c_{j}$ is found for any $j$, $S_{j}$ will equal $c_{j}$ for all
future queries, so any counterexamples must fail on an $i\neq j$.

We separately show for each type of query that a correct answer is given to at
least one learner $A_{i}$ for each subset (resp. equivalence) query to the
cross-product oracle. Moreover, at most $k$ membership queries are made per
subset (resp. equivalence) query, yielding the desired bound.

Subset Queries: For each subset query $\prod S_{i}\subseteq\prod c^{*}_{i}$,
the algorithm either returns ‘yes’ or gives a counterexample
$\vec{x}=(x_{1},\dots,x_{k})\in\prod S_{i}\backslash\prod c^{*}_{i}$. If the
algorithm returns ’yes’, then by Observation 1 $S_{i}\subseteq c^{*}_{i}$ for
all $i$, so the algorithm can return ’yes’ to each $A_{i}$. Otherwise,
$\vec{x}\not\in\prod c^{*}_{i}$, so there is an $i$ such that $x_{i}\not\in
c^{*}_{i}$. By Observation 2 the algorithm can query $\vec{p}[j\leftarrow
x_{j}]$ for all $j$ until the $x_{i}\not\in c^{*}_{i}$ is found.

Equivalence Queries: For each equivalence query $\prod S_{i}=\prod c^{*}_{i}$,
the algorithm either returns ’yes’, or gives a counterexample
$\vec{x}=(x_{1},\dots,x_{k})$. If the algorithm returns ‘yes’, then a valid
target concept is learned. Otherwise, either $\vec{x}\in\prod
S_{i}\backslash\prod c^{*}_{i}$ or $\vec{x}\in\prod c^{*}_{i}\backslash\prod
S_{i}$. In the first case, as with subset queries, the algorithm uses $k$
membership queries to query $\vec{p}[j\leftarrow x_{j}]$ for all $j$. Once the
$x_{i}\not\in c^{*}_{i}$ is found it is given to $A_{i}$ as a counterexample.
In the second case, as with superset queries, the algorithm checks if
$x_{j}\in S_{j}$ for all $j$ until the $x_{i}\not\in c^{*}_{i}$ is found and
given to $A_{i}$.

Result: Learn $\prod c^{*}_{i}\in{{\boxtimes}}C_{i}$

for  _$i=1\dots k$_ do

Set $S_{i}$ to initial query from $A_{i}$

while  _Some $A_{i}$ has not completed_ do

Query $\prod S_{i}$ to oracle;

if  _The Oracle returns ‘yes’_ then

Pass ‘yes’ to each $A_{i}$;

// If Q = {EQ} each sublearner will immediately complete

else

Get counterexample $\vec{x}=(x_{1},\dots,x_{k})$;

if  _$\vec{x}\in\prod c^{*}_{i}\backslash\prod S_{i}$_ then

// Only happens if Q = {EQ}

for  _i = 1 …k_ do

if  _$x_{i}\not\in S_{i}$_ then

Pass counterexample $x_{i}$ to $A_{i}$;

Update $S_{i}$ to new query from $A_{i}$;

else

for  _i = 1 …k_ do

Query $\vec{p}[i\leftarrow x_{i}]\in\prod c^{*}_{i}$;

if  _$\vec{p}[i\leftarrow x_{i}]\not\in\prod c^{*}_{i}$ and $x_{i}\in S_{i}$_
then

Pass counterexample $x_{i}$ to $A_{i}$;

Update $S_{i}$ to new query from $A_{i}$;

Each $A_{i}$ returns some $c_{i}$;

Return $\prod c_{i}$;

Algorithm 2 Algorithm for learning from Equivalence (or Subset) Queries,
Membership Queries, and One Positive Example

Finally, learning from only membership queries and one positive example if
fairly easy.

###### Proposition 5

If $Q=\\{\emph{Mem}\\}$ and a single positive example $\vec{p}\in\prod
c^{*}_{i}$ is given, then $\prod c^{*}_{i}$ is learnable in
$k\cdot\sum\\#\emph{Mem}_{i}(c^{*}_{i})$ membership queries.

###### Proof

The algorithm learns by simulating each $A_{i}$ in sequence, moving on to
$A_{i+1}$ once $A_{i}$ returns a hypothesis $c_{i}$. For any membership query
$M_{i}$ made by $A_{i}$, $M_{i}\in c^{*}_{i}$ if and only if
$\vec{p}[i\leftarrow M_{i}]\in\prod c^{*}_{i}$ by Observation 2. Therefore the
algorithm is successfully able to simulate the oracle for each $A_{i}$,
yielding a correct hypothesis $c_{i}$.

##  6 Learning From Only Membership Queries

We have seen that learning with membership queries can be made significantly
easier if a single positive example is given. In this section we describe a
learning algorithm using membership queries when no positive example is given.
This algorithm makes $O(max_{i}\\{\\#\emph{Mem}_{i}(c^{*}_{i})\\}^{k})$
queries, matching the lower bound given in a previous section.

For this algorithm to work, we need to assume that $\emptyset\not\in C_{i}$
for all $i$. If not, there is no way to distinguish between an empty and non-
empty concept. For example consider the classes
$C_{1}=\\{\\{1\\},\emptyset\\}$ and $C_{2}=\\{\\{j\\}\mid j\in\mathbb{N}\\}$.
It is easy to know when we have learned the correct class in $C_{1}$ or in
$C_{2}$ using membership queries. However, learning from their cross-product
is impossible. For any finite number of membership queries, there is no way to
distinguish between the sets $\emptyset$ and $\\{(1,j)\\}$ for some $j$ that
has yet to be queried.

The main idea behind this algorithm is that learning from membership queries
is easy once a single positive example is found. So the algorithm runs until a
positive example is found from each concept or until all concepts are learned.
If a positive example is found, the learner can then run the simple algorithm
from Proposition 5 for learning from membership queries and a single positive
example.

###### Proposition 6

Algorithm 3 will terminate after making
$O(max_{i}\\{\\#\emph{Mem}_{i}(c^{*}_{i})\\}^{k})$ queries.

###### Proof

The algorithm works by constructing sets $S_{i}$ of elements and querying all
possible elements of $\prod S_{i}$. We will get our bound of
$O(max_{i}\\{\\#\emph{Mem}_{i}(c^{*}_{i})\\}^{k})$ by showing the algorithm
will find a positive example once
$|S_{i}|>max_{i}\\{\\#\emph{Mem}_{i}(c^{*}_{i})\\}$ for all $i$. Since the
algorithm queries all possible elements of $\prod S_{i}$, it is sufficient to
prove that $S_{i}$ will contain an element of $c^{*}_{i}$ once
$|S_{i}|>\\#\emph{Mem}_{i}(c^{*}_{i})$. We will now show this is true for each
$i$.

Assume that the sublearner $A_{i}$ eventually terminates with the correct
answer $c^{*}_{i}$. Let $\vec{q_{i}}:=(q_{1}^{i},q_{2}^{i},\dots)\in
X_{i}^{*}$ be the elements whose membership $A_{i}$ would query assuming it
only received negative answers from an oracle. If $\vec{q_{i}}$ is finite,
then there is some set $N_{i}\in C_{i}$ that $A_{i}$ outputs after querying
all elements in $\vec{q_{i}}$ (and receiving negative answers). We will
consider the cases when $c^{*}_{i}=N_{i}$ and $c^{*}_{i}\neq N_{i}$

Assume $c^{*}_{i}=N_{i}$: Then by our assumption that $\prod
c^{*}_{i}\neq\emptyset$, $N_{i}$ contains some element $n_{i}$. Note that
although sampling elements from a set might be expensive in general, this is
only done for $N_{i}$ and can therefore be hard-coded into the learning
algorithm. The algorithm will start with $S_{i}:=\\{n_{i}\\}$, so $S_{i}$
contains an element of $c^{*}_{i}$ at the start of the algorithm.

Assume $c^{*}_{i}\neq N_{i}$: By our assumption that $A_{i}$ eventually
terminates, $A_{i}$ must eventually query some $q_{j}^{i}\in c^{*}_{i}$
(Otherwise, $A_{i}$ would only receive negative answers and would output
$N_{i}$). So after $j$ steps, $S_{i}$ contains some element of $c^{*}_{i}$.
Since $j<\\#\emph{Mem}_{i}(c^{*}_{i})$, we have that $S_{i}$ contains a
positive example once $|S_{i}|>\\#\emph{Mem}_{i}(c^{*}_{i})$, completing the
proof.

for  _$i=1\dots k$_ do

if  _$N_{i}$ and $n_{i}$ exist_ then

Set $S_{i}:=\\{n_{i}\\}$;

else

Set $S_{i}:=\\{\\}$;

Set $j:=0$;

while  _Some $A_{i}$ has not terminated_ do

for  _i = 1, …, k_ do

if  _$A_{i}$ has not terminated_ then

Get query $q_{j}^{i}$ from $A_{i}$ ;

Pass answer ‘no’ to $A_{i}$;

Set $S_{i}:=S_{i}\cup\\{q_{j}^{i}\\}$;

for  _$\vec{x}\in\prod S_{i}$_ do

Query $\vec{x}\in\prod c^{*}_{i}$;

if  _$\vec{x}\in\prod c^{*}_{i}$_ then

Run Proposition 5 algorithm using $\vec{x}$ as a positive example;

$j:=j+1$;

Algorithm 3 Algorithm for Learning from Membership Queries Only

##  7 Learning from Equivalence or Subset Queries is Hard

The previous section showed that learning cross products of membership queries
requires at most $O(max_{i}\\{\\#\emph{Mem}_{i}(c_{i})\\}^{k})$ membership
queries. A natural next question is whether this can be done for equivalence
and subset queries. In this section, we answer that question in the negative.
We will construct a class $\mathfrak{C}$ that can be learned from $n$
equivalence or subset queries but which requires at least $k^{n}$ queries to
learn $\mathfrak{C}^{k}$.

We define $\mathfrak{C}$ to be the set $\\{\mathfrak{c}(s)\mid
s\in\mathbb{N}^{*}\\}$, where $\mathfrak{c}(s)$ is defined as follows:

$\mathfrak{c}(\lambda):=\\{\lambda\\}\times\mathbb{N}$
$\mathfrak{c}(s):=(\\{s\\}\times\mathbb{N})\cup\mathfrak{c}_{sub}(s)$
$\mathfrak{c}_{sub}(sa):=(\\{s\\}\times(\mathbb{N}\backslash\\{a\\}))\cup\mathfrak{c}_{sub}(s)$

For example,
$\mathfrak{c}(12)=(\\{12\\}\times\mathbb{N})\cup(\\{1\\}\times(\mathbb{N}\backslash\\{2\\}))\cup(\\{\lambda\\}\times(\mathbb{N}\backslash\\{1\\}))$.

An important part of this construction is that for any two strings
$s,s^{\prime}\in\mathbb{N}$, we have that
$\mathfrak{c}(s)\subseteq\mathfrak{c}(s^{\prime})$ if and only if
$s=s^{\prime}$. This implies that a subset query will return true if and only
if the true concept has been found. Moreover, an adversarial oracle can always
give a negative example for an equivalence query, meaning that oracle can give
the same counterexample if a subset query were posed. So we will show that
$\mathfrak{C}$ is learnable from equivalence queries, implying that it is
learnable from subset queries.

We will prove a lower-bound on learning $\mathfrak{C}^{k}$ from subset queries
from an adversarial oracle. This will imply that $\mathfrak{C}^{k}$ is hard to
learn from equivalence queries, since an adversarial equivalence query oracle
can give the exact same answers and counterexamples as a subset query oracle.

###### Proposition 7

There exist algorithms for learning from equivalence queries or subset queries
such that any concept $\mathfrak{c}(s)\in\mathfrak{C}$ can be learned from
$|s|$ queries.

###### Proof

(sketch) Algorithm 4 shows the learning algorithm for equivalence queries, and
Figure 2 show the decision tree. When learning $\mathfrak{c}(s)$ for any
$s\in\mathbb{N}^{*}$, the algorithm will construct $s$ by learning at least
one new element of $s$ per query. Each new query to the oracle is constructed
from a string that is a substring of $s$ If a positive counterexample is
given, this can only yield a longer substring of $s$.

Result: Learns $\mathfrak{C}$

Set $s=\lambda$;

while  _True_ do

Query $\mathfrak{c}(s)$ to Oracle if  _Oracle returns ‘yes’_ then

return $\mathfrak{c}(s)$

if  _Oracle returns $(s^{\prime},m)\in c^{*}\backslash\mathfrak{c}(s)$ _ then

Set $s=s^{\prime}$;

if  _Oracle returns $(s,m)\in\mathfrak{c}(s)\backslash c^{*}$_ then

Set $s=sm$;

Algorithm 4 Learning $\mathfrak{C}$ from equivalence queries.
$\mathfrak{c}(\lambda)$ $\mathfrak{c}(1)$ $\mathfrak{c}(2)$ $...$
$\mathfrak{c}(11)$ $\mathfrak{c}(12)$ $...$
$(\lambda,1)$$(\lambda,2)$$(1,1)$$(1,2)$ Figure 2: A tree representing
Algorithm 4. Nodes are labelled with the queries made at each step, and edges
are labelled with the counterexample given by the oracle.

###  7.1 Showing $\mathfrak{C}^{k}$ is Hard to Learn

It is easy to learn $\mathfrak{C}$, since each new counterexample gives one
more element in the target string $s$. When learning a concept,
$\prod\mathfrak{c}(s_{i})$, it is not clear which dimension a given
counterexample applies to. Specifically, a given counterexample $\vec{x}$
could have the property that $\vec{x}[i]\in\mathfrak{c}(s_{i})$ for all $i\neq
j$, but the learner cannot infer the value of this $j$. It must then proceed
considering all possible values of $j$, requiring exponentially more queries
for longer $s_{i}$. This subsection will formalize this notion to prove an
exponential lower bound on learning $\mathfrak{C}^{k}$. First, we need a
couple definitions.

A concept $\prod\mathfrak{c}(s_{i})$ is _justifiable_ if one of the following
holds:

  * •

For all $i$, $s_{i}=\lambda$

  * •

There is an $i$ and an $a\in\mathbb{N}$ and $w\in\mathbb{N}^{*}$ such that
$s_{i}=wa$, and the $k$-ary cross-product
$\mathfrak{c}(s_{1})\times\dots\times\mathfrak{c}(w)\times\dots\times\mathfrak{c}(s_{k})$
was justifiably queried to the oracle and received a counterexample $\vec{x}$
such that $\vec{x}[i]=(w,a)$.

A concept is _justifiably queried_ if it was queried to the oracle when it was
justifiable.

For any strings $s,s^{\prime}\in\mathbb{N}^{*}$, we write $s\leq s^{\prime}$
if $s$ is a substring of $s^{\prime}$, and we write $s<s^{\prime}$ if $s\leq
s^{\prime}$ and $s\neq s^{\prime}$. We say that the _sum of string lengths_ of
a concept $\prod\mathfrak{c}(s_{i})$ is of size $r$ if $\sum|s_{i}|=r$

Proving that learning is hard in the worst-case can be thought of as a game
between learner and oracle. The oracle can answer queries without first fixing
the target concept. It will answer queries so that for any $n$, after less
than $k^{n}$ queries, there is a concept consistent with all given oracle
answers that the learning algorithm will not have guessed. The specific
behavior of the oracle is defined as follows:

  * •

It will always answer the same query with the same counterexample.

  * •

Given any query $\prod\mathfrak{c}(s_{i})\subseteq c^{*}$, the oracle will
return a counterexample $\vec{x}$ such that for all $i$,
$\vec{x}[i]=(s_{i},a_{i})$, and $a_{i}$ has not been in any query or
counterexample yet seen.

  * •

The oracle never returns ‘yes’ on any query.

The remainder of this section assumes that queries are answered by the above
oracle. An example of answers by the above oracle and the justifiable queries
it yields is given below.

###### Example 1

Consider the following example when $k=2$. First, the learner queries
$(\mathfrak{c}(\lambda),\mathfrak{c}(\lambda))$ to the oracle and receives a
counter-example $((\lambda,1),(\lambda,2))$. The justifiable concepts are now
$(\mathfrak{c}(1),\mathfrak{c}(\lambda))$ and
$(\mathfrak{c}(\lambda),\mathfrak{c}(2))$. The learner queries
$(\mathfrak{c}(1),\mathfrak{c}(\lambda))$ and receives counterexample
$((1,3),(\lambda,4))$. The learner queries
$(\mathfrak{c}(\lambda),\mathfrak{c}(2))$ and receives counterexample
$((\lambda,5),(2,6))$. The justifiable concepts are now
$(\mathfrak{c}(1),\mathfrak{c}(4))$, $(\mathfrak{c}(1\cdot
3),\mathfrak{c}(\lambda))$, $(\mathfrak{c}(5),\mathfrak{c}(2))$ and
$(\mathfrak{c}(\lambda),\mathfrak{c}(2\cdot 6))$. At this point, these are the
only possible solutions whose sum of string lengths is $2$. The graph of
justifiable queries is given in Figure 3.

JQ: $(\mathfrak{c}(\lambda),\mathfrak{c}(\lambda))$ CE:
$((\lambda,1),(\lambda,2))$ JQ: $(\mathfrak{c}(1),\mathfrak{c}(\lambda))$ CE:
$((1,3),(\lambda,4))$ JQ: $(\mathfrak{c}(\lambda),\mathfrak{c}(2))$ CE:
$((\lambda,5),(2,6))$ JQ: $(\mathfrak{c}(1\cdot 3),\mathfrak{c}(\lambda))$ JQ:
$(\mathfrak{c}(1),\mathfrak{c}(4))$ JQ: $(\mathfrak{c}(5),\mathfrak{c}(2))$
JQ: $(\mathfrak{c}(\lambda),\mathfrak{c}(2\cdot 6))$ $1\leq s_{1}$$2\leq
s_{2}$$1,3\leq s_{1}$$4\leq s_{2}$$5\leq s_{1}$$2,6\leq s_{2}$ Figure 3:  The
tree of justifiable queries used in Example 1. Each node lists the justifiable
query (JQ) and counterexample (CE) given for that query. The edges below each
node are labelled with the possible inferences about $s_{1}$ and $s_{2}$ that
can be drawn from the counterexample.

The following simple proposition can be proven by induction on sum of string
lengths.

###### Proposition 8

Let $\prod\mathfrak{c}(s_{i})$ be a justifiable concept. Then for all $w_{1}$,
$w_{2}$, …, $w_{k}$ where for all $i$, $w_{i}\leq s_{i}$,
$\prod\mathfrak{c}(w_{i})$ has been queried to the oracle.

###### Proposition 9

If all justified concepts $\prod\mathfrak{c}(s_{i})$ with sum of string
lengths equal to $r$ have been queried, then there are $k^{r+1}$ justified
queries whose sum of string lengths equals $r+1$

###### Proof

This proof follows by induction on $r$. When $r=0$, the concept
$\prod\mathfrak{c}(\lambda)$ is justifiable.For induction, assume that there
are $k^{r}$ justifiable queries with sum of string lengths equal to $r$. By
construction, the oracle will always chose counterexamples with as-yet unseen
values in $\mathbb{N}$. So querying each concept $\prod\mathfrak{c}(s_{i})$
will yield a counterexample $\vec{x}$ where for all $i$,
$\vec{x}[i]=(s_{i},a_{i})$ for new $a_{i}$. Then for all $i$, this query
creates the justifiable concept $\prod\mathfrak{c}(s^{\prime}_{j})$, where
$s^{\prime}_{j}=s_{j}$ for all $j\neq i$ and
$s^{\prime}_{i}=\mathfrak{c}(s_{i}\cdot a_{i})$. Thus there are $k^{r+1}$
justifiable concepts with sum of string lengths equal to $r+1$.

We are finally ready to prove the main theorem of this section.

###### Theorem 7.1

Any algorithm learning $\mathfrak{C}^{k}$ from subset (or equivalence) queries
requires at least $k^{r}$ queries to learn a concept
$\prod\mathfrak{c}(s_{i})$, whose sum of string lengths is $r$. Equivalently,
the algorithm takes $k^{\sum\\#q_{i}}$ subset (or equivalence) queries.

###### Proof

Assume for contradiction that an algorithm can learn with less than $k^{r}$
queries and let this algorithm converge on some concept
$c=\prod\mathfrak{c}(s_{i})$ after less than $k^{r}$ queries. Since less than
$k^{r}$ queries were made to learn $c$, by Proposition 9, there must be some
justifiable concept $c^{\prime}=\prod\mathfrak{c}(s^{\prime}_{i})$ with sum of
string lengths less than or equal to $r$ that has not yet been queried. By
Proposition 8, we can assume without loss of generality that for all
$w_{i}\leq s_{i}^{\prime}$, $\prod\mathfrak{c}(w_{i})$ has been queried to the
oracle. We will show that $c^{\prime}$ is consistent with all given oracle
answers, contradicting the claim that $c$ is the correct concept. Let
$c_{v}:=\prod\mathfrak{c}(v_{i})$ be any concept queried to the oracle, and
let $\vec{x}$ be the given counterexample. If for all $i$, $v_{i}\leq
s^{\prime}_{i}$, then by construction, there is a $j$ with
$\vec{x}[j]=(v_{j},a_{j})$ such that $v_{j}\cdot a_{j}\leq s^{\prime}_{j}$, so
$\vec{x}$ is a valid counterexample. Otherwise, there is an $i$ such that
$v_{i}\not\leq s^{\prime}_{i}$. So
$(\\{v_{i}\\}\times\mathbb{N})\cap\mathfrak{c}(s^{\prime}_{i})=\emptyset$, so
$\vec{x}$ is a valid counterexample. Therefore, all counterexamples are
consistent with $c^{\prime}$ being correct concept, contradicting the claim
that the learner has learned $c$.

##  8 Disjoint Union

This section discusses learning disjoint unions of concept classes. This is
generally much easier than learning cross-products of classes, since
counterexamples belong to a single dimension in the disjoint union. This
problem uses the same notation as the cross-product case, but we denote the
disjoint union of two sets as
$A\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B$
and the disjoint union of many sets as
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
A_{i}$. We define the concept class of disjoint unions as
$C_{\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}}:=\\{\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
c_{i}\mid c_{i}\in C_{i}\\}$.

The algorithm for learning from membership queries is very easy and won’t be
stated here. Algorithm 5 shows the learning procedure for when
$Q\in\\{\\{\emph{Sub}\\},\\{\emph{Sup}\\},\\{\emph{EQ}\\}\\}$. The correctness
of this algorithm follows from the following simple facts. Assume we have sets
$S_{1},\dots,S_{k}$ and $T_{1},\dots,T_{k}$. Then
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
S_{i}\subseteq\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
T_{i}$ if and only $S_{i}\subseteq T_{i}$ for all $i$. Likewise
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
S_{i}=\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
T_{i}$ if and only if $S_{i}=T_{i}$ for all $i$.

We can summarize these results in the following proposition.

###### Proposition 10

Take any
$Q\in\\{\\{\emph{EQ}\\},\\{\emph{Sub}\\},\\{\emph{Sup}\\},\\{\emph{Mem}\\}\\}$
and assume each concept class $C_{i}$ is learnable from $\\#q{i}$ many
queries. Then there exists an algorithm that can learn the disjoint union of
concept classes
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
c_{i}$ in $\sum\\#q{i}$ many queries.

Result: Learning Disjoint Unions

for  _$i=1\dots k$_ do

Set $S_{i}$ to initial query from $A_{i}$

while  _Some $A_{i}$ has not terminated_ do

Query
$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
S_{i}$ to oracle;

if  _Oracle returns ‘yes’_ then

Pass ’yes’ to each $A_{i}$;

Get updated $S_{i}$ from each $A_{i}$;

else

Get counterexample $x_{i}\in X_{i}$ for some $i$;

Pass $x_{i}$ as counterexample to $A_{i}$;

Get updated $S_{i}$ from each $A_{i}$;

return
_$\mathop{\vphantom{\bigcup}\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\bigcup\cr\cdot\crcr}}}}\displaylimits
S_{i}$_ ;

Algorithm 5 Learning Disjoint Unions

##  9 Efficient PAC-Learning

This sections discusses the problem of PAC-learning the cross products of
concept classes.

Previously, van Der Vaart and Weller [8] have shown the following bound on the
VC-dimension of cross-products of sets:

$\mathcal{V}\mathcal{C}(\prod C_{i})\leq
a_{1}log(ka_{2})\sum\mathcal{V}\mathcal{C}(C_{i})$

Here $a_{1}$ and $a_{2}$ are constants with $a_{1}\approx 2.28$ and
$a_{2}\approx 3.92$. As always, $k$ is the number of concept classes included
in the cross-product.

The VC-dimension gives a bound on the number of labelled examples needed to
PAC-learn a concept, but says nothing of the computational complexity of the
learning process. This complexity mostly comes from the problem of finding a
concept in a concept class that is consistent with a set of labelled examples.
We will show that the complexity of learning cross-products of concept classes
is a polynomial function of the complexity of learning from each individual
concept class.

First, we will describe some necessary background information on PAC-learning.

###  9.1 PAC-learning Background

###### Definition 1

Let $C$ be a concept class over a space $X$. We say that $C$ is efficiently
PAC-learnable if there exists an algorithm $A$ with the following property:
For every distribution $\mathcal{D}$ on $X$, every $c\in C$, and every
$\epsilon,\delta\in(0,1)$, if algorithm $A$ is given access to
$EX(c,\mathcal{D})$ then with probability $1-\delta$, $A$ will return a
$c^{\prime}\in h$ such that $error(c^{\prime})\leq\epsilon$. $A$ must run in
time polynomial in $1/\epsilon$, $1/\delta$, and $size(c)$.

We will refer to $\epsilon$ as the ‘accuracy’ parameter and $\delta$ as the
‘confidence’ parameter. The value of $error(c)$ is the probability that for an
$x$ sampled from $\mathcal{D}$ that $c(x)\neq c^{*}(x)$. PAC-learners have a
_sample complexity_ function
$m_{C}(\epsilon,\delta):(0,1)^{2}\rightarrow\mathbb{N}$. The sample complexity
is the number of samples an algorithm must see in order to probably
approximately learn a concept with parameters $\epsilon$ and $\delta$.

Given a set $S$ of labelled examples in $X$, we will use $A(S)$ to denote the
the concept class the algorithm $A$ returns after seeing set $S$ .

A learner $A$ is an _empirical risk minimizer_ if $A(C)$ returns a $c\in C$
that minimizes the number of misclassified examples (i.e., it minimizes
$|\\{(x,b)\in S\mid c^{*}(x)\neq b\\}|$).

Empirical risk minimizers are closely related to VC dimension and PAC-
learnability as shown in the following theorem (Theorem 6.7 from [9])

###### Theorem 9.1

If the concept class $C$ has VC dimension $d$, then there is a constant, $b$,
such that applying an Empirical Risk Minimizer $A$ to $m_{C}(\epsilon,\delta)$
samples will PAC-learn in $C$, where

$m_{C}(\epsilon,\delta)\leq b\frac{d\cdot
log(1/\epsilon)+log(1/\delta)}{\epsilon}$

Finally, we will discuss the _growth function_. The growth function describes
how many distinct assignments a concept class can make to a given set of
elements. More formally, for a concept class $C$ and $m\in\mathbb{N}$, the
growth function $G_{C}(m)$ is defined by:

$G_{C}(m)=\max_{x_{1},x_{2},\dots,x_{m}}\Big{\lvert}\\{(c(x_{1}),c(x_{2}),\dots,c(x_{m}))\mid
c\in C\\}\Big{\rvert}$

Each $x_{i}$ in the above equation is taken over all possible elements of
$X_{i}$. The VC-dimension of a class $C$ is the largest number $d$ such that
$G_{C}(d)=2^{d}$.

We will use the following bound, a corollary of the Perles-Sauer-Shelah Lemma,
to bound the runtime of learning cross-products [9].

###### Lemma 1

For any concept class $C$ with VC-dimension $d$ and $m>d+1$:

$G_{C}(m)\leq(em/d)^{d}$

###  9.2 PAC-Learning Cross-Products

We now have enough background to describe the strategy for PAC-learning cross-
products. We will just describe learning the cross-product of two concepts. As
above, assume concept classes $C_{1}$ and $C_{2}$ and PAC-learners $A_{1}$ and
$A_{2}$ are given. We define $A_{i}(\epsilon,\delta)$ as the runtime of the
sublearner $A_{i}$ to PAC-learn with accuracy parameter $\epsilon$ and
confidence parameter $\delta$.

Assume that $C_{1}$ and $C_{2}$ have VC-dimension $d_{1}$ and $d_{2}$,
respectively. We can use the bound from van Der Vaart and Weller to get an
upper bound $d$ on the VC-dimension of their cross-product. Assume the
algorithm is given an $\epsilon$ and $\delta$ and there is a fixed target
concept $c^{*}=c_{1}^{*}\times c_{2}^{*}$. Theorem 9.1 gives a bound on the
sample complexity $m_{C_{1}\times C_{2}}(\epsilon,\delta)$. The algorithm will
take a sample of labelled examples of size $m_{C_{1}\times
C_{2}}(\epsilon,\delta)$. Our goal is to construct an Empirical Risk Minimizer
for $C_{1}\times C_{2}$. In our case, $c_{1}\in C_{1}$ and $c_{2}\in C_{2}$.
Therefore, for any sample $S$, an Empirical Risk Minimizer will yield a
concept in $C_{1}\times C_{2}$ that is consistent with $S$. This algorithm is
show in Algorithm 6.

So let $S$ be any such sample the algorithm takes. This set can easily be
split into positive examples $S^{+}$ and negative examples $S^{-}$, both in
$X_{1}\times X_{2}$. The algorithm works by maintaining sets labeled samples
$L_{1}$ and $L_{2}$ for each dimension. For any $(x_{1},x_{2})\in S^{+}$, it
holds that $x_{1}\in c^{*}_{1}$ and $x_{2}\in c^{*}_{2}$ so $(x_{1},\top)$ and
$(x_{2},\top)$ are added to $L_{1}$ and $L_{2}$ respectively. For any
$(x_{1},x_{2})\in S^{-}$, we know that $x_{1}\not\in c^{*}_{1}$ or
$x_{2}\not\in c^{*}_{2}$ (or both), but it is not clear which is true.
However, since the goal is only to create an Empirical Risk Minimizer, it is
enough to find any concepts $C_{1}$ and $C_{2}$ that are consistent with these
samples. In other words, we need to find a $c_{1}\in C_{1}$ and a $c_{2}\in
C_{2}$ such that for every $(x_{1},x_{2})\in S^{+}$, $x_{1}\in c_{1}$ and
$x_{2}\in c_{2}$ and for all $(x_{1},x_{2})\in S^{-}$, either $x_{1}\not\in
c^{*}_{1}$ or $x_{2}\not\in c^{*}_{2}$. One idea would be to try out all
possible assignments to elements in $S^{-}$ and check if any such assignment
fits any possible concepts. This, however, would be exponential in $|S^{-}|$.

Bounding the size of the growth function can narrow this search. Specifically,
let $S_{1}^{-}:=\\{x\mid\exists y,(x,y)\in S^{-}\\}$, let $m=|S_{1}^{-}|$ and
order the elements of $S_{1}^{-}$ by $x_{1},x_{2},\dots,x_{m}$. By the
definition of the growth function and Lemma 1:

$|\\{(c(x_{1}),c(x_{2}),\dots,c(x_{m}))\mid c\in C_{1}\\}|\leq
G_{C_{1}}(m)\leq(em/d)^{d}$

In other words, there are less than $(em/d)^{d}$ assignments of truth values
to elements of $S_{1}^{-}$ that are consistent with some concept in $C_{1}$.
If the algorithm can check every $c_{1}\in C_{1}$ consistent with $S^{+}$ and
$S^{-}_{1}$, it can then call $A_{2}$ to see if there is any $c_{2}\in C_{2}$
such that $(c_{1}\times c_{2})$ assigns true to every element in $S^{+}$ and
false to every element in $S^{-}$.

Finding these consistent elements of $C_{1}$ is made easier by the fact that
we can check whether partial assignments to $S^{-}_{1}$ are consistent with
any concept in $C_{1}$. As mentioned above, it starts by creating the sets
$L_{1}$ and $L_{2}$ containing all samples in the first and second dimension
of $S^{+}$, respectively. It then iteratively adds labeled samples from
$S^{-}$. At each step, the algorithm chooses one element $(x_{1},x_{2})\in
S^{-}$ at a time and checks which possible assignments to $x_{1}$ are
consistent with $L_{1}$. If $(x_{1},\bot)$ is consistent, it adds
$(x_{1},\bot)$ to $L_{1}$ and calls $RecursiveFindSubconcepts$ on $L_{1}$ and
$L_{2}$. If $(x_{1},\top)$ is consistent with $C_{1}$, then the algorithm adds
$(x_{1},\top)$ to $L_{1}$ and $(x_{2},\bot)$ to $L_{2}$ and calls
$RecursiveFindSubconcepts$. In either case, if an assignment is not
consistent, no recursive call is made. We can summarize these results in the
following theorem.

###### Theorem 9.2

Let concept classes $C_{1}$ and $C_{2}$ have VC-dimension $d_{1}$ and $d_{2}$,
respectively. There exists a PAC-learner for $C_{1}\times C_{2}$ that can
learn any concept using a sample of size $m=((d_{1}+d_{2})\cdot
log(1/\epsilon)+log(1/\delta))/\epsilon$. The learner requires time
$O(m^{d_{1}}(A_{1}(1/m,log(\delta))+A_{2}(1/m,log(\delta))))$.

Result: Find Subconcepts Consistent with Sample

Input: $S^{+}$: Set of positive examples in $X_{1}\times X_{2}$

$S^{-}$: Set of negative examples in $X_{1}\times X_{2}$

$\delta:$ Confidence parameter in $(0,1)$

FindSubconcepts  _( $S^{+}$, $S^{-}$, $\delta$)_

$\delta^{\prime}:=\delta/(|S^{-}|G_{C_{1}}(|S^{-}|)+G_{C_{2}}(|S^{-}|))$;

$\epsilon^{\prime}:=1/|S|$;

// $L_{1}$: Labelled samples in $X_{1}$

$L_{1}:=\\{(x_{1},\top)\mid\exists y,(x_{1},y)\in S^{+}\\}$;

// $L_{2}$: Labelled samples in $X_{2}$

$L_{2}:=\\{(x_{2},\top)\mid\exists y,(y,x_{2})\in S^{+}\\}$;

$U:=S^{-}$;

return RecursiveFindSubconcepts($L_{1}$, $L_{2}$, $U$, $\epsilon^{\prime}$,
$\delta^{\prime}$) ;

RecursiveFindSubconcepts  _( $L_{1}$, $L_{2}$, $U$, $\epsilon^{\prime}$,
$\delta^{\prime}$):_

// Run once all labels are assigned to the first dimension of $U$

// Attempts to find concept in $C_{2}$ consistent with all labels given in
$L_{2}$

if  _$U=\emptyset$_ then

if  _$A_{2}(L_{2},\epsilon^{\prime},\delta^{\prime})$_ then

return
_$(A_{1}(L_{1},\epsilon^{\prime},\delta^{\prime}),A_{2}(L_{2},\epsilon^{\prime},\delta^{\prime}))$_
;

else

$\bot$;

Get $(x_{1},x_{2})\in U$;

$U:=U\backslash\\{(x_{1},x_{2})\\}$;

// Attempts to label $x_{1}$ as false in $c^{*}_{1}$

if
_$A_{1}(L_{1}\cup\\{(x_{1},\bot)\\},\epsilon^{\prime},\delta^{\prime})\neq\bot$_
then

$c=RecursiveFindSubconcepts(L_{1}\cup\\{(x_{1},\bot)\\},L_{2},U,\epsilon^{\prime},\delta^{\prime})$;

if  _$c\neq\bot$_ then

return c;

// Attempts to label $x_{1}$ as true in $c^{*}_{1}$

if
_$A_{1}(L_{1}\cup\\{(x_{1},\top)\\},\epsilon^{\prime},\delta^{\prime})\neq\bot$_
then

$c=RecursiveFindSubconcepts(L_{1}\cup\\{(x_{1},\top)\\},L_{2}\cup\\{(x_{2},\bot)\\},U,\epsilon^{\prime},\delta^{\prime})$;

if  _$c\neq\bot$_ then

return c ;

Algorithm 6 Learning Disjoint Unions

###  9.3 Efficient PAC-learning with Membership Queries

Although polynomial, the complexity of PAC-learning cross-products from a EX
oracle is fairly expensive. We will show that when a learner is allowed to
make membership queries, PAC-learning cross-products becomes much more
efficient. This is due to the previously shown technique, which uses
membership queries and a single positive example to determine on which
dimensions a negatively labelled example fails.

In this case, assuming that $\emptyset\in{{\boxtimes}}C_{i}$, we can ignore
the assumption that a positive example is given. If no positive example
appears in a large enough labeled sample, the the algorithm can pose
$\emptyset$ as the hypothesis.

If $S$ does contain a positive example $\vec{p}$, then $S$ can be broken down
into labeled samples for each dimension $i$. The algorithm initialize the sets
of positive and negative examples to
$S^{+}_{i}:=\\{\vec{x}[i]\mid(\vec{x},\top)\in S\\}$ and $S^{-}_{i}:=\\{\\}$,
respectively. For each $(\vec{x},\bot)\in S$, a membership queries
$\vec{p}[i\leftarrow\vec{x}[i]]\in\prod c^{*}_{i}$. If so, $\vec{x}[i]$ is
added to $S^{+}_{i}$. Otherwise it is added to $S^{-}_{i}$. This labelling is
correct by Observation 2. The set of labelled examples
$S_{i}:=(S_{i}^{+}\times\\{\top\\})\cup(S_{i}^{-}\times\\{\bot\\})$ is then
passed to the sublearner $A_{i}$. $A_{i}$ is run on $S_{i}$ with accuracy
parameter $\epsilon^{\prime}:=\epsilon/k$ and confidence parameter
$\delta^{\prime}:=\delta/k$ .

###### Proposition 11

The algorithm described above PAC-learns from the concept class
${{\boxtimes}}C_{i}$ with accuracy $\epsilon$ and confidence $\delta$. It
makes $m_{C}(\epsilon,\delta)$ queries to EX, $k\cdot m_{C}(\epsilon,\delta)$
membership queries, and has runtime $O(\sum A_{i}(\epsilon/k,\delta/k))$.

##  10 Conclusion

The final collection of query complexities for learning cross products is
given in Figure 4. All of the bounds are tight, except for the problem of
learning with superset queries, membership queries, and one positive example.
Additionally, learning disjoint unions from any
$Q\in\\{\\{\emph{EQ}\\},\\{\emph{Sub}\\},\\{\emph{Sup}\\}\\}$ requires as many
queries as is needed to learn each concept separately. Finally, we have shown
that the computational complexity of PAC learning cross-products of concepts
is a polynomial function of learning the individual concepts.

| Only $Q$ |  $Q$ with Mem and $\emph{1}Pos$
---|---|---
$Q\downarrow$ | #q | #_Mem_ | #q
Pos | Not Possible | Not Possible | Not Possible
_Sup_ | $\sum\\#\emph{Sup}$ | $0$ | $\sum\\#\emph{Sup}$
_Mem_ | $(max_{i}\\{\\#\emph{Mem}_{i}\\})^{k}$ | $\sum\\#\emph{Mem}_{i}$ | $\sum\\#\emph{Mem}_{i}$
_Sub_ | $k^{\sum\\#\emph{Sub}_{i}}$ | $k\sum\\#\emph{Sub}_{i}$ | $\sum\\#\emph{Sub}_{i}$
_EQ_ | $k^{\sum\\#\emph{EQ}_{i}}$ | $k\sum\\#\emph{EQ}_{i}$ | $\sum\\#\emph{EQ}_{i}$
Figure 4:  Final collection of query complexities for learning cross products.
The rows represents the set $Q$ of queries needed to learn each $C_{i}$. The
columns determine whether the cross product is learned from queries in just
$Q$ or $Q\cup\\{\emph{Mem},\emph{1}Pos\\}$. In the latter case, the column is
separated to track the number of membership queries and queries in $Q$ that
are needed. The value $k$ denotes the number of dimensions (i.e., concept
classes) included in the cross-product.

## References

  * [1] Pranav Garg, Christof Löding, P Madhusudan, and Daniel Neider.  Ice: A robust framework for learning invariants.  In International Conference on Computer Aided Verification, pages 69–87. Springer, 2014.
  * [2] Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat.  Combinatorial sketching for finite programs.  ACM Sigplan Notices, 41(11):404–415, 2006.
  * [3] Jamieson M Cobleigh, Dimitra Giannakopoulou, and Corina S Păsăreanu.  Learning assumptions for compositional verification.  In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 331–346. Springer, 2003.
  * [4] Dana Angluin.  Queries and concept learning.  Machine learning, 2(4):319–342, 1988.
  * [5] Frits W. Vaandrager.  Model learning.  Commun. ACM, 60(2):86–95, 2017.
  * [6] Falk Howar and Bernhard Steffen.  Active automata learning in practice.  In Machine Learning for Dynamic Software Analysis: Potentials and Limits, pages 123–148. Springer, 2018.
  * [7] Susmit Jha and Sanjit A Seshia.  A theory of formal synthesis via inductive learning.  Acta Informatica, 54(7):693–726, 2017.
  * [8] Aad Van Der Vaart and Jon A Wellner.  A note on bounds for VC dimensions.  Institute of Mathematical Statistics collections, 5:103, 2009.
  * [9] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.