Language Modeling là gì

Language model
Language model

Trong bài viết này, ta sẽ tìm hiểu thế nào là một mô hình ngôn ngữ (language modeling). Làm sao để xây dựng được một mô hình ngôn ngữ từ tập các mẫu câu của một ngôn ngữ bất kỳ (Anh, Việt, Nhật, …). Mô hình ngôn ngữ ban đầu được ứng dụng trong nhận dạng tiếng nói (speech recognition) và đã được áp dụng vào trong những tác vụ khác liên quan trong lĩnh vực Xử lý ngôn ngữ tự nhiên (Natural Language Processing – NLP) như gán nhãn từ loại (tagging), phân tích cây cú pháp (parsing), dịch máy (machine translation), …

Tại sao chúng ta cần mô hình ngôn ngữ? Lý do thứ nhất, mô hình này cung cấp cho bạn thông tin về phân bố xác suất tiền nghiệm (prior distribution) p(x_1...x_n) để xét xem câu gồm các từ đầu vào có phù hợp hay không với ngôn ngữ xác định. Ví dụ, ta sẽ có xác suất của câu p(toi \ nay \ duoc \ di \ choi \ roi \ vui \ qua) > p(qua \ roi \ vui \ di \ choi \ toi \ nay \ duoc) nhờ vậy mà ta xác định được câu “tối nay được đi chơi rồi vui quá” sẽ phù hợp hơn với ngôn ngữ tiếng Việt hơn câu hai “quá rồi vui đi chơi tối”. Thứ hai, các kĩ thuật liên quan đến ước lượng tham số cho mô hình thông qua tập dữ liệu huấn luyện cho trước được sử dụng trong các mô hình khác như Hidden Markov Model, Natural Language Parsing. Và cuối cùng, đây là một trong những cơ sở kiến thức để các bạn đọc hiểu được các bài viết liên quan đến Long short-term memory (LSTM).

Đặt vấn đề

Giả sử ta có một ngữ liệu (corpus) thu thập được từ các trang web như vnexpress, baomoi, hay foody. Ngữ liệu là tập dữ liệu gồm các câu (sentence) cho một ngôn ngữ xác định. Tiếp theo, ta định nghĩa V (vocabulary) là bộ từ vựng của một ngôn ngữ gồm tập hợp hữu hạn các từ. Ví dụ, trong ngôn ngữ tiếng Việt, ta sẽ có danh sách các từ sau (con, con mèo, kêu, nhảy, chuối, bánh, kem, …):

V = \{con, con \ meo, keu, nhay, chuoi, banh \ kem, ...\}

Mục tiêu của chúng ta là xây dựng được mô hình có khả năng tính toán xác suất của một câu bất kỳ thuộc về một ngôn ngữ cụ thể

p(x_1...x_n).

Trong đó, x_1x_2...x_n là chuỗi các từ tạo nên một câu. n là chiều dài của câu, n \ge 1x_i \in V trong đó i \in \{1...(n-1)\}. Ta đặt x_n=STOP là một ký hiệu đặc biệt (STOP \notin V). Như vậy, ta sẽ có tập hợp các câu như bên dưới

con meo nhay STOP
con meo keu STOP
keu meo con STOP
meo meo meo STOP
STOP
...

Từ đây, ta đặt V^+ là tập hợp tất cả các câu từ bộ từ vựng V. Đây là tập vô hạn, vì các câu có độ dài bất kỳ.

Định nghĩa một cách toán học một xíu. Một mô hình ngôn ngữ gồm tập hữu hạn từ vựng V, và một hàm xác suất p(x_1,x_2,...,x_n) sao cho:

\forall <x_1...x_n> \in V^+, p(x_1,x_2,...,x_n) \ge 0

\sum_{<x_1...x_n> \in V^+} p(x_1,x_2,...,x_n) = 1

Như vậy p(x_1, x_2,...x_n) là phân bố xác suất của các câu trong tập V^+

Ta có thể định nghĩa xác suất trên bằng công thức đơn giản như sau

p(x_1...x_n) = \frac{c(x_1...x_n)}{N}

Với c(x_1...x_n) (count) là số lần xuất hiện của câu x_1...x_n trong ngữ liệu, và N là số lượng các câu trong ngữ liệu huấn luyện.

Sentence frequency
Sentence frequency

Công thức này thật sự đơn giản khi bắt đầu, nhưng ta cần biết được hạn chế của nó khi tử số bằng không. Tử số bằng không có nghĩa là câu được tính không nằm trong ngữ liệu huấn luyện. Điều này dẫn đến mô hình không có khả năng tổng quát hoá, trong khi mục tiêu của Machine Learning là đi tổng quát hoá để có thể dự đoán được bất kỳ mẫu dữ liệu nào không có trong ngữ liệu. Ta sẽ đi khắc phục nhược điểm này ở các phương pháp sẽ được đề cập ở mục tiếp theo.

Markov Models

Ý tưởng chính của mô hình Markov là giả định xác suất của đối tượng hiện hành chỉ phụ thuộc vào k (k \le (n-1)) đối tượng trước đó của một chuỗi. Ngược lại với xác suất đồng thời (chain rule), xác suất của đối tượng hiện hành phải phụ thuộc vào n - 1 đối tượng trước đó. Trigram Language Models được rút ra trực tiếp từ mô hình này, ta sẽ bàn ở mục tiếp theo.

Xét một chuỗi các biến ngẫu nhiên X_1, X_2, ..., X_n. Mỗi biến ngẫu nhiên này có thể có các giá trị thuộc tập hữu hạn V. Mục tiêu của chúng ta là mô hình hoá xác suất của một chuỗi bất kỳ x_1x_2...x_n, trong đó n \ge 1x_i \in V sao cho i=1,...,n như sau

P(X_1=x_1, X_2=x_2,...,X_n=x_n)

Như vậy, với chuỗi có dạng x_1x_2...x_n ta có thể phát sinh ra được |V|^n các khả năng. Rõ ràng ta không thể liệt kê hết bằng tay danh sách các chuỗi này để tính xác suất. Thay vì vậy, ta có thể tổng quát hoá thành công thức bên dưới, với tên gọi là mô hình Markov bậc nhất (first-order Markov)

P(X_1=x_1, X_2=x_2,..., X_n=x_n)
= P(X_1=x_1)\prod_{i=2}^n P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1}) (1.1)
= P(X_1=x_1)\prod_{i=2}^n P(X_i=x_i|X_{i-1}=x_{i-1}) (1.2)

(1.1) là công thức chuẩn suy ra được từ xác suất đồng thời (chain rule), (1.2) suy ra được từ công thức này với giả định rằng đối tượng thứ i chỉ phụ thuộc điều kiện vào một đối tượng trước đó là x_{i-1} trong chuỗi. Nghĩa là

P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1}) = P(X_i=x_i|X_{i-1}=x_{i-1})

Tương tự, ta có mô hình Markov bậc hai (second-order Markov)

P(X_1=x_1, X_2=x_2,..., X_n=x_n)
= \prod_{i=1}^n P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})

Để thuận tiện cho xử lý, ta đặt x_0 = x_{-1} = *, trong đó * là ký hiệu bắt đầu của một chuỗi/câu.

Để tính xác suất xuất hiện của đối tượng x_i có phân bố là

P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})

ta thực hiện các bước sau

  1. Khởi tạo i=1, và x_0 = x_{-1} =*
  2. Phát sinh đối tượng x_i từ công thức
    P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})
  3. Nếu x_i = STOP thì ta trả về chuỗi x_1...x_i. Ngược lại, ta gán i = i + 1 và quay lại bước 2.

Như vậy, ta đã có một mô hình có thể phát sinh được một chuỗi có chiều dài bất kỳ

Trigram Language Models

Unigram
Unigram

Trong thực tế, ta có nhiều cách để xây dựng mô hình ngôn ngữ, nhưng ta sẽ tập trung vào mô hình cơ bản nhất là Trigram Language Models. Mô hình này chính là Markov bậc hai như đã đề cập ở phần trên.

P(X_1=x_1, X_2=x_2,..., X_n=x_n)
= \prod_{i=1}^n P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})

Định nghĩa cho mô hình này gồm một tập hữu hạn từ vựng V, và tham số

q(w|u,v)

với mỗi trigram u,v,w, ta có w \in V \cup \{STOP\}u, v \in V \cup \{*\}. Trong đó, q(w|u,v) được hiểu như xác suất xuất hiện của từ w ngay sau bigram (u,v). Với mọi câu x_1...x_n, trong đó x_i \in V sao cho i=1...(n-1)x_n=STOP, xác suất của một câu trong trigram language model sẽ là

p(x_1...x_n) = \prod_{i=1}^n q(x_i|x_{i-2},x_{i-1})

và đặt x_0 = x_{-1} = *

Các tham số q này thoả ràng buộc trigram (u, v, w) và bigram (u, v)

q(w|u,v) \ge 0

\sum_{w \in V \cup \{STOP\}} q(w|u,v) = 1

Ta có thể xem ví dụ bên dưới cho câu “Việt nam là đất nước tươi đẹp”

p(viet \ nam \ la \ dat \ nuoc \ xinh \ dep \ STOP) = q(viet|*, *) \times q(nam|*,viet) \times q(la|viet,nam) \times q(dat|nam,la) \times q(nuoc|la,dat) \times q(xinh|dat,nuoc) \times q(dep|nuoc,xinh) \times q(STOP|xinh,dep)

Maximum-Likelihood Estimates

Để ước lượng xác suất cực đại, ta định nghĩa c(u, v, w) là số lần xuất hiện của trigram (u, v, w) trong ngữ liệu, ví dụ c(cho, gam, xuong) là số lần xuất hiện của chuỗi gồm ba từ chó gặm xương trong ngữ liệu. Tương tự, ta định nghĩa c(u, v) là số lần xuất hiện của bigram (u, v)  trong ngữ liệu. Từ hai định nghĩa này, ta đặt

q(w|u,v) = \frac{c(u,v,w)}{c(u,v)}

Ví dụ cho câu chó gặm xương ta có

q(xuong|cho,gam) = \frac{c(cho,gam,xuong)}{c(cho,gam)}

Công thức ước lượng thật đơn giản phải không nào. Tuy nhiên, công thức trên vướng phải những vấn đề sau:

  1. Do số lượng từ vựng của chúng ta trong thực tế là khá lớn khoảng 10,000 từ vựng, như vậy ta sẽ có khoảng 10,000 \times 10,000 \times 10,000 = 10^{12} các khả năng của tham số q(w|u,v). Vì vậy, sẽ có nhiều mẫu câu có giá trị xác suất bằng không do c(u,v,w)=0
  2. Và tham số không xác định khi c(u,v) = 0.

Để giải quyết vấn đề này, ta có thể áp dụng một số phương pháp như

Linear interpolation

Ta định nghĩa trigram, bigram, và unigram như sau

q_{ML}(w|u,v) = \frac{c(u,v,w)}{c(u,v)}

q_{ML}(w|v) = \frac{c(v,w)}{c(v)}

q_{ML}(w) = \frac{c(w)}{c()}

Trong đó, ta lưu ý c() là tổng số các từ xuất hiện trong ngữ liệu (không phải tổng số từ vựng V). Nhờ có tham số q_{ML}(w), ta luôn có giá trị lớn hơn không để đảm bảo xác suất của một câu đầu vào khác không.

Ý tưởng của phương pháp linear interpolation (nội suy tuyến tính) đó là sử dụng cả ba tham số trên bằng cách định nghĩa trigram estimate như sau

q(w|u,v) = \lambda_1 \times q_{ML}(w|u,v) + \lambda_2 \times q_{ML}(w|v) + \lambda_3 \times q_{ML}(w)

Trong đó, \lambda_1, \lambda_2, \lambda_3 là các tham số thêm vào mô hình, thoả các điều kiện

\lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_3 \ge 0

\lambda_1 + \lambda_2 + \lambda_3 = 1

Chúng còn được gọi là trọng số trung bình (weighted average) cho từng tham số q. Để ước lượng giá trị cho tham số \lambda, ta có thể áp dụng phương pháp Log-likelihood và bucketing.

_ Log-likelihood

Ta chia ngữ liệu ban đầu thành ba tập: training, testing, developing (ví dụ tỷ lệ tương ứng là 60%, 10%, 20%). Ta định nghĩa c^\prime (u,v,w) là số lần xuất hiện của trigram (u,v,w) trong tập developing. Ta có công thức log-likelihood cho tập developing này

L(\lambda_1, \lambda_2, \lambda_3)

= \sum_{u,v,w} c^\prime (u,v,w) log \ q(w|u,v)

= \sum_{u,v,w} c^\prime (u,v,w) log(\lambda_1 \times q_{ML}(w|u,v) + \lambda_2 \times q_{ML}(w|v) + \lambda_3 \times q_{ML}(w))

Mục tiêu của chúng ta là chọn được các giá trị \lambda sao cho giá trị L(\lambda_1, \lambda_2, \lambda_3) đạt được cực đại

arg \max_{\lambda_1, \lambda_2, \lambda_3} L(\lambda_1, \lambda_2, \lambda_3)

_ Bucketing

Ta định nghĩa lại các tham số \lambda một các đơn giản hơn

\lambda_1 = \frac{c(u,v)}{c(u,v) + \gamma}

\lambda_2 = (1 - \lambda_1) \times \frac{c(v)}{c(v) + \gamma}

\lambda_3 = 1 - \lambda_1 - \lambda_2

Trong đó \gamma > 0  là tham số duy nhất cần tìm của phương pháp này và được tính nhờ vào maximum log-likelihood.

Discounting Methods

Đây là một hướng tiếp cận khác để ước lượng tham số q(w|u,v) trong thực tế. Đầu tiên, ta xét trường hợp bigram

q(w|v)

với mọi w \in V \cup \{STOP\}, v \in V \cup \{*\}

Với mọi bigram c(v, w) > 0, ta định nghĩa discounted counts (trừ đi một giá trị \beta nào đó sau khi đếm c(v, w)).

c^* (v, w) = c(v, w) - \beta

trong đó \beta \in [0, 1] (thông thường ta đặt \beta = 0.5). Ta làm như vậy là do trong quá trình đếm tần suất các câu trong ngữ liệu, ta đã làm cho tần suất của câu trong ngữ liệu quá cao và tần suất của câu không nằm trong ngữ liệu quá thấp. Điều này giúp cho mô hình của chúng ta ít bị over-fitting hơn.

Từ đây, ta định nghĩa

q(w|v) = \frac{c^\prime (v, w)}{c(v)}

Ví dụ, sau khi áp dụng công thức trên, ta có bảng tương tự bên dưới (\beta = 0.5)

x c(x) c^\prime(x) \frac{c^\prime(x)}{c(con)}
con 48
con,chó 15 14.5 14.5/100
con,mèo 11 10.5 10.5/100
con,gà 10 9.5 9.5/100
con,bò 5 4.5 4.5/100
con,tàu 2 1.5 1.5/100
con,con 1 0.5 0.5/100
con,cóc 1 0.5 0.5/100
con,heo 1 0.5 0.5/100
con,mồi 1 0.5 0.5/100
con,thoi 1 0.5 0.5/100

Với mọi ngữ cảnh v, ta tính được khối xác suất bị mất (missing probability mass)

\alpha(v) = 1 - \sum_{w:c(v,w) > 0} \frac{c^\prime(v,w)}{c(v)}

Từ bảng ví dụ trên ta có

\sum_{w:c(v,w) > 0}\frac{c^\prime(v,w)}{c(v)} = \frac{14.5}{48} + \frac{10.5}{48} +\frac{9.5}{48} +\frac{4.5}{48} +\frac{1.5}{48} +5 \times \frac{0.5}{48} = \frac{43}{48}

Lúc này \alpha(con) = 1 - \frac{43}{48} = \frac{5}{48}. Ta dùng giá trị này để tính giá trị cho các c(u, w) = 0. Như vậy, ta định nghĩa hai tập A, B = q_D(w|v) như sau

A(v) = \{w:c(v,w) > 0\} = \frac{c^*(v,w)}{c(v)}

B(v) = \{w:c(v,w) = 0\} = \alpha(v) \times \frac{q_{ML}(w)}{\sum_{w\in B(v)} q_{ML} (w)}

Theo ví dụ trên ta có

A(con) = \{con,cho,meo,ga,bo,coc,heo,moi,thoi\}

B(con) là các cặp từ còn lại.

Tổng quát hoá cho trường hợp trigram

Với mọi bigram (u,v) ta định nghĩa đệ quy cho trigram như sau

c^*(u,v,w) = c(u,v,w) - \beta

\alpha(u,v) = 1 - \sum_{w \in A(u,v) = \frac{c^*(u,v,w)}{c(u,v)}}

A(u,v) = \{w : c(u,v,w) > 0\} = \frac{c^*(u,v,w)}{c(u,v)}

B(u,v) = \{w : c(u,v,w) = 0\} = \alpha(u,v) \times \frac{q_D(w|v)}{\sum_{w\in B(u,v)} q_D(w|v)}

Trong mô hình này, để ước lượng tham số \beta ta lại áp dụng phương pháp held-out lên tập developing bằng cách cực đại hoá log-likelihood

\sum_{u,v,w} c^\prime (u,v,w) log \ q_D(w|u,v)

Ta thực hiện bằng cách lặp qua các giá trị \beta = \{0.1, 0.2, ..., 0.9\} để tính log-likelihood và chọn ra giá trị \beta khiến cho hàm này đạt cực đại.

 Đánh giá mô hình này như thế nào

Làm thế nào để đánh giá chất lượng của một mô hình ngôn ngữ? Một trong những phương pháp phổ biến đó là perplexity (độ hỗn độn).

Giả sử ta có tập các câu để test (held-out: không nằm trong tập training) x^{(1)},x^{(2)},...,x^{(m)}. Mỗi câu x^{(i)}i \in \{1...m\} là chuỗi các từ x_1^{(i)},...,x_{n_i}^{(i)}, trong đó n_i là độ dài của câu thứ i.

Ta tính xác suất p(x^{(i)}) cho từng x^{(i)} thông qua mô hình ngôn ngữ vừa training xong. Khi đó, chất lượng của mô hình ngôn ngữ này sẽ được tính như sau

\prod_{i=1}^m p(x^{(i)})

giá trị thu được từ phép tính trên càng cao thì chất lượng của mô hình càng tốt đối với dữ liệu chưa hề thấy trong tập training.

Perplexity được định nghĩa như sau

2^{-l}

trong đó

\begin{cases}  M = \sum_{i=1}^m n_i\\  l = \frac{1}{M} \sum_{i=1}^m log_2 p(x^{(i)})\\  \end{cases}

Theo công thức trên, nếu giá trị của perplexity càng nhỏ, mô hình ngôn ngữ xây dựng được càng tốt.

Trong thực nghiệm của Goodman, ông đưa ra biểu đồ cho thấy perplexity là 74 đối với trigram model, 137 cho bigram model, và 955 cho unigram model. Mô hình này đơn giản chỉ gán xác suất 1/50,000 cho từng từ với bộ từ vựng 50,000. Như vậy trigram model cho ta giá trị đánh giá mô hình ngôn ngữ tốt hơn bigram và unigram.

Nguồn tham khảo
Language models
Language modeling a billion words
Music Language Modeling with Recurrent Neural Networks

Advertisements

3 thoughts on “Language Modeling là gì

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s