图 书 馆
诚实压缩及其在压缩方案中的应用Honest Compressions and Their Application to Compression Schemes |
|
| 课程网址: | http://videolectures.net/colt2013_livni_schemes/ |
| 主讲教师: | Roi Livni |
| 开课单位: | 耶路撒冷希伯来大学 |
| 开课时间: | 2013-08-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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 finite VC-dimension. Specifically, 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 field 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 defined by hyperplanes, polynomials, exponentials, restricted analytic functions and compositions, additions and multiplications of all of the above. |
| 关 键 词: | VC维概念类; 压缩方案; 统计学习理论; 模型理论; 重构函数 |
| 课程来源: | 视频讲座网公开课 |
| 最后编审: | 2019-05-26：cwx |
| 阅读次数: | 31 |