BriefGPT.xyz
Mar, 2015
VC类样本压缩方案
Proper PAC learning is compressing
HTML
PDF
Shay Moran, Amir Yehudayoff
TL;DR
本文提出采样压缩序列作为一种学习算法的抽象形式，并回答了问题：每个概念类别C具有VC维度d的序列都具有指数大小的采样压缩序列，这得益于对VC维下二进制矩阵的逼近极小现象。
Abstract
We prove that proper
pac learnability
implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a
sample compression
scheme of size $2^{O(d)}$. In p
→