Mickael Febrissy

Aghiles Salah

Melissa Ailem

Mohamed Nadif

Improving NMF Clustering by Leveraging Contextual Relationships Among Words

Non-negative Matrix Factorization (NMF) and its variants have been successfully used for clustering text documents. However, NMF approaches like other models do not explicitly account for the contextual dependencies between words. To remedy this limitation, we draw inspiration from neural word embedding and posit that words that frequently co-occur within the same context (e.g., sentence or document) are likely related to each other in some semantic aspect. We then propose to jointly factorize the document-word and word-word co-occurrence matrices.

The decomposition of the latter matrix encourages frequently co-occurring words to have similar latent representations and thereby reflecting the relationships among them. Empirical results, on several real-world datasets, provide strong support for the benefits of our approach. Our main finding is that we can drastically improve the clustering performance of NMF by leveraging the contextual relationships among words explicitly.

Introduction

Since the work of Lee and Seung [START_REF] Daniel | Learning the parts of objects by non-negative matrix factorization[END_REF][START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF], Non-negative Matrix Factorization (NMF) has been receiving more and more attention as a fundamental tool for analyzing positive data arising in various areas, such as computer vision and text analysis.

Compared to other matrix factorization techniques such as Singular Value Decomposition (SVD), NMF is attractive due to the non-negativity constraints, making it possible to produce latent representations which are highly interpretable and well-suited for some tasks such as clustering, for which we focus on.

Although clustering is not the primary purpose of Non-negative Matrix Factorization (NMF) [START_REF] Daniel | Learning the parts of objects by non-negative matrix factorization[END_REF][START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF], the latter has received a lot of interest in the clustering community resulting in a new class of clustering algorithms-based on NMF.

Furthermore, a series of works [START_REF] Ding | On the equivalence of nonnegative matrix factorization and spectral clustering[END_REF][START_REF] Li | The relationships among various nonnegative matrix factorization methods for clustering[END_REF][START_REF] Chris Hq Ding | Convex and semi-nonnegative matrix factorizations[END_REF] established theoretical connections between NMF and k-means, spectral clustering, providing strong support and theoretical foundations for NMF-based clustering. More precisely, NMF is equivalent to a relaxed k-means clustering yielding a soft partitioning.

In this paper, we deal with NMF from a clustering perspective, and we particularly focus on the task of text document clustering, which constitutes one of the most popular and prominent applications of NMF. Clustering text documents is of great interest for several practical reasons such as: automatic summarization and organization of documents, efficient browsing and navigation of huge text corpora, visualization, speed up search engines, etc. In this context, NMF-based algorithms decompose the document-word matrix into a document and word factor matrices containing, respectively, the low dimensional representations-embeddings-of each document and word [START_REF] Xu | Document clustering based on nonnegative matrix factorization[END_REF]. It turns out that, the document factor matrix encodes some latent patterns of the original matrix that are well suited to cluster text documents. Despite all the notable efforts which highlighted the potential of NMF for 2 clustering text documents [START_REF] Li | Nonnegative matrix factorizations for clustering: A survey[END_REF], this approach still exhibits some limitations, namely it does not explicitly account for the semantic relationships between words. Hence, words having a common meaning-synonyms-or more generally words that are about the same topic are not guaranteed to be mapped in the same direction in the latent space. This is simply due to the fact that words with similar meanings are not necessarily used exactly in the same documents. Consequently, similar embeddings are not guaranteed even for closely related documents using words with similar meanings. Hence, our intuition is that, if we are successful in capturing the semantic relationships among words in an NMF model we can expect document factors which are even better for clustering.

The research question is how to capture and leverage the relationships among words in an NMF model? In this paper, we draw inspiration from neural word embedding and rely on the distributional hypothesis [START_REF] Zellig | Distributional structure[END_REF], which states that words in similar contexts have similar meanings. The context is a modeling choice that could be data-or problem-specific. For instance, a document or a sentence is a context in which words co-occur. Note that other definitions of "contexts" are possible [START_REF] Levy | Neural word embedding as implicit matrix factorization[END_REF]. An early application of that hypothesis in Matrix Factorization is the Hyperspace Analogue to Language (HAL) [START_REF] Lund | Producing high-dimensional semantic spaces from lexical co-occurrence[END_REF] framework. It employs a word-word co-occurrence matrix whose entries encode the number of times each pair of words has occurred in the same context. Thus, following the distributional hypothesis, we assume that words which frequently co-occur in the same context are likely related to each other in some semantic aspect. We then, propose a new NMF model which jointly decomposes the document-word and word-word cooccurrence matrices into two separate products that share one factor. The intuition behind the decomposition of the latter matrix is to make the representations of frequent co-occurring words closer to each other in the latent space so as to reflect the relationships among them. We further consider a non-linear transformation of the word co-occurrences, based on the Pointwise Mutual Information (PMI), for effectiveness and efficiency purposes.

In order to infer the factor matrices, we propose a scalable alternating optimization procedure based on a set of multiplicative update rules, similar to original NMF, which guarantees to decrease monotonically our objective function at each iteration, until convergence. We conduct extensive experiments to illustrate the benefits of our model and better characterize the circumstances in which it offers the most significant improvements. Our main finding is that, we can drastically improve the clustering performance of NMF by leveraging explicitly the contextual relationships among words 1 .

The outline of the paper is as follows. Section 2 is devoted to present related work. In Section 3, we briefly review the original NMF model and some recent results concerning the skip-gram model with negative sampling-word2vecthat we exploit in our work. In section 4, we present our model and derive a scalable iterative algorithm for inference. Section 5 is devoted to numerical experiments. Subsequently, we discuss some possible extensions of our model that we have already investigated (section 6). Finally, we conclude and suggest paths for future research in section 7.

Related Works

Our contribution is mainly related to the works on non-negative matrix factorization for clustering. The literature on NMF is very large; for instance the reader can refer to [START_REF] Wang | Nonnegative matrix factorization: A comprehensive review[END_REF]. Below we try to provide a brief review of works that are most closely related to our contribution.

There has been a lot of research on developing new variants of NMF in the direction of clustering. For instance, Ding et al. [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF], Yoo and Choi [START_REF] Yoo | Orthogonal nonnegative matrix factorization: Multiplicative updates on stiefel manifolds[END_REF] proposed orthogonal NMF, which constrains the document factor matrix to be orthogonal, and highlighted the importance of such constraint for clustering. Ding et al. [START_REF] Chris Hq Ding | Convex and semi-nonnegative matrix factorizations[END_REF] introduced Semi-NMF and Convex-NMF, enforcing the non-negativity constraint on the document factor matrix, but allowing the original data to have mixed signs [START_REF] Allab | A semi-nmf-pca unified framework for data clustering[END_REF]. Although both variants have been found to perform somewhat less well than NMF for clustering positive data, they expand the applicable range of NMF models, to data having mixed sings, as well as strengthen their relation to clustering. In [START_REF] Yuan | Projective nonnegative matrix factorization: Sparseness, orthogonality, and clustering[END_REF][START_REF] Yang | Linear and nonlinear projective nonnegative matrix factorization[END_REF] the authors proposed Projective NMF (PNMF) with a single latent factor matrix only. PNMF is equivalent to soft k-means clustering and performs better than NMF for text document clustering.

Cai et al. [START_REF] Cai | Graph regularized nonnegative matrix factorization for data representation[END_REF] developed Graph Regularized NMF (GNMF), which aims to preserve the intrinsic geometry of the data distribution. In GNMF, the data (document) manifold structure is modeled by a nearest neighbor graph, and it is incorporated into original NMF as an additional regularization term in order to force the embeddings of documents, which are connected, to be close to each other. Shang et al. [START_REF] Shang | Graph dual regularization non-negative matrix factorization for co-clustering[END_REF] proposed graph dual regularized NMF, which extends GNMF to model both the data manifold and feature manifold simultaneously. In order to reduce the sensitivity of GNMF to the nearest neighbor graph's parameters, the authors in [START_REF] Jing-Yan | Multiple graph regularized nonnegative matrix factorization[END_REF] developed multiple graph regularized NMF where the the data manifold is approximated by a linear combination of several nearest neighbor graphs having different parameters. In the same vein, more robust extensions of NMF, which can handle data points lying in complex manifolds, have been recently proposed [START_REF] Huang | Robust manifold nonnegative matrix factorization[END_REF][START_REF] Gao | Local centroids structured non-negative matrix factorization[END_REF]. Modeling document manifolds is an orthogonal direction to the present work; here we focus on preserving the contextual relationships between words.

Extensions of NMF to co-clustering have been developed to cluster objects (e.g. documents) and features (e.g. words), simultaneously. These approaches [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF][START_REF] Yoo | Orthogonal nonnegative matrix tri-factorization for co-clustering: Multiplicative updates on stiefel manifolds[END_REF][START_REF] Labiod | Co-clustering under nonnegative ma-trix tri-factorization[END_REF][START_REF] Del | Non-negative matrix tri-factorization for co-clustering: an analysis of the block matrix[END_REF][START_REF] Allab | Multi-manifold matrix decomposition for data co-clustering[END_REF], commonly referred to as Non Negative Matrix Tri-Factorization (NMTF), seek a decomposition of the original data matrix into three non-negative factor matrices. Some other works [START_REF] Inderjit | Generalized nonnegative matrix approximations with bregman divergences[END_REF][START_REF] Cichocki | Csiszar's divergences for non-negative matrix factorization: Family of new algorithms[END_REF][START_REF] Cichocki | Non-negative matrix factorization with α-divergence[END_REF][START_REF] Qian | Non-negative matrix factorization with sinkhorn distance[END_REF] have focused on developing algorithmic extensions of NMF to accommodate different cost functions and different machine learning tasks, or to develop more effective and efficient algorithms to solve the NMF problem [START_REF] Klingenberg | Non-negative matrix factorization: Ill-posedness and a geometric algorithm[END_REF][START_REF] Gong | Efficient nonnegative matrix factorization via projected newton method[END_REF]. For more details on NMF and its extensions for clustering, please refer to [START_REF] Li | Nonnegative matrix factorizations for clustering: A survey[END_REF].

In order to leverage the relationships among words in NMF, we draw inspiration from neural word embedding. These approaches, seek continuous representations of words that reflect various linguistic regularities between them [START_REF] Bengio | A neural probabilistic language model[END_REF][START_REF] Mnih | A scalable hierarchical distributed language model[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. To achieve their objective, most neural word embedding methods rely on the distributional hypothesis of Harris [START_REF] Zellig | Distributional structure[END_REF]. For instance, the recently proposed skip-gram model with negative sampling aims to maximize the dot-product between the vectors of frequently occurring word-context pairs, and minimize it for random word-context pairs. For more details please refer to [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. What makes these models particularly appealing is their ability to learn word vectors that are good at capturing meaningful semantic and syntactic regularities between words [START_REF] Mikolov | Linguistic regularities in continuous space word representations[END_REF]. Similar to word embedding techniques, the model we propose relies on the distributional hypothesis to capture the semantic relationships between words in NMF. Our preliminary investigation of infusing NMF with contextual relationships among words has appeared recently as a short paper [START_REF] Ailem | Non-negative matrix factorization meets word embedding[END_REF]. In the present manuscript, we delve in-depth into this idea and present several new theoretical and empirical results.

Notation. Matrices are denoted with boldface uppercase letters and vectors with boldface lowercase letters. The Frobenius norm is denoted by . F and the Hadamard product by . The document-word matrix is represented by a matrix X = (x ij ) ∈ R n×d + , its i th row represents the weighted term frequency vector of document i ∈ I, i.e., x i = (x i1 , . . . , x id ) where denotes the transpose.

The word co-occurrence matrix is represented by C = (c jj ) ∈ R d×d + , following the nomenclature in neural word embedding, row j ∈ J corresponds to word w j , column j ∈ J denotes context word w j , and each entry c jj denotes the number of times the word-context pair (w j ,w j ) occurred in the same context (e.g., a sentence or a document). The word and context word vocabularies, J and J might be different.

Preliminaries

In the context of text data, NMF seeks a decomposition of a document-word matrix X into two low dimensional factor matrices Z = (z ik ) ∈ R n×g + and W = (w jk ) ∈ R d×g + , such that X ≈ ZW . To infer the latent factor matrices, NMF attempts to solve the following optimization problem

arg min Z,W D(X, ZW ), s.t. Z, W ≥ 0. ( 1
)
where D is a cost function that allows us to quantify the quality of the approximation of X by ZW ; D can be, for instance, the Frobenius norm or the I-divergence. As NMF has an inherent clustering property, the document factor matrix Z is usually considered as a soft cluster membership matrix, where z ik denotes the degree to which document i belongs to cluster k. A partition of the set of documents can then be obtained by assigning each document to the most likely cluster. Notice that, in order to make the solution of (1) unique, Z is usually normalized to have unit-length column vectors.

The PMI is an information theoretic measure widely used to quantify the association between pairs of outcomes coming from discrete random variables.

Formally, the PMI between word w j and its context word w j is given by PMI(w j , w j ) = log p(w j , w j ) p(w j )p(w j ) .

Given the word co-occurrence matrix C defined above, the PMI between w j and w j can be empirically estimated as follows

PMI(w j , w j ) = log c jj × c .. c j. × c .j , (3)

Method

Formulation

In this section, we describe our model, Semantic-NMF, which jointly performs NMF on the document-word matrix and word-word PPMI matrix, with shared word factors, to better capture and leverage the semantic relationships among words.

Formally the objective function of Semantic-NMF, to be minimized, is given by

F(Z, W, Q) = D 1 (X, ZW ) NMF +λ D 2 (M, WQ ) word embedding , (4)
where

D

Inference

In this section, we shall investigate the case where both D 1 and D 2 are the square of the Frobenius norm, and derive an iterative optimization procedure to infer the latent factor matrices. In this case, (4) takes the following form:

F(Z, W, Q) = 1 2 ||X -ZW || 2 F + λ 2 ||M -WQ || 2 F = 1 2 Tr (X -ZW )(X -ZW ) + λ 2 Tr (M -WQ )(M -WQ ) = 1 2 Tr XX -2XWZ + ZW WZ + λ 2 Tr MM -2MQW + WQ QW . (5)
In the following, we derive a set of multiplicative update rules in order to minimize

F under the constraints of positivity of Z, W and Q. Let α ∈ R n×g , β ∈ R d×g ,
γ ∈ R d ×g be the Lagrange multipliers for the constraints, the Lagrange function

L(Z, W, Q, α, β, γ) = L is given by L = F(Z, W, Q) + Tr (αZ ) + Tr (βW ) + Tr (γQ ).
The derivatives of L with respect to Z, W and Q are

∇ Z L = -XW + ZW W + α, (6a)
∇ W L = -(X Z + λMQ) + W(Z Z + λQ Q) + β, (6b)
∇ Q L = -λM W + λQW W + γ. (6c)
Setting these gradients to zero and making use of the Kuhn-Tucker conditions

         α Z = 0 β W = 0 γ Q = 0
we obtain the following stationary equations:

-(XW) Z + (ZW W) Z = 0,
-(X Z + λMQ) W + W(Z Z + λQ Q) W = 0, -(M W) Q + (QW W) Q = 0.
Based on the above equations we derive the following multiplicative update rules

Z ← Z XW ZW W , (7a)
W ← W (X Z + λMQ) W(Z Z + λQ Q) , (7b)
Q ← Q M W QW W . ( 7c
)
These update rules are analogous to those of NMF [START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF]. The difference is in how we update the word factors in Semantic-NMF. In the latter, the update of W depends on two sources of data (i) the document-word matrix and (ii) the PPMI co-occurence matrix M.

Theorem 1. The objective function of Semantic-NMF is non-increasing under the update formulas (7a), (7b) and (7c).

Proof. Equations (7a) and (7c) are similar to those of NMF [START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF], therefore based on the proof of [START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF] the objective function of Semantic-NMF is non-increasing under these two equations. Hence, we only need to demonstrate that F is nonincreasing under the update rule (7b), given Z and Q. To this end, we follow a similar approach to the one described in [START_REF] Daniel | Algorithms for non-negative matrix factorization[END_REF], which is inspired by the Expectation-Maximization (EM) algorithm [START_REF] Arthur P Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] and consists in using an auxiliary function.

Definition. G(w, w ) is an auxiliary function for F(w) if the following conditions are satisfied G(w, w ) ≥ F(w) and G(w, w) = F(w).

A key point to the auxiliary function is described by the following lemma.

Lemma 1. If G is an auxiliary function for F, then F is non-increasing under the update

w (t+1) = arg min w G(w, w (t) ). (8)
Proof.

F(w (t+1) ) ≤ G(w (t+1) , w (t) ) ≤ G(w (t) , w (t) ) = F(w (t) ). Now we will make use of an appropriate auxiliary function to demonstrate that our objective function F is non-increasing under the update rule (7b). Let w jk denote any element in W, and let F(w jk ) denote the part of F containing w jk . As the update (7b) is element-wise, it is sufficient to show that F is non-increasing under the update of w jk based on equation (7b). The first and second partial derivatives of F noted F , F are respectively given by

F (w jk ) = -X Z -λMQ + W(Z Z + λQ Q) jk , F (w jk ) = Z Z + λQ Q kk .
The following lemma yields an auxiliary function for F.

Lemma 2. The function G defined as follows

G(w jk , w (t) jk ) = F(w (t) jk ) + F (w (t) jk )(w jk -w (t) jk ) + W Z Z + λQ Q jk 2w (t) jk (w jk -w (t) jk ) 2 (9)
is an auxiliary function for F.

Proof. Based on Lemma 2 it straightforward to verify that G(w jk , w jk ) = F(w jk ).

We will now show that G(w jk , w

jk ) ≥ F(w jk ), by making use of the second order Taylor expansion of F about w (t) jk given by

F(w jk ) = F(w (t) jk ) + F (w (t) jk )(w jk -w (t) jk ) + Z Z + λQ Q kk 2 (w jk -w (t) jk ) 2 . (10)
Since

WZ Z jk = g k =1 w (t) jk Z Z k k ≥ w (t)
jk Z Z kk and similarly

WQ Q jk ≥ w (t) jk Q Q kk , we have (W(Z Z+λQ Q)) jk w (t) jk ≥ Z Z + λQ Q kk .
Thereby, from ( 9) and [START_REF] Cichocki | Non-negative matrix factorization with α-divergence[END_REF],

G(w jk , w (t) jk ) ≥ F(w jk ) holds.
Thus, to prove Theorem 1 it is sufficient to show that equation (7b) for w jk satisfies Lemma 1 where the auxiliary function G is given by Lemma 2. Substituting equation [START_REF] Cai | Graph regularized nonnegative matrix factorization for data representation[END_REF] to G(w jk , w

(t) jk ) in Lemma 1 leads to solve ∂G(w jk ,w (t) jk ) ∂w jk = 0 or, F (w (t) jk ) + W(Z Z + λQ Q) jk 2w (t) jk (2w jk -2w (t) jk ) = 0. Then w (t+1) jk = arg min w G(w jk , w (t) jk ) leads to w (t+1) jk = -w (t) jk F (w (t) jk ) (W (Z Z + λQ Q)) jk + w (t) jk = w (t) jk (X Z + λMQ) jk (W(Z Z + λQ Q)) jk .
It follows from the latter result and Lemma 1 that F is non-increasing under the update of w jk in equation (7b), ∀j, k. Given that (7b) is element-wise, the objective function of Semantic-NMF is non-increasing under the update rule (7b).

Thereby, based on Theorem 1, the fact that (7a), (7b) and (7c) satisfy the KKT conditions at convergence and F is bounded from below by 0, iteratively alternating the application of (7a), (7b) and (7c) will monotonically decrease criterion ( 5) and converge to a locally optimal solution. Our optimization procedure is depicted in Algorithm 1.

Algorithm 1 Semantic-NMF (SNMF). Input: X, M, λ and g the dimension of the latent factors.

Output: Z, W and Q.

1. Initialization: Z ← Z (0) ; W ← W (0) and Q ← Q (0) ; repeat 2. Z ← Z XW ZW W ; 3. W ← W (X Z+λMQ) W(Z Z+λQ Q) ; 4. Q ← Q M W QW W ; until convergence 5.
Normalize Z so as it has unit-length column vectors.

Computational Complexity Analysis

The following Proposition shows that the computational complexity of the SNMF algorithm scales linearly with the number of non-zero entries in the document-word and PPMI matrices. In practice X and M are very sparse, i.e., nz X n × d and nz M d × d. Furthermore, multiplicative update rules (7a), (7a) and (7c) are parallelizable across documents and words, thereby Semantic-NMF can easily scale to large datasets.

Proposition 1. Let nz X and nz M denote respectively the number of non-zero entries in X and M, and let it be the number of iterations. The computational

complexity of Semantic-NMF is given in O(it • g • (nz X + nz M ) + it • g 2 • (n + d)) .
Proof. The computational bottleneck of SNMF is with the multiplicative update formulas (7a), (7b) and (7c). Equations (7a) and (7c) are similar to those of NMF, and their respective complexities are O(nz

X •g +(n+d)•g 2 ) and O(nz M •g +d•g 2 ).
The number of operation in (7b), including multiplications, additions and divisions, is g(2nz X + 3nz M + 3d + g(4d + 2n + 1)), where we used d = d. The complexity of (7b) is thereby given in O(g

• (nz X + nz M ) + (n + d) • g 2 ).
Therefore, the total computational complexity of Semantic-NMF is

O(it • g • (nz X + nz M ) + it • g 2 • (n + d)).

Experimental study

Our objective is to investigate the effect of the contextual relationships between words on NMF models. To this end, we conduct extensive experiments in which we benchmark our model, Semantic-NMF (SNMF), against several state-of-the-art algorithms (including NMF models and clustering algorithms) on several realworld datasets. Furthermore, we also challenge the choice of the PPMI for M by considering another transformation arising from the word-word co-occurrence matrix, namely the Global Vectors for Word Representation (GloVe) [START_REF] Pennington | Glove: Global vectors for word representation[END_REF]. Note that, the Hellinger PCA (HPCA) [START_REF] Lebret | Word emdeddings through hellinger pca[END_REF] was also tested but did not demonstrated good enough performances to be considered in our proposal.

Datasets

We use six popular benchmark datasets, described in Table 1, namely CSTR

[33], CLASSIC42 , RCV1 containing the four largest classes of the Reuters corpus 3 , the SPORTS dataset (from the CLUTO toolkit [START_REF] Karypis | Cluto-a clustering toolkit[END_REF]) containing documents relating to seven different sports, the 20-newsgroups dataset NG20 3 , and the NG5 dataset consisting of five classes4 of NG20. These datasets are carefully selected so as to represent various particular challenging situations: different numbers of clusters, different sizes, different degrees of cluster overlap and different degrees of cluster balance (the Balance coefficient being the ratio of the minimum cluster size to the maximum cluster size). For each dataset, we apply the TF-IDF weighting scheme and normalize each document to unit L 2 norm so as to remove the biases induced by the length of documents.

Competing methods

Without the word embedding term in [START_REF] Biernacki | Model-based cluster and discriminant analysis with the mixmod software[END_REF], when λ = 0, the proposed SNMF degenerates to the original NMF (NMF) [START_REF] Xu | Document clustering based on nonnegative matrix factorization[END_REF]. Hence, we can achieve our objective of studying the effects of the word relationships on NMF, most effectively by comparing SNMF to NMF. Moreover, in order to show that leveraging the contextual relationships among words in NMF is effective for text document clustering, we also consider three strong NMF variants, namely orthogonal NMF (ONMF) [START_REF] Yoo | Orthogonal nonnegative matrix factorization: Multiplicative updates on stiefel manifolds[END_REF],

Projective NMF (PNMF) [START_REF] Yuan | Projective nonnegative matrix factorization: Sparseness, orthogonality, and clustering[END_REF] and graph regularized NMF (GNMF) [START_REF] Cai | Graph regularized nonnegative matrix factorization for data representation[END_REF]. All the above models have been found to perform very well and better than several other approaches in terms of text document clustering. A Deep-Learning algorithm, namely Deep Clustering Network (DCN) [START_REF] Yang | Towards k-means-friendly spaces: Simultaneous deep learning and clustering[END_REF] is also considered in our comparison; it outperforms several clustering (k-means, Spectral Clustering), NMF based method such as (LCCF) [START_REF] Cai | Locally consistent concept factorization for document clustering[END_REF] and Deep Learning algorithms (e.g. SAE [START_REF] Vincent | Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion[END_REF]). The Spherical k-means algorithm Skmeans [START_REF] Inderjit | Concept decompositions for large sparse text data using clustering[END_REF], which to this day, remains popular for the task document clustering is also included rather than k-means that is not suitable for sparse data.

Evaluation metrics

We retain two widely used measures to assess the quality of clustering, namely the Normalized Mutual Information (NMI) [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] and the Adjusted Rand Index (ARI) [START_REF] Hubert | Comparing partitions[END_REF]. Intuitively, NMI quantifies how much the estimated clustering is informative about the true clustering, while the ARI measures the degree of agreement between an estimated clustering and a reference clustering; both NMI and ARI are equal to 1 if the resulting clustering is identical to the true one.

Settings

For each dataset, g is the true number of clusters. To produce a fair comparison, the same initialization (namely Skmeans) was used across the NMF-like algorithms.

Similar settings to the ones used to in [START_REF] Pennington | Glove: Global vectors for word representation[END_REF] are employed for producing the GloVe embeddings; note that any other type of word-embedding can be used for the matrix M. Therefore, the GloVe embeddings dimension (in our case d ) was set to 100,

x max to 100, α to 3/4. A stochastic gradient descent algorithm with a learning rate of 0.15 was used to train the model. Subsequently, all negative entries in the GloVe embeddings are set to zero. In the following, this transformation is referred to as PGLOVE. The setting of the regularization parameter λ is achieved empirically and established w.r.t. the PPMI and PGLOVE matrices.

Empirical results

Below we comment on the results of our experiments and answer several questions related to our proposal.

What is the impact of the regularization parameter on the performances of SNMF? difficult and unreliable. However, a good trade off would be λ = 0.1. On the other hand, using the PPMI (see Figure 2), the variations of the NMI and ARI scores are consistent and linear once a jump is observed. In this case, setting λ is much trivial and reliable and we recommend to set λ to 0.1 since we observe good performance scores even for higher values of λ on all the datasets. For these reasons, using the PPMI appears as safer alternative. with an extra term encoding word co-occurrences. We can therefore attribute the improvement of SNMF upon the performance of NMF to the additional factorization of the PGLOVE or PPMI matrix. In addition, between our two versions (PGLOVE, PPMI), using the PPMI appears to offer better performance overall and will be the version considered in the rest of the paper. To gain further insights into the performances of SNMF and characterize the circumstances in which it provides the most significant improvements, we investigate several research questions below.

What happens with document embeddings? Figure 4 shows the distribution of the cosine similarities between pairs of documents belonging to the same "true" class, computed using the document embeddings produced by NMF (grey boxplots)

and SNMF (green boxplots). We observe that documents from the same class (topic) tend to have more similar embeddings under SNMF than NMF. This provides empirical evidence that accounting for the semantic relationships among words yields document factors that encode the clustering structure even better.

Is SNMF actually capturing the semantic relationships between words? Based on the document-word matrix, we select the top thirty words of each true class.

In Figure 5, we report the distribution of the cosine similarities between pairs of top words of the same class, computed using the word vectors inferred by NMF (grey boxplots) and SNMF (blue boxplots). Because the cosine similarity is likely We also investigate the effect of the contextual relationships between words by comparing SNMF with NMF in terms of cluster interpretability. To human subjects, interpretability is closely related to coherence [START_REF] Newman | Automatic evaluation of topic coherence[END_REF], i.e., how much the top words of each cluster are "associated" with each other. For each cluster k, we select its top 30 words based on the kth column of W. We use the PMI, which is highly correlated with human judgments [START_REF] Newman | External evaluation of topic models[END_REF][START_REF] Role | Handling the impact of low frequency events on co-occurrence based measures of word similarity-a case study of pointwise mutual information[END_REF], to measure the degree of association between top word pairs. For each cluster we average the PMI's among its top words, and for a model we average PMI across clusters. Because SNMF already exploits the PMI estimated from word co-occurrences in each dataset, we propose to use an external corpus to estimate the PMI in this experiment. Following Newman et al.

[41], we use the whole English WIKIPEDIA corpus, that consists of approximately 4 millions of documents and 2 billions of words. Hence, p(w j ) is the probability that word w j occurs in WIKIPEDIA, and p(w j , w j ) is the probability that words w j and w j co-occur in a 5-word window in any WIKIPEDIA document.

Figure 6 shows the average PMI obtained by SNMF and NMF, over the different datasets; it is clear that SNMF successes in capturing more semantics and inferring more interpretable clusters than NMF.

Cluster Ensembles

Throughout our experiments, Skmeans has proved to be a good initialization for gaining better NMF solutions with text data. However, we noticed that random starting values could sometimes lead to better solutions. Table 3 reports results of SNMF initialized with Skmeans and randomly. We can see that with RCV1, SNMF (Random) provides better partitions than SNMF (Skmeans). While this improvement only appears with one dataset (other encountering losses, see CLASSIC4 and NG5), we tried to benefit from that infrequent/inconsistent behavior by using the SNMF (Random) solutions along side those obtained with a Skmeans initialization. Furthermore, in unsupervised learning, selecting an unique partition among the set of trials has also been a reluctant problem which to this day remains unclearly addressed. In the case of NMF, the objective function is not defined as a clustering problem, therefore, it often happens that the selection of the best run (criterion-wise) among several does not account for getting the best clustering. However the best clustering could be among a set of lead solutions (for instance the 10 first ones). In other words, a consensus approach will also help us to overcome this issue.

In machine learning, the idea of utilizing multiple sources of data partitions firstly occurred with multi-learner systems where the output of several classifier algorithms where used together in order to improve the accuracy and robustness of a classification or regression, for which strong performances were acknowledged [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF][START_REF] Sharkey | On combining artificial neural nets[END_REF][START_REF] Amanda | Multi-net systems[END_REF]. At this stage, very few approaches have worked toward applying a similar concept to unsupervised learning algorithms. In this sense, we denote the work of [START_REF] Paul | Refining initial points for k-means clustering[END_REF] who tried to combine several clustering partitions according to the combination of the cluster centers. In the early 2000, [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] were the first to consider an idea of combining several data partitions however, without accessing any original sources of information (features) or led computed centers. This approach is referred to as cluster ensembles. At the time, their idea was motivated by the possibility of taking advantage of existing information such as a prior clustering partitions or an expert categorization (all regrouped under the terms Knowledge Reuse), which may still be relevant or substantial for a user to consider in a new analysis on the same objects, whether or not the data associated with these objects may also be different than the ones used to define the prior partitions. Another motivation was Distributed computing, referring to analyzing different sources of data (which might be complicated to merge together for instance for privacy reasons) stored in different locations. In our concept, we will use cluster ensembles to improve the quality of the final partition (as opposed to selecting a unique one) and therefore extract all the possibilities offered by the miscellaneous best solutions created by NMF.

In [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF], the authors introduced three consensus methods that can produce a partition. All of them consider the consensus problem on a hypergraph representation H of the set of partitions H r . More specifically, each partition H r equals a binary classification matrix (with objects in rows and clusters in columns) where the concatenation of all the set defines the hypergraph H.

• The first one is called Cluster-based Similarity Partitioning Algorithm (CSPA)

and consists in performing a clustering on the hypergraph according to a similarity measure.

• The second is referred to as HyperGraph Partitioning Algorithm (HGPA) and aims at optimizing a minimum cut objective.

• The third one is called Meta-CLustering Algorithm (MCLA) and looks forward to identifying and constructing groups of clusters.

Furthermore, in [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] the authors proposed an objective function to characterize the cluster ensembles problem and therefore allowing a selection of the best consensus algorithm among the three to deliver its ensemble partition. Let Λ = {λ (q) |q ∈ {1, . . . , r}} be a given set of r partitions λ (q) represented as labels vectors. The ensemble criterion denoted as λ (k-opt) is called the optimal combine clustering and aims at maximizing the Average Normalized Mutual Information (ANMI). It is defined as follows:

λ (k-opt) = arg max λ r q=1 NMI( λ, λ (q) ). ( 11
)
The ANMI is simply the average of the normalized mutual information of a labels vector λ with all labels vectors λ (q) in Λ:

ANMI(Λ, λ) = 1 r r q=1 NMI( λ, λ (q) ). (12)
To cast with cases where the vector labels λ (q) have missing values, the authors have proposed a generalized expression of ( 11) not substantially different that viewers can refer to in the original paper [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF].

Following the cluster-based consensus approach which implies a similaritybased clustering algorithm, we decided to make use of a model-based clustering to go and try to obtain a better final partition than the one delivered by cluster ensembles. In [START_REF] Topchy | A mixture model for clustering ensembles[END_REF], the authors have used the kq is the probability that an element m i in the group k takes the category h for the partition/variable λ q . The density probability function of the model can be stated as:

f (M; Θ) = n i=1 g k=1 π k r q=1 g h=1 (α (h) kq ) m (h) iq , (13)
where Θ = (π, α) are the parameters of the model with π = (π 1 , . . . , π k ) being the proportions and α the vector of the components parameters.

The Rmixmod package5 [START_REF] Biernacki | Model-based cluster and discriminant analysis with the mixmod software[END_REF][START_REF] Lebret | Rmixmod: the r package of the model-based unsupervised, supervised and semi-supervised classification mixmod library[END_REF] is used to achieve our analysis. We employ the default settings to compute the clustering, allowing the selection between 10 parsimonious models according to the Bayesian information Criterion (BIC) [START_REF] Schwarz | Estimating the dimension of a model[END_REF].

Consensus results

Following the previous statements, we believe that using SNMF (Random) solutions could potentially improve the quality of the final partition. While they look unattractive compared to those of SNMF (Skmeans) due to their lower performance (see Table 3 where overall, SNMF (Random) appears to be a bad initialization strategy except for RCV1), these solutions still lead to minima which question is difficult but through our obtained results we can nevertheless make some useful recommendations for the user.

1. First, it is clear that the MMM approach is undoubtedly superior to the CE approach [START_REF] Strehl | Cluster ensembles-a knowledge reuse framework for combining multiple partitions[END_REF] (see Table 3).

2. Between the two approaches Skmeans and Random, the former seems more often better than the latter. This can be due to the diversity it offers; see for example SPORTS and NG20.

3. In the absence of diversity, the MMM approach does not bring improvement whatever the strategy used (Skmeans or Random). In this case combining them (Skmeans & Random) can even degrade the result as is the case with RCV1. Otherwise, with a great diversity of the two strategies one can expect an improvement; this is the case of NG20.

Discussion

In this section, we discuss some directions that we have already investigated since we developed Semantic-NMF. We also discuss some weaknesses and possible improvements of Semantic-NMF.

The orthogonality constraint

The orthogonality constraint on Z is almost always adopted for the clustering task [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF][START_REF] Yoo | Orthogonal nonnegative matrix factorization: Multiplicative updates on stiefel manifolds[END_REF]. With this constraint NMF is equivalent to k-means clustering, and several work empirically demonstrated that such constrain improves the clustering performance of NMF, in most situations. In our case, we found that the orthogonality constraint on Z has only a slight impact on the performances of Semantic-NMF.

Since this constraint adds a little computational overhead, we have chosen not to consider it for efficiency purposes. Note that, introducing the orthogonality constraint into Semantic-NMF is trivial as we only need to replace the update rule of Z (7a) by the one of Orthogonal NMF [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF][START_REF] Yoo | Orthogonal nonnegative matrix factorization: Multiplicative updates on stiefel manifolds[END_REF].

Regularizing document factors using document-document co-occurrences

A natural extension of Semantic-NMF is to regularize the document factors using the document-document co-occurrence information. While such an extension is expected to yield further improvements, our first results show that in some cases adding this regularization declines the clustering performance of Semantic-NMF. We believe that this is might be due to the fact that even the most closely related documents do not necessarily use exactly the same words. We are currently performing further investigations and try to figure out what is causing this issue.

Weaknesses and possible improvements

Although we have shown that Semantic-NMF improves the performances of NMF models by a noticeable amount, Semantic-NMF has two potential weaknesses:

(i) as in most NMF models, the dimensionality, g, of the latent space is the same for both documents and words. For the clustering task, g also denotes the number of clusters. When the latter is small (< 10), this may not be enough to learn high quality word representations that capture finer linguistic regularities and patterns between words. A better alternative, is to make the dimensionality of the word embeddings independent from the number of clusters. This is possible using Non-Negative Matrix Tri-factorization [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF]. (ii) In some situations, when the PPMI matrix, M, is defined deterministically from the local corpus of each dataset-as this is the case in this paper-, Semantic-NMF does not have a clear generative interpretation, which could limit the scope of its use. We can overcome this weakness by using a huge external corpora such as WIKIPEDIA and GOOGLE to build the PPMI matrix. In this case, not only Semantic-NMF has a clear generative interpretation and can be embedded in a well defined probabilistic model [START_REF] Mnih | Probabilistic matrix factorization[END_REF],

but also the PPMI matrix encodes richer and more accurate semantic regularities between words. Leveraging a huge external corpora, such as the aforementioned ones, so as to preserve semantics in NMF, constitutes our main focus for a future extension of Semantic-NMF.

Conclusion

We describe Semantic-NMF, a novel non-negative factorization model which explicitly accounts for the semantic relationships among words. Similar to neural word embedding techniques, our model follows the distributional hypothesis so as to leverage the relationships between words. Formally, Semantic-NMF jointly decomposes the document-word and PPMI word-context matrices, with shared word factors. The intuition behind our approach, is to map words having common meaning roughly to the same direction in the latent space. More interestingly, by capturing more semantics, our model implicitly brings the embeddings of documents which are about the same topic closer to each other, as illustrated in our experiments. This results in document factors that are even better for clustering.

Moreover, we identify in which situations Semantic-NMF does provide the most significant improvements, which allows us to gain further insights into the benefits of leveraging the word relationships.

Overall, our findings suggest that, leveraging the contextual relationships between words, explicitly, makes it possible to preserve more semantics and drastically improve the clustering performance of NMF models. Interestingly, our approach does not require an additional source of data.

Semantic-NMF is a flexible model that can be extended in several directions, which open up good opportunities for future research. For instance, it could benefit from the wide range of regularization schemes already applied to the original NMF. As a concrete example, we believe that it would be very interesting to combine Graph regularized NMF (GNMF), which relies on document manifold regularization, with Semantic-NMF to lead to Semantic-GNMF. We expect such combination to yield further improvements as manifold regularization has proven to be useful for clustering [START_REF] Cai | Graph regularized nonnegative matrix factorization for data representation[END_REF][START_REF] Shang | Graph dual regularization non-negative matrix factorization for co-clustering[END_REF][START_REF] Jing-Yan | Multiple graph regularized nonnegative matrix factorization[END_REF][START_REF] Leng | Adaptive total-variation for non-negative matrix factorization on manifold[END_REF]. On the other hand, the idea of Semantic-NMF could be extended to other variants of NMF. Furthermore, because theoretical connections have been already established between NMF and k-means, spectral clustering, our work could be the building block for Semantic Clustering Models, i.e., clustering models which account for the semantic relationships between words.

where c .. = d j=1 dj

 j=1 =1 c jj , c j. = d j =1 c jj and c .j = d j=1 c jj . The expected value of the PMI across all the possible events is the Mutual Information (MI) that is positive. A null PMI indicates that the events are independent, negative values of PMI indicate that those events occur less frequently than expected. Therefore a useful variation called Positive PMI (PPMI) is to set all negative PMI values to zero. This transformation has been shown to produce good semantic representations[START_REF] John | Extracting semantic representations from word co-occurrence statistics: A computational study[END_REF].

1 and D 2 ,

 2 are cost functions for measuring the divergence between nonnegative matrices, λ is a regularization parameter, and following the nomenclature in neural word embedding, we refer to Q ∈ R d ×g + as the context factor matrix. The above objective function can be viewed as regularizing the word factors in NMF beyond usual regularization schemes (e.g., L 2 norm). Note that, both terms in (4) infer low dimensional representations of words. In the NMF term, word factors encode how words are used in documents, while in the word embedding term, word representations encode word co-occurrence patterns. Semantic-NMF seeks to leverage both of the above information, simultaneously. Additionally, whilst d = d due to M defined as a word-word PPMI matrix, Semantic-NMF can easily accommodate the definition of M as a word embedding matrix where d = d (favorably d ≤ d).Figure 1 provides a graphical illustration of Semantic-NMF.

Figure 1 :

 1 Figure 1: Illustrative scheme of the proposed Semantic-NMF model. X ≈ ZW and M ≈ WQ

Figure 2

 2 Figure 2 and 3 display the behaviors of SNMF w.r.t. the PGLOVE and PPMI matrices respectively. The results are shown in terms of NMI and ARI scores for several values of λ going from 0 to 10 3 . In the case PGLOVE (see Figure 2), the variations of the NMI and ARI scores are unfortunately inconsistent across the range of λ values (see CSTR, RCV1, NG5, SPORTS) making the setting of λ quite

Figure 2 :

 2 Figure 2: Impact of the regularization parameter λ (PGLOVE).

Figure 3 :

 3 Figure 3: Impact of the regularization parameter λ (PPMI).

Figure 4 :

 4 Figure 4: Distribution of cosine similarities between pairs of documents belonging to the same class, computed using the documents' embeddings obtained by NMF and SNMF. The documents of the same class tend to have more similar embeddings under SNMF than NMF.

Figure 5 :

 5 Figure 5: Distribution of cosine similarities between the top 30 words characterizing each document class, computed using the words' embeddings obtained by NMF and SNMF. The top words of the same class tend to have more similar embeddings under SNMF than NMF.

Figure 6 :

 6 Figure 6: Cluster interpretability: Average PMI score. Semantic-NMF leads more interpretable document clusters than NMF.

  in an unsupervised situation, could benefit to other groups of individuals. More specifically, clusters could be different to the ones captured by SNMF (Skmeans) and therefore might bring another source of information to get closer to the actual partition. Our proposition referred to as SNMF (Skmeans & Random) consists in retrieving the 5 top SNMF solutions given by each initialization strategy (Skmeans and Random) and performing a consensus using the ensemble methods defined earlier. For comparison, we also provide a consensus for SNMF (Skmeans) and SNMF (Random) individually. Table3also reports the average performances of the mix of solutions of SNMF (Skmeans & Random). Consensus results obtained with CE and MMM for each strategy are also available.

Figure 7

 7 Figure 7 displays the pairwise NMI and ARI between the top partitions of each strategy: SNMF (Skmeans) denoted "SNMF Sk", SNMF (Random) denoted "SNMF Ra" and SNMF (Skmeans& Random) denoted "SNMF Sk & Ra". This allow us to assess how similar/related the respective partitions of each strategy are among each other. For instance SNMF Sk & Ra will translate how different SNMF (Random) solutions are from SNMF (Skmeans), while SNMF Sk relates how different SNMF (Skmeans solutions) are between each other. The closer we are to 1, the less diversity there is in the set of partitions. Through our experiments, one can wonder what strategy should we use to improve clustering performance ? As we are in an unsupervised context, this

Figure 7 :

 7 Figure 7: Pairwise NMI & ARI averages between the top 10 solutions.

Table 1 :

 1 Description of Datasets, # denotes the cardinality.

	Datasets			Characteristics
		#Documents #Words #Clusters nz X (%) Balance
	CSTR	475	1000	4	3.40	0.399
	CLASSIC4	7095	5896	4	0.59	0.323
	RCV1	6387	16921	4	0.25	0.080
	NG5	4905	10167	5	0.92	0.943
	SPORTS	8580	14870	7	0.86	0.0358
	NG20	18846	14390	20	0.59	0.628

Table 2 ,

 2

summarizes the results of the different methods in terms of NMI and ARI, over all datasets. All the scores are averages considering the 10 best solutions (in terms of criterion) among a set of fifty different trials. As this table clearly

shows, both versions of our model SNMF outperform the other competing methods by an important margin, in most cases. Recalling that SNMF corresponds to NMF

Table 2 :

 2 Mean ± SD of NMI and ARI over different datasets.

	Datasets	Metrics Skmeans	NMF	ONMF	PNMF	GNMF	DCN	SNMF (PGLOVE) SNMF (PPMI)
	CSTR	NMI 0.76±0.00 0.73±0.04 0.65±0.00 0.72±0.04 0.69±0.00 0.63±0.024 ARI 0.80±0.00 0.75±0.10 0.60±0.03 0.73±0.09 0.75±0.02 0.53±0.03	0.76±0.00 0.80±0.00	0.76±0.01 0.80±0.01
	CLASSIC4	NMI 0.60±0.00 0.59±0.00 0.49±0.02 0.51±0.00 0.62±0.00 0.57±0.01 ARI 0.47±0.00 0.47±0.00 0.41±0.01 0.42±0.00 0.45±0.00 0.42±0.01	0.61±0.02 0.47±0.00	0.61±0.03 0.47±0.00
	RCV1	NMI 0.38±0.00 0.38±0.00 0.35±0.00 0.36± 0.00 0.34±0.00 0.34±0.00 ARI 0.18±0.00 0.18±0.00 0.14±0.00 0.16±0.00 0.12±0.00 0.12±0.00	0.51±0.08 0.39±0.15	0.56±0.00 0.45±0.00
	NG5	NMI 0.72±0.02 0.72±0.02 0.52±0.01 0.69± 0.00 0.58±0.04 0.62±0.02 ARI 0.60±0.01 0.60±0.01 0.29±0.00 0.54±0.00 0.50±0.07 0.47±0.02	0.79±0.00 0.76±0.00	0.78±0.00 0.75±0.01
	SPORTS	NMI 0.62±0.02 0.61±0.03 0.55±0.02 0.56±0.00 0.55±0.00 0.59±0.01 ARI 0.40±0.04 0.41±0.04 0.28±0.01 0.28±0.00 0.28±0.00 0.37±0.03	0.62±0.05 0.46±0.07	0.63±0.04 0.48±0.05
	NG20	NMI 0.49±0.02 0.49±0.02 0.38±0.01 0.43±0.03 0.00±0.00 0.43±0.01 ARI 0.30±0.02 0.30±0.02 0.20±0.00 0.22±0.02 0.00±0.00 0.17±0.01	0.49±0.02 0.29±0.01	0.49±0.02 0.33±0.03

  1} n×rg is usually used instead of Λ with value m

	disjunctive matrix M ∈ {0, (h) iq
	where h ∈ 1, . . . , g is a cluster label. Therefore, the data value m (h) iq are assumed to
	be generated from a Multinomial distribution of parameter M(m (h) iq ; α	(h) kq ) where
	α	(h)
			Multinomial mixture ap-
	proach to propose a consensus function. In model-based clustering, it is assumed
	that the data are generated by a mixture of underlying probability distributions,
	where each component k of the mixture represents a cluster.
		Let Λ ∈ N n×r 0	be the data matrix of labels vectors from the top r solutions. Our
	data being categorical, we used a Multinomial Mixture Model (MMM) in order to
	partition the elements λ i . Categorical data being a generalization of binary data;
	assuming a perfect scenario where there is no partition with an empty cluster, a

Table 3 :

 3

	Datasets	Metrics	SNMF (Skmeans)	SNMF (Random)		SNMF (Skmeans & Random)
			Mean±SD	CE	MMM	Mean±SD	CE	MMM	Mean±SD	CE	MMM
	CSTR	NMI ARI	0.76±0.01 0.80±0.01	(0.76) (0.80)	(0.76) (0.80)	0.75±0.00 0.80±0.00	(0.75) (0.80)	(0.75) (0.80)	0.75±0.00 0.80±0.00	(0.75) (0.80)	(0.77) (0.81)
	CLASSIC4	NMI ARI	0.61±0.03 0.47±0.00	(0.60) (0.47)	(0.60) (0.47)	0.54±0.00 0.38±0.00	(0.49) (0.31)	(0.54) (0.38)	0.58±0.05 0.48±0.05	(0.57) (0.40)	(0.65) (0.47)
	RCV1	NMI ARI	0.56±0.00 0.45±0.00	(0.56) (0.45)	(0.56) (0.45)	0.61±0.00 0.63±0.00	(0.51) (0.38)	(0.61) (0.63)	0.59±0.03 0.54±0.04	(0.51) (0.45)	(0.52) (0.45)
	NG5	NMI ARI	0.78±0.00 0.75±0.01	(0.78) (0.75)	(0.78) (0.74)	0.67±0.00 0.64±0.00	(0.67) (0.64)	(0.67) (0.64)	0.73±0.06 0.69±0.06	(0.67) (0.60)	(0.77) (0.79)
	SPORTS	NMI ARI	0.63±0.04 0.48±0.05	(0.63) (0.48)	(0.66) (0.54)	0.43±0.00 0.32±0.00	(0.43) (0.32)	(0.43) (0.32)	0.54±0.12 0.41±0.10	(0.53) (0.40)	(0.57) (0.46)
	NG20	NMI ARI	0.49±0.02 0.33±0.03	(0.50) (0.33)	(0.50) (0.30)	0.47±0.01 0.32±0.02	(0.47) (0.33)	(0.47) (0.33)	0.48±0.02 0.32±0.02	(0.50) (0.34)	(0.52) (0.37)

Mean ± SD of NMI and ARI & consensus over different datasets using CE and the Multinomial Mixture Model (MMM).

In this paper we use " contextual relationships" and "semantic relationships" interchangeably. The former relationships underlie the latter ones, and our objective is to rely on the words' context to capture the semantic relationships among them

http://www.dataminingresearch.com/

http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html

rec.sport.baseball, soc.religion.christian, talk.politics.mideast, sci.electronics and sci.med

https://cran.r-project.org/web/packages/Rmixmod/Rmixmod.pdf


Mireille Fares

Catherine Pelachaud

Nicolas Obin

Transformer Network for Semantically-Aware and Speech-Driven Upper-Face Generation

Keywords: Semantically and Speech Driven Gestures, Transformers, Visual Prosody, Embodied Conversational Agents

We propose a semantically-aware speech driven model to generate expressive and natural upper-facial and head motion for Embodied Conversational Agents (ECA). In this work, we aim to produce natural and continuous head motion and upper-facial gestures synchronized with speech. We propose a model that generates these gestures based on multimodal input features: the first modality is text, and the second one is speech prosody. Our model makes use of Transformers and Convolutions to map the multimodal features that correspond to an utterance to continuous eyebrows and head gestures. We conduct subjective and objective evaluations to validate our approach and compare it with state of the art.

I. INTRODUCTION

A. Context

The human face is a key channel of communication in human-human interaction. During speech, humans spontaneously and continuously display various facial and head gestures that convey a large panel of information to the interlocutors. These gestures are known as "visual prosody" [START_REF] Graf | Visual prosody: facial movements accompanying speech[END_REF]: facial or head movement are produced in conjunction with verbal communication. During speech, the Fundamental Frequency (F0) variations and upper-facial movements are highly correlated [START_REF] Yehia | Linking facial animation, head motion and speech acoustics[END_REF]; they are the results of linguistic and conversational choices. Eyebrow motion can also occur during pauses. Another kinematic-acoustic relation that happens during production of speech is between F0 and head motion [START_REF] Yehia | Linking facial animation, head motion and speech acoustics[END_REF]. Natural and rhythmic head movements are one of the key factors in producing natural animations [START_REF] Ding | Modeling multimodal behaviors from speech prosody[END_REF], [START_REF] Chen | Talking-head generation with rhythmic head motion[END_REF].

B. Related works and our contributions

A large number of head motion generation systems has been proposed in previous works [START_REF] Hofer | Automatic head motion prediction from speech data[END_REF]- [START_REF] Wang | Audio2head: Audio-driven one-shot talking-head generation with natural head motion[END_REF]. A variety of generative statistical models aimed to predict the multimodal behavior of a virtual agent. Hidden Markov Models (HMM) [START_REF] Hofer | Automatic head motion prediction from speech data[END_REF], Recurrent Neural Networks (RNN) [START_REF] Haag | Bidirectional LSTM networks employing stacked bottleneck features for expressive speech-driven head motion synthesis[END_REF], [START_REF] Wang | Audio2head: Audio-driven one-shot talking-head generation with natural head motion[END_REF], and Dynamic Bayesian Networks (DBN) [START_REF] Mariooryad | Generating human-like behaviors using joint, speech-driven models for conversational agents[END_REF], [START_REF] Sadoughi | Speech-driven animation with meaningful behaviors[END_REF] have been used to generate head motion from speech; Generative Adversarial Networks (GAN) have been proposed to produce facial gestures from speech [START_REF] Vougioukas | Realistic speech-driven facial animation with gans[END_REF], [START_REF] Karras | Audio-driven facial animation by joint end-to-end learning of pose and emotion[END_REF]. [START_REF] Kucherenko | Gesticulator: A framework for semanticallyaware speech-driven gesture generation[END_REF] generates continuous 3D hand gestures based on acoustics and semantics. However, most of the aforementioned approaches exploit as input one modality only, namely speech, This work was performed within the Labex SMART (ANR-11-LABX-65) supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02.

and neglect to render their approach using semantic information. Also, most of them focus only on facial expressions while the correlation between facial expressions and head movements are crucial to produce a natural behavior. For instance, [START_REF] Hofer | Automatic head motion prediction from speech data[END_REF]- [START_REF] Lu | Prediction of head motion from speech waveforms with a canonical-correlation-constrained autoencoder[END_REF], [START_REF] Sadoughi | Speech-driven animation with meaningful behaviors[END_REF] do not generate eyebrow motion along with head motion, which are both correlated to F0 [START_REF] Yehia | Linking facial animation, head motion and speech acoustics[END_REF], and therefore are correlated to each other. On the other hand, transformer networks and attention mechanisms have been recently proved to be very efficient for sequence-to-sequence modelling, with particular advances for modelling multimodal processes. For instance, Transformers were previously used for translating speech to text (ASR) [START_REF] Hrinchuk | Correction of automatic speech recognition with transformer sequence-to-sequence model[END_REF], [START_REF] Mohamed | Transformers with convolutional context for asr[END_REF], and multimodal learning of images based on text [START_REF] Yao | Multimodal transformer for multimodal machine translation[END_REF]. To overcome those limitations, we propose a novel approach for upper-facial and head gestures generation based on a multimodal transformer network. Our contributions can be listed as follows: 1) a transformer network operating on multi-modal input text and speech information in order to generate upper-facial and head movements, and 2) a cross-attention module that can efficiently exploit semantic and speech information. 1 The paper is organised as follows. The next section describes the proposed architecture of our model and its multimodal features. Then our objective and subjective evaluation experiments are presented including the LSTM-based Baseline Model. We finally discuss our results.

II. PROPOSED ARCHITECTURE

A. Multimodal Input/Output Features

The upper-facial movements and head rotations are represented by mean of Action Units (AUs) as defined in the Facial Action Coding Systems (FACS) [START_REF] Ekman | What the face reveals: Basic and applied studies of spontaneous expression using the Facial Action Coding System (FACS)[END_REF] and 3D head angles. The work presented in this paper only considers the AUs that represent eyebrows movements which are: inner raise eyebrow AU1, outer raise eyebrow AU2, frown AU4, upper lid raiser AU5, cheek raiser AU6, and lid tightener AU7. Head rotations have three degrees of freedom, represented by the Euler angles roll, pitch and yaw. They are represented by RX, RY and RZ which are the rotation of the head with respect to the X, Y and Z axes. In this paper, F0 values were extracted from the speech signal at a 5ms audio frame rate, linearly interpolated between unvoiced segments, and clipped to the range of 50 to 550Hz which represents the F0 range of human speech. Since F0, AU intensities (AU) and head rotations (R) are continuous, they were quantized to produce a finite set of discrete values to reduce the model size and energy consumption [START_REF] Guo | A survey on methods and theories of quantized neural networks[END_REF]. Finally, BERT word embeddings were extracted from the text transcription. The proposed architecture aims at mapping multimodal speech and text feature sequence into continuous facial and head gestures. This problem is treated as a multimodal sequence-to-sequence problem, for which a transformer network operating at the word level is presented as illustrated in Fig. 1 (a). The inputs and outputs of the transformer network consist of one feature vector for each word W of the input text sequence. The input text corresponds to an Inter-Pausal Unit (IPU) which is a sequence of words separated by silent pauses longer than 0.2 seconds. F0 input sequence as well as AU intensities AU and head rotations R output sequences have a variable length. We set the maximum F0 input sequence length to 100, and the maximum AU/R output length to 124. Shorter sequences were padded to the maximum length, and longer ones were truncated. In order to handle continuous flow of input and output information with different timing, the transformer is wrapped with a F0 encoder module at its input and to a AU/R decoder at its output. The objective of the F0 encoder is to encode the continuous F0-values at the word level and the objective of the AU/R decoder is to reconstruct the continuous values for AU and R from a word-level encoding. Each spoken word W is represented by a word-level F0 embedding vector X

(1) W which at its turn corresponds to the sequence of F0values X (1) = (F 0 1 , . . . , F 0 N W ), where N W is the number of F0-values corresponding to the spoken word W; and X

(2) W is the BERT word embedding vector corresponding to the spoken word W -including silences. Silences less than 0.2 secs may belong to IPUs. They do not have a contextual BERT embedding. Hence, we replaced them by a comma -",". Each spoken word W is also represented by a word-level AU vector Y

(j) W,AU (resp. R vector Y (j) W,R
) which in turn corresponds to the sequence of values dY

(j) AU = (AU (j) 1 , . . . , AU (j) N ′ W ) (resp. Y (j) R = (R (j) 1 , . . . , R (j) N ′ W
)) where j denotes the j th AU/R and N ′ W the number AU/R-values corresponding to the word W. F0 Encoder: As depicted in Fig. 1 (a), for each W, three one-dimensional convolutional layers are applied to project the input F0 sequence X W is then fed as an input to the Transformer Encoder.

Transformer Encoder: The transformer encoder architecture is depicted in Fig. 1 (b); it is similar to the one proposed in [START_REF] Vaswani | Attention is all you need[END_REF]. In our work, it is composed of a stack of N = 4 identical layers. Each layer has two sub-layers: the first one is a multihead self attention mechanism with 4 attention heads, and the second one is a position-wise fully connected feed-forward network. As the original transformer encoder, we employ a residual connection around each of the 2 sub-layers, followed by layer normalization.

Cross-Modality Attention Module (CMAM): The output of the transformer encoder Z, as well as X

(2)

W are fed as inputs to the Cross-Modality Attention Module (see Fig. 1 (a)). This Module has the same structure as the Transformer Decoder in [START_REF] Vaswani | Attention is all you need[END_REF]. It generates a representation that can take into account both modalities, text and speech. The representation learning is done in a master/slave manner, where one modality -the master -is used to highlight the extracted features in the other modality -the slave. This module takes X

(2) W -Text Modality -as master, and Z -Speech Modality -as slave. Thus, it performs cross-attention such that the attention mask is derived from text modality, and is harnessed to leverage the latent features from the speech modality.

Transformer Decoder: The decoder is composed of N = 4 identical decoding layers, with 4 attention heads. Similar to the one proposed in [START_REF] Vaswani | Attention is all you need[END_REF], it is composed of residual connections applied around each of the sub-layers, followed by layer normalization. As depicted in Fig. 1 (c), the self-attention sublayer in the decoder stack is modified to prevent positions from attending to subsequent positions. The output predictions which are offset by one position, and this masking ensure that the predictions for position index j depend only on the known outputs at positions less than j. We use 6 Transformer Decoders, one for each AU/R. For simplicity, Fig. 1 (a) only illustrates one decoder. AU/R decoder: As depicted in Fig. 1 (a), the Transformer Decoder outputs are concatenated together, then fed to 3 onedimensional convolutional layers that include 64 filters, with a kernel size equal to 3, to learn the correlation between the 6 output features, and therefore the correlation between facial and head movements. Finally, a Dense layer with a Softmax activation function is applied on each of the outputs, to convert the outputs to predicted next-token probabilities. The final output sequences are Y AU and Y R .

Transformer Sub-Layers and Hyperparameters: the transformer encoder and decoders have attention sub-layers, and contain fully connected feed-forward networks which are applied to each position separately and identically. Similarly to other sequence to sequence models, we use learned embeddings to convert the input tokens and output tokens to vectors of dimension d model = 64. All sub-layers and embedding layers therefore use this dimension. The inner feed-forward layers are of dimension d f f = 400. Positional encodings are applied to the inputs of the transformer encoder and decoders. They have the same dimension as the embeddings, so that they can be added together. We use sine and cosine functions, similar to [START_REF] Vaswani | Attention is all you need[END_REF].

III. EXPERIMENTS A. Material and Experimental Setups

We trained it on a subset of the TED dataset collected in [START_REF] Fares | Towards multimodal human-like characteristics and expressive visual prosody in virtual agents[END_REF], containing preprocessed AUs/R, F0s, and BERT embeddings of filtered shots where speakers' face and head are visible and close to the camera. Our subset consists of the features of 200 videos. Videos vary between 2 and 25 minutes, with a frame rate of 24 FPS, the total numbers of IPUs is 919, and of words is 62307. We shuffled all the IPUs, then split them into: training set (80%), validation set (10%) and test set (10%). There are two test conditions: SD (Speaker Dependent) and SI (Speaker Independent). The SD condition aims to assess to what extent the model can generalize on new sentences pronounced by a speaker seen during training -training set included multiple speakers. The SI condition aims to assess the extent to which gestures predictions can be extrapolated to unseen speakers. Each training batch contained 128 pairs of word embeddings, F0 sequences, and their corresponding AUs, RX, RY and RZ. The loss function used is the categorical cross-entropy between predicted and actual values. We used Adam optimizer with β 1 = 0.9, β 2 = 0.98 and ϵ = 10 9 . We used a learning rate scheduler as in [START_REF] Vaswani | Attention is all you need[END_REF], with warmup steps = 4000. We applied a dropout = 0.1 to the output of each sub-layer of the transformer, and to the sums of the positional encodings in the Transformer encoder and decoder stacks. All features values were normalized between 0 and 1. The total number of the model's parameters is 2051133.

B. Objective Evaluation

To assess the quality of the generated gestures, we used the following measures: Root Mean Squared Error (RMSE), Pearson Correlation Coefficient (PCC), Activity Hit Ratio (AHR) and Non-Activity Hit Ratio (NAHR). AHR and NAHR were proposed by Freeman et al. [START_REF] Ong | Real-time robust voice activity detection using the upper envelope weighted entropy measure and the dual-rate adaptive nonlinear filter[END_REF], to evaluate the performance of Voice Activity Detector (VAD) systems. We also considered them since evaluating AU activity looks similar to VAD evaluation. We considered an AU as "Activated" when its value is greater than 0.5, otherwise it is "Not-Activated". AHR is the percentage of predicted AU activation with respect to ground truth. If it is greater than 100%, it means that the model is predicting more activation than the amount of activation that is in the ground truth. NAHR is the same but for non-activity. We assessed the full model using the SD test set. We additionally evaluated its capacity to generalize on the SI set. To evaluate the different parts of our architecture, we conducted an ablation study as follows:

(1) speech ablation, (2) text ablation, (3) CMAM ablation, and (4) AU/R decoder ablation. The ablation study was evaluated using RMSE metric.

C. Comparing to LSTM-based Baseline Model

We compared our approach to a sequence to sequence LSTM-based model [START_REF] Fares | Towards multimodal human-like characteristics and expressive visual prosody in virtual agents[END_REF] to predict upper-face movements based on speech and text. This LSTM model [START_REF] Fares | Towards multimodal human-like characteristics and expressive visual prosody in virtual agents[END_REF] was developed only for predicting eyebrows movements (AUs). We extended it to include head movements (R). This extended model consists of mapping sequences of F0 and the Bert embedding that correspond to a Word (W), to the sequences of (AUs/R) of that corresponding W. It employs 2 layers of Bidirectional LSTMs to encode the concatenation of wordlevel F0 contours and Bert embeddings. The hidden internal states are then transmitted to 6 decoders to produce the corresponding AUs and R for a given input. The decoders are followed by Dense Layers with Softmax Activation. The hyperparameters of the extended LSTM model are as follows: in both encoder and decoders, the first layer of bidirectional LSTM has 200 units, and the second one has 100 units. The activation function used in these layers is LeakyReLU with alpha = 0.01. We trained and tested this model using the same training, validation and test sets described in Section III -A. We trained it on 300 epochs, using a batch size = 128. We used Root Mean Squared Propagation (RMSProp) optimizer, and Categorical Cross Entropy Loss. We used the same metrics described in III.B to compare this SOTA Baseline model to our Transformer-based model.

D. Subjective Evaluation

To investigate human perception of the facial gestures produced by our model, we conducted two different experimental studies using the virtual agent Greta [START_REF] Pelachaud | Greta: a conversing socio-emotional agent[END_REF]. We followed the recommendations proposed in [START_REF] Wolfert | A review of evaluation practices of gesture generation in embodied conversational agents[END_REF], by adapting them to facial gesture generation and assessed the naturalness, coherence, and human-likeness of the virtual agent's gestures. Since we are not evaluating deictic and iconic gestures, we did not use the metrics appropriateness, and intelligibility as proposed in [START_REF] Wolfert | A review of evaluation practices of gesture generation in embodied conversational agents[END_REF]. We added the metrics synchronization, and alignment to evaluate the gestures' temporal property with speech.

Participants in both studies were fluent in English, with a University degree, and recruited on Prolific, a crowd sourcing website. We added attention checks at the beginning of our perceptual evaluations, to filter out inattentive participants.

The first study was done by 35 participants, and consisted of presenting 16 videos: each video showed the virtual agent saying a sequence of words that corresponds to a sequence of IPUs. We considered 4 conditions: 4 videos (condition M) used our full model of SD gestures predictions; 4 videos (condition GT) were simulated using the gestures extracted from TED videos, which serve as ground truth; 4 videos of the virtual agent were simulated using the LSTM-based Baseline model of SD predictions (condition SOTA). The remaining 4 videos were produced using predicted gesture animation of IPUs with the sound of other IPUs (condition E). The second study was conducted by 55 participants. The goal of the second study was to evaluate our model when simulated with SI data, and therefore its capability to generalise to new speakers. It included 8 videos: 4 were simulated with our model's SI predictions, and 4 using SI gestures extracted from SI set (described in III.A), which serve as ground truth. For each video in both studies, participants were asked to rate the 5 factors, namely naturalness, coherence, human-likeness, synchronization, and alignment of the virtual agent's gestures on a 1 to 7 likert scale [START_REF] Wolfert | A review of evaluation practices of gesture generation in embodied conversational agents[END_REF]. The questions were listed in a random order. The agent's mouth movements were blurred to prevent participants from getting distracted by these gestures which were not inferred by our model, and therefore focus on the model's generated gestures.

IV. RESULTS AND DISCUSSION Table I reports the model's as well as the SOTA's objective evaluation results using the same SD test set. Results reveal that RMSE errors are much smaller for M (0.0229 ≤error≤ 0.3) than SOTA (0.2046 ≤error≤0.9786). On the other hand, PCC coefficients show that M's predictions (0.94≤PCC≤1.0) are more correlated than SOTA's predictions (-0.0525≤PCC≤0.0179) to GT. AHR and NAHR were calculated to measure the activation of AUs only, since they are not applicable for R. Results show that M predicts better the activation rate AHR (AHR≥98.0) than SOTA (20.211≤AHR≤60.314). The non-activation rate is higher for SOTA (107.084≤NAHR≤135.95) than for M(100≤NAHR≤130). This constitutes objective validation that M gives better results than SOTA in terms of error, correlation, and AU's activation rate. Ablation studies conducted on our model resulted in higher RMSE errors when performing Speech and Text Ablation for some AUs/R. For instance, AU01 RMSE error (0.0819 for full model) increased to 0.0836 with text ablation and to 0.09 with speech ablation. On the contrary, RZ RMSE score (0.3036 for full model) increased to 0.3089 with text ablation, and 0.3111 with speech ablation. AU/R Decoder ablation resulted in even higher RMSE errors especially for head rotations. AUs and R RMSE scores increased after CMAM ablation (i.e. AU01 RMSE increased to 0.0901). This constitutes objective validation that the use of multi-modal inputs (speech and text modalities) in M improves predictions. Thus we can also conclude that CMAM module is an efficient and a key component of our model, as it improves the generation accuracy of face gestures and head rotations. As mentioned previously, we also tested our model on the SI set. RMSE errors are between 0.301 and 0.89 for AUs, and between 0.25 and 0.93 for R. As we could expect, we got higher errors than the errors we had for the SD condition (Table I) since the speakers in SI set were not seen by our model during the training phase.

For our first perceptive study conducted on SD data, Fig. 2 (a) shows the mean scores obtained on the 5 factors for the 4 conditions: our model M, the baseline SOTA, the ground truth GT, and the error E. For the 5 factors, M is perceived as much closer to GT than SOTA and E, especially in terms of Alignment and Synchronization between speech and gestures. The mean difference between M and GT is 0.72 for Alignment and 0.74 for Synchronization (Fig. 2 (a)). SOTA is perceived as the closest to E especially in terms of Coherence, and Alignment: the mean difference is 0.4 and 0.44 respectively (Fig. 2 (a)). We also conducted ANOVA Between-Subjects to test whether there are significant differences between the 4 conditions along all the 5 factors. Results showed that for all factors, tests were significant (p<0.001). We additionally performed a post-hoc Fisher's LSD Test to do pair-wise comparisons of the means between the factors of all conditions. Significant results (p<0.001) were found for all the factors when comparing the condition GT with the 3 other conditions and when comparing our model M with SOTA and E. In particular, there were significant differences between M and SOTA in terms of the 5 factors (p<0.007). This constitutes experimental validation that when used with SD data, condition M is perceived significantly better than SOTA and E for all the factors. The difference for the 5 factors between M and GT is not significant. For our second perceptive study conducted on SI data, Fig. 2 (b) shows the means scores obtained on all factors for conditions M and GT: for the 5 factors M is perceived as close to GT. As our data were not normally distributed (Shapiro test's p<0.5), we conducted a post-hoc unpaired Wilcoxon test on each factor for the two conditions. For all tests, we could not find significant differences (p>0.05). Thus our model when used with SI data and GT received similar values for the 5 factors.

V. CONCLUSION

We have presented a new approach for modelling upper facial and head gestures using Transformer model. We conducted objective and subjective evaluations that showed that our model produces animations that are close to the ground truth in term of expressivity while ensuring that speech and computed gestures are aligned and synchronized. In a next future, we plan to expand our model to learn different speaker styles for gesture generation.

Fig. 1 :

 1 Fig. 1: Face Gesture Generation Model Architecture B. Face Gesture Generation Model Architecture

( 1 )

 1 W into a word-level representation of F0 contours covering local context of F0 variations. These convolutional layers include 64 filters, with a kernel size equal to 3. The generated output vector of the latter layers X[START_REF] Graf | Visual prosody: facial movements accompanying speech[END_REF]

Fig. 2 :

 2 Fig. 2: Subjective Evaluation Results

TABLE I :

 I Objective Evaluation: comparison of proposed transformer model vs. SOTA baseline model