CƠ SỞ Lý TH UYẾT PHâN TíCH Cú PHáP THEO PHƯƠNG PHáP THỐNG Kê

1.Lý thuyết xác suất

1.1. Xác suất

Xác suất của một biến cố (Probability of an event) : Độ đo khả năng xuất hiện của một biến cố.

Hàm xác suất (Probability function):

Ω là không gian các sự kiện rời rạc và P là xác suất phân bố trên Ω thoả mãn tính chất:

0 £ P (e_i) £ 1, "e_i Î Ω

å_i=1..n P(e_i) =1

Xác suất có điều kiện: xác suất của biến cố A được tính với điều kiện biến cố B đã xảy ra được gọi là xác suất có điều kiện của A.

P (A|B) = P (A ù B) / P (B)

Trong đó xác suất P (A ù B) là xác suất khi 2 sự kiện A và B xảy ra đồng thời.

Công thức Bayes cho xác suất có điều kiện:

P (A | B) = P (B | A) * P (A) / P (B)

hay P (A | B) * P (B) = P (B | A) * P (A)

Hai biến cố được gọi là độc lập nhau khi sự xuất hiện của biến cố này không gây ảnh hưởng đến khả năng xuất hiện của biến cố kia.

Hai biến cố A, B độc lập nhau Û P (A|B) = P (A)

và P(A & B) = P(A) * P(B)

1.2. Xác suất và ngôn ngữ

Lý thuyết xác suất được ứng dụng nhiều trong xử lý ngôn ngữ tự nhiên, ví dụ trong ứng dụng Part_Of_Speech Tagging, cho một câu có các từ nhập nhằng về từ loại, câu hỏi là từ loại nào thích hợp dùng cho mỗi từ ?

Ví dụ: Gọi biến ngẫu nhiên mô tả từ loại C Î (N,V)

Gọi w là biến ngẫu nhiên mô tả 1 từ cụ thể.

Ta có: P (C=N| w=flies) viết tắt là P(N | flies) mô tả khả năng là danh từ ứng với từ flies đã biết. Tương tự P(V | flies) mô tả khả năng là động từ ứng với từ flies đã biết.

Trong phạm vi đề tài sẽ ứng dụng lý thuyết xác suất trong việc phân tích cú pháp. Để giải quyết sự nhập nhằng khi phân tích cú pháp của một câu trước đó chưa phân tích, ta cần dựa vào dữ liệu của những câu đã được phân tích trước đó và ước lượng xác suất cho câu cần phân tích, với dữ liệu ban đầu càng lớn thì khả năng ước lượng càng chính xác [17]

1.3. Thông số ước đoán khả năng xảy ra lớn nhất (MLE)

Cho một mô hình phân tích cú pháp thống kê với văn phạm G, khi đó cây phân tích cú pháp có khả năng xảy ra lớn nhất của một câu cần phân tích s là [11][23]

1.4. Corpus – database của ngôn ngữ

Corpus là kho dữ liệu được dùng trong quá trình xử lý ngôn ngữ tự nhiên trên máy tính.

Để quá trình xử lý ngôn ngữ tự nhiên đạt hiệu quả, thông thường người ta chuyển các corpus thành tagged corpus – corpus mà trong đó từ và các mệnh đề có đi kèm từ loại của chúng; đồng thời người ta cũng tạo các corpus thống kê số lần xuất hiện của các cặp từ loại, sự xuất hiện của các từ cũng giúp chúng ta tính được xác suất xuất hiện của từ trong các corpus hoặc các treebank - corpus mà trong đó chứa các mẫu cây phân tích cú pháp.

Việc xây dựng corpus và thống kê từ loại là một việc làm khó và đòi hỏi phải tốn rất nhiều thời gian và công sức đặc biệt cho ngôn ngữ tiếng Việt. Hiện cũng có một số corpus cho tiếng Việt nhưng cũng chỉ dừng lại ở dạng từ điển.

Một số corpus:

- Wall Street Journal.

- Brown corpus: phát triển năm 1961 của Đại học Brown, có khoảng 1triệu từ.

- LOB corpus: phát triển năm 1961, có khoảng 1 triệu từ.

- Brishtish National Corpus (BNC): phát triển năm 1965, có khoảng 110 triệu từ, trong đó 10 triệu từ xuất phát từ ngôn ngữ nói và còn lại là ngôn ngữ viết.

- Penn Treebank : có khoảng 1triệu từ, đã được chèn từ loại ngay sau vị trí các từ trong câu.

Và một số corpus khác.

1.5. Penn treebank

Treebank là tập các mẫu cây phân tích cú pháp và các công cụ học. Hiện nay đã có rất nhiều loại treebanks khác nhau phục vụ cho nhiều lĩnh nhiều vực khác nhau như kinh tế, xã hội, …trong phạm vi phân tích cú pháp ngôn ngữ, chúng ta chỉ quan tâm đến Penn treebank vì Penn treebank được biết đến nhiều nhất vì số lượng và tính sẵn sàng của nó.

Ví dụ về cấu trúc một số cây trong Penn Treebank:

((S (INTJ (UH No) (, ,)) (NP (PRP it)) (VP (VBD was) (RB n't) (NP (NNP Black) (NNP Monday) (. .)))))

((S (NP (NP (DT The) (NNP Dow) (POS 's)) (NN decline)) (VP (VBD was) (ADJP (JJ second) (PP (IN in) (NP (NN point) (NNS terms))) (PP (ADVP (RB only)) (TO to) (NP (NP (DT the) (JJ 508-point) (NNP Black) (NNP Monday) (NN crash)) (SBAR (WHNP (WDT that)) (S (VP (VBD occurred) (NP (NNP Oct.) (CD 19) (, ,) (CD 1987) (. .)))))))))))

((S (NP (NP (DT The) (CD 49) (NN stock) (NN specialist) (NNS firms)) (PP (IN on) (NP (DT the) (NNP Big) (NNP Board) (NN floor) (: --)))) (NP (NP (DT the) (NNS buyers) (CC and) (NNS sellers)) (PP (IN of) (NP (NP (JJ last) (NN resort)) (SBAR (WHNP (WP who)) (S (VP (VBD were) (VP (VBN criticized) (PP (IN after) (NP (DT the) (CD 1987) (NN crash) (: --)))))))))) (ADVP (RB once) (RB again)) (VP (MD could) (RB n't) (VP (VB handle) (NP (DT the) (NN selling) (NN pressure) (. .))))))

((S (S (NP (JJ Big) (NN investment) (NNS banks)) (VP (VBD refused) (S (VP (TO to) (VP (VB step) (PRT (RP up)) (PP (TO to) (NP (DT the) (NN plate))) (S (VP (TO to) (VP (VB support) (NP (DT the) (JJ beleaguered) (NN floor) (NNS traders)) (PP (IN by) (S (VP (VBG buying) (NP (NP (JJ big) (NNS blocks)) (PP (IN of) (NP (NN stock) (, ,))))))))))))))) (NP (NNS traders)) (VP (VBP say) (. .))))

…

Sau đây trình bày một số ký hiệu trong Penn Treebank [9],[11]

STT	Ký hiệu tag	ý nghĩa	Ví dụ cơ bản
	CC	Liên từ	and, neither, nor, or, but
	DD	Số	2, 2.5, 1000
	DT	Mạo từ	a, an, the
	EX		There
	FW	Từ tiếng nước khác	Từ tiếng Pháp, Đức
	IN	Giới từ	in, on, of
	JJ	Tính từ	good, beautiful
	JJR	Tính từ so sánh hơn	higher, more, lower
	JJS	Tính từ so sánh nhất	most, largest, least
	LS	Số thứ tự	first, second, third
	MD	Động từ đặc biệt- modal verb	will, can, should
	NN	Danh từ số ít	book, paper, salary
	NNS	Danh từ số nhiều	books, months, benefits
	NNP	Danh từ riêng số ít	John, Mary, Mr., Inc.
	NNPS	Danh từ riêng số nhiều	Japanese, Labs, Fords
	PDT	Tiền định tố	such, aasll, half
	POS	Sở hữu cách	’s
	PRP	Đại từ nhân xưng	he, she, they
	PRP$	Đại từ sở hữu	his, their, yours
	RB	Phó từ, trạng từ	too, now, seriously
	RBR	Phó từ, trạng từ so sánh hơn	more, earlier, less
	RBS	Phó từ, trạng từ so sánh nhất	most, hardest
	RP	Tiền tố, hậu tố	off, up, back
	SYM	Biểu tượng
	TO		To
	UH	Cảm thán từ	ah, oh, yes
	VB	Động từ nguyên mẫu	say, think, resign
	VBD	Động từ chia thì quá khứ	said, thought, resigned
	VBG	Động danh từ	narrowing, controlling
	VBN	Quá khứ phân từ
	VBP	Động từ số nhiều	are, enjoy, take
	VBZ	Động từ số ít	is, enjoys, takes
	WDT	Wh-determiner	whatever, which, that
	WP	Đại từ quan hệ	what, who, whom
	WP$	Đại từ quan hệ sở hữu	Whose
	WRB	Phó từ/ trạng từ quan hệ	When, where, how
	#	Ký hiệu rào
	$	Ký hiệu dollar
	.	Dấu chấm hết câu
	,	Dấu phẩy
	:	Dấu hai chấm
	(	Dấu ngoặc trái
	)	Dấu ngoặc phải
	“	Dấu nháy kép
	`	Dấu nháy đơn trái
	”	Dấu nháy kép trái
	’	Dấu nháy đơn phải
	“	Dấu nháy kép phải

Table 4.1:Ttập ký hiệu tag của Penn Treebank corpus

STT	Ký hiệu tag	ý nghĩa	Ví dụ cơ bản
	S	Bắt đầu một mệnh đề nhưng không bắt đầu từ các liên từ chỉ sự phụ thuộc hay đại từ quan hệ
	SBAR	Mệnh đề bắt đầu từ các liên từ chỉ sự phụ thuộc
	SBARQ	Câu hỏi trực tiếp bắt đầu bằng đại từ quan hệ
	SINV	Câu đảo ngữ nhằm mục đích nhấn mạnh và không phải là câu hỏi	(SINV (ADVP-TMP Never) had (NP-SBJ I) (VP seen (NP such a place)))
	SQ	Câu hỏi yes-no
	NP	Ngữ danh từ
	VP	Ngữ động từ
	ADJP	Ngữ tính từ
	PP	Ngữ giới từ
	ADVP	Ngữ phó từ
	CONJP	Ngữ liên từ	(S (NP-SBJ Willie (CONJP as well as) Casey) (VP saw (NP the ball)
	FRAG	Đoạn
	INTJ	Thán từ
	LST	Dãy số
	NAC	Dùng để giới hạn tầm vực của các bổ ngữ trong ngữ danh từ	(NP-SBJ (NAC (NNP Huntsville) (, ,) (NNP Ala.) (, ,)) (NNP Boeing))
	NX	Dấu mở ngoặc đơn
	PRT	Tiểu từ chỉ chung mạo từ, phó từ, giới từ, tiền tố, hậu tố
	QP	Ngữ liên quan đến số lượng dùng trong ngữ danh từ	(QP (CD 5.8) (CD million))
	RRC	Mệnh đề quan hệ rút gọn
	UCP	Ngữ kết hợp	(UCP (NN computer) (CC and) (JJ local))
	WHADJP	Ngữ tính từ kết hợp với đại từ quan hệ	(WHADJP (RB just) (WRB how) (JJ strong) (CC or) (JJ weark))
	WHADVP	Ngữ trạng từ kết hợp với đại từ quan hệ
	WHNP	Ngữ danh từ kết hợp với đại từ quan hệ	(WHNP (WP$ whose) (NNS shareholders))
	WHPP	Ngữ giới từ kết hợp với đại từ quan hệ	(WHPP (IN in) (WHNP (WDT which)
	X	Không xác định được từ loại

Bảng 4.2: Tập ký hiệu tag của Penn Treebank corpus bổ sung

4.1.6. Văn phạm phi ngữ cảnh có xác suất (PCFG)

Văn phạm phi ngữ cảnh có xác suất là một văn phạm phi ngữ cảnh có gắn xác suất vào trong các luật sinh [17][25].

Một văn phạm phi ngữ cảnh có xác suất G bao gồm :

• Một tập các ký hiệu kết thúc: {w^k}, k = 1,…,V
• Một tập các ký hiệu không kết thúc : {Nⁱ}, i = 1,…,N
• Một ký hiệu bắt đầu : N¹
• Một tập các luật sinh { Nⁱ ®z^j}, trong đó z^j là chuỗi các ký hiệu kết thúc và không kết thúc.

Một tập các xác suất tương ứng trên các luật như:

trong đó xác suất P(Nⁱ ®z^j) được hiểu là P(Nⁱ ®z^j | Nⁱ)

PCFG models of tree structures [20][23]

Trong PCFG xác suất của cây t được định nghĩa :

Trong đó C_t(A-->a) là số lần luật A-->a dùng để dẫn xuất ra t.

Để ước lượng PCFG từ một treebank cho trước, ta giả sử tập huấn luyện của treebank gồm n cây t₁, t₂, … t_{n .} Mỗi cây t_i gồm r_i luật a_ij -->b_ij , 1£ j £ r_i. Khi đó hàm khả năng xảy ra của corpus được viết như sau:

Trong đó C_t (a -->b) là số lần luật (a -->b) xuất hiện trong tập huấn luyện dùng để dẫn xuất ra t. Và tham số ước lượng khả năng xảy ra lớn nhất được ước lượng bởi:

2. Một số giải thuật phân tích cú pháp bằng xác suất

2.1. Giải thuật CKY(Cocke,Kasami, Younger) mở rộng, CKY+ [26]

Giải thuật CKY₊ là một giải thuật phân tích cú pháp theo sơ đồ từ dưới lên, sử dụng văn phạm nhập là văn phạm phi ngữ cảnh G trong dạng chuẩn Chomsky (CNF). Trong CNF, mỗi luật có một trong hai dạng:

A --> B C , A, B, C Î V

A --> a , A Î V và a Î T

Phương pháp:

Thêm vào chart tất cả các luật sinh dạng (k --> w_i) Î G và xác suất tương ứng của luật sinh đó, trong đó w_i là từ loại tương ứng từ thứ i trong câu.

Với mỗi cụm từ có chiều dài l (có 2 đến n từ):

Duyệt từ trái qua phải, kết hợp các cụm từ để tạo nên cụm từ mới với chiều dài l, trong đó, nếu có nhiều luật sinh mở rộng cho cùng một thành phần (vế trái trùng nhau) thì chọn luật sinh có xác suất lớn hơn.

Nếu 1 Î chart [0,n], cho kết quả là cây phân tích cú pháp tương ứng câu w.

2.2. Giải thuật Best-First Parsing[7]

Giải thuật tìm cây phân tích có xác suất cao nhất, giải thuật này được nghiên cứu và đánh giá là một trong những giải thuật hiệu quả trong phân tích cú pháp đối với văn phạm phi ngữ cảnh có xác suất với treebank lớn [10]. Giải thuật được tóm tắt như sau [12]:

Để thêm một thành phần C vào vị trí từ p₁ đến p₂ thực hiện các bước sau:

1. Thêm C vào sơ đồ từ vị trí p₁ đến p₂.

2. Với bất kỳ cung hoạt động có dạng X ® X₁…^o C … X_n từ vị trí p₀ đến p₁; thêm cung mới X ® X… C₁ …X_o từ p₀ đến p_1.

Để thêm một cung hoạt động có dạng X® X₁ … C ^o C’…X_n vào vị trí từ p₁ đến p₂ thực hiện các bước sau:

1. Nếu C là thành phần cuối cùng (tức là cung đã hoàn thành), thêm một thành phần có dạng X vào agenda.

2. Ngược lại, nếu có 1 thành phần Y dạng C’ trong sơ đồ từ vị trí p₂ đến p₃ thì thêm 1 cung hoạt động X® X₁ …C C’^o …X_n từ vị trí p₀ đển p₃ (có thể thêm nhiều cung hoặc tạo nhiều thành phần).

2.3. Giải thuật ViterbiPCFGParser[7]

ViterbiPCFGParser là một giải thuật phân tích cú pháp từ dưới lên cho PCFG, dùng lập trình động để tìm cây phân tích đơn nhất phù hợp với câu phân tích. ViterbiPCFGParser phân tích câu bằng cách điền vào bảng các thành phần thích hợp nhất. Bảng này lưu giữ tất cả các cây diễn dịch phù hợp nhất với bất kỳ chiều dài và giá trị nào của node. Đặc biệt, bảng này có chứa entry gồm mọi chỉ số đầu, chỉ số cuối và giá trị của node, lưu giữ các cây con phù hợp nhất có chiều dài từ chỉ số đầu đến chỉ số cuối và giá trị node tương ứng.

Đầu tiên ViterbiPCFGParser điền vào các entry các thành phần có chiều dài bằng 1 (tức chỉ số cuối lớn hơn chỉ số đầu 1 đơn vị). Tiếp theo là điền các thành phần có chiều dài bằng 2 và cứ thế tiếp tục điền các thành phần có chiều dài ngày càng lớn hơn cho đến khi toàn bộ bảng được điền xong. Cuối cùng, giải thuật trả về bảng các entry cho thành phần bao trùm câu phân tích.

Mã giả của giải thuật được trình bày như sau:

• Create an empty most likely constituent table, MLC.
• For width in 1...len(text):
  • For start in 1...len(text)-width:
    • For prod in grammar.productions:
      • For each sequence of subtrees [t[1], t[2], ..., t[n]] in MLC, where t[i].node = prod.rhs[i], and the sequence covers [start:start+width]:
        • old_p = MLC[start, start+width, prod.lhs]
        • new_p = P(t[1])*P(t[1])*...*P(t[n])*P(prod)
        • if new_p > old_p:
          • new_tree = Tree(prod.lhs, t[1], t[2], ..., t[n])
          • MLC[start, start+width, prod.lhs] = new_tree
• Return MLC[0, len(text), start_symbol]

2.4. Giải thuật stack decoding[11]

ý tưởng của giải thuật được tóm tắt như sau:

- Giải thuật được mô tả thông qua việc dùng một hàng đợi lưu trữ các phần tử được sắp thứ tự để thực hiện push, pop các phần tử có thứ hạng cao nhất. Cấu trúc của hàng đợi được dùng là dữ liệu dạng heap.

- Bước khởi đầu của quá trình phân tích: Bắt đầu bằng 1 hàng đợi có chứa 1 phần tử.

- Bước lặp :

+ Lấy phần tử có xác suất cao nhất từ đầu của hàng đợi.

+ Mở rộng hàng đợi bằng cách tăng từ n bước dẫn xuất thành n+1 bước dẫn xuất. Kết quả trả về thứ tự xác suất được sắp xếp trên hàng đợi.

+ Quá trình lặp kết thúc khi có 1 cây dẫn xuất hoàn thành trên đỉnh của hàng đợi.

- Nếu hàng đợi là vô hạn thì giải thuật này được đảm bảo là tìm được cây phân tích có xác suất cao nhất bởi vì những dẫn xuất có xác suất cao hơn luôn được mở rộng trước những dẫn xuất có xác suất thấp.

Chính vì thế giải thuật này được đánh giá là complete và optimal (đảm bảo tìm ra 1 lời giải và lời giải đó là tốt nhất nếu có nhiều lời giải).

2.5. Giải thuật phân tích tìm kiếm A*[8]

Mã giả giải thuật được trình bày như sau:

parse(sentence, goal, estimate)

initialize(sentence, goal)

while the agenda is non-empty

e = nextEdge(agenda, estimate)

finishEdge(e)

nextEdge(agenda, estimate)

priority of e is score(e)+estimate(e)

return the e in agenda with best priority

initialize(sentence, goal)

create a new chart and new agenda

for each word w:[start,end] in the sentence

add w:[start,end] to the agenda

exploreTraversal(Traversal t)

e = result(t)

if notYetDiscovered(e)

add e to the agenda

relaxEdge(e, t)

relaxEdge(Edge e, Traversal t)

newScore = combineScores(t)

if (newScore is better than score(e))

score(e) = score(t)

bestTraversal(e) = t

finishEdge(Edge e)

add e to the chart

for all adjacent edges f in the chart

for all labels x

let t = combine(e, f )

if t is valid

exploreTraversal(t)