论文标题
图中球的样品压缩方案
Sample compression schemes for balls in graphs
论文作者
论文摘要
机器学习中的开放问题之一是，VC-Dimension $ d $的任何设定室是否承认$ o（d）$的样本压缩方案。在本文中，我们研究了图中的球。对于一个agragh $ g =（v，e）$的球$ b = b_r（x）$，$ b $的可实现样本是签名的子集$ x =（x^+，x^ - ）$ v $ $ v $，这样$ b $包含$ x^+$，并且与$ x^ - $不相交。尺寸$ k $的适当样品压缩方案由压缩机和重建器组成。压缩机将所有可实现的样本$ x $映射到最多$ k $的子样本$ x'$。重建者地图每个这样的子样本$ x'$ to a ball $ b'的$ g $，以便$ b'$包括$ x^+$，并且与$ x^ - $不相交。 对于任意半径$ r $的球，我们设计了适当的标记样品压缩计划，大小为2美元的树木，尺寸为$ 3 $的循环，尺寸为$ 4 $的$ 4 $，尺寸为$ 6 $ $ 6 $ $ 6 $ of Cycles of Cycles $ 22 $ $ 22 $的免费中间图。对于给定半径的球，我们设计了适当的标记的样品压缩方案，树木的尺寸为$ 2 $，间隔图的尺寸为$ 4 $。我们还设计了$δ$ hyperbolic图的球2的近似样品压缩方案。
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 $δ$-hyperbolic graphs.
