All Questions
Tagged with learning-theory co.combinatorics
11
questions
0
votes
0
answers
63
views
VC dimension of full-dimensional closed polyhedral cone in $\mathbb R^d$
Consider a fixed set of vectors $\{x_i\}_{i\in[n]}$ in $\mathbb R^d$ and closed polyhedral cone $C = \{w \in \mathbb R^d : w^\top x_i \geq 0, \forall i \in [n]\}$ with full dimension i.e. $C$ contains ...
- 1
7
votes
2
answers
448
views
Upper bound on VC-dimension of partitioned class
Fix $n,k\in \mathbb{N}_+$.
Let $\mathcal{H}$ be a set of functions from $\mathbb{R}^n$ to $\mathbb{R}$ with finite VC-dimension $d\in \mathbb{N}$. Let $\mathcal{H}_k$ denote the set of maps of the ...
- 362
1
vote
1
answer
189
views
Rademacher complexity for a family of bounded, nondecreasing functions?
Let $\{\phi_k\}_{k=1}^K$ be a family of functions mapping from an interval $[a, b]$ to $[-1, 1]$.
That is, $\phi_k \colon[ a,b] \to [-1, 1]$ are nondecreasing maps on some finite interval $[a, b] \...
- 460
1
vote
1
answer
546
views
Upper bounding VC dimension of an indicator function class
I would like to upper bound the VC dimension of the function class $ F$ defined as follows:
$$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q ...
- 11
5
votes
1
answer
978
views
VC dimension of axis-parallel boxes on the torus
First the basic definitions: Let $H$ be a family of sets, and let $P$ be a set of points. Then $H$ is said to shatter $P$ if $\{ h \cap P:~h \in H\}=2^P$, that is, if every subset of $P$ can be ...
- 2,199
1
vote
1
answer
255
views
VC dimension of cone-restricted linear classifiers
Let $\mathcal{C}$ be a pointed, salient cone in $\mathbb{R}^d$. We may also assume that $\mathcal{C}$ is full-dimensional. Consider the set of binary classifiers $$\mathcal{H} = \{\boldsymbol{x}\...
- 215
1
vote
1
answer
357
views
What is the shatter coefficient / VC - dimension of some hypothesis set?
Let $H:=\{h:\mathbb{N}_0^n \rightarrow \{0,1\}| h(x_1,\cdots,x_n) = \mathbb{1}_0(\sum_{i\in I}{x_i}-\sum_{j \notin I}{x_j}) \text{ for some } I \subset \{1,\cdots,n\}\}$
where $\mathbb{1}$ is the ...
user6671
7
votes
1
answer
290
views
"Separated" version of Sauer's lemma on VC classes
Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
- 2,199
1
vote
0
answers
124
views
Vertex cover for hamming graphs representing sets of bounded VC dimension
Let $S$ be a set of binary vectors (in $\lbrace 0,1 \rbrace^m $) whose VC dimension is $d$. Let $H$ be the Hamming graph generated from this set where each node represents a binary vector and two ...
- 11
0
votes
0
answers
548
views
VC dimension and boolean hypercube subgraphs
Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.
- 11
3
votes
2
answers
2k
views
Vapnik-Chervonenkis dimension of lines in the plane
I'm having some problems with this problem concerning VC dimensions (http://en.wikipedia.org/wiki/VC_dimension), I hope for some helping input.
Given a set $L$ of $n$ lines in the plane, define a ...
- 393