📊 statistics

A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

Este artigo propõe uma implementação de privacidade diferencial de alta entropia que satisfaz invariantes de agregação linear obrigatórios (como totais de estado) com quase certeza, ao mesmo tempo em que deriva novas garantias de privacidade e aborda questões teóricas relativas ao espaço nulo de matrizes de correlação.

Autores originais: Ryan Lafferty, Anindya Roy

Publicado 2026-07-27

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Ryan Lafferty, Anindya Roy

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um bibliotecário tentando compartilhar uma lista secreta de leitores de livros com o público, mas tem uma promessa rigorosa: você nunca deve revelar quem pegou emprestado um livro específico. Para manter essa promessa, você decide adicionar um pouco de "estática" ou ruído à lista, como adicionar alguns nomes aleatórios que não estavam lá ou mudar ligeiramente alguns nomes. Esta é a ideia central da Privacidade Diferencial, um escudo matemático usado por governos e gigantes da tecnologia para nos permitir aprender com os dados sem expor indivíduos.

No entanto, há um porém. Às vezes, as regras do jogo exigem que certos números macro permaneçam exatamente iguais. Por exemplo, o número total de pessoas em um estado deve corresponder à soma das pessoas em todos os seus condados. Se você apenas adicionar ruído aleatório à contagem de cada condado, o total do estado provavelmente irá desviar, quebrando a matemática e tornando os dados inúteis para registros oficiais. Isso cria um cabo de guerra: você quer adicionar ruído suficiente para esconder indivíduos, mas também precisa que o ruído se cancele perfeitamente para que os totais macro permaneçam intocados. Este artigo aborda a matemática complexa de como adicionar esse ruído de "cancelamento perfeito" sem quebrar o escudo de privacidade.

O Enigma do Ruído Perfeitamente Equilibrado

Imagine que você é um chef tentando assar um bolo para um juiz muito exigente. O juiz tem duas regras:

A Regra do Sabor: Cada mordida do bolo deve ter exatamente o sabor de um sabor específico (digamos, baunilha) para garantir que a receita seja seguida.
A Regra do Peso: O peso total do bolo deve ser exatamente 1.000 gramas. Nem mais, nem menos.

Agora, imagine que você está adicionando "ingredientes secretos" (ruído) à massa para proteger a origem da receita. Se você apenas polvilhar um punhado de favas de baunilha em cada tigela aleatoriamente, o peso total do bolo provavelmente estará errado. Você pode acabar com 1.005 gramas ou 990 gramas. Se você tentar corrigir o peso apenas subtraindo os gramas extras do topo, você arruína a "Regra do Sabor" porque a camada superior agora terá um sabor diferente do restante.

Este é o problema exato que os autores, Ryan Lafferty e Anindya Roy, estão resolvendo. No mundo dos dados, o "bolo" é um banco de dados (como o Censo dos EUA), as "mordidas" são pontos de dados individuais (como a contagem de uma pessoa em um bairro) e os "ingredientes secretos" são os números aleatórios adicionados para esconder identidades. A "Regra do Peso" representa invariantes lineares — restrições como "a população total de um estado deve ser igual à soma de seus condados".

O Jeito Antigo vs. O Jeito Novo

Anteriormente, os cientistas de dados tentavam resolver isso adicionando ruído primeiro e depois "corrigindo" os totais posteriormente. Eles adicionavam números aleatórios a cada condado, viam que o total do estado estava incorreto e então ajustavam os números para forçar o total de volta ao valor correto.

Os autores argumentam que essa abordagem de "consertar depois" é como tentar alisar um papel amassado pressionando-o com um livro pesado. Ele pode parecer plano, mas o papel agora está esmagado e distorcido. Em termos matemáticos, este método de "projeção" espreme o ruído em um canto, tornando-o menos aleatório (menor entropia) e potencialmente enfraquecendo as garantias de privacidade. É como se o ruído se tornasse previsível, o que é ruim para a privacidade.

A Solução de "Máxima Entropia"

Em vez de consertar a bagunça depois do fato, os autores propõem uma maneira mais inteligente de misturar os ingredientes desde o início. Eles desenvolveram um método para gerar ruído que é correlacionado.

Pense nisso como uma equipe de dançarinos. Se cada dançarino se mover aleatoriamente, o grupo parece caótico, mas o centro do grupo pode se deslocar. Se você quer que o grupo permaneça em um lugar (o invariante), você não pode simplesmente dizer a eles para pararem de se mover. Em vez disso, você os coreografa para que, quando um dançarino der um passo à frente, outro dê um passo atrás exatamente na mesma medida. Eles estão se movendo juntos, mas seus movimentos estão interligados para que o grupo permaneça no lugar.

O artigo propõe uma implementação de "Máxima Entropia". Em termos simples, "entropia" é uma medida de aleatoriedade ou surpresa. Os autores querem que o ruído seja o mais imprevisível e "surpreendente" possível (alta entropia), enquanto ainda obedece à regra de que a soma total é zero. Eles usam uma ferramenta matemática chamada Gradiente Descendente Projetado (uma forma sofisticada de dizer "ajustar iterativamente os passos da dança") para encontrar a coreografia perfeita.

Eles também usam uma técnica chamada POCS (Projeção em Conjuntos Convexos), que é como um jogo de "quente ou frio" onde você continua ajustando o ruído até que ele se encaixe perfeitamente dentro de uma forma definida pelas regras. O resultado é um vetor de ruído que:

Parece o ruído padrão que esperamos (Gaussiano ou Laplace) para cada dado individual;
Soma exatamente zero (ou o invariante necessário) todas as vezes;
É o mais aleatório possível matematicamente, garantindo a proteção de privacidade mais forte.

O Que Eles Descobriram e Provaram

Os autores não apenas supuseram que isso funcionaria; eles provaram.

A Garantia: Eles mostraram que, mesmo com este ruído complexo e interligado, o sistema ainda fornece a garantia matemática padrão de Privacidade Diferencial (especificamente, $(\epsilon, \delta)$ -DP). Isso significa que o escudo de privacidade é tão forte quanto os métodos antigos e mais simples, embora o ruído agora esteja "dançando" de forma coordenada.
A Magia Matemática: Uma grande parte do trabalho deles envolveu resolver um enigma difícil sobre matrizes de correlação (grades matemáticas que descrevem como as variáveis se relacionam). Eles forneceram uma solução parcial para uma questão aberta sobre o "espaço nulo" dessas matrizes — essencialmente descobrindo quais padrões de ruído interligado são possíveis.
A Simulação: Eles testaram seu método com dados simulados, incluindo um cenário que mimetiza o Censo dos EUA com estados, condados e blocos. Eles mostraram que, ao adicionar ruído aos blocos menores, os totais de condados e estados permaneceram perfeitamente intactos, enquanto as contagens dos blocos individuais ainda eram suficientemente obscurecidas para proteger a privacidade.

Por Que Isso Importa

Isso não é apenas um jogo teórico. O Departamento do Censo dos EUA e outras agências enfrentam exatamente este problema toda vez que liberam dados. Eles têm mandatos constitucionais que dizem que os totais dos estados não podem ser alterados, mas também precisam proteger a privacidade de cada pessoa.

O método dos autores oferece uma maneira "principiada" de fazer isso. Em vez de hackear os dados após o fato, eles fornecem uma maneira de gerar os dados corretamente desde o início. Eles também observaram que esta abordagem poderia ser útil para outros tipos de dados, como leituras de medidores inteligentes (onde o uso total de energia de um bairro deve corresponder à soma das casas individuais) ou dados de dispositivos vestíveis (wearables).

Em resumo, o artigo mostra que você não precisa escolher entre totais precisos e privacidade forte. Ao usar um pouco de matemática avançada para coreografar o ruído, você pode ter ambos: um conjunto de dados que é perfeitamente consistente com as grandes regras, mas completamente seguro para os pequenos detalhes.

Resumo Técnico: Uma Implementação de Máxima Entropia de Privacidade Diferencial sob Invariantes Lineares

Enunciado do Problema
A privacidade diferencial (DP) é o padrão para a privacidade de dados, tipicamente implementada pela adição de ruído Gaussiano ou Laplace independente às consultas de banco de dados. No entanto, em aplicações como o Censo Decenal dos EUA, certas consultas agregadas (ex: totais populacionais em nível estadual) estão sujeitas a "invariantes" — restrições lineares determinadas por lei ou política que não podem ser perturbadas. Mecanismos de DP padrão, que adicionam ruído independente, violam essas restrições porque a soma de termos de ruído independentes raramente é zero.

Embora existam técnicas de pós-processamento para forçar os agregados a corresponderem aos invariantes, tais métodos alteram a distribuição do ruído, potencialmente modificando as garantias de privacidade e a interpretação do mecanismo de DP. Além disso, projetar o ruído não restrito no espaço dos invariantes frequentemente resulta em uma solução com menor entropia, reduzindo a utilidade dos dados liberados. O desafio central é projetar um mecanismo de adição de ruído que:

Mantenha as distribuições marginais especificadas (ex: Laplace ou Gaussiana) no nível granular.
Satisfaça as restrições de agregação linear (invariantes) com probabilidade um.
Maximize a entropia do vetor de ruído dentro do subespaço restrito para garantir que o ruído seja o mais "independente possível", dadas as restrições.

Metodologia
Os autores propõem um mecanismo de Privacidade Diferencial de Agregação Invariante (AI-DP). A abordagem trata tanto o ruído Gaussiano quanto o Laplace como misturas de escala de distribuições normais. A metodologia procede em três estágios principais:

Formalização do Universo de Dados Invariante:
Os autores redefinem a estrutura do banco de dados vizinho para garantias de DP. Em vez da troca de entrada única padrão, bancos de dados vizinhos no universo invariante ( $D_{Q,A,c}$ ) devem diferir de uma forma que preserve as restrições lineares $AQ(D) = c$. Isso geralmente requer a troca de múltiplas entradas simultaneamente. As garantias de privacidade são então avaliadas dentro deste universo restrito.
Construção da Matriz de Correlação via POCS:
Para satisfazer as restrições $AX = 0$ enquanto mantém marginais específicas, o vetor de ruído $X$ é modelado como uma normal multivariada $N(0, \Sigma)$ onde $\Sigma = DRD$ . Aqui, $D$ é uma matriz diagonal de escalas (derivada da distribuição de mistura) e $R$ é uma matriz de correlação satisfazendo $RB = 0$ (onde $B = AD$).
Encontrar tal $R$ é formulado como um Problema de Viabilidade Convexa (CFP): encontrar uma matriz na interseção de três conjuntos convexos:

$C_1$ : O cone de matrizes semidefinidas positivas.
$C_2$ : O subespaço afim de matrizes com entradas diagonais unitárias (matrizes de correlação).
$C_3$ : O subespaço de matrizes onde $RB = 0$.
Os autores empregam o algoritmo de Projeção Cíclica sobre Conjuntos Convexos (POCS) para encontrar uma solução $R$ nesta interseção.

Otimização de Máxima Entropia:
A solução POCS fornece uma matriz de correlação válida, mas não garante máxima entropia. Para satisfazer o requisito [R3] de maximizar a entropia, os autores formulam um problema de otimização:
$R_{opt} = \min_{R \in C_n} \left[ \text{Tr}(B^T R B) - \tau \log \det(K^T R K) \right]$
onde o primeiro termo impõe a restrição (idealmente zero) e o segundo termo (com parâmetro de ajuste $\tau$ ) penaliza a baixa entropia. Isso é resolvido usando um Algoritmo de Gradiente Projetado.

Principais Contribuições

Garantias Teóricas de Privacidade: O artigo deriva garantias de $(\epsilon, \delta)$ -DP para o mecanismo proposto sob o universo de dados invariante. Prova-se que o mecanismo satisfaz essas garantias para bancos de dados que diferem por entradas que preservam os invariantes.
Teoria de Matrizes de Correlação: O trabalho contribui com novos resultados para a literatura sobre matrizes de correlação, especificamente em relação ao espaço nulo de matrizes de correlação.
- Fornece uma condição necessária e suficiente para a existência de uma matriz de correlação $R$ tal que $RB=0$ para uma matriz de restrição de posto- $k$ .
- Caracteriza o conjunto de soluções como faces do eliptóide (o conjunto de matrizes de correlação) e identifica a solução de posto máximo como residindo no interior relativo deste conjunto.
Estrutura Algorítmica: O artigo apresenta um algoritmo prático (Algoritmo 1 e 2) para amostrar ruído de misturas de escalas de normais sob restrições de igualdade linear, utilizando POCS e gradiente descendente projetado.
Tratamento de Restrições Hierárquicas: A metodologia mostra-se adaptável a estruturas hierárquicas aninhadas (ex: blocos $\to$ condados $\to$ estados), garantindo consistência em todos os níveis enquanto preserva os invariantes de nível superior.

Resultos

Ilustrações Numéricas:
- Agregação Simples: Para o caso em que o vetor de restrição é um vetor de uns (somando um total), os autores mostram que uma matriz de correção intraclasse específica (posto $n-1$ ) é a solução única de máximo posto e máxima entropia, eliminando a necessidade de otimização iterativa neste caso específico.
- Mecanismo de Laplace: Ao representar o ruído Laplace como uma mistura de escala Gaussiana, os autores geraram com sucesso 100 amostras de ruído com distribuição Laplace satisfazendo uma única restrição linear. Os gráficos Q-Q confirmaram a distribuição marginal, e as violações de restrição foram insignificantes (ordem de $10^{-6}$ ).
- Convergência: O algoritmo de gradiente projetado demonstrou convergência na minimização da função de perda enquanto mantinha o termo de penalidade para entropia.
Probabilidade de Violação: O artigo analisa a probabilidade de um vetor de restrição aleatório não ser "balanceado" (uma condição necessária para a existência de uma matriz de correlação nula). Fornece um limite de cauda mostrando que, para vetores com entradas de cauda pesada, a probabilidade de inviabilidade é exponencialmente pequena.

Significância e Alegações
Os autores alegam que este trabalho fornece uma maneira fundamentada de abordar restrições de agregação na implementação de DP sem sacrificar a interpretação padrão de privacidade diferencial. Ao garantir que o vetor de ruído tenha máxima entropia dentro das restrições, o método minimiza a distorção das propriedades estatísticas dos dados além do necessário para satisfazer os invariantes.

O artigo afirma explicitamente que contribui para a discussão sobre como analisar dados liberados e interpretar a semântica de DP na presença de invariantes, uma lacuna identificada na literatura anterior de implementação de censo (Abowd et al., 2022). A metodologia é apresentada como tendo utilidade geral além dos dados do censo, aplicável a qualquer cenário envolvendo amostragem de modelos de mistura normal sob restrições de igualdade linear, como dados de medidores inteligentes e dispositivos vestíveis (wearables).

Os autores mantêm-se modestos quanto ao escopo, observando que o trabalho atual foca em restrições de igualdade linear e que trabalhos futuros são necessários para abordar sistemas mais gerais de igualdade e desigualdade linear (ex: não-negatividade). Eles também notam que a prova teórica relativa ao espaço nulo de matrizes de correlação é uma solução parcial para uma questão aberta nesse campo.

O Enigma do Ruído Perfeitamente Equilibrado

O Jeito Antigo vs. O Jeito Novo

A Solução de "Máxima Entropia"

O Que Eles Descobriram e Provaram

Por Que Isso Importa

Mais como este