18/11/2021 04:27:05 PM

Lập trình

Bài 02: CƠ SỞ LÝ TH UYẾT PHÂN TÍCH CÚ PHÁP THEO PHƯƠNG PHÁP THỐNG KÊ

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

      1.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 (ei) £ 1,   "ei Î Ω

åi=1..n P(ei) =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.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.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.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.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 1.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 1.2: Tập ký hiệu tag của Penn Treebank corpus bổ sung

      1.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: {wk},  k = 1,…,V
  • Một tập các ký hiệu không kết thúc : {Ni},  i = 1,…,N
  • Một ký hiệu bắt đầu : N1
  • Một tập các luật sinh { Ni ®zj}, trong đó  zj 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(Ni ®zj) được hiểu là P(Ni ®zj | Ni)

           PCFG models of tree structures [20][23]

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

           Trong đó Ct(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 t1, t2, … tn . Mỗi cây ti gồm ri luật  aij -->bij , 1£ j  £ ri. Khi đó hàm khả năng xảy ra của corpus được viết như sau:

           Trong đó Ct (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:

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

      1.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 --> wi) Î G và xác suất tương ứng của luật sinh đó, trong đó wi 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.

      1.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ừ p1 đến p2 thực hiện các bước sau:

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

2. Với bất kỳ cung hoạt động có dạng  X ® X1…o C … Xn  từ vị trí p0 đến p1;  thêm cung mới X ® X… C1 …Xo  từ p0 đến p1.

Để thêm một cung hoạt động có  dạng  X® X1 … C o C’…Xn vào vị trí từ p1 đến p2 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í p2 đến p3 thì thêm 1 cung hoạt động  X® X1 …C C’o …Xn  từ vị trí p0 đển p3 (có thể thêm nhiều cung hoặc tạo nhiều thành phần).

      4.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]

      1.3.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).

      1.3.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)

 

» Tin mới nhất:

» Các tin khác:

Hôm nay, ngày

23/11/2024

Tuần học:

16

Sinh viên tiêu biểu

Số lượt truy cập: 9079842