有 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 |