Naive Bayes Classifier

1. Bayes (optimal) classifier

Ta xét bài toán classifier như sau cho một dataset Giả sử rằng , tức là bằng cách nào đó ta biết được phân phối , khi đó hàm Bayes optimal classifier của chúng ta được định nghĩa là:

Sở dĩ gọi classifier này là optimal vì nó luôn chọn ra label có xác suất xảy ra cao nhất, nên nó tối thiểu hóa được sai số. Tuy nhiên, rõ ràng ta không thể áp dụng thực tiễn ngay được vì gần như ta không thể nào biết được phân bố .

Tuy nhiên, ta sẽ cố gắng ước lượng được bằng suy diễn thống kê. Ta có biến đổi:

Ước lượng được thường là dễ dàng, ví dụ với dữ liệu rời rạc, ta có thể ước lượng bằng tần số xuất hiện của nhãn (theo MLE), hoặc thêm cả smoothing (theo MAP). Vấn đề khó hơn là làm sao để ước lượng .

Ta hoàn toàn có thể dùng hướng tiếp cận MLE hoặc cả MAP, tuy nhiên khi đó ta cần phải có đủ nhiều data để mô tả một cách tương đối đầy đủ không gian sự kiện. Giả sử, dữ liệu có chiều và mỗi feature chỉ lấy giá trị 0 hoặc 1, có nhãn, khi đó ta cần khoảng điểm dữ liệu để mô tả đủ không gian sự kiện. Tức là số lượng data cần tăng theo hàm mũ của chiều dữ liệu. Như vậy, khi số chiều quá lớn, việc thu nhập đủ dữ liệu cho ước lượng này là không khả thi!

Để giải quyết việc này, ta cần đặt ra một giả định (assumption) nào đó cho dữ liệu của chúng ta để cho bài toán dễ hơn, như mọi thuật toán machine learning khác đều làm. Và hướng tiếp cận ta đề cập trong bài viết này chính là Naive Bayes Classifier.

2. Naive Bayes Classifier

Định nghĩa

Giả định mà ta đặt ra với dữ liệu chính là: các feature của đôi một độc lập với nhau. Khi đó ta có:

Điều này khiến số lượng data cần thu thập từ tăng theo hàm mũ so với , thành chỉ còn tăng tuyến tính theo .

Như vậy, ta có:

Khi đó, Naive Bayes Classifier được định nghĩa là:

Dưới góc nhìn của nhà khoa học máy tính, ta cũng có thể viết:

Đây chính là dạng công thức chung cho Naive Bayes Classifier. Tất nhiên ta cần phải tìm các ước lượng cho các hàm xác suất trong (1).

Ước lượng cho

Ta ký hiệu tham số và gọi là một ước lượng cho nó. Bằng MLE, ta có thể chọn

trong đó # là hàm đếm số lượng khẳng định đúng khi chạy khắp phần tử của .

Hoặc bằng MAP với prior là Dirichlet Distribution (tương đương với kỹ thuật dễ hiểu hơn là Laplace Smoothing), ta chọn:

Thế là ta đã ước lượng xong . Còn đối với cách ước lượng , điều này phụ thuộc vào tập nguồn . Vì thế ta sẽ khảo sát kỹ ở ngay mục sau.

3. Naive Bayes cho inputs rời rạc

3. 1 Categorical features

Giả sử mỗi feature đều nhận các giá trị rời rạc thuộc tập hợp , tức là tuân theo categorical distribution của nó. Ta ký hiệu tham số:

Khi đó, với MLE, ta có ước lượng:

trong đó # là hàm đếm số lượng khẳng định đúng khi chạy khắp phần tử của .

Ta cũng có thể dùng MAP và dễ dàng có được ước lượng:

Thành lập các ước lương này chính là bước train data. Thay các ước lượng đã lập được vào (1), ta sẽ có được Naive Bayes Classifier:

Cách này thường được áp dụng trong text classification với hai thuật toán tiêu biểu:

• Bernoulli event model: chính là Naive Bayes cho các feature là nhị phân, tức là tuân theo phân phối Bernoulli.
• Multinomial event model: còn được gọi với cái tên là Multinomial Naive Bayes, tuy nhiên mô hình này không phải là mỗi feature đều tuân theo phân phối Multinomial mà bản chất vẫn thuộc loại Categorical Features. Thực tế, việc đặt tên này là khá gây bối rối và khiến tôi mất khá nhiều thời gian để tìm hiểu. Chi tiết cụ thể hơn sẽ được trình bày ngay phần sau.

3.2 Multinomial Naive Bayes

Khi nhắc đến Naive Bayes, đây chính là thứ mà mọi người sẽ mặc định nghĩ đến. Tuy nhiên, thuật toán này không chỉ áp dụng y nguyên công thức ở phần 3.1, mà có một số sự điều chỉnh.

Nhìn vào , ta thấy rằng, nếu trong một document, thì một từ chỉ được đếm 1 lần. Với text classification, điều này là còn khá yếu. Ví dụ, ta muốn phân loại email thành spam/normal. Nếu chỉ dùng Bernoulli event model (là áp dụng trực tiếp của ) thì rõ ràng “Buy product” hay “Buy Product Buy Product Buy Product Buy Product” đều có chung một ước lượng. Ta cần một ước lượng chính xác hơn, gắn liền với tần suất nó suất hiện trong văn bản.

Trước khi đi vào phần điều chỉnh, ta có một số quy ước. Đầu tiên, ta viết lại tập dataset cho hợp hơn với bài toán text classification:

trong đó là một document, là class của nó. Giả sử document là một dãy từ, gồm:

Tất cả các từ thuộc tất cả documents đều thuộc cùng một tập vocabulary (cũng có người gọi là dictionary), tức là

Để tạo ra được ước lượng gắn liền với tần suất mà từ xuất hiện, trước tiên ta gọi

tức là “banh các documents ra”.

Bây giờ chính là phần điều chỉnh. Vẫn như trên, ta vẫn có ký hiệu tham số:

Với MLE, ta có ước lượng:

trong đó # là hàm đếm số lượng khẳng định đúng khi chạy khắp phần tử của . Lưu ý là không đổi. Rõ ràng với sự điều chỉnh này, tần số xuất hiện của 1 từ sẽ có tác động lớn hơn trong việc phân loại.

Ngoài ra, nhìn vào ta cũng thấy rằng ước lượng không phụ thuộc vào nữa, nên ta đặt:

Vậy, với một document để test , ta có hàm likelihood:

Ở bước implementation, để đơn giản hơn và tiết kiệm bộ nhớ, người ta thường cho và tạo một vector gồm các tần số của các từ trong document (đây gọi là kỹ thuật bags of words). Chú ý rằng có chiều chính là số từ phân biệt trong và từ lặp lại lần, ta có Multinomial Naive Classifier:

Bàn về cách đặt tên “Multinomial Naive Bayes (MNB)”: Rõ ràng đây là một cách đặt tên rất gây hiểu nhầm khi mỗi feature không hề tuân theo Multinomial distribution. Có người lý giải rằng: “Trong cộng đồng DS-AI, Multinomial và Categorical Distribution có thể dùng thay thế cho nhau nên MNB với Categorical NB là một.” Cách lý giải này khá hợp lý khi MNB chính là CNB khi mỗi feature là một word thuộc chung một vocabulary. Thật ra, nếu ta coi mỗi document tuân theo Multinomial Distribution với các xác suất ,, tức là:

thì ta vẫn sẽ thu được Classifier y như . Điều này giải thích cho “Multinomial” trong cái tên. Nhưng ngay cả như thế, nó cũng không hề “Naive Bayes” khi không tuân theo . Tóm lại, cái tên khá là “lú”! Tuy vậy, đây là tên được dùng khá phổ biến, kể cả Wikipedia và scikit-learn.

4. Naive Bayes cho inputs liên tục - Gaussian Naive Bayes

Giả sử mỗi feature đều nhận các giá trị liên tục. Ta có thể giả sử nó tuân theo phân phối chuẩn, ta hoàn toàn có thể chọn phân phối liên tục khác nhưng phân phối chuẩn là lựa chọn phổ biến. Tức là ta chọn .

Bằng MLE, ta cũng có thể có được các ước lượng:

trong đó là feature thứ của vector , là indicator function.

5. Naive Bayes với binary classification chính là một Linear Classifier! (đọc thêm)

Ta sẽ chứng minh khẳng định ở tiêu đề với MNB.

Giả sử . Ta sẽ lần lượt tính likelihood:

với lúc này là số chiều dữ liệu sau khi dùng kỹ thuật Bags of Words, là vector các tham số .

Tương tự, ta cũng có:

Ta đặt

Lúc này, ta có

Như vậy

Với GNB, ta cũng có thể thu được kết quả tương tự nếu ta giả sử:

Kết quả đó có dạng:

Như vậy ta có điều phải chứng minh.

Nhận xét: Công thức của GNB có hình thức rất giống với Logistic Regression, nên ta có thể coi hai biến thể này là “họ hàng” của nhau. Tuy nhiên, mặc dù cùng một công thức, ta vẫn cần nhớ rằng tham số thay vào của mỗi mô hình là khác nhau! Rộng hơn, GNB là Generative model, còn LR là Discriminative model.