Phân loại Naive Bayes – VietTech Group

Hôm nay:

Bayes Classifiers
Conditional Independence
Naïve Bayes

Readings:

Mitchell: “Naïve Bayes and Logistic Regression” (có sẵn trên trang web của lớp)

Hai nguyên tắc ước lượng tham số

Maximum Likelihood Estimate (MLE): chọn θ để tối đa hóa xác suất của dữ liệu được quan sát D

Ước tính tối đa của Posteriori (MAP): chọn θ có khả năng xảy ra nhất với xác suất trước và dữ liệu

Ước tính khả năng xảy ra tối đa

X=1 X=0

P(X=1) = θ

P(X=0) = 1-θ

(Bernoulli)

Ước tính tối đa của Posteriori (MAP)

X=1 X=0

Hãy tìm hiểu các bộ phân loại bằng cách học P(Y|X)

Xem xét Y=Wealth, X=<Gender, HoursWorked>

Phải có bao nhiêu tham số Chúng ta ước tính?

Giả sử X =<X₁,… X_n> trong đó X_i và Y là RV boolean

Để ước lượng P(Y| X₁, X₂, … X_n)

Nếu chúng ta có 30 boolean X_i‘s: P(Y | X₁, X₂, … X₃₀)

Chúng ta phải ước lượng bao nhiêu thông số?

Giả sử X =<X₁,… X_n> trong đó Xi và Y là RV boolean

Để ước lượng P(Y| X₁, X₂, … X_n)

Nếu chúng ta có 30 X_i thay vì 2?

Quy tắc Bayes

Đó là cách viết tắt của:

Tương đương:

Chúng ta có thể giảm tham số bằng Quy tắc Bayes không?

Giả sử X =<X₁,… X_n> trong đó X_i và Y là RV boolean

Có bao nhiêu tham số để xác định P(X₁,…X_n | Y)?

Có bao nhiêu tham số để xác định P(Y)?

Chúng ta có thể giảm tham số bằng Quy tắc Bayes không?

Giả sử X =<X₁,… X_n> trong đó X_i và Y là RV boolean

Naïve Bayes

Giả định Naïve Bayes

tức là X_i và X_j độc lập có điều kiện với Y, với mọi i≠j

Độc lập có điều kiện

Định nghĩa: X độc lập có điều kiện với Y với Z, nếu phân phối xác suất chi phối X độc lập với giá trị của Y, cho trước giá trị của Z

mà chúng ta thường viết

Ví dụ,

Naïve Bayes sử dụng giả định rằng X_i độc lập có điều kiện, với Y. Ví dụ,

Với giả định này, thì:

Naïve Bayes sử dụng giả định rằng X_i độc lập có điều kiện, với Y. Ví dụ,

Với giả định này, thì:

nói chung:

Naïve Bayes sử dụng giả định rằng X_i độc lập có điều kiện, với Y. Ví dụ,

Với giả định này, thì:

nói chung:

Có bao nhiêu tham số để mô tả P(X₁…X_n|Y)? P(Y)?

Không có giả định độc lập có điều kiện?
Với giả định độc lập có điều kiện?

Độc lập có điều kiện

Naïve Bayes sử dụng giả định rằng X_i độc lập có điều kiện, với Y

Với giả định này, thì:

nói chung:

Có bao nhiêu tham số để mô tả P(X₁…X_n|Y)? P(Y)?

Không có giả định độc lập có điều kiện?
Với giả định độc lập có điều kiện?

Sơ lược về Naïve Bayes

Quy tắc Bayes:

Giả định sự độc lập có điều kiện giữa X_i‘s:

Vì vậy, để chọn Y có thể xảy ra nhất cho X^new = < X₁, …, X_n >

Thuật toán Naïve Bayes – Xi rời rạc

Huấn luyện Naïve Bayes (mẫu)
cho mỗi* giá trị y_k
- ước tính
- cho mỗi* giá trị x_ij của mỗi thuộc tính X_i
  - ước tính
Phân loại (X^new)

^* xác suất phải có tổng bằng 1, vì vậy chỉ cần ước tính n-1 trong số này…

Ước tính Tham số: Y, Xi có giá trị rời rạc

Ước tính khả năng tối đa (MLE’s):

Ví dụ: Sống ở Sq Hill? P(S|G,D,M)

S=1 nếu sống ở Squirrel Hill
G=1 nếu mua sắm tại SH Giant Eagle
D=1 nếu Lái xe đến CMU
M=1 nếu là người hâm mộ Rachel Maddow

Chúng ta phải ước tính các tham số xác suất nào?

Ví dụ: Sống ở Sq Hill? P(S|G,D,M)

S=1 nếu sống ở Squirrel Hill
G=1 nếu mua sắm tại SH Giant Eagle
D=1 nếu Lái xe đến CMU
M=1 nếu là người hâm mộ Rachel Maddow

Ví dụ: Sống ở Đồi Sq? P(S|G,D,B)

S=1 nếu sống ở Squirrel Hill
G=1 nếu mua sắm tại SH Giant Eagle
D=1 nếu Lái xe hoặc đi chung xe đến CMU
B=1 nếu Sinh nhật trước ngày 1 tháng 7

Chúng ta phải ước tính các tham số xác suất nào?

Ví dụ: Sống ở Sq Hill? P(S|G,D,E)

S=1 nếu sống ở Squirrel Hill
G=1 nếu mua sắm tại SH Giant Eagle
D=1 nếu lái xe hoặc đi chung xe đến CMU
B=1 nếu sinh nhật trước ngày 1 tháng 7

Naïve Bayes: Tinh tế #1

Thường thì X_i không thực sự độc lập có điều kiện

Dù sao thì chúng ta cũng sử dụng Naïve Bayes trong nhiều trường hợp và nó thường hoạt động khá tốt
- thường là phân loại đúng, ngay cả khi xác suất không đúng (xem [Domingos&Pazzani, 1996])
Điều gì ảnh hưởng đến ước tính P(Y|X)?
- Trường hợp cực đoan: điều gì sẽ xảy ra nếu chúng ta cộng hai bản sao: X_i = X_k

Trường hợp cực đoan: điều gì xảy ra nếu chúng ta cộng hai bản sao: X_i = X_k

Naïve Bayes: Subtlety #2

Nếu không may mắn, Ước tính MLE của chúng ta cho P(X_i | Y) có thể bằng không. (ví dụ: X_i = ngày sinh. X_i = Jan_25_1992)

Tại sao phải lo lắng về chỉ một tham số trong số nhiều tham số?
Có thể làm gì để giải quyết vấn đề này?

Naïve Bayes: Tinh tế #2

Nếu không may mắn, ước tính MLE của chúng ta cho P(X_i | Y) có thể bằng không. (ví dụ: X_i = Birthday_Is_Jan_30_1992)

Tại sao phải lo lắng về chỉ một tham số trong số nhiều tham số?
Có thể làm gì để giải quyết vấn đề này?

Các tham số ước tính

Ước tính khả năng tối đa (MLE): chọn θ tối đa hóa xác suất của dữ liệu được quan sát D
Ước tính tối đa của Posteriori (MAP): chọn θ có khả năng xảy ra nhất với xác suất trước đó và dữ liệu

Tham số ước tính: Y, Xi có giá trị rời rạc

Ước tính khả năng tối đa:

Ước tính MAP (Beta, Dirichlet Priors):

Học cách phân loại tài liệu văn bản

Phân loại email nào là thư rác?
Phân loại những email hứa hẹn một tập tin đính kèm?
Phân loại trang web nào là trang chủ của sinh viên?

Làm thế nào chúng ta sẽ trình bày các tài liệu văn bản cho Naïve Bayes?

Baseline: Phương pháp tiếp cận Bag of Words

Học cách phân loại tài liệu: P(Y|X) mô hình “Túi từ”

Y có giá trị rời rạc. ví dụ: Spam hay không
X = <X₁, X₂, … X_n> = tài liệu
X_i là một biến ngẫu nhiên mô tả từ ở vị trí i trong tài liệu
các giá trị có thể có của X_i : bất kỳ từ w_k nào trong tiếng Anh
Tài liệu = túi từ: vectơ đếm cho tất cả các w_k’s
- như #heads, #tails, nhưng chúng ta có nhiều hơn 2 giá trị
- giả sử xác suất từ không phụ thuộc vào vị trí (iid cuộn của một con súc sắc 50.000 mặt)

Thuật toán Naïve Bayes – X_i rời rạc

Huấn luyện Naïve Bayes (mẫu)
cho từng giá trị y_k
- ước tính
- cho từng giá trị x_j của từng thuộc tính X_i
  - ước tính
Phân loại (X^new)

^* Giả định bổ sung: xác suất từ không phụ thuộc vào vị trí

Ước tính MAP cho túi từ

Ước tính Map cho đa thức

Chúng ta nên chọn những β gì?

Để biết mã và dữ liệu, hãy xem www.cs.cmu.edu/~tom/mlbook.html nhấp vào “Phần mềm và dữ liệu”

Những điều bạn nên biết:

Đào tạo và sử dụng bộ phân loại dựa trên quy tắc Bayes
Độc lập có điều kiện
- Nó là gì
- Tại sao nó quan trọng
Naïve Bayes
- Nó là gì
- Tại sao chúng ta sử dụng nó nhiều như vậy
- Đào tạo sử dụng MLE, ước tính MAP
- Biến rời rạc và liên tục (Gaussian)

Câu hỏi:

Làm thế nào chúng ta có thể mở rộng Naïve Bayes nếu chỉ có 2 X_i là phụ thuộc?
Bề mặt quyết định của bộ phân loại Naïve Bayes trông như thế nào?
Trình phân loại sẽ mắc lỗi gì nếu giả định Naïve Bayes được thỏa mãn và chúng ta có dữ liệu huấn luyện vô hạn?
Bạn có thể sử dụng Naïve Bayes để kết hợp X_i rời rạc và giá trị thực không?

Nếu chúng ta có X_i liên tục thì sao?

Ví dụ: phân loại ảnh: X_i là pixel thứ i

Nếu chúng ta có X_i liên tục thì sao?

phân loại hình ảnh: X_i là pixel thứ i, Y = trạng thái tinh thần

Vẫn còn có:

Chỉ cần quyết định cách biểu diễn P(X_i | Y)

Nếu chúng ta có X_i liên tục thì sao?

Ví dụ: phân loại ảnh: X_i là pixel thứ i

Gaussian Naïve Bayes (GNB): giả sử

Đôi khi giả sử σ_ik

độc lập với Y (tức là σ_i),
hoặc độc lập với X_i (tức là σ_k)
hoặc cả hai (tức là σ)

Thuật toán Gaussian Naïve Bayes – X_i liên tục

(nhưng Y vẫn rời rạc)

Huấn luyện Naïve Bayes (mẫu)
cho mỗi giá trị y_k
- ước tính*
- cho mỗi thuộc tính X_i ước tính trung bình có điều kiện của lớp μ_ik, phương sai σ_ik
Phân loại (X^new)