GitHubの横幅を広げるbookmarklet

javascript:document.getElementsByClassName(‘container new-discussion-timeline experiment-repo-nav’)[0].style.width = “2200px”;void(0);

Advertisements

Stravaヒートマップで米軍(?)の裏道ぽいの

Stravaのヒートマップが面白い。筆者は横浜市港南区在住で、たまに鎌倉・逗子・田浦あたりのハイキングに出かける。神武寺駅の北側にはいい山があるのに、米軍施設であるため探索することができない。

山レコの地図でこのエリアを見てもらえればわかるが、基本的にハイカーがこのエリアに入っている様子は無い。

Stravaでみたところ、どうやら米軍関係者にも山を愛するものがいるようで、下図の紫の矢印の2つの裏道が存在するようだ。どちらもハイキングコース(紫矢印の上、斜めに地図を横切る、やや明るいオレンジのライン)に到達している。実に興味深いw

繰り返しになるがこの2本のラインは山レコ登録者が通っている形跡はない。

この2つの道に一般人が入ると、おそらく怖いひとに怒られるのだろうと思う。今度、合流点がどうなっているのか気にしながら歩いてみようと思う。

strava_ikego


単純なラベルよりもスコアや確率で表現する方がよい…説

いわゆる教師有り学習の「ラベル」は、例えば

  • このインスタンスはクラス2です
  • このインスタンスはクラス3です
  • このインスタンスはクラス3です

という形で与えられる。これは一般的なので皆あまり疑問に思わなくなってしまっているかもしれないが、実は情報量としてはかなり少ない状態だ。

  • このインスタンスは明らかにクラス2です。
  • このインスタンスはクラス2に近いが、クラス3です
  • このインスタンスは明らかにクラス3です。

という形の方が、より情報量が多い。

普段ベイジアンネットワークを使っていると「迷いのない状況」と「迷う状況」が確率の値として出てくるので、個別にチューニング等がうまくいっているか(=モデルが良くできているか)を把握しやすくかなりいい。
そのため、前者のような「単純なラベルのみが付与されたデータに基づくデータサイエンス」が圧倒的に良く使われている状況に疑問を持っていた。もっとスコアや確率的な情報が与えられる方が良いのではないか、と。

今日偶然アノマリ検知について調べていたら

http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0152173
の「Anomaly Detection Algorithm Output」の項目で(つまり正確には教師有りデータのラベルではなくモデルの出力に関する項目だが)

First, a label can be used as a result indicating whether an instance is an anomaly or not. Second, a score or confidence value can be a more informative result indicating the degree of abnormality.

という記述に出会うことができて、自分がモヤモヤ思っていた事が間違いではなかったと確信できてよかった(興味ある人はこの項全体を読むことをオススメ)。


大量のラベルなしデータを異常検知にどう活かすか

先のエントリで紹介したアノマリ検知の性能評価用フレームワークを作る際に思いついた手法は

インスタンスを正しいクラスに分類できたかどうか(あるいはできなかったかどうか)

ではなく、

あるインスタンスがあるクラスである、と「どの程度の確信の強さで分類するか」

に注目してみた。これはノリとしてはloglossに似ている。モデルがはじき出した結果そのものではなく確率(あるいはスコア)を見る。

http://data.gunosy.io/entry/2016/08/05/115345
より引用
『予測モデルの出力が特定のクラスに属する確率であることが多いので』
『上図の場合には、予測モデル2の評価が高くなります(Multi-class logarithmic loss自体は0に近い方がよい)。
Accuracyで評価した場合には予測モデル1、予測モデル2の双方とも同じ評価になります。』

 

アノマリ検知のモデルを作った後、評価を下記の2つのデータセットで行う。

  • ラベル付きの、少量の「異常」のデータのみのデータセット
  • ラベルなしの大量のデータからなるデータセット。こちらはラベルは付いていないが実際には「正常」と「異常」両方を含む。「正常」が「異常」よりもかなり多いことはわかっている。つまり現場で収集するのが容易なもの。

上記2つのデータセットをそれぞれをA,Bとする。

モデルに求められることは

  • Aを適切な確率(あるいはスコア)で「異常である」と分類(認識)すること
  • Bのデータに対する「異常である確率(あるいはスコア)」の平均値が、より低いこと(この理由は、Bは多くの正常なデータを多く含むため)

の両方を満たすこと。

2つモデルを作って、それぞれについて下記v1/v2を計算する

  • Aの全データについての「異常である」確率(あるいはスコア)の平均値(v1)
  • 同じくBについての平均値(v2)

v1が適切な範囲であれば、v1とv2の差が大きい方が、より優れたモデルである、と言えることになる。これによって複数のモデルの比較を定量的に行うことが可能になる。

上記手法により、ラベル無しの大量のデータを使って自動的にモデルの性能を高めることなどが可能になり特徴エンジニアリング等が客観的に実施できるようになる。

この手法は偶然思いついたのだが、たぶん既に研究者が発見しているのではないかと思う。これから探してみて、見つけたら追記する予定。

(2018/01/23追記)

散々論文等を読み漁ったが、この手法(おそらくメタアルゴリズムに分類されるものだと思う)は誰も紹介していないようだった。もしかしたら結構すごい発見かも…?


アノマリ検知の性能評価フレームワーク

word_path_avg

K-meansを使うアノマリ検知、これまでは
・入力のデータ
・処理(アルゴリズムや前処理・後処理など全て)
・出力される結果
の3つそれぞれをバラバラに見たり変えたりしながら、全体を通じて「ふむ、まぁ動くな…」というレベルまで作ってきたんだけど、そろそろ目で見るのではなく定量的に評価したくなった。
そこで年末の休みの時間を利用して評価するためのフレームワークを作ったら、かなり楽しいことになった。
教師なし学習だけど、データはベイジアンネットワークやシグネチャ等であらかじめ「クロ」と判断されているものと、そうではないものの2種類を用意。
それぞれoutlier/inlierというラベルをつける。inlier側には実質的にはoutlierなデータも多少混じってしまうかもしれない状況。
(たとえばbotのクロール等、攻撃ではないがアノマリな感じのアクセスをするもの)
この2つのクラスのインスタンス群に対してアノマリ検知を行う。それぞれのインスタンスについて、アノマリ側が0、正常側が12くらいの12段階くらいのスコアが計算される。
『outlierラベルが付いた群の平均点とinlier群の平均点の差が広がればアルゴリズムが改善していると考えることができる』という考え方。
実際動かすまでこれを実現できる自信がなかったんだけど、ちょうど初日の出頃の時間にうまく動いた。
・クラスタ数が5より10の方が検知精度が良い
・クラスタ数が10と15の場合、それほど変わらない
・前処理で外れ値を除去すると検知精度が良くなる
などが定量的に見えるようになった。評価のフレームワークがあると急にサイエンスっぽくなっていいね。
教師有り学習だとROC曲線に代表されるように手法が確立されているけど、今回自分で頭をひねって教師なし学習の評価フレームワークを作れたのはかなり良かった。


CodeIQ本[Q57:あみだくじの問題]についてのメモ

これまで、コンピュータサイエンスの真ん中の勉強をしてこなかったので、少しずつやってみようかなと思った。とりあえず書店でよさげなCodeIQの「プログラマ脳を鍛える数学パズル」をゲット。謎のプライドが発動し、いきなり上級編の第四章からやってみることに。上級編の最初はQ57、あみだくじの問題。(以下はこの本の出題内容を知らないとわけがわからないと思うので、該当の本を持っていない人は読んでも時間のムダになります。)

「あみだくじをどういう風にコードに落としこむのか」というとっかかりがまったく掴めず脳みそが真っ白になり、「さっぱりわからねぇ…」という状態が10分ほど続く。我ながら笑った。パズル的なものをコードで解いた経験はほぼゼロだったのだが、10年以上プログラミングで食ってきたのでこういうのもチョチョイとできるイメージを持っていた。全然違うよ。

しかし落ち着いてとりあえず書き始めたら何とか1時間くらいで答えを出すことができ、きちんと一発目で正解。初心者らしく、まず「横線を10本引く」パターンについて総当りし、すべてのありえるパターンの結果を列挙。その中から「横線が9本以下でも起こりえるパターン(こちらも総当り)」をすべて消去し、残ったパターンの数が回答になる、という方法。この方法だと計算量が多いらしく、答えが出るまで結構待たされた。

https://github.com/Kanatoko/codeiq_book/blob/master/q57_amida1.java

アルゴリズムそのものとは別に色々とチューニングの余地がありそうだが、とりあえず答えが合っていたので良しとする。続いて別の方法を少し考えてみることに。

最初の方法は非常に原始的で、まず横線を引くパターンをすべて計算し、次にそれぞれの場合にあみだくじの結果がどうなるかを順番に処理するという形。ここで気づいたのは、あみだくじの横線によって2つの数値が入れ替わるということ。いままで感覚としてあみだくじというのは選んだ要素が階段状に降りていくイメージを持っていたのだが、単純に左右が入れ替わると捉えることもできる。

amida1

上記のように、初期状態は「1 2」だが、横線によって「2 1」という状態に変化する。

さらに、別の捉え方をすることもできる。「横線によって、1が右に移動した」と考えるのだ。このとき「1が右に移動し、2が左に移動した」ではなく、「1が右に移動した。2はそのままの位置にいた」つまり「2は動いていないのだが、1が2の右にきた」と考えるのだ。

これにより「あみだくじに横線を追加することで、任意の要素を右に1つ移動させることができる」と考えることができる。ただし、一番右の要素は移動先が存在しないので、移動させることはできない。

また、「左に移動する」という概念は存在しないと考えることができる。左に移動したように見える要素(上図の2)は移動しておらず、あくまでも左にいたもの(1)が右に来たのだ、と考えることで、「2は左に移動したわけではない」と考えることができる。

少し拡張して縦線が4本あるケースを考えてみる。

amida2

上記は3本の横線があるが、これらをすべて「1を右に動かすため」のものであると考える。「2,3,4は動いておらず、1だけが右に移動した」と考える。

このように考えると、上記の縦線4本のあみだくじで言えば

  • 1は右に最大3移動できる
  • 2は右に最大2移動できる
  • 3は右に最大1移動できる
  • 4は移動できない

となる。今回の問題はすべての横線を引いたときにはじめて出現するパターンを求めるものなので、ひたすら右を目指して移動するパターンのみ考えればよい。(横線が縦に連続した場合は元に戻ってしまうわけだが、そういうケースは無視してよいのだ。)

上図は「1234」という文字列を「2341」に変換するための距離が3、のようないわゆる編集距離のような感覚で考えることができる。(1を3回移動させるので距離が3と考える)

今回の出題内容は「縦線が7本・横線が10本」だが、これだと多いので、縦線が4本・横線が5本のケースを例に考える。

横線が5本ということは、いずれかの要素を選び、合計で5回右に移動させることができるということだ。

例えば、1は最大で3移動できるので、とりあえず3移動させるものとしよう。残りの横線は2本だ。2は最大2移動できるので2を2移動させよう。これで合計の5を使いきった。

amida3

赤線は1を移動させている。青線は2を移動させている。3と4は移動していないと考える。

このように考えると横線が5本の場合は下記3パターンがあり得る。

  • 1が3移動、2が2移動(合計5)
  • 1が3移動、2が1移動、3が1移動(合計5)
  • 1が2移動、2が2移動、3が1移動(合計5)

そのため答えは「3通り」になる。

これをコードに落とし込んだのが

https://github.com/Kanatoko/codeiq_book/blob/master/q57_amida2.java

で、こちらは一瞬で処理が終わる。計算量が少なく済むようだ。

この手のネタをやったことがなかったので最初は再帰させることにも気づかずあっぷあっぷしたが、最終的には非常に良い脳みその体操になった。あみだくじと編集距離の関係に気づくなど予想もしていなかった。


Clojure vs Java速度比較

twitterで「ClojureはJavaより遅いから…」とつぶやいたら複数人に「どんなケースか?」のような質問を受けて驚いた。実はちょっとうれしくて、僕としてもClojureが本当に速いならそれに越したことはない。

少しincanterを使ってデータをいじっている感覚だと、メモリ上に載せた数十万行〜100万行くらいのデータについて処理している感じでもJavaよりもっさりした感覚があった。

元々STMが遅かったのが強烈な印象だったのだが、普通にでかいファイルを処理する際にはClojureはどの程度速いのか測ってみることにした。

テスト内容は超シンプルに、100万行のCSVファイルの1カラム目の最大値を求める、というもの。コードは以下。

https://github.com/Kanatoko/cljbench/

Clojureのコードを書くのが数年ぶりなのでインデントとかよくわからなくてキモいコードですみません。何か致命的なミスをしている気もするがとりあえず動いている。

速度を比較した感じ、Clojureで10かかるところがJavaだと4で終わる感じ。60%速い。

2017/12/4 06:55追記

今回は「普段使い」のパフォーマンス的な比較をしたいので、2つのコードとも「なるべく深く考えずに、とりあえず書く状態」を目指している。カリカリに速くした状態ではない。

例えばJava側だったらsplit(正規表現なので遅い)を避けてカンマの位置をindexOfで求めに行く方がずっと速くなると思うが(業務でやっているのサーバのパフォーマンスチューニングはそんなのばっかり)、何をやってるのかわかりにくくなるし、最初のカラムではなく別のカラムを求める場合にコードの変更点が増えるので。でももしかしたらsplitは単純なケースだと速いかも。

Clojure側はできるだけClojureらしいコードにしたい。ClojureのコードにBufferedInputStream…とかJavaのクラスがなるべく出てこないようにしたい。

2017/12/4 07:55追記

添削して頂いたらJava版より1〜2割程度遅いくらいまで速くなった。これだと「Clojureは遅い」という評価は当てはまらない。充分に速いと言える。素晴らしい。

このチューニングが具体的にやっているのは「Javaの関数を直接使うようにした」という点なのが微妙(Clojureの関数とJavaの関数が入り乱れてキモいコードになる)だと感じたが、Clojureの哲学としては「Javaを歓迎」して良いはずなのでこれに慣れていけばいいだけか。

あやぴさんありがとうございました。