Введение в значения SHAP и их применение в машинном обучении

Узнайте, как библиотека SHAP работает внутри

SHAP — это математический метод для объяснения прогнозов моделей машинного обучения. Он основан на концепциях теории игр и может использоваться для объяснения прогнозов любой модели машинного обучения путем расчета вклада каждой функции в прогноз. SHAP может определить наиболее важные особенности и их влияние на предсказание модели. SHAP — это математическая тема, и ее нельзя полностью понять, не объяснив стоящую за ней математику. Тем не менее, мы стараемся максимально упростить математические темы, объясняя их интуицию и предоставляя несколько примеров для каждой темы. Читатель также может пропустить более сложные темы, представленные в дополнительных разделах или приложении. Мы также реализуем различные алгоритмы SHAP с нуля, используя Python, чтобы помочь вам полностью понять, как они работают.

Библиотека SHAP в Python

В этой статье мы изучим различные методы, которые можно использовать для вычисления значений SHAP, и каждый метод будет реализован на Python с нуля. Однако код используется только для демонстрации того, как работают алгоритмы, и он неэффективен для реальных приложений. Библиотека SHAP в Python может использоваться для эффективного расчета значений SHAP модели, и в этой статье мы кратко покажем вам, как использовать эту библиотеку. Мы также используем его для проверки вывода сценариев Python, приведенных в каждом разделе (код был протестирован с помощью shap 0.40.0).

Объяснение прогнозов модели

Большинство моделей машинного обучения предназначены для прогнозирования цели. Здесь очень важна точность прогноза, однако нам также необходимо понимать, почему модель делает тот или иной прогноз. Итак, нам нужен инструмент для объяснения модели. Под объяснением мы подразумеваем, что хотим иметь качественное понимание взаимосвязи между прогнозом модели и компонентами экземпляра данных, которые модель использовала для создания этого прогноза. Эти компоненты могут быть функцией экземпляра данных (если у нас есть табличный набор данных) или набором пикселей в изображении или словом в текстовом документе. Мы хотим увидеть, как наличие (или отсутствие) этих компонентов влияет на прогноз.

Некоторые модели машинного обучения, такие как линейная регрессия или деревья решений, интерпретируемы. Здесь интерпретируемость относится к тому, насколько легко людям понять процессы, которые модель использует для прогнозирования. Например, если мы построим классификатор дерева решений, мы сможем легко понять, как он делает определенный прогноз. С другой стороны, модели глубокого обучения подобны черному ящику, и мы не можем легко понять, как эти режимы делают прогноз. SHAP — это индивидуализированный независимый от модели объяснитель. Модельно-независимый метод предполагает, что объясняемая модель является черным ящиком и не знает, как эта модель работает внутри. Таким образом, независимый от модели метод может получить доступ только к входным данным и прогнозу модели, которую необходимо объяснить. Индивидуальный независимый от модели объяснитель сам по себе является интерпретируемой моделью. Объяснитель может приблизительно сделать такой же прогноз модели, которую нужно объяснить, для конкретного экземпляра данных (рис. 1). Теперь мы можем предположить, что эта интерпретируемая модель имитирует процесс, который исходная модель использует для того, чтобы сделать этот единственный конкретный прогноз. Следовательно, мы говорим, что интерпретируемая модель может объяснить исходную модель. Таким образом, SHAP может объяснить любую модель машинного обучения, не зная, как эта модель работает внутри, и может достичь этого, используя концепции теории игр. Итак, чтобы понять это, во-первых, нам нужно ознакомиться со значениями Шепли.

Ценности Шепли

Значение Шепли — это математическое понятие в теории игр, которое было введено Ллойдом Шепли в 1951 году. Позднее за эту работу он был удостоен Нобелевской премии по экономике. Предположим, что у нас есть кооперативная игра с M игроками, пронумерованными от 1 до M, и пусть F обозначает множество игроков, поэтому F = {1, 2, . . . , М}. Коалиция S определяется как подмножество F (S ⊆ F), и мы также предполагаем, что пустое множество ∅ является коалицией, в которой нет игроков. Например, если у нас есть 3 игрока, то возможные коалиции:

Множество F также является коалицией, и мы называем ее большой коалицией. Легко показать, что для M игроков у нас есть 2M коалиций. Теперь мы определим функцию v, которая отображает каждую коалицию в вещественное число. v называется характеристической функцией. Итак, для каждой коалиции S количество v(S) является действительное число и называется стоимостью коалиции S. Он рассматривается как общий выигрыш или коллективный выигрыш, который игроки в этой коалиции могут получить, если будут действовать сообща. Поскольку в пустой коалиции нет игроков, можно считать, что

Теперь мы хотим знать, что в коалиционной игре с M игроками, каков вклад каждого игрока в общий выигрыш? Другими словами, как наиболее справедливо разделить общий выигрыш между игроками?

Мы можем показать вам, как решить эту проблему на примере. Представьте, что у нас есть игра с 5 игроками, поэтому F = {1, 2, . . . , 5}. Предположим, мы формируем большую коалицию F, добавляя игроков в пустое множество по одному, поэтому каждый раз, когда мы добавляем нового игрока, мы формируем новую коалицию из F. Например, мы сначала добавляем {1} к пустому набору, поэтому текущий набор игроков — {1}, который является коалицией F. Затем мы добавляем {2}, а текущим набором является коалиция {1,2}, и мы продолжаем, пока не получим F={1, 2, 3, 4, 5 }. Когда каждый игрок добавляется к текущему набору игроков, он увеличивает общий выигрыш предыдущей коалиции. Например, если текущий набор равен {1, 2}, общий выигрыш v({1, 2}). После добавления {3} общий выигрыш становится равным v({1, 2, 3}). Теперь мы можем предположить, что вклад {3} в текущую коалицию это разница между значением текущей коалиции (включая {3}) и предыдущей коалиции, которая не включала {3}:

После добавления {3} мы можем добавить {4} и {5}, и они также изменят общий выигрыш. Однако это не влияет на вклад {3}, поэтому предыдущее уравнение по-прежнему дает вклад {3} (рис. 2). Однако здесь есть проблема. Порядок добавления игроков также важен.

Предположим, что эти игроки являются сотрудниками отдела в компании. Сначала компания нанимает {1}. Затем они выясняют, что им не хватает набора навыков, поэтому нанимают {2}. После найма {2} общая прибыль компании увеличивается на 10 000 долл. США, и это вклад {2} при добавлении к {1}. После найма {3} вклад {3} составляет всего 2000 долларов. Кроме того, предположим, что у сотрудников {2} и {3} одинаковые наборы навыков. Теперь сотрудник {3} может заявить, что, если бы его наняли раньше, его вклад был бы равен {2}. Другими словами, вклад {3} при добавлении к {1} также может составить 10 000 долларов США. Таким образом, чтобы иметь справедливую оценку вклада каждого игрока, нам также необходимо учитывать порядок, в котором они добавляются для формирования большой коалиции.

На самом деле, чтобы получить справедливую оценку вклада игрока {i}, мы должны сформировать все перестановки F и вычислить вклад {i} в каждый из них, а затем взять среднее значение этих вкладов. Например, одна из возможных перестановок F={1, 2, 3, 4, 5}:

И вклад {3} в эту перестановку:

Другая перестановка может быть:

И вклад {3} в эту перестановку:

Важно отметить, что характеристическая функция v принимает в качестве аргумента коалицию, а не перестановку. Коалиция — это множество, поэтому порядок элементов в ней не важен, а перестановка — это упорядоченный набор элементов. В такой перестановке, как [3,1,2,4,5], 3 — это первый игрок, а 5 — последний игрок, добавленный в команду. Таким образом, для каждой перестановки порядок элементов может изменить их вклад в общий выигрыш, однако общий выигрыш или ценность перестановки зависит только от элементов, а не от их порядка. Так:

Итак, для каждой перестановки P нам нужно сначала вычислить ценность коалиции игроков, которые были добавлены до {i}. Назовем эту коалицию S. Затем нам нужно рассчитать ценность коалиции, которая образуется путем добавления {i} к S, и мы называем эту коалицию S U {i}. Теперь вклад игрока {i}, обозначенный ϕᵢ, равен:

Общее количество перестановок большой коалиции F равно |F|! (здесь |F| означает количество элементов множества F), поэтому делим сумму взносов, чтобы взять среднее значение вкладов для {i} (рис. 3).

Как видно на рисунке 3, некоторые перестановки имеют одинаковый вклад, поскольку их коалиции S и SU{i} совпадают. Таким образом, более простой способ расчета уравнения 1 заключается в том, что мы вычисляем только отдельные значения вкладов и умножаем их на количество повторений. Для этого нам нужно выяснить, сколько перестановок может быть сформировано из каждой коалиции. Пусть F-{i} будет набором всех игроков, кроме игрока {i}, а S — одна из коалиций F-{i} (S ⊆ F-{i}). Например, для F={1,2,3,4,5} и {i}={3} мы имеем

Количество элементов в S обозначается |S|, и мы можем иметь |S|! перестановки с этими элементами. Например, если S={1,2}, то|S|=2, и у нас 2! =2 перестановки: [1, 2] и [2, 1] (рис. 4). Мы также знаем, что стоимость каждой перестановки, образованной из S, равна v(S). Теперь мы добавляем игрока {i} в конце каждой перестановки, образованной из S. Ценность результирующих перестановок равна v(SU {i}), так как все они принадлежат коалиции SU {i}. Набор F имеет |F|-|S|-1 оставшийся элемент, за исключением элементов S U {i}, которые можно добавить в конец SU {i}, чтобы сформировать перестановку, содержащую все элементы F. Итак, есть (|F|-|S|-1)! способов добавить их в S U {i}.

Например, в предыдущем примере оставшимися элементами F являются {4} и {5}. Итак, у нас есть (|F|-|S|-1)! = (5–2–1)!=2 способа сформировать большую коалицию, используя оставшиеся элементы. В результате у нас есть S! (|F|-|S|-1)! способы формирования перестановки F, в которой {i} стоит после перестановки S, а остальные игроки идут после {i} (рис. 4).

Вклад {i} в общий выигрыш от каждой перестановки:

И общий вклад {i} в общий выигрыш всех этих перестановок равен

До сих пор мы рассмотрели перестановки одной возможной коалиции S в F и рассчитали общий вклад { i} к общему выигрышу. Теперь мы можем повторить ту же процедуру для других коалиций F-{i}, чтобы получить сумму вкладов { i} во всех перестановках F:

Наконец, мы знаем, что у нас есть |F|! перестановки для F. Таким образом, средний вклад {i} в общий выигрыш всех перестановок F можно получить, разделив предыдущий член на | F|!

Здесь ϕᵢ называется значением Шепли элемента {i}, которое представляет собой средний вклад {i} во всех перестановках F. Это математически справедливая доля игрока {i} в общем выигрыше всех игроков в F. Как мы показали ранее, каждая коалиция S может создать S! (|F|-|S|-1)! перестановки. Поскольку общее количество перестановок равно |F|!, мы можем написать:

Значение Шепли должно иметь следующие свойства:

1- Эффективность: сумма вкладов всех игроков должна давать общий выигрыш:

1- Симметрия: если i и j таковы, что v(S ∪ {i}) = v(S ∪ {j}) для каждой коалиции S, не содержащей i и j, то ϕᵢ=ϕⱼ . Это означает, что если два игрока добавляют одинаковый выигрыш ко всем возможным коалициям, то они должны иметь одинаковый вклад.

2- Пустота: если i таково, что v(S) = v(S ∪ {i}) для каждой коалиции S, не содержащей i, то ϕᵢ = 0. Это означает, что если игрок не добавляет никакого выигрыша ни к одной возможной коалиции, то его вклад равен нулю.

3- Аддитивность. Предположим, что u и v — две разные характеристические функции для игры. Пусть вклад игрока i в них равен ϕᵢ(u) и ϕᵢ(v) соответственно (здесь ϕᵢ(u) означает, что ϕᵢ является функцией u). Тогда у нас есть ϕᵢ(u + v) = ϕᵢ(u) + ϕᵢ(v). Поясним это свойство на примере. Предположим, что команда сотрудников работает над двумя разными проектами, и их общая отдача и вклад в каждый проект различны. Тогда, если мы объединим эти проекты, вклад сотрудника в объединенный проект будет суммой его вкладов в каждый проект.

Мы можем легко показать, что значения Шепли в уравнении 3 удовлетворяют этим свойствам.

Доказательство (необязательно):

Если для каждой коалиции S имеем v(S) = v(S ∪ {i}), то мы получим:

Итак, у них есть фиктивное свойство. Они также удовлетворяют свойству эффективности. Из уравнения 2 мы знаем, что:

где cᵖᵢ обозначает вклад {i} в общий выигрыш перестановки P. Теперь предположим, что элементами этой перестановки являются:

Итак, у нас есть|F|=M. Мы можем рассчитать значения для cᵖᵢ каждого элемента:

Теперь, если мы добавим значения cᵖᵢдля всех игроков, первый член в каждом cᵖᵢ отменяет второй член в cᵖᵢ₊₁и мы получаем:

Итак, для каждой перестановки сумма вкладов всех игроков дает общий выигрыш большой коалиции. Мы знаем, что у нас есть |F|! перестановки. Следовательно, используя уравнение 2, мы можем написать:

Ценности Шепли в машинном обучении

Но как мы можем связать значение Шепли игрока с особенностями модели машинного обучения? Предположим, что у нас есть набор данных с N строками и M функциями, как показано на рис. 5.

Здесь Xᵢ — i-й признак набора данных, xᵢ⁽ʲ⁾ — значение i-й объект в j-м примере, а y⁽ʲ⁾ является целью j-я строка. Значения признаков могут формировать вектор признаков, который представлен вектором-строкой с элементами M:

Здесь у нас есть X₁=x₁, X₂=x₂, … X_M=x_M (в линейной алгебре векторы обычно считаются векторами-столбцами, но в этой статье мы предполагаем, что они являются векторами-строками). Вектор признаков также может быть j-й строкой набора данных. В этом случае мы можем написать:

Или это может быть тестовая точка данных, которой нет в наборе данных (в этой статье выделенные полужирным шрифтом строчные буквы (например, x) относятся к векторам. Жирные прописные буквы (например, A) относятся к матрицам, а строчные буквы (например, x₁) относятся к скалярным значениям). Характеристики набора данных обозначаются заглавными буквами, например (X₁). Пара (x⁽ʲ⁾, y⁽ʲ⁾) называется обучающий пример этого набора данных. Теперь мы можем использовать модель для изучения этого набора данных:

Функция принимает вектор признаков x, что означает, что она применяется ко всем элементам x. Например, для линейной модели имеем:

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

Таким образом, f(x⁽ʲ⁾) — это предсказание модели для j-я строка набора данных и разница между f(x⁽ʲ⁾) и y⁽ʲ⁾ — ошибка предсказания модели для j-го обучающего примера.

Можно предположить, что модель машинного обучения — это коалиционная игра, а функции M — это M игроков в этой игре. Но какова должна быть характерная функция этой игры? Наше первое предположение может быть самим f(x). Но помните, что характеристическая функция должна удовлетворять уравнению 1, что означает, что когда у нас нет игроков, общий выигрыш равен нулю. Как мы можем оценить f(x), если у нас нет функций (игроков)? Когда функция не является частью игры, это означает, что ее текущее значение неизвестно, и мы хотим предсказать цель модели, не зная значения этой функции. Когда у нас нет фич в игре, это значит, что текущее значение ни одной из фич неизвестно. В этом случае мы можем использовать обучающий набор только для прогнозирования. Здесь мы можем взять среднее значение f(x⁽ʲ⁾) для выборки обучающих примеров. (или все из них) в качестве нашей наилучшей оценки. Итак, наш прогноз, когда у нас нет признаков:

Где NA означает недоступную функцию (поэтому ни один из параметров f здесь недоступен). Мы также выбрали k экземпляров данных (векторов признаков) из обучающего набора данных (k≤N). Теперь мы определим нашу характеристическую функцию для большой коалиции как:

Если у нас нет признаков, то, используя уравнение 7, мы получаем:

Эта характеристическая функция теперь удовлетворяет уравнению 1 и может дать значение большой коалиции F={X₁, X >₂,…, X_M}. Но нам также нужно значение любой коалиции F-{i}, чтобы иметь возможность использовать уравнение 3. Как мы можем применить функцию f в подмножество исходных аргументов? Мы можем сделать это двумя способами. Во-первых, мы можем переобучить ту же модель (с теми же гиперпараметрами) только на подмножестве исходных признаков. Например, если коалиция S содержит следующие функции:

Затем нам нужно предельное значение f для этих функций, которое называется fₛ(xₛ):

Здесь xₛ — это вектор, который содержит только значения функций, присутствующих в S (обратите внимание, что коалиция состоит из признаков, но функция принимает значения этих признаков). Мы можем либо переобучить тот же тип модели на функциях, присутствующих в коалиции S, чтобы получить fₛ (xₛ), или мы можем использовать исходную функцию f для вычисления fₛ. Если признак отсутствует в S, это означает, что мы не знаем его текущего значения и можем заменить его на NA. (Нет в наличии).

Например, если F={X₁, X₂, X₃, X₄, X₅} и коалиция S={X₁, X₂, X₅}, то нам неизвестно текущее значение признаков X₃иX₄. Так:

Здесь мы предполагаем, что модель, представленная f, может обрабатывать значения NA. Отсюда ценность этой коалиции:

где fₛ(xₛ)получается путем переобучения модели на функции, представленные в коалиции S или из уравнения 9. Например, для F={ X₁, X₂, X₃, X₄, X₅} и S={X₁, X₂, X₅}, стоимость S это:

Теперь мы можем просто использовать уравнение 3 и уравнение 10 для расчета значения Шепли функции Xᵢ:

Обратите внимание, что в этом уравнении мы должны были написать ϕₓᵢ, чтобы соответствовать уравнению 3. Однако мы используем ϕᵢ для простоты. Таким образом, в этом уравнении i обозначает i-й признак (Xᵢ). Упрощая предыдущее уравнение, получаем:

где fₛ(xₛ) — предельное значение f для функций, присутствующих в коалиции S, и f_S∪{ i}(x_S∪{i}) — предельное значение f для функций, представленных в объединении Sплюс функция {i}. Если мы используем свойство эффективности значений Шепли (уравнение 5), мы можем написать:

что означает, что сумма значений Shapely всех признаков дает разницу между предсказанием модели с текущим значением признаков и средним предсказанием модели для всех обучающих примеров.

Математическое описание объяснения модели

Прежде чем обсуждать значения SHAP, нам нужно иметь математическое описание модели объяснения, такой как SHAP. Пусть f будет исходной моделью, которую нужно объяснить, определяемой как:

Таким образом, модель использует вектор признаков x и f(x) предсказание модели для этого вектора признаков. Этот вектор признаков может быть одним из экземпляров обучающего набора данных (x⁽ʲ⁾) или тестовым вектором признаков, который не существуют в обучающем наборе данных. Теперь мы создаем набор упрощенных входных объектов, чтобы показать, присутствует ли объект в векторе объектов или нет:

Вектор x’ называется упрощенным вектором признаков. Каждый x'ᵢ представляет собой двоичную переменную, которая показывает, наблюдается ли соответствующий признак Xᵢ в векторе признаков (x'ᵢ = 1) или неизвестно (x'ᵢ = 0). Например, если ваш вектор признаков

Затем

Мы можем предположить, что существует функция сопоставления, которая сопоставляет x’ с x:

Итак, он берет упрощенный вектор признаков x’ и возвращает вектор признаков x:

Объяснитель представляет собой интерпретируемую модель g, которая принимает M бинарных переменных:

Где M — количество упрощенных входных объектов в уравнении 13. Вектор-строка z' представляет собой коалицию доступных значений x.Поэтому нулевые элементы x' всегда равны нулю в z', а 1 элемент x' может быть либо 1, либо 0 в z'. Мы называем z’ вектором коалиции. Например, если значения признаков:

Тогда вектор признаков:

И упрощенная функция:

Теперь значение z’, например

просто представьте коалицию S={X₁, X₃}, так как только эти два объекта имеют соответствующий 1 в z'. Мы также можем заключить, что x' представляет большую коалицию F={X ₁, X₂, X₃}, поэтому x' также можно рассматривать как коалиционный вектор. Как упоминалось ранее, мы хотим, чтобы прогноз модели объяснения был близок к прогнозу исходной модели для одного вектора признаков. Предположим, мы начинаем с коалиционного вектора z’, который очень близок к большой коалиции x’. Предсказание g для этой коалиции равно просто g(z’). Но как мы можем получить предсказание f, используя z’? Проблема в том, что f принимает вектор признаков, а не коалиционный вектор. Поэтому нам нужна функция сопоставления hx, чтобы найти соответствующее значение признаков для z». Здесь hₓ(z') возвращает соответствующее значение функций, присутствующих в z', а значение других функций будет NA. Например, если у нас есть

Затем

Прогноз f для функций, представленных в z’, будет следующим:

Мы также определяем fₓ как предельное значение f для функций, представленных в z'. Итак, мы можем написать:

Обратите внимание, что в уравнении 8 fₛ обозначает предельное значение f для функций, присутствующих в коалиции S. Однако здесь мы фокусируемся на z' вместо коалиции, а fₓ обозначает предельное значение f для функций, представленных в z'. В этом примере z' представляет коалицию S={x₁ , х₃}. Так что мы также можем написать:

Мы хотим, чтобы прогноз f, равный f(z), был очень близок к прогнозу g, то есть (g(z')) чтобы убедиться, что g имитирует одно и то же процесс, который f использует для прогнозирования. Подводя итог, мы хотим

чтобы иметь возможность утверждать, что g может объяснить f.

Мы можем классифицировать методы объяснения на основе g. Методы атрибуции аддитивных признаков имеют модель объяснения, которая представляет собой линейную функцию бинарных переменных:

где ci — некоторые константы. Как мы увидим позже, SHAP относится к этому классу методов. Итак, мы хотим выразить уравнение 11 через z’. Пусть x — вектор признаков, а x’ — его упрощенный вектор признаков. Мы можем показать, что значения Шепли могут быть выражены как:

где ϕᵢ(f, x) подчеркивает, что значение Шепли является функцией f и x. Здесь мы рассматриваем все возможные коалиционные векторы x’ (которые соответствуют всем коалициям x). Для каждого вектора коалиции z’ мы рассчитываем вклад признака i. |з’| количество ненулевых записей в z' (размер соответствующей коалиции) и |x'| — количество ненулевых записей в x’ (размер большой коалиции). z’\i означает, что соответствующая коалиция не включает функцию {i}. Таким образом, z'\iобозначает коалиционный вектор, полученный в результате установки i-го элемента z' на 0 (z'ᵢ=0). Например, если 3 представляет 3-й признак x₃, то мы можем написать:

Легко показать, что уравнения 11 и 18 эквивалентны.

Доказательство (необязательно): во-первых, обратите внимание, что |F| в уравнении 11 равно |x’| в уравнении 18, так как оба они относятся к общему количеству функций, M. Помните, что каждая коалиция S в уравнении 11 не включает функцию i, поскольку S ⊆ F-{i}. Легко видеть, что каждой коалиции S в уравнении 11 соответствует значение z'\ i в уравнении 18. Например, если у нас есть:

Затем мы получаем:

И соответствующее значение z'\iдляS равно [1 1 0 0 1].

Заменив эти значения в уравнении 11, мы получим соответствующий термин для этого значения S:

В уравнении 18 соответствующий термин для этого значения z’:

Теперь, основываясь на уравнении 15, мы заключаем, что уравнение 19 и уравнение 20 дают один и тот же результат. Как правило, для каждой коалиции S в уравнении 11 у нас есть z'\i которыйпредставляет его. В результате z' также представляет S∪ {i}, а мы можем заменить fₛ(xₛ) и f_S ∪{i}(x_S∪{i}) с fₓ(z') и fₓ(z'\i) соответственно. Кроме того, |S| и |F| равны |z’|-1 и |x’|. Следовательно, каждому члену в уравнении 11 (для коалиции S, которая не включает i) соответствует член в уравнении 18, в котором коалиция vector z' включает I, и оба термина дают одно и то же значение:

Но это относится только к элементам z в уравнении 18, которые включают {i}. В уравнении 18 у нас также могут быть z, которые не включают {i}. Для коалиционного вектора z', который не включает {i}, мы можем написать fₓ(z')=fₓ(z'\{i}), поэтому соответствующий член в уравнении 18 равен нулю

и это ничего не добавляет к уравнению 18. Следовательно, мы заключаем, что уравнение 11 и уравнение 18 эквивалентны и дают одинаковый результат. ∎

Важно отметить, что в уравнении 18 коалиционный вектор пустой коалиции (z’=[0 0 … 0]) не включен в сумму. Для этого коалиционного вектора имеем:

который не определен. Даже если бы удалось это вычислить, эта коалиция ничего бы не добавила к этой сумме, т.к.

Также обратите внимание, что в оригинальной статье, в которой представлен метод SHAP, уравнение 18 написано неправильно (см. уравнение 8 в [1]). Уравнение 11 — это классическое уравнение значения Шепли, и в этом уравнении мы фокусируемся только на доступных функциях. Уравнение 18 вводит понятие отсутствия. Здесь вектор большой коалиции x' может иметь некоторые пропущенные значения, для которых x'ᵢ=1. Уравнение 18 имеет некоторые интересные свойства, которые описаны ниже:

Свойство 1 (локальная точность)

Пусть g(x’) — модель объяснения, определенная как

где ϕ₀ =E[f(x)] и ϕᵢ — значения Шепли для f. Предположим, что у нас есть вектор признаков x, а его упрощенный вектор признаков равен x', поэтому мы имеем x = hₓ(x'). Затем на основе этого свойства прогноз g для x' совпадает с прогнозом исходной модели fдляx . Итак, мы можем написать:

Доказательство (необязательно). Предположим, что |F|=M (количество функции), и все функции доступны (x'ᵢ=1 для всех i), мы можем использовать уравнение 12 для записи:

где ϕ₀ =E[f(x)]. ∎

Как упоминалось ранее, уравнение 11 рассматривает только доступные функции. Поскольку уравнение 12 получено из этого уравнения, оно включает только значения Шепли доступных функций. Например, если последняя функция недоступна, то из уравнения 12 мы получаем

Однако этот результат по-прежнему согласуется с уравнением 22, поскольку для последнего признака мы имеем x’_M=0.

Свойство 2 (отсутствие)

Отсутствующий признак должен иметь нулевое значение Шепли.

Доказательство (необязательно): это не обязательное условие для классических значений Шепли в уравнении 11, поскольку оно не включает недостающие функции. Однако, если мы вычислим значения Шепли, используя уравнение 18, мы сможем показать, что оно удовлетворяет этому свойству. Рассмотрим все векторы коалиций z’, полученные из x’. Если x’ᵢ=0, то z’ᵢ =0. Итак, для этих коалиционных векторов получаем z'\i=z' , и мы можем написать:

Свойство 3 (согласованность)

Непротиворечивость означает, что изменение исходной модели для увеличения влияния функции на модель никогда не уменьшит ее значение Шепли. Математически, если у нас есть один вектор признаков x и две модели f и f' (обе f и f' являются функцией x), так что

для всех входов z’, то

Помните, что в уравнении 18 член

пропорционален вкладу функции Xᵢ в прогноз. Поэтому, если изменить модель с f на f' и получить более высокий вклад функции Xᵢ в прогноз x увеличивается (или остается неизменным), то значение Шепли Xᵢ никогда не уменьшается.

Доказательство (необязательно). Опять же, легко показать, что уравнение 18 удовлетворяет этому свойству. Поскольку у нас один и тот же вектор признаков x для обеих моделей, у нас будет один и тот же x’. Теперь для каждого коалиционного вектора z’ из x’ мы имеем

Итак, добавив эти условия для всех z’, мы имеем:

Теперь, когда мы знакомы со значениями Шепли и их свойствами, мы можем увидеть, как они могут объяснить модель машинного обучения. Предположим, у нас есть модель f и вектор признаков x. Мы определяем модель g как:

где ϕ₀ =E[f(x)], ϕᵢ – это значения Шепли для f, а x' – это упрощенный вектор признаков для x (то есть x = hₓ(x')). Модель g является линейной, поэтому ее можно интерпретировать. Кроме того, на основании свойства 1 g(x')=f(x ), поэтому g может идеально имитировать f для одного прогноза f(x ) и может использоваться в качестве объяснительной модели для f. Можно показать, что для аддитивного метода атрибуции признаков модель g, определенная выше, является единственно возможной объяснительной моделью, которая следует уравнению 17 и удовлетворяет свойствам 1, 2 и 3. Таким образом, модель Шепли значения могут предоставить коэффициенты линейной модели, которые можно использовать в качестве идеального объяснения для любой модели машинного обучения.

От значений Шепли к значениям SHAP

Значения Шепли имеют солидную теоретическую основу и интересные свойства, однако на практике их вычислить непросто. Для их расчета нам нужно вычислить fₓ(z') в уравнении 18 илиfₛ(xₛ) в уравнении 11. Помните, что

Таким образом, вычисление fₓ(z') или fₛ (xₛ) означает, что нам нужно вычислить f(x) с некоторыми отсутствующими функциями, которые не включены в z' или S. Проблема в том, что большинство моделей не могут обрабатывать пропущенные значения. Например, в линейной модели нам нужны все значения xᵢ для вычисления f(x). Итак, нам нужен способ обработки отсутствующих значений в f(x). Как упоминалось ранее, для каждой коалиции S отсутствующие элементы x — это значения функций, которые не присутствует в S. Чтобы вычислить fₛ(xₛ), мы предполагаем, что:

Здесь E[f(x)|xₛ] – это ожидаемое значение f(x), зависящее от функций, присутствующих в S. Точно так же мы можем написать:

Значения Шепли, рассчитанные с использованием условных ожиданий в уравнении 23 или уравнении 24, называются SHAP (Shapley Additive exPlanation)) значениями. Итак, чтобы получить значения SHAP из уравнения 11, мы можем написать:

И для расчета значений SHAP из уравнения 18 мы можем написать:

SHAP — это метод аддитивной атрибуции признаков, в котором у нас есть модель линейного объяснения. В этой статье мы обсуждаем два метода расчета условных ожиданий в уравнении 23 или уравнении 24. Первый обсуждается в этом разделе, а второй, который подходит для данных с древовидной структурой, будет обсуждаться позже.

Пусть S̅обозначает дополнение коалиции S. Таким образом, x_S̅обозначает часть исходных функций, которых нет в S. Теперь мы можем использовать закон полной вероятности, чтобы написать:

где f(x_S̅, xₛ) означает, что некоторые параметры f принадлежат xₛ, а остальные параметры принадлежат x_S̅ . Конечно, параметры xₛ или x_S̅ не обязательно располагаются последовательно. P(x_S̅|xₛ) — условная вероятность x_S̅ с учетом xₛ. Итак, чтобы вычислить значение fₛ(xₛ), нам нужна условная вероятность P(x_S̅|xₛ). К сожалению, в большинстве случаев мы не знаем этого распределения. Следовательно, в SHAP мы предполагаем, что функции независимы друг от друга, Итак:

Заменив это уравнение в уравнении 27, мы получим:

Поскольку у нас есть дискретные точки данных, мы можем аппроксимировать этот интеграл суммой. Мы выбираем k экземпляров данных (векторов признаков) из набора обучающих данных (k≤N) и называем каждый из них x⁽ʲ⁾. Функции в каждом экземпляре данных принадлежат либо S, либо S̅:

Затем для каждого экземпляра данных мы заменяем значения функций, присутствующих в S, соответствующими значениями в xₛ и сделайте прогноз для этого экземпляра данных:

Теперь предыдущий интеграл можно аппроксимировать средним значением этих предсказаний:

На рис. 6 показан пример вычисления этого интеграла. Точно так же мы можем написать:

где zₛ — это набор функций, которые имеют ненулевой индекс в z’. На рис. 6 показан пример этого метода. Здесь у нас есть модель f(x₁, x₂, x₃, x₄, x₅), где xₛ = {x₁, x₃, x₄}. Итак, x_S̅ ={x₂, x₅} и функции X₂ и X₅ означают Н/em> в x. Вектор признаков x имеет вид x=[x₁ NA x₃ x₄ Н/П]. Чтобы вычислить f(x), нам нужно значение отсутствующих признаков, поэтому мы заимствуем их значение из выборки обучающего набор данных. Для i-го экземпляра данных этой выборки мы заменяем отсутствующие значения вектора признаков x (X₂, X₅) с соответствующим значением в этом экземпляре (x₂^(i), x ₅^(i)) и вычислить f(x_S̅^(i), xₛ) = f(x₁, x₂^( i), x₃, x₄, x₅^(я)). Итак, для каждого экземпляра данных у нас теперь есть прогноз. Наконец, мы берем среднее значение этих прогнозов и сообщаем его как нашу оценку f(x). Теперь мы можем использовать приближения, данные в уравнении 29 и уравнении 30, для расчета значений SHAP в уравнении 25 или уравнении 26.

Обратите внимание, что уравнение 30 также согласуется с уравнением 7. Когда все элементы z' равны нулю, S становится пустым набором, поэтому мы берем только среднее значение предсказания модели для k экземпляров данных обучающего набора.

Линейная форма

Предположим, что наша прогностическая модель f является моделью линейной регрессии:

где x₀=1, а признаки Xᵢ, i = 1, …, M независимы. Теперь мы можем показать, что значения SHAP задаются следующим уравнением:

Где k — количество экземпляров данных в выборке обучающего набора данных, которые мы используем для расчета значений SHAP. Вы можете обратиться к приложению для доказательства. Мы также можем управлять этим уравнением интуитивно. В линейной модели вклад функции Xᵢ в f(x) равен просто cᵢxᵢ . Итак, мы могли бы написать:

Однако уравнение 22 добавляет ограничение к значениям Шепли:

Итак, мы вычитаем

из cᵢxᵢ в уравнении 31, чтобы удовлетворить уравнению 22. Если мы добавим значения Шепли из уравнения 31, мы увидим, что результат согласуется с уравнением 22:

Вычисление значений SHAP в Python

Линейная форма

В качестве нашего первого примера мы используем Python для расчета линейных значений SHAP (уравнение 31) для фиктивного набора данных. Сначала мы определяем набор данных. У нас есть только две функции, заполненные некоторыми случайными числами, и цель определяется как линейная комбинация этих функций. Характеристики независимы.

# Listing 1 # Defining the dataset X = pd.DataFrame({'a': [2, 4, 8, 0, 3, 6, 9], 'b': [1, 5, 0, 7, 1, -2, 5]}) y = 5*X['a'] + 2*X['b'] + 3

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

# Listing 2 # Defining a linear model linear_model = LinearRegression() linear_model.fit(X, y) print("Model coefficients:") for i in range(X.shape[1]): print(X.columns[i], "=", linear_model.coef_[i].round(4))

Output:

Model coefficients: a = 5.0 b = 2.0

Наконец, мы используем уравнение 31 для расчета значений SHAP для первого примера этого набора данных:

# Listing 3 shap_values = ((X[:1] — X.mean()) * linear_model.coef_) shap_values_table = shap_values.T shap_values_table.columns = ['SHAP_value'] shap_values_table

Итак, у нас есть:

где 1 и 2 относятся к функциям a и b соответственно.

Линейный SHAP с использованием библиотеки SHAP

Мы также можем использовать библиотеку SHAP для вычисления значений SHAP линейной модели, определенной в листинге 2:

import shap explainer = shap.LinearExplainer(linear_model, X) shap_values = explainer.shap_values(X[:1]) shap_values

Output:

array([[-12.85714286, -2.85714286]])

Класс LinearExplainer() в библиотеке SHAP принимает обученную модель и набор обучающих данных. Метод shap_values() в этом классе принимает массив строк для объяснения и возвращает их значения SHAP. Обратите внимание, что здесь мы получаем тот же результат, что и в листинге 3.

Точные значения SHAP

В следующем примере мы вычисляем значения SHAP для линейной модели с зависимостью от признаков. Таким образом, мы не можем использовать уравнение 31. Вместо этого мы используем уравнение 11 и вычисляем значения SHAP, используя все возможные коалиции. Здесь мы используем набор данных Boston в библиотеке scikit-learn:

# Listing 4 d = load_boston() df = pd.DataFrame(d['data'], columns=d['feature_names']) y = pd.Series(d['target']) X = df[['LSTAT', 'AGE', 'RAD', 'NOX']] X100 = X[100:200] linear_model2 = LinearRegression() linear_model2.fit(X, y)

Набор данных Бостона содержит 13 признаков, но мы выбираем только 4 из них (LSTAT, AGE, RAD, NOX). Мы также выбираем 100 строк этого набора данных для оценки fₛ(xₛ) в уравнении 29 (т.е. k=100). Мы храним эти строки в X100. Затем мы используем этот набор данных для обучения линейной модели. Теперь нам нужно определить некоторые функции для вычисления значений SAHP в Python:

Функция coalition_worth() используется для расчета стоимости коалиции. Требуется модель, образец обучающего набора данных (X_train), экземпляр данных (x) и набор коалиций (coalition). Здесь коалиция представляет S в уравнении 11. Эта функция заменяет столбцы X_train значениями, заданными в наборе коалиции, а затем использует модель для прогнозирования цели всех эти ряды. Наконец, он берет среднее значение всех этих прогнозов и возвращает его как оценку fₛ(xₛ ).

Функция coalitions() возвращает набор всех коалиций экземпляра данных, за исключением признака col. Таким образом, он вычисляет все коалиции F-{i} в уравнении 11, где col представляет функцию i.

Функция coalition_contribution() вычисляет вклад каждой коалиции в уравнении 11 (каждый член суммирования в уравнении 11). Здесь мы использовали тот факт, что:

Таким образом, функция comb() в scipy использовалась для вычисления биномиального коэффициента:

Наконец, функция calculate_exact_shap_values() берет векторы признаков, которые необходимо объяснить (X_explain), и вычисляет значения SHAP для каждого вектора признаков в нем. Он добавляет вклад каждой коалиции для расчета значения SHAP каждой функции в векторе функций. Теперь мы можем использовать эту функцию для вычисления значений SHAP первой строки набора данных Boston, используя образец строк набора данных (X100):

# Listing 6 calculate_exact_shap_values(linear_model2, X100, X.iloc[0])

Output:

(22.998930866827823, [[7.809214247585507, -0.7308440229196315, 0.1290501127229501, 0.23758951510828266]])

Вычисление значений SHAP с помощью библиотеки SHAP

Класс Explainer() в библиотеке shap принимает функцию прогнозирования модели (не только модель) и набор обучающих данных, а метод shap_values() возвращает значения SHAP. Если мы не передаем имя конкретного алгоритма, он пытается найти лучший алгоритм для вычисления значений SHAP на основе данной модели и набора обучающих данных. Здесь мы используем его для той же модели, что и в листинге 4.

explainer = shap.Explainer(linear_model2, X100) shap_values = explainer.shap_values(X.iloc[0:1]) shap_values ### Output: array([[ 7.80921425, -0.73084402, 0.12905011, 0.23758952]]) explainer.expected_value ### Output: 22.998930866827834

Здесь массив shap_values дает значения от ϕ₁ до ϕ_M. Значение ϕ₀ хранится в поле ожидаемое_значение в Объяснителе. Здесь мы получаем почти те же значения SHAP, что и calculate_shap_values() в листинге 6. Важно отметить, что класс объяснителя автоматически выбирает 100 строк обучающих данных (если количество строк больше 100) и использует их для вычисления значений SHAP. Поэтому, если мы используем набор обучающих данных, содержащий более 100 строк, вывод Explainer больше не будет соответствовать выводу calculate_exact_shap_values():

explainer = shap.Explainer(linear_model2, X[:150]) shap_values = explainer.shap_values(X.iloc[0:1]) shap_values ### Output: array([[ 8.88370884e+00, -2.97655621e-01, 1.17561972e-01, -1.48202335e-03]]) calculate_exact_shap_values(linear_model2, X[:150], X.iloc[0]) ### Output: (22.521908424669917, [[7.993180897252836, -0.11946396867250808, 0.11973195423751992, -0.07141658816282939]])

Ядро SHAP

Чтобы рассчитать значения SHAP модели с использованием уравнения 11 или уравнения 18, нам нужно рассчитать все возможные коалиции. Как упоминалось ранее, для функций M общее количество возможных коалиций равно 2. Конечно, в уравнении 25 мы вычисляем все коалиции F-{i}. Таким образом, фактическое количество коалиций, которое нам нужно для вычисления каждого значения SHAP, равно 2ᴹ⁻¹, а для признаков M временная сложность равна

Для каждой коалиции нам нужно оценить fₛ(xₛ) и f_ S∪{i}(x_S∪{i})используя уравнение 29, и в этом уравнении мы берем среднее из k выборок. Таким образом, временная сложность этого алгоритма составляет O(kM2ᴹ).

Основываясь на этом результате, количество возможных коалиций увеличивается экспоненциально, когда увеличивается M, и нахождение значений SHAP с использованием этих уравнений становится трудновыполнимым с точки зрения вычислений, когда у нас есть более нескольких признаков. Kernel SHAP — это приближенный метод, который можно использовать для решения этой проблемы. Этот метод был впервые разработан Лундбергом и Ли [1].

ИЗВЕСТЬ

Чтобы понять SHAP ядра, мы должны сначала ознакомиться с другим методом объяснения, не зависящим от модели, который называется LIME (Local Interpretable Model-agnostic Explanations). LIME был разработан до SHAP, и его целью было определить интерпретируемую модель для классификатора, которая локально соответствует ему. Предположим, у вас есть модель f(x) и вы хотите найти наилучшую интерпретируемую модель g(z') для этого (помните, что g является функцией коалиционного вектора z'). Пусть x — вектор признаков, который нужно объяснить, а x’ — его коалиционный вектор.

Теперь нам нужно найти несколько случайных коалиционных векторов вблизи x’. Например, мы можем выбрать некоторые ненулевые компоненты x' и изменить их с 1 на 0 с вероятностью 0,5, чтобы получить коалиционный вектор z'. В результате мы получаем несколько векторов коалиции около x’. Обычно мы называем каждый из этих коалиционных векторов z', а набор всех этих векторов называем Z .Можно предположить, что x' и z' — некоторые точки в M-мерном пространстве (рис. 7). Мы можем использовать функцию сопоставления hₓ, чтобы найти соответствующий вектор каждого z' в пространстве признаков ( Рисунок 7):

Нам нужна количественная мера расстояния между x’ и каждым z’. Итак, мы определили функцию πₓ(z') как меру расстояния между x' и z'. Эта функция сопоставляет коалиционный вектор z’ с неотрицательным действительным числом ({0,1}ᴹ → R≥ 0). πₓ(z') должно увеличиваться как z' приближается к x'.

Теперь предположим, что у нас есть набор интерпретируемых объяснительных моделей G, и мы хотим найти наиболее точную объяснительную модель g для f. (x) среди них (g∈ G). Из уравнения 16 мы хотим иметь:

В результате мы можем определить функцию потерь L(f, g,πₓ) которое пропорционально расстоянию между f(z) и g(z') для всех векторов z' в Z. Мы хотим, чтобы g(z') был очень близок к f(z), когда z' очень близко к x'. Однако некоторые точки в Z могут быть не очень близки к x', поэтому нам нужно добавить срок наказания для них. Поскольку πₓявляетсямерой расстояния между x' и z', мы можем добавить его в качестве параметра функции потерь. Например, мы можем определить функцию потерь как:

Добавляя πₓк функции потерь,мы добавляем более высокий штраф за баллы в Z, которые далеки от x', и более близкие точки становятся более важными для минимизации. Следовательно, функция потерь определяет, насколько плохо функция объяснения g аппроксимирует f в точках z', которые очень близко к x'. Теперь нам нужно найти функцию gв G (множество всех интерпретируемых функций, которые мы хотим попробовать), которая минимизирует эту функцию потерь.

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

Это эквивалентно решению этой задачи минимизации:

Теперь мы можем использовать следующую теорему для определения метода ядра SHAP:

Теорема 1. Предположим, что у нас есть вектор признаков x с признаками M и модель f, которая принимает x в качестве входных данных. Пусть g — линейная модель, определенная как:

где z'ᵢ — это i-й элемент z', который коалиционный вектор x; ϕ₀ =E[f(x)] (средний прогноз модель для экземпляров выборки обучающего набора данных) и ϕᵢ (для i›0) являются значениями Шепли для fи x определяется уравнением 18. Когда M стремится к бесконечности, решение уравнения 32 (функция g) приближается к функции, указанной в уравнении 33, если L, Ω, πₓ определены как:

где |z’| количество ненулевых записей в z’.

Доказательство этой теоремы дано в приложении. Интересно отметить, что в исходной статье, в которой был представлен SHAP [2], эта теорема не была правильно доказана (подробнее см. в приложении). Давайте посмотрим, как мы можем использовать этот метод на практике. Мы предполагаем, что у нас есть вектор признаков x с признаками M. Мы рассчитываем упрощенный вектор признаков x’. Здесь мы предполагаем, что в x нет NA для простоты (в теореме 1 x может иметь значения NA), поэтому все элементы x' равны 1. Затем мы вычисляем все возможные коалиционные векторы x' (их также называют возмущением x'). Каждый коалиционный вектор x' называется z'ᵢ и является вектором с M элементов, в которых каждый элемент может быть либо 0, либо 1. У нас есть 2ᴹ вектора коалиции, и мы помещаем все эти векторы коалиции в матрицу 2ᴹ× M X:

Эта матрица называется матрицей коалиции. Для каждого коалиционного вектора z'ᵢ мы можем вычислить предсказание модели fₓ(z' ᵢ). Мы определяем вектор-столбец y как:

гдеϕ₀ =E[f(x)] (среднее значение прогнозов экземпляров данных в выборке обучающего набора данных).

Наконец, мы определяем диагональную матрицу 2ᴹ×2ᴹ W следующим образом:

где

Например, пусть вектор признаков будет:

Тогда у нас есть:

И коалиционная матрица будет иметь 2³=8 строк:

И у нас есть:

Из уравнений Уравнение 32 и Уравнение 34 мы знаем, что нам нужно решить эту задачу минимизации, чтобы получить оценку значений Шепли:

Мы ограничиваем поиск оптимальной функции g линейными функциями следующего вида:

Вектор-столбец c определяется как:

Теперь можно показать, что (подробности приведены в приложении):

Таким образом, задача минимизации эквивалентна

g является только функцией cᵢ, поэтому вместо поиска функции g, которая минимизирует целевую функцию, мы находим значение вектора c, который сводит его к минимуму. Функция πₓ(z'ᵢ) также называется Вес ядра Шепли. На основании (уравнения 40) каждое значение πₓ(z'ᵢ) похоже на вес для (g(z'ᵢ)-fₓ(z'ᵢ))², и поскольку этот термин является только функцией z'ᵢ, он также является весом для вектор коалиции z'ᵢ, показывающий, насколько важна коалиция.

Как показано в приложении, решение этой задачи минимизации таково:

Из теоремы 1 мы знаем, что это решение является аппроксимацией значений Шепли:

Поскольку ϕ₀ =E[f(x)], мы имеем все ценности Шепли. Термин R в уравнении 41 не зависит от конкретного экземпляра данных, который необходимо объяснить, поэтому, если мы хотим объяснить несколько экземпляров данных, нам нужно только вычислить R один раз. Затем для каждого экземпляра данных вычисляется новое значение y и умножается на R, чтобы получить значения SHAP. .

Важно отметить, что порядок векторов коалиции в X не важен. Например, в уравнении 39 коалиционный вектор [0 0 0] — это первая строка X, однако он может быть и последней строкой, и уравнение 41 остается в силе ( если вы посмотрите на доказательство теоремы 1 в приложении, мы не делаем никаких предположений о порядке коалиционных векторов z'ᵢ в виде строк матрицы X. Ему нужны только все 2 вектора коалицииᴹ.

Ядро SHAP в Python

Теорема 1 верна, даже если вектор признаков x имеет некоторые недоступные функции, но на практике мы реализуем SHAP, предполагая, что все функции x доступны. Таким образом, все элементы x' равны единице, а |x'|=M. Теперь давайте посмотрим, как мы можем реализовать SHAP ядра в Python. Для этого нам сначала понадобится функция Python для вычисления πₓ(z’ᵢ).

Функция pi_x() принимает коалиционный вектор z'ᵢ (в виде списка) и возвращает значения πₓ (z'ᵢ) на основе уравнения 38. Функция generate_colaition_vectors() принимает количество объектов (num_features) и генерирует для них все возможные коалиционные векторы.

Например:

generate_coalition_vectors(num_features)

Output

[[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0], [1.0, 1.0, 0.0], [1.0, 0.0, 1.0], [0.0, 1.0, 1.0], [1.0, 1.0, 1.0]]

Теперь нам нужна функция для генерации диагональных элементов матрицы W в уравнении 37. Здесь у нас есть проблема. Глядя на уравнение 38, мы видим, что если |z'ᵢ |=0 (когда все элементы z'ᵢ равны нулю) и |z'ᵢ|=M(когда все элементы z'ᵢ равно единице), затем πₓ(z'ᵢ)= ∞. Помните, что мы хотим минимизировать следующую целевую функцию (уравнение 40):

Предположим, что первый z’₁ — это коалиция, в которой все элементы равны нулю:

И пусть последней коалицией будет та коалиция, в которой все элементы едины:

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

Мы также знаем, что когда все функции доступны:

Итак, для последней коалиции имеем:

Теперь в уравнении 42 πₓ(z’₁) — это вес этого термина:

Поскольку πₓ(z'₁) бесконечно, нам нужно, чтобы этот член был равен нулю, что означает, что мы должны иметь:

которое является свойством линейной модели, основанной на значениях Шепли (уравнение 22). Бесконечное значение πₓ(z'_2ᴹ) означает, что мы должен иметь:

Мы также знаем, что по мере того, как M стремится к бесконечности, значения cⱼ, минимизирующие целевую функцию, становятся ближе к значениям Шепли f и х. Таким образом, приведенное выше уравнение просто показывает свойство линейной модели, основанное на значениях Шепли (уравнение 22). Теперь построим график πₓ(z'ᵢ) для особого случая, когда M=13. Для этой цели мы можем использовать листинг 9:

# Listing 9 pi_values = [1e7] for i in range(1, 14): try: pi_values.append(pi_x(13, i)) except: pi_values.append(1e7) plt.plot(pi_values, marker=’o’) plt.xlabel(“$|\mathregular{z}’_i|$”, fontsize=14, weight=”bold”, style=”italic”,) plt.ylabel(“$\pi_\mathregular{x}(\mathregular{z}’_i)$”, fontsize=14, weight=”bold”, style=”italic”,) plt.ylim([0, 0.1]) plt.show()

Результат показан на рисунке 8. Мы использовали большую константу (1e7) вместо бесконечности для πₓ(z'₁) и πₓ(z'_2ᴹ) чтобы иметь возможность их зарисовать.

Сюжет симметричен, а |z’ᵢ| приближается к 0 или M, πₓ(z'ᵢ) увеличивается . Каждое значение πₓ(z'ᵢ) похоже на вес коалиционного вектора z'ᵢ. Как уже упоминалось, прежде чем использовать уравнение 30 для оценки fₓ(z’). Для z’₁ мы знаем, что

А для z’_2ᴹ мы знаем, что

Эти два коалиционных вектора являются наиболее важными, поскольку мы можем точно вычислить значение fₓ(z' ᵢ) для них. Следовательно, они имеют бесконечные веса. Однако для других коалиций (z'ᵢ) мы можем оценить только fₓ(z'ᵢ). Когда коалиция z'ᵢприближается к z'₁ или z'_2ᴹ, πₓпридает ему гораздо больший вес.

Функция generate_pi_values() генерирует диагональные элементы W. Для каждого коалиционного вектора z'ᵢ эта функция вычисляет πₓ(z'ᵢ), используя pi_x(). Мы не можем использовать pi_x() для z'₁ и z'_2M, так как это заканчивается исключением деления на ноль. Вместо этого мы заменяем πₓ(z'ᵢ) большой константой 1e7 для коалиций, в которых | z'ᵢ|=0 и |z'ᵢ|=M.

Затем нам нужна функция Python для вычисления fₓ(z'ᵢ) для каждого вектора коалиции. Для этой цели мы можем использовать уравнение 30. Предположим, что наш вектор признаков, который необходимо объяснить, равен x. Мы собираем все функции в x, которые присутствуют в z'ᵢ в набор под названием xₛ. Затем для каждого экземпляра данных в образце обучающего набора данных мы заменяем значения функций, которые присутствуют в S, соответствующими значениями в xₛ и сделайте прогноз для этого экземпляра данных:

Мы берем среднее значение этих прогнозов для всех экземпляров обучающего набора в качестве приближения для fₓ(z'ᵢ):

Функция Python f_x_z_prime() использует этот метод для вычисления fₓ(z'ᵢ ) для каждого коалиционного вектора:

Функция kernel_shap() принимает предиктор модели, набор обучающих данных, его весовой массив и векторы признаков, которые должны быть объяснены ядром SHAP (X_explain). Он генерирует векторы коалиций E[f(x)] и диагональные элементы матрицы W. Затем он вызывает функцию calculate_shap_values() для вычисления значений SHAP каждого вектора признаков в X_explain. Для каждого вектора признаков, который необходимо объяснить, эта функция вычисляет значения SHAP с помощью уравнения 41. Она формирует матрицы X и W и вектор-столбец y. Затем использует уравнение 41 для расчета от ϕ₁ до ϕ_M. Он возвращает кортеж, в котором первым элементом является ϕ₀, а вторым элементом является массив значений SHAP (от ϕ₁ до ϕ_M ) каждого вектора признаков в X_explain.

Теперь давайте попробуем kernel_shap() на наборе данных. Мы снова используем набор данных Бостона и включаем все функции (13 функций). Затем мы обучаем на этом регрессор случайного леса.

# Listing 13 d = load_boston() df = pd.DataFrame(d['data'], columns=d['feature_names']) X = df[['AGE', 'RAD', 'TAX', 'DIS', 'RM', 'LSTAT', 'B', 'INDUS', 'CHAS']] y = pd.Series(d['target']) rf_model = RandomForestRegressor(max_depth=6, random_state=0, n_estimators=10).fit(X, y)

Теперь мы можем попробовать kernel_shap() на этом наборе данных. Мы используем первые 420 строк X набора данных в качестве набора данных обучения, а затем пытаемся объяснить строку номер 470. В этом примере все элементы набора данных обучения (X_train) имеют одинаковый вес.

# Listing 14 X_train = X.iloc[:100].copy() data_to_explain = X.iloc[470:471].copy() weights = np.ones(len(X_train)) / len(X_train) shap_values = kernel_shap(rf_model.predict, X_train.values, weights, data_to_explain) shap_values

Output:

(22.74244968353333, array([[ 4.05579739e-02, -4.91062082e-02, -4.69741706e-01, 9.28299842e-02, -8.88366342e-01, -2.86693055e+00, 2.19117329e-01, -3.57934578e-02, 7.10305024e-09]]))

На выходе кортеж. Первый элемент этого кортежа дает ϕ₀ (22,742), а второй элемент представляет собой массив, который дает значения ϕ₁ для ϕ ₁₃ соответственно.

Важно отметить, что количество примеров в наборе обучающих данных сильно влияет на время выполнения ядра SHAP. Чтобы вычислить y в уравнении 36, нам нужно вычислить fₓ(z'ᵢ) для i=2…2ᴹ,и для вычисления каждого значения fₓ(z'ᵢ), нам нужно взять среднее значение прогнозов для всех экземпляров в выборке обучающего набора (уравнение 44). В результате большая обучающая выборка может замедлить вычисления, и для этой цели мы используем только небольшую выборку обучающей выборки. Мы можем либо случайным образом выбрать k экземпляров данных из набора обучающих данных, либо использовать алгоритм кластеризации для выборки из набора обучающих данных. Например, мы можем использовать k-средних, чтобы найти k кластеров в обучающем наборе данных. Вес каждого кластера пропорционален количеству точек данных в нем. Для каждого кластера мы рассчитываем его среднее значение и вес и суммируем набор обучающих данных с набором взвешенных средних.

Альтернативная форма уравнения ядра SHAP

Мы также можем использовать трюк, чтобы удалить z'1 и z'_2ᴹот целевой функции. Помните, что термины, соответствующие z'₁ и z'_2ᴹ в целевая функция связана со свойствами значений Шепли, описанных в уравнении 22:

Мы можем удалить термины, соответствующие z'₁ и z'_2ᴹ. в целевой функции и добавьте приведенные выше уравнения в качестве отдельного ограничения. Итак, целевая функция в уравнении 40 принимает вид:

Рассмотрим коалиционную матрицу X, определенную в уравнении 35, и пусть z'₁ и z '_2ᴹбыть коалициями "все нули" и "все единицы" соответственно. Пусть Xₜ будет матрицей (2ᴹ-2)×M, которая создается удалением z'₁ и z'_2ᴹ из коалиционной матрицы Х:

И пусть Xᵣ будет (2ᴹ-2)×(M -1) матрица определяется как:

Здесь *,i означает i-й столбец Xₜ. Таким образом, Xᵣ формируется путем вычитания последнего столбца Xₜ из первого M-1 столбцов. Мы также определяем вектор-столбец cᵣ как:

и определите вектор-столбец yᵣ с 2ᴹ-2 элементами как:

где x — вектор признаков, который необходимо объяснить. Наконец, мы определяем (2ᴹ-2)×(2ᴹ-2) диагональную матрицу Wᵣ как:

Обратите внимание, что Wᵣ теперь не имеет бесконечных диагональных элементов. Можно показать (подробности приведены в приложении), что целевая функция в уравнении 45 может быть записана как:

Итак, нам нужно решить эту задачу минимизации:

и значение cᵣ, которое минимизирует эту целевую функцию:

Итак, на основании теоремы 1 имеем:

Мы знаем это

И как только мы получим от ϕ₁ до ϕ_M-1, мы можем вычислить ϕ_M, используя уравнение 22:

Итак, используя этот метод, мы можем вычислить все значения SHAP, не имея дело с бесконечными элементами W. Как и в уравнении 41, термин Rᵣ не зависит от конкретного экземпляра данных, который нужно объяснить, поэтому, если мы хотим объяснить несколько экземпляров данных, нам нужно только вычислить это один раз. Чтобы реализовать SHAP ядра с помощью уравнения 47, нам нужно изменить некоторые функции Python. Функция generate_coalition_vectors2() в листинге 15 аналогична функции, определенной в листинге 8, но она не генерирует коалиции «все нули» и «все единицы». Таким образом, он генерирует только строки матрицы Xₜ.

Функция generate_pi_values2() аналогична функции generate_pi_values(), определенной в листинге 10, но в ней нет обработки исключений, поскольку у нас нет бесконечных значений πₓ( г'ᵢ). Эта функция возвращает список диагональных элементов матрицы диагональной матрицы Wᵣ.

Функция kernel_shap2() вычисляет значения SHAP, вызывая функцию calculate_shap_values2(). Он вычисляет ϕ₁ до ϕ_M-1, используя уравнение 47, а затем вычисляет с их помощью ϕ_M.

Мы можем попробовать kernel_shap2() на нашей предыдущей модели и наборе данных, определенных в листинге 13.

# Listing 18 shap_values = kernel_shap2(rf_model.predict, X_train, weights, data_to_explain) shap_values

Output:

(22.74244968353333, array([[ 4.05579906e-02, -4.91062100e-02, -4.69741717e-01, 9.28299916e-02, -8.88366357e-01, -2.86693056e+00, 2.19117328e-01, -3.57934593e-02, 4.44089210e-16]]))

Как видите, возвращенные значения SHAP почти идентичны значениям kernel_shap() в листинге 14.

Ядро SHAP с выборкой

Когда модель имеет так много функций, вычисление правой части уравнения 41 или уравнения 47 по-прежнему требует значительных вычислительных ресурсов. В этом случае мы можем использовать выборку векторов коалиции z'ᵢ для формирования матрицы коалиции X. Коалиционная матрица X состоит из 2ᴹстрок, и каждая строка является коалиционным вектором z'ᵢ. Вес ядра Шепли, πₓ(z'ᵢ), дает вес коалиционный вектор z'ᵢ. Однакобольшинство коалиционных векторов имеют очень маленькое ядро Шепли, что означает, что они не так сильно влияют на значения Шепли. Следовательно, мы можем игнорировать эти коалиционные векторы и аппроксимировать значения Shapely без них.

Если мы предположим, что веса ядра Шепли дают распределение вероятностей векторов коалиции, мы можем выбрать (с заменой) подмножество векторов коалиции D из исходных 2ᴹ-2коалиционные векторы, которые не включают z'₁ и z'_2ᴹ. Поместим эти векторы в коалиционную матрицу D×M X_p:

где z'₁...z'ᴅ — выборочные коалиционные векторы . Теперь мы можем использовать уравнение 47 для расчета значений Шепли, используя эту новую коалиционную матрицу. Мы формируем матрицу D×(M-1) Xᴅ как:

вектор-столбец cᴅ определяется как:

и мы определяем вектор-столбец yᴅ с элементами D как:

Наконец, мы определяем диагональную матрицу D×D Wᴅ как:

Причина того, что все веса ядра Шепли равны 1, заключается в том, что мы уже выбрали вектора коалиции, используя их веса ядра Шепли. Таким образом, выбранные коалиции теперь имеют одинаковый вес в новой матрице коалиций. Теперь мы можем использовать уравнение 47 для вычисления значений Шепли с использованием выбранных коалиционных векторов:

Теперь мы можем использовать модифицированную версию уравнения 47 для вычисления значений Шепли с использованием выбранных коалиционных векторов. Чтобы реализовать этот метод в Python, нам нужно всего лишь изменить функции, определенные в листинге 17:

В kernel_shap3() мы используем функцию choice() в Numpy для выборки коалиционных векторов, используя их нормализованные веса ядра Shaply. Здесь мы отбираем половину исходных коалиционных векторов (но это может быть и другое число). Выборочные коалиционные векторы будут переданы в calculate_shap_values3() для расчета значений SHAP. На этот раз нам не нужны значения πₓ(z'ᵢ), поскольку все они равны 1.

Ядро SHAP в библиотеке SHAP

Класс kernelExplainer() можно использовать для вычисления значений SHAP с использованием метода SHAP ядра. Мы используем тот же набор данных и модель, что и в листинге 13. Этот класс берет модель и набор обучающих данных, а его метод shap_values() возвращает ϕ₁ в ϕ_M. Значение ϕ₀ хранится в поле expected_value.

explainer = shap.KernelExplainer(rf_model.predict, X_train) k_shap_values = explainer.shap_values(data_to_explain) phi0 = explainer.expected_value k_shap_values ### Output:array([[ 0.04055799, -0.04910621, -0.46974172, 0.09282999, -0.88836636, -2.86693056, 0.21911733, -0.03579346, 0. ]]) phi0 ### Output: 22.742449683533327

Как вы видите, результат почти такой же, как у kernel_shap() в листинге 14 или kernel_shap2() в листинге 18. В отличие от класса Explainer, KernelExplainer не выбирает автоматически набор обучающих данных и будет использовать весь переданный ему набор обучающих данных. Мы можем либо вручную выбрать набор данных, как в примере выше, либо использовать для этого методы shap.sample() и shap.kmeans(). Например, мы можем случайным образом выбрать 100 строк обучающего набора данных, используя shap.sample():

explainer = shap.KernelExplainer(rf_model.predict, shap.sample(X, 100))

Или мы можем обобщить набор обучающих данных, используя shap.kmeans():

explainer = shap.KernelExplainer(rf_model.predict, shap.kmeans(X, 100))

Здесь алгоритм k-средних используется для поиска 100 кластеров в наборе обучающих данных, а вес каждого кластера пропорционален количеству точек данных в нем. Результатом является среднее значение 100 кластеров с соответствующими весами. Теперь этот набор взвешенных данных используется в качестве образца исходного набора данных для расчета значений SHAP. В следующем коде показано, как можно реализовать выборку k-средних в Python. Сначала мы используем класс KMeans в библиотеке scikit-learn, чтобы разделить X на 100 кластеров. Затем создается массив weights на основе количества точек данных в каждом кластере. Наконец, центр кластеров и массив weights передаются в kernel_shap2() для генерации значений SHAP.

kmeans = KMeans(n_clusters=100, random_state=10).fit(X) cluster_size = np.bincount(kmeans.labels_) weights = cluster_size / np.sum(cluster_size) X_train_kmeans = kmeans.cluster_centers_ shap_values = kernel_shap2(rf_model.predict, X_train_kmeans, weights, data_to_explain)

Значения SHAP для древовидных моделей

Помните, что мы использовали это уравнение:

для расчета значений SHAP (см. уравнение 23). Чтобы вычислить условное математическое ожидание в приведенном выше уравнении, мы использовали приближение, данное в уравнении 29:

Как мы видим в этом разделе, для древовидных моделей (деревьев и ансамблей деревьев) существует лучший способ вычисления E[f(x)|xₛ].

Как мы упоминали ранее, SHAP не зависит от модели, поэтому объясняемая модель представляет собой черный ящик, и мы не знаем ее типа. Но в таких методах, как линейный SHAP или древовидный SHAP, мы должны знать тип модели, поэтому эти методы на самом деле не зависят от модели. Однако это не является важным ограничением, поскольку в реальных приложениях мы обычно знаем, какой тип модели необходимо объяснить.

Давайте начнем с того, что попробуем древовидную модель на наборе данных Бостона.

# Listing 20 d = load_boston() df = pd.DataFrame(d['data'], columns=d['feature_names']) y = pd.Series(d['target']) X = df[['AGE', 'RAD', 'TAX', 'DIS']] tree_model = DecisionTreeRegressor(max_depth=3) tree_model.fit(X, y) fig = plt.figure(figsize=(20, 10)) plot_tree(tree_model, feature_names=X.columns, fontsize =16) plt.show()

Здесь мы используем регрессор дерева решений (из библиотеки scikit-learn) для моделирования подмножества бостонского набора данных с 4 функциями (AGE, RAD, TAX и DIS). Мы подгоняем модель и строим результирующее дерево, показанное на рисунке 9.

Каждый внутренний узел в этом дереве помечен функцией набора данных и представляет собой проверку этой функции. Каждая ветвь этого узла представляет результат теста. Значение каждого листового узла дает прогноз модели дерева для вектора признаков, который проходит все тесты на пути от корня дерева к листу. Например, мы можем использовать эту модель для прогнозирования целевого значения первой строки X в листинге 20:

X.iloc[0] ### Output: AGE 65.20 RAD 1.00 TAX 296.00 DIS 4.09 tree_model.predict(X.iloc[0:1]) ### Output: array([23.02767857])

Для этой строки у нас есть TAX <=416.5, TAX <= 267.5 и RID <= 7.5, поэтому, начиная с корня дерева, мы получаем лист со значением 23,028 (рис. 10). Это значение является предсказанием модели для первой строки X.

Теперь давайте посмотрим, что произойдет, если у нас есть значение NA в векторе признаков. Предположим, что у нас нет значений DIS в первой строке X. Таким образом, вектор признаков:

На основе этих значений мы можем перейти от корня к внутреннему узлу с тестом RAD<=7.5 (рисунок 11), но мы не можем пройти дальше, так как у нас нет значения RAD. Однако, глядя на левый и правый листы, мы знаем, что в этой модели у нас есть только два возможных прогноза для этого вектора признаков. Если RAD<=7.5, то прогноз равен 23,028. В противном случае прогноз равен 30,358. Мы также знаем, сколько выборок данных обучающего набора данных попало в каждый лист. Здесь 224 из 248 проб попали в левый лист, а остальные 24 пробы попали в правый лист (рис. 11). Количество отсчетов, попадающих в каждый узел, называется покрытием этого узла, поэтому покрытие узла с тестом RAD<=7.5 равно 248. На основании этих результатов можно сказать, что вероятность получения значение левого узла — 224/248, а вероятность получения значения правого узла — 24/248. Следовательно, прогнозируемое значение модели для этого вектора признаков равно:

Это среднее значение значений левого и правого листьев, взвешенных по их обложкам. Если вы посмотрите на рисунок 11, вы заметите, что значение узла, которое проверяет RAD <=7.5, равно тому же числу (23,737). Здесь scikit-learn вычисляет и показывает эти средние значения для всех внутренних узлов дерева. Давайте посмотрим на другой пример. Здесь вектор признаков:

В корневом узле мы не знаем значения TAX, поэтому берем средневзвешенное значение левой и правой ветвей. В правой ветке у нас нет значений признаков, протестированных на каких-либо внутренних узлах, поэтому мы берем средневзвешенное значение всех листьев:

Вероятность получения этого значения составляет 166/506. В левой ветви корня у нас нет значения TAX, поэтому берем средневзвешенное значение узлов с тестами TAX<=254.5 и RAD<=7.5. Для узла, который тестирует TAX<=254.5, мы берем средневзвешенное значение обоих листьев. Нам известно значение RAD, поэтому для узла, который тестирует RAD<=7.5, значение равно 23,028 с вероятностью 248/506. Наконец, прогноз модели для этого вектора признаков (рис. 12):

Теперь, когда мы знаем, как обрабатывать функции NA в древовидной модели, мы можем использовать рекурсивный алгоритм в алгоритме 1 для вычисления fₛ(xₛ)=E[f(x)|xₛ].

Функция EXPVALUE() берет вектор признаков для объяснения (x), коалицию S (содержащую доступные признаки) и древовидную модель и вычисляет f ₛ(xₛ)≈E[f(x)|xₛ]. В модели дерева у каждого узла есть индекс, а индекс корня равен 1. v — это вектор значений узлов. vⱼ.type указывает, является ли узел внутренним узлом или листом. Векторы a и b представляют индексы левого и правого узлов для каждого внутреннего узла. Вектор t содержит пороговое значение для каждого внутреннего узла, а d представляет собой вектор индексов признаков, используемых для разбиения во внутренних узлах. Вектор r содержит покрытие каждого узла. x.feature(dⱼ) дает имя функции в x с индексом dⱼ. На рис. 13 показано значение этих векторов для выборочного узла.

Функция G() принимает индекс узла и аккумулятора. Для внутреннего узла, если его признак не является членом S (что означает, что у нас нет значения этого признака), функция рекурсивно вычисляет значение левой и правой ветвей и возвращает их средневзвешенное значение.

Если функция узла находится в S, то левая или правая ветвь выбирается путем сравнения значения этой функции с порогом, и значение ветви вычисляется рекурсивно. Наконец, для листового узла его значение умножается на покрытие листа и возвращается. Реализация этого алгоритма на языке Python представлена в листинге 21.

Мы можем протестировать эту функцию на коалиции, показанной на рисунках 11 и 12:

expvalue(tree_model, x=X[:1].T.squeeze(), S=['TAX', 'AGE', 'DIS']) ### Output: 23.73709677419353 expvalue(tree_model, x=X[:1].T.squeeze(), S=['RAD']) ### Output: 22.18510728402032

Что произойдет, если мы попробуем пустой список для S?

expvalue(tree_model, x=X[:1].T.squeeze(), S=[]) ### Output: 22.532806324110666

Это средневзвешенное значение всех листьев в дереве. На самом деле scikit-learn уже вычислил его как значение корневого узла (см. рис. 9). Это равно среднему значению прогнозов всех экземпляров данных в наборе обучающих данных. Это связано с тем, что для каждого экземпляра данных прогноз модели представляет собой просто значение одного из листьев, и мы знаем вес каждого значения для всего набора обучающих данных. Из уравнения 7, когда у нас нет доступных функций, прогноз модели представляет собой среднее значение прогнозов для экземпляров в выборке набора обучающих данных, и здесь мы используем весь набор обучающих данных вместо выборки. Мы также знаем из свойства 1, что ϕ₀ =E[f(x )]. Таким образом, запуск expvalue() с пустой коалицией возвращает ϕ₀. Кроме того, значение корневого узла, рассчитанное с помощью scikit-learn, также равно ϕ₀.

Теперь мы можем использовать эту функцию для вычисления значения SHAP регрессора дерева решений. Мы можем использовать тот же код в листинге 5 с небольшими изменениями. В функции coalition_contribution() мы используем expvalue() для расчета предсказания модели для каждой коалиции, а в calculate_exact_tree_shap_values() мы используем значение корневого узла как ϕ₀.

Теперь мы можем протестировать эту функцию, чтобы объяснить строку X:

# Listing 23 calculate_exact_tree_shap_values(tree_model, X.iloc[470])

Output:

(22.532806324110698, [[0.17363555010556078, 1.6225955204216118, -6.753886031609969, 1.1484597480832428]])

Функция EXPVALUE(), определенная в алгоритме 1, гораздо лучше подходит для вычисления fₛ(xₛ). Теперь у нас есть:

Это позволяет нам получить точное значение fₛ(xₛ) для обученной древовидной модели. на определенном наборе данных, и ответ более надежен, чем приближение, данное в

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

Временная сложность алгоритма 1 пропорциональна количеству листьев в дереве. Это потому, что наихудший сценарий — это когда у нас есть коалиция, которая не содержит ни одного из признаков внутренних узлов дерева. В этом случае алгоритм должен вычислить средневзвешенное значение всех листьев. Таким образом, временная составляющая EXVALUE() равна O(L), где L — количество выходов. У нас есть функции M, и для каждой функции мы должны оценить 2ᴹ-1 коалиций (исключая эту функцию). Таким образом, временная сложность нахождения значений SHAP всех признаков составляет O(LM2ᴹ⁻¹)=O(LM2ᴹ)

Наконец, для модели ансамбля мы можем использовать деревья T в ансамбле, что приводит к временной сложности O(TLM2 ᴹ) для вычисления значений SHAP всех функций M. В результате вычисление значений SHAP древовидной модели с использованием алгоритма 1 требует больших вычислительных ресурсов для больших значений M.

Алгоритм дерева SHAP

Лундберг и др. al [3] предложил эффективный алгоритм, который может уменьшить временную сложность поиска значений SAHP в древовидной модели. К сожалению, алгоритм, приведенный в [3], содержит очень много опечаток и не имеет четкого объяснения. Итак, в этом разделе я представлю исправленную версию этого алгоритма и попытаюсь объяснить, как он работает. Алгоритм 2 дает исправленную версию исходного алгоритма из [3] (исправления отмечены красным).

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

Мы можем протестировать функцию tree_shap() с той же строкой, которая использовалась в листинге 23:

# Listing 25 tree_shap(tree_model, X.iloc[470])

Output:

(22.532806324110698, array([ 0.17363555, 1.62259552, -6.75388603, 1.14845975]))

Здесь мы получаем те же значения SHAP, что и в листинге 23.

Как работает алгоритм дерева SHAP? (необязательно)

Чтобы понять этот алгоритм, нам сначала нужно понять математику, стоящую за ним [4]. Здесь мы используем те же обозначения алгоритма 1, но нам также необходимо ввести некоторые дополнительные обозначения (рис. 14). Предположим, что у нас есть дерево с листьями L, и значения этих листьев равны v₁…v_L. Путь Pₖ определяется как набор внутренних узлов, начиная с корня и заканчивая листом со значением vₖ (мы включаем только внутренние узлы, поэтому лист сам не входит в путь). Следовательно, у нас есть пути L в этом дереве (P₁…P_L).

Пусть j будет j-м внутренним узлом в пути Pₖ (так что для каждого пути Pₖ, jравно нулюдля корневого узла и увеличивается на 1 для следующего узла пути), и пусть Dₖ = {dⱼ | j ϵ Pₖ} — набор индексов уникальных признаков, используемых для разбиения во внутренних узлах пути Pₖ (здесь предполагается, что каждый признак в векторе признаков x имеет индекс). Кроме того, tₖⱼобозначает порог внутреннего узла j в пути Pₖ. Отсюда {tₖⱼ | j ϵ Pₖ} — набор порогов внутренних узлов на пути Pₖ. Мы предполагаем, что Tₖⱼ = (-∞, tₖⱼ], если узел j соединяется со своим левым дочерним элементом на пути Pₖ и Tₖⱼ = (tₖⱼ, ∞), если узел j соединяется со своим правым дочерним элементом на пути Pₖ. Наконец, коэффициенты покрытия вдоль пути Pₖ обозначаются множеством {Rₖⱼ | j ϵ Pₖ}, где Rₖⱼ = r_(k,j+1)/rₖⱼ и rₖⱼ является покрытием внутреннего узла j пути Pₖ.

Теперь можно показать, что значение ϕᵢ можно рассчитать по следующей формуле:

где 𝟙{.} — индикаторная функция, поэтому

Доказательство этого уравнения дано в [4].

Первая сумма в уравнении 48 относится ко всем путям, в которых узел содержит функцию i. Как упоминалось ранее, Dₖ — это набор всех уникальных функций пути Pₖ. Третья сумма в этом уравнении вычисляется по всем коалициям Dₖ с элементами m, которые не содержат признак i. Итак, для каждой функции i нам нужно найти пути, содержащие эту функцию, и рассчитать вклад каждого пути в значение SHAP этой функции. На основании уравнения 48 значение SHAP представляет собой сумму всех этих вкладов:

Теперь давайте посмотрим, как работает алгоритм дерева SHAP. Алгоритм 2 рекурсивно находит все пути в дереве. В конце каждого пути он вычисляет вклад этого пути во все функции и добавляет их к переменной ϕᵢ (так что каждый ϕᵢ в алгоритме 2 является аккумулятором для значение SHAP функции i). Когда алгоритм охватывает все пути, ϕᵢ равняется значению SHAP признака i. Переменная m в алгоритме 2 (эквивалентная фрейму данных m в листинге 24) представляет собой таблицу с 4 полями: d, z, o и w. В этих полях хранится информация, необходимая нам в каждом пути для расчета его вклада в значение SHAP функции i. Когда алгоритм перемещается по пути, m содержит индексы всех уникальных функций, найденных на этом пути до сих пор. Эти индексы хранятся в поле d в m. В функции RECURSE() если мы находим лист, то используем этот цикл:

Здесь w = sum(UNWIND(m, i).w) равно:

mᵢ.o в таблице m дает значение:

И mᵢ.zдает:

Таким образом, вычисление w(mᵢ.o-mᵢ.z).vⱼ эквивалентно вычислению:

в уравнении 48. Следовательно, цикл For вычисляет вклад пути в значение SHAP функций, присутствующих в этом пути. Цикл For начинается с 2, так как мы начинаем заполнять m с этого индекса. Функция RECURSE(j, m, pz , po, pᵢ) принимает пять параметров. j — это индекс текущего узла в дереве (мы инициализируем его 0, который является индексом корневого узла). Индекс функции, которая используется для разделения предыдущего узла по пути, хранится в pᵢ. Функция, которая используется для разделения текущего узла, — vⱼ. В зависимости от значения этого признака следует выбирать левый или правый дочерний узел. Индекс выбранного узла называется горячим индексом (h), а индекс другого дочернего узла будет холодным индексом (c):

Поскольку нам нужен только набор уникальных признаков в пути, алгоритм проверяет, хранится ли уже vⱼ в m или нет? Если это повторяющаяся функция, она будет удалена с помощью UNWIND(). Функция RECURSE() вызывает себя в конце как для горячего, так и для холодного индекса:

Если dⱼ является повторяющимся объектом, его коэффициент покрытия в m (поле mₖ.z) находится и сохраняется в iz. В противном случае имеем iz=1. Коэффициент покрытия текущего узла (либо rₕ/rⱼ, либо r𝒸/rⱼ) затем умножается на i𝓏 и передается как p𝓏 в RECURSE(). Следовательно, p𝓏 накапливается

вдоль пути. pₒ следит за

Для горячего индекса мы передаем mₖ.o (если dⱼ является повторяющейся функцией) или 1 как pₒ для RECURSE(), а для холодного индекса мы передаем 0 как pₒ. Функция EXTEND() вызывается для хранения информации о каждом объекте, найденном на пути. Он сохраняет pᵢ, pz иpₒ в mᵢ.d,mᵢ.z,иmᵢ.o соответственно. Он также вычисляет

И сохраняет его в mᵢ.w.

Но как эти значения генерируются вдоль пути? Функция EXTEND() отвечает за формирование значений

для h=0, 1, …,|Dₖ|. В конечном узле поле w в m содержит значения уравнения 50 для h=0, 1, …,|Dₖ|. Обратите внимание, что в уравнении 48 третья сумма превышает S⊆Dₖ\{i},|S|=ч. Таким образом, чтобы рассчитать вклад пути в значения SHAP, сначала нам нужно удалить функцию {i} из уравнения 50. Вот почему мы сначала вызываем UNWIND(m, i).w), а затем применяем SUM() к результату. Как упоминалось ранее, sum(UNWIND(m, i).w) равно уравнению 49. Также обратите внимание, что и EXTEND(), и UNWIND() делают копию m перед изменением и возвратом. Скопированный m будет использоваться для текущего узла, а исходный m останется неизменным для предыдущего узла. В результате, когда мы путешествуем по дереву, m содержит только набор уникальных признаков на текущем пути.

Алгоритм 2 уменьшает временную сложность алгоритма 1 с экспоненциальной до полиномиальной низкого порядка. Циклы в функциях EXTEND() и UNWIND() ограничены длиной m. Поскольку m отслеживает уникальные объекты вдоль пути, он ограничен D максимальной глубиной дерева. Следовательно, временная сложность UNWIND() и EXTEND() равна O(D). Цикл в функции RECURSE() также ограничен длиной m. Однако для листа функция UNWIND() вызывается внутри этого цикла, поэтому временная сложность RECURSE() составляет O(D²), так как UNWIND() вложена в цикл, ограниченный Д. Функция RECURSE() должна найти все пути дерева, а количество путей равно количеству листьев. Таким образом, если предположить, что L — это максимальное количество листьев в любом дереве, временная сложность RECURSE() для всего дерева будет O(LD² ). Наконец, для ансамбля Tдеревьев временная сложность становится O(TLD²).

Tree SHAP для ансамблей деревьев

Мы можем легко использовать функцию tree_shap() для вычисления значений SHAP моделей ансамбля деревьев. Предположим, что у нас есть ансамбль деревьев T. Мы можем рассчитать значения SHAP для каждого дерева отдельно, и мы называем значение SHAP признака i в j-м дереве ϕᵢ⁽ʲ⁾. Поскольку все эти деревья одинаково важны, значение SHAP функции i для всего ансамбля представляет собой просто среднее значение значений SHAP iдля всех деревьев внутри ансамбля. :

Функцию tree_shap_ensemble() в листинге 26 можно использовать для вычисления значений SHAP модели ансамбля деревьев.

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

# Listing 27 d = load_boston() df = pd.DataFrame(d['data'], columns=d['feature_names']) y = pd.Series(d['target']) X = df[['AGE', 'RAD', 'TAX', 'DIS']] rf_model2 = RandomForestRegressor(random_state=0, n_estimators=4).fit(X, y) tree_shap_ensemble(rf_model2, X.iloc[470]) ### Output: (22.340563241106732, array([-0.60018849, 1.36914776, -6.2207912 , 2.33626868]))

Дерево SHAP в библиотеке SHAP

Класс TreeExplainer в библиотеке SHAP можно использовать для вычисления значений SHAP с использованием метода дерева SHAP как для деревьев, так и для ансамблей деревьев. Здесь мы используем этот класс для вычисления значений SHAP набора данных и модели, определенных в листинге 20.

explainer = shap.TreeExplainer(tree_model) shap_values = explainer.shap_values(X.iloc[470]) shap_values ### Output: array([ 0.17363555, 1.62259552, -6.75388603, 1.14845975]) explainer.expected_value ### Output: array([22.53280632])

Как видите, значения SHAP почти такие же, как значения SHAP, возвращаемые calculate_shap_values() в листинге 23 и tree_shap() в листинге 25. Этот класс также можно использовать для случайного леса, определенного в листинге 27, и результат почти такой же, как и вывод. этого Листинга.

explainer = shap.TreeExplainer(rf_model2) shap_values = explainer.shap_values(X.iloc[470]) shap_values ### Output: array([-0.60018849, 1.36914776, -6.2207912 , 2.33626868]) explainer.expected_value ### Output: array([22.34056324])

Графики SHAP

В библиотеке Shap есть несколько хороших инструментов для визуализации значений SHAP. Графики водопада могут отображать значения SHAP для отдельных векторов признаков. В качестве примера мы обучаем модель XGBoost на наборе данных Бостона и отображаем график водопада для одного экземпляра X:

d = load_boston() df = pd.DataFrame(d['data'], columns=d['feature_names']) X = df y = pd.Series(d['target']) xgb_model = xgboost.XGBRegressor(random_state=1).fit(X, y) explainer = shap.Explainer(xgb_model, X) explanation_object = explainer(X) shap_values = explainer.shap_values(X) # visualize the first prediction's explanation shap.plots.waterfall(explanation_object[0])

Помните, что из уравнения 22 мы имеем:

График водопада может визуализировать это уравнение для нас. Нижняя часть каскадного графика начинается с E[f(x)]=22,343, и каждая стрелка в этот график показывает положительный (красный) или отрицательный (синий) вклад каждой функции в прогноз. Длина каждой стрелки равна абсолютному значению SHAP соответствующего признака. Значение SHAP записывается над стрелкой, а значение соответствующего признака также записывается по вертикальной оси (например, на графике выше значение признака LSTAT равно 4,98, а его значение SHAP равно 4,64). Если значение SHAP положительное, стрелка становится красной и идет вправо. Для отрицательного значения SHAP он синий и идет влево. Следуя этим стрелкам, мы, наконец, достигаем значения предсказания модели f(x)=21,019. Объекты сортируются по абсолютным значениям их SHAP, поэтому объект с наибольшим абсолютным значением SHAP находится вверху. Обратите внимание, что нам нужно напрямую передать объект объяснения в waterfall(), а не значения SHAP, возвращаемые методом shap_values() из Explainer.

Мы также можем использовать график силы для визуализации значений SHAP:

shap.initjs() shap.plots.force(explanation_object[0])

График силы похож на график водопада, однако стрелки расположены горизонтально. Красные стрелки и стрелки сортируются в зависимости от их длины, поэтому красные стрелки становятся длиннее слева направо, а синие стрелки — справа налево. Значение каждого признака (не его значение SHAP) написано за соответствующей стрелкой. Самая длинная красная и синяя стрелки пересекаются в точке f(x)=21,019. Значение E[f(x)]=22,343 также показано на графике, помеченном как основание ценить.

Мы также можем использовать гистограмму для отображения значений SHAP. Мы можем использовать функцию shap.plots.bar(), которая принимает объект Explanation. На гистограмме не показаны стрелки, значения f(x) и E[f(x)] и значение функций. Длина каждой полосы равна абсолютному значению SHAP соответствующего признака. Полоса окрашивается в красный/синий цвет для положительных/отрицательных значений SHAP, а значения SHAP записываются рядом с каждой полосой. Функции сортируются по абсолютным значениям их SHAP-значений.

shap.plots.bar(explanation_object[0])

Мы также можем заставить гистограмму отображать только абсолютные значения SHAP:

shap.plots.bar(explanation_object[0].abs)

Пчелиный график полезен для подведения итогов анализа SHAP для большого количества случаев. Во-первых, мы используем его только для одного экземпляра. Функция shap.plots.beeswarm() принимает объект Explanation. Обратите внимание, что функция имеет баг, и при ее вызове она изменяет значения SHAP объекта Explanation, которые она принимает, поэтому всегда следует передавать ей глубокую копию объекта Explanation.

import copy shap.plots.beeswarm(copy.deepcopy(explanation_object[0:1]))

График похож на гистограмму, однако вместо гистограммы у нас есть точки для каждого значения SHAP. Позиция x каждой точки дает значение SHAP соответствующего объекта. Поскольку у нас есть только один экземпляр, все точки имеют одинаковый цвет. Теперь мы попробуем это для двух экземпляров. Теперь для каждой функции у нас есть две точки, и каждая точка представляет один из экземпляров.

shap.plots.beeswarm(copy.deepcopy(explanation_object[0:2]))

Точки окрашены в зависимости от значения соответствующего признака. Для каждой функции экземпляр с более высоким значением (этой функции) окрашен в красный цвет, а другой — в синий. Но как сортируются функции, когда у нас более одного экземпляра? Функции сортируются на основе среднего значения абсолютных значений SHAP для всех экземпляров. Теперь мы можем попробовать это на других экземплярах:

shap.plots.beeswarm(copy.deepcopy(explanation_object))

Как вы видите на этом графике, максимальное значение SHAP принадлежит объекту DIS, но LSTAT имеет самое высокое среднее значение для всех экземпляров. Мы можем изменить это и отсортировать функцию по максимальному абсолютному значению SHAP.

shap.plots.beeswarm(copy.deepcopy(explanation_object), order=explanation_object.abs.max(0))

Теперь DIS сидит сверху. Мы также можем использовать более одного экземпляра с гистограммой. В этом случае он рассчитает среднее значение абсолютного значения SHAP для всех экземпляров и отсортирует объекты на его основе. Среднее значение абсолютных значений SHAP также показано рядом с полосами.

shap.plots.bar(explanation_object)

Наконец, мы можем отобразить график силы для нескольких экземпляров. Вот пример для 3 экземпляров:

shap.force_plot(explainer.expected_value, shap_values[0:3,:], X.iloc[0:3,:], plot_cmap="DrDb")

Этот график представляет собой комбинацию трех отдельных графиков силы (подобных графику в уравнении 14), повернутых на 90 градусов и сложенных горизонтально (см. рисунок 16). Вот еще один пример с большим количеством экземпляров:

shap.force_plot(explainer.expected_value, shap_values, X, plot_cmap="DrDb")

Мы можем выбрать, как будут складываться отдельные силовые графики. Например, на рис. 25 отдельные графики сгруппированы по сходству. Если предположить, что значения SHAP каждого экземпляра образуют точку в M-мерном пространстве, то сходство определяется евклидовым расстоянием между этими точками и точками (или экземплярами), которые больше подобные (имеющие меньшее расстояние) укладываются вместе. Есть и другие варианты стекирования экземпляров. Например, мы можем отсортировать их по значению f(x) для каждого экземпляра. Это показано на рисунке 26. Здесь значение f(x) для экземпляров уменьшается слева направо.

Объяснение моделей машинного обучения является важной темой. Под объяснением мы подразумеваем, что хотим иметь качественное понимание взаимосвязи между индивидуальным прогнозом модели и функциями, используемыми для создания этого прогноза. Мы можем объяснить сложную модель с помощью простого интерпретируемого объяснения модели и определить важность ее функций. SHAP — это индивидуализированный объяснитель, не зависящий от модели, который был разработан на основе теоретико-игровой концепции, называемой значениями Шепли. Значения SHAP предоставляют коэффициенты линейной модели, которая в принципе может объяснить любую модель машинного обучения.

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

Я надеюсь, что вам понравилось читать эту статью. Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы или предложения. Все листинги кода в этой статье доступны для загрузки в виде блокнота Jupyter с GitHub по адресу: https://github.com/reza-bagheri/SHAP.

Ссылки

1-Скотт М. Лундберг и Су-Ин Ли. Единый подход к интерпретации прогнозов моделей. В материалах 31-й международной конференции по нейронным системам обработки информации, стр. 4768–4777, 2017 г.

2- Скотт М. Лундберг и Су-Ин Ли. Единый подход к интерпретации прогнозов модели. Материалы 31-й международной конференции по нейронным системам обработки информации (2017 г.), Дополнительный материал (https://papers.nips.cc/paper/2017/file/8a20a8621978632d76c43dfd28b67767-Supplemental.zip).

3-Скотт М. Лундберг, Габриэль Г. Эрион и Су-Ин Ли. Согласованная индивидуализированная атрибуция признаков для ансамблей деревьев. Препринт arXiv arXiv:1802.03888, 2018.

4-Джилэй Ян. Fast TreeSHAP: ускорение расчета стоимости SHAP для деревьев.
препринт arXiv arXiv:2109.09847, 2021.

Приложение

Доказательство линейного уравнения SHAP

Предположим, что наша прогностическая модель f является моделью линейной регрессии:

где x₀=1, а признаки Xᵢ, i = 1, …, M независимы. Используя уравнение 28, мы можем написать:

Предположим, что в наборе S̅ есть k объектов. Поскольку все эти функции независимы, мы имеем:

Заменив это уравнение в предыдущем, получим:

Поскольку все вероятности нормированы, мы можем написать:

Кроме того, у нас есть:

Итак, у нас есть:

Теперь, чтобы вычислить f_S∪{i}(x_S∪{i}) из fₛ(xₛ), нам нужно взять признак i из S̅в уравнении 52 и добавить его к S:

Заменив это уравнение в уравнении 11 и используя уравнение 4, мы получим:

Обратите внимание, что в уравнении 51 мы можем полагаться только на выборку обучающего набора данных для расчета среднего значения, поэтому мы имеем:

Здесь E[xᵢ] — среднее значение xᵢ по всем экземплярам выборки обучающего набора данных (k экземпляры), и мы имеем:

Доказательство ядерной теоремы SHAP (теорема 1)

Мы предполагаем, что у нас есть вектор признаков x с признаками M. Сначала мы докажем это для случая, в котором нет недостающих признаков, поэтому мы имеем:

Затем мы вычисляем все возмущения x’. Каждое возмущение x' представляет собой коалиционный вектор с элементами M, и каждый элемент может быть либо 0, либо 1. Таким образом, мы имеем 2ᴹ возмущения. Мы называем каждое возмущение z’ᵢ (что является вектором-строкой). Поместим все эти возмущения (или коалиционные векторы) в коалиционную матрицу 2ᴹ×M X:

Для каждого коалиционного вектора z'ᵢ мы можем вычислить предсказание модели fₓ(zᵢ ). Мы определяем вектор-столбец y как:

где c₀ — константа. В исходной статье, в которой представлен SHAP [1], c₀ не включено в y, что неверно. Мы предполагаем, что

И мы определяем 2ᴹ×2ᴹ диагональную матрицу W как:

Теперь предположим, что

Нам нужно показать, что при стремлении M к бесконечности решение уравнения

is

где ϕᵢ — значения Шепли f и x, определенные в уравнении 18. Путем замены уравнения 57 и уравнения 58 в уравнении 59 мы получаем:

Итак, минимизируемая целевая функция:

Мы можем заменить коалиционные векторы z’ᵢв уравнение 60, чтобы получить:

Мы ограничиваем поиск оптимальной функции g линейными функциями следующего вида:

Здесь c₀ — та же константа, что и в уравнении 54. Для каждого коалиционного вектора zᵢ это уравнение записывается как:

где [z'ᵢ]ⱼ — j-й элемент коалиционного вектора z'ᵢ. Заменив это уравнение в уравнении 61, мы получим:

Здесь мы использовали тот факт, что [z'ᵢ]ⱼ является элементом ij матрицы X в уравнении 53, а yᵢ — это i-й элемент вектора y в уравнении 54. Теперь мы определяем вектор-столбец c как:

Итак, мы можем использовать определение умножения матриц, чтобы написать:

Обратите внимание, что Xc — это вектор-столбец, а [Xc]ᵢ его i-й элемент. Мы также знаем, что πₓ(z'ᵢ)является i-й диагональный элемент матрицы W (уравнение 56). Итак, мы можем снова использовать определение умножения матриц, чтобы написать:

В результате делаем вывод, что:

Здесь мы используем тот факт, что g является только функцией cᵢ, поэтому вместо поиска функции g, которая минимизирует целевую функцию, мы находим значение вектора c, которое минимизирует его. Фактически эта целевая функция аналогична функции потерь модели взвешенной линейной регрессии. Теперь мы можем минимизировать эту целевую функцию:

Таким образом, значение c, которое минимизирует целевую функцию, равно:

Теперь нам нужно упростить это уравнение. Во-первых, упростим XᵀW:

Итак, у нас есть:

Из уравнения 64 мы можем заключить, что i-я строка XᵀW равна:

И j-й столбец X:

Теперь, исходя из определения умножения матриц, элемент ij в XᵀWX равен скалярному произведению. i-й строки XᵀW и j-й столбец X:

Теперь давайте посмотрим на определение πₓ(z’ᵢ):

Как видите, это функция M и количества ненулевых записей в z' (|z '|). Итак, для того же x:

Кроме того, мы знаем, что максимальное значение |z’ᵢ| это M. В уравнении 66, если i=j, мы имеем:

Поскольку z'ᵢ является бинарным вектором, [z'ₖ]ᵢ либо ноль, либо единица. Таким образом, нам нужно включить только те термины, для которых [z’ₖ]ᵢ=1. Теперь в этом уравнении мы можем сгруппировать все слагаемые, для которых |z’ᵢ| это определенное число, скажем, m. Для каждой группы πₓ(z'ᵢ) одно и то же (только функция m ):

Важно отметить, что для m=0 (когда все элементы z'ᵢ равны нулю) и m=M(когда все элементы z'ᵢ равны единице), πₓ (z'ᵢ)=∞. Однако это не влияет на это доказательство. Для каждого значения m мы подсчитываем количество терминов, для которых |z'ᵢ|=m и [ z'ₖ]ᵢ=1, и мы обозначаем это количество как:

Все эти термины имеют одно и то же πₓ(z’ᵢ). Итак, уравнение 67 можно записать так:

Аналогично, если i≠j, имеем:

Теперь нам нужно вычислить значение

Мы знаем, что коалиционный вектор z’ₖсодержит M элементов. Мы хотим, чтобы i-й элемент был равен 1. А общее количество единиц в z'ₖ должно быть m. Таким образом, помимо i-го элемента, нам нужно, чтобы m-1 элементов z'ₖ были равны 1 а остальные равны 0. Таким образом, это похоже на выбор m-1 элементов из M-1 элементов. Так:

Аналогично имеем:

Комбинируя эти уравнения с уравнением 68, уравнением 69 и уравнением 70, мы получаем:

На основании этого результата все диагональные элементы XᵀWX равны E1, а все не -диагональные элементы равны E2. Итак, мы можем написать XᵀWX как:

где I — это единичная матрица M×M, а J — это матрица единиц M×M, в которой каждый элемент равен единице. Теперь нам нужно вычислить a и b в этом уравнении. Для недиагональных элементов XᵀWX имеем:

А для диагональных элементов:

Итак, у нас есть система из двух уравнений и решая их получаем:

Для m=M последние два члена в правой части этого уравнения компенсируют друг друга (хотя оба они стремятся к бесконечности):

Теперь мы можем упростить это уравнение:

Подставив это уравнение в уравнение 71, мы получим:

Теперь нам нужно вычислить (XᵀWX)⁻¹. Мы можем показать, что:

Чтобы доказать это, мы должны помнить, что для любой матрицы A:

Теперь у нас есть:

Длялюбой матрицы M×Mнапример, J мы можем легко показать, что:

Заменив это уравнение в предыдущем, получим:

Так как M стремится к бесконечности, правая часть этого уравнения становится I. Точно так же мы можем показать, что:

Однако в исходной статье, в которой был представлен SHAP [2], XᵀWXвыводится неправильно (XᵀWX)⁻¹ по-прежнему верно!

Теперь нам нужно вычислить (XᵀWX)⁻¹XᵀW. Из уравнения 65 мы знаем, что j-й столбец XᵀW равен πₓ(z'ⱼ)z'ⱼᵀ. Элемент ij из (XᵀWX)⁻¹X ᵀW – это скалярное произведение i-й строки (XᵀWX)⁻¹ и j-й столбец XᵀW. Из уравнения 73 мы знаем, что

Где индекс i,* обозначает i-ю строку матрицы. Наконец, мы можем вычислить вектор c по уравнению 63. j-й элемент вектора c — скалярное произведение j-й строки матрицы (XᵀWX)⁻¹XᵀW и i-й элемент вектора г:

Сначала рассмотрим коалиционный вектор z'ᵢ, для которого [z'ᵢ]ⱼ=0. Для такого вектора мы можем использовать уравнение 55 и уравнение 74 и написать:

Затем мы рассматриваем коалиционный вектор z'ᵢ₊, равный z'ᵢ с j-м элементом, равным 1. Таким образом, мы можем написать:

Мы также предполагаем, что:

Теперь мы можем использовать уравнение 74 и уравнение 77, чтобы написать:

Комбинируя уравнение 76 и уравнение 78, мы имеем:

Наконец, мы можем использовать уравнение 75, чтобы написать:

Вместо суммирования по z'ᵢдля которых [z'ᵢ]ⱼ =0, мы можем суммировать по z'ᵢ₊. В этом случае, используя уравнение 77, мы имеем:

Помните, что для z'ᵢ₊ элемент j установлен равным 1. Однако мы также можем добавьте любое z'ᵢв котором [z'ᵢ]ⱼ=0 . Это потому, что для такого коалиционного вектора fₓ(z'ᵢ₊)-fₓ(z'ᵢ)=0, поэтому к этой сумме ничего не прибавляется, поэтому мы можем добавить любую коалицию вектор x' к этой сумме:

Если мы сравним это уравнение с уравнением 18, мы придем к выводу, что:

Таким образом, вектор c дает значения Шепли f и x, и функция, которая минимизирует целевую функцию в уравнении 61, имеет следующий вид:

Что в общем случае можно записать так:

Как видите, минимизация не определяет значение c₀. (Это похоже на минимизацию функции типа y=x²+c, где точка минимума находится в x= 0 независимо от значения c). Чтобы определить c₀, мы установили для всех функций значение NA, затем z'ᵢ=0 для i=1..М. Следовательно, мы имеем:

Мы также знаем, что в этом случае прогноз модели представляет собой среднее значение прогнозов экземпляров в выборке обучающего набора данных (уравнение 22). Так:

Следовательно, поскольку M стремится к бесконечности, мы имеем:

где ϕ₀ =E[f(x)] и ϕᵢ (для i=1..M) дают значения Шепли для f и x. Для этого доказательства мы изначально предполагали, что |x'|=M, поэтому x' не имеет нулевых элементов, а x не имеет отсутствующих функций. Если у нас есть нулевые элементы в x' (|x'|‹ M), мы включаем только те элементы x', которые равны 1 (x'ᵢ=1) и к ним применимо то же доказательство. Для нулевых элементов x' (которые соответствуют отсутствующим функциям в x) мы предполагаем, что ϕᵢ=0, что соответствует уравнению 18.

Упрощенное уравнение решения ядра SHAP

Рассмотрим коалиционную матрицу X, определенную в уравнении 35, и пусть z'₁ и z '_2ᴹбудет коалицией "все нули" и "все единицы" соответственно. Сначала мы создаем новую матрицу с именем Xₜ, исключая z'₁ и z '_2ᴹиз коалиционной матрицы X:

Если исключить термины, соответствующие z'₁ и z'_2ᴹ в целевой функции уравнения 40 мы получаем:

Теперь мы можем использовать уравнение 43, чтобы получить:

Обратите внимание, что [z'ᵢ]_M — это M-й столбец матрицы Xₜ. Теперь мы можем определить матрицу (2ᴹ-2)×(M-1) X ᵣ как:

Здесь [Xₜ]_*,i — это i-й столбец Xt. Таким образом, Xᵣ формируется путем вычитания последнего столбца Xₜ из первого M-1 столбцов. Теперь вы можете легко показать, что элемент ij Xₜ равен:

Мы также определяем вектор-столбец cᵣ как:

и определите вектор-столбец yᵣ с 2ᴹ-2 элементами как:

Итак, i-й столбец yᵣ:

Теперь, используя определение матричного умножения, мы имеем:

Наконец, мы определяем (2ᴹ-2)×(2ᴹ-2) диагональную матрицу Wᵣ как:

Теперь, если мы будем следовать той же процедуре, которая использовалась для упрощения уравнения 62, мы получим:

Итак, нам нужно решить эту задачу минимизации:

и аналогично уравнению 63, значение cᵣ, которое минимизирует эту целевую функцию, равно:

Введение в значения SHAP и их применение в машинном обучении

Узнайте, как библиотека SHAP работает внутри

Вопросы по теме