文法推斷

在統計模式識別方法中，經常用已知類別的模式樣本集訓練判別函數，同樣在句法模式識別中，也可以用已知類別的模式樣本集來訓練類別文法，這種訓練過程或者説學習過程稱為文法推斷。文法推斷就是要構造出能正確描述某類模式的文法，其中主要是求生成式集合P。前面關於模式描述方法的討論是在假定文法已知的前提下進行的。

每一類模式有一個文法，由於模式用句子表示，而句子可以由鏈、樹、圖表示，所以相應地就有鏈文法、樹文法和圖文法的推斷問題。當選擇了文法的形式之後，就可以根據一組數目足夠且具有代表性的樣本來推斷文法。

通過文法推斷可以得到一組重寫規則，它們除了能描述給定的有限樣本集外，還能描述那些雖不在給定樣本集內但卻與給定樣本集在某種意義上有同樣性質(屬於同一類)的模式，從而可以用這一組重寫規則對輸入模式進行句法分析以達到識別的目的。

文法推斷過程就是對模式類進行描述的過程，它的正確性在很大程度上決定於所給樣本集的完備性和人們對模式性質瞭解的程度，文法推斷算法至今仍然是句法模式識別中的一個重要研究課題。 ^[1] 

文法推斷課題的一般性質是：

給定某個文法G所產生的語言L(G)的一個有限子集S+(叫正樣本集)和不屬於這個語言的集合的一個有限子集S-(叫負樣本集)，須假定S+是結構完整的，即描述L(G)的每一條重寫規則在描述S+中的樣本時至少使用一次

在理想情況下，L(Ga)=L(G)。在實際問題中，由於所提供樣本的侷限性，S+往往不是結構完整的，推斷得到的文法Ga只是G的一種近似。對於同樣的有限樣本集，不同的推斷算法可以得到不同的Ga，因此需要定義一個所推斷出的文法對於給定樣本集的優度度量，從而能在某種意義上得到一個滿意的結果。

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

①窮舉文法推斷算法：在一個文法類中進行搜索，以求得與所給樣本集和學習系統（教師）所提供的其他附加信息一致的文法。為了提高搜索的效率可以利用覆蓋這個重要概念：如果某個文法G1不產生S+中所有的語句，在窮舉中可以刪去被G1所覆蓋的所有文法；而如果文法G1產生S-中某些句子，則在窮舉中可刪去所有覆蓋G1的文法。

②歸納文法推斷算法：從正樣本S+中求得語言L的遞歸結構，從而使一個恰好產生給定正樣本的非遞歸性文法成為一個能夠產生任意多語句的遞歸性文法。

文法推斷（Grammatical Inference）與機器學習（Machine Learning）的區別，機器學習是狹義的（或標準的）機器學習。從廣義上講，文法推斷也屬於機器學習的範疇。

兩者的共同之處都是從有限的經驗數據自動學習知識，嘗試找到一種隱藏在樣本數據背後的模式。機器學習的處理對象是數值型數據，學習結果是對數據分類和迴歸分析；文法推斷的處理對象是字符序列，學習結果是生成字符序列的形式文法。 ^[2]