\documentstyle[epsbox,jnlpbbl]{jnlp_j_b5}

\setcounter{page}{93}
\setcounter{巻数}{6}
\setcounter{号数}{7}
\setcounter{年}{1999}
\setcounter{月}{10}
\受付{1999}{3}{24}
\採録{1999}{4}{25}

\setcounter{secnumdepth}{2}
\setlength{\parindent}{\jspaceskip}

\title{文字クラスモデルによる日本語単語分割}
\author{小田 裕樹\affiref{TUIS}\affiref{NTTSOFT} \and 森 信介\affiref{IBMTRL} \and 北 研二\affiref{TUIS}}

\headauthor{小田, 森, 北}
\headtitle{文字クラスモデルによる日本語単語分割}

\affilabel{TUIS}{徳島大学工学部}
{Faculty of Engineering, Tokushima University}
\affilabel{NTTSOFT}{現在，NTTソフトウェア(株)}
{Presently with NTT Software Corporation}
\affilabel{IBMTRL}{日本アイ・ビー・エム(株)東京基礎研究所}
{Tokyo Research Laboratory, IBM Japan, Ltd.}

\jabstract{
日本語処理において，単語の同定，すなわち文の単語分割は，最も
基本的かつ重要な処理である．
本論文では，日本語文字のクラス分類により得られた文字クラスモデルを
用いる新しい単語分割手法を提案する．
文字クラスモデルでは，推定すべきパラメータ数が文字モデルより
少ないという大きな利点があり，文字モデルより頑健な推定を可能とする．
したがって，文字クラスモデルを単語分割へ適用した場合，
文字モデルよりもさらに頑健な未知語モデルとして機能することが
期待できる．
文字クラスタリングの基準はモデルの推定に用いるコーパスとは別に
用意したコーパスのエントロピーであり，探索方法は貧欲アルゴリズムに
基づいている．このため，局所的にではあるが最適な文字のクラス分類が
クラスの数をあらかじめ決めることなく得られる．
ATR 対話データベースを用いて評価実験を行った結果，
文字クラスモデルを用いた提案手法の単語分割精度は文字モデルによる精度
より高く，特に，文字クラスを予測単位とする可変長 $n$-gram クラスモデルでは
オープンテストにおいて再現率 96.38\%，適合率 96.23\% の高精度を達成した．
}

\jkeywords{単語分割，未知語モデル，文字 $n$-gram モデル，可変長 $n$-gram モデル，文字クラスモデル，文字クラスタリング}

\etitle{A Japanese Word Segmenter by\\
a Character Class Model}
\eauthor{Hiroki Oda\affiref{TUIS}\affiref{NTTSOFT} \and Shinsuke Mori\affiref{IBMTRL} \and Kenji Kita\affiref{TUIS}} 

\eabstract{
Word segmentation, which segments an input sentence into words,
is the most fundamental process of Japanese language processing.
In this paper, we present a new method for Japanese word segmentation
based on a character class model.
The character class model is more robust than a character-based model
because the number of parameters of the character class model
is fewer than that of a character-based model.
The measurement for Japanese character clustering
is the entropy on a corpus different from the corpus for model estimation
and the search method is based on the greedy algorithm.
For this reason, this clustering method gives us
an optimum character classification without giving the number of classes.
As the result of experiments on the ADD (ATR Dialogue Database) corpus,
the proposed Japanese word segmenter using
the character class model marked a higher accuracy
than a character-based model.
In particular,
the proposed method using a variable-length $n$-gram class model
achieved 96.38\% recall and 96.23\% precision for open text.
}

\ekeywords{word segmentation, unknown word model, character-based $n$-gram model, variable-length $n$-gram model, character class model, character clustering}

\begin{document}
\maketitle


\section{はじめに}

日本語や中国語等においては，単語間に空白を入れる習慣がないため，
これらの言語の計算機処理では，まず文を単語列に分割する処理が必要となる．
単語分割は日本語処理における最も基本的かつ重要な技術であり，
精度・速度ともに高い水準の性能が要求される．
単語分割と品詞付けから成る日本語形態素解析法の多くは，
単語辞書の登録語との照合を行い，複数の形態素解析候補がある場合は
ヒューリスティクス (heuristics) を用いて
候補間の順位付けを行うというものである．
しかし，実際に，辞書中にすべての単語を網羅するのは不可能であるため，
未知語 (辞書未登録語) という重大な問題が生ずる．
また，ヒューリスティクスでは扱うことのできない例外的な言語現象の存在や，
例外現象に対処するための規則の複雑化が問題となる．
その結果，一部の規則修正が全体に与える影響を人間が把握することが
困難になり，規則の保守・管理に大きな労力を必要とすることとなる．

一方，英語の品詞付けでは，タグ付きコーパスを用いた確率的手法が
確立されている\cite{Church88,Cutting92,Charniak93}．
言語表現の出現頻度に基づく確率的言語モデルを用いる方法には，
対象領域のテキストからモデルのパラメータを学習する方法が存在する
という大きな利点があり，タグ付きコーパスが整備されている領域では，
実験的に最も高い精度が報告されている．
英語の正書法は単語間で分かち書きするため，これらの手法は，
単語モデル (word-based model) を用いている．
英語の品詞付けは，日本語の単語分割と技術的に似ているため，
英語の品詞付け手法の多くは日本語の単語分割にも適用可能となる．
しかし，単語モデルを日本語に適用するためには，いくつかの問題がある．
日本語では，未知語の存在が単語の同定に影響を与える上，
分割が曖昧で，異なる長さの多くの分割候補があり，それらの
候補を比較する必要がある\cite{Yamamoto97}．
このため，単語モデルを用いるためには，
分割候補の確率を正規化する必要が生じる．

以上の点から，我々は文字モデル (character-based model) に基づく
単語分割法を提案した\cite{Oda99a,Oda99b}．
文字モデルは，未知語モデルとしても機能するために，
学習データに含まれていない単語に対しても対応が可能である．
本論文では，より頑健な単語分割モデルを構築するために，
日本語文字のクラスタリング (グループ化) を行うことを考える．
日本語漢字は表意文字であり，一文字が何らかの意味を担っている．したがって，
何らかの基準によりいくつかのグループ (クラス) に分類することが可能である．
文献\cite{Yamamoto97}で示されている文字モデルの利点に加え，
文字クラスモデルでは，文字モデルよりもさらにモデルのパラメータ数を
少なくすることができるという大きな利点がある．
したがって，より頑健なモデルである文字クラスモデルを
単語分割へ適用した場合，未知語に対する頑健性がさらに向上すると考えられる．

文字とクラスの対応関係を得るためのクラスタリング処理には，
クロス・バリデーション法 (cross-validation) の適用により求められる
平均クロス・エントロピーを言語モデルの
評価基準としたクラスタリング法\cite{Mori97}を用いる．
平均クロス・エントロピーを評価基準として求められた
単語 bigram クラスモデルは，単語 bigram モデルよりも
予測力という点において優れていることが実験的に示されている\cite{Mori97,Mori98}．
本論文では，この方法を日本語文字のクラスタリングに
適用し，文字クラスモデルを構築する．

以下，本論文では，文字クラスモデルに基づく新しい単語分割手法を提案する．
まず，基本となる文字モデルに基づく単語分割モデルについて簡単に説明する．
さらに，類似した文字を自動的にグループ化するクラス分類法について
説明し，文字クラスモデルに基づいた単語分割モデルを提案する．
ADD(ATR Dialogue Database)コーパスを用いた評価実験において，
文字モデルを用いた場合と，文字クラスモデルを用いた場合の単語分割精度を
比較し，提案した手法の評価を行う．

\section{文字モデルに基づく単語分割法}

本節では，文字モデルに基づく単語分割法\cite{Oda99a,Oda99b}について説明する．
まず，言語モデルとして，文字 $n$-gram モデルを用いることを考える．
文字 $n$-gram モデルでは，言語の文字生起は，$(n-1)$ 重マルコフモデルで
近似される．
長さ $l$ の文字列 $c_1^l = c_1 c_2 \cdots c_l$ において，
直前の $(n-1)$ 文字のみが次の文字の生起確率に影響する．
実際によく用いられるモデルは，$n = 2$ あるいは $n = 3$ のモデルであり，
これらは bigram モデル，trigram モデルと呼ばれている．
以下では，$n = 3$ の文字 trigram モデルを用いることで，単語分割モデルの
定式化を行う．

単語分割モデルの学習データとしては，
単語境界位置の付与されたデータを用いる．
図\ref{Fig:training}に学習データの例を示す．
記号 $\langle {\rm d}\rangle$ は単語境界 (単語間のスペース) を表す
特殊記号であり，
$\langle {\rm s}\rangle$ と $\langle {\rm /s}\rangle$ はそれぞれ
文頭と文末を表す特殊記号である．
\begin{figure}[hbt]
\begin{center}
\psbox[width=0.95\textwidth]{training.eps}
\end{center}
\caption{学習データの例}
\label{Fig:training}
\end{figure}

単語境界位置の付与された学習データから文字 trigram モデルの確率値を
推定し，これを用いて単語分割を行う．
与えられた「ベタ書き」文を単語列に分割するためには，
入力文中の各文字位置に対し，その文字の前で単語分割が起こるか
否かを求めればよい．
このために，それぞれの文字位置に対し，2 つの状態 1 と 0 を仮定する．
状態 1 はその文字の前が単語境界となることを表す状態であり，
状態 0 は単語境界とならないことを表す状態である．
文字位置 $i (\ge 2)$ の状態の推定は次式で与えられる．
なお，$P_j(c_1^i)$ は文字列 $c_1^i = c_1 c_2 \cdots c_i$ を生成して
状態 $j$ に到達する確率を表す．
\begin{eqnarray}
\lefteqn{ P_0(c_1^i) = \max(P_0(c_1^{i-1}) A_i,~
	P_1(c_1^{i-1}) B_i)}
	\label{Eq:WordSegMainNoS}\\
\lefteqn{ P_1(c_1^i) = \max(P_0(c_1^{i-1}) C_i,~
	P_1(c_1^{i-1}) D_i)}
	\label{Eq:WordSegMainS}\\[3pt]
 & & A_i = p(c_i|c_{i-2}c_{i-1}) \nonumber\\
 & & B_i = p(c_i|\langle {\rm d}\rangle c_{i-1}) \nonumber\\
 & & C_i = p(\langle {\rm d}\rangle|c_{i-2}c_{i-1}) p(c_i|c_{i-1}\langle {\rm d}\rangle) \hspace{7mm}\nonumber\\
 & & D_i = p(\langle {\rm d}\rangle|\langle {\rm d}\rangle c_{i-1}) p(c_i|c_{i-1}\langle {\rm d}\rangle) \nonumber
\end{eqnarray}
また，文字位置 $i = 1$ の場合は，次式で求めることができる．
\begin{eqnarray}
P_0(c_1) &=& p(c_1|\langle {\rm s}\rangle)
        \label{Eq:WordSegBeginNoS}\\
P_1(c_1) &=& 0
        \label{Eq:WordSegBeginS}
\end{eqnarray}
ここで，学習データ中の文字位置 1 の前には単語境界記号がないため，
式(\ref{Eq:WordSegBeginS})を定義する．

入力文 $s = c_1^m$ に対する最適な単語分割は，
各文字位置に対する状態 1 と 0 の最適な状態遷移系列として
与えられる．
単語分割モデルの計算のため，実際の入力文には，文頭記号と文末記号を
各々 $0$ 番目と $m+1$ 番目の文字として加えて処理を行う．
学習データ中の文末記号 $\langle {\rm /s}\rangle$ の前には
単語境界 $\langle {\rm d}\rangle$ がないので，
最適な状態遷移系列は
\begin{equation}
\max P_0(c_1^{m+1})
\end{equation}
となるような状態遷移系列である．
これを求めるためには，動的計画法の一種である
ビタビ・アルゴリズム (Viterbi algorithm) を用いることができる
(図\ref{Fig:viterbi}参照)．
\begin{figure}[hbt]
\vspace{-2mm}
\begin{center}
\psbox[width=0.70\textwidth]{viterbij.eps}
\end{center}
\caption{ビタビ・アルゴリズムを用いた文の分割}
\label{Fig:viterbi}
\vspace{-6mm}
\end{figure}

求められた最尤状態遷移系列において，状態 1 である文字位置の
前で単語分割を行う．図\ref{Fig:viterbi}において単語境界を点線で示す．
文字 trigram モデルを言語モデルとして用いた場合，以上の単語分割モデル
により，入力文に対して最適な単語分割を求めることができる．

また，同様の考えに基づいて可変長 $n$-gram モデル
(variable-length $n$-gram model) を用いた単語分割を
行うことも可能である\cite{Oda99a,Oda99b}．その場合は，解探索における
単語分割候補の指数的増加を避けるために，各文字位置において
確率の高い候補のみを後続する文字位置での探索に用いるようにする．
もし文字 trigram モデルによる単語分割モデルと同様に，
文字位置 $i$ の直前が単語境界である (状態 1) か否 (状態 0) かの
2 つの仮定に対する各々の最尤解のみに関して解探索を行うならば，
その探索空間は，図\ref{Fig:viterbi} に示す探索空間と同じとなる．

\section{日本語文字のクラスタリング}
\label{Sec:CharClustering}

\subsection{文字 $n$-gram クラスモデル}

$n$-gram モデルに，クラスという概念を導入したモデルを
$n$-gram クラスモデル ($n$-gram class model) と呼ぶ\cite{Brown92}．
ここで，クラスとは $n$-gram モデルの予測単位とする文字(あるいは単語)の
集合を何らかの基準でクラスタリング (クラス分類) したものを指す．
本節では，特に日本語漢字が表意文字であり，一文字が何らかの意味を担っている
ことから，類似した文字を自動的にグループ化することを考える．

文字クラス数は文字数に比べると少ないものとなるので，
文字 $n$-gram モデルよりも文字 $n$-gram クラスモデルの方が
推定すべきパラメータ数が少ないという利点がある．
また，文字クラスモデルは，文字クラスを用いた一種のスムージングであり，
頑健なモデルを構築することが期待できる．
このため，文字 $n$-gram クラスモデルは，文字 $n$-gram モデル
よりも必要な学習データ量が少なく，
たとえ小さな学習データからでも，より信頼性のある確率値を推定する
ことが容易となる．

文字 $n$-gram クラスモデルでは，次の文字を直接予測するのではなく，
先行する文字クラス列から次の文字クラスを予測した上で次の文字を
予測する．ここで，文字が一つのクラスにしか属さないとすると，
文字の生起確率は次の式で表すことができる．
\begin{equation}
P(c_i|c_1^{i-1}) = P(c_i|{\cal C}_i)P({\cal C}_i|{\cal C}_{i-n+1}^{i-1})
\label{Eq:CharClassModel}
\end{equation}
クラス ${\cal C}_i$ は，文字 $c_i$ の属する文字クラスである．
また，確率 $P(c_i|{\cal C}_i)$ は次式により最尤推定できる．
\begin{equation}
P(c_i|{\cal C}_i) = \frac{N(c_i)}{N({\cal C}_i)}
\label{Eq:CharClassProb}
\end{equation}
ここで，$N(c_i)$ は学習データ中で文字 $c_i$ が出現した回数であり，
$N({\cal C}_i)$ はクラス ${\cal C}_i$ の文字が出現した回数である．

さらに，本論文では，未知文字を考慮するために，未知文字のクラスを考える．
未知文字クラスには，学習データ中に出現しない未知文字と，
頻度の小さい文字を含めることとする(未知文字の実例の収集)．
未知文字 $c$ が未知文字クラス ${\cal C}$ から
生起する確率 $P(c|{\cal C})$ は次式により計算することができる．
\begin{equation}
P(c|{\cal C}) = \frac{1}{|A-A_k|}
\label{Eq:UnknownCharClassProb}
\end{equation}
ここで，$A$ は対象言語の文字集合であり，$A_k$ は既知文字集合である．

\subsection{文字クラスタリング法}

クラス分類法には様々なものが提案されている\cite{Brown92}．
優れた文字クラスモデルを獲得するためには，モデルの予測力を向上させる
(すなわちクロス・エントロピーの値を小さくする) 文字とクラスの
対応関係を発見する必要がある．
しかし，クラスタリングに関する多くの先行研究では，確率値の推定に
用いる学習データのエントロピーの値を評価基準とすることでクラスタリングの
優劣を判定している．
学習データのエントロピーを小さく (学習データを高い精度で予測) する
ことを目的とするのであれば，モデルのパラメータ数は多いほど良いこととなる．
したがって，学習データのエントロピーを評価基準としてクラスタリングの
解探索を行う限り，
どのような文字の組合せに対しても複数の文字を同一視することで
必ず情報の損失が生じるため，文字モデルよりもエントロピーの値が小さい
文字クラスモデルは解空間に存在しないこととなる．

以上のように，学習データのエントロピーは，クラスタリングの評価基準と
しては不適切なものであり，
得られた文字クラスモデルが文字モデルより優れた言語モデルで
あることが期待できないという重大な問題が生じる．
実際，文献\cite{Brown92}の手法では，
停止基準として人間が決定する閾値 (クラス数) を導入し，
閾値までパラメータ数を減少させた場合における
最も良い (情報の損失の少ない) 解を
求めているが，得られたモデルの予測力は低下していることが報告されている．

そもそも言語モデルの評価は確率の推定に用いない未知の評価データに
対する予測力によって決められる．
したがって，理想的には，対象言語の未知のデータに対して
クロス・エントロピーを小さくするように文字をグループ化することが望ましい．
以上の点から，文献\cite{Mori97}では，学習データ内の一部を
未知の評価データとして扱い，その評価データのクロス・エントロピーが
小さくなるようにクラス分類を行うアルゴリズムを提案している．
このクラス分類法には，停止基準を評価基準から導き出せるという
利点があり，人間の判断に委ねられる停止基準 (閾値) を必要としない
(詳細に関しては後述する)．
実際に，得られた単語 bigram クラスモデルは単語 bigram モデルよりも
優れた性能を示すことが実験的に報告されている．
そこで，本論文では日本語文字のクラスタリングに文献\cite{Mori97}の手法を
適用することを考える．

\subsubsection{クラスタリングの評価基準}

クラスタリングの評価基準として用いる平均クロス・エントロピーについて説明する．
ここで，
言語モデルの性能尺度であるクロス・エントロピー $H$ は以下の式で定義される．
\begin{equation}
H(M, T) = -\frac{\sum_{i=1}^n \log p_M(s_i)}{\sum_{i=1}^n |s_i|}
\label{Eq:Entropy}
\end{equation}
ここで，$M$ は言語モデル，$s_i$ は評価データ $T$ 中の $i$ 番目の文である．
$|s_i|$ は文 $s_i$ を構成する文字の数とする．
このとき，文区切りを考慮するために，$s_i$ は文末記号までを含むと仮定する．

学習データ内に未知の評価用データを用意して，その評価データにより
クラス分類の性能を評価する．これを実現するために，
削除補間 (deleted interpolation) のように
クロス・バリデーション法 (cross-validation) あるいは
交差検定法と呼ばれる技術を用いる．
クロス・バリデーション法とは，
データの役割を交替しながら繰り返し学習および評価を行う方法のことを指す．
\begin{enumerate}
\item 学習データ $L$ を $m$ 個の部分データ $L_1, L_2, \cdots, L_m$ に分割する．
\item 各部分データ $(i = 1, 2, \cdots, m)$ に対し，ステップ 3, 4 を行う．
\item 学習データから $L_i$ を削除し，残りの $m-1$ 個のデータから
確率値を推定する．
\item 削除されたデータ $L_i$ で，式(\ref{Eq:Entropy})により
クロス・エントロピーの値を計算する．
\end{enumerate}
以上のようにして，$m$ 個のクロス・エントロピーの値を得ることができるので，
それらの値の平均値 $\overline{H}$ (平均クロス・エントロピー)を
全体の評価関数とする．
\begin{equation}
\overline{H} = \frac{1}{m} \sum_{i=1}^m H(M_i, L_i)
\end{equation}
ここで，$M_i$ はステップ 3 で $L_i$ を削除した残りのデータから推定
されたモデルである．

平均クロス・エントロピー $\overline{H}$ は確率推定に用いない
データにおけるクロス・エントロピーの平均値であるため，
文字とクラスの対応関係を変更していくつかの文字を同一視する
ようにした場合，同一視しなかった場合に比べて $\overline{H}$ の値が
増加することもあれば減少することもあるという振舞をみせる．
したがって，クラスタリングの解探索は $\overline{H}$ が
減少する場合のみクラスの変更を施せば良いという極めて自然なものとなる．
以上の $\overline{H}$ の値を最小とする文字とクラスの対応関係を
求めることが，本論文の文字クラスタリングの最終目的となり，
クラスの併合過程においてどのような併合も $\overline{H}$ を
減少させることができない状態に到達することがアルゴリズムの停止条件と
なる．
\vspace{-2mm}
\subsubsection{クラスタリング・アルゴリズム}
\vspace{-1mm}

文字クラスモデルを構築するためには，文字クラスタリングにより
文字とクラスの対応関係を求めることが必要となる．
文字とクラスの対応関係としては，ある文字が一定の確率で複数のクラスに
属するという確率的な関係も考えられるが，解空間が広大になるので，
本論文では，文字は一つのクラスのにみ属することを仮定する．

以下では，文字とクラスの対応関係を返すクラス関数 $f$ を用いて説明する．
たとえば，文字 $c_1$ の属するクラスとして，$f(c_1)=\{c_1, c_2, c_3\}$
を返す．このとき，
文字 $c_2, c_3$ に対するクラス関数 $f$ も，各々の文字が属する
クラスとして同じく文字集合 $\{c_1, c_2, c_3\}$ を返すこととなる．
ここで，クラスタリング対象文字の集合を $A_k$ とすると，$A_k$ 中のすべての
文字のクラス関数 $f$ の和集合は $A_k$ となり，$A_k$ と未知文字クラスの
和集合が対象言語の文字集合 $A$ となる．

さらに，文字のクラス分類に対する解探索を行うために，
文字とクラスの対応関係の変更を表す関数 $move$ を定義する．
移動関数 $move$ は，文字とクラスの関係 $f$ に対して，文字 $c$ をクラス
${\cal C}$ に移動した結果得られる文字とクラスの関係を返す．
文字は唯一のクラスに属するとしているので，$move(f, c, {\cal C})$
は，現在，文字 $c$ が属するクラス $f(c)$ から，集合の要素 $c$ を取り除き，
クラス ${\cal C}$ に要素$c$を加えることを意味する．

文字クラス分類の最適解を求めるためには，あらゆる可能な文字とクラスの
対応関係を調べる必要がある．
クラス分けの総数は有限であるので，理論的には総当たり戦略により
最適なクラスを見つけることはできる．しかし，総当たり法は非現実的で
あるため，準最適なアルゴリズムを用いることとなる．
文献\cite{Mori97}のアルゴリズムを以下に示す．
\vspace{3mm}
\begin{tabbing}
{\bf 文字クラスの学習アルゴリズム}\\
{文字集合 $A_k$ 中の文字を頻度の降順にソートし，$c_1, c_2, \cdots, c_n$ とする}\\
{\bf foreach} {$i  (1, 2, \cdots, n)$}\\
\hspace*{2ex} \= ${\cal C}_i := \{c_i\}$\\
\> $f(c_i) := {\cal C}_i$\\
{\bf foreach} {$i  (2, 3, \cdots, n)$} \+ \\
${\cal C} := {\bf argmin}_{{\cal C} \in \{{\cal C}_1, {\cal C}_2, ..., {\cal C}_{i-1}\}} \overline{H}(move(f, c_i, {\cal C}))$\\
{\bf if} $(\overline{H}(move(f, c_i, {\cal C})) < \overline{H}(f))$ {\bf then} \\
\hspace{2ex} $f := move(f, c_i, {\cal C})$  \-
\end{tabbing}
\vspace{3mm}
上記アルゴリズムはボトムアップ型の探索を行っており，
初期状態において，各文字を各々一つのクラスと
みなしている．後は，頻度の高い文字の順に他のクラスへの文字の移動
を仮定して，平均クロス・エントロピーの値を再計算している．
このとき，平均クロス・エントロピーが減少する文字とクラスの
新しい対応関係が発見できれば，クラス関数 $f$ を変更する．
頻度の高い文字から処理を行う理由は，
頻繁に出現する文字ほどクロス・エントロピーに与える影響が大きいと
考えられるので，早い段階での移動が後の移動によって影響されにくく，
収束がより速くなると考えられるからである．
クラスタリングの処理の例を図\ref{Fig:ClusteringImage}に示す．
\begin{figure}[hbt]
\begin{center}
\psbox[width=0.60\textwidth]{cluster.eps}
\end{center}
\caption{文字クラスタリングの処理の例}
\label{Fig:ClusteringImage}
\end{figure}

\section{文字クラスモデルに基づく単語分割法}
\vspace{-1mm}

文字クラスモデルを言語モデルとして，単語分割を行う．
ここで，\ref{Sec:CharClustering}節の文字クラスタリング法では，
文字と文字クラスの関係が一意に定まることを考えると，
一文を構成する文字列 $c_1^m$ がそのまま文字クラス列 ${\cal C}_1^m$ に
変換できることが分かる．
単語分割モデルでは，入力文の各文字間において単語境界の有無を
仮定して文の生成確率を計算・比較する．
ここで，式(\ref{Eq:CharClassProb}) および式(\ref{Eq:UnknownCharClassProb})
から分かるように，
確率 $p(c_i|{\cal C}_i)$ は単語境界の有無には影響を受けない値である．
さらに，一文を構成する文字は不変であるので，
$\prod_{i=1}^m p(c_i|{\cal C}_i)$ はどのような
分割候補の確率を求める場合でも一定の値の項となる
(式(\ref{Eq:CharClassModel})参照)．
したがって，文字 trigram クラスモデルによる単語分割モデルでは，
以下のようにクラス連鎖の確率のみを用いて簡単に計算することができる．
\begin{eqnarray}
\lefteqn{ P_0(c_1^i) = \max(P_0(c_1^{i-1}) A_i,~
	P_1(c_1^{i-1}) B_i)}
	\label{Eq:ClassWordSegMainNoS}\\
\lefteqn{ P_1(c_1^i) = \max(P_0(c_1^{i-1}) C_i,~
	P_1(c_1^{i-1}) D_i)}
	\label{Eq:ClassWordSegMainS}\\[3pt]
 & & A_i = p({\cal C}_i|{\cal C}_{i-2}{\cal C}_{i-1}) \nonumber\\
 & & B_i = p({\cal C}_i|\langle {\rm d}\rangle {\cal C}_{i-1}) \nonumber\\
 & & C_i = p(\langle {\rm d}\rangle|{\cal C}_{i-2}{\cal C}_{i-1}) p({\cal C}_i|{\cal C}_{i-1}\langle {\rm d}\rangle) \hspace{7mm}\nonumber\\
 & & D_i = p(\langle {\rm d}\rangle|\langle {\rm d}\rangle {\cal C}_{i-1}) p({\cal C}_i|{\cal C}_{i-1}\langle {\rm d}\rangle) \nonumber
\end{eqnarray}
また，文字位置 $i = 1$ の場合は，次式で求めることができる．
\begin{eqnarray}
P_0(c_1) &=& p({\cal C}_1|\langle {\rm s}\rangle)
	\label{Eq:ClassWordSegBeginNoS}\\
P_1(c_1) &=& 0
	\label{Eq:ClassWordSegBeginS}
\end{eqnarray}

上記の単語分割モデルをみれば分かるように，
文字クラスモデルを用いた場合は，
文字クラスの連鎖により単語境界を予測するという問題に置き換わる．
文字 trigram クラスモデルを用いた場合も，
$\max P_0(c_1^{m+1})$ となる状態遷移系列をビタビ・アルゴリズムを
用いて求めることで，入力文に対する最適な単語分割を得ることができる
(図\ref{Fig:viterbi}参照)．
また，可変長 $n$-gram クラスモデルを用いる場合でも，同様に，
クラス連鎖における単語境界の出現の有無により確率比較を行い，
解探索を行うこととなる．

\section{評価実験}

以上で提案した手法を評価するために，
ATR 対話データベースを用いた評価実験を行った．
それぞれのデータの文数，単語数，文字数を表\ref{Tab:datasize}に示す．
\begin{table}[hbt]
\begin{center}
\caption{学習データと評価データのサイズ}
\label{Tab:datasize}
\begin{tabular}{l|r|r}
\hline
\hline
 & 学習データ & 評価データ\\
\hline
文数 & 11,430 & 1,267\\
\hline
単語数 & 155,553 & 17,829\\
\hline
文字数 & 278,771 & 31,450\\
\hline
\end{tabular}
\end{center}
\end{table}

\subsection{文字クラスモデルのクロス・エントロピー評価}

前節の単語分割モデルで用いる文字クラスモデルを作成する．
したがって，文字 trigram クラスモデルや
可変長 $n$-gram クラスモデルの予測力を改善するような
文字クラスを求める必要がある．
しかし，文字クラスタリング・アルゴリズムの評価基準である
平均クロス・エントロピーの計算を考えると，
高次のモデルでは，必要な記憶容量と計算時間が大きな問題となる．

そこで，本実験では，クロス・エントロピーの計算は，
低次の bigram 確率によって計算した．
bigram モデルであれば，高速なクラスタリング処理が可能である．
もし日本語における文字分類の最適解に近い解を得ることができれば，
得られたクラス関数 $f$ はどのような次数のモデルに対しても
ある程度有効であると考えられる．

また，本論文では，日本語文字が明らかに字種によって分類できることから，
クラスタリング処理において，字種により規制を設けることを考えた．
たとえば，漢字は漢字同士でグループ化するというように考えることで，
文字とクラスの対応関係の変更を考える場合に
必要な計算量を少なくすることができる．これにより，
漢字の場合は $move$ 関数の移動先クラスとして漢字のクラスのみを
考えることとなり，
ひらがなの場合はひらがなのクラスのみとなる．

以上の条件により，
文字クラスタリングを行うために，学習データを 9 個のデータ
$L_1, L_2, \cdots, L_9$ に分割した．ここで，1 個のデータにしか出現しない
文字は未知文字とし，字種ごとに未知文字クラスを用意した．
これは，クロス・バリデーション法による
平均クロス・エントロピーの計算 (9 回の評価) において
未知文字であった文字をそのまま学習データ全体における未知文字の
実例の収集に用いることを意味する．
したがって，クラスタリングの対象となる文字は，2 個以上のデータに
出現する文字となる．
また，単語分割に用いる言語モデルを獲得することを念頭におくため，
単語間に単語境界記号を挿入した分かち書きデータを用いた．
単語境界記号自体はクラスタリングの対象ではないが，
その存在により，
クロス・エントロピー評価では単語境界(単語間のスペース)まで考慮するようになる．

本実験において，評価データ中の未知文字(クラスタリング対象文字以外)は
字種ごとに異なる特別な記号に置き換えてクロス・エントロピーの計算を行った．
未知文字の扱いは文字モデルと文字クラスモデルで共通であるので，
未知文字の確率はモデルの比較においては問題とならない．
重要なことは，クラスタリング対象文字のグループ化によって，
モデルの予測力がどのように変化するかである．
以上の点から，モデルの状態は，既知文字すべて(もしくは文字クラスすべて)，
未知文字クラス(字種ごと)，単語境界，文区切りの各々に対応することとなる．
実験により得られた，文字 bigram モデルと文字 bigram クラスモデルの
クロス・エントロピーを表\ref{Tab:CrossEntropy}に示す．
\begin{table}[hbt]
\begin{center}
\caption{言語モデルのクロス・エントロピー}
\label{Tab:CrossEntropy}
\begin{tabular}{l|r}
\hline
\hline
言語モデル & \multicolumn{1}{c}{$H$}\\
\hline
文字bigramモデル & 3.5980\\
文字bigramクラスモデル & 3.5591\\
\hline
\end{tabular}
\end{center}
\end{table}

本実験において，文字クラスモデルのクロス・エントロピーは
文字モデルのものよりも小さく，より予測力の高い言語モデルの
獲得に成功している
\footnote{
単語間のスペースを考慮しない「ベタ書き」の日本語データを用いた
実験では，
クロス・エントロピーは，文字 bigram モデルでは 4.3563 ビット，
文字 bigram クラスモデルでは 4.3060 ビット
であり，同様に，文字クラスモデルのほうが一文字当たりのクロス・エントロピーが
小さいという結果が得られている．
}．
また，表\ref{Tab:CharClassParameters}に，クラスタリング対象文字数
とそれらをクラスタリングした後の文字クラス数を示す．
学習データ中には，1357 種類の文字が含まれていたが，
約 200 種類の低頻度文字が未知文字として取り扱われた．
実験の結果，クラス当たりの平均要素(文字)数は 1.36 文字であり，
最大のクラスの所属文字数は 12 文字であった．
\begin{table}[hbt]
\begin{center}
\caption{文字数と文字クラス数の比較}
\label{Tab:CharClassParameters}
\begin{tabular}{l||r|r}
\hline
\hline
 & \multicolumn{1}{|c|}{既知文字数} & \multicolumn{1}{c}{文字クラス数}\\
\hline
漢字 & 935 & 675\\
ひらがな & 70 & 67\\
カタカナ & 78 & 71\\
数字 & 10 & 8\\
英字 & 42 & 13\\
記号 & 23 & 15\\
\hline
合計 & 1,158 & 849\\
\hline
\end{tabular}
\end{center}
\end{table}

文字クラスタリング実験により得られたクラス関数 $f$ が返す
文字集合 (文字クラス) を，図\ref{Fig:ExampleCharClass}にいくつか示す．
必ずしもすべての文字クラスが言語直観から納得がいくものではないが，
いくつかのノイズと思われる文字を除けば，(特に出現位置の類似という点で)
ある程度良い解が得られていることが分かる．
不自然な印象を受ける文字のグループが存在するのは，
あくまで bigram クラスモデルの改善における準最適解を求めている
からであると考えられる．
\begin{figure}[hbt]
\{ 送, 乗, 居, 貼 \}
\{ 私, 誠, 娘, 又 \}
\{ 思, 誓 \}
\{ 今, 昨 \}
\{ 部, 型 \}
\{ 中, 低 \}
\{ 他, 皆, 僕 \}\\
\{ 原, 松, 草 \}
\{ 山, 竹, 塚, 吉 \}
\{ 別, 誰 \}
\{ 特, 既 \}
\{ 忙, 楽 \}
\{ 近, 多, 暗\}
\{ 渡, 貸, 探, 押 \}\\
\{ 朝, 昼 \}
\{ 市, 職, 命, 履 \}
\{ 安, 幸 \}
\{ 図, 計, 義 \}
\{ 島, 木, 川, 根 \}
\{ 食, 刻, 飯 \}
\{ 帰, 困 \}\\
\{ 女, 性 \}
\{ 校, 化, 枠, 郊 \}
\{ 映, 厳, 撮 \}
\{ 含, 休, 混 \}
\{ 購, 納 \}
\{ 離, 訪 \}
\{ 項, 故 \}\\
\{ 戸, 宮 \}
\{ 欄, 横, 机, 縦, 層, 逆 \}
\{ 界, 株, 財 \}
\caption{実験により得られた文字クラスの例}
\label{Fig:ExampleCharClass}
\end{figure}

本実験では，各文字クラスに属する文字数は少なく，
文字クラスタリングによって，
それほど極端にパラメータ数が減少するということにはならなかった．
この原因は，今回用いたコーパスの規模が小さく，学習データに
含まれる文字の種類が少なかったためであると考えられる．
より多くの文字種をクラスタリングの対象とすれば，
モデルのパラメータ数の減少度はさらに大きくなるであろう．

\subsection{単語分割精度の比較評価}
\vspace{-1.5mm}
文字クラスタリング実験により得られたクラス関数 $f$ を用いる
ことで，文字 trigram クラスモデルや可変長 $n$-gram クラスモデルを
構築することができる．
ここで，文字クラスタリングでは字種別にグループ化を行ったので，
単語分割に用いる文字クラスモデルを作成するときに，
クラス関数 $f$ を用いる字種を限定してみることについても
試みることとした．
もしあまり有効でない文字のグループ化が行われている字種が
あれば，それらの文字はクラス関数 $f$ を用いず，文字を予測単位
として処理すれば，より性能の良いモデルが得られる可能性がある．

また，本論文で提案した文字クラスモデルに基づく単語分割モデルは非常に
簡単な構造となっており，いかにクラス連鎖により単語境界の
生起を把握するかが単語分割精度の鍵となる．
ここで，字種変化によるヒューリスティクスを考慮した場合，
カタカナ，数字，英字はその字種同士の文字間では分かち書きされる
可能性がほとんどないと考えられる．
単語分割を行う場合，これらの文字は単にカタカナか数字か英字である
という情報のみでモデル化したほうが良い結果が得られる可能性がある．
そこで，それらの字種に関しては字種全体を一つのクラスとみなして
同一視することについても検討することとした．

以上の点から，文字クラスモデルと文字モデルの比較において，
表\ref{Tab:ClusteringCondition}の 5 つのモデルを考え，単語分割実験を
行った．表中には，字種ごとに何を予測単位としてモデル化を行うかを示している．
モデル 1 は文字モデルであり，モデル 2 は文字クラスタリングの結果に
何も手を加えず
に，すべての文字でクラス関数 $f$ を用いた文字クラスモデルである．
モデル 3, 4, 5 は字種クラス
(字種全体を一つのクラスとする) を予測単位と
することを試みたモデルであり，それらの中のモデル 4 とモデル 5 では
文字クラスタリングの結果得られるクラス関数 $f$ を用いる文字を限定している．
\begin{table}[hbt]
\begin{center}
\caption{字種ごとに予測単位を使い分けることを仮定したモデル}
\label{Tab:ClusteringCondition}
{\tabcolsep 1.5mm
\begin{tabular}{c||llllll}
\hline
\hline
モデル & 漢字 & ひらがな & カタカナ & 数字 & 英字 & 記号\\
\hline
1 & 文字 & 文字 & 文字 & 文字 & 文字 & 文字\\
\hline
2 & クラス & クラス & クラス & クラス & クラス & クラス\\
\hline
3 & 文字 & 文字 & 字種 & 字種 & 字種 & 文字\\
\hline
4 & クラス & クラス & 字種 & 字種 & 字種 & クラス\\
\hline
5 & クラス & 文字 & 字種 & 字種 & 字種 & 文字\\
\hline
\end{tabular}
}
\end{center}
\end{table}
\vspace{-2mm}


表\ref{Tab:PerformanceTrigram}に，
文字 trigram モデルと文字 trigram クラスモデル
に基づく単語分割モデルによる単語分割精度を示す．
単語分割の性能は，再現率({\it recall})と適合率({\it precision})
により評価する\cite{Nagata94}．
ここで，Std をコーパス中の単語数，Sys を本手法で分割された単語数，
M を照合した単語数とすると，再現率は ${\rm M}/{\rm Std}$ ，
適合率は ${\rm M}/{\rm Sys}$ で表される．
\begin{table}[hbt]
\begin{center}
\caption{trigram モデルと trigram クラスモデルによる単語分割精度}
\label{Tab:PerformanceTrigram}
{\tabcolsep 1.5mm
\begin{tabular}{c||c|c|c|c}
\hline
\hline
 & \multicolumn{2}{|c|}{クローズドテスト} & \multicolumn{2}{c}{オープンテスト}\\
\cline{2-5}
モデル & 再現率 & 適合率 & 再現率 & 適合率\\
\hline
1 & 98.10\% & 98.56\% & 95.48\% & 94.11\%\\
2 & 98.09\% & 98.56\% & 95.83\% & 94.34\%\\
3 & 97.82\% & 98.44\% & 95.91\% & 94.73\%\\
4 & 97.80\% & 98.43\% & 95.86\% & 94.70\%\\
5 & 97.83\% & 98.44\% & 96.01\% & 94.74\%\\
\hline
\end{tabular}
}
\end{center}
\end{table}

本実験では，バックオフ・スムージング\cite{Katz87}
付きの trigram 確率値を計算した．
表\ref{Tab:PerformanceTrigram}のモデル 1 とモデル 2 は
文字 trigram モデルと文字 trigram クラスモデルの精度であるが，
オープンテストにおいて文字クラスモデルの精度が上回る結果となっている．
また，モデル 1 とモデル 3 およびモデル 2 とモデル 4 の
オープンテストの結果を比較することで，
カタカナ，数字，英字を各々一つのクラスとしたほうが
未知語を含むデータに対して，精度が向上していることが分かる．
したがって，字種単位でのグループ化の有効な字種の存在が確認できた．
全体として，オープンテストでは，漢字に関して文字クラスを用いたモデル 5 の
場合が最も高精度であった．
本実験結果より，文字クラスタリングの動機であった漢字のクラスタリング
には特に良い解が得られていることが分かる．

また，可変長 $n$-gram モデル\cite{Oda99a,Oda99b}と
可変長 $n$-gram クラスモデルの比較に関する単語分割実験も行ったが，
trigram 同様，クラスモデルの方が高精度であった．
本実験において，可変長 $n$-gram クラスモデルによる探索空間は
trigram による場合と同じものとした．
文献\cite{Oda99b}において，trigram モデルによる探索空間と同じ
場合に最も高い精度を達成している可変長 $n$-gram モデルを用いた
場合の結果を表\ref{Tab:PerformancePPMBackOff}に示す．
実験結果から，可変長 $n$-gram クラスモデルは trigram クラスモデル
よりもさらに高い単語分割精度を達成できることが分かる．
学習データと評価データの組を変更して，
可変長 $n$-gram クラスモデルによる単語分割の再評価を行ったところ，
オープンテストで 96\% 〜 98\% 以上のかなりの高精度を達成することを確認した．
パラメータ数の少ない文字クラスモデルでは，
本論文で用いたような比較的小規模の学習データからでも信頼のおける確率値を
得ることが容易となり，有効な未知語モデルとして機能できることが結論できる．
\begin{table}[hbt]
\begin{center}
\caption{可変長 $n$-gram モデルと可変長 $n$-gram クラスモデルによる単語分割精度}
\label{Tab:PerformancePPMBackOff}
{\tabcolsep 1.5mm
\begin{tabular}{c||c|c|c|c}
\hline
\hline
 & \multicolumn{2}{|c|}{クローズドテスト} & \multicolumn{2}{c}{オープンテスト}\\
\cline{2-5}
モデル & 再現率 & 適合率 & 再現率 & 適合率\\
\hline
1 & 99.51\% & 99.71\% & 95.89\% & 95.91\%\\
2 & 99.50\% & 99.71\% & 96.30\% & 96.04\%\\
3 & 99.42\% & 99.68\% & 96.20\% & 96.15\%\\
4 & 99.38\% & 99.67\% & 96.27\% & 96.17\%\\
5 & 99.42\% & 99.69\% & 96.38\% & 96.23\%\\
\hline
\end{tabular}
}
\end{center}
\end{table}

\section{おわりに}

本論文では，日本語のような単語間で分かち書きをしない言語のための
新しい単語分割モデルを提案した．入力文に対して最適な単語分割を見つける
ために，本手法は文字クラスモデルを言語モデルとして用いる．
ADD コーパスを用いた評価実験で，
クロス・エントロピー評価によるクロス・バリデーション法を適用した
文字クラスタリングを行い，モデルのパラメータ数を減少させた上で，
優れた予測力を持つ頑健な文字クラスモデルを獲得できることを示した．
また，提案した単語分割モデルにおいて，
文字モデルを用いた場合と，文字クラスモデルを用いた場合の
単語分割精度の比較を行い，文字クラスモデルによる単語分割モデルの方が
未知語を含むデータに対する解析力が優れていることを示した．

今後は，文字クラスモデルの有効性をさらに確認するために，高次のクラス
モデルの性能を直接改善するようなクラスタリング実験を行うことを考えている．
また，より多くの文字種を含む大規模コーパスでの文字クラスモデルの
クロス・エントロピーおよびパラメータ数の減少度を計測し，その有効性を
確認することを予定している．


\bibliographystyle{jnlpbbl}
\bibliography{v06n7_05}

\begin{biography}
\biotitle{略歴}
\bioauthor{小田 裕樹}{
1975年生．1997年徳島大学工学部知能情報工学科卒業．
1999年同大学大学院博士前期課程修了．
同年，NTTソフトウェア(株)入社．
在学中，確率・統計的自然言語処理の研究に従事．
現在，自然言語処理，情報検索等の研究開発支援に従事．
情報処理学会会員．
}
\bioauthor{森 信介}{
1970年生．1995年京都大学大学院工学研究科修士課程修了．
1998年同大学大学院博士後期課程修了．
同年，日本アイ・ビー・エム(株)入社．
東京基礎研究所において計算言語学の研究に従事．
工学博士．1997年情報処理学会山下記念研究賞授賞．
情報処理学会会員．
}
\bioauthor{北 研二}{
1957年生．1981年早稲田大学理工学部数学科卒業．
1983年から 1992年まで沖電気工業(株)勤務．
この間，1987年から 1992年まで ATR 自動翻訳電話研究所に出向．
1992年 9月から徳島大学工学部勤務．現在，同助教授．工学博士．
確率・統計的自然言語処理，情報検索等の研究に従事．
情報処理学会，電子情報通信学会，日本音響学会，日本言語学会，
計量国語学会，ACL 各会員．
}

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

\end{biography}

\end{document}

