ホーム » kiwamizamurai の投稿

作者アーカイブ: kiwamizamurai

Contextual Bandit LinUCB LinTS

こんにちは。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 ガウス = ガウス」なのですが、、、、、問題は多次元なんですよね、、、、僕計算めちゃめちゃ嫌いなんですよね、、、、 って感じで、一応サンプリングできます。

LogisticTS

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

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

実装

実際の報酬のアームの分布は次の通りです。
LinUCBの結果
LinTSの結果
パラメータを変化させてRegretも確認
ちょっと疲れました。
ロジスティックはまた今度機会があればやります。

References

Scureなapkを作るためのNative

こんにちは。kiwamizamuraiです。

今回はセキュアなapkの作り方について少しまとめます。apkってなんだ?という方は以下の記事をどうぞ。

そもそもこの記事を書こうと思ったのはJavaが原因なんですよね。

Recap

とりあえず3つの手法があるようです。

Isolate Java Program

重要なClassをサーバー側に置いておくことです。クライアントとは通信によってそのファイルへアクセスさせます。こうすることでデコンパイル自体を不可能することができます。重要なデータについてもサーバー側に置いておくことでデクリプションの可能性もなくなります。

Convert to Native Codes

アンドロイドアプリケーションはJava(Kotlin)が一般的です。しかしJavaはデコンパイルされやすいです。(理由は後述します。)そこでデコンパイルが難しいネイティブを組み込む方法です。ネイティブはデコンパイルしたところでアセンブリになります。画像をもって説明します。
NDKはアプリケーションの一部をネイティブに変換するためのツールです。また、コンパイルされたsoファイル(共有ファイル、windowsの場合は.dll)はJNIによってJavaが扱えるようにされます。また、ネイティブを使うことによって早くなることもメリットの一つになります。

一方でデメリットもあります。一つはファイルが大きくなることです。アンドロイドはさまざまなアーキテクチャ上で動くことができるため、その分互換性のあるファイルを多く持つ必要があります。デコンパイルしたapkのlib内を確認してみます。
上の画像からわかるようにそれぞれのマイクロプロセッサーに対応する機械語のファイルがあることがわかります。

Code Obfuscation

ProGuardなどのツールを用いてコードを難読化する方法です。クラス名やメソッド名が乱数になったりします。以下をしてくれます。
  1. Shrinking – detects and removes unused classes, fields, methods, and attributes.
  2. Optimization – analyzes and optimizes the bytecode of the methods.
  3. Obfuscation – renames the remaining classes, fields, and methods using short meaningless names.
具体的なObfuscationの方法はconfiguration file(build.gradle)に設定するようです。
詳しくはドキュメントを読んでください。

Why is Java easily cracked?

先ほど対策方法でネイティブを埋め込む理由としてJavaはデコンパイルされやすいと言いました。それについて少し深入りします。そもそもJavaのコンパイル、デコンパイルの流れを確認しましょう。
JavaのコードはDEXと呼ばれるバイトコードに変換されます。これはARTで動くためです。最近のアプリケーションはARTで実行されます。一昔前はJavaVMで動いていました。で、問題はこのバイトコードがデコンパイルされやすいことです。デコンパイルの過程も復習します。
復習ですがsmaliファイルはdexのアセンブリでした。このデコンパイルが簡単な理由は次のようです。
簡単に言えば、コンパイルの最適化が単純なことが原因です。メタデータ(クラス名やメソッド名)が付与されることが大きい理由らしいです。で、なぜコンパイルが単純なのか僕なりに調べました。原因はJITです。

Just-In-Time Compiler

JITはJavaのコンパイラです。ネイティブのコンパイルとの違いはタイミングです。これはdexをnative codeに変換します。公式からワークフローを拾ってきました。 よくわからないのでコピペで引用します。
JIT コンパイラは、ART の現行の事前(AOT)コンパイラを補完し、ランタイムのパフォーマンスの改善、ストレージ容量の節約、アプリとシステムのアップデートの高速化を実現します。また、アプリの自動アップデート中のシステム シャットダウンや無線(OTA)アップデート中のアプリの再コンパイルを回避することで、AOT コンパイラのパフォーマンスも改善します。

ここはまだ理解できる気がしないので今後の課題にしておきます。

ちなみに、dexじゃなくて機械語にコンパイルすればいいじゃんということにもなります。GCJというコンパイラが一応ありますが詳しくはわかっておりません。

Reverse Engineering Native Code

Javaが単純なのでNativeで書こう、ということになりました。ではNative Codeは本当に安全なのでしょうか?少しだけ深入りします。
僕の中の回答はIDA Proの商用版で解析することです。Free版だと対応のCPUがありません。。。。まあせっかくなのでJavaでnativeが動くまでについても調べてみます。

ネイティブメソッドが走るには.so内のSystem.loadLibraryかSystem.loadが呼ばれる必要があるようです。そしてその時に先ほど紹介したJNIのJNI_OnLoad()とかが使われるらしいです。じゃあ具体的にNativeってJavaの中でどう書かれているの?と思うのでみてみます。
ちょっと複雑ですが簡単にいうとnativeがあればネイティブメソッドということです。詳しくは参照よりどおぞ。

感想

やはりネイティブ最高、リバエン最高ですね

References

Doubly Robust AIPTW

こんにちは。kiwamizamuraiです。

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

Recap

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

ただ、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

Frida 入門

こんにちは。kzです。

今回はFridaを使ってAndroid用のCTFを解いてみます。
これが今回のapkです。Objectiveのところにあるように、secret stringを見つけて、root検出の回避が目標です。

とりあえず起動してみるとこんな感じ。(エミュレータを使用しています。実機ほしい、、、、)
おー、root detectedですね。これは端末がroot化されているものを検出したということです。たとえばiPhoneのJailbreakも同じようなものです。なぜroot化かするのか?ですがたとえばゲームがいい例です。ゲームでチートってあるじゃないですかあれとかができるようになります。他にもiPhoneの場合だとTweakというアプリが作れたりします。ただ、よくないので行わないでください。

Source Code

Javaのコードをデコンパイルして覗いてみましょう。やり方は前回の記事にあります。こうすることでroot detectedの実装が確認できます。
root判定の部分がありました。
ふむふむ、Successとなるように分岐されるところのソースコードをみてみます。
Base64の文字列5UJiFctbmgbDoLXmpL12mkno8HT4Lv8dlat8FxR2GOc=ともう一つ気になるHex?があります、8d127684cbc37c17616d806cf50473ccこれはなんだろう、、?その後にAESもありますね、ということは逆算してパスフレーズがわかりそうです。ぐぐるとJavaにはCipherというAES/ECB/PKCS7Padding暗号があるようです。

どうやらkeyと平文を引数とする関数のようです。さらにHexの方がKeyであることがソースコードよりわかります。
なのでPythonでちゃちゃっとやります。
パスフレーズがわかりました。イエーい。まあそれはおいておいて、今回はFridaがメインみたいなところありますからね、、

Frida

Fridaとはモバイルアプリケーションの動的解析ツールです。静的解析と違ってソースコードを書き換えてリビルドしてアプリを起動する、といった一連の流れをスキップして動的に解析が可能です。
使い方は少々面倒ですが公式のドキュメントを頑張って読みましょう。 まずはfridaとfrida-serverのインストールです。frida-serverはアンドロイドに埋め込んでfridaを実行できる環境にするためのものです。
では、fridaのドキュメントを参考にしながらbypassのためのコードを書きます。exploit.jsと命名しました。アプリの挙動から考えて起動後最速でHookしたいですね。あ、Hookとはアプリケーション外に定義されたスクリプトを実行する行為のことを言います。

ここではアプリ起動時のroot detectedのスクリプトをHookingにより無効にします。そして入力可能な状況を確立し、先ほどのパスフレーズを入力して目標を達成します。他にもいろいろやり方はあるのでいろんなwrite-upを参考にしてくださいね。

exploit.js

ではHooking用のスクリプトを書きます。このjsのコードをpythonのファイルに埋め込んでpythonのAPIより実行します。
最終的にはこんな感じ
あとはターミナルを開いてfrida-serverを立てたのちにpyを実行するだけです。
起動時
rootをbypassできました。先ほどのパスフレーズを入力してみると
簡単ですね。ちなみに、Pythonでなくてもjsでfrida CLIから実行する場合は

Root Detection

iOSのJailbreak検出の実際の手法をいくつか紹介だけしておきます。

  • System Files Check
  • Symbolic Links Detection
  • Calling Cydia’s URL Scheme
  • Loaded Libraries
おそらくわかりやすいのは一つ目ではないかと思います。これはTweak含め、特定のファイルがあるかないかで検出します。たとえばWinterBoard.appiCleaner.appなどですね。今回の例題だとc.cにあたります。ソースコードを見てみてください。

とはいえ、level1なだけあって簡単ですね。マルウェア解析もやっていきたいです。

References


Counterfactual Machine Learning 入門

こんにちは。kzです。

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

表記とか

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

そこで登場する手法が反事実モデルです。報酬関数を高い精度で得るためにまずはポリシーの分布を近づけてバイアスを消そうというアイデアです。
次の例を考えます。
つまり3種類のアクションに対して、各報酬はバイナリです。まずは単純な評価を行ってみます。
本当にこれでいいのでしょうか?そこで反事実という概念を導入します。

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

Inverse Propensity Score Estimator

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

IPS Utility Estimator

このIPSを用いて次のように改めて定義します。先ほどの指示関数のところが新しいポリシーによる確率分布に変わりました。分母は変わらず傾向スコアです。
こう定義することで以下が得られます。計算
んー、正直僕はまだちゃんと理解できていません。すいません。ただわかったことを改めてまとめますと反事実モデルとIPSを用いることによって新たなアルゴリズム(ポリシー)のシミュレーションができると言うことです。

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

Self-Normalized Estimator

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

Doubly Robust Estimator

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

感想

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

References

UpliftModeling 入門

こんにちは。kzです。
本日はアップリフトモデリングやっていきます。こちらも傾向スコア分析と同様にマーケティングの分野で使われる機械学習的な手法です。ちなみに論文の原本はこちらです。 まず前回の復習を行い、今回のアップリフトモデリングとの違いをはっきりさせましょう。

傾向スコア分析

復習です。傾向スコア自体はバランシングスコアの特殊形として定義される実数でした。その実数を出力する関数(モデル)としてロジスティック回帰を使うのでした。こうして得られた傾向スコアがRubinのSUTVAを満たしてくれるおかげで、「もしTreatmentを受けていたら〜」の代替として扱えるのでした。

今回のアップリフトモデリングは少し異なります。名前の「アップリフト」からわかるように費用対効果を最大化するためのモデリングです。つまり、どういったユーザーをTreatすれば無駄なく効果を最大化できるかをモデリングします。一方で傾向スコア分析は因果効果の推定方法です。

Who is Target ?

上のセクションで述べた「どういったユーザー」について確認します。Rubinのモデルを思い出してください。「もし〜だったら」も含めたユーザーの行動の有無を考えると行動パターンは次の4種類になります。
前回のサイゼリアを例にするとTreatmentはクーポンの配布です。ラベルYがサイゼリアに行ったか、行かなかったかです。アップリフトはこのクーポンの費用対効果を最大化させるための指標です。

見ての通り、図中の白い部分のユーザーを対象にクーポン配布することが最も効果的であることがわかります。

Two-Model Approach

ではそのアップリフトの定義です。
The uplift is defined as the difference between success probabilities in the treatment and control groups.

見ての通りこれは各集合における成功確率の差です。(モデルはそれぞれ定義します。)したがってアップリフトモデルは
として定義されます。ちなみに、参考文献ではアップリフトを差ではなく、割合として定義されていました。おそらくどちらでも構わないと思いますが、この記事では論文にしたがって差として話を進めていきます。(割合にすると理論上は無限まで飛びます。)

また、先ほどの図とこのUMの値を共に考えていただきたいのですが、UMが大きいとはつまり、P(Y=1|X, G=T)が大きく、P(Y=1|X, G=T)が小さいことを意味します。これはまさに図中の白い部分に相当します。逆も同様です。したがってアップリフトが費用対効果最大化の指標として素晴らしいことがわかります。

AUUCとLIFT

AUUCはアップリフトモデリングの指標になります。
The Area Un- der the Uplift Curve (AUUC) can be used as a single number summarizing model performance.
AUCのように面積が広い方が精度が高いことを意味します。このAUUCの導出の際にLIFTと呼ばれる値を用います。AUCがどうやって導出されたかを思い出して考えます。AUCは無数の閾値で与えられたグラフでした。さらにTPRとFPRに対してトレードオフの性質を持っていました。AUUCも同じようなものです。

アップリフト上位のk個のサンプルに対して次がliftになります。
N_TはTreatmentの総数です。またベースラインはアップリフトの上位ではなくランダムで算出した値になります。

ここで考えます。アップリフト上位のデータ群に対するLIFTは右上がりになりますよね。これは先ほどのUMの写像の際の説明からわかります。となると逆も然りです。つまり、アップリフト下位のデータ群はLIFTは右下がりになることが予想できます。したがって最終的にAUUCのグラフはAUCと同様に凸関数のような形になり、その頂上を刺す時のUPLIFTが閾値として最適であると判断できます。(AUUC図のx軸はアップリフトの降順、y軸はLIFT)AUUC自体はbaselineとliftに囲まれた実数になります。

ここまでのTwo-Model ApproachではTreatmentとControlのそれぞれについてmodelを用いてYを予測しました。しかし、二つのmodelを用いることによってパラメータチューニングが難しくなるなどの問題点があります。共変量シフトがあるかもしれないので。そこで単一のモデルのみを用いたClass Variable Transformationについてみてみます。

Class Variable Transformation

とはいえ単一のモデルでどうやってアップリフトを定義するのでしょうか。非常に気になります。文字がかなり出てきますが頑張っていきましょう。

まずは次の変数を導入するところからです。
これを用いて先ほどと同じようにZについて確率を計算してみます。
ここで割り当ては無作為を仮定します。これ重要。したがって
こちらも必要な仮定になります。
また、次も成り立ちます。
すると次が得られます。
お、できました、移項すると
つまり新しく導入したZが1になる確率を予測するモデル一つで先ほどと同じようにアップリフトが算出できるということです。

ちなみにAUUCとLIFTはアップリフトモデリングの指標なのでこちらのアプローチにももちろん使えます。

アルゴリズムの比較

まずはAUUCです。
閾値としてのアップリフトスコアは0.03あたりが良さそうです。ちなみにスコアと各確率は次のような感じ
先ほどのグラフで原点より左が潰れていることがここから確認できます。ではもう一方のアルゴリズムでも確認してみます。
シングルモデルのおかげか綺麗なグラフになっています。ちなみにコンバージョン率のパーセンタイル分布は以下のようになってます。
シングルモデルの方が上位60パーセントにおいてTreatの効果があることがわかります。

長くなりましたが実装貼っておきます。
一般化傾向スコア分析が難しすぎます。でわ

References

Android リバースエンジニアリング 入門

こんにちは。kzです。

前どこかの記事で書いたかもしれませんが、僕はリバエンが大好きです。好きすぎてやばいです。めちゃめちゃ楽しいので皆さんにも紹介します。

UnCrackable App for Android Level 1

リバエンしていきたいと思います。この.apkはCTF的なやつでroot detectedをbypassするのが最終目的になります。しかし今回の記事では.apkからJaveのコードをデコンパイルするまでの内容になります。

apkってなに?という方もいるかと思うので用語などについて説明します。

Introduction to .apk file

アンドロイドのアプリケーションは.apkという拡張子を持ちます。実はこれは.zipと同じでリネームして展開すると開ます。今回の.apkを例にとって開いてみましょう。
見ての通り.pngなどいろいろありますね。これはあくまで一例ですが、いくつか紹介します。
  • AndroidManifest.xml
    • permissionとかpackageとかapiとか
  • META-INF
    • MF アプリのハッシュ値
    • RSA アプリの証明書
    • SF: list of resources and the SHA-1 digest of the corresponding lines in the MANIFEST.MF file
  • classes.dex
    • コンパイルされたJava(Kotlin)のDalvik bytecode(プログラムの部分)
  • res
    • 画像とかのリソース
  • assets
    • マルウェア系が組み込まれやすいところ
  • lib
    • nativeライブラリ
  • .smali
    • .dexのアセンブリ
僕もまだよくわかってないところが多いですがとりあえず、.xmlとclasses.dexくらいだけまず気にかけておけばいいです。ちなみに.smaliはこんな感じ

From .apk To .dex

上では.apkを.zipにリネームしてから開く方法を紹介しましたが実はこれよくないです。なぜならば一部がバイナリ エンコードされています。そこで専用のツールを使って.apkをdecompileして.dexを取得する方法を紹介します。
apktoolというものを使います。これを使えば.apkを展開できます。結果的に上で紹介したAndroidManifest.xmlなどが見れます。
上のどちらかのコマンドで.apkを展開できます。

これで展開したので.smaliを直接書き換えてから.apkを新しくリビルドする作戦でもいいですが、初心者には少しきついのでとりあえずここではJavaのソースコードまでコンパイルする作戦でいきます。ソースコードが見れれば振る舞いが理解しやすいですしね。

そこで.dexをJavaに変換するツールが必要になります。

From .dex To Java (decompiled)

dex2jarというものをつかいます。 どちらも一応同じものですが
  • d2j_invoke.sh
  • d2j-dex2jar.sh
をchmod +xで実行可能にします。そしてdex2jar-2.0/d2j-dex2jar.shを実行するだけです。一連の流れをまとめますと
出力される.jarファイルはclasses-dex2jar.jarです。ちなみに.apkから.jarまで一気にやるパターンは試してません。

See Decompiled Java Code

あとはJD-GUIを使えばソースコードが見れます。
僕はmacなのでmac版をインストールして上で作ったclasses-dex2jar.jarを開けば
いい感じです。

Resign signature

デコンパイルした.apkをEmulatorでも実機でもどちらでもインストールしようとすると
Failure [INSTALL_PARSE_FAILED_UNEXPECTED_EXCEPTION]

とエラーが出る場合が多いです。そんな時はsignature(certification)が潰れてるので再発行します。その前にリビルド
からの
これでインストールできます。adb系のコマンドはいろいろありますね。
とりあえず今回はここまでにします。リバエンかfridaかどっちが好きですか?

References

傾向スコアとは

こんにちは。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

2つ目の手法はマッチングです。といっても層別も層別マッチングなんですけど、、、、まあ置いておいて、、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になります。
具体的には上のようにすることでバイアスを修正しつつ、ルービンの難題であった『〜だったら』の時の不偏推定量となることが次のリンクよりわかります。

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

実装

使うデータはこんな感じです。リンク先のデータを使わせていただきました。そこではIPWのみの実装になっていたので今回紹介した、層別とキャリパーで比較してみようと思います。
20代、30代の男性にバイアスを載せました。詳しくはコードを見て下さい。結果としてはIPWが最もいい精度でした。
アップリフトモデリングやります。でわ

References

事前分布に深入りする

こんにちは。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の意味

さて、これを使う意味ですが個人的には2つあると思っています。
  • リパラメタライゼーションによる新しいモデル構築が容易な点
  • posteriorとのKLを最大ができる点
まず、一つ目は対象のパラメータに対して別のモデルを考える時にヤコビをかけるだけで済むのがいい点の一つだと思います。

そして二つ目、こちらが各だと思っています。Jeffreyを用いることでそのposteriorとのKLを最大化させることができます(データが十分多い時)。これによってposteriorはpriorには極力影響されない一方で、最大限にデータの影響のみを受けた分布になります。つまり、データをはっきりと表現していることになります。
実はこの話はBernardo reference priorというものと関係があるようです。そのパラメータ\thetaが一変数という条件がJeffrey Priorと一致するようです。

こういう意味でJeffrey priorはuninformativeと言われているようです。ついでにパラメータをいじった事後分布の結果を見てみましょう。
5種類の事前分布に対する事後分布の変化の図です。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がいいなと思いました。ここで、考慮するものとはたとえばデータのタイプであったり、物理的な何かであったり詳しいことは僕にはわかりませんが事前情報というよりは制約的な形で考慮するものなんだと思います。たとえば、画像処理における事前分布だと以下のようなものがあります。 そしてこのJeffrey Priorですが改めてまとめますと、これベルナドのrerefence priorの単変量バージョンに相当します。そしてこれはフィッシャー情報量から導出されます。これはつまり今あるデータから事前分布を構築するということを意味します。したがってよく使われる直感、inductive biasというべきでしょうか、の影響を極限まで希薄した事前分布を意味します。また、無情報事前分布と言われている理由はデータが十分に大きい場合、事後分布とのKLを最大化させるためです。この証明は参考文献にあります。最終的には場合分けで解が得られていました。

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

References

Variational Bayes 入門

こんにちは。kzです。

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

変分とは?

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

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

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

変分ベイズとは?

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

ではもういきなりですが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