随机自回归学习

受LLM逐步采样下一词元分布的启发，本文提出二元随机自回归PAC学习模型，推广已有确定性自回归学习框架。固定生成器为每个提示字符串指定伯努利下一词元分布；从输入提示开始，采样一个词元并追加，再调用同一生成器，重复M步。研究比较三类监督：一步基础样本、揭示完整M步随机轨迹的思维链样本，以及只揭示最终词元的端到端样本。平方损失误差为ε时，分别研究学习一步概率或终点词元概率所需的最少样本数。随机理论与确定性理论有根本区别：同一ε尺度下，三类任务不存在普适比较，思维链与基础学习、端到端与思维链学习的样本数比都可以同时任意大于M/ε。但改变尺度后，思维链学习在ε尺度的复杂度不超过基础学习在ε/M²尺度的复杂度；忽略对数因子，端到端学习在ε尺度的复杂度不超过(M/ε)乘以思维链学习在Θ(ε)尺度的复杂度。这些尺度依赖基本紧致。论文还分析模型中的d维逻辑函数。