README.md 4.98 KB
Newer Older
MARMORET Axel's avatar
MARMORET Axel committed
1
# nn-fac: Nonnegative Factorization techniques toolbox
MARMORET Axel's avatar
MARMORET Axel committed
2
Python code for computing some Nonnegative Factorizations, using either an accelerated version of Hierarchical Alternating Least Squares algorithm (HALS) with resolution of Nonnegative Least Squares problem (NNLS) [1] for factorizations subject to the minimization of the Euclidean/Frobenius norm, or the Multiplicative Update [2,3] for factors, by minimizing the $\beta$-divergence [3]..
3 4 5

This work has been done during my Research Master's (SIF, master.irisa.fr) internship in PANAMA team at IRISA/Inria Rennes, under the direction of BERTIN Nancy and COHEN Jeremy.

6
It has been extended during my PhD in the same Team, under the direction of BERTIN Nancy and COHEN Jeremy and BIMBOT Frederic.
Axel Marmoret's avatar
Axel Marmoret committed
7

MARMORET Axel's avatar
MARMORET Axel committed
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
## Installation

You can install it using pip:

    pip install nn-fac

You can then use code by typing:

    import nn_fac

For example, if you want to use nmf, type:

    import nn_fac.nmf

Don't hesitate to reach the author in case of problem. Comments are welcomed!

## Contents
### NNLS
26 27
This toolbox contains a NNLS resolution algorithm, developed as described in [1]. This code is based on COHEN Jeremy python code adaptation of GILLIS Nicolas MatLab code.

MARMORET Axel's avatar
MARMORET Axel committed
28 29 30
### MU
This toolbox contains a MU resolution algorithm, developed as described in [3] for NMF, also extended for tensorial factorizations. This code is based on an internship of Florian VOORWINDEN and has been improved with COHEN Jeremy and Valentin LEPLAT.

MARMORET Axel's avatar
MARMORET Axel committed
31
This toolbox also contains 4 factorization methods:
MARMORET Axel's avatar
MARMORET Axel committed
32
### NMF
MARMORET Axel's avatar
MARMORET Axel committed
33
Nonnegative Matrix Factorization [2] - Factorization of a nonnegative matrix X in two nonnegative matrices W and H, where WH approach X.
34

MARMORET Axel's avatar
MARMORET Axel committed
35 36 37
In the hals condition, this is solved by minimizing the Frobenius norm between both matrices X and WH by NNLS.

In the mu condition, this is solved by minimizing the $\beta$-divergence [3] between both matrices X and WH by Multiplicative Updates.
38

MARMORET Axel's avatar
MARMORET Axel committed
39
### NTF - Nonnegative PARAFAC
MARMORET Axel's avatar
MARMORET Axel committed
40 41 42
Nonnegative Tensor Factorization, also called Nonnegative PARAFAC decomposition. PARAFAC decomposition consists in factorizing a tensor T in a sum of rank-one tensors [4]. By concatenating the vectors along each mode of this sum, we obtain as much factors as the number of modes of the tensor [5]. This algorithm returns these factors.

In the hals condition, this factorization is computed as an ALS algorithm, described in [6], solved with NNLS, and using the toolbox Tensorly [7]. It returns the nonnegative factors of a nonnegative tensor T.
43

MARMORET Axel's avatar
MARMORET Axel committed
44
In the mu condition, this factorization is computed as NMF subproblems, described in [3], solved with Multiplicative Update, and using the toolbox Tensorly [7]. It returns the nonnegative factors of a nonnegative tensor T subject to the minimization of the $\beta$-divergence.
45

MARMORET Axel's avatar
MARMORET Axel committed
46
### Nonnegative PARAFAC2
MARMORET Axel's avatar
MARMORET Axel committed
47
Nonnegative Tensor Factorization admitting variability over a factor [8]. More precisely, this implemented version is based on a flexible coupling approach [9], where the coupling is enforced by a penalty term.
48

MARMORET Axel's avatar
MARMORET Axel committed
49
### NTD - Nonnegative Tucker Decomposition
MARMORET Axel's avatar
MARMORET Axel committed
50
Nonnegative Tucker Decomposition, which consists in factorizing a tensor T in factors (one per mode) and a core tensor, generally of smaller dimensions than T, which links linearly all factors [6]. This algorithm returns these factors and this core tensor.
Axel Marmoret's avatar
Axel Marmoret committed
51

MARMORET Axel's avatar
MARMORET Axel committed
52 53 54
In the hals condition, this factorization is computed as an ALS algorithm, described in [6], solved with NNLS, and using the toolbox Tensorly [7]. It also uses a gradient update rule for the core.

In the mu condition, this factorization is computed as NMF subproblems (computationally optimized with tensor contractions), described in [3], solved with the Multiplicative Update [3], and using the toolbox Tensorly [7].
Axel Marmoret's avatar
Axel Marmoret committed
55

MARMORET Axel's avatar
MARMORET Axel committed
56
## References
57 58 59 60
[1] N. Gillis and F. Glineur, "Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization," Neural Computation 24 (4): 1085-1105, 2012.

[2] D. D. Lee and H. S. Seung, "Learning the parts of objects by non-negative matrix factorization," Nature, vol. 401, no. 6755, p. 788, 1999.

MARMORET Axel's avatar
MARMORET Axel committed
61 62 63
[3] Févotte, C., & Idier, J. (2011). Algorithms for nonnegative matrix factorization with the β-divergence. Neural computation, 23(9), 2421-2456.

[4] R. A Harshman et al. "Foundations of the PARAFAC procedure: Models and conditions for an" explanatory" multimodal factor analysis," 1970.
64

MARMORET Axel's avatar
MARMORET Axel committed
65
[5] J. E. Cohen, and N. Gillis, "Dictionary-based tensor canonical polyadic decomposition," IEEE Transactions on Signal Processing, 66(7), 1876-1889, 2017.
66

MARMORET Axel's avatar
MARMORET Axel committed
67
[6]  T. G. Kolda, and B. W. Bader, "Tensor decompositions and applications," SIAM review, 51(3), 455-500, 2009.
68

MARMORET Axel's avatar
MARMORET Axel committed
69
[7] J. Kossaifi, Y. Panagakis, A. Anandkumar and M. Pantic, "TensorLy: Tensor Learning in Python," Journal of Machine Learning Research (JMLR), volume 20, number 26, 2019.
70

MARMORET Axel's avatar
MARMORET Axel committed
71
[8] R. A Harshman, "PARAFAC2: Mathematical and technical notes," UCLA working papers in phonetics 22.3044, 1972.
72

MARMORET Axel's avatar
MARMORET Axel committed
73
[9] J. E Cohen and R. Bro, "Nonnegative PARAFAC2: a flexible coupling approach," International Conference on Latent Variable Analysis and Signal Separation. Springer. 2018.