特征表示
| Field | feature | feature取值 | x | 備注 | |
| user側 | Field1 | 性别 | 男 | x1 | 每個取值對應一個x |
| 女 | x2 | ||||
| Field2 | 年齡 | <18 | x3 | 連續特征先離散化 | |
| 19-24 | x4 | ||||
| 25-30 | x5 | ||||
| 31-35 | x6 | ||||
| 36-40 | x7 | ||||
| >40 | x8 | ||||
| Field3 | 省 | 山西 | x9 | ||
| 廣西 | x10 | ||||
| 陝西 | x11 | ||||
| ... | .... | ||||
| 城市 | 洛陽 | x300 | 可能的取值很多， 一個樣本隻會命 中一個取值 | ||
| 安陽 | x301 | ||||
| 南陽 | x302 | ||||
| item側 | Field4 | 關鍵詞 | 足球 | x1000 | 一個樣本會同時命 中多個 |
| 5G | x1001 | ||||
| Field5 | 時效性 | 3小時 | x5000 | ||
| 當天 | x5001 | ||||
| 7天 | x5002 | ||||
| 永久 | x5003 |
這個例子中，一共有5個域，6個特征，5003個x，但對于一樣本“最多”隻有$5+l$個x是1，其它x全是0，$l$表示item關鍵詞的個數，之是以說“最多”是因為一個樣本的某些特征可能取不到，對應的x就全是0。
FFM公式變換
$$\hat{y}=\sum_{i=1}^nw_ix_i+\sum_{k=1}^K\sum_{i=1}^n\sum_{j=i+1}^nV_{i,fj,k}V_{j,fi,k}x_ix_j$$
$x$非0即1，是以乘上$x$實際上是對$w$和$V$進行挑選。$V$是一個size為$n\times F \times K$的三維矩陣，$n$是x的個數，在表一中$n=5003$，F是域的個數，在表一中F=5，$V_{i,fj}是$x_i$去跟$Field_j$交叉時使用的向量，$K是向量的長度，通常取4、8、16。
上式的第一項對所有的$w$求和，這沒什麼好說的，我們重點關注第二項的形式變換。第二項最外層按$k$求和也變不出什麼花樣，在$k$取某一個具體值的情況下我們看看$\sum_{i=1}^n\sum_{j=i+1}^nV_{i,fj}V_{j,fi}$如何做形式變換。這要分成兩種情況來看待：$i$和$j$是否屬于同一個Field。
$i$和$j$屬于不同的Field
試想屬于同一個Field的$x$下标都是連續的，當$i$和$j$屬于不同的Field時
$$\sum_{i=1}^n\sum_{j=i+1}^nV_{i,fj}V_{j,fi}=\sum_{p=1}^F\sum_{q=p+1}^F\sum_{i\in Filed_p}\sum_{j\in Filed_q}V_{i,q}V_{j,p}=\sum_{p=1}^F\sum_{q=p+1}^F\sum_{i\in Filed_p}V_{i,q}\sum_{j\in Filed_q}V_{j,p}$$
令$F_{p,q}=\sum_{i\in Filed_p}V_{i,q}$，它表示$Field_p$内部的所有$x$跟$Field_q$交叉時使用的向量按位相加之和。
舉個例子，比如$a$、$b$、$c$屬于Field1，$d$、$e$屬于Field2，則$ad+ae+bd+de+cd+ce=(a+b+c)(d+e)$。隻需要一次乘法。
$i$和$j$屬于同一個Field
當$i$和$j$屬于同一個Field時
\begin{eqnarray*} \begin{aligned} \sum_{i=1}^n\sum_{j=i+1}^nV_{i,fj}V_{j,fi}=\sum_{f=1}^F\sum_{i=1}\sum_{j=i+1}V_{i,f}V_{j,f}&=\sum_{f=1}^F\frac{1}{2}\left[\sum_{i=1}\sum_{j=1}V_{i,f}V_{j,f}-\sum_{i=1}V_{i,f}^2\right]\\ &=\sum_{f=1}^F\frac{1}{2}\left[\sum_{i=1}V_{i,f}\sum_{j=1}V_{j,f}-\sum_{i=1}V_{i,f}^2\right]\\ &=\sum_{f=1}^F\frac{1}{2}\left[\left(\sum_{i=1}V_{i,f}\right)^2-\sum_{i=1}V_{i,f}^2\right] \end{aligned} \end{eqnarray*}
解釋一下第一行的變換是怎麼來的，試想一個對稱方陣上角元素之和等于方陣所有元素之和減去對角線元素之和，再除以2。
舉個例子，比如$a$、$b$、$c$屬于同一個Fied，則$ab+ac+bc=\frac{1}{2}[(a+b+c)^2-(a^2+b^2+c^2)]$。乘法計算量由$O(n^2)$ 降為$O(n)$，$n$表示該Field内有幾個特征。
user和item的向量表示
給一個user推薦一批item，FFM決策函數裡隻跟user特征相關的項可以去掉，不影響item的排序，這包括$\sum_{x_i \in UserFeature}w_ix_i$以及$\sum_{i=1}^n\sum_{j=i+1}^n\vec{V}_{i,fj}\cdot\vec{V}_{j,fi}x_ix_j$中$x_i$和$x_j$同時屬于UserFeature的情況。
對應地，隻跟item特征相關的項全部加起來，構成ItemBias。即
$$ItemBias=\sum_{i=1}^nw_ix_i+\sum_{i=1}^n\sum_{j=i+1}^n\vec{V}_{i,fj}\cdot\vec{V}_{j,fi}x_ix_j\qquad x_i \in ItemFeature\ \text{且}\ x_j \in ItemFeature$$
用這個圖來了解FFM的二次項，設Field1、2、3是user側的，Field4、5是item側的。Field1、2、3域之間的交叉以及每個域内部各特征之間的交叉是紅色區域，這一塊屬于UserBias，可以丢棄掉不影響item的排序。綠色區域屬于ItemBias。黃色區域是UserFeature和ItemFeature之間的交叉，它相當于
\begin{equation}F_{1,4}F_{4,1}+F_{1,5}F_{5,1}+F_{2,4}F_{4,2}+F_{2,5}F_{5,2}+F_{3,4}F_{4,3}+F_{3,5}F_{5,3}\label{cross}\end{equation}
下三角白色區域是不需要交叉的，因為在FFM的二次項裡j是從i+1開始的，推出$Field_p$和$Field_q$交叉時隻需要計算$q>p$的情況。圖中的對角線也标上了顔色，并不是說一個域需要自己跟交叉，而是說一個域内部各特征之間還需要交叉。
把$[F_{1,4},F_{1,5},F_{2,4},F_{2,5},F_{3,4},F_{3,5}]$首尾相連拼接成User向量，把$[F_{4,1},F_{5,1},F_{4,2},F_{5,2},F_{4,3},F_{5,3}]$首尾相連拼接成Item向量，則(\ref{cross})式等于User向量和Item向量的内積。
為了把ItemBias加進來，需要在User向量最後補一個1，同時在Item向量最後補一個ItemBias。
再次明确一下ItemBias包含三部分：
\begin{matrix}\sum_{i=1}^nw_ix_i & x_i \in ItemFeature \\\sum_{f\in ItemField}\sum_{i=1}\sum_{j=i+1}\vec{V}_{i,f}\cdot\vec{V}_{j,f} & x_i \in Field_f\textrm{且} x_j \in Field_f,\textrm{即同一個Field内部各特征做交叉}\\\sum_p\sum_{q=p+1}F_{p,q}\cdot F_{q,p} & p\in ItemField\textrm{且}q\in ItemField, \text{即item側Field之間兩兩交叉}\end{matrix}
尋找向量的最近鄰
KD Tree次元小于20時效率最高，随着次元的增加效率會迅速下降，是以就有了Ball Tree。
Faiss通過PCA和PQ(乘積量化)對向量進行壓縮和編碼。
最後再附上我做的PPT: FM和FFM召回算法
