2017-12-09

いま修論を振り返る

この記事は Sansan Advent Calendar の9日目です。

約5年前、修士時代にやってた機械学習の研究の話をします。この分野で5年前といったら化石のような内容かもしれませんが、いま思い返してもなかなか面白いテーマでした。ちなみに普段の私の業務では機械学習は扱ってません。

画像データは当時のものを使いまわしています。ダサいのは知ってます。

(もっとゆるい記事を書くつもりだったのですが、これまでマジメな内容しかないので方針をかえました)

前提

機械学習を分類×回帰、教師あり×教師なしの四象限でみたとき、分類かつ教師あり、を対象にしています。学習機械は Support Vector Machines (SVM) を想定します。

これらの用語の説明はここでは行いません。

能動学習 (active learning)

いまも能動学習という分野があるのかわかりませんが (世間では教育系の用語として定着している感はありますが) 、扱う問題は「教師あり学習の学習データをどうやって集めるか？」というものです。どういうことかというと、教師あり学習の学習データはラベルが付いている必要があるわけですが、ラベルが付いていないデータが大量にあったときに、全部のデータのラベルを付けるとコストがかかるので避けたい。つまり、ラベルをつけるデータの数が少なく、かつ、予測性能を高めたい。

流れとしては以下を想定します (結局最初にラベル付けるの？という疑問がありそうですが、ここで説明するとゴチャゴチャするのでとりあえずそういうもんだと思ってください)

ラベル付きデータを用意する
学習する
ラベルなしデータからラベルを付けるデータを選択する
データに人間がラベルを付ける
1. に戻る

似た問題に対処する手法に半教師あり学習 (semi-supervised learning) があります。こちらは、ラベルが付いているデータと付いていないデータの両方が手元にあったとき、両方を使って学習しようというものです。能動学習は、新たにラベルを付けるとしたらどのデータにつけるか、という問題を扱います。半教師あり学習と能動学習と排反な関係ではありません。つまり、半教師あり学習に能動学習を組み込むこともできるわけです。今回は半教師あり学習についてはここまで触れるだけに留めておきます。

既存研究

Tong and Koller (2001) の Margin 法では、現在の学習で得られた情報からみてラベルが最も不確実なデータを選択します。SVM でいうと不確実性とは識別面からの距離です。

f:id:tkrtkhsh:20171209131709p:plain

ギリギリ境目のデータを学習させようということですね。たしかに直感的です。が、実は落とし穴があります。そして、それら落とし穴に対応した手法も存在します。

局所的な選択になりがち
- 初回の学習データが全体からまんべんなくされたものであるとは限りません。いちど識別面が決まってしまったら、そこから離れたデータは二度と選択されなくなってしまいます。
- Baram ら (2004) や Osugi ら (2005) の手法では、データ集合全体から大局的にデータを取得しようとします。
複数のデータを選択する際、選択したデータが似ていると効率が悪い
- どうせ学習するのであれば、違った種類のデータを学習させたいものです。上記の手法ではその観点を考慮していません。
- Brinker (2003) の手法は、cosine similarity を使ってデータ同士の多様性を考慮します。
外れ値が防げない
- 不確実だと外れ値が多い、と一概にいえるわけではないのですが、除外することが考慮されていません。
- Settles と Craven (2008) の手法は、データが高密度な領域から選択しようとします。

既存研究はいろいろあるが

上記色々な手法があるわけですが、どの戦略を重視すべきかがわかりません。ユーザーパラメーターで重み付け、という提案もあるにはあったわけですが、パラメーターチューニングのためには正解データを用意しなければならない (= 人間のラベル付けが必要) なので本末転倒です。

で、どうするか。

Small Pool 法

ちょっとだけ話が逸れます。

Ertekin らによる Small Pool 法は Margin 法の拡張です。ラベルなしデータのなかから無作為にデータを抽出し、そのなかから最も不確実なデータを選択する、というものです。

なんじゃそりゃという感じですが、意外と理に叶っています。無作為抽出ということは分布にしたがって高密度な領域のデータが選択されやすく、外れ値が混入する確率が低くなります。また、全データに対して不確実性を求める必要がないので、計算時間も少なく済みます。

ちなみにデータ抽出件数ですが、「不確実性の高い上位 5% を 95% の確率で選択するためには、全体のデータ数によらず 59 件取得すれば十分である」ということが証明されています。不思議！！(でもそんなに難しくないので別の記事で紹介しようと思っています)

で、この Small Pool 法を拡張しようと考えました。つまり、無作為に抽出していたデータを、ある程度尺度を設けて抽出しようということを考えました。

提案手法 (名前は無い)

以下のような流れです。2. - 4. が、 Small Pool 法にはなかったプロセスです。

ラベルなしデータから無作為にデータを取得する。
データに対して多様性、探索性の評価値を計算する。
1. で求めた評価値をそれぞれに対して乱数と比較、いずれもそれらの乱数より大きければ、ラベル付け候補データに含める。そうでなければ破棄して 1. に戻る。
1. までを、データ個数が目的の個数になるまで繰り返す。
ラベル付け候補データの中から最も不確実性の高いデータをラベル付け対象データとする。
で乱数を用いているのは、データ全体に対して評価値を計算するのは現実的でないのと、無作為性を残したかったからです (平たくいうと楽したかった) 。

(評価値の定義はまたややこしくなるので載せません、もし知りたいという奇特な方がいらっしゃれば教えてください)

比較

で、結果どうだったかというと、まあまあ高い予測性能になりました。以下、F1値の ALC です。縦軸はテストに用いたデータセット、横軸は手法です。Proposed1 が上記の提案手法です。

(テストデータはもともと全てラベルが付いてあるものですが、付いていないものと付いているもので分け、はじめに述べた能動学習の流れにおける「データに人間がラベルを付ける」のときにもともとのラベルを使用する、ということにしました)

f:id:tkrtkhsh:20171209140052p:plain

ちなみに計算時間も短いです。こちらは MNIST-8 というデータセットに対して行った結果で、縦軸は対数軸です。訓練事例数というのはラベル付きデータ数です。上の表で AD という手法が Proposed1 に次いで高い値を出していますが、かなりの計算時間がかかっていることがわかります。

f:id:tkrtkhsh:20171209140320p:plain

というわけで

だいぶ端折ましたが、修論を振り返りました。こんなもんで許してください。

2017-12-07

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倍であれば十分、のはず...？) にしておくべきだ。

2017-12-06

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 を使うことになる。その話はまた今度。

2017-12-05

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 単位にしか付与できない。

2017-12-05

正解率の高い予測が必ずしも良い予測ではない

タイトルのとおりなんですが、何かしらの予測に対してその良さを語るために「正解率90%」とか「精度90%」とかよく表現されますね。

で、今回は「正解率が高ければ良いというわけじゃない」という話です。

正解率 (accuracy)

正解率の定義は、当然、正解数を問題数で割った数値です。

$\displaystyle \frac{正解数}{問題数}$

予測を評価するための数値として、きわめて真っ当に見えます。しかし、必ずしもそうではないのです。

コンピューターウィルスを予測する

「PC 内のファイルがコンピューターウィルスかそうでないか」という問題を考えてみましょう。

通常、 PC 内のファイルはほとんどがウィルスではありません。仮に、 0.01 % のファイルがウィルスだったとしましょう（かなり多いですが）。そうすると、「全てのファイルはウィルスではない」という予測ですら、正解率は 99.99% になってしまいます。

数値は高いですが、これでは何の意味もありません。

ではこのとき、どういった数値をみる必要があるのでしょうか？

適合率 (recall)

コンピューターウィルスを予測するときは、ウィルスでないファイルをウィルスであるという誤検知が多少あったとしても、ウィルスであるファイルを確実にウィルスである、と予測したいでしょう。

$\displaystyle \frac{正しくウィルスであると予測できた数}{実際のウィルスファイル数}$

正解率との違いがわかるでしょうか？表現を変えると以下のようになります。

$\displaystyle \frac{実際にウィルスであり、ウィルスだと予測できた数}{実際にウィルスであり、ウィルスだと予測できた数 + 実際にウィルスだが、ウィルスだと予測できなかった数}$

このような尺度を適合率 (recall) と呼びます。

精度 (precision)

話は変わります。冒頭で、「正解率90%」と並べて「精度90%」と表現しました。実は、精度 (precision) という尺度が正解率と別に定義されています。

$\displaystyle \frac{実際にAである数}{Aであると予測した数}$

さきほどのコンピューターウィルスの例を使いまわすと、以下のようになります。

$\displaystyle \frac{正しくウィルスであると予測できた数}{ウィルスだと予測し、実際にウィルスだった数 + ウィルスだと予測し、ウィルスではなかった数}$

適合率と精度

さて、コンピューターウィルスを予測する際は適合率を高くしたいという話がありました。しかし、ここでも罠があります。やはり、「全てのファイルがウィルスである」という予測をすると、適合率が100%になってしまいます。確かに全てのコンピューターウィルスを検知できたのですが、これでは役に立ちません。

そこで、適合率と精度を組み合わせるという手段があります。

こんな表を用意します。ここで T : True (実際に正解), F : False (実際に不正解), P : Positive (正解と予測), N : Negative (不正解と予測) を意味します。

	実際は正解	実際は不正解
正解と予測	TP	FP
不正解	TN	FN

ぱっと見、なんだかややこしい気がしますが、さきほどのコンピューターウィルスの例と同じです。

$適合率 = \displaystyle \frac{TP}{TP + TN}$

$\displaystyle \frac{TP}{TP + FP}$

これのちょうどいいバランスをとりたいわけです。例えばこんな感じだとどうでしょう。

$精度 = \displaystyle \frac{2 \times 適合率 \times 精度}{適合率 + 精度}$

これは調和平均と呼ばれる平均の一種です。普通の平均だとダメなの？という疑問が湧くと思いますが、今回は割愛します。

この数値自体は F 値 (F-measure) と呼ばれます。

まとめ

というわけで、「正解率が高ければ良いというわけじゃない」という話でした。

しかし、「F値こそが正義！」というわけでもありません。単純に適合率と精度の真ん中らへんをとっているというだけですから、実際はどのあたりのバランスが「現実的に嬉しいのか」を考える必要があります。コンピューターウィルスの例では、おそらく、精度よりも適合率の方を重視した尺度を用意すべきように思います。

また、他にも ROC curve だったり AUC だったり、今回みた以外にもいろいろな尺度があります。奥が深いですね。

専門家ではないのでこのへんで。

2017-12-03

いろいろな交響曲第1番

作曲家にとって交響曲第1番はロックバンドにおける 1st アルバムと同じ。 Oasis の Definitely Maybe だし、 Weezer の blue album だ。今回は、偉大なる作曲家たちの交響曲第1番を振り返ってみる。セレクションは適当です。

L. v. ベートーヴェン

www.youtube.com

1st アルバムとか言っておきながら、ベートーヴェンが交響曲第1番を発表したのは彼が30歳のとき。満を持しての交響曲である。

冒頭、ハ長調というど真ん中の調のくせに、属七のヘ長調から始まり、4小節目でようやく五度のト長調になる。異常だ。そして10小節目でハ長調とみせかけてのト短調。序奏からしてもう名曲だ。スピード感あふれる第1主題も最高。展開部の変奏も楽聖としか言いようがなさすぎる。第3楽章のスケルツォ（メヌエットということになっているが、実質スケルツォ）、私は古典派のスケルツォ楽章は退屈でしょうがないのだが、この裏拍感が支配するダイナミックな音楽、現代のロックバンドに見習ってほしいほどである。

F. J. ハイドン

www.youtube.com

交響曲の父ハイドン。彼は生涯で 104 番 (番号なしを含めると 108 曲らしい) までの交響曲を生み出した。一聴してわかるとおり、完成度が高すぎる。どうやら彼が本当に最初に作曲した交響曲ではないらしい。 104 番まで作っておきながら、捨て曲が無いというのがありえない。

P. I. チャイコフスキー

www.youtube.com

最も人気のあるシンフォニストのひとり、チャイコフスキー。彼の交響曲第1番は標題つきであることもあって演奏される機会もそこそこあるが、正直、地味だし演奏効果も低いと思う。だが、たとえばフィナーレ弱奏部の煽り方など、所々に「こいつ、もしかしたら凄い作曲家になるのでは？？」という期待感がある。 Happy Mondays の 1st のような、 Number Girl の SCHOOL GIRL BYE BYE のような、改めて聴くと大事にしたくなるような感じだ。

A. ドヴォルザーク

www.youtube.com

神が作ったかのような交響曲第9番「新世界より」は、史上最も完成度の高い交響曲であると認める人も多い。そんなドヴォルザークの交響曲第1番、私は今回初めて聴いた。まぁ...ちょっと...つかみどころが無いかな... 内声の充実度は当時からあったみたいね...

G. マーラー

www.youtube.com

マーラーは近代作曲家のなかでも最も人気のある人物といっていいだろう。冒頭の宇宙的和音（ユニゾンだけど）、第2楽章の耽美なワルツ、既に彼の世界観が確立されている。ムカつく。フィナーレの大勝利感。何がベルアップだよ。最高だ。

J. シベリウス

www.youtube.com

私が最も好きな作曲家、シベリウス。世間の評価でいうと、後期の第4番以降の作品は洗練されていて完成度が高いといわれる。最もよく演奏される交響曲は第2番である。（クレルヴォ交響曲という番号なしの大交響曲があるが、今回は無視する）

そんな彼の第1番は、初期衝動そのもの。これが俺の音楽だ。ロマンティシズムだ。たとえば交響曲第6番と比べると、全く別人の音楽である。「シベ1は後期の作品と比べると音楽性が低いよね笑」なんて言う人もいるが、この美しい第4楽章第2主題の前では、そんな戯言に価値は無い。

ブラームスどうしたよ！とか、交響曲といえばセーゲルスタムだろ！（そんな人いるか？）とかの声もあると思うが、今回はこのあたりで。

2017-12-02

Elasticsearch でつまづいた話 (2)

今日のテーマは複数の Nested Field があるときの Aggregations 。

Nested Field とは

日本語での説明はこのあたりに譲るが、簡単に言うと親子関係が維持された Array である。データの見た目は Array と同じだ。

  "user" : [ 
    {
      "first" : "John",
      "last" :  "Smith"
    },
    {
      "first" : "Alice",
      "last" :  "White"
    }
  ]

クエリはこんな感じになる。

{
   "query" : {
      "nested" : {
         "path" : "user",
         "query" : {
            "match" : {
               "user.first" : "John"
            }
         }
      }
   }
}

Array だったら↓で済むので少し複雑になっている。

{
   "query" : {
      "match" : {
         "user.first" : "John"
      }
   }
}

Aggregation ならこうなる。

{
   "aggs" : {
      "nested_by_resellers" : {
         "nested" : {
            "path" : "resellers"
         },
         "aggs" : {
            "aggs_by_resellers_id" : {
               "terms" : {
                  "field" : "reseller.id"
               }
            }
         }
      }
   }
}

Nested Field が複数ある場合もある。

{
  "mappings": {
    "product" : {
        "properties" : {
            "resellers" : { 
                "type" : "nested",
                "properties" : {
                    "id" : { "type" : "keyword" },
                    "name" : { "type" : "text" },
                    "price" : { "type" : "double" }
                }
            }, 
            "sources" : {
               "type" : "nested",
               "properties" : {
                  "id" : { "type" : "keyword" },
                  "name" : { "type" : "text" }
               }
            }
        }
    }
  }
}

このとき resellers の id で集約し、更に sources の id でも集約したい場合どうするか。これが今回のつまづいた話だ。たとえば↓のように書きたくなるが、これではうまくいかない。

{
   "aggs" : {
      "nested_by_resellers" : {
         "nested" : {
            "path" : "resellers"
         },
         "aggs" : {
            "aggs_by_resellers_id" : {
               "terms" : {
                  "field" : "reseller.id"
               },
               "aggs" : {
                  "nested_by_sources" : {
                     "nested" : {
                        "path" : "sources"
                     },
                     "aggs" : {
                        "aggs_by_sources_id" : {
                           "terms" : {
                              "field" : "sources.id"
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }
}

なぜか？ reseller の下に sources がいないからだ。そりゃそうだ。

じゃどうするか。 reverse nested というものを使う。これによって nested を抜け出すことができる。

{
   "aggs" : {
      "nested_by_resellers" : {
         "nested" : {
            "path" : "resellers"
         },
         "aggs" : {
            "aggs_by_resellers_id" : {
               "terms" : {
                  "field" : "reseller.id"
               },
               "aggs" : {
                  "reverse" : {
                     "reverse_nested" : {},
                     "aggs" : {
                        "nested_by_sources" : {
                           "nested" : {
                              "path" : "sources"
                           },
                           "aggs" : {
                              "aggs_by_sources_id" : {
                                 "terms" : {
                                    "field" : "sources.id"
                                 }
                              }
                           }
                        }
                     }
                  }
               }
            }
         }
      }
   }
}

reverse_nested を挟むことによって、 resellers の下にいた状態から抜け出して、更に sources の下に入ることができた。めでたしめでたし。

... とはいえ、複雑な json だよなぁ。

参考 :

Reverse nested Aggregation | Elasticsearch Reference [6.0] | Elastic