배깅을 통한 최적의 자기회귀 사고 과정 학습
Optimal Autoregressive Chain-of-Thought Learning via Bagging
한국어 초록
클래스 $\mathcal{F}$에 속하는 자기회귀 다음 토큰 생성기 $f\colon\Sigma^\star\to\Sigma$가 만든 길이 $T$의 사고 과정(CoT) 시연을 바탕으로 $f$를 학습하는 방법을 연구한다. 배깅을 기반으로 하는 간단한 알고리즘을 제시한다. 이 알고리즘은 학습 데이터의 부트스트랩 표본마다 CoT와 일치하도록 생성기를 학습시키고, 여러 생성기의 다수결 결과를 출력한다. 이진 토큰 집합에서는 CoT 길이 $T$와 무관하게 최적 표본 복잡도 $O((d_{\mathrm{VC}}+\log(1/\delta))/\epsilon)$를 달성한다. 여기서 $d_{\mathrm{VC}}$는 $\mathcal{F}$의 VC 차원이다. 유한 토큰 집합 $\Sigma$에서는 다중 클래스에 대응하는 그래프 차원 $d_{\mathrm{G}}$가 VC 차원을 대신한다. 이때 표본 복잡도는 $\log|\Sigma|$ 인자를 제외하면 최적이다. 다수결 앙상블에 포함되는 생성기의 수는 $O(\log(T/\delta))$이다. 레이블이 없는 프롬프트 $n\log(nT)$개를 추가로 사용하면 앙상블을 $\mathcal{F}$에 속하는 단일 생성기로 증류할 수 있음을 보인다.
원문 초록
We study how to learn an autoregressive next-token generator $f\colon\Sigma^\star\to\Sigma$ 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/\delta))/\epsilon)$, independent of the CoT length $T$, where $d_{\mathrm{VC}}$ is the VC dimension of $\mathcal{F}$. For finite token sets $\Sigma$, 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|\Sigma|$ factor. The number of generators in the majority-vote ensemble is $O(\log(T/\delta))$, and we show that the ensemble can be distilled into a single generator in $\mathcal{F}$ at the expense of $n\log(nT)$ unlabeled prompts.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.