Skip to main content
Share Your Experience: Take the 2024 Developer Survey
5 votes

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 ...
Matifou's user avatar
  • 149
4 votes
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 ...
ehudk's user avatar
  • 241
4 votes

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 ...
Green Falcon's user avatar
  • 14.1k
3 votes
Accepted

Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?

Lets use the quotes from the book. To give an upper bound, we need to prove that no set $S$ of cardinality $d + 1$ can be shattered by $H$ By doing this, we are proving that $\text{VCdim}(H) <...
Esmailian's user avatar
  • 9,322
3 votes
Accepted

A trick used in Rademacher complexity related Theorem

This requires hell of a derivation, but I liked the question :) My question is, why can we swap $z_i$ and $z'_i$? The key insight is that notation $S \sim \mathcal{D}^m$ is equivalent to $Z_1 \...
Esmailian's user avatar
  • 9,322
2 votes

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 ...
Tophat's user avatar
  • 2,430
2 votes
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 ...
DaL's user avatar
  • 2,643
2 votes

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 ...
Ben Reiniger's user avatar
  • 11.9k
2 votes
Accepted

Finding the tightest (smallest) triangle that fits all points

There appear to be a few issues with this approach. In the second step you have $(y_1,y_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})≤r_{max}$ twice. Presumably one of these should be $(y_1,y_2)⋅(-\frac{\sqrt{...
Lynn's user avatar
  • 1,307
2 votes

Why does PAC learning focus on learnability of the hypothesis class and not the target function?

Fair warning, this is just an intuition and I'm not really expert in this kind of question. Nice question anyway :) Theoretical models of learning like PAC are meant to be used to prove learnability ...
Erwan's user avatar
  • 25.5k
1 vote

Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

I agree, the claim as written is incorrect. If $C^*$ is shattered by $\mathcal{H}$, and $C\subseteq C^*$, then $C$ is also shattered by $\mathcal{H}$; to be possibly over-pedantic: For each $B\...
Ben Reiniger's user avatar
  • 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 ...
Esmailian's user avatar
  • 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)$ ...
Esmailian's user avatar
  • 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. ...
DuttaA's user avatar
  • 793

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