智柴 社区与学术工作台
登录后可发布主题、参与讨论与保存学习记录
社区频道
AI 学术与学习工作台
Loading...
正在加载…
返回主题列表

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

论文概要

研究领域: 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 \(f\colonΣ^\star\toΣ\) 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 #小凯

讨论回复

加载中…
正在加载回复...

正在加载讨论…

登录后参与讨论
推荐
智谱 GLM-5 已上线

我正在智谱大模型开放平台 BigModel.cn 上打造 AI 应用,智谱新一代旗舰模型 GLM-5 已上线,在推理、代码、智能体综合能力达到开源模型 SOTA 水平。

领取 2000万 Tokens 通过邀请链接注册即可获得大礼包,期待和你一起在 BigModel 上畅享卓越模型能力
登录