- PVSM.RU - https://www.pvsm.ru -
Сегодня в Лондоне стартовала одна из главных Data Science конференций года, постараюсь оперативно рассказывать о том, что интересного удалось услышать.
Начало выдалось нервным — в то же утро в этом же центре организовалась массовая встреча свидетелей иеговы, поэтому найти стойку регистрации КДД было не просто, а когда в итоге нашел — очередь на регистрацию была длиною метров 150-200. Тем не менее после ~20 минут ожидания получил вожделенный бэйдж и оправился на воркшоп.
Первый туториал был посвящен сохранению приватности при анализе данных. На начало я опоздал, но, судя по всему, особо ничего не потерял — там рассказывали о том что приватность важно и как могут злоумышленники нехорошо использовать расскрытую приватную информацию. Рассказывают, кстати, вполне уважаемые люди от Гугла, ЛинкедИн-а и Эпла. По итогам воркшоп оставил очень положительное впечатление, слайды все доступны здесь [1].
Оказывается уже достаточно давно существует концепция Differential Privacy [2], онсновная идея которого заключается в том, чтобы добавлять шум, затрудняющий установление истинных индивидуальных значений, но сохраняющий возможность восстановление общих распределений. Собственно есть два параметра e — насколько сложно раскрыть данные и d — насколько искажены ответы.
В оригинале концепции предполагается что между аналитиком и данным присутствует некоторое промежуточное звено — «Куратор» — именно он обрабатывает все запросы и формирует ответы так, чтобы шум скрывал приватные данные. В реальности часто используется модель Local Differential Privacy когда данные пользователя остаются на устройстве пользователя (например, мобильном телефоне или ПК), но при ответе на запросы разработчика приложение с личного устройства отправляется такой пакет данных, который не позволяет выяснить что же именно ответил данный конкретный пользователь, но, при объединении ответов от большого числа пользователей можно с высокой точностью восстановить общую картину.
Хороший пример — опрос о том, «делали ли вы аборт». Если делать опрос «в лоб», то правду никто не скажет. Но если организовать опрос следующим образом «подкиньте монетку, если будет орел, то кидайте еще раз и на орла говорите да, а на решку нет, иначе ответьте правду» легко получается восстановить истинное распределение при сохранении индивидуальной приватности. Развитием этой идеи стала механика сбора чувствительной статистики от гугла RAPPOR [3](RAndomized Privacy-Preserving Ordinal Report), использовавшийся для сбора некоторой статистики об использовании браузера Chrome и его форков.
Сразу после выхода Хрома в опенсоурс появилось достаточно большое количество желающих сделать собственный браузер с переопределенной домашней страницей, поисковым движком, собственными рекламными плашками и т.д. Естественно пользователи и гугл от этого были не в восторге. Дальнейшие действия в целом понятны — выяснить наиболее распространенные подмены и придавить административно, но вышел нежданчик… Политика приватности хрома не позволяла гуглу взять и собрать информацию о настройке домашней страницы и поисковика пользователя на сервак :(
Чтобы преодолеть это ограничение и появился RAPPOR, который работает следующим образом:
Схематично построение фильтра выглядит так:
Опыт внедрения RAPPOR оказался очень позитивен и количество приватных статистик с помощью него собранных быстро увеличивалось. Среди основных факторов успеха авторы выделили:
Однако, у такого подхода есть и существенное ограничение — необходимо иметь списки ответов-кандидатов для расшифровки (именно поэтому и O — Ordinal). Когда компания Apple начать собирать статистику об используемых в текстовых сообщениях словах и эмоджи стало понятно что этот подход не годится. В результате на конференции WDC-2016 одной из топовых новых заявленных фич в ИОС стало добавление differential privacy. В качестве основы также была использована комбинация структуры-скетча с добавлением шума, однако пришлось решить много технических проблем:
В итоге пришли к схеме с использование count-min-sketch [4] для кодирования слов, далее выбирался ответ только одной из хеш-функций случайным образом (но с фиксацией выбора для пары юзер/слово), вектор преобразовывался с помощью Hadamard transform [5] и на сервер слался только один значащий «бит» для выбранной хеш-функции.
В итоге для восстановления результата на сервер так же надо было просмотреть гипотезы-кандидаты, но, выяснилось что при большом размере словаря даже для кластера это слишком сложно. Нужно было как-то эвристически выбирать наиболее перспективные направления поиска. Эксперимент с использование биграм как начальных точек из которых затем можно собрать пазл оказался неудачным — все биграммы были примерно одинаково популярны. Подход биграмма+хеш слова решал проблему, но вел к нарушению приватности. В итоге остановились на префиксных деревьях — статистика собиралась по начальным частям слова и далее по слову целиком.
Анализ используемого Эпл алгоритма приватности исследовательским сообществом, тем не менее, показал что при долговременном сборе статистики приватность все-таки может быть скомпрометирована [6].
В более сложной ситуации оказался LinkedIn в исследовании о распределении зарплат пользователей. Дело в том, что differential privacy хорошо работает когда у нас есть очень большое количество измерений, иначе не удается надежно вычесть шум. В зарплатом же опросе количество отчетов ограничено и линкедин решил пойти по другому пути: совместить технические инструменты криптографии и кибербезопасности с концепцией k-Anonymity [7] — данные пользователя считаются достачно замаскированны если подавать их пачкой где есть к ответов с одинаковыми входными атрибутами (например, локация и профессия) и отличающиеся только целевой переменной (зарплата).
В итоге был построен комплексный пайплайн где разные сервисы передают друг другу куски данных постоянно шифруя так, что раскрыть их целиком не может одна отдельно взятая машина. В итоге пользователи бьются на когорты по их атрибутам и по достижению когортой минимального размера её стата уходит в ХДФС для анализа.
Отдельного внимания заслуживает таймстамп — его так же необходимо анонимизировать, иначе имеется возможность выяснить чей-же это ответ по логу заходов. Но целиком убирать время не хочется — ведь интересно следить за динамикой. В итоге решили добавить таймстамп к атрибутам по которым строится когорта и усреднять его значение в ней.
В результате получилась интересная премиум-фича и несколько интересных открытых вопросов:
GDPR предполагает что по запросу мы должны уметь удалять все данные пользователя, но мы так постарались спрятать чьи-же это данные что теперь не можем найти. Имея данные по большому количеству разных срезов/когорт есть вероятность вычленить соответствия и расширить список открытых атрибутов
Этот подход работает для данных большой размерности, но не работает с непрерывными данными. Практика показывает что просто дискретизировать данные не очень хооршая идея, но Микрософт на NIPS2017 предложил [8]как с этим работать. К сожалению, детали уже расскрыть не успели.
Второй туториал по анализу больших графов начался после обеда. Несмотря на то, что вели его тоже ребята из Гугла и ожиданий от него было больше, понравился он гораздо меньше — рассказывали про свои закрытые технологии то пускаясь в банальщину и общую философию, то погружаясь в дикие детали не успев даже сформулировать задачу. Тем не менее некоторые интересные аспекты смог уловить. Слайды можно найти здесь [9].
Во первых, понравилась схема под названием ego-network clustering, думаю, на её основе можно построить интересные решения. Идея очень простая:
В подобном преобразованном графе многие проблемы решаются проще и алгоритмы ранжирования работают чище. Например, гораздо проще такой граф сбалансированно партиционировать, а при ранжировании в рекомендации друзей узлы-мосты гораздо меньше шумят. Именно для задачи рекомендации друзей ENC и рассматривали/промотировали.
Но в целом ENC был только примером — в Гуглу целый отдел занимается разработкой алгоритмов на графах и поставляет их другим отделам в качестве библиотеки. Заявленный функционал библиотеки впечатляет — либа мечты для SNA, но все закрыто. В лучшем случае отдельные блоки можно постараться воспроизвести по статьям. Утверждается что у либы сотни внедрений внутри Гугла, в том числе на графах с более чем триллионом ребер.
Далее было примерно минут 20 рекламной акции модели MapReduce, будто мы сами не знаем насколько оно круто. После чего ребята показали, что многие сложные задачи можно решить (приблизительно) по модели Randomized Composable Core Sets. Основная идея метода заключается в том, что данные о ребрах рандомно раскидываются на N узлов, там втягиваются в память и решается задача локально, после чего результаты решения передаются на центральную машину и там агрегируются. Утверждается что таким образом можно задешево получить хорошие аппроксимации для многих проблем — компоненты связности, минимальный остовный лес, макс матчинг, макс коверадж и т.д. В некоторых случаях, при этом, и на мэперах и в редьюсе решается одна и та же задача, но могут быть и немного разные. Наглядный пример того, что иногда ради того чтобы в простое решение поверили надо назавать его сложным умным образом.
Собственно затем пошел разговор про то, ради чего я сюда и шел — Balanced Graph Partitioning. Т.е. как порезать граф на N частей так, чтобы части были примерно равного размера, а количество связей внутри частей значительно превышало количество внешних связей. Если уметь хорошо решать такую задачу то очень многие алгоритмы становятся проще, и даже А/Б тесты можно запускать более качественно с компенсацией вирусного эффекта. Но рассказ немного разочаровал, все выглядело как «гномий план» — присваиваем номера на базе иерархической аффинной кластеризации, двигаем, добавляем имбаланс. Без деталей. Будет позже на КДД выделенный доклад от них же про это, попробую сходить. Плюс есть блогпост [10].
Тем не менее дали сравнение с некоторыми конкурентами в этой области, часть из них откырта: Spinner [11], UB13 [12] от FB, Fennel [13]от Микрософта, Metis [14]. Можно посмотреть и на них тоже.
Дальше немного рассказывали про технические детали. У них используется несколько парадигм работы с графами:
Идея ASYMP очень похожа на Pregel:
Например при поиске компонент связности инициализируем всем вершинам случайные веса U[0,1], после чего начинаем слать друг другу минимум по соседям. Соответственно получив от соседей их минимумы ищем минимум по ним и т.д. пока минимум не стабилизируется. Отмечают важный поинт для оптимизации — схлопывать сообщения от одной ноды (для этого и очередь), оставляя только последнее. Так же говорят про то, как легко делать восстановление после сбоев, сохраняя стейты нод.
Говорят что без гемора строят очень быстрые алгоритмы, похоже на правду — концепт простой и рациональный. Есть публикации [17].
В итоге напрашивается вывод — ходить на рассказы про закрытые технологии грустно, но некоторые полезные биты удается ухватить.
Автор: dmitrybugaychenko
Источник [18]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/data-mining/289816
Ссылки в тексте:
[1] здесь: https://sites.google.com/view/kdd2018-tutorial/home
[2] Differential Privacy: https://en.wikipedia.org/wiki/Differential_Privacy
[3] RAPPOR : https://github.com/google/rappor
[4] count-min-sketch: https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
[5] Hadamard transform: https://en.wikipedia.org/wiki/Hadamard_transform
[6] может быть скомпрометирована: https://arxiv.org/pdf/1709.02753
[7] k-Anonymity: https://en.wikipedia.org/wiki/K-anonymity
[8] предложил : https://papers.nips.cc/paper/6948-collecting-telemetry-data-privately.pdf
[9] здесь: https://drive.google.com/file/d/1KfdZVM9zSD290xrw7P_0rXWilpPYDCDM/view
[10] блогпост: https://ai.googleblog.com/2018/03/balanced-partitioning-and-hierarchical.html
[11] Spinner: https://arxiv.org/pdf/1404.3861
[12] UB13: https://web.stanford.edu/~jugander/papers/wsdm13-blp.pdf
[13] Fennel : https://www.microsoft.com/en-us/research/publication/fennel-streaming-graph-partitioning-for-massive-scale-graphs/
[14] Metis: http://glaros.dtc.umn.edu/gkhome/views/metis
[15] под названием dataflow: https://cloud.google.com/dataflow/
[16] тут: https://dl.acm.org/ft_gateway.cfm?id=2670997&type=pdf
[17] публикации: https://arxiv.org/pdf/1712.09731
[18] Источник: https://habr.com/post/420625/?utm_campaign=420625
Нажмите здесь для печати.