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

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

Andreas Janecek (University of Vienna, Austria) and Ying Tan (Peking University, China)
DOI: 10.4018/978-1-5225-0788-8.ch060
OnDemand PDF Download:
$37.50

Abstract

Low-rank approximations allow for compact representations of data with reduced storage and runtime requirements and reduced redundancy and noise. The Non-Negative Matrix Factorization (NMF) is a special low-rank approximation that allows for additive parts-based, interpretable representation of the data. Various properties of NMF are similar to Swarm Intelligence (SI) methods: indeed, most NMF objective functions and most SI fitness functions are non-convex, discontinuous, and may possess many local minima. This chapter summarizes efforts on improving convergence, approximation quality, and classification accuracy of NMF using five different meta-heuristics based on SI and evolutionary computation. The authors present (1) new initialization strategies for NMF, and (2) an iterative update strategy for NMF. The applicability of the approach is illustrated on data sets coming from the areas of spam filtering and email classification. Experimental results show that both optimization strategies are able to improve NMF in terms of faster convergence, lower approximation error, and/or better classification accuracy.
Chapter Preview
Top

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.

Complete Chapter List

Search this Book:
Reset