\section{はじめに}
\label{sec:intro}ある程度の長さの文章は，一般的に，複数のトピックからなる．そのような文章を切り分けて，それぞれの切り分けた部分が一つのトピックになるようにすることを，テキスト分割と呼ぶ．テキスト分割は，情報検索や要約などにおいて重要である．まず，情報検索においては，文書全体ではなく，ユーザの検索要求を満す部分(トピック)だけを検索した方が効果的である\cite{hearst93:_subtop_struc_full_lengt_docum_acces,salton96:_autom_text_decom_using_text,mochizuki2000}．また，要約においては，長い文書をトピックに分ければ，それぞれのトピックごとに要約を作成することにより，文書全体の要約を作成できるし，重要なトピックだけを選んで要約を作成することもできる\cite{kan98:_linear_segmen_segmen_signif,nakao00:_algor_one_summar_long_text}．これらの目的のために，多くの手法が研究されている\cite[など]{kozima93:_text_segmen_simil_words,hearst94:_multi_parag_segmen_expos_text,okumura94:_word_sense_disam_text_segmen,salton96:_autom_text_decom_using_text,yaari97:_segmen_expos_texts_hierar_agglom_clust,kan98:_linear_segmen_segmen_signif,choi00:_advan,nakao00:_algor_one_summar_long_text,mochizuki2000}．これらの手法の主な共通点は，これらの手法が，分割対象のテキスト(および辞書やシソーラス)しか分割に利用しないことである．たとえば，\cite{hearst94:_multi_parag_segmen_expos_text}は，テキスト内の単語分布の類似度しか分割に利用しない．言い換えれば，これらの手法は，その手法をテキスト分割に使用するにあたって，訓練データを必要としない．そのため，これらの手法は，訓練データの存在する分野に限られることなく，どんな分野の文章でも分割対象とすることができる．この点は重要である．なぜなら，情報検索や要約が対象とする文書は，分野を限定しない文書であるので，そのような文書に対応するためには，分野を限定しないテキスト分割の手法が必要であるからである．本稿で述べる手法も，これらの従来手法と同様に，訓練データを利用せずに，テキスト内の単語分布のみを利用してテキストを分割する．我々が，訓練データを利用しないテキスト分割手法を採用した理由は，我々が，テキスト分割の結果を利用して，長い文書を要約したり，講演のディクテーション結果を要約することを目的としているからである．そのためには，分野を限定しない(訓練データを利用しない)テキスト分割の方法が必要であるからである．本稿で述べる手法は，テキストの分割確率が最大となるような分割を選択するというものである．このようなアプローチは，分野を限定しないテキスト分割としては，新しいアプローチである．なお，従来の研究で，分野を限定しないテキスト分割の研究では，主に，語彙的な結束性を利用してテキストを分割している．その例としては，意味ネットワーク上での活性伝播に基づく結束性を利用するもの\cite{kozima93:_text_segmen_simil_words}や，単語分布の類似度(コサイン)を結束性としたもの\cite{hearst94:_multi_parag_segmen_expos_text}や，単語の繰り返し状況に基づいて結束性を計るもの\cite{reynar94:_autom_method_findin_topic_bound}や，文間の類似度としてコサインを直接使うのではなくコサインの順位を結束性の指標とするもの\cite{choi00:_advan}などがある．なお，テキスト分割の方法としては，訓練データを利用しない(分野を限定しない)方法の他に，訓練データを利用する方法もある．そのような方法の応用としては，複数ニュースを個々のニュースに分割するものがある\cite{allan98:_topic_detec_track_pilot_study_final_repor}．この場合には，分野が明確であり，また，訓練データも多量にあるので，訓練データを利用したシステムにより，ニュースの境界を推定し分割する手法が主流である\cite[など]{mulbregt98:_hidden_markov_model_approac_text,beeferman99:_statis_model_text_segmen}．しかし，そのような方法は，訓練データが利用できない分野については適用できないので，我々の目的である，テキスト分割の結果を利用して，長い文書を要約したり，講演のディクテーション結果を要約するためのテキスト分割手法としては適さない．以下，\ref{sec:model}章では，テキスト分割のための統計的モデルを述べ，\ref{sec:algorithm}章で，最大確率の分割を選択するアルゴリズムを述べる．\ref{sec:experiments}章では，まず，我々の手法を公開データに基づいて評価することにより，我々の手法が他の手法よりも優れた分割精度を持つことを示し，次に，我々の手法を長い文書に適用した場合の分割精度を述べる．\ref{sec:discussion}章は考察，\ref{sec:conclusion}章は結論である．
\section{テキスト分割のための統計的モデル}
\label{sec:model}本章では，テキストの分割結果の確率を定義し，それを用いて最大確率であるような分割を定義する．そして，次章で，最大確率であるような分割を選ぶアルゴリズムを示す．本章では，テキスト$W$が与えられたときに，その任意の分割$S$に対して，条件付き確率$\Pr(S|W)$を定義する．$\Pr(S|W)$は，テキスト$W$を条件とする分割$S$の条件付き確率であるので，この値が最大の分割$\hat{S}$を選ぶことにより，$W$が指定された場合の最大確率の分割$\hat{S}$を選ぶことができる．このような分割$\hat{S}$は，テキスト$W$の本来の分割の推定として適当であると考えられる．まず，$n$個の延べ単語からなるテキスト$W=w_1w_2\ldotsw_n$が与えられたとき，$m$個の区間からなる分割$S=S_1S_2\ldotsS_m$の確率$\Pr(S|W)$は，\begin{equation}\label{eq:PrSW}\Pr(S|W)=\frac{\Pr(W|S)\Pr(S)}{\Pr(W)}\end{equation}である．ここで，$\Pr(W|S)$と$\Pr(S)$については，詳しくは，以下で定義するが，$\Pr(W|S)$は，分割$S$が与えられたときに，テキスト$W$が生起する確率であり，$\Pr(S)$は，分割$S$の確率である．また，$\Pr(W)$は，テキスト$W$の確率であるが，これは，$W$が与えられているときには，定数であるから，最大確率の分割を求める際には無視できる．よって，最大確率の分割$\hat{S}$は，\begin{equation}\label{eq:hatS}\hat{S}=\arg\max_S\Pr(W|S)\Pr(S)\end{equation}である．以下では，$\hat{S}$を最適分割と呼ぶことにする．次に，\ref{sec:PrWS}節で$\Pr(W|S)$を定義し，\ref{sec:PrS}節で$\Pr(S)$を定義する．\vspace{3pt}\subsection{$\Pr(W|S)$の定義}\label{sec:PrWS}区間$S_i$に$n_i$個の延べ単語があるとして，$S_i$中の$j$番目の単語を$w^i_j$とし，$W_i=w^i_1w^i_2\ldotsw^i_{n_i}$とする．つまり，$S_i$と$W_i$とを一対一に対応させる．このようにすると，$n=\sum_{i=1}^mn_i$，$W=W_1W_2\dotsW_m$である．このとき，ある区間に属する単語列は，その他の区間には独立に生起するとし，更に，同一区間に属する単語も，区間が与えられているという条件下では確率的に独立であるとすると，\begin{eqnarray}\label{eq:PrWSexpand}\Pr(W|S)&=&\Pr(W_1W_2\ldotsW_m|S)\nonumber\\&=&\prod_{i=1}^m\Pr(W_i|S)\nonumber\\&=&\prod_{i=1}^m\Pr(W_i|S_i)\nonumber\\&=&\prod_{i=1}^m\prod_{j=1}^{n_i}\Pr(w^i_j|S_i)\end{eqnarray}である．この式の，2行目と3行目は，「ある区間に属する単語列は他の区間とは独立に生起する」という仮定から変形でき，最後の行は，「同一区間に属する単語は，その区間が与えられているという条件では，その他の単語と確率的に独立である」という仮定から変形できる．また，$\Pr(W_i|S_i)$は，区間$S_i$で単語列$W_i$が生起する確率であり，$\Pr(w^i_j|S_i)$は，区間$S_i$で単語$w^i_j$が生起する確率である．次に，$W$中における異なり単語の数を$k$，$W_i$において$w^i_j$と同じ単語\footnote{トークンとしては異なるがタイプとしては同じということである．たとえば，$W_i=aababab$のとき，$W_i$中には，同一タイプである$a$が異なるトークンとして4回出現する．よって，$f_i(a)=4$である．}の数を$f_i(w^i_j)$とし，\begin{equation}\label{eq:PrwS}\Pr(w^i_j|S_i)\equiv\frac{f_i(w^i_j)+1}{n_i+k}\end{equation}と定義する．ここで，(\ref{eq:PrwS})式は，ラプラス推定(Laplace'slaw)と呼ばれる確率推定式\cite{manning99:_found_statis_natur_languag_proces}である\footnote{確率推定のその他の方法の一つとして最尤推定がある．最尤推定の場合には，$\Pr(w^i_j|S_i)\equiv\frac{f_i(w^i_j)}{n_i}$と推定できるが，最尤推定の推定精度は，一般に，観測事象の数(この場合には$n_i$)が大きくないと良くないことが知られており，観測事象の数が少ないときには，何らかのスムージングが必要である．ラプラス推定は，そのようなスムージング方法の一つである．たとえば，最尤推定によると，ある区間$S_i$に一回も出現しない単語の確率は，$\frac{0}{n_i}=0$と推定されるが，ラプラス推定では，一回も出現しない単語についても，$\frac{0+1}{n_i+k}>0$の確率が割当てられる．}．なお，$f_i(w^i_j)$は，厳密には，次式で定義される．\begin{eqnarray}\label{eq:f}f_i(w^i_j)\equivg(w^i_j|w^i_1w^i_2\ldotsw^i_{n_i})\end{eqnarray}\begin{eqnarray}\label{eq:g}g(w^i_j|w^i_1w^i_2\ldotsw^i_{n_i})\equiv\sum_{k=1}^{n_i}\delta(w^i_k,w^i_j).\end{eqnarray}ただし，$\delta$については，単語$a$と単語$b$とが同じとき$\delta(a,b)=1$，そうでないとき，$\delta(a,b)=0$である．\subsection{$\Pr(S)$の定義}\label{sec:PrS}分割$S$に対する事前確率$\Pr(S)$の定義に関しては，任意性が大きい．たとえば，同じ区間数からなる分割であっても，各区間の長さが揃っている分割の方を，長さが不揃いの分割よりも優先したい場合には，長さが揃っている分割の事前確率を大きくすべきである．しかし，ここでの我々の仮定は，そのような優先すべき分割がないというものであるので，そのような優先すべき分割を前提としないような事前確率を設定しなくてはならない．我々は，事前確率$\Pr(S)$の設定において，\cite{stolcke94:_best_model_mergin_hidden_markov_model_induc}と同様に，記述長にもとづく事前確率を与えることにした．以下では，分割確率最大化とMDL(MinimumDescriptionLength,最小記述長)原理\cite{yamanishi92}との関係について極く簡単に述べ，その後で，記述長に基づいた$\Pr(S)$の設定について述べる．なお，MDL原理とは，「与えられたデータを，モデル自身の記述も含めて最も短く符号化できるような確率モデルが最良のモデルである」と主張するものである．\subsubsection{分割確率最大化とMDL原理との関係}我々は，確率最大であるような分割を得るために，(\ref{eq:hatS})式の右辺にある\begin{equation}\Pr(W|S)\Pr(S)\end{equation}を最大化しようとしているが，これは，\begin{equation}-\log\Pr(W|S)-\log\Pr(S)\end{equation}を最小化しようとしていることと等価である．このことは，MDL原理の観点からは，分割$S$が与えられたときのテキスト$W$の記述長$-\log\Pr(W|S)$と，分割$S$の記述長$-\log\Pr(S)$との和を最小化しようとしていることになる．なぜなら，一般に，ある事象$X$の確率が$\Pr(X)$のときには，$X$を記述(符号化)するために必要な最小記述長は$-\log\Pr(X)$であるからである．ただし，ここで，$\log$の底は2である．このように，最小記述長であるような分割を選択することと，最大確率であるような分割を選択することとは同等である．\vspace{5pt}\subsubsection{記述長に基づく事前確率}以上の議論の逆から言えば，分割$S$に対して，適当な記述長$l(S)$を割当てた場合には，その記述長を利用して，\begin{equation}\label{eq:dl}\Pr(S)=2^{-l(S)}\end{equation}と定義できる\footnote{このように定義した場合，全ての分割$S$に対する$\Pr(S)$の和は1以下となる．つまり，$\sum_{S}\Pr(S)\le1$となる\cite{yamanishi92}．}．なぜなら，$l(S)=-\log\Pr(S)$であるからである．つまり，分割$S$の記述長を求めることにより，その事前確率を求めることができる．よって，以下では，分割$S$の記述長を求めることにより，その事前確率を求めることにする．ここで，我々に，既に，分割対象のテキストが与えられているとすると，分割$S$を指定するために必要な情報は，各区間の長さ，$n_1,n_2,\ldots,n_m$のみである．たとえば，我々に，既に，$W=abcdefghi$という長さが9のテキストが与えられていると仮定すると，そのテキストの分割を指定するためには，たとえば，2,3,3,1という4つの数字からなる数字列を指定すればよい．そうすれば，$W$を$W=[ab][cde][fgh][i]$のように4分割できる．つまり，我々は，$m$個の区間からなる分割を指定(記述)するためには，$m$個の数字を指定すれば良い．次に，これらの個々の数字は，1以上$n$以下の$n$個のうちの一つであることに注意すると，これらの個々の数字は，$1/n$の確率で選択されると考えることができるので，$\logn$の記述長で記述できる．よって，$m$個の数字を記述するためには，$m\logn$の記述長があれば良い．以上より，$l(S)=m\logn$と計算できる\footnote{このような$m$個の数字を記述するための記述長には，いくつかの変種がある．それらについては，\cite{stolcke94:_best_model_mergin_hidden_markov_model_induc}を参照のこと．}．そのため，$\Pr(S)$は\begin{equation}\label{eq:PrM}\Pr(S)\equivn^{-m}\end{equation}と定義できる．一般的にいって，$\Pr(S)$の値は，分割数が小さいほど大きな値を取る．一方，$\Pr(W|S)$の値は，分割数が大きいほど大きな値を取る．そのため，もし，分割を推定するのに，$\Pr(W|S)$だけを利用した場合には，推定される分割結果は，分割数が大きい分割，すなわち，細かすぎる区間からなる．それに対して，$\Pr(S)$と$\Pr(W|S)$の両方を利用した場合には，両者のバランスの取れた分割が得られる．
\section{最適分割を選択するアルゴリズム}
\label{sec:algorithm}本章では，分割$S$のコスト$C(S)$を，\begin{equation}\label{eq:costS}C(S)\equiv-\log\Pr(W|S)\Pr(S)\end{equation}と定義し，このコストが最小となる分割$\hat{S}=\arg\min_SC(S)$を選択することにより，最大確率である分割$\hat{S}$を選択する．ここで，$C(S)$は以下のように展開できる．\begin{eqnarray}\label{eq:CS}C(S)&=&-\log\Pr(W|S)\Pr(S)\nonumber\\&=&-\sum_{i=1}^m\sum_{j=1}^{n_i}\log\Pr(w^i_j|S_i)+m\logn\nonumber\\&=&\sum_{i=1}^mc(w^i_1w^i_2\ldotsw^i_{n_i}|n,k).\end{eqnarray}ただし，\begin{eqnarray}\label{eq:cS_i}c(w^i_1w^i_2\ldotsw^i_{n_i}|n,k)&\equiv&\sum_{j=1}^{n_i}\log\frac{n_i+k}{f_i(w^i_j)+1}+\logn\nonumber\\&=&\sum_{j=1}^{\#(w^i_1w^i_2\ldotsw^i_{n_i})}\log\frac{\#(w^i_1w^i_2\ldotsw^i_{n_i})+k}{g(w^i_j|w^i_1w^i_2\ldotsw^i_{n_i})+1}+\logn.\nonumber\\\end{eqnarray}ここで，$\#(\cdots)$は，その引数である単語列の長さ(延べ単語数)である．なお，(\ref{eq:cS_i})式を，その最終行において，$n_i$や$f_i$を使わないで定義する理由は，次節で述べるアルゴリズムにおいて，(\ref{eq:cS_i})式を使うときの便宜を考えてのことである．次に，最小コスト分割(最大確率分割)である$\hat{S}$を求めるアルゴリズムを示す．\subsection{最小コスト分割を求めるアルゴリズム}まず，用語を定義する．延べ語数$n$のテキスト$W=w_1w_2\ldotsw_n$において，$i$番目の分割候補点$g_i$とは，単語$w_{i}$と$w_{i+1}$の間を言う．ただし，$g_0$は$w_1$の直前，$g_n$は$w_n$の直後である．このとき，分割候補点は$g_0,g_1,\ldots,g_n$の$n+1$個ある．また，分割候補点の集合をノード集合とするグラフを考えるとき，$e_{ij}(0\lei<j\len)$は$g_i$から$g_j$への有向辺である．このように定義されたグラフの例を，図\ref{fig:graph}に示す．\hspace*{1em}\begin{figure}[htbp]\begin{center}\atari(125,16)\caption{分割候補点をノードとするグラフ}\label{fig:graph}\end{center}\end{figure}このとき，$e_{ij}$は，単語列$w_{i+1}w_{i+2}\ldotsw_j$をカバーするという．$e_{ij}$は，テキストの，ある一区間$w_{i+1}w_{i+2}\ldotsw_j$を表現している．そのため，$e_{ij}$のコスト$c_{ij}$を，(\ref{eq:cS_i})式を利用することにより，次式で定義する．\begin{equation}\label{eq:costeij}c_{ij}=c(w_{i+1}w_{i+2}\ldotsw_j|n,k)\end{equation}ただし，$k$は，$W$中の異なり単語数である．以上の準備の下で，最小コストを与える最適分割を求める手順は以下の通りである．\begin{description}\item[Step1.]有向辺$e_{ij}$のコスト$c_{ij}$を(\ref{eq:costeij})式により計算する．$(0\lei<j\len).$\item[Step2.]$g_0$から$g_n$までの最小コストパスを求める．\end{description}ここで，Step2を効率的に解くアルゴリズムは良く知られている\footnote{Step2は日本語の形態素解析においてコスト最小解(確率最大の解)を探索するアルゴリズムと同一(実際はより簡単)であるので，DP(DynamicProgramming)を用いて効率的に解くことができる\cite{nagata94:_stoch_japan_morph_analy_using}．また，本稿で述べた手法を実装したプログラムが第1著者より入手できる．なお，DPを用いてテキストを分割する研究としては，\cite{ponte97:_text_segmen_topic,heinonen98:_optim_multi_parag_text_segmen_dynam_progr}がある．}．なお，Step2は，全ての可能なパスの中での大域的な最小コストパスを求めるものであるが，そうする代りに，パスの長さを指定した最小コストパスを求めることもできる．そのようにして求められた最小コストパスは，区間数を指定した場合の最適分割に対応している．このようにして求めた最小コストパスについて，その各辺にカバーされる単語列を，それぞれ一つの区間とすると，それは最適分割である．たとえば，図\ref{fig:graph}で，$e_{01}e_{13}e_{35}$が最小コストパスであるとすると，最適分割は，$[w_1][w_2w_3][w_4w_5]$である．なお，実際にテキストを分割するときには，全ての分割候補点を考慮するのではなく，たとえば，文と文の間でのみテキストを分割したい場合がある．その場合には，分割位置として許される分割候補点の間にのみ有向辺を張るようにすれば良い．そして，そのグラフ上での最小コストパスを探索すれば良い．次節では，我々は，文間のみでテキストが分割されると仮定して議論している．\subsection{最小コスト分割よりも細かい分割をする際の問題点と解決策}\label{eq:rec}前節で述べたように，グラフの最小コストパスを求めることにより，大域的な最小コストパスによる分割だけでなく，区間数を指定した最小コストパスによる分割を求めることもできる．しかし，予備実験の結果から，指定された区間数が，もし，大域的な最小コストパスにより求められる分割の区間数よりも，ある程度以上に大きいときには，1文や2文からなる小さい区間が生じやすいことが判った．このことは，大域的な最小コストパスによる分割のみが必要な場合，あるいは，大域的な最小コストパスによる分割よりも大雑把な分割が必要な場合には問題ではない．しかし，大域的な最小コストパスによる分割よりも細かい分割が必要なときには，問題である．そこで，我々は，大域的な最小コストパスよりも細かい分割が必要なときには，まず，文章全体を大域的な最小コストパスにより分割し，そのあとで，各々の区間を，その区間を一つの文章として，再帰的に分割することにした\footnote{予備実験の結果から，我々の方法は，1000文を越すような長い文章が与えられたときでも，その大域的な最小コストパスによる分割の区間数は10から20程度であることが分かった．それと逆に，新聞の社説のような比較的短いものについても，4から6程度の区間数の分割が最適分割となる場合が多い．この性質は，我々がテキスト分割の結果を要約に利用しようとしているという観点からは望ましいものである．なぜならば，要約においては，文章の長さに関わらず，それを適当に少ないトピックにまとめる必要があるので，分割の結果得られる区間数は，文章の長さに，それほど影響されない方が望ましいからである．なお，このように，我々の手法において，分割の区間数が文章の長さに必ずしも比例しない理由は，(\ref{eq:CS})式の，$m\logn$における$\logn$が，長い文章ほど大きくなるので，長い文章においては，短かい文章よりも分割が抑制されやすいからである．}．このとき，各々の区間を分割するときの区間数は，その区間の長さの，全体の長さにおける割合に比例するようにした．たとえば，1000文からなる文章を20区間に分割したいときに，大域的な最小コストパスにより，200,400,300,100文からなる四つの区間が得られたときには，それぞれの区間を，4,8,6,2だけの区間に分割する．なお，分割数に余りがでるときには，その他の区間よりも大きい区間を，他よりも一つだけ余分に分割するようにした．たとえば，上述の文章を22に分割したいときには，それぞれを，4,8+1,6+1,2だけの区間に分割する．このようにすれば，1文や2文からなる小さい区間が生じにくいようにすることができる\footnote{再帰的分割により細かい分割も妥当にできる定性的な理由は以下の通りである：まず，(\ref{eq:CS})式のコスト関数は，$C(S)=\log\frac{1}{\Pr(W|S)}+\log\frac{1}{\Pr(S)}$である．$C(S)$の第1項をデータのコストと呼び，第2項をモデルのコストと呼ぶことにする．一般に，データのコストは，分割が細かいほど小さくなり，モデルのコストは分割が細かいほど大きくなる．そして，最小コスト解は，これらのバランスがとれたところとなる．ところが分割を最小コスト解よりも細かくすると，モデルのコストがデータのコストよりも大幅に大きくなるため，分割の決定においてデータのコストが反映されにくくなり，妥当な分割が得られなくなる．一方，再帰的に分割したときには，再帰的な分割の対象となる各区間においては，(\ref{eq:CS})式の$m$も$n$も再帰的な分割をする前と比べて小さい値となるため，モデルのコストが小さくなる．そのため，モデルのコストとデータのコストのバランスが取れ，妥当な分割が得られやすくなる．以上をまとめると，\begin{quote}\begin{tabular}{cccl}{\bf再帰前}&データのコスト&$\ll$&モデルのコスト\\&&$\Rightarrow$&データのコストが分割に反映されない\\&&$\Rightarrow$&データを無視した妥当でない分割となる\\{\bf再帰後}&データのコスト&$\sim$&モデルのコスト\\&&$\Rightarrow$&データのコストが分割に反映される\\&&$\Rightarrow$&データを考慮した妥当な分割となる．\end{tabular}\end{quote}}．このプロセスは，必要な分割数が得られるまで再帰的に実行できるが，\ref{sec:exp2}節で必要な，100程度までの分割数に対しては，1回だけの再帰で十分であった．なお，再帰的な分割の効果については，\ref{sec:exp2}節で確認する．\vspace*{5pt}
\section{実験}
\label{sec:experiments}本章では，まず，実験1で，我々の手法を公開データに基づいて評価することにより，我々の手法が他の手法よりも優れた分割精度を持つことを示し，次に，実験2で，我々の手法を長い文書に適用した場合の分割精度を述べる．二つの実験の本稿全体における位置付けは以下の通りである．まず，実験1の目的は，提案手法と従来手法とを比較することにより，提案手法が，従来手法よりも，テキストを精度良く分割できることを示すことにある．そのため，もし，提案手法と従来手法とを比較したいだけならば，実験1のみで十分である．したがって，本稿の主要な目的である，提案手法の他の手法に対する優位性を示すためには，実験1だけで十分である\footnote{もちろん，この言明は，実験1で用いたデータによる分割結果の精度が，どれほど現実のテキストの分割結果の精度を反映しているかによる．我々は，この分割結果の精度が，そのまま現実のテキストにおける分割結果の精度となることはないとしても，この分割結果で明かになる，テキスト分割システムの精度の順位は，現実のテキストにおいても反映されると考えている．また，現在，我々が入手可能なデータの中では，実験1に用いたデータが，最も包括的に従来手法を網羅しているため，各種手法を比較するテストベッドとしては妥当であると考える．}．しかし，我々の最終的な目的は，テキスト分割の結果を，長い文書の要約\cite{nakao00:_algor_one_summar_long_text}や講演のディクテーション結果の要約に使うことであるので，その目的のために，提案手法が，どれほど役に立つかを調べたい．そのために，実験2においては，提案手法による分割が，どの程度，元の文書の章や節と一致するかを調べることにより，提案手法の，長い文書を要約するときへの応用の可能性を把握することを目的とする．そのため，実験2の位置付けは，今後我々の手法を実際の応用へと適用させるための前段階と考えている．我々は，将来的には，何らかのタスクに基づいて提案手法を評価することを考えている．\subsection{実験1：公開データによる評価}\label{sec:exp1}実験1で用いたデータは，\cite{choi00:_advan}により，各種のテキスト分割手法を比較するために用いられたデータである\footnote{{\tthttp://www.cs.man.ac.uk/\~{}choif/software/C99-1.2-release.tgz}より入手可能である．このパッケージを展開したときにできる{\ttnaacl00Exp/data/\{1,2,3\}/\{3-11,3-5,6-8,9-11\}/*}を実験に用いた．}．Choiは，彼の提案手法$C99$と，TextTiling\cite{hearst94:_multi_parag_segmen_expos_text}，DotPlot\cite{reynar98:_topic},Segmenter\cite{kan98:_linear_segmen_segmen_signif}を比較し，$C99$では，他の手法と比較し，誤り確率が半減されたと述べている．ただし，誤り確率とは，テキストを構成する単位(単語，文，パラグラフ等)について，任意に選んだ$r$単位だけ離れた二つの単位が誤って分割される確率のことである．ここで，$r$は，正しい分割における各区間の長さの平均の半分が良いとされている\cite{beeferman99:_statis_model_text_segmen}．なお，実験1における$r$の単位は単語である．また，誤り確率が低いほど精度は良い．この実験データは，700個のテキストからなり，個々のテキストは，10個のテキスト断片を連結したものである．そして，それぞれのテキスト断片は，BrownCorpusからランダムサンプリングされたテキストの最初の$s$行である．個々のテキストは，$s$により特徴付けられる．表\ref{tab:testcorpus}には，実験データの諸元を示す．\begin{table}[htbp]\begin{center}\caption{実験データの諸元\protect{\cite{choi00:_advan}}}\begin{tabular}{|l|c|c|c|c|}\hline$s$の範囲&$3-11$&$3-5$&$6-8$&$9-11$\\\hlineテキスト数&400&100&100&100\\\hline\end{tabular}\label{tab:testcorpus}\end{center}\end{table}各テキストは，Choiのパッケージにあるライブラリを利用したstemmerにより正規化され，その正規化されたテキストが提案手法により分割された．ただし，分割可能な位置は，\cite{choi00:_advan}と同様に，文間のみである．その後，分割されたテキストの誤り確率は，Choiのパッケージにある評価プログラムにより計算された．その評価結果を表\ref{tab:U00vsC99}と表\ref{tab:U00bvsC99b}に示す．これらの表において，$U00$は，提案手法において，大域的な最小コスト分割を求めたときの評価結果であり，$U00_{(b)}$は，提案手法において，区間数を10に指定\footnote{この際には，\ref{eq:rec}節で述べた再帰的分割は適用していない．}したときの評価結果である．また，$C99$は，Choiのアルゴリズムによる最適分割の評価結果であり，$C99_{(b)}$は，Choiのアルゴリズムにおいて区間数を10に指定した場合の評価結果である\footnote{表\ref{tab:U00bvsC99b}の$C99_{(b)}$の行にある数値は，\cite{choi00:_advan}のTable6のものと若干異なる．その理由は，元々の数値は500のサンプルテキストに基づいたものであるのに対して，この表のものは，700のサンプルに基づいて我々が再実験した結果だからである(Choi,personalcommunication)．なお，\cite{choi00:_advan}で使われた500サンプルにおける$C99_{(b)}$の誤り確率は以下の表のものである．\begin{tabular}{|c|cccc|c|}\hline&$3-11$&$3-5$&$6-8$&$9-11$&全体\\\hline$C99_{(b)}$&12\%&12\%&9\%&9\%&12\%\\\hline\end{tabular}}．また，二つの表において，$**$は，比較対象であるアルゴリズムの誤り確率が$t$検定により，有意水準1\%で有意差があることを示す．なお，「$3-11$」などの列の数字は，それに該当するテキストにおける誤り確率の平均であり，「全体」は，全部のテキストについての誤り確率の平均である．\begin{table}[htbp]\begin{center}\caption{分割数をプログラムが決めた場合の誤り確率の比較}\begin{tabular}{|c|cccc|c|}\hline&$3-11$&$3-5$&$6-8$&$9-11$&全体\\\hline$U00$&11\%$^{**}$&13\%$^{**}$&6\%$^{**}$&6\%$^{**}$&10\%$^{**}$\\$C99$&13\%&18\%&10\%&10\%&13\%\\\hline\end{tabular}\label{tab:U00vsC99}\end{center}\end{table}\begin{table}[htbp]\begin{center}\caption{分割数が指定された場合の誤り確率の比較}\begin{tabular}{|c|cccc|c|}\hline&$3-11$&$3-5$&$6-8$&$9-11$&全体\\\hline$U00_{(b)}$&10\%$^{**}$&9\%&7\%$^{**}$&5\%$^{**}$&9\%$^{**}$\\$C99_{(b)}$&12\%&11\%&10\%&9\%&11\%\\\hline\end{tabular}\label{tab:U00bvsC99b}\end{center}\end{table}これらの表から，提案手法が，$C99$あるいは$C99_{(b)}$と，同等あるいは，より精度良くテキストを分割できると言える．そして，$C99$あるいは$C99_{(b)}$は，分野非依存のテキスト分割手法のなかでは，その他の従来手法よりも精度良くテキストを分割できるので，我々の提案手法が，従来手法よりも精度良くテキストを分割できることが言える．\subsection{実験2：長い文書の章や節との一致度による評価}\label{sec:exp2}実験2では，比較的長い文章を分割し，その分割結果と元々の章や節による分割とを比較することにより，提案手法を評価した．実験に用いたデータは，文部省年報\footnote{{\tthttp://wwwwp.mext.go.jp/download.html}よりダウンロードできる．}である．我々がこのデータを用いた理由は，それが公開されているということに加えて，SGMLでタグ付けされているため，付録に示す簡単なPerlスクリプトにより章(chapter)や節(section)を切り出せるためである\footnote{このPerlスクリプトにより切り出せないものもある．実験に用いたものは，このスクリプトにより処理可能なものである．}．\begin{table}[htbp]\begin{center}\caption{文部省年報の諸元}\begin{tabular}{|c|ccc|}\hline&章の数&節の数&ページ数\\\hline昭和６０年度&13&63&62\\昭和６２年度&22&96&109\\昭和６３年度&13&65&52\\平成元年度&13&64&54\\平成２年度&13&64&55\\\hline\end{tabular}\label{tab:monbu}\end{center}\end{table}表\ref{tab:monbu}には，実験に用いた文部省年報の諸元を示す．表で，章や節の数は，元のファイルでの章や節の数を数えたものであるが，ページ数は，我々が，元テキストをポストスクリプトファイルに変換して数えたものであるので，一応の目安と考えておくのが良い．表\ref{tab:monbu}に示す文部省年報には，以下の前処理が加えられた．まず，付録のスクリプトを用いて，章や節を切り出した結果から，分割位置を示す記号を除いたテキストを得た．次に，そのテキストに対して，ChaSenversion2.25\cite{matsumoto99:_japan_morph_analy_system_chasen_manual}を適用し，その結果から，ChaSenの品詞体系における「名詞」「未知語」「記号-アルファベット」「接頭詞」に該当するもののみを抽出し，提案手法への入力とした．ただし，名詞のうちで，その下位分類が「数」「代名詞」「非自立」「特殊」「接続詞的」「動詞非自立的」に該当するものは除いた．また，平仮名だけからなる形態素も除いた．なお，このときの分割可能な位置はスクリプトの出力結果の各行の終りである．これは，段落の間で分割していることに相当する．表\ref{tab:chap}，表\ref{tab:secnorec}，表\ref{tab:secrec}には，このようにして得られたテキストを，分割対象の章や節の数を指定して，分割したときの精度を示す．ここで，表のタイトルに付記している再帰的分割とは，\ref{eq:rec}節で述べた再帰的方法により分割した場合を示し，非再帰的分割とは，再帰的分割をしていない場合を示す．また，精度とは，\begin{displaymath}\frac{元の章や節と一致した分割位置の数}{章や節の分割位置の総数}\end{displaymath}である．ただし，章や節の数を$n$とすると，分割位置の数は，$n-1$である．なお，本実験で分割数を指定している理由は，本実験の目的が，指定された粒度の分割をどの程度の精度で実現できるかを調べることにあるからである．粒度を指定した分割は，長い文書から，必要に応じた長さの要約を得るときに重要である\cite{nakao00:_algor_one_summar_long_text}．\begin{table}[htbp]\begin{center}\caption{分割結果と章の区切れとの対応(非再帰的分割)}\begin{tabular}{|c|ccc|}\hline&章の数&±1の精度&±0の精度\\\hline昭和６０年度&13&0.42(0.019)&0.33(0.006)\\昭和６２年度&22&0.52(0.021)&0.29(0.007)\\昭和６３年度&13&0.50(0.021)&0.42(0.007)\\平成元年度&13&0.50(0.020)&0.42(0.007)\\平成２年度&13&0.50(0.020)&0.42(0.007)\\\hline平均&&0.49(0.020)&0.37(0.007)\\\hline\end{tabular}\label{tab:chap}\end{center}\end{table}\begin{table}[htbp]\begin{center}\caption{分割結果と節の区切れとの対応(非再帰的分割)}\begin{tabular}{|c|ccc|}\hline&節の数&±1の精度&±0の精度\\\hline昭和６０年度&63&0.29(0.10)&0.13(0.033)\\昭和６２年度&96&0.17(0.10)&0.07(0.032)\\昭和６３年度&65&0.34(0.11)&0.16(0.038)\\平成元年度&64&0.37(0.11)&0.19(0.036)\\平成２年度&64&0.38(0.11)&0.18(0.036)\\\hline平均&&0.31(0.10)&0.14(0.035)\\\hline\end{tabular}\label{tab:secnorec}\end{center}\end{table}\begin{table}[htbp]\begin{center}\caption{分割結果と節の区切れとの対応(再帰的分割)}\begin{tabular}{|c|ccc|}\hline&節の数&±1の精度&±0の精度\\\hline昭和６０年度&63&0.50(0.10)&0.31(0.033)\\昭和６２年度&96&0.45(0.10)&0.32(0.032)\\昭和６３年度&65&0.48(0.11)&0.28(0.038)\\平成元年度&64&0.56(0.11)&0.38(0.036)\\平成２年度&64&0.57(0.11)&0.40(0.036)\\\hline平均&&0.51(0.10)&0.34(0.035)\\\hline\end{tabular}\label{tab:secrec}\end{center}\end{table}これらの表において，「±0の精度」とは，システムによる分割位置が，元文書の分割位置と正確に同一な場合を一致としたときの精度である．また，「±1の精度」とは，正確に同一な場合に加えて，前後1行のずれまでを許容して一致としたときの精度である．なお，それぞれの精度を示す列において，括弧内の数値は，精度のベースライン\begin{equation}\label{eq:bl}\frac{テキストにおいて一致と判定する許容範囲のサイズの合計}{テキストのサイズ}\end{equation}である\cite{nakao99}\footnote{\cite{nakao99}では，(\ref{eq:bl})式を再現率のベースラインとしているが，本実験の場合には，分割数を指定しているので，再現率と精度が一致する．}．ただし，本実験の場合には，サイズは行数でカウントする．まず，表\ref{tab:chap}における，章の数を分割数としたときの分割精度を見る．表\ref{tab:chap}では，±1の精度の平均が0.49であり，±0の精度の平均が0.37である．ここで，\cite{reynar99:_statis_model_topic_segmen}では，英文テキスト4文書について，彼の手法による分割結果が，平均0.25の精度で章の区切れと一致することを述べていて，\cite{nakao00:_algor_one_summar_long_text}では，ベースラインが0.005〜0.01のとき，F値\footnote{これは，我々の精度に相当する．なお，F値(=$\frac{2\times再現率\times適合率}{再現率+適合率}$)は，\cite{nakao00:_algor_one_summar_long_text}のTable3から計算で求めた．}が，0.31〜0.39である．これらの結果は，±0の精度に対応するが，テキストが違うため，直接比較することは不可能である．しかし，数値だけを比較するならば，我々の方法は，章の分割に関しては，これらの方法と比べて，少なくとも同等程度に章の区切れを再現していると考える．次に，節の数を指定したときの分割精度を表\ref{tab:secnorec}と表\ref{tab:secrec}に示す．また，表\ref{tab:num}には，最小コスト解による分割数と章や節の数とを示す．表\ref{tab:secnorec}は，再帰をせずに，分割数を指定して分割したときの精度を示している．このとき，±1の精度の平均が0.31であり，±0の精度の平均が0.14である．一方，再帰的分割をしたときには，表\ref{tab:secrec}に示すように，±1の精度の平均が0.51であり，±0の精度の平均が0.34である．これから分かるように，最小コスト解よりも粒度の細かい分割が必要なときには，再帰的分割をした方が精度良く分割ができる．なお，\cite{nakao00:_algor_one_summar_long_text}では，ベースラインが0.035のときにF値が0.29であるので，再帰的分割による方法は，\cite{nakao00:_algor_one_summar_long_text}と比べて，少なくとも同等程度に節の区切れを再現していると考える．\begin{table}[htbp]\begin{center}\caption{最小コスト解による分割数と章や節の数}\begin{tabular}{|c|ccc|}\hline&最小コスト解による分割数&章の数&節の数\\\hline昭和６０年度&13&13&63\\昭和６２年度&12&22&96\\昭和６３年度&11&13&65\\平成元年度&12&13&64\\平成２年度&12&13&64\\\hline\end{tabular}\label{tab:num}\end{center}\end{table}\vspace*{20pt}
\section{考察と今後の課題}
\label{sec:discussion}提案手法は，分割確率最大化という観点からテキスト分割を定式化した．これに類似の手法として，訓練データを利用したテキスト分割では，\cite{mulbregt98:_hidden_markov_model_approac_text}が隠れマルコフモデルに基づいて，複数ニュースを個々のニュースに分割しているが，訓練データを利用しないテキスト分割では，類似の研究はない．また，\cite{mulbregt98:_hidden_markov_model_approac_text}についても，彼等は，テキストの分割確率を直接扱っているのではなく，各単語を生起させるようなトピックを単語毎に求め，同一トピックの単語が連続する部分を同一トピックとする，という間接的アプローチをとっている．そのため，彼等のアプローチでは，たとえば，トピックの平均の長さなどを直接取り込むことが難しい．一方，我々のアプローチでは，このことは素直に表現できる．たとえば，\cite{ponte97:_text_segmen_topic}と同様に，トピックの長さ$x$が，平均長$\mu$，標準偏差$\sigma$の正規分布$N(x|\mu,\sigma)$に従うと仮定すると，単純な拡張としては，(\ref{eq:cS_i})式を，$\alpha+\beta+\gamma=1$として，以下のようにすれば，トピックの長さが平均と同じくなるような分割が優先される．\begin{eqnarray}c(w^i_1w^i_2\ldotsw^i_{n_i}|n,k,\mu,\sigma,\alpha,\beta,\gamma)&=&\alpha\sum_{j=1}^{\#(w^i_1w^i_2\ldotsw^i_{n_i})}\log\frac{\#(w^i_1w^i_2\ldotsw^i_{n_i})+k}{g(w^i_j|w^i_1w^i_2\ldotsw^i_{n_i})+1}+\beta\logn\nonumber\\&&+\gamma\log\frac{1}{N(\#(w^i_1w^i_2\ldotsw^i_{n_i})|\mu,\sigma)}.\nonumber\end{eqnarray}更に，彼等の手法と我々の手法との大きな違いは，彼等が単語の確率を訓練データから推定しているのに対して，我々は，単語の確率を分割対象のテキストから推定している点である．なお，訓練データが利用可能な場合に，彼等の手法と我々の手法とを比較することは興味深いであろう．その場合には，上式で示したような，トピックの長さをコスト関数として取り込むことや，種々の手がかり表現をコスト関数に取り込むことも検討したい．次に，提案手法のテキスト分割における特徴としては，\ref{eq:rec}節で述べたように，長い文章でも短かい文章でも，分割数が，大幅には変動しないというものがある．これは，短かい文章は，細かい粒度で分割し，長い文章は大雑把な粒度で分割するということである．この性質は，我々がテキスト分割をする目的が要約のため，という観点からは適した性質である．なぜなら，要約では，文章の長さに関わらず，それを適当に少ないトピックにまとめる必要があるので，分割の結果得られる区間数は，文章の長さに，それほど影響されない方が望ましいからである．しかし，応用によっては，任意に指定した粒度の分割が望ましい場合もあると考えられる．そのために，我々は，本稿では，大域的な最小コスト解よりも細かい分割が必要な場合には，再帰的な分割を適用し，それは有効ではあったが，より有効な分割方法を考えることは今後の課題としたい．そのための見込みのある方法の一つは，\cite{nakao99}で提案されているように，分割したい粒度に応じて窓の大きさを設定し，その窓内を一つの文章としてテキストを分割することである．最後に，提案手法によると，テキストの分割の結果として，テキストの各区間における単語の確率(密度)が自然に求まる．このような密度は，重要単語の抽出\cite{bookstein95:_detec_conten_words_serial_clust}や，重要説明箇所の特定\cite{kurohashi97}に有用であることが知られている．提案手法を，このようなアプリケーションに対して適用することも興味深い．
\section{おわりに}
\label{sec:conclusion}我々は，本稿において，分割確率最大化という観点から，テキスト内の情報のみを用いて，テキストを分割する手法を提案した．提案手法は，従来の手法と比べて，同等以上の精度でテキストを分割することができた．このことは提案手法がテキストの分割に有用であることを示している．我々は，今後，実際の応用におけるテキスト分割の有効性を調べることを考えている．\appendix\subsection*{章や節の切り出しに用いたPerlスクリプト}\footnotesize\begin{verbatim}##perlnpaa-div.pl(chapter|section)<file.sgm##ファイルの第1部(part)のchapterまたはsectionに相当する部分を#抜き出して，区切り(================)を入れるプログラム．#$type=shift;#typeiseither'chapter'or'section'while(<>){if(m&<part>&i){while(<>){lastifm&</part>&i;if(m&<$type&i){print"================\n";while(<>){lastifm&</$type>&i;unless(m&^<&i){s/&.+?;//g;s/\r//g;print;}}redoifm&<$type&i;}}last;}}print"================\n";\end{verbatim}\normalsize\bibliographystyle{jnlpbbl}\bibliography{seg}\normalsize\begin{biography}\biotitle{略歴}\bioauthor{内山将夫}{筑波大学第三学群情報学類卒業(1992).筑波大学大学院工学研究科博士課程修了(1997).博士(工学).信州大学工学部電気電子工学科助手(1997)．郵政省通信総合研究所非常勤職員(1999).独立行政法人通信総合研究所任期付き研究員(2001).言語処理学会，情報処理学会，ACL，人工知能学会，日本音響学会，各会員．}\bioauthor{井佐原均}{1978年京都大学工学部電気工学第二学科卒業．1980年同大学院修士課程修了．博士（工学）．同年通商産業省電子技術総合研究所入所．1995年郵政省通信総合研究所．現在、独立行政法人通信総合研究所けいはんな情報通信融合研究センター自然言語グループリーダー．自然言語処理，機械翻訳の研究に従事．言語処理学会，情報処理学会，人工知能学会，日本認知科学会，ACL，各会員．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}