カシミアのニット

カシミヤのニット

日々のメモです

Argo Workflowをローカル環境で使ってみる

Argo について

github.com

Argoはコンテナベースのワークフローエンジンで,ワークフローの各ステップをコンテナとして実装することを可能にします.

つまり,各ステップはdockerのイメージを使用して実行されます.

また,ワークフローはCustom Resource Definitionで定義します.

そのため,kubenetesのマニフェスト管理と同様にhelmなどを用いてワークフロー自体を管理することができます.

GoogleGithub,PFNなど世界でも有数の企業がArgoを使用しています.

f:id:lapis_zero09:20190303011345p:plain
https://github.com/argoproj/argo

Argo公式ブログがより詳しいです.

Introducing Argo — A Container-Native Workflow Engine for Kubernetes

Argoのインストール

Argoを導入するための下準備

ここではminikubeを使って,kubenetesのクラスタをローカルに構築します.

minikubeを使うことでGoogle Kubenetes Engineなどを使うことなく無料でkubenetesクラスタを構築できます.

手元で試したいときに非常に便利ですね.

minikubeのインストールはHomebrewで一発完了です.

brew cask install minikube
minikube version

minikubeを起動してみましょう.

minikube start

初めての起動が正常にいけば以下のような表示がえられるでしょう.

f:id:lapis_zero09:20190228163904p:plain
minikube start

次にkubectlでコンテキストを確認してkubectlがminikubeに向いていることを確認できたらminikubeの導入は完了です.

kubectl config current-context

f:id:lapis_zero09:20190228164041p:plain
kubectl config current-context の結果

Argoのインストール

これでArgoをインストールする準備は整いました.

まず,はじめにArgo CLIをインストールします.

brew install argoproj/tap/argo
argo version

f:id:lapis_zero09:20190228165031p:plain
argo versionの結果

次に,Namespaceを作り,argoのmanifestを反映します.

kubectl create ns argo
kubectl apply -n argo -f https://raw.githubusercontent.com/argoproj/argo/v2.2.1/manifests/install.yaml

f:id:lapis_zero09:20190302235212p:plain
argoのmanifestを反映したところ

次に default サービスアカウントに権限を付与します. これをしないと,Argo Workflowの一部の機能(ファイル出力,secretへのアクセスなど)が使えません.

kubectl create rolebinding default-admin --clusterrole=admin --serviceaccount=default:default

ここまでくれば導入完了も同然です. port forwardをしてargo UIにアクセスしてみましょう.

kubectl -n argo port-forward deployment/argo-ui 8001:8001

http://localhost:8001/workflows

f:id:lapis_zero09:20190303001148p:plain
argo UI

では,実際にworkflowを実行してみましょう.

argo submit --watch https://raw.githubusercontent.com/argoproj/argo/master/examples/hello-world.yaml
apiVersion: argoproj.io/v1alpha1
kind: Workflow
metadata:
  generateName: hello-world-
spec:
  entrypoint: whalesay
  templates:
  - name: whalesay
    container:
      image: docker/whalesay:latest
      command: [cowsay]
      args: ["hello world"]

このworkflowでは dockerのwhalesayイメージを指定し,cowsayコマンドを実行します.

watchオプションをつけることで実行状況をterminal上で監視できます.

f:id:lapis_zero09:20190303002039p:plain
argo submit watchの表示

workflowは一つのpodとして実行されるので argo list または kubectl get po で一覧を取得することができます.

f:id:lapis_zero09:20190303002652p:plain
submitしたworkflow一覧

実行したworkflowはもちろんargo UIからも確認できます.

f:id:lapis_zero09:20190303002237p:plain
argo UIでworkflowの確認

workflowをクリックすることで詳細を確認できます.

f:id:lapis_zero09:20190303002801p:plain
workflow詳細

YAML からsubmitしたworkflow,logからworkflowからの標準出力を確認することができます.

f:id:lapis_zero09:20190303003057p:plain
workflowのlog

次は別のworkflowの例です.

argo submit --watch https://raw.githubusercontent.com/argoproj/argo/master/examples/coinflip-recursive.yaml
apiVersion: argoproj.io/v1alpha1
kind: Workflow
metadata:
  generateName: coinflip-recursive-
spec:
  entrypoint: coinflip
  templates:
  - name: coinflip
    steps:
    - - name: flip-coin
        template: flip-coin
    - - name: heads
        template: heads
        when: "{{steps.flip-coin.outputs.result}} == heads"
      - name: tails
        template: coinflip
        when: "{{steps.flip-coin.outputs.result}} == tails"

  - name: flip-coin
    script:
      image: python:alpine3.6
      command: [python]
      source: |
        import random
        result = "heads" if random.randint(0,1) == 0 else "tails"
        print(result)

  - name: heads
    container:
      image: alpine:3.6
      command: [sh, -c]
      args: ["echo \"it was heads\""]

このworkflowでは,前回ステップの結果をもとに次のステップを変更しています.

また,templateを定義し,再利用することができます.

初めのステップでpythonのdockerイメージからrandintを実行します.

その結果を次のステップの when で受け取り,条件によってはもう一度同じテンプレートからステップを実行します.

これによって再帰的にステップを実行することも可能です.

f:id:lapis_zero09:20190303005447p:plain
再帰workflow

今回はローカルにインストールしたminukubeにArgoをインストールし,2つの例を実行しました.

Argoでできることはここで紹介したことにとどまりません.

次回以降,豊富なworkflow例と共にcookbookを作成・紹介していきたいと思っているので引き続きよろしくお願いします.

参考

書きました

新人ブログリレーということ以下の記事を書きました.

 

あなたの生産性を向上させるJupyter notebook Tips | リクルートテクノロジーズ メンバーズブログ

 

他の同期は入社してからの業務を中心に記事を書いています.

私の記事は自分が持っているjupyterについての知識を体系化しました.

 

お役に立てば幸いです!

GW開発合宿でGoのレコメンドエンジンを作った

今週のお題ゴールデンウィーク2018」

開発合宿

GWを利用して同期の有志5人で開発合宿をしました.

場所は千葉県の東浪見駅から徒歩20分ほどの民泊で海まで徒歩5分という感じです.

東浪見駅はめちゃめちゃ自然あふれる場所で最寄りのコンビニも数キロ先という都会の喧騒とはかけ離れた場所でした.

f:id:lapis_zero09:20180506162005j:plain
東浪見

f:id:lapis_zero09:20180506162103j:plain
民泊

開発は個人で勝手にテーマを決めてやっていくスタイルです.

GAEやElixir, CTFなど各々がやりたいことをやりました.

僕は今更ながらGo入門してました.

やったこと

作ったのがこれです.

github.com

ユーザ/アイテムベースの協調フィルタリングを行うことができる簡素なレコメンドシステムです.

具体的には,ユーザのアイテム評価データからアイテム評価行列を作ってユーザ/アイテムの類似度を計算し, 類似のユーザ/アイテムを取得可能というものです.

f:id:lapis_zero09:20180506170525p:plain

類似度関数は以下をサポートしています.

普段は機械学習周りをやっててPythonなどリッチな言語を使ってライブラリで済んでしまうことも多いのでこういうのもいいです.

疲れ時は海に散歩に行ったり,アコギ持ってきてる人がいてみんなで歌ったり,終始酒を飲みながら開発をして最高でした.

github.com

Notionが便利すぎてぜひオススメしたい話

f:id:lapis_zero09:20180422130631p:plain



こんにちは.最近は,入社して社会になってます.

Notion*1

自分の考えをまとめたり,チームでの共有事項をまとめたりするためのツールはたくさんあります.

Google DocsGithub Wiki,TrelloやDropbox Paper,どれも素晴らしいツールですが,色々導入しすぎて「今回の案件にはどれが最適なのか...」ってなる時ありませんか?

それを解決してくれるのがNotionです.

Notionとは All-in-one workspace を謳った上記ツールの機能を網羅してくれるツールです.

www.notion.so

概要

Notionは,web,Desktop,iOSなど各プラットフォームにも対応しており,電車での移動中などでも簡単に編集・確認ができます.

コードを含めたドキュメントはもちろん,kanbanや表,カレンダーを作成することができます.

これらの要素は,インラインでページ中に作成することもでき,また,一つの独立したページとして作ることも可能です.

非常に理に適った動きをしてくれて,ストレスフリーな設計となっています.



https://www.notion.so/front/use-cases/use-case-screenshot-note.gif



数式もTeX形式で書くことができて簡単です.

f:id:lapis_zero09:20180422145941p:plain


kanban機能もあります.

https://www.notion.so/front/use-cases/use-case-screenshot-task.gif




表やカレンダーも作成することができます.

https://www.notion.so/front/use-cases/use-case-screenshot-database.gif



作成したドキュメントやkanban,表・カレンダーは簡単に構造化して管理することができます.

https://www.notion.so/front/use-cases/use-case-screenshot-wiki.gif



もちろん,権限があれば複数人での編集も可能です.





論文のまとめと実装の管理の例*2

↓↓↓論文のまとめと実装の管理の例を公開してみたのでぜひ触ってみてください↓↓↓

https://www.notion.so/lapiszero09/Home-b322ed09f90e405e9a9d904709fb37fb

↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

上のリンクからnotionのデモを触れるので,「論文まとめ」や「実装」などをクリックしてみてください.



f:id:lapis_zero09:20180422151730p:plain

An Adaptive Version of the Boost by Majority Algorithm

An Adaptive Version of the Boost by Majority Algorithm

Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

link.springer.com

実装はこちらです.

github.com

以前ゼミで,Introduction to ensemble methods for beginners Introduction to ensemble methods for beginners

というタイトルで以下のようなアンサンブルについての概要を簡単にまとめた資料を発表しました(突貫工事なのでまとまりがないのは目を瞑っていただきたく).

その中でも,History of Boosting節のBrownBoost*1について今回は紹介します.

BrownBoost

本論文では,AdaBoostがノイズに弱い*2という特徴を考慮したBrownBoostを提案しています.

本論文以外でも,ノイズ耐性を持つBoostingは提案されています*3

しかし,PACの枠組みの中で定義されている正式なブースティング特性はありません.

そこで,FreundはBoosting-By-Majorityを適用することでノイズ耐性を受け継いだPACに基づいたBrownBoostを提案しました.

Boosting-By-Majority*4

Boosting-By-Majority(以下,BBM)は,Freundによって提案された最初のブースティングアルゴリズムです.

また,ノイズ耐性*5があります.

しかし,BBMを使用するためには,基本学習器の誤差限界パラメータとして与える必要があり,実用には向きません.

BBMとBrownBoostの関係

このパラメータを削除した手法がBrownBoostです.

具体的には,パラメータを削除し,候補モデルの誤差に適応的に最終的なアンサンブルを生成します.

BrownBoostでは,候補モデルの数を指定するパラメータはなく,代わりに cというパラメータがあります.

このパラメータによって”残り時間”が決められます.

この”残り時間”は,BrownBoostのイテレーションに関するパラメータです.

また,候補モデルが訓練された時,”残り時間”と分類マージンに基づいてそのモデルの重みが決まります.

そして,その重みに基づいて”残り時間”は減算されます.

この分類マージンにより,BBMやBrownBoostでは各インスタンスを正解するように候補モデルを訓練することができます.

一方で,各候補モデルの正答率が低いインスタンスに対しては,負のマージンが割り当てられ,そのようなインスタンスはノイズであると判断されます.

これがBBM,BrownBoostがノイズに強い所以です.



BrownBoostのイテレーションは,”残り時間”が収束するまで続きます.

候補モデルの重み付き誤差によって決まるのでアルゴリズムの実行時間はBBMに比べて非常に長くなり得ます.

この問題に関しては,候補モデルの誤差を0.5に近づけた時のアンサンブルの振る舞いを考えることで答えることが可能です.

モデルの誤差を(1/2 - \delta)とし,時間 tにおけるアンサンブルの出力を \sum h(x)と表します.

この時,時間を t=\delta ^2 iをすると,BrownBoostの収束後の時間は \deltaとは無関係の定数となり,これにより下式で表現される”位置”を定義します.

\begin{align} r_\delta(t) = \delta \sum^{\lceil t/\delta^2 \rceil}h(x) \end{align}

モデルの誤差を0.5に近づけることが前提であり,この時の”位置r_\delta(t)”は下式で得られる平均 \mu(t)と分散 \sigma ^2 (t)によって特徴付けられるブラウン運動による連続時間確率過程r(t)に近づきます.

{
\begin{align}
\mu(t) = \int_{0}^{t} \frac{1}{\gamma(s)}ds
\end{align}
}
{
\begin{align}
\sigma^{2}(t) = t
\end{align}
}

ここで, 1/2 - \gamma(t)は時刻tにおけるモデルhの重み付き誤差を表します.

ここまでで誤差を0.5に近づけた時のアンサンブルの振る舞いがわかりました.

ここからはBBMで定義される重みの限界を考えます.

BBMの重み関数は二項分布であり,以下で表します.

\begin{align} \alpha^i_r = {}_{k_\delta - i - 1} C _{\lfloor k_\delta/2 \rfloor - 2} \biggl(\frac{1}{2} + \delta \biggr)^{\lfloor k_\delta/2 \rfloor - r} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta/2 \rfloor - i - 1 + r} \end{align}

ここで, k_\deltaイテレーションの回数で,iは現在のイテレーション番号です.

rはこれまでの正しい予測の数です.

前述のr_\deltatの定義から誤差を0.5に近づけると\alpha^{i}_{r}の限界を得ることができます.

\begin{align} \alpha(t,r) = \exp \biggl(-\frac{(r(t)+c-t)^2}{c-t} \biggr) \end{align}

ここで, c = \lim_{\delta \to 0} \delta ^2 k_\deltaです.

同様に,誤差限界は下式のように表せます.

\begin{align} \beta^i_r = \sum^{\lfloor k_\delta/2 \rfloor - r} {}_{k_\delta - i} C _{j} \biggl(\frac{1}{2} + \delta \biggr)^{j} \biggl(\frac{1}{2} - \delta \biggr)^{\lfloor k_\delta \rfloor - i - j} \end{align}
\begin{align} \beta(t,r) = \frac{1}{2}\biggl(1 - erf \biggl(\frac{r(t)+c-t}{\sqrt{c-t}} \biggr) \biggr) \end{align}

ここで, erf(\cdot)は誤差関数であり,下式で表現されます.

\begin{align} erf(a) = \frac{2}{\pi}\int_{0}^{a} \exp(-x^2)dx \end{align}

以上のようにtr(t)\alpha(t,r),及び,\beta(t,r)の定義が与えられると、BBMアルゴリズムを連続時間領域に変換できるようになります.

この領域では,BBMを実行する代わりに,候補モデルの誤差が0.5である分布に対応するtの値を定義する微分方程式を解くことで近似解を得ることができます.

また,BrownBoostの損失関数は,\beta(t,r)に対応した形になり,同様に近似によって多項式時間での収束が可能となります.

ブラウン運動のシュミレーション

ブラウン運動は,連続時間ランダムウォークをモデル化したものです.

2次元ブラウン運動のシュミレーションを行い,その結果を可視化しました.

f:id:lapis_zero09:20180330014413p:plain
2次元ブラウン運動のシュミレーション

実装はここにあるので,遊んでみてください.

BrownBoost/brownian_motion.ipynb at master · lapis-zero09/BrownBoost · GitHub

BrownBoostの実装

BrownBoostのアルゴリズムは以下に示すとおりです.

f:id:lapis_zero09:20180330014919p:plain

アルゴリズム中ステップ3は論文に示されているとおり,Newton-Raphson法により解を導いています.

実装はこちらです.

github.com

実験

ここに簡単な実験を示しています.

BrownBoost/brownboost.ipynb at master · lapis-zero09/BrownBoost · GitHub

感想など

尻すぼみ感が否めませんが,明日も朝から研修なので許して.

後ほど追加実験をします.

*1:Freund, Y.: An adaptive version of the boost by majority algorithm, Machine Learning, vol. 43, no. 3, pp. 293‒318, 2001.

*2:Dietterich, T. G.: An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40:2, 139–158.

*3:Friedman, J., Hastie, T., Tibshirani, R.: Additive logistic regression: a statistical view of boosting. Ann. Statist. 28 (2000), no. 2, pp. 337-407.

*4:Freund, Y.: Boosting aweaklearning algorithm by majority. Information and Computation, 121:2, 256–285.

*5:J. a. Aslam and S. E. Decatur, General bounds on statistical query learning and PAC learning with noise via hypothesis boosting, Proc. 1993 IEEE 34th Annu. Found. Comput. Sci., vol. 118, pp. 85‒118, 1993.

pythonのlambda式をtex形式に変換する

pythonのlambda式をtexに変換する

pythonで書いた数式と本来の数式を比較して正しいか見るのが意外とめんどくさいです.

sympy.simplifyとsympy.latexを使うとsympyで定義した数式をtex形式に変換することができます.

これらを利用してlambda式を与えるとtex表記を返してくれる関数が以下です.

gist.github.com

Model Compression

Model Compression

Bucilua, C., Caruana, R. and Niculescu-Mizil, A.: Model Compression, Proc. ACM SIGKDD, pp. 535–541 (2006).

https://dl.acm.org/citation.cfm?id=1150464

モデル圧縮

この論文はHintonらによるDistilling the Knowledge in a Neural Network*1の先駆けとなった論文です.

Once the cumbersome model has been trained, we can then use a different kind of training, which we call “distillation” to transfer the knowledge from the cumbersome model to a small model that is more suitable for deployment. A version of this strategy has already been pioneered by Rich Caruana and his collaborators.

[1503.02531] Distilling the Knowledge in a Neural Network

Hintonらの"distillation"では,soft targetと呼ばれる教師モデルが各正解クラスに対して出力した確率分布を入力として与えます.

これにより,教師モデルが相対的に間違った答えを導き出した場合でも,生徒モデルは教師モデルの確率という情報を新たに得ることで正解できるように訓練できる場合があります.

この時,教師モデルに含まれる基本モデルの予測分布の算術または幾何平均をsoft targetとしています.

一方,Caruanaらの提案では,教師モデルによって予測したone-hotなクラスラベルを正解ラベルとして生徒モデルを学習します.

これだけでは,生徒モデルは元の訓練データで訓練できるモデルよりもいいパフォーマンスを発揮できません.

教師モデルの性能を維持したまま元の訓練データで訓練できる軽量なモデルよりも優れたモデルを得るために擬似データを使用しました.

Model Compression*2

Caruanaらは,同論文でMUNGEと呼ばれる擬似データ生成手法を提案し,訓練データから大量のラベルなし擬似データを生成し訓練に用いました.

ラベルなし擬似データは,教師モデルによってラベル付けし,生徒モデルの訓練に利用します.

MUNGEのアルゴリズムは以下の通りです.

f:id:lapis_zero09:20180322174833p:plain
Pseudo code of MUNGE

MUNGEは見ての通り非常にシンプルな擬似データ生成手法です.

まず,訓練データ内のインスタンス {e}について,最近傍を発見します.

次に,確率パラメータに基づいて最近傍とインスタンス {e}から得られる正規分布からランダムに値を得ます.

これを各インスタンスに対し,複数回行うことで任意数の擬似データを得ることができます.

MUNGEの実装はこちらです.

github.com

Caruanaらは,MUNGEを用いたモデル圧縮によって教師モデルと同等の精度を持ち,教師モデルよりも高速かつ軽量な生徒モデルを得ています.

f:id:lapis_zero09:20180322175855p:plain

簡単な実験

irisデータを使って擬似データ生成アルゴリズムMUNGEの簡単な実験を行います.

詳細はこちらです.

github.com

正規化したirisデータは以下のようにプロットできます.

f:id:lapis_zero09:20180322215209p:plain
iris with normalization

このデータに対してMUNGEで擬似データを生成した結果が以下です.

f:id:lapis_zero09:20180322215304p:plain
p = 0.5, s = 10.0

良さそうですね.

しかし,確率パラメータを低くすると擬似データ数が多くなった場合,過学習する可能性が高くなります.

f:id:lapis_zero09:20180322220200p:plain
p = 0.8, s = .01

導出アルゴリズムからわかるように分散パラメータが小さすぎると明らかにおかしいデータが出来上がります.

f:id:lapis_zero09:20180322215543p:plain
p = 0.8, s = 1.0

一見良さそうですが,データが密集しすぎていて経験的にこのような場合は過学習することがあります.

f:id:lapis_zero09:20180322215624p:plain
p = 0.8, s = 10.0

いい感じです.

f:id:lapis_zero09:20180322215709p:plain
p = 0.8, s = 100.0

少し規則的に並び過ぎて人工データ感が否めません.

感想など

MUNGEはとてもシンプルなアルゴリズムであるが,データの特徴をよく捉えた擬似データを生成できます.

しかし,クラスの決定境界を意識して擬似データを生成しているわけではありません.

よって,上述のirisデータのプロットにおける青と緑のように境界面で接地したデータを分離しづらくなってしまいます.

あくまでも,モデル圧縮の文脈における擬似データ生成アルゴリズムなので教師モデルの特徴を活かしてこの辺りを改善したいですね.

*1:Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. In In Deep Learning and Representation Learning Workshop, NIPS, 2014.

*2:Bucilua, C., Caruana, R. and Niculescu-Mizil, A.: Model Compression, Proc. ACM SIGKDD, pp. 535–541 (2006).

Selective Ensemble under Regularization Framework

Selective Ensemble under Regularization Framework

Li, N. and Zhou, Z.-H.: Selective Ensemble under Regularization Framework, Proc. MCS, pp. 293–303 (2009).

link.springer.com

実装はここに置いています.

github.com

アンサンブル枝刈り

アンサンブル枝刈りはensemble pruningとも呼ばれます.

アンサンブル枝刈りは訓練された複数の基本モデルが与えられた上で,その全てを結合するのではなく,部分集合を選択することです.

アンサンブル枝刈りにより,より小さなサイズのアンサンブルでより良い汎化性能を得ることが期待されます.

Tsoumakasらは,アンサンブル枝刈りを順序付けに基づく枝刈り,クラスタリングに基づく枝刈り,最適化に基づく枝刈りの3つのカテゴリーに分類しました*1

この詳しい話については後ほど別の記事にしようと思ってます.

今回はその中でも最適化に基づく枝刈りに属するRSE(regularized selective ensemble)についてです.

RSE(regularized selective ensemble)*2

RSEはLiとZhouによって提案されたアンサンブル枝刈りをQP問題へと帰着させる手法です.

この手法の良いところは,従来のアンサンブル枝刈り手法よりもアンサンブルに含まれる基本モデルの数が少ないにもかかわらず,その性能がいいという点です.

また,正則化項にグラフラプラシアン正則化を用いており,半教師あり学習の場面でも使用することができます.

それでは詳しく見ていきましょう.

{M}個のモデル{\{h_1, \ldots, h_M\}}に対し,アンサンブル結合重みベクトルを{\boldsymbol{w} = [w_1, \ldots, w_M]^{\mathrm{T}}}と定義します.

この時,{w_i \geq 0} かつ {\sum_{i=1}^{M}w_i = 1}です.

RSEは,以下の正則化リスク関数を最小化することにより{\boldsymbol{w}}を決定します.

\begin{align} R(\boldsymbol{w}) = \lambda V(\boldsymbol{w}) + \Omega(\boldsymbol{w}) \end{align}

ここで,{V(\boldsymbol{w})}は訓練データ{D = {(\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_N, y_N)}}に対する誤分類の経験損失で, {\Omega(\boldsymbol{w})}正則化項であり, {\lambda}{V(\boldsymbol{w})}{\Omega(\boldsymbol{w})}の最小化における正則化パラメータを表す.

ヒンジ損失とグラフラプラシアン正則化項をそれぞれ経験損失と正則化として用いることにより,問題は下式で定式化されます.

\begin{align} & \underset{\boldsymbol{w}}{\text{minimize}} & & \boldsymbol{w}^{\mathrm{T}}{\boldsymbol{PLP}^{\mathrm{T}}}\boldsymbol{w} + \lambda\sum_{i=1}^N {\text{maximize}}(0, 1 - y_i\boldsymbol{p}_i^{\mathrm{T}}\boldsymbol{w})\\ & \text{subject to} & & \boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \; \boldsymbol{w} \geq \boldsymbol{0}. \label{eq:hinge_laplacian} \end{align}

ここで,{\boldsymbol{p}_i = (h_1(\boldsymbol{x}_i), \ldots, h_M(\boldsymbol{x}_i))^{\mathrm{T}}}は訓練データ{\boldsymbol{x}_i}に対する個々のモデルの予測を表し, {\boldsymbol{P} \in {{-1, +1}}^{M \times N}}は全訓練データに対する全モデルの予測を集めた予測行列で, {\boldsymbol{P}_{ij} = h_i(\boldsymbol{x}_j)}です.

{\boldsymbol{L}}は訓練データの近傍グラフ{G}の正規化グラフラプラシアンです.

グラフラプラシアンの詳細については,長くなってしまうので件の論文や他文献に譲ります.

行列{G}の重み付け隣接行列を{\boldsymbol{W}}で表し,{\boldsymbol{D}}{D_{ii} = \sum_{j=1}^N W_{ij}}の対角行列です.

この時,{\boldsymbol{L} = \boldsymbol{D}^{-\frac{1}{2}}(\boldsymbol{D} - \boldsymbol{W})\boldsymbol{D}^{-\frac{1}{2}}}となります.

上式の{maximize(\cdot)}は滑らかではので,スラック変数{{\boldsymbol{\xi}} = (\xi_1, \ldots, \xi_m)^{\mathrm{T}}}を導入することにより,上式は下式で書き表せます.

\begin{align} & \underset{\boldsymbol{w}}{\text{minimize}} & & \boldsymbol{w}^{\mathrm{T}}{\boldsymbol{PLP}^{\mathrm{T}}}\boldsymbol{w} + \lambda\boldsymbol{1}^{\mathrm{T}}\boldsymbol{\xi} \\ & \text{subject to} & & y_i\boldsymbol{p}_i^{\mathrm{T}}\boldsymbol{w} + \xi_i \leq 1, \; (\forall i = 1, \ldots, N) \\ & & & \boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \; \boldsymbol{w} \geq \boldsymbol{0}, \; \boldsymbol{\xi} \geq \boldsymbol{0}. \label{eq:hinge_laplacian_slack} \end{align}

この時,上式は標準的なQP問題となり,従来の最適化パッケージを用いて,効率的に解くことができます.

また,{\boldsymbol{1}^{\mathrm{T}}\boldsymbol{w} = 1, \boldsymbol{w} \geq \boldsymbol{0}}という制約は、スパース誘導性を持つ{l_1}ノルム制約となり,重み{\boldsymbol{w}}のいくつかの要素を強制的にゼロにします.

この特徴により,従来のアンサンブル枝刈り手法よりもアンサンブルに含まれる基本モデルの数が少ないにもかかわらず,それなりの性能を出すことができます.

また,簡単な例を代入すればわかりやすいのですが,正則化 {\boldsymbol{PLP}}の部分が似ているデータに対して違うラベルを割り当てると正則化するという振る舞いをします.

導出された結合重みベクトル{\boldsymbol{w}}を用いて,下式のようにアンサンブルの予測を得ます.

\begin{align} H(\boldsymbol{x}) = \sum_{w_i > 0}w_ih_i(\boldsymbol{x}) \quad\text{(RSE-w)} \label{eq:rse-w} \end{align}

また,下式のように{\boldsymbol{w}}の要素がゼロでない候補モデルの投票により予測を決定する選択的アンサンブルも提案されています.

\begin{align} H(\boldsymbol{x}) = \sum_{w_i > 0}h_i(\boldsymbol{x}) \qquad\text{(RSE)} \label{eq:rse} \end{align}

少なくともerrorに関してはなかなかいい結果です.

f:id:lapis_zero09:20180321163932p:plain

errorだけの比較なのは,あまりいい感じはしませんが,アンサンブルの目指す所的にいいのかな

実装

実装はここに置いています.

github.com

最適化を行う前に,グラフラプラシアンに用いる行列{\boldsymbol{W}}を導出する必要があります.

これは,pythonでは遅すぎたのでJavaで実装しています.

しかし,訓練データはnpz形式で保存していたので,pythonでデータを読み込んでpy4j*3で起動したJavaサーバで計算を行っています.

    /**
     * get the matrix W for Laplacian
     * @return w_link filename
     * @throws Exception
     */
    public String[] getKernelLinkMatrix(byte[] data, String fold) throws Exception {
        System.out.println("\t\t[*] Hello from Java!");
        // get the link matrix
        // create java matrix from numpy
        Instances d = createFromPy4j(data);
        Matrix LMat = new Matrix(m_numInst, m_numInst);
        RBFKernel krl = new RBFKernel();
        double g = 0.5 / m_numAttr;
        krl.setGamma(g);
        krl.buildKernel(d);

        System.out.println("\t\t[*] calculating w_link on Java...");
        for (int i = 0; i < m_numInst; i++) {
            for (int j = 0; j <= i; j++) {
                double vt = krl.eval(i, j, d.instance(i));
                LMat.set(i, j, vt);
                LMat.set(j, i, vt);
            }
        }
        d = null;
        krl = null;
        System.out.println("\t\t[-] calc done...");

        return returnFilename(LMat, m_numInst, fold);
}

ラプラシアン行列の計算や重みの最適化はMatlabで行いました.

本件ではpythonよりも速く,また,最適化パッケージであるmosek*4の扱いが簡単だったためです.

mosekは論文でも採用されており,QP問題に関しては最速らしいです.

function Lap = LaplacianMatrix(W)
% compute the laplacian matrix
%
% Input:
%       W: the line matrix
% Output:
%       Lap: the laplacian matrix


D = diag(sum(W,2));
N = D^(-0.5);
Lap = N *(D-W)* N;
function weight = compute_weight(lambda, Y, Prd, Q, dirname);
% compute the weights for the base classifiers
%
% Input:
%       Cfr: the ensemble classifier, which contains multiple base
%       classifiers
% Output:
%       weight: the weights for the base classifiers in the ensemble


% M : set the size of classifiers
% N : set the size of training data
[M, N] = size(Prd)
NumVar = M + N;

% ---- Prepare QP ----
%equal constaint

Aeq = [ones(1,M),zeros(1,NumVar - M)];
beq = 1;
% lower and upper bounds
lb = zeros(NumVar,1);
% Ax <= b
AP = Prd';
for id = 1:N
    AP(id, :) = AP(id, :) * Y(id);
end
AP = -1 .* AP;
A = [ AP, -1 * eye(N) ];
b = -1 * ones(N ,1);

% H
H = zeros(NumVar,NumVar);
H(1:M, 1:M) = Q;
% f
% lambda = 1.0;
f = lambda * [zeros(M,1);ones(N, 1)];

% Optimization Using QP - MOSEK
options = optimset('Display','off','TolFun', 1e-100);
x0 = quadprog(H,f,A,b,Aeq,beq,lb,[],[],options);
weight = x0(1:M);
weight((weight <= 1e-6)) = 0;
filename = sprintf('%sweight/weight_lambda_%d%s',dirname,lambda,'.csv')
disp(filename)
csvwrite(filename,weight);

簡単な実験

Phonemeデータセットに対して,5分割交差検証でRSEを使用しました.

SVM,KNN,Decision Tree,Bagged Decision Trees,Boosted Decision Trees,Boosted Decision Stumpsなどを様々なパラメータで767個のモデルをアンサンブルの候補としました.

このとき最もよかった候補モデルは,XGBoostではなくRandomForestで,mseが0.092937219730941698,f1が0.93484136670163342という値でした.

RSEは,mseが0.0859865470852018,f1が0.93981530924414192という結果だったので良くなっていますね.

best base model RSE
mse 0.0929372197309416 0.93484136670163342
f1 0.0859865470852018 0.93981530924414192

詳細は,

github.com

感想など

グラフラプラシアンを使っている以上うまく適合するデータとそうでないデータはもちろんあると思います.

また,この手法では,アンサンブル候補モデルに対する結合重みを二次計画問題と捉え最適解を導出しますが,候補モデルが一律に似たような性能を示している場合,二次計画問題となり得ず,解くことができません.

{l_1}ノルム制約を使って候補モデルの数をガンガン減らすのはとても理にかなっていると思ったので,回帰とかにも使えると嬉しいですね.

*1:Tsoumakas, G., Partalas, I. and Vlahavas, I.: An En- semble Pruning Primer, SUEMA, pp. 1–13 (2009).

*2:Li, N. and Zhou, Z.-H.: Selective Ensemble under Regularization Framework, Proc. MCS, pp. 293–303 (2009).

*3:https://www.py4j.org/

*4:https://www.mosek.com/

春はなぜか新しいWebページを作りたくなる

春はなぜかWebサイトを作りたくなる

なりません?

僕はなります.

https://www.lapis-zero09.xyz/profile/

https://www.lapis-zero09.xyz/profile/

https://www.lapis-zero09.xyz/profile/

iPhoneで見られることをあまり想定していないものになってしまいました.

デザイン教えて