Gán Nhãn Từ Loại (Part-of-Speech Tagging POS) - Ông Xuân Hồng

Trang chủ » Gán Nhãn Từ Loại Tiếng Việt » Gán Nhãn Từ Loại (Part-of-Speech Tagging POS) - Ông Xuân Hồng

Có thể bạn quan tâm

Tagging problem
Tagging problem

Trong nhiều tác vụ của Xử lý ngôn ngữ tự nhiên (XLNNTN), ta mong muốn xây dựng được một mô hình mà chuỗi các quan sát đầu vào (từ, ngữ, câu,…) đi kèm với chuỗi các nhãn đầu ra (từ loại, ranh giới ngữ, tên thực thể,…) gọi là pairs of sequences.

Gán nhãn từ loại (Part-of-speech tagging – POS) có lẽ là bài toán sớm nhất được nghiên cứu và được mọi người biết đến khi nhập môn chuyên ngành XLNNTN. Trong bài viết này, ta sẽ tìm hiểu về bài toán gán nhãn từ loại, các hướng tiếp cận và thuật toán cơ bản để giải quyết vấn đề này.

Giới thiệu

Trong gán nhãn từ loại, mục tiêu của chúng ta khi đưa chuỗi đầu vào là một câu ví dụ như “con ruồi đậu mâm xôi đậu”

con\ ruoi\ dau\ mam\ xoi\ dau

thì chuỗi đầu ra sẽ là nhãn (tag sequence) được giống hàng tương ứng

D\ N\ V\ N\ N\ N

Ở đây, D: determinator (định từ), N: noun (danh từ), V: verb (động từ). Khi đó, ta có chuỗi các cặp từ và từ loại tương ứng như sau con/D \ ruoi/N \ dau/V \ mam/N \ xoi/N \ dau/N

Gán nhãn (sequence labeling problem, tagging problem) có các bài toán thường gặp

  • POS tagging (gán nhãn từ loại). Là cơ sở phục vụ cho các bài toán về ngữ nghĩa cao hơn.
  • Named-Entity recognition (gán nhãn tên thực thể). Ví dụ: bà ba [CON NGUOI] bán bánh mì [THUC PHAM] ở phường mười ba [DIA DIEM]. Có giá trị về mặt ngữ nghĩa ở mức trung bình, thường được dùng để phân lớp văn bản.
  • Machine translation (dịch máy). Đầu vào là một câu của ngôn ngữ A, đầu ra là câu của ngôn ngữ B tương ứng. Bài toán này từng rất cấp thiết trong chiến tranh thế giới thứ 2, khi mà thông tin tình báo của địch cần được dịch trong thời gian ngắn nhất, giúp cho các lãnh đạo có thể đưa ra những chiến lược cấp thiết.
  • Speech recognition (nhận diện tiếng nói). Đầu vào là âm thanh tiếng nói, đầu ra là câu dạng văn bản. Ngày nay, theo thống kê của Apple, người dùng thích sử dụng tiếng nói của mình để nhập văn bản hơn là cách nhập dữ liệu bằng bàn phím như truyền thống, đồng thời tương tác giữa người và máy theo cách này có tốc độ nhập liệu nhanh hơn.

Khi làm việc với bài toán này ta sẽ đối mặt với hai thách thức chính

  • Nhập nhằng (ambiguity): một từ có thể có nhiều từ loại, hay một từ có thể có nhiều nghĩa, Ví dụ “con ruồi đậu mâm xôi đậu“, từ “đậu” có lúc là động từ (hành động đậu lên một vật thể) hoặc có lúc là danh từ (tên của một loài thực vật).
  • Trong thực tế, có nhiều từ không xuất hiện trong ngữ liệu huấn luyện (training corpus) nên khi xây dựng mô hình gán nhãn sẽ gặp nhiều khó khăn.

Độ chính xác của mô hình gán nhãn phụ thuộc vào hai yếu tố

  • Bản thân từ đó sẽ có xu hướng (xác suất lớn) về từ loại nào. Ví dụ từ “đậu” có xu hướng là động từ nhiều hơn là danh từ (phụ thuộc vào ngữ liệu đang xét).
  • Ngữ cảnh trong câu. Ví dụ “con ruồi đậu mâm xôi đậu“. Từ “đậu” có xu hướng là động từ khi theo sau từ “ruồi” và từ “đậu” có xu hướng là danh từ khi theo sau từ “xôi”.

Generative Models, và The Noisy Channel Model

Để gán nhãn từ loại, ta sử dụng phương pháp học có giám sát (supervised learning), cụ thể là xác suất liên hợp thường gọi là mô hình sinh mẫu (Generative model). Hidden Markov Model là một trong những mô hình thuộc phân nhóm này.

Supervised learning được định nghĩa như sau

Cho tập huấn luyện (x^{(1)}, y^{(1)})...(x^{(m)}, y^{(m)}), trong đó đầu vào gồm x^{(i)} là mẫu quan sát, y^{(i)} là nhãn gán cho mẫu quan sát. Ta đặt X là tập dữ liệu đầu vào, Y là tập dữ liệu đầu ra. Nhiệm vụ của chúng ta là xây dựng được hàm f : X \to Y ánh xạ x vào không gian f(x).

Để tính hàm f(x) ta có thể sử dụng mô hình điều kiện conditional model. Đây là mô hình thường dùng trong tác vụ phân lớp. Ví dụ, cho vào một bức ảnh x, xác định xem đây là ảnh con mèo hay con chó bằng nhãn y

p(y|x)

Sau khi huấn luyện các tham số của mô hình. Ta cho dữ liệu đầu vào là x, dữ liệu đầu ra sẽ được tính dựa theo công thức

f(x) = arg \max_{y \in Y} p(y|x).

Một hướng tiếp cận khác là generative model,  thay vì tính trực tiếp hàm p(y|x) ta tính xác suất hợp (joint probability)

p(x, y).

Hàm này được phân tích thành

p(x, y) = p(y)p(x|y).

Trong đó

  • p(y) là phân bố xác suất tiền nghiệm (prior probability distribution) của nhãn y.
  • p(x|y) là khả năng phát sinh x khi cho trước nhãn y.

p(y) và p(x|y) thường được gọi là noisy-channel. p(x|y) là một “channel”

Khi cho dữ liệu test đầu vào x, ta sẽ dự đoán nhãn y như sau

f(x) = arg \max_y p(y|x) = arg \max_y \frac{p(y)p(x|y)}{p(x)}

f (x) = arg \max_{y\in Y} p(y)p(x|y)

Quá trình phân tích ra f(x) từ dữ liệu đầu vào x được gọi là decoding problem. Tiếp theo, ta sẽ áp dụng generative model vào bài toán gán nhãn gọi tên là Generative Tagging Model.

Generative Tagging Model

Định nghĩa: giả sử ta có tập từ vựng V và tập nhãn K. S là tập tất cả các cặp sequence/tag-sequence <x_1...x_n, y_1...y_n> sao cho n \ge 0, x_i \in V, i = 1...n và y_i \in K, i = 1...n. Khi đó generative tagging model là một hàm p sao cho

  1. Với mọi <x_1...x_n, y_1...y_n> \in S

p(x_1...x_n, y_1...y_n) \ge 0

  1. Và

\sum_{<x_1...x_n, y_1...y_n> \in S} p(x_1...x_n, y_1...y_n) = 1

Ta xây dựng ánh xạ từ câu x_1...x_n vào chuỗi nhãn (tag sequences) y_1...y_n. Với mọi x_1...x_n, ta sẽ chọn ra chuỗi nhãn y_1...y_n nào có giá trị xác suất cao nhất.

f(x_1...x_n) = arg \max_{y_1...y_n} p(x_1...x_n,y_1...y_n)

Để xây dựng được hàm này ta cần trả lời các câu hỏi sau:

  1. Làm sao tính được p(x_1...x_n, y_1...y_n) ?
  2. Ước lượng tham số cho mô hình như thế nào từ ngữ liệu huấn luyện?
  3. Làm sao tính được xác suất cực đại \max_{y_1...y_n} p(x_1...x_n,y_1...y_n)

Trigram Hidden Markov Models (Trigram HMMs)

Ở câu hỏi đầu tiên, ta sẽ dùng trigram hidden Markov model. Mô hình này có hai tham số quan trọng là  q(s|u,v) và e(x|s). Khi cho trước tập hữu hạn từ vựng V và nhãn K. Ta có:

  • Với mọi trigram (u,v,s), ta có s \in K \cup \{STOP\}, và u, v \in K \cup \{*\}.  q(s|u,v) là khả năng nhìn thấy nhãn s ngay sau bigram nhãn (u,v).
  • Với mọi x \in V, s \in K.  e(x|s) là khả năng của quan sát (observation/từ trong câu) x đi với nhãn s (state).

Với S là tập tất cả các cặp chuỗi quan sát/nhãn (sequence/tag-sequence pairs) <x_1...x_n, y_1...y_{n+1}>. Khi đó, xác suất cặp chuỗi quan sát/nhãn được xác định như sau

p(x_1...x_n, y_1...y_{n+1}) = \prod_{i=1}^{n+1} q(y_i|y_{i-2}, y_{i-1}) \prod_{i=1}^n e(x_i|y_i)

Lưu ý, ta đặt y_0 = y_{-1} = *

Ví dụ câu “em ăn cơm”

p(x_1...x_n, y_1...y_{n+1}) = q(N|*,*) \times q(V|*,N) \times q(N|N,V) \times q(STOP|V,N) \times e(em|N) \times e(an|V) \times e(com|N)

Đây là một ví dụ cho mô hình noisy-channel với

q(N|*,*) \times q(V|*,N) \times q(N|N,V) \times q(STOP|V,N)

là xác suất tiền nghiệm nhìn thấy chuỗi nhãn N\ V\ N\ STOP. Ở đây, ta áp dụng mô hình Markov bậc hai hay mô hình trigram vào trong câu. Và

e(em|N) \times e(an|V) \times e(com|N)

là xác suất có điều kiện của p(em\ an\ com | N\ V\ N\ STOP). Ta có thể thấy, đây chính là xác suất có điều kiện p(x|y), trong đó x là câu em\ an\ com và y là chuỗi nhãn N\ V\ N\ STOP

Ước lượng tham số cho mô hình Trigram HMM

Trả lời cho câu hỏi thứ hai, ta sẽ ước lượng tham số của mô hình bằng phương pháp maximum-likelihood cho hai tham số q(s|u,v) và e(x|s) như sau

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

e(x|s) = \frac{c(s \leadsto x)}{s}

Trong đó

  • c(u, v, s) là số lần xuất hiện trigram (u, v, s) trong ngữ liệu huấn luyện.
  • c(u, v) là số lần xuất hiện bigram (u, v) trong ngữ liệu huấn luyện.

Ví dụ ta ước lượng

q(N|N,V) = \frac{c(N, V, N)}{c(N, V)}

e(com|N) = \frac{c(N \leadsto com)}{N}

Trong trường hợp ta muốn “làm trơn” tham số để giải quyết vấn đề xuất hiện từ hiếm gặp, ta có thể thêm vào các thông số \lambda như bên dưới

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

Trong đó, q_{ML} là xác suất tính được dựa vào maximum-likelihood, \lambda_1, \lambda_2, \lambda_3 là thông số làm trơn thoả \lambda_1 \ge 0, \lambda_2 \ge 0, \lambda_3 \ge 0 và \lambda_1 + \lambda_2 + \lambda_3 = 1

Decoding HMMs bằng thuật toán Viterbi

Giả sử ta có câu đầu vào là

em ăn cơm

với tập các từ loại K = \{N, V\}, ta có thể phát sinh các chuỗi nhãn như bên dưới

N N N STOP N N V STOP N V V STOP V V V STOP …

Như vậy, đối với câu gồm 3 từ, ta sẽ có tất cả 2^3 = 8 các khả năng. Con số này sẽ bùng nổ khi số từ vựng và chuỗi từ ngày càng tăng.

Ý tưởng thuật toán Viterbi

Thay vì tính toán hết các trường hợp, ta có thể áp dụng phương pháp quy hoạch động (dynamic programming) như thuật toán Viterbi với

Đầu vào: x_1...x_n

Đầu ra: y_{-1}, y_0, y_1,...,y_n. Trong đó, k \in {1...n}, y_i \in K, i = 1...k và y_{-1} = y_0 = *

Xác suất có điều kiện của k nhãn đầu tiên là

r (y_{-1}, y_0, y_1, ..., y_k) = \prod_{i = 1}^k q(y_i|y_{i-2}, y_{i-1}) \prod_{i=1}^k e(x_i|y_i)

Như vậy công thức p(x_1...x_n, y_1...y_{n+1}) ban đầu sẽ thành

p(x_1...x_n, y_1...y_{n+1}) = r(*,*, y_1,...,y_n) \times q(y_{n+1} | y_{n-1}, y_n)

= r(*,*, y_1,...,y_n) \times q(y_{n+1} | STOP, y_n)

Đặt K_k, k \in \{-1...n\} là các giá trị có thể có của nhãn tại vị trí thứ k. Trong đó, K_{-1} = K_0 = {*} và K_k = K, k \in \{1...n\}.

Tiếp theo, với mọi k \in \{1...n\}, với mọi u \in K_{k-1}, v \in K_k, ta định nghĩa S(k, u, v) là tập các chuỗi y_{-1}, y_0, y_1, ..., y_k sao cho y_{k-1} = u, y_k = v và y_i \in K_i, i \in \{-1...k\}. Nói cách khác, S(k, u, v) là tập tất cả chuỗi các nhãn có độ dài k, kết thúc là bigram (u, v). Ta đi xây dựng công thức sau

\pi (k, u, v) = max_{<y_{-1}, y_0, y_1, ..., y_k> \in S(k, u, v)} r (y_{-1}, y_0, y_1, ..., y_k).

Trong đó, \pi (k, u, v) là xác suất cực đại mà ta thu được với chuỗi có độ dài k kết thúc là bigram (u,v). Để tính hàm này, ta định nghĩa đệ quy với

Phần cơ sở

\pi (0, *, *) = 1

Phần đệ quy

Với mọi k \in \{1...n\}, với mọi u \in K_{k-1}, v \in K_k, ta định nghĩa hàm đệ quy

\pi (k, u, v) = max_{w \in K_{k-2}} (\pi (k-1, w, u) \times q(v|w, u) \times e(x_k|v))

Như vậy, ta đã trả lời được câu hỏi thứ ba

\max_{y_1...y_{n+1}} p(x_1...x_n, y_1...y_{n+1}) = \max_{u \in K_{n-1}, v \in K_n} (\pi (n, u, v) \times q(STOP|u,v))

Độ phức tạp tính toán của thuật toán này là O(n|K|^3), tuyến tính theo độ dài n của chuỗi và bằng lập phương số lượng nhãn. Nếu số lượng nhãn không quá lớn, thuật toán này có thể đạt được độ phức tạp tuyến tính.

Tiếp theo, ta sẽ mô tả bằng ngôn ngữ mã giả bằng hai thuật toán: thuật toán đệ quy cơ bản và thuật toán đệ quy có con trỏ lần ngược (để xác định chuỗi nhãn đang xét có xác suất là bao nhiêu).

Thuật toán đệ quy cơ bản

Input: a sentence x_1...x_n, parameters q(s|u, v) and e(x|s).

Definitions: Define K to be the set of possible tags. Define K_{-1} = K_0 = \{*\}, and K_k =K for k=1...n.

Initialization: Set \pi (0, *, *) = 1.

Algorithm:

  • For k=1...n,
    • For u \in K_{k-1}, v \in K_k,
      • \pi (k, u, v) = max_{w \in K_{k-2}} (\pi (k-1, w, u) \times q(v|w, u) \times e(x_k|v))
  • Return max_{u \in K_{n-1}, v \in K_n} (\pi (n, u, v) \times q(STOP|u, v))

Thuật toán đệ quy có backward pointer

Input: a sentence x_1...x_n, parameters q(s|u, v) and e(x|s).

Definitions: Define K to be the set of possible tags. Define K_{-1} = K_0 = \{*\}, and K_k =K for k=1...n.

Initialization: Set \pi (0, *, *) = 1.

Algorithm:

  • For k=1...n,
    • For u \in K_{k-1}, v \in K_k,
      • \pi (k, u, v) = max_{w \in K_{k-2}} (\pi (k-1, w, u) \times q(v|w, u) \times e(x_k|v))
      • bp(k, u, v) = arg max_{w \in K_{k-2}} (\pi (k-1, w, u) \times q(v|w, u) \times e(x_k|v))
  • Set (y_{n-1}, y_n) = arg max_{u \in K_{n-1}, v \in K_n} (\pi(n, u, v) \times q(STOP|u, v))
  • For k = (n-2)...1,
    • y_k = bp(k+2, y_{k+1}, y_{k+2})
  • Return the tag sequence y_1...y_n

Kết

Như vậy, ta đã tìm hiểu được thế nào là bài toán gán nhãn từ loại, các hướng tiếp cận và thuật toán để giải quyết vấn đề này. Một số điểm cần nhớ

  • Trigram HMM có hai tham số quan trọng là q(s|u, v) và e(x|s) để định nghĩa lên mô hình cho chuỗi đầu vào là x_1...x_n và chuỗi nhãn tương ứng là y_1...y_{n+1}, với y_{n+1} = STOP.

p(x_1...x_n, y_1...y_{n+1}) = \prod_{i=1}^{n+1} q(y_i|y_{i-2}, y_{i-1}) \prod_{i=1}^n e(x_i|y_i)

  • Khi cho trước ngữ liệu huấn luyện, ta có thể ước lượng maximum-likelihood cho hai tham số trên

q(s|u,v) = \frac{c(u,v,s)}{c(u,v)} e(x|s) = \frac{c(s \leadsto x)}{(c(s)}

  • Khi cho một câu test đầu vào x_1...x_n và tham số q, e được ước lượng trong quá trình huấn luyện, ta có thể xác định được xác suất cực đại của chuỗi nhãn x_1...x_n thông qua thuật toán Viterbi.

Nguồn tham khảo

  • Tagging Problems, and Hidden Markov Models
  • Gán nhãn từ loại tiếng Việt dựa trên các phương pháp học máy thống kê
  • JVnTagger: Công cụ gán nhãn từ loại tiếng Việt dựa trên Conditional Random Fields và Maximum Entropy
  • Gán nhãn từ loạI cho tiếng việt dựa trên văn phong và tính toán xác suất
  • Gán nhãn từ loạI tiếng việt sử dụng mô hình markov ẩn
  • Sử dụng bộ gán nhãn từ loạI xác suất qtag cho văn bản tiếng việt
  • Facebook
  • LinkedIn
Thích Đang tải...

Có liên quan

Từ khóa » Gán Nhãn Từ Loại Tiếng Việt