Вектор Шепли

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

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

Перейти к: навигация, поиск

Версия 11:22, 15 июля 2026

Статья написана с использованием LLM DeepSeek-V4и проверена участником Oleg Aleksandrov 15:08, 15 июля 2026 (MSD)

Содержание

1 Вектор Шепли

Вектор Шепли

Вектор Шепли (англ. 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)}}
-== Вектор Шепли ==
+= Вектор Шепли =
-'''Вектор Шепли''' ({{lang-en|Shapley value}}) — метод распределения общего выигрыша между игроками в [[Кооперативная теория игр|кооперативной теории игр]] пропорционально их индивидуальному вкладу. Концепция предложена [[Шепли, Ллойд|Ллойдом Шепли]] в 1953 году. В [[Машинное обучение|машинном обучении]] ({{lang-en|machine learning}}) этот математический аппарат применяется в рамках [[Интерпретируемое машинное обучение|интерпретируемого искусственного интеллекта]] ({{lang-en|Explainable AI, XAI}}) для оценки влияния отдельных [[Признак (машинное обучение)|признаков]] ({{lang-en|features}}) на результат работы предиктивной модели.
+'''Вектор Шепли''' (англ. ''Shapley value'') — решение задачи дележа в теории [[Кооперативные игры|кооперативных игр]] (англ. ''cooperative games''), представляющее собой единственное распределение суммарного выигрыша большой коалиции между её участниками, удовлетворяющее набору аксиом справедливости. Значение для каждого игрока определяется как его усреднённый предельный вклад во все возможные коалиции, в которых он мог бы участвовать.
-В задачах блэкбокс-интерпретации вектор Шепли определяет локальную важность признаков для конкретного наблюдения выборки.
+В машинном обучении концепция адаптирована для задач [[Объяснимый искусственный интеллект|объяснимого искусственного интеллекта]] (англ. ''Explainable AI'', XAI), оценки важности признаков (англ. ''feature importance''), ценообразования обучающих данных (англ. ''data valuation'') и распределения вклада участников в [[Федеративное обучение|федеративном обучении]] (англ. ''federated learning'').
-=== Интуиция метода ===
+== Интуитивная интерпретация ==
-В классической постановке теории игр рассматривается коалиция участников, которые совместно генерируют определенную ценность (выигрыш). Задача состоит в справедливом разделении этого выигрыша. Метод Шепли предписывает выделять каждому участнику его средний маргинальный (предельный) вклад по всем возможным сценариям формирования коалиции. Рассматриваются все перестановки игроков, фиксируется прирост общей ценности при присоединении конкретного игрока к уже собранной группе, после чего эти приросты усредняются.
+Задача дележа возникает в любой системе, где агенты действуют сообща, а их индивидуальные вклады неаддитивны. Наивные схемы распределения — поровну или пропорционально изолированной работе каждого — либо игнорируют синергию, либо не учитывают альтернативные сценарии сотрудничества.
-При переносе концепции в плоскость машинного обучения роли распределяются следующим образом:
+Вектор Шепли решает проблему через мысленный эксперимент: участники присоединяются к коалиции последовательно, в случайном порядке. При вступлении каждого нового игрока прирост выигрыша зачисляется на его счёт. Значение Шепли — математическое ожидание такого прироста по всем возможным перестановкам порядка вступления.
-* '''Игроки''' — это признаки исследуемого объекта данных.
-* '''Коалиция''' — подмножество доступных признаков.
-* '''Выигрыш коалиции''' — разница между предсказанием модели на данном подмножестве признаков и базовым (ожидаемым) предсказанием по всей генеральной совокупности.
-=== Математическая формулировка ===
+В задачах машинного обучения роли «игроков» выполняют:
-Пусть кооперативная игра с трансферабельной полезностью задана парой <tex>(N, v)</tex>, где:
+* компоненты входного вектора — для объяснения отдельного предсказания;
-* <tex>N = \{1, 2, \dots, n\}</tex> — конечное множество из <tex>n</tex> игроков (признаков).
+* объекты обучающей выборки — для оценки их полезности;
-* <tex>v: 2^N \to \mathbb{R}</tex> — характеристическая функция, сопоставляющая каждому подмножеству (коалиции) <tex>S \subseteq N</tex> вещественное число <tex>v(S)</tex>, отражающее ценность этой коалиции. По определению <tex>v(\emptyset) = 0</tex>.
+* агенты или базовые модели — для оценки вклада в [[Ансамбли моделей|ансамбли]] (англ. ''model ensembles'').
-Компонента вектора Шепли для <tex>i</tex>-го игрока выражается формулой:
+== Формальное определение ==
-<tex>\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S))</tex>
+Рассматривается кооперативная игра с трансферабельной полезностью, задаваемая парой <tex>(N, v)</tex>, где <tex>N = \{1, \dots, M\}</tex> — множество игроков, а <tex>v: 2^N \to \mathbb{R}</tex> — характеристическая функция, определяющая выигрыш любой коалиции <tex>S \subseteq N</tex>, причём <tex>v(\emptyset) = 0</tex>.
-Здесь:
+Вектор Шепли <tex>\phi(v) = (\phi_1(v), \dots, \phi_M(v))</tex> задаётся формулой:
-* <tex>S</tex> — подмножество игроков, не содержащее игрока <tex>i</tex>.
-* <tex>|S|</tex> — мощность (количество элементов) подмножества <tex>S</tex>.
-* <tex>v(S \cup \{i\}) - v(S)</tex> — маргинальный вклад игрока <tex>i</tex> при его включении в коалицию <tex>S</tex>.
-Весовой коэффициент перед разностью представляет собой вероятность того, что в случайной перестановке множества <tex>N</tex> перед игроком <tex>i</tex> окажется ровно подмножество <tex>S</tex>.
+<tex>\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(M - |S| - 1)!}{M!} \bigl[v(S \cup \{i\}) - v(S)\bigr].</tex>
-==== Аксиоматическое обоснование ====
+Коэффициент перед предельным вкладом совпадает с вероятностью того, что в случайной равновероятной перестановке всех <tex>M</tex> игроков множество предшествующих игроку <tex>i</tex> участников окажется в точности равным <tex>S</tex>. Эквивалентная запись через перестановки <tex>\pi \in \Pi(N)</tex>:
-Вектор Шепли — единственное правило распределения ценности, одновременно удовлетворяющее четырем фундаментальным критериям:
+<tex>\phi_i(v) = \frac{1}{M!} \sum_{\pi \in \Pi(N)} \bigl[v(P_i^\pi \cup \{i\}) - v(P_i^\pi)\bigr],</tex>
-# '''Эффективность (Efficiency):''' Сумма вкладов всех элементов полностью покрывает разность между выигрышем полной коалиции и пустой: <tex>\sum_{i=1}^n \phi_i(v) = v(N) - v(\emptyset)</tex>. В контексте XAI это гарантирует, что отклонение локального прогноза от среднего математического ожидания декомпозируется без остатка.
+где <tex>P_i^\pi</tex> — множество игроков, стоящих перед <tex>i</tex> в перестановке <tex>\pi</tex>.
-# '''Симметричность (Symmetry):''' Если два признака <tex>i</tex> и <tex>j</tex> привносят одинаковую ценность в любое подмножество (<tex>v(S \cup \{i\}) = v(S \cup \{j\})</tex> для всех <tex>S \subseteq N \setminus \{i, j\}</tex>), их расчетные вклады равны: <tex>\phi_i(v) = \phi_j(v)</tex>.
-# '''Болван (Dummy):''' Если признак <tex>i</tex> не изменяет ценность ни одной коалиции (<tex>v(S \cup \{i\}) = v(S)</tex> для всех <tex>S</tex>), его вклад равен нулю: <tex>\phi_i(v) = 0</tex>.
-# '''Аддитивность (Additivity):''' Для двух независимых игр с функциями <tex>v</tex> и <tex>w</tex> выполняется <tex>\phi_i(v + w) = \phi_i(v) + \phi_i(w)</tex>. Это свойство позволяет линейно агрегировать вклады признаков в [[Ансамбль моделей (машинное обучение)|ансамблях моделей]].
-=== Фреймворк SHAP ===
+== Аксиоматика ==
-Прямой перенос теории игр в машинное обучение ограничен тем, что предиктивные алгоритмы требуют на вход фиксированный вектор признаков и не могут вычислить значение функции на произвольном подмножестве <tex>S</tex>. Данную проблему решает метод '''SHAP''' ({{lang-en|SHapley Additive exPlanations}}), предложенный Скоттом Лундбергом и Су-Ин Ли в 2017 году.
+Шепли доказал, что описанная конструкция является '''единственным''' отображением <tex>v \mapsto \phi(v)</tex>, одновременно удовлетворяющим четырём требованиям:
-==== Аппроксимация отсутствующих признаков ====
+* '''Эффективность''' (англ. ''efficiency''): <tex>\sum_{i \in N} \phi_i(v) = v(N)</tex>. Выигрыш большой коалиции распределяется полностью.
+* '''Симметрия''' (англ. ''symmetry''): если для любых <tex>S</tex> выполняется <tex>v(S \cup \{i\}) = v(S \cup \{j\})</tex>, то <tex>\phi_i(v) = \phi_j(v)</tex>.
+* '''Нулевой игрок''' (англ. ''null player''): если <tex>v(S \cup \{i\}) = v(S)</tex> для всех <tex>S</tex>, то <tex>\phi_i(v) = 0</tex>.
+* '''Аддитивность''' (англ. ''additivity''): <tex>\phi_i(v + w) = \phi_i(v) + \phi_i(w)</tex> для любых двух игр на одном множестве игроков.
-В SHAP функция ценности коалиции <tex>v(S)</tex> задается как условное математическое ожидание прогноза модели <tex>f(X)</tex> при фиксированных значениях подмножества признаков <tex>X_S = x_S</tex>:
+Эти свойства задают эталон «справедливого» распределения: любое альтернативное решение неминуемо нарушает хотя бы одно из них.
-<tex>v(S) = \mathbb{E}[f(X) \mid X_S = x_S]</tex>
+== Применение в машинном обучении ==
-Поскольку точное вычисление этого ожидания требует знания многомерной плотности распределения, на практике часто используют маргинальное распределение. Признаки вне коалиции <tex>N \setminus S$</tex> интегрируются по их фоновым значениям из обучающей выборки, что эквивалентно допущению об их независимости от признаков из множества <tex>S</tex>.
+=== Локальная интерпретация моделей: SHAP ===
-==== Аддитивная суррогатная модель ====
+Наиболее распространённое применение концепции в ML реализовано в подходе '''SHAP''' (SHapley Additive exPlanations). Пусть обучена произвольная модель <tex>f: \mathcal{X} \to \mathbb{R}</tex> и требуется объяснить её предсказание на фиксированном объекте <tex>x</tex>. Игроками объявляются компоненты вектора признаков <tex>x_1, \dots, x_M</tex>, а характеристическая функция задаётся условным математическим ожиданием:
-SHAP строит локальное объяснение в виде линейной функции от бинарных переменных:
+<tex>v(S) = \mathbb{E}_{X_{\bar{S}}}\bigl[f(x_S, X_{\bar{S}})\bigr],</tex>
-<tex>g(z') = \phi_0 + \sum_{i=1}^M \phi_i z'_i</tex>
+где <tex>x_S</tex> — значения признаков из <tex>S</tex>, зафиксированные как у объясняемого объекта, а <tex>X_{\bar{S}}</tex> — случайные признаки из дополнительного множества. Благодаря аксиоме эффективности выполняется точное аддитивное разложение:
-Где <tex>z' \in \{0, 1\}^M</tex> — вектор коалиции (1 — признак активен, 0 — признак замещен фоновым значением), <tex>M</tex> — полное число признаков, <tex>\phi_0 = \mathbb{E}[f(X)]</tex> — базовое ожидаемое предсказание, а коэффициенты <tex>\phi_i</tex> соответствуют вектору Шепли.
+<tex>f(x) = \phi_0 + \sum_{i=1}^M \phi_i,</tex>
-=== Методы вычисления ===
+где <tex>\phi_0 = \mathbb{E}[f(X)]</tex> — базовое предсказание по всей выборке. Каждый <tex>\phi_i</tex> интерпретируется как вклад признака <tex>i</tex> в отклонение <tex>f(x)</tex> от среднего значения. Агрегация абсолютных величин <tex>|\phi_i|</tex> по выборке даёт глобальную оценку [[Важность признаков|важности признаков]] (англ. ''feature importance''), более устойчивую, чем встроенные метрики наподобие Gini importance для [[Деревья решений|деревьев решений]] (англ. ''decision trees'').
-Вычисление точного вектора Шепли требует <tex>2^n</tex> проходов модели, что вычислительно невозможно для размерностей <tex>n > 15</tex>. В инженерной практике применяются специализированные алгоритмы аппроксимации:
+=== Оценка ценности обучающих данных ===
-* '''KernelSHAP:''' Модельно-агностический ({{lang-en|model-agnostic}}) метод. Аппроксимирует значения Шепли с помощью локальной взвешенной [[Линейная регрессия|линейной регрессии]]. В качестве функции потерь используется специальное ядро ({{lang-en|Shapley kernel}}), минимизация которого теоретически сводит веса линейной модели к значениям Шепли.
+В парадигме Data-Centric AI возникает задача количественной оценки вклада каждого обучающего примера в итоговое качество модели. Для обучающей выборки <tex>\{z_1, \dots, z_N\}</tex> и метрики качества <tex>U</tex> определяется характеристическая функция:
-* '''TreeSHAP:''' Оптимизированный алгоритм для древесных моделей, таких как [[Дерево решений|деревья решений]], [[Случайный лес|случайные леса]] и [[Градиентный бустинг|градиентный бустинг]] (XGBoost, LightGBM, CatBoost). TreeSHAP оптимизирует вычисление условных математических ожиданий, прослеживая пути в структуре деревьев, что снижает временную сложность с экспоненциальной до полиномиальной <tex>O(TLD^2)</tex>, где <tex>T</tex> — число деревьев, <tex>L</tex> — максимальное число листьев, а <tex>D</tex> — глубина.
-* '''DeepSHAP:''' Метод для [[Нейронная сеть|нейронных сетей]], комбинирующий алгоритм DeepLIFT и теоретические свойства вектора Шепли для эффективного аналитического приближения вкладов через модифицированный бэкпропагейшн.
-=== Ограничения и критика ===
+<tex>v(S) = U\bigl(\mathcal{A}(S)\bigr),</tex>
-Несмотря на солидный математический фундамент, метод имеет ряд уязвимостей при практическом внедрении:
+где <tex>\mathcal{A}</tex> — алгоритм обучения. Величины <tex>\phi_i(v)</tex> называют '''Data Shapley''' и используют для очистки данных от шумовых объектов (отрицательный вклад), выявления атак [[Отравление данных|отравления данных]] (англ. ''data poisoning'') и организации [[Активное обучение|активного обучения]] (англ. ''active learning'').
-* '''Мультиколлинеарность:''' Шаблонное предположение о независимости признаков при вычислении маргинальных распределений приводит к генерации нереалистичных синтетических объектов (находящихся вне распределения, {{lang-en|out-of-distribution}}). Модель штрафуется или поощряется на неестественных комбинациях данных, искажая реальный вклад коррелирующих переменных.
+Прямой расчёт Data Shapley требует переобучения модели на всех <tex>2^N</tex> подвыборках, что делает метод неприменимым для нетривиальных объёмов данных. Это стимулировало разработку специализированных аппроксимаций.
-* '''Вычислительные затраты:''' Применение KernelSHAP на больших тестовых выборках с сотнями признаков требует аппроксимаций высокой степени разреженности, что ведет к росту дисперсии оценок.
-* '''Проблема робастности:''' Метод восприимчив к состязательным атакам ({{lang-en|adversarial attacks}}). Возможно построить "суррогатную" модель-оболочку, которая демонстрирует нейтральные значения SHAP для дискриминирующих признаков, скрывая истинную логику базового алгоритма.
-=== Литература ===
+=== Федеративное обучение и распределение вклада ===
-* {{статья |автор=Shapley L. S. |заглавие=A Value for n-Person Games |журнал=Contributions to the Theory of Games |год=1953 |том=2 |страницы=307—317}}
+В сценариях федеративного обучения множество агентов совместно строят модель, сохраняя локальные данные приватными. Возникает экономическая и алгоритмическая задача: определить, какой клиент принёс больше пользы, чтобы справедливо распределить вознаграждение или скорректировать веса при агрегации параметров. Значения Шепли позволяют учесть не только объём локальных данных, но и их разнообразие и соответствие глобальной задаче.
-* {{статья |автор=Lundberg S. M., Lee S.-I. |заглавие=A Unified Approach to Interpreting Model Predictions |журнал=Advances in Neural Information Processing Systems |год=2017 |том=30 |страницы=4765—4774}}
-* {{статья |автор=Lundberg S. M., Erion G., Chen H. et al. |заглавие=From local explanations to global understanding with explainable AI for trees |журнал=Nature Machine Intelligence |год=2020 |том=2 |номер=1 |страницы=56—67}}
+== Алгоритмы вычисления и аппроксимации ==
-* {{статья |автор=Štrumbelj E., Kononenko I. |заглавие=Explaining prediction models and individual predictions with feature contributions |журнал=Knowledge and Information Systems |год=2014 |том=41 |номер=3 |страницы=647—665}}
-* {{книга |заглавие=The Shapley Value: Essays in Honor of Lloyd S. Shapley |ответственный=ed. by A. E. Roth |издательство=Cambridge University Press |год=1988}}
+Прямое вычисление по определению требует <tex>O(2^M)</tex> запросов к характеристической функции, что делает метод неприменимым при десятках и сотнях игроков. Практические реализации опираются на два класса подходов.
-* {{статья |автор=Sundararajan M., Najmi A. |заглавие=The many Shapley values for model explanation |журнал=International Conference on Machine Learning |год=2020 |страницы=9269—9278}}
+=== Модельно-независимые методы ===
+* '''Метод Монте-Карло''' (англ. ''Monte Carlo method''): равномерное сэмплирование перестановок игроков с усреднением предельных вкладов. Даёт несмещённую оценку, сходимость гарантируется законом больших чисел, но требует тысяч инференс-вызовов для одного объяснения.
+* '''KernelSHAP''': взвешенная линейная регрессия по случайным коалициям с весами, соответствующими ядру Шепли. Позволяет объяснять любые [[Чёрный ящик (машинное обучение)|модели-чёрные ящики]] (англ. ''black-box models'').
+=== Модельно-ориентированные методы ===
+* '''TreeSHAP''': алгоритм точного вычисления значений Шепли для ансамблей деревьев решений и [[Градиентный бустинг|градиентного бустинга]] (англ. ''gradient boosting'') за полиномиальное время. Основан на рекурсивном обходе дерева и одновременном учёте всех путей, что устраняет экспоненциальный перебор.
+* '''DeepSHAP''': аппроксимация для [[Нейронные сети|нейронных сетей]] (англ. ''neural networks''), сочетающая аксиоматику Шепли с правилами обратного распространения, заимствованными из метода DeepLIFT.
+=== Аппроксимации для Data Shapley ===
+* '''TMC-Shapley''' (Truncated Monte Carlo): метод сэмплирования с ранней остановкой, использующий сходимостные критерии для сокращения числа переобучений.
+* '''KNN-Shapley''': подмена сложной модели на [[Метод k-ближайших соседей|метод <tex>k</tex>-ближайших соседей]] (англ. ''k-nearest neighbors''), допускающий вычисление значений Шепли в замкнутой форме за <tex>O(N \log N)</tex>.
+* '''Beta Shapley''': модификация весовой схемы, устраняющая математические артефакты, возникающие при применении классических аксиом к задачам с конечной обучающей выборкой.
+== Ограничения и проблемные места ==
+Механический перенос аксиоматики из теории игр в ML приводит к нескольким концептуальным проблемам.
+=== Распределение вне обучающих данных ===
+При вычислении <tex>v(S)</tex> через маргинальное ожидание модель вынуждена делать предсказания на объектах, в которых значения признаков из <tex>S</tex> и <tex>\bar{S}</tex> склеены независимо. Такие комбинации могут быть физически невозможными, а поведение модели на них не определено. Это искажает значения Шепли и требует аккуратной спецификации условных распределений.
+=== Условные значения Шепли ===
+Использование условного математического ожидания <tex>\mathbb{E}[f(X) \mid X_S = x_S]</tex> решает проблему некорректных объектов, но требует оценки многомерных интегралов по совместному распределению <tex>P(X)</tex>, что вычислительно неподъёмно в пространствах большой размерности.
+=== Каузальность против корреляции ===
+Значения Шепли объясняют механику работы модели, но не [[Каузальный вывод|каузальную структуру]] (англ. ''causal inference'') предметной области. Признак, не имеющий причинного влияния на целевую переменную, может получить высокий <tex>\phi_i</tex> за счёт сильной корреляции с истинно важными признаками. Разграничение прокси-эффектов и реальных вкладов требует явного каузального моделирования.
+== См. также ==
+* [[Кооперативные игры]]
+* [[Объяснимый искусственный интеллект]]
+* [[Важность признаков]]
+* [[LIME]]
+* [[Федеративное обучение]]
+* [[Активное обучение]]
+== Литература ==
+* {{книга
+| автор = Shapley L. S.
+| заглавие = A value for n-person games
+| место = Princeton
+| издательство = Princeton University Press
+| год = 1953
+| том = 2
+| серия = Contributions to the Theory of Games
+| страницы = 307—317
+}}
+* {{статья
+| автор = 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
+| серия = Survey Track
+}}

Вектор Шепли

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

Версия 11:22, 15 июля 2026

Содержание

Вектор Шепли

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

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

Аксиоматика

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты