Statistical Analysis Stack Exchange
Statistical Analysis Stack Exchange

Questions tagged [pac-learning]

PAC is Probably Approximately Correct learning

https://en.wikipedia.org/wiki/Probably_approximately_correct_learning

56 questions
478
votes
20 answers

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 to this: Simon Blomberg: From R's fortunes …
Shane
  • 11,961
  • 17
  • 71
  • 89
43
votes
3 answers

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 same or is there some difference? In the adaboost…
vrushali
  • 431
  • 1
  • 4
  • 3
27
votes
4 answers

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 learning. Particularly, lots of literature that can be…
Quickbeam2k1
  • 223
  • 1
  • 4
  • 11
22
votes
2 answers

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 could detail this theory for me. This theory is…
BetterEnglish
  • 523
  • 1
  • 6
  • 16
21
votes
1 answer

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 Least Squares fitting and easy to solve with…
petrichor
  • 1,615
  • 2
  • 15
  • 17
20
votes
6 answers

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 'fundamental' idea in machine learning for estimating…
user28
16
votes
2 answers

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. Sontag [1998] "VC dimension of neural networks"…
Artem Kaznatcheev
  • 2,569
  • 1
  • 20
  • 38
10
votes
1 answer

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 learn these subjects or should I concentrate…
Daniel Yefimov
  • 1,222
  • 1
  • 11
  • 27
9
votes
1 answer

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 and remarkable to me, I'm not so sure about its…
syeh_106
  • 746
  • 4
  • 15
7
votes
1 answer

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 vectors (i.e. with all elements equal to either 1…
ciri
  • 1,123
  • 9
  • 21
7
votes
1 answer

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 assumptions are made that your function class contains…
luispedro
  • 740
  • 4
  • 17
6
votes
1 answer

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 this paper, it says, Learning approach such as…
Cherry Wu
  • 289
  • 2
  • 11
5
votes
3 answers

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 introduction to what it exactly is.
Cupitor
  • 1,415
  • 1
  • 11
  • 22
5
votes
0 answers

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 unbounded losses (with finite moments or…
gappy
  • 5,390
  • 3
  • 28
  • 50
4
votes
1 answer

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 performance with the present set of features is not…
prashanth
  • 3,747
  • 4
  • 21
  • 33
1
2 3 4