範例推理

一、原理和特徵?

類比是人們經常運用的解決問題的方法，有人甚至認為類比是人類問題解決過程中最主要的心理機制。人們在問題解決的過程中，常常依賴以前解決相似問題的經驗，來得到新問題的解決辦法。有時已有的問題解決方法可直接運用來獲得新問題的解，但更多的情形是經驗中並沒有解決新問題的現成答案，而是需要根據問題的求解目標修改過去解決類似問題時曾用過的方法以適應目前問題的要求，或綜合曾經成功運用過的多種方法來獲取最終的解決方案。基於範例推理（Case Based Reasoning，CBR）正是以人類解決問題的這種實際心理歷程為基礎的一種人工智慧範式。?

基於範例推理既是人類推理的一種重要形式，也是人工智慧研究中的一種範式。它不同於通過鏈式推理產生問題結論的基於規則的推理，是一種基於過去實際經驗或經歷的推理。?

基於範例推理，其工作原理是從眾多的已知範例中挑選出一個或多個和當前新問題最相似的範例，對它（們）的解決方案進行修改，從而得到新問題的解決方案。CBR系統的核心包括四個部分：（1）範例庫（case base）：存儲先前的經驗；（2）檢索機（indexing mechanism）：用一種有意義的方法排列範例；（3）匹配演演算法（matching algorithm）：比較新範例與舊範例的相似度；（4）調整機制（adaptation or inference mechanism）：推演得出最後的解法。?

CBR系統的運作過程可概括為“4Rs”，即（1）提取（Retrieve）；（2）重用（Reuse）；（3）修改（revise）和（4）存儲（Retain）。基於範例推理的步驟如下：（1）提出新問題作為目標範例，定義新問題的特徵或屬性；（2）檢索範例庫，根據問題的要求，在範例庫中找出與目標範例最為相似的範例（源範例），其關鍵是找出對新問題的解決有最大潛在啟發價值的舊範例；（3）根據修正規則來修改檢索到的舊範例，為新範例進行計算求解，為成功解決問題提供參考；（4）將有利用價值的新範例存儲到範例庫中，並對CBR系統的作相應的調整，以完成CBR的學習功能。CBR既是模擬人類推理和思考過程的方法論，也是建造智能計算系統的人工智慧技術。?

CBR系統是利用範例庫中存儲的先前解決類似問題的辦法進行推理，範例庫可以從某個知識豐富的資料庫中抽取，也通過各種知識獲取（knowledge acquisition）方法來得到。CBR系統從過去的經驗出發進行推理，能夠通過引用範例解釋其推理，如果範例庫中沒有現成的精確的解法，CBR系統會作出調整給出一個近似的解法，系統用檢索或匹配機制來判定範例間的相似性，幾乎不需要抽取專家知識。因此，CBR具有符合人類解決問題的心理適宜性。?

CBR有兩種基本類型：解釋型CBR和問題求解型CBR。解釋型CBR是應用舊範例構建一種分析和證明，以對新範例作出某種解釋；問題求解型CBR則是通過調整舊範例的解答以滿足新問題的要求。前者多應用於諮詢系統中，後者在計劃、設計工程中更為常用。?

基於範例推理和其它人工智慧範式相比有許多優勢。首先是獲取知識相對容易。開發基於規則推理的系統時，需要領域專家和知識工程師密切合作獲取規則或模型，而在許多複雜領域中，很難從對專家解決問題的的研究中獲得能用語言符號明確表述的該知識領域中的規則和原理，導致知識獲取的瓶頸問題。在CBR中，不需要對經驗分解或抽象以形成規則，知識表徵的單位是範例，而範例在許多領域容易收集，獲取代價較低。其次是知識維護容易。隨著系統的運行，知識系統常需要更新，在基於規則的推理系統中增加新規則可能會和原有的規則產生衝突，甚至導致非常大的系統變動；基於範例推理則不存在這樣的問題，它可以不需要專家的干預而把缺少的範例添加到範例庫中。三是解決問題範圍的擴大。其它人工智慧範式多為演繹推理模式，所有關於問題的答案都預先包含知識庫中，不具有創新求解能力。CBR主要基於類比推理，通過適應性修改可以形成與舊範例的解決方案不同的創新解答。最後是用戶接受度高。基於範例推理的根據是歷史事實，事實勝於雄辯，因此對用戶更有說服力。?

二、研究問題?1、範例庫的建立?

範例庫是CBR中的重要組成部分，它是CBR 中主要的知識庫。範例庫的大小及其組織結構直接影響CBR系統應用的效率和效果。如何表示範例，如何組織範例，如何建立範例庫的索引，是建立範例庫的主要問題。實際上，這是三個相互聯繫著的問題。?

（1）範例表示?

CBR系統所依賴的知識主要存儲在範例中，範例的集合構成範例庫。一個範例可以是一個病人的病歷，也可以是一個菜譜、一個法律的範例，可以是一座簡單房子的平面圖，也可以是一座音樂廳的最詳細的全部設計圖。?

在CBR範例庫的建造中，一個合理的、一致的範例表示方法是必不可少的。範例應該包含什麼？一般認為，範例可以定義為能夠導致特定結果的一組特徵或屬性的集合。從問題求解的角度來看，一個範例的內容主要由三部分組成：一是問題或情境描述（situation）；二是解決方案描述（solution）；三是結果描述（outcome），即可以表示為三元組：C=<問題或情境描述，解決方案描述，結果描述>。怎樣用一種合適的方式把範例的三個部分表示出來，是CBR系統首先要解決的問題。在CBR系統中沒有通用的範例表示方法，往往需要在分析具體問題領域的基礎上通過選擇、綜合或修改現有的各種知識表示方法來實現。最簡單的方法是對範例進行屬性抽取，然後對各個屬性賦值。有人採用框架方法表示範例。?

另外，一個範例既可以作為整體來存儲，也可以把範例分解為部分分別存儲在不同的模塊中單獨使用。前者適合於結構性差的範例，存取簡單但應用時不夠靈活；後者適合於結構性強的範例，應用和維護時較靈活。 ?

（2）範例的組織與索引?

索引是通過以重要屬性組合範例來對範例分類和存儲，其目標是在對已有範例進行索引后，當給定一個新範例時，如果範例庫中有與該範例相關的範例，則可根據索引快速找到那些符合需要的相關範例。一個範例的索引就是這個範例的重要屬性的集合，這些屬性可以將這個範例同其他範例區分開來。索引問題的主要任務包括：選擇什麼類型的索引，如何定義索引辭彙表，如何構建索引的搜索空間等。?

良好的範例索引能使範例提取快速而準確。良好範例索引的建立是建立在對問題領域和問題目標充分理解的基礎之上的。Kolodner認為，索引問題就是在適宜的時候提取可應用範例的問題，也就是給每個範例貼標籤以表明在什麼條件下該範例能用來作出有用的推理。他曾給出良好索引的四個品質：一是預測性，能夠明確範例的問題解決目標；二是抽象性，具有一定的抽象度，以便能夠適應問題情境的變化；三是具體性，索引應是無需作進一步解釋就可在將來問題情境中加以再認；四是有用性，索引應能以一種有用的方式把範例區分開來，能夠對面臨的決策提供指導。?

在範例庫中，範例間的組織方法主要有三種：線性組織、層狀組織和網狀組織。具體採用哪種組織，要看範例間的關係如何。在實際應用中，有時把幾種組織方法組合起來使用。?

陳敏等結合存儲組織包結構和語義模型描述了一種通用的範例表示結構；王亞英等人探討了在CBR中範例的粗集表達法和索引法；趙鵬等人利用數據挖掘技術從傳統資料庫中構造範例庫。?

2、範例檢索或提取?

範例的檢索或提取是從範例庫中找到一個或多個與當前問題最相似的範例。範例庫中的每一個範例都包括以前問題的一般描述即情景與解法。當接受了一個求解新問題的要求后，CBR利用相似度知識和特徵索引從範例庫中找出一組與當前問題相關的符合要求的範例，並從中選擇一個最佳範例。因為檢索得到的範例的數量和質量直接影響問題的解決效果，所以範例檢索在CBR系統中是非常關鍵的環節。?

範例檢索通過三個子過程實現的。一是特徵辯識，就是對新問題進行分析，提取有關特徵；二是初步匹配，指從範例庫中找到一組與當前問題相關的候選範例；三是最佳選定，就是從初步匹配過程中獲得的一組範例中選取一個或幾個與當前問題最相關的範例。?

檢索過程的核心之一是檢索演演算法。演演算法與數據結構密切相連，不同的範例庫組織結構要有相應的不同演演算法來檢索。因此，CBR中已經形成了一系列範例組織和檢索的策略和演演算法，但並沒有通用的檢索演演算法。最常用的檢索演演算法三種，一是最近鄰法，該方法採用屬性間的加權匹配來估計範例間的相似度，其關鍵是如何確定屬性的權重；二是歸納法，採用歸納法可以確定哪個特徵在區分範例時最好，用這種方法能生成一顆決策樹，可以有效地組織範例；三是模板檢索，該方法能返回在一定參數值範圍內的所有範例。國內有人對範例提取進行了探索。

CBR成功應用的關鍵是通過檢索得到相似範例。因為範例檢索是在相似比較的基礎上進行的，因此，如何定義相似度對檢索結果至關重要。範例表示是由許多屬性組成的，範例間的相似度就是根據屬性之間的相似度定義的。相似性關係可分為表面相似性和結構相似性，前者定義為對確定問題的解不扮演因果角色的那些共性，後者指影響問題目標的那些共性。?

相似性的計算可分為兩步，屬性間相似性的計算和範例間相似性的計算。屬性間相似性計算根據數值類型的不同分為數值性屬性的相似度、枚舉型屬性的相似度和順序性屬性的相似度。計算範例間相似度就是考慮把一個範例的各個屬性相似度綜合在一起形成的效應。?

範例間相似度通常是通過距離來定義的，常用的典型距離有絕對值距離，歐氏距離和麥考斯基距離等。國內的工作者也對範例相似度的評估和計算方法進行了研究。?

3、範例調整或修改?

把檢索到的舊範例的解答覆用到新問題時，首先要對復用結果進行評估，如果成功，就不需要調整或修改，否則需要對解決方案進行調整或修改。進行結果評估既可依據在實際應用后的反饋，也可通過向專家諮詢完成。?

檢索到的舊範例一般不可能和新問題完全匹配，因此CBR系統一般都必須調整過去的問題解答以得到適合新問題的較好的解答。範例調整方法主要有四類，第一種是替換法，把舊解中的相關值作相應替換而形成新解。如重新例化（reinstantiaton）,將舊解決方案重新實例化為新對象；參數調整（parameter adjustment），通過不同的輸入參數會導致不同的輸出結果的啟髮式方法，對舊解答的數值參數進行調整；局部搜索（local seach），通過搜索輔助的知識結構來替換那些不適合新情況的值或結構的方法；查詢（query），用帶條件的查詢在範例庫或輔助知識結構中獲得替換的內容；特定搜索（specialized seach），同時在範例庫和輔助知識結構中進行查詢，但在範例庫中查詢時使用輔助知識來啟髮式指導如何搜索；基於範例的替換（case based substitution），使用其他範例來建議一個替換。第二種是轉換法，包括常識轉換法（common-sense transformation）和模型制導修補法（model-guided repair），前者使用明白易懂的常識性啟髮式從舊解中替換、刪除或填加某些組成成分。後者是通過因果模型來指導如何轉換；第三種是特定目標驅動法(special purpose adaptation or repair)，該方法是基於規則的產生式系統給出領域特定的適應性修改。第四種是派生重演(derivation replay)，使用過去推導出舊解的方法來推導出新解，它關心是解是如何求出來的。?

目前，雖然多數CBR系統的範例修改是通過人機交互過程來完成的，但對自動的範例修改方法的探索已有一些成果，如有人提出通過使用一個基於範例的適應性修改部件來獲得和復用成功的適應性修改過程，這是一種在CBR方法自身過程中應用CBR方法的思想。?

4、範例學習與記憶

新問題一旦得到解決，其解決過程或方案可能會用於與之相似的未來問題。因此，有必要把它加入到範例庫中，這就是CBR的學習和記憶，也就是知識獲取。範例學習主要涉及到兩個問題，一是選擇哪些信息予以保留；二是如何建立有效的索引，以便日後能對它作出有效的回憶。?

CBR的學習途徑可分為成功驅動的學習與失敗驅動的學習。當問題得到解決時，CBR系統學習到了成功的經驗，新的成功範例添加到範例庫中，系統增加了對問題領域的覆蓋範圍，這是成功驅動的學習。失敗驅動的學習可以幫助CBR系統注意到哪些問題是重要的，是否忽略了某些要點，如何避免和減少將來的失敗等。?

CBR系統通過以下幾種方法完成學習：一是新範例的積累，保存成功和失敗的範例，這是對CBR所依賴的知識的學習；二是建立、修改和撤消指向範例的索引路徑，完善索引機制，這是對如何檢索CBR系統中範例的元知識的學習。三是歸納學習，具有某種共同特徵或同屬於某個分類的範例的集合可以描述一個概念，在向這樣的範例庫中添加新範例是，可以理解為CBR系統在學習這一概念，從某種意義上說，保存一個典型的範例可以被認為是歸納學習的一種形式。?

CBR不僅代表了一種推理方法，而且了代表了一個機器學習方法。