\section{はじめに}
\label{sec:introduction}電子化されたテキストが利用可能になるとともに，階層的文書分類の自動化が試みられてきた．階層的分類の対象となる文書集合の例としては，特許\footnote{http://www.wipo.int/classifications/en/}，医療オントロジー\footnote{http://www.nlm.nih.gov/mesh/}，Yahoo!やOpenDirectoryProject\footnote{http://www.dmoz.org/}のようなウェブディレクトリが挙げられる．文書に付与すべきラベルは，タスクによって，各文書に1個とする場合と，複数とする場合があるが，本稿では複数ラベル分類に取り組む．階層的分類における興味の中心は，あらかじめ定義されたラベル階層をどのように自動分類に利用するかである．そもそも，大量のデータを階層的に組織化するという営みは，科学以前から人類が広く行なってきた．例えば，伝統社会における生物の分類もその一例である．そこでは分類の数に上限があることが知られており，その制限は人間の記憶容量に起因する可能性が指摘されている\cite{Berlin1992}．階層が人間の制約の産物だとすると，そのような制約を持たない計算機にとって，階層は不要ではないかと思われるかもしれない．階層的分類におけるラベル階層の利用という観点から既存手法を整理すると，まず，非階層型と階層型に分けられる．非階層型はラベル階層を利用しない手法であり，各ラベル候補について，入力文書が所属するか否かを独立に分類する．ラベル階層を利用する階層型は，さらに2種類に分類できる．一つはラベル階層を候補の枝刈りに用いる手法（枝刈り型）である．典型的には，階層を上から下にたどりながら局所的な分類を繰り返す\cite{Montejo2006,Qiu2009full,Wang2011IJCNLPfull}．枝刈りにより分類の実行速度をあげることができるため，ラベル階層が巨大な場合に有効である．しかし，局所的な分類を繰り返すことで誤り伝播が起きるため，精度が低下しがちという欠点が知られている\cite{Bennett2009}．もう一つの手法はパラメータ共有型である．この手法では，ラベル階層上で近いラベル同士は似通っているので，それらを独立に分類するのではなく，分類器のパラメータをラベル階層に応じて部分的に共有させる\cite{Qiu2009full}．これにより分類精度の向上を期待する．これらの既存手法は，いずれも複数ラベル分類というタスクの特徴を活かしていない．複数ラベル分類では，最適な候補を1個採用すればよい単一ラベル分類と異なり，ラベルをいくつ採用するかの加減が人間作業者にとっても難しい．我々は，人間作業者が出力ラベル数を加減する際，ラベル階層を参照しているのではないかと推測する．例えば，科学技術文献を分類する際，ある入力文書が林業における環境問題を扱っていたとする．この文書に対して，「林業政策」と「林業一般」という2個のラベルは，それぞれ単独でみると，いずれもふさわしそうである．しかし，両者を採用するのは内容的に冗長であり，よりふさわしい「林業政策」だけを採用するといった判断を人間作業者はしているかもしれない．一方，別のラベル「環境問題」は「林業政策」と内容的に競合せず，両方を採用するのが適切を判断できる．この2つの異なる判断は，ラベル階層に対応している．「林業政策」と「林業一般」は最下位層において兄弟関係にある一方，「林業政策」と「環境問題」はそれぞれ「農林水産」と「環境工学」という異なる大分類に属している．このように，我々は，出力すべき複数ラベルの間にはラベル階層に基づく依存関係があると仮定する．そして，計算機に人間作業者の癖を模倣させることによって，（それが真に良い分類であるかは別として）人間作業者の分類を正解としたときの精度が向上することを期待する．本稿では，このような期待に基づき，ラベル間依存を利用する具体的な手法を提案する．まずは階層型複数ラベル文書分類を構造推定問題として定式化し，複数のラベルを同時に出力する大域モデルと，動的計画法による厳密解の探索手法を提案する．次に，ラベル間依存を表現する枝分かれ特徴量を導入する．この特徴量は動的計画法による探索が維持できるように設計されている．実験では，ラベル間依存の特徴量の導入により，精度の向上とともに，モデルの大きさの削減が確認された．本稿では，\ref{sec:task}節で問題を定義したうえで，\ref{sec:proposed}節で提案手法を説明する．\ref{sec:experiments}節で実験結果を報告する．\ref{sec:related-work}節で関連研究に言及し，\ref{sec:conclusion}節でまとめと今後の課題を述べる．
\section{問題設定}
\label{sec:task}階層型複数ラベル文書分類では，与えられた文書に対して，それをもっともよく表すラベルの集合$\mathcal{M}\subset\mathcal{L}$を返す．ここで，$\mathcal{L}$はあらかじめ定義されたラベルの集合である．$\mathcal{L}$は図\ref{fig:tree}のように木構造で組織化されているとする\footnote{いくつかの既存研究では，有向非循環グラフ(directedacyclicgraph,DAG)を扱っている\cite{Labrou1999,LSHTC3}．有向非循環グラフでは，木と異なり，ノードが一般に複数の親を持ち得る．有向非循環グラフへの対応は今後の課題とし，本稿では木構造に対象をしぼる．}．また，付与対象のラベルは葉のみであり，内部ノードはラベルとならないとする．図\ref{fig:tree}の場合，$\mathrm{AA}$，$\mathrm{AB}$，$\mathrm{BA}$および$\mathrm{BB}$がラベル候補となる．\begin{figure}[b]\begin{center}\includegraphics{21-1ia3f1.eps}\end{center}\caption{ラベル階層の例（灰色の葉のみが付与対象のラベル）}\label{fig:tree}\end{figure}いくつかの記法を整理しておく．$\mathrm{leaves}(c)$は，$c$の子孫である葉の集合を返す．例えば，$\mathrm{leaves}(\mathrm{A})=\{\mathrm{AA},\mathrm{AB}\}$．ただし，$c$自身が葉の場合は，$\mathrm{leaves}(c)=\{c\}$．$p\rightarrowc$は親$p$から子$c$への辺を表す．$\mathrm{path}(c)$は$\mathrm{ROOT}$と$c$を結ぶ辺の集合を返す．例えば，$\mathrm{path}(\mathrm{AB})=\{\mathrm{ROOT}\rightarrow\mathrm{A},\mathrm{A}\rightarrow\mathrm{AB}\}$．また，$\mathrm{tree}(\mathcal{M})=\bigcup_{l\in\mathcal{M}}\mathrm{path}(l)$とする．これは$\mathcal{M}$を被覆する最小の部分木に対応する．例えば，$\mathrm{tree}(\{\mathrm{AA},\mathrm{AB}\})=\{\mathrm{ROOT}\rightarrow\mathrm{A},\mathrm{A}\rightarrow\mathrm{AA},\mathrm{A}\rightarrow\mathrm{AB}\}$．文書$x$は$\phi(x)$により特徴量ベクトルに変換される．特徴量として，例えば，文書分類タスクで一般な単語かばん(bag-of-words)手法を用いることができる．本タスクは教師あり設定であり，訓練データ$\mathcal{T}=\{(x_i,\mathcal{M}_i)\}_{i=1}^T$が与えられる．$\mathcal{T}$を用いてモデルを訓練し，これとは別のテストデータによって性能を評価する．
\section{提案手法}
\label{sec:proposed}\subsection{大域モデル}ラベル間依存を利用するための準備として，入力文書$x$に対して出力ラベル集合$\mathcal{M}$を同時に推定する大域モデルを提案する．具体的には，階層的複数ラベル文書分類を構造推定問題とみなし，$\mathcal{M}$が作る部分木に対してスコアを定義する．\[\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})=\vect{w}^{\mathrm{global}}\cdot\Phi^{\mathrm{global}}(x,\mathrm{tree}(\mathcal{M}))\]$\vect{w}^{\mathrm{global}}$は重みベクトルであり，訓練データを用いて学習すべきパラメータである．$\vect{w}^{\mathrm{global}}$は，辺に対応する局所的な重みベクトルを連結することにより構成される．例えば，図\ref{fig:tree}の場合は\[\vect{w}^{\mathrm{global}}=\vect{w}_{\mathrm{ROOT}\rightarrow\mathrm{A}}\oplus\vect{w}_{\mathrm{ROOT}\rightarrow\mathrm{B}}\oplus\vect{w}_{\mathrm{A}\rightarrow\mathrm{AA}}\oplus\vect{w}_{\mathrm{A}\rightarrow\mathrm{AB}}\oplus\vect{w}_{\mathrm{B}\rightarrow\mathrm{BA}}\oplus\vect{w}_{\mathrm{B}\rightarrow\mathrm{BB}}\]となる．特徴関数$\Phi^{\mathrm{global}}$は，文書$x$と$\mathrm{tree}(\mathcal{M})$を入力とし，$\vect{w}^{\mathrm{global}}$と同次元のベクトルを返す．具体的には，各$p\rightarrowc\in\mathrm{tree}(\mathcal{M})$に対応する部分ベクトルに$\phi(x)$を，残りの要素に$0$を入れた特徴量ベクトルを返す．したがって，$\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})$は以下のように書き換えられる．\[\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})=\sum_{p\rightarrowc\in\mathrm{tree}(\mathcal{M})}\vect{w}_{p\rightarrowc}\cdot\phi(x)\]この定式化により，$\vect{w}^{\mathrm{global}}$が与えられた時，部分木のスコアを最大化する$\mathcal{M}$を探す問題となる．\[\argmax_{\mathcal{M}}\quad\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})\]\subsection{動的計画法による解探索}\begin{algorithm}[t]\caption{$\mbox{\scmaxtree}(x,p)$}\label{alg:bu-search}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\REQUIRE文書$x$,木のノード$p$\ENSUREラベル集合$\mathcal{M}$,スコア$s$\STATE$\mathcal{U}\leftarrow\{\}$\FORALL{$p$の各子$c$}\IF{$c$が葉}\STATE$\mathcal{U}\leftarrow\mathcal{U}\cup\{(\{c\},\vect{w}_{p\rightarrowc}\cdot\phi(x))\}$\ELSE\STATE$(\mathcal{M}^\prime,s^\prime)\leftarrow\mbox{\scmaxtree}(x,c)$\STATE$\mathcal{U}\leftarrow\mathcal{U}\cup\{(\mathcal{M}^\prime,s^\prime+\vect{w}_{p\rightarrowc}\cdot\phi(x))\}$\ENDIF\ENDFOR\STATE$\mathcal{R}\leftarrow\{(\mathcal{M}^\prime,s^\prime)\in\mathcal{U}|s^\prime>0\}$\IF{$\mathcal{R}$が空}\STATE$\mathcal{R}\leftarrow\{(\mathcal{M}^\prime,s^\prime)\}$ただし，$(\mathcal{M}^\prime,s^\prime)$は$\mathcal{U}$のなかで$s^\prime$が最大のもの\ENDIF\STATE$\mathcal{M}\leftarrow\bigcup_{(\mathcal{M}^\prime,s^\prime)\in\mathcal{R}}\mathcal{M}^\prime$\STATE$s\leftarrow\sum_{(\mathcal{M}^\prime,s^\prime)\in\mathcal{R}}s^\prime$\RETURN$(\mathcal{M},s)$\end{algorithmic}\end{algorithm}大域モデルの，現在のパラメータ$\vect{w}^{\mathrm{global}}$のもとでの厳密解は，動的計画法により効率的に求められる．Algorithm~\ref{alg:bu-search}に動的計画法の擬似コードを示す．$\mbox{\scmaxtree}(x,p)$は，$p$を根とする部分木の集合から，スコアが最大のものを再帰的に探索する．したがって，我々が呼び出すのは$\mbox{\scmaxtree}(x,\mathrm{ROOT})$である．子$c$は，(1)$c$を根とするスコア最大の部分木を作るラベル集合，および(2)そのスコアとひも付けされている．ただし，葉のスコアは0である．$p$から見た$c$のスコアは，$c$の部分木のスコアと辺$p\rightarrowc$のスコアの和である（3--8行目）．$p$の部分木のスコアを最大にするには，正のスコアを持つ$c$をすべて採用すればよい（10行目）．いずれの子も正のスコアを持たない場合は，最大のスコアを持つ子を1個採用する（11--13行目）．採用された子の集合により，$p$のラベル集合とスコアが決定される（14--15行目）．このアルゴリズムの拡張としては，上位$N$個の候補集合を出すというものが考えられる．木に対する動的計画法としては，構文解析\cite{McDonald2005full}よりもはるかに簡単なため，上位$N$個への拡張\cite{Collins2005}もさほど難しくない．\subsection{ラベル間依存の利用}\label{sec:proposed-branch}以上の準備により，ラベル間依存を利用する条件が整った．ラベル間依存の捕捉は，大域モデルに対する特徴量の追加により実現される．具体的には，あるノードがいくつの子を採用しやすいかを制御する枝分かれ特徴量を導入する．枝分かれ特徴量は$\phi^{\mathrm{BF}}(p,k)$により表される．ここで$p$は根あるいは内部ノードであり，$k$は$p$が採用する子の数である．ただし，あらゆる$k$の値に対して特徴量を設けると疎になるため，ある$R$について，$R+1$個($1,\cdots,R$もしくは$>R$)の特徴量に限定する．さらに，ノードごとの特徴量だけでなく，すべての根あるいは内部のノードが共有する$R+1$個の特徴量も設ける．つまり，追加される特徴量は$(I+1)(R+1)$個であり，各ノードに対して2個の特徴量が発火する．ここで，$I$はラベル階層における根および内部ノードの個数とする．\begin{algorithm}[t]\caption{枝分かれ特徴量を組み込むための修正（Algorithm\ref{alg:bu-search}の10--15行目を以下で置き換える）}\label{alg:bu-branch}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\setcounter{ALC@line}{9}\STATE$r\leftarrow\mathcal{U}$を$s$により降順にソートした配列\STATE$\mathcal{R}^\prime\leftarrow\{\}$,\quad$s^\prime\leftarrow0$,\quad$\mathcal{M}^\prime\leftarrow\{\}$\FOR{$k=1..\mbox{sizeof$r$}$}\STATE$(\mathcal{M},s)\leftarrowr[k]$\STATE$s^\prime\leftarrows^\prime+s$,\quad$\mathcal{M}^\prime\leftarrow\mathcal{M}^\prime\cup\mathcal{M}$\STATE$\mathcal{R}^\prime\leftarrow\mathcal{R}^\prime\cup\{(\mathcal{M}^\prime,s^\prime+\vect{w}^{\mathrm{BF}}\cdot\phi^{\mathrm{BF}}(p,k))\}$\ENDFOR\STATE$(\mathcal{M},s)\leftarrow$$\mathcal{R}^\prime$のなかでスコア$s$が最大の要素\end{algorithmic}\end{algorithm}この枝分かれ特徴量は，動的計画法による厳密解探索が維持できるように設計されている．この特徴量を組み込むには，Algorithm~\ref{alg:bu-search}の10--15行目をAlgorithm~\ref{alg:bu-branch}で置き換えればよい．枝分かれ特徴量のスコア$\vect{w}^{\mathrm{BF}}\cdot\phi^{\mathrm{BF}}(p,k)$は$k$のみに依存する．そこで，まずは採用する子の数$k$によって候補をグループ分けし，各グループのなかでスコアが最大の候補を選ぶ（12--16行目）．最後に，異なるグループ同士を比較し，スコアが最大となる候補を採用する（17行目）．グループ内でスコアが最大の候補を選ぶには，子をスコア順に並べ，上位$k$個を採用すれば良い．候補のスコアは，$p$から見た各子のスコアと枝分かれ特徴量のスコアの和となる（15行目）．枝分かれ特徴量の導入により，ラベルの採否の判断が，ラベル同士の相対的な比較によって行われるようになる．\ref{sec:introduction}節で触れた，「林業政策」と「環境問題」というラベルが付与された文書を再び例に挙げる．この文書に対して「林業一般」というラベルはそれほど不適切には見えないが，枝分かれ特徴量を持たないモデルは，「林業一般」を付与{\bfしない}理由を，$\phi(x)$に対応する重みですべて説明しなければならない．\ref{sec:discussion}節で示すように，枝分かれ特徴量の重みは，一般に，負の値を持ち，ペナルティとして働く．また，子の数が増えるにつれてペナルティが増えるように学習される．したがって，子を2個採用するとよりペナルティがかかるので，「林業一般」に対応する重みを無理に引き下げることなく，相対的により適切な「林業政策」のみを採用することが可能となる．\subsection{大域訓練}大域モデルの訓練手法をここでは大域訓練と呼ぶ．本稿では，パーセプトロン系のオンライン学習アルゴリズムを採用する．具体的には，構造推定問題に対するPassive-Aggressiveアルゴリズム\cite{Crammer2006}を用いる．Passive-Aggressiveを採用した理由としては，実装の簡便さ，バッチ学習と異なり，大量の訓練データに容易に対応可能なオンライン学習であること，次節で述べるように並列分散化が容易に実現できることが挙げられる．ただし，これは提案手法がパーセプトロン系アルゴリズムでしか実現できないことを意味せず，構造化SVM~\cite{Tsochantaridis:ICML2004}を含む他の構造学習アルゴリズムの導入も検討に値する．\begin{algorithm}[t]\caption{大域訓練のためのPassive-Aggressiveアルゴリズム（PA-I，予測ベース更新）}\label{alg:pa-global}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\REQUIRE訓練データ$\mathcal{T}=\{(x_i,\mathcal{M}_i)\}_{i=1}^T$\ENSURE重みベクトル$\vect{w}^{\mathrm{global}}$\STATE$\vect{w}^{\mathrm{global}}\leftarrow\vect{0}$\FOR{$n=1..N$}\STATE$\mathcal{T}$をシャッフル\FORALL{$(x,\mathcal{M})\in\mathcal{T}$}\STATE$\hat{\mathcal{M}}\leftarrow\argmax_{\mathcal{M}}\,\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})$\STATE$\rho\leftarrow1-2|\mathcal{M}\cap\hat{\mathcal{M}}|/(|\mathcal{M}|+|\hat{\mathcal{M}}|)$\IF{$\rho>0$}\STATE$l\leftarrow\mathrm{score}^{\mathrm{global}}(x,\hat{\mathcal{M}})-\mathrm{score}^{\mathrm{global}}(x,\mathcal{M})+\sqrt{\rho}$\STATE$\tau\leftarrow\min\{C,\frac{l}{\norm{\Phi^{\mathrm{global}}(x,\mathrm{tree}(\mathcal{M}))-\Phi^{\mathrm{global}}(x,\mathrm{tree}(\hat{\mathcal{M}}))}^2}\}$\STATE$\vect{w}^{\mathrm{global}}\leftarrow\vect{w}^{\mathrm{global}}+\tau(\Phi^{\mathrm{global}}(x,\mathrm{tree}(\mathcal{M}))-\Phi^{\mathrm{global}}(x,\mathrm{tree}(\hat{\mathcal{M}})))$\ENDIF\ENDFOR\ENDFOR\end{algorithmic}\end{algorithm}大域モデルの場合の擬似コードをAlgorithm~\ref{alg:pa-global}に示す．ここで，$N$は訓練の反復数を表し，パラメータ$C$は$1.0$とする．現在のパラメータにおける厳密解は上述の動的計画法により求まる（5行目）．予測を誤った場合，正解ラベル集合を出力する方向に重みを更新する（10行目）．ここで，コスト$\rho$はモデル予測の誤り度合いを表し，重みの更新幅を変化させる．$\rho$は，正解ラベル集合とシステムの出力の一致の度合いに基づいている．\subsection{大域訓練の並列分散化}\label{sec:proposed-parallel}大域訓練には学習が非常に遅いという欠点がある．ラベル集合の分類はラベル1個の2値分類とは比較にならないほど遅い．しかも，大域訓練はモデルを一枚岩とするため，モデルを局所分類器に分割して並列化することができない．そこで，繰り返しパラメータ混ぜ合わせ法~\cite{McDonald2010full}を用いて並列分散化を行う．基本的な考えは，モデルを分割する代わりに，訓練データを分割することで並列化を行うというものである．別々の訓練データ断片から学習されたモデル群を繰り返し混ぜ合わせることで収束性を保証している．Algorithm~\ref{alg:ipm}に繰り返しパラメータ混ぜ合わせ法の擬似コードを示す．ここで$N^\prime$は繰り返しパラメータ混ぜ合わせ法の反復数，$S$は訓練データの分割数を表す．繰り返しパラメータ混ぜ合わせ法では，断片ごとに並列に訓練を行う．各反復の最後に，並列に訓練された複数のモデルを平均化する．次の反復では，この平均化されたモデルを初期値として用いる．繰り返しパラメータ混ぜ合わせ法はパーセプトロン向けに提案されたものである．しかし，\cite{McDonald2010full}が言及している通り，Passive-Aggressiveアルゴリズムに対しても収束性を証明することができる．\begin{algorithm}[t]\caption{繰り返しパラメータ混ぜ合わせ法による大域訓練}\label{alg:ipm}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\REQUIRE訓練データ$\mathcal{T}=\{(x_i,\mathcal{M}_i)\}_{i=1}^T$\ENSURE重みベクトル$\vect{w}^{\mathrm{global}}$\STATE$\mathcal{T}$を$\mathcal{T}_1,\cdots\mathcal{T}_S$に分割\STATE$\vect{w}^{\mathrm{global}}\leftarrow\vect{0}$\FOR{$n=1..N^\prime$}\FOR{$s=1..S$}\STATE$\vect{w}_s^{\mathrm{global}}\leftarrow$非同期的にAlgorithm\ref{alg:pa-global}を呼び出す．ただしいくつかの修正を加える．$\mathcal{T}$を$\mathcal{T}_s$で置き換える．$\vect{w}^{\mathrm{global}}$を$\vect{0}$ではなく$\vect{w}^{\mathrm{global}}$で初期化する．反復数を$N=1$とする．\ENDFOR\STATE非同期処理の終了を待つ\STATE$\vect{w}^{\mathrm{global}}\leftarrow\frac{1}{S}\sum_{s=1}^S\vect{w}_s^{\mathrm{global}}$\ENDFOR\end{algorithmic}\end{algorithm}\begin{figure}[t]\begin{center}\includegraphics{21-1ia3f2.eps}\end{center}\caption{JSTPlusの文書例}\label{fig:jstplus-example}\end{figure}
\section{実験}
\label{sec:experiments}\subsection{データ}評価データとしてJSTPlus\footnote{http://jdream3.com/service/jdream.html}を用いる．JSTPlusは科学技術振興機構が作成している科学技術文献のデータベースである．各文書は，標題，抄録，著者一覧，ジャーナル名，分類コード一覧や，その他数多くの項目からなる．文書例を図\ref{fig:jstplus-example}に示す．実験では，標題と抄録を文書分類に用いるテキストとし，分類コードを付与すべきラベルとみなす．また，2010年の文献のうち，日本語の標題と日本語の抄録の両方を含むものを実験の対象とした．その結果，455,311件の文書を得た．これを409,892件の訓練データと45,419件の評価データに分割した．ラベル（分類コード）は3,209個からなり，これは4,030個の辺に対応する．ラベル階層は，根を除いて，最大で5階層となっている．ただし，いくつかの辺は中間層を飛ばす（例えば，第2層のノードの子が第4層にある場合がある）．各文書は平均で1.85個のラベルが付与されている（分散は0.85）．文書ごとの最大ラベル数は9である．文書の特徴関数$\phi(x)$には以下の2種類の特徴量を用いる．\begin{enumerate}\itemジャーナル名．2値特徴量で，各文書につき1個の特徴量が発火する．\item標題と抄録中の内容語．値は頻度．ただし，標題中の内容語の頻度は2倍する．\end{enumerate}内容語抽出には，形態素解析器JUMAN\footnote{http://nlp.ist.i.kyoto-u.ac.jp/index.php?JUMAN}および構文解析器KNP\footnote{http://nlp.ist.i.kyoto-u.ac.jp/index.php?KNP}を用いた．まずJUMANによって各文を単語列に分割し，次にKNPが持つ規則を使って内容語にタグ付けした．各文書は平均で380文字を含んでいた．これは内容語としては120語に相当する．\subsection{モデル設定}\label{sec:experiments-model}大域訓練で訓練された大域モデル({\bfGM-GT})について，枝分かれ特徴量({\bfBF})を用いた場合と用いなかった場合を比較する．大域モデルの繰り返しパラメータ混ぜ合わせ法については，訓練データを10個の断片に分割し，反復数は$N^\prime=10$とする．枝分かれ特徴量について，$R=3$とする．その他の比較対象として，従来研究を参考にして以下のモデルを用いる．\subsubsection{非階層型}\label{sec:experiments-model-flat}非階層型({\bfFLAT})はラベル階層を無視し，各ラベル$l$を文書$x$に付与すべきか否かを独立に決定する．そのために各$l$に対して2値分類器を用意する．分類器の実装手法としては，ナイーブベイズ，ロジスティック回帰，サポートベクタマシンなどが用いられてきたが，本稿では，提案手法との比較のためにPassive-Aggressiveアルゴリズム~\cite{Crammer2006}を用いる．ラベル$l$に対する2値分類器は重みベクトル$\vect{w}_{l}$を持つ．スコア$\vect{w}_{l}\cdot\phi(x)$が正のとき，$l$を$x$に付与する．ただし，文書に対して最低1個のラベルを付与する．そのために，いずれのラベルも正のスコアを取らない場合は，一番高いスコアを持つラベルを1個採用する．$\vect{w}_l$を訓練するために，元の訓練データ$\mathcal{T}$を以下のようにして$\mathcal{T}_l$に変換する．\[\mathcal{T}_l=\left\{(x_i,y_i)\left|\begin{array}{l@{\hspace{0em}}l}y_i=+1&\quad\mbox{if$l\in\mathcal{M}_i$}\\y_i=-1&\quad\mbox{otherwise}\end{array}\right.\right\}_{i=1}^T\]各文書はラベル$l$を持つとき正例，そうでなければ負例となる．擬似コードをAlgorithm~\ref{alg:pa-binary}に示す．ここで，パラメータ$C$は$1.0$とする．訓練の反復数は$N=10$とする．なお，各2値分類器は独立なので，訓練は容易に並列化できる．\begin{algorithm}[t]\caption{2値分類器に対するPassive-Aggressiveアルゴリズム(PA-I)}\label{alg:pa-binary}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\REQUIRE訓練データ$\mathcal{T}_l=\{(x_i,y_i)\}_{i=1}^T$\ENSURE重みベクトル$\vect{w}_l$\STATE$\vect{w}_l\leftarrow\vect{0}$\FOR{$n=1..N$}\STATE$\mathcal{T}_l$をシャッフル\FORALL{$(x,y)\in\mathcal{T}_l$}\STATE$l\leftarrow\max\{0,1-y(\vect{w}_{l}\cdot\phi(x))\}$\IF{$l>0$}\STATE$\tau\leftarrow\min\{C,\frac{l}{\norm{\phi(x)}^2}\}$\STATE$\vect{w}_l\leftarrow\vect{w}_l+\tauy\phi(x)$\ENDIF\ENDFOR\ENDFOR\end{algorithmic}\end{algorithm}\subsubsection{枝刈り型}\label{sec:experiments-model-ls}枝刈り型({\bfPRUNE})はラベル階層を利用する手法であり，ラベル階層に対応する2値分類器の集合を持つ\cite{Montejo2006,Wang2011IJCNLPfull,Sasaki2012}\footnote{ラベル階層に対応する2値分類器の集合を使う他の手法としては，\cite{Punera2008}が階層上の等調回帰により，局所分類器の出力を後処理している．}．各2値分類器はラベル階層上の辺$p\rightarrowc$とひも付けされ，重み$\vect{w}_{p\rightarrowc}$を持つ．$\vect{w}_{p\rightarrowc}\cdot\phi(x)>0$は，$x$を$p$のいずれかの子孫に割り当てるべきであることを表す．これらの2値分類器も並列に訓練できる．パラメータ$C$の値，訓練の反復数は非階層型と同じとする．枝刈り型には誤り伝播\cite{Bennett2009}とよばれる問題が知られている．すなわち，階層上位の分類器による誤りから回復する手段がないため，累積的に誤りが作用する．誤り伝播を軽減するために様々な手法が提案されているが，煩雑さを避けるため，本稿では，Algorithm~\ref{alg:td-search}に示す単純な実装を採用する．各ノード$p$において，局所分類器が正のスコアを返す子すべてを採用する（4--7行目）．ただし，いずれの子も正のスコアを得ない場合は，一番高いスコアを得た子を1つ採用する（8--10行目）．この操作を葉に到達するまで繰り返す．2値分類器の訓練データ$\mathcal{T}_{p\rightarrowc}$の構築方法としては，以下の2種類を試す．\paragraph{ALL}\hspace{1zw}全訓練データを利用する\cite{Punera2008}．\[\mathcal{T}_{p\rightarrowc}=\left\{(x_i,y_i)\left|\begin{array}{ll}y_i=+1&\mbox{if$\existsl\in\mathcal{M}_i,l\in\mathrm{leaves}(c)$}\\y_i=-1&\mbox{otherwise}\end{array}\right.\right\}_{i=1}^T\]各文書は$c$のいずれかの子孫のラベルが割り当てられていれば正例，そうでなければ負例となる．\paragraph{SIB}\hspace{1zw}正例は{\bfALL}と同じだが，負例を$c$の兄弟の子孫が割り当てられている場合に限定する．\[\mathcal{T}_{p\rightarrowc}=\left\{(x,y)\left|\begin{array}{ll}y=+1&\mbox{if$\existsl\in\mathcal{M}$},l\in\mathrm{leaves}(c)\\y=-1&\mbox{if$\existsl\in\mathcal{M}$},l\in\mathrm{leaves}(p)\,\mbox{かつ}\,l\notin\mathrm{leaves}(c)\end{array}\right.\right\}\]こうすることで，全体として小さなモデルが学習される．なぜなら，数の多い階層下位の分類器に与えられる訓練データが小さくなるからである．従来研究では{\bfSIB}を採用する場合が多い\cite{Liu2005,Wang2011IJCNLPfull,Sasaki2012}．\begin{algorithm}[t]\caption{枝刈り型探索}\label{alg:td-search}\DeclarePairedDelimiter\norm{\lVert}{\rVert}\renewcommand{\algorithmicrequire}{}\renewcommand{\algorithmicensure}{}\algsetup{indent=1.2em}\setlength{\baselineskip}{11pt}\begin{algorithmic}[1]\REQUIRE文書$x$\ENSUREラベル集合$\mathcal{M}$\STATE$q\leftarrow[\mathrm{ROOT}]$,\,$\mathcal{M}\leftarrow\{\}$\WHILE{$q$が空でない}\STATE$p\leftarrow$$q$の最初の要素を取り出す,\,$\vect{t}\leftarrow\{\}$\FORALL{$p$の子である$c$}\STATE$\vect{t}\leftarrow\vect{t}\cup\{(c,\vect{w}_{p\rightarrowc}\cdot\phi(x))\}$\ENDFOR\STATE$\mathcal{U}\leftarrow\{(c,s)\in\vect{t}|s>0\}$\IF{$\mathcal{U}$が空}\STATE$\mathcal{U}\leftarrow\{(c,s)\}$,ただし$c$は$p$の子のなかで一番高いスコア$s$を持つ\ENDIF\FORALL{$(c,s)\in\mathcal{U}$}\IF{$c$が葉}\STATE$\mathcal{M}\leftarrow\mathcal{M}\cup\{c\}$\ELSE\STATE$c$を$q$に追加\ENDIF\ENDFOR\ENDWHILE\end{algorithmic}\end{algorithm}\subsection{評価尺度}\label{sec:experiments-measures}複数ラベル分類に対する評価尺度は数多く存在するが，大きく2種類に整理できる．1つは，文書を単位とした評価尺度で，しばしば用例ベースの尺度とよばれる\cite{Godbole2004,Tsoumakas2010full}．文書単位の尺度として，適合率(EBP)，再現率(EBR)およびF値(EBF)が以下のように定義される．{\allowdisplaybreaks\begin{gather*}\mathrm{EBP}=\frac{1}{T}\sum_{i=1}^T\frac{|\mathcal{M}_i\cap\hat{\mathcal{M}}_i|}{|\hat{\mathcal{M}}_i|}\\\mathrm{EBR}=\frac{1}{T}\sum_{i=1}^T\frac{|\mathcal{M}_i\cap\hat{\mathcal{M}}_i|}{|\mathcal{M}_i|}\\\mathrm{EBF}=\frac{1}{T}\sum_{i=1}^T\frac{2|\mathcal{M}_i\cap\hat{\mathcal{M}}_i|}{|\hat{\mathcal{M}}_i|+|\mathcal{M}_i|}\end{gather*}}ここで$T$はテストデータ中の文書数，$\mathcal{M}_i$は$i$番目の文書の正解ラベル集合，$\hat{\mathcal{M}}_i$はそれに対応するシステムの出力とする．もう一つは，ラベルを単位とした評価尺度で，通常の適合率，再現率およびF値が用いられる．ただし，複数のラベルの集計方法としてマクロ平均とマイクロ平均がある\cite{Tsoumakas2010full}．そのため合計で，LBMaP，LBMaR，LBMaF，LBMiP，LBMiRおよびLBMiFの6種類の尺度を用いる．最後に階層的な評価も行う\cite{Kiritchenko2005}．これは，出力ラベルがラベル階層上において正解と近いときに「部分点」を与えるものである．今回のように循環がない木構造を仮定した場合，適合率(hP)および再現率(hR)は以下のように定義される．\begin{gather*}\mathrm{hP}=\frac{\sum_{i=1}^T|\mathrm{tree}(\mathcal{M}_i)\cap\mathrm{tree}(\hat{\mathcal{M}}_i)|}{\sum_{i=1}^T|\mathrm{tree}(\hat{\mathcal{M}}_i)|}\\\mathrm{hR}=\frac{\sum_{i=1}^T|\mathrm{tree}(\mathcal{M}_i)\cap\mathrm{tree}(\hat{\mathcal{M}}_i)|}{\sum_{i=1}^T|\mathrm{tree}(\mathcal{M}_i)|}\end{gather*}F値(hF)はhPとhRの調和平均として定義される．\begin{table}[b]\caption{モデルの比較結果}\label{tb:experiments-summary}\input{03table01.tex}\end{table}\subsection{結果}各種モデルの精度比較を表\ref{tb:experiments-summary}に示す．枝分かれ特徴量を組み込んだ大域モデル({\bfGM-GT-BF})が7種類の尺度で最高精度を得た．枝分かれ特徴量なしのモデル({\bfGM-GT})と比較すると，EBP，LBMaR以外の尺度で{\bfGM-GT-BF}が上回り，すべてのF値を改善した．この改善は統計的に有意($p<0.01$)であった．大域モデルを非階層型({\bfFLAT})と比較すると，適合率の改善が著しい一方，再現率に大きな差は見られない．2種類の枝刈り型({\bfPRUNE})を比較すると，兄弟のみで訓練する場合({\bfSIB})の方が全体的にやや良い精度が得られた．しかし，多くの尺度で非階層型に敗れており，従来研究の結果を再現する形となっている．誤り例を見ると，誤って採用したラベル，誤って採用しなかったラベルのいずれも，正解ラベルから離れて人間として改めて判断すると，必ずしも誤りとは言い切れない場合が少なくなかった．特に，該当文書にとって周辺的な話題を表すラベルをどこまで採用べきかを判断するのが難しかった．なお，モデル間の分類結果の差分からは，明確な誤り，改善の傾向をつかむのは困難であった．時間はテストデータの分類に要した時間であり，モデルの読み込み時間は含まない\footnote{実験では8コアIntelXeon2.70~GHzCPUの1コア，64~GBのメモリを用い，実装にはPerlを用いた．}．予想される通り，枝刈り型が圧倒的に速い．{\bfGM-GT-BF}は{\bfPRUNE-ALL}と比較して約60倍の時間を要した．しかし，{\bfFLAT}と比較すると，階層を利用するにも関わらず，約18\%の増加にとどまっている．これは，{\bfGM-GT-BF}のモデルの大きさが{\bfFLAT}よりも約16\%小さいことで説明できるかもしれない．モデルの大きさは重みベクトル中で，絶対値が$10^{-7}$より大きい要素の数とする．大きさは{\bfPRUNE-SIB}が最小で，{\bfPRUNE-ALL}が最大となった．{\bfGM-GT-BF}が{\bfGM-GT}よりも大きさを約9\%削減したことは特筆に値する．訓練に用いたPassive-Aggressiveアルゴリズムには重みを0につぶそうとする仕組みがないことから，大きさが削減された理由は，学習過程で{\bfGM-GT-BF}が{\bfGM-GT}よりも予測を誤る回数が少なかったからと考えられる．このように，より小さなモデルでより高い精度が得られたことは，出力すべき複数ラベルの間にはラベル階層に基づく依存関係があるという我々の仮定を支持するものと考える．\subsection{議論}\label{sec:discussion}大域モデルの重み$\vect{w}^{\mathrm{global}}$自体は，大域訓練({\bfGT})だけでなく，枝刈り型で用いた2値分類器群を連結することによっても構成できる({\bfLT})．大域モデルの性質をさらに調べるために，こうしたモデルとの比較も行った．表\ref{tb:experiments-dp}に大域モデルの訓練方法の比較結果を示す．訓練データとして{\bfSIB}を用いた場合，極端に多くの候補を出力するようになり，その結果，極端に低い適合率と高い再現率を得た．{\bfSIB}という限定されたデータで訓練された局所的な分類器に対して，大域モデルが未知の文書の分類を行わせたため，このような不安定な振る舞いとなった．一方，訓練データとして{\bfALL}を用いた場合，枝刈り型({\bfPRUNE-ALL})から精度を大幅に向上させ，大域訓練とくらべても遜色のない精度が得られた．モデルの大きさや分類速度において大域訓練に劣りはするものの，大域モデルの最適化を行わずにこのような高精度が得られたことは興味深い．これは，訓練手法に改善の余地があることを示唆する．本稿では10並列による繰り返しパラメータ混ぜ合わせ法を用いたが，今後の最適化技術の発展が期待される．\begin{table}[b]\vspace*{-1\Cvs}\caption{大域モデルの訓練方法の比較}\label{tb:experiments-dp}\input{03table02.tex}\end{table}\begin{table}[b]\caption{訓練データにおける精度}\label{tb:experiments-training}\input{03table03.tex}\end{table}表\ref{tb:experiments-training}に訓練データに対する精度を示す．訓練データに対しては非階層型({\bfFLAT})が一番高い精度を示し，{\bfALL}により局所訓練された大域モデル({\bfGM-LT-ALL})がそれに続いた．大域訓練を行った場合({\bfGM-GT-BF})との比較から，局所訓練が過学習をもたらしているとみられる．また，局所訓練と大域モデルの組み合わせにより，枝刈り型探索が誤りの主要因であることが確認できた．すなわち，{\bfPRUNE-ALL}を訓練データに適用したところ，33\%の文書について，{\bfPRUNE-ALL}が出力したラベル集合よりも，正解ラベル集合の方が大域モデルにおいて高いスコアを持っていた．言い換えると，正しく探索を行えば犯さない誤りであった．ただし，この高い数値には過学習の影響も含まれており，同じ操作をテストデータに適用した場合は，割合は14\%に下がった\footnote{ラベル階層が大規模で厳密解探索が難しいといった理由で，枝刈り型探索をAlgorithm\ref{alg:pa-global}の訓練に用いる場合，探索誤りから生じる「非侵害」問題に対処しなければならない．すなわち，モデル予測$\hat{\mathcal{M}}$が正解$\mathcal{M}$よりも低いスコアを持つ場合，重みベクトルの更新が無効となってしまう．この問題に対処するための手法がいくつか提案されている~\cite{Collins2004full,Huang2012full}．}．\begin{figure}[b]\begin{center}\includegraphics{21-1ia3f3.eps}\end{center}\caption{辺ごとのモデルの大きさとスコアの比較}\label{fig:size-score-comp}\end{figure}より詳細にモデルを調べるために，辺に分解した結果を示す．図\ref{fig:size-score-comp}は{\bfGT-BF}，{\bfLT-ALL}，{\bfLT-SIB}の比較である．図(a)から(c)は辺に対応する局所ベクトルの大きさを示す．ここで，大きさの定義は表\ref{tb:experiments-summary}と同じである．辺を子の階層によって集約し，大きさを平均した結果を示す．一般に，上位階層ほど多数の有効な重みベクトルが必要となることが確認できる．{\bfGT-BF}は{\bfLT-ALL}よりも大きさが小さいが，辺ごとの大きさの比率は似通っている．{\bfLT-SIB}と比較すると，{\bfGT-BF}は上位階層では小さいが，下位階層では大きな有効重みベクトルを持つ．{\bfLT-SIB}では兄弟からの識別のみを考慮していたが，大域学習ではすべての辺が適切なスコアを返す必要があるため，有効重みベクトルがより大きくなったとみられる．図(d)から(f)は，各辺が得たスコアの絶対値の平均を表す．ここで，スコアは，テストデータに対するモデル出力から計算されたものである．これにより，どの階層の辺が強くモデル出力に影響しているかが推測できる．この結果から，上位階層ほど大きな影響を持つことがわかる．しかし，{\bfGT-BF}は他とくらべて上位階層の影響が小さい．すなわち，{\bfGT-BF}においては下位階層の辺が相対的に重要な役割を果たしている．枝分かれ特徴量に対応する重みを図\ref{fig:br-heatmap}にヒートマップとして示す．各要素の値は，親ノードに与えられた重み（ノードごとの重みと共有された重みの和）を平均したものである．平均化された値はすべて負となり，子の数が増えるにつれてペナルティが単調増加した．異なる階層間の重みの比較は，それらが重みベクトルの他の部分の値に依存するため難しい．しかし，下位ノードほど子の数に応じた重みの落差が大きいという結果は，階層上近いラベル候補同士ほど強い競合関係にあるという我々の仮説を支持しているようにみえる．最後に，訓練データおよび評価データの正解ラベルについて，正解ラベルを被覆する最小の部分木を作り，親が採用する子の数を調べた．採用した子の数が複数である割合は，根で34.9\%，第1層で10.1\%，第2層で4.6\%，第3層で1.5\%，第4層で0.6\%であり，下位ノードほど強い競合関係にあることが確認できた．\begin{figure}[t]\begin{center}\includegraphics{21-1ia3f4.eps}\end{center}\caption{枝分かれ特徴量のヒートマップ表現}\label{fig:br-heatmap}\end{figure}
\section{関連研究}
\label{sec:related-work}階層型文書分類において，枝刈り型が非階層型にしばしば敗れることが報告されており，誤り伝播を軽減するために様々な手法が提案されてきた．\cite{Sasaki2012}は枝刈り探索時の枝刈り基準を緩め，最後に候補の枝刈りを行う．すなわち，Algorithm~\ref{alg:td-search}の7行目の閾値を$0$から$-0.2$などに引き下げて，より多くの候補を採用する．最後に，各候補について，根から葉までのパスの（シグモイド関数で変換された）局所スコアの和を取り，これに閾値を設定することによって出力ラベルを絞り込む．S-cut~\cite{Montejo2006,Wang2011IJCNLPfull}は，一律の閾値を用いるのではなく，局所分類器ごとに閾値を設定する手法である．R-cutは上位$r$個の候補を採用する手法で，選び方には大域的手法\cite{Liu2005,Montejo2006}と局所的手法\cite{Wang2011IJCNLPfull}がある．\cite{Wang2011IJCNLPfull}は採用されたラベル候補をメタ分類器にかけ，最終的な出力を決定する．メタ分類器の特徴量としては，根から葉までの局所スコアやその累積などを用いる．本稿ではこれらを総称して後付け補正とよぶ．後付け補正では，いずれもモデルあるいは探索が本質的に不完全であることを想定し，追加のパラメータによる補正を行なっている．そうしたパラメータは，人手で設定するか，あるいは訓練データとは別に開発データを用意して推定しなければならず煩雑である．一方，提案手法には後付け補正は不要であり，モデル自体の改善に専念できる．ラベル階層を下から上へ探索しながら候補を探すという点で，提案手法と似た手法が\cite{Bennett2009}により提案されている．しかし，彼らの手法では，大域モデルも大域訓練も用いられていない．代わりに，階層下位の分類器のスコアが上位の分類器のメタ特徴量として用いられている．分類器の訓練は局所的に行われ，煩雑な交差確認を必要とする．本稿ではあらかじめ定義されたラベル階層を利用した．そうした手がかりがない場合にラベル間依存を捉えるための手法も研究されている．\cite{Ghamrawi:CIKM2005full,Miyao:COLING2008full}は，出力すべきラベル集合中のラベルペアを特徴量に組み込んでいる．本稿のようにラベル階層が利用できる場合は，それをもとに限られた数のラベル同士の関係を考慮すればすむ．一方，ラベル階層がない場合は，モデルはすべてのラベルペアを考慮する必要があり，訓練および解探索に大きな計算コストを要する．こうしたモデルの検証は，ラベルの異なり数が数十程度のデータセットを用いて行われてきた．ラベルの異なり数が大きな場合について，\cite{Tai:2012full}は，ラベル集合を低次元の直交座標系に写像し，この空間上で非階層型の分類器を学習する手法を提案している．予測時には，分類器の出力を元の空間へ写像するという自明でない復号が必要となる．\cite{Bi:ICML2011}は，ラベル階層を組み込むために，木あるいは有向非循環グラフの制約を満たすような復号手法を提案している．
\section{おわりに}
\label{sec:conclusion}本稿では，階層型複数ラベル文書分類を構造推定問題として定式化し，動的計画法による厳密解探索方法，大域訓練，ラベル間依存をとらえる枝分かれ特徴量を提案した．枝分かれ特徴量はモデルの大きさを削減するとともに精度の向上をもたらした．この結果は，人間作業者が複数のラベル候補から出力を選択する際，ラベル階層に基づいて，競合する候補の相対的な重要性を考慮していることを示唆する．今後の方向性としては，枝分かれ特徴量以外によってラベル間依存をとらえる方法を探究するというものが考えられる．例えば，「〜その他」や「〜一般」といったラベルは，他のラベルとの関係において特殊な振る舞いをすると予想される．また，本稿では葉のみが付与対象ラベルという問題設定を行ったが，従来研究には内部ノードも付与対象である場合を扱ったものがある~\cite{Liu2005}．こうした内部ノードの振る舞いも特殊である．内部ノードを採用するとき，その子孫へのラベル付与を行わないことが多い．さらに，木構造から有向非循環グラフへの提案手法の一般化も課題である．\acknowledgment本研究で評価実験に用いたJSTPlusは，共同研究を通じて，独立行政法人科学技術振興機構に提供していただきました．深く感謝いたします．本研究は一部JSTCRESTの支援を受けました．\bibliographystyle{jnlpbbl_1.5}\begin{thebibliography}{}\bibitem[\protect\BCAY{Bennett\BBA\Nguyen}{Bennett\BBA\Nguyen}{2009}]{Bennett2009}Bennett,P.~N.\BBACOMMA\\BBA\Nguyen,N.\BBOP2009\BBCP.\newblock\BBOQRefinedExperts:ImprovingClassificationinLargeTaxonomies.\BBCQ\\newblockIn{\BemProceedingsofthe32ndInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'09)},\mbox{\BPGS\11--18}.\bibitem[\protect\BCAY{Berlin}{Berlin}{1992}]{Berlin1992}Berlin,B.\BBOP1992\BBCP.\newblock{\BemEthnobiologicalClassification:PrinciplesofCategorizationofPlantsandAnimalsinTraditionalSocieties}.\newblockPrincetonUniversityPress.\bibitem[\protect\BCAY{Bi\BBA\Kwok}{Bi\BBA\Kwok}{2011}]{Bi:ICML2011}Bi,W.\BBACOMMA\\BBA\Kwok,J.\BBOP2011\BBCP.\newblock\BBOQMulti-LabelClassificationonTree-and{DAG}-StructuredHierarchies.\BBCQ\\newblockIn{\BemProceedingsofthe28thInternationalConferenceonMachineLearning(ICML-11)},\mbox{\BPGS\17--24}.\bibitem[\protect\BCAY{Collins\BBA\Koo}{Collins\BBA\Koo}{2005}]{Collins2005}Collins,M.\BBACOMMA\\BBA\Koo,T.\BBOP2005\BBCP.\newblock\BBOQDiscriminativeRerankingforNaturalLanguageParsing.\BBCQ\\newblock{\BemComputationalLinguistics},{\Bbf31}(1),\mbox{\BPGS\25--70}.\bibitem[\protect\BCAY{Collins\BBA\Roark}{Collins\BBA\Roark}{2004}]{Collins2004full}Collins,M.\BBACOMMA\\BBA\Roark,B.\BBOP2004\BBCP.\newblock\BBOQIncrementalParsingwiththe{P}erceptronAlgorithm.\BBCQ\\newblockIn{\BemProceedingsofthe42ndMeetingoftheAssociationforComputationalLinguistics(ACL'04),MainVolume},\mbox{\BPGS\111--118}.\bibitem[\protect\BCAY{Crammer,Dekel,Keshet,Shalev-Shwartz,\BBA\Singer}{Crammeret~al.}{2006}]{Crammer2006}Crammer,K.,Dekel,O.,Keshet,J.,Shalev-Shwartz,S.,\BBA\Singer,Y.\BBOP2006\BBCP.\newblock\BBOQOnlinePassive-AggressiveAlgorithms.\BBCQ\\newblock{\BemJournalofMachineLearningResearch},{\Bbf7},\mbox{\BPGS\551--585}.\bibitem[\protect\BCAY{Ghamrawi\BBA\McCallum}{Ghamrawi\BBA\McCallum}{2005}]{Ghamrawi:CIKM2005full}Ghamrawi,N.\BBACOMMA\\BBA\McCallum,A.\BBOP2005\BBCP.\newblock\BBOQCollectiveMulti-labelClassification.\BBCQ\\newblockIn{\BemCIKM'05:Proceedingsofthe14thACMInternationalConferenceonInformationandKnowledgeManagement},\mbox{\BPGS\195--200}.\bibitem[\protect\BCAY{Godbole\BBA\Sarawagi}{Godbole\BBA\Sarawagi}{2004}]{Godbole2004}Godbole,S.\BBACOMMA\\BBA\Sarawagi,S.\BBOP2004\BBCP.\newblock\BBOQDiscriminativeMethodsforMulti-labeledClassification.\BBCQ\\newblockInDai,H.,Srikant,R.,\BBA\Zhang,C.\BEDS,{\BemAdvancesinKnowledgeDiscoveryandDataMining},\lowercase{\BVOL}\3056of{\BemLectureNotesinComputerScience},\mbox{\BPGS\22--30}.SpringerBerlinHeidelberg.\bibitem[\protect\BCAY{Huang,Fayong,\BBA\Guo}{Huanget~al.}{2012}]{Huang2012full}Huang,L.,Fayong,S.,\BBA\Guo,Y.\BBOP2012\BBCP.\newblock\BBOQStructured{P}erceptronwithInexactSearch.\BBCQ\\newblockIn{\BemProceedingsofthe2012ConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics:HumanLanguageTechnologies},\mbox{\BPGS\142--151}.\bibitem[\protect\BCAY{Kiritchenko}{Kiritchenko}{2005}]{Kiritchenko2005}Kiritchenko,S.\BBOP2005\BBCP.\newblock{\BemHierarchicalTextCategorizationandItsApplicationtoBioinformatics}.\newblockPh.D.\thesis,UniversityofOttawa.\bibitem[\protect\BCAY{Labrou\BBA\Finin}{Labrou\BBA\Finin}{1999}]{Labrou1999}Labrou,Y.\BBACOMMA\\BBA\Finin,T.\BBOP1999\BBCP.\newblock\BBOQYahoo!asanOntology:Using{Y}ahoo!CategoriestoDescribeDocuments.\BBCQ\\newblockIn{\BemProceedingsoftheEighthInternationalConferenceonInformationandKnowledgeManagement(CIKM'99)},\mbox{\BPGS\180--187}.\bibitem[\protect\BCAY{Liu,Yang,Wan,Zeng,Chen,\BBA\Ma}{Liuet~al.}{2005}]{Liu2005}Liu,T.-Y.,Yang,Y.,Wan,H.,Zeng,H.-J.,Chen,Z.,\BBA\Ma,W.-Y.\BBOP2005\BBCP.\newblock\BBOQSupportVectorMachinesClassificationwithaVeryLarge-scaleTaxonomy.\BBCQ\\newblock{\BemSIGKDDExplorationsNewsletter},{\Bbf7}(1),\mbox{\BPGS\36--43}.\bibitem[\protect\BCAY{LSHTC3}{LSHTC3}{2012}]{LSHTC3}LSHTC3\BED\\BBOP2012\BBCP.\newblock{\BemECML/PKDD-2012DiscoveryChallengeWorkshoponLarge-ScaleHierarchicalTextClassification}.\bibitem[\protect\BCAY{McDonald,Crammer,\BBA\Pereira}{McDonaldet~al.}{2005}]{McDonald2005full}McDonald,R.,Crammer,K.,\BBA\Pereira,F.\BBOP2005\BBCP.\newblock\BBOQOnlineLarge-MarginTrainingofDependencyParsers.\BBCQ\\newblockIn{\BemProceedingsofthe43rdAnnualMeetingoftheAssociationforComputationalLinguistics(ACL'05)},\mbox{\BPGS\91--98}.\bibitem[\protect\BCAY{McDonald,Hall,\BBA\Mann}{McDonaldet~al.}{2010}]{McDonald2010full}McDonald,R.,Hall,K.,\BBA\Mann,G.\BBOP2010\BBCP.\newblock\BBOQDistributedTrainingStrategiesfortheStructured{P}erceptron.\BBCQ\\newblockIn{\BemHumanLanguageTechnologies:The2010AnnualConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics},\mbox{\BPGS\456--464}.\bibitem[\protect\BCAY{Miyao\BBA\Tsujii}{Miyao\BBA\Tsujii}{2008}]{Miyao:COLING2008full}Miyao,Y.\BBACOMMA\\BBA\Tsujii,J.\BBOP2008\BBCP.\newblock\BBOQExactInferenceforMulti-labelClassificationusingSparseGraphicalModels.\BBCQ\\newblockIn{\BemColing2008:Companionvolume:Posters},\mbox{\BPGS\63--66}.\bibitem[\protect\BCAY{Montejo-R{\'a}ez\BBA\Ure{\~n}a-L{\'o}pez}{Montejo-R{\'a}ez\BBA\Ure{\~n}a-L{\'o}pez}{2006}]{Montejo2006}Montejo-R{\'a}ez,A.\BBACOMMA\\BBA\Ure{\~n}a-L{\'o}pez,L.~A.\BBOP2006\BBCP.\newblock\BBOQSelectionStrategiesforMulti-labelTextCategorization.\BBCQ\\newblockIn{\BemAdvancesinNaturalLanguageProcessing},\mbox{\BPGS\585--592}.Springer.\bibitem[\protect\BCAY{Punera\BBA\Ghosh}{Punera\BBA\Ghosh}{2008}]{Punera2008}Punera,K.\BBACOMMA\\BBA\Ghosh,J.\BBOP2008\BBCP.\newblock\BBOQEnhancedHierarchicalClassificationviaIsotonicSmoothing.\BBCQ\\newblockIn{\BemProceedingsofthe17thInternationalConferenceonWorldWideWeb(WWW'08)},\mbox{\BPGS\151--160}.\bibitem[\protect\BCAY{Qiu,Gao,\BBA\Huang}{Qiuet~al.}{2009}]{Qiu2009full}Qiu,X.,Gao,W.,\BBA\Huang,X.\BBOP2009\BBCP.\newblock\BBOQHierarchicalMulti-LabelTextCategorizationwithGlobalMarginMaximization.\BBCQ\\newblockIn{\BemProceedingsoftheACL-IJCNLP2009ConferenceShortPapers},\mbox{\BPGS\165--168}.\bibitem[\protect\BCAY{Sasaki\BBA\Weissenbacher}{Sasaki\BBA\Weissenbacher}{2012}]{Sasaki2012}Sasaki,Y.\BBACOMMA\\BBA\Weissenbacher,D.\BBOP2012\BBCP.\newblock\BBOQ{TTI'S}Systemforthe{LSHTC}3Challenge.\BBCQ\\newblockIn{\BemECML/PKDD-2012DiscoveryChallengeWorkshoponLarge-ScaleHierarchicalTextClassification}.\bibitem[\protect\BCAY{Tai\BBA\Lin}{Tai\BBA\Lin}{2010}]{Tai:2012full}Tai,F.\BBACOMMA\\BBA\Lin,H.-T.\BBOP2010\BBCP.\newblock\BBOQMulti-labelClassificationwithPrincipalLabelSpaceTransformation.\BBCQ\\newblockIn{\BemProceedingsofthe2ndInternationalWorkshoponLearningfromMulti-LabelData},\mbox{\BPGS\45--52}.\bibitem[\protect\BCAY{Tsochantaridis,Hofmann,Joachims,\BBA\Altun}{Tsochantaridiset~al.}{2004}]{Tsochantaridis:ICML2004}Tsochantaridis,I.,Hofmann,T.,Joachims,T.,\BBA\Altun,Y.\BBOP2004\BBCP.\newblock\BBOQ{S}upport{V}ector{M}achineLearningforInterdependentandStructuredOutputSpaces.\BBCQ\\newblockIn{\BemProceedingsoftheTwenty-firstInternationalConferenceonMachineLearning(ICML'04)},\mbox{\BPGS\104--113}.\bibitem[\protect\BCAY{Tsoumakas,Katakis,\BBA\Vlahavas}{Tsoumakaset~al.}{2010}]{Tsoumakas2010full}Tsoumakas,G.,Katakis,I.,\BBA\Vlahavas,I.\BBOP2010\BBCP.\newblock\BBOQMiningMulti-labelData.\BBCQ\\newblockInMaimon,O.\BBACOMMA\\BBA\Rokach,L.\BEDS,{\BemDataMiningandKnowledgeDiscoveryHandbook},\mbox{\BPGS\667--685}.Springer.\bibitem[\protect\BCAY{Wang,Zhao,\BBA\Lu}{Wanget~al.}{2011}]{Wang2011IJCNLPfull}Wang,X.-L.,Zhao,H.,\BBA\Lu,B.-L.\BBOP2011\BBCP.\newblock\BBOQEnhanceTop-downMethodwithMeta-ClassificationforVeryLarge-scaleHierarchicalClassification.\BBCQ\\newblockIn{\BemProceedingsof5thInternationalJointConferenceonNaturalLanguageProcessing},\mbox{\BPGS\1089--1097}.\end{thebibliography}\begin{biography}\bioauthor{村脇有吾}{2006年京都大学工学部情報学科卒業．2008年京都大学大学院情報学研究科修士課程修了．2011年，同博士後期課程修了．博士（情報学）．同年京都大学学術情報メディアセンター特定助教．2013年，九州大学大学院システム情報科学研究院助教，現在に至る．計算言語学，自然言語処理の研究に従事．}\end{biography}\biodate\end{document}