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

Экспоненциальный механизм — это метод разработки дифференциально частных алгоритмов. Его разработал Фрэнк МакШерри. и Кунал Талвар в 2007 году. Их работа была признана одним из победителей премии PET 2009 года за выдающиеся исследования в области технологий повышения конфиденциальности.

Большая часть первоначальных исследований в области дифференциальной конфиденциальности вращалась вокруг вещественнозначных функций, которые имеют относительно низкую чувствительность к изменению данных одного человека и чья полезность не ограничивается небольшими аддитивными возмущениями. Естественный вопрос: что происходит в ситуации, когда хочется сохранить более общие наборы свойств? Экспоненциальный механизм помогает расширить понятие дифференциальной конфиденциальности для решения этих проблем. Более того, он описывает класс механизмов, включающий все возможные дифференциально частные механизмы.

Механизм

Источник:

Алгоритм

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

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

Из этого определения следует тот факт, что вероятность возврата $r\,\!$ растет экспоненциально с увеличением стоимости $q(d,r)\,\!$. Игнорирование базовой меры $\mu \,\!$ тогда значение $r\,\!$ который максимизирует $q(d,r)\,\!$ имеет наибольшую вероятность. Более того, этот механизм является дифференциально частным. Доказательство этого утверждения будет приведено ниже. Одна техническая особенность, которую следует иметь в виду, заключается в том, что для правильного определения ${\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$ тот $\int _{r}e^{\varepsilon q(d,r)}\times \mu (r)\,\!$ должно быть конечным.

Теорема (дифференциальная конфиденциальность): ${\mathcal {E}}_{q}^{\varepsilon }(d)\,\!$ дает $(2\varepsilon \Delta q)\,\!$-дифференцированная конфиденциальность.

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

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

Теперь, если одно изменение в $d\,\!$ изменения $q\,\!$ максимум $\Delta q\,\!$ то числитель может измениться не более чем в раз. $e^{\varepsilon \Delta q}\,\!$ а минимум знаменателя в раз $e^{-\varepsilon \Delta q}\,\!$. Таким образом, соотношение новой плотности вероятности (т.е. с новой $d\,\!$) и более ранний не более $\exp(2\varepsilon \Delta q)\,\!$.

Точность

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

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

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

${\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})}}.$

Стоимость $\mu ({\bar {S}}_{2t})\,\!$ не более единицы, поэтому из этой оценки следует утверждение леммы.

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

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

Мы можем предположить $\mu (A)\,\!$ для $A\subseteq {\mathcal {R}}\,\!$ быть меньше или равно единице во всех вычислениях, потому что мы всегда можем нормализовать с помощью $\mu ({\mathcal {R}})\,\!$ .

Пример приложения

Источник:

Прежде чем мы углубимся в детали примера, давайте определим некоторые термины, которые мы будем широко использовать в ходе нашего обсуждения.

Определение (глобальная чувствительность): глобальная чувствительность запроса. $Q\,\!$ это его максимальная разница при оценке на двух соседних наборах данных $D_{1},D_{2}\in {\mathcal {D}}^{n}\,\!$:

$GS_{Q}=\max _{D_{1},D_{2}:d(D_{1},D_{2})=1}|(Q(D_{1})-Q(D_{2}))|.\,\!$

Определение: запрос предиката. $Q_{\varphi }\,\!$ для любого предиката $\varphi \,\!$ определяется как

$Q_{\varphi }={\frac {|\{x\in D:\varphi (x)\}|}{|D|}}.\,\!$

Обратите внимание, что $GS_{Q_{\varphi }}\leq 1/n\,\!$ для любого предиката $\varphi \,\!$.

Механизм выпуска

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

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

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

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

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

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

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

Интересным фактом является то, что алгоритм, который мы собираемся разработать, генерирует синтетический набор данных, размер которого не зависит от исходного набора данных; на самом деле это зависит только от VC-размерности класса концептов и параметра $\alpha \,\!$. Алгоритм выводит набор данных размером ${\tilde {O}}(\operatorname {VCDim} (H)/\alpha ^{2})\,\!$

Мы заимствовали теорему о равномерной сходимости из комбинаторики и сформулировали из нее следствие, соответствующее нашим потребностям.

Лемма: Учитывая любой набор данных $D\,\!$ существует набор данных ${\widehat {D}}\,\!$ размера $=O(\operatorname {VCDim} (H)\log(1/\alpha ))/\alpha ^{2}\,\!$ такой, что $\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\leq \alpha /2\,\!$.

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

Из теоремы о равномерной сходимости мы знаем, что

${\begin{aligned}&\Pr \left[\,\left|Q_{h}(D)-Q_{h}({\widehat {D}})\right|\geq {\frac {\alpha }{2}}{\text{ for some }}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}}$

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

Теперь мы задействуем экспоненциальный механизм.

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

Из экспоненциального механизма мы знаем, что это сохраняет $(\varepsilon nGS_{q})\,\!$-дифференцированная конфиденциальность. Вернемся к доказательству теоремы.

Мы определяем $(q(D),q({\widehat {D}}))=-\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\,\!$.

Чтобы показать, что этот механизм удовлетворяет $(\alpha ,\delta )\,\!$-полезность, мы должны показать, что он выводит некоторый набор данных ${\widehat {D}}\,\!$ с $q(D,{\widehat {D}})\geq -\alpha \,\!$ с вероятностью $1-\delta \,\!$. Есть максимум $2^{km}\,\!$ наборы выходных данных и вероятность того, что $q(D,{\widehat {D}})\leq -\alpha \,\!$ максимально пропорционально $e^{-\varepsilon \alpha n/2}\,\!$. Таким образом, согласно объединению, вероятность вывода любого такого набора данных ${\widehat {D}}\,\!$ максимально пропорционально $2^{km}e^{-\varepsilon \alpha n/2}\,\!$. Опять же, мы знаем, что существует некоторый набор данных ${\widehat {D}}\in (\{0,1\}^{k})^{m}\,\!$ для чего $q(D,{\widehat {D}})\geq -\alpha /2\,\!$. Следовательно, такой набор данных выводится с вероятностью, по крайней мере, пропорциональной $e^{-\alpha \varepsilon n/4}\,\!$.

Позволять $A:=\,\!$ событие, когда экспоненциальный механизм выводит некоторый набор данных ${\widehat {D}}\,\!$ такой, что $q(D,{\widehat {D}})\geq -\alpha /2\,\!$.

$B:=\,\!$ событие, когда экспоненциальный механизм выводит некоторый набор данных ${\widehat {D}}\,\!$ такой, что $q(D,{\widehat {D}})\leq -\alpha \,\!$.

$\therefore {\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}}}.\,\!$

Теперь установим это количество как минимум $1/\delta \geq (1-\delta )/\delta \,\!$, мы находим, что достаточно иметь

$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).\,\!$

И тем самым мы доказываем теорему.

Приложения в других доменах

В приведенном выше примере использования экспоненциального механизма можно вывести синтетический набор данных дифференциально-частным способом и использовать этот набор данных для ответа на запросы с хорошей точностью. Другие частные механизмы, такие как апостериорная выборка, который возвращает параметры, а не наборы данных, можно сделать эквивалентным экспоненциальному.

Помимо настройки конфиденциальности, экспоненциальный механизм также изучался в контексте теории аукционов и алгоритмов классификации . В случае аукционов экспоненциальный механизм помогает добиться правдивых настроек аукциона.

Внешние ссылки

• Алгоритмические основы дифференциальной конфиденциальности Синтии Дворк и Аарона Рота, 2014.