オッズアルゴリズム

意思決定理論において、オッズアルゴリズム（またはブルスアルゴリズム）は、最適停止問題領域に属する一連の問題に対する最適戦略を計算する数学的手法である。これらの問題の解はオッズ戦略から導かれ、オッズ戦略の重要性はその最適性にある（以下で説明する）。

オッズアルゴリズムは 、ラストサクセス問題と呼ばれる種類の問題に適用されます。正式には、これらの問題の目的は、連続的に観測される独立したイベントのシーケンスにおいて、特定の基準を満たす最後のイベント（「特定イベント」）を特定する確率を最大化することです。この特定は観測時に行う必要があります。以前の観測を再検討することは許可されません。通常、特定イベントは、意思決定者によって、明確に定義された行動をとるために「停止」するという観点から真に重要なイベントとして定義されます。このような問題は、様々な状況で発生します。

例

2 つの異なる状況は、最後の特定のイベントで停止する確率を最大化することの重要性を例示しています。

1. ある車が最高額入札者（最良の「オファー」）に販売されるとします。購入希望者が反応し、車を見たいと申し出ます。各購入者は、売り手が入札を受け入れるか否かを即座に決定することを要求します。入札を興味深いと定義し、以前のすべての入札よりも良い場合は 1 を、そうでない場合は 0 をコード化します。入札は0 と 1 のランダムなシーケンスを形成します。売り手は 1 のみに興味を持ちます。売り手は、連続する 1 が最後の 1 になるのではないかと恐れるかもしれません。定義から、最後の 1 が最高入札額であることがわかります。したがって、最後の 1 で売れる確率を最大化することは、最高ので売れる確率を最大化することを意味します。${\displaystyle n}$
2. 医師は、特別な治療を行う際に、治療が成功した場合はコード1を、そうでない場合はコード0を使用する場合があります。医師は一連の患者を同じように治療し、苦痛を最小限に抑え、一連の反応のある患者全員を治療したいと考えています。このようなランダムな0と1の列の最後の1で治療を止めれば、この目的は達成されます。医師は予言者ではないので、最後の1で治療を止める確率を最大化することが目的です。（「コンパッショネート・ユース」を参照）。${\displaystyle n}$

定義

独立事象のシーケンス を考えます。このシーケンスに、 値 1 または 0 を持つ別の独立事象のシーケンス を関連付けます。ここで 、 は成功と呼ばれ、k 番目の観測が興味深い事象（意思決定者によって定義）であるイベントを表し、 は興味のない事象を表します。これらの確率変数は順次観測され、最後の成功が観測されたときに正しく選択することが目標です。 ${\displaystyle n}$ ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$ ${\displaystyle \,I_{k}=1}$ ${\displaystyle \,I_{k}=0}$ ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$

k番目のイベントが興味深いものになる確率を とします。さらに と とします。 はk番目のイベントが興味深いものになる確率を表しており、これがオッズアルゴリズムの名前の由来です。 ${\displaystyle \,p_{k}=P(\,I_{k}\,=1)}$ ${\displaystyle \,q_{k}=\,1-p_{k}}$ ${\displaystyle \,r_{k}=p_{k}/q_{k}}$ ${\displaystyle \,r_{k}}$

アルゴリズム手順

オッズアルゴリズムはオッズを逆順に合計する

${\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,}$

この合計が初めて1に達するか超えるまで。インデックスsでこれが発生した場合、 sと対応する合計 を保存します。

${\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,}$

オッズの合計が1に達しない場合は、s  = 1に設定します。同時に計算します。

${\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,}$

出力は

1. ${\displaystyle \,s}$ 停止閾値
2. ${\displaystyle \,w=Q_{s}R_{s}}$ 、勝利の確率。

オッズ戦略

オッズ戦略は、イベントを次々に観察し、インデックスs以降の最初の興味深いイベント (存在する場合) で停止するというルールです。ここで、sは出力 a の停止しきい値です。

オッズ戦略、ひいてはオッズ アルゴリズムの重要性は、次のオッズ定理にあります。

オッズ定理

オッズ定理によれば、

1. オッズ戦略は最適です。つまり、最後の 1 で停止する確率を最大化します。
2. オッズ戦略の勝利確率は ${\displaystyle w=Q_{s}R_{s}}$
3. の場合、勝利確率は常に少なくとも1/ e = 0.367879...となり、この下限は可能な限り最良です。${\displaystyle R_{s}\geq 1}$ ${\displaystyle w}$

特徴

オッズアルゴリズムは、最適な戦略と最適な勝率を同時に計算します。また、オッズアルゴリズムの演算回数はnに対して（劣）線形です。したがって、あらゆるシーケンスに対してこれより高速なアルゴリズムは存在し得ず、オッズアルゴリズムは同時にアルゴリズムとしても最適です。

出典

Bruss 2000はオッズアルゴリズムを考案し、その名称を命名しました。Brussアルゴリズム（戦略）とも呼ばれています。無料の実装はウェブ上で見つけることができます。

アプリケーション

アイコンの高さが望ましさを示す秘書問題の 3 つのケース:

1. 探索セットが小さすぎると、最適な候補 (*) が見つかる前に、最適ではない候補が選択されます。
2. 理想的なセットは最良のものを識別します。
3. 大きすぎるセットに最善の候補が含まれている場合は、最後の候補が選択されます。

アプリケーションは、臨床試験における医学的な問題から、販売問題、秘書問題、ポートフォリオ選択、(一方通行)検索戦略、軌道問題、駐車問題、オンラインメンテナンスなどの問題にまで及びます。

同様の考え方に基づき、ポアソン過程のような独立増分を持つ連続時間到着過程に対するオッズ定理が存在する（Bruss 2000）。場合によっては、オッズが必ずしも事前に分かっているとは限らず（上記の例2のように）、オッズアルゴリズムを直接適用することができない。このような場合、各ステップでオッズの逐次推定値を用いることが可能である。これは、未知パラメータの数が観測値の数nに比べて大きくない場合に有効である。しかし、その場合、最適性の問題はより複雑になり、さらなる研究が必要となる。オッズアルゴリズムの一般化により、停止失敗と誤った停止に対して異なる報酬を与えることが可能になり、独立性仮定をより弱い仮定に置き換えることも可能となる（Ferguson 2008）。

バリエーション

Bruss & Paindaveine 2000 は、最後の成功を選択する問題について議論しました。 ${\displaystyle k}$

玉木（2010）は、最後の成功のいずれかで停止するという問題を取り扱う乗法オッズ定理を証明した。勝率の厳密な下限は、松井・阿野（2014）によって導かれている。 ${\displaystyle \ell}$

Matsui & Ano 2017は、直近の成功例から選択する問題を議論し、勝率の厳密な下限値を得た。 この問題がBrussのオッズ問題と等価である場合、 この問題がBruss & Paindaveine 2000の問題と等価である場合、Tamaki 2010で議論された問題は、次のように設定することで得られる。${\displaystyle k}$ ${\displaystyle \ell}$ ${\displaystyle \ell =k=1,}$ ${\displaystyle \ell =k\geq 1,}$ ${\displaystyle \ell \geq k=1.}$

多肢選択問題

プレイヤーは複数の選択肢を持ち、いずれかの選択肢が最後の成功であれば勝利する。古典的な秘書問題については、Gilbert & Mosteller 1966 が の場合について議論した。オッズ問題については、Ano, Kakinuma & Miyoshi 2010 が議論している。オッズ問題のその他の事例については、Matsui & Ano 2016 を参照のこと。 ${\displaystyle r}$ ${\displaystyle r=2,3,4}$ ${\displaystyle r=2,3}$

この問題に対する最適な戦略は、一連の閾値数によって定義される戦略のクラスに属します。 ${\displaystyle (a_{1},a_{2},...,a_{r})}$ ${\displaystyle a_{1}>a_{2}>\cdots >a_{r}}$

具体的には、 からまでラベル付けされた合格通知があるとします。担当者はそれぞれ1通の合格通知を持っています。あなたは候補者との面接を続け、すべての担当者が閲覧できる表に候補者をランク付けします。担当者は、から までのすべての候補者の中で最初に成績が良かった候補者に合格通知を送ります。（送付されなかった合格通知は、標準的な秘書問題と同様に、デフォルトで最後の応募者に渡されます。） ${\displaystyle r}$ ${\displaystyle 1}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle a_{i}}$

のとき、Ano、Kakinuma、Miyoshi 2010 は、勝利確率のタイトな下限が に等しいことを示しました。 一般的な正の整数 の場合、Matsui & Ano 2016 は、勝利確率のタイトな下限が、わずか k 回の試行で上位 k 個の候補者を選択しなければならない秘書問題変種の勝利確率であることを証明しました。 ${\displaystyle r=2}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.}$ ${\displaystyle r}$

のとき、勝利確率の厳密な下限はそれぞれ、、に等しくなり ます。 ${\displaystyle r=3,4,5}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},}$

のさらなる数値例および一般的なケースのアルゴリズムについては、Matsui & Ano 2016 を参照してください。 ${\displaystyle r=6,...,10}$

参照

• オッズ
• 臨床試験
• 拡大されたアクセス
• 秘書問題

参考文献

• 阿野 健; 柿沼 秀; 三好 暢 (2010). 「多重選択確率を考慮したオッズ定理」.応用確率ジャーナル. 47 (4): 1093– 1104. doi : 10.1239/jap/1294170522 . S2CID  17598431.
• Bruss, F. Thomas (2000). 「オッズを1に合計して停止する」. 『確率年報』. 28 (3). 数理統計研究所: 1384–139 ​​1. doi : 10.1214/aop/1019160340 . ISSN  0091-1798.
  • 「最適停止のオッズ定理の境界に関する注記」、Annals of Probability Vol. 31、1859–1862、(2003)。
  • 「正しい決断の技術」、ヨーロッパ数学会ニュースレター、第62号、14-20、(2005年)。
• TSファーガソン：（2008年、未発表）
• Bruss, FT; Paindaveine, D. (2000). 「独立試行における最後の成功のシーケンスの選択」(PDF) .応用確率ジャーナル. 37 (2): 389– 399. doi :10.1239/jap/1014842544.
• ギルバート, J; モステラー, F (1966). 「数列の最大値の認識」アメリカ統計学会誌. 61 (313): 35– 73. doi :10.2307/2283044. JSTOR  2283044.
• 松井 剛; 阿野 健 (2014). 「最適停止の乗法オッズ定理の下限値に関する考察」応用確率誌. 51 (3): 885– 889. doi : 10.1239/jap/1409932681 .
• 松井 剛; 阿野 健 (2016). 「多重停止を伴うBrussのオッズ問題の下限値」.オペレーションズ・リサーチ数学. 41 (2): 700– 714. arXiv : 1204.5537 . doi :10.1287/moor.2015.0748. S2CID  31778896.
• 松井 剛; 阿野 健 (2017). 「オッズの対称多項式の比を1と比較し、停止する」応用確率ジャーナル. 54 : 12–22 . doi :10.1017/jpr.2016.83. S2CID  41639968.
• Shoo-Ren HsiaoとJiing-Ru. Yang：「マルコフ依存試行における最後の成功の選択」、Journal of Applied Probability、第93巻、271-281ページ、(2002年)。
• Tamaki, M (2010). 「乗法オッズを1まで合計して停止する」.応用確率ジャーナル. 47 (3): 761– 777. doi : 10.1239/jap/1285335408 . S2CID  32236265.
• 玉木光志：「軌道上の最適停止と投票問題」、応用確率誌第38巻、946-959 (2001)。
• E. Thomas、E. Levrat、B. Iung: 「L'algorithme de Bruss comme conmetribution à une main preventive」、Sciences et Technologies de l'automation、Vol. 4、13-18 (2007)。

外部リンク

• Bruss Algorithmus http://www.p-roesler.de/odds.html