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

Learn & Enjoy …

Posts Tagged ‘cực đại hóa khả năng’

« Những bài viết trước

Phân lớp bằng siêu phẳng (2) – Sử dụng các đại lượng thống kê (linear discriminant analysis)

Đăng bởi tqlong on Tháng tám 1, 2008

Ta đã thấy, Perceptron với thuật toán huấn luyện có thể chỉ ra bộ trọng số \displaystyle (w,b) phân tách được tập mẫu học. Tuy nhiên, kết quả này hoàn toàn không quan tâm đến phân bố xác suất của dữ liệu mà chỉ tìm cách phân lớp tuyến tính một tập mẫu học cho trước. Trong bài này, ta sẽ tìm hiểu một cách tiếp cận khác để huấn luyện một hàm phân lớp tuyến tính, trong đó có sử dụng các đại lượng thống kê của dữ liệu (ví dụ: giá trị kì vọng, ma trận hiệp phương sai).

Ta đã biết, nếu giả sử dữ liệu từ hai lớp \displaystyle \omega_1,\omega_2 đều tuân theo phân bố chuẩn với ma trận hiệp phương sai giống nhau, ranh giới phân lớp tối ưu là siêu phẳng với vectơ pháp tuyến (trọng số \displaystyle w) là

\displaystyle \widehat{w}_{\mathrm{LDA}} = \Sigma^{-1}(\mu_1 - \mu_2)

với \displaystyle \mu_1,\mu_2 là kì vọng, \displaystyle \Sigma là ma trận hiệp phương sai của cả 2 lớp đối tượng.

Hàm phân lớp tuyến tính của Fisher (Fisher’s linear discriminant – FLD)

Năm 1936, Fisher gợi ý sử dụng hàm phân lớp tuyến tính sao cho dữ liệu qua ánh xạ tuyến tính sẽ cực đại hóa tỉ số

\displaystyle S(w) = \frac{\sigma^2_{\mathrm{between}}}{\sigma^2_{\mathrm{within}}}= \frac{(\langle w,\mu_1-\mu_2\rangle)^2}{w^T(\Sigma_1+\Sigma_2)w}

trong đó:

  • Độ phân tách giữa hai lớp sau ánh xạ tuyến tính:

    \displaystyle \sigma^2_{\mathrm{between}} = (\langle w,\mu_1\rangle-\langle w,\mu_2\rangle)^2

    Ta muốn \displaystyle \sigma^2_{\mathrm{between}} càng lớn càng tốt (kì vọng của 2 lớp cách xa nhau).

  • Tổng phương sai của hai lớp sau ánh xạ tuyến tính:

    \displaystyle \sigma^2_{\mathrm{within}} = w^T\Sigma_1w+w^T\Sigma_2w

    Ta muốn \displaystyle \sigma^2_{\mathrm{within}} càng nhỏ càng tốt (phương sai của 2 lớp nhỏ).

Cực đại hóa \displaystyle S(w):

Đặt \displaystyle d = \mu_1-\mu_2,\Sigma = \Sigma_1+\Sigma_2, bài toán cực đại hóa \displaystyle S(w) tương đương với

\displaystyle \max_w \frac{\langle w,d\rangle^2 }{w^T\Sigma w}

Lấy gradient của \displaystyle S(w) theo \displaystyle w và đặt bằng \displaystyle {0} , ta được

\displaystyle \nabla S(w) = \frac{2\langle w,d\rangle (w^T\Sigma w) d - 2\langle w,d\rangle^2\Sigma w }{(w^T\Sigma w)^2} = 0 \displaystyle \Leftrightarrow \Sigma w = \frac{w^T\Sigma w}{\langle w,d\rangle}d

Để ý là \displaystyle S(\lambda w) = S(w), do đó, giá trị cực đại của \displaystyle S(w) đạt tại

\displaystyle \widehat{w}_{\mathrm{Fisher}} = \Sigma^{-1}d = ( \Sigma_1+\Sigma_2)^{-1}(\mu_1-\mu_2)

Nhận xét:

  1. Về bản chất, hàm tuyến tính của Fisher chiếu cả 2 lớp đối tượng lên một đường thẳng theo hướng \displaystyle w, và tìm hướng \displaystyle w sao cho ảnh của 2 lớp đối tượng trên đường thẳng này càng dễ phân biệt càng tốt.

    Hàm phân lớp tuyến tinh Fisher

    Hàm phân lớp tuyến tính Fisher (bên phải)

  2. Hướng \displaystyle w là hướng (1 chiều) dễ phân biệt 2 lớp đối tượng nhất. Đây là gợi ý dẫn đến các phương pháp giảm số chiều (dimension reduction) của dữ liệu nhưng vẫn đảm bảo khả năng phân lớp.
  3. Trong phân tích ở trên không thấy có vai trò của \displaystyle b do \displaystyle b không ảnh hưởng đến tỉ số \displaystyle S. Tuy nhiên, nếu ta giả sử dữ liệu tuân theo phân phối chuẩn thì sau ánh xạ tuyến tính \displaystyle x\rightarrow \langle w,x\rangle , ta phải phân lớp trên trục số thực với 2 lớp có kì vọng và phương sai

    \displaystyle m_1 = \langle w,\mu_1\rangle,\sigma_1^2 = w^T\Sigma_1 w
    \displaystyle m_2 = \langle w,\mu_2\rangle, \sigma_2^2 = w^T\Sigma_2 w

    và có thể áp dụng cách tìm ngưỡng \displaystyle b đã biết ở ví dụ trước.

  4. Có thể xác định \displaystyle \mu_1,\mu_2,\Sigma_1,\Sigma_2 từ tập các mẫu học bằng phương pháp cực đại hóa khả năng (MLE).

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , | Leave a Comment »

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

Đăng bởi tqlong 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 là

\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 là

\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) là 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 và

\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 là

\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 và \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 và \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).

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , , , , , , , , , , | Leave a Comment »

« Những bài viết trước