Damien Bouvier

Nicolas Obin

Marco Liuni

Axel Roebel

A SOURCE/FILTER MODEL WITH ADAPTIVE CONSTRAINTS FOR NMF-BASED SPEECH SEPARATION

Keywords: speech separation, non-negative matrix factorization, source/filter model, constraints

This paper introduces a constrained source/filter model for semisupervised speech separation based on non-negative matrix factorization (NMF). The objective is to inform NMF with prior knowledge about speech, providing a physically meaningful speech separation. To do so, a source/filter model (indicated as Instantaneous Mixture Model or IMM) is integrated in the NMF. Furthermore, constraints are added to the IMM-NMF, in order to control the NMF behaviour during separation, and to enforce its physical meaning. In particular, a speech specific constraint -based on the source/filter coherence of speech -and a method for the automatic adaptation of constraints' weights during separation are presented. Also, the proposed source/filter model is semi-supervised: during training, one filter basis is estimated for each phoneme of a speaker; during separation, the estimated filter bases are then used in the constrained source/filter model. An experimental evaluation for speech separation was conducted on the TIMIT speakers database mixed with various environmental background noises from the QUT-NOISE database. This evaluation showed that the use of adaptive constraints increases the performance of the source/filter model for speaker-dependent speech separation, and compares favorably to fully-supervised speech separation.

INTRODUCTION

Speech separation consists in the separation of a speech signal from a background environment, referred as noise, which is defined as everything but the speaker of interest (i.e., environmental sounds such as background non-speech sounds or background speech). Speech separation is essential for further speech processing in real speech technologies, such as speech recognition, speaker recognition, speaker localization, and audio multi-media technologies for speech extraction and remixing. Audio source separation methods have been recently introduced for speech separation, in which the audio signal is described as the sum of two sources: a speech signal and a background noise signal. In particular, the non-negative matrix factorization (NMF) of an audio signal is extremely popular for source separation, and is widely used in recent times for speech separation [1,2,3,4,5,[START_REF] Magoarou | Text-informed audio source separation. Example-based approach using nonnegative matrix partial co-factorization[END_REF]. In the original formulation, the NMF decomposition of an audio signal is strictly unsupervised [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF]. In the last decade, audio and speech separation has massively converged to informed audio source separation, in order to provide prior knowledge about the audio sources to be separated [START_REF] Liutkus | An overview of informed audio source separation[END_REF]. In the context of speech separation, two main trends co-exist: semi-supervised speech separation uses prior knowledge about speech only [5,[START_REF] Magoarou | Text-informed audio source separation. Example-based approach using nonnegative matrix partial co-factorization[END_REF], and supervised speech separation adds prior knowledge about the background environment [3,[START_REF] Virtanen | Active-set newton algorithm for non-negative sparse coding of audio[END_REF]. This latter case remains extremely limited when the background environment is unknown, which is the case of most real-world applications.

In this context, semi-supervised speech separation is the most common approach. The main advantage of semi-supervised speech separations is that robust prior knowledge about speech can be exploited, while the integration of prior knowledge about the background environment is clearly not realistic, regarding the extreme variability of the background environment. For semi-supervised speech separation, the experience into speech processing and speech recognition can be exploited: a source/filter model can be used to inform NMF-based separation [1,2]. Also, a universal speech model (USM) has been proposed for speaker-independent speech separation [3], in which a speaker can be represented by a combination of the most similar speakers bases. A real-time implementation of the USM has been recently proposed for on-line background noise estimation [4]. Furthermore, hidden Markov models (HMM) has been added to NMF speech separation, in order to construct a language model [5] and to use prior text information for speech separation [START_REF] Magoarou | Text-informed audio source separation. Example-based approach using nonnegative matrix partial co-factorization[END_REF]. Finally, deep neural networks (DNN) has been successfully introduced for speech separation [START_REF] Wang | A Neural Network For Time-Domain Signal Reconstruction: Towards Improving The Perceptual Quality Of Supervised Speech Separation[END_REF], and deep-NMF [START_REF] Le Roux | Deep NMF for speech separation[END_REF] has been proposed in order to integrate the advantages of DNN within the NMF framework.

In this paper, we propose a constrained source/filter model for semi-supervised and physically-motivated NMF-based speech separation. To do so, a source/filter NMF model is described in Section 2. Then, constraints are added to this model in Section 3, in which a specific speech constraint and a method for the automatic adaptation of the constraints' weights during separation are proposed. An experiment is conducted in Section 4 in order to explore the use of constraints within the source/filter model, with comparison to stateof-the-art speech separation methods.

NMF AND SOURCE/FILTER MODEL

NMF principle

Let V denotes our observation matrix, with only non-negative coefficients (for audio, usually the STFT magnitude of the observed mixture signal); the NMF consists of finding the best approximation given a chosen cost C:

V W H (1)
where W and H also contains only non-negative coefficients. W represents a dictionary matrix and H is the activation matrix (it can be seen as the gains of the projection of V onto the space defined by W ). Afterwards, source separation can be made using Wiener filters [START_REF] Benaroya | Audio source separation with a single sensor[END_REF].

ité des filtres, chaque base du dictionnaire des filtres est représenté comme une combi-linéaire de filtres élémentaires venant d'un banc de filtre. La

Autres méthodes de séparation de parole

r pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref if des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques n'est pas la seule intégration du modèle source/filtre dans la NMF ; on peut citer par exemple les travaux en et Klapuri [START_REF] Benaroya | Audio source separation with a single sensor[END_REF] qui proposent une nouvelle factorisation où chaque base spectrale est décomposée en it d'un spectre d'amplitude d'une excitation harmonique par celui d'un filtre.

Bouvier

M2 ATIAM -Rapport de Stage

Chapitre 3

Évaluation expériment

Dans ce chapitre, nous évaluons les di érents algorithmes p de la parole dans un environnement bruité.

H H ex V ƒ (W ex H ex ) ¢ ! W U H " + ! W N H N " V ƒ W ex H ex ¢ W U H + W N H N V ƒ W U H ) W , U * ) W ex , H ex , W , U , H , W N , H N *

Bases de données

Afin d'évaluer la tâche proposé, nous avons construit un paroles bruitées. Pour cela, nous avons utilisé comme base de de bruit celle utilisé pour la construction de QUT-NOISE-TI TIMIT est une base de parole comprenant 3600 phrases teurs di érents. Chaque locuteur a enregistré 10 phrases, don 2 phrases exposent toutes les variantes de prononciations des d'apprentissage. Les autres phrases servent de base de test. QUT-NOISE-TIMIT contient des enregistrements longue dur nores (cuisine, rue, café, intérieur d'une voiture, ...). Lorsqu bruit est fait sur les 5 premières minutes du fichier.

Notre base de test est construite de la manière suivante :

• nous avons sélectionné 20 locuteurs, 10 de chaque sexe ; 16 source/filtre de la voix et de son intégration dans le modèle de la NMF ; enfin nous dressons un tableau (non succinct) des di érentes méthodes de séparation de parole, en se concentrant principalement sur les méthodes utilisant la NMF.

La factorisation en matrices non-négatives

Le principe de la NMF, introduit tout d'abord par Paatero et Tapper [1] et popularisé par Lee et Seung [2], est d'approcher une matrice V de taille F ◊ N à coe cients positifs ou nuls par

V ƒ = W H (1.1)
où W et H sont deux matrices à coe cients positifs ou nuls, de taille respective F ◊K et K ◊N .

La NMF revient donc à chercher, pour un K préalablement choisi, la meilleure matrice approchée de rang maximum K, selon une fonction de coût choisie ; chaque colonne de la matrice W est une base de la décomposition de , et H correspond à l'encodage de selon cette décomposition. L'idée principale des NMF est la contrainte de positivité des matrices, qui oblige l'estimation des données à se faire de manière additive, de sorte que l'annulation entre bases de W n'est pas possible (contrairement à l'analyse en composantes principales).

En audio, la matrice V est une représentation temps-fréquence du signal à analyser, le plus souvent la Transformée de Fourier à Court-Terme (TFCT) ou la transformée à Q-constant. Puisque l'on nécessite des coe cients positifs ou nuls, la matrice considérée est une puissance positive de l'amplitude, e.g. dans le cas de la STFT :

V fn = |TFCT{x} fn | -, -> 0 (1.2)
Dans ce cadre là, W est un dictionnaire des sources sonores, chaque colonne étant un spectre de puissance -, et H représente les activations temporelles de ces sources.

Fonctions de coût

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N " ( 1

Autres méthodes de séparation de parole

Autres méthodes de séparation de

Pour pouvoir mieux situer nos travaux par rapport à la littéra descriptif des di érents algorithmes de séparation de la parole, en Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical po le fond sonore pour nous) est représenté en utilisant le décomposition classiqu modèle obtenu s'écrit :

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N "

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dr descriptif des di érents algorithmes de séparation de la parole, en se focalisant

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N où

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nou descriptif des di érents algorithmes de séparation de la parole, en se focalisa 4. Ce n'est pas la seule intégration du modèle source/filtre dans la NMF ; on peut citer de Virtanen et Klapuri [START_REF] Benaroya | Audio source separation with a single sensor[END_REF] Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9 décrites en Annexe A.2.

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici u descriptif des di érents algorithmes de séparation de la parole, en se focalisant sur les tech

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N " où les matrices H ex , H et H N représentent respectivement les activations tempore Damien Bouvier 8 M2 ATIAM -Rapport d
semi-supervised one where we can inject knowledge about speech (physical model, speaker information, textual information, ...) but use no priors on the noise type.

In this paper, our goal is to give a physical meaning (interpretation?) to the NMF for speech separation. We used an informed semi-supervized NMF in order to perform a speaker-dependent speech separation task. The main contribution of this article is the formalization of a speech-specific constraint in pre-existing source/filter model for NMF-based speech separation.

The paper is organized as follows: first, we will describe the inclusion of the source/filter model in the NMF framework; then we will explain the structure of our algorithm and particularly the developed constraint; afterwards, we will describe our experimental setup, and finally we will discuss the results.

NMF AND SOURCE/FILTER MODEL

NMF principle

Let V denotes our observation matrix, with only non-negative coefficients (for audio, usually the STFT magnitude of the observed mixture); the NMF consists of finding the best approximation:

V ' W H (1)
given a cost C, where W and H also contains non-negative coefficients. W represent a dictionary matrix and H is the activation where ⇥ represents either W and H, ⌦ denotes the Hadamard product and the division is pointwise.

A source/filter-NMF for speech

In order to refine the representation of the speech, we used the source/filter model for NMF proposed in [START_REF] Benaroya | Audio source separation with a single sensor[END_REF], and we integrated a learning step for the vocal filters. If V is a STFT magnitude of a speech signal, we can modeled it as follows:

V = V ex ⌦ V ' (W ex H ex ) | {z } excitation ⌦ ⇣ c W H ⌘ | {z } excitation (4)
where V ex and V are respectively the amplitude spectrogram of the excitation part and source filter part, W ex and H ex the basic NMF decomposition (approximation?) for V ex , and c W and H the basic NMF decomposition (approximation?) for V . In order to impose smoothness on the filter spectrum, we decompose c W as the product W U , where W is a dictionary of smooth "atomic" filters and U is the coefficient matrix combining those elementary filters to form a vocal filter. Fig. 1 shows an example of the overall source/filter model for NMF.

V ' (W ex H ex ) ⌦ ⇣ W U H ⌘ + W N H N (5)
Chapitre 3

Évaluation expérimentale

Dans ce chapitre, nous évaluons les di érents algorithmes proposés sur une tâche de séparation de la parole dans un environnement bruité. Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont décrites en Annexe A.2.

H H ex V ƒ (W ex H ex ) ¢ ! W U H " + ! W N H N " V ƒ W ex H ex ¢ W U H + W N H N V ƒ W U H ) W , U * ) W ex , H ex , W , U , H , W N , H N *

Bases de données

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref descriptif des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont décrites en Annexe A.2.

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref descriptif des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont décrites en Annexe A.2.

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N " (1.

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref descriptif des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont décrites en Annexe A.2.

Autres méthodes de séparation de parole

Pour pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref descriptif des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques

= ex ¢ + N = (W ex H ex ) ¢ ! W U H " + ! W N H N " (1.11)
Damien Bouvier 8 M2 ATIAM -Rapport de Stage tation?) to the NMF for speech separation. We used an informed semi-supervized NMF in order to perform a speaker-dependent speech separation task. The main contribution of this article is the formalization of a speech-specific constraint in pre-existing source/filter model for NMF-based speech separation.

The paper is organized as follows: first, we will describe the inclusion of the source/filter model in the NMF framework; then we will explain the structure of our algorithm and particularly the developed constraint; afterwards, we will describe our experimental setup, and finally we will discuss the results.

NMF AND SOURCE/FILTER MODEL

NMF principle

Let V denotes our observation matrix, with only non-negative coefficients (for audio, usually the STFT magnitude of the observed mixture); the NMF consists of finding the best approximation:

V ' W H (1)
where W and H also contains non-negative coefficients, given a cost D(V |W H). W represent a dictionary matrix and H is the activation matrix containing the gains of the basis in W .

A source/filter-NMF for speech

Speech can be modelized using a source/filter model, with a glottal excitation convoluted by the vocal tract. So it is easy to see that in order to fully represent all potential speech signals, we will need very large dictionaries, and so loose the rank-reduction advantage of the NMF. In order to get around this problem, we used the Instant Mixture Model (IMM) proposed for the NMF in [5] :

V = V ex ⌦ V ' (W ex H ex ) | {z } excitation ⌦ ⇣ c W H ⌘ | {z } excitation ' (W ex H ex ) ⌦ W U H (5)
where V ex and V are respectively the amplitude spectrogram of the excitation part and source filter part, W ex and H ex the basic NMF decomposition (approximation?) for V ex , and V decomposition is as follows: H is the activation matrix of the filter basis, W is a dictionary of smooth "atomic" filters and U is the coefficient matrix combining those elementary filters into the filter basis.

In [5], the authors imposed and fixed W ex and W , letting all others matrices free; we kept the same construction methods, with the addition of a learning step for U . For W ex , the excitation dictionary, we incorporated voiced and unvoiced basis.

?) to the NMF for speech separation. We used an informed supervized NMF in order to perform a speaker-dependent h separation task. The main contribution of this article is rmalization of a speech-specific constraint in pre-existing /filter model for NMF-based speech separation. he paper is organized as follows: first, we will describe the ion of the source/filter model in the NMF framework; then ill explain the structure of our algorithm and particularly the ped constraint; afterwards, we will describe our experimental and finally we will discuss the results.

NMF AND SOURCE/FILTER MODEL MF principle

denotes our observation matrix, with only non-negative conts (for audio, usually the STFT magnitude of the observed re); the NMF consists of finding the best approximation:

V ' W H (1)
W and H also contains non-negative coefficients, given a (V |W H). W represent a dictionary matrix and H is the tion matrix containing the gains of the basis in W .

A source/filter-NMF for speech

Speech can be modelized using a source/filter model, with a glottal excitation convoluted by the vocal tract. So it is easy to see that in order to fully represent all potential speech signals, we will need very large dictionaries, and so loose the rank-reduction advantage of the NMF. In order to get around this problem, we used the Instant Mixture Model (IMM) proposed for the NMF in [5] :

V = V ex ⌦ V ' (W ex H ex ) | {z } excitation ⌦ ⇣ c W H ⌘ | {z } excitation ' (W ex H ex ) ⌦ W U H (5)
where V ex and V are respectively the amplitude spectrogram of the excitation part and source filter part, W ex and H ex the basic NMF decomposition (approximation?) for V ex , and V decomposition is as follows: H is the activation matrix of the filter basis, W is a dictionary of smooth "atomic" filters and U is the coefficient matrix combining those elementary filters into the filter basis.

In [5], the authors imposed and fixed W ex and W , letting all others matrices free; we kept the same construction methods, with the addition of a learning step for U . For W ex , the excitation dictionary, we incorporated voiced and unvoiced basis. In audio, usual costs are Kullback-Leiber (KL) and Itakura-Saito (IS) divergence [START_REF] Févotte | Algorithms for nonnegative matrix factorization with the β-divergence[END_REF], which are both limit cases of the β-divergence (respectively for β = 1 and β = 0). In this paper, we use the IS divergence for its scale-invariance, which is an interesting property for audio signals:

C = DIS (V |W H) = F f N n dIS V f n | (W H) f n (2)
with dIS(x|y) = x ylog x y -1. Moreover, we use the artificial noise floor introduced in [START_REF] Roebel | On automatic drum transcription using non-negative matrix deconvolution and Itakura-Saito divergence[END_REF] in order to control the noise robustness of the IS-NMF.

The solution of the NMF problem, using β-divergence, can be efficiently obtained by applying an iterative algorithm, derived from a gradient step descent technique [START_REF] Févotte | Algorithms for nonnegative matrix factorization with the β-divergence[END_REF]. The i-th iteration is based on the application, on both W and H, of the following multiplicative rule:

Θ (i+1) ←-Θ (i) ⊗ ∇ - Θ (i) C ∇ + Θ (i) C (3)
where Θ represents either W or H, ∇ + Θ (i) and∇ - Θ (i) are the positive and negative parts of the gradient of the cost C with respect to Θ (i) , ⊗ denotes the Hadamard product, and the division is pointwise.

A source/filter-NMF for speech

In order to provide an explicit representation of speech, we use the source/filter model for NMF proposed in [2], in which a training step is added to estimate the vocal filters. The NMF source/filter decomposition of the STFT magnitude V S of a speech signal can be expressed as:

V S = V ex ⊗ V Φ (W ex H ex ) excitation ⊗ W Φ H Φ filter ( 4
)
where V ex and V Φ are respectively the magnitude STFT of the excitation part and the filter part, W ex and H ex are the standard NMF decomposition for the speech excitations V ex (where W ex is a fixed dictionary, including periodic and noisy basis), and W Φ and H Φ are the standard NMF decomposition for the speech filters V Φ . In order to ensure the smoothness of the speech filters W Φ , we further decompose W Φ as the product W Φ U Φ , where W Φ is a fixed dictionary of smooth "atomic" filters (here, Hann windows) and U Φ is the coefficient matrix linearly combining those elementary filters to form a speech filter. Figure 1 illustrates the architecture of the source/filter model for NMF.

For speech separation, the observed signal V is assumed to be a mixture of a speech signal V S and a background noise signal V N . V can be approximated by V as follows:

V V = W ex H ex ⊗ W Φ U Φ H Φ + W N H N (5)
in which the background noise signal V N is expressed using a standard NMF decomposition. Following the denomination used in [2], we will refer to this mixture decomposition as the "Instantaneous Mixture Model for NMF" (IMM-NMF).

Semi-supervision of the IMM-NMF

In the IMM-NMF, the speech filters W Φ of a speaker are explicitly represented by the coefficients matrix U Φ . In [2], this matrix was directly estimated from the observed signal V , thus fully unsupervised. Here, we propose to estimate the speech filters from clean speech signals of a speaker. To do so, the speech filter matrice V Φ is first estimated by a spectral envelope estimation algorithm [START_REF] Villavicencio | Improving LPC spectral envelope extraction of voiced speech by true-envelope estimation[END_REF], which is then approximated by the NMF filter decomposition:

V Φ W Φ U Φ H Φ (6)
Furthermore, we used phonetic information in order to train phonemes separately and to have one basis for each speech filter (i.e. each phoneme).

SOURCE/FILTER MODEL UNDER CONSTRAINTS

Constrained-NMF

The main objective of this work is to inform NMF speech separation with a physical model of speech. For this purpose, we use constraints into the NMF to penalize solutions not respecting the speech model. Accordingly, the cost C is modified with the addition of the constraint penalty cost P:

C = DIS V | V + µP (7)
with µ a positive value determining the weight of the constraint. The new multiplicative update for the i-th iteration will be of the form :

Θ (i+1) ←-Θ (i) ⊗ ∇ - Θ (i) DIS + µ∇ - Θ (i) P ∇ + Θ (i) DIS + µ∇ + Θ (i) P (8)
for any non-fixed matrix Θ in the model. In our method, we use several constraints ans sum their values in order to obtain the total penalty cost P.

State-of-the-art constraints

We used three constraints from the literature :

• the sparsity constraint described in [START_REF] Joder | A comparative study on sparsity penalties for NMF-based speech separation: Beyond Lp-norms[END_REF] as the Column-Normalized 1-norm, in order to promote the activation, at any given time, of a single filter basis and a single excitation basis. • the normalized decorrelation constraint, based on the correlation measure proposed in [START_REF] Li | Learning spatially localized, parts-based representation[END_REF], in order to penalize simultaneous activation between bases. • a smoothness constraint proposed in [START_REF] Virtanen | Monaural sound source separation by nonnegative matrix factorization with temporal continuity and sparseness criteria[END_REF] to prevent filter activation to jump from one phoneme to another between frames.

Source/filter coherence constraint

The first contribution of this paper consists in the elaboration of a speech-specific source/filter coherence constraint for the IMM-NMF. This constraint is based on the fact that all phonemes corresponds to a match between one excitation one corresponding filter:

• vocal filters corresponding to voiced phoneme will always be used simultaneously with a periodic excitation; • vocal filters corresponding to unvoiced phoneme will always be used with a noisy excitation; Because the IMM-NMF allows unreal combination leading to audible artefacts, we propose a source/filter coherence constraint which aims to avoid unrealistic combinations between excitation and filter (see Figure 2). This constraint is inspired by the normalized decorrelation constraint, and is expressed as follow:

P φ = k∈periodic l∈unvoiced H ex H Φ T kl H ex k 2 H Φ l 2 + k∈noise l∈voiced H ex H Φ T kl H ex k 2 H Φ l 2 (9)
The left term of the sum is a measure of the correlation between periodic excitation basis and filter basis corresponding to unvoiced phoneme, normalized by their power; the right term is the same measure, but between noisy excitation basis and filter basis corresponding to voiced phoneme. the algorithms using the SDR criteria for BSS defined in [START_REF] Li | Learning spatially localized, parts-based representation[END_REF] and the PESQ, which is a MOS measure defined in [START_REF] Virtanen | Monaural sound source separation by nonnegative matrix factorization with temporal continuity and sparseness criteria[END_REF].

The proposed algorithms were used on the STFT magnitude of the observed signals, using a Hamming window of 64 ms and a hop size of 32 ms. The maximum number of iteration of the NMF was fixed to 100, and we used the IS divergence with a noise floor of 60dB (see [START_REF] Liutkus | An overview of informed audio source separation[END_REF]). The filterbank W was created with 50 Hann window spaced linearly from 0 to 8000 Hz and the excitation dictionary W ex was made up with 250 periodic basis (spanning every twentieth of tone between 80 and 350 Hz) and 100 white noise basis.

RESULTS AND DISCUSSION

The results that we show here are the one obtained for optimized values of constraint weight and number of noise basis; those values were found by testing on a separate and smaller database.

Table 1 shows our experimental results for all the tested algorithms. Firstly, we can see that our baseline algorithm (# 1) has better results than the algorithm V-IMM, as expected by the inclusion of a learning step in the IMM-NMF.

Secondly, if we compare algorithms with similar constraints, we observe that our adaptive weight method improve the separation results for all SNR, especially when the coherence constraint is used. We can also see that the best algorithm we proposed is the one using all constraints and the adaptive method (# 7); the constraints from the literature (decorrelation, sparsity and smoothness) have small effect (see # 1 and # 5), and the developed constraint is more effective in noisier environment.

Finally, we can see that our best algorithm (# 7) offers results far better than the unsupervised algorithm V-IMM which it is based on, and that those results are close from the ones obtained by ASNA. Indeed, it could have been interesting to compare our algorithms with other unsupervised method, but the only others authors could find were the algorithm proposed in [3], which uses the USM (and so the comparison with our speaker-dependent method would be flawed), and in [4], which is also based on the USM and is an online method.

CONCLUSION

In this paper, we presented a new semi-supervised method for speech separation, using a constrained NMF with a source/filter decomposition from the literature. The main contribution are a new speechspecific constraint, ensuring phonetic coherence, and an adaptive weight method for constraints.

Constraints

SoA the algorithms using the SDR criteria for BSS defined in [START_REF] Li | Learning spatially localized, parts-based representation[END_REF] and the PESQ, which is a MOS measure defined in [START_REF] Virtanen | Monaural sound source separation by nonnegative matrix factorization with temporal continuity and sparseness criteria[END_REF].

The proposed algorithms were used on the STFT magnitude of the observed signals, using a Hamming window of 64 ms and a hop size of 32 ms. The maximum number of iteration of the NMF was fixed to 100, and we used the IS divergence with a noise floor of 60dB (see [START_REF] Liutkus | An overview of informed audio source separation[END_REF]). The filterbank W was created with 50 Hann window spaced linearly from 0 to 8000 Hz and the excitation dictionary W ex was made up with 250 periodic basis (spanning every twentieth of tone between 80 and 350 Hz) and 100 white noise basis.

RESULTS AND DISCUSSION

The results that we show here are the one obtained for optimized values of constraint weight and number of noise basis; those values were found by testing on a separate and smaller database.

Table 1 shows our experimental results for all the tested algorithms. Firstly, we can see that our baseline algorithm (# 1) has better results than the algorithm V-IMM, as expected by the inclusion of a learning step in the IMM-NMF.

Secondly, if we compare algorithms with similar constraints, we observe that our adaptive weight method improve the separation results for all SNR, especially when the coherence constraint is used. We can also see that the best algorithm we proposed is the one using all constraints and the adaptive method (# 7); the constraints from the literature (decorrelation, sparsity and smoothness) have small effect (see # 1 and # 5), and the developed constraint is more effective in noisier environment.

Finally, we can see that our best algorithm (# 7) offers results far better than the unsupervised algorithm V-IMM which it is based on, and that those results are close from the ones obtained by ASNA. Indeed, it could have been interesting to compare our algorithms with other unsupervised method, but the only others authors could find the algorithm in [3], which uses the USM (and so the comparison with our speaker-dependent method would be flawed), and in [4], which is also based on the USM and is an online method.

CONCLUSION

In this paper, we presented a new semi-supervis separation, using a constrained NMF with a sou tion from the literature. The main contributio specific constraint, ensuring phonetic coheren weight method for constraints.

Constraints

SoA the algorithms using the SDR criteria for BSS defined in [START_REF] Li | Learning spatially localized, parts-based representation[END_REF] and the PESQ, which is a MOS measure defined in [START_REF] Virtanen | Monaural sound source separation by nonnegative matrix factorization with temporal continuity and sparseness criteria[END_REF].

The proposed algorithms were used on the STFT magnitude of the observed signals, using a Hamming window of 64 ms and a hop size of 32 ms. The maximum number of iteration of the NMF was fixed to 100, and we used the IS divergence with a noise floor of 60dB (see [START_REF] Liutkus | An overview of informed audio source separation[END_REF]). The filterbank W was created with 50 Hann window spaced linearly from 0 to 8000 Hz and the excitation dictionary W ex was made up with 250 periodic basis (spanning every twentieth of tone between 80 and 350 Hz) and 100 white noise basis.

RESULTS AND DISCUSSION

The results that we show here are the one obtained for optimized values of constraint weight and number of noise basis; those values were found by testing on a separate and smaller database.

Table 1 shows our experimental results for all the tested algorithms. Firstly, we can see that our baseline algorithm (# 1) has better results than the algorithm V-IMM, as expected by the inclusion of a learning step in the IMM-NMF.

Secondly, if we compare algorithms with similar constraints, we observe that our adaptive weight method improve the separation results for all SNR, especially when the coherence constraint is used. We can also see that the best algorithm we proposed is the one using all constraints and the adaptive method (# 7); the constraints from the literature (decorrelation, sparsity and smoothness) have small effect (see # 1 and # 5), and the developed constraint is more effective in noisier environment.

Finally, we can see that our best algorithm (# 7) offers results far better than the unsupervised algorithm V-IMM which it is based on, and that those results are close from the ones obtained by ASNA. Indeed, it could have been interesting to compare our algorithms with other unsupervised method, but the only others authors could find were the algorithm proposed in [3], which uses the USM (and so the comparison with our speaker-dependent method would be flawed), and in [4], which is also based on the USM and is an online method.

CONCLUSION

In this paper, we presented a new semi-supervised metho separation, using a constrained NMF with a source/filter tion from the literature. The main contribution are a n specific constraint, ensuring phonetic coherence, and weight method for constraints.

[1] G. J. Mysore the algorithms using the SDR criteria for BSS defined in [START_REF] Li | Learning spatially localized, parts-based representation[END_REF] and the PESQ, which is a MOS measure defined in [START_REF] Virtanen | Monaural sound source separation by nonnegative matrix factorization with temporal continuity and sparseness criteria[END_REF].

The proposed algorithms were used on the STFT magnitude of the observed signals, using a Hamming window of 64 ms and a hop size of 32 ms. The maximum number of iteration of the NMF was fixed to 100, and we used the IS divergence with a noise floor of 60dB (see [START_REF] Liutkus | An overview of informed audio source separation[END_REF]). The filterbank W was created with 50 Hann window spaced linearly from 0 to 8000 Hz and the excitation dictionary W ex was made up with 250 periodic basis (spanning every twentieth of tone between 80 and 350 Hz) and 100 white noise basis.

RESULTS AND DISCUSSION

The results that we show here are the one obtained for optimized values of constraint weight and number of noise basis; those values were found by testing on a separate and smaller database.

Table 1 shows our experimental results for all the tested algorithms. Firstly, we can see that our baseline algorithm (# 1) has better results than the algorithm V-IMM, as expected by the inclusion of a learning step in the IMM-NMF.

Secondly, if we compare algorithms with similar constraints, we observe that our adaptive weight method improve the separation results for all SNR, especially when the coherence constraint is used. We can also see that the best algorithm we proposed is the one using all constraints and the adaptive method (# 7); the constraints from the literature (decorrelation, sparsity and smoothness) have small effect (see # 1 and # 5), and the developed constraint is more effective in noisier environment.

Finally, we can see that our best algorithm (# 7) offers results far better than the unsupervised algorithm V-IMM which it is based on, and that those results are close from the ones obtained by ASNA. Indeed, it could have been interesting to compare our algorithms with other unsupervised method, but the only others authors could find were the algorithm proposed in [3], which uses the USM (and so the comparison with our speaker-dependent method would be flawed), and in [4], which is also based on the USM and is an online method.

CONC

In this paper, we presented a new s separation, using a constrained NM tion from the literature. The ma specific constraint, ensuring pho weight method for constraints.

REFE

[1] G. J. Mysore

Adaptation of constraints weights

One of the main limitations of constrained-NMF is the difficulty for finding a good constraint weight for speech separation. A small weight would conduct to a small or null effect of the constraint, while a strong weight will over-consider the constraint over the reconstruction cost, thus lead to a wrong solution depending on the initialization (generally random). The second contribution of this paper consists in adapting the constraint's weight at each iteration during speech separation: from small to strong depending on the evolution of the reconstruction (i.e. the evolution rate of the β-divergence value). At the i-th iteration, the constraint's weight is updated as:

µ (i) = µmax DIS V | V (i-2) -DIS V | V (i-1) DIS V | V (i-2) ( 10
)
where µ is initialized at 0 for the first two iterations, and after varies in the interval [0 µmax], where µmax is a chosen value. The stronger the β-divergence diminishes, the smaller the constraint; the smaller it diminishes, the higher the constraint. Figure 3 shows an example of the effect of this adaptive method on costs evolution. 1. Results from the experimental evaluation. SoA refers to the state-of-the-art constraints (decorrelation, sparsity and smoothness), coherence to the proposed source/filter coherence constraint and adaptation to the adaptive weight method.

4. EXPERIMENT

Experimental setups

An experiment was conducted to evaluate the performance of the semi-supervised and constrained source/filter model for speech separation. The benchmark includes: the semi-supervised source/filter model, with variants on the use of the constraints (with/without constraints, state-of-the-art constraints vs. source/filter coherence constraint, and with/without the constraint adaptation), with comparison to state-of-the-art unsupervised V-IMM source/filter model [2] (originally developed for singing voice / music separation), and the supervised ASNA algorithm [START_REF] Virtanen | Active-set Newton algorithm for overcomplete non-negative representations of audio[END_REF] (see Table 1 for details).

The database used for the experiment is a mix of the TIMIT speech database for clean speech [START_REF] Zue | Speech database development at MIT: TIMIT and beyond[END_REF] and the QUT-NOISE database for environmental background noises [START_REF] Dean | The QUT-NOISE-TIMIT corpus for the evaluation of voice activity detection algorithms[END_REF]. We used 20 TIMIT speakers (10 women and 10 men), with each 10 sentences: 2 sentences, shared among all the speakers, were used for training, and the 8 remaining sentences, different for all speakers, were used as the test set for speech separation. We mixed those 160 test sentences with 4 different background noises from the QUT-NOISE database (city street, home kitchen, car window, cafe) and white noise, using 3 signal-to-noise-ratio (SNR) (-6 dB, 0 dB, +6 dB), resulting in 2, 400 mixture signals. For the training, the 2 shared sentences were used for each speaker for the semi-supervised and the supervised algorithms, and one 5 s. extract of the background noise (different of the one used for mixing) was used for the supervised algorithm. The performance of the speech separation was measured based on the signal-to-distortion ratio (SDR) [START_REF] Vincent | Performance measurement in blind audio source separation[END_REF] (in dB), and the perceptive evaluation of speech quality (PESQ) [START_REF] Rix | Perceptual evaluation of speech quality (PESQ) -a new method for speech quality assessment of telephone networks and codecs[END_REF].

All benchmark speech separation algorithms were based on the STFT magnitude of the audio signal, using a Hamming window of 64 ms and a hop size of 32 ms. For training, the filterbank dictionary W Φ was created with 50 Hann windows linearly spaced from 0 to 8000 Hz, and the excitation dictionary W ex was created with 250 periodic bases (spanning every twentieth of tone between 80 and 350 Hz) and 100 white noise bases. For testing, the maximum number of iteration of the NMF was set to 100, and we used the IS divergence with a noise floor of -60dB (see [START_REF] Roebel | On automatic drum transcription using non-negative matrix deconvolution and Itakura-Saito divergence[END_REF] for details). Various constraint weights (from 10 -2 to 10 3 ) and number of background noise bases (from 5 to 100, used for all algorithms) were tested.

Results and Discussion

Table 1 summarizes the scores obtained for the benchmark algorithms, optimized for the state-of-the-art algorithms, and sharing the same optimal setup for all of the proposed algorithms. Firstly, the semi-supervised source/filter algorithm (# 1) improves the performance over a standard unsupervised source/filter, which naturally confirms the importance of training the filter dictionary for speech separation. Secondly, the use of constraints in the source/filter model without adaptation does not improves speech separation (# 1 vs. # 2, # 3, and # 4) on the one side. On the other side, the use of constraints with adaptation (# 5, # 6, and # 7) substantially improves speech separation. This shows the importance of the adaptation during speech separation, by gradually increasing the importance of the constraints depending on the convergence of the speech separation. This is especially true when using all constraints together (# 7). A comparison of the constraints reveals that the state-of-the-art constraints (decorrelation, sparsity and smoothness) have a small effect (# 5) whereas the source/filter coherence constraint provides a strong effect, and is more efficient for a high SNR (# 6). Finally, the semi-supervised constrained source/filter algorithm shows encouraging performance, compared to state-of-the-art algorithms. The semi-supervised algorithm stands in between unsupervised algorithm (V-IMM) and the supervised algorithm (ASNA). In particular, the semi-supervised algorithm is close to the supervised algorithm, without any prior knowledge about the nature the noise environment. This proves the importance of using prior knowledge on speech for informed speech separation.

CONCLUSION

In this paper, we presented a semi-supervised method for speech separation, based on a constrained source/filter model for NMF-based speech separation, with the add of a speech specific constraint, and the adaptive weighting of constraints during separation. An experimental validation proved the efficiency of the constrains for speech separation, and beyond indicates the importance of prior knowledge about speech and physically-motivated speech separation. Further research will focus on the integration of a source/filter model for text-informed speech separation [5,[START_REF] Magoarou | Text-informed audio source separation. Example-based approach using nonnegative matrix partial co-factorization[END_REF], and speaker-independent speech separation (Universal Speech Model [3]), and on the unsupervised estimation of the background noise [4,[START_REF] Roebel | On automatic drum transcription using non-negative matrix deconvolution and Itakura-Saito divergence[END_REF].

Figure 1 igure 1 . 2 -

 112 Modèle de décomposition source/filtre proposé dans [1] pour la NMF t ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu et al., sonore pour nous) est représenté en utilisant le décomposition classique de la NMF. Le obtenu s'écrit : atrices H ex , H et H N représentent respectivement les activations temporelles des ons, des filtres et du bruit, W ex est un dictionnaire d'excitations, W est un dictionnaire s élémentaires, U contient les combinaisons linéaires construisant les bases de filtres à e W , et W N est le dictionnaire des bases de bruit. Les matrices W ex et W sont ites préalablement à la NMF, et restent fixes durant toutes les itérations ; W ex contient des excitations harmonique et des excitations bruitées. Le Tableau 1.2 résume le rôle rentes matrices. es de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont en Annexe A.2.

  Dans la littérature, la factorisation (1.1) se fait en minimisant arg min W ,HØ0 D(V |W H) (1.3) 3 Durrieu et al. [1] proposent une factorisation en matrices non-négatives spécifique au source/filtre pour une tâche de séparation de l'instrument principal en musique 4 . élisent le spectrogramme d'amplitude de la voix (ou de l'instrument à séparer) comme it d'un spectrogramme des sources ex par un spectrogramme des filtres . La factoclassique de la NMF est alors appliqué sur ex et . Mais, pour assurer une certaine ité des filtres, chaque base du dictionnaire des filtres est représenté comme une combilinéaire de filtres élémentaires venant d'un banc de filtre. La Figure 1.2 illustre cette osition. = ¢ igure 1.2 -Modèle de décomposition source/filtre proposé dans [1] pour la NMF t ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu et al., sonore pour nous) est représenté en utilisant le décomposition classique de la NMF. Le obtenu s'écrit :

  .11) atrices H ex , H et H N représentent respectivement les activations temporelles des ons, des filtres et du bruit, W ex est un dictionnaire d'excitations, W est un dictionnaire s élémentaires, U contient les combinaisons linéaires construisant les bases de filtres à e W , et W N est le dictionnaire des bases de bruit. Les matrices W ex et W sont ites préalablement à la NMF, et restent fixes durant toutes les itérations ; W ex contient des excitations harmonique et des excitations bruitées. Le Tableau 1.2 résume le rôle rentes matrices. es de mise à jour multiplicatives spécifiques à ce modèle, déduites à partir de (1.9), sont en Annexe A.2.

4 .Figure 1 . 2 -

 412 Figure 1.2 -Modèle de décomposition source/filtre proposé dans [1] po

4 .Figure 1 . 2 -W

 412 Figure 1.2 -Décomposition source/filtre du spectrogramme d le produit d'un spectrogramme des sources ex par un spectrogramme des risation classique de la NMF est alors appliqué sur ex et . Mais, pour continuité des filtres, chaque base du dictionnaire des filtres est représent naison linéaire de filtres élémentaires venant d'un banc de filtre. La Figu décomposition. A W ex H ex W U H W N ex H N

Figure 1 . 2 -

 12 Figure 1.2 -Modèle de décomposition source/filtre proposé dans [1] pour la NMF Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu le fond sonore pour nous) est représenté en utilisant le décomposition classique de la NM modèle obtenu s'écrit : =

4 .Figure 1 . 2 -W

 412 Figure 1.2 -Décomposition source/filtre du spectrogramme d'une voix le produit d'un spectrogramme des sources ex par un spectrogramme des filtres . La risation classique de la NMF est alors appliqué sur ex et . Mais, pour assurer une c continuité des filtres, chaque base du dictionnaire des filtres est représenté comme une naison linéaire de filtres élémentaires venant d'un banc de filtre. La Figure 1.3 illustr décomposition. A W ex H ex W U H W N ex H N

Figure 1 . 2 -

 12 Figure 1.2 -Modèle de décomposition source/filtre proposé dans [1] pour la NMF Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu et al., le fond sonore pour nous) est représenté en utilisant le décomposition classique de la NMF. Le modèle obtenu s'écrit : =

4 .Figure 1 . 2 -

 412 Figure 1.2 -Modèle de décomposition source/filtre proposé dans [1] pour la NMF Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu et al., le fond sonore pour nous) est représenté en utilisant le décomposition classique de la NMF. Le modèle obtenu s'écrit : =

4 .Figure 1 . 2 -W

 412 Figure 1.2 -Décomposition source/filtre du spectrogramme d'une voix le produit d'un spectrogramme des sources ex par un spectrogramme des filtres . La factorisation classique de la NMF est alors appliqué sur ex et . Mais, pour assurer une certaine continuité des filtres, chaque base du dictionnaire des filtres est représenté comme une combinaison linéaire de filtres élémentaires venant d'un banc de filtre. La Figure 1.3 illustre cette décomposition. A W ex H ex W U H W N ex H N

4 .

 4 Ce n'est pas la seule intégration du modèle source/filtre dans la NMF ; on peut citer par exemple les travaux de Virtanen et Klapuri [12] qui proposent une nouvelle factorisation où chaque base spectrale est décomposée en un produit d'un spectre d'amplitude d'une excitation harmonique par celui d'un filtre. Damien Bouvier 7 M2 ATIAM -Rapport de Stage des di érentes matrices.

4 .W

 4 Ce n'est pas la seule intégration du modèle source/filtre dans la NMF ; on peut citer par exemple les travaux de Virtanen et Klapuri[START_REF] Benaroya | Audio source separation with a single sensor[END_REF] qui proposent une nouvelle factorisation où chaque base spectrale est décomposée en un produit d'un spectre d'amplitude d'une excitation harmonique par celui d'un filtre.Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical pour Durrieu et al., le fond sonore pour nous) est représenté en utilisant le décomposition classique de la NMF. Le modèle obtenu s'écrit :

Fig. 1 .

 1 Fig. 1. Illustration of the source/filter decomposition for the IMM-NMF described in (4).

FrequencyFigure 2 . 5 -

 25 Figure 2.5 -Comparaison W après séparation avec et san

Fig. 3 .

 3 Fig.3. Evolution of the reconstruction cost (in green), constraints cost (in red) and total cost (in blue) with (right graphic) and without (left graphic) the weight adaptation method, in function of the iteration number.

  ex , H et H N représentent respectivement l excitations, des filtres et du bruit, W ex est un dictionnaire d'excit de filtres élémentaires, U contient les combinaisons linéaires con partir de W , et W N est le dictionnaire des bases de bruit. L construites préalablement à la NMF, et restent fixes durant toute à la fois des excitations harmonique et des excitations bruitées. L des di érentes matrices. Les règles de mise à jour multiplicatives spécifiques à ce modèle, décrites en Annexe A.2.

				=
			Figure 1.2 -Modèle de décomposition source/filtre propo
			Tout ce qui est considéré comme bruit (i.e. l'accompagnemen le fond sonore pour nous) est représenté en utilisant le décompos modèle obtenu s'écrit :
			où les matrices H	= = (W ex H ex ) ¢ ex ¢	!	W U H	+ " +
	n'est pas la seule intégration du modèle source/filtre dans la NMF ; on peut citer par exemple les travaux en et Klapuri [12] qui proposent une nouvelle factorisation où chaque base spectrale est décomposée en it d'un spectre d'amplitude d'une excitation harmonique par celui d'un filtre.
	Bouvier	7	M2 ATIAM -Rapport de Stage

r pouvoir mieux situer nos travaux par rapport à la littérature, nous dressons ici un bref if des di érents algorithmes de séparation de la parole, en se focalisant sur les techniques

  où les matrices H ex , H et H N représentent respectivement les activation excitations, des filtres et du bruit, W ex est un dictionnaire d'excitations, W e de filtres élémentaires, U contient les combinaisons linéaires construisant les partir de W , et W N est le dictionnaire des bases de bruit. Les matrices W construites préalablement à la NMF, et restent fixes durant toutes les itératio à la fois des excitations harmonique et des excitations bruitées. Le Tableau 1 des di érentes matrices. Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à pa décrites en Annexe A.2.

  les matrices H ex , H et H N représentent respectivement les activat où les matrices H ex , H et H N représentent respectivement les activat excitations, des filtres et du bruit, W ex est un dictionnaire d'excitations, W de filtres élémentaires, U contient les combinaisons linéaires construisant partir de W , et W N est le dictionnaire des bases de bruit. Les matrice construites préalablement à la NMF, et restent fixes durant toutes les itéra à la fois des excitations harmonique et des excitations bruitées. Le Tablea des di érentes matrices. Les règles de mise à jour multiplicatives spécifiques à ce modèle, déduites à décrites en Annexe A.2.

	=					¢
	Figure 1.2 -Modèle de décomposition source/filtre proposé dans [1
	Tout ce qui est considéré comme bruit (i.e. l'accompagnement musical le fond sonore pour nous) est représenté en utilisant le décomposition clas modèle obtenu s'écrit :
	= = (W ex H ex ) ¢ ex ¢	!	W U H	+ " +	!	N W N H N
	Damien Bouvier		8			M2 ATIAM

2.2.3 Contrainte de cohérence source/filtre

  En linguistique, on distingue deux grands type de phonèmes : • les phonèmes voisées, qui correspondent à une excitation harmoniq vocales ; ce sont par exemple les voyelles /a/ ou /e/ ou les nasales /m • les phonèmes non-voisées, qui correspondent à une excitation bruitée certaines occlusives , comme /b/ ou /d/, ou certaines fricatives, com Lors des premiers tests, nous avons pu observer que des filtres vocaux ass voisés étaient activées en même temps que des excitations bruitées, et invers vocaux de phonèmes non-voisés. Malheureusement, cela résultait en la pré audibles, et baissait la qualité de la reconstruction. Puisque nous connaissons, pour chaque base de W , le phonème corres pensé à créer une contrainte de cohérence source/filtre pour empêcher l'ap mène. Le principe de cette contrainte serait d'empêcher les activations sim lignes de H ex et H que l'on connaît ; nous avons donc pensé à utiliser u celle de la contrainte de décorrélation (2.6). Notons V l'ensemble des indic vocaux voisés et H l'ensemble des indices des bases d'excitations harmoniq

	IMM-NMF Constraints Adaptation			3	3	3 SoA Coherence 3 Without weight adaptation 3 All	nous l'utilisons ici pour éliminer le avec des échelles d'amplitudes di é 3 3 SoA Coherence 3 All With weight adaptation
	6dB	SDR PESQ	5.8 2.00	4.4 1.22	4.0 1.91 1.91 4.1	5.0 1.94	5.2 1.92 1.91 4.1	5.2 2.01	Figure 2.5 -Compa 5.4 2.01
	+0dB	SDR PESQ	10.7 2.44	7.8 1.54	9.1 2.30 2.30 9.2	9.0 2.24	8.9 2.23 2.30 9.2	9.8 2.34	9.8 2.35
	+6dB	SDR PESQ	15.0 2.85	9.7 1.82	Periodic 13.0 12.8 2.62 2.61	11.1 2.46	Noisy 10.9 13.0 2.44 2.62	2.2.3 Contrainte de cohé 12.8 12.9 2.59 2.62
	Mean	SDR PESQ	10.5 2.43	7.3 1.52	8.7 2.28 2.27 8.7	8.4 2.21	8.3 2.20 2.28 8.7	En linguistique, on distingue de 9.3 9.4 2.31 2.33
										• les phonèmes voisées, qui co vocales ; ce sont par exemple • les phonèmes non-voisées, qu certaines occlusives , comme
						/s/ /a/			Lors des premiers tests, nous avon voisés étaient activées en même tem vocaux de phonèmes non-voisés. M audibles, et baissait la qualité de la Puisque nous connaissons, pour ch pensé à créer une contrainte de coh mène.
					Voiced (	/i/	)			Unvoiced (	/s/	)
						/u/			/a/
						s				/i/
						a				/u/
						i				s
						u				a
										i
										u
					Damien Bouvier		14 Le principe de cette contrainte M2 ATIAM lignes de H ex et H que l'on con celle de la contrainte de décorrélat vocaux voisés et H l'ensemble des i
										Damien Bouvier

Table 1 .

 1 Results from the experimental validation. SoA refers to the State-of-the-Art constraints (decorrelation, sparsity and smoothness) whereas Coherence refers to the proposed source/filter coherence constraint. Bold values are the best scores in the proposed methods.

Table 1 .

 1 Results from the experimental validation. SoA refers to the State-of-the-Art constraints (decorrelation, spar whereas Coherence refers to the proposed source/filter coherence constraint. Bold values are the best scores in the prop

	Adaptation				Coherence Without weight adaptation All	SoA Coherenc With weight ada
	6dB	SDR PESQ	5.8 2.00	4.4 1.22	4.0 1.91 1.91 4.1	5.0 1.94	5.2 1.92 1.91 4.1	5.2 2.01
	+0dB	SDR PESQ	10.7 2.44	7.8 1.54	9.1 2.30 2.30 9.2	9.0 2.24	8.9 2.23 2.30 9.2	9.8 2.34
	+6dB	SDR PESQ	15.0 2.85	9.7 1.82	13.0 12.8 2.62 2.61	11.1 2.46	10.9 13.0 2.44 2.62	12.8 2.59
	Mean	SDR PESQ	10.5 2.43	7.3 1.52	8.7 2.28 2.27 8.7	8.4 2.21	8.3 2.20 2.28 8.7	9.3 2.31

Table 1 .

 1 Results from the experimental validation. SoA refers to the State-of-the-Art constraints (decorrelation, sparsity and whereas Coherence refers to the proposed source/filter coherence constraint. Bold values are the best scores in the proposed met

	Adaptation				Coherence Without weight adaptation All	SoA Coherence With weight adaptation All
	6dB	SDR PESQ	5.8 2.00	4.4 1.22	4.0 1.91 1.91 4.1	5.0 1.94	5.2 1.92 1.91 4.1	5.2 2.01	5.4 2.01
	+0dB	SDR PESQ	10.7 2.44	7.8 1.54	9.1 2.30 2.30 9.2	9.0 2.24	8.9 2.23 2.30 9.2	9.8 2.34	9.8 2.35
	+6dB	SDR PESQ	15.0 2.85	9.7 1.82	13.0 12.8 2.62 2.61	11.1 2.46	10.9 13.0 2.44 2.62	12.8 2.59	12.9 2.62
	Mean	SDR PESQ	10.5 2.43	7.3 1.52	8.7 2.28 2.27 8.7	8.4 2.21	8.3 2.20 2.28 8.7	9.3 2.31	9.4 2.33

Table 1 .

 1 Results from the experimental validation. SoA refers to the State-of-the-Art constraints (decorr whereas Coherence refers to the proposed source/filter coherence constraint. Bold values are the best score

	and P. Smaragdis, "A non-negativ to language informed speech separation," in Lat Analysis and Signal Separation. Springer, 356-363. [Online]. Available: https://ccrma.s ⇠ gautham/Site/lva ica 2012.html
	[2] L. Le Magoarou, A. Ozerov, and N. Q. Duong, "Te audio source separation. example-based approach negative matrix partial co-factorization," Journa Processing Systems, pp. 1-15, 2014.
	[3] D. L. Sun and G. J. Mysore, "Universal spe for speaker independent single channel source in Acoustics, Speech and Signal Processing (ICA IEEE International Conference on. IEEE, 2013, p
	[4] F. G. Germain and G. J. Mysore, "Speaker and no dent online single-channel speech enhancement," i Speech and Signal Processing (ICASSP), 2015 IE tional Conference on. IEEE, 2015, pp. 71-75.
	[5] D. S. Williamson, Y. Wang, and D. Wang, "Deep works for estimating speech model activations," i Speech and Signal Processing (ICASSP), 2015 IE tional Conference on. IEEE, 2015, pp. 5113-511


Ahmet Iscen
email: ahmet.iscen@inria.fr

Michael Rabbat
email: michael.rabbat@mcgill.ca

Teddy Furon
email: teddy.furon@inria.fr

Efficient Large-Scale Similarity Search Using Matrix Factorization

We consider the image retrieval problem of finding the images in a dataset that are most similar to a query image. Our goal is to reduce the number of vector operations and memory for performing a search without sacrificing accuracy of the returned images. We adopt a group testing formulation and design the decoding architecture using either dictionary learning or eigendecomposition. The latter is a plausible option for small-to-medium sized problems with high-dimensional global image descriptors, whereas dictionary learning is applicable in large-scale scenarios. We evaluate our approach for global descriptors obtained from both SIFT and CNN features. Experiments with standard image search benchmarks, including the Ya-hoo100M dataset comprising 100 million images, show that our method gives comparable (and sometimes superior) accuracy compared to exhaustive search while requiring only 10% of the vector operations and memory. Moreover, for the same search complexity, our method gives significantly better accuracy compared to approaches based on dimensionality reduction or locality sensitive hashing.

Introduction

This paper is about image retrieval and similarity search for large datasets. Image retrieval aims to find the images in a large scale dataset that are most similar to a given query image. Recent approaches [START_REF] Jégou | Triangulation embedding and democratic kernels for image search[END_REF][START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] aggregate local SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] features or use deep-learning networks [START_REF] Babenko | Neural codes for image retrieval[END_REF] to create a global descriptor vector for each image. Visual similarity is then quantified by measuring the similarity of these vectors (e.g., cosine similarity). If the dataset has N images each represented by a d-dimensional feature vector, then an exhaustive search for each query requires dN operations.

A common approach to accelerate image search is indexing, which operates in sub-linear time [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF]. Indexing partitions the feature space R d into clusters and computes similarities between the query and dataset vectors that fall in the same or neighboring clusters. Yet, as the dimension d grows, the chance that similar images are assigned to different clusters increases, and the efficiency of these methods collapses [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF][START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF]. This is problematic in computer vision since most state-of-the-art image descriptors have high intrinsic dimensionality. A recent work tries to solve this by indexing descriptors based on sparse approximation [START_REF] Borges | High-dimensional indexing by sparse approximation[END_REF].

Another popular approach to efficient image search performs a linear scan over the dataset, computing approximate similarities using compact codes [START_REF] Arandjelović | Extremely low bit-rate nearest neighbor search using a set compression tree[END_REF][START_REF] Babenko | The inverted multi-index[END_REF][START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF][START_REF] Dong | Asymmetric distance estimation with sketches for similarity search in highdimensional spaces[END_REF][START_REF] Jégou | Product quantization for nearest neighbor search[END_REF][START_REF] Weiss | Spectral hashing[END_REF]. These techniques have a complexity of d ′ N where d ′ < d is the reduced dimensionality of the compact code. The similarity between vectors in R d is approximated by the distance between their compact codes. State-of-the-art large scale search algorithms combine indexing strategies with approximated similarities [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF].

Recently, a complementary approach inspired by group testing has emerged [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF][START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF]. Here the goal is to reduce the number of vectors against which the query is compared. The full dataset of N vectors is first summarized by M ≪ N group vectors, where each group vector is also d-dimensional. As the name suggests, each group vector represents a small subset of images in the original dataset. These groups are composed by a random partition of the dataset. Computation of the group vectors is performed offline under a specific construction such that a comparison group vector vs query vector measures how likely the group contains query matching vectors. Then, when presented with a query, the system compares the query with the group vectors instead of individual image vectors. This reduces the complexity from dN to dM .

Initial attempts [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF][START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF] considered an adaptive group testing approach. M groups are composed from the dataset, and querying proceeds in two stages. In the first stage, the scores between group vectors and the query are computed. They measure how likely their group contains some matching images. Then, in the second stage, the query is compared with individual image vectors for only the mostly likely positive groups. If the groups are roughly balanced in size and the query only matches a small number of group vectors, then the complexity is reduced from dN to d(M + N/M ). Although this results in efficient image retrieval, it has one major drawback: memory usage is increased since the group vectors and mapping from images to groups are stored in addition to the dataset feature vectors. In other words, these works trade complexity for memory. This is not a tractable option for large-N datasets.

In this work, we pursue the idea of deducing which vectors are matching in a database of size N from only M < N measurements. We re-examine the group testing formulation. Rather than a random partition of the dataset into groups followed by a specific construction of the group vectors, we formulate the problem of finding an optimal group testing design for a given image dataset. Removing the restriction to binary designs, the continuous version of this optimization problem turns out to be equivalent to dictionary learning. For small and medium sized datasets, with N < d, one can remove the requirement of a sparse design matrix, and then the problem simplifies further to that of a matrix factorization whose solution is given by the SVD.

The paper is organized as follows. Section 2 introduces the problem formulation and notation. Section 3 proposes different techniques to solve the problem depending on the parameters N and d. Section 4 shows the compatibility of our approach with an existing coding method in the literature. Section 5 presents the evaluation of proposed method using real image datasets.

Problem statement

The dataset is composed of N d-dimensional vectors {x i } N i=1 such that x i = 1, for all i, and each x i is the global feature vector of one image in the dataset. The similarity between two vectors x i and x j is the scalar product

x ⊤ i x j . Denote by X the d × N matrix [x 1 , . . . , x N ].
As mentioned in Section 1, we aim to find M group vectors of dimension d, {y i } M i=1 , stored in d × M matrix Y. Unlike the previous group testing approaches, we do not randomly assign dataset vectors to groups and we do not compute the group vectors according to a specific construction. Our goal is to directly find the best M group vectors globally summarizing the dataset. We call this process the encoding, and we restrict our scope to a linear encoding:

Y = enc(X) = XG ⊤ . ( 1
)
Given a query image, represented by its global descriptor vector q, we compute the group scores,

s = q ⊤ Y. (2)
Finally, we estimate the similarities between query and database vectors c = q ⊤ X from the measurements s. Again, we assume a linear estimator:

ĉ = dec(s) = sH. ( 3
)
Our aim is to design G ∈ R M ×N and H ∈ R M ×N to allow for a fast and accurate search. Note that this setup is similar to the pioneering work of Shi et al. [START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF]: in their paper, G is indeed a randomly generated binary matrix where G(i, j) = 1 if x j belongs to the i-th group and G(i, j) = 0 otherwise. Hence, in the previous group testing approach, G captures both how groups are made and how the group vectors are computed (a simple sum in [START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF]). On the contrary, we look for the best matrix representing the dataset, which will heavily depend on X. Complexity. Exhaustive search involves computing q ⊤ X, which has a complexity of dN . Computing the group measurements (2) takes dM operations, and the decoding (3) takes M N . This gives a complexity of dM + N M for group-testing search, compared to dN operations for exhaustive search. The complexity ratio is thus ρ = M/N + M/d, implying that M must be smaller than both N and d to yield efficient queries.

Previous work based on group testing [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF][START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF] designs groups so that every column of G has exactly m ≪ M ones; i.e., each dataset vector belongs to m groups. This produces a sparse decoding matrix H which, in turn, yields the better complexity ratio ρ = M/N + m/d. However, none of the approaches [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF][START_REF] Shi | A group testing framework for similarity search in high-dimensional spaces[END_REF] attempt to optimize G and H. They either create G randomly or use a clustering algorithm to coarsely group similar dataset vectors [START_REF] Iscen | Memory vectors for similarity search in high-dimensional spaces[END_REF]. In the following sections, we discuss two techniques that optimize the matrices G and H for a particular dataset X.

We focus on the complexity of performing a query. Determining the optimal encoding and decoding matrices G and H requires additional computation applied offline or periodically. We assume that the corresponding complexity is not as critical as in the query stage. Our only requirement is that the complexity of this offline computation be polynomial in N and d to ensure that it is tractable.

Proposed solutions

We now provide two alternative solutions for the setup described in Section 2. As we will show in the experimental section, both solutions have advantages and drawbacks, and can be chosen depending on the feature vectors and the number of items in the dataset.

First solution: Eigendecomposition

In the first approach, we consider finding matrices G ∈ R M ×N and H ∈ R M ×N so that the approximate scores ĉ and exact scores c are as close as possible. Based on (1), (2) and (3), this amounts to: minimize

G,H q∈Q c -ĉ 2 2 = minimize G,H q∈Q q T X -q T XG ⊤ H 2 2 ,
where Q is assumed to be representative of typical queries. Of course, this distance cannot be zero for all q ∈ R d since the N × N matrix G ⊤ H has rank at most M < N . We focus on providing accurate scores for typical queries. We use the dataset of vectors itself as a proxy of the typical ensemble of queries. This amounts to replacing q by X and to consider the Frobenius matrix norm:

minimize G,H X ⊤ X -X ⊤ XG ⊤ H 2 F . ( 4
)
This problem is commonly solved by eigendecomposition. Let A = X ⊤ X be the Gramian symmetric matrix associated to X. As a real symmetric matrix, A is diagonalizable: A = UΛU ⊤ , where U is an orthogonal matrix (U ⊤ U = UU ⊤ = I N ). This means that we can simply assign G ⊤ = U M and H = U ⊤ M , where U M are the eigenvectors associated with the M largest eigenvalues.

In practice, we do not need to compute the Gram matrix A = X ⊤ X . The singular value decomposition (SVD) of X is defined as X = SΣU ⊤ , where S are the eigenvectors of XX ⊤ , and U are the eigenvectors of X ⊤ X. Hence, this SVD gives us the desired output without having to calculate A. It is worth noting that this solution resembles a well known dimension reduction method: Principal Component Analysis (PCA). However, while PCA is usually employed to reduce the dimensionality of the vectors from d to d ′ components, in our approach we use it to reduce the number of vectors from N to M . Alternatively, more efficient dimensionality reduction methods, such as sparse projectors [START_REF] Negrel | Dimensionality reduction of visual features using sparse projectors for content-based image retrieval[END_REF], can be used to construct H.

The major drawback of this approach is that H is not sparse. Therefore, the complexity of the decoding (3) is in O(M N ). Hence, this solution is efficient for scenarios where d is larger than N .

Second solution: Dictionary learning

Dictionary learning has been widely applied in imaging problems, e.g., to obtain efficient representations and discover structure using local patches; see [START_REF] Mairal | Sparse modeling for image and vision processing[END_REF] for a survey. Our second solution applies dictionary learning to find a sparse description of the dataset enabling efficient image search. For any query q, we expect the score vector c to be sparse; the few high-amplitude coefficients correspond to the matching images, and remaining low-amplitude coefficients correspond to non-matching images. Moreover, we do not need the estimate ĉ to be very close to c, per se, as long as the matching images receive a substantially higher score than the non-matching ones.

Because the three steps (1), ( 2) and (3) of our method are linear, this reconstruction of the similarities through a sparse matrix H implies a sparse representation of the dataset vectors, which leads to the connection with dictionary learning. Specifically, we aim to approximate X by YH where H ∈ R M ×N stores the sparse representations of the dataset vectors in terms of columns (so-called atoms) of the dictionary Y ∈ R d×M . This leads to the following optimization problem:

minimize Y,H 1 2 X -YH 2 F + λ H 1 subject to y k 2 ≤ 1 for all 0 ≤ k < M.
The ℓ 1 -norm penalty on H (sum of the magnitude of its elements) encourages a solution where each column of X can be represented as a sparse combination of columns of the dictionary Y. The level of sparsity depends on λ. Unlike the previous solution of Section 3.1, this scheme is competitive when N is larger than d since we benefit from the reduced complexity of sparse matrix multiplication. An algorithm such as Orthogonal Matching Pursuit (OMP) [START_REF] Davis | Adaptive timefrequency decompositions with matching pursuit[END_REF][START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] allows us to strictly control the sparsity of H. For a given dictionary Y, OMP finds

H = [h 1 , • • • , h N ] by sequentially solving minimize hi 1 2 x i -Yh i 2 2
subject to

h i 0 ≤ m.
Adopting this algorithm, we control the sparsity of the matrix H by setting m to a desired value. Note that this solution is directly related with the problem statement in Section 2, even if G is not directly a part of the solution. The reconstruction of the vectors X is linear up to an approximation, X ≈ YH. Since this is a linear process , we have Y = XG ⊤ (1) where G ⊤ = H + (pseudo-inverse). Therefore, the connection is obvious. Furthermore, G is not needed during the search; what matters is Y and H.

This solution is similar to the recently proposed indexing strategy based on sparse approximation [START_REF] Borges | High-dimensional indexing by sparse approximation[END_REF], which also involves training a dictionary Y and a sparse matrix H. However, the way these matrices are used in [START_REF] Borges | High-dimensional indexing by sparse approximation[END_REF] is completely different from the approach proposed here. Their framework adheres to a space partitioning approach; it indexes each descriptor in buckets using an inverted file based on the non-zero entries of H. For a given query, their system runs orthogonal matching pursuit (OMP) to find a sparse approximation, and then it calculates distances between the query and the dataset vectors that share the same buckets. In contrast, the method proposed here involves no indexing and makes no direct distance calculations between the query and the dataset vectors. Indeed, this allows us to completely avoid touching dataset vectors at query time.

Similarly, clustering can be used to make groups, as in traditional indexing approaches [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF], but the decoding does not perform well for the following reason. The decoding matrix is too sparse: a single non-zero component in each column (this vector belongs to that cluster). This requires an additional verification step after the decoding step for the vectors in the leading cluster. This is not needed in our method, hence we obtain huge savings in complexity and memory. Our approach can be seen as performing a sortof soft clustering, where each vector belongs to multiple clusters with different weights.

Large-scale dictionary learning

When designing an image search system, one must consider large-scale problems consisting of millions to billions of images. As explained in Section 1, our primary goal is an efficient image search system whose query time complexity (computational, and memory) is reduced. Although we have been ignoring the complexity of the encoding phase, by assuming that the complexity of this stage is less critical application-wise, it should remain tractable.

One of the most widely-known dictionary learning algorithms is that proposed by Mairal et al. [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF]. This algorithm provides a fast implementation and allows other possibilities such as mini-batch learning and online dictionary updates. These features make it an attractive algorithm for large-scale problems. However, the training time increases dramatically with M for large-N datasets, as reported in Section 5. Even though this calculation needs to be done only once in the offline stage, we still need a scalable training approach to index all dataset vectors easily.

One solution is to use a subset of dataset vectors as a surrogate for the entire dataset. Once the dictionary Y is trained on the subset, a less expensive sparse decoding algorithm, such as OMP, can be used to compute the matrix H for the entire dataset.

Elhamifar et al. [START_REF] Elhamifar | See all by looking at a few: Sparse modeling for finding representative objects[END_REF] propose a solution similar to dictionary learning, with the sole aim of finding representatives from the data. A related approach is to use coresets [START_REF] Agarwal | Approximating extent measures of points[END_REF]. A coreset C is a problem-dependent approximation of a dataset X. Feldman et al. [START_REF] Feldman | Learning big (image) data via coresets for dictionaries[END_REF] show that for every X and ǫ > 0 there exists a coreset C ∈ R d×N ′ , N ′ < N , for which the following inequality holds:

(1 -ǫ)• min H∈R M ×N X -YH 2 F ≤ min H∈R M ×N ′ C -Y H 2 F ≤ (1 + ǫ) • min H∈R M ×N X -YH 2 F .
Typically, C has many fewer columns than X, thereby summarizing the whole dataset with just a few representatives. The main advantage of this approach is its speed. Finding a coreset for a large-scale dataset takes a short time, only a few seconds in our experiments. Then, running dictionary learning on the coreset is significantly faster than on the original dataset. We empirically evaluate the speedup and the effect on accuracy in the experimental section.

Compressed dictionaries

Instead of dealing with a database of N image vectors of length d, our novel approach now manages a database of M group vectors of the same dimension. Compared to a linear scan, we reduce the number of comparisons from N to M , and yet, rank N items based on their estimated score.

Nevertheless, our scheme remains compatible with the traditional coding methods briefly introduced in the introduction. Instead of a linear scan browsing group vectors, we can add on top of our method an approximate search. This can take the form of either an embedding producing compact representations of the group vectors, or an indexing structure finding the closest group vectors w.r.t. a query. This improves even further the overall efficiency.

Case study: Combination with PQ-codes. An embedding offers a compact representation of group vectors allowing a fast approximation of their dot products with the query. PQ-codes [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF], for instance, are a priori not compliant since they operate on Euclidean distances. We convert Euclidean distance to cosine similarity in the following way. Each group vector y is split into ℓ subvectors ỹu , where

1 ≤ u ≤ ℓ. Each subvector ỹu is quantized using the code- book C u = {c i,u } Q i=1 : v u = arg min 1≤i≤Q ỹu -c i,u
. The compact representation of y is the list of codeword indices (v 1 , . . . , v ℓ ) ∈ {1, . . . , Q} ℓ . This is exactly the same encoding stage as the original PQ-codes [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF].

The dot product query vs group vector is approximated by the dot product query vs quantized group vector:

q ⊤ y = ℓ u=1 q⊤ u ỹu ≈ ℓ u=1 q⊤ u c vu,u , (5)
where qu is the u-th subvector of the query. As in the original application of PQ-codes, the quantities {q ⊤ u c i,u } are computed at query time and stored in a lookup table for evaluating [START_REF] Borges | High-dimensional indexing by sparse approximation[END_REF] efficiently over a large number of group vectors. Using approximate dot products is an additional source of error, but experiments in the next section show that the decoding schemes described above gracefully handle this.

Experiments

After detailing the experimental protocol, we report retrieval performance results together with a comparison with other image retrieval approaches.

Experimental setup

Datasets. We evaluate our retrieval system using the Ox-ford5k [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and Paris6k [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF] datasets, which contain 5,063 and 6,412 images respectively. For large-scale experiments we add 100,000 Flickr distractor images [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF], resulting in datasets referred as to Oxford105k and Paris106k. Additionally, we use the Yahoo Flickr Creative Commons 100M [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF]. DL gives better performance, all the more so as the dataset is large. We only evaluate DL up to M/N = 1/10 for Oxford105k and Paris106k. Performance eventually converges to the baseline after this point.

dataset [START_REF] Thomee | Yfcc100m: The new data in multimedia research[END_REF] (referred as to Yahoo100M), which comprises about 100 million image vectors. For comparison with other works, we also run experiments on the Holidays [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] and UKB [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF] datasets.

For each dataset, we follow its standard procedure to evaluate performances. The mean Average Precision (mAP) measures the retrieval quality in all datasets except for UKB, where the performance is gauged by 4×recall@4.

Features. For most of our experiments, we use the stateof-the-art R-MAC features [START_REF] Tolias | Particular object retrieval with integral max-pooling of cnn activations[END_REF]. Depending on the network used, these features have dimensionality of either d = 512 or d = 256. 1 In section 5.3, we use T-embedding features [START_REF] Jégou | Triangulation embedding and democratic kernels for image search[END_REF] with d = 8, 064 to allow a more direct comparison with the most similar concurrent methods. For Ya-hoo100M, we use VLAD [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] with d = 1, 024 as in [START_REF] Spyromitros-Xioufis | A comprehensive study over VLAD and product quantization in large-scale image retrieval[END_REF].

Complexity analysis. We report the complexity ratio, ρ = (M d + s)/dN , where s = nnz(H) is the number of nonzero elements of matrix H. For the eigendecomposition, we set s = M N , whereas for dictionary learning (Section 3.2), m controls the sparsity of H making the complexity ratio ρ = M/N + m/d. Unless otherwise specified, we set m = 10 for R-MAC features; when d = 512 then decoding contributes only 0.02 to ρ (i.e., 2% of the complexity of exhaustive search). The memory ratio, the ratio of the memory required compared to that of exhaustive search, is equal to ρ for non-sparse H. When H is sparse, we need to store mN scalars and their indices, making the memory ratio M/N + m/d + m log 2 (M )/d ≈ ρ.

Retrieval performance

We first evaluate our system for different M using either eigendecomposition or dictionary learning solutions. We also include the popular sketching technique LSH [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF], which approximates similarity by comparing binary compact codes of length d ′ = ρd. We measure the retrieval performance in terms of mAP and complexity ratio as mentioned in Section 5.1.

Figure 1 shows the retrieval performance for different complexity ratios. It is clearly seen that eigendecomposition suffers at low complexity ratio in large-scale datasets. 1 Features available online: ftp://ftp.irisa.fr/local/ texmex/corpus/memvec/cvpr16/rmac/ This is expected because we must set M to a very small value to obtain a low complexity ratio since the decoding matrix H is not sparse in this solution. On the other hand, we can set M to a much higher value for a given complexity ratio using dictionary learning since H is sparse.

Our variant based on dictionary learning performs better than the baseline on all datasets. One would expect the performance to be worse than baseline for M ≪ N due to loss of information, but this is surprisingly not the case. A possible explanation is that dictionary learning "denoises" similarities between vectors. In computer vision, each image is represented by a global vector, which is usually obtained by aggregating local features, such as SIFT, or response maps from convolutional neural networks (in the case of R-MAC). These local features are obtained from both useful structure of the scene and also from clutter.

Our interpretation is that dictionary learning decreases the impact of features extracted from clutter patches because they are not common across the image collection; i.e., it favors the frequent visual patterns in the image collection. To explore this phenomenon further, we plot the distribution of matching and non-matching vector similarities from Oxford5k using the original global descriptors. We repeat the same process using the reconstructed similarities from dictionary learning. As we see in Figure 2, both reconstructed similarity distributions have a lower variance than the original distributions. This is especially true for the nonmatching distribution. This variance reduction increases the separation between the distributions, which translates to the better performance of our dictionary learning method. Sparsity of H is controlled by parameter m in dictionary learning (see Section 3.2). This is an important factor in the complexity ratio ρ. The ratio between m and d contributes to ρ independently from M . It is possible to set this ratio to a small value to eliminate its influence.

We compute a dictionary of M atoms and we calculate several matrices H by applying OMP with different m. We plot the retrieval performance for different m and M in Figure 3. In most cases, the performance does not vary much w.r.t. m. The biggest difference is observed for Oxford105k where larger m leads to better performance for small M . The dimensionality of the vectors is an important factor affecting the overall complexity. Lower dimensionality im- plies lower complexity and less memory usage. Although our experiments up to now are done in what can be considered as a low-dimensional feature space (d = 512), we evaluate our system with even smaller features, d = 256, in Figure 4. The results are similar to those for d = 512, although the accuracy of eigendecomposition increases at a slower rate for large N .

The training stage computes Y and H and is performed only once and offline. However, it is important that this stage is scalable for updating the dictionary if needed. Experimentally, a small number of iterations (≈ 100) is sufficient for dictionary learning. This does not require much training time. Using Mairal et al. 's algorithm [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF], we report the duration of the offline training on Figure 5. All experiments are done on a server with Intel Xeon E5-2650 2.00GHz CPU and 32 cores. The training time is reasonable for all datasets, but it increases dramatically with M in large datasets. Other training procedures would be necessary for handling large M and N .

Coresets, as explained in Section 3.3, reduce the training time even further for large datasets. Instead of using the entire dataset, we find a coreset C which represents the data with a few representatives vectors to train the dictionaries. We report results for coresets of different sizes in Table 1. Empirically, we achieve a similar performance by training on coresets of vectors. This allows us to train the dictionary for larger M in just a few minutes. Note that Paris106k has fast training time even without coresets. This is because the best performance for this dataset is obtained with M = 532, a rather small value. The drawback to using coresets 1. Performance and training time (in minutes) using coresets to train the dictionary. M is set to 5, 257 and 532 for Oxford105k and Paris105k respectively, and m = 50. Each experiment is run 5 times, and we report the mean and the standard deviation.

is that H is less sparse: m = 50. This results in the same performance but slightly higher complexity. The search time is the average number of seconds to respond to a query. Although comparing vector operations is reliable in general, we also include the actual timings. Exhaustive search takes 0.029s on Oxford105k and 0.03s on Paris106k (average per query). Our method takes 0.003s on Oxford105k (M = 5, 257), and 0.001s on Paris106k (M = 532), with higher mAP than exhaustive search.

Comparison with other methods

We compare our system with other image retrieval approaches. First we compare with the popular FLANN toolbox [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF] using Oxford105k and R-MAC features. We set the target precision to 0.95 and use the "autotuned" setting of FLANN, which optimizes the indexing structure based on the data. We repeat this experiment 5 times. The average speed-up ratio provided by the algorithm is 1.05, which corresponds to a complexity ratio of 0.95. In other words, FLANN is ineffective for these R-MAC descriptors, most likely due to their high intrinsic dimensionality (d = 512): as discussed by its authors [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF], FLANN is not better than exhaustive search when applied to truly high-dimensional vectors. In contrast, our approach does not partition the feature space and does not suffer as much the curse of dimensionality. Our descriptors are whitened for better performance [START_REF] Jégou | Negative evidences and cooccurrences in image retrieval: The benefit of PCA and whitening[END_REF], which tends to reduce the effectiveness of partitioning-based approaches.

Next we compare our method with other group testing and indexing methods in the image retrieval literature. To have a fair comparison, we report the performance using the same high-dimensional features (d = 8, 064), same datasets, and the same complexity ratio as the group testing methods. Additionally, we also compare our scores to a dictionary learning-based hashing method [START_REF] Borges | High-dimensional indexing by sparse approximation[END_REF], LSH [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF] and PCA, where dimensionality of vectors is reduced such that d ′ = 0.4d. Table 2 shows the comparison for a fixed complexity ratio. We outline two observations. First, eigendecomposition works well in these experiments. This is especially true for the Holidays dataset where N = 1, 491 and d = 8, 064; large M can be used while keeping the complexity ratio low since N < d. This is clearly a scenario where it is plausible to use the eigendecomposition approach. Second, dictionary learning performs poorly for Holidays. This dataset contains only 1, 491 images, which constrains the size of the dictionary M to be small and prevents sparsity: the best parameters (via cross-validation) are found to be M = 519 and m = 409, giving ρ = 0.4. Note that this experiment uses long t-embedding descriptors (d = 8, 096) in small and mid-scale datasets. Most likely, these features have low intrinsic dimensionality, and PCA and LSH are thus favored. Table 3 uses shorter R-MAC features (d = 512) for comparison. The increase in performance is more significant, especially for large datasets.

Yahoo100M is a recently released large-scale dataset consisting of approximately 100M images. Since there is no manually annotated ground-truth, we use the following evaluation protocol: a dataset vector is considered to match the query if its cosine similarity is at least 0.5. There are 112 queries randomly selected from the dataset. Each query has between 2 and 96 matches, and 11.4 matches on average. can perform this offline stage in parallel. At query time, we pool scores from each chunk together and sort them to determine a final ranking. When we evaluate the retrieval performance, we obtain a mAP of 89.4 with ρ ≈ 1/10. This is a significant increase compared to running the same setup with LSH, which results in a mAP of 70.9. Furthermore, it is still possible for the dictionary learning approach to obtain very good performance with ρ < 1/10 by setting M and m to smaller values as shown in Table 5.3.

Similar to other datasets, we apply coresets for the Ya-hoo100M dataset. We learn a coreset for each chunk separately, which makes its calculation feasible. We set |C| = N/2, m = 100 and M = N/100, and obtain a mAP of 87.9 compared to a mAP of 89.4 using the entire chunks. Compatibility with coding methods. One of the main strengths of our method is its complementarity with other popular coding strategies in computer vision. We combine our method with PQ-codes [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF] Table 6 shows the difference of performance with and without PQ-codes. Observe that the performance remains almost the same for b = 8. The compression factor by PQ- code is significant (8 floats replaced by 1 byte).

Conclusion

This paper lowers the complexity of image search by reducing the number of vector comparisons. We formulate the image search problem as a matrix factorization problem, which can be solved using eigendecomposition or dictionary learning. We show that the former is a plausible option for small datasets, whereas the latter can be applied for large-scale problems in general. When applied to real datasets comprising up to 10 8 images, our framework achieves a comparable, and sometimes better performance, than exhaustive search within a fraction of complexity. It is worth noting that this approach is complementary to other indexing/approximated similarity approaches such that it can be combined to further increase efficiency.

Figure 2 .

 2 Figure 2. Distributions of matching and non-matching vector similarities from Oxford5k dataset. Red (blue) curves represent distributions of true (resp. reconstructed) similarities. The main improvement comes from the reduction of variance under the negative distribution.

Figure 3 .

 3 Figure 3. Retrieval performance with different M and m. Varying m does not affect the performance in most cases, except for Oxford105k, where increasing m improves performance for small M .

Figure 4 .Figure 5 .

 45 Figure 4. Retrieval performance using smaller features: d = 256.

Table 4 .

 4 Some examples of match and query in Yahoo100M dataset. Two vectors are considered a match if their similarity is above 0.5. M = N/200 M = N/100 M = N/50 mAP ρ Performance (mAP) and complexity ratio (ρ) in Ya-hoo100M for different M and m.

  as explained in Section 4. We use ℓ = d/b subvectors for different values of b and Q = 256 codewords per each subquantizer (except for Paris6k where Q = 16 due to small M ). This reduces the term O(M × d) by a factor of b if we neglect the fixed cost of complexity of building the lookup table.

6 .

 6 Baseline Our Method b = 8 b = 64 Oxford5k 66Combination of our method with PQ-codes. We use M = 350 for Oxford5k, M = 30 for Paris6k, M = 5257 for Oxford105k, and M = 532 for Paris106k.

Table 2 .

 2 Comparison in image retrieval for a given complexity ratio of 0.4. This experiment uses long t-embedding features (d = 8, 096). Eigendecomposition and dictionary learning generally performs better at lower memory ratio.

		Mem. Ratio	Holidays	Oxford5k	UKB
	Exhaustive		1.0	77.1	67.4 3.63
	Iscen et al. [11]-Kmeans	1.4	76.9	67.3 3.63
	Iscen et al. [11]-Rand	1.4	75.8	62.0 3.63
	Shi et al. [27] w/ bp.		1.4	75.5	64.4 3.63
	Borges et al. [5]		1.0	59.2	59.9 3.43
	LSH [6]		0.4	73.9	65.8 3.61
	PCA		0.4	75.4	64.3 3.61
	Shi et al. [27] w/o bp.	0.4	8.7	24.1 1.33
	Ours -Eigen.		0.4	76.9	67.7 3.63
	Ours -Dict. Learn.		0.4	55.2	68.8 3.59
	Mem. Ratio	Oxf5k	Oxf105k	Paris6k	Paris106k
	Exhaustive	1.0	66.9	61.6	83.0	75.7
	[11]-Kmeans	1.1	65.6	61.2	79.7	75.7
	[11]-Rand	1.1	25.1	43.7	21.2	44.4
	[27] w/ bp.	1.1	15.4	28.1	18.7	37.7
	[5]	1.0	8.5	22.7	8.2	18.9
	LSH [6]	0.1	48.6	40.5	70.1	58.2
	PCA	0.1	58.1	8.0	86.1	38.9
	Ours-Eigen.	0.1	56.8	8.0	86.3	40.9
	Ours-D.L.	0.1	73.7	65.5	85.3	78.9

Table 3 .

 3 Comparison with R-MAC features (d = 512) and 0.1 complexity ratio.

Table 5 .

 5 [START_REF] Arandjelović | Extremely low bit-rate nearest neighbor search using a set compression tree[END_REF] shows visual examples of queries and matches. This dataset is split into chunks of N ′ = 100k images. We run dictionary learning and OMP independently to learn matrices Y and H for each chunk, setting M ′ = N ′ /100 and m = 100. Overall, it results in M = N/100. We

	Query	Match	Query	Match	Query	Match
	Query	Match	Match	Match	Match	Match
	Query	Match	Match	Match	Match	Match

Acknowledgments

This work was supported, in part, by the Natural Sciences and Engineering Research Council of Canada through grant RGPAS 429296-12, and by the French National Project IDFRAud (ANR-14-CE28-0012). Portions of this work were completed while the first author was visiting McGill University.