---
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

- $m$-th movie
- $n$-th user
- 這是困難的 ML 問題：feature $\tilde x$ 非常抽象，只有編號

### Binary Vector Encoding of Categorical Feature

- 數字大小沒有意義，只代表種類，叫 categorical features
- 但是大多數 ML model 需要有意義的 numerical features
- 那就 binary encoding ㄅ

### Feature Extraction from Encoded Vector

- $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

- $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

- $Vx=\phi(x)$ (feature transform)
- 要預測第 $m$ 部電影，其實也只需要 $W$ 的第 $m$ 個 column，我們寫作 $w_m$
- 其實 $h_m(x_n)$ 就是 $w_m$ 跟 $v_n$ 的內積

### Matrix Factorization

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

### Matrix Factorization Learning

- 有兩組 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


### Linear Autoencoder versus Matrix Factorization

- 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?


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

### Another Possibility: Stochastic Gradient Descent


### Gradient of Per-Example Error Function

- "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


### SGD for Matrix Factorization in Practice

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

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


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

### Map of Extraction Models

- 藍色的部分可以視為 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

- functional gradient descent 還頗玄的，改天再複習一次
- **autoencoder 可以用來 initialize NN；k-means 可以用來挑 RBFNet 的中心點。這告訴我們 unsupervised learning 非常有用。**

### Pros and Cons of Extraction Models

- **non-convex** !!!
- overfitting !!