Differential Privacy for Markov Chain State Trajectories

기술 요약: 마르코프 체인 상태 궤적을 위한 차분 프라이버시

문제 정의
데이터 기반 시스템은 신용 위험 전이, 도시 교통 패턴, 인터넷 브라우징과 같은 행동을 모델링하기 위해 마르코프 체인에 의해 생성된 상태 궤적에 자주 의존한다. 이러한 궤적은 유용하지만, 이를 공유하는 것은 심각한 프라이버시 위험을 초래하며, 짧은 시퀀스는 종종 사용자의 신원을 재구성하는 데 사용될 수 있다. 마르코프 체인 궤적을 비결정론적 유한 상태 오토마타로 취급하여 전이 확률을 무시하고 균등 무작위 보행(uniform random walks)을 통해 프라이빗 상태를 선택하는 기존 방식은, 마르코프 체인의 기저 구조적 특성을 결여한 "비전형적인(atypical)" 궤적을 생성하여 하위 분석을 위한 프라이빗 데이터의 효용성을 저하시키는 경우가 많다. 또한, 이전 연구들은 궤적을 오프라인으로 프라이버시 처리하거나 구조적 유사성을 유지하기 위해 특정 전이 역학을 활용하지 못하는 경우가 많다.

방법론
저자들은 민감한 궤적과 동시에 프라이빗 궤적이 생성되는 온라인 방식의 $\epsilon$-차분 프라이빗 상태 궤적 생성 프레임워크를 제안한다. 이 방법론의 핵심은 마르코프 체인을 에지 가중치가 전이 확률의 음의 로그($W_{ij} = -\log(P_{ij})$)인 가중치 유향 그래프로 취급하는 것이다.

1. 그래프 유도 및 거리: 저자들은 이 그래프에서 최단 경로 거리 $G(i, j)$를 정의한다. 명제 1은 이 그래프에서의 최단 경로가 마르코프 체인에서 두 상태 사이의 가장 가능성 높은 경로와 일치함을 입증한다.
2. 인접성 정의: 새로운 궤적 인접성 개념이 도입된다 (정의 4). 두 궤적은 대응하는 상태들 간의 대칭 최단 경로 거리의 합이 파라미터 $\rho$에 의해 제한될 때 인접한 것으로 간주된다. 이는 해밍 거리(차이가 있는 항목을 세는 방식)에 의존하는 이전 연구와 달리, 전이의 가능성에 기반하여 유사성을 더 미묘하게 정의할 수 있게 한다.
3. 메커니즘 설계 (Mechanism 1): 제안된 메커니즘은 permute-and-flip 메커니즘에서 영감을 얻어 온라인으로 프라이빗 상태를 생성한다. 각 시간 단계 $t$에서, 이전 프라이빗 상태 $s'_{t-1}$와 현재 민감한 상태 $s_t$가 주어지면, 메커니즘은 가용 이웃 $N(s'_{t-1})$ 내에서 다음 프라이빗 상태 $s'_t$를 선택한다. 선택 확률은 유틸리티 함수 $u(w, w') = -\sum G(s'_t, s_t)$에 의해 편향되며, 이는 그래프 거리 측면에서 실제 상태로부터 멀리 떨어진 상태에 페널티를 부여한다.
4. 드리프트 분석: 저자들은 민감한 상태와 프라이빗 상태의 결합 과정을 은닉 마르코프 모델로 모델링한다. 그들은 Foster-Lyapunov 드리프트 분석을 활용하여 프라이빗 궤적이 "음의 드리프트(negative drift)"를 가짐을 증명하는데, 이는 프라이빗 궤적이 민감한 궤적에서 벗어나더라도 통계적으로 다시 근처로 돌아올 가능성이 높음을 의미한다.

주요 기여
본 논문은 네 가지 주요 기여를 한다:

• 새로운 프라이버시 정의 및 메커니즘: 저자들은 최단 경로 거리에 기반한 마르코프 체인 궤적의 새로운 인접성 정의를 도입하고, 이 정의에 맞춤화된 온라인 $\epsilon$-차분 프라이빗 메커니즘인 Mechanism 1을 개발한다.
• 오차 경계: 저자들은 프라이빗 궤적이 민감한 궤적으로부터 크게 벗어날 확률에 대한 집중 경계(concentration bound)를 제공하며(정리 2), 큰 오차가 지수적으로 감소하는 확률로 발생함을 보여준다.
• 전형성 및 엔트로피 경계: 저자들은 프라이빗 궤적의 기대 경험적 엔트로피를 제한하고(정리 3), 프라이빗 궤적이 높은 확률로 기저 마르코프 체인의 $\eta$-전형 집합(typical set) 내에 존재함을 보여주는 집중 경계를 제공한다(정리 4). 이는 프라이빗 데이터가 원래 프로세스의 통계적 특성을 유지하도록 보장한다.
• 실증적 검증: 제안된 메커니즘은 신용 전이, 도시 교통(플로리다주 게인즈빌), 인터넷 트래픽(Wikispeedia)의 세 가지 실제 데이터셋을 통해 테스트되었다.

결과
수치 시뮬레이션 결과, Mechanism 1은 동일한 프라이버시 수준을 유지하면서도 최신 기술(Chen et al., 2023b)보다 효용성 측면에서 성능이 크게 향상됨을 입증했다:

• 엔트로피 감소: 3-차분 프라이버시 조건 하에서, Mechanism 1은 기존 최신 기술에 비해 최대 80%의 엔트로피 감소를 보였다. 이는 생성된 프라이빗 궤적이 마르코프 체인의 실제 통계적 분포에 훨씬 더 가깝다는 것을 나타낸다.
• 오차 확률: 이 메커니즘은 기존 방법들과 비교하여 큰 오차(최단 경로 거리에서의 편차)가 발생할 확률을 최대 **4 자릿수(orders of magnitude)**까지 줄인다. 예를 들어, 신용 전이 예시에서 큰 오차($v=15$)가 발생할 확률은 0.003에서 $2 \times 10^{-7}$로 떨어졌다.
• 구조적 유사성: 궤적 길이가 길어짐에 따라 엔트로피가 증가하는 무작위 보행으로 퇴화하는 경lain 기존 방법들과 달리, Mechanism 1은 일정 궤적 길이 이후 일정한 엔트로피 수준을 유지하여 데이터의 구조적 무결성을 보존한다.

의의
본 논문은 자신의 프레임워크가 마르코프 체인 데이터의 프라이버시와 효용성 사이의 결정적인 트레이드오프 문제를 해결한다고 주장한다. 전이 확률을 사용하여 거리와 인접성을 정의함으로써, 이 메커니즘은 프라이빗 궤적이 민감한 데이터와 "전형적"이며 구조적으로 유사하게 유지되도록 보장한다. 이를 통해 하위 시스템은 사용자 프라이버시를 침해하지 않으면서 프라이빗 데이터를 효과적으로 활용할 수 있다. 저자들은 이 접근 방식이 신경망이나 문맥 특화적 거리 함수를 요구하지 않으므로, 전이 확률을 알고 있는 모든 마르코프 체인 환경에 직접 적용 가능하다는 점을 강조한다. 본 연구는 시스템의 기저 역학을 존중하는 온라인 프라이빗 궤적을 생성하는 것이 가능하다는 것을 입증하였으며, 이는 상태 공간을 구조화되지 않은 집합으로 취급하는 기존 방법들에 비해 상당한 진전이다.