Экспоненциальный механизм (дифференциальная конфиденциальность) - Exponential mechanism (differential privacy)

В экспоненциальный механизм это техника для проектирования дифференциально частный алгоритмы. Он был разработан Фрэнк МакШерри^[1] и Кунал Талвар^[2] в 2007 году. Их работа была признана одним из лауреатов премии PET Award 2009 за выдающиеся исследования в области технологий повышения конфиденциальности.^[3]

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

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

Алгоритм

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

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

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

Теорема (дифференциальная конфиденциальность): ${displaystyle {mathcal {E}}_{q}^{varepsilon }(d),!}$ дает ${displaystyle (2varepsilon 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 d,!}$) и более ранний не более ${displaystyle exp(2varepsilon Delta q),!}$.

Точность

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

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

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

${displaystyle {frac {p({ar {S}}_{2t})}{p(S_{t})}}={frac {int _{{ar {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 ({ar {S}}_{2t})}{mu (S_{t})}}.}$

Значение ${displaystyle mu ({ar {S}}_{2t}),!}$ не больше единицы, поэтому из этой оценки следует утверждение леммы.

Теорема (точность): Для этих значений ${displaystyle tgeq ln left({frac {OPT}{tmu (S_{t})}}ight)/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 tgeq ln left({frac {OPT}{tmu (S_{t})}}ight)/varepsilon ,!}$. Подставляя значение ${displaystyle t,!}$ мы получаем эту вероятность как минимум ${displaystyle 1-t/OPT,!}$. Умножение на ${displaystyle OPT-2t,!}$ дает желаемую оценку.

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

Пример применения экспоненциального механизма ^[5]

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

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

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

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

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

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

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

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

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

Неформально это означает, что с большой вероятностью запрос ${displaystyle Q_{h},!}$ будет вести себя аналогичным образом в исходном наборе данных ${displaystyle D,!}$ и на синтетическом наборе данных ${displaystyle {widehat {D}},!}$.
Рассмотрим распространенную проблему интеллектуального анализа данных. Предположим, есть база данных ${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}},!}$ что позволит пользователю изучить (приблизительно) то же линейное полупространство при запросе к этой синтетической базе данных. Мотивация для такого алгоритма состоит в том, что новая база данных будет сгенерирована дифференциально конфиденциальным образом и, таким образом, обеспечит конфиденциальность отдельных записей в базе данных. ${displaystyle D,!}$.

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

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

${displaystyle |D|geq Oleft({frac {kcdot operatorname {VCDim} (H)log(1/alpha )}{alpha ^{3}varepsilon }}+{frac {log(1/delta )}{alpha varepsilon }}ight),!}$

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

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

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

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

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

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

${displaystyle {egin{aligned}&Pr left[,left|Q_{h}(D)-Q_{h}({widehat {D}})ight|geq {frac {alpha }{2}}{ ext{ for some }}hin Hight][5pt]leq {}&2left({frac {em}{operatorname {VCDim} (H)}}ight)^{operatorname {VCDim} (H)}cdot e^{-alpha ^{2}m/8},end{aligned}}}$

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

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

Определение: Для любой функции ${displaystyle q:(({0,1}^{k})^{n} imes ({0,1}^{k})^{m})ightarrow 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 _{hin 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}}in ({0,1}^{k})^{m},!}$ для которого ${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 {widehat {D}},!}$ такой, что ${displaystyle q(D,{widehat {D}})leq -alpha ,!}$.

${displaystyle herefore {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 ngeq {frac {4}{varepsilon alpha }}left(km+ln {frac {1}{delta }}ight)geq Oleft({frac {dcdot operatorname {VCDim} (H)log(1/alpha )}{alpha ^{3}varepsilon }}+{frac {log(1/delta )}{alpha varepsilon }}ight).,!}$

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

Экспоненциальный механизм в других областях

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

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

Рекомендации

1. Фрэнк МакШерри
2. Кунал Талвар
3. «Прошлые победители премии PET».
4. Ф. МакШерри и К. Талвар. Разработка механизмов с помощью дифференциальной конфиденциальности. Материалы 48-го ежегодного симпозиума основ информатики, 2007.
5. Аврим Блюм, Катрина Лигетт, Аарон Рот. Подход теории обучения к не-итеративной конфиденциальности базы данных // Материалы 40-го ежегодного симпозиума ACM по теории вычислений, 2008 г.
6. Христос Димитракакис, Блейн Нельсон, Айкатерини Митрокотса, Бенджамин Рубинштейн. Надежный и частный байесовский вывод. Теория алгоритмического обучения 2014
7. Ю-Сян Ван, Стивен Э. Финберг, Алекс Смола Конфиденциальность бесплатно: апостериорная выборка и стохастический градиент Монте-Карло. Международная конференция по машинному обучению, 2015.
8. Шива Прасад Касивисванатан, Хомин К. Ли, Кобби Ниссим, Софья Расходникова, Адам Смит. Чему мы можем научиться в частном порядке? Материалы 49-го ежегодного симпозиума IEEE 2008 г. по основам информатики. arXiv: 0803.0924

внешняя ссылка

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