2019-02-27

Calibrated Recommendations (Recsys 2018) を読んだ

3行で

レコメンドエンジンの性能がよくなればなるほど、かつアイテムに偏りがある場合(ECサイトにおけるアイテムジャンルの偏りなど)、次第にレコメンド結果が似通ったアイテムに偏りがちになるという問題が存在します。

本論文ではその補正(calibrate)の方法について提案しました。おなじみMovieLens20Mを用いた実験で提案手法が想定通り機能することを示しています。

背景

ある動画サイトではAとB２つのジャンルがあるとします。ジャンルAには動画の70%, Bには動画の30%があるとする。このサイトには随時N件のレコメンド枠があるとします。

とあるユーザーUはジャンルA,B同等に興味を持つとします。

このとき、

Uに対してA:B 7:3の割合で提示する Uはこの中からランダムに選ぶ (ポジションバイアスなどは忘れる) が、Aを7割の確率で選ぶことにレコメンドエンジンはUがAを選びやすいことから、Aをより多く出すようにする。。。

の繰り返しの結果、いつしかユーザーUに対してはジャンルAの動画ばかり並ぶことになる、というのがこの論文で主題にしている問題となります。(エコーチェンバー現象と名付けられています)

本論文はこの課題をスコア補正によって解決しようと試みています。ようするに、レコメンドされるアイテムのジャンル比率を、過去にそのユーザーが見たアイテムのジャンル比率と一致させるように補正すればいいよねっていう発想です。

手法

metrics

まず、「適切に補正されているか」を示すメトリクスが必要になります。少なくとも筆者によれば「この課題に特化したmetricsはない」と言っています (DiversityやFairnessのmetricsもtackleしている問題設定としては似ていますが、非なる問題であると言及)

ユーザーuが過去に再生した動画のジャンル分布を

$p(g|u) = \frac{\Sigma _ {i \in H} w _ {u,i} \cdot p(g|i)}{\Sigma _ {i \in H} w _ {u,i}}$

ユーザーuがレコメンドされた動画セット $I$ のジャンル分布を

$q(g|u) = \frac{\Sigma _ {i \in I} w _ {r(i)} \cdot p(g|i)}{\Sigma _ {i \in I} w _ {r(i)}}$

で表現したとき、KLダイバージェンス

$C _ {KL} (p ,q) = \Sigma _ {g} p(g|u) log \frac{p(g|u} {\tilde{q}(g|u)}$

を「小さいほど、ユーザーの興味に対して推薦アイテムのジャンルが偏っていない」　指標として用いるわけです。

そして、推薦アイテム集合 $I$ があるとき、 $s(I)$ をアイテムセットIに含まれるスコア(クリック予測値とかそういったもの) の和として、

f:id:Graphium:20190227174203p:plain

( $I$ はユーザーにレコメンドするアイテムの集合、Nはレコメンドするアイテムの数、 $\lambda$ はレコメンドスコアとcalibrated scoreのどちらをより重視するかのパラメータとなります.

この最適化問題を解くことでジャンル偏りを補正することを提案していますただし当然ながら多項式で解ける問題ではないです。故に空のリストを用意し、推薦スコアの高いアイテムから順にCalibrated Scoreが最大化するようなアイテムを探してリストに追加していく、というアルゴリズムを用いることを提案しています

実験

「本来なら先行研究と比較したいが、おれが考えた問題設定でだれも解いたこと無いから俺たちの手法が期待通り動いていることを示すぜ(意訳)」ということで、そういうことです

Movielens-20M使って、補正の強さ項 $\lambda$ を変化させたときのCalibrateの様子を実験しています。データとしては、ジャンルタグのついてないアイテム及び再生されていないアイテムを削除し、99%をtrain, 1% とtestに分割.

f:id:Graphium:20190216155131p:plain f:id:Graphium:20190216162831p:plain

$\lambda =0.95$ くらいまではcalibration scoreの増加の割にrecallの減少がゆるやかだね、という主張です。

お気持ち

院ですこしだけやりましたが、この手の(diversityやfiarness含め) 、メトリクスを「適切に」定義するところから議論しなければならないの厳しい。

読む必要・参考文献など

http://ir.ii.uam.es/saul/pubs/recsys2014-vargas-tid.pdf

2019-02-27

Ranking Distillation: Learning Compact Ranking Models With High Performance for Recommender System (KDD 2018)を読んだ

3行で

ランク学習にたいする知識蒸留タスクに対する手法を提案する論文です。利用方法として、モデルサイズを小さくして応答時間を良くしたり、オンラインでの学習を実現しやすくできることが考えられます。

背景

Deepを使ってレコメンドタスクを解くことを考えます。どんなにオフライン指標が高いモデルができたとしても、インフラが貧弱で、サービスに載らなければ売上には繋がりません

... というわけで、こういったことの解決策の一つとして、「モデルを小さくする」ということが挙げられます。すこし悪いくらいの予測精度で、もっと小さなモデルを構築できれば、システムに載る可能性がでてきます。

いろんな方法が提案されていて、(中には3Dプリンタでモデルを書き出し、レーザー光を当てて出力を観測し予測、文字通り光の速さで予測できるよ、という論文もあります) 今回は蒸留によってモデルを小さくする話となります。

Knowledge Distillation

一般的なclassificationタスクでの蒸留手法はさまざま提案されていますが、ランク学習という枠組みでは解かれて来ませんでした。Classificationに対するKnowledge Distillationは大まかに言ってある入力にたいするラベルの分布、を真似するように小さいモデルを学習させますが、例えばレコメンドにおけるラベルの分類というのは下手をすればアイテムの個数分となります。

提案手法

ざっくりいうと次の手順を踏みます

データセットD0を用いてTeacherである大きなモデルを学習させる
データセットD1 (ラベルなし) をTeacherに予測させ、上位のDocumentを取得
データセットD2 (ラベルあり) による誤差と、2で得られたDocumentを真似るような誤差とを合わせてChildを学習

f:id:Graphium:20190216170613p:plain

このうち3.でのロス関数は次の定義です。

$L (\theta _ s) = (1-\alpha) L^{R} (\bf{y}, \hat{\bf{y}}) + \alpha L^{D} (\pi _ {1 \cdots K}, \hat{\bf{y}})$

右辺の左側は通常のpoint-wiseなランク学習のロス関数

$L^{R} (\bf{y},\hat{\bf{y}}) = - ( \sum _ {d \in \bf{y} _ {d+}} \log (P (rel = 1 | \hat{y} _ d)) + \sum_{d \in \bf{y} _ {d-}} \log (1 - P (rel = 1 | \hat{y} _ d)))$

で、右が本題の手順2. のドキュメントを利用するときのロス関数に当たります(後述)

Teacher modelの蒸留

前述のロス関数右辺第二項は以下のように定義されます

$L^{D} (\pi _ {1 \cdots K}, \hat{\bf{y}}) = - \sum ^{K} _ {r=1} w _ {r} \cdot \log( P(rel = 1| \hat{y} _ {\pi _ r}))$

$\pi _ {r}$ というのは、「Teacherがtop-r位に予測したDocument」ということを示します. $K$ は、Teacherの予測の上位何位までをStudentの学習に用いるか、というハイパラになります。

そして、一つ一つのDocumentの誤差の和を取る際につける重み $w _ r$ は

$w _ {r} = \frac{ ( w ^ {a} _ {r} \cdot w ^ {b} _ {r} ) } { \sum ^ {K} _ {i=1} w ^ {a} _ {i} \cdot w ^ {b} _ {r}}$ で定義されます。

これは２つの要素からなっており、 Teacher が上位だと予測したdocumentほど、大きい値になる(= この重みが大きいDocumentを上位に予測するとより褒めてくれる) 重み $w _ a$ $w _ r ^ {a} \propto e ^ {-r / \lambda } , \lambda \in \mathbb{R} ^ {+}$

と、「このDocumentは本来Studentくんにr位くらいと予測してほしいが、ちょっと難しそうなので厳しく教えるね」という重み $w _ b$

$w _ r ^ {b} = tanh (max ( \mu \cdot ( \hat{r _ {\pi _ r }} - r), 0 ))$

の２つを混ぜ合わせて計算します。

$\hat{r _ {\pi _ r }}$ というのは、「 $\pi_r$ をStudentくんがドキュメント全体の何位に予測するだろうか」　という数値です。ランダムにサンプルしたデータの予測結果と比較して、全ドキュメントの何位あたりにに $\pi_r$ が予測されるか、という数値を求め、　その順位が大きければ大きいほど $w _ b$ は大きくなることになります

f:id:Graphium:20190216183318p:plain 　

実験

データセット

データセットは次の２つ。全actionのうち、train:valid:test = 7:1:2としている。 f:id:Graphium:20190216184500p:plain

評価指標

Precision@n, nDCG@n, MAP ( $n \in {3, 5, 10}$ )

比較対象

Fossil : Similarity + 多次元マルコフチェイン
Caser : CNNによるDocumentのEmbeddingと、UserのEmbeddingのFusion
POP : popularityベースのレコメンド
ItemCF : 強調フィルタリング
BPR : Baysian personalized ranking

上２つの手法をTeacherとして、それぞれごく普通のLinear Layerを重ね合わせただけのStudentを学習させます。

結果

提案手法と比較対象の予測性能差

f:id:Graphium:20190216190210p:plain -T とついているのは元のTeacherモデルで、-RDとついているのは提案手法。　-SはTeacherを学習させたときと同じデータで、蒸留をせずStudentモデルを学習させた場合を表します。

ここで、-S のStudentモデルのモデルサイズは、「少しずつTeacherとcomparableになるまでモデルサイズを大きくしていった」と書かれています。

-RD と-Sを比較すると、-RDが大幅に性能がよい = 提案された蒸留方法がよく機能している　ということが言えます

蒸留したモデルの予測計算時間

f:id:Graphium:20190216185633p:plain テストデータに対する全アイテムの予測時間です。先程の予測性能表と見比べると、「同じ程度の予測性能があるのに、予測にかかる時間は半分程度になったよ」ということが言えます

Distillation lossの有効性

f:id:Graphium:20190216185642p:plain 横軸iteration, 縦軸MAP. 最初はDistillation Lossを用いいずにStudentを学習させ、iteration = 30の破線があるタイミングでDistillation Lossを導入してみたところ(紫の折れ線)、学習曲線がよくなったことから、提案したLoss関数が有効だと主張しています。

Studentのモデルサイズと予測性能の関係

f:id:Graphium:20190216185633p:plain 横軸にStudentのモデルサイズ (棒が右軸で示されるパラメータ数), 折れ線がStudentの予測性能(MAP), 破線がTeacherの予測性能となります。「ある程度モデルが小さくなるまでは、モデルパラメータ数に対して線形に性能が変化する傾向」、つまり多少モデルサイズを減らしたところで一気にStudentの予測性能が落ちるわけではない、ということが分かります。

二種類の重みを用いることの有用性

f:id:Graphium:20190216185651p:plain 横軸に2種類の重みのどちらをより使うかのパラメータ、縦軸にMAP. いい感じに2つの重みをmixさせると予測性能いい感じだよ、というグラフですね.

2017-06-06

Chainrmn をTSUBAME2.5にインストール

これはなに？

分散型深層学習フレームワークchainermnがリリースされました。TSUBAMEで早速使うべくインストールバトルをしたのでその記録です

GCC 野良ビルド

これは各自がんばってください(C++11が使えることが必須)

NCCL

makefile23-25行をコメントアウト

NVCC_GENCODE ?= -gencode=arch=compute_35,code=sm_35 \                             
                -gencode=arch=compute_50,code=sm_50 \                            
                -gencode=arch=compute_52,code=sm_52 \                             
                #-gencode=arch=compute_60,code=sm_60\                             
                #-gencode=arch=compute_61,code=sm_61 \                            
                #-gencode=arch=compute_60,code=compute_60

make CUDA_HOME=/usr/apps.sp3/cuda/7.5 test

MVAPICH

./configure --enable-cuda --prefix=PATH_TO_INSTALL
make -j4
make install
echo 'export MV2_USE_CUDA=1' >> ~/.bashrc

mpi4py

git clone https://github.com/mpi4py/mpi4py
cd mpi4py
python setup.py install

defaultのPYTHONPATHに、

/usr/apps.sp3/isv/amber/16_update01/i2013.1.046_ompi1.6.5_cuda7.5/amber16/lib/python2.7/site-packages

が~~何故か~~入っていてここにpython2.7のmpi4pyが入っているため競合して死にますのでテキトーにこれを削除すること

chainermn

CC=~/where_to_gcc/bin/gcc-*.* CPATH=/usr/apps.sp3/cuda/7.5/include/:where_to_nccl/src/ LD_LIBRARY_PATH=$NCCL_ROOT/lib/:$LD_LIBRARY_PATH  python setup.py install

chainerの修正

TSUBAME上のGlibcが古いためadamの計算中に死にます

from math import pow
...

def lr(self):                                                                 
        fix1 = 1. - pow(self.hyperparam.beta1 , self.t)                           
        fix2 = 1. - pow(self.hyperparam.beta2 , self.t)                           
        return self.hyperparam.alpha * math.sqrt(fix2) / fix1

と変更

実行

(py35) ****@t2a006178:> python train_mnist.py --communicator naive -u 3
GPU: -1
# unit: 3
# Minibatch-size: 100
# epoch: 20
epoch       main/loss   validation/main/loss  main/accuracy  validation/main/accuracy  elapsed_time
1           1.66641     1.37389               0.386533       0.477                     2.28905       
2           1.29713     1.22861               0.505617       0.5274                    4.62439       
3           1.18703     1.1563                0.555467       0.5726                    6.97202       
4           1.12184     1.10202               0.586317       0.6042                    9.2815        
5           1.07451     1.06617               0.60965        0.6231                    11.5855       
6           1.03577     1.03241               0.626          0.6427                    13.8904       
7           1.00202     1.00216               0.64285        0.6502                    16.2714       
8           0.971201    0.972216              0.654417       0.6621                    18.5773       
9           0.944552    0.94554               0.663717       0.68                      20.8936       
10          0.923072    0.93476               0.67625        0.6806                    23.2178       
11          0.904248    0.909097              0.684383       0.6966                    27.4446       
12          0.887569    0.901461              0.695067       0.6992                    29.7539       
13          0.872541    0.879583              0.701683       0.7024                    32.0666       
14          0.860256    0.870163              0.707083       0.7094                    34.4527       
15          0.849695    0.868137              0.713617       0.7098                    36.7594       
16          0.840893    0.857363              0.716383       0.7179                    39.08         
17          0.831741    0.847023              0.720683       0.7158                    41.9922       
18          0.825027    0.837325              0.72385        0.7226                    44.3936       
19          0.818212    0.835769              0.727233       0.7271                    46.7902       
20          0.811998    0.828687              0.7304         0.73                      49.2771

2015-04-23

私的コーヒーの飲み方まとめ

保存

豆の状態で冷凍一択です。できればジップロックのような空気が入らないような入れ物がbetter。
挽いてしまった豆は数日で酸化して美味しく無くなります。実は豆の状態できちんと冷凍したとしても、一週間も経てば微妙な感じになってしまいます。ちなみに新鮮じゃなくなったかどうかはドリッパーにお湯を垂らした瞬間にわかります。

ドリッパー

日本で普通に売ってるドリッパーの形には二種類(以上)あります。
円錐形をしているドリッパー(カリタ)は、フィルターの中にお湯が漂う時間がより長くなるため、より成分を抽出することができます。僕はこっちの方がお気に入りで8年くらいずっと円錐ドリッパー使ってます。一方で、間違えると濃すぎる珈琲が出来上がることになるので、ミルの挽き加減を調節する必要があります。(実家近くの喫茶店マスター曰く、「客に苦い苦いとクレーム食らってよく話を聞いてみたらこれを使ってた」らしい)

挽く

調節

まずミルを調節する必要がある...のですが、他の使う器具、豆の種類、果てには個人の好みによって正解が変わってしまうため、何度も淹れては調節することを繰り返して最適解を見つける必要があります。とりあえずグラニュー糖くらいの大きさにした上で、少しずつ細かくしていくのがいいと思います。

管理

とくに夏場、使わないで放っておくと、場合によってはカビが生えます。普通のミルなら金属の部分は外れるので、定期的に掃除します

グラインド

個人的にそんなに違いがあるのかよ、とは思うのですが、力任せに早く回してしまうと、摩擦熱で粉が酸化してしまうそうです。ゆっくり今日これからの予定を話しかけるようにしながらグラインドします。一人あたり10g。

以下ペーパードリップ(画像がない、まるでただの(ry

抽出

お湯

お湯を沸かします。ちなみに一度沸騰させてしまったお湯を温めなおすのはNGです。なぜなら、水道水に含まれているガス類が抜けることで味が(悪い方に)変わってしまうためです。
コーヒーの抽出に最適な温度は80度少しなので、沸騰したら少し一呼吸おいて冷ましましょう。ただし、酸味が強いコーヒーが好きな人はもう少しお湯を覚ましてもいいかもしれません。

蒸らし

お湯が用意できたら、コーヒーの粉の上に少しだけ注ぎます。目安は、サーバーにぽつ、ぽつっと少しずつ垂れてくるくらい。ちなみにこの時に粉面がどれだけ膨らむかどうかで新鮮さがわかります。よく膨らむのは新鮮な豆の証拠です。古い豆を使うと、注いだところが穴になったりします。
蒸らす時間はやっぱり好みですが、20秒くらい放っておけば十分だと思います。個人的な意見ですが、スッキリしたものが飲みたい時は短め、目を覚ましたいようならその逆にするといいかと。

淹れる

蒸らしが終わったら静かに注ぎます。まず注意点としては、膨らんだところを潰さないことです。ふくらみの周辺部はそのままペーパーの方までいって濾過層(重要)になります。
一回目の抽出が終わったら二回目に入りますが、ここで絶対にやってはいけないのは「'の'の字にお湯をまわしかける」ことです。一回目の抽出を終えたところで粉面やペーパーには白~茶の泡が浮かんでいると思います。これはコーヒーのアクなので、何としてでもサーバーに落としてはいけないわけです。ゆっくりと真ん中に注ぎます。
また、珈琲の美味しい成分自体は一回目の抽出で大抵出終わっています。二回目以降は濃さを調整するくらいのイメージでやったほうがいいかと思います。

気が向いたら直火エスプレッソとフレンチプレスも書きたい。

2015-04-02

記法テスト

${\displaystyle f_t = \sigma ( W_{xf} X + W_{hf} h_{t-1} + W_{cf} c h_{t-1} + b_f ) }$

import numpy as np
import theano
import theano.tensor as T



from collections import OrderedDict


def adadelta(rho_,eps_,cost,params,L1_rate,L2_rate):
        updates = OrderedDict()
        gparams = [T.grad(cost + L1_rate * param.norm(L=1) + L2_rate * param.norm(L=2) , param) for param in params]
        gparams_mean=[gparam.mean() for gparam in gparam in gparams]

        eg2=[theano.shared(np.zeros_like(param.get_value(borrow=True))) for param in params]
        dxt=[theano.shared(np.zeros_like(param.get_value(borrow=True))) for param in params]
        ex2=[theano.shared(np.zeros_like(param.get_value(borrow=True))) for param in params]

        for gparam, param, eg2_,ex2_ in zip(gparams,params,eg2,ex2):
         updates[eg2_]=T.cast(rho_ * eg2_ +(1. -rho_)*(gparam **2) ,theano.config.floatX)
         dparam = -T.sqrt((ex2_ + eps_)/(updates[eg2_] + eps_)) * gparam
         updates[ex2_]=T.cast(rho_ * ex2_ + (1. -rho_)*(dparam **2),theano.config.floatX)
         updates[param]=T.cast(param + dparam,theano.config.floatX)
        return updates,eg2,ex2

def sgd(lr,cost,params,L1_rate,L2_rate):
    gparams = [T.grad(cost + L1_rate * param.norm(L=1) + L2_rate * param.norm(L=2) , param) for param in params]
    gparams_mean=[gparam.mean() for gparam in gparams]
    updates = [(param,param - lr * gparam) for param,gparam in zip(params,gparams)]
    return updates,gparams_mean

def sgd_momentum(lr,momentum,cost,params,L1_rate,L2_rate):
    gparams = [T.grad(cost + L1_rate * param.norm(L=1) + L2_rate * param.norm(L=2) , param) for param in params]
    #gparams_mean=[gparam.mean() for gparam in gparam in gparams]
    ex2=[theano.shared(np.zeros_like(param.get_value(borrow=True))) for param in params]

    for gparam,param,ex2_ in zip(gparams,params,ex2):
        updates[ex2_]=ex2_
        updates[param]=T.cast(param + momentum * ex2_ - lr * gparam,theano.config.floatX)
    return updates,ex2

3行で

背景

手法