Gunosy8月入社のshunk(@makuramoto1)です．前職は研究員とマネージャーの間みたいなことをやっておりました．現在は，Gunosyのデータ分析や，どのように記事を出したりするかといったロジックを開発する仕事を担当しています．Web業界に初めて参入して，現在の職種もキャリアチェンジみたいなことをしたので，いち早く仕事をこなせるように邁進しております．

さて，本記事はGunosy Advent Calender2018の5日目の記事です．弊社では論文輪読会が週1で行われています．その際に，推薦モデルProd2Vecのハイパーパラメータ*1のチューニングに関する論文がありまして，面白そうだなと思い，以下の「Prod2Vecのパラメータチューニングに関する論文」を拝読いたしました．

拝読した論文達

Prod2Vecのパラメータチューニングに関する論文
Word2vec applied to recommendation: hyperparameters matter
Prod2Vecに関する元論文
E-commerce in Your Inbox: Product Recommendations at Scale

この内容がハイパーパラメータによるProd2Vecの性能調査を行っていただいているものの，やや思ってたのと違ったので，個人的にパラメータチューニングの手法を提案します．ただ，ハイパーパラメータチューニングの性能評価はできませんでしたが．．．．．そこは追々ということで．

論文概要

さて，ハイパーパラメータのチューニング方法を提案する前に，E-commerce in Your Inbox: Product Recommendations at Scaleの一部をざっくりと下記の流れで紹介します．

Word2Vec(W2V)とは
W2Vを応用したProd2Vec(P2V)
P2Vによる商品推薦方法
P2Vのハイパーパラメータによる性能

Word2Vec(W2V)とは

おそらく，本記事をご覧になっている方では，ご存知の方も多いと思いますが，単語のベクトル表現を行う時に用いられるモデルです．あまりにも多く知られているので，ここで私があえて説明することもないと思います．下記のサイトが非常にわかりやすいので，載せておきます．また，論文も調べていただければ出てくると思いますので，割愛させていただきます．

Word2Vec のニューラルネットワーク学習過程を理解する http://tkengo.github.io/blog/2016/05/09/understand-how-to-learn-word2vec/

ここで抑えていただきたいポイントが，W2Vとは，文脈から統計的にに単語を表現したベクトルということです．
例えば，W2Vの次元数を5とします．そのとき，単語は下記のようなW2Vになっていると仮定します

ドラえもん: [0.8, 0.1, 1.2, 0.05, 0.5]
ロボット: [0.5, 0.05, 1.5, 0.04, 0.7]
のび太: [1.2, 0.2, 0.01, 0.8, 0.1]

このとき，ドラえもんとロボットはなんとなく近そうだけど，ドラえもんとのび太は遠そうだなって，感覚的にわかると思います．ドラえもんはロボットやから，ロボットのベクトルと似てます．一方，ドラえもんは人間ではないので，人間ののび太のベクトルとは遠くなっているわけです．

W2Vを応用したProd2Vec(P2V)

W2Vを応用して，P2Vを構築します．W2Vは単語のベクトル表現ですが，P2Vは商品のベクトル表現です．W2Vは文脈から単語のベクトルを生成しますが，P2Vでは購入履歴から商品のベクトルを生成します．

商品の購入履歴の集合 $S$ があります．集合 $S$ の要素を $s$ とします．この $s$ は購入した商品の配列となっており，この商品は $p_i$ で示します．商品の購入履歴の集合から $N$ 次元のP2Vを生成します．

目的関数 $L$ ，購入履歴の集合 $S$ ，購入履歴の集合の要素 $s$ ，対象購入商品の前後の履歴をどこまで利用するか(コンテキスト)のサイズであるWindow Size: $c$ ，対象購入商品: $p_i$ ，購入商品の表現ベクトル $v$ ，コンテキスト中の対象購入商品の表現ベクトル $v'$ とします．あと，下記の式には出てきませんが，商品種類は $V$ とします．

この目的関数 $L$ を最大化するような $v'$ が商品のベクトル表現となります．

f:id:makuramoto1:20181204183853p:plain:w300

f:id:makuramoto1:20181204183856p:plain:w260

f:id:makuramoto1:20181204201020p:plain:w120

目的関数 $L$ を最大化するためにに確率的勾配降下法を用います．目的関数 $L$ を偏微分して，目的関数の変数空間の勾配を導出し，変数を徐々にいい感じの方向にずらします．繰り返し回数n回終わったら，だいたい目的関数が最大化したとみなして，その値を近傍最大解とします．

下記の式を， $v'$ と $\nabla L$ を更新しながら $n$ 回繰り返して，商品の履歴の表現ベクトルv'を算出します． $\nabla L$ は目的関数 $L$ の勾配を示します． $\eta$ は学習率です．

f:id:makuramoto1:20181204211300p:plain:w120

P2Vによる商品推薦方法

商品のP2Vが求まりましたら，商品推薦します．購入した商品に対して類似した商品を推薦するとします．商品Aと類似した商品Bがあります．このとき，商品Aと商品Bは類似しているので，商品AのP2Vと商品BのP2Vは類似しており，ABのP2V間の距離やコサイン類似度は近くなります．

購入した商品の類似した商品を推薦するには，購入した商品のP2Vと類似しているP2Vを探して，それに該当する商品を提案すればいいわけです．

P2Vのハイパーパラメータによる性能

P2Vによる商品推薦の品質は，ハイパーパラメータによって，性能が大きく左右されることが下記の論文で示されています．
Word2vec applied to recommendation: hyperparameters matter
Datasetの性質によるらしいですが，ハイパーパラメータを最適化する前とした後では，10倍以上の推薦の品質に差が出るらしいです．しかし，上記の論文ではハイパーパラメータのチューニング方法に関しては特に言及されてませんでした．

本稿ではP2Vのハイパーパラメータは下記の4つとなります．

購入商品の表現ベクトルの次元数: N次元
ウィンドウサイズ: $c$
学習の繰り返し回数: $n$
学習率: $\eta$

以降で，このハイパーパラメータのチューニング方法を示します．

P2Vのハイパーパラメータチューニングを実数値遺伝的アルゴリズムで妄想する

P2Vのパラメータチューニング方法には，遺伝的アルゴリズム（Genetic Algorithm，以下GA）が使えるのでは？と思ったので，GAによるP2Vのパラメータチューニング方法を妄想します．

(GAは以前私が研究していた分野であり，便利なのにそこまで情報が公開されていないような？気がしていたのでやってみようと思ったわけです．)

遺伝的アルゴリズムとは？

遺伝的アルゴリズムとは数理最適化手法の一つです．目的関数を与えると，その最小値ないし最大値の近傍解と，その近傍解になる入力値を出力します．今回では実数値空間のみを対象とします．
数理最適化問題は下記の式で示されます．

$\rm{argmin\ or\ max} \begin{eqnarray} f({x}) \end{eqnarray}$

関数 $f({x})$ を最小または最大化し，そのパラメータを得る式となっております．ここでは最大化問題として話を通します．例えば， $f(x) =- x^{2}$ とするならば， $f(x)$ を最大化するのは $x = 0$ ですよね．この $x= 0$ を求める問題なるわけです．

$f(x) = x^{2}$ くらい簡単な式ならば，因数分解なり直感的なりにわかるのですが，複雑な式の場合，または，そもそも $f(x)$ が数式化されていない場合はどうしたらいいでしょうか， $x = 1$ 与えたら， $f(x =1)$ という何かしらの値だけ返却されるシステムだとしたら，どうやって最小値，ないし，最大値を求めたらいいの？となるでしょう．そのときに使うのが数理最適化手法であり，その一つがGAです．

GAについて説明します． GAにもいろんな手法がありますが，ここは比較的簡単なREX/JGGを用います．REX/JGGの論文はREX/JGGに関しては，実数値GAのフロンティアです．なんらかの値が帰ってくるシステム，ないし，関数 $f(x)$ があります．入力するパラメータをベクトル $x$ として考えます．求めたいパラメータが10個あるならば，10次元のベクトル $x$ とし，個体と総称します．そして，個体 $x$ の定義域を設定します．

GAの初期動作として， $x$ の定義域内に，個体 $x$ をランダムに $n$ 個生成します．この $n$ 個の個体を集団 $P$ とします．これより，以下の手順で実行していきます，

集団 $P$ からランダムに個体 $y$ を $\mu$ 個，非復元抽出する．この抽出した個体を親個体とする
親個体 $y$ から個体 $x$ を $\lambda$ 個を以下の式に従って生成する．このとき， $m, \langle y \rangle$ は親個体の重心である． $\epsilon_{i, j}$ は平均0，分散1/nに従う正規乱数である．個体 $x$ を子個体とする．
$\lambda$ 個生成された子個体 $x_{i}$ を性能 $C(x)$ によって評価する．評価が良い個体から $\mu$ 個，個体を選択肢，集団 $P$ に追加する．選択されなかった子個体は集団に加えず，破棄する．
1~3を任意の回数繰り返し，評価値が最も良い個体を最良個体 $x_{\rm best}$ とする．

これより， $f(x)$ の最適パラメータ $x_{\rm best}$ が導出されます．
以下，図を用いた説明をしてます．

REX/JGG Algorithm from makuramoto

P2Vのハイパーパラメータチューニング

GAを理解したら，あとはGAアルゴリズムに，最大化したい関数 $f(x)$ と，パラメータ $x$ を決めて，入力するだけです．
最大化する $f(x)$ にが，P2Vの性能 $C(x)$ となります．最適化したいハイパーパラメータは下記です．

購入商品の表現ベクトルの次元数: $N$ 次元
ウィンドウサイズ: $c$
学習の繰り返し回数: $n$
学習率: $\eta$

ハイパーパラメータを4次元のベクトル $x = (N, c, n, \eta)$ として，GAのREX/JGGで最適化すれば， $C(x)$ を最大化することができるでしょう．

おわりに

長文，かつ，複雑になってしまいましたが以上となります．今後の執筆で，各々個別のわかりやすい説明をしていければと思います．

本稿には不足している部分が多々あります．例えば，Prod2VecのところのNegative SampllingやSub Samplingや，もっと性能がいいGAの導入などがあります．そのせいで，知見がある方は既に所有している知識との差分に困惑した部分もあるかと思います．申し訳ありません．

本稿で少しでも，推薦システムや，遺伝的アルゴリズムに興味を持っていただけたら幸いです．

*1:ハイパーパラメータって何：あるモデルやシステムを用いる時に，ユーザが決定しなければならないパラメータ（値）のこと．カメラをシステムとすると，絞りとかシャッター速度みたいなもの．適当に値を決めて撮影することもできるけど，綺麗な写真撮ろうと思ったら，絞りとかシャッター速度とか良い値をユーザが決めなきゃいけない．実行可能か？といった観点では重要ではないけど，質を求めるのであれば重要な値．