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

Learn & Enjoy …

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)

Posted by Trần Quốc Long 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).

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: