Ranking Preserving Nonnegative Matrix Factorization

1 Introduction

As a well-known approach for finding parts-based representations of non-negative data, nonnegative matrix factorization (NMF) [Lee and Seung, 1999] has shown remarkable competitiveness in variety of applications, such as clustering [Wang et al., 2017b] and classification [Zhang et al., 2015].

Recent advances in NMF could be roughly categorized into the unsupervised and the semi-supervised. The former [Cai et al., 2011; Wang et al., 2017b] mainly focuses on the features of data. In addition to features, the later [Liu et al., 2012; Zhang et al., 2016] utilizes a small amount of supervision information to achieve more discriminative representation learning. Examples of such information are category labels or pairwise relations including must-link and cannot-link, which specify whether the data must be or cannot be in the same class. Semi-supervised NMFs have benefited from the supervision information. However, existing supervisions suffer two major limitations. One is that both labels and pairwise relations are absolute information, so they are non-trivial to obtain if there is no prior knowledge provided; the other is that these supervisions only characterize the relationships between data and class, yet data usually contain rich information beyond what they can describe. To this end, we are inspired to tackle these limitations and further achieve more accurate learning by exploring data information more deeply.

∗Corresponding author

In reality, one may easily observe that ordinal relations are ubiquitous among data. Given three data i, j and q, an ordinal relation represents that i is more related to j than to q. For example, an image of "apple" is often more related to that of "banana" than to that of "ball"; a frame of a video sequence is often more related to its neighbouring frames than to those far way. Such comparative relation is naturally available and reliable [Liu et al., 2016]. It reflects the relative order among data and therefore can also uncover latent data structure. Furthermore, recent studies in numerous research fields such as ordinal embedding [Le and Lauw, 2016], hashing [Liu et al., 2016] and social networks [Song et al., 2015], have demonstrated that the ordinal relation plays an important role in performance improvements. Unfortunately, the ordinal relation is largely ignored by existing NMFs.

In this paper, we propose a novel ranking preserving NMF (RPNMF) to learn orderly structured representations. Figure 1 outlines RPNMF with a two-class dataset with each class being marked in red or blue. The original data representation matrix Xmay not reflect the true data structure, since real data are complex and often contaminated by noises. However, given a set of ordinal relations such as data i is more related to j than to q, i.e., R(i, j) > R(i, q), RPNMF can effectively enforce the distances among their corresponding representations to have the relation D(hi, hj) < D(hi, hq). Moreover, from Figure 1, we can easily deduce R(i, j) > R(i, q) >

R(i, s). Accordingly, the representation of data i, i.e., hi, is enforced to be the closest to hj and the furthest fromhs, i.e., D(hi, hj) < D(hi, hq) < D(hi, hs). As a result, a more discriminative representation matrix H is achieved with orderly structure rendered as a whole.

The main contributions of this paper are as follows:

• To our best knowledge, RPNMF is the first to incorporate the ordinal relation into NMF for representation learning. Due to the natural availability of the ordinal relation, RPNMF is also practical for real applications.
• With the ordinal relation, RPNMF effectively ranks the learned representations according to the true data structure of data, so that more discriminative representations are obtained.
• We derive an efficient linear iterative updating rule to solve the RPNMF's objective function, with its convergence guaranteed.
• Extensive experiments have demonstrated that RPNMF unifies the process of representation learning with orderly structure preserving, leading to more accurate clustering and classification against the state-of-the-arts.

2 RelatedWork

Several variants of NMF have been proposed to seek for more effective data representation in recent years. Under the unsupervised setting, [Cai et al., 2011] proposed a graph regularized NMF (GNMF) to model the local manifold structure. Later, MCNMF [Wang et al., 2017b] explores diverse information among multiple components (sub-features) of data. Under the semi-supervised setting, CNMF [Liu et al., 2012] ensures data with the same label to have the same representations with the utilization of labels. CPSNMF [Wang et al., 2016] propagates the pairwise relations from supervised data to unsupervised data to obtain the supervisions of the entire dataset. As one of the most representative pairwise NMFs, NMFCC [Zhang et al., 2016] enforces the similarity/dissimilarity for data on a must-link/cannot-link. Although pairwise NMFs incorporate the relations of data as supervisions, our RPNMF works quite differently and is actually more advanced in three main aspects. Firstly, the mustlink/cannot-link is limited to paired data which belong to the same class or two different ones, but the ordinal relation is a triplet information either within one class or across multiple ones. Secondly, with must-link/cannot-link, pairwise NMFs enforce representations to be close/far away, but RPNMF takes a step further by preserving relative order among data, even when they are from the same class. Thirdly, two pairwise relations may derive an order relation, such as if i is must-link to j but cannot-link to q, we can derive i is more related to j than to q. However, the reverse derivation may not hold. That is to say, pairwise relations could be utilized by RPNMF, but pairwise NMFs cannot effectively incorporate ordinal relations. An elaborate review of existing NMFs can be found in [Wang and Zhang, 2013]. However, none of them pay attention to the ordinal relations among data.

The ordinal relation was originally explored in ordinal embedding. The goal of ordinal embedding is to learn lowdimensional representations by utilizing ordinal relations only. Recently, a number of approaches have been proposed from different aspects. For example, LOE [Terada and Luxburg, 2014] simultaneously preserves the ordinal structure and the density structure of the data. MVTE [Amid and Ukkonen, 2015] uncovers multiple hidden attributes of data, since the data relations can be measured based on different attributes (e.g. colors, shapes). Thereafter, COE [Le and Lauw, 2016] preserves co-embedding cross multiple types of data. The most relevant work to ours is t-STE [Van Der Maaten and Weinberger, 2012], which collapses higher related data and repels data on a lower relation. However, t-STE and other approaches have not considered features of data.

3 Ranking Preserving NMF (RPNMF)

Given ordinal relations and a data matrix X = [x1, x2, . . . , xn] ∈ Rm×n , where each column is a data vector with m-dimensional features, we aim to learn a low-dimensional representation matrix H = [h1, h2, . . . , hn] ∈ Rk×n of X with the ordinal relations preserved, where k (usually k ≪ min{m, n}) denotes the reduced dimension.

3.1 Preliminary

NMF seeks for a basis matrix W and a representation matrix H, where the product of the two matrices can well approximate the original matrix X, i.e., X ≈ WH. Mathematically, NMF solves the following objective function:

where ‖ · ‖F denotes Frobenius norm. Then the multiplicative algorithm is derived to infer W and H [Lee and Seung, 2001]. Obviously, the representation learning process of NMF depends on the features of data only. The learned H may not maintain ordinal structure when ordinal relations are available, as proven in the Proposition 1.

Proposition 1 Given an ordinal relation, i.e., data i is more related to j than to q, NMF cannot ensure the corresponding representation hi be closer to hj than to hq.

Proof. Here, we use the "proof by contradiction" with assuming that given an ordinal relation, i.e., data i is more related to j than to q. NMF can ensure the corresponding representation hi be closer to hj than to hq.

To prove this, we use the following counter example.

Given that

of which, the first three columns xi, xj or xq are corresponding to data i, j and q, respectively. According to (1), we obtain a basis matrix W and a representation matrix H with

and

Hence the distance between i and j in original space is smaller than the distance between i and q, i.e., ‖xi -xj‖22 < ‖xi - xq‖22 . Whereas the distance between i and j, as well as i and q in representation space are ‖hi - hj‖22 = 1.1854 and ‖hi -hq‖22 = 0.0109, respectively. Therefore, it is easy to check that given data i is more related to j than to q, ‖hi - hj‖22 > ‖hi - hq‖22 , which means the assumption does not hold. Therefore, Proposition 1 is proven.

In the following, we introduce our ranking preserving NMF (RPNMF) to embed ordinal relations so that more discriminative representations could be achieved.

3.2 RPNMF-model

We use R(i, j) > R(i, q) to denote an ordinal relation, i.e., data i is more related to j than to q. The objective of RPNMF is to enforce the representations of the data i and j to be closer than that of data i and q , i.e.,

where D denotes the distance measure. To achieve so, we minimize the following term:

Here, R+(·)/R-(·) indicates a higher/lower relative relation between two data. I(·) is an indicator which equals to "1" if the condition in the parenthesis is satisfied and "0" otherwise. It is clear to see that when R(i, j) > R(i, q), minimizing (3) enforces D(hi, hj ) < D(hi, hq).

Use L to represent a set of ordinal relations, then (3) could be extended for ∀(i, j, q) ∈ L as follows,

Using Euclidean distance for D, we can rewrite (4) as

To ensure a distance between ‖hi - hj‖22 and ‖hi - hq‖22 , a tunable threshold δ > 0 is incorporated to regulate the distances in-between as

(6)

Because (6) is non-continuous, we use a ReLU loss function f(t) = max(0, t) and obtain

where t = ‖hi - hj‖22 - (‖hi - hq‖22 - δ). Clearly, when R(i, j) > R(i, q), (7) penalizes t to encourage ‖hi -hj‖22 - ‖hi -hq‖22 → -δ. However, since (7) is non-differentiable with respect to hi, hj and hq, we use a Softplus loss function f(t) = log(1 + exp(t)) to approximate ReLU and get

By incorporating (8) into NMF, we obtain the objective function as follows,

where the first term represents the errors between X and the product of W and H. The second term is to maintain ordinal structure, and α is the trade-off parameter in between.

4 Optimization

In order to facilitate optimization, we rewrite (9) as

where X∪ indicates the rest vectors without ordinal information and H∪ is the corresponding representation matrix. The optimization problem in (10) is not convex, so it is non-trivial to find the global minimum. Here we divide (10) into several subproblems for alternately updating each variable with others fixed.

The optimizations of both W-subproblem and H∪-subproblem lead to NMF formulation [Lee and Seung, 2001], so the updating rules for W and H∪ are

hi-subproblem: Updating hi with other variables fixed leads to

By setting the derivative of F(hi) with respect to hi, we get the positive part ∇+ and the negative part ∇- as following,

Based on the coordinate descent algorithm [Tan and F´evotte, 2009], multiplying the ratio of ∇+ to ∇- in (14) with hi leads to the following updating rule:

Similarly, we obtain the updating rules for hj-subproblem and hq-subproblem as

4.1 Convergence Analysis

We have solved problem (10) by optimizing each subproblem alternately. Now, we analyze the convergence of the above and prove the value of the objective function is non-increasing under each updating rule in Proposition 2.

Proposition 2. The alternating optimization of (10) converges to local minimum.

Proof. Since the convergence of updating rules of W and H∪ can be guaranteed by NMF [Lee and Seung, 2001], here we only study the convergence of (10) under the rules of hi, hj and hq. Denoting the solution of the objective function F in (10) at the iteration round t as (W(t) , H(t) ∪ , h(t) i , h(t) j , h(t) q ). For the other variables being fixed with the value solved in the (t - 1)th step, the minimization of (10) w.r.t. hi at the iteration round t is turned into (13), which is a standard convex loss function. Therefore, we can deduce that, at the iteration round t, the solution h(t) i satisfies F(W(t) ,H(t) ∪ , h(t) i , h(t) j , h(t) q ) ≤ F (W(t-1) , H(t-1) ∪ , h(t-1) i , h(t-1) j , h(t-1) q ), with W(t) = W(t-1) , H(t) ∪ = H(t-1) ∪ , h(t) j = h(t-1) j , h(t) q = h(t-1) q . Similarly, we can prove that the above situation can also be satisfied when minimizing (10) w.r.t. h(t) j and h(t) q with other variables fixed. Therefore, the objective function F(W,H∪, hi, hj, hq) will monotonically decrease and the alternating iterations converge.

4.2 Complexity Analysis

The computations of updating (11) and (12) are O(mkn) and O(mknl), respectively, where nl represents the number of columns of X∪. As to (15), we use gi to represent the number of relations associated with hi. Similarly, gj and gq are used for (16) and (17). The cost for updating (15), (16) and (17) are O(k(m + gi)), O(k(m + gj)) and O(k(m+gq)). We also use ni, nj and nq to denote the number of non-repreated data i, j and q in the set L, respectively. So the total costs for hi, hj and hq are O(k(m + gi)ni), O(k(m+ gj)nj) and O(k(m+ gq)nq), respectively. Since max{nl, ni, nj, nq} < n, the overall computation cost of RPNMF is O(k(mn + gini + gjnj + gqnq)). Therefore, RPNMF has linear complexity w.r.t the number of data n.

5 Experiments

To demonstrate the effectiveness of RPNMF, we conducted both clustering and classification experiments not only on image benchmarks, i.e., Yale, ORL, Coil20 and NHill, but also on sequential datasets, including a cartoon video sequence and Hdm motion capture.

5.1 Datasets

The Yale [Liu et al., 2012] contains 11 face images for each of 15 subjects. Each subject's face images are in different facial expressions or configurations. The ORL [Liu et al., 2012] consists of 400 face images of 40 different subjects. Similar to the Yale, the images were taken with various lighting and facial expressions. The Coil20 [Wang et al., 2017b]is composed of 1440 images for 20 objects. The 72 images of each object were captured by a fixed camera at a pose intervals of 5 degree. The NHill [Wang et al., 2017b] is a face dataset sampled from the movie "Notting Hill". The faces of 5 main casts were used, including 4660 faces in 76 tracks. The Cartoon [Wang et al., 2017a] is a video sequence extracted from a short animation available online, which has 282 frames of three scenes. The Hdm05 is a motion capture dataset. As in [Wang et al., 2017a], we chose the scene 1-1 which contains 9842 frames and 14 activities.

5.2 Experiment Setup

We compared RPNMF with several state-of-the-arts, including unsupervised NMFs: NMF [Lee and Seung, 1999], RNMF [Kong et al., 2011], GNMF [Cai et al., 2011], ORNMF [Wang et al., 2017a], MCNMF [Wang et al., 2017b], a semi-supervised NMF: NMFCC [Zhang et al., 2016]) and an ordinal embedding approach: t-STE [Van Der Maaten and Weinberger, 2012]. Worth to mention that, unlike existing semi-supervised NMFs which utilize absolute information as priors, RPNMF makes the first attempt to introduce comparative relations. Thus, it is infeasible to compare with existing semi-supervised NMFs due to different supervisions. Nevertheless, to demonstrate that the ordinal relation cannot be effectively utilized by existing pairwise NMFs, we compared

4000

3500

3000

2500

2000

1500

1000

-500

0

500 1000 1500 2000 2500 3000

1

0.8

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8 -1

-0.5

0

0.5

1

1.5

0.8

0.6

0.4

0.2

0

-0.2

-0.4

-0.6

-0.8

-1.2 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8

Table 1: Clustering Results (%)

RPNMF with NMFCC by splitting each ordinal relation into a pair of must-link and cannot-link. The parameters for each compared method were set according to the parameter settings in original papers. For RPNMF, we varied the regularization parameter α and δ within {0.0001, 0.001, 0.01, 0.1, 1} and {0.001, 0.01, 0.1, 1, 10, 100}, respectively. To construct ordinal relations for t-STE and RPNMF, we first randomly selected 10% data for each dataset, and then constructed 30 ordinal relations for each selected data as in [Chang et al., 2014]. Without losing generality, the ordinal relations were constructed from two aspects. For each image dataset, we use the data matrix X and labels because they can be directly used for constructing ordinal relations, although the relations can also be formed by observing images. In particular, one half were constructed with labels as data with the same label are more related than those with different ones. The other half were constructed from p-nearest neighbour- Metrics Methods Yale ORL Coil20 NHill Cartoon Hdm05

t-STE

54.55 81.25 90.97 94.78 82.72 80.64

NMF

57.58 95.00 93.40 91.09 81.93 84.98

RNMF 48.48 88.75 94.44 79.61 82.14 71.39

AC GNMF 42.42 92.50 81.60 91.31 82.14 82.88

ORNMF 63.64 91.25 94.79 79.83 82.86 76.42

MCNMF 64.70 95.00 86.46 92.49 83.54 76.88

NMFCC 57.58 90.00 93.06 90.34 84.21 85.92

RPNMF 66.67 96.25 94.79 96.24 85.26 88.11

t-STE

28.57 35.38 55.17 91.42 74.71 18.85

NMF

30.00 60.00 59.57 53.41 74.30 18.68

RNMF 19.05 40.00 68.00 64.02 72.22 11.62

F-score GNMF 24.00 50.00 39.08 73.02 72.22 17.60

ORNMF 25.00 46.15 66.67 64.26 74.65 14.39

MCNMF 28.57 60.00 40.00 85.23 75.43 13.33

NMFCC 30.00 60.00 61.54 81.71 75.47 20.63

RPNMF 35.29 66.67 68.09 92.54 76.32 25.00

Table 2: Classification Results (%)

ing graph since data are usually more related to their nearest neighbours than those far away and p was set as 5 according to [Gong et al., 2017]. For the sequential datasets, we chose the first 15 relations with each containing two frames from the same scene/activity and one from another. Each of the second 15 relations is formed by choosing from a scene/activity two neighbouring frames and one farther away. All the experiments were done using Matlab 2014 in an Intel Core 3.50GHZ desktop.

5.3 Results and Analysis

Clustering. We applied k-means to the learned representation matrix H and adopted two widely used metrics, accuracy (AC) [Liu et al., 2017b] and normalized mutual information (NMI) [Liu et al., 2012], to assess the quality of clustering results. Since k-means is sensitive to initial values, we repeated the clustering 50 times, each with a new set of initial AC(%)

45

44.5

44

43.5

43

42.5

42

41.5

41

0 5 10 15 20 25 30

Numbers of ordinal relations for each data

10 20 50

45

44.5

44

43.5

centroid. Moreover, since all the compared methods converge to local minimum, we ran each method 10 times to avoid randomness. The average results are reported in Table 1. It can be seen that RPNMF achieves the best results on all datasets, which demonstrates the effectiveness of incorporating ordinal relations. Notably, NMFCC which incorporates pairwise relations by splitting the ordinal relations does not perform as well as RPNMF, proving that the ordinal relations cannot be directly or fully utilized by pairwise NMF approach.

Classification. We used H to classify data into a set of labels. For each dataset, 80% data from each class was randomly selected as training dataset and the rest as testing dataset. Similar to [Liu and Tsang, 2017; Liu et al., 2017a], the LIBLINEAR package [Fan et al., 2008] was used to train the classifiers. Same as clustering, we repeated each method 10 times and report the average AC and F-score [Pan et al., 2016], shown in Table 2. As we can see, RPNMF consistently outperforms the other methods on all cases, which demonstrates the effectiveness of RPNMF on classification. This could be due to a fact that the ordinal relation represents the relative order among data, thus brings more discriminations.

Ordinal relations analysis. We closely examined H for NMF and RPNMF to analyze the effect of the ordinal relations. Due to page restriction, we took a subset of Yale as an example for the following analyses. The Figure 2(a) shows that xi is closer to xq than to xj, although there exists R(i, j) > R(i, q). Seen from Figure 2(b), NMF still gives D(hi, hj ) > D(hi, hq), which experimentally proves that

NMF cannot maintain the ordinal structure and validates the Proposition 1. Consequently, it leads hj to be close to hs which belongs to a different group, so that an unsatisfied clustering result (AC = 68.18%) occurs. In contrast, RPNMF effectively enforces D(hi, hj) < D(hi, hq) < D(hi, hs) with R(i, j) > R(i, q) > R(i, s) as shown in Figure 2(c). Apparently, both hi and hj represent the faces of the same subject with glass, which are definitely of highest relativity. Since hs represents a face of a different subject, it is the least related to hi. Therefore, the H learned through RPNMF demonstrates a clearer structure of data and a more accurate clustering result (AC = 85.86%) is achieved.

Since the number of ordinal relations may influence the performance of RPNMF, we also analyzed this in Figure 3 from two aspects. Specifically, we first selected 10% data from the Yale and varied the relations associated with each selected data from 0 to 30 with 5 interval as in

Yale Yale AC(%)

50

45

40

35

30

25

20

15

10 0.0001 0.001 0.01

Parameter

(a)

50

45

40

35

30

25

AC(%)

20

15

10 0.001 0.01 0.1 1

Parameter

(b)

Figure 4: Clustering AC of RPNMF w.r.t parameters α and δ.

4

x 10

Yale

0 20 40 60 80 100120140160180 200

Iteration number

2 3 5

Yale

8 10

4

15

Number of cluster k

Figure 5: Convergence curve. Figure 6: Execution time.

Figure 3(a). We then varied percentages of data within {0%, 1%, 5%, 10%, 20%, 50%} and fixed 30 ordinal relations for each selected data in Figure 3(b). Both figures show that, overall, AC increases with more supervisions which prove further the effectiveness of incorporating ordinal relations.

Parameter analysis. We tested the effect of parameter α and δ of RPNMF on the Yale. First, we fixed δ = 10 to test α with varying from 0.0001 to 1, and then fixed α = 0.1 to test δ varying from 0.001 to 100. Figure 4 shows that both α and δ perform with a similar trend. For example, AC is relatively stable when α increases from 0.0001 to 0.1 then drop sharply when α > 0.1. This well demonstrates the robustness and effectiveness of RPNMF when both α and δ are chosen within a suitable range.

Computational speed analysis. Having proven the convergence of the updating rules of RPNMF in the section 4.1, here we experimentally demonstrated its convergence on the Yale in Figure 5. It can be seen that the objective function values are non-increasing and drop sharply within 200 iterations, which empirically validates the Proposition 2. As discussed in the section 4.2, RPNMF has linear complexity against the number of data n. To verify this claim, we varied the number of clusters k (each cluster contains 11 data) within {2, 3, 5, 8, 10, 15} and report the average execution time in Figure 6. Clearly, RPNMF is computationally linear.

6 Conclusion

In this paper, we have explored a new stream of semisupervised NMF and proposed a novel ranking preserving nonnegative matrix factorization (RPNMF). Unlike existing approaches which utilize labels or pairwise relations as supervisions, RPNMF is the first to incorporate the relative or-

4

Yale

0.1

1

Yale

10 100

der among data, i.e., ordinal relation. By unifying the orderly structure preservation and representation learning, RPNMF explicitly ranks the representations according to the relations. Extensive experiments on both image and sequential datasets have demonstrated that RPNMF can not only uncover the true data structure which beyond what existing NMFs can offer, but also achieves more accurate clustering and classification against the state-of-the-arts. With the natural availability of the ordinal relation, RPNMF is also practical in real applications.

Acknowledgements

This work was supported by JST CREST (No. JPMJCR1304), National Natural Science Foundation of China (No. 61702296) and EU H2020 project (No. 691215).