证明近邻法在双度度量空间中在线一致性
Online Consistency of the Nearest Neighbor Rule
- 在双度度量空间中，近邻法仅需温和绝对连续性假设即在线一致
- 错误率最终趋于零，无需独立同分布或类别分离强假设
- 适用于非平稳数据流，适合理论学习与在线算法研究者
在可实现的在线设定中，学习者需对数据流进行预测，且每次预测后会获得正确答案。若学习规则的错误率最终消失，则称其为在线一致。近邻法（Fix and Hodges, 1951）是一种基础预测策略，但以往仅在强统计或几何假设下被证明一致：实例独立同分布，或标签类别良好分离。本文证明，在双度度量空间中，只要实例生成过程相对于一个有限、上双度测度是均匀绝对连续的，近邻法对所有可测函数均在线一致。
原文摘要 · Abstract (English)
In the realizable online setting, a learner is tasked with making predictions for a stream of instances, where the correct answer is revealed after each prediction. A learning rule is online consistent if its mistake rate eventually vanishes. The nearest neighbor rule (Fix and Hodges, 1951) is a fundamental prediction strategy, but it is only known to be consistent under strong statistical or geometric assumptions: the instances come i.i.d. or the label classes are well-separated. We prove online consistency for all measurable functions in doubling metric spaces under the mild assumption that the instances are generated by a process that is uniformly absolutely continuous with respect to a finite, upper doubling measure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。