# 2.8 Dimensions of a Supervised Machine Learning Algorithm

假設我們現在有個 sample：

> ==$t$== 代表的是這 $N$ 個 instances 中的其中一個的 index
> ==$x^t$== 是一個任意維的 input
>> 例如以前區分 family car 的 class 的例子裡面，我們的 input 就是兩維的價格和引擎動力
>>
> ==$r^t$== 是對應的預期 output
>> - 如果我們的 classification 只有兩個 classes，那 $r^t$ 是 $0/1$。
>> - 如果我們的 classification 是 $K$-class $(K>2)$，那 $r^t$ 就是 $K$ 維的 binary vector，其中只有一個維度是 $1$，其餘都是 $0$。
>> （因為理論上我們預期每個 instance 只會屬於一個 class）
>> - 如果是 regression，那 $r^t$ 是某個實數。

$\rightarrow$ 這個 sample 是 <font color = "snake">independent and identically distributed (iid)</font>，這些 instances 的順序不重要，而且所有的 instances 都有同樣的 distribution $p(x,r)$

我們的目標是用 model $g(x^t|\theta)$ 去對 $r^t$ 建立一個好的、有用的 approximation。
> 為什麼是 approximation，如同前面講過的，我們的 data 可能不夠讓我們找到唯一的那個 hypothesis，因此我們需要一個 inductive bias，也就是 hypothesis class，去找出 mapping 結果最逼近 $r^t$ 的那個 model。

$\rightarrow$ 為了要去找到這個 approximation，我們必須去決定 三個東西：

1. model
2. loss function
3. optimization procedure

## 1. model


其中 $g(·)$ 定義了一個 hypothesis class $H$，然後某個特定的 $\theta$ 會去確立一個 hypothesis $h \in H$（也就是每一組 parameters 會定義一個 hypothesis）
> 舉例來說：
>
> - 在 class learning 中，我們用長方形當作我們的 model，而長方形的四個角就是我們的 parameters $\theta$
> - 在 linear regression 中，model 是 linear function，而斜率和截距是從 data learn 的 parameters

我們的 model，也就是 inductive bias，或是說 $H$，是由 ML 的 system designer 決定；而 hypothesis $h$ 的選擇（或者說是 parameters 的調整）則是由 learning algorithm 利用從 $p(x,r)$ sample 的 training set 來做。
> 為什麼我們可以說 model = inductive bias = $H$？
>
> 如同前面 $2.7$ 小節所說的，通常我們能夠拿到的 data 其實不足以去確立某個特定的 hypothesis，因此，我們引入了 inductive bias，像是前面提過的例子裡：
>
> 當我們希望找到某個方程式來 fit 一些點的時候，我們去限制 hypothesis class 是一條直線，或是一個二次曲線，或是三次式⋯⋯，這些限制劃分出一個個 hypothesis class $H$，我們是從這些很多的 $H_i$ 中每個各挑出一個最好的 $h_i$，再去比較這些 $h_i$ 到底哪個最好。
>> 這個例子的細節在 $2.6$

## 2. loss function

> ==$L(·)$== 是 <font color = "snake">loss function</font>，用來計算我們的 approximation $g(x^t|\theta)$ 和預期的 output $r^t$ 之間的差距。
>
> ==$E(\theta|X)$== 是 <font color = "snake">approximation error (loss)</font>，就是每個個別 instance 的 loss 的總和。

再詳細一點去解釋這個式子：

> 首先，我們的 model $g()$ 由某一組特定的變數 $\theta$ 去定義。
>
> $g()$ 這個 model 會把 input $x$（$t$ 是 $x$ 的 index，像是 input 1 就是 $x^1$）map 到它預測的 label。
> 舉例來說，如果只有兩個 classes，$g(x^1|\theta)$ 可能等於 $0$ 或是 $1$。
>
> 接著，如果是 output 是 $0/1$ 的 class learning ，$L(·)$ 這個 loss function 就會去檢查 prediction 和實際正確的 output 是否相等；在 regression 中，因為 $g(x^t|\theta)$ 的 output 是某個數值，所以我們能夠去計算預測和正確的差距，進而去排序。
>
> 最後，在我們對每個 input 都去計算 loss 以後，我們把這些 loss 加總，就是我們的 approximation error。簡而言之就是去計算每個 input 預期和實際的落差，然後加總起來，我們才能去比較哪個 model 比較好。

## 3. optimization procedure

透過前面的 approximation error 的計算，我們能知道各個 model 誰的 error 大，誰的 error 小，因此 optimization procedure 就是去找出某一組 optimal 的 $\theta$（以 $\theta^*$ 表示），來得到它定義的 error 最小的 model。

> $\rightarrow$ optomization procedure 是為了去找到某個 parameter 使得整體的 error 最小。
>
> 其中 $arg\min$ 會 return 使 error 最小的 argument
>> 在 regression 中，我們可以透過去分析最佳的結果來反推回去，但我們也沒辦法總是這麼做，如果是其他的 models 和 error functions，++optimization problem 的 complexity++ 就變得很重要。
>>
>> $\rightarrow$ 我們特別會去關注的是，它究竟是有一個單一的 minimum 對應到一個 globally optimal solution，還是有好幾個 minima 對應到許多的 locally optimal solutions。

為了讓整個設定順利進行，我們必須滿足以下的條件：

1. $g(·)$ 所定義出的 hypothesis class 必須夠大
> 也就是有足夠的 capacity 去涵蓋在 noisy form 的情況下，產生 $X$ 中 data 的未知 function。

2. training data 要夠多
> 才能讓我們從 hypothesis class 中找出正確的那個 hypothesis。

3. 要有夠好的 optimization method 來讓我們在給定 training data 的情況下找到正確的 hypothesis

不同的 ML algorithms 可能是 model (hypothesis class / inductive bias) 不同，或是用不同的 loss measures，又或是 optimization procedure 選的不一樣，在後面的章節就可以看到許多例子。