2020 - 隨機算法與機器學習#

案件摘要#

2010–2020 年代，隨機算法完成了它最大的一場擴張：機器學習全面隨機化。深度學習的核心引擎——隨機梯度下降（SGD）、Dropout、批次取樣、LLM 的取樣生成——本質上都是隨機算法。蒙地卡羅方法（見 1946-Ulam蒙地卡羅.md）的「用隨機樣本逼近確定答案」，在深度學習時代成為訓練億級參數模型的唯一可行方式。隨機不再是「允許的錯誤」，而是「本質的方法」。

前因 -- 為什麼會有這個案子#

深度學習的訓練問題：對 \(N\) 筆資料、 \(P\) 個參數的模型，最小化損失：

\[ L(\theta) = \frac{1}{N}\sum_{i=1}^N \ell(f_\theta(x_i), y_i) \]

確定性梯度下降：每步計算全部 \(N\) 筆的梯度—— \(N\) 是億級時完全不可行（ImageNet 1400 萬張、LLM 數兆 token）。

Robbins–Monro (1951) 的隨機逼近早已給出答案：隨機取樣一小批（mini-batch），用有噪聲的梯度估計：

\[ g_t = \nabla_\theta \ell(f_\theta(x_{i_t}), y_{i_t}), \quad i_t \sim \text{Uniform}(\{1..N\}) \]

\[ \theta_{t+1} = \theta_t - \eta_t g_t \]

\(g_t\) 是無偏估計： \(E[g_t] = \nabla L(\theta_t)\) 。有噪聲的步子，卻能收斂到（甚至比確定性更好的）答案。

線索與推理 -- 數學式、程式、理論#

SGD 的收斂理論#

凸損失下，SGD 的期望收斂（Robbins–Monro 條件 \(\sum \eta_t = \infty\) 、 \(\sum \eta_t^2 < \infty\) ）：

\[ E[L(\theta_T)] - L^* \le O\left(\frac{1}{\sqrt{T}}\right) \]

非凸（深度學習的實況）下：SGD 幾乎總是收斂到局部極小，且噪聲幫它逃離鞍點。噪聲是特性不是缺陷：

逃離鞍點：確定性梯度在鞍點卡住，噪聲把它推走（Jin et al. 2017 的逃離鞍點理論）
隱式正則化：SGD 噪聲偏好「平坦極小值」——泛化更好（Keskar et al. 2017）
SGD ≈ Langevin 動力學：大 batch 極限下，SGD 的連續近似是隨機微分方程：

\[ d\theta = -\nabla L(\theta)\,dt + \sqrt{\frac{\eta}{B}}\,\Sigma(\theta)\,dW_t \]

（與布朗運動（見 1905-布朗運動.md）同一數學——訓練是能量下降 + 擴散！）

Dropout：隨機化的正則化#

2012 年 Hinton 等人在 AlexNet 中發明 Dropout：訓練時每個神經元以機率 \(p\) （典型 0.5）隨機丟棄：

\[ \tilde{h}_i = \frac{m_i h_i}{1-p}, \quad m_i \sim \text{Bernoulli}(1-p) \]

推理：等價於訓練 \(2^n\) 個子網路的集成（ensemble），逼網路不依賴任何單一神經元——隨機化對抗過擬合。Dropout 的理論基礎正是 Blum–Micali 式的「隨機化破壞精確依賴」（見 1985-BlumMicali偽隨機產生器.md 的對偶：那裡隨機化製造不可區別性，這裡隨機化製造魯棒性）。

程式碼：SGD 與 Dropout#

import random, math

def sgd(grad_fn, theta0, data, lr=0.01, batch=32, epochs=100):
    theta = theta0
    for _ in range(epochs):
        batch_data = random.sample(data, batch)      # 隨機取樣！
        g = grad_fn(theta, batch_data)               # 有噪聲的梯度
        theta = [t - lr * gi for t, gi in zip(theta, g)]
    return theta

random.seed(42)
# 例：最小化 f(θ) = θ²（梯度 = 2θ）
data = list(range(1000))
grad = lambda th, batch: [2 * th[0] * len(batch) / len(batch)]
theta = sgd(grad, [10.0], data, lr=0.1, epochs=500)
print(f"SGD 收斂到 θ = {theta[0]:.4f}")   # ≈ 0

def dropout(h, p=0.5):
    """訓練時隨機丟棄神經元（inverted dropout）"""
    return [hi / (1 - p) if random.random() > p else 0.0 for hi in h]

# 500 次訓練集成 ≈ 隨機化的魯棒性

LLM 取樣：隨機化的生成#

大型語言模型的生成是蒙地卡羅取樣的直系後代：模型輸出下一個 token 的機率分佈 \(P(x_{t+1} | x_{1..t})\) ，生成方式：

取樣策略	公式	特點
Greedy	\(x = \arg\max P\)	確定，常重複
Temperature	\(P(x) \propto e^{\log P(x)/T}\)	\(T\) 控制隨機度
Top-p (nucleus)	從累積機率 \(\ge p\) 的核心取樣	平衡品質與多樣性

推理的哲學：創造性的本質是受控的隨機性—— \(T=0\) 的模型只會抄襲訓練資料的「最大機率」， \(T\) 高一點的模型才能組合出新答案。蒙地卡羅方法的兩百年後，擲骰子成為創造的引擎。

現代隨機算法的版圖#

2020 年代的隨機算法全景：

訓練：SGD、Dropout、資料增強（隨機裁剪/翻轉）、LoRA 隨機初始化
推理：LLM 取樣、MCTS（AlphaGo 的蒙地卡羅樹搜索）
估算：HLL、CMS、MinHash 的大數據統計
密碼學：Miller–Rabin、PRG、零知識證明（隨機挑戰）
理論：BPP = P 懸案、平滑分析、隨機提取器

偵探筆記：本案的推理是「正名」——1946 年 Ulam 的隨機是「無奈的替代」（解析算不了才模擬），2020 年代的隨機是本質的方法：噪聲幫助泛化、隨機製造創造、取樣逼近分佈。從 Buffon（1777）到 LLM（2020s），隨機算法完成了從「擲針估 π」到「擲骰子寫文章」的旅程——但靈魂從未改變：用受控的隨機，換取確定的統計答案。

結案 -- 後果與影響#

深度學習的引擎：沒有 SGD 的隨機化，億級參數模型的訓練不可行——隨機算法成為 AI 時代的基礎設施。
隨機性的哲學地位：噪聲是特性（逃鞍點、隱式正則化）——「隨機性或許無本質力量」（BPP=P 懸案）與「隨機性是本質方法」（ML）並存不悖：一個說計算複雜度，一個說優化與泛化。
MCTS 與 AlphaGo：2016 年 AlphaGo 的蒙地卡羅樹搜索擊敗李世石——蒙地卡羅方法（1946）的巔峰時刻。
LLM 的創造性：溫度取樣使 AI 能生成原創文字——隨機性的新哲學。
理論待續：BPP vs P、電路下界、平均複雜度——隨機算法的理論故事還沒寫完。

關鍵人物與文獻#

Robbins & Monro：隨機逼近 (1951)——SGD 的理論源頭
Hinton et al.：Dropout (2012, AlexNet)、圖靈獎 2018
Keskar et al.：隱式正則化 (2017)
Jin et al.：SGD 逃離鞍點 (2017)
Silver et al.：AlphaGo / MCTS (2016)
交叉參照：1946-Ulam蒙地卡羅.md、1905-布朗運動.md、1953-MetropolisHastings演算法.md、1985-BlumMicali偽隨機產生器.md