Count-Min 算法:利用经验误差分布进行最优估计和紧密误差界限
用机器学习技术改进估计频率的算法,特别是使用了重要元素预测的算法,在一些参数范围内以及加入重要元素预测后,理论上超越了之前算法的性能,并在实验中取得了优于其他方法的表现。
Dec, 2023
本文提出了一种流式算法,可以在一次样本遍历中,线性时间内实现并且使用的空间仅为每个样本大小的线性。算法能够在每个问题上达到与 $ERM$ 相同的统计收敛速率,甚至考虑常数因素,而且算法性能随初始误差下降的超多项式速率,算法易于并行。此外,本文量化了算法与 $ERM$ 竞争的(有限样本)速度。
Dec, 2014
本文详细研究了在保持从统计学家隐藏数据的严格设置中概率分布(离散和连续)的估计,给出了这些本地私有设置中估计的尖锐最小极限速率,展示了隐私和收敛速率之间的根本权衡,以及提供允许沿隐私 - 统计效率连续体移动的工具。我们结果的一个后果是,华纳关于随机响应的经典工作是进行调查抽样并保持受访者隐私的最佳方法。
May, 2013
本文研究数据保护与统计估计之间的平衡,开发了私有版本的信息熵界限,提出了一些新的基于隐私保护机制和计算效率估计,并给出了一些实验结果,证明了这些过程的重要性。
Apr, 2016
探讨了基于 Catoni 均值估计的经验风险最小化问题,并发展了基于 Catoni 的均值估计器的链式论据性能界限,以应对损失函数不一定有界,可能具有重尾分布的情况。
Jun, 2014
本篇论文设计了一种基于部分知识编译的新型近似模型计数方法 PartialKC,其在可伸缩性和准确性方面都表现显著优于以前的近似计数器,并可以收敛于精确计数器,实验证明其具有精确计数器可比的性能。
Dec, 2022
研究计算基于观测边际的离散对象的最大熵分布的问题,研究表明在一般条件下存在着多项式大小的描述,给出了一些关于近似计算和计数最大熵分布的算法,并且阐明了计算最大熵分布和计算数量之间的等价性。
Apr, 2013
本研究针对离散分布 P 进行 n 个独立同分布样本的香农熵估计,使用逼近理论法进行估计,实现了在估计熵的最小二乘率方面的极致。通过采用自适应估计框架,该方法相对极小值优化估计方法在分布 P 的嵌套子序列上实现了最小二乘率的估计,从而进一步证明了估计在样本 n 的情况下是最优的,并且基本上相当于 MLE 使用 nlnn 个样本进行估计。
Feb, 2015
本论文详细介绍了针对离散分布的 Shannon 熵估计器的一些估计方法,适用于 N 个样本点分布到 M 个箱中,其中 N 和 M -> oo,但 N/M < oo,高采样区域(每个箱子 <<1 个点)具有指数级小的偏差,低采样区域的误差增加,但仍远小于大多数其他估计器。其中一个优势是我们的主要估计器通过解析方法得到,偏差有明确已知的解析公式。
Jul, 2003
MinMax 采样是一种降采样实向量的技术,旨在最小化所有向量分量上的最大方差。本研究提出一种有偏的 MinMax 估算方案 (B-MinMax),通过增加估算偏差来减小方差。当无聚合时,B-MinMax 的均方差严格低于无偏的 MinMax 估计器;当需要聚合时,在样本量较小或聚合向量数目有限时,B-MinMax 较为优选。实验证明,在实际应用中,该方法可以大幅降低 MinMax 采样的均方差。
Apr, 2024