beberapa waktu lalu gw lagi nyari-nyari referensi tentang mesin inferensi di
http://www.sourceforge.net dan nemu contoh implementasi mesin inferensi yang cukup sederhana dalam bahasa Ruby -> SIE (Simple Inference Engine). karena gw lagi ngutak-atik irrlicht yang notabene pake C++ akhirnya gw port ke dalam C++ dengan memanfaatkan STL dan irrXML 1.2.
mesin inferensi dan sistem pakar
mesin inferensi merupakan elemen inti dari sistem pengambilan keputusan berbasis kaidah dalam intelejensia buatan. sistem pengambilan keputusan sendiri merupakan salah satu instans dari sistem berbasis pengetahuan (knowledge-based system) yang istilah populernya adalah sistem pakar (expert system).
sistem pakar punya arsitektur umum yaitu terdiri dari 4 komponen :
-
knowledge base, atau mungkin lebih tepatnya rule-base
-
working memory
-
mesin inferensi
-
user interface
rulebase, dalam bahasa indonesia berarti basis kaidah. isinya koleksi kaidah yang bisa di-inferensikan. setiap kaidah umumnya terdiri dari 2 bagian yaitu
anteseden dan
konsekuen dan dideskripsikan sebagai kaidah if-then seperti berikut :
Code:
IF anteseden THEN konsekuen
anteseden sederhananya adalah ekspresi boolean terhadap kebenaran suatu fakta. evaluasi kebenaran suatu fakta menggunakan acuan fakta-fakta yang 'diketahui' dalam 'working memory'
konsekuen adalah aksi-aksi yang dieksekusi jika kondisi dalam anteseden terpenuhi. aksi yang dapat dilakukan bisa berupa penalaran fakta baru (fact assertion), pembantahan/penghapusan fakta dari working memory (fact retraction), ataupun modifikasi terhadap fakta yang ada
working memory, merupakan koleksi fakta yang didefinisikan sejak awal, atau dibuat secara
run-time dari proses inferensi terhadap knowledge base.
mesin inferensi, mesin ini yang memproses kumpulan fakta dan kumpulan kaidah sehingga dibangkitkan fakta-fakta baru. kondisi berhenti mesin inferensi bisa saja ketika fakta tertentu yang menjadi tujuan(goal) muncul, ataupun tidak ada lagi aturan yang bisa dieksekusi (fired) berdasarkan fakta yang ada. untuk melakukan inferensi ada dua cara :
- inferensi maju (forward chaining), algoritma ini dimulai dengan
mencari kaidah yang sesuai dengan fakta yang 'diketahui'.
kaidah yang dievaluasi akan menghasilkan fakta baru yang selanjut
nya akan menyebabkan kaidah lainnya untuk dievaluasi. algoritma
ini akan berhenti jika tidak ada lagi fakta yang memenuhi kaidah
dalam basis kaidah.
- inferensi mundur (backward chaining), algoritma ini merupakan
sistem pembuktian teorem (theorem proving). cara kerja algoritma
ini dimulai dengan fakta yang ingin dibuktikan kebenarannya,
lalu kaidah-kaidah yang 'dicurigai' akan membuktikan fakta tsb.
akan dievaluasi. algoritma ini akan berhenti jika fakta yang menjadi
goal berhasil dibuktikan atau tidak berhasil dibuktikan.
user interface, antarmuka untuk interaksi dengan pengguna. misalnya dalam kasus sistem pakar jaman dulu, antarmukanya dialog
terminal-like antara user(manusia) dengan 'pakar'
Representasi Pengetahuan
fakta bisa didefinisikan sebagai suatu simbol (string?) yang punya nilai kebenaran (boolean?). simbol bisa jadi berupa suatu
term/'nama', proposisi dalam logika orde pertama (
First Order Logic) seperti dalam prolog, sebuah pasangan (
2-tuple) <nama_variabel,nilai_variabel>, atau triple OAV (
object-attribute-value)<nama_objek,nama_atribut,nilai_atribut>, jaringan semantik (simbol dan relasi {is-a, part-of, has, de el el.}), atau berupa
frame yaitu gabungan triple OAV ke dalam sistem slot, jadi setiap objek punya koleksi slot yang merupakan pasangan <attribute,value>.
mesin inferensi yang gw bikin pake representasi pasangan <attribute,value> dengan operasi evaluasinya hanya 'sama dengan' (untuk atribut <A,V> maksudnya jadi apakah variabel A nilainya sama dengan V bernilai
true atau tidak).
Quote:
|
gile, teorinya panjang juga ya..? udah lah, segini aja. kalo yang mo penjelasan lebih lanjut, baca buku tentang AI aja
|
Time to code
contoh file masukan dalam XML
Code:
<knowledgebase>
<!-- contoh goal -->
<goal>
<attribute>type.disease</attribute>
<text>Based on rudimentary knowledge, I believe the child has type.disease</text>
</goal>
<!-- contoh kaidah -->
<rules>
<rule>
<name>1</name>
<conditions>
<condition>
<attribute>active.temp.over.101</attribute>
<value>yes</value>
</condition>
</conditions>
<actions>
<action>
<attribute>fever</attribute>
<value>yes</value>
</action>
</actions>
</rule>
</rules>
<!-- contoh pertanyaan -->
<questions>
<question>
<attribute>squeaky.breath</attribute>
<text>Does the child squeake as he breaths?</text>
<response>yes</response>
<response>no</response>
</question>
</questions>
</knowledgebase>
Knowledge Representation
representasi pengetahuannya pake model pair <Attribute,Value>
Code:
class CKnowledgeAV
{
public:
CKnowledgeAV();
CKnowledgeAV( string Name, string Value );
~CKnowledgeAV();
string getValue();
void setValue(string Value);
string getName();
string toString();
protected:
string name;
string value;
};
Kaidah dan Pertanyaan
kelas kaidah
Code:
typedef map<string, CKnowledgeAV*> knowledgebase;
typedef map<string, CKnowledgeAV*>::iterator kb_iterator;
class CQuestion;
class CRule
{
public:
CRule(string Name);
~CRule();
void addCondition(CKnowledgeAV* cond);
void addAction(CKnowledgeAV* act);
string toString() ;
string getName();
bool isActive();
void setActive(bool bValue);
bool deactivate();
int getConditionCount();
bool isConditionMatch(knowledgebase knowledge);
bool isConditionSatisfied(knowledgebase knowledge);
bool isResolvable(map<string, CQuestion*> questions );
vector<string> getConditionAttributes();
void OnRuleFire(knowledgebase * knowledge);
knowledgebase getConditions();
knowledgebase getActions();
protected:
string name;
bool active;
knowledgebase condition; //antecedent
knowledgebase action; //consequent
};
kelas pertanyaan di-sekip aja..
Mesin Inferensi
kelas mesin inferensi, di-
embed ke XML Parser
Code:
//modification from simple inference engine in ruby
class CXMLRuleReader
{
public:
CXMLRuleReader(const char * filename);
~CXMLRuleReader();
void parse();
ie_state run();
void setQuestionHandler(IQuestionHandler* handler) ;
ie_state getStatus();
protected:
map<string, CRule*> rules;
map<string, CKnowledgeAV*> facts;
map<string, CQuestion*> questions;
IQuestionHandler* qHandler;
ie_state status;
CRule* current_rule;
CQuestion* current_question;
string fact_attr, fact_val;
string q_attr;//needed for consult to user
string goal_attr;
string goal_text;
IrrXMLReader* m_xml;
//control to continue inference process
bool isGoalKnown();
bool isFactKnown(string fact_attr);
bool isQuestionExists(string fact_attr);
CQuestion* getQuestion(string attr);
void consult(string attr);
};
algoritma inferensi
Code:
ie_state
CXMLRuleReader::run()
{
bool didsomething = false;
map<string, CRule*>::iterator pos;
int active_rule_count = rules.size();
status = IE_MORE;
while ((active_rule_count > 0) && (status == IE_MORE))
for (pos = rules.begin(); pos != rules.end(); ++pos){
CRule* r = pos->second;
if ( r->isActive() ){
if ( facts.size() > 0 ){
//printFactsKnown();
} //if
//try to resolve current rule
vector<string> rule_conds = r->getConditionAttributes();
bool rule_resolvable = true;
for (int i = 0; i<rule_conds.size(); ++i){
if ( !isFactKnown( rule_conds[i] ) )
if ( isQuestionExists( rule_conds[i]) )
consult( rule_conds[i] );
else{
rule_resolvable = false;
break;
}
} //for
if ( !rule_resolvable ){
//continue to next rule
continue;
} //if
//check if rule can be fired
if ( r->isConditionSatisfied( facts ) ){
r->OnRuleFire( &facts );
r->deactivate();
active_rule_count--;
//filter out non fireable rules
//forall rule
for (map<string, CRule*>::iterator p = rules.begin(); p != rules.end(); ++p){
CRule* rule = p->second;
knowledgebase kb = rule->getConditions();
//forall condition in rule that exist in knowledge base
for (kb_iterator kpos = kb.begin(); kpos != kb.end(); ++kpos){
//if attribute known and doesnt satisfied then deactivate rule
CKnowledgeAV* f = kpos->second;
if ( isFactKnown(kpos->first) ){
if ( f->getValue() != facts[kpos->first]->getValue() ){
r->deactivate();
break;
} //if
} //if
} //for
} //for
} //if
if ( isGoalKnown() ){
string tmpresult = goal_text;
CKnowledgeAV* fact = facts[goal_attr];
tmpresult = tmpresult.replace(tmpresult.find(goal_attr), goal_attr.length(), fact->getValue());
printFactsKnown();
status = IE_COMPLETE;
return status;
} //if
} //if r.isactive
} //for
//no more rules
return IE_COMPLETE;
}
main program
Code:
int main(int argc, char *argv[])
{
CXMLRuleReader* rules = new CXMLRuleReader(argv[1]);
rules->parse();
IQuestionHandler* handler = new CQuestionConsole();
rules->setQuestionHandler( handler );
rules->run();
delete rules;
delete handler;
return 0;
}
Linear Mode
