---
# System prepended metadata

title: Ch15 Matrix Factorization
tags: [機器學習技法]

---

---
tags: 機器學習技法
---

Ch15 Matrix Factorization
===

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Linear Network Hypothesis](https://www.coursera.org/learn/machine-learning-techniques/lecture/EYwL7/linear-network-hypothesis)

### Recommender System Revisited

![](https://i.imgur.com/1mIfJMY.png)
- $m$-th movie
- $n$-th user
- 這是困難的 ML 問題：feature $\tilde x$ 非常抽象，只有編號

### Binary Vector Encoding of Categorical Feature

![](https://i.imgur.com/AeJr4t4.png)
- 數字大小沒有意義，只代表種類，叫 categorical features
- 但是大多數 ML model 需要有意義的 numerical features
- 那就 binary encoding ㄅ

### Feature Extraction from Encoded Vector

![](https://i.imgur.com/2kSkzZ4.png)
- $x_n$ binary encoding 表示它是哪個使用者
- $y_n$ 表示它對各 movies 的評分
- 我們考慮一個 NN，input $x$，希望他 output $y$
    - 記得 $x$ 只有一個 feature 會是 $1$；其他都 $0$
- **其實好像不需要有 activation function**
    - 想想現在 $x_n$ 是 $1$ (其他都 0)的情況下，那 output 到第 $i$ 個 neuron 的 hidden output 就是 $\tanh(w_{ni})$，只被這個 weight 給控制。也就是說就算不用 $\tanh$，也可以找出對的 weight。

### 'Linear' Network Hypothesis

![](https://i.imgur.com/SkTKtfo.png)
- $V\in\mathbb R^{\tilde d\times N}$
- $W\in\mathbb R^{\tilde d\times M}$
- hypothesis $h(x)=W^T Vx$
- 利用 $x_n=e_n$ 的性質，我們知道 $Vx=v_n$，即 $V$ 的第 $n$ 個 column
    - $v_n$ 可以視為對第 $n$ 個使用者的一種特徵轉換
    - 轉換之後再做 linear transform $W^T$ 預測對各電影的喜好

## [Basic Matrix Factorization](https://www.coursera.org/learn/machine-learning-techniques/lecture/2HFwO/basic-matrix-factorization)

### Linear Network: Linear Model Per Movie

![](https://i.imgur.com/AFunaOV.png)
- $Vx=\phi(x)$ (feature transform)
- 要預測第 $m$ 部電影，其實也只需要 $W$ 的第 $m$ 個 column，我們寫作 $w_m$
- 其實 $h_m(x_n)$ 就是 $w_m$ 跟 $v_n$ 的內積

### Matrix Factorization

![](https://i.imgur.com/7KG7AkN.png)
- $v_n$ 與 $w_m$ 做內積
    - 可以想像成：每個 dimension 分別代表一些屬性：喜劇片/動作片/大作...
    - ex: element 1 = 使用者喜歡喜劇片的程度 vs 電影是否喜劇片的程度

### Matrix Factorization Learning

![](https://i.imgur.com/cGQefy1.png)
- 有兩組 variables 所以 alternating minimization
- 固定 $v_n$ 解 $w_m$ 就跟解 linear regression 一樣
    - 注意這邊跟一般 linear regression 不一樣，不需要 $w_0$
    - **意思是去看所有觀眾對電影 $m$ 的評價來解 $w_m$ 吧**
- 固定 $w_m$ 解 $v_n$ 呢?
    - 角度互換應該就可以了，去看該觀眾 $n$ 對所有電影的評價
    - > Q: 所以數學式應該要改ㄅ


### Alternating Least Squares

![](https://i.imgur.com/Sb8pDiU.png)

### Linear Autoencoder versus Matrix Factorization

![](https://i.imgur.com/toKDb6D.png)
- Linear Autoencoder 也可以看成是矩陣分解
    - 把 $X$ 分解成 $W$ 和 $W^T X$
- Matrix Factorization 也可以看成是 linear NNet
- > Q: Matrix Factorization 可以找出 hidden user 是什麼意思??


### Fun Time: How Many Least Square Problems Solved in Matrix Factorization?

![](https://i.imgur.com/PuYKV8x.png)


## [Stochastic Gradient Descent](https://www.coursera.org/learn/machine-learning-techniques/lecture/Lu5FJ/stochastic-gradient-descent)

### Another Possibility: Stochastic Gradient Descent

![](https://i.imgur.com/cI1FH0N.png)

### Gradient of Per-Example Error Function

![](https://i.imgur.com/2aWHKBa.png)
- "residual" 即 $r_{nm}-w_m^T v_n$
- "the other feature vector" 如果在更新 $v_n$ 那就是 $w_m$；如果在更新 $w_m$ 那 "other vector" 就是 $v_n$。

### SGD for Matrix Factorization

![](https://i.imgur.com/q9zVZOp.png)

### SGD for Matrix Factorization in Practice

![](https://i.imgur.com/tYAZlF5.png)
- KDDCup 2011 台大又拿世界冠軍啦
- 跟基石課程說的一樣，強化比較近期的資料。
- 固定在最後 $T'$ 個 iteration 給他看 $T'$ 筆最新的資料。
- **如果我們知道我們的模型是如何做最佳化的，那就很容易可以根據我的需求做改變！**

### Fun Time: What If Initialize Matrices as Zeros?

![](https://i.imgur.com/yXEbsc1.png)


## [Summary of Extraction Models](https://www.coursera.org/learn/machine-learning-techniques/lecture/ugr7L/summary-of-extraction-models)

### Map of Extraction Models

![](https://i.imgur.com/riLWxBQ.png)
- 藍色的部分可以視為 feature transform 或者 hidden variables
- 紅色的部分可以視為 linear model
- 而 Matrix Factorization 的 $v_n$ 以及 $w_m$ 是對稱的：同時可以看成是 feature transform 或者是 linear model
    - 例如：$v_n$ 可以看成是 user 的 feature transform；也可以看成是 movie features 的 linear model
    - 反之亦然。
- > Q: k-NN 的部分比較不解，改天再看

### Map of Extraction Techniques

![](https://i.imgur.com/dyN5Hs9.png)
- functional gradient descent 還頗玄的，改天再複習一次
- **autoencoder 可以用來 initialize NN；k-means 可以用來挑 RBFNet 的中心點。這告訴我們 unsupervised learning 非常有用。**

### Pros and Cons of Extraction Models

![](https://i.imgur.com/UBX7mTU.png)
- **non-convex** !!!
- overfitting !!

