1. Предпосылки

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

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

2. Проблемы

Проблемы системы векторного поиска Xianyu в основном заключаются в нескольких аспектах:

Большой объем данных Общее количество видеокадров продуктов Xianyu находится на уровне 100 миллионов;
Высокая однокадровая размерность Для обеспечения точности векторного вызова текущая однокадровая размерность вектора составляет 1024 измерения;
Чтобы обеспечить эффект точности отзыва, точность вектора отзыва должна быть выше 95%;
Высокая производительность Для удобства пользователей потребление одного кадра для одного вызова составляет около 100 мс, а количество запросов в секунду — более 1000.

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

разреженность. По мере увеличения размерности увеличивается разреженность пространственного распределения данных;
Явление пустого пространства. Для наборов данных, которые следуют нормальному распределению, менее 1% точек данных распределяются вблизи центра, когда размерность приблизительно увеличивается до 10;
размерный эффект. По мере увеличения числа измерений эффективность обслуживания индекса резко падает, а расстояния между точками данных в многомерном пространстве становятся почти равными.

3. План реализации

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

3.1 Векторизация видео

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

Векторизация видео предназначена для извлечения ключевых кадров в видео и выполнения извлечения признаков для каждого кадра видео, включая извлечение локальных и глобальных признаков. Извлечение локальных признаков включает в себя «обнаружение характерных точек», «описание характерных точек» и «уменьшение размеров описания признаков». Извлечение глобальных признаков также включает несколько шагов.Мы инкапсулируем эти шаги в виде пользовательских операторов и используем модель Tensorflow Lite для объединения пользовательских операторов, чтобы операторы можно было динамически обновлять для достижения цели обновления алгоритма в реальном времени.

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

3.2 Расчет векторного расстояния

3.2.1 Расстояние Хэмминга

严格来说，海明距离其实和向量没有太大关系，海明距离计算的是两个等长字符串对应位置字符不同的个数。换句话说，海明距离表示将一个字符串变换成另一个字符串所需要替换的字符个数。对于向量来说，海明距离可以看作是将一个向量变换成另一个向量所需要替换的坐标个数。

0100→1001 Расстояние Хэмминга равно 3 0110→1110 Расстояние Хэмминга равно 1

3.2.2 Косинус угла вектора

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

В двумерном пространстве координаты вектора A равны [x1, y1], а координаты вектора B равны [x2, y2]. Формула косинуса угла между векторами A и B:

Та же формула косинуса угла верна и для многомерных векторов Предположим, что координаты A и B равны [A1, A2,..., An], [B1, B2,..., Bn] соответственно, тогда между A и B Формула косинуса прилежащего угла θ:

Чем ближе косинус прилежащего угла θ к 1, тем ближе прилежащий угол к 0 градусам, то есть тем более похожи два вектора.Вот как определить сходство векторов, вычислив прилежащий угол векторов.

3.2.3 Евклидов вектор расстояния

Векторное евклидово расстояние — это расстояние между вершинами вектора, формула расстояния между двумя точками x1 и x2 в N-мерном пространстве:

Чем меньше евклидово расстояние, тем ближе вершины вектора, то есть тем более похожи векторы.

3.1.4 Векторный внутренний продукт

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

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

3.3 Векторный поиск

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

3.3.1 Методы на основе дерева

KD tree — это классический алгоритм под ним. Вообще говоря, когда пространственная размерность относительно мала, производительность поиска дерева KD относительно эффективна, но когда векторная размерность относительно высока, метод вырождается в насильственное перечисление, и производительность относительно низкая. следующий метод ha или метод векторного квантования.

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

3.3.2 хэш-метод

LSH (Locality-Sensitive Hashing) — типичный алгоритм метода хеширования. Он использует метод хеширования для хеширования данных из исходного пространства в новое пространство, так что аналогичные данные в исходном пространстве имеют высокую вероятность быть похожими в новом пространстве, в то время как разные данные в исходном пространстве имеют высокую вероятность. вероятность. , вероятность сходства в новом пространстве мала.

Для небольших и средних наборов данных (несколько миллионов миллионов миллионов) эффект и производительность методов на основе LSH очень хороши. В этом отношении в этом отношении есть 2 инструмента с открытым исходным кодом Falconn и NMSLib.

3.3.3 Способ вектора квантования

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

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

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

3.3.3.1 Алгоритм иерархической кластеризации (HC)

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

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

3.3.3.2 Алгоритм производительности (PQ)

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

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

Алгоритм PQ можно понимать как разделяй и властвуй для векторного квантования.Во-первых, исходное векторное пространство разлагается на декартово произведение m маломерных векторных пространств, а разложенные векторные пространства малой размерности квантуются соответственно.Что насчет низких -мерные векторные пространства для квантования? Так уж получилось, что используется алгоритм kmeans. Другими словами, исходный D-мерный вектор (например, D=128) делится на m групп (например, m=4), и каждая группа

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

Можно видеть, что m = 1 или m = D являются двумя крайними случаями алгоритма PQ. При m = 1 алгоритм PQ возвращается к векторному квантованию. При m = D алгоритм PQ эквивалентен каждому измерению исходный вектор Вычислите кодовую книгу с kmeans.

Фиг.2 представляет собой схематический вид данных об исходных данных 128 алгоритма PQ. В этой конфигурации по умолчанию.

Согласно вышеуказанному введению, мы в основном тестируйте метод вектора квантования и тестируйте алгоритмы HC и PQ, поддерживаемые двигателем. Тестовый вектор Размер: 760W, размерность: 65, метод расчета расстояния: внутренний продукт, векторный тип: Результаты теста следующие:

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

3.4 Архитектура проекта

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

3.4.1 Архитектура приложения

Архитектура приложения разделена на несколько частей:

Клиент
Клиент idle fish разработал алгоритмический контейнер на основе Tensorflow Lite и реализует видео для извлечения ключевого кадра на конце, вычисления одиночного кадра видео; в соответствии с рассчитанными на конце функциями извлекает векторную библиотеку видео на Облако, Получить похожие векторы и, наконец, вычислить похожее видео.
Кластер микросервисов
Серверная часть инкапсулирует универсальный векторный унифицированный уровень доступа, защищает от воздействия стыковки нижнего уровня с различными механизмами поиска векторов на верхний уровень и резервирует точки расширения, чтобы заложить основу для последующего доступа к векторам изображений и векторам товаров. После получения видео-вектора серверная часть вызывает базовый механизм поиска векторов, чтобы вспомнить похожие результаты, фильтрует и пересчитывает показатель сходства видео в соответствии со статусом продукта; серверная часть сохраняет данные видео-вектора в журнале, а система синхронизации мониторинга журнала синхронизирует векторные данные с автономным центром обработки данных.
Система синхронизации мониторинга логов

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

Автономный центр обработки данных генерирует раздел инкрементных видео-векторных данных в реальном времени каждые 15 минут. Каждый день объединены полные данные вчера и инкрементные данные текущего дня, а затем возвращаются объединенные полные данные текущего дня. к вектору поискового двигателя, чтобы построить полные данные дня. Индекс.
Механизм векторного поиска
Механизм векторного поиска, который мы используем на этот раз, — это BE, который был разработан Alibaba самостоятельно. BE — это механизм, отвечающий за онлайн-отзыв рекомендательной системы Alibaba. системы от автономного до онлайн-поиска, и полагаться на мощную систему управления и контроля для достижения полного управления жизненным циклом от разработки, запуска до эксплуатации и обслуживания.

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

Механизм BE глубоко интегрирует библиотеку KNN с открытым исходным кодом — FAISS, преобразует и настраивает ее для поддержки распределенного построения и запроса векторных индексов, а также реализует различные методы на основе квантования, такие как грубое квантование, квантование произведения и комбинация грубых квантование + квантование продукта и т. д., и задержка онлайн-запросов и производительность построения индекса превосходны.

3.5 Онлайн-эффект

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

4. Резюме

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

Техническая команда Xianyu — это небольшая и мощная инженерно-техническая команда. Мы не только фокусируемся на эффективном решении бизнес-задач, но в то же время продвигаем передовую практику разрушения разделения труда в стеке технологий (унификация моделей и языков программирования android/iOS/Html5/Server) и технология компьютерного зрения на мобильных терминалах. В качестве инженера-программиста в технической команде Xianyu у вас есть возможность продемонстрировать все свои таланты и мужество, доказав, что развитие технологий является движущей силой изменения образа жизни во всей эволюции продукта и решении проблем пользователей.

Доставка резюме: guicai.gxy@alibaba-inc.com

5. Ссылки

Алгоритм ПК
faiss
Large-scale video retrieval using image queries
https://lear.inrialpes.fr/pubs/2011/JDS11/jegousearchingwith_quantization.pdf
https://en.wikipedia.org/wiki/Hamming_distance
https://zh.wikipedia.org/wiki/K-d%E6%A0%91
https://github.com/facebookresearch/faiss
https://github.com/andrefaraujo/videosearch