AIというとPythonが多く使われますが、
今回はCで簡単なAIのアプリケーションを
実装して体験してみたいと思います。
エキスパートシステム、
それは人工知能の技術を用いた
1種のアプリケーションです。
専門家の思考を模したシステムです。
人間は生活しているといつかのタイミングで
予期せぬことに見舞われることが多々あります。
例えば、病気やパソコントラブルなど。
もし病気であれば、
「お医者さんに病名や直し方を聞きたい」
そう思うはずです。
そこでエキスパートシステムは
事前に用意された専門家の知識をもとに、
入力(症状)から出力(病名)を求めます。
やらんとしていることはいたって単純です。
エキスパートシステムの実現には、
そのコア技術である推論エンジンと
それの動力源となる知識ベースが
必要になってきます。
推論エンジンだけあっても
エキスパートシステムは動きませんし、
知識ベースだけあっても
エキスパートシステムは動きません。
それではまず、
推論エンジンと知識ベースの
大まかな説明からです。
推論エンジンとは何か
推論エンジンは入力から出力を
導くための仕組みのことを言います。
Wikipediaの定義によると、
知識ベースから答えを求める仕組み
と表現されています。
これは検索エンジンに似ています。
入力(検索ワード)があって、
そこから出力(検索結果)を求めます。
推論エンジンを説明する上で、
以下の3つの言葉が必要です。
- 知識ベース
- オブジェクト
- 属性(アトリビューション)
知識ベースとは、
専門家の知識を詰め込んだ
データベースのようなイメージです。
この知識ベースには、あらかじめ
オブジェクトと属性の関係が登録されます。
病気で言うなら病名と症状です。
この病気はこういう症状をもっている、
逆に言うなら、
こういう症状であればこの病気だ
といったことを登録します。
厳密に定義するなら、
オブジェクト：
保持する属性やルールを基に定義された名前
属性：
オブジェクトを定義する助けとなる特別な性質
エキスパートシステムの
全体イメージを以下に示します。
エキスパートシステムでは、
属性をヒントにして知識ベースから、
推論エンジンによってオブジェクトを求めます。
求めたオブジェクトには一般的に、
「決定的」 deterministic
「確率的」 probabilistic
の２つに分けることが出来ます。
エキスパートシステムが求めた
オブジェクトは100%正しいか
それとも○%の確率であるかの違いです。
つまり確率論的な答えは、
断言が出来ず、あくまで可能性がある、
ということで不確実性を持っています。
多くの場合は決定論的な問題は少なく
むしろ確率論的な問題が多いです。
不確実性をもつ推論エンジンは、
コードが長くなるので、
ここでは決定的推論エンジンを
扱っていきます。
なお推論エンジンの実装にあたって
「後ろ向き推論」を用いています。
推論法の詳しい説明を書くと、
より長い記事になってしまうので、
以下に簡単にご紹介だけします。
後ろ向き推論とは何か
後ろ向き推論とは、
「前向き推論」の逆の手法です。
ここで前向き推論とは、
属性から(オブジェクト)推論結果を導く方法です。
後ろ向き推論は、
ある推論結果(オブジェクト)を
あらかじめ予想・仮定し、
それが正しいかどうか、
属性を集めて確認する方法です。
今回は分かりやすいように、
オブジェクトに対しその属性をもつか
持たないか、という簡単なシステムですが
もう少し複雑なシステムあれば、
ルールを明確に定義して推論結果を導きます。
Cでエキスパートシステムの実装
パーツごとに分けています。
※以下の参考図書中のコードを
一部抜粋、改変しています。
「Cで学ぶAI」(マグロウヒル出版)
著者：渋谷恵津子、渋谷昇
まずは実行結果を見て、
全体的なイメージを掴みます。
実行すると最初に
メニューが現れます。
Enter / Query / Save / Load / eXit
の中から一つ選択します。
知識ベースを入力するために、
Enterを選択します。
適当に以下の
オブジェクトと属性を
知識ベースに登録します。
なお知識ベースの所在は、
実行ファイルと同じディレクトリ上です。
"expert.dat"というファイル名で
知識ベースが作成・登録されます。
| オブジェクト | 属性 | ||
|---|---|---|---|
| Japan | asia | small | advanced |
| China | asia | big | developed |
| America | north america | big | advanced |
知識ベースの登録が完了したら、
エキスパートシステムへ
問い合わせを行います。
1回目の問い合わせです。
質問に対してyesかnoを答えます。
Chinaがヒットしました。
続いて知識ベースには登録されてない
オブジェクトになるようにあえて
意図的に答えてみます。
No object foundになりました。
これらはエキスパートシステムが
あるオブジェクトを一つ仮定して、
順にその属性を満たすかどうか
質問してきます。
もしyesであれば、
仮定したオブジェクトに登録された
次の属性に関数質問をしてきます。
もしnoであればその属性を除外します。
仮定したオブジェクトが異なっていても
ある属性は共通している場合があります。
例えば日本と中国の"asia"という属性です。
この場合は、最初に日本と仮定していて、
asiaですかの質問にnoと答え場合、
中国は仮定されなくなります。
このことはシステムの効率化を図ります。
同じ質問を繰り返していては、
正解までに時間がかかります。
ちなみに、オブジェクトの仮定は、
ヒューリスティック性を実装していないので、
システムは知識ベースに登録した順に、
オブジェクトを仮定していくことになります。
それでは実際にコードを見てみます。
インクルードとマクロ定義です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #include<unistd.h> #define MAX 100 //オブジェクト最大数 #define NAME 50 //オブジェクト名の最大文字数 #define ATTRIB 50 //属性の最大文字数 struct attribute{ char attrib[ATTRIB]; struct attribute *next; }at; struct object{ char name[NAME]; struct attribute *alist; }ob; struct object k_base[MAX]; int l_pos = -1; //オブジェクト番号(配列の添え字)に相当 struct attribute *yes, *no; struct attribute *yesnext, *nonext; void free_trails(void); void enter(void); void query(void); int try(struct attribute *p, char *ob); int trailno(struct attribute *p); int trailyes(struct attribute *p); int ask(char *attrib); int get_next(void); char menu(void); void save(void); void load(void); void clear_kbase(void); void clear_kbase(void); int is_in(char ch, char *s); |
オブジェクトと属性の関係は、
リスト構造をとっています。
オブジェクト構造体のメンバに
属性構造体のポインタが入ります。
また属性は1個ではないので、
属性構造体のメンバに
属性構造体のポインタが入ります。
main文です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
int main(void){ char ch; no = yes = NULL; do{ free_trails();//Init ch = menu(); switch(ch){ //メニューの遷移 case 'e': //Enterメニュー enter(); break; case 'q': //Queryメニュー query(); break; case 's': //Saveメニュー save(); break; case 'l': //Loadメニュー load(); } }while(ch!='x'); //exitメニューでなければループ return 0; } void free_trails(void){ struct attribute *p; while(yes){ p = yes->next; free(yes); yes = p; } while(no){ p = no->next; free(no); no = p; } } //メニューを入力するための関数 char menu(void){ char ch; printf("(E)nter, (Q)uery, (S)ave, (L)oad, e(X)it\n"); do{ printf("[+]Choose one: "); ch = tolower(getchar()); //大文字入力だった場合、小文字にコード変換 while(getchar()!='\n'); //clear buffer }while(!is_in(ch, "eqslx")); //メニュー外の文字だった場合は再度入力し直し printf("\n"); return ch; } int is_in(char ch, char *s){ while(*s) if(ch==*s++) return 1; return 0; } |
最初に初期化して、
メニュー関数を呼びます。
メニュー関数からの戻り値で、
どのメニューが実行されたか知ります。
switch文で、選択されたメニューに応じて
それぞれ処理する関数に移ります。
Enterメニューが選択された場合です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
void enter(void){ int t, i; struct attribute *p, *oldp; char eol[]="\n\0"; //EOL:End of Line char *sp; for(;;){ t = get_next(); //オブジェクト番号取得 printf("KnowkedgeBase Nomber: %d\n", l_pos); if(t==-1){ printf("[-]Out of list space\n"); return; } printf("[+]Object name: "); fgets(k_base[t].name, NAME, stdin); //オブジェクト名を入力 if(k_base[t].name[0]=='\n'){ //ただエンター押されただけ l_pos--; //オブジェクト番号を減らす break; }else{ //名前が入力された sp = strstr(k_base[t].name, eol); //名前の配列に\n\0が入っているのでそのアドレスを取得 if(sp!=NULL) *sp = ' '; //スペースに変更。結果を上手く表示するために必要。 } if(!*k_base[t].name){ l_pos--; printf("out l_pos = %d\n", l_pos); break; } p = (struct attribute *)malloc(sizeof(at)); //属性のメモリ確保 if(p==NULL){ printf("[-]Out of memory.\n"); return; } k_base[t].alist = p; for(i=0; i<sizeof(p->attrib);i++) p->attrib[i]=' ';//Init printf("[+]Enter attributes (Enter to quit)\n"); for(;;){ //属性入力の終了=エンター押す、それまでループ printf(": "); fgets(p->attrib, ATTRIB, stdin); //実際に属性を入力 if(p->attrib[0]=='\n'){ //もしエンターのみなら if(oldp->next==p){ //一度でも属性が入力されている場合(for2回目以降) free(p); oldp->next = NULL; }else l_pos--; //1回目のforなら属性登録なしに該当するので無効 break; }else{ //属性が入力された場合 sp = strstr(p->attrib, eol); //\n\0がattrib配列に入っているので、そのアドレスを取得 if(sp!=NULL) *sp = ' '; //\n\0をスペースに変える。これをやらないと結果出力時に上手く動作しない。 } oldp = p; p->next = (struct attribute *)malloc(sizeof(at)); //次の属性用のメモリ確保 if(p->next==NULL){ printf("[+]Out of memory.\n"); return; } p = p->next; p->next = NULL; for(i=0; i<sizeof(p->attrib); i++) p->attrib[i] = ' ';//Init } } } int get_next(void){ l_pos++; if(l_pos<MAX) return l_pos; else return -1; } |
queryメニューが押された場合です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
void query(void){ int i; char ch; struct attribute *p; for(int t=0; t<=l_pos; t++){ //オブジェクトが見つかるか、登録したオブジェクトを全てチャックし終えるまで繰り返す。 p = k_base[t].alist; if(try(p, k_base[t].name)){ //仮定したオブジェクトをtry関数に渡す。try関数でそのオブジェクトが正しいか判断 printf("[+]The object is < %s>\n", k_base[t].name); //仮定が正しければ、オブジェクト名を表示 return; } } printf("[-]No object found\n"); //知識ベースには登録されていない } //仮定したオブジェクトが正しいが判断する関数(属性のyes/noを聞く) int try(struct attribute *p, char *ob){ char answer; char buffer[5]; struct attribute *a, *t; if(!trailno(p)) return 0; //yesの属性 if(!trailyes(p)) return 0; //属性が除外されていないか while(p){ if(ask(p->attrib)){ printf("[+]%s? y or n: ", p->attrib); fgets(buffer, sizeof(buffer), stdin); answer = buffer[0]; a = (struct attribute *)malloc(sizeof(at)); if(!a){ printf("[-]Out of memory\n"); return 0; } a->next = NULL; switch(answer){ case 'n': //質問に対してnoの場合 strcpy(a->attrib, p->attrib); if(!no){ no = a; nonext = no; }else{ nonext->next = a; nonext = a; } return 0; case 'y': //質問に対してyesの場合 strcpy(a->attrib, p->attrib); if(!yes){ yes = a; yesnext = yes; }else{ yesnext->next = a; yesnext = a; } p = p->next; break; } } else p = p->next; } return 1; } int trailno(struct attribute *p){ struct attribute *a, *t; a = no; while(a){ t = p; while(t){ if(!strcmp(t->attrib, a->attrib)) return 0; t = t->next; } a = a->next; } return 1; } int trailyes(struct attribute *p){ struct attribute *a, *t; char ok; a = yes; while(a){ ok = 0; t = p; while(t){ if(!strcmp(t->attrib, a->attrib)) ok = 1; t = t->next; } if(!ok) return 0; a = a->next; } return 1; } int ask(char *attrib){ struct attribute *p; p = yes; while(p && strcmp(attrib, p->attrib)) p = p->next; if(!p) return 1; else return 0; } |
trailno 関数は、ユーザ(回答者)が
no と答えた属性を格納し、
新たな属性と一致するか確認します。
trailyes 関数は、逆に yes を扱います。
これらの関数は、回答者に対して、
同じ質問をするのを防ぐ働きがあります。
saveメニューが選択された場合です。
知識ベースを保存しておくことが出来ます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void save(void){ int t, x; struct attribute *p; FILE *fp; if((fp=fopen("expert.dat", "w"))==0){ printf("[-]cannot open file\n"); return; } printf("[+]Saving knowledgebase\n"); for(t=0; t<=l_pos; t++){ for(x=0; x<sizeof(k_base[t].name); x++) putc(k_base[t].name[x], fp); p = k_base[t].alist; while(p){ for(x=0; x<sizeof(p->attrib); x++) putc(p->attrib[x], fp); p = p->next; } for(x=0; x<sizeof(p->attrib); x++) putc('\0', fp); } putc('\0', fp); fclose(fp); } |
load関数が選択された場合です。
保存した知識ベースをロードします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
void load(void){ int t, x; struct attribute *p, *oldp; FILE *fp; if((fp=fopen("expert.dat", "r"))==0){ printf("[-]cannot open file\n"); return; } printf("[+]Loading knowledgebase\n"); clear_kbase(); for(t=0; t<MAX; t++){ if((k_base[t].name[0] = getc(fp))==0) break; for(x=1; x<sizeof(k_base[t].name); x++) k_base[t].name[x] = getc(fp); k_base[t].alist = (struct attribute *)malloc(sizeof(at)); p = k_base[t].alist; if(!p){ printf("[-]Out of memory\n"); return; } for(;;){ for(x=0; x<sizeof(p->attrib); x++) p->attrib[x] = getc(fp); if(!p->attrib[0]){ oldp->next = NULL; break; } p->next = (struct attribute *)malloc(sizeof(at)); if(!p->next){ printf("[-]Out of memory\n"); break; } oldp = p; p = p->next; } } fclose(fp); l_pos = t-1; } void clear_kbase(void){ int t; struct attribute *p, *p2; for(t=0; t<=l_pos; t++){ p = k_base[t].alist; while(p){ p2 = p; free(p); p = p2->next; } } } |
以上です。
最後まで読んでいただきありがとうございました。
余談：
世界初(諸説あり)のエキスパートシステムは
1970年代にスタンフォード大学で
開発された、Mycin(マイシン)と
呼ばれる感染症診断システムだそうです。
当時では、その推論結果の精度は
大成功な値だったそうですが、
専門家が機械を拒んだため、
実際の現場では使われなかったとか。