情報システム研究所 - 日本大学生産工学部

ISSN 2186-5647
−日本大学生産工学部第47回学術講演会講演概要(2014-12-6)−
2-38
不完全情報 AHP の諸問題
1.
はじめに
日大生産工(非常勤)
○篠原 正明
情報システム研究所
篠原 健
以下に証明の概略を示す(詳細ならびに関連する考察は[1]
AHP において、一部要素が欠落した不完全な一対比較行列
参照)
。
から DAP にもとづきウェイトベクトルを推定する際の諸
不完全情報下の一対比較行列 A0 において、欠落要素は 0
問題(不完全情報 DAP の更新式、整合性とトポロジー条件、
で、欠落要素以外を 1 とした行列 A1(無向グラフの一種の
内外評価不等式、逆固有ベクトル問題、重み付き DAP、連
点-点接続行列)を考える。H = D(n)-1A1 と置くと、行列 H
続判断 AHP の DAP、連続時間・連続判断 AHP の DAP)
は行確率行列である。従って、エルゴード性と非周期性を
を考察し、それらの解答を与える。
仮定すると、
2.
と定常状態に収束する。すなわち、更新式
不完全情報 DAP の更新式
DAP 更新式:x(t+1) = D(n)-1 A0x(t)
定常解
:x(t+1) =νx(t), νD(n)x = A0x
誤差行列 E :νD(n)1 = E1, E = D(x)-1A0D(x)
R = H t(t→∞)
(3.8)
(2.1)
x(t+1) = D(n)-1 A1x(t) = Hx(t)
(2.2)
も収束する。DAP 更新式(2.1)と更新式(3.9)、あるいは係数
(2.3)
行列の P = D(n)-1A0 と H = D(n)-1A1 を対比し、等長パス性
(3.9)
但し、D(n) = diag(ni), ni は第 i 行測定数、A0 を欠落要素を 0
が成立すれば、
ここでHtとPtのトポロジ的意味を考慮して、
と置換した m×m 比較行列とする。
S = Pt(t→∞)に対して、sij = rij· gij
3.
が成立する( 但し、R={rij }, S={sij }, rij =
整合性とトポロジー条件
3.1 整合性指標
N
)
。
従って、t→∞の DAP 更新式(2.1)において、x(t+1) = x(t)、
誤差平均として、
ave(E) = ave.ind.exm(E) = 1TE1/N=ν
(3.10)
nj
(3.1)
すなわちν= 1 が成立し、CI = CJ = 0 が成立する。
〔QED〕
を採用する。但し、N = Σni , ind は including diagonal,
4.
exm は excluding missing で、平均対象として対角要素は
完全情報での[2]の結果を行列表示で整理し、この内外評価
含み、欠落要素は除外した。
不等式が不完全情報 DAP でも成立することを示す。
整合度:CJ = ave(E)-1 =ν-1
(3.2)
内外評価不等式
4.1
完全情報 DAP
Ax(t)
A0 で(欠落要素対を除いて)逆比性が成立すれば、ν≧1
x(t+1) =
(3.3) が成立し、CJ≧0
(CI+1)x =
(3.4) も成立する。Saaty 氏によ
3.2 トポロジー条件
m−1
(CJ+1)x =μx =
る整合度 CI においても CI≧0 (3.5) が成立する。
CI = CJ· N/(N-m)
(4.1)において、x(t+1) = x(t) = x とすると、
m
(A−I)x
(3.6)
(4.2)
Ax
(4.3)
m
が成立する。両式において左辺の x が内部(真の自己)評
完全情報下では、
「aii = 1, 逆比性
価ウェイトベクトル、右辺が外部評価である。(4.2)では自
aij・aji = 1, 三角整合性 aij・ajk = aik」(3.7)ならば、CI = 0
分を除いた外部、(4.3)では自分も含めた外部(というより
であるが、不完全情報下でのCI = CJ = 0 の条件は?
は、全体)評価である。CI+1≧1, CJ+1=≧1 なので、内
一対比較デザイングラフにおいて、
「任意の 2 点 ( i→j ) 間
≦外不等式が成立する。すなわち、外部評価は常に内部評
の任意パスの一対比較重み積が同じ値 gij に等しい条件」を
価よりも高く、その乖離度合いは不整合性に比例する。
「等長パス性」と定義する。
4.2
不完全情報 DAP
〔定理 3.1〕不完全情報下の整合性トポロジー定理 CI = CJ
(2.2)より、以下を得る。
= 0 の必要十分条件は、等長パス条件(に加えて、エルゴー
(D(n)-I)-1(νD(n)-I)x = (D(n)-I)-1(A0-I)x
ド(強連結)条件と非周期性条件)が成立することである。
diag{
 −1
 −1
}x = diag{
1
 −1
}(A0-I)x
Solutions to the Incomplete Information Issues in AHP and DAP
Masaaki SHINOHARA and Ken SHINOHARA
― 257 ―
(4.4)
(4.5)
(4.5)は(4.4)の別表現である。右辺が外部評価であり、A0
の逆比性仮定の下ではν≧1 なので、左辺の xi の乖離度合
 −1
い係数
 −1
≧1 となる。従って、完全情報の場合と同様に
Saaty の NNP[3]における完全情報下の離散判断と連続判
断での固有値問題定式化は各々(6.1), (6.2)で与えられる。
Ax =λx, Σaijxj =λxi
(6.1)
∫K(u, v)x(v)dv =λx(u)
(6.2)
内≦外不等式が成立する。但し、乖離度合いは xi 毎に ni に
(6.1)の行列表現にて、A を無限次元とし、i を u、j を v に
依存して、異なりうる。すなわち、被評価対象数が多いほ
対応させれば、連続判断での定式化となる。時間変数を t
ど、乖離度合いは小さくなる。なお、内≦全不等式はより
で表すと、不完全情報下の連続判断 DAP の定式化は以下の
単純な(4.6)となり、同様に成立する。
とおりである(積分は K(u, v)の定義域、非定義域:K(u, v)=0)。
νx = D(n)-1A0x
(4.6)
なお、(4.7), (4.8)の等式変形より、内外不等式と内全不等式
m−1
−I=
m
A
( − I)
m−1 m
(D(n)-I)-1(A0-I)-I = D(n)(D(n)-I)-1[D(n)-1A0-I]
5.
∫ (,)(,)
(6.3)
∫ 1(,)
x(t+1) = D(n)-1A0x(t)
は等価であることがわかる。
A−I
x(u, t+1) =
(6.4)
(4.7)
(6.4)は積分表現(6.3)の行列表現である。(6.4)にて、x, D(n),
(4.8)
A0 は無限次元である。(6.4)の第 i 式は(6.5)となるが、ni が
重み付き DAP(あるいは w-DAP)
(6.3)右辺の分母∫1(u, v)dv に対応する。但し、1(u, v)は行
不完全情報 DAP では一対比較行列 A の一部要素が欠落し
列 A1 に対応し、K(u, v)の定義域(非欠落域)では 1、それ
た場合を扱ったが、欠落要素をその重みが 0 と考えること
以外で 0 をとる関数である。なお、原著[3]では K(u, v)にて
により、(i , j)要素に対して重み wij を考慮した w-DAP を提
変数 (s, t)を使用してるが、本論文では t を時間変数として
案し、その更新式を以下に示す。
使うので(u, v)を用いた。
更新式:xi(t+1) = ∑    ()
x(t+1) = (W∘A)x(t)
(5.1)
xi(t+1) = ∑∊   ()/ni
(5.2)
積分表現(6.3)と行列表現(6.4)が等価なので、(6.4)と(2.1)が
(5.2)は(5.1)のベクトル行列表現で、∘は要素毎の乗算を意
(6.5)
対応し、2~4 章の議論が積分表現でも適用できる。
味する。 x(t+1) =κx(t) =κx とすると、以下を得る。
例えば、(2.2)の定常解は(6.6)、(2.3)の誤差行列は(6.7)、(3.1)
定常解:κx = (W∘A)x
の誤差平均 ave(E)は(6.8)、3 章の行確率行列 H=D(n)-1A1 は
(5.3)
誤差行列:κ1 = (W∘E)1, E = D(x)-1AD(x) (5.4)
(6.9)、(4.6)の内≧全不等式は(6.10)、(4.4)の内≧外不等式は
一般論では、W = {wij}は任意であるが、以下は W≧0, Σwij
(6.11)となる。
= 1 の条件を付与した行確率行列の場合を考察する。又、一
対比較行列 A = {Aij}は完全情報であり、欠落無しである。
1
誤差平均:ave(E) = 1T(W∘E)1/m= ∑,   =κ (5.5)

ここで、ave(E)=κは全要素 m2 個の重み wij 付き平均で、欠
落要素は wij = 0 とし、非欠落要素は行毎に重みを wij =1/ni
と均等化すると、不完全情報 DAP を模擬し、そのときの
(5.5)のκと(3.1)のνは一致する。なお、w-DAP で不完全情
報を模擬する場合は、欠落要素(i , j)は測定しなかったので
はなく、測定値 aij(さらには eij)は存在するが、その重み
wij = 0 で完全に無視するという立場である。さらに、A の
逆比性を仮定し、W を対称確率行列(wij = wji , wij≧0 ,
∑  = 1)とすれば、κ≧1 が成立する。
6.
連続判断 AHP の不完全情報 DAP
定常解:νx(u) =
∫ (,)()
(6.6)
∫ 1(,)
誤差関数:
()
ν∫1(u,v)dv =∫E(u,v)dv , E(u,v) =K(u,v)
(6.7)
()
誤差平均:ave(E) =
行確率行列 H(u,v) =
∬ (,)
∬ 1(,)
1(,)
∫ 1(,)
内≦全不等式:νx(u) =
内≦外不等式:x(u)
= ν (6.8)
∫ (,)()
∫ 1(,)
 ∫ 1(,)−1
∫(1(,)−(,))
― 258 ―
(6.9)
(6.10)
=
∫( (,)−(,))()
∫(1(,)−(,))
無向枝(i , j)、j∈Si が付随し、誤差方程式(8.1)の第 i 行は
(6.11)
(8.2)となり、誤差和∑  がνni に等しいことを主張する。
(6.8)において、離散判断の時と同じ論理で、K(u,v)(≧0)
但し、ni = |Si|。
∑∈  = 
が逆比性を持てば、誤差関数 E(u,v)(≧0)も逆比性を持ち、
定義域は u と v に関して対称と仮定すれば、
K(u,v)+1/K(u,v)≧2
i = 1,…,m
(8.2)
(8.1)の各行、あるいは(8.2)は行毎に独立であり、従って、
(6.12) が成立するので、ν≧1
独立な方程式の数|Q|= [G の点数|V|] = m
−
(8.3)
(6.13) を得る。従って、この場合には内≦全不等式(6.10)、
未知変数の数|U| = [G の枝数|L|] =
内≦外不等式(6.11)が成立する。(6.11)ではデルタ関数を
自由変数の数|F| = |U|-|Q|
導入するなど、厳密性の観点からは問題があり、その意
すなわち、未知変数群 U = 従属変数群 Q + 自由(独立)
味では、内≦全不等式が本質的と言える。又、連続判断
変数群 F (8.6).
での定式化において、K(u,v) =auvδ(u-i)δ(v-j) ,
以下に、Q(あるいは F)の選び方を考察する。
x(u) = xuδ(u-i) (6.14)等とすれば、離散判断での定式
2
(8.4)
(8.5)
(i)G 上で従属変数(枝)群 Q が連結な場合
木枝数 = m-1、かつ、m 個の節点対応の各独立方程式
化に帰着する。
は接続枝対応の変数を含むことを考慮して、Q として G
7.
連続時間・連続判断 AHP の DAP
x(t+1) = Bx(t) と
()

上の単閉路木(SL 木、Single Loop Tree)を選ぶ。ここ
= Cx(t) を比較すると、離散時間
で、
SL木とは木に1本の補木枝を付加したグラフである。
上で両者が同じ値となるためには、
B = exp(C) (7.1) あ
SL 木では、唯一存在する閉路の各節点に部分木が接続す
るいは C = log B (7.2)、一次近似で C=B-I (7.3)を得
るトポロジー(図 8.1)を持つ。
る。B = A/m or D(n)-1A0 (7.4) とすると、内全評価差を
時間変化の原因とする微分方程式モデルを得る。
〔連続時間・離散判断の DAP〕

= k(A/m-I)x
完全情報:


不完全情報:

= k(D(n)-1A0-I)x
(7.5)
(7.6)
〔連続時間・連続判断・不完全情報の DAP〕
()

∫ (,)()
=k{
∫ 1(,)
-x(u) }
図 8.1 単閉路木(SL 木)のトポロジー例
F を与えれば、
(単閉路上を除く)
部分木上の Q が定まり、
(7.7)
残るは単閉路上の Q のみとなるが、これらは 2 次方程式
k>0 は比例定数、(7.7)の右辺は内全評価差((6.10)参照)
を解くことにより、定まる(付録 1 参照)
。
(ii)G 上で従属変数(枝)群 Q が非連結な場合
となっている。
G の節点集合 V を被覆して非連結な SL 木の集合へ分割
8.
する。V を疎な節点集合群{V1,V2,…,Vz}へと分割し、
逆固有ベクトル問題
(2.3)を再掲し、誤差方程式(8.1)と呼ぶ。
E1 =νD(n)1
部分集合ViとVi内を相互接続する枝からなる各部分グラ
(8.1)
フ G〔Vi〕(i = 1,…,z)において SL 木を変数として選ぶ。
(8.1)において、固有値(定常成長率)ν、デザイングラ
V = V1∪V2∪…∪Vz ,Vi∩Vj =φ (i≠j), |Vi|≧3 (8.7)
フ G が与えられた下で、E を求める問題が逆固有ベクト
〔例 8.1〕図 8.2(a)のデザイングラフ G において、
ル問題である。以下では、対欠落、逆比性、自己同一性
V = {1,2,3,4,5,6,7,8}と 1 つの(連結な)SL 木、
(aii=1)
、対角要素非欠落を仮定する。なお、G は無向グ
V = {1,2,3,4}∪{5,6,7,8}と 2 つの SL 木、
ラフとなり、G より n = {ni}がわかる。
V = {1,2,3}∪{4,5,6,7,8}と 2 つの SL 木、
G において節点 i は項目 i に対応し、節点 i に接続する
として Q を選んだ例を図 8.2(b) , (c) , (d)に示す。
― 259 ―
参考文献
[1]篠原正明、篠原健:不完全情報AHP・DAP の諸問題とその解答、
情報システム研究所報告、ISRC2014-1(2014.12).
(a) デザイングラフ G
[2] K. Sekitani and N. Yamaki:A Logical Interpretation for the
Eigenvalue Method in AHP, Journal of the Operations Research
Society of Japan, 42 (1999)
[3] T. Saaty : The Neural Network Process, RWS Publications (2014)
(b) 連結 SL 木として Q を選んだ例
[4] Masaaki SHINOHARA: INVERSE PROBLEMS IN AHP,
Proceedings of the International Symposium on the Analytic Hierarchy
Process 2014 (2014.6)
(c)2 つの SL 木として Q を選んだ例 1
付録 1 単閉路に関する逆固有ベクトル問題の解法
(i)閉路長3 の場合
e12 +
1
31
= Κ1 (A-1) e23 +
1
= Κ2 (A-2) e31 +
12
1
23
= Κ3(A-3)
x = e31 とすると、(A-1)~(A-3)より、x は以下の2 次方程式(A-4)
(d)2 つの SL 木として Q を選んだ例 2
の根により定まる。 ax2 + bx + c = 0
図 8.2 デザイングラフ G と従属変数群 Q 選択例
(A-4)
a= Κ1Κ2-1, b=Κ1+Κ3-Κ2-Κ1Κ2Κ3,c =Κ2Κ3-1 (A-5)
|U|= 16 , |Q| = 8 なので|F|=|U|-|Q|= 8 となる。
(ii)閉路長4 の場合
(b) , (c) , (d)において、太線枝が従属変数群 Q、細線枝が
e12 +
自由変数群 F に対応する。例えば、(b)では F が与えられ
e34 +
れば、
(1,2)→(1,3)、
(7,8)→(5,7)の順に Q の一部が決まり、
x = e41 とすると、(A-6)~(A-9)より、x は以下の係数a , b , c を持
残った閉路(3,4,6,5)について 2 次方程式(付録 1)を解く
つ2 次方程式の根として定まる。
ことにより、残りの Q が決まる。又、(d)では三角形閉路
a = Κ1Κ2Κ3-Κ3-Κ1 ,
の SL 木へ分割する方法で、G が完全グラフなら常に三
Κ1Κ2Κ3Κ4 , c = Κ2Κ3Κ4-Κ2-Κ4
角形閉路の SL 木への分割が常に可能である([4]参照)
。
(iii)閉路長5 の場合
なお、本例においては、(8.7)の最後の条件により、最大
e12 +
1
41
1
23
1
51
1
= Κ1
(A-6)
e23 +
= Κ3
(A-8)
e41 +
=Κ1(A-11) e23 +
34
= Κ2 (A-7)
= Κ4 (A-9)
b =Κ1Κ2+Κ1Κ4+Κ3Κ4-Κ2Κ3-
1
12
=Κ2(A-12) e34 +
e51 +
1
=Κ3(A-13)
9.
x = e51 とすると、(A-11)~(A-15)より、x は以下の係数a , b , c を
45
= Κ5
1
23
e45 +
おわりに
(A-14)
(A-10)
で2 個までのSL 木への分割が許容される。
〔例8.1 の終わり〕
34
= Κ4
1
12
1
(A-15)
詳細検討、数値計算例、ならびに本論文でとりあげてい
持つ 2 次方程式の根として定まる。
ない他の不完全情報 AHP の課題(例えば、べき乗一般化
a = Κ1Κ2Κ3Κ4―Κ1Κ2―Κ1Κ4―Κ3Κ4+1 ,
平均 DAP、パス代数 DAP に関する諸問題、逆固有ベク
b = -Κ1Κ2Κ3Κ4Κ5+Κ1Κ2Κ3-Κ2Κ3Κ4+Κ3Κ4Κ5
トル問題の最適化解法、w-DAP の一般化、x(t+1) =
+Κ1Κ4Κ5+Κ1Κ2Κ5+Κ2+Κ4-Κ1-Κ3-Κ5 ,
D(n)-1A0x(t)+f(t),等‥)については[1]を参照してください。
c = Κ2Κ3Κ4Κ5-Κ4Κ5-Κ2Κ5-Κ2Κ3+1
なお、神経情報処理系では生理解剖学的に隣接領域から
(iv)係数a , b , c に関する閉路長k≧3 の再帰関係式
の情報収集が支配的なため(厳密には、連続判断モデルに
a(k+1) = f(k+1), b(k+1) = g(k+1)-Κk+1f(k+1)-d(k+1),
て距離二乗減衰強度の一対比較情報、等)、NNP[3]のモ
c(k+1) =-g(k+1)Κk+1-e(k+1), d(k+1) =-f(k),
デル化では不完全情報 DAP が本質的と考えられる。本研
e(k+1) =-g(k), f(k+1) = Κkf(k)+d(k), g(k+1) = Κkg(k)+e(k)
究成果は、その理論的基盤を与える。
[初期値:d(3) =-Κ1 , e(3) = 1 , f(3) =Κ1Κ2-1 , g(3) =-Κ2]
― 260 ―
(A-16)