东莞服装网站建设,东莞网站建设排行,如何自建网页,全国网站备案拍照文章目录 1. \textbf{1. } 1. 导论 1.1. \textbf{1.1. } 1.1. 研究背景 1.2. \textbf{1.2. } 1.2. 本文的研究 1.3. \textbf{1.3. } 1.3. 有关工作 2. \textbf{2. } 2. 对 OOD \textbf{OOD} OOD负载的分析与验证 2.1. \textbf{2.1. } 2.1. 初步的背景及其验证 2.1.1. \textbf{2… 文章目录 1. \textbf{1. } 1. 导论 1.1. \textbf{1.1. } 1.1. 研究背景 1.2. \textbf{1.2. } 1.2. 本文的研究 1.3. \textbf{1.3. } 1.3. 有关工作 2. \textbf{2. } 2. 对 OOD \textbf{OOD} OOD负载的分析与验证 2.1. \textbf{2.1. } 2.1. 初步的背景及其验证 2.1.1. \textbf{2.1.1. } 2.1.1. 对模态差距的验证 2.1.2. SOTA-ANN \textbf{2.1.2. }\textbf{SOTA-ANN} 2.1.2. SOTA-ANN在 OOD \textbf{OOD} OOD任务上的表现 2.2. \textbf{2.2. } 2.2. 对 OOD \textbf{OOD} OOD上 ANN \textbf{ANN} ANN工作负载的分析 2.2.1. OOD-ANNS \textbf{2.2.1. OOD-ANNS} 2.2.1. OOD-ANNS和 ID-ANNS \textbf{ID-ANNS} ID-ANNS的两个差异 2.2.2. \textbf{2.2.2. } 2.2.2. 为何传统 SOTA-ANN \textbf{SOTA-ANN} SOTA-ANN在 ODD \textbf{ODD} ODD表现不佳 3. RoarGraph \textbf{3. RoarGraph} 3. RoarGraph 3.1. RoarGraph \textbf{3.1. RoarGraph} 3.1. RoarGraph的设计思路 3.2. RoarGraph \textbf{3.2. RoarGraph} 3.2. RoarGraph的构建: 三个阶段 3.2.1. \textbf{3.2.1. } 3.2.1. 阶段 1 \textbf{1} 1: 查询 ↔ \boldsymbol{\xleftrightarrow{}} 基础二分图构建 3.2.2. \textbf{3.2.2. } 3.2.2. 阶段 2 \textbf{2} 2: 领域感知投影 3.2.3. \textbf{3.2.3. } 3.2.3. 连通性增强 3.3. RoarGraph \textbf{3.3. RoarGraph} 3.3. RoarGraph性能的验证 3.3.1. \textbf{3.3.1. } 3.3.1. 实验设置 3.3.2. \textbf{3.3.2. } 3.3.2. 实验结果 3.4. RoarGraph \textbf{3.4. RoarGraph} 3.4. RoarGraph的一些讨论 原文章: RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search \text{RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search} RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search 1. \textbf{1. } 1. 导论 1.1. \textbf{1.1. } 1.1. 研究背景 1️⃣跨模态检索 含义使用某个模态的数据作为 query \text{query} query返回另一个模态中语义相似的内容示例输入Apple后返回苹果的照片 2️⃣模态差距 (gap) \text{(gap)} (gap)不同模态数据即使映射到同一语义空间(比如用 CLIP \text{CLIP} CLIP)其分布特征仍差距显著 \quad 3️⃣两种 ANN \text{ANN} ANN 单模态 ANN \text{ANN} ANN查询向量分布 ↔ ID \xleftrightarrow{\text{ID}} ID 基础数据分布即查询来源于与数据库数据相同的分布跨模态 ANN \text{ANN} ANN查询向量分布 ↔ OOD \xleftrightarrow{\text{OOD}} OOD 基础数据分布即查询来源于与数据库数据不同的分布 1.2. \textbf{1.2. } 1.2. 本文的研究 1️⃣研究动机当前 SOTA \text{SOTA} SOTA的 ANN \text{ANN} ANN都是单模态的在 OOD \text{OOD} OOD负载上表现差 2️⃣研究内容 OOD \text{OOD} OOD工作负载分析跨模态后性能下降源于查询过远 标签分散 → \text{→} →收敛变慢 / / /跳数增加 类型查询 ↔ 距离 \boldsymbol{\xleftrightarrow{距离}} 距离 基础数据查询最邻近 i ↔ 距离 \boldsymbol{i\xleftrightarrow{距离}} i距离 查询最邻近查询 ↔ 分布 \boldsymbol{\xleftrightarrow{分布}} 分布 基础数据单模态 ANN \text{ANN} ANN近(基本假设)近(基本假设) ID \text{ID} ID跨模态 ANN \text{ANN} ANN远(实验得到)远(实验得到) OOD \text{OOD} OOD RoarGraph \text{RoarGraph} RoarGraph的提出 原理让查询参与图构建 → \text{→} →将[查询点 ↔ \xleftrightarrow{} 基础点]邻接关系投影到基础点 → \text{→} →形成仅有基础点的图意义让空间上很远但是查询上很近的点相连从而能高效处理 OOD-ANNS \text{OOD-ANNS} OOD-ANNS 效果在跨模态数据集上实现了 QPS \text{QPS} QPS和 Recall \text{Recall} Recall指标的提升 1.3. \textbf{1.3. } 1.3. 有关工作 方法核心思想优缺点束搜索终止利用查询训练分类模型判断何时终止搜索提升效率但训练成本较高图卷积 (GCN) \text{(GCN)} (GCN)引入 GCN \text{GCN} GCN学习最优搜索路径路径优化明显但训练成本较高 GCNRL \text{GCNRL} GCNRL强化学习与 GCN \text{GCN} GCN结合引导搜索路由提升效果显著但训练成本较高 GraSP \text{GraSP} GraSP概率模型与子图采样学习边重要性性能优化明显但索引构建成本高 ScaNN \text{ScaNN} ScaNN结合向量量化和 PQ \text{PQ} PQ进行分区与压缩压缩与搜索性能高效但依赖调参 2. \textbf{2. } 2. 对 OOD \textbf{OOD} OOD负载的分析与验证 2.1. \textbf{2.1. } 2.1. 初步的背景及其验证 2.1.1. \textbf{2.1.1. } 2.1.1. 对模态差距的验证 1️⃣ OOD \text{OOD} OOD的量化 距离类型衡量什么如何理解 Wasserstein \text{Wasserstein} Wasserstein距离两个分布间的差异把一个分布搬到另一个的最小代价 Mahalanobis \text{Mahalanobis} Mahalanobis距离一个向量到一个分布的距离一个点相对于一个分布的异常程度 1️⃣实验 1 1 1用 Wasserstein \text{Wasserstein} Wasserstein距离衡量 OOD \text{OOD} OOD特性 数据集基础数据集中抽取的无交叉集 B 1 / B 2 B_1/B_2 B1/B2 OOD \text{OOD} OOD的查询集 Q Q Q结果 Wasserstein ( B 1 , Q ) \text{Wasserstein}(B_1,Q) Wasserstein(B1,Q)和 Wasserstein ( B 2 , Q ) \text{Wasserstein}(B_2,Q) Wasserstein(B2,Q)大致是 Wasserstein ( B 1 , B 2 ) \text{Wasserstein}(B_1,B_2) Wasserstein(B1,B2)两倍 2️⃣实验 2 2 2用 Mahalanobis \text{Mahalanobis} Mahalanobis距离衡量 OOD \text{OOD} OOD特性 数据集满足分布 P P P的基础数据来自 ID \text{ID} ID查询集的 q i d q_{id} qid来自 OOD \text{OOD} OOD查询集的 q o o d q_{ood} qood结果 Mahalanobis ( q id , P ) Mahalanobis ( q ood , P ) \text{Mahalanobis}(q_{\text{id}},P)\text{}\text{Mahalanobis}(q_{\text{ood}},P) Mahalanobis(qid,P)Mahalanobis(qood,P) 2.1.2. SOTA-ANN \textbf{2.1.2. }\textbf{SOTA-ANN} 2.1.2. SOTA-ANN在 OOD \textbf{OOD} OOD任务上的表现 1️⃣对传统的 SOTA-ANN \text{SOTA-ANN} SOTA-ANN 索引方法在 OOD \textbf{OOD} OOD上的表现(相比在 ID \textbf{ID} ID上) HNSW \text{HNSW} HNSW性能显著下降在 BeamSearch \text{BeamSearch} BeamSearch过程显著访问更多的结点(要经历更多跳) IVF-PQ \text{IVF-PQ} IVF-PQ性能显著下降需要更多的聚类数才能达到相同的 Recall \text{Recall} Recall 2️⃣对改进的 ANN \text{ANN} ANN针对 OOD-ANNS \text{OOD-ANNS} OOD-ANNS的首个图索引 RobustVamana(OOD-DiskANN) \text{RobustVamana(OOD-DiskANN)} RobustVamana(OOD-DiskANN) 原理先用 Vamana \text{Vamana} Vamana建图然后再用 RobustStitch \text{RobustStitch} RobustStitch根据查询向量连接新的边性能比 DiskANN \text{DiskANN} DiskANN在 OOD \text{OOD} OOD任务上提升了 40% \text{40\%} 40%性能但是查询速度慢了 × 4 -10 {\text{×}4\text{-10}} ×4-10 2.2. \textbf{2.2. } 2.2. 对 OOD \textbf{OOD} OOD上 ANN \textbf{ANN} ANN工作负载的分析 2.2.1. OOD-ANNS \textbf{2.2.1. OOD-ANNS} 2.2.1. OOD-ANNS和 ID-ANNS \textbf{ID-ANNS} ID-ANNS的两个差异 1️⃣两种差异及实验结果 OOD \text{OOD} OOD查询离其最邻近很远即 δ ( q ood , i t h -NN ood ) ≫ δ ( q id , i t h -NN id ) \delta\left(q_{\text{ood}}, i^{t h} \text{-NN}_{\text{ood}}\right) \text{≫} \delta\left(q_{\text{id}}, i^{t h} \text{-NN}_{\text{id}}\right) δ(qood,ith-NNood)≫δ(qid,ith-NNid)左为 i 1 i\text{}1 i1时的分布结果 OOD \text{OOD} OOD查询的最邻近彼此原理 10 0 t h -NN 100^{t h} \text{-NN} 100th-NN互相之间的平均距离实验结果如右 2️⃣对差异的直观理解 简单(概念)示例 ID \text{ID} ID查询查询与其最邻近在球面上相互靠近 ODD \text{ODD} ODD查询查询在球心其最邻近在球面上(由此距离较远且查询不多 \text{} 分散分布) 真实示例真实数据 PCA \text{PCA} PCA降到二维的视图 ID \text{ID} ID查询更为集中 2.2.2. \textbf{2.2.2. } 2.2.2. 为何传统 SOTA-ANN \textbf{SOTA-ANN} SOTA-ANN在 ODD \textbf{ODD} ODD表现不佳 0️⃣传统 ANN \text{ANN} ANN的设计 基于两假设查询 / / /数据同分布 k k k个最近邻彼此相互靠近(邻居的邻居是邻居)刚好全反的设计的思路 建图用 BeamSearch \text{BeamSearch} BeamSearch来构建 KNN \text{KNN} KNN图 → \text{→} →空间中相近的点转化为图中紧密连接的结点搜索从中心点开始 GreedySearch \text{GreedySearch} GreedySearch 1️⃣在基于图 ANN \text{ANN} ANN上 OOD \text{OOD} OOD会使得搜索空间增大 可识别搜索空间包围当前访问结点 x x x的 B s ( x ) B k ( 1 st -NN , R ) B^{s}(x)\text{}B^{k}\left(1^{\text{st}}\text{-NN}, R\right) Bs(x)Bk(1st-NN,R) 球 B k ( 1 st -NN , R ) B^{k}\left(1^{\text{st}}\text{-NN}, R\right) Bk(1st-NN,R)以 1 st -NN 1^{\text{st}}\text{-NN} 1st-NN为球心 k k k邻近间互相距离 δ ( i th -NN , j th -NN ) \delta\left(i^{\text{th}}\text{-NN}, j^{\text{th}}\text{-NN}\right) δ(ith-NN,jth-NN)最大值为半径球 B s ( x ) B^{s}(x) Bs(x)以当前结点 x x x为圆心以 δ ( x , i th -NN ) \delta\left(x, i^{\text{th}}\text{-NN}\right) δ(x,ith-NN)的最大值(到最远最邻近的距离)为半径 OOD \text{OOD} OOD的影响搜索空间大幅增大 对 B k B^{k} Bk由于 OOD \text{OOD} OOD的性质 R ood ≫ R id R_{\text {ood }}\text{≫}R_{\text{id}} Rood ≫Rid这一差异在体积层面放大到 ( R ood R id ) D \left(\cfrac{R_{\text {ood }}}{R_{\text{id}}}\right)^D (RidRood )D级别对 B s B^{s} Bs由于 OOD \text{OOD} OOD的性质 δ ( x , i th -NN ood ) ≫ δ ( x , i th -NN id ) \delta\left(x, i^{\text{th}}\text{-NN}_{\text{ood}}\right)\text{≫}\delta\left(x, i^{\text{th}}\text{-NN}_{\text{id}}\right) δ(x,ith-NNood)≫δ(x,ith-NNid)使得体积也大幅膨胀 对搜索过程的影响 对于 ID \text{ID} ID查询由于最近邻彼此靠近 GreedySearch \text{GreedySearch} GreedySearch可以使 B s ( x ) B^{s}(x) Bs(x)轻松收敛起点 - 近邻1 - 近邻2 - 近邻3 (一个小范围内)对于 OOD \text{OOD} OOD查询最近邻方向分散难以收敛需要更大的 Beam \text{Beam} Beam宽度 / / /搜索路径等 近邻2↗️
起点 - 近邻1 - 近邻3 (分散在大范围内)↘️ 近邻42️⃣在基于划分 IVF \text{IVF} IVF上 原理上 IVF \text{IVF} IVF先将原数据分簇 ID \text{ID} ID查询最邻近集中在少数几个相邻簇中 OOD \text{OOD} OOD查询最邻近分散在多个不相邻簇中 实验上 OOD \text{OOD} OOD查询需要扫描更多的簇性能下降 2.5 2.5 2.5倍 3. RoarGraph \textbf{3. RoarGraph} 3. RoarGraph 3.1. RoarGraph \textbf{3.1. RoarGraph} 3.1. RoarGraph的设计思路 1️⃣面向解决三种挑战 边的建立如何连接查询 / / /基础两类结点同时避免基础结点度数太高搜索效率查询结点要保持极高出度以覆盖基础节点但同时也会大幅增加跳数 / / /内存开销连通性避免出现孤立结点独立子图 1️⃣大致的设计流程 构建建立查询 ↔ \boldsymbol{\xleftrightarrow{}} 基础二分图 → \text{→} →将邻接信息投影到基础点中 → \text{→} →增强连接查询同样是用 BeamSearch \text{BeamSearch} BeamSearch 3.2. RoarGraph \textbf{3.2. RoarGraph} 3.2. RoarGraph的构建: 三个阶段 3.2.1. \textbf{3.2.1. } 3.2.1. 阶段 1 \textbf{1} 1: 查询 ↔ \boldsymbol{\xleftrightarrow{}} 基础二分图构建 1️⃣二分图概述 基本概念将所有的点分为两个集合所有边必须连接不同子集的点不能内部连接 在此处两子集查询结点 基础节点两种边[查询结点 → \text{→} →基础结点] \text{} [查询结点 ← \text{←} ←基础结点] 2️⃣构建过程概述 \quad 预处理计算每个查询向量的真实 N q -NN N_q\text{-NN} Nq-NN标签边构建 方向操作查询点 → \text{→} →基础点查询点 → 连接 \xrightarrow{连接} 连接 查询点的 N q -NN N_q\text{-NN} Nq-NN基础点基础点 → \text{→} →查询点查询点 ← 连接 \xleftarrow{连接} 连接 查询点的 1 -NN 1\text{-NN} 1-NN基础点查询点 → 断连 \xrightarrow{断连} 断连 查询点的 1 -NN 1\text{-NN} 1-NN基础点 示例预处理: T1 - X1, X2, X3 (Nq3)
边构建: T1 - X2, X3 T1 - X1 2️⃣构建过程分析 结点度数的考量 高查询结点出度提高 N q N_q Nq值增加[基础点 → 覆盖性 重叠性 \xrightarrow[覆盖性]{重叠性} 重叠性 覆盖性查询点]使多基础点可由同一查询点联系低基础节点出度为了解决上述挑战 1 1 1目的在于提高二分图上的搜索效率 边方向的考虑不进行双向连接避免二分图搜索时要去检查邻居的邻居( N q 2 N_q^2 Nq2)预处理: T1 - X1, X2, X3 (Nq3)
边构建: T1 - X1, X2, X3 T1 - X1T1 - X2T1 - X33.2.2. \textbf{3.2.2. } 3.2.2. 阶段 2 \textbf{2} 2: 领域感知投影 1️⃣一些分析 优化动机二分图内存消耗高(额外存储了查询节点)搜索路径长(需要额外经过查询结点)关于投影 目的移除二分图中的查询结点并保留从查询分布获得的邻近关系方式最简单的可将查询点所连的全部基础点全连接(度数太高)优化方法如领域感知投影 2️⃣投影过程 预处理 遍历查询点获得与查询点相连的最邻近基础点查询Q - {B1, B2, B3, B4, B5} (Q连接了5个基础节点)选择中心点即查询点的 1-NN \text{1-NN} 1-NN点作为 Pivot \text{Pivot} Pivot查询Q - {B1, B2, B3, B4, B5} (Q连接了5个基础节点)pivot排序基础结点将余下 N q -NN N_q\text{-NN} Nq-NN点按与 Pivot \text{Pivot} Pivot的距离排序 感知投影 连接让中心点与余下点建立连接B1 - B2 (最近)
B1 - B3 (次近)
B1 - B4 (较远)
B1 - B5 (最远)过滤保证与 Pivot \text{Pivot} Pivot连接方向的多样性 条件含义操作 Dist ( X , Y ) Dist ( Pivot , Y ) \text{Dist}(X,Y)\text{}\text{Dist}(\text{Pivot},Y) Dist(X,Y)Dist(Pivot,Y)该方向已有连接则筛掉 Y Y Y(不与 Pivot \text{Pivot} Pivot建立连接) Dist ( X , Y ) Dist ( Pivot , Y ) \text{Dist}(X,Y)\text{}\text{Dist}(\text{Pivot},Y) Dist(X,Y)Dist(Pivot,Y)代表新的搜索方向则保留 Y Y Y(可与 Pivot \text{Pivot} Pivot建立连接) 填充当 Pivot \text{Pivot} Pivot的出度小于度数限制则又重新连接之前过滤掉的结点 3.2.3. \textbf{3.2.3. } 3.2.3. 连通性增强 1️⃣为何要增强仅依赖于二分图的覆盖范围投影图的连通性还太低对 GreedySearch \text{GreedySearch} GreedySearch不友好 2️⃣增强的方法 检索从基础集的 Medoid \text{Medoid} Medoid开始对每个基础点执行 BeamSearch \text{BeamSearch} BeamSearch得到最邻近(作为候选点)连边在不超过度数限制的前提下让该基础点连接一定数量的候选点作 3.3. RoarGraph \textbf{3.3. RoarGraph} 3.3. RoarGraph性能的验证 3.3.1. \textbf{3.3.1. } 3.3.1. 实验设置 1️⃣数据集 数据集描述查询集索引集 Text-to-Image \text{Text-to-Image} Text-to-Image流行基准数据集含图像和文本查询向量官方 1 w 1\text{w} 1w条余下不重叠数据 LAION \text{LAION} LAION数百万对图像 − - −替代文本对采样 1 w 1\text{w} 1w条余下不重叠数据 WebVid \text{WebVid} WebVid素材网站获取的字幕和视频对采样 1 w 1\text{w} 1w条余下不重叠数据 2️⃣超参数设置 模型超参数列表 HNSW \text{HNSW} HNSW M 32 M\text{}32 M32, efConstruction 500 \text{efConstruction}\text{}500 efConstruction500 NSG \text{NSG} NSG R 64 R\text{}64 R64, C L 500 C\text{}L\text{}500 CL500 τ -MNG \tau\text{-MNG} τ-MNG R 64 R\text{}64 R64, C L 500 C\text{}L\text{}500 CL500, τ 0.01 \tau\text{}0.01 τ0.01 RobustVamana \text{RobustVamana} RobustVamana R 64 R\text{}64 R64, L 500 L\text{}500 L500, α 1.0 \alpha\text{}1.0 α1.0 RoarGraph \text{RoarGraph} RoarGraph N q 100 N_q\text{}100 Nq100(最近邻候选数量), M 35 M\text{}35 M35(出度约束), L 500 L\text{}500 L500(候选集大小) 3️⃣性能指标 Recallk \text{Recallk} Recallk和 QPS \text{QPS} QPS(检索速度) 3.3.2. \textbf{3.3.2. } 3.3.2. 实验结果 1️⃣ QPS \text{QPS} QPS与召回 RoarGraph \text{RoarGraph} RoarGraph最优(超过 RobustVamana \text{RobustVamana} RobustVamana) HNSW/NSG \text{HNSW/NSG} HNSW/NSG差不多, τ -MNG \tau\text{-MNG} τ-MNG最差 2️⃣跳数与召回 RoarGraph \text{RoarGraph} RoarGraph跳数显著减少且随 Recall \text{Recall} Recall的 k k k增大减少趋势下降 3️⃣消融实验对比了二分图 / / /投影图 / / /完整图可见通过邻域感知投影显著提升性能 4️⃣查询集规模即查询集大小占基础集大小比重对索引性能的影响可见起始模型对规模并不敏感 5️⃣在 ID \text{ID} ID负载上的性能 RoarGraph \text{RoarGraph} RoarGraph依旧能打和 HNSW \text{HNSW} HNSW相当 6️⃣索引开销成本使用 10 % 10\% 10%数据可大幅降低构建成本同时保持搜索性能 \quad 3.4. RoarGraph \textbf{3.4. RoarGraph} 3.4. RoarGraph的一些讨论 1️⃣运用场景结合大量历史查询数据用多模态深度学习模型生成嵌入部署在大型检索 / / /推荐系统 2️⃣更新机制 初始搜索 结点查询将新插入下新基础节点 v v v作为查询在基础数据集中搜索其最邻近结点筛选要求最邻近满足曾在图构建过程中与至少一个查询点连接过的基础点反向回溯对该最邻近点回溯到与其曾建立过连接的距离最近的查询点 q q q 子图构建 二分子图将 q ↔ N out ∪ v q\xleftrightarrow{}N_{\text {out}}\text{∪}v q Nout∪v整合为二分子图邻域投影将 v v v作为 Pivot \text{Pivot} Pivot按同样的方式生成投影图 3️⃣删除操作采用墓碑标记法 Tombstones \text{Tombstones} Tombstones即被删结点任参与路由但排除在搜索结果中
