<p>As mentioned in the comments, if you allow some extra additive slack of <span class="math-container">$\varepsilon\in(0,1]$</span> (an input parameter) in the error guarantee, and relax the success probability from one to <span class="math-container">$1-\delta$</span> (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class <span class="math-container">$\mathcal{C}_n$</span> of <span class="math-container">$n$</span>-state DFAs with membership queries.</p>

<p>Indeed, while you do not have accuracy queries <span class="math-container">$\mathrm{AQ}$</span>, those can be easily simulated by sampling in the PAC setting (leading to the <span class="math-container">$\pm\varepsilon$</span> and <span class="math-container">$1-\delta$</span> relaxation).</p>

<p>However, <a href="http://www.jmlr.org/papers/v10/feldman09a.html" rel="nofollow noreferrer">this paper by Vitaly Feldman</a> [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:</p>

<blockquote>
  <p>[...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.</p>
</blockquote>

<p>In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of <span class="math-container">$n$</span>-state DFAs.</p>

<hr>

<p>[Feldman09] Vitaly Feldman. <em>On The Power of Membership Queries in Agnostic Learning.</em> Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.</p>

CC BY-SA 4.0
2019-05-28T18:20:42.050Z
2019-05-28T18:20:42.050Z
Clement C.
<p>Angluin's membership+equivalence query algorithm allows to efficiently and <em>exactly</em> learn a target <span class="math-container">$n$</span>-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?</p>

<p>Here's the formal setting. We have a target concept <span class="math-container">$f^\star$</span> and distribution <span class="math-container">$D$</span> over <span class="math-container">$\Sigma^*$</span>. A membership query <span class="math-container">$MQ:\Sigma^*\to\{0,1\}$</span> returns the value of <span class="math-container">$f^\star(x)$</span>. An "accuracy query" <span class="math-container">$AQ$</span> takes a DFA <span class="math-container">$f$</span> as input and returns
<span class="math-container">$$\mathrm{err}(f):=\sum_{x\in\Sigma^*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$</span> a output.</p>

<p>The goal is to efficiently produce a small (up to <span class="math-container">$n$</span>-states) DFA <span class="math-container">$f$</span> with small (or minimum) <span class="math-container">$\mathrm{err}(f)$</span> using the oracles <span class="math-container">$MQ$</span> and <span class="math-container">$AQ$</span>. [A trivial solution is to brute-force search over all <span class="math-container">$n$</span>-state DFAs.]</p>

<p>Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?</p>

<p>Edit: It was pointed out off-line that for parity-type concepts, <span class="math-container">$\mathrm{err}(f)$</span> might be close to <span class="math-container">$1/2$</span>. So to clarify:
the question seeks not a bound on the worst-case <span class="math-container">$\mathrm{err}(f)$</span>,
but rather an efficient procedure of attaining it via an <span class="math-container">$n$</span>-state DFA.</p>

CC BY-SA 4.0
2019-05-28T17:52:47.363Z
So, if you allow an extra slack of say $\\varepsilon$ (and high probability of success only, instead of probability one), you can always cheaply estimate $\mathrm{err}(f)$ by sampling, and this becomes equivalent to proper PAC-learning DFAs with membership queries, isn't it?
Clement C.
CC BY-SA 4.0
2019-05-28T17:55:10.320Z
Yes, exactly right. I haven't yet figured out if this question and answer have any relevance https://cstheory.stackexchange.com/questions/153/computational-query-complexity-of-sq-learning?rq=1
Aryeh
CC BY-SA 4.0
2019-05-28T17:56:52.820Z
For the agnostic case, where $f^\ast$ may not itself be a DFA, this looks relevant (if I parse the abstract correctly: MQ are not very useful): http://www.jmlr.org/papers/volume10/feldman09a/feldman09a.pdf
Clement C.
CC BY-SA 4.0
2019-05-28T18:00:36.873Z
Hmm, you may be right. If you turn this into a full answer, I'll accept.
Aryeh
CC BY-SA 4.0
2019-05-28T18:01:32.237Z
That still leaves the non-agnostic case open, though (not sure how much of your original motivation that is).
Clement C.
CC BY-SA 4.0
2019-05-28T18:02:40.727Z
What do you mean by non-agnostic? Where $f^\star$ is an $n$-state DFA?
Aryeh
CC BY-SA 4.0
2019-05-28T18:04:18.923Z
Yes -- or even say an $O(n)$-state one (I am not sure what the above result implies in that case).
Clement C.
CC BY-SA 4.0
2019-05-28T18:06:35.330Z
Right... but that's not the case I'm so interested in...
Aryeh
<automata-theory><machine-learning><lg.learning><query-complexity>
Agnostic query learning for DFAs
Aryeh
# Agnostic query learning for DFAs

(Asked by: username_0 on 2019-05-28)

Angluin's membership+equivalence query algorithm allows to efficiently and *exactly* learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?

Here's the formal setting. We have a target concept $f^\star$ and distribution $D$ over $\Sigma^\*$. A membership query $MQ:\Sigma^\*\to\{0,1\}$ returns the value of $f^\star(x)$. An "accuracy query" $AQ$ takes a DFA $f$ as input and returns
$$\mathrm{err}(f):=\sum\_{x\in\Sigma^\*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$ a output.

The goal is to efficiently produce a small (up to $n$-states) DFA $f$ with small (or minimum) $\mathrm{err}(f)$ using the oracles $MQ$ and $AQ$. [A trivial solution is to brute-force search over all $n$-state DFAs.]

Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?

Edit: It was pointed out off-line that for parity-type concepts, $\mathrm{err}(f)$ might be close to $1/2$. So to clarify:
the question seeks not a bound on the worst-case $\mathrm{err}(f)$,
but rather an efficient procedure of attaining it via an $n$-state DFA.

**Tags:** automata-theory, machine-learning, lg.learning, query-complexity
> **Comments:**
> **username_1**: So, if you allow an extra slack of say $\\varepsilon$ (and high probability of success only, instead of probability one), you can always cheaply estimate $\mathrm{err}(f)$ by sampling, and this becomes equivalent to proper PAC-learning DFAs with membership queries, isn't it?  
> **username_0**: Yes, exactly right. I haven't yet figured out if this question and answer have any relevance https://cstheory.stackexchange.com/questions/153/computational-query-complexity-of-sq-learning?rq=1  
> **username_1**: For the agnostic case, where $f^\ast$ may not itself be a DFA, this looks relevant (if I parse the abstract correctly: MQ are not very useful): http://www.jmlr.org/papers/volume10/feldman09a/feldman09a.pdf  
> **username_0**: Hmm, you may be right. If you turn this into a full answer, I'll accept.  
> **username_1**: That still leaves the non-agnostic case open, though (not sure how much of your original motivation that is).  
> **username_0**: What do you mean by non-agnostic? Where $f^\star$ is an $n$-state DFA?  
> **username_1**: Yes -- or even say an $O(n)$-state one (I am not sure what the above result implies in that case).  
> **username_0**: Right... but that's not the case I'm so interested in...  

---

## 1 answers

### Answer by username_1 on 2019-05-28. Score: 2 | Accepted answer

As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}\_n$ of $n$-state DFAs with membership queries.

Indeed, while you do not have accuracy queries $\mathrm{AQ}$, those can be easily simulated by sampling in the PAC setting (leading to the $\pm\varepsilon$ and $1-\delta$ relaxation).

However, [this paper by Vitaly Feldman](http://www.jmlr.org/papers/v10/feldman09a.html) [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:

> [...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.

In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of $n$-state DFAs.

---

[Feldman09] Vitaly Feldman. *On The Power of Membership Queries in Agnostic Learning.* Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.


---

