無作為抽出のトリック
この記事で、「ある集合の上位 5% を 95% の確率で選択するためには、全体のデータ数によらず 59 件取得すれば十分である」という命題を使用しました。これを証明しましょう。
集合 U の部分集合 Q があり、 Q の要素数は U の要素数に対して割合が p だとします。このとき更に U の部分集合である P を考えます。P に Q の要素が全く含まれない確率は ですから、 P のうち少なくとも 1 つの要素が Q に含まれる確率は です。ここで
とおくと
が得られます。このとき , とすると、 です。つまり、ある集合から無作為に複数の要素を選択する際、ある 5% の要素を 95% の確率で選択するためには、 59 個の要素を選択すれば十分である、ということになります。
なんだか狐につままれたような気分になりますが「95% の確率で選択する」というところがミソですね。シンプルですがなかなか強力な技だと思います。
参考文献: A. J. Smola and B. Schölkopf, “Sparse Greedy Matrix Approximation for Machine Learning", inProceedings of 17th International Conference on Machine Learning, pp. 911-918, 200.
会社の創業記念パーティのBGMを振り返る
弊社の Advent Calendar ネタにするつもりだったが、その前の流れがみんな真面目だったのでお蔵入りにしかけた内容。
今年の6月に会社の創業記念パーティがあり BGM を選曲したので振り返る。一晩で選んだので投げやり感もあるがご愛嬌。あと「音楽好きです!」といっておきながらこういうパーティ向きの曲のレパートリーが少なすぎることに後から気づいた。
会場は青山迎賓館という洋式の結婚式場だった。なのでエレクトロニカや最近のダンスミュージックは避け、アコースティック要素を多めにした。日本語の歌は、披露宴感が高まってしまうため除外。あと歌があるものは一応歌詞をチェックしている。
開始前
人が徐々に入り初めてくるときのBGM。バロック〜近代のクラシックでまとめた。本当だったらバレエ音楽とかワルツとか多めにしたかったのだが残念ながらあまり音源をもっておらず。基本的には時代に沿った順番。ストラヴィンスキーは無視。前半3曲ぶんくらいは人がほぼいない状態で、眠れる森の美女のワルツが山場だ。ちょうど開始直前に流せたので満足。
演奏のこだわりは特に無いので記載しない。
- テレマン ヴィオラ協奏曲 第2楽章 アレグロ
- バッハ ブランデンブルク協奏曲 第1番 第1楽章 アレグロ
- バッハ 管弦楽組曲第3番 第1曲 序曲
- ハイドン 交響曲第94番 第3楽章 メヌエット
- ベートーヴェン 交響曲第2番 第2楽章 アレグレット
- ストラヴィンスキー 組曲「プルチネッラ」第1曲 シンフォニア
- ブラームス 交響曲第2番 第3楽章 アレグレット
- ドヴォルザーク スラブ舞曲 第3曲
- チャイコフスキー 組曲「眠れる森の美女」 第5曲 ワルツ
- チャイコフスキー 交響曲第5番 第3楽章 ワルツ
第1部
オープニングムービーがあり、乾杯があった後。派手に初めてあとはジャズにつなげた。
Another Day of Sun
- 映画「ラ・ラ・ランド」のメインテーマ。演奏も歌も豪華だしめっちゃいい曲ですね。映画は見ていない。バッドエンドであることは知っている。
Overture
- 映画「セッション」より。「ラ・ラ・ランド」の曲と同じく Justin Hurwitz 作曲。クールながらアップテンポなビッグバンド曲。ドラムは意外と理性的である。映画は見ていない。明るい話じゃないのは知っている。
Pieces Of Dreams / Buddy Rich
- 2曲目は Buddy Rich につなげることが目的だったという面もある。本当なら Roar of ’74 から選びたかったのだが、ちょっとやりすぎ感があったのでこのへんにした。
Straight Life / Art Pepper
- ジャズサックス奏者だと Art Pepper が一番好きだ。トリオなのでだいぶ編成が小さくなってしまったがこのテンションの高さでなんとかつながってるはず?
Cherokee / Clifford Brown
- 同じくテンションの高いトリオ。
N.Y. Time / Lee Ritenour
- いま並べてみると、さすがにどうかという感じだな。リトナーを流したかっただけだ。
Limsy / The New Mastersounds
- ちょっと明るくしたかったので Jazz Funk にした。このあたりの流れ、選曲中もかなり悩んだけどやっぱり苦しい。
Forgiveness / The New Mastersounds
- 余白を埋める用。当日はかかってなかったかもしれない。
第2部
出し物でひとしきり盛り上がった後。ポップな洋ロック中心。
Sports & Wine / Ben Folds Five
- ピアノ入りでジャズ感を若干引きずりながら盛り上がりを維持。裏拍のノリが全編通して最高だけど、特に間奏が良い。
(If You're Wondering If I Want You To) I Want You To / Weezer
- 似たようなリズムの刻み方でギターを厚めにする。
The Calling / Yes
- なんでだよ。いや、ちょっと言い訳させてもらうとあまりポップなロックを知らないので絞り出したのだ。あるいは、あわよくば、なんでだよと突っ込んでもらいたかった。
Rock & Roll / Eric Hutchinson
- ちょっと落ち着いてみる。 Eric Hutchinson は声が良い。好きだ。イマイチ売れきらないところも好きだ。
Our Song / Taylor Swift
- もうちょっと落ち着いたまま。 Taylor Swift は 1st が一番好きだ。1st を聴きながら田舎の電車に乗ると最高なのでみんなやってほしい。
Lifestyles Of The Rich & Famous / Good Charlotte
- アップテンポでオーソドックスなロック。歌詞はちょっとどうかと思ったけど、逆にアリと判断した。
Whatever / Oasis
- 続く第3部が少ししっとりした雰囲気になるので、ちょっと下地をつくっておく。
Every Breath You Take / The Police
- これも余白を埋める用。
第3部
ちょっと感動的なムービーを挟んで、最後のパート。70〜80年代洋楽がメイン。
Don't You Worry 'Bout A Thing / Incognito
- なんでこの曲にしたか思い出せない、、
Work To Do / Isley Brothers
- 社畜ソング。
Sing A Song / Earth, Wind & Fire
- この曲の万能感は尋常じゃない。嫌味な感じが全くしない。 Sing a song って笑えるくらいシンプルな歌詞も良い。BGM が必要な場面ではどんな場所でも流れててほしい。
店を、探そう / The Screen Tones
Stay Gold / Stevie Wonder
- ちょっと落ち着かせる。落ち着きすぎだな。
Covina / Shakatak
- このへんも念のために用意したもの。
終了後
当日の記憶では BGM がほぼ聞こえなかった気がするが、静かなクラシックで蛍の光(正式には「別れのワルツ」だが)感を出したかった。なんとなくコンチェルトの緩徐楽章で揃えた。
Elgar, Cello Concerto 3. Adagio / Jacqueline du Pré, Sir John Barbirolli, London Symphony Orchestra
- 泣かせる演奏なんだこれが。
Gliere, Horn Concerto 2. Andante / Marie Luise Neunecker, Werner Andreas Albert, Bamberger Symphony Orchestra
Rachmaninov; Piano Concerto No.2 2. / Vladimir Ashkenazy; Bernard Haitink; Royal Concertgebouw Orchestra
- ロイヤルコンセルトヘボウは私が最も好きな音のオケだ。アシュケナージのピアノも当然素晴らしいが、冒頭のクラのヴィブラート利かせた歌心あふれるソロも痺れる。
Brahms; Concerto for Violin, Cello & Orchestra / Gidon Kremer; Clemens Hagen; Nikolaus Harnoncourt; Royal Concertgebouw Orchestra
Brahms; Piano Concerto No.1 2. Adagio / Maurizio Pollini; Karl Böhm; Vienna Philharmonic Orchestra
Dvorak; Cello Concerto 2. Adagio / Pierre Fournier; George Szell; Berliner Phillharmoniker
- フルニエの落ち着いたチェロ、セルの精緻な構成が見事に噛み合った名演。
いま修論を振り返る
この記事は Sansan Advent Calendar の9日目です。
約5年前、修士時代にやってた機械学習の研究の話をします。この分野で5年前といったら化石のような内容かもしれませんが、いま思い返してもなかなか面白いテーマでした。ちなみに普段の私の業務では機械学習は扱ってません。
画像データは当時のものを使いまわしています。ダサいのは知ってます。
(もっとゆるい記事を書くつもりだったのですが、これまでマジメな内容しかないので方針をかえました)
前提
機械学習を分類×回帰、教師あり×教師なしの四象限でみたとき、分類かつ教師あり、を対象にしています。学習機械は Support Vector Machines (SVM) を想定します。
これらの用語の説明はここでは行いません。
能動学習 (active learning)
いまも能動学習という分野があるのかわかりませんが (世間では教育系の用語として定着している感はありますが) 、扱う問題は「教師あり学習の学習データをどうやって集めるか?」というものです。どういうことかというと、教師あり学習の学習データはラベルが付いている必要があるわけですが、ラベルが付いていないデータが大量にあったときに、全部のデータのラベルを付けるとコストがかかるので避けたい。つまり、ラベルをつけるデータの数が少なく、かつ、予測性能を高めたい。
流れとしては以下を想定します (結局最初にラベル付けるの?という疑問がありそうですが、ここで説明するとゴチャゴチャするのでとりあえずそういうもんだと思ってください)
- ラベル付きデータを用意する
- 学習する
- ラベルなしデータからラベルを付けるデータを選択する
- データに人間がラベルを付ける
- に戻る
似た問題に対処する手法に半教師あり学習 (semi-supervised learning) があります。こちらは、ラベルが付いているデータと付いていないデータの両方が手元にあったとき、両方を使って学習しようというものです。能動学習は、新たにラベルを付けるとしたらどのデータにつけるか、という問題を扱います。半教師あり学習と能動学習と排反な関係ではありません。つまり、半教師あり学習に能動学習を組み込むこともできるわけです。今回は半教師あり学習についてはここまで触れるだけに留めておきます。
既存研究
Tong and Koller (2001) の Margin 法では、現在の学習で得られた情報からみてラベルが最も不確実なデータを選択します。SVM でいうと不確実性とは識別面からの距離です。
ギリギリ境目のデータを学習させようということですね。たしかに直感的です。が、実は落とし穴があります。そして、それら落とし穴に対応した手法も存在します。
- 局所的な選択になりがち
- 初回の学習データが全体からまんべんなくされたものであるとは限りません。いちど識別面が決まってしまったら、そこから離れたデータは二度と選択されなくなってしまいます。
- Baram ら (2004) や Osugi ら (2005) の手法では、データ集合全体から大局的にデータを取得しようとします。
- 複数のデータを選択する際、選択したデータが似ていると効率が悪い
- 外れ値が防げない
- 不確実だと外れ値が多い、と一概にいえるわけではないのですが、除外することが考慮されていません。
- Settles と Craven (2008) の手法は、データが高密度な領域から選択しようとします。
既存研究はいろいろあるが
上記色々な手法があるわけですが、どの戦略を重視すべきかがわかりません。ユーザーパラメーターで重み付け、という提案もあるにはあったわけですが、パラメーターチューニングのためには正解データを用意しなければならない (= 人間のラベル付けが必要) なので本末転倒です。
で、どうするか。
Small Pool 法
ちょっとだけ話が逸れます。
Ertekin らによる Small Pool 法は Margin 法の拡張です。ラベルなしデータのなかから無作為にデータを抽出し、そのなかから最も不確実なデータを選択する、というものです。
なんじゃそりゃという感じですが、意外と理に叶っています。無作為抽出ということは分布にしたがって高密度な領域のデータが選択されやすく、外れ値が混入する確率が低くなります。また、全データに対して不確実性を求める必要がないので、計算時間も少なく済みます。
ちなみにデータ抽出件数ですが、「不確実性の高い上位 5% を 95% の確率で選択するためには、全体のデータ数によらず 59 件取得すれば十分である」ということが証明されています。不思議!!(でもそんなに難しくないので別の記事で紹介しようと思っています)
で、この Small Pool 法を拡張しようと考えました。つまり、無作為に抽出していたデータを、ある程度尺度を設けて抽出しようということを考えました。
提案手法 (名前は無い)
以下のような流れです。2. - 4. が、 Small Pool 法にはなかったプロセスです。
- ラベルなしデータから無作為にデータを取得する。
- データに対して多様性、探索性の評価値を計算する。
- で求めた評価値をそれぞれに対して乱数と比較、いずれもそれらの乱数より大きければ、ラベル付け候補データに含める。そうでなければ破棄して 1. に戻る。
- までを、データ個数が目的の個数になるまで繰り返す。
ラベル付け候補データの中から最も不確実性の高いデータをラベル付け対象データとする。
で乱数を用いているのは、データ全体に対して評価値を計算するのは現実的でないのと、無作為性を残したかったからです (平たくいうと楽したかった) 。
(評価値の定義はまたややこしくなるので載せません、もし知りたいという奇特な方がいらっしゃれば教えてください)
比較
で、結果どうだったかというと、まあまあ高い予測性能になりました。以下、F1値の ALC です。縦軸はテストに用いたデータセット、横軸は手法です。Proposed1 が上記の提案手法です。
(テストデータはもともと全てラベルが付いてあるものですが、付いていないものと付いているもので分け、はじめに述べた能動学習の流れにおける「データに人間がラベルを付ける」のときにもともとのラベルを使用する、ということにしました)
ちなみに計算時間も短いです。こちらは MNIST-8 というデータセットに対して行った結果で、縦軸は対数軸です。訓練事例数というのはラベル付きデータ数です。上の表で AD という手法が Proposed1 に次いで高い値を出していますが、かなりの計算時間がかかっていることがわかります。
というわけで
だいぶ端折ましたが、修論を振り返りました。こんなもんで許してください。
Elasticsearch でつまづいた話 (4)
前回に引き続きページング取得の話。
Aggregations でページング
Terms Aggregations したとき、キーが多すぎる場合に分割して取得したい。そんなときは Partition に区切って取得することになる。
{ "size": 0, "aggs": { "aggregation_name": { "terms": { "field": "hoge", "include": { "partition": 0, "num_partitions": 10 }, "size" : 1000, } } } }
この例では 10 分割にしている。 partition
に 1〜9 を指定すると余りを取得することになる。注意したいのは、この例では 1000 件 × 10 partition で最後まで取得できる、と想定しているということだ。
推奨される流れとしては以下のとおり。
Cardinality Aggregation でキーの数を測る
キーの数に応じてチャンクの数 (上述の例でいう
10
) を決める各チャンクのサイズ (上述の例でいう
1000
) を決めるクエリする
更に述べておくと、各 Partition で取得される件数は、 Cardinality / num_partition
に必ずしも一致しない。上述の例でいうと、毎回の取得件数は 1000 件より少なくなることがある (ふつうはその方が多い) 。集計結果が Partition をまたぐことがあるためだと思う。なので、 size の値は Cardinality / num_partition
にすると取りこぼしが発生するので、それよりも大きい値 (2倍であれば十分、のはず...?) にしておくべきだ。
Elasticsearch でつまづいた話 (3)
今回のテーマはページング取得。
Query したときの件数
RDB の発想だと SQL select * from table
したら全件取得されるのが当然だが Elasticsearch だと何も指定しなければ 10 件までしか取得されない。
size を指定するとこれを大きくできる。
{ "size" : 100, "query" : { ... } }
だが、この size にも上限がある。デフォルトだと 10,000 件だ ( _settings の index.max_result_window
で定義されている) 。
作法としては Scroll API というのを使う。これは、ある時点でのスナップショットを保存して、取得しきれなかった分を辿っていくというものだ。
( From/Size でやろうとすると追加/削除があった場合に過不足が発生するので良くない)
クエリ文字列として scroll=hoge
を渡す。 hoge
は 1m
など、スナップショットを保持する期間を指定する。
curl -XGET '[host]/_search?scroll=1m' -d ' { "size" : 100, "query" : { ... } }'
レスポンスは以下のようになる。
{ "_scroll_id" : "hogehoge", "hits" : { ... } }
_scroll_id
があるということは、取得しきれなかった分があることを意味する。続きを取得するには、以下のリクエストを送る。このときクエリを指定する必要はない。
curl -XGET '[host]/_search?scroll' -d ' { "scroll_id" : "hogehoge" }'
このレスポンスにも続きがあれば新たな _scroll_id
が返ってくるので、それを使って再び叩くことになる。
取得が完了したら、 DELETE
でスナップショットを削除すると行儀がいい。
Aggregation 時もページングが必要になる場合があるが、その際はまたちょっと違った API を使うことになる。その話はまた今度。
ASP.NET のセッションと同時実行
ASP.NET で複数リクエストからセッションを扱おうとすると困ったことになるよという話。
SPA とかだと、画面からいろんなリクエストを非同期で飛ばして、パーツごとに表示することがある。 そんなとき、たとえば認証情報をセッションから取得して、その情報で DB を見に行き、取得内容を返す、といったことが考えられる。
[HttpGet] public ActionResult Company(string id) { var loginInfo = Session[id]; var company = GetCompany(loginInfo.CompanyId); return Json(company, JsonRequestBehavior.AllowGet) } [HttpGet] public ActionResult User(string id) { var loginInfo = Session[id]; var user = GetUser(loginInfo.UserId); return Json(user, JsonRequestBehavior.AllowGet) }
こんなとき Ajax で Company
と User
を呼ぶと、後に呼ばれたリクエストは先に呼ばれたリクエストの response が完了するまで待たされてしまう。
これは .NET が Session をロックしているためだ。確かに同時実行中に書き換わってしまったら困るのだが、パフォーマンス的にはそれでは困る。
回避するためには、セッションに対して書き込みは行わないよ!ということを属性で明示する。
[SessionState(SessionStateBehavior.ReadOnly)] HomeController : Controller { ... }
残念なことに SessionState
属性は Action ではなく Controller 単位にしか付与できない。
正解率の高い予測が必ずしも良い予測ではない
タイトルのとおりなんですが、何かしらの予測に対してその良さを語るために「正解率90%」とか「精度90%」とかよく表現されますね。
で、今回は「正解率が高ければ良いというわけじゃない」という話です。
正解率 (accuracy)
正解率の定義は、当然、正解数を問題数で割った数値です。
予測を評価するための数値として、きわめて真っ当に見えます。しかし、必ずしもそうではないのです。
コンピューターウィルスを予測する
「PC 内のファイルがコンピューターウィルスかそうでないか」という問題を考えてみましょう。
通常、 PC 内のファイルはほとんどがウィルスではありません。仮に、 0.01 % のファイルがウィルスだったとしましょう(かなり多いですが)。 そうすると、「全てのファイルはウィルスではない」という予測ですら、正解率は 99.99% になってしまいます。
数値は高いですが、これでは何の意味もありません。
ではこのとき、どういった数値をみる必要があるのでしょうか?
適合率 (recall)
コンピューターウィルスを予測するときは、ウィルスでないファイルをウィルスであるという誤検知が多少あったとしても、ウィルスであるファイルを確実にウィルスである、と予測したいでしょう。
正解率との違いがわかるでしょうか?表現を変えると以下のようになります。
このような尺度を適合率 (recall) と呼びます。
精度 (precision)
話は変わります。冒頭で、「正解率90%」と並べて「精度90%」と表現しました。実は、精度 (precision) という尺度が正解率と別に定義されています。
さきほどのコンピューターウィルスの例を使いまわすと、以下のようになります。
適合率と精度
さて、コンピューターウィルスを予測する際は適合率を高くしたいという話がありました。しかし、ここでも罠があります。やはり、「全てのファイルがウィルスである」という予測をすると、適合率が100%になってしまいます。確かに全てのコンピューターウィルスを検知できたのですが、これでは役に立ちません。
そこで、適合率と精度を組み合わせるという手段があります。
こんな表を用意します。ここで T : True (実際に正解), F : False (実際に不正解), P : Positive (正解と予測), N : Negative (不正解と予測) を意味します。
実際は正解 | 実際は不正解 | |
---|---|---|
正解と予測 | TP | FP |
不正解 | TN | FN |
ぱっと見、なんだかややこしい気がしますが、さきほどのコンピューターウィルスの例と同じです。
これのちょうどいいバランスをとりたいわけです。例えばこんな感じだとどうでしょう。
これは調和平均と呼ばれる平均の一種です。普通の平均だとダメなの?という疑問が湧くと思いますが、今回は割愛します。
この数値自体は F 値 (F-measure) と呼ばれます。
まとめ
というわけで、「正解率が高ければ良いというわけじゃない」という話でした。
しかし、「F値こそが正義!」というわけでもありません。単純に適合率と精度の真ん中らへんをとっているというだけですから、実際はどのあたりのバランスが「現実的に嬉しいのか」を考える必要があります。コンピューターウィルスの例では、おそらく、精度よりも適合率の方を重視した尺度を用意すべきように思います。
また、他にも ROC curve だったり AUC だったり、今回みた以外にもいろいろな尺度があります。奥が深いですね。
専門家ではないのでこのへんで。