新納浩幸
† 本論文では決定リ スト を 弱学習器と し たアダブースト によ る 日本語単語分割法を 提案 する ． 日本語単語分割は， 入力文の各文字の間に単語区切り を 置く か置かな いかの問 題と みな すこ と で， 分類問題と し て 定式化でき る ． こ の分類問題を 決定リ スト を 利用 し て 解く こ と で単語分割が行え る ． こ こ では決定リ スト で利用する 属性に辞書情報を 含めな い． そのた めこ こ での単語分割は未知語の問題を 受け な いと いう 長所があ る ． 更に単語分割を 分類問題と し て 解く 場合， 近年研究の盛んな アダブースト の手法を 適 用でき る ． ア ダブースト を 用いる こ と で， 決定リ ス ト の精度を 高める こ と ができ る ． 実験では， 京大コ ーパス（ 約 4 万文） を 利用し て 決定リ スト を 作成し た ． こ の決定リ スト によ る 単語分割の正解率は 97.52% であ っ た． こ の値は、 同じ 訓練データ から 構 築し た tri-gram モデルに基づく 単語分割法での正解率 92.76% を 大き く 上回っ た． ま たアダブースト を 利用する こ と で精度が 98.49% にま で向上さ せる こ と ができ た． ま た作成し た単語分割システム は未知語の検出能力が高いこ と も 確認でき た． キーワ ード: 単語分割， 分類問題， 決定リ スト ， アダブーストJapanese word segmentation by Adaboost
using the decision list as the weak learner
Hiroyuki Shinnou†
In this paper, we propose the new method of Japanese word segmentation by Ad-aboost using the decision list as the weak learner. The word segmentation is regarded as the classification problem of judging whether the word boundary exists between two characters or not. By solving the problem by the decision list method, we can conduct Japanese word segmentation. Our method has the advantage not to suffer the unknown word problem because we do not use dictionary information as an at-tribute of our decision list. Moreover, by taking this approach we can use Adaboost which is actively researched in the machine learning domain recently. Adaboost improves the precision of our decision list. In experiments, we built the decision list through Kyoto University Corpus (about 40K sentences). The precision of this decision list was 97.52%. This values was much higher than the precision of char-acter based tri-gram model, 92.76%. By using Adaboost method, our precision was improved to 98.49%. Furthermore, our word segmentation system was excellent in detecting unknown words.
KeyWords: Word segmentation, classification problem, decision list, Adaboost
1
はじ めに
本論文では日本語単語分割を 分類問題と みなし ， 決定リ スト を 利用し てその問題を 解く ． こ のア プロ ーチは文字ベース の手法の一種と な り ， 未知語の問題を 受け な いと いう 長所があ る ． ま た 分類問題と と ら え る こ と で， ブーステ ィ ン グの手法が適用でき る ． その結果， 単独の決定 リ スト を 利用する よ り も ， さ ら に精度を 向上さ せる こ と ができ る ． 日本語形態素解析は， 日本語情報処理において 必須の要素技術であり ， その重要性は明ら か である ． 日本語形態素解析は単語分割と 分割さ れた単語への品詞付与と いう ２ つのタ ス ク を も つ． 正し い単語分割から は英語の品詞タ ガーな ど の技術を 利用し て ， 高精度に 品詞付与ができ る ために， 日本語形態素解析の本質的に困難な 部分は単語分割である ． 特に未知語の問題が深 刻であ る ． 未知語の問題と は， 辞書に登録さ れて いな い単語の出現に よ り その単語と そ の単語 の前後での単語分割が誤る と いう 問題である ． 未知語の問題に対処する 一つの方法と し て ， 文字ベースの単語分割手法がある ． 文字ベース の手法と は， 辞書を 使わずに， 各文字間に単語境界が存在する かど う かを 判定する こ と で単語分 割を 行う 手法である ． 従来， 文字ベースの手法と し ては， 文字ベースの HMM (Hidden Markov Model)が提案さ れて いる ． 文字ベース の HMM は， 状態と し て 文字間に単語境界が存在する （ 状態１ ） と し な い（ 状態０ ） の２ つを 設定し ， 状態間を 遷移する と き に各文字が出力さ れる モ デルである ． 単語分割は遷移し た状態列を 推定する こ と で行える ． 文字ベースの HMM では状 態 a から 状態 b に 移る と き に 文字 c を 出力する 確率を 訓練データ から 得る ． 本質的に こ の確 率の精度が単語分割の精度を 左右する ． 通常そ の確率を 計算する ために tri-gram モデルを 利 用する が， 常識的に 考え て も ， 前 2 文字から 次の文字を 予測する こ と は難し く ， 文字ベース の HMM単独ではそ れほど の精度は期待でき な い． こ のため， 様々 な 工夫を 付加する 必要がある (山本 増山 1997; Tsuji and Kageura 1997; 小田 北 1998)．本論文では単語分割を HMM によ り モデル化し て 解く のではな く ， 分類問題と し て 定式化 し て 解く ． 先ほども 述べたよ う に， 日本語単語分割は， 各文字間に単語境界が存在する（ ク ラ ス +1） か存在し な い（ ク ラ ス −1） かを 判定する 問題であり ， こ れは分類問題に他なら ない． 分類 問題を 解く ために設定する 属性と し て， 辞書情報を 使わないこ と で， 文字ベースの単語分割手法 と 同様未知語の問題を 受け な い． ま た分類問題と し て 見な すこ と で， n-gram モデルでは利用 の困難であっ た様々 な 属性を 判定の材料と し て 利用可能に な る ． さ ら に， 分類問題は機械学習 や統計学で活発に研究さ れて いる 問題であり ， それら の研究成果を 直接利用する こ と ができ る ． 本論文では単語分割を 分類問題と 見な し ， 分類問題に対する 帰納学習手法の一つである 決定 リ ス ト (Yarowsky 1994) を 用いて ， そ の問題を 解く ． さ ら に， 近年， 機械学習の研究分野では 弱学習器を 組み合わせて 強学習器を つく る ブーステ ィ ン グの研究が盛んであ る ． こ こ ではその 代表的な 手法である アダブースト (Freund and Schapire 1997) を 本問題に対し て 適用する ．
定リ ス ト を 作成し た． その決定リ スト を 利用し た単語分割は， 同じ データ から 学習さ せた文字 tri-gramモデルに基づく 単語分割法（ 文字ベース の HMM の一種） よ り も 高い精度を 示し た． さ ら に ， アダブースト を 利用する こ と で， 単独の決定リ ス ト よ り も 高い精度を 得る こ と ができ た． ま た本手法の未知語の検出率が高いこ と も 確認し た．
2
決定リ スト によ る 単語分割
2.1
単語分割と 分類問題
n文字から な る 入力文を s = c1c2· · · cn （ 各 ciは文字を 表す） と する と ， 日本語単語分割 は文字 ci と ci+1 の間（ bi と 名付け る ） に単語境界がある (+1) かな い (−1) かを 与え る こ と に よ っ て 行え る 。 つま り bi （ i = 1, 2, · · ·, n − 1 ） に +1 か −1 を 与え る 分類問題と し て と ら え ら れる . 例え ば，「 太郎は海でアイ スク リ ーム を 食べた。」 と いう 文に対し て は， 図 1 のよ う に各文 字間にク ラ ス +1 あ る いは −1 を 付与し ， +1 の部分を 単語境界に置き 換え る こ と によ り 単語分 割が行え る ．%
wwâwwwwww*ww]ww_wwtwwjww¥ww·wwwwUww)ww<ww"ww
ï
%wwâwww*w]ww_wwtwwjww¥ww·wwwUw)ww<ww"wï
図1 ク ラ スの付与によ る 単語分割図1 Word segmentation by class assignment
分類問題を 解く 手法は様々 な も のがある ． ど の手法が優れて いる かは問題に依存する ために 一概には言え な い． 本論文では決定リ スト を 利用し て 上記の分類問題を 解く ．
2.2
決定リ スト の構築
決定リ スト は帰納学習手法の一種であり ， 正解付き の訓練データ から ， 分類規則を 学習する ． 決定リ スト の場合， 分類規則は証拠と ク ラ スの組の順序付き の表と な る ． こ こ で証拠と は属性 と その属性の値の組であ る ． 実際の分類はリ ス ト の上位のも のから 順に， その証拠があ る かど う かを 調べ， その証拠があれば， それに対応する ク ラ スを 出力する ．決定リ スト の作成は概ね以下の手順によ る ． step 1 属性を 設定する ．
例え ば n 個の属性を att1, att2, · · · , attnと する 。 step 2 訓練データ から 証拠と ク ラ スの組の頻度を 調べる ．
訓練データ 中のある データ の属性 att の値が a である と し ， そのデータ のク ラ スが C だ と する ． その場合， (att, a) と いう 証拠と ク ラ ス C の組 ((att, a), C) の頻度に 1 を 足す． こ れを 訓練データ 中の全データ に対する 全属性について 行う ．
step 3 証拠の判別力と 分類ク ラ スを 導く ．
((att, a), C)の頻度が fC であっ た場合， fC の最大値を 与え る ˆC が証拠 (att, a) に対す る 分類ク ラ スと な る ． ま たそのと き の判別力 pw(att, a) は以下で定義さ れる ．
pw((att, a)) = log fCˆ P C6= ˆCfC step 4 判別力の順に並べる ． 全て の証拠と 分類ク ラ スの組を 判別力の大き い順に並べる ． こ れに よ っ て 作成でき た表 が決定リ スト である ．
2.3
属性の設定
各文字間 biがど のク ラ スに属する かを 判断する 材料が属性である ． 本論文では biの属性と し て ， 表 1 の 7 種類を 用意し た． 表1 設定し た属性 表 1 Setting attributes 属性 値 att1 文字列 ci−1cici+1att2 文字列 cici+1ci+2
att3 文字列 ci−1ci
att4 文字列 cici+1
att5 文字列 ci+1ci+2
att6 字種の接続関係1 ((ciの大分類字種), (ci+1の大分類字種)) att7 字種の接続関係2 ((ciの細分類字種), (ci+1の細分類字種)) 6， 7 番目の属性と し て ， 字種の情報を 利用し ている 形にな っ て いる ． こ こ では字種を 大分類 と 細分類の二つの観点から 分類し た． 字種の大分類は 6 番目の属性， 字種の細分類は 7 番目の属 性で利用し た． 字種の大分類は表 2 に示し た 9 種類である ．
表2 大分類字種
表 2 Classification of character types
字種 意味 例 平 平仮名 あ， い， う ， … カ カ タ カ ナ ア， イ， ウ， … 数 漢数字 一， 二， …， 百， 千， … 漢 漢字 亜， 位， 卯， … Ｎ 英数字 ０ ， １ ， ２ ， … ア アルフ ァ ベッ ト Ａ ， Ｂ ， Ｃ ， … 記 記号 、 ，。 ，「 ， … 〇 小丸かゼロ 〇 ○ 大丸かゼロ ○ 字種の細分類は大分類の平仮名の部分を その文字自身にし たも のである ． ま た注意と し て ， 本論文の決定リ スト では default の証拠を 導入し て いな い． 決定リ スト で は通常 default と いう 証拠を 設け て ， それ以下の判別力の証拠は表には入れな い． default は文 脈上の証拠が決定リ スト に存在し な い場合の処理と と ら え ら れる が， こ こ では大分類の字種の 情報が必ずヒ ッ ト する ので， default の証拠を 含める 必要がな い． 6 番目の属性から の証拠の最 下位のも のが， 決定リ スト の最下位の証拠と な る ．
2.4
利用例
決定リ スト の利用例を 示す． 例え ば「 太郎は海でアイ スク リ ーム を 食べた。」 と いう 入力文 の 5 番目の文字 “で” と 6 番目の文字 “ア” の間， つま り b5 にク ラ ス +1 ある いは −1 を 与えて みる ． b5の持つ証拠は以下の 7 種である ．(att1, ”海でア”)， (att2, ”でアイ ”)， (att3, ”海で”)， (att4, ”でア”)， (att5, ”アイ ”)， (att6, ”平カ ”)， (att7, ”でカ ”)
後述する 実験で得ら れた決定リ スト を 用いる と ， 各証拠の分類ク ラ スと 判別力は以下の通り である ．
表3 ク ラ ス判別の例
表 3 Example of class judgement
証拠 分類ク ラ ス 判別力 (att1,”海でア”) – – (att2,”でアイ”) – – (att3,”海で”) +1 2.74377 (att4,”でア”) +1 5.83188 (att5,”アイ”) +1 1.64565 (att6,”平カ”) +1 6.33293 (att7,”でカ”) +1 8.64488 表の中で “–” の記号のも のは， 決定リ ス ト 中に その証拠がな いこ と を あ ら わす． ま た本来 な ら ば， 決定リ ス ト 中の順位を 求めな け ればな ら な いが， こ こ では相対的な 順位関係だけ が必 要であり ， 順位の値自体は必要でな い． 判別力の最も 大き な も のが最上位の順位にな る はずで あ る ． こ の場合， 証拠 (att7, ”でカ”) が最も 大き な 判別力を 持つので， こ の証拠の分類ク ラ ス +1が判定結果と な る ． つま り b5 には単語境界を 置く と 判定する ．
3
ア ダブースト の利用
精度の低い分類規則を 組み合わせて 精度の高い分類規則を 得る 方式を ブース ティ ン グと い う ． アダブース ト はブース ティ ン グ方式の一つであり ， 現在ま で多く の理論的検証と 実験的実 証から 有効性が示さ れて いる ． アダブースト のアルゴリ ズム を 図 2 に示す． 分類ク ラ ス (図 2 の Y ) を こ こ では {+1, −1} の 2値と する ． ま た訓練データ を (x1, y1), (x2, y2), · · · , (xm, ym)で表す． こ こ で各 xiはデータ を 表 し ， yi はデータ xi のク ラ スである ． 具体的に yi は +1 ある いは −1 の値である ． こ の訓練デー タ に対し て ， 分類問題に対する 学習アルゴリ ズム ， 例え ば， 決定木や決定リ ス ト な ど を 適用し て ， 分類規則 h1を 学習する ． 得ら れた分類規則 h1を 訓練データ に 適用する と ， h1によ っ て 各 xiの判定ク ラ ス が得ら れる ． 今， xiの実際のク ラ ス yi は与え ら れて いる ので， 分類規則 h1が 各 xiに対し て 正し い判定を 行っ たかど う かを 調べら れる ． こ れによ っ て 不正解のデータ を 集め， それら 不正解のデータ に対し てある 重みを 付加し て， 訓練データ (x1, y1), (x2, y2), · · · , (xm, ym) を 再構成する ． そ し て こ の再構成さ れた 訓練データ に 対し て ， 再び学習ア ルゴ リ ズム を 適用 し て ， 分類規則 h2を 学習する ． こ れを T 回繰り 返す． こ の繰り 返し によ っ て ， T 組の分類規則 h1, h2, · · · , hT が得ら れる ． 実際の判定は入力データ に対し て各分類規則が出力する ク ラ スの重 み付き 多数決によ り 行われる ． 例え ば， T = 3 と し ， 入力データ x に対し て ， 分類器 h1 によ る 判定ク ラ スが +1， h2 による 判定ク ラ スが −1， h3 によ る 判定ク ラ スが +1 であり ， 各重みが 1 ， 2.0 ， 2.2 であっ た場合， 重み付き 多数決の結果は +1.2 である ． 最終的な 判定ク ラ ス は総和の符合によ り 求ま る ． こ の 例の場合， 符合は正である ので， +1 が判定ク ラ スにな る ．
アダブースト のポイ ン ト は不正解のデータ に課す重みの与え 方である ． 概略， 得ら れた分類 規則の誤り 確率（ 図 2 におけ る ǫt)が小さ いほど 重みが大き く な る よ う に設定し て いる ．
Given: (x1, y1), · · · , (xm, ym) where xi∈ X,yi∈ Y = {1, −1} Initialize Di(i) = 1/m
For t = 1, · · · , T
• Train weak learner using distribution Dt • Get weak hypothesis ht: X → Y with error
ǫt= P ri∼Dt[ht(xi) 6= yi] • Choose αt= 1 2ln( 1 − ǫt ǫt ) • Update: Dt+1(i) = Dt(i) Zt × ( e−αt if h t(xi) = yi eαt if h t(xi) 6= yi where Zt is a normalization factor
Output the final hypothesis: H(x) = sign( T X t=1 αtht(x)) 図2 アダブースト 図2 AdaBoost 本論文では． 分類問題に対する 学習アルゴリ ズム を 決定リ スト に設定する ． 不正解データ に 与え る 重みを ど のよ う に 反映さ せる かが問題である ． こ こ では， 重みを 頻度と し て 与え る こ と にし た． 例え ば，「 太郎が東京へ行く 。」 と いう 文に 以下のよ う に 単語境界 “/” が置かれた も の が訓練データ である ．
太郎/が/東京/へ/行く /。
今， 4 番目の文字 “東” と 5 番目の文字 “京” の間， つま り b4 に対する 証拠は以下の通り で ある ．
(att1, ”が東京”)， (att2, ”東京へ”)， (att3, ”が東”)， (att4, ”東京”)， (att5, ”京へ”)， (att6, ”漢漢”)， (att7, ”漢漢”)
“東” と “京” の間には， 単語境界がな いので， ク ラ スは −1 である ． そし て ， 決定リ スト 作 成の step 2 で示し たよ う に， 以下の証拠の頻度に 1 が足さ れる ．
((att1, ”が東京”), −1)， ((att2, ”東京へ”), −1)， ((att3, ”が東”), −1)，
((att4, ”東京”), −1)， ((att5, ”京へ”), −1)， ((att6, ”漢漢”), −1)， ((att7, ”漢漢”), −1)
こ の頻度に加算さ れる 1 と いう 数値に重みを 反映さ せる ． 例え ば， 決定リ スト hk によ り 上記例文の 4 番目の文字 “東” と 5 番目の文字 “京” の間の判 定ク ラ スが +1 と 判定さ れた場合， こ の判定は不正解である ． そこ で次の決定リ ス ト hk+1を 作 成する と き に， 上記の７ つの各証拠の頻度に 1 ではな く ， 重み自身を 加え る ． つま り 決定リ スト を 作成する 際には各訓練データ には重みがついて いる と し て ， その重みが 決定リ スト 作成の step 2 で各証拠と 正解の組に付加する 数値と する ． 図 2 のアルゴリ ズム では 正規化する ために重みの総和が１ にな っ て いる が， こ こ では重みの最小値が１ と な る よ う にし て 計算を 簡単に し た． こ のた め最初の決定リ ス ト を 作成する 際の各訓練データ の重みは１ であ り ， ２ 回目では正解のデータ の重みは１ で変化せず， 不正解の部分の重みが大き く な る ．
4
実験
4.1
文字 n-gram モデルに基づく 単語分割法と の比較
こ こ では決定リ スト を 利用し た単語分割の有効性を 示すために， 文字 n-gram モデルに基づ く 単語分割法 (小田・ 北 1998) と の比較を 行う ． 文字 n-gram モデルに基づく 単語分割法では， 概略， 単語境界を 付与し た訓練データ において， 単語境界の記号自体も 一つの特殊文字と し て考 えて ， ある 文字列の後に単語境界が生じ る 確率ある いは生じ ない確率を 文字 n-gram モデルに基 づいて 計算する ． 最終的に は Viterbi アルゴリ ズム な ど の動的計画法を 利用し て ， 文字列の出 現確率が最大にな る よ う に単語境界のある な し の列を 決定する ． こ れは文字ベースの HMM に おいて ， 遷移確率やシン ボル出力確率を ある 確率モデルに基づいて 計算し たも のと 同等である ． 訓練データ と し ては京大コ ーパス (約 4 万文) を 利用し た． 京大コ ーパスは人手でタ グを つけたコ ーパスであり ， 正解付き の訓練データ と し て 利用でき る ． 京大コ ーパスの中から 950117.KNP と いう フ ァ イ ルに納めら れた 1,234 文1を テスト データ と し た． 結果， 訓練データ は京大コ ーパ ス から テ スト データ を 除いた 35,717 文 である ． テ ス ト データ 1,234 文の中には， 単語境界を 置く か置かな いかを 判定する 位置が 56,411 個所存在する ． こ の 56,411 個所に対し て 正し いク ラ スを 付与でき た割合を 正解率と する ．
訓練データ から 文字 tri-gram 確率を 求める ために CMU-Cambridge Toolkit 2を 利用し た． ス ム ージン グの手法と し て は Witten-Bell discounting を 用い， カ ッ ト オフ は頻度 0 と 設定し た (北 1999)． 文字 tri-gram 確率から tri-gram モデルに基づく 単語分割法を 実装し た シス テム を 作成し ， テスト データ に対し て 単語分割を 行っ た． 結果， 56,411 個所の判定位置について ， 52,328 個所 で正し い判定を 行い， 4,083 個所で誤っ た 判定を 行っ た． つま り 正解率は 92.76% であっ た ． 次に上記の訓練データ を 利用し て本論文で提案し た決定リ スト を 作成し た． 頻度 7 以下の証 拠は間引いた． 作成でき た決定リ スト の大き さ は 136,114 であっ た ． こ の決定リ ス ト によ り テ スト データ に対し て 単語分割を 行っ た． 結果と し て ， 56,411 個所の判定位置について ， 55,015 個所で正し い判定を 行い， 1,396 個所で誤っ た 判定を 行っ た ． つま り 正解率は 97.52% であっ た． こ の値は tri-gram モデルに 基づく 単語分割法の正解率 92.76% を 大き く 上回っ て おり ， 本 手法の有効性が示せた．
4.2
ブースティ ン グの効果
前述し たアダブースト によ り ， 決定リ スト のブースティ ン グを 行っ た． ブースティ ン グの回 数を 横軸に， テスト データ に対する 正解率 % を 縦軸にし たグラ フ が 図 3 である ． 図 3 から わかる よ う に， ブースティ ングによ り 3 組の決定リ スト を 作成し ， それら の重み付 き 多数決によ っ て 判別し た結果が最も 優れて いた． そのと き 56,411 個所の判定位置について ， 55,560個所で正し い判定を 行い， 851 個所で誤っ た判定を 行っ た． つま り 正解率は 98.49% ま で向上し た．4.3
未知語の検出
ブースティ ン グによ り 3 組の決定リ スト を 作成し ， それら の重み付き 多数決によ っ て 各文字 間に単語境界の有無を 判定する 手法（ 以下こ れを 本手法と 呼ぶ） が， 本実験において ， ど の程 度の未知語を 検出でき たか調べる ． 前述し た訓練データ 35,717 文と テ スト データ 1,234 文の正確な 単語分割結果から ， それぞ れに含ま れて いる 単語文字列を 取り 出し た． こ こ でいう 単語文字列と は， 単純に単語分割さ れ 1こ こ ではコ ーパス中の記号 EOS の数を 文の数と し て いる ． 句点 “。 ” の数ではな いこ と を 注意し て おく ．97.4 97.6 97.8 98 98.2 98.4 98.6 1 2 3 4 5 6 7 ’precision’ 図3 ブースティ ン グによ る 正解率 図 3 Precision by boosting た分割要素の文字列のこ と である ． つま り 用言の活用語尾が異な る も のも ， 異な る 単語文字列 と し て 取り 出すこ と に 注意する ． 結果， 訓練データ に は 914,392 個（ 41,890 種類） の単語文字 列， テス ト データ には 32,764 個（ 6,479 種類） の単語文字列が存在し た． そし て テス ト データ に は含ま れる が， 訓練データ に は含ま れな い単語文字列が 1,024 個（ 832 種類） 存在し た ． こ の 1,024 個（ 832 種類） の単語文字列が本実験におけ る 未知語と な る ． 結論から 述べる と ， 本手法に よ り こ の 1,024 個（ 832 種類） の未知語の中で， 正し く 検出で き たも のは 688 個（ 562 種類） ， つま り 個数で 67.2%， 種類数で 67.5% の検出率であっ た ． 検出でき た未知語の中には， 字種区切り のよ う な 単純な ヒ ュ ーリ スティ ク スから 検出でき る も のも 存在する ので， 本手法の未知語検出が， 実質ど の程度の有用性がある のかを 示すために， 対象の未知語を 以下のよ う に 9 タ イ プに分類し た． (1) 用言であり ， そ の原型を 同じ と する 単語が訓練データ に含ま れる （ 124 個（ 123 種類）） ． 例え ば，「 押し つぶし た」 と いう 単語文字列は， テスト データ には含ま れる が， 訓練デー タ には含ま れな いために ， 本手法では未知語と し て 扱われる ． し かし 通常の辞書を 利用 し た シス テム では，「 押し つぶし た」 の原型「 押し つぶす」 が辞書に 登録さ れて いれば， 正し く 解析でき る ． 訓練データ には，「 押し つぶす」 の語尾変化形であ る 単語文字列「 押
し つぶし て 」 が含ま れている ． そこ で， 通常のシステム の辞書には， 原型「 押し つぶす」 が登録さ れて いたと 考え ，「 押し つぶし た」 は正し く 解析でき る と 考え る ． こ こ では， こ のよ う なタ イ プの未知語は， 通常のシステムの用言の語尾変化の規則によ っ て 検出でき る タ イ プの未知語と し て 考え る ． (2) 用言であり ， そ の原型を 同じ と する 単語が訓練データ に含ま れない（ 94 個（ 91 種類）） ． 例え ば，「 飲みすぎて 」 と いう 単語文字列は， テスト データ には含ま れる が， 訓練データ には含ま れな い． し かも (1) の場合と は異な り ，「 飲みすぎて 」 の原型「 飲みすぎる 」 を 語尾変化さ せた 単語文字列も 訓練データ に 含ま れな い． こ れは通常のシステム に おいて も 未知語と な る も のである ． (3) 数値表現と なっ て いる （ 44 個（ 41 種類）） ． 例えば，「 一万九千百八十五」 や「 ２ ７ ・ ７ 」 と いう 単語文字列は未知語と な っ て いる が， 通常のシス テム はこ れら の表現を 数値表現 と し て 認識でき る 規則を 持っ て いる ． こ の種の未知語も 通常のシステム で検出でき る タ イ プの未知語と する ． (4) ア ルフ ァ ベッ ト のみで構成さ れる （ 7 個（ 3 種類）） ． 「 Ａ Ｃ 」「 Ｏ Ｅ Ｋ 」「 Ｐ Ａ Ｈ 」 の単 語文字列であ る ． こ れら は字種区切り のよ う な 単純な ヒ ュ ーリ スティ ク ス から 通常のシ ステム でも 検出可能である ． (5) カ タ カ ナのみで構成さ れる （ 210 個（ 156 種類）） ． 例えば，「 アロ マセラ ピスト 」 や「 スー ザン 」 のよ う な 単語文字列である ． こ れら も 字種区切り のよ う な 単純な ヒ ュ ーリ ステ ィ ク スから 通常のシステム でも 検出可能である ． (6) 平仮名のみで構成さ れる （ 38 個（ 32 種類）） ． 例え ば，「 ごあいさ つ」 や「 ぞろ ぞろ 」 の よ う な 単語文字列である ． こ れら の検出は通常のシステム では不可能である ． (7) 漢字１ 文字で構成さ れる （ 21 個（ 17 種類）） ． 例え ば，「 魁」 や「 鋼」 のよ う な 単語文字 列である ． 通常のシステムでも 未知語と な る が， 単語分割の他の候補が生じ な いために， 結果的に正し く 単語分割でき る 場合も 多い． (8) 漢字のみで構成さ れる （ 426 個（ 310 種類）） ． 例え ば，「 重文」 や「 三井造船」 のよ う な 単語文字列である ． こ れら の検出は通常のシステム では不可能である3． (9) 複数の字種から 構成さ れる （ 64 個（ 59 種類）） ． 例え ば，「 寝泊ま り 」 や「 亡き 後」 のよ う な 単語文字列である ． こ れら の検出は通常のシステム では不可能である ． 上記 9 タ イ プの未知語の本手法によ る 検出結果を 表 4 に 示す． 同時に 通常のシス テム で想 定でき る 検出結果も 示す． 3例え ば， 漢字１ 文字から な る 未知語と 既知語を 全体と し て 未知語と し て 認識でき る 可能性が指摘さ れた ． し かし そ の ヒ ュ ーリ スティ ク スがど の程度妥当かは疑問がある ． ま た， その場合 (7) と の区別がつかない． こ こ では多少強引だが， (8)は既存のシステム では検出不可能と し た．
表4 未知語の検出
表4 Detection of unknown words
タ イ プ 総出現数 本手法によ る 検出 通常のシステム によ る 検出 (1)辞書登録の用言 124 101 124 (2)辞書未登録の用言 94 57 0 (3)数値表現 44 40 44 (4)アルフ ァ ベッ ト 列 7 5 7 (5)カ タ カ ナ列 210 188 210 (6)平仮名列 38 19 0 (7)漢字１ 文字 21 4 21 (8)漢字列 426 246 0 (9)複数の字種 64 28 0 合計 1,024 688 (67.2%) 406 (39.6%) 表 4 に示すよ う に通常のシス テム の検出率は 39.6% であり ， 本シス テム の検出率 67.2% と 大き く 差がある ． こ れは本システム の未知語の検出能力の高さ を 示し て いる ． ま た通常のシス テ ム に よ り 検出でき る と し た 未知語のタ イ プ (1),(3),(4),(5),(7) に対し て ， 本手法の検出率は 83.3%であり ， 通常のシステ ム によ り 検出でき る 未知語の多く は本システム でも 検出でき る と 考え ら れる ．
5
考察
本手法での判別の出力は 2 値であり ， 判別に使っ た判別力の値自体は利用さ れて いない． テ スト データ に対し て判別力の値によ る 正解率を 調べる ために， 以下の調査を 行っ た． テスト デー タ には 56,411 個所の判定位置がある が， 0 以上 1 未満の間の判別力で判定さ れた位置は 83 個 所であ り ， その正解率は 57.83% であっ た ． 同様にし て ， 1 以上 2 未満の間， 2 以上 3 未満の 間と いう 具合いに順に調べて いっ た 結果を 示し た も のが図 4 であ る ． こ のグラ フ から も わかる よ う に ， 判別に利用し た判別力が小さ いほど 誤る 確率が高く な る ． こ のよ う な 判別力の値を 利 用し て ， さ ら に誤り を 減ら せる 工夫も 可能であろ う ． ま た本論文では分類問題の解法と し て 決定リ スト を 利用し たが， 他の手法， 例え ば， 決定木 (Quinlan 1993)や最大エン ト ロ ピー法 (Ratnaparkhi 1998) の利用も 可能である ． ただし 本論文 で利用し た属性にあたる も のを ， それら の手法では単純には利用でき な い． 決定木を 利用する 場合， 属性の数は 7 種類であり 問題な いが， bi-gram ある いは tri-gram にあたる 属性の値の種 類数が非常に 多い． こ のため決定木の各ノ ード から 出る 枝の数が膨大にな り ， 現実的には決定 木を 作成でき な い． ま た最大エン ト ロ ピ ー法では素性の設定と 素性パラ メ ータ の算出が必要と な る ． 素性は本論文で述べた証拠自体と な る ため， 素性の種類は頻度 7 で間引いて 約 14 万弱0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0 2 4 6 8 10 12 14 図4 判別力と 正解率
図4 Identification strength and precision
であ る ． 最大エン ト ロ ピ ー法で利用でき る 素性の数は現実的に は， 数万が限度であ る た めに ， 最大エン ト ロ ピ ー法の利用も 現実的に は無理があ る ． 文字ベースの手法を 利用する 場合に は， bi-gramや tri-gram な ど の情報を 直接利用でき る 決定リ スト は現実的に有効な 選択である ． 本論文では単語分割を 分類問題と し てみな し て解決し た． 分類問題と みな し た場合， 精度に 関わる 最も 大き な 要因は属性の選択である ． アダブース ト を 利用する と いう 枠組みでは， 属性 の設定はさ ら に考慮すべき である ． ブースティ ン グは弱学習アルゴリ ズム に対し て 利用でき る ． 具体的には精度が 50% を 越え る よ う なアルゴリ ズム であれば適用でき る ． つま り 作成でき た決 定木な ど の分類システム 自体の精度はそれほど 高い必要はな い． 属性を う ま く 考慮し て 決定リ スト の精度を 上げる よ り も ， 作成さ れる 決定リ スト の精度は低いが， ブースティ ン グに よ り 精 度が増し て ゆく よ う な 属性を 設定する アプロ ーチも 有望である ． いく つかの実験を 行っ た結果， 以下の点が確認でき た． • 属性を 増やす， 間引き の頻度を 調整する ， な ど の工夫を 入れて 決定リ スト の精度を 上げ た場合， ブースティ ン グでは精度が上がら な かっ た． • 属性を 単純化し て 決定リ スト の精度を 若干下げた場合， ブース ティ ン グによ っ て 精度は 上がる が本実験で行っ た 結果以上には精度は上がら な かっ た ． 結論的には本論文で設定し た属性の情報を 利用する 上では， 本論文で示し た値程度が限界に近 いと 感じ ら れた． 分類誤り の原因を 追求する と ， 訓練データ に現れな い表現ある いは頻度の低い表現の部分で
分類が誤っ て いる4． こ れは未知語の問題そのも のであり ， 未知語への対処が単語分割の中心の 課題と 言え る ． こ の解決策は 3 つ考え ら れる ． 1 つ目は規則の一般化を 精度良く 行う こ と であ る ． 例え ば文字ク ラ ス (小田, 森, 北 1999) など の導入な ど が考え ら れる ． 2 つ目は別リ ソ ースの 利用である ． 例え ば辞書の利用である ． 単語分割に本手法の分類手法と 辞書に よ る 最長一致法 を 利用する こ と も 考え ら れる ． 3 つ目は訓練データ の拡充である ． 事例ベースの手法 (山下 松本 1998;伊東 1999) は訓練データ つま り 事例を 大規模化する こ と で精度が上がる ． た だし 大規模 な 正解付き の訓練データ が用意でき な い現状では， 正解のな い訓練データ を ど う 使う かが鍵と な る (新納 2000)． １ つ目のアプロ ーチ以外は， 未知語の検出に対し て 理論的な 保証がな い． し かし だから と いっ て ， 単語分割を 文字ベースの手法によ っ て 解く こ と に 意味がな いわけ ではな い． 辞書に基づいた分割では数値表現や字種区切り が有効にな る よ う な未知語し か解析でき ず， 解析でき る 未知語が限定さ れて いる ． こ のよ う な 未知語の多く は， 実験に示し たよ う に， 本手 法でも その多く を 検出でき る ． さ ら に 文字ベースの手法では， その他のタ イ プの未知語も 検出 でき る 場合が多々 あ る が， 辞書に基づいた分割では確実に検出でき な い． こ の違いは大き い． 最後に 本手法のア プ ロ ーチ は解析が決定的に な る と いう 長所も あ る こ と を 付記し て おく (Shinnou 2000)． 通常の形態素解析シス テム も 現実的にはほぼ文字数に 比例し た時間で解析が 行え る ので， 決定的である と いう こ と はそれほど 大き な 長所ではな い． ただし 理論的に 線形時 間での解析を 保証でき る こ と には意味がある ．
6
おわり に
本論文では日本語単語分割を 分類問題と みな し ， 決定リ スト を 利用し て そ の問題を 解いた． 本手法は未知語の問題を 受け な いと いう 長所がある ． 実験では， 文字ベースの n-gram モデル に基づく 単語分割法と の比較を 行い， 決定リ ス ト によ る 単語分割の方が優れて いる こ と を 示し た． ま た 分類問題と と ら え る こ と で， ブース ティ ン グの手法を 適用でき る こ と も 示し た． アダ ブース ト を 利用する こ と によ っ て ， 単独の決定リ ス ト よ り も さ ら に精度を 向上さ せる こ と がで き た． 未知語の検出能力も 高かっ た． 訓練データ に な い表現を ど のよ う にカ バーし て ゆく かが 今後の課題である ． 謝辞 本研究は（ 財） 栢森情報科学振興財団の研究助成金（ K11 研 IV 第 71 号） によ っ て 行われま し た． 深く 感謝し ま す. 4先の実験によ り 示し た本手法が検出でき なかっ た未知語の出現数（ 336） から 考えて ， 全体の誤り の数（ 851） が多いよ う にも 感じ ら れる ． し かし こ れは， 本実験では頻度 7 以下の証拠を 間引いて いる ために， 本手法におけ る 未知語の実質 的な 総数は， 先の実験で示し た数よ り も 多いこ と によ る ．参考文献
Freund, Y. and Schapire, R. E. (1997). “A decision-theoretic generalization of on-line learning and an application to boosting.” Journal of Computer and System Sciences, 55 (1), 119–139.
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publisher. Ratnaparkhi, A. (1998). “Maximum Entropy Models for Natural Language Ambiguity
Reso-lution.” In PhD thesis. University of Pennsylvania.
Shinnou, H. (2000). “Deterministic Japanese Word Segmentation by Decision List Method.” In PRICAI-2000 (poster session), pp. 822–822.
Tsuji, K. and Kageura, K. (1997). “An HMM-based Method for Segmenting Japanese Terms and Keywords based on Domain-Specific Bilingual Corpora.” In The 4th Natural
Lan-guage Processing Pacific Rim Symposium, pp. 557–560.
Yarowsky, D. (1994). “Decision Lists for Lexical Ambiguity Resolution: Application to Ac-cent Restoration in Spanish and French.” In 32th Annual Meeting of the Association for
Computational Linguistics, pp. 88–95. 伊東秀夫 (1999). “Suffix array を 用いた 日本語単語分割.” 情報処理学会自然言語処理研究会, NL-131-7. 小田裕樹 北研二 (1998). “P P M∗モデルによ る 日本語単語分割.” 情報処理学会自然言語処理研 究会, NL-128-2. 小田裕樹, 森信介, 北研二 (1999). “文字ク ラ スモデルによ る 日本語単語分割.” 自然言語処理, 6 (7), 93–108. 北研二 (1999). 確率的言語モデル. 東京大学出版会. 新納浩幸 (2000). “日本語単語分割へのタ グな し コ ーパス と タ グ付き コ ーパスの利用.” 情報処 理学会自然言語処理研究会, NL-140-1. 山下達雄 松本裕治 (1998). “品詞タ グ付き コ ーパスを 直接利用し た形態素解析.” 言語処理学会 第 4 回年次大会, pp. 524–527. 山本幹雄 増山正和 (1997). “品詞・ 区切り 情報を 含む拡張文字の連鎖確率を 用いた日本語形態 素解析.” 言語処理学会第 3 回年次大会, pp. 421–424.
