最適停止とは?

Weblio 辞書 > 学問 > OR事典 > 最適停止の意味・解説 

最適停止

読み方さいてきていし
【英】:optimal stopping

概要

結合分布既知である確率変数X_1, X_2, \cdots \,,と実数利得関数y_0, \ y_1(x_1), \,  \ y_2(x_1, x_2), \,  \cdots, \ y_{\infty}(x_1, x_2,\dots) \,に対して, 逐次確率変数X_1 \,, X_2 \,, \cdots \,観測し, 各n \,段階においてX_1=x_1, X_2=x_2, \cdots, X_n=x_n \,観測後に観測停止して利得y_n(x_1, \dots, x_n) \,を得るか, 継続してX_{n+1} \,観測するかを決定下す.このとき, 期待利得最大にする(もしくは期待費用最小化する)停止時刻を求めるのが最適停止問題である.

詳説

 逐次観測される確率変数に基づき, 期待利得最大化したり期待費用最小化するためにある行動を取る時刻を選ぶ問題最適停止問題という. 最適停止は次の2つの要素を持つ. (i) 結合分布既知である確率変数列: X_1, X_2, \cdots\, , (ii) 実数利得関数列: y_0, \ y_1(x_1), \ y_2(x_1, x_2), \cdots ,\, \ y_{\infty}(x_1, x_2, \cdots)\, . 逐次確率変数X_1\, , X_2\, , \cdots\, 観測し, 最初n\, 段階においてX_1=x_1,X_2=x_2, \cdots, X_n=x_n\, 観測後に観測停止して利得y_n(x_1, \cdots, x_n)\, を得るか, 継続してX_{n+1}\, 観測するかの決定下す. 全く観測しないならばy_0\, , 決して停止しないならばy_{\infty}(x_1, x_2, \cdots)\, 利得を得る.このとき, 利得最大にするタイミングである停止時刻を求めるのが最適停止問題である.要素の(ii)は, Y_n=y_n(X_1, \cdots , X_n)\, としたとき, (ii') 結合分布既知である利得を表す確率変数列: Y_0, \ Y_1, \ Y_2, \ \cdots, \ Y_{\infty},\, してもよい. このとき, E(Y_N)\, 最大にする停止時N\, 求めるのが最適停止問題であるとも記述できる. Y_N\, 利得ではなく何らかの費用損失解釈すると, 費用ないし損失最小にする停止規則(時刻)N\, 求め問題となる.

 より一般的には, 最適停止問題次の様に記述されている. 確率空間 (\Omega, {\mathcal F}, P)\, 与えられ, {\mathcal F}_n\, X_1, \cdots, X_n\, によって生成される \mathcal F\, 部分 \sigma\, 集合, {\mathcal F}_0=\{\Omega, \phi\}, {\mathcal F}\, \cup {\mathcal F}_n\, によって生成される \sigma\, 集合とし, {\mathcal F}_0 \subset {\mathcal F}_1 \subset \cdots\subset {\mathcal F}_n \subset \cdots\subset {\mathcal F}_{\infty} \subset {\mathcal F}\, とする. (i)(ii) にかわり(i') 増加部分\sigma\, 集合列:{\mathcal F}_0 \subset {\mathcal F}_1 \subset \cdots \subset {\mathcal F}_{\infty}\subset {\mathcal F}\, , (ii") 結合分布既知利得を表す確率変数列: Y_0,Y_1, \cdots, Y_n, \cdots, Y_{\infty}\, ,とし, Y_n\, {\mathcal F}_n\, -可測, n=0, 1, \cdots, \infty\, とする. \{N=n\}\in {\mathcal F}_n\, である非負整数確率変数N\, 停止規則と定義する. (この定義は, いつ停止するかの決定今まで観測のみに基づき, 将来観測には基づかないと解釈するとわかりやすい.) このとき E(Y_N)\, 最大にする停止規則N\, 求めるのが最適停止問題である. 一般に全ての最適停止問題を解くことは難しいが, 有限期間問題単調問題(monotone problem)は解くことができる. 確率変数X_1, X_2, \cdots, X_n, n<\infty\, 観測後に必ず停止なければならないとき, 有限期間問題と呼ぶ.有限期間問題は基本的に向き帰納法 (backward induction) によって解かれる. n\, 期では停止なければならないので, V_n^{(n)}\, V_n^{(n)}(x_1, \cdots, x_n)=y_n(x_1, \cdots, x_n)\, と定義する. (n-1)\, 期では, ここで停止したときの利得 y_{n-1}(x_1, \cdots, x_{n-1})\, と, 継続してn\, 期で停止したときの期待利得 \mbox{E} (V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\, 比較すれば, (n-1)\, 期で停止すべきか継続すべきかが判明する. V_{n-1}^{(n)}(x_1, \cdots, x_{n-1})\, 次のように定義する. V_{n-1}^{(n)}(x_1, \cdots, x_n) = \max\{y_{n-1}(x_1, \cdots, x_{n-1}), \mbox{E}(V_n^{(n)}(x_1, \cdots, x_{n-1}, X_n)|X_1 = x_1, \cdots, X_{n-1}=x_{n-1})\}.\, 同様に j=n-2, n-3, \cdots, 0\, 後ろ向きV_j^{(n)}(x_1, \cdots, x_j)\, を定義し,


\begin{array}{ll}
V_j^{(n)}(x_1,\cdots, x_j) = & \max\{y_j(x_1,\cdots, x_j), \\
& \quad \mbox{E} (V_{j+1}^{(n)}
 (x_1,\cdots, x_j, X_{j+1})|X_1=x_1,\cdots,
X_j=x_j) \}
\end{array}\,


とする. このように定義された V_j^{(n)}(x_1, \cdots, x_j)\, は, X_1=x_1, \cdots\, , X_j=x_j\, 観測してj\, 期から始めたときの最大期待利得を表し, 上式は最適方程式呼ばれる. これは動的計画最適性の原理によって得られる関数再帰方程式に他ならず, DP(ダイナミック\cdot\, プログラミング)方程式とも呼ばれる. j\, 期においては, 停止して得られる利得y_j(x_1, \cdots, x_j)\, j\, 期より継続して得られる最大期待利得\mbox{E}(V_{j+1}^{(n)}(x_1, \cdots, x_j, X_{j+1})|X_1 = x_1, \cdots, X_j=x_j)\, より良ければ停止し, 逆ならば継続するのが良い. それゆえに, 有限期間問題の最適停止規則N\, は, 初めV_j^{(n)}(x_1, \cdots, x_j)=y_j(x_1, \cdots, x_j)\, となるj\, 停止することである. 有限期間問題最大期待利得は, V_0^{(n)}\, となる.

 最適停止問題において, 事象A_n=\{Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\, , n=0, 1, 2, \cdots\, \textstyle A_0 \subset A_1 \subset \cdots \subset;\ {\bigcup}_1^{\infty} A_n=\Omega \, (almost surely) を満たしているとき単調問題とよぶ. 単調問題では, ある条件の下で([1]参照) OLA (one-stage look-ahead) 停止規則N:=\min\{n\ge 0: Y_n\ge E(Y_{n+1}|{\mathcal F}_n)\}\, が最適停止規則となる. OLA 停止規則とは, もう1期だけ継続してから停止するよりも, 今停止するほうがよいときに停止することを要求する規則である.

 独自のクラス形成してきたといえる確率最大化最適停止問題秘書問題がある. 秘書問題結婚問題とも呼ばれ, 最も基本となる古典的秘書問題次のように記述される. 1人の秘書雇いたい. 面接した応募者には同ランクはなくランク付けが可能とする. 1人ずつ面接する毎に, 今まで面接した応募者の相対ランクに基づき採用するか否か決めなければならず, 一度不採用にした応募者を採用することはできない. n\, 人の応募者があり, n\, 人の面接順列一つ実現する確率1/n!\, のとき, n\, 人中のベストランクを得る確率最大にする最適停止規則求めたい. 最適停止規則は, r^{\ast}-1\, 番目までの応募者は全て採用見送り, それ以降最初に面接する相対的ベスト応募者を採用しなさい, となり, ここで, \textstyle r^{\ast}=\min\{i\ge 1:\sum_{j=i}^{n-1}(1/j) \le 1\}\, によりr^{\ast}\, 与えられる. n\to \infty\, のとき, r^{\ast}/n \to 1/{\rm e} \approx 0.3678\, となる. 大まかに言うと, n\, が十分大きいとき, 36.8%まではパスしてそれ以 降到着する相対的ベスト応募者を採用するのが最適である.



参考文献

[1] Y. S. Chow, H. Robbins and D. Siegmund, Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin Company, Boston, 1971.

[2] T. S. Ferguson, "Who Solved the Secretary Problem?," Statistical Science, 4 (1989), 282-289.

[3] A. N. Shiryaev, Optimal Stopping Rules, Springer-Verlag, New York, 1978.

[4] J. L. Snell, ""Applications of Martingale System Theorems," Trans. Amer. Math. Soc., 73 (1952), 293-312.

[5] S. M. Ross, Applied Probability Models with Optimization Applications, Holden - Day, San Francisco, 1970.



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「最適停止」の関連用語

最適停止のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



最適停止のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2020 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2020 Weblio RSS