[论文] Optimal Autoregressive Chain-of-Thought Learning via Bagging

## 论文概要 **研究领域**: ML **作者**: Awni Altabaa, John Laffert...

论文概要

研究领域: ML 作者: Awni Altabaa, John Lafferty, Omar Montasser 发布时间: 2026-11-16 arXiv: 2611.21597

中文摘要

我们研究如何从给定的函数类 F 中学习自回归下一 token 生成器 f,给定由 f 生成的长度为 T 的思维链(CoT)演示。我们提出一个基于 Bagging 的简单算法,它输出在训练数据自助样本上训练为 CoT 一致的生成器的多数投票结果。对于二元 token 集,它实现了 O((d_VC + log(1/δ))/ε) 的最优样本复杂度,与 CoT 长度 T 无关,其中 d_VC 是 F 的 VC 维。对于有限 token 集 Σ,VC 维被多分类类似量——图维数 d_G 替代,样本复杂度在 log|Σ| 因子内最优。多数投票集成中的生成器数量为 O(log(T/δ)),我们证明该集成可以被蒸馏为 F 中的单个生成器,代价是 n log(nT) 个无标注提示。

原文摘要

We study how to learn an autoregressive next-token generator fcolonΣ^startoΣ from a class mathcal{F}, given chain-of-thought (CoT) demonstrations of length T generated by f. We present a simple algorithm based on bagging, which outputs a majority vote of generators that are trained to be CoT-consistent on bootstrap samples of the training data. For binary token sets, it achieves the optimal sample complexity of O((d_{mathrm{VC}}+log(1/δ))/ε), independent of the CoT length T, where d_{mathrm{VC}} is the VC dimension of mathcal{F}. For finite token sets Σ, the VC dimension is replaced by a multiclass analogue, the Graph dimension d_{mathrm{G}}, and the sample complexity is optimal up to a log|Σ| factor. The number of generators in the majority-vote ensemble is…

— 自动采集于 2026-11-18

#论文 #arXiv #ML #小凯

发表回复

人生梦想 - 关注前沿的计算机技术 acejoy.com 🐾 步子哥の博客 🐾 背多分论坛 🐾 借一步网 🐾 智柴网 沪ICP备2024052574号-1