Transforming Classifier Scores into Accurate Multiclass Probability Estimates

論文読み

Zadrozny and Elkan, “Transforming classifier scores into multiclass probability estimates”, SIGKDD‘02 (http://www.research.ibm.com/people/z/zadrozny/kdd2002-Transf.pdf) を読んだ。なぜ読んだかというと、Scikit-learnのSGDClassifierに関するドキュメント(http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.SGDClassifier.html)で複数のone-vs-restの二値分類器の出力を用いて多クラス分類において各クラスに属する確率を推定する方法として参照されていて興味を持ったため。

この論文では分類問題に置ける各クラスの確率の推定のための二つの手法を提案している。

  • calibrationされた二値分類問題の各クラスへの所属確率の推定値を各データ点に対するスコア（確率とは限らない）から推定
    • Naive BayesやSVMが出力する値は各クラスへの真の所属確率と単調な関係になっているが一致しているわけではない。Isotonic regression（単調増加する入力に対して出力も単調増加するようにフィッティングするノンパラメトリックなモデル）を用いてスコアを所属確率に近づけることによってうまく推定できる。
  • 多クラス分類問題での各クラスの確率を複数の二値分類問題での確率の推定値を用いて計算
    • 複数の二値分類問題をone-vs-restやall-pairsで作成して学習する。ここで学習されたモデルの出力を適当な最適化問題を解くことでP(c | x)を学習する（正直なところ次の行のone-vs-restのケース場合だけわかれば満足だったのでどのような最適化問題を解くかについては書かない）。one-vs-restで二値分類問題を作ったのならばP(c | x)の合計が1になるように正規化すればOK。

RoaringBitmapについて少し勉強した

社内で使用されている高速省メモリなビット集合の実装であるRoaringBitmap (https://github.com/RoaringBitmap/RoaringBitmap)の解説 (https://arxiv.org/pdf/1402.6407.pdf)を読んだ。以下では32bit整数の集合を管理することを前提に話を進める。この実装のアイデアは全体の整数集合を最上位の16bitを共有する216個の整数毎に分割したコンテナとして管理し、各コンテナ内部の要素数に応じて整数集合の管理方法を変更するという点。内部の要素数が4096個以上ならばビット集合で管理し、 それ以下ならば16bit整数のソート済みリストで管理する。このような場合分けを行うことによって一つの整数を16bit以下で表現できるようになる（実際にはデータ構造を管理するためのデータもあるがそれらは無視できるサイズ）。もちろん整数集合が密であれば一つの整数あたりのbit数はさらに小さくなる。ANDやORなどの論理演算は各コンテナ毎にANDやORを行ってそれを集約すれば可能。それぞれのコンテナ同士の論理演算はビット集合同士・ビット集合とソート済み配列・ソート済み配列同士の場合分けでやるだけ。やってることはシンプルだけど他のビット集合実装（例えばランレングスエンコーディングを使ったものなど）と比べて半分程度のサイズを実現し、ANDの処理が数百倍速くなることもあるらしい（圧縮・解凍をやるととても遅くなることがあるということらしい）。簡単なアイデアで高い性能を実現するいい話。最近のSIGMOD論文（http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA.pdf）でも推されているようだ（これはRoaringBitmapのトップページで引用されている）。

KaggleのAllstate Claims Severityというコンペに参加したのでメモ

Kaggle

今年の10月10日から12月12日にかけてKaggleで開催されたAllstate Claims Severityというコンペに参加した．

www.kaggle.com 各保険請求に関する特徴量として114個のカテゴリ変数と16個の連続変数が与えられるので，それを元に保険請求の金額を予測する．訓練データ188318件の各特徴量と請求額から学習モデルを構築し，テストデータの125546件に対して請求額の予測を行う．予測した請求額と実際の請求額の差の平均が最も小さい参加者が優勝．

このコンペで使用されるデータはzip圧縮を行っていない状態でも合計で100MBを大きく超えないので，同時に開催されていた他のコンペと比べるとかなり参加するハードルが低いように感じた．結果としてはpublic Leaderboard(LB)で134位でprivate LBで86位となり，参加者3055名中のTop-5%以内に食い込むことができたので銀メダルを取ることができた．

自分がやったこと

学習モデル

実行環境としてはGCPのn1-highcpu-16を使用．（vCPU x 16、メモリ 14.4 GB） コードはMacで書いてrsyncで仮想マシンに送っていた．

最終的にはまず以下のようなモデルを作成した．．

  • Keras (3つ)
    1. https://www.kaggle.com/mtinti/allstate-claims-severity/keras-starter-with-bagging-1111-84364 そのままのやつ
    2. 上記のもののlossの変換をlog(x + 200)から(x + 1) ** 0.25に変更したもの．時間をケチったのでバギングする個数を10個から3個に減らしてしまっている．
    3. 2.で各層のニューロンを少しずつ増やした．この3つのモデルの単独でのスコアはほとんど変わらなかった気がする．記憶が怪しい．
  • XGB (3つ)
    1. どこかのフォーラムで公開されていたのをそのまま利用した．今回は特徴量の作成とモデルの学習は分けているのでそのまま利用したと言っても特徴量に若干の差異があるかもしれない．単独でPublic LB = 1112くらいだったと思う．Early stoppingをしても40000本以上くらいの木を作成しようとしてモデルをシリアライズしたらMemory Errorで落ちた．結局木の本数を30000本に制限して動かした．
    2. https://www.kaggle.com/mariusbo/allstate-claims-severity/xgb-lb-1106-33084/code　違うフォーラムのやつ. こいつもPublic LB = 1107くらい．データの前処理に若干違いがあるみたいでForumでのスコアよりも少し悪くなっている．
    3. 2.のやつで重要度が高い特徴量同士の相互作用に関する特徴量を入れた．単独でのスコアは上昇しなかったがアンサンブル学習のときに効果があった．
  • LightGBM (2つ)
    1. XGBの2つめと同様の入力に対してLightGBMを走らせたんだったと思う．ちょっと違うかもしれない．
    2. 上記のモデル + fair_obj. fair_objは今回のコンペで重要な役割を果たしたxgbでの勾配の計算に使用される関数. LightGBMでは簡単に追加することができないのでLightGBMのC++コードをいじった．期待に反して微粒子レベルの効果しかなかった．

これらのモデルの出力を元にstackingした．今回stackingに用いた学習器はSGDRegressor(loss='huber', penalty='elasticnet') なのでweighted averagingと変わらないかもしれない．この学習器のlossとかpenaltyとかはhyperoptを使って正則化の強さと一緒に決定した．．まともにパラメタチューニングをしたのはここだけ．ニューラルネットを用いようともしたが結局うまくいかなかった．

最終スコア

  • Public 1101.62827
  • Private 1113.23506

優勝者のスコア

  • Public 1097.67455
  • Private 1109.70772

銀メダルボーダー

  • Private 1114.10023

差が大きい・・・

特徴量の分析はできなかった

各特徴量の名前は隠されているので（cat13とかcont12みたいな感じで与えられる）各特徴量がどういう意味を持っているかを調べることは難しかった．結局Forumを眺めて得られる以上の解析はできなかった． Forumでのdiscussionの多くは連続特徴量をどのように変換すると学習器が高いパフォーマンスを発揮できるかなどが主に議論されていた．

上位勢がやっていたこと

とにかくたくさんモデルを作成してstackingをしている．

自分がまだ触れたことのないモデルとしては

  • Regularized Greedy Forest
  • Vowpal Wabbit
  • LibFM
  • LibFFM
  • ExtraTrees(sklearn)
  • glmnet (R)

などがある．

他の工夫としてはlossの値が大きい部分と小さい部分に対してそれぞれモデルを構築したり，Nelder-Meadソルバーを用いて誤差の平均が最小になるように重み付き平均の重みを調整したりしていたようだ．

感想

  • データサイエンスのコンペではない気がする．何を競っていたのだろうか？
  • 結局自分ではろくに特徴量エンジニアリングもパラメータチューニングもしていない・・・どれだけモデルをたくさん立ててもアンサンブルしても単一で強いモデルがないとスコアは良くならないようなので次から頑張ろう． 今振り返ってみると幾つかのXGB, LightGBMに関してはパラメタチューニングすることも可能だった．
  • 今回はチームを組むのは禁止されていましたが他の多くのコンペではそうではないので，そういったコンペを一人で戦うのはより大変そう．例えば今回のコンペで上位だった何人かの投稿を合わせると簡単に一位を超えるスコアが出るみたい．Does it blend? - Allstate Claims Severity | Kaggle
  • Easy way to get score 1105.05 on Leaderboard - Allstate Claims Severity | Kaggleというトピックが出ていて，NNとxgbの公開されているモデルの平均をとるだけで最終のPublic LBでTop-15%以内のスコアをとることができる．案外勝とうとして参加している人は少ないんだろうか？
  • 文章を書くのは疲れる

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs (KDD'15)

アブストのみ 論文読み

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

Ethan R. Elenberg, K. Shanmugam, M. Borokhovich, Alexandros G. Dimakis (The University of Texas, Austin, TX, USA)

概要

3-vertex subgraphの数え上げをsparsificationによって辺を減らした後, 分散アルゴリズムによって推定値を計算する.

感想

WWW'15 で3-path samplingに基づく4-vertex subgraphが出てしまっているのでなんだか微妙に感じてしまう.

Network Lasso: Clustering and Optimization in Large Graphs (KDD'15)

アブストのみ

Network Lasso: Clustering and Optimization in Large Graphs

David Hallac, Jure Leskovec, Stephen Boyd (Stanford University)

　概要

凸最適化はデータ分析において非常に重要な役割を担っているが汎用の凸最適化ソルバは大規模な問題に対してスケールせず,　一部の問題に対してスケールするソルバが扱える問題は狭い範囲のものでしかなかった.この論文ではネットワーク上での最適化やクラスタリングを行う問題に対して, group lassoを一般化したnetwork lassoというものを提案する. Alternating Direction Method of Multipliers (ADMM)に基づくアルゴリズムを開発し大規模なネットワークでも計算が収束するようにした. 二値分類・家賃予測・時系列データのイベント予測などの凸でない問題も含む問題において既存手法と比較することによってnetworks lassoに基づく手法が高速で高精度であることをしめした.

アブスト訳すだけになってしまった・・・

Localization and centrality in networks (Phys. Rev. E. '14)

論文読み アブストのみ

Localization and centrality in networks (Phys. Rev. E. '14)

　T. Martin, Z. Xiao, M.E. J. Newman

概要

Eigenvector centralityは頂点の重要度を表す有名な指標であるが,高い次数の頂点とその隣接頂点のみ値が大きくなってしまい（localization）それ以外の頂点の相対的な優先度がわからなくなってしまうという問題点が知られていた.本論文ではまず,その問題点を数学的に解析し,べき乗則にしたがうネットワークでも同様の現象が起こることをしめす.次に,その解決策としてeigenvector centralityの亜種を新たに提案し,その指標ではlocalizationが発生しないということを理論・実験の両方によって示している.

詳しい説明は次のページで https://www.quora.com/What-is-an-intuitive-explanation-of-the-Hashimoto-non-backtracking-matrix-and-its-utility-in-network-analysis

感想

論文中にあったEigenvector centralityにおけるlocalizationと提案手法によってそれが解消された図はかなりimpressiveであった. ランダムウォークで直前の辺を通らないというアイデアはだいぶ前からあったようだし,提案された指標の新規性がどうなのかは正直わからない.数学的な解析が主な貢献ということでいいんだろうか？もうひとつ気になったのはeigenvector centralityの計算方法で今知られている高速なものはなんなんだろうかということ.これはこの論文では触れられていなかった.

Maintaining the duality of closeness and betweenness centrality (Social Networks'15)

Maintaining the duality of closeness and betweenness centrality (Social Networks'15)

　U. Brandes, S. Borgatti, L.C. Freeman

概要

媒介中心性は各ノードが持つ他のノードへの影響力を表しており,近接中心性は他のノードへのアクセスの効率または他のノードの影響力からの影響の受けにくさを表している. 媒介中心性と近接中心性は影響力の視点で考えた時に双対的な関係があると言われているが,それはあくまで直感的なものに過ぎなかった. 今回の研究では,１つめの貢献としてフォーマルな形でこれらの中心性の双対的な関係を示している. ２つ目の貢献としては有向重み付きなネットワークにおいて近接中心性をもともとの定義（全ノードへの距離の和の逆数）として扱うよりも媒介中心性との双対性を元に新しく定義した指標を用いることを提案している.

はてなで数式書くのつらい・・・