shapley-value-for-circuit 0.1.0

Polynomial circuit-local Shapley attribution for single boolean circuit samples.

shapley-value-for-circuit

Polynomial circuit-local Shapley attribution for a single boolean circuit sample.

This package uses circuit-static-description to load, parse, and validate circuits. Given a circuit, a complete input sample, and one output index, it returns the attribution of that output to each original input.

Installation

pip install -e .

For development and tests:

pip install -e .[test]
pytest

Quick Start

from circuit_static_description import Circuit
from shapley_value_for_circuit import explain, shapley_values

circuit = Circuit(
    2, # number of input
    1, # number of output
    outputs=["AND(I0, I1)"],
)

result = explain(circuit, inputs=[1, 1], output=0)

print(result.values)
# Attribution for each original input:
# I0 contributes 1/2, and I1 contributes 1/2.
# (Fraction(1, 2), Fraction(1, 2))

print(result.base_value, result.output_value)
# The target output is 0 on the all-zero baseline input,
# and 1 on the current input [1, 1].
# 0 1

print(shapley_values(circuit, [1, 1], as_float=True))
# Same attributions returned as floats.
# [0.5, 0.5]

You can also pass circuit text in the circuit-static-description format:

from shapley_value_for_circuit import explain

text = """
INPUTS 3
OUTPUTS 1
V0 = AND(I0, I1)
OUT0 = OR(V0, I2)
"""

result = explain(text, inputs=[1, 1, 0], output="OUT0")
print(result.values)
# I0 and I1 explain V0 = AND(I0, I1).
# I2 is unchanged from the baseline, so its contribution is 0.
# (Fraction(1, 2), Fraction(1, 2), Fraction(0, 1))

Intuition

The circuit output is boolean, so result.base_value and result.output_value are always either 0 or 1. The attribution values are not restricted to booleans: they explain how the output changed from the baseline sample to the current sample.

With the default all-zero baseline, AND(I0, I1) on input [1, 1] gives:

base_value = 0
# Output of AND(0, 0) on the all-zero baseline input.

output_value = 1
# Output of AND(1, 1) on the current input.

values = [1 / 2, 1 / 2]
# I0 contributes 1/2.
# I1 contributes 1/2.

base_value + sum(values) == output_value
# 0 + 1/2 + 1/2 == 1

Both inputs are needed to turn the output on, so the local credit is split equally.

OR(I0, I1) on input [1, 1] also gives:

base_value = 0
# Output of OR(0, 0) on the all-zero baseline input.

output_value = 1
# Output of OR(1, 1) on the current input.

values = [1 / 2, 1 / 2]
# I0 contributes 1/2.
# I1 contributes 1/2.

Either input would be enough by itself, so the redundant positive effect is split between them.

AND(I0, I1) on input [1, 0] gives:

base_value = 0
# Output of AND(0, 0) on the all-zero baseline input.

output_value = 0
# Output of AND(1, 0) on the current input.

values = [0, 0]
# I0 changed from 0 to 1, but the target output stayed 0.
# I1 stayed at 0.

The first input changed, but the requested output did not change from the baseline, so there is no output change to attribute.

NOT(I0) on input [1] gives:

base_value = 1
# Output of NOT(0) on the all-zero baseline input.

output_value = 0
# Output of NOT(1) on the current input.

values = [-1]
# I0 contributes -1 because changing I0 from 0 to 1 turns the output off.

base_value + sum(values) == output_value
# 1 + (-1) == 0

The input change turns the output off, so the attribution is negative.

API

explain(circuit, inputs, output=0, *, baseline_inputs=None) -> ShapleyResult

circuit may be one of:

• circuit_static_description.Circuit
• circuit text
• a circuit file path

baseline_inputs is the reference sample. By default, it is the all-zero input. You can also pass one boolean value for all inputs, or a sequence with the same length as the circuit input count.

shapley_values(circuit, inputs, output=0, *, baseline_inputs=None, as_float=False)
calculate_shapley_values(...)  # Alias for shapley_values.

Useful ShapleyResult fields:

• values: one attribution per input, represented exactly as fractions.Fraction
• output_value: output value for the current sample
• base_value: output value for the baseline sample
• input_values: normalized current sample inputs
• baseline_input_values: normalized baseline inputs

The result always satisfies:

result.base_value + sum(result.values) == result.output_value

Algorithm

This package computes circuit-local Shapley propagation. It does not enumerate all input subsets and does not compute the exponential global Shapley value.

The algorithm is:

1. Each original input starts with its change from the baseline.
2. Each logic gate is explained by the exact Shapley values of its unary or binary local game.
3. Each gate-level attribution is propagated through the upstream attribution vectors until it reaches the original inputs.

Supported circuit-static-description gates:

• AND
• OR
• NOT
• XOR
• NAND
• NOR

The runtime is polynomial. If n is the input count and g is the number of gates and variables reachable from the requested output, the dense worst case is approximately O(g * n), because each intermediate node may carry an attribution vector over all original inputs. Sparse cases are usually smaller.