Author: kanatoko

AtCoderでアルゴリズムの勉強をして効率性でつまづいている

僕は四捨五入すると50歳になるおっさんであるが、いわゆる教科書的なアルゴリズムを真面目に勉強したことがなかったので、ちょいちょい本を読んだりコードで実装してみたりしている。

そしてAtCoderに流れ付き、少し時間を使って楽しませてもらった。といっても子供の面倒をみる時間が断続的に発生する生活なので開始時間が決まっている競プロのコンテストに出場するような形ではなく、過去問をのんびりと解くスタイル。

AtCoderを使わせてもらって本当に驚いたのが、この過去問で勉強するスタイルが無料で可能だということ。多くの言語がサポートされているし、他人の回答を見ることができる。同じ問題をまったく違うアプローチで解く人のコードを見ると面白いし、何より勉強になる。また、コードが消費する時間やメモリのリソースがかなり正確に計測されるので、こちらも実際の業務のコードを書く上で役に立つ。普通にかなり課金したいサービスである。

さて本題だが、ある程度AtCoderでやってみたのだが、壁にぶつかった。なかなか解けない問題で、なぜ解けないのかがわからないのだ。提出したコードが最初の3つくらいは問題ないが、そのうちTLEとなってしまうようなパターンが多い。おそらく根本的に別のアルゴリズムで計算量を少なくする必要があるのだろうが、このTLEとなる際の入力が秘密の情報であるため、それを推測してみて自分のコードで試す、というサイクルがなかなか廻せない。

僕はもう20年以上仕事でプログラミングをしているが、いわゆるデバッグ作業では、再現性があればかなり楽だが、再現性がないともう諦めたくなるくらい難しくなる。いわゆる「エスパーする」みたいなノリになる。

AtCoderで自分のコードが途中でTLEになるのは、僕の印象では「再現性がないデバッグをしている」ような形になる。手元で、そのアルゴリズムが遅い状態で動かせないのだ。

もちろん頑張って想像し、問題を起こす（TLEになる）ようなデータを自分で探り当てることも何度かやったが、異常に時間がかかってしまうし、心が折れやすい。

ということで、以下のような僕にとって都合がよいアルゴリズム勉強サービスを探している。

  • 自分のコードをアップロードすると勝手に動いてくれて採点してくれる
  • テストが失敗した場合はその入力を見ることができる
  • Javaで提出できる（ｗ

だれかそういうの知ってたら教えてください…

あるいは、サービスではなく、手元のマシンで動かすような問題集（データを自分でダウンロードするようなもの）でもいいかも。

『Wizard Bible事件から考えるサイバーセキュリティ』執筆プロジェクト について

こちらの件、無事にクラウドファンディングが成立したとのことで、おめでとうございます(私も1部購入しておきました)。

ここで取り上げられるであろういくつかの事件について、僕はざっと見た程度で細かく情報を確認はしていないけれど、何人かの方が警察によって（おそらく不適切な形で）精神的にひどい目にあわれたことについて、非常に残念なことだったと思います。

事件の当事者以外のIT技術者（僕も含む）にとっても、特にセキュリティ関係の情報発信をしている人からするとまったく他人事ではなく、簡単に言うと「怖い」状況があるために、クラウドファンディングが成立したという側面もあるだろうと思います。

僕個人の話では、かつてはWizardBibleに大量に記事を投稿させていただいていましたし、今もScutumやVAddyというセキュリティサービスにおいて、主にブログの形でセキュリティ技術の記事を投稿しています。やはり上記の事件を受けて情報発信については非常に慎重になりましたし、会社でも「こういうブログ記事を投稿すること自体はどうだろうか？」といった会話をしたこともあります。

さてここからが本題です。うまく書いて僕の意図を伝えることができるかどうかが心配ですが、書いてみます。

『Wizard Bible事件から考えるサイバーセキュリティ』を書く方に、下記の視点も持って、可能であれば取材して欲しいという点があります。非常に難しいと思いますが。

上記の一連の事件をうけ、「ちょっと乱暴すぎるのではないか」「これはあまりにも強引なこじつけだろう」といったIT技術者を中心とした大きな（警察に対する）反発がありました。そしてその後、同様の事件が減ったように見えます。（本当に減ったのかどうかは私の情報収集能力ではわかりませんが）

仮に減ったのだとすると、やはり警察内部でも、それなりに世間のフィードバックを受けて冷静な判断がなされるような変化があったのではないか。もしあったのなら、それは前向きなものであると思うので、評価してもよいと思います。

もちろん不適切な形で警察に逮捕されたりひどい目にあった人は「警察憎し！」という感情になるのは当たり前なので「警察についてよい評価をする」というのはものすごくイヤだと思います。しかし誰かこの執筆プロジェクトにおいて、警察組織のなるべく上のポジションにいる人から、この「変化」があったのかどうか、あったのならばどのような形なのか（トップダウンで指示があったのか、あるいはそれぞれの組織のレベルでそれぞれそういう方向になったのか）等についてインタビュー等をしてもらえると、非常に面白いだろうなと思います。

サイバー犯罪は本当に悪いやつらが跋扈しはじめており、一方で警察もたまにすごいレベルの捜査と検挙を行っているケースを見るようになりました。最終的には日本国内のIT技術者と警察の間のギャップが埋まり、お互いに協力して使いやすいインターネットが実現されることが理想なので、この執筆プロジェクトがその方向にもうまく作用するようなものになれば最高かなと思います。

ということで書いてみました。あくまで個人のなんとなくの考えを書いただけなので、適当に読み飛ばしてください…

 

 

 

Ubuntuバックアップの理想形に到達した

メインの開発マシン(Ubuntu20.04LTS、GNOMEデスクトップ環境、主にEclipseでJava開発)のバックアップがようやく理想形にたどり着いた。

Linuxにおけるバックアップという概念はそれこそ何十年も前から存在するが、今回到達したのは商用ソフトウェアのVMWare Workstation(2万5000円くらい)を使う、少し亜流な方法である。

このバックアップで想定する障害は、下記のようなもの。

  • 単体のストレージデバイス(SSD)の物理的な故障
  • 誤操作による意図しないファイル、データの消去/上書き
  • 誤操作や意図しないソフトウェアアップデートによってOS等が起動しなくなる障害

想定しない障害は下記

  • 同時に複数のストレージデバイスが物理的に故障する(地震や火災でPC全体が壊れるような状態)

内容を簡潔に書くと、下記のようになる。

  • ゲストOSを作成し、そこにホストOSのデータをコピーする。
  • ゲストOSとして起動できるようにする(/etc/fstabの編集など)
  • ゲストOSを停止した状態で、仮想ディスクをホストOSにマウントする
  • 任意のタイミングで、ホストOS上でrsyncにより差分バックアップを取る
  • たまに、仮想ディスクをアンマウントし、ゲストOSとして起動させ、システム全体として稼働できる状態が保たれていることを確認する
  • ある時点のスナップショットを取りたい場合には、VMWareのスナップショット機能を使う
  • バックアップ全体をさらに(スナップショットも含めて)バックアップしたい場合は、ゲストOSが存在するディレクトリをまるごとどこかにコピーする

この方法のメリットは

  1. rsyncを使うので、差分バックアップとなり、軽量
  2. rsyncを使うので必要な場合の小回りが効く
  3. 任意の時点のスナップショットを取ることができる
  4. 基本的にはデータが1ファイルに入っており、物理デバイスにそのままddすることでリストアできるものであるため、将来的にVMWareの使用をやめるとしても大きな問題はない(スナップショット関連機能は失われる)
  5. シンプルである
  6. バックアップされたデータがシステム全体として整合性を保ち、起動・稼働できる状態になっているか、をバックアップ対象となるメインマシンの上で手軽に確認できる
  7. 大きめのソフトウェアアップデートなどについては、まずゲストOS上で先に適用して、問題ないかを確認できる。確認後はその状態を破棄して適用前の時点(スナップショット)に戻すことができる
  8. ホストOSにマウントできるので、任意のファイルのみ復旧させるなども容易

（7については、もはやバックアップの仕事ではないが、とりあえず出来るということで)

上記のメリットのうち、個人的に最も重要なのは6。システム全体のリストアのテストを、1台のマシン上で、超簡単な操作だけで、ほんの1〜2分で行うことができる。今まで色々なバックアップ方法を試してきたが、これを達成できるものには巡り合っていなかった。

この方法のデメリットはほとんど無いが、強いてあげれば下記の2点。

  • VMWareを買う必要がある
  • バックアップ先が圧縮されないので、バックアップ対象より少し大きいくらいのストレージ領域が必要

具体的な方法は細々とは書かない（興味があるひとがいたら@kinyukaに質問してください)が、下記の点がポイントになる。

  • 最初はフルバックアップをデバイスイメージ全体に対して行うので、バックアップ対象のデータのサイズは、別デバイス上に配置可能なサイズにする必要がある。(まぁ、当たり前だが…)
  • バックアップ先はもちろん、別の物理デバイスにする
  • バックアップ先のVMWareの仮想ディスクは、preallocatedな単一のファイルにする。これによってVMWareが使えない状態になっても(普通はならないが)単にファイルをddでデバイスにコピーするだけで復旧が可能になる
  • ゲストOSとして起動できるようにするため、/etc/fstabはバックアップ対象外とするか、uuidを記述しない形にする（詳しくは書かないのでそのへんはググってくだちい)

それでは皆様、快適なバックアップライフを。

二分探索木の平均探索回数(失敗時)に関するメモ

Isolation Forestの論文に出てくる

c(n) = 2H(n-1)-(2(n-1)/n)

を理解するためにあちこち調べて苦労してしまったのでメモ。

これは二分探索木の平均探索回数(失敗時=外点に到達)を意味している。そのため二分探索木について詳しく記述されている文献や発表資料を見ると、あちこちで証明つきで説明されている。

結局僕が理解できたのは日本語書籍の「アルゴリズムの基礎とデータ構造」のおかげ。Isolation Forestの場合には内点と外点の数え方の関係なのか、上の式は右側がn-1を中心に構成されている。仮に1つずらしてn-1をnとした場合には

c(n)=2H(n)-(2n/n+1)

となる。そしてこれは「アルゴリズムの基礎とデータ構造」で導出される

c(n)=2H(n+1)-2

と同じである。

この式の導出には「アルゴリズムの基礎とデータ構造」のP.99上の方にある

c(n+1)=c(n) + 2/(n+2)

という式がキモになるのだが、この式に至る過程は(この書籍に紹介されている以外のものも含めて)結構面倒くさい。

しかし実は上の式は直感的に理解できるので、その内容をここにメモしておく。

c(n)はn個の内点から構成され得るさまざまな形の、すべてのパターンの木におけるすべての外点のパス長の平均値である。上の式に出てくるのはどちらもcであるので、平均値についてのみ考えればよい。

n個の内点から構成される木(Tnとする)がn+1個の内点から構成される木(Tn+1とする)に変わるときには、Tnでは外点だったある1つの点(vとする)が内点に変わり、さらにその内点に2つの外点がぶら下がることになる。

前述したように「平均についてのみ考える」ことにする。実際には根に近い(浅い)ところにいる点も、深い所にある点も存在しているのだが、それらを全て仮の平均化、均質化された世界に移して考えてみる。するとTnのすべての外点のパス長はc(n)である。このうちの1つがvである。

Tn+1では、vは内点になってしまったが、その内点の先に2つの外点がある。この2つの外点のうち1つは、Tnで外点だったvが移動した先だと考えよう。すると平均値+1の長さの外点となる。もう一方の外点はnがn+1になった際に追加された外点だと考える。こちらもvと同じように平均値+1の長さの外点である。（ここでの平均値はTnについてのものであり、Tn+1ではない)

この2つの外点以外の全ての外点は、まったく長さが変わっていない。つまりすべての外点について平均からの変動を考えると、全体で2だけ増えているのである。

この「増えた2」も平均値として考える場合は全ての外点において平均的に増えたと考え直す必要がある。そのため2を外点の数すなわち「n+2」で割った2/(n+2)が、その差となる。

つまりc(n)に2/(n+2)を足したものがc(n+1)になるのだ。

おしまい。

XBOS Anomaly Detection

What is XBOS?

Cross interaction based outlier score (XBOS) is a cluster-based algorithm for unsupervised anomaly detection. It uses k-means clustering for the first stage, and then calculate cross interaction between clusters as the second stage. Because of this second stage, A small cluster near another large cluster is treated as if that is a middle cluster, so that the data points belong to the cluster is scored ‘not so anomalous’ as a result.

XBOS assumes independence of the features as same as HBOS. XBOS shows very good performance on Kaggle credit card dataset compared to Isolation Forest and HBOS.

kaggle1.png

XBOS is a really simple algorithm and implemented in just 55 lines of Python code.

Source code is available at GitHub.

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

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

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

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

繰り返しになるがこの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追記)

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

(2020/05/03追記)

これは半教師あり学習に分類される方法になると思われるが、Aのデータに対して過剰適合する可能性があるので、それほど最高の方法ではなさそう。Aのデータを増やせば増やすほどよいが、結局Aの数を十分に確保できるのであれば、そのラベル付け(アノテーション)の過程で教師あり学習用のデータを確保できる可能性があり、それならば最初から教師あり学習をした方が精度が高まると考えられる。