We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its correct label. When the true labels are determined via a nearest neighbor partition -- i.e. the label of a point is given by which of $k$ centers it is closest to in Euclidean distance -- we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the geometric problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest.


翻译:我们考虑的是多级分类问题,在多级分类中,一连串的对立选择查询到达,必须在线分配标签。与试图尽量减少错误分类率的传统界限不同,我们尽量缩小每个查询与与其正确标签相对应的区域之间的总距离。当真正的标签通过最近的邻里分区确定时,即标出一个点的标签,用点的标签来表示它最接近于欧格利德距离的美元中心,我们表明,一个人可以实现一个与查询总数无关的损失。我们通过显示学习一般二次曲线组合需要每查询几乎线性损失来补充这一结果。我们的结果是在为背景搜索的几何问题提供遗憾保证的基础上形成的。此外,我们开发了一种从多级分类到二元分类的新式的削减技术,可能具有独立的兴趣。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
50+阅读 · 2020年12月14日
最新《几何深度学习》教程,100页ppt,Geometric Deep Learning
专知会员服务
100+阅读 · 2020年7月16日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年1月20日
Max-Margin Contrastive Learning
Arxiv
18+阅读 · 2021年12月21日
Arxiv
7+阅读 · 2021年10月19日
Hardness-Aware Deep Metric Learning
Arxiv
6+阅读 · 2019年3月13日
Arxiv
13+阅读 · 2019年1月26日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
8+阅读 · 2018年5月15日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
0+阅读 · 2022年1月20日
Max-Margin Contrastive Learning
Arxiv
18+阅读 · 2021年12月21日
Arxiv
7+阅读 · 2021年10月19日
Hardness-Aware Deep Metric Learning
Arxiv
6+阅读 · 2019年3月13日
Arxiv
13+阅读 · 2019年1月26日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
8+阅读 · 2018年5月15日
Arxiv
5+阅读 · 2017年12月14日
Top
微信扫码咨询专知VIP会员