論文メモ: Item2Vec: Neural Item Embedding for Collaborative Filtering

NLP Recommender system 論文メモ

word2vecをリコメンデーションに応用した論文"Item2Vec: Neural Item Embedding for Collaborative Filtering"を読みましたので、そのメモとなります。

[1603.04259] Item2Vec: Neural Item Embedding for Collaborative Filtering

1. INTRODUCTION AND RELATED WORK

SGNS(skip-gram negative sampling, word2vec)をアイテムベースの協調フィルタリングに応用する。

それをitem2vecと名付け、SVDと比較して優位性を示す。

2. SKIP-GRAM WITH NEGATIVE SAMPLING

SGNSについて概観する(初出はこちらの論文)。

前処理まで完了した文章(単語列の形式で、例えばI have a pen.なら[I, have, a, pen])を {(w_i)^K_{i-1}}、文章内で現れる全単語を {W={w_i}^W_{i=1}}とすると、skip-gramは以下の目的関数の最大化を目指して、確率的勾配降下法で学習する。

\frac{1}{K} \sum^K_{i=1} \sum_{-c \le j \le c, j \ne 0} \log p(w_{i+j} \mid w_i)

cはウィンドウサイズで、前後c単語(周辺単語と呼ぶ)を考慮する。
{p(w_j | w_i)}は、対象の単語 {w_i}と周辺単語 {w_{i+j}}の共起確率を表すソフトマックス関数です。

p(w_j \mid w_i) = \frac{\exp(u^T_i v_j)}{\sum_{k \in I_W} \exp(u^T_i v_k)}

{u_i}は対象単語のベクトル、 {v_j}は周辺単語のベクトル、 {I_W}は全単語のインデックスを表す。 単語ベクトル長(mとする)はハイパーパラメータとして設定する。

上の式では、分母で全単語との総和を計算しているため、pの計算量は出現する全ての単語数(105〜106)に比例して増大してしまう。

negative samplingでは、周辺外単語の計算(分母の計算)は全ての単語について計算するのではなく、ランダムにサンプリングされたN個の単語についてのみ行うことで近似する。
以下の式になる。ただし、 {\sigma(x) = 1/(1+\exp(-x))}と置いている。

p(w_j \mid w_i) = \sigma(u^T_i v_j) \prod^N_{k=1} \sigma(-u^T_i v_k)

なお、単語の出現頻度による偏りを防ぐために、出現頻度が高い単語はサンプリングされにくいように工夫する。
単語wの出現頻度をf(w)、閾値をρとすると、以下の確率で単語wはサンプリングから外す。

p(discard \mid w)=1-\sqrt{\frac{\rho}{f(w)}}

参考

SGNSについては、こちらの方の記事がとても参考になります。 あわせて読むと理解が捗ります。

word2vecのソースを読んでみた - Qiita

Word2Vec のニューラルネットワーク学習過程を理解する · けんごのお屋敷

3. ITEM2VEC - SGNS FOR ITEM SIMILARITY

SGNSをアイテムベース協調フィルタリングへ組み込む方法について説明する。

SGNSでは単語列からある単語とその周辺の単語から関連性を計算していた。
アイテムベースCFでは、単語をアイテム、単語列をアイテム集合(バスケット)と置き換えることでSGNSを適用する。

列から集合となったことで、SGNSでは持っていた時間・位置の近接情報については、捨てることにした。
したがって目的関数からは、ウィンドウサイズを取り払い、以下の式に変更する。

\frac{1}{K} \sum^K_{i=1} \sum^K_{j \ne i} log p(w_{i+j} \mid w_i)

アイテムiのベクトルを {u_i}とする。 アイテム間の関連度はコサイン類似度で計算する。

以降では、このプロセスやこのプロセスで得られたアイテムベクトルを総称してitem2vecと呼ぶ。

4. EXPERIMENTAL SETUP AND RESULTS

SVDを比較対象とし、データセットを使った実験と評価を行う。

SVDは以下の手順でベクトルを作る。 item2vec同様、アイテム間のコサイン類似度を計算する。

  1. K×Kの正方行列を用意する(Kはアイテム数)
    • (i, j)の要素は {(w_i, w_j)}の同時出現頻度が正規化された値がセットされる
  2. 正方行列を特異値分解して、 {US^{1/2}}行の単語ベクトルを得る
    • Sは対角行列(K×K)で、Sから重要度の高いベクトルをm個を持つ(したがって、m次元まで圧縮できる)
    • Uは左特異行列(K×K)
  3. (SVDについて正しく理解できていないので、記述が誤っているかもしれません。)

評価には2種類のデータセットを使う。

  • Microsoft Xbox Musicの再生ログ
    • 732,000ユーザと49,000アーティストの9,000,000再生ログ
  • Microsoft Storeの購入ログ
    • 1,706アイテム、379,000オーダー
    • 「同時に購入された」という情報のみを持つ(その他のユーザの情報は使わない)

まずはMusicデータセットについて、それぞれの手法(item2vecとSVD)でジャンル分けして、精度を見る。
t-SNEで2次元に可視化した結果が下の図(原文Fig.2を引用。左がitem2vec、右がSVD)で、概ねitem2vecの方がきれいに分離していることがわかる。(SVDは図右下で混在が見られる)。

f:id:ohke:20171130142811p:plain

数字(原文TABLE 2を引用)でもitem2vecのほうが精度が高く、特に人気の低い(15人以下のユーザが再生した)アーティストでは約10%の差を付けている。 これは、人気の高い(出現頻度の高い)アイテムについては間引かれやすく(p(discard | w)の式)、またnegative samplingの対象にもなりやすいので、人気の低いアイテムの影響が相対的に高くなったためである。

f:id:ohke:20171130143303p:plain

最後にMusicとStoreのそれぞれにおいて、item2vecとSVDが推薦したアイテムを比較し、いずれもitem2vecの方がより類似したアイテムを推薦していることを確認した(原文TABLE 3, TABLE 4を引用)。
特にStoreでは、「同時に購入された」という情報以外のアイテムに関する情報を捨てているにもかかわらず、類似した物が連なっていることがわかる。

f:id:ohke:20171201083136p:plain

所感

最後に私の所感をまとめます。

ドメイン情報無しで適用できる

2つ目の実験で明らかになってますが、ユーザやアイテムに関するドメイン情報を使わず、「同時に購入された」という組み合わせ情報だけで、関連度の高いアイテムが抽出できているのは注目に値するかと思います。

ドメイン情報を必要としないword2vecと協調フィルタリングの利点を、そのまま残しています。

ドメイン情報をどうやって注入するか

一方で、ビジネスに適用して高い精度を達成するためには、ドメイン情報を上手く表現して組み込む必要があるかと思います。

今回は実験のために「同時に購入された」以外の情報をばっさり落としてますが、例えばECであれば、一般的に以下のような傾向は想定されます。

  • ユーザAが今回購入する物は、1年前に購入した物より、先週購入した物と類似している

こうした時間的な近接性はitem2vecの目的関数にはありません。
概念的にはword2vecにあったウィンドウの考え方が近いので、それをitem2vecにも組み込めれば表現できそうです(後続の研究でこうした取り組みもあるかと予想されます)。

次の機会には実装してみたいと思います。

Visual Studio Codeでシーケンス図を描く(PlantUML拡張機能)

Visual Studio Code

VSCodeでシーケンス図などのUMLを描くことができる拡張機能を紹介します。

ドキュメントに関しては、テーブル定義やAPI仕様など必要最低限のみを作成するようにしているのですが、シーケンス図は詳細設計や実装前のフローの整理ということでよく描きます。
この拡張機能を使うと、楽に作成できるようになり、Git上でも管理できるようになります。

PlantUML

PlantUMLはUML図を記述するためのドメイン特化言語です。

シーケンス図の書き方については、こちらの方の記事に詳しく記載されています。

PlantUML - シーケンス図 | プログラマーズ雑記帳

PlantUML拡張機能

VSCodeで、PlantUMLのシンタックスハイライトやプレビュー、ファイルへの出力などを行う拡張機能が開発されています。

marketplace.visualstudio.com

"PlantUML"で検索して、インストールします。

f:id:ohke:20171122084120p:plain

この拡張機能は、拡張子.puのファイルをPlantUMLファイルとして認識しますので、.puファイルにPlantUMLで記述していきます。
例えば、簡単なブログページの表示をシーケンス図をPlantUMLで表現すると、こんなコードになります。

/'
ブログのシーケンス図
- ブラウザでトップページを表示する
- JavaScriptで通知件数を表示する
'/

@startuml

actor Browser as browser
participant BlogWeb as web
participant BlogAPI as api
database BlogDB as db

activate browser

group 画面の表示
    browser -> web :トップページにランディング\nGET: ohke.hogeblog.jp
    activate web
    web -> db :トップに表示するエントリを取得
    db --> web :
    web --> browser :トップページを表示
    deactivate web
end

group 通知の表示
    browser ->> api :ユーザへの通知情報をリクエスト\nGET api.hogeblog.jp/notify/ohke
    activate api
    api -> db :ohkeへの通知を取得
    db --> api :
    api --> browser :通知情報をレスポンス\n{"count":2,"messages":[...]}
    deactivate api
    alt countが1以上
        browser -> browser :件数をアイコンの横に表示
    end
end
note right: ロードしたnotify.jsから実行

deactivate browser

@enduml

.puファイルを編集中に、Alt+Dでプレビューを表示できます。

f:id:ohke:20171123104021p:plain

完成した.puファイルは、.pngや.jpgなどの画像ファイルにエクスポートできます。

f:id:ohke:20171123110649p:plain

エクスポートした画像ファイルはoutディレクトリ以下に出力されます。

f:id:ohke:20171123110810p:plain

シーケンス図以外にも、ユースケース図やフローチャートなどもPlantUMLで記述できますので、使いでのある拡張機能かと思います。

読書メモ: Machine Learning 実践の極意(Part I)

読書メモ 機械学習

「Machine Learning 実践の極意」を読みましたので、そのPart Iの読書メモです。

Machine Learning実践の極意 機械学習システム構築の勘所をつかむ！ impress top gearシリーズ

Machine Learning実践の極意 機械学習システム構築の勘所をつかむ！ impress top gearシリーズ

  • 作者: Henrik Brink,Joseph W. Richards,Mark Fetherolf,株式会社クイープ
  • 出版社/メーカー: インプレス
  • 発売日: 2017/11/17
  • メディア: Kindle版
  • この商品を含むブログを見る

Jupyter notebookのサンプルコードは以下のレポジトリにあります。

github.com

この本を読むモチベーション

2つあります。 読む箇所に緩急を付けますので、読書メモとしては乱杭になるかと思います。

  • 機械学習で得られたモデルを改善するプロセスやテクニックを獲得する
    • 第1部でアルゴリズムではなくプロセスごとに章立てされており、第2部ではさらに具体的な問題に適用しながらモデルを洗練させていく過程が記されているので、上の目的を果たしそう
    • どうすればさらに精度が高い答えにたどり着けるのか、についてメモしていきます
  • 機械学習に直接関連する学習からここ数ヶ月遠ざかっていたので、復習して、再定着を図る
    • この本はscikit-learn、pandasなどPythonのオーソドックスなツールを使って実装されており、上の目的を果たしそう
    • 「忘れてた」「こういう便利なものもあるのか」という再発見をメモしていきます

Part I 機械学習ワークフローの基礎

第2章 現実世界のデータ

  • 特徴量(説明変数)をどうやって選択すべきか
    • レンジを広くすると無関係な特徴量を含んでノイズとなるが、狭くすると関係する特徴量が抜け落ちるというトレードオフに悩まされる
    • 現実的なアプローチは、最初は関係する可能性が高い特徴量のみでモデルを構築し、それで十分な予測性能が得られない場合は、その他の特徴量を追加して拡張していく
      • 拡張した特徴量セットは特徴選択アルゴリズムで効果的な説明変数を選び出す
  • 目的変数(ground truth)を含むデータセットをどうやって収集すべきか
    • 既知の目的変数を含むデータセットを使って、未知の目的変数を含むデータセットから、トレーニングセットの候補を抽出する能動学習(active learning)と呼ばれる手法がある
  • トレーニングセットの量はどれくらい必要か(十分なのか)
    • データの典型性が維持されていれば、多ければ多いほうが良い
    • トレーニングセット数を増やしていき、予測性能が頭打ちになる点が無いかを調べる(頭打ちしている点が十分なトレーニングセット数)
  • トレーニングセットの典型性は十分なのか
    • トレーニングセットと、最終的に予測したい将来のデータが類似しているかどうか
    • サンプル選択時のバイアス、特徴量の収集方法の変化、データそのものの特性の変化が影響する
  • データが欠測していることに意味(情報利得)の有無で欠測値の扱いが異なる
    • 意味が有る場合は、MissingやNoneなどのカテゴリ値や、-1などの終端値に置き換える
    • 意味が無い場合は、その列の平均値や中央値、あるいは線形回帰などで補完する

第5章 特徴エンジニアリングの基礎

  • 特徴量選択の方法として、変数増加法(forward selection)と変数減少法(backward elimination)の2つがある
    • 変数増加法は以下プロセスで行う(変数減少法はこの逆で、全ての特徴量を含んだ特徴量セットからスタートして、1つずつ減らしていく)
      1. 空の特徴量セットを作る
      2. 利用可能な特徴量から1つを選択して、特徴量セットに一時的に追加して、交差検証を行う
      3. 利用可能な全ての特徴量に対して、2.を行う
      4. 最も性能が良い特徴量を選択して、特徴量セットに追加する
      5. 全ての特徴量が追加されたか、目標の性能に達するまで、2.〜4.を繰り返す
    • 上記の過程で、性能に影響を与える順番で特徴量がソートされるため、重要な特徴量を見抜くことにも役立つ

scikit-learnで特徴選択

特徴選択については、scikit-learnを使った実装まで掘り下げてみたいと思います。 (ちなみに第5章だけレポジトリにサンプルコードがレポジトリにありません。)

これまでランダムフォレストの重要度(例えばRandomForestClassifer.feature_importances_)やロジスティック回帰の重み(例えばLogisticRegressionClassifier.coef_)などで代用してきましたが、scikit-learnには特徴選択用のクラスも提供されています。 それらをいくつか試していきます。

http://scikit-learn.org/stable/modules/feature_selection.html

はじめにscikit-learn付属の乳がんデータセットをDataFrameにロードしておきます。
数値のみの30次元のデータを持ち、今回の検証では使いやすいデータセットとなっています。

import pandas as pd
from sklearn.datasets import load_breast_cancer


dataset = load_breast_cancer()

X = pd.DataFrame(data=dataset.data, columns=dataset.feature_names)
print('X shape: {}'.format(X.shape))
# X shape: (569, 30)

y = pd.DataFrame(data=dataset.target, columns=['target'])
print('y shape: {}'.format(y.shape))
# y shape: (569, 1)

RFE (recursive feature elimination)による特徴選択

変数減少法に近い実装として、sklern.feature_selection.RFE、および、RFEに交差検証を追加したRFECV(交差検証)があります。

RFEは、変数減少法と同じく、最初に全ての特徴量を使ってモデルを構築します。 そのモデルの中で最も重要度の低いを特徴量を削り、性能を再計測するという処理を、指定数(デフォルトでは1)の特徴量になるまで繰り返します。 重要度の指標にはfeature_importancesやcoefが使われます。

乳がんデートセットに対して、分類器にSVMを使い、REFCV(5分割交差検証)で特徴量を削減する実装は以下のとおりです。

  • ranking_には認識率が高くなる特徴量のランキングが昇順でセットされています
    • つまり値が1となっている特徴量のみを使うと最も高い認識率となり、今回の例では14個だけで十分ということです
    • プロットされたグラフを見てみても、特徴量数14の点で最も高い認識率(0.96)をマークしています
import matplotlib.pyplot as plt
from sklearn.svm import SVC
from sklearn.model_selection import StratifiedKFold
from sklearn.feature_selection import RFECV


# SVMによる分類
estimator = SVC(kernel='linear')

# 5分割交差検証
cv = StratifiedKFold(5)

# 特徴量削減
rfecv = RFECV(estimator, cv=cv, scoring='accuracy', step=1)

# 学習
rfecv.fit(X, y)

print('Feature ranking: \n{}'.format(rfecv.ranking_))
# Feature ranking: 
# [ 1  8  3 17  1  1  1  1  1 14 12  1  1  9 10  6  5  7 15 13  1  2 11 16  1 1  1  1  1  4]

# 最も高い認識率となる特徴量14個
print('Rank 1 features: \n{}'.format(X.columns[rfecv.ranking_ == 1]))
# Rank 1 features: 
# Index(['mean radius', 'mean smoothness', 'mean compactness', 'mean concavity',
#        'mean concave points', 'mean symmetry', 'texture error',
#        'perimeter error', 'worst radius', 'worst smoothness',
#        'worst compactness', 'worst concavity', 'worst concave points',
#        'worst symmetry'],
#       dtype='object')

# 特徴量数と認識率の変化をプロット
plt.plot(range(1, len(rfecv.grid_scores_) + 1), rfecv.grid_scores_)
plt.show()

f:id:ohke:20171118145833p:plain

SelectPercentileによる特徴選択

ある指標に従って、上位X%の特徴量を選択するのがsklearn.feature_selection.SelectPercentileです。
指標には、カイ二乗検定(chi2)、F検定(f_classif)などが使えます。

類似したクラスとして、上位k個の特徴量を選択するSelectKBestがあります。

カイ二乗値の上位20%の特徴量を選択する実装を以下に示します。

from sklearn.feature_selection import SelectPercentile, chi2

# 20%(6個)の特徴量を選択
transformed_X = SelectPercentile(chi2, percentile=20).fit_transform(X, y)

print('Transformed X shape: {}'.format(transformed_X.shape))
# Transformed X shape: (569, 6)

SelectFromModelによる特徴選択

feature_importanceやcoefを使った特徴量選択の方法として、sklearn.feature_selection.SelectFromModeも提供されています。

SelectFromModelは学習済みのモデル(feature_importanceまたはcoefを持つことが前提)と閾値を生成時に渡し、transformメソッドで閾値以上の重要度の特徴のみを抽出した特徴ベクトルへ変換する、前処理として機能します。
あくまで変換のみに使うため、分類は別のモデルで行うこともできます。

SelectFromModelを使って、ランダムフォレストのfeature_importances_で特徴選択するコードを以下に示します。

  • prefitがTrueの場合は、学習済みの分類器を用意して、SelectFromModelにセットします
    • thresholdで選択する特徴量の閾値を設定してます(今回は平均値以上の特徴量を選択します)
  • transformメソッドで30次元から9次元まで削減されます
from sklearn.ensemble import RandomForestClassifier
from sklearn.feature_selection import SelectFromModel
from sklearn.pipeline import Pipeline


# ランダムフォレスト
estimator = RandomForestClassifier(random_state=0)
estimator.fit(X, y)

# 重要度が平均値以上の特徴量を抽出
sfm = SelectFromModel(estimator, threshold='mean', prefit=True)
transformed_X = sfm.transform(X)

# 30次元から9次元まで削減
print('Transformed X shape: {}'.format(transformed_X.shape))
# Transformed X shape: (569, 9)

# estimatorから計算した場合と一致することを確認
importances = estimator.feature_importances_
importances[importances > sum(importances)/len(importances)]
# array([ 0.07046207,  0.08107073,  0.14697489,  0.04568418,  0.12102667,
#         0.1117098 ,  0.10620932,  0.04035243,  0.10317082])