\documentclass[japanese,other]{jnlp_3.8}
\usepackage{jnlpbbl_2.3}
\usepackage[dvipdfmx]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[hyphens]{url}
\usepackage{array}
\usepackage{hangcaption_jnlp}
\allowdisplaybreaks

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\dyck}[1]{\mathrm{Dyck}_{#1}}
\newcommand{\sdyck}[1]{\mathrm{Shuffle\text{-}Dyck}_{#1}}
\newtheorem{theorem}{定理}
\newtheorem{proposition}{命題}
\newtheorem{corollary}{系}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Volume{32}
\Number{4}
\Month{December}
\Year{2025}
%%%%\Issuetitle{「　　　　」特集号}

\setcounter{page}{1310}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%   タイトル部分                                      %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\jsubject{学会記事}
\jtitle{Theoretical Analysis of Hierarchical Language Recognition and Generation
by Transformers without Positional Encoding}
\jauthor{早川　大地\affiref{Author_1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% 英語タイトル・英語著者名
\etitle{Theoretical Analysis of Hierarchical Language Recognition and Generation
by Transformers without Positional Encoding}
\eauthor{Daichi Hayakawa \affiref{Author_1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\headauthor{早川}
\headtitle{ACL2025採択論文と執筆を振り返って}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% 所属
\affilabel{Author_1}{東京大学}{The University of Tokyo}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{はじめに}

本稿では，ACL 2025に採択された論文``Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encoding''\cite{hayakawa-sato-2025-theoretical}についての解説をする．
本研究は，Transformerが位置符号化を用いなくても，入力列の先頭に開始トークンと呼ばれる特殊なトークンを導入することで，階層構造をもつ言語を正しく認識・生成できることを，表現力の観点から示したものである．
さらに本稿では，論文内容の解説に加えて，研究テーマを決定するまでの過程と実際に参加したACL 2025の経験についても述べる．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{研究テーマ決定の過程}

本研究の出発点は，Transformerアーキテクチャがトークン列に含まれる「数」の情報をどのように保持しているのかという疑問であった．Transformerの重要なコンポーネントである自己注意機構(Self-Attention)では，アテンション重みがソフトマックス関数を用いて通常計算され，各トークンは他のトークンを重みつき平均として集約する．この処理は，直感的には「数」の情報を「割合」の情報へ変換しており，「数」の情報が失われてしまう可能性がある．
例えば，以下2つのトークン列を考える:
\begin{equation*}
\text{(i)}\quad \texttt{a} \quad \texttt{b} \quad,\qquad \text{(ii)}\quad \texttt{a} \quad \texttt{a} \quad \texttt{b} \quad \texttt{b} \quad 
\end{equation*}
末尾のトークン$\texttt{b}$からはどちらも同一のトークン列に見えてしまうのではないかという疑問が生じる．これは，$a_{\texttt{b}\rightarrow \texttt{a}}, a_{\texttt{b}\rightarrow \texttt{b}}$を，それぞれトークン$\texttt{b}$から$\texttt{a}, \texttt{b}$へのアテンションスコアとしたとき，いずれの場合もトークン$\texttt{a}$の情報とトークン$\texttt{b}$の情報を$\exp({a_{\texttt{b}\rightarrow \texttt{a}}}) : \exp({a_{\texttt{b}\rightarrow \texttt{b}}})$の割合で集約するためである．

このように「数」の情報を必要とするタスクに対する，Transformerの性能をアーキテクチャの観点から分析している研究を探す過程で，Yaoらの研究\cite{yao-etal-2021-self}に出会った．この論文では，Transformerが階層的言語を処理できるかどうかを調べるため，重要な言語クラスであるDyck言語に注目し，言語の認識・生成として問題を定式化した上で，表現力の観点からTransformerがDyck言語を認識・生成できることを示した．ここで，Dyck言語とは，直感的には整合のとれた括弧列のみから構成される文脈自由言語である．例えば，$()()$はDyck言語に属するが，$()(($は属さない．

Transformerがこのような「数」の情報を必要とするタスクを解ける理由を理解するため，この論文および関連研究(\cite{NEURIPS2023_79ba1b82}, \cite{bhattamishra-etal-2020-ability})を読み進めていった結果，表\ref{tab: diff of results}に示すように，これらの研究には現実のTransformerとは異なる設定や非効率的な点が存在していることがわかった．具体的には次の3点である：(i)特定の位置符号化を仮定していること，(ii)ネットワーク幅がDyck言語の括弧の種類数$k$に線形以上に依存していること，(iii)Dyck言語のサブセットのみを対象としていること，である．
これらは本質的に必要な仮定なのだろうか？もしそうであれば，現実のTransformerは階層構造を完全には把握できないことになる．文脈自由文法は，自然言語をモデリングする際や，プログラミング言語を定義する際に使用されており，両言語を解釈する上で極めて重要である．そのため，「現実的な条件下でTransformerは階層構造をどこまで把握できるのか」というテーマは，理論的にも応用的にも重要な課題であり，本研究の中心的なテーマとして位置づけられた．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% table 1
\begin{table}[t]
\input{33table01.tex}%
\hangcaption{本研究と既存研究との比較．$\dyck{k, D}$とは，階層構造の深さが$D$に制限した$\dyck{k}$の部分集合を表す．ネットワーク幅はTransformerブロックの幅を表し，各タスクに固有のヘッド部分は除いている．タスク固有のヘッドはと，認識タスクでは$\mathbb{R}^{d_{\mathrm{model}}}\rightarrow \mathbb{R}$の写像，生成タスクでは$\mathbb{R}^{d_{\mathrm{model}}}\rightarrow\mathbb{R}^K$（ただし $K$は語彙の種類）の写像である．また，位置符号化に関して，例えば，$i/n$は入力長の最大値を$n$と仮定し，$i$番目のトークンに$i/n$という値を付加することを表す．}
\label{tab: diff of results}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{本研究の理論的結果}

本研究では，Yaoらの研究\cite{yao-etal-2021-self},と同様に，Dyck言語の認識・生成として問題を定式化し分析を行っている．

$\dyck{k}$は$k$種類の括弧からなるDyck言語を表す．例えば$\dyck{2}$言語は2種類の括弧$(, ), \{, \}$からなる言語であり，$(\{\})()$は$\dyck{2}$に属するが，$\{())$は$\dyck{2}$に属さない．チョムスキー＝シュッツェンベルガー表現定理\cite{CHOMSKY1959118}によれば，任意の文脈自由言語は，正規言語とDyck言語の共通部分のホモモルフィズムで表現できる．このことから，Dyck言語は文脈自由言語のクラスの性質を有した極めて重要な言語クラスであるといえる．

次に，本研究で扱う認識・生成タスクについて説明する．認識タスクとは，与えられた文字列が，対象とする言語に属しているかを判定する問題である．例えば，$\dyck{2}$の認識タスクでは，$(\{\})()$が与えられた場合には「属する」と，$\{())$に対しては「属さない」と判定できれば正解となる．一方，生成タスクとは，正しいDyck言語の接頭辞が与えられたときに，その続きとして出現しうる次の文字を予測する問題である．例えば，$\dyck{2}$の生成タスクでは，$(\{\})($に対しては，次に現れる可能性のある文字の集合として$(, ), \{$を出力できれば正解となる．

本研究では，入力列の先頭に付加する特殊なトークン（以下，開始トークン）を利用した，位置符号化なしのTransformerを対象とし，以下では各定理の内容を具体的に紹介する．
まず，定理1および2は，位置符号化を用いないTransformerがDyck言語を効率的に処理できることを示している．
なお，ここで示す定理番号は，原論文の番号に対応していることに留意されたい．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5\baselineskip}

{
\renewcommand{\thetheorem}{1, 2}
\begin{theorem} [Transformerによる$\dyck{k}$の認識・生成]
    任意の括弧の種類数$k$に対して，$\dyck{k}$を認識・生成する，開始トークンとCausal maskingを有する，$O(\log k)$幅の定数層の位置符号化を用いないTransformerネットワークが存在する．
\end{theorem}
}

\vspace{0.5\baselineskip}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

定数層のTransformerで$\dyck{k}$を認識できる理由を簡潔に説明する．本定理の証明は，認識タスクを解くTransformerを実際に構成することによってなされ，図\ref{fig:dyck_recognition}に示すように3つのフェーズに分解できる．まず第1のフェーズでは，開始トークンへのアテンションスコアの割合を用いて，各トークンの位置および階層の深さの情報を計算する．次に第2のフェーズでは，各閉括弧が，自身と深さが合致した最も近い開括弧を参照し，括弧の種類が一致するかを判定する．最後の第3のフェーズでは，第2のフェーズで得られた局所的な判定結果を自己注意機構で集約することで，入力文字列が$\dyck{k}$に属するかどうかを最終的に判定する．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig 1
\begin{figure}[t]
    \begin{center}
    \includegraphics{32-4ia33f01.eps}
    \end{center}
    \caption{$\dyck{k}$を認識するTransformerの構成方法．図中の$\texttt{bos}$は開始トークンを表す．}
    \label{fig:dyck_recognition}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

さらに以下の命題6では，開始トークンが存在しない場合であっても，先頭のトークンに対し，開始トークンと同様の役割を与えられることができることを示した．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5\baselineskip}

{
\renewcommand{\theproposition}{6}
\begin{proposition} [開始トークンを持たないTransformerによる開始シグナルの生成]
埋め込みベクトルが全て異なり，かつ等しい2ノルムをもつと仮定する．このとき，先頭の2トークンが異なる場合，開始シグナル（先頭のトークンのみ1で，それ以外の場合は0となる中間表現の次元）を生成する開始トークンを持たないTransformerブロックが存在する．  
\end{proposition}
}\label{proposition: starting signal generation}

\vspace{0.5\baselineskip}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

命題6により，開始トークンがない場合の議論を，開始トークンありの場合に帰着させることができ，結果として以下2つの系が導かれる．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{0.5\baselineskip}

{
\renewcommand{\thecorollary}{1, 2}\label{corollary: dyck recognition and generation by transformers without starting token}
\begin{corollary} [開始トークンを持たないTransformerによる$\dyck{k}$の認識と生成]
命題6と同じ仮定の下で，先頭の2トークンが異なる場合，任意の括弧の種類数$k$に対して，$\dyck{k}$を認識・生成する，$O(\log k)$幅で定数層の開始トークンを用いないTransformerネットワークが存在する．
\end{corollary}
}

\vspace{0.5\baselineskip}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

本研究ではさらに，Dyck言語の派生言語であるShuffle-Dyck言語も対象としている．\linebreak
$\sdyck{k}$とは，$k$種類の$\dyck{1}$言語をシャッフルしたものであり，直感的には複数の階層構造を並列に処理する能力の分析に有用である．例えば，$\sdyck{2}$は，$(, )$と$\{,\}$のそれぞれからなる$\dyck{1}$言語をシャッフルしたもので，$(\{)\}()$は，それぞれの種類の部分文字列$()()$, $\{\}$が正しく整合しているため$\sdyck{2}$に属する．詳細は原論文を参照されたい．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{おわりに}
本稿では，位置符号化を用いないTransformerが階層構造を持つ言語を認識・生成できることを理論的に示した研究を解説した．
筆者にとって今回が初めての国際会議での発表であったが，世界中の研究者が一堂に会し，率直な意見をぶつけ合う熱気あふれる議論の場を目の当たりにし大きな衝撃を受けた．現在は研究からは離れて会社員として働いているが，今後もこの分野の最新の研究動向には継続的に触れ，発展を見守っていきたい．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%
%%% Acknowledgement %%%
%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment
本論文の執筆および学会参加にあたり，指導教員である東京大学大学院 情報理工学系研究科 コンピュータ科学専攻 佐藤一誠教授には終始多大なご指導を賜りました．心より感謝いたします．



%%%%%%%%%%%%%%%%%%%%
%%% Bibliography %%%
%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{jnlpbbl_1.8}
\bibliography{33refs}


\clearpage
%%%%%%%%%%%%%%%%%
%%% Biography %%%
%%%%%%%%%%%%%%%%%
\begin{biography}
\bioauthor{早川　大地}{%
2023年東京大学理学部情報科学科卒業．2025年東京大学大学院情報理工学系研究科コンピュータ科学専攻修士課程修了．
}

\end{biography}


\end{document}


