TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
─────── * ───────
BÀI TẬP LỚN MÔN :
XỬ LÝ NGÔN NGỮ TỰ NHIÊN
ĐỀ TÀI :
PHÂN TÍCH CÚ PHÁP THỐNG KÊ

Gv hướng dẫn:
PGS.TS Lê Thanh Hương
Nhóm 14 : MSSV
Đỗ Văn Dương 20080546
Hoàng Đức Thọ 20082559
Trần Xuân Trường 20082854
Hoàng Thanh Tùng 20082997
Hà Nội, tháng 5 năm 2012
MỤC LỤC
I.GIỚI THIỆU
Phân tích cú pháp là một vấn đề cơ bản và quan trọng trong xử lý ngôn
ngữ tự nhiên. Với một công cụ phân tích cú pháp tốt, chúng ta có thể tích hợp
vào nhiều ứng dụng trong xử lý ngôn ngữ tự nhiên như dịch máy, tóm tắt văn
bản, các hệ thống hỏi đáp, … để tăng tính chính xác của các ứng dụng đó.
Mục tiêu của phân tích cú pháp là ngôn ngữ tự nhiên là cho một câu đầu
vào, và đầu ra trả về một đại diện cú pháp tương ứng có khả năng giải thích ngữ
nghĩa của câu. Ví dụ, đầu vào, là câu sau:
I buy cars with tires.
Đầu ra, trả ra một cây cú pháp có định dạng:
Trong đó các nhãn trung gian ( không phải nút lá và nút gốc) là các dạng
của từ loại ( vd: PP: giới từ, VP: động từ…).
Phân tích cú pháp đúng đắn là một nhiệm vụ khó khăn bởi vì ngữ nghĩa
của từ - từ quan điểm của bộ phân tích cú pháp – thay đổi trong ngữ cảnh của

để tạo một độ lệch
mới mới d’={a1,a2….a
n+1
). Chức năng của các hàm được thiết kế sao cho bất cứ
cây cú pháp T nào hoàn chỉnh cũng có đúng một sai số.
Các procedures ở đây là TAG, CHUNK, BUILD và CHECK, và được áp
dụng trong ba giai đoạn từ trái sang phải trên câu đầu vào
Giai đoạn đầu tiên sử dụng TAG, giai đoạn 2 sử dụng CHUNK, giai đoạn
3 sử dụng BUILD và CHECK.
Chức năng của các hàm được tổng hợp trong bảng dưới đây:
Các phần dưới đây lấy ví dụ là câu: I saw the man with the telescope
1.1. First Pass:
Đầu tiên lấy câu đầu vào, sử dụng TAG để gán cho mỗi từ một nhãn từ
loại. Kết quả của TAG cho mỗi từ như dưới đây:
Giai đoạn này giống như bộ gán nhãn trong bài giảng của
(Weishedel,1993) nhưng tích hợp hàm tìm kiếm của bộ phân tích, do đó bộ
phân tích không cần không cần thực hiện việc gán nhãn cho một chuỗi thẻ từ
loại đơn
1.2. Second Pass:
Giai đoạn 2 lấy đầu ra của giai đoạn 1, sử dụng CHUNK để xác định các
cụm từ nguyên tố của câu. Đi từ trái, CHUNK gán nhãn mỗi cặp (word, POS
tag) một nhãn “chunk”, có thể là Start X, Joint X hoặc Other, trong đó X là một
nhãn phần tử nguyên tố, kết quả của giai đoạn này như sau:
1.3. Third Pass:
Giai đoạn này là kết hợp luân phiên của BUILD và CHECK, ghép hoàn
toàn các nhãn nguyên tố lại. BUILD luôn xử lý cây bên trái nhất mà không có
Start X hoặc Join X, hình dưới là kết quả sau khi áp dụng BUILD được Join VP,
sau khi BUILD, bộ điều khiển chuyển qua CHECK, để kết luận xem kết quả có
được sử dụng:
Hình dưới đây là quá trình đi từ bên phải

f = từ (race), từ trước (to)
c = VP
Mục tiêu : Ước lượng xác suất p.
Chọn p có maximum entropy tùy thuộc vào ràng buộc đã biết trước:
Trong đó :
A: là tập các lớp biết trước .
B: là tập ngữ cảnh .
b. Các đặc trưng :
Một đặc trưng là một ánh xạ được dùng để mô tả đặc trưng của thông tin
đã biết.
A: Tập các lớp có thể có (ví dụ các tag trong POS tagging)
B: Không gian ngữ cảnh (ví dụ: các từ kế cận
Ví dụ:
c. Một số kí hiệu:
- Tập huấn luyện: S
)(
~
xp
- Xác suất được quan sát của x trong tập S:
- Mô hình xác suất p của x: P(x)
- Đặc trưng thứ j: f
j.
∑
∈
=
ε
x
jjp
xfxpfE )()(
~

2
, b
2
), …, (a
N
, b
N
)}
Trong đó: a
1
, a
2
, …, a
N
: tập các lớp biết trước.
b
1
, b
2
, …, b
N
: tập ngữ cảnh được phân lớp đúng .
+ Templates (Tập khuôn mẫu)
- Là những điểm cần chú trọng để tạo ra các đặc trưng.
- Template do người dùng định nghĩa.
- Một số template trong bài tách câu:
+ GIS/IIS Algorithm: Giải thuật ước lượng tham số là giải thuật tính trọng số
cho tập fj
+ Thuật toán GIS:
-

xp
1
)(
)(
)(
απ
Khi :
C
j
p
jp
n
j
n
j
fE
fE
n
1
~
)()1(
][
)(
λλ
=
+
Cập nhật:
Đặc điểm của GIS:
- L(p
(n+1)

Tốc độ của hàm tìm kiếm:
IV.KẾT LUẬN
- Mô hình maximum entropy tương đối hiệu quả trong bài toán phân loại
cú pháp thống kê.
- Phương pháp phân tích cho kết quả tốt
- Thời gian trả kết quả tương đối nhanh
- Có thể dễ diễn giải với người dùng
- Hướng phát triển: ứng dụng cho ngôn ngữ Tiếng Việt
V. Tài liệu tham khảo
1. />sentences
2. />3. Giáo trình “ Xử lý ngôn ngữ tự nhiên” – Lê Thanh Hương.
4. Micheal Collins. 2003. Head-Driven Statisticcal Models for Natural
Language Parsing. MIT Artificial Intelligence Laboratory.
5. Learning to Parse Natural Language with Maximum Entropy Models. Dept,
of Computer and Information Science University of Pennsylvania 200 South
33rd Street Philadelphia, PA 19104-6389.
6. Eugene Charniak. 1997. Statistical parsing with a context-free grammar and
word statistics. Proceedings of the Fourteenth National Conference on Artificial
Intelligence, AAAI Press/MIT Press, Menlo Park.