Nelder Mead Method を python で実装
最近会社で Kaggle 本 Kaggleで勝つデータ分析の技術 の本読みをやっています。昨日は第二章でしきい値の最適化の文脈で Nelder Mead Method を使った最適化が記載されていました。ちょっと気になったので実装してみたという話です。
Nelder Mead Method とは
最適化手法の一種です。いくつかのデータ点(単体)での評価値をベースに更新していく方法で、勾配の情報などを使わないため目的関数さえ評価できれば実行できるお手軽さがメリットです。
アルゴリズムの概要は英語版 wikipedia が詳しいです。(自分が見た限りでは日本語版では一部の更新で符号がまちがっているように見受けられたので英語のほうがよさ気)
前提として $N$ 次元のベクトルの最適化をしたいとすると
- 適当に選んだ $N$ 次元ベクトル + 各次元に $+1$ した合計で $N+1$ の $N$ 次元ベクトルを計算
- 1で計算した各点での目的関数値を計算して、その順序を保存。
- 一番悪かった点以外の重心を計算
- 一番悪かった点と重心の対称な点(反射点)を計算
この反射点を使って場合分けを計算していきます。
- 反射点が二番目に悪い点より良い場合は採用として一番悪い点を置き換え
- 反射点が一番良い場合、もっとソッチの方に移動しても良いという発想で、最悪点から反対側に更に移動した点(拡大点)を計算。
拡大点が反射点より良い場合には拡大点を採用として一番悪い点を置き換えます。(拡大点が反射点より悪い時はすなおに反射点で妥協) - それ以外の時(2番めのものより悪い時)は重心と最悪点の内点(縮小点)を計算
- 縮小点が最悪よりは良い時は最悪点を縮小点で置き換え。
- 縮小点も悪い時は最良点以外の点を、最良点との内点に置き換え
python のコードにすると以下のような感じです。Notebook はこちら https://nyker510.gitlab.io/notebooks/posts/nelde-mead/ にあげています。
import numpy as np init_point = np.random.uniform(-.1, .1, 2) - np.array([1.5, 1.5]) alpha = 1. gamma = 2. rho = .5 sigma = .5 scaling_factor = 1. eval_points = np.vstack([init_point + np.eye(2) * scaling_factor, init_point]) best_points = [init_point] for i in range(100): # 目的関数で評価して並び替え objective_values_by_point = objective(eval_points[:, 0], eval_points[:, 1]) orders = np.argsort(objective_values_by_point) f_values = objective_values_by_point[orders] eval_points = eval_points[orders] # 最悪点以外で重心を計算 centroid = np.mean(eval_points[:-1], axis=0) p_worst = eval_points[-1] # 反射点 (最悪点から重心の対象な点) を計算 + そのときの目的関数を評価 p_reflect = centroid + alpha * (centroid - p_worst) f_ref = objective(*p_reflect) f_best = f_values[0] f_second_worse = f_values[-2] f_worst = f_values[-1] # 反射点がそこそこ良い場合 (second worse よりは良い) → 最悪点を反射点で置き換え if f_best <= f_ref < f_second_worse: eval_points[-1] = p_reflect # 反射点が一番良い場合 elif f_ref < f_best: # もうちょっと良い点がないか探りに行くイメージ (拡大点) # 最悪点が一番悪い → 反射点の方にもっと移動するイメージ (反射点 + centroid - p_worst [i.e. 最悪点からみた重心方向]) p_expand = centroid + gamma * (centroid - p_worst) f_expand = objective(*p_expand) # 拡大点が良かったら採用. だめだったら反射点で妥協 if f_expand < f_ref: eval_points[-1] = p_expand else: eval_points[-1] = p_reflect # 反射点が二番目に悪い点より良くない時 elif f_second_worse <= f_ref: # 重心と最悪点の間を計算 (大体すべての点のまんなかあたりに対応する) p_cont = centroid + rho * (p_worst - centroid) f_cont = objective(*p_cont) # 縮小点が最悪よりは良い時 # 重心方向への移動は良いと判断して最悪点を置き換え if f_cont < f_worst: eval_points[-1] = p_cont else: # そうでない時最良点めがけて縮小させる (最良点との内点に移動して三角形ちっちゃくするイメージ) shrink_points = eval_points[0] + sigma * (eval_points - eval_points[0]) eval_points[1:] = shrink_points[1:] best_points = np.vstack([best_points, eval_points[0]])
実験
はじめに自分で適当に作った関数でやります。たぶん (0, -.4) あたりが最適解なはず(あやしい)。
def objective(x, y): return (x - .1) ** 2 + (y - .3) ** 2 + np.sin((x + .5) * 2) * np.sin(y * 3) + sigmoid(x * 4)
これでやると以下のような感じ。わりとよさ気。
ついでに Rosenbrock function でもやってみましょう。
こちらは最適な座標は (1, 1) になるように設定しています(見えにくいですが黒い丸があるところ)。
実行すると以下のような感じ。たどり着いてるっぽいですね。
NOTE
これは Nelder Mead に限った話ではないですが、問題のスケールをちゃんと -1, 1 ぐらいに合わせておく必要があります。というのは一番初めに生成する点列の評価値に依存してその後の点列が決定するため、一番初めの点の性質が悪いと上手く更新が進まないためです。
例えば今回で言うと init_point に対して np.eye(1) を足すことで初期の点を生成していますが、これを np.eye(1) * .00001 などにすると上手く収束してくれません。
反対に大きすぎても更新幅が大きすぎて発散気味になります。
これと同様にそもそもの初期点をどう選ぶかもとても重要です。コード中では np.random.uniform(-.1, .1, 2) - np.array([1.5, 1.5]) としていますが、たとえばこの周りだけ凹んでいる関数だった場合そこから抜け出せずに局所解に陥って終わりになることもあります。ちょっとうまくいかないなーという時はスケールがあっているかを確認+初期点を変えてやってみるのも大切そうです。
Kaggleで勝つデータ分析の技術: 今までの機械学習本と全く違う最強の実務本
この度光栄なことに著者の @Maxwell さんから「Kaggleで勝つデータ分析の技術」 を献本いただきました。 私事ですがこのような形で献本頂いたのは初めての経験だったのでとてもうれしくまた恐縮している次第です。
光栄なことに @Maxwell_110 さんからKaggleで勝つデータ分析の技術を頂きました〜 目次の充実が話題になってましたがサラッと見ただけでも濃い内容満載で読むのワクワクです😆 https://t.co/VTKmsR5Z6s pic.twitter.com/yuRS72YyTs
— ニューヨーカーGOTO (@nyker_goto) October 2, 2019
「せっかく本を頂いたので書評をかこう!!」と思ってここ数日読み進めていたのですが、この本が自分がここ一年ぐらいで読んだ機械学習に関連する本の中でもずば抜けて内容が濃くまた情報量の多い本であったため「これは僕も頑張らねばならぬ…」とウンウン唸っているうちに今まで時間が経ってしまいました。
すでに全体像に関する書評に関しては u++さんの記事や ばんくしさんが書かれた素晴らしい記事ありますのでそちらを参考にしていただければと思います。
お二方とも超がつく高評価でこの本の完成度が伺えると思います。
お二人と同じようなことを書いても差別化ができない(?) ので以下では nyker_goto 的な視点 (実務でデータ分析をしていてシステムへの組み込みなども自分でやっている人) でこの本を見ていきたいと思います。
体系的に Kaggle の知がまとまっている最強のほん
「Kaggleで勝つデータ分析の技術」と銘打っている通り、Kaggle のノウハウがこれまでかというまでに詰まっています。
まず Kaggle への参加方法までを丁寧に説明するところから始まり、評価指標の話や、過去のソリューションの解説、特徴量の作り方や XGBoost などの Kaggle でおなじみのアルゴリズムの説明、はたまたチューニングノウハウまでもがまとめてあります。*1
上記内容は体系だった本があるわけではなく、Kaggle の DiscussionやNotebook、Kagglerのブログなどに散らばっている内容です。これらを一気に一つの本で読むことができるというのは個人的にとんでもないことだと思っています(自分が Kaggle 始める前に読みたかったです)。これだけでも本の値段にお釣りが来る価値があると思います。
これから Kaggle を始めたいと思っている人はこの本をベースに知らないことを調べながら学習していけば良いと思いますし、また Kaggle をやっている人もこの本を見て復習したり、抜けている知識や議論の分かれる問題に対して意見を考えるのも非常にためになると思います。
Validation の作り方の専門書
そして個人的にこの本の一番の勝ちは Validation の作り方のセクションにあると思っています。 なぜなら Validation をちゃんと作るというのは Kaggle だけでなく 実務で機械学習を使う上で一番大事なのにも関わらず、他の本ではほとんど触れられてこなかった と思っているからです。
Trust CV
Kaggle では Trust CV とよく言われます。Trust CV とは簡単に言うと、今の見えているランキングの値を信じるのではなく、自分の学習データで評価した自分のモデルの評価値を信じなさい、ということです。これはランキングばかりを追いかけているとランキングに過学習してしまい最終的な評価値が悪化してしまうことを避けるための格言です。
この Trust CV を最もしなくてはいけないのはいつなのか、というと実は実務で機械学習のモデルを作るときなのではないか、と僕は思っています。
ex). 時系列のデータの予測モデルを作るとき…
例えば時系列の予測を行うモデルを作りたいというとき CV の切り方がわかっていない人は単純に KFold で Fold ごとの validation score がモデルの評価値だと思い、学習を行うでしょう。(なんなら KFold している時点でまだまし、なのかもしれません。) そうして Production にいざデプロイすると全然スコアが出ない、なんていうことはざらにあるんだろうと思います。これは Production では常に未来の予測をしているのに対して単純な KFold だと未来の情報も使って予測ができるようになっていてモデルが予測する際の条件が揃っていないことが原因と考えられます。
上記のミスは一般的な? Kaggler なら当たり前にわかることなのですが、なんかちょっと前に京都大学の先生がこれをやっていたり、専門家でもやってしまいがちなミスです。 じゃあなぜそんなミスが専門家でもやってしまいがちなのか、というと一般的な機械学習のアルゴリズムの本にはそんなことは「一切」載っていないし重要視されていないからなんだろうと思います。
一般的な機械学習の本が全然触れないデータ分析のこと
それは僕が大好きなPRMLでもカステラ本でもみどりぼんでもそうです。 それらの本で対象にしているのはモデルの仕組みであって、実問題を解くためにTestデータとTrainデータをどのように用意すればいいかは範囲外だからです。そして厄介なことに scikit-learn とかで得られるデータってだいたい KFold で十分なんですよね… mnist しかりあやめしかり。
実データはそんな単純な問題ではないことが多いですし、大抵は時系列やユーザーごとに切り分けて考えることが必要です。 それって実際に問題を解く際には避けては通れない道なのですよね。(ここに機械学習の勉強と、実問題を解くことができるの一つの壁があると思っています。)
一方で Kaggle はシビアにそれがわかります。だって「それでは勝てない」のです。勝てないがゆえに勝てるためにちゃんとCVをして自分のモデルの能力をしっかりと計測するという文化が出来上がってきています。
そして、このしっかりモデルの力を測る力は、実務でモデルを適用しようとしている人が一番必要な力です。だってちゃんとモデルを測れなかったら Production で痛い目を見るからです。本番での性能なんて知ったこっちゃない、っていう人は別かもですが…
まとめ
以上ながなが書きましたが、この本は
- Kaggle をやりはじめる人にとって案内となる本であり
- 同時に Kaggle 経験者も知識の振り返りに使える本であり
- 実は Kaggle をしない実務で機械学習をしている人が一番必要としている本
だと思っています。要するに 機械学習する人はみんな必要 です。とにかく素晴らしいので、ぜひ皆さん手にとってご覧になってください。
最後にこのような素晴らしい本を書いてくださった著者のみなさまに感謝を述べてこの書評を終わりとさせてください。
ここまで読んでいただいてありがとうございました。
*1:僕もチューニングの気持ちを書いたエントリがありますが完全にリプレイスされました
elasticsearch で cosine類似度検索する
全文検索エンジンで cosine 類似度検索できるらしいというのを bert × elasticsearch の記事で見かけてとてもたのしそうだったので、自分でも環境作るところからやってみました。
やっているのは以下の内容です
- docker/docker-compose で elasticsearch x kibana x jupyter の立ち上げ
- jupyter の python から実際に特徴量ベクトルの登録 + 検索の実行
- kibana での可視化 (ちょっとだけ)
紹介するコードはすべて以下のリポジトリから参照できます。
Requirements
- docker
- docker-compose
Setup
docker-compose build docker-compose up -d
以上実行するとサーバーが3つ立ち上がります。docker-compose ps をやって以下のような感じになってれば成功です。
23:00:17 in start-elastic-search on master on 🐳 v18.06.1 took 24s
➜ docker-compose ps
Name Command State Ports
----------------------------------------------------------------------------------------------------------------------------
startelasticsearch_elasticsearch_1 /usr/local/bin/docker-entr ... Up 0.0.0.0:9200->9200/tcp, 0.0.0.0:9300->9300/tcp
startelasticsearch_jupyter_1 /usr/bin/tini -- jupyter n ... Up 0.0.0.0:8888->8888/tcp
startelasticsearch_kibana_1 /usr/local/bin/dumb-init - ... Up 0.0.0.0:5601->5601/tcp
elasticsearch
今回の主題である elasticsearch は localhost:9300 でつながります。これを直接 REST API で叩いても当然つかうことが出来ます。
定義ファイルは ./elasticsearch ディレクトリに入っています。
詳しくは elasticsearch 公式 docker document を参考にして下さい
https://www.elastic.co/guide/en/elasticsearch/reference/current/docker.html
Production Usage の時の注意点 https://www.elastic.co/guide/en/elasticsearch/reference/current/docker.html#_notes_for_production_use_and_defaults とかもあります。
Kibana
Kibana は elasticsearch 用のクライアントアプリケーションです。 localhost:5601 で kibana container とつながっています。開いて適当なサンプルデータを突っ込むとわかりますがとにかくめっちゃいろんなことができることはわかります。開いて色々動かすだけでもわりと楽しいです。
設定について
kibana の container はデフォルトで elasticsearch:9300 につなごうとするので elasticsearch も default の 9300 で起動するよう特に何もいじっていません。
設定ファイルを弄りたい場合には environment に記述する若しくは kibana.yml を bind して up すると良いです。詳しくは kibana の docker document を参考にして下さい。
http://localhost:5601 にアクセスすると kibana server にアクセスできます。
jupyter
python から elasticsearch 使いたいよね、ということで jupyter notebook server を用意しています。
jupyter には http://localhost:8888/tree/notebooks からアクセスできます。 password は "dolphin" です。
python 環境には elasticsearch が pip で入っていますので python client はデフォルトで使うことが出来ます。
Sample notebook
いくつかサンプルのコードが入っていますので参考にして下さい。
特徴ベクトルでの類似度検索
~/client/notebooks/sample_search_by_cosine-sim.ipynb に特徴ベクトルでの類似度検索を行うサンプルが入っています。
128 次元のベクトルを "matching" index に 100000 件登録して、クエリのベクトルとコサイン類似度の意味で近い順にソートする、ということを行っています。
例えば以下のような例が応用でしょうか。
- 画像の特徴ベクトルでの類似度検索
(クエリ画像と、マスタ画像の類似度を arcface や center-loss などの metric learning で得たモデルの特徴量でソート) - 文章を表す特徴量でのソート
(SWEM など文章を埋め込む(embedding)手法)
Result
検索の時間は以下のようになりました。 elasticsearch 爆足だぜ :D
| method | %%timeit |
|---|---|
| scipy.spatial.distance & list内包記法 | 3.27 s ± 17.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) |
| scipy.spatial.distance & joblib parallel | 5.2 s ± 108 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) |
| elasticsearch | 43.7 ms ± 661 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) |
Kibana でも見る
上記の notebook を実行すると実際に index が出来上がるので, Kibana からもデータを見ることが出来ます。
インタラクティブに見る
http://localhost:5601/app/kibana#/management/kibana/index_pattern?_g=() にアクセスすると index の pattern をいれる画面が立ち上がります。ここに作成した "matching" と入力して Next Step > create index patterns と進みましょう。
その後左側のナビゲーションの上から二番目、方位磁石っぽいアイコンを押します。するとずらずらっとデータが 100001 件出てきます。これが今 elasticsearch に "matching" index として登録されているドキュメントです。
この画面もまあまあできることが多いのですが一番わかり易い使い方はうえの search toolbar だと思います。ここにカーソルを当てるといい感じにクエリをサジェストしてくれます。なかなか楽しいです。
また http://localhost:5601/app/kibana#/dev_tools/console?_g=() からクエリを叩くことも出来ます。たとえば
GET matching/_search { "query": { "match_all": {} } }
とかやると全件取得が出来ます。楽しいですね。
参考
連続変数で StratifiedKFold
pandas.qcut で int に変換すると良さげ
from sklearn.model_selection import StratifiedKFold import pandas as pd def get_stratified_fold_split(X, y, n_folds=10, q=20): # Categorical.codes で各クラスに対応する int が取得できる y_cat = pd.qcut(y, q=q).codes fold = StratifiedKFold(n_splits=n_folds, random_state=71) return fold.split(X, y_cat)
q は int 化するときの分割数なので n_folds に合わせていい感じに合わせると良いかな?
