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

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

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

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}\,$ からの２段確率決定樹表

スタイル検討

表2：状態 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_1\, } からの２段確率決定樹表(続き)

スタイル検討

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

履歴 = $x_{0}~~r_{0}(u_{0})\,$／構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u_0~~p_0~~x_1~~r_{1}(u_1)\,} ／構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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})\,$

加法 $=\,$ 評価値の和 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle = 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 =\,} 経路確率 構文解析に失敗 (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 =\, } 加法 構文解析に失敗 (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}\, } からの(最適原始決定関数を経て)最適一般決定関数

$\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}$

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

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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.