Posted in Khác

Gán nhãn từ loại cho từ Tiếng Anh

Trigram Hidden Markov Model

I) Giới thiệu

Một số lượng lớn hệ thống xử lý ngôn ngữ hiện tại sử dụng part-of-speech tagger như một công việc tiền xử lý . Gán nhãn từ loại là công việc

Yêu cầu của bài toán gán nhãn từ loại là khả năng phân loại đúng cao .

Mô hình Markov cùng với kĩ thuật smoothing tốt và xử lý unknown words mang lại phần trăm cao và training và tagging tốc độ cao .

  1. Bài toán gán nhãn từ loại

P (T1 … Tn / w1 … wn)

Ti là nhãn từ loại , wi là từ

Ta cần tìm T1 … Tn sao cho xác suất trên là cực đại

Sử dụng quy tắc Bayes :

P (T1 … Tn / w1 … wn)=

Do mẫu số không phụ thuộc vào nhãn , nên ta cần tìm T1…Tn sao cho tử số đạt cực đại

+)Hạng thức thứ nhất

P (T1 … Tn)=P(T1)P(T2/T1)P(T3/T2T1)  ………..P(Tn/Tn-1..T1)

≈ P(T1)P(T2/T1)

+) Hạng thức thứ hai

P(w1 … wn/ T1 … T2) ≈

1 hashmap lưu xs wi/ti

Key là tag

value là 1 hashmap có key là word , value là số lần xuất hiện

Tổng hợp lại

P(T1…Tn)P(w1…wn/T1…Tn)= P(T1)P(T2/T1)

Với P(T1)=P(T1/T0)

P(T2/T1)=P(T2/T1,T0)

Với To là kí tự đặc biệt kí hiệu đầu câu

1hashmap key là tên tag , value là vị trí trong mảng

1 mảng 3 chiều lưu xs ti/ti-1,ti-2

1 mảng 2 chiều lưu xs ti/ti-1

1 mảng 1 chiều lưu xs ti

1 mảng 1 chiều lưu xs t1/t0

1 mảng 2 chiều lưu xs t2/t1 , t0 .

  1. Smoothing

P(Ti/Ti-1,Ti-2) không thể tính trực tiếp được bởi vì vấn đề thưa thớt của dữ liệu . Nghĩa là không phải bộ ba Ti Ti-1 Ti-2 nào cũng xuất hiện trong văn bản .

Sử dụng nội suy tuyến tính (linear interpolation)

Ps(Ti/Ti-1,Ti-2 = λ1 P(Ti)+ λ2P(Ti/Ti-1)+ λ2(Ti/Ti-1,Ti-2)

Với λ1+ λ2+ λ3=1

Λ1,2,3 xác định bởi công thức

Λ1= λ2= λ3=0

Với mỗi trigram T1,T2,T3  với P(T1,T2,T3)>0

Phụ thuộc vào giá trị lớn nhất của 3 giá trị sau

Nếu (P(T1,T2,T3)-1)/(P(T1,T2)-1) thì λ3+=P(T1,T2,T3)

Nếu (P(T2,T3)-1)/(P(T2)-1)thì λ2+=P(T1,T2,T3)

Nếu (P(t3)-1)/N thì λ1+=P(T1,T2,T3)

Chuẩn hóa λ1, λ2, λ3

N là kích thước của bộ từ đã được phân loai

  • Xử lý từ chưa xuất hiện trong tập từ đã được phân loại

Có rất nhiều phương pháp xử lý unknown word : Laplace (làm tốt trong text categorization nhưng không tốt trong pos tagging), Good-Turing , Kneser-Ney , suffix analysis .

Trong những ngôn ngữ đặc thù như tiếng anh thì nhưng từ có kết thúc là able thì thường là adjectives (JJ) đến 98% (fashionable,  ) còn 2% là danh từ (N) ( cable , variable).

Xác suất  m từ cuối li của 1 từ có n từ mang nhãn t là P( ,…, /t)

Smoothing

P( ,…, /t) =

Với  =

Số loại từ là s

a =   ^2

P=

Số hậu tố sẽ lấy từ 1 đến 10 hậu tố xem trường hợp nào tốt nhất sẽ lấy làm số hậu tố cuối cùng : Giả sử là n là trường hợp tốt nhất

Khi đọc 1 từ trong bộ ngữ liệu của chúng ta , ta thêm n hậu tố của từ này vào hashmap chứa hậu tố , n hậu tố này có độ dài từ 1 đến n

Key của hashmap là các hậu tố value 1 mảng m phần tử là số lần xuất hiện các hậu tố theo loại từ .

Đồng thời cũng có 1 mảng m phần tử , phần tử i lưu số lần xuất hiện của hậu tố có độ dài I trong bộ ngữ liệu .

Sau khi đọc hết bộ ngữ liệu sẽ lấy toàn bộ value ra để tính xác suất

chuyển về log e.

  1. Thuật toán Viterbi

Có 3 mảng :

Mảng 1 lưu tên từ vừa xét

Mảng 2 lưu max tại từ đó

Mảng 3 lưu đường đi từ gốc tới từ đó

Khi chuyển sang từ mới :

Xác định các từ loại của từ đó thêm vào 1 mảng

http://www.sls.hawaii.edu/bley-vroman/brown_corpus.html

Advertisements

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đă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 )

Google+ photo

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

Connecting to %s