Gán nhãn từ loại (Part-of-Speech tagging POS)

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...ny_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

\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\ comy 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\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...ky_{-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 = {*}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 = vy_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)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

Advertisement

Một suy nghĩ 9 thoughts on “Gán nhãn từ loại (Part-of-Speech tagging POS)

  1. Hi anh,
    Đối với bài toán Knowledge Extraction From Text thì hướng giải quyết như thế nào anh nhỉ? Ở đây vẫn tập trung vào các close domain anh nhé, ví dụ như từ 1 đống văn bản về kiến thức nông nghiệp, em muốn build lên 1 graph để tiện tìm kiếm thông tin liên quan đến nông nghiệp chẳng hạn ạ. Theo em tìm hiểu thì ở đây có 2 phần cần tách bạch:
    1. Cấu trúc của graph, định nghĩa các nodes, edges, … như thế nào?
    2. Gán dữ liệu cho các thành phần đã định nghĩa ở trên.
    Mong anh cho ý kiến ạ. Thanks anh.

    Thích

    1. Hướng tiếp cận của em cũng là một cách để truy vấn thông tin dựa trên Graph, như vậy tri thức của em sẽ là quan hệ trên đồ thị. Ngoài ra còn có những hướng tiếp cận khác để trích chọn những đặc trưng tri thức trong văn bản như:
      Rapier: https://vvvvw.aaai.org/Papers/AAAI/1999/AAAI99-048.pdf
      BWI: http://www.aaai.org/Papers/AAAI/2000/AAAI00-088.pdf
      Memory Based Learning algorithm (MBL): http://delivery.acm.org/10.1145/980000/977059/p173-sang.pdf
      Transformation-based learning (TBL): http://shiva.iiit.ac.in/SPSAL2007/SPSAL-Proceedings.pdf#page=27
      SVM, MaxEnt, HMM, và CRF cho tác vụ Name Entity Recognition.

      Thích

      1. Những bài báo anh giới thiệu ở trên theo em hiểu là phần thứ 2. em có nêu ra ở trên, tức là gán dữ liệu cho các thành phần của Graph sau khi đã định nghĩa cấu trúc. Em thì lại đang thắc mắc ở cách xây dựng cấu trúc anh ạ.

        Thích

        1. Ý tưởng chung đó là rút trích NER và lưu thành cấu trúc quan hệ ví dụ như cơ sơ dữ liệu quan hệ. Từ đó, ta áp dụng các thuật toán tìm kiếm, matching subgraph, finding pattern trong CSDL này.
          Một số tài liệu em có thể đọc để nắm tổng quan và các thuật toán state-of-the-art:

          Click to access Graph-based-KBs-eng.pdf

          Click to access 1503.00759.pdf

          Click to access Maitrayee-Mukherjee-LinkKDD-2004.pdf

          Click to access 1237_Quirin-JOI-4-3-2010-pp291-312.pdf

          https://github.com/gromgull/subdue

          Click to access Washio.pdf

          Thích

  2. Hi anh, anh có thể viết bài bao gồm cả thuật toán để xử lý bài toán tự động thêm dấu cho tiếng việt được không ạ? Hoặc có nguồn nào tham khảo không ạ? Em cảm ơn anh

    Thích

Trả lời

Điền thông tin vào ô dưới đây hoặc nhấn 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 Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s