アルゴリズム思考術:問題解決の最強ツール（2017/10/19）／ブライアン クリスチャン＆トム グリフィス【読書ノート】
ベンチャービジネスを売却するタイミングはいつか。車をどの駐車スペースに停めるべきか。何人めの交際相手で手を打って結婚すべきか。……それぞれ違った問題のようだが、コンピューター科学者ならまとめて解決してしまう――どれにもあてはまる、最良と証明された手順があるからだ。こうした、問題解決のために定められ、機械的に進めれば目的を達成できる一連の手続きがアルゴリズム。初歩のプログラミングから人工知能まで、基本はこれである。じつはビジネスから日常生活まで、私たちがぶつかる問題には、アルゴリズムによる解決がすでに見つかっていることが多い。達人でも天才でもなくても難題を切り抜け、仕事を楽にする秘訣がアルゴリズムに学べる。《フォーブス》ほか各紙誌絶賛、現代人必読の書。
野口悠紀雄氏推薦
「実に興味深い論考。世の中のさまざまな問題を最適化アルゴリズムを用いて説明し、超整理法がなぜ最適かの証明もある」「コンピューター科学と人間心理学を融合させた、本書は僕が久しく待望してきた1冊だ。読めば誰でも、現代世界を動かすコンピューター科学が理解できるばかりか、さらに大事なことに、コンピューター科学が日常にどう役立つかがわかる」――デイヴィッド・イーグルマン(『あなたの脳のはなし』)
「『アルゴリズム思考術』には、時間やスペース、あるいは仕事をより効率的に扱う、いますぐ役立つ知恵満載。……『やることリスト』を最適化したい人、クロゼットをスッキリさせたい人、人間の記憶力に興味がある人、みんなを唸らせる1冊だ」――チャールズ・デュヒッグ(『習慣の力』)
はじめに―人の暮らしのアルゴリズム
1最適停止―「見る」のをやめるタイミング
最適停止問題（Optimal Stopping Problem）は、統計学や確率論、選択理論における一般的な問題設定です。最適停止問題は、いつ行動を停止し、どの時点で最適な選択を行うかを決定するための戦略を求める問題です。具体的な例としては、求職活動、購入時期の決定、あるいは投資のタイミングなどがあります。以下に、最適停止問題の基本的な要素と例を示します。
問題設定:
最適停止問題は、ある連続的または離散的な選択のシーケンスに対する最適な停止時点を求める問題です。この問題は、各時点で得られる報酬やコストが確率的に変動し、それに対する最適な戦略を見つけ出すことを目的としています。
具体的な例 - 秘書問題:
最適停止問題の典型的な例として秘書問題があります。この問題では、雇用主がn人の候補者の中から最も適した秘書を選ぶ必要があります。各候補者は、面接の後に即座に採用または不採用を決定しなければならず、一度不採用とした候補者に戻ることはできません。このシナリオでは、最適な停止戦略を見つけることで、最も適した候補者を採用する確率を最大化することが目的となります。
解法:
最適停止問題は、動的計画法や確率論、統計的推論を利用して解くことが可能です。これらの手法を使用することで、各時点での最適な選択を決定し、長期的な報酬を最大化する戦略を計算することができます。
実用例:
最適停止問題の解法は、金融、経済学、工学、情報理論など様々な分野で利用されています。例えば、オプションの価格設定や在庫管理、リソースの割り当てなどに最適停止問題の概念が適用されています。
最適停止問題は、不確実性のもとでの最適な決定を行うための重要なフレームワークを提供し、多くの実用的な応用があります。この問題は、確率的な環境での最適な選択を理解するための基本的なツールとなっています。
秘書問題
「秘書問題」（または「結婚問題」「停止問題」などとも呼ばれる）は、確率論や意思決定理論の分野でよく知られる問題で、最適な停止時点を見つけることを目的とした問題です。具体的には、最適な候補者を選ぶことを目的としています。問題の基本的な設定は以下のようになります。
あなたは、n人の秘書の中から1人を選ぶ仕事を持っています。
秘書たちは一人ずつ順番に面接を受けてきます。
各秘書を面接した直後に、その秘書を採用するかどうかの決定をしなければなりません。
一度採用の決定をしたら、その後の候補者を見ることはできません。
この問題での目標は、最適な秘書を採用する確率を最大化する停止戦略を見つけることです。この問題の解決策として知られているのは「37%ルール」または「1/eルール」です（e≒2.71828 ）。この戦略では、最初の37%の候補者を観察のみとして、その後の候補者から最初の37%の中での最適な候補者よりも優れた者が現れた時点で採用する、というものです。この戦略を採用することで、最適な候補者を採用する確率は約37%になります。
秘書問題は、リアルな意思決定の状況や、機会の最適なタイミングを見極める問題としての洞察を提供する例として、数多くの文脈で言及されます。
三七パーセントはどこから?
「見てから跳べルール」（Look before you leap rule）は、決断や選択をする際に、事前に情報を収集し、状況を評価してから行動することを勧める一般的な原則またはアドバイスです。このルールは、衝動的な決断や無計画な行動のリスクを減らし、より慎重かつ知識に基づいた選択を促すことを目的としています。具体的な状況やコンテキストに応じて、このルールはさまざまな方法で解釈や適用される可能性があります。
以下に「見てから跳べルール」のいくつかの側面を示します。
情報収集:
このルールは、重要な決断を下す前に必要な情報を収集し、リサーチを行うことを推奨しています。情報は、適切な選択を行うための基盤を提供し、未知のリスクや問題を明らかにする可能性があります。
リスク評価:
行動する前にリスクを評価し、可能な結果を検討することは、不測の事態や悪い結果を避けるために重要です。リスク評価は、未来の予測と準備を改善するのに役立ちます。
計画と準備:
このルールは、計画と準備の重要性を強調しています。計画的なアプローチは、目標を達成し、期待される結果を得る可能性を高めます。
慎重な判断:
衝動的な決断や急激な行動は、しばしば予期しない結果や問題を引き起こす可能性があります。慎重に情報を検討し、可能な選択肢を比較することは、良い判断を下すのに役立ちます。
経験と知識の活用:
過去の経験や知識は、新しい状況や決断に対する洞察を提供する可能性があります。これらのリソースを活用することで、より賢明な選択を行うことができます。
「見てから跳べルール」は、日常生活、ビジネス、個人的な決定など、多くの異なるコンテキストで有用であり、知識に基づいて慎重に行動することの重要性を強調しています。
恋人にジャンプ
よいものを見逃さない―完全情報
売却のタイミング
駐車のタイミング
やめるタイミング
人生は停止問題に満ちている
2探索と活用―最も新しいものと最もすばらしいもの
探索と活用
残り時間を見極める
勝てばキープ
ギッティンズ指数
後悔と楽観
オンラインのバンディット
臨床試験を試験する
世界は変わる
探索と……
……活用
3ソート―秩序を生み出す
ソートの悦び
ソートの苦しみ
ビッグO（オー）―最悪の事態の尺度
ビッグオー記法（Big O notation）は、アルゴリズムの効率や計算量を記述するために用いられる数学的な記法です。具体的には、アルゴリズムがどれだけの時間（時間計算量）やメモリ（空間計算量）を必要とするかを、最悪ケース、平均ケース、または最良ケースで示すために使われます。ビッグオー記法は、入力サイズ ( n ) に対するアルゴリズムの動作を評価する際に特に役立ちます。例えば、アルゴリズム ( A ) の時間計算量が ( O(n^2) ) であるという場合、入力サイズ ( n ) が大きくなるにつれて、必要な計算時間は ( n ) の二乗に比例して増加するということを示しています。
以下は、よく用いられるビッグオーの例です：
( O(1) ): 定数時間（Constant time）
入力サイズに関わらず、常に一定の時間がかかるアルゴリズム。( O(\log n) ): 対数時間（Logarithmic time）
二分探索など、入力サイズが2倍になるごとに必要な時間が一定量増加するようなアルゴリズム。( O(n) ): 線形時間（Linear time）
入力サイズに比例して時間がかかるアルゴリズム。例えば、単純な探索アルゴリズムなど。( O(n \log n) ): 線形対数時間（Linearithmic time）
マージソートやクイックソートなど、よく用いられるソートアルゴリズムで見られる計算量。( O(n^2) ): 二乗時間（Quadratic time）
単純なソートアルゴリズム（バブルソートなど）や、二重ループを用いるアルゴリズム。( O(2^n) ), ( O(n!) ): 指数時間（Exponential time）、階乗時間（Factorial time）
非常に効率が悪いアルゴリズム。全探索、組み合わせ問題など。
ビッグオー記法は、アルゴリズムの「スケーラビリティ」を理解する上で非常に有用です。同じ問題を解く複数のアルゴリズムがある場合、ビッグオー記法を用いてそれぞれの効率を評価することができます。
二乗時間―バブルソートと挿入ソート
バブルソート（Bubble Sort）は、シンプルで初学者にも理解しやすいソートアルゴリズムの一つです。このアルゴリズムの基本的なアイデアは、隣り合う要素を比較して、必要ならば交換するという操作を繰り返すことで、配列全体をソートするというものです。バブルソートのアルゴリズムは以下のように動作します：
配列の最初から最後に向かって進み、隣り合う要素を比較します。
もし隣り合う2つの要素が逆の順序になっていれば、それらを交換します。
配列の最後に到達するまでこの操作を繰り返します。
配列の最後の要素は、その時点で配列内で最も大きい値であると保証されるため、それ以降は操作対象から除外されます。
このプロセスを配列の全要素に対して行います。
このアルゴリズムは計算量が(O(n^2))と非常に効率が悪いため、大規模なデータセットには通常推奨されません。ただし、実装が簡単であるため、教育的な文脈ではよく紹介されます。以下はバブルソートの疑似コードです：
function bubbleSort(arr)
n = length(arr)
for i from 0 to n-2
for j from 0 to n-i-2
if arr[j] > arr[j+1]
swap arr[j] and arr[j+1]この疑似コードは、基本的なバブルソートアルゴリズムの一例です。実際には、早期終了条件を追加するなど、さまざまな最適化が可能です。
挿入ソート（Insertion Sort）は、ソートアルゴリズムの一つで、非常に直感的で実装が簡単な方法です。挿入ソートは、手でカードをソートするときに自然に行うような方法に似ています。アルゴリズムは次のように動作します：
配列の先頭の要素をソート済みとします（一つの要素だけなので、自動的にソート済みです）。
未ソート部分から一つずつ要素を取り出し、すでにソート済みの部分と比較しながら適切な位置に挿入します。
この手順を配列の最後まで繰り返します。
以下は挿入ソートの疑似コードです：
function insertionSort(arr)
n = length(arr)
for i from 1 to n-1
key = arr[i]
j = i - 1
// arr[0..i-1]はソート済みであるとする
// keyより大きい要素を一つずつ右へずらしていく
while j >= 0 and arr[j] > key
arr[j + 1] = arr[j]
j = j - 1
// keyを適切な位置に挿入
arr[j + 1] = key挿入ソートは、平均計算量と最悪計算量が共に(O(n^2))となりますが、小さな配列やほぼソート済みの配列に対しては非常に効率的です。また、安定なソートアルゴリズムであり、インプレース（追加のメモリをほとんど必要としない）なのも特徴です。一般に、データ量が多くなると他のより効率的なアルゴリズム（例えば、マージソートやクイックソート）が推奨されます。しかし、単純さと実装の容易性から、教育目的や小規模なタスクでよく用いられます。
二乗時間の壁を破る―分けて征服
比較を超えて―対数時間を出し抜く
ソートは検索の事前対策
ソートとスポーツ
あえて非効率に―ノイズと頑健性
戦いの末に―力関係の序列
戦いではなくレースを
4キャッシュ―さっさと忘れよう
メモリー階層
追い出しと千里眼
図書館を裏返す
近所のクラウド
家庭内のキャッシュ
整理と山積み（ファイリングとバイリング）
忘却曲線
経験の暴虐
5スケジューリング―最初のものを最初に
時間の使い方が学問となる
納期を守る
最早納期優先
ムーアのアルゴリズム
仕事を片づける問題を選ぶ
優先度逆転と先行制約
優先度逆転（Priority Inversion）
低優先度のタスクが高優先度のタスクよりも先に実行される現象を指します。これは通常、低優先度のタスクがリソースを保持している状態で、高優先度のタスクがそのリソースを要求した際に発生します。この状態では、高優先度のタスクは低優先度のタスクがリソースを解放するまで実行待ちとなり、結果として優先度が逆転します。優先度逆転の問題を解決する一つの方法は、プライオリティ・シーリング・プロトコル（Priority Ceiling Protocol）を使用することです。これは、リソースを取得したタスクの優先度を一時的に引き上げることで、他の高優先度のタスクがブロックされるのを防ぐ方法です。
先行制約（Precedence Constraint）
先行制約は、プロジェクト管理において、一つのタスクが別のタスクよりも先に完了しなければならないという関係を表します。これは、あるタスクの開始または完了が、別のタスクの開始または完了に影響を与えるという意味です。例えば、建築プロジェクトで基礎を築く作業が完了しないと、壁を建てる作業を開始することはできません。この場合、基礎を築く作業が壁を建てる作業の先行制約となります。先行制約は、プロジェクトのスケジュールを計画し、タスク間の依存関係を管理する上で非常に重要な役割を果たします。これにより、プロジェクトマネージャーはリソースを効率的に割り当て、プロジェクトをスムーズに進行させることができます。
行く手を阻むもの
すべてを捨てる―割り込みと不確実性
未来が見渡せないとき必要なのは予定表ではない『やることリスト』があればよい。
割り込みはタダではない―コンテキストスイッチ
コンテキストスイッチは、コンピュータのオペレーティングシステムがマルチタスクを効率的に処理するために行うプロセスの切り替えのことを指します。具体的には、CPUが現在実行中のプロセスまたはスレッドから別のプロセスまたはスレッドに切り替える際に、システムは現在のプロセスの状態（コンテキスト）を保存し、新しく実行するプロセスの状態を復元する必要があります。このプロセスの状態には、CPUレジスタ、プログラムカウンタ、メモリの使用状況などが含まれます。
コンテキストスイッチは、ユーザーが複数のアプリケーションを同時に実行しているかのように感じられるようにするため、またはシステムリソースを効率的に利用するために必要です。しかし、コンテキストスイッチにはオーバーヘッドがかかるため、頻繁に発生するとシステムのパフォーマンスに影響を与えることがあります。
オペレーティングシステムのスケジューラは、実行すべきプロセスを決定し、必要に応じてコンテキストスイッチを行います。スケジューリングのアルゴリズムやポリシーは、システムの性能と応答性に直接影響を与えます。
コンテキストスイッチは、プリエンプティブマルチタスキング（オペレーティングシステムがプロセスを強制的に切り替えることができる）環境で特に重要です。これにより、各プロセスは公平なCPUの時間を受け取り、システムの応答性が向上します。
スラッシング
スレッディング（Threading）
プログラムの実行単位を複数のスレッドに分割し、これらを並行して実行するプログラミングの手法です。スレッドは、プログラム内で独立して実行されるシーケンスであり、各スレッドは独自の実行コンテキスト（レジスタの状態、プログラムカウンタなど）を持ちますが、メモリ空間やオープンしているファイルなどのリソースは他のスレッドと共有することができます。
スレッディングを使用する主な利点は、プログラムの応答性の向上とリソースのより効率的な利用です。例えば、マルチコアプロセッサを搭載したコンピュータでは、複数のスレッドを同時に実行することで全体の処理速度を向上させることができます。
スラッシング（Thrashing）
スラッシングは、コンピュータシステムのメモリが不足した際に発生する現象で、システムのパフォーマンスが著しく低下することを指します。これは、実行中のプログラムが利用するデータやプログラムコードの大部分がメモリ上に収まらず、頻繁にページフォールト（データがメモリ上になく、ディスクから読み込む必要がある状態）が発生するため、CPUが実際の計算よりもページのスワッピング（ディスクとメモリ間でのデータの移動）に多くの時間を費やすことになります。
スラッシングは、適切なメモリ管理とリソースの割り当てによって予防または軽減することが可能です。例えば、プログラムのメモリ要求を適切に管理したり、十分な物理メモリをシステムに搭載することで、スラッシングの発生を防ぐことができます。
スレッディングとスラッシングは、それぞれプログラムの並行実行とメモリ管理に関連していますが、スレッディングはプログラムの効率を向上させるための技術であり、スラッシングはシステムのパフォーマンスを低下させる問題を指します。
割り込み軽減
6ベイズの法則―未来を予想する
『ビッグデータ』の時代に生きている我々の日常は『スモールデータ』で満ちている。
ベイズ牧師と後ろ向き推論
ラプラスの法則
n回の試行で、当たりがw枚だったとすると、（w＋1）/（n＋2）となる。
（くじを三枚買って全て当たりだったら五分の四となる。）
ベイズの法則と事前信念
コペルニクス原理
ベイズとコペルニクスの邂逅
現実世界の事前確率と...
・正規分布（ガウス分布・鐘形曲線）：寿命・身長・体重・血圧・IQ……
・べき分布（パワーロー分布／ロングテール・ファットテール）：ある量が非常に小さい値をとることは多いが、非常に大きい値をとることは稀であるという特徴を持つ～所得分布・都市の人口・地震の強さ・インターネットの接続性・語彙の使用頻度・企業の規模サイトの訪問者数etc.
…その予想ルール
・正規分布⇒平均ルール
・べき分布⇒乗法ルール
・アーラン分布⇒加法ルール
スモールデータと直感
予想が予想者について明かすこと
複製技術時代の事前確率
7オーバーフィッティング―過ぎたるは及ばざるがごとし
過学習（overtraining）／過剰適合（overfitting）
別名：オーバーフィッティング／オーバーフィット
オーバーフィッティング（過学習）とは、機械学習モデルが訓練データに対して過度に最適化され、新しい未知のデータに対して一般化する能力が低下する現象を指します。
あるゲームでの例を考えてみましょう。あなたが新しいゲームを学ぶとき、最初は友達と対戦し、その友達の戦術を覚えます。最初は友達に勝てなかったけれど、何度も練習するうちに、友達の戦術を完璧に理解し、毎回勝てるようになりました。
これで、あなたは友達に対して「過度に適応（オーバーフィット）」してしまったと言えます。なぜなら、友達との対戦に合わせて、その特定の戦術だけを学んでしまい、他の人とのゲームでうまくいかない可能性があるからです。
機械学習でも同じことが起こります。コンピューターがたくさんのデータを学ぶと、そのデータに合わせた特別なルールを作ります。しかし、そのルールがあるデータにはぴったり合うけれど、新しいデータには合わないことがあります。これは、あなたが友達に勝つための特別な戦術を学んでしまったのと似ています。
だから、機械学習では、あまりにも訓練データに「オーバーフィット」しないように気をつけなければなりません。新しいデータでもちゃんと役立つルールを作るために、訓練データだけではなく、いろんなデータを考える必要があるのです。
考える量を意図的に少なくするほうが物事はうまくいく。
複雑性に対する申し立て
データの偶像崇拝
オーバーフィッティングはいたるところに
オーバーフィッティングを見つけ出す―クロス確認
オーバーフィッティングと闘うには―複雑さにペナルティーを与える
オッカムの剃刀は、簡単に言うと「シンプルな説明が良い説明だ」という考え方です。例えば、宇宙には星がたくさんあります。それらの星がどうやってできたのかを考えるとき、いくつかの説明が考えられます。一つは「神様が星を作った」という説明です。もう一つは「星はガスと塵が集まってできた」という説明です。
オッカムの剃刀を使うと、よりシンプルな説明が好ましいとされます。なぜなら、「神様が星を作った」という説明は、神様の存在や意図を説明する必要があり、複雑だからです。一方、「星はガスと塵が集まってできた」という説明は、シンプルで、科学的な証拠に基づいています。
したがって、オッカムの剃刀を考えると、シンプルで複雑さを避けた説明が良い説明とされます。この原則は、科学の研究や問題解決において、シンプルなアイディアや仮説を好む考え方です。
ヒューリスティックの利点
過去の重み
思考を抑えるべきとき
なにかのデザインを始める時には、ボールペンではなく太いシャーピーマーカーを使ってアイデアのあらましを書き留める。
8緩和法―大目に見よう
最適化の難しさ
困難さを定義する
ただ緩和（リラックス）せよ
数えきれないほどたくさんのグレーの色調（シェイズ・オブ・グレイ）―連続緩和
ペナルティーを受け入れる―ラグランジュ緩和
緩和法の習得
9ランダム性―偶然に任せるべきとき
サンプリング
乱択アルゴリズム
サンプリング礼讃
エラーのトレードオフ
山、谷、わな
極大値を脱する
焼きなまし法
ランダム性、進化、創造性
10ネットワーキング―どうつながるか
パケット交換
確認応答
指数バックオフ寛容のアルゴリズム
流れ制御と渋滞回避
あいづち―言語における流れ制御
バッファーブロート―遅延が問題だ
遅れるよりはやらないほうがまし
11ゲーム理論―他者の心
再帰
均衡の達成
支配戦略、よかれ悪しかれ
共有地の悲劇
メカニズムデザイン
ゲームのやり方を変える
進化によるメカニズムデザイン
情報カスケード―バブルの悲劇的な合理性
汝自身のために計算せよ
結論計算の負担を軽くする
結論―計算の負担を軽くする
アルゴリズムの世界は、日々変わり続ける領域であり、多様なアルゴリズムが存在します。その中で「多腕バンディット問題」は探索と活用のバランスを取る問題として知られ、この問題に対するアプローチの一つに「最適停止」があります。「見てから跳べ」の原則や「閾値ルール」を利用して最適な決定を下すことが求められます。
また、アルゴリズムの中には、ノイズを考慮しながらの頑健性を追求するものも多い。こうしたノイズに対応するために、「ベラーディのアルゴリズム」や「ランダムエビクション」、「最長未使用時間法」などのキャッシュ関連の方法が利用されることがあります。また、「ギッティング指数」や「疑わしきは罰せず」の原則は、情報の整理や忘却の仕方に関連しています。
データ処理においては、「バケットソート」や「ソート」といった基本的なアルゴリズムがあり、これらはデータの整列や高速な検索を助けます。しかし、「オーバーフィッティング」の問題が生じることもあるため、それに対する「クロス確認」や「正則化」「ヒューリスティック」「緩和法」「ラグランジュ緩和」などの手法が考案されています。
ランダム性を利用するアプローチとしては、「モンテカルロ法」「メトロポリス・アルゴリズム」「焼きなまし法」が挙げられます。これらは確率的なアルゴリズムとして、特定の解に固執せずに解の探索を行います。
「ゲーム理論」は複数の主体が相互に戦略を取りながら最適な行動を決定する理論で、「ナッシュ均衡」や「アルゴリズム的ゲーム理論」「囚人のジレンマ」「メカニズムデザイン」といった概念があります。
最後に、情報の伝搬に関連して、「情報カスケード」や「顕示原理」といった現象や原理が存在し、これらは社会的なネットワーキングの中で重要な役割を果たしています。
用語の簡単説明
最適停止: 決断を下す最良の時点を決定する問題。例えば、いくつかの選択肢の中から最良のものを選ぶ際に、いつ選択を停止するべきかを考える。
見てから跳べ: 情報を収集してから行動をとること。
閾値ルール: ある基準値を超えた時点で行動を開始するルール。
探索と活用: 新しいものを試す「探索」と、既知のものを最大限に活用する「活用」とのバランスを取ること。
多腕バンディット問題: 複数の選択肢があり、それぞれの報酬が不確かな状況で、最も報酬が高い選択を繰り返し行う問題。
勝てばキープ、負ければスイッチ: 過去の結果に基づいて戦略を変更するアプローチ。
ギッティング指数: あるトピックの研究活動の新しさを示す指標。
疑わしきは罰せず: 不確実性の下での慎重な行動や判断。
世界は変わる: 環境や状況は常に変動するという概念。
ソート: データを特定の順序に並べること。
バケットソート: データをいくつかのバケットに分けてソートするアルゴリズム。
ノイズと頑健性: データやシステムが持つ不確実性（ノイズ）にどれだけ耐えるか（頑健性）。
キャッシュ: 高速にアクセス可能な一時的な記憶領域。
ベラーディのアルゴリズム: キャッシュの置き換え戦略の一つ。
ランダムエビクション: キャッシュからランダムにデータを排除する戦略。
最長未使用時間法: 最も長い間使用されていないデータをキャッシュから排除する戦略。
忘却と整理の仕方: 記憶の維持と整理の方法。
スケジューリング: タスクや作業を計画的に配置すること。
コンテキストスイッチとスラッシング: マルチタスク環境でのタスクの切り替え（コンテキストスイッチ）と、それが頻繁すぎてシステムが非効率になる現象（スラッシング）。
ベイスの法則: 事前情報をもとに新しいデータを使って確率を更新する方法。
後ろ向き推論: 望む結果から逆算して考える手法。
ラプラスの法則: 情報が不足している場合にすべての事象が同じ確率で発生すると考える原理。
コペルニクス原理: 我々の存在や観察が宇宙や事象の中で特別ではないという原理。
スモールデータと直感: 少量のデータと直感を基に意思決定を行う考え方。
オーバーフィッティング: 学習データに過度に最適化されてしまい、新しいデータに対する予測性能が落ちる現象。
クロス確認: データを複数のサブセットに分け、一部を学習用、一部を評価用としてモデルの性能を評価する手法。
正則化: モデルの複雑さを制限してオーバーフィッティングを防ぐ手法。
ヒューリスティック: 問題解決のための経験的な方法や近似的な手法。
緩和法: 制約の一部を緩和して問題を簡単にする手法。
ラグランジュ緩和: 最適化問題の制約を目的関数に組み込むことで問題を緩和する手法。
ランダム性: 予測や制御が難しい非決定的な性質。
モンテカルロ法: ランダムなサンプリングを用いて数値的な解を求める方法。
メトロポリス・アルゴリズム: 統計力学やモンテカルロ法において使用されるランダムサンプリング手法。
焼きなまし法: システムの最適な状態を探索するための確率的な手法。
ネットワーキング: 人々や機器が相互に接続・通信すること。
加法的増加・乗法的減少: ネットワーク制御のための調整方法の一つ。
階層なき制御: 中央集権的な制御を持たないシステムやネットワーク。
ゲーム理論: 戦略的状況下での意思決定を研究する数学的理論。
再帰: 自分自身を呼び出すプロセスや手法。
ナッシュ均衡: ゲーム理論で、各プレイヤーが他者の戦略を考慮して最適な戦略をとる状態。
アルゴリズム的ゲーム理論: ゲーム理論と計算機科学を結びつけた研究領域。
囚人のジレンマ: 二人のプレイヤーが協力することで最適な結果を得ることができるが、個々に考えると裏切りの方が有利になるゲーム理論の問題。
メカニズムデザイン: ゲームのルールを設計することで、望ましい結果を引き出す方法の設計。
情報カスケード: 個人が他者の行動や選択に影響されて、自らの情報や信念を無視する現象。
顕示原理: 優れた特性や能力を持つものがそれを明示的に示すことで、他者からの評価や信頼を得る原理。
人生の重要な決定
この本では、例えば採用面接のような人生の重要な決定を通じて、アルゴリズムの役割が解説されています。面接での最適な停止ポイントや、どの候補者を採用すべきかを決定するためのアルゴリズムについて考察されています。数学的アプローチを用いることで、正しい決定をする確率が高まります。
リソース最適化
アルゴリズム思考術は、リソース最適化にも役立ちます。例えば、アパート探しや駐車場選びの際に、どこまで探すべきかを決める際に役立つアルゴリズムが紹介されています。これにより、最良の選択肢を見つけるための戦略を簡単に見つけることができます。
探索と利用のバランス
本書では、探索と利用のバランスについても議論されています。スロットマシンのような状況では、どの時点で別の選択肢に移行すべきか、どの戦略が最も利益を上げるかが取り上げられています。完璧な最適解を求めることは難しい場合もありますが、アルゴリズムを用いることで収益を最大化できる可能性が高まります。
実生活での適用
アルゴリズム思考術は、実生活でも応用可能です。野球の試合進行やトーナメント戦、あるいはコンピュータサイエンスの分野でのトレードオフの問題など、さまざまなシナリオでアルゴリズム思考術が役立つことが紹介されています。
まとめ
この本は、アルゴリズムの力を通じて人生の重要な決定や問題を解決する方法について考察しています。日常生活からコンピューターサイエンスの応用まで、アルゴリズム思考術は幅広い分野で役立つアプローチを提供しています。