NLP [P4] - Beam Search - Thuật toán tìm kiếm hỗ trợ Seq2Seq

Trong phần trước NLP [P3] — Seq2Seq Model — Hạt nhân của Google Translate chúng ta tìm hiểu về mô hình Encoder-Decoder ( Seq2Seq) trong việc xử lí bài toán Dịch Máy. Trong nội dung bài viết lần này, mình sẽ trình bài về một thuật toán tìm kiếm giúp gia tăng độ chính xác của quá trình Decoder.

Ý tưởng của Beam Search
Chọn ra những từ có xác suất lớn nhất
Chọn ra những câu có xác suất lớn nhất

Ý tưởng của Beam Search

Trong mô hình cơ bản của Seq2Seq, tại bước Decode, vector đầu ra của LSTM sẽ được đưa qua một hàm Softmax để tìm kiếm từ có xác suất xuất hiện lớn nhất. Và từ này sẽ là vector đầu vào để dự đoán từ tiếp theo, thế nhưng liệu xác suất của từ cao nhất liệu có luôn là tốt nhất?

Chọn ra những từ có xác suất lớn nhất

Thuật toán Beam Search có một tham số được gọi là beam width. Tại mỗi bước dự đoán, thay vì chọn ra từ có xác suất lớn nhất, ta sẽ chọn ra beam width kết quả có xác suất cao nhất. Ví dụ chúng ta cần dịch câu sau từ tiếng Phát sang tiếng Anh:

(X = Jane\ visite\ l’Afrique\ en\ septembre)

Chọn beam width = 3. Ta có 3 từ có xác suất lớn nhất tại step 1:

(y^{<1>} = { in, jane, september })

Lúc này, xác suất mỗi từ xuất hiện sẽ là (P \left(y^{<1>}\ |\ X \right)) Đưa lần lượt những từ này vào step tiếp theo và tiếp tục chọn ra 3 từ có xác suất lớn nhất:

[in => y^{<2>} = { september, … }]

[jane => y^{<2>} = { is, visits, … }]

Chúng ta hoàn toàn có thể sử dụng 1 mức threshold để lựa chọn những từ có xác suất đạt chuẩn trong 3 từ kia, nếu không có từ nào thỏa mãn thì chúng ta có thể dừng việc xét nhánh từ đó. Xác suất của chuỗi từ lúc này sẽ là: (P\left( y^{<2>} | X,\ y^{<1>} \right))

Chọn ra những câu có xác suất lớn nhất

Cứ tiếp túc tính toán các bộ xác suất như vậy cho tới khi kí tự EOS - hết câu xuất hiện. Lúc này ta sẽ có một cây xác suất

Công việc lúc này là nhân tất cả cả xác suất của cả chuỗi có điều kiện lại:

[P = P\left( y^{<1>}

X \right) P\left( y^{<2>}

X,\ y^{<1>} \right)\ … P\left( y^{<T_y>}

X,\ y^{<1>}\ … y^{<T_y - 1>}\right)]

Câu kết quả sẽ là câu có xác suất lớn nhất. Ví xác suất thường là những số nhỏ hơn 1 nên nếu với câu có độ dài thì kết quả có thể sẽ rất nhỏ nên người ta sẽ thường dùng tới Logarit để thuận tiện cho việc tính toán.

Việc sử dụng Beam Search có khả năng tăng độ chính xác tuy nhiên việc lưu lại thông tin xác suất của chuỗi dài có thể làm tăng thời gian training, tốn tài nguyên phần cứng.

Bài viết được tham khảo và sử dụng hình ảnh từ: