Đồ án tốt nghiệp
Đào Văn Trung – 100009
3
Tuy nhiên, một văn bản thật sự (một bài báo khoa học chẳng hạn) có thể có
đến hàng nghìn câu, và ta không phải có một mà hàng triệu văn bản. Web là một
nguồn dữ liệu văn bản khổng lồ, và cùng với các thƣ viện điện tử − khi trong một
tƣơng gần các sách báo xƣa nay và các nguồn âm thanh đƣợc chuyển hết vào máy
tính (chẳng hạn bằng các chƣơng trình nhận dạng chữ, thu nhập âm thanh, hoặc gõ
thẳng vào máy) − sẽ sớm chứa hầu nhƣ toàn bộ kiến thức của nhân loại. Vấn đề là
làm sao “xử lý” (chuyển đổi) đƣợc khối dữ liệu văn bản và tiếng nói khổng lồ này
qua dạng khác để mỗi ngƣời có đƣợc thông tin và tri thức cần thiết từ chúng.
II. Cơ sở khoa học
II.1 Một số khái niệm cơ bản
a. Ngôn ngữ tự nhiên
Ngôn ngữ là hệ thống để giao thiệp hay suy luận dùng một cách biểu diễn
phép ẩn dụ và một loại ngữ pháp theo logic, mỗi cái đó bao hàm một tiêu chuẩn
hay sự thật thuộc lịch sử và siêu việt. Nhiều ngôn ngữ sử dụng điệu bộ, âm thanh, lý
hiệu, hay chữ viết, và cố gắng truyền khái niệm, ý nghĩa, và ý nghĩ, nhƣng mà nhiều
khi những khía cạnh này nằm sát quá, cho nên khó phân biệt nó.
b. Xử lý ngôn ngữ tự nhiên
Xử lý ngôn ngữ tự nhiên (natural language processing - NLP) là một nhánh
của trí tuệ nhân tạo tập trung vào các ứng dụng trên ngôn ngữ của con ngƣời.Trong
trí tuệ nhân tạo thì xử lý ngôn ngữ tự nhiên là một trong những phần khó nhất vì nó
liên quan đến việc phải hiểu ý nghĩa ngôn ngữ - công cụ hoàn hảo nhất của tƣ duy
và giao tiếp.
c. Trí tuệ nhân tạo
Trí tuệ nhân tạo hay trí thông minh nhân tạo (tiếng Anh: artificial
intelligence hay machine intelligence, thƣờng đƣợc viết tắt là AI) là trí tuệ đƣợc
biểu diễn bởi bất cứ một hệ thống nhân tạo nào. Thuật ngữ này thƣờng dùng để nói
đến các máy tính có mục đích không nhất định và ngành khoa học nghiên cứu về
các lý thuyết và ứng dụng của trí tuệ nhân tạo.
d. Nhập nhằng
Nhập nhằng trong ngôn ngữ học là hiện tƣợng thƣờng gặp, trong giao tiếp
hàng ngày con ngƣời ít để ý đến nó bởi vì họ xử lý tốt hiện tƣợng này. Nhƣng trong
Đồ án tốt nghiệp
Đào Văn Trung – 100009
4
các ứng dụng liên quan đến xử lý ngôn ngữ tự nhiên khi phải thao tác với ý nghĩa từ
vựng mà điển hình là dịch tự động nhập nhằng trở thành vấn đề nghiêm trọng. Ví dụ
trong một câu cần dịch có xuất hiện từ “đƣờng” nhƣ trong câu “ra chợ mua cho mẹ
ít đƣờng” vấn đề nảy sinh là cần dịch từ này là road hay sugar, con ngƣời xác định
chúng khá dễ dàng căn cứ vào văn cảnh và các dấu hiệu nhận biết khác nhƣng với
máy thì không. Một số hiện tƣợng nhập nhằng: Nhập nhằng ranh giới từ, Nhập
nhằng từ đa nghĩa, Nhập nhằng từ đồng âm (đồng tự), Nhập nhằng từ loại.
II.2 Lý thuyết thông tin
a. Khái niệm
Lý thuyết thông tin nghiên cứu về: Áp dụng các công cụ toán học trong việc
lƣợng hóa data cho mục đích lƣu trữ và truyền dữ liệu. Độ đo thông tin là Entropy, là
số lƣợng bít trung bình cần thiết để cho việc lƣu trữ hay truyền dữ liệu. Đóng vai trò
quan trọng trong xử lý thông tin bằng các phƣơng pháp thống kê, đặc biệt trong NLP
b. Entropy
Entropy là một độ đo thông tin. Entropy ~ hỗn độn, mờ, trái nghĩa với order,
Đo độ không chắc chắn: Entropy thấp -> Đo độ không chắc chắn thấp ;
Entropy cao -> Đo độ không chắc chắn cao. Trong vật lý: Entropy giảm khi năng
lƣợng đƣợc sử dụng. Ký hiệu p(x) là một phân bố của một biến ngẫu nhiên X. là
không gian mẫu của X Entropy đƣợc tính nhƣ sau:
H(X) = - ∑ x p(x) log2p(x) .
Đơn vị: bits (log10: nats) .
Kí hiệu: H(X) = Hp(X) = H(p)
c. Perplexity - Cross Entropy
c. 1. Entropy liên quan thế nào đến hiểu ngôn ngữ?
Liên quan đến sự ko chính xác: một vấn đề càng có nhiều thông tin thì Entropy
càng thấp. Có nhiều mô hình -> entropy đo chất lƣợng của các mô hình?
Ví dụ: mô hình mã hóa ký tự với trung bình số bít sử dụng trên mỗi ký tự là 2.5
Đây là mô hình ngôn ngữ 0-gram, nếu đặt trong sự liên kết của các âm tiết thì chúng
ta có thể sinh đƣợc mô hình tốt hơn, chẳng hạn cho entropy 1.22 bít trên một ký tự.
c. 2. Perplexity
Entropy của một phân bố p(X) là: Hp(X)Thì giá trị 2H đƣợc gọi là perplexity
Đồ án tốt nghiệp
Đào Văn Trung – 100009
5
perplexity là số lƣợng mẫu trung bình mà một biến phải lựa chọn.Perlexity càng bé
(tức là entropy càng bé) thì mô hình càng tốt <=> số bít dùng để mã hóa thông tin
càng bé.
Ví dụ: Cho 8 con ngựa với xác suất lựa chọn nhƣ sau:
Ngựa 1: 1/2 ngựa 2: 1/4 ngựa 3: 1/8 ngựa 4: 1/16
Ngựa 5: 1/64 ngựa 2: 1/64 ngựa 3: 1/64 ngựa 4: 1/64
c.3. Entropy rate
Tính entropy của một dãy các từ trong một ngôn ngữ L
H(w1, ,wn) = - W L p(W1n)log(W1n)
Entropy rate đƣợc coi nhƣ per-word entropy. Coi một ngôn ngữ nhƣ một quá
trình ngẫu nhiên sản xuất một dãy các từ. Cần quan tâm đến một dãy vô hạn từ.
Entropy rate H(L) đƣợc định nghĩa nhƣ sau:
), ,(log), ,(
1
lim), ,(
1
lim)(
111 nn
L
n
n
n
wwpwwp
n
wwH
n
LH
c.4 . Cross Entropy
Cross entropy đƣợc sử dụng khi chúng ta không biết phân bố thật p.
Cross-entropy của phân bố m của phân bố thật p đƣợc định nghĩa:
), ,(log
1
lim), ,(log), ,(
1
lim),(
111 n
n
L
nn
n
wwm
n
wwmwwp
n
mpH
(theo lý thuyết Shannon-McMillan-Breiman)
c.5. Cross entropy để so sánh các mô hình : H(p) ≤ H(p,m)
Cross entropy H(p,m) là cận trên của entropy H(p).
Mô hình m càng chính xác thì cross entropy H(p,m) càng gần với entropy H(p).
Độ khác nhau H(p,m) và H(p) đo độ chính xác của mô hình m.
c.6. Các công thức Cross Entropy
Cross entropy giữa biến X với phân bố xác suất đúng p(x) và một phân bố m
đƣợc tính nhƣ sau:
)(log)()||()(),( xmxpmpDXHmXH
x
Chú ý: D(p||q) = ∑x p(x) log2 (p(x)/q(x))
II.3 Quy 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
Đồ án tốt nghiệp
Đào Văn Trung – 100009
6
trình đó sang chƣơng trình ở dạng ngôn ngữ đích. Chƣơng này trình bày một cách
tổng quan về cấu trúc của một trình biên dịch và mối liên hệ giữa nó với các thành
phần khác - “họ hàng” của nó - nhƣ bộ tiền xử lý, bộ tải và soạn thảo liên kết, v.v.
Cấu trúc của trình biên dịch đƣợc mô tả trong chƣơng 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.
Hình 2 : Một trình biên dịch
a. Phân tích từ vựng (Lexical Analysis)
Trong một trình biên dịch, giai đọan phân tích từ vựng sẽ đọc chƣơng trình nguồn
từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các thẻ từ (token).
Ví dụ 1.2:
Quá trình phân tích từ vựng cho câu lệnh gán position := initial + rate * 60 sẽ
tách thành các token nhƣ sau:
1. Danh biểu position
2. Ký hiệu phép gán :=
3. Danh biểu initial
4. Ký hiệu phép cộng (+)
5. Danh biểu rate
6. Ký hiệu phép nhân (*)
7. Số 60
Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua.
b. 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
Đồ án tốt nghiệp
Đào Văn Trung – 100009
7
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.
Ví dụ 1.3: Giả sử ngôn ngữ đặc tả bởi các luật sinh sau :
Stmt → id := expr
expr → expr + expr | expr * expr | id | number
Với câu nhập: position := initial + rate * 60, cây phân tích cú pháp đƣợc xây
dựng nhƣ sau :
Hình 3 :Một cây phân tích cú pháp
Cấu trúc phân cấp của một chƣơng trình thƣờng đƣợc diễn tả bởi quy luật đệ qui.
Ví dụ 1.4:
1) Danh biểu (identifier) là một biểu thức (expr).
2) Số (number) là một biểu thức.
3) Nếu expr1 và expr2 là các biểu thức thì:
expr1 + expr2
expr1 * expr2
(expr)
4) Cũng là những biểu thức. Câu lệnh (statement) cũng có thể định nghĩa đệ qui:
4.1) Nếu id1 là một danh biểu và expr2 là một biểu thức thì id1 := expr2 là
một lệnh (stmt).
4.2) Nếu expr1 là một biểu thức và stmt2 là một lệnh thì while (expr1) do
stmt2 và if (expr1) then stmt2: đều là các lệnh. Ngƣời ta dùng các qui tắc đệ qui
nhƣ trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình
Đồ án tốt nghiệp
Đào Văn Trung – 100009
8
phân tích từ vựng và phân tích cú pháp cũng tuỳ theo công việc thực hiện.
c. 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 checking) và ép chuyển đổi kiểu.
Ví dụ 1.5: Trong biểu thức position := initial + rate * 60
Các danh biểu (tên biến) đƣợc khai báo là real, 60 là số integer vì vậy trình
biên dịch đổi số nguyên 60 thành số thực 60.0
.
Hình 4: Chuyển đổi kiểu trên cây phân tích cú pháp
d. Các giai đoạn của trình biên dịch
Một trình biên dịch đƣợc chia thành các giai đoạn, mỗi giai đoạn chuyển
chƣơng trình nguồn từ một dạng biểu diễn này sang một dạng biểu diễn khác.
VÍ DỤ: Một cách phân rã điển hình trình biên dịch đƣợc trình bày trong hình
:
Hình 5: Các giai đoạn của một trình biên dịch
Việc quản lý bảng ký hiệu và xử lý lỗi đƣợc thực hiện xuyên suốt qua tất cả
Đồ án tốt nghiệp
Đào Văn Trung – 100009
9
các giai đoạn. Các giai đoạn mà chúng ta đề cập ở trên là thực hiện theo trình tự
logic của một trình biên dịch. Nhƣng trong thực tế, cài đặt các hoạt động của nhiều
hơn một giai đoạn có thể đƣợc nhóm lại với nhau. Thông thƣờng chúng đƣợc nhóm
thành hai nhóm cơ bản, gọi là: kỳ đầu (Front end) và kỳ sau (Back end).
1. Kỳ đầu (Front End)
Kỳ đầu bao gồm các giai đoạn hoặc các phần giai đoạn phụ thuộc nhiều vào
ngôn ngữ nguồn và hầu nhƣ độc lập với máy đích. Thông thƣờng, nó chứa các giai
đoạn sau: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa và Sinh mã
trung gian. Một phần của công việc tối ƣu hóa mã cũng đƣợc thực hiện ở kỳ đầu.
Front end cũng bao gồm cả việc xử lý lỗi xuất hiện trong từng giai đoạn.
2. Kỳ sau (Back End)
Kỳ sau bao gồm một số phần nào đó của trình biên dịch phụ thuộc vào máy
đích và nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn
ngữ trung gian. Trong kỳ sau, chúng ta gặp một số vấn đề tối ƣu hoá mã, phát sinh
mã đích cùng với việc xử lý lỗi và các thao tác trên bảng ký hiệu.
II.4 Một số thuật toán phân tích cú pháp
1. Topdown
Phân tích từ trên xuống, từ trái qua phải.
Khi gặp một từ (terminal) thì phân tích nút tiếp theo.
Khi không tƣơng ứng với input word thì quay lui.
2. Bottom-up
Là một dạng của shift - reduce actions.
Khi gặp vế phải của một luật thì thu gọn thành vế trái.
Khi không phân tích đƣợc tiếp thì quay lui.
3. CYK (Cocke-Younger-Kasami)
Văn phạm dạng chuẩn Chomsky (Chomsky Normal Form).
Các luật thuộc một trong 2 dạng:
A -> B C
A -> a
Ví dụ:
S -> X Y
Đồ án tốt nghiệp
Đào Văn Trung – 100009
10
X -> X A | a | b
Y -> A Y | a
A -> a
Phân tích câu “babaa” -> không sinh ra câu.
“baaa” -> sinh ra câu.
Xác định các đặc điểm sau đây:
1) Sinh ra giá trị một nút nhƣ thế nào?
A[i,j] <- ? + ?
2) Lƣu lại đƣờng đi nhƣ thế nào để sinh lại cây.
Tính nhập nhằng: một A[,] có thể có nhiều tag, mỗi tag lại đƣợc dẫn xuất
bằng nhiều cách.
3) Tại sao thuật toán CYK lại cần văn phạm dạng chuẩn Chomsky.
Phân tích câu:
“book that flight”
“book the flight through Houston”
Đồ án tốt nghiệp
Đào Văn Trung – 100009
11
Chuyển từ văn phạm CFG sang văn phạm dạng chuẩn Chomsky.
1) A -> B C D
A -> X D
X -> B C
2) Bỏ luật dạng A -> B
Với mọi B -> , sinh luật A ->
Đồ án tốt nghiệp
Đào Văn Trung – 100009
12
Thử sinh ra một văn phạm tƣơng ứng.
4. Thuật toán parsing CYK
Đặc điểm:
- Có thể chuyển mọi văn phạm dạng CFG về dạng chuẩn Chomsky.
- Searching theo kiểu Bottom-up.
- Độ phức tạp phân tích là O(n3).
- Thuật toán là một dạng của dynamic programming.
- Có thể mở rộng thuật toán CYK để phân tích văn phạm xác suất.
III. Các ứng dụng của xử lý ngôn ngữ tự nhiên
1. Nhận dạng tiếng nói (speech recognition): Từ sóng tiếng nói, nhận biết và
chuyển chúng thành dữ liệu văn bản tƣơng ứng. Giúp thao tác của con ngƣời trên
các thiết bị nhanh hơn và đơn giản hơn, chẳng hạn thay vì gõ một tài liệu nào đó
bạn đọc nó lên và trình soạn thảo sẽ tự ghi nó ra. Đây cũng là bƣớc đầu tiên cần
phải thực hiện trong ƣớc mơ thực hiện giao tiếp giữa con ngƣời với robot. Nhận
Không có nhận xét nào:
Đăng nhận xét