Swarm Intelligence for Dimensionality Reduction: How to Improve the Non-Negative Matrix Factorization with Nature-Inspired Optimization Methods

Introduction

Low-rank approximations are utilized in several content based retrieval and data mining applications, such as text and multimedia mining, web search, etc. and achieve a more compact representation of the data with only limited loss in information. They reduce storage and runtime requirements, and also reduce redundancy and noise in the data representation while capturing the essential associations. The Non-negative Matrix Factorization (NMF, (Lee and Seung 1999)) leads to a low-rank approximation which satisfies non-negativity constraints. NMF approximates a data matrix by where and are the NMF factors. NMF requires all entries in, andto be zero or positive. Contrary to other low-rank approximations such as the Singular Value Decomposition (SVD), these constraints force NMF to produce so-called “additive parts-based” representations. This is an impressive benefit of NMF, since it makes the interpretation of the NMF factors much easier than for factors containing positive and negative entries (Berry, Browne et al. 2007) (Janecek and Gansterer 2010) (Lee and Seung 1999).

The NMF is usually not unique if different initializations of the factors and are used. Moreover, there are several different NMF algorithms which all follow different strategies (e.g. mean squared error, least squares, gradient descent, etc.) and produce different results. Mathematically, the goal of NMF is to find a “good” (ideally the best) solution of an optimization problem with bound constraints in the form , where is the nonlinear objective function of NMF, and is the feasible region (for NMF, is restricted to non-negative values). is usually not convex, discontinuous and may possess many local minima (Stadlthanner, Lutter et al. 2007). Since meta-heuristic optimization algorithms are known to be able to deal well with such difficulties they seem to be a promising choice for improving the quality of NMF. Over the last decades nature-inspired meta-heuristics, including those based on swarm intelligence, have gained much popularity due to their applicability for various optimization problems. They benefit from the fact that they are able to find acceptable results within a reasonable amount of time for many complex, large and dynamic problems (Blackwell 2007). Although they lack the ability to guarantee the optimal solution for a given problem (comparably to NMF), it has been shown that they are able to tackle various kinds of real-world optimization problems (Chiong 2009). Meta-heuristics as well as the principles of NMF are in accordance with the law of sufficiency (Eberhart, Shi et al. 2001): If a solution to a problem is good enough, fast enough and cheap enough, then it is sufficient.