Quaternion Ordinal Embedding

Wenzheng Hou, Qianqian Xu, Ke Ma, Qianxiu Hao, Qingming Huang

Introduction

Ordinal Embedding (OE) is a fundamental task in machine learning and information retrieval that involves mapping objects into a low-dimensional space based on relative similarity constraints. These constraints typically take the form of triplets: "Object $A$ is more similar to $B$ than to $C$." While traditional approaches rely on vector-based representations, they often struggle to capture the multi-faceted nature of semantic relationships.

In standard vector-based models, different semantic features are "entangled" into a single high-dimensional point. This makes it difficult to explicitly model distinct concepts simultaneously. For instance, a "toasted salmon" and "marinated pork" might share a "high protein" feature but differ significantly in categories like "seafood" versus "meat." A simple Euclidean distance between two vectors often fails to represent these nuanced, overlapping semantic channels.

Comparison between vector-based and the proposed matrix-based ordinal embedding mechanism.

Methodology: The QOE Framework

To address the limitations of vector entanglement, the authors propose Quaternion Ordinal Embedding (QOE). This method represents each object as a set of semantic subspaces defined by matrices rather than single points.

1. Quaternion Representation

To maintain parameter efficiency while using matrix representations, the model utilizes quaternions ($q = w + xi + yj + zk$). Each object is embedded into a $D$-dimensional quaternion space. Each dimension can be transformed into a $4 \times 4$ representation matrix or a $3 \times 3$ rotation matrix. This allows the model to capture complex matrix structures using only four parameters per dimension, matching the efficiency of traditional vector models.

2. Subspace Distance and Optimization

Instead of standard Euclidean distance, QOE employs a distance function inspired by the chordal Grassmannian distance. This measures the distance between the subspaces spanned by the quaternion-derived matrices. By doing so, the model can capture similarity across multiple semantic "channels" in a unified geometric framework. The model is optimized using a generic OE loss function (such as GNMDS or CKL) that penalizes violations of the input triplet constraints.

The overall framework of QOE, from input triplets to quaternion-based matrix embeddings and loss calculation.

Experimental Evaluation

The authors evaluated QOE against state-of-the-art vector-based (EOE) and hyperbolic (HOE) methods across several real-world datasets, including Music Artists, Food (images based on ingredients/taste), and Bird species.

Key Results

  • Significant Error Reduction: QOE consistently outperformed baselines. On the Food dataset, it reduced testing error by up to 46.12% compared to the best baseline. On the Bird dataset, improvements reached 42.42%.
  • Robustness to Sparse Data: The model maintained superior performance even with low training split ratios, suggesting better generalization capabilities than traditional methods.
  • Geometric Suitability: The authors observed that using $3 \times 3$ rotation matrices often yielded better results than $4 \times 4$ representation matrices, indicating that the geometric properties of rotation are particularly effective for capturing ordinal relationships.

Discussion and Key Insights

The primary strength of QOE lies in disentanglement through subspaces. By modeling objects as sets of subspaces, the model can allocate different semantic concepts to different matrix dimensions. This prevents features from merging into a muddled vector sum, allowing for clearer semantic clustering (e.g., meat, salads, and desserts appearing as distinct groups in t-SNE visualizations).

Limitations and Future Work

While empirically strong, the computational overhead of matrix operations and chordal distance calculations in very large-scale applications remains to be fully explored. Additionally, while the model captures semantic meaning effectively, future work could focus on grounding these subspaces in known ontologies to explicitly label which subspace corresponds to specific human-understandable concepts like "protein content" or "geographic origin."

In conclusion, Quaternion Ordinal Embedding provides a parsimonious and powerful alternative to vector-based embedding, offering a more nuanced way to represent the complex, multi-dimensional nature of human-perceived similarity.

Summary updated

Abstract

Ordinal embedding (OE) aims to project objects into a low-dimensional space while preserving their ordinal constraints as well as possible. Generally speaking, a reasonable OE algorithm should simultaneously capture a) semantic meaning and b) the ordinal relationship of the objects. However, most of the existing methods merely focus on b). To address this issue, our goal in this paper is to seek a generic OE method to embrace the two features simultaneously. We argue that different dimensions of vector-based embedding are naturally entangled with each other. To realize a), we expect to decompose the D dimensional embedding space into D different semantic subspaces, where each subspace is associated with a matrix representation. Unfortunately, introducing a matrix-based representation requires far more complex parametric space than its vector-based counterparts. Thanks to the algebraic property of quaternions, we are able to find a more efficient way to represent a matrix with quaternions. For b), inspired by the classic chordal Grassmannian distance, a new distance function is defined to measure the distance between different quaternions/matrices, on top of which we construct a generic OE loss function. Experimental results for different tasks on both simulated and real-world datasets verify the effectiveness of our proposed method.
BibTeX
@inproceedings{hou2022quaternion,
  author = {Wenzheng Hou and Qianqian Xu and Ke Ma and Qianxiu Hao and Qingming Huang},
  title = {{Quaternion Ordinal Embedding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/287},
}
Figure