---
disqus: ierosodin
---

# Introduction

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `machine learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Machine_Learning)==

## Diffrence bettween algorithm and machine learning

Algorithm 是 ==step by step== 的告訴 machine 要怎麼做才能達到目標結果，而 machine learning 並沒有告訴機器 detail，也就是 ==machine don't know waht data is or what data for==，我們只告訴機器要用甚麼方法來找到一個適合的 model to fit our data。

# Linear Regression

Linear regression 被應用在像是 curve fitting 以及 classification

在多維空間中，我們將每一點視為一筆資料，因此可以利用一個高維的空間，來記錄一群數據。然而，我們希望找到一個關係，它能代表這個空間中的所有資料，以一個二維空間為例：
:::info
我們有兩筆資料：

$(1, 2) 與 (4, 7)$

現在希望能從這些資料 (data) 中找到一個對應，使得給出一個體重，就能得出相對應的身高，我們可以利用一個簡單的二維數學式子來表達這件事：

${ax + b = y}$

其中，$x$ 為input，$y$ 為output，或是我們稱為target，而 $a$ 與 $b$ 就是我們要找出的關係。
在這個例子中，我們可以得出以下式子：

${{\left[
\begin{array}{cc}
4 & 1 \\
1 & 1 \\
\end{array}
\right]}{\left[
\begin{array}{c}
a \\
b \\
\end{array}
\right]} = {\left[
\begin{array}{c}
7 \\
2 \\
\end{array}
\right]}}$

:::

要解以上的問題，有許多數值分析的方法能找到答案，例如 Gauss Jordden elimation 、 LL 、 LU 分解等。

:::danger
## Gauss Jordden elimation

${{\left[
\begin{array}{cc|cc}
4 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 \\
\end{array}
\right]} = {\left[
\begin{array}{cc|cc}
1 & 0 & \frac13 & \frac{-1}3 \\
0 & 1 & \frac{-1}3 & \frac43 \\
\end{array}
\right]} \Rightarrow {\left[
\begin{array}{c}
a \\
b \\
\end{array}
\right]} = {\left[
\begin{array}{cc}
\frac13 & \frac{-1}3 \\
\frac{-1}3 & \frac43 \\
\\
\end{array}
\right]} {\left[
\begin{array}{c}
7 \\
2 \\
\end{array}
\right]}}$

缺點：時間複雜度為 ${O(n^3)}$
:::

:::danger
## LDL

${\begin{split}
{\left[
\begin{array}{ccccc}
a_{11} & a_{12} & a_{13} & ... & a_{1n} \\
a_{21} & a_{22} & a_{23} & ... & a_{2n} \\
a_{31} & a_{32} & a_{33} & ... & a_{3n} \\
... & ... & ... & ... & ... \\
a_{n1} & a_{n2} & a_{n3} & ... & a_{nn} \\
\end{array}
\right]} = & {\left[
\begin{array}{ccccc}
1 & 0 & 0 & ... & 0 \\
l_{21} & 1 & 0 & ... & 0 \\
l_{31} & l_{32} & 1 & ... & 0 \\
... & ... & ... & ... & ... \\
l_{n1} & l_{n2} & l_{n3} & ... & 1 \\
\end{array}
\right]} \times \\
& {\left[
\begin{array}{ccccc}
d_1 & 0 & 0 & ... & 0 \\
0 & d_2 & 0 & ... & 0 \\
0 & 0 & d_3 & ... & 0 \\
... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & d_n \\
\end{array}
\right]} \times {\left[
\begin{array}{ccccc}
1 & l_{21} & l_{31} & ... & l_{n1} \\
0 & 1 & l_{32} & ... & l_{n2} \\
0 & 0 & 1 & ... & l_{n3} \\
... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & 1 \\
\end{array}
\right]}
\end{split}}$

其中，
${d_k = a_{kk} - \sum_{t=1}^{k-1} l_{kt}^2d_t}$
${l_{jk} = \frac{1}{d_k}(a_{jk} - \sum_{t=1}^{k-1} l_{jt}l_{kt}d_t),\ j > k}$
:::
:::danger
## LU

${\begin{split}
{\left[
\begin{array}{ccccc}
a_{11} & a_{12} & a_{13} & ... & a_{1n} \\
a_{21} & a_{22} & a_{23} & ... & a_{2n} \\
a_{31} & a_{32} & a_{33} & ... & a_{3n} \\
... & ... & ... & ... & ... \\
a_{n1} & a_{n2} & a_{n3} & ... & a_{nn} \\
\end{array}
\right]} = &{\left[
\begin{array}{ccccc}
1 & 0 & 0 & ... & 0 \\
l_{21} & 1 & 0 & ... & 0 \\
l_{31} & l_{32} & 1 & ... & 0 \\
... & ... & ... & ... & ... \\
l_{n1} & l_{n2} & l_{n3} & ... & 1 \\
\end{array}
\right]} \times {\left[
\begin{array}{ccccc}
u_{11} & u_{12} & u_{13} & ... & u_{1n} \\
0 & u_{22} & u_{23} & ... & u_{2n} \\
0 & 0 & u_{33} & ... & u_{3n} \\
... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & u_{nn} \\
\end{array}
\right]}
\end{split}}$

其中，
${u_{1j} = a_{1j},\ j = 1, 2, 3, ..., n}$
${l_{j1} = \frac{a_{j1}}{u_{11}},\ j = 2, 3, ..., n}$
${u_{kj} = a_{kj} - \sum_{t=1}^{k-1}l_{kt}u_{tj},\ j = k, k + 1, k + 2, ..., n, k = 2, 3, 4, ..., n}$
${l_{jk} = \frac{1}{u_{kk}}(a_{jk} - \sum_{t=1}^{k-1}l_{jt}u_{tk}),\ j = k + 1, k + 2, k + 3, ..., n,\ k = 2, 3, 4, ..., n}$

:::

然而真實世界中，==通常找不到一個完美的 model to fit our data==，因為我們得到的資料通常是不完美的，例如資訊亮得不夠多、判斷誤差、量測誤差等，要如何在有缺陷、數量不足的資料情況下，找出背後隱藏的==趨勢==，就是我們想知道的。


以上圖為例，我們有 9 筆資料，他可能是一個 sin 波函數所得到的量測資料，由於蒐集資料過程中各種誤差的結果，導致我們無法直接得到正確的函數。

但我們仍希望有一種方法，找到這些資料間的一個趨勢，即使這個趨勢無法完美套用在每筆資料上，但整體而言，趨勢是對的。

其中一種預測方式是利用==多項式 (polynomial basis funciton)== 來預測輸出與輸入之間的關係：

:::danger
${y(x, w) = w_0 + w_1x + w_2x^2 + ... + w_Mx^M = \sum_{j=0}^Mw_jx^j}$
其中，
${x = [x_1 x_2 ... x_N]^T}$ 為已知的輸入
${y = [y_1 y_2 ... y_N]^T}$ 為經由函式所得到的結果
${w}$ 則是我們想要找出的關係的參數

而我們會有一組 ${t = [t_1 t_2 ... t_N]^T}$ 代表我們希望的結果 (target)，因此當 $y$ 與 $t$ 越相近，則此方程式越能代表這些輸出與輸入之間的關係
:::

因為==對 ${w}$ 來說，此方程式是線性的==，所以又稱為 ==linear method==，至於 non-linear case，在往後的課程會提到。

# LSE

有了模型，我們還必須有一個方法，來決定這個 model 的好壞，也就是常說的評估 ==loss、cost、distance 或者有時會稱作 likelihood==，這裡介紹 least square error (LSE)，也就是將目標結果與經由函式所得到的結果相減，再取平方和：

:::danger
${E(\textbf w) = min_w\ \{y(x_n, \textbf w) - t_n\}^2}$
or
${E(\textbf w) = min\ \sum(f(x_i) - y_i)^2 = min\ ||A\vec{x} - \vec{b}||^2}$
其中，
$A$ 為 input data 的集合
$\vec{x}$ 為所求函式的參數
$\vec{b}$ 則是目標 (target) 的集合
:::

因此當這個函式越接近真實的關係時，LSE 就會愈小，找最小極值即找出方程式==微分 $=0$== 的地方：

:::danger
${min\ ||A\vec{x} - \vec{b}||^2 = (A\vec{x} - \vec{b})^T(A\vec{x} - \vec{b}) = {\left[
\begin{array}{c}
(ax_0 - b - y_0)^2 \\
(ax_1 - b - y_1)^2 \\
... \\
\end{array}
\right]}}$
:::
:::danger

${\begin{split} min\ ||A\vec{x} - \vec{b}||^2 &= (A\vec{x} - \vec{b})^T(A\vec{x} - \vec{b}) \\
&= (\vec{x}^TA^T - \vec{b}^T)(A\vec{x} - \vec{b}) \\
&= \vec{x}^TA^TA\vec{x} - \vec{b}^TA\vec{x} - \vec{x}^TA^T\vec{b} + \vec{b}^T\vec{b}\end{split}}$

${\because \vec{b}^TA\vec{x} 和 \vec{x}^TA^T\vec{b}}$ 皆為純量，因此轉置後的值相同
${\vec{b}^TA\vec{x} = (\vec{b}^TA\vec{x})^T = \vec{x}^TA^T\vec{b}}$

${\therefore min\ ||A\vec{x} - \vec{b}||^2 = \vec{x}^TA^TA\vec{x} - 2\vec{x}^TA^T\vec{b} + \vec{b}^T\vec{b}}$

微分可得：${\frac{d(min\ ||A\vec{x} - \vec{b}||^2)}{d(\vec{x})} = \frac{d(\vec{x}^TA^TA\vec{x})}{d(\vec{x})} - 2\frac{d(\vec{x}^TA^T\vec{b})}{d(\vec{x})}}$

首先解 ${\frac{d(\vec{x}^TA^TA\vec{x})}{d(\vec{x})}}$，令 ${A^TA = G}$，且 ${G}$ 為一對稱矩陣
${\begin{split} 則 \frac{d(\vec{x}^TA^TA\vec{x})}{d(\vec{x})} &=
{\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{ccccc}
x_1 & x_2 & x_3 & ... & x_n
\end{array}
\right]}
{\left[
\begin{array}{ccccc}
g_{11} & g_{12} & g_{13} & ... & g_{1n} \\
g_{21} & g_{22} & g_{23} & ... & g_{2n} \\
g_{31} & g_{32} & g_{33} & ... & g_{3n} \\
... & ... & ... & ... & ... \\
g_{n1} & g_{n2} & g_{n3} & ... & g_{nn} \\
\end{array}
\right]}
{\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
... \\
x_n
\end{array}
\right]} \\
&= {\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{c}
x_1(g_{11}x_1 + g_{12}x_2 + g_{13}x_3 + ... + g_{1n}x_n) + \\
x_2(g_{21}x_1 + g_{22}x_2 + g_{23}x_3 + ... + g_{2n}x_n) + \\
x_3(g_{31}x_1 + g_{32}x_2 + g_{33}x_3 + ... + g_{3n}x_n) + \\
... + \\
x_n(g_{n1}x_1 + g_{n2}x_2 + g_{n3}x_3 + ... + g_{nn}x_n) \\
\end{array}
\right]} \\
&= {\left[
\begin{array}{c}
(g_{11}x_1 + g_{12}x_2 + ... + g_{1n}x_n) + (g_{11}x_1 + g_{21}x_2 + ... + g_{n1}x_n) \\
(g_{21}x_1 + g_{22}x_2 + ... + g_{2n}x_n) + (g_{12}x_1 + g_{22}x_2 + ... + g_{n2}x_n) \\
(g_{31}x_1 + g_{32}x_2 + ... + g_{3n}x_n) + (g_{13}x_1 + g_{23}x_2 + ... + g_{n3}x_n) \\
... \\
(g_{n1}x_1 + g_{n2}x_2 + ... + g_{nn}x_n) + (g_{1n}x_1 + g_{2n}x_2 + ... + g_{nn}x_n) \\
\end{array}
\right]} \\
&= {\left[
\begin{array}{c}
(g_{11}x_1 + g_{12}x_2 + ... + g_{1n}x_n) \\
(g_{21}x_1 + g_{22}x_2 + ... + g_{2n}x_n) \\
(g_{31}x_1 + g_{32}x_2 + ... + g_{3n}x_n) \\
... \\
(g_{n1}x_1 + g_{n2}x_2 + ... + g_{nn}x_n) \\
\end{array}
\right]} + {\left[
\begin{array}{c}
(g_{11}x_1 + g_{21}x_2 + ... + g_{n1}x_n) \\
(g_{12}x_1 + g_{22}x_2 + ... + g_{n2}x_n) \\
(g_{13}x_1 + g_{23}x_2 + ... + g_{n3}x_n) \\
... \\
(g_{1n}x_1 + g_{2n}x_2 + ... + g_{nn}x_n) \\
\end{array}
\right]} \\
&= G\vec{x} + G^T\vec{x} = 2G\vec{x} (\because\ G\ is\ symmetric)
\end{split}
}$
:::
:::danger
${\begin{split} 接著是\frac{d(\vec{x}^TA^T\vec{b})}{d(\vec{x})} &=
{\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{ccccc}
x_1 & x_2 & x_3 & ... & x_n
\end{array}
\right]}
{\left[
\begin{array}{ccccc}
a_{11} & a_{12} & a_{13} & ... & a_{1n} \\
a_{21} & a_{22} & a_{23} & ... & a_{2n} \\
a_{31} & a_{32} & a_{33} & ... & a_{3n} \\
... & ... & ... & ... & ... \\
a_{n1} & a_{n2} & a_{n3} & ... & a_{nn} \\
\end{array}
\right]}
{\left[
\begin{array}{c}
b_1 \\
b_2 \\
b_3 \\
... \\
b_n
\end{array}
\right]} \\
&= {\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{c}
x_1(a_{11}b_1 + a_{12}b_2 + a_{13}b_3 + ... + a_{1n}b_n) + \\
x_2(a_{21}b_1 + a_{22}b_2 + a_{23}b_3 + ... + a_{2n}b_n) + \\
x_3(a_{31}b_1 + a_{32}b_2 + a_{33}b_3 + ... + a_{3n}b_n) + \\
... + \\
x_n(a_{n1}b_1 + a_{n2}b_2 + a_{n3}b_3 + ... + a_{nn}b_n) \\
\end{array}
\right]} \\
&= {\left[
\begin{array}{c}
(a_{11}b_1 + a_{12}b_2 + ... + a_{1n}b_n) \\
(a_{21}b_1 + a_{22}b_2 + ... + a_{2n}b_n) \\
(a_{31}b_1 + a_{32}b_2 + ... + a_{3n}b_n) \\
... \\
(a_{n1}b_1 + a_{n2}b_2 + ... + a_{nn}b_n) \\
\end{array}
\right]} \\
&= A^T\vec{b}
\end{split}
}$

${\therefore \frac{d(min\ ||A\vec{x} - \vec{b}||^2)}{d(\vec{x})} = 2A^TA\vec{x} - 2A^T\vec{b} = 0 \\ \Rightarrow \vec{x} = (A^TA)^{-1}A^T\vec{b}}$
:::

> Note：
> 為甚麼找到的極值就會是最小值？
>> 因為這裡的 loss 必有最小值，所以對於一個二次式，==必為開口向上的 function==，因此找極值必為最小值

另外，也可以以幾何的方式解釋：


從上述的結果，我們可以發現，這其實是一個==投影問題==，${\vec{x} = (A^TA)^{-1}A^T\vec{b}}$ 相當於在 ${A}$ 的空間中，找到 ${\vec b}$ 的投影向量，我們假設投影出的向量為 ${\vec x}$，則 ${\vec{b} - A\vec{x}}$ 與 A 必為==正交關係==

${<\vec{b} - A\vec{x}, A> = A^T(\vec{b} - A\vec{x}) = 0 \\
\Rightarrow A^T\vec{b} = A^TA\vec{x} \\
\Rightarrow \vec{x} = (A^TA)^{-1}A^T\vec{b}}$

但由於 ==${A^TA}$ 只保證半正定 (Semidefinite)==，只能保證 ${det(A^TA)} \geq 0$，故無法保證 ${A^TA}$ 可逆

> Note：
> 因為在 data 中，可能有 (0, 0, 0, ..., 0) 的資料存在

:::info
### Semidefinite

For any vector ${\mu}$, if ${M^T\mu M}$ always ${\geq 0}$, then ${X}$ is called semidefinite.
:::

所以我們必須要==決定 w 以及每一項的次方 (basic function 的形式)==

:::info
### basic function

如果我們希望 input 是高次方的，可以令 ${\phi(x) = x^n}$，即可將一次的 input 轉換為 n 次的資料。
利用這種方式，即可將 ${x_0}$ fit to ${x_0^0,\ x_0^1,\ x_0^2,\ ...}$，
using ${\phi_0(x) = x^0,\ \phi_1(x) = x^1,\ \phi_2(x) = x^2,\ ...}$

:::

因為 LSE 是二次多項式，其微分為一次多項式，故 ==${E'(w) = 0}$ 有唯一解。==

以下我們以 sin 函數為例，在一個 sin 函數中取 9 筆資料作為我們的 training set，並以不同的次方模型進行訓練>


從上圖我們可以發現，次方的選擇會大大的影響預測的結果：
1. 當次方太小時，可能不足以表達一個較複雜的資料分布
2. 當次方太大，可能由於資料量的不足，而使我們誤判分布的趨勢；換個方式說，當次方太大時，可能將問題想得太複雜，雖然計算模型時，可以將所有點 (training set) 預估在趨勢線上，但對於其他未知的點 (testing point)，反而會做出錯誤的預判，也就是所謂的 overfitting。

上圖為利用 root mean square (RMS) 來評估訓練的結果，可以發現當維度提高時，對於 training set 來說，RMS 越來越低，但是 testing set 反而做出嚴重錯誤的結果。也就是說，對於這九筆資料，我們一樣可以利用高維的 model 來找出適合的方程式，但僅是對於這九筆資料，而非對於其他沒有被取樣的資料，因此在做 testing 時，才會反而得到更差的結果。

從以下各維度 training 出來的 model 參數，我們也可以發現，==當發生 overfitting 時，其係數的絕對值都非常的大。==


而造成 overfitting 的原因可能有以下幾點：
1. 訓練的資料量太小
2. 有雜訊

因此當我們將訓練的資料量提高，即可發現它與真實的 sin 函數更加相近。


:::info
### Root Mean Square (RMS)

對於每一點 input data 的 $y$ 及 $t$，我們可以計算其 RMS 為：
${\sqrt{\frac{\sum_{i=0}^N\ \{y(x_i, \textbf w) - t_i\}^2}{N}}}$
:::

# rLSE

為了解決係數太大的問題，我們可以==將係數的大小加入 loss error 中==，在某種程度上的避免 overfitting，也就是在 error 中，增加一項來懲罰係數太大的項：

:::danger
${E(\textbf w) = min\ \{y(x_n, \textbf w) - t_n\}^2 + \lambda\ || \textbf w ||^2}$
:::

然而，${\lambda}$ 的選擇也相當重要，太小則相當而沒有，太大則會造成前項的 error 不明顯而被忽略，本末倒置。


同樣，我們將其微分：

:::danger
${\frac{d(min\ \{A\vec{x} - \vec{b}\}^2 + \lambda\ || \vec{x} ||^2)}{dx} = \frac{d(min\ \{A\vec{x} - \vec{b}\}^2}{dx} + \frac{d(\lambda\ || \vec{x} ||^2)}{dx} = 2A^TA\vec{x} - 2A^T\vec{b} + 2\lambda \vec{x} \\
\Rightarrow \vec{x} = (A^TA + \lambda I)^{-1}A^T\vec{b}}$

因為 ${\lambda > 0 \Rightarrow \lambda I}$ is positive definite

所以如果 ${A^TA}$ 為正定，則 ${A^TA + \lambda I}$ 必定為正定，若前者不為正定，${A^TA + \lambda I}$ 仍為正定，因此可以保證其可逆性。
:::
:::danger

> Note：
> ${\begin{split}\frac{d(\lambda\ || \vec{x} ||^2)}{dx} &= \frac{d(\lambda \vec x^T \vec x)}{d\vec x} \\
> &= \lambda{\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{ccccc}
x_1 & x_2 & x_3 & ... & x_n
\end{array}
\right]}
{\left[
\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
... \\
x_n
\end{array}
\right]}\\
> &= \lambda{\left[
\begin{array}{c}
\frac{\partial}{\partial x_1} \\
\frac{\partial}{\partial x_2} \\
\frac{\partial}{\partial x_3} \\
... \\
\frac{\partial}{\partial x_n} \\
\end{array}
\right]}
{\left[
\begin{array}{c}
x_1^2\ +\ x_2^2\ +\ x_3^2\ +\ ...\ +\ x_n^2
\end{array}
\right]} \\
> &= 2\lambda \vec{x}\end{split}}$
:::

若以幾何來解釋：


上圖中藍色的等高線為不同的 ${\textbf w}$ 所得到的 ${\{y(x_n, \textbf w) - t_n\}^2}$，而實心土色的圓則為${|| \textbf w ||^2}$，因此 ${\lambda}$ 會影響最後結果接近哪個圓，若 ${\lambda}$ 很大，則會造成嚴重偏離藍色圓心，使得最後的結果並不是我們所期望的；但若 ${\lambda}$ 太小，則會產生 ${\textbf w}$ 係數絕對值太大的問題，而得到 overfitting 的結果。

這種方法被稱為 ==ridge relular LSE==，或是 ==L2 regular LSE==。

> Note：
> 藍色的同心圓在 ${(w_1,\ w_2,\ loss)}$ 的 dimension 中，即為 ${(w_1,\ w_2)}$ 對 ${loss}$ 的三維拋物線
> 

類似的方法還有 ==Lasso regular LSE==，或稱為 ==L1 regular LSE==：

:::danger
${E(\textbf w) = min\ \{y(x_n, \textbf w) - t_n\}^2 + \lambda\ || \textbf w ||}$
:::

以此方式對係數做懲罰，則會得到類似下圖的結果：


會喜歡使用 L1 regular LSE 的原因為，其==最佳點通常會發生在頂點上==，意味著其他維度的參數值皆為零，能簡化後續的運算。

> Note：
> 但是 ${\lambda ||\textbf w||}$ 不可微，必須要其他的數值方法來解