Экспоненциальный механизм

В общем виде механизм приватности отображает набор из ${\displaystyle n}$ входных данных из области ${\displaystyle {\mathcal {D}}}$ в некоторое множество значений ${\displaystyle {\mathcal {R}}}$. Это отображение может быть рандомизированным, при этом каждому элементу области ${\displaystyle {\mathcal {D}}}$ соответствует вероятностное распределение на ${\displaystyle {\mathcal {R}}}$. Не делается никаких предположений о природе ${\displaystyle {\mathcal {D}}}$ и ${\displaystyle {\mathcal {R}}}$, кроме наличия базовой меры ${\displaystyle \mu }$ на ${\displaystyle {\mathcal {R}}}$. Пусть задана функция ${\displaystyle q:{\mathcal {D}}^{n}\times {\mathcal {R}}\rightarrow \mathbb {R} }$, которая интуитивно присваивает паре ${\displaystyle (d,r)}$ (где ${\displaystyle d\in {\mathcal {D}}^{n}}$ и ${\displaystyle r\in {\mathcal {R}}}$) некоторый балл; чем больше значение ${\displaystyle q(d,r)}$, тем «лучше» соответствие пары ${\displaystyle (d,r)}$. На входе ${\displaystyle d\in {\mathcal {D}}^{n}}$ задача механизма — вернуть такое ${\displaystyle r\in {\mathcal {R}}}$, чтобы функцию ${\displaystyle q(d,r)}$ было примерно максимизировано. Для этого определим механизм ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)}$ следующим образом:

Определение: для любой функции ${\displaystyle q:({\mathcal {D}}^{n}\times {\mathcal {R}})\rightarrow \mathbb {R} }$ и меры ${\displaystyle \mu }$ на ${\displaystyle {\mathcal {R}}}$:

${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d):=}$ выбрать ${\displaystyle r}$ с вероятностью, пропорциональной ${\displaystyle e^{\varepsilon q(d,r)}\cdot \mu (r)}$, где ${\displaystyle d\in {\mathcal {D}}^{n},r\in {\mathcal {R}}}$.

Это определение означает, что вероятность возврата ${\displaystyle r}$ возрастает экспоненциально с ростом ${\displaystyle q(d,r)}$. Если проигнорировать базовую меру ${\displaystyle \mu }$, то максимизирующее ${\displaystyle q(d,r)}$ значение будет иметь наибольшую вероятность. При этом данный механизм является дифференциально-приватным. Чтобы корректно определить ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)}$, необходимо, чтобы ${\displaystyle \int _{r}e^{\varepsilon q(d,r)}\cdot \mu (r)}$ была конечной.

Теорема (дифференциальная приватность): Механизм ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)}$ обеспечивает ${\displaystyle (2\varepsilon \Delta q)}$-дифференциальную приватность, где ${\displaystyle \Delta q}$ определяется далее.

Доказательство: вероятность для ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)}$ принять значение ${\displaystyle r}$ равна

${\displaystyle {\frac {e^{\varepsilon q(d,r)}\mu (r)}{\int e^{\varepsilon q(d,r)}\mu (r)\,dr}}}$.

Если изменение в одном элементе ${\displaystyle d}$ меняет ${\displaystyle q}$ не более чем на ${\displaystyle \Delta q}$, то числитель изменится не более чем в ${\displaystyle e^{\varepsilon \Delta q}}$ раз, а знаменатель — не менее чем в ${\displaystyle e^{-\varepsilon \Delta q}}$ раз. Соответственно, изменение плотности вероятности не превышает ${\displaystyle \exp(2\varepsilon \Delta q)}$^[4].

Желательно, чтобы случайные значения ${\displaystyle r}$, возвращаемые механизмом ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)}$, почти максимизировали ${\displaystyle q(d,r)}$. Если принять ${\displaystyle \max _{r}q(d,r)=OPT}$, доказывается, что вероятность значительного отклонения от ${\displaystyle OPT}$ мала, если множество ${\displaystyle r}$ с близким к максимальному ${\displaystyle q}$ достаточно велико по мере ${\displaystyle \mu }$.

Лемма: Пусть ${\displaystyle S_{t}=\{r:q(d,r)>OPT-t\}}$ и ${\displaystyle {\bar {S}}_{2t}=\{r:q(d,r)\leq OPT-2t\}}$, тогда ${\displaystyle p({\bar {S}}_{2t})}$ не больше ${\displaystyle \exp(-\varepsilon t)/\mu (S_{t})}$, где вероятность берётся по ${\displaystyle {\mathcal {R}}}$.

Доказательство: вероятность ${\displaystyle p({\bar {S}}_{2t})}$ не больше ${\displaystyle p({\bar {S}}_{2t})/p(S_{t})}$. Обе вероятности имеют одинаковый нормирующий множитель, поэтому

${\displaystyle {\frac {p({\bar {S}}_{2t})}{p(S_{t})}}={\frac {\int _{{\bar {S}}_{2t}}\exp(\varepsilon q(d,r))\mu (r)\,dr}{\int _{S_{t}}\exp(\varepsilon q(d,r))\mu (r)\,dr}}\leq \exp(-\varepsilon t){\frac {\mu ({\bar {S}}_{2t})}{\mu (S_{t})}}.}$

Пусть ${\displaystyle \mu ({\bar {S}}_{2t})\leq 1}$, тогда получаем нужную оценку.

Теорема (о точности): Для всех ${\displaystyle t\geq \ln \left({\frac {OPT}{t\mu (S_{t})}}\right)/\varepsilon }$ выполняется: ${\displaystyle E[q(d,{\mathcal {E}}_{q}^{\varepsilon }(d))]\geq OPT-3t}$.

Доказательство: из предыдущей леммы следует, что вероятность того, что балл будет хотя бы ${\displaystyle OPT-2t}$, равна ${\displaystyle 1-\exp(-\varepsilon t)/\mu (S_{t})}$. По предположению ${\displaystyle t\geq \ln \left({\frac {OPT}{t\mu (S_{t})}}\right)/\varepsilon }$. Подставляя ${\displaystyle t}$, получаем вероятность не менее ${\displaystyle 1-t/OPT}$. Умножая на ${\displaystyle OPT-2t}$, получаем искомое неравенство.

В вычислениях можно считать, что ${\displaystyle \mu (A)\leq 1}$ для любого ${\displaystyle A\subseteq {\mathcal {R}}}$, нормируя по ${\displaystyle \mu ({\mathcal {R}})}$.

Следующее утверждение принадлежит Авриму Блуму, Катрине Лигетт и Аарону Роту.

Определение (полезность): Механизм ${\displaystyle {\mathcal {A}}}$ называется ${\displaystyle (\alpha ,\delta )}$-полезным для запросов из класса ${\displaystyle H}$ с вероятностью ${\displaystyle 1-\delta }$, если ${\displaystyle \forall h\in H}$ и для любого набора данных ${\displaystyle D}$, при ${\displaystyle {\widehat {D}}={\mathcal {A}}(D)}$, выполняется ${\displaystyle |Q_{h}({\widehat {D}})-Q_{h}(D)|\leq \alpha }$.

Информально, это означает, что с высокой вероятностью запрос ${\displaystyle Q_{h}}$ вернёт на исходном и синтетическом наборах данных близкие результаты. Рассмотрим типичную задачу Data Mining: имеется база ${\displaystyle D}$ из ${\displaystyle n}$ записей вида ${\displaystyle k}$-кортежей ${\displaystyle (x_{1},x_{2},\dots ,x_{k})}$, где ${\displaystyle x_{i}\in \{0,1\}}$. Пользователь хочет найти линейное полупространство вида ${\displaystyle \pi _{1}x_{1}+\pi _{2}x_{2}+\cdots +\pi _{k-1}x_{k-1}\geq x_{k}}$ — то есть такие коэффициенты ${\displaystyle \pi _{1},\pi _{2},\dots ,\pi _{k-1}}$, чтобы максимальное число записей удовлетворяло неравенству. Приводимый дальше алгоритм позволяет сгенерировать синтетическую базу ${\displaystyle {\widehat {D}}}$, на которой пользователь сможет обучать те же линейные полупространства — причём с соблюдением дифференциальной приватности.

В этом разделе показано: можно опубликовать набор данных, полезный для концептов из класса с полиномиальной VC-измеримостью, сохранив при этом ${\displaystyle \varepsilon }$-дифференциальную приватность, если исходный набор достаточно велик полиномиально относительно VC-измеримости. Формально:

Теорема: Для любого класса функций ${\displaystyle H}$ и данных ${\displaystyle D\subset \{0,1\}^{k}}$, если

${\displaystyle |D|\geq O\left({\frac {k\cdot \operatorname {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon }}\right)}$,

можно построить ${\displaystyle (\alpha ,\delta )}$-полезный набор ${\displaystyle {\widehat {D}}}$, сохраняющий ${\displaystyle \varepsilon }$-дифференциальную приватность. При этом эффективность алгоритма не гарантируется.

Замечательно, что размер синтетического набора зависит не от исходных данных, а лишь от VC-измеримости концепта и параметра ${\displaystyle \alpha }$: ${\displaystyle {\tilde {O}}(\operatorname {VCDim} (H)/\alpha ^{2})}$.

Воспользуемся теоремой о единообразной сходимости из комбинаторики и её следствием для нашей задачи.

Лемма: Для любого набора ${\displaystyle D}$ найдётся ${\displaystyle {\widehat {D}}}$ размера ${\displaystyle O(\operatorname {VCDim} (H)\log(1/\alpha ))/\alpha ^{2}}$, такое что ${\displaystyle \max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\leq \alpha /2}$.

Доказательство:

Из теоремы единообразной сходимости:

${\displaystyle {\begin{aligned}&\Pr \left[\,\left|Q_{h}(D)-Q_{h}({\widehat {D}})\right|\geq {\frac {\alpha }{2}}{\text{ для некоторого }}h\in H\right]\\[5pt]\leq {}&2\left({\frac {em}{\operatorname {VCDim} (H)}}\right)^{\operatorname {VCDim} (H)}\cdot e^{-\alpha ^{2}m/8},\end{aligned}}}$

где вероятность берётся по распределению датасета. Если правая часть будет меньше единицы, гарантировано существование нужного множества ${\displaystyle {\widehat {D}}}$. Для этого требуется ${\displaystyle m\geq \lambda (\operatorname {VCDim} (H)\log(m/\operatorname {VCDim} (H))/\alpha ^{2})}$, где ${\displaystyle \lambda }$ — положительная константа. Поскольку выходной размер ${\displaystyle {\tilde {O}}(\operatorname {VCDim} (H)/\alpha ^{2})}$, достаточно требовать ${\displaystyle m\geq \lambda (\operatorname {VCDim} (H)\log(1/\alpha )/\alpha ^{2})}$.

Введём экспоненциальный механизм:

Определение: для функции ${\displaystyle q:((\{0,1\}^{k})^{n}\times (\{0,1\}^{k})^{m})\rightarrow \mathbb {R} }$ и входных данных ${\displaystyle D}$, экспоненциальный механизм выбирает набор ${\displaystyle {\widehat {D}}}$ с вероятностью, пропорциональной ${\displaystyle e^{q(D,{\widehat {D}})\varepsilon n/2}}$.

Из свойств механизма видно, что, он реализует ${\displaystyle (\varepsilon nGS_{q})}$-дифференциальную приватность.

Положим ${\displaystyle (q(D),q({\widehat {D}}))=-\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|}$.

Чтобы механизм был ${\displaystyle (\alpha ,\delta )}$-полезным, требуется, чтобы возвращался такой ${\displaystyle {\widehat {D}}}$, что ${\displaystyle q(D,{\widehat {D}})\geq -\alpha }$ с вероятностью ${\displaystyle 1-\delta }$. Всего выходных наборов ${\displaystyle 2^{km}}$; вероятность, что ${\displaystyle q(D,{\widehat {D}})\leq -\alpha }$, не более ${\displaystyle e^{-\varepsilon \alpha n/2}}$. Следовательно, по неравенству объединения, вероятность возвратить такой ${\displaystyle {\widehat {D}}}$ не превышает ${\displaystyle 2^{km}e^{-\varepsilon \alpha n/2}}$. Поскольку всегда существует ${\displaystyle {\widehat {D}}}$ с ${\displaystyle q(D,{\widehat {D}})\geq -\alpha /2}$, оно выбирается с вероятностью не менее ${\displaystyle e^{-\alpha \varepsilon n/4}}$.

Обозначим

• ${\displaystyle A}$ — событие, что механизм возвращает такой ${\displaystyle {\widehat {D}}}$, что ${\displaystyle q(D,{\widehat {D}})\geq -\alpha /2}$;
• ${\displaystyle B}$ — событие, что возвращается ${\displaystyle q(D,{\widehat {D}})\leq -\alpha }$.

  Тогда

${\displaystyle {\frac {\Pr[A]}{\Pr[B]}}\geq {\frac {e^{-\alpha \varepsilon n/4}}{2^{km}e^{-\alpha \varepsilon n/2}}}={\frac {e^{\alpha \varepsilon n/4}}{2^{km}}}}$.

Требуя, чтобы это было не меньше ${\displaystyle 1/\delta \geq (1-\delta )/\delta }$, получаем достаточное условие на размер исходных данных:

${\displaystyle n\geq {\frac {4}{\varepsilon \alpha }}\left(km+\ln {\frac {1}{\delta }}\right)\geq O\left({\frac {d\cdot \operatorname {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon }}\right).}$

Таким образом, теорема доказана.