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

Помню, как меня впервые попросили дать оценку

Тогда это застало врасплох.

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

Аналитики зачитали некоторые требования от клиента. Мы их коротко обсудили.

И тут мой начальник повернулся ко мне и спросил: Сколько времени это займет?

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

И вдруг на меня все смотрят и ждут ответа, а я растерялся и не знаю, что сказать.

Передо мной лежала бумага для заметок. Я взял один листок и начал писать какие-то числа без понятия, для чего, но точно не для этой оценки.

Где-то через минуту, которая показалась мне часом, я решил просто сказать первое, что пришло в голову: Не знаю часов 600?

Начальник рассмеялся, а затем сказал остальным рассчитывать на примерно 1200часов.

Не очень люблю вспоминать тот день.

Понятно, что мне еще многое предстояло узнать, но меня мучил один вопрос: как оценивать объем предстоящей работы?

Цель проведения оценки

Прежде чем приступать к оценке, нужно понять, для чего она будет использоваться. Вы сообщите цифры начальнику или вышестоящему руководству и что будет дальше?

Оценка объема работы используется в основном в двух целях:

• Планирование.

• Выставление счета клиенту.

Планирование

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

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

Допустим, в вашей команде разработчиков три человека. Каждый работает по 40часов в неделю это примерно 160часов в месяц, или 480часов в квартал (на троих примерно 1500часов).

Представьте, что ваша команда должна выполнить пять проектов с оценками объемов работ 800, 400, 300, 200 и 50часов. Планируя загрузку, вы будете видеть, что не сможете к концу квартала выполнить все проекты. Менеджеры составят график, использующий определенный процент максимальной загрузки на случай, если разработка займет больше времени, чем предполагалось.

С оценками из нашего примера можно было бы взяться за проекты на 800, 400 и 50часов, и при этом осталась бы некоторая свобода для маневра.

Выставление счета клиенту

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

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

Примечание. Это применимо не ко всем компаниям разработчикам ПО: не все занимаются разработкой на заказ. Если вы не разрабатываете ПО на заказ, то оценки объема работ будут использоваться в основном для планирования.

Ключевые факторы при оценке

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

1. Не оценивайте, сколько времени понадобится ВАМ

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

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

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

2. Не занижайте завышайте

Помните, что в первую очередь оценка делается для планирования. Поэтому не нужно давать цифры, которые, по вашему мнению, могут быть превышены.

Если разработчики выйдут за отведенный вами срок, это нарушит график работ.

Находиться в границах 20% это нормально, но только если оценка оказалась завышена а не занижена.

К какой бы цифре вы ни пришли, добавьте к ней 20%: задачи обычно оказываются сложнее в реализации, чем кажется.

3. Повышение квалификации

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

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

4. Примеры аналогичных проектов

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

Если у команды имеется некий опорный материал в виде ранее разработанного ПО, то объем работы может значительно снизиться. Разработчикам проще действовать по принципу копировать, вставить, заменить, и это отражается на скорости выполнения задач.

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

5. Не забывайте об аналитиках

Часто вас будут просить дать полную оценку, а она включает в себя время разработчиков, бизнес-аналитиков и специалистов по обеспечению качества.

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

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

Заключение

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

Со временем оценки будут даваться вам всё легче. Запомните перечисленные моменты, научитесь понимать, сколько времени занимает разработка определенных элементов, и полагайтесь на свой опыт.

Если резюмировать самое главное, запомните вот что:

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

Никто не будет злиться, если у вас всё пойдет по плану, начальство даже порадуется! И при этом у вас останется больше времени на другие проекты.

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

О переводчике

Перевод статьи выполнен в Alconost.

Alconost занимается локализацией игр, приложений и сайтов на 70 языков. Переводчики-носители языка, лингвистическое тестирование, облачная платформа с API, непрерывная локализация, менеджеры проектов 24/7, любые форматы строковых ресурсов.

Мы также делаем рекламные и обучающие видеоролики для сайтов, продающие, имиджевые, рекламные, обучающие, тизеры, эксплейнеры, трейлеры для Google Play и App Store.

Перед вами вторая часть руководства по антипаттернам деплоя в Kubernetes. Советуем также ознакомиться с первой частью.

Список антипаттернов, которые мы рассмотрим:

1. Использование образов с тегом latest

2. Сохранение конфигурации внутри образов

3. Использование приложением компонентов Kubernetes без необходимости

4. Использование для деплоя приложений инструментов для развёртывания инфраструктуры

5. Изменение конфигурации вручную

6. Использование кubectl в качестве инструмента отладки

7. Непонимание сетевых концепций Kubernetes

8. Использование неизменяемых тестовых окружений вместо динамических сред

9. Смешивание кластеров Production и Non-Production

10. Развёртывание приложений без Limits

11. Неправильное использование Health Probes

12. Не используете Helm

13. Не собираете метрики приложений, позволяющие оценить их работу

14. Отсутствие единого подхода к хранению конфиденциальных данных

15. Попытка перенести все ваши приложения в Kubernetes

6. Использование кubectl в качестве инструмента отладки

Утилита kubectl незаменима при работе с кластерами Kubernetes. Но не стоит использовать её как единственный отладочный инструмент.

При возникновении проблем, особенно в production кластере, вашим первым импульсом не должен быть запуск kubectl. Если вы поступаете именно так, то вы уже проиграли битву, особенно если сейчас 3 часа ночи, сервисы не работают, и вы на связи.

kubectl get nskubectl get pods -n saleskubectl describe pod prod-app-1233445 -n saleskubectl get svc - n saleskubectl describe...

Вместо этого все ваши кластеры Kubernetes должны иметь надлежащие системы мониторинга, трассировки и сбора логов, которые можно использовать для своевременного выявления проблем. Если вам нужно запустить kubectl для проверки чего-либо, это означает, что вы не учли это, настраивая вашу систему мониторинга.

Сложно переоценить ценность метрик и трассировок, мы расскажем о них отдельно в одном из следующих антипаттернов.

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

Например, обратите внимание на Kubevious, это универсальная панель управления Kubernetes, которая позволяет вам искать и отображать ресурсы Kubernetes в соответствии с настраиваемыми правилами.

7. Непонимание сетевых концепций Kubernetes

Прошли те времена, когда единственный балансировщик нагрузки был всем, что необходимо для настройки подключения к вашему приложению. Kubernetes представляет свою собственную сетевую модель, и вам нужно разобраться с её основными концепциями. По крайней мере, вы должны быть знакомы с типами сервисов - Load Balancer, Cluster IP, Node Port и понимать, чем сервисы отличаются от Ingress.

Сервисы типа Сluster IP используются внутри кластера, Node Port также могут использоваться внутри кластера, но при этом доступны снаружи, а балансировщики нагрузки могут принимать только входящий трафик.

Но это ещё не всё потребуется разобраться, как в кластере Kubernetes работает DNS. И не забывать, что весь трафик между служебными компонентами шифруется и нужно контролировать срок действия сертификатов.

Будет полезно разобраться, что такое Service Mesh и какие проблемы она решает. Необязательно разворачивать Service Mesh в каждом кластере Kubernetes. Но желательно понимать, как она работает и зачем вам это нужно.

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

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

8. Использование неизменяемых тестовых окружений вместо динамических сред

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

Один из наиболее распространенных подходов наличие как минимум трех сред (QA / Staging / Production), в зависимости от размера компании их может быть больше. Наиболее важной из них является интеграционная, которая содержит результат слияния всех обновлений с основной веткой.

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

Если вы используете единое окружение для интеграции, когда несколько разработчиков выполняют слияние результатов работы и что-то ломается, не сразу становится понятно, какая из функций вызвала проблему. Если 3 разработчика объединяют свои функции в промежуточной среде и развертывание завершается неудачно (либо сборка завершается неудачно, либо тесты интеграции терпят неудачу, либо показатели взрываются...), тогда существует несколько сценариев:

1. Обновление A содержит ошибки, B и C в порядке

2. Обновление B содержит ошибки, A и C в порядке

3. Обновление C содержит ошибки, B и A в порядке

4. Каждое обновление в отдельности работает, но при работе вместе с обновлениями A и B возникает ошибка

5. Каждое обновление в отдельности работает, но при работе вместе с обновлениями A и C возникает ошибка

6. Каждое обновление в отдельности работает, но при работе вместе с обновлениями B и C возникает ошибка

7. Каждое обновление в отдельности работает, но все 3 обновления вместе не работают

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

Способы избежать подобных проблем:

1. "Резервирование" промежуточного (stage) окружения разработчиками, чтобы они имели возможность тестировать свои обновления изолированно.

2. Компания создает несколько staging сред, которые разработчики используют для тестирования своих обновлений (поскольку единственное staging окружение может быстро стать узким местом).

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

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

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

Есть много способов реализовать этот сценарий, по крайней мере, каждый запрос Pull Request должен создавать динамическую среду, содержащую только этот запрос Pull Request и ничего больше. Среда автоматически уничтожается, когда Pull Request объединяется / закрывается или по прошествии определенного времени.

Преимущество динамических сред это полная свобода разработчиков. Если я разработчик и только что закончил работу с обновлением A, а мой коллега завершил работу над обновлением B, я должен иметь возможность:

git checkout mastergit checkout -b feature-a-b-togethergit merge feature-agit merge feature-bgit push origin feature-a-b-together

Как по волшебству, будет создана динамическая среда:feature-a-b-together.staging.company.comилиstaging.company.com/feature-a-b-together.

Для создания динамических сред вы можете использовать, например, пространства имен Kubernetes.

Обратите внимание, что это нормально, если у вашей компании есть постоянные staging среды для специализированных нужд, таких как нагрузочное тестирование, тестирование на проникновения, развертывание A / B и т. д. Но для базового сценария Я разработчик и хочу, чтобы моё обновление работало изолированно и запускались интеграционные тесты динамические среды лучшее решение.

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

9. Смешивание кластеров Production и Non-Production

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

Прежде всего, смешивание Production и Non-Production кластеров может привести к нехватке ресурсов.

Так как приложение, работающее некорректно, может утилизировать слишком много ресурсов.

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

Пространства имен Kubernetes не являются мерой безопасности. Если ваша команда обладает глубокими знаниями Kubernetes, то действительно можно поддерживать мультитенантность внутри кластера и защищать все рабочие нагрузки друг от друга. Но это требует значительных усилий, и в большинстве случаев гораздо проще создать второй кластер исключительно для production.

Если вы объедините этот антипаттерн со вторым (сохранение конфигурации внутри образов), должно стать очевидно, что может произойти множество негативных сценариев, например:

1. Разработчик создает новое пространство имен, используемое для тестирования и production.

2. Далее развертывается приложение и запускаются интеграционные тесты.

3. Интеграционные тесты записывают фиктивные данные или очищают БД.

4. К сожалению, в контейнерах были рабочие URL-адреса и конфигурация внутри них, и, таким образом, все интеграционные тесты фактически повлияли на работу production!

Чтобы не попасть в эту ловушку, гораздо проще просто создать Production и Non-Production кластера. К сожалению, многие руководства описывают сценарий при котором, пространства имен можно использовать для разделения сред, и даже в официальной документации Kubernetes есть примеры с пространствами имен prod / dev.

Обратите внимание, что в зависимости от размера вашей компании у вас может быть больше кластеров, чем два, например:

1. Production

2. Pre Production (Shadow) клон production, но с меньшими ресурсами

3. Development кластер, который мы уже обсуждали выше

4. Специализированный кластер для нагрузочного тестирования / тестирования безопасности

5. И даже отдельный кластер для служебных инструментов

10. Развёртывание приложений без Limits

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

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

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

Одно из преимуществ Kubernetes эластичность ресурсов. Если кластер убивает / перезапускает ваше приложение, когда оно начинает обрабатывать значительную нагрузку (например, ваш интернет-магазин испытывает всплеск трафика), вы не используете все преимущества Kubenetes. Вы можете решить эту проблему с использованием vertical pod auto-scaler (VPA).

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

Меня зовут Женя Замятин, я работаю в команде Core ML ВКонтакте. Хочу рассказать, как устроены рекомендации, которые делают ближе пользователей самой крупной социальной сети рунета.

Обзор

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

Прежде всего сформулируем задачу, которую будем решать: для каждого пользователя необходимо найти k кандидатов, которых он с наибольшей вероятностью добавит в друзья. Метрика, на которую будем ориентироваться, recall@k. Она идеально описывает задачу: на первом уровне нам не интересен порядок кандидатов, но важна их релевантность.

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

Ещё один важный метод рекомендаций Adamic/Adar. В его основе лежит всё тот же анализ общих друзей, но с модификацией: авторы предлагают учитывать число друзей у общего друга. Чем больше это значение, тем меньше информации о релевантности он несёт.

Кроме методов на основе анализа общих друзей, довольно распространены рекомендации на базе эмбеддингов. В Лаборатории искусственного интеллекта ВКонтакте в МФТИ мы провели исследование: сравнили эффективность разных подходов к задаче предсказания дружб в VK. Результаты совпали с нашим опытом решения на базе графовых эмбеддингов у нас работают плохо. Учитывая это, мы стали развивать систему отбора кандидатов по пути анализа общих друзей.

EGOML

Общая схема нашего метода продолжает идеи числа общих друзей и Adamic/Adar. Финальная мера релевантности E(u, v), с помощью которой мы будем отбирать кандидатов, всё так же раскладывается в сумму по общим друзьям u и v. Ключевое отличие в форме слагаемого под суммой: в нашем случае это мера ez_c(u, v).

Сначала попробуем понять физический смысл меры ez_c(u, v). Представим, что мы взяли пользователя c и спросили у него: Насколько вероятно, что два твоих друга, u и v, подружатся? Чем больше информации для оценки он учтёт, тем точнее будет его предсказание. Например, если c сможет вспомнить только число своих друзей, его рассуждения могут выглядеть следующим образом: Чем больше у меня друзей, тем менее вероятно, что случайные двое из них знакомы. Тогда оценка вероятность дружбы u и v (с точки зрения c) может выглядеть как 1/log(n), где n число друзей. Именно так устроен Adamic/Adar. Но что если c возьмёт больше контекста?

Прежде чем отвечать на этот вопрос, разберёмся, почему ez_c(u, v) важно определять через пользователя c. Дело в том, что в таком виде очень удобно решать задачу распределённо. Представим, что теперь мы разослали всем пользователям платформы анкету с просьбой оценить вероятность дружбы в каждой паре их друзей. Получив все ответы, мы можем подставить значения в формулу E(u, v). Именно так выглядит вычисление E(u, v) с помощью MapReduce:

• Подготовка. Для каждого c выделяется тот контекст, который он будет учитывать для вынесения оценок. Например, в Adamic/Adar это будет просто список друзей.

• Map. Спрашиваем у каждого c, что он думает про возможность дружбы в каждой паре его друзей. По сути, вычисляем ez_c(u, v) и сохраняем в виде (u, v) ez_c(u, v) для всех u, v in N(c). В случае Adamic/Adar: (u, v) 1/log|N(c)|.

• Reduce. Для каждой пары (u, v) суммируем все соответствующие ей значения. Их будет ровно столько, сколько общих друзей у u и v.

Таким образом мы получаем все ненулевые значения E(u, v). Заметим: необходимое условие того, что E(u, v) > 0, существование хотя бы одного общего друга у u и v.

Контекстом пользователя c в случае меры ez_c будет тот же список друзей, но дополненный информацией о связях внутри этого списка. Такую структуру в науке называют эго-графом. Если более формально, эго-граф вершины x это такой подграф исходного графа, вершинами которого являются все соседи x и сама x, а рёбрами все рёбра исходного графа между этими вершинами. Коллеги из Одноклассников написали подробную статью об эго-графах и затронули в ней вопрос их эффективного построения.

Ключевая идея меры ez_c в том, что её можно сделать обучаемой. Для каждого пользователя c, его эго-графа и всех пар пользователей u, v внутри него мы можем посчитать много разных признаков, например:

• число общих друзей u и v внутри эго-графа c;

• число общих друзей u и c;

• интенсивность взаимодействий между v и c;

• время, прошедшее с последней дружбы между u и кем-либо из эго-графа c;

• плотность эго-графа c;

• и другие.

Таким образом мы получим датасет с признаками. Но для обучения нужны ещё и метки. Пусть датасет был построен по состоянию графа на момент времени T. Тогда в качестве положительных примеров возьмём те пары пользователей, которые не были друзьями на момент T, но подружились к T + T. А как отрицательные все остальные, не подружившиеся, пары пользователей. Заметим: поскольку мы решаем задачу предсказания новых дружб, те пары пользователей, которые уже дружат на момент T, учитывать не нужно ни на обучении, ни на применении.

В конечном счёте мы получаем датасет следующего вида:

• для каждой пары пользователей u и v, а также их общего друга c, посчитаны признаки по эго-графу c;

• пара пользователей u и v встречается в датасете ровно столько раз, сколько у них общих друзей;

• все пары пользователей в датасете не являются друзьями на момент времени T;

• для каждой пары u и v проставлена метка подружились ли они в течение определённого промежутка времени начиная с T.

По такому датасету мы и будем обучать нашу меру ez_c. В качестве модели выбрали градиентный бустинг с pairwise функцией потерь, где идентификатором группы выступает пользователь u.
По сути, мера ez_c(u, v) определяется как предсказание описанной выше модели. Но есть один нюанс: при pairwise-обучении распределение предсказаний модели похоже на нормальное. Поэтому, если в качестве определения меры ez_c(u, v) взять сырое предсказание, может возникнуть ситуация, когда мы будем штрафовать финальную меру E(u, v) за общих друзей, так как значения предсказаний бывают отрицательными. Это выглядит не совсем логично хочется, чтобы с ростом числа общих друзей мера E(u, v) не убывала. Так что поверх предсказания модели мы решили взять экспоненту:

Такой подход хорошо себя показывает на небольших графах. Но чтобы применить его на реальных данных, необходимо выполнить ещё одно действие. Суть проблемы такая: мы не можем вычислять признаки и применять модель для каждой пары пользователей всех эго-графов это слишком долго. Для решения мы придумали специальный трюк. Представим, что наш градиентный бустинг обучился таким образом, что каждое дерево использует признаки только одного пользователя: либо u, либо v. Тогда мы могли бы разделить весь ансамбль на две группы: к группе A мы бы отнесли деревья, которые используют только признаки пользователя u, к B пользователя v. Предсказание такой модели можно представить в виде:

Имея такую модель, мы могли бы получить предсказания для всех пар пользователей одного эго-графа быстрее. Достаточно применить модели A и B для каждого пользователя, а затем сложить соответствующие парам предсказания. Таким образом, для эго-графа из n вершин мы могли бы сократить число применений модели с O(n^2) до O(n). Но как получить такую модель, каждое дерево которой зависит только от одного пользователя? Для этого сделаем следующее:

1. Исключим из датасета все признаки, которые одновременно зависят и от u и от v. Например, от признака число общих друзей u и v внутри эго-графа c придётся отказаться.

2. Обучим модель A, используя только признаки на базе u, c и эго-графа c.

3. Для обучения модели B оставим только признаки на базе v, c и эго-графа c. Также в качестве базовых предсказаний передадим предсказания модели A.

Если объединим модели A и B, получим то что нужно: первая часть использует признаки u, вторая признаки v. Совокупность моделей осмысленна, поскольку B была обучена корректировать предсказания A. Эта оптимизация позволяет ускорить вычисления в сотни раз и делает подход применимым на практике. Финальный вид ez_c(u, v) и E(u, v) выглядит так:

Вычисление меры E в онлайне

Заметим, что E(u, v) можно представить в виде:

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

При построении рекомендаций мы уже вычислили предсказания моделей для всех существующих дружб. Поэтому для каждого пользователя мы можем собрать векторы и сложить их в доступное онлайн key-value хранилище. После этого сможем получать значение E(u, v) для любой пары пользователей в онлайне простой операцией перемножения векторов. Это даёт возможность использовать E(u, v) как лёгкую функцию релевантности в нагруженных местах либо как дополнительный признак финальной модели ранжирования.

Итог

В результате система EGOML позволяет:

1. Распределённо отбирать кандидатов для каждого пользователя в офлайне. Асимптотическая сложность оптимизированного алгоритма составляет O(|E|) вычислений признаков и применений модели, где |E| число связей в графе. На кластере из 250 воркеров время работы алгоритма составляет около двух часов.

2. Быстро вычислять меру релевантности E(u, v) для любой пары пользователей в онлайне. Асимптотическая сложность операции O(|N(u)| + |N(v)|).

3. Улучшать качество рекомендаций, расширяя количество учтённых графов (по дружбам, скрытиям рекомендаций, отправленным сообщениям и другим графам) и добавляя всевозможные метки на рёбра и вершины. Например, интенсивность взаимодействий на ребре, дату образования ребра, город, место работы или учёбы пользователя.

В конечном счёте мы перешли со способа отбора кандидатов с использованием Adamic/Adar к системе EGOML и внедрили в модель второй уровень признаков на основе меры E(u, v). И это позволило увеличить количество подтверждённых дружб со всей платформы на несколько десятков процентов.

Благодарность

Хочу сказать спасибо руководителю команды Core ML Андрею Якушеву за помощь в разработке метода и подготовке статьи, а также всей команде Core ML за поддержку на разных этапах этой работы.