[fundamentals of machine learning 04] matrix factorization

Completed the basic learning of machine learning , The author also shared the matrix decomposition based CTR Model for reference
Matrix decomposition advanced ：FM、FFM
Matrix decomposition and deep learning ：DeepFM、xDeepFM
Matrix decomposition and characteristic intersection ：Wide & Deep、Deep & Cross Network

Matrix decomposition （Matrix Factorization）

For datasets $\mathcal{D}$ , The square error based error measurement of the assumed function is ：
$$E_{\text{in }}\left(\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\}\right)=\frac{1}{{\sum }_{m=1}^M\left|{\mathcal{D}}_m\right|}\sum _{\text{user }n\text{ rated movie }m}{\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right)}^2$$
So now it's time to use the data set $\mathcal{D}$ Conduct ${\mathbf{v}}_n$ and ${\mathbf{w}}_m$ To ensure the minimum error :
$$\begin{array}{rl}\underset{\mathrm{W},\mathrm{V}}{\min }{E}_{\text{in }}\left(\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\}\right)& \propto \sum _{\text{usern rated movie }m}{\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right)}^2\\ & =\sum _{m=1}^M\left(\sum _{\left({\mathbf{x}}_n,r_{nm}\right)\in {\mathcal{D}}_m}{\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right)}^2\right)\\ & =\sum _{n=1}^N\left(\sum _{\left({\mathbf{x}}_n,r_{nm}\right)\in {\mathcal{D}}_m}{\left(r_{nm}-{\mathbf{v}}_n^T{\mathbf{w}}_m\right)}^2\right)\end{array}$$
Because there is $v_n$ and $w_m$ Two variables , It may be difficult to optimize at the same time , So the basic idea is to use alternate minimization operations （alternating minimization）：

1. Fix ${\mathbf{v}}_n$, That is to say, fixed user eigenvectors , Then find each one ${\mathbf{w}}_m\equiv \mathrm{minimize}{E}_{\text{in }}$ within ${\mathcal{D}}_m$.
2. Fix ${\mathbf{w}}_m$, That is to say, the feature vector of the movie , Then find each one ${\mathbf{v}}_n\equiv \mathrm{minimize}{E}_{\text{in }}$ within ${\mathcal{D}}_{m\text{ . }}$

This process is called alternating least squares algorithm （alternating least squares algorithm）. specific working means ：

initialize$\tilde{d}$ dimension vectors $\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\}$

alternating optimization of $E_{\text{in }}:$repeatedly

1. optimize ${\mathbf{w}}_1,{\mathbf{w}}_2,\dots ,{\mathbf{w}}_M:$ update ${\mathbf{w}}_m$ by $m$ -th-movie linear regression on $\left\{\left({\mathbf{v}}_n,r_{nm}\right)\right\}$

2. optimize ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_N:$ update ${\mathbf{v}}_n$ by $n$ -th-user linear regression on $\left\{\left({\mathbf{w}}_m,r_{nm}\right)\right\}$

until converge

SGD for Matrix Factorization

Remember that our error function is ：
$$E_{\text{in }}\left(\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\}\right)=\frac{1}{{\sum }_{m=1}^M\left|{\mathcal{D}}_m\right|}\sum _{\text{user }n\text{ rated movie }m}{\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right)}^2$$
Because only one sample is taken out for optimization each time , Then first observe the error measurement of a single sample ：
$$\text{ err }\left(\text{ user }n,\text{ movie }m,\text{ rating }{r}_{nm}\right)={\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right)}^2$$
So partial derivative ：

$$\begin{gathered} {\nabla }_{{\mathbf{v}}_n}\mathrm{err}\left(\text{ user }n,\text{ movie }m,\text{ rating }{r}_{nm}\right)=-2\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right){\mathbf{w}}_m \\ {\nabla }_{{\mathbf{w}}_m}\mathrm{err}\left(\text{ user }n,\text{ movie }m,\text{ rating }{r}_{nm}\right)=-2\left(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n\right){\mathbf{v}}_n \end{gathered}$$
That is to say, only for the current sample ${\mathbf{v}}_n$ and ${\mathbf{w}}_m$ Have an impact on , The partial derivatives of other parameters are all zero . In conclusion, it is ：
$$\text{ per-example gradient }\propto -(\text{ residual })(\text{ the other feature vector })$$
Then the practical steps of using the random gradient descent method to solve the matrix decomposition are ：

Be careful. , If you recommend anything related to timing , For example, the test set is the data after the training set time , Then you can put SGD Medium “S” It's about time , That is, according to the time sequence pick (n, m).