Box Graph: как мы создали спонтанную социальную сеть

Сеш Джалагам, старший инженер по персоналу

К настоящему времени ни для кого не секрет, что объем создаваемого и распространяемого контента растет в геометрической прогрессии. Чтобы извлечь пользу из всего этого контента, мы ввели Box Skills - фреймворк, который привносит инновации в машинное обучение в контент, хранящийся в Box. Например, видеоинтеллект, один из начальных навыков бокса, обеспечивает транскрипцию, определение темы и распознавание лиц для отдельных видеороликов. Но это только один файл за раз.

Мы также разрабатываем способ лучше понять ваш контент в масштабе, чтобы дать вам представление о взаимоотношениях между контентом и людьми. Когда пользователи сотрудничают друг с другом для выполнения своей работы, это сотрудничество может быть недолгим или длиться месяцами или дольше. Это действие неявно формирует спонтанную социальную сеть на вашем предприятии. В отличие от социальных сетей, управляемых пользователями, эта спонтанность требует распределенного графа в реальном времени, который вычисляет сеть.

Используйте Box Graph, нашу собственную модель машинного обучения, которая активно интерпретирует, а затем отображает, как работает ваша организация. Box Graph понимает отношения между контентом и другим контентом, контентом и людьми, а также людьми и людьми. Graph постоянно учится на всем, что вы делаете в Box: от общих ссылок, которые вы создаете, до партнеров, с которыми вы сотрудничаете.

На рисунке ниже показаны отношения между пользователями, которые сформировались в течение определенного периода на предприятии.

Из графика мы можем получить различную информацию:

пользователи склонны группироваться из-за выполняемой работы
некоторые кластеры изолированы
некоторые пользователи действуют как связующие, соединяющие кластеры
некоторые пользователи связаны гораздо больше, чем другие

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

Неявные сети

Ежедневно миллионы пользователей взаимодействуют с контентом на различных предприятиях для выполнения своей работы. Каждое взаимодействие вносит вклад в более широкую картину того, как работа выполняется в этой организации. Мы можем смотреть на взаимодействия пользователей (комментарии, просмотры, модификации и т. Д.) С контентом, чтобы понять, как пользователи взаимодействуют друг с другом, это формирует основу для блочного графика.

В приведенном выше примере:

Джо работает с File1, Сью работает с File2, а Боб работает с File3.
Как только Сью начинает взаимодействовать с File1, она устанавливает связь с Джо.
Точно так же, по мере того, как работа продвигается, все больше людей могут быть частью графика; в этом случае Боб имеет отношение как к Сью, так и к Джо

Это создает неявный межпользовательский граф, полученный из явного межпользовательского графа.

Эти неявные сети могут быть разных типов, которые могут существовать в файлах, местах, задачах и других объектах.

Построение масштабируемого графика в реальном времени

В нашей модели толщина края на графике представляет силу края, выраженную в баллах. Если пользователи тесно сотрудничают, они имеют более высокий балл. Рекомендуя файлы, мы рекомендуем наибольший вклад от лучших соавторов для пользователя (в приведенном выше примере Сью и Боб - лучшие соавторы Джо). Для этого график должен уметь:

В реальном времени вычислите баллы сотрудничества между пользователем и пользователем (чтобы определить лучших соавторов) от пользователя к взаимодействию с файлом.
Выполняйте эти вычисления оценок с высокой пропускной способностью и малой задержкой, чтобы они масштабировались до миллиардов ребер (для обработки трафика Box).
Составьте список лучших соавторов и лучших вкладов с малой задержкой (для быстрого выполнения рекомендаций)

Мы создали горизонтально масштабируемую систему с версионным графом, которая может размещать формулы оценки в реальном времени под названием Score Keeper Service (SKS), чтобы поддерживать отношения пользователя с пользователем и пользователя с файлом. Мы асинхронно обновляем граф на основе пользовательских событий, используя постоянную систему очередей с высокой пропускной способностью и малой задержкой, называемую службой очереди сообщений (MQS - это очередь гарантированной доставки с изоляцией и поддержкой QoS).

SKS построен на основе HBase с понятием каналов (разделение пространства имен), каждый канал может содержать один или несколько графиков. Формула определяет, как графы обновляются событиями и как извлекать верхние ребра для данной вершины.

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

На следующей диаграмме показан ключевой дизайн для таблицы оценок и ранжирования.

Где SourceType - это тип исходной вершины, а TargetType - это тип целевой вершины ребра. Вышеупомянутый дизайн гарантирует, что ScoreRowKey и RankRowKey будут иметь один и тот же префикс, увеличивает шансы на совместное размещение RankRows с ScoreRows, хеширование снижает количество горячих точек и обеспечивает разделение графиков на уровне каналов.

Обновление 4 миллиардов ребер в день

Обновления ребер с высокой пропускной способностью достигаются за счет:

Разделенные записи для каждого предприятия: все записи в определенный раздел сериализуются, что позволяет нам выполнять межстрочные транзакции для данного предприятия.
Использование пакетного API на всем пути от клиента к hbase: уменьшает количество вызовов
Удаление событий закрытия: уменьшает количество операций записи в hbase, когда наблюдается всплеск событий.
Накопление на уровне формулы: в сочетании с пакетной обработкой накопление на уровне формулы позволяет нам накапливать несколько изменений на одном ребре и выполнять одну запись в бэкэнд.

Срезы времени позволяют нам смотреть на снимки графиков такими, какими они были в данный момент времени. С помощью простой формулы подсчета и моментального снимка за день можно задать графу вопросы, например, сколько просмотров произошло за последние 7 дней. Или гораздо более сложные вопросы, например: покажите лучших пользователей, с которыми я работал месяц назад над этим проектом. Временное разделение графика достигается за счет использования управления версиями hbase и обеспечения для параметра KEEP_DELETED_CELLS значения true на HBase.

Формулы в реальном времени

Одним из ключевых требований к формулам для работы в реальном времени является то, что они имеют инкрементный характер и могут быть представлены как функция накопления.

Давность и частота
Теория, лежащая в основе блочного графика, - это наша собственная версия совместной фильтрации. В нашей версии мы думаем, что наши пользователи описываются вектором взаимодействия файлов. Запись вектора пользователя измеряет силу взаимодействия этого пользователя с соответствующим файлом. Мы оцениваем эту силу как сумму всех взаимодействий пользователя с файлом, как показано на графике ниже.

Сумма берется по всем наблюдаемым пользовательским событиям с этим файлом (все время, когда пользователь открывает, редактирует, комментирует, делится и т. Д.), T - текущее время, wᵢ - вес, связанный с событием (например, чтобы подчеркнуть, что редактирование означает более сильную связь с файлом, чем просто его открытие), а tᵢ - время события.

Параметр λ позволяет нам управлять компромиссом между новизной и частотой в зависимости от времени. Когда λ равно 0, формула сводится к подсчету количества взаимодействий пользователя с файлом. Если λ очень велико (и отрицательно), то только самое последнее событие будет вносить что-либо значимое в итоговую оценку. Чтобы иметь возможность постепенно обновлять счет в реальном времени, мы используем трюк LogSumExp.

Косинусное сходство

Каждого пользователя можно описать вектором с записью для каждого файла

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

Два пользователя считаются ближайшими соавторами, если у них одинаковые оценки сродства для одних и тех же файлов, и в этом случае их косинусное сходство равно 1. Если они никогда не работали с какими-либо общими файлами, их косинусное сходство равно 0. Это можно выразить как

Теперь мы можем сделать вывод о силе любых двух пользователей, наблюдая за взаимодействиями файлов, и сила этих отношений, естественно, уменьшается во времени и обновляется по мере того, как наблюдается больше событий.

На практике мы должны решить, как часто обновлять все оценки. Мы можем обновить все оценки (пользовательский файл, а также пользователь-пользователь) через определенные промежутки времени с помощью больших пакетных вычислений, мы можем выбрать обновление всех оценок по каждому событию, мы можем сделать некоторое приближение или мы можем использовать некоторая комбинация этих стратегий. Чтобы постепенно обновлять длину пользователя для каждого события пользовательского файла вместе с LogSumExp, мы используем трюк LogDiffExp.

Чтобы уловить характер сотрудничества в реальном времени, мы решили обновлять оценки на каждом мероприятии. Каждый раз, когда пользователь взаимодействует с файлом, эта запись в векторе пользователя изменяется, и отношения этого пользователя со всеми остальными также изменяются. Из-за большого количества пользователей, которые имеют клиенты Box, такое количество вычислений для каждого события невозможно. Вместо этого для каждого события мы придумываем приблизительное значение, обновляя оценки пользователь-пользователь только для подмножества других пользователей. Поскольку у большинства пользователей очень слабые отношения почти со всеми другими пользователями, разумный выбор оценок для обновления дает довольно хорошее приближение к полному обновлению. Мы храним логарифмическое значение числителя и знаменателя косинусного сходства, и с небольшими математическими упрощениями мы можем постепенно обновлять.

A / B-тестирование
Чтобы включить A / B-тестирование, нам нужно убедиться, что мы можем поддерживать несколько графиков с разными формулами. Ниже показана необходимая для этого установка. Первичная очередь может обновлять график с помощью формулы A, а вторичная очередь может обновлять графики с помощью формулы B. Эту настройку также можно использовать для разогрева формулы B перед выпуском, пока формула A активна.

Бэктестинг
Для реализации этого алгоритма необходимо сделать несколько вариантов - мы должны выбрать скорость затухания (λ), веса событий (wᵢ) и решить, как реализовать наш пользовательский -пользователь обновляет правило. Мы используем как бэктестинг, так и A / B-тестирование, чтобы понять влияние параметров или алгоритмов. Бэктестинг позволяет нам экспериментировать с разными формулами и разными параметрами. Это дает нам механизм для проверки формул, который может быть намного сложнее, чем совместная фильтрация, и дает представление о том, насколько далеко от других стратегий может быть наш текущий выбор.

Одна из проблем, характерных для Box, заключается в том, что при тестировании на исторических данных, как Graph может использоваться в различных продуктах для обслуживания файлов для пользователей (например, в Feed), мы должны учитывать права доступа к файлам - разрешено ли пользователю просматривать определенный файл на день, когда мы проводим бэктестинг? Права доступа к файлам в Box довольно сложны и слишком велики, чтобы их можно было денормализовать. Чтобы преодолеть эту проблему и масштабировать тестирование на истории для многих корпоративных клиентов, мы кэшируем минимальный объем исторических данных, необходимых для получения разрешений, и разработали схему «пакетного вычисления» разрешений поверх результатов тестирования, чтобы иметь более точное представление того, как продукт будет работать.

Поскольку он использует офлайн-данные, мы никогда не можем быть уверены, что результаты, полученные в офлайновом тестировании, сохранятся в продукте, но это доказало свою прямую актуальность. Напротив, A / B-тестирование дает нам гораздо более точный контроль над тем, что мы наблюдаем. Мы можем развернуть систему с различным выбором параметров и измерить, как пользователи взаимодействуют с функциями, построенными на вершине графика. Это помогает нам понять, какие значения параметров работают лучше всего и какие тесты запускать дальше.

Люди собираются вместе, чтобы выполнить свою работу, чтобы уловить эту спонтанную природу, нам понадобился график в реальном времени. Мы создали прямоугольный график с высокой пропускной способностью в реальном времени, используя структуры данных, оптимизированные для извлечения данных по верхним краям и обновления краев с малой задержкой. Воспользовавшись некоторыми математическими приемами и оптимизацией обработки, мы создали формулы для совместной фильтрации, позволяющие вычислять рекомендации в реальном времени. С помощью бэктестинга и A / B-тестирования мы можем точно настроить параметры формулы для различных уникальных сценариев использования в Box.

Box Graph: как мы создали спонтанную социальную сеть

Неявные сети

Построение масштабируемого графика в реальном времени

Обновление 4 миллиардов ребер в день

Формулы в реальном времени

Вопросы по теме