Shapley values, worked by hand

A three-input example small enough to check on paper, and what it shows about splitting a model's output among its inputs.

Glassforge AI

Sample post. It ships with the site to show what a post can do. Replace or delete it before launch.

A credit model gives an applicant a score. The next question is always the same: which inputs moved it, and by how much? Shapley values are one answer. The idea is much easier to trust once you have computed a few yourself, so this post does exactly that.

The setup

Take a model with three inputs, A, B and C. Write v(S)v(S) for the model’s output when only the inputs in the set SS are known.

Suppose the model behaves like this:

Inputs knownOutput
none0
A10
B20
C0
A, B40
A, C10
B, C30
A, B, C60

A alone is worth 10 and B alone is worth 20, but together they are worth 40. The inputs interact, so there is no single obvious way to say what A is worth.

The rule

Shapley’s rule is to add the inputs one at a time, in every possible order, and record how much the output changes when each input arrives. An input’s Shapley value is its average change across all the orders.

Written out, for input ii among nn inputs:

ϕi(v)=∑S⊆N∖{i}∣S∣! (n−∣S∣−1)!n! (v(S∪{i})−v(S))\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(n-|S|-1)!}{n!}\,\bigl(v(S \cup \{i\}) - v(S)\bigr)

The fraction counts how many orders have exactly the inputs in SS arriving before ii. Everything else is the change ii causes when it joins them.

By hand

Three inputs can arrive in six orders. For each order, here is the change each input causes when it arrives:

OrderABC
A, B, C103020
A, C, B10500
B, A, C202020
B, C, A302010
C, A, B10500
C, B, A30300
Average18.3333.338.33
Each input's share of the full output of 60. The shares add up exactly, with nothing left over.

Two things are worth noticing.

First, the three values add up to 60, which is the full output. This always happens:

∑iϕi(v)=v(N)−v(∅)\sum_{i} \phi_i(v) = v(N) - v(\varnothing)

Every point of the score is assigned to some input and nothing is left over. That is the property that makes Shapley values usable as an explanation.

Second, C is worth nothing on its own, yet its Shapley value is 8.33. C only matters in combination with the others, and the averaging gives it credit for that.

In code

The same calculation in a few lines of Python:

from itertools import permutations

v = {
    frozenset(): 0,
    frozenset("A"): 10,
    frozenset("B"): 20,
    frozenset("C"): 0,
    frozenset("AB"): 40,
    frozenset("AC"): 10,
    frozenset("BC"): 30,
    frozenset("ABC"): 60,
}

def shapley(players, v):
    orders = list(permutations(players))
    totals = dict.fromkeys(players, 0.0)
    for order in orders:
        seen = frozenset()
        for p in order:
            totals[p] += v[seen | {p}] - v[seen]
            seen = seen | {p}
    return {p: round(total / len(orders), 2) for p, total in totals.items()}

print(shapley("ABC", v))
# {'A': 18.33, 'B': 33.33, 'C': 8.33}

Why this gets hard

Three inputs mean 6 orders and 8 rows in the table. Thirty inputs mean 2302^{30} rows, a little over a billion, and 30!30! orders, about 2.65×10322.65 \times 10^{32}. A real credit model has hundreds of inputs, so nobody computes Shapley values this way. Every practical method approximates, either by sampling orders or by using the structure of the model.

An approximation is only as trustworthy as your ability to check it. That is the reason to keep a small example with an exact answer close at hand.