3 votes

VC dimension of the class of all polygons with k vertices

Assuming that the $k$-gon is simple (i.e., does not intersect itself and has no holes) and $k>3$, the two-ears theorem, https://en.wikipedia.org/wiki/Two_ears_theorem implies that it can be ...
  • 10.1k
2 votes

PAC learning over continuous functions

In PAC learning, you specify the function class a priori. Thus, there might not be a function in your class that fits the sample perfectly. You'll typically minimize some empirical risk, such as $L_1$ ...
  • 10.1k
1 vote

Differing definitions of a weak learner

Suppose that the output of $h,c$ is either $+1$ or $-1$. Then $h(x)c(x)=1$ iff $h(x)=c(x)$. Moreover, if we let $p=\Pr[h(x)=c(x)]$, then $$\begin{align*} \mathbb{E}[h(x)c(x)] &= 1 \cdot \Pr[h(x)=...
  • 10.8k
1 vote

Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions

I will address the "VC" part. Let $F_{d,k}$ be the collection of all $k$-piecewise linear functions from $\mathbb{R}^d$ to $\mathbb{R}$. Let $H_{d,k}=\mathrm{sign}(F_{d,k})$ be this class ...
  • 10.1k

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