Putting the "Learning" into Learning-Augmented Algorithms for Frequency Estimation
Putting the "Learning" into Learning-Augmented Algorithms for Frequency Estimation
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Elbert Du;Franklyn Wang;M. Mitzenmacher
中科院分区：
文献类型：
--
作者：
Elbert Du;Franklyn Wang;M. Mitzenmacher
在学习增强算法中，使用来自机器学习算法的信息来增强算法。反过来，这表明我们应该针对目标算法定制我们的机器学习方法。我们在这里考虑这种协同作用的背景下学习计数分钟草图从（Hsu等人，2019年）。这里的学习用于从数据流中预测重量级人物，这些人物在草图之外被显式计算。我们表明，一个近似足够的统计性能的基本计数最小草图是由覆盖的预测，或归一化的L1范数的关键是过滤的预测显式计数。我们表明，根据平均绝对频率误差，经过训练以优化覆盖范围的机器学习模型与先前的方法相比，性能有了很大的提高。我们的源代码可以在https://github.com/franklynwang/上找到。
In learning-augmented algorithms, algorithms are enhanced using information from a machine learning algorithm. In turn, this suggests that we should tailor our machine-learning approach for the target algorithm. We here consider this synergy in the context of the learned count-min sketch from (Hsu et al., 2019). Learning here is used to predict heavy hitters from a data stream, which are counted explicitly outside the sketch. We show that an approximately sufficient statistic for the performance of the underlying count-min sketch is given by the coverage of the predictor, or the normalized L 1 norm of keys that are filtered by the predictor to be explicitly counted. We show that machine learning models which are trained to optimize for coverage lead to large improvements in performance over prior approaches according to the average absolute frequency error. Our source code can be found at https://github.com/franklynwang/ putting-the-learning-in-LAA .