Tham lam và chùm tia
Tham lam và chùm tia
Mô hình ngôn ngữ chỉ cho bạn xác suất của từ tiếp theo. Biến chuỗi xác suất đó thành một câu là việc của thuật toán giải mã, và cách chọn rẻ nhất cũng là cách hay sai nhất.
Một mô hình ngôn ngữ không sinh ra câu. Nó chỉ trả lời một câu hỏi rất hẹp: cho phần đã viết, từ tiếp theo có khả năng là gì và với xác suất bao nhiêu. Muốn có cả câu, ta phải tự đi trên cây các khả năng đó. Cách rẻ nhất là giải mã tham lam: mỗi bước lấy từ có xác suất cao nhất, gắn vào, rồi đi tiếp và không bao giờ nhìn lại.
Vấn đề là một từ rẻ ở bước này có thể mở ra cả một vùng câu tốt ở bước sau, còn một từ đắt lại dẫn thẳng vào ngõ cụt. Giải mã chùm tia (beam search) giữ lại B giả thuyết tốt nhất ở mỗi bước thay vì đúng một, nên cửa sổ tìm kiếm rộng hơn. Sim dưới đây cho bạn kéo B và tự sửa từng con số log xác suất, kể cả sửa cho tới lúc bẫy biến mất.
Bảng log xác suất bên dưới do người soạn bài đặt ra để lộ đúng vài hiện tượng, nó không phải đầu ra của một mô hình ngôn ngữ nào. Vì vậy mọi con số trong bài chỉ nói lên cơ chế, không nói lên tỉ lệ: đừng suy từ đây ra rằng tham lam thua chùm tia bao nhiêu phần trăm trong một hệ dịch máy thật. Phạt độ dài dùng ở đây cũng chỉ là một biến thể trong nhiều biến thể đang được dùng.
| Hạng | Chuỗi | Độ dài | log P tổng | Mẫu số lp | Điểm sau chia |
|---|---|---|---|---|---|
| 1 | mèo ngủ | 2 | -1.70 | 1.000 | -1.700 |
lp = (5 + len)^alpha / 6^alpha. Ở alpha = 0 nó bằng đúng 1 nên cột điểm trùng cột log P tổng. Đây là biến thể của Wu và cộng sự năm 2016, không phải công thức duy nhất: chia cho đúng độ dài, hoặc cộng một phần thưởng cố định mỗi từ, đều là những biến thể được dùng và chúng cho thứ hạng khác nhau.| Bước | Ứng viên | Giữ | Cắt |
|---|---|---|---|
| 1 | 3 | 1 | 2 |
| 2 | 2 | 1 | 1 |
| Trạng thái hiện tại | Từ tiếp theo | log P của từ | Cộng dồn tới đó |
|---|---|---|---|
| gốc | mèo | -0.10 | |
| con | -0.30 | ||
| chú | -2.60 | ||
| mèo | ngủ | -1.70 | |
| kêu | -2.30 | ||
| con | mèo | -0.50 | |
| chó | -2.20 | ||
| chú | mèo | -2.65 | |
| con mèo | nằm | -1.20 | |
| ngủ | -1.40 | ||
| con chó | sủa | -2.50 | |
| chú mèo | ngủ | -2.75 | |
| con mèo nằm | trên | -1.40 | |
| con mèo nằm trên | tấm | -1.70 | |
| chiếu | -3.20 | ||
| con mèo nằm trên tấm | thảm | -1.80 |
-9 tới 0, vì log xác suất không thể dương, và khi kẹp thật sự xảy ra thì có một dòng báo ngay phía trên bảng. Ở alpha = 1 mẫu số của chuỗi ba từ là 8/6 = 1.333, của chuỗi sáu từ là 11/6 = 1.833.Đọc cái vừa xảy ra
B = 1 chính là tham lam. Khi chùm chỉ giữ một giả thuyết, việc xếp hạng ứng viên rút gọn thành so sánh log xác suất của riêng từ vừa thêm, vì phần cộng dồn phía trước giống nhau ở mọi ứng viên. Trên cây mặc định, mèo là từ đầu mạnh nhất với -0.10, nhưng cả hai lối ra của nó đều cụt, nên tham lam dừng ở mèo ngủ với tổng -1.70. Nó chỉ sinh 5 ứng viên và nhìn thấy đúng 1 trong 7 chuỗi hoàn chỉnh.
Kéo B lên 2 là đáp án đổi. Chùm giữ thêm con với -0.30. Ở bước 2, ứng viên con mèo cộng dồn -0.50 đứng trên mèo ngủ với -1.70, nên nhánh vừa nãy bị bỏ qua nay sống tiếp và cho con mèo ngủ với tổng -1.40. Trên cây này B = 2 đã chạm đúng kết quả của vét cạn, đổi lại 13 ứng viên thay vì 16.
Ứng viên cạnh tranh bằng tổng cộng dồn, không bằng từ vừa thêm. Đây là chỗ hay nhầm nhất. Chùm không so -0.90 với -0.70, nó so -1.40 với -1.20. Vì mỗi log xác suất đều âm, chuỗi càng dài tổng càng thấp, và một chuỗi dài hay sẽ luôn thua một chuỗi ngắn tầm thường nếu ta chấm bằng tổng thô.
Phạt độ dài là cách vá chuyện đó. Núm alpha dùng công thức của Wu và cộng sự năm 2016:
score = logP / lp với lp = (5 + len)^alpha / 6^alpha
Ở alpha = 0 cả hai luỹ thừa bằng 1 nên lp bằng đúng 1, tức không phạt gì, và cột điểm trùng khít cột log xác suất tổng. Ở alpha = 1 mẫu số của chuỗi ba từ là 8/6 = 1.333, của chuỗi sáu từ là 11/6 = 1.833, nên chuỗi dài được chia cho một số lớn hơn và bớt thiệt. Đặt B = 2 rồi kéo alpha: tới 0.80 thì con mèo nằm trên tấm thảm với tổng -1.80 vượt lên trên con mèo ngủ với tổng -1.40. Mốc đảo hạng tính được là khoảng 0.789, nghiệm của 1.80 / 1.40 = (11/8)^alpha.
Ba điều đừng tin quá
- Chùm tia không bảo đảm tìm ra chuỗi tốt nhất. Nó chỉ mở cửa sổ tìm kiếm rộng ra. Thẻ so sánh trong sim luôn đặt kết quả của chùm cạnh kết quả vét cạn để bạn thấy khoảng cách, và ở
B = 1khoảng cách đó là0.300điểm. - Rộng hơn không phải lúc nào cũng tốt hơn. Bấm Chùm rộng hoá dở:
B = 1chosáng mưa tovới-3.15, cònB = 2tụt xuốngchiều nắng gắtvới-5.50, vì ở bước 2 hai nhánh củachiềucộng dồn tốt hơn nên chiếm hết chỗ và hấtsáng mưara khỏi chùm. TớiB = 3mới quay lại-3.15. Không có định lý nào nói điểm phải tăng theoB. - Phạt độ dài là quy ước, không phải định lý. Con số 5 và 6 trong công thức là hằng số người ta chọn cho hệ dịch máy của Google năm 2016. Có nhiều biến thể khác, chia cho đúng độ dài là một, cộng thêm phần thưởng cố định mỗi từ là hai. Đổi biến thể là đổi thứ hạng, và không bản nào đúng hơn bản nào một cách phổ quát.
Những gì sim này chọn thay bạn
Ba lựa chọn cài đặt dưới đây đều là quy ước, người khác cài khác đi vẫn hợp lệ. Riêng cái đầu tiên hoá ra còn không phải một lựa chọn thật, và đó mới là chỗ đáng đọc kỹ.
- Cắt tỉa dựa trên log xác suất thô, phạt độ dài chỉ dùng khi xếp hạng các chuỗi đã hoàn chỉnh. Cần nói rõ điều này mua được ít hơn vẻ ngoài của nó: vì sim bước đồng bộ, mọi ứng viên trong cùng một bước đều dài bằng nhau, nên
lplà một hằng số dương chung cho cả bước và chia tất cả cho nó không đổi được thứ tự nào. Xếp hạng ứng viên bằng điểm đã phạt sẽ cho đúng cùng một chùm. Chỗ bản GNMT gốc thật sự khác là nó cho chuỗi đã hoàn chỉnh ở lại tranh chỗ trong chùm với chuỗi chưa xong, và lúc đó độ dài mới khác nhau nên phạt độ dài mới đổi được cái gì bị cắt. - Chuỗi hoàn chỉnh không chiếm chỗ trong chùm. Khi một giả thuyết chạm trạng thái không còn từ nào nối tiếp, nó được cất sang bảng kết quả và các bước sau vẫn còn đủ
Bchỗ cho phần chưa xong. - Hoà điểm thì ứng viên sinh ra trước thắng. Thứ tự sinh là thứ tự cha trong chùm rồi tới thứ tự dòng trong bảng xác suất. Bấm Hoà điểm để thấy:
xanhvàđỏcùng-0.70, hai chuỗi cùng-1.00, vàxanh láluôn đứng trên.
Còn một giới hạn nữa của chính sim: cây chỉ sâu tối đa 12 bước, và nếu bạn dựng được một cây chạm trần đó thì sim báo thẳng bằng một dòng chữ đỏ chứ không lặng lẽ cắt. Gõ một log xác suất ngoài khoảng -9 tới 0 cũng vậy, giá trị bị kẹp và sim nói ra lúc kẹp.
B = 1 là tham lam, và tham lam sai vì nó quyết định vĩnh viễn ở bước đầu bằng thông tin của riêng bước đầu. Chùm tia mua thêm cơ hội sửa sai bằng cách trả thêm tính toán, nhưng nó vẫn là tìm kiếm gần đúng: nó có thể bỏ lỡ chuỗi tốt nhất, và rộng hơn đôi khi lại tệ hơn. Phạt độ dài không sửa được thuật toán, nó chỉ đổi thước đo dùng để xếp hạng những gì thuật toán tìm được.
- 1Trên cây mặc định, vì sao tham lam dừng ở mèo ngủ với -1.70 trong khi tồn tại chuỗi -1.40?
- 2Đặt alpha = 0 thì mẫu số lp bằng bao nhiêu, và hệ quả là gì?
- 3Tăng B từ 1 lên 2 có bảo đảm chuỗi thắng tốt hơn hoặc bằng không?