修士論文 要旨

文字列集合の分類問題における最適パタン発見の効率的アルゴリズム
数理情報学専攻 48156226
指導教員

守屋 航一
定兼 邦彦 教授

目し，その 1 要素のみを変数とする最適化問題と見て，1 序論

その最適値で更新する，という手法であり，1 つのパラ

多くのデータ・変数を扱う機械学習において，メモリメータの更新に対してそのパラメータのみを用いて行

容量は常に付きまとう問題であり，初期からメモリ容量うことができる．L1 ロジスティック回帰では近似を用に着目した工夫・改良が行われている．カーネル法などいることで，以下の更新式が導出される．

入力から非線形的特徴を抽出しようとする場合，特徴に対応した変数すべてがメモリに載らなくなり，変数の更新に工夫を要する．データそのものがメモリに載らない場合，ディスクのデータにアクセスする時間が問題となってくる．データがメモリに載らない場合のアプ

wjt+1 =

D(w,x ,y )− 1

1
D(w,xi ,yi )+ 2C∑ 2
ϕ(x)ii j
1D(w,x ,yi )− 2C
wjt < ∑ ϕi 2 (x)
ii j

wjt >

i2C
wjt − ∑ ϕi 2 (xi)i j
0o.w.
∑TD(w, xi , yi ) =(wt ϕ(xi ) − yi )ϕj (xi )i

ローチとして，Langford らは 2 つの方向性，並列化とオンライン学習を上げている [2]．


1D(w,x ,yi )+ 2C
wjt − ∑ ϕi 2 (x)ii j

FCL では，writer と trainer の 2 つのスレッドを独このような状況における正則化項付き最小化問題に立して動かす．writer は，ディスクのデータを読み取対するブロック化最小化スキームは，Yu らによって初り，ランダムに選ばれた ϕj (xi ) をキャッシュに書き出めて提案された [3]．この手法では，データをいくつかす．一方 trainer は，キャッシュからランダムに選んだのブロックに分解し，そのブロックに含まれるデータの特徴のパラメータを上の更新式を用いて更新する．2 つみで変数を更新している．Matsushima は座標降下法のスレッドは独立して動かすことが可能であり，並列を用いたスキーム Feature Cashed Loop (FCL) を提案

実行可能であることがこのスキームの強みの 1 つとい

し，並列可能を可能にしつつ，各変数の更新に用いるメえる．

モリ容量を抑えることに成功した [1]．一方で，このス

3 実問題とその定式化

キームにおいて，更新する変数はランダムに選択されているが，組合せの数が膨大であるため，目的関数の最適本研究で扱う実問題は，スプライス部位認識問題と呼化に寄与しない変数を選んでしまうという問題が存在ばれるバイオインフォマティクスにおける重要な問題した．本研究は，この変数選択に関する高効率のアルゴである．機械学習における 2 クラス分類問題として解リズムを提案するものである．

釈できる問題であり，入力 xi ∈ Σd と出力 ±1 の組から，出力が +1（または −1）に共通するパタンを見つけ2 学習モデルと最適化手法る問題といえる．このとき，パタンにはワイルドカード入力となるデータ列 X = (xi ), (i = 1, . . . , n) から出（任意の文字と一致する記号）を許すものとする．この力となるデータ列 y ∈ Rn を予測する問題を考える．計問題を正則化項付きリスク最小化問題として式 1 のよ算のため，データ xi ∈ X を特徴関数 ϕ : X → Rp を用うに定式化し，前述のアルゴリズムおよびスキームを用いて p 次元ベクトルに写像する．このとき，wT ϕ(X) ≈いて学習を行う．

y となるパラメータベクトル w ∈ Rp を求める問題を考える．FCL は以下の式 1 で表される関数の最小化として定式化される L1 ロジスティック回帰の学習を座標降下法を用いて実装している．

L(w) = ∥w∥1 + Cn∑

4 最適パタン発見問題とそのアルゴリズム
FCL スキームでは，更新するパタンをランダムに選択していたが，パタン数の多さからその効率性に問題があった．また FCL スキームでは，「|C∇j L(wt )| の値log(1 + exp(−yi wT ϕ(xi )) (1)i=1

座標降下法は更新するパラメータの 1 つの要素に着が小さいものは 0 に収束する」というヒューリスティ
クスを利用して，パタンの選別を行っていた．そこで，この値をスコアとして，全パタンの中からスコアが閾値文字列集合の分類問題における最適パタン発見の効率的アルゴリズム (守屋 航一)

以上のパタンを列挙する問題を考える．パタンの探索いたが，b = 12 では Downward Algorithm が優る結果方向として「ワイルドカードの少ないものから調べる」が得られた．パタン長が短い場合，Upward Algorithm

Upward Algorithm と「ワイルドカードの多いものかが優位であり，長い場合に Downward Algorithm の枝ら調べる」Downward Algorithm の 2 つを提案した．

刈りの優位性が現れることを示した．

Upward Algorithm はすでに計算したパタンのスコパタン長を変えて Downward Algorithm を計算した

アの足し合わせにより次のパタンのスコアを計算する

結果を比較し，短パタン長でのスコア上位パタンが長ことができるが，現れた全てのパタンを探索する必要がパタン長でのスコア上位パタンに現れることを示した．

ある．一方で，Downward Algorithm ではスコアの計

また，長パタン長でのみ表現可能なパタンが上位に出現

算に毎回パタンの探索を行う必要があるものの，適宜条することもわかった．短時間の計算での比較では，パタ件に応じた探索の打ち切りを行うことができる．

ン長が短い場合に計算速度が高いことから，最適化速度および学習速度で優位になることを示した．一方，長時5 実験

間の実験から，パタン長が長い場合でも学習度合の改善

既存手法と提案手法の比較および提案 2 手法の比較を実験で行った．

が図れることもわかった．
ワイルドカード数に制限を加えて行った実験からは，既存手法と Upward Algorithm の比較では，時間ご制限によりパタン総数が少なくなることで計算速度向との目的関数値の減少度・学習性能を表す AUPRC の上は見込めるものの，表現力の低下から最適化・学習性増加度いずれにおいても提案手法が優っていた．また，

能で良い結果を得ることはできなかった．

正例・負例比率の偏った元データではテスト精度の改善度合いが測れなかったため，正例・負例を同数にした人

6 結論

工データに対して同様の実験を行い，テスト精度におい本研究では，文字列集合分類問題に対する機械学習スても，既存手法が 0 であり続けたのに対し，提案手法でキームに対し，最適なパタンを発見する効率的アルゴリは 0.8 まで短時間の計算で得られることを示した．

ズムを 2 つ提案した．このアルゴリズムを用いることで，従来手法よりも高速な最適化・学習を行うことに成

700

Objective function

upwardrandom600

功した．2 つのうち Upward Algorithm はパタン長が500短い場合に特に有効であり，Downward Algorithm は400パタン長が長くなっても十分な速度で計算が可能であることを実験により示した．

300200

本研究で用いたデータは非常に正例の数が少なく，そ100れに対応したアルゴリズムを構成したものの，正例に共00100200300

400500600700800

time of computation (s)図 1. 既存手法と U.A. の比較．20s ごとの目的関通するパタンの発見は長時間の計算を経ても厳しいことがわかった．このため，さらなる高速化やパタンの拡張などが求められるだろう．

数値
0.12
upwardrandom

参考文献

0.1

AUPRC

0.08

0.06

0.04

0.02

00100200300400500600700800

time of computation (s)図 2. 既存手法と U.A. の比較．20s ごとの AUPRC

提案 2 手法をパタン長 b を変えて比較したところ，

b = 8 の場合 Upward Algorithm が計算速度で優って[1] S. Matsushima. (2016). Asynchronous Feature Extraction for Large-Scale Linear Predictors. In Frasconi P., Landwehr N., Manco G., Vreeken J.
(eds) Machine Learning and Knowledge Discovery
in Databases. ECML PKDD 2016. Lecture Notes in
Computer Science, vol. 9851. Springer, Cham.
[2] J. Langford, L. Li and T. Zhang. (2009). Sparse online learning via truncated gradient. In JMLR, vol.
10, pp. 771–801.
[3] H.F. Yu, C.J. Hsieh, K.W. Chang, and C.J. Lin.
(2010). Large linear classification when data cannot
fit in memory. In Proceedings of Knowledge Discovery and Data Mining, pp. 833–842.