AT
locality sensitive hashing на n-граммах для приближения жакара попробуйте, с достаточно большими бакетами, а дальше брать по примеру из бакета
хорошая мысль, спасибо
Size: a a a
2021 January 14
СШ
мне кажется, эту задачу можно динамикой решить по аналогии с тем как решается задача о рюкзаке
СШ
в качестве стоимости можно взять максимальное расстояние по левенштейну между объектом и другими объектами в рюкзаке.
SD
посчитать все попарные расстояния левенштейна для 100к строк это уже долго, а если масштабировать, то растет квадратично
SD
а еще на это сверху алгоритм накручивать
AT
Вот Сергей чувствует мою боль 🙂
SD
Плавали-знаем 😏
SS
Энкодер берешь по желанию и все это в быстрый индекс, например hnsw. А дальше просто
СШ
поправьте меня, если не прав, но там будет сложность m (сколько мы ищем для анализа)^ 2 * n (сколько всего объектов), если m очень мало, оно должно будет достаточно быстро отрабатывать. Помимо этого, если я правильно понял задачу, нам нужно найти максимально далекие точки, а LSH даст нам наоборот самые близкие
СШ
да и в изначальной постановке задачи не говорится, что этот набор надо собирать с некоторой частотой, а не один раз.
SS
Среди ANN-решений hnsw один из самых быстрых и точных, а инвертировать его выдачу под цели конкретной задачи несложно.
DD
Привет, а вот представьте себе, что у меня есть большое количество коротких строк (товарных названий), скажем 100К.
Среди них очень много близких по написанию, а я хочу выбрать семпл из наиболее разнообразных по некоторой метрике. Например по левенштейну или другой метрике попарной близости.
Есть ли какие-то существующие наработки для такой задачи? Или придется что-то самим выдумывать?
Среди них очень много близких по написанию, а я хочу выбрать семпл из наиболее разнообразных по некоторой метрике. Например по левенштейну или другой метрике попарной близости.
Есть ли какие-то существующие наработки для такой задачи? Или придется что-то самим выдумывать?
Мне кажется, для этой задачи вполне годится эвристическое решение. Например, такое:
1) насэмплить случайную выборку в несколько раз больше, чем нужно, и посчитать внутри неё все попарные расстояния
2) итеративно выкидывать из выборки текст с самым близким средним расстоянием до k ближайших соседей в оставшейся выборке, пока она не уменьшится до нужного размера.
Думаю, что это будет на порядки быстрее, чем строгое решение, и мало отличимо по качеству.
1) насэмплить случайную выборку в несколько раз больше, чем нужно, и посчитать внутри неё все попарные расстояния
2) итеративно выкидывать из выборки текст с самым близким средним расстоянием до k ближайших соседей в оставшейся выборке, пока она не уменьшится до нужного размера.
Думаю, что это будет на порядки быстрее, чем строгое решение, и мало отличимо по качеству.
DD
А ещё можно применить к твоему датасету любой алгоритм кластеризации (мне для больших датасетов нравится Birch, но для него нужно метрическое пространство), и взять по примеру из каждого достаточно крупного кластера.
AT
А ещё можно применить к твоему датасету любой алгоритм кластеризации (мне для больших датасетов нравится Birch, но для него нужно метрическое пространство), и взять по примеру из каждого достаточно крупного кластера.
Вот это мы сейчас как раз и делаем. Хотим поэкспериментировать с альтернативными подходами.
НК
жаль, что там нельзя gpu поставить..
AT
Вообщем что я понял: готовых решений (как в случае кластеризации) нет, костыли на эмпириках - наше все :)
М
locality sensitive hashing на n-граммах для приближения жакара попробуйте, с достаточно большими бакетами, а дальше брать по примеру из бакета
Согласен, lsh, на мой взгляд, будет нормально работать. Можно поиграть с порогом
ЕЗ
да и в изначальной постановке задачи не говорится, что этот набор надо собирать с некоторой частотой, а не один раз.
Можно динамически добавлять элементы в индекс с библиотекой близнецом hnswlib
ЕЗ
для мультиязычности сейчас крутой mT5 трансформер выпустили на huggingface<3
Ваш совет в итоге стал решением. Спасибо! Написал такую функцию, которая всегда возвращает 512 вектор: https://paste.ofcode.org/vynJRq9GLjjDUXrmvdPmbb
A
Ваш совет в итоге стал решением. Спасибо! Написал такую функцию, которая всегда возвращает 512 вектор: https://paste.ofcode.org/vynJRq9GLjjDUXrmvdPmbb
Уверен что 512 возвращать будет всегда?