Matrix factorization or factor analysis is an important task helpful in the analysis of high dimensional real world data. There are several well known methods and algorithms for factorization of real data but many application areas including information retrieval, pattern recognition and data mining require processing of binary rather than real data. Unfortunately, the methods used for real matrix factorization fail in the latter case. In this paper we introduce background and initial version of Genetic Algorithm for binary matrix factorization.
Matrix factorization (or matrix decomposition) is an important task in data analysis and processing. A matrix factorization is the right-side matrix product in
A ≈ F1 · F2 · . . . · Fk (1) for the matrix A. The number of factor matrices depends usually on the requirements of given application area. Most often, k = 2 or k = 3. There are several matrix decomposition methods reducing data dimensions and simultaneously revealing structures hidden in the data. Such methods include Singular Value Decomposition (SVD) and Non-negative Matrix Factorization (NMF), which is our subject of interest in this research. 2.1
Non-negative matrix factorization (NMF) [
A ≈ W · H
There are several algorithms for NMF computation based on iterative
minimization of given cost function [
Boolean matrix factorization (BMF) or Boolean factor analysis is the
factorization of data sets in binary (1, 0) alphabet based on Boolean algebra. Boolean
factor analysis is extremely important in computer applications since the natural
data representation for computerized processing is binary. Binary factorization
finds its application in data mining, information retrieval, pattern recognition,
image processing or data compression [
The BMF can be defined in a similar manner as NMF [
A ≈ W ⊗ H (6) where ⊗ stands for Boolean matrix multiplication.
The appeal of BMF lies in the fact that computerized data are binary in its essence and BMF is intensively investigated.
Keprt [
Evolutionary algorithms (EA) are family of iterative stochastic search and
optimization methods based on mimicking successful optimization strategies
observed in nature [
EA operate with population (also known as pool) of artificial individuals
(referred often as items or chromosomes) encoding possible problem solutions.
Encoded individuals are evaluated using objective function which assigns a
fitness value to each individual. Fitness value represents the quality (ranking) of
each individual as solution of given problem. Competing individuals search the
problem domain towards optimal solution [
For the purpose of EAs, a proper encoding representing solutions of given problem as encoded chromosomes suitable for evolutionary search process, is necessary. Finding proper encoding is non-trivial problem dependent task affecting the performance and results of evolutionary search while solving given problem. The solutions might be encoded into binary strings, real vectors or more complex, often tree-like, hierarchical structures, depending on the needs of particular application.
The iterative phase of evolutionary search process starts with an initial population of individuals that can be generated randomly or seeded with potentially good solutions. Artificial evolution consists of iterative application of genetic 1 Matrix A is binary iff ∀ij : [a]ij = 0 ∨ [a]ij = 1 operators (selection, crossover, mutation), introducing to the algorithm evolutionary principles such as inheritance, survival of the fittest and random perturbations. Current population of problem solutions is modified with the aim to form new and hopefully better population to be used in next generation. Iterative evolution of problem solutions ends after satisfying specified termination criteria and especially the criterion of finding optimal solution. After terminating the search process, evolution winner is decoded and presented as the most optimal solution found.
EAs are successful general adaptable concept with good results in many areas. The class of evolutionary techniques consists of more particular algorithms having numerous variants, forged and tuned for specific problem domains. The family of evolutionary algorithms consists of genetic algorithms, genetic programming, evolutionary strategies and evolutionary programming. 3.1
Genetic algorithms (GA) introduced by John Holland and extended by David Goldberg are wide applied and highly successful EA variant. Basic workflow of originally proposed standard generational GA is:
I. Define objective function II. Encode initial population of possible solutions as fixed length binary strings and evaluate chromosomes in initial population using objective function III. Create new population (evolutionary search for better solutions): a. Select suitable chromosomes for reproduction (parents) b. Apply crossover operator on parents with respect to crossover probability to produce new chromosomes (offspring) c. Apply mutation operator on offspring chromosomes with respect to mutation probability. Add newly constituted chromosomes to new population d. Until the size of new population is smaller than size of current population go back to a.
e. Replace current population by new population IV. Evaluate current population using objective function V. Check termination criteria; if not satisfied go back to III.
There are variants of standard generational GA. The differences are mostly
in particular selection, crossover, mutation and replacement strategy [
In this paper, we to propose a Genetic Algorithm for Binary Matrix Factorization (Genetic BMF - GBMF). For that, we first analzye the factors that are to be found by the algorithm and define an algorithm suggesting initial values of the factors.
The factors W and H found by NMF algorithm by Lee and Seung can be straightforwardly interpreted. Columns of W are basis vectors of column space of A and columns of H are weights associated with the base vectors. In order to find out interpretation of the matrix factorization task for GA which might be different, consider a graph-like representation of a matrix:
Then, the factorization can be seen as a task of finding tripartite graph G0 that will exclusively preserve the arcs between the pairs of ‘edge’ vertices from G in the form of a two step long paths through a ‘middle layer’. Intuitively, the number of vertices in middle layer corresponds to r in NMF. The graphs G and G0 from 7 can be depicted as follows:
When adopting this notion of Boolean matrix factorization, the interpretation of factors W and H slightly differs from the interpretation of NMF factors. The rows of H are base vectors of row space of A and rows of W are associated weights. 4.2
In order to provide the genetic algorithm with better than random initial population, a constructive algorithm for suggesting base vectors of matrix row space is defined:
I. Compute the cardinality (number of 1 elements) of the rows of A; divide rows of A to classes AC per cardinality. Let W and H be ’empty’. Let k = 0. II. Randomly pick up row AiC from the row class with lowest cardinality. Let j = 0.
III. For base row hj in H : a. Check whether hj is covered2 by AiC . If not, attach AiC to H as hk, and set W [i, k] = 1. Increase k and go back to II. In case hj is covered by AiC , go to II. b. Let W [i, j] = 1. Let AC = AiC - wj .
i c. If AiC is not zero vector, go back to II.
The rows of the matrix A can be then constructed using linear combinations of the rows of H. 2 i.e. hj − AiC = o where o = (0, 0, . . . , 0) is zero vector.
We propose a genetic algorithm for BMF. It will exploit the initial factors constructed using the algorithm introduced in previous section. The objective function will be Hamming distance between reconstructed and original matrix. Crossover will aim to modify weights factor (matrix W ) and mutation will primarily aim to alter basis vectors (matrix H). The algorithm can be summarized as follows:
I. Create initial population of N (W H) chromosomes and evaluate II. Evolve population a. Select suitable chromosomes for reproduction (parents) b. Apply crossover on matrix W of selected parents. c. With very small probability, mutate W d. Mutate H e. Migrate offspring chromosomes to population III. Evaluate current population using objective function IV. Check termination criteria; if not satisfied go back to II.
The evaluation of chromosomes in population is implemented as comparison of original matrix V to the product of W and H. The fitness function is based on Euclidean distance between V and W H: f =
1 qPi Pj (V [i, j] − W H[i, j])2 (8)
The termination criteria were based on specified threshold defining minimum acceptance of evolved solution and maximum number of generations processed. The maximu number of generations was se to 1000 and the minimum acceptance 0.3.
In this way, the algorithm explores different combinations of base vectors (via crossover) and simultaneously adjust the base vector suggestions. Evolutionary principles will be applied and the factor interpretation maintained. 5
This section provides summary on computer experiments conducted in order to verify proposed algorithms. 5.1
In 4.2 was defined a constructiove algorithm to suggest base vectors for initial matrix factors. We have compared the average error obtained after using random initial factors and initial factors suggested by CAS for several random square matrices. For every matrix dimension n, we have computed the average error (i.e. Hamming distance) between original matrix and its reconstruction. The dimension was reduced to n2 and the experiment was repeated 100 times for each n.
Obviously, the error produced by random initial factors is aproximately twice as big as the error obtained when using CAS initial factors. 5.2
GBMF was implemented and run for some testing binary matrices. Black and white images were chosen as representation of input and output binary matrices for the ease of visual interpretatin of the results.
In all cases, GBMF was run with the following parameters: a population of 50 prospective factors, probability of crossover 0.9 and probability of mutation 0.2. GBMF was executed for 5000 generations.
The algorithm was first tested on a set of bar images. Testing bar images contained white background and black bars – vertical or horizontal lines generated with certain probability (0.2 for horizontal bar and 0.3 for vertical bar). The dimension of testing images was 15 × 25 pixels.
Initially, a small collection of 6 bar images (shown in figure 5.2) was processed by the algorithm to reduce its dimension to 3.
Next, the progam was used to process in the same way a collection of 25 face images taken from the facial expression collection. The images were transformed from grayscale original to black and white (so they could be interpreted as binary matrices). The dimension of testing images was 19 × 19 pixels.
In both cases delivered the algorithm a set of images (i.e. matrices) which clearly share some elements with the original input. Albeit some base images were obtained, they did not contain distinguished features as for instance when using NMF for non-binary matrices. Moreover, the black and white images used for algorithm evaluation are not typical real world binary matrices. Also both binary and real-valued pseudorandom matrices do not contain features significant for matrices describing real world phenomena (i.e. in economics, physics etc.). 6
In this paper, we have introduced initial version of a genetic algorithm for binary matrix factorization. In order to define Genetic Algorithm oriented approach to
BMF, an interpretation of binary factors was presented. Next, an algorithm for lossless BMF was used to create initial binary factors. Genetic BMF was defined, implemented and applied on first sample problems. In the future, we will focus on tuning the GBMF mplementation and evaluation of the algorithm on real world binary matrices. Some matrix properties such as sparsity might be exploited for algorithm modification.