takuti.me ABOUT

2017-01-27

Courseraの推薦システムのコースを修了した

昨年の話だけど、Courseraで開講されていた "Introduction to Recommender Systems" を履修・修了した。教えてくれたのはこの分野で知らぬ者はいない、ミネソタ大学のJoseph Konstan先生。2000年あたりの協調フィルタリングなど古典的な推薦手法に関する文献を漁ると、必ず彼のグループの論文にたどり着く。かの有名なMovieLensデータセット(画像処理でいうMNIST的な、定番データセット)も、このグループが提供している。

コースは全8回で内容は以下。

  1. Introduction to Recommender Systems
    • 推薦システムの歴史やその背景
  2. Non-Personalized Recommenders
    • 『最も人気のアイテムを常に推薦する』といった、個人化を行わない推薦手法
  3. Content-Based Recommenders
  4. User-User Collaborative Filtering
    • ピアソン相関係数およびコサイン類似度に基づく類似度計算と正規化の重要性
    • ユーザ・アイテム間の行列における、ユーザ側の類似度に基づく推薦
  5. Evaluation
    • 精度からセレンディピティまで、いろいろな評価指標
  6. Item Based
    • ユーザ・アイテム間の行列における、アイテム側の類似度に基づく推薦
    • ユーザベースとの比較
  7. Dimensionality Reduction
    • 特異値分解、Matrix Factorizationによる行列補完
  8. Advanced Topics
    • Cold-start問題など

※ 現在このコースはすでにCoursera上に存在せず、アップデート版の Recommender Systems Specialization が代わりに開講されている。しかし残念ながら有料なので、各トピックの詳細は上記目次を参考にしつつググってください :(

全体として、コンパクトに推薦システムの世界がまとまった非常に良い内容だった。この分野は新しい手法が次から次へと生まれておりトレンドを追うのも一苦労だが、どのような手法でも基本は変わらない。このコースの内容さえ理解していればとりあえず推薦システムは作れるし、その良し悪しを議論することもできるだろう。

各回には講義パートとインタビューパートがあり、インタビューパートではゲストを招いた対話形式のコンテンツが提供されていた。これがすごく良くて、例えばコンテキストを考慮した推薦 (context-aware recommendation) について話してくれたのは、 Recommender Systems Handbook の編集者・Francesco Ricci先生だった!業界のトッププレイヤーたちから基礎が学べるなんて、いい時代に生まれたものだと思う。

推薦アルゴリズムの基本は、ユーザ・アイテム間の履歴(e.g., クリックした/してない、高評価/低評価)を以下のような行列のかたちで表現するところにある。なお、要素が取りうる値は0/1や実数値、具体的な5段階の評価値まで様々。

User-Item Matrix

そして、僕らが解くべき問題は行列の未観測値を予測することであり、予測値を元に「この人はどんなアイテムを好みそうか」という傾向を見つけていく。

このコースでは最初に 非個人化推薦 (Non-Personalized Recommender) を扱う。具体的には、『最も人気のアイテムを常に推薦する』であったり、『行列の未観測値は、その行(列)の平均値で埋める』であったり、そんな頭の悪そうな手法。しかしこんな手法でも、データによっては高度なアルゴリズムよりも高い精度を叩き出すことがあるので侮れない。推薦システムを作りたいときはこういうナイーブなところから始めるのも悪くない。

次に扱うのは 個人化推薦 (Personalized Recommender) で、数式や機械学習を使った賢そうな手法の多くはこれに該当する。中でも特に重要な手法は、Amazonの「この商品を買った人はこちらの商品も〜」で有名な 協調フィルタリング (Collaborative Filtering) だろう。

協調フィルタリング

協調フィルタリングにはユーザ間類似度に基づく方法 (user-based) とアイテム間類似度に基づく方法 (item-based) の二種類がある。どちらも基本は同じで、行(列)のペアに対して計算した類似度に基づいて未観測値を予測して、予測値の高いアイテムから上位N件を推薦する。以下は5段階の評価値行列に対する協調フィルタリングのイメージ。"Item-Based Collaborative Filtering Recommendation Algorithms"の図1に倣って書いた。

Collaborative Filtering

講義の中では「user-basedとitem-based、どちらが良いのか?」という問いにも答えていた。一般に、世の中のインターネットサービスは膨大なユーザを抱えており、各ユーザの趣味・嗜好は動的に変化する。ゆえに、ユーザ間類似度は計算が非効率で、かつ頻繁な再計算が必要となる。一方、アイテム数はユーザ数に比べると十分に少なく、それらの特徴はある程度静的だ。というわけで、user-basedよりもitem-basedのほうが現実的な選択と言える。

類似度についてはピアソン相関係数から始まり、正規化、コサイン類似度との関連について丁寧に解説されていた。おかげで、「協調フィルタリングの”気持ち”は分かったけど、どうやって実装すれば良いのか…」ということにはならない。以前読んだ『実践 機械学習』は、”気持ち”の解説に徹していて数学的な処理はブラックボックスのままだった。

次元削減(特異値分解、Matrix Factorization)

ひと通り協調フィルタリングを解説すると、講義では以下のような問題点が指摘される。

  • ユーザ・アイテム間行列が巨大すぎて、すべてのユーザ(アイテム)ペアについて類似度計算を行うのは非現実的
  • この行列は一般に疎(スパース;要素の多くが未観測値)なので、計算された類似度が有意義だとは言い難い

そこで「ユーザ・アイテム間の行列からできるだけ効率的に、より本質的なユーザの趣味・嗜好を抽出したい」というモチベーションから生まれた、協調フィルタリングの先にある推薦手法が 特異値分解 に基づくもの。

特異値分解は与えられた行列 $A$ を $U$, $\Sigma$, $V$ の3つに分解する手続きで、$A$がユーザ・アイテム間行列だとすれば、$U$はユーザに関する特徴が詰まった行列、$V$はアイテムに関する特徴が詰まった行列、$\Sigma$はそれらに与える重み、に相当する。

SVD

これらの積 $\hat{A} = U \Sigma V^{\mathrm{T}}$ は元の行列 $A$ の近似になっていて、$A$で未観測だった要素も$\hat{A}$ではなんらかの値が入っている。この値を予測値とみなして推薦をしましょう、というのが基本的なアイディア。

ちなみにPython + numpyならこんな感じ。

import numpy as np
import numpy.linalg as ln

# ユーザ5人、アイテム6つに対する行列(0は観測値)
A = np.array([[5, 0, 1, 1, 0, 2],
              [0, 2, 0, 4, 0, 4],
              [4, 5, 0, 1, 1, 2],
              [0, 0, 3, 5, 2, 0],
              [2, 0, 1, 0, 4, 4]])

U, s, V = ln.svd(A, full_matrices=False)

# どれくらいの粒度で近似するか
k = 2

A_ = np.dot(np.dot(U[:, :k], np.diag(s[:k])), V[:k, :])
# [[ 3.19741238  1.98064059  0.19763307  0.50430074  1.04148574  2.47123826]
#  [ 1.20450954  1.18625722  1.50361641  3.5812116   1.61569345  2.37803076]
#  [ 4.36792826  2.68465163  0.20157659  0.52659617  1.36419993  3.30665072]
#  [-0.94009727  0.07701659  2.08296828  4.93223799  1.52652414  1.44132726]
#  [ 2.67985286  1.80342544  0.63125085  1.52750202  1.27145836  2.54266834]]

ただしこの手法には重大な問題があって、未観測値をゼロで埋めている。5段階の評価値行列で0とは、すなわち「全く興味がない」に相当する。しかし本来、行列の未観測値には2種類の意味ある

  1. 全く興味がないからスルーしていた
  2. そもそもユーザはそのアイテムの存在に気づいていなかった

どちらの意味で”未観測”なのかが判断できない以上、テキトーな値で補完して処理を行うのはナンセンスだ。というわけで Matrix Factorization へと話が進む。これも行列を分解する手続きの一種で、$R$という行列を$P$と$Q$に分解する。

MF

特異値分解と比較すると、$U$が$P$に相当して、$V$が$Q$に相当する。ただし、重み$\Sigma$は$P$, $Q$の内部に埋め込まれている、というイメージ。

Matrix Factorizationのキモは、逐次的なアルゴリズムよって観測した値のみを使って行列を分解するところにある。

推薦の文脈での初出はNetflix Prizeの最中に投稿されたSimon Funkのブログエントリで、これが学術論文でめちゃめちゃ引用されている!1ブログエントリから始まった手法は今や業界では定番中の定番な手法となり、その先にあるProbabilistic Matrix Factorization、Tensor Factorization、Factorization Machinesなど、すべてはここを土台に議論ができる。

本当はこの先にあるもっと機械学習っぽい手法がアツくて面白いのだけど、そこは推薦システムの本質ではない。すべての基礎はこのコースで扱う話題の範囲内にあるのだと思う。ヒューリスティクスや非個人化手法が勝ることも十分ありうるわけだし。その意味で、Matrix Factorizationの導入までで講義を終え、より具体的かつ発展的な手法はすべてインタビューパートに回したコース構成はお見事だったと思う。

また、最終回にはAdvanced topicsとして、cold-start問題(履歴が存在しない新規ユーザ・アイテムに対して推薦をするのが難しい問題)に関する議論や、実践的な視点でのインタビューがあった。

まとめ

協調フィルタリングが発明されてから、Netflix Prizeを経てMatrix Factorizationの登場に至るまでの経緯が整理されたとても良いコースだった。手法や事例が無数に存在する分野なので、書籍やサーベイ論文を読んでもこのあたりを順序立てて学ぶのは結構難しかったりする。

インターン先のメンターにオススメされて受講しはじめたものの、すでに知っていることも多かったので途中サボったりして修了までに半年くらいかかってしまった。とはいえ、終えてみると得られたものは結構多かったなぁという実感がある。何より、このコースのおかげで推薦システムについて書いた僕の修士論文のBackgroundの章はものすごく充実した(と思う)。

難点をあげるとすれば、課題がスプレッドシートの上で行うことを想定して作られていたことだろうか。これに素直に従うのは死ぬほど退屈なので、僕は与えられたデータをCSVに変換した後、Juliaで実装しながら課題を解いた。この実装たちはライブラリにまとめて公開したので、興味があればぜひ。記事にもまとめました

余談だけど、ちょうど受講中に学生ボランティアとしてRecSys 2016に参加して、Konstan先生のユーモアや鋭い質問に間近で触れることができたのはマジ感動でした。さらに学生ボランティアの中にはKonstan先生のグループの学生もいて、その人は本会議に論文が採択されていて、ひょえ〜と思いつつ、とても高まった。