Kernel SHAP hoạt động như thế nào? "Bí mật" đằng sau Hồi quy Tuyến tính có Trọng số

Trong thế giới Machine Learning, có một nghịch lý thú vị: Các mô hình càng mạnh thì càng khó giải thích. Deep Neural Networks, XGBoost, Random Forests - tất cả đều là những "hộp đen" bí ẩn. SHAP (SHapley Additive exPlanations) ra đời để giải quyết vấn đề này, nhưng nó lại đối mặt với một thách thức toán học khổng lồ.

Bài viết này sẽ đi sâu vào Kernel SHAP - một thuật toán thiên tài biến bài toán tính Shapley Value với độ phức tạp $O(2^n)$ thành một bài toán hồi quy tuyến tính đơn giản. Đây không phải magic, mà là sự kết hợp tinh tế giữa lý thuyết trò chơi, thống kê, và tối ưu hóa.

1. Giới thiệu - Từ NP-hard đến Linear Regression

Mở đầu với một nghịch lý
Chúng ta đang đối mặt với một nghịch lý thú vị: Các mô hình càng mạnh mẽ và chính xác thì càng khó giải thích. Deep Neural Networks có thể nhận diện hình ảnh với độ chính xác vượt trội con người, XGBoost dominates các cuộc thi Kaggle, nhưng khi được hỏi "Tại sao mô hình đưa ra dự đoán này?", chúng ta thường chỉ biết nhún vai. Đây chính là vấn đề của các mô hình "hộp đen" (black-box models), cũng là nỗi sợ về những điều không thể lý giải trong học máy cũng hiện hữu tương tự.

SHAP và thách thức tính toán
SHAP (Shapley Additive Explanations) ra đời năm 2017 bởi Lundberg và Lee như một framework hợp nhất để giải thích mô hình. Nó dựa trên nền tảng vững chắc của Lý thuyết Trò chơi - cụ thể là Giá trị Shapley được Lloyd Shapley phát triển năm 1953 (và đoạt giải Nobel Kinh tế năm 2012).

Tuy nhiên, việc áp dụng Shapley Value vào ML gặp phải một rào cản khổng lồ về mặt tính toán. Để tính chính xác giá trị Shapley cho một mô hình với n đặc trưng, ta cần:
- Với $n = 4$: Phải chạy mô hình $4 \times 2^4 = 64$ lần
- Với $n = 32$: Phải chạy mô hình $32 \times 2^{32} = 137.4$ tỷ lần!

Kernel SHAP - Giải pháp thiên tài
Đây chính là lúc Kernel SHAP thể hiện sự elegant của mình. Thay vì tính toán brute-force qua tất cả $2^n$ liên minh (coalitions), Kernel SHAP thực hiện một phép biến đổi thông minh:

1. Chuyển đổi bài toán: Từ việc tính exact Shapley Values sang việc xấp xỉ thông qua một mô hình giải thích tuyến tính.
2. Áp dụng sampling thông minh: Không cần xét tất cả coalitions mà chỉ lấy mẫu một số quan trọng.
3. Sử dụng Weighted Linear Regression: Biến bài toán thành việc fit mô hình tuyến tính có trọng số.

Model-Agnostic - Sức mạnh của tính tổng quát
Một điểm quan trọng: Kernel SHAP là một phương pháp model-agnostic (không phụ thuộc vào mô hình). Điều này có nghĩa:

• Áp dụng được cho MỌI loại mô hình: từ Linear Regression đến Deep Learning
• Không cần biết cấu trúc bên trong của mô hình
• Chỉ cần khả năng query mô hình (đưa input, nhận output)

Kernel SHAP là một thuật toán model-agnostic (tạm dịch: không phụ thuộc vào mô hình) thuộc họ LIME (Local Interpretable Model-agnostic Explanations).

Cấu trúc bài viết

Trong bài viết này, chúng ta sẽ đi sâu vào từng khía cạnh kỹ thuật của Kernel SHAP:
- Phần 2: Phân tích vấn đề cốt lõi - Tại sao không thể tính Shapley Value trực tiếp
- Phần 3: Tìm hiểu nền tảng lý thuyết AFAMs
- Phần 4: Chi tiết 4 bước trong Kernel SHAP Pipeline
- Phần 5: Deep dive vào Shapley Kernel và công thức trọng số
- Phần 6: Ví dụ tính toán cụ thể với 3 features
- Phần 7: Các kỹ thuật tối ưu trong implementation
- Phần 8: Kết luận và nhìn nhận

2. Vấn đề cốt lõi - Tại sao không thể tính Shapley Value trực tiếp?

2.1. Từ Lý thuyết Trò chơi đến Machine Learning

Để hiểu vấn đề, chúng ta cần bắt đầu từ nền tảng - Lý thuyết Trò chơi (Game Theory). Giá trị Shapley được phát triển để giải quyết bài toán phân chia công bằng trong "trò chơi hợp tác" (cooperative game).

Ví dụ trực quan: Hãy tưởng tượng một startup với 3 thành viên: An, Bình, và Châu. Khi làm việc cùng nhau, họ tạo ra lợi nhuận khác với tổng lợi nhuận khi làm riêng lẻ. Đây chính là "hiệu ứng cộng hưởng" (synergy).

Khi áp dụng vào Machine Learning, sự tương ứng được thiết lập như sau:

• Người chơi → Các đặc trưng (features) của tập dữ liệu
• Trò chơi → Việc đưa ra một dự đoán duy nhất cho một điểm dữ liệu cụ thể
• Hàm đặc trưng v(S) → Đầu ra của mô hình khi chỉ sử dụng tập hợp các đặc trưng trong liên minh $S$
• Giá trị Shapley φᵢ → Giá trị SHAP của đặc trưng $i$

2.2. Công thức Shapley Value - Vẻ đẹp và Gánh nặng

Công thức tính Giá trị Shapley cho người chơi (đặc trưng) i được định nghĩa:

$$\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(|N| - |S| - 1)!}{|N|!} [v(S \cup \{i\}) - v(S)]$$

Giải thích từng thành phần:

• $φi(v)$ là giá trị Shapley (đóng góp công bằng) của người chơi $i$.
• $N$ là tập hợp tất cả người chơi.
• $S$ là một liên minh không chứa người chơi i.
• $v(S ∪ ${i}$)−v(S)$ chính là đóng góp cận biên của i khi tham gia vào liên minh S.
• Phần phân số $\frac{|S|!(|N| - |S| - 1)!}{|N|!}$ là trọng số, đại diện cho tất cả các thứ tự hoán vị mà liên minh $S$ có thể hình thành trước khi $i$ tham gia.

2.3. Vấn đề "Bùng nổ tổ hợp" (Combinatorial Explosion)

Đây là điểm then chốt khiến việc tính toán trực tiếp trở nên bất khả thi. Với $n$ đặc trưng, số lượng liên minh cần xét là $2^n$. Cụ thể:

• $n = 4: 4 × 2^4 = 64$ lần chạy mô hình
• $n = 32: 32 × 2^32 = 17.1$ tỷ lần chạy mô hình
  Với chỉ 32 đặc trưng, số lượng liên minh cần xét đã lên đến hàng tỷ, khiến việc chạy mô hình lặp đi lặp lại là không thể.

2.4. Thách thức kỹ thuật: "Missing Features Problem"

Một vấn đề kỹ thuật quan trọng: Làm thế nào để tính $v(S)$ - giá trị mô hình khi chỉ có một số features?

Ví dụ cụ thể: Giả sử mô hình dự đoán giá nhà với 3 features:

• $x₁$: Diện tích $(m²)$
• $x₂$: Số phòng ngủ
• $x₃$: Khu vực (city center hay suburb)

Khi tính $v(${x₁, x₂}$)$, ta cần dự đoán với chỉ diện tích và số phòng ngủ, KHÔNG có thông tin về khu vực. Nhưng mô hình được train với ĐẦY ĐỦ 3 features!

Các cách tiếp cận và vấn đề:

1. Bỏ cột feature?

• Không thể! Mô hình expect đầu vào có đủ chiều
• Sẽ gây lỗi dimension mismatch

2. Điền giá trị 0 hoặc NA?

• Sai lệch! 0 có thể là giá trị hợp lệ
• NA không phải lúc nào cũng được mô hình xử lý

3. Marginalize over missing features?

• Đúng về mặt lý thuyết
• Nhưng cần tính kỳ vọng - rất expensive!

Các thuật toán SHAP hiện đại sử dụng các kỹ thuật xấp xỉ, chẳng hạn như thay thế các đặc trưng còn thiếu bằng các giá trị đại diện từ tập dữ liệu

2.5. Marginal Contribution - Khái niệm then chốt

Để hiểu sâu hơn, khái niệm đóng góp cận biên (marginal contribution):

Ví dụ: Đóng góp của Châu cho liên minh {An, Bình}:

$$\Delta v = v(\{An, Bình, Châu\}) - v(\{An, Bình\})$$

Vấn đề quan trọng: Giá trị đóng góp phụ thuộc vào thứ tự!

• Châu tham gia đầu tiên: đóng góp = $v(\{Châu\}) - v(\varnothing)$
• Châu tham gia cuối: đóng góp = $v(\{An, Bình, Châu\}) - v(\{An, Bình\})$

2.6. Tại sao cần một phương pháp xấp xỉ?

Tổng kết lại, việc tính Shapley Value trực tiếp gặp phải 3 rào cản lớn:
1. Độ phức tạp tính toán $O(2^n)$: Không khả thi với $n > 20$
2. Missing features problem: Không thể đơn giản bỏ features
3. Order dependency: Cần tính trung bình qua TẤT CẢ hoán vị

Đây chính là lý do Kernel SHAP ra đời - biến một bài toán NP-hard thành một bài toán có thể giải được trong thời gian hợp lý.

3. Nền tảng - Additive Feature Attribution Methods (AFAMs)

3.1. Ý tưởng cốt lõi của AFAMs

Kernel SHAP thuộc họ Additive Feature Attribution Methods - các phương pháp giải thích mô hình thông qua một hàm cộng tính đơn giản. Ý tưởng là xấp xỉ mô hình hộp đen phức tạp $f(x)$ bằng một mô hình giải thích tuyến tính $g(x')$:

$$g(x') = \phi_0 + \sum_{i=1}^{M} \phi_i x'_i$$

Các thành phần:
- g(x'): Mô hình giải thích (explainer model)
- x'ᵢ ∈ {0,1}: Vector nhị phân (1 = feature có mặt, 0 = vắng mặt)
- φ₀: Giá trị cơ sở (base value) - dự đoán khi không có feature nào
- φᵢ: Hiệu ứng (effect) của feature $i$ - chính là giá trị SHAP!

3.2. Ví dụ trực quan

• Baseline (φ₀): $mean(predictions) = 0.3$ (30% khả năng được duyệt)
• Dự đoán cho khách hàng A: $f(A) = 0.55$ (55% khả năng)
• Phân tích SHAP:
• Tuổi: $+0.1$ (tăng 10%)
• Thu nhập: $+0.2$ (tăng 20%)
• Nợ xấu: $-0.05$ (giảm 5%)
• Tổng: $0.3 + 0.1 + 0.2 - 0.05 = 0.55 $

3.3. Ba thuộc tính quan trọng của AFAM

Một phương pháp AFAM tốt phải đảm bảo:

1. Local Accuracy (Tính chính xác cục bộ)
- $g(x') ≈ f(x)$ khi $x' ≈ x$
- "You look the same as part of me"
- Đảm bảo giải thích phản ánh đúng hành vi local của mô hình

2. Missingness (Tính vắng mặt)
- Nếu $x'ᵢ = 0$ → $φᵢ$ không ảnh hưởng đến dự đoán
- "We can't do the same without green"
- Feature không được sử dụng thì contribution phải $= 0$

3. Consistency (Tính nhất quán)
- Nếu feature trở nên quan trọng hơn trong mô hình mới, $φᵢ$ phải tăng
- Không thể contribution tăng mà SHAP value lại giảm

3.4. Tại sao chọn mô hình tuyến tính?

Dạng mô hình đơn giản nhất mà con người có thể hiểu là mô hình tuyến tính.

Ưu điểm của linear model:
- Dễ hiểu: Mỗi feature có một hệ số rõ ràng
- Cộng tính: Tổng contributions = tổng thay đổi
- Có closed-form solution: Không cần iterative optimization

3.5. Kết nối với Shapley Values

Điểm then chốt: SHAP đảm bảo rằng các giá trị φᵢ trong mô hình AFAM chính là các giá trị Shapley!

SHAP đảm bảo rằng các giá trị $φᵢ$ này chính là các giá trị Shapley, mang lại cho mô hình giải thích các thuộc tính lý thuyết mong muốn.

Điều này có nghĩa SHAP kế thừa tất cả các thuộc tính toán học đẹp của Shapley Values:
- Efficiency: $$\sum\phi_i = f(x) - E[f(x)]$$
- Symmetry: Features giống nhau có SHAP value giống nhau
- Dummy: Feature không ảnh hưởng có SHAP value $= 0$
- Additivity: SHAP values có thể cộng qua các mô hình

4. Kernel SHAP Pipeline - 4 bước chuyển đổi thần kỳ

Bước 0: Khởi tạo Background Dataset và Baseline Value

Trước khi bắt đầu, Kernel SHAP cần xác định "điểm xuất phát" - giá trị cơ sở $φ₀$. Đây là dự đoán trung bình của mô hình trên toàn bộ tập dữ liệu.

Quy trình:
- Lấy một phần tập training làm background dataset B (thường $100-1000$ mẫu)
- Tính vector trung bình: $$E[x_{bg}]$$
- Giá trị cơ sở: $$\phi_0 = f(E[x_{bg}])$$

Bước 1: Tạo Coalition Samples (Mẫu liên minh)

Thay vì tính tất cả $2^n$ coalitions, Kernel SHAP lấy mẫu thông minh:

Quá trình tạo mẫu "lai" (hybrid):
- Lấy mẫu coalition $Z'$ (vector nhị phân)
- $Z' = [1,0,1,0]$ nghĩa là giữ feature 1 và 3
- Tạo mẫu lai: kết hợp giá trị từ $X$ (mẫu gốc) và $B$ (background)

Ví dụ cụ thể:
- Mẫu gốc $X$: [1.4, 2.3, 5.2]
- Background $B$: [1.0, 4.5, 3.2]
- Coalition $Z'$: [0, 1, 0]
- Mẫu lai $Z$: [1.0, 2.3, 3.2]

Bước 2: Tính Shapley Kernel Weights

Đây là "bí mật" của Kernel SHAP - không phải mọi coalition đều quan trọng như nhau.

Công thức trọng số:

$$w_C = \frac{M-1}{\binom{M}{|C|} \times |C| \times (M-|C|)}$$

Phân tích công thức:
- Tử số $(M-1)$: Hằng số chuẩn hóa
- Số coalitions cùng kích thước $$\binom{M}{|C|}$$
- Boundary correction term $$|C| \times (M-|C|)$$

Trường hợp đặc biệt:
- Empty coalition $(|C|=0): w = ∞$
- Full coalition $(|C|=M): w = ∞$
- Đảm bảo mô hình đi qua điểm đầu và cuối

Bước 3: Huấn luyện Weighted Linear Regression

Với dữ liệu đã chuẩn bị, giải bài toán hồi quy:

Input cho regression:
- $X$: Ma trận coalition (binary) $z'$
- $y$: Dự đoán từ mô hình $f(z)$
- $w$: Trọng số từ Shapley kernel

Bài toán tối ưu:

$$\min_{\phi} \sum_{z'} w_{z'} [f(z) - (\phi_0 + \sum_i \phi_i z'_i)]^2$$

Bước 4: Extract SHAP Values và Visualization

Các hệ số $φᵢ$ từ linear regression chính là SHAP values!

Thuộc tính quan trọng - Local Accuracy:

$$\phi_0 + \sum_{i=1}^M \phi_i = f(x)$$

Waterfall Plot - Trực quan hóa:
- Bắt đầu từ baseline $E[f(x)]$
- Mỗi feature "đẩy" hoặc "kéo" dự đoán
- Thanh đỏ: contribution dương
- Thanh xanh: contribution âm
- Kết thúc tại $f(x)$

Tóm tắt Pipeline

# Pseudo-code của Kernel SHAP
1. background_set = sample(training_data, 100)
2. baseline = mean(f(background_set))
3. for coalition in sampled_coalitions:
      hybrid = create_hybrid(x, background, coalition)
      prediction = f(hybrid)
      weight = shapley_kernel_weight(coalition)
4. shap_values = weighted_linear_regression(coalitions, predictions, weights)
5. visualize(sh
ap_values)

5. Deep Dive - Shapley Kernel và Trọng số

5.1. Tại sao cần trọng số đặc biệt?

Không phải mọi coalition đều cung cấp thông tin như nhau về đóng góp của features. Kernel SHAP nhận ra rằng:
- Coalition nhỏ ($1-2$ features): Cho biết đóng góp thuần của từng feature
- Coalition lớn ($M-1$ features): Cho biết marginal contribution khi thêm feature cuối
- Coalition giữa ($M/2$ features): Ít thông tin hơn do nhiều interaction phức tạp

5.2. Phân tích công thức Shapley Kernel

$$w_C = \frac{M-1}{\binom{M}{|C|} \times |C| \times (M-|C|)}$$

Ví dụ cụ thể với M=5 features:

Từ bảng ta thấy:
- Coalition size 1 và 4: Trọng số cao nhất (0.20)
- Coalition size 2 và 3: Trọng số thấp hơn (0.067)
- Phân bố hình chữ $U$ - ưu tiên các coalition ở biên

Tính toán chi tiết cho |C|=1:

$$w = \frac{5-1}{\binom{5}{1} \times 1 \times (5-1)} = \frac{4}{5 \times 1 \times 4} = \frac{4}{20} = 0.20$$

5.3. Infinity Weights - Đảm bảo tính chính xác

Hai coalition đặc biệt được gán trọng số vô cùng:
- Empty coalition $z'$ = [0,0,...,0]: Đảm bảo $g(0) = φ₀$
- Full coalition $z'$ = [1,1,...,1]: Đảm bảo $g(1) = f(x)$

Điều này buộc mô hình linear phải đi qua 2 điểm then chốt, đảm bảo Local Accuracy.

5.4. Ý nghĩa thực tế của trọng số

Shapley kernel thực chất đang:
- Ưu tiên các coalition cung cấp nhiều thông tin (biên)
- Giảm thiểu ảnh hưởng của coalition ít thông tin (giữa)
- Đảm bảo tính công bằng qua việc chuẩn hóa theo số lượng

6. Ví dụ tính toán từng bước với 3 features

6.1. Setup bài toán

Mô hình đơn giản:

$$f(F_1, F_2, F_3) = 5 + 2 \times F_1 + 3 \times F_2 - F_3$$

Dữ liệu:
- Instance cần explain: $X = (5, 2, 4)$
- Background mean: $E[X_bg] = (2, 1, 7)$
- Baseline: $φ₀ = f(2,1,7) = 5$
- Target: $f(5,2,4) = 17$

6.2. Tạo coalition và tính predictions

6.3. Weighted Linear Regression

Giải bài toán với các constraints từ infinity weights:
- $g(0,0,0) = 5$ (baseline)
- $g(1,1,1) = 17$ (target)

Kết quả SHAP values:
- $φ₁ = 6.0$ ($F1$ contribution)
- $φ₂ = 3.0$ ($F2$ contribution)
- $φ₃ = 3.0$ ($F3$ contribution)

6.4. Verification

$$\phi_0 + \phi_1 + \phi_2 + \phi_3 = 5 + 6 + 3 + 3 = 17$$

Interpretation:
- $F1$ (từ 2→5): Tăng dự đoán +6 đơn vị
- $F2$ (từ 1→2): Tăng dự đoán +3 đơn vị
- $F3$ (từ 7→4): Tăng dự đoán +3 đơn vị (giảm penalty)

7. Tối ưu hóa và Tricks trong Implementation

7.1. Sampling Strategy - Lấy mẫu thông minh

Thay vì random sampling, các thư viện SHAP thực tế áp dụng chiến lược lấy mẫu có định hướng:

Ưu tiên theo coalition size:
- Tập trung vào coalitions size 1 và 2 (low-order interactions)
- Coalitions size $M-1$ (marginal effects)
- Skip các coalition giữa nếu $M$ lớn

7.2. Background Set Size Trade-off

Kích thước background set ảnh hưởng trực tiếp đến accuracy và speed:

Khuyến nghị từ:
- Minimum: $50-100$ samples
- Recommended: $100-1000$ samples
- Diminishing returns sau $1000$

7.3. Xử lý Missing Features

Kernel SHAP sử dụng các chiến lược khác nhau cho missing features:

Với Tabular Data:
- Thay thế bằng giá trị từ background set
- Hoặc dùng expected value $E[X_{bg}]$

Với Image Data:
- Blur: Làm mờ vùng bị loại bỏ
- Inpainting: Điền vào bằng thuật toán inpainting
- Noise: Thêm nhiễu vào patch

7.4. Computational Shortcuts

Caching predictions:
- Lưu kết quả $f(z)$ cho các coalition xuất hiện nhiều lần
- Tránh gọi mô hình lặp lại không cần thiết

Vectorization:
- Batch processing thay vì loop
- Tận dụng GPU cho deep learning models

8. Kết luận - Elegance in Simplicity

8.1. Tóm tắt Journey của Kernel SHAP

Kernel SHAP đã thực hiện một hành trình biến đổi ấn tượng:

1. Bắt đầu: Bài toán Shapley Value với độ phức tạp $O(2^n)$
2. Reformulate: Chuyển thành Additive Feature Attribution
3. Approximate: Dùng weighted sampling thay vì exhaustive search
4. Transform: Biến thành Linear Regression - có closed-form solution

8.2. Những đóng góp then chốt

Về mặt lý thuyết:
- Kết nối Game Theory với Machine Learning Explainability
- Đảm bảo các thuộc tính toán học (Local Accuracy, Consistency, Missingness)
- Unified framework cho nhiều phương pháp giải thích

Về mặt thực tiễn:
- Model-agnostic: Áp dụng cho mọi loại mô hình
- Computationally tractable: Khả thi với số features lớn
- Interpretable output: SHAP values có ý nghĩa trực quan

8.3. Hạn chế và hướng phát triển

Hạn chế hiện tại:
- Phụ thuộc vào random seed
- Khó giải thích non-linear local space phức tạp
- Chi phí tính toán vẫn cao với very high dimensional data

Hướng phát triển:
- TreeSHAP: Tối ưu cho tree-based models
- DeepSHAP: Linearizing neural networks
- SHAP Flow: Biểu diễn dạng graph
- HEDGE SHAP: Token-level explanation cho NLP

8.4. Kết luận

Kernel SHAP là minh chứng cho câu nói "Simplicity is the ultimate sophistication". Bằng cách nhìn nhận vấn đề từ góc độ phù hợp và áp dụng các kỹ thuật thông minh, thuật toán đã biến một bài toán NP-hard thành tractable mà vẫn giữ được theoretical guarantees.

Điểm mạnh của Kernel SHAP không chỉ nằm ở tính model-agnostic hay computational efficiency, mà còn ở sự elegant trong thiết kế - kết hợp hài hòa giữa lý thuyết vững chắc và thực tiễn khả thi.

Kết luận: SHAP hiện được coi là chuẩn mực vàng của Explainable AI (XAI) nhờ các lý do chính sau: Nền tảng toán học vững chắc, tính giải thích mạnh bạch và trực quan, phổ quát và linh hoạt.

Bài viết dựa trên tài liệu học tập từ khoá học AI Việt Nam (AIO2025)