Мы представляем новые алгоритмы для сохранения конфиденциальности пользователей при публикации данных, улучшая существующий уровень в области выбора разделов с дифференциальной приватностью.
Быстрые ссылки
- Бумага
- Делиться
Большие массивы данных, созданные на основе пользовательского опыта, бесценны для развития моделей искусственного интеллекта и машинного обучения. Они стимулируют инновации, которые напрямую приносят пользу пользователям благодаря улучшенным услугам, более точным прогнозам и персонализированному опыту. Сотрудничество и обмен такими массивами данных могут ускорить исследования, способствовать появлению новых приложений и внести вклад в более широкое научное сообщество. Однако использование этих мощных массивов данных также сопряжено с потенциальными рисками для конфиденциальности данных.
Процесс идентификации конкретного, значимого подмножества уникальных элементов, которые можно безопасно передавать из обширной коллекции на основе частоты или заметности их появления во многих отдельных фрагментах (например, поиск всех общих слов, используемых в огромном наборе документов), называется «дифференциально-приватным (ДП) выбором разделов». Применение дифференциальной защиты конфиденциальности при выборе разделов позволяет выполнить этот выбор таким образом, чтобы никто не мог узнать, внесли ли данные какого-либо отдельного человека конкретный элемент в итоговый список. Это достигается путем добавления контролируемого шума и выбора только тех элементов, которые достаточно распространены даже после включения этого шума, обеспечивая тем самым конфиденциальность отдельных лиц. ДП является первым шагом во многих важных задачах анализа данных и машинного обучения, включая извлечение словаря (или n -грамм) из большого закрытого корпуса (необходимый шаг во многих приложениях анализа текста и языкового моделирования), анализ потоков данных с сохранением конфиденциальности, получение гистограмм по пользовательским данным и повышение эффективности тонкой настройки закрытых моделей.
В контексте обработки огромных массивов данных, таких как пользовательские запросы, параллельный алгоритм имеет решающее значение. Вместо обработки данных по одному фрагменту за раз (как это делал бы последовательный алгоритм), параллельный алгоритм разбивает задачу на множество более мелких частей, которые могут вычисляться одновременно на нескольких процессорах или машинах. Эта практика важна не только для оптимизации; это фундаментальная необходимость при работе с масштабами современных данных. Параллелизация позволяет обрабатывать огромные объемы информации одновременно, что дает исследователям возможность работать с наборами данных, содержащими сотни миллиардов элементов. Благодаря этому можно обеспечить надежные гарантии конфиденциальности без ущерба для полезности, получаемой от больших наборов данных.
В нашей недавней публикации «Масштабируемый выбор частного разбиения с помощью адаптивного взвешивания», представленной на конференции ICML2025, мы представляем эффективный параллельный алгоритм, позволяющий применять выбор частного разбиения к различным наборам данных. Наш алгоритм демонстрирует лучшие результаты среди параллельных алгоритмов и масштабируется до наборов данных, содержащих сотни миллиардов элементов, что в три порядка больше, чем у предыдущих последовательных алгоритмов. Для поощрения сотрудничества и инноваций в исследовательском сообществе мы публикуем исходный код алгоритма выбора частного разбиения в открытом доступе на GitHub.
Как работает алгоритм
Цель выбора раздела DP (Disprivacy Persistence) состоит в максимизации количества уникальных элементов, выбранных из объединения наборов данных, при строгом сохранении DP на уровне пользователя. Это означает, что очень популярные элементы, принадлежащие многим пользователям, часто могут быть безопасно сохранены для последующих вычислительных задач, тогда как элементы, принадлежащие только одному пользователю, не будут включены. Разработчик алгоритма должен стремиться к оптимальному компромиссу между конфиденциальностью и полезностью при выборе элементов из набора данных, соблюдая при этом требование дифференциальной конфиденциальности.
Стандартная парадигма: вес, шум и фильтр.
Традиционный подход к выбору разделов с дифференциальной приватностью включает три основных этапа:
- Вес: Для каждого элемента вычисляется «вес», обычно представляющий частоту встречаемости элемента или некоторую совокупность данных по всем пользователям. Это формирует гистограмму весов. Важнейшим требованием конфиденциальности является «низкая чувствительность», то есть общий вес, внесенный любым отдельным пользователем, ограничен. В стандартной неадаптивной среде пользователи присваивают веса своим элементам независимо от того, что вносят другие пользователи (например, базовый метод гауссова взвешивания).
- Шум: Для обеспечения защиты от копирования к вычисленному весу каждого элемента добавляется случайный шум (например, гауссовский шум с определенным стандартным отклонением). Это искажает точные данные, не позволяя злоумышленнику определить присутствие или данные конкретного человека.
- Фильтрация: Наконец, применяется пороговое значение, определяемое параметрами DP. В итоговый результат включаются только те элементы, чьи зашумленные веса превышают это пороговое значение.
Парадигма веса, шума и фильтра. На всех графиках по оси x отложены элементы (A–F), а по оси y — вес, присвоенный элементам. Алгоритм сначала вычисляет гистограмму весов для элементов ( слева ), добавляет шум ( в центре ) и возвращает элементы с зашумленным весом выше порогового значения ( справа ).
Повышение полезности за счет адаптивного взвешивания
Ограничением стандартного неадаптивного подхода является потенциальная «нерациональность». Наиболее популярные товары могут получать значительно больший вес, чем необходимо для преодоления порога конфиденциальности, фактически «избыточное распределение» веса. Этот избыточный вес можно было бы более эффективно использовать для продвижения товаров, находящихся чуть ниже порога, тем самым увеличив общее количество выпущенных товаров и повысив полезность результата.
Для решения этой проблемы мы вводим адаптивный подход в процесс присвоения весов. В отличие от неадаптивных методов, где вклад каждого пользователя независим, адаптивная конструкция позволяет учитывать вклад других пользователей при определении веса, присвоенного пользователем элементу. Это тонкий баланс, которого необходимо достичь, не нарушая конфиденциальность и не снижая вычислительную эффективность.
Наш новый алгоритм MaxAdaptiveDegree (MAD) стратегически перераспределяет вес. Он выявляет элементы со значительным «избыточным весом» (значительно превышающим пороговое значение) и перенаправляет часть этого веса на «недостаточно распределенные» элементы (те, которые находятся чуть ниже порогового значения). Это адаптивное перераспределение гарантирует, что большее количество менее часто встречающихся элементов сможет преодолеть порог конфиденциальности и быть включено в выходные данные. Более того, MAD сохраняет те же низкие границы конфиденциальности и эффективность, что и базовый алгоритм, что означает, что он предлагает те же надежные гарантии конфиденциальности и масштабируемость в системах параллельной обработки (таких как системы типа MapReduce), но со значительно большей полезностью.
Кроме того, мы распространяем эту концепцию на многораундовые системы выбора разделов DP. Мы демонстрируем, как безопасно освобождать промежуточные зашумленные векторы весов между раундами. Эта дополнительная информация позволяет добиться еще большей адаптивности, поскольку мы можем уменьшить будущие распределения весов для элементов, которые ранее получили слишком большой вес (и, вероятно, снова будут перераспределены) или слишком маленький вес (и вряд ли когда-либо пересекут пороговое значение). Это дополнительно уточняет распределение весов, максимизируя полезность без ущерба для конфиденциальности, и еще больше увеличивает количество элементов на выходе.
Эксперименты
Мы провели обширные эксперименты, сравнивая наш алгоритм MAD с одной или несколькими итерациями с масштабируемыми базовыми алгоритмами для выбора частного раздела.
Как показано в таблице ниже, метод MAD всего с двумя итерациями (столбец MAD2R) достигает самых современных результатов на многих наборах данных — часто выдавая значительно больше элементов, чем другие методы (даже те, которые используют больше раундов), при этом сохраняя те же гарантии конфиденциальности.
Сравнение количества элементов, возвращаемых нашими алгоритмами: двухэтапный (MAD2R) и другие базовые алгоритмы («Basic», представляющий собой алгоритм с равномерным взвешиванием, и DP-SIPS ) на девяти общедоступных наборах данных. Благодаря использованию новых методов адаптации, наш двухэтапный алгоритм достигает самых современных результатов на многих наборах данных.
В нашей статье мы представляем теоретические результаты, которые предполагают, что наш однораундовый алгоритм (MAD) всегда должен превосходить упомянутый выше базовый алгоритм гауссова взвешивания за один раунд. Наши результаты демонстрируют, что эта теоретическая гипотеза, по-видимому, верна. Превосходная производительность наших новых методов сохраняется при широком выборе параметров конфиденциальности и гиперпараметров. Пример реализации нашего алгоритма в памяти на Python доступен в репозитории с открытым исходным кодом.
На крупномасштабном общедоступном наборе данных Common Crawl (содержащем около 800 миллиардов записей) мы получили DP на уровне записей, рассматривая записи как «пользователей», а слова в этих записях как элементы. На этом наборе данных наш двухэтапный алгоритм MAD выдал набор элементов, охватывающий 99,9% записей (каждая из которых имеет хотя бы один элемент в выходных данных) и 97% записей базы данных (соответствующих элементу, присутствующему в выходных данных), при этом гарантируя DP.
Всего за две итерации наш алгоритм достиг самых современных результатов в широком диапазоне настроек параметров. Как и ожидалось, исходя из наших теоретических результатов, наш алгоритм всегда превосходил базовый.
Количество элементов, возвращаемых нашим двухэтапным алгоритмом MAD, в зависимости от частоты встречаемости (количество записей, содержащих данный элемент) в наборе данных Common Crawl. Хотя алгоритм MAD не может возвращать элементы с низкой частотой, нарушающие конфиденциальность, он выдает подавляющее большинство элементов, принадлежащих множеству записей.
Заключение
Мы представляем новые методы для улучшения компромисса между полезностью и конфиденциальностью в алгоритмах выбора разделов DP. Наш алгоритм достигает самых современных результатов на наборах данных, приближающихся к триллиону записей. Мы надеемся, что этот алгоритм поможет специалистам добиться большей полезности в своих рабочих процессах, строго соблюдая при этом конфиденциальность пользователей.
Благодарности
Мы благодарим Алессандро Эпасто и Винсента Коэна-Аддада, сотрудников группы алгоритмов и оптимизации Google Research , которые внесли свой вклад в эту работу.
Источник: research.google
