\section{はじめに}
入力文の構文構造を明らかにする構文解析手法には，大きく分けて，1)可能な構造をすべて生成する手法と，2)可能な構造に優劣を付け，そのうち最も適切なものだけを，または適切なものから順に生成する手法，の二つがある．前者の手法として，これまでに，一般化LR法\cite{Tomita85}やSAX\cite{Matsumoto86}，LangLAB\cite{Tokunaga88}などの効率の良い手法が数多く提案されている．しかしながら，これらの手法を，機械翻訳システムなどの実用を目指した自然言語処理システムに組み込むことは，必ずしも適切ではない．なぜならば，通常，可能な構文構造の数は膨大なものになるため，それらをすべて意味解析などの構文解析以降の処理過程に送ると，システム全体としての効率が問題になるからである\footnote{文献\cite{Tomita85}には，構文構造の曖昧さをユーザとの対話で解消する方法も示されている．}．意味的親和性や照応関係に関する選好なども考慮に入れて全体で最も適切となる解釈は，最も適切な構文構造から得られるとは限らないので，システム全体で最も適切な解釈を得るためには，最悪の場合，可能な構造をすべて生成しなければならない．しかし，より適切な構文構造がシステム全体で最も適切な解釈の構成要素となる可能性が高いと期待されるので，適切でない構造は生成しなくてもよい可能性が高い．従って，可能な構造のうち最も適切なものだけをまず生成し，構文解析以降の処理からの要請があって初めて，次に適切な構造を生成するための処理を開始する後者の手法のほうが，システム全体の効率の観点からは望ましい．後者の手法を実現するためのアプローチでは，費用が付与された部分構造を状態とする状態空間において，目標状態のうち費用の最も小さいものを発見するという探索問題として構文解析を捉えるのが自然である．このように捉えると，確立された種々の探索戦略を構文解析に応用することができる．本稿では，可能な構造のうち生成費用の最も小さいものだけをまず生成し，必要ならば可能な構造が尽きるまですべての構造を生成費用の昇順に生成する構文解析法を提案する．基本的な考え方は，チャート法のアジェンダ\cite{Kay80}を$\A^*$法の探索戦略\cite{Nilsson80}に従って制御することである\cite{Yoshimi90}．チャート法は，良く知られているように，重複処理を行わない効率の良い構文解析の枠組みである．解析過程において生成されうる部分構造に，構文規則に付与された費用に基づいて計算される生成費用を付与するとともに，その構造を構成要素として持つ全体構造を生成するまでの費用を，$\A^*$法の最適性条件を満たし実際の費用になるべく近くなるように推定して付与し，競合する部分構造のうちその生成費用と推定費用の和が最も小さいものに対する処理を優先的に進めれば，効率の良い構文解析が実現できる．本稿の手法と同じように，適切な構造を優先的に生成する手法として，これまでに，Shieberの手法\cite{Shieber83}やKGW+p\cite{Tsujii88}，島津らの手法\cite{Shimazu89}などが提案されている．これら関連する研究との比較は\ref{sec:comparison}節で行なう．
\section{$\A^*$法の探索戦略に従うアジェンダ制御}
\label{sec:astar_chart}$\A^*$法\hspace{0.1mm}と\hspace{0.1mm}チャート法について簡\hspace{0.1mm}単に説\hspace{0.1mm}明した後，\hspace{0.1mm}これらを組\hspace{0.1mm}み\hspace{0.1mm}合\hspace{0.1mm}わせて，可\hspace{0.1mm}能な構\hspace{0.1mm}文\hspace{0.1mm}構\hspace{0.1mm}造を\\適切な順に必要なだけ生成する手法について述べる．$\A^*$法は，初期状態から現在状態までの費\\用$g$と，現在状態から目標状態までの推定費用$\hat{h}$との和$\hat{f}$を発見的知識として探索を行なう．適\\用可能な状態遷移オペレータが残っている状態と残っていない状態を，それぞれ，OPENリストとCLOSEリストに保持する．探索では，1)全推定費用$\hat{f}$の最も小さい状態をOPENリスト\\から取り出し，CLOSEリストに入れる，2)取り出した状態に状態遷移オペレータを適用して，すべての継続状態を生成する，3)各継続状態について$\hat{f}$を計算し，継続状態のうちOPENリストとCLOSEリストのいずれにも入っていない状態をOPENリストに入れる，という三つの過程を繰り返し，OPENリストから取り出した状態が目標状態であれば，探索を終える．$\A^*$法の\\探索戦略に従う探索では，推定費用$\hat{h}$が現在状態から目標状態までの実際の費用$h$より大きくないという最適性条件が成り立つならば，目標状態が存在する限り，費用の最も小さい目標状態に到達できることが証明されている．チャート法は，チャートと呼ばれる表に，弧と呼ばれる部分的構文構造を登録しながら処理を進める．構文規則$\alpha\rightarrow\beta_1\ldots\beta_m$から生成される弧は，$[\beta_1\ldots\beta_i\[?]_{\beta_{i+1}}\ldots[?]_{\beta_m}]_\alpha$の形式で表\\される．$\beta_1\ldots\beta_i$は既に完成した構造の列であり，$[?]_{\beta_{i+1}}\ldots[?]_{\beta_m}$は空所と呼ばれる未完成の構造の列である．弧は，空所があるとき($1\lei<m$のとき)活性弧と呼ばれ，ないとき($i=m$のとき)不活性弧と呼ばれる．また，その弧の生成に用いられた構文規則の左辺の構文範疇でラベル付けされている．以後，紛れなければ，弧をその構文範疇名で呼ぶ．上昇型チャート法の枠組みは，1)不活性弧のラベルを右辺の第一項として持つ構文規則を適用することで弧を成長させる予測手続き，2)活性弧の空所を不活性弧で埋めることで弧を成長させる結合手続き，の二つの手続きから成る．解析のある時点において，予測手続きまたは結合手続きの処理対象となる弧が複数存在するとき，そのうちどの弧を選択するかは，アジェンダと呼ばれるリストを用いて制御される．アジェンダ制御にどのような戦略を用いるかに応じて，チャート法は様々な振舞いを示す．チャート法による構文解析を探索問題と捉えると，自然な対応付けとして，チャート法における弧，予測手続きと結合手続き，アジェンダ，チャートは，それぞれ，探索問題における状態，状態遷移オペレータ，OPENリスト，CLOSEリストとみなせる．以後，ラベルが終端構文範疇であり，初期状態に相当する不活性弧を初期弧と呼ぶ．また，$n$を入力文の終了位置とするとき位置が$[0,n]$であり，ラベルが目標構文範疇であり，目標状態に相当する不活性弧を目標弧と呼ぶ．弧には，費用付き構文規則を適用して初期弧からその弧を生成するために要した費用を付与する．これは，初期状態から現在状態までの費用$g$に相当し，後に\ref{sec:rule}節で示す式(\ref{eq:cost})で計算される．さらに，弧には，それを構成要素として持つ目標弧を生成するための推定費用を付与する．これは，現在状態から目標状態までの推定費用$\hat{h}$に相当し，後に\ref{sec:est}節で示す式(\ref{eq:est})\\で計算される．\hspace*{-0.5mm}式(\ref{eq:est})\hspace*{-0.3mm}で計算される推定費用$\hat{h}$は，\hspace*{-0.5mm}$\A^*$法の最適性条件$\hat{h}\leh$を満たすので，\hspace*{-0.5mm}$g$\hspace*{-0.1mm}と\hspace*{-0.1mm}$\hat{h}$\\の和$\hat{f}$が小さい順に弧をアジェンダから取り出せば，$\A^*$法の探索戦略に従う上昇型チャート法が実現できる．そのアルゴリズムを図\ref{fig:astar_chart}に示す．このアルゴリズムは，費用の最も小さい目標弧を生成した後も，そのまま処理を続ければ，目標弧を費用の昇順に必要なだけ生成することができる．\begin{figure}\samepage\begin{center}\fbox{\small{\begin{minipage}{0.9\textwidth}\vspace*{0.5em}\setcounter{algocounter}{0}\begin{ALGORITHM}\stepすべての初期弧をアジェンダに入れる．\stepアジェンダが空ならば，終了．\label{algo:ac_loop}\step全推定費用$\hat{f}$の最も小さい弧をアジェンダから取り出し，チャートに入れる．それが目標弧ならば，解析成功．不活性弧ならば，予測手続きを実行．活性弧ならば，結合手続きを実行．\label{algo:ac_pop}\step予測手続きまたは結合手続きで弧が生成されていれば，そのうちアジェンダまたはチャートに存在しないものをアジェンダに入れる．\label{algo:ac_push}\step予測手続きまたは結合手続きで生成された弧が不活性弧であれば，チャート中の活性弧のうちこの不活性弧と結合できるものをすべてアジェンダに戻す．ステップ\ref{algo:ac_loop}へ．\end{ALGORITHM}\begin{LIST}\item[\bf予測手続き]位置が$[x,y]$である不活性弧$\beta_1$が存在するとき，右辺第一項が$\beta_1$であるすべての構文規則$\alpha\rightarrow\beta_1\ldots\beta_m$を適用し，位置が$[x,y]$である活性弧$[\beta_1\[?]_{\beta_{2}}\ldots[?]_{\beta_{m}}]_\alpha$を新たに生成する．ただし，$m=1$ならば不活性弧を生成する．\item[\bf結合手続き]活性弧$\alpha$の位置が$[x,y]$であり，最左空所が$[?]_{\beta_{i}}$であるとき，位置が$[y,z]$であるすべての不活性弧$\beta_i$で$[?]_{\beta_{i}}$を埋め，位置が$[x,z]$である活性弧を新たに生成する．ただし，$i=m$ならば不活性弧を生成する．\end{LIST}\vspace*{0.5em}\end{minipage}}}\end{center}\caption{$\A^*$法の探索戦略に従うチャート法}\label{fig:astar_chart}\end{figure}図\ref{fig:astar_chart}のアルゴリズムは最も基本的なものである．この基本アルゴリズムに次のような改良を加えれば，生成される弧の数は減少する．可能な構文構造を効率良く表現するために，1)二つの構造が持つすべての情報が同じであるとき，それらの構造を共有し(sub-treesharing)，2)二つの構造が持つ情報のうち内部構造以外のすべての情報が同じであるとき，それらの構造を統合する(localambiguitypacking)方法\cite{Tomita85}が用いられることがある．元のチャート法に基づく基本アルゴリズムでは，前者は実現されているが後者は実現されていない．実現するためには，ステップ\ref{algo:ac_push}を次のように変更すればよい．\begin{LIST}\item[{\bfステップ\ref{algo:ac_push}'}]生成された弧が不活性弧であり，そのラベル，位置，全推定費用と同じものを持つ不活性弧がアジェンダに存在すれば，それら二つの弧を統合してアジェンダに入れ，チャートに存在すれば，二つの弧を統合してチャートに入れる．さもなければ，生成された弧をアジェンダに入れる．\end{LIST}
\section{弧の生成費用の計算}
\label{sec:rule}弧を生成するための費用は，構文規則に付与された費用に基づいて計算される．費用付き構文規則は，文脈自由文法の形式に従い，一般に次のように表せる．\begin{equation}\alpha\rightarrow\beta_1/w_{\beta_1}\ldots\beta_m/w_{\beta_m},\\C_\alpha\label{eq:rule}\end{equation}$\alpha$は非終端構文範疇，$\beta_i$は終端構文範疇または非終端構文範疇である．$C_\alpha$は，この規則の適用\\費用を表す．$w_{\beta_i}$は，弧$\beta_i$と$\beta_j\(j\neqi)$の相対的関係を表す重みである．$C_\alpha$は非負の実数，$w_{\beta_i}$\\は正の実数とする．活性弧$[\beta_1\ldots\beta_i\[?]_{\beta_{i+1}}\ldots[?]_{\beta_{m}}]_\alpha$($i=m$ならば不活性弧)を生成するための費用は，不活性弧$\beta_j\(1\lej\lei)$を生成するための費用$g_{\beta_j}$に重み$w_{\beta_j}$をかけたものの和に，規則(\ref{eq:rule})の適用\\費用$C_\alpha$を加えた値であると定め，次式で計算する．\begin{equation}g_\alpha=\sum_{j=1}^iw_{\beta_j}\timesg_{\beta_j}+C_\alpha\\(1\lei\lem)\label{eq:cost}\end{equation}初期弧の生成費用は0とする．
\section{目標弧までの費用の推定}
\label{sec:est}弧から目標弧までの費用の推定は，入力文とは独立に，構文規則だけに基づいてあらかじめ\\行なっておく．\hspace*{0.1mm}従って，\hspace*{0.1mm}一\hspace*{0.1mm}度\hspace*{0.1mm}求めた推\hspace*{0.1mm}定\hspace*{0.1mm}費\hspace*{0.1mm}用は，\hspace*{0.1mm}費\hspace*{0.1mm}用\hspace*{0.1mm}付き構\hspace*{0.1mm}文\hspace*{0.1mm}規\hspace*{0.1mm}則に変\hspace*{0.1mm}更がない限り変\hspace*{0.1mm}更され\\ない．\hspace*{0.1mm}推\hspace*{0.1mm}定は，上\hspace*{0.1mm}昇\hspace*{0.1mm}型\hspace*{0.1mm}解\hspace*{0.1mm}析とは逆\hspace*{0.1mm}方\hspace*{0.1mm}向に目\hspace*{0.1mm}標\hspace*{0.1mm}弧から初\hspace*{0.1mm}期\hspace*{0.1mm}弧に向けて行ない，\hspace*{0.1mm}求めた推\hspace*{0.1mm}定\hspace*{0.1mm}費\hspace*{0.1mm}用を\\各弧に付与する．推定を下降型で行なうので，本節では，弧$\alpha$から目標弧までの推定費用を，目\\標弧から弧$\alpha$までの推定費用と呼ぶ．推定費用は，構文解析で活性弧の空所が左から順に埋って\\いくことを前提として計算する．目標構文範疇から始めて，構文規則を左辺から右辺への書き換えに繰り返し用い，目標弧から活性弧$[?]_\alpha$までの推定費用$\hat{h}_\alpha$が計算済みであり，規則(\ref{eq:rule})が存在するとき，目標弧から活性弧$[?]_{\beta_i}$までの推定費用$\hat{h}_{\beta_i}$は，次式で計算できる．\begin{equation}\hat{h}_{\beta_i}=\left\{\begin{array}{ll}\min\hat{h}_\alpha+\displaystyle\sum_{j>i}^mw_{\beta_j}\times\ming_{\beta_j}+C_\alpha&(i=1のとき)\\\min\hat{h}_\alpha+\displaystyle\sum_{j>i}^mw_{\beta_j}\times\ming_{\beta_j}&(1<i<mのとき)\\\min\hat{h}_\alpha&(i=mのとき)\end{array}\right.\label{eq:est}\end{equation}$C_\alpha$は規則(\ref{eq:rule})の適用費用であり，$\displaystyle\sum_{j>i}^mw_{\beta_j}\times\ming_{\beta_j}$は活性弧$[\beta_1\ldots\beta_i\[?]_{\beta_{i+1}}\ldots[?]_{\beta_{m}}]_\alpha$のすべ\\ての空所を埋めるための最小費用である．下降型推定で求めた目標弧から活性弧$[?]_\alpha$までの費用$\hat{h}_\alpha$は，\hspace*{-0.4mm}上昇型構文解析を行なうときには不活性弧$\alpha$から目標弧までの推定費用となる．\hspace*{-0.4mm}式(\ref{eq:est})\\で計算される推定費用は，目標弧から活性弧$[?]_\alpha$までの可能な推定費用のうち最小値を右辺第一項とし，\hspace*{-0.4mm}可能な不活性弧$\beta_j$の生成費用のうち最小値を第二項としているので，\hspace*{-0.4mm}$\A^*$法の最適性\\条件を満たす．式(\ref{eq:est})を用いて推定費用を求めるために，まず，不活性弧$\beta_j$の最小生成費用$\ming_{\beta_j}$を計算\\する．そのアルゴリズムを図\ref{fig:min_cost}に示す．\begin{figure}\samepage\begin{center}\fbox{\small{\begin{minipage}{0.9\textwidth}\vspace*{0.5em}\setcounter{algocounter}{0}\begin{ALGORITHM}\step与えられたすべての構文規則をリストに入れる．初期弧の生成費用を0とする．\label{algo:cost_init}\stepリストが空ならば，終了．\label{algo:cost_loop}\stepリストの先頭の規則$\alpha\rightarrow\beta_1/w_{\beta_1}\ldots\beta_m/w_{\beta_m},\\C_\alpha$を取り出す．\label{algo:cost_pop}\stepすべての不活性弧$\beta_i$について，生成費用が計算済みならば，不活性弧$\alpha$の生成費用を\ref{sec:rule}節の式(\ref{eq:cost})で計算し，ステップ\ref{algo:cost_min}へ．さもなければ，取り出した規則をリストの最後尾へ入れ，ステップ\ref{algo:cost_loop}へ．\label{algo:cost_cost}\step不活性弧$\alpha$について，今求めた値と以前求めた値の大小比較を行ない，小さいほうを不活性弧$\alpha$の生成費用とする．今求めた値のほうが小さければ，既にリストから取り出した規則のうち構文範疇$\alpha$を導出するすべての規則をリストに戻す．ステップ\ref{algo:cost_loop}へ．\label{algo:cost_min}\end{ALGORITHM}\vspace*{0.5em}\end{minipage}}}\end{center}\caption{不活性弧の最小生成費用を求めるアルゴリズム}\label{fig:min_cost}\end{figure}例えば，図\ref{fig:rule}のような費用付き構文規則\footnote{この構文規則は，文献\cite{Kay80}に示された規則に費用を付与したものである．}が与えられたとき，この規則に従って生成される各不活性弧の最小生成費用は，図\ref{fig:min_cost}のアルゴリズムを用いて次のように計算される．\begin{figure}\begin{center}\small{\begin{tabular}{clclcclcl}(a)&S&$\rightarrow$&NP/1\VP/1,\1&&(f)&A&$\rightarrow$&failing/1,\1\\(b)&NP&$\rightarrow$&A/1\N/1,\1&&(g)&A&$\rightarrow$&hard/1,\1\\(c)&NP&$\rightarrow$&PRP/1\N/1,\5&&(h)&PRP&$\rightarrow$&failing/1,\1\\(d)&VP&$\rightarrow$&V/1\A/1,\5&&(i)&N&$\rightarrow$&student/1,\1\\(e)&VP&$\rightarrow$&V/1\AV/1,\1&&(j)&V&$\rightarrow$&looked/1,\1\\&&&&&(k)&AV&$\rightarrow$&hard/1,\1\end{tabular}}\end{center}\caption{費用付き構文規則の例}\label{fig:rule}\end{figure}まず，ステップ\ref{algo:cost_init}で，$g_\FAIL=0$，$g_\HARD=0$，$g_\STUD=0$，$g_\LOOK=0$となる．\hspace*{0.1mm}ス\hspace*{0.1mm}テ\hspace*{0.1mm}ッ\hspace*{0.1mm}プ\ref{algo:cost_init}で，リストに，規\hspace*{0.1mm}則(a)が先\hspace*{0.1mm}頭，規\hspace*{0.1mm}則(k)が最\hspace*{0.1mm}後\hspace*{0.1mm}尾という順\\で入っているとすると，一回目のループのステップ\ref{algo:cost_pop}で，規則(a)~$\SS\rightarrow\NP/1\\VP/1,\1$が取り\\出されるが，$g_\NP$も$g_\VP$もまだ求まっていないので，この規則はステップ\ref{algo:cost_cost}でリストの最後尾に入れられる．二〜五回目のループでも同様に，規則(b)〜(e)が取り出されるが，いずれもステップ\ref{algo:cost_cost}でリストの最後尾に入れられる．六回目のループのステップ\ref{algo:cost_pop}では規則(f)が取り出される．$g_\FAIL$は既に求まっているので，ステップ\ref{algo:cost_cost}で，$g_\A=w_\FAIL\timesg_\FAIL+C_\A=1$と計算される．この値は不活性弧Aについて初めて計算された値であるので，ステップ\ref{algo:cost_min}では何も行なわれない．七回目のループのステップ\ref{algo:cost_pop}で規則(g)が取り出されると，ステップ\ref{algo:cost_cost}で$g_\A=1$となる．この値は不活性弧Aについて既に求まっている値より小さくないので，ステップ\ref{algo:cost_min}では何も行なわれない．以下，同様にして，$g_\PRP=1$，$g_\N=1$，$g_\V=1$，$g_\AV=1$，$g_\NP=3$，$g_\VP=3$，$g_\SS=7$が順に求まる．次に，\hspace*{0.3mm}以\hspace*{0.1mm}上\hspace*{0.1mm}の\hspace*{0.1mm}よ\hspace*{0.1mm}う\hspace*{0.1mm}に\hspace*{0.1mm}し\hspace*{0.1mm}て計\hspace*{0.1mm}算\hspace*{0.1mm}された\hspace*{0.1mm}不\hspace*{0.2mm}活\hspace*{0.2mm}性\hspace*{0.2mm}弧の最\hspace*{0.1mm}小\hspace*{0.1mm}生\hspace*{0.2mm}成\hspace*{0.2mm}費\hspace*{0.2mm}用\hspace*{0.1mm}を式(\ref{eq:est})に代入して，\hspace*{0.3mm}目\hspace*{0.1mm}標\hspace*{0.1mm}弧\\から各弧までの最小推定費用を再帰的に求める．そのアルゴリズムを図\ref{fig:min_est}に示す．\begin{figure}\samepage\begin{center}\fbox{\small{\begin{minipage}{0.9\textwidth}\vspace*{0.5em}\setcounter{algocounter}{0}\begin{ALGORITHM}\step目標構文範疇をリストに入れる．目標弧から目標弧までの推定費用を0とする．\label{algo:est_init}\stepリストが空ならば，終了．\label{algo:est_loop}\stepリストの先頭の構文範疇$\alpha$を取り出す．\label{algo:est_pop}\step左辺が$\alpha$であるすべての規則$\alpha\rightarrow\beta_1/w_{\beta_1}\ldots\beta_m/w_{\beta_m},\\C_\alpha$に現れる各$\beta_i$について，推定費用を式(\ref{eq:est})で計算し，それを不活性弧$\beta_i$までの推定費用とする．ただし，$\beta_i$が複数の規則に現れるか，または，ある一つの規則において$\beta_i=\beta_j\(i\neqj)$ならば，求まった値のうち最小値を不活性弧$\beta_i$までの推定費用とする．目標弧から活性弧$[\beta_1\ldots\beta_i\[?]_{\beta_{i+1}}\ldots[?]_{\beta_m}]_\alpha$までの推定費用は，$1<i<m$のとき，不活性弧$\beta_i$までの推定費用と同じ値とし，$i=1$のとき，不活性弧$\beta_1$までの推定費用から規則の適用費用$C_\alpha$を引いた値とする．\label{algo:est_est}\step活性弧$[\beta_1\ldots\beta_i\[?]_{\beta_{i+1}}\ldots[?]_{\beta_m}]_\alpha$について，今求めた値と以前求めた値の大小比較を行ない，小さいほうを目標弧からこの活性弧までの推定費用とする．また，不活性弧$\beta_i$についても同様に，今求めた値と以前求めた値のうち小さいほうを目標弧から不活性弧$\beta_i$までの推定費用とする．\label{algo:est_compare}\step今求めた推定費用が初めて計算された値か，または，以前求めた値よりも小さい値であれば，構文範疇$\beta_i$をリストの最後尾に入れる．ステップ\ref{algo:est_loop}へ．\label{algo:est_push}\end{ALGORITHM}\vspace*{0.5em}\end{minipage}}}\end{center}\caption{目標弧から弧までの最小費用を推定するアルゴリズム}\label{fig:min_est}\end{figure}図\ref{fig:rule}の費用付き構文規則が与えられているとき，推定費用は次のように計算される．ステップ\ref{algo:est_pop}で構文範疇Sが取り出されるので，規則(a)がステップ\ref{algo:est_est}での処理対象となり，目標弧から不活性弧NPまでの推定費用は，$\hat{h}_\NP=\hat{h}_\SS+w_\VP\timesg_\VP+C_\SS=4$と計算され，不活性弧VPまでの推定費用は$\hat{h}_\VP=\hat{h}_\SS=0$となる．活性弧$[\NP\[?]_\VP]_\SS$までの推定費用は，$\hat{h}_{[\NP\[?]_\VP]_\SS}=3$と\hspace*{0.2mm}な\hspace*{0.2mm}る．\hspace*{0.2mm}こ\hspace*{0.2mm}れ\hspace*{0.2mm}ら\hspace*{0.2mm}の\hspace*{0.2mm}推\hspace*{0.2mm}定\hspace*{0.2mm}値\hspace*{0.2mm}は\hspace*{0.2mm}初\hspace*{0.2mm}め\hspace*{0.2mm}て\hspace*{0.2mm}計\hspace*{0.2mm}算\hspace*{0.2mm}さ\hspace*{0.2mm}れ\hspace*{0.2mm}た\hspace*{0.2mm}値\hspace*{0.2mm}で\hspace*{0.2mm}あ\hspace*{0.2mm}る\hspace*{0.2mm}の\hspace*{0.2mm}で，\hspace*{0.2mm}\hspace*{0.2mm}ス\hspace*{0.2mm}テ\hspace*{0.2mm}ッ\hspace*{0.2mm}プ\hspace*{0.2mm}\ref{algo:est_compare}で\hspace*{0.2mm}の\hspace*{0.2mm}大\hspace*{0.2mm}小\hspace*{0.2mm}比\hspace*{0.2mm}較\hspace*{0.2mm}は\hspace*{0.2mm}行なわれない．ステップ\ref{algo:est_push}でNPとVPがリストの最後尾に入れられる．二回目のループのステップ\ref{algo:est_pop}では構文範疇NPが取り出され，規則(b)と(c)がステップ\ref{algo:est_est}での処理対象となる．規則(b)について，不活性弧Aまでの推定費用は，$\hat{h}_\A=\hat{h}_\NP+w_\N\timesg_\N+C_\NP=6$となり，\hspace*{-0.3mm}不活性弧Nまでの推定費用は$\hat{h}_\N=\hat{h}_\NP=4$となる．\hspace*{-0.3mm}活性弧$[\A\[?]_\N]_\NP$までの推定費用は，$\hat{h}_{[\A\[?]_\N]_\NP}=5$となる．規則(c)については，不活性弧PRPまでの推定費用は，$\hat{h}_\PRP=\hat{h}_\NP+w_\N\timesg_\N+C_\NP=10$と計算され，活性弧$[\PRP\[?]_\N]_\NP$までの推定費用は，$\hat{h}_{[\PRP\[?]_\N]_\NP}=5$となる．ステップ\ref{algo:est_push}でA，PRP，Nがリストの最後尾に入れられる．三回目のループのステップ\ref{algo:est_est}では，規則(d)と(e)が処理対象となる．規則(d)について，不活性弧Vまでの推定費用は，$\hat{h}_\V=\hat{h}_\VP+w_\A\timesg_\A+C_\VP=6$，不活性弧Aまでの推定費用は$\hat{h}_\A=\hat{h}_\VP=0$となる．活性弧$[\V\[?]_\A]_\VP$までの推定費用は，$\hat{h}_{[\V\[?]_\A]_\VP}=1$となる．規則(e)については，不活性弧Vまでの推定費用は，$\hat{h}_\V=\hat{h}_\VP+w_\AV\timesg_\AV+C_\VP=2$，不活性弧AVまでの推定費用は$\hat{h}_\AV=\hat{h}_\VP=0$となる．不活性弧Vについて，規則(d)から得られた値6と規則(e)から得られた値2のうち小さいほうの後者がその推定費用となる．ステップ\ref{algo:est_compare}では，不活性弧Aについて，今，規則(d)から得られた値0は，二回目のループで規則(b)から得られた値6より小さいので，推定費用は0となる．以下，同様に処理が進むと，表\ref{tab:est}に示す推定費用が最終的に得られる．\begin{table}\caption{目標弧からの推定費用}\label{tab:est}\begin{center}\begin{tabular}{|l|r||l|r||l|r|}\hline\multicolumn{1}{|c|}{不活性弧\rule{0pt}{11pt}}&\multicolumn{1}{|c||}{$\hat{h}$}&\multicolumn{1}{|c|}{不活性弧}&\multicolumn{1}{|c||}{$\hat{h}$}&\multicolumn{1}{|c|}{活性弧}&\multicolumn{1}{|c|}{$\hat{h}$}\\\hline\hlineS&0&V&2&$[\NP\[?]_\VP]_\SS$&3\\NP&4&AV&0&$[\A\[?]_\N]_\NP$&5\\VP&0&failing&1&$[\PRP\[?]_\N]_\NP$&5\\A&0&hard&1&$[\V\[?]_\A]_\VP$&1\\PRP&10&student&5&$[\V\[?]_\AV]_\VP$&1\\N&4&looked&3&&\\\hline\end{tabular}\end{center}\end{table}
\section{解析例}
図\ref{fig:rule}の構文規則と表\ref{tab:est}の推定費用を用いて`failingstudentlookedhard'を解析する過程を追う．解析アルゴリズムは，\ref{sec:astar_chart}節で述べた改良を加えていない図\ref{fig:astar_chart}の基本的なものを用いることにする．表\ref{tab:chart}は，この例文に対して全解探索を行なった場合に得られるチャートである．図\ref{fig:astar_chart}のアルゴリズムによる解析で，費用の最も小さい目標弧が得られるまでのアジェンダの変化の様子を表\ref{tab:agenda}に示す．表\ref{tab:agenda}の各行は，解析のある時点でのアジェンダの内容を表す．アジェンダの要素は，弧と全推定費用($\hat{f}=g+\hat{h}$)の対であり，$\hat{f}$の昇順に左から右へ並んでいる．表\ref{tab:agenda}の最左要素がアジェンダの先頭要素である．アジェンダは，図\ref{fig:astar_chart}の解析アルゴリズムにおける第$k$回目のループでの処理で，第$k$行目から第$k+1$行目へ変化する．以後，第$k$行目のアジェンダをアジェンダ$k$と呼ぶ．弧は，表\ref{tab:chart}の\#欄の番号で表される．例えば，アジェンダ1の第一要素1:\#4は，表\ref{tab:chart}の四行目の全推定費用が1である弧hardを指す．まず，アジェンダ1から先頭要素1:\#4を取り出し，不活性弧\#4に予測手続きを適用して得られた弧\#9と\#10をアジェンダに加え，$\hat{f}$の昇順に並べると，アジェンダ2へ変化する．アジェンダ2の先頭要素の不活性弧\#10は，それに対して適用できる構文規則が存在しないので，アジェンダ3へ変化する．アジェンダ3，4，5，6，7の先頭要素は不活性弧であるので，これらに予測手続きを適用して得られた弧を加え，$\hat{f}$の昇順に並べると，それぞれ，アジェンダ4，5，6，7，8となる．アジェンダ8の先頭要素である弧\#15は活性弧であるので，\#15と不活性弧\#10に結合手続きを適用して得られた弧\#19をアジェンダに加え，$\hat{f}$の昇順に並べると，アジェンダ9へ変化する．以下，同様に処理を進め，アジェンダ15から先頭要素7:\#23を取り出すと，弧\#23は目標弧であるので，費用の最も小さい目標弧を発見したことになり，解析を中断する．もし費用が二番目に小さい目標弧が必要ならば，アジェンダ16から処理を再開すればよい．以上の解析過程の追跡からわかるように，弧\#13，\#17，\#18，\#21，\#22，\#24，\#25を生成せずに，また，弧\#6，\#11，\#14に対して手続きを適用せずに，生成費用の最も小さい目標弧が得られる．\begin{table}\caption{例文に対して全解探索を行なった場合のチャート}\label{tab:chart}\begin{center}\begin{tabular}{|r|r|c|l|}\hline\multicolumn{1}{|c|}{\#}&\multicolumn{1}{|c|}{$g+\hat{h}$}&位置&\multicolumn{1}{|c|}{項}\\\hline\hline1&$0+1$&[0,1]&failing\\2&$0+5$&[1,2]&student\\3&$0+3$&[2,3]&looked\\4&$0+1$&[3,4]&hard\\5&$1+0$&[0,1]&$[\FAIL]_\A$\\6&$1+10$&[0,1]&$[\FAIL]_\PRP$\\7&$1+4$&[1,2]&$[\STUD]_\N$\\8&$1+2$&[2,3]&$[\LOOK]_\V$\\9&$1+0$&[3,4]&$[\HARD]_\A$\\10&$1+0$&[3,4]&$[\HARD]_\AV$\\11&$2+5$&[3,4]&$[[\HARD]_\A\[?]_\N]_\NP$\\12&$2+5$&[0,1]&$[[\FAIL]_\A\[?]_\N]_\NP$\\13&$6+5$&[0,1]&$[[\FAIL]_\PRP\[?]_\N]_\NP$\\14&$6+1$&[2,3]&$[[\LOOK]_\V\[?]_\A]_\VP$\\15&$2+1$&[2,3]&$[[\LOOK]_\V\[?]_\AV]_\VP$\\16&$3+4$&[0,2]&$[[\FAIL]_\A\[\STUD]_\N]_\NP$\\17&$7+4$&[0,2]&$[[\FAIL]_\PRP\[\STUD]_\N]_\NP$\\18&$7+0$&[2,4]&$[[\LOOK]_\V\[\HARD]_\A]_\VP$\\19&$3+0$&[2,4]&$[[\LOOK]_\V\[\HARD]_\AV]_\VP$\\20&$4+3$&[0,2]&$[[[\FAIL]_\A\[\STUD]_\N]_\NP\[?]_\VP]_\SS$\\21&$8+3$&[0,2]&$[[[\FAIL]_\PRP\[\STUD]_\N]_\NP\[?]_\VP]_\SS$\\22&$11+0$&[0,4]&$[[[\FAIL]_\A\[\STUD]_\N]_\NP\[[\LOOK]_\V\[\HARD]_\A]_\VP]_\SS$\\23&$7+0$&[0,4]&$[[[\FAIL]_\A\[\STUD]_\N]_\NP\[[\LOOK]_\V\[\HARD]_\AV]_\VP]_\SS$\\24&$15+0$&[0,4]&$[[[\FAIL]_\PRP\[\STUD]_\N]_\NP\[[\LOOK]_\V\[\HARD]_\A]_\VP]_\SS$\\25&$11+0$&[0,4]&$[[[\FAIL]_\PRP\[\STUD]_\N]_\NP\[[\LOOK]_\V\[\HARD]_\AV]_\VP]_\SS$\\\hline\end{tabular}\end{center}\end{table}\begin{table}\caption{例文解析時のアジェンダの変化の様子}\label{tab:agenda}\begin{center}\begin{tabular}{r|l}\hline&\multicolumn{1}{|c}{アジェンダ}\\\hline\hline1.&1:\#4,\1:\#1,\3:\#3,\5:\#2\\2.&1:\#10,\1:\#9,\1:\#1,\3:\#3,\5:\#2\\3.&1:\#9,\1:\#1,\3:\#3,\5:\#2\\4.&1:\#1,\3:\#3,\5:\#2,\7:\#11\\5.&1:\#5,\3:\#3,\5:\#2,\7:\#11,\11:\#6\\6.&3:\#3,\5:\#2,\7:\#12,\7:\#11,\11:\#6\\7.&3:\#8,\5:\#2,\7:\#12,\7:\#11,\11:\#6\\8.&3:\#15,\5:\#2,\7:\#12,\7:\#11,\7:\#14,\11:\#6\\9.&3:\#19,\5:\#2,\7:\#12,\7:\#11,\7:\#14,\11:\#6\\10.&5:\#2,\7:\#12,\7:\#11,\7:\#14,\11:\#6\\11.&5:\#7,\7:\#12,\7:\#11,\7:\#14,\11:\#6\\12.&7:\#12,\7:\#11,\7:\#14,\11:\#6\\13.&7:\#16,\7:\#11,\7:\#14,\11:\#6\\14.&7:\#20,\7:\#11,\7:\#14,\11:\#6\\15.&7:\#23,\7:\#11,\7:\#14,\11:\#6\\16.&7:\#11,\7:\#14,\11:\#6\\\hline\end{tabular}\end{center}\end{table}
\section{関連研究との比較}
\label{sec:comparison}KGW+p\cite{Tsujii88}は，拘束規則に基づいてすべての可能な部分構造を生成する機構と，優先規則に基づいて構造の良さを比較し，それらの間に有意な差が生じたときに，一部の構造を選択する機構から構成されている．KGW+pでは，解析のある時点で優先されなかった部分構造が選択されるのは，優先された部分構造を構成要素とする構造が生成できなかった場合に限られており，局所的な選択の積み重ねで解析を進める一種のビーム探索が行なわれている．このため，生成された全体構造が可能な構造のうち最も適切なものであることが保証されない．これに対し，本手法では保証される．シフト／レデュース法において，1)シフト操作とレデュース操作の適用に競合が生じた場合には，シフト操作を優先させ，2)レデュース操作同士の競合が生じた場合には，右辺がより長い構文規則の適用を優先させる，という二つのメタレベルの優先方略に従い，右連合(rightassociation)や最小付加(minimalattachment)などの英語における選好を反映した構造を生成する手法が提案されている\cite{Shieber83}．また，日本語文の構文的特徴が左枝分かれ構造であることに着目し，これを反映する構造を最初に生成するために，上記の優先方略を変更した手法も示されている\cite{Shimazu89}．これらの手法では，優先方略が探索機構の中に組み込まれているため，右連合や最小付加，左枝分かれ構造以外の構造を優先する必要が生じた場合，探索機構自体を変更しなければならない．これに対し，本手法では，探索機構と規則記述の枠組みが分離されているので，探索機構には手を加えずに，構文規則の適用費用を修正するだけで，優先すべき構造を柔軟に変更できる．例えば，名詞句の左枝分かれ構造を優先したい場合，本手法では，構文規則$\NP\rightarrow\NP/1\\NP/2,\\1$を用いればよい．この規則に従って生成される不活性弧を図\ref{fig:leftright}に示す．括弧内の数値が生成費用である．\begin{figure}\begin{center}\epsfile{file=leftright.eps}\vspace{-0.5mm}\end{center}\caption{左枝分かれ構造と右枝分かれ構造}\label{fig:leftright}\vspace{-0.5mm}\end{figure}逆に，右枝分かれ構造を優先したい場合は，右辺の第一項と第二項の重みを入れ換えればよい．また，本手法では，優先すべき構造をメタレベルの優先方略に従って選択する手法と異なり，個々の規則に付与された費用に基づいて選択するので，優先すべき構造をきめ細かく指定できる．PAMPS\cite{Uehara83}は，構文規則に付与された費用に基づいて，優先すべき構造を選択する枠組みとなっている点では，本手法と同じである．しかし，本手法と異なり，部分構造から全体構造を得るまでの費用の推定が行なわれていないので，解析過程で生成される部分構造の数は，本手法で生成される数よりも多くなる可能性が高い．確率付き構文規則は，文脈自由文法形式の規則に$0<p_\alpha\le1$なる実数を規則の適用確率として付与したものである．ただし，左辺の構文範疇が同じである各規則の適用確率の和は1でなければならない．確率付き規則を用いた構文解析では，構文構造にはその構造の生成に関与した規則の適用確率の積が付与される．確率付き規則$\alpha\rightarrow\beta_1\ldots\beta_m,\\p_\alpha$は，適用確率$p_\alpha$をそ\\の逆数の対数$\log\frac{1}{p_\alpha}$に置き換えれば，費用付き規則とみなせ，本稿の構文解析手法を適用することができる．しかし，その逆の費用付き規則から確率付き規則への変換を行なうことはできない．確率付き規則では，左辺の構文範疇が異なる規則の間での競合が記述できないからである．例えば，図\ref{fig:rule}の構文規則において，規則(f)を(h)より優先させたい場合，費用付き規則では，(f')~$\A\rightarrow\FAIL/1,\1$と(h')~$\PRP\rightarrow\FAIL/1,\2$とすればよいが，確率付き規則では，規則の適用確率$p_\alpha$は$0<p_\alpha\le1$なる実数であり，左辺の構文範疇が同じである各規則の適用確率の和は1でなければならないので，規則(h)の適用確率よりも大きな値を規則(f)に付与することはできない．従って，費用付き構文規則のほうが記述力の点で優れている．これまでに，不適格文を処理するための種々の手法が提案されている\cite{Matsumoto94}．ここでは，本手法が，語句の欠落や語順の誤りなどを含む構文的不適格文を効率良く処理できることを示す．これまでに提案されている手法の多くは，適格文用の構文規則を用いて解析を行なう機構と，この機構による通常の解析が失敗した時点で起動される不適格文を処理するための別の機構を備えている．これに対し，本手法を用いれば，Fassらの手法\cite{Fass83}と同じく，適格文と不適格文を区別せずに，両者の処理を統一的な枠組みで行なうことができる．すなわち，不適格文用の構文規則を，適格文用の規則と同じように記述し，前者の適用費用を後者のものよりも高く設定しておく．一般に，適格文と不適格文を区別しないように構文規則を拡張すると，適格文を解析する際に生成される部分構造の数が多くなり，効率が悪くなるという問題が生じる．しかし，本手法では，適用費用が高い不適格文用の規則は，適格文用の規則の適用が失敗した場合にのみ適用される可能性が高いので，効率が悪化する恐れは少ないと考えられる．
\section{おわりに}
本稿では，可能な構文構造に優劣を付け，適切な構造から順に必要なだけ生成する構文解析手法を示した．本手法は次のような特徴を持っている．\begin{enumerate}\item部分構造の共有と統合を行ない，重複処理を避ける．\item$\A^*$法の最適性条件を満たすよう推定費用を計算し，可能な構造のうち費用の最も小さい全体構造を効率良く生成する．\item優先すべき構造をきめ細かく指定でき，その変更も容易に行なえる規則記述の枠組みを提供する．\end{enumerate}自然言語処理システムは，最終的には，可能な解釈の中からシステム全体で最も適切な解釈を一つ選び出さなければならない．そのような解釈は，より適切な構造から得られると考えられるので，構文解析以降の処理からの要請があるまで，適切でない構造の生成を保留する本手法は，システム全体としての効率の向上に寄与する．本手法では，現在のところ，入力文とは独立に構文規則だけに基づいて費用の推定を行なっている．この方法では，推定を，文が入力される度に行なう必要はなく，費用付き構文規則に変更がない限り一度だけ行なっておけばよい．しかし，費用推定の精度をさらに高めるためには，入力文を参照しながら推定を行なわなければならない．これは今後の課題である．もう一つの課題は，人間が見て最も適切な構文構造を最初に生成できるように，構文規則に費用を付与することである．\ref{sec:comparison}節で述べたように，費用付き構文規則は確率文脈自由文法規則の拡張とみなせるので，確率文脈自由文法規則のパラメータ学習法として知られているInside-Outsideアルゴリズムなどを利用することで，この課題には対処できる．しかし，最終的には，学習したパラメータを人手で調整しなければならず，そのための実験が必要になろう．本手法は，最適な費用付き構文規則を記述するための実験環境を文法記述者に提供する．\bibliographystyle{jnlpbbl}\bibliography{bfc}\begin{biography}\biotitle{略歴}\bioauthor{吉見毅彦}{1962年生．1987年電気通信大学大学院計算機科学専攻修士課程修了．現在，シャープ(株)情報商品開発研究所にて日英機械翻訳システムの研究開発に従事．}\bioauthor{JiriJelinek}{1939年生．チェコのプラハのUniversitaKarlova卒業(言語学・英語学・日本語学)．1959年以来，日英機械翻訳実験中．英国Sheffield大学日本研究所専任講師を1996年退職．現在，シャープ専任研究員．}\bioauthor{西田収}{1961年10月19日生．1984年大阪教育大学教育学部中学校課程数学科卒業，同年より神戸大学工学部応用数学科の教務補佐員として勤務．1987年シャープ（株）に入社．現在は，同社の情報商品開発研究所に所属．主に，日英機械翻訳，多言語翻訳の研究に従事．情報処理学会会員．}\bioauthor{田村直之}{1957年1月31日生．1985年神戸大学大学院自然科学研究科システム科学専攻博士課程修了．学術博士．同年，日本アイ・ビー・エム(株)に入社し東京基礎研究所に勤務．1988年神戸大学工学部システム工学科助手．講師を経て，現在同大学大学院自然科学研究科助教授．論理型プログラミング言語，線形論理などに興味を持つ．著書に「Prologプログラミング入門」(オーム社，共著)．情報処理学会，日本ソフトウェア科学会，システム制御情報学会，ACM，IEEE各会員．}\bioauthor{村上温夫}{1929年生．1952年大阪大学理学部数学科卒業．神戸大学理学部助手，講師，教養部助教授を経て，1968年より工学部教授．この間，UniversityofKansas客員助教授，UniversityofNewSouthWales客員教授，NanyangUniversity客員教授を併任．1992年より甲南大学理学部教授．神戸大学名誉教授．理学博士(東京大学)．関数解析，偏微分方程式，人工知能，数学教育などに興味を持つ．著書に``MathematicalEducationforEngineeringStudents''(CambridgeUniversityPress)など．日本数学会，日本数学教育学会，情報処理学会，教育工学会，AMS各会員．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}