Запрети мне псевдолейблить

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

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

Сигма-тест — это когда ты сразу выкатываешь и сразу наблюдаешь за падающими графиками.

Тати оказывается тоже завела канал. Это человек, с которым я нафармил свою первую медальку в 2019 году за компетишны и стафф инженер Linkedin. Когда мы решали Lyft Тати созванивалась с нами из декрета и решала кагл, пока ребенок спит.

#intro

Welcome to Wonderland Тати.

Буду писать о науке, машинном обучении, искусстве, книгах, психологии, философии, карьере, фейлах, лайфхаках, Ирландии и мире.

И конечно же, кулстори из жизни, которые все так любят.

Забыл вам сказать подписчики. Видимо это сейчас важно. Все это время мне было 17 лет

Админу LDT 16, он у нас в школе на воротах на футбике стоит и шитпостит
Валера Бабушкин наш физрук

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

Наше комьюнити хостит сореву ☝️. Я пока топ 1 на лб с первого же сабмита.
Главный приз- соавторство в публикации в A* журнале по комбинаторике

Go get me

Неожиданное. Запустил сореву на каггле. https://www.kaggle.com/competitions/lrx-oeis-a-186783-brainstorm-math-conjecture/overview

Хорошее решение ML/RL-ем имеет важное прикладное значение и можно стать соавтором статьи. Алгоритмические не так интересны, потому что плохо обобщаются.

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

Второй на лб кагглер пишет ГГ прямо на доске если выигрывает или проигрывает 3-0 (потому что раундов 5 и он уже победил/проиграл)

Влетел на 390 место и 16,616 рейтинга. ВКУСНО 🎲

Про то, почему не работал бимсерч и чем санта 24 отличается от санты 23

В прошлом (2023) «Санте» требовалось собрать многомерный кубик Рубика в упорядоченное положение кратчайшим путём. Это классическая задача поиска кратчайшего пути: при наличии подходящего алгоритма и отсутствии отрицательных циклов её можно решить в полиномиальное время. Даже если точное решение найти затруднительно, задачу можно разбить на подзадачи и последовательно ограничивать поиск, отсекая пути, которые уже заведомо не могут быть короче найденного решения, а потом искать оптимизации между промежуточными пунктами с помощью бимсерча.

В «Санте» 2024 года мы имеем более сложную задачу: нужно переставить заданные слова в таком порядке, чтобы минимизировать перплексию для модели Gemma-2-9b. Иначе говоря, это задача коммивояжёра (TSP) (а еще лучше задача о Питербуржских мостах): надо обойти «города» (здесь — слова) и вернуться к начальному условию или достичь некоторого состояния, при этом пропускать слова нельзя. TSP относится к классу NP-трудных задач, и при более чем 66 «городах» (в нашем случае слов около 100) её невозможно точно решить перебором за разумное время: потребуются миллиарды лет вычислений даже на гипотетическом сверхмощном компьютере.

Почему beam search (и аналогичные алгоритмы поиска кратчайшего пути) в данном случае не помогают? Основная причина в том, что в задаче коммивояжёра, по сути, могут существовать «отрицательные циклы» с точки зрения нашей целевой функции (перплексии). В классическом поиске кратчайшего пути алгоритмы гарантированно работают только при условии, что нет отрицательных циклов, т.е. нет подпути, который имеет отрицательную длину. D 2024 же нам специально нужно найти такую последовательность (цикл посещения всех «городов»), при которой итоговая «стоимость» (перплексия) окажется минимальной. Метод beam search, который хорош в задачах без отрицательных циклов, не способен эффективно отсеивать невыгодные ветви в условиях просто потому, что не обладает достаточной информацией, где каждое добавление нового «города» может кардинально изменить оценку перплексии.

Поскольку слова пропускать нельзя, обойти «сложные» участки не получится. Задача действительно носит характер TSP, а он, не допускает эффективных точных решений при большом количестве вершин. Поэтому для «Санты» 2024 года оправдано применение эвристических или стохастических методов (например, отжига или других метаэвристик), которые не гарантируют точное решение, но на практике позволяют получить приемлемый результат за разумное время.

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

🎅 Santa 2024 Top-1 🎅

Описание задачи
Участникам предлагалось решить достаточно простую задачу:
Переставить фиксированный набор слов так, чтобы итоговая последовательность минимизировала перплексию модели Gemma-2-9b.
При этом можно было использовать только перестановки заданных слов.

Общая картина
Практически все участники использовали те или иные алгоритмы отжига (simulated annealing) или их модификации, поэтому публичные решения были довольно похожи. Даже чел с 2 места просто использовал SA. В соревновании отсутствовал приватный LB — использовался только публичный, а значит и шейкапа не было.

Победители обнаружили глобальный оптимум ещё два месяца назад и спокойно чилили до последней ночи соревнования. Почему глобальный оптимум? Потому что все команды из золота финишировали с одним и тем же скором. Слишком большое совпадение. Как принято, были и китайские анонимные гении, которые две недели назад зарегали аккаунт и влетели в золото в последний день с 10 сабмитов. Но вернемся к победителям:

Примочки
Дистилировали Gemma-2-9b
Так как домен ограничен сотней слов, они смогли сжать модель до 1/5000 от оригинала. Я тоже пытался дистиллировать, но не смог добиться стабильного результата. Теперь выпрашиваю на форуме дать посдказок и правильных ответов, а то месяц мучал этот подход. Мб все же надо решать nlp соревы иногда.

Основной алгоритм победы — Iterated Local Search (ILS):
Принцип опишем так:

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

2. Пертурбация:
Из текущего решения выбираем блок из нескольких подряд идущих слов, которые затем случайным образом переставляем. Это позволяет "оттолкнуться" от текущего состояния и исследовать новые варианты.

3. Локальный поиск:
После пертурбации в стиле брутфорса пытаемся переставить каждое слово. Полученный результат фиксируем, а его оценка с не большим марджином (10%), запоминаем, чтобы отсекать неперспективные варианты.

4. Поиск в глубину:
Затем перебираем все перестановки с глубиной N+1 (переставляем два слова, потом три слова всеми возможными вариантами). Если ни одно из новых решений не оказывается лучше установленного порога, текущий локальный оптимум считается финальным, и алгоритм возвращается к пертрубации.

Все, готово. Ставим сосиски на гпу и ждем, когда они превратятся в пепел.

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

АХ НУ ДА, БИМ СЕРЧ НЕ РАБОТАЛ, ФИГНЯ БИМ СЕРЧ ВАШ. Он для совсем других целей. Ставьте 🧠️️️️️️ если хотите, чтобы я объяснил

Заняли 23 место в Santa 2024 и нафармили серебро 🥈. К сожалению в этот без прогресса к КГМ.
После понижения рейтинга (случается после конца каждого соревнования) у меня осталось 13,971. По моим расчетам должен допрыгнуть до 15к и с 470 места влететь в <400, чем, вероятно, обновлю свой лучший результат в рейтинге снова.

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

Всем приветики. Давно не было постов, тк становится всё сложнее вести канал. Не буду обещать что исправлюсь, но буду постить когда есть что-то о чём другие каналы не говорят достаточно.

И сегодня будут не новости (о ChatGPT Operator можете прочитать где угодно), а открытая позиция на PhD студента в моей старой лабе в UMass Lowell - Text Machine Lab.

Это NLPшная позиция с довольно широким спектром того чем можно заниматься: от interpretability и prompting до alignment, мультимодальных моделей, low-rank training, PEFT итд. Глава лабы - Prof. Anna Rumshisky исследователь в UMass Lowell, MIT и в Amazon Alexa AI/Amazon AGI. Например, она один из авторов Amazon Nova

Требования: релевантный бакалавриат+магристратура/специалитет, хорошее понимание линейной алгебры, анализа, вероятности, базовые знания Deep Learning и NLP. Большим плюсом будут опубликованные статьи (включая воркшопы), но строгого требования на них нет.

Позиция fully funded - ваше обучение бьудет покрыто полностью и вам будут платить стипендию которой достаточно для проживания в Массачусеттсе.

Для подачи высылайте ваше CV и короткое cover letter на [email protected]. Для попадания в поток 2025 надо сделать это до 15 февраля

Если хотите прочитать про мою историю поступления и первые дни в США, я в 2019 писал об этом серию постов и вот первый: telegra.ph/CHast-1-Postuplenie-08-24

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

Linkedin превратился в апостола мертвого интернета. Пора ли уже и из него удаляться? Какими сервисами вы пользуетесь?

🚀 Разбираем решение, которое принесло нашей команде 6-е место в Kaggle-соревновании по обработке данных миссии Ariel

Пост про то, что это вообще за сорева вот тут.

Мы работали с частотными сигналами, которые изначально были очень шумными. Для их сглаживания использовали:
1️⃣ Гауссовский регрессор
2️⃣ Фильтр Савицкого-Голея

Далее ищем границы транзитной зоны планеты. Делаем через простой эмпирический детектор: транзит на графике светимости звезды имеет вид \_/ — яркость падает, когда планета проходит перед звездой, так как часть частотных компонентов теряет интенсивность.

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

🔍 Фичи и модели:

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

Параллельно обучаем CNN, которая анализировала частотные изменения в заданных временных окнах.
Это:
Помогает учитывало локальные особенности спектра и переходов (энергии?) между частотами
Позволяло понять взаимосвязи между соседними частотами, улучшая точность предсказаний.
🔗 Финал:

Смешали (блендили) результаты линейной регрессии и CNN. Затем финальную спектрограмму еще раз сгладили, чтобы убрать артефакты.

💡 Бонус материал: пример 'подъема' спектра на картинке

У меня ощущение, что никто никогда кодфорсес не решал.

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

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

https://codeforces.com/blog/entry/20762?locale=ru

НЕЕЕЕТ ТЫ НЕ ПОНИМАЕШЬ ТЫ ДОЛЖЕН ЗНАТЬ ЧЕМ ОТЛИЧАЕТСЯ RSLORA ОТ QLORA, ты должен знать чем отличается sageattn от fa2 от fa3, ВсМыСлЕ тЫ Не зНаЕшь чЕм отличается adan от LiOn у НаС тИмЛиД еГо ПиСаЛ!!!!

Про что был NeurIPS Competition track в этом году?

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

На вход даются симулированные данные детектора, направленного на звезду, на выходе надо предсказать состав атмосферы планеты, проходящей транзит.

Данные на вход давались в двух вариантах:
1. Честные цифры с детектора, который сам по себе двухмерный + время
2. Данные обработанные в частотный формат. При этом частоты еще и очень удобно метчились с таргетами.

Метрика качества- Gaussian Log-likelihood. Т.е. честное, взаправдашное правдоподобие с учетом оценки дисперсии.

https://x.com/ZeyuanAllenZhu/status/1867867881146638720

На нипсе расистский скандал. Ждем подробности в твиттуре

В этом соревновании в десятке были еще наши слоны:

Выступил на NIPS, на воркшопе посвященному соревнованию Ariel Data Challenge. Выступал на английском, опыт интересный, даже не факапнулся в рече. С темой своего выступления как обычно кринжанул, думал там ребята посвященные слушают, а там просто проходящие энтузиасты астрофизики зашли, а я как на зло погружение решил скипнуть со словами "I hope all of you are in the context of the data and the task". Вместо описания решения, как остальные участники, решил сделать спич с заголовком "почему моё решение хоть и решает метрику, но не решает задачу". Ещё и в 2 ночи по Шанхаю спикать пришлось, в полубредовом состоянии.

В общем да, эмоции переполняют, надо больше тренироваться на конфах выступать. В следующий раз надеюсь не на воркшоп, а на статью навайбю 🤓

Воркшоп по сореве NeuralIPS начался, можно смотреть на мои 10 минут русского акцента:
https://neurips.cc/virtual/2024/competition/84802

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

Обновил превьюшку в тг. Вы вот знали, что тг один раз генерит превью для ссылки и потом не обновляет, пока не попросишь специального бота это сделать? В смысле старое превью моей ссылки на кэггл не обновлялось больше года :0
@WebpageBot

Прошел калибровку на 409 ранг

Сутра:
1. Kaggle решат
2. Соревы обозреват
3. Gold фармить
4. Социальност

Канал о пути к Kaggle competitions Master Grandmaster, баварских сосисках и пиве, которым обливаешься в процессе

https://www.kaggle.com/asimandia

Для вопросов: @dimitriy_rudenko

ВЫСТУПАЕМ НА ПРИВАТНОМ НИПСЕ

ВЫСТУПАЕМ НА НИПСЕ В ЭТОМ ГОДУ

ЖДЕМ ЗАВТРА


(а честнее 00:00 по гринвичу сегодня)

GreySnow is following you

Во-вторых, теперь можно наконец-то нормально устанавливать пакеты через специальный интерфейс Package manager.

Представьте, теперь не надо создавать датасеты с source кодом и устанавливать все в ноутбук через магические команды jupyter. Самое полезное- это то, что теперь можно устанавливать пакеты в Code Competitions, когда код должен быть отправлен в ноутбуке, у которого нет доступа к интернету. Теперь код из Package Manager выполнится и установит нужные пакеты заранее и с интернетом. Кстати поддерживается только pip, никакого вам poetry и uv

Я очень давно ждал эту штуку, и теперь буду со всей силы ждать возможность качать данные не из tar.gz архива, а через что-нибудь с поддержкой разбивки частей архива и rsync или даже может быть с торрентов, потому что качать террабайт данных со скорость 5мб/сек одним большим куском- очень больно и слишком 2011. Тем более с текущей надежностью серверов с данными на каггле.

https://www.kaggle.com/discussions/product-feedback/532336tart

На Kaggle случилось два апдейта.

Во первых, следуя за гитом и прочими платформами выкатили награды и бейджи:

Награды это какие-то ДОСТИЖЕНИЯ.
Например за то, что я был хостом соревнования Инстамарта (Сбермаркета (Купера)) на стажировку, я получил от Kaggle награду. Еще вот Сергею Фиронову дали ачивку за топ 100.

Бейджи дают за более доступные штуки:
Возраст акаунта
Стрики логинов
Форк ноутбуков
etc

Жду сториз и удаление стены!

Полный список бейджей

Да в смысле вам не нравится. Объяснитесь!

Глупый телеграм пережимает, вот вам оригинал:
https://www.linkedin.com/posts/astratoanalytics_datadna-dataviz-datadna-activity-7003783958660292608-da5X?utm_source=share&utm_medium=member_desktop

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

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

оверфит начинается с головы, а ощущается гораздо ниже

История с продвижением математики вперед с помощью ML пока не закончилась

Скоро будет онлайн-доклад от известного математического физика Сергея Гукова , где они решили один из вопросов в теории групп , который стоял 39 лет с помощью МЛ

https://t.me/sberlogabig/514

Все, преза кончилась. Весь шитпост спрячу в первый пост. Спасибо, что были с нами

BeVIT на ваших эпл часах? А может лучше на роботе пылесосе?

Эпл добавил neural engine в часы и обещают инференсить dense transformers

Сергей Фиронов завел свой канал. Если вы не в курсе кто это, вам тем более надо подписаться

https://t.me/abacabadabacaba404

Снова про Polars.
Очень рекомендую подкаст для свободных слушателей на английском о том, как библиотека построена с точки зрения Rust сообщества:
Spotify: https://open.spotify.com/episode/7CrTW3a3X2Kd2q6at3LsJW?si=xqIHROIlTKut5fYCKcda_Q
Self-hosted: https://rustacean-station.org/episode/ritchie-vink/

Вот пока слушал подкаст еще раз вдохновился всем объяснить почему polars круто и быстро.

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

Достигается все известным трюкам, просто вынесенным в Python-интерфейс и выполняемым локально, а не на далекой и сложной для дебага JVM в облаке с множеством уровней доступа и доступ-привратниками Data Lake, которые тайно молятся Adeptus Mechanicus уже пять поколений.

Первый кирпичик — это ленивое вычисление (lazy evaluation). В Pandas для выполнения одной операции условно есть два пути: использовать исключительно Python-движок (так никто не делает, но можно), что, конечно, медленно. Второй вариант — конвертировать данные в Cython и обрабатывать их с его помощью. Для этого нужно сначала выести строгие типы данных, сконвертировать данные в них, подобрать нужный кусочек Cython-кода, выполнить вычисления, а затем сконвертировать данные обратно в Python-объекты и вернуть результат. Автоматически и без головной боли, но надо так делать для каждой операции, а их у нас в пайплайне могут быть сотни.

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

Второй кирпичик — это стриминг (streaming). Предположим, данных стало существенно больше или ресурсов стало меньше. Классический пример: вам на Kaggle дали 250 ГБ таблиц для расчета фичей для вашего ML. У вас есть 32 ГБ ОЗУ, так что все эти таблицы вместе в память не влезут. Обычно решение выглядит так: мы считаем одну группу фич, сохраняем их в памяти для финального этапа (или пишем в CSV), и, ловко оперируя gc.collect() и del, выбрасываем ненужные промежуточные куски из памяти Python. Получается неудобно и костыльно.

Стриминг позволяет сделать что-то подобное, но интеллектуально и автоматически. Polars строит индекс по таблицам и разбивает все данные на части, не загружая их полностью в память. Затем вычисляет связи между этими батчами и оптимизирует граф их взаимодействий так, чтобы в самом "широком по памяти" месте графа использовать не более доступной памяти, но при этом обрабатывать каждый батч как можно быстрее. И только после этого читает каждый индексированный батч данных с диска, обрабатывает его и выполняет вычисления до конца пайплайна. А если вдруг где-то не хватит места, то Polars может притормозить и дампнуть какой-нибудь батч на диск, чтобы обработать прочие. Это можно сравнить с тем, как если нужно выкопать яму, вместо попытки сразу сдвинуть тонну песка, можно впятером быстро перекидать его лопатами. Только представьте, как это шикарно дружится с Parquet!

Если представить не можете, ставьте 🤔️️️️️️. Напишу пост про Parquet и станет сильно понятнее

Как ведет себя поиск по эмбедингам разных моделей при применении Binary Quantization?

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

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

У Qdrant есть не только векторная база данных, но и fastembed, питонический пакет для быстрого и простого извлечения эмбеддингов. Быстро — потому что поддержка параллелизации встроена из коробки и работает без лишних усилий на разных бекендах. Просто — потому что минимум зависимостей и все они лёгкие, без необходимости тянуть за собой 3 Гб torch или 1.5 Гб Tensorflow. Эмбеддинги можно извлекать как из текстов, так и из картинок.

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

Вопросы, которые я себе задал:
1. Как влияет использование разных моделей на производительность Qdrant?
2. Как изменяется время поиска для разных моделей при увеличении параметра EF (который отвечает за количество связей на очередном слое HNSW)?
3. Какие модели наименьшим образом деградируют при переключении в режим BQ?
4. Что объединяет модели, которые работают с BQ хорошо и плохо?

Для ответа на эти вопросы я взял 10% данных Imagenet с любимого Kaggle, заэмбеддил их и залил в базу. Бенчмарк сравнивал метрики качества поиска с Exact search (честное сравнение каждого запроса со всеми объектами в базе) по метрике Dot_product. Для тестирования использовал все доступные в fastembed модели для картинок:

clip-ViT-B-32-vision — живая классика.
Unicom-ViT-B-16 — специальная модель из open metric learning.
Unicom-ViT-B-32 — тоже модель для open metric learning (по менбше).
ResNet50 — полуживая классика.

Основные выводы:
1. Время поиска линейно зависит от параметра EF, а скорость поиска — от размера эмбеддингов.
2. Качество поиска от EF скейлится логарифмически, что делает этот компромисс очень выгодным.
3. ResNet50 плохо работает с BQ, в то время как модели, специально обученные для metric learning, показывают минимальную деградацию.

Общий вывод:
Если бы я начинал стартап по поиску похожих лиц, то выбрал бы Unicom-16b. Это позволило бы при росте числа лиц легко переключиться на Binary Quantization с оверсемплингом и минимально потерять в качестве.

А теперь приглашаю к обсуждению в комментариях:

1. Влияет ли loss-функция, на которую обучалась модель, на её деградацию в BQ?
2. Какие модели стоит ещё попробовать?
3. Какую другую метрику близости стоило использовать для сравнения и почему?

Ускоряем HNSW: Квантизация для ANN-поиска

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

Реализуем это максимально просто и эффективно: заменим все значения больше нуля на единицы, а все, что меньше нуля — на нули. Вот и все, Binary Quantization готова.

Что это дает? Значительное ускорение поиска. Вектор длиной 512 можно упаковать в 64 байта и использовать SIMD-инструкции на CPU. Почему это не сломает поиск? Потому что эмбединги как и сами нейросети содержат множество избыточных параметров, от которых можно избавиться без заметной потери качества. Иногда даже лучше становится!

Оптимальный подход — комбинированный. Сначала строим бинарный индекс, отбираем кандидатов с запасом например в два раза больше чем нам надо объектов, а затем выполняем полноценный поиск (либо в лоб, либо с использованием HNSW). Плюс ко всему, теперь весь бинарный индекс можно хранить в оперативной памяти и загружать полные вектора только по мере необходимости.

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

Что за HNSW такой?

Базовый подход, на котором работает Qdrant, — это HNSW (Hierarchical Navigable Small World). Давайте разберёмся, что это такое и как оно работает.

Small world graphs — это такие графы, которые характеризуются высоким коэффициентом кластеризации и малым расстоянием между любой парой вершин. Navigable Small World использует эти свойства для поиска ближайших соседей в многомерном пространстве. Представим, что мы строим такую структуру на наших эмбеддингах, чтобы перемещаться по ней было эффективно. Как добиться этой эффективности?

Начинаем с эмбеддинга случайного объекта из нашей базы и шагаем по рёбрам графа в сторону эмбеддинга-запроса, пока не сойдёмся к локальному минимуму. Для каждой пары эмбедингов мы можем посчитать расстояние, так что идти в сторону ближайшего к эмбедингу-запросу вполне себе можем на каждом шаге. Если бы мы связали ребрами все эмбеддинги, каждый с каждым, то минимальное расстояние находилось бы за один шаг, но пришлось бы просмотреть n дистанций. Если связать все эмбеддинги в двусвязный список, то на каждом шаге будет выполняться только одно сравнение, но шагов придётся сделать столько, сколько у нас точек, что тоже не очень эффективно. Зато уже n/2 в среднем! Как найти баланс? Никак, надо тестить на каждой новой базе

Но есть некоторое соображение: рёбра "средней длины" в графе часто оказываются наименее полезными. По ним мы движемся к точке с умеренной скоростью, но их слишком много, и приходится делать много шагов. Это как передвигаться на автобусе в пределах МКАДа — долго и автобусов слишком много, так что приходится делать кучу пересадок. Легче доехать на метро до нужной станции, а затем сделать последнюю милю на самокате.
Так что, построим наш граф поиска следующим образом:

1. Посчитаем расстояние от каждого объекта до каждого.
2. Возьмём случайный объект из базы и проверим, есть ли он в нашем графе поиска. Если есть — пропускаем. В первом прогоне его, конечно, там нет, но дальше цикл будет работать.
3. Возьмём X процентов ближайших объектов к целевому и построим между ними рёбра.
4. Сделаем то же самое с Y процентами самых дальних объектов.
5. Повторяем с пункта 2, пока не добавим в граф все объекты из базы.

Теперь на первых шагах мы будем часто пользоваться длинным ребрами, и в конце искать оптимум за счет коротких.
Да, в редких случаях (скажем, в 1% случаев) мы не найдём самого ближайшего соседа, но зато будем работать гораздо быстрее — скажем, в 12 раз. Конечно, всё сильно зависит от реализации, но ускорение впечатляет.

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

А еще HNSW- в русской раскладке это РТЫЦ. Живите с этим

Кто такие ANN?

Вот сетап из 2018 года, которая отлично иллюстрирует, зачем нам нужны методы ускорения поиска похожих объектов, в частности, ANN (Approximate Nearest Neighbor). Сейчас все их используют для RAG, но мою историю я прочувствовал лично.

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

Маленькая деталь: по каким-то причинам почти все мужчины оказывались похожи на Стивена Вулфа

К сожалению, на том хакатоне первое место занял, кажется, Noize, а третье досталось девченкам, которые запустили домашку какого-то ММПшника с гитхаба по баесовским методам для склеивания нескольких плохих фоток в одну хорошую. Мы ничего не получили и на наш проект забили, а через полгода появился Gradient: Celebrity Look Like от того же PicsArt, который стал очень популярным и подозрительно похожим на нашу идею. Так я понял, зачем на самом деле нужны продуктовые хакатоны.

Представим, что мы бы продолжили наш сервис развивать. Пока у нас был датасет из 1000 знаменитостей, можно было справляться с поиском в лоб. Мы просто брали эмбеддинги размером в 512, меряли dot_distance каждый с каждым, и готово. Но дела сильно усложняются, если у нас миллион пользователей. А если хочется находить по-настоящему похожие фото, то может понадобиться и 100 миллионов изображений.

И вот тогда нужны ANN. Зачем сравниваться для запроса со всеми, если можно построить умную структуру данных и делать гораздо меньше сравнений? Примерно как в поиске по бинарному дереву, только сложнее и с учётом специфики задачи. ANN позволяет находить "почти ближайших соседей" за гораздо меньшее время, чем прямой перебор, что становится критически важным, когда база для поиска стремительно пухнет.

Если юзкейс кажется не очень, то представьте что мы на маркетплейсе все платья прогнали через Clip и хотим искать по текстовому запросу 'Красное платье' , даже если в описание указано, что платье 'Алое'.

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