Mô hình n-gram và bài toán xác suất bằng không
Mô hình n-gram và bài toán xác suất bằng không
Đếm cụm từ thì dễ, nhưng ngữ liệu nào cũng thiếu. Mô hình đếm thẳng sẽ gán xác suất đúng bằng 0 cho những câu hoàn toàn hợp lệ, và một số 0 trong phép nhân là đủ để giết cả câu.
Mô hình ngôn ngữ trả lời một câu hỏi duy nhất: cho vài từ đã có, từ tiếp theo nhiều khả năng là gì. Cách cũ nhất và cũng dễ hiểu nhất là đếm. Muốn biết P(máy | học) thì đi khắp ngữ liệu, đếm xem học xuất hiện bao nhiêu lần và trong số đó bao nhiêu lần từ đi sau là máy, rồi chia. Đó là toàn bộ mô hình n-gram: bậc 1 không nhìn từ nào phía trước, bậc 2 nhìn một từ, bậc 3 nhìn hai từ.
Vấn đề lộ ra ngay khi bạn thử một câu bình thường. Ngữ liệu dù to đến đâu cũng chỉ chứa một phần rất nhỏ những cặp từ có thể có, nên phép chia ở trên rất hay ra tử số bằng 0. Mà xác suất của cả câu là tích các xác suất từng bước, nên chỉ cần một bước bằng 0 là cả câu bằng 0, bất kể những bước còn lại đẹp cỡ nào. Sim dưới đây để bạn tự tạo ra tình huống đó rồi tự chữa.
bậc đang dùng = 2|V| = 10k = 0.00count(ngữ cảnh) = 5mẫu số = 5.00| Từ tiếp theo | đếm(ngữ cảnh, từ) | tử số = đếm + k | mẫu số | P(từ | ngữ cảnh) | độ lớn |
|---|---|---|---|---|---|
| máy | 3 | 3.00 | 5.00 | 0.6000 | |
| toán | 2 | 2.00 | 5.00 | 0.4000 | |
| bạnchưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| họcchưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| mỗichưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| ngàychưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| nhanhchưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| rấtchưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| thíchchưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 | |
| tôichưa từng thấy | 0 | 0.00 | 5.00 | 0.0000 |
học. Không phải "rất nhỏ", mà là 0: bất cứ câu nào chứa một trong các cặp đó sẽ có tích xác suất bằng 0. Kéo k lên khỏi 0 để xem cả cột sống lại.| Bước | Từ | Ngữ cảnh dùng | đếm | mẫu số | P từng bước | Tích luỹ |
|---|---|---|---|---|---|---|
| 1 | tôi | rỗngđầu câu, bậc 1 | 3 | 22.00 | 0.1364 | 0.136364 |
| 2 | thích | tôi | 2 | 3.00 | 0.6667 | 0.090909 |
| 3 | học | thích | 3 | 3.00 | 1.0000 | 0.090909 |
| 4 | toán | học | 2 | 5.00 | 0.4000 | 0.036364 |
| 5 | mỗi | toán | 0 | 0 · không chia được | 0.0000 | 0 |
| 6 | ngày | mỗi | 1 | 1.00 | 1.0000 | 0 |
Trước khi tin bất kỳ con số nào ở dưới, biết trước một chuyện: sim này có bảy lựa chọn cài đặt là quy ước chứ không phải chân lý, từ cách đếm mẫu số tới cách lùi bậc và cơ số của log. Đổi một quy ước là mọi con số in ra đổi theo. Chúng được liệt kê đầy đủ ở mục Những quy ước của sim này cuối bài, và những cái ảnh hưởng trực tiếp tới đoạn bạn đang đọc thì được nhắc lại ngay tại chỗ.
Ở trạng thái mặc định, bảng đang nói gì
Ngữ liệu có 5 câu, 22 token và từ vựng gồm 10 từ, nên |V| = 10. Ngữ cảnh đang xét là học, và học xuất hiện 5 lần, lần nào cũng có từ đi sau, nên count(học) = 5. Trong 5 lần đó, 3 lần từ tiếp theo là máy và 2 lần là toán.
Với k = 0 thì bảng đọc thẳng ra từ hai con số đó: P(máy | học) = 3/5 = 0,6000 và P(toán | học) = 2/5 = 0,4000. Tám từ còn lại của từ vựng nhận đúng 0, không phải một số bé, mà là số không tròn trĩnh. Hàng của chúng tô đỏ và thanh ngang biến mất hẳn. Cột xác suất vẫn cộng lại đúng 1, vì 0,6 + 0,4 đã dùng hết khối lượng.
Điều đó nghĩa là mô hình đang khẳng định một chuyện rất mạnh: sau học thì không thể có tôi, không thể có bạn, không thể có bất cứ từ nào ngoài hai từ nó đã thấy. Khẳng định ấy sai, và nó sai chỉ vì ngữ liệu bé. Đây chính là nghĩa của cụm "dữ liệu thưa": không phải mô hình thiếu chính xác một chút, mà là mô hình phát biểu điều bất khả thi ở những chỗ nó chưa được nhìn.
Kéo thanh k lên và nhìn cái giá phải trả
Làm mượt add-k cộng thêm k vào mọi tử số, và để cột vẫn cộng lại 1 thì mẫu số phải cộng thêm đúng k nhân với số từ trong từ vựng:
P(w | ngữ cảnh) = (đếm(ngữ cảnh, w) + k) / (đếm(ngữ cảnh) + k × |V|)
Cái |V| ở mẫu số là chỗ dễ quên nhất và cũng là chỗ quan trọng nhất. Quên nó thì mọi con số riêng lẻ vẫn trông hợp lý nhưng cả cột cộng lại lớn hơn 1, tức là bạn không còn cầm một phân phối xác suất nữa. Đây là loại lỗi lọt lưới dễ nhất, vì nó không làm hỏng con số nào đủ để bạn nhận ra khi liếc qua. Bạn tự bắt được nó ngay trên trang: dòng Tổng cả cột xác suất ngay dưới bảng phải luôn đọc 1.000000, với mọi ngữ cảnh và mọi giá trị k. Nếu có lúc nào nó đọc ra một số lớn hơn 1 thì |V| đã rơi mất khỏi mẫu số. Cổng kiểm của bài quét lại đúng bất biến đó trên mọi ngữ cảnh của vài ngữ liệu và nhiều giá trị k.
Kéo thanh tới k = 1, tức làm mượt Laplace cổ điển. Mẫu số thành 5 + 1 × 10 = 15. Bây giờ P(máy | học) = 4/15 = 0,2667, P(toán | học) = 3/15 = 0,2000, và mỗi từ trong tám từ chưa từng thấy nhận 1/15 = 0,0667. Không còn số 0 nào. Nhưng nhìn dòng "khối lượng xác suất chuyển cho từ chưa từng thấy": 53,3%. Hơn một nửa khối lượng vừa bị lấy khỏi hai từ mà ngữ liệu thật sự quan sát được, đem chia đều cho tám từ mà ngữ liệu chưa bao giờ thấy đứng ở đó.
Kéo về k = 0,5 thì mẫu số là 10, P(máy | học) = 0,3500, và phần chuyển đi còn 40,0%. Vậy k là một cái núm đánh đổi: nhỏ quá thì mô hình vẫn còn số 0, lớn quá thì mô hình gần như quên mất nó đã đếm được gì.
Chỗ này mới là điểm đáng nhớ. Ở đây |V| chỉ có 10 mà add-k đã nuốt hơn nửa khối lượng. Một mô hình thật có từ vựng cỡ vài chục nghìn từ, nên với k = 1 thì mẫu số bị cộng thêm vài chục nghìn trong khi tử số chỉ cộng thêm 1. Toàn bộ số đếm thật gần như bị dìm chết dưới hằng số. Đó là lý do add-k được dạy để hiểu ý tưởng, nhưng hệ thống thật dùng những cách làm mượt tinh hơn nhiều như Kneser-Ney, vốn ước lượng phần khối lượng dành cho cái chưa thấy từ chính dữ liệu chứ không rải đều.
Lùi bậc: khi ngữ cảnh dài chưa từng xuất hiện
Có một kiểu hỏng khác hẳn kiểu trên. Ở trên, ngữ cảnh học có tồn tại, chỉ là cặp học với một từ nào đó thì chưa thấy. Nhưng nhiều khi chính ngữ cảnh chưa từng xuất hiện, và lúc đó mẫu số bằng 0. Chia cho 0 không ra số nhỏ, nó không ra gì cả.
Thử ngay: kéo k về 0 trước đã, rồi chọn bậc 3, gõ thích máy vào ô ngữ cảnh và tắt công tắc lùi bậc. Sim báo mẫu số bằng 0 và không vẽ bảng nào, vì cặp thích máy chưa bao giờ xuất hiện trong ngữ liệu. Bật công tắc lùi bậc lên: mô hình bỏ từ cũ nhất của ngữ cảnh, tụt từ bậc 3 xuống bậc 2 với ngữ cảnh còn lại là máy, và bảng hiện ra với mẫu số 2, P(mỗi | máy) = 0,5000 và P(rất | máy) = 0,5000. Khối vàng ở trên nói rõ nó vừa lùi về bậc mấy, vì nếu không nói thì bạn sẽ tưởng mình đang đọc số của bậc 3.
Bước kéo k về 0 không phải thủ tục thừa. Nếu bạn để nguyên k = 0,5 của đoạn trước rồi gõ thích máy, mẫu số không còn bằng 0 mà bằng 0 + 0,5 × 10 = 5, và sim vẽ ra một bảng đầy đủ trong đó cả mười từ đều nhận đúng 0,1000. Bảng ấy trông lành lặn nhưng nó là phân phối đều dựng lên từ không một quan sát nào: dòng "Số từ từng đứng sau ngữ cảnh này" đọc 0 / 10 và khối lượng chuyển cho từ chưa từng thấy đọc 100,0%. Đó là kiểu hỏng thứ ba, khó thấy hơn cả hai kiểu trên, vì làm mượt đã che mất chuyện mô hình chẳng biết gì.
Lùi bậc trong sim này là lùi thô: nó đổi ngữ cảnh rồi đọc thẳng con số của bậc thấp hơn, không nhân thêm hệ số phạt nào. Biến thể quen thuộc tên là stupid backoff nhân 0,4 mỗi lần tụt một bậc, để bậc thấp không được tin ngang bậc cao. Mục quy ước ở cuối bài nói rõ cái giá của lựa chọn này.
Câu thử mặc định cũng dính đúng chuyện này ở bước 5. Từ toán trong ngữ liệu chỉ nằm ở cuối dòng, nên nó chưa bao giờ có từ đi sau, tức count(toán) = 0. Với k = 0 và lùi bậc tắt, bước 5 không có mẫu số, xác suất 0, tích cả câu bằng 0. Bật lùi bậc: bước 5 tụt xuống bậc 1 và dùng xác suất unigram P(mỗi) = 1/22 = 0,0455, tích cả câu nhảy từ 0 lên 0,001653, log tự nhiên là -6,4052 và perplexity là 2,908.
Một số 0 giết cả câu, và log cho bạn thấy điều đó
Bảng câu thử nhân dồn từ trái sang phải, cột cuối là tích luỹ. Ở mặc định, bốn bước đầu đều đẹp, riêng bước 5 bằng 0, thế là cột tích luỹ tụt xuống 0 và nằm đó mãi. Log xác suất hiện âm vô cùng, perplexity hiện vô cùng. Đây không phải lỗi hiển thị: ln(0) thật sự không phải một số.
Người ta hay dùng log xác suất thay vì xác suất vì hai lý do. Thứ nhất, tích của nhiều số nhỏ hơn 1 tụt rất nhanh về gần 0 và máy tính sẽ làm tròn nó thành 0 thật, còn tổng các log thì không bị vậy. Thứ hai, log biến số 0 thành một dấu hiệu không thể bỏ qua thay vì một con số bé lẫn vào đám số bé khác.
Đặt k = 1 và tắt lùi bậc, cả câu thử có xác suất 3,228e-5, log -10,3412, perplexity 5,604. Con số 3,228e-5 nhỏ, nhưng nó là một xác suất thật, so sánh được với câu khác. Số 0 thì không so được với gì.
Còn một giới hạn mà làm mượt không chạm tới. Gõ tôi thích máy tính vào ô câu thử, để k = 1 và bật lùi bậc. Từ tính không có trong ngữ liệu nên không nằm trong V, sim gắn nhãn "ngoài từ vựng" và cho nó xác suất 0 dù k bằng bao nhiêu. Lý do đơn giản: add-k rải k lên |V| từ đã biết, mà từ ngoài V thì không có trong danh sách để được rải. Chú ý bước ngay trước đó: P(máy | thích) = 0,0769 tuy cặp thích máy chưa từng thấy, vì máy có trong V. Hai kiểu "chưa thấy" ấy hoàn toàn khác nhau, và chỉ kiểu thứ nhất được add-k cứu. Muốn xử lý từ lạ thì phải có một token <unk> ngay từ lúc dựng từ vựng, việc mà sim này cố tình không làm để bạn nhìn thấy khoảng trống.
Những quy ước của sim này và cái giá của từng cái
Bài này cố ý dùng ngữ liệu tí hon để mọi con số kiểm được bằng tay, nên có mấy chỗ khác với hệ thống thật, và có mấy lựa chọn chỉ là quy ước chứ không phải chân lý. Đây là chỗ gom đủ cả bảy, mỗi cái kèm cái giá của nó.
- Ngữ liệu 5 câu là quá bé để nói gì về ngôn ngữ. Con số
0,6và0,4trông sắc nét nhưng chúng đến từ đúng 5 lần quan sát. Với ngữ liệu thật, một phân phối bậc 2 thường tãi trên hàng chục từ tiếp theo chứ không gọn thành hai. Cái ngữ liệu bé cho bạn thấy đúng là cấu trúc của vấn đề, không phải độ lớn của nó. count(ngữ cảnh)ở đây là số lần ngữ cảnh xuất hiện và có từ đi sau, không phải số lần nó xuất hiện. Từmáycó mặt 3 lần nhưng chỉ làm ngữ cảnh 2 lần, vì một lần nó đứng cuối dòng. Đây là quy ước bắt buộc: chỉ có nó mới làm cột xác suất cộng lại đúng 1.- Không có ký hiệu đầu câu và cuối câu. Hệ thật thường chèn
<s>và</s>để mô hình học được từ nào hay mở đầu và từ nào hay kết thúc. Sim bỏ chúng cho bảng gọn, cái giá là những từ chỉ đứng cuối dòng trở thành ngữ cảnh chết, đúng như trường hợptoán. - Ngữ cảnh không vắt qua hai dòng, mỗi dòng của ô ngữ liệu là một câu riêng. Cái giá là chỗ xuống dòng trở thành một quyết định mô hình hoá chứ không phải chuyện trình bày: gộp hai dòng thành một sẽ đẻ thêm một cặp từ ở chỗ nối và làm đổi cả mẫu số lẫn cột xác suất, dù bạn không thêm một chữ nào. Thử gộp hai dòng đầu thành một dòng: số token vẫn là 22 và
|V|vẫn là 10, nhưngcount(máy)nhảy từ 2 lên 3 vàP(mỗi | máy)tụt từ0,5000xuống0,3333. - Đầu câu thử dùng ngữ cảnh cụt. Ở bước 1 chưa có từ nào phía trước nên sim dùng ngữ cảnh rỗng, tức bậc 1, và gắn nhãn "đầu câu" vào hàng đó. Cách khác cũng hợp lý là bỏ hẳn không chấm mấy bước đầu. Hai cách cho hai con số khác nhau, nên khi so perplexity của hai hệ, phải hỏi bên kia làm cách nào.
- Lùi bậc ở đây là lùi thô, không nhân hệ số phạt. Biến thể quen thuộc tên là stupid backoff nhân thêm 0,4 mỗi lần tụt một bậc, để bậc thấp không được tin ngang bậc cao. Mỗi bậc riêng lẻ trong sim vẫn là một phân phối cộng lại 1, nhưng vì các bậc không được trộn theo trọng số nào, cái bạn nhận không phải một mô hình chuẩn hoá chung cho mọi bậc.
- Log ở đây là log tự nhiên. Nhiều tài liệu dùng log cơ số 2 để đọc ra bit. Đổi cơ số chỉ là nhân với hằng số, thứ hạng giữa các câu không đổi, nhưng mọi con số in ra thì đổi hết.
- Tách token là hạ chữ thường, bỏ dấu câu, rồi cắt theo khoảng trắng. Nên
học máylà hai token chứ không phải một khái niệm, và đó là chỗ quy ước này đắt nhất với tiếng Việt: phần lớn từ tiếng Việt gồm hai âm tiết, nên bậc 2 ở đây nhiều khi mới chỉ nối được hai nửa của một từ chứ chưa bắt được quan hệ giữa hai từ. Hạ chữ thường nghĩa làHọcvàhọcđược gộp làm một, có lợi cho ngữ liệu bé nhưng xoá mất tín hiệu tên riêng. Chỉ dấu câu thường bị bỏ, còn gạch nối thì không:học-máyvẫn là một token.
Mô hình n-gram không phải là "gần đúng" ở chỗ nó chưa thấy, nó sai hẳn: nó gán xác suất 0, và số 0 trong một phép nhân xoá sạch mọi thứ khác. Vì vậy làm mượt không phải một bước tinh chỉnh thêm vào cho đẹp, nó là điều kiện để mô hình dùng được. Nhưng làm mượt cũng không miễn phí: k × |V| ở mẫu số lấy đi khối lượng thật, và từ vựng càng lớn thì lấy càng nhiều. Cuối cùng, add-k chỉ cứu được những cặp chưa thấy giữa các từ đã có trong từ vựng; từ hoàn toàn lạ vẫn nhận 0, và đó là một bài toán khác.
- 1Ngữ cảnh "học" có count bằng 5, từ vựng có 10 từ, và "bạn" chưa bao giờ đứng sau "học". Với k = 1 thì P(bạn | học) bằng bao nhiêu?
- 2Vì sao add-k với k = 1 lại hại nhiều hơn lợi khi từ vựng lớn tới vài chục nghìn từ?
- 3Câu thử có từ "tính", vốn không xuất hiện trong ngữ liệu. Kéo k lên 1 và bật lùi bậc thì xác suất của bước chứa "tính" ra sao?