仅需O(d*log(1/ε))比特就能表示数据，新编码器让任意任务预测误差≤ε！
Communication Complexity of Universal Features
📖 AI 总结
该论文研究机器学习中“通用特征”的表示复杂度问题：编码器在任务函数族确定之前观察数据X并生成有限编码，解码器随后需对任意任务f以不超过ε的误差预测f(X)。作者构造的编码器输出长度为O(d*log(1/ε))比特，其中d*为函数族的对偶VC维，其核心是一种新的势函数论证，通过比较贪心选择带来的熵增益与对偶VC维允许的模式数来建立上界。下界结果表明，该表示长度在最坏情况下对每个d*≥1和ε<1/4达到最优（至多相差常数因子），并对每个函数族达到实例级最优（至多相差O(log(1/ε))因子）。作者还给出两种从无标注样本学习该表示的方法，实验验证了贪心构造在精度与规模间的权衡，并探讨了其与神经网络稀疏自编码器的联系。
🔑 关键词速览
| 对偶 VC 维 (dual VC dimension) | 函数族的一种组合复杂度度量，定义为该函数族对偶集族的 VC 维，用于刻画表示学习所需的信息量。 |
| 势函数论证 (potential function argument) | 一种分析算法性能的方法，通过构造一个随算法进程单调变化的势函数来界定每一步的增益或代价。 |
| 贪婪选择 (greedy selection) | 一种逐步构建解的算法策略，每一步都选择当前看来最优的函数，以逼近全局目标。 |
| 稀疏自编码器 (sparse autoencoder) | 一种神经网络模型，通过强制隐藏层稀疏性来学习数据的有效表示，常用于特征提取和降维。 |
| 样本复杂度 (sample complexity) | 学习算法达到给定精度所需的最少训练样本数量，是统计学习理论中的核心概念。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅