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

Learn & Enjoy …

Posts Tagged ‘bayes’

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

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

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

Đă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) (3) – Biến ngẫu nhiên, phân bố xác suất

Đăng bởi tqlong on Tháng Bảy 27, 2008

Định nghĩa (Biến ngẫu nhiên thực): Cho không gian xác suất \displaystyle (\Omega, F, P), hàm \displaystyle X:\Omega\rightarrow \mathbb{R} gọi là biến ngẫu nhiên trên không gian xác suất nếu

\displaystyle \{s\in \Omega|X(s)\leq x\}\in F,\forall x\in \mathbb{R}

Nhận xét:

  1. Như vậy, biến ngẫu nhiên là một hàm trên tập các kết quả thực nghiệm ngẫu nhiên.
  2. Điều kiện trên cho phép ta tính được xác suất \displaystyle P\{X\in R\} = P(\{s\in\Omega|X(s)\in R\}) với mọi tập đo được (measurable set) \displaystyle R \subset \mathbb{R}.
  3. Để cho tiện, ta kí hiệu biến cố \displaystyle \{X\in R\}=\{s\in\Omega|X(s)\in R\}.

Ví dụ:

  1. Xét ví dụ hỏi 3 người cùng lúc xem họ có thích màu đỏ hay không, không gian xác suất là \displaystyle \Omega=\{111,110,101,100,011,010,001,000\} và tập biến cố là \displaystyle F=2^\Omega (tập tất cả các tập con của \displaystyle \Omega). Giả sử \displaystyle P({s}) = \frac{1}{8},\forall s\in\Omega (xác suất đều cho mọi kết quả). Xét biến ngẫu nhiên \displaystyle X là số người thích màu đỏ. Như vậy ta có

    \displaystyle P\{X=0\}=\frac{1}{8}, P\{X=1\}=\frac{3}{8}, P\{X=2\}=\frac{3}{8}, P\{X=3\}=\frac{1}{8}
    \displaystyle P\{X\leq 1\}=\frac{4}{8}=\frac{1}{2}, P\{X>0\}=\frac{7}{8}

Định nghĩa (Phân bố xác suất): Hàm \displaystyle F_X(x) = P\{X\leq x\} gọi là hàm phân bố xác suất (cummulative distribution function – CDF) của biến ngẫu nhiên \displaystyle X.

Nhận xét:

  1. Khi nói về các biến ngẫu nhiên, người ta ngầm hiểu là có một không gian xác suất \displaystyle (\Omega, F, P) nào đó và thường chỉ sử dụng hàm phân bố xác suất \displaystyle F_X(x) thay vì sử dụng đến không gian xác suất.
  2. Theo cách nói của lý thuyết độ đo thì hàm \displaystyle X đã chuyển độ đo \displaystyle P trên \displaystyle F thành độ đo \displaystyle dF trên \displaystyle \mathbb{R}.
  3. Thường người ta viết \displaystyle F(x) thay cho \displaystyle F_X(x) khi không bị nhầm lẫn với các biến ngẫu nhiên khác.
  4. Khi xét 2 biến hoặc nhiều biến ngẫu nhiên cùng lúc, hàm phân bố xác suất là

    \displaystyle \begin{array}{rcl}F_{XY}(x,y) &=& P(\{X\leq x\} \cap \{Y\leq y\}) = P\{X\leq x|Y\leq y\}P\{Y\leq y\}\\ &=& F_{X|Y\leq y}(x) F_Y(y)\end{array}

  5. Hai biến ngẫu nhiên \displaystyle X,Y gọi là hai biến ngẫu nhiên độc lập với nhau nếu

    \displaystyle F_{XY}(x,y)=F_X(x)F_Y(y),\forall x,y

Một số tính chất của hàm phân bố xác suất:

  1. Hàm \displaystyle F(x) không âm và đơn điệu tăng.
  2. \displaystyle F(\infty) = \lim_{x\rightarrow \infty}F(x) = P\{X\in \mathbb{R}\}=P(\Omega)=1
    \displaystyle F(-\infty) = \lim_{x\rightarrow -\infty}F(x) = P(\emptyset)=0
  3. Hàm \displaystyle F(x) liên tục từ bên phải\displaystyle \lim_{\epsilon\rightarrow 0^+}F(x+\epsilon) = F(x)
  4. \displaystyle P\{X>x\}=1-F(x)
  5. Nếu \displaystyle x_1<x2 thì \displaystyle F(x_1<X\leq x_2)=F(x_2)-F(x_1)
  6. Xác suất \displaystyle P\{X=x\}=F(x)-\lim_{\epsilon\rightarrow 0^+} F(x-\epsilon)

Định nghĩa (mật độ xác suất): Nếu hàm phân bố \displaystyle F(x) có đạo hàm tại \displaystyle x thì \displaystyle f(x)=F'(x) gọi là hàm mật độ xác suất (probability density function – PDF)của biến ngẫu nhiên \displaystyle X tại \displaystyle x .

Một số tính chất của hàm mật độ xác suất:

  1. Do \displaystyle F(x) đơn điệu tăng nên \displaystyle f(x)\geq 0,\forall x\in \mathbb{R}
  2. \displaystyle P(a\leq X\leq b)=\int_a^b f(x)dx, \int_{-\infty}^\infty f(x)dx=1
  3. Khi hàm mật độ được định nghĩa tại \displaystyle x thì \displaystyle P\{X=x\}=0
  4. Cách dùng hàm mật độ không khác gì dùng hàm xác suất

    \displaystyle f_{XY}(X\in A, y) = f_{Y|X}(y|X\in A)P\{X\in A\}=P\{X\in A|Y=y\}f_Y(y)
    \displaystyle f_{XY}(x,y) = f_{Y|X}(y|X=x)f_X(x)=f_{X|Y}(x|Y=y)f_Y(y)
    \displaystyle P\{X\in A, Y\in B\} = \int_{B}f_{XY}(X\in A, y)dy = \int_{B}P\{X\in A|Y=y\}f_Y(y)dy

  5. Nếu hai biến ngẫu nhiên \displaystyle X,Y độc lập thì

    \displaystyle f_{XY}(x,y)=f_X(x)f_Y(y)

Một số phân bố thường gặp:

Phân bố Bernoulli: \displaystyle X\sim\mathrm{Bernoulli}(p)

\displaystyle P\{X=k\}=\begin{cases}p &k=1\\ q=1-p & k=0\\ 0 & k\neq 0,1 \end{cases}

Phân bố nhị thức (binomial distribution): \displaystyle X\sim B(n, p)

\displaystyle P\{X=k\}=\begin{cases}C_k^n p^k(1-p)^{n-k} &0\leq k\leq n\\ 0 & k<0~\&~k>n\end{cases}

Phân bố đều (continuous uniform distribution): \displaystyle X \sim U(a,b)

\displaystyle f(x)=\begin{cases}0 &x<a\\ \frac{1}{b-a} & a\leq x\leq b\\ 0 & x> b \end{cases}

Phân bố chuẩn (normal/Gaussian distribution): \displaystyle X\sim\mathcal{N}(\mu,\sigma^2)

\displaystyle f(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\exp\left\{-\frac{1}{2}\frac{(x-\mu)^2}{\sigma^2}\right\}

Trong đó \displaystyle \mu là giá trị kì vọng, \displaystyle \sigma^2 là phương sai của phân bố.

Phân bố chuẩn cho nhiều biến: \displaystyle \mathbb{R}^n\ni X\sim \mathcal{N}(\mu,\Sigma) với \displaystyle \mu\in \mathbb{R}^n,\Sigma \in \mathbb{R}^{n\times n}

\displaystyle f(x) = f(x_1,\ldots,x_n) = \frac{1}{(\sqrt{2\pi})^{n/2}|\Sigma|^{1/2}} \exp\left\{-\frac{1}{2} (x-\mu)^T\Sigma^{-1}(x-\mu)\right\}

Trong đó \displaystyle \mu là kì vọng, ma trận xác định dương \displaystyle \Sigma là ma trận hiệp phương sai của phân bố.

Phân bố mũ (exponential distribution): \displaystyle X\sim \mathrm{Exponential}(\lambda)

\displaystyle f(x)=\begin{cases}0 & x<0\\ \lambda e^{-\lambda x} &x\geq 0\end{cases}

Ví dụ:

  1. Một đồng xu có xác suất ra mặt ngửa là \displaystyle p (phân bố Bernoulli). Ban đầu ta chưa biết \displaystyle p nhưng sau khi tung đồng xu 4 lần, ta thấy có 3 lần mặt ngửa. Hỏi có thể ước lượng \displaystyle p chính xác hơn hay không?
    Giải: Gọi \displaystyle X là biến ngẫu nhiên tương ứng với số lần ra mặt ngửa trong 4 lần tung. Vì ban đầu chưa thể xác định được \displaystyle p, ta coi \displaystyle p là một biến ngẫu nhiên theo phân bố đều \displaystyle p\sim U(0,1). Như vậy, giả sử biết \displaystyle p, xác suất để tung 4 lần ra 3 lần mặt ngửa là

    \displaystyle P(X=3|p) = p^3(1-p)=(p^3-p^4)
    \displaystyle f(X=3,p)=P(X=3|p)f(p) = (p^3-p^4)
    \displaystyle P(X=3)=\int_0^1 f(X=3,p)dp = \int_0^1(p^3-p^4)dp=\left(\frac{1}{4}-\frac{1}{5}\right)=\frac{1}{20}
    \displaystyle f(p|X=3)=\frac{f(X=3,p)}{P(X=3)} = 20(p^3-p^4)

    Bayes inference of parameter

    Phân bố của p trước và sau khi quan sát kết quả thí nghiệm

    Như vậy, sau khi quan sát kết quả thí nghiệm \displaystyle X=3, ta có thể ước lượng \displaystyle p chính xác hơn (phân bố có đỉnh gần 1 hơn). Đặc biệt, phân bố đạt đỉnh ở \displaystyle p=\frac{3}{4} (có thể tính bằng cách lấy đạo hàm của \displaystyle f(p|X=3)), điểm này chính là tỉ lệ số lần được mặt ngửa (3 lần / 4 lần).

  2. Trong ví dụ trên, ta thấy cách tính

    \displaystyle f(p|X=3)=\frac{P(X=3|p)f(p)}{\displaystyle \int_0^1 P(X=3|p)f(p)dp}

    chính là một dạng của công thức Bayes nhưng áp dụng đối với phân bố liên tục.

  3. Xét một ví dụ khác, giả sử dữ liệu được lấy từ một phân bố chuẩn \displaystyle \mathcal{N}(\mu,1), tuy nhiên ta chưa biết \displaystyle \mu mà chỉ tạm thời dự đoán \displaystyle \mu \sim \mathcal{N}(0,1). Sau khi lấy được 3 mẫu dữ liệu độc lập \displaystyle x_1=-1, x_2 = 0.5, x_3 = 1, hỏi có thể dự đoán chính xác hơn về \displaystyle \mu hay không?
    Giải: Đặt \displaystyle D={x_1,x_2,x_3}, ta có

    \displaystyle f(D|\mu) = \prod_{i=1}^3 p(x_i|\mu) = \left(\frac{1}{\sqrt{2\pi}}\right)^3\exp\left(-\frac{1}{2}\sum_{i=1}^3 (x_i-\mu)^2\right)
    \displaystyle f(D,\mu) = f(D|\mu)f(\mu) = \left(\frac{1}{\sqrt{2\pi}}\right)^4\exp\left\{-\frac{1}{2}\left(\sum_{i=1}^3 (x_i-\mu)^2+\mu^2\right)\right\}
    \displaystyle f(D) = \int_{-\infty}^\infty f(D,\mu)d\mu = \int_{-\infty}^\infty\left(\frac{1}{\sqrt{2\pi}}\right)^4\exp\left\{-\frac{1}{2}\left(\sum_{i=1}^3 (x_i-\mu)^2+\mu^2\right)\right\}d\mu
    \displaystyle f(\mu|D) = \frac{f(D,\mu)}{f(D)} = \mathcal{N} ( 1/8, (1/2)^2)

    Để tính tích phân trên, ta phải chuyển tổng trong trong cơ số mũ về dạng tổng bình phương rồi áp dụng công thức \displaystyle \int_{-\infty}^\infty \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}\mu^2\right)d\mu = 1. Như vậy, với việc quan sát được dữ liệu, ta có thể chỉnh sửa lại phân bố xác suất (ước lượng) của \displaystyle \mu từ \displaystyle p(\mu)=\mathcal{N} (0,1) thành \displaystyle p(\mu|D)=\mathcal{N} ( 1/8, (1/2)^2). Để ý là phân bố xác suất sau khi có dữ liệu có phương sai nhỏ hơn (chính xác hơn) phân bố lúc đầu.

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

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