《多段確率決定樹表(ツリーテーブル)》

出典: ORWiki

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

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


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


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\, からの２段確率決定樹表

画像:多段階確率決定樹表fig1.jpg

画像:多段階確率決定樹表fig2.jpg


決定樹表(繰り返し法)では, 次のように簡略化している：
履歴 = 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)\,
経路 =\, 経路確率 = p_0 p_1\,
積 =\, 加法 \times\, 経路, 　　部期 =\,部分期待値, 　　全期 =\, 全期待値.


この樹表によって s_{1}\, からの(最適原始決定関数を経て)最適一般決定関数


\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} が得られる. さらに, s_{2},\,s_{3} からの樹表(省略)と合わせると, マルコフ政策\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.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E5%A4%9A%E6%AE%B5%E7%A2%BA%E7%8E%87%E6%B1%BA%E5%AE%9A%E6%A8%B9%E8%A1%A8%28%E3%83%84%E3%83%AA%E3%83%BC%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%29%E3%80%8B" より作成