\documentstyle[jnlpbbl,epsf]{jnlp_j}


\setcounter{page}{19}
\setcounter{巻数}{8}
\setcounter{号数}{4}
\setcounter{年}{2001}
\setcounter{月}{10}
\受付{2000}{12}{22}
\再受付{2001}{5}{12}
\採録{2001}{6}{29}

\setcounter{secnumdepth}{2}

\title{統計的手法による分野非依存のテキスト分割}
\author{内山 将夫\affiref{U} \and 井佐原 均\affiref{U}}

\headauthor{内山，井佐原}
\headtitle{統計的手法による分野非依存のテキスト分割}

\affilabel{U}{通信総合研究所}{Communications Research Laboratory}

\jabstract{
複数のトピックからなる文章を，それぞれのトピックに切り分けるこ
とをテキスト分割と呼ぶ．テキスト分割は，情報検索や要約のための
基本技術として有用である．本稿では，分割確率最大化という観点か
らテキスト分割を定式化した．その定式化の特色の一つは，テキスト
内の単語しか，確率推定に利用しないことである．そのため，提案手
法は，任意の分野のテキストに対して適用できる．提案手法の有効性
は二つの実験により確認された．まず，実験1では，公開データに対し
て提案手法を適用することにより，提案手法の分割精度が従来手法の
分割精度よりも優れていることが示された．次に，実験2では，長い文
書の元々の章や節の構造と提案手法による分割結果とを比較した結果，
厳密な一致のみを正解とする場合，章には0.37, 節には0.34の割合で
一致し，±1行のずれを許容する場合，章には0.49,節には0.51の割合
で一致した．これらのことは，提案手法が，テキスト分割に対して有
効であることを示している．}

\jkeywords{テキスト分割，統計的手法}

\etitle{A Statistical Approach to \\ Domain Independent Text Segmentation}
\eauthor{Masao Utiyama\affiref{U} \and Hitoshi Isahara\affiref{U}}

\eabstract{A text is usually composed of multiple topics. Segmenting such
a text into coherent topics is useful both for information
retrieval and for automatic text summarization. This paper
proposes a statistical method that selects the segmentation of
the highest probability among possible segmentations as the
best segmentation of the given text. Since the method estimates
probabilities of segmentations from the given text, it does not
need training data. Therefore, it can be applied to any text in
any domain. The effectiveness of the method was confirmed
through two experiments. The first experiment evaluated the
accuracy of the method by using publicly available data. The
experimental results showed that the accuracy of the proposed
method is at least as good as that of a state-of-the-art text
segmentation system. The second experiment compared the
segmentations done by our method with those of original
segments in relatively long documents. When we compared our
system's segmentations with chapters in the documents, the
accuracy was 0.37 on the condition that we regarded only exact
matches as correct matches. If we regarded ±1 line differences
as correct then the accuracy was 0.49. When we compared our
system's segmentations with sections, the accuracies were 0.34
and 0.51, respectively.  These results show that our method is
effective for domain independent text segmentation.}

\ekeywords{text segmentation, statistical approach}


\begin{document}
\maketitle



















\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_1 w_2 \ldots w_n$
が与えられたとき，$m$個の区間からなる分割 $S = S_1 S_2 \ldots
S_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_1 w^i_2 \ldots w^i_{n_i}$とする．つ
まり，$S_i$と$W_i$とを一対一に対応させる．このようにすると，$n
= \sum_{i=1}^m n_i$，$W = W_1 W_2 \dots W_m$ である．

このとき，ある区間に属する単語列は，その他の区間には独立に生起
するとし，更に，同一区間に属する単語も，区間が与えられていると
いう条件下では確率的に独立であるとすると，
\begin{eqnarray}
  \label{eq:PrWSexpand}
  \Pr(W|S) & = & \Pr(W_1 W_2 \ldots W_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's
law)と呼ばれる確率推定式
\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) \equiv g(w^i_j|w^i_1 w^i_2 \ldots w^i_{n_i})
\end{eqnarray}
\begin{eqnarray}
  \label{eq:g}
  g(w^i_j|w^i_1 w^i_2 \ldots w^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(Minimum Description Length, 最小記述長)原理
\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) \le
  1$となる\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$の確率で選択されると考えることができるので，
$\log n$の記述長で記述できる．よって，$m$個の数字を記述するため
には，$m \log n$の記述長があれば良い．以上より，$l(S) = m \log
n$ と計算できる\footnote{このような$m$個の数字を記述するための
  記述長には，いくつかの変種がある．それらについては，
  \cite{stolcke94:_best_model_mergin_hidden_markov_model_induc}
  を参照のこと．}．

そのため，$\Pr(S)$は
\begin{equation}
  \label{eq:PrM}
  \Pr(S) \equiv n^{-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_S C(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 \log n \nonumber \\
  & = & \sum_{i=1}^m c(w^i_1 w^i_2 \ldots w^i_{n_i}|n,k).
\end{eqnarray}
ただし，
\begin{eqnarray}
  \label{eq:cS_i}
  c(w^i_1 w^i_2 \ldots w^i_{n_i}|n,k) & \equiv & \sum_{j=1}^{n_i} \log \frac{n_i+k}{f_i(w^i_j)+1} + \log n \nonumber \\
  & = & \sum_{j=1}^{\#(w^i_1 w^i_2 \ldots w^i_{n_i})} \log \frac{\#(w^i_1 w^i_2 \ldots w^i_{n_i})+k}{g(w^i_j|w^i_1 w^i_2 \ldots w^i_{n_i})+1} + \log n.\nonumber \\
\end{eqnarray}
ここで，$\#(\cdots)$は，その引数である単語列の長さ(延べ単語数)
である．なお，(\ref{eq:cS_i})式を，その最終行において，$n_i$や
$f_i$を使わないで定義する理由は，次節で述べるアルゴリズムにおい
て，(\ref{eq:cS_i})式を使うときの便宜を考えてのことである．

次に，最小コスト分割(最大確率分割)である$\hat{S}$を求めるアルゴ
リズムを示す．

\subsection{最小コスト分割を求めるアルゴリズム}

まず，用語を定義する．延べ語数$n$のテキスト$W = w_1 w_2 \ldots
w_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 \le i < j \le n)$ は $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} \ldots w_j$をカバー
するという．$e_{ij}$は，テキストの，ある一区間$w_{i+1} w_{i+2}
\ldots w_j$を表現している．そのため，$e_{ij}$のコスト$c_{ij}$を，
(\ref{eq:cS_i})式を利用することにより，次式で定義する．
\begin{equation}
  \label{eq:costeij}
  c_{ij} = c(w_{i+1} w_{i+2} \ldots w_j|n,k)
\end{equation}
ただし，$k$は，$W$中の異なり単語数である．

以上の準備の下で，最小コストを与える最適分割を求める手順は以下
の通りである．
\begin{description}
\item[Step 1.] 有向辺$e_{ij}$のコスト$c_{ij}$を
  (\ref{eq:costeij})式により計算する．$(0 \le i < j \le n).$
\item[Step 2.] $g_0$から$g_n$までの最小コストパスを求める．
\end{description}
ここで，Step 2 を効率的に解くアルゴリズムは良く知られている
\footnote{Step 2 は日本語の形態素解析においてコスト最小解(確率
  最大の解)を探索するアルゴリズムと同一(実際はより簡単)であるので，
  DP(Dynamic Programming)を用いて効率的に解くことができる
  \cite{nagata94:_stoch_japan_morph_analy_using}．また，本稿で
  述べた手法を実装したプログラムが第1著者より入手できる．なお，
  DPを用いてテキストを分割する研究としては，
  \cite{ponte97:_text_segmen_topic,heinonen98:_optim_multi_parag_text_segmen_dynam_progr}
  がある．}．なお，Step 2 は，全ての可能なパスの中での大域的な
最小コストパスを求めるものであるが，そうする代りに，パスの長さ
を指定した最小コストパスを求めることもできる．そのようにして求
められた最小コストパスは，区間数を指定した場合の最適分割に対応
している．

このようにして求めた最小コストパスについて，その各辺にカバーさ
れる単語列を，それぞれ一つの区間とすると，それは最適分割である．
たとえば，図\ref{fig:graph}で，$e_{01} e_{13} e_{35}$ が最小コ
ストパスであるとすると，最適分割は，$[w_1][w_2 w_3][w_4 w_5]$で
ある．

なお，実際にテキストを分割するときには，全ての分割候補点を考慮
するのではなく，たとえば，文と文の間でのみテキストを分割したい
場合がある．その場合には，分割位置として許される分割候補点の間
にのみ有向辺を張るようにすれば良い．そして，そのグラフ上での最
小コストパスを探索すれば良い．次節では，我々は，文間のみでテキ
ストが分割されると仮定して議論している．

\subsection{最小コスト分割よりも細かい分割をする際の問題点と解決策}
\label{eq:rec}

前節で述べたように，グラフの最小コストパスを求めることにより，
大域的な最小コストパスによる分割だけでなく，区間数を指定した最
小コストパスによる分割を求めることもできる．しかし，予備実験の
結果から，指定された区間数が，もし，大域的な最小コストパスによ
り求められる分割の区間数よりも，ある程度以上に大きいときには，1
文や2文からなる小さい区間が生じやすいことが判った．このことは，
大域的な最小コストパスによる分割のみが必要な場合，あるいは，大
域的な最小コストパスによる分割よりも大雑把な分割が必要な場合に
は問題ではない．しかし，大域的な最小コストパスによる分割よりも
細かい分割が必要なときには，問題である．

そこで，我々は，大域的な最小コストパスよりも細かい分割が必要な
ときには，まず，文章全体を大域的な最小コストパスにより分割し，
そのあとで，各々の区間を，その区間を一つの文章として，再帰的に
分割することにした\footnote{予備実験の結果から，我々の方法は，
  1000文を越すような長い文章が与えられたときでも，その大域的な
  最小コストパスによる分割の区間数は10から20程度であることが分
  かった．それと逆に，新聞の社説のような比較的短いものについて
  も，4から6程度の区間数の分割が最適分割となる場合が多い．この
  性質は，我々がテキスト分割の結果を要約に利用しようとしている
  という観点からは望ましいものである．なぜならば，要約において
  は，文章の長さに関わらず，それを適当に少ないトピックにまとめ
  る必要があるので，分割の結果得られる区間数は，文章の長さに，
  それほど影響されない方が望ましいからである．なお，このように，
  我々の手法において，分割の区間数が文章の長さに必ずしも比例し
  ない理由は，(\ref{eq:CS})式の，$m \log n$における 
  $\log n$ が，長い文章ほど大きくなるので，長い文章においては，
  短かい文章よりも分割が抑制されやすいからである．
}．

このとき，各々の区間を分割するときの区間数は，その区間の長さの，
全体の長さにおける割合に比例するようにした．たとえば，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{{\tt http://www.cs.man.ac.uk/\~{}choif/software/C99-1.2-release.tgz} より入手可能である．このパッケージを展開したときにできる {\tt naacl00Exp/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個のテキスト断片を連結したものである．
そして，それぞれのテキスト断片は，Brown Corpus からランダムサン
プリングされたテキストの最初の$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}の Table 6 のものと若干
  異なる．その理由は，元々の数値は500のサンプルテキストに基づい
  たものであるのに対して，この表のものは，700のサンプルに基づい
  て我々が再実験した結果だからである(Choi, personal
  communication)．なお，\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{{\tt
    http://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}に示す文部省年報には，以下の前処理が加えられた．
まず，付録のスクリプトを用いて，章や節を切り出した結果から，分
割位置を示す記号を除いたテキストを得た．次に，そのテキストに対
して，ChaSen version
2.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}のTable
  3 から計算で求めた．}が，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_1 w^i_2 \ldots w^i_{n_i}|n,k,\mu,\sigma,\alpha,\beta,\gamma)& = &\alpha \sum_{j=1}^{\#(w^i_1 w^i_2 \ldots w^i_{n_i})} \log \frac{\#(w^i_1 w^i_2 \ldots w^i_{n_i})+k}{g(w^i_j|w^i_1 w^i_2 \ldots w^i_{n_i})+1} + \beta \log n \nonumber \\
  & & + \gamma \log \frac{1}{N(\#(w^i_1 w^i_2 \ldots w^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}
#
# perl npaa-div.pl (chapter|section) < file.sgm
#
# ファイルの第1部(part)の chapter または section に相当する部分を
# 抜き出して，区切り(================)を入れるプログラム．
#

$type = shift;          # type is either 'chapter' or 'section'
while(<>){
    if(m&<part>&i){
        while(<>){
            last if m&</part>&i;
            if(m&<$type&i){
                print "================\n";
                while(<>){
                    last if m&</$type>&i;
                    unless(m&^<&i){
                        s/&.+?;//g;
                        s/\r//g;
                        print;
                    }
                }
                redo if m&<$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}
