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

【ただんかくりつけっていじゅひょう (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}\,$ からの２段確率決定樹表

\begin{table}[ht] \caption{状態 $s_1$ からの２段確率決定樹表} \begin{center}\footnotesize\renewcommand{\arraystretch}{0.91} \begin{tabular}{|cr@{\hspace*{0.5mm}}|c|l|l|c|c|} \hline \multicolumn{2}{|c|}{\makebox[62.6mm][c]{履歴}}& \makebox[0.1mm][c]{加法} & {経路} & \multicolumn{1}{|c|}{積} & \multicolumn{1}{|c|}{部期} & {全期}\\ \hline \hline &$s_1$ 0.3 & 2.0 & {\it 0.64} & 1.28 & & \\ &$s_2$ 1.0 & 2.7 & {\it 0.08} & 0.216 & \makebox[6mm][c]{1.696} & \\ &$s_3$ 0.8 & 2.5 & {\it 0.08} & 0.2 & & \\ \cline{3-5} &$s_1$ 0.3 & 1.6 & {\it 0.08} & 0.128 & & \\ &$s_2$ 1.0 & 2.3 & {\it 0.72} & 1.656 & \makebox[6mm][c]{\bf 1.784} & \\ &$s_3$ 0.8 & 2.1 & {\it 0.0} & 0 & & \\ \cline{3-6} &$s_1$ 0.3 & 2.0 & {\it 0.0} & 0 & & \\ &$s_2$ 1.0 & 2.7 & {\it 0.01} & 0.027 & \makebox[6mm][c]{\bf 0.252} & \\ &$s_3$ 0.8 & 2.5 & {\it 0.09} & 0.225 & & \makebox[6mm][c]{2.248} \\

\cline{3-5}

&$s_1$ 0.3 & 1.6 & {\it 0.08} & 0.128 & & \\ &$s_2$ 1.0 & 2.3 & {\it 0.01} & 0.023 & \makebox[6mm][c]{0.172} & \\ &$s_3$ 0.8 & 2.1 & {\it 0.01} & 0.021 & & \\ \cline{3-6} &$s_1$ 0.3 & 2.0 & {\it 0.08} & 0.16 & & \\ &$s_2$ 1.0 & 2.7 & {\it 0.01} & 0.027 & \makebox[6mm][c]{\bf 0.212} & \\ &$s_3$ 0.8 & 2.5 & {\it 0.01} & 0.025 & & \\ \cline{3-5} &$s_1$ 0.3 & 1.6 & {\it 0.01} & 0.016 & & \\ &$s_2$ 1.0 & 2.3 & {\it 0.0} & 0 & \makebox[6mm][c]{0.205} & \\ &$s_3$ 0.8 & 2.1 & {\it 0.09} & 0.189 & & \\ %\cline{3-7} \hline \end{tabular} \end{center}

\vspace*{-228mm}\hspace*{6mm} \setlength{\unitlength}{0.001in} %\setlength{\unitlength}{0.0001in} \begin{picture}(2300,5750)(0,0) \special{pn 8}%

\special{pa 1600 492.4}% \special{pa 2270 340}% \special{fp}% \special{pa 1600 492.4}% \special{pa 2270 492.4}% \special{fp}% \special{pa 1600 492.4}% \special{pa 2270 644.8}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 949.6}% \special{pa 2270 797.2}% \special{fp}% \special{pa 1600 949.6}% \special{pa 2270 949.6}% \special{fp}% \special{pa 1600 949.6}% \special{pa 2270 1102}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 1406.8}% \special{pa 2270 1254.4}% \special{fp}% \special{pa 1600 1406.8}% \special{pa 2270 1406.8}% \special{fp}% \special{pa 1600 1406.8}% \special{pa 2270 1559.2}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 1864}% \special{pa 2270 1711.6}% \special{fp}% \special{pa 1600 1864}% \special{pa 2270 1864}% \special{fp}% \special{pa 1600 1864}% \special{pa 2270 2016.4}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 2321.2}% \special{pa 2270 2168.8}% \special{fp}% \special{pa 1600 2321.2}% \special{pa 2270 2321.2}% \special{fp}% \special{pa 1600 2321.2}% \special{pa 2270 2473.6}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 2778.4}% \special{pa 2270 2626}% \special{fp}% \special{pa 1600 2778.4}% \special{pa 2270 2778.4}% \special{fp}% \special{pa 1600 2778.4}% \special{pa 2270 2930.8}% \special{fp}%

\special{pa 1000 721}% \special{pa 1600 492.4}% \special{da 0.05}% \special{pa 1000 721}% \special{pa 1600 949.6}% \special{da 0.05}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1000 1635.4}% \special{pa 1600 1406.8}% \special{da 0.05}% \special{pa 1000 1635.4}% \special{pa 1600 1864}% \special{da 0.05}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1000 2549.8}% \special{pa 1600 2321.2}% \special{da 0.05}% \special{pa 1000 2549.8}% \special{pa 1600 2778.4}% \special{da 0.05}%

\special{pa 500 1635.4}% \special{pa 1000 721}% \special{fp}% \special{pa 500 1635.4}% \special{pa 1000 1635.4}% \special{fp}% \special{pa 500 1635.4}% \special{pa 1000 2549.8}% \special{fp}%

\special{pa 180 3007}% \special{pa 500 1635.4}% \special{da 0.05}%

\put(300,-2950){\makebox(0,0){$s_1$}} \put(1000,-621){\makebox(0,0){$s_1$}} \put(1000,-1735.4){\makebox(0,0){$s_2$}} \put(1000,-2649.8){\makebox(0,0){$s_3$}}

\put(400,-2507){\makebox(0,0){$a_1$}}

\put(1400,-644.8){\makebox(0,0){$a_1$}} \put(1400,-949.6){\makebox(0,0){$a_2$}} \put(1400,-1559.2){\makebox(0,0){$a_1$}} \put(1400,-1864){\makebox(0,0){$a_2$}} \put(1400,-2473.6){\makebox(0,0){$a_1$}} \put(1400,-2778.4){\makebox(0,0){$a_2$}}

\put(200,-2407){\makebox(0,0){\small 0.7}}

\put(700,-1021){\makebox(0,0){\small\it 0.8}} \put(800,-1535.4){\makebox(0,0){\small\it 0.1}} \put(700,-2249.8){\makebox(0,0){\small\it 0.1}}

\put(1200,-542.4){\makebox(0,0){\small 1.0}} \put(1300,-749.6){\makebox(0,0){\small 0.6}} \put(1200,-1456.8){\makebox(0,0){\small 1.0}} \put(1300,-1664){\makebox(0,0){\small 0.6}} \put(1200,-2371.2){\makebox(0,0){\small 1.0}} \put(1300,-2578.4){\makebox(0,0){\small 0.6}}

\put(1900,-340){\makebox(0,0){\small\it 0.8}} \put(2100,-432.4){\makebox(0,0){\small\it 0.1}} \put(2100,-542.4){\makebox(0,0){\small\it 0.1}} \put(1900,-797.2){\makebox(0,0){\small\it 0.1}} \put(2100,-889.6){\makebox(0,0){\small\it 0.9}} \put(2100,-999.6){\makebox(0,0){\small\it 0.0}} \put(1900,-1244.4){\makebox(0,0){\small\it 0.0}} \put(2100,-1336.8){\makebox(0,0){\small\it 0.1}} \put(2100,-1446.8){\makebox(0,0){\small\it 0.9}} \put(1900,-1701.6){\makebox(0,0){\small\it 0.8}} \put(2100,-1794){\makebox(0,0){\small\it 0.1}} \put(2100,-1904){\makebox(0,0){\small\it 0.1}} \put(1900,-2153.8){\makebox(0,0){\small\it 0.8}} \put(2100,-2246.2){\makebox(0,0){\small\it 0.1}} \put(2100,-2356.2){\makebox(0,0){\small\it 0.1}} \put(1900,-2626){\makebox(0,0){\small\it 0.1}} \put(2100,-2703.4){\makebox(0,0){\small\it 0.0}} \put(2100,-2813.4){\makebox(0,0){\small\it 0.9}}

\end{picture} \end{table} %

\clearpage

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

\begin{table}[ht] \caption{状態 $s_1$ からの２段確率決定樹表(続き)}

\begin{center}\footnotesize\renewcommand{\arraystretch}{0.91} \begin{tabular}{|cr@{\hspace*{0.5mm}}|c|l|l|c|c|} \hline \multicolumn{2}{|c|}{\makebox[62.6mm][c]{履歴}}& \makebox[0.1mm][c]{加法} & {経路} & \multicolumn{1}{|c|}{積} & \multicolumn{1}{|c|}{部期} & {全期}\\ \hline \hline &$s_1$ 0.3 & 2.3 & {\it 0.08} & 0.184 & & \\ &$s_2$ 1.0 & 3.0 & {\it 0.01} & 0.03 & \makebox[6mm][c]{0.242} & \\ &$s_3$ 0.8 & 2.8 & {\it 0.01} & 0.028 & & \\ \cline{3-5} &$s_1$ 0.3 & 1.9 & {\it 0.01} & 0.019 & & \\ &$s_2$ 1.0 & 2.6 & {\it 0.09} & 0.234 & \makebox[6mm][c]{\bf 0.253} & \\ &$s_3$ 0.8 & 2.4 & {\it 0.0} & 0 & & \\ \cline{3-6} &$s_1$ 0.3 & 2.3 & {\it 0.0} & 0 & & \\ &$s_2$ 1.0 & 3.0 & {\it 0.09} & 0.27 & \makebox[6mm][c]{\bf 2.538} & \\ &$s_3$ 0.8 & 2.8 & {\it 0.81} & 2.268 & & \makebox[6mm][c]{\bf 2.791} \\

\cline{3-5}

&$s_1$ 0.3 & 1.9 & {\it 0.72} & 1.368 & & \\ &$s_2$ 1.0 & 2.6 & {\it 0.09} & 0.234 & \makebox[6mm][c]{1.818} & \\ &$s_3$ 0.8 & 2.4 & {\it 0.09} & 0.216 & & \\ \cline{3-6} &$s_1$ 0.3 & 2.3 & {\it 0.0} & 0 & & \\ &$s_2$ 1.0 & 3.0 & {\it 0.0} & 0 & \makebox[6mm][l]{\bf 0} & \\ &$s_3$ 0.8 & 2.8 & {\it 0.0} & 0 & & \\ \cline{3-5} &$s_1$ 0.3 & 1.9 & {\it 0.0} & 0 & & \\ &$s_2$ 1.0 & 2.6 & {\it 0.0} & 0 & \makebox[6mm][l]{\bf 0} & \\ &$s_3$ 0.8 & 2.4 & {\it 0.0} & 0 & & \\ \hline \end{tabular} \end{center}

\vspace*{-228mm}\hspace*{6mm} \setlength{\unitlength}{0.001in} %\setlength{\unitlength}{0.0001in} \begin{picture}(2300,5750)(0,-2700) \special{pn 8}%

\special{pa 1600 3235.6}% \special{pa 2270 3083.2}% \special{fp}% \special{pa 1600 3235.6}% \special{pa 2270 3235.6}% \special{fp}% \special{pa 1600 3235.6}% \special{pa 2270 3388}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 3692.8}% \special{pa 2270 3540.4}% \special{fp}% \special{pa 1600 3692.8}% \special{pa 2270 3692.8}% \special{fp}% \special{pa 1600 3692.8}% \special{pa 2270 3845.2}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 4150}% \special{pa 2270 3997.6}% \special{fp}% \special{pa 1600 4150}% \special{pa 2270 4150}% \special{fp}% \special{pa 1600 4150}% \special{pa 2270 4302.4}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 4607.2}% \special{pa 2270 4454.8}% \special{fp}% \special{pa 1600 4607.2}% \special{pa 2270 4607.2}% \special{fp}% \special{pa 1600 4607.2}% \special{pa 2270 4759.6}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 5064.4}% \special{pa 2270 4912}% \special{fp}% \special{pa 1600 5064.4}% \special{pa 2270 5064.4}% \special{fp}% \special{pa 1600 5064.4}% \special{pa 2270 5216.8}% \special{fp}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1600 5521.6}% \special{pa 2270 5369.2}% \special{fp}% \special{pa 1600 5521.6}% \special{pa 2270 5521.6}% \special{fp}% \special{pa 1600 5521.6}% \special{pa 2270 5674}% \special{fp}%

\special{pa 1000 3464.2}% \special{pa 1600 3235.6}% \special{da 0.05}% \special{pa 1000 3464.2}% \special{pa 1600 3692.8}% \special{fp}% \special{pa 1000 4378.6}% \special{pa 1600 4150}% \special{fp}% \special{pa 1000 4378.6}% \special{pa 1600 4607.2}% \special{da 0.05}% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \special{pa 1000 5293}% \special{pa 1600 5064.4}% \special{fp}% \special{pa 1000 5293}% \special{pa 1600 5521.6}% \special{fp}%

\special{pa 500 4378.6}% \special{pa 1000 3464.2}% \special{fp}% \special{pa 500 4378.6}% \special{pa 1000 4378.6}% \special{fp}% \special{pa 500 4378.6}% \special{pa 1000 5293}% \special{fp}%

\special{pa 180 3007}% \special{pa 500 4378.6}% \special{fp}%

\put(300,-3067){\makebox(0,0){$s_1$}}

\put(1000,-3344.2){\makebox(0,0){$s_1$}} \put(1000,-4458.6){\makebox(0,0){$s_2$}} \put(1000,-5373){\makebox(0,0){$s_3$}}

\put(400,-3507){\makebox(0,0){$a_2$}}

\put(1400,-3368){\makebox(0,0){$a_1$}} \put(1400,-3672.8){\makebox(0,0){$a_2$}} \put(1400,-4282.4){\makebox(0,0){$a_1$}} \put(1400,-4587.2){\makebox(0,0){$a_2$}} \put(1400,-5196.8){\makebox(0,0){$a_1$}} \put(1400,-5501.6){\makebox(0,0){$a_2$}}

\put(200,-3607){\makebox(0,0){\small 1.0}}

\put(700,-3744.2){\makebox(0,0){\small\it 0.1}} \put(800,-4258.6){\makebox(0,0){\small\it 0.9}} \put(700,-4973){\makebox(0,0){\small\it 0.0}}

\put(1200,-3265.6){\makebox(0,0){\small 1.0}} \put(1300,-3472.8){\makebox(0,0){\small 0.6}} \put(1200,-4180){\makebox(0,0){\small 1.0}} \put(1300,-4387.2){\makebox(0,0){\small 0.6}} \put(1200,-5094.4){\makebox(0,0){\small 1.0}} \put(1300,-5301.6){\makebox(0,0){\small 0.6}}

\put(1900,-3063.2){\makebox(0,0){\small\it 0.8}} \put(2100,-3155.6){\makebox(0,0){\small\it 0.1}} \put(2100,-3265.6){\makebox(0,0){\small\it 0.1}} \put(1900,-3525.4){\makebox(0,0){\small\it 0.1}} \put(2100,-3607.8){\makebox(0,0){\small\it 0.9}} \put(2100,-3717.8){\makebox(0,0){\small\it 0.0}} \put(1900,-3972.6){\makebox(0,0){\small\it 0.0}} \put(2100,-4065){\makebox(0,0){\small\it 0.1}} \put(2100,-4175){\makebox(0,0){\small\it 0.9}} \put(1900,-4424.8){\makebox(0,0){\small\it 0.8}} \put(2100,-4517.2){\makebox(0,0){\small\it 0.1}} \put(2100,-4627.2){\makebox(0,0){\small\it 0.1}} \put(1900,-4882){\makebox(0,0){\small\it 0.8}} \put(2100,-4974.4){\makebox(0,0){\small\it 0.1}} \put(2100,-5084.4){\makebox(0,0){\small\it 0.1}} \put(1900,-5339.2){\makebox(0,0){\small\it 0.1}} \put(2100,-5431.6){\makebox(0,0){\small\it 0.0}} \put(2100,-5541.6){\makebox(0,0){\small\it 0.9}} \end{picture} \end{table} \clearpage %

% % \begin{center}

\begin{tabular}{cccc}
    $u_t=a_1$ & \hspace{30mm} &Orsjwiki 2007年7月3日 (水) 15:52 (JST)& $u_t=a_2$ \\
      \cline{1-1}\cline{4-4}

\end{tabular} \end{center} \begin{center}

\begin{tabular}{ccccccccc}
     \cline{1-4}\cline{6-9}
 \multicolumn{1}{r|}{$x_t＼x_{t+1}$} & $s_1$ & $s_2$ & $s_3$ & 

2007年7月3日 (水) 15:52 (JST)Orsjwiki 2007年7月3日 (水) 15:52 (JST)& \multicolumn{1}{r|}{$x_t＼x_{t+1}$} & $s_1$ & $s_2$ & $s_3$ \\

 \cline{1-4}\cline{6-9} \\
 \noalign{\vskip-4.3mm}
\multicolumn{1}{c|}{$s_1$} & {\it 0.8} & {\it 0.1} & {\it 0.1} & &

\multicolumn{1}{c|}{$s_1$} & {\it 0.1} & {\it 0.9} & {\it 0.0} \\

\multicolumn{1}{c|}{$s_2$} & {\it 0.0} & {\it 0.1} & {\it 0.9} & &

\multicolumn{1}{c|}{$s_2$} & {\it 0.8} & {\it 0.1} & {\it 0.1} \\

\multicolumn{1}{c|}{$s_3$} & {\it 0.8} & {\it 0.1} & {\it 0.1} & &

\multicolumn{1}{c|}{$s_3$} & {\it 0.1} & {\it 0.0} & {\it 0.9} \\

 \cline{1-4}\cline{6-9}
\end{tabular}

\end{center}

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

履歴 = 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) \\ & & \mbox{ただし}~ p_0 = p(x_1 | x_0,u_0), Orsjwiki 2007年7月3日 (水) 15:52 (JST)p_1 = p(x_2 | x_1,u_1) \\ & & \mbox{加法} = \mbox{評価値の和} = r_{0}(u_0) + r_{1}(u_1) + r_G(x_2) \\ & & \mbox{経路} = \mbox{経路確率} = p_0 p_1 \\ & & \mbox{積} = \mbox{加法} \times \mbox{経路},2007年7月3日 (水) 15:52 (JST)\mbox{部期} =

\mbox{部分期待値},2007年7月3日 (水) 15:52 (JST)\mbox{全期} = \mbox{全期待値}.  

\end{eqnarray*}

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

$$\sigma_{0}(s_{1}) = a_{2};2007年7月3日 (水) 15:52 (JST)\sigma_{1}(s_{1}, s_{1}) =

a_{2},Orsjwiki\sigma_{1}(s_{1}, s_{2}) = a_{1},Orsjwiki\sigma_{1}(s_{1}, s_{3}) =
a_{1},a_{2}  $$

および最大値 $V_{1}(s_{1}) = {\bf 2.791} $ が得られる. さらに, $s_{2},\,s_{3} $からの樹表(省略)と合わせると, マルコフ政策

$ \pi = \{\pi_{0}, \pi_{1} \} $ :$$\pi_{0}(s_{1}) = a_{2},Orsjwiki\pi_{0}(s_{2})
= a_{2},Orsjwiki\pi_{0}(s_{3}) = a_{2}$$

$$\pi_{1}(s_{1}) = a_{2},Orsjwiki\pi_{1}(s_{2}) = a_{1},Orsjwiki\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.