学術情報処理研究 No.1 1997 pp.16-24

マルコフ連鎖を応用した問題分析手法(SMAP法)


橘   文  夫


新潟大学総合情報処理センター
新潟市五十嵐2の町8050
TEL 025(262)6113 FAX 025(262)6232 funko@cc.niigata-u.ac.jp


概要

 現状を分析し、問題解決へと導くための簡単でかつ有効な手法(SMAP法)を提案する。 問題解決のための手法として、KJ法あるいはSAD法が知られているが、SMAP法はこれらの手法とは異なり、マルコフ連鎖の概念、すなわち時間ステップの概念を取り入れてある。 SMAP法はSAD法と比して取り扱いが非常に簡単であるにもかかわらず分析結果はSAD法と類似することが判った。

キーワード

問題分析、KJ法、SAD法、マルコフ連鎖

A New Method Using Markov Chain for Analyzing of Problem

F. Tachibana


Information Processing Center, Niigata University
Ikarashi 2-8050, Niigata 950, Japan.
TEL 025(262)6113 FAX 025(262)6232 funko@cc.niigata-u.ac.jp

Abstract

 A new method for analyzing of problem (SMAP method) is proposed. Markov Chain is applied to SMAP method to get time steps. SMAP method is compared with SAD method proposed by Mori. Though SMAP method is simple and easy to analyze problem, results by SMAP method are similar to those by SAD method.

Keywords

problem analysis, KJ method, SAD method, Markov Chain

1.はじめに

 世はまさに情報化時代のまっただ中にある。年々(いや日々というべきか)高度化・多様化 する情報の処理と通信の環境は、大学の総合情報処理センターの役割を一層重要なものにして いる。新潟大学においては、教養部の廃止に伴い全学の教養教育としての情報処理教育の実施 及び改善のため、工学部とともに総合情報処理センター(以下センターという)がその一翼を 担うことになった。現在、センターの下部委員会である情報処理教育専門委員会において、 新潟大学の情報処理教育の現状と将来のあるべき姿について調査・検討を進めているところ である[1]。
 このような中にあって、筆者は数年前から教養科目としての「情報処理概論」の講義と実習を 担当してきた。筆者はこの間、講義や実習を通して、学生から以下のような訴えを受けることが 少なからずあった。
  1. コンピュータやネットワークに関する情報が氾濫する中、何をどういう手順で勉強して いいのか分からない。
  2. 情報処理や情報通信が自分の将来の仕事とどんな関わりを持つのか予測ができない。
  3. プログラミングやインターネット利用のための適性が自分にあるのか不安である。
 計算機科学の学習に関するこのような質問や相談に限らず、解決すべき様々な問題(悩み) が与えられたとき、それを明快な手法で定量的に分析し、客観的な判断のもとで、適切な 指導・助言を与え得るシステムを作れないものであろうか。
 川喜多によって提唱されたKJ法[2]は,問題解決の手法としてあまりにも 有名である。KJ法にまつわる様々な話題[3]やKJ法の適用事例とそれに対する 評価[4]によれば、KJ法の問題解決へ果たしてきた役割には大きいものがある。 また森によって提唱されたSAD法[5]も問題解決のための手法のひとつである。 これらの手法の長短については、それぞれの手法の考案者によって冷静に分析されている。 [2-5] 川喜多自身の言によれば「KJ法は複雑難解な、いわゆる大問題を扱う ときに威力を発揮する」[2]し、また森によれば「KJ法とSAD法とでは、形式的 な類似点はあるものの、利用目的、分析手順、分析結果などが異なる」[5] 。 筆者の感想では、これら2つの手法はいずれも、問題解決の手法としては非常に有用である けれども、問題を分析する過程で作成されるフローチャートが複雑になり、学生や筆者のような” しろうと”には理解しにくいところがあるようである。
 このような背景のもとで、筆者はマルコフ連鎖[6]を応用した手法、SMAP (Systems Markov Analysis Problem)法による問題分析システムを考案した。本稿で SMAP法を紹介し読者の批判を待ちたい。KJ法は広く知られた手法であるし、上で述 べたような学生の抱える中小問題には適用しにくい面があるので、ここでは述べない。2. でSAD法の概要を紹介し、3.で筆者の提案するSMAP法について述べる。4.で SMAP法の適用と考察を行なう。

2.SAD法

 森によって提唱されたSAD(Systems Accommodation & Design)法[5] の手順は次のようである。
  1. 自分の抱えている問題(悩み)は何か、また達成したい目標は何かを特定する。
  2. 問題の要因(目標達成を妨げる要因)となっているものを全て挙げる。
  3. これらの要因間を、因果関係、包含関係を示す矢線で結ぶ。要因は、外的要因と内的要 因とに分類される。因果関係や包含関係を「影響」と呼ぶことにする。外的要因とは、他の 要因に影響を与えるが、他の要因から影響を受けない要因であり、内的要因とは、他に影響 を与え、他からも影響を受ける要因である。
  4. 各要因を結ぶ矢線に影響の大きさ、すなわち影響度を数値で記入する。
  5. 各要因と数値化された影響度に対して、適当なマトリクス演算を施すことによって、 問題解決の妨げになっている要因(元凶)を絞りこんでいく。
  6. 絞りこまれた要因を取り除くための行動を起こす。
 以上の手順から想像されるように、SAD法は中小問題にも適用が可能で取り扱いも比較的 容易である。手順 5. に記したマトリクス演算は次のように行なわれる。
 内因を
外因を
とし,内因列 ベクトルを



外因列ベクトルを



で表す。
 内因 iから内因 lへの因果関係の程度をβli、外因 j から内因 l への因果関係の程度を γljとする。(Fig.1 参照)


Figure 1: 要素間の因果関係

ただし



である。因果方程式は次のようになる。



 ここで B は βliを要素とするG行G列のマトリクス、 Γは γljを要素とするG行K列のマトリクスである。 (2.4)式は、I をG行G列の単位マトリクスとすると



のように変形される。マトリクス
の要素 δij



の関係にあり、外因 xj の内因 yiに対する相対的な影響度 を表わしている。  内因の内因への影響度を見るには、当該内因を外因ベクトルに移動させ、(2.3)式の値を ゼロにすればよい。
 解決したい問題、つまり最終目的として、ひとつあるいは複数の内因を採る。この内因に 対する各外因の影響度を評点 vと定義する。最終目的にそれぞれの重要度に応じて重みを与える。 この重み行ベクトルを
とすると



となる。
を評点ベクトルという。 要素 ej は、外因 xj が最終目的に与える影響度 を表わしている。ただし



である。この ej の値を円グラフなどで見やすく表示すれば、改善すべき外因、 すなわち元凶が明らかになる。  森は更に、元凶を取り除くために実施する政策の評価についても述べている[5]が、 ここでは言及しない。

3.マルコフ連鎖とSMAP法

3.1 マルコフ連鎖

  マルコフ連鎖は確率過程を扱うときに有用な概念であり、その応用範囲は広い[7]。 本節ではSMAP法の理解を助けるために、マルコフ連鎖の簡単な解説を行なう。
 N番目の試行 XNにおいて、状態の有限集合 S={S1,S2,....,Si,...SN} の中の状態 Siが出現することを



と表わし、試行 XN に先行するj個 (j < N) の試行で



の状態(これを系列とよび、簡単に XN-1,XN-2,..., XN-j=S と記す) が生じた後、試行 XNで状態 Siが出現する確率が a であることを



と表わす。このとき定常過程は



と表わされ、またマルコフ過程は



と定義される。  (3.4)と(3.5)を同時に満足するとき、つまり定常なマルコフ過程をマルコフ連鎖といい、 次のように表わされる。



 すなわち、任意の系列 Sのあとで状態 Siが生起する確率が、 1つ手前の状態にのみ依存し、かつ時間に依存しない場合にこれをマルコフ連鎖という。  マルコフ連鎖は次のような遷移マトリクスで記述することができる。



 マルコフ連鎖を適用した、ひとつの簡単な例を挙げる[8]。 ある人が車を買い換える場合、 どの車種を選ぶかは、その人が現在所有している車種に依存するであろう。M社、T社、 N社の3車種についての、この割合が例えば次のようであるとする。

Table 1 : 購入車種の割合


所有車種がM社製、T社製、N社製である状態をそれぞれ、S1,S2, S3 とすれば、遷移マトリクス P は、



と書ける。
 車を買い換えるまでの期間を1タイムステップとすれば、Pn は n タイムステップ後の 状態遷移確率を表わすことになる。すなわち、S1,S2, S3 を要素とする状態ベクトルを sとし、初期状態ベクトルをs(0)、 m タイムステップ後の状態ベクトルをs(m)と記せば、



と表わせる。m が大きくなるにつれて、s(m)は一定の値に近づくことが知られて おり[6]、これは、充分時間が経過した後の最終的な状態の割合を表わす。
 (3.9)式を使って、例えば現在M社の車を所有している人の4タイムステップ後の状態、 s(4)を求めると、s(0)=(1 0 0)として、



となる。この人の場合、4タイムステップ後にはN社の車を購入する確率が最も大きくなる ことが分かる。

3.2 SMAP法

 筆者の提案するSMAP法の手順は以下のようである。
  1. 自分のあるべき状態(目標が達成された状態)を特定する。
  2. あるべき状態に関連していると考えられる状態を全て挙げる。
  3. これらの状態間を、遷移確率で結ぶ。状態は、内部状態と外部状態とに分類される。 内部状態は自分自身の状態、外部状態は自分以外の状態である。内部状態と外部状態は互い に遷移してもよい。(例えば自分がAさんに好意を持てばAさんも自分に好意を持つように なるかもしれない。)
  4. 各状態間の遷移確率を要素とする遷移マトリクスを作成する。
  5. 遷移マトリクスに適当な演算を施すことによって、あるべき状態に近づくための最 も効果的な状態を絞りこんでいく。
  6. 絞りこまれた状態を実現すべく行動を起こす。
 この手順は、2.に記したSAD法の手順の「除くべき要因」を「あるべき状態」に、 「外因」を「外部状態」に、「内因」を「内部状態」に、また「影響度」を「遷移確率」 に置き換えたものとほぼ同じになっている。両手法の手順は類似しているが、SMAP法 がSAD法と本質的に異なる点は、マルコフ連鎖を応用することによって、問題を確率過程 として分析すること、すなわちタイムステップの概念を取り入れてあることである。
 上の手順5.の遷移マトリクスの演算法を説明する。
 内部状態を、S1,S2,...,SG、 外部状態を、SG+1,SG+2 ,...,SG+Kとし、これらをまとめて状態行ベクトル



とする。 状態 Siから状態 Sjへの遷移確率 Pij を要素に持つ遷移マトリクス (式(3.7))を P とすると、(3.9)式と同様の計算により、状態 S1,S2,...,Sn の、mタイムステップ後の状態の相対的な存在割合を求めることができる。
 状態 S1,S2,...,Sn のそれぞれに、総和が1となるように相対的な値(初期状態) を付けておき、m の増加とともに状態の割合がどのように変化するかを見ていく。 目的とする状態の存在割合を増加させるには、どの状態(主に外部状態)の割合を強めたら 良いのかを探る。
 上で述べた「状態」の数や内容は、分析の対象となる人(以下被験者という)の抱える問題(悩み) の種類や程度によって千差万別であろう。また「遷移確率」の値も被験者の主観によって設定 されることになる。言い換えれば、一見同じ問題であっても被験者の「個性」によって分析結果 はそれぞれ違ったものになるであろう。得られた分析結果は、普遍的、客観的な意味を持つもの ではなく「その人にとってのみ」有効なのである。従って、状態の種類や遷移確率の値をいかに すべきかという問題を厳密に議論することは、この場合必要なことではない。

4.SMAP法の適用と考察

 SMAP法とSAD法を比較するために、森によって分析された、「不眠症の解消」[5] にSMAP法を適用してみる。遷移マトリクスを次のように設定した。前節でも触れたように、 状態の種類や遷移確率の与え方は、専ら被験者の置かれた環境、性格、人生観などに依るもの であり、被験者以外の人が「客観的な」値を設定しても意味がない。以下の状態と遷移確率は、 森の分析結果と比較するために、「不眠症の解消」の分析対象となった被験者が設定したものに 合わせたものである。



 状態
は外部状態すなわち被験者以外の状態、その他は内部状態 すなわち被験者自身の状態である。初期状態が、




の3つの場合についてそれぞれ、m=1 から10のステップ毎の状態ベクトル、 S(m)を求めた。 1タイムステップは、各状態が他の状態へ遷移するまでの期間である。この期間の長さを 1日とみるか1週間とみるか、あるいは1ヶ月とみるかは被験者により異なるであろう。
 状態ベクトルs(m)の m に対する変動を追跡することもできるが、ここでは上 の3つの場合について、m=10 のときの主な内部状態の実現割合を求めた。なぜなら m が10に近づくころからs(m) がほぼ一定になるからである。その結果をTable 2 に示す。



 Table 2 から次のことが明らかになった。
  1. 「時間が充分にとれる」という状態は、遊べるし勉強もできるようになるが、 仕事が順調になるということにはあまり寄与せず、ストレスの解消にも比較的繋がっていない。
  2. 「資金が潤沢」という状態は、遊びや勉強の時間があまり取れないけれども、仕事を 順調にする効果は最大であり、その結果ストレスの解消に最も役立っている。
  3. 「人手が足りる」状態は、上の2つの場合の中間の傾向を示している。
  4. 以上の3つの場合とも、ストレスがない状態とすぐ眠れる状態の和はほぼ同じ割合になる。
  5. 従って、仕事を順調にこなし、ひいては不眠症を解消するためには、暇を作ったり人手を 充足したりするよりも、多少の無理をしてでも資金を潤沢にすることが最良の方法である。
 この分析結果は、森がSAD法によって分析したものとほぼ同じである[5]。 用いた手法が異なるにもかかわらず分析結果がほぼ同様であるということは何を意味するので あろうか。被験者の抱える問題が同じで、与えた条件が同じであれば、分析結果が同じになる ということはある意味では当然のことであるが、SMAP法がSAD法と同様に正しい手法で あるということを表わしてもいる。言い換えれば、SMAP法は「不眠症の解消」問題だけで なく他のいろいろな問題にも有用な手法であるということを示しているのである。
 またSMAP法はSADと比して以下のような特徴を持っている。
  1. マルコフ連鎖の応用によって時間経過の概念を導入してあるので、各状態の時間による 変化を追跡でき、充分時間が経過した後の最終的な状態も予測できる。
  2. 状態(要因)を結ぶ矢線が要らないので、モデルを表現するための複雑なフローチャートを 書く必要がない。
  3. 内因(内部状態)と外因(外部状態)あるいは内因と内因が相互に影響する場合にも適用できる。
  4. SAD法で障害となっている、矢線が堂々めくりをする場合にもなんら問題なく適用できる。
  5. SAD法で現れた逆マトリクス((2.5)式)を扱わなくともよいので、マトリクス演算が不得 手な被験者にとっても扱いやすい。

5.おわりに

 マルコフ連鎖を応用した問題分析手法、SMAP法の概念をSAD法と比較しながら紹介 してきた。その結果SMAP法は簡単で適用が容易であるにもかかわらず、分析結果はSAD 法と類似することが示された。また前節の「不眠症の解消」の例のような個人の抱える比較的 小さな問題、しかし当人にとっては複雑で出口が見えないような問題に有用であることも分か った。しかし言うまでもないことであるが、SAD法もSMAP法も、改善すべき問題点を明 らかにすることはできるけれども、改善しようとする意志や努力までは提供することはできない。 これはまた別の問題である。
 SMAP法で扱う演算はマトリクスの乗算だけであるので、この計算は,例えば表計算ソフトの エクセルで簡単に行なうことができる。またエクセルの持つグラフ作成機能は分析結果の表示に活 用できる。学生がエクセルを学習する際に、本稿の冒頭に記したような自分の抱えている問題(悩 み)にSMAP法を適用して、自ら解決の糸口を見つけることができれば、これはまさに学習と問 題解決の一石二鳥といえるかもしれない。
 今後は、式(3.7)あるいは式(4.1)に現れた遷移確率の微少な変化が分析結果に及ぼす影響を定量 的に分析する、いわゆる感度分析の研究を行ない、適当なプレゼンテーションツールと組み合わせ た、「SMAP法によるカウンセリングシステム」の開発を進める予定である。
 大学の総合情報処理センターの業務内容は、それぞれの大学によって異なるであろう。 新潟大学では、本稿の冒頭に述べたように、情報処理教育への参加もセンター業務のひとつに なっている。本稿で提案した、SMAP法による問題分析システムは、上に記したように リテラシー教育への適用が容易であり、情報処理教育への寄与は大きい。

謝辞:エクセルの操作法を教えて頂いた、新潟大学経済学部2年稲村真哉君に感謝いたします。

参考文献

[1]
橘 文夫,山崎一生:新潟大学における情報処理教育,新潟大学・大学教育研究年報, Vol.3, 1997, 233-245.

[2]
川喜多二郎:「KJ法」,中央公論社,1986.

[3]
発想法の科学(川喜多二郎著作集4),中央公論社,1995.

[4]
KJ法と未来学(川喜多二郎著作集6),中央公論社,1996.

[5]
森 彰:「コンピュータ創造工学」,日刊工業新聞社,1981.

[6]
例えば,金子哲夫:「マルコフ決定理論入門」,槙書店,1973.
北川敏男編:「マルコフ過程」,情報科学講座,共立出版,1967.

[7]
橘 文夫:人間による乱数列をマルコフ連鎖としてみたときの特性, 情報処理学会論文誌, Vol.20,No. 1, 1979, 1-7.

[8]
大鹿譲訳:「オペレーションズリサーチの基礎」マグロウヒル好学社,1979.



(1997年7月5日受付;1997年8月15日採録)
(Received 5 July 1997 ; accepted 15 August 1997)