如何用Hoeffding不等式估計機器學習模型的泛化誤差

什麼是Hoeffding 不等式?

Hoeffding 不等式的公式：

其中：

• R^(h) 是模型在訓練集上的經驗風險（即平均訓練誤差）。
• R(h) 是模型的真實風險（即在整個數據分佈上的誤差）。
• ϵ 是模型的泛化誤差界。
• n 是訓練集的樣本數。

Hoeffding 不等式範例

我們可以在建立機器學習分類模型的時候，先設定一個誤差區間，並進行Hoeffding 的估計，來得出模型當中的Hoeffding 上界為多少，可以估計出訓練集與測試集之間出現偏差的機率，用來確保模型的泛化誤差界線範圍。

以下的code將會放在我的colab上，可以直接進行運算。

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score

# Hoeffding 不等式的泛化誤差計算函數
def hoeffding_bound(n, epsilon):
    """計算 Hoeffding 不等式的上界"""
    return 2 * np.exp(-2 * epsilon**2 * n)

# 生成簡單的二元分類數據集
np.random.seed(28)
X = np.random.randn(1000, 2)
y = (X[:, 0] + X[:, 1] > 0).astype(int)  # 標籤基於線性分割

# 將數據分成訓練集和測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=28)

# 訓練一個簡單的邏輯回歸模型
model = LogisticRegression()
model.fit(X_train, y_train)

# 計算經驗風險（訓練集誤差）和真實風險（測試集誤差）
train_predictions = model.predict(X_train)
test_predictions = model.predict(X_test)

train_error = 1 - accuracy_score(y_train, train_predictions)
test_error = 1 - accuracy_score(y_test, test_predictions)

# 計算訓練樣本數
n = len(X_train)

# 設定泛化誤差上限 epsilon
epsilon = 0.05

# 使用 Hoeffding 不等式估計泛化誤差界
hoeffding_prob = hoeffding_bound(n, epsilon)

# 顯示結果
print(f"訓練集誤差: {train_error:.4f}")
print(f"測試集誤差: {test_error:.4f}")
print(f"泛化誤差界線 epsilon: {epsilon}")
print(f"Hoeffding 不等式上界: {hoeffding_prob:.6f}")

# 可視化泛化誤差的結果
import matplotlib.pyplot as plt

epsilons = np.linspace(0.01, 0.2, 100)
bounds = [hoeffding_bound(n, e) for e in epsilons]

plt.plot(epsilons, bounds, label='Hoeffding Bound')
plt.axvline(x=epsilon, color='r', linestyle='--', label=f'Epsilon = {epsilon}')
plt.title('Hoeffding Bound for Generalization Error')
plt.xlabel('Epsilon (Generalization Error)')
plt.ylabel('Hoeffding Bound Probability')
plt.legend()
plt.show()

訓練集誤差: 0.0025

測試集誤差: 0.0050

泛化誤差界線: epsilon: 0.05

Hoeffding 不等式上界: 0.036631

討論

訓練集誤差和測試集誤差比較

我們經過上面的運算結果，可以得到:

• 訓練集誤差: 0.0025（0.25%）
• 測試集誤差: 0.0050（0.50%）

上面的結果說明模型並沒有明顯的過擬合或欠擬合問題發生，並且有很好的泛化能力。

表示建立的模型在數據上的擬合效果非常好。

Hoeffding 不等式推論結果

我們所設定的泛化誤差為0.05，而經過計算後的Hoeffding 不等式上界為0.036631，表示訓練出的模型在測試集和訓練集上的表現偏差大於0.05的機率不超過3.66%。

也證明模型在訓練集和測試集的效能表現是相當一致，是一個表現穩定的模型。