Интерпретация моделей и диагностика сдвига данных: LIME, SHAP и Shapley Flow13.01.2022 16:16

В этом обзоре мы рассмотрим, как методы LIME и SHAP позволяют объяснять предсказания моделей машинного обучения, выявлять проблемы сдвига и утечки данных, осуществлять мониторинг работы модели в production и искать группы примеров, предсказания на которых объясняются схожим образом.

Также поговорим о проблемах метода SHAP и его дальнейшем развитии в виде метода Shapley Flow, объединяющего интерпретацию модели и многообразия данных.

Содержание

Интерпретация моделей машинного обучения
    Распределение данных
    Сдвиг данных
    Утечка данных
    Локальная интерпретация моделей
LIME: Local Interpretable Model-agnostic Explanations
    Локальное упрощенное представление
    Объясняющая модель
    Примеры и обсуждение
    LIME-SP: объединение локальных интерпретаций в глобальную
SHAP: Shapley Additive Explanation Values
    Shapley values в теории игр
    Shapley regression values
    SHAP values
    Проблемы и ограничения SHAP values
    Independent SHAP
    Kernel SHAP
    Tree SHAP
SHAP на практике
    Waterfall plot
    Summary plot
    Dependence plot
    Диагностика сдвига данных с помощью SHAP loss values
    Supervised-кластеризация данных с помощью SHAP
Проблемы SHAP values
    SHAP values в условиях взаимной зависимости признаков
    Соблюдение границ многообразия данных
Shapley Flow
    Использование метода Shapley Flow
    Принцип работы метода Shapley Flow
Заключение
Список источников

Интерпретация моделей машинного обучения

Модели машинного обучения (такие как нейронные сети, машины опорных векторов, ансамбли решающих деревьев) являются «прозрачными» в том смысле, что все происходящие внутри них вычисления известны. Но тем не менее часто говорят, что модели машинного обучения плохо интерпретируемы. Здесь имеется в виду то, что процесс принятия решения не удается представить в понятной человеку форме, то есть:

Понять, какие признаки или свойства входных данных влияют на ответ
Разложить алгоритм принятия решения на понятные составные части
Объяснить смысл промежуточных результатов, если они есть
Описать в текстовом виде алгоритм принятия решения (возможно, с привлечением схем или графиков)

Достичь полной интерпретируемости в машинном обучении, как правило, не удается, но даже частичная интерпретация может существенно помочь. Обзор способов интерпретации моделей машинного обучения можно найти, например, в Linardatos et al., 2020 и Li et al., 2021. Чем же может помочь интерпретация модели?

Во-первых, интерпретировав алгоритм, мы можем открыть для себя что-то новое о свойствах исследуемых данных (например, какие признаки в табличных данных в наибольшей степени влияют на ответ).

The need to explain predictions from tree models is widespread. It is particularly important in medical applications, where the patterns uncovered by a model are often even more important than the model«s prediction performance. (Lundberg et al., 2019)

Во-вторых, интерпретация модели помогает оценить ее качество. Если мы узнаем, на что именно обращает модель, какими правилами руководствуется при предсказании, то сможем оценить правдоподобность этих правил.

Humans usually have prior knowledge about the application domain, which they can use to accept (trust) or reject a prediction if they understand the reasoning behind it. (Ribeiro et al., 2016)

Казалось бы, разве недостаточно знать метрику качества модели на тестовой выборке? Часто может оказаться, что после развертывания модель работает в среднем хуже, чем на тестовой выборке из-за ряда проблем, таких как сдвиг и утечка данных.

Распределение данных

На протяжении всего обзора будет использоваться понятие распределения данных, поэтому сначала повторим значение этого понятия.

Если модель использует входных признаков, и -й признак принимает значения из множества X_i , то все пространство признаков равно $X = X_1 \times X_2 \times \dots \times X_N$ . Однако на практике далеко не все сочетания этих признаков возможны, то есть область реальных данных представляет собой лишь малую часть пространства .

Как правило, в машинном обучении используется статистический подход (statistical learning framework), при котором имеющийся датасет $D = \{x_i, y_i\}_{i=1}^\ell$ рассматривается как выборка из совместного распределения данных P(x, y) = P(x) P(y|x) , иногда называемого также генеральной совокупностью. Конечно, представление датасета как взятого из распределения P(x, y) довольно условно, потому что обычно мы имеем лишь конечную выборку данных, но не имеем строгого определения для P(x, y) . Но в целом мы считаем, что P(x) наиболее велико для «типичных» примеров , и равно нулю для невозможных примеров. P(x, y) также задает вероятность для любого пожмножества примеров.

Например, пусть мы имеем датасет из объявлений о продаже автомобилей. Для нашего датасета верно, например, следующее:

Количество авто «Lada Granta» превосходит количество авто «Москвич-412»
Количество авто «Победа» с двигателем мощностью 500 л. с. равно нулю

Тогда мы можем считать датасет выборкой из распределения, в котором для P(x) верно следующее:

$P(x|\text{марка}(x) = \text{$ P (x|\text{марка}(x) = \text{«Москвич-412»})» src=«https://habrastorage.org/getpro/habr/upload_files/a55/b46/561/a55b46561c0e8ab7c42cd45613668180.svg» />
$P(x|\text{марка}(x) = \text{$

Таким образом, описывает соотношение разных типов примеров, и датасет рассматривается как выборка из . На таком подходе основана большая часть теоретических исследований, посвященных машинному обучению, в которых доказывается эффективность тех или иных методов.

Модели машинного обучения делятся в основном на дискриминативные и генеративные, при этом генеративные моделируют P(x) или P(x, y) , а дискриминативные — только P(y|x) , при этом в регрессии, как правило, упрощая его до мат. ожидания $E_{x \sim P(x)}[y|x]$ . Если ваша модель предсказывает целевой признак по исходным — то это дискриминативная модель. Но такие модели не выучивают никакой информации о распределении P(x) , то есть о том, насколько правдоподобно сочетание входных признаков и лежит ли оно в области реальных данных, то есть само многообразие данных не моделируется.

Сдвиг данных

Сдвиг данных (data shift) означает, что данные, на которых модель будет применяться, среднестатистически отличаются от тех, на которых модель обучалась и тестировалась, то есть распределение входных данных отличается при тестировании и применении: $P_{test}(X, Y) \neq P_{usage}(X, Y)$ . Поскольку P(X, Y) = P(Y|X)P(X) , то двумя вариантами сдвига данных являются:

Сдвиг в распределении исходных данных
Сдвиг в условном распределении целевой переменной

Проблема 1. Большинство метрик качества (accuracy, MSE, logloss, F1 и другие) зависят от распределения исходных данных P(X) , то есть, упрощенно говоря, от соотношения разных типов примеров в датасете. Например, пусть модель тестировалась на датасете, в котором 80% изображений были высокого качества (HQ), а применяться будет в условиях, когда, наоборот, 80% изображений будут низкого качества (LQ). Пусть мы сравниваем две модели: на HQ-изображениях точность первой модели лучше, чем второй, а на LQ-изображениях, наоборот, точность второй модели лучше, чем первой. Если при тестировании большая часть изображений были HQ, то мы сделаем вывод, что первая модель лучше, тогда как на самом деле лучше была бы вторая.

Проблема 2. В обучающих и тестовых данных могут присутствовать такие корреляции, которые не обобщаются на другие выборки. Например, мы классифицируем животных по изображению, но большинство изображений рыб, которые у нас имеются, содержат также пальцы рыбака (эти изображения мы используем как при обучении, так и при тестировании). Модель может научиться классифицировать как рыбу изображение, содержащее пальцы, что в целом неверно и может не работать на других выборках (Brendel and Bethge, 2019).

Проблема 3. Обучающие данные часто недостаточно разнообразны, то есть не покрывают все те типы примеров, на которых желательна корректная работа модели (либо покрывают их в неправильном соотношении). Поэтому при применении модели могут встречаться примеры таких типов, которые никогда не встречались при обучении или встречались редко, то есть лежали вне распределений $P_{train}$ и $P_{test}$ (out-of-distribution, OOD). Иными словами, $\{x | P_{train}(x) > 0\} \subsetneq \{x | P_{usage}(x) > 0\} \subsetneq X» src=«https://habrastorage.org/getpro/habr/upload_files/0d3/db0/254/0d3db025497c2d8987b11677b3200f10.svg» /> (<em>рис. 1</em>), и модель, обучающаяся на <img alt=$ , может не научиться корректно работать на $P_{usage}$ . Таким образом, gримеры некоторых типов не встречались при обучении, но на них желательна корректная работа модели, как минимум для защиты от атак, «обманывающих» модель (рис. 1) (cм. Brown et al., 2017; Akhtar and Mian, 2018).

Например, в датасете из фотографий практически исключено появление фотографий собаки, покрашенной в радужные цвета, или фотографий лица человека, которому на лоб приклеено фото другого человека. Такие изображения считаются OOD-данными. Также OOD-данными можно считать примеры с очень редкими значениями каких-либо признаков, которые имеют мало шансов попасть в обучающую выборку. Диагностика сдвига данных является важной практической задачей (Yang et al., 2021), а способность модели обобщаться на большее разнообразие примеров и ситуаций, чем те, что встречались при обучении, является открытой проблемой в машинном обучении и одной из метрик «интеллектуальности» модели (Shen et al., 2021; Goyal and Bengio, 2020; Battaglia et al., 2018; Chollet, 2019).

Рис. 1. Примеры некоторых типов не встречались при обучении, но на них желательна корректная работа модели, как минимум для защиты от атак, Рис. 1. Примеры некоторых типов не встречались при обучении, но на них желательна корректная работа модели, как минимум для защиты от атак, «обманывающих» модель.

Утечка данных

Утечкой данных (data leakage, или target leakage) называется ситуация, когда существует некий признак, который при обучении содержал больше информации о целевой переменной, чем при последующем применении модели на практике. Например, ID пациента может сильно коррелировать с диагнозом, но только в текущем датасете (который поделен на обучающую и тестовую часть). Модель, предсказывающая диагноз по ID, будет иметь высокую точность на тестовом датасете, но в целом очевидно, что в данной задаче такой способ предсказания некорректен и не будет хорошо работать на других данных. Утечка данных является частным случаем сдвига данных, поскольку зависимость ID $\to$ диагноз была в $P_{train}$ и $P_{test}$ , но ее не будет в $P_{usage}$ . Диагностировать утечку данных не всегда просто.

Еxample for this is KDD-Cup 2008 breast cancer prediction competition, where the patient ID contained an obvious leak. It is by no means obvious that removing this feature would leave a leakage-free dataset, however. Assuming different ID ranges correspond to different health care facilities (in different geographical locations, with different equipment), there may be additional traces of this in the data. If for instance the imaging equipment’s grey scale is slightly different and in particular grey levels are higher in the location with high cancer rate, the model without ID could pick up this leaking signal from the remaining data, and the performance estimate
would still be optimistic (the winners show evidence of this in their report). (Kaufman et al., 2011)

Если удастся интерпретировать модель (хотя бы приблизительно), то мы получим дополнительную информацию, которая поможет надежнее оценить ее качество в условиях возможной утечки и сдвига данных.

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

Вместо попыток интерпретировать модель целиком, что может быть очень сложно, мы можем рассмотреть задачу интерпретации ответа модели на конкретном, фиксированном примере x_0 . Например, если на данном изображении модель распознала собаку, то почему она распознала собаку? Какие части и свойства изображения повлияли на предсказание модели?

Local explanations have a distinct advantage over global explanations because by only focusing on a single sample they can remain more faithful to the original model. We anticipate that in the future local explanations will become foundational building blocks for many downstream tasks in machine learning. (Lundberg et al., 2019)

Для ответа на этот вопрос мы можем изменять x_0 и смотреть, как изменится при этом ответ модели, то есть мы изучаем зависимость $f(x_0 + \Delta x)$ от $\Delta x$ . При этом возможно удастся с хорошей точностью аппроксимировать эту зависимость простой функцией $g(\Delta x)$ . Такой подход называется локальной аппроксимацией модели в окрестности точки x_0 .

Например, рассчитав градиент $\nabla f(x)$ в точке x_0 мы узнаем, как изменится ответ при очень малых изменениях $\Delta x$ . При этом мы получаем локальную линейную аппроксимацию (в курсе высшей математики такая аппроксимация называется дифференциалом функции ). Такой подход используется, например, при расчете так называемых saliency maps в компьютерном зрении (Simonyan et al., 2013) — производных выходных значений сети по отдельным пикселям изображения. Но такая аппроксимация далеко не всегда адекватна:

Производная локальна и не говорит о том, как изменится ответ при существенных изменениях $\Delta x$ . Например, если один из признаков достиг состояния «насыщения», то есть значение данного признака более чем достаточно, чтобы сделать какой-то вывод о целевой переменной, то производная по нему почти равна нулю. Эффект будет лишь если мы сильно изменим данный признак.
В некоторых моделях (решающих деревьях) производная либо равна нулю, либо не существует.
Для бинарных признаков производная не всегда информативна, поскольку малое изменение признака ведет в «невозможную» область нецелого значения, в котором модель и не обязана работать корректно.

Есть и другие подходы к локальной интерпретации модели. В качестве $\Delta x$ мы можем рассматривать некий набор осмысленных, не бесконечно малых изменений входных данных — такой подход используется в методе LIME (Ribeiro et al., 2016).

Также мы можем интерпретировать не само предсказание f(x_0) , а одну из следующих величин:

Разницу между двумя предсказаниями $\Delta y = f(x_0) - f(x_{background})$
Разницу между текущим и усредненным предсказанием $\Delta y = f(x_0) - E[f(x)]$ .

Это означает, что мы пытаемся объяснить изменение в предсказании, вызванное изменением входных признаков (в первом случае) или появлением информации о входных признаках (во втором случае). При этом мы вычисляем вклад каждого признака в $\Delta y$ . Такой подход используется в методе SHAP (Lundberg and Lee, 2017).

Методы LIME и SHAP можно применить к любой модели машинного обучения, поскольку они никак не используют информацию о том, как устроена модель «изнутри», то есть являются model-agnostic методами (хотя существуют вычислительно эффективные реализации для конкретных видов моделей, такие как Tree SHAP).

Существуют также специфические способы интерпретации, позволяющие объяснить $\Delta y$ для конкретных типов моделей, например DeepLIFT (Shrikumar et al., 2017) и Integrated Gradients (Sundararajan et al., 2017) для нейронных сетей (т. е. дифференцируемых моделей). Эти методы в данном обзоре мы не будем рассматривать. Обзор других методов локальной интерпретации моделей можно найти, например, в Lundberg et al., 2019, раздел «Methods 7».

LIME: Local Interpretable Model-agnostic Explanations

LIME (Ribeiro et al., 2016) — это подход к интерпретации ответа модели f(x_0) на конкретном тестовом примере x_0 с помощью вычисления значений $f(x_0 + \Delta x)$ для некоторого конечного набора значений $\Delta x$ . Иллюстрация работы метода LIME приведена на рис. 2. Чтобы формально описать метод LIME, нам понадобится ввести ряд обозначений, которые мы будем использовать и в следующих частях обзора.

Рис. 2. Иллюстрация работы метода LIME. Рис. 2. Иллюстрация работы метода LIME.

Мы интерпретируем модель на примере x_0 :

$f: X \to Y$ — исходная модель
$x_0 \in X$ — выбранный тестовый пример, предсказание на котором интерпретируется

Локальное упрощенное представление

Для примера x_0 вводим осмысленных, интерпретируемых изменений $\Delta_i$ . Например, для изображений таким изменением может быть удаление отдельного суперпикселя, то есть участка изображения с похожим содержимым и четкими границами (рис. 1b). Каждое изменение бинарно, то есть оно либо есть, либо нет. Соответственно, мы получаем 2^M различных вариантов $\Delta x$ . Наличие или отсутствие каждого из изменений можно описать числом 0 или 1: из этих чисел можно собрать бинарный вектор размерностью , который будем называть упрощенным представлением (рис. 1c).

Например, на рис. 1 функция работает следующим образом: все «пристствующие» суперпиксели ( z_i = 1 ) рисуются без изменений. Все «отсутствующие» суперпиксели ( z_i = 0 ) заполняются белым цветом (либо, как вариант, усредненным цветом соседних суперпикселей). При этом $h([1, 1, \dots, 1]) = x_0$ , поскольку вектор из единиц означает отсутствие всех изменений. Фактически выбор функции равносилен выбору изменений $\Delta_i$ , то есть семантики упрощенного представления.

Функцию мы можем выбрать произвольно, но так, чтобы отдельные изменения $\Delta_i$ были интерпретируемы. При этом мы надеемся, что объяснить предсказание модели на x_0 можно интерпретировать, изучая, как влияют на ответ эти изменения. Конечно, функция может быть выбрана неудачно. Например, если модель определяет стиль фотографии как «ретро» при наличии оттенка «сепия», то изменения отдельных суперпикселей не помогут интерпретировать модель. Если $\Delta_i$ были выбраны неудачно, то всегда можно попробовать заново с другими изменениями $\Delta_i$ .

Для табличных данных мы можем в качестве $\Delta_i$ рассматривать замену одного из признаков на ноль, среднее или медианное значение по обучающему датасету.

Объясняющая модель

Теперь мы можем обучить модель предсказывать значение f(h(z)) по вектору упрощенного представления . При этом модель должна быть простой и интерпретируемой (поскольку смысл метода LIME в интерпретации). Например, это может быть линейная модель или решающее дерево. Чтобы обучить модель, нужно собрать обучающую выборку. Для этого нам потребуется получить ответ модели для разных (то есть для разных $x_0 + \Delta x$ , поскольку определяет $\Delta x$ ) и таким образом собрать обучающую выборку для модели .

Максимально возможный размер обучающей выборки равен 2^M , но обычно велико, и приходится ограничиться перебором лишь некоторых значений . Авторы предлагают уделять основное внимание таким , которые близки к вектору из единиц: это соответствует небольшим изменениям в x_0 (чем больше нулей в , тем больше одновременных изменений x_0 мы рассматриваем). Введем функцию $\pi(z)$ , определяющую меру близости h(z) к x_0 , и назначим веса $\pi(z^{(i)})$ примерам из обучающей выборки.

Примечание. В kernel SHAP, который мы рассмотрим в следующих разделах, в качестве $\pi$ берется функция, назначающая большие веса как векторам с большим количеством единиц, так и векторам с большим количеством нулей. Так мы акцентируем внимание в том числе на значениях с большим количеством нулей, то есть на отдельных интерпретируемых компонентах (напрмер, отдельных суперпикселях в случае изображений).

Для обучения модели осталось выбрать функцию потерь — например, среднеквадратичное отклонение. Эта функция будет сравнивать предсказания моделей и . Авторы предлагают также использовать «штраф за сложность» $\Omega(g)$ — например, количество ненулевых весов в линейной модели. Если в качестве функции потерь выбрано среднеквадратичное отклонение, то задача оптимизации формулируется следующим образом:

$\sum\limits_{i=1}^N w^{(i)} \Big( g(z^{(i)}) - f(h(z^{(i)})) \Big)^2 + \Omega(g) \to \min\limits_g$

В данной формуле мы считаем квадрат разности предсказаний объясняющей модели $g(z^{(i)})$ и исходной модели $f(h(z^{(i)}))$ , и считаем взвешенную сумму по обучающей выборке, используя веса $w^{(i)}$ . Кроме того мы прибавляем штраф за сложность объясняющей модели $\Omega(g)$ .

Таким образом, суть подхода LIME в том, что мы аппроксимируем предсказание модели в окрестности тестового примера x_0 более простой, легко интерпретируемой моделью , которая использует упрощенное представление . Например, если модель линейна, то каждому изменению $\Delta_i$ (например, суперпикселю в изображении) сопоставляется некий вес.

При этом мы надеемся, что такая аппроксимация адекватна, то есть наличие -го изменения линейно влияет на предсказание модели . В некоторых случаях это может оказаться совсем не так, и модель не сможет хорошо обучиться (функция потерь остенется высокой). Например, в случае изображений это может означать, что мы не можем линейно влиять на предсказание модели, удаляя отдельные суперпиксели. Возможно, модель ориентируется не на отдельные объекты, а на цвет изображения в целом. Тогда можно попробовать использовать другое упрощенное представление, элементами которого является информация об усредненном цвете изображения.

Работа алгоритма LIME не зависит от вида модели (нейронная сеть, решающие деревья и т. д.) и никак явно не использует информацию о том, как модель устроена «изнутри», то есть LIME является «model-agnostic» алгоритмом интерпретации.

Примеры и обсуждение

На рис. 3 мы видим объяснение предсказания сверточной нейронной сети Inception (Szegedy et al., 2014). Сначала мы рассматриваем выходной нейрон, соответствующий классу «Electric guitar», и пытаемся аппроксимировать значение на этом нейроне с помощью линейной модели , которая использует информацию о наличии или отстутствии суперпикселей ( бинарных признаков, где — количество суперпикселей). В результате для каждого суперпикселя мы получаем вес, то есть вклад этого суперпикселя в предсказание «Electric guitar», и выделяем суперпиксели с наибольшим весом. Далее повторяем тот же алгоритм для двух других выходных нейронов, соответствующих классам «Acoustic guitar» и «Labrador». Как можно видеть из примера, алгоритм LIME концептуально достаточно прост.

Рис. 3. Пример результатов, полученных с помощью метода LIME. Отмечены суперпиксели с наибольшими весами в линейной объясняющей модели. Рис. 3. Пример результатов, полученных с помощью метода LIME. Отмечены суперпиксели с наибольшими весами в линейной объясняющей модели.

Работа алгоритма LIME определяется выбором набора изменений $\Delta_i$ , этот выбор осуществляется вручную и в каких-то случаях может быть неудачным. Поэтому LIME можно рассматривать как метод, в котором мы сначала формулируем гипотезу о том, как можно было бы объяснить предсказание модели, а затем проверяем ее.

Интересно было бы попробовать применить алгоритм LIME для интерпретации предсказаний человека на различных задачах. Такой подход мог бы дать лучшее понимание плюсов, минусов и границ применимости алгоритма.

Один из минусов заключается в том, что измененные примеры $x_0 + \Delta x$ могут быть неестественными, ненатуральными (например, изображение, в котором стерта часть суперпикселей). Модель , напротив, обучалась только на натуральных примерах, и чаще всего от нее не требуется корректная работа на ненатуральных примерах (не лежащих в многообразии исходных данных, в терминологии из книги Deep Learning, раздел 5.11.3). Хотелось бы проверять работу только для тех $x_0 + \Delta x$ , которые также выглядят натурально. Об этой проблеме мы еще поговорим в дальнейшем в разделе «Соблюдение границ многообразия данных».

Конечно, можно разрабатывать более эффективные способы интерпретации для конкретных предметных областей, но особенность LIME именно в том, что это очень общий подход, который может быть применен к широкому классу моделей. При этом многие детали в нем, в частности вид упрощенного представления, могут быть выбраны произвольно.

LIME-SP: объединение локальных интерпретаций в глобальную

Авторы также предлагают надстройку над алгоритмом LIME, называемую submodular pick (SP), которая может помочь интерпретировать модель в целом, а не только на конкретном примере. Для этого выбирается набор тестовых примеров, и каждый пример интерпретируется алгоритмом LIME, при этом к каждому примеру мы применяем одни и те же по смыслу изменения. Используя линейную модель , в результате мы получаем матрицу , строкой которой является номер примера, столбцом — позиция в векторе упрощенного представления, значением — вес данной позиции на данном примере.

Например, в случае модели, работающей с текстом и использующей bag-of-words, столбец матрицы будет соответствовать номер слова в словаре. Однако с суперпикселями так не получится, поскольку на каждом тестовом примере суперпиксели разные по смыслу.

Получив матрицу , мы можем рассчитать глобальный вес каждой позиции, найдя норму каждого столбца. Также мы можем попытаться выбрать небольшой набор строк матрицы такой, чтобы в этом наборе для каждого столбца хотя бы раз встретилось большое значение. Этот набор строк соответствует набору тестовых примеров, которых предположительно может быть достаточно для глобальной интерпретации модели.

SHAP: Shapley Additive Explanation Values

В данном разделе мы рассмотрим подход SHAP (Lundberg and Lee, 2017), позволяющий оценивать важность признаков в произвольных моделях машинного обучения, а также может быть применен как частный случай метода LIME.

Shapley values в теории игр

Теория игр — это область математики, изучающей взаимодействие (игру) между игроками, преследующими некие цели и действующими по неким правилам. Кооперативной игрой называется такая игра, в которых группа игроков (коалиция) действует совместно. С середины XX века (Shapley, 1952) известны так называмые Shapley values, которые позволяют численно оценить вклад каждого игрока в достижение общей цели.

Примечание. Понятие «игра» в данном случае может ввести в заблуждение. Обычно под игрой понимается противостояние двух и более сторон, здесь же речь пойдет скорее о кооперативном процессе, в котором каждый участник вносит вклад в общий результат.

Определение (Shapley values). Пусть существует характеристическая функция , которая каждому множеству игроков сопоставляет число — эффективность данной коалиции игроков, действующей совместно. Тогда Shapley value для каждого игрока — это число, рассчитываемое по достаточно простой формуле. Обозн