🌟 MAD: алгоритм безопасной работы с огромными датасетами.

Большие данные - это топливо для ИИ. Но как их использовать, чтобы не нарушить приватность, например датасета, где есть персональные данные?

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

Таким алгоритмом стал Max Adaptive Degree (MAD), представленный Google на ICML 2025. Он не только эффективнее других параллельных методов, но и работает с наборами данных на десятки и сотни миллиардов записей.

🟡Стандартный MAD метод состоит из 3 шагов:

🟢Каждому элементу присваивается вес (обычно по частоте использования).

🟢К весу добавляется случайный шум для защиты приватности.

🟢Выбираются только те элементы, чей вес с шумом превышает определенный порог.

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

MAD решает ее с помощью адаптивного взвешивания, перераспределяя вес: забирает часть у популярных элементов и отдает тем, чьи значения уже находятся у порога. Это позволяет отобрать больше полезных данных без потери приватности.

Простой пример: представьте 100 пользователей, у каждого по 3 элемента. Один элемент (A) есть у всех, а остальные элементы уникальны. В базовом алгоритме элемент A получит слишком много веса (намного больше необходимого), а уникальные элементы - слишком мало. MAD "забирает" часть веса у A и распределяет его между уникальными элементами, давая им шанс пройти порог.

🟡MAD2R.

Метод можно использовать в несколько итераций, публикуя промежуточные результаты с шумом. Так можно еще точнее распределять вес между раундами.

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

На практике MAD показал отличные результаты. Всего за 2 этапа он отобрал больше полезных элементов, чем другие методы. Например, в Common Crawl (800 млрд. записей) он выбрал набор слов, который покрыл 99.9% всех записей и 97% уникальных слов с полным соблюдением приватности.


🟡Статья
🟡Arxiv
🖥GitHub


@ai_machinelearning_big_data

#AI #ML #Selection #MAD #Google