\section{はじめに}
自然言語処理においてchunk同定問題(chunking)とは，単語列(一般にこれをtoken列とよぶ)をある視点からまとめ上げていき，まとめ上げた固まり(chunk)をそれらが果たす機能ごとに分類する一連の手続きのことを指す．この問題の範疇にある処理として，英語の単名詞句同定(baseNPchunking)，任意の句の同定(chunking)，日本語の文節まとめ上げ，固有名詞/専門用語抽出などがある．また，各文字をtokenとしてとらえるならば，英語のtokenization，日本語のわかち書き，品詞タグ付けなどもchunk同定問題の一種としてとらえることができる．一般に，chunk同定問題は，文脈から得られる情報を素性としてとらえ，それらの情報から精度良くchunkを同定するルールを導出する手続きとみなすことができる．そのため，各種の統計的機械学習アルゴリズムを適用可能である．実際に機械学習を用いた多くのchunk同定手法が提案されている\cite{Ramshaw95,Tjong_Kim_Sang2000a,Tjong_Kim_Sang2000b,Tjong_Kim_Sang2000d,内元00,Sassano00b}．しかしながら，従来の統計的手法は，いくつかの問題がある．例えば，隠れマルコフモデルや最大エントロピー(ME)モデルは素性どうしの組み合わせ(共起関係)を効率良く学習できず，有効な組み合わせの多くは人手によって設定される．また多く機械学習アルゴリズムは高い精度を得るために慎重な素性選択を要求し，これらの素性選択も人間の発見的な手続きにたよっている場合が多い．一方，統計的機械学習の分野では，Boosting\cite{Freund96}，SupportVectorMachines(SVMs)\cite{Vapnik95a,Vapnik98}等の学習サンプルと分類境界の間隔(マージン)を最大化にするような戦略に基づく手法が提案されている．特にSVMは，学習データの次元数(素性集合)に依存しない極めて高い汎化能力を持ち合わせていることが実験的にも理論的にも明らかになっている．さらに，Kernel関数を導入するとこで，非線形のモデル空間を仮定したり，複数の素性の組み合せを考慮した学習が可能である．このような優位性から，SVMは多くのパターン認識の分野に応用されている．自然言語処理の分野においても，文書分類や係り受け解析に応用されており，従来の手法に比べて高い性能を示している\cite{Joachims99,平2000,kudo2000b,kudo2000c,工藤02}本稿ではchunk同定問題として，英語の単名詞句のまとめ上げ(baseNPchunking)および英語の任意の句の同定(chunking)を例にとりながら学習手法としてSVMを用いた手法を述べる．さらに，chunkの表現方法が異なる複数の学習データから独立に学習し，それらの重み付き多数決を行うことでさらなる精度向上を試みる．その際，本稿では，各モデルの重みとしてSVMに固有の新たな2種類の重み付けの手法を提案する．本稿の構成は以下の通りである．2章でSVMの概要を説明し，3章で一般的なchunk同定モデルおよびSVMの具体的な適用方法，重み付け多数決の方法について述べる．さらに4章で実際のタグ付きコーパスを用いた評価実験を提示し，最後に5章で本稿をまとめる．
\section{SupportVectorMachine}
\subsection{最適分離平面}分類問題において，正例，負例の2つのクラスに属す学習データのベクトル集合を，\begin{eqnarray*}({\bfx}_i,y_i),\ldots,({\bfx}_l,y_l)\qquad{\bfx}_i\in{\bfR}^n,\,\,y_i\in\{+1,-1\}\end{eqnarray*}とする．ここで${\bfx}_i$はデータ$i$の特徴ベクトルで，一般的に$n$次元の素性ベクトル$({\bfx}_i=[f_1,f_2,\ldots,f_n]^T\in{\bfR}^n)$で表現される．$y_i$はデータ$i$が正例($+1$)あるいは負例($-1$)のいずれかを表わす値である．パターン認識とは，この学習データ${\bfx}_i\in{\bfR}^n$から，クラスラベル出力$y\in\{\pm1\}$への識別関数$f:{\bfR}^n\rightarrow\{\pm1\}$を導出することにある．SVMでは，以下のような$n$次元Euclid空間上の平面で正例，負例を分離することを考える．\begin{eqnarray}{\bfw}^T{\bfx}+b=0\qquad{\bfw}\in{\bfR}^n,b\in{\bfR}\label{eq:hyperplane}\end{eqnarray}この時，近接する正例と負例の間の間隔({\bfマージン})ができるだけ大きいほうが，汎化能力が高く，精度よく評価データを分類できる．図\ref{fig:hyperplane}に，2次元空間上の正例(白丸)，負例(黒丸)を分離する問題を例にこのマージン最大化の概略を表す．\begin{figure}\begin{center}\epsfxsize=7cm\epsfbox{hyperplane.eps}\caption{マージン最大化}\label{fig:hyperplane}\end{center}\end{figure}図\ref{fig:hyperplane}中の実線は式(\ref{eq:hyperplane})の分離平面を示す．一般にこのような分離平面は無数に存在し，図\ref{fig:hyperplane}に示す2つの分離平面はどちらも学習データを誤りなく分離している．分離平面に平行する2つの破線は分離平面が傾き${\bfw}$を変化させないまま平行移動したときに，分類誤りなく移動できる境界を示す．この2つの破線間の距離を{\bfマージン}と呼び，SVMはマージンが最大となる分離平面を求める戦略を採用している．図\ref{fig:hyperplane}の例では，右の分離平面が左の分離平面にくらべて大きなマージンを持っており，精度よくテスト事例を分離できることを意味している．実際に2つの破線を求めてみる．破線は，正例($+1$)もしくは負例($-1$)のラベルを出力する境界面になるように正規化を行えば，\begin{eqnarray*}&{\bfw}^T{\bfx}+b=\pm1\qquad{\bfw}\in{\bfR}^n,b\in{\bfR}\end{eqnarray*}で与えられる．さらにマージン$d$は，分離平面上の任意の点${\bfx'}$から各破線までの距離の和であり，${\bfx'}$は，${\bfw}^T{\bfx'}+b=0$を満たすため，\begin{eqnarray*}d&=&\frac{|{\bfw}^T{\bfx'}+b-1|}{\|{\bfw}\|}+\frac{|{\bfw}^T{\bfx'}+b+1|}{\|{\bfw}\|}=\frac{|-1|}{\|{\bfw}\|}+\frac{|1|}{\|{\bfw}\|}\nonumber\\&=&\frac{2}{\|{\bfw}\|}\end{eqnarray*}となる．このマージンを最大化するためには，$\|{\bfw}\|$を最小化すればよい．つまり，この問題は以下の制約付き最適化問題を解くことと等価となる\footnote{実際の我々の実験では多少の解析誤りを認めるSoftMarginの項を追加した最適化問題を解いている}．\begin{eqnarray*}&目的関数:&L({\bfw})=\frac{1}{2}\|{\bfw}\|^2\rightarrow最小化\\&制約条件:&y_i({\bfw}^T{\bfx}_i+b)\geq1\,\,(i=1\ldotsl)\end{eqnarray*}ここで，2つの破線上の分類を決定づける事例をサポートベクターと呼び，サポートベクター以外の事例は実際の学習結果に影響を及ぼさない．さらに，一般的な分類問題においては，学習データを線形分離することが困難な場合ある．このような場合，各素性の組み合わせを考慮し，より高次元な空間に学習データを写像すれば線形分離が容易になる．実際の証明は省略するがSVMの学習，分類アルゴリズムは事例間の内積しか使用しない．この点を生かし，各事例間の内積を任意のKernel関数におきかえることで，SVMは低次元中の非線形分類問題を高次元中の線形分離問題としてみなし分類を行うことが可能となっている．多くのKernel関数が提案されているが，我々は以下の式で与えられる$d$次の多項式Kernel関数を用いた．\begin{eqnarray*}K({\bfx}_i,{\bfx}_j)=({\bfx}_i^T{\bfx}_j+1)^d\label{eq:kernel_pol}\end{eqnarray*}$d$次の多項式関数は$d$個までの素性の組み合わせ(共起)を考慮した学習モデルと見なすことができる．\subsection{SVMの汎化能力}ここで，汎化能力に関する一般的な理論について考察する．学習データおよびテストデータがすべて独立かつ同じ分布$P({\bfx},y)$から生成されたと仮定すると，識別関数$f$のテストデータに対する汎化誤差$E_g[f]$，学習データに対する誤差$E_t[f]$は以下のように与えられる．\begin{eqnarray*}E_g[f]&=&\int\frac{1}{2}|f({\bfx})-y|dP({\bfx},y)\\E_t[f]&=&\frac{1}{l}\sum_{i=1}^{l}\frac{1}{2}|f({\bfx}_i)-y_i|\end{eqnarray*}さらに，$E_g[f],E_t[f]$には以下のような関係が成立することが知られている\cite{Vapnik98}．\newtheorem{theorem}{}\begin{theorem}[Vapnik]学習データの事例数を$l$，モデルのVC次元を$h$とする時，汎化誤差$E_g[f]$は，$1-\eta$の確率で以下の上限値を持つ．\begin{eqnarray}E_g[f]\leqE_t[f]+\sqrt{\frac{h(\ln\frac{2l}{h}+1)-\ln\frac{\eta}{4}}{l}}\label{eq:svm_gen}\end{eqnarray}\end{theorem}ここでVC次元$h$とは，モデルの記述能力，複雑さを表すパラメータである．式(\ref{eq:svm_gen})の右辺をVCboundと呼び，汎化誤差を小さくするには，VCboundをできるだけ小さくすればよい．従来からある多くの学習アルゴリズムは，モデルの複雑さであるVC次元$h$を固定し，学習データに対するエラー率を最小にするような戦略をとる．そのため，適切に$h$を選ばないとテストデータを精度良く分類できない．また適切な$h$の選択は一般的に困難である．一方SVMは，学習データに対するエラー率をSoftMarginやKernel関数を使って固定し，そのうえで右辺の第二項を最小化する戦略をとる．実際に式(\ref{eq:svm_gen})の右辺第二項に注目すると，$h$に対して増加関数となっている．つまり，汎化誤差$E_g(h)$を小さくするには，$h$をできるだけ小さくすればよい．SVMではVC次元$h$とマージン$M$には以下の関係が成立することが知られている\cite{Vapnik98}．\begin{theorem}[Vapnik]事例の次元数を$n$，マージンを$d$，全事例を囲む球面の最小直径を$D$とすると，SVMのVC次元$h$は，以下の上限値を持つ．\begin{eqnarray}h\leq\min(D^2/d^2,n)+1\label{eq:teiri}\end{eqnarray}\end{theorem}式(\ref{eq:teiri})から，$h$を最小にするためには，マージンを最大にすればよく，これはSVMがとる戦略そのものであることが分かる．また，学習データの次元数が十分大きければ，VC次元$h$は，学習データの次元数に依存しない．さらに，$D$は，使用するKernel関数によって決まるため，式(\ref{eq:teiri})はKernel関数の選択の指針を与える能力も持ちあわせていることが知られている\cite{Vapnik98}．また，Vapnikは式(\ref{eq:svm_gen})とは別に，SVMに固有のエラー率の上限を与えている．\begin{theorem}[Vapnik]$E_l[f]$を{\itLeave-One-Out}によって評価されるエラー率とする場合\begin{eqnarray}E_l[f]\leq\frac{サポートベクター数}{学習サンプル数}\label{eq:loo}\end{eqnarray}となる．\end{theorem}{\itLeave-One-Out}とは，$l$個の学習データのうち1個をとりのぞいてテストデータとし，残り$l-1$を使って学習することをすべてのデータについて$l$回繰り返すことで，未知データに対するエラー率を予測する手法である．式(\ref{eq:loo})は容易に証明可能である．つまり，SVMの特徴としてsupportvector以外の事例は最終の識別関数には一切影響を及ぼさない．そのため個々のsupportvectorすべてが誤ったときが最悪のケースとなり，式(\ref{eq:loo})が導かれる．このboundは，単純明解で汎化誤差のおおまかな値を予測することを可能にする．しかし，supportvectorの数が増えても汎化能力が向上する事例もあり，式(\ref{eq:loo})の汎化誤差の予測能力は式(\ref{eq:svm_gen})には劣ることが知られている．\vspace{-4mm}
\section{SVMに基づくChunk同定}
\subsection{Chunkの表現方法}Chunk同定の際，各chunkの状態をどう表現するかが問題となる．一つの手法として，各chunk同定を分割問題とみなし，各単語の間(ギャップ)にタグを付与する手法が考えられる．しかし，この手法は単語とは別の位置にタグを付与する必要があり，従来からある形態素解析などのタグ付けタスクとは異なる枠組が必要となる．その一方で，各単語にchunkの状態を示すタグを付与する手法がある．この手法は，従来からあるタグ付け問題と同じ枠組でモデル化ができる利点がある．後者の単語にタグを付与する表現法として，以下2種類の手法が提案されている．\begin{enumerate}\itemInside/Outside\\この手法は英語のbaseNP同定でよく用いられる手法の一つである\cite{Ramshaw95}．この手法では，chunkの状態として以下の3種類を設定する．\begin{tabular}{cl}I&現在位置の単語は，chunkの一部である．\\O&現在位置の単語は，chunkに含まれない．\\B&現在位置の単語は，あるchunkの直後に位置するchunkの先頭である．\\\end{tabular}\vspace*{5mm}さらにTjongKimSangらは，上記のモデルをIOB1と呼び，このモデルを基にIOB2/IOE1/IOE2の3種類の表現方法を提案している\cite{Tjong_Kim_Sang2000e}．\begin{tabular}{cp{34zw}}IOB2&IOB1と基本的に同じだが，Bタグの意味づけがことなる．IOB2の場合，Bタグはすべてのchunkの先頭に付与される．\\IOE1&IOB1と基本的に同じだが，Bタグの代わりにEタグを導入する．Eタグは，あるchunkの直前に位置するchunkの末尾の単語に付与される．\\IOE2&IOE1と基本的に同じだが，Eタグはすべてのchunkの末尾の単語に付与される．\end{tabular}\itemStart/End\\この手法は日本語固有名詞抽出において用いられた手法\cite{内元00}で，各単語に付与するタグとして以下の5種類を設定する\footnote{内元らは，C/E/U/O/Sの5種類のタグを用いているが，IOB1/IOB2/IOE1/IOE2モデルとの整合性から，便宜的にB/E/I/O/Sタグを用いる．タグの名称の変更のみで本質的なタグの意味づけに変更はない．}．\begin{tabular}{cp{34zw}}B&現在位置の単語は，2つ以上の単語から構成されるchunkの先頭の単語である．\\E&現在位置の単語は，2つ以上の単語から構成されるchunkの末尾の単語である．\\I&現在位置の単語は，3つ以上の単語から構成されるchunkの先頭，末尾以外の中間の単語である．\\S&現在位置の単語は単独で一つのchunkを構成する．\\O&現在位置の単語はchunkに含まれない\\\end{tabular}\end{enumerate}これら5種類のタグ付け手法を英語の単名詞句抽出(baseNPchunking)を例に以下に示す．\begin{center}\begin{tabular}{l|ccccc}&IOB1&IOB2&IOE1&IOE2&IOBES\\\hlineIn&O&O&O&O&O\\early&I&B&I&I&B\\trading&I&I&I&E&E\\in&O&O&O&O&O\\busy&I&B&I&I&B\\Hong&I&I&I&I&I\\Kong&I&I&E&E&E\\Monday&B&B&I&E&S\\,&O&O&O&O&O\\gold&I&B&I&E&S\\was&O&O&O&O&O\\\end{tabular}\end{center}各chunkに対し，そのchunkの役割を示すタグを付与する場合は，B/E/I/O/Sといったchunkの状態を示すタグと，役割を示すタグを'-'で連結し新たなタグを導入することによって表現する．例えば，IOB2モデルにおいて，動詞句(VP)の先頭の単語はB-VPというタグを付与すればよい．\subsection{SVMによるChunk同定}基本的にSVMは2値分類器である．そのため，chunkのタグ表現のように多値の分類問題を扱うためにはSVMに対し何らかの拡張を行う必要がある．一般に，2値分類器を多値分類器に拡張する手法として，以下に述べる2種類の手法がある．一つは，{\itoneclassvs.allothers}と呼ばれる手法で，$K$クラスの分類問題に対し，あるクラスかそれ以外かを分類する計$K$種類の分類器を作成する手法である．もう一つは，{\itpairwise}法であり，各クラス2つの組み合わせを分類する$K\times(K-2)/2$種類の分類器を作成し，最終的にそれらの多数決でクラスを決定する手法である．また，DietterichやAllweinらは，上記の二つを含む形で，二値分類を多値分類器に拡張するための統一的な手法を提案している\cite{dietterich95solving,allwein00reducing}．本稿では，多値分類器への拡張手法として{\itpairwise}法を採用した．採用の理由として以下が挙げられる．\begin{itemize}\item一般に，SVMは$O(n^2)\simO(n^3)$($n$は学習データのサイズ)の学習コストを要求する．そのために，個々の二値分類器に用いられる学習データのサイズが小さければ，学習コストを大幅に削減することができる．{\itpairwise}法は，{\itoneclassvs.others}に比べ多くの二値各分類器を作成するが，各二値分類器に用いられる学習データは少量であり，全体的に学習のコストを小さくすることができる．\item{\itpairwise}法が実験的に良い結果が得られたという報告\cite{Ulrich}がある．\end{itemize}chunkタグの学習に用いる素性としては，現在の単語およびその周辺の単語や品詞といった文脈を用いる．具体的には，位置$i$のchunkタグ$c_i$の推定を行う素性として$c_i$自身の単語と品詞，および右2つ，左2つの単語と品詞を用いた．また，左2つのchunkタグも素性として使用した．さらに，解析方向を逆(右向きから左向き)にし，右2つのchunkを素性として使用することも考えられる．本稿では，これら2つの解析手法を{\bf前向き解析/後ろ向き解析}と呼び区別する．\begin{center}\begin{tabular}{cccccc}&&$\rightarrow$&解析方向&$\rightarrow$&\\単語:&$w_{i-2}$&$w_{i-1}$&$w_{i}$&$w_{i+1}$&$w_{i+1}$\\品詞:&$t_{i-2}$&$t_{i-1}$&$t_{i}$&$t_{i+1}$&$t_{i+1}$\\chunk:&$c_{i-2}$&$c_{i-1}$&\fbox{$c_{i}$}\end{tabular}\end{center}一般に，左2つ(後ろ向きの場合は右2つ)のchunkタグは学習データに対しては付与されているが，テストデータに対しては付与されていない．そこで実際の解析時には，これらの素性は左から右向きに(後向きの場合は右から左に)解析しながら動的に追加していくこととした．このような処理は，一種の動的計画法(DP)と考えることができる．すなわち，全体として最尤なchunkタグ列は，各chunkタグに付与されるある種のスコアの和が最大になるようなタグ列を選択することにより決定される．さらに，動的計画法を行う際に，解析のビーム幅を指定することで曖昧性の候補の爆発を抑えることができる．CoNLL2000のsharedtaskにおいて，我々はスコアとしてpairwise時の投票数，また，ビーム幅を5として解析を行っている\cite{kudo2000a}．本稿では，このような曖昧性を考慮したビーム幅付きの解析は行わず，ビーム幅1の決定的な解析を行った．その理由としては以下が挙げられる．\begin{itemize}\item我々の詳細な調査の結果，ビーム幅を大きく設定しても，顕著な精度向上に繋がらず，決定的な解析でも十分な解析精度が得られることが分かった．\item本稿の目的は，後述する重み付き多数決の手法を比較することであり，単純な設定にすることで，個々の重み付け手法の相違点を明確にすることができる．\end{itemize}\subsection{重み付き多数決}重み付き多数決とは，1つの学習器で出力を得るのではなく，学習データ，学習データの表現方法，素性の選択手法，学習アルゴリズム，あるいは学習アルゴリズムのパラメータ等の異なる複数の学習器を線形結合して出力を得るアルゴリズムのことを指す．このような重み付き多数決の手法は，潜在的にマージン最大化の効果があり，汎化能力の高い強学習アルゴリズムを作成できることが理論的にも実験的にも明らかになっている．ここで，多数決がなぜ精度向上に繋がるのか，その簡単な証明を行う．重み付き多数決に用いる学習器の1つを$f_i\in{\bfR}$，さらに学習すべき対象(正解)を$t\in{\bfR}$とする．また，$f_i$の$M$個を均一な重み$1/M$で線形結合した学習器を$f'=\frac{1}{M}\sum_{i=1}^Mf_i$とする．この時，$f_i$と$t$，および$f'$と$t$の二乗誤差の期待値には以下のような関係が成立する．ただし$E[x]$は，$x$の期待値を表現する．\begin{eqnarray}E[(f'-t)^2]&=&E[\textstyle(\frac{1}{M}\textstyle\sum_{i=1}^Mf_i-t)^2]\nonumber\\&=&E[\textstyle\frac{1}{M}\textstyle\sum_{i=1}^M(f_i-t)^2-\frac{1}{M}\textstyle\sum_{i=1}^M(f_i-\frac{1}{M}\sum_{i=1}^Mf_i)^2]\nonumber\\&\leq&E[\textstyle\frac{1}{M}\sum_{i=1}^M(f_i-t)^2]\nonumber\\&=&E[(f_i-t)^2]\label{eq:w}\end{eqnarray}式\ref{eq:w}より，多数決を行った学習器の二乗誤差の期待値のが，単独に学習した学習器の期待値より小さくなることが分かる．ここでは，証明を簡単にするために均一な重みとしたが，不均一な重みの場合に対する一般化も可能である．詳細については文献\cite{Haykin99}を参照されたい．この重み付き多数決の概念の一つとしてBoosting\cite{Freund96}があり，自然言語処理の多くのタスクに応用され高い精度を示している．Chunk同定問題においても，重み付き多数決の手法が適用されている．例えば，TjongKimSangらは，baseNP同定の問題に対し，弱学習アルゴリズムにMBL，ME，IGTree等の7種類のアルゴリズム，さらにIOB1/IOB2/IOE1/IOE2の4種類の表現を用いて独立に学習した複数のモデルの重み付き多数決を行うことで，個々のモデルのどれよりも高精度の結果が得られたと報告している\cite{Tjong_Kim_Sang2000a,Tjong_Kim_Sang2000b}．本稿では，弱学習アルゴリズムにSVMを用い，IOB1/IOB2/IOE1/IOE2の4種類の表現，さらに解析方向(前向き/後ろ向き)の合計$4\times2=8$種類の重み付け多数決を行うことで精度向上を試みる．IOB1/IOB2/IOE1/IOE2には，それぞれ次のような特徴がある．IOB1/IOE2は，chunkが連続したときのみ他とは異なるタグ(B/E)が付与される．つまり，chunkが連続するような事例に特化した学習が行われる．また，IOB2/IOE2は，chunkの開始/終了位置に他とは違ったタグ(B/E)が付与される．これらは，chunkの開始/終了位置に特化した学習が行われるさらに，chunk中の主辞(Head)となる単語は，chunkの成立に必要不可欠であるために，他の単語に比べ頻出し，同定が容易である．主辞がchunkの先頭にある場合は，前向きに解析を行うことで，主辞が最初に決定され，その結果が後続するタグの素性に影響を及ぼすため，全体として高い精度が期待できる．逆に，主辞がchunkの末尾にある場合は，後ろ向きに解析を行ったほうが高い精度が得られる．前向き/後ろ向きとは，すべてのchunkの主辞が先頭/末尾にあると仮定し，それぞれの仮定に特化した学習手法である．このように，chunkの表現方法，及び解析方向の異なる複数の学習器を作成することで，それぞれ視点の異なる複数の学習器が作成される．一般に，複数の学習器の性質が異なれば異なるほど，多数決の結果の精度が高くなるために，単独のタグ表現方法，及び解析方向の手法より高い精度が期待できる．重み付き多数決を行う場合，各モデルの重みをどう決定するかが問題となる．真のテストデータに対する精度を用いることで良い結果を得ることができるが，一般に真のテストデータを評価することは不可能である．Boostingでは学習データの頻度分布を変更しながら，各ラウンドにおける学習データに対する精度を重みとしている．しかしながら，SVMは，SoftMarginパラメータ，Kernel関数の選択次第で，学習データを完全に分離することができ，単純に学習データに対する精度を重みにすることは困難である．本稿では，重み付き多数決の重みとして以下の4種類の手法を提案し，それぞれの手法の精度や計算量などを考察する．\begin{enumerate}\item{\bf均一重み}\\これは，すべてのモデルに対し均一の重みを付与する手法である．最も単純な手法であり，他の手法に対するベースラインとなる．\item{\bf交差検定}\\学習データを$N$等分し，$N-1$を学習データ，残りの$1$をテストとして評価する．この処理を$N$回行い，それぞれの精度の平均を各モデルの重みとして利用する．\item{\bfVCbound}\\式(\ref{eq:svm_gen})，式(\ref{eq:teiri})を用いてVCboundを計算し，その値から正解率の下限を推定し\footnote{エラー率の上限であるため，1からこの値を引き，正解率の下限とみなす．}，重みとする手法である．ただし，式(\ref{eq:teiri})における全事例を囲む最小直径$D$は各学習データから原点までのノルム最大値を用いて近似を行った．\begin{eqnarray*}D^2\sim\max_{i}\{K({\bfx}_i,{\bfx}_i)-2K({\bfx}_i,O)+K(O,O)\}\,\,\,\,(O:原点)\end{eqnarray*}\item{\bfLeave-One-Out(L-O-O)bound}\\式(\ref{eq:loo})のLeave-One-Outboundを求め，正解率の下限を推定し，重みとする手法である．\end{enumerate}実際の解析は以下のように行った．\begin{enumerate}\item学習データをIOB1/IOB2/IOE1/IOE2の各表現に変換する．\item4つの表現に対し，前向き解析，後ろ向き解析の計$4\times2=8$種類のモデルを作成し，SVMで独立に学習する．\item8種類のモデルに対し，VCbound，Leave-One-Outboundを計算し重みを求める．交差検定に関しては，(1)，(2)の処理を各分割したデータに対して行い，各ラウンドのタグ付け精度の平均を重みとする．実際の実験では，交差検定における分割数$N$は，5とした．\item合計8種類のモデルを用いて学習データとは別のテストデータを解析する．個々の8種類のモデルが出力するchunkの表現は，それぞれ異なるため，そのままでは多数決を行うことができない．多数決を行うためには，個々の結果を1つの統一表現に変換する必要がある．この目的のために，解析後のデータをIOB1/IOB2/IOE1/IOE2の各表現に再び変換する．\itemIOB1/IOB2/IOE1/IOE2の個々に変換された結果に対し，タグレベルで合計8種類の重みつき多数決を行う\footnote{実際にはchunkレベルで行わないとchunkの整合性が取れなくなる可能性があるが，本稿では問題を簡単にするためタグレベルで多数決を取ることとした}．つまり各重み付けの手法に対し，IOB1/IOB2/IOE1/IOE2の4種類の表現方法で評価した結果を得ることとなる．最終的に，$4$(統一表現のタイプ)$\times$$4$(重み付けの方法)$=16$種類の結果を得ることとなる．\end{enumerate}重み付き多数決の候補として，IOBES前向き解析とIOBES後向き解析の各モデルを参加させることは可能であるが，我々はそのような実験を行わなかった．その理由として，推定すべきクラスの数がIOB1，IOB2，IOE1，IOE2モデルは3に対し，IOBESモデルは5と異なり，VCboundや，Leave-One-Outboundを同じ条件で比較することが困難なことが挙げられる．IOBES前向き解析とIOBES後向き解析の各モデルの実験は，IOB1，IOB2，IOE1，IOE2の各モデルとの精度を比較するために行った．
\section{実験と考察}
\subsection{実験環境，設定}実験には以下の2種類のタグ付きデータを用いた．\begin{itemize}\itembaseNP標準データセット({\bfbaseNP})\\PennTree-bank/WSJの15-18を学習データ，00-14，19-24をテストデータとし，BrillTagger\cite{Brill95}を用いてpart-of-speech(POS)を付与したデータである．テストデータのサイズ以外は，baseNP抽出に用いられるデータとして一般的なものである．\itemChunkingデータセット({\bfchunking})\\baseNP標準データセットと基本的に同一であるが，baseNP以外に{\smallVP,PP,ADJP,ADVP,CONJP,INITJ,LST,PRT,SBAR}の合計10種類の英語の句を表現するタグが付与されている．テストデータのサイズを除けば，CoNLL-2000SheadTask\cite{Tjong_Kim_Sang2000c}と同一のデータである．\end{itemize}それぞれのデータのサイズを表\ref{fg:env}に示す．\begin{table}\begin{center}\begin{tabular}{r|r|r|r}\hline\hline&トークン(単語)数&chunk数&文数\\\hlinebaseNP学習データ&211,727&53,371&8,936\\baseNPテストデータ&962,039&248,656&40,272\\chunking学習データ&211,727&104,893&8,936\\chunkingテストデータ&962,039&483,301&40,272\\\end{tabular}\end{center}\caption{実験データ}\label{fg:env}\end{table}実験にはSVM学習パッケージ{\itTiny}SVMを用いた\footnote{http://cl.aist-nara.ac.jp/\~\,taku-ku/software/TinySVM/から入手可能}．このツールは，本実験のようなバイナリの素性表現に特化して高速化が施されており，VCboundを自動的に推定する機能を持っている．また，すべての実験において，Kernel関数は2次の多項式Kernelを使用した．評価方法としては，適合率と再現率の調和平均で与えられるF値($\beta=1$)を用いた．これはchunk同定において一般的に用いられる評価方法である．以後，特にことわらない限りF値のことを精度と呼ぶ．\subsection{実験結果}表\ref{fg:ind}に，各chunkの表現方法，および解析方向が異なる計8種のモデルで独立に学習した実験結果(テストデータに対する精度，推定された重み)をまとめた．また，比較対象として，Start/End法を用いた学習結果についても示している．さらに，表\ref{fg:voting}に，これらを均一重み，\,\,交差検定($N=5$)，\,\,VCbound，\,\,LeaveonOutboundの4種類の重み付けで多数決を行った際の結果をまとめた．表\ref{fg:best}には，各の重み付け手法の中の最良の結果について，その適合率と再現率を示す．\begin{table}\begin{center}\begin{tabular}{@{}c@{}@{}c@{}|p{2.4zw}|ccc@{}}\hline\hline\multicolumn{2}{c|}{学習条件}&\multicolumn{1}{c|}{精度}&\multicolumn{3}{c}{推定された重み}\\学習データ&変換先&$F_{\beta=1}$&交差検定&VCbound&L-O-Obound\\\hlinebaseNP&IOB1-前&94.04&.9394&.4310&.9193\\&IOB1-後&94.08&.9422&.4351&.9184\\&IOB2-前&94.13&.9410&.4415&.9172\\&IOB2-後&94.13&.9407&.4300&.9166\\&IOE1-前&93.91&.9386&.4274&.9183\\&IOE1-後&94.14&.9425&.4400&.{\bf9217}\\&IOE2-前&94.09&.9409&.4350&.9180\\&IOE2-後&{\bf94.23}&{\bf.9426}&{\bf.4510}&.9193\\\hlinechunking&IOB1-前&93.56&.9342&.6585&.9605\\&IOB1-後&93.58&.9346&.6614&.9596\\&IOB2-前&93.54&.9341&.6809&.9586\\&IOB2-後&93.52&.9355&.6722&.9594\\&IOE1-前&93.46&.9335&.6533&.9589\\&IOE1-後&{\bf93.65}&.9358&.6669&.9611\\&IOE2-前&93.50&.9341&.6740&{\bf.9606}\\&IOE2-後&{\bf93.65}&{\bf.9361}&{\bf.6913}&.9597\\\hline\hlinebaseNP&IOBES-前&93.93&&&\\&IOBES-後&93.94&&&\\\hlinechunking&IOBES-前&93.36&&&\\&IOBES-後&93.41&&&\\\end{tabular}\end{center}\caption{個々のモデルの精度比較}\label{fg:ind}\end{table}\begin{table}\begin{center}\begin{tabular}{@{}c@{}c|ccccc@{}}\hline\hline\multicolumn{2}{c|}{学習条件}&\multicolumn{4}{c}{各重み付けに対する精度$F_{\beta=1}$}\\学習データ&評価手法&均一重み&交差検定&VCbound&L-O-Obound\\\hlinebaseNP&IOB1&94.31&94.37&94.39&94.36\\&IOB2&94.33&94.39&{\bf94.41}&94.38\\&IOE1&94.32&94.38&94.38&94.36\\&IOE2&94.33&94.38&94.40&94.38\\\hlinechunking&IOB1&93.78&93.81&93.81&93.81\\&IOB2&93.74&{\bf93.84}&{\bf93.84}&{\bf93.84}\\&IOE1&93.79&93.81&93.81&93.81\\&IOE2&93.81&93.82&93.83&93.82\\\end{tabular}\end{center}\caption{重み付き多数決の結果}\label{fg:voting}\end{table}\begin{table}\begin{center}\begin{tabular}{c|ccc}\hline\hlineデータセット&適合率&再現率&$F_{\beta=1}$\\\hlinebaseNP&94.48\%&94.34\%&94.41\\chunking&93.85\%&93.83\%&93.84\\\end{tabular}\end{center}\caption{各データセットに対する最良結果}\label{fg:best}\end{table}\subsection{Chunkの表現方法と解析精度}表\ref{fg:ind}から，Inside/Outsideに基づく8つの手法を比較すると，「IOE2+後ろ向き」が最良の精度を，「IOE1+前向き」が最低の精度を示すことが分かる\footnote{chunkingデータセットの「IOE1+後ろ向き」以外は，「IOE2+後ろ向き」の結果が10\%の棄却率で有意であることが確認された．}．これは，以下に述べる我々の直観と合致する．\begin{itemize}\item多くの場合，chunk中の主辞は末尾の単語となる．すなわち，後ろ向きからから解析すると，主辞を最初に決定できるため優位となる．\\$\rightarrow$(後ろ向き$>$前向き)\itemIOEは，主辞となりやすいchunkの末尾に特化した学習が行われるため，先頭に特化するIOBに比べ優位となる．\\$\rightarrow$(IOE$>$IOB)\itemIOBは，chunkの先頭を，IOEは，chunkの末尾に特化して学習が行われる．そのため，IOBは，前向き，IOEは後ろ向きから解析すると特化して学習される単語が先に推定されるため，優位となる．\\$\rightarrow$(IOB+前向き$>$IOB+後ろ向き，IOE前向き$<$IOE後ろ向き)\item同一のchunkが連続することは稀である．すなわち，chunkの連続に特化するIOB1/IOE1は，chunkの先頭/末尾に特化するIOB2/IOE2に比べ劣る．\\$\rightarrow$(\{IOB1IOE1\}$<$\{IOB2IOE2\})\item同一chunkが連続する場合は，前のchunkの末尾の単語(主辞)よりはむしろ，後続するchunkの先頭の単語が境界の認定に役割を果たす場合が多い．そのため，chunkが連続する場合は，chunkの先頭に特化するIOB1がIOE1に比べ優位となる．\\$\rightarrow$(IOB1$>$IOE1)\end{itemize}次にInside/Outside法(IOB1/IOB2/IOE1/IOE2の各手法)とStart/End法の精度を比較する．颯々野らは，各学習アルゴリズムの特徴を考察しながら，決定リストについては細かい組み合せを考慮するStart/End法が，最大エントロピー方についてはより粗い情報を考慮するInside/Outside法が精度が良いと報告している\cite{Sassano00b}．SVMを用いた本手法では，全体的にInside/Outside法の法が，Start/Endに比べ高い精度を示している．SVMは，決定リストのように単独の素性(ルール)で分類するのではなく，最大エントロピーと同じく複数の素性の線型結合で分類するために，この結果は，颯々野らの分析と合致する．さらに，別の要因として以下が考えられる．まず，Start/Endは，5種類のタグを使い表現するため，Inside/Outsideと比較して，データスパースネスの問題を助長してしまう恐れがある．また，5種類のタグを使うことで，矛盾のあるタグのシーケンスの数が増えてしまう．具体的には，S→E，I→B，O→Iといったタグの連続は，タグ付けとしては不適切である．一方，IOB1は，O→Bのみ，IOB2はO→Iのみが不適切な連続である．タグ付けに関する指針，制約といった「タグ付けスキーマ」は，それらを明示的な形で与えない本手法では，システム自身がデータから学習する必要があり，それだけ余計なコストが生じてしまう．つまり，矛盾のあるタグ列が少ない表現方法が優位であると考える．\subsection{モデル選択能力}重み付き多数決を行う際の重みは，各システムの未知データに対する精度の予測値であるため，これらの大小を比較することでモデル選択が行える．表\ref{fg:ind}から，VCbound，交差検定，それぞれが「IOE2+後ろ向き」に対し最高の重みを，「IOE1+前向き」に最低の重みを算出しており，テストデータに対する精度をうまく予想してる．これらの結果から，VCbound，交差検定がモデル選択基準として良好に機能していることが分かる．交差検定はモデル選択に用いられる一般的な手法であるが，分割数が多くなると推定に多くの計算量を必要とする．その一方で，VCboundは学習と同時にモデル選択が行え，交差検定に比べ効率的であると考える．Leave-One-Outboundは他に比べ計算コストの小さいモデル選択手法であるが，その能力はVCboundや交差検定よりも劣ることが分かった．\subsection{多数決の効果}表\ref{fg:voting}から，多数決を行うことで，重みの付与方法によらず，単独のどのモデルよりも精度が向上することが確認できる\footnote{棄却率10\%以下で有意差があると判定された}．重み付き多数決の手法間の精度差には，多くの場合，顕著な差は見られなかった．特にVCbound，交差検定，Leave-One-Outboundは，ほぼ同等の精度となった．しかし，均一重みと比較して，上記の3つ手法で重みを推定するほうが，若干ながら優位であることが分かる．\subsection{関連研究との比較}\subsubsection{baseNPデータセット}TjongKimSangらは，弱学習アルゴリズムにMBL，ME，IGTree等の7種類のアルゴリズム，さらにIOB1/IOB2/IOE1/IOE2の4種類の表現を用いて独立に学習した複数のモデルの重み付き多数決を行うことで，baseNPデータセットに対し93.86の精度が得られたと報告している\cite{Tjong_Kim_Sang2000a,Tjong_Kim_Sang2000b}．我々は単独の表現を用いた場合でも93.91-94.23の精度を得ている．テストデータが異なるため，厳密な比較は行えないが，SVM単独の結果は，従来手法と同等だと考える．一方，従来手法は7種類の学習アルゴリズム，及び4つのchunk表現の異なるシステムの多数決の結果であり，個々の学習器の学習，及びテストの計算量は，SVM単独のシステムに比べ大きい．システムの複雑さという観点から見れば，SVM単独のシステムは，従来手法に比べ優位であると考える．さらに，従来手法と同様に，各表現の重み付き多数決を行うことで94.40の精度を得ることができた．これは，従来法の精度93.86に比べ優れていると考える．多数決を実行することは，全体としてシステムが複雑になることが一つの問題点である．TjongKimSangらによる手法は，MBL，ME，IGTreeといった，7種類のアルゴリズムを用いており，全体として複雑になっている．さらに，個々の学習器のパラメータは恣意的に設定されており，これらの最適なパラメータを考慮すると，設定すべきパラメータの数が多く，制御が困難であると考える．一方，本手法は，単一のSVMのみを用い，それ以外の学習アルゴリズムを用いていない．重み付き多数決を行うという観点から見れば，本手法は，従来手法に比べシステム全体の設計が，簡潔であり，設定すべきパラメータ数が少ない．この点も，本手法の優位な点と考える．\subsubsection{CoNLLデータセット}CoNLL-2000SharedTaskにおいて我々はSVMとIOB2と前向き解析の単独システム用いて93.48の精度を報告している\cite{kudo2000a}\footnote{テストデータが異なるため精度に若干差が出ている．}．本実験結果から，多数決を行うことで，「IOB2+前向き」に限らず，どの単独システムに比べても精度が向上している．またCoNLL-2000で報告された重み付き多数決に基づく他の手法\cite{Tjong_Kim_Sang2000d}よりも高い精度を示すことができた．\subsection{今後の課題}\begin{itemize}\item他の分野への応用\\我々の提案する手法は，日本語の文節まとめ上げや固有名詞，専門用語抽出と一般的なchunk同定問題に応用可能である．我々の提案する手法がこれらの他の分野でも有効であるか実際に検証を行う予定である．\item可変長モデル\\本稿では，左右2つの文脈のみを考慮する単純な固定長モデルを採用した．しかし実際には，個々のchunkを同定に必要な文脈長は可変であり，個々のchunkに対し最適な文脈長を選択することでさらなる精度向上が期待できる．颯々野らは日本語の固有名詞抽出において可変長モデルを提案し単純な固定長のモデルより高い精度が得られたと報告している\cite{Sassano00b}．今後このような可変長のモデルを取りいれたいと考えている．\itemより予測能力の高いboundの採用\\本稿では，重み付き多数決の重みとして，SVMに固有の概念---VCbound，Leave-One-Outboundを提案した．その一方でChapelleらは，これらより予測能力の高いboundを提案し，Kernel関数の選択やSoftMarginパラメータの選択に極めて有効であるとこを示している\cite{ChaVap00}．これらの予測能力の高いboundを重みとして採用することでさらなる精度向上が期待できる．\end{itemize}
\section{まとめ}
本稿では，SupportVectorMachine(SVM)に基づく一般的なchunk同定問題の解析手法を提案し，実際のタグ付きコーパスを用いて実験を行った．英語の単名詞句抽出における実験では，複数のシステム混合に基づく従来のモデルと同等の精度を示し，SVMの持つ高い汎化能力を裏づける結果となった．また，chunkの表現方法や解析方向の異なる複数のシステムの中から最適なものを選択するための「モデル選択基準」として，本稿で採用したVCboundは，従来からある交差検定と同程度の予測性能があることが確認された．VCboundは，交差検定のように学習を繰り返す必要がなく，学習と同時に計算が可能であるため，計算量の軽減に繋がる．さらに，chunkの表現方法や解析方向の異なる複数のシステムの重み付き多数決を行うことで，個々のどのモデルよりも高い精度を示した．\bibliographystyle{jnlpbbl}\bibliography{main}\begin{biography}\biotitle{略歴}\bioauthor{工藤拓}{1976年生．1999年京都大学工学部電気電子工学科卒，2001年奈良先端科学技術大学院大学情報科学研究科博士前期課程修了，同年同大学院博士後期課程に進学．専門は統計的自然言語処理．機械学習，統計的手法に興味を持つ．}\bioauthor{松本裕治}{1955年生．1977年京都大学工学部情報工学科卒．1979年同大学大学院工学研究科修士課程情報工学専攻修了．同年電子技術総合研究所入所．1984〜85年英国インペリアルカレッジ客員研究員．1985〜87年(財)新世代コンピュータ技術開発機構に出向．京都大学助教授を経て，1993年より奈良先端科学技術大学院大学教授，現在に至る．工学博士．専門は自然言語処理．情報処理学会，日本ソフトウェア科学会，言語処理学会，認知科学会，AAAI，ACL，ACM各会員}\bioreceived{受付}\biorevised{再受付}\biorerevised{再々受付}\bioaccepted{採録}\end{biography}\end{document}