Сегодня в Лондоне стартовала одна из главных Data Science конференций года, постараюсь оперативно рассказывать о том, что интересного удалось услышать.
Начало выдалось нервным — в то же утро в этом же центре организовалась массовая встреча свидетелей иеговы, поэтому найти стойку регистрации КДД было не просто, а когда в итоге нашел — очередь на регистрацию была длиною метров 150-200. Тем не менее после ~20 минут ожидания получил вожделенный бэйдж и оправился на воркшоп.
Приватность в анализе данных
Первый туториал был посвящен сохранению приватности при анализе данных. На начало я опоздал, но, судя по всему, особо ничего не потерял — там рассказывали о том что приватность важно и как могут злоумышленники нехорошо использовать расскрытую приватную информацию. Рассказывают, кстати, вполне уважаемые люди от Гугла, ЛинкедИн-а и Эпла. По итогам воркшоп оставил очень положительное впечатление, слайды все доступны здесь.
Оказывается уже достаточно давно существует концепция Differential Privacy, онсновная идея которого заключается в том, чтобы добавлять шум, затрудняющий установление истинных индивидуальных значений, но сохраняющий возможность восстановление общих распределений. Собственно есть два параметра e — насколько сложно раскрыть данные и d — насколько искажены ответы.
В оригинале концепции предполагается что между аналитиком и данным присутствует некоторое промежуточное звено — «Куратор» — именно он обрабатывает все запросы и формирует ответы так, чтобы шум скрывал приватные данные. В реальности часто используется модель Local Differential Privacy когда данные пользователя остаются на устройстве пользователя (например, мобильном телефоне или ПК), но при ответе на запросы разработчика приложение с личного устройства отправляется такой пакет данных, который не позволяет выяснить что же именно ответил данный конкретный пользователь, но, при объединении ответов от большого числа пользователей можно с высокой точностью восстановить общую картину.
Хороший пример — опрос о том, «делали ли вы аборт». Если делать опрос «в лоб», то правду никто не скажет. Но если организовать опрос следующим образом «подкиньте монетку, если будет орел, то кидайте еще раз и на орла говорите да, а на решку нет, иначе ответьте правду» легко получается восстановить истинное распределение при сохранении индивидуальной приватности. Развитием этой идеи стала механика сбора чувствительной статистики от гугла RAPPOR (RAndomized Privacy-Preserving Ordinal Report), использовавшийся для сбора некоторой статистики об использовании браузера Chrome и его форков.
Сразу после выхода Хрома в опенсоурс появилось достаточно большое количество желающих сделать собственный браузер с переопределенной домашней страницей, поисковым движком, собственными рекламными плашками и т.д. Естественно пользователи и гугл от этого были не в восторге. Дальнейшие действия в целом понятны — выяснить наиболее распространенные подмены и придавить административно, но вышел нежданчик… Политика приватности хрома не позволяла гуглу взять и собрать информацию о настройке домашней страницы и поисковика пользователя на сервак :(
Чтобы преодолеть это ограничение и появился RAPPOR, который работает следующим образом:
- Данные по домашней странице записываются в небольшой, порядка 128 бит, Блум фильтр.
- К этому блум фильтру добавляется перманентный белый шум. Перманентный = одинаковый для этого юзера, без сохранения шума множественными запросами можно было бы расскрыть данные юзера.
- Поверх постоянного шума накладывается индвидуальный шум, генерируемый на каждый запрос.
- Получившийся битовый вектор отсылается гуглу, где начинается дешифровка общей картины
- Сначала статистическими методами вычитаем из общей картины эффект от шума
- Далее строим битовые вектора кандидатов (самые популярные сайты/поисковики по инету в принципе)
- Используя полученные вектора в качестве базиса строим линейную регрессию для восстановления картины
- Комбинируем линейную регрессию с ЛАССО для подавления иррелевантных кандидатов
Схематично построение фильтра выглядит так:
Опыт внедрения RAPPOR оказался очень позитивен и количество приватных статистик с помощью него собранных быстро увеличивалось. Среди основных факторов успеха авторы выделили:
- Простоту и понятность модели
- Открытость и документированность кода
- Наличие на итоговых графиках границ ошибок
Однако, у такого подхода есть и существенное ограничение — необходимо иметь списки ответов-кандидатов для расшифровки (именно поэтому и O — Ordinal). Когда компания Apple начать собирать статистику об используемых в текстовых сообщениях словах и эмоджи стало понятно что этот подход не годится. В результате на конференции WDC-2016 одной из топовых новых заявленных фич в ИОС стало добавление differential privacy. В качестве основы также была использована комбинация структуры-скетча с добавлением шума, однако пришлось решить много технических проблем:
- Клиент (телефон) должен иметь возможность за разумное время этот ответ построить и вместить в память
- Далее этот ответ должен быть упакован в ограниченное по размеру сетевой сообщение
- В итоге на стороне Эпла все это должно быть агрегируемо за разумное время
В итоге пришли к схеме с использование count-min-sketch для кодирования слов, далее выбирался ответ только одной из хеш-функций случайным образом (но с фиксацией выбора для пары юзер/слово), вектор преобразовывался с помощью Hadamard transform и на сервер слался только один значащий «бит» для выбранной хеш-функции.
В итоге для восстановления результата на сервер так же надо было просмотреть гипотезы-кандидаты, но, выяснилось что при большом размере словаря даже для кластера это слишком сложно. Нужно было как-то эвристически выбирать наиболее перспективные направления поиска. Эксперимент с использование биграм как начальных точек из которых затем можно собрать пазл оказался неудачным — все биграммы были примерно одинаково популярны. Подход биграмма+хеш слова решал проблему, но вел к нарушению приватности. В итоге остановились на префиксных деревьях — статистика собиралась по начальным частям слова и далее по слову целиком.
Анализ используемого Эпл алгоритма приватности исследовательским сообществом, тем не менее, показал что при долговременном сборе статистики приватность все-таки может быть скомпрометирована.
В более сложной ситуации оказался LinkedIn в исследовании о распределении зарплат пользователей. Дело в том, что differential privacy хорошо работает когда у нас есть очень большое количество измерений, иначе не удается надежно вычесть шум. В зарплатом же опросе количество отчетов ограничено и линкедин решил пойти по другому пути: совместить технические инструменты криптографии и кибербезопасности с концепцией k-Anonymity — данные пользователя считаются достачно замаскированны если подавать их пачкой где есть к ответов с одинаковыми входными атрибутами (например, локация и профессия) и отличающиеся только целевой переменной (зарплата).
В итоге был построен комплексный пайплайн где разные сервисы передают друг другу куски данных постоянно шифруя так, что раскрыть их целиком не может одна отдельно взятая машина. В итоге пользователи бьются на когорты по их атрибутам и по достижению когортой минимального размера её стата уходит в ХДФС для анализа.
Отдельного внимания заслуживает таймстамп — его так же необходимо анонимизировать, иначе имеется возможность выяснить чей-же это ответ по логу заходов. Но целиком убирать время не хочется — ведь интересно следить за динамикой. В итоге решили добавить таймстамп к атрибутам по которым строится когорта и усреднять его значение в ней.
В результате получилась интересная премиум-фича и несколько интересных открытых вопросов:
GDPR предполагает что по запросу мы должны уметь удалять все данные пользователя, но мы так постарались спрятать чьи-же это данные что теперь не можем найти. Имея данные по большому количеству разных срезов/когорт есть вероятность вычленить соответствия и расширить список открытых атрибутов
Этот подход работает для данных большой размерности, но не работает с непрерывными данными. Практика показывает что просто дискретизировать данные не очень хооршая идея, но Микрософт на NIPS2017 предложил как с этим работать. К сожалению, детали уже расскрыть не успели.
Анализ больших графов
Второй туториал по анализу больших графов начался после обеда. Несмотря на то, что вели его тоже ребята из Гугла и ожиданий от него было больше, понравился он гораздо меньше — рассказывали про свои закрытые технологии то пускаясь в банальщину и общую философию, то погружаясь в дикие детали не успев даже сформулировать задачу. Тем не менее некоторые интересные аспекты смог уловить. Слайды можно найти здесь.
Во первых, понравилась схема под названием ego-network clustering, думаю, на её основе можно построить интересные решения. Идея очень простая:
- Рассматриваем локальный граф с точки зрения конкретного пользователя, НО за вычетом его самого
- Кластеризуем этот граф
- Далее «клонируем» вершину нашего пользователя добавляя по экземпляру на каждый кластер и не связывая их друг с другом ребрами
В подобном преобразованном графе многие проблемы решаются проще и алгоритмы ранжирования работают чище. Например, гораздо проще такой граф сбалансированно партиционировать, а при ранжировании в рекомендации друзей узлы-мосты гораздо меньше шумят. Именно для задачи рекомендации друзей ENC и рассматривали/промотировали.
Но в целом ENC был только примером — в Гуглу целый отдел занимается разработкой алгоритмов на графах и поставляет их другим отделам в качестве библиотеки. Заявленный функционал библиотеки впечатляет — либа мечты для SNA, но все закрыто. В лучшем случае отдельные блоки можно постараться воспроизвести по статьям. Утверждается что у либы сотни внедрений внутри Гугла, в том числе на графах с более чем триллионом ребер.
Далее было примерно минут 20 рекламной акции модели MapReduce, будто мы сами не знаем насколько оно круто. После чего ребята показали, что многие сложные задачи можно решить (приблизительно) по модели Randomized Composable Core Sets. Основная идея метода заключается в том, что данные о ребрах рандомно раскидываются на N узлов, там втягиваются в память и решается задача локально, после чего результаты решения передаются на центральную машину и там агрегируются. Утверждается что таким образом можно задешево получить хорошие аппроксимации для многих проблем — компоненты связности, минимальный остовный лес, макс матчинг, макс коверадж и т.д. В некоторых случаях, при этом, и на мэперах и в редьюсе решается одна и та же задача, но могут быть и немного разные. Наглядный пример того, что иногда ради того чтобы в простое решение поверили надо назавать его сложным умным образом.
Собственно затем пошел разговор про то, ради чего я сюда и шел — Balanced Graph Partitioning. Т.е. как порезать граф на N частей так, чтобы части были примерно равного размера, а количество связей внутри частей значительно превышало количество внешних связей. Если уметь хорошо решать такую задачу то очень многие алгоритмы становятся проще, и даже А/Б тесты можно запускать более качественно с компенсацией вирусного эффекта. Но рассказ немного разочаровал, все выглядело как «гномий план» — присваиваем номера на базе иерархической аффинной кластеризации, двигаем, добавляем имбаланс. Без деталей. Будет позже на КДД выделенный доклад от них же про это, попробую сходить. Плюс есть блогпост.
Тем не менее дали сравнение с некоторыми конкурентами в этой области, часть из них откырта: Spinner, UB13 от FB, Fennel от Микрософта, Metis. Можно посмотреть и на них тоже.
Дальше немного рассказывали про технические детали. У них используется несколько парадигм работы с графами:
- MapReduce поверх Flume. Не знал что так можно — Flume ведь для сбора а не для анализа данных, в Интернете тоже не пишут особо. Думаю, что это внутригугловое извращение. UPD: Выяснил что это действительно внутренний продукт Гугла ничего общего с Apache Flume не имеющий, есть некоторый его эрзац в облаке под названием dataflow
- MapReduce + Distributed Hash Table. Говорят что помогает значительно сократить число раундов МР, но в инете про эту методику тоже не так много написано, например тут
- Pregel — говорят что скоро сдохнет
- ASYnchronous Message Passing — самая крутая, быстрая и перспективная
Идея ASYMP очень похожа на Pregel:
- узлы распределены, держат свой стэйт и могу послать мессадж соседям
- на машине строится очередь с приоритетами что куда слать (порядок может отличаться от порядка добавления)
- получив сообщение узел может поменять или не поменять состояние, при изменении шлем сообщение соседям
- заканчиваем когда все очереди пустые
Например при поиске компонент связности инициализируем всем вершинам случайные веса U[0,1], после чего начинаем слать друг другу минимум по соседям. Соответственно получив от соседей их минимумы ищем минимум по ним и т.д. пока минимум не стабилизируется. Отмечают важный поинт для оптимизации — схлопывать сообщения от одной ноды (для этого и очередь), оставляя только последнее. Так же говорят про то, как легко делать восстановление после сбоев, сохраняя стейты нод.
Говорят что без гемора строят очень быстрые алгоритмы, похоже на правду — концепт простой и рациональный. Есть публикации.
В итоге напрашивается вывод — ходить на рассказы про закрытые технологии грустно, но некоторые полезные биты удается ухватить.
Автор: dmitrybugaychenko
