---
# System prepended metadata

title: Lecture Notes ML4AI 2021

---

# Lecture Notes ML4AI 2021

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}$=$\frac{X_{1}+X{2}+\cdot \cdot \cdot +X_{N}}{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**:
- [**1** Point] What are the main differences between representations by PCA and by sparse coding? **Solution**:
- [**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**:
(0,1,0)
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**:
![](https://i.imgur.com/PseEFdZ.png)
- $z_{A}$=[]
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
    - sofmax regression with 3 classes? **Solution**:[W1,W2,W3]
- [**1** Point] What is function $\mathsf{s}(\cdot)$ for 
    - 1 dimentional linear regression? **Solution**: sigmoid
    - SVM binary classification? **Solution**: hinge
- [**1** Point] Why logistic regression (for binary classification) has only 1 probability output while there are 2 classes? **Solution**: vì probability còn lại thì lấy 1-probability kia
4. [**2** Points] Evaluation procedure 
- [**1** Point] Explain the main use of the train--dev (validation)--test sets. **Solution**:train là tập dùng để xây dựng nên model, validation là tập để chọn model trong nhiều model được tạo ra, còn test là tập thực tế
- [**1** Point] What are the main similarity and differences between linear SVM and logistic regression? **Solution**:
- logistic regression làm cho hàm có dạng bậc thang, khó trượt nên khó ra kết quả tối ưu
- còn SMV là cho performance trơn nên dễ ra kết quả đúng nhất
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. 
![](https://i.imgur.com/PseEFdZ.png)
- [**1** Point] How many classes do we need? **Solution**:5 classes là 1,2,3,4,5 sao
- [**1** Point] What is the size of $W$ if we use softmax regression $\hat{y}=s(Wz+b)$ for to classify ratings? **Solution**:
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**:
- $\hat{y}$=s(${W}'(\gamma(Wz+b))+{b}'$)
- [**1** Point] What are the parameters of the fully-connected layer in your equation? **Solution**:weights và bias

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**: dễ thực hiệ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**:

## Tóm tắt $\S$ 1
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.
- Đưa input X, chỉnh trọng số W => output
-  Hàm tuyến tính: là 1 đường hay mặt phẳng thẳng đi qua các điểm với khoảng cách lệch nhỏ nhất.

  **$\bigtriangleup$ Cách tìm hàm tối ưu:**
- Từ input X đưa vào không gian Z và đưa ra dự đoán và có thể điều chỉnh dựa trên các mẫu.
**$\bigtriangleup$Các loại dữ liệu:**
-- Bằng số
-- Nhóm
 
    **$\bigtriangleup$ Phân loại dữ liệu:**
- Các cách phân loại:
-- Regression 
-- Classification

* Phân loại theo ý bản thân người lập trình (classification) và ý của máy tính (clustering)
$\hat{y}$ = $s \cdot (wz +b)$   (với z là đặc trưng, w là trọng só)
- Đánh giá hàm bằng so sánh sai số ($y$,$\hat{y}$).
- Để đánh giá mức độ giống nhau: sử dụng tích chấm, cosine similarity,K-NN...
## Tóm tắt $\S$ 2
## Tóm tắt $\S$ 3
#### $\hat{y}$ = s(WZ+b)
#### X$\overset{B1,B2...}{\longrightarrow}$ Z
- Non-linear predictor
- Decision boundaries: các niềm tin bằng nhau
- Decision boundaries: linear and non-seperable
- Có lỗi nonseperable khi các dữ liệu noisy
- Nonlinearseperable $\rightarrow$ transformation$\rightarrow$linear seperable
#### $Transformation$: tách entangling thành không gian có thể linearly seperable
- $Z$ $\overset{L}{\rightarrow}$${Z}'=A.Z$ với $A$ là một ma trận, không gian là phẳng
#### Biến đổi phi tuyến nhiều lớp MLP: xoay, co giãn, lật để làm ${Z}'$= A.Z rồi bóp méo bằng hàm $\Theta$
- Mỗi lớp bóp méo gọi là một neuron
- Só trọng số cần học=Innode.Outnode+Outnode (bias) rồi cộng qua nhiều lớp
- 3 hàm activation chính là sigmoid,softmax,relu
- Cách chạy của hàm:
B$_{1}$: random weight
B$_{2}$: $\hat y$ = wx + b
B$_{3}$: tính loss ($\hat y$, $y$)
B$_{4}$: chọn lại weight (optimizer)
rồi quay về lại bước ở B$_{2}$ (Từng bước trong epochs)
>****Số node trong mỗi lớp nên là $2^{n}$ để tối ưu hóa hàm****
#### Handcrafted:
#### Kernel trick : chuyển qua không gian mới rồi dot product của 2 z
#### Local linear: Chia nhỏ rồi chia linear



## Tóm tắt $\S$ 4: Recommendation Systems(RecSys)
- Vấn đề $long-tailed$: cần giải quyết độ trải nghiệm, hài lòng chứ không chỉ độ phổ biến của sản phẩm.
- Bài toán recommend:
-- Có 2 nhóm: người dùng và sản phẩm
-- Cần dự báo cho người dùng và sản phẩm là độ phù hợp, nếu ở mức độ cao thì khuyến khích sử dụng.
- Cách giải quyết bài toán: 2 cách cơ bản:

-- User-based filtering: thích nhiều sản phẩm giống nhau$\Rightarrow$cùng sở thích$\Rightarrow$thích cùng sản phẩm.
-- Item-based filtering: nhiều người thích$\Rightarrow$người bất kì nào đó cũng thích.
- Một số loại input: 
-- Hành vi: thông tin giao dịch, khối lượng mua,...
-- Thông tin cá nhân: nơi ở, tuổi tác, ...
-- Thông tin khách quan: thời gian, địa điểm, mạng xã hội,...
-- Hệ thống mã : có thể chỉ sử dụng data (thông tin chung) (không sử dụng model) hoặc xây dựng model.
**Collaborative Fitering (CF)**
- ***Key idea : similarity***: sử dụng công thức như Dot Product, Cosine Similarity, ...
-  Cần trích xuất vector Z đặc trưng của từng cái để so sánh và tính độ giống nhau.
-  Item - based CF:
--  Chuyển đánh giá của người dùng thành 1 ma trận utilites (gồm user, item và rating)
--  Mỗi người dùng là một đặc trưng
--  Dùng cosine similarity để tính
-- Công thức tính: rating nhân độ giống nhau chia tổng độ giống nhau
- User - based CF:
-- Cũng là bài toán Item - based nhưng lượng user lớn hơn item rất nhiều
-- Chuyển vị rồi tính như item based
>**Lưu ý**: cần trừ các giá trị sẵn có cho giá trị trung bình của cột và cho những chỗ cần tính là zero thì kết quả sẽ chính xác hơn.
># Tóm tắt $\S$ 5
Metrics: Chuẩn đánh giá là thước đo xem hàm $f$ có tốt hay không
Losses: tối ưu hàm
commom metrics and loss:
MSE
RMSE
MAE: dữ liệu bị nhiễu
MAPE
accuracy: classification,balanced dataset
F1: classification,imbalanced dataset
$F_{\beta}$ score- (1+$\beta^{2}$)$\frac{Precision \cdot Recall}{\beta^{2}Precision+Recall}$$\Rightarrow F1$
Precision: how ***useful*** the search results are
Recall: how ***sensitive*** the results are
# Tóm tăt $\S$ 7
$\Theta*$=$argmin_{\Theta}$$J(\Theta,X,y)$
Đạo hàm cho biết vận tốc tăng của hàm số
Hàm loss như 'trần nhà', ta cần tìm hàm loss để 'trần nhà' thấp nhất
Vector Gradient:
$\nabla_\theta J(\theta;X,{\bf y}) = \Big(\frac{\partial}{\partial\theta_1}J_\theta, \dots, \frac{\partial}{\partial\theta_k}J_\theta, \dots, \frac{\partial}{\partial\theta_n}J_\theta\Big)$ với $\text{ } \frac{\partial}{\partial\theta_k}J_\theta = \lim_{\Delta \theta_k\to 0}\frac{J(\theta_1,\dots,\theta_k,\dots,\theta_n) - J(\theta_1,\dots,\theta_k + \Delta \theta_k,\dots,\theta_n)}{\Delta \theta_k}$
Đi ngược chiều Gradient tăng nhanh nhất
VD: Đối MLP ta có Backwardpropagation để update từng layer
Classification có hàm loss dạng bậc tahng nên khó tìm hàm tồi ưu nên cần đổi về hàm loss smooth để tìm hàm tối ưu
Các khó khăn: local minimum,thung lũng hẹp, bước đi quá lớn hoặc quá nhỏ, có tác động của momentum Gradient
>At the minimumpoint: $\nabla_\theta J(\theta^*;X,{\bf y}) =0$ (đạo hàm),but not necessarily vice versa
>
Giải pháp: $Batch\Rightarrow minibatch \Rightarrow SGD$
Có tác động của momentum Gradient
Tìm parameter
Early stopping để khắc phục overfit
Tắt một số nodes trong MLP

# Tóm tắt $\S8$ : CNN

**Giới thiệu**

- Trong xử lý ảnh, phương pháp CNN giúp ta giữ lại các đặc trưng về không gian của ảnh.
- CNN dựa trên inner product để tính similarity giữa kernel - dùng để trượt(sliding), và các vùng ảnh , quá trình này gọi là matching. Matching và sliding làm nên Convolution. 
- Cách tính inner product giống với dot product nhưng là tính trong không gian hai chiều.
- Filters trong CNN là quá trình từ input cho ra feature map bằng cách tính inner product giữa kernel và ảnh đồng thời trượt kernel đó trên toàn ảnh

**CNN operations**

- Padding: bằng cách bọc thêm vào viền của ảnh ban đầu các lớp chứa con số 0. Padding giúp giữa nguyên hoặc tăng kích thước đầu vào trong quá trình filters điều này giúp tránh thất thoát thông tin trên góc cạnh. Để giữ nguyên kích thước đầu vào ta có thể tính số lớp padding bằng cách lấy kích thước kernel trừ 1 rồi chia 2.
- Stride: chỉ số sải chập quyết định cách mà kernel di chuyển cả ngang lẫn dọc điều này sẽ thu nhỏ kích thước dữ liệu ban đầu
- Pooling: phép gộp giúp giảm 2 lần kích thước input, giúp mô hình vững chác trước các sai lệch nhỏ, pooling gồm AVG pooling (lấy trung bình các điểm dữ liệu -> smooth feaure) và Max pooling (lấy điểm dữ liệu có giá trị lớn nhất -> sharp feature).
    - Phép gộp giảm chiều dữ liệu xuống hai lần như với stride bằng hai nhưng khác là ta không cần phải tính toán các tham số.
- Công thức tổng quát tính output feature map:
    - $n_\text{out}=[\frac{n_\text{in}+2p-k}{s}]+1$
        - k là kích thước kernel
        - p là số lớp padding
        - s là số bước sải chập 

- Cách tính số trọng số cần tối ưu: lấy kích thước của kernel cộng với số feature map.
    - Có thể thấy CNN cần ít trọng số hơn fully Connect.
- DCNN là toàn bộ quá trình từ input là bức ảnh ta trượt kernel chứa các đặc trưng rời rạc qua nhiều lớp Convolution-MaxPooling rồi tới fully connected cho ra output

# Tóm tắt $\S$ 9
**Giới thiệu**
- Giúp ta dự báo theo những chuỗi hành động thay đổi theo thời gian, cho ta những dự báo chuẩn xác
VD: Dự đoán giá vàng, dự đoán hành động, lời nói tiếp theo,...
- CNN: để trích xuất những đặc trưng rời rác trong không gian
- PCA: trích xuất những thành phần chính
- Trích xuất xong, đặc trưng nằm trong vùng khái niệm
- Input: Hình ảnh,âm thanh,giá, nhu cầu mua sắm... chuỗi dữ liệu mà các dữ liệu liên quan với nhau theo thời gian 
- Xử lí yêu cầu di chuyển trong không gian khái niệm,
- Di chuyển trong không gian tham số z $\to {z}'$ , ta làm băng cách cộng z thêm những $\bigtriangleup_{Z}$
- Di chuyển trong không gian khái niệm $h \to {h}'$, ta làm như sau $${\bf h} \to {\bf h'} = \sigma\Big(U{\bf h} + W {\bf x} + {\bf b}\Big)$$
hay $${\bf h}_{t-1} \to {\bf h}_{t} = \sigma\Big(U{\bf h}_{t-1} + W {\bf x}_t + {\bf b}\Big)$$
- Các tham số $U,W$ giống nhau, chỉ khác nhau ở inputs (weights sharing) như CNN
- Khi gặp lỗi, ta truyền lỗi vè bằng back propagation để update U,V, kết hợp với việc ta phải trải không gian khái niệm ra thời gian, nên ta có Backpropagation through time
- Ta lan truyền ngược,các thông tin ( $\bigtriangleup_{Z}$) có thể bị mai một ( shorttermmemort )

# Tóm tắt $\S$ 10

- Học không cần ví dụ y mà chỉ có đầu vào x
- Tự học được nhiều thứ đưa ra khái niệm 
- Đưa ra những đặc trưng chính và giảm chiều
- 'Unsupervised classification/ segmentation(khoanh vùng những khu có ý nghĩa giống nhau)'$\to$ clustering
- Outputs y không được gắn lables
- Ứng dụng: customers classification
- Regression: mỗi class có 1 W, dot product ra Z qua softmax ra probability rồi argmax ra output y
-  Centroid: trung bình những cái gần nó nhất
-  K-means: dùng khoảng cách Euclid để xác định centroid (argmin)
    - **B1**: Chọn K điểm bất kì làm centroid ban đầu
    - **B2**:gán mỗi input vào cluster có centoid gần nó nhất
    - **B3**: Nếu việc gán dữ liệu vào cluster không thay đổi so với vòng lặp trước thì nó dừng
    - **B4**:cập nhật centroid cho từng cluster( trung bình cộng các dữ liệu trong centroid)
    - **B5**: quay lại **B2**
    ![](https://i.imgur.com/TA9K1g5.png)
    ![](https://i.imgur.com/Z9e8bEu.png)


    ![](https://i.imgur.com/ubGwtB6.gif)

    - Đầu ra tốt hay không phụ thuộc các centroid chọn ban đầu 
    - Tiêu chí đánh giá:
        - inter cluster seperability(khoảng cách cluster phải rõ ràng)
        - intra cluster similarity(các data point phải 'chặt' với nhau)$\to$ tối ưu bằng $J = \frac1{N}\sum_{t=1}^N d^2({\bf z}^t, {\bf m}_k^t)$
        - Chọn số cluster: elbow method hay silhoutte method
            - silhoutte method: tính $SA_i = \frac{b_i - a_i}{\max(a_i, b_i)}$với $a_{i}$  average intra-cluster distance & $b_{i}$ average distance of nearest-cluster
                - =1$\to$ xa cluster khác(tốt)
                - =0$\to$ gần boudaries (khá)
                - =-1$\to$ sai cluster (sai)
1) làm thế nào để dùng clustering giảm chiều dữ liệu?
2) Ngoài tính khoảng cách có thể dùng similarity với centroid để gom cụm được không?
- Decision boundaries là đường trung trực của các  centroid nên Kmeans là linear model

# Tóm tắt $\S$ 11
 ***MDP Planning : Dự báo chuỗi hành động***
 Gọi O là những thứ ngoài môi trường, qua agent tạo ra Z, biểu diễn trong đầu là R
 Ta có được Z là tập con của O
 Plan là chuỗi các hành động mang đến kết quả với hiệu quả cao nhất
 Cần Policy để hướng dẫn hành động
 ![](https://i.imgur.com/vYTxmbT.png)
 ***Easiest Formulation: Assumptions***
 $(S,A,T,R,\gamma) \to  \text{policy } \pi(s) \text{ and value } q^\pi(s,a)\to ***optimumplan***$
 - what to do at each & every situation $\forall s_t\in S$ (i.e., MDP states): $a_t\leftarrow$ policy $\pi(s_t)$
 - how good each action is in the future (sum of rewards sense): action value $q^\pi(s,a)$
 Observation $o_{i} \to \text{representsation } z_{i}=\text{external environment state } s_{i}$
 Agent $a_{i}$ sẽ thay đổi $s_{i}\to s_{i+1}$ và cho ra reward/penalty $r_{i+1}$
 $\to MDP(S,A,T,R,\gamma)$ với $\gamma$ giống như lãi suất hay lạm phát
 $G^\pi (s) = \sum_{t=1}^T \gamma^{t-1} r_t$
$q^\pi(s,a) = \frac1{K} \sum_{k=1}^K \Big(r_1 + \gamma G^\pi_k(s') \Big)$
 $\pi^* = \arg\max_\pi q^\pi(s,a), ~ \forall s\in S$
 Ta thực hiện theo hành động có reward lớn nhất
 ***Bellman***
 $\boxed{q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a)\max_{a'} q^*(s',a')}$
 Unknown MDP (missing T orR or both) $\to$ Learn to plan $\to$ Reinforce Learning
 

 









>---
tags: COTAI AI4HighSchool
slideOptions:
  transition: slide
  width: 1920
  height: 1080
  margin: 0.1
  minScale: 0.2
  maxScale: 1.5
  
---

# ML4AI Session 12 Final Exam (for Students)

<br>

![](https://i.imgur.com/eDOwrsO.png)

<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?
    - T: input là những bức hình, trích xuất ra đặc trưng là những thành phần chính rồi đưa ra dự đoán
    - F: là những thành phần chính của bức hình

- 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)
- 1.3 [**2** Point, 3.1] to build a customer segmentation model using k-means?
- 1.4 [**2** Point, 3.1] to build a sentiment analysis model (good, bad, neutral comments) using RNN+Softmax Classifier?

2. [**6** Points] Convolutional filters (or kernels)
- 2.1 [**1** Point, 1.1, 3.2] How do we extend them from dot product?
    - Ta tách từ ma trận lớn ra thành những ma trận nhỏ bao gồm những đặc trưng chính, khi nhân lại sẽ ra được ma trận ban đầu
- 2.2 [**1** Point, 1.1, 3.2, 3.4] Why do we call their outputs "feature maps"?
- 2.3 [**1** Point, 3.2] Explain padding: how to do & main purpose
    - ta bọc viền ngoài của ma trận bằng những con số 0
    - mục đích: tránh thất thoát dữ liệu
- 2.4 [**1** Point, 3.2] Explain pooling: how to do & main purpose
    - phép gộp giúp giảm 2 lần kích thước input, giúp mô hình vững chác trước các sai lệch nhỏ, pooling gồm AVG pooling (lấy trung bình các điểm dữ liệu -> smooth feaure) và Max pooling (lấy điểm dữ liệu có giá trị lớn nhất -> sharp feature).
    
- 2.5 [**1** Point, 3.2] Explain stride: how to do & main purpose
    - chỉ số sải chập quyết định cách mà kernel di chuyển cả ngang lẫn dọc điều này sẽ thu nhỏ kích thước dữ liệu ban đầu
- 2.6 [**1** Point, 3.2, 3.4] Explain their **effective** receptive field: why do they produce highly absstract features?

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à những dữ liệu thường xuyên biến động theo thời gian. VD: giá vàng, giọng nó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)$
    - $h_{t}$: là dự báo của hành động trong thời điểm t
    - $h_{t-1}$: là dự báo của hành động trong thời điểm t-1
    - $\gamma$: là hàm nắn đầu ra
    - A,T: là những bộ trọng số luôn giữ nguyên trong suốt quá trình dự báo
- 3.3 [**2** Point, 1.3, 2.1, 3.2] WWhat 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à những sai lầm ở thời điểm t sẽ truyền ngược lại dằng trước để update tham số lên để ra được 1 bộ trọng số mới
- 3.4 [**1** Point, 1.3, 3.2] Explain vanishing gradient problem for simple RNNs.
    - khi lan truyền ngược thì dữ liệu sẽ bị thất thoát nên đến 1 lúc nào đó sẽ không có tín hiệu dùng để uodate bộ trọng số
- 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.
    - dữ liệu sẽ qua 1 hàm tách các chữ ra rồi lọc đi lấy những từ khóa,từ những từ khóa đó sẽ chuyển về dạng vector rồi qua áp vô 1 chuẩn có sẵn để cho biết đánh giá
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).
    - S: là trạng thái của agent vào thời điểm t
    - A: là hành động của agent
    - T: là hướng dẫn agent thực hiện hành động
    - R: là phần thưởng hoặc phạt đối với hành động A
    - $\gamma$ : giống như lãi suất hay lạm phát
- 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)$?
    - Bellman: $q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a)\max_{a'} q^*(s',a')$
- 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.
    - PCA,CNN:giúp ta giữ lại các đặc trưng về không gian của ảnh,dựa trên inner product để tính similarity giữa kernel - dùng để trượt(sliding), và các vùng ảnh , quá trình này gọi là matching. Matching và sliding làm nên Convolution. 
    - DCNN:là toàn bộ quá trình từ input là bức ảnh ta trượt kernel chứa các đặc trưng rời rạc qua nhiều lớp Convolution-MaxPooling rồi tới fully connected cho ra output
- 5.2 [**2** Points] List all *taught* algorithms for making predictions and their main ideas.
    - MLP
    - knn
- 5.3 [**2** Points] What are the main *general* differences between linear predictors? And in your opinion why do we need different algorithms?
    - để phù hợp cho các loại dữ liệu khác nhau
    - tối ưu hóa output với từng loại dữ liệu
- 5.4 [**1** Points] For MDPs, what are the predictions $\hat{Y}$ used to make decisions $A$?

6. [**2** Points] RecSys
![](https://i.imgur.com/PseEFdZ.png)
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?