什麼是 Rademacher Complexity？
Rademacher Complexity的定義為在給定資料集上，假設空間對隨機標籤的適應能力，用已衡量模型在隨機標籤下的表現，從而推導出模型的泛化誤差界限。
也就是說，它衡量了假設空間中函數（Function）在隨機噪聲下的適應能力，它與 VC 維度類似，但更加精細，可以捕捉到假設空間的實際複雜度。
- Rademacher Complexity 越高，表示模型更容易擬合隨機噪聲，泛化能力可能越差，越有過擬合（Overfitting）的情況發生。
- Rademacher Complexity 越低，表示模型不容易擬合隨機噪聲，過擬合的風險較低，泛化能力往往較強。但如果 Rademacher Complexity 過低，模型可能會欠擬合（Underfitting），無法充分學習資料當中的有用資訊。
Rademacher Complexity 的範圍通常在 0~1 之間
- 當 Rademacher Complexity 接近 1 時，表示模型在隨機標籤上表現得非常好，能夠擬合隨機的數據波動，這意味著模型的複雜度很高，且很有可能會產生過擬合。
- 當 Rademacher Complexity 接近 0 時，表示模型幾乎無法擬合隨機標籤。這通常意味著模型比較簡單，對隨機噪聲不敏感，具有較強的泛化能力。
甚麼是泛化誤差?
泛化誤差（Generalization Error） 是機器學習中的一個重要概念，它表示模型在新資料（即模型在訓練過程中沒有學習過的資料）上的表現與準確性；泛化誤差衡量的是模型對於從同樣的資料分佈中抽取的測試資料的預測誤差。
- 訓練誤差（Training Error）：模型在訓練集上的預測誤差。
- 泛化誤差（Generalization Error）：模型在測試資料集或未見過的新資料上的預測誤差。
推導模型的泛化誤差方法
- Rademacher Complexity (拉德馬赫複雜度)
- VC 維度（Vapnik-Chervonenkis 維度）
- Hoeffding 不等式（Hoeffding’s Inequality）
- PAC 學習框架中的界限（Probably Approximately Correct Learning）
估計Rademacher Complexity範例
計算 Rademacher 複雜度通常需要手動實現，因為目前的機器學習庫（如 Scikit-learn）沒有直接提供這一功能。以下是一個簡單的 Python 程式，展示如何估計 Rademacher 複雜度。
安裝所需的套件
先在Jupyter Notebook當中安裝需要的套件(前面要加上 ! )
!pip install scikit-learn numpy計算 Rademacher Complexity
我們會先寫一個100次的Rademacher 複雜度估計，然後建立決策樹模型，並進行複雜度的估計，最後在繪製一個X軸為隨機抽樣的特徵數量，Y軸為Rademacher 複雜度與分類模型的F1-score估計，下面的範例code可以從我的colab上進行操作。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import f1_score
# 計算Rademacher 複雜度，並設計實驗次數
def calculate_rademacher_complexity(X, y, model, num_trials=100):
"""
計算模型的 Rademacher 複雜度
Parameters:
X (ndarray): 特徵
y (ndarray): 標籤
model: 機器學習模型
num_trials (int): 進行 Rademacher 隨機實驗的次數
Returns:
float: Rademacher 複雜度的估計值
"""
n = X.shape[0]
complexity = 0.0
for _ in range(num_trials):
# 生成 Rademacher 符號（+1 或 -1）
sigma = np.random.choice([-1, 1], size=n)
# 訓練模型
model.fit(X, sigma)
# 預測並計算符號的匹配
predictions = model.predict(X)
match = sigma * predictions
complexity += np.sum(match) / n
# 計算平均值
complexity /= num_trials
return complexity
# 加載鳶尾花資料集(原本為3分類)
X, y = load_iris(return_X_y=True)
X = X[y != 2] # 轉換為二分類問題
y = y[y != 2]
# 分割訓練和測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=28)
# 建立決策樹模型
model = DecisionTreeClassifier(max_depth=5)
# 決策樹使用全部特徵建模得到的rademacher_complexity值
base_model_rc = calculate_rademacher_complexity(X_train, y_train, model, num_trials=100)
print("Decision Tree使用全部特徵的rademacher_complexity \n", base_model_rc.round(4))
# 設定不同的特徵數量 n, 由少至多
n_values = np.arange(1, X_train.shape[1] + 1)
rademacher_complexities = []
f1_scores = []
# 計算每個 n 對應的 Rademacher 複雜度和 F1-score
for n in n_values:
# 隨機抽取 n 個特徵
X_train_n = X_train[:, :n]
X_test_n = X_test[:, :n]
# 訓練並計算 Rademacher 複雜度
rc = calculate_rademacher_complexity(X_train_n, y_train, model, num_trials=100)
rademacher_complexities.append(rc)
# 訓練並計算 F1-score
model.fit(X_train_n, y_train)
y_pred = model.predict(X_test_n)
f1 = f1_score(y_test, y_pred)
f1_scores.append(f1)
# 繪製折線圖
fig, ax1 = plt.subplots(figsize=(10, 6))
# 繪製 Rademacher 複雜度
color = 'tab:blue'
ax1.set_xlabel('Number of Features (n)')
ax1.set_ylabel('Rademacher Complexity', color=color)
ax1.plot(n_values, rademacher_complexities, color=color, marker='o', label='Rademacher Complexity')
ax1.tick_params(axis='y', labelcolor=color)
ax1.grid(True) # 添加網格
# 設置右側 Y 軸 (F1-score)
ax2 = ax1.twinx()
color = 'tab:red'
ax2.set_ylabel('F1-score', color=color)
ax2.plot(n_values, f1_scores, color=color, marker='o', linestyle='--', label='F1-score')
ax2.tick_params(axis='y', labelcolor=color)
# 添加標題
plt.title('Rademacher Complexity and F1-score vs Number of Features')
fig.tight_layout() # 確保圖形不重疊
plt.show()最後的輸出結果:
Decision Tree使用全部特徵的rademacher_complexity
0.6049
討論
可以發現特徵數量的提升與F1-score的提升，是相對幅度的成長，也就是說iris dataset的四項特徵，對於分類模型都有很顯著的提升。
同時在rademacher complexity的累積上，也從單一特徵(約0.40)至全部四項特徵(約0.60)，沒有過高的rademacher_complexity值，無須擔心泛化誤差過大或是過擬合，影響最終分類模型的準確性。