Honest Compressions and Their Application to Compression Schemes
Honest Compressions and Their Application to Compression Schemes
复制标题
诚实压缩及其在压缩方案中的应用
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Pierre Simon
中科院分区：
文献类型：
--
作者：
Roi Livni;Pierre Simon
为每个具有有界 VC 维度的概念类提供压缩方案，是统计学习理论中最古老的未决问题之一。在这里，我们证明了在比有界 VC 维度更强的假设条件下，这种压缩方案的存在。具体来说，我们为每个概念类关联了一个概念类族，我们称之为交替概念类。在这些概念类的 VC 维度有界的假设下，我们证明了压缩方案的存在性。这一结果是由模型理论领域在类比问题上的最新进展促成的。事实上，我们的证明可以看作是这些进展的建设性证明。这意味着我们明确地描述了重构函数。同样重要的是，我们提出的定理和证明都是纯粹的组合术语，不熟悉模型理论的读者也可以使用。此外，我们还利用模型理论的工具，在一些有趣的情况下应用了我们的结果并证明了压缩方案的存在，如由超平面、多项式、指数、受限解析函数和上述所有函数的组合、加法和乘法表示的概念类。
The existence of a compression scheme for every concept class with bounded VC-dimension is one of the oldest open problems in statistical learning theory. Here we demonstrate the existence of such compression schemes under stronger assumptions than nite VCdimension. Specically, for each concept class we associate a family of concept classes that we call the alternating concept classes. Under the assumption that these concept classes have bounded VC-dimension, we prove existence of a compression scheme. This result is motivated by recent progress in the eld of model theory with respect to an analogues problem. In fact, our proof can be considered as a constructive proof of these advancements. This means that we describe the reconstruction function explicitly. Not less important, the theorems and proofs we present are in purely combinatorial terms and are available to the reader who is unfamiliar with model theory. Also, using tools from model theory, we apply our results and prove existence of compression schemes in interesting cases such as concept classes dened by hyperplanes, polynomials, exponentials, restricted analytic functions and compositions, additions and multiplications of all of the above.