COLT
[Paper Note] Learning Compositional Functions with Transformers from Easy-to-Hard Data, Zixuan Wang+, COLT'25
Paper/Blog Link My Issue
#Analysis #Pretraining #LanguageModel #Transformer #PostTraining Issue Date: 2025-06-01 GPT Summary- 本研究では、Transformerベースの言語モデルの学習可能性を探求し、$k$-fold compositionタスクに焦点を当てる。$O(\log k)$層のトランスフォーマーでこのタスクを表現できる一方、SQオラクルに対するクエリの下限を示し、サンプルサイズが指数的である必要があることを証明。さらに、カリキュラム学習戦略を用いて、簡単な例と難しい例を含むデータ分布がトランスフォーマーの効率的な学習に必要であることを明らかにした。 Comment
元ポスト:
こちらはまず元ポストのスレッドを読むのが良いと思われる。要点をわかりやすく説明してくださっている。
元ポストとalphaxivでざっくり理解したところ、
Transformerがcontextとして与えられた情報(σ)とparametric knowledge(π)をk回の知識マッピングが必要なタスク(k-fold composition task)を学習するにはO(log k)のlayer数が必要で、直接的にk回の知識マッピングが必要なタスクを学習するためにはkの指数オーダーのデータ量が最低限必要となることが示された。これはkが大きくなると（すなわち、複雑なreasoning stepが必要なタスク）になると非現実的なものとなるため、何らかの方法で緩和したい。学習データを簡単なものから難しいものをmixingすること（カリキュラム学習）ことで、この条件が緩和され、指数オーダーから多項式オーダーのデータ量で学習できることが示された
といった感じだと思われる。
じゃあ最新の32Bモデルよりも、よりパラメータ数が大きくてlayer数が多い古いモデルの方が複雑なreasoningが必要なタスクを実は解けるってこと！？直感に反する！と一瞬思ったが、おそらく最近のモデルでは昔のモデルと比べてparametric knowledgeがより高密度に適切に圧縮されるようになっていると思われるので、昔のモデルではk回の知識マッピングをしないと解けないタスクが、最新のモデルではk-n回のマッピングで解けるようになっていると推察され、パラメータサイズが小さくても問題なく解けます、みたいなことが起こっているのだろう、という感想を抱くなどした
[Paper Note] Contextual Dueling Bandits, Miroslav Dudík+, COLT'15, 2015.02
Paper/Blog Link My Issue
#InformationRetrieval #LearningToRank #Online/Interactive #Pocket Issue Date: 2018-01-01 GPT Summary- 相対的なペアワイズ比較を用いて文脈情報を活用した行動選択の学習問題を、デュエリングバンディットフレームワークで拡張して研究。新たに提案する「フォン・ノイマン勝者」は、他のポリシーに勝つか引き分けるランダム化ポリシーで、コンドルセ勝者の制限を克服。オンライン学習のための3つの効率的なアルゴリズムを提示し、特に低い後悔を達成するアルゴリズムはポリシー空間に対して線形の要件を持つ。その他の2つは、オラクルへのアクセスがあれば対数的な要件で済む。