ホーム » 機械学習

「機械学習」カテゴリーアーカイブ

Contextual Bandit LinUCB LinTS

2020年3月26日 / コメントする

こんにちは。kiwamizamuraiです。

本日は文脈バンディットをやっていきます。行列とかでてきて、、、、計算が苦手な僕は、、、って感じなんですけどやってることは前回のUCBをTSと全く同じなので気楽にいきましょう。

Contextual Bandit

文脈バンディットとは以前のバンディット問題にユーザーの特徴量ベクトルを導入されたものです。というとは、前回は単純に時刻tにおいて行動価値関数のみでアームを選んでいましたが、文脈バンディットではユーザーの情報も加味してアームを選ぼうという考えです。

アルゴリズムに入っていく前に具体例と一緒にこの文脈バンディット問題の全体像を掴みます。

たとえば上の図のような感じです。報酬は購入額（例えば正規分布）とかでもいいです。とりあえず問題設定はできました。

ポリシーに対するoffline評価などはまた次回やりたいと思います。今回は単純に次の二つのポリシーの実装のお話です。

LinUCB

まずLinUCBとは前回したUCBの文脈バンディットへの拡張アルゴリズムです。この時点で上界・分散的なイメージをもって欲しいです。また、Linearの略です。見ていきます。（添字a,tは時刻tにおける行動aに対する、という意味）

LinUCBのLinearの部分はここからきています。LinUCBは報酬に対して上記の線形モデルを仮定します。また、ノイズとしてsub-Gaussianを乗せます。すると期待値は次の通りです。

このように行動aに対して確率分布を仮定し、さらにそのパラメータを逐次的に更新することでより柔軟なアームの選択が可能になります。ではそのパラメータの更新式を導出します。

上のように定義します。するとbiased-MFまたはRidgeの時と同じ導出より

次が得られます。

次にUCBの部分についてです、

どうやら上は定理のようです。そこまで終えませんでした。すいません。とはいえこれがわかったので前回のUCBを思い出してUpper Boundを加算してアームを選べばよいだけです。

まあA_aは共分散行列とやらですね、inverseをとる点だけ注意していればおkです。では改めましてpresuso-codeは

いい感じですね。ちなみにハイブリットモデルというバージョンのものもあります。

ハイブリッドでは上のように報酬に対する線形モデルが少し変わります。これは前回実装したbiased-MFと全く同じ発想で、zはユーザーの特徴ベクトル、betaは全アームに共通する共有ベクトルと行った感じです。（勝手に命名しました。）presudo-codeも貼っておきます。

でわLinear Thompson Samplingも見ていきましょう

LinTS

これは前回のTSと全く同じで事後分布からパラメータシータをサンプリングする方法です。ただ、論文中の事前分布とかは結構複雑で結果的に次のpresudo-codeになってます、

ガウス分布を仮定していますが、パラメータが複雑なので簡略化しましょう。なので上の疑似コードは一旦無視です。

とりあえずベイズを使って上を分解していくんですけど、ここでは事前分布としてsub-Gaussianを仮定します。

尤度は今回の場合だとガウス分布です。（最初の線形モデルの仮定より）

となると事後分布なんですけど、「ガウス x ガウス = ガウス」なのですが、、、、、問題は多次元なんですよね、、、、僕計算めちゃめちゃ嫌いなんですよね、、、、

https://stats.stackexchange.com/questions/28744/multivariate-normal-posterior

って感じで、一応サンプリングできます。

LogisticTS

ただ、前回実装したbanditって報酬はベルヌーイを仮定したじゃないですか、ということはcontextualにもあるはずですよね。

モデルは簡単です、先ほどの線形モデルにロジスティックをかますだけです。

そうなんです、あるんです、ただロジスティックを使ってしまうと事後分布が解析的には得られないので勾配法とかになっちゃうところをラプラス近似でやろう！という発想です。僕はラプラス近似をあまり知らないのでそれも勉強しないといけませんが、とりあえず話を進めると事後分布は正規分布になるようです、さらに共分散行列は対角行列らしいです。presudo-codeは次のとおりです。

ぎょえええって感じですね、これを実装しなければいけないのか、、、、

実装

実際の報酬のアームの分布は次の通りです。

LinUCBの結果

LinTSの結果

パラメータを変化させてRegretも確認

ちょっと疲れました。

ロジスティックはまた今度機会があればやります。

References

Doubly Robust AIPTW

2020年3月19日 / コメントする

こんにちは。kiwamizamuraiです。

本日はダブルロバストについて勉強します。まぁ、IPWも厳密には理解できていないんですけどね。。。。僕の勉強スタイルはとにかく大きく進んで大きく戻っての繰り返しです。するとたまにぱってアイデアが生まれてわかる時があります。まあそんなことはおいておいて

Recap

この記事ではダブルロバストの理論について触れます。その前に前回のIPWの復習も行い、新しい知見が得られることにも個人的に期待します。

https://research.miidas.jp/2020/02/傾向スコアとは/

ただ、Counterfactual Machine Learningにもダブルロバストが登場して用語などが非常にごっちゃになりやすいところだと思うのでそれについてもまとめます。

Multi-Arm Bandit Algorithm
Reinforcement Learning
Counterfactual Machine Learning
Causal Inference

ここら辺は正直ごちゃまぜになっている気がしますね。。。。。さきに断りますが今回のダブルロバストは因果推論におけるものを指します。反事実機械学習のポリシー評価に対するダブルロバストではありません。

因果推論の復習

僕たちが測りたい因果効果はATE(Average Treatment Effect)といいます。

ちなみに割り当てがされた、つまり処置群における平均処置効果はATTといいます。

ATEについては各群間での効果量の差をとればいいじゃん、という単純な案がありましたが駄目でした。それはoutcomeである $y$ の期待値が確率収束するものの条件付きの値だからです。つまり、上記のATEではないということです。そこでRubinのSUTVAの仮定のもとで因果効果を「無作為割り当てでないことによるバイアス」を消去しつつ測ろうというものでした。

そして登場するのが傾向スコアです。 $y$ に対してセミパラメトリックなアプローチができ、モデルの誤設定の可能性が低まります。また、 $N$ 次元であった共変量が1次元になることでその影響も排除することができます。

この傾向スコアはSUTVAを満たしてくれるので等しい傾向スコアのもとで

が成り立ち、

がATEであることがわかります。少し補足をしておきます。

傾向スコアのモデルはロジスティックが一般的ですが、RFなどのアルゴリズムも使用可能です。ただ、その後たとえばマッチングを行うと仮定するとRFの高精度な分類により各分布が大きくことなる可能性があります。この場合、マッチングがうまく働かないかもしれません。なので個人的にはロジスティックがいいかなと思います。

Inverse Propensity Score Weighting

最近傍マッチングと層別解析については触れません。ここではIPWの復習を個人的に行います。このアルゴリズムは無作為割り当ての問題を解決しつATEを算出することができます。では解説します。

真の傾向スコアが既知かつSUTVAが成り立つとする。

このとき、上のように定義することでそれぞれy1,y0の周辺平均の不偏推定量となります。さらに、我々が算出する傾向スコアに対してもタイスの法則よりこれらは一致推定量になります。（ちなみに分母を集合の濃度Nで代用する方法もありますがこちらのほうが精度は高いことがしられています。）次のセクションではこの意味について考えてみます。

Pseudo-population

eは傾向スコア、つまり確率です。この逆数を重みとする、というのはどういう意味があるのでしょうか？例えば0.1の逆数は10です。0.8の逆数は1.25です。

これはつまり確率を割合として考えれば個人的にはわかる気がします。つまり、各群の集合の濃度を傾向スコアの逆数で補正しているということです。Inverse Weightingの値をPseudo-populationといいます。たとえばマッチングにおける問題点の一つは分布差でした。つまり。個体数が異なります。この個体数差をInverseで重み付けという形で加味できるということです。

Doubly Robust

では個人的に本題のダブルロバストについてです。これは二つのモデルを仮定してどちらか少なくともどちらか一方が正しければうまくいく、というものです。二つのモデルのうちの一つは単純な回帰によるATEの推定モデルです。

これはyの真のモデルであればの話です。そしてもう一つはIPWを使った上記のものです。

こちらは傾向スコアを通したATE測定のためのモデルでした。ダブルロバストはこれらを融合します。つまり、yとeのモデルを融合するということです。DR(Doubly Robust)はこれらのモデルによって得られたe,y_1y_0を用いて算出されます。

計算式は上の通りです。シグマの前の1/nはIPWのセクションで述べた理由からです。デルタはATEのことです。非常にややこしい式ですね、、、少しずつみていきます。

この大括弧内の初項はIPTW、第二項はAugmentationと呼ばれます。とりあえずこの期待値をみてみましょう。

つまり、第二項がゼロでいてくれればE(Y1)が推定できます。ではどのような時がゼロになってくれるのか？ここでダブルロバストが生きます。

まず、傾向スコアが正しくて、回帰モデルが誤っている場合。つまり、

であり、傾向スコアが真であるとき、

とうまく第二項が消えてくれました。わーい。E(y0)も同様です。では逆の場合を考えましょう。つまり、傾向スコアが誤っていて、回帰モデルが正しい場合

であり、回帰モデルmは正しい時、同じように第二項は

となります。こういう意味でダブルロバストと言われています。ちなみにですがこの推定方法をAugmented IPTWといいます。AIPTWです。

実装

データは前回と同じものを使いました。IPTWとAIPTWを比較するとわずかですが今回はIPTWが勝ちました。また、分母に集合濃度Nを用いると大きく精度が悪化しました。

次は反事実機械学習のダブルロバスト！

References

Counterfactual Machine Learning 入門

2020年3月15日 / コメントする

こんにちは。kzです。

本日は反事実機械学習に軽く入門してみようと思います。Causal InferenceやCounterfactual MLは個人的にはまだ若い分野だと思っていて非常に今後が楽しみです。ちなみに共分散構造分析(SEM)も気になります。

https://en.wikipedia.org/wiki/Structural_equation_modeling

表記とか

反事実機械学習とは「オフライン環境下での新しいポリシーの学習・評価」のことです。まず記事中の表記は下の通りです。

$\delta$ が報酬ですね。ちなみに $x_i$ はContextとありますがこれは文脈バンディットの文脈にあたります。Contextual Banditとは各ユーザーのデータ $x_i$ をその特徴ベクトルし、バンディット問題を達成するアルゴリズムです。この特徴ベクトルをcontextといいます。

広告を例にとりますとこんな感じです。

このデータセット $S$ より以下を目標とします。いわばこれが反事実機械学習の考え方の核です。（ちなみにデータのことをポリシー $\pi$ によるログデータともいいます。）

まずonlineとofflineについてですがこれらは逐次学習と一括学習をそれぞれ意味します。新たなアルゴリズムによるsystemをofflineで評価することが目的です。また、より良いsystemを学習させることも目標になります。（systemはpolicyのこと）画像を通してみてみます。

ポリシーの評価についてもっとも単純なアイデアはA/Bテストですね。画像上のことです。これをcounterfactorを用いてオフラインで行うことが目標です。画像下のことです。

そこで重要なのが評価指標です。CTRなどは前回解説しました。他にも次のようなものがあります。

特にインターリービングは僕は今回初めて知ったんですがA/Bテストより大いに効果を発揮してくれるものだそうです。Netflixさんも使っているらしいです。また今度詳しくみてみます。

Reward Prediction

system $\pi$ を評価する方法の一つ目がReward Predictorです。これは報酬関数を学習により得ようとする方針です。報酬関数がわかれば新たなポリシーに対してシミュレーションができます。

ただ、この方法だと $\pi$ がバイアスに影響を受けやすいようです。考えられるバイアスとしてはモデルバイアスとセレクションバイアスがあります。モデルバイアスとは特徴量とモデルに依存します。セレクションバイアスはポリシーによる過学習（過表現）です。

モデルバイアスとは報酬関数の複雑性に起因します。この関数は非線形であったり、または考え付かないほど複雑な構造を持っているかもしれません。そのような関数を学習することは難しいです。セレクションバイアスとはポリシーによる行動選択が一部に偏ってしまう現象をいいます。これはポリシーによる各行動の分布差から生じます。

Counterfactual model

そこで登場する手法が反事実モデルです。報酬関数を高い精度で得るためにまずはポリシーの分布を近づけてバイアスを消そうというアイデアです。

次の例を考えます。

つまり３種類のアクションに対して、各報酬はバイナリです。まずは単純な評価を行ってみます。

本当にこれでいいのでしょうか？そこで反事実という概念を導入します。

選択していないアクションはCounterfactorと呼ばれます。従来のポリシーの評価では選択したアクションのみが評価対象でした、ここでは反事実つまり、選択されなかったアクションも評価にいれます。ではどうやって導入して、さらには指標として生かすのかみていきます。

Inverse Propensity Score Estimator

IPSと呼ばれる指標を紹介します。

このように行動に対するIPSは反事実を含めて算出されます。単純計算（3/4）から得られるよりも実質的な効果を表しているんじゃないかと個人的に考えています。とはいえこのIPSを用いてポリシーの評価方法を考えていきます。

IPS Utility Estimator

このIPSを用いて次のように改めて定義します。先ほどの指示関数のところが新しいポリシーによる確率分布に変わりました。分母は変わらず傾向スコアです。

こう定義することで以下が得られます。計算

んー、正直僕はまだちゃんと理解できていません。すいません。ただわかったことを改めてまとめますと反事実モデルとIPSを用いることによって新たなアルゴリズム（ポリシー）のシミュレーションができると言うことです。

最後にその他の指標について軽く触れておきます。少しでも理解しておきたい、、、、

Self-Normalized Estimator

どうやらIPSにおける定数問題を解決した指標らしい

https://www.cs.cornell.edu/people/tj/publications/swaminathan_joachims_15d.pdf

Doubly Robust Estimator

二つの手法のいいとこ取りをした指標らしい

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/double_robust.pdf

感想

非常に難しいです。新しい知識が多く得られたのでその点は嬉しいですが自分の実力不足にかなり萎えています。もう一度勉強しなおそうと思います。でわ

References

傾向スコアとは

2020年2月26日 / コメントする

こんにちは。kzです。

今回はマーケティング分野で有名な傾向スコアについてやっていきます。ちなみにですけど巷では次の本が流行っているらしいです。

まず初めにですが、傾向スコア分析とアップリフトモデリングは別の手法です。当初僕はごっちゃになっていました。まあ後者はこの記事では触れませんが、、

とりあえずこの記事のフォーカスは「因果」です。因果を図ります。まずは簡単に用語の説明から。

今からする話は上の構造を元に成り立っています。例えばサイゼリアのクーポンの例を用いて解説します。

Treatment is クーポンを貰った人たちの集合
Control is 貰ってない人たちの集合
Confounder is 年収、外食の頻度など（交絡因子/共変量）
$\Omega$ is 全データの集合
$y$ is サイゼリアに行ったかどうか（購入額もおk）
Selection Bias is トリートメントとコントロール集合間の分布のズレ（共変量シフト的なイメージ）

たとえばこのクーポンの効果を図りたいとします。この時TreatmentとControl間で差を見るだけでは正確ではないかもしれません。その原因がConfounderによるSelection biasです。つまり、集合間で分布に差が生じてしまうかもしれないからです。

実際今回の例で用いるデータを単なる集合間の引き算で算出するとその値は真の値（設定したもの）と異なりました。なのでもっといい因果効果の測定方法についてみていきましょう。

Rubin Model

因果推論で有名なのはこの人、Rubinさんです。因果効果の最もベーシックな考え方は次の画像です。

図からわかるようにデータを $X_i$ さんで考えた時にTreatmentの効果があるかどうかは物理的に測定できません。なぜなら「仮に〜だったら」のデータは得られないからです。

先ほどの例も含めて、因果効果を図るのはやはり非常に難題です。

ただ、解決策の一つとしては各集合間に無作為な割り当てを行えばいいかもしれませんが、実はそれは現実的ではありません。なぜなら例えば治療薬を例にとります。患者さんのあらゆる共変量を考慮してTreatmentの割り当てを行うため、どうしてもSelection biasが起きてしまいます。そこで使われる手法が傾向スコアを用いた層別化（これもマッチング）やマッチングです。

SUTVA

Stable Unit-Treatment-Value Assumptionの略です。RubinのモデルにはSUTVAという重要な仮定があります。

The potential outcomes for any unit do not vary with the treatments assigned to other units, and, for each unit, there are no different forms or versions of each treatment level, which lead to different potential outcomes.
http://utstat.toronto.edu/~nathan/teaching/STA305/classnotes/week4/sta305week4classnotes.html#stable-unit-treatment-value-assumption-sutva

つまり、任意のOutcomeは他の個体に割り当てられたTreatmentに干渉しない。例を出すと、Aさんがサイゼリアに行った結果、サイゼリアがめちゃめちゃ人気になってしまってみんなクーポンを欲しがるのはダメ。という感じですかね？これを数式で表すと

です。つまり共変量（ $x$ ）を固定した場合、Outcome（ $y$ ）は割り当て（ $z$ ）と独立である。ことが重要な仮定になります。もう一度具体例で噛み砕きます。

共変量（年齢、性別など）のみがクーポンの配布（割り当て）を決定する
共変量が等しければ割り当ては同確率

このおかげで先ほどの「仮に〜だったら」のデータを擬似的に得ることができます。つまり、共変量が等しいデータを探すということです。

しかし、先ほどの治療を例にこの仮定を考え直してみます。共変量としてシンプルに年齢を考えます。この時、Treatmentここでは薬Aの割り当ては本当に年齢のみによって決まるでしょうか？また、共変量は現実問題では観測されない可能性も考えると共変量が等しいという状況に疑問が抱かれます。なので「共変量が等しいデータを探し方」について次は探っていきましょう。

Propensity Score

Rubinはまず次の関数をバランシングスコアと定義しました。

そしてRosenbaumとRubinは傾向スコア $e(x)$ を次のように定義しました。

そして彼らはいくつかの定理を証明し、最終的に次の主張を得ました。

Propensity Score is Balancing Score
任意のBalancing ScoreはPropensity Score、if and only if、 $e(x)=f(b(x))$
Balancing ScoreはSUTVAを満たす

ここで、 $f$ としてidentity functionをとることで $b(x)$ が傾向スコアであることがわかります。これらを用いて傾向スコアマッチングや層別解析が誕生しました。SUTVAの仮定を用いると

また、

が得られます。なお、傾向スコア $e(x)$ についてはロジスティックモデルが一般的のようですが、決定木などでもいいです。

ということで「共変量が等しいデータを探し方」についてですが、「傾向スコアが等しいデータ」で代用できることがわかりました。あとは分析手法を見て実装するのみです。

層別解析

傾向スコア分析はいくつか手法があります。ここではまず層別解析についてです。これは単純で、傾向スコアをブロック分割します。

傾向スコアにはロジスティックなどを持ちいると仮定するので、 $e(x) \in [0,1]$ になります。

層別に分けてそれぞれの層においてOutcomeの平均の差で因果効果を算出します。ここで $n$ についてですが通常はサブクラスのサイズが等しくなるように分割するらしいです。個人的には $n$ を細分化すればするほど精度があがるんじゃないかなと思っています。

Matching

２つ目の手法はマッチングです。といっても層別も層別マッチングなんですけど、、、、まあ置いておいて、、TreatmentとControlの各集合の要素をPropensity Scoreの類似度でマッチングします。この時、最近傍やマハラノビス距離を用いた手法などいろいろありますが、ここではキャリパーマッチングを実装します。これはマッチングに閾値を設ける手法です。

下の図のようなマッチングが得られたとします。

キャリパーマッチングでは三つ目のマッチングにおいて傾向スコアの差がCaliperを超えている（ $|0.63 -0.33 | > 0.2$ ）のでマッチング不成立となります。成立したデータを対象に層別の時と同様に平均の差で因果効果を算出します。

とはいえ実はマッチングはSUTVAの仮定などが原因で良くないらしいです。

傾向スコアマッチングが近似しようとしているのは完全なランダム化である．これは共変量を1次元の指標にして，共変量とは独立にトリートメントの効果を推定しようとしていることからも明らかである（本文中に書かれているが1対1マッチングにおいて同じ傾向スコアのマッチング相手がいたらランダムにどちらかを選ぶ）．それに対して，マハラノビス距離やCEMなど他の方法は完全にブロック（層化）したうえでのランダム化に近似しようとしている（各共変量の距離を計算するので）．したがって，傾向スコアマッチングよりもマハラノビス距離マッチングやCEMの方が望ましいということである．というわけで，Kingらはマッチングをする際にはマハラノビス距離やCEMを利用することを薦めている．ただし，傾向スコアが数式的に問題があるというわけでなく，またマッチング以外に傾向スコアを用いることについては今回の指摘はあてはまらないと繰り返している． http://analyticalsociology.hatenadiary.com/entry/2017/09/11/121102

そこで登場するIPWという手法も見てみたいと思います。

IPW

冒頭でも申したとおり、単純に集合間で引き算をするとやはり共変量シフトによる選択バイアスが大きく現れます。そこでこのバイアスの修正を試みる手法がIPWになります。

具体的には上のようにすることでバイアスを修正しつつ、ルービンの難題であった『〜だったら』の時の不偏推定量となることが次のリンクよりわかります。

https://qiita.com/deaikei/items/df3626486986566cb65c

まだいろいろありますが、内容が難しく、理解できてないのでいったんここで切ります。

実装

使うデータはこんな感じです。リンク先のデータを使わせていただきました。そこではIPWのみの実装になっていたので今回紹介した、層別とキャリパーで比較してみようと思います。

20代、30代の男性にバイアスを載せました。詳しくはコードを見て下さい。結果としてはIPWが最もいい精度でした。

アップリフトモデリングやります。でわ

References

事前分布に深入りする

2020年2月20日 / コメントする

こんにちは。kzです。

本日はprior distributionについて深入りしてみようと思います。事前分布って不思議ですよね。個人的には共役事前分布って誰が見つけたのかなー？と永遠思ってます。事前分布のスキルを高めるということはベイズの力を高めるということだと思います。なのでやっていきましょう。

Conjugate Prior

欲しいものはいつもposterior distributionです。

$p(\theta)$ と $p(\theta|X)$ が同じ分布になる時、そのpriorをconjugate priorといいます。共役事前分布です。しかし、実世界においてconjugate priorで十分か、といいますとそうではありません。なので現状はMCMCを使った次のようなアルゴリズムを使って数値計算するらしいです。

Stan
WinBUGS（Bayesian inference Using Gibbs Sampling）
OpenBUGS（Bayesian inference Using Gibbs Sampling）
JAGS（Just Another Gibbs Sampler）
PyMC（Hamiltonian Monte Carlo）
INLA（Integrated nested Laplace approximation）

とはいえ共役事前分布はもう皆さんご存知で、飽きていると思うので少し特殊なPriorを見ていこうと思います。

Improper Prior

事前分布が以下を満たす時、improper priorと言います。

たとえば、

$Beta(0,0)$
$Uniform(-\infty, +\infty)$

などです。priorがimproperであることが問題かどうかは人によってことなるようです。ベイジアンのLuca Rossiniという方はimproperでも問題ないと言っているようです。とはいえ、ベイズの定理の右辺が求まらないのであれば事後分布を得ることはできないのでもともこもありません。

Uninformative Prior

とはいえパラメータの事前分布なんてわからないのにどうすればいいんだ、、、という時に使われるのが無情報事前分布です。non-informative priorともいいます。情報がない、以外にも次の理由で使われたりします。

priorの事前情報がない
posteriorに変な影響を与えたくない
データのみの情報でposteriorを決定したい

一様分布はいい例じゃないでしょうか。そして他には以下のようなものがあります。

ここではJeffry’s Priorについて深入りしようと思います。

Jeffrey’s Prior

以下を満たす時、パラメータ $\theta$ のpriorが近似的にnon informative priorとなり（次で話します）、そのpriorをJeffreyの事前分布といいます。

見ての通り、フィッシャー情報量のルートになっています。また、このpriorはリパラメタライゼーションに対して不変です。これについては下で述べます。

とはいえ、これだけだとなにを意味してしているかよくわかりません。なので簡単な例、二項分布でJeffrey priorを求めてみます。

尤度は上のものを考えます。Jeffrey priorを $p_J(\theta)$ と表すことにします。

よってフィッシャー情報量は

したがって

とこの尤度に対するJeffrey priorを求めることができました。しかもよく見るとこれは $Beta(1/2,1/2)$ ですね。ついてでに分布も見ておきます。

ちなみにリパラメタライゼーションについては全単射な関数 $g$ を考えます。このとき $\phi = g(\theta)$ という変数変換にたいして $p_J(\phi)$ は次の二通りの方法で得られます。

まずは変数変換後の尤度を用いて計算する方法。そして

ヤコビを使う方法です。たとえば

というリパラメタライゼーションを考える例は参考文献にあるので気になる方はどうぞ。

Jeffrey’s Priorの意味

さて、これを使う意味ですが個人的には２つあると思っています。

リパラメタライゼーションによる新しいモデル構築が容易な点
posteriorとのKLを最大ができる点

まず、一つ目は対象のパラメータに対して別のモデルを考える時にヤコビをかけるだけで済むのがいい点の一つだと思います。

そして二つ目、こちらが各だと思っています。Jeffreyを用いることでそのposteriorとのKLを最大化させることができます（データが十分多い時）。これによってposteriorはpriorには極力影響されない一方で、最大限にデータの影響のみを受けた分布になります。つまり、データをはっきりと表現していることになります。

実はこの話はBernardo reference priorというものと関係があるようです。そのパラメータ $\theta$ が一変数という条件がJeffrey Priorと一致するようです。

こういう意味でJeffrey priorはuninformativeと言われているようです。ついでにパラメータをいじった事後分布の結果を見てみましょう。

５種類の事前分布に対する事後分布の変化の図です。Jeffrey Priorは右から二つ目です。データの情報を最大限に説明する分布と言いましたが、まさにそうなんじゃないかなと思いました。まず注目すべきは $y=0,n=1$ です。一回の試行で裏の出た時ですが、パラメータはグイっと左によっています。右の一様分布ではそうなりません。

次に注目したのが $y=1,n=2$ です。 $\alpha=\beta=0.001$ の同じ条件と比べると事後分布が綺麗に半円を描いています。関数が滑らかであることはいろいろと都合がいいと思うのでこれもJeffreyの良さかなと思いました。

お気づきかと思いますが、 $\alpha=\beta=0.333$ と比べるとあまり差がないように思います。僕もそう思いもう少し調べてみました。

見ての通り、事後分布にそれほど大きな差はないと思いました。よって僕の中の結論としてはデータ数が非常に少ない場合においてJeffrey Priorは力を発揮するのでは？です。

僕的まとめ

この記事でreference priorとjeffrey priorの二つの新しい事前分布を紹介しましたが、共役に加えて最終的なベストなものは何なのか、というのが気になる点です。パラメータについて考慮するものがなければ共役事前分布またはreference priorがいいなと思いました。ここで、考慮するものとはたとえばデータのタイプであったり、物理的な何かであったり詳しいことは僕にはわかりませんが事前情報というよりは制約的な形で考慮するものなんだと思います。たとえば、画像処理における事前分布だと以下のようなものがあります。

https://dmitryulyanov.github.io/deep_image_prior

そしてこのJeffrey Priorですが改めてまとめますと、これベルナドのrerefence priorの単変量バージョンに相当します。そしてこれはフィッシャー情報量から導出されます。これはつまり今あるデータから事前分布を構築するということを意味します。したがってよく使われる直感、inductive biasというべきでしょうか、の影響を極限まで希薄した事前分布を意味します。また、無情報事前分布と言われている理由はデータが十分に大きい場合、事後分布とのKLを最大化させるためです。この証明は参考文献にあります。最終的には場合分けで解が得られていました。

話が長くなりましたが今回個人的には学ぶことが多かったです。情報幾何に少し近づけた気がします。でわ

References

Variational Bayes 入門

2020年2月13日 / コメントする

こんにちは。kzです。

本日は変分ベイズやります。ちなみに呼び方はいくつかありまして、変文ベイズ、変分推論、Variational Approximation（変分近似）など。

変分とは？

そもそも変分ってなに！って感じですよね。実はこれ微分方程式とか汎関数とかが関わってます。

例えば点推定である最尤法はスコア関数（対数尤度）を微分して解を求めますよね。変分法はこれを拡張した概念です。

つまり、関数の関数の微分が変分です。

変分とは汎関数の微分です。詳しくは調べていただくとすぐわかりますが例えば最短曲線など求めるときはオイラーラグランジュ方程式と変分法を用いたりします。

変分ベイズとは？

事後分布 $p(\theta, X)$ を求める手法の一つです。MCMCと同じ感じ？と思った方もおられると思います。はい、MCMCも事後分布を求める手法です。

mcmc入門-gibbs-sampling

ではもういきなりですがVBとMCMCどっちがいいの？という疑問が生まれます。

ずばり、一番の違いは速度です。一般的にはVBの方が早く、計算の多いMCMCは遅いです。データ $X$ が多いときはVBの方がいいかもしれません。ただ上にあるようにVBは漸近的に分布を保証するわけではありません。

まずは変分下限の登場です。EMアルゴリズムの時と似てます。

$z$ は潜在変数（パラメータ）です。 $H[z] = - \mathbb{E}_q[\log q(z)]$ は前回登場したShannon entropyですね。最後の式が変分下限です、 $L$ と置くことにします。

せっかくなのでKLダイバージェンスとの関係も見てみます。

目的は事後分布 $p(z|X)$ を近似することです。なので $q(z)$ でKL最小化を目指します。式の最後で出てきた $L$ は先程と同じ。つまり、KLの最小化は変分下限の最大化に等しいことがわかりました。

しかもよくみてください、KLって汎関数ですよね。

Mean-Field Approximation

変分ベイズでは平均場近似という重要なポイントがあります。これは $q(z)$ に与える次の仮定です。

つまり、各潜在変数が独立であると仮定します。すると変分下限は次のように書き直せます。

計算を整理するために次を用います。対象の変数以外での期待値です。

これを用いて先程の式をさらに展開していきます。

$i$ に注目していただければわかりますが、くくりあげています。第二項は $i$ を除く $j$ の項です。ラグランジュを用いて次の目的関数を得ます。

ここで変分法を使います。具体的には $q_j(z_i)$ に関してEuler-Lagrangeを用います。

ここで、 $Z_i$ は正規化定数と呼ばれるものです。以上からわかるように $q_i$ の最適化には他のすべての $q_j$ が必要になるのでイテラティブな更新になります。

一変数ガウスの例

次のような例を考えます。

変分ベイズを用いてパラメーラ $\mu, \tau$ の分布を逐次的に求めます。まず以下の尤度をばらしておきます。

また平均場近似より次を仮定します。

では先程の計算を用いて $q_\mu$ を計算します。

$\mu$ に関して平方完成して以下を得ます。

同様の作業を次は $\tau$ について行います。

ガンマ分布に注意して

以上より

がわかりました。これより各期待値も簡単にもとまります。

したがって

を用いて更新すればいいことがわかります。

もう一つの例として混合ガウス分布をVBを使ったEMで求める例がありますが、非常に難しいので詳しくは以下をご覧ください。

応用

難しすぎて実装できませんでしたが変分ベイズを使った応用はたとえば自然言語処理におけるLDAがあります。とても難しい、、、、でわ

References

バンディットアルゴリズムの続き

2020年2月7日 / コメントする

こんにちは。kzです。

今回は前回のバンディットアルゴリズムの続きです。UCBと簡単なトンプソンサンプリングの実装を行います。前回実装した $\epsilon$ -GreedyとBoltzmann Softmaxとの最終的な比較も行います。

Keywords

この記事のキーワードを先にリストアップします。

$\epsilon$ -Greedy
Boltzmann Softmax
Hoeffding’s inequality
UCB
Bayesian UCB
Thompson Sampling
scaled inverse chi-squared Distribution

先頭２つは前回やったので３つ目から話します。

強化学習　Bandit Algorithm で入門する

Hoeffding’s inequality

Hoeffdingの不等式です。これはUCBの導出に使います。証明にはマルコフの不等式とチェビシェフの不等式を使います。まあそれは置いておいて、この不等式の意味を考えます。

確率変数 $Z$ の平均とその期待値の誤差 $t\in\mathbb{R}_+$ の確率を $t$ で測っています。これがまさに後述するUCBの核の考え方です。こちら側で $t$ そ操作することで、期待値のブレの許容範囲をある確率の範囲で操作することができます。

UCB

UCBはアームの期待値に加えてその上限（Upper Confidence Bound）、いわばアームの可能性（分散）、を考慮したアルゴリズムです。どうやって上限を加味するかといいますと、対象のアームを選択した回数の逆数で重み付けします。こうすることで多数引いたアームにはより小さい上限を、少数引いたアームにはより大きい上限を付与することができます。

これは直感的にもいいですよね。何度も引いたことのあるガチャガチャよりも数回しか引いたことのないガチャガチャの方が可能性を感じますよね。そういうことです。

ただし、

見ての通り、分母 $N_t(a)$ が小さいほど大きい値が加算されます。イメージは次の感じです。

お気づきかもしれませんが逆数と言いつつ、ルートを付けてます。気になりますよね。ということで証明します。先程のHoeffdingの不等式を用います。

Hoeffdingの不等式において $X_i \in [a,b]$ を $[0,1]$ として次が得られます。（ $u\geq 0$ ）。報酬はベルヌーイを仮定しました。

$a \in \mathcal{A}$ を一つとり固定します。私たちの問題に書き換えるためNotationを定義します。

$r_t(a)$ 報酬（確率変数）
$\mathcal{Q}(a)$ を真の行動価値
$\mathcal{\hat{Q}}(a)$ を経験上の行動価値
$u$ をupper confidence bound, $u=U_t(a)$

代入しますと

ここで上限に対する閾値をこちらで設定します。

これを $U_t(a)$ に関して解けば終了です

おや？よくみると2の位置が異なります。それは $\epsilon$ をこちらで設定する必要があるからです。confidence levelと言われます。

UCBはこのconfidence levelをパラメータとして持ちます。もっとも一般的な値は次のようになります。

そしてこの時のアルゴリズムをUCB1いいます。代入して計算すると

先程の結果になりました。では実装してみます。

実はよくない結果です。前回のEGとBSと比べるとわかります。この記事の最後に全アルゴリズムの比較を行いますのでとりあえずは進めていきます。

Bayesian UCB

UCBにベイズを応用したアルゴリズムのことです。今までは報酬の分布にベルヌーイを仮定しましたが、他にもガウス分布の仮定があります。それぞれ次のように呼びます

Bernoulli – Thompson Sampling
Gaussian – Thompson Sampling

察しの通り事後分布からパラメータをサンプリングしてアームを選択します。

本当にハードなんですが、Gaussianの場合の詳しい計算は

https://cafeunder.github.io/rosenblock-chainers-blog/2018/03/07/bayes-gaussian-mean-sigma.html

この方がやってくれています。

Thompson Sampling

定義は少し複雑ですが、実装の際はサンプリングを行うので思ったよりはシンプルです。

とある $a$ が他のどの $a'$ よりも価値が高い、という事後確率（ $\pi$ ）を計算して $a$ を選ぶアルゴリズムです。 $R_t$ は時刻tまでのアームのhistoryです。

事後確率は積分を用いて次のように計算されます。

ここで $R_i$ は $arm_i$ の報酬履歴です。左の積分が $\mathcal{Q}(a) = \theta_i$ になる確率で右の積分がその他のアームで $\mathcal{Q}(a') \leq \theta_i$ となる確率です。積分が解析的ではないので、サンプリングします。困ったときはサンプリングです。結果アルゴリズムは次のように単純化できます。

各アーム $a$ の報酬の期待値に関する事後分布 $\pi( \theta |R_a)$ から乱数 $\theta_a$ を生成
$TS(a) = \arg \max_{a\in\mathcal{A}} \theta_a \sim \pi( \theta |R_a)$

何度も言いますが報酬の分布はベルヌーイを仮定するので事後分布であるベータ分布は非常にシンプルになります。

実装では一様分布を仮定するのでパラメータは共に1とします。

Best Arm RateをUCBと比較してみます。

全アルゴリズムでBARとCumulative Rewardsも比較してみます。

Thompson Samplingが圧勝でした。

scaled inverse chi-squared Distribution

もしGaussianでThompson Samplingを実装するならばこちらを $\sigma^2$ の事前分布として導入します。（事前分布 $p(\mu, \sigma^2)$ を条件付き確率で分解する）scaled inverse chi-squared分布といいます。

$p (\sigma^2) \sim \mathcal{X}^2 (v_{0}, \hat{\sigma}_{0}^{2})$

Code

Gaussian Thompson Samplingすごく難しいですね、パラメータが多すぎてなにがなんだが、、、

次回はContextual BanditとIPSについてまとめたいと思います。でわ

References

強化学習　Bandit Algorithm で入門する

2020年1月29日 / コメントする

こんにちは。kzです。

本日は強化学習に入門します。けどMDPとかはやらないので安心してください。簡単だと思います。ビジネスにおいてもバンディット問題は多くあるということなのでためになるかなーと思います。

Keywords

この記事のキーワードを先にリストアップします。こうしたほうが読みやすくないか？と最近やっと気づきましたすいません。

Exploitation / Exploration
MAB (Multi-Armed-Bandit)
Advertising Technology
A/B Test
Bayesian A/B Test
$\epsilon$ – Greedy
Boltzmann Softmax

Exploration / Exploitation

Exploitation is 活用
Exploration is 探索

になります。僕の日常生活を例にして説明します。

ラーメンが好きで毎回行きつけのラーメン屋さんにいくんですよね。もちろん、毎回いっているということはそこが美味しいって経験からわかっているので通っているんです。これがExploitationです。

しかし、同じラーメン屋さんにばかり通っていると仮に近くにもっと美味しいラーメン屋さんやつけ麺屋さんがあってもその存在を知り得ないですよね。なのでたまには自分の知らないお店に期待していきたくなりますよね。僕も3回に1回くらいの割合で新しいお店を体験します。これがExplorationです。

ただ、新しいお店だと「美味しい！」時と「普通かなー」な時と「んー」な時がありますよね。これらを報酬といいます。もちろん報酬の高い、つまり「美味しい！」を選択できるようなExplorationができれば理想ですね。

これらを考慮すると、ベストな選択としては行きつけでExploitationしつつも期待度の高いお店にExplorationしたいですよね。

期間 $T$ 内で探索・活用をベストな比率で行って最終的に最高の報酬（満足度）を得たい！がBandit問題です。

Multi-Armed Bandit

上記のように複数の選択肢に対してExploration / Exploitationを考える問題を多腕バンディット問題といいます。

期待値がわからないK個の選択肢が存在する
$N$ 回の試行全てにおいて最善の選択肢を選び続けトータルの報酬を最大化したい

という感じです。（お気づきの方もいるかもしれませんが状態 $S$ を考えません。厳密には $|S| = 1$ ）

もっともポピュラーな例は広告の最適化とかですかね。薬の投与などもたまにExampleで見られますがここでは広告を例にして話を進めます。なのでいったんBanditからは離れてこれについてちょっと深入りしていきます。

Advertising Technology

広告に関わる全住民つまり、広告主側と媒体側（広告主，メディア，消費者）を幸せにするためのテクノロジーです。

そのなかでもReal time bidding（RTB）がキーワードになります。それを説明する前に次の用語を簡単に

DSP (Demand-Side Platform)
SSP (Supply Side Platform)

DSPは広告主側の広告効果を最適化するため、ユーザーに適した単価の安い配信先を探す側。媒体側の広告収益を最適化するため、より高額な広告に入札する側です。

つまり、DSPが「この広告貼ってー」とお願いし、SSPが「ええよー」と返します。しかし、一対一関係ではないので「俺の広告も貼ってくれー」といろんな人がお願いします。（SSPも複数あります。サイトA、サイトB的な感じです）

そんなマーケットのことをRTBといいます。複数のDSPが各々資金を持ってSSPに交渉し、最も価格の高いDSPをSSPが決定します。ただ値段の妥当性がわからないですよね。これも機械学習で最適化するそうです。そこで次の用語が登場します。

CVR：ConVersion Rate．コンバージョン率
CTR：Click Through Rate．クリック率

これらの指標をもちいてDSPの値段が決定されたりします。これ以上はここでは触れません。気になる方は参考文献より飛んでください。

Bayesian A/B Test

A/Bテストってご存知ですよね。AとBどっちがいいの？？を統計学的仮説検定を元に検証する試験のことです。

Bayesian A/Bテストとは、A/Bテストをベイズでやろう！！のことです。たとえば商品Aの購入率が $p$ 、商品Bの購入率が $q$ としたとき分布に有意差あんの？をベイズで解決します。

http://tdual.hatenablog.com/entry/2018/04/21/004620

この方の記事が最高に纏まっています。一応僕もベイズ推定の記事書いてます。

ベイジアン入門　ベイズ推定

ちなみにバンディットのアルゴリズム実装の最後にベイズ使うので理解しておくことをおすすめします。

Banditを再確認

これらを踏まえてBanditをおさらいすると

バンディットアルゴリズムはアームを選択した結果得られる報酬を逐次的に反映し、次のアームの選択に活かすことからA/Bテストに比べて機会損失の低減が見込めます。いわば逐次最適化A/Bテスト的な感じですかね。

加えてですねえ、A/Bテストは事前分布の問題もあるのでねえ、では次のセクションで最適化に移るためにBandit Algorithmを定式化します。

英語やああああああ、と思わないでください。よく見てくださいめっちゃ簡単な単語しか出てきてません。

注目して欲しいのは $\mathcal{Q}(a)$ です。これは行動 $a$ を入力とする行動価値関数と言われます。

注目すべきはRegret（後悔）です。これは最適な行動価値から実際にとった行動価値の差分で定義されます。定義より小さいほうがいいことがわかります。

$\epsilon$ – Greedy

では一つ目のアルゴリズムの紹介です。

パラメータ $\epsilon \in (0,1)$ を設定
の確率でExploration
- ランダムでArmを選択
の確率でExploitation
- 経験を元に、最大の行動価値を持つArmを選択

経験を元に算出される行動価値は次で定義されます

ただし

はaction= $a$ が選択された総数です。したがってExploitationは次のように定式化されます

$\epsilon$ を変化させて実装結果を確認します。アームは10種類でそれぞれの確率は単調増加で設定しました。なのでインデックスでは9番が最大の行動価値をもったアームということになります。

たしかに、 $\epsilon$ を増やすとExplorationが多くされていることがわかりまうす。Rewardsと最適なアームを選んだ割合（BAR）の変化を比較します。

青が小さい $\epsilon$ でオレンジが大きい $\epsilon$ での結果です。 $\epsilon$ をおきくするほど探索の割合が大きくなるのでその影響がBARに顕著に現れています。

Boltzmann Softmax

$\epsilon$ の問題は探索をランダムで行っている点です。つまり、実際には行動価値の高いアームも低いアームも等確率で扱っていた点です。BoltzmannのアルゴリズムではSoftmax関数を用いることで各アームを経験行動価値で重み付します。その出力をそれぞれのアームの確率で扱います。

パラメータ $\epsilon \in (0,1)$ を設定 (small)
パラメータ $w \in (0,1)$ を設定 (small)
の確率でExploration
- 各Armの行動価値をSoftmaxで重み付けし選択
の確率でExploitation
- 経験を元に、最大の行動価値を持つArmを選択

定式化すると次のようになります。

よく見てみると $w$ で割り算されていることがわかります。これもハイパーパラメータです。察しの通りで $w \rightarrow \infty$ のとき $p_a = 1/|\mathcal{A}|$ となるので $\epsilon$ -Greedyと同じようになります。

したがってExploitationは次のように定式化されます

では実装結果を確認します。

$\epsilon$ -Greedyと比較してみます。

いいかんじ

$T$ を分割して確認しますとうすい水色である本来のベストなアームが $T=200$ を超えたあたりから盛り返してきてることがわかります。

最後にコードを貼っておきます。

次回はUDBとThompson sampling実装しますー。でそのノリでContextual Banditとかも頑張りますー。

References

https://accel-brain.com/semantics-of-natural-language-processing-driven-by-bayesian-information-search-by-deep-reinforcement-learning/verstarkungslernalgorithmus-als-funktionale-erweiterung-des-banditenalgorithmus/
https://ferret-plus.com/11986
https://www.cs.princeton.edu/courses/archive/fall16/cos402/lectures/402-lec22.pdf
https://lilianweng.github.io/lil-log/2018/01/23/the-multi-armed-bandit-problem-and-its-solutions.html
https://www.smartbowwow.com/2018/08/python.html
https://haltaro.github.io/2017/08/08/introduction-to-ad-tech
https://github.com/brianfarris/RLtalk/blob/master/RLtalk.ipynb
https://blog.albert2005.co.jp/2017/01/23/%E3%83%90%E3%83%B3%E3%83%87%E3%82%A3%E3%83%83%E3%83%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%80%E5%9F%BA%E6%9C%AC%E7%B7%A8/
https://www.cs.princeton.edu/courses/archive/fall16/cos402/lectures/402-lec22.pdf

Feature Importanceを知る

2020年1月24日 / コメントする

こんにちは。kzです。

世の中ではやはり解釈性が重要らしいです。

shap値で解釈する前にpermutation-importanceを知る

前回、SHAP含めてモデル解釈の指標についていくつか触れました。やはり一度では僕は残念ながら理解できないので復習も含めて今回この記事を書きます。

前回の復習

上記のリンク先が前回の記事になります。

Permutation Importance
Partial Dependence
LIME
SHAP

雑におさらいするとPIは対象の変数をシャッフルして精度の変化からその変数の影響力を見る手法。PDは対象の変数以外を周辺化で消すことによってその変数のみの影響力を見る手法。LIMEは対象の入力データ周辺でブラックボックスモデルを線形近似しその重みでそれぞれの変数の寄与具合を見る手法。SHAPはLIMEのモデルに複数の制約（Consistencyなど）を与えてできた特殊な距離を使った手法（LIMEの上位互換）

ちなみに他にもDrop-Column Importanceとかもあるらしいです。

Feature Importance

順番的には逆になってしまいましたが、決定木自体にはFeature Importanceというものがあります。ご存知ですよね。どうやって算出されてるのや？と思ったので調べました。結論から言えばあまりにも式が複雑で完全に理解し切るのはかなりハードです。。

なのでその計算の核となるGini Impurityから始めます。

Gini不純度

あるノードにおけるGini不純度は上のように定義されます。記号については以下の通り

$C$ はクラスの総数
$p_i$ はクラスiの割合

分類においては各ノードではできるだけ少数のクラスであって欲しいですよね。具体的に計算してみます。

         二郎系   家系  　  まぜそば 
count =  4       4        4 
p     =  4/12    4/12     4/12       
      =  1/3     1/3      1/3 
GI    = 1 - [ (1/3)^2 + (1/3)^2 + (1/3)^2 ]  
      = 1 - [ 1/9 + 1/9 + 1/9 ]    
      = 1 - 1/3    
      = 2/3   
      = 0.667

各クラスから均等な量の場合とあるクラスに偏りがある場合

         二郎系   家系  　  まぜそば 
count =  3       3        6 
p     =  3/12    3/12     6/12   
      =  1/4     1/4      1/2 
GI    = 1 - [ (1/4)^2 + (1/4)^2 + (1/2)^2 ]
      = 1 - [ 1/16 + 1/16 + 1/4 ]
      = 1 - 6/16   
      = 10/16    
      = 0.625

少し小さくなりました。ではあるノードにおいて単一のクラスのみある場合はどうでしょうか。

         二郎系   家系  　  まぜそば 
count =  0       12        0
p     =  0/12    12/12     0/12
      =  0       1         0 
GI    = 1 - [ 0^2 + 1^2 + 0^2 ]
      = 1 - [ 0 + 1 + 0 ]
      = 1 - 1
      = 0.00

0となりました。きれいに分類できている証拠ですね。決定木のFeature ImportanceはこのGiniを用いて算出されているようです。参考文献によると

とありました。難しいですが、要は最後の式だけ見ればなんとなくわかります。分母は前ノードにおけるImpurity Reductionの総和であり、分子は対象の特徴量 $j$ による分岐ノードでのImpurity Reductionの総和となっています。

つまり、対象の特徴量が木全体においてどれだけGini不純度の減少に寄与できたかという指標でFeature Importanceが算出されているということです。

ということはです。分岐点を多く作りやすい変数の方が相対的にFeature Importanceが大きくなるのは直感的ですよね。単純に考えるとカテゴリカル変数よりも連続値変数の方がFeature Importanceが相対的に高まってしまうということです。さらに木を深めることで多くの分岐点が生成されるのであればその効果は莫大です。

実際Feature ImportanceにはCardinalityが密接に関係します。次にCardinalityについてみてみます。

Cardinality

みんな大好きKaggleにおいて次のような質問があった。

タイタニックデータをxgboostでバイナリ分類したのちfeature importanceをみた結果、特徴量の１つであるSexは目的変数と高い相関があるにもかかわらず、比較的低いimportaceが得られたらしい。これに対して気になるコメントがあった。

なにを言っているのかというと。カーディナリティによってfeature importanceにバイアスが生じる。high-cardinalityはhigh-importanceを持つ。これが原因でSexが相対的にlow-importaceになっている。

ここでカーディナリティとは、対象の変数の多様性のこと。つまり性別のようなカテゴリカル変数よりは連続値の変数の方がカーディナリティは相対的に高い。

これはまさに上記のGiniの定義より得られた考えのことだ。よってさきほどのFeature Importanceに対する理解は正しかったということだ。

Information Gain

実は決定木における重要な指標はGini Impurityだけではなく、Information Gain（平均情報量）というものが別であります。

じゃあ、どっちを決定木では使うの？どっちのほうがいいの？という問に対する答えはGini Impurityです。理由は簡単で計算が楽だからです。後者を選んでしまうと対数の計算が必要になります。詳しくは次のリンクへどうぞ

Why are implementations of decision tree algorithms usually binary and what are the advantages of the different impurity metrics?

LIME

じゃあ、どうしたらちゃんとした、まともな、直感的なFeature Importanceが得られるのか。という問に対する答えは僕の知るベストだとSHAPだ。もうSHAPしかない。

上述した理由から決定木におけるFeature Importanceに信憑性はない、結果的に重回帰がやはり好かれている。しかし、分類という点においては決定木やNNには重回帰では残念ながら勝てない。

最高に分類できる状態を保ちつつ、重回帰のように最高の形でFeature Importanceがほしい、という欲求を満たしてくれるのがSHAPだ。LIMEの上位互換なのでやってることはほぼ同じ。

記事の最後になりましたがここでは低次元空間においてLIMEの振る舞いを簡単に実装してSHAP（LIMEの上位互換）のイメージを理解します。下のような非線形データを考えます。

可視化に力をいれたいのでgridでデータを再度作成し、とあるインプット（青）を考えます。このインプットしたいするlimeを求めます。

LIMEもSHAPもローカルなので局所的な空間を考えます。多様体の言葉でいうとチャート、または局所座標近傍です。

距離関数としてL2距離を算出します。実際にロス関数を定義して重みを最適化するのではなく、この距離を線形回帰のライブラリのweightというパラメータに用いて外れ値を考慮した線形モデルを構築します。

前述通り今回はロス関数を定義して計算しているわけではないので厳密なLIMEの実装ではないので注意。あとは線形回帰モデルを作って重みを取得するだけです。

両軸を特徴量として扱っているので線形モデルの直線は可視化できませんが上のマークより、その振る舞いは理解できたのでわないかと思います。ピンクの部分はプラスでグレーの部分はマイナスと分類されています。その時の切片、係数も取得できます。これがlimeです。厳密ではないですがLIMEのやっていることは理解できたかな？と思います。

ちなみにSHAPの凄いところは制約3つめのConsistencyです。これによって対象の特徴量のFIがより重み付されます。これによって決定木におけるFIの相対的なつぶれよりも直感的なFIを得ることができます。

SHAPの距離のところがよくわからない。でわ

Reference

モデル評価　入門

2020年1月17日 / コメントする

こんにちは。kzです。

本日は機械学習のモデルの評価方法についてまとめます。Gistsがかなり重くなってしまったので一発で見れない場合はColabで開くか、Gistsに飛んだのちページを何度か更新してみてください。

分類指標

この記事では分類問題に焦点を当てます。なので回帰におけるMSEとかは話しません。

TP / TN / FP / FN (真陽性 / 真陰性 / 偽陽性 / 偽陰性)
confusion matrix (混同行列)
simple accuracy (正解率)
recall (再現率) (sensitivity)
precision (適合率)
f1 measure (F値)
f1 beta measure (重み付きF値)
threshold (閾値)
ROC / AUC (受信者操作特性 / AUC下部の面積)
MCC (マシューズ相関係数)

これらのベーシックな指標についてまとめます。またF-betaについては少し深入りします。でわやっていきましょう。

分類指標の必要性

もちろん、汎用性がめちゃくちゃ高いものがあればそれでいいんですが残念ながら私は知らないです。。。他にも具体例で考えてみましょう。

たとえば、100枚のラーメンの写真をデータセットとします。モデル $f$ で

二郎系だ
二郎系ではない

という分類をしたとするじゃないですか、Accuracy=99%となったとするじゃないですか、この数値だけ見ればすごく上出来なんですけど仮に100枚中1枚しか二郎系がなかったとしたら $f$ はなにも考えず1を出力するだけで99%とれちゃいますよね。これって $f$ はまともな学習をしていないことになりますよね。つまり、このモデル $f$ よくないですよね。

Confusion Matrix

クラス分類の結果をまとめた表のこと。各要素がTP / TN / FP / FNとなる。ただし、これは二値の場合。しかし多値分類でも同様に作れます。

Pythonで実装する際はパーセンテージも表示させるといいですね。

で、Confusion Matrixの中の指標を一個づつ見ていきます。

Accuracy

もっとも、シンプルかつ、直感的な正答率

Precision

少しの外れを許すが機会損失したくない時に使う

Recall (Sensitivity)

機会損失してでもとにかく正確に当てたい時に使う

PrecisionとRecallの具体例

たとえば全国の二郎系を制覇したいという目的に対してはRecallよりもPrecisionを重視します。なぜならば行ったラーメン店が高い確率で二郎系あっても素通りしてしまっては目標が達成できないからです。

逆にRecallを重視するのはたとえば病気を判別するときです。病気なのに病気ではない、と判断すると大変ですよね

とはいえ、完璧な分類は共に高いのでどうせならこの二つの指標を同時に見たいですよね。つまり。２つの指標を同時に加味して「全体としての良さ」を測りたい時に $F_1$ の登場です。

F1 measure

RecallとPrecisionを同時に考慮する指標です。調和平均という見方もできますが $FP + FN$ が「外れの総数」であることに注意すると外れの平均を考慮した正解率と考えることができます。

しかしです。先程の例のようにどっちかを特別重要視してモデルを評価したい時多いですよね。つまり、recallとprecisionを同じくらい重視して全体の良さを図るのではなくどちらかを相対的に重視したモデルの良さの指標が欲しい時の方がぼくは多い気がします、そこで $F-beta$ の登場です。

F-beta measure

RecallとPrecisionに重みを加えたF measureです。いわば一般化です。

Precisionを重視したいなら ( $F_0 = Precision$ )

$\beta \in (0,1)$

Recallを重視したいなら ( $F_\infty = Recall$ )

$\beta \in (1,\infty)$

$\beta=1$ のときはまさに $F1$ となります。しかしです、この式おかしいと思いませんか？相対的に重みづけするならば一方が $w_1 \in [0,1]$ でもう片方は $w_2 \in [0,1]$ だと思いませんか？つまり

のほうが自然なF-betaですよね？え？ぼくだけ、、？笑。まあそういうことにしてちょっと聞いてください。

van Rijsbergen’s E (effectiveness) function

F-measureは実は別の指標から導出されたものらしいです。起源は次のもの

前述の $F_\beta$ の定義が[Chinchor, 1992]なのに対してこれは[van Rijsbergen, 1979]です。たしかに古い。

代入して変形します。

この関数 $E$ を $R, P \in [0,1]$ でプロットしてみます。

次は $\beta$ を動かしていって $F_\beta$ を見てみます。 $E$ ではないことに注意。

で、このグラフを頭に置いたまま話を戻すと関数 $E(R, P)$ の $\alpha$ はなぜあのような形なのか？気になります。調べますと次の条件を満たすようにされているらしいです。

真実を確かめるために計算していきます。

ここで $\beta=R/P$ なので $R$ を $\beta P^2$ と置き換えて

と、確かに導出されました。しかし、勾配が等しくなるという条件にどういう意味があり、なぜ必要なのかは理解できませんでした。すいません、、

とはいえ、わかったことをまとめると直感的な加重調和平均は $\alpha$ の方だということ。重み $\alpha$ に戻して考えると $\beta$ が $sqrt{2}$ のとき重みが1/3対2/3になり、たしかに直感的に２倍の重みを置いていることになりますね。

ROCとAUC

確率出力に対して最もいい閾値を見つけると同時に、モデルを比較するための指標をグラフ化したものです。

グラフ上の点は特定の閾値を用いてラベリングされたのちの混合行列から算出されたspecificity, sensitivityである。次の動画がかなりわかりやすいので絶対見てください。

https://youtu.be/vP06aMoz4v8

簡単にまとめると、例えばロジスティック回帰を用いた2値分類を考えます。この時に閾値をいくつにするかが問題ですよね。出力の確率と閾値を比較して大きければ1,小さければ0のようにラベルを振る必要があるからです。つまり実数からカテゴリカルに変換する必要性。

ということはです、もちろん閾値と混合行列は一対一対応します。

どの閾値がもっともいい分類をしてくれるのか？という問に答えてくれるのがROCです。

そしていくつかのモデルに対してどのモデルがいいか、つまりどのROCがいいかという問に答えてくれるのがAUCです。

各軸はTPR、FPRとよばれます。言い換えると縦がRecallで横が(1-Sepecificity)です。つまり左上に近づくほど理想的であることがこの定義よりわかります。

そして上の図中の点ですが、これひとつひとつが特定の閾値によって算出された混合行列を用いて計算されたTPR、FPRです。

ここでわかったこととして他クラスのROCはそう単純ではないということです。sklearnに実装はありますがバイナリで実装されているのか閾値をクラス数で分割しているのかわかりませんが、理論上はそう簡単にROCが作れないことは気にかけておいた方がいいと思います。

MCC

各クラスのサイズが非常に異なっていても使用できる評価指標です。

この記事の冒頭で極端な例をあげましたが、実世界の分析においてはよくあることだと思います。ですのでその点ではいい指標だなと思います。

でわコードを貼って終わりにします。

パラメータ空間は位相空間。でわ

「機械学習」カテゴリーアーカイブ

最近の投稿

カテゴリー

Contextual Bandit

LinUCB

LinTS

LogisticTS

実装

References

Recap

因果推論の復習

Inverse Propensity Score Weighting

Pseudo-population

Doubly Robust

実装

References

表記とか

Reward Prediction

Counterfactual model

Inverse Propensity Score Estimator

IPS Utility Estimator

Self-Normalized Estimator

Doubly Robust Estimator

感想

References

Rubin Model

SUTVA

Propensity Score

層別解析

Matching

IPW

実装

References

Conjugate Prior

Improper Prior

Uninformative Prior

Jeffrey’s Prior

Jeffrey’s Priorの意味

僕的まとめ

References

変分とは？

変分ベイズとは？

Mean-Field Approximation

一変数ガウスの例

応用

References

Keywords

Hoeffding’s inequality

UCB

Bayesian UCB

Thompson Sampling

scaled inverse chi-squared Distribution

Code

References

Keywords

Exploration / Exploitation

Multi-Armed Bandit

Advertising Technology

Bayesian A/B Test

Banditを再確認

– Greedy

Boltzmann Softmax

References

前回の復習

Feature Importance

Gini不純度

Cardinality

Information Gain

LIME

Reference

分類指標

分類指標の必要性

Confusion Matrix

Accuracy

Precision

Recall (Sensitivity)

PrecisionとRecallの具体例

F1 measure

F-beta measure

van Rijsbergen’s E (effectiveness) function

$\epsilon$ – Greedy