スライドメモ:KDD2014 Tutorial “the Recommender Problem Revisited”

Netflixの中の人によるKDD2014 Tutorialの”The Recommender Problem Revisited”のスライド1を読んだので，簡単にまとめてみた．レコメンドのこれまでと現状をひと通り網羅したチュートリアルという感じ．このスライドはKDD2014 Tutorial向けだけれど，今度のRecSys 2014のTutorialでも同様の発表があるようだ(link)．

  • レコメンドの大まかな流れを知りたい人
    • このチュートリアルもいいけど，日本語で書かれたしましま先生の資料の方が丁寧でわかりやすいかも
  • レコメンドの具体的な手法や流行を知りたい人
    • このチュートリアルで興味ある分野の箇所を見て個別にReferenceを当たる

どっちにしろ素人のまとめなので，以下のメモは参考程度にお願いします．

Kdd 2014 Tutorial - the recommender problem revisited

(追記:2014.10.8) RECSYSのスライドも公開された．

Recsys 2014 Tutorial - The Recommender Problem Revisited

TL;DR

レコメンドのこれまでと現状をひと通り網羅した資料．情報過多の時代においてレコメンドは必要不可欠な技術であり，いまでは従来のレコメンドに加えてパーソナライズやインターフェイスなどの複合要素を考慮したレコメンドが必要になってきた．それにともなって，レコメンド手法としても古典的な協調フィルタリングから，Netflix Prizeにより出現した次元削除の手法，ランキングアルゴリズムやディープラーニングを用いたコンテンツベースのレコメンドなどへと広がりをみせている．

1. The Recommender Problem

  • レコメンデーションは必須
  • レコメンドの定義
    • 今までの定義：ユーザが好きなアイテムを自動的に予測する効用関数を作る
    • これからのレコメンド：今までのレコメンド＋α
      • セレンディピティ（偶然の発見＆ユーザが既に知っているアイテムを推薦しない）
      • ユーザインターフェイス，パーソナライズなど
  • レコメンドの進化
    • 単純なレート付け→ランキング→ページ最適化→コンテキストを含めたレコメンドへ

2. Traditional Approaches

2.1 Collaborative Filtering (CF)

協調フィルタリングの基本

  • 協調フィルタリングの構成要素
    • ユーザがアイテムに付けたレートが基本
    • レートが無くても購買履歴などから補完することもできる
  • アクティブユーザの情報がメイン
  • ユーザ間の類似度を使う
    • 一種のパーソナライズと取れる
    • ピアソンの相関係数/コサイン類似度
  • あるユーザに類似したユーザを探しだしてレート付けされてない作品を推測する
  • ユーザベースの協調フィルタリング / アイテムベースの協調フィルタリング
  • 協調フィルタリングの特徴
    • 長所：最小限の情報で計算できて，だいたいにおいて性能が良い
    • 短所：アイテム数が増えるとスパースになる＆スケールが難しい
      • ユーザ数xアイテム数のうち，値が入っているのはごく僅か(1%以下)

モデルベースの協調フィルタリング Model-based CF

  • Netflix Prize

    • アルゴリズム的にRMSE基準でトップ2つのアルゴリズム
      • SVD
      • RBM
    • 今でもNetflixのレート推定の一部に使われている
      • SVD++とRBMの組み合わせ

  • Simon Funk’s SVD

    • Netflix Prizeで出てきた面白いアルゴリズム（Blogが初出）
    • SVD++

  • Restricted Boltzmann Machines

クラスタリング Clustering

クラスタリング：ユーザを特定の好みごとにクラスタリングして推薦する

  • Locality-sensitive Hashing(LSH)
    • 高次元空間で類似したアイテムをクラスタリングする手法
    • 似たアイテムが近くにくるようなハッシュ関数を探す
    • 最近傍探索(NN)によく使われる
  • 他のクラスタリングアルゴリズム
    • k-means
    • Affinity Propagation
    • Spectral Clustering
    • HDPs

相関ルール Association Rule

  • アプリオリ・アルゴリズムなど

分類器 Classifiers

  • いわゆる普通の分類器
    • 使い勝手が良くて組み合わせも可能だが，トレーニングセットが必要で正則化などが必要
    • ロジスティック回帰，ベイジアンネット，SVM，決定木など

協調フィルタリングの限界 Limitations of Collaborative Filtering

  • コールドスタート問題
    • 他のユーザの評価が十分に無いと機能しない
    • 新しいアイテムなどで推薦が難しい
  • 人気バイアス
    • 既に人気のあるアイテムを推薦しがち

2.2 Content-based Recommenders

コンテンツベースの特徴

  • 長所
    • 他のユーザ情報が不要なためコールドスタートやスパース性を考慮しなくて良い
    • ユーザ独自の好みに合わせることができる
    • 新しいアイテムを推薦することができる
    • レコメンドの理由を説明しやすい
  • 短所
    • アイテムの内容から意味のある特徴量を抽出する必要がある
    • セレンディピティのある推薦が難しい
    • ユーザに最適化されすぎる

2.3 Hybrid Approach

  • Content-based recommendation with Bayesian classifier
  • Hybridization Method
    • (see P.68)

3. Beyond traditional Approarches to Recommendation

3.1 Ranking

  • ほとんどのレコメンドアルゴリズムは推薦するアイテムをソート済みのリストで返すから，レコメンドはランキングの問題とも捉えることができる
  • レートでランキングの順位を付ける
  • RMSEはランキングに使えない(?)
    • Linear modelで考えた時に，RMSEを最小にした結果ランキングに違いが生じる（Predicted RankingとFinal Rankingが違う）
    • (詳しくは図を参照)
  • ランキングを測る指標
    • Normalized Discounted Cumulative Gain
    • Mean Reciprocal Rank (MRR)
    • Fraction of Concordant Pairs (FCP)
  • 最近はランキング指標自体を最適化する研究も

3.2 Similarity

  • SimRank
    • グラフベースの類似度を考える
  • 幾つかの類似度を組み合わせる
    • データごとに様々な類似度がある（e.g. タグ，ユーザの行動，ユーザのレート付け）
    • 組み合わせの時の重みは回帰で学習する

3.3 Deep Learning for Recommendation

3.4 Social Recommendations

  • (詳細は省略)

3.5 Page Optimization

  • どうやって推薦したアイテムを表示させるかというページ構成の話
    • デバイスによって表示できるアイテム数などが違う
  • ユーザの注目度をモデリング，ヒートマップで可視化
  • 限られた状態で何を重視するか
  • 共存させるためのモデル
    • Navigational/Attention Model
    • Personalized Relevance Model
    • Diversity Model

3.6 Tensor Factorization & Factirization Machines

3.7 MAB Explore/Exploit



私的Vowpal Wabbitまとめ

VWとは

The Vowpal Wabbit (VW) project is a fast out-of-core learning system sponsored by Microsoft Research and (previously) Yahoo! Research.

Home · JohnLangford/vowpal_wabbit Wiki

Install

要Boost．

Linux

vowpal_wabbit/README.mdに書いてある通り，git cloneしてmakeする．それが駄目なら./autogen.shしてからmakeする．

自分の場合は./autogen.shがエラーを吐いたので調べたところ，./autogen.sh内部でldconfigに失敗してBOOST_DIR_ARGが取得できていないのが原因だった．su権限でldconfigをしてLIBFILEの箇所を以下のように書き換えて対処した．当然ながらこれは環境に依存するので，自身の環境でLIBFILEに渡すコマンドを実行して置き換える．

1
2

#  LIBFILE=`ldconfig -p | grep program_options | tail -n 1 | cut -d '>' -f 2`
  LIBFILE="/usr/lib64/libboost_program_options-mt.so"

Mac OS X

Mac OS Xの場合Homebrewでバイナリをインストール可能だが，vw-varinfo等のutil系は入らない．

1
2
3
4
5
6
7
8
9
10

$ brew info vowpal-wabbit
vowpal-wabbit: stable 7.7 (bottled), HEAD
https://github.com/JohnLangford/vowpal_wabbit
/usr/local/Cellar/vowpal-wabbit/7.7 (30 files, 4.7M) *
  Poured from bottle
From: https://github.com/Homebrew/homebrew/blob/master/Library/Formula/vowpal-wabbit.rb
==> Dependencies
Build: boost ✔, autoconf ✔, automake ✔, libtool ✔

$ brew install vowpal-wabbit

Windows

VWを始めるときに気をつけるポイント

  • VWの独自フォーマット
    • VWを使いはじめるときの最初の難関ポイント
    • 自分でcsvなどのデータをVWフォーマットに変換する必要がある
    • カテゴリ変数やテキストはそのまま列挙しても大丈夫．VWの方でn-gramも取ることができる
  • VWのパラメータ名
    • 資料によってパラメータの名前が違うので注意
    • 自分の環境でvw --helpして適宜読み替える

Tutorial

vw-varinfoについて

vw-varinfoを使うことによって，変数ごとに重み等の情報を出力することができる．

Other Resources



kimonoでKaggleユーザのクロールをしてみた

ふとKaggleに参加している日本人がどれくらいいるのかが気になったので，簡単にクローラーを作って調べてみた．

Kimonoを使ったクロール

手動でクローラーを書いてもいいのだけれども，今回はkimonoというクローラーを使ってみた．

kimonoはWebから簡単にクローラーを作成してAPIやJSON形式で取得できるようにするようなアプリケーションで，Chrome Extensionを使うことでインタラクティブにクロールする内容を選択することができる．今回は，Kaggle Rankingsのランキング500ページ分をクロールして，20000人分のユーザの情報（名前，ランク，ポイント，ロケーション）を取得した．今回クロールした結果は，以下のkimonoのウェブページから誰でも利用できるはず(アカウント持ってないと見れないかな)．ただしrankとptsが一緒になってたりとちょっと汚いので注意．

ちなみに，どれくらい簡単にできるかをgif動画にしてみた．最初は色々戸惑った部分もあったけれど，慣れてしまえば本当に簡単に扱える．以下の場合だと，ユーザ情報がページあたり50人分あるので，ある部分を選択したあとに他の部分も同様に取得するようにチェックを付けるのが重要．あと，paginationはいわゆる「次」にあたる部分を選択する．本当は選択した部分に対して正規表現を掛けてテキスト処理をかけることもできるのだけれども，今回は行っていない．

後処理

クロール自体はkimonoに任せることができたので，ここからはpythonスクリプトをちゃちゃっと書いて整形作業．クロールしたデータはJSON形式やcsv形式でダウンロードすることもできるが，今回はAPIから叩いてみる．kimonoの”Use in code”というタブに，CurlやjQuery，Node，PHP，Python，Rubyでそれぞれ書かれたスクリプトがあるので，それを使ってデータを取得する．例えば，curlとPythonだと以下のようになる

1

$ curl --include --request GET "https://www.kimonolabs.com/api/dyo7tdm8?apikey=7ZTTugRoP8xgIlOdAdyiHmwP4rFLviDO"
1
2
3
4

import json
import urllib

results = json.load(urllib.urlopen("https://www.kimonolabs.com/api/dyo7tdm8?apikey=7ZTTugRoP8xgIlOdAdyiHmwP4rFLviDO"))

今回は日本人のアカウント一覧が欲しいので，”Country of residence”にJapanと書かれていてかつポイントを持っているアカウント一覧を出力した．なお，ユーザプロフィールの記入は基本任意なので，プロフィールで”Country of residence”を編集していない日本人は対象外になっている．

リスト(2014/08/18現在)

ユーザページに飛べるように一応HTMLにした．気が向いたら定期的にアップデートするようにして，もっときちんと体裁整えるかも．こういった公開も含めてkimono側で簡単なインターフェイスがあると楽なんだけどなーと思った．



「バッドデータハンドブック ―データにまつわる問題への19の処方箋」読了

最近流行りの華々しいデータ解析の現実をつきつけられる1冊．ビッグデータといって騒いでいるお偉いさんは「顧客の行動データを収集して解析することで業務効率化」といった言葉を軽々しく口にするけれども，実際はそんな一言で片付けられるほど容易ではない．現実のデータ解析は泥臭く，手垢にまみれていて，そしていつも試行錯誤の繰り返しだ．手に入るデータがどれも十分な量あって構造化されていて綺麗なことなんてあるわけがない．そんなバッドデータを相手にどう立ち振る舞うかについて，大学で統計学を教えている講師から，データサイエンティスト，経済学者，スタートアップの共同創業者などなど，様々な分野の人間が自身の体験や知識をもとに書いている．それぞれがコンパクトにまとまっていて関連性が無いので，雑誌をペラペラめくる感覚で好きな箇所を読むことができる．

そのなかで個人的に面白かった章を幾つかピックアップして紹介してみる．

3章 機械ではなく人間が使うことを意図したデータ

いわゆるネ申エクセルのような人間が読むことを前提にした非構造化データを，いかにプログラムで読み取るかという話．ここではニュージーランドの学校ごとの成績の統計を取ろうとしているのだけれども，Excelのスプレッドシートにまとめられているうえに，男子校だからという理由で女生徒の情報が入力されていなかったり，男子校なのになぜか女生徒の結果が入っていたり…とデータ取得の苦労が見られる．それでも著者は，コードを書くことが解決法であり，データフォーマットを自在に変換できることこそが重要な能力であると断言する．実際には厳しい道だけれども，まさにその通りだと思う．

8章 血と汗と尿

英国安全衛生研究所に持ち込まれる大量のサンプルの化学的解析を行っていた著者の話．化学者のカルチャーを身をもって体験した話がとても面白く，実験系の人のことを知っていれば非常に共感できる内容になっている．著者の同僚の化学者はその道のプロフェッショナルで，データの測り方に必要な計器のキャリブレーション，実験で出てくるデータのピアレビューといった方法など，化学の世界で独自に発展させてきた技術や経験があるものの，いまだにExcelですべて完結させていたりと，データ解析の面では改良の余地がある．なんとかして構造化データとしてまとめた上で自動化したいんだけど，現実にはデータのタイプや欠損値の扱いなど様々なハードルがある．それでも怠惰という自動化は素晴らしいし，適切なコードを書くことで達成できるというもの．

14章 クラウドコンピューティングの神話

この章はちょっと系統が違っていて，データ解析というよりかはクラウドの現実に焦点が当てられている．著者はMongoDBを開発している10genのエバンジェリスト．内容はストーリー仕立てで，自分のサービスをクラウドで運用しはじめたスタートアップCTOの主人公が，次第に規模が大きくなっていくにつれて様々な障害に直面していくという流れになっている．地道なパフォーマンスチューニングにはじまり，クラウドが落ちてどうしようもなくなったり，小規模だからといって手動で行っていたことが仇となったり，次第にスケールしなくなっていく水平方向のサーバ増強，コストの増加など，非常にリアルな話が次々と出てくる．結局はバズワードに飛びつくのは勝手だが現状を打破して何でも解決してくれる技術なんて存在しないということなんだけれども，将来的に技術が発展してそういう未来になるといいよねという，本来私たちが望んでいる理想で締められているところが良い．

16章 機械学習の専門家の手なづけ方

Kaggleというデータ解析のコンテストに出題側として参加したスタートアップの創業者の話．サービスに合う機械学習アルゴリズムの開発をKaggleを通してアウトソースするのは，一見簡単そうに見えて実は大変で，データセットの作成から評価方法の検討，匿名化，コンテスト運営など，クリアしなければいけない関門は意外に多い．それでもコンテストの結果は満足のいくものだったし，自分たちで正解セットをタグ付けしたり特徴量を考えたりすることによって，結果的に出題者自身が問題を正しく理解できたという側面もあったという．こういったデータ解析分野としての新しいコミュニティやプラットフォームが出てきて企業の問題解決につながるというのは，データ解析に身をおく人間として望む未来だよなぁとしみじみ思う．



iPython Notebookの–pylab Inlineは使うのをやめようという話

TL;DR

ipython notebook --pylab inlineのかわりにipython notebook --matplotlib inlineを使おう．もしくはipythonの始めに%matplotlib inlineを実行しておく．

iPython Notebookについて

周知の事実だとは思うが，iPythonは超便利なPythonのインタラクティブシェルだ．その一部としてiPython Notebookというのがあり，ブラウザでコードを実行できたり，実行結果をノートとして保存したり，matplotlibなどで描写したグラフをノートの中にそのまま表示したりできる．RでいうところのRstudio+knitrのような，解析レポートを作るときには重宝するツールとなっている．


http://nbviewer.ipython.org/gist/twiecki/3962843より

(http://nbviewer.ipython.org/gist/twiecki/3962843より)

で，iPython Notebookに関する記事を見ていると，だいたい以下のようなコマンドで実行している．

1

$ ipython notebook --pylab inline

ipython notebookで起動，それにくわえて–pylab inlineとすることでiPython Notebook内で描写したグラフが展開できて嬉しいわけだけど，一つ問題がある．それはpylabをインポートしている点だ．

無意識にpylabを使うとなにが危ないか

pylab自体は色々と便利なパッケージなんだけれども，そのpylabの挙動に少し問題がある．上で示したようなコマンドでpylabフラグを付けて実行すると，実は裏ではnumpyのモジュールがnpのエイリアスとともに，トップレベルでもインポートされている．実際にコマンドを叩いて確かめてみると以下のようになる．

1
2
3
4
5
6
7

$ ipython --pylab

In [1]: np.arange(0,10)
Out[1]: array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

In [2]: arange(0,10)
Out[2]: array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

どっちも実行できていて何の変哲もないように見えるんだけど，よくNumpyの実行環境で見るimport numpy as npの場合だと，1行目の書き方では実行できるが，2行目の書き方では実行できない．それが，pylabをインポートしているとどちらもできてしまう，正確に言えば，Numpyの関数がモジュール名もしくはエイリアスを先頭に付けなくても実行できてしまう．

ではこれの何が問題かというと，関数の名前がかぶるというわけだ．たとえば組み込み関数のsum()やall()は，実はNumpyにも同様の名前の関数がある（sum(),all()）．なのでpylabをインポートすると，勝手にsumやallがNumpyのモジュールのものに置き換わってしまう．

1
2
3
4
5
6
7
8
9
10
11

# pylabをインポートしない場合
$ ipython

In [1]: sum,all
Out[1]: (<function sum>, <function all>)

# pylabをインポートした場合
$ ipython --pylab

In [1]: sum,all
Out[1]: (<function numpy.core.fromnumeric.sum>, <function numpy.core.fromnumeric.all>)

意識的にpylabを使おうと思って書くコードなら良いんだけど，もしpylab関係なくいつもiPython Notebook使ってるからという感覚でpythonのコードを書いたとして，あとで普通のpythonで実行したら動かない，なんてことが起こりかねない．まあ気をつければ済む話かもしれないが，こういう地雷は踏まないに限る．

公式にも–pylabは使えなくなる見込み

あと，–pylabを使ってiPython Notebookを起動すると以下のような警告文が出る．

1
2
3
4
5
6
7
8
9

$ ipython notebook --pylab inline

[...]

[NotebookApp] WARNING | Starting all kernels in pylab mode is not recommended,
    and will be disabled in a future release.
    Please use the %matplotlib magic to enable matplotlib instead.
    pylab implies many imports, which can have confusing side effects
    and harm the reproducibility of your notebooks.

ということで，iPython Notebookを使うときには–pylabで読み込みをしないほうが良い．

pylabを使わないでinline表示させるには

–pylab inlineを回避する方法は2つある．

  • ipython notebook --matplotlib inlineで起動する
  • %matplotlib inlineをiPython Notebookの冒頭で実行しておく

こうすることによって，pylabのインポートを回避しつつiPythonのノート内でグラフを描写することができる．1つ目のiPythonのフラグで指定するほうが簡単だとは思うのだが，ぐぐってもこのコマンドで実行している例があまり出てこないのだけれども，たぶん問題無いと思う．

注意

ここまで読んだならわかるとは思うけれども，pylabの行儀悪いNumpyインポートを避けようということをしたわけだから，当然Numpyは別でインポートしないといけないし，そのへんのウェブページに載っているiPython Notebookの実行例とかのNumpyの関数の入ったコードはそのままでは実行できない．今回の方法を使っているなら，そのあたりは適宜読み替える必要がある．あんまり見たこと無い関数があったら，それがPythonの組み込み関数なのかNumpyやpylabの関数なのか疑ってかかろう．もしNumpyの関数なら，import numpy as npがされていることを確認したうえでnp.を関数の先頭につければ実行できる．なんかコードのサンプルをコピペしたけど動かないというときは，まあ大抵この問題だ．

元ネタ

追記(2015/01/25)

ipython notebookのコンフィグに追記しておく方法もあるようです．

参考

参考