多段確率決定樹表

【ただんかくりつけっていじゅひょう (multistage stochastic decision tree-table)】

概要

多段期待値最適化において, 問題から最適解に至るまでを1枚に図解したもの. 問題は樹(ツリー)に, 計算過程は表(テーブル)に, 最適解は樹表(ツリー・テーブル)にそれぞれ図示される. 方法としては全数列挙法(total enumeration method)であるが, 最適解の構成までが簡単明瞭に表わされている. この樹表から, 原始政策, 一般政策, マルコフ政策が生成される状況が分かる. 特に, 加法型評価に対してはマルコフ政策が最適になることが読み取れる.

詳説

　多段確率決定樹表 (ツリーテーブル) は, いわゆる決定樹(ディシジョンツリー), 決定表(ディシジョンテーブル)をそれぞれ進化発展させ, 多段階にわたる確率決定過程の問題記述から最適解構成に至るまでを１枚に統合した図表である. 問題のデータを過程の進行状況に応じて配列し, あらゆる可能な経路とその評価値と確率を図示し, 各段における最適決定の選択を明示している. この意味では列挙法の解構成を与えている. この樹表ではあらゆる型の評価関数の期待値最適化, 確率最適化が解かれる. 樹表には問題に応じて繰り返し法, 直接法などいくつかの型がある[1][2][3].

　ここでは3状態2決定2段(3-2-2)モデルで加法型最適化問題：

${\begin{array}{ll}{\mbox{max.}}&{\mbox{E}}[\,r_{0}(u_{0})+r_{1}(u_{1})+r_{G}(x_{2})\,]\\{\mbox{s. t.}}&p(\,\cdot \,|x_{n},u_{n})\sim x_{n+1}~\,(n=0,1,u_{0}\in U),\ u_{1}\in U,\end{array}}$

を考える. ただし, 数値は次の通り：

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r_{0}(a_{1}) = 0.7 \quad r_{0}(a_{2}) = 1.0; \quad r_{1}(a_{1}) = 1.0 \quad r_{1}(a_{2}) = 0.6}

$r_{G}(s_{1})=0.3\quad r_{G}(s_{2})=1.0\quad r_{G}(s_{3})=0.8$

表1：状態 $s_{1}\,$ からの２段確率決定樹表

決定樹表(繰り返し法)では, 次のように簡略化している：

履歴 = $x_{0}~~r_{0}(u_{0})\,$／$u_{0}~~p_{0}~~x_{1}~~r_{1}(u_{1})\,$／$u_{1}~~p_{1}~~x_{2}~~r_{G}(x_{2})\,$

ただし $p_{0}=p(x_{1}|x_{0},u_{0}),~p_{1}=p(x_{2}|x_{1},u_{1})\,$

加法 $=\,$ 評価値の和 $=r_{0}(u_{0})+r_{1}(u_{1})+r_{G}(x_{2})\,$

経路 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle =\,} 経路確率 $=p_{0}p_{1}\,$

積 $=\,$ 加法 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \times\,} 経路, 　　部期 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle =\, } 部分期待値, 　　全期 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle =\, } 全期待値.

この樹表によって 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_{1}\, } からの(最適原始決定関数を経て)最適一般決定関数

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma_{0}(s_{1}) = a_{2}; \quad \sigma_{1}(s_{1}, s_{1}) = a_{2}, \quad \sigma_{1}(s_{1}, s_{2}) = a_{1}, \quad \sigma_{1}(s_{1}, s_{3}) = a_{1},a_{2}}

および最大値 $V_{1}(s_{1})=\mathbf {2.791}$ が得られる. さらに, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_{2},\,s_{3}} からの樹表(省略)と合わせると, マルコフ政策構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \pi = \{\pi_{0}, \pi_{1} \} : \, }

$\pi _{0}(s_{1})=a_{2},\quad \pi _{0}(s_{2})=a_{2},\quad \pi _{0}(s_{3})=a_{2}$

$\pi _{1}(s_{1})=a_{2},\quad \pi _{1}(s_{2})=a_{1},\quad \pi _{1}(s_{3})=a_{1}$

が最適になっていることがわかる. これは加法型特有の性質である. 一般に, 任意の評価関数に対しては, 原始政策, したがって一般政策が最適になる.

---

参考文献

[1] S. Iwamoto and T. Fujita, "Stochastic Decision-making in a Fuzzy Environment," Journal of the Operations Research Society of Japan, 38 (1995), 467-482.

[2] T. Fujita and K. Tsurusaki, "Stochastic Optimization of Multiplicative Functions with Negative Value," Journal of the Operations Research Society of Japan, 41 (1998), 351-373.

[3] S. Iwamoto, K. Tsurusaki and T. Fujita, "Conditional Decision-making in a Fuzzy Environment," Journal of the Operations Research Society of Japan, 42 (1999), 198-218.