Quaternion Ordinal Embedding

1 Introduction

Ordinal Embedding (OE) aims to embed objects into a space such that the distances between the embeddings satisfy the constraints of the relative comparisons (also called ordinal relationships) as much as possible. This problem has first been studied by Shepard [Shepard, 1962a; Shepard, 1962b] and Kruskal [Kruskal, 1964a; Kruskal, 1964b], and lately has drawn wide interests in the multimedia, information retrieval and computer vision communities.

Most of the existing ordinal embedding methods pursue the vector-based representations of objects. Specifically, denote xa, xb and xc as the vector representations of object a, b and c, respectively. If object a is more similar to object b than object c, then OE tries to push xa and xb together while pull xa and xc away. We illustrate this convention in the upper part of Fig. (1).

∗Corresponding Author

Intuitively, a good representation should convey both the semantic meanings (for example, the toasted salmon and the marinated pork in Fig. (1) are rich in protein) and the ordinal relationships (for example, the toasted salmon is more similar to the marinated pork than the Herb salad). However, the vector-based representation and the corresponding element-wise similarity function, e.g., Minkowski distance, cosine similarity, hamming distance, etc, might fail to simultaneously capture the above two information well. This is because the objects are mapped into a single common highdimensional space so that it is hard to disentangle different dimensions to express different semantics. For example, the toasted salmon and the marinated pork are semantically related w.r.t the concept 'rich in protein'. However, a simple vector-based representation is hard to explicitly model such a concept.

To avoid such a problem, we propose to model an object as a set of semantics subspace, with each subspace representing a potential semantic concept, as opposed to a single vectorbased representation. By doing so, we hope to establish an explicit connection between the overall similarity in the embedding space and the semantic concepts.

Then two key problems arise: 1) how to formulate a subspace? 2) how to measure the distance across subspaces? To solve the first problem, we might resort to a matrix-based representation in the sense that each linear subspace corresponds to a matrix. At first glance, one might directly represent an object by a matrix. However, this requires a huge number of parameters. In this paper, we propose to embed objects into a D-dimensional quaternion space. Thanks to the algebraic and geometric properties of quaternions, we are able to find a more efficient way to represent a matrix. To be more specific, a quaternion q = w+x · i+y · j +z · k corresponds to at least a 4 × 4 matrix and a 3 × 3 matrix. In this sense, these matrices only require 4 parameters. Therefore, a D-dimensional quaternion suffices to express D semantic subspaces in a parsimonious manner.

In terms of the second problem, on top of the quaternions, we only need to find a distance function for quaternion embeddings. Traditional methods [Zhang et al., 2019] project the quaternion embeddings into the high-dimensional Euclidean space and then adopt the Euclidean distance. Obviously, this strategy loses the algebraic and geometric properties of quaternions. Hence, it may not utilize the semantic subspace well. To overcome this limitation, inspired by the chordal Grassmannian distance [Bengtsson et al., 2007], we define a new distance function for the matrices corresponding to quaternions rather than the quaternions vectors. As a key trait, the proposed distance function could measure the similarity between two sets of matrices, encapsulating multiple semantic subspaces into a unified measurement.

We summarize the contributions of this work as follows:

• We present an early trial to reformulate the ordinal embedding problem in a quaternion space with matrixbased representations. Using matrix-based representation learning, we model an object as a set of subspaces with each subspace implying an inherent concept in the similarity comparisons.
• Inspired by chordal Grassmannian distance, a new distance function is proposed to measure the similarity for matrix-based representations established from quaternions.
• Experiments on both simulated and real datasets demonstrate that the proposed method achieves a convincing improvement over existing vector-based methods.

2 RelatedWork

2.1 Ordinal Embedding

In recent years, the ordinal embedding in the Euclidean space has been extensively studied. This problem is first studied by [Shepard, 1962a; Shepard, 1962b; Kruskal, 1964a; Kruskal, 1964b]. Subsequently, under a margin-loss-based setting, GNMDS [Agarwal et al., 2007] find a low-rank kernel matrix to make embedding satisfy the triplet constraints. Based on the probabilistic model setting, CLK

[Tamuz et al., 2011] samples responses to adaptively choose triplet-based relative-similarity queries. STE and t-STE [Van Der Maaten and Weinberger, 2012], assuming the BradleyTerryLuce noise model [Luce, 2012], think relative-similarity triplets are insufficient for obtaining a truthful embedding of objects, where the embeddings are learned from both relatively similar and dissimilar triplets instead. Since the similarity of objects would not be consistent with different tasks, POE [McFee and Lanckriet, 2011] integrates heterogeneous data to conform to the similarity measure optimally. SPE [Shaw and Jebara, 2009] and LOE [Terada and Luxburg, 2014] are proposed to generate embedding that preserves the ordinal constraints and the dataset's density structure simultaneously. Meanwhile, SVRG-SBB [Ma et al., 2019] accelerates the calculation of the ordinal embedding process by stochastic variance reduced gradient. However, all the above methods consider OE in the Euclidean space. HOE [Suzuki et al., 2019] is the first to extend the problem to the hyperbolic space, which can express hierarchical structure more effectively. Two types of ordinal embedding methods with different embedding spaces are summarized in Appendix C.

2.2 Distance Function

Generally speaking, there are three kinds of distance functions defined on point to point, point to subspace, and subspace to subspace respectively. Point to point distance can be denoted by d(x1, x2), the distance between two points x1 and x2, usually called Euclidean distance. Point to subspace distance can be denoted by d(x, S), the distance from point x to the subspace S, which is called L2-Hausdorff distance in [Moghaddam and Pentland, 1997; Turk and Pentland, 1991]. Subspace to subspace distance can be denoted by d(S1, S2), the distance between two subspaces S1 and S2. The principal angle is a commonly used concept in subspaces, which has a good performance [Nishiyama et al., 2005; Wolf and Shashua, 2004]. [Sun and Cheng, 2006] gives the relationship between the similarity and distance of the subspaces, designing a general construction framework of subspace. [Zuccon et al., 2009] analyzes the semantic difference between subspace distance and Euclidean distance in information retrieval. As for applications, subspace distance is widely used in many computer vision fields such as classification [Liu et al., 2011], clustering [Wang et al., 2016], and face recognition [Wang et al., 2008; Pang et al., 2009], which all achieve promising performance.

3 Methodology

In this section, we describe our proposed method in detail. As shown in Fig. 2, we try to model each object with a set of subspaces/matrices. We start by elaborating on the problem setting. Then introduce how to get matrix-based representation in the quaternion space and define a distance function to measure the similarity between two objects' representations.

3.1 Problem Setting

Given N objects and the ordinal relationship triplets

where [N] = {1, . . . ,N} and object a is more similar to object b than it is to object c. Given some distance function d(·, ·), the OE problem aims to learn the representations of objects, denoted as {x1, x2, . . . , xN}, such that the following objectives hold as much as possible:

3.2 Representations in Quaternion Space

Existing OE methods like EOE[Agarwal et al., 2007; Terada and Luxburg, 2014] and HOE[Suzuki et al., 2019] represent the objects as vectors. However, as is stated in Sec. 1, traditional methods might be insufficient to capture latent semantic information. To overcome the limitation, in this paper, we adopt quaternions to represent an object as a set of subspaces.

A quaternion vector consists of one real part and three imaginary parts, defined as q = w + x · i + y · j + z · k, where w, x, y, z are D dimensional real vectors and i, j, k are imaginary units that satisfy the following Hamilton's rules:

In the following two subsections, we show that a quaternion corresponds to at least two matrices. One is a 4 × 4 matrix termed as representation matrix, the other one is a 3 × 3 matrix called rotation matrix.

Representation Matrix of a Quaternion

Let wi, xi, yi, zi be the i-th dimension of w, x, y, z respectively. Then quaternion Qi = wi + xi · i + yi · j + zi · k is associated with a 4 × 4 matrix as follows:

We term this matrix form as the representation matrix of a quaternion. Interestingly, this matrix formulation preserves many algebraic properties of quaternions, such as: the quaternion addition and multiplication correspond to matrix addition and matrix multiplication; the conjugate of Qi corresponds to the transpose of Qi; Qi could be projected onto four matrix basis with projected values being wi, xi, yi, zi, respectively, and the four matrix basis satisfying similar Hamilton's rules (expect that the multiplication of three skewsymmetric matrix basis equals to the identity matrix -I).

Besides, from a representation matrix Qi, we could easily obtain the original quaternion Qi. Seeing the above good properties, we consider the representation matrix as a candidate matrix formulation of quaternions. Next, we continue to derive another matrix formulation.

Rotation Matrix of a Quaternion

It is noteworthy that a quaternion rotation p′ = QipQ-1 i can be algebraically manipulated into a matrix rotation p′ = Rip, where Ri is the rotation matrix given by:

where

This matrix form preserves the geometric properties of quaternions. Besides, according to [Bar-Itzhack, 2000; Markley, 2008], the original quaternion Qi can also be restored from the rotation matrix Ri.

3.3 Distance between Two Quaternions

Next, we elaborate on how to calculate the distance between two quaternion embeddings. Traditional methods [Zhang et al., 2019] project the quaternion embedding into the highdimensional Euclidean space. Specifically, given a quaternion vector q ∈ RD×4 , we can obtain a vector ˜ q = {w, x, y, z} ∈ R4D . Then the distance between two quaternion vectors ˜ q1, ˜ q2 can be calculated by the inner product, i.e., dE(˜ q1, ˜ q2) = √(˜ q1 - ˜ q2)T ( ˜ q1 - ˜ q2). Straightforward as it seems to be, such a distance function makes the quaternion space degenerate into the Euclidean space.

Remind that we aim to represent each object with a set of subspaces so that the distance should reflect the distance between two subspaces. We know that a matrix could span a linear subspace. Then it is a natural idea to measure the distance of two quaternion embeddings based on their matrix reformulation.

Then how to calculate the distance between two matrices? In this paper, inspired by the classic chordal Grassmannian distance [Bengtsson et al., 2007], we proposed a distance function to calculate the distance between two quaternion embeddings. The chordal Grassmannian distance is defined as follows

where A and B denote a pair of matrices, tr(·) is the trace of a matrix, m is the dimension of the matrix, and Om denotes the set of all m×m orthogonal matrices.

Herein, we would like to point out that the representation matrix Qi and the rotation matrix Ri are both orthogonal matrices as long as w2 i + x2i + y2 i + z2 i = 1 for a quaternion qi = wi + xi · i + yi · j + zi · k. On top of this, our distance function is based on the chordal Grassmannian distance. For each D-dimension quaternion embedding q = {q1, . . . , qi, . . . , qD}, we could obtain D 4×4 representation matrices {Q1, · · · ,Qi, · · · ,QD} andD 3×3 rotation matrices {R1, · · · ,Ri, · · · ,RD}. Let Mi ∈ Rm×m denote either Qi (m = 4) or Ri(m = 3). We could construct a new diagonal matrices Mwith M1,M2, ...,MD as the diagonal sub-matrices, i.e.,

where the omitted parts are all zero matrices. The distance function between two quaternion embeddings qa and qb is defined as follows

where M a i is the i-th diagonal sub-matrices of thematrixMa corresponding to the quaternion vector qa.

3.4 Optimization Objective

On top of the quaternion embeddings and the developed distance function, our optimization objective is to learn the representations of objects {q1, q2, . . . , qN}, such that:

hold as much as possible. Let ℓ be the loss function of one triplet. Then the loss function is developed as:

where |S| is the number of triplets. In the experiments, we implement different loss functions such as the GNMDS loss function [Agarwal et al., 2007; Terada and Luxburg, 2014] and the CKL loss function [Tamuz et al., 2011]. The readers are referred to Appendix A for more details.

4 Experiments

In this section, we conduct extensive experiments to verify the effectiveness of our proposed method on one synthetic dataset and three real-world datasets. We show a detailed description of the four datasets in the Appendix B.

4.1 Synthetic Dataset

Evaluation metrics. We adopt testing error as our evaluation metric, which is defined as the ratio of the wrongly predicted triples in the test set. For sake of better credibility of our experiments, we also provide the mean and standard deviation of the test error.

Competitors. We compare our method against two types of vector-based ordinal embedding: one is in the Euclidean space (EOE [Agarwal et al., 2007]) and other one is in the Hyperbolic space (HOE [Suzuki et al., 2019]). To further demonstrate the effectiveness of our proposed QOE, we apply five different loss functions (see Appendix A) on top of EOE, HOE and QOE (ours), respectively. More specifically, the five losses include: 1) GNMDS1: GNMDS loss function [Terada and Luxburg, 2014] with q = 1; 2) GNMDS2: GNMDS loss function with q = 2; 3) CKL [Tamuz et al., 2011]; 4) STE [Van Der Maaten and Weinberger, 2012]; 5) t-STE. Ours1 and Ours2 represent QOE based on the representation matrix Q in Eq.(1), and the rotation matrix R in Eq.(2), respectively. For HOE and Ours, we report the best results on five loss functions.

Implementation details. To ensure a similar total number of parameters to make fair comparisons, when the dimension of real vectors in EOE or HOE is D, we set the dimension of quaternion vectors is D/4. We conduct experiments for D = {4, 8, 16}. We apply random initialization for embedding and choose Adam [Kingma and Ba, 2015] as optimizer. The batch size is set to 512, learning rating λ = 0.1 and the number of epochs is set to 200 for all methods. During training, if the optimal results of several epochs are not updated, we will end the training early. The experimental environment is shown in the appendix D. All experiments are conducted on Ubuntu 16.04.6 LTS, with NVIDIA TITAN RTX. The algorithm is written in Python 3.6.8 and uses the deep learning framework called TensorFlow 1.14.

Results. The results are presented in Tab. 1, fromwhich we can observe that Our QOE achieves a clear margin in performance gain over all baselines on three different dimensions. This shows that the matrix-based representation can better model ordinal relationships and better capture the latent semantic information of objects than vector-based representation methods. Besides, Ours2 obtains the minimum error in most cases while Ours1 is the second best in most cases. This shows that the rotation matrix may better model the inherent properties of quaternions than the representation matrix.

4.2 Music Artists Dataset

Implementation details. The batch size 1,024, learning rating λ = 0.5 and the epochs number 100 are used for all methods. During training, if the optimal results of several epochs are not updated, we will end the training early. The other settings are the same as setting on the synthetic dataset.

Results. As shown in Tab. 2, our proposed method also outperforms competitors. In particular, Ours2 improves the best competitor's performance by 6.43%, 9.31%, 20.00% on three dimensions, respectively. We also report AUC (the other datasets do not have class labels, thus we can not calculate AUC on them), which is shown in Fig. 3, from which we can see our proposed method also outperforms the competitors. Therefore, the effectiveness of matrix-based representation is again validated.

4.3 Food Dataset

Implementation details. We set the batch size to 1, 024, the learning rating λ = 0.05 and the number of epochs to 80

for all methods. Other settings are the same as the synthetic dataset.

Results. The testing errors for split ratio of 0.3 are recorded in Tab. 3. It shows that our proposed method still consistently outperforms all baselines over test error metric. Specifically, Ours2 outperforms the best competitor by 30.32%, 46.12%, 42.76% on three dimensions, respectively. As the proportion of the test set increases, the errors of each method are increasing. It is easy to understand that the smaller training set will result in over fitting, and embedding cannot satisfy the ordinal constraints well. This shows that QOE is more robust.

4.4 Bird Dataset

The testing errors of bird dataset are recorded in Tab. 4. It shows that our proposed method still consistently outperforms both baselines over testing errors metric. Specifically, Ours2 outperforms the best competitor by 36.88%, 40.22%, 42.42% on three dimensions, respectively. The clear margin in performance gain validates the effectiveness of the proposed QOE methods.

4.5 Embedding Visualization

We visualize the embeddings learned by our methods on Food dataset and Bird dataset, as shown in Fig. 4 and Fig. 5. For Food dataset, from Fig. 4, we see that the learned embeddings shows good clustering behavior with desserts gathered into the bottom right. The meats are close to each other into the left, as are the salads into the bottom middle and baking goods into top left. As for the Bird dataset, from Fig. 5 we see that the learned embeddings also cluster into different groups and each cluster represent category of birds. The classification effect shown in both figures demonstrate that the proposed QOE method is able capture semantic meanings thanks to the proper-structured matrix-based representations.

4.6 Ablation Study

We compare the performance of using quaternions (Ours) and using random matrix. To ensure that the total number of parameters is similar, we compare between 3 × 3 randominitialized matrices and 2-dimensional quaternion vectors (D = 8). The results are shown in Tab. 5. As shown in Tab. 5, in most cases, QOE performs better than using random matrices, which shows that our QOE method is both efficient and effective.

Furthermore, we split datasets into training/test sets by different split ratios [0.2, 0.3, ..., 0.8], where the split ratio is equal to the proportion of the test set to the total dataset. For each split ratio, several experiments are performed and we report the mean and standard deviation of testing errors, as shown in Fig. 6. From the figure, as the proportion of the test set increases, the errors of each method are increasing. However, our QOE is shown to perform better when there is less training samples, which shows that our method is more robust to over-fitness and has better generalization performance.

5 Conclusion

In this work, we propose a matrix-based representation learning to model the similarity relationships among objects. Specifically, we adopt the quaternion space as the embedded space, where every quaternion vector corresponding to an object can be converted into a collection of matrices, which spans a subspace of the embedded space. Furthermore, inspired by the classic chordal Grassmannian distance, a new distance function is defined to measure the similarity of different subspaces. We also conduct experiments on synthetic and several real datasets to verify our proposed method's effectiveness, which achieve promising experimental results.

Ethical Statement

There are no ethical issues.

Acknowledgements

This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, in part by National Natural Science Foundation of China: U21B2038, 61931008, 61836002, 6212200758, 61976202 and 62006217, in part by the Fundamental Research Funds for the Central Universities, in part by Youth Innovation Promotion Association CAS, in part by the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDB28000000, and in part by China Postdoctoral Science Foundation 2021T140653 and 2020M680651.