[拼音]：wenfa tuiduan

[外文]：grammaticalinference

根據(jù)給定的有限樣本集推斷產(chǎn)生該樣本集所屬語言類的文法規(guī)則的學(xué)習(xí)算法。它是句法模式識別（見結(jié)構(gòu)模式識別）的重要組成部分。通過文法推斷可以得到一組重寫規(guī)則（見短語結(jié)構(gòu)文法），它們除了能描述給定的有限樣本集外，還能描述那些雖不在給定樣本集內(nèi)但卻與給定樣本集在某種意義上有同樣性質(zhì)(屬于同一類)的模式，從而可以用這一組重寫規(guī)則對輸入模式進(jìn)行句法分析以達(dá)到識別的目的。文法推斷過程就是對模式類進(jìn)行描述的過程，它的正確性在很大程度上決定于所給樣本集的完備性和人們對模式性質(zhì)了解的程度，文法推斷算法至今仍然是句法模式識別中的一個(gè)重要研究課題。

文法推斷課題的一般性質(zhì)是：

（1）給定某個(gè)文法G所產(chǎn)生的語言L(G)的一個(gè)有限子集S⁺(叫正樣本集)和不屬于這個(gè)語言的集合的一個(gè)有限子集S ^–(叫負(fù)樣本集)，須假定S⁺是結(jié)構(gòu)完整的，即描述L(G)的每一條重寫規(guī)則在描述S ⁺中的樣本時(shí)至少使用一次。

（2）推斷得到的文法G_a應(yīng)滿足S⁺??L(G_a)和。在理想情況下,L(G_a)=L(G)。在實(shí)際問題中,由于所提供樣本的局限性,S⁺往往不是結(jié)構(gòu)完整的，推斷得到的文法G_a只是G 的一種近似。對于同樣的有限樣本集，不同的推斷算法可以得到不同的G_a，因此需要定義一個(gè)所推斷出的文法對于給定樣本集的優(yōu)度度量，從而能在某種意義上得到一個(gè)滿意的結(jié)果。

文法推斷算法有窮舉文法推斷算法和歸納文法推斷算法兩種形式。

（1）窮舉文法推斷算法：在一個(gè)文法類中進(jìn)行搜索，以求得與所給樣本集和學(xué)習(xí)系統(tǒng)（教師）所提供的其他附加信息一致的文法。為了提高搜索的效率可以利用覆蓋這個(gè)重要概念：如果某個(gè)文法G₁不產(chǎn)生S⁺中所有的語句，在窮舉中可以刪去被G₁所覆蓋的所有文法；而如果文法G₁產(chǎn)生S^–中某些句子，則在窮舉中可刪去所有覆蓋G₁的文法。

（2）歸納文法推斷算法：從正樣本S⁺中求得語言L的遞歸結(jié)構(gòu),從而使一個(gè)恰好產(chǎn)生給定正樣本的非遞歸性文法成為一個(gè)能夠產(chǎn)生任意多語句的遞歸性文法。以規(guī)范微商文法為基礎(chǔ)的推斷算法和基于k尾的文法是文法推斷算法的兩個(gè)例子。

以規(guī)范微商文法為基礎(chǔ)的推斷算法

首先用形式微商概念求出一個(gè)只產(chǎn)生學(xué)習(xí)樣本集（語句集合）的規(guī)范文法。語句集合A對于終止符a∈Σ的形式微商是D_aA={x|ax∈A}。A對于空符號鏈λ（即符號數(shù)為0的鏈）的微商D_λA＝A。A對于某個(gè)子句a₁a₂的形式微商是 D_??1??2A＝D_??2(D_??1A)。類似地，D_??1??2…??nA＝D_??n(D_??n-1(…(D_??1A…)))。對應(yīng)正樣本集S ⁺的規(guī)范微商有限狀態(tài)文法G_CD＝(N，Σ，P，S)按下列方法求得：

（1）∑是S ⁺中所有語句中包含的所有互異的終止符集合。

（2）N是S ⁺對于∑的不為空的形式微商集合,N＝{u₁,…,u_r},其中u₁=D_λS ⁺。

（3）S＝u₁。

（4）按下列條件得到P中的重寫規(guī)則:(i)u_i→au_j在P中的充分必要條件是D_??u_i=u_j;(ii)u_i→a在P中的充分必要條件是λ∈D_??u_i。例如S ⁺＝{01,1001}的規(guī)范微商文法G_CD＝(N，∑，P，s)，其中∑＝{0,1}；N＝{u₁,u₂,u₃,u₄}(u₁＝D_λS ⁺＝{01,1001}，u₂＝D₀u₁＝{1},u₃＝D₁u₁＝{001},u₄＝D₀u₃＝{01},此外D₀u₄＝{1}＝u₂);S＝u₁；P:u₁─→0u₂,u₂─→1，u₁─→1u₃，u₃─→0u₄，u₄─→0u₂。在求得G_CD的基礎(chǔ)上可以得到相應(yīng)的遞歸性文法G＝(N′，∑，P′，s′)。這時(shí)把G_CD的非終止符集劃分為若干互不相交的子集，例如N₁={u₁,u₂},N₂＝{u₃,u₄},則N′＝{N₁,N₂}。為了求P′,只要把原來P 中的非終止符按它屬于哪一個(gè)劃分子集而改為N′中的相應(yīng)符號,因此P′:N₁─→0N₁,N₁─→1,N₁─→1N₂，N₂─→0N₂，N₂─→0N₁,此外s′＝N₁，∑＝{0,1}。顯然G產(chǎn)生的語言除了 S ⁺外還有無限多的語句。G_CD 中的非終止符集可以用有限的不同方法劃分為互不相交的子集，因此相應(yīng)地有有限個(gè)遞歸性文法，其中至少有一個(gè)文法是推斷問題的解。

基于k尾的文法

語言集合s對于終止符構(gòu)成的子句_z的k尾微商是

例如，對于語句集合S⁺＝{01,100,111,0010}而言，

設(shè)u_i和u_i是規(guī)范微商有限狀態(tài)文法G_CD 中兩個(gè)互異的非終止?fàn)顟B(tài),u_i和u_j分別對應(yīng)于微商D_xiS ⁺ 和D_xjS ⁺，其中x_i，x_j∈∑ ^*。則u_i和u_j為k尾等價(jià)狀態(tài)的充分必要條件是

g(x_i，S⁺,k)＝g(x_j，S⁺,k)

把規(guī)范微商文法中等價(jià)的狀態(tài)合并，可得到從G_CD導(dǎo)出的可數(shù)個(gè)遞歸性文法，其中包含至少一個(gè)文法可作為推斷問題的解。

對于正則文法，已研究出以規(guī)范微商文法為基礎(chǔ)的推斷算法和基于 k尾的文法推斷算法，但對于上下文無關(guān)文法的推斷則尚無普遍適用的算法，只是對某些特殊限制的上下文無關(guān)文法有了一些啟發(fā)式的算法。例如應(yīng)用結(jié)構(gòu)信息序列推斷算子優(yōu)先文法以及k齊次、k互異文法和樞軸文法推斷，圖形描述文法的啟發(fā)式推斷等。在隨機(jī)文法的推斷方面，曾經(jīng)提出一種直接綜合隨機(jī)有限狀態(tài)自動(dòng)機(jī)算法。其中狀態(tài)轉(zhuǎn)移概率可以從隨機(jī)語句集合中相應(yīng)的概率信息中導(dǎo)出。

此外，在人機(jī)對話式的文法推斷系統(tǒng)結(jié)構(gòu)、正則樹文法、網(wǎng)狀文法等推斷方法方面都已經(jīng)取得了一定的成果。

參考書目

1. K.S.Fu and　P.H.Swain，On Synthatic Pattern Recognition，In Software　Engineering，Vol.2, Academic Press, New York,1971.

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：文法推斷

版權(quán)聲明：本文采用知識共享 署名4.0國際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《文法推斷》

文章鏈接：http://www.kaputelugumatrimony.com/13592.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識整合。如若侵權(quán)請通過投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。