目次
背景
- 最近、色々なことを探索する機会の増加している
- 商品、仕事、旅行先、投資先、学習テーマ、技術選定などの比較など
- 選択肢が増えるほど難しくなる意思決定
- ROS2のNAVや機械学習、仕事でもこれらは頻出する
- 一見すると別々の分野の理論とも見える
- ただし、根底にある共通の問題として定義できる
限られた情報の中で、どこまで探索し、どのように推定し、いつ意思決定するか
探索に含まれる問題
探索を分解すると、主に以下の問題。
- 候補の生成
- 情報の収集
- 状態の推定
- 将来の予測
- 候補の比較
- 不確実性の評価
- 探索終了の判断
- 最終的な選択
それぞれの問題に対応する手法。
手法
最適停止問題
探索をいつ終了するかという問題。
代表例が秘書問題。
- 候補が一人ずつ順番に登場
- その場で採用または不採用の判断
- 一度見送った候補への後戻りは禁止
- 全候補を確認してからの決定も禁止
- 最も良い候補を選ぶことが目的
古典的な条件では、最初の約37%を観察に使い、その後に現れた過去最高の候補を選ぶ戦略。
いわゆる37%ルール。
探索期間と決断期間の分離。
- 前半における基準の形成
- 後半における基準を超えた候補の選択
- 永遠に探し続ける問題の回避
- 早すぎる決断の回避
ただし、37%という数字が成立するのは、候補数が既知、順序がランダム、後戻り不可などの条件がある場合。
日常生活で重要なのは37%という数字そのものではなく、探索と決断を分ける発想。
別の言い方だと次の不等式が成りたたないからということ。
$$ 追加情報の期待価値>調査コスト+意思決定を遅らせるコスト $$
これには、機会損失も含まれるのかもしれない。
ベイズ推定
新しい情報によって評価を更新する方法。
基本となる三つの要素:
- 事前確率
- 観測された情報
- 更新後の確率
最初から正しい評価を作るのではなく、観測のたびに評価を更新する考え方。
例えば、あるサービスを導入する場合。
導入前の評価:
- 評判の良さ
- 導入コスト
- 他社の事例
- 機能の充実度
試用後に追加される情報。
- 実際の操作性
- 自分の用途との相性
- チームの反応
- 想定外の制約
それらを使った評価の更新。
固定された点数ではなく、変化し続ける確信度。
「最初の予想が外れた」という失敗ではなく、「新しい情報によって評価が更新された」という理解。
マルコフモデル
状態の変化を考えるための方法。
基本となる要素。
- 現在の状態
- 次に起こり得る状態
- 状態間の遷移確率
典型的な状態の例:
- 未認知
- 興味あり
- 比較中
- 購入
- 継続利用
- 離脱
現在の状態から、次の状態へ進む確率のモデル化。
重要なのは、現在の状態を過去の情報が圧縮されたものとして扱う点。
- 過去の出来事をすべて保存する代わりの現在状態
- 状態間の移動としての将来予測
- 一回の選択ではなく、連続する変化への注目
探索対象を静止した点ではなく、変化する状態として見る方法。
カルマンフィルター
ノイズを含む観測から、本当の状態を推定する方法。
現実で直接観測できるものの多くは不完全。
- 一時的な売上
- 短期間のアクセス数
- 他人からの評価
- 商品レビュー
- 市場価格
- 自分の体調
- 学習の進捗
観測値そのものと、本当の状態の区別。
カルマンフィルターにおける基本的な流れ。
- 過去からの予測
- 新しい観測
- 予測と観測の誤差
- 推定値の修正
- 次の時点の予測
観測を全面的に信用するのでも、過去の予測に固執するのでもない姿勢。
予測の信頼度と観測の信頼度を考慮した更新。
一時的な数字に振り回されず、背後にある状態を推定するための考え方。
グリッドサーチ
あらかじめ決めた候補の組み合わせを網羅的に試す方法。
例えば、以下の組み合わせ。
- 価格帯
- 利用人数
- 導入期間
- 機能数
- サポート品質
各項目に複数の候補を設定し、すべての組み合わせを比較。
特徴:
- 分かりやすい仕組み
- 比較過程の透明性
- 見落としの少なさ
- 計算量の増加
- 探索範囲の設定への依存
候補数が少ない場合の強力な方法。
一方で、軸や選択肢が増えるほど急増する組み合わせ。
探索範囲を誰が決めるのかという問題。
モンテカルロ法
不確実な条件を何度もランダムに発生させ、結果の分布を見る方法。
一つの予測値ではなく、多数のシナリオ。
- 楽観的な場合
- 標準的な場合
- 悲観的な場合
- 極端な場合
- 予想外の組み合わせ
例えば、新規事業の評価。
変動する条件。
- 顧客数
- 顧客単価
- 継続率
- 開発費
- 広告費
- 市場成長率
それぞれを固定値ではなく確率分布として設定。
多数回のシミュレーションによって得られるもの。
- 平均的な結果
- 結果のばらつき
- 赤字になる確率
- 目標を達成する確率
- 最悪ケースの大きさ
単一の未来予測ではなく、未来の可能性の分布。
「いくらになるか」ではなく、「どの程度の確率で、どの範囲になるか」という問い。
効率的フロンティア
複数の評価軸から、明らかに劣る候補を除外する方法。
基本的な流れ。
- 二つの評価軸の決定
- 候補のリスト化
- 各候補の数値化
- グラフへの配置
- 他の候補に支配される候補の除外
- 効率的フロンティアの抽出
- フロンティア上からの選択
投資では、一般的にリスクと期待リターンの関係として利用。
- 同じリスクなら、より高いリターン
- 同じリターンなら、より低いリスク
- どちらの面でも劣るポートフォリオの除外
ゲーム理論
二人以上の取引だと囚人問題の例のようになることがある。
この場合は最適解は
- パレート最適
- ナッシュ均衡
非協力で損を避けるか、協力して得を取るかという事。
二分法
- 最も古典的だが役立つ手法
- 例えば、コードにバグがあったとする
- どこか全くわからないときはシンプルに半分コメントアウトする
- すると、1/2でバグに当たる
- バグにあたったら更に1/2とこのように繰り返す
- $O(\log_2 n)$の計算量になる
Just Do it
- 下手の考え休むに似たり
- 行動したほうが速いこともある
- 探索しないアルゴ
- 行動そのものを低コストな情報収集として使うアルゴリズムとも言える
まとめ
- 改めて全体を見渡すと、普通に知識が大切だと思った
- ヌケモレなく、MECEかどうか、全体を網羅しているのか
- 最初の候補で、この前提がない場合は最適解に行きづらい
- しかし、知識を増やし続ければ正解に到達できるとは限らない
- 知識の獲得にもコストがあり、環境が変われば古くなる
- 結局は、探索と活用のトレードオフは常につきもの
- 大切なのはその見極め