Timeline for Upper bounding VC dimension of an indicator function class
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 21:52 | comment | added | Gustave Emprin | The fact that the mediator does not contain a plane changes $P_d(N)$. For exemple, consider the mediators (in $R^2$) of (-3,-1) , (3,1) and between (-4,1) and (2,3). Together, they define 5 domains in $R^2$, while $P_2(2)$ is only $4$. | |
| Jun 15, 2020 at 21:06 | history | edited | Gustave Emprin | CC BY-SA 4.0 |
added 18 characters in body
|
| Jun 15, 2020 at 20:59 | comment | added | Gustave Emprin | The separation by an hyperplane. I am revising now and I was mistaken, the domains $||q-x_i||_1>||q-x_j||_1$ and converse are not separated by hyperplanes. The proof thus only holds for $p=2$. | |
| Jun 15, 2020 at 16:26 | comment | added | ato_42 | I see your updated proof. Which part of the argument requires $p \in \{ 1, 2, \infty\}$ ? | |
| Jun 15, 2020 at 15:03 | history | edited | Gustave Emprin | CC BY-SA 4.0 |
added 256 characters in body
|
| Jun 15, 2020 at 14:38 | history | edited | Gustave Emprin | CC BY-SA 4.0 |
added 1383 characters in body
|
| Jun 15, 2020 at 13:19 | comment | added | Gustave Emprin | My result should be on the VC dimension of the family of functions $$\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_2-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$\{(x,t)\mapsto1(\min_q||x-q_i||_2-t_i>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ In the proof, the $x_i$ are the points to pulverize, and the center of balls are $q1,...,q_k$. It seems to me that $c_Q$ only shifts the value of $t$. The problem with my answer is that I used the euclidian distance instead of the $||\cdot||_1$, so my answer may not have anything to do with your question. | |
| Jun 15, 2020 at 0:37 | comment | added | ato_42 | Thank you. If I'm correct, your result is for the function class $F := \left\{ \min_{q \in Q} d(x,q) \; | \; Q \subset \mathbb{R}^{d}, |Q| = k \right\},$ where $d(x,y)$ is a distance on $\mathbb{R}^d$. How can one adapt the proof to find VC dimension of the collection of sets (indexed over Q) $ C := \left\{ (x \in \mathbb R^d,t\in \mathbb R), \min_{q \in Q} d(x,q) - t > 0 \; | \; Q \subset \mathbb{R}^{d}, |Q| = k \right\}, $ (which corresponds to the VC of the indicator function class I defined) | |
| Jun 13, 2020 at 20:44 | history | edited | Gustave Emprin | CC BY-SA 4.0 |
added 790 characters in body
|
| Jun 13, 2020 at 19:27 | comment | added | Gustave Emprin | The number of open regions $P_d(N)$ was posted by @AnginaSeng at math.stackexchange.com/questions/2312255/… | |
| Jun 13, 2020 at 19:17 | history | edited | Gustave Emprin | CC BY-SA 4.0 |
added 5 characters in body
|
| Jun 13, 2020 at 19:08 | history | answered | Gustave Emprin | CC BY-SA 4.0 |