文法推斷

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

文法推斷課題的一般性質是:①給定某個文法G所產生的語言L(G)的一個有限子集S+(叫正樣本集)和不屬於這個語言的集合的一個有限子集S -(叫負樣本集)，須假定S+是結構完整的，即描述L(G)的每一條重寫規則在描述S +中的樣本時至少使用一次。②推斷得到的文法Ga應滿足S+吇L(Ga)和。在理想情況下,L(Ga)=L(G)。在實際問題中，由於所提供樣本的局限性,S+往往不是結構完整的，推斷得到的文法Ga只是G 的一種近似。對於同樣的有限樣本集，不同的推斷演演算法可以得到不同的Ga，因此需要定義一個所推斷出的文法對於給定樣本集的優度度量，從而能在某種意義上得到一個滿意的結果。

文法推斷演演算法有窮舉文法推斷演演算法和歸納文法推斷演演算法兩種形式。①窮舉文法推斷演演算法：在一個文法類中進行搜索，以求得與所給樣本集和學習系統（教師）所提供的其他附加信息一致的文法。為了提高搜索的效率可以利用覆蓋這個重要概念：如果某個文法G1不產生S+中所有的語句，在窮舉中可以刪去被G1所覆蓋的所有文法；而如果文法G1產生S-中某些句子，則在窮舉中可刪去所有覆蓋G1的文法。②歸納文法推斷演演算法：從正樣本S+中求得語言L的遞歸結構，從而使一個恰好產生給定正樣本的非遞歸性文法成為一個能夠產生任意多語句的遞歸性文法。以規範微商文法為基礎的推斷演演算法和基於k尾的文法是文法推斷演演算法的兩個例子。

以規範微商文法為基礎的推斷演演算法 首先用形式微商概念求出一個只產生學習樣本集（語句集合）的規範文法。語句集合A對於終止符a∈Σ的形式微商是DaA={x|ax∈A}。A對於空符號鏈λ（即符號數為0的鏈）的微商DλA＝A。A對於某個子句a1a2的形式微商是 Dɑ1ɑ2A＝Dɑ2(Dɑ1A)。類似地，Dɑ1ɑ2…ɑnA＝Dɑn(Dɑn-1(…(Dɑ1A…)))。對應正樣本集S +的規範微商有限狀態文法GCD＝(N，Σ，P，S)按下列方法求得：①∑是S +中所有語句中包含的所有互異的終止符集合。②N是S +對於∑的不為空的形式微商集合,N＝{u1,…,ur},其中u1=DλS +。③S＝u1。④按下列條件得到P中的重寫規則:(i)ui→auj在P中的充分必要條件是Dɑui=uj;(ii)ui→a在P中的充分必要條件是λ∈Dɑui。例如S +＝{01,1001}的規範微商文法GCD＝(N，∑，P，s)，其中∑＝{0,1}；N＝{u1,u2,u3,u4}(u1＝DλS +＝{01,1001}，u2＝Du1＝{1},u3＝D1u1＝{001},u4＝Du3＝{01},此外Du4＝{1}＝u2);S＝u1；P:u1─→0u2,u2─→1，u1─→1u3，u3─→0u4，u4─→0u2。在求得GCD的基礎上可以得到相應的遞歸性文法G＝(N′，∑，P′，s′)。這時把GCD的非終止符集劃分為若干互不相交的子集，例如N1={u1,u2},N2＝{u3,u4},則N′＝{N1,N2}。為了求P′,只要把原來P 中的非終止符按它屬於哪一個劃分子集而改為N′中的相應符號，因此P′:N1─→0N1,N1─→1,N1─→1N2，N2─→0N2，N2─→0N1,此外s′＝N1，∑＝{0,1}。顯然G產生的語言除了 S +外還有無限多的語句。GCD 中的非終止符集可以用有限的不同方法劃分為互不相交的子集，因此相應地有有限個遞歸性文法，其中至少有一個文法是推斷問題的解。

基於k尾的文法 語言集合s對於終止符構成的子句z的k尾微商是

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

設ui和ui是規範微商有限狀態文法GCD 中兩個互異的非終止狀態,ui和uj分別對應於微商DxiS + 和DxjS +，其中xi，xj∈∑ *。則ui和uj為k尾等價狀態的充分必要條件是

g(xi，S+,k)＝g(xj，S+,k)

把規範微商文法中等價的狀態合併，可得到從GCD導出的可數個遞歸性文法，其中包含至少一個文法可作為推斷問題的解。

對於正則文法，已研究出以規範微商文法為基礎的推斷演演算法和基於 k尾的文法推斷演演算法，但對於上下文無關文法的推斷則尚無普遍適用的演演算法，只是對某些特殊限制的上下文無關文法有了一些啟髮式的演演算法。例如應用結構信息序列推斷運算元優先文法以及k齊次、k互異文法和樞軸文法推斷，圖形描述文法的啟髮式推斷等。在隨機文法的推斷方面，曾經提出一種直接綜合隨機有限狀態自動機演演算法。其中狀態轉移概率可以從隨機語句集合中相應的概率信息中導出。

此外，在人機對話式的文法推斷系統結構、正則樹文法、網狀文法等推斷方法方面都已經取得了一定的成果。

參考書目

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