# ML2021 - Homework 1
### The Learning Problem
* [Question 1](#Q1)
### Modifications of PLA
* [Question 2](#Q2)
* [Question 3](#Q3)
### Extensions of PLA
* [Question 4](#Q4)
* [Question 5](#Q5)
### The Learning Problems
* [Question 6](#Q6)
* [Question 7](#Q7)
### Off-Training-Set Error
* [Question 8](#Q8)
### Point Estimation
* [Question 9](#Q9)
### Bad Data
* [Question 10](#Q10)
* [Question 11](#Q11)
### Multiple-Bin Sampling
* [Question 12](#Q12)
### Experiments with Perceptron Learning Algorithm
* [Question 13](#Q13)
* [Question 14](#Q14)
* [Question 15](#Q15)
* [Question 16](#Q16)

# Q1
### Hint
Find out whether the entire behavior in the options is suitable for using ML to make the effect or efficiency better

---

找出選項中的整個行為是否有適合使用ML的地方，使效果或效率變更好

# Q2

### Hint
If $x_{n(t)}$ is classified incorrectly at step t, use the following options to update it to ensure that the updated $w_{t+1}$ can be corrected for $x_{n(t)}$. In short, explain which of the following options $w_{t+1}$ can make $y_{n(t)}w^{T}_{t+1}x_{n(t)}>0$. You can calculate the `option [c]` and then solve the `option [e]`

---

在第t步時發生分類錯誤 $x_{n(t)}$，使用以下的選項進行更新能保證更新後的 $w_{t+1}$ 能修正 $x_{n(t)}$。簡言之，說明以下哪個選項的 $w_{t+1}$ 能使 $y_{n(t)}w^{T}_{t+1}x_{n(t)}>0$。可以算完`選項[c]`後再解`選項[e]`

# Q3

### Hint

Try to find the upper bound T for each option of Q2. No matter what kind of data set is selected, $\frac{T\rho}{\sqrt{T}R}$ can be greater than or equal to 1

---

試著找出[Q2](#Q2)每個選項的次數上限T。選擇不論何種資料集都能使 $\frac{T\rho}{\sqrt{T}R}$ 這項大於或等於1

# Q4

### Hint
Calculate $\rho$ and $R$ using $\rho = \min \limits_ny_n\frac{w^T_f}{||w_f||}x_n$ and $R^2 = \max \limits_n||x_n||^ 2$, then use $T \leq (\frac{R}{\rho})^2$ to find T. Because $w_f$ is unknown, we need to think about how to find $w_f$ through $f(x)=sign(z_+(x)-z_-(x)-0.5)$. Don't forget $||w_f||$

TA explanation : [Link](https://l.facebook.com/l.php?u=https%3A%2F%2Fdrive.google.com%2Ffile%2Fd%2F1zQpRmf1nBqNrJ2tisfS9H3Basz6TSDja%2Fview%3Fusp%3Ddrivesdk%26fbclid%3DIwAR2a7rbXuPMDjppANXAnIe5FaAGLLthVM_x-d-Xk5OCgpxPPFmsEM5fmILI&h=AT22xOkPxlHswYmDMQf-UknOxQiHjlzk8dlhqV_-OsNH94J1NYiiJmUDRj7GrEorgfXVqKRXF3FSkZLzxcoNEfp6iNyJobdnBEL5Wiy32pvDTJURuovQ3vohuzp6ksT7LuoxIm1nY2YK3JxToEBKuw)

---

計算 $\rho$ 與 $R$ 使用 $\rho = \min \limits_ny_n\frac{w^T_f}{||w_f||}x_n$ 與 $R^2 = \max \limits_n||x_n||^2$，再使用 $T \leq (\frac{R}{\rho})^2$求得 T
因為 $w_f$ 是未知的，需透過 $f(x)=sign(z_+(x)-z_-(x)-0.5)$ 來思考如何找到 $w_f$。記得有 $||w_f||$ 這項

TA 講解 : [Link](https://l.facebook.com/l.php?u=https%3A%2F%2Fdrive.google.com%2Ffile%2Fd%2F1zQpRmf1nBqNrJ2tisfS9H3Basz6TSDja%2Fview%3Fusp%3Ddrivesdk%26fbclid%3DIwAR2a7rbXuPMDjppANXAnIe5FaAGLLthVM_x-d-Xk5OCgpxPPFmsEM5fmILI&h=AT22xOkPxlHswYmDMQf-UknOxQiHjlzk8dlhqV_-OsNH94J1NYiiJmUDRj7GrEorgfXVqKRXF3FSkZLzxcoNEfp6iNyJobdnBEL5Wiy32pvDTJURuovQ3vohuzp6ksT7LuoxIm1nY2YK3JxToEBKuw)

# Q5

Discuss separately how to update $w$ when $g(x)$ is wrongly selected. Remember that Multiclass PLA updates $w_1$ and $w_2$ at the same time. The weight of correct label will add $x_n$, otherwise, the weight of wrong label will be subtracted $x_n$.

---

分別討論 $g(x)$ 選錯時，會如何更新 $w$。記得 Multiclass PLA是同時更新 $w_1$ 與 $w_2$，正確的標籤會加上 $x_n$，反之，錯誤的減去 $x_n$。

# Q6

### Hint
* `Active` : improve hypothesis with fewer labels (hopefully) by asking questions strategically
* `Reinforcement` : learn with partial/implicit information (often sequentially)
* `Multi-class classification` : classify input to multiple (or no) categories
* `Self-supervised learning` : recipe to learn physical knowledge before actual task
* `Online` : hypothesis improves through receiving data instances sequentially

---

* `Active` : 通過有策略地提出問題，用更少的標籤（希望如此）改進訂好的假設
* `Reinforcement` : 使用部分/隱式信息學習（通常按順序）
* `Multi-class classification` : 將輸入分類到多個（或沒有）類別
* `Self-supervised learning` : 在實際任務之前先學習物理知識
* `Online` : 將訂好的假設通過有順序的接收實例數據來改進

# Q7

### Hint

# Q8

# Q9

# Q10

# Q11

# Q12

# Q13
Data : [Link](http://www.csie.ntu.edu.tw/~htlin/course/ml21fall/hw1/hw1_train.dat)

The following are all program questions, remember to change the random seed for different experiments. The program can use this [Link](https://carbon.now.sh/?fbclid=IwAR0iwx_ujw9B5alx_ji6ba6yYGctGch5gUkpmmBxUJjriLXgYxnNqJdcaRE) to submit

---

以下皆為程式題，記得不同次實驗的random seed要更改。程式可以使用[Link](https://carbon.now.sh/?fbclid=IwAR0iwx_ujw9B5alx_ji6ba6yYGctGch5gUkpmmBxUJjriLXgYxnNqJdcaRE)來繳交

# Q14

# Q15

# Q16