Mục Lục
Giới thiệu
Trong bài toán phân loại dựa trên xác suất (Probabilistic classification), mục tiêu là gán (map) dữ liệu đầu vào cho nhãn của lớp có xác suất cao nhất. Quá trình huấn luyện (training) mô hình bao gồm việc điều chỉnh các tham số sao cho xác suất dự đoán càng gần với xác suất thực tế (ground-truth probabilities) càng tốt.
Chúng ta xét mô hình với nhãn các lớp là phân biệt. Ví dụ, trong bài toán phân loại ảnh số từ cơ sở dữ liệu MNIST, với dữ liệu đầu vào là danh sách các ảnh và đầu ra là các số từ 0 đến 9. Mô hình sẽ dự đoán xác suất đầu ra (cho mỗi ảnh đầu vào) là một danh sách 10 số, mỗi số là xác suất mà ảnh đầu vào thuộc lớp tương ứng, và tổng của chúng bằng 1.
Trong quá trình training, giả sử chúng ta có ảnh đầu vào là ảnh mang số “5” và mô hình được kỳ vọng sẽ dự đoán xác suất đầu ra gần với ground-truth class probability, nghĩa là xác suất tại vị trí số 5 của output đạt giá trị gần 1. Giả sử mô hình dự đoán phân bố xác suất output khác biệt so với target, với p = [0.1, 0.1, 0.05, 0.05, 0.1, 0.2, 0.1, 0.1, 0.1, 0.1], thì chúng ta cần điều chỉnh tham số của mô hình sao cho tiến gần tới phân phối ground truth q = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0].
Vậy, thế nào là điều chỉnh tham số để tiến gần tới? Chúng ta cần một cách để đánh giá sự khác biệt giữa p và q.
Có nhiều cách để đánh giá sự khác biệt này. Bài viết này sẽ đi sâu vào một trong số những cách phổ biến nhất: cross-entropy, và đánh giá tại sao cross-entropy lại phù hợp cho bài toán phân loại (classification).
Entropy
Mã, Từ Mã (Codeword), Mã Hóa-Giải Mã (Encode-Decode)
Câu chuyện giữa Alice và Bob về an toàn bảo mật thông tin có một diễn biến mới. Bob rất thích động vật, anh ấy có thể nói chuyện cả ngày với Alice về chủ đề này. Đặc biệt, khi nói chuyện với Alice, anh ấy chỉ sử dụng 4 từ: “dog”, “cat”, “fish” và “bird”.
Một lần, Bob đi du lịch xa và liên lạc với Alice qua tin nhắn, mã hoá tin nhắn chỉ gồm các ký tự nhị phân 0 và 1. Tin nhắn của Bob như sau:
Dãy bit nhị phân được sử dụng trong tin nhắn giữa Bob và Alice.
Để thuận tiện cho việc trao đổi, Bob và Alice thống nhất mã hoá tin nhắn bằng cách thay thế mỗi từ thành một chuỗi nhị phân (codeword) độ dài 2 bit tương ứng và ghép lại thành một chuỗi tin nhắn duy nhất. Cụ thể:
Bảng mã hóa 2-bit ban đầu được Bob và Alice thống nhất sử dụng.
Việc giải mã thông tin diễn ra như sau:
Quá trình giải mã tin nhắn ban đầu sử dụng mã 2-bit.
Mọi chuyện diễn ra suôn sẻ cho đến khi giá cước tăng lên đáng kể. Để giảm chi phí, Bob và Alice quyết định tìm cách làm cho tin nhắn ngắn hơn nhưng vẫn đảm bảo đầy đủ thông tin.
Alice nhận thấy rằng tần suất các từ trong tin nhắn của Bob không đồng đều. Bob thực sự thích “dog”, anh ấy chủ yếu nói về “dog”, thỉnh thoảng mới nhắc đến “cat”, “fish” và “bird”. Tần suất cụ thể như bảng thống kê dưới đây:
Bảng thống kê tần suất xuất hiện các từ “dog”, “cat”, “fish”, “bird” trong tin nhắn của Bob.
Phân tích chi tiết hơn về codeword mà 2 bạn đã dùng bằng biểu đồ dưới đây, với: Trục tung – Thể hiện xác suất xuất hiện của 1 word; Trục hoành – Độ dài của codeword tương ứng; Diện tích – Expected codeword length: Độ dài kỳ vọng hay độ dài trung bình của một codeword được gửi đi, ở đây = 2 bit:
Biểu đồ thể hiện độ dài codeword và xác suất xuất hiện tương ứng của các từ ban đầu.
Mục tiêu của cả hai là cực tiểu hóa độ dài của tin nhắn gửi đi. Họ nhận ra rằng có thể lựa chọn codeword có độ dài khác nhau. Theo thuật toán tham lam, từ nào xuất hiện nhiều (ví dụ: “dog”) sẽ ưu tiên chọn codeword ngắn hơn, và ngược lại, từ nào xuất hiện ít (ví dụ: “bird”) sẽ có codeword dài hơn. Cụ thể:
Bảng mã hóa mới với độ dài codeword khác nhau dựa trên tần suất xuất hiện.
Biểu đồ phân tích cho bộ codeword mới như sau:
Biểu đồ thể hiện độ dài codeword và xác suất xuất hiện tương ứng của các từ sau khi tối ưu.
Trong biểu đồ trên, độ dài của codeword phổ biến ngắn hơn, trong khi độ dài của codeword hiếm dài hơn. Diện tích được tính toán cũng nhỏ hơn, tương ứng với độ dài trung bình của codeword là 1.75 bit. Bằng cách sử dụng codeword có độ dài khác nhau, độ dài trung bình của codeword đã giảm.
Tại sao không dùng tất cả codeword độ dài bằng 1? Với cách này, bạn sẽ gặp phải vấn đề nhập nhằng (ambiguity) trong quá trình giải mã (decode) (sẽ giải thích cụ thể hơn ở phần tiếp).
Với ví dụ trên cùng với phân bố xác suất P(dog) = 0.5, P(cat) = 0.25, P(fish) = 0.125, P(bird) = 0.125, 1.75 là giá trị tối ưu, nghĩa là không thể tìm được bộ codeword nào phù hợp mà có giá trị trung bình nhỏ hơn 1.75.
Như vậy, với mỗi bộ phân bố xác suất cho trước, ta hoàn toàn xác định được giá trị tối ưu của code, hay độ dài trung bình tối ưu của codeword. Giá trị này được gọi là Entropy.
Giá trị Entropy thể hiện độ dài trung bình tối ưu của codeword.
Không gian codeword
Chúng ta có 2 codeword độ dài 1 là: 0 và 1; 4 codeword độ dài 2 là: 00, 01, 10, 11; và tổng quát là 2n codeword độ dài n.
Không gian codeword với các độ dài khác nhau.
Bạn hoàn toàn có thể tùy ý lựa chọn codeword có độ dài bất kỳ. Ví dụ như hình trên là 8 codeword độ dài 3, bạn có thể lựa chọn một cách tổ hợp các codeword có độ dài khác nhau như bạn chọn 2 codeword độ dài 2, 4 codeword độ dài 3 chẳng hạn.
Vậy điều gì quyết định đến việc chọn lựa codeword với độ dài khác nhau?
Bob mã hóa tin nhắn bằng cách thay thế từng word bằng codeword tương ứng và ghép lại thành một chuỗi mã hóa nhị phân.
Quá trình mã hóa tin nhắn sử dụng codeword có độ dài khác nhau.
Cần lưu ý rằng, làm thế nào để từ chuỗi mã hóa bạn có thể giải mã ngược lại thành chuỗi các codeword. Nếu như chọn codeword có độ dài như nhau thì việc này khá đơn giản. Tuy nhiên, khi lựa chọn codeword độ dài khác nhau, việc giải mã ngược lại được thành chuỗi codeword là rất quan trọng.
Thực tế, bạn cần chọn bộ codeword sao cho việc giải mã là duy nhất. Bằng không, bạn sẽ rơi vào tình trạng “nhập nhằng”, nghĩa là từ một chuỗi mã hóa sẽ có nhiều chuỗi giải mã thỏa mãn. Ví dụ, nếu bạn chọn cả “0” và “01” trong bộ codeword, thì với chuỗi mã hóa “01” bạn sẽ khó quyết định đâu là codeword phù hợp được dùng để giải mã cho 2 bit đầu. Do đó, bạn sẽ không chọn bộ codeword là prefix code – nghĩa là không codeword nào là prefix của codeword trong cùng một bộ.
Để dễ dàng cho việc lựa chọn prefix code, bạn sẽ sử dụng một phương pháp gọi là “hi sinh”, nghĩa là khi bạn đã chọn một codeword, ví dụ như “0”, thì toàn bộ không gian codeword bắt đầu bằng “0” sẽ không được sử dụng, ví dụ bạn sẽ không được dùng các codeword như: “00”, “01”, … bởi nó sẽ gây ra tình trạng “nhập nhằng” cho quá trình giải mã.
Không gian codeword bị “hi sinh” khi một codeword được chọn.
Với “0” trong tổng số codeword bắt đầu bằng “0”, như vậy nếu codeword “0” được chọn, bạn sẽ phải “hi sinh” tổng số codeword. Đây là “chi phí” bạn phải trả để có được một codeword độ dài 2.
Mã tối ưu (Optimal Encoding)
Ở đây, hãy coi việc này giống như bạn đang có một ngân khố đầy đủ với tỷ lệ 100%, mỗi khi bạn chọn một codeword độ dài L thì theo thuyết “hi sinh” ở trên bạn phải “hi sinh” một “chi phí” với tỷ lệ codeword là 1/2L.
Chi phí cho codeword có độ dài là 1/20 = 1 – tức toàn bộ codeword – nghĩa là nếu bạn chọn codeword có độ dài 0 thì bạn sẽ không được chọn bất kỳ codeword nào khác nữa; Chi phí cho codeword độ dài 1, ví dụ như codeword “0”, là 1/21 = 1/2 vì có số lượng codeword bắt đầu bằng “0”; Chi phí cho codeword độ dài 2, ví dụ “10”, là 1/22 = 1/4 vì có số lượng codeword bắt đầu bằng “10”. Tổng quát, Chi phí cho codeword giảm theo hàm lũy thừa của độ dài codeword.
Chi phí cho codeword giảm theo hàm lũy thừa của độ dài codeword.
Công thức tính Entropy
Chi phí cho codeword độ dài L là 1/2L, hay ngược lại nếu ta biết P(x) của 1 codeword thì ta có thể tính được độ dài của codeword như sau: L = log2(1/P(x)) = -log2(P(x)). Nếu bạn “tiêu” một chi phí P(x) cho codeword x, độ dài của codeword x sẽ là -log2(P(x)).
Với một phân bố xác suất cụ thể P, ta xác định được độ dài trung bình ngắn nhất của bộ codeword – được gọi là “entropy” của P, kí hiệu là H(P). Ta có:
Nói một cách khác, nếu x là một sự kiện ngẫu nhiên rời rạc (có thể nhận các giá trị là 1..n), P(x) là xác suất xảy ra của giá trị x, thì Entropy chính là giá trị kỳ vọng số bits được mã hoá tối ưu. Như vậy, trung bình mỗi khi cần nhắn tin, Bob và Alice cần sử dụng ít nhất H(P) bit.
Entropy mô tả độ “không chắc chắn” của thông tin và là một cách để bạn định lượng được thông tin này. Giả sử nếu bạn biết chắc chắn có 2 sự kiện xảy ra với xác suất 50/50, bạn chắc chắn chỉ cần dùng 1 bit để nhắn tin. Hoặc nếu bạn biết có 16 sự kiện xảy ra với xác suất như nhau (1/16) thì bạn chắc chắn chỉ cần 4 bit để nhắn tin.
Cross Entropy
Cross-entropy có thể được xem là một “tool” để đo lường sự khác biệt giữa các phân phối.
Trở lại với câu chuyện của Bob và Alice. Trước đây, 2 bạn chỉ nói tới sự quan tâm của Bob về 4 loại động vật: dog, cat, fish và bird, đặc biệt sở thích của Bob là dog. Bây giờ, Alice cũng thích cả 4 loại động vật trên như Bob, nhưng cô thích nói về “cat” hơn cả. Như vậy, 2 người có cùng “vocabulary” nhưng khác nhau về tần suất cho từng loại. Bob có thể nói cả ngày về chủ đề “dog”, trong khi đó Alice lại có thể nói cả ngày với chủ đề “cat”.
Cụ thể như hình dưới đây:
So sánh tần suất các từ giữa Bob và Alice.
Ban đầu, Alice gửi tin cho Bob cùng sử dụng bộ code của Bob. Tuy nhiên, tin nhắn của Alice lại có vẻ dài hơn so với mong đợi của 2 bạn. Bộ code của Bob đã được tối ưu dựa trên phân bố xác suất của Bob. Alice đã sử dụng bộ code được tối ưu (suboptimal) dựa trên phân bố xác suất của riêng mình. Do đó, trong khi độ dài trung bình codeword của Bob là H(Bob) khi sử dụng bộ code của Bob là 1.75 bit, thì độ dài trung bình codeword của Alice khi sử dụng bộ code của Bob lại dài hơn là 2.0 bit.
Vậy làm sao để đánh giá 2 codeword này?
Cross-Entropy là độ đo đánh giá độ dài trung bình số lượng bit cần thiết để mã hoá thông điệp với phân bố xác suất là p, sử dụng bộ codeword tối ưu (có phân bố xác suất là q).
Nếu bạn nghĩ phân bố xác suất là một tool để mã hoá thông tin, thì entropy là độ đo để đánh giá số lượng bit bạn cần để sử dụng tool chuẩn – đây là tool đã được tối ưu vì bạn không thể mã hoá sử dụng số bit trung bình ít hơn.
Ngược lại, cross-entropy là số lượng bit bạn cần nếu bạn mã hoá thông tin của tool chuẩn sử dụng tool sai. Nghĩa là khi mã hoá thông điệp cho sự kiện x thay vì sử dụng -log(p(x)) bit, bạn lại dùng -log(q(x)) bit.
Ta có:
Ví dụ ta có:
- Cross-entropy luôn luôn lớn hơn Entropy. Việc mã hoá sử dụng tool sai sẽ luôn phải sử dụng nhiều bit hơn.
- Cross-entropy không có tính chất đối xứng, nghĩa là H(p, q) != H(q, p).
Ta có thể có một vài kịch bản sau:
- Bob sử dụng Bob code: 1.75 bit
- Alice sử dụng Bob code: 2.0 bit
- Alice sử dụng Alice code: 1.75 bit
- Bob sử dụng Alice code: 2.0 bit
So sánh entropy và cross-entropy trong các trường hợp khác nhau.
Tại sao cross-entropy lại quan trọng?
Cross-entropy cho biết mức độ khác biệt giữa 2 phân bố xác suất. Sự khác biệt giữa phân bố p và q càng lớn, thì cross-entropy của p đối với q sẽ càng lớn hơn entropy của p.
Cross-entropy tăng khi sự khác biệt giữa hai phân phối xác suất tăng.
Tương tự, sự khác biệt giữa phân bố p và q càng lớn, thì cross-entropy của q đối với p sẽ càng lớn hơn entropy của q.
Cross-entropy tăng khi sự khác biệt giữa hai phân phối xác suất tăng.
KL Divergence – KL phân kỳ
KL Divergence đo khoảng cách giữa hai phân phối xác suất.
Điều thực sự thú vị ở đây chính là sự khác biệt giữa entropy và cross-entropy. Có thể nói nó là sự khác biệt hay khoảng cách giữa 2 phân bố xác suất p và q. Nếu 2 phân bố xác suất này giống nhau thì khoảng cách là 0 và ngược lại, sự khác biệt càng lớn thì giá trị này càng lớn.
Và nó được gọi là KL divergence:
D(p || q) = Σ p(x) * log(p(x)/q(x)) = H(p, q) - H(p)
với H(p, q) là cross-entropy; H(p) là entropy của P.
Lưu ý:
- Việc cực tiểu hóa cross-entropy tương đương với việc cực tiểu hóa KL phân kỳ.
- Cross entropy và KL phân kỳ được sử dụng phổ biến trong Machine Learning. Chúng ta thường muốn một phân bố xác suất nào đó tiến gần với một phân bố khác. Ví dụ như chúng ta muốn phân bố của dự đoán tiến gần với phân bố cơ sở. KL phân kỳ cho ta một cái nhìn tự nhiên về vấn đề trên, tuy nhiên, có vẻ như cross entropy lại được biết đến và sử dụng rộng rãi hơn.
Khả năng dự đoán (Likelihood)
Mục tiêu là điều chỉnh mô hình để tối đa hóa khả năng dự đoán đúng.
Chúng ta sử dụng cross-entropy để đánh giá sự khác biệt giữa 2 phân bố xác suất y và y_hat, sau đó tính lỗi (loss) dựa trên tổng cross entropy của toàn bộ dữ liệu training.
Cụ thể, ta có hàm mục tiêu như sau:
H({y^(n)}, {y_hat^(n)}) = Σ H(y^(n), y_hat^(n))
Một cách tiếp cận phổ biến khác là chúng ta tiến hành điều chỉnh tham số mô hình sao cho likelihood của mô hình với dữ liệu đầu vào đạt max. Với bài toán phân lớp, chúng ta thường hay sử dụng mô hình phân biệt (discriminative model) ở đó dữ liệu training thường bao gồm cả dữ liệu và nhãn cần dự đoán. Nói cách khác, chúng ta thường sẽ dự đoán ground-truth labels với dữ liệu cho trước.
Với giả sử dữ liệu của bài toán là độc lập và phân bố đồng nhất (independent and identically distributed), likelihood sẽ được tính như sau:
Vậy thế nào là likelihood? Đó chính là phần tử cụ thể của y_hat^(n) tương ứng với ground-truth label của x^(n).
Ví dụ trong bài toán phân loại ảnh số MNIST: Với ảnh training thứ nhất có nhãn là “3”, thì likelihood sẽ là phần tử thứ 3-th của kết quả dự đoán y_hat^(1), hay y_hat^(1)3.
Tiếp tục giả sử chúng ta có tất cả 3 ảnh trong training data là các số 3, 5, 8 với các phân bố ground-truth là:
y^(1) = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
y^(2) = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], và
y^(3) = [0, 0, 0, 0, 0, 0, 0, 0, 1, 0].
Mô hình sẽ dự đoán 3 phân bố tương ứng là:
y_hat^(1) = [0.1, 0.05, 0.1, 0.3, 0.05, 0.05, 0.1, 0.1, 0.05, 0.1],
y_hat^(2) = [0.05, 0.1, 0.05, 0.1, 0.1, 0.2, 0.05, 0.1, 0.15, 0.05], và
y_hat^(3) = [0.05, 0.05, 0.1, 0.05, 0.15, 0.1, 0.05, 0.1, 0.2, 0.15].
Và likelihood của cả training data sẽ là:
L = y_hat^(1)<sub>3</sub> * y_hat^(2)<sub>5</sub> * y_hat^(3)<sub>8</sub> = 0.3 * 0.2 * 0.2 = 0.012
Vậy nhiệm vụ của chúng ta là điều chỉnh tham số mô hình sao cho likelihood đạt max.
Likelihood
Đo lường và tối ưu hóa likelihood để cải thiện độ chính xác của mô hình.
Cùng phân tích cụ thể hơn về công thức tính likelihood trên:
Thứ nhất, hàm logarit là hàm đơn điệu, do vậy việc cực đại hoá likelihood sẽ tương đương với việc cực đại hoá log likelihood, hay ngược lại là tương đương với việc cực tiểu hoá negative log likelihood.
Thứ hai, log likelihood của y_hat^(n) được tính khá đơn giản chính là log của phần tử tương ứng trong y_hat^(n), cụ thể hơn là phần tử thứ i thỏa mãn y^(n)i = 1.
Do đó, chúng ta có thể viết lại công thức tính log likelihood cho mẫu training data thứ n đơn giản hơn như sau:
log(y_hat^(n)) = Σ y^(n)<sub>i</sub> * log(y_hat^(n)<sub>i</sub>)
và negative log likelihood cũng được viết lại như sau:
-log(y_hat^(n)) = - Σ y^(n)<sub>i</sub> * log(y_hat^(n)<sub>i</sub>)
Và đây chính là công thức tính tổng tất cả cross-entropy trên toàn bộ training data:
Thảo luận
Thảo luận về vai trò của cross-entropy trong việc xây dựng mô hình xác suất.
Khi xây dựng mô hình xác suất cho bài toán phân lớp có các lớp phân biệt lẫn nhau, chúng ta cần đánh giá sự khác biệt giữa xác suất dự đoán và xác suất ground-truth và trong quá trình training chúng ta sẽ điều chỉnh tham số sao cho sự khác biệt là nhỏ nhất.
Cross-entropy là một lựa chọn phù hợp cho bài toán phân lớp trên vì hai lý do:
- Thứ nhất, việc cực tiểu hoá cross-entropy cho phép chúng ta tìm được y_hat thỏa mãn số bits tối thiểu cần thiết để mã hoá thông tin từ y sử dụng y_hat.
- Thứ hai, việc cực tiểu hoá cross-entropy tương đương với việc cực tiểu hoá negative log likelihood, hay chính là việc đánh giá trực tiếp khả năng dự đoán của mô hình.
Nguồn tham khảo
- Visual Information Theory