基礎統計(26)マルチパスワード制限アルゴリズム

3800 ワード
統計 テキストリンク

📈 クリーンアップ用語

  • マルチアームバンディ(MAB、マルチアームバンディ):お客様が選択できるハンドルは、複数の仮想スロットマシンであり、各ハンドルには異なる収益があります.多処理実験の比喩と考えられる.
  • ハンドル:実験中にある処理(例えば「Webテスト中のヘッダ線A」)
    • を指す.
  • ボーナス(収入):タイガーマシンで獲得したボーナスの実験的比喩(例えば「顧客クリックリンク数」)

    • 📈 マルチパスワード制限の原因(A/Bテストで問題)


  • このアルゴリズムは,従来の実験設計統計法と比較して,明示的な最適化とより速い決定を実現し,種々の試験,特にWeb試験に用いることができる.

  • 従来のA/B検定では、処理方法によってAかBのどちらが良いですか?与えられた質問の答えを与えます.そして,いったん答えが得られると,実験は終了し,結果に基づいて行動する.

  • この方法にはいくつかの困難がある.第一に、結論を下すのは難しいかもしれません.実験結果から有効と推定できるが,有効であっても(従来の統計基準を満たす)大きさを証明できる標本がない可能性がある.

  • 第二に,得られた結果を実験終了前に利用することもできる.

  • 第三に、実験が終わった後、追加入力されたデータに基づいて他のものを試したいかもしれません.

  • 第四に、テスト時間が長く、費用が高く、第五に、A案が良ければ、B案を適用する過程で最終的に損失を受ける.最後に、A案はいいですが、1週間後にはB案がいいかもしれません.

  • 柔軟性に欠ける結論を出す.

  • コンピュータの能力が向上するにつれて、柔軟な方法が可能になり、データ科学とビジネス全体で、統計的な合理性ではなく、さまざまなコストと結果を最適化することに関心が集まっています.

  • 今回紹介したファンドリーアルゴリズムを用いて,既存の統計設計よりも迅速に結論を導くために,複数の処理を一度にテストすることができる.

    • 📈 マルチパスワード制限アルゴリズム



  • これは賭博で使われる俗語から名前をつけるアルゴリズムです.

  • 2つ以上のハンドルがあり、それぞれのハンドルが異なる速度でお金を払うトラ機を想像してみてください.このアルゴリズムの正式な名前(マルチアームの強度、マルチアームの帯域幅)と呼ぶことができる.

  • 私たちの目標はできるだけ多くのお金を稼ぐことです.より具体的には、ボーナスの豊富なハンドルを後で確認するのではなく、できるだけ早く確認することです.しかし、困ったのは、手を引くときに全部でいくら払うか分からないことです.

  • 3つのハンドルがあると仮定すると、すべてのハンドルは同じボーナスです.違いは勝つ確率です.(50回試した結果、以下の結果が得られた)
    • 손잡이 A : 50번 중 10번 승리
손잡이 B : 50번 중 2번 승리
손잡이 C : 50번 중 4번 승리

  • 「次のような極端な結論が出るかもしれない」ハンドルAが一番よく見えます.「他の取っ手に挑戦せず、Aだけ引く」これは,初期試験で得られた情報を十分に利用する方法である.もしAが本当に優越であれば、私たちは初期にその利益を得ることになります.しかし、実際には、BやCがもっと良ければ、私たちはこの事実を発見する機会を逃した.

  • もう一つの方向の極端な結論は「すべての人がランダムだ」ということだ.みんなが同じように引っ張ることだ.この近接はA以外のものを解除する確率を最大限に与えるが,確率の低い挙動を推定し続けなければならない.どれくらい試しますか??

  • ファンデディアルゴリズムは混合方式を採用している.まずAが一番確率が高いので、もっと頻繁にAを引くことを選びましたが、BとCを引く機会をあきらめません.Aで成績を取り続けると、その時BとCを引く機会がAに多くなり、Aを引く機会も多くなり、Cがもっと良くなり、Aがもっと悪くなると、初めてAを引く機会がCに多くなります.どちらかがAより優れており,これが最初の50回の実験で隠された結果であれば,より多くの試験により,この事実を証明する機会がある.

  • Webページを例にとると、ビデオバーがインストールされている場合、お客様はクリックしたりしません.当初,各種提案はランダムに平均表示された.これにより,一つの提案が別の提案よりも良い結果を生み始めると,より頻繁に現れる.

  • すなわち,多岩帯開発(MAB)において,核心的な問題は探索と利用(Exploration and Exploration)である.この問題を解決してこそ、かなりのビジネス問題を解決することができます.

  • 1つ目は、グレースケールアルゴリズム(greedy):1回遊ぶたびに、点数の良いスロットマシンで押し合います.最初に聞いた例のように、タイガーマシンが3台あるときは、回転するたびに最高のスロットに投資します.これはまだ十分な探索が行われていない.

  • では、ドラッグスケールを修正するアルゴリズムのパラメータは何でしょうか.引き延ばし比率はいつどのように修正しますか?

  • 第二に、Essilon-Greedyアルゴリズム(epsilon-Greedy Algorithm,e-greedy algorithm):コインを投げた後、上に出れば得点の高いタイガーマシン、後ろに出ればランダムに選択し、前にGredyアルゴリズムで不足していた探検戦略を修正しました.トラ機をランダムに選択する確率がある.上から出ると点数の良いタイガーマシンを選ぶ確率は50%、後ろから出るとタイガーマシンの性能に関係なくランダムに選ぶ確率は50%です.ここで,コインの正面に現れる確率の50%はεという超パラメータである.

  • 第三に、「Upper Confidence Bound」(UCB)
    収益率が高く、最適な選択になる可能性のあるタイガーマシンを選択します.
    2つ目の戦略は、最高のトラ機を探してランダムに探検することです.しかし、探検するときは必ずランダムにしなければなりませんか?もっと合理的に探検できますか?

  • ランダムでないスロットマシンが最適になる可能性を数値で計算し、最も可能性のあるスロットマシンを選択したらどうなりますか?開始日.

  • 基本的なGriddyアルゴリズムに式を追加し,この式はトラマシンが最適なトラマシンになる可能性があることを意味する.可能性や不確実性と言える.

  • 第四に、トプソンサンプリング(Thompson's sampling):各ステップに1つのサンプル(ハンドルを引き出す)を抽出し、最適なハンドルを選択する確率を最大化する.どれが一番いいハンドルなのか分かりません(これはいつも問題です).しかし,連続抽出により得られた収益を観察すれば,より多くの情報を得ることができる.トムソンサンプリングはベース方式を採用した.すなわち,β分布を用いて収益の部分が予め分布していると仮定する.各抽出情報の蓄積に伴い,情報更新は,次回最適ハンドルを選択する確率を効果的に最適化できる.

    • 📈 整理する

  • 従来のA/B検定はランダムサンプリングプロセスに基づいており、収益の低いものを多く試みる可能性がある.
  • と比較して、MABは、統合実験中に得られた情報と、低収益の周波数を減少させる点からサンプリングプロセスを変更する.
  • は、2つ以上の処理を効率的に処理することもできる.
  • 抽出確率を収益の低い処理から収益の高い推定に移すアルゴリズムは複数ある.
    • Linuxの中の2>&1は一体何ですか
    [AVA-4]DIPとDIについて