研究ぶーろぐ

【整合性管理機構】：TMS
仮説に基づく問題解決において，効率的に仮説の整合性を管理するための機構


ルール　　　　(ノード１)　if ?x is a student then ?x wants to study
アサーション　(ノード２)　taro is a student
推論エンジン (ノード３)　taro wants to study

TMSを利用せず，以上のような推論を行った後，推論エンジンはノード１２３を，TMSに渡す．
つまり，１と２から３が推論できるということを正当化としてTMSに渡す．

■　TMSの役割
・推論結果の説明
「＜（１，２），３，演算推論＞」

■　TMSのノード
・前提ノード　：常に成り立つノード
・矛盾ノード　：常に成り立たないノード
・仮説ノード　：成り立つか成り立たないかのどちらかを選択しなければならないノード

TMSは複数のノードと正当化からなる依存ネットワークを生成し，
ノード間の整合性を管理する．

★ATMS★
TMSの中で，一般的なのがATMS.
各ノードのらべるからnogoodな環境を取り除くことによってノードの整合性を維持する．
ATMSにおいて，各ノードのラベル矛盾が起こらないように計算し更新するアルゴリズムは，
ラベル更新アルゴリズムと呼ばれる．

★ルールベースシステム
　　　if 条件 then アクション



【前向き推論】
　与えられたアサーションに対してルールの「条件」の部分に対してマッチングを行い、アクションを実行していく。
（例）「AはBである」という事実と、「BならばC」という規則から、「AはCである」という結論を導く推論方式
　　　事実から結果を求める作業を繰り返して、最終的な結論を導き出す方法

【後ろ向き推論】
　与えられた仮説が現在のアサーション集合において成り立つかどうかをルールを用いて検証していく。
「Ａ＝Ｃを証明するためには，Ｂ＝Ｃ，が示されればよい」と「目標Ａ＝Ｃ」の「副目標Ｂ＝Ｃ」を導く推論

【フレーム】
・セマンティックネットの概念を拡張した知識表現
・フレーム名と複数のスロットより構成　（ノード名とリンクに相当）

・フレーム －インスタンスフレーム　：特定な具体的な物事を表現
　　　　　　　　　　　　　　　　　　　　　　個々の個体・事項 (インスタンス) に関する情報
　　　　　　 －クラスフレーム　　　　 ：物事を一般化し抽象化した概念を表現
　　　　　　　　　　　　　　　　　　　　　　類似の個体・事項の集まり (クラス) に関する情報
　　　　　　（例）人；クラスフレーム　マツムラ：インスタンスインスタンスフレーム

・is-a：　インスタンスがあるクラスのインスタンスであることを示す
・ako：　あるクラスが別のクラスの概念を継承していることを示す」

・スロット
値：　　　 数値、文字列、他のフレームへのリンク、あるいはそれらの集合。
制約： 　 そのスロットの値として許されるものがどのようなものであるかを記述。
埋め込み手続き
　　　スロットの対象が
　　　　　　要求されたとき (when-requested procedure)
　　　　　　値を書き込んだ後 (when-written procedure)
　　　　　　値を読み出すとき (when-read procedure)
　　　などに自動的に呼び出される手続き。デーモン手続きと言われる。

「新谷という名前の教官と福田という名前の学生がいて，それぞれが計算機のOSとしてMacOS及びWindowsを好んでいる」

【セマンティックネットとは】
・ノードとリンクからなる有向グラフ
・ノード：　物、事柄、概念
・リンク：　ノードの関係と関係の名称

【概念間の関係】
・is-a関係：　　概念関係の上下、または包含関係　
　　　　　　　　 属性の継承が行われる

・has-a関係：　概念間の部分全体関係
　　　　　　　　　

Example実行結果
*** Links ***
baseball =is-a=> sports
Ito =is-a=> NIT-student
Ito =speciality=> AI
Ferrari =is-a=> car
car =has-a=> engine
( Ferrari =has-a=> engine )　//()で囲まれているのは，継承により作成されたリンクである
Ito =hobby=> baseball
Ito =own=> Ferrari
NIT-student =is-a=> student
( Ito =is-a=> student )
student =donot=> study
( NIT-student =donot=> study )
( Ito =donot=> study )
*** Nodes ***
baseball
sports
Ito
NIT-student
AI
Ferrari
car
engine
student
study
*** Query ***
?y =own=> Ferrari
?y =is-a=> student
?y =hobby=> baseball
[{?y=Ito}]

★新しいリンクを生成する場合、is-aリンクかどうかをチェック
　↓
　is-aリンクの場合、継承を行う

質問：フェラーリを所有していてかつ学生であり、かつ野球を趣味とするのは誰か？

⇒質問を分解：各質問についてマッチングを行う
質問１：野球を趣味としているのは誰か？
質問２：フェラーリを所有しているのは誰か？
質問３：学生であるのは誰か？

■Matching　
・パターンがアサーションに一致するかどうかをテスト
・実行には２つ引数を用意

実行結果
hanako
hanako
true

【?x is a girl she is a girlで実行】
?x
is
{?x=is}
true

【アサーション： Hanako is a girl】
・TrueであるアサーションをFactと呼ぶ

【パターン： ？x is a girl】

・Hanako is a girl と ？x is a girl のパターンマッチング
　⇒"？x"　を　"Hanako"に具体化(変数束縛)し、true

【プログラム】
class Matching
　arg.lengthの長さが一緒かどうか
　一緒なら、Matcherクラスのmatchingへ

class Matcher

public boolean matching(String string1,String string2)
　同じなら成功
　各トークンに分ける
　　数が異なったら失敗（countToken）
　　定数通しでトークンがマッチングに失敗したら失敗（tokenMatchingで行う）
　　最後までOKなら成功

boolean tokenMatching




■Unify
・パターンとパターンが一致するかどうかをテスト
・変数同士の比較をユニフィケーションという
・

実行結果
【?x ?y ?y byeを実行】
?x
?y
{?x=?y}
true

【?x aiu eo aiuを実行】
?x
aiu
{?x=eo}
true

以下のプログラムはUnifierである

定数同士
44: // 定数同士
45: int length = st1.countTokens();
46: buffer1 = new String[length];
47: buffer2 = new String[length];
48: for(int i = 0 ; i < style="display: none;" id="FLASH_MESSAGE">

構造は、マッチングとほぼ変わらないが、上記のプログラムで全てのトークンをいったん配列に格納している。
これは、ある変数に束縛されたとき、同じ変数名のトークンをあらかじめ具現化しておくためである。

■ 幅探索・深さ探索

幅優先探索

48:　 /***
49: * 幅優先探索
50: */
51: public void breadthFirst(){
52: Vector open = new Vector();
53: open.addElement(node[0]);
54: Vector closed = new Vector();
55: boolean success = false;
56: int step = 0;
57:
58: for(;;){
59: System.out.println("STEP:"+(step++));
60: System.out.println("OPEN:"+open.toString());
61: System.out.println("closed:"+closed.toString());
62: // openは空か？
63: if(open.size() == 0){
64: success = false;
65: break;
66: } else {
67: //openの先頭を取り出し node とする．
68: Node node = (Node)open.elementAt(0);
69: open.removeElementAt(0);
70: //node は ゴールか？
71: if(node == goal){
72: success = true;
73: break;
74: } else {
75: // node を展開して子節点をすべて求める．
76: Vector children = node.getChildren();
77: // node を closed に入れる．
78: closed.addElement(node);
79: // 子節点 m が open にも closed にも含まれていなければ，int=jなし
80: for(int i = 0 ; i < m =" (Node)children.elementAt(i);" m ="=">
81: Node m = (Node)children.elementAt(i);
82: if(!open.contains(m) && !closed.contains(m)){
83: // m から node へのポインタを付ける．
84: m.setPointer(node);
85: if(m == goal){
86: open.insertElementAt(m,0);
87: } else {
88: open.addElement(m);
89: }
90: }
91: }
92: }
93: }
94: }
95: if(success){
96: System.out.println("*** Solution ***");
97: printSolution(goal);
98: }
99: }

深さ優先探索

101: /***
102: * 深さ優先探索
103: */
104: public void depthFirst(){
105: Vector open = new Vector();
106: open.addElement(node[0]);
107: Vector closed = new Vector();
108: boolean success = false;
109: int step = 0;
110:
111: for(;;){
112: System.out.println("STEP:"+(step++));
113: System.out.println("OPEN:"+open.toString());
114: System.out.println("closed:"+closed.toString());
115: // openは空か？
116: if(open.size() == 0){
117: success = false;
118: break;
119: } else {
120: //openの先頭を取り出し node とする．
121: Node node = (Node)open.elementAt(0);
122: open.removeElementAt(0);
123: //node は ゴールか？
124: if(node == goal){
125: success = true;
126: break;
127: } else {
128: // node を展開して子節点をすべて求める．
129: Vector children = node.getChildren();
130: // node を closed に入れる．
131: closed.addElement(node);
132: // 子節点 m が open にも closed にも含まれていなければ，
133: // 以下を実行．幅優先探索と異なるのはこの部分である．
134: // j は複数の子節点を適切にopenの先頭に置くために位置
135: // を調整する変数であり，一般には展開したときの子節点
136: // の位置は任意でかまわない．
137: int j = 0;
138: for(int i = 0 ; i < m =" (Node)children.elementAt(i);" m ="=" style="color: rgb(255, 0, 0);">146: open.insertElementAt(m,j);
147: }
148: j++;
149: }
150: }
151: }
152: }
153: }
154: if(success){
155: System.out.println("*** Solution ***");
156: printSolution(goal);
157: }
158: }

　
　　 完全性 最適性 時間 　 空間
　　 　　　　 計算量 計算量
幅 　 ○ 　　　　 △ 　　 × 　　　 ×
深さ × 　　　 × 　　　 × 　　　 ○


■ 分岐限定法
・g（n）：各ノードのコスト
・h（n）:ヒューリスティックな値
・g（ｎ）が最小をたどる
・g（ｎ）が同じなら後に追加
・Ｃｌｏｓｅｄの順は関係なく、一番小さいg（ｎ）をかく

■山登り法
・h（ｎ）だけ用いる
・ｈ（ｎ）の最小をたどる
・直前に得たノードの子ノードの中だけから次に展開するノードを選択
・ｈ（ｎ）は正確な値ではないため、目標ノードを発見できない場合がある（ループするなど）

■最良優先探索
・山登り法を改善
・h（ｎ）最小をたどる
・現在展開した子ノードの他に今まで探索したノードから展開するノードを選択する
・最適コストの経路を発見できる保証はないが、グラフが有限ならたどり着く

■ＡアルゴリズムとＡ*アルゴリズム
・h(n)、g(n)、f(n)を利用
・f(n) ： h(n) と g(n) を足したもの
・OPENリストに含まれている：　f(n)が小さいものを書く
・Closedリストに含まれている：　

■ Iknow

　：e-learning

■ Friends Season 1 Episode 1 Part 1

　　：英語になれるのに丁度いいアメリカドラマ
　　 日本語のはこちら
　　 日本語の訳はこちら

■ Podcast

　　：初めてPodcast使ってみた．
　　 Ituneに登録するだけで，毎日手軽に英語のヒヤリングができて楽しい．
　　
　　【お勧めされたもの】
　　・ＢｕｓｓＯｕｔＬｏｕｄ
　　・ＥｎｇｌｉｓｈａｓａＳｅｃｏｕｎｄＬａｎｇｕａｇｅＰｏｄｃａｓｔ
　　・CNN Student News

　　【何気に登録してみたもの】：どちらもItuneStoreのランク上位
　　・ECC　英会話
　　・ポッド de モット　英会話

★ＥｖｅｒＮｏｔｅを使ってみる

ＥｖｅｒＮｏｔｅ：最高のオンラインメモツールらしい

【特徴】
　１．画像やWebクリップなども保存できる(IPhoneからも)
　２．Webアプリケーションとして閲覧や書き込みができ，
　　　それらは，Windows 版やMac OS版、Windows Mobile版、iPhone版など
　　　どんなデバイスでメモを取っても自動的に同期される


アカウントを作成し，macかwinか選択してダウンロード

・NOTEを作成，一番上がタイトル，タグをつけ管理
・写真でも英語文字で検索可能
・NOTE，写真，PDFなど
・ネット上で同期
・無料アカウントはUPが１月に40Mまで
・IPhoneから写真撮影するだけで同期
・1時間ごとに同期をとる（変更可能？

------------------------------------
DropBoxも使ってみたい！

------------------------------------

余談やけど，
マイミクへお勧めのコミュニティ教える機能って，
教えたら，mixiのメッセージへ
「おすすめのコミュニティが１件あります」
みたいに表示されるのかと思ったら，
普通にメールアカウントの方へくるのね．
なんか，びみょーにもにょるね