Share Your Experience: Take the 2024 Developer Survey

# Tag Info

## Hot answers tagged pac-learning

### Are decision tree algorithms linear or nonlinear

As many pointed out, a regression/decision tree is a non-linear model. Note however that it is a piecewise linear model: in each neighborhood (defined in a non-linear way), it is linear. In fact, the ...
• 149
Accepted

### Generalization Error Definition

There exists somewhere in the world a distribution $D$ from which you can draw some samples $x$. The notation $x \sim D$ simply states that the sample $x$ came from the specific distribution that was ...
• 241

### Are decision tree algorithms linear or nonlinear

A decision tree is a non-linear classifier. If your dataset contains consistent samples, namely you don't have the same input features and contradictory labels, decision trees can classify the data ...
• 14.1k
Accepted

• 9,322

### Meaning of Instance Space and Concept Class, (PAC Learnable)

This kind of language is typically associated within a field of math called computational learning theory (clt). CLT is inherently abstract since it's trying to derive general observation about ...
• 2,430
Accepted

### What is PAC learning?

PAC stands for Probably Approximately Correct. It was a very common research area in computer science looking for proof of learnability of certain hypothesis sets. The usual hypothesis sets were not ...
• 2,643

### VC-dimension proof for a family of classifiers

The VC dimension of this family is not infinite. Most of your text is fluff, restating definitions and what must be shown. Some of that can be useful, but IMO there's rather too much of it for a ...
• 11.9k
Accepted

• 11.9k
1 vote
Accepted

### Generalization bound (single hypothesis) in "Foundations of Machine Learning"

You are right. The relaxed inequality $$R(h) \le \hat{R}_S(h)+ \epsilon.$$ can be replaced with the complete inequality $$\left |\hat{R}_S(h) - R(h) \right| \le \epsilon.$$ Actually, authors use ...
• 9,322
1 vote

### A question on realizable sample complexity

We want to prove: If H is PAC learnable, then $\forall \epsilon, \exists C, \forall m \geq m_2:=Clog(1/\epsilon)(m_1+1/\epsilon^2), E[L] \leq \epsilon \mbox{ (a)}$ where $m_1:=m(\epsilon/2,1/2)$ ...
• 9,322
1 vote

### PAC Learnability - Notation

The explanations are as follows: $m_H:(0,1)^2 \rightarrow \mathbb N$ is a similar notation to $f:R^n\rightarrow \mathbb N$ which means it takes a n-dimensional input consisting of real numbers only. ...
• 793

Only top scored, non community-wiki answers of a minimum length are eligible