Questions tagged [pac-learning]

PAC is Probably Approximately Correct learning

Filter by
Sorted by
Tagged with
0 votes
0 answers
52 views

Learning Algorithm Time & Sample Complexity

Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$ and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
user avatar
0 votes
0 answers
67 views

vc-dimension of reunion

I started learning Advanced Machine Learning recently and got stuck on the next problem: Consider $\mathcal{H} = \mathcal{H}_1 \cup \mathcal{H}_2 \cup \mathcal{H}_3$, where: $\mathcal{H}_1 = \{h_{\...
user avatar
  • 1
2 votes
0 answers
70 views

Hypothesis class with n elements that shatters a set C of n/2 points

I started learning Advanced Machine Learning and came across a problem that stuck. I would be grateful if you could help me with some ideas or solutions: What is the maximum value of the natural even ...
user avatar
  • 21
1 vote
0 answers
54 views

What makes an algorithm a PAC learner?

I am new to Machine Learning theory and some of the topics are not very intuitive to me. I don't quite understand how the sample complexity in PAC theorem depends only on the concept class. As we see ...
user avatar
  • 111
2 votes
2 answers
67 views

Can weak-learner be defined in the case of regression problem?

weak-learner is often defined relating to PAC learning. However, to the extent I know, I have never seen the definition of weak-learner when regression. That is, the definition of weak-learner on ...
user avatar
  • 21
0 votes
1 answer
24 views

Characterizations of uniformly learnable function classes in the distribution-specific setting

Let $X$ be some input domain (a measurable space). Then let $D$ be some class of probability distributions on $X\times\{0,1\}$. We will call such distributions learning tasks. We say that $D$ is ...
user avatar
  • 389
0 votes
0 answers
10 views

Proper statement of PAC Learning Theorem

Let $X$ be an input space and $Y$ be an output space. Suppose there is some unknown underlying distribution $P_{pop}$ (pop here stands for population) that generates data $\lbrace (x_i,y_i) \rbrace_{i=...
user avatar
1 vote
0 answers
43 views

VC-Dimensions and PAC-learning of some specific certain class of classifiers

I'm learning VC-dimensions and PAC-learnability right now and I need some help. I'm answering a practice exercise question that I'm prepping for an exam. So suppose we have some domain $\mathcal{X} = \...
user avatar
  • 11
1 vote
0 answers
84 views

Has Fundamental Theorem of Statistical Learning been proven for infinite classes of functions?

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
user avatar
  • 244
2 votes
1 answer
512 views

What is an "ERM rule" in Understanding Machine Learning by Shai Shalev-Shwartz et al.?

I am reading "Understanding Machine Learning" book by Shalev-Shwartz, Ben David. On the page 48, the theorem 6.7 (The fundamental theorem of statistical learning, FTSL) says: Let $H$ be a ...
user avatar
  • 244
1 vote
0 answers
359 views

VC-Dimension of Axis-Aligned Right Triangles and 5-point Convex Hull

I am having trouble proving the following fact about the VC dimension of triangles. Consider axis-aligned right triangles in the plane, with the the right angle in the lower left corner. The ...
user avatar
  • 113
1 vote
1 answer
120 views

how is the expectation of the empirical error based on an i.i.d. sample S is equal to the generalization error?

I am on the 28 page of the book called "foundations of machine learning" by M.Mohri which states that for a fixed hypothesis h,the expected value of the empirical error is equal to ...
user avatar
2 votes
1 answer
153 views

what's the difference between hypothesis function outputed by algorithm A and polynomial function in the book,"foundations of machine learning"

I am on the 28 page of the book called "foundations of machine learning" by M.Mohri which contains this(in the iamge below) defination of the PAC learning framework.I am a bit coufused about ...
user avatar
1 vote
1 answer
158 views

Why sample complexity must be polynomial for PAC learning?

I'm reading up on Probably Approximately Correct (PAC) learning and most sources require that the sample complexity must be polynomial in $\frac{1}{\epsilon}$ and $\frac{1}{\delta}$, where ${\epsilon}$...
user avatar
  • 113
2 votes
1 answer
88 views

Does majority-vote boost weak learners to strong learners?

A learner is a function mapping finite vectors with elements in $X\times\{0, 1\}$ onto binary functions on $X$. Given a set $H$ of binary functions on $X$, we say that: A learner $(\delta, \epsilon)$-...
user avatar
  • 389
0 votes
1 answer
101 views

How are bias and variance related to overfitting and model capacity?

Many people use the MSE decomposition to illustrate bias and variance. However, is there any statistical learning theory connecting these concepts? Namely, is there a formula calculating model ...
user avatar
  • 201
3 votes
1 answer
186 views

Does a generalization bound that holds with high probability imply a bound that holds in expectation?

I am interested in generalization bounds, for example PAC bounds (Probably Approximately Correct). In particular, I wonder if a high probability bound implies a bound in expectation (or vice versa). ...
user avatar
  • 1,032
1 vote
0 answers
86 views

PAC Learnability of axis aligned squares

Ok, so I already know how the pac learnability of an axis aligned rectangle is demonstrated, that is we fix some distribution $D$ over $X$, define $R^* = R_{(a_1^*, b_1^*, a_2^*, b_2^*)}$ the ...
user avatar
0 votes
1 answer
124 views

PAC Learning for OLS and noisy regression

Hi guys I would like to get some references on PAC Learning for the following settings: PAC Learning type results for OLS. Most materials that tackle OLS are from a statistical point of view, i.e. ...
user avatar
2 votes
1 answer
1k views

What is Massart Noise?

One of best papers during NeurIPS 2019 - Distribution-Independent PAC Learning of Halfspaces with Massart Noise mentions Massart Noise in the title. What is this type of noise? How is it different ...
user avatar
  • 129
1 vote
1 answer
175 views

Need mathematical steps for Hoeffding's Inequality applied to Bernoulli Distribution

I am trying to understand Hoeffiding's Inequality in Machine Learning and I am referring to WikiPedia for it. Hoeffding's Inequality is defined as follows: $ P(|\hat{\theta} - \theta)| \ge \epsilon) \...
user avatar
  • 2,595
1 vote
1 answer
113 views

How should I understand the "combinatorial property" here?

I came across the following statement on page 78 of the book "Understanding Machine Learning: From Theory to Algorithms" The fundamental theorem of learning theory characterizes PAC learnability of ...
user avatar
  • 153
3 votes
1 answer
602 views

How do you understand the relation between the number of parameters and the VC dimension of a hypothesis class?

It is often the case that the VC-dimension of a hypothesis class equals (or can be bounded above by) the number of parameters one needs to set in order to define each hypothesis in the class. For ...
user avatar
  • 153
2 votes
1 answer
116 views

How can I understand the multiclass verison of "shattering" intuitively?

I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering. I know that ...
user avatar
  • 153
0 votes
1 answer
355 views

is PAC-learning used in machine learning practice?

Is the PAC-learning theory actually used in every day machine learning? Or is this something that you learn at university and don't really need unless you do research on algorithms and need to provide ...
user avatar
0 votes
0 answers
24 views

References for generalization bounds?

I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or ...
user avatar
  • 21
2 votes
2 answers
155 views

agnostic PAC model: Learnability and Bias-Complexity Trade-off

I am reading "Understanding Machine Learning: From Theory to Algorithms." In Chapter 5.2, it says that choosing the hypothesis class $\mathcal{H}$ to be a very rich class decreases the approximation ...
user avatar
2 votes
2 answers
230 views

About PAC-Bayesian bounds in learning theory

Consider PAC-Bayesian bounds used in learning theory (as defined in say section $1.2$, page $3$ of this paper, https://arxiv.org/pdf/1707.09564.pdf). I want to know what is the precise mathematical ...
user avatar
2 votes
2 answers
3k views

Proving $\mathcal{H}_{Singleton}$ is PAC-learnable

I'm referring to Section 3.5, ex. 2 in Understanding machine learning. To my understanding, given $\varepsilon, \delta$, I need to find minimum sample size $n$ s.t. $$P[e_P(ERM(S_n) > \varepsilon] ...
user avatar
  • 145
2 votes
1 answer
791 views

Example for a class that is not PAC learnable

I'm looking for a reference (with proof) on hypothesis classes that are not PAC learnable. Is there a simple one too? Are they of any use (if not in practice, maybe as counter examples for some claims)...
user avatar
  • 161
2 votes
2 answers
1k views

PAC learning definition and the properties of the problem

I am trying to understand the basic definition of realizable PAC learning from Shai Shalev-Shwartz's "understanding machine learning". They define a hypothesis class H to be PAC learnable if for every ...
user avatar
1 vote
1 answer
1k views

VC dimension of decision tree [duplicate]

I encountered a question that I really can't figure out: Suppose your hypothesis class(H) consists of decision trees with 7 nodes that splits on only one feature. How to calculate the VC dimension of ...
user avatar
3 votes
0 answers
327 views

What does it mean when a class is not PAC learnable?

I understood that when a hypothesis class is PAC learnable, we can learn about the sample size, accuracy, and confidence. Suppose we have following problem which is not PAC learnable: Input: $\{0,1\}^...
user avatar
  • 211
1 vote
0 answers
480 views

Prove PAC Learnable [closed]

How can I prove that a hypothesis space is PAC learnable? The setup for this is X which is a discrete instance space. H is a set of hypotheses over X. H contains all singleton functions as well as ...
user avatar
  • 11
9 votes
1 answer
800 views

What is the utility/significance of PAC learnability and VC dimension?

I've been reading Shalev-Shwartz & Ben-David's book, "Understanding Machine Learning", which presents the PAC theory in its Part I. While the theory of PAC learnability does appear very elegant ...
user avatar
  • 806
6 votes
1 answer
365 views

Why noisy data will benefit Bayesian?

Recently I am reading a paper in 2001, Michael D. Ernst, Jake Cockrell, William G. Griswold, David Notkin Dynamically Discovering Likely Program Invariants to Support Program Evolution TSE 2001, in ...
user avatar
  • 289
1 vote
0 answers
127 views

PAC learnability of real valued function w.r.t. zero loss function

The necessary and sufficient conditions for learning to occur in the task of binary classification are among the fundamental results in learning theory. In the sources I'm familiar with, this theorem ...
user avatar
3 votes
3 answers
214 views

What characterizes a function that is easy to learn?

When performing machine learning, the performance of the machine learning method is dependent on the original function $f$ that we are trying to learn (let's forget for a moment the non-deterministic ...
user avatar
10 votes
1 answer
2k views

Complex analysis, Functional analysis for deeper understanding Machine Learning

I want to get deeper into the Machine Learning(theory and application in Finance). I want to ask how relevant are complex analysis and functional analysis as a basis for Machine Learning? Do I need to ...
user avatar
0 votes
1 answer
163 views

Is machine learning only about estimating programs? [closed]

Q: Can we say that all of machine learning is, essentially, only about finding good estimations of programs? If not, is there any example of a machine learning problem that is not about finding ...
user avatar
  • 2,501
3 votes
1 answer
361 views

What is the PAC function of an AR(2)?

What is the PACF(1) of the following AR(2) process? $ y_t = \phi y_{t-2}+\epsilon_t $ with $\epsilon_t \sim WN(0, \sigma^2)$
user avatar
  • 71
4 votes
1 answer
2k views

Best approaches for feature engineering?

I have a regression problem. The aim is to estimate the best fitting curve from a set of features. Now I have extracted a set of features that are relevant based on the literatures found. Now the ...
user avatar
  • 3,787
1 vote
0 answers
667 views

An example for a finite hypothesis class which is not PAC learnable?

Finite hypothesis class with bounded loss function are PAC learnable. Are there examples for finite hypothesis classes in the case of unbounded loss function, which aren't PAC learnable?
user avatar
  • 11
27 votes
4 answers
10k views

Introduction to machine learning for mathematicians

In some sense this is a crosspost of mine from math.stackexchange, and I have the feeling that this site might provide a broad audience. I am looking for a mathematical introduction to machine ...
22 votes
2 answers
26k views

What does PAC learning theory mean?

I am new in machine learning. I am studying a course in machine learning (Stanford University ) and I did not understand what is meant by this theory and what is its utility. I am wondering if someone ...
user avatar
1 vote
0 answers
234 views

Sample complexity for agnostic PAC learning for real valued functions

How many samples are needed for ERM to have $\epsilon$ excess risk relative to the best hypthosis $h^*$? Assume a bounded (and Lipschitz, if needed) loss function. The only survey I have been able to ...
user avatar
  • 11
5 votes
0 answers
581 views

Rademacher bounds for unbounded loss functions

All common treatment of PAC bounds based on Rademacher complexity assume a bounded loss function (for a self-contained treatemnt, see this handout by Schapire. However, I could not find any result for ...
user avatar
  • 5,400
3 votes
1 answer
267 views

Is "not-overfitting" a utopian scenario?

We say a model overfits when classification error increases on the test data. The reason behind this is that the training data is not a representative of the distribution from which data is sampled. ...
user avatar
  • 383
1 vote
2 answers
185 views

Repeatedly measuring accuracy against the hold out set

I have an iterative document classification task, corpus size = 300,000 documents. The labels are binary valued (yes/no). I wanted to know whether the following methodology is valid. The assumption is ...
user avatar
  • 31
45 votes
3 answers
53k views

What is meant by 'weak learner'?

Can anyone tell me what is meant by the phrase 'weak learner'? Is it supposed to be a weak hypothesis? I am confused about the relationship between a weak learner and a weak classifier. Are both the ...
user avatar
  • 451