Data summarization has become a valuable tool in understanding even terabytes of data. Due to their compelling theoretical properties, submodular functions have been in the focus of summarization algorithms. These algorithms offer worst-case approximations guarantees to the expense of higher computation and memory requirements. However, many practical applications do not fall under this worst-case, but are usually much more well-behaved. In this paper, we propose a new submodular function maximization algorithm called ThreeSieves, which ignores the worst-case, but delivers a good solution in high probability. It selects the most informative items from a data-stream on the fly and maintains a provable performance on a fixed memory budget. In an extensive evaluation, we compare our method against $6$ other methods on $8$ different datasets with and without concept drift. We show that our algorithm outperforms current state-of-the-art algorithms and, at the same time, uses fewer resources. Last, we highlight a real-world use-case of our algorithm for data summarization in gamma-ray astronomy. We make our code publicly available at https://github.com/sbuschjaeger/SubmodularStreamingMaximization.


翻译:数据总和已经成为理解甚至数据百万字节的宝贵工具。 由于其令人信服的理论属性, 子模块函数一直处于总化算法的焦点。 这些算法提供了最坏情况的近似保证, 以更高的计算和记忆要求为代价。 然而, 许多实际应用并不属于最坏的情况, 但是通常要更加守规矩。 在本文中, 我们提议一个新的子模块函数最大化算法, 叫做“ 三赛维斯 ”, 它忽略了最坏的情况, 但提供了一种非常可能的良好解决方案。 它选择了来自苍蝇上的数据流中信息最丰富的项目, 并在固定的记忆预算上保持了一种可变的性能。 在一项广泛的评估中, 我们比较了我们的方法, 在8美元不同的数据集上, 并且没有概念的漂移, 。 我们显示我们的算法优于当前最先进的算法, 同时使用的资源也更少。 最后, 我们强调我们用于伽玛射线天文学中的数据总和算法的实世应用案例。 我们通过 https:// magres/Mabexmasialalalalalal。

0
下载
关闭预览

相关内容

【实用书】流数据处理,Streaming Data,219页pdf
专知会员服务
76+阅读 · 2020年4月24日
专知会员服务
60+阅读 · 2020年3月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
8+阅读 · 2018年10月31日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习算法实践:决策树 (Decision Tree)
Python开发者
9+阅读 · 2017年7月17日
Arxiv
1+阅读 · 2021年2月11日
Arxiv
0+阅读 · 2021年2月10日
Arxiv
0+阅读 · 2021年2月9日
Arxiv
0+阅读 · 2021年2月9日
Arxiv
0+阅读 · 2021年2月8日
Arxiv
4+阅读 · 2019年1月1日
Arxiv
5+阅读 · 2018年1月30日
VIP会员
相关VIP内容
【实用书】流数据处理,Streaming Data,219页pdf
专知会员服务
76+阅读 · 2020年4月24日
专知会员服务
60+阅读 · 2020年3月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
8+阅读 · 2018年10月31日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习算法实践:决策树 (Decision Tree)
Python开发者
9+阅读 · 2017年7月17日
Top
微信扫码咨询专知VIP会员