Нахождение похожих векторов в субквадратичном времени

9

Позволять d:{0,1}k×{0,1}kRбыть функцией, которую мы называем функцией подобия . Примерами функции подобия являются косинусное расстояние,l2 норма, расстояние Хэмминга, сходство Жакара и т. д.

Рассматривать n двоичные векторы длины k: v({0,1}k)n,

Наша цель - сгруппировать векторы, которые похожи. Более формально, мы хотим вычислить граф подобия, где узлы - это векторы, а ребра - векторы, которые похожи (d(v,u)ϵ).

n а также k очень большие числа, и сравнивая две длины k векторы дорогие, мы не можем сделать всю грубую силу O(n2)операции. Мы хотим вычислить граф подобия с существенно меньшим количеством операций.

Это возможно? Если нет, мы можем вычислить приближение к графу, которое содержит все ребра в графе подобия плюс, возможно, самое большееO(1) другие края?

Баран
источник
Должно ли это быть ε скорее, чем ε?
Усул
@usul Спасибо за ваш комментарий :) Здесь нам интересно сгруппировать элементы, которые очень похожи. Я отредактировал вопрос, надеюсь, теперь это понятно.
Рам
Похоже, вы могли бы использовать хеширование, сохраняющее сходство ( arxiv.org/pdf/1311.7662v1.pdf ), чтобы уменьшить размер проблемы.
РБ
4
Этот вопрос не совсем определен, пожалуйста, предоставьте более подробную информацию. Например, еслиd дается оракулом, то вы, очевидно, не можете сделать лучше, чем (N2),
domotorp
5
Ты работаешь на твиттер? blog.twitter.com/2014/all-pairs-sdentifity-via-dimsum Серьезно, даже определить , есть ли ребро в этом графе (т. е. это не независимый набор вершин), будет очень трудно сделать быстрее, чемО(N2)для произвольной функции подобия.
Райан Уильямс

Ответы:

5

Там может быть способ вставить теорему Джонсона-Линденштраусса в эту проблему. По сути, JL заявляет, что вы можете проецировать данные больших размеров в пространства меньших размеров таким образом, что попарные расстояния почти сохраняются. С практической точки зрения, у Ахлиоптаса есть статья под названием « Случайные проекции , удобные для баз данных»: Джонсон-Линденштраусс с бинарными монетами, которая делает эту проекцию случайным образом, что довольно хорошо работает на практике.

Теперь, конечно, ваша функция подобия не совсем совпадает с той, что вписывается в теорему JL. Тем не менее, это похоже на функцию расстояния, и, возможно, некоторые из приведенных выше теорий могут помочь.

wyer33
источник