\section{はじめに}
構文解析において，精度と同様，計算効率も，自然言語処理の重要な問題の一つである．構文解析の研究では，精度に議論の重点を置くことが多いが，効率についての研究もまた重要である．特に実用的な自然言語処理のアプリケーションにとっては，そうである．精度を落とすことなく効率を改善することは，とても大きな課題である．本研究の目的は，日本語の係り受け解析(依存構造解析)を行なう効率のよいアルゴリズムを提案し，その効率の良さを理論的，実験的の両面から示すことである．本論文では，日本語係り受け解析の線形時間アルゴリズムを示す．このアルゴリズムの形式的な記述を示し，その時間計算量(timecomplexity)を理論的に論じる．加えて，その効率と精度を京大コーパスVersion2\cite{Kurohashi1998}を使って実験的に評価する．本論文の構成は以下の通りである．第~2節では，日本語の構文的な特徴と典型的な日本語文の解析処理について述べる．第~3節では，英語や日本語の依存構造解析の従来研究について簡単に述べる．その後，第~4節で我々の提案手法を述べる．次に，第~5節で，二つの文節の依存関係を推定するための改良したモデルを述べる．第~6節では実験結果とその考察を記す．最後に，第~7節で本論文での我々の貢献をまとめる．
\section{日本語文の解析}
本節では，日本語の構文的特徴と典型的な日本語文の解析の手順について整理する．\subsection{日本語の構文的特徴}\label{sec:prop}日本語は基本的にはSOV言語である．語順は比較的自由である．英語では，文中の語の構文的機能は語順で表される．一方，日本語では，後置詞(postpositions)によって表される．この点では，名詞の後に置かれる日本語の格助詞はドイツ語名詞の格変化と類似の役割を持っている．ドイツ語名詞は格変化することによって，文法的な格を表している．文節の概念\footnote{韓国語の{\emeojeol}も日本語の文節と似た概念である\cite{Yoon1999}．文献\cite{Abney1991}で定義される英語のチャンク(chunk)も文節に近いといえる．}は上記の日本語の性質と親和性があり，日本語文を構文的に分析するときに使われてきた．{\em文節}は，1~個以上の内容語(contentwords)とそれに続く0~個以上の機能語(functionwords)から構成される．文節をこのように定義することによって，ドイツ語のような屈折言語において文中の語の文法的役割を分析するときと似た手法を日本語文を分析するときにも使うことができる．それゆえ，厳密なことを言えば，日本語の場合，語順が自由なのではなく，文節の順序が自由である．ただし，文の主動詞を含む文節は文の末尾に置かれなければならない．例えば，以下の2文は同じ意味を持つ:(1)健が彼女に本をあげた．(2)健が本を彼女にあげた．この2例文で，最も右の文節「あげた」(動詞の語幹と，過去や完了を表すマーカで構成されている)は文の末尾に置かれていることに注意されたい．ここで，上に述べたものも含めて，通常の書き言葉の日本語で仮定される係り受けの制約条件をまとめておく．\begin{description}\item[C1.]最も右の文節を除いて，全ての文節は必ず一つの\TermHead{}を持つ．\item[C2.]\TermHead{}となる文節は，必ず係り元の文節の右側に位置する．\item[C3.]係り関係は交差しない\footnote{「これが僕は正しいと思う」という例文のようにこの制約条件が成立しないこともあるが，書き言葉では殆どの場合成り立つ\cite[187ページ]{Nagao1996}．}．\end{description}これらの特徴は，基本的には韓国語やモンゴル語でも共通である．\subsection{日本語文解析の典型的な手順}日本語には前節のような特徴があるので，日本語文の解析では次のような手順が非常に一般的である:\begin{enumerate}\item文を形態素に分割する(つまり形態素解析する)\itemそれらを文節にまとめ上げる\item文節間の係り関係を解析する\itemそれぞれの係り関係にagent，object，locationなどの意味的役割のラベルを付ける\end{enumerate}我々は(3)における係り受け解析に焦点を置く．
\section{関連研究}
ここでは，主に時間計算量に重点を置いて関連研究を述べる．日本語はもちろん英語でも依存構造解析(dependencyanalysis)は研究されている\cite{Lafferty1992,Collins1996,Eisner1996}．これらの論文の解析アルゴリズムでは，$O(n^{3})$の時間がかかる．ここで$n$は単語数である\footnote{Nivre\shortcite{Nivre2003}は，projectivedependencyparsingの決定的なアルゴリズムを提案している．このアルゴリズムの時間計算量の上限は$O(n)$である．このアルゴリズムをスウェーデン語のテキストで評価している．}$^{,}$\footnote{Ratnaparkhiは実際の処理時間が$O(n)$となる句構造を返す英語のパーザについて述べている\cite{Ratnaparkhi1997}．これは依存構造解析について述べたものではない．このアルゴリズムでは，解析途中の各ノードに対して，いくつかの手続きを行ない，その中で確率値の高い$K$個の導出(derivation)を残して解析を進める(幅優先探索)．そのため，時間計算量の上限は$O(n^2)$と考えられる．}．日本語の係り受け解析では，文中の二つの文節の係り受けの確率を使うことが非常に多かった．Harunoら\shortcite{Haruno1998}は，決定木を用いて係り受けの確率を推定した．FujioとMatsumoto\shortcite{Fujio1998}はCollinsのモデル\cite{Collins1996}の修正版を日本語の係り受け解析に適用した．Harunoらと，FujioとMatsumotoの両グループともCYK法を用いている．これは$O(n^{3})$の時間がかかる．ここで$n$は文の長さ，つまり文節数を表している．Sekineら\shortcite{Sekine2000Backward}は最大エントロピー法(MaximumEntropyModeling;ME)を係り受けの確率の推定に使い，後方ビームサーチ(文末から文頭に向かうビームサーチ)で最もよい解析結果を見つける．このビームサーチのアルゴリズムは$O(n^{2})$の時間がかかる．KudoとMatsumoto\shortcite{Kudo2000Japanese}らも同じ後方ビームサーチをMEではなくサポートベクタマシン(SVMs)とともに用いている\footnote{彼らは，係り先候補間の係りやすさの相対的な大小関係をモデル化する手法も報告している\cite{Kudo2005}．係り受けのモデルは異なるが，同じく後方ビームサーチを用いている．}．二つの文節間の係り受けの確率を使わない統計的手法も少ないながらある．一つはSekineの決定的有限状態変換器を用いる手法\cite{Sekine2000Japanese}である．Sekineは，\TermHead{}の場所の97\%は文中の五つの候補でカバーされると報告している．似た現象はMaruyamaとOgino\cite{Maruyama1992}も観測している．これらの調査にもとづき，Sekineは，決定的有限状態変換器を用いる効率のよい解析アルゴリズムを提案している．このアルゴリズムは，考慮する係り先の文節数を制限することでしらみつぶしに探索することを避け，$O(n)$の時間計算量となっている．しかしながら，彼のパーザは京大コーパスに対して77.97\%の係り受け正解率(定義は第~\ref{subsec:results}節で述べる)しか得られていない．これは，89\%を超える現在の最高精度よりもかなり低い．2文節間の係り受けの確率を用いない別の興味深い手法は，KudoとMatsumoto\shortcite{Kudo2002}によるCascadedChunkingModelである．このモデルは\cite{Abney1991,Ratnaparkhi1997}のアイデアにもとづく．彼らはこのモデルとSVMsを用いて，89.29\%を得ている．彼らの手法では，解析時に評価される係り関係の数はCYK法や後方ビームサーチよりも相当少ないが，それでも時間計算量の上限は$O(n^2)$である．以上見たように，高い精度を保ちつつ線形時間の処理を保証して，どのように日本語係り受け解析を行なうかは，まだ解決されていない問題である．以下に記述するアルゴリズムがこの問題に対する答えとなろう．
\section{アルゴリズム}
label{sec:algo}本節では，提案アルゴリズムを解析時に使うものと，学習時に使うものとに分けて記す．解析時のアルゴリズム，その時間計算量，学習時のアルゴリズムを順に述べ，最後に提案アルゴリズムの特徴のまとめと関連研究との理論的な比較を述べる．\subsection{文を解析するアルゴリズム}\begin{figure}[t]//入力:N:一文中の文節の数\\//\hspace*{1em}w[]:処理対象の文の文節列を保持する配列\\//出力:outdep[]:解析結果，つまり文節間の係り関係を格納する整数の配列．\\//\hspace*{1em}例えば，j番目の文節の係り先IDは{\rmoutdep[j]}で表現される．\\//\\//stack:係り元文節のIDを保持する．もし空なら，このスタックに対する\\//\hspace*{1em}popメソッドは，{\rmEMPTY}($-1$)を返す．\\//functionestimate\_dependency(j,i,w[]):\\//\hspace*{1em}{\rmj}番目の文節が{\rmi}番目の文節に係ると判断するとき，非ゼロを返す．\\//\hspace*{1em}それ以外のとき，ゼロを返す．\\functionanalyze(w[],N,outdep[])\\stack.push(0);\hspace*{1em}//ID0をスタックに積む．\\for(inti=1;i$<$N;i++)\{\hspace*{1em}//変数iは係り先文節，変数jは係り元文節を指すのに使う．\\\hspace*{1em}intj=stack.pop();\hspace*{1em}//スタックから値を降ろし，変数jにセットする．\\\hspace*{1em}while(j!=EMPTY\&\&(i==N$-$1$||$estimate\_dependency(j,i,w)))\{\\\hspace*{2em}outdep[j]=i;\hspace*{1em}//j番目の文節がi番目の文節に係る．\\\hspace*{2em}j=stack.pop();\hspace*{1em}//次にチェックすべき係り元文節のIDをスタックから降ろす．\\\hspace*{1em}\}\\\hspace*{1em}if(j!=EMPTY)\\\hspace*{2em}stack.push(j);\\\hspace*{1em}stack.push(i);\\\}\par\vspace{8pt}\caption{提案手法の擬似コード(解析時)．ここで``i==N-1''はi番目の文節が文末の文節であることを\hspace*{27pt}意味している．}\label{code:analysis}\end{figure}\begin{figure}[t]//indep[]:訓練事例から与えられる正しい係り受け関係を保持する整数の配列．\\//\\//functionestimate\_dependency(j,i,w[],indep[]):\\//\hspace*{1em}indep[j]==iが満たされるとき，非ゼロを返す．それ以外のとき，ゼロを返す．\\//\hspace*{1em}同時に，j番目の文節がi番目の文節に係るか係らないかに応じて，1あるいは-1の\\//\hspace*{1em}ラベル付きで，素性ベクタ(エンコードされた事例)を出力する．\\functiongenerate\_examples(w[],N,indep[])\\stack.push(0);\\for(inti=1;i$<$N;i++)\{\\\hspace*{1em}intj=stack.pop();\\\hspace*{1em}while(j!=EMPTY\&\&(i==N$-$1$||$estimate\_dependency(j,i,w,indep)))\{\\\hspace*{2em}j=stack.pop();\\\hspace*{1em}\}\\\hspace*{1em}if(j!=EMPTY)\\\hspace*{2em}stack.push(j);\\\hspace*{1em}stack.push(i);\\\}\par\vspace{8pt}\caption{訓練事例を作るための擬似コード．変数w[],Nとstackは図~\ref{code:analysis}のものと同じである．}\label{code:generate}\end{figure}我々の提案する係り受け解析のアルゴリズムの擬似コードを図~\ref{code:analysis}に示す．このアルゴリズムは，ある文節が別の文節に係るかどうかを決定する推定器(estimator)とともに用いる．推定器の典型的なものとして，SVMや決定木などの訓練できる分類器が考えられる．ここでは，文中の二つの文節の係り関係を推定できる，つまり係るか否かを決定できる何らかの分類器があり，その分類器の時間計算量は文の長さに影響されないと仮定しておく．係り関係の推定器を別にすれば，このアルゴリズムで使うデータ構造はわずか二つである．一つは入力に関するもので，もう一つは出力に関するものである．前者は，チェックすべき係り元の文節のIDを保持するためのスタックである．後者は，既に解析された係り先文節のIDを保持する整数の配列である．\begin{figure}[t]\begin{center}\begin{tabular}{llllll}&健が&彼女に&あの&本を&あげた．\\文節ID&0&1&2&3&4\\係り先&4&4&3&4&-\end{tabular}\end{center}\vspace{8pt}\caption{例文}\label{sample-parsing}\end{figure}以下では，例を使いながら先に示したアルゴリズムの動作を説明する．図~\ref{code:analysis}の擬似コードに沿って，図~\ref{sample-parsing}にある例文を解析してみよう．説明のため，図~\ref{code:analysis}の{\itestimate\_dependency}()として完璧な分類器があるとする．この分類器は図~\ref{sample-parsing}の例文に対して必ず正しい結果を返すとする．まず始めに0(健が)をスタックに積む．0は文の先頭の文節のIDである．この初期化の後，{\rmfor}ループの各繰り返し(iteration)の中で解析がどのように進むかを見る．最初のiterationでは，0番目の文節と1番目の文節(彼女に)の係り関係をチェックする．0番目の文節は1番目の文節に係らないから，0をスタックに積み，次に1を積む．ここで，スタックの底は0であって1ではないことに注意されたい．より小さいIDが必ずスタックの底のほうに保持される．この性質のおかげで，非交差の制約(第~\ref{sec:prop}のC3)を破らずに解析を進めることができる．2回目のiterationでは，1をスタックから降ろし，1番目の文節と2番目の文節(あの)の係り関係をチェックする．1番目の文節は2番目には係らないので，再び1と2をスタックに積む．3回目のiterationでは，2をスタックから降ろし，2番目の文節と3番目の文節(本を)の係り関係をチェックする．2番目の文節は3番目に係るので，その関係を{\itoutdep}[]に格納する．{\itoutdep}[$j$]の値は，第~$j$番目の文節の係り先を表す．例えば{\itoutdep}[$2$]$=3$は2番目の文節の係り先は3番目の文節であることを意味している．次に，1をスタックから降ろし，1番目の文節と3番目の文節の係り関係をチェックする．1番目の文節は3番目に係らないので1を再びスタックに積む．その後，3をスタックに積む．この段階で，スタックには頭から底に向けて3，1，0が格納されている．3回目のiterationでは，3をスタックから降ろす．3番目の文節と4番目の係り関係はチェックする必要がない．4番目の文節は文中の最も末尾の文節であり，3番目の文節は必ず4番目にかかるからである．そこで{\itoutdep}[$3$]$=4$とする．次に1をスタックから降ろす．この場合も，1番目の文節と4番目との係り関係のチェックはする必要がない．同様に，0番目の文節も4番目に係る．結果として{\itoutdep}[$1$]$=4$と{\itoutdep}[$0$]$=4$となる．この時点でスタックは空となり，この解析の関数{\itanalyze}()は終了する．解析結果である係り受け関係は，配列\linebreak{\itoutdep}[]に得られている．\subsection{時間計算量}\label{subsec:time}一見したところ，提案したアルゴリズムの時間計算量の上限は，2重ループを含むため$O(n^{2})$と思える．しかしそうではない．時間計算量の上限が$O(n)$であることを，図~\ref{code:analysis}における{\rmwhile}ループの条件部が何回実行されるかを考えることによって示す．条件部が失敗する回数と成功する回数とに分けて考える．{\rmwhile}ループの条件部は$N-2$回失敗する．何故なら外側の{\rmfor}ループが1から$N-1$へ，つまり$N-2$回実行されるからである．もちろん，{\rmwhile}ループが無限ループになることはない．{\rmwhile}ループの内部でstackに値を新たに積むことなく降ろしているので，いつか$j=={\rmEMPTY}$になる．つまり$j\!={\rmEMPTY}$を満たさず，{\rmwhile}ループを抜けることになる．一方，この条件部は$N-1$回成功する．何故なら{\itoutdep}[$j$]$=i$が$N-1$回実行されるからである．文節$j$それぞれについて，{\itoutdep}[$j$]$=i$は必ず一度だけ実行される．{\itj=stack.pop}()を実行すると，$j$に格納されている値は失われ，その値は二度と再びスタックに積まれることはないからである．つまり，{\rmwhile}ループは，高々$N-1$回実行される．これは末尾の文節を除く文節数に等しい．結局，{\rmwhile}ループの条件部の実行回数は，失敗回数$N-2$と成功回数$N-1$を合計し$2N-3$となる．これは時間計算量の上限が$O(n)$となることを意味している．\subsection{訓練事例を作り出すアルゴリズム}前節のアルゴリズムで用いる分類器のための訓練事例を作り出すには，図~\ref{code:generate}に示すアルゴリズムを使う．図~\ref{code:analysis}にある解析用のアルゴリズムと殆ど同じである．違いは，{\itindep}[]を使って{\itestimate\_dependency}()が正しい係り関係の判定を返す点と，{\itoutdep}[]に係り先のIDを格納する必要がない点である．\subsection{特徴のまとめと関連研究との理論的な比較}\label{comp:theory}我々の提案アルゴリズムは次のような特徴を持つ:\begin{itemize}\item[F1.]特定の機械学習の方法に依存しない．訓練できる分類器ならどれでも使える．\item[F2.]左から右へ文を一度だけスキャンする．\item[F3.]時間計算量の上限は$O(n)$である．アルゴリズム中，最も時間を消費する部分である分類器の呼び出しの回数は，高々$2N-3$回である．\item[F4.]アルゴリズムの流れとデータ構造は非常に簡単である．そのため，実装も易しい．\end{itemize}我々のアルゴリズムと最も関連が深いモデルの一つは，\cite{Kudo2002}の\linebreakCascadedChunkingModelである．彼らのモデルと我々のアルゴリズムはF1を始め多くの共通点がある\footnote{文献\cite{Uchimoto1999}に代表される2文節間の係り受け確率を考える確率モデルと，CascadedChunkingModelとの比較は文献\cite{Kudo2002}で詳細になされている．ほぼ全ての議論が確率モデルと我々の提案手法との比較にも当てはまる．}．彼らのモデルと我々のアルゴリズムの大きな違いは，入力文を何回スキャンするかにある(F2)．彼らのモデルでは，入力文を何回かスキャンする必要があり，これは計算上の非効率につながっている．最悪の場合では$O(n^{2})$の計算が必要になる．我々の解析アルゴリズムは，左から右に一度だけしかスキャンせず，実時間の音声認識などのような実用的なアプリケーションに対しても，より好適であろう．それに加えて，アルゴリズムの流れと利用するデータ構造は，CascadedChunkingModelで使われるものよりもずっと簡単である(F4)．彼らのモデルでは，チャンクタグを保持する配列が必要となり，入力文を何度もスキャンする間，この配列は正しく更新されなければならない．NivreによるProjectiveDependencyParsingの手法\cite{Nivre2003}も，我々のアルゴリズムと深い関係がある\footnote{Nivreのいう``projective''とは，依存関係(係り関係)が交差しないことと同じである．}．彼のアルゴリズムも，スタックを用いており，時間計算量の上限も$O(n)$である．ただし，我々のアルゴリズムが日本語を対象とし，係り先が必ず右にあることを前提にしているのに対し，Nivreのアルゴリズムは依存関係の向きはどちらでもよい．その点では，彼のアルゴリズムは我々の手法をより一般的にしたものと考えることができる．一方，\cite{Nivre2003}では，単語間の依存関係を決めるルールを用意しておき，ある一定の優先度で選ぶとしている\footnote{スウェーデン語を対象に126のルールを人手で記述している．ルールを，「右向きに係る」「左向きに係る」「対象語をスタックから降ろす」「対象語をスタックに積む」の四つのタイプに分け(詳細はここでは略す)，タイプ間の優先度は，事前に人手で決める場合のみ実験で検証されている．ここでいう対象語とは，アルゴリズム中で係り関係をチェックする対象となっている語を指す．}．我々は，依存関係が一方向である日本語に対して，機械学習を用いる方法を提示し，実際に検証している．我々の解析アルゴリズムは，shift-reduce法の最も簡単な形の一つと考えられる．典型的なshift-reduce法との違いは，アクションの型を複数持つ必要がなく，スタックの先頭のみ調べればよいという点である．これらの簡潔さの理由は，日本語が制約C2(第~\ref{sec:prop}節参照)を仮定できること，文脈自由文法の解析ではなく，係り受け関係のみの解析であることの二つによる．
\section{係り関係を推定するためのモデル}
label{sec:models}2文節間の係り関係を推定するために，2文節に関係する形態的，文法的情報を素性のベクタとして表現し，それを入力として分類器に係るか否かを判断させる．その分類器として，サポートベクタマシン(SVMs)\cite{Vapnik1995}を用いた．SVMsは優れた特徴を持っている．その一つは，多項式カーネルを用いると，ある事例の持つ素性の組合せが自動的に考慮される点である．現在まで多数の分類タスクに対して，非常に優れた性能が報告されている．SVMsの形式的な記述については，文献\cite{Vapnik1995}を参照されたい．素性として，第~\ref{subsec:stfe}節以降で述べるものを用いた．実際には2文節間の係り関係の推定の処理は，図~\ref{code:analysis}の{\itestimate\_dependency}()の中で行なう．推定しようとする2文節の形態的，文法的情報を素性のベクタとして表現し，SVMsに係るか否かを判定させることになる．以下では，まず基本となる標準素性を述べ，次にそれに追加して用いる付加的な素性について述べる．\subsection{標準素性}\label{subsec:stfe}ここで「標準素性」といっているものは，\cite{Uchimoto1999,Sekine2000Backward,Kudo2000Japanese,Kudo2002}でほぼ共通に使われている素性セットを指す．それぞれの文節について以下の素性を使った:\begin{enumerate}\item主辞品詞，主辞品詞細分類，主辞活用型，主辞活用形，主辞表層形\item語形品詞，語形品詞細分類，語形活用型，語形活用形，語形表層形\item句読点\item開き括弧，閉じ括弧\item位置—文の先頭か文の末尾か\end{enumerate}ここで主辞とは，概ね文節内の最も右の内容語に相当する．品詞が特殊，助詞，接尾辞を除き，最も文末に近い形態素を指す．語形とは，概ね文節内の最も右の機能語に相当する．品詞が特殊となるものを除き，最も文末に近い形態素を指す．これらに加えて，2文節間のギャップに関する素性も用いた．距離(1，2--5，6以上)と，助詞，括弧，句読点である．\subsection{注目文節の前後の文節}\label{subsec:loc}注目している係り元文節，係り先文節の前後の文節も有用である．それらが固定的な表現や格フレーム，その他の連語を表すことがあるからである．第~$j$番目の文節が係り元文節で，第~$i$番目の文節が係り先文節の候補だとする．$j$番目の文節と$i$番目の文節の前後にある文節のうち，次の三つを素性として考慮する:$j-1$番目の文節($j$に係るときのみ)と，$i-1$番目の文節，$i+1$番目の文節の三つである．我々のアルゴリズムでは，$j<i-1$を満たし$j$番目の文節が$i$番目の文節に係るかチェックしているとき，$i-1$番目の文節は必ず$i$番目の文節に係っていることに注意されたい．提案手法におけるデータ構造を簡単にしておくために，$j$番目，$i$番目の文節からさらに遠い文節については考慮しなかった．なお，$j-1$番目の文節が$j$番目の文節に係るかどうかは{\itoutdep}[]を見れば簡単にチェックできる．注目している文節の前後を使うのは，\cite{Kudo2002}における動的素性\footnote{Kudoらのモデルは，以下の三つから動的素性を作る:$j$番目の文節に係るもの(タイプB)，$i$番目の文節に係るもの(タイプA)，$i$番目の文節の係り先(タイプC)．我々の提案手法では解析が左から右に進むので，タイプCの素性を取り入れるためには，スタッキング\cite{Wolpert1992}やその他の手法を用いる必要がある．}と似ている．\subsection{文節内の追加素性}「標準素性」では，文節内に二つ以上の機能語を含むとき格助詞の情報を見落とすことがある．ある文節が格助詞と提題助詞\footnote{提題助詞とは，主題を提示する助詞である\cite[page50]{Masuoka1992}．代表的な提題助詞は「は」である．}を持つとする．このとき格助詞の後ろに提題助詞が来る．それゆえ，格助詞の情報を見落としてしまう．「標準素性」では文節内の最も右の機能語しか素性として扱われないからである\footnote{例えば，係り元文節が「本-に-は」の場合，第~\ref{subsec:stfe}の語形の素性として「は」に関する素性が採用される．「に」に関する素性は使われない．}．こういった情報を見落とさないように，文節内の全ての格助詞を素性として扱う．「標準素性」で見落とされる重要な情報は他にもある．それは，係り先候補の文節の最も左の語の情報である．この語は係り元の文節の最も右の語と慣用表現のような強い相関関係を持つことも多い．これに加えて，係り先候補文節の直後の文節の表層形も素性として使う．これは，第~\ref{subsec:loc}節の素性とともに用いる．\subsection{並列句のための素性}並列構造を正しく認識することは，長い文を正しく解析する際に最も難しいことの一つである．KurohashiとNagaoは，二つの文節列の類似度を計算することによって並列句を認識する手法を提案している\cite{Kurohashi1994}．現在までのところ，機械学習を使うシステムの中で並列構造を認識するための素性はあまり研究されていない．我々は最初のステップとして，並列構造を認識するための基本的な二つの素性を試した．注目している文節が{\emキー文節}({\itdistinctivekeybunsetsu})\cite[page510]{Kurohashi1994}であるとき，この二つの素性は使われる．一つ目の素性は，係り元文節がキー文節であるときアクティブになるものである．もう一つの素性は，係り元文節がキー文節で，その係り元文節と係り先候補の文節の主辞表層形が一致していればアクティブになるものである．単純さを保つため，対象とする主辞品詞は名詞のみとした．
\section{実験と考察}
提案アルゴリズムを利用したパーザをC++で実装し，その時間計算量の振る舞いや解析精度を実験的に評価した．\subsection{コーパス}提案アルゴリズムを評価するために，京大コーパスVersion2\cite{Kurohashi1998}を使った．新聞記事の1月1日から1月8日分(7,958文)を訓練事例とし，1月9日分(1,246文)をテスト事例とした．1月10日分を開発用に用いた．これらの記事の使い方は\cite{Uchimoto1999,Sekine2000Backward,Kudo2002}と同じである．\subsection{SVMの設定}独自にC++で実装したSVMsのツールを用いた．カーネルとして，3次の多項式カーネルを用いた．特に記述がない限り誤分類のコストは1に設定した．\subsection{実験結果}\label{subsec:results}\begin{table}[b]\caption{テスト事例に対する精度}\label{tbl:acc}\begin{center}\begin{tabular}{lcc}\hline\hline&係り受け正解率(\%)&文正解率(\%)\\\hline標準素性&88.72&45.88\\全て&89.56&48.35\\前後文節素性(5.2~節)なし&88.91&46.33\\文節内追加素性(5.3~節)なし&89.19&47.05\\並列句素性(5.4~節)なし&89.41&47.86\\\hline\end{tabular}\end{center}\end{table}{\bf解析精度}\hspace{0.4em}テスト事例に対する我々のパーザの性能を表~\ref{tbl:acc}に示す．従来研究との比較のために，性能評価には京大コーパスで標準的に使われる尺度である係り受け正解率と文正解率の二つを用いる．係り受け正解率とは，正しく解析された係り受けの割合であり(他の多くの文献と同様，文末の一文節を除く)，文正解率とは，全ての係り関係が正しく解析された文の割合である．「標準素性」を用いた場合の精度は比較的よい．実際，この係り受け正解率は動的素性を用いないときのCascadedChunkingModel\cite{Kudo2002}とほぼ同じである．第~\ref{sec:models}節で述べた全ての素性を用いた場合，我々のパーザは89.56\%の係り受け正解率を得た．これは京大コーパスVersion2に対して公表されている精度の中で最もよいものである．\begin{figure}[t]\begin{center}\includegraphics[scale=1.2]{speed-j02.eps}\end{center}\caption{一文あたりの処理時間}\label{speed}\end{figure}{\bf時間計算量の漸近的な振る舞い}\hspace{0.4em}図~\ref{speed}に，我々のパーザのテスト事例に対する実行時間を示す．これはワークステーション(UltraSPARCII450MHz,1GBメモリ)を用いて計測した．図~\ref{speed}より実行時間の上限が文の長さに比例しているのが分かる．これは，第~\ref{subsec:time}節で行なった理論的な分析と一致している．この実験結果を見て，確かに従来研究よりも時間計算量の上限は低く抑えられているが，我々のパーザの実際の処理時間はそれほど速くないと思われるかもしれない．パーザのこの遅さの主たる原因は，SVMsにおけるカーネル評価での膨大な計算のせいである．我々の実験では，SVMの分類器は4万個以上のサポートベクタを持っている．それゆえ，係り関係を判定するたびに膨大な内積計算が必要となる．幸い，この問題に対する解決策は既にKudoとMatsumoto\shortcite{Kudo2003}によって与えられている．彼らは高次の多項式カーネルを線形カーネルに変換する手法を提案し，変換された線形カーネルでは，精度を保ったまま元の多項式カーネルよりもおよそ30から300倍高速だったと報告している．彼らの手法を我々のパーザに適用すれば，処理時間も十分高速化されるだろう．彼らの手法を用いればどのくらい我々のパーザの速度が改善されるか粗く見積もるために，線形カーネルを用い，同じテスト事例に対してパーザを走らせてみた．図~\ref{speed:lin}に，線形カーネルを用いたパーザの処理時間を示す．なお計測には多項式カーネルを用いた場合と同じマシンを使った．3次の多項式カーネルを使う場合に比べて相当に高速である．非常に長い文であっても0.02秒以内で解析が行なえている．加えて，このパーザのスピードばかりでなく精度も我々が期待した以上だった．係り受け正解率は87.36\%，文正解率は40.60\%に達した．これらの精度は，素性の組合せを人手で選択して追加しているパーザ\cite{Uchimoto1999}よりもわずかに良い．\begin{figure}[t]\begin{center}\includegraphics[scale=1.2]{speed-lin-j02.eps}\end{center}\caption{線形カーネルを使った場合の一文あたりの処理時間．誤分類のコストは0.0056．}\label{speed:lin}\end{figure}\subsection{関連研究との比較}\label{sec:relatedwork}我々のパーザと関連研究におけるパーザとを時間計算量と精度の点から比較する．比較のサマリを表~\ref{tbl:comp}に示す．我々のアルゴリズムとSVMsと組み合わせたものが時間計算量の点から優れた性質を持ち，加えてトップレベルの精度が得られている．\begin{table}[t]\caption{関連研究との性能の比較．KM02=KudoandMatsumoto2002,KM00=KudoandMatsumoto\hspace*{27pt}2000,USI99=Uchimotoetal.1999,andSeki00=Sekine2000.提案アルゴリズムをStack\hspace*{27pt}DependencyAnalysisと記述．}\label{tbl:comp}\begin{center}\begin{tabular}{l|l|c|c}\hline\hline&アルゴリズム/モデル&\multicolumn{1}{c|}{時間計算量}&係り受け正解率(\%)\\\hline本論文&StackDependencyAnalysis(SVMs)&$n$&89.56\\&StackDependencyAnalysis(linearSVMs)&$n$&87.36\\\hlineKM02&CascadedChunkingModel(SVMs)&$n^2$&89.29\\KM00&後方ビームサーチ(SVMs)&$n^2$&89.09\\USI99&後方ビームサーチ(ME)&$n^2$&87.14\\Seki00&決定的有限状態変換器&$n$&77.97\\\hline\end{tabular}\end{center}\end{table}文献\cite{Kudo2002}との比較は，第~\ref{comp:theory}の記述にゆずる．Uchimotoら\shortcite{Uchimoto1999}は最大エントロピー法と後方ビームサーチを用いている．文献\cite{Sekine2000Backward}によれば，解析時間は$n^{2}$に比例するとのことである．これに対し，我々のパーザは線形時間で文を解析し，精度もよい．工藤と松本\cite{Kudo2005}の「相対モデル」のパーザ\footnote{京大コーパスVersion2に対する精度が不明なため，表~\ref{tbl:comp}にはあげていない．}も，後方ビームサーチを用いているので，時間計算量という点ではUchimotoらのパーザと同様である．文献\cite{Kudo2005}では，「相対モデル」のパーザは，京大コーパスVersion3.0に対して，係り受け正解率91.37\%を得，CascadedChunkingModelは91.23\%を得たと報告されている．我々のパーザは，京大コーパスVersion2において，CascadedChunkingModelの精度を0.27ポイント上回っていることを考えると，我々のパーザと「相対モデル」パーザとの差も大きなものではないと判断できる\footnote{「相対モデル」がCascadedChunkingModelよりも，長距離の文節間の係り受けF値が上回っている\cite{Kudo2005}ことは注目に値する．我々の提案手法もCascadedChunkingModelと同様，直後に係りやすいという性質を利用しているため，「相対モデル」のほうが提案手法よりも長距離の文節間の係り受けF値がよい可能性が高い．}．また，我々と同様Sekine\shortcite{Sekine2000Japanese}も線形時間で処理が進む非常に高速なパーザを提案している．彼の手法は，後方から係り先を決定していく．係り元の文節の語形の情報と，係り先候補(5つまで)の主辞の情報から，係り先を一つに決める決定的有限状態変換器を用いている．係り元の語形や5つの係り先候補の主辞の情報を細かく区別すると，状態(state)の数が多くなりすぎ，大量のメモリを消費するため，係り元の語形の状態を40に，係り先の主辞の状態を18に限定している．品詞や活用形の情報のみ利用している．このため，精度が大きく犠牲になっている．
\section{おわりに}
我々は線形時間で処理を行なう日本語係り受け解析のアルゴリズムを提案した．京大コーパスVersion2に対して実験を行ない，時間計算量と解析精度を調べた．時間計算量の上限は$O(n)$であることが確認でき，解析精度も従来報告されているものを上回った．精度の差は従来研究で報告されているものと大きくないため，精度面からの優位性は結論できないが，本研究で(1)提案アルゴリズムが理論的にも実験的にも時間計算量の上限が$O(n)$で抑えられていることと，(2)時間計算量を抑え，左から右へ一度しかスキャンしないにも関わらずトップレベルの精度が得られることの二つを示せた意義は大きいと考える．後方の文節を直接考慮しない提案アルゴリズムに一定の限界があることは明らかであるが，係り先として考慮する文節の数を増やしても精度が向上するとは限らず，その解決は単純ではない．我々はスタッキングにより精度が向上しないか検討したいと考えている．また，並列構造の認識についてもよりよいモデルを提案したい．\bibliographystyle{jnlpbbl_1.1}\begin{thebibliography}{}\bibitem[\protect\BCAY{Abney}{Abney}{1991}]{Abney1991}Abney,S.~P.\BBOP1991\BBCP.\newblock\BBOQParsingbyChunks\BBCQ\\newblockInBerwick,R.~C.,Abney,S.~P.,\BBA\Tenny,C.\BEDS,{\BemPrinciple-BasedParsing:ComputationandPsycholinguistics},\mbox{\BPGS\257--278}.KluwerAcademicPublishers.\bibitem[\protect\BCAY{Collins}{Collins}{1996}]{Collins1996}Collins,M.\BBOP1996\BBCP.\newblock\BBOQANewStatisticalParserBasedonBigramLexicalDependencies\BBCQ\\newblockIn{\BemProc.ofACL-96},\mbox{\BPGS\184--191}.\bibitem[\protect\BCAY{Eisner}{Eisner}{1996}]{Eisner1996}Eisner,J.~M.\BBOP1996\BBCP.\newblock\BBOQThreeNewProbabilisticModelsforDependencyParsing:AnExploration\BBCQ\\newblockIn{\BemProc.ofCOLING-96},\mbox{\BPGS\340--345}.\bibitem[\protect\BCAY{Fujio\BBA\Matsumoto}{Fujio\BBA\Matsumoto}{1998}]{Fujio1998}Fujio,M.\BBACOMMA\\BBA\Matsumoto,Y.\BBOP1998\BBCP.\newblock\BBOQJapaneseDependencyStructureAnalysisbasedonLexicalizedStatistics\BBCQ\\newblockIn{\BemProc.ofEMNLP-1998},\mbox{\BPGS\88--96}.\bibitem[\protect\BCAY{Haruno,Shirai,\BBA\Ooyama}{Harunoet~al.}{1998}]{Haruno1998}Haruno,M.,Shirai,S.,\BBA\Ooyama,Y.\BBOP1998\BBCP.\newblock\BBOQUsingDecisionTreestoConstructaPracticalParser\BBCQ\\newblockIn{\BemProc.ofCOLING/ACL-98},\mbox{\BPGS\505--511}.\bibitem[\protect\BCAY{Kudo\BBA\Matsumoto}{Kudo\BBA\Matsumoto}{2000}]{Kudo2000Japanese}Kudo,T.\BBACOMMA\\BBA\Matsumoto,Y.\BBOP2000\BBCP.\newblock\BBOQJapaneseDependencyStructureAnalysisBasedonSupportVectorMachines\BBCQ\\newblockIn{\BemProc.ofEMNLP/VLC2000},\mbox{\BPGS\18--25}.\bibitem[\protect\BCAY{Kudo\BBA\Matsumoto}{Kudo\BBA\Matsumoto}{2002}]{Kudo2002}Kudo,T.\BBACOMMA\\BBA\Matsumoto,Y.\BBOP2002\BBCP.\newblock\BBOQJapaneseDependencyAnalysisusingCascadedChunking\BBCQ\\newblockIn{\BemProc.ofCoNLL-2002},\mbox{\BPGS\63--69}.\bibitem[\protect\BCAY{Kudo\BBA\Matsumoto}{Kudo\BBA\Matsumoto}{2003}]{Kudo2003}Kudo,T.\BBACOMMA\\BBA\Matsumoto,Y.\BBOP2003\BBCP.\newblock\BBOQFastMethodsforKernel-basedTextAnalysis\BBCQ\\newblockIn{\BemProc.ofACL-03},\mbox{\BPGS\24--31}.\bibitem[\protect\BCAY{工藤\JBA松本}{工藤\JBA松本}{2005}]{Kudo2005}工藤拓\JBA松本裕治\BBOP2005\BBCP.\newblock\JBOQ相対的な係りやすさを考慮した日本語係り受け解析モデル\JBCQ\\newblock\Jem{情報処理学会論文誌},{\Bbf46}(4),\mbox{\BPGS\1082--1092}.\bibitem[\protect\BCAY{Kurohashi\BBA\Nagao}{Kurohashi\BBA\Nagao}{1994}]{Kurohashi1994}Kurohashi,S.\BBACOMMA\\BBA\Nagao,M.\BBOP1994\BBCP.\newblock\BBOQASyntacticAnalysisMethodofLong{J}apaneseSentencesBasedontheDetectionofConjunctiveStructures\BBCQ\\newblock{\BemComputationalLinguistics},{\Bbf20}(4),\mbox{\BPGS\507--534}.\bibitem[\protect\BCAY{Kurohashi\BBA\Nagao}{Kurohashi\BBA\Nagao}{1998}]{Kurohashi1998}Kurohashi,S.\BBACOMMA\\BBA\Nagao,M.\BBOP1998\BBCP.\newblock\BBOQBuildinga{J}apaneseParsedCorpuswhileImprovingtheParsingSystem\BBCQ\\newblockIn{\BemProc.ofthe1stLREC},\mbox{\BPGS\719--724}.\bibitem[\protect\BCAY{Lafferty,Sleator,\BBA\Temperley}{Laffertyet~al.}{1992}]{Lafferty1992}Lafferty,J.,Sleator,D.,\BBA\Temperley,D.\BBOP1992\BBCP.\newblock\BBOQGrammaticalTrigrams:AProbabilisticModelofLinkGrammar\BBCQ\\newblockIn{\BemProc.oftheAAAIFallSymp.onProbabilisticApproachestoNaturalLanguage},\mbox{\BPGS\89--97}.\bibitem[\protect\BCAY{Maruyama\BBA\Ogino}{Maruyama\BBA\Ogino}{1992}]{Maruyama1992}Maruyama,H.\BBACOMMA\\BBA\Ogino,S.\BBOP1992\BBCP.\newblock\BBOQAStatisticalPropertyof{J}apanesePhrase-to-PhraseModifications\BBCQ\\newblock{\BemMathematicalLinguistics},{\Bbf18}(7),\mbox{\BPGS\348--352}.\bibitem[\protect\BCAY{益岡隆志\JBA田窪行則}{益岡隆志\JBA田窪行則}{1992}]{Masuoka1992}益岡隆志\JBA田窪行則\BBOP1992\BBCP.\newblock\Jem{基礎日本語文法---改訂版---}.\newblockくろしお出版.\bibitem[\protect\BCAY{長尾真\JBA佐藤理史\JBA黒橋禎夫\JBA角田達彦}{長尾真\Jetal}{1996}]{Nagao1996}長尾真\JBA佐藤理史\JBA黒橋禎夫\JBA角田達彦\BBOP1996\BBCP.\newblock\Jem{自然言語処理}.\newblock岩波書店.\bibitem[\protect\BCAY{Nivre}{Nivre}{2003}]{Nivre2003}Nivre,J.\BBOP2003\BBCP.\newblock\BBOQAnEfficientAlgorithmforProjectiveDependencyParsing\BBCQ\\newblockIn{\BemProc.ofIWPT-03},\mbox{\BPGS\149--160}.\bibitem[\protect\BCAY{Ratnaparkhi}{Ratnaparkhi}{1997}]{Ratnaparkhi1997}Ratnaparkhi,A.\BBOP1997\BBCP.\newblock\BBOQALinearObservedTimeStatisticalParserBasedonMaximumEntropyModels\BBCQ\\newblockIn{\BemProc.ofEMNLP-1997},\mbox{\BPGS\1--10}.\bibitem[\protect\BCAY{Sekine}{Sekine}{2000}]{Sekine2000Japanese}Sekine,S.\BBOP2000\BBCP.\newblock\BBOQJapaneseDependencyAnalysisusingaDeterministicFiniteStateTransducer\BBCQ\\newblockIn{\BemProc.ofCOLING-00},\mbox{\BPGS\761--767}.\bibitem[\protect\BCAY{Sekine,Uchimoto,\BBA\Isahara}{Sekineet~al.}{2000}]{Sekine2000Backward}Sekine,S.,Uchimoto,K.,\BBA\Isahara,H.\BBOP2000\BBCP.\newblock\BBOQBackwardBeamSearchAlgorithmforDependencyAnalysisof{J}apanese\BBCQ\\newblockIn{\BemProc.ofCOLING-00},\mbox{\BPGS\754--760}.\bibitem[\protect\BCAY{Uchimoto,Sekine,\BBA\Isahara}{Uchimotoet~al.}{1999}]{Uchimoto1999}Uchimoto,K.,Sekine,S.,\BBA\Isahara,H.\BBOP1999\BBCP.\newblock\BBOQJapaneseDependencyStructureAnalysisBasedonMaximumEntropyModels\BBCQ\\newblockIn{\BemProc.ofEACL-99},\mbox{\BPGS\196--203}.\bibitem[\protect\BCAY{Vapnik}{Vapnik}{1995}]{Vapnik1995}Vapnik,V.~N.\BBOP1995\BBCP.\newblock{\BemTheNatureofStatisticalLearningTheory}.\newblockSpringer-Verlag.\bibitem[\protect\BCAY{Wolpert}{Wolpert}{1992}]{Wolpert1992}Wolpert,D.~H.\BBOP1992\BBCP.\newblock\BBOQStackedGeneralization\BBCQ\\newblock{\BemNeuralNetworks},{\Bbf5},\mbox{\BPGS\241--259}.\bibitem[\protect\BCAY{Yoon,Choi,\BBA\Song}{Yoonet~al.}{1999}]{Yoon1999}Yoon,J.,Choi,K.,\BBA\Song,M.\BBOP1999\BBCP.\newblock\BBOQThreeTypesofChunkingin{K}oreanandDependencyAnalysisBasedonLexicalAssociation\BBCQ\\newblockIn{\BemProc.ofthe18thInt.Conf.onComputerProcessingofOrientalLanguages},\mbox{\BPGS\59--65}.\end{thebibliography}\begin{biography}\bioauthor{颯々野学}{1991年京都大学工学部電気工学第二学科卒業．同年より富士通研究所研究員．1999年9月より1年間，米国ジョンズ・ホプキンス大学客員研究員．2006年3月よりヤフー株式会社勤務．自然言語処理の研究に従事．2006年10月より京都大学大学院情報学研究科知能情報学専攻博士後期課程在学．言語処理学会，情報処理学会，ACL各会員．}\end{biography}\biodate\end{document}