読者です 読者をやめる 読者になる 読者になる

ML blog

備忘録を兼ねた IT 系のブログでございます。

Meituan技術チーム ( 美团点评技术团队 ) の勢い

中国の O2O 大手 Meituan (美団)の技術チームのサイトがあるのですが、自己紹介ページの文章が印象的でした。

关于我们 - 美团点评技术团队

内容をざっと翻訳してみると:


私達について

僅か数名のエンジニアの技術グループが、今では優秀な技術者が千名を超える規模になりました。Meituan技術チームは、Meituan O2Oビジネスの5年連続の急速な発展を支えかつ後押ししています。過去5年間で数百名に登る優秀な卒業生が校内募集により私たちに加わり、ここでの学習・成長につれ、多くのプロジェクトにて重要またはコアの開発力となっています。

日平均1.4回開かれる各種の技術シェアの場; 各技術に応じた多レベルの対面トレーニング; 社外から不定期に招かれる技術達人による講座と交流活動; 蔵書量4200冊を超える完全に貸出閲覧自由なMeituan図書館....

Meituan人はMeituanにとって最も重要なプロダクトであり、最高に優秀なインターネット研究開発チームを作り出すのが私達のの目標です。

技術トレーニング体系

Meituan技術学院が運営するトレーニングプラットフォーム上には、15を超える技術トレーニングプロジェクトがあります。上半期には23期を超え、累計で100クラスを超える専門技術トレーニングコース開設を担ってきました。技術トレーニング体系では、各チーム、各技術流域、基礎技能の3つの領域で異なるレベルの対面トレーニングが開設されます。講師陣は、第一線での実戦経験豊富な高級エンジニア、技術プロフェッショナルおよび各技術チームの高級管理者、技術副総裁などから構成され、各層のエンジニアに対し、業務、専門技能、共通素養等の全方位のトレーニングを提供します。

内部技術共有

2015年7月までに、内部技術共有プラットフォームにて197回の各種の完全にオープンな技術共有活動を開催しており、これはワーキングデイ平均で1.4回になります。この中には、各領域の技術の達人による素晴らしい講義や、“Roundtable”“吃货恳谈会”のような定期的に実施されるサロン活動が含まれます。技術学院は、毎年10回を超える“Techshow”、“大前端技术沙龙”等のテーマサロン活動の実施を担うことにより、内部の情報共有や技術交流を強化し、各チームによる研究開発成果と技術力の披露を支援しています。

業界技術交流

オープン性はインターネット技術の遺伝子です。私たちは不定期に業界の達人を招待し、著名技術チームをMeituanに招いて技術交流を行います。CSDN、infoQ、W3Tech等の組織と協力関係を持ち、CTO俱乐部、EGO走进美团、W3CTech走进名企などの技術交流活動を主催・共催します。

ハッカソン

Meituan技術チーム Hackathon は、Meituan技術学院が主催する、Meituanの全開発/製品ポジションに向けた大型技術競技活動であり、Meituan技術チームで最も重要なブランディング活動であり、Meituanの全エンジニアの祭日です。

興味、革新、実用は、Meituan技術チーム Hackathon のシンボルであり、私たちは製品と技術の革新に焦点を当て、技術の実践が第一の生産力であることを信念とします。2013年9月から今日まで、4回の Hackathon を成功裏に開催しました。400人が相次いで参加し、数十の有用なプロジェクトを生み出しました。この中で、移動会議室、Meituan図書館は重要な内部システムへと成長し、フロントエンド早期警報システム、Smart SQL Editor等は技術チームの内部ツールシステムとなっています。O2O大口顧客衛星システム、リアルタイム消費地図など多くのプロジェクトが異なる形でMeituanの商店やユーザーへのサービスを提供しています。

Meituan図書

書籍は人類進歩の踏み台ですが、Mieutanには、Meituan人が進歩するためのエレベータがあります:業界で先駆的なMeituan図書館です。図書館の蔵書量は現在4200冊を超え、图灵などの出版社と協力関係を築いています。図書館はMeituanの全同僚に開放しており、分散管理下でのP2P閲覧があり、閲覧の流れが非常にスムーズです。もし本が人気で借りれなかったり、新しすぎて図書館にない場合は?私たちは図書購入専用の経費があるため、申請すればOKです。

~~~


この技術チームのサイトでは大規模データ処理や機械学習などを含む成果を大量に公開していました。 文章归档 - 美团点评技术团队 (時間を見て、どんな文章があるか追記しようと思っています)

優秀な卒業生を獲得し、強力なチームを作り上げていく戦略は、上記文章からも伺えます(求職=ガールハントの文言のある女性に少々失礼な非公式求人ポスターも出回っているとのことですが、それくらい目立つ活動をしているのでしょうか http://news.cnad.com/html/Article/2015/0505/20150505114524251.shtml

若手中国エンジニアにとって非常に魅力的な環境に思えます。

ニューラルネットワークの学習過程をアニメーションにしてみた

人工知能 (AI) や機械学習 (Machine Learning) の分野では Deep Learning が話題になっていますが、ベースとなるニューラルネットワーク(Neural Network)の学習過程を、3D CG を使ってアニメーション化してみました。 NN(ニューラルネットワーク)の説明では、入力層→隠れ層→出力層とそれぞれの間を線で結んだ図が良く出てきますが、実際にどういうタイミングでどの部分が活性化するかなど直感的に視覚で捉えられないかと思ったのが動機です。

概要

百聞は一見に如かず、まずはちょこっと再生してみてください。

youtu.be

実際の学習コードの動きを忠実に反映した動画を作ろうと思ったのですが、良いものがないか検索した所、以下ページの Python コードが簡潔だったので使わせて頂きました。本格的な学習コードと比べるとかなり簡略化されていますが、まずは学習過程を直感的に視覚化するには十分と判断しました。

iamtrask.github.io

学習コードの説明

上記ページには2つコードが掲載されていますが、使用したのは2番めの「3 Layer Neural Network」です。日本語コメントを追加したものを貼っておきます。

import numpy as np

# ユーティリティ関数が定義されています。
def nonlin(x,deriv=False):
  if(deriv==True):
    # deriv 引数が True の場合は、
    # 微分で傾きを出しています。
    return x*(1-x)

  # シグモイド関数の結果を返しています。
  # ここで x 引数の値が0~1の値に変換されます。
  # 例えば、仮に x が1億でも限りなく1に近づきますが
  # 決して1 は超えません。
  # また x 引数がマイナス10億でも0は下回りません。
  return 1/(1+np.exp(-x))
    
# 入力値(X変数)、つまり学習に使うデータです。
# 3値配列の学習データを4件使用しています。
X = np.array([[0,0,1],   # 1件目の学習データ
              [0,1,1],   # 2件目の学習データ
              [1,0,1],   # 3件目の学習データ
              [1,1,1]])  # 4件目の学習データ
                
# あるべき出力値(y変数)、つまり上記4件の入力値(学習データ)を
# NNで計算した結果としてのあるべき値です。
# 教師あり学習の教師の役目を果たすべきもので、
# このあるべき値との誤差を小さくするように機械学習を進めます。
# ラベル値と呼ばれることもあります。
y = np.array([[0],     # 1件目の学習データに対応するあるべき出力値
              [1],     # 2件目の学習データに対応するあるべき出力値
              [1],     # 3件目の学習データに対応するあるべき出力値
              [0]])    # 4件目の学習データに対応するあるべき出力値

np.random.seed(1)

# randomly initialize our weights with mean 0
# ウェイト変数(syn0,syn1)を定義して、初期化しています。
# 初期化は平均が 0 になるように、ランダムな値を与えています。
# syn0 には、入力層⇒隠れ層の間のウェイト値を格納します。
syn0 = 2*np.random.random((3,4)) - 1
# syn1 には、隠れ層⇒出力層の間のウェイト値を格納します。
syn1 = 2*np.random.random((4,1)) - 1

# 4件一組の学習データによる学習を1回のループとして、
# ループ毎に入力値から計算した出力値とあるべき値(y)との誤差
# を小さくするよう学習(ウェイトを調整)します。
# ループを回すごとに、ウェイトが調整された結果として、
# 誤差が徐々に小さくなっていき、学習が進むことになります。
# 各ループのことを Epoch と呼ぶこともあります。
# アニメーションではループ1~3回と1998~2000回目を描画し、
# 学習の進み具合を視覚化しています。
for j in xrange(60000):

  #------------------------------------------------------
  # フォワード プロパゲーション (Forward Propagation)
  #------------------------------------------------------
  # Feed forward through layers 0, 1, and 2
  # 入力層(l0変数)に入力値(X変数、学習データ)をセットします。
  # 1回のループでは4件の学習データを行列計算で一度に扱うため、
  # 4件すべてを入力層に設定しています。
  l0 = X
  # 入力層の値に入力層⇒隠れ層間のウェイトを乗算してから、
  # 足し合わせ、nonlinユーティリティ関数内のシグモイド関数にて
  # 0~1の値に変換したものを、隠れ層(l1変数)の値とします。
  l1 = nonlin(np.dot(l0,syn0))
  # 同様に、隠れ層の値に、隠れ層⇒出力層間のウェイトにを乗算してから、
  # 足し合わせ、nonlinユーティリティ関数内のシグモイド関数にて
  # 0~1の値に変換したものを、出力層(l2変数)の値とします。
  # 今時の高校生は行列は習わないようですが、ウェイトを乗算して
  # 足し合わせる部分はドット積(内積)メソッド"np.dot"を呼んでいます。
  l2 = nonlin(np.dot(l1,syn1))

  # how much did we miss the target value?
  # あるべき出力値(y変数)から出力層(l2変数)の値を引き算することにより、
  # 出力層誤差(l2_error変数)を算出しています。
  # 4件の学習データとあるべき出力値に対応して、
  # 出力層誤差の値が4つ算出されます。
  l2_error = y - l2
    
  #------------------------------------------------------
  # バック プロパゲーション (Back Propagation)
  #------------------------------------------------------
  # 表示用の出力層誤差を計算します。
  # コードでは 10000 レコード毎に出力しますが、アニメーションでは、
  # フォワード プロパゲーション終了時に毎回表示します。
  # 表示用の出力誤差は、4件の出力層誤差の絶対値の平均です。
  if (j% 10000) == 0:
    print "Error:" + str(np.mean(np.abs(l2_error)))
        
  # in what direction is the target value?
  # were we really sure? if so, don't change too much.
  # 出力層誤差(l2_error変数)と、出力層(l2変数)の値の微分値
  # (nonlinユーティリティ関数を deliv 引数を True で呼び出して取得)
  # を乗算して、出力層デルタ(l2_delta)を算出します。
  # 注:出力層の値が0または1に近づくほど、微分値は小さくなり、
  # その分、ウェイト更新に使われるデルタの値も小さくなります。
  l2_delta = l2_error*nonlin(l2,deriv=True)

  # how much did each l1 value contribute to the l2 error (according to the weights)?
  # 出力層デルタ(l2_delta)と、隠れ層⇒出力層間のウェイト(syn1)の
  # 内積を算出し、隠れ層誤差(l1_error)とします。
  l1_error = l2_delta.dot(syn1.T)
    
  # in what direction is the target l1?
  # were we really sure? if so, don't change too much.
  # 隠れ層誤差(syn1)と、隠れ層(l1変数)の値の微分値
  # (nonlinユーティリティ関数を deliv 引数を True で呼び出して取得)
  # を乗算して、隠れ層デルタ(l1_delta)を算出します。
  l1_delta = l1_error * nonlin(l1,deriv=True)

  # 隠れ層(l1変数)の値と出力層デルタ(l2_delta)の内積を算出し、
  # 隠れ層⇒出力層間のウェイト(syn1変数)に加えることで、
  # ウェイトを更新(学習)します。
  syn1 += l1.T.dot(l2_delta)
  # 入力層(l0変数)の値と隠れ層デルタ(l1_delta)の内積を算出し、
  # 入力層⇒隠れ層間のウェイト(syn0変数)に加えることで、
  # ウェイトを更新(学習)します。
  syn0 += l0.T.dot(l1_delta)

アニメーションの説明

レイアウトについて

動画の各部位の説明です。 f:id:hhok:20161107185741p:plain f:id:hhok:20161107185844p:plain f:id:hhok:20161107185851p:plain  
 
以下、処理順序に画面を説明します。


初期化


 [入力層⇒隠れ層の間のウェイト値]の初期化

まず、[入力層⇒隠れ層の間のウェイト値]を初期化します。 対応コード部位:

# ウェイト変数(syn0,syn1)を定義して、初期化しています。
# 初期化は平均が 0 になるように、ランダムな値を与えています。
# syn0 には、[入力層⇒隠れ層の間のウェイト値]を格納します。
syn0 = 2*np.random.random((3,4)) - 1

注:図ではウェイトの大小を線の直径の大小で表しています。 f:id:hhok:20161107191045p:plain

次の値が設定されます:
[[-0.16595599 0.44064899 -0.99977125 -0.39533485]
[-0.70648822 -0.81532281 -0.62747958 -0.30887855]
[-0.20646505 0.07763347 -0.16161097 0.370439 ]]

 [隠れ層⇒出力層の間のウェイト値]の初期化

次に、[隠れ層⇒出力層の間のウェイト値]を初期化します。

# syn1 には、[隠れ層⇒出力層の間のウェイト値]を格納します。
syn1 = 2*np.random.random((4,1)) - 1

f:id:hhok:20161107191147p:plain

次の値が設定されます:
[[-0.5910955 ]
[ 0.75623487]
[-0.94522481]
[ 0.34093502]]


学習の開始


学習を開始します。
ループ内のセフォワード プロパゲーションとバック プロパゲーションを繰り返すことにより、学習を進めます。

# 4件一組の学習データによる学習を1回のループとして、
# ループ毎に入力値から計算した出力値とあるべき値(y)との誤差
# を小さくするよう学習(ウェイトを調整)します。
# ループを回すごとに、ウェイトが調整された結果として、
# 誤差が徐々に小さくなっていき、学習が進むことになります。
# 各ループのことを Epoch と呼ぶこともあります。
# アニメーションではループ1~3回と1998~2000回目を描画し、
# 学習の進み具合を視覚化しています。
for j in xrange(60000):

最初のループを開始します。 f:id:hhok:20161107194604p:plain


フォワード プロパゲーション


4件の [学習レコード] を使用したフォワード プロパゲーションにより、それぞれ [出力値] を算出します。[出力値] は [あるべき出力値] と比較する形で、後で誤差の算出に使用されます。

 1番目の [学習レコード] の処理

  [入力層] の設定

1番目の [学習レコード] [0,0,1] を [入力層] に設定します。

  l0 = X

(コードでは行列演算のために4件の [学習レコード] をまとめて設定しています)
  
注:数値の大小を図形の大小で表しています。 f:id:hhok:20161107194938p:plain

  [隠れ層] の1番目ノードの設定

[入力層の値] と、[入力層⇒隠れ層間のウェイト] の内積を算出し、シグモイド関数で0~1の範囲に変換した数値を、[隠れ層] の1番目のノードの値に設定します。

  l1 = nonlin(np.dot(l0,syn0))

(コードでは行列演算により4件の [学習レコード] と [隠れ層] のすべてのノード値をまとめて計算しています)
f:id:hhok:20161107235853p:plain 検算:

> z = 0.0*-0.16595599 + 0.0*-0.70648822 + 1.0*-0.20646505
> 1/(1+np.exp(-z))
0.44856631662664037

  [隠れ層] の2番目ノードの設定

同様に、[隠れ層] の2番目ノードを設定します。 f:id:hhok:20161108010348p:plain

> z = 0.0*0.44064899 + 0.0*-0.81532281 + 1.0*0.07763347
> 1/(1+np.exp(-z))
0.51939862559049366

  [隠れ層] の3番目ノードの設定

同様に、[隠れ層] の3番目ノードを設定します。 f:id:hhok:20161108010949p:plain

> z = 0.0*-0.99977125 + 0.0*-0.62747958 + 1.0*-0.16161097
> 1/(1+np.exp(-z))
0.45968496535549458

  [隠れ層] の4番目ノードの設定

同様に、[隠れ層] の4番目ノードを設定します。 f:id:hhok:20161108011154p:plain

> z = 0.0*-0.39533485 + 0.0*-0.30887855 + 1.0*0.370439
> 1/(1+np.exp(-z))
0.5915650520492296

  [出力層] の設定

[隠れ層の値] と、[隠れ層⇒出力層間のウェイト] の内積を算出し、シグモイド関数で0~1の範囲に変換した数値を、[出力層の値] に設定します。

  l2 = nonlin(np.dot(l1,syn1))

(コードでは行列演算により4件の [学習レコード] 分をまとめて計算しています)

f:id:hhok:20161108011759p:plain

> z = 0.448566316626640*-0.5910955 + 0.519398625590494*0.75623487 + 0.459684965355495*-0.94522481 + 0.591565052049230*0.34093502 
> 1/(1+np.exp(-z))
0.47372957108332214

[あるべき出力値] である 0 に対して、[出力値] は 0.47372957108332214 なので、[出力誤差] は -0.47372957108332214 となります。

 2番目の [学習レコード] の処理

1番目の [学習レコード] と同様に、2番目の [学習レコード] を処理します。

  [入力層] の設定

2番目の [学習レコード] [0,1,1] を [入力層] に設定します。 f:id:hhok:20161108014130p:plain

  [隠れ層] の1番目ノードの設定

f:id:hhok:20161108014207p:plain

> z = 0.0*-0.16595599 + 1.0*-0.70648822 + 1.0*-0.20646505
> 1/(1+np.exp(-z))
0.28639588721102011

  [隠れ層] の2番目ノードの設定

f:id:hhok:20161108014233p:plain

> z = 0.0*0.44064899 + 1.0*-0.81532281 + 1.0*0.07763347
> 1/(1+np.exp(-z))
0.32350962799042776

  [隠れ層] の3番目ノードの設定

f:id:hhok:20161108014242p:plain

> z = 0.0*-0.99977125 + 1.0*-0.62747958 + 1.0*-0.16161097
> 1/(1+np.exp(-z))
0.3123639793175344

  [隠れ層] の4番目ノードの設定

f:id:hhok:20161108014255p:plain

> z = 0.0*-0.39533485 + 1.0*-0.30887855 + 1.0*0.370439
> 1/(1+np.exp(-z))
0.51538525402952473

  [出力層] の設定

f:id:hhok:20161108014304p:plain

> z = 0.286395887211020*-0.5910955 + 0.323509627990428*0.75623487 + 0.312363979317534*-0.94522481 + 0.515385254029525*0.34093502 
> 1/(1+np.exp(-z))
0.48895695615901025

[あるべき出力値] である 1 に対して、[出力値] は 0.48895695615901025 なので、[出力誤差] は 0.5110430438409898 となります。

 3番目の [学習レコード] の処理

同様に3番目の [学習レコード] [1,0,1] を処理すると以下の結果になります。 f:id:hhok:20161108021200p:plain

> z = 0.407956142741789*-0.5910955 + 0.626746060390834*0.75623487 + 0.238416219308552*-0.94522481 + 0.493776358949476*0.34093502 
> 1/(1+np.exp(-z))
0.54384085630684809

あるべき [出力値] である 1 に対して、[出力値] は 0.54384085630684809 なので、[出力誤差] は 0.4561591436931519 となります。

 4番目の [学習レコード] の処理

同様に4番目の [学習レコード] [1,1,1] を処理すると以下の結果になります。 f:id:hhok:20161108022544p:plain

> z = 0.253712484571769*-0.5910955 + 0.426281153143997*0.75623487 + 0.143212326822233*-0.94522481 + 0.417322537900416*0.34093502 
> 1/(1+np.exp(-z))
0.54470836902350805

[あるべき出力値] である 0 に対して、[出力値] は 0.544708369023508 なので、[出力誤差] は -0.544708369023508 となります。


バック プロパゲーション


4件の [学習レコード] を処理し、各 [出力層誤差] の計算が完了した後、ウェイトを更新するためにバック プロパゲーションを実施します。

 [表示用の出力層誤差] の計算

各 [学習レコード] 処理から計算された4件の [出力層誤差] の絶対値を取り、それらの平均値を [表示用の出力層誤差] として表示します。

np.mean(np.abs(l2_error))

f:id:hhok:20161108024122p:plain

> (abs(-0.473729571083322)+abs(0.511043043840990)+abs(0.456159143693152)+abs(-0.544708369023508)) / 4
0.496410031910243

 [出力層デルタ] の計算

各 [出力層誤差] の値に、[出力層の値] の微分値を乗算して、[出力層デルタ] を計算します。[出力層デルタ] は後で [隠れ層⇒出力層間のウェイト] に加算される形でウェイトの調整(学習)に使われます。
[出力層の値] が0または1に近く確信度が高い場合、[微分値] は小さく、逆に0または1より遠く確信度は低い場合、[微分値] は高くなります。つまり確信度が大きく [微分値] が小さいと、[微分値] を [出力層誤差] に乗算した [出力層デルタ] も小さくなり、結果としてウェイトの更新量が小さくなります。

  l2_delta = l2_error*nonlin(l2,deriv=True)

[出力層デルタ] として以下の配列が得られます:
[[-0.11810546]
[ 0.12769844]
[ 0.11316304]
[-0.13508831]]

検算:

> x = 0.473729571083322  # 1番目のレコードの出力値
> d = x*(1-x)            # 微分値を計算
> d
0.24930986456453375
> -0.473729571083322 * d # 出力誤差と微分値を乗算
-0.11810545520699767
> x = 0.488956956159010  # 2番目のレコードの出力値
> d = x*(1-x)            # 微分値を計算
> d
0.24987805118272596
> 0.511043043840990 * d  # 出力誤差と微分値を乗算
0.12769843986547497
> x = 0.543840856306848  # 3番目のレコードの出力値
> d = x*(1-x)            # 微分値を計算
> d
0.24807797931828232
> 0.456159143693152 * d  # 出力誤差と微分値を乗算
0.11316303861495514
> x = 0.544708369023508  # 4番目のレコードの出力値
> d = x*(1-x)            # 微分値を計算
> d
0.24800116173925782
> -0.544708369023508 * d # 出力誤差と微分値を乗算
-0.13508830832692637

 [隠れ層誤差] の計算

[出力層デルタ] と [隠れ層⇒出力層間のウェイト] の内積により、[隠れ層誤差] を計算します。4x1 配列の [出力層デルタ] と 1x4 配列の [隠れ層⇒出力層間のウェイト] の内積により 4x4 配列の [隠れ層誤差] が得られます。

  l1_error = l2_delta.dot(syn1.T)

[隠れ層誤差] として以下の配列が得られます:
[[ 0.0698116 -0.08931546 0.11163621 -0.04026629]
[-0.07548197 0.09657001 -0.12070373 0.04353687]
[-0.06689016 0.08557784 -0.10696451 0.03858124]
[ 0.07985009 -0.10215849 0.12768882 -0.04605634]]

検算:

> dlt = -0.11810545520699767    # 1番目の出力層デルタ
> s0 = np.array([-0.5910955,0.75623487,-0.94522481,0.34093502]) # 隠れ層⇒出力層間のウェイト
> print(dlt * s0)
[ 0.0698116  -0.08931546  0.11163621 -0.04026629]
> dlt =0.12769843986547497     # 2番目の出力層デルタ
> s0 = np.array([-0.5910955,0.75623487,-0.94522481,0.34093502]) # 隠れ層⇒出力層間のウェイト
> print(dlt * s0)
[-0.07548197  0.09657001 -0.12070373  0.04353687]
> dlt =0.11316303861495514     # 3番目の出力層デルタ
> s0 = np.array([-0.5910955,0.75623487,-0.94522481,0.34093502]) # 隠れ層⇒出力層間のウェイト
> print(dlt * s0)
[-0.06689016  0.08557784 -0.10696451  0.03858124]
> dlt =-0.13508830832692637    # 4番目の出力層デルタ
> s0 = np.array([-0.5910955,0.75623487,-0.94522481,0.34093502]) # 隠れ層⇒出力層間のウェイト
> print(dlt * s0)
[ 0.07985009 -0.10215849  0.12768882 -0.04605634]

 [隠れ層デルタ] の計算

各 [隠れ層誤差] の値に、[隠れ層の値] の微分値を乗算して、[隠れ層デルタ] を計算します。[隠れ層デルタ] は後で [入力層⇒隠れ層間のウェイト] に加算される形でウェイトの調整(学習)に使われます。

  l1_delta = l1_error * nonlin(l1,deriv=True)

[隠れ層デルタ] として以下の配列が得られます:
[[ 0.01726822 -0.02229526 0.02772761 -0.00972897]
[-0.0154265 0.02113446 -0.02592628 0.01087391]
[-0.01615584 0.02001969 -0.01942197 0.00964382]
[ 0.01511901 -0.02498445 0.01566774 -0.01119926]]

検算:

> # 隠れ層誤差
> l1err = np.array([[ 0.06981161, -0.08931547,  0.11163621, -0.04026629],
>        [-0.07548197,  0.09657001, -0.12070373,  0.04353687],
>        [-0.06689016,  0.08557784, -0.10696451,  0.03858124],
>        [ 0.07985009, -0.10215849,  0.12768882, -0.04605634]])
> # 隠れ層の値
> l1 = np.array([[ 0.44856632,  0.51939863,  0.45968497,  0.59156505],
>  [ 0.28639589,  0.32350963,  0.31236398,  0.51538526],
>  [ 0.40795614,  0.62674606,  0.23841622,  0.49377636],
>  [ 0.25371248,  0.42628115,  0.14321233,  0.41732254]])
> # 隠れ層の値の微分値を計算
> deliv = l1 * (1 - l1) 
> print(deliv)
 0.24735458  0.24962369  0.2483747   0.24161584]
 [ 0.20437328  0.21885115  0.21479272  0.24976329]
 [ 0.24152793  0.23393544  0.18157393  0.24996127]
 [ 0.18934246  0.24456553  0.12270256  0.24316444]]
> # 隠れ層誤差と隠れ層の値の微分値を乗算して隠れ層デルタを算出
> print(l1err * deliv)
[[ 0.01726822 -0.02229526  0.02772761 -0.00972897]
 [-0.0154265   0.02113446 -0.02592628  0.01087391]
 [-0.01615584  0.02001969 -0.01942197  0.00964382]
 [ 0.01511901 -0.02498445  0.01566774 -0.01119926]]

 [隠れ層⇒出力層間のウェイト] の更新

[隠れ層の値] と [出力層デルタ] の内積を算出し、 [隠れ層⇒出力層間のウェイト] に加えることで、 ウェイトを更新(学習)します。

  syn1 += l1.T.dot(l2_delta)

f:id:hhok:20161108161920p:plain

次の値が [隠れ層⇒出力層間のウェイト] に設定されます:
[[-0.59560936]
[ 0.74954163]
[-0.95199413]
[ 0.33638369]]

検算:

> # 隠れ層の値
> l1 = np.array([[ 0.44856632,  0.51939863,  0.45968497,  0.59156505],
>  [ 0.28639589,  0.32350963,  0.31236398,  0.51538526],
>  [ 0.40795614,  0.62674606,  0.23841622,  0.49377636],
>  [ 0.25371248,  0.42628115,  0.14321233,  0.41732254]])
> # 出力層デルタ
> l2delta = np.array([[-0.11810546],
>  [ 0.12769844],
>  [ 0.11316304],
>  [-0.13508831]])
> # 更新値の計算
> upd = l1.T.dot(l2delta)
> print(upd)
[[-0.00451386]
 [-0.00669325]
 [-0.00676932]
 [-0.00455133]]
> # 隠れ層⇒出力層間のウェイト
> syn1 = np.array([[-0.5910955 ],
>  [ 0.75623487],
>  [-0.94522481],
>  [ 0.34093502]])
> # 更新値を加算してウェイトを更新
> syn1 = syn1 + upd
> print(syn1)
[[-0.59560936]
 [ 0.74954162]
 [-0.95199413]
 [ 0.33638369]]

 [入力層⇒隠れ層間のウェイト] の更新

[入力層の値] と [隠れ層デルタ] の内積を算出し、 [入力層⇒隠れ層間のウェイト] に加えることで、 ウェイトを更新(学習)します。

  syn0 += l0.T.dot(l1_delta)

f:id:hhok:20161108162005p:plain

次の値が [入力層⇒隠れ層間のウェイト] 設定されます:
[[-0.16699282 0.43568423 -1.00352547 -0.3968903 ]
[-0.7067957 -0.8191728 -0.63773812 -0.3092039 ]
[-0.20566016 0.07150791 -0.16356387 0.37002849]]

検算:

> # 入力層の値
> l0 = np.array([[0, 0, 1],
>  [0, 1, 1],
>  [1, 0, 1],
>  [1, 1, 1]])
> # 隠れ層デルタ
> l1delta = np.array([[ 0.01726822, -0.02229526,  0.02772761, -0.00972897],
>  [-0.0154265,   0.02113446, -0.02592628,  0.01087391],
>  [-0.01615584,  0.02001969, -0.01942197,  0.00964382],
>  [ 0.01511901, -0.02498445,  0.01566774, -0.01119926]])
> # 更新値の計算
> upd = l0.T.dot(l1delta)
> print(upd)
[[-0.00103683 -0.00496476 -0.00375423 -0.00155544]
 [-0.00030749 -0.00384999 -0.01025854 -0.00032535]
 [ 0.00080489 -0.00612556 -0.0019529  -0.0004105 ]]
> # 入力層⇒隠れ層間のウェイト
> syn0 = np.array([[-0.16595599,  0.44064899, -0.99977125, -0.39533485],
>  [-0.70648822, -0.81532281, -0.62747958, -0.30887855],
>  [-0.20646505,  0.07763347, -0.16161097,  0.370439  ]])
> # 更新値を加算してウェイトを更新
> syn0 = syn0 + upd
> print(syn0)
[[-0.16699282  0.43568423 -1.00352548 -0.39689029]
 [-0.70679571 -0.8191728  -0.63773812 -0.3092039 ]
 [-0.20566016  0.07150791 -0.16356387  0.3700285 ]]

学習の経過


上記のフォワード プロパゲーションとバック プロパゲーションの繰り返しループにより学習を進めます。以下に各ループ終了時の状態を示します。

2回目ループの終了時

2回目ループ終了時には、下図となります。[表示用の出力層誤差] が1回目の 0.49641 から 0.49630 に減っており、ウェイトも更新されています。

f:id:hhok:20161108173742p:plain

1998回目ループの終了時

1998回目ループ終了時までジャンプした結果です。[表示用の出力層誤差] が2回目の 0.49630 から 0.02415 と大幅に減っています。また、ウェイトも大幅に更新されており、ウェイトの大小を表す線太さに反映されています。[出力値] と [あるべき出力値] を表す左端の数字と四角形の大きさが非常に近づいており、学習が進んだことが分かります。

f:id:hhok:20161108173805p:plain

1999回目ループの終了時

1999回目ループ終了時には、[表示用の出力層誤差] が1998回目の 0.02415 から 0.02414 とごく僅かながら減少しています。また、ウェイトの変化で見えるものは赤枠でかこった一部となっています。

f:id:hhok:20161108181538p:plain

2000回目ループの終了時

2000回目ループ終了時でも、[表示用の出力層誤差] が1999回目の 0.02414 から 0.02413 と僅かに減少しています。

f:id:hhok:20161108181557p:plain

おわりに

試行錯誤しながら作ってみました。至らぬ点がございましたらご容赦ください。
 
my TODO:

  1. バックプロパゲーションの部分をより詳細に可視化する方法を考えたい。
  2. 学習が進むと、ウェイト更新が小さくなる状態を記載したい。
  3. GPU 使用でもレンダリングが激遅かった。早いきれいな方法を探したい。
  4. 3DCG 生成につかった python コードを公開できるくらい整理したい。

Apache Sparkや機械学習: 海外オンライン講座の受講感想

機械学習Apache Spark に関して、最近流行りの海外オンライン講座を幾つか受けてみました。 コースをお探し中の方の参考になるかもしれませんので、以下に感想を残しておきます。

視認性には優れませんが、受けた講座順に時系列で記します。  
 

Implementing Predictive Analytics with Spark in Azure HDInsight

EDX, by Microsoft

2016年4月に受講したのですが、講座ページの公開は修了していて、現在は以下講座に変わっているようです:

www.edx.org

新旧講座でどこが変わっているか違いを見たのですが、新たにR言語統合が加わったりかなり変更があるようです。 旧講座が私にとって初めてのオンライン講座受講だったのですが、いきなり時系列分析分野の ARIMA の知識を前提とした展開だったり、Final Exam の難易度もやや高く、不合格となった学生からのコメントもフォーラムで目につきました。他の講座で基礎を固めてから受講すべき講座との感想も持ちつつ、分散処理と機械学習分野の大まかな雰囲気を整理するには役立った講座と思います。Azure で Spark ! など新鮮な驚きもあり、以降 Microsoft 系の講座を多く受けることになりました。  
  
 

Introduction to R for Data Science

EDX, by Microsoft、2016年5月受講

www.edx.org データサイエンス分野では R が共通言語のようで、統計検定試験でも出題に出てきていたので、受講しておくことにしました。 こちらの講座の課題は、DataCamp の演習環境を使用するもので、R言語の文法になれるために非常に役立ちました。やはり一度手を動かして触っておくと、後で忘れたと思っていても楽に思い出せるようです。 www.datacamp.com   
 

Programming in R for Data Science

EDX, by Microsoft、2016年5月受講

www.edx.org 基礎から回帰分析、SQL DB接続、作図(ggplot2)など一通り紹介がありました。ggmap による地図統合など視覚的にインパクトもあり楽しめました。ただ、講師の方の英語の発音は非ネイティブスピーカーの私にはやや聞き取り難かったです。その後 R 言語を AzureML と組み合わせて使うプチ機会があったのですが、この講座と金先生の以下R本に目を通した上で、後は必要な実装詳細を都度Google検索で調べるなどの方法で、望む機能を実装することができました。

Rによるデータサイエンス-データ解析の基礎から最新手法まで

Rによるデータサイエンス-データ解析の基礎から最新手法まで

  
 

Principles of Machine Learning

EDX, by Microsoft、2016年7月受講

www.edx.org この講座での一番の収穫は、Azure ML Studio で手軽に機械学習モデルを構築できることと、その具体的な方法や作法を理解できた点です。マウスで視覚的にモデルを組み上げられるよう配慮されていて、面倒と思いがちな作業に対する心理的な負担がかなり軽減されます。Python や R 言語など既存のコードやスキルも使い続ける点でオープン性にも気を配っていることが感じられます。SVM なんかもドラッグアンドドロップで使えるようですが、台湾大学のChih-Jen Lin(林智仁、LIBSVM の作者)先生のホームページに来年まで Microsoft 訪問とあった理由もこの辺でしょうか。こんなプラットフォームまで出てきて、昨今の機械学習や AI のトレンドがもし本物であれば一気に大衆化しそうですが、どうなのでしょうか。講座では Adaboost が予測性能が最も高いアルゴリズムの一つとして取り上げられており、Adaboost の説明は直感的な理解を助けてくれる点で良かったです。演習は R と Python が用意されており、両方やってみた結果、R の Python との違いや向き不向きを比較体感することができました。  
 

Applied Machine Learning

EDX, by Microsoft、2016年8月受講

www.edx.org 時系列(ARIMA)や地理分析(variogram)の2単元では非常に多くを学べました。他の講座でこのあたりを詳しく扱っているものはあるのでしょうか。AR と MA の違いは直感で理解できるようになりますし、背景を理解した上でパラメータチューニングについて説明があります。講座の先生も言及していましたが、トレンドや季節変動の時系列の分解を初めて目の当たりにすると手品を見せられた気分になりますが、種明かしとしての背後で動いている仕組みを丁寧に説明してくれます。地理分析の理論的な紹介は時系列の単元ほど直感的ではありませんが、応用できる場は多くありそうで想像を膨らませてくれる内容でした。こちらは単元によって R と Python を向き不向きで使い分けていて、時系列や地理分析は R を使っています。  
 

Introduction to Apache Spark

EDX, by カリフォルニア大学バークレー校、2016年7月受講

www.edx.org 講座シリーズ『Data Science and Engineering with Apache® Spark™ | edX』を構成する3講座のうちの最初のものでした。演習課題に Web サーバーのログ解析がありました。以下の資料に事前に目を通していたので、本講座の演習で手を動かすことにより、知識の固定化に役立ちました。

1.Spark のオンラインドキュメント

Overview - Spark 2.0.2 Documentation

2.入門書籍(日本語版も出ていたのですね)

Learning Spark: Lightning-Fast Data Analysis

Learning Spark: Lightning-Fast Data Analysis

  • 作者: Holden Karau,Andy Konwinski,Patrick Wendell,Matei Zaharia
  • 出版社/メーカー: Oreilly & Associates Inc
  • 発売日: 2015/02/27
  • メディア: ペーパーバック
  • この商品を含むブログを見る

3.志の高い有志様によるサイト
AMPcamp-ja (掲載コードを一通り走らせて勉強させて頂きました)  
 

Distributed Machine Learning with Apache Spark

EDX, by カリフォルニア大学バークレー校、2016年8月受講

www.edx.org この講座は少々苦労しました。上記の Spark シリーズ初回講座は受講終了期限まで3ヶ月ほどの猶予があったので、第2弾のこちらもゆっくり受講すれば良いと思いきや、実は受講期間が1ヶ月でした。気づいたときは受講期限が残り1週間。焦って手を付けたのもあり、また公開したての講座でしたので演習問題に一部不備があったりで、かなり手こずりました。最終的にはフォーラムでの他の受講生のやりとりを参考に完了できましたが、やや消化不良でした。機械学習の取扱についてはAPIを呼び出すだけでなく、アルゴリズムも理解させようと講座が組まれていましたが、Spark 特有の作法を明確に認識できるためにも、このあたりは以下で述べる Andrew Ng 先生の Machine Learning 講座を終えてから手を付けるほうが深い理解が得られると思います。PCA演習課題での脳活度プロットの美しさは見ものです。  
 

Big Data Analysis with Apache Spark

EDX, by カリフォルニア大学バークレー校、2016年8月受講 https://www.edx.org/course/big-data-analysis-apache-spark-uc-berkeleyx-cs110x

ビッグデータ分析と銘打っていますが、機械学習が中心の印象です(例えば本3講座シリーズにて、Spark のグラフ計算(GraphX)の紹介はありませんでした)。上記 Microsoft 講座でもありましたが、機械学習の各種アルゴリズムの性能比較が演習に取り入れられていて楽しめました。本講座の講師の方が過去に発電所の発電予測の案件を担当したとあり、演習でも発電所の予測が取り上げられていました。その中で、LinearRegression、DecisionTreeRegressor、RandomForestRegressor の予測比較では、RandomForest が良い成績を収めていました。他の演習では、Matrix Factorization、TF-IDF が取り上げられていました。  
 

Machine Learning

Coursera, by スタンフォード大学 Andrew Ng(吳恩達)先生、2016年9月受講

www.coursera.org 機械学習分野では鉄板の人気講座とのことです。こちらを最後に受けることになったのですが、それでも、それだからこそこの講座の素晴らしさを実感できました。まずアルゴリズムの「直感」を得ることを優先にした授業と内容の濃さは抜群でした。講座の紹介ビデオを見た時は、何やら人がよく頼りなさげなお兄さんがニコニコしている印象でしかなかったのですが、こちらが Deep Learning の猫の件でもあちこちで名前が出ている大先生なのですね。本当にすみません。香港人シンガポールの大学卒業→から今の地位を築くまでのサクセスストーリーとしての人生ドラマにも興味がわきます。こういう人が正当に評価される米国社会の懐の深さについても改めて敬服しました。Octave(Matlab)は Ng 先生が私を信じてと言っていたとおり、確かに使いやすかったです。

その他

機械学習とは切っても切り離せない統計学についても学んだのですが、オンライン受験が開始されるとアナウンスされていた統計検定受験を目標にしていました。この検定の問題はよく考えられた良問が多く、日本で統計学を普及させたいとの思いが伝わってくるものでした。受験した2級は近年難易度もやや上がっているようで、合格はできましたが、実力が得点に反映されるように難易度の高い問題もバランス良く散りばめられていて、高得点での合格には盤石の実力が必要との印象を持ちました。

www.toukei-kentei.jp

統計関連の学習には Khan アカデミーも使わせて頂きました。 www.khanacademy.org  
 

まとめ

海外オンライン講座は、作りにやや荒削りな部分が気になったことはあったものの、受講は大変有意義なものでした。ベンダー主催の講座では、知識だけでなく、実装に直結した作法まで面倒を見てくれます。無料でこのような知識をどんどん吸収できる時代に生まれた今の学生さんたちは本当に羨ましいです。ちなみに上記講座はすべて無料でも受講を完了できますが、私の場合は半数ほどは対価を払って Certificate (受講合格の証書)を入手しました。

(draft)FFM (Field-aware Factorization Machines)を理解したい

はじめに

FFM(Field-aware Factorization Machines)は、機械学習分野で比較的新出のアルゴリズムです。CTR(click-through rate)やCVR(conversion rate)の予測コンペにおいて、FM(Factorization Machines)と共に良い成績を収めているようです。

誰が作ったの?

Yu-Chin Juan(阮毓欽)さん等の台湾大学の出身者・在籍者により提起されたもので、論文『Field-aware Factorization Machines for CTR Prediction』台湾大学サイトにあります。私がこのアルゴリズムについて知ったのは、apache sparkのオンライン講座のCTR予測の演習問題で、とあるkaggleコンペ(criteo)のデータを使っていたのですが、そのコンペでFFMの提起者であるYu-Chin JuanらがFFMを駆使して優勝していたのを見たからでした。ちなみにFFM作者Yu-Chin Juanさんは現在はコンペ主催者criteo社に在籍のようです。Yu-Chin Juanさんらは、もう一つのkaggleコンペ(avazu)でもFFMを使って優勝しています。

由来は?

Yu-Chin Juanさんらは、PITFMichael Jahrer氏の論文でのFieldの概念を取り入れる形で、FM(Factorization Machines)の改良版としてFFM(Field-aware Factorization Machines)を提起しました。次章では、まずFMの概略を説明してから、FFMの変更点について述べます。

必要な知識

協調フィルタリングでよく言及されるMF(Matrix Factorization)を理解していると良いようです。特にk次元に削減された表現の部分です。MFの理解には、人気のCouseraのMachine Learning講座もおすすめです。FMはMFをより汎用化したものと言えます。

FM(Factorization Machines)

FMは現在googleに在籍するSteffen Rendle氏により2010年に提起されたとのことですが、論文PDFを見ると表題に大阪大学の名前があります。論文でも強調されていますが、SVM等とは異なり、FMは非常にスパース(sparse)なデータ、つまりスカスカで値がほとんど入っていないデータからも学習が可能な点が長所です。

スパースなデータ、One-Hot-Encoding

ここで言うスパースなデータが生じる原因の一つとして、One-Hot-Encodingという手法で、カテゴリカルデータから新たな特徴量を生成する過程が挙げられます。

One-Hot-Encoding前:

東京
沖縄
北海道
東京

One-Hot-Encoding後:

県:東京 県:沖縄 県:北海道
1 0 0
0 1 0
0 0 1
1 0 0

上記例では、3県のみなので、3列が特徴量として生成されていますが、47都道府県であれば、47の特徴量が生まれます。また、各行を見たとき、47の特徴量のうち、1つのみが有効(非ゼロ)である点で、スパースなデータ、すまりスカスカなデータとなります。

例えば、上記spark講座の演習例では、One-Hot-Encoding後に特徴量が20万に増加し、値が入っている割合(Sparsity)が0.02%といった具合でした。更に本番のより大規模なコンペデータ(criteo)ではこの20万が3000万以上に激増します。(注:このため上記演習では、ハッシュ法で特徴量を十分の一に減らす処理も紹介しています)。

特徴量の組み合わせ

上記のようなスパースデータにて、特徴量の間に関連性がある場合を考えます。

性別:男 性別:女 製品:スカート ... クリックあり
1 0 1 ... 0
0 1 1 ... 1

上記は女性はスカートと関連が強いことをイメージしました。このような関連性は男児と少年ジャンプ、バレンタインデーとチョコレート、東アジア地域とお箸など様々なものが想定されます。

この関連性を抽出するため、特徴量間の組み合わせもモデリングします。この際、特徴量の両方が有効(非ゼロ)の場合のみが対象となります。しかしながら、スパースなデータで生ずる困難として、データ内の値がスカスカなため、学習に使える十分なデータが揃わなく、学習の精度が上がらない問題があります。

つまり、以下数式モデルの第3項目のウェイト w_{ij}の学習のための充分な x_i y_jの組み合わせが揃わないことになります。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^nw_{ij}x_ix_j

論文PDFでは次のような例を挙げていました: 典型的な協調フィルタリングでは、トレーニングデータ内の組み合わせはせいぜい一度しか出現せず、テストデータ内の組み合わせは通常トレーニングデータでは全く現れない。例えば、Aliceさんが映画Titanicを見た組み合わせ(Alice, Titanic)は1つであり、Aliceさんが映画Star Trekを見た組み合わせ(Alice, Star Trek)は存在しない。

行列分解

この問題を解決するために、各特徴量に k 次元のベクトルを持たせておいて、そのベクトルの内積で組み合わせのウェイトを表現します。  <\mathbf{v}_i ,\mathbf{v}_j> の部分です。このあたりはMF(Matrix Factorization)を把握していると理解しやすそうです。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_i ,\mathbf{v}_j>x_ix_j
 \displaystyle
<\mathbf{v}_i ,\mathbf{v}_j>:=\sum_{c=1}^kv_{i,c}\cdot v_{j,c}

 \mathbf{v}_i x_iの k 次元ベクトルで、  \mathbf{v}_j x_jの k 次元ベクトルです。

これで何が良いかというと、例えば <\mathbf{v}_i ,\mathbf{v}_j> <\mathbf{v}_i ,\mathbf{v}_l>とでは、お互いに \mathbf{v}_iを共有しているため、 \mathbf{v}_iをより多くのサンプルから学習することができます。もともとの w_{ij} w_{il}形式の場合、それぞれが全く独立なものとして取り扱われます。

AliceさんがStar Trekを見た組み合わせ(Alice, Star Trek)が存在しないケースでも、 \mathbf{v}_{alice} \mathbf{v}_{startrek}を活用できるため、相互作用を推定することができます。

FFM(Field-aware Factorization Machines)

次に、FMに対してFFMが拡張された箇所を説明します。

Field-aware

FMでの各特徴量に対するK次元ベクトルは1つしか存在しません。そのため、(商品=A, 日付=1/1)と(商品=A, 性別=男)の組み合わせでは、商品AのK次元ベクトルが、日付と性別という異なる対象に対して共有されます。FFMでは、商品、日付、性別などのくくりをFieldと捉え、Fieldごとに異なるk次元ベクトルを使用します。例えば、日付Fieldの組み合わせ対象に対する商品AのK次元ベクトル、性別Fieldの組み合わせ対象に対する商品AのK次元ベクトルといったように、各特徴量ごとに使い分けて学習します。

 \displaystyle
\hat{y}(\mathbf{x}):=w_0 + \sum_{i=i}^nw_ix_i + \sum_{i=1}^n\sum_{j=i+1}^n<\mathbf{v}_{if(j)} ,\mathbf{v}_{if(i)}>x_ix_j

jが属するフィールドとiが属するフィールドを表す f(j) f(i)が追加されており、組み合わされる対象のFieldごとにベクトルを使い分けていることが分かります。

展開例

ユーザ 映画 ジャンル 価格
太郎 影武者 コメディ、アクション 999
ユーザ:太郎 映画:影武者 ジャンル:コメディ ジャンル:アクション 価格
1 1 1 1 999
FMの場合

FMの場合、モデル式の第3項(組み合わせ項)は以下のように展開されます。

  <Vユーザ:太郎, V映画:影武者> · xユーザ:太郎 · x映画:影武者 
+ <Vユーザ:太郎, Vジャンル:コメディ> · xユーザ:太郎 · xジャンル:コメディ 
+ <Vユーザ:太郎, Vジャンル:アクション> · xユーザ:太郎 · xジャンル:アクション 
+ <Vユーザ:太郎, V価格> · xユーザ:太郎 · x価格

+ <V映画:影武者, Vジャンル:コメディ> · x映画:影武者 · xジャンル:コメディ 
+ <V映画:影武者, Vジャンル:アクション> · x映画:影武者 · xジャンル:アクション 
+ <V映画:影武者, V価格> · x映画:影武者 · x価格

+ <Vジャンル:コメディ, Vジャンル:アクションi> · xジャンル:コメディ · xジャンル:アクション 
+ <Vジャンル:コメディ, V価格> · xジャンル:コメディ · x価格

+ <Vジャンル:アクション, V価格> · xジャンル:アクション · x価格

  <Vユーザ:太郎, V映画:影武者> · 1 · 1 
+ <Vユーザ:太郎, Vジャンル:コメディ> · 1 · 1 
+ <Vユーザ:太郎, Vジャンル:アクション> · 1 · 1 
+ <Vユーザ:太郎, V価格> · 1 · 999

+ <V映画:影武者, Vジャンル:コメディ> · 1 · 1 
+ <V映画:影武者, Vジャンル:アクション> · 1 · 1 
+ <V映画:影武者, V価格> · 1 · 999

+ <Vジャンル:コメディ, Vジャンル:アクションi> · 1 · 1 
+ <Vジャンル:コメディ, V価格> · 1 · 999

+ <Vジャンル:アクション, V価格> · 1 · 999
FFMの場合

FFMの場合、モデル式の第3項(組み合わせ項)は以下のように展開されます。

  <Vユーザ:太郎|映画, V映画:影武者|ユーザ> · xユーザ:太郎 · x映画:影武者 
+ <Vユーザ:太郎|ジャンル, Vジャンル:コメディ|ユーザ> · xユーザ:太郎 · xジャンル:コメディ 
+ <Vユーザ:太郎|ジャンル, Vジャンル:アクション|ユーザ> · xユーザ:太郎 · xジャンル:アクション 
+ <Vユーザ:太郎|価格, V価格|ユーザ> · xユーザ:太郎 · x価格

+ <V映画:影武者|ジャンル, Vジャンル:コメディ|映画> · x映画:影武者 · xジャンル:コメディ 
+ <V映画:影武者|ジャンル, Vジャンル:アクション|映画> · x映画:影武者 · xジャンル:アクション 
+ <V映画:影武者|価格, V価格|映画> · x映画:影武者 · x価格

+ <Vジャンル:コメディ|ジャンル, Vジャンル:アクション|ジャンル> · xジャンル:コメディ · xジャンル:アクション 
+ <Vジャンル:コメディ|価格, V価格|ジャンル> · xジャンル:コメディ · x価格

+ <Vジャンル:アクション|価格, V価格|ジャンル> · xジャンル:アクション · x価格

  <Vユーザ:太郎,映画, V映画:影武者|ユーザ> · 1 · 1
+ <Vユーザ:太郎|ジャンル, Vジャンル:コメディ|ユーザ> · 1 · 1
+ <Vユーザ:太郎|ジャンル, Vジャンル:アクション|ユーザ> · 1 · 1
+ <Vユーザ:太郎|価格, V価格|ユーザ> · 1 · 999

+ <V映画:影武者|ジャンル, Vジャンル:コメディ|映画> · 1 · 1
+ <V映画:影武者|ジャンル, Vジャンル:アクション|映画> · 1 · 1
+ <V映画:影武者|価格, V価格|映画> · 1 · 999

+ <Vジャンル:コメディ|ジャンル, Vジャンル:アクション|ジャンル> · 1 · 1
+ <Vジャンル:コメディ|価格, V価格|ジャンル> · 1 · 999

+ <Vジャンル:アクション|価格, V価格|ジャンル> · 1 · 999

実装

FFMが広く使われるようになって欲しいということで、Yu-Chin Juanさんら作者によりオープンソース実装であるLIBFFMが公開されています。

論文PDFには、SG(Stochastic Gradient)の簡易アルゴリズムが掲載されています。実装面で気になった点について、幾つか記します:

  • AdaGradを学習率の調整に使用している。XGBoostの開発者Tianqi Chen(陈天奇)さんが"Interesting!"と詳細を質問していた。
  • 過学習を避けるためにEarly Stoppingを採用している。epoch(学習ループ)毎にValidationセットのロスを計算し、上昇した時点で中断する。
  • SGをパラレルで実行している。並列化で収束の振る舞いが異なる可能性があるものの、同様な収束が見られたとのこと。

おわりに

FFMの論文では、Chih-Jen Lin(林智仁、國立台灣大學資訊工程學系)さんの名前もありますが、この方がYu-Chin Juanさんらの指導教官だったようです。Chih-Jen LinさんはLIBSVMの作者として有名らしく、背後にいるラスボスにみたいな方でしょうか。ホームページにはさりげなく2017/2までmicrosoft訪問中とあり、研究室メンバーのページには、googleとかmicrosoftなどの名前が並んでいます。今度台北に行ったら、アジア最高のML研究所のひとつとして、どんなところか見に行きたい。