User:Siyuwj/沙盒/4

对非负矩阵分解估计的直观解释：矩阵V被两个更小的矩阵W和H表示，它们的乘机可以近似地重建V

非负矩阵分解（英語：non-negative matrix factorization，NMF），也被称为非负矩阵估计（英語：non-negative matrix approximation）是多元统计分析和线性代数中的一组算法的统称。这些算法将一个矩阵分解为（通常是）两个矩阵W和H，三个矩阵都没有负元素。这一非负性使得最终求解的矩阵更容易被分析。由于这一问题通常不能被准确地求解，因而数值近似方法是常用的求解方法。

非负矩阵分解在计算机视觉、文本聚类、化学计量学和推荐系统中都有应用 。

历史

在化学计量学中，非负矩阵分解被称为“自模式曲线分辨”，由很长的研究历史。 在这一框架中，右边矩阵中的向量并非是离散向量，而是连续的曲线。一群芬兰研究者也曾经在20世纪90年代中期进行过类似的“正矩阵分解”研究工作。 当丹尼尔李和塞巴斯蒂安宋研究了这一算法的性质并对两类分解问题提出了一些简单有效的算法之后，“非负矩阵分解”这一名称开始为人熟知。

背景

使得矩阵V为两个矩阵W和H的乘积，即

$\mathbf {V} =\mathbf {W} \mathbf {H} \,.$

这一矩阵乘积可以实现为将矩阵W的列向量使用矩阵H中的参数进行线性组合得到矩阵V的列向量来计算。亦即，V的每一列都可以用下面的方式来计算：

$\mathbf {v} _{i}=\mathbf {W} \mathbf {h} _{i}\,,$

其中，v_i是乘积矩阵V的第i个列向量，h_i是乘积矩阵H的第i个列向量。

When multiplying matrices, the dimensions of the factor matrices may be significantly lower than those of the product matrix and it is this property that forms the basis of NMF. NMF generates factors with significantly reduced dimensions compared to the original matrix. For example, if V is an m×n matrix, W is an m×p matrix, and H is a p×n matrix then p can be significantly less than both m and n.

Here's an example based on a text-mining application:

• Let the input matrix (the matrix to be factored) be V with 10000 rows and 500 columns where words are in rows and documents are in columns. That is, we have 500 documents indexed by 10000 words. It follows that a column vector v in V represents a document.
• Assume we ask the algorithm to find 10 features in order to generate a features matrix W with 10000 rows and 10 columns and a coefficients matrix H with 10 rows and 500 columns.
• The product of W and H is a matrix with 10000 rows and 500 columns, the same shape as the input matrix V and, if the factorization worked, also a reasonable approximation to the input matrix V.
• From the treatment of matrix multiplication above it follows that each column in the product matrix WH is a linear combination of the 10 column vectors in the features matrix W with coefficients supplied by the coefficients matrix H.

This last point is the basis of NMF because we can consider each original document in our example as being built from a small set of hidden features. NMF generates these features.

It's useful to think of each feature (column vector) in the features matrix W as a document archetype comprising a set of words where each word's cell value defines the word's rank in the feature: The higher a word's cell value the higher the word's rank in the feature. A column in the coefficients matrix H represents an original document with a cell value defining the document's rank for a feature. This follows because each row in H represents a feature. We can now reconstruct a document (column vector) from our input matrix by a linear combination of our features (column vectors in W where each feature is weighted by the feature's cell value from the document's column in H.

Types

Approximate non-negative matrix factorization

Usually the number of columns of W and the number of rows of H in NMF are selected so the product WH will become an approximation to V. The full decomposition of V then amounts to the two non-negative matrices W and H as well as a residual U, such that: V = WH + U. The elements of the residual matrix can either be negative or positive.

When W and H are smaller than V they become easier to store and manipulate. Another reason for factorizing V into smaller matrices W and H, is that if one is able to approximately represent the elements of V by significantly less data, then one has to infer some latent structure in the data.

Convex non-negative matrix factorization

In standard NMF, matrix factor $W\in \Re _{+}^{m\times k}$， i.e., W can be anything in that space. Convex NMF restricts $W$ to a be convex combination of the input data vectors $(v_{1},\cdots ,v_{n})$. This greatly improves the quality of data representation of W. Furthermore, the resulting matrix factor H becomes more sparse and orthogonal.

Nonnegative rank factorization

In case the nonnegative rank of V is equal to its actual rank, V=WH is called a nonnegative rank factorization. The problem of finding the NRF of V, if it exists, is known to be NP-hard.

Different cost functions and regularizations

There are different types of non-negative matrix factorizations. The different types arise from using different cost functions for measuring the divergence between V and WH and possibly by regularization of the W and/or H matrices.

Two simple divergence functions studied by Lee and Seung are the squared error (or Frobenius norm) and an extension of the Kullback–Leibler divergence to positive matrices (the original Kullback–Leibler divergence is defined on probability distributions). Each divergence leads to a different NMF algorithm, usually minimizing the divergence using iterative update rules.

The factorization problem in the squared error version of NMF may be stated as: Given a matrix $\mathbf {V}$ find nonnegative matrices W and H that minimize the function

$F(\mathbf {W} ,\mathbf {H} )=\|\mathbf {V} -\mathbf {WH} \|_{F}^{2}$

Another type of NMF for images is based on the total variation norm.

When L1 regularization (akin to Lasso) is added to NMF with the mean squared error cost function, the resulting problem may be called non-negative sparse coding due to the similarity to the sparse coding problem, although it may also still be referred to as NMF.

Algorithms

There are several ways in which the W and H may be found: Lee and Seung's multiplicative update rule has been a popular method due to the simplicity of implementation. Since then, a few other algorithmic approaches have been developed.

Some successful algorithms are based on alternating non-negative least squares: in each step of such an algorithm, first H is fixed and W found by a non-negative least squares solver, then W is fixed and H is found analogously. The procedures used to solve for W and H may be the same or different, as some NMF variants regularize one of W and H. Specific approaches include the projected gradient descent methods, the active set method, and the block principal pivoting method among several others.

The currently available algorithms are sub-optimal as they can only guarantee finding a local minimum, rather than a global minimum of the cost function. A provably optimal algorithm is unlikely in the near future as the problem has been shown to generalize the k-means clustering problem which is known to be NP-complete. However, as in many other data mining applications, a local minimum may still prove to be useful.

Exact NMF

Exact solutions for the variants of NMF can be expected (in polynomial time) when additional constraints hold for matrix V. A polynomial time algorithm for solving nonnegative rank factorization if V contains a monomial sub matrix of rank equal to its rank was given by Campbell and Poole in 1981. Kalofolias and Gallopoulos (2012) solved the symmetric counterpart of this problem, where V is symmetric and contains a diagonal principal sub matrix of rank r. Their algorithm runs in O(rm^2) time in the dense case. Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) give a polynomial time algorithm for exact NMF that works for the case where one of the factors W satisfies the separability condition.

Relation to other techniques

In Learning the parts of objects by non-negative matrix factorization Lee and Seung proposed NMF mainly for parts-based decomposition of images. It compares NMF to vector quantization and principal component analysis, and shows that although the three techniques may be written as factorizations, they implement different constraints and therefore produce different results.

NMF as a probabilistic graphical model: visible units (V) are connected to hidden units (H) through weights W, so that V is generated from a probability distribution with mean $\sum _{a}W_{ia}h_{a}$.

It was later shown that some types of NMF are an instance of a more general probabilistic model called "multinomial PCA". When NMF is obtained by minimizing the Kullback–Leibler divergence, it is in fact equivalent to another instance of multinomial PCA, probabilistic latent semantic analysis, trained by maximum likelihood estimation. That method is commonly used for analyzing and clustering textual data and is also related to the latent class model.

It has been shown NMF is equivalent to a relaxed form of K-means clustering: matrix factor W contains cluster centroids and H contains cluster membership indicators, when using the least square as NMF objective. This provides theoretical foundation for using NMF for data clustering.

NMF can be seen as a two-layer directed graphical model with one layer of observed random variables and one layer of hidden random variables.

NMF extends beyond matrices to tensors of arbitrary order. This extension may be viewed as a non-negative version of, e.g., the PARAFAC model.

Other extensions of NMF include joint factorisation of several data matrices and tensors where some factors are shared. Such models are useful for sensor fusion and relational learning.

NMF is an instance of the nonnegative quadratic programming (NQP) as well as many other important problems including the support vector machine (SVM). However, SVM and NMF are related at a more intimate level than that of NQP, which allows direct application of the solution algorithms developed for either of the two methods to problems in both domains.

Uniqueness

The factorization is not unique: A matrix and its inverse can be used to transform the two factorization matrices by, e.g.,

$\mathbf {WH} =\mathbf {WBB} ^{-1}\mathbf {H}$

If the two new matrices $\mathbf {{\tilde {W}}=WB}$ and $\mathbf {\tilde {H}} =\mathbf {B} ^{-1}\mathbf {H}$ are non-negative they form another parametrization of the factorization.

The non-negativity of $\mathbf {\tilde {W}}$ and $\mathbf {\tilde {H}}$ applies at least if B is a non-negative monomial matrix. In this simple case it will just correspond to a scaling and a permutation.

More control over the non-uniqueness of NMF is obtained with sparsity constraints.

Clustering property

NMF has an inherent clustering property, i.e., it automatically clusters the columns of input data $\mathbf {V} =(v_{1},\cdots ,v_{n})$.

More specifically, the approximation of $\mathbf {V}$ by $\mathbf {V} \simeq \mathbf {W} \mathbf {H}$ is achieved by minimizing the error function

$\min _{W,H}||V-WH||_{F},$ subject to $W\geq 0,H\geq 0.$

If we add additional orthogonality constraint on $H$, i.e., $HH^{T}=I$, then the above minimization is identical to the minimization of K-means clustering.

Furthermore, the computed $H$ gives the cluster indicator, i.e., if $\mathbf {H} _{kj}>0$, that fact indicates input data $v_{j}$ belongs/assigned to $k^{th}$ cluster. And the computed $W$ gives the cluster centroids, i.e., the $k^{th}$ column gives the cluster centroid of $k^{th}$ cluster.

When the orthogonality $HH^{T}=I$ is not explicitly imposed, the orthogonality holds to a large extent, and the clustering property holds too, as in most applications of NMF.

When the error function is replaced by Kullback–Leibler divergence, it is proved shown that NMF is identical to the Probabilistic latent semantic analysis, a popular document clustering method.

Applications

Text mining

NMF can be used for text mining applications. In this process, a document-term matrix is constructed with the weights of various terms (typically weighted word frequency information) from a set of documents. This matrix is factored into a term-feature and a feature-document matrix. The features are derived from the contents of the documents, and the feature-document matrix describes data clusters of related documents.

One specific application used hierarchical NMF on a small subset of scientific abstracts from PubMed. Another research group clustered parts of the Enron email dataset with 65,033 messages and 91,133 terms into 50 clusters. NMF has also been applied to citations data, with one example clustering Wikipedia articles and scientific journals based on the outbound scientific citations in Wikipedia.

Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) have given polynomial-time algorithms to learn topic models using NMF. The algorithm assumes that the topic matrix satisfies a separability condition that is often found to hold in these settings.

Spectral data analysis

NMF is also used to analyze spectral data; one such use is in the classification of space objects and debris.

Scalable Internet distance prediction

NMF is applied in scalable Internet distance (round-trip time) prediction. For a network with $N$ hosts, with the help of NMF, the distances of all the $N^{2}$ end-to-end links can be predicted after conducting only $O(N)$ measurements. This kind of method was firstly introduced in Internet Distance Estimation Service (IDES). Afterwards, as a fully decentralized approach, Phoenix network coordinate system is proposed. It achieves better overall prediction accuracy by introducing the concept of weight.

Non-stationary speech denoising

Speech denoising has been a long lasting problem in audio signal processing. There are lots of algorithms for denoising if the noise is stationary. For example, the Wiener filter is suitable for additive Gaussian noise. However, if the noise is non-stationary, the classical denoising algorithms usually have poor performance because the statistical information of the non-stationary noise is difficult to estimate. Schmidt et al. use NMF to do speech denoising under non-stationary noise, which is completely different from classical statistical approaches.The key idea is that clean speech signal can be sparsely represented by a speech dictionary, but non-stationary noise cannot. Similarly, non-stationary noise can also be sparsely represented by a noise dictionary, but speech cannot.

The algorithm for NMF denoising goes as follows. Two dictionaries, one for speech and one for noise, need to be trained offline. Once a noisy speech is given, we first calculate the magnitude of the Short-Time-Fourier-Transform. Second, separate it into two parts via NMF, one can be sparsely represented by the speech dictionary, and the other part can be sparsely represented by the noise dictionary. Third, the part that is represented by the speech dictionary will be the estimated clean speech.

Bioinformatics

NMF has been successfully applied to bioinformatics.

Current research

Current research in nonnegative matrix factorization includes, but not limited to,

(1) Algorithmic: searching for global minima of the factors and factor initialization.

(2) Scalability: how to factorize million-by-billion matrices, which are commonplace in Web-scale data mining, e.g., see Distributed Nonnegative Matrix Factorization (DNMF)

(3) Online: how to update the factorization when new data comes in without recomputing from scratch.

See also

• Online NMF (Online non-negative matrix factorization)
• Multilinear algebra
• Multilinear subspace learning
• Tensor
• Tensor decomposition
• Tensor software

Sources and external links

Others

• J. Shen, G. W. Israël. A receptor model using a specific non-negative transformation technique for ambient aerosol. Atmospheric Environment. 1989, 23 (10): 2289–2298. doi:10.1016/0004-6981(89)90190-X. 
• Pentti Paatero. Least squares formulation of robust non-negative factor analysis. Chemometrics and Intelligent Laboratory Systems. 1997, 37 (1): 23–35. doi:10.1016/S0169-7439(96)00044-5. 
• Raul Kompass. A Generalized Divergence Measure for Nonnegative Matrix Factorization. Neural Computation. 2007, 19 (3): 780–791. PMID 17298233. doi:10.1162/neco.2007.19.3.780. 
• Liu, W.X. and Zheng, N.N. and You, Q.B. Nonnegative Matrix Factorization and its applications in pattern recognition (PDF). Chinese Science Bulletin. 2006, 51 (17–18): 7–18. doi:10.1007/s11434-005-1109-6. 
• Ngoc-Diep Ho, Paul Van Dooren and Vincent Blondel. Descent Methods for Nonnegative Matrix Factorization. 2008. arXiv:0801.3199  [cs.NA]. 
• Andrzej Cichocki, Rafal Zdunek and Shun-ichi Amari. Nonnegative Matrix and Tensor Factorization. IEEE Signal Processing Magazine. 2008, 25 (1): 142–145. doi:10.1109/MSP.2008.4408452. 
• Cédric Févotte, Nancy Bertin, and Jean-Louis Durrieu. Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis. Neural Computation. 2009, 21 (3): 793–830. PMID 18785855. doi:10.1162/neco.2008.04-08-771. 
• Ali Taylan Cemgil. Bayesian Inference for Nonnegative Matrix Factorisation Models. Computational Intelligence and Neuroscience. 2009, 2009 (2): 1. PMC 2688815 . PMID 19536273. doi:10.1155/2009/785152. 

[[Category:线性代数]] [[Category:矩阵理论]] [[Category:多元统计]] [[Category:机器学习]]