Cho tới thời điểm này chúng ta đã có 1 số khái niệm và phương pháp căn bản của xác suất thống kê. Vậy giờ chúng ta áp dụng nó thể nào cho các bài toán học máy?

Bài viết này sẽ chỉ ra lý thuyết đằng sau bài toán phân loại để có thể hiểu sâu hơn về cách áp dụng lý thuyết xác suất thống kê cho các bài toán học máy.

Mục lục

1. Bài toán phân loại

Trong học máy, bài toán phân loại là bài toán gắn nhãn cho mỗi đầu vào. Do các nhãn này là biết trước nên ta có thể biểu diễn chúng qua một tập hợp $ Y $ hữu hạn. Còn các đầu vào sẽ được coi là một tập hợp $ X $. Như vậy, thực chất bài toán dãn nhãn là đi tìm $ y \in Y $ sao cho xác suất của nó đối với 1 đầu vào $ x \in X $ là lớn nhất. Tập dữ liệu huấn luyện của ta là một tập các cặp $ (x, y) $ đã biết trước.

Về mặt toán học, ta có thể biểu diễn mỗi cặp $(x, y)$ bằng một hàm số dự đoán: $\hat y = f(x)$. Như vậy bài toán của ta có thể biểu diễn thành dạng: $\hat{y}=f(x)=\underset{y}{\mathrm{argmax}}\hat{P}(Y = y|X)$.

$\underset{y}{\mathrm{argmax}}$ là hàm trả ra giá trị của tham số $y$ mà tại đó khiến hàm đạt được giá trị lớn nhất.

Lưu ý rằng mỗi nhãn $ y \in Y \subset \mathbb{N} $ là một nhãn riêng biệt và ta quy ước nó thuộc trường số tự nhiên. Còn mỗi đầu vào $ x \in X \subset \mathbb{R^m} $ là một véc-tơ tương ứng với số thuộc tính của $ x $, hay nói cách khác nếu mỗi đầu vào có $m$ thuộc tính thì $x$ là một véc-tơ $m$ chiều với mỗi phần tử đại diện cho 1 thuộc tính.

2. Giải thuật Naive Bayes

2.1. Tóm tắt giải thuật

Giải thuật Naive Bayes được trình bày như sau:

  • Huấn luyện
    Mục tiêu của quá trình huấn luyện là đánh giá xác suất $ P(Y) $ và $ P(X_i|Y) $ cho mọi thuộc tính $ i=\overline{1, m} $. Để làm việc này, ta có thể sử dụng 1 trong 2 cách đánh giá sau:
    • MLE (Maximum Likelihood Estimation) $$ \hat{p}(X_i=x_i|Y=y) = \frac{(\text{training examples where Xi = xi and Y = y})}{(\text{training examples where Y = y})} $$
    • Laplace MAP (Maximum A Posteriori probability) $$ \hat{p}(X_i=x_i|Y=y) = \frac{(\text{training examples where Xi = xi and Y = y}) + 1}{(\text{training examples where Y = y}) + 2} $$
  • Dự đoán
    Với mỗi đầu vào $ x $, ta đánh giá $ y $ như sau: $$ \begin{aligned} \hat{y} &= \underset{y}{\mathrm{argmax}}\hat{P}(X|Y)\hat{P}(Y) \cr \ &= \underset{y}{\mathrm{argmax}}\prod_{i=1}^m\hat{p}(X_i=x_i|Y=y)\hat{p}(Y=y) \cr \ &= \underset{y}{\mathrm{argmax}}\sum_{i=1}^m\log\hat{p}(X_i=x_i|Y=y) + \log\hat{p}(Y=y) \end{aligned} $$

Ở đây, ta lấy phiên bản $\log$ nhằm tránh việc triệt tiêu số khi nhân vì xác suất luôn nằm trong khoảng $[0, 1]$ nên khi nhân vào sẽ ra số rất bé dẫn tới chuyện triệt tiêu mất số khi tính toán. Tuy nhiên nếu số lượng tập huấn luyện và thuộc tính đầu vào là ít, ta vẫn có thể sử dụng được phiên bản nhân xác suất.

2.2. Lý thuyết

Về mặt lý thuyết ta có thể giải bài toán phân loại bằng cách sử dụng phương pháp vét cạn. Để làm như vậy ta có thể tối ưu xác suất kết hợp $\hat{P}(Y, X)$. Vì sao ta có thể nói như vậy?

Quay lại lý thuyết của bài toán phân loại rằng ta cần tìm $y$ sao cho: $$\hat{y} = f(x) = \underset{y}{\mathrm{argmax}}\hat{P}(Y = y|X)$$. Do đây là xác suất có điều kiện nên: $$\hat{y} = \underset{y}{\mathrm{argmax}}\frac{\hat{P}(X,Y)}{\hat{P}(X)}$$ Vì $\hat{P}(X)$ là hằng số do $X$ là tập đã biết trước, nên ta có: $$\hat{y} = \underset{y}{\mathrm{argmax}}\hat{P}(X,Y)$$

Vì lượng thuộc tính của $x \in X$ là $m$ nên khi tính xác suất hợp này ta có tới $2^m$ tham số! Tức không gian nhớ cần để thực hiện phương pháp này là $\Theta({2^m})$, thật khủng khiếp phải không?

Tuy nhiên bằng giả thiết Naive Bayes, ta có thể giảm không gian này xuống còn $\Theta{(m)}$. Giả thuyết này cho rằng mỗi thuộc tính của $x$ là độc lập đối với mỗi nhãn $y$ bất kì. Giải thuyết này là sai nhưng cực kì hữu ích và vẫn thực hiện tốt việc phân loại trong rất nhiều bài toán thực tế. Với giả thuyết này ta sẽ có: $$ \begin{aligned} \hat{y} &= \underset{y}{\mathrm{argmax}}\hat{P}(X,Y) \cr \ &= \underset{y}{\mathrm{argmax}}\hat{P}(X|Y)\hat{P}(Y) \cr \ &= \underset{y}{\mathrm{argmax}}\prod_{i=1}^m\hat{p}(X_i=x_i|Y=y)\hat{p}(Y=y) \cr \end{aligned} $$

Bằng ước lượng kiểu này mà giải thuật của ta có thể chạy nhanh và ổn định cho cả 2 việc huấn luyện và dự đoán. Naive Bayes là một dạng đơn giản của mô hình đồ họa xác suất (Probabilistic Graphical Models) trong lĩnh vực học máy. Với bài toán dạng này, ta có thể vẽ một đồ thị thể hiện mối tương quan giữa các biến từ đó đưa ra giả thuyết nhằm đánh giá, dự đoán bằng phép kết hợp xác suất có điều kiện.

3. Giải thuật Logistic Regression

3.1. Tóm tắt giải thuật

Logistic Regression là một giải thuật phân loại bằng cách học một hàm ước lượng xác suất $P(X|Y)$. Với giả thuyết trọng tâm rằng xác suất này có thể biểu diễn bằng một hàm $\mathrm{sigmoid}$ với tham số là một kết hợp tuyến tính của các thuộc tính đầu vào. Việc hiểu giải thuật này là rất cần thiết vì nó là bước cơ bản nhất của một mạng trí tuệ nhân tạo, nên bạn đừng vội vàng bỏ qua lý thuyết đằng sau nó nhé.

Kết hợp tuyết tính có thể hiểu đơn giản là một hàm tuyến tính (linear function) hay còn gọi là hàm bậc nhất.

Về mặt toán học, với mỗi điểm dữ liệu huấn luyện (x, y), Logistic Regression giả sử rằng: $$P(Y=1|X=x) \triangleq \sigma(z) ~~~, \text{where } z = \theta_0 + \sum_{i=1}^m\theta_ix_i $$

Đặt $x_0 = 1$, giả thuyết này có thể được viết dưới các dạng tương đương sau: $$ \begin{aligned} P(Y=1|X=x) &= \sigma(\theta^\intercal x) \cr P(Y=0|X=x) &= 1 - \sigma(\theta^\intercal x) \end{aligned} $$

Như vậy bài toán của ta lúc này sẽ là đi tìm các $\theta$ sao cho xác suất cho tập dữ liệu của ta là lớn nhất có thể.

Tương tự như giải thuật Naive Bayes, ta cũng sẽ sử dụng ước lượng theo hàm $\log$ để tìm $\theta$ (Log Likelihood) như sau:

$$LL(\theta) = \sum_{i=1}^n y^{(i)}\log\sigma(\theta^\intercal x) + (1-y^{(i)})\log\big(1-\sigma(\theta^\intercal x)\big) $$

Về mặt toán học để tìm cực đại của hàm này là không đơn giản chút nào, nhưng ta có thể thực hiện bằng máy tính bằng phương pháp leo đồi - Gradient Ascent Optimization. Ý tưởng đằng sau giải thuật này là nếu ta tiến từng bước nhỏ theo hướng của gradient thì ta sẽ đạt được cực đại cục bộ. Nhưng trong bài toán Logistic Regression ta có thể chứng minh rằng cực đại này chính là cực đại toàn cục. Mỗi bước tiến nhỏ như vậy được được dịch chuyển bởi 1 độ học $ \eta $ đủ nhỏ để ta không bị vượt quá giá trị cực trị nhưng cũng không quá nhỏ khiến giải thuật ta bị chậm đi. Tại mỗi bước đó, ta cập nhập các tham số $\theta$ như sau:

$$\theta_j^\text{new} = \theta_j^\text{old} + \eta\frac{\partial LL(\theta^\text{old})}{\partial\theta_j^\text{old}}$$

Do gradient của $LL(\theta)$ theo mỗi véc-tơ $\theta_j$ là $\sum_{i=1}^n\Big(y^{(i)}-\sigma(\theta^\intercal x)\Big)x_j^{(i)}$, nên ta có:

$$\theta_j^\text{new} = \theta_j^\text{old} + \eta\sum_{i=1}^n\Big(y^{(i)}-\sigma(\theta^\intercal x)\Big)x_j^{(i)}$$

Giải thuật tối ưu hoàn chỉnh có thể viết dưới dạng giả mã như sau:

// Init theta
for i = 0 to m
    theta_j := 0
// optimize
do (many times)
    // calc gradient
    for j = 0 to m
        gradient[j] := 0
    for each training data (x, y)
        for j = 0 to m
            z := transpose(theta) ・ x
            gradient[j] += x_j(y - sigmoid(z))
    // gradient ascent
    for j = 0 to m
        theta_j += eta * gradient[j]

3.2. Lý thuyết

Để giải quyết bài toán phân loại này ta lại sử dụng phương pháp đánh giá MLE (Maximum Likelihood Estimation) bằng 2 bước:

  • Biểu diễn hàm tối ưu dạng hàm log-likelihood của $\theta$
  • Tìm $\theta$ để hàm này đạt cực đại

Với giả thuyết ta chỉ có 2 nhãn $y = 0$ hoặc $y=1$, ta có thể sử dụng hàm xác suất Béc-nu-li $Y \sim \mathrm{Bern}(p)$ để ước lượng xác suất của mỗi nhãn như sau:

$$P(Y=y|X=x) = p^y (1-p)^{(1-y)} $$

Trong đó: $p = \sigma(\theta^\intercal x)$. Từ đây ta có tích xác suất hợp của cả tập dữ liệu như sau:

$$ \begin{aligned} L(\theta) &= \prod_{i=1}^n P(Y=y^{(i)}|X=x^{(i)}) \cr \ &= \sigma(\theta^\intercal x)^{y^{(i)}} \big(1-\sigma(\theta^\intercal x)\big)^{1-y^{(i)}} \end{aligned} $$

Giờ ta lấy $\log$ để phân rã phép nhân để có hàm Log-Likelihood như sau:

$$LL(\theta) = \sum_{i=1}^n y^{(i)}\log\sigma(\theta^\intercal x)+(1-y^{(i)})\log(1-\sigma(\theta^\intercal x))$$

Bước tiếp theo là tìm $\theta$ để hàm này đạt cực đại bằng phương pháp Gradient Ascent đề cập ở trên. Để tìm được gradient đối với mỗi $\theta_j$, ta có thể sử dụng phương pháp đạo hàm của hàm hợp (quy tắc chuỗi) như sau:

$$\frac{\partial LL(\theta)}{\partial \theta_j} = \frac{\partial LL(\theta)}{\partial p}\frac{\partial p}{\partial z}\frac{\partial z}{\partial \theta_j}$$

Trong đó: $z=\theta^\intercal x$ và $p=\sigma(z)$. Giờ sẽ tính đạo hàm của từng thành phần rồi sau ghép lại với nhau.

  • $\displaystyle\frac{\partial LL(\theta)}{\partial p}$
    Ta có $LL(\theta)=y\log p + (1-y)\log(1-p)$ nên đạo hàm sẽ là: $$ \begin{aligned} \frac{\partial LL(\theta)}{\partial p} &= \frac{y}{p}-\frac{1-y}{1-p} \cr \ &= \frac{y-p}{p(1-p)} \end{aligned} $$

  • $\displaystyle\frac{\partial p}{\partial z}$
    Ta có $p=\sigma(z)$ nên đạo hàm sẽ là: $$ \begin{aligned} \frac{\partial p}{\partial z} &= \sigma(z)(1-\sigma(z)) \cr \ &= p(1-p) \end{aligned} $$

  • $\displaystyle\frac{\partial z}{\partial \theta_j}$
    Ta có $z=\theta^\intercal x$ nên đạo hàm sẽ là: $$\frac{\partial z}{\partial \theta_j} = x_j$$

Kết hợp chúng lại với nhau ta sẽ được: $$ \begin{aligned} \frac{\partial LL(\theta)}{\partial \theta_j} &= \frac{\partial LL(\theta)}{\partial p}\frac{\partial p}{\partial z}\frac{\partial z}{\partial \theta_j} \cr \ &= \frac{y-p}{p(1-p)} p(1-p) x_j \cr \ &= (y-p) x_j \cr \ &= (y - \sigma(\theta^\intercal x)) x_j \end{aligned} $$

Như vậy gradient của hàm Log-Likelihood trên là: $$\frac{\partial LL(\theta)}{\partial \theta_j} = (y - \sigma(\theta^\intercal x)) x_j$$

Với đạo hàm như vậy ta có thể thực hiện được hàm thuật toán leo đồi như trên rồi.

4. Kết luận

Qua bài toán đơn giản này hi vọng bạn có được cái nhìn về cách áp dụng xác suất thống kê cho các bài toán học máy cũng như tầm quan trọng của nó trong việc xây dựng các thuật toán học máy.