Всем привет! Меня зовут Андрей Русланцев, я Senior Machine Learning Engineer в команде матчера в AliExpress Россия. И это статья для тех, кто предпочитает читать, а не смотреть видео — в ней я расскажу о том, как мы сделали матчер: какие проблемы нам пришлось решить, какие модели мы использовали, как выглядит наш текущий пайплайн, и почему наш матчинг действительно супер.

Матчер: что, зачем и почему

Матчинг — это процесс сопоставления объектов между собой. Зачем маркетплейсу матчинг? Сопоставляя товары, мы можем определять оптимальную цену и сравнивать наши предложения с предложениями конкурентов, «склеивать» карточки одного и того же товара, который предлагают несколько продавцов, мониторить ассортимент.

Казалось бы: берите и сравнивайте каждый товар с каждым — но на практике все не так просто. Для декартова произведения миллиона товаров на миллион товаров расчет их похожести потребует огромных вычислительных ресурсов. Не так давно на kaggle проходил конкурс по созданию матчера, и лучшее решение выполняло матчинг всего лишь 30 тысяч товаров в течение 6 часов. Для сравнения, на AliExpress представлено порядка 2 млрд товаров. 

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

Именно поэтому мы решили делать собственный матчинг.

Как выглядят товары и данные о них, с которыми нам приходится иметь дело? Для начала у нас есть карточка товара или так называемый Item. Item — это группа товаров, которые различаются характеристиками, типом доставки, ценой. Помимо этого есть SKU — конкретный товар, который получит пользователь, с учетом всех характеристик: цвета, объема памяти и так далее.

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

Одинаковые ли эти два товара? Ответ зависит от целей матчинга. Если нам надо склеить SKU в один Item, то эти товары мы могли бы считать одинаковыми. Но перед нами была задача сделать матчер в первую очередь для ценообразования, поэтому мы должны сопоставлять товары с одинаковыми характеристиками — и с этой точки зрения SKU разные. Следовательно, нам надо матчить товары с четко определенными характеристиками, поэтому наш матчер работает на уровне SKU.

Какие проблемы нам необходимо решить, чтобы сделать качественный матчинг? 

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

Вторая проблема — это количество товаров. Идеальный способ  — матчить каждый товар с каждым, но для нас он не подходит, поскольку в AliExpress более 2 млрд. SKU. А матчер должен работать быстро и качественно.

Что же сделали мы?

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

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

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

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

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

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

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

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

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

А теперь поговорим о том, как мы обучали наши модели.

Картиночная модель: ArcFace и TrashPred

При обучении «картиночной» модели мы решили использовать функцию потерь ArcFace, которая учит различать лица, снятые с разных ракурсов. Благодаря ей мы можем узнать, один и тот же человек перед нами или разные.

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

Различия в положении эмбеддингов в пространстве: слева модель обучена с использованием кросс-энтропии, и эмбеддинги классов накладываются друг на друга в многомерном пространстве. Справа модель обучена с использованием ArcFace. Эмбеддинги объектов из одного класса лежат более компактно, и между классами есть пространство,.

Вы спросите: это же модель для лиц, откуда у товаров лица?

Все так, но мы нашли решение. Чтобы использовать эту модель, нам нужно было сделать “лица” — кластеры из одинаковых товаров. Мы взяли данные о матчах, размеченные для нас «толокерами», и объединили товары по одинаковым картинкам.

Разберем на примере:

На рисунке видно, что товары 0, 3 и 4 объединены по картинке, а товары 2 и 6 — по данным из Яндекс.Толоки, как и товары 1 и 5. Получается, что группу товаров 0, 2, 6, 3, 4 можно считать одним “лицом” с точки зрения изображений.

Но не все так просто: данные могут оказаться очень “грязными”. Например, у нас есть одинаковые фотографии чехлов на сиденья, которые встречаются 320 раз, или фотография с текстом, которая объединяет 39 тысяч разных товаров. Или же клавиатура и ТВ-приставка, имеющие в описании одинаковую картинку с промокодом, попадут в один кластер и будут представлять одно “лицо”, что введет модель в заблуждение, и она не сможет хорошо обучиться.

Нам нужно было решить вопрос чистоты обучающей выборки — и тут на помощь пришел TrashPred.

TrashPred — это наш «побочный» продукт для обучения, который предсказывает ценность картинок для матчинга. С его помощью мы можем определить, какие картинки бесполезны, а какие мы возьмем для обучения модели. Например, картинка с габаритами стульев нужна покупателям, но для нас она не несет никакой информации — в обучающую выборку и матчинг не берем.

Остановимся подробнее на том, как обучается TrashPred:

1. Берем все известные матчи — в первую очередь, матчи из базы Яндекс.Толоки.

2. Находим почти одинаковые картинки по эмбеддингам предобученной модели, например ResNet34.

3. Строим и анализируем граф связности товаров.

4. Обучаем и прогоняем TrashPred.

5. Исключаем плохие картинки, обновляем выборку треша и снова возвращаемся к третьему пункту.

6. Повторяем, пока данные не очистятся.

7. Обучаем модель на полученных “лицах”.

В итоге у нас получилось примерно 300-400 тысяч групп (или “лиц”) товаров, на которых была обучена модель.

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

Текстовая часть матчера: BERT’ы

Наша текстовая часть основана на BERT’ах — языковых моделях-трансформерах. Это мощные модели, которые могут идентифицировать различия в названиях товаров всего в один символ, чего не сможет сделать, например, Word2Vec.

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

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

Почему же она так хорошо работает?

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

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

Мы обучали нашу модель с использованием функции потерь triplet loss. Что это значит?
Мы учим модель ставить положительный пример к ключевому объекту, лежащему в центре, ближе, чем отрицательный, таким образом, чтобы между ними был отступ не меньше, чем α. Обучив модель таким образом, мы получаем довольно высокое качество поиска ближайших соседей.

Часть для Document у нас уже предрассчитана, но у нас 1 миллиард токенов, и если эмбеддинги имеют размерность 768, то это занимает 3 TB:

1B (tokens) * 768 (dim) * 4 (bytes-per-value) ~3TB

Но если в процессе обучения мы будем использовать автокодировщик, снизим размерность эмбеддингов до 64 и будем хранить в формате половинной точности, то получим всего 120 гигабайт. И при этом потеряем не более 0.1% recall:

1B (tokens) * 64 (dim) * 2 (bytes-per-value) ~0.12TB

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

И она уже умеет “говорить нет” похожим, но все-таки разным товарам.

Павлов и его сестры

Теперь поговорим о том, как мы запускали это в своей инфраструктуре.

Что мы использовали:

• Cluster ODPS — кластер в инфраструктуре Alibaba, в котором можно запускать SQL-запросы и несложные user-defined функции на Python, но в нем нет видеокарт.

• Сервер Pavlov — наш туннель в ODPS; только с него мы можем выкачивать данные и закачивать обратно в ODPS.

• Сестра Павлова — наша “GPU-ферма”.

Как же они работают вместе?

В ODPS поступают задания на matching, там же хранятся все данные о товарах.

Все нужные для матчинга данные мы передаем через сервер Pavlov на нашу “ферму” — туда же мы закачиваем картинки.

На “сестре” мы запускаем все наши нейросетевые модели, они отрабатывают — ищут ближайших соседей — после чего рескорят их. В итоге мы получаем уже рескоренные пары, которые снова складываем в ODPS. Вся эта система управляется при помощи Apache AirFlow. 

За время отладки мы сталкивались и с проблемами трансфера ODPS → Pavlov → Sestra и обратно, и с правами доступа тоже было не все гладко. Оборудование нам тоже подкинуло немало проблем: месяц мы ездили в data-центр, общались с саппортом. И в какой-то момент мы заставили всю эту систему работать.

Суперматчинг

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

Как было?

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

Как стало?

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

Выглядит это следующим образом:

Мы ищем порог для заданной точности с использованием бутстрепа: например, заданная точность — 95%. В таком случае вся заштрихованная красным область на нижнем графике считается точными матчами.

Почему же стало лучше?

Пороги определяются для каждой выборки по ее подвыборке, а значит

• мы не зависим от флуктуаций в данных и проседания модели;

• получаем несмещенную оценку качества — не обманываем;

• проще поддерживать несколько разных видов моделей;

• теперь есть интерфейс взаимодействия с Толокой;

• получаем заодно hard negative samples и разметку вообще;

• все единицы из сэмплов засчитываются нам в статистике ;)

Тут мы решили сравнить наше решение с существующими на рынке. Собрали выборку в 5000 SKU — результаты представлены в таблице:

У нас recall пониже, но истинных матчей мы приносим больше. Кажется, что такого не может быть, но мы умеем привозить на один SKU несколько матчей из одного магазина, что умеют далеко не все. Еще одно преимущество в том, что мы можем настраивать точность в зависимости от потребностей: нужно 95% — будет 95%.

Таким образом, это решение является state-of-the-art.

Если вы строили свой матчер или просто хотите поговорить об этом — жду вас в комментариях!