
\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}

\newcounter{algocounter}
\newcounter{algocnt}[algocounter]
\newenvironment{ALGORITHM}{}{}

\newenvironment{LIST}{}{}

\newcommand{\FAIL}{}
\newcommand{\STUD}{}
\newcommand{\HARD}{}
\newcommand{\LOOK}{}
\newcommand{\A}{}
\newcommand{\AV}{}
\newcommand{\N}{}
\newcommand{\NP}{}
\newcommand{\PRP}{}
\newcommand{\SS}{}    
\newcommand{\V}{}
\newcommand{\VP}{}

\setcounter{page}{69}
\setcounter{巻数}{3}
\setcounter{号数}{3}
\setcounter{年}{1996}
\setcounter{月}{7}
\受付{1995}{8}{25}
\再受付{1995}{10}{20}
\採録{1995}{11}{28}

\setcounter{secnumdepth}{2}

\title{$\A^*$法に従うアジェンダ制御による構文解析}
\author{吉見 毅彦\affiref{SHARP} \and
Jiri Jelinek\affiref{SHARP} \and
西田 収\affiref{SHARP} \and
田村 直之\affiref{KOBE} \and
村上 温夫\affiref{KONAN}}

\headauthor{吉見 毅彦・Jiri Jelinek・西田 収・田村 直之・村上 温夫}
\headtitle{$\A^*$法に従うアジェンダ制御による構文解析}

\affilabel{SHARP}{シャープ株式会社 情報商品開発研究所}
{Information Systems Product Development Laboratories, SHARP Corporation}
\affilabel{KOBE}{神戸大学 大学院自然科学研究科}
{Graduate School of Science and Technology, Kobe University}
\affilabel{KONAN}{甲南大学 理学部経営理学科}
{Department of Information Systems and Management Science, Faculty of
Science, Konan University}

\jabstract{本稿では，構文解析を探索問題と捉えた上で，$\A^*$法の探索戦
略に従ってチャート法のアジェンダを制御し，最も適切な構文構造から順に必
要なだけ生成する構文解析手法を提案する．
文脈自由文法形式の費用付き構文規則が与えられたとき，規則に従って生成さ
れうる各部分構造について，その構造に相当する現在状態からその構造を構成
要素として持つ全体構造に相当する目標状態までの費用を，構文解析に先立っ
て，$\A^*$法の最適性条件を満たすように推定しておく．
従って，構文解析では，競合する構造のうちその生成費用と推定費用の和が最
も小さいものから優先的に処理していくと，生成費用の最も小さい全体構造が
必ず得られる．
また，優先すべき構造は，個々の規則に付与された費用に基づいて定まるので，
優先すべき構造をきめ細かく指定でき，優先したい構造の変更も規則の費用を
変更するだけで容易に行なえる．
費用付き構文規則は，記述力の点で，確率文脈自由文法規則の拡張とみなすこ
とができる．}

\jkeywords{構文解析，チャート法，$\A^*$法，優先性}

\etitle{Parsing based on $\A^*$ Algorithm Agenda Control}
\eauthor{Takehiko Yoshimi\affiref{SHARP} \and 
Jiri Jelinek\affiref{SHARP} \and
Osamu Nishida\affiref{SHARP} \and
Naoyuki Tamura\affiref{KOBE} \and
Haruo Murakami\affiref{KONAN}}

\eabstract{In this study we propose a method of syntactic analysis
which approaches parsing as a search problem, controls the agenda of
the chart parser following the strategy of $\A^*$ \hspace{0.1mm}algorithm \hspace{0.1mm}and\hspace{0.1mm}
generates \hspace{0.1mm}only \hspace{0.1mm}the \hspace{0.1mm}required \hspace{0.1mm}number \hspace{0.1mm}of \hspace{0.1mm}syntactic \hspace{0.1mm}structures, \hspace{0.1mm}from\\ the
most adequate in descending order of goodness.
Given a set of costed rules of syntactic analysis in CFG form, at the
pre-processing stage, for $\A^*$ to become admissible, every
sub-structure which can be generated by these rules receives an
estimate of the cost from the present state, corresponding to the
sub-structure itself, to the goal state, corresponding to a complete
structure of which this sub-structure is a constituent part.
Then, at the stage of syntactic analysis proper, all competing
structures are processed in the order from the lowest-costing, where
cost is the sum of the estimate and the actual cost of generating the
structure, and thus the lowest-costing structure is guaranteed to be
obtainable.
This method allocates appropriate cost values to each parsing rule.
This makes it possible to prioritize syntactic structures in great
detail and also to modify priorities, if necessary, simply by altering
the cost values.
Costed CFG rules can be seen as extending the descriptive power of
Probabilistic CFG rules.}

\ekeywords{Parsing, Chart Parsing, $\A^*$ Algorithm, Prioritization}

\begin{document}
\maketitle

\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 \le i < 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} \le h$を満たすので，\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-tree sharing)，2)二
つの構造が持つ情報のうち内部構造以外のすべての情報が同じであるとき，
それらの構造を統合する(local ambiguity packing)方法\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 \neq i)$の相対的関係を表す
重みである．
$C_\alpha$は非負の実数，$w_{\beta_i}$\\は正の実数とする．

活性弧
$[\beta_1 \ldots \beta_i\ [?]_{\beta_{i+1}} \ldots [?]_{\beta_{m}}]_\alpha$
($i = m$ならば不活性弧)を生成するための費用は，
不活性弧$\beta_j\ (1 \le j \le i)$を生成するための費用$g_{\beta_j}$に
重み$w_{\beta_j}$をかけたものの和に，規則(\ref{eq:rule})の適用\\費用
$C_\alpha$を加えた値であると定め，次式で計算する．
\begin{equation}
g_\alpha = \sum_{j=1}^i w_{\beta_j} \times g_{\beta_j}  + C_\alpha\ \ (1 \le i \le m)
\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}^m w_{\beta_j} \times \min g_{\beta_j} + C_\alpha & (i = 1 のとき) \\
\min \hat{h}_\alpha + \displaystyle \sum_{j>i}^m w_{\beta_j} \times \min g_{\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}^m w_{\beta_j} \times \min g_{\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$の最小生成費用$\min g_{\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 \times g_\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 \neq j)$ならば，求まった値のうち最小値を不活性
弧$\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 \times g_\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 \times g_\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 \times g_\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 \times g_\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 \times g_\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\hline
S      &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} の推定費用を用いて`failing
student looked hard'を解析する過程を追う．
解析アルゴリズムは，\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\hline
1 & $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\hline
1. &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)レデュース操作同士の競合が生
じた場合には，右辺がより長い構文規則の適用を優先させる，という二つのメ
タレベルの優先方略に従い，右連合(right association)や最小付加(minimal
attachment)などの英語における選好を反映した構造を生成する手法が提案さ
れている\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 \le 1$なる実
数を規則の適用確率として付与したものである．
ただし，左辺の構文範疇が同じである各規則の適用確率の和は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 \le 1$なる実数であり，左辺の構
文範疇が同じである各規則の適用確率の和は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{Jiri Jelinek}{1939年生．
チェコのプラハのUniversita Karlova卒業(言語学・英語学・日本語学)．
1959年以来，日英機械翻訳実験中．
英国Sheffield大学日本研究所専任講師を1996年退職．
現在，シャープ専任研究員．}
\bioauthor{西田 収}{1961年10月19日生．
1984年大阪教育大学教育学部中学校課程数学科卒業，同年より神戸大学工学部
応用数学科の教務補佐員として勤務．
1987年シャープ（株）に入社．
現在は，同社の情報商品開発研究所に所属．
主に，日英機械翻訳，多言語翻訳の研究に従事．
情報処理学会会員．}
\bioauthor{田村 直之}{1957年1月31日生．
1985年神戸大学大学院自然科学研究科システム科学専攻博士課程修了．
学術博士．
同年，日本アイ・ビー・エム(株)に入社し東京基礎研究所に勤務．
1988年神戸大学工学部システム工学科助手．
講師を経て，現在同大学大学院自然科学研究科助教授．
論理型プログラミング言語，線形論理などに興味を持つ．
著書に「Prologプログラミング入門」(オーム社，共著)．
情報処理学会，日本ソフトウェア科学会，システム制御情報学会，ACM，IEEE
各会員．}
\bioauthor{村上 温夫}{1929年生．
1952年大阪大学理学部数学科卒業．
神戸大学理学部助手，講師，教養部助教授を経て，1968年より工学部教授．
この間，University of Kansas客員助教授，University of New South Wales
客員教授，Nanyang University客員教授を併任．
1992年より甲南大学理学部教授．
神戸大学名誉教授．
理学博士(東京大学)．
関数解析，偏微分方程式，人工知能，数学教育などに興味を持つ．
著書に``Mathematical Education for Engineering Students''(Cambridge
University Press)など．
日本数学会，日本数学教育学会，情報処理学会，教育工学会，AMS各会員．}

\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}

\end{biography}

\end{document}
