Мы обсудим основы Ценностей Шепли (SV). SV берут свое начало в теории игр (GT) и были названы в честь их изобретателя, лауреата Нобелевской премии Ллойда С. Шепли (см. краткий биографический очерк в конце). В этой заметке мы сосредоточимся на самых основных аспектах — как определяются и рассчитываются SV. В следующей заметке мы рассмотрим базовый вариант использования в машинном обучении. Мы начнем с простого примера.

Простой пример (Как разделить совместную прибыль в фирме): Предположим, у нас есть два бизнесмена (называемые игроками или агентами в GT) a и b. Когда a работает в одиночку, они могут принести 150 (единиц — представьте себе долларов). Когда b работает сам по себе, они могут принести 400. Однако, когда они работают вместе, благодаря их хорошей синергии они зарабатывают 600. Как это должно быть вместе разделить между ними заработанную сумму в 600? Конечно, есть много способов разделить совместный заработок: во-первых, мы могли бы просто разделить поровну — каждый получает 600/2 = 300. Другой способ — разделить по их «история». Таким образом, a получает: 600 * (150 / (150 + 400)) = 163,64, а b получает: 600 * (400 / ((150 + 400)) = 436,37. . Могут быть и другие способы. Однако ответ, согласно Шепли, заключается в том, что при принципиальном разделении каждый получает долю, равную его индивидуальной SV. Чтобы вычислить SV для a и b, мы беремсреднее значение их предельных вкладов. Грубо говоря, «предельный» следует понимать здесь в том же смысле, что и «дополнительный». См. таблицы ниже:

Таким образом, a должен получить 175, что является их SV; так как SV b равен 425, они должны получить 425. Как мы рассчитали SV? Возьмем случай a:

  • Сначала мы находим, сколько раз a появляется в «групповой расстановке» (коалиции в GT): Здесь они появляются дважды — один раз сами по себе, S₁= {а}; а затем с b, S₂= {a, b}.
  • Для каждой такой коалиции Sᵢ:
  • * Находим значение или вклад этой коалиции: v(Sᵢ)
  • * Затем мы удаляем a из сопоставления Sᵢ, сохраняя при этом всех остальных, и находим значение усеченной коалиции Sᵢ' (= Sᵢ-{a} = Sᵢ -a ): v (Sᵢ')
  • * Затем мы находим предельное значение a для Sᵢ как разность двух приведенных выше значений: dvᵢ = v(Sᵢ) — v(Sᵢ’)
  • Мы берем среднее значение всех предельных значений, сгенерированных, как указано выше.

Здесь у нас есть:

  1. S₁ = {а}; S₁’ = пустой набор; v(S₁) = 150, v(S₁’) = 0 и dv₁ = 150–0 = 150.
  2. S₂ = {а, б}; S₂’ = {b}; v(S₂) = 600, v(S₂’) = 400 и dv₂ = 600–400 = 200.

Следовательно, SV для a: SV(a) = mean(dv₁, dv₂) = (150 + 200) / 2 = 350 / 2 = 175.

Аналогичные вычисления можно выполнить для b, чтобы получить SV(b) = 425. Отметим несколько моментов:

  • Сумма SV составляет 600, что равно общему заработку.
  • Как отмечалось выше, распределение с использованием SV не является ни равномерным, ни просто пропорциональным. Интуитивно понятно, что именно синергия (или ее отсутствие) в каждой коалиции влияет на каждое из соответствующих предельных значений и, в свою очередь, на SV.

Итак, чего мы достигли? Мы разделили совместно заработанные совместные доходы и выделили соответствующую сумму каждому сотрудничающему игроку; сумма, выделенная для каждого игрока, является их SV.

Формула SV: Давайте обсудим общую формулу для вычисления SV.Нам дан набор N = {1, 2, 3, …, n} из n, взаимодействующих друг с другом. игроков и функцию значений v() для каждой коалиции игроков. Мы будем условно называть v() «игрой» с |N| = п в виду. Набор мощностей (т. Е. Набор всех подмножеств) N равен 2 ^ N, который имеет мощность 2 ^ | N |; тогда мы можем записать отображение v в виде v: 2^N -> R. Коалиция S — это любой член этого набора степеней (например, для |N| = 10 существует 2¹⁰ = 1024 коалиции; одна коалиция-кандидат S равна { 1, 4, 9}); и, как и ранее, S-i обозначает ту же коалицию, но без игрока i в ней. Тогда SV ϕᵢ(v) игрока i в игре v() будет:

где сумма берется по всем коалициям S, содержащим игрока i (с учетом того, что |S| = s). Формула выражает SV игрока i как взвешенную сумму членов формы [v(S) — v(S-i)]. Каждый такой член представляет собой предельный вклад игрока i в коалицию S.

Хотя это довольно просто, давайте применим формулу к вычислению SV b сверху. У нас есть |Н| = n = 2 и две коалиции с участием b; соответствующие маргиналы и веса следующим образом:

  • S₁ = {b}; s = 1, маргинал (S₁) = 400–0 = 400; вес w₁ = (1–1)! (2–1)! / 2! = ½ и
  • S₂ = {а, б}; s = 2, предельный (S₂) = 600–150 = 450; вес w₂ = (2–1)! (2–2)! / 2! = ½.

Следовательно, SV(b) = ½ * 400 + ½ * 450 = 200 + 225 = 425, как и выше. Заметим, что веса в формуле для SV ϕᵢ(v) одинаковы для всех коалиций одинаковой мощности s. Более того, они равны и для мощностей s и n-s+1 (можно проверить подстановкой в ​​формулу (n-s)! (s-1)!). Последний отвечает за равные веса ½ в примере.

Почему? Шепли опубликовал приведенную выше формулу в своей знаменитой статье 1953 года ([1]). В своей статье Шепли аксиоматизировал некоторые желательные свойства «справедливого» разделения стоимости, возникающего в результате кооперативной игры (в которой игроки образуют коалиции, подобные той, которую мы обсуждали). Он продемонстрировал, что приведенная выше формула была единственным решением, удовлетворяющим аксиомам.

Интуитивный способ представить формулу выглядит следующим образом (благодаря лауреату Нобелевской премии Элвину Э. Роту, получившему премию вместе с Шепли в 2012 году): рассмотрим кооперативную игру с N игроками, как указано выше; нас интересует нахождение SV ϕᵢ(v) игрока i. Предположим, есть комната, и игроки входят в комнату в таком порядке, что все n! заказы N равновероятны. Тогда оказывается, что ϕᵢ(v) — это ожидаемый (в смысле теории вероятностей) предельный вклад игрока i, когда он входит в комнату. Чтобы понять, рассмотрим любую коалицию S, содержащую i, а затем:

(а) Из n! перестановок N, есть (s -1)! различные порядки, в которых первые s -1 игроков могут войти в комнату раньше игрока i.

(b) Затем игрок i входит в комнату.

(c) Количество способов, которыми оставшиеся n-s игроков могут войти в комнату, равно (n-s)!

(d) Таким образом, всего (s — 1)! (н—с)! перестановки, в которых ровно игроки S-i предшествуют i.

(e) Поскольку, как уже упоминалось, все n! расстановки равновероятны, вероятность того, что игрок i войдет в комнату, чтобы найти именно игроков в коалиции S-i уже есть (s-1)! (н-с)! / п!

(f) Поскольку вероятность (s-1)! (н-с)! / п! — вес маргинала [v(S)-v(S-i)] в сумме формулы, мы видим, что SV ϕᵢ(v) действительно является ожидаемым маргинальным вкладом.

SV и машинное обучение (ML): я намерен написать отдельный пост на эту тему. На очень высоком уровне предположим, что у нас есть набор данных, который использовался для подбора модели ML к данным. Что касается SV, мы можем думать так: Особенности = Игроки; Выход модели = созданная стоимость; т. е. функции взаимодействуют для создания выходных данных модели. В частности, каждую «строку» данных можно рассматривать как одну конкретную коалицию. Затем с помощью аппарата SV мы можем описать (точнее, оценить), насколько каждая функция могла повлиять на решение, принятое моделью для этой конкретной строки — это просто SV функции. Например, мы могли бы выяснить, подав в суд анализ на основе SV, что ценность признака человека, имеющего четыре кредитные карты, способствовала + 20% к решению модели об отклонении заявки на кредит этого человека. Этот построчный анализ можно считать локальным; его также можно расширить до глобального анализа, чтобы определить вклад данного признака в решение по всему набору данных. Помимо этого базового представления, применение SV для анализа моделей ML было широко разработано, что привело к различным высокоэффективным сценариям приложений.

Ллойд С. Шепли. Ллойд С. Шепли (1923–2016) внес важный вклад в математическую экономику и, в частности, в теорию игр. Как упоминалось выше, Шепли вместе с Элвином Э. Ротом получил Нобелевскую премию по экономике 2012 года «за теорию стабильного распределения и практику проектирования рынка». Он считается одним из четырех величайших современная теория игр; трое других: Джон фон Нейман, Оскар Моргенштерн и Джон Форбс Нэш-младший (современники Принстонского университета). У Нэша и Шепли был Альберт В. Такер (буква «Т» в условиях KKT из теории математической оптимизации) в качестве научного руководителя. Один интересный анекдот о Шепли заключается в том, что во время службы в армии США во время Второй мировой войны он нарушил советский погодный кодекс, за что получил не только награду «Бронзовая звезда», но и повышение до капрала и прибавку в размере 4 долларов в месяц. Шепли в то время было чуть за двадцать! Данные о погоде, по-видимому, были жизненно важны для планирования бомбардировок с воздуха.

Ссылки:

1. Шепли Л. С., «Ценность для игр с n людьми», Вклад в теорию игр, т. 1, с. 2, Х. Кун и А. В. Такер (редакторы), Принстон: Издательство Принстонского университета, 1953, стр. 307–317.

2. https://statmodeling.stat.columbia.edu/2006/05/01/marginal_and_ma/

3. https://www.nobelprize.org/prizes/economic-sciences/2012/summary/

4. https://en.wikipedia.org/wiki/Shapley%E2%80%93Shubik_power_index