Thuật toán dự đoán từ

Question

Tôi chắc chắn có một bài đăng trên trang này, nhưng tôi không thể tìm thấy bài đăng hỏi câu hỏi chính xác này. Hãy xem xét những điều sau đây:

1. Chúng tôi có một cuốn từ điển chữ có sẵn
2. Chúng tôi đang ăn nhiều đoạn văn từ, và tôi muốn để có thể dự đoán từ kế tiếp trong một câu cho đầu vào này.

Giả sử chúng tôi có một vài câu như "Xin chào tôi tên là Tom", "Tên anh ấy là jerry", "Anh ta đi đâu không có nước". Chúng tôi kiểm tra bảng băm nếu một từ tồn tại. Nếu không, chúng tôi gán cho nó một id duy nhất và đặt nó vào bảng băm. Bằng cách này, thay vì lưu trữ một "chuỗi" các từ như một chuỗi các chuỗi, chúng ta chỉ có thể có một danh sách các uniqueID.

Ở trên, chúng tôi sẽ có ví dụ (0, 1, 2, 3, 4), (5, 2, 3, 6) và (7, 8, 9, 10, 3, 11, 12). Lưu ý rằng 3 là "is" và chúng tôi đã thêm id duy nhất mới khi chúng tôi phát hiện từ mới. Vì vậy, nói rằng chúng tôi được đưa ra một câu "tên cô ấy", đây sẽ là (13, 2, 3). Chúng ta muốn biết, với bối cảnh này, từ tiếp theo sẽ là gì. Đây là thuật toán tôi nghĩ đến, nhưng tôi không nghĩ rằng thuật toán của nó hiệu quả:

1. Chúng tôi có một danh sách các chuỗi N (câu được quan sát). 3,6,2,7,8.
2. Mỗi chuỗi có kích thước trung bình M, trong đó M là chiều dài câu trung bình
3. Chúng tôi được cung cấp một chuỗi mới có kích thước S, ví dụ. 13, 2, 3 và chúng tôi muốn biết từ tiếp theo có thể xảy ra nhất là gì?

Thuật toán:

1. Đầu tiên quét toàn bộ danh sách các chuỗi đối với những người có chỉ số S đầu vào đầy đủ (13,2,3, trong ví dụ này). Vì chúng ta phải quét các chuỗi N, mỗi chiều dài M, và so sánh các chữ S tại một thời điểm, O của nó (N * M * S).

2. Nếu không có chuỗi nào trong quá trình quét của chúng tôi có S đầy đủ, lần quét tiếp theo bằng cách xóa từ ít quan trọng nhất (ví dụ: từ đầu tiên, vì vậy hãy xóa 13). Bây giờ, quét cho (2,3) như trong 1 trong trường hợp xấu nhất O (N * M * S) mà thực sự là S-1.

3. Tiếp tục quét theo cách này cho đến khi chúng tôi nhận được kết quả> 0 (nếu có).

4. Kiểm đếm các từ tiếp theo trong tất cả các chuỗi còn lại mà chúng tôi đã thu thập được. Chúng tôi có thể sử dụng bảng băm đếm mỗi lần chúng tôi thêm và theo dõi từ được thêm nhiều nhất. O (N) trường hợp xấu nhất xây dựng, O (1) để tìm từ tối đa.

5. Từ tối đa được tìm thấy là có nhiều khả năng nhất, vì vậy hãy trả lại từ đó.

Mỗi lần quét mất trường hợp xấu nhất O (M * N * S). Điều này là do có N chuỗi, mỗi chuỗi có các số M và chúng tôi phải kiểm tra các số S để phủ một kết quả phù hợp. Chúng tôi quét S lần trường hợp xấu nhất (13,2,3, sau đó 2,3, sau đó 3 cho 3 lần quét = S). Như vậy, tổng độ phức tạp là O (S^2 * M * N).

Vì vậy, nếu chúng tôi có 100.000 chuỗi và độ dài câu trung bình là 10 từ, chúng tôi đang xem xét 1.000.000 * S^2 để có được từ tối ưu. Rõ ràng, N >> M, vì chiều dài câu không quy mô với số câu được quan sát nói chung, vì vậy M có thể là một hằng số. Sau đó chúng ta có thể giảm độ phức tạp xuống O (S^2 * N). O (S^2 * M * N) có thể hữu ích hơn khi phân tích, vì M có thể là một "hằng số" khá lớn.

Đây có thể là cách tiếp cận hoàn toàn sai lầm đối với loại vấn đề này, nhưng tôi muốn chia sẻ suy nghĩ của mình thay vì chỉ yêu cầu blatantly yêu cầu bảo lãnh. Lý do im quét theo cách tôi làm là vì tôi chỉ muốn quét nhiều như tôi phải làm. Nếu không có S đầy đủ, chỉ cần tiếp tục cắt tỉa S cho đến khi một số chuỗi khớp với nhau. Nếu họ không bao giờ phù hợp, chúng tôi không có ý tưởng gì để dự đoán như là từ tiếp theo! Bất kỳ đề xuất về một giải pháp phức tạp ít thời gian/không gian? Cảm ơn!

Answer 1

Đây là vấn đề của language modeling. Đối với một cách tiếp cận đường cơ sở, Điều duy nhất bạn cần là một bảng băm ánh xạ các chuỗi có độ dài cố định của các từ, nói theo chiều dài k, với từ sau nhất có thể xảy ra. (*)

Tại thời gian đào tạo, bạn phá vỡ nhập vào (k+1)-grams bằng cửa sổ trượt. Vì vậy, nếu bạn gặp

The wrath sing, goddess, of Peleus' son, Achilles 

bạn tạo ra, cho k = 2,

START START the 
START the wrath 
the wrath sing 
wrath sing goddess 
goddess of peleus 
of peleus son 
peleus son achilles 

này có thể được thực hiện trong thời gian tuyến tính. Đối với mỗi 3-gram, kiểm đếm (trong một bảng băm) mức độ thường xuyên từ thứ ba sau hai đầu tiên.

Cuối cùng, lặp qua bảng băm và cho mỗi khóa (2-gram) chỉ giữ từ thứ ba phổ biến nhất. Thời gian tuyến tính.

Vào thời điểm dự đoán, chỉ xem k (2) từ cuối cùng và dự đoán từ tiếp theo. Điều này chỉ mất thời gian liên tục vì nó chỉ là tra cứu bảng băm.

Nếu bạn đang băn khoăn tại sao bạn chỉ nên giữ các đoạn con ngắn thay vì chuỗi đầy đủ, hãy xem xét lý thuyết Markov windows. Nếu mô hình của bạn phải nhớ tất cả các chuỗi từ mà nó đã nhìn thấy trong đầu vào của nó, thì nó sẽ làm hỏng dữ liệu đào tạo của nó và chỉ tái tạo đầu vào của nó tại thời điểm dự đoán. Phụ thuộc nhiều vào tập huấn luyện (nhiều dữ liệu hơn), nhưng đối với k> 4 bạn thực sự cần smoothing trong mô hình của mình.

(*) Hoặc phân phối xác suất, nhưng điều này không cần thiết cho trường hợp sử dụng ví dụ đơn giản của bạn.

Answer 2

Yeh Whye Teh cũng có một số công việc thú vị gần đây giải quyết vấn đề này. "Trình ghi nhớ chuỗi" mở rộng lược đồ kết hợp từng phần dự đoán truyền thống để xem xét lịch sử dài tùy ý.

Dưới đây là một liên kết các giấy bản gốc: http://www.stats.ox.ac.uk/~teh/research/compling/WooGasArc2011a.pdf

Nó cũng rất đáng đọc một số các công việc nền, có thể được tìm thấy trong các giấy "A Bayesian Interpretation of Interpolated Kneser-Ney"