Comments 8
Насколько понимаю, в вашей задаче можно обойтись и приближённым алгоритмом поиска ближайших соседей, что работает значительно быстрее. Рассматривали ли вы другие готовые решения — Faiss, Annoy, и им подобные? (В Faiss имеется реализация точного поиска, если без него обойтись никак нельзя.)
Легко ли найти специалистов со знанием именно Dlib, а не TensorFlow и PyTorch? Как вы выбирали модель и настраивали её параметры?
+1 к комментарию.
Даже если предположить, что авторы провели какие-то исследования на рынке, а не просто написали велосипед сразу (хотя верится в это с трудом) — в статье нету вообще никаких ссылок/отсылок.
- Где сравнения с существующими алгоритмами и решениями?
- Почему postgre (где сравнение с другими)?
- Как специфика задачи повлияла на выбор решения (типо если бы надо было больше писать или реже читать — взяли бы что-то другое?)
Почему 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
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 в целом.
Авторам — респект.
Как помнить всех в лицо, или эффективный поиск лиц в большой базе