Questions tagged [pac-learning]
PAC is Probably Approximately Correct learning
62
questions
0
votes
0
answers
8
views
extending PAC bound result to validation set generalization error
I PAC-bound I learned consider the following decompistion:
$R(f) = R_n(f) + \left(R(f) - R_n(f)\right)$
where $R(f)$ is the test error, $R_n(f)$ is the training error $\left(R(f) - R_n(f)\right)$ is ...
- 363
0
votes
0
answers
13
views
Generalization bound on out of distribution data
Assume we have two sets of data $X_1$ and $X_2$ drawn from two different distributions. Are the loss of the empirical risk minimizer of $X_1$ on $X_2$: $l_{X_2}(f_{X_1})$ the same as the loss of the ...
- 363
1
vote
0
answers
9
views
Extending efficient PAC learning with classification noise to statistical query model with unlabeled random draws for axis-aligned rectangles in $R^2$
I have proven that if $C$, a concept class, is efficiently learnable from statistical queries using $H$, a representation class over $X$, then $C$ is efficiently PAC learning using $H$ in the presence ...
- 111
0
votes
0
answers
14
views
Does PAC bound or MLE imply the distribution of empirical risk minimizer?
We know that PAC bounds tell us the empirical risk on training data cannot be too different from the true risk. My question is, does this result imply empirical risk minimizer also cannot be too far ...
- 363
0
votes
0
answers
29
views
Could we code a program to compute VC-dimension of any given hypothesis class?
I've been studying machine learning theory and the fundamental theorem of the statistical learning for a while, but I still didn't found a general algorithm that could compute the VC dimension of any ...
- 1
0
votes
0
answers
99
views
What does it mean to say in PAC learning that if the running time of the algorithm is polynomial in 1/e and 1/d, the sample size must be also poly
In the context of PAC learning, why it is true to say that if an algorithm A is a PAC-learning algorithm, then the sample size required by it must also be polynomial, i.e., how to properly interpret ...
0
votes
0
answers
21
views
What is the mathematical term for a real world categorical function that yields several categories for the same inputs?
Background and Color
Contextually, this is pertaining to machine learning and natural language processing. Specifically, it has to do with the labeling of real world data for partitioning by a machine ...
- 326
0
votes
0
answers
70
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\ }\...
- 101
2
votes
0
answers
80
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 ...
- 21
1
vote
0
answers
106
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 ...
- 111
2
votes
2
answers
191
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 ...
- 21
0
votes
1
answer
33
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 ...
- 409
1
vote
0
answers
80
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} = \...
- 11
1
vote
0
answers
100
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 ...
- 244
2
votes
1
answer
982
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 ...
- 244
1
vote
0
answers
855
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 ...
- 113
1
vote
1
answer
496
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 ...
- 35
2
votes
1
answer
208
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 ...
- 35
2
votes
1
answer
336
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}$...
- 123
2
votes
1
answer
147
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)$-...
- 409
0
votes
1
answer
191
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 ...
- 231
4
votes
1
answer
591
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).
...
- 1,042
2
votes
0
answers
163
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 ...
0
votes
1
answer
359
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. ...
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 ...
- 129
2
votes
1
answer
663
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) \...
- 3,145
2
votes
1
answer
231
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 ...
- 163
3
votes
1
answer
966
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 ...
- 163
2
votes
1
answer
183
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 ...
- 163
0
votes
1
answer
420
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 ...
- 173
0
votes
0
answers
28
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 ...
- 21
2
votes
2
answers
227
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 ...
- 155
3
votes
2
answers
382
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 ...
- 331
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] ...
- 145
2
votes
1
answer
962
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)...
- 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 ...
- 239
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 ...
- 11
3
votes
0
answers
393
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\}^...
- 211
1
vote
0
answers
538
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 ...
- 11
9
votes
1
answer
971
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 ...
- 826
6
votes
1
answer
534
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 ...
- 331
1
vote
0
answers
152
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 ...
- 53
3
votes
3
answers
238
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 ...
- 131
14
votes
1
answer
3k
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 ...
- 1,412
0
votes
1
answer
164
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 ...
- 2,691
3
votes
1
answer
439
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)$
- 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 ...
- 4,007
1
vote
0
answers
696
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?
- 11
29
votes
4
answers
12k
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 ...
23
votes
2
answers
33k
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 ...
- 543