米事案と路地狩るプログラミング

semantic netの試験対策のためのノート

2008-07-14T14:54:00.011+09:00

sentence: "I know what I like and I like what I know."

I.
Q1) frame size = 5の語彙共起行列

	I	know	what	like	and
I	null	6	3	7	5
know	3	null	3	3	1
what	6	3	null	6	4
like	7	3	6	null	5
and	5	1	4	5	null

Q2)frame size = 5, radius = 2の共起頻度行列（IAWではなくKey-Word Based）


	I	know	what	like	and
key:I		3	4	4	2
key:know	3		2
key:what	3	2		2
key:like	4		2		2
key:and	2			2

Q3) Q2の共起頻度行列から得られる重みなし無効グラフと隣接行列

	I	know	what	like	and
I	0	1	1	1	1
know	1	0	1	0	0
what	1	1	0	1	0
like	1	0	1	0	1
and	1	0	0	1	0

III.
Q1) ４ノードからなる完全グラフと隣接行列

	node1	node2	node3	node4
node1	0	1	1	1
node2	1	0	1	1
node3	1	1	0	1
node4	1	1	1	0

Q2) Q1の辺の数：3+2+1 = 6

Q3)
完全グラフなので、４つのノードから考えられる3-クリークの数と実際のグラフに存在する3-クリークの数は一致する。
よってcurvature = 1である。

Q4) danglingノードが６つのスターグラフと隣接行列

	node1	node2	node3	mpde4	mpde5	node6	node7
node1	0	1	1	1	1	1	1
node2	1	0	0	0	0	0	0
node3	1	0	0	0	0	0	0
node4	1	0	0	0	0	0	0
node5	1	0	0	0	0	0	0
node6	1	0	0	0	0	0	0
node7	1	0	0	0	0	0	0

Q5) スターグラフでは、3-クリークが一つも存在しないのでcurvature = ０である。

Q6) ノード１の次元は６、それ以外のノードの次元は１である。

III.
Q1)
cos similarity を計算する関数の定義（Rでの関数定義）

cos_value <- function(a,b){
inner_product_ab <- sum(a*b)
norm_a <- sqrt(sum(a*a))
norm_b <- sqrt(sum(b*b))
product_norm_ab <- norm_a*norm_b
cos_val <- inner_product_ab/product_norm_ab
cos_val
}

cosmonauteとastronauteのcos similarityを計算。
cosm <- c(8,9,4,1,10)
astr <- c(10,8,3,8,2)
cos_value(cosm,astr)
[1] 0.7640857 Q2)

IIIの表から得られる二部グラフと隣接行列。

	cosmonaute	astronaute	space	ship	rocket	NASA	Soviet
cosmonaute	0	0	1	1	1	1	1
astronaute	0	0	1	1	1	1	1
space	1	1	0	0	0	0	0
ship	1	1	0	0	0	0	0
rocket	1	1	0	0	0	0	0
NASA	1	1	0	0	0	0	0
Soviet	1	1	0	0	0	0	0

Q3)
２部グラフの定義：
グラフG = (V,E) について以下のことが成り立つとき、Gを二部グラフと呼ぶ。

頂点集合V1,V2を以下のように定義する。
このとき、V1の任意の２つ頂点間に辺が存在しない、かつV2の任意の２つの頂点に辺が存在しないなら、Gは二部グラフである。

V = V1∪V2 (V1∩V2 = φ：空集合)
（このようなV1,V2を独立点集合という）

if
∀ei, ej ∈ V1 , ∉ E
∀es, et ∈ V2, ∉ E

then G is bi-patite graph.

二部グラフの特徴:

n部グラフはn色彩色可能（定理）　→　２部グラフは２色彩色可能
奇閉路が存在しない

III
Q1) だいたいwikipediaに書いてある。
http://ja.wikipedia.org/wiki/%E6%BD%9C%E5%9C%A8%E6%84%8F%E5%91%B3%E8%A7%A3%E6%9E%90

Q3)
絵画に画像解析を行い、絵画の特徴を自然言語を用いて語るという研究がある。
これは、人間は絵画を見ることで感じる”印象”を自然言語で語っていることに注目した研究である。
具体的には、絵画の様々な画像情報と用意された印象語との対応をコンピュータに解析・学習させるというものである。

ここで、このアプローチを私なりにさらに改良したものを提案する。
先攻研究では、印象語をあらかじめ用意していた。
しかし、この印象語が絵画を語るのに十分である保証はない。
そこで、私は以下に述べることを提案する。

先攻研究では絵画の特徴を規定の印象語の尺度で語って終わりであった。
私の提案する方法は、絵画の特徴を自由な印象語で語り、さらにその印象語がもつ潜在的な意味を大規模コーパスから見いだすものである。
この方法により、先攻研究の手法よりさらに言語の持つ特徴を利用した解析が行えるのではないかと期待する。

Q3)
言語の意味を語るものは言語である。
これは終わりのない再帰的な関係である。
仮に終わりがあるのであれば、言語全体を語るのに十分な基底ベクトルのような言語が存在することになる。
ここで、この基底ベクトルを基底言語と呼ぶことにする。
私は、この基底言語の集合の部分集合が意味なのだと考える。
つまり、言語とは基底言語の部分集合族のようなものと考えるわけである。
基底言語集合が有限であるのか無限であるのかは分からない。
また、基底言語が自然言語として存在しているのかどうかも分からない。
しかし、私はこのような基底言語が存在することを信じている。

エルブラン解釈

2008-07-11T14:19:00.005+09:00

先々週くらいに生協で見つけて思わず買ってしまった”新・人工知能の基礎知識（太原育夫）”という本がとてもGoodです。
人工知能における探索、論理、知識、仮説推論、準矛盾推論について、具体例を豊富にあげながらわかりやすく書いてあります。

そして、いままで全くもって理解できなかったエルブラン解釈というものが少し理解できた気がします。

わかった気になっているうちに、なんとなくでもわかったことを書いておきたいと思います。

述語論理の意味論における解釈
命題論理では、論理式の意味はその論理式が真であるのか偽であるのかであった。
述語論理でも同様に、述語論理における論理式の意味はその論理式が真であるか偽であるかある。

命題論理では原始式に真偽の割当てを行い、論理式が充足可能であるかどうかを判定する。
述語論理では原始式ではなく変数を扱う述語に真偽の割当を行い、論理式（節集合）が充足可能であるかどうかを判定する。
また、述語以外に関数記号、個体定数、個体変数にたいしても割当を決めなければいけない。
述語論理では、これらの割当のことまとめ解釈と呼ぶ。

領域のすべての要素について、あらゆる解釈のもとでの節集合の充足可能性を判断すれば、節集合の充足可能性は判定できる。

ここで、充足不能性を証明する事を考える。
説集合があらゆる解釈の上で充足不能であることを証明できるば、その節集合は充足不能であるが、これは事実上不可能である。

しかし、少なくとも充足不能性を示すために十分な対象領域が存在する。
それがエルブラン領域である。

エルブラン領域におけるエルブラン解釈を節集合に行い充足不能性が示されれば、その節集合の充足可能性を示した事と等しくなる。

以上が、述語論理におけるエルブラン解釈が必要（？）な理由です。

なぜ十分なのかはわかりません。
べつにそこまでわかりたいとも思いません。

とにかく、エルブラン領域・定理というのが何なのかがすこしでも理解できてよかったです。

Combining Probability and Logic with ICL, PRISM and SLPs

2008-07-09T18:35:00.017+09:00

"Integrating by Separating: Combining Probability and Logic with ICL, PRISM and SLPs"
James Cyssens
Department of Computer Science
University of York
January 25, 2005

PRISMのコード付きで文章が書かれている論文だったので興味本位で読んでみました。
主な内容は、以下の３つの確率的論理プログラミングの関係についてでした。
ちなみに古くから発表されているICLというのは初耳でした。

The independent statistical logic (ICL) [Poole,1993b,1997]
Programming in statistical modelling (PRISM) [Sato,1995; Sato & Kameya,2001]
Stochastic logic programs (SLPs) [Muggleton,1996; Cussens,2001]

論文のはじめに、佐藤先生により要約されたICLとPRISMの明白なbasic ideaが紹介されていました。要約内容は、

論理プログラムDBは、事実(fact)の集合Fと規則(rule)の集合Rの和集合からなる集合
DB = F∪R である。

Fにより同時分布P_Fが与えられるとき、Rを用いてこれをDBの最小モデル集合上の同時確率P_DBへと拡張できる。

ふむ、とりあえずICLとやらもPRISMのような分布意味論を基礎としたフレームワークらしいです。

論文では、ICLとPRISMをHMMの具体的な例をあげながら解説しています。
両者が基礎とする分布意味論（ICLでは分布意味論とは言わないのかな？）をどう表現しているのかを比較しながら話は進んでいきます（ほぼPRISMメイン）。
しかし、話題がサンプリングの話になってからよくわからなくなってしまいました。

ICLとPRISMの話が終わるとSLPsの話です。
SLPsは、Uniqueness Conditionを自動的に保証するICL/PRISMモデルの特殊なケースと考えられると言ってます。
論文には、SLPsでPRISMのプログラム（HMM）をシミュレートするコードが紹介されてます。
あとの話はよくわかりません。

読み終えての感想は、やっぱりSLPsはよくわからない！ということです。
PRISMやICLは確率空間と確率測度を明確にしてコルモゴロフの公理に基づく確率を扱っていることを明白にしてる感じがしますが、SLPsは全然そんな気がしません。

SLPsで扱っている”確率”って何なのでしょうか？
”０〜１の値をとる単なる重み”にしか感じません。
ちゃんとそこんとこは説明されてるんでしょうか？

とにかく、分布意味論の良さを確認できた気がしますので、これから分布意味論についてちゃんと理解したいと思います。

古川先生の「帰納論理プログラミング」講義資料を読んで

2008-07-04T14:44:00.010+09:00

途中何度か寝そうになりながら、昨日落としてきた古川先生の帰納論理プログラミングの講義資料をさっと読みました。
とりあえず、イメージは分かりました。

しかし、本題の帰納論理プログラミングよりも、最後の講義資料に載っていた”確率と述語論理の融合”でまとめられていた資料が目に留まりました。

「ベイジアンネットワークの表現力の向上」

KBMC (Knowledge-Based Model Construction)

CPTの構築にPrologを使い、述語論理の表現力をBNへ。
節の含意部に確率を与える。
意味論も確率空間もない　→　あくまでBNの構造とCPTの構築のために述語論理を用いる。

SLP (Stochastic Logic Programimng)

確率文脈文法の拡張。
節の含意部に確率を与える。
確率空間の議論がない。
論理式の証明に確率を割り当てたので、意味論的に問題が多い。(exp. P(A∧A)≠P(A)となる可能性がある)

PRISM (Programing in Statistical Modeling)

最初から単一の確率空間を構成して、その上で論理式の確率を議論する立場をとる。
論理プログラムの意味論の確率的拡張を与える。

KBMCのアプローチだと、基本的に確率空間をあらかじめ定義することはないそうです。
あくまで知識の表現としてだけに述語論理を用いて、確率を語るためには一度確率的命題論理（BNなど）を構築する必要があると思って間違いはないでしょうかね。
Bayesian Logic ProgramやLogical Bayesian NetworksもKBMCの立場からのアプローチなので、確率空間を考えたりはしてないんですね。

個人的には、PRISMやProbLogのような確率空間をあらかじめ定義するような手法の方が理解しやすいです。
たぶん、実際にPRISMでプログラムを書いたことがあるからでしょうけど。
とりあえず、ProbLogにさらに興味を持ってきたのでさらに勉強してみたいです。

帰納論理プログラミング(Inductive Logic Programming)

2008-07-03T18:08:00.008+09:00

帰納論理プログラミング(ILP)を勉強したいのですが、Googleスカラーで見つかる特集記事が難しくて困ります。

いろいろ探していたら、慶応の古川先生の”帰納論理プログラミング”という講義の講義資料を発見。
これを使えばきっと基礎は分かるんだと信じます。

ProbLog: A Probabilistic Prolog and its Application in Link Discovery

2008-07-03T12:25:00.007+09:00

"ProbLog: A Probabilistic Prolog and its Application in Link Discovery"
Luc de Raedt, Angelika Kimming and Hannu Toivonen
Machine Learning Lab, Albert-Ludwigs-University Freiburg, Germany
(IJCAI-07)

ProbLogという確率的Prologの紹介。
Stochastic Logic Programmings(SLPs)、PHA、PRISM、probabilistic Datalog(pD)との違いを述べている。
PHAとpDはまだ見た事がなかったので早速調べてみたいと思う。

何となく分かった事は、他の確率的論理プログラミングとは違い、すべてのclauseに対してtrueになる確率を付与していることらしい。
Bayesian Logic Programming(BLP)などでは、確率的なprobabilisitic clauseと決定的なlogical clauseという２つの（本当は３つくらいあったかも）clauseを区別して考えている。
ProbLogでは、clauseがtrueになる確率を１にすることでlogical clauseを表現できる。

ProbLogでは、clauseの確率計算をDNFを通して行う。
DNFを使った確率計算の効率化のためにbinary decision diagrams(BDD)というものを利用するらしい。

あまり詳しく読んでいないから、実際のプログラムをどのように書けばいいのかがわかりません。
ProbLogを使って既存の確率モデル(BNとか)をどう表現できるのかをコード付きで説明してもらえるとうれしいです。

論文を読んでみる感じでは、そこそこ変数の数が大規模なデータでも動くらしいのでもう少し勉強してみたい。

PROLOG Programming for Artificial Intelligence

2008-07-01T16:14:00.004+09:00

"PROLOG Programming for Artificial Intelligence (third edition)"
Ivan Bratko

先週、AmazonでPrologについての本を探していたら見つけた本です。
先生におねだりして買ってもらいました。

Prologの基本的なプログラミング作法から、人工知能分野でホットな技術まで幅広く網羅してます。
Constraint Logic Programming、Machine Learning、Inductive Logic Programming、Bayesian Networkなどがソコード付きで解説されてます。

ちょこちょこ読んでますが、とってもおもしろいです。
Prologを使った研究をしたいと思わされます。

この本を読んで、どのようにベイズ統計と絡めていくかを具体的に模索してきたいです。

研究用ブログ

2008-07-01T16:04:00.002+09:00

研究資料の記録用にブログ開設しました。

研究のモチベーション維持のためにもまめに更新していきたいものです。