我的雲端生活網 - Life+

Tuesday, December 30, 2008

以 Prolog 示範規則推論系統

規則推論系統,須由規則推論引擎、知識庫、以及輸入事實三者構成。推理方法有向前鏈接 (forward chaining) 和向後鏈接 (backward chaining) 方式,分別對應二種不同的需要。向前鏈接是由規則的前提向規則的結論方向串連可用的規則,由原因導出結果。向後鏈接是由規則的結論向規則的前提方向串連可用的規則,由結果導出原因。於是,前者適用於預測和決策,而後者適用於診斷和歸納。
Prolog 是法文 programmation en logique ,即英文 programming in logic 的合併詞,是個以邏輯操作為主的程式語言。 Prolog 的推理方法是向後鏈接,而且,將 Prolog 系統比擬為推論引擎,是使用 Markov 演算法作為規則歸納策略。說「比擬為推論引擎」,指 Prolog 並不是完整的專家系統框架。不過, Prolog 提供了足夠的基礎架構,可能做出小型、甚至大型的規則推論系統。
本篇以一份小、且不完整的規則知識庫,解決學術界一項著名的小問題「猴子取香蕉」 (the monkey and bananas problem) ,作為對於規則推論系統的展示。
問題描述:
在空間中有猴子,和香蕉、梯子、躺椅等物品,散置於各處。猴子窩在躺椅上,香蕉懸在高處,而且躺椅、香蕉和梯子彼此相隔特定距離。猴子必須站在夠高的位置,並靠近夠近的距離,才能取得香蕉。於是,問題是:猴子該如何取得香蕉?
猴子取香蕉的問題在學術界有各面的討論,例如,研究心理與認知的人關心動物如何操作心理的機能以達成學習。我們對於規則推論系統的討論,則關心要解決這件問題,該建立哪些知識,以及該如何使用這些知識來推理。以下是我的程式。須注意這份程式只是示範,並是知識未建置完整。所示範的重點是:可建立足夠的知識以取得解答,以及掌握 Prolog 向後鏈接推理方法的原則撰寫規則。
% The monkey and bananas problem

% Naming principle:
% 1. Adjectives: for checking properties.
% 2. Verbs: for goals with two members, i.e., a subjective and a objective.
% 3. Past Participles: for goals with two members, i.e., two objectives.

% facts
:-
assert(near(monkey, position(3, 4))),
assert(near(bananas, position(5, 2))),
assert(near(ladder, position(1, 1))),
assert(near(couch, position(3, 4))),
assert(on(monkey, couch)),
assert(light(bananas)),
assert(light(ladder)),
assert(high(bananas)).

% backward chaining rules
holds(monkey, W) :-
not(high(W)),
light(W),
made_neared(monkey, W),
format('Monkey holds ~w.~n', W)
;
high(W),
light(W),
made_neared(ladder, W),
not(on(monkey, ladder)),
climbs(monkey, ladder),
holds(monkey, W)
;
high(W),
light(W),
made_neared(ladder, W),
on(monkey, ladder),
holds(monkey, W)
.
made_neared(O1, O2) :-
near(O1, P1),
near(O2, P2),
moves(O1, P2),
format('Now ~w is near ~w at ~w.~n', [O1, O2, P2])
;
near(O1, P),
near(O2, P),
format('~w and ~w are at the same position.~n', [O1, O2])
.
moves(S, P) :-
retractall(near(S, _)),
assert(near(S, P)),
format('Action performed: moving ~w to ~w.~n', [S, P])
.
climbs(S, O) :-
retractall(high(_)),
assert(on(S, O)),
format('~w climbs on ~w.~n', [S, O])
.
Prolog 的基本符號有:小寫開頭符號為詞彙 (term),大寫開頭符號為變數,帶有參數的詞彙為描述詞 (predicate)。 ":-" 是規則的中介符號,其左邊項是規則的結論,右邊項是規則的前提。句點是一則完整描述的結尾,逗點是 and 連接詞,分號是 or 連接詞。一則完整描述若只帶有左邊項(沒有右邊項和 ":-" 符號),是單元詞彙,代表既存在的事實。一則完整描述若只有右邊項和 ":-" 符號,代表一則查詢。以上程式撰寫了事實與規則。程式的啟動狀態為:
near(monkey, position(3, 4))
near(bananas, position(5, 2))
near(ladder, position(1, 1))
near(couch, position(3, 4))
on(monkey, couch)
light(bananas)
light(ladder)
high(bananas)
以上描述詞彙,使用 assert 描述詞和逗號組合成查詢句型,使程式被載入時能動態地建立這些詞彙。( Prolog 中,只有動態建立的描述詞才能被動態地刪除。)這些詞彙稱為事實,構成推論系統的工作空間及狀態。
規則的組成結構,以第一條規則為例,是:
holds(monkey, W) :-
not(high(W)),
light(W),
made_neared(monkey, W),
format('Monkey holds ~w.~n', W).
要找到一項目標 holds(monkey, W) ,「要猴子抓住某物品W」,附帶若干條件例如「物品W位置不高」、「物品W很輕」,則必須找到一項前置目標 made_neared(monkey, W) ,「要讓猴子與物品W是位置接近的」。最後一項 format('Monkey holds ~w.~n', W) 是將物品W放進字串 "Monkey holds ~w.~n" 的 ~w 位置,作為結果輸出。最後一項輸出存在的意義是,引用的這一項規則之後,狀態為「猴子抓住了香蕉」。其他規則比照於此,都包含了一項目標 (goal)、必要的前置目標 (subgoal)、相關的條件、以及引用規則之後的狀態。將程式存檔為 .pl 副檔名,用 Prolog 載入這份程式,並輸入查詢:
?- holds(monkey, bananas).
以上查詢是問「猴子抓住香蕉,怎麼做?」結果輸出為:
Action performed: to move ladder to position(5, 2).
Now ladder is near bananas at position(5, 2).
monkey climbs on ladder.
Action performed: to move monkey to position(5, 2).
Now monkey is near bananas at position(5, 2).
Monkey holds bananas.
true
換個查詢:
?- holds(monkey, ladder).
「猴子怎麼取梯子?」結果輸出為:
Action performed: to move monkey to position(1, 1).
Now monkey is near ladder at position(1, 1).
Monkey holds ladder.
true
以上例子要展示,對於一些有多個解決方向的問題,也許不適合直接寫一條演算法,或者不適合強制決定一項結果。而使用了規則推論系統,只要寫了適合的規則知識,就能夠取得可接受的答案。雖然答案的正確程度取決於規則的正確程度,不過,此系統的優勢是對於取得解答的要求與限制是寬鬆的、軟性的。
備註: Prolog 的規則格式,左邊項幾乎只能有一項描述詞,而缺乏 and 或 or 連接詞的寫法。因應於此限制,規則的四項構成物件:目標、前置目標、相關條件、以及引用規則的描述,只有目標寫在左邊項。其他使用向前鏈接推理的系統,例如 OPS ,規則格式寫成 "if ... then ..." 格式,能夠容許左邊項和右邊項都有 and 或 or 連接詞的寫法,則是在左邊項寫了前置目標和相關條件,並在右邊項則寫了目標和引用描述。

Monday, December 29, 2008

推論引擎

最近在閱讀有關規則推論引擎 (rule-based inference engine) 的書和資料。這方面的研究知識早在九零年代結束之前就成熟了,但在國內技術應用看起來像是冷門技術項目。有人說專家系統是沒落的東西。然而,放眼看過去技術應用趨勢,八零年代時 LISP 的使用也相當熱門,九零年代初期 Prolog 已取得成功應用,而專家系統 (expert system) 的規則推論引擎和框架系統 (frame-based system) 是二項成功產物。資訊領域並不是只有命令式程式 (imperative programming) 計算模型,並不是要會寫 C 或 Java ,或者要會雕刻組合語言,才佔領全局。還有其他的聰明、高產能的選項可挑選!
推論引擎的產生,來自於解決問題的需要 --- 許多問題並不只是寫一則演算法就能解決。有些問題的思考空間太龐大,而且對於那些問題,經常只有一部分的解題規則,這些規則可能來自於專家的知識或經驗。於是生成系統 (Production System) 出現,後來此系統類型稱為專家系統。規則式生成系統的構成,有一組以具體表達的規則所組成的知識庫、知識輸入介面、推論引擎、以及工作空間。系統接受一些事實作為輸入,由推論引擎將輸入事實與知識庫中的解題規則互相比對,藉由邏輯的歸納推理產生解決方案。此系統的好處是,答案是由專家知識所導出,而且導出答案的那些規則可以直接作為解釋。缺點是,系統所容納的知識庫不能太大,若規則太多則耗費計算時間,以及知識規則的建置花費工夫。
推論引擎的效能問題,在於輸入的事實與知識庫的規則比對所消耗的時間。 Markov 演算法提出順序式的比對,帶來直接的毛病是:有多少規則,就要比對多少時間以上。而且,規則的比對經常花費 O(n2) 級的成本,因為推論引擎必須做到衝突決議 (conflict-resolution) 的處理程序,意即經過眾多層次不同且可能有彼此矛盾的規則,綜合評判之後,取得一致的正確結果。為了適應規則推論引擎的特殊計算環境, Rete 演算法提出以網狀資料結構 (rete 是拉丁文,意思是 net ) 處理衝突決議。推論引擎總是進行循環工作,進行步驟有:1. 接受輸入事實並啟動; 2. 比對規則; 3. 衝突決議:若沒有比對到任何規則,則關閉,否則由比對到的規則中挑選一條規則,認定為生效; 4. 將生效的規則啟動,改變工作空間的狀態; 5. 回到步驟 (2) 。
推論引擎雖然不好寫,卻也可以用組合語言或 C 撰寫。 2003 年, Lynwood Wilson 在 Dr. Dobb's 雜誌發表的文章 ”Rule-Based Programming in C” 示範了二項注意事項: 1. 要做衝突決議; 2. 將專家系統劃分為模組使計算時間減少。因為是簡單的示範,他使用 Markov 演算法比對規則。
參考文獻
1. Joseph C. Giarratano & Gary D. Riley. Expert Systems: Principles and Programming. (4 ed.) Course Technology, Thomson Learning, 2005.
2. Charles L. Forgy. Rete: a fast match algorithm. AI Expert, vol. 2, issue 1, 1987.
3. Lynwood Wilson. Rule-Based Programming in C. Dr. Dobb's Portal. Available online: http://www.ddj.com/184405245.

Saturday, December 20, 2008

可以在ORACLE使用PL/SQL發送MSN訊息?

<imoo msn機器人測試平台,將於下週三(2009.6.24)取消所有未經申請試用的認證資訊,詳見相關資訊>



我好久沒碰RDBMS了,主要是因為我覺得殺雞焉用牛刀?這幾年我都使用檔案系統來處理資料,不過在此之前;我幾乎摸過了市面上各式各樣的RDBMS,當然也包括ORACLE,以前我們常使用ORACLE的trigger 或是store procedure 來處理一些事務,所以;我還沒忘記,ORACLE 內有一個很好用的利器UTL_HTTP Package,這裡有一個範例:
http://www.oracle.com/technology/sample_code/tech/pl_sql/htdocs/x/Utl_Http_Package_Enhancements/Cr_Using_Utl_Http.htm
事實上只要利用這個Package,我們就能直接使用triger配合 URL_HTTP 直接線上呼叫msnSDK 發送msn訊息,這個連結也一併給您參考 http://rd-program.blogspot.com/2008/12/msn_18.html 您可以參考這個簡易的範例知道怎麼透過http protocol發送msn訊息

抱歉!我因為太久沒直接碰oracle,手邊也沒有伺服器可用,所以沒辦法直接給出範例,不過我相信過這個描述你們自己一定做的出這個範例,如果有人做出範例;願意讓我知道的話在麻煩您給我一個連結,我會請其他有興趣的人直接去讀您的大作囉...

當然;我同時也相信oracle 現在應該已經有soap 這類的package,因為;我在使用oracle的那段時光,soap尚未成為標準,所以沒有接觸過,否則;有能直接使用這類的package操作msnSDK,不只ORACLE,MSSQL也能透過呼叫外部的ACTIVEX 來做同樣的事...

Wednesday, December 17, 2008

如何直接使用瀏覽器發送MSN訊息

<imoo msn機器人測試平台,將於下週三(2009.6.24)取消所有未經申請試用的認證資訊,詳見相關資訊>



使用瀏覽器就能對MSN發送訊息

使用程式運用msnSDK傳遞MSN訊息真的很簡單,這個例子我們直接使用瀏覽器來發送MSN訊息,現在要找到一種語言不支援這些介面還真不容易(msnSDK支援ADO/CGI/SOAP 三種介面)

--------------
STEP 1:
首先要使用msnSDK 發送訊息,必須取得使用SDK權限
---------------------------------------------------------------
http://59.120.234.84:8082/msnSDK/msn_cgi-win32?FUNC=GETSPID&USERID=apiblogt7&PASSWD=msnsdkt

瀏覽器得到回應(SPID 是一個隨機碼)
1\tSPID
或是
0\t失敗原因

比如: (請注意! 5M9AzR700NWZbbAf 會一直變動,而一旦通過認證這個SPID 可使用6個小時不需重複取用SPID,過期再取即可)

1 5M9AzR700NWZbbAf

--------------
STEP 2:
邀請聯絡人,我想大家都知道,要透過MSN發送訊息,得要對方是我們自己的聯絡人,要特別注意的是XXXXXXXX@hotmail.com得要是真正的MSN地址,因為發送MSN訊息時,得要對方再線上(範例是這樣使用,不過;msnSDK本身可以自動判斷對方是否再線上決定是否發送離線訊息...這需要參考文件,可自行下載文件)
---------------------------------------------------------------
http://59.120.234.84:8082/msnSDK/msn_cgi-win32?FUNC=REGISTER&UIDS=XXXXXXXX@hotmail.com&SESSION=5M9AzR700NWZbbAf

瀏覽器得到回應
1\t成功訊息
或是
0\t失敗原因

<<此時註冊為機器人聯絡人的帳號會在msn 上收到邀請成為聯絡人,選擇受邀請為聯絡人後>>
--------------
STEP 3:
發送訊息給XXXXXXXX@hotmail.com (這必須要是真的MSN帳號,且這個帳號必須在線上,如需傳遞離線訊息...請參考文件)
---------------------------------------------------------------
http://59.120.234.84:8082/msnSDK/msn_cgi-win32?UIDS=XXXXXXXX@hotmail.com&MSG=測試&flags=0&FUNC=SENDMSG&ENCODING=BIG5&SESSION=5M9AzR700NWZbbAf

瀏覽器得到回應
1\t成功訊息
或是
0\t失敗原因

--------------
其他功能可自行下載文件參考,msnSDK 同時支援YAHOO及MSN 的訊息傳遞(傳送與接收),且線上使用免費;歡迎所有有興趣的人直接在網路上應用它,如欲合作,可將合作提案寄到sonet.all@gmail.com

Monday, December 8, 2008

半分鐘搞定msn機器人互動式選單

msnSDK訊息控制開發套件,可支援訊息雙向傳遞;如您非程式開發人員,卻又有訊息雙向傳遞的需求,即可採用如下的作法,輕鬆達成簡易的需求。

Step1:安裝msnSDK訊息控制開發套件後,您可先至目錄msdSDKMenu。
開啟help.lst




PS,上述項目為既有範例,使用者可依據需求進行編輯。
開啟MSN,與MSN機器人的對話中,鍵入『?』或『#help』並Enter,出現如下的對話訊息。



Step2:於主選單增加一筆對話資訊
編輯help.lst,並存檔



與MSN機器人的對話中,再度鍵入『?』或『#help』並Enter。




Step3:編輯互動內容
至目錄msdSDKMenu下新增一目錄,目錄名稱需對應先前於主選單help所增加的指令字串,本例為『#mp』;建議直接複製預設的目錄如『#showndown』(此目錄內的其他檔案需一併複製),完成後將之更名即可。



可編輯目錄下的help.lst



編輯action.lst以呈現互動的結果



與MSN機器人的對話中,『#mp』並Enter。



如msn出現的說明,鍵入任意文字即出現回應訊息。



上述步驟即為簡易的訊息雙向傳遞,

此方法也支援直接直接取用url 資源

http://url....?msn=$msn_passport$&參數=$ARGVS[0]$


如配合原先企業或單位內已撰寫好的網頁或資料庫,不僅可成為單位內重要的訊息查閱管道更是KM整合的一大利器,而衍伸用法可達成不同以往的『單一簽入』型態及解決方案。

Wednesday, December 3, 2008

MSNC:File transfer 拒絕檔案傳送的程序

讀了相關資訊也從google 找資料,但是對 MSNSLP(P2P protocol)的描述多半語焉不詳,尤其是File Transfer,或許是自己的理解能力不好,只得自己SNIFFER,以下是整個拒絕檔案傳送的過程,試了一下;已正常可運行,我順便參考查看了某個msn的函式,發現他的做法不對;反而會造成client 不斷的請求(INVITE)

ps.以下相關msn帳號為測試帳號,並不會用來接收資訊

====Recv====
MSG xue.luke@hotmail.com ?? 1344\r\n
MIME-Version: 1.0\r\n
Content-Type: application/x-msnmsgrp2p\r\n
P2P-Dest: luke0@livemail.tw\r\n
\r\n
(00-00-00-00) (EF-64-8B-13) (00-00-00-00-00-00-00-00)
(2C-05-00-00-00-00-00-00) (B2-04-00-00) (00-00-00-00)
(3C-75-7B-23) (00-00-00-00) (00-00-00-00-00-00-00-00)
INVITE MSNMSGR:luke0@livemail.tw MSNSLP/1.0\r\n
To: \r\n
From: \r\n
Via: MSNSLP/1.0/TLP ;branch={9D589759-6F32-4136-BE3C-6CA353A20907}\r\n
CSeq: 0 \r\n
Call-ID: {8673FEF1-6E96-449D-AF21-8AD10E58630C}\r\n
Max-Forwards: 0\r\n
Content-Type: application/x-msnmsgr-sessionreqbody\r\n
Content-Length: 989\r\n
\r\n
EUF-GUID: {5D3E02AB-6190-11D3-BBBB-00C04F795683}\r\n
SessionID: 662509335\r\n
SChannelState: 0\r\n
Capabilities-Flags: 1\r\n
AppID: 2\r\n
Context: fgIAAAMAAAACAAAAAAAAAAEAAABiAGkAbgBhAHIAeQBfAGIAdQBpAGwAZABfADEALgAwAC4AMwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\� � Hide� Hide� 512� Recvb� AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
(00-00-00-00)

====Recv====
MSG xue.luke@hotmail.com ?? 264\r\n
MIME-Version: 1.0\r\n
Content-Type: application/x-msnmsgrp2p\r\n
P2P-Dest: luke0@livemail.tw\r\n
\r\n
(00-00-00-00) (EF-64-8B-13) (B2-04-00-00-00-00-00-00)
(2C-05-00-00-00-00-00-00) (7A-00-00-00) (00-00-00-00)
(3C-75-7B-23) (00-00-00-00) (00-00-00-00-00-00-00-00)
AAAAAAAAAAAAAAAAAAAAAAAAA/////wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=\r\n\r\n
00 (00-00-00-00)


====Send====
MSG 81 D 145\r\n
MIME-Version: 1.0\r\n
Content-Type: application/x-msnmsgrp2p\r\n
P2P-Dest: xue.luke@hotmail.com\r\n
\r\n
(00-00-00-00) (5A-C9-9C-1E) (00-00-00-00-00-00-00-00)
(00-00-00-00-00-00-00-00) (00-00-00-00) (02-00-00-00)
(EF-64-8B-13) (3C-75-7B-23) (2C-05-00-00-00-00-00-00)
(00-00-00-00)


====Recv====
ACK 81\r\n

====Send====
MSG 82 D 524\r\n
MIME-Version: 1.0\r\n
Content-Type: application/x-msnmsgrp2p\r\n
P2P-Dest: xue.luke@hotmail.com\r\n
\r\n
(00-00-00-00) (5B-C9-9C-1E) (00-00-00-00-00-00-00-00)
(7B-01-00-00-00-00-00-00) (7B-01-00-00) (00-00-00-00)
(47-A4-7E-27) (00-00-00-00) (00-00-00-00-00-00-00-00)
MSNSLP/1.0 603 Decline\r\n
To: \r\n
From: \r\n
Via: MSNSLP/1.0/TLP ;branch={9D589759-6F32-4136-BE3C-6CA353A20907}\r\n
CSeq: 1 \r\n
Call-ID: {8673FEF1-6E96-449D-AF21-8AD10E58630C}\r\n
Max-Forwards: 0\r\n
Content-Type: application/x-msnmsgr-sessionreqbody\r\n
Content-Length: 66\r\n
\r\n
SessionID: 662509335\r\n
SChannelState: 0\r\n
Capabilities-Flags: 1\r\n\r\n
00 (00-00-00-00)


====Recv====
ACK 82\r\n

====Recv====
MSG xue.luke@hotmail.com ?? 142\r\n
MIME-Version: 1.0\r\n
Content-Type: application/x-msnmsgrp2p\r\n
P2P-Dest: luke0@livemail.tw\r\n

(00-00-00-00) (F0-64-8B-13) (00-00-00-00-00-00-00-00)
(00-00-00-00-00-00-00-00) (00-00-00-00) (02-00-00-00)
(5B-C9-9C-1E) (47-A4-7E-27) (7B-01-00-00-00-00-00-00)
(00-00-00-00)

Blog Archive