Вектор Шепли

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM Qwen 3.7 max thinking и проверена участником Oleg Aleksandrov 15:23, 15 июля 2026 (MSD)

Вектор Шепли (англ. Shapley value) — решение задачи дележа в теории кооперативных игр (англ. cooperative games), представляющее собой единственное распределение суммарного выигрыша большой коалиции между её участниками, удовлетворяющее набору аксиом справедливости. Значение для каждого игрока определяется как его усреднённый предельный вклад во все возможные коалиции, в которых он мог бы участвовать.

В машинном обучении концепция адаптирована для задач объяснимого искусственного интеллекта (англ. Explainable AI, XAI), оценки важности признаков (англ. feature importance), ценообразования обучающих данных (англ. data valuation) и распределения вклада участников в федеративном обучении (англ. federated learning).

Интуитивная интерпретация

Задача дележа возникает в любой системе, где агенты действуют сообща, а их индивидуальные вклады неаддитивны. Наивные схемы распределения — поровну или пропорционально изолированной работе каждого — либо игнорируют синергию, либо не учитывают альтернативные сценарии сотрудничества.

Вектор Шепли решает проблему через мысленный эксперимент: участники присоединяются к коалиции последовательно, в случайном порядке. При вступлении каждого нового игрока прирост выигрыша зачисляется на его счёт. Значение Шепли — математическое ожидание такого прироста по всем возможным перестановкам порядка вступления.

В задачах машинного обучения роли «игроков» выполняют:

компоненты входного вектора — для объяснения отдельного предсказания;
объекты обучающей выборки — для оценки их полезности;
агенты или базовые модели — для оценки вклада в ансамбли (англ. model ensembles).

Формальное определение

Рассматривается кооперативная игра с трансферабельной полезностью, задаваемая парой $(N, v)$ , где $N = \{1, \dots, M\}$ — множество игроков, а $v: 2^N \to \mathbb{R}$ — характеристическая функция, определяющая выигрыш любой коалиции $S \subseteq N$ , причём $v(\emptyset) = 0$ .

Вектор Шепли $\phi(v) = (\phi_1(v), \dots, \phi_M(v))$ задаётся формулой:

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

Коэффициент перед предельным вкладом совпадает с вероятностью того, что в случайной равновероятной перестановке всех $M$ игроков множество предшествующих игроку $i$ участников окажется в точности равным $S$ . Эквивалентная запись через перестановки $\pi \in \Pi(N)$ :

$\phi_i(v) = \frac{1}{M!} \sum_{\pi \in \Pi(N)} \bigl[v(P_i^\pi \cup \{i\}) - v(P_i^\pi)\bigr],$

где $P_i^\pi$ — множество игроков, стоящих перед $i$ в перестановке $\pi$ .

Аксиоматика

Шепли доказал, что описанная конструкция является единственным отображением $v \mapsto \phi(v)$ , одновременно удовлетворяющим четырём требованиям:

Эффективность (англ. efficiency): $\sum_{i \in N} \phi_i(v) = v(N)$ . Выигрыш большой коалиции распределяется полностью.
Симметрия (англ. symmetry): если для любых $S$ выполняется $v(S \cup \{i\}) = v(S \cup \{j\})$ , то $\phi_i(v) = \phi_j(v)$ .
Нулевой игрок (англ. null player): если $v(S \cup \{i\}) = v(S)$ для всех $S$ , то $\phi_i(v) = 0$ .
Аддитивность (англ. additivity): $\phi_i(v + w) = \phi_i(v) + \phi_i(w)$ для любых двух игр на одном множестве игроков.

Эти свойства задают эталон «справедливого» распределения: любое альтернативное решение неминуемо нарушает хотя бы одно из них.

Применение в машинном обучении

Локальная интерпретация моделей: SHAP

Наиболее распространённое применение концепции в ML реализовано в подходе SHAP (SHapley Additive exPlanations). Пусть обучена произвольная модель $f: \mathcal{X} \to \mathbb{R}$ и требуется объяснить её предсказание на фиксированном объекте $x$ . Игроками объявляются компоненты вектора признаков $x_1, \dots, x_M$ , а характеристическая функция задаётся условным математическим ожиданием:

$v(S) = \mathbb{E}_{X_{\bar{S}}}\bigl[f(x_S, X_{\bar{S}})\bigr],$

где $x_S$ — значения признаков из $S$ , зафиксированные как у объясняемого объекта, а $X_{\bar{S}}$ — случайные признаки из дополнительного множества. Благодаря аксиоме эффективности выполняется точное аддитивное разложение:

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

где $\phi_0 = \mathbb{E}[f(X)]$ — базовое предсказание по всей выборке. Каждый $\phi_i$ интерпретируется как вклад признака $i$ в отклонение $f(x)$ от среднего значения. Агрегация абсолютных величин $|\phi_i|$ по выборке даёт глобальную оценку важности признаков (англ. feature importance), более устойчивую, чем встроенные метрики наподобие Gini importance для деревьев решений (англ. decision trees).

Оценка ценности обучающих данных

В парадигме Data-Centric AI возникает задача количественной оценки вклада каждого обучающего примера в итоговое качество модели. Для обучающей выборки $\{z_1, \dots, z_N\}$ и метрики качества $U$ определяется характеристическая функция:

$v(S) = U\bigl(\mathcal{A}(S)\bigr),$

где $\mathcal{A}$ — алгоритм обучения. Величины $\phi_i(v)$ называют Data Shapley и используют для очистки данных от шумовых объектов (отрицательный вклад), выявления атак отравления данных (англ. data poisoning) и организации активного обучения (англ. active learning).

Прямой расчёт Data Shapley требует переобучения модели на всех $2^N$ подвыборках, что делает метод неприменимым для нетривиальных объёмов данных. Это стимулировало разработку специализированных аппроксимаций.

Федеративное обучение и распределение вклада

В сценариях федеративного обучения множество агентов совместно строят модель, сохраняя локальные данные приватными. Возникает экономическая и алгоритмическая задача: определить, какой клиент принёс больше пользы, чтобы справедливо распределить вознаграждение или скорректировать веса при агрегации параметров. Значения Шепли позволяют учесть не только объём локальных данных, но и их разнообразие и соответствие глобальной задаче.

Алгоритмы вычисления и аппроксимации

Прямое вычисление по определению требует $O(2^M)$ запросов к характеристической функции, что делает метод неприменимым при десятках и сотнях игроков. Практические реализации опираются на два класса подходов.

Модельно-независимые методы

Метод Монте-Карло (англ. Monte Carlo method): равномерное сэмплирование перестановок игроков с усреднением предельных вкладов. Даёт несмещённую оценку, сходимость гарантируется законом больших чисел, но требует тысяч инференс-вызовов для одного объяснения.
KernelSHAP: взвешенная линейная регрессия по случайным коалициям с весами, соответствующими ядру Шепли. Позволяет объяснять любые модели-чёрные ящики (англ. black-box models).

Модельно-ориентированные методы

TreeSHAP: алгоритм точного вычисления значений Шепли для ансамблей деревьев решений и градиентного бустинга (англ. gradient boosting) за полиномиальное время. Основан на рекурсивном обходе дерева и одновременном учёте всех путей, что устраняет экспоненциальный перебор.
DeepSHAP: аппроксимация для нейронных сетей (англ. neural networks), сочетающая аксиоматику Шепли с правилами обратного распространения, заимствованными из метода DeepLIFT.

Аппроксимации для Data Shapley

TMC-Shapley (Truncated Monte Carlo): метод сэмплирования с ранней остановкой, использующий сходимостные критерии для сокращения числа переобучений.
KNN-Shapley: подмена сложной модели на метод $k$ -ближайших соседей (англ. k-nearest neighbors), допускающий вычисление значений Шепли в замкнутой форме за $O(N \log N)$ .
Beta Shapley: модификация весовой схемы, устраняющая математические артефакты, возникающие при применении классических аксиом к задачам с конечной обучающей выборкой.

Ограничения и проблемные места

Механический перенос аксиоматики из теории игр в ML приводит к нескольким концептуальным проблемам.

Распределение вне обучающих данных

При вычислении $v(S)$ через маргинальное ожидание модель вынуждена делать предсказания на объектах, в которых значения признаков из $S$ и $\bar{S}$ склеены независимо. Такие комбинации могут быть физически невозможными, а поведение модели на них не определено. Это искажает значения Шепли и требует аккуратной спецификации условных распределений.

Условные значения Шепли

Использование условного математического ожидания $\mathbb{E}[f(X) \mid X_S = x_S]$ решает проблему некорректных объектов, но требует оценки многомерных интегралов по совместному распределению $P(X)$ , что вычислительно неподъёмно в пространствах большой размерности.

Каузальность против корреляции

Значения Шепли объясняют механику работы модели, но не каузальную структуру (англ. causal inference) предметной области. Признак, не имеющий причинного влияния на целевую переменную, может получить высокий $\phi_i$ за счёт сильной корреляции с истинно важными признаками. Разграничение прокси-эффектов и реальных вкладов требует явного каузального моделирования.

См. также

Литература

Shapley L. S. A value for n-person games. — Princeton: Princeton University Press, 1953. — T. 2. — С. 307—317. — (Contributions to the Theory of Games).
Lundberg S., Lee S.-I. A Unified Approach to Interpreting Model Predictions // Advances in Neural Information Processing Systems (NeurIPS). — 2017. — Т. 30. — С. 4765—4774.
Lundberg S. M., Erion G., Chen H., DeGrave A., Prutkin J. M., Nair B., Katz R., Himmelfarb J., Bansal N., Lee S.-I. From local explanations to global understanding with explainable AI for trees // Nature Computational Science. — 2020. — Т. 1. — № 1. — С. 56—67.
Ghorbani A., Zou J. Data Shapley: Equitable Valuation of Data for Machine Learning // Proceedings of the 36th International Conference on Machine Learning (ICML). — 2019. — С. 2242—2251.
Jia R., Zhang C., Zhang Z., Wang X., Dong M. Towards Efficient Data Valuation Based on the Shapley Value // Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS). — 2019. — С. 2731—2739.
Kwon Y., Zou J. Beta Shapley: a unified and noise-reduced data valuation framework for machine learning // Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS). — 2022. — С. 2480—2502.
Rozemberczki B., Watson L., Bayer C., Yang H., Kiss O., Nilsson S., Fehér B., Ferber J. The Shapley Value in Machine Learning // Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI). — 2023.

Источник — «http://recognition.su/wiki/index.php?title=%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80_%D0%A8%D0%B5%D0%BF%D0%BB%D0%B8»

@@ Строка 1: / Строка 1: @@
-{{well|Статья написана с использованием LLM '''DeepSeek-V4'''и проверена участником [[Участник:Oleg Aleksandrov|Oleg Aleksandrov]] 15:08, 15 июля 2026 (MSD)}}
+{{well|Статья написана с использованием LLM '''Qwen 3.7 max thinking''' и проверена участником [[Участник:Oleg Aleksandrov|Oleg Aleksandrov]] 15:23, 15 июля 2026 (MSD)}}
-= Вектор Шепли =
 '''Вектор Шепли''' (англ. ''Shapley value'') — решение задачи дележа в теории [[Кооперативные игры|кооперативных игр]] (англ. ''cooperative games''), представляющее собой единственное распределение суммарного выигрыша большой коалиции между её участниками, удовлетворяющее набору аксиом справедливости. Значение для каждого игрока определяется как его усреднённый предельный вклад во все возможные коалиции, в которых он мог бы участвовать.