1、FM背景
在計算廣告和推薦系統中（比如大家常玩的抖音、今日頭條；訂酒店用的攜程、購物用的淘寶。。。），CTR預估（click-through rate）是非常重要的一個環節，判斷一個影片/文章/商品/廣告是否進行推薦需要根據CTR預估的點選率來進行。在進行CTR預估時，除了單特徵外，往往要對特徵進行組合。對於特徵組合來說，業界現在通用的做法主要有兩大類：FM系列與Tree系列。今天，我們就來講講FM演算法。
2、one-hot編碼帶來的問題
FM（Factorization Machine）主要是為了解決資料稀疏的情況下，特徵怎樣組合的問題。以一個廣告分類的問題為例，根據使用者與廣告位的一些特徵，來預測使用者是否會點選廣告。資料如下：（本例來自美團技術團隊分享的paper）
clicked是分類值，表明使用者有沒有點選該廣告。1表示點選，0表示未點選。而country，day，ad_type則是對應的特徵。對於這種categorical特徵，一般都是進行one-hot編碼處理。
將上面的資料進行one-hot編碼以後，就變成了下面這樣 ：
因為是categorical特徵，所以經過one-hot編碼以後，不可避免的樣本的資料就變得很稀疏。舉個非常簡單的例子，假設淘寶或者京東上的item為100萬，如果對item這個維度進行one-hot編碼，光這一個維度資料的稀疏度就是百萬分之一。由此可見，資料的稀疏性，是我們在實際應用場景中面臨的一個非常常見的挑戰與問題。
one-hot編碼帶來的另一個問題是特徵空間變大。同樣以上面淘寶上的item為例，將item進行one-hot編碼以後，樣本空間有一個categorical變為了百萬維的數值特徵，特徵空間一下子暴增一百萬。所以大廠動不動上億維度，就是這麼來的。
3、對特徵進行組合
普通的線性模型，我們都是將各個特徵獨立考慮的，並沒有考慮到特徵與特徵之間的相互關係。但實際上，大量的特徵之間是有關聯的。最簡單的以電商為例，一般女性使用者看化妝品服裝之類的廣告比較多，而男性更青睞各種球類裝備。那很明顯，女性這個特徵與化妝品類服裝類商品有很大的關聯性，男性這個特徵與球類裝備的關聯性更為密切。如果我們能將這些有關聯的特徵找出來，顯然是很有意義的。
一般的線性模型為：
從上面的式子很容易看出，一般的線性模型壓根沒有考慮特徵間的關聯。為了表述特徵間的相關性，我們採用多項式模型。在多項式模型中，特徵xi與xj的組合用xixj表示。為了簡單起見，我們討論二階多項式模型。具體的模型表示式如下：
上式中，n表示樣本的特徵數量，xi表示第i個特徵。
與線性模型相比，FM的模型就多了後面特徵組合的部分。
4、FM求解
從上面的式子可以很容易看出，組合部分的特徵相關引數共有n（n−1）/2個。但是如第二部分所分析，在資料很稀疏的情況下，滿足xi，xj都不為0的情況非常少，這樣將導致ωij無法透過訓練得出。
為了求出ωij，我們對每一個特徵分量xi引入輔助向量Vi=（vi1，vi2，⋯，vik）。然後，利用vivj^T對ωij進行求解。
那麼ωij組成的矩陣可以表示為：
那麼，如何求解vi和vj呢？主要採用了公式：
具體過程如下：
上面的式子中有同學曾經問我第一步是怎麼推導的，其實也不難，看下面的手寫過程（大夥可不要嫌棄字醜喲）
經過這樣的分解之後，我們就可以透過隨機梯度下降SGD進行求解：
5、tensorflow程式碼詳解
程式碼參考地址：https：//github。com/babakx/fm_tensorflow/blob/master/fm_tensorflow。ipynb
上面的程式碼使用的是python2編碼，在python3下執行會出錯，所以如果大家使用的是python3的話，可以參考我寫的，其實就是修復了幾個bug啦，哈哈。
我的github地址：
https：//github。com/princewen/tensorflow_practice/tree/master/recommendation-FM-demo。
本文使用的資料是MovieLens100k Datase，資料包括四列，分別是使用者ID，電影ID，打分，時間。
輸入變換
要使用FM模型，我們首先要將資料處理成一個矩陣，矩陣的大小是使用者數 * 電影數。如何根據現有的資料進行處理呢？使用的是scipy。sparse中的csr。csr_matrix，理解這個函式真的費了不少功夫呢，不過還是在下面部落格（https：//blog。csdn。net/u012871493/article/details/51593451）的幫助下理解了函式的原理。盜用部落格中的一張圖來幫助大家理解這個函式的輸入：
函式形式如下：
csr_matrix（（data， indices， indptr）
可以看到，函式接收三個引數，第一個引數是數值，第二個引數是每個數對應的列號，第三個引數是每行的起始的偏移量，舉上圖的例子來說，第0行的起始偏移是0，第0行有2個非0值，因此第一行的起始偏移是2，第1行有兩個非0值，因此第二行的起始偏移是4，依次類推。
下面的程式碼是如何將原始的檔案輸入轉換成我們的矩陣：
def vectorize_dic（dic，ix=None，p=None，n=0，g=0）： “”“ dic —— dictionary of feature lists。 Keys are the name of features ix —— index generator （default None） p —— dimension of featrure space （number of columns in the sparse matrix） （default None） ”“” if ix==None： ix = dict（） nz = n * g col_ix = np。empty（nz，dtype = int） i = 0 for k，lis in dic。items（）： for t in range（len（lis））： ix［str（lis［t］） + str（k）］ = ix。get（str（lis［t］） + str（k），0） + 1 col_ix［i+t*g］ = ix［str（lis［t］） + str（k）］ i += 1 row_ix = np。repeat（np。arange（0，n），g） data = np。ones（nz） if p == None： p = len（ix） ixx = np。where（col_ix < p） return csr。csr_matrix（（data［ixx］，（row_ix［ixx］，col_ix［ixx］）），shape=（n，p）），ixcols = ［‘user’，‘item’，‘rating’，‘timestamp’］train = pd。read_csv（‘data/ua。base’，delimiter=‘\t’，names = cols）test = pd。read_csv（‘data/ua。test’，delimiter=‘\t’，names = cols）x_train，ix = vectorize_dic（{‘users’：train［‘user’］。values， ‘items’：train［‘item’］。values}，n=len（train。index），g=2）x_test，ix = vectorize_dic（{‘users’：test［‘user’］。values， ‘items’：test［‘item’］。values}，ix，x_train。shape［1］，n=len（test。index），g=2）y_train = train［‘rating’］。valuesy_test = test［‘rating’］。valuesx_train = x_train。todense（）x_test = x_test。todense（）
如果不做處理，函式返回的矩陣是按如下的格式儲存的：
使用todense變換後，變成如下樣式：
估計值計算
得到我們的輸入之後，我們使用tensorflow來設計我們的模型，其實很簡單啦，我們模型的估計值由兩部分構成，原始的可以理解為線性迴歸的部分，以及交叉特徵的部分，交叉特徵直接使用我們最後推導的形式即可，再回顧一遍：
因此，我們需要定義三個placeholder，分別是輸入的x，輸入的y，以及我們的 使用者數*電影數大小的待學習的fm矩陣：
n，p = x_train。shapek = 10x = tf。placeholder（‘float’，［None，p］）y = tf。placeholder（‘float’，［None，1］）w0 = tf。Variable（tf。zeros（［1］））w = tf。Variable（tf。zeros（［p］））v = tf。Variable（tf。random_normal（［k，p］，mean=0，stddev=0。01））#y_hat = tf。Variable（tf。zeros（［n，1］））linear_terms = tf。add（w0，tf。reduce_sum（tf。multiply（w，x），1，keep_dims=True）） # n * 1pair_interactions = 0。5 * tf。reduce_sum（ tf。subtract（ tf。pow（ tf。matmul（x，tf。transpose（v）），2）， tf。matmul（tf。pow（x，2），tf。transpose（tf。pow（v，2））） ），axis = 1 ， keep_dims=True）y_hat = tf。add（linear_terms，pair_interactions）
定義損失函式
這裡我們定義的損失函式除了平方損失外，還加了l2正則項，並使用梯度下降法進行引數的更新：
lambda_w = tf。constant（0。001，name=‘lambda_w’）
lambda_v = tf。constant（0。001，name=‘lambda_v’）
l2_norm = tf。reduce_sum（
tf。add（
tf。multiply（lambda_w，tf。pow（w，2）），
tf。multiply（lambda_v，tf。pow（v，2））
）
）
error = tf。reduce_mean（tf。square（y-y_hat））
loss = tf。add（error，l2_norm）
train_op = tf。train。GradientDescentOptimizer（learning_rate=0。01）。minimize（loss）
模型訓練
接下來就是訓練啦，這段程式碼比較好理解：
epochs = 10batch_size = 1000# Launch the graphinit = tf。global_variables_initializer（）with tf。Session（） as sess： sess。run（init） for epoch in tqdm（range（epochs）， unit=‘epoch’）： perm = np。random。permutation（x_train。shape［0］） # iterate over batches for bX， bY in batcher（x_train［perm］， y_train［perm］， batch_size）： _，t = sess。run（［train_op，loss］， feed_dict={x： bX。reshape（-1， p）， y： bY。reshape（-1， 1）}） print（t） errors = ［］ for bX， bY in batcher（x_test， y_test）： errors。append（sess。run（error， feed_dict={x： bX。reshape（-1， p）， y： bY。reshape（-1， 1）}）） print（errors） RMSE = np。sqrt（np。array（errors）。mean（）） print （RMSE）
參考文章：
1、http：//blog。csdn。net/bitcarmanlee/article/details/52143909
2、https：//blog。csdn。net/u012871493/article/details/51593451
