Differentially Private Data-Driven Markov Chain Modeling

Título: Modelagem de Cadeias de Markov Orientada a Dados com Privacidade Diferencial

1. Problema

As cadeias de Markov são ferramentas poderosas para modelar comportamentos de usuários em diversas áreas, como uso doméstico de tempo, padrões de tráfego e navegação na internet. Em cenários orientados a dados, as probabilidades de transição são derivadas de bancos de dados observacionais de comportamento do usuário.

• O Dilema: Gerar modelos precisos requer grandes volumes de dados sensíveis. No entanto, compartilhar os modelos resultantes (matrizes de transição) sem proteções pode revelar informações sensíveis sobre os dados subjacentes ou padrões individuais (ex: comportamento de compras ou ocupação residencial), mesmo em dados agregados.
• O Desafio Técnico: Mecanismos de privacidade padrão, como os de Laplace ou Gaussiana, adicionam ruído com suporte infinito, o que pode fazer com que os vetores de saída deixem de ser estocásticos (soma das entradas igual a 1 e entradas não negativas). Projetar esses vetores de volta para o simplex unitário resulta em baixa precisão. Além disso, a privacidade deve ser garantida nos dados usados para calcular as probabilidades, e não apenas nas próprias probabilidades.

2. Metodologia

Os autores propõem um framework baseado em Privacidade Diferencial (DP) para proteger bancos de dados usados para formular modelos de cadeias de Markov. A abordagem é dividida em duas etapas principais:

A. Privacidade para Vetores Estocásticos (Simplex Unitário)

• Mecanismo Dirichlet Estendido: Os autores estendem o mecanismo Dirichlet (introduzido anteriormente por Gohari et al.) para privatizar consultas de banco de dados cujas saídas são vetores estocásticos.
• Funcionamento: Dado um vetor de contagem sensível $C(D, \rho)$ (que representa a distribuição de categorias em um banco de dados), o mecanismo gera uma saída privada $\tilde{C}$ seguindo uma distribuição Dirichlet centrada em $k \cdot C(D, \rho)$, onde $k$ é um parâmetro de privacidade.
• Garantia de DP: Diferente de trabalhos anteriores que privatizavam elementos do simplex diretamente, este método privatiza o banco de dados subjacente. Eles provam que o mecanismo satisfaz a $(\epsilon, \delta)$-privacidade diferencial convencional (e não apenas probabilística) sob certas suposições de limites inferiores para as entradas do vetor.
• Análise de Precisão: A precisão é quantificada limitando a divergência de Kullback-Leibler (KL) esperada entre o vetor original e o privatizado.

B. Modelagem de Cadeias de Markov (Matrizes Estocásticas)

• Composição Paralela: Uma matriz de transição de Markov é composta por linhas, onde cada linha é um vetor estocástico. O framework aplica o mecanismo Dirichlet a cada linha da matriz de transição individualmente.
• Teorema de Composição: Utilizam uma prova de "composição paralela" para mecanismos $(\epsilon, \delta)$-diferencialmente privados. Isso permite que a matriz completa seja privatizada mantendo a garantia de privacidade global, onde o $\epsilon$ e $\delta$ finais são os máximos dos parâmetros de cada linha.
• Análise de Impacto no Modelo:
  • Comportamento Assintótico: Derivam limites superiores para a mudança na distribuição estacionária ($\pi$) entre o modelo original e o privatizado.
  • Comportamento Transiente: Derivam limites para a mudança no coeficiente de ergodicidade (uma métrica proxy para a taxa de convergência para a distribuição estacionária).
  • Ambos os limites mostram que o erro escala como $O(\log(k^{-1}))$, indicando que pequenas alterações nos parâmetros de privacidade podem melhorar significativamente a precisão.

3. Contribuições Principais

1. Framework de Privatização: Desenvolvimento de um método para privatizar consultas de banco de dados que resultam em vetores estocásticos e matrizes estocásticas, garantindo $(\epsilon, \delta)$-privacidade diferencial.
2. Provas Teóricas:
   • Prova de que o mecanismo Dirichlet estendido é $(\epsilon, \delta)$-diferencialmente privado para consultas de simplex.
   • Limites analíticos para a divergência KL entre vetores privados e não privados.
   • Limites analíticos para a variação na distribuição estacionária e no coeficiente de ergodicidade de cadeias de Markov privatizadas.
3. Validação Empírica: Aplicação do método em dois conjuntos de dados reais:
   • Distribuição de notas de um curso universitário (EUA).
   • Dados de viagens de táxi amarelo em Nova York (NYC Taxi).
4. Análise de Trade-off: Demonstração de que é possível obter alta precisão no modelo mantendo fortes garantias de privacidade.

4. Resultados

• Precisão do Modelo: As simulações mostram que, sob uma implementação típica de privacidade, o método resulta em menos de 2% de erro na distribuição estacionária.
• Dados de Taxis de NYC: Em um conjunto de dados massivo com quase 3 milhões de viagens ($N = 2.933.898$), o modelo privatizado com parâmetros $(\epsilon=3.73, \delta=3 \times 10^{-6})$ manteve uma distância total de variação (TV) média na distribuição estacionária de apenas $0.017$ em comparação com o modelo não privado.
• Divergência KL: Mesmo com privacidade forte ($\epsilon \approx 2.25$), a divergência KL entre as distribuições de notas privatizadas e reais permaneceu baixa (0.103), indicando que o modelo captura fielmente o comportamento do sistema.
• Escalabilidade: O estudo mostrou que a agregação de categorias (ex: combinar zonas de táxi menores) pode melhorar significativamente a privacidade ($\epsilon$ menor) sem sacrificar drasticamente a utilidade do modelo.

5. Significância

Este trabalho é significativo por abordar a lacuna entre a necessidade de dados detalhados para modelagem de Markov e a exigência de privacidade dos usuários.

• Proteção de Dados Subjacentes: Diferente de abordagens anteriores que perturbavam as próprias probabilidades de transição, este método protege o banco de dados bruto, oferecendo privacidade no nível de eventos.
• Viabilidade Prática: Ao provar que é possível gerar modelos de Markov úteis e precisos com garantias rigorosas de privacidade diferencial, o trabalho habilita o uso seguro de dados sensíveis em aplicações críticas como planejamento urbano, otimização de tráfego e sistemas de recomendação.
• Fundamento Teórico: As provas de composição paralela para DP probabilística e os limites de perturbação para distribuições estacionárias fornecem ferramentas teóricas valiosas para pesquisadores que trabalham com privacidade em processos estocásticos.

Em resumo, o artigo estabelece que a modelagem de cadeias de Markov orientada a dados pode ser realizada de forma segura, preservando a utilidade do modelo para análise de sistemas complexos enquanto protege a privacidade individual dos usuários.