私有热门词

在 TensorFlow.org 上查看 在 Google Colab 中运行 在 GitHub 上查看源代码 下载笔记本

本教程展示了如何使用 tff.analytics.heavy_hitters.iblt.build_iblt_computation API 构建一个联合分析计算，以发现人群中最常见的字符串（私有热门词）。

环境设置

请运行以下命令以确保您的环境已正确设置。如果您没有看到问候语，请参阅 安装 指南以获取说明。

# tensorflow_federated_nightly also bring in tf_nightly, which
# can causes a duplicate tensorboard install, leading to errors.
pip install --quiet tensorflow-text-nightly
pip install --quiet --upgrade tensorflow-federated

import collections

import numpy as np
import tensorflow as tf
import tensorflow_federated as tff
import tensorflow_text as tf_text

np.random.seed(0)
tff.backends.test.set_sync_test_cpp_execution_context()

tff.federated_computation(lambda: 'Hello, World!')()

b'Hello, World!'

背景：联合分析中的私有热门词

考虑以下设置：每个客户端都有一组字符串，每个字符串都来自一个开放集，这意味着它可能是任意的。目标是在联合设置中私下发现最流行的字符串（**热门词**）及其计数。此 colab 演示了使用以下隐私属性解决此问题的解决方案

  • 安全聚合：计算聚合的字符串计数，这样服务器不应该能够了解任何客户端的个体值。有关更多信息，请参阅 tff.federated_secure_sum。
  • 差分隐私 (DP)：一种广泛使用的方法，用于限制和量化分析中敏感数据的隐私泄露。您可以将用户级中心 DP 应用于热门词结果。

安全聚合 API tff.federated_secure_sum 支持整数向量的线性求和。如果字符串来自大小为 n 的封闭集，那么将每个客户端的字符串编码为大小为 n 的向量很容易：让向量中索引 i 处的值为封闭集中第 i 个字符串的计数。然后，您可以安全地将所有客户端的向量求和，以获得整个群体中字符串的计数。但是，如果字符串来自开放集，则不清楚如何将它们正确编码以进行安全求和。在这项工作中，您可以将字符串编码为 可逆布隆查找表 (IBLT)，这是一种概率数据结构，能够以高效的方式对大型（或开放）域中的项目进行编码。IBLT 草图可以线性求和，因此与安全求和兼容。

您可以使用 tff.analytics.heavy_hitters.iblt.build_iblt_computation 创建一个 TFF 计算，将每个客户端的本地字符串编码为 IBLT 结构。这些结构通过加密安全多方计算协议安全地求和到一个聚合的 IBLT 结构中，服务器可以对其进行解码。然后，服务器可以返回前几个热门词。以下部分展示了如何使用此 API 创建一个 TFF 计算并使用莎士比亚数据集运行模拟。

加载和预处理联合莎士比亚数据

莎士比亚数据集包含莎士比亚戏剧中人物的台词。在此示例中，选择了一部分人物（即客户端）。预处理器将每个人物的台词转换为字符串列表，并删除任何仅包含标点符号或符号的字符串。

# Load the simulation data.
source, _ = tff.simulation.datasets.shakespeare.load_data()

# Preprocessing function to tokenize a line into words.
def tokenize(ds):
  """Tokenizes a line into words with alphanum characters."""
  def extract_strings(example):
    return tf.expand_dims(example['snippets'], 0)

  def tokenize_line(line):
    return tf.data.Dataset.from_tensor_slices(tokenizer.tokenize(line)[0])

  def mask_all_symbolic_words(word):
    return tf.math.logical_not(
        tf_text.wordshape(word, tf_text.WordShape.IS_PUNCT_OR_SYMBOL))

  tokenizer = tf_text.WhitespaceTokenizer()
  ds = ds.map(extract_strings)
  ds = ds.flat_map(tokenize_line)
  ds = ds.map(tf_text.case_fold_utf8)
  ds = ds.filter(mask_all_symbolic_words)
  return ds

batch_size = 5

def client_data(n: int) -> tf.data.Dataset:
  return tokenize(source.create_tf_dataset_for_client(
      source.client_ids[n])).batch(batch_size)

# Pick a subset of client devices to participate in the computation.
dataset = [client_data(n) for n in range(10)]

模拟

要运行模拟以发现莎士比亚数据集中最流行的单词（热门词），首先需要使用 tff.analytics.heavy_hitters.iblt.build_iblt_computation API 创建一个 TFF 计算，并使用以下参数

  • capacity：IBLT 草图的容量。此数字应大致等于一轮计算中可能出现的唯一字符串总数。默认为 1000。如果此数字太小，则由于哈希值的冲突，解码可能会失败。如果此数字太大，则会消耗比必要更多的内存。
  • string_max_bytes：IBLT 中字符串的最大长度。默认为 10。必须为正数。长度超过 string_max_bytes 的字符串将被截断。
  • max_words_per_user: 每个客户端允许贡献的最大字符串数量。如果非 None，则必须为正整数。默认为 None，这意味着所有客户端都贡献其所有字符串。
  • max_heavy_hitters: 要返回的最大项目数。如果解码结果中的项目数超过此数，则将按估计计数降序排列并返回前 max_heavy_hitters 个项目。默认为 None，这意味着返回结果中的所有热门项目。
  • secure_sum_bitwidth: 用于安全求和的位宽。默认值为 None，这将禁用安全求和。如果非 None，则必须在 [1,62] 范围内。请参阅 tff.federated_secure_sum。
  • multi_contribution: 每个客户端是否允许贡献多个计数，还是只允许对每个唯一词贡献一个计数。默认为 True。当需要差分隐私时，此参数可以提高效用。
  • batch_size: 数据集每个批次中的元素数量。默认为 1，表示输入数据集由 tf.data.Dataset.batch(1) 处理。必须为正整数。
max_words_per_user = 8
iblt_computation = tff.analytics.heavy_hitters.iblt.build_iblt_computation(
    capacity=100,
    string_max_bytes=20,
    max_words_per_user=max_words_per_user,
    max_heavy_hitters=10,
    secure_sum_bitwidth=32,
    multi_contribution=False,
    batch_size=batch_size)

现在，您可以使用 TFF 计算 iblt_computation 和预处理输入数据集来运行模拟。输出 iblt_computation 包含四个属性

  • clients: 参与计算的客户端数量。
  • heavy_hitters: 聚合热门项目的列表。
  • heavy_hitters_counts: 聚合热门项目计数的列表。
  • num_not_decoded: 未成功解码的字符串数量。
def run_simulation(one_round_computation: tff.Computation, dataset):
  output = one_round_computation(dataset)
  heavy_hitters = output.heavy_hitters
  heavy_hitters_counts = output.heavy_hitters_counts
  heavy_hitters = [word.decode('utf-8', 'ignore') for word in heavy_hitters]

  results = {}
  for index in range(len(heavy_hitters)):
    results[heavy_hitters[index]] = heavy_hitters_counts[index]
  return output.clients, dict(results)

clients, result = run_simulation(iblt_computation, dataset)
print(f'Number of clients participated: {clients}')
print('Discovered heavy hitters and counts:')
print(result)

Number of clients participated: 10
Discovered heavy hitters and counts:
{'to': 8, 'the': 8, 'and': 7, 'you': 4, 'i': 4, 'a': 3, 'he': 3, 'your': 3, 'is': 3, 'of': 2}

具有差分隐私的私有热门项目

为了获得具有中心 DP 的私有热门项目，对开放集直方图应用 DP 机制。其思想是对聚合直方图中字符串的计数添加噪声，然后只保留计数超过一定阈值的字符串。噪声和阈值取决于 (epsilon, delta)-DP 预算，请参阅 此文档 以了解详细的算法和证明。噪声计数作为后处理步骤被四舍五入为整数，这不会削弱 DP 保证。请注意，当需要 DP 时，您将发现更少的热门项目。这是因为阈值步骤过滤掉了计数较低的字符串。

iblt_computation = tff.analytics.heavy_hitters.iblt.build_iblt_computation(
    capacity=100,
    string_max_bytes=20,
    max_words_per_user=max_words_per_user,
    secure_sum_bitwidth=32,
    multi_contribution=False,
    batch_size=batch_size)

clients, result = run_simulation(iblt_computation, dataset)

# DP parameters
eps = 20
delta = 0.01

# Calculating scale for Laplace noise
scale = max_words_per_user / eps

# Calculating the threshold
tau = 1 + (max_words_per_user / eps) * np.log(max_words_per_user / (2 * delta))

result_with_dp = {}
for word in result:
  noised_count = result[word] + np.random.laplace(scale=scale)
  if noised_count >= tau:
    result_with_dp[word] = int(noised_count)
print(f'Discovered heavy hitters and counts with central DP:')
print(result_with_dp)

Discovered heavy hitters and counts with central DP:
{'the': 8, 'you': 4, 'to': 7, 'tear': 3, 'and': 7, 'i': 3}