双曲神经网络容量界(Bound): HNN可以将任意大小的树以任意高精度嵌入双曲空间

1. 基本信息

• 论文题目:用于隐式树结构表示的双曲神经网络容量界
• Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures
• 作者:Anastasis Kratsios, Ruiyang Hong, Haitz Sáez de Ocáriz Borde
• 机构:麦克马斯特大学数学系、牛津机器人研究所

2. 摘要

本文研究了深度双曲神经网络(HNN)用于表示任意有限加权树的表示能力。首先,作者证明了任何多层感知机(MLP)都无法低失真地将大树嵌入低维欧式空间,与其深度、宽度或激活函数无关。具体而言,作者证明了任何嵌入树结构的MLP,其叶节点数大于欧式空间维数的二次方,其失真至少为叶节点数开d次根。与此形成对比的是,作者证明HNN可以将任意点云及其隐式树结构按任意精度地等距地嵌入双曲空间。此外,实现这种嵌入的HNN的深度、宽度和可训练参数数量与表示精度无关。实验结果证明了理论预测,即HNN优于MLP表示树结构。本文揭示了欧几里得空间与树结构之间的基本不兼容性,以及双曲空间的高效表示能力。

3. 介绍

• HNN最近在表示具有隐式层次结构的数据方面表现强劲,但主要依据的是直觉和经验。
• 本文通过数学分析证明了HNN表示树结构的优势,与此形成对比的是,作者证明了MLP表示大树结构必然产生失真。
• 本文的主要贡献是:
• 证明了MLP失真下界,与网络结构无关
• 证明HNN可以任意精度表示树结构,网络复杂度与精度无关
• 实验验证了上述理论预测

4. 方法

MLP树结构嵌入的下界

设,激活函数,是一个组合树,,叶节点数。

对任意MLP ,激活函数为,满足

其中与无关。则的失真至少为

常数项与的结构无关。

此结果表明,如果足够大,包含一个叶节点数为的树结构,是一个任意MLP,则对该树结构的表示失真至少为。也就是说,如果足够大,任意MLP都无法很好地表示该树结构,原因是欧几里得空间与树结构之间的几何结构不兼容,而非MLP结构的问题。

HNN树结构嵌入的上界

设,,。对任意点子集,任意度数至少为2的树结构。

存在曲率和HNN ,对任意满足

且定义的深度、宽度和可训练参数数量与无关,见表1。

该结果表明,HNN可以将任意大小的树以任意高精度嵌入双曲空间,且网络复杂度与精度无关。

5. 实验发现

• 在合成数据上比较了HNN和具有相同参数数量的MLP表示二叉树、三叉树和随机树的效果。
• HNN在所有设置下都优于MLP,达到更低的MSE损失。
• 随着树规模的增大和嵌入空间维数的减小,HNN与MLP的性能差异更加明显。

6. 结论

• 证明了MLP表示大树结构存在难以逾越的下界,与网络结构无关。
• 证明了HNN可以任意精度表示树结构,网络复杂度与精度无关。
• 实验验证了HNN优于MLP表示树结构。
• 揭示了欧几里得空间与树结构之间的基本不兼容性。
• 证明了双曲空间表示树结构的高效性。
• 支持了HNN在表示层次结构数据方面的优越性。