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) (2) – Xác suất, công thức Bayes

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

Định nghĩa (\displaystyle \sigma- đại số): Cho tập \displaystyle \Omega, tập \displaystyle F gọi là \displaystyle \sigma- đại số của \displaystyle \Omega nếu

  1. Các phần tử của \displaystyle F là các tập con của \displaystyle \Omega
  2. Tập \displaystyle F khác rỗng: \displaystyle F\neq \emptyset
  3. Tập \displaystyle F đóng với phép hợp: \displaystyle X_1,X_2\in F\Rightarrow (X_1\cup X_2)\in F.
  4. Tập \displaystyle F đóng với phép bù: \displaystyle X\in F\Rightarrow (\Omega\setminus X)\in F

Ví dụ:

  1. Từ các tính chất, ta thấy \displaystyle \sigma- đại số luôn chứa tập rỗng \displaystyle \emptyset và tập vũ trụ \displaystyle \Omega (vì \displaystyle F\neq \emptyset\Rightarrow \exists X\in F\displaystyle \Rightarrow (\Omega\setminus X)\in F\Rightarrow \Omega \in F \Rightarrow \emptyset \in F).
  2. Nếu \displaystyle \Omega=\{1,2,3\} thì \displaystyle F_1=\{\emptyset,\{1,2,3\}\}, \displaystyle F_2=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}, \displaystyle F_3=\{\emptyset,\{1\},\{2,3\},\{1,2,3\}\} là các \displaystyle \sigma- đại số trên \displaystyle \Omega.

Định nghĩa (độ đo): Cho \displaystyle \Omega và \displaystyle F là \displaystyle \sigma- đại số trên \displaystyle \Omega. Hàm \displaystyle \mu: F\rightarrow \mathbb{R} gọi là độ đo trên \displaystyle F nếu

  1. \displaystyle \mu(S) \geq 0, \forall S\in F
  2. \displaystyle \mu(\emptyset) = 0
  3. Nếu \displaystyle S_1, S_2, \ldots \in F và không giao nhau từng đôi một (\displaystyle S_i\cap S_j = \emptyset, \forall i\neq j) thì \displaystyle \mu\left(\bigcup_{i=1}^\infty S_i\right) = \sum_{i=1}^\infty \mu(S_i)

Ta nói bộ \displaystyle (\Omega, F,\mu) là không gian đo được.

Định nghĩa (không gian mẫu, biến cố, xác suất):

Không gian mẫu: Một tập \displaystyle \Omega khác rỗng gọi là không gian mẫu nếu các phần tử của nó có thể là kết quả của một phép thực nghiệm ngẫu nhiên.

Ví dụ:

  1. Có một hộp có gồm 10 viên bi bên trong, nhắm mắt lại chọn ngẫu nhiên 1 viên bi. Như vậy mỗi viên bi đều có thể là kết quả của phép thực nghiệm này, không gian mẫu là \displaystyle \Omega=\{1,2,3,4,5,6,7,8,9,10\} là số hiệu cuả từng viên bi.
  2. Có 3 người, chọn ngẫu nhiên 1 người và hỏi người này có thích màu đỏ không? Không gian mẫu là \displaystyle \Omega=\{(1,\textrm{like}),(2,\textrm{like}),(3,\textrm{like}),(1,\textrm{dislike}),(2,\textrm{dislike}),(3,\textrm{dislike})\}. Nếu hỏi cả 3 người xem họ có thích màu đỏ không, lúc này không gian mẫu lại là \displaystyle \Omega = \{111,110,101,100,011,010,001,000\}, trong đó 1 là thích, {0} là không thích.

Biến cố: Một \displaystyle \sigma- đại số \displaystyle F của không gian mẫu \displaystyle \Omega gọi là tập các biến cố trên \displaystyle \Omega. Mỗi tập \displaystyle S\in F gọi là một biến cố. Khi thực nghiệm ngẫu nhiên cho kết quả \displaystyle x\in \Omega thì với các biến cố \displaystyle S\in F mà \displaystyle x\in S, ta nói biến cố \displaystyle S đã xảy ra.

Ví dụ:

  1. Xét hòm bi có 3 viên bi, \displaystyle \Omega=\{1,2,3\} và tập biến cố \displaystyle F=\{\emptyset,\{1\},\{2,3\},\{1,2,3\}\}. Nếu ta nhấc được hòn bi số \displaystyle 1 thì các biến cố \displaystyle \{1\},\{1,2,3\} đã xảy ra, còn các biến cố \displaystyle \emptyset, \{2,3\} không xảy ra.
  2. Nếu hỏi cả 3 người xem họ có thích màu đỏ không, không gian mẫu là \displaystyle \Omega = \{111,110,101,100,011,010,001,000\}. Biến cố “có đúng 2 người thích màu đỏ là” \displaystyle S_1=\{110,101,011\}, biến cố “có ít nhất 1 người không thích màu đỏ” là \displaystyle S_2=\{110,101,100,011,010,001,000\}.

Xác suất: Xét một thực nghiệm ngẫu nhiên với không gian mẫu \displaystyle \Omega và tập các biến cố \displaystyle F, ta nói độ đo \displaystyle P trên \displaystyle F là độ đo xác suất nếu \displaystyle P(\Omega) = 1 (có thể suy ra \displaystyle P(\emptyset) = 0).

Ví dụ:

  1. Như vậy, xác suất theo định nghĩa trên chỉ đơn giản là một hàm (độ đo) trên tập các biến cố. Giá trị của hàm này trên từng biến cố có thể xác định bằng thực nghiệm hoặc qua chủ quan của chính ta. Ví dụ, nếu ta tung đồng xu 1000 lần, trong đó 495 lần được mặt ngửa, 505 lần được mặt sấp, ta hoàn toàn có thể gán \displaystyle P(\emptyset)=0, P(\{\textrm{head}\})=\frac{495}{1000}, P(\{\textrm{tail}\})=\frac{505}{1000}, P(\{\textrm{head,tail}\})=1. Tuy nhiên, “kinh nghiệm” bảo ta rằng, xác suất tung đồng xu ra hai mặt sấp ngửa nên bằng nhau thì “hợp lý” hơn và ta có thể “áp đặt” xác suất của các biến cố này như sau: \displaystyle P(\emptyset)=0, P(\{\textrm{head}\})=\frac{1}{2}, P(\{\textrm{tail}\})=\frac{1}{2}, P(\{\textrm{head,tail}\})=1. Sau đây ta sẽ thấy, việc áp đặt giá trị xác suất ban đầu không ảnh hưởng lắm đến giá trị xác suất “thực sự”, ta có thể sử dụng công thức Bayes để tính lại các giá trị xác suất này sau khi quan sát được các kết quả thực nghiệm.
  2. Để cho tiện, khi nói đến một thực nghiệm ngẫu nhiên, người ta ngầm hiểu là có một không gian mẫu \displaystyle \Omega, một tập các biến cố \displaystyle F và một độ đo xác suất \displaystyle P trên \displaystyle F.

Một số công thức xác suất:

Công thức cộng: \displaystyle P(A\cup B)=P(A)+P(B)-P(A\cap B)

Người ta thường viết tắt \displaystyle A\cap B=AB

Công thức DeMorgan: \displaystyle P(\overline{A\cup B}) = P(\overline{A}\cap \overline{B})=1-P(A\cup B)

Xác suất điều kiện: Xác suất xảy ra biến cố \displaystyle A khi biến cố \displaystyle B đã xảy ra là

\displaystyle P(A|B)=\frac{P(AB)}{P(B)}

Nhận xét:

  1. Xác xuất xảy ra biến cố \displaystyle B khi biến cố \displaystyle A đã xảy ra là\displaystyle P(B|A)=\frac{P(BA)}{P(A)}\displaystyle \Rightarrow P(AB)=P(A|B)P(B)=P(B|A)P(A)do \displaystyle P(AB)=P(BA).
  2. Có thể hiểu xác suất có điều kiện khi đã biết biến cố \displaystyle B xảy ra là xác suất được định nghĩa trên không gian mẫu mới \displaystyle B, tập các biến cố \displaystyle F_B = \{A\cap B | A\in F\}. Vì thế, khi đã biết biến cố \displaystyle B, có thể kiểm tra được xác suất có điều kiện thỏa mãn mọi điều kiện của một độ đo xác suất bình thường.

Độc lập xác suất: Hai biến cố \displaystyle A, B độc lập với nhau nếu

\displaystyle P(AB) = P(A)P(B).

Nhận xét:

  1. \displaystyle P(\emptyset) = 0 = P(\emptyset)P(B),\forall B nên \displaystyle \emptyset, B độc lập với nhau.
  2. Vì \displaystyle P(AB)=P(A|B)P(B) nên nếu \displaystyle P(B)\neq 0 ta có \displaystyle P(A|B)=P(A). Nghĩa là biến cố \displaystyle B đã xảy ra hay không không làm ảnh hưởng đến xác suất của biến cố \displaystyle A.

Công thức Bayes: Cho biến cố \displaystyle B và các biến cố \displaystyle A_1, A_2, ... A_n sao cho

  1. Các tập \displaystyle A_i, i=1,\ldots,n rời nhau từng đôi một
  2. \displaystyle \bigcup_{i=1}^nA_i = \Omega

thì ta có công thức xác suất tổng

\displaystyle P(B) = \sum_{i=1}^n P(B|A_i)P(A_i)

và công thức Bayes

\displaystyle P(A_k|B)=\frac{P(BA_k)}{P(B)}=\frac{P(B|A_k)P(A_k)}{\displaystyle \sum_{i=1}^n P(B|A_i)P(A_i)}

Chứng minh: Rõ ràng

\displaystyle B = B\Omega = B\bigcup_{i=1}^nA_i=\bigcup_{i=1}^nBA_i

Do \displaystyle A_i,i=1,\ldots,n rời nhau từng đôi một nên \displaystyle BA_i,i=1,\ldots,n cũng rời nhau từng đôi một. Do \displaystyle P là độ đo nên

\displaystyle P(B) = P\left(\bigcup_{i=1}^nBA_i\right)=\sum_{i=1}^nP(BA_i)=\sum_{i=1}^n P(B|A_i)P(A_i)

Ví dụ:

  1. Giả sử trong một cộng đồng dân cư có một loại bệnh \displaystyle X. Tỉ lệ số người mắc bệnh \displaystyle X là \displaystyle 20\%. Để chẩn đoán bệnh này, người ta dùng xét nghiệm \displaystyle Y. Tuy nhiên, xét nghiệm \displaystyle Y không chính xác tuyệt đối, tỉ lệ chẩn đoán đúng với người có bệnh (true positive) là \displaystyle 95\%, trong khi đó, tỉ lệ chuẩn đoán sai với người không có bệnh (false positive) là \displaystyle 5\%. Giả sử một người được chuẩn đoán là có bệnh, hỏi xác suất để người này thực sự có bệnh là bao nhiêu?
    Giải: Gọi \displaystyle A_1 là biến cố “có bệnh”, \displaystyle A_2 là biến cố “không có bệnh”, \displaystyle B là biến cố “chẩn đoán có bệnh”. Như vậy các biến cố \displaystyle A_1, A_2 thỏa mãn điều kiện của công thức cộng xác suất và công thức Bayes.

    \displaystyle P(B)=P(B|A_1)P(A_1)+P(B|A_2)P(A_2)=\frac{95}{100}\frac{20}{100}+\frac{5}{100}\frac{80}{100}=\frac{23}{100}
    \displaystyle P(A_1|B)=\frac{P(B|A_1)P(A_1)}{P(B)}=\frac{95}{100}\frac{20}{100}\frac{100}{23} \approx 82,6\%

    Như vậy, khi bị chẩn đoán có bệnh, người này có khả năng bị bệnh cao hơn tỉ lệ bình thường (\displaystyle 82,6\% > 20\%), nhưng cũng chưa thể chắc chắn là người này bị bệnh, lí do là có thể chẩn đoán sai. Ví dụ này cũng cho thấy công thức Bayes cho phép chỉnh sửa lại xác suất khi quan sát được kết quả thực nghiệm.

  2. Giả sử sau khi bị chẩn đoán có bệnh, người này tiếp tục đi chẩn đoán lần thứ 2, xác suất để chẩn đoán lần này cũng có bệnh là bao nhiêu?
    Giải: Gọi \displaystyle C là biến cố “tiếp tục bị chẩn đoán có bệnh. Ta cần tính xác suất \displaystyle P(C|B). Để tính công thức xác suất tổng

    \displaystyle P(C|B) = P(C|B,A_1)P(A_1|B)+P(C|B,A_2)P(A_2|B)

    ta phải giả sử 2 lần xét nghiệm hoàn toàn độc lập với nhau, bất kể người đó có bệnh hay không, khi đó

    \displaystyle P(C,B|A_1)=P(C|B,A_1)P(B|A_1)=P(C|A_1)P(B|A_1)
    \displaystyle \Rightarrow P(C|B,A_1) = P(C|A_1) = 95\%, P(C|B,A_2)=P(C|A_2)=5\%
    \displaystyle P(A_2|B) = \frac{P(B|A_2)P(A_2)}{P(B)}=\frac{5}{100}\frac{80}{100}\frac{100}{23} \approx 17,4\%=1-P(A_1|B)

    Thế vào công thức trên ta được \displaystyle P(C|B)=\frac{95}{100}\frac{82,6}{100}+\frac{5}{100}\frac{17,4}{100}\approx 79,3\%. Nghĩa là xác suất chẩn đoán có bệnh tăng lên rất nhiều so với lần chẩn đoán đầu tiên (\displaystyle P(B)=23\%).

  3. Xác suất người này có bệnh sau khi cả hai lần chẩn đoán đều có bệnh là

    \displaystyle P(A_1|C,B) = \frac{P(C|B,A_1)P(A_1|B)}{P(C|B)} = \frac{95}{100}\frac{82,6}{100}\frac{100}{79,3}\approx 98,9\%

    Tức là gần như chắc chắn người này có bệnh sau khi 2 lần chẩn đoán đều cho kết quả dương tính (positive).

Bài viết này được đăng vào Tháng Bảy 26, 2008 lúc 6:15 chiều và tập tin được lưu ở Lý thuyết học máy. Tagged: , , , , , , , , . Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

XHTML: Bạn có thể sử dụng những thẻ sau: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

«
»