CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Các khái niệm trong Học máy (Machine Learning) (7) – Một số ví dụ

Posted by Trần Quốc Long on Tháng Bảy 30, 2008

Ước lượng tham số của phân phối chuẩn (normal distribution): Ở bài thứ 3, ta đã thấy một ví dụ sử dụng công thức Bayes để ước lượng xác suất của tham số. Trong ví dụ này, ta sẽ thử sử dụng nguyên tắc cực đại hóa khả năng (maximum likelihood estimation – MLE) để ước lượng tham số.

Ví dụ 1. Giả sử dữ liệu \displaystyle D=\{x_1,x_2,\ldots,x_N\} được lấy từ phân phối chuẩn \displaystyle \mathcal{N}(\mu,1). Hãy xác định \displaystyle \mu.

Giải: Giá trị của \displaystyle \mu phải cực đại hóa khả năng (likelihood) của dữ liệu

\displaystyle p(D|\mu) = \prod_{i=1}^N \left(\frac{1}{\sqrt{2\pi}}\exp \left\{-\frac{1}{2}(x_i-\mu)^2 \right\}\right)

Lấy logarit cơ số tự nhiên cả hai vế và loại bỏ đi hằng số, việc cực đại hóa \displaystyle p(D|\mu) tương đương với việc cực đại hóa hàm log-likelihood sau

\displaystyle L(\mu) = -\frac{1}{2}\sum_{i=1}^N (x_i-\mu)^2

Lấy đạo hàm \displaystyle L'(\mu) và đặt bằng \displaystyle {0} rồi giải ra ta được ước lượng MLE của \displaystyle \mu

\displaystyle \widehat{\mu}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N x_i = \overline{x}

Ví dụ 2. Giả sử dữ liệu \displaystyle D=\{x_1,x_2,\ldots,x_N\} được lấy từ phân phối chuẩn \displaystyle \mathcal{N}(\mu,\sigma^2). Hãy xác định \displaystyle \mu, \sigma^2=v.

Giải: Tương tự như trên hàm log-likelihood là:

\displaystyle L(\mu,v) = -\frac{N}{2}\ln v - \frac{1}{2v} \sum_{i=1}^N (x_i-\mu)^2

Đầu tiên, cực đại hóa \displaystyle L(\mu,v) theo \displaystyle \mu, ta được

\displaystyle \widehat{\mu}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N x_i = \overline{x}

\displaystyle \overline{L}(v) = \max_\mu L(\mu,v) = L(\overline{x},v) = -\frac{N}{2}\ln v - \frac{1}{2v} \sum_{i=1}^N (x_i-\overline{x})^2

Tiếp tục cực đại hóa \displaystyle \overline{L}(v) theo \displaystyle v ta có

\displaystyle \overline{L'}(v) = -\frac{N}{2v}+\frac{1}{2v^2} \sum_{i=1}^N (x_i-\overline{x})^2 = 0

\displaystyle \widehat{v}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N (x_i-\overline{x})^2

Lưu ý:

  1. Qua 2 ví dụ trên, ta thấy \displaystyle \mu,\sigma^2 xác định qua nguyên tắc cực đại hóa khả năng chính là các đại lượng trung bình cộng của dữ liệu và trung bình bình phương sai số.
  2. Đối với dữ liệu nhiều chiều, \displaystyle \mathbb{R}^n\ni x\sim \mathcal{N}(\mu,\Sigma), với cách làm tương tự (có phức tạp hơn 1 chút), ta cũng có thể tính được

    \displaystyle \widehat{\mu}_{\mathrm{MLE}} = \overline{x}
    \displaystyle \widehat{\Sigma}_{\mathrm{MLE}} = \frac{1}{N} \sum_{i=1}^N (x_i-\overline{x})(x_i-\overline{x})^T

Ví dụ 3. Giả sử có hai lớp đối tượng \displaystyle \omega_1,\omega_2 , ta biết rằng

\displaystyle p(x|\omega_1) = \mathcal{N}(\mu_1,\sigma^2)

\displaystyle p(x|\omega_2) = \mathcal{N}(\mu_2,\sigma^2)

Nghĩa là phân bố của hai lớp đối tượng đều là phân phối chuẩn, có phương sai giống nhau. Đồng thời giả sử \displaystyle P(\omega_1)=P(\omega_2) = 0.5. Hãy xây dựng luật phân lớp tối ưu và ước lượng xác suất lỗi.

Giải: Do \displaystyle P(\omega_1)=P(\omega_2) = 0.5 nên luật phân lớp tối ưu

\displaystyle x\in\omega_1\Leftrightarrow p(x|\omega_1) \geq p(x|\omega_2)

\displaystyle x\in\omega_1\Leftrightarrow \frac{1}{\sqrt{2\pi}\sigma}\exp \left\{-\frac{1}{2}\frac{(x_i-\mu_1)^2}{\sigma^2} \right\} \geq \frac{1}{\sqrt{2\pi}\sigma}\exp \left\{-\frac{1}{2}\frac{(x_i-\mu_2)^2}{\sigma^2} \right\}

Lấy logarith cơ số tự nhiên cả hai vế của bất đẳng thức rồi loại bỏ hằng số chung ta được

\displaystyle x\in\omega_1\Leftrightarrow (x-\mu_1)^2 \leq (x-\mu_2)^2

\displaystyle x\in\omega_1\Leftrightarrow |x-\mu_1| \leq |x-\mu_2|

Tức là nếu \displaystyle x ở gần \displaystyle \mu_1 hơn thì sẽ được phân vào lớp \displaystyle \omega_1 và ngược lại. Hoặc nếu \displaystyle \mu_1<\mu_2, ta có thể viết

\displaystyle x\in\omega_1\Leftrightarrow x\leq \frac{\mu_1+\mu_2}{2}

Để tính xác suất lỗi (generalization error), ta có

\displaystyle P\{\mathrm{error}\} = P\left\{X> \left.\frac{\mu_1+\mu_2}{2}\right|\omega_1\right\}P(\omega_1)+P\left\{\left.X\leq \frac{\mu_1+\mu_2}{2}\right|\omega_2\right\}P(\omega_2)

Do \displaystyle P(\omega_1)=P(\omega_2) = 0.5 và tính đối xứng của các phân bố ta có

\displaystyle P\{\mathrm{error}\} = P\left\{\left.X\leq \frac{\mu_1+\mu_2}{2}\right|\omega_2\right\}=\mathbf{\Phi}\left(\frac{\mu_1-\mu_2}{2\sigma}\right)

Trong đó \displaystyle \mathbf{\Phi}(x)hàm phân bố xác suất (cummulative distribution function) của phân bố chuẩn \displaystyle \mathcal{N}(0,1).

Ví dụ 4. Xét trường hợp tổng quát hơn \displaystyle x\in \mathbb{R}^n

\displaystyle p(x|\omega_1) = \mathcal{N}(\mu_1,\Sigma_1) = \frac{1}{(2\pi)^{n/2}|\Sigma_1|^{1/2}}\exp\left\{-\frac{1}{2}(x-\mu_1)^T\Sigma_1^{-1}(x-\mu_1)\right\}

\displaystyle p(x|\omega_2) = \mathcal{N}(\mu_2,\Sigma_2) = \frac{1}{(2\pi)^{n/2}|\Sigma_2|^{1/2}}\exp\left\{-\frac{1}{2}(x-\mu_2)^T\Sigma_2^{-1}(x-\mu_2)\right\}

Điều kiện để phân \displaystyle x vào lớp \displaystyle \omega_1

\displaystyle p(x|\omega_1)P(\omega_1)\geq p(x|\omega_2)P(\omega_2)

Lấy logarit cơ số tự nhiên cả 2 vế, ta có

\displaystyle \ln P(\omega_1)-\frac{1}{2}\ln |\Sigma_1|-\frac{1}{2} (x-\mu_1)^T\Sigma_1^{-1}(x-\mu_1)\displaystyle \geq \ln P(\omega_2)-\frac{1}{2}\ln |\Sigma_2|-\frac{1}{2} (x-\mu_2)^T\Sigma_2^{-1}(x-\mu_2)

Như vậy, ở trường hợp phân phối chuẩn tổng quát, đường phân ranh giới tối ưu giữa 2 lớp là một đường cong bậc 2. Nó có thể là đường thẳng, elipsoid, hyperbol hay parabol tùy thuộc vào \displaystyle \Sigma_1\displaystyle \Sigma_2. Ta xét một số trường hợp đơn giản:

  • \displaystyle \Sigma_1=\Sigma_2=\sigma^2 I_n: khi đó bất đẳng thức trên tương đương với

    \displaystyle \|x-\mu_1\|^2-2\sigma^2\ln P(\omega_1)  \leq \|x-\mu_2\|^2-2\sigma^2\ln P(\omega_2)

    Nghĩa là quyết định phân lớp tương đương với việc so sánh khoảng cách Euclid (Euclidean distance) từ \displaystyle x đến kì vọng của 2 phân phối. Trường hợp này, đường ranh giới là một đường thẳng vuông góc với đường thẳng nối \displaystyle \mu_1\displaystyle \mu_2.

  • \displaystyle \Sigma_1=\Sigma_2=K^{-1}: khi đó bất đẳng thức tương đương với

    \displaystyle (x-\mu_1)^T K (x-\mu_1) -\ln P(\omega_1) \leq (x-\mu_2)^T K (x-\mu_2) -\ln P(\omega_2)

    Đại lượng \displaystyle \sqrt{(x-\mu_1)^T K (x-\mu_1)} gọi là khoảng cách Mahalanobis (Mahalanobis distance) tương ứng với ma trận \displaystyle K. Tiếp tục đơn giản bất đẳng thức trên ta có

    \displaystyle -2\mu_1^TKx +\mu_1^TK\mu_1 - \ln P(\omega_1) \leq -2\mu_2^TKx +\mu_2^TK\mu_2 - \ln P(\omega_2)
    \displaystyle 2(\mu_1-\mu_2)^TKx - \mu_1^TK\mu_1+\mu_2^TK\mu_2+ \ln P(\omega_1) - \ln P(\omega_2)\geq 0

    Nghĩa là đường phân ranh giới giữa 2 lớp là một siêu phẳng có véctơ pháp tuyến \displaystyle K(\mu_1-\mu_2).

Lưu ý:

  1. Do ma trận \displaystyle K=\Sigma_1^{-1} là ma trận xác định dương nên dễ thấy các tính chất sau

    \displaystyle d_K(x,y) = \sqrt{(x-y)^T K (x-y)}\geq 0,\forall x,y\in \mathbb{R}^n
    \displaystyle d_K(x,y) = 0 \Leftrightarrow x=y
    \displaystyle d_K(x,y) = d_K(y,x)
    \displaystyle d_K(x,y)+d_K(y,z) \geq d_K(x,z) (bất đẳng thức tam giác)

    Tức là khoảng cách Mahalanobis thỏa mãn các tính chất cần có của khoảng cách trong không gian metric.

  2. Với giả sử phân phối của 2 lớp là phân phối chuẩn với ma trận hiệp phương sai \displaystyle \Sigma giống nhau, theo ví dụ trên, đường phân giới tối ưu là một siêu phẳng. Vì vậy một số phương pháp phân lớp trực tiếp tìm một siêu phẳng để phân tách 2 lớp (linear discriminant analysis – LDA). Trong các bài sau, ta sẽ thấy đây là một phương pháp phân lớp rất mạnh (về độ chính xác/tốc độ học/tốc độ phân lớp), đặc biệt khi ta có thể biến đổi không gian đặc trưng lên không gian nhiều chiều hơn (tức là tạo một ánh xạ \displaystyle \phi:\mathbb{R}^n\rightarrow \mathbb{R}^D với \displaystyle D\gg n và tiến hành phân lớp bằng siêu phẳng trên \displaystyle \mathbb{R}^D). Đây cũng là ý tưởng cơ bản của các phương pháp sử dụng vectơ hỗ trợ (Support Vector Machines) do giáo sư Vapnik đề xuất (từ “hỗ trợ” ở đây có nghĩa là siêu phẳng được một số véctơ/điểm dữ liệu “đỡ” lấy).

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: