V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zxCoder
V2EX  ›  问与答

请教一个算法复杂度问题

  •  
  •   zxCoder · 2022-07-14 09:03:18 +08:00 · 698 次点击
    这是一个创建于 864 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有 N 个 embedding (就是一列浮点数),和另外 M 个 embedding 。

    要求出这 N 个 embedding 分别在另外 M 个 embedding 里相似度最高的那个 embedding 。

    这个算法复杂度最优能做到什么程度?不考虑实现问题

    相似度可以看成 O(1) 就行

    zhangxh1023
        1
    zhangxh1023  
       2022-07-14 09:18:53 +08:00
    猜测一波
    相似度是啥?如果是最接近的值,或者可以排序,那就可以 O((N + M)logM)?
    zxCoder
        2
    zxCoder  
    OP
       2022-07-14 09:21:32 +08:00
    @zhangxh1023 相似度是余弦相似度,不过这里看成 O(1)复杂度就行
    msaionyc
        3
    msaionyc  
       2022-07-14 10:11:16 +08:00
    O(NM)
    otakustay
        4
    otakustay  
       2022-07-14 10:21:36 +08:00
    提前让 2 个数组都有序可以快不少,不然就是 O(NM)了
    Jooooooooo
        5
    Jooooooooo  
       2022-07-14 10:41:20 +08:00
    有个隐含的问题是, "相似度" 这个计算是否具备某种关联性.

    举个例子, 相似度是 f 的话, 那么已知 f(a, b) 和 f(b, c) 的前提下, 是否能获得 f(a, c) 呢?

    或者按照楼上所说, 排序好的数据相似度有更好的结构信息吗?
    yuruizhe
        6
    yuruizhe  
       2022-07-14 14:10:44 +08:00
    本质是查找相似度最高的 embeding ,而不是计算相似度
    所以实际问题是:向量检索的最快方法有哪些?
    暴力检索 100%最精确最耗时,近似最近邻 ANN 检索会有速度与准确性的 trade-off ,可以参考 https://yongyuan.name/blog/ann-search.html 入门介绍
    princelai
        7
    princelai  
       2022-07-14 14:18:22 +08:00
    我做 1xM 的余弦相似都使用 scipy 的 cKDTree,我特地搜了一下,文档里这句话应该就是答案吧

    https://scikit-learn.org/stable/modules/neighbors.html#k-d-tree
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2809 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 11:51 · PVG 19:51 · LAX 03:51 · JFK 06:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.