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) (6) – Ước lượng hàm phân lớp, nguyên lý tối thiểu rủi ro

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

Bài toán phân lớp còn có thể giải quyết bằng cách tìm hàm phân lớp

\displaystyle f:\mathbb{R}^n\rightarrow \{1,\ldots,K\}.

Cũng như phương pháp ước lượng hàm mật độ, ta cũng có các vấn đề sau:

  1. Xây dựng thuật toán tìm hàm phân lớp dựa vào dữ liệu \displaystyle D=\{(x_1,y_1),\ldots, (x_N,y_N)\} (trường hợp học có giám sát) hoặc \displaystyle D = \{x_1,\ldots,x_N\} (học không có giám sát), đồng thời nếu có thể, tìm cách tận dụng được các kiến thức chuyên ngành (field knowledge).
  2. Xây dựng cơ chế để ước lượng xác suất lỗi (generalization error) hoặc giá trị kì vọng của rủi ro (expected risk) khi phân lớp nhầm.

Để đơn giản, ta xét trường hợp học có giám sát, dữ liệu gồm các mẫu học \displaystyle D=\{(x_1,y_1),\ldots, (x_N,y_N)\}, trong đó \displaystyle x_i\in \mathbb{R}^n, y_i\in \{1,\ldots,K\}. Giả sử có hàm \displaystyle L(i, j) chỉ ra rủi ro/giá phải trả khi đoán nhầm đối tượng thuộc lớp \displaystyle \omega_i thành đối tượng của lớp \displaystyle \omega_j. Như vậy, rủi ro khi phân lớp đối tượng \displaystyle x thuộc lớp \displaystyle \omega_y bằng hàm phân lớp \displaystyle f(x)\displaystyle L(f(x), y). Vậy, giá trị kì vọng của rủi ro, xét trên toàn bộ không gian mẫu học và các lớp đối tượng, là

\displaystyle R = \sum_{y=1}^K\left(\int_{\mathbb{R}^n}L(f(x),y)p(x|Y=y)dx\right)P\{Y=y\}

Nếu ta đặt \displaystyle z = (x,y) thì công thức trên có thể chuyển thành

\displaystyle R(f) = \int_{z\in \mathbb{R}^n\times\{1,\ldots,K\}} R(z) p(z)dz = E\left[R_f(z)\right]

trong đó \displaystyle R_f(z) = L(f(x),y), p(z) = p(x|Y=y)P\{Y=y\}. Nghĩa là, kì vọng của rủi ro là kì vọng của hàm \displaystyle R_f(z) trong không gian xác suất \displaystyle \mathbb{R}^n\times\{1,\ldots,K\} với hàm mật độ \displaystyle p(z).

Khi thiết kế một thuật toán tìm hàm phân lớp, rõ ràng ta muốn tìm hàm \displaystyle f^*(x) sao cho

\displaystyle R^* = R(f^*) = \min_f R(f).

Tuy ta không thể tính \displaystyle R = E\left[R(z)\right] vì không biết \displaystyle p(z) nhưng ta có thể tính giá trị rủi ro thực nghiệm (empirical risk) bằng cách lấy trung bình cộng rủi ro trên các mẫu học \displaystyle z_i = (x_i, y_i), i=1,\ldots,N:

\displaystyle R_N^{\mathrm{emp}}(f)=\frac{1}{N}\sum_{i=1}^NR_f(z_i)

Như vậy, thay vì tối thiểu hóa giá trị kì vọng của rủi ro, ta tối thiểu hóa giá trị thực nghiệm trên. Nguyên lý này gọi là nguyên lý tối thiểu rủi ro thực nghiệm (empirical risk minimization – ERM principle). Theo nguyên lý này, ta phải tìm hàm \displaystyle f^* sao cho

\displaystyle R_N^*=R_N^{\mathrm{emp}}(f^*)=\min_f R_N^{\mathrm{emp}}(f)

Tương tự như việc ước lượng mật độ xác suất có điều kiện, nguyên lý tối thiểu hóa rủi ro thực nghiệm chỉ nên áp dụng nếu có thể ước lượng:

  1. Liệu \displaystyle R_N^*\displaystyle R(f^*) có hội tụ đến \displaystyle R^* (theo xác suất) khi \displaystyle N\rightarrow \infty hay không?

    \displaystyle P\{\lim_{N\rightarrow \infty} |R_N^*-R^*|=0\}=1
    \displaystyle P\{\lim_{N\rightarrow \infty} |R(f^*)-R^*|=0\}=1

    Tính chất này gọi là hội tụ chắc (consistent).

  2. Tốc độ hội tụ của \displaystyle R_N^*\displaystyle R(f^*) đến \displaystyle R^*: tức là với \displaystyle N hữu hạn, có thể ước lượng (theo xác suất) sai số \displaystyle |R_N^*-R^*| hay \displaystyle |R(f^*)-R^*| hay không?

    \displaystyle P\{|R_N^*-R^*|<\epsilon\}
    \displaystyle P\{|R(f^*)-R^*|<\epsilon\}

Lưu ý: Các kí hiệu

  • \displaystyle R^*: giá trị kì vọng rủi ro tối ưu (trên toàn bộ không gian hàm phân lớp và toàn bộ không gian mẫu).

    \displaystyle R^* = \min_f R(f).

  • \displaystyle R_N^*: giá trị rủi ro thực nghiệm tối thiểu (trên toàn bộ không gian hàm phân lớp với tập mẫu học cố định \displaystyle D=\{z_i=(x_i,y_i)\}_{i=1}^N).

    \displaystyle R_N^*=\min_f R_N^{\mathrm{emp}}(f)

  • \displaystyle R(f^*): giá trị kì vọng rủi ro khi sử dụng hàm phân lớp \displaystyle f^* tìm được nhờ tối thiểu hóa giá trị rủi ro thực nghiệm. Đây chính là xác suất lỗi (generalization error) khi ta sử dụng hàm phân lớp

    \displaystyle f^*=\arg\min_f R_N^{\mathrm{emp}}(f)

    Để ý là \displaystyle R(f^*)\geq R^*.

Do tập tất cả các hàm phân lớp có thể có quá lớn, người ta thường giới hạn việc tìm kiếm \displaystyle f trong một lớp hàm \displaystyle \mathcal{F} nào đó. Việc xác định \displaystyle \mathcal{F} dựa vào các kiến thức chuyên ngành hoặc áp đặt chủ quan của người thiết kế thuật toán học máy. Như vậy ta phải xác định

\displaystyle f^* = \arg\min_{f\in \mathcal{F}} R_N^{\mathrm{emp}}(f)
\displaystyle R_N^* = R_N^{\mathrm{emp}}(f^*)

Một lần nữa, Vapnik và Chervonenkis, bằng lý thuyết VC, chứng minh được rằng với một số điều kiện trên tập các hàm rủi ro \displaystyle \{R_f(z)|f\in \mathcal{F}\} ta có

\displaystyle P\{\lim_{N\rightarrow \infty} |R_N^*-R^*|=0\}=1
\displaystyle P\{\lim_{N\rightarrow \infty} |R(f^*)-R^*|=0\}=1

Tức là \displaystyle R_N^*\displaystyle R(f^*) hội tụ chắc đến \displaystyle R^*. Hơn nữa, nếu số chiều VC của tập hàm trên hữu hạn, có thể tính được tốc độ hội tụ của hai đại lượng này đến \displaystyle R^* tương tự như bất đẳng thức Dvoretzky–Kiefer–Wolfowitz.

Ví dụ:

  1. Trung bình bình phương sai số tối thiểu (least mean square error): Khi hàm \displaystyle L(f(x),y) có dạng

    \displaystyle R_f(z) = L(f(x),y) = \left[f(x)-y\right]^2

    Việc tối thiểu hóa rủi ro thực nghiệm \displaystyle R_N^{\mathrm{emp}}(f) = \frac{1}{N} \sum_{i=1}^N R_f(z_i) gọi là tối thiểu trung bình bình phương sai số. Đây là bài toán được phát triển khá đầy đủ, có mặt ở rất nhiều phương pháp xác định mô hình (model identification).

  2. Một điểm thú vị khác là việc ước lượng mật độ xác suất cũng có thể viết theo nguyên tắc tối thiểu rủi ro thực nghiệm. Nếu ta muốn tối thiểu hóa khoảng cách Kullback-Leibler

    \displaystyle D_{\mathrm{KL}}(p,q)=\int_{\mathbb{R}^n}\ln \frac{p(x)}{q(x)}p(x)dx
    \displaystyle p^*=\arg\min_q D_{\mathrm{KL}}(p,q)

    Dễ thấy rằng

    \displaystyle p^*=\arg\min_q \int_{\mathbb{R}^n}-\ln[q(x)]p(x)dx = \arg\min_q E\{-\ln[q(x)]\},

    tức là có thể tìm \displaystyle p^* bằng cách tối thiểu hóa giá trị rủi ro thực nghiệm

    \displaystyle R_N^{\mathrm{emp}}(q) = \frac{1}{N}\sum_{i=1}^N -\ln[q(z_i)]

    Do

    \displaystyle \sum_{i=1}^N\ln[q(z_i)] = \ln \prod_{i=1}^N q(z_i) = \ln q(z_1,\ldots,z_n) = \ln q(D),

    việc tối thiểu hóa rủi ro thực nghiệm trên tương đương với việc cực đại hóa mật độ xác suất đồng thời (joint probability density) của toàn bộ dữ liệu. Vì vậy, phương pháp này còn gọi là phương pháp cực đại hóa khả năng (maximum likelihood estimation – MLE), một phương pháp rất quen thuộc trong ngành xác suất thống kê.

  3. Gần đây, người ta nhận ra rằng, thuật toán phân cụm K-means (một thuật toán học không có giám sát) cũng có thể viết theo nguyên lý tối thiểu hóa rủi ro thực nghiệm. Từ đó có thể sử dụng lý thuyết VC để ước lượng xác suất lỗi cũng như tính hội tụ của thuật toán phân cụm.

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: