von Mises-Fisher distribution.
1. vMF分布
von Mises-Fisher (vMF)分布是定义在$d$维空间中$d-1$维超球面上的概率分布。定义样本空间$S^{d-1}={x|x\in \Bbb{R}^d,||x||=1}$，则vMF分布的概率密度函数为：
\[p(x) = \frac{e^{<\xi,x>}}{Z_{d,||\xi||}}, \quad Z_{d,||\xi||}=\int_{S^{d-1}} e^{<\xi,x>} d S^{d-1}\]其中$\xi$是预先给定的参数向量，$<\xi,x>$为内积操作，$Z_{d,||\xi||}$为归一化因子。上式表示该分布是在超球面$S^{d-1}$上以$\xi$为中心的分布。若记$\mu=\frac{\xi}{||\xi||}$，$\kappa=||\xi||$，$C_{d,\kappa} = \frac{1}{Z_{d,||\xi||}}$，则vMF分布也可表示为：
\[p(x) = C_{d,\kappa} e^{\kappa <\mu,x>}\]由于$\mu$和$x$是单位向量，则$<\mu,x>$为$\mu$和$x$的夹角余弦，因此vMF分布是一种以余弦相似度为度量指标的分布。在一些使用余弦相似度的应用中(如自然语言处理中的句子重构)，使用vMF分布是更加自然合理的假设。
$\kappa$为凝聚度(concentration)，$\kappa$越大则分布越集中在$\mu$附近；$\kappa$越小则分布越分散，当$\kappa=0$时，vMF分布退化为球面上的均匀分布。
归一化因子$Z_{d,||\xi||}$实际上是vMF分布的母函数，可以用来表示分布的各阶矩。比如vMF分布的一阶矩：
\[\begin{aligned} \Bbb{E}_{p(x)}[x] &= \int_{S^{d-1}} xp(x) dS^{d-1} = \int_{S^{d-1}} x\frac{e^{<\xi,x>}}{Z_{d,||\xi||}} dS^{d-1} = \frac{\nabla_{\xi} Z_{d,||\xi||}}{Z_{d,||\xi||}} \\ &= \nabla_{\xi} \log Z_{d,||\xi||} = \nabla_{||\xi||} \log Z_{d,||\xi||} \cdot \nabla_{\xi} ||\xi|| = \nabla_{||\xi||} \log Z_{d,||\xi||} \cdot\frac{\xi}{||\xi||} \end{aligned}\]由上式可知vMF分布的一阶矩与$\xi$方向相同。
2. vMF分布的采样
⚪ 特殊情况1：$\kappa=0$
当$\kappa=0$时，vMF分布退化为$d-1$维超球面上的均匀分布。对球面上的均匀分布进行采样可以通过标准正态分布实现。由于标准正态分布是各向同性的，其概率密度$\frac{1}{\sqrt{2\pi}}e^{-\frac{||x||^2}{2}}$仅与模长$||x||$有关，因此从$d$维标准正态分布中采样$z$，则$x=\frac{z}{||z||}$即为$d-1$维超球面上的均匀采样结果。
⚪ 特殊情况2：$\mu=[1,0,\cdots,0]$
当$\kappa>0$时，考虑特殊情况$\mu=[1,0,\cdots,0]$。此时对于单位向量$x=[x_1,x_2,\cdots x_d]$，概率密度计算为：
\[p(x) = C_{d,\kappa} e^{\kappa <\mu,x>}= C_{d,\kappa} e^{\kappa x_1}\]此时概率密度正比于$\kappa x_1$，转换为球坐标系：
\[\begin{aligned} x_1&=\cos \phi_1 \\ x_2 &= \sin \phi_1 \cos \phi_2 \\ x_3 &= \sin \phi_1 \sin \phi_2 \cos \phi_3 \\ &\cdots \\ x_{d-1} &= \sin \phi_1 \cdots \sin \phi_{d-2} \cos \phi_{d-1} \\ x_{d} &= \sin \phi_1 \cdots \sin \phi_{d-2} \sin \phi_{d-1} \end{aligned}\]超球坐标的积分变换：
\[\begin{aligned} e^{\kappa x_1} d S^{d-1} &= e^{\kappa \cos \phi_1 } \sin^{d-2} \phi_1 \sin^{d-3} \phi_2 \cdots \sin \phi_{d-2} d \phi_1 d \phi_2 \cdots d \phi_{d-1} \\ &= (e^{\kappa \cos \phi_1 } \sin^{d-2} \phi_1 d \phi_1) (\sin^{d-3} \phi_2 \cdots \sin \phi_{d-2} d \phi_2 \cdots d \phi_{d-1}) \\ &= (e^{\kappa \cos \phi_1 } \sin^{d-2} \phi_1 d \phi_1) d S^{d-2} \end{aligned}\]该分解表明从vMF分布中采样$x$等价于先从概率密度正比于$e^{\kappa \cos \phi_1 } \sin^{d-2} \phi_1 d \phi_1$的分布中采样$\phi_1$，然后从$d-2$维超球面上均匀采样一个$d-1$维向量$\epsilon=[\epsilon_2,\epsilon_3,\cdots \epsilon_d]$，并组合成采样结果：
\[x = [\cos \phi_1, \epsilon_2 \sin \phi_1, \epsilon_3 \sin \phi_1, \cdots, \epsilon_d \sin \phi_1]\]设$w=\cos \phi_1 \in [-1,1]$，有：
\[|e^{\kappa \cos \phi_1 } \sin^{d-2} \phi_1 d \phi_1| = |e^{\kappa w}(1-w^2)^{\frac{d-3}{2}}dw|\]因此问题转化为从概率密度正比于$e^{\kappa w}(1-w^2)^{\frac{d-3}{2}}$的分布中采样$w$。对于任意一维分布$p(w)$，设其累积概率函数为$\Phi(w)$，则$w=\Phi^{-1}(\epsilon),\epsilon\text{~}U[0,1]$是一种通用的采样方案。在实践中可以通过数值计算实现：
import numpy as np
def sample_from_pw(batch, kappa, dims, epsilon=1e-7):
w = np.arange(-1+epsilon, 1, epsilon)
logp = kappa*w + np.log(1-w**2)*(dims-3)/2
p = np.cumsum(np.exp(logp-logp.max())) # 计算累积概率
p = p / p[-1] # 归一化累积概率
return np.interp(np.random.random(batch), p, w) # 使用线性插值模拟反函数
注意到在计算概率$e^{\kappa w}(1-w^2)^{\frac{d-3}{2}}$时先计算对数值，减去最大值后再计算指数值，从而防止数值溢出。
由上述讨论可以看出，从$\mu=[1,0,\cdots,0]$的vMF分布中采样$x$等价于从概率密度正比于$e^{\kappa w}(1-w^2)^{\frac{d-3}{2}}$的分布中采样$w$，从$d-2$维超球面上均匀采样一个$d-1$维向量$\epsilon=[\epsilon_2,\epsilon_3,\cdots \epsilon_d]$，并组合成采样结果：
\[\begin{aligned} x&=w \times [1,0,0,\cdots,0] + \sqrt{1-w^2}\times [0, \epsilon_2,\epsilon_3,\cdots \epsilon_d] \\ &= [w, \epsilon_2 \sqrt{1-w^2}, \epsilon_3 \sqrt{1-w^2}, \cdots, \epsilon_d \sqrt{1-w^2}] \end{aligned}\]⚪ 一般情况
由于vMF分布是各向同性的，对于一般的$\mu$，采样结果也具有类似上面的形式。
从具有任意$\mu$的vMF分布中采样$x$等价于从概率密度正比于$e^{\kappa w}(1-w^2)^{\frac{d-3}{2}}$的分布中采样$w$，从与$\mu$正交的$d-2$维超球面上均匀采样一个$d-1$维向量$\nu$，并组合成采样结果：
\[x=w \mu + \sqrt{1-w^2}\nu\]在采样时应保证$\nu$与$\mu$是正交的。在实现时先从$d$维标准正态分布中采样$z$，然后保留与$\mu$正交的分离并归一化即可：
\[\nu = \frac{z-<z,\mu>\mu}{||z-<z,\mu>\mu||}, \quad z \text{~} \mathcal{N}(0,I_d)\]
