private_heavy_hitters.ipynb

Kernel: Python 3

Copyright 2022 The TensorFlow Authors.

#@title Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

Heavy Hitters privados

Ver en TensorFlow.org

Ejecutar en Google Colab

Ver fuente en GitHub

Descargar el bloc de notas

NOTA: Se ha verificado que esta colaboración funciona con la última versión publicada del paquete pip tensorflow_federated. Es posible que esta colaboración no se actualice para funcionar con main.

Este tutorial muestra cómo usar la API tff.analytics.heavy_hitters.iblt.build_iblt_computation para crear un cálculo analítico federado para descubrir las cadenas más frecuentes (heavy hitters privados) en la población.

Configuración del entorno

Ejecute lo que se encuentra a continuación, para asegurarse de que el entorno esté preparado correctamente. Si no ve un mensaje de inicio, consulte la guía de instalación para acceder a las instrucciones.

#@test {"skip": true}

# 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!'

Antecedentes: Heavy Hitters ​​privados en el análisis federado

Considere la siguiente configuración: cada cliente tiene una lista de cadenas y cada cadena pertenece a un conjunto abierto, lo que significa que podría ser arbitraria. El objetivo es descubrir las cadenas más populares (Heavy Hitters) y sus recuentos de forma privada en un entorno federado. Esta colaboración demuestra una solución a este problema con las siguientes propiedades de privacidad:

• Agregación segura: calcula los recuentos de las cadenas agregadas de modo que el servidor no pueda conocer el valor individual de ningún cliente. Consulte tff.federated_secure_sum para obtener más información.

• Privacidad diferencial (DP): método ampliamente utilizado para delimitar y cuantificar la fuga de privacidad de datos confidenciales que se produce durante el análisis. Puede aplicar DP central a nivel de usuario a los resultados de Heavy Hitters.

La API de agregación segura tff.federated_secure_sum admite sumas lineales de vectores enteros. Si las cadenas son de un conjunto cerrado de tamaño n, entonces es fácil codificar las cadenas de cada cliente en un vector de tamaño n: sea el valor en el índice i del vector el recuento de la i ^-ésima cadena en el conjunto cerrado. Luego puede sumar de forma segura los vectores de todos los clientes para obtener el recuento de cadenas en toda la población. Sin embargo, si las cadenas pertenecen a un conjunto abierto, no resulta obvio cómo codificarlas correctamente para obtener una suma segura. En este trabajo, puede codificar las cadenas en tablas de búsqueda invertibles de Bloom (IBLT), que es una estructura de datos probabilística que tiene la capacidad de codificar elementos en un dominio grande (o abierto) de una manera eficiente. Los esquemas de IBLT se pueden sumar linealmente, por lo que son compatibles con la suma segura.

Puede usar tff.analytics.heavy_hitters.iblt.build_iblt_computation para crear un cálculo de TFF que codifique las cadenas locales de cada cliente en una estructura de IBLT. Estas estructuras se suman de forma segura a través de un protocolo criptográfico seguro de cálculo multipartito en una estructura de IBLT agregada que el servidor puede decodificar. Luego de esto, el servidor puede devolver a los Heavy Hitters. Las siguientes secciones muestran cómo se usa esta API para crear un cálculo de TFF y ejecutar simulaciones con el conjunto de datos de Shakespeare.

Carga y procesamiento previo de los datos federados de Shakespeare

El conjunto de datos de Shakespeare contiene líneas de personajes de obras de Shakespeare. En este ejemplo, se selecciona un subconjunto de caracteres (es decir, clientes). Un preprocesador convierte las líneas de cada personaje en una lista de cadenas y se eliminan todas las cadenas que solo contengan puntuación o símbolos.

# 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)]

Simulaciones

Para ejecutar simulaciones con el fin de descubrir las palabras más populares (heavy hitters) en el conjunto de datos de Shakespeare, primero debemos crear un cálculo de TFF a partir de la API tff.analytics.heavy_hitters.iblt.build_iblt_computation con los siguientes parámetros:

• capacity: la capacidad del esquema de IBLT. Este número debería ser aproximadamente el número total de cadenas únicas que podrían aparecer en una ronda de cálculo. El valor predeterminado es 1000. Si este número es demasiado pequeño, la decodificación podría fallar a causa de una colisión de valores hash. Si este número fuera demasiado grande, consumiría más memoria de la necesaria.

• string_max_bytes: la longitud máxima de una cadena en la IBLT. El valor predeterminado es 10. Debe ser positivo. Las cadenas más largas que string_max_bytes se truncarán.

• max_words_per_user: el número máximo de cadenas que cada cliente puede contribuir. Si no es None, debe ser un número entero positivo. El valor predeterminado es None, lo que significa que todos los clientes contribuyen con todas sus cadenas.

• max_heavy_hitters: el número máximo de elementos que se devolverán. Si los elementos decodificados superan este número, se ordenarán de forma decreciente según los recuentos estimados y se devolverán los elementos max_heavy_hitters principales. El valor predeterminado es None, lo que significa devolver todos los heavy hitters ​​del resultado.

• secure_sum_bitwidth: el ancho de bits que se usa para obtener una suma segura. El valor predeterminado es None, que deshabilita la suma segura. Si no es None, debe estar en el rango [1,62]. Consulte tff.federated_secure_sum.

• multi_contribution: si a cada cliente se le permita contribuir con múltiples recuentos o solo con uno para cada palabra única. El valor predeterminado es True. Este argumento podría mejorar la utilidad cuando se requiere privacidad diferencial.

• batch_size: el número de elementos en cada lote del conjunto de datos. El valor predeterminado es 1, lo que significa que el conjunto de datos de entrada es procesado por tf.data.Dataset.batch(1). Debe ser un número entero positivo.

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)

Ahora tiene todo listo para ejecutar simulaciones con el cálculo de TFF iblt_computation y el conjunto de datos de entrada de preprocesamiento. La salida de iblt_computation tiene cuatro atributos:

• clients: un número escalar de clientes que participaron en el cálculo.

• heavy_hitters: una lista de heavy hitters ​​agregados.

• heavy_hitters_counts: una lista de los recuentos de heavy hitters agregados.

• num_not_decoded: un número escalar de cadenas que no se decodifican correctamente.

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}

Heavy Hitters privados con privacidad diferencial

Para obtener Heavy Hitters ​​privados con DP central, se aplica un mecanismo de DP para histogramas de conjunto abierto. La idea es agregar ruido a los recuentos de cadenas en el histograma agregado y luego conservar solo las cadenas con recuentos que se sitúen por encima de un umbral específico. El ruido y el umbral dependen del presupuesto (épsilon, delta)-DP; consulte este documento para obtener pruebas y algoritmos detallados. Los recuentos ruidosos se redondean a números enteros como paso de posprocesamiento, lo que no debilita la garantía de DP. Tenga en cuenta que descubrirá heavy hitters menos importantes ​​cuando la DP sea un requisito. Esto se debe a que el paso de umbral filtra las cadenas con recuentos bajos.

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}