Metadata-Version: 2.4
Name: shapley-value-for-circuit
Version: 0.1.0
Summary: Polynomial circuit-local Shapley attribution for single boolean circuit samples.
Author-email: GGN_2015 <neko@jlulug.org>
License: MIT
License-File: LICENSE
Requires-Python: >=3.10
Requires-Dist: circuit-static-description<0.2,>=0.1.9
Provides-Extra: test
Requires-Dist: pytest>=8; extra == 'test'
Description-Content-Type: text/markdown

# shapley-value-for-circuit

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

This package uses
[`circuit-static-description`](https://pypi.org/project/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

```bash
pip install -e .
```

For development and tests:

```bash
pip install -e .[test]
pytest
```

## Quick Start

```python
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:

```python
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:

```python
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:

```python
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:

```python
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:

```python
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

```python
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.

```python
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:

```python
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.
