# Questions tagged [pac-learning]

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

45 questions
Filter by
Sorted by
Tagged with
10 views

55 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 ...
66 views

### Show that if $H$ is PAC learnable (in the standard one-oracle model), then $H$ is also learnable in the two-oracle model

Consider a variant of the PAC model in which there are two example oracles: one that generates positive examples and one that generates negative examples, both according to the underlying distribution ...
46 views

### Applying Hoeffding's inequality in uniform convergence proof in “Understanding Machine Learning: From Theory to Algorithms”

I am trying to understand the proof of the uniform convergence property for classes with finite VC dimension, as given in the textbook "Understanding Machine Learning: From Theory to Algorithms" (an ...
92 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 ...
12 views

### Output vectors of the training cases

I'm reading the following paper Keeping Neural Networks Simple by Minimizing the Description Length of the Weights (Hinton and van Camp 1993) where the first sentence in the abstract says ...
24 views

### PAC learnability

I don't understand the solution. Everything required to compute $m$ is already given. Then why can't we apply PAC learning theory? The training error is not zero in this case so is that the reason why ...
16 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 ...
42 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 ...
53 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-...
38 views

### What is a “concept” in computational 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 ...
89 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 ...
1k 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] ...
213 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)...
327 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 ...
668 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 ...
183 views

336 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 ...
196 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. ...
174 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 ...
37k 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 ...
3k 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 ...
385 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 ...
11k 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 ...
805 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. ...
333 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 ...