Pull to refresh

Comments 8

Насколько понимаю, в вашей задаче можно обойтись и приближённым алгоритмом поиска ближайших соседей, что работает значительно быстрее. Рассматривали ли вы другие готовые решения — Faiss, Annoy, и им подобные? (В Faiss имеется реализация точного поиска, если без него обойтись никак нельзя.)


Легко ли найти специалистов со знанием именно Dlib, а не TensorFlow и PyTorch? Как вы выбирали модель и настраивали её параметры?

+1 к комментарию.


Даже если предположить, что авторы провели какие-то исследования на рынке, а не просто написали велосипед сразу (хотя верится в это с трудом) — в статье нету вообще никаких ссылок/отсылок.


  1. Где сравнения с существующими алгоритмами и решениями?
  2. Почему postgre (где сравнение с другими)?
  3. Как специфика задачи повлияла на выбор решения (типо если бы надо было больше писать или реже читать — взяли бы что-то другое?)
Почему postgre (где сравнение с другими)?
В статье действительно не хватает ссылок. О чём идёт речь поймёт только тот кто и так уже знает. Имеется ввиду cube. Он использует GiST индекс для нахождения ближайшей точки в n-мерном пространстве:
SELECT c FROM test ORDER BY c <-> cube(array[0.5,0.5,0.5]) LIMIT 1
Автор статьи же использует свою формулу расчёта ближайшей точки, потому его запрос скорее всего не использует индекс:
ORDER BY sqrt(power(CUBE(array[{}]) <-> vec_low, 2) + power(CUBE(array[{}]) <-> vec_high, 2)) ASC

Хотя запрос всё равно отрабатывает быстро, возможно оптимизатор постгреса перестраивает запрос для использования индексов.

На мой взгляд cube — пожалуй единственное опенсурсное коробочное решение, которой просто поставил, запустил и всё заработало. Наверно поэтому автор и пишет, что это "+- сказка".

В PostgreSQL есть такой индекс spgist, который в том числе реализует и k-d-деревья (https://habr.com/ru/company/postgrespro/blog/337502/). А в 12-й версии появился поиск ближайших соседей по этому индексу.
Можно класс операторов под свою задачу заточить, а не писать базу данных целиком.

Вот и у меня первая мысль была, почему не использовать k-d spgist

Автор явно любит свои велосипеды. Не использют, все больше проникающую в стандарт pathlib, обучали собственный каскад сетей вместо попробовать ArcFace. Недавно в ods.ai обсуждалось как ускорить поиск по эмбедингу лица и там было штук 5 решений со ссылками в том числе и на хабр.

O(N*k) — оценка сложности по операциям сложения/умножения, но нужно учесть что OpenBLAS делает операцию вычисления евклидова расстояния векторно, что приводит нас к мысли, что данная оценка сложности не коррелирует с реальным временем. Таким образом, писать про O(N*k) некорректно в рамках поставленноой задачи. А еще можно хранить в БД квадрат длины вектора-эмбединга и за O(1) находить cos угла между БД эмбедингом и входным, а затем теорема косинусов и получаем оценку O(N).

«лабораторку провинциального вуза» — грубо по отношению к 85% жителей не столиц.

А в завершении еще и оказывается (я не знал) k-d в postgres есть. Зато автор дает совет учить алгоритмы пасанам, вместо rtfm, в том числе и для себя.

В результате, пользу от статьи лично я получил (узнал про k-d в postgres), но осадок от подачи остался.

Решал похожую задачу. ИМХО можно было бы немножко улучшить систему если:
1) Строить базу используя более длинный эмбендинг (в моем случае 256 бит) и использовать расстояние Хэмминга для расчета похожести лиц.
2) Для поиска похожих эмбендингов можно использовать алгоритм Vantage Point Tree. Данный алгоритм имеет ряд преимуществ перед простым k-d tree по эффективности поиска на больших объемах данных


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

Отличный ответ на вопрос, зачем нужны алгоритмы и структуры данных (в комментариях нередко проскакивают эти темы).
Для решения крутых задач типа такой, и в ML / data science в целом.

Авторам — респект.
Sign up to leave a comment.

Articles