Дифференциальная приватность (DP) — золотой стандарт защиты информации пользователей в крупномасштабном машинном обучении и анализе данных. Важной задачей в рамках DP является выбор раздела — процесс безопасного извлечения максимально возможного набора уникальных элементов из огромных наборов данных, предоставленных пользователями (например, запросов или токенов документов), при сохранении строгих гарантий конфиденциальности.
Команда исследователей из MIT и Google AI Research представила новые алгоритмы для выбора разделов с дифференциальной приватностью. Этот подход позволяет максимизировать количество уникальных элементов, выбранных из объединения наборов данных, при строгом сохранении конфиденциальности на уровне пользователей.
Проблема выбора раздела в дифференциальной приватности
По сути, выбор раздела ставит вопрос: как мы можем раскрыть как можно больше различных элементов из набора данных, не рискуя конфиденциальностью отдельных лиц? Элементы, известные только одному пользователю, должны оставаться секретными; только те, которые имеют достаточную «краудсорсинговую» поддержку, могут быть безопасно раскрыты.
Эта проблема лежит в основе критически важных приложений, таких как:
* частный словарь и извлечение n-грамм для задач НЛП;
* категориальный анализ данных и вычисление гистограмм;
* обучение с сохранением конфиденциальности встраиваний на основе предоставленных пользователями элементов;
* анонимизация статистических запросов (например, к поисковым системам или базам данных).
Стандартные подходы и ограничения
Традиционно используемое решение (реализовано в библиотеках типа PyDP и в наборе инструментов Google для дифференциальной приватности) включает три шага:
1. Взвешивание: каждый элемент получает «оценку», обычно его частоту среди пользователей, при этом вклад каждого пользователя строго ограничен.
2. Добавление шума: чтобы скрыть точную активность пользователей, к весу каждого элемента добавляется случайный шум (обычно гауссовский).
3. Установка порогов: только элементы, чей зашумлённый вес превышает установленный порог (рассчитанный на основе параметров конфиденциальности ε, δ), публикуются.
Этот метод прост и хорошо распараллеливается, что позволяет масштабировать его до гигантских наборов данных с помощью таких систем, как MapReduce, Hadoop или Spark. Однако он страдает от фундаментальной неэффективности: популярные элементы накапливают избыточный вес, который не способствует повышению конфиденциальности, в то время как менее распространённые, но потенциально ценные элементы часто не раскрываются из-за того, что избыточный вес не перенаправляется на помощь им в преодолении порога.
Адаптивное взвешивание и алгоритм MaxAdaptiveDegree (MAD)
Исследования Google представляют первый адаптивный, распараллеливаемый алгоритм выбора раздела — MaxAdaptiveDegree (MAD), и его многоэтапное расширение MAD2R, предназначенное для действительно огромных наборов данных (сотни миллиардов записей).
Ключевые технические достижения:
* Адаптивное перевзвешивание: MAD идентифицирует элементы с весом, значительно превышающим порог конфиденциальности, и перенаправляет избыточный вес для повышения представленности менее представленных элементов. Это «адаптивное взвешивание» увеличивает вероятность раскрытия редких, но доступных для обмена элементов, максимизируя таким образом полезность выходных данных.
* Строгие гарантии конфиденциальности: механизм перенаправления поддерживает те же требования к чувствительности и шуму, что и классическое равномерное взвешивание, обеспечивая конфиденциальность на уровне пользователей (ε, δ)-дифференциальной приватности в рамках центральной модели DP.
* Масштабируемость: MAD и MAD2R требуют только линейной работы в зависимости от размера набора данных и постоянного количества параллельных раундов, что делает их совместимыми с массовыми системами распределённой обработки данных. Они не требуют размещения всех данных в памяти и поддерживают эффективное выполнение на нескольких машинах.
* Многоэтапное улучшение (MAD2R): разделяя бюджет конфиденциальности между раундами и используя зашумлённые веса из первого раунда для смещения второго, MAD2R дополнительно повышает производительность, позволяя безопасно извлекать ещё больше уникальных элементов — особенно в длиннохвостых распределениях, типичных для реальных данных.
Как работает MAD — алгоритмические детали
1. Начальное равномерное взвешивание: каждый пользователь делится своими элементами с единой начальной оценкой, обеспечивая границы чувствительности.
2. Усечение и перенаправление избыточного веса: элементы выше «адаптивного порога» имеют свой избыточный вес, обрезанный и перенаправленный пропорционально обратно вкладчикам, которые затем перераспределяют это на свои другие элементы.
3. Окончательная корректировка веса: добавляется дополнительный равномерный вес, чтобы компенсировать небольшие ошибки начального распределения.
4. Добавление шума и вывод: добавляется гауссовский шум; элементы выше зашумлённого порога выводятся.
В MAD2R выходные данные первого раунда и зашумлённые веса используются для уточнения того, на какие элементы следует сосредоточиться во втором раунде, при этом весовые смещения гарантируют отсутствие потери конфиденциальности и дальнейшее повышение полезности выходных данных.
Экспериментальные результаты: современный уровень производительности
Обширные эксперименты на девяти наборах данных (от Reddit, IMDb, Wikipedia, Twitter, Amazon и вплоть до Common Crawl с почти триллионом записей) показывают:
* MAD2R превосходит все параллельные базовые алгоритмы (Basic, DP-SIPS) на семи из девяти наборов данных по количеству выходных элементов при фиксированных параметрах конфиденциальности.
* В наборе данных Common Crawl MAD2R извлек 16,6 миллиона из 1,8 миллиарда уникальных элементов (0,9%), но охватил 99,9% пользователей и 97% всех пар «пользователь-элемент» в данных — демонстрируя замечательную практическую полезность при сохранении конфиденциальности.
Для небольших наборов данных MAD приближается к производительности последовательных, немасштабируемых алгоритмов, а для больших наборов данных он явно выигрывает как по скорости, так и по полезности.
Конкретный пример: разрыв в полезности
Рассмотрим сценарий с «тяжёлым» элементом (очень часто общим) и множеством «лёгких» элементов (которыми поделились немногие пользователи). Базовый выбор DP переоценивает тяжёлый элемент, не поднимая лёгкие элементы достаточно, чтобы преодолеть порог. MAD стратегически перераспределяет, увеличивая вероятность раскрытия лёгких элементов и в результате обнаруживая до 10% больше уникальных элементов по сравнению со стандартным подходом.
Резюме
Благодаря адаптивному взвешиванию и параллельной структуре исследовательская группа выводит выбор разделов DP на новый уровень масштабируемости и полезности. Эти достижения гарантируют, что исследователи и инженеры смогут более полно использовать частные данные, извлекая больше информации без ущерба для конфиденциальности отдельных пользователей.
1. Какие проблемы решает дифференциальная приватность в контексте машинного обучения и анализа данных?
Дифференциальная приватность (DP) решает задачу защиты информации пользователей в крупномасштабном машинном обучении и анализе данных. Она обеспечивает строгие гарантии конфиденциальности при извлечении максимально возможного набора уникальных элементов из огромных наборов данных, предоставленных пользователями.
2. В чём заключается основная идея алгоритма MaxAdaptiveDegree (MAD)?
Основная идея алгоритма MaxAdaptiveDegree (MAD) заключается в адаптивном перевзвешивании элементов для максимизации количества уникальных элементов, выбранных из объединения наборов данных, при сохранении конфиденциальности на уровне пользователей. MAD идентифицирует элементы с весом, значительно превышающим порог конфиденциальности, и перенаправляет избыточный вес для повышения представленности менее представленных элементов.
3. Какие технические достижения представлены в исследованиях Google для алгоритма MAD?
В исследованиях Google для алгоритма MAD представлены следующие технические достижения:
* адаптивное перевзвешивание;
* строгие гарантии конфиденциальности;
* масштабируемость;
* многоэтапное улучшение (MAD2R).
4. Как работает алгоритм MAD на практике?
Алгоритм MAD работает следующим образом:
1. Начальное равномерное взвешивание: каждый пользователь делится своими элементами с единой начальной оценкой.
2. Усечение и перенаправление избыточного веса: элементы выше «адаптивного порога» имеют свой избыточный вес, обрезанный и перенаправленный пропорционально обратно вкладчикам.
3. Окончательная корректировка веса: добавляется дополнительный равномерный вес, чтобы компенсировать небольшие ошибки начального распределения.
4. Добавление шума и вывод: добавляется гауссовский шум; элементы выше зашумлённого порога выводятся.
5. Каковы экспериментальные результаты применения алгоритма MAD2R на различных наборах данных?
Экспериментальные результаты применения алгоритма MAD2R на девяти наборах данных (от Reddit, IMDb, Wikipedia, Twitter, Amazon и вплоть до Common Crawl с почти триллионом записей) показывают, что MAD2R превосходит все параллельные базовые алгоритмы на семи из девяти наборов данных по количеству выходных элементов при фиксированных параметрах конфиденциальности. В наборе данных Common Crawl MAD2R извлёк 16,6 миллиона из 1,8 миллиарда уникальных элементов (0,9%), но охватил 99,9% пользователей и 97% всех пар «пользователь-элемент» в данных.