PAC learning theory and lower bound on the amount of input samples - Cross Validated most recent 30 from stats.stackexchange.com 2019-07-17T08:59:12Z https://stats.stackexchange.com/feeds/question/69554 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://stats.stackexchange.com/q/69554 7 PAC learning theory and lower bound on the amount of input samples ciri https://stats.stackexchange.com/users/12752 2013-09-09T12:19:55Z 2017-04-08T15:29:25Z <p>I am trying to answer the following question: "How much (binary) data do I need for my learner to have seen every variable of the dataset at least once?" In my set-up I am feeding my algorithm binary vectors (i.e. with all elements equal to either 1 or 0), these vectors have a known 'density' (average amount of ones) which - for the purpose of answering this question - are uniformly constant (ok) or follow a long tailed distribution (better). I have tried looking at it from the perspective of combinatorics but this was harder than expected. I suppose this question must have been asked before, but I have not been able to find any references so far.</p> <p>In <a href="http://www.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/ValiantLearnable.pdf" rel="nofollow">"A theory of the Learnable"</a> by Valiant, I read that:</p> <blockquote> <p>Let L(h,S) be the smallest integer such that in $L(h,S)$ independent Bernoulli trials each with probability at least $h^{-1}$ of success, the probability of having fewer than $S$ successes is less than $h^{-1}$. [...] PROPOSITION: For all integers $S &gt; 1$ and all real $h &gt; 1$. $$L(h,S) \leq 2 h (S + \ln (h))$$</p> </blockquote> <p>This can be translated to an upper bound for my question given that each feature is assumed to be drawn from an independent Bernoulli trial, but not a lower bound. Does anyone know of other related work that could point me towards a lower bound?</p> https://stats.stackexchange.com/questions/69554/-/70912#70912 2 Answer by ciri for PAC learning theory and lower bound on the amount of input samples ciri https://stats.stackexchange.com/users/12752 2013-09-24T13:23:11Z 2013-09-24T13:48:46Z <p>To answer my own question, it is easy to get a lower bound when you assume that all variables are uniformly distributed. Then the probability of this event (let's call it A) becomes:</p> <p>$$P(A) = 1 - P (X_1 = 0, X_2 = 0, \ldots, X_n = 0) \\ = 1 - \prod P(X_i = 0) \quad \quad \quad \quad \quad\\ = 1 - \left[ \binom{n}{k}\,\theta^{k} (1-\theta)^{n-k} \right]^m \quad\\ = \cdots \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$$</p> <p>The solution for non-uniform distributions can be found by <a href="http://en.wikipedia.org/wiki/Compound_probability_distribution" rel="nofollow">compounding</a> the Bernoulli distribution with an a priori Beta distribution.</p>