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 hashes)

Uploaded source

Built Distribution

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

Uploaded py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page