Nov, 2010
来自精确采样的流算法
Streaming Algorithms from Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
TL;DR该研究提出了一种名为 Precision Sampling 的概率性方法来解决一系列数据流算法问题,包括向量构图、重量估算以及求不同范数的估值,同时也能够很好地解决估值的精度问题。
Abstract
A technique introduced by Indyk and Woodruff [STOC 2005] has inspired several
recent advances in data-stream algorithms. We show that a number of these
results follow easily from the application of a single probabilistic method
called →
data-stream algorithmsprecision samplingvector sketchingheavy-hitter estimationapproximation algorithms
发现论文,激发创造
非自适应自适应抽样的转门流
该研究提出了一种适应性采样算法,能够在单处理器计算中对数据进行概括,同时提供了一种在旋门流数据上执行的采样算法,同时进行了容器选择、子空间逼近、投影聚类和体积最大化等各种类型的数据概括算法。
Apr, 2020
做更少,得更多:带子采样的流式子模最大化
该论文提出了首个一次遍历的流算法,用于求解子模最大化问题,采用数据采样,能够在各种情况下获得最紧密的逼近保证,同时具有最小的内存占用和对函数评估数量的最低要求,试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上
Feb, 2018
改进的频率估计算法(带有或不带有预测)
用机器学习技术改进估计频率的算法,特别是使用了重要元素预测的算法,在一些参数范围内以及加入重要元素预测后,理论上超越了之前算法的性能,并在实验中取得了优于其他方法的表现。
Dec, 2023
有关算法子采样的计量经济学视角
这篇论文研究数据分析中的线性回归和数据素描技术,探讨在样本量有限的情况下如何选择行列子集对数据进行估计和推断,发现虽然算法上的优化子集无法适用于预测和推断,但通过统计学方法可以提供建议的子集大小,并通过实验表明,使用不同的子集来估计结果可以将预测结果效率与使用全样本的方法几乎相同。
Jul, 2019
简单且确定的矩阵草图
该研究论文介绍了一种基于矩阵素描的流式算法,可用于近似项目频率,具有确定性、易于实现和基本易于证明的优点,并在计算上具有竞争力,比目前广泛使用的方法能够得到更为精确的矩阵素描。
Jun, 2012
从数据流中公平且代表性地选择子集
本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题,并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。
Oct, 2020