機器學習模型複雜度的指標：VC維度

VC 維度（Vapnik-Chervonenkis 維度）是一種統計分類模型複雜性的指標。它由 Vladimir Vapnik 和 Alexey Chervonenkis 提出，主要用於學習理論（Learning Theory）和統計學中。

什麼是VC 維度？

VC 維度描述了模型能夠將資料集中的任意分佈情況分開的能力。

也就是說，VC 維度表示的是模型能夠完全「分割」（或稱 shatter）的樣本點的最大數量。

以下是 VC 維度的幾個重要特性：

  1. 分割（Shattering）： 若對於一組 n 個樣本點，模型能夠為這些點的每一種可能的標籤組合找到一個分類邊界，使得所有標籤都正確分類，則稱該模型「分割」了這組樣本點。
  2. VC 維度的定義： 某模型的 VC 維度是它可以分割的樣本點數量的最大值。如果模型的 VC 維度是 d，那麼它可以分割最多 d 個點，但對於任意 d+1 個點，就無法保證可以分割所有可能的標籤組合了。
  3. 模型複雜性： VC 維度越高，模型的複雜性也越高，也表示該模型更有能力處理複雜的資料模式，但同時也更容易發生過擬合。
  4. 泛化能力： VC 維度還可以用來衡量模型的泛化能力，VC 維度較低的模型通常具有較強的泛化能力，但可能在複雜資料上表現不佳；而 VC 維度較高的模型則相反。

VC 維度在機器學習中非常重要，可以幫助我們更好地理解模型的容量和潛在的風險。

而在了解VC 維度之前，我們會需要知道一個也十分重要的東西Growth Function。

Growth Function（增長函數）

Growth Function 是用來衡量某個假設空間 H 的能力，特別是在針對給定的樣本集時，它能夠產生多少種不同的標籤配置。

具體來說，假設我們有一個大小為 n 的樣本集，增長函數 mH(n) 是該樣本集能夠被假設空間 H 產生的所有可能標籤配置的數量。

  • 若 mH(n) = 2n：表示假設空間能夠將樣本集中的每個樣本都完全正確區分，即可以完全打散樣本集。這也意味著模型非常強大，甚至可能過擬合。
  • 若 mH(n) < 2n：表示假設空間無法打散樣本集，模型可能過於簡單或受限制。

增長函數隨樣本數量 n 的增長趨勢是分析模型複雜度的重要指標。

Vapnik-Chervonenkis Dimension（VC 維度）

VC 維度是一個衡量假設空間複雜度的指標，它表示模型能夠完全打散多少個樣本點。

具體來說，對於一個模型 H，若其 VC 維度為 d，則意味著它能夠對最多 d 個樣本進行所有可能的標籤配置（也就是打散），但無法對更多的樣本做到這一點。

  • VC 維度越大，表示模型越複雜，越有能力進行高度擬合，也可能會有更大的過擬合風險。
  • VC 維度越小，表示模型的複雜度較低，可能無法擬合複雜的資料模式，容易欠擬合。

VC維度與資料樣本的分佈與數量無關!

增長函數與 VC 維度的關係

增長函數與 VC 維度密切相關，因為增長函數的增長速度被 VC 維度所控制。

VC 維度是指是模型內部的屬性，通常與模型的複雜度有關。

在機器學習建模中，並不存在直接設置 VC 維度的參數，我們可以通過控制模型的複雜度參數（特徵數量或樹的深度等等）來間接影響 VC 維度。

不同模型的 VC 維度與結構相關：

  • 線性分類器（如 Logistic Regression 或 線性SVM）：VC 維度與特徵空間的維度成正比。比如，對於一個有 d 個特徵的線性分類器，VC 維度通常為 d+1。表示當特徵數量增加時，模型變得更加複雜，就夠擬合更多樣本。
  • 決策樹模型：VC 維度與決策樹的深度（depth）相關。當決策樹的深度增加時，VC 維度會增大，因為樹可以產生更複雜的決策邊界，所以控制樹的最大深度 max_depth 可以間接的控制 VC 維度。
  • 支持向量機（核函數SVM）：使用非線性核函數的ＳＶＭ時，VC 維度取決於核函數的選擇和模型參數，例如更大的 C 值允許更少的分類錯誤，可能增加模型的複雜度和 VC 維度。

增長函數與 VC 維度範例

安裝需要的套件與切分訓練集和測試集

首先先建立1000筆的二元分類資料集，資料集當中含有20項特徵，其中15項是對於分類任務有高重要的特徵資訊，其餘5項則是干擾特徵，以下的code我都會放在我的colab上，可以在網路上面直接執行。

from sklearn.datasets import make_classification
from sklearn.tree import DecisionTreeClassifier
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt
from itertools import combinations

# 生成二元分類資料集
X, y = make_classification(n_samples=1000, n_features=20, n_informative=15, n_classes=2, random_state=28)

# 分割訓練和測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=28)
print(X_train.shape, X_test.shape, y_train.shape, y_test.shape)

(800, 20) (200, 20) (800,) (200,)

得到的訓練集是800筆，測試集200筆。

步驟一：依據資料計算增長函數和ＶＣ維度

from itertools import combinations

# Growth Function 計算邏輯，基於不同的樣本子集進行分類，並估計不同標籤配置的數量
def calculate_growth_function(X, y, model, max_samples=None):
    n = X.shape[0] if max_samples is None else min(X.shape[0], max_samples)
    possible_labelings = set()

    # 遍歷所有子集，計算每個子集的標籤配置
    for subset_size in range(1, n + 1):
        for subset in combinations(range(n), subset_size):
            subset_X = X[list(subset)]
            subset_y_pred = model.predict(subset_X)
            possible_labelings.add(tuple(subset_y_pred))  # 保存不同的標籤配置

    return len(possible_labelings)

# 計算決策樹和 SVM 模型的增長函數
def calculate_growth_function_for_models(X_train, y_train, models):
    growth_function_results = {}
    for model_name, model in models.items():
        model.fit(X_train, y_train)
        growth_function = calculate_growth_function(X_train, y_train, model, max_samples=10)  # 設置子集最大大小
        growth_function_results[model_name] = growth_function
    return growth_function_results

# 定義兩個模型：Decision Tree 和 SVM
models = {
    "Decision Tree": DecisionTreeClassifier(max_depth=5),
    "SVM": SVC(kernel='linear')
}

# 計算增長函數結果
growth_function_results = calculate_growth_function_for_models(X_train, y_train, models)

# 打印結果
print("不同模型對應增長函數的樣本數量：", growth_function_results)


from math import comb

# 計算增長函數與 VC 維度之間的關係
def estimate_vc_dimension_from_growth_function(n, growth_function_value):
    for vc_dim in range(1, n+1):
        # 計算增長函數的上界
        sum_of_combinations = sum(comb(n, i) for i in range(vc_dim + 1))
        if sum_of_combinations >= growth_function_value:
            return vc_dim
    return n

# 假設 n=10, 增長函數為 125 (之前的結果)
n = 10
growth_function_value = growth_function_results['Decision Tree']

# 估計 VC 維度
estimated_vc_dimension = estimate_vc_dimension_from_growth_function(n, growth_function_value)
print("估計出的 VC 維度數量：", estimated_vc_dimension)

不同模型對應增長函數的樣本數量： {'Decision Tree': 143, 'SVM': 132}
估計出的 VC 維度數量： 3

可以看到兩個模型的增長函數其實略有不同的值，但是在最後估計的VC 維度數量都是 3，接著我們將增長函數與VC 維度畫成折線圖，來進一步觀察為何VC 維度數量都是 3。

# 計算不同的增長函數值對應的 VC 維度，並繪製成折線圖
def calculate_vc_dimension_curve(n_values, growth_function_values):
    vc_dimensions = []
    for growth_function_value in growth_function_values:
        vc_dimension = estimate_vc_dimension_from_growth_function(n_values, growth_function_value)
        vc_dimensions.append(vc_dimension)
    return vc_dimensions

# 假設我們有一系列的增長函數值範圍
growth_function_values = range(1, 1025, 100)  # 假設增長函數從 1 到 1024 的不同值
n = 10

# 計算對應的 VC 維度
vc_dimensions = calculate_vc_dimension_curve(n, growth_function_values)

# 繪製增長函數值與 VC 維度之間的折線圖
plt.figure(figsize=(10, 6))
plt.plot(growth_function_values, vc_dimensions, marker='o', color='blue')
plt.xlabel('Growth Function Value')
plt.ylabel('VC Dimension')
plt.title('VC Dimension vs Growth Function')
plt.grid(True)
plt.show()

步驟二：依據ＶＣ維度的增加觀察訓練集合測試集的誤差程度（訓練集是否過擬合）

接下來需要觀察在訓練集和測試集在進行訓練的過程當中，模型會不會有過擬合的問題產生，也就是說，繪製出的訓練集和測試集，兩個樣本之間相同的VC 維度，能不能有相近的誤差程度。

若訓練集和測試集之間的誤差過大，表示模型很可能已經產生過擬合的問題，這也是我們在建立模型上要極力避免的問題。

若訓練集和測試集之間的誤差相近似，表示我們建立的模型本身他的泛化能力是比較好的，能夠穩定的預測沒有見過的測試集，並有相近的準確度。

# 訓練模型並計算訓練和測試誤差隨著不同 VC 維度的變化
def calculate_error_with_vc_dimension(X_train, y_train, X_test, y_test, max_depth_values):
    train_errors = []
    test_errors = []
    vc_dimensions = []

    for depth in max_depth_values:
        # 訓練 Decision Tree 模型
        model = DecisionTreeClassifier(max_depth=depth)
        model.fit(X_train, y_train)

        # 訓練集誤差
        y_train_pred = model.predict(X_train)
        train_error = 1 - accuracy_score(y_train, y_train_pred)
        train_errors.append(train_error)

        # 測試集誤差
        y_test_pred = model.predict(X_test)
        test_error = 1 - accuracy_score(y_test, y_test_pred)
        test_errors.append(test_error)

        # VC 維度與決策樹的深度相關，這裡使用 max_depth
        vc_dimensions.append(depth)

    return vc_dimensions, train_errors, test_errors

# 設定不同的 max_depth 值對應 VC 維度
max_depth_values = range(1, 11)

# 定義 SVM 模型的 VC Dimension 計算與誤差
def calculate_error_with_vc_dimension_svm(X_train, y_train, X_test, y_test, feature_range):
    train_errors = []
    test_errors = []
    vc_dimensions = []

    for num_features in feature_range:
        # 減少特徵數量，模擬 VC 維度的變化
        X_train_reduced = X_train[:, :num_features]
        X_test_reduced = X_test[:, :num_features]

        # 訓練線性 SVM 模型
        model = SVC(kernel='linear')  # 可以使用不同的核函數，例如 'linear'、'rbf' 等
        model.fit(X_train_reduced, y_train)

        # 訓練集誤差
        y_train_pred = model.predict(X_train_reduced)
        train_error = 1 - accuracy_score(y_train, y_train_pred)
        train_errors.append(train_error)

        # 測試集誤差
        y_test_pred = model.predict(X_test_reduced)
        test_error = 1 - accuracy_score(y_test, y_test_pred)
        test_errors.append(test_error)

        # VC 維度與線性模型使用的特徵數量相關，這裡使用 num_features
        vc_dimensions.append(num_features)

    return vc_dimensions, train_errors, test_errors

# 設定不同的特徵數量來模擬 VC Dimension
feature_range = range(1, X_train.shape[1] + 1)

# 計算 Decision Tree 模型的誤差與 VC Dimension
vc_dimensions_dt, train_errors_dt, test_errors_dt = calculate_error_with_vc_dimension(X_train, y_train, X_test, y_test, max_depth_values)

# 計算 SVM 模型的誤差與 VC Dimension
vc_dimensions_svm, train_errors_svm, test_errors_svm = calculate_error_with_vc_dimension_svm(X_train, y_train, X_test, y_test, feature_range)

# 繪製兩個模型的圖
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 6))

# 圖1: Decision Tree
ax1.plot(vc_dimensions_dt, train_errors_dt, label='Training Error', marker='o', color='blue')
ax1.plot(vc_dimensions_dt, test_errors_dt, label='Testing Error', marker='o', color='red')
ax1.set_xlabel('VC Dimension (Max Depth of Decision Tree)')
ax1.set_ylabel('Error Rate')
ax1.set_title('Decision Tree: Training and Testing Error vs VC Dimension')
ax1.legend()
ax1.grid(True)

# 圖2: SVM 模型
ax2.plot(vc_dimensions_svm, train_errors_svm, label='Training Error', marker='o', color='blue')
ax2.plot(vc_dimensions_svm, test_errors_svm, label='Testing Error', marker='o', color='red')
ax2.set_xlabel('VC Dimension (Number of Features)')
ax2.set_ylabel('Error Rate')
ax2.set_title('SVM: Training and Testing Error vs VC Dimension')
ax2.legend()
ax2.grid(True)

plt.tight_layout()
plt.show()

討論

從上面的圖可以看的出來，在VC 維度為3或是4的時候，其實就能夠將錯誤率降低到0.2~0.3之間，同時在測試集的表現上也是如此，結果也表明這樣的VC 維度估計法可以掌握在模型當中:

  • 線性模型所挑選的特徵數量
  • 樹結構模型所設定的深度 depth

以避免模型進一步學習了過於複雜的資料內容，導致過擬合現象的產生。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *