BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
CƠ SỞ 2 THÀNH PHỐ HỒ CHÍ MINH

MÔN HỌC:
NGUYÊN LÝ CHƯƠNG TRÌNH DỊCH
GV BỘ MÔN:TS HÀ CHÍ TRUNG
ĐỀ TÀI:
TÌMHIỂUVẤNĐỀGÁNNHÃNVĂN BẢNTIẾNGVIỆT
VÀ MỘT SỐ PHƯƠNG PHÁPGÁNNHÃNVĂN BẢN (ÍT
NHẤT2 PHƯƠNG PHÁP)
Học viên thực hiện : Phan Thị Ngọc Tuyết Vân
Mã học viên : 14871114
Lớp :CHKHMT K.26B
Tp.HCM, năm 2015
Đồ án môn Nguyên Lý Chương Trình Dịch

LỜI MỞ ĐẦU
Kính Thưa Thầy, trước tiên em xin gởi đến Thầy lời cảm ơn chân thành nhất.
Thầy đã hướng dẫn môn học NGUYÊN LÝ CHƯƠNG TRÌNH DỊCH cho lớp
CHKHMT – TPHCM25A13. Dẫu trong thời gian ngắn, nhưng Thầy đã giảng giải cho
chúng em khái quát và những gì cô đọng nhất về môn học. Khi phân công bài tập, Thầy
hướng dẫn và phân tích để chúng em hiểu cách trình bày cho việc hoàn thành bài tập.
Em rất cảm ơn sự tận tâm của Thầy đã giúp chúng em hoàn tất bài tập.
Trong khuôn khổ của một bài viết sẽ không tránh khỏi những thiếu sót. Em rất
mong nhận được sự góp ý cũng như chỉ bảo thêm của Thầy, được như vậy tất cả chúng
em sẽ có thể được học hỏi thêm nhiều kiến thức của Thầy, giúp chúng em tiến bộ hơn
trong tương lai.
Trân trọng.
MỤC LỤC
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 2

hữu ích cho mình.
II. Qui trình xử lý ngôn ngữ tự nhiên
Để máy tính có thể hiểu và thực thi một chương trình được viết bằng ngôn ngữ cấp
cao, ta cần phải có một trình biên dịch thực hiện việc chuyển đổi chương trình đó sang
chương trình ở dạng ngôn ngữ đích. Cấu trúc của trình biên dịch là một cấu trúc mức
quan niệm bao gồm các giai đoạn: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ
nghĩa, Sinh mã trung gian, Tối ưu mã và Sinh mã đích. Nói một cách đơn giản, trình biên
dịch là một chương trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn
ngữ - ngôn ngữ nguồn (source language) - rồi dịch nó thành một chương trình tương
đương ở một ngôn ngữkhác - ngôn ngữ đích (target languague). Một phần quan trọng
trong quá trình dịch là ghi nhận lại các lỗi có trong chương trình nguồn để thông báo lại
cho người viết chương trình
1. Phân tích từ vựng (Lexical Analysis)
Phân tích từ vựng là giai đoạn đầu tiên của mọi trình biên dịch. Nhiệm vụ chủ yếu
của nó là đọc các ký hiệu đầu vào rồi tạo ra một chuỗi các mã thông báo token được sử
dụng bởi bộ phân tích cú pháp.
2. Phân tích cú pháp (Syntax Analysis)
Giai đoạn phân tích cú pháp thực hiện công việc nhóm các thẻ từ của chương trình
nguồn thành các ngữ đoạn văn phạm (grammatical phrase), mà sau đó sẽ được trình biên
dịch tổng hợp ra thành phẩm. Thông thường, các ngữ đoạn văn phạm này được biểu diễn
bằng dạng cây phân tích cú pháp (parse tree) với:
- Ngôn ngữ được đặc tả bởi các luật sinh.
- Phân tích cú pháp dựa vào luật sinh để xây dựng cây phân tích cú pháp.
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 4
Đồ án môn Nguyên Lý Chương Trình Dịch

3. Phân tích ngữ nghĩa (Semantic Analysis)
Giai đoạn phân tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương trình nguồn
có chứa lỗi về ngữ nghĩa hay không và tập hợp thông tin về kiểu cho giai đoạn sinh mã
về sau. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu (type

Giai đoạn tiền xử lý: Phân tách xâu ký tự thành chuỗi các từ. Giai đoạn này có thể
đơn giản hay phức tạp tuỳ theo ngôn ngữ và quan niệm về đơn vị từ vựng. Chẳng hạn đối
với tiếng Anh hay tiếng Pháp, việc phân tách từ phần lớn là dựa vào các ký hiệu trắng.
Tuy nhiên vẫn có những từ ghép hay những cụm từ gây tranh cãi về cách xử lý. Trong
khi đó với tiếng Việt thì dấu trắng càng không phải là dấu hiệu để xác định ranh giới các
đơn vị từ vựng do tần số xuất hiện từ ghép rất cao.
Khởi tạo gán nhãn: tức là tìm cho mỗi từ tập tất cả các nhãn từ loại mà nó có thể
có. Tập nhãn này có thể thu được từ cơ sở dữ liệu từ điển hoặc kho ngữ liệu đã gán nhãn
bằng tay. Đối với một từ mới chưa xuất hiện trong cơ sở ngữ liệu thì có thể dùng một
nhãn ngầm định hoặc gắn cho nó tập tất cả các nhãn. Trong các ngôn ngữ biến đổi hình
thái người ta cũng dựa vào hình thái từ để đoán nhận lớp từ loại tương ứng của từ đang
xét.
Quyết định kết quả gán nhãn: đó là giai đoạn loại bỏ nhập nhằng, tức là lựa chọn
cho mỗi từ một nhãn phù hợp nhất với ngữ cảnh trong tập nhãn khởi tạo nói trên. Có
nhiều phương pháp để thực hiện việc này, trong đó người ta phân biệt chủ yếu các
phương pháp dựa vào quy tắc ngữ pháp (với đại diện nổi bật là phương pháp Brill) và các
phương pháp xác suất. Ngoài ra còn có các hệ thống sử dụng mạng nơ-ron, các hệ thống
lai sử dụng kết hợp tính toán xác suất và ràng buộc ngữ pháp, gán nhãn nhiều tầng, …
7. Các khó khăn của bài toán gán nhãn từ loại
Nếu mỗi từ chỉ có một nhãn từ loại và ta có thể xây dựng được một từ điển hữuhạn
các từ và nhãn tương ứng của nó thì chắc chắn có thể giải quyết được bài toán gánnhãn từ
loại với kết quả tối ưu. Tuy nhiên, trong thực tế một từ đôi khi có thể có nhiềuhơn một
nhãn từ loại thích hợp, và ta cũng không thể kiểm soát được toàn bộ các từ cóthể xuất
hiện trong văn bản, điều này dẫn đến hai vấn đề mà bài toán gán nhãn từ loạiphải đối
mặt: Nhập nhằng từ loại và từ mới.Vấn đề chủ yếu của bài toán gán nhãn từ loại thực
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 6
Đồ án môn Nguyên Lý Chương Trình Dịch

chất là việc loại bỏ nhậpnhằng về từ loại, tức là khi một từ có nhiều từ loại, nhưng trong
một ngữ cảnh cụ thể,nó chỉ có thể có một từ loại đúng mà thôi

• Có khả năng tiến hành thực hiện việc gán nhãn (Tức là số lượng các từ loại càng ít càng
dễ tiến hành).
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 7
Đồ án môn Nguyên Lý Chương Trình Dịch

8. Các hướng tiếp cận bài toán gán nhãn từ loại
a. Gán nhãn bằng phương pháp dựa trên hệ luật
Đây là phương pháp gán nhãn từ loại ra đời sớm nhất, các bộ gán nhãn “sơ
khai”đều thực hiện theo phương pháp này. Nội dung chính của phương pháp này là
xâydựng một cơ sở dữ liệu lớn các “luật” được viết bằng tay, vì vậy phương pháp này
cònđược gọi là phương pháp gán nhãn thủ công. Các luật được xây dựng dựa vào ngữ
cảnh thích hợp, ví dụ, nếu một từ nhập nhằng đang xét đi sau một từ chỉ định thì nó có
xuhướng là một danh từ hơn là một động từ.
Đại diện tiêu biểu cho nhóm các phương pháp thủ công dựa trên hệ luật này
làENGTWOL (Voutilainen, 1995).
b. Các phương pháp dựa vào học máy
Phương pháp dựa trên luật là một phương pháp thủ công còn tiềm tàngrất nhiều
nhập nhằng. Cùng với đó, việc xây dựng một hệ thống trích chọn dựa trêncác luật là rất
tốn công sức. Thông thường để xây dựng một hệ thống như vậy đòi hỏicông sức vài
tháng từ một lập trình viên với nhiều kinh nghiệm về ngôn ngữ học. Giảipháp cho các
giới hạn này là phải xây dựng một hệ thống bằng cách nào đó có thể “tựhọc”, điều này sẽ
giúp giảm bớt sự tham gia của các chuyên gia ngôn ngữ và làm tăngtính khả chuyển cho
hệ thống, các phương pháp như vậy được gọi là các phương phápdựa vào học máy.
Như đã nói ở trên, các phương pháp dựa vào học máy là các phương pháp
xâydựng hệ thống mà bằng cách nào đó có thể “tự học” (để ngắn gọn ở các phần dưới
đâyta sẽ gọi là các phương pháp học máy). Phần này sẽ xem xét một đại diện tiêu biểu
củaphương pháp học máy, giải quyết nhập nhằng bằng cách sử dụng một bộ dữ liệu
huấnluyện để tính toán xác suất của một từ cho sẵn sẽ được gán với một nhãn nào đó
trongngữ cảnh cho trước, vì bản chất đó, họ các phương pháp này còn được gọi là
cácphương pháp xác suất.

Tˆ = argmaxT ∈τ P(T )P(W | T )
Áp dụng luật chuỗi xác suất, ta có công thức
Vẫn không có phương pháp hiệu quả để tính xác suất của chuỗi này một cáchchính
xác, vì nó yêu cầu quá nhiều dữ liệu. Ở đây ta phải áp dụng các giả thiết độc lậpđiều kiện
để có một xác suất đơn giản hơn (giả thiết rằng mỗi từ đều là độc lập với cáctừ khác và
đặc tính của một từ chỉ phụ thuộc vào nhãn của nó). Sử dụng giả thiết N-gram để mô hình
hóa xác suất chuỗi từ:
Cụ thể ta dùng mô hình phổ biến nhất là mô hình tri-gram.
P
( t1 ,t2 ,t3 ) = P ( t2 | t1 ) P ( t3 | t2 )
Đầu tiên, ta đơn giản hóa rằng xác suất của một từ thì chỉ phụ thuộc vào nhãn
củanó:
P(w
i
| w
1
t
1
w
i
−
1
t
i
−
1
t
i
) = P(w
i

Ta có thể mô hình hóa HMM dưới dạng một đồ thị có hướng như hình
Như đã nói ở trên, thông thường trong mô hình HMM thuật toán hay được sửdụng
để tìm dãy trạng thái tối ưu là thuật toán Viterbi. Thuật toán này dựa trêncông thức truy
hồi dưới đây:
Một trong những bộ gán nhãn tiêu biểu sử dụng phương pháp này là bộ gán
nhãnTnT của tác giả Thorsten Brants sử dụng phương pháp tri-gram, cho kết quả 96.7%
vớitập nhãn Penn TreeBank và bộ dữ liệu WallStreet trong tiếng Anh. QTAG là mộtbộ
gán nhãn dựa trên mô hình HMM do nhóm nghiên cứu Corpus Research thuộctrường đại
học tổng hợp Birmingham phát triển, cung cấp miễn phí cho mục đíchnghiên cứu. Một
điểm nổi trội của QTAG là dù được xây dựng cho tiếng Anh nhưngnó có thể được huấn
luyện để sử dụng cho các ngôn ngữ khác. Phương pháp xácsuất còn được sử dụng để gán
nhãn từ loại trong rất nhiều ngôn ngữ khác nhau, ví dụviệc áp dụng mô hình HMM cho
bài toán gán nhãn từ loại tiếng Trung Quốc đạt đến93.5 % trong nghiên cứu của các tác
giả GouDong Zhou và Jian Su; Hai tác giảFábio N.Kepler và Marcelo Finger cũng công
bố kết quả sử dụng mô hình HMM đểgán nhãn từ loại cho tiếng Bồ Đào Nha với kết quả
93.48 % .
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 10
Đồ án môn Nguyên Lý Chương Trình Dịch

Tuy nhiên, mặc dù tính đến thời điểm hiện tại, đây là một trong những
phươngpháp gán nhãn theo phương pháp xác suất thông dụng nhất được biết đến nhưng
nóvẫn còn tiềm tàng những giới hạn khó giải quyết. Adrew McCallum trong các
nghiêncứu của mình đã đưa ra hai vấn đề mà các mô hình HMM truyền thống nói riêngvà
các mô hình sinh (generative models) nói chung gặp phải khi gán nhãn cho dữ liệudạng
chuỗi.
Ngoài HMM, còn rất nhiều phương pháp xác suất khác có thể sử dụng để
giảiquyết bài toán gán nhãn từ loại nói chung và bài toán gán nhãn từ loại tiếng Việt
nóiriêng, nhiều trong số chúng có những ưu điểm giải quyết được các hạn chế của
môhình HMM mà ta đã nói ở trên. Cùng với đó, bên cạnh các phương pháp học máy
xácsuất, còn có các phương pháp học máy khác, ví dụ phương pháp học máy dựa trên

T
Chuyển nhãn
Điều kiện Ví dụ
Cũ Mới
1 NN VB Nhãn trước đó là TO To/TO race/NN VB
2 VBP VB
1 trong 3 nhãn trước đó là MD
Might /MD vanish/VBP
VB
3 NN VB
1 trong 2 nhãn trước đó là DT
Might/MD not
reply/NNVB
4 VB NN 1 trong 3 nhãn trước đó là VBZ
5 VBD VBN
Ví dụ: Xét từ “race” trong hai câu dưới đây
- It is expected to race tomorrow.
- The race for outer space.
Thuật toán sẽ thực hiện như sau:
• Đầu tiên, gán nhãn tất cả các từ “race” là NN (nhãn thường gặp nhất trong
tậpngữ liệu Brown corpus). Tức là:
“It is expected to race/NN tomorrow”
“The race/NN for outer space”
• Sau đó, sử dụng luật biến đổi để thay thế các nhãn NN bằng VB cho tất cả cáctừ
“race” mà đứng trước nó là từ được gán nhãn TO. Tức là:
“It is expected to race/VB tomorrow”
Và “The race/NN for outer space”
Đại diện tiêu biểu cho phương pháp này là bộ gán nhãn từ loại Brill’s (được
xâydựng bởi Eric Brill) sử dụng cho tiếng Anh, đây là một bộ gán nhãn rất thông dụng
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 12

ngoài ra không đưa thêm bất kì một giả thiết nào khác”. Điều này có nghĩa là phân phối
mô hình phải thỏa mãn mọi ràng buộc được rút ra từ thực nghiệm, và phải gần nhất với
phân phối đều. Nói theo ngôn ngữ toán học, ta phải tìm phân phối mô hình p(y|x)thỏa
mãn hai điều kiện, một là nó phải thuộc tập P’ và hai là nó phải làm cực đại Entropy điều
kiện.
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 13
Đồ án môn Nguyên Lý Chương Trình Dịch

Với P là không gian của tất cả các phân phối xác suất điều kiện,và P’ là tập con
của P, P’ được xác định như sau:
e. Mô hình xác suất
Mô hình xác suất được định nghĩa theo không gian H x T, trong đó H là tập từ có
thể và ngữ cảnh từ loại, hoặc còn gọi là “lịch sử”, và T là tập các nhãn có thể có. Xác suất
mô hình của lịch sử h cùng với nhãn t được định nghĩa theo công thức
Trong đó, Π là hằng số chuẩn hóa, {μ, α1, … αk} là các tham số mang giá trị
dương của mô hình và{f1, …, fk} chính là các đặc trưng, thỏa mãnfj (h,t){0, 1}. Chú
ýrằng mỗi tham số aj tương ứng với một đặc trưng fj.
Cho trước một tập các từ {w1, …, wn} và một chuỗi nhãn {t1, …, tn} được
xem là dữ liệu huấn luyện, ta định nghĩa hi là lịch sử khi dự đoán nhãn ti. Các tham số
{μ, α1,… αk} được chọn sao cho làm cực đại likelihood dữ liệu huấn luyện sử dụng p
theocông thức:
Mô hình này được xem xét dưới dạng Maximum Entropy, trong đó mục tiêu là
cực đại entropy của một phân phối dưới những ràng buộc nhất định. Ở đây, entropy của
phân phối p được định nghĩa theo công thức:
Và các ràng buộc được cho bởi công thức:
Trong đó kỳ vọng đặc trưng của mô hình là:
và kỳ vọng đặc trưng quan sát là:
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 14
Đồ án môn Nguyên Lý Chương Trình Dịch


CRF là mô hình đồ thị vô hướng. Điều này cho phép CRF có thể định nghĩa phân phối
xác suất của toàn bộ chuỗi trạng thái với điều kiện biết chuỗi quan sát cho trước thay vì
phân phối trên mỗi trạng thái với điều kiện biết trạng thái trước đó và quan sát hiện tại
như trong các mô hình đồ thị có hướng khác. Bản chất “phân phối điều kiện” và “phân
phối toàn cục” của CRF cho phép mô hình này khắc phục được những nhược điểm của
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 15
Đồ án môn Nguyên Lý Chương Trình Dịch

các mô hình trước đó trong việc gán nhãn và phân đoạn các dữ liệu dạng chuỗi mà tiêu
biểu là vấn đề ‘label bias.
a Khái niệm CRF
Kí hiệu X là biến ngẫu nhiên nhận giá trị là chuỗi dữ liệu cần phải gán nhãn và Y là
biến ngẫu nhiên nhận giá trị là chuỗi nhãn tương ứng. Mỗi thành phần Yi của Y là một
biến ngẫu nhiên nhận gía trị trong tập hữu hạn các trạng thái S. Trong bài toán gán nhãn
từ loại, X có thể nhận giá trị là các câu trong ngôn ngữ tự nhiên (gồm các từ), Y là một
chuỗi ngẫu nhiên các nhãn tương ứng với các từ tạo thành câu này và mỗi một thành
phần Yi của Y có miền giá trị là tập tất cả các nhãn từ loại có thể (danh từ, động từ, tính
từ, ).
Cho một đồ thị vô hướng không có chu trình G = (V, E), ở đây V là tập các đỉnh
của đồ thị và E là tập các cạnh vô hướng nối các đỉnh đồ thị. Các đỉnh V biểu diễn các
thành phần của biến ngẫu nhiên Y sao cho tồn tại ánh xạ một- một giữa một đỉnh và một
thành phần Yv của Y. Ta nói (Y|X) là một trường ngẫu nhiên điều kiện (Conditional
Random Field) khi với điều kiện X, các biến ngẫu nhiên Yv tuân theo tính chất Markov
đối với đồ thị G:
Ở đây, N(v) là tập tất cả các đỉnh kề với v. Như vậy, một CRF là một trường ngẫu
nhiên phụ thuộc toàn cục vào X. Trong các bài toán xử lý dữ liệu dạng chuỗi, G đơn giản
chỉ là dạng chuỗi G = (V={1,2,…m}, E={(i,i+1)}).
Kí hiệu X=(X
1
, X

k
.
Có hai loại thuộc tính là thuộc tính chuyển (kí hiệu là t) và thuộc tính trạng thái (kí
hiệu là s) tùy thuộc vào A là đồ thị con gồm một đỉnh hay một cạnh của G. Thay các hàm
tiềm năng vào công thức và thêm vào đó một thừa sổ chuẩn hóa Z(x) để đảm bảo tổng
xác suất của tất cả các chuỗi nhãn tương ứng với một chuỗi dữ liệu quan sát bằng 1, ta
được:
Ở đây, x, y là chuỗi dữ liệu quan sát và chuỗi trạng thái tương ứng; t
k
là thuộc tính
của toàn bộ chuỗi quan sát và các trạng thái tại ví trí i-1, i trong chuỗi trạng thái;s
k
là
thuộc tính của toàn bộ chuỗi quan sát và trạng thái tại ví trí i trong chuỗi trạng thái.
Thừa số chuẩn hóa Z(x) được tính như sau:
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 17
Đồ án môn Nguyên Lý Chương Trình Dịch

h. Thuật toán gán nhãn cho dữ liệu dạng chuỗi.
Tại mỗi vị trí i trong chuỗi dữ liệu quan sát, ta định nghĩa một ma trận chuyển|S|*|
S| như sau:
Ở đây Mi(y’, y, x) là xác suất chuyển từ trạng thái y’ sang trạng thái y với chuỗidữ
liệu quan sát là x. Chuỗi trạng thái y* mô tả tốt nhất cho chuỗi dữ liệu quan sát x
lànghiệm của phương trình: y* = argmax{p(y|x)}
Chuỗi y* được xác định bằng thuật toán Viterbi cải tiến. Định nghĩalà xác suất của
“chuỗi trạng thái độ dài i kết thúc bởi trạng thái y và có xác suất lớn nhất”, biết chuỗi
quan sát là x.
Giả sử biết tất cả với mọi y
k
thuộc tập trạng thái S của mô hình, cần xácđịnh . Ta

likelihood. Có nhiều phương pháp tìm cực đại của hàm log-likelihoodnhư các phương
pháp lặp (IIS, GIS), các phương pháp tối ưu số (phương pháp dựa trênvector gradient như
phương pháp gradient liên hợp, quasi-Newton …) và L-BFGs cóthể phục vụ cho ước
lượng tham số mô hình. Trong các phương pháp tìm cực trị hàmlog-likelihood này,
phương pháp L-BFGs được đánh giá là vượt trội và có tốc độ hộitụ nhanh nhất.
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 19
Đồ án môn Nguyên Lý Chương Trình Dịch

Tài liệu tham khảo
[1] Nguyễn Quang Châu- Phan Thị Tươi- Cao Hoàng Trụ, (2006),“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”, Tạp chí phát triển KH&CN,
tập 9(số 2).
[2] Nguyễn Thị Minh Huyền - Vũ Xuân Lương - Lê Hồng Phương, (2003), “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”, Kỷ yếu Hội thảo
ICT.rda’03.
HVTH: Phan Thị Ngọc Tuyết Vân - 14871114 Trang 20