2008-03-22
Application of Dimensionality Reduction in Recommender System - A Case Study
- Sparsity, reduced coverage
- ex. amazon: 200 万件の 1% は 20000 件: 1% を rate してるユーザはほとんどいない.
- user-based の手法らしい: neighbor もってきて合算
- SVD はオフラインでやっておく
- E-commerce のデータ(very sparse)では結果悪い
- MovieLens のデータでは結果良い
んー. いまいちよくわからん... でも次元縮退の具体的なやりかたがわかったからいいか... しかし主成分分析でやった分散行列とかぜんぜん出てこないで, いきなり rating matrix を SVD しちゃうのね. なんでそれで良いのかがわからん.
“Indexing by Latent Semantic Analysis” (Deerwester 1990) が 元ネタらしい. 他の SVD based recommender をいくつか見てから読もう.
http://sifter.org/~simon/journal/20061211.html
- sigmoid ?
- 何が SVD なのかわからんが, これがいわゆる "incremental SVD" らしい...
- empty element を fulfill する方法とか
http://sifter.org/~simon/journal/20070815.html
- gradient descent?
- さっぱりだ...
何がわかってないのか?
- そもそも recommender system でどうやって SVD を使うのか？なぜそれが成立するのか？
- incremental SVD の実装
- grouplens での式の根拠がわかってないのが敗因だな... 出てくる式は似てるから.
Latent Semantics Analysis
wikipedia again. 混乱のないように document-term の用語で...
X = USV のとき, U は concept space での term vector のリスト, V は concept space での document vector の list になっている. SVD の残りの部分 (U なら SV) は, concept scape から元の doc-term matrix への変換になる.
だから類似の文書を探すには, 入力となる文書 vector d を concept scape の vector d' に変換し, それから concept space の文書 vector 群 V (の個々の列)と比較すれば良い.
recommender system でも同じ理屈が使える. concept space で item vector (個々の要素は user concept: SF 好きとか) を 表現しておき, item 間の比較は concept vector で行う. 同様に user vector も concept space で表現しておく. (個々の要素は item concept: SF とか.) すると concept space でユーザ間の距離を比較できる.
ポイントは, document と term (=user と item) で別々の concept space が あるということ. (変換も別. US と SV.) X は doc vector であり かつ term vector だったが, SVD によってその二つが分離されたのがミソだった.
やー, わかってなかったなあ先週は... 今度こそわかったはず...
そして recommender system での SVD と PCA は関係なかった! なんてこったい.
Dimensionality Reduction and the Singular Value Decomposition
なんか途中の図が間違ってるな.
新しい知見はなかったけど, 理解は clarify された. あとやはり incremental SVD は勉強せなあかんことがわかった. simonfunk の方法は one of them らしい...
Interview with Simon Funk
かっけー.
simonfunk はフツーに incremental SVD の考案者だった. マジかよ.
しかし何も面倒がないから netflix やってみたってのはスゲー理由だなー.
Korbell/BellKor
下から順に読んでくか.
Modelling relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems.
BellKor.
- |item| < |user| なら item based の方が効率的. item-item sim を前計算できる
- ex. 映画.
- amazon はどうか？
- neighbor-based の欠点: similarity の計算に根拠がない
- neighbor 情報を生かさない: 続編モノの影響がでかくなる
- error-based method: "predict the quality of predictions"
ごめん. 全然わかんない...
Chasing $1,000,000: How We Won The Netflix Progress Prize
BellKor.
- 複数手法を combine するのが有効だ
- どうやって組合せるのか？-> "confidence score" というのがあるらしい...
- 既存手法の改善もした
- Neighborhood-Aware Factorization
- Accounting for Which Movies are Rated
- Interporation Weights for Neighborhood Models
- Regulation
結局よーわからんです... 理解したいけど...
Improved Neighborhood Based Collaborative Filtering
- recommendation は missing data estimation である
- kNN の 3 つのコンポーネント
- data normalization
- neighbor selection
- determination of interpolation weights
global effect についてはようわからず.
w の算出について
- optimization problem に帰着する
- least square problem になる -> regress して解く (えー...)
線形問題解くとかヤだなー...
CMU 学生の reading memo.
global effect removal は regression だといわれてもなー. さっぱしですよ...
どうしたものか.
- 回帰分析を勉強する？
- ほっといて incremental SVD を勉強する？
- ほっといて続きを読む？
だいぶ脳みそがしんどくなってきたな. とりあえず続きを読んで, wikipedia で回帰分析読んで, incremental SVD かな. とりあえずわからないのが何かは clarify しときたい.
やー, わかんね. 続きも最適化問題に帰着する, というところまではわかったけど, そのあとがわからん. 教養不足だなあ.
とりあえず回帰分析が関係ありそうだから, 教科書で勉強してから出直そう.
[Book] パターン認識と機械学習
よく目次を見たくなるのでリンク. もう買って読もう.
updating reading queue
んー. 最初は generic な理解からスタートして, 途中から netflix 中心にスイッチ. で KorBell で行き詰まっていまここ.
たぶん古いやつや, 大仰な overview ばかり読み進めても実装の訳には立たないだろう. 世間の OSS 実装をみならって, item/user/rate 的なのをちょっと generalize したくらいのモデルを相手にしたアルゴリズムに絞ってよいだろう.
KorBell は理解したい. Incremental SVD も理解したい. KorBell 理解のために PRML 読もう. 回帰分析まで. 動機のはっきりした文献は潰していく.
動機のはっきりしない, 教養的な文献, 実験的な性質の強い文献, 評価のよくわからない文献は 優先度を下げて読み進もう.
明日は PRML 買いにいくぜ予定. その前に掃除もせんとな. あと翻訳...
acceptable complexity
しかし Simen では回帰分析/最小二乗法とか実装すんのかな. 重かったり数値計算的に複雑だったりするのはパスしたいなあ. 当面は.
やっぱり素朴なアルゴリズムと良いアーキテクチャで実験できる土台を固めて, 精度や速度の評価とかの仕組みを作ってから色々複雑なものを作ることになるんだろうねえ.