文献分享: Muvera多向量到单向量的转化方法——原理与理论保证

原论文

详细的理论证明，包含了所有细节

$\text{1. MUVERA}$的全过程

1️⃣文本嵌入：对查询文本和段落文本分别应用嵌入器(如$\text{ColBERTv2}$)，得到各自的多向量嵌入

1. 查询嵌入$Q$： { q 1 , q 2 , . . . , q m } \{q_1,q_2,...,q_m\} {q1​,q2​,...,qm​}，其中$q_i\text{⊆}{\mathbb{R}}^d$即为固定$d$维
2. 段落嵌入$P$： { p 1 , p 2 , . . . , p n } \{p_1,p_2,...,p_n\} {p1​,p2​,...,pn​}，其中$p_i\text{⊆}{\mathbb{R}}^d$即为固定$d$维

2️⃣向量分桶：用$\text{SimHash}$将原有空间分为$2^{k_{\text{sim}}}$个桶，每个桶用长为$k_{\text{sim}}$的定长二进制向量编码

1. 法向抽取：从高斯分布中抽取$k_{\text{sim}}\text{≥}1$个向量$g_1,\dots ,g_{k_{\text{sim}}}\text{∈}{\mathbb{R}}^d$，作为$k_{\text{sim}}$个超平面的法向量
2. 空间划分：$\phi (x)\text{=}\left(1\left(⟨g_1,x⟩\text{>}0\right),\dots ,1\left(⟨g_{k_{\text{sim}}},x⟩\text{>}0\right)\right)$
   • $1\left(⟨g_i,x⟩\text{>}0\right)$：当$⟨g_i,x⟩\text{>}0$成立(即$x$投影在超平面$g_i$的正侧)时，将该位设为$1$
3. 向量分桶：让所有的$m\text{+}n$个嵌入通过$\phi (\cdot )$得到长$k_{\text{sim}}$的二进制编码，相同编码者(即桶编码)放入同一桶

3️⃣向量生成：按照如下三种情况，为每个桶$k$都生成一个子向量${\vec{q}}_{(k)},{\vec{p}}_{(k)}\text{⊆}{\mathbb{R}}^d$

$\text{Case}$	桶$\mathbf{k}$的情况	桶$\mathbf{k}$子向量${\vec{\mathbf{q}}}_{(\mathbf{k})}$	桶$\mathbf{k}$子向量${\vec{\mathbf{p}}}_{(\mathbf{k})}$
$\text{Case-0}$	无 p i → { q 1 , q 2 , . . . ∣ } p_i\text{→}\{q_1,q_2,...\mid{}\} pi​→{q1​,q2​,...∣}	${\vec{q}}_{(k)}=\sum q_i$	${\vec{p}}_{(k)}=$与该桶海明距离最近的$p$
$\text{Case-1}$	单 p i → { q 1 , q 2 , . . . ∣ p } p_i\text{→}\{q_1,q_2,...\mid{}p\} pi​→{q1​,q2​,...∣p}	${\vec{q}}_{(k)}=\sum q_i$	${\vec{p}}_{(k)}=p$
$\text{Case-n}$	多 p i → { q 1 , q 2 , . . . ∣ p 1 , p 2 , . . . } p_i\text{→}\{q_1,q_2,...\mid{}p_1,p_2,...\} pi​→{q1​,q2​,...∣p1​,p2​,...}	${\vec{q}}_{(k)}=\sum q_i$	${\vec{p}}_{(k)}=\frac{1}{\#p}\sum p_j$($p$的质心)

4️⃣向量压缩：对每个${\vec{q}}_{(k)},{\vec{p}}_{(k)}\text{⊆}{\mathbb{R}}^d$应用随机线性投影$\psi \text{:}{\mathbb{R}}^d\text{→}{\mathbb{R}}^{d_{\text{proj}}}(d_{\text{proj}}\text{≤}d)$

1. 投影函数：$\mathbf{\psi }(x)\text{=}\left(\frac{1}{\sqrt{d_{\text{proj}}}}\right)\mathbf{S}x$，其中$\mathbf{S}\text{∈}{\mathbb{R}}^{d_{\text{proj}}\text{×}d}$为随机矩阵
   • 当$d_{\text{proj}}\text{=}d$时$\mathbf{S}$的每个元素$s_{ij}\text{=}1$，即$\mathbf{\psi }(x)\text{=}x$
   • 当$d_{\text{proj}}\text{<}d$时$\mathbf{S}$的每个元素$s_{ij}$满足离散均匀分布$\mathbb{P}r\left[s_{ij}\text{=}1\right]\text{=}\mathbb{P}r\left[s_{ij}\text{=}–1\right]\text{=}\frac{1}{2}$
2. 投影操作：$\{\begin{array}{l}{\vec{q}}_{(k),\psi }\text{⊆}{\mathbb{R}}^{d_{\text{proj}}}\stackrel{\psi \left({\vec{q}}_{(k)}\right)}{\leftarrow }{\vec{q}}_{(k)}\text{⊆}{\mathbb{R}}^d\\ \\ {\vec{p}}_{(k),\psi }\text{⊆}{\mathbb{R}}^{d_{\text{proj}}}\stackrel{\psi \left({\vec{p}}_{(k)}\right)}{\leftarrow }{\vec{p}}_{(k)}\text{⊆}{\mathbb{R}}^d\end{array}$
3. 合并操作：将每个桶的压缩向量依次从左到右合并$\text{→}\{\begin{array}{l}{\vec{q}}_{\psi }\text{=}\left({\vec{q}}_{(1),\psi },\dots ,{\vec{q}}_{(B),\psi }\right)\text{⊆}{\mathbb{R}}^{d_{\text{proj}}{2}^{k_{sim}}}\\ \\ {\vec{p}}_{\psi }\text{=}\left({\vec{p}}_{(1),\psi },\dots ,{\vec{p}}_{(B),\psi }\right)\text{⊆}{\mathbb{R}}^{d_{\text{proj}}{2}^{k_{sim}}}\end{array}$

5️⃣重复生成：重复2️⃣$\text{→}$4️⃣过程$R_{\text{reps}}$次，每次重复完成后生成${\vec{q}}_{i,\psi },{\vec{p}}_{i,\psi }$，拼接所有${\vec{q}}_{i,\psi },{\vec{p}}_{i,\psi }$

1. $Q$最终生成的单向量：${\mathbf{F}}_{\mathrm{que}}(Q)\text{=}\left({\vec{q}}_{1,\psi },\dots ,{\vec{q}}_{R_{\text{reps}},\psi }\right)\text{⊆}{\mathbb{R}}^{d_{\text{proj}}{2}^{k_{sim}}{R}_{\text{reps}}}$
2. $P$最终生成的单向量：${\mathbf{F}}_{\mathrm{doc}}(P)\text{=}\left({\vec{p}}_{1,\psi },\dots ,{\vec{p}}_{R_{\text{reps}},\psi }\right)\text{⊆}{\mathbb{R}}^{d_{\text{proj}}{2}^{k_{sim}}{R}_{\text{reps}}}$

$\text{2. }$定理$\text{2.1}$证明的思路

$\text{3.0. }$定理$\text{2.1}$的主要内容

👉前提$1$：设定$\forall \epsilon ,\delta \text{>}0$(其中$\epsilon \text{≤}\frac{1}{2}$且$\delta \le \epsilon$)，给定单位向量集$P,Q\text{⊆}{\mathbb{R}}^d$并满足$m\text{=}|Q|\text{+}|P|$

👉前提$2$：选择参数$k_{\text{sim}}\text{=}O\left(\frac{1}{\epsilon }\log \left(\frac{m}{\delta }\right)\right)$，$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon \delta }\right)\right)$，$R_{\text{reps}}\text{=}1$

👉结论：$\text{Chamfer}(Q,P)\text{–}\epsilon \text{≤}\text{FDE}(Q,P)\text{≤}\text{Chamfer}(Q,P)\text{+}\epsilon$以$\text{Pr}\text{≥}1\text{–}\delta$概率成立，即给出了$\text{FDE}$相似度的上下界

$\text{2.1. }$无投影无重复时$\text{FDE}$相似度的上界

➡️$\text{Chamfer}$后期交互的本质：一套针对$q_i$向量的映射策略

1. $f(q_i)$操作为将$q_i$映射到某一个 p q i ∈ P = { p 1 , p 2 , . . . , p m } p_{q_i}\text{∈}P\text{=}\{p_1,p_2,...,p_m\} pqi​​∈P={p1​,p2​,...,pm​}向量
2. 在$\text{Chamfer}$后期交互中$f(q_i)\text{=}{p}_{q_i}\text{=}\underset{p\text{∈}P}{\arg }\text{MaxSim}(q_i,P)$，即遍历 p q i ∈ P = { p 1 , p 2 , . . . , p m } p_{q_i}\text{∈}P\text{=}\{p_1,p_2,...,p_m\} pqi​​∈P={p1​,p2​,...,pm​}，最终选取使内积$⟨q_i,p_{q_i}⟩$最大的$p_{q_i}$
3. 最终合并所有的内积$\sum _{i\text{=1}}^n⟨q_i,p_{q_i}⟩$是为$\text{Chamfer}$相似度，即$\sum _{i\text{=1}}^n⟨q_i,p_{q_i}⟩\text{=}\text{Chamfer}(Q,P)\text{=}⟨Q,P^{\prime }⟩$

➡️$\text{Muvera}$分桶的本质：另一套针对$q_i$向量的映射策略

1. 对于单个桶$\text{Bucket-k}$中有$⟨{\vec{q}}_{(k)},{\vec{p}}_{(k)}⟩\text{=}⟨\sum _{k_i}{q}_{k_i},{\vec{p}}_{(k)}⟩\text{=}\sum _{k_i}⟨q_{k_i},{\vec{p}}_{(k)}⟩$，相当于为每个落入该桶$k$的$q_{k_i}$映射了一个${\vec{p}}_{(k)}$
2. 合并$B$个桶的结果有$\sum _{k\text{=}1}^B⟨{\vec{q}}_{(k)},{\vec{p}}_{(k)}⟩\text{=}\sum _{q_i\text{∈}Q}⟨q_i,{\vec{p}}_{(k_{q_i})}⟩$，相当于为每个$q_i\text{∈}Q$都映射一个 p ⃗ ( k q i ) = p q i ∗ ∈ { p ⃗ ( 1 ) , . . . , p ⃗ ( B ) } \vec{p}_{(k_{q_i})}\text{=}p_{q_i}^*\text{∈}\{\vec{p}_{(1)},...,\vec{p}_{(B)}\} p ​(kqi​​)​=pqi​∗​∈{p ​(1)​,...,p ​(B)​}

➡️对两种映射方案的对比：有$⟨q_i,p_{q_i}^{\ast }⟩\text{≤}⟨q_i,p_{q_i}⟩$

1. $p_{q_i}$的得到有且只有一种情况，就是$p_{q_i}\text{=}\arg \underset{p\text{∈}P}{\max }⟨q_i,p⟩\text{=}\underset{p\text{∈}P}{\arg }\text{MaxSim}(q_i,P)$
2. $p_{q_i}^{\ast }$的得到分为三种情况，即$\text{Case-0/Case-n}$(其中视$\text{Case-0}$为$\text{Case-n}$种$\text{n=1}$的情形)
   • $\text{Case-0}$时，假设$q_i$所落入的是桶$k$，则选取离桶$k$编码最近的一点${\hat{p}}_k$，即$p_{q_i}^{\ast }\text{=}{\vec{p}}_{(k)}\text{=}{\hat{p}}_k$
   • $\text{Case-n}$时，假设$q_i$所落入的是桶$k$，则$p_{q_i}^{\ast }\text{=}{\vec{p}}_{(k)}\text{=}\sum _{\phi (p_j)\text{=}k}\frac{1}{\left|P\text{∩}{\phi }^{–1}(k)\right|}{p}_j$，相当于桶$k$种所有$p$向量的质心
3. 定义集合$\text{Pdt=}\{⟨q_i,p_1⟩,⟨q_i,p_2⟩,...,⟨q_i,p_m⟩\}$，根据$p_{q_i}$的定义可知$⟨q_i,p_{q_1}⟩$是$\text{Pdt}$集合的最大值
   • $\text{Case-0}$时，显然有$⟨q_i,p_{q_i}^{\ast }⟩\text{=}⟨q_i,{\hat{p}}_k⟩\text{∈Pdt}$，因此$⟨q_i,p_{q_i}^{\ast }⟩\text{≤}⟨q_i,p_{q_i}⟩$即小于集合最大值
   • $\text{Case-n}$时，对每个$p_j$都有$⟨q_i,p_{q_i}^{\ast }⟩\text{=}⟨q_i,\sum _{\phi (p_j)\text{=}k}\frac{1}{\left|P\text{∩}{\phi }^{–1}(k)\right|}{p}_j⟩\text{=}\sum _{\phi (p_j)\text{=}k}\frac{1}{\left|P\text{∩}{\phi }^{–1}(k)\right|}⟨q_i,p_j⟩$
     • 集合$\text{Pdt}$中$\sum _{\phi (p_j)\text{=}k}\frac{1}{\left|P\text{∩}{\phi }^{–1}(k)\right|}⟨q_i,p_j⟩$是子集均值，$⟨q_i,p_{q_i}⟩$是全集最大值，后者必然更大
     • 所以$⟨q_i,p_{q_i}^{\ast }⟩\text{=}\sum _{\phi (p_j)\text{=}k}\frac{1}{\left|P\text{∩}{\phi }^{–1}(k)\right|}⟨q_i,p_j⟩\text{≤}⟨q_i,p_{q_i}⟩$

➡️两种相似评分的对比

1. $\text{Chamfer}$相似度：根据定义为$\text{Chamfer}(Q,P)\text{=}\sum _{i\text{=1}}^n⟨q_i,p_{q_i}⟩\text{=}⟨Q,P⟩$
2. $\text{FDE}$相似度：根据定义没经过投影和重复的$\text{FDE}$相似度可写作$\text{FDE}(Q,P)\text{=}\sum _{k\text{=}1}^B⟨{\vec{q}}_{(k)},{\vec{p}}_{(k)}⟩\text{=}\sum _{i\text{=1}}^n⟨q_i,p_{q_i}^{\ast }⟩\text{=}⟨Q,P^{\prime }⟩$
3. 已证了$⟨q_i,p_{q_i}^{\ast }⟩\text{≤}⟨q_i,p_{q_i}⟩$故$\text{FDE}(Q,P)\text{≤}\text{Chamfer}(Q,P)$

$\text{2.2. }$加上一定维度的投影后原上界近似成立

➡️$\text{Muvera}$分桶$\text{+}$投影的过程

1. 同样首先相当于为每个$q_i\text{∈}Q$都映射一个 p ⃗ ( k q i ) = p q i ∗ ∈ { p ⃗ ( 1 ) , . . . , p ⃗ ( B ) } \vec{p}_{(k_{q_i})}\text{=}p_{q_i}^*\text{∈}\{\vec{p}_{(1)},...,\vec{p}_{(B)}\} p ​(kqi​​)​=pqi​∗​∈{p ​(1)​,...,p ​(B)​}，但是后续参与交互(内积)的从原始向量变为了投影向量
2. 所以原有的$\text{FDE}(Q,P)$为直接将内积$⟨q_i,p_{q_i}^{\ast }⟩$累加，现在变成将各自投影后的内积$⟨\psi (q_i),\psi \left(p_{q_i}^{\ast }\right)⟩$累加
   • $\text{FDE}$相似度(无投影)：可写作${\text{FDE}}_{\text{orgn}}(Q,P)\text{=}\sum _{k\text{=}1}^B⟨{\vec{q}}_{(k)},{\vec{p}}_{(k)}⟩\text{=}\sum _{i\text{=1}}^n⟨q_i,p_{q_i}^{\ast }⟩$，并且已证明${\text{FDE}}_{\text{orgn}}(Q,P)\text{≤}\text{Chamfer}(Q,P)$
   • $\text{FDE}$相似度(无投影)：可写作${\text{FDE}}_{\text{proj}}(Q,P)\text{=}\sum _{k\text{=}1}^B⟨\psi \left({\vec{q}}_{(k)}\right),\psi \left({\vec{p}}_{(k)}\right)⟩\text{=}\sum _{i\text{=1}}^n⟨\psi (q_i),\psi \left(p_{q_i}^{\ast }\right)⟩$

➡️事实$\text{A2}$表明了：给定$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \frac{m}{\delta }\right)$则$⟨x,y⟩\text{–}\epsilon \text{≤}⟨\psi (x),\psi (y)⟩\text{≤}⟨x,y⟩\text{+}\epsilon$以$\text{Pr}\text{≥}1\text{–}\delta$概率成立

1. 将$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \frac{m}{\delta }\right)$作为前提引入，代入结论有$\sum _{i\text{=1}}^n⟨q_i,p_{q_i}^{\ast }⟩\text{–}|Q|\epsilon \text{≤}\sum _{i\text{=1}}^n⟨\psi (q_i),\psi \left(p_{q_i}^{\ast }\right)⟩\text{≤}\sum _{i\text{=1}}^n⟨q_i,p_{q_i}^{\ast }⟩\text{+}|Q|\epsilon$
   • 概率调整为，以$\text{Pr}\text{≥}(1\text{–}\delta {)}^n\text{≥}1\text{–}|Q|\delta$概率成立
   • 也可写作${\text{FDE}}_{\text{orgn}}(Q,P)\text{–}|Q|\epsilon \text{≤}{\text{FDE}}_{\text{proj}}(Q,P)\text{≤}{\text{FDE}}_{\text{orgn}}(Q,P)\text{+}|Q|\epsilon$
2. 稍作调整，则有${\text{FDE}}_{\text{proj}}(Q,P)\text{≤}{\text{FDE}}_{\text{orgn}}(Q,P)\text{+}|Q|\epsilon \text{≤}\text{Chamfer}(Q,P)\text{+}|Q|\epsilon$，以$\text{Pr}\text{≥}1\text{–}|Q|\delta$概率成立
3. 再按常数$Q$的比例调整$\delta$(注意$\epsilon$为与后续统一故不调整)，则有${\text{FDE}}_{\text{proj}}(Q,P)\text{≤}\text{Chamfer}(Q,P)\text{+}|Q|\epsilon$，以$\text{Pr}\text{≥}1\text{–}\delta$概率成立

$\text{2.3. }$已给出无重复$\text{FDE}$上界👉还需证明什么才能给出无重复$\text{FDE}$的上下界

➡️不妨假设需要证明的是$\text{Chamfer}(Q,P)\text{–}|Q|\epsilon \text{≤}\text{FDE}(Q,P)\text{≤}\text{Chamfer}(Q,P)\text{+}|Q|\epsilon$以$\text{Pr}\text{≥}1\text{–}\delta$概率成立

1. 令下界成立为事件$F_L/$上界成立为事件$F_U/$上下界都成立为事件$F$，原问题变为要证明$\text{Pr}[F]\text{≥}1\text{–}\delta$
2. 不难得到当$\epsilon \text{≤}\frac{1}{2}$时，同时满足$\text{Pr}[F_L]\text{≥}1\text{–}\epsilon \delta$和$\text{Pr}[F_U]\text{≥}1\text{–}\epsilon \delta$，可推导出$\text{Pr}[F]\text{≥}1\text{–}\delta$
3. 由已证明的上界结论可知设定$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon \delta }\right)\right)$则有$\text{Pr}[F_U]\text{≥}1\text{–}\epsilon \delta$
4. 所以增加前提$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon \delta }\right)\right)$以及$\epsilon \text{≤}\frac{1}{2}$后，原问题变为要证明$\text{Pr}\left[F_L\right]\text{≥}1\text{–}\epsilon \delta$

➡️对$\text{Chamfer}(Q,P)\text{–}|Q|\epsilon \text{≤}\text{FDE}(Q,P)$的进一步变换

1. 根据$\text{Chamfer}$的定义有$\text{Chamfer}(Q,P)\text{=}\sum _{q_i\text{∈}Q}\text{MaxSim}(q_i,P)$
2. 又由于$\text{FDE}$对$q_i$的处理式独立线性的，所以$\text{FDE}(Q,P)\text{=}\sum _{q_i\text{∈}Q}\text{FDE}(q_i,P)$
3. 所以原问题变为需证$\sum _{q_i\text{∈}Q}\left(\text{MaxSim}(q_i,P)\text{–}\epsilon \right)\text{≤}\sum _{q_i\text{∈}Q}\text{FDE}(q_i,P)$，以$\text{Pr}\text{≥}1\text{–}\epsilon \delta$概率成立
4. 去掉求和号后，原问题变为需证$\text{MaxSim}(q_i,P)\text{–}\epsilon \text{≤}\text{FDE}(q_i,P)$，以$\text{Pr}\text{≥}1–\frac{\epsilon \delta }{|Q|}$概率成立

➡️后续称$\text{FDE}(q_i,P)$的上下界为$\text{FDE}$的子上下界

$\text{2.4. }$无投影无重复时$\text{FDE}$相似度的子下界

➡️结合之前的分析，对于$\text{FDE}(q_i,P)\text{=}⟨q_i,p_{q_i}^{\ast }⟩$，在无投影时总存在一个子集$S\text{⊆}P$，使得$p_{q_i}^{\ast }\text{=}\frac{1}{|S|}\sum _{p_j\text{∈}S}{p}_j\text{=}{S}_{\text{center}}$

1. 当单个$q_i$落入的桶属于$\text{Case-0}$情形时，$S$是单个点${\hat{p}}_k\text{=}\arg \underset{p_j\text{∈}P}{\min }\Vert \phi (q_i)–\phi (p_j){\Vert }_0$，也就是离桶编码$\phi (q_i)$海明距离最近的点
2. 当单个$q_i$落入的桶属于$\text{Case-n}$情形时，$S$元素需满足$\phi (q_i)\text{=}\phi (p_j)$，也就是所有落入该桶的$q_j$点

➡️对事实$\text{A4}$给定$k_{\text{sim}}\text{=}O\left(\frac{1}{\epsilon }\log \left(\frac{m}{\delta }\right)\right)$时$\forall p_j\text{∈}P$有$\left|\frac{\Vert \phi (q_i)–\phi (p_j){\Vert }_0}{k_{\mathrm{sim}}}\text{–}\frac{\theta (q_i,p_j)}{\pi }\right|\text{≤}\sqrt{\epsilon }$以$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}$概率成立

1. 对于$q_i$和$p_{q_1}^{\ast }$还有$p_{q_1}$，总是会有$\frac{\Vert \phi (q_i)–\phi (p_{q_1}^{\ast }){\Vert }_0}{k_{\mathrm{sim}}}\text{≤}\frac{\Vert \phi (q_i)–\phi (p_{q_1}){\Vert }_0}{k_{\mathrm{sim}}}$
   • 对于$\text{Case-0}$情形，$p_{q_i}^{\ast }$为离编号为$\phi (q_i)$的桶海明距离最近的$p_j$向量，所以$\Vert \phi (q_i)–\phi (p_{q_i}^{\ast }){\Vert }_0\text{≤}\Vert \phi (q_i)–\phi (p_{q_i}){\Vert }_0$
   • 对于$\text{Case-n}$情形，$p_{q_i}^{\ast }$为与$q_i$同桶的所有$p_j$向量的质心，即 S = { p j ∈ P ∣ φ ( q i ) = φ ( p j ) } S\text{=}\left\{p_j\text{∈}P|{\varphi}(q_i)\text{=}\varphi(p_j)\right\} S={pj​∈P∣φ(qi​)=φ(pj​)}的质心$S_{\text{center}}$
     • 回忆$\text{SimHash}$分桶的本质，就是用$k_{\text{sim}}$个法平面将空间切割为$2^{k_{\text{sim}}}$个子空间
     • 所有$p_j\text{∈}S$都落入同一桶即在同一子空间，则其质心$p_{q_i}^{\ast }\text{=}{S}_{\text{center}}$也一定在该子空间中，所以$\phi (q_i)\text{=}\phi (p_j)\text{=}\phi (p_{q_i}^{\ast })$
     • 所以$\Vert \phi (q_i)–\phi (p_{q_i}^{\ast }){\Vert }_0\text{=}0\text{≤}\Vert \phi (q_i)–\phi (p_{q_i}){\Vert }_0$
2. $p_{q_1}$和$p_{q_1}^{\ast }$都代入事实$\text{A4}$，则$\frac{\theta (q_i,p_{q_1}^{\ast })}{\pi }–\sqrt{\epsilon }\text{≤}\frac{\Vert \phi (q_i)–\phi (p_{q_1}^{\ast }){\Vert }_0}{k_{\mathrm{sim}}}\text{≤}\frac{\Vert \phi (q_i)–\phi (p_{q_i}){\Vert }_0}{k_{\mathrm{sim}}}\text{≤}\frac{\theta (q_i,p_{q_i})}{\pi }\text{+}\sqrt{\epsilon }$以$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}$概率成立
   • 因此$\left|\theta (q_i,p_{q_1}^{\ast })–\theta (q_i,p_{q_i})\right|\text{=}O\left(\sqrt{\epsilon }\right)$以$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}$概率成立
   • 上式可得$\left|\cos \theta (q_i,p_{q_1}^{\ast })–\cos \theta (q_i,p_{q_i})\right|\text{<}O(\epsilon )$以$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}$成立，其中$\{\begin{array}{l}\cos \theta (q_i,p_{q_1}^{\ast })\text{=}⟨q_i,p_{q_1}^{\ast }⟩\text{=}\text{FDE}(q_i,P)\\ \\ \cos \theta (q_i,p_{q_i})\text{=}⟨q_i,p_{q_i}⟩\text{=}\text{MaxSim}(q_i,P)\end{array}$
   • 所以$\text{MaxSim}(q_i,P)–O(\epsilon )\text{≤}\text{FDE}(q_i,P)\text{≤}\text{MaxSim}(q_i,P)\text{+}O(\epsilon )$ 以$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}$概率成立

➡️事实$\text{A4}$给出了$\text{FDE}(q_i,P)$的子上下界

1. 取结论的左半边$\text{MaxSim}(q_i,P)–O(\epsilon )\text{≤}\text{FDE}(q_i,P)$并给概率放水$\text{Pr}\text{＞}1–\frac{\epsilon \delta }{m^2}\text{>}1–\frac{\epsilon \delta }{|Q|}$，便得到了一个更弱的结论
2. 再对$O(\epsilon )$进行常数缩放为$\epsilon$，该更弱的结论就变成了所要证的$\text{FDE}$相似度的子下界

$\text{2.5. }$加上一定维度的投影后原子下界近似成立

➡️投影前后的对比：用${\text{FDE}}_{\text{orgn}}$和${\text{FDE}}_{\text{proj}}$表示区分

1. 投影前为${\text{FDE}}_{\text{orgn}}(q_i,P)\text{=}⟨q_i,p_{q_i}^{\ast }⟩\text{=}⟨q_i,\frac{1}{|S|}\sum _{p_j\text{∈}S}{p}_j⟩\text{=}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨q_i,p_j⟩$
2. 投影后为${\text{FDE}}_{\text{proj}}(q_i,P)\text{=}⟨\psi (q_i),\psi \left(p_{q_i}^{\ast }\right)⟩\text{=}⟨\psi (q_i),\psi \left(\frac{1}{|S|}\sum _{p_j\text{∈}S}{p}_j\right)⟩\text{=}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨\psi (q_i),\psi \left(p_j\right)⟩$

➡️应用事实$\text{A2}$：用$\frac{\epsilon \delta }{|Q|}$替代$\delta$以设定$d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{|Q|}{\epsilon \delta }\right)\right)\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon \delta }\right)\right)$

1. 则有内积的偏差$⟨x,y⟩\text{–}\epsilon \text{≤}⟨\psi (x),\psi (y)⟩\text{≤}⟨x,y⟩\text{+}\epsilon$以$\text{Pr}\text{≥}1\text{–}\frac{\epsilon \delta }{|Q|}$概率成立概率成立
2. 将事实$\text{A2}$代回则有$\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨q_i,p_j⟩\text{–}\epsilon \text{≤}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨\psi (q_i),\psi p_j⟩\text{≤}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨q_i,p_j⟩\text{+}\epsilon$，以$\text{Pr}\text{≥}1\text{–}\frac{\epsilon \delta }{|Q|}$概率成立概率成立
   • 其中${\text{FDE}}_{\text{orgn}}(q_i,P)\text{=}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨q_i,p_j⟩$，以及${\text{FDE}}_{\text{proj}}(q_i,P)\text{=}\frac{1}{|S|}\sum _{p_j\text{∈}S}⟨\psi (q_i),\psi \left(p_j\right)⟩$
   • 所以${\text{FDE}}_{\text{orgn}}(q_i,P)\text{–}\epsilon \text{≤}{\text{FDE}}_{\text{proj}}(q_i,P)\text{≤}{\text{FDE}}_{\text{orgn}}(q_i,P)\text{+}\epsilon$，以$\text{Pr}\text{≥}1\text{–}\frac{\epsilon \delta }{|Q|}$概率成立概率成立
3. 已证$\text{MaxSim}(q_i,P)–O(\epsilon )\text{≤}{\text{FDE}}_{\text{proj}}(q_i,P)\text{≤}\text{MaxSim}(q_i,P)\text{+}O(\epsilon )$以$\text{Pr}\text{≥}1–\frac{\epsilon \delta }{|Q|}$概率成立
   • 代入得${\text{FDE}}_{\text{proj}}(q_i,P)\text{≥}{\text{FDE}}_{\text{orgn}}(q_i,P)\text{–}\epsilon \text{≥}\text{MaxSim}(q_i)\text{–}\epsilon –O(\epsilon )$
   • 对$\epsilon$进行常数因子缩放后，即证毕

$\text{3. }$定理$\text{2.2}$证明的思路

$\text{3.0. }$定理$\text{2.2}$的主要内容

👉条件$1$：给定单个查询$Q$以及多个段落 P = { P 1 , … , P n } P\text{=}\left\{P_{1},\ldots,P_{n}\right\} P={P1​,…,Pn​}并且$Q,\forall P_i\text{⊆}{\mathbb{R}}^d$，并令$m\text{=}|Q|\text{+}\underset{i\text{∈}[n]}{\max }\left|P_i\right|$

👉条件$2$：给定$\forall \epsilon \text{>}0$，设置参数$k_{\text{sim}}\text{=}O\left(\frac{\log m}{\epsilon }\right),d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon }\right)\right),R_{\text{reps}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log n\right)$

👉条件$3$：令$i^{\ast }\text{=}\arg \underset{i\text{∈}[n]}{\max }\text{FDE}(Q,P_i)$，即$P_{i^{\ast }}$是通过$\text{Muvera}$方法找到的，与查询$Q$最相似的段落

👉结论$1$：$\frac{1}{|Q|}\text{Chamfer}\left(Q,P_{i^{\ast }}\right)\text{≥}\underset{i\text{∈}[n]}{\max }\frac{1}{|Q|}\text{Chamfer}\left(Q,P_i\right)–\epsilon$以$\text{Pr=}1\text{–}\frac{1}{\text{poly}(n)}$概率成立

$\text{3.1. }$定理$\text{2.2}$的主要内容

➡️在考虑重复$R_{\text{reps}}$次的情况下，对于每个重复$k\text{∈}\left[R_{\text{reps}}\right]$，设定每次重复对最终相似度的贡献为${\text{FDE}}^k(Q,P_{\alpha })$

1. 对于最终相似度，有$\text{FDE}(Q,P_{\alpha })\text{=}\sum _{k\text{=}1}^{R_{\text{reps}}}{\text{FDE}}^k(Q,P_{\alpha })$，不妨设定随机变量$X_k\text{=}\frac{1}{|Q|}{\text{FDE}}^k(Q,P_{\alpha })$

➡️最关键的一步在于，对$X_k$尝试运用$\text{Chernoff}$界限，即$\forall X_i\text{∈}[a,b]$有$\text{Pr}\left[\left|\frac{1}{R}\sum _{i=1}^R{X}_i–\mu \right|\text{≥}\epsilon \right]\text{≤}2e^{\left(–\frac{2R{\epsilon }^2}{(b–a{)}^2}\right)}$

1. 对$\text{Chernoff}$界限中参数的确定
   • 将上式中$R$视作$R_{\text{reps}}$，并将$R_{\text{reps}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log n\right)$作为前提引入
   • 对于$\mu$即均值，根据定理$\text{2.1}$引入前提$k_{\text{sim}}\text{=}O\left(\frac{\log m}{\epsilon }\right),d_{\text{proj}}\text{=}O\left(\frac{1}{{\epsilon }^2}\log \left(\frac{m}{\epsilon }\right)\right)$后，有$\mathbb{E}[X_k]\text{∈}\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha })\text{±}\epsilon$
   • 对于$[a,b]$即$X_k$的范围，不难得到$X_k\text{∈}[–m,m]$
2. 将以上参数套用到$\text{Chernoff}$界限则有
   • 概率：以$\text{Pr}\text{≥}1–2e^{\left(–\frac{R_{\text{reps}}{\epsilon }^2}{2m^2}\right)}$概率成立，可以进一步转化为$\text{Pr}\text{≥}1–2e^{\left(–\frac{R_{\text{reps}}{\epsilon }^2}{2m^2}\right)}\text{≥}1–\frac{2}{n^C}\text{=}1\text{–}\frac{1}{\text{poly}(n)}$
   • 事件：$\left|\sum _{k\text{=}1}^{R_{\text{reps}}}\frac{X_k}{R_{\text{reps}}}–\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha })\right|\text{≤}2\epsilon$
     • 代入$\text{FED}$最相似文档$P_{{\alpha }^{\ast }}$后，有$\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha }^{\ast })\text{≥}\frac{1}{|Q|R_{\text{reps}}}\text{FDE}(Q,P_{\alpha }^{\ast })–2\epsilon \text{=}\underset{\alpha \text{∈}[n]}{\max }\frac{1}{|Q|R_{\text{reps}}}\text{FDE}(Q,P_{\alpha })–2\epsilon$
     • 根据定理$\text{2.1}$又可以知道$\underset{\alpha \text{∈}[n]}{\max }\frac{1}{|Q|R_{\text{reps}}}\text{FDE}(Q,P_{\alpha })\text{≥}\underset{\alpha \text{∈}[n]}{\max }\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha })\text{–}\epsilon$
     • 所以最终原事件可转化为$\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha }^{\ast })\text{≥}\underset{\alpha \text{∈}[n]}{\max }\frac{1}{|Q|}\text{Chamfer}(Q,P_{\alpha })\text{–}3\epsilon$，对$\epsilon$做常数倍变换即证毕