# LECTURE OF MACHINE LEARNING
## Session :three: : Recommender Systems (Hệ khuyến nghị)
similarity $\to$ linear regression for score predictor
Có hai thực thể chính trong RecSys là:
* Users $\to$ người dùng
* Items $\to$ sản phẩm
Chức năng chính:
* Generalization counts $\to$ đáp ứng nhu cầu khái quát hóa sản phẩm (bán và yêu cầu những sản phẩm bán chạy nhất trên thị trường)
* Personalization counts $\to$ đáp ứng đủ nhu cầu cá nhân hóa sản phẩm, gợi ý những sản phẩm (dù không phổ biến) nhưng nó đáp ứng đủ nhu cầu người dùng.

Hiện tượng Long - Tail Issue:
* Head: chứa những số lượng sản phẩm bán chạy nhất $\to$ hơn 80% doanh thu của cửa hàng từ số tiền bán được 20% số loại sản phẩm.
* Long Tail: chứa niche product + sorta / kinda popular $\to$ less popular $\to$ less items sold, but better customer experience / satisfaction.
### I. Content-based RecSys
* Là mô hình đánh giá đặc tính của items được recommended.
* Yêu cầu việc sắp xếp các _items_ vào từng nhóm hoặc đi tìm các đặc trưng của từng _item_. Tuy nhiên, có những _items_ không có nhóm cụ thể và việc xác định nhóm hoặc đặc trưng của từng _item_ đôi khi là bất khả thi.
#### 1. Model - based CB RecSys
* Là bài toán đi tìm mô hình $\theta_i$ cho mỗi user có thể được coi là một bài toán Regression trong trường hợp ratings là một giá trị liên tục, hoặc Classification nếu ratings là một vài trường hợp cụ thể (like / dislike)
* Dữ liệu training để xây dựng mỗi mô hình $\theta_i$ là các cặp (_item profile, ratings_) tương ứng với các _items_ mà _user_ đó đã _rated_. Việc _điền_ các giá trị còn thiếu trong ma trận Utility chính là việc dự đoán đầu ra cho các _unrated items_ khi áp dụng mô hình $\theta_i$ lên chúng.
#### 2. Model - free CB RecSys
* Là mô hình tính độ consine similarity giữa user-item dựa trên item features
* Trích xuất đặc trưng $x_1, x_2, ..., x_d$ -> vector embedding z
* Sử dụng items như là $\phi_i$ để tính dot product giữa user $u_i$ và đặc trưng $x_k$
* Tính cosine similarity giữa ${\bf z_{\text{user}_i}}$ qua đặc trưng x với ${\bf z_{\text{user}_j}}$ như là like / dislike proabilities.
### II. Collaborative Filtering RecSys
#### 1. Neighborhood - based Collaborative Filtering
* Là mô hình khuyến nghị những món hàng có rating / matching scores cao nhất cho người dùng.
* Ví dụ:
* Các đường nét liền $\to$ thể hiện user đó đã mua hay rate cho item đó.
* Các đường nét đứt $\to$ thể hiện hệ thống yêu cầu item này đến user đó.
<center><img src = https://d1q4qwyh0q55bh.cloudfront.net/images/9RknPOgdJ6DHlp6Sh17npFBbi18Gc7Hq3gFbW5IyuONbsk1QWJeG1AWhQNYYRAza.jpeg?d=desktop-thumbnail></center>
##### a. User - based Collaborative Filtering
* Ý tường: xác định mức độ quan tâm của người dùng tới một sản phẩm dựa trên các users khác gần giống với user này. Việc gần giống nhau giữa các user có thể được xác định thông qua mức độ quan tâm của các user này tới các items khác mà hệ thống đã biết.
* Là mô hình tính độ giống nhau giữa các users (mỗi user được xem là vector embedding ${\bf z_{\text{user}}}$ thể hiện từng cái đặc trưng mua hàng là các items $\Phi = (\phi_1, ..., \phi_n)$.
* Ta sẽ dùng mô hình Linear Predictor để tính độ giống nhau giữa các users thông qua các vector embedding ${\bf z_{\text{user}}}$ của các đặc trưng $\text{item } i \equiv \phi_i$.
* Ví dụ:
* Giả sử các users từ $u_0$ đến $u_6$ và các item từ $i_0$ đến $i_4$ trong đó các số trong ô vuông thể hiện số sao mà mỗi user đã rated cho item với giá trị cao hơn thể hiện mức độ quan tâm cao hơn. Các dấu chấm hỏi là các giá trị mà hệ thống cần phải đi tìm.
* Nhận xét: original utility matrix Y thường có rất nhiều missing ratings vì mỗi user thường chỉ rated một số lượng rất nhỏ các items.
* a. Thay vi điền các giá trị 0 vào ô trống ($\to$ không tốt vì giá trị 0 là tương đương với mức độ quan tâm thấp nhất) hay lấy trung bình cộng của các ô mức thấp nhất (các ô đã rate và chưa rate) và các ô mức cao nhất ($\to$ hạn chế đối với những user dễ tính hoặc khó tính), chúng ta có thể xấp xỉ utility matrix bằng trung bình cộng của các ratings mà users tương ứng đã thực hiện $\implies$ tránh được việc users quá khó tính hay dễ tính (lúc nào cũng có những items mà một user thích hơn so với những items khác).
* b. Lấy original utility matrix tiếp tục trừ mỗi rating đi giá trị trung bình đã tính được bước (a) và thay các giá trị chưa biết (?) bằng 0 $\to$ normalized utility matrix.
* Giá trị trong ô > 0 $\to$ user này thich item đó.
* Giá trị trong ô < 0 $\to$ user này không thích item đó.
* Giá trị trong ô = 0 $\to$ chưa xác định user có thích item đó hay không.
* c. Ta chọn $\phi_k = i_k$ nên rating của 1 user cho item $i_k$ là embedding coordinate $z_k$ của user đó.
$\implies$ ${\bf z_{u1}} = (2.25, 0, 1.25, -0.75, -2.75)^\top$.
Tính độ giống nhau giữa các ${z_{u1}, ..., z_{u_n}}$.
<center><img src = https://i.imgur.com/2kB0rKh.jpg></center>

* Một số hạn chế của User - based CF:
* Thực tế: số lượng users nhiều hơn số lượng items rất nhiều $\to$ user similarity matrix rất lớn với số phần tử phải lưu giữ là hơn 1 nửa bình phương số lượng users.
* Utility Matrix Y thường rất sparse (có nhiều ô trống và chỉ có một vài phần tử khác 0 do user thường lười rating) $\to$ user thay đổi hoặc thêm rating thì trung bình cộng các ratings cũng như vector chuẩn hóa tương ứng với user này thay đổi nhiều $\to$ cần phải tính toán lại User Similarity Matrix $\to$ tốn rất nhiều thời và nhiều bộ nhớ
##### b. Item - based Collaborative Filtering
* Là mô hình tính độ giống nhau giữa các items (mỗi items được xem là vector embedding ${\bf z_{\text{item}}}$ thể hiện mức độ có mặt của từng đặc trưng người dùng (tức là người dùng đã rate $\to$ độ ratings) $\Phi = (\phi_1, \phi_2, ..., \phi_n)$)
* Ta sẽ dùng mô hình Linear Predictor để tính độ giống nhau giữa các items thông qua các vector embedding ${\bf z_{\text{item}}}$ của các đặc trưng $\text{user } i \equiv \phi_i$.
* Ví dụ:
* Chọn $\phi_k = u_k$ nên rating của user $u_k$ cho 1 item sẽ là embedding coordinate $z_k$
* i1 $\to {\bf z_{1i}} = (2, 3, 5, 0)^\top$
* i2 $\to {\bf z_{2i}} = (0, 2, 3, 2)^\top$
* Để tính độ giống nhau giữa các items $\to$ cosine similarity function.
* Ta có thể loại bỏ các hàng ko đủ user rating cho cả 2 item (thay vì sử dụng 0).
<center><img src = https://i.imgur.com/HEqxtJF.png></center>

* Lợi ích:
* số lượng items nhỏ hơn số lượng users, similarity matrix nhỏ thuận lợi cho việc lưu trữ.
* vì số lượng phần tử đã biết trong Utility Matrix là như nhau nhưng số items (hàng) ít hơn số users (cột) => mỗi hàng nhiều phân tử hơn mỗi cột => vì mỗi item được rated bởi nhiều user => giá trị trung bình của mỗi hàng ít bị thay đổi khi có thêm một vài ratings => user similarity matrix có thể được thực hiện ít thường xuyên hơn.
#### 2. Matrix Factorization Collaborative Filtering
##### a. Solved by truncated SVD (Single Value Decomposition)
* Một ma trận (dữ liệu) A bất kỳ được phân tách thành 3 ma trận khác qua phép phân tích / phân rã SVD: $A \xrightarrow[]{\text{SVD}} \text{USV}^\top$ trong đó
* U$ và $V$ là 2 ma trận trực chuẩn (vuông góc với nhau và độ lớn = 1) với các vectors hàng hoặc cột của mỗi ma trận = 1 và vuông góc nhau $\to$ singular vectors.
* $S$ là ma trận đường chéo với các giá trị $\sigma_i$ trên đường chéo thể hiện mức độ quan trọng của từng singular vector: nếu $\sigma_i \approx 0$ ta có thể loại bỏ các hàng/cột thứ i của 2 ma trận $U$ và $V$.
##### b. Solved by Regularized Alternating Least Squares (Tham khảo)
---
## Session :four: : Non-linear Predictors (Dự báo phi tuyến)
Chúng ta có thể phân tách các vùng ngữ nghĩa dữ liệu riêng biệt nằm rải rác trong một không gian tọa độ phi tuyến tính (thường là những dữ liệu thô với các đặc trưng bậc rất thấp) thông qua hai cách chính:
### 1. **==Locally==** linear / nonlinear models
Vì đồ thị và hình dạng phân bố của cụm dữ liệu ban đầu là **non - lỉnear shape** $z = g(x, y)$ có dạng mặt **"cong"** $\to$ phân bố dữ liệu gồm nhiều embedding coordinates ${\bf z} = (z_1, z_2, ..., z_n)$ tương ứng theo từng đặc trưng $\Phi = (\phi_1, \phi_2, ..., \phi_n)$ trong "semantic sapce" đa tạp, xoắn, rồi vào nhau $\to$ khó phân tách dữ liệu trong "sematic space" bằng decision boundary $\to$ khó thực hiện để vẽ và biểu hiện sự phân tách như các cách phân chia cụm dữ liệu bằng decision boundary trong linear models
* Locally linear models: Decision Tree
* chia không gian tọa độ nhúng z thành nhiều khu vực nhỏ sau đó apply từng mô hình linear predictor vào trong từng 'local' region.)
* Locally non-linear models: kNN classification (non - smooth) (do decision boundary của kNN là một non - linear surface $\to$ thể hiện tính non-linear cục bộ)
### 2. **==Globally==** linear predictors $\hat{y} = s(W\phi(z) + b)$
Bằng cách biến không gian phi tuyến thành không gian tuyến tính để phân tách dữ liệu bằng linear decision boundary $\implies$ trích xuất được các đặc trưng tốt hơn $\implies$ vector embedding tốt hơn $\implies$ output $\hat{y}$ tốt hơn. $$X \xrightarrow[]{\Phi} Z \xrightarrow[]{T} Z' \xrightarrow[]{p} Y$$ Z space $\to$ **non-linear** boundary, $Z'$ space $\to$ **linear** boundary.
#### a. Design
Nonlinear predictor in ${\bf z} \xrightarrow[]{\phi}$ linear predictor in ${\bf z'}$
* Non - linear *quadratic* feature $$z=(x,y)\in\mathbb{R}^2\xrightarrow{\text{features }\phi(z)} z'=(x,y,h = x^2+y^2)\in\mathbb{R}^3 \to {\text{linear predictor }} \hat{y} = \mathsf{s}(Wz'+b)$$
* Non - linear *rbf* feature $$z=[x,y]\in\mathbb{R}^2\xrightarrow{\text{features }\phi(z)} z'=[x,y,h = \mathsf{rbf}(x,y;c)]\in\mathbb{R}^3 \to {\text{linear predictor }} \hat{y} = \mathsf{s}(Wz'+b)$$
#### b. Non - linear predictors by transformations $\hat{y} = s(W.\Phi({\bf z}) + b)$
* **==Feature engineering $z' = \phi(z)$ - "hand-crafted":==** tìm các đặc trưng thô từ không gian tọa độ này sang không gian tọa độ khác
* **==MLP (Multi Layer Perceptrons):==** phương pháp này biến đổi cấu trúc dữ liệu bằng cách sử dụng activation function $\gamma$, bộ ma trận trọng số $W$, vector bias ${\bf b}$ nhằm xoay - co giãn, xê dịch, bóp / nắn / cắt dữ liệu $\to$ single neuron / perceptron layer nhằm đưa dữ liệu qua nhiều lớp neuron để trích xuất các đặc trưng đầu vào bậc thấp thành các đặc trưng đầu ra bậc cao $\implies$ tối ưu hóa việc phân tách ngữ nghĩa dữ liệu.
* ==Linear Tranformation ${\bf z'} = W{\bf z} \equiv$ rotate/flip + scale + rotate/flip $\to$ có làm thay đổi số đặc trưng (số trục) ban đầu==
* Đầu tiên: đi kèm với từng vector embedding ${\bf z} = (z_1, z_2, ..., z_n)$ là một hệ trục thể hiện các hướng của tập hơp các đặc trưng $\Phi = (\phi_1, \phi_2, ..., \phi_n)$. Tương tự cho ${\bf z'}$ với hệ trục chuẩn là $\phi'$.
* Sau đó ta dùng thuật toán SVD: $A = W = USV^\top$ (thực hiện tính toán từ phải sang trái) để phân rã weighted matrix thành các phần có chức năng sau:
* $U$ hay $V^\top$ là ma trận trực chuẩn $\to$ hiệu ứng biến đổi ${\bf z'} = A{\bf z}$ là xoay và lật (rotate / flip) các hướng / trục của tập hợp đặc trưng $\Phi = (\phi_1, \phi_2, ..., \phi_n)$ của vector embedding ${\bf z}$ thành các hướng / trục mới thể hiện cho tập hợp các đặc trưng mới $\Phi' = (\phi_1', \phi_2', ..., \phi_n')$ quanh gốc tọa độ O nhưng theo chiều ngược lại. Đồng thời do U ban đầu có là ma trận trực chuẩn nên các trục mới thể hiện hướng của từng đặc trưng $\phi_i'$ chính là hướng của các vector hàng của ma trânj mới $U$ vì phép nhân ma trận trực chuẩn là phép chiếu $z_i' = u_i^\top{\bf z}$
* $S$ là ma trận đường chéo $\to$ hiệu ứng biến đổi ${\bf z'} = A{\bf z}$ là co giãn (scale) từng trục của $\phi_i$ theo tỉ lệ nghịch đảo $\displaystyle \frac{1}{\lambda_i}$ để có hệ trục mới $\phi_i'$, tương đương với việc co giãn từng tọa độ $z_i' = \lambda_i.z_i$ $\to$ bước này có thể làm cho đặc trưng bị biến mất hoặc được sinh ra do quá trình co / giãn các đặc trưng theo từng embedding.
* Sau đó khi tách $W$ ta sẽ dot product lần lượt từ phải sang trái $$W.{\bf z} \xrightarrow[]{\text{SVD}} (USV^\top).{\bf z}\to \overset{\text{xoay}}{\overbrace{A = {\bf z}.V^\top}} \to \overset{\text{co / giãn}}{\overbrace{B = A.S}} \to \overset{\text{xoay}}{\overbrace{C = B.U}}$$ Ở đây, ta thấy **phép SVD** sẽ làm **xoay - co/giãn - xoay** (gồm **2 phép xoay** và **1 phép co / giãn**), tức là vector embedding coordinate ${\bf z}$ trong "semantic space" ban đầu $\Phi({\bf z})$ sẽ bị xoay bởi $V^\top$ rồi co giãn các tọa độ mới bị xoay thông qua ma trận đường chéo $S$ và cuối cùng các tọa lúc này sẽ bị xoay bởi $U$ để cho ra vector embedding ${z'}$ mới tương ứng với tập hợp đặc trưng mới $\Phi'$ (vẫn là các đặc trưng cũ trong "semantic space" nhưng từng đặc trưng này sẽ ứng với từng $z'$ mới sau khi dùng SVD).
* ==Translation ${\bf z''} = W{\bf z} + b = {\bf z'} + b \equiv$ tịnh tiến vector embedding ${\bf z'}$ $\to$ ko làm thay đổi số đặc trưng (số trục) ban đầu==
* Sau bước Linear Transformation $W{\bf z}$, chúng ta có vector embedding coordinates mới ${\bf z'} = (z_1', z_2', ..., z_n') = W.{\bf z}$ tương ứng với hệ trục / các đặc trưng mới $\Phi' = (\phi_1', \phi_2', ..., \phi_n')$ trong "sematic space" ban đầu nhưng có một điều khó khăn là ${\bf z'}$ vẫn còn ở dịch chuyển cố định xung quanh gốc tọa độ $O$ trong "semantic space", muốn khắc phục ta cần phải tịnh tiến ${\bf z'} = W.{\bf z}$ lên (nếu $b > 0$) xuống (nếu $b < 0$) để xê dịch, dịch chuyển cụm dữ liệu này thoát khỏi gốc tọa độ $O$ mà không làm thay đổi cấu trúc, hình dạng, hướng/ trục của từng $\phi_i'$ trong không gian tọa mới.
* ==Nonlinear shapping ${\bf z'''} = \tau({\bf z''}) = \gamma({\bf z''}) = \gamma({\bf z'} + b)= \gamma(W{\bf z} + b) \to$ quá trình này làm thay đối số đặc trưng (số trục) vốn có ban đầu trong semantic space==
* Sau khi ta đã thực hiện các bước trên lúc này ta đã có ${\bf z''} = W.{\bf z} + b$ trong không gian đặc trưng $\Phi''({\bf z''})$ nhưng vẫn còn mang tính đa tạp (nhiều tọa độ thuộc nhiều loại khác nhau), rối và xoắn vào nhau nên chưa thể phân cắt dữ liệu bằng **linear decision boundary** hay nói cách khác ${\bf z''}$ vẫn còn tính non - linear.
* Để khắc phục điều trên, ta vẫn phải cho vector embedding ${\bf z'}$ đi qua một hàm **non - linear transformation function $\gamma()$** như sau:
* Sigmoid: $\sigma(x) = \displaystyle \frac{1}{1+e^{-x}}\implies$ nắn đầu ra thuộc khoảng [0, 1]
* tanh: $\text{tanh(x)} = \displaystyle \frac{e^{2x} - 1}{e^{2x} + 1} \implies$ nắn đầu ra thuộc khoảng [-1, 1]
* Relu: max(0, x) $\to$ nắn đầu ra thuộc khoảng (0, $+\infty$) $\implies$ thường được sử dụng để cắt không gian Input
* Hàm **non - linear transformation function $\gamma()$** có chức năng bóp/nắn/cắt embedding coordinate ${\bf z''} = W{\bf z} + b$ (vì chúng ta đang muốn cắt đơn giản embedding coordinates để phân tách các concepts trong embedding space Z) nhằm gỡ rối ${\bf z''}$, tức là thực hiện phép "element - wised" để thay đổi kích thước, giá trị của từng phần tử trong ma trận ${\bf z''}$ $\to$ thay đổi bản chất, kích thước ma trận ${\bf z''}$
* **++Bóp (Squashing) và Nắn (Stretching)++**: Hàm $\gamma$ có thể thực hiện các phép biến đổi để bóp / nắn giãn phạm vi của dữ liệu input. Ví dụ: hàm sigmoid có thể được sử dụng để bóp các giá trị điểm dữ liệu đầu vào thành con số xác suất (0, 1), trong khi hàm tanh có thể bóp về khoảng (-1, 1).
* **++Cắt (Clipping)++**: Một số hàm $\gamma$ có thể cắt bớt các giá trị của dữ liệu nằm ngoài một phạm vi xác định. Ví dụ: giá trị của hàm ReLU trả ra chỉ là những con số dương, vì vậy nó có tác dụng cắt bớt các giá trị âm thành 0 và giữ nguyên giá trị dương $\to$ giảm độ lớn của các giá trị âm và tạo ra một biến đổi không tuyến tính trên dữ liệu.
<center><img src = https://i.imgur.com/rL2JioS.png></center>
* ${\bf z'''} = \tau({\bf z''}) = \gamma({\bf z''}) = \gamma({\bf z'} + b)= \gamma(W{\bf z} + b)$ còn gọi là một neural / perceptron layer $\to$ là không gian tọa độ của các đặc trưng bậc cao được biểu diễn bởi các hàng của bộ trọng số W.
* ==Multilayer Perceptron (MLP): repeat for new neural/perceptron layers $(W_L ... \gamma(W_2(\gamma(W_1{\bf z} + b_1)+ b_2) + ...+ b_L)$==
* Hay còn gọi là **Feedfordward Neural Network (FFNN)** và **Fully Connected / Dense** Layers.
* **Feedfordward Neural Network (FFNN)** Layers: do các dữ liệu đi theo tuần tự từ embedding space đầu tiên sang embedding space cuối cùng mà không có sự quay lại (tức là không có vòng lặp)
* **Fully Connected** Layers hay gọi là "Dense" Layers: tất cả các node giữa các layers đều được kết nối từng node với nhau thông qua bộ $\theta = (W, b)$.
* "RELU" layers là "Layers" of weights hay còn gọi là tập các node layers.
* Nếu layer sau có nhiều nodes hơn layer trước (tức là quá trình biến đổi không gian đặc trưng được mở rộng) $\to$ phép expansion các đặc trưng, giúp tạo ra các đặc trưng mới, phức tạp hơn từ các đặc trưng ban đầu $\to$ giúp mạng neuron học được các biểu diễn phức tạp và trừu tượng hóa của dữ liệu đầu vào.
* Nếu layer sau có ít nodes hơn layers trước (tức là quá trình biến đổi không gian đặc trưng được thu hẹp) $\to$ phép thu hẹp / chiếu (compression / projection), giúp chuyển đổi các đặc trưng ban đầu thành một không gian đặc trưng ít chiều hơn $\to$ giảm sự phức tạp dữ liệu đầu vào, giảm thiểu sự overfitting và tăng cường hiệu suất mạng neuron.
* ==Linear Predictor = Last layers $\hat{y} = s(W_L ... \gamma(W_2(\gamma(W_1{\bf z} + b_1)+ b_2) + ...+ b_L) = s(W_L{\bf z''} + b_L)$==
* Dùng các hàm nắn s() đã trình bày trong chương 2 phần linear predictors.
* **==Kernel machines:==** phương pháp này không cần phải biến đổi cấu trúc dữ liệu trong không gian mà chỉ cần tính độ giống nhau của các đặc trưng thông qua hàm đặc trưng $\phi(X)$.