ML101.07: Naive Bayes

Sau khi đã tìm hiểu về Gaussian Discriminant Analysis, ở bài này chúng ta sẽ tìm hiểu một thuật toán generative machine learning khác. Đó là Naive Bayes (NB), NB là một thuật toán đơn giản nhưng lại mang đến hiệu quả bất ngờ cho rất nhiều bài toán, đặc biệt là phân lớp cho dữ liệu rời rạc. Để tìm hiểu về NB, ta xét bài toán Sentiment Analysis như sau:

Cho một bình luận bất kỳ ở dạng văn bản, hãy phân loại bình luận này vào một trong ba loại: tích cực (positive), tiêu cực (negative), trung tính (neutral).

Đây là một bài toán rất cổ điển trong lĩnh vực xử lý ngôn ngữ tự nhiên và là điển hình cho bài toán phân loại văn bản. Để giải quyết bài toán này, trước hết chúng ta phải tìm cách biểu diễn văn bản thành vector đặc trưng. Một trong những cách đơn giản nhất chính là sử dụng phương pháp look-up dictionary. Ví dụ ta có từ điển %D% gồm những từ sau: %D=% {"sản", "này", "phẩm", "đẹp", "rất", "xấu", "tốt"}. Và một câu bình luận dạng văn bản: "sản phầm này rất đẹp". Khi đó, vector đặc trưng của của câu trên theo %D% được mô tả là:

$$x=\left[\begin{array}{c}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0\end{array}\right] $$

Trong đó, %x_j=1% nếu từ thứ %j% của từ điển %D% xuất hiện trong câu văn đầu vào, ngược lại %x_j=0%. Do đó, %x% là chỉ gồm các số %0% và %1% có số phần tử bằng với số từ trong từ điển hay %x \in \{0, 1\}^{|D|}%. Tương tự, ta có vector đặc trưng của câu: "sản phẩm này rất xấu" sẽ như sau:

$$x=\left[\begin{array}{c}1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0\end{array}\right]$$

Có thể thấy số lượng phần tử của vector %x% có thể là rất lớn vì nó tùy thuộc vào độ lớn của từ điển. Do đó, thực tế để cài đặt hiệu quả phương pháp này thì thông thường chúng ta chỉ chọn top K từ xuất hiện nhiều nhất trong dataset làm từ điển mà thôi. Ví dụ ta có top-5000 dictionary là từ điển gồm 5000 từ xuất hiện nhiều nhất trong tập dữ liệu. Khi đó, mỗi vector đặc trưng %x% sẽ có 5001 phần tử. Ta có thêm 1 phần tử thứ 5001 là do nếu chỉ lấy 5000 từ xuất hiện nhiều nhất trong tập dữ liệu thì ta cần một kí hiệu cho những từ còn lại, từ đó thường được goi là "Unknown".

Phân lớp Naive Bayes

Sau khi đã tìm được cách biễu diễn văn bản thành vector đặc trưng. Theo ý tưởng của Generative Machine Learning, ta thực hiện tìm %p(x\mid y)%. Để làm được điều đó, ta phải đặt một giả định rất quan trọng về mặt dữ liệu được gọi là Naive Bayes. Đó là ta xem tất cả các đặc trưng %x_i% độc lập có điều kiện (conditionally independent) theo %y%. Điều này có nghĩa rằng tất cả các từ trong vector đặc trưng hoàn toàn độc lập với nhau theo biến đầu ra %y%. Do đó ta có thể viết %p(x_i\mid y)=p(x\mid y, x_{j\neq i})%. Nhờ vào giả định này, ta có mô hình của %p(x\mid y)% như sau:

$$\begin{aligned}&p\left(x_1, \ldots, x_{|D|} \mid y\right)\\&=p\left(x_1 \mid y\right) p\left(x_2 \mid y, x_1\right) p\left(x_3 \mid y, x_1, x_2\right) \cdots p\left(x_{|D|} \mid y, x_1, \ldots, x_{|D|-1}\right)\\&=p\left(x_1 \mid y\right) p\left(x_2 \mid y\right) p\left(x_3 \mid y\right) \cdots p\left(x_{|D|} \mid y\right)\\&=\prod_{j=1}^{|D|} p\left(x_j \mid y\right)\end{aligned}$$

Có thể thấy, nếu không có giả định về sự độc lập của dữ liệu, thì ta không thể biến đổi từ bước thứ nhất sang bước thứ hai để có một kết quả đẹp như vậy.

Tương tự như Gaussian Discriminant Analysis, sau khi đã tính được %p(x\mid y)%, ta sử dụng định lý Bayes để tìm giá trị xác suất cho từng nhãn %y%:

$$p(y\mid x) = \frac{p(y)p(x\mid y)}{p(x)}$$

Ví dụ đối với bài toán sentiment analysis trong văn bản, thì ta chỉ cần so sánh các giá trị sau để có kết quả cuối cùng.

$$\begin{aligned}p(y=\text{positive}\mid x) &= \frac{p(y=\text{positive})p(x\mid y=\text{positive})}{p(x)}\\ p(y=\text{neutral}\mid x) &= \frac{p(y=\text{neutral})p(x\mid y=\text{neutral})}{p(x)}\\p(y=\text{negative}\mid x) &= \frac{p(y=\text{negative})p(x\mid y=\text{negative})}{p(x)}\end{aligned}$$

Tùy vào đặc trưng của bài toán thì ta có những biến thể khác nhau của Naive Bayes. Ví dụ với bài toán sentiment analysis như trên. Ta thấy công việc thật sự mà thuật toán cần làm là tìm %p(x\mid y)%. Mà %x% lại là vector %\{0, 1\}^{\mathbb{R}^{|D|}}%. Do đó, tại mỗi vị trí thứ %j% của %x% ta chỉ cần xác định xem từ %D_j% có tồn tại trong %x% hay không. Do chỉ cần xác định có hay không, nên ta gọi đây là Bernoulli event model của Naive Bayes. Ngoài ra, thay vì %x_j% chỉ nhận hai giá trị là %0% và %1% biểu thị sự hiện diện của %D_j%, ta có thể định nghĩa theo kiểu khác. Nếu ta định nghĩa %x_j% biểu hiện số lần mà %D_j% xuất hiện trong văn bản đầu vào thì %x_j% sẽ nhận được nhiều giá trị hơn (vì đây là số đếm). Khi đó, mô hình của chúng ta là Multinomial Naive Bayes. Vì vậy, tùy vào event model khác nhau của đặc trưng đầu vào, ta có những biến thể khác nhau của Naive Bayes. Khi so sánh với Gaussian Discriminant Analysis thì Naive Bayes thường vượt trội hơn so với GDA khi dùng cho dữ liệu rời rạc. Do đó, có khá nhiều bài toán ta chọn cách "rời rạc hóa" dữ liệu đầu vào để tận dụng sức mạnh của mô hình Naive Bayes. Ví dụ với dữ liệu về giá nhà, thay vì đầu vào là những số thực, ta có thể thực hiện rời rạc hóa rồi sau đó mới sử dụng Naive Bayes. Dưới đây là một ví dụ về bảng ánh xạ để rời rạc hóa dữ liệu giá nhà.