Hyperbolic Representation Learning for CV_hyperbolic image embeddings

Hyperbolic geometry

• blog: Hyperbolic geometry (双曲几何简介)

[CVPR 2020] Hyperbolic visual embedding learning for zero-shot recognition

• Liu, Shaoteng, et al. “Hyperbolic visual embedding learning for zero-shot recognition.” Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2020.
• code: https://github.com/ShaoTengLiu/Hyperbolic_ZSL

Introduction

• A robust ZSL system should have the ability to output a correct but less fine-grained label. 大型数据集的类别通常具有标签层次结构，例如 ImageNet 的类别服从 WordNet hierarchy. 对于标签层次树上的一些细粒度类别，有监督学习都很难加以区分，Zero-Shot Learning (ZSL) 更是难上加难。作者认为，当 ZSL 模型难以将样本分类为叶结点细粒度类别时，给出一个正确的粗粒度类别比给出一个错误的细粒度类别要更具实用性
  
• 为了引入层次结构信息，作者首次提出在非欧空间中进行 ZSL，这使得模型能够做出更加鲁棒的预测
  

Approach

Hyperbolic Label Embedding Learning

• Hyperbolic Label Embedding Learning 用于将 image labels $\mathcal{C}$ 嵌入到双曲空间 $\mathcal{H}$，其中 Poincaré Embedding $p_c$ 基于 WordNet hierarchy 学得 hyperbolic word embeddings (100-dimensional vector trained on the transitive closure of the WordNet Noun hierarchy)，用于编码类别间的 hierarchical information，Poincaré Glove $q_c$ 在 Poincaré ball 中训练 GloVe 模型得到能反映类间语义关系的 word embed (100-dimensional vector for each image class based on the En-glish Wikipedia dump). hierarchy 信息可以看作 explicit knowledge，semantic 信息可以看作 implicit knowledge，在 ZSL 领域，已经有研究表明结合 explicit 和 implicit knowledge 可以有效提高模型性能
  • 例如，对于类别为 Red Squirrel 的样本，仅基于 Poincaré Embedding 的模型 top-5 prediction 为 “Red Squirrel”, “Tree Squirrel”, “Squirrel”, “Tree Wallaby”, and “Kangaroo”，更倾向于预测 general labels；而仅基于 Poincaré Glove 的模型 top-5 prediction 为 “Red Squirrel”, “Kangaroo”, “Tree Wallaby”, “Tree Squirrel”, and “Lemur”，更倾向于预测 similar and specific labels (e.g., “Kangaroo”)
• Final class embedding 为 Poincaré Embedding 和 Poincaré Glove 的连接 $[p_c;q_c]$. 此外，为了确保连接后的 embed 依然在 Poincaré ball 上 (norm < 1)，作者使用了指数变换来得到双曲空间中最接近连接向量的 embed
  

Hyperbolic Image Embedding Learning

• 首先用 ResNet 抽取出 2048 维的图像特征得到 Image feature $v_{\mathcal{I}}$，然后使用指数变换将欧氏空间中的图像特征变换到双曲空间得到 Projected image feature ${\tilde{v}}_{\mathcal{I}}$
  $${\tilde{v}}_{\mathcal{I}}={\exp }_0(v_{\mathcal{I}})$$接着用 Möbius Transformation $f^{\otimes }(x)={\exp }_0\left(f\left({\log }_0(x)\right)\right)$ 对双曲空间中的特征进行非线性变换，以便与 label embeddings 进行对齐 (将 projected image feature 变换到与 label embed 同一维数)。具体来说，作者采用了两层的 hyperbolic FFN，其中 Möbius matrix-vector multiplication 如下：
  双曲空间中与经过变换后的 Transformed image feature 距离最近的 label embed 即为模型预测的标签。双曲空间内的距离公式如下：
  
• Model Training. 损失函数为 Rank loss. 给定三元组 $<h_{\mathcal{I}},t_{C_{\mathcal{I}}},t_{C_{\mathcal{I}}}^{-}>$，其中 $t_{C_{\mathcal{I}}}$ 为 image embedding $h_{\mathcal{I}}$ 对应的 label embedding，$t_{C_{\mathcal{I}}}^{-}$ 为随机采样的负类标签，rank loss 的目标是进行 image embed 和 label embed 的对齐：
  其中 margin $\delta \in (0,+\infty )$. 在优化时，训练 Poincaré Glove 采用 RADAGRAD 优化器，训练 Poincaré embedding 和 Möbius feature transformation 采用 Riemannian stochastic gradient descent (RSGD) (For Poincaré embedding, RADAGRAD is not suitable as it requires the hyperbolic space to be a product of Riemannian manifolds.)

Experiment

• Datasets. 数据集为 ImageNet. 1,000 known classes 来自于 ImageNet 2012 1K. Unseen classes 来自于 ImageNet 的其他类别，基于 WordNet hierarchy，类别根据到 1K known concepts 的距离被划分为 “2-hops” (1,589 classes), “3-hops” (7,860 classes) 和 “All” (20,841 classes) 3 个数据集。在评估时，Zero-Shot Learning (ZSL) 表示只在 unseen classes 上评估模型性能，Generalized Zero-Shot Learning (GZSL) 表示在所有类别上评估模型性能，包括 3 个数据集 “2-hops + 1K”, “3-hops + 1K”, and “All + 1K”
• Hierarchical Evaluation. ZSL 常用的评价指标为 Top-k Hit Ratio (Hit@k)，即 Top-k Acc. 为了反映模型预测的鲁棒性，假设样本 GT 类别为 $c$ (e.g., red squirrel)，作者将 $c$ 的 immediate parent class (e.g., tree squirrel) 也作为 GT 类别，然后计算 Hit@k
  
• Performance Comparison. 在 3 hops 和 All 测试集上，作者提出的方法性能都要优于 DGP (注意到，其他两个比较强的 baseline GCNZ 和 DGP 都是通过 GNN 来引入 class hierarchy 信息，也都将 explicit 和 implicit knowledge 进行了结合)
  
• Ablation Study.
  
• Dimension Analysis.
  

[CVPR 2020] Hyperbolic Image Embeddings

• Khrulkov, Valentin, et al. “Hyperbolic image embeddings.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.
• code: https://github.com/leymir/hyperbolic-image-embeddings

Introduction

• 作者想要证明，在很多视觉的实际应用场景下，Hyperbolic image embeddings 能够很好地替代 Euclidean image embeddings 和 Spherical image embeddings. 如下图所示，在很多视觉任务中，图像间都具有层次关系，因此在双曲空间中学习 embed 是比较合理的选择
  
• 为了进一步验证上述观点，作者将 hyperbolic neural networks 用在了多个视觉任务上，包括 image classification, one-shot, few-shot learning 以及 person re-identification. 实验证明 hyperbolic embed 在很多场景下都能提升 Euclidean or spherical embed 的性能。此外，作者还提出可以基于 Gromov $\delta$-hyperbolicity 来衡量数据集的 hyperbolicity，并且还可以估计给定数据集 embed 对应的 Poincarré disk 半径

$\delta$-Hyperbolicity

$\delta$-Hyperbolicity

• 对于任意 metric space $X$，$\delta$-Hyperbolicity 可以衡量 $X$ 和 hyperbolic space 的相近程度，$\delta$ 越小越相近
• 假设 metric space $X$ 的 distance function 为 $d$，则 $x,y,p\in X$ 的 Gromov product 为
  $$(x,y{)}_p=\frac{1}{2}(d(p,x)+d(p,y)-d(x,y))$$对任意 $x,y,z,p\in X$，$\delta$ 被定义为使下式恒成立的最小值
  $$(x,z{)}_p\ge \min \left((x,y{)}_p,(y,z{)}_p\right)-\delta$$树可以看作 discrete metric space，距离度量采样结点间的最短路径长度。如上图所示，对于树而言 $\delta =0$，tree endowed with a natural shortest path metric 为 0-Hyperbolic space，Hyperbolic space 可以看作是连续的树。The definition of hyperbolic space in terms of the Gromov product can be seen as saying that the metric relations between any four points are the same as they would be in a tree, up to the additive constant $\delta$. $\delta$-Hyperbolicity captures the basic common features of “negatively curved” spaces like the classical real-hyperbolic space ${\mathbb{D}}^n$ and of discrete spaces like trees.
• 在实际计算中，我们可以固定设置 $p=p_0$，此时有
  $$\delta \ge \min \left((x,y{)}_{p_0},(y,z{)}_{p_0}\right)-(x,z{)}_{p_0}$$我们可以用矩阵 $A$ 表示所有点之间的 Gromov products，i.e. $A_{ij}=(i,j{)}_{p_0}$. $\delta$ 即为矩阵 $(A\otimes A)-A$ 中的最大值，$\otimes$ 为 min-max matrix product
  当样本数过大难以计算 $A$ 时，我们可以随机采样 $N$ 个点计算两两之间的 Gromov products 作为 $A$ 的近似
• 此外，为了得到一个标准化的 $\delta$ 值，作者采用了 scale-invariant metric ${\delta }_{rel}(X)$
  $${\delta }_{rel}(X)=\frac{2\delta (X)}{\mathrm{diam}(X)}\in [0,1]$$其中 $\mathrm{diam}(X)$ 为数据集直径 (maximal pairwise distance). 作者给出了一些常见空间的理论 ${\delta }_{rel}$ 值以及估算出的 ${\delta }_{rel}$ 值
  此外，作者还计算了一些常见图像数据集的 ${\delta }_{rel}$ 值，图像间的距离采用在 ImageNet 上预训练的 CNN 得到的 features 间的距离，包括 Inception v3、ResNet34 和 VGG19，采样的样本数为 1000. 可以看到图像数据集的 degree of hyperbolicity 还是相当高的 (${\delta }_{rel}$ are significantly closer to 0 than to 1)
  

---

Relation between $\delta$-hyperbolicity and Poincaré disk radius

• 标准 Poincaré ball 为 $\delta$-hyperbolic with ${\delta }_P=\log (1+\sqrt{2})\approx 0.88$ (c.f. Hyperbolic word embeddings section 8 and appendix B). 由于 Poincaré ball 的直径无限大，因此 ${\delta }_{rel}=0$. 但从计算的角度看，样本不可能无限靠近边界，也就是说直径是有限的，此时我们可以计算出 effective ${\delta }_{rel}$
• 设 clipping value 为 $10^{-5}$ (Euclidean norm 不超过 $1-10^{-5}$)，则对应的 Poincaré ball 直径约为 12.204，由此计算得到的 effective ${\delta }_{rel}$ 约为 0.144. 假设数据集 $X$ 的 ${\delta }_{rel}$ 为 ${\delta }_X$，利用这个值可以估算出合适的 Poincaré ball radius $c(X)$ ($c=1$ 对应 Poincaré ball，$c\to 0$ 对应欧氏空间)
  对于上述图像数据集，$c$ 值约为 0.33 (sometimes adjusting this value (e.g., to 0.05) provides better results, probably because the image representations computed by deep CNNs pretrained on ImageNet may not have been entirely accurate.)

Hyperbolic operations

• 作者通过对欧式模型的输出使用指数变换将其从欧氏空间变换到双曲空间来学习 hyperbolic image embed，然后使用 hyperbolic neural netowrks 中提出的双曲空间中的运算操作。 这类似于对模型的输出归一化使其从欧氏空间变换到球体上，因此这种方法能和现有的欧式 backbone 很好地兼容
• 由于使用 ${\exp }_0$ 来实现从欧氏空间到双曲空间的近似，原点 $0$ 就变得比较特殊了，欧式模型的输出最好集中在原点附近 (e.g., in the unit ball)，而目前的欧式模型完全可以满足这一要求。另外，在双曲空间中训练 embed 会使得 image embed 将更抽象的样本放在靠近原点的地方，而更加具体的样本将被放在靠近边界的地方，因此在图像分类中，hyperbolic embed 距离原点的距离可以反映模型的 confidence
• Numerical stability. 为了保证训练过程中的数值稳定性，作者在指数变换后进行了 clip by norm，使得 norm 不超过 $\frac{1}{\sqrt{c}}(1-10^{-3})$

---

Hyperbolic averaging

• 求向量均值在双曲空间内的推广被称为 Einstein midpoint，这可以借助 Klein model of hyperbolic space 完成，
  其中 $\mathbf{x}$ 为 Klein coordinates，${\gamma }_i=\frac{1}{\sqrt{1-c\Vert {\mathbf{x}}_i{\Vert }^2}}$ 为 Lorentz factors
• Klein model 与 Poincaré model 类似，也是定义在单位球体内 K n = { x ∈ R n : ∥ x ∥ < 1 } \mathbb K^n=\{x\in\R^n:\|\mathbf x\|<1\} Kn={x∈Rn:∥x∥<1}，但 metric tensor 不一样。令 ${\mathbf{x}}_{\mathbb{D}}$ 和 ${\mathbf{x}}_{\mathbb{K}}$ 分别表示同一个点在 Poincaré 和 Klein 模型中的坐标，它们之间的坐标转换公式为
  因此在计算 Hyperbolic averaging 时，我们只需先将 Poincaré 坐标转换为 Klein 坐标后求加权均值，再将得到的均值坐标转换回 Poincaré 坐标

Experiments

Distance to the origin as the measure of uncertainty

• 作者在 MNIST 上训练 CNN 作为图像分类器，最后一个隐藏层的输出使用指数变换映射到 Poincaré ball，最后接 hyperbolic multi-linear regression (MLR) layer 进行图像分类。在训练精度达到 99% 后，作者在 Omniglot 上进行推理，得到的 MNIST 和 Omniglot embeddings 如下图所示 (2 维 Poincaré embed)，可以看到 MNIST 中不清晰和模糊的图像以及 Omniglot 中的大部分图像都在原点附近
  
• 下图给出了 MNIST 和 Omniglot 数据集中样本到原点的 hyperbolic distance 的分布 ($n$ 为 embed 维数). 可以看出，大部分 Omniglot 样本到原点的距离都相对较近，可以被判断为 out-of-domain
  作者还计算了不同维数下 MNIST 和 Omniglot 数据集中样本到原点距离分布间的距离 $d_{\mathcal{D}}(\mathbf{x},0)$. 此外，作者还在 MNIST 上训练了普通的欧式模型然后在 Omniglot 上进行推理，并计算了 MNIST 和 Omniglot 数据集中样本置信度分布间的距离 (i.e., maximum class probability predicted by the network). 分布间的距离计算采用 Kolmogorov-Smirnov distances，结果如下。可以看出，在 3 个维数下，Distance to the origin 都比欧式模型输出的样本置信度更能反映出 dataset dissimilarity
  

Few-shot classification

• 作者基于 Prototypical networks (ProtoNets) 构建模型。ProtoNets 将某一类的 embedded support set 均值作为该类别的 prototype representation. 为了将该模型扩展到双曲空间，作者将 Euclidean mean operation 替换为了 HypAve 得到 Hyperbolic ProtoNet. 实验结果表明，Hyperbolic ProtoNet 性能不仅超过了 ProtoNet，还达到了 SOTA
  

Person re-identification

• 可以看到，维数越小，双曲模型的优势就越大
  

[CVPR 2020] Searching for Actions on the Hyperbole

• Long, Teng, et al. “Searching for actions on the hyperbole.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.
• code: https://github.com/Tenglon/hyperbolic_action

Introduction

• Action search 是指通过动作名或示例视频来检索相应的动作视频。这一检索问题可以被当作分类问题进行解决，即根据动作视频对应各个动作的分类得分进行排序得到检索结果；也可以直接将动作视频和 embedded action names 或 query video 进行对齐。然而，作者认为现有工作忽略了动作之间存在的层级结构
• 为此，作者在 action search 中加入了动作的层级结构，将 action hierarchies 和 videos 映射到同一个双曲空间，projected actions 可以当作 hyperbolic prototypes，然后通过 matching function 将 projected videos 与 prototypes 进行匹配，以此来进行 hierarchical action search by name and video example
  

Hyperbolic action network

Hyperbolic action embedding

• 令 A = { 1 , 2 , . . . , ∣ A ∣ } \mathcal A=\{1,2,...,|\mathcal A|\} A={1,2,...,∣A∣} 为动作类别集合，它们的上位词组成的类别集合为 H = { ∣ A ∣ + 1 , ∣ A ∣ + 2 , . . . , ∣ A ∣ + ∣ H ∣ } \mathcal H=\{|\mathcal A|+1,|\mathcal A|+2,...,|\mathcal A|+|\mathcal H|\} H={∣A∣+1,∣A∣+2,...,∣A∣+∣H∣}. $|\mathcal{A}|\cup |\mathcal{H}|$ 组成了类别层次树 P = { p 1 , p 2 , . . . , p ∣ A ∣ + ∣ H ∣ } \mathbf P=\{\mathbf{p_1},\mathbf{p_2},...,\mathbf{p_{|\mathcal A|+|\mathcal H|}}\} P={p1​,p2​,...,p∣A∣+∣H∣​}
• 令 $\mathcal{P}=\{(\mathbf{u},\mathbf{v})|\mathbf{u}=h(\mathbf{v})\}$ 为上位词正样本对，其中 $h(\mathbf{v})$ 为 $\mathbf{v}$ 的上位词；$\mathcal{N}=\{({\mathbf{u}}^{\prime },{\mathbf{v}}^{\prime })|{\mathbf{u}}^{\prime }=h({\mathbf{v}}^{\prime })\}$ 为上位词负样本对，作者采用了和 Poincaré embeddings 论文中类似的损失函数
  此外，作者还采用如下损失函数用于将所有非上位词动作类别对应的 prototypes 分开
  其中 P ˉ = { p 1 , p 2 , . . . , p ∣ A ∣ } \bar{\mathbf P}=\{\mathbf{p_1},\mathbf{p_2},...,\mathbf{p_{|\mathcal A|}}\} Pˉ={p1​,p2​,...,p∣A∣​} 为非上位词动作类别对应的 prototypes，$\hat{\mathbf{P}}$ 为 vector-wise ${\ell }_2$-normalization of $\bar{\mathbf{P}}$. 注意到，虽然 prototypes 位于双曲空间，但这项损失函数还是用欧氏空间的余弦相似度去作为 prototypes 间的距离度量，从直观上看就是让非上位词动作类别对应的 prototypes 均匀分布在 Poincaré ball 的四周 (The main reason for this is that in search, we aim to be discriminative for the actions we are searching. A large margin separation enables this goal.)。总的损失函数为
  
• 由上述损失函数训练得到的 hyperbolic embedding 并不能保证 entailment，即 region of each subtree to be fully covered by their parent. 为此，作者借鉴了 Hyperbolic entailment cones for learning hierarchical embeddings，将使用上述损失函数得到的 hyperbolic embedding 进一步使用下面的损失函数进行训练，从而使得不同子树彼此分开：
  其中 $E(\mathbf{u},\mathbf{v})$ 为 $\mathbf{u},\mathbf{v}$ 间的角度

Matching actions and videos

• Hyperbolic video embedding. $v\in {\mathbb{R}}^{W\times H\times T\times 3}$ 为 $T$ 帧的视频，由 3D ConvNet 可以得到 $D$-dimensional video representation $\mathbf{v}=\Psi (v;\theta )\in {\mathbb{R}}^D$，然后用指数变换将其投影到双曲空间得到 Hyperbolic video embedding ${\Psi }_e(v;\theta )={\exp }_0^c(\Psi (v;\theta ))$
  
• Hyperbolic prototype matching.
  注意到，Hyperbolic action embedding ${\varphi }_c(k)$ 是事先就训练好的，没有和 Hyperbolic video embedding 一起优化 (we keep the action prototypes fixed after projection into the shared space)

Hierarchical action search

• 根据 Hyperbolic action embedding 的优化过程，我们知道 siblings of an action class fall under the same entailment cone，即相似的动作 embed 之间的余弦相似度应该较高。对于 query $\mathbf{q}\in {\mathbb{D}}_c^n$，query 可以为 action name 或 video example，我们可以计算 query 和测试集中所有 video 之间的余弦距离来检索出最匹配的 video
  
• Sibling retrieval and classification. We retrieve actions by increasingly enlarging the entailment cone of a query in the shared space. For an action query, we start our search from the projection in the hyperbolic space and expand the entailment cone of the query in all directions. Upon enlarging the entailment cone, we first absorb videos from sibling action cones, then cousin cones. Only afterwards, we retrieve actions from other cones.
  

Experiments

• Ablation studies.
  Effect of hyperbolic curvature. Overall, we find that hyperbolic spaces are beneficial for hierarchical search and any value of $0<c\le 0.1$ results in a stable result across all three metrics. We therefore employ a fixed value of $c=0.1$ throughout further experiments.
  Effect of hyperbolic dimensionality.
  Effect of the discriminative loss.
  Visualizing action similarities.
  
• Hierarchical action search applications.
  Search by action name (注：${\Delta }^n$ 为 simplex，${\mathbb{S}}^{n-1}$ 为球形空间)
  Search by video example
  Hierarchical action recognition
  Zero-shot action search
  

[CVPR 2021] Unsupervised Hyperbolic Metric Learning

• Yan, Jiexi, et al. “Unsupervised hyperbolic metric learning.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.
• code: https://github.com/junhocho/HGCAE

Introduction

• 作者提出 Unsupervised Hyperbolic Deep Metric Learning，使得提取出的样本特征间的距离满足数据自身的层级结构

Methodology

• Hyperbolic Metric Learning. 作者在欧式模型 (CNN + FC) 后使用指数变换得到双曲嵌入，其中欧式模型使用预训练参数
• Hierarchical Similarity Generation. 作者使用 hierarchical clustering 对双曲空间内的样本点进行聚类。在层次聚类的每个 merging step 中，作者合并两个距离最近的 sub-clusters，合并时的 distance threshold 为 $\delta$，距离小于 $\delta$ 的 sub-clusters 才会被合并，其中 sub-clusters $C_a,C_b$ 间的距离为
  如上所述，设置不同的 $\delta$ 就可以得到不同数量的 sub-clusters. 如下图所示，作者设置了 3 组不同的 $\delta$ 值进行 3 次层次聚类，这 3 次层次聚类的结果就可以构成样本点的层次结构
  根据该层次结构，样本 $i,j$ 间的 similarity degree 为
  其中， L k ∈ { 1 , 2 , . . . , K } L_k\in\{1,2,...,K\} Lk​∈{1,2,...,K} 为 $i,j$ 被合并到同一 sub-cluster 时对应的 similarity level. 层次聚类计算 similarity degree 的过程在每个 epoch 开始时进行一次
• Loss Function. a new log-ratio loss that aims to approximate the ratio of similarity degrees by the ratio of distances in the learned hyperbolic embedding space
  其中，$z_i,z_j,z_l$ 为 triplet sample，$\Omega >0$ 为平衡 similarity degree 的超参，$i,j$ 间的相似度为 ${\Omega }^{s_{ij}}$
  

Experiments

Performance Comparisons with State­-of-­the-art Methods on image retrieval tasks

---

Ablation Studies

• Impact of different similarity levels
  
• Impact of different hyperparameter $\Omega$
  
• Performance contributions analysis
  

[CVPR 2022] Hyperbolic Vision Transformers: Combining Improvements in Metric Learning

• Ermolov, Aleksandr, et al. “Hyperbolic vision transformers: Combining improvements in metric learning.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
• code: https://github.com/htdt/hyp_metric

Introduction

• 作者提出了一种基于 ViT 的 hyperbolic-based model，就是将 ViT 输出的 [CLS] token 对应的 embed 通过指数变换投影到双曲空间 (Poincaré ball)，然后使用作者提出的 pairwise cross-entropy loss with hyperbolic distances 优化 embed

Method

Pairwise Cross-Entropy Loss

• 在每次迭代时随机采样 $N$ 个类别的图像，每个类别采样两个样本，形成 $K=2N$ 大小的 batch，其中包含了 $N$ 个正样本对 (想用大 batch 训练时也可以每个类别采样更多的样本数)。正样本对的损失函数为
  其中 $\mathbf{z}$ 为双曲空间中的 embed，$D$ 为距离函数，可以为双曲空间中的距离 $D_{hyp}$，也可以为 cosine similarity $D_{cos}$. 不过实验证明 $D_{hyp}$ 始终优于 $D_{cos}$
  
• The total loss is computed for all positive pairs, both $(i,j)$ and $(j,i)$, in a batch.

$\delta$-hyperbolicity

• 作者使用 3 种不同的 encoder 估算了数据集的 ${\delta }_{rl}$，用于计算出每个数据集最合适的 Poincaré disk radius $c$
  

Feature Clipping

• 由于 Poincaré embed 在优化时会使得 embed 靠近 Poincaré ball 的边界，因此 hyperbolic neural network 在优化时可能会有梯度消失的问题 (making the gradients of Euclidean parameters vanish). 常用的解决方法是 clip by norm (the standard norm value is $\frac{1}{\sqrt{c}}(1-10^{-5})$，即限制的最大 Enclidiean norm)，而 Clipped Hyperbolic Classifiers Are Super-Hyperbolic Classifiers 则提出 feature clipping 来解决上述问题：
  其中 ${\mathbf{x}}^E$ 位于欧氏空间，${\mathbf{x}}_C^E$ 为 ${\mathbf{x}}^E$ clip 后的结果，$r$ 为 a new effective radius of the Poincaré ball. 直观上看，feature clipping 通过将 embed 推离边界来避免梯度消失问题

Experiments

• ViT. 为了便于与以 ResNet-50 为 backbone 的模型做公平比较，作者使用 ViT-S，它在 MSA 只使用 6 个头 (base 版本使用 12 个头)，在参数量 (22M for ViT-S and 23M for ResNet-50) 和计算开销上 (8.4 FLOPS for ViT-S and 8.3 FLOPS for ResNet-50) 均与 ResNet-50 相近。除此之外，作者还尝试了 3 种预训练方法 (ViT-S, DeiT-S and DINO)，在微调时冻结 patch embeddings 的 linear projection 层
• Datasets. four benchmark datasets for category-level retrieval. CUB-200-2011 (CUB). The training set corresponds to the first 100 classes with 5,864 images, and the remain-ing 100 classes with 5,924 images are used for testing. Cars-196 (Cars). First 98 classes (8,054 images) are used for training and the other 98 classes (8,131 images) are held out for testing. Stanford Online Product (SOP). 11,318 classes (59,551 images) for training and remaining 11,316 classes (60,502 images) for testing. In-shop Clothes Retrieval (In-Shop). First 3,997 categories (25,882 images) are for training, the remaining 3,985 categories are used for testing partitioned into a query set (14,218 images) and a gallery set (12,612 images).
• Results. Sph 代表在损失函数中使用 $D_{cos}$，Hyp 代表在损失函数中使用 $D_{hyp}$
  128-dimensional encoder embedding. 要是作者能直接比较下双曲模型和对应的欧式模型在相同训练设置下的性能就好了~
  384-dimensional encoder embedding.
  
• We use UMAP method with the “hyperboloid” distance metric to reduce the dimensionality to 2D for visualization. For the training part, we can see that samples are clustered according to labels, and each cluster is pushed closer to the border of the disk. However, for the testing part, the structure is more complex. We observe that some of the samples tend to move towards the center and intermix, while others stay in clusters, showing possible hierarchical relationships. We can see that car images are grouped by several properties: pose, color, shape, etc.
  
• Impact of Hyperparameters.
  Encoder patch size.
  Manifold curvature. $c$ 越小，Poincaré 半径越大，$c$ 趋近于 0 时双曲空间退化为欧氏空间. We observe that the method is robust in the range (0.01, 0.3). 注意到根据估算得到的 $\delta$-hyperbolicity 值，$c$ 的估算值大约为 0.2，但根据这里的实验，更小的 $c$ 值在训练时更稳定. we believe this is due to an optimisation process that can be improved for the hyperbolic space. For this reason, we adjusted the default value towards a smaller 0.1
  Embedding size. the method has a reasonable representation power even in the case of lower dimensions.
  Batch size. The batch size directly influences the number of negative examples during the training phase; thus, intuitively, larger values have to be more profitable for the model performance. However, as the experiments show, the method is robust for batch size ≥ 400, having a minor accuracy degradation for batch size equal to 200.
  

[CVPR 2022] Clipped Hyperbolic Classifiers Are Super-Hyperbolic Classifiers

• Guo, Yunhui, et al. “Clipped Hyperbolic Classifiers Are Super-Hyperbolic Classifiers.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.

Introduction

• 目前，Hyperbolic Neural Networks (HNNs) 已经在具备 semantic hierarchies 的数据集上性能超过了 Euclidean neural networks (ENNs)，但在没有明显 hierarchies 的数据集上，HNNs 的性能仍弱于 ENNs，这限制了 HNNs 的进一步发展
• 作者认为这是源于欧式网络和双曲网络的混合架构带来的 BP 阶段梯度消失的问题，具体来说，是因为 HNNs 在训练时会使得 hyperbolic embeddings 接近 Poincaré ball 的边界，进而导致欧式网络参数梯度消失
  
• 对此，作者提出了一种高效的解决方法 Feature Clipping，即在训练 HNNs 时裁剪欧式特征的 feature magnitude 来防止 hyperbolic embedding 在训练时过于接近边界. 实验表明 clipped HNNs become super-hyperbolic classifiers，它们不仅在 hierarchical data 上性能超过了 HNNs，在 MNIST, CIFAR10, CIFAR100 和 ImageNet 数据集上性能也与 ENNs 相近，同时还具备更好的 adversarial robustness 和 out-of-distribution detection 性能

Super-Hyperbolic Classifiers from Clipping

Vanishing Gradient Problem in Training Hyperbolic Neural Networks

• Training Hyperbolic Neural Networks with Backpropagation. Euclidean parameters ${\mathbf{w}}^E$ 对应的梯度为
  其中 ${\mathbf{x}}^H$ 为输入 $\mathbf{x}$ 的 hyperbolic embedding，$\frac{\partial {\mathbf{x}}^H}{\partial {\mathbf{w}}^E}$ 为 Jacobian matrix. 由于 ${\mathbf{x}}^H$ 位于双曲空间，因此 $\frac{\partial \ell }{\partial {\mathbf{x}}^H}\in T_{{\mathbf{x}}^H}{\mathbb{B}}_c^n$ 为 Riemannian gradient，其中 B c n = { x ∈ R n : c ∥ x ∥ < 1 } \mathbb{B}_c^n=\left\{\mathrm{x} \in \mathbb{R}^n: c\|\mathrm{x}\|<1\right\} Bcn​={x∈Rn:c∥x∥<1}
  其中 $\nabla \ell ({\mathbf{x}}^H)$ 为 Euclidean gradient. 可以看到，当 $\Vert {\mathbf{x}}^H\Vert$ 趋近于 1 时，不管 $\nabla \ell ({\mathbf{x}}^H)$ 有多大，$\frac{\partial \ell }{\partial {\mathbf{w}}^E}$ 都将变得很小，从而产生梯度消失问题
• The Effect of Gradient Update of Euclidean Parameters on the Hyperbolic Embedding. 作者还理论分析了当欧式参数出现梯度消失时，双曲嵌入会几乎停止更新。令 ${\mathbf{x}}_{t+1}^H$ 为 $t+1$ 时刻的双曲嵌入，
  其中 $E:{\mathbb{R}}^m\to {\mathbb{R}}^n$ 为 Euclidean sub-network. 利用 ${\mathbf{w}}_{t+1}^E={\mathbf{w}}_t^E+\eta \frac{\partial \ell }{\partial {\mathbf{w}}^E}$ 和一阶泰勒展开可得
  令 $J_{{\mathbf{w}}_t^E}:=\eta {\left(\frac{\partial E\left({\mathbf{w}}_t^E\right)}{\partial {\mathbf{w}}_t^E}\right)}^T\frac{\partial \ell }{\partial {\mathbf{w}}^E}$，继续一阶泰勒展开，有
  令 $C\left(E\left({\mathbf{w}}_t^E\right)\right):={\left(\frac{\partial {\mathrm{Exp}}_0^c\left(E\left({\mathbf{w}}_t^E\right)\right)}{\partial E\left({\mathbf{w}}_t^E\right)}\right)}^T\eta {\left(\frac{\partial E\left({\mathbf{w}}_t^E\right)}{\partial {\mathbf{w}}_t^E}\right)}^T$，有
  其中指数映射 ${\mathrm{Exp}}_0^c(\mathbf{v})=\tanh (\sqrt{c}\Vert \mathbf{v}\Vert )\frac{\mathbf{v}}{\sqrt{c}\Vert \mathbf{v}\Vert }$ 对其输入的梯度为
  可以看到，当 $\Vert {\mathbf{x}}^H\Vert$ 趋近于 1 时，$\frac{\partial \ell }{\partial {\mathbf{w}}^E}$ 趋近于 0，双曲嵌入几乎停止更新
• Vanishing Gradient Problem. 作者还用实验做了进一步验证。作者在 MNIST 上训练了 CNN + hyperbolic classifier 的双曲模型，下图展示了训练过程中 6 个样本的 embed 在 Poincaré disk 上的移动轨迹，一个箭头就代表一次梯度更新。可以看到，随着训练的开展，所有 embed 都逐渐移动到了靠近边界的地方，进而导致了梯度消失
  从下图中也可以看出，刚开始训练时梯度大小随损失降低而减小，但在训练后期，尽管训练损失增加，但由于双曲嵌入靠近边界，梯度大小仍然很小
  

Clipped Hyperbolic Neural Networks

• Euclidean Feature Clipping. We employ the following hard constraint which regularizes the Euclidean embedding before the exponential map whenever its norm exceeds a given threshold
  $$\mathrm{CLIP}\left({\mathrm{x}}^E;r\right)=\min \left\{1,\frac{r}{\Vert {\mathrm{x}}^E\Vert }\right\}\cdot {\mathrm{x}}^E$$其中 ${\mathbf{x}}^E=E(\mathbf{x};{\mathbf{w}}^E)$ 为指数变换前的欧式嵌入，$r>0$ 为超参。双曲嵌入由裁剪后的欧式嵌入经过指数变换得到
  $$\mathrm{CLIP}\left({\mathrm{x}}^H;r\right)={\mathrm{Exp}}_0^c\left(\mathrm{CLIP}\left({\mathrm{x}}^E;r\right)\right)$$clipping value $r$ 和 effective radius of Poincaré ball 之间的对应关系如下图所示 (Clipped HNNs utilize a reduced region of Poincaré ball.) 作者在实验中发现 HNNs 对 $r$ 值比较鲁棒，因此作者固定 $r$ 值为 1
  

Experimental Results

• Results on Standard Benchmarks.
  
• Few-Shot Learning.
  
• Adversarial Robustness.
  
• Out-of-Distribution Detection. Out-of-distribution de-tection aims at determining whether or not a given in-put is from the same distribution as the training data.
  
• The Effect of Feature Dimension.
  

[Arxiv 2023] Hyperbolic Contrastive Learning

• Yue, Yun, et al. “Hyperbolic Contrastive Learning.” arXiv preprint arXiv:2302.01409 (2023).
• blog: [Arxiv 2023] Hyperbolic Contrastive Learning

[CVPR 2023] HIER: Metric Learning Beyond Class Labels via Hierarchical Regularization

• Kim, Sungyeon, Boseung Jung, and Suha Kwak. “HIER: Metric Learning Beyond Class Labels via Hierarchical Regularization.” (CVPR, 2023).
• code: https://github.com/tjddus9597/HIER-CVPR23
• blog: [CVPR 2023] HIER: Metric Learning Beyond Class Labels via Hierarchical Regularization

References

• 当复杂网络遇上机器学习：理解、计算网络的新视角—双曲几何
• Hyperbolic Representation Learning for Computer Vision (ECCV 2022 tutorial) (included some illustrative jupyter notebooks)