Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

svfl-0.1.0.tar.gz (5.1 kB view details)

Uploaded Source

Built Distribution

svfl-0.1.0-py3-none-any.whl (4.5 kB view details)

Uploaded Python 3

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

Hashes for svfl-0.1.0.tar.gz
Algorithm Hash digest
SHA256 26d84363082997dd0d92417fca7e63ce363e9498a809679255781f7f54f31d04
MD5 39dae35f3c0a13fb815ec816ce9e9d5b
BLAKE2b-256 a44da04bb685001869d8803ace27c70830ab3343e6d1309c2101be6c8cd0fc89

See more details on using hashes here.

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

Hashes for svfl-0.1.0-py3-none-any.whl
Algorithm Hash digest
SHA256 24685b52dff91029552cc067ee5270f32b5d751c269654bbe4caecf67c72bbfa
MD5 a5397b453994b202442116c4236fb88e
BLAKE2b-256 0a80ad04db451e8cecc2b742f67e4928546b0e1c84301dd8f94d248398661c1c

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page