PowerPoint プレゼンテーション

Prologによる意思決定と情報のモデル
犬童健良
関東学園大学経済学部
Email: [email protected]
http://www.us.kanto-gakuen.ac.jp/indo
2015/9/30
2
Prologによる意思決定のモデリング
Prologの特徴


論理学・自動定理証明技術に基礎を置くプログラミング言語
知識処理・AIシステム作成の代表的手段..だった
モデリングツールとしてのProlog



論理や離散的領域（AIシステム）のモデリングに適す
再帰的なコード化スタイルは、DPの考え方にもなじむ..はず
数学的ユーティリティを作成可能
意思決定の理論モデルへの応用



社会選択・ゲーム理論（メカニズムデザイン）
動学的最適化のモデリング
情報システムのモデリング
具体的なモデリング例

決定木分析、最適探索、線形代数、協力ゲーム、信念関数、最短
路アルゴリズム、関係代数など
2015/9/30
3
本研究の目標とアプローチ
知りたいこと：

動的最適化や不完全情報を含む意思決定のモデリング

それはいかなる知的作業なのか？（背景となる認知科学的関心）
H.A.Simonの人工物デザイン
C. Levi-Straussの具体の科学
J. Piagetの具体的操作段階の知能

Prologはそのためのツールとして使えるか？（今回の作業目標）
 離散的な領域以外でもうまく使えるのか？


OR/経営科学の古典的手法が含むもの：
確率・期待値、資源配分、行列演算、最適化
アプローチ：以下の３＋１ステップ
ステップ０：モデルやモデリングの概念を自分なりに整理してみる
ステップ１：モデル記述言語の満たすべき条件を考える
ステップ２：実際に作ってみよう！実際にはこれを先に実行した
ステップ３：モデル事例から一般化できそうなことを探す
2015/9/30
4
意思決定のモデリング例
数理計画モデルの例
=10
目的関数
x+y+2z →最小化
制約条件
x≦ 5,
y + z ≦ 10,
z ≧ 3,
x + y = 10
y
x
≦5
≦10
非負条件
x ≧ 0,
y ≧ 0,
z ≧ 0,
z
≧3
図．例題の直観的意味に対応する
ネットワーク（輸送問題）
2015/9/30
5
意思決定のモデリング（規範的）
モデリングーーー意思決定の問題やその解法をデ
ザインする一連の知的作業
(1) 意思決定プロセスの入出力である代替案とその属性
（＝評価）を含むデータ形式を決める。
(2) 適切な選択基準の下で最善案集合（＝解）を選択する。
(2.5)以上のことを思考し、適切なデザインを決める。それ自
体が再帰的。
モデリングを支援する情報システムの満たすべき条
件ーーーブラックボックス化の回避
(3) 当該領域の規範的エキスパートシステムないしDSSとし
て機能すること。つまりシステム自身が、意思決定問題を
解く能力を有すること。
(4）モデルベースとしての再利用や拡張性を有すること、
(5）対話的作業誘導のみならず、モデルの説明・解釈、ある
いはモデリングエラーを診断・助言ができること。
2015/9/30
6
Prologによるモデリング例
実行すると3通りの解が求
まる。セミコロン；でバックト
ラック（別解探索）する。
前出の例題を、整数値に制限した問題を
Prologでモデリングすると以下のようにな
る。
feasible_plan([X,Y,Z],Cost):member(X,[0,1,2,3,4,5]),
Y is 10 - X,
member(W,[0,1,2,3,4,5,6,7,8,9,10]),
Z is W - Y,
Z >= 3,
Cost is X + Y + 2 * Z.
optimal_cost(Plan,Cost):feasible_plan(Plan,Cost),
\+ (
feasible_plan(_P,C),
C < Cost
).
?- optimal_cost(A,B).
A = [3, 7, 3]
B = 16 ;
A = [4, 6, 3]
B = 16 ;
A = [5, 5, 3]
B = 16 ;
No
2015/9/30
7
比較：表計算ソフトとソルバーによるモデリング
2015/9/30
8
Prologによるモデリングとそのメリット
(1) 代替案とその属性：節形式ないしリストで表現する。
(2）解・選択基準：対応するルール節を作成する。
(3) 解の計算・シミュレーション： (2)をゴールとして実行する。
可能解や必要条件を満たす部分解をバックトラックで生成
できる。つまりモデリングがシミュレーションに直結し、この
ため数学的直観だけでなく、「具体的操作」に基づくモデリ
ングが可能。
(4) 拡張性・再利用性：再帰性ゆえ問題サイズに対する処
理変更は不要。節形式で表現されたモデルは新しいモデ
ルを作成するときの参考になる。また選択基準の強化や
変更も、ルールの追加・変更で対処できる。
(5) 誤り診断・知的モデリング支援：コード自体が２進決定
木と見なせるので、比較的モデリングの誤りを発見しやす
い。またその診断プロセスをプログラム化することも可能と
思われる。
2015/9/30
9
アプローチ（詳細レベル）
ステップ１：モデル記述言語の満たすべき条件
Prologはその候補としてEligibleだと思われる。


モデルが、数式や論理式や日常言語に近い形で、知識表現可能。
だが、できるだけ意味論が厳密な（準）形式的システムがよい。
つまり、作成過程のモデルは、それ自体が「形式的に」可読であること。

かつ事例の自動生成などを通じて、適宜、具体的操作により検証・修正で
きること。
 つまり、モデリングとシミュレーションがシームレスないし相互反復的。
ステップ２：実際に作ってみた。（今回できたのはここまでです）
Prologによるモデリングケース作成
まず、規範的解法の知られるタイプの問題を選んだ。

ただしいくつかの異なるタイプの問題で、緩やかに重なりのあるもの。

実際に、短期間で、Prologで、モデリングしてみた。
ステップ３：一般化できそうなこと。（残されたこと）

例からの帰納。（Prologや導出原理はアドホックなAIから帰納された？）


作成されたモデル間の共通性や差異をどのように抽出できるか？
モデリング作業そのものをPrologによってコード化できるか？
2015/9/30
10
デバッグ・テスト段階の評価基準
各プログラムの開発段階の評価基準は次のようである。なお今回は、段
階Aを目標とした。
S: 要求仕様の複雑性に照らして、必要十分なテストデータを実験計画
して動作確認済みである。
A: 目的の機能を実現し、例題の解を正しく求めており、現在までのとこ
ろ、とくに直すべきところは見当たらない。
B: 目的とする主な機能を実現し、例題に対し正しく動作するが、拡張的
なコード部分が未完成または致命的でない小さなミスがいくつかある。
C: 一応コーディングは完成したが、検証が不順分であり、一部に軽視で
きない誤動作が見つかっている。
D: 試作段階で設計上の問題が残っており、コーディングの完成に至ら
ないでいる。
2015/9/30
11
モデリング事例
１．決定木分析：dtree0.pl
２．最適停止（サーチ）：pjtsea.pl
３．信念関数：belief0.pl
４．協力ゲーム：coop.pl
５．線形代数：matrix1.pl
６．最短路アルゴリズム：traveler.pl
７．関係代数：rdb01.pl
８．その他
 集合・リストの操作：set.pl
 算術・確率モデル：math1.pl
 乱数発生（モンテカルロ法）：mcpi.pl
2015/9/30
（事例１）決定木分析：dtree0.pl
12
デバッグ・テスト段階の評価基準：
S: 要求仕様の複雑性に照らして、必要十分なテストデー
タを実験計画して動作確認済みである。
A: 目的の機能を実現し、例題の解を正しく求めており、現
在までのところ、とくに直すべきところは見当たらない。
B: 目的とする主な機能を実現し、例題に対し正しく動作す
るが、拡張的なコード部分が未完成または致命的でない小
さなミスがある。
C: 一応コーディングは完成したが、一部に軽視できない誤
動作が見つかっている。
D: 試作段階で設計上の問題が残っており、完成に至らな
いでいる。
手法の特徴：決定木によるリスクのある投資案の評価・選択。
開発データ：

期間：21-22 Feb 2003.

ステップ数：約400行。 pjtsea.plから分離。その約半分は共通ユーティリティから。

デバッグレベル： A
主な機能・述語：

決定木に対応する投資案の表現 decision_tree /3

時間割引後期待利得 npv / 4, expected_value_of /3

ロールバック（後方機能推論）による最適パス roll_back /3, is_an_optimal_path /3
その他：標準的な意思決定分析。ロールバックはその計算式を表示する。確率や期待値のユーティリティ使用。
?- expected_value_of(node(a),B,C).
% an example of decision tree
%----------------------------------------------------decision_tree(node(r),parent(null),choice([node(a),node(b)]),delay([0,0])).
decision_tree(node(a),parent(r),chance([node(c),node(d)]),prob([0.5,0.5])).
decision_tree(node(b),parent(r),choice([node(e),node(f)]),delay([0,1])).
decision_tree(node(f),parent(b),chance([node(c),node(e)]),prob([0.2,0.8])).
decision_tree(node(c),payoff(10)).
decision_tree(node(d),payoff(0)).
decision_tree(node(e),payoff(4)).
interest_rate(1.1).
?- figure(1).
%
r
a
0.5
%
-------[ ]--------------( )--------* c(10)
%
|
|
%
|
0.5|
%
b|
e
* d(0)
%
[ ]------* e(4)
%
|
%
f|
0.2
%
( )------* c(10)
%
|
%
0.8|
%
* e(4)
%
% Figure 1. a decision tree.
図１－１．決定木による意思決定問題の表現
B = 0.5*0+0.5*10
C=5
Yes
?- expected_value_of(node(b),B,C).
B = 1.1^ (-1)* (0.8*4+0.2*10)
C = 4.72727
Yes
?- roll_back([r|A],B,C),C=[D|_], E is D.
A = [a, c]
B = [choice, chance, terminal]
C = [0.5*0+0.5*10, 0.5*10, 10]
D = 0.5*0+0.5*10
E=5;
A = [a, d]
B = [choice, chance, terminal]
C = [0.5*0+0.5*10, 0.5*0, 0]
D = 0.5*0+0.5*10
E=5;
No
図１－２．ロールバック解の計算
2015/9/30
13
決定木の期待利得の再帰的計算（事例1）
expected_value_of(node(N),E,V):decision_tree(node(N),payoff(E)),
V is E.
expected_value_of(node(N),Eq,V):decision_tree(node(N),_,_,_),
expected_value_of_0(node(N),Eq,V).
decision_tree(node(r),parent(null),choice([node(a),node(b)]),delay([0,0])).
decision_tree(node(a),parent(r),chance([node(c),node(d)]),prob([0.5,0.5])).
decision_tree(node(b),parent(r),choice([node(e),node(f)]),delay([0,1])).
decision_tree(node(f),parent(b),chance([node(c),node(e)]),prob([0.2,0.8])).
decision_tree(node(c),payoff(10)).
decision_tree(node(d),payoff(0)).
decision_tree(node(e),payoff(4)).
expected_value_of_0(node(N),Eq,V):decision_tree(node(N),parent(_),choice(C),delay(_F)),
optimal_choice(C,_Y,Eq,V),
!.
optimal_choice(Y,X):optimal_choice(Y,X,_EqV,_V).
optimal_choice([X],X,EqV,V):-
expected_value_of_0(node(N),Eq,V):decision_tree(node(N),parent(_),chance(X),prob(P)),
findall(U1,
(
member(B,X),
expected_value_of(B,U1,_)
),
U),
p_expected_value_eq(P,U,_,Eq0),
npv_of_node(N,_A,Eq0,Eq),
V is Eq.
expected_value_of(X,EqV,V).
optimal_choice([X|Y],Z,Eq,V):optimal_choice(Y,Z1),
expected_value_of(Z1,Eq1,_V1),
expected_value_of(X,EqX,Vx),
V is max(EqX, Eq1),
(Vx >= V -> Z = X; Z = Z1),
(Vx >= V -> Eq = EqX; Eq = Eq1).
2015/9/30
（事例２）最適停止（サーチ）：pjtsea.pl
14
手法の特徴：サーチ順序の最適化。Weitzman(1979)の２つの例題。
開発データ：



期間：12-25 Feb 2003.
ステップ数：約千行。ただし４００行ほどはdtree.pl と共通。
デバッグレベル： A(-)
主な機能・述語：

例題1：R&D投資。研究開発プロジェクトの順序を最適化。 expected_value_of /3, roll_back /3 （dtree.pl）

例題２：パンドラの箱。留保水準を用いた最適停止ルール sfp /8.
その他：期待値はユーティリティ p_expected_vale_eq /4 他を利用。乱数発生は使わない。ちなみに相対ランクによるサーチは別途
作成（sea2.pl）。
% example of R & D projects (Weitzman,1979)
%--------------------------------------------project(alpha,
cost(15), duration(1), reward([100,55]), probability([0.5,0.5])).
project(omega,
cost(20), duration(2),
reward([240,0]),
probability([0.2,0.8])).
interest_rate(1.1).
?- expected_value_of(node(A->M),B,C).
A = alpha
M = omega
B = 0.5* (- (15+1.1^ (-1)*20)+1.1^ (-3)* (0.8*55+0.2*240))+0.5* (-15+1.1^ (-1)*
(0*55+1*100))
C = 55.9241 ;
A = omega
M = alpha
B = 0.8* (- (20+1.1^ (-2)*15)+1.1^ (-3)* (0.5*55+0.5*100))+0.2* (-20+1.1^ (-2)*
(0*0+1*240))
C = 56.3336 ;
No
?-
sfp(DR,L,Y,A,S,M,Csq,E,V):search_for_projects(DR,L,Y,A,S,M,Csq,E,V).
% DR: Decision rule, ( pandora)
% L : List of projects for search.
% Y: Total time of search,
% A: history of Accept or not,
% S: Seqence of sampled projects,
% M: Memory of sampled values,
% Csq: Sequence of cumulative sampling costs,
% Esq: Expected values of realized projects,
% V: Values of numerical evaluation of current decision.
%-------------------------------------------------------?- sfp(pandora,L,Y,A,S,M,Cq,Eq,V).
< - - omit : several steps of backtrack - - >
L = [box(1), box(2), box(3)]
Y=4
A = [box(3), box(3), non]
S = [box(1), box(3), box(2)]
M = [ (4, 2, 0, 0.5), (3, 1, 100, 0.5), (2, 2, 0, 0.8)]
Cq = [20+30+15, 20+30, 20]
Eq = [0, 100, 0]
V = -65 ;
No
図２－１．研究開発プロジェクト選択問題
図２－２．パンドラ問題（最適停止）のシミュレーション
2015/9/30
15
サーチ問題の決定木への埋め込み
（事例2）
% example of R & D projects
(Weitzman,1979)
%--------------------------------------------project(alpha,
cost(15),
duration(1),
reward([100,55]),
probability([0.5,0.5])
).
project(omega,
cost(20),
duration(2),
reward([240,0]),
probability([0.2,0.8])
).
decision_tree(node(r),parent(null),
choice([node((alpha->omega)),node((omega>alpha))]),delay([0,0])).
decision_tree(node((G1->G2)),parent(r),chance(Z),prob(P)):order_of_projects((G1->G2)),
project(G1,_,_,_,probability(P)),
A = resolved(G1,_,_,_V1),
B = option((G2/A)),
C = or(A,B),
findall(node(C),(project(A,_,_,_,_)),Z).
decision_tree(node(C),parent((G1->G2)),choice(X),delay([0,0])):A = resolved(G1,_,_,_V1),
B = option((G2/A)),
C = or(A,B),
order_of_projects((G1->G2)),
decision_tree(node((G1->G2)),parent(r),chance(Z),prob(_)),
member(node(C),Z),
X = [node(A),node(B)].
decision_tree(node(D),payoff(Eq)):A = resolved(G1,_,_,_V1),
B = option((G2/A)),
C = or(A,B),
decision_tree(node(C),parent((G1->G2)),choice(X),delay(_)),
member(node(D),X),
expected_value_of(project(D),Eq,_V).
2015/9/30
16
（事例３）信念関数：belief0.pl
手法の特徴： Shafer(1976)の信念関数と可能性関数、およびDempster-Shaferルールによる更新。
開発データ：



期間：27 Feb - 1 Mar 2003. （前年秋に作りかけたが、今回全面的に作り直しした。）
ステップ数：約1100行。ただし２００～３００行ほどは実行サンプルなど。また共通ユーティリティは１５０行ほど引用。
デバッグレベル： A
主な機能・述語：

基本確率割当（マス）
bpa0(A,B), mass(A,B,C)（反転公式による）

信念関数、可能性関数 sbel(A,B,C), spos(A,B,C)

信念更新 update_mass /3, update_sbel /3, update_spos /3 , update_bel_ul /3, etc.
その他：確率論でない不確実性推論モデル。凸ゲームと関係。あいまい確率下の意思決定に応用。
% example 1. Ellsberg 3 color problem
% (Gilboa and Schmeidler, 1993, p.36)
%--------------------------------------------------states([r,b,y]).
% Basic probability assignment
bpa0([],0).
bpa0([r],1/3).
bpa0([b,y],2/3).
?- sevent(A),mass(A,B,C),bpa(A,D).
A = [r]
B = 1/3* -1^0
C = 0.333333
D = 1/3 ;
A = [b]
B = 0* -1^0
C=0
D=0;
A = [y]
B = 0* -1^0
C=0
D=0;
(continued)
?- update_sbel(A/[b,y],_,B).
A = [b, r]
B = 1/3* -1^1+ (1/3+0)* -1^0+0* -1^1
C=0
D=0;
A = []
B=0;
A = [r, y]
B = 1/3* -1^1+ (1/3+0)* -1^0+0* -1^1
C=0
D=0;
A = [b]
B=0;
A = [b, y]
B = (2/3+0)* -1^0+0* -1^1
C = 0.666667
D = 2/3
A = [b, r, y]
B = 1/3* -1^2+ (2/3+0)* -1^1+ (1/3+0)* 1^1+ (2/3+1/3+0)* -1^0+0* -1^2
C = 0.333333
D = 1/3 ;
No
A = [r]
B=0;
A = [y]
B=0;
A = [b, r]
B=0;
A = [r, y]
B=0;
A = [b, y]
B=1;
A = [b, r, y]
B=1;
?- sevent(A),
update_bel_ul(A/[b,y],_,B).
A = []
B=0;
A = [r]
B=0;
A = [b]
B=0;
A = [y]
B=0;
A = [b, r]
B=0;
A = [r, y]
B=0;
A = [b, y]
B=1;
A = [b, r, y]
B=1;
No
No
図３－１．Ｅｌｌｓｂｅｒｇ背理に対応する基本確率割当
図３－２．ＤＳルールとＵＬルールによる信念更新
2015/9/30
17
（事例４）協力ゲーム：coop.pl
手法の特徴：協力ゲーム、すなわち提携構造と特性関数の下でのコア、仁、Ｓｈａｐｌｅｙ値などの解概念
開発データ：



期間：7 - 9 Feb 2003. コード化は1日で完了。9日にサンプル実行をコメントに追加。
ステップ数：600行弱。コメントを含めて本体は３００行強。残りは共通ユーティリティからの引用。
デバッグレベル： A
主な機能・述語：




提携形ゲーム（特性関数） game(G,value,X,P)
全体合理性、配分、コア col_rat_outcome /3, imputation(G,C,P), core(G,C,P)
シュメイドラーの仁 nucleolus(G,A) 不満の少なさを辞書式順序(@>)で最適化
シャプレー値 shapley(G,N,V)
その他：各種解概念は、定義に対して率直。ただし提携利益の分配案は共通ユーティリティ allocation /3 を用いた格子点近似。
% game c2: Who does a ought to sell, to b or to c?
game(c2, form(characteristic), players([a,b,c]),
coalitions([[],[a],[b],[c],[a,b],[b,c],[a,c],[a,b,c]])).
game(c2,value,[],0).
game(c2,value,[a],0).
game(c2,value,[b],0).
% coa is not empty if modified as below
%game(c2,value,[a],1).
%game(c2,value,[b],1).
game(c2,value,[c],0).
game(c2,value,[a,b],2).
game(c2,value,[b,c],0).
game(c2,value,[a,c],5).
game(c2,value,[a,b,c],5).
core(game(G),players(N),payoff(A)):imputation(game(G),players(N),payoff(A)),
\+ coalitionally_complain(G,_/N,_Y-_Y=_/A,yes).
?- core(game(c2),B,C).
B = players([a, b, c])
C = payoff([5, 0, 0]) ;
B = players([a, b, c])
C = payoff([4, 0, 1]) ;
B = players([a, b, c])
C = payoff([3, 0, 2]) ;
B = players([a, b, c])
C = payoff([2, 0, 3]) ;
No
図４－１．取引ゲームｃ１とそのコア
% game c1: majority vote.
game(c1,
form(characteristic), players([a,b,c]),
coalitions([[],[a],[b],[c],
[a,b],[b,c],[a,c],[a,b,c]])).
game(c1,value,[],0).
game(c1,value,[a],0).
game(c1,value,[b],0).
game(c1,value,[c],0).
game(c1,value,[a,b],1).
game(c1,value,[b,c],1).
game(c1,value,[a,c],1).
game(c1,value,[a,b,c],1).
%
% game c3: cost-sharing problem.
game(c3,
form(characteristic), players([a,b,c]),
coalitions([[],[a],[b],[c],
[a,b],[b,c],[a,c],[a,b,c]])).
game(c3,value,[],0).
game(c3,value,[a],0).
game(c3,value,[b],0).
game(c3,value,[c],0).
game(c3,value,[a,b],6).
game(c3,value,[b,c],8).
game(c3,value,[a,c],0).
game(c3,value,[a,b,c],20).
図４－２．多数決ゲームｃ１と費用分担
ゲームｃ３
?- is_more_acceptable_than(c3,
[12,4,4],[6,0,14],B,C).
B = [0, 0, -4, -4, -10, -12, -16]
C = [0, 0, 0, -6, -6, -14, -20]
Yes
?- nucleolus(A,B).
A = c1
B = [1, 0, 0] ;
A = c1
B = [0, 1, 0] ;
?- shapley(A,B,C),
col_rat_outcome(A,_,payoff(
C)).
A = c1
B = [a, b, c]
C = [0.333333, 0.333333,
0.333333] ;
A = c2
B = [a, b, c]
C = [2.83333, 0.333333,
1.83333] ;
A = c1
B = [0, 0, 1] ;
A = c3
B = [a, b, c]
C = [5, 9, 6] ;
A = c2
B = [3, 0, 2] ;
No
A = c3
B = [6, 7, 7] ;
No
図４－３．Ｓｃｈｍｅｉｄｌｅｒの仁
図４－４．Ｓｈａｐｌｅｙ値
2015/9/30
18
協力ゲームの解（仁）（事例４）
% Schmeidler(1969)'s nucleolus
% ------------------------------------------------- %
% lexicographically minimizing the sorted complaining
vector.
complain_vector(G,A,Zs):imputation(game(G),players(N),payoff(A)),
findall(Z,coalitionally_complain(G,_B/N,_=Z/A,_),Zs).
complain_vector_indexed(G,A,Bs):imputation(game(G),players(N),payoff(A)),
findall((B,Z),coalitionally_complain(G,B/N,_=Z/A,_),Bs).
sorted_complain_vector(G,A,Z):complain_vector(G,A,S0),
asort(S0,S),
reverse(S,Z).
is_more_acceptable_than(G,A,A1):is_more_acceptable_than(G,A,A1,_,_).
is_more_acceptable_than(G,A,A1,Z,Z1):sorted_complain_vector(G,A,Z),
sorted_complain_vector(G,A1,Z1),
Z @< Z1.
nucleolus(G,A):imputation(game(G),players(_N),payoff(A)),
\+ is_more_acceptable_than(G,_A1,A).
% sample execution
%-----------------------------------------------------?- is_more_acceptable_than(c3,[12,4,4],[6,0,14],B,C).
B = [0, 0, -4, -4, -10, -12, -16]
C = [0, 0, 0, -6, -6, -14, -20]
Yes
?- nucleolus(A,B).
A = c1
B = [1, 0, 0] ;
A = c1
B = [0, 1, 0] ;
A = c1
B = [0, 0, 1] ;
A = c2
B = [3, 0, 2] ;
A = c3
B = [6, 7, 7] ;
No
?-
2015/9/30
19
（事例５）線形代数：matrix1.pl
手法の特徴：行列と線形代数の基礎。単位行列、各種演算、ガウスの消去法による逆行列（連立方程式の解）
開発データ：



期間： 25 -26 Feb 2003.
ステップ数：千行弱。半分は共通ユーティリティからの引用だが、未使用部分を含む。
デバッグレベル： A
主な機能・述語：





任意サイズＮ×Ｍの行列形式 matrix_of_size(A,N,M)
加算・減算・乗算 matrix_add(X + Y = Z), matrix_subtract(X - Y = Z), matrix_multiply(p*Q=E)
転置 matrix_transpose(Y -> Z)
基本行演算 row_operation /5 リスト処理ユーティリティ replace /4 を使用。
逆行列 matrix_inverse(p^(-1)=Q)
その他：計算結果の数値だけを示すのでなく、行列の計算式を引数において表現する点を工夫した。
% matrix representation
% ----------------------------------------- %
matrix(i(2),[[1,0],[0,1]]).
matrix(i(3),[[1,0,0],[0,1,0],[0,0,1]]).
matrix(a,[[0,-1],[1,0]]).
matrix(b,[[1,-1],[2,0]]).
matrix(c,[[3,-6,-2],[1,-2,-1],[-2,6,3]]).
matrix(p,[[1,3,2],[0,1,1],[1,0,-2]]).
matrix(q,[[2,-6,-1],[-1,4,1],[1,-3,-1]]).
% identity matrix
matrix(i(N),I):integer(N),
N > 3,
matrix_of_size(I,N,N),
findall(R,
(
nth1(K,I,R),
findall(C,
(
nth1(L,R,C),
(L = K -> C = 1; C = 0)
),
R)
),
I), !.
% basic calculations of matrix
% -------------------------------------- %
matrix_add(X + Y = Z):(matrix(X,A);X=A),
(matrix(Y,B);Y=B),
matrix_of_size(A,N,M),
matrix_of_size(B,N,M),
findall(ZK,
(
nth1(K,A,AK),
nth1(K,B,BK),
findall(ZKL,
(
nth1(L,AK,AKL),
nth1(L,BK,BKL),
ZKL = AKL + BKL
),
ZK)
),
Z).
?- matrix_add(2*i(2)+a=C).
C = [[2+0, 0+ -1], [0+1, 2+0]] ;
図５－２．行列の演算（加算）
図５－１．行列と単位行列
% row operations
% ------------------------------------------ %
row_operation(P,0,[_,_], _, P).
row_operation(P,C,[K,L], A + C * B, E):% +P: a matrix
% +C: constant
% K,A: target row (K-th row)
% L,B: pivot row (L-th row)
% E: outcome
eval_number(C,C1),
\+ C1 is 0,
(matrix(P,Q);Q=P),
matrix_of_size(Q,N,M),
matrix_of_size(E,N,M),
nth1(K,Q,A),
nth1(L,Q,B),
row_vector_multiply(C*B=CB),
matrix_add([A]+[CB]=[ACB]),
replace(K/N,Q,ACB,E).
?- row_operation(a,2,[K,L], A + C * B, E).
K=1
L=1
A = [0, -1]
C=2
B = [0, -1]
E = [[0+0, -1+ -2], [1, 0]]
Yes
図５－３．基本行演算（ガウスの
消去法）
matrix_inverse(P ^ -1 = Q):(matrix(P,B);P=B),
matrix_of_size(B,N,M),
length(Xs,N),
eliminate_3(P,Xs,_,V),
anum_seq1(Ys1,N),
matrix(z(1,M,M),O),
matrix_add([Ys1]+O=R),
matrix([Ys] is R),
matrix_cols(V,Ys,Q),
!.
?- matrix_inverse(p^(1)=Q),matrix_multiply(p*Q=E),matri
x(F is E).
Q = [[2, -6, -1], [-1, 4, 1], [1, -3, -1]]
E = [[2*1+3* -1+1*2, 2* -3+3*4+1* 6, 2* -1+3*1+1* -1], [1*1+1* -1+0*2,
1* -3+1*4+0* -6, 1* -1+1*1+0* -1], [2*1+0* -1+1*2, -2* -3+0*4+1* -6, -2*
-1+0*1+1* -1]]
F = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
図５－４．逆行列（ガウスの消去法
による）
2015/9/30
20
（事例６）最短路アルゴリズム：traveler.pl
手法の特徴： Ford-BellmanのＤＰ解法(Bellman,1956) とDijkstra(1959)の２つの最短路アルゴリズム
開発データ：



期間： 2-5 Mar 2003. (4 Apr 解パス表示をデバッグ）
ステップ数：５０0行強。共通ユーティリティは用いない。
デバッグレベル： A
主な機能・述語：




ノード node(Name,Symbol)
アーク arc(From,To, [Cost|_]): direct move
最小費用経路 min_cost(M,Start,End,Path,Costs)
M: ford_bellman or dijkstra
その他：例題をexample /2 に登録し、分析するモデルはmodel /1でセットする。無限値 infinite を処理するための工夫が必要。
% example 1.
% transshipment system of spring water.
% 宿場町の例題（文献[12]）
%-----------------------------------------------------% nodes (i.e.,vertics)
example(yado, node(s, '富士山')).
example(yado, node(1, '宿場町1')).
example(yado, node(2, '宿場町2')).
example(yado, node(3, '宿場町3')).
example(yado, node(t, '江戸')).
% arcs (i.e., edges) with direction
example(yado, arc(s, 1, [10])).
example(yado, arc(2, 1, [3])).
example(yado, arc(s, 2, [5])).
example(yado, arc(1, 2, [2])).
example(yado, arc(2, 3, [2])).
example(yado, arc(1, t, [1])).
example(yado, arc(3, t, [6])).
% example 2.
%-----------------------------------------------------example(yado1, node(A, B)):example(yado, node(A, B)).
example(yado1, arc(A, B, C)):example(yado, arc(A, B, C)).
example(yado1, arc(3, 1, [-5])).
% default model
model(Default):- Default = yado1.
figure(yado):wn('%
[1]------------- [t]'),
wn('%
10 /|
1 /'),
wn('%
/|
6/ '),
wn('%
/ 3|
/ '),
wn('%
/ |2
/ '),
wn('%
/ |
/ '),
wn('%
[s]-----[2]------[3] '),
wn('%
5
2
'),
nl.
figure(yado1):wn('%
[1]------------- [t]'),
wn('%
10 /| |
1 /'),
wn('%
/ | |-5
6/ '),
wn('%
/ 3| |
/ '),
wn('%
/ |2 | / '),
wn('%
/ |
| / '),
wn('%
[s]-----[2]------[3] '),
wn('%
5
2
'),
nl.
?- network(Mode,[Nodes,Arcs,Costs]).
Mode = yado1
Nodes = [s, 1, 2, 3, t]
Arcs = [ (s, 1), (2, 1), (s, 2), (1, 2), (2,
3), (1, t), (3, t), (3, 1)]
Costs = [ (s, 1, 10), (2, 1, 3), (s, 2, 5),
(1, 2, 2), (2, 3, 2), (1, t, 1), (3, t, 6),
(3, ..., ...)]
Yes
図６－１．ネットワーク問題の例
図６－２．モデルyado1の要約
?- min_cost(ford_bellman,s,3,P,C).
---- potentials -------------------------t=5, node=s, pot=0
t=5, node=1, pot=2
t=5, node=2, pot=4
t=5, node=t, pot=3
t=5, node=3, pot=6
---- predecessors --------------------t=5, node=s, pred= t=5, node=1, pred=3
t=5, node=2, pred=1
t=5, node=t, pred=1
t=5, node=3, pred=2
---- end --------------------------------The circuit of negative or zero
cost has detected :
[3, 1, 2, 3]
?- abolish(model/1).
P = [3, 2, 1, 3]
C = [-1, -3, -5, 0] ;
P = [2, s]
C = [7, 5, 0]
Yes
Yes
図６－３．Ｆｏｒｄ－Ｂｅｌｌｍａｎ法に
よって例題yado1を解く（負費用回
路の検出）
Yes
?- assert(model(yado)).
Yes
?- min_cost(dijkstra,s,3,P,C).
---- potentials -------------------------t=3, node=s, pot=0
t=3, node=2, pot=5
t=3, node=1, pot=8
t=3, node=3, pot=7
t=3, node=t, pot=13
optimal cost=(7)
optimal route/cumulative cost=
->(s/0)->(2/5)->(3/7)
図５－４．例題yadoに対してＤｉｊｋ
ｓｔｒａ法を適用
2015/9/30
21
（事例７）関係代数：rdb01.p
手法の特徴：E. F. Codd(1979)の関係代数のタプル演算。
開発データ：



期間： 1, 5-6 Mar 2003. 概ね１日に作成したが、 Coddの論文を入手後、シータ演算を含む完成に２日かかった。
ステップ数：９00行強。共通ユーティリティからの引用は５０行ほど。
デバッグレベル： A
主な機能・述語：








合併 rdb_union(T1,T2,U)
差 rdb_difference(T1,T2,D)
積 rdb_product(T1,T2,P)
射影 rdb_projection(T,A,U)
リスト処理ユーティリティ list_projection /3 を使用。
選択 rdb_select(T,value(F=V),U)
θ－選択 rdb_select(T,theta(THETA),U)
結合 rdb_join(T1,T2,CF,U)
θ－結合 rdb_join(T1,T2,theta(THETA),U)
その他： θ演算を引数として使う。述語をそのままタプルとみなすより簡略なバージョンsrdb1.pl も作成した。
?- rdb_select(room,theta(capacity>100),large1).
% example 2. curriculum database
%-----------------------------------db(table(teacher),fields,[teacher_id,name,position]).
db(table(teacher),tuple,[t001,smith,professor]).
db(table(teacher),tuple,[t002,johnson,lecturerer]).
db(table(teacher),tuple,[t003,ito,professor]).
db(table(teacher),tuple,[t004,kim,associate_professor]).
db(table(teacher),tuple,[t005,simon,professor]).
db(table(teacher),tuple,[t006,keynes,professor]).
db(table(subject),fields,[class_id,subject,day,hour,room,teacher]).
db(table(subject),tuple,[c001,english,mon,1,103,smith]).
db(table(subject),tuple,[c002,english,fri,1,104,smith]).
db(table(subject),tuple,[c003,english,tues,2,103,johnson]).
db(table(subject),tuple,[c003,english,tues,3,104,johnson]).
db(table(subject),tuple,[c005,mathematics,fri,1,205,ito]).
db(table(subject),tuple,[c006,statistics,fri,3,101,ito]).
db(table(subject),tuple,[c007,computer,wed,1,c1,kim]).
db(table(subject),tuple,[c008,economics,wed,2,201,simon]).
db(table(subject),tuple,[c009,economics,thurs,3,201,keynes]).
db(table(room),fields,[room_id,capacity]).
db(table(room),tuple,[101,150]).
db(table(room),tuple,[102,50]).
db(table(room),tuple,[103,80]).
db(table(room),tuple,[104,30]).
db(table(room),tuple,[201,100]).
db(table(room),tuple,[202,150]).
db(table(room),tuple,[203,50]).
db(table(room),tuple,[204,30]).
db(table(room),tuple,[205,150]).
db(table(room),tuple,[c1,200]).
% rdb_projection /3 uses list_projection /3 cited from
set.pl.
rdb_projection(Table,Selects,Project):check_existence_of_db(Table,Fields,yes),
check_existence_of_db(Project,_,no),
check_of_fields(Selects/Fields),
list_projection(LPX,Fields,Selects),
domains(Table,Domains),
list_projection(LPX,Domains,NewDomains),
create_table(Project,Selects, NewDomains),
collect_tuples(Table,Tuples0),
findall(X,
(
member(D,Tuples0),
list_projection(LPX,D,X)
),
Tuples1),
sort(Tuples1, Tuples),
update_table(Project,Tuples),
display_table(Project).
図７－２．射影のプログラム
----------------------------------------------------table=large1
fields:
[room_id, capacity]
data:
[101, 150]
[202, 150]
[205, 150]
[c1, 200]
end of db
Yes
?rdb_join(large1,subject,theta(room_id=room),class1).
----------------------------------------------------table=class1
fields:
[large:room_id, large:capacity, subject:class_id,
subject:subject, subject:day, subject:hour,
subject:room, subject:teacher]
data:
[101, 150, c006, statistics, fri, 3, 101, ito]
[205, 150, c005, mathematics, fri, 1, 205, ito]
[c1, 200, c007, computer, wed, 1, c1, kim]
end of db
Yes
図７－１．授業についてのデータベース例
図７－３．θ 選択とθ 結合の各実行例
2015/9/30
22
（事例８）その他
手法の特徴：算術、確率と期待値、リスト・集合操作の各種共通ユーティリティ(math1.pl, set.pl)。およびモンテカルロ法(mcpi.pl)。
開発データ：



期間： 12 Jan – 27 Feb 2003 (math1.pl), 12 Jan – 25 Mar 2003 (set.pl), ただし確率モデル以外の部分は遂行理論のモデルで作成したものを引用
ないし改訂。18-19 Nov 2002 (mcpi.pl)
ステップ数：３００行強(math1.pl), ５６０行ほど(set.pl), ただし一部重複。60行(mcpi.pl)。
デバッグレベル： A, A, A(-)
主な機能・述語：




算術 sum /3, sum_eq /4, product_sum /4, product_sum_eq /5
分配、確率、期待値 allocation /3, probabilities /2, /3, p_expected_value /3, p_expected_value_eq /4
部分集合、リスト射影、置換 subset_of /3, list_projection /3, replace /4
乱数発生 sim_pi /3 円周率の近似を試みる例題
その他：乱数発生には random 述語を用いた。ヒストグラムを作成するプログラムpdist1.pl (19 Nov 2002) も試作した。
% sum
% ------------------------------------------------- %
sum([],0).
sum([X|Members],Sum):sum(Members,Sum1),
%number(X),
Sum is Sum1 + X.
% product
% ------------------------------------------------- %
product([],1).
product([X|Members],Z):product(Members,Z1),
%number(X),
Z is Z1 * X.
% weighted sum
% ------------------------------------------------- %
product_sum([],[],[],0).
product_sum([P|Q],[A|B],[E|F],V):length(Q,N),
length(B,N),
product_sum(Q,B,F,V1),
E is P * A,
V is V1 + E.
product_sum_eq([],[],[],0,0).
product_sum_eq([P|Q],[A|B],[E|F],V,Vq):length(Q,N),
length(B,N),
product_sum_eq(Q,B,F,V1,Vq1),
Eq = (P) * A,
E is Eq,
(Vq1=0 -> Vq = Eq; Vq = Vq1 + Eq),
V is V1 + E.
図８－１．算術のユーティリティ
% allocation
% -------------------------------------------- %
allocation(N,A,[X|Y]):allocation(N,A,A,[X|Y]).
allocation(0,_,0,[]).
allocation(N,A,B,[X|Y]):integer(A), length([X|Y],N),
allocation(_N1,A,B1,Y),
K is A - B1 + 1,
length(L,K), nth0(X,L,X),
B is B1 + X.
% probability (percentile)
% -------------------------------------------- %
probabilities(0,[]).
probabilities(N,[X|Y]):integer(N), length([X|Y],N),
allocation(N,100,[X|Y]).
% any ratio (weight) as prob.
%------------------------------------------scale(W,1/Z,P):findall(Y,(nth1(_K,W,X),Y is X/Z),P).
probabilities(W,N,P):length(W,N),
sum(W,Z),
scale(W,1/Z,P).
% expected value
% ------------------------------------- %
p_expected_value_eq(W,A,E,Eq):length(A,N),
probabilities(W,N,P),
product_sum_eq(P,A,_,E,Eq).
図８－２．分配、確率
% subset-enumeration
% ----------------------------------- %
subset_of(A,N,As):length(As,L),
length(D,L),
list_projection(D,As,B),
length(B,N),
sort(B,A).
% a sequence of binary choice:
%--------------------------------------list_projection([],[],[]).
list_projection([X|Y],[_A|B],C):X = 0,
list_projection(Y,B,C).
list_projection([X|Y],[A|B],[A|C]):X = 1,
list_projection(Y,B,C).
% replace(Project,G,Base,G1):% -------------------------------------- %
% X=1 --> preserve the value of Base.
% X=0 --> do replace G with G1.
replace([],[],[],[]).
replace([X|A],[_|B],[Z|C],[Z|D]):X = 0,
replace(A,B,C,D).
replace([X|A],[Y|B],[_|C],[Y|D]):X = 1,
replace(A,B,C,D).
図８－３．期待値、部分集合、
リストの射影、同じく置換
mc_trial:X is integer(random(101) - 50),
Y is integer(random(101) - 50),
Z is X^2 + Y^2,
update_counter,
(Z > 2500-> true;update_pi).
update_pi:retract(pi(P)), P1 is P + 1, assert(pi(P1)).
update_counter:retract(n(N)), N1 is N + 1, assert(n(N1)).
pi(0).
n(0).
n_init:abolish(sim_result,2), abolish(pi,1),
abolish(n,1), assert(pi(0)), assert(n(0)).
large_n(5000).
sim_pi(_,N,abend):large_n(O), N > O, write('Please try a smaller.').
sim_pi(G,N,Pi):G=mc_trial, large_n(O), N =< O, n_init, length(X,N),
forall(
nth1(K,X,_),
(
G,
sim_result(Pi),
assert(sim_result(K,Pi)),
trim_stacks
)
),
sim_result(N,Pi).
sim_result(Pi):pi(A), n(N), Pi is integer(A * 400 / N).
図８－４．モンテカルロ法の例(mcpi.pl)
2015/9/30
23
目的とアプローチ（Reminder）
知りたかったこと：

動的最適化や不完全情報を含む意思決定のモデリング

それはいかなる知的作業なのか？
cf., H.A.Simonの人工物デザイン

Prologはそのためのツールとして使えるか？
 離散的な領域以外でもうまく使えるのか？
アプローチ：以下の３＋１ステップ
ステップ０：モデルやモデリングの概念を自分なりに整理してみる
ステップ１：モデル記述言語の満たすべき条件を考える
ステップ２：実際に作ってみよう！実際にはこれを先に実行した
ステップ３：モデル事例から一般化できそうなことを探す
2015/9/30
24
予想と結果
予想：動的最適化や不完全
情報を含むモデリングにお
けるPrologの利点
Prolog処理系は、基本的にテキ
ストベースだが、標準化が進んで
おり、手軽に利用できる。
Prologはプログラムが論理学
（ホーン節）の意味を持ち、また内
部データベースからゴール節を、
導出原理に基づき、自動推論す
る。
よって、正しいモデリングは、解の
生成をシミュレーション可能にす
る。つまり、ソルバーとしても機能
する。
再帰プログラミングにより、DP問
題・解法を表現できる。
よって、数値・数式の処理を追加
すれば、離散的領域と数値的領
域の混じった意思決定問題で幅
広く役立つ。
結果：モデル記述言語として
Prologはどうだったか？
DP的処理や反復演算を含むいく
つかのOR・経営科学および情報
科学の問題・解法を、実際に、比
較的短期間で、モデリングできた。
とくに再帰的プログラミングとバッ
クトラックが、有限期のDP問題
の構造を表せた。だが作成は必
ずしも容易ではなかった。
また最適解、ゲームの解、不確
実な情報の下での信念更新など
を容易に計算できた。
これにより、理論理解に役立った。
たとえば、いくつかの異なる分野
の問題構造が、形式上互いに類
似していることが、あらためて
はっきりした。
確率や配分の組、期待値の計算、
集計計算、数式表現、文字列操
作、集合演算など、ユーティリ
ティの共通化を行った。
2015/9/30
25
問題点
対処可能と思われること



DP的処理や代数系の反復演算は、たしかに実装できたも
のの、思うように制御するのは、意外に難しかった。
確率を含むゲーム分析などでは、定義に忠実な（素朴な）
モデリングでは、近似精度と計算量にトレードオフがあり、
より効率的な解法（ソルバーの改良）は別途必要になる。
また以下のことは、積み残しになった。
残されたこと



作成されたモデル間の共通性や差異をどのように抽出でき
るか？
モデリング作業そのものをPrologによってコード化できる
か？
つまり、モデラーの思考をモデリングし、支援するには？
2015/9/30
26
モデリングとは
モデリング（デザイン活動）



現実の対象問題、その解法、あるいは問題解決者の思考を、記述・
表現・定式化すること。
規範的な意思決定ないし情報システムのデザインにおいては、最終
的に適切な「モデル記述言語」によってその記述が行われる。
モデリング初心者は普通のことばや図で考える。慣れると、このパス
がショートカットされるようになるらしい。
Cf., 「エージェント（人形）を使って（現実社会のアナロジーを）考える。」
モデル記述言語（モデリングツール）

明確な意味を持った（準）形式的システムとしての記述言語。例えば、
数学的言語（論理式・集合論的記法、多項式、LPやDPなどの数理計画
法など）、
表計算や最適化・シミュレーション用システム、
その他のプログラム言語、
あるいは情報システムの論理的デザイン、
その図法（例えばフローチャート、ER、DFD、UML、IDEF0)。
2015/9/30
27
モデルとは
「モデル」




モデリングの結果。あるいはその表現(定式化）を解釈し
た意味内容
例えば、代数系、帰納的関数、動的システム、表計算や
最適化・シミュレーション用システムで作成した計算的モ
デル、あるいはプログラムの動作として客観化ないし間主
観化できることが必要。＝＞いわば完全情報ゲーム。
一方、そのモデルの「直観的解釈」はもとの現実対象を指
す。その意味はモデラーないしデザイナーの脳の活動（な
いし私的情報）＝＞いわば不完全情報ゲーム。
各人が現実対象に対して持つ解釈の間のずれは、各自
の描くモデルのちがいとして、外化できるため、ある程度
客観化できるだろう。
2015/9/30
28
参考文献
信念関数・あいまい信念の更新と意思決定
[1] Shafer,G.(1976). Mathematical Theory of Evidence. Princeton University Press.
[2] Dempster, A.P.(1967). Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics 38:
325-339.
[3] Moral,S.and De Campos, L.M.(1991). Updating uncertain information. In the Proceedings of IPMU90, LNCS 521, Springer,
pp.58-67.
[4] Dow, J. and S. R. da Costa Werlang (1992). Excess volatility of stock prices and Knightian uncertainty. European Economic
Review 36: 631-638.
[5] Jaffray J-.Y. and P. Wakker (1994). Decision making with belief functions: compatibility and incompatibility with the sure-thing
principle. Journal of Risk and Uncertainty 8: 255-271.
[6] Gilboa,I. and D. Schmeidler (1993). Updating ambiguous beliefs. Journal of Economic Theory 59: 33-49.
サーチ・最適停止
[7] Weizman, M. L. (1979). Optimal search fot the best alternative. Econometrica 47(3): 641-654.
協力ゲーム
[8] 武藤滋夫 (2001). 『ゲーム理論入門』. 日経文庫.
[9] Aumann, R.J.(1989). Lectures on Game Theory. Stanford University. [丸山・立石訳, 『ゲーム論の基礎』,勁草書房, 1991.]
最短路・ネットワーク問題
[10] Bellman, R.(1956). On a routing problem. Quarterly of Applied Mathematics 16: 87-93.
[11] Dijkstra, E.(1959). A note on two problems in connection with graphs. Numerische Mathematics 1: 269-271.
[12] 久保幹雄、『組合わせ最適化とアルゴリズム』、共立出版．
[13] 猪平進ら、『インターネット時代の情報管理概論』、共立出版．
関係代数
[14] E. F. Codd, Extending the database relational model to capture more meaning. ACM Trans. on Database Systems 4(4)
(1979), 397-434.
2015/9/30
29
付録．本文で紹介したプログラムの添付
３．１．
３．２．
３．３．
３．４．
３．５．
３．６．
３．７．
３．８．
決定木分析：dtree0.pl
最適停止（サーチ）：pjtsea.pl
信念関数：belief0.pl
協力ゲーム：coop.pl
線形代数：matrix1.pl
最短路アルゴリズム：traveler.pl
関係代数：rdb01.pl
その他
2015/9/30
30
作成したモデルの一覧（１）
決定木分析：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
最適停止（サーチ）：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
信念関数：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
dtree0.pl
決定木によるリスクのある投資案の評価・選択。
21-22 Feb 2003.
約400行。 pjtsea.plから分離。約半分は共通ユーティリティから。
A
決定木に対応する投資案の表現 decision_tree /3、
時間割引後期待利得 npv/4, expected_value_of /3、
ロールバック解 roll_back /3, is_an_optimal_path /3
標準的な意思決定分析。計算式を表示する。
pjtsea.pl
サーチ順序の最適化。Weitzman(1979)の２つの例題。
12-25 Feb 2003.
約千行。ただし４００行ほどはdtree.pl と共通。
A(-)
例１：R&D投資の順序最適化。（dtree.plへの埋め込み）
例２：パンドラの箱。最適停止ルールのシミュレーション sfp /8.
ユーティリティ p_expected_vale_eq /4 他利用。乱数発生はしない。
ちなみに相対ランクによるサーチは別途作成（sea2.pl）。
belief0.pl
Shafer(1976)の信念関数と可能性関数、およびDempster-Shafer更新。
27 Feb - 1 Mar 2003. （前年秋は試作。今回全面的に作り直しした。）
約１１００行。３００行は実行サンプル。ユーティリティ１５０行引用。
A
基本確率割当（マス） bpa0(A,B), mass(A,B,C) （反転公式による）、
信念関数、可能性関数 sbel(A,B,C), spos(A,B,C)、
不確実性推論と意思決定への応用が可能。協力ゲームと関係。
2015/9/30
31
作成したモデルの一覧（２）
協力ゲーム：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
線形代数：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
最短路アルゴリズム：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
（６）その他：
coop.pl
協力ゲーム。特性関数の下で提携と配分、コア、仁、シャプレー値。
7 - 9 Feb 2003. 実質1日。9日にサンプル実行をコメントに追加。
６００行弱。実質３００行。残りはユーティリティからの引用。
A
提携形ゲーム（特性関数） game(G,value,X,P)、
全体合理性、配分、コア col_rat_outcome/3, imputation/3, core/3、
Schmeidlerの仁 nucleolus(G,A) 、不満を辞書式順序で最適化、
シャプレー値 shapley/3。
定義にほぼ忠実。配分案はユーティリティ allocation /3 で格子点近似。
matrix1.pl
行列と各種演算、単位行列、ガウスの消去法、逆行列（連立方程式の解）
25 -26 Feb 2003.
千行弱。半分は共通ユーティリティからの引用だが、未使用部分を含む。
A
任意サイズＮ×Ｍの行列形式 matrix_of_size(A,N,M)、
加算・減算 matrix_add(X + Y = Z), matrix_subtract(X - Y = Z),
乗算 matrix_multiply(p*Q=E)、転置 matrix_transpose(Y -> Z)、
基本行演算 row_operation /5 ユーティリティ replace /4 を使用。
逆行列 matrix_inverse(p^(-1)=Q)。
計算結果だけでなく、行列の演算式を表現する点を工夫した。
traveler.pl
Bellman(1956) とDijkstra(1959)の２つの最短路アルゴリズム
2-5 Mar 2003.
５００行強。共通ユーティリティは用いない。
B(+)
ノード node(Name,Symbol)、アーク arc(From,To, [Cost|_])、
最適経路 min_cost(M,Start,End,Path,Costs) M: ford_bellman/dijkstra
example /2 に例を登録、model /1でモデル設定。無限値 infinite を処理。
2015/9/30
32
作成したモデルの一覧（３）
関係代数：
（１）手法の特徴：
（２）開発期間：
（３）ステップ数：
（４）デバッグレベル：
（５）主な機能・述語：
rdb01.pl
E. F. Codd(1979)の関係代数のタプル演算。
1, 5-6 Mar 2003. Coddの論文を入手しθ演算とドメインを含めた。
９００行強。共通ユーティリティからの引用は５０行ほど。
A
合併 rdb_union/3、差 rdb_difference/3、積 rdb_product/3 、
射影 rdb_projection/3 ユーティリティ list_projection /3 を使用。
選択 rdb_select(T,value(F=V),U)、θ選択 rdb_select(T,theta(X),U)、
結合 rdb_join(T1,T2,CF,U)、θ結合 rdb_join(T1,T2,theta(X),U)
（６）その他：
述語をタプルとみなす簡略バージョンsrdb1.pl も作成。
その他：
set.pl, math1.pl, mcpi.pl
（１）手法の特徴：
リスト、集合操作のユーティリティ(set.pl)、
算術、確率のユーティリティ(math1.pl)、
乱数実験・モンテカルロ法(mcpi.pl)。
（２）開発期間：
12 Jan – 27 Feb 2003 (math1.pl),
12 Jan – 25 Mar 2003 (set.pl),
18-19 Nov 2002 (mcpi.pl)
確率モデル以外は、遂行理論のモデルで作成したものが元になっている。
（３）ステップ数：
３００行(math1.pl), ５６０行(set.pl), ただし一部重複。60行(mcpi.pl)。
（４）デバッグレベル： A, A, A(-)
（５）主な機能・述語：算術 sum /3, sum_eq /4, product_sum /4, product_sum_eq /5
確率、期待値 allocation /3, probabilities /3, p_expected_value_eq /4
部分集合、射影、置換 subset_of /3, list_projection /3, replace /4
乱数発生 sim_pi /3 円周率の近似を試みる例題
（６）その他：
乱数発生には random 述語を用いた。
ヒストグラムを作成するプログラムpdist1.pl (19 Nov 2002) も別途試作済。

Download Report