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) (5) – Ước lượng mật độ xác suất có điều kiện

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

Qua phân tích về quyết định tối ưu, ta thấy bài toán phân lớp có thể giải quyết bằng cách xác định/ước lượng xác suất có điều kiện của từng lớp đối tượng \displaystyle p(x|\omega_k), k=1,\ldots,K. Các vấn đề phải giải quyết của cách tiếp cận này là:

  1. Xây dựng thuật toán để ước lượng mật độ xác suất \displaystyle p(x|\omega_k),k=1,\ldots,K: làm thế nào để tận dụng được dữ liệu (các mẫu học) hoặc các kiến thức chuyên ngành (field knowledge) để ước lượng xác suất này. Đồng thời phải đánh giá được thời gian/bộ nhớ/số lượng mẫu học cần thiết để đảm bảo sai số của ước lượng không vượt quá một ngưỡng \displaystyle \epsilon cho trước nào đó.
  2. Khi chấp nhận ước lượng mật độ xác suất có điều kiện không chính xác tuyệt đối, phải đánh giá được tác động từ sai số lên xác suất lỗi của các quyết định dựa trên ước lượng mật độ này. Cụ thể là phải đánh giá được xác suất lỗi \displaystyle P\{\mathrm{error}\} của thuật toán so với xác suất lỗi tối ưu \displaystyle P_{\mathrm{Bayes}}\{error\} khi sử dụng luật phân lớp tối ưu Bayes.

Khi ước lượng được \displaystyle p(x|\omega_k), ta nói máy tính đã “học” được khái niệm (concept) về lớp \displaystyle \omega_k. Đồng thời, do bài toán phân lớp có thể quy về bài toán ước lượng xác suất, gần như mỗi thuật toán ước lượng xác suất đều dẫn đến một thuật toán phân lớp tương ứng.

Bài toán ước lượng mật độ xác suất (density estimation): Bài toán ước lượng mật độ xác suất là bài toán kinh điển của khoa học xác suất thống kê. Trong bài toán này, không mất tính tổng quát, ta coi tất cả dữ liệu cùng thuộc về một lớp, nghĩa là mọi dữ liệu \displaystyle x có được đều xuất phát từ một phân bố xác suất \displaystyle p(x) nào đó mà ta chưa biết. Bài toán đặt ra là với dữ liệu \displaystyle x_1,x_2,\ldots,x_N\sim p(x) và các kiến thức chuyên ngành (các hiểu biết cơ bản về \displaystyle p(x)) ta cần xác định hàm mật độ \displaystyle p(x) “chính xác” nhất có thể được.

Như vậy, ta cần tìm một ước lượng \displaystyle \widehat{p}(x|x_1,\ldots,x_N) của \displaystyle p(x). Độ chính xác của ước lượng có thể đánh giá bằng nhiều cách. Ví dụ:

  • Dùng khoảng cách \displaystyle \mathrm{L}_\infty: \displaystyle D_\infty(p,\widehat{p}) = \max_x |p(x)-\widehat{p}(x)|
  • Dùng khoảng cách \displaystyle \mathrm{L}_1: \displaystyle D_1(p,\widehat{p}) = \int_{\mathbb{R}^n}|p(x)-\widehat{p}(x)|dx
  • Dùng khoảng cách \displaystyle \mathrm{L}_2: \displaystyle D_2(p,\widehat{p}) = \int_{\mathbb{R}^n}|p(x)-\widehat{p}(x)|^2dx
  • Dùng khoảng cách Kullback-Leibler: \displaystyle D_{\mathrm{KL}}( p,\widehat{p}) = \int_{\mathbb{R}^n}\ln \frac{p(x)}{\widehat{p}(x)}p(x)dx

Các khoảng cách trên đều có tính chất \displaystyle D(p,\widehat{p})\geq 0 và bằng \displaystyle {0} khi và chỉ khi \displaystyle p=\widehat{p}. Một mệnh đề thường thấy khi ước lượng mật độ xác suất là “cần ít nhất \displaystyle N(P,\epsilon) mẫu học để đảm bảo với xác suất \displaystyle P, khoảng cách \displaystyle D(p,\widehat{p})\leq \epsilon“.

Hàm phân bố thực nghiệm (empirical distribution function)

Về mặt lý thuyết, có thể tìm \displaystyle \widehat{p}(x) từ tập tất cả các mật độ xác suất có thể có trên \displaystyle \mathbb{R}^n. Hoặc tổng quát hơn, ta có thể tìm ước lượng \displaystyle \widehat{F}(x) của hàm phân bố \displaystyle F(x)=P\{X\leq x\}=\int p(x)dx. Một phương pháp trực tiếp và khá đơn giản là sử dụng hàm phân bố thực nghiệm.

Trước tiên, giả sử \displaystyle n=1, nghĩa là \displaystyle x \in \mathbb{R}. Khi đó hàm phân bố thực nghiệm \displaystyle \widehat{F}_N(x) định nghĩa như sau

\displaystyle \widehat{F}_N(x|x_1,\ldots,x_N) = \frac{1}{N}\sum_{i=1}^N I(x_i\leq x)

trong đó \displaystyle I(.) gọi là hàm chỉ thị (indicator function), nó trả về \displaystyle 1 nếu mệnh đề đúng và \displaystyle {0} nếu mệnh đề sai. Nghĩa là hàm \displaystyle \widehat{F}_N(x) tính tỉ lệ số mẫu học nằm bên trái \displaystyle x trên trục số thực.

Định lý (Glivenko-Cantelli): Khi \displaystyle N\rightarrow \infty, xác suất để khoảng cách \displaystyle D_\infty(F, \widehat{F}_N) \rightarrow 0 bằng \displaystyle 1:

\displaystyle P\{\lim_{N\rightarrow\infty} D_\infty(F, \widehat{F}_N) = 0\}=1

Ta nói hàm \displaystyle \widehat{F}_N(x) hội tụ đều (uniform convergence) theo xác suất đến \displaystyle F(x) gần như chắc chắn (xác suất bằng \displaystyle 1).

Định lý (bất đẳng thức Dvoretzky–Kiefer–Wolfowitz): Với \displaystyle N mẫu học và với mọi \displaystyle \epsilon>0 ta có

\displaystyle P\{D_\infty(F, \widehat{F}_N)>\epsilon\}<2\exp\{-2N\epsilon^2\}

Định lý cho biết tỉ lệ hội tụ của hàm \displaystyle \widehat{F}_N(x) đến \displaystyle F(x)tuyến tính theo \displaystyle N. Đồng thời, định lý đúng với bất kể hàm phân bố \displaystyle F nào. Ở đây, nếu đặt \displaystyle P = 1-2\exp\{-2N\epsilon^2\}, ta có thể tính \displaystyle N(P,\epsilon) = \frac{1}{2\epsilon^2}\ln \frac{2}{1-P}.

Ví dụ: Hỏi cần bao nhiêu mẫu học để với xác suất ít nhất là \displaystyle 90\%, khoảng cách \displaystyle D_\infty(F,\widehat{F}_N) nhỏ hơn \displaystyle 0.1 ?

Giải: Ta có \displaystyle P\{D_\infty(F, \widehat{F}_N)<0.1\}>1-2\exp\{-2N(0.1)^2\}. Ta cần tìm \displaystyle N để

\displaystyle \begin{array}{cl} &1-2\exp\{-2N(0.1)^2\} \geq 90\%\\ \Leftrightarrow& 0.1 \geq 2\exp\{-2N/100\}\\ \Leftrightarrow& \ln \frac{0.1}{2}\geq -2N/100\\ \Leftrightarrow& N \geq 50\ln 20 \approx 149.78\end{array}

Như vậy, với mọi hàm phân bố \displaystyle F, ta cần \displaystyle N=150 mẫu học để với xác suất ít nhất là \displaystyle 90\%, khoảng cách \displaystyle D_\infty(F,\widehat{F}_N) nhỏ hơn \displaystyle 0.1.

Định lý Glivenko-Cantelli có thể được mở rộng cho trường hợp \displaystyle x\in \mathbb{R}^n, khi đó hàm phân bố thực nghiệm được định nghĩa như sau

\displaystyle \widehat{F}_N(x|x_1,\ldots,x_N) = \frac{1}{N}\sum_{i=1}^N I(x_i\leq x)

trong đó phép so sánh hai véctơ \displaystyle x,x_i\in \mathbb{R}^n được thực hiện bằng cách so sánh tất cả các tọa độ của cả 2 véctơ.

Lớp các phân bố/mật độ (distribution/density class): Trong trường hợp từ các kiến thức chuyên ngành, ta biết thêm các tính chất của hàm phân phối (hoặc hàm mật độ), ta có thể tiến hành tìm kiếm các ước lượng \displaystyle \widehat{F}_N(x) (hoặc \displaystyle \widehat{p}_N(x)) trong lớp các hàm mật độ hoăc phân phối thỏa mãn các tính chất này. Giả sử lớp các hàm phân phối thỏa mãn các tính chất đã biết là \displaystyle \mathcal{F}, dựa vào dữ liệu \displaystyle D=\{x_1,\ldots,x_N\} ta cần tìm hàm phân phối \displaystyle \widehat{F}_N(x|D)\in \mathcal{F} sao cho:

\displaystyle P\{D(F^*,\widehat{F}_N) < \epsilon\}\geq P

với \displaystyle F^* = \arg\min_{G\in \mathcal{F}} D(F,G). Để ý là \displaystyle F=F^* nếu \displaystyle F\in \mathcal{F}. Như vậy, mệnh đề trên có nghĩa là: với xác suất ít nhất là \displaystyle P, khoảng cách từ ước lượng \displaystyle \widehat{F}_N đến hàm phân phối \displaystyle F^* gần \displaystyle F nhất trong lớp các hàm phân phối \displaystyle \mathcal{F} nhỏ hơn \displaystyle \epsilon.

Giáo sư Vapnik và Chervonenkis đã phát triển lý thuyết VC (VC theory) mang tên hai ông mô tả các điều kiện cần có của lớp hàm phân phối \displaystyle \mathcal{F} để ta có thể ước lượng được các xác suất trên. Đặc biệt, hai ông gợi ý ta có thể dùng một đại lượng gọi là chiều VC (VC dimension) để mô tả khả năng thể hiện (capacity) của một lớp hàm. Các công thức trong lý thuyết VC ước lượng xác suất tương tự như bất đẳng thức Dvoretzky–Kiefer–Wolfowitz đều chứa đại lượng chiều VC.

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: