N-gram là gì

     

N-grams được hiểu dễ dàng là tần suất xuất hiện của n kí từ bỏ (từ) thường xuyên xuấthiện trong dữ hiêu

Một số mô hình n-grams phổ biến

unigram, quy mô với n=1, tức là ta công thêm tần suất mở ra của một kí tự(từ), như: “k”, “a”,…

bigrams với n=2 , là quy mô được sử dụng nhiều trong vấn đề phân tích những hìnhthái đến ngôn ngữ

trigrams cùng với n-3, với n càng bự thì độ bao gồm xác càng tốt tuy nhiên đi kèmvới đó thì độ tinh vi cũng to hơn

Để xây cất một mô hình n-gram, ban đầu người ta dựa trên một tập tài liệu huấnluyện( Tranning set). Sau khi quy mô được xây dựng, ta thực hiện kiểm tra môhình dựa trên một tập tài liệu test. Bài toán kiểm tra rất tốt là thực hiện một tập dữkiệu không có trong đào tạo luyện. Phụ thuộc việc đánh giá này cơ mà ta có thể biếtđược mô hình có giỏi hay khôngx.

Bạn đang xem: N-gram là gì

Mô hình N-gram:

Để tính xác suất của một câu: W1W2….Wk….Wn. Theo công thức Bayes ta sẽtính bằng cách:

Tuy nhiên, bí quyết trên bao gồm độ phức hợp lớn, vì chưng vậy bạn ta thường xuyên sử dụngcông thức Markov:

Trong đó:

Do khi tính xác suất có khá nhiều trường phù hợp sẽ chạm chán các các n-grams chưa xuất hiệnhoặc vị sự phân bổ không hầu hết trong tập huấn luyện sẽ dẫn tới việc tính toánkhông chủ yếu xác. Bởi vậy tín đồ ta chuyển ra cách thức làm mịn để khắc phục vấn đềnày

Một số cách thức làm mịn phổ biến:

Discounting: giảm tỷ lệ các các n-grams gồm xác suất to hơn 0 để bù chocác nhiều n-grams chưa xuất hiện

Back-off: tính phần trăm các nhiều n-grams chưa xuất hiện thêm bằng các cụm ngắn hơnvà tất cả xác suất to hơn 0

Interpolation: tính tỷ lệ của tất cả các các n-grams bằng những cụm ngắn hơn

Làm mịn bằng phương thức Kneser – Ney smoothing (Interpolation).

Kneser-Ney là phương thức chủ yếu hèn được áp dụng để đo lường phân cha xác suấtcủa n-grams trong một tài liệu dựa vào những tính toán đã có.

Kneser-Ney được nhìn nhận là cách thức hiệu quả nhất để làm mịn do việc sử dụngcác chiết khấu tuyệt đối bằng cách trừ đi một giá bán trị cố định từ điều kiệnvề tần số bậc rẻ của tỷ lệ để bỏ qua mất n-grams với tần số thấp hơn. Đây làphương pháp kết quả với bigrams và các quy mô n-grams cao hơn.

Một ví dụ thông dụng để minh họa các khái niệm đằng sau phương pháp này là tầnsố Bigrams cảu các “San Francisco”. Nếu nó mở ra nhiều lần vào một ngữliệu huấn luyện, tần số của unigrams “Francisco” cũng trở thành cao. Dựa vào chỉ cótần số unigrams để tham dự đoán các tần số của n-grams vẫn dẫn đến hiệu quả sai lệch.Tuy nhiên, Kneser-Ney mịn chỉnh này bằng phương pháp xem xét các tần số của unigramliên quan tới những từ ở trước.

Công thức Kneser – ney:


Trong xử lý ngữ điệu tự nhiên, như những bài toán dịch thứ hay việc tạo tiêuđề đều hoàn toàn có thể đưa về việc sinh chuỗi từ.

Các mô hình sinh hình dáng này hay tính xác suất mở ra của từng từ trong chuỗitừ ngơi nghỉ đầu ra, bởi vậy đề nghị một thuật toán lời giải để tìm ra chuỗi từ gồm xác suấtlớn nhất. Trong project này, chúng tôi đưa ra hai thuật toán cơ phiên bản để tìm kiếmchuỗi từ, chính là thuật toán tham ăn uống (greedy) và thuật toán beam search.

Xem thêm: Thay Màn Hình Samsung Galaxy S4 Chính Hãng, Uy Tín, Giá Rẻ Nhất

Khi thực hiện các mô hình ngôn ngữ hay những mạng nở ron hồi quy, thì áp ra output của cácmô hình này là các từ trong từ điển với xác suất xuất hiện thêm các từ kia trong ngữcảnh tương ứng. Thuật toán tìm kiếm vẫn tìm trên tổng thể các chuỗi này cùng tìm rachuỗi từ có xác suất xuất hiện lớn nhất. Form size của từ điển phụ thuộc vào vàobài toán, hay là vài trăm, vài nghìn hoặc thậm chí vài triệu từ. Vấn đề tìmkiếm này còn có độ phức hợp tăng theo hàm nón của độ lâu năm câu, là bài bác tóan NP-đủ, vìvậy cần thiết giải đúng được.

Trong thực tế, các cách thức heuristic được sử dụng để tìm kiếm nghiệm giao động “đủtốt” cho việc này.

Thuật toán tham ăn

Ở giải mã tìm kiếm tham ăn, tại từng bước tìm kiếm, lựa chọn ra trong tập dự đoántừ nào có xác suất cao nhất. Sau đó lặp lại quá trình trên.

Ưu điểm của thuật toán này chính là tốc độ, trong lúc nhược điểm là độ bao gồm xáckhông hề cao, kết quả rất có thể khác xa tác dụng tối ưu. Do chỉ việc sai một tự thìcác từ tiếp sau sẽ bị tác động nhiều.

Thuật toán beam search

Là một thuật toán tìm kiếm kiếm theo chiều rộng.

Thay vì chỉ rước một ngôi trường hợp tất cả xác suất cao nhất tại mỗi bước, beam tìm kiếm mởrộng trường tra cứu kiếm bằng cách giữ lại k tài năng có xác suất cao nhất, cùng với k làhằng số được lựa chọn. Quá trình tiếp theo tái diễn trên k mẫu mã trước đó, và nhưngsau đó cũng chỉ cất giữ k mẫu mã cho cách tiếp theo. Cứ như vậy cho tới bước cuốicùng thì lựa chọn mẫu gồm xác suất tối đa trong k mẫu.


Bài toán thêm vết được thực hiện theo các bước như sau:

Xây dựng mô hình Trigrams để lấy ra xác suất mở ra 1 từ trường hợp biết 2 từđứng trước nó

Đối với từng từ giờ đồng hồ Việt không dấu, thực hiện generate toàn bộ các trườnghợp có thể điền dấu mang lại từ

Sử dụng thuật toán tham ăn hoặc thuật toán beam search để lấy ra được câucho phần trăm lớn nhất

Test demo kết quả

Trong project này, công ty chúng tôi thử nghiệm 2 quy mô phổ vươn lên là đó là mô hình 3-gramvà 2-gram. Kết quả dưới đấy là độ đúng đắn được tính trên tập validation vớicác tham số không giống nhau của thuật toán beam search.

N_gramN_beamVal_scoreSeconds/sentenceTest scoreModel size
2grams10.82318.541Mb
20.890514.65
30.913815
40.921616.5
50.925818.30.9221
60.927318.5
70.928218.9
3grams10.8849
20.912815.5
30.930914.35
40.936919.5
50.941125.50.9401441Mb
60.943826.5
70.945331.9