---
tags: COTAI LHP
---

# Lecture Notes ML4AI 2021

## Session 1 -- Linear Predictors

**I. Lý thuyết:**
- Mô hình TEFPA của linear regression:
**1. T- Task**
- Input X là các loại số liệu numerical data liên tục
- Output Y là 1 con số liên tục (continuous variable) chẳng hạn như dự đoán giá nhà,... --> sau đó so sánh với y thực tế bằng hàm Loss để căng chỉnh các parameters
- Nhiệm vụ chính là chỉnh các parameters của phương trình sao cho y dự đoán generalize gần đúng với y thực tế tốt nhất có thể (nhưng không bị overfitting)

2. **E-Experience**

- Chúng ta cung cấp cho máy tính dữ liệu thực tế (gồm các nhóm input x và output y trong thực tế, $\{(x^t,y^t)\}_{t=1}^n$)

3. **P- Performance**

- Sử dụng hàm loss để đánh giá được model (sự khác biệt giữa giá trị liên tục y dự đoán và y thực tế từ các điểm input data points)

**4. F-Function Space**

- Không gian hàm số phải tối ưu chính là không gian tuyến tính có các trục tọa độ là các giá trị parameters được máy tự căn chỉnh khác nhau và trục output chính là giá trị lấy được từ hàm Loss

**5. A-Algorithm**

- Có nhiều cách khác nhau để đưa giá trị Cost Value xuống global minimum, với 1 tập data đơn giản ít input thì có thể dùng gradient descent
- Thực ra thứ được tạo ra từ linear regression không phải là 1 đường thẳng mà thứ được tạo ra là 1 mặt phẳng (hay còn gọi là siêu phẳng) tùy vào cái dimension của data inputs mà mình offer

**II. Classifcation:**


Classification vs. Clustering?
--> phân loại dựa trên ý muốn cùa máy tính (nếu muốn dựa trên ý của mình thì phải có labels )

***1. Similarity measures:***
- Feature Vector is basically a vector that is composed by many values of its features (e.g [1,2,5,6,7] each value represent a meaning for the feature it measures) --> những con số này thường mang nghĩa biểu tượng cho meaning nó represent hơn là mang giá trị đại số cụ thể 

- Nói rõ hơn về các loại similarity measure
+ Distance:
* Euclidean distance: $\text{In general: } d(A,B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + \cdots + (z_1 - z_2)^2}$
* Manhattan Distance: we use it when we need to calculate the distance between two data points in a grid-like path 

* Chebyshev distance: 

* Cosine distance: use when the magnitude of the two vector does not important but the orientation 

+ Classfication: regression of score on each predicting class 

- Các function cần reminded:
+ Softmax: 

**II. Về phần code:**
- Import tập LinearRegression() từ sklearn.linear_model
- Chuẩn bị dữ liệu dưới dạng Numpy Array (nhớ reshape lại x với x.reshape(-1,1))
- Model= LinearRegression() để tạo
- Có thể dùng câu lệnh như X_train, X_test , y_train, y_test = train_test_split(X, y, test_size =0.2, random_state=42) trong train_test_split để phân ngẫu nhiên tập luyện với test nếu cần thiết
- Model.fit(x,y) để luyện
- model.score() để đánh giá accuracy của model

---

## Session 2: Cách trích ra features để đưa vào
- Cơ chế chung: $X \to Z \to$ Model (từ dữ liệu X raw input data chiết xuất ra các features Z)
- Có 5 cách để triết xuất ra các đặc trưng (features):
1. Sparse Coding:

- Embedding coordinates with very few nonzeroes

- Represent most values in the given vector (pixel values in images for example will be 0s)

2. Feature Engineering- Hand-crafted:
- Exploiting the already-existing features (not automatically made and self tuned like in CNN)

4. PCA: principal components analysis
$$X = X_{avg} + \alpha_1 U_1 + \dots + \alpha_n U_n$$
with *orthonormal* features $U_i$ and coordinates ${\bf z} = (\alpha_1,\dots, \alpha_n)$.
5. Convolution kernels
6. Word embeddings
- "so khớp"

- Convolution basically là trượt qua ảnh để kiểm xem có 1 featura A ko (convolution layer)

***II. Face decomposition***
- Về PCA:

- PCA giúp chiết xuất các features quan trọng
- Như việc có thể triết xuất các features để tạo ra các thuật toán tự tạo khuôn mặt

**PCA in depth:**
- Basically để plot trên graph để visualize data (giảm chiều không gian để làm chuyện đó) --> cho clustering
- PCA sẽ cho chúng ta biết variables nào là tốt nhất cho việc clustering

**Cách PCA hoạt động**
- Calculate the center of the given data (Ví dụ như data có 2 dimension là x và y, ta sẽ tính toán x trung bình của data trên trục Ox trước, sau đó tương tự với điểm trung bình y trên trục Oy. Từ đó, tọa độ điểm trung tâm của data sẽ cho là $(x_{tb}, y_{tb})$ )
- Shift the graph (PCA.transform và PCA.fit) --> shift làm sao cho điểm center sẽ nằm ở tọa độ O $(0,0)$
- Sau đó, vẽ 1 đường line (na ná như linear regression) mà fit với điểm dữ liệu sau khi đã dịch chuyển

---

## Session 3:
**I. Linear and Nonlinear surface:**

- Mặt phẳng: được tạo ra bởi Ax+By+Cz+Dl+...=0 (giống như trong trường đã học, đây là phương trình cấu hình nên mặt phẳng)

- Nonlinear chính xác hơn
- Nonlinear seperable: đôi khi do dataset có nhiều noise nên dữ liệu không chia cắt ra các class hoàn hảo được --> chỉ có thể dùng nonlinear model để

II. Lỗi manifold:
- Entangled embedding manifolds: các dữ liệu khi chưa biến đổi thì không thể thực hiện
--> phải biến đổi lại để tốt hơn

**II.Data transformation (L)**
- X -(B)-> Z -(T)-> Z' -(L)->L
- Đưa từ z=(x,y) về thành x'(x,y,h) (đưa về 1 chiều không gian khác -có thể nhiều dimension hơn để chia cắt các class tốt hơn)
- Vì sao t phải transform nó? Để model work được
- CNN kernels khi extract feature cũng làm việc tương tự, đưa ảnh về các feature maps để thay đổi mô hình không gian của nó để làm việc được
- Entangle embedding manifolds --> đưa ra 1 chiều không gian khác

**III. Linear/Nonlinear Transformation:**
- Đưa vào 1 chiều không gian Z phẳng --> đầu ra Z' cũng phẳng là linear transform
- có thể được biểu diễn bằng 1 ma trận nhân và (matrix multiplications)
- Bản chất của linear transformation: xoay, co giãn, then rotate/flip again


- Nonlinear --> đầu ra Z' cong (có thể đưa vào mô hình sigmoid chẳng hạn để bẻ cong từ thẳng --> nonlinear)
- Có thể được biểu diễn bằng 1 ma trận xong bóp méo nó (y^= s(ax+b))

**IV. Ví dụ:**
- Multi-layer perceptrons: Z' --> Z'' --> Z''' --> ... --> Y (cứ mỗi lớp biến đổi thêm môi trường data cho đến khi linear seperable)
Φ(z)= 𝛾(𝐴z+𝑏) is called a perceptron layer
- Example: 1. Linear transformation of

- Hàm softmax là 1 loại linear predictor (linear seperable)
**V.Kernel trick**

**VI. Locally non-linear models:**
- Chia không gian lớn thành các vùng không gian nhỏ hơn để linear seperable

---

## RecSys:

**I. Problems:**
- Longtail issue:
 

--> những mặt hàng tốt với 1 nhóm người nhưng lại ít phổ biến (niche products)
--> có 1 trade-off ở đây: cân bằng giữa độ phổ biến và trải nghiệm cá nhân để đưa ra trải nghiệm phù hợp

- Problem formulation:

https://upload.wikimedia.org/wikipedia/commons/5/52/Collaborative_filtering.gif

- Reminder of embedding:
1. Embedding nghĩa là biến 1 label nào đó về dạng 1 vector (trước đó chúng ta đã từng có LabelEncoder : biến 1 label thành 1 số k bất kì, và OneHotEncoder: biến 1 label thành chuỗi các con số 1 và 0)
Ví dụ: mỗi chữ cái ở trên coi như là 1 label kkhác nhau --> chúng ta map những chữ cái đó thành 1 vector với các giá trị khác nhau . Các con số (biểu thị cho thang màu) chỉ mang ý nghĩa biểu tượng symbolic để biểu thị cho 1 cái meaning nào đó
Chúng ta có thể dùng các câu lệnh như most_similar_given để map ra bản đồ chung như này:

**II. Các cách tiếp cận vấn đề:**
- User-based filtering (assumption là 2 người giống nhau sẽ mua những sản phẩm tương tự nhau)
- Items-based filtering (assumption là khi thấy mọi người khi mua sản phẩm A sẽ mua thêm sản phẩm B, nên nếu có 1 người dùng mua sản phẩm A/ hay B thì recommend sản phẩm còn lại)

--> Key idea: similarity! Key question: what are the embeddings of users & items?

**III. Input data:**
- Potential input data để đưa ra dự báo:


**IV. RecSys taxonomy:**


- Các công thức tính độ giống nhau đã biết: cosine similarity, dot product, distance

***- Item-based CF:***
==This picture is inaccurate. Use [this one](https://i.imgur.com/1KYqMCm.png).==

- Giải thích:
1. Có 4 người dùng (u1,u2,u3,u4) và 3 món đồ (i1,i2,i3)
2. Tạo vector embedding v1 cho i1, v2 cho i2 và v3 cho i3 (giải thích: 2u1 là do người dùng u1 đã rate i1 với giá trị là 2...) (những cái 0 là những cái mà người dùng chưa rate - ví dụ người dùng u4 chưa rate sản phẩm i1 )
3. Đã có được vector embedding của 3 items --> so sánh độ giống nhau giữa chúng bở cosine similarity --> vẽ được cái bảng ở phần 2.2
4. Sử dụng công thức rating để dự báo giá trị mới (ví dụ dự đoán người dùng u1 sẽ rate i2 với giá trị là bao nhiêu). Tính bằng cách so với các giá trị khác đã có sẵn trong cái row đó (ví dụ: u1 đã rate i1 và i3 )

--> Key idea: items as features
→ compute user-user similarity matrix. Note that simply transposing the utility matrix [the table in step 1] in user-based CF before computing gives item-based CF result (more efficient since #users ≫#items).

***- User-based CF:***
- Giải thích:

1. Step 1 : Normalize lại tất cả các giá trị trong bảng : n-k (n: là giá trị thực tại, k là giá trị trung bình) (các chỗ chấm hỏi sau khi normalize sẽ có giá trị là 0) (lưu ý: không chia cho range vì mình không normalize trên scale từ 1 -> -1)
2. Từ bảng ở phần b) --> ta đã có được tọa độ vector embedding cho từng user
3. Dùng cosine similarity ta vẽ được bảng ở phần c)
4. Nhìn sang bảng ở cột d), giả sử chúng ta muốn dự đoán giá trị u1-i1, chúng ta thấy rằng i1 mới chỉ được ba người vote
5. Nhìn sang bảng e), ở đây chúng ta sử dụng phép KNN và chọn k=2, nghĩa là chúng ta chọn 2 người user giống với u1 nhất (nhớ rằng ở đây chúng ta làm cosine similarity dựa trên vector embedding của các user) (ở trường hợp này, 2 người giống với user nhất là u0 và u5- nhớ rằng trong cosine similarity là số càng cao thì càng giống nhau).

**Matrix factorization:**


- Idea: chuyển các user và items ra các embedding vectors --> sau đó stack them up tạo thành các matrix
- Lấy vector embedding của user i (i.e. Zi) nhân với (dot product) của vector embedding của item j (i.e. Zj ) nhân với nhau sẽ ra rating của người i cho item j

---

## S5. Evaluation:
**Cách đánh giá model:**

- Regression thường dùng MSE
- Để hàm đó optimize tốt --> fitting f(x) in D model
- Mô hình cũng phải generalize tốt:
- Interpolation: data đưa vào training
- Extrapolation: data phải dự đoán (data không có trên tập training) --> key cho generalization
- Combinatorics: xảy ra khi ta đưa vào model 1 input hoàntoàn mới, không phải input máy tính được dạy và được train

- Trong các linear classifier có độ accuracy cao như nhau --> largest margin model should be choosen (đường thẳng/siêu phẳng phân chia dữ liệu nằm cách xa dữ liệu được cho nhất)


**Các chuẩn evaluation khác trong regression:**



**Chuẩn đánh giá của classification:**
- Natural metric : chỉ cần đánh giá lỗi (class dự báo khác class thực tế)
--> confusion matrix dạng đếm :

Đường chéo là đúng, còn lại là lệch

--> phiên bản normalized (giống %)
Như có thể thấy được, dự đoán hoa versicolor chỉ đúng 62% , trong khi 2 cái còn loại đúng hết 100%
--> đánh gia bị imbalanced

**Precision và Recall**


-Giả sử chia ra 2 cái (dạng binary) là Positive (dự đoán 1) và Negative (dự đoán là 0)
1. Precision: quantifies the number of correct positive made
2. Recall: how many "real-positive" numbers have been made

**ROC:**
TPR vs FPR

**Smooth proxy losses:**
- Chuyển đổi để gradient descent trượt được đến optimal losses

- Tạo ra đường large margin model (cách xa các điểm cần phân chia nhất) --> cách đều các điểm cần phân chia --> chống nhiễu tốt
- c lớn --> margin nhỏ (trade-off giữa margin và accuracy)
- gamma : độ cong của decision boundary

## Session 6: Midterm exam

Students copy Markdown code of these questions to their Lecture notes and write down solutions in there.

1. [**5** Point] Given a set of inputs $(X^1,\dots,X^N)$, we use PCA to represent them as $X^t = X_0 + z_1U_1+\dots+z_nU_n$ with $X_0$ the mean input and $U_i$ the orthonormal principal components.

- [**2** Points] Write down equation for $X_0$, and equations for properties of $U_i,U_j$: unit length & mutual orthogonal. **Solution**: $X_0$ = $\sum \left ( x_{1} +x_{2}+... + x__{n} \right )$ /n với n input
, unit length là độ dài của vector đó trong không gian đa chiều hơn,
- [**1** Point] We need to reduce the dimensions of $X^t$ to visualize them on 2D. What is the embedding vector ${\bf z}^t$ of $X^t$ if we use only 2 first principal components to represent it? What is the last feature of ${\bf z}^t$ in this case? **Solution**: dùng Z=($1, Z_{1}$, $Z_{2}$)^T

- [**1** Point] What are the main differences between representations by PCA and by sparse coding? **Solution**:
Sparse Coding: chuyển đổi cái original data đến dạng sparse mà ở đó các data được mã hóa đa phần ở dạng 0s, nhưng vẫn có thể mã hóa để chuyển đổi lại data ban đầu được. Tuy nhiên, ở PCA, chúng ta sẽ bị mất data hoàn toàn (PCA khi ép xuống dimension thấp hơn sẽ gây mất thông tin)

- [**1** Point] If we cluster the dataset into 3 groups with centroids $({\bf m}_1, {\bf m}_2, {\bf m}_3),$ what is the label embedding coordinates of $X^t$ if it belongs to cluster 2? **Solution**: $X^(t,2)$

2. [**1** Point] If we use each song as a feature to represent the users, what is the embedding coordinates ${\bf z}_A$ of user A in the dataset below? **Solution**:
${\bf z}_A$ = (5*i1, 5*i2, 0*i3, 1*i4, 1*i5) với i1, i2,i3,i4,i5 là các bài hát

3. [**3** Point] From the general form of linear predictors: $\hat{y}=\mathsf{s}(Wz+b)$ with $\mathsf{s}(\cdot)$ a transfer function for desired output interpretation.
- [**1** Point] What is $W$ for
- 1 dimentional linear regression? **Solution**: W là weight cho phương trình đường thẳng
- sofmax regression with 3 classes? **Solution**:$\hat{y}=\mathsf{s}(W_{1}* Z_{1}+W_{2}* Z_{2} + W_{3}* Z_{3})$

- [**1** Point] What is function $\mathsf{s}(\cdot)$ for
- 1 dimentional linear regression? **Solution**: đây là hàm identity
- SVM binary classification? **Solution**: đây là hàm sign
- [**1** Point] Why logistic regression (for binary classification) has only 1 probability output while there are 2 classes? **Solution**: vì probability của cả 2 classes khi công lại sẽ ra là 1 nên chỉ cần represent 1 cái là đủ

4. [**2** Points] Evaluation procedure
- [**1** Point] Explain the main use of the train--dev (validation)--test sets. **Solution**: đo đạc performance của model trên tập dataset mà nó chưa từng thấy trước trước khi thử nó trên tập test

- [**1** Point] What are the main similarity and differences between linear SVM and logistic regression? **Solution**: giống nhau: cả 2 đều được dùng trong mục đích chung để phân loại ; khác nhau:

5. [**2** Points] There are **1100 items** and **one million users**. We need to build a content-based RecSys by extracting **120 features** ${\bf z}_i$ describing each item $i$ then learn a classifier ${\bf \theta}_j$ for each user $j$ to predict **ratings from 1 to 5 stars** of each user for each item.
- [**1** Point] How many classes do we need? **Solution**: có 5 classes
- [**1** Point] What is the size of $W$ if we use softmax regression $\hat{y}=s(Wz+b)$ for to classify ratings? **Solution**: sẽ là matrix với shape là (5,120)

6. [**2** Points] Nonlinear predictors have general form $\hat{y}=s(W'\phi(z)+b')$. For Multilayer Perceptrons (MLP) in particular: $\phi(z) = \gamma(Wz+b)$ recursively, each called a "hidden layer".
- [**1** Point] Give explicit equation of an MLP with 2 hidden layers. **Solution**:
$\phi(z_{1}) = \gamma(Wz+b)$
$\phi(z_{2}) = s(W'$ $\phi(z_{1})+b')$

- [**1** Point] What are the parameters of the fully-connected layer in your equation? **Solution**:
đó là W và b

7. [**2** Points] Kernel machines use "kernel trick" $\phi(z_i)\cdot\phi(z_j) = \kappa(z_i,z_j)$.
- [**1** Point] Explain why kernel trick is useful. **Solution**: kernel trick giúp tiết kiệm và thời gian, đồng thời có thể giúp model perform tốt hơn
- [**1** Point] Explain how we can use kernel trick in feature-space prediction $\hat{y}=s(W^\phi\phi(z)+b)$ to turn a linear predictor into a nonlinear one. **Solution**:

---

## Midterm Coding (1 hour)
[Đề thi](https://colab.research.google.com/drive/1WuytAqhN_6EBZQK-0S7YYDiiu_MHy41V?usp=sharing).

## Decision Tree:

### Bagging:


Random Forest:
1. Using bootstraped dataset to train many different tree forests.
2. For each decision tree in the forest, at each node only consider a subset of variables as potential classifier candidates (in contrast to considering all variables as classifier candidate for each node). ==> this will create a variety of decision trees in the forest.
3. Basicallly follow the model of bagging to ensemble the results.

### Boosting
#### AdaBoost:
Simply put, the idea is to set weights to both classifiers and data points (samples) in a way that forces classifiers to concentrate on observations that are difficult to correctly classify.
The process was done sequentially:

* Khởi tạo weight ban đầu là bằng nhau (bằng $1/N$) cho mỗi điểm dữ liệu
* Tại vòng lặp thứ i
- Train model $w_i$ (weak learner) mới được thêm vào.
- Tính toán giá trị loss (error) của model đó, từ đó tính toán ra giá trị confidence score của model vừa train
- Cập nhật model chính $W = W + c_i$
- Cuối cùng, đánh lại trọng số cho các điểm dữ liệu (Các điểm dữ liệu bị đoán sai --> tăng trọng số, các điểm dữ liệu đoán đúng --> giảm trọng số).

* Sau đó lặp lại với vòng lặp thêm model tiếp theo `i + 1`.


## Convolutional
- Filter hoạt động dựa trên nguyên tắc tích chập
- Lý do có hình vuông : để lấy được điểm ở giữa
- Có padding xung quang --> dimension sẽ không giảm
- Max pooling --> output sẽ sharp , trong khi với average pooling thì output sẽ smooth hơn nhiều
- Có 3 kênh màu --> kết quả cộng lại chia cho 3
- Nhớ là mỗi lần lướt filter --> kết quả sẽ có cộng thêm 1 bias

--> có 28 trọng số (9 trong mỗi filter cùng với 1 bias cuối cùng)

- Vì filter là để lấy điểm ở giữa --> thêm padding để không bị mất data ở ngoài rìa
- Convnet đi chiết xuất các đặc trưng local, trong khi mạng MLP là các đặc trưng global
- Max Pooling
- Receptive field
--> điểm màu vàng trong lớp cuối cùng theo toán học là tượng trưng cho toàn bộ hình ở layer 1
- Stack nhiều lớp convolution lại để máy tính có thể tahays được 1 bức tranh tổng thể (nhờ việc cuối cùng nó thấy được những điểm nhỏ đại diện cho tấm hình rộng ban đầu)

- Làm sao nó có thể thấy được cái feature phức tạp ? Nó sẽ dùng những filter tượng trưng (hay để tìm) những features nhỏ hơn
--> ví dụ như trên hình, phần cuối cùng là những features nhỏ/đơn giản nhất
- Các features nhỏ này sẽ kết hợp với nhau để tạo ra những features phức tạp hơn

- Công dụng của filter:
--> phía trên là filter detect đường viền (được biểu thị bởi việc chuyển từ vùng sáng qua tối)

# Recurrent neural networks (RNNs)

- Dữ liệu ảnh được đưa vào sẽ được chiết xuất đặc trưng --> rồi đưa lên không gian nhúng (tạo nên 1 điểm dữ liệu trong tọa độ khồng gian nhúng)
)
Ảnh sau khi đưa lên không gian nhúng

- RNNs --> phân tích dữ liệu dạng chuỗi

- Ứng dụng

- Chuyển động trong không gian nhúng

--> di chuyển trong không gian khái niệm để tạo ra những khái niệm mới


- Làm sao để tạo ra 1 khái niệm mới (về mặt toán học)
${\bf h} \to {\bf h'} = \sigma\Big(U{\bf h} + W {\bf x} + {\bf b}\Big)$

Đưa khái niệm cũ (h) cộng thêm biến đổi trong chiều không gian nhúng (x) --> tạo ra 1 khái niệm mới (h')

${\bf h}_{t-1} \to {\bf h}_{t} = \sigma\Big(U{\bf h}_{t-1} + W {\bf x}_t + {\bf b}\Big)$

Output cuối cùng cho ra lần này (${\bf h}_{t-1}$) sẽ quay lại làm cho input dữ liệu (vòng lặp tiếp theo) --> tạo ra output mới thêm (${\bf h}_{t}$)

**- Vanilla RNNs:**

--> chỉ có x và W và b là thay đổi

Continue performing the same way to update the value of the hidden state for an arbitrarily long sequence of observations.


- Common structures of RNNs:

**- Vanishing / Exploding gradient:**

1. *Vanishing* --> khi backpropagation thì gradient ngày càng nhỏ đi đến gần như biến mất
2. *Exploding* --> tương tự vậy như gradient càng ngày càng lớn

**- Vấn đề short-term memory của RNN:**

--> chọn những model tốt hơn của RNNs

# Clustering:
**Ứng dụng**:
- Tương tự như PCA --> dùng để giảm chiều không gian xuống

**Giới thiệu clustering**
- Mỗi cụm sẽ được biểu diễn bởi 1 centroid (nó tương tự như cách mỗi class được biểu hiện trong supervised learning)
--> điểm centroid biểu diễn cho cụm đó là điểm trung bình của cả cụm
- Cách tính chiết xuất của centroid: giả sử mỗi Z input có 5 chiết xuất (features) là Z1 -->Z5. Cách tính trung bình cho C1 của centroid trọng cụm đó là tính Z1 trung bình của các giá trị input Z trong khoảng đó

- Khi có input mới vào --> dùng euclidena distance để xem điểm đó gần với centroid nào nhất --> gắn input vô cụm đó

Đây là K-means clustering (chia data thành K nhóm)

**Cách algorithm hoạt động**

- Chọn n điểm làm centroid bất kì --> mối điểm sẽ được assign với centroid được chọn gần nó nhất (assign a point to the nearest clusters/centroid) --> sau đó tạo được n nhóm với các điểm gần nhất với nó (lưu ý số lượng các điểm trong từng nhóm có thể khác nhau) --> tính means (trung bình của từng cluster) --> tiếp tục so sánh với các điểm rồi tính toán lại --> centroid sẽ di chuyển dần dần lên
- Thuật toán (iteration) sẽ ngừng khi sau khi so sánh khoảng cách từ các điểm đến centroids thì các điểm không còn thay đổi nhóm nữa (clusters no longer change)
- Thuật toán (phụ thuộc vào số iterations) sẽ lập đi lập lại tương tự (nhưng với các điểm lựa chọn random ban đầu sẽ khác nhau)
- Cuối cùng, dựa vào chuẩn đánh giá --> đánh giá trường hợp chia K-clustering nào là tốt nhất





**Chuẩn đánh giá (metrics)**

1. Seperability --> khoảng cách giữa các nhóm với nhau phải xa nhất có thể
2. Intra cluster similarity --> các điểm trong đó phải gần nhau mới tốt


--> Objective: minimizing mean sum of intra-cluster distances (e.g., Euclidean distance) (đây cũng là hàm loss của chúng ta)

**Heuristic**
- Chọn K số nào cho tốt ?
Elbow-method
- Thông thường, hàm đánh giá của chúng ta sẽ dựa trên number of variation bên trong mỗi cluster --> vì vậy, như 1 lẽ tự nhiên, hệ số k càng lớn (càng chia thành nhiều cụm) thì số variation sẽ càng giảm
- Elbow-method: như hình trên, từ k=3 trở đi thì sum of squared errors không còn giảm nhiều như trước


Silhouette medthod

--> chọn chỉ số silhouette cao nhất


## ML4AI Session 12 Final Exam (for Students)

<br>


<br>

CoTAI AI Training Program for Highschool Students

© [CoTAI](https://gem.cot.ai) 2021

---

Open book. Choose to answer as many questions as possible, as concisely as possible. Ask instructors if you have difficulty in understanding the questions.

**Questions**

1. [**8** Points] The unified TEFPA framework to build a ML model: task $\mathcal{T}$, experience $\mathcal{E}$, function space $\mathcal{F}$, performance $\mathcal{P}$, and algorithm $\mathcal{A}$ to search. What are the elements in TEFPA framework...
- 1.1 [**2** Point, 3.1] to build a face recognition model using a DCNN?

Task: Input là ảnh khuôn mặt, output là 1 label (ví dụ là tên người)

Experience: học tập dựa trên tập ảnh input (gồm nhiều ảnh đến từ nhiều khuôn mặt của nhiều người), mô hình học cách dự đoán xem ảnh nào là thuộc về người nào

Function Space: concept embedding space

Performance: Dùng Categorical Crossentropy hay Sparse Crossentropy để tính toán hàm loss, từ đó backpropagagate lại để model tự tinh chỉnh thông số

Algorithm to optimize: thường dùng các thuật toán như Adam, RMSprop,...

- 1.2 [**2** Point, 3.1] to build a RecSys? (using one of the models you have learned: item-based, user-based, content-based, MF)
Model user-based
Task: input là thông tin của người dùng (chẳng hạn như người A đó rating sản phẩm A như thế nào) và người A và người b giống nhau như thế nào. Output là người B đó sẽ phản ứng như thế nào đối với sản phẩm A (dựa trên thông tin có được từ người A và sản phẩm A đó)

Experience: rating (hay phản ứng nói chung) của người A đối với sản phẩm A, độ giống nhau giữa người A và người B

Function Space:

Performance: đánh giá dựa trên cosine similarity

Algorithms: tính toán cosine similarity --> dự đoán được phản ứng của người B với món đồ A( rating)

- 1.3 [**2** Point, 3.1] to build a customer segmentation model using k-means?
Task: input là lượng thông tin của các khách hàng (như là giới tính, độ tuổi,..). Output là chúng ta có thể phân chia được các nhóm khách hàng và visualize được data bằng 2D
Experience:
Function space: trên bất cứ chiều không gian nào (thường làm 2D hay 3D để visualize boundary hay clusters được). Nếu muốn visualize k-means clustering cho dữ liệu có số chiều cao hơn 3 thì đầu tiên phải dùng PCA để giảm số chiều lại trước, sau đó plot lên 2D hay 3D plot
Performance measure: độ khít giữa các điểm trong cùng 1 cluster
Algorithm to optimize: elbow method hay Silhouette method để chọn số k hợp lý

- 1.4 [**2** Point, 3.1] to build a sentiment analysis model (good, bad, neutral comments) using RNN+Softmax Classifier?
Task: input là những con số thể hiện cho các từ trong câu đó, output là nhãn đánh giá câu đó (good, bad, neutral)
Experience: concept embedding spaces của các từ
Function space: không gian word embedding của các từ đó
Performance
Algorithms : Vanilla RNN, LSTM,...
2. [**6** Points] Convolutional filters (or kernels)
- 2.1 [**1** Point, 1.1, 3.2] How do we extend them from dot product?
Lấy vùng được cover (bởi filter) rồi dot product với filter lướt ra --> slide dần tạo ra feature map
- 2.2 [**1** Point, 1.1, 3.2, 3.4] Why do we call their outputs "feature maps"?
Gọi là feature map bởi vì các output này map lên những feature bậc cao hơn từ những ảnh ban đầu đã có
- 2.3 [**1** Point, 3.2] Explain padding: how to do & main purpose
Padding số 0 xung quanh ảnh --> để không bị mất thông tin ở rìa, đồng thời không làm giảm size của ảnh
- 2.4 [**1** Point, 3.2] Explain pooling: how to do & main purpose
Dùng Maxpooling hay Average Pooling --> lấy ra được những feature quan trọng nhất, đồng thời giảm mạnh chiều không gian của bức ảnh/feature xuống
- 2.5 [**1** Point, 3.2] Explain stride: how to do & main purpose
Stride là độ lướt của filter trên bức ảnh (ở cả lớp convolution và lớp Pooling). Stride sẽ là yếu tố quyết định dimension của bức ảnh lúc sau
- 2.6 [**1** Point, 3.2, 3.4] Explain their **effective** receptive field: why do they produce highly absstract features?
Vì filters lúc đầu thường lấy ra những features đơn giản nhất trong bức hình (như đường thẳng , đường viền,...). Càng về sau thì filters chiết xuất các features ngày càng bậc cao hơn
3. [**6** Points] Recurrent neural networks (RNNs) can be used for sequential modeling.
- 3.1 [**1** Point, 3.2] What does sequential data mean?
Là data dạng chuỗi
- 3.2 [**1** Point, 1.1, 3.2, 3.4] Explain each element in this basic equation of RNNs $h_t = \mathsf{\gamma}(Ah_{t-1}+Wz_t)$

- 3.3 [**2** Point, 1.3, 2.1, 3.2] What does back-propagation-through-time mean, why do we need it instead of using plain back-prop, and how does it work for training RNNs?
Là backpropagate theo time steps
- 3.4 [**1** Point, 1.3, 3.2] Explain vanishing gradient problem for simple RNNs.
Càng về sau gradient descent của model càng nhỏ đi (lúc backpropagate ngược lại), dẫn tới đến khi gradient descent quá nhỏ
- 3.5 [**1** Point, 3.1, 3.3] If we want to classify the sentiment of each user comment (good, bad, neutral) at the end of each sequence using RNN+Softmax classifier: explain briefly the model architecture.
Embedding layer --> các lớp LSTM --> các lớp Dense --> lớp output
4. [**6** Points] Planning in Markov Decision Process (MDP) $(S,A,T,R,\gamma)$.
- 4.1 [**1** Point, 3.1, 3.2] Explain 5 elements in MDP model (equation of each element if available).
Có state (gồm trạng thái hiện tại và trạng thái tiếp theo), agent (chủ thể gây ra hành động, environment (môi trường), action (tác động lên environment) và reward (tác động lên môi trường sẽ nhận được lại)
- 4.2 [**1** Point, 3.2] Following a policy $\pi(s)$ to generate a trajectory of 10 time steps $(s_t,a_t,s_{t+1},r_{t+1})$. Compute the return. Equation of $a_t$?
- 4.3 [**1** Point, 1.2, 3.2] Repeat for 10 days: from $s_0 = \text{HOME}$ take action $a_0 = \text{GET_BUS}$ with cost $r_1 = 6000 \text{VNĐ}$ then following policy $\pi(s)$ to generate $K=10$ trajectories, each with total cost $G_k$. Compute the average cost of taking bus then following $\pi$: $Q^\pi(\text{HOME, GET_BUS})$.
- 4.4 [**1** Point, 1.1, 1.3, 2.1, 3.2] How do we compute an optimal plan (i.e., optimal policy $\pi^*$) of a known MDP $(S,A,T,R,\gamma)$?
- 4.5 [**1** Point, 3.2] Why do we say that the action value function $Q^\pi(s,a)$ gives predictions into very far future?
- 4.6 [**1** Point, 1.2, 3.2] What is the meaning of action value function when we set $\gamma = 1$? $\gamma = 0$?

5. [**7** Points] Unified ML models
$\text{Input } X \xrightarrow[B_{\beta}]{\text{Features}}\text{ Embedding Coordinates }Z \xrightarrow[P_{\theta}]{\text{Predictor}}\text{ Predictions }\hat{Y} \xrightarrow[{\pi^*}]{\text{Policy}}\text{ Action }A$
- 5.1 [**2** Points] List all *taught* algorithms for feature extraction and their main ideas.
MLP: xây dựng mạng lưới neuron networks để lấy các features phức tạp
CNN: tương tự như MLP những có thêm các lớp Convolution và Maxpooling... để lấy được cả những features có tính không gian
RNN: gần giống như CNN, nhưng là cho dữ liệu dạng chuỗi

- 5.2 [**2** Points] List all *taught* algorithms for making predictions and their main ideas.
Logistic Regression: best-fit 1 đường non-linear để dự đoán label của dữ liệu đưa vào
Linear Regression: best-fit 1 đường linear để dự đoán ra 1 output khác từ dữ liệu được nhập vào
Support Vector Machine: trả ra tên nhóm từ dữ liệu được nhập vào
K-means : dự đoán nhóm của dữ liệu được nhập vào
K nearest neighbors : tương tự như K-means
CNN, MLP, RNN
- 5.3 [**2** Points] What are the main *general* differences between linear predictors? And in your opinion why do we need different algorithms?
- 5.4 [**1** Points] For MDPs, what are the predictions $\hat{Y}$ used to make decisions $A$?

6. [**2** Points] RecSys
We build item embeddings ${\bf z}_i \in \mathbb{R}^2$ as in table, and use **softmax regression** to predict ratings 1 to 5. Choose a specific user $X\in \{A,\dots,F\}$, what is the training set for learning $\theta_X$? What are the parameters $\theta_X$ to be learned (with their shapes)?

7. [**6** Points] MDP Planning for playing Chess. Let rewards = 1 for winning, -1 for losing, and 0 for a draw or unfinished game, and no discount.
- 7.1 [**2** Points] What is the range of value of the optimal action-value function $Q^*(s,a)$, and how to derive probability of win/loss from it?
- 7.2 [**2** Points] If we use all the games already played in history to compute $Q^*(s,a)$, explain the method?
- 7.3 [**2** Points] Because there are so many state and action pairs $(s,a)$, we need to use *learning* to approximate and generalize for all $(s,a)$ pairs. If we use MLP to learn $Q^*(s,a)$, what is the dataset and possible network structure?