Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pac-learning]

PAC is Probably Approximately Correct learning, see https://en.wikipedia.org/wiki/Probably_approximately_correct_learning

0
votes
0answers
5 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 ...
2
votes
1answer
31 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 ...
0
votes
0answers
29 views

PAC-Bayes bound for multiclass classification

I am starting to learn PAC learning, and have an interest in PAC-Bayes bound. However, most of the materials I found assumed binary classification only, while I am looking for the extension of PAC-...
0
votes
0answers
88 views

What will be the VC dimension of a axis aligned cuboid? Can someone explain with an example?

I am new to machine learning and while going through Vc dimensions I came across that the Vc dimension of a rectangle is 4. Is the Vc dimension of a cuboid 6?
0
votes
0answers
16 views

Terminology, meaning of “Concepts” in Statistical Learning Theory

I'm studying the definition of PAC learnable: Let C be a concept class over X. We say that C is PAC learnable if there exists an algorithm A with the following property: for every ...
1
vote
1answer
40 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 ...
1
vote
1answer
536 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] ...
0
votes
1answer
138 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)...
0
votes
2answers
158 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 ...
1
vote
1answer
427 views

VC dimension of decision tree

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 ...
2
votes
0answers
140 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\}^...
1
vote
0answers
350 views

Prove PAC Learnable

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 ...
6
votes
0answers
219 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 ...
4
votes
1answer
170 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 ...
1
vote
0answers
83 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 ...
4
votes
3answers
147 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 ...
9
votes
1answer
1k 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 ...
0
votes
1answer
154 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 ...
3
votes
1answer
87 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)$
4
votes
1answer
1k 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 ...
1
vote
0answers
540 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?
22
votes
4answers
6k 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 ...
12
votes
2answers
7k 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 ...
1
vote
1answer
159 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 ...
2
votes
0answers
281 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 ...
2
votes
1answer
182 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. ...
1
vote
2answers
171 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 ...
31
votes
3answers
31k 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 ...
4
votes
2answers
2k views

A Reference for PAC-Bayesian?

I've recently came across topic known as PAC-Bayesian, but I cannot find a source to read about it. Any article that I came across are talking about its application in a specific area but there is no ...
7
votes
1answer
320 views

PAC learning theory and lower bound on the amount of input samples

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 ...
16
votes
1answer
10k views

Why do we assume that the error is normally distributed?

I wonder why do we use the Gaussian assumption when modelling the error. In Stanford's ML course, Prof. Ng describes it basically in two manners: It is mathematically convenient. (It's related to ...
16
votes
2answers
706 views

What are alternatives to VC-dimension for measuring the complexity of neural networks?

I have come across some basic ways to measure the complexity of neural networks: Naive and informal: count the number of neurons, hidden neurons, layers, or hidden layers VC-dimension (Eduardo D. ...
7
votes
1answer
325 views

Theoretical results for cross-validation estimation of classification accuracy?

For classification, what theoretical results are between cross-validation estimate of accuracy and generalisation accuracy? I particularly asking about results in a PAC-like framework where no ...
18
votes
6answers
14k views

What is the 'fundamental' idea of machine learning for estimating parameters?

The 'fundamental' idea of statistics for estimating parameters is maximum likelihood. I am wondering what is the corresponding idea in machine learning. Qn 1. Would it be fair to say that the '...
414
votes
20answers
144k views

The Two Cultures: statistics vs. machine learning?

Last year, I read a blog post from Brendan O'Connor entitled "Statistics vs. Machine Learning, fight!" that discussed some of the differences between the two fields. Andrew Gelman responded favorably ...