这是一个创建于 870 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 N 个 embedding （就是一列浮点数），和另外 M 个 embedding 。
要求出这 N 个 embedding 分别在另外 M 个 embedding 里相似度最高的那个 embedding 。
这个算法复杂度最优能做到什么程度？不考虑实现问题
相似度可以看成 O(1) 就行
 |
1
zhangxh1023 2022-07-14 09:18:53 +08:00
猜测一波
相似度是啥？如果是最接近的值，或者可以排序，那就可以 O((N + M)logM)？ |
 |
2
zxCoder OP @zhangxh1023 相似度是余弦相似度，不过这里看成 O(1)复杂度就行
|
 |
3
msaionyc 2022-07-14 10:11:16 +08:00
O(NM)
|
 |
4
otakustay 2022-07-14 10:21:36 +08:00
提前让 2 个数组都有序可以快不少，不然就是 O(NM)了
|
 |
5
Jooooooooo 2022-07-14 10:41:20 +08:00
有个隐含的问题是, "相似度" 这个计算是否具备某种关联性.
举个例子, 相似度是 f 的话, 那么已知 f(a, b) 和 f(b, c) 的前提下, 是否能获得 f(a, c) 呢? 或者按照楼上所说, 排序好的数据相似度有更好的结构信息吗? |
 |
6
yuruizhe 2022-07-14 14:10:44 +08:00
本质是查找相似度最高的 embeding ，而不是计算相似度
所以实际问题是：向量检索的最快方法有哪些？ 暴力检索 100%最精确最耗时，近似最近邻 ANN 检索会有速度与准确性的 trade-off ，可以参考 https://yongyuan.name/blog/ann-search.html 入门介绍 |
 |
7
princelai 2022-07-14 14:18:22 +08:00
我做 1xM 的余弦相似都使用 scipy 的 cKDTree,我特地搜了一下，文档里这句话应该就是答案吧
https://scikit-learn.org/stable/modules/neighbors.html#k-d-tree |
Select Language