Резюме: Далее я попытаюсь разобраться в различных концепциях Faiss и взаимосвязях между ними посредством разработки различных структур классов в исходном коде Faiss.
Эта статья опубликована в сообществе Huawei Cloud Community "Анализ исходного кода Faiss (1): анализ структуры классов", оригинальный автор: HW007.
Faiss — это платформа, разработанная Facebook AI Research для обеспечения эффективного поиска сходства и кластеризации для плотных векторов. Благодаря официальному руководству для новичков мы можем быстро ознакомиться с основными функциями Faiss. Однако я полагаю, что после прочтения официального руководства для новичков большинство людей все еще имеют смутное представление о многих понятиях Файса и не могут четко определить границы между этими понятиями. Например, в Faiss, какова концепция квантайзера, какова связь между ним и индексом, какова связь между различными индексами и так далее. С этой целью в дальнейшем я попытаюсь разобраться в различных концепциях Faiss и взаимосвязях между ними посредством разработки различных структур классов в исходном коде Faiss.
Во-первых, диаграмма классов исходного кода Faiss представлена следующим образом, файл подробной диаграммы классов EA показан во вложении:
Рисунок 1: Семейный портрет на диаграмме классов Файсса
Во-первых, давайте взглянем на основную функцию Faiss: поиск сходства. Как показано на рисунке ниже, на примере поиска изображений так называемый поиск по сходству заключается в том, чтобы найти указанную мной цель (нижний левый угол рисунка ниже) в данной группе изображений (атлас в левом верхнем углу). углу рисунка ниже) изображение автобуса) наиболее похожие K изображений, также называемые проблемой KNN (K-ближайших соседей).
Далее давайте посмотрим, что хотя бы нам нужно сделать в инженерии, чтобы решить проблему KNN. Очевидно, необходимо сделать две вещи: во-первых, нам нужно сохранить галерею из приведенного выше примера, во-вторых, когда пользователь указывает изображение, нам нужно знать, как найти самые последние сходства из сохраненной галереи. К изображений. Исходя из этого, мы определили как минимум две функции, которые Faiss должен иметь в своих сценариях приложений: функция добавления и функция поиска.
Студенты, знакомые с базой данных, должны чувствовать здесь запах «CRUD». Действительно, когда мы добавляем и сохраняем действия в «атлас», также следуют такие функции, как модификация и удаление. Таким образом, Faiss по сути является векторной базой данных. Для баз данных оптимизация пространства-времени — это две вечные темы, то есть как хранить больше информации с меньшим объемом памяти и как искать более точную информацию с большей скоростью поиска. Как сократить время поиска? Наиболее распространенной операцией в базе данных является добавление различных индексов и инкапсуляция функций различных алгоритмов ускоренного поиска или стратегий изменения пространства и времени в различные индексы для соответствия различным эталонным сценариям.
Отсюда нетрудно понять, почему в Faiss так много Индексов, ведь само понятие Индекса завязано на ускоренный поиск. Также видно, что в Faiss первоочередной задачей является быстрое и точное нахождение похожих векторов. На рисунке ниже показаны два наиболее важных базовых класса в Faiss: Index и IndexBinary.
На рисунке выше три самые важные функции в этих двух базовых классах отмечены белыми стрелками, среди которых функции add() и search() соответствуют как минимум двум функциям, которые Faiss должен реализовать, как указано выше. : хранение и поиск. Кстати, по сравнению с традиционными базами данных Faiss's Index также включает в себя функции хранения данных.Если вы буквально с самого начала понимаете концепцию индексов в традиционных базах данных, это может показаться немного странным. Далее поговорим о функции train() в Index.Все мы знаем, что пирог не будет напрасным.Фаиссу,будь то для уменьшения места для хранения или ускорения поиска,необходимо заранее сделать некоторые приготовления для работы , здесь в игру вступает функция train().
Взяв в качестве примера сокращение памяти, мы все знаем, что при обработке изображений PCA может преобразовывать изображения из многомерного пространства (p-мерного) в низкоразмерное пространство (q-мерное, где p > q), и конкретная операция для преобразования многомерного пространства (p > q).Вектор изображения (n*p) в пространстве умножается на матрицу преобразования (p*q), в результате чего получается вектор (n*q) в низкоразмерном пространстве . Чтобы свести к минимуму потерю информации в течение всего процесса уменьшения размерности, нам необходимо проанализировать и рассчитать изображение, которое необходимо преобразовать, чтобы получить соответствующую матрицу преобразования (p*q). То есть матрица преобразования, умноженная на это уменьшение размера, тесно связана с изображением, которое нужно преобразовать.
Возвращаясь к нашему Faiss, предположим, что я рассчитываю использовать предварительную обработку PCA для уменьшения места для хранения в индексе.Во всем процессе, помимо ввода галереи поиска, я должен ввести дополнительную матрицу преобразования, но эта матрица преобразования то же, что и Библиотека тесно связана и может быть рассчитана на основе данных библиотеки. Если рассматривать эту матрицу преобразования как параметр, то можно обнаружить, что в какой-то предварительной обработке Файса мы введем некоторые параметры, причем эти параметры нельзя указать вручную в начале, а можно обучить только путем подачи сэмплов, поэтому необходимо быть такой функцией train() в Index, чтобы предоставить интерфейс для ввода обучающих выборок для обучения таких параметров. Отсюда мы также можем обнаружить, что образцы данных, переданные в функцию train(), лучше всего согласуются с атласом, который будет добавлен и сохранен позже, а также с целью поиска. матрицу преобразования в PCA, добавить набор данных лица в этот индекс и, наконец, выполнить распознавание лица по этому индексу, что определенно не так хорошо, как подача набора данных лица для получения матрицы преобразования PCA в начале.
Из вышеизложенного мы уже можем примерно понять, что такое индекс в Faiss, из трех функций train (), add () и search () Далее, давайте посмотрим на различные индексы в Faiss. Как видно из диаграммы классов на рис. 1, в Faiss большинство классов в основном наследуют или используют интерфейс Index, и они либо реализуют собственные персонализированные реализации функций обучения, добавления и поиска, определенных в интерфейсе Index (класс отмечены светло-оранжевым цветом на рис. 1), или он должен упаковать классы трех основных функций, которые были реализованы, и обеспечить некоторую обработку в процессе, кроме трех функций (отмечены светло-голубым на рис. 1). вид) .
На рисунке 1 видно, что эти частично упакованные подклассы индекса, отмеченные голубым цветом, имеют отношения «является» и «держат» между собой и базовым классом индекса. Это видно в структуре класса. , дизайнер либо разрабатывает узел дерева или связанного списка, либо разрабатывает класс-оболочку. Очевидно, что в Фаиссе предпочтение отдается последнему. С одной стороны, светло-голубой подкласс индекса предоставляет базовые функции обучения, добавления и поиска с помощью индекса, который он «держит», так что он соответствует стандарту определения интерфейса индекса и становится своего рода индексом, который встроенный слой за слоем для последующих слоев.Пакеты обеспечивают поддержку. С другой стороны, он расширил некоторые общие функции до класса Index, который он «держит». Как показано в классе IndexPreTransform на следующем рисунке, Faiss абстрагирует предварительную обработку сохраненного атласа, такую как нормализация, уменьшение размерности PCA и другие функции, в интерфейс VectorTransform, который используется IndexPreTransform для добавления предварительной обработки к индексу, который он «держит». функция, эта функция предварительной обработки не имеет ничего общего с тем, какой индекс она «держит», поэтому я предпочитаю приписывать эту функцию функции упаковки в процессе, отличном от индекса. Например, класс IndexPreTransform предоставляет функцию предварительной обработки данных, класс IndexIDMap предоставляет функцию пользовательского идентификатора, а класс IndexShards обеспечивает соответствующую поддержку параллельного вычисления индекса.
Далее давайте взглянем на подклассы Index, отмеченные светло-оранжевым цветом на рисунке 1, такие как IndexLSH, IndexPQ, IndexIVFPQ и т. д. Из названий можно примерно понять, что эти классы основаны на каких-то разных алгоритмах. и способы поиска разные. Но в целом можно найти и некоторые другие структурные общности. Из вышеизложенного мы знаем, что индекс имеет функцию хранения.Эти подклассы индекса, отмеченные светло-оранжевым цветом, можно в основном разделить на две категории с точки зрения методов хранения данных.Во-первых, хранить их в одном контейнере, таком как IndexLSH, IndexPQ и т. д. Мы все можем видеть векторный контейнер с именем code. Другой тип сегментирован и хранится в нескольких контейнерах, что в основном обеспечивает поддержку последующего неточного сегментированного частичного поиска индекса.По этой причине Faiss специально абстрагирует интерфейс InvertedLists.Все подклассы индекса, которые должны поддерживать сегментированный частичный поиск, будут там. является экземпляром удержания, который реализует интерфейс InvertedLists (отмечен сиреневым цветом) для хранения своих данных. Как показано на рисунке ниже, Faiss предоставляет три различных реализации интерфейса InvertedLists, включая массивы, связанные списки и дисковые файлы.
На рисунке 1 также есть два класса, отмеченные светло-зеленым, ProductQuantizer и ScalarQuantizer, которые заслуживают вашего внимания.Конструктивно эти два класса не имеют производных подклассов, а все остальные классы относятся к ним как «удерживающие» отношения, очень чисто инструментальный класс. Судя по суффиксу Quantizer в названии, роль этих двух классов инструментов состоит в том, чтобы «дискретизировать или разрежать», «непрерывно или плотно» данные, то есть просто выполнять операции кластеризации, как мы. процесс кластеризации, точно так же, как людей младше 18 лет называют подростками, а людей в возрасте от 18 до 50 лет — людьми среднего возраста. Из рисунка 1 также видно, что есть еще четыре класса с суффиксом Quantizer: MultiIndexQuantizer, MultiIndexQuantizer2, IndexScalarQuantizer и Level1Quantizer. Первые три из них реализуют функцию Quantizer, упаковывая ProductQuantizer или ScalarQuantizer, В этом нет ничего необычного, но последний класс Level1Quantizer фактически обертывает два класса Index, а имя атрибута одного из классов Index по-прежнему Quantizer, как показано ниже. на рисунке.
Является ли Index также квантователем? Действительно, для Index мы больше знакомы с его функцией хранения наборов данных и поиска K ближайших соседей определенных данных в наборе данных. Но если то, что хранится в индексе, является центральной точкой каждого класса после классификации данных, то для определенных данных мы можем использовать KNN в индексе, чтобы найти его K (в настоящее время K = 1) ближайших соседей, эти класс представленный полученной центральной точкой, является классом, к которому принадлежат данные в кластеризации. Из этого мы видим, что Index можно использовать для кластеризации и количественного определения данных в центральной точке класса. Поэтому неудивительно, что Index можно обернуть как квантайзер. На самом деле, функция кластеризации индекса очень распространена в дизайне Faiss.В дополнение к вышеупомянутому квантователю ее также можно использовать для помощи в реализации алгоритма K-средних.Есть причина для существования свойства типа индекса с именем clustering_index. Благодаря приведенному выше анализу мы также можем узнать, что в классе Quantizer Файсса должно быть место для хранения «центроидов», используемых для помощи в квантовании, то есть центральных точек класса, которые есть в большинстве сценариев.После обучения данных (например, K -означает кластеризацию данных), его также можно напрямую установить вручную в нескольких сценариях.
Наконец, давайте сосредоточимся на классе IndexIVF (сиреневый класс, обведенный на изображении выше). Возможно, когда выше я представил кластер класса InvertedLists бледно-лилового цвета, у некоторых людей возникли бы сомнения.Класс InvertedLists и его производные подклассы в основном предоставляют неточную функцию локального поиска ведра для индекса в Faiss, которая не имеет ничего общего с типом индекса. критерии классификации для подклассов, полученных из приведенного выше индекса, класс IndexIVF должен быть частично упакованным подклассом индекса и должен быть отмечен голубым цветом. Действительно, как показано на рисунке выше, хотя класс IndexIVF не «удерживает» класс Index напрямую, он косвенно «удерживает» класс Index, наследуя класс Level1Quantizer, который на самом деле является производным от класса частичной оболочкой подкласса Index. Цветовая маркировка на рисунке 1 предназначена только для выделения класса Index с функцией IVF, а цвет используется для облегчения визуального различения каждого кластера функционального класса, поэтому нет необходимости углубляться в него.
Из вышеизложенного мы можем обнаружить, что весь дизайн структуры классов Faiss очень четкий и лаконичный.Во-первых, он делит процесс решения проблем KNN на три этапа: обучение, добавление и поиск, а также абстрагирование базового класса Index. Затем из этих базовых классов выведите различные частичные реализации функций или частичные подклассы индекса упаковки процессов. Кроме того, для индекса предусмотрено два метода хранения: централизованное и сегментированное (IVF). Наконец, предоставляются два инструмента кодирования квантования, SQ и PQ, а также классы, которые объединяют эти инструменты кодирования или другие индексы в квантователи.
Нажмите «Подписаться», чтобы впервые узнать о новых технологиях HUAWEI CLOUD~