9.8. Tìm kiếm Chùm¶
Trong Section 9.7, chúng ta đã thảo luận cách huấn luyện mô hình mã hóa - giải mã với đầu vào và đầu ra có độ dài thay đổi. Phần này giới thiệu cách sử dụng mô hình để dự đoán đầu ra là chuỗi có độ dài thay đổi.
Trong Section 9.5, khi chuẩn bị dữ liệu huấn luyện, ta thường thêm ký hiệu kết thúc câu “<eos>” vào sau mỗi câu. Ta sẽ tiếp tục sử dụng ký hiệu trên trong phần này. Để thuận tiện, giả sử rằng đầu ra của bộ giải mã là một chuỗi văn bản. Gọi kích thước của bộ từ điển đầu ra \(\mathcal{Y}\) (chứa tất cả các từ có thể xuất hiện ở chuỗi đầu ra, bao gồm cả “<eos>”) là \(\left|\mathcal{Y}\right|\), và chiều dài tối đa của chuỗi đầu ra là \(T'\). Như vậy có tổng cộng \(\mathcal{O}(\left|\mathcal{Y}\right|^{T'})\) chuỗi đầu ra có thể được sinh ra. Tất cả những chuỗi con nằm phía sau “<eos>” trong chuỗi đầu ra sẽ bị lược bỏ. Bên cạnh đó, ta ký hiệu \(\mathbf{c}\) là vector ngữ cảnh mã hóa thông tin của tất cả trạng thái ẩn từ đầu vào.
9.8.1. Tìm kiếm Tham lam¶
Đầu tiên, hãy xem xét một phương pháp đơn giản: tìm kiếm tham lam. Tại mỗi bước thời gian \(t'\) của chuỗi đầu ra, ta chọn từ có xác suất có điều kiện cao nhất trong \(|\mathcal{Y}|\) từ làm đầu ra như sau:
Khi gặp “<eos>” hoặc khi chuỗi đầu ra đạt chiều dài tối đa \(T'\), ta kết thúc việc dự đoán.
Như đã đề cập khi thảo luận về bộ giải mã, xác suất có điều kiện của một chuỗi đầu ra được sinh từ chuỗi đầu vào là \(\prod_{t'=1}^{T'} P(y_{t'} \mid y_1, \ldots, y_{t'-1}, \mathbf{c})\). Chuỗi đầu ra tối ưu là chuỗi có xác suất có điều kiện cao nhất. Vấn đề lớn nhất của tìm kiếm tham lam là không đảm bảo chuỗi tìm được là chuỗi tối ưu.
Xét ví dụ dưới đây. Giả sử ta có bốn từ “A”, “B”, “C”, và “<eos>” trong từ điển đầu ra. Bốn giá trị dưới mỗi bước thời gian trong Fig. 9.8.1 là xác suất có điều kiện của “A”, “B”, “C”, và “<eos>” tại bước thời gian đó. Tại mỗi bước thời gian, tìm kiếm tham lam chọn từ có xác suất có điều kiện cao nhất. Vì vậy, chuỗi đầu ra “A”, “B”, “C”, và “<eos>” được tạo ra như trong Fig. 9.8.1. Xác suất có điều kiện của cả chuỗi đầu ra này là \(0.5\times0.4\times0.4\times0.6 = 0.048\).
Fig. 9.8.1 Dưới mỗi bước thời gian là xác suất có điều kiện của “A”, “B”, “C”, và “<eos>” tại bước thời gian đó. Tại mỗi bước thời gian, phương pháp tìm kiếm tham lam sẽ chọn từ có xác suất cao nhất.¶
Bây giờ, hãy xét một ví dụ khác trong Fig. 9.8.2. Khác với Fig. 9.8.1, tại bước thời gian 2 ta chọn “C”, từ có xác suất có điều kiện cao thứ hai. Vì bước thời gian 3 phụ thuộc vào bước thời gian 1 và 2, mà chuỗi con đầu ra tại hai bước thời gian này thay đổi từ “A” và “B” trong Fig. 9.8.1 thành “A” và “C” trong Fig. 9.8.2, nên xác suất có điều kiện của các từ tại bước thời gian 3 cũng thay đổi. Chúng ta chọn “B”, từ có xác suất có điều kiện cao nhất. Bây giờ, chuỗi con đầu ra trước bước thời gian 4 là “A”, “C”, và “B”, khác với “A”, “B”, và “C” trong Fig. 9.8.1. Do đó xác suất có điều kiện của các từ tại bước thời gian 4 cũng thay đổi. Vẫn chọn từ có xác suất cao nhất tại bước thời gian này là “<eos>”, ta có xác suất có điều kiện của cả chuỗi đầu ra “A”, “C”, “B”, và “<eos>” là \(0.5\times0.3\times0.6\times0.6=0.054\), cao hơn xác suất của chuỗi được sinh ra dựa trên phương pháp tìm kiếm tham lam. Vì vậy, chuỗi đầu ra “A”, “B”, “C”, và “<eos>” có được từ phương pháp tìm kiếm tham lam không phải chuỗi tối ưu.
Fig. 9.8.2 Dưới mỗi bước thời gian là xác suất có điều kiện của “A”, “B”, “C”, và “<eos>” tại bước thời gian đó. Tại bước thời gian 2, từ “C” được chọn có xác suất có điều kiện cao thứ hai.¶
9.8.2. Tìm kiếm Vét cạn¶
Nếu mục tiêu là tìm được chuỗi tối ưu, ta có thể xem xét giải thuật vét cạn: kiểm tra tất cả những chuỗi đầu ra có thể, trả kết quả là chuỗi có xác suất có điều kiện cao nhất.
Mặc dù chúng ta có thể sử dụng thuật toán tìm kiếm vét cạn để tìm chuỗi tối ưu, nhưng chi phí tính toán của nó \(\mathcal{O}(\left|\mathcal{Y}\right|^{T'})\) là quá cao. Ví dụ, khi \(|\mathcal{Y}|=10000\) và \(T'=10\), chúng ta cần kiểm tra \(10000^{10} = 10^{40}\) chuỗi. Điều này gần như là bất khả thi. Chi phí tính toán của tìm kiếm tham lam là \(\mathcal{O}(\left|\mathcal{Y}\right|T')\), ít hơn nhiều so với vét cạn. Ví dụ, khi \(|\mathcal{Y}|=10000\) và \(T'=10\), chúng ta chỉ cần kiểm tra \(10000\times10=1\times10^5\) chuỗi.
9.8.3. Tìm kiếm Chùm¶
Tìm kiếm chùm (beam search) là một thuật toán cải tiến dựa trên tìm kiếm tham lam. Nó có một siêu tham số \(k\) gọi là kích thước chùm (beam size). Tại bước thời gian 1, ta chọn \(k\) từ có xác suất có điều kiện cao nhất để bắt đầu \(k\) chuỗi đầu ra ứng viên. Tại các bước thời gian tiếp theo, dựa trên \(k\) chuỗi đầu ra ứng viên từ bước thời gian trước đó, ta tính và chọn \(k\) chuỗi có xác suất có điều kiện cao nhất trong tổng số \(k\left|\mathcal{Y}\right|\) khả năng. Đây sẽ là các chuỗi đầu ra ứng viên cho bước thời gian đó. Cuối cùng, ta lọc ra các chuỗi có chứa “<eos>” từ các chuỗi đầu ra ứng viên tại mỗi bước thời gian và loại bỏ tất cả các chuỗi sau ký tự đó để thu được tập các chuỗi đầu ra ứng viên cuối cùng.
Fig. 9.8.3 Quá trình tìm kiếm chùm. Kích thước chùm bằng 2 và độ dài tối đa của chuỗi đầu ra bằng 3. Các chuỗi đầu ra ứng viên là \(A\), \(C\), \(AB\), \(CE\), \(ABD\), và \(CED\).¶
Fig. 9.8.3 minh họa một ví dụ cho quá trình tìm kiếm chùm. Giả sử bộ từ vựng của chuỗi đầu ra chỉ chứa năm từ: \(\mathcal{Y} = \{A, B, C, D, E\}\) và một trong số chúng là ký hiệu đặc biệt “<eos>”. Đặt kích thước chùm bằng 2 và độ dài tối đa của chuỗi đầu ra bằng 3. Tại bước thời gian 1 của chuỗi đầu ra, giả sử các từ có xác suất có điều kiện \(P(y_1 \mid \mathbf{c})\) cao nhất là \(A\) và \(C\). Tại bước thời gian 2, với mọi \(y_2 \in \mathcal{Y},\) ta tính
và
và chọn hai giá trị cao nhất trong 10 giá trị này, giả sử đó là
Sau đó, tại bước thời gian 3, với mọi \(y_3 \in \mathcal{Y}\), ta tính
và
và chọn hai giá trị cao nhất trong số 10 giá trị này, giả sử đó là
Kết quả là, ta thu được 6 chuỗi đầu ra ứng viên: (1) \(A\); (2) \(C\); (3) \(A\), \(B\); (4) \(C\), \(E\); (5) \(A\), \(B\), \(D\); và (6) \(C\), \(E\), \(D\). Cuối cùng, ta sẽ có một tập chuỗi đầu ra ứng viên cuối cùng dựa trên 6 chuỗi này.
Trong tập các chuỗi đầu ra ứng viên cuối cùng, ta sẽ lấy chuỗi có điểm số cao nhất làm chuỗi đầu ra. Điểm số cho mỗi chuỗi được tính như sau:
Ở đây, \(L\) là độ dài của chuỗi ứng viên cuối cùng và \(\alpha\) thường được đặt bằng 0.75. \(L^\alpha\) trong mẫu số là lượng phạt lên tổng logarit cho các chuỗi dài. Có thể ước tính rằng chi phí tính toán của tìm kiếm chùm là \(\mathcal{O}(k\left|\mathcal{Y}\right|T')\). Nó nằm trong khoảng giữa chi phí tính toán của tìm kiếm tham lam và tìm kiếm vét cạn. Ngoài ra, tìm kiếm tham lam có thể được coi là tìm kiếm chùm với kích thước chùm bằng 1. Tìm kiếm chùm tạo ra sự cân bằng giữa chi phí tính toán và chất lượng tìm kiếm bằng cách sử dụng linh hoạt kích thước chùm \(k\).
9.8.4. Tóm tắt¶
- Các phương pháp dự đoán chuỗi có độ dài thay đổi bao gồm tìm kiếm tham lam, tìm kiếm vét cạn và tìm kiếm chùm.
- Tìm kiếm chùm tạo ra sự cân bằng giữa chi phí tính toán và chất lượng tìm kiếm bằng cách sử dụng linh hoạt kích thước chùm.
9.8.5. Bài tập¶
- Ta có thể coi tìm kiếm vét cạn là tìm kiếm chùm với kích thước chùm đặc biệt không? Tại sao?
- Ta đã sử dụng các mô hình ngôn ngữ để tạo các câu trong Section 8.5. Các mô hình này sử dụng phương pháp tìm kiếm đầu ra nào? Hãy cải thiện các phương pháp đó.
9.8.6. Thảo luận¶
9.8.7. Những người thực hiện¶
Bản dịch trong trang này được thực hiện bởi:
- Đoàn Võ Duy Thanh
- Nguyễn Đình Nam
- Nguyễn Duy Du
- Nguyễn Văn Quang
- Lê Khắc Hồng Phúc
- Phạm Hồng Vinh
- Nguyễn Văn Cường