<p><strong>The discussion in the comments below indicades that I have misunderstood the question.  My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.</strong></p>

<hr>

<p>Because the target distribution is fixed for every target $f^* \in F$, the PAC-sample upper bound applies (this follows from the fact that the target distribution for this bound can even completely depend on $f^*$). Hence, 
$$
m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)
$$
examples should suffice to find a hypothesis of error $\le \epsilon$ w.p. $\ge 1-\delta$. Note -- after seeing these examples, one needs to find a consistent hypothesis from $F$, and this may not be tractable.</p>

<p>On the other hand, one can get a nearly matching lower bound even for the case of $p=q=U$, the uniform distribution, where $m \ge \Omega(\mathrm{VC}(F))$ examples are still required (this can be improved slightly).</p>

<p>The variational distance between $p$ and $q$, as well as $k$ may play a role in the small gap between these bounds, but I doubt it.</p>

CC BY-SA 3.0
2013-04-10T17:01:10.793Z
The typical PAC-learning setting has an oracle $(f,D)$ that draws a sample $x$ from distribution $D$, and returns $(x, f(x))$. This is not the setting described in Suresh's question or the blog post that inspired it: http://bit.ly/YtwdST. In both of these, the oracle *is* the function $f$, and the learner is free to submit any element from the instance set (bitstrings of length $n$). Lev, does your answer assume an oracle of the first type, or the second type? If the second type, are we still talking about PAC-learning?
Keki Burjorjee
CC BY-SA 3.0
2013-04-10T18:15:17.617Z
I see. In PAC, the "oracle" usually is thought of as a button which returns $(x, f(x))$ where $x \sim D$.  The Oracle you describe is called a "membership query" to $f$.  My answer only applies to the former.  If you only membership queries, how do you find out any information about $p$ or $q$ using Suresh's framework?  Let's say $p=q$ for simplicity.
Lev Reyzin
CC BY-SA 3.0
2013-04-10T19:08:13.460Z
Thanks for that clarification. So in the case Suresh described, the  "membership query" oracle works as follows (I presume you've put this entity in quotes because the oracle can return a real value, not just a boolean is-a-member/not-a-member answer): if the parity of the effective attributes is 1, then the result returned is drawn from distribution $p$. Otherwise, the result is drawn from distribution $q$. There's an additional wrinkle. The oracle remembers all its previous answers, and returns them if queried with the same input. In other words, it is deterministic.
Keki Burjorjee
CC BY-SA 3.0
2013-04-10T19:44:46.790Z
I don't understand.  If the oracle is simply a function $f$ and you query it by giving it $x$, doesn't it just return $f(x)$? How does $p$ or $q$ come in to play if the learner is generating $x$ himself?  I think I've been failing to understand this basic point all along...
Lev Reyzin
CC BY-SA 3.0
2013-04-10T21:57:07.867Z
For $p=\mathcal N(+0.25, 1)$ and $q = \mathcal N(-0.25, 1)$, the pseudocode of the oracle for the problem with the "wrinkle" is given at the bottom of this reddit comment: http://bit.ly/XvVMC4 (`def fitness() ...`). I can't inline the code because SE doesn't allow newlines in comments. To obtain the "non-wrinkly" version of the problem, just remove the line `random_number_generator.set_seed(x)`.
Keki Burjorjee
CC BY-SA 3.0
2013-04-11T00:26:39.417Z
I don't understand your reddit comment either -- is the oracle the "fitness" function?  Can you simply explain how the oracle works?  How do you call the oracle -- what is its input? What does it output? Do you give an example $x$ and the oracle gives $f(x)$? Do you give an example $x$ and the oracle returns some function of $f(x)$ and $p$ or $q$?  Do you call the oracle with no input? etc.
Lev Reyzin
CC BY-SA 3.0
2013-04-11T01:30:52.693Z
I think I know where the confusion lies. First some clarification: In the "wrinkly" variant of the problem, the oracle is exactly "`fitness`". In "non-wrinkly" variant, the oracle is "`fitness`" sans the line `random_number_generator.set_seed(x)`. In both variants of the problem, the input to the oracle can be any string of bits of length n. In both variants, the output is a rational.
Keki Burjorjee
CC BY-SA 3.0
2013-04-11T01:39:21.180Z
Here's where I think the confusion lies: In both variants of the problem the concept and hypthothesis space are not sets of functions but the set of all combinations of $k$ integers between 1 and n. These are the $k$ effective attributes. The task is to learn them. The oracle for when $k=4$ is given by "`fitness`"
Keki Burjorjee
CC BY-SA 3.0
2013-04-09T15:22:52.087Z
2013-04-11T04:03:13.370Z
2013-04-11T04:03:13.370Z
Lev Reyzin
<p>Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are "reasonably" different from each other (if you like, their variational distance is at least $\epsilon$, or something similar). </p>

<p>Now each function $f$ in this class is defined by a collection of $k$ indices $S$, and is evaluated as follows: If the parity of the selected bits is 0, return a random sample from $p$, else return a random sample from $q$.</p>

<p><strong>Problem</strong>: Suppose I'm given oracle access to some $f$ from this class, and while I know $\epsilon$ (or some other measure of distance), I don't know $p$ and $q$. </p>

<blockquote>
  <p>Are there any bounds on the number of calls I need to make to
  PAC-learn $f$ ? Presumably my answer will be in terms of $n, k$ and $\epsilon$. </p>
</blockquote>

<p><strong>Note</strong>: I didn't specify the output domain. Again, I'm flexible, but for now let's say that $p$ and $q$ are defined over a finite domain $[1..M]$. In general, I'd also be interested in the case when they are defined over ${\mathbb R}$ (for example, if they're Gaussians)</p>

CC BY-SA 3.0
2013-04-08T18:21:51.173Z
I'm not sure I understand the model. What do you specify in an oracle call?  Are the examples always drawn from the distribution specified by the target?
Lev Reyzin
CC BY-SA 3.0
2013-04-08T20:44:28.447Z
In an oracle call, you invoke f() and it returns a value.
Suresh Venkat
CC BY-SA 3.0
2013-04-08T21:25:25.670Z
So depending on the target function $f \in F$, either $p$ or $q$ is always used to generate examples?  (I assume you are pac learning some class $F$.)
Lev Reyzin
CC BY-SA 3.0
2013-04-09T02:53:29.773Z
Yes that is correct. the problem is to learn which one (or learn the parity bit being used)
Suresh Venkat
CC BY-SA 3.0
2013-04-09T02:59:42.143Z
Then who cares which distribution is the "target"?  I think the standard PAC bound from Occam's Razor Theorem simply applies. Just find a consistent hypothesis from $F$ after drawing $O(\lg(|F|)/\epsilon)$ examples (where $\epsilon$ is the target error rate, not distance). What am I missing?
Lev Reyzin
CC BY-SA 3.0
2013-04-09T03:17:04.217Z
You may not be missing anything - I'm a n00b at PAC-learning. But it's possible I didn't model the original problem correctly (it came from a post on genetic algorithms)
Suresh Venkat
CC BY-SA 3.0
2013-04-10T19:14:33.437Z
What is the right COLT model for this problem? What are the bounds on a solution with and without the wrinkle? The fate of a field depends on the answers to these questions. No pressure :)
Keki Burjorjee
CC BY-SA 3.0
2013-04-11T07:04:17.457Z
I am not sure how you adapt the PAC model to this model. But it seems that it's enough to be able to distinguish $p$ from $q$ with probability $1 - 1/(2k)$ and then you can get the $f(x)$ values for $k$ linearly independent $x$ and use gaussian elimination to find $f$ (since $f$ is linear). distinguishing two well-separated gaussians will be easy for example.
Sasho Nikolov
<lg.learning>
A parity learning question
Suresh Venkat
# A parity learning question

(Asked by: username_0 on 2013-04-08)

Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are "reasonably" different from each other (if you like, their variational distance is at least $\epsilon$, or something similar).

Now each function $f$ in this class is defined by a collection of $k$ indices $S$, and is evaluated as follows: If the parity of the selected bits is 0, return a random sample from $p$, else return a random sample from $q$.

**Problem**: Suppose I'm given oracle access to some $f$ from this class, and while I know $\epsilon$ (or some other measure of distance), I don't know $p$ and $q$.

> Are there any bounds on the number of calls I need to make to
> PAC-learn $f$ ? Presumably my answer will be in terms of $n, k$ and $\epsilon$.

**Note**: I didn't specify the output domain. Again, I'm flexible, but for now let's say that $p$ and $q$ are defined over a finite domain $[1..M]$. In general, I'd also be interested in the case when they are defined over ${\mathbb R}$ (for example, if they're Gaussians)

**Tags:** lg.learning

> **Comments:**
> **username_1**: I'm not sure I understand the model. What do you specify in an oracle call?  Are the examples always drawn from the distribution specified by the target?  
> **username_0**: In an oracle call, you invoke f() and it returns a value.  
> **username_1**: So depending on the target function $f \in F$, either $p$ or $q$ is always used to generate examples?  (I assume you are pac learning some class $F$.)  
> **username_0**: Yes that is correct. the problem is to learn which one (or learn the parity bit being used)  
> **username_1**: Then who cares which distribution is the "target"?  I think the standard PAC bound from Occam's Razor Theorem simply applies. Just find a consistent hypothesis from $F$ after drawing $O(\lg(|F|)/\epsilon)$ examples (where $\epsilon$ is the target error rate, not distance). What am I missing?  
> **username_0**: You may not be missing anything - I'm a n00b at PAC-learning. But it's possible I didn't model the original problem correctly (it came from a post on genetic algorithms)  
> **username_2**: What is the right COLT model for this problem? What are the bounds on a solution with and without the wrinkle? The fate of a field depends on the answers to these questions. No pressure :)  
> **username_3**: I am not sure how you adapt the PAC model to this model. But it seems that it's enough to be able to distinguish $p$ from $q$ with probability $1 - 1/(2k)$ and then you can get the $f(x)$ values for $k$ linearly independent $x$ and use gaussian elimination to find $f$ (since $f$ is linear). distinguishing two well-separated gaussians will be easy for example.  

---

## 1 answers

### Answer by username_1 on 2013-04-09. Score: 6

**The discussion in the comments below indicades that I have misunderstood the question. My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.**

---

Because the target distribution is fixed for every target $f^\* \in F$, the PAC-sample upper bound applies (this follows from the fact that the target distribution for this bound can even completely depend on $f^\*$). Hence,
$$
m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)
$$
examples should suffice to find a hypothesis of error $\le \epsilon$ w.p. $\ge 1-\delta$. Note -- after seeing these examples, one needs to find a consistent hypothesis from $F$, and this may not be tractable.

On the other hand, one can get a nearly matching lower bound even for the case of $p=q=U$, the uniform distribution, where $m \ge \Omega(\mathrm{VC}(F))$ examples are still required (this can be improved slightly).

The variational distance between $p$ and $q$, as well as $k$ may play a role in the small gap between these bounds, but I doubt it.

> **Comments:**
> **username_2**: The typical PAC-learning setting has an oracle $(f,D)$ that draws a sample $x$ from distribution $D$, and returns $(x, f(x))$. This is not the setting described in Suresh's question or the blog post that inspired it: http://bit.ly/YtwdST. In both of these, the oracle *is* the function $f$, and the learner is free to submit any element from the instance set (bitstrings of length $n$). Lev, does your answer assume an oracle of the first type, or the second type? If the second type, are we still talking about PAC-learning?  
> **username_1**: I see. In PAC, the "oracle" usually is thought of as a button which returns $(x, f(x))$ where $x \sim D$.  The Oracle you describe is called a "membership query" to $f$.  My answer only applies to the former.  If you only membership queries, how do you find out any information about $p$ or $q$ using Suresh's framework?  Let's say $p=q$ for simplicity.  
> **username_2**: Thanks for that clarification. So in the case Suresh described, the  "membership query" oracle works as follows (I presume you've put this entity in quotes because the oracle can return a real value, not just a boolean is-a-member/not-a-member answer): if the parity of the effective attributes is 1, then the result returned is drawn from distribution $p$. Otherwise, the result is drawn from distribution $q$. There's an additional wrinkle. The oracle remembers all its previous answers, and returns them if queried with the same input. In other words, it is deterministic.  
> **username_1**: I don't understand.  If the oracle is simply a function $f$ and you query it by giving it $x$, doesn't it just return $f(x)$? How does $p$ or $q$ come in to play if the learner is generating $x$ himself?  I think I've been failing to understand this basic point all along...  
> **username_2**: For $p=\mathcal N(+0.25, 1)$ and $q = \mathcal N(-0.25, 1)$, the pseudocode of the oracle for the problem with the "wrinkle" is given at the bottom of this reddit comment: http://bit.ly/XvVMC4 (`def fitness() ...`). I can't inline the code because SE doesn't allow newlines in comments. To obtain the "non-wrinkly" version of the problem, just remove the line `random_number_generator.set_seed(x)`.  
> **username_1**: I don't understand your reddit comment either -- is the oracle the "fitness" function?  Can you simply explain how the oracle works?  How do you call the oracle -- what is its input? What does it output? Do you give an example $x$ and the oracle gives $f(x)$? Do you give an example $x$ and the oracle returns some function of $f(x)$ and $p$ or $q$?  Do you call the oracle with no input? etc.  
> **username_2**: I think I know where the confusion lies. First some clarification: In the "wrinkly" variant of the problem, the oracle is exactly "`fitness`". In "non-wrinkly" variant, the oracle is "`fitness`" sans the line `random_number_generator.set_seed(x)`. In both variants of the problem, the input to the oracle can be any string of bits of length n. In both variants, the output is a rational.  
> **username_2**: Here's where I think the confusion lies: In both variants of the problem the concept and hypthothesis space are not sets of functions but the set of all combinations of $k$ integers between 1 and n. These are the $k$ effective attributes. The task is to learn them. The oracle for when $k=4$ is given by "`fitness`"  

---

