ICMLJun, 2024

优化复杂绩效指标的通用在线算法

PDF
TL;DR我们介绍和分析了一种通用的在线算法，适用于二元、多类和多标签分类问题中的各种复杂性能指标，该算法的更新和预测规则简单且计算效率高，无需存储任何过去的数据，而且对于凹函数和平滑度函数达到了 O (ln n/n) 的遗憾，并通过实证研究验证了所提算法的效率。
performance metricsconfusion matrixclassifieronline learningalgorithm
发现论文，激发创造
  • 在线度量算法的混合预测

    本文阐述了一种基于多种算法或预测器的学习增强在线算法技术，通过针对在线问题的分析，设计出与动态组合相竞争的算法，能够在多种预测器之间切换，具有灵活性和实用性。

    Apr, 2023

  • 优化不可分解性能度量：两个类别的故事

    本文提出一种自适应线性化技术，实现了基于 TPR 和 TNR 的点随机更新，通过提出 SPADE 和 STAMP 方法，可以应对实际中出现的数据标签不平衡及其他特殊要求，并获得了显着的速度优势和精准度，同时确保了收敛性。

    May, 2015

  • 在线优化：与动态比较器竞争

    本文提出了一种完全自适应的方法，适用于在线学习中的动态比较基准，并且应用到了零和博弈中。

    Jan, 2015

  • 优化拟线性性能度量的理论：以 F - 度量为例

    研究了一些非线性性能度量的理论属性，包括 F - 度量，Jaccard 指数等，将这些性能度量优化问题归约为具有未知成本的成本敏感分类问题，并提出了一种具有可证明保证的算法来获得近似最优分类器以解决 F - 度量优化问题。

    May, 2015

  • 学习度量的非参数在线回归

    研究在线非参数回归算法，可以学习回归函数平滑的方向；基于回归函数梯度外积矩阵 G，学习 Mahalanobis 度量（可以自适应 G 矩阵的有效秩），同时考虑到 G 的频谱，限制在相同数据序列上的遗憾；作为分析的初步步骤，将 Hazan 和 Megiddo 的非参数在线学习算法扩展，使其能够竞争相对于任意 Mahalanobis 度量计量 Lipschitzness 的函数。

    May, 2017

  • 一种广义的在线镜像下降算法及其在分类和回归中的应用

    本文提供了一种新的方法，将在线预测算法在线镜像下降推广到具有通用更新的时间变化正则化器，并演示了该方法的强大功能。

    Apr, 2013

  • 具有不受信任预测的在线度量算法

    本文提出了适用于任意度量任务系统（MTS）（例如缓存、k-server 和凸体追逐）和在线匹配的预测模型，并利用在线算法理论的结果来展示如何使模型更具鲁棒性，其中特别针对缓存问题，本文提出的算法相对于一般 MTS 问题可使得其性能的预测误差表现成指数级别提升。最后，我们使用实际数据集对所提出的方法进行了实证评估，并得出实用性较好的结论。

    Mar, 2020

  • 多标签分类中基于宏 $K$ 指标的一致算法

    在多标签分类的人口效用框架下，我们考虑复杂性能度量的优化问题。我们主要关注一种指标，它线性可分解为对每个标签分别应用的二分类效用的总和，并对每个实例预测出恰好 k 个标签。这些 “宏 - at-$k$” 指标在具有长尾标签的极端分类问题中具有理想的性质。遗憾的是，at-$k$ 约束将原本相互独立的二分类任务耦合起来，导致优化问题比标准的宏平均更具挑战性。我们提供了一个统计框架来研究这个问题，证明了最优分类器的存在和形式，并基于 Frank-Wolfe 方法提出了一个统计一致且实用的学习算法。有趣的是，我们的主要结果还涉及非线性函数的更一般度量，这些函数是标签混淆矩阵的函数。实证结果证明了所提方法的竞争性能。

    Jan, 2024

  • 非分解损失函数的在线和随机梯度方法

    本文提出了一种针对非可分离损失函数的在线学习框架，通过引入新型算法设计和分析，该模型具有高效的在线学习算法，具有亚线性遗憾和在线转换界限；进一步开发了可扩展的随机梯度下降求解器，经过实验在真实数据集上证明，该方法比近期提出的切割面算法快得多。

    Oct, 2014

  • 在线图算法预测

    本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。

    Dec, 2021