もちもちしている

おらんなの気まぐれブログ

ニューラルネットの調和解析

はじめに

この記事はDeep Learning Advent Calendar 2016 3日目の記事です.

とうとうAdventCalendar以外でブログを更新しなくなってしまいましたが,元気よく書いていきたいと思います.

今回はニューラルネットブラックボックス性とその解析をしている論文の紹介です.Deep Learning Advent Calendarをやるぞ!と言っておきながら,この記事で取り上げるのは浅いニューラルネットです.

ニューラルネットブラックボックス性とその議論

ニューラルネット自然言語処理音声認識,ゲームAIなどの様々なタスクに応用されるようになり,いずれも大きな成果を挙げていることに間違いはありません.

しかしその一方で,ニューラルネットは中間層を挟むため,学習で得られる内部状態は不明瞭となります.このことから,結果の考察がしにくいという理由で忌避されることも多いと思います*1

この問題は1980年代後半から議論されています.議論は中間層の素子数と目的関数の近似誤差の関係に着目するという方向性となり,"基底となる関数を自由に選べるという条件下で,中間層素子が無限にあれば任意の関数を近似できる"という命題のもと,様々な証明のテクニックが考案されました.Irie, Miyake, Cybenko,Whiteらは,フーリエスライス定理やラドン変換などの概念に基づいて,この命題を証明しています[1, 2, 3].Funahashiはまた,Kolmogorov-Arnoldの定理とSprecherの定理を使って証明を与えています[4].

この議論を進めていくうちに,Anzellottiは,目的関数のクラスを限ると,3層ネットワークの平均二乗誤差の上限は中間層の数に反比例することを示しました[5].それは多層ネットワークと勾配降下法を用いた手法が,次元の呪い*2に束縛されないことを意味しています.

1996年にMurata[6],1998年にはCandes[7]が,ニューラルネット非線形変換に適したRidge関数を用いて,Ridge関数の積分変換と逆変換を定義し,この積分表現(後述します)を利用することで,Murataらは単純な3層ネットワークの中間層の素子に直接的な意味を与えられることを示しました. このアイデアは,3層ネットワークの関数近似の問題を過完備基底関数系上での展開と捉え.その近似性能を論じたものです.

積分表現はニューラルネット関数解析的に扱えるという大きなメリットがあります.この積分表現について,少しだけ触れていきたいと思います.

まずはRidge関数の積分表現です.

Ridge関数を用いた積分表現

Ridege関数の積分表現は以下のリンク先で書いたので,こちらを参照して頂きたいと思います.

hackmd.io

MurataはこのRidge関数の積分変換を3層ネットワークに取り入れることで,中間素子数nの3層ネットワークの平均二乗誤差がオーダ1/n以下で近似できると定量的に示しました.

その後,Sonodaらはこの理論を発展させ,活性化関数の新しいデファクトスタンダードであるRectified Linear Unit (ReLU)を用いた場合でも,3層ネットワークが上記で示した万能近似性能を有していることを示しています[8].

次は,ニューラルネット積分表現です.

ニューラルネット積分表現

活性関数ηを持つニューラルネット(3層ネットワーク)の関数 \( f : \mathbb{R}^m → \mathbb{C} \)の近似を以下のように定義します.

f:id:olanleed:20161203060403p:plain

この時,\( (a_j, b_j) \) は中間層(hidden layer)のパラメータで,\( c_j \)は出力層のパラメータです. このニューラルネット\( g_J(x) \)は,以下のニューラルネット積分表現を離散化することによって得ることができます.

f:id:olanleed:20161203060517p:plain

ニューラルネットの和の部分を積分に置き換え,連続化した関数を得ることを積分表現といいます.

\( \mathbb{Y}^{m+1} \) は中間層のパラメータ空間 \( \mathbb{R}^m \times \mathbb{R} \)です.右辺は,ηに対するT(a, b)の双対リッジレット変換とされています.

f:id:olanleed:20161203055625p:plain

T(a,b)において,Ψに関するfのリッジレット変換を代入することによって

f:id:olanleed:20161203061137p:plain

を得ます.そして,Ψとηが許容条件

f:id:olanleed:20161203065151p:plain

を満たす時,fに対して次のような再生公式が成り立ちます.

f:id:olanleed:20161203061850p:plain

得られた再生公式を離散化することにより,活性化関数ηを用いたニューラルネットの近似性能を検証することができるとされています.

ReLUネットワークへの拡張

先の方法は活性化関数ηが有界関数(sigmoid関数やtanh関数)を用いた場合でのリッジレット変換であり, ReLUのような非有界関数を扱うことは想定されていませんでした.そこでSonodaらはアイデアを拡張して,活性化関数ηがReLUのような非有界かつLizorkin超関数に属するクラスであっても,ReLUネットワークを積分表現で分析できることを示しました.ReLUネットワークの万能近似性能については,フーリエスライス定理,ラドン変換,パーセバルの定理を用いた3つの再生公式によって,それを満たすことが示されています.そして,ニューラルネットが学習の結果として獲得する情報表現の正体はリッジレット変換であると述べています.

この論文の非常に興味深い主張として,許容条件に従えば,リッジレット変換を単純に離散化することによって,誤差逆伝播を経たずにネットワークを学習させることが可能であるということです.また,この理論を応用することでランダム初期化よりも有利な条件で学習させる方法も示しています[9].

深層学習への応用

深層学習の積分表現は自明ではないらしく,論文は投稿の最中ということなので,公開を待つことにします.

おわりに

ニューラルネットの解析は私が強く興味を持っている研究の一つなので,今回取り上げた論文はとても面白く感じました. 私の理解が足りてない部分が多々あるので,それぞれの要素や論文についても時間が取れたら書きたいところです.

参考文献

[1] Irie and Miyake. Capabilities of three-layered Perceptrons. In Proceedings of International Conference on Neural Networks. pp. 641-648 (1988).
[2] Cybenko. Approximation by superpositions of a sigmoid function. Mathematics of Control, Signals and Systems, pp. 303-314 (1989).
[3] White H. Connectionist nonparametric regression: multilayer feedforward networks can learn arbitrary mappings. Neural Networks. pp. 535- 549 (1990).
[4] Funahashi. On the approximate realization of continuous mappings by neural networks. Neural Networks. pp. 183-192 (1989).
[5] Girosi and Anzellotti. Convergence rates of approximation by translates (Tech. Rep. A.I. memo 1288). Articial Intelligence Laboratory, Massachusetts Institute of Technology (1992).
[6] Noboru Murata. An Integral representation of functions using three-layered networks and their approximation bounds. Neural Networks, Vol. 9, No. 6, pp. 947–956 (1996).
[7] Cands, E. J. Harmonic analysis of neural networks, Appl. Comput. Harmon. Anal. 6, pp. 197-218 (1999).
[8] Sho Sonoda, Noboru Murata. Neural network with unbounded activation functions is universal approximator. Appl. Comput. Harmon. Anal (2015).
[9] Sho Sonoda and Noboru Murata. Sampling hidden parameters from oracle distribution. In 24th Int. Conf. Artif. Neural Networks, Vol. 8681, pp. 539–546 (2014).

*1:膨大なデータ量と計算リソースの必要性も含まれると思いますが

*2:精度が入力次元の大きさに強く依存する性質

第24羽 chainer-goghを愛した少女と名画に愛された少女

この記事はごちうさ Advent Calendar 2015 24日目の記事です.

gochiusa.connpass.com

はじめに

パリのルーヴル美術館に行きたい思っているのですが,資金的な問題があるため毎日インターネットでグーグル美術館です.どうもolanleedです.

論文投稿に追われたり風邪をこじらせたり,激しいDeep LearningMacBookが故障したりする怒涛の12月でしたが,今期のアニメ「ご注文はうさぎですか??」のおかげで正気を保てています.

ありがとう,ごちうさ

今日はchainer-goghを使い,ごちうさの登場人物と世界の絵画を合成して「ご注文はうさぎですか?」美術展覧会を開きたいと思います.

今回用いたchainer-goghについてはこちらに書かれております.

https://research.preferred.jp/2015/09/chainer-gogh/

それではご覧下さい.

1枚目「コーヒーを注ぐチノ」

f:id:olanleed:20151224011351p:plain

ヨハネス「牛乳を注ぐ女」とチノちゃんの合成です.

油彩のタッチにより独特な雰囲気となってますね.

2枚目「淑女」

f:id:olanleed:20151224011331p:plain

マルタン・カヴェルの絵画(名前忘れました...)とリゼさんの合成です.

淑女というタイトルをつけたんですけど,元のリゼさんがエロいためなんかエロいです.

3枚目「金髪比」

f:id:olanleed:20151224010849p:plain

ダ・ヴィンチの人体図とシャロちゃんの合成です.

巨匠同士の絵を合成したはずなのに,なぜか落書きっぽい絵が生成された...

4枚目「桜下千夜」

f:id:olanleed:20151224010506p:plain

菊川英山「桜下美人」とチヤさんの合成です.

チヤさんと浮世絵の画風がすごくマッチしてます.

傑作「叫び」

f:id:olanleed:20151224005631p:plain

ムンク「叫び」とココアさんの合成です.個人的に一番これが好きです.

ココアさんの表情が「叫び」をよく表現してます.

Deep Learningのハイパパラメータの調整

この記事はDeep Learning Advent Calendar 2015 23日目の記事です.

はじめに

コンピュータセキュリティシンポジウム2015 キャンドルスターセッションで(急遽)発表したものをまとめたものです.

また,私の体力が底を尽きてるので,後日に大幅な加筆・修正します.

Deep Learning Advent Calendar 21日目の記事はすいません,しばらくお待ちください...

Deep Leaningの光と闇

Deep Learningが様々なタスクにおいて大きな成果を上げています.また,各種フレームワークの登場によって,Deep Learningの導入や実践する敷居が大幅に下がりました.このことから,Deep Learningを活用していこうと考えてる,あるいはすでに活用している企業や研究者が増えてきています.

Deep Learningによって従来の手法を大きく上回る性能を発揮したり,今まで実現できなかったことが実現できたりと脚光を浴びてる一方で,「あるタスクにDeep Learningを導入したものの,所望の効果が得られない」あるいは「従来の手法に性能で負けてしまった」などと,うまくいかないこともあると思います.

高いポテンシャルを秘めてることは確かのですが,Deep Learningは深いアーキテクチャなだけに深い考察が必要です.そのため,以下のことを考えなくてはなりません.

  1. タスクごとにネットワークの構成を考えなくてなはらない

  2. 最適な(あるいは最適に近い)ハイパパラメータを求めなくてはならない

1に関しては,例えば画像認識をやる場合はCNNを使うと思います.CNNにも色々な構成があるので,問題に応じて色々構成を変えると性能が良くなることがあります.タスクに応じてstate-of-the-artな構成が公開されていることがあるので,それを用いるのが良いでしょう.

一番問題なのは,2のハイパパラメータの調整だと思います.

機械学習アルゴリズムは基本的に調整が必要なハイパパラメータが存在します.これをデタラメに調整したかと厳密に調整したかどうかで性能は雲泥の差があります.

学習させる全てのタスクにおいて共通の最適なハイパパラメータがあれば,1回だけ厳密に求めてあとは使い回せば良いのですが,基本的にタスクごとに求める必要があります.

AROWやSCWなどのオンライン線形分類器はハイパパラメータが1・2個しかないのに対して,ニューラルネットワークで構成されていることが多いDeep Learningでは,ハイパパラメータはとんでもない数になります(学習係数,隠れ層のユニット数,層の段数,epoch,dropout,momentum,weight decay,batch size...etc.).

これを探索する手法はグリッドサーチがよく用いられます.しかし,ハイパパラメータが1つ増えるたびに組み合わせの数が爆発的に増えるため,1回の試行時間が長いかつ組み合わせ数が多いDeep Learningでグリッドサーチを行うのは現実的ではありません.

では,このたくさんのハイパパラメータをどうやって調整するのでしょうか.

ランダムサンプリング

ランダムサンプリングとは,文字通り無作為にパラメータを抽出していく方法です.

f:id:olanleed:20151223151040p:plain

パラメータには重要なパラメータとそうでないパラメータが存在します.グリッドサーチではこの重要なパラメータが探索から漏れてしまうことがありますが,ランダムサンプリングだとこれを拾えるだけでなく,探索の分布や幅などを変えるといったことが可能です.

他にも探索が高速,いつ計算を打ち切ってもよい,並列化が容易などでグリッドサーチよりも大きなメリットがあります.

詳細は以下の論文に書かれています.

http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf

Bayesian Optimization

http://papers.nips.cc/paper/4522-practical-bayesian-optimization-of-machine-learning-algorithms.pdf

関数の最適化問題とみなして,学習器を最適化していく手法が存在します.ハイパパラメータをx,学習器の誤差関数をf(x)として,このf(x)を最小にするxを求めていきます.

ただし,Deep Learningの関数の形はわからないため,BlackBox関数の最適化問題となります.

BlackBox関数の最適化手法には遺伝的アルゴリズムや差分進化法*1がなどが有名でしょう.

この項で紹介するBayesian Optimizationでは,"BlackBox関数の事前分布を仮定し,事後分布を見て最適化する"という手法をとっています.

Bayesian Optimizationの流れは以下のとおりです.

  1. f(x)を何かしらの手法で事前分布を仮定する
  2. ランダムに生成したサンプル点のf(x)を評価し,f(x)の事後分布を決める
  3. 得たf(x)の事後分布と,サンプル点の候補としての良さを測る

Bayesian Optimizationを実行する際に行われなければならない二つの主要な項目があります.

第一に,BlackBox関数の事前分布を仮定する必要がありますが,このBlackBox関数は直接最適化が難しいため,何かしら計算しやすい形で近似します.論文の著者は,柔軟性と扱いやすさから"Gaussian process "という手法を用いています.

Gaussian processについては以下の記事が参考になります.

naoyat.hatenablog.jp

Gaussian processは平均と共分散をパラメータとして受け取りますが,共分散を計算するためにはカーネルが必要です.

論文では ARD Matern 5/2と呼ばれるカーネルを利用しています.

f:id:olanleed:20151223170843p:plain

第二に,GPでBlackbox関数を近似した後,次に調べるサンプル点を決める必要があります.これを闇雲に決めるのではなく,いくつかサンプルする候補を作って「候補の良さ」を測ります.

これに"Acquisition Function"というものを使います.これはサンプル点がf(x)を最小にするような期待値を算出するもので,算出した期待値を「候補としての良さ」とします.

Acquisition Functionには以下のようなものがあります.

Probaiblity of Improvement (PI)

f:id:olanleed:20151223171646p:plain

これまでのベストを更新する確率が最大となる点を次のサンプル点とする.

Expected Improvement (EI)

f:id:olanleed:20151223172128p:plain

これまでのベストに対してどれだけ更新できそうかの期待値を最大化する点を次のサンプル点とする.

GP Upper Confidence Bound(GP-UCB)

f:id:olanleed:20151223172418p:plain

平均と分散の和がもっとも大きなところを次のサンプル点とする.

論文ではEIが一番性能が良いとされています.ただし,Acquisition Functionも多峰性の関数なので,ランダムに生成した候補点を用いてx_t = argmax(a(x_m))となる候補x_mを次のサンプル点x_tとします.

上記より,Bayesian Optimizationではx_t = argmax a(x_m)x* = argmin f(x_t)という過程を繰り返して目的関数を最小化していきます.

おわりに

まとめです.

  • 気軽に探索したいのであればランダムサンプリングを使う
  • 少し気合を入れて探索したいのであればBayesian Optimizationを使う

Bayesian Optimizationも実装がかなり出回っているので,そのうち試してみようと思います.

最後の方がかなり適当になってしまったので,後日加筆します.

RNNを使った機械翻訳モデルで遊ぶ

この記事はDeep Learning Advent Calendar 5日目の記事です.

はじめに

皆様,ご無沙汰にしております.olanleedです.

とうとうAdvent Calendar以外でブログを更新しないダメな人間になってしましました.更新しようといろいろ考えてたのですが,学会やらジャーナルへの論文投稿などがあって,なかなか厳しいものがありました.

この12月は異常なまでにAdvent CalendarとLTを入れたので,怒涛の更新になりそうです.お付き合いください.

それでは本題に入りたいと思います.

RNNを用いた機械翻訳

Deep Learningが様々な分野で大きな成果を出している現在,統計的機械翻訳でもRecurrent Neural Network(RNN)を活用した研究が成功を収めています. 今回はRNN(LSTM)を用いた翻訳モデルの一つであるSequence to Sequence Modelを実装して遊んでみました.

Sequence to Sequence Modelの主要な構成要素であるRNN-LSTMについてはこちらをご覧下さい.

olanleed.hatenablog.com

Sequence to Sequence Model(Seq2Seq)とは

seq2seqとは,異なる長さの翻訳元の単語列(Sequence)を入力とし,異なる長さの翻訳先の単語列(Sequence)を出力としてマッピングする手法です.

f:id:olanleed:20151205025212p:plain

翻訳元の単語列ABCを4層からなるDeep LSTMで読み取っていき,隠れ状態ベクトルを求めます.End of Sentenceが来たら翻訳先の単語列WXYZを出力するような学習をさせます.この時,EncoderとDecoderとして利用するDeep LSTMは別々に学習させる必要があります.

seq2seqの著者は,性能を向上させるために

  • Decode時に単純なビームサーチを使用して,最も可能性の高い翻訳を探索する

  • 5個のDeep LSTMを用いてEnsembleさせる

という手法をとっています.

しかし,それよりも単純かつ効果的な手法に「入力文を反転させる」というのがあります.翻訳元単語列ABCとあったら,CBAと読み込んでいき,翻訳先単語列WXYZを出力させる感じです.

もちろん,全部組み合わせたEnsemble+Beam Search+入力文反転が一番いい結果を出していますが,入力文反転だけでも十分な気がします.

似たような手法にRNN Encoder-Decoder Modelも存在します.こちらも読んでみるといいでしょう.

また,RNNのこういった手法は言語だけでなく画像にも使うことができ,CNNの出力をLSTMでエンコードすると,画像に対する説明文を生成できるRNNを実現することができます.

Google

f:id:olanleed:20151206171410p:plain

f:id:olanleed:20151206030342p:plain

http://arxiv.org/pdf/1411.4555.pdf

Stanford University

f:id:olanleed:20151207111414p:plain

https://cs.stanford.edu/people/karpathy/cvpr2015.pdf

翻訳モデルで何をするのか

seq2seqを使って素朴に機械翻訳をするのはあまりにも芸がないと考えたので,今回は「適当なタイトルを与えると,ライトノベルっぽいあらすじを生成する」というのを題材にしました.

翻訳元をタイトルにして,翻訳先をあらすじに設定します.

学習時の制約

ライトノベルのタイトルとあらすじは各レーベルから16000件以上集めました.しかし,今回は6000件くらいで試しています.レーベルにも偏りがあります.

時間の問題もあるため,元の論文では4層のLSTMを使ってますが,2層に減らす,Dropoutをしない,など学習時間をできるだけ短くしました.性能向上のアプローチも入力文反転のみです.

デモンストレーション

ライトノベルや漫画などから無作為に選んだ学習させてないタイトル,適当に思いついたタイトルを入力して,どのような出力が返ってくるか見てみたいと思います.

学習させてないタイトル

f:id:olanleed:20151210165048p:plain

お兄様なら巨大な陰謀の解決など朝飯前ですね.

f:id:olanleed:20151210172334p:plain

何となく,あらすじっぽい感じがします.

f:id:olanleed:20151210152554p:plain

こんな壮大な世界観の作品でしたっけ...

f:id:olanleed:20151210180614p:plain

ツンデレ な 」を予言する、とは?

f:id:olanleed:20151210184053p:plain

異世界に転生する定めよ 漢

適当に思いついたタイトル

f:id:olanleed:20151210153241p:plain

ラノベっぽい! けど話が転々としたり微妙に日本語になってなかったりしてますね.

f:id:olanleed:20151210190311p:plain

急展開すぎる...

f:id:olanleed:20151210164624p:plain

ちょっと哲学的過ぎますね...

課題

タイトルと関係してそうなあらすじは生成されていますが、そうでないのが多い感じがします.日本語になってない文書も見受けられます.

今回は制約が多かったので,今後は学習データを増やしたり,モデルを見直したりして実験してみたいと考えています.

また,翻訳元は文字N-gram,翻訳先は形態素N-gramでやってるのですが,こちらも文字N-gramにするかして,自然な日本語が生成できたらいいなと考えています.

なお,実装したモデルは会社から拝借したものであるためソースコードを公開することができません.ですが,GoogleのTensorflowにはseq2seqが実装されてるとのことなので,こちらを利用してみるといいかもしれません.

https://www.tensorflow.org/versions/master/tutorials/seq2seq/index.html

おわりに

学習に手間取ってましたが,5000円分のAWSクーポンあったので使えばよかった ~終~

次回は前半と後半に分けてRNNで文書のポジネガ判定をやってみたいと思います.お楽しみに.

Recurrent NNで文書のポジネガ判定する(モデル考案編)

この記事はDeep Learning Advent Calendar 7日目の記事です.

準備が大変なので前後半にわけてやりたいと思います.前半はモデルの考案と考えてる応用先について書きます.

はじめに

Deep Learningは画像認識や音声認識で多大な成果を挙げていますが,自然言語処理の分野でも大きな変化をもたらしたと思っています.現に,評判分析や機械翻訳などでDeep Learningを用いた手法は他を圧倒する成果を挙げています.

そのため,機械学習自然言語処理に取り組んでいる私にとっても,Deep Learningによる自然言語処理がとても熱いです.

今回は実験として,Deep Learningの一つであるRecurrent NNを使い,文書が肯定的(Positive)なのか,否定的(Negative)なのかを分類する感情分析をやってみたいと思います.

感情分析ではRecursive NN*1やParagraph Vectorのほうが有名な気がしますが,あえてRecurrent NN-LSTMで挑戦してみたいと思います.

Recurrent Neural Networks

通常のフィードフォワードニューラルネットワークは入出力は固定長で,文書などの可変長の入力に対応させるためには何かしらの方法で文書の特徴ベクトルを固定長にするが必要です.文書の特徴ベクトルを固定長にする手法は以下が一般的でしょう.

  • Bag-of-Wards
    文書中の単語の出現回数を素性とする

  • Binary
    文書中に単語が出現したか否かを1,0で表現して素性とする

  • TF-IDF
    TF:Term Frequency -> 単語の出現頻度,IDF:Inverse Document Frequency -> 単語の文書頻度であるdf(document frequency)の逆数*2

しかし,これら手法は「単語数がそのまま次元数になるので超高次元になりやすい」「語の順序が失われる」という問題があります*3

そこでRecurrent Neural Networks(RNN)の考え方です.

RNNは時系列を扱えるニューラルネットワークで,ある時刻tにおける隠れ層の状態を,次の時刻t+1の入力に使うものです.

これにより,文書や音声など,可変長の入力に対応しています.

f:id:olanleed:20151207231516p:plain

Long Short-Term Memory(LSTM)

RNNで可変長の入出力に対応できるようになったので無敵か!?と思うかもしれませんが,素朴なRNNには問題があります.

RNNの勾配計算にはBack Propagation Through Time(BPTT)という方法が使われています.RNNは時間方向に展開すると,非常に長いニューラルネットワークと見なすことができます.

これをBackPropagationして勾配を計算していくのですが,誤差信号が長い時間を遡っていくと,誤差信号が消失したり,非常に大きくなったりしたりします.

誤差信号が大きくなるのは正規化することで対処可能ですが,消失するのはどうにもなりません.

この問題に取り組んだのがLSTMです.LSTMは,この誤差信号をトラップして,うまいこと伝搬させる仕組みを設けることで,長期依存を学習させることを可能にしました.

LSTMはnishioさんのスライドで詳しく書かれています.

www.slideshare.net

ポジネガ判定で使うために考案したモデル

RNN-LSTMで以下の図のようなモデルをdeeplearning.netを参考に考えました.

f:id:olanleed:20151207214940p:plain

参考にしたモデルの改良点として

  • LSTMを多層化

  • Meam PoolingをMax Poolingに変更

  • 分類器にAROWを採用

が挙げられます.

Meam PoolingをMax Poolingにした理由として,Max poolingで得られる特徴ベクトルは識別性能が高いこと,線形分類器との相性が良いことです.その根拠は以下の論文で述べられています.

http://www.di.ens.fr/willow/pdfs/icml2010b.pdf

分類器にAROW*4を採用した理由としては,調整すべきハイパパラメータが少なく,識別性能が高いことから,個人的に使い勝手がいいという理由です.ギリギリまで精度が欲しい場合はSCW*5などを利用するといいかもしれません.

応用先

現在,私は修士論文とは別に,卒業までにやっておきたいとDeep Learningによるマルウェア検出に取り組んでいます.

構想としてはマルウェアを静的解析して得た素性(Hexdump,逆アセンブル)と動的解析して得た素性(APIの呼び出しなど)を,それぞれこのモデルで学習させ,アンサンブルさせることでうまいこと検出精度を高めることができないかと考えています.

おわりに

次回はこのモデルを実装し,文書のポジネガ判定をやってみたいと思います.お楽しみに.

*1:Recursive Neural Networks:http://www.iro.umontreal.ca/~bengioy/talks/gss2012-YB6-NLP-recursive.pdf

*2:TF-IDF:http://www.cse.kyoto-su.ac.jp/~g0846020/keywords/tf-idf.html

*3:この問題を解決している方法としてParagraph Vectorもあります

*4:Adaptive Regularization of Weight Vectors:http://www.cs.jhu.edu/~mdredze/publications/nips09_arow.pdf

*5:Exact Soft Confidence-Weighted Learning:http://icml.cc/2012/papers/86.pdf

オンライン機械学習ライブラリを作ったので宣伝

はじめに

MochiMochiというSCW、AROW、Adagrad_RDA、ADAMといったオンライン線形分類器を実装し、ライブラリとして使えるようにしたので公開します。
使い方はexampleを参考にしてください。

olanleed/MochiMochi · GitHub

実装したアルゴリズム

それぞれのアルゴリズムの解説は検索すれば詳しい記事が出てくると思うので、ここではしません。

ADAM

ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION

http://arxiv.org/pdf/1412.6980v4.pdf

Adagarad RDA

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

Adagarad = Adaptive Gradiant
RDA = Regularized Dual Averaging

http://www.magicbroom.info/Papers/DuchiHaSi10.pdf

AROW

Adaptive Regularization of Weight Vectors

http://www.cs.jhu.edu/~mdredze/publications/nips09_arow.pdf

SCW

Exact Soft Confidence-Weighted Learning

http://icml.cc/2012/papers/86.pdfs

今後の予定

マルチクラス分類と回帰ができるようにします。

おわりに

Pull Requestお待ちしております!

D言語でコルモゴロフ-スミルノフ検定

この記事はD言語 Advent Calendar 2014 24日目の投稿です。

なぜこの題材を選んだのか

私は研究室内で行われたプログラミング講習にて、DDoS検知システムを作りました。その検知ロジックにコルモゴロフ-スミルノフ検定を利用したのですが、Rubyで実装したため、とても遅いのが問題でした。

そこで、ネイティヴで動き、C++よりもはるかに習得が容易だと私のまわりでHotなプログラミング言語であるD言語で実装し直してみることにしました。

コルモゴロフ-スミルノフ検定とは

コルモゴロフ-スミルノフ検定(以下、KS検定)とは、標本Xと標本Yの分布の相違を計る仮説検定のひとつです。

出典:http://sysplan.nams.kyushu-u.ac.jp/gen/edu/MarineStatistics/2007/kougi12/kougi12.pdf

計算手順

1. 標本Xの累積確率分布 S_n(x)と、標本Yの累積確率分布S_m(y)を求める。
2. 上記の2つの累積確率分布の差の絶対値の最大値であるKS統計量Dを求める。


D=max|S_n(x)-S_m(y)|

3. Dから検定統計量\chi ^2、相関係数pを算出する。


\chi ^2=4 D ^2 \frac{sum(x)sum(y)}{sum(x)+sum(y)}


p=min(1, qchi2(\chi ^2, 2) ^2)

4. 帰無仮説の採否を決める(有意水準5%の場合)

p > 0.05の場合 : 帰無仮説の採択
p <= 0.05の場合 : 帰無仮説の棄却

カイ2乗分布を求める

qchi2はカイ2乗分布の上側累積確率を求める関数です。実装は以下の通りです。

//正規分布の下側累積確率
auto p_nor(immutable double z)
in {
  assert(z >= 0.0 && z <= 3.09);
}
out(probability) {
  assert(probability >= 0.0 && probability <= 0.499);
}
body {
  double t, p;
  t = p = z * exp(-0.5 * z * z) / sqrt(2 * PI);

  for(size_t i = 3; i < 200; i+= 2) {
    immutable auto prev = p;
    t *= z * z / i;
    p += t;
    if (p == prev) { return 0.5 + p; }
  }
  return (z > 0.0) ? 1.0 : 0.0;
}

// 正規分布の上側累積確率
auto q_nor(immutable double z)
in {
  assert(z >= 0.0 && z <= 3.09);
}
out (probability) {
  assert(probability >= 0.001 && probability <= 0.5);
}
body {
  return 1.0 - p_nor(z);
}

//上側累積確率
auto q_chi2(immutable int df, immutable double chi2)
in {
  assert(df >= 1 && df <= 300);
  assert(chi2 >= 0.00003927 && chi2 <= 366.844);
}
out(probability) {
  assert(probability >= 0.0 && probability <= 1.0);
}
body {
  double s, t;
  if ((df & 1) == 1) { //自由度が奇数
    const auto chi = sqrt(chi2);
    if (df == 1) { return 2.0 * q_nor(chi); }
    s = t = chi * exp(-0.5 * chi2) / sqrt(2 * PI);
    for (size_t i = 3; i < df - 1; i += 2) {
      t *= chi2 / i;
      s += t;
    }
    return 2 * (q_nor(chi) + s);
  } else { //自由度が偶数
    s = t = exp(-0.5 * chi2);
    for (size_t i = 2; i < df - 1; i += 2) {
      t *= chi2 / i;
      s += t;
    }
    return s;
  }
}

KS検定を行う

KS検定を行うプログラムは以下の通りになります。

//累積和を求める 
auto cumsum(immutable double[] a) {
  auto b = cast(double[])a;
  foreach(i; 1 .. a.length) {
    b[i] = a[i] + a[i - 1];
  }

  return b;
}

auto ks_test(immutable double[] x, immutable double[] y)
in  {
  assert(x.length == y.length);
 }
out(results) {
  assert(results[2] >= 0.0 && results[2] <= 1.0);
}
body {
  immutable auto sum_x = x.reduce!("a + b");
  immutable auto sum_y = y.reduce!("a + b");
  auto cum_x = cumsum(x).map!(s => s / sum_x);
  auto cum_y = cumsum(y).map!(s => s / sum_y);

  double[] cum = new double[cum_x.length];

  for(size_t i = 0; i < cum.length; i++) {
    cum[i] = abs(cum_x[i] - cum_y[i]);
  }

  // 累積分布関数の差の最大値
  immutable auto d = cum.reduce!(max);
  // 検定統計量
  immutable auto chi = 4 * d * d * sum_x * sum_y / (sum_x + sum_y);
  // 相関係数(p値)
  immutable auto p = [1.0, pow(q_chi2(2, chi), 2.0)].reduce!(min);

  return [d, chi, p];
}

void main() {
  immutable auto x = [1.0,2.0,1.0,3.0,2.0,3.0,3.0,2.0,7.0,11.0,10.0,9.0,13.0,13.0,22.0,17.0,23.0,20.0,17.0,14.0,13.0,5.0,2.0,1.0,1.0,1.0];
  immutable auto y = [0.0,1.0,2.0,2.0,4.0,5.0,6.0,8.0,10.0,7.0,16.0,17.0,17.0,13.0,19.0,13.0,18.0,10.0,4.0,6.0,6.0,5.0,1.0,3.0,0.0,0.0];

  immutable auto p = ks_test(x, y)[2];

  // 帰無仮説の採否(有意水準5%)
  // p <= 0.05 (帰無仮説の棄却:二つの分布に差があると言える)
  // p > 0.05 (帰無仮説の採択:二つの分布に差があると言えない)
  (p <= 0.05).writeln();

}

実装は以上となります。全体の実装は以下のサイトに置いてあります。

KS_test.d · GitHub

感想

Rubyで実装したときは楽に実装できましたが、D言語でも同じくらい楽に実装できました。D言語最高〜〜〜✌('ω')