# Machine Learning

### 1. Phân nhóm dựa trên phương thức học
**Supervised Learning (Học có giám sát)**
* Classification (Phân loại)
* Regression (Hồi quy)

**Unsupervised Learning (Học không giám sát)**
* Clustering (phân nhóm)
* Association

**Semi-Supervised Learning (Học bán giám sát)**
**Reinforcement Learning (Học Củng Cố)**
### 2. Phân nhóm dựa trên chức năng
* Regression Algorithms
* Classification Algorithms
* Instance-based Algorithms
* Regularization Algorithms
* Bayesian Algorithms
* Clustering Algorithms
* Artificial Neural Network Algorithms
* Dimensionality Reduction Algorithms
* Ensemble Algorithms

## Linear Regression
#### 1.
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y \approx f(\mathbf{x}) = \hat{y}$
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~f(\mathbf{x}) =w_1 x_1 + w_2 x_2 + w_3 x_3 + w_0$
* $w1,w2,w3,w0$ là các hằng số, w0 còn được gọi là bias. Mối quan hệ $y≈f(x)$ bên trên là một mối quan hệ tuyến tính (linear). Bài toán đi tìm các hệ số tối ưu ${w1,w2,w3,w0}$ chính vì vậy được gọi là bài toán Linear Regression.
* $y$ là giá trị thực của *outcome* (dựa trên số liệu thống kê chúng ta có trong tập training data), trong khi $\hat{y}$ là giá trị mà mô hình Linear Regression dự đoán được.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y \approx \mathbf{\bar{x}}\mathbf{w} = \hat{y}$
* $\mathbf{w} = [w_0, w_1, w_2, w_3]^T$ là vector (cột) hệ số cần phải tối ưu
* $\mathbf{\bar{x}} = [1, x_1, x_2, x_3]$ là vector (hàng) dữ liệu đầu vào mở rộng (x bar)
#### 2.
Chúng ta mong muốn rằng sự sai khác $e$ giữa giá trị thực $y$ và giá trị dự đoán $\hat{y}$ là nhỏ nhất. Nói cách khác, chúng ta muốn giá trị sau đây càng nhỏ càng tốt:
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\frac{1}{2}e^2 = \frac{1}{2}(y - \hat{y})^2 = \frac{1}{2}(y - \mathbf{\bar{x}}\mathbf{w})^2$
trong đó hệ số $\frac{1}{2}$ là để thuận tiện cho việc tính toán (khi tính đạo hàm thì số $\frac{1}{2}$ sẽ bị triệt tiêu). Chúng ta cần $e^2$ vì $e=y−\hat{y}$ có thể là một số âm, việc nói $e$ nhỏ nhất sẽ không đúng vì khi $e=−∞$ là rất nhỏ nhưng sự sai lệch là rất lớn.
Hàm bình phương có đạo hàm tại mọi nơi, trong khi hàm trị tuyệt đối thì không (đạo hàm không xác định tại 0)
#### 3.
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\mathcal{L}(\mathbf{w}) = \frac{1}{2}\sum_{i=1}^N (y_i - \mathbf{\bar{x}_i}\mathbf{w})^2$
Hàm số $L(w)$ được gọi là hàm mất mát (loss function) của bài toán Linear Regression. Chúng ta luôn mong muốn rằng sự sai số là nhỏ nhất, điều đó đồng nghĩa với việc tìm vector hệ số $w$ sao cho giá trị của hàm mất mát này càng nhỏ càng tốt. Giá trị của $w$ làm cho hàm mất mát đạt giá trị nhỏ nhất được gọi là điểm tối ưu (optimal point), ký hiệu:
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\mathbf{w}^* = \arg\min_{\mathbf{w}} \mathcal{L}(\mathbf{w})$

Đặt $\mathbf{y} = [y_1; y_2; \dots; y_N]$ là một vector cột chứa tất cả các output của training data; $\mathbf{\bar{X}} = [\mathbf{\bar{x}}_1; \mathbf{\bar{x}}_2; \dots; \mathbf{\bar{x}}_N ]$ là ma trận dữ liệu đầu vào (mở rộng) mà mỗi hàng của nó là một điểm dữ liệu.
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\mathcal{L}(\mathbf{w}) = \frac{1}{2}\sum_{i=1}^N (y_i - \mathbf{\bar{x}_i}\mathbf{w})^2 = \frac{1}{2} \|\mathbf{y} - \mathbf{\bar{X}}\mathbf{w} \|_2^2$
với $\| \mathbf{z} \|_2$ là Euclidean norm (chuẩn Euclid, hay khoảng cách Euclid), nói cách khác $\| \mathbf{z} \|_2^2$ là tổng của bình phương mỗi phần tử của vector $z$

#### 4.
**Cách phổ biến nhất để tìm nghiệm cho một bài toán tối ưu là giải phương trình đạo hàm (gradient) bằng 0**
Đạo hàm theo $w$ của hàm mất mát là:
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\frac{\partial{\mathcal{L}(\mathbf{w})}}{\partial{\mathbf{w}}}
= \mathbf{\bar{X}}^T(\mathbf{\bar{X}}\mathbf{w} - \mathbf{y})$
Phương trình đạo hàm bằng 0 tương đương với:
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\mathbf{\bar{X}}^T\mathbf{\bar{X}}\mathbf{w} = \mathbf{\bar{X}}^T\mathbf{y} \triangleq \mathbf{b}$
(nghĩa là đặt $\mathbf{\bar{X}}^T\mathbf{y}$ bằng b)
* Nếu ma trận vuông $\mathbf{A} \triangleq \mathbf{\bar{X}}^T\mathbf{\bar{X}}$ khả nghịch (non-singular hay invertible) thì phương trình có nghiệm duy nhất: $\mathbf{w} = \mathbf{A}^{-1}\mathbf{b}$
* Nếu ma trận A không khả nghịch (định thức bằng 0) vô nghiệm or vô số nghiệm. Giả nghịch đảo (pseudo inverse) $\mathbf{A}^{\dagger}$ (A dagger):

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\mathbf{w} = \mathbf{A}^{\dagger}\mathbf{b} = (\mathbf{\bar{X}}^T\mathbf{\bar{X}})^{\dagger} \mathbf{\bar{X}}^T\mathbf{y}$
#### 5.
(cân nặng) = w_1*(chiều cao) + w_0

# height (cm)
X = np.array([[147, 150, 153, 158, 163, 165, 168, 170, 173, 175, 178, 180, 183]]).T
# weight (kg)
y = np.array([[ 49, 50, 51,  54, 58, 59, 60, 62, 63, 64, 66, 67, 68]]).T

# Building Xbar 
one = np.ones((X.shape[0], 1))
Xbar = np.concatenate((one, X), axis = 1)

# Calculating weights of the fitting line 
A = np.dot(Xbar.T, Xbar)
b = np.dot(Xbar.T, y)
w = np.dot(np.linalg.pinv(A), b) #(pseudo inverse)

`w = [[-33.73541021]
[ 0.55920496]]`
#### 6.
Hạn chế đầu tiên của Linear Regression là nó rất nhạy cảm với nhiễu (sensitive to noise). Vì vậy, trước khi thực hiện Linear Regression, các nhiễu (outlier) cần phải được loại bỏ. Bước này được gọi là tiền xử lý (pre-processing).

Hạn chế thứ hai của Linear Regression là nó không biễu diễn được các mô hình phức tạp.
## K-means Clustering
Giả sử có $N$ điểm dữ liệu là $\mathbf{X} = [\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_N] \in \mathbb{R}^{d \times N}$ và $K<N$ là số cluster chúng ta muốn phân chia. Chúng ta cần tìm các center $\mathbf{m}_1, \mathbf{m}_2, \dots, \mathbf{m}_K \in \mathbb{R}^{d \times 1}$ và label của mỗi điểm dữ liệu.
Với mỗi điểm dữ liệu $\mathbf{x}_i$ đặt $\mathbf{y}_i = [y_{i1}, y_{i2}, \dots, y_{iK}]$ là label vector của nó, trong đó nếu $\mathbf{x}_i$ được phân vào cluster $k$ thì $y_{ik} = 1$ và $y_{ij} = 0, \forall j \neq k$.

**Đầu vào**: Dữ liệu $X$ và số lượng cluster cần tìm $K$.
**Đầu ra**: Các center $M$ và label vector cho từng điểm dữ liệu $Y$.
1. Chọn $K$ điểm bất kỳ làm các center ban đầu.
2. Phân mỗi điểm dữ liệu vào cluster có center gần nó nhất.
3. Nếu việc gán dữ liệu vào từng cluster ở bước 2 không thay đổi so với vòng lặp trước nó thì ta dừng thuật toán.
4. Cập nhật center cho từng cluster bằng cách lấy trung bình cộng của tất các các điểm dữ liệu đã được gán vào cluster đó sau bước 2.
5. Quay lại bước 2.

**Các hàm số cần thiết cho K-means clustering**
1. `kmeans_init_centers` để khởi tạo các centers ban đầu.
2. `kmeans_asign_labels` để gán nhán mới cho các điểm khi biết các centers.
3. `kmeans_update_centers` để cập nhật các centers mới dữa trên dữ liệu vừa được gán nhãn.
4. `has_converged` để kiểm tra điều kiện dừng của thuật toán.

def kmeans_init_centers(X, k):
    # randomly pick k rows of X as initial centers
    return X[np.random.choice(X.shape[0], k, replace=False)]

def kmeans_assign_labels(X, centers):
    # calculate pairwise distances btw data and centers
    D = cdist(X, centers)
    # return index of the closest center
    return np.argmin(D, axis = 1)

def kmeans_update_centers(X, labels, K):
    centers = np.zeros((K, X.shape[1]))
    for k in range(K):
        # collect all points assigned to the k-th cluster 
        Xk = X[labels == k, :]
        # take average
        centers[k,:] = np.mean(Xk, axis = 0)
    return centers

def has_converged(centers, new_centers):
    # return True if two sets of centers are the same
    return (set([tuple(a) for a in centers]) == 
        set([tuple(a) for a in new_centers]))

def kmeans(X, K):
    centers = [kmeans_init_centers(X, K)]
    labels = []
    it = 0 
    while True:
        labels.append(kmeans_assign_labels(X, centers[-1]))
        new_centers = kmeans_update_centers(X, labels[-1], K)
        if has_converged(centers[-1], new_centers):
            break
        centers.append(new_centers)
        it += 1
    return (centers, labels, it)

(centers, labels, it) = kmeans(X, K)

**Hạn chế**
* Chúng ta cần biết số lượng cluster cần clustering
* Nghiệm cuối cùng phụ thuộc vào các centers được khởi tạo ban đầu
* Các cluster cần có só lượng điểm gần bằng nhau
* Các cluster cần có dạng hình tròn
* Khi một cluster nằm phía trong 1 cluster khác

Chính sách ưu đãi cho những nhóm khách hàng. Phân nhóm các chữ số viết tay. Tách vật thể (image segmentation). Nén ảnh/dữ liệu (image compression)
## K-nearest neighbor
Khi training, thuật toán này không học một điều gì từ dữ liệu training (đây cũng là lý do thuật toán này được xếp vào loại lazy learning), mọi tính toán được thực hiện khi nó cần dự đoán kết quả của dữ liệu mới.
K-nearest neighbor có thể áp dụng được vào cả hai loại của bài toán Supervised learning là Classification và Regression. KNN còn được gọi là một thuật toán Instance-based hay Memory-based learning.
* Với KNN, trong bài toán Classification, label của một điểm dữ liệu mới (hay kết quả của câu hỏi trong bài thi) được suy ra trực tiếp từ K điểm dữ liệu gần nhất trong training set. Label của một test data có thể được quyết định bằng major voting (bầu chọn theo số phiếu) giữa các điểm gần nhất, hoặc nó có thể được suy ra bằng cách đánh trọng số khác nhau cho mỗi trong các điểm gần nhất đó rồi suy ra label.
* Trong bài toán Regresssion, đầu ra của một điểm dữ liệu sẽ bằng chính đầu ra của điểm dữ liệu đã biết gần nhất (trong trường hợp K=1), hoặc là trung bình có trọng số của đầu ra của những điểm gần nhất, hoặc bằng một mối quan hệ dựa trên khoảng cách tới các điểm gần nhất đó.

**Ưu điểm của KNN**
1. Độ phức tạp tính toán của quá trình training là bằng 0.
2. Việc dự đoán kết quả của dữ liệu mới rất đơn giản.
3. Không cần giả sử gì về phân phối của các class.

**Nhược điểm của KNN**
1. KNN rất nhạy cảm với nhiễu khi K nhỏ.
2. KNN là một thuật toán mà mọi tính toán đều nằm ở khâu test. Trong đó việc tính khoảng cách tới từng điểm dữ liệu trong training set sẽ tốn rất nhiều thời gian, đặc biệt là với các cơ sở dữ liệu có số chiều lớn và có nhiều điểm dữ liệu. Với K càng lớn thì độ phức tạp cũng sẽ tăng lên. Ngoài ra, việc lưu toàn bộ dữ liệu trong bộ nhớ cũng ảnh hưởng tới hiệu năng của KNN.

## Gradient Descent
Điểm màu xanh lục là điểm local minimum (cực tiểu), và cũng là điểm làm cho hàm số đạt giá trị nhỏ nhất. Từ đây trở đi, tôi sẽ dùng local minimum để thay cho điểm cực tiểu, global minimum để thay cho điểm mà tại đó hàm số đạt giá trị nhỏ nhất. Global minimum là một trường hợp đặc biệt của local minimum.
Giả sử chúng ta đang quan tâm đến một hàm số một biến có đạo hàm mọi nơi. Xin cho tôi được nhắc lại vài điều đã quá quen thuộc:
1. Điểm local minimum $x^*$ của hàm số là điểm có đạo hàm $f’(x^*)$ bằng 0. Hơn thế nữa, trong lân cận của nó, đạo hàm của các điểm phía bên trái $x^*$ là không dương, đạo hàm của các điểm phía bên phải $x^*$ là không âm.
2. Đường tiếp tuyến với đồ thị hàm số đó tại 1 điểm bất kỳ có hệ số góc chính bằng đạo hàm của hàm số tại điểm đó.
Trong hình phía trên, các điểm bên trái của điểm local minimum màu xanh lục có đạo hàm âm, các điểm bên phải có đạo hàm dương. Và đối với hàm số này, càng xa về phía trái của điểm local minimum thì đạo hàm càng âm, càng xa về phía phải thì đạo hàm càng dương.

Trong Machine Learning nói riêng và Toán Tối Ưu nói chung, chúng ta thường xuyên phải tìm giá trị nhỏ nhất (hoặc đôi khi là lớn nhất) của một hàm số nào đó. Ví dụ như các hàm mất mát trong hai bài Linear Regression và K-means Clustering. Nhìn chung, việc tìm global minimum của các hàm mất mát trong Machine Learning là rất phức tạp, thậm chí là bất khả thi. Thay vào đó, người ta thường cố gắng tìm các điểm local minimum, và ở một mức độ nào đó, coi đó là nghiệm cần tìm của bài toán.

Các điểm local minimum là nghiệm của phương trình đạo hàm bằng 0. Nếu bằng một cách nào đó có thể tìm được toàn bộ (hữu hạn) các điểm cực tiểu, ta chỉ cần thay từng điểm local minimum đó vào hàm số rồi tìm điểm làm cho hàm có giá trị nhỏ nhất (đoạn này nghe rất quen thuộc, đúng không?). Tuy nhiên, trong hầu hết các trường hợp, việc giải phương trình đạo hàm bằng 0 là bất khả thi. Nguyên nhân có thể đến từ sự phức tạp của dạng của đạo hàm, từ việc các điểm dữ liệu có số chiều lớn, hoặc từ việc có quá nhiều điểm dữ liệu.

Hướng tiếp cận phổ biến nhất là xuất phát từ một điểm mà chúng ta coi là gần với nghiệm của bài toán, sau đó dùng một phép toán lặp để tiến dần đến điểm cần tìm, tức đến khi đạo hàm gần với 0. Gradient Descent (viết gọn là GD) và các biến thể của nó là một trong những phương pháp được dùng nhiều nhất.

**Thuật toán Gradient Descent:**
1. Dự đoán một điểm khởi tạo $\theta = \theta_0$.
2. Cập nhật $\theta$ đến khi đạt được kết quả chấp nhận được:

$~~~~~~~~~~~~~~~~~~~~~~~~\theta = \theta - \eta \nabla_{\theta}J(\theta)$
với $\nabla_{\theta}J(\theta)$ là đạo hàm của hàm mất mát tại $\theta$.

Quay trở lại hình vẽ ban đầu và một vài quan sát tôi đã nêu. Giả sử $x_{t}$ là điểm ta tìm được sau vòng lặp thứ $t$. Ta cần tìm một thuật toán để đưa $x_{t}$ về càng gần $x^*$ càng tốt.
Trong hình đầu tiên, chúng ta lại có thêm hai quan sát nữa:
1. Nếu đạo hàm của hàm số tại $x_{t}$: $f’(x_{t}) > 0$ thì $x_{t}$ nằm về bên phải so với $x^*$ (và ngược lại). Để điểm tiếp theo $x_{t+1}$ gần với $x^*$ hơn, chúng ta cần di chuyển xtxt về phía bên trái, tức về phía âm. Nói các khác, chúng ta cần di chuyển ngược dấu với đạo hàm:
$~~~~~~~~~~~~~~~~~~~~~~~~x_{t+1} = x_{t} + \Delta$
Trong đó Δ là một đại lượng ngược dấu với đạo hàm $f’(x_{t})$.
3. $x_{t}$ càng xa $x^*$ về phía bên phải thì $f’(x_{t})$ càng lớn hơn 0 (và ngược lại). Vậy, lượng di chuyển Δ, một cách trực quan nhất, là tỉ lệ thuận với $-f’(x_{t})$.

Hai nhận xét phía trên cho chúng ta một cách cập nhật đơn giản là: $x_{t+1} = x_{t} - \eta f’(x_{t})$

Trong đó $η$ (đọc là eta) là một số dương được gọi là learning rate (tốc độ học). Dấu trừ thể hiện việc chúng ta phải đi ngược với đạo hàm (Đây cũng chính là lý do phương pháp này được gọi là Gradient Descent - descent nghĩa là đi ngược). Các quan sát đơn giản phía trên, mặc dù không phải đúng cho tất cả các bài toán, là nền tảng cho rất nhiều phương pháp tối ưu nói chung và thuật toán Machine Learning nói riêng.

def grad(x):
    return 2*x+ 5*np.cos(x)

def cost(x):
    return x**2 + 5*np.sin(x)

def myGD1(eta, x0):
    x = [x0]
    for it in range(100):
        x_new = x[-1] - eta*grad(x[-1])
        if abs(grad(x_new)) < 1e-3:
            break
        x.append(x_new)
    return (x, it)

1. `grad` để tính đạo hàm
2. `cost` để tính giá trị của hàm số. Hàm này không sử dụng trong thuật toán nhưng thường được dùng để kiểm tra việc tính đạo hàm của đúng không hoặc để xem giá trị của hàm số có giảm theo mỗi vòng lặp hay không.
3. `myGD1` là phần chính thực hiện thuật toán Gradient Desent nêu phía trên. Đầu vào của hàm số này là learning rate và điểm bắt đầu. Thuật toán dừng lại khi đạo hàm có độ lớn đủ nhỏ.

## Perceptron Learning Algorithm (PLA)
Perceptron là một thuật toán Classification cho trường hợp đơn giản nhất: chỉ có hai class (lớp) (bài toán với chỉ hai class được gọi là binary classification) và cũng chỉ hoạt động được trong một trường hợp rất cụ thể. Tuy nhiên, nó là nền tảng cho một mảng lớn quan trọng của Machine Learning là Neural Networks và sau này là Deep Learning.
Cũng giống như các thuật toán lặp trong K-means Clustering và Gradient Descent, ý tưởng cơ bản của PLA là xuất phát từ một nghiệm dự đoán nào đó, qua mỗi vòng lặp, nghiệm sẽ được cập nhật tới một ví trí tốt hơn. Việc cập nhật này dựa trên việc giảm giá trị của một hàm mất mát nào đó.
1. Chọn ngẫu nhiên một vector hệ số $w$ với các phần tử gần 0.
2. Duyệt ngẫu nhiên qua từng điểm dữ liệu $\mathbf{x}_i$:
o Nếu $\mathbf{x}_i$ được phân lớp đúng, tức $\text{sgn}(\mathbf{w}^T\mathbf{x}_i) = y_i$, chúng ta không cần làm gì.
o Nếu $\mathbf{x}_i$ bị misclassifed, cập nhật $w$ theo công thức:
$~~~~~~~~~~~~~~~~~~~~~~~~\mathbf{w} = \mathbf{w} + y_i\mathbf{x}_i$
3. Kiểm tra xem có bao nhiêu điểm bị misclassifed. Nếu không còn điểm nào, dừng thuật toán. Nếu còn, quay lại bước 2.

def h(w, x):    
    return np.sign(np.dot(w.T, x))

def has_converged(X, y, w):    
    return np.array_equal(h(w, X), y) 

def perceptron(X, y, w_init):
    w = [w_init]
    N = X.shape[1]
    d = X.shape[0]
    mis_points = []
    while True:
        # mix data 
        mix_id = np.random.permutation(N)
        for i in range(N):
            xi = X[:, mix_id[i]].reshape(d, 1)
            yi = y[0, mix_id[i]]
            if h(w[-1], xi)[0] != yi: # misclassified point
                mis_points.append(mix_id[i])
                w_new = w[-1] + yi*xi 
                w.append(w_new)
                
        if has_converged(X, y, w[-1]):
            break
    return (w, mis_points)

d = X.shape[0]
w_init = np.random.randn(d, 1)
(w, m) = perceptron(X, y, w_init)

1. `h(w, x)`: tính đầu ra khi biết đầu vào x và weights w.
2. `has_converged(X, y, w)`: kiểm tra xem thuật toán đã hội tụ chưa. Ta chỉ cần so sánh h(w, X) với ground truth y. Nếu giống nhau thì dừng thuật toán.
3. `perceptron(X, y, w_init)`: hàm chính thực hiện PLA.

##### Mô hình Neural Network đầu tiên
Hàm số xác định class của Perceptron $\text{label}(\mathbf{x}) = \text{sgn}(\mathbf{w}^T\mathbf{x})$ có thể được mô tả như hình vẽ (được gọi là network) dưới đây:

Đầu vào của network $x$ được minh họa bằng các node màu xanh lục với node $x_0$ luôn luôn bằng 1. Tập hợp các node màu xanh lục được gọi là Input layer. Trong ví dụ này, tôi giả sử số chiều của dữ liệu $d=4$. Số node trong input layer luôn luôn là $d+1$ với một node là 1 được thêm vào. Node $x_0 = 1$ này đôi khi được ẩn đi.
Các trọng số (weights) $w0,w1,…,wd$ được gán vào các mũi tên đi tới node $\displaystyle z = \sum_{i=0}^dw_ix_i = \mathbf{w}^T\mathbf{x}$. Node $y = \text{sgn}(z)$ là output của network. Ký hiệu hình chữ Z ngược màu xanh trong node yy thể hiện đồ thị của hàm số sgnsgn.
Trong thuật toán PLA, ta phải tìm các weights trên các mũi tên sao cho với mỗi xixi ở tập các điểm dữ liệu đã biết được đặt ở Input layer, output của network này trùng với nhãn yiyi tương ứng.
Hàm số $y = \text{sgn}(z)$ còn được gọi là activation function. Đây chính là dạng đơn giản nhất của Neural Network.
Các Neural Networks sau này có thể có nhiều node ở output tạo thành một output layer, hoặc có thể có thêm các layer trung gian giữa input layer và output layer. Các layer trung gian đó được gọi là hidden layer. Khi biểu diễn các Networks lớn, người ta thường giản lược hình bên trái thành hình bên phải. Trong đó node $x_0=1$ thường được ẩn đi. Node $z$ cũng được ẩn đi và viết gộp vào trong node $y$. Perceptron thường được vẽ dưới dạng đơn giản như Hình 5 bên phải.
Để ý rằng nếu ta thay activation function bởi $y=z$, ta sẽ có Neural Network mô tả thuật toán Linear Regression như hình dưới. Với đường thẳng chéo màu xanh thể hiện đồ thị hàm số $y=z$. Các trục tọa độ đã được lược bỏ.

> **Hai mô hình tuyến tính (linear models) Linear Regression và Perceptron Learning Algorithm (PLA) có chung một dạng:
> $~~~~~~~~~~~~~~~~~~~~~~~~y = f(\mathbf{w}^T\mathbf{x})$
trong đó $f()$ được gọi là activation function, và $x$ được hiểu là dữ liệu mở rộng với $x_0 = 1$ được thêm vào để thuận tiện cho việc tính toán. Với linear regression thì $f(s) = s$, với PLA thì $f(s) = \text{sgn}(s)$. Trong linear regression, tích vô hướng $\mathbf{w}^T\mathbf{x}$ được trực tiếp sử dụng để dự đoán output $y$, loại này phù hợp nếu chúng ta cần dự đoán một giá trị thực của đầu ra không bị chặn trên và dưới. Trong PLA, đầu ra chỉ nhận một trong hai giá trị $1$ hoặc $−1$, phù hợp với các bài toán binary classification.**

## Logistic Regression
Đầu ra dự đoán của:
• Linear Regression:
$~~~~~~~~~~~~~~~~~~~~~~~~f(\mathbf{x}) = \mathbf{w}^T \mathbf{x}$
• PLA:
$~~~~~~~~~~~~~~~~~~~~~~~~f(\mathbf{x}) = \text{sgn}(\mathbf{w}^T\mathbf{x})$
Đầu ra dự đoán của logistic regression thường được viết chung dưới dạng:
$~~~~~~~~~~~~~~~~~~~~~~~~f(\mathbf{x}) = \theta(\mathbf{w}^T\mathbf{x})$
Trong đó $θ$ được gọi là logistic function. Một số activation cho mô hình tuyến tính được cho trong hình dưới đây:

• Đường màu vàng biểu diễn linear regression. Đường này không bị chặn nên không phù hợp cho bài toán này. Có một trick nhỏ để đưa nó về dạng bị chặn: cắt phần nhỏ hơn 0 bằng cách cho chúng bằng 0, cắt các phần lớn hơn 1 bằng cách cho chúng bằng 1. Sau đó lấy điểm trên đường thẳng này có tung độ bằng 0.5 làm điểm phân chia hai class, đây cũng không phải là một lựa chọn tốt. Giả sử có thêm vài bạn sinh viên tiêu biểu ôn tập đến 20 giờ và, tất nhiên, thi đỗ. Khi áp dụng mô hình linear regression như hình dưới đây và lấy mốc 0.5 để phân lớp, toàn bộ sinh viên thi trượt vẫn được dự đoán là trượt, nhưng rất nhiều sinh viên thi đỗ cũng được dự đoán là trượt (nếu ta coi điểm x màu xanh lục là ngưỡng cứng để đưa ra kết luận). Rõ ràng đây là một mô hình không tốt. Anh chàng sinh viên tiêu biểu này đã kéo theo rất nhiều bạn khác bị trượt.
• Đường màu đỏ (chỉ khác với activation function của PLA ở chỗ hai class là 0 và 1 thay vì -1 và 1) cũng thuộc dạng ngưỡng cứng (hard threshold). PLA không hoạt động trong bài toán này vì dữ liệu đã cho không linearly separable.
• Các đường màu xanh lam và xanh lục phù hợp với bài toán của chúng ta hơn. Chúng có một vài tính chất quan trọng sau:
* Là hàm số liên tục nhận giá trị thực, bị chặn trong khoảng (0,1)(0,1).
* Nếu coi điểm có tung độ là 1/2 làm điểm phân chia thì các điểm càng xa điểm này về phía bên trái có giá trị càng gần 0. Ngược lại, các điểm càng xa điểm này về phía phải có giá trị càng gần 1. Điều này khớp với nhận xét rằng học càng nhiều thì xác suất đỗ càng cao và ngược lại.
* Mượt (smooth) nên có đạo hàm mọi nơi, có thể được lợi trong việc tối ưu.

### Sigmoid function
Trong số các hàm số có 3 tính chất nói trên thì hàm sigmoid:
$~~~~~~~~~~~~~~~~~~~~~~~~f(s) = \frac{1}{1 + e^{-s}} \triangleq \sigma(s)$
được sử dụng nhiều nhất, vì nó bị chặn trong khoảng $(0,1)$. Thêm nữa:
$~~~~~~~~~~~~~~~~~~~~~~~~\lim_{s \rightarrow -\infty}\sigma(s) = 0; ~~ \lim_{s \rightarrow +\infty}\sigma(s) = 1$
Đặc biệt hơn nữa:
$~~~~~~~~~~~~~~~~~~~~~~~~\begin{eqnarray}
\sigma’(s) &=& \frac{e^{-s}}{(1 + e^{-s})^2} \\
&=& \frac{1}{1 + e^{-s}} \frac{e^{-s}}{1 + e^{-s}} \\
&=& \sigma(s)(1 - \sigma(s))
\end{eqnarray}$
Ngoài ra, hàm tanh cũng hay được sử dụng:
$~~~~~~~~~~~~~~~~~~~~~~~~\text{tanh}(s) = \frac{e^{s} - e^{-s}}{e^s + e^{-s}}$
Hàm số này nhận giá trị trong khoảng (−1,1)(−1,1) nhưng có thể dễ dàng đưa nó về khoảng (0,1)(0,1). Bạn đọc có thể chứng minh được:

$~~~~~~~~~~~~~~~~~~~~~~~~\text{tanh}(s) = 2\sigma(2s) - 1$

X = np.array([[0.50, 0.75, 1.00, 1.25, 1.50, 1.75, 1.75, 2.00, 2.25, 2.50, 
              2.75, 3.00, 3.25, 3.50, 4.00, 4.25, 4.50, 4.75, 5.00, 5.50]])
y = np.array([0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1])

# extended data 
X = np.concatenate((np.ones((1, X.shape[1])), X), axis = 0)

def sigmoid(s):
    return 1/(1 + np.exp(-s))

def logistic_sigmoid_regression(X, y, w_init, eta, tol = 1e-4, max_count = 10000):
    w = [w_init]    
    it = 0
    N = X.shape[1]
    d = X.shape[0]
    count = 0
    check_w_after = 20
    while count < max_count:
        # mix data 
        mix_id = np.random.permutation(N)
        for i in mix_id:
            xi = X[:, i].reshape(d, 1)
            yi = y[i]
            zi = sigmoid(np.dot(w[-1].T, xi))
            w_new = w[-1] + eta*(yi - zi)*xi
            count += 1
            # stopping criteria
            if count%check_w_after == 0:                
                if np.linalg.norm(w_new - w[-check_w_after]) < tol:
                    return w
            w.append(w_new)
    return w
eta = .05 
d = X.shape[0]
w_init = np.random.randn(d, 1)

w = logistic_sigmoid_regression(X, y, w_init, eta)

## Mô hình chung cho các bài toán Machine Learning
#### TRAINING PHASE
Có hai khối có nền màu xanh lục chúng ta cần phải thiết kế:
##### Feature Extractor
ĐẦU RA
Mục đích của Feature Engineering là tạo ra một Feature Extractor biến dữ liệu thô ban đầu thành dữ liệu phù hợp với từng mục đích khác nhau.
ĐẦU VÀO
* **raw training input**. Raw input là tất cả các thông tin ta biết về dữ liệu. Ví dụ: với ảnh thì là giá trị của từng pixel; với văn bản thì là từng từ, từng câu; với file âm thanh thì nó là một đoạn tín hiệu; với cơ sở dữ liệu Iris thì nó là độ dài các cánh hoa và đài hoa, … Dữ liệu thô này thường không ở dạng vector, không có số chiều như nhau. Thậm chí có thể có số chiều như nhau nhưng số chiều quá lớn, như một bức ảnh màu 1000 pixel x 1000 pixel thì số elements đã là 3×1063×106 (3 vì ảnh màu thường có 3 channels: Red, Green, Blue). Đây là một con số quá lớn, không lợi cho lưu trữ và tính toán.
* **(optional) output của training set**. Trong các bài toán Unsupervised learning, ta không biết output nên hiển nhiên sẽ không có đầu vào này. Trong các bài toán Supervised learning, có khi dữ liệu này cũng không được sử dụng. Ví dụ: nếu raw input đã có cùng số chiều rồi nhưng số chiều quá lớn, ta muốn giảm số chiều của nó thì cách đơn giản nhất là chiếu vector đó xuống một không gian có số chiều nhỏ hơn bằng cách lấy một ma trận ngẫu nhiên nhân với nó. Ma trận này thường là ma trận béo (số hàng ít hơn số cột, tiếng Anh - fat matrices) để đảm bảo số chiều thu được nhỏ hơn số chiều ban đầu. Việc làm này mặc dù làm mất đi thông tin, trong nhiều trường hợp vẫn mang lại hiệu quả vì đã giảm được lượng tính toán ở phần sau. Đôi khi ma trận chiếu không phải là ngẫu nhiên mà có thể được học dựa trên toàn bộ raw input, ta sẽ có bài toán tìm ma trận chiếu để lượng thông tin mất đi là ít nhất. Trong nhiều trường hợp, dữ liệu output của training set cũng được sử dụng để tạo ra Feature Extractor. Ví dụ: trong bài toán classification, ta không quan tâm nhiều đến việc mất thông tin hay không, ta chỉ quan tâm đến việc những thông tin còn lại có đặc trưng cho từng class hay không. Ví dụ, dữ liệu thô là các hình vuông và hình tam giác có màu đỏ và xanh. Trong bài toán phân loại đa giác, các output là tam giác và vuông, thì ta không quan tâm tới màu sắc mà chỉ quan tâm tới số cạnh của đa giác. Ngược lại, trong bài toán phân loại màu, các class là xanh và đỏ, ta không quan tâm tới số cạnh mà chỉ quan tâm đến màu sắc thôi.
* **(optional) Prior knowledge about data**: Đôi khi những giả thiết khác về dữ liệu cũng mang lại lợi ích. Ví dụ, trong bài toán classification, nếu ta biết dữ liệu là (gần như) linearly separable thì ta sẽ đi tìm một ma trận chiếu sao cho ở trong không gian mới, dữ liệu vẫn đảm bảo tính linearly separable, việc này thuận tiện hơn cho phần classification vì các thuật toán linear, nhìn chung, đơn giản hơn.
Sau khi học được feature extractor thì ta cũng sẽ thu được extracted features cho raw input data. Những extracted features này được dùng để huấn luyện các thuật toán Classification, Clustering, Regression,… ở phía sau.
##### Main Algorithms
Khi có được extracted features rồi, chúng ta sử dụng những thông tin này cùng với (optional) training output và (optional) prior knowledge để tạo ra các mô hình phù hợp, điều mà chúng ta đã làm ở những bài trước.

***Chú ý**: Trong một số thuật toán cao cấp hơn, việc huấn luyện feature extractor và main algorithm được thực hiện cùng lúc với nhau chứ không phải từng bước như trên.
**Một điểm rất quan trọng:** khi xây dựng bộ feature extractor và main algorithms, chúng ta không được sử dụng bất kỳ thông tin nào trong tập test data. Ta phải giả sử rằng những thông tin trong test data chưa được nhìn thấy bao giờ.*
#### TESTING PHASE
Bước này đơn giản hơn nhiều. Với raw input mới, ta sử dụng feature extractor đã tạo được ở trên (tất nhiên không được sử dụng output của nó vì output là cái ta đang đi tìm) để tạo ra feature vector tương ứng. Feature vector được đưa vào main algorithm đã được học ở training phase để dự đoán output.
## Softmax Regression
Các bài toán classification thực tế thường có rất nhiều classes (multi-class), các binary classifiers mặc dù có thể áp dụng cho các bài toán multi-class, chúng vẫn có những hạn chế nhất định. Với binary classifiers, kỹ thuật được sử dụng nhiều nhất one-vs-rest có một hạn chế về tổng các xác suất. Một phương pháp mở rộng của Logistic Regression sẽ được giới thiệu giúp khắc phục hạn chế trên. Một lần nữa, dù là Softmax Regression, phương pháp này được sử dụng rộng rãi như một phương pháp classification.
**Mô hình one-vs-rest**. Output layer (màu đỏ nhạt) có thể phân tách thành hai sublayer như hình dưới đây:
Dữ liệu $x$ có số chiều là $(d+1)$ vì có phần tử 1 được thêm vào phía trước, thể hiện hệ số tự do trong hàm tuyến tính. Hệ số tự do $w_{0j}$ còn được gọi là bias.
Giả sử số classes là $C$. Với one-vs-rest, chúng ta cần xây dựng $C$ Logistic Regression khác nhau. Các đầu ra dự đoán được tính theo hàm sigmoid:
$~~~~~~~~~~~~~~~~~~~~~~~~a_i = \text{sigmoid}(z_i) = \text{sigmoid}(\mathbf{w}_i^T\mathbf{x})$
Chú ý rằng các mô hình Linear Regression, PLA, Logistic Regression chỉ có 1 node ở output layer. Trong các trường hợp đó, tham số mô hình chỉ là 1 vector $w$. Trong trường hợp output layer có nhiều hơn 1 node, tham số mô hình sẽ là tập hợp tham số $w_i$ ứng với từng node. Lúc này, ta có ma trận trọng số $\mathbf{W} = [\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_C]$.
#### Softmax function
Chúng ta cần một mô hình xác suất sao cho với mỗi input $x$, $a_i$ thể hiện xác suất để input đó rơi vào class $i$. Vậy điều kiện cần là các $a_i$ phải dương và tổng của chúng bằng 1. Để có thể thỏa mãn điều kiện này, chúng ta cần nhìn vào mọi giá trị $z_i$ và dựa trên quan hệ giữa các $z_i$ này để tính toán giá trị của $a_i$. Ngoài các điều kiện aiai lớn hơn 0 và có tổng bằng 1, chúng ta sẽ thêm một điều kiện cũng rất tự nhiên nữa, đó là: giá trị $z_i = \mathbf{w}_i^T\mathbf{x}$ càng lớn thì xác suất dữ liệu rơi vào class $i$ càng cao. Điều kiện cuối này chỉ ra rằng chúng ta cần một hàm đồng biến ở đây.
Chú ý rằng $z_i$ có thể nhận giá trị cả âm và dương. Một hàm số mượt đơn giản có thể chắc chắn biến $z_i$ thành một giá trị dương, và hơn nữa, đồng biến, là hàm $\exp(z_i) = e^{z_i}$. Điều kiện mượt để thuận lợi hơn trong việc tính đạo hàm sau này. Điều kiện cuối cùng, tổng các aiai bằng 1 có thể được đảm bảo nếu:
$~~~~~~~~~~~~~~~~~~~~~~~~a_i = \frac{\exp(z_i)}{\sum_{j=1}^C \exp(z_j)}, ~~ \forall i = 1, 2, \dots, C$
Hàm số này, tính tất cả các $a_i$ dựa vào tất cả các $z_i$, thõa mãn tất cả các điều kiện đã xét: dương, tổng bằng 1, giữ được thứ tự của $z_i$. Hàm số này được gọi là **softmax function**
Hình vẽ dưới đây thể hiện mạng Softmax Regression dưới dạng neural network:
Ở phần bên phải, hàm tuyến tính $Σ$ và hàm softmax (activation function) được tách riêng ra để phục vụ cho mục đích minh họa. Dạng short form ở bên phải là dạng hay được sử dụng trong các Neural Networks, lớp aa được ngầm hiểu là bao gồm cả lớp $z$.
## Hàm mất mát và phương pháp tối ưu
#### One hot coding
Với cách biểu diễn network như trên, mỗi output sẽ không còn là một giá trị tương ứng với mỗi class nữa mà sẽ là một vector có đúng 1 phần tử bằng 1, các phần tử còn lại bằng 0. Phần tử bằng 1 năm ở vị trí tương ứng với class đó, thể hiện rằng điểm dữ liệu đang xét rơi vào class này với xác suất bằng 1 (sự thật là như thế, không cần dự đoán). Cách mã hóa output này chính là one-hot coding mà tôi đã đề cập trong bài K-means clustering và bài trước.
Khi sử dụng mô hình Softmax Regression, với mỗi đầu vào $x$, ta sẽ có đầu ra dự đoán là $\mathbf{a} = \text{softmax}(\mathbf{W}^T\mathbf{x})$. Trong khi đó, đầu ra thực sự chúng ta có là vector $y$ được biểu diễn dưới dạng one-hot coding.
Hàm mất mát sẽ được xây dựng để tối thiểu sự khác nhau giữa đầu ra dự đoán $a$ và đầu ra thực sự $y$. Một lựa chọn đầu tiên ta có thể nghĩ tới là:
$~~~~~~~~~~~~~~~~~~~~~~~~J(\mathbf{W}) = \sum_{i=1}^N ||\mathbf{a}_i - \mathbf{y}_i||_2^2$
Tuy nhiên đây chưa phải là một lựa chọn tốt. Khi đánh giá sự khác nhau (hay khoảng cách) giữa hai phân bố xác suất (probability distributions), chúng ta có một đại lượng đo đếm khác hiệu quả hơn. Đại lượng đó có tên là cross entropy.
#### Cross Entropy
Cross entropy giữa hai phân phối $p$ và $q$ được định nghĩa là:
$~~~~~~~~~~~~~~~~~~~~~~~~H(\mathbf{p}, \mathbf{q}) = \mathbf{E_p}[-\log \mathbf{q}]$
Với $p$ và $q$ là rời rạc (như $y$ và $a$ trong bài toán của chúng ta), công thức này được viết dưới dạng:
$~~~~~~~~~~~~~~~~~~~~~~~~H(\mathbf{p}, \mathbf{q}) =-\sum_{i=1}^C p_i \log q_i$
Có hai nhận xét quan trọng sau đây:
* Giá trị nhỏ nhất của cả hai hàm số đạt được khi q=pq=p tại hoành độ của các điểm màu xanh lục.
* Quan trọng hơn, hàm cross entropy nhận giá trị rất cao (tức loss rất cao) khi qq ở xa pp. Trong khi đó, sự chênh lệch giữa các loss ở gần hay xa nghiệm của hàm bình phương khoảng cách (q−p)2(q−p)2 là không đáng kể. Về mặt tối ưu, hàm cross entropy sẽ cho nghiệm gần với pp hơn vì những nghiệm ở xa bị trừng phạt rất nặng.

Hai tính chất trên đây khiến cho cross entropy được sử dụng rộng rãi khi tính khoảng cách giữa hai phân phối xác suất.
**Chú ý:** Hàm cross entropy không có tính đối xứng $H(\mathbf{p}, \mathbf{q}) \neq H(\mathbf{q}, \mathbf{p})$. Điều này có thể dễ dàng nhận ra ở việc các thành phần của $p$ trong công thức có thể nhận giá trị bằng 0, trong khi đó các thành phần của $q$ phải là dương vì $log⁡(0)$ không xác định. Chính vì vậy, khi sử dụng cross entropy trong các bài toán supervised learning, $p$ thường là đầu ra thực sự vì đầu ra thực sự chỉ có 1 thành phần bằng 1, còn lại bằng 0 (one-hot), $q$ thường là đầu ra dự đoán, khi mà không có xác suất nào tuyệt đối bằng 1 hoặc tuyệt đối bằng 0 cả.
## Multi-layer Perceptron và Backpropagation
*Hình 1: PLA biểu diễn các hàm logic đơn giản.*
*Hình 2: Multilayer Perceptron biểu diễn hàm XOR*

* **Perceptron Learing Algorithm** là một trường hợp của *single-layer neural network* với activation fucntion là hàm $sgn$. Trong khi đó, Perceptron là tên chung để chỉ các Neural Network với chỉ một input layer và một output tại output layer, không có hidden layer.
* Các activation function có thể là các nonlinear function khác, ví dụ như *sigmoid function* hoặc *tanh function*. Các activation function phải là nonlinear (phi tuyến), vì nếu không, nhiều layer hay một layer cũng là như nhau. Ví dụ với hai layer trong Hình 2, nếu activation function là một hàm linear (giả sử hàm $f(s)=s$), thì cả hai layer có thể được thay bằng một layer với ma trận hệ số $\mathbf{W} = \mathbf{W}^{(1)}\mathbf{W}^{(2)}$ (tạm bỏ qua biases).
* Khác với các bài trước về Neural Networks, khi làm việc với MLP, ta nên tách riêng phần biases và ma trận hệ số ra. Điều này đồng nghĩa với việc vector input $x$ là vector KHÔNG mở rộng.
#### Layers
Ngoài Input layers và Output layers, một Multi-layer Perceptron (MLP) có thể có nhiều Hidden layers ở giữa. Các Hidden layers theo thứ tự từ input layer đến output layer được đánh số thứ thự là Hidden layer 1, Hidden layer 2, … Hình 3 dưới đây là một ví dụ với 2 Hidden layers.
Số lượng layer trong một MLP được tính bằng số hidden layers cộng với 1. Tức là khi đếm số layers của một MLP, ta không tính input layers. Số lượng layer trong một MLP thường được ký hiệu là $L$. Trong Hình 3 trên đây, $L=3$.
#### Units
Một node hình tròn trong một layer được gọi là một unit. Unit ở các input layer, hidden layers, và output layer được lần lượt gọi là input unit, hidden unit, và output unit. Đầu vào của các hidden layer được ký hiệu bởi $z$, đầu ra của mỗi unit thường được ký hiệu là $a$ (thể hiện activation, tức giá trị của mỗi unit sau khi ta áp dụng activation function lên $z$). Đầu ra của unit thứ $i$ trong layer thứ $l$ được ký hiệu là $a_i^{(l)}$. Giả sử thêm rằng số unit trong layer thứ $l$) (không tính bias) là $d(l)$. Vector biểu diễn output của layer thứ $l$ được ký hiệu là $\mathbf{a}^{(l)} \in \mathbb{R}^{d^{(l)}}$.
Khi làm việc với những Neural Networks phức tạp, cách tốt nhất để hạn chế lỗi là viết cụ thể chiều của mỗi ma trận hay vector ra
#### Weights và Biases
Có $L$ ma trận trọng số cho một MLP có $L$ layers. Các ma trận này được ký hiệu là $\mathbf{W}^{(l)} \in \mathbb{R}^{d^{(l-1)}\times d^{(l)}}, l = 1, 2, \dots, L$ trong đó $W(l)$ thể hiện các kết nối từ layer thứ $l−1$ tới layer thứ $l$ (nếu ta coi input layer là layer thứ $0$). Cụ thể hơn, phần tử $w^{(l)}_{ij}$ thể hiện kết nối từ node thứ $i$ của layer thứ $(l−1)$ tới node từ $j$ của layer thứ $(l)$. Các biases của layer thứ $(l)$ được ký hiệu là $\mathbf{b}^{(l)} \in \mathbb{R}^{d^{(l)}}$. Các trọng số này được ký hiệu như trên Hình 4. Khi tối ưu một MLP cho một công việc nào đó, chúng ta cần đi tìm các weghts và biases này.
Tập hợp các weights và biases lần lượt được ký hiệu là $W$ và $b$
#### Activation functions
Mỗi output của một unit (trừ các input units) được tính dựa vào công thức:
$~~~~~~~~~~~~~~~~~~~~~~~~a_i^{(l)} = f(\mathbf{w}_i^{(l)T}\mathbf{a}^{(l-1)} + b_i^{(l)})$
Trong đó $f(.)$ là một (nonlinear) activation function. Ở dạng vector, biểu thức bên trên được viết là:
$~~~~~~~~~~~~~~~~~~~~~~~~\mathbf{a}^{(l)} = f(\mathbf{W}^{(l)T}\mathbf{a}^{(l-1)} + \mathbf{b}^{(l)})$
Khi activation function $f(.)$ được áp dụng cho một ma trận (hoặc vector), ta hiểu rằng nó được áp dụng cho từng thành phần của ma trận đó. Sau đó các thành phần này được sắp xếp lại đúng theo thứ tự để được một ma trận có kích thước bằng với ma trận input. Trong tiếng Anh, việc áp dụng lên từng phần tử như thế này được gọi là element-wise.
##### Hàm sgn không được sử dụng trong MLP
Hàm sgn (còn gọi là hard-threshold) chỉ được sử dụng trong PLA, mang mục đích giáo dục nhiều hơn. Trong thực tế, hàm sgn không được sử dụng vì hai lý do: đầu ra là discrete, và đạo hàm tại hầu hết các điểm bằng 0 (trừ điểm 0 không có đạo hàm). Việc đạo hàm bằng 0 này khiến cho các thuật toán gradient-based (ví dụ như Gradient Descent) không hoạt động!
##### Sigmoid và tanh
Hàm sigmoid có dạng $f(s) = 1/(1 + \exp(-s))$ với đồ thị như trong Hình 5 (trái). Nếu đầu vào lớn, hàm số sẽ cho đầu ra gần với 1. Với đầu vào nhỏ (rất âm), hàm số sẽ cho đầu ra gần với 0. Hàm số này được sử dụng nhiều trong quá khứ ví có đạo hàm rất đẹp. Những năm gần đây, hàm số này ít khi được sử dụng. Nó có một nhược điểm cơ bản:
* Sigmoid saturate and kill gradients: Một nhược điểm dễ nhận thấy là khi đầu vào có trị tuyệt đối lớn (rất âm hoặc rất dương), gradient của hàm số này sẽ rất gần với 0. Điều này đồng nghĩa với việc các hệ số tương ứng với unit đang xét sẽ gần như không được cập nhật. Bạn đọc sẽ hiểu rõ hơn phần này trong phần Backpropagation.

Hàm tanh cũng có nhược điểm tương tự về việc gradient rất nhỏ với các đầu vào có trị tuyệt đối lớn.
##### ReLU
ReLU (Rectified Linear Unit) được sử dụng rộng rãi gần đây vì tính đơn giản của nó. Đồ thị của hàm ReLU được minh họa trên Hình 5 (trái)). Nó có công thức toán học $f(s) = \max(0, s)$ - rất đơn giản. Ưu điểm chính của nó là:
* ReLU được chứng minh giúp cho việc training các Deep Networks nhanh hơn rất nhiều (theo Krizhevsky et al.). Hình 5 (phải) so sánh sự hội tụ của SGD khi sử dụng hai activation function khác nhau: ReLU và tanh. Sự tăng tốc này được cho là vì ReLU được tính toán gần như tức thời và gradient của nó cũng được tính cực nhanh với gradient bằng 1 nếu đầu vào lớn hơn 0, bằng 0 nếu đầu vào nhỏ hơn 0.
* Mặc dù hàm ReLU không có đạo hàm tại $s=0$, trong thực nghiệm, người ta vẫn thường định nghĩa $ReLU′(0)=0$ và khẳng định thêm rằng, xác suất để input của một unit bằng 0 là rất nhỏ.
Hàm ReLU có nhiều biến thể khác như Noisy ReLU, Leaky ReLu, ELUs.
> * Output layer nhiều khi không có activation function mà sử dụng trực tiếp giá trị đầu vào z(l)izi(l) của mỗi unit. Hoặc nói một cách khác, activation function chính là hàm identity, tức đầu ra bằng đầu vào. Với các bài toán classification, output layer thường là một Softmax Regression layer giúp tính xác suất để một điểm dữ liệu rơi vào mỗi class.
> * Mặc dù activation function cho mỗi unit có thể khác nhau, trong cùng một network, activation như nhau thường được sử dụng. Điều này giúp cho việc tính toán được đơn giản hơn.
#### Backpropagation
Phương pháp phổ biến nhất để tối ưu MLP vẫn là Gradient Descent (GD). Để áp dụng GD, chúng ta cần tính được gradient của hàm mất mát theo từng ma trận trọng số $W(l)$ và vector bias $b(l)$. Trước hết, chúng ta cần tính predicted output $\mathbf{\hat{y}}$ với một input $x$
Bước này được gọi là feedforward vì cách tính toán được thực hiện từ đầu đến cuối của network. MLP cũng được gọi
Giả sử $J(W,b,X,Y)$ là một hàm mất mát của bài toán, trong đó $W,b$ là tập hợp tất cả các ma trận trọng số giữa các layers và biases của mỗi layer. $X,Y$ là cặp dữ liệu huấn luyện với mỗi cột tương ứng với một điểm dữ liệu. Để có thể áp dụng các gradient-based methods (mà Gradient Descent là một ví dụ), chúng ta cần tính được:
$~~~~~~~~~~~~~~~~~~~~~~~~\frac{\partial J}{\partial \mathbf{W}^{(l)}} ; \frac{\partial J}{\partial \mathbf{b}^{(l)}},~~ l = 1, 2, \dots, L$
Một ví dụ của hàm mất mát là hàm Mean Square Error (MSE) tức trung bình của bình phương lỗi.
$~~~~~~~~~~~~~~~~~~~~~~~~\begin{eqnarray}
J(\mathbf{W, b, X, Y}) &=& \frac{1}{N}\sum_{n=1}^N || \mathbf{y}_n - \mathbf{\hat{y}}_n||_2^2 \\
&=&\frac{1}{N}\sum_{n=1}^N || \mathbf{y}_n - \mathbf{a}_n^{(L)}||_2^2
\end{eqnarray}$
Với $N$ là số cặp dữ liệu $(x,y)$ trong tập training.
Theo những công thức ở trên, việc tính toán trực tiếp giá trị này là cực kỳ phức tạp vì hàm mất mát không phụ thuộc trực tiếp vào các hệ số. Phương pháp phổ biến nhất được dùng có tên là **Backpropagation** giúp tính gradient ngược từ layer cuối cùng đến layer đầu tiên. Layer cuối cùng được tính toán trước vì nó gần gũi hơn với predicted outputs và hàm mất mát. Việc tính toán gradient của các layer trước được thực hiện dựa trên một quy tắc quen thuộc có tên là chain rule, tức đạo hàm của hàm hợp.
## Validation
Chúng ta vẫn quen với việc chia tập dữ liệu ra thành hai tập nhỏ: training data và test data. Vậy làm cách nào để biết được chất lượng của mô hình với unseen data (tức dữ liệu chưa nhìn thấy bao giờ)?
Phương pháp đơn giản nhất là trích từ tập training data ra một tập con nhỏ và thực hiện việc đánh giá mô hình trên tập con nhỏ này. Tập con nhỏ được trích ra từ training set này được gọi là validation set. Lúc này, training set là phần còn lại của training set ban đầu. Train error được tính trên training set mới này, và có một khái niệm nữa được định nghĩa tương tự như trên validation error, tức error được tính trên tập validation.
Với khái niệm mới này, ta tìm mô hình sao cho cả train eror và validation error đều nhỏ, qua đó có thể dự đoán được rằng test error cũng nhỏ. Phương pháp thường được sử dụng là sử dụng nhiều mô hình khác nhau. Mô hình nào cho validation error nhỏ nhất sẽ là mô hình tốt.
Thông thường, ta bắt đầu từ mô hình đơn giản, sau đó tăng dần độ phức tạp của mô hình. Tới khi nào validation error có chiều hướng tăng lên thì chọn mô hình ngay trước đó. Chú ý rằng mô hình càng phức tạp, train error có xu hướng càng nhỏ đi.
#### Cross-validation
Trong nhiều trường hợp, chúng ta có rất hạn chế số lượng dữ liệu để xây dựng mô hình. Nếu lấy quá nhiều dữ liệu trong tập training ra làm dữ liệu validation, phần dữ liệu còn lại của tập training là không đủ để xây dựng mô hình. Lúc này, tập validation phải thật nhỏ để giữ được lượng dữ liệu cho training đủ lớn. Tuy nhiên, một vấn đề khác nảy sinh. Khi tập validation quá nhỏ, hiện tượng overfitting lại có thể xảy ra với tập training còn lại. Có giải pháp nào cho tình huống này không?
Câu trả lời là **cross-validation.**
**Cross validation** là một cải tiến của validation với lượng dữ liệu trong tập validation là nhỏ nhưng chất lượng mô hình được đánh giá trên nhiều tập validation khác nhau. Một cách thường đường sử dụng là chia tập training ra $k$ tập con không có phần tử chung, có kích thước gần bằng nhau. Tại mỗi lần kiểm thử , được gọi là run, một trong số $k$ tập con được lấy ra làm validata set. Mô hình sẽ được xây dựng dựa vào hợp của $k−1$ tập con còn lại. Mô hình cuối được xác định dựa trên trung bình của các train error và validation error. Cách làm này còn có tên gọi là **k-fold cross validation.**
Khi $k$ bằng với số lượng phần tử trong tập training ban đầu, tức mỗi tập con có đúng 1 phần tử, ta gọi kỹ thuật này là **leave-one-out**.
## Regularization
Một nhược điểm lớn của **cross-validation** là số lượng **training runs** tỉ lệ thuận với k. Điều đáng nói là mô hình polynomial như trên chỉ có một tham số cần xác định là bậc của đa thức. Trong các bài toán Machine Learning, lượng tham số cần xác định thường lớn hơn nhiều, và khoảng giá trị của mỗi tham số cũng rộng hơn nhiều, chưa kể đến việc có những tham số có thể là số thực. Như vậy, việc chỉ xây dựng một mô hình thôi cũng là đã rất phức tạp rồi. Có một cách giúp số mô hình cần huấn luyện giảm đi nhiều, thậm chí chỉ một mô hình. Cách này có tên gọi chung là **regularization**.
**Regularization**, một cách cơ bản, là thay đổi mô hình một chút để tránh overfitting trong khi vẫn giữ được tính tổng quát của nó (tính tổng quát là tính mô tả được nhiều dữ liệu, trong cả tập training và test). Một cách cụ thể hơn, ta sẽ tìm cách di chuyển nghiệm của bài toán tối ưu hàm mất mát tới một điểm gần nó. Hướng di chuyển sẽ là hướng làm cho mô hình ít phức tạp hơn mặc dù giá trị của hàm mất mát có tăng lên một chút.
Một kỹ thuật rất đơn giản là **early stopping**.
Trong nhiều bài toán Machine Learning, chúng ta cần sử dụng các thuật toán lặp để tìm ra nghiệm, ví dụ như Gradient Descent. Nhìn chung, hàm mất mát giảm dần khi số vòng lặp tăng lên. **Early stopping** tức dừng thuật toán trước khi hàm mất mát đạt giá trị quá nhỏ, giúp tránh overfitting.
## Support Vector Machine
• Với bài toán **binary classification** mà 2 classes là **linearly separable**, có vô số các siêu mặt phẳng giúp phân biệt hai classes, tức mặt phân cách. Với mỗi mặt phân cách, ta có một classifier. Khoảng cách gần nhất từ 1 điểm dữ liệu tới mặt phân cách ấy được gọi là **margin** của classifier đó.
• **Support Vector Machine** là bài toán đi tìm mặt phân cách sao cho margin tìm được là lớn nhất, đồng nghĩa với việc các điểm dữ liệu an toàn nhất so với mặt phân cách.
• Bài toán tối ưu trong SVM là một bài toán lồi với hàm mục tiêu là **stricly convex**, nghiệm của bài toán này là duy nhất. Hơn nữa, bài toán tối ưu đó là một **Quadratic Programming (QP)**.
• Mặc dù có thể trực tiếp giải SVM qua bài toán tối ưu gốc này, thông thường người ta thường giải bài toán đối ngẫu. Bài toán đối ngẫu cũng là một QP nhưng nghiệm là sparse nên có những phương pháp giải hiệu quả hơn.
• Với các bài toán mà dữ liệu gần **linearly separable** hoặc **nonlinear separable**, có những cải tiền khác của SVM để thích nghi với dữ liệu đó.

Có một sự tương ứng thú vị giữa hai nhóm thuật toán phân lớp phổ biến nhất: **Neural Network** và **Support Vector Machine**. Chúng đều bắt đầu từ bài toán phân lớp với 2 **linearly separable classes**, tiếp theo đến 2 **almost linear separable classes**, đến bài toán có nhiều classes rồi các bài toán với biên không tuyến tính. Sự tương ứng được cho trong bảng dưới đây:

| Neural Networks | Support Vector Machine | Tính chất chung |
| -------- | -------- | -------- |
| PLA | Hard Margin SVM | Hai classes là linearly separable |
| Logistic Regression | Soft Margin SVM | Hai classes là gần linearly separable |
| Softmax Regression | Multi-class SVM | Bài toán phân loại nhiều classes (biên là tuyến tính) |
| Multi-layer Perceptron | Kernel SVM | Bài toán với dữ liệu không linearly separable |
Ý tưởng cơ bản của **Kernel SVM** và các phương pháp kernel nói chung là tìm một phép biến đổi sao cho dữ liệu ban đầu là không phân biệt tuyến tính được biến sang không gian mới. Ở không gian mới này, dữ liệu trở nên phân biệt tuyến tính.
### Xác suất
Câu nói nói cũng như không này là khơi nguồn cho rất nhiều các thuật toán Machine Learning có liên quan đến xác suất.

Cách giải quyết bài toán Machine Learning có thể viết gọn lại thành 3 bước chính: **Modeling**, **Learning** và **Inference**.

* **Modeling là việc đi tìm môt mô hình thích hợp cho bài toán cần giải quyết**. Với bài toán **Linear Regressio**n, modeling chính là việc mô hình dữ liệu đầu ra (output) như là tổ hợp tuyến tính của dữ liệu đầu vào (input). Với bài toán **k-means clustering**, modeling chính là việc quan sát ra rằng các clusters thường được mô tả bởi các centroids (hoặc centers) và mỗi điểm được xếp vào cluster tương ứng với centroid gần nó nhất. Trong bài toán **Support Vector Machine** cho dữ liệu linearly separable, modeling chính là bước quan sát thấy rằng đường thằng phân chia hai classes phải là đường làm cho margin đạt giá trị lớn nhất. Việc đi tìm ra mô hình nào phù hợp cho bài toán chính là bước **Modeling**.
* **Learning là bước tiến hành tối ưu các tham số của mô hình**. Mỗi model được mô hình bởi một bộ các tham số (parameters). Với **Linear Regression**, tham số mô hình là bộ vector hệ số và bias $(w,b)$. Với **K-means clustering**, tham số mô hình có thể được coi là các clusters. Với **Support Vector Machine**, tham số mô hình có thể là vector hệ số và bias mô tả đường thằng $(w,b)$. Việc đi tìm các tham số cho mô hình thường được thực hiện bằng việc giải một bài toán tối ưu. Quá trình giải bài toán tối ưu, hay chính là quá trình đi tìm tham số của mô hình, chính là quá trình Learning. Sau bước Learning này, chúng ta thu được các **trained parameters**.
* **Inference là bước dự đoán ouput của mô hình dựa trên các trained parameters**. Với **Linear Regression**, Inference chính là việc tính $y = \mathbf{w}^T\mathbf{x} + b$ dựa trên bộ các tham số đã được huấn luyện $(w,b)$. Với **K-means clustering**, việc inference chính là việc đi tìm centroid gần nhất. Với **Support Vector Machine**, Inference chính là việc xác định class của một dữ liệu mới dựa vào công thức $y = \text{sgn}(\mathbf{w}^T\mathbf{x} + b)$. So với hai bước Modeling và Learning, Inference thường đơn giản hơn.

#### Maximum Likelihood Estimation
Giả sử có các điểm dữ liệu $x_1,x_2,…,x_N$. Giả sử thêm rằng ta đã biết các điểm dữ liệu này tuân theo một phân phối nào đó được mô tả bởi bộ tham số $θ$.
**Maximum Likelihood Estimation** là việc đi tìm bộ tham số $θ$ sao cho xác suất sau đây đạt giá trị lớn nhất:
$~~~~~~~~~~~~~~~~~~~~~~~~\theta = \max_{\theta} p(\mathbf{x}_1, \dots, \mathbf{x}_N | \theta)$
Giả sử rằng ta đã biết mô hình rồi, và mô hình này được mô tả bởi bộ tham số $θ$. Thế thì, $p(x1|θ)$ chính là xác suất xảy ra sự kiện $x_1$ biết rằng mô hình là (được mô tả bởi) $θ$ (đây là một conditional probability). Và $p(x_1,…,x_N|θ)$ chính là xác suất để toàn bộ các sự kiện $x_1,x_2,…,x_N$ xảy ra đồng thời (nó là một joint probability), xác suất đồng thời này còn được gọi là **likelihood**. Ở đây, likelihood chính là hàm mục tiêu.
**Maximum Likelihood** chính là việc đi tìm bộ tham số $θ$ sao cho Likelihood là lớn nhất.
#### Independence Assumption và log-likelihood
Việc giải trực tiếp bài toán thường là phức tạp vì việc đi tìm mô hình xác suất đồng thời cho toàn bộ dữ liệu là ít khi khả thi. Một cách tiếp cận phổ biến là giả sử đơn giản rằng các điểm dữ liệu $x_n$ là độc lập với nhau, nếu biết tham số mô hình $θ$ (độc lập có điều kiện). Nói cách khác, ta xấp xỉ **likelihood**
$~~~~~~~~~~~~~~~~~~~~~~~~p(\mathbf{x}_1, \dots, \mathbf{x}_N | \theta) \approx \prod_{n = 1}^N p(\mathbf{x}_n |\theta)$
(Nhắc lại rằng hai sự kiện $x,y$ là độc lập nếu xác suất đồng thời của chúng bằng tích xác suất của từng sự kiện: $p(x,y)=p(x)p(y)$. Và khi là xác suất có điều kiện: $p(x,y|z)=p(x|z)p(y|z)$)
Lúc đó, bài toán có thể được giải quyết bằng cách giải bài toán tối ưu sau:
$~~~~~~~~~~~~~~~~~~~~~~~~\theta = \max_{\theta} \prod_{n=1}^N p(\mathbf{x}_n| \theta)$
Việc tối ưu hoá một tích thường phức tạp hơn việc tối ưu một tổng, vì vậy việc tối đa hàm mục tiêu thường được chuyển về việc tối đa loglog của hàm mục tiêu. Ôn lại một chút:
* log của một tích bằng tổng của các log.
* vì rằng log là một hàm đồng biến, một biểu thức sẽ là lớn nhất nếu log của nó là lớn nhất, và ngược lại.

Bài toán **Maximum Likelihood** được đưa về bài toán **Maximum Log-likelihood**:
$~~~~~~~~~~~~~~~~~~~~~~~~\theta = \max_{\theta} \sum_{n = 1}^N \log\left(p(\mathbf{x}_n | \theta)\right)$