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) (4) – Bài toán phân lớp, quyết định tối ưu, hàm phân lớp

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

Bài toán phân lớp (classification):

Ví dụ:

  1. Trong một dây chuyền lựa chọn hoa quả, cụ thể là quả cam, ta cần lựa chọn những quả cam có kích thước và có màu sắc theo tiêu chuẩn để đóng gói, còn các quả cam khác không đủ tiêu chuẩn sẽ bị loại. Như vậy, bài toán phân lớp quả cam có 2 lớp “đủ tiêu chuẩn” và “không đủ tiêu chuẩn”, tiêu chí để lựa chọn dựa trên 2 đặc trưng “kích thước” và “màu sắc”.
  2. Các bài toán nhận dạng khác cũng có cấu trúc tương tự: nhận dạng chữ viết tay (đầu vào là ảnh, đầu ra là chữ cái hoặc chữ số),; nhận dạng các bất thường trong dữ liệu (ví dụ: nhiễu dữ liệu, gian lận tài chính v.v…); nhận dạng mặt người, giọng nói, vân tay; và rất nhiều ví dụ khác.

Như vậy, bài toán phân lớp tự động có đặc điểm chung là:

  1. Máy tính được cung cấp dữ liệu về các đặc trưng (features) của đối tượng.
  2. Máy tính quyết định/đoán đối tượng thuộc về lớp đối tượng/khái niệm (class/concept) nào.
  3. Các lớp đối tượng/khái niệm có thể được biết trước (học có giám sát – supervised learning) hoặc chưa được biết trước (học không có giám sát – unsupervised learning).

Một vấn đề là làm thế nào để đánh giá một thuật toán phân lớp, hoặc so sánh hai thuật toán phân lớp trên các tiêu chí:

  1. Tần suất nhận dạng lỗi (hay xác suất lỗigeneralization error): xác suất máy tính đoán nhầm lớp đối tượng.
  2. Tốc độ/bộ nhớ cần thiết để thuật toán nhận dạng một mẫu đối tượng.
  3. Tốc độ/bộ nhớ/số lượng mẫu học (training samples) cần thiết trong quá trình học để “nhớ” các lớp đối tượng.

Một kiểu mệnh đề kinh điển trong Học máy là “cần ít nhất \displaystyle N=N(\delta,\epsilon)  mẫu học để đảm bảo với xác suất ít nhất \displaystyle 1-\delta, xác suất nhận dạng lỗi không lớn hơn \displaystyle \epsilon cho trước” (xem Probably Approximately Correct learning).

Để nói về các khái niệm cơ bản của bài toán phân lớp, ta xét bài toán phân lớp đơn giản có 2 lớp \displaystyle \omega_1\displaystyle \omega_2 với véctơ các đặc trưng \displaystyle x nằm trong \displaystyle \mathbb{R}^n (có \displaystyle n đặc trưng cần quan tâm). Giả sử một thuật toán nhận dạng đoán

\displaystyle x\in \omega_1 \Leftrightarrow x\in R_1\subset \mathbb{R}^n

\displaystyle x\in \omega_2 \Leftrightarrow x\in R_2 = \mathbb{R}^n\setminus R_1.

Nếu ta gọi \displaystyle \omega_1 là biến cố “đối tượng thuộc lớp \displaystyle \omega_1“, \displaystyle \omega_2 là biến cố “đối tượng thuộc lớp \displaystyle \omega_2” thì khi \displaystyle x\in R_1, xác suất nhận dạng lỗi là \displaystyle P(\omega_2|x) còn khi \displaystyle x\in R_2, xác suất nhận dạng lỗi là \displaystyle P(\omega_1|x)=1-P(\omega_2|x). Như vậy, sử dụng công thức xác suất tổng ta có xác suất lỗi của thuật toán nhận dạng là

\displaystyle \begin{array}{rcl}P\{\mathrm{error}\} &=& \displaystyle P(\mathrm{error}, x\in R_1)+P(\mathrm{error},x\in R_2) \\&=&\displaystyle \int_{R_1} P(\mathrm{error}|x)p(x)dx + \int_{R_2} P(\mathrm{error}|x)p(x)dx \\&=&\displaystyle  \int_{R_1} P(\omega_2|x)p(x)dx + \int_{R_2} P(\omega_1|x)p(x)dx\end{array}

Suy ra, để \displaystyle P\{\mathrm{error}\} nhỏ nhất (tối ưu), hai vùng \displaystyle R_1\displaystyle R_2 phải thỏa mãn

\displaystyle R_1 = \{x\in \mathbb{R}^n|P(\omega_1|x)\geq P(\omega_2|x)\}

\displaystyle R_2 = \{x\in \mathbb{R}^n|P(\omega_1|x)<P(\omega_2|x)\}

Nói cách khác, luật phân lớp là

\displaystyle x\in\omega_1 nếu \displaystyle P(\omega_1|x)\geq P(\omega_2|x) còn \displaystyle x\in\omega_2 nếu ngược lại.

Quyết định phân lớp như trên gọi là quyết định tối ưu (optimal decision), hay còn gọi là luật Bayes (Bayes decision rule). Tất nhiên, ta luôn muốn quyết định phân lớp là quyết định tối ưu. Tuy nhiên, để đạt được tính tối ưu, ta cần tính được các xác suất \displaystyle P(\omega_1|x)\displaystyle P(\omega_2|x)=1-P(\omega_1|x). Theo công thức xác suất điều kiện, ta có

\displaystyle P(\omega_1|x)=\frac{p(\omega_1,x)}{p(x)}=\frac{p(x|\omega_1)P(\omega_1)}{p(x)}

\displaystyle P(\omega_2|x)=\frac{p(\omega_2,x)}{p(x)}=\frac{p(x|\omega_2)P(\omega_2)}{p(x)}

Do đó, việc so sánh

\displaystyle P(\omega_1|x)\geq P(\omega_2|x) tương đương với \displaystyle p(x|\omega_1)P(\omega_1)\geq p(x|\omega_2)P(\omega_2),

tức là bài toán quy về việc xác định các (mật độ) xác suất có điều kiện (density estimation) \displaystyle p(x|\omega_1)\displaystyle p(x|\omega_2) do các xác suất \displaystyle P(\omega_1)\displaystyle P(\omega_2) có thể xác định bằng việc quan sát tỉ lệ số mẫu học thuộc vào 2 lớp \displaystyle \omega_1,\omega_2 hoặc đơn giản bằng việc giả sử \displaystyle P(\omega_1)=P(\omega_2)=0.5 (giả sử hai lớp đối tượng có xác suất xuất hiện như nhau).

Một cách nhìn khác đối với luật phân lớp trên là

\displaystyle x\in\omega_1 nếu \displaystyle P(\omega_1|x)- P(\omega_2|x)\geq 0 còn \displaystyle x\in\omega_2 nếu ngược lại.

Như vậy, nếu ta ước lượng hoặc xấp xỉ được hàm \displaystyle f(x) = P(\omega_1|x)- P(\omega_2|x) hoặc \displaystyle f(x) = p(x|\omega_1)P(\omega_1)- p(x|\omega_2)P(\omega_2) thì luật phân lớp là

\displaystyle x\in\omega_1 nếu \displaystyle f(x)\geq 0 còn \displaystyle x\in\omega_2 nếu \displaystyle f(x)<0.

Như vậy, bài toán phân lớp có thể giải quyết bằng cách ước lượng hàm phân lớp (discriminative function) \displaystyle f(x).

Trường hợp bài toán có nhiều lớp (multi-class) \displaystyle \omega_1,\ldots,\omega_K , bằng suy luận tương tự như trên, luật phân lớp tối ưu là

\displaystyle x\in\omega_k khi và chỉ khi \displaystyle \omega_k=\arg\max_{\omega_i} P(\omega_i|x)

và ta cũng có hàm phân lớp tương ứng.

Trong một số trường hợp, “hậu quả” của việc đoán một đối tượng thuộc lớp \displaystyle \omega_i là đối tượng của lớp \displaystyle \omega_j không giống nhau với mọi \displaystyle i, j=1,\ldots,K. Ví dụ khi kiểm tra an ninh, thà ta nhận nhầm người trong công ty (authenticated person) là người ngoài (impostor) vẫn hơn là ta nhận nhầm người ngoài là người trong công ty và trao quyền truy xuất. Khi đó, người ta đưa vào ma trận giá (cost matrix) \displaystyle C\in \mathbb{R}^{K\times K} sao cho

\displaystyle c_{ij} = giá phải trả khi đoán đối tượng lớp \displaystyle \omega_i là đối tượng của lớp \displaystyle \omega_j.

Như vậy, khi ta đoán đối tượng \displaystyle x thuộc vào lớp \displaystyle \omega_j (hay \displaystyle x\in R_j)  thì giá trị kì vọng của giá phải trả là

\displaystyle c_j(x) = \sum_{i=1}^n c_{ij} P(\omega_i|x)

Giá trị kì vọng của giá phải trả trên toàn bộ \displaystyle \mathbb{R}^n

\displaystyle C = \sum_{k=1}^K\int_{R_k} c_k(x)p(x)dx

Suy luận tương tự như trên, ta có luật phân lớp tối ưu là

\displaystyle x\in\omega_k khi và chỉ khi \displaystyle k = \arg\min_j c_j(x)

và bài toán vẫn có thể quy về việc tính mật độ xác suất có điều kiện hoặc ước lượng hàm phân lớp.

Như vậy có 2 phương pháp chính (thật ra là 2 trường phái) để giải quyết bài toán phân lớp:

  1. Ước lượng mật độ xác suất có điều kiện \displaystyle p(x|\omega_k), k=1,\ldots,K.
  2. Ước lượng hàm phân lớp \displaystyle f:\mathbb{R}^n\rightarrow \{1,\ldots,K\}.

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: