Generalization Error Bound for Hyperbolic Ordinal Embedding
Atsushi Suzuki,u00a0Atsushi Nitanda,u00a0Jing Wang,u00a0Linchuan Xu,u00a0Kenji Yamanishi,u00a0Marc Cavazza
Hyperbolic ordinal embedding (HOE) represents entities as points in hyperbolic space so that they agree as well as possible with given constraints in the form of entity $i$ is more similar to entity $j$ than to entity $k$. It has been experimentally shown that HOE can obtain representations of hierarchical data such as a knowledge base and a citation network effectively, owing to hyperbolic spaceu2019s exponential growth property. However, its theoretical analysis has been limited to ideal noiseless settings, and its generalization error in compensation for hyperbolic spaceu2019s exponential representation ability has not been guaranteed. The difficulty is that existing generalization error bound derivations for ordinal embedding based on the Gramian matrix are not applicable in HOE, since hyperbolic space is not inner-product space. In this paper, through our novel characterization of HOE with decomposed Lorentz Gramian matrices, we provide a generalization error bound of HOE for the first time, which is at most exponential with respect to the embedding spaceu2019s radius. Our comparison between the bounds of HOE and Euclidean ordinal embedding shows that HOEu2019s generalization error comes at a reasonable cost considering its exponential representation ability.
