電子図書館用高速データベース管理システム[稲田]

Transcription

1 03/0/ 情報処理技術演習問題の分類. 分類実験情報処理技術者資格試験問題には何章の問題であるかの区別はない. 概ね同じ章の問題が連続して出題されるが,00% 正しいわけでない. したがって, 過去問題を章別に分類管理するには, 人手による分類作業が必要となる. 本研究では自動分類を試みる. 情報処理技術者資格試験の過去問題,40 問を教師データ,30 問をテストデータとして分類実験を行った. データは問題文および選択肢を chaen で形態素解析して, そのデータから計算した fdf 値を用いた. 乗和が ( ベクトルの長さが ) になるようにノーマライズした実験も行った. 元の単語数は 5,563 語であるが, 一つの問題にしか現れない単語を除いたため,3,09 語となった. 三つの手法 (euro,sv, 類似度 ) で分類を行った. 精度はそれぞれ 93.7%,90.8%,90.5% となった. 計算時間は類似度手法が圧倒的に高速である.SV はまだ十分にマスターしていないことから, 現在のプログラムは遅い. また,euro もここでは最も基本的なモデルを用いているので, 遅い. 拡張 BP 法の採用などにより, 数倍の高速化が実現できるかもしれない. 形態素解析から名詞, 動詞, 形容詞を取り出した. 動詞, 形容詞を無視した結果も求めたいところである. かえって, いい結果が得られるかもしれない. 類似度手法は数学的にはどのような最適化問題を解いていることになるのであろうか? Lnear Kernel に当るのか? データフォーマットは以下の通り ( 教師データ, および 40 を示した ). 印刷の都合で, 一つのレコードが複数行になっているが, データでは レコードが 行となっている. 各レコードの最初の数値が章番号で, その後にターム番号とその fdf 値のペアが続く. ペアはターム番号が小さい順に並んでいる... 今後の課題 ( 修論, 卒論として ) 類似度算出 ( および分類 ) では TfIdf ファイルの全てのタームを用いている. 類似度算出では誤差を生むタームも存在する. このようなターム (,,, についてはニューラルネットワーク入力 - 中間層の結合荷重 ) はほぼ 0( もしくは負の値 ) となっているのではなかろうか? もしそうならばこのよ うなタームを除去すれば類似度の精度が改善される可能性がある. euro など他の手法に頼らず, 類似度計算で直接, 誤差を生むタームを除去できないか? 主成分分析によって特徴ベクトルの次数を低減することも考えられる. ただし, 何となくだが, 精度は上がらない気がする. ニューラルネットについては拡張 BP 法についても調べる. ただし, 収束は速くなるが, 精度は変わらないと思われる. 今回は,460 問について調べたが, さらに追加して, 現在,940 問のデータを持っている. データ数を増やしても大きな改善は見込めないが, 次のフェーズでは,,940 問のデータを使用する. ニューロでは 94% の分類精度が得られた. しかし, 類似度手法で, 類似度最大のものに分類するときの精度は 85% 程度である. 類似度そのものの改善ではこの値を向上させる必要がある. [fdf.daa],40 レコード pare

2 .. ニューラルネットワーク 03/0/ 付録には拡張 BP 法の解説を載せているが, 今回の実験では基本 BP 法を用いた. 即ち, としている. 学習パラメータは 0.8, 0. とした. ノーマライズした場合にも, まれに ( 数回 ) 局所解に陥り, 収束 しないことがあったが, 初期値を乱数で決めていることから, 再実行では収束した. 入力データをノーマライズしたとき, 中間層の数と認識率の関係を次表に示す. 実行時間は 3,4 分である.( いずれ正確に測定すべきである ) なお, ノーマライズしないときは学習が容易に収束しそうになかったので実験を中止した. 中間層数 正解率 (%) 中間層数 正解率 (%) :9.5 最高値は 93.7% であるが, 中間層数による変動が比較的大きい. 中間層数 =7~9 では正解率にムラがある. 中間層数 =~6 付近では安定しており, 最高値は 93.7% である..3. SV * K(w, ): カーネル関数 (Kernel Funcon) * lnear(defaul) (w * ) nnerproduc(w, ) * polnomal (a w * + b)^d * gauan(radal ba funcon) ep(-/(a) w - ^) a: gma_quared * neural anh(a w * + b).3.. Lnear ノーマライズなしのとき,Lnear Kernel に対する結果を下表に示す. C 正解率 (%) C 正解率 (%) 比較的安定した結果が得られている.C=0.007~0.0 での平均正解率は 90.8% である. 他のカーネル関数についても実験中であるが, 今のところ, いい結果が得られていない. この最適化問題自身がおおよそ線形問題に近いということかもしれない. しかし, 線形問題ならば, ニューラルネットワークでの中間層の数は でもいいのではなかろうか? 中間層の数として 4,5 が最良ということはリニア問題ではないことを意味しているはずだが. ノーマライズしたときの Lnear Kernel に対する結果を下表に示す. 実行時間は c=0.00 など値が小さいときはニューラルネットよりかなり速い..0 C 正解率 (%) C E-04 E-04 3E-04 4E-04 5E-04 6E-04 7E-04 8E-04 9E 正解率 (%) Polnomal ava -Xm500B SV -m 40P0.model -f fdf40.daa -p d. c= % precon=89.37% (Error Rae=34/30) c= % precon=89.06% (Error Rae=35/30) ava -Xm500B SV -m 40P0.model -f fdf40.daa -p -d 0.9 -c 0.09 precon=88.75% (Error Rae=36/30) C: EL SV>ava -Xm500B SV -m 40P0.model -f fdf30.daa -p -d 0.9 -c b 0 z precon=88.43% (Error Rae=37/30)

3 Gauan ava -Xm500B SV -m 40G.model -f fdf40.daa -g -c -z c=.0 03/0/.4. 類似度による分類.4.. 複数レコードの判定結果からの判定 各教師データとの類似度 m を求めて, 類似度の高い順に n 件のレコードについて, め, その値が最大となる章を解とする. m deg ree を章別に和を求 旧データ ノーマライズなし (n=0) degree 正解率 ノーマライズあり (n=0) degree 正解率 ノーマライズなし (degree=.4) データ数 (n) 正解率 ノーマライズあり (degree=.65) データ数 (n) 正解率 ノーマライズなし (n=0) degree 正解率 ノーマライズあり (n=0) degree 正解率 ノーマライズなし (degree=.4) データ数 (n) 正解率 ノーマライズあり (degree=.0) データ数 (n) 正解率 fdf 値は小数点以下 桁としている. 旧データでは fdf 値が 0. 未満のものは無視していた. 新データでは無視していない. ニューラルネットおよび SV では新データの方が若干いい結果となっているが, 類似度法ではわずかであるが, 悪くなっている. ノーマライズなしのとき,degree=.4,n=0~5 の平均正解率は 90.5% である. ava CbS 0.4( 正解率 9.%) での誤りの発生を次表に示す. 正誤 3 3 3, 5, 7 4,, 6, 7 5, 3 6, 3, 4, 73 7,, 33 3

4 03/0/ 6 章,7 章において正しく認識されていない比率が高い. また, 誤って 章,3 章,7 章とするケースが多い..4.. 類似度最高レコードによる判定前項でノーマライズなしのとき 85.0%, ノーマライズありのとき 84.0% である. n とすれば, 分類先を類似度最高のレコードと同じ章と判定することになる.. 付録.. 階層型ニューラルネットワーク... バックプロパーゲーション法ニューラルネットワークの代表的なアルゴリズムの一つとしてバックプロパゲーション (BP) 法がある ),3) BP 法は 図 に示すような階層型ニューラルネットワークを対象として 二乗誤差和を評価関数として誤差を逆伝搬させながら結合荷重を修正することにより学習を進める 学習の高速化とネットワークの構造化を図るものとして これを発展させた拡張 BP 法が知られている ) ユニットの出力関数としては 通常 シグモイド関数 / ( ep( )) が用いられ BP 法では 傾き は 定数 ( 特に が多い ) である 拡張 BP 法では 傾き はユニット毎に異なる値を取れるものとして 結合荷重と同様に誤差を逆伝搬させながら傾きを修正し学習を進める 中間層出力計算 出力層出力計算 教 3 教 師 誤 師 入 差 出 力 計 力 算 5 中間層 結合荷重, 傾き修正 4 出力層 結合荷重, 傾き修正 図 階層型ニューラルネットワーク 拡張 BP 法の概略は次の通りである 番目の入力ユニットの出力信号を 番目の中間ユニットの入力および出力信号をそれぞれ u および 番目の出力ユニットの入力および出力信号をそれぞれ v および z とすると ニューラルネットワークの状態は u v z I 0 0 ep( u ) ep( v ) で記述される ここで I および はそれぞれ入力層 中間層および出力層のユニット数である 4 () () (3) (4)

5 03/0/ および はそれぞれ 入力 - 中間層および中間 - 出力層の各ユニット間の結合荷重である 入力層 中間層の 0 番目のユニットは しきい値を結合荷重に含めて統一的に扱うための仮想的なユニットである 0 0 であり 0 および 0 は それぞれこのネットワークに関する評価関数 E を E ( T z ) (5) 番目の中間ユニットおよび 番目の出力ユニットのしきい値にあたる 番目の出力ユニットへの教師信号を表わす で定義する ここで T は拡張 BP 法は 式 (8) の評価関数をもとに 出力誤差を逆伝搬させながら結合荷重 出力関数傾きを修正することにより学習を行う 結合荷重 出力関数傾きの修正量はそれぞれ E (6) E (7) によって計算する ここで は を は を代表する 出力層では 結合荷重および出力関数のパラメータの修正量は (8) v (9) となる ここで ( T z ) z ( z ) (0) である 中間層に対しては となる ここで () u () ( ) (3) である 実際のプログラムでは 振動を減らし 学習の収束を早めるために (8) 式の代わりに ( ) ( ) を用いる 3) ここで は より小さい正の定数 ても同様である 学習アルゴリズム [ ステップ ] 学習サンプルを読み込み 配列に格納する ( 配列への格納は必須ではない ) [ ステップ ] (4) 階層型ニューラルネットワークの入力 - 中間層間の結合荷重を 05. ~05. を 0. ~0. は修正の回数を表わす (9) 式 () 式および () 式につい の乱数で 中間 - 出力層間の結合荷重 の乱数で初期化する また 出力関数の傾きを全て で初期化する [ ステップ 3] 学習サンプルに対して 拡張 BP 法を用いて結合荷重と出力関数の傾きを修正する このとき 出力ユニットを行単位の誤差配列に格納する また 全体を通じての最大誤差も求める の誤差の最大値 ma{ T z } [ ステップ 4] ステップ 3 全体での最大誤差が 0. 05未満のとき 学習を完了する また この最大誤差が 0 かつ前回の学習サイクルにおける最大誤差との差が 0 0 学習を継続するときは ステップ 3 に戻る. 未満であり. 未満の状態が 0 回連続したときも学習を完了する 認識アルゴリズム [ ステップ ] 5

6 03/0/ 認識を行うデータを読み込み 属性ベクトルを算出して 属性配列に格納する [ ステップ ] 学習によって得た結合荷重 出力関数の傾きデータを用いて 中間層の計算を経て 出力ユニットの出力の値を求める ニューラルネットワーク自体での認識では 出力の値が 05未満のとき論理値 そうでなければ論理値 0 とする.. SV... SV とは SV(Suppor Vecor achne) は,Vapn によって提案された二値分類のための教師ありアルゴリズムである []. その概念図を図 に示す. 学習データセットを次のベクトルで表す. ここで, SV は, ( u n, ),,( u, ), R, {, } は事例 を表す特徴ベクトル, は事例 の教師信号 ( 正例を+, 負例を- とする ) である. を次の分離平面で正例, 負例に分離する.. 図 SV の概念図 (Suppor Vecor achne) w b 0, wr 6 n, br まず, 学習セットが線形分離可能な場合を考える.SV ではマージン最大となる分離平面を求める. マージンは / w であり, これを最大化するには以下の 次計画問題を考えればよい. nmze w,b J( w) w ubec o ( w 学習事例が線形分離不可能な場合には, 各学習事例に関して非負の C は正しく分離できなかった学習事例 ( 図 の nmze w, b, b) 0 を導入して, 以下の最小化問題とする. m ) に対するペナルティ項の重み係数である. u J( w, ) w C ubec o ( w b) ( ) 0 f ( ) gn( g( が求ま この 次計画問題をラグランジュの未定乗数法を用いて解くことによって判別関数 )) る. g() は以下の式となる. ここで, は正のラグランジュ乗数である. 0 となる g( ) ( ) b u は uppor vecor と呼ばれ, 判別関数は uppor vecor のみによって記述される. さらに, ベクトルの内積によって定義される Kernel 関数を用いることによって, 線形 SV のアルゴリズムを容易に非線形に拡張することができる. これによって複雑な分離平面を記述することができる. g() は内積をカーネル関数 K( ) で置き換え, 以下の式で表される. g( ) K(, ) b u

7 代表的なカーネル関数として次の polnomal 関数が知られている. K (, ) ( ) d 03/0/ 別の文献 [3] では判別関数 で表されている. ここで, て得られる. f ( ) K(, ) b は各学習事例に対して与えられる係数であり, 次の 次計画問題を解くことによっ mnmze ubec o, K(, 0 C, ) 0, ( これは双対問題に当る ) mnmze ubec o W( α) α 0 α ec, T Qα e T α, T α 0 Q K(, )... SV に対する最適化手法 S(Sequenal nmal pmzaon) 法では, 二つの係数, のみを変数, 他の を定数として, 部分 問題の最適化を行う ( 解析的な方法で簡単に解が得られる ) ことを繰り返して, 全体問題の最適化を行う. 二つの変数の選び方がポイントとなる. 今, アルゴリズムの 回目の繰り返しにおいて, 実行可能解 ( 制約条件を満たす解 ) α が得られていると仮定する. I ( α) { 0 C}, 0 I ( α) { 0, I ( α) { C,,, or or C, 0, }, }. Iu( α) I0( α) I( α), Il ( α) I0( α) I( α W ( α ) Id ( α )}, argmn{ W とし, さらに ) と定めると, 次式で二つの変数を選ぶ. argma{ ここで, W(α) はベクトル ( α) Qα e 通常, W( α ) W( α ) が最適解である. ( α ) I ( α W の第 成分を表す.( すなわち l )} Q である ) であり, そうでなければ b ( W( α ) W( α )) / 矢島 ( 東工大 ): サポートベクターアルゴリズムの理論と実装..3. Smo-boo.pdf [John C. Pla] Quadarac Program: ma W( ) ubec o f ( ) K(, ) b 0 C, - この最適解は次の Karuh-Kuhn-Tucer(KKT) 条件を満たす., K(, 0 ), とすれば, これ 7