New answers tagged machine-learning
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 ...
2
votes
Accepted
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Let us suppose that $H$ shatters some $k$ points $(x_i,y_i)$, $i\in[k]$.
That means that for all $b\in\{0,1\}^k$, there is an $f=f_b\in F$ such that $y_if(x_i)\le\gamma$ if $b_i=1$ and
$y_if(x_i)>\...
1
vote
Accepted
VC-dimension of the infinite intersection of two spheres
Once the OP has clarified that the question is about the VC-dimension of the 2-fold intersection of spheres in $\mathbb{R}^d$ (in fact, $d=2$ was specified), a simple upper bound can be stated. The VC-...
Top 50 recent answers are included
Related Tags
machine-learning × 333lg.learning × 114
reference-request × 46
st.statistics × 33
pac-learning × 30
vc-dimension × 29
ds.algorithms × 27
cc.complexity-theory × 22
ne.neural-evol × 20
optimization × 19
ai.artificial-intel × 16
approximation-algorithms × 13
clustering × 13
graph-theory × 11
pr.probability × 10
boolean-functions × 8
sample-complexity × 8
cg.comp-geom × 7
query-complexity × 7
online-learning × 7
graph-algorithms × 6
it.information-theory × 6
convex-optimization × 6
network-modeling × 6
property-testing × 6