\section{はじめに}
係り受け解析は日本語文解析の基本的な方法として認識されている．日本語係り受けには，主に以下の特徴があるとされている\footnote{もちろん，例外は存在するが\cite{sshirai:jnlp98}，その頻度は現在の解析精度を下回り，現状では無視して構わないと考える．つまり，これらの仮定の基に解析精度を向上させた後に，そのような例外に対し対処する手法を考えればよいのではないかと思う．また，(4)の特徴はあまり議論されてはいないが，我々が行なった人間に対する実験で90\%以上の割合で成立する事が確認された．}．我々はこれらの特徴を仮定として採用し，解析手法を作成した．\begin{itemize}\item[(1)]係り受けは前方から後方に向いている．(後方修飾)\item[(2)]係り受け関係は交差しない．(非交差条件)\item[(3)]係り要素は受け要素を一つだけ持つ．\item[(4)]ほとんどの場合，係り先決定には前方の文脈を必要としない．\end{itemize}このような特徴を仮定した場合，解析は文末から文頭に向けて行なえば効率良く解析ができると考えられる．以下に述べる二つの利点が考えられるためである．今，文節長Nの文の解析においてM+1番目の文節まで解析が終了していると仮定し，現在M番目の文節の係り先を決定しようとしているとする(M$<$N)．まず，一つ目の利点は，M番目の文節の係り先は，すでに解析を終了しているM+1番目からN番目の文節のいずれかであるという事である．したがって，未解決な解析状態を積み上げておく必要はないため，チャートパーザーのように活性弧を不必要に多く作る必要はないし，一般的なLRパーザー等で利用されているようなスタックにそれまでの解析結果を積んで後の解析に依存させるという事をしなくて済む．別の利点は，M番目の文節の解析を開始する時点には，M+1番目からN番目の係り受け解析はなんらかの形式において終了しており，可能な係り先は，非交差条件を満足する文節だけに絞られるという事である．実験では，この絞り込みは50\%以下になり，非常に有効である．また，この論文で述べる統計的手法と文末からの解析手法を組み合せると，ビームサーチが非常に簡単に実現できる．ビームサーチは解析候補の数を絞りながら解析を進めていく手法である．ビーム幅は自由に設定でき，サーチのための格納領域はビーム幅と文長の積に比例したサイズしか必要としない．これまでにも，文末からの解析手法はルールベースの係り受け解析において利用されてきた．例えば\cite{fujita:ai88}．しかし，ルールベースの解析では，規則を人間が作成するため，網羅性，一貫性，ドメイン移植性という点で難がある．また，ルールベースでは優先度を組み入れる事が難しく，ヒューリスティックによる決定的な手法として利用せざるを得なかった．しかし，本論文で述べるように，文末から解析を行なうという手法と統計的解析を組み合せる事により解析速度を落す事なく，高い精度の係り受け解析を実現する事ができた．統計的な構文解析手法については，英語，日本語等言語によらず，色々な提案が80年代から数多くあり\cite{fujisaki:coling84}\cite{magerman:acl95}\cite{sekine:iwpt95}\cite{collins:acl97}\cite{ratnaparkhi:emnlp97}\cite{shirai:emnlp98}\cite{fujio:emnlp98}\cite{sekine:nlprs97}\cite{haruno:nlpsympo97}\cite{ehara:nlp98}，現在，英語についてはRatnaparkhiのME(最大エントロピー法)を利用した解析が，精度，速度の両方の点で最も進んでいる手法の一つと考えられている．我々も統計的手法のツールとしてMEを利用する．次の節でMEの簡単な説明を行ない，その後，解析アルゴリズム，実験結果の説明を行なう．
\section{最大エントロピー法の利用}
最大エントロピー法(ME)は，トレーニングデータ中の素性の頻度等の情報から特徴的な素性を学習し，その特徴を生かした確率的なモデルを作成する方法である．素性とは，我々の場合，二つの文節間の係り受けの確率を計算するための情報であり，そこで使用される基本素性には表~\ref{素性}に挙げた種類の素性を利用した．括弧内の数字は素性値の数である．\begin{table}[tbh]\begin{center}\caption{素性}\label{素性}\begin{tabular}{|l|l|}\hline前文節/後文節&主辞見出し(2204)，品詞(34)，活用情報(90)，\\&語形情報(218)，助詞の細い情報(135)，\\&句読点，括弧の情報(31)\\\hline文節間情報&距離(3)，読点，括弧の有無(6)，「は」の有無(2)，\\&前文節と同じ素性を持つ物の有無等(127)\\&後文節と同じ素性を持つ物の有無等(220)\\\hline\end{tabular}\end{center}\end{table}また，これらの素性を組合せた組合せの素性も利用した．その数は約4万個である．素性の詳細，および素性の選択による比較実験については\cite{uchimoto:nlken98}を参照されたい．そして，テストの際には，トレーニングデータを使用して学習されたモデルを基にテスト文中に与えられた二つの文節の素性からその二つの文節の係り受けの確率を計算する．これまでの多くの先行研究と同様にすべての係り受けは独立であると仮定し，一文全体の係り受け確率を，その文中にあるそれぞれの係り受けの確率の積で表す．そして，一文全体の確率が最大となるような係り受け関係が正しい係り受け関係であると仮定する．
\section{解析アルゴリズム}
この章では，解析アルゴリズムを紹介する．まず，例を利用して，概略を説明し，その後フォーマルな形で解析アルゴリズムを示す．特徴は文末から文頭に向けての係り受け解析と確率を利用したビームサーチにある．例には以下の入力文を用いる．文節解析まで終っていると仮定しており，文節の区切は''$|$''で示される．説明図において，文節の係り先は，それぞれの文節の下にある番号で示される．\begin{verbatim}-----------------------------------------------------------<初期状態>ID123456彼は，|再び|パイを|作り，|彼女に|贈った．-----------------------------------------------------------\end{verbatim}\begin{flushleft}\underline{解析手順}\end{flushleft}\begin{enumerate}\item[(1)]{\bf文末から二つ目の文節}\\文末の文節は係り先はなく，文末から二つ目の文節は必ず文末の文節にかかる．この結果は以下のようになる．\end{enumerate}\begin{verbatim}-----------------------------------------------------------<文末から二つ目まで>ID123456彼は，|再び|パイを|作り，|彼女に|贈った．候補6------------------------------------------------------------\end{verbatim}\begin{enumerate}\item[(2)]{\bf文末から三つ目の文節}\\この文節(「作り，」)は，係り先として二つの文節が考えられる．一つは「彼女に」であり，もう一つは「贈った」である．MEを利用して計算された確率を付与した二つの解析候補を作成する．(それぞれの確率は0.1，0.9としてあり，各候補の最後には，総合の確率(各係り受けの確率の積)を括弧の中に示す．)\end{enumerate}\begin{verbatim}-----------------------------------------------------------<文末から三つ目まで>ID123456彼は，|再び|パイを|作り，|彼女に|贈った．候補166-(0.9)候補256-(0.1)-----------------------------------------------------------\end{verbatim}\begin{enumerate}\item[(3)]{\bf文末から四つ目の文節}\\それぞれの候補に対して，「パイを」の文節の係り先を求める．候補1に対しては，非交差の条件から「パイを」の文節は「彼女に」の文節に係る事はありえない．したがって「パイを」が「作り，」と「贈った」のそれぞれに係る候補を作成する．候補2についても同様にする．\end{enumerate}\begin{verbatim}-----------------------------------------------------------<文末から四つ目まで>ID123456彼は，|再び|パイを|作り，|彼女に|贈った．候補1466-(0.54)候補2666-(0.36)候補3456-(0.05)候補4656-(0.04)候補5556-(0.01)-----------------------------------------------------------\end{verbatim}\begin{enumerate}\item[]このように計算していくと，候補の数は文頭に行くにしたがって増えていく．しかし，解析途中の候補の数に上限を設けて，ビームサーチを行なえば，解析候補数の爆発は防げる．また，上記の例から直感的に分るように，その場合でも解析精度の悪化も少なく抑えられる．実際の実験で得られたビーム幅と精度のデータは次章で紹介する．例えば，この例でビーム幅を3とすると，候補4と候補5はこの段階で捨てられ，以降の解析には使用されない．\item[(4)]{\bfそれ以降}\\上記で示したような解析を文頭まで繰り返す．例えば，ビーム幅を3とした場合の解析結果は以下のようになる．\end{enumerate}\begin{verbatim}-----------------------------------------------------------<文頭まで>ID123456彼は，|再び|パイを|作り，|彼女に|贈った．候補164466-(0.11)候補244666-(0.09)候補364656-(0.05)-----------------------------------------------------------\end{verbatim}以下にフォーマルな解析アルゴリズムを示す．\begin{verbatim}----------------------------------------------------------------Length:入力文節長Input[Length]:入力文N:ビーム幅Cand[Length][N]:解析結果候補(各文節の係り先文節IDの配列で表される)例えばCand[1][1]={6,4,4,6,6,-}．この方法では，必要なメモリのサイズは文長とビーム幅の積以上になるが，簡単な変換で，上記のサイズに納める事ができる．add(l,cand):cand(解析結果候補)の確率がl番目の文節の解析結果候補の内のN番目のものより良い場合は，candをCand[l]の解析候補に加える．この際，N+1番目の候補になった物は捨てられる．get(l):Cand[l]の候補群から候補を取り出す．候補がなければNULLを返す．ins(i,cand):iをcandの先頭に追加する．procedure係り受け解析beginadd(Length-1,{Length,-});for(i=Length-2;i>=1;i--)beginwhile((cand=get(i))!=NULL)beginfor(j=i+1;j<=Length;j++)beginif(iからjへの係り受けがcandにおいて有効)add(i,ins(j,cand));endifendendendend----------------------------------------------------------------\end{verbatim}このアルゴリズムの解析時間オーダーは，文節数の2乗であり，ビーム幅をNとすると，ビーム幅に対しNlog(N)であると推測される．
\section{実験結果}
この章では，係り受け解析の実験を色々な角度から分析する．実験に用いたコーパスは，京大コーパス(Version2)\cite{kurohashi:nlp97}の一般文の部分で，基本的にトレーニングには1月1日と1月3日から8日までの7日分(7960文)，試験には1月9日の1日分(\mbox{1246}文)を用いた．試験は頻繁に行なうと，高い成績を追及する結果その試験のデータに自然とチューニングされてしまう危険性があるので，頻繁に行なわないようにした．\subsection{実験結果}まず最初に，我々の結果を示し，他の手法の結果との比較を行なう．それ以降の節では，我々の実験内で得られた興味深いデータを紹介する．まずは，我々の解析結果を表~\ref{Result}に示す．京大コーパス1月9日の\mbox{1246}文に対して，形態素解析，文節区切認定まで終った状態から文節間係り受けの解析を決定的に(ビーム幅=1)行なった結果である．\begin{table}[tbh]\begin{center}\caption{解析結果}\label{Result}\begin{tabular}{|l|l|}\hline係り受け正解率(文末から二つ目の文節も含める)&87.14\%(9814/11263)\\係り受け正解率(文末から二つ目の文節を除く)&85.54\%(8575/10024)\\文正解率(文全体の解析が正しい割合)&40.60\%(503/1239)\\平均解析時間(一文当り)&0.03秒\\\hline\end{tabular}\end{center}\end{table}また，文節数と係り受け正解率の関係を図~\ref{LengthAndAccuracy}に示す(文節数28以上は，それぞれデータ数が1なので図に載せていない．)．図から分るように，文節数の増加に伴なう精度の劣化は比較的に小さいと考えられる．日本語の係り受けは多くの場合，係り元と係り先以外の大域的な情報を利用せず，局所的な情報のみで決められる事が多いので，文が長くなっても係り受け正解率の劣化があまり見られないのは納得できる．\begin{figure}[htbp]\beginpicture\setcoordinatesystemunits<6pt,180pt>\setplotareaxfrom0to30,yfrom0to1\axisbottomlabel{文節数}ticksshortquantity7numberedat0102030//\axisleftlabel{係り受け正解率}ticksshortquantity11numberedat00.20.40.60.81.0//\multiput{*}at30.937540.944450.908960.894570.901480.897790.8812100.8880110.8639120.8742130.8605140.8778150.8777160.8474170.8415180.8529190.8360200.8368210.8346220.8214230.8591240.8385250.7986260.8640270.8205280.9185/\setlinear\plot30.937540.944450.908960.894570.901480.897790.8812100.8880110.8639120.8742130.8605140.8778150.8777160.8474170.8415180.8529190.8360200.8368210.8346220.8214230.8591240.8385250.7986260.8640270.8205280.9185/\put{0.8714}at-100.8714\multiput{-}at-70.8714*3710/\endpicture\caption{文節数と係り受け正解率}\label{LengthAndAccuracy}\end{figure}\subsection{他の手法との比較}この節では他の手法との比較を行なう．他の手法においては同じコーパスを使って評価した物がないため，その精度は参考として載せる．同じプラットフォームで同じ評価方法を用いた比較が望まれる．\begin{flushleft}\underline{白井およびKNPとの比較}\end{flushleft}白井\cite{shirai:jnlp98:1}は構文規則に基いた確率一般化LR法を提案している．構文および語彙的な統計情報を用い，その学習にはMEを利用している．実験では京大コーパスの文節数7〜9の文からランダムに選んだ500文の内，KNPによる文節区切がコーパスと一致した388文を対象に，白井の解析結果とKNPの解析結果の正解率を比較している．(KNPについては\cite{kurohashi:snlr94}を参照の事．)そこで，我々の試験コーパスの中で文節数が7〜9の文，279文における結果を用いて比較した(表~\ref{CompShiraiKNP})．すべて，文末から二つ目の文節は評価から除いており，白井の方法も文節切りができた状態からの解析である．\begin{table}[tbh]\caption{白井，KNPとの比較}\label{CompShiraiKNP}\begin{center}\begin{tabular}{|l|c|}\hlineシステム&係り受け正解率\\\hline白井&84.53\%\\KNP&90.76\%\\本手法&87.41\%\\\hline\end{tabular}\end{center}\end{table}対象の文が完全に一致しておらず，対象の文の選択の方法も異なるので，参考にしかできないが，この文長の文に対しては，白井の手法に比較して3\%程度良い結果を，KNPと比較した場合には3\%程度悪い結果を得た．白井の実験では，EDRコーパス，RWCコーパスを利用し，トレーニングデータとしては我々よりも大きなデータを利用している．また，白井はランダムに選んだ500文については84.34\%という解析結果を示している．KNPは，この評価で使用したテストコーパスに基づいて改良されており，KNPの評価結果は，トレーニングデータに対するものと言う事ができる．\begin{flushleft}\underline{藤尾，春野との比較}\end{flushleft}藤尾\cite{fujio:emnlp98}は文節間の属性の共起頻度による統計的解析手法を提案した．また，春野\cite{haruno:nlpsympo97}は決定木およびブースティングを利用した係り受け解析を行なっている．これらの評価はＥＤＲコーパスを利用し，試験対象データの選択手法も我々とは異なっているため，直接的な評価は難しい．彼等の場合は，形態素解析から解析を行なっているが，評価には文節区切が正しい物のみを利用したり，正解を自分の文節区切の結果に翻訳してから評価を行なっている．しかし，共に85\%程度の正解率が出ており，我々の手法も同様な位置を占めている．これらの手法は，ほぼ利用している知識の種類が同様であり，計算の手法に違いがあるものの，同様な結果を得ていると考えていいと思う．手法の違いによる詳しい比較を行なうためにも，同じプラットフォームでの実験とそれを元にした考察が望まれる．\begin{flushleft}\underline{江原との比較}\end{flushleft}江原の手法\cite{ehara:nlp98}は，我々の手法と同様にMEを用いており，そういった意味で比較するのは意味があるが，対象文は，NHKのニュース原稿であり，平均文節数も17.8と我々の対象にしている京大コーパスとは全く異なっている(平均文節数は10.0)．ただし，図~\ref{LengthAndAccuracy}に示したように，我々の結果は文節数と係り受け正解率の関係はあまり変化が見られず，長いからといって必ずしも解析が困難だとは限らない．これらの理由により，単純な比較は意味がないが，正解率において，我々の手法が約10\%上回っているのはなんらかの要因が存在すると考えられる．(江原の手法では正解率は76.4\%と報告されている．)特に江原の方法とは素性の数に大きな差があるようである．江原が用いた一次的な素性値の数は200個程度であり，我々の一時的な素性値の数の約5000個とは大きく異なっている．また，我々は組合せの素性も4万個程度利用している．この点深く掘り下げて検討する事に意味があると考える．また，MEに利用する素性の選択に関しては，江原の他にも白井\cite{shirai:jnlp98:2}Berger\cite{berger:emnlp98}等が興味深い提案をしている．\subsection{ビーム幅と精度}次に，我々の実験の中での比較結果を報告する．まずは，解析時に用いたビーム幅と精度の関係である．解析時のビーム幅が広ければ広い程，全体として確率の高い解析が得られる可能性が高くなるので，ビーム幅は高く設定した方が望ましいと考えられる．しかし，結果はその直観とは異なっていた．表~\ref{BeamAndAccuracy}にビーム幅を1から20に変化させた時の係り受け正解率と文正解率を示す．\begin{table}[tbh]\caption{ビーム幅と係り受け正解率，文正解率との関係}\label{BeamAndAccuracy}\begin{center}\begin{tabular}{|c||c|c|}\hlineビーム幅&係り受け正解率&文正解率\\\hline1&87.14&40.60\\2&87.16&40.76\\3&87.20&40.76\\5&87.14&40.60\\10&87.20&40.60\\15&86.21&40.60\\20&86.21&40.60\\\hline\end{tabular}\end{center}\end{table}全体的に変化は小さいが，係り受け正解率はビーム幅が3と10の時に，文正解率はビーム幅が2と3の時に最大になっている．これは，全体の確率が最大の物が正解ではなく，各段階ごとに正解を絞っていった方が正解になるという場合がある事を示している．これは「はじめに」で書いた，日本語係り受けの特徴(4)にも関係していて面白い．この結果によると，文末から文頭に係り受け解析をする際に，最良の結果のみを得たい場合には，決定的に行なってもかなり精度の良いものが得られるという事が言える．実際に，ビーム幅を1とした時に得られた答が，ビーム幅20とした時の解析結果のどこに現われるかを調査した結果を表~\ref{OneOnTwenty}に示す．\begin{table}[tbh]\caption{決定的解析結果の位置}\label{OneOnTwenty}\begin{center}\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}\hline位置&1&2&3&4&5&6&7&8&9&10\\\hline頻度&1175&20&11&8&4&2&1&2&0&3\\(\%)&(95.3)&(1.6)&(0.9)&(0.6)&(0.3)&(0.2)&(0.1)&(0.2)&&(0.2)\\\hline\hline位置&11&12&13&14&15&16&17&18&19&20以上\\\hline頻度&1&0&1&0&1&0&1&1&0&8\\(\%)&(0.1)&&(0.1)&&(0.1)&&(0.1)&(0.1)&&(0.6)\\\hline\end{tabular}\end{center}\end{table}実際に全体の95\%の場合，ビーム幅1の解析結果がビーム幅20の解析において最大の確率を持つ結果と同等であった．また，ビーム幅が1の解析において文全体が正解であった503文の中では，N=20での結果において1位の場所に同じ解析結果があったものが498文(99.0\%)と非常に高い率であった(以下2位の位置が3文，3位と5位の位置がそれぞれ1文づつあった．)．これらの文においては，最大の確率を持つ解析は，文末から解析していった場合に，各文節ごとの段階においてつねに最良の結果であったという事を意味している．これは，「はじめに」で書いた特徴(4)とも関係がある．「はじめに」の脚注に書いた人間に対する実験は文節に対する割合であるので，上記の文に対しての数字は，人間の実験で得られたよりもかなり高い割合で，前方の文脈の不必要さを実証したという事になる．\subsection{N--Best文正解率}文正解率はビーム幅が1の実験では40.60\%であったが，最終的に得られる解析の数を広くすればする程，正解率が向上する事が考えられる．図~\ref{NBestAccuracy}にビーム幅を20として解析を行なった場合のN--best文正解率を示す．N--best文正解率とは，上位N個の解析結果を見た場合に，文中のすべての文節係り受けの解析が正しい解析結果がその中にある割合の事を言う．\begin{figure}[htbp]\beginpicture\setcoordinatesystemunits<10pt,4pt>\setplotareaxfrom0to20,yfrom30to80\axisbottomlabel{N}ticksshortquantity21numberedat05101520//\axisleftlabel{文正解率}ticksshortquantity6numberedat304050607080//\multiput{*}at140.60253.19358.35462.71565.54667.96769.65870.70971.271072.481173.771275.061375.541476.431576.671677.241777.891878.291978.292078.53/\setlinear\plot140.60253.19358.35462.71565.54667.96769.65870.70971.271072.481173.771275.061375.541476.431576.671677.241777.891878.291978.292078.53/\put{40.60\%}[lb]at240.60\put{78.53\%}[lb]at1973\endpicture\caption{N--best文正解率}\label{NBestAccuracy}\end{figure}N=20，つまり，ビーム幅と同様の最終結果を見た場合に，文全体の係り受けが正解である解析結果が上位20個の解析結果に含まれる割合は78.5\%であるという事である．この中から正解を捜し出せる理想的なシステムを開発できた場合には，文正解率が78.5\%という非常に優れた解析システムができる可能性があるという事である．この結果から二つの考察ができる．まず，一点はN=1の文正解率は約40\%であるのに対して，N=2で向上した割合，つまり，2番目の解析結果が正解であった割合は10\%程度と非常に低くなっている．また，この40\%という数字は，N=20の場合の78.5\%という数字の半分以上であり，半分以上の場合においてN=1の所に正解が存在したという事を意味する．これは，我々の確率の計算手法が，まだ改善の余地はあるものの，かなり正確であるという事を示している．もう一点は，文正解率が80\%あたりで飽和しており，80\%程度以上の向上はNを多少大きくしても望めなさそうであるという事である(もちろん，Nをすべての組み合わせの数にすれば100\%にはなるが現実的に意味はない．)．これは，我々が何か大きな要因を見過ごしている可能性がある．特に，並列構造についての解析能力が低いようである．この点を改良し，再度検討していきたいと思う．\subsection{解析速度}前章にあるアルゴリズムを分析すると，解析時間は文節長に対して2乗になっていると推測できる．実際に，ビーム幅1の時の文節長と解析速度の関係を調べた(図~\ref{Kaisekisokudo})．実験はSunのUltra10，周波数(300MHz)を利用した．係り受け解析のプロセスの大きさは8M程度であった．\begin{figure}[htbp]\beginpicture\setcoordinatesystemunits<4pt,360pt>\setplotareaxfrom0to50,yfrom0to0.5\axisbottomlabel{文長}ticksshortquantity6numberedat01020304050//\axisleftlabel{解析時間(秒)}ticksshortquantity11numberedat00.10.20.30.40.5//\multiput{*}at170.06750.008120.048150.06190.029120.045100.02660.01450.00880.011190.05560.014100.039100.04070.01790.025140.035130.03350.010110.03970.016190.05780.01990.02260.014100.022160.03810.00040.007230.12360.012150.04340.006130.03160.01660.015100.018100.01710.00160.01230.00410.00110.00140.005140.04550.01120.00240.00550.01030.00360.01050.00860.00930.00350.01080.02620.00290.031140.058160.087140.033150.041110.035100.03770.018100.03090.020170.109100.030100.03350.01460.011140.041130.02540.00870.02090.02270.01920.00310.00140.00820.00280.01720.002120.04160.01410.00190.01650.00740.01130.00530.00470.022110.03440.008160.05040.00560.01780.01440.00560.00870.01540.00620.00290.03120.00330.00450.010100.02590.027130.03650.00860.01370.012170.039110.042100.02310.00190.02060.01690.030160.06380.02070.01320.002120.02640.00950.011160.04050.008130.05580.01970.01510.00160.00860.01660.01380.01980.01590.025160.09970.02020.003110.041140.05980.026130.051170.063270.087130.031110.03080.020140.050210.191210.067120.04580.01680.01950.008110.03050.008100.035140.083200.11150.010130.037100.051100.02250.01160.01650.01240.00740.006190.07660.01060.011110.025110.026110.032130.03450.00880.017100.026110.02840.00650.013130.04260.013130.039100.02480.018100.021110.027230.09280.018140.058100.03840.00640.00970.01050.01090.01870.015100.03540.008150.06440.006150.03450.01550.01020.003120.02960.01590.02310.00150.007180.04980.01670.013120.065120.032140.04670.022110.04380.02050.009140.02560.01270.01590.02730.00430.005100.03840.005120.03990.01950.006110.02830.00790.023120.044140.04730.00380.025110.02880.018120.05370.01450.00980.01890.017120.033140.03790.03870.01470.01360.01680.026100.04270.018100.022150.07130.00550.012190.060100.036220.111230.06430.00440.006180.042210.10560.01270.01480.016190.075110.02230.00490.022130.03780.01350.01040.00690.017140.038130.039110.016130.03540.00540.00590.02390.02340.01090.03560.02160.01430.00540.006100.02040.00850.00850.00730.00550.01140.00520.00430.00430.00360.01260.013100.02270.01620.00380.01710.00160.01090.03290.023130.03220.00360.01460.012110.03380.02480.01950.01320.00390.026100.02790.03380.01680.018150.04640.008220.08250.008150.05060.01590.02560.014110.03060.020140.04680.022150.045140.039140.034250.082140.038150.042100.031140.049110.028120.046150.057120.02990.020150.05090.038100.02780.02720.00350.01290.01930.005100.04170.021110.034120.044190.090210.078140.059190.119130.04330.003170.03670.017120.02670.01660.01330.003180.07560.01080.020110.048100.06080.02610.00190.04530.00510.00210.001180.059100.033120.04590.01940.00890.03090.024130.04470.01940.008160.05430.003100.06290.01850.009150.03890.02850.01260.00990.02110.00140.00720.00210.00150.009240.10320.00320.00230.00450.00710.00160.01420.003100.02740.00880.018130.02780.023180.082100.02490.02910.00020.00150.00940.00640.00880.01780.01240.00780.023140.04260.00940.007100.023100.037130.031110.03530.003120.02950.011150.09150.007120.03090.01850.011110.031250.104270.11860.01130.006130.04450.01280.017300.126100.021160.05940.007110.043260.12570.01490.02170.01970.015280.133200.078120.040100.031220.06660.015170.07460.02570.020200.079130.03910.000100.020120.05280.018120.02610.001130.03080.017120.039120.04190.01790.02050.008160.04220.00240.010110.03040.00810.00160.009140.07280.02350.01170.01990.01830.00450.008130.02680.01940.00540.00590.02040.00880.01690.01850.00550.009150.05680.014100.02280.01340.008150.03540.00760.011180.05480.020100.04090.019130.03390.01990.019140.05240.01220.003100.02590.020170.05270.02450.010120.022110.034160.05760.01250.01190.032120.034120.039140.03770.01830.00740.00740.00760.013120.02750.00970.01690.024190.05330.00470.014150.07780.02130.00560.012120.02650.011160.041120.03960.01020.00270.01590.020130.05340.01090.02440.005180.04680.014100.02420.00390.02280.02180.03230.00420.003140.03850.01170.021140.06060.01270.013110.032120.03260.018130.031180.05590.022130.04980.018110.03250.00880.01930.00490.018140.03950.00740.00960.010100.02710.00120.00260.00910.00240.00660.014140.05370.014140.03680.02030.00580.01970.01890.020130.02810.001150.026140.055110.035240.142180.08490.021170.055170.09690.026100.029150.03530.006140.03590.02280.02160.00980.02070.02270.01940.00760.01780.01670.01760.01390.01660.01440.008160.05230.004120.02470.01410.00130.005100.031110.02540.00990.02040.00980.02340.00650.01280.020130.03390.02420.00340.00640.00890.03530.00360.01170.01370.01340.009150.043110.038120.03150.008120.03450.00980.02310.00120.00340.010180.10290.01990.01740.00930.00490.01790.03430.00590.02330.004150.04840.008270.139130.029140.05350.00970.017100.02290.01790.03180.028130.047160.046100.026140.04660.01260.012150.080120.029120.03580.01930.004170.060230.143230.096110.029100.040140.04280.014240.09790.03290.031220.066150.043100.023150.05180.021150.06190.029210.088110.02230.006110.026140.038180.039100.028200.102140.04580.02950.01090.055140.064210.124100.04680.018110.051140.097120.05930.005160.05290.02840.007160.045200.06690.032180.04720.00260.01070.01710.00120.00240.00860.00820.00620.00340.006110.02830.003150.05740.00650.013160.07730.00550.01360.01310.00150.012130.030200.06650.01280.027110.03540.01150.01360.013210.09280.035100.02170.02470.01470.01360.013140.04090.02670.021120.023140.03910.00130.003150.03450.01170.02660.01240.00760.01850.01030.00640.00450.01250.008100.02890.02560.01380.01860.01380.01990.02760.00920.00310.00190.02670.02430.00790.02180.023130.05040.00720.00260.01260.01130.00480.020100.02340.00690.02570.01380.01690.014110.02840.008130.04170.015210.06550.01260.010190.065200.062110.02750.009120.03990.018140.03190.02550.014250.087150.080160.059180.070120.041160.047150.044220.104130.040100.024160.05380.02080.019120.031100.029180.063200.078110.02890.02690.022160.06210.00040.00760.011170.04540.00740.00630.006170.03750.00870.01680.01390.02690.02620.00170.018110.02640.00720.00280.02650.010250.06970.01790.023100.02120.00410.00130.00410.00190.01960.012180.06980.02340.006140.06270.02080.040170.061130.02660.015130.050120.03290.03110.00190.030200.06350.009170.041110.02960.013110.030150.08690.022110.03370.013140.035140.039100.026110.01770.01290.03340.006200.065110.033170.05110.00040.009170.04790.020100.041150.03660.01450.01130.00660.01720.00430.00410.00140.01030.00540.00620.00390.02490.020160.03720.00380.02210.00150.00820.00230.003100.02640.006140.05320.002400.28790.01600.00080.017150.061100.042110.031130.06440.008170.074100.03090.02670.01460.01990.030130.034240.10140.00620.00340.01070.02270.01400.00080.01940.00640.00960.01780.01660.01350.010100.032260.07240.004110.02930.00340.00910.00160.01460.01780.01820.00390.02090.02150.01540.00670.01640.00840.00840.006120.046110.02660.015250.11460.01510.001180.094120.059110.041130.03860.014270.113140.076140.04250.00880.02490.026210.091130.03890.023170.065150.046170.090140.03960.008100.024130.04450.010200.09490.02790.02290.03190.02440.00980.01850.009270.267170.133160.04660.01390.02180.02470.01780.021150.050110.031100.030100.02650.009190.06220.00450.00940.00380.01670.011130.038180.05440.00830.00890.02530.00360.01190.03570.014150.060130.034130.03430.007100.031100.031140.04370.01580.022240.06730.006100.02380.020110.03440.008110.03950.00940.007100.032220.10070.018170.05870.012160.03670.01530.003110.027230.067200.09130.005240.076260.16170.026160.04390.02120.00470.032100.03950.013230.13060.023100.032180.08630.006160.076370.151180.062130.03030.004180.040150.04580.02170.01530.00580.026210.059100.02290.027100.03130.005150.06130.005100.041130.046110.03470.026110.040100.03310.00160.01020.002160.055220.119360.19250.00980.02640.008210.09050.013100.02150.01490.01760.01280.02990.025220.11890.02580.033210.08420.00230.005110.03770.01240.005120.035140.05810.00180.02140.01070.01930.006100.03360.01370.015120.044110.033130.058100.023140.052100.033180.059200.059120.046150.057100.023160.05250.01160.01360.012140.07530.00740.007170.05680.016130.036120.04590.022160.04530.00640.00630.00670.012220.098220.14840.00890.02540.008130.039120.05840.013130.05680.023110.02730.005/\setquadratic\plot00200.08400.32/\put{$t=0.0002*n^{2}$}[lb]at300.4\endpicture\caption{ビーム幅1の時の文節長と解析速度の関係}\label{Kaisekisokudo}\end{figure}図から実際の解析時間も，文長に対してほぼ2乗になっている事が分かる(参考の為に描き入れた二次曲線を参照．)．実際は定数部分がある為に曲線の最初の部分は分布よりも下になっていると考えられる．一文あたりの平均解析時間は0.03秒(平均文節数10.0)，最長文である41文節の文に対しては0.29秒で解析を行なった．実際，プログラムを最適化する余地は存在し，その係数については改善の余地があると考えている．また，プロセスサイズについても必要ならば，縮小する余地はあると考えている．
\section{まとめ}
本論文では文末から解析する統計的係り受け解析アルゴリズムを示した．日本語の係り受けは，ほとんどが前方から後方であるという特徴を生かし，解析は文末から文頭の方向へ解析を進めるという点と，色々な提案によって有効性が示されている統計的文解析を利用するという二つの特徴を兼ね備えた日本語文係り受け解析を提案した．係り受けの正解率は，正しい文節解析ができた結果から開始した場合，京大コーパスを使用した実験で係り受け正解率が87.2\%，文正解率が40.8\%と高い精度を示している．ビームサーチのビーム幅を調整した実験では，ビーム幅を小さくする事による精度の劣化が認められなかった．実際にビーム幅が1の際に得られた結果の95\%はビーム幅20の時の最良の結果と同一であった．また，N--best文正解率を見た時には，Nが20の時には78.5\%という非常に高い結果を示している．解析速度は，解析アルゴリズムから推測される2乗程度であり，平均0.03秒(平均文節数10.0)，最長文である41文節の文に対しては0.29秒で解析を行なった．また，他の手法との比較では，共通のベンチマークがない為，直接的な比較はできなかったが，各手法と同程度か優れた結果が得られたと判断した．共通のベンチマークを作る事は，お互いのシステムの特徴を直接的に比較し，技術の向上を計る為に有意義であると考えられる．また，今回は，文節切りができている点から解析を開始したが，そうでなく文からの解析を行なった場合には，評価の方法も難しくなる．特に文節切りが正解とシステムが出した結果とで異なる場合にはどのように判断したらよいかスタンダードな方法がない状態である．協力しあってこのようなスタンダードを決める事は意味があると思われる．\bibliographystyle{jnlpbbl}\bibliography{jpaper}\begin{biography}\biotitle{略歴}\bioauthor{関根聡}{1987年東京工業大学応用物理学科卒．同年松下電器東京研究所入社．1990-1992年UMIST，CCL，VisitingResearcher．1992年MSc．1994年からNewYorkUniversity，ComputerScienceDepartment，AssistantResearchScientist．1998年PhD．同年からAssistantResearchProfessor．自然言語処理の研究に従事．情報処理学会，人工知能学会，言語処理学会，ACL会員．}\bioauthor{内元清貴}{1994年京都大学工学部電気工学第二学科卒業．1996年同大学院修士課程修了．同年郵政省通信総合研究所入所，郵政技官．自然言語処理の研究に従事．言語処理学会，情報処理学会，各会員．}\bioauthor{井佐原均}{1978年京都大学工学部電気工学第二学科卒業．1980年同大学院修士課程修了．工学博士．同年通商産業省電子技術総合研究所入所．1995年郵政省通信総合研究所関西支所知的機能研究室室長．自然言語処理，機械翻訳の研究に従事．情報処理学会，言語処理学会，人工知能学会，日本認知科学会，各会員．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}