A package for computing the average marginal contribution (Shapley Value) for each client in a Federated Learning environment
Project description
ShapleyValueFL
A pip library for computing the marginal contribution (Shapley Value) for each client in a Federated Learning environment.
Table of Content
Brief
The Shapley Value is a game theory concept that explores how to equitably distribute rewards and costs among members of a coalition. It is extensively used in incentive mechanisms for Federated Learning to fairly distribute rewards to clients based on their contribution to the system.
Let $v(S)$ where $S\subset N$ is defined as the contribution of the model collaboratively trained by the subset $S$. $N$ is a set of all the participants in the system. The $i-th$ participant’s Shapley Value $\phi(i)$ is defined as
$$\phi(i) = \sum_{S\subset N \backslash {i}} \frac{|S|!(N-|S|-1)!}{|N|!}(v(S\cup {i}) - v(S))$$
The marginal contribution of the $i-th$ participant is defined as $(v(S \cup {i}) - v(S))$ when they join this coalition.
Let's see this equation in action, consider a Federated Learning environment with three clients, so $N = {0, 1, 2}$. We list the contribution of each subset within this coalition. Let's consider the contribution to be measured in terms of model accuracy.
$v(\emptyset) = 0$ $v({0}) = 40$ $v({1}) = 60$ $v({2}) = 80$
$v({0,1}) = 70$ $v({0,2}) = 75$ $v({1,2}) = 85$
$v({0,1,2}) = 90$
Subset | Client #0 | Client #1 | Client #2 |
---|---|---|---|
$0 \leftarrow 1 \leftarrow 2$ | 40 | 30 | 20 |
$0 \leftarrow 2 \leftarrow 1$ | 40 | 15 | 35 |
$1 \leftarrow 0 \leftarrow 2$ | 10 | 60 | 20 |
$1 \leftarrow 2 \leftarrow 0$ | 5 | 60 | 25 |
$2 \leftarrow 0 \leftarrow 1$ | 0 | 10 | 80 |
$2 \leftarrow 1 \leftarrow 0$ | 5 | 5 | 80 |
$Sum$ | 100 | 180 | 260 |
$\phi(i)$ | 16.67 | 30 | 20 |
The arrow signifies the order in which each client joins the coalition. Consider the first iteration $0 \leftarrow 1 \leftarrow 2$, we calculate the marginal contribution of each client using the above equation.
- Client 0's marginal contribution is given as $v({0}) = 40$.
- Client 1's marginal contribution is given as $v({0, 1}) - v({0}) = 30$.
- Client 2's marginal contribution is given as $v({0, 1, 2}) - v({0, 1}) - v({0}) = 20$.
The marginal contribution is calculated for each permutation likewise, and the Shapley Value is derived by averaging all of these marginal contributions.
Usage
from svfl.svfl import calculate_sv
models = {
"client-id-1" : ModelUpdate(),
"client-id-2" : ModelUpdate(),
"client-id-3" : ModelUpdate(),
}
def evaluate_model(model):
# function to compute evaluation metric, ex: accuracy, precision
return metric
def fed_avg(models):
# function to merge the model updates into one model for evaluation, ex: FedAvg, FedProx
return model
# returns a key value pair with the client identifier and it's respective Shapley Value
contribution_measure = calculate_sv(models, evaluate_model, fed_avg)
Future Work
- Built-in support for standard averaging methods like FedAvg, & FedProx.
Feedback
Any feedback/corrections/additions are welcome:
If this was helpful, please leave a star on the github page.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file svfl-0.1.0.tar.gz
.
File metadata
- Download URL: svfl-0.1.0.tar.gz
- Upload date:
- Size: 5.1 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.0 CPython/3.9.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 |
26d84363082997dd0d92417fca7e63ce363e9498a809679255781f7f54f31d04
|
|
MD5 |
39dae35f3c0a13fb815ec816ce9e9d5b
|
|
BLAKE2b-256 |
a44da04bb685001869d8803ace27c70830ab3343e6d1309c2101be6c8cd0fc89
|
File details
Details for the file svfl-0.1.0-py3-none-any.whl
.
File metadata
- Download URL: svfl-0.1.0-py3-none-any.whl
- Upload date:
- Size: 4.5 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.0 CPython/3.9.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 |
24685b52dff91029552cc067ee5270f32b5d751c269654bbe4caecf67c72bbfa
|
|
MD5 |
a5397b453994b202442116c4236fb88e
|
|
BLAKE2b-256 |
0a80ad04db451e8cecc2b742f67e4928546b0e1c84301dd8f94d248398661c1c
|