agnostic PAC model: Learnability and Bias-Complexity Trade-off - Cross Validated most recent 30 from stats.stackexchange.com 2019-08-23T05:40:58Z https://stats.stackexchange.com/feeds/question/393147 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://stats.stackexchange.com/q/393147 2 agnostic PAC model: Learnability and Bias-Complexity Trade-off induction601 https://stats.stackexchange.com/users/205113 2019-02-18T21:53:41Z 2019-02-20T17:26:20Z <p>I am reading <a href="https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf" rel="nofollow noreferrer">"Understanding Machine Learning: From Theory to Algorithms."</a> In Chapter 5.2, it says that choosing the hypothesis class <span class="math-container">$\mathcal{H}$</span> to be a very rich class decreases the approximation error but at the same time</p> <blockquote> <p><strong>might</strong> increase the estimation error, as a rich <span class="math-container">$\mathcal{H}$</span> <strong>might</strong> lead to overfitting.</p> </blockquote> <p>Based on this, it does not explain why overfitting is bad as we are talking about an upper bound. In this regard, I am even not sure in what sense Learning theory is necessary. As far as I know, the learning theory is concerned with the problem of generalization. To describe the problem in more detail, let me give some setup.</p> <p>Let <span class="math-container">$\mathcal{D} \sim \mathcal{X}\times \mathcal{Y}$</span> be a data distribution and <span class="math-container">$\mathcal{T}_m = \{(x_i, y_i)\}_{i=1}^m$</span> be a set of <span class="math-container">$m$</span>- iid data from <span class="math-container">$\mathcal{D}$</span>. Let <span class="math-container">$\mathcal{H}$</span> be a hypothesis class. For each <span class="math-container">$h \in \mathcal{H}$</span>, let us define <span class="math-container">$$L_{\mathcal{T}_m}(h) = \frac{1}{m}\sum_{i=1}^m (h(x_i) -y_i)^2, \qquad L_{\mathcal{D}}(h) = \mathbb{E}_{(x,y) \sim \mathcal{D}}[(h(x)-y)^2].$$</span> By Glivenko–Cantelli theorem or Kolmogorov's theorem, we know that the empicical measure converges to the underlying distribution. Therefore, <span class="math-container">$$\lim_{m \to \infty} L_{\mathcal{T}_m}(h) = L_\mathcal{D}(h).$$</span> I couldn't find an analog of this result on a high-dimension. However, assuming <span class="math-container">$|L_{\mathcal{D}}(h) - L_{\mathcal{T}_m}(h)| \le \mathcal{O}(m^{-1/d})$</span> where <span class="math-container">$d$</span> is the input dimension, I believe that the generalization is now well explained. It shows that how the empirical error is close to the true error and the difference goes to 0 as the number of samples goes to <span class="math-container">$\infty$</span>.</p> <p>Then I think that the learnability is all about measuing difference between the empirical measure and the underlying measure. If then, why do we even care about statements like, with probability exceeding <span class="math-container">$1-\delta$</span> on the iid <span class="math-container">$m$</span>-samples, <span class="math-container">$$L_{\mathcal{D}}(h) \le L_{\mathcal{T}_m}(h) + \mathcal{O}\left(\frac{\log |\mathcal{H}|/\delta}{m}\right).$$</span> By the way, this is a PAC learnablitiy statement for a finite hypothesis class. Even this simple case, it does not explain that why overfitting is bad in generalization. </p> <p>Any comments/suggestions/answers will be very appreciated.</p> https://stats.stackexchange.com/questions/393147/-/393191#393191 2 Answer by Ankitp for agnostic PAC model: Learnability and Bias-Complexity Trade-off Ankitp https://stats.stackexchange.com/users/76915 2019-02-19T04:35:29Z 2019-02-20T17:26:20Z <p>You are correct in the connection between Learning theory and Glivenko-Cantelli theorem. Note that original Glivenko-Cantelli theorem was only for half-bounded intervals. Indeed, if we take <span class="math-container">$\mathcal{H}$</span> to be the set of half-bounded intervals, then Glivenko-Cantelli theorem is equivalent to <span class="math-container">$$\lim_{m\to \infty} \sup_{h \in \mathcal{H}} | L_{\tau_m}(h) - L_{\mathcal{D}}(h) | \to 0$$</span> This notion of uniform convergence over half-intervals was then generalized to <span class="math-container">$\mathcal{H}$</span> having finite VC-dimension. For example, one can obtain a similar convergence in multiple dimensions by choosing the hypothesis class <span class="math-container">$\mathcal{H}$</span> as all half-cuboids which has finite VC Dimension. </p> <p>One may wonder what if you include a lot of functions in <span class="math-container">$\mathcal{H}$</span>. If <span class="math-container">$\mathcal{H}$</span> is allowed to be large, then one can come up with an example where the uniform convergence doesn't hold. Following results give lower bounds on the estimation error, necessating the need of choosing <span class="math-container">$\mathcal{H}$</span> wisely.</p> <p>(1) No Free Lunch theorem in the book, Theorem 5.1.</p> <p>(2) Fundamental theorem of Learning, Theorem 6.8.</p> <p>To quote the authors from Chapter 5 - "Learning theory studies how rich we can make <span class="math-container">$\mathcal{H}$</span> while still maintaining reasonable estimation error." </p> <p>The book referenced is "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz.</p>