Sample compression schemes for balls in graphs
| Autor: | Chalopin, Jérémie, Chepoi, Victor, Inerney, Fionn Mc, Ratel, Sébastien, Vaxès, Yann |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics, 37(4):2585-2616, 2023 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1137/22m1527817 |
| Popis: | One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a realizable sample for $B$ is a signed subset $X=(X^+,X^-)$ of $V$ such that $B$ contains $X^+$ and is disjoint from $X^-$. A proper sample compression scheme of size $k$ consists of a compressor and a reconstructor. The compressor maps any realizable sample $X$ to a subsample $X'$ of size at most $k$. The reconstructor maps each such subsample $X'$ to a ball $B'$ of $G$ such that $B'$ includes $X^+$ and is disjoint from $X^-$. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs. Comment: 27 pages, 8 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|