8M is an old but nowadays virtually unknown algorithm for Boolean matrix factorization. In this paper, we provide a detailed analysis of 8M. We demonstrate by experiments that even though the algorithm uses a limited insight into the decomposition problem, its performance is reasonably good even from today's perspective. We analyze all the steps involved in 8M, provide a first complete description of 8M, and the relationships of 8M to the main currently available factorization algorithms. It turns out that 8M involves certain interesting concepts, which are not exploited by the current algorithms. We discuss the prospect of these concepts and, furthermore, propose an enhancement of 8M which is based on the current understanding of Boolean matrix factorization and significantly improves the performance of the original 8M.
1.1
In the past decade or so, considerable research has been devoted to Boolean
matrix factorization (BMF, called also Boolean matrix decomposition). This
research has resulted in various new methods of analysis and processing of Boolean
data and has also contributed to our understanding of Boolean (binary, yes/no)
data as regards foundational aspects. A vast majority of the respective research
contributions has been devoted to the design of factorization algorithms, which
is also the subject of our paper. To name some of the best-known algorithms
(more detailed information about some of these algorithms is provided in the
subsequent sections), let us recall Tiling [
Interestingly, there exists an old BMF algorithm, namely the 8M algorithm,
which is virtually unknown in the present research on BMF. This fact is
remarkable particularly in view of our experimental evaluations which demonstrate that
the 8M algorithm performs reasonably well even from today’s perspective. We
learned about this algorithm from Hana Rˇ ezankov´a who used it in her
various works on comparison of various clustering and factorization methods; see
e.g. the references in [
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp.
167{178, Department of Computer Science, Palacky University Olomouc, 2018.
Copying permitted only for private and academic purposes.
the literature. The goal of this paper is threefold. First, we provide a complete
description of the 8M algorithm, including its pseudo-code and the description
of its principles from today’s perspective. Second, we propose an improvement
of the 8M algorithm, which turns out to improve its performance reasonably.
Third, we utilize one of the principles of 8M to enhance the performance of two
standard algorithms. Note at this point that we discussed the 8M algorithm in
our yet unpublished paper [
The set of all n × m Boolean matrices shall be denoted {0, 1}n×m and the particular matrices by I, J , and the like. An input matrix I shall primarily be interpreted as an object-attribute incidence matrix (hence the symbol I). That is, the entry Iij corresponding to the row i and the column j is either 1 or 0, indicating that the object i does or does not have the attribute j, respectively. The ith row and jth column vector of I is denoted by Ii and I j , respectively. In BMF, one generally attempts to find for a given I ∈ {0, 1}n×m matrices A ∈ {0, 1}n×k and B ∈ {0, 1}k×m for which
I (approximately) equals A ◦ B, where ◦ is the Boolean matrix product, i.e. (A ◦ B)ij = maxlk=1 min(Ail, Blj ). A decomposition of I into A ◦ B may be interpreted as a discovery of k factors that exactly or approximately explain the data: Interpreting I, A, and B as object-attribute, object-factor, and factor-attribute matrices, model (1) reads: The object i has the attribute j if and only if there exists factor l such that l applies to i and j is one of the particular manifestations of l. The least k for which an exact decomposition I = A ◦ B exists is called the Boolean rank (or Schein rank) of I. The approximate equality in (1) is assessed in BMF by means of the metric E(·, ·), defined for C, D ∈ {0, 1}n×m by
E(C, D) = Pm,n i,j=1 |Cij − Dij |.
(1) (2) The following particular variants of the BMF problem, relevant to this paper, are considered in the literature.
– Discrete Basis Problem (DBP, [
Given I ∈ {0, 1}n×m and a positive integer k, find A ∈ {0, 1}n×k and B ∈
{0, 1}k×m that minimize E(I, A ◦ B).
– Approximate Factorization Problem (AFP, [
Given I and prescribed error ε ≥ 0, find A ∈ {0, 1}n×k and B ∈ {0, 1}k×m with k as small as possible such that E(I, A ◦ B) ≤ ε.
These problems reflect two important views of BMF: DBP emphasizes the importance of the first few (presumably most important) factors; AFP emphasizes the need to account for (and thus to explain) a prescribed portion of data. In general, the committed error E(I, A ◦ B) has two parts, namely E(I, A ◦ B) = Eu(I, A ◦ B) + Eo(I, A ◦ B), (3) where Eu(I, A ◦ B) = |{hi, ji | Iij = 1 and (A ◦ B)ij = 0}| and Eo(I, A ◦ B) = |{hi, ji | Iij = 0 and (A ◦ B)ij = 1}| are the so-called undercovering error and overcovering error, respectively, which view shall be used below. 2 2.1 8M
The 8M method is one of the many data analysis methods available in an old and widely used statistical software package known as BMDP. The acronym “BMDP” stands for “Bio-Medical Data Package” (some sources say “BioMeDical Package”). The package was developed primarily for biomedical applications since the 1960s at the University of California in Los Angeles (UCLA) under the leadership of W. J. Dixon.1 BMDP was originally available for free, later through BMDP Statistical Software, Inc., and then by its subsidiary, Statistical Solutions Ltd. As of 2017, BMDP is no longer available.2
BMDP and its methods are described in several editions of manuals, starting
with a 1961 manual of BMD, a direct predecessor of BMDP. In our description of
8M, we use the 1992 edition [
The 8M method has been added to BMDP in the late 1970s: It was not part of the 1979 manual but it is part along with other new methods in the next version, whose revised printing appeared in 1983. According to this edition, 8M is based on research done by the statistician M. Ray Mickey of the UCLA, was designed by Mickey with contributions from Laszlo Engelman, and was programmed by Peter Mundle and Engelman.3 2.2
Even though the description of 8M in [
Basic Idea We first describe the basic idea of 8M. The algorithm takes as its input four parameters: an n × m Boolean matrix I (object-attribute matrix), a number k of desired factors, and two auxiliary parameters, a number init of initial factors, and a number cost used to refine the factors being computed. The desired output consists of n × k and k × m Boolean matrices A (object-factor matrix) and B (factor-attribute matrix).
The algorithm starts by computing init initial factors. Then the algorithm iteratively computes new factors until k desired factors are obtained. The way 8M computes the factors is very different from the current BMF algorithms in two respects. First is the very way of generating a new factor. Second is the fact that the previously generated factors are revisited and dropped. The corresponding procedures are described in detail below.
Even though 8M’s revisiting of the previously generated factors is done in a
straightforward manner, it represents an interesting property. Namely, while the
undercovering and overcovering error, Eu and Eo, see (3), seem symmetric, they
have a different role in the design of BMF algorithms: Due to the NP-hardness
of the various versions of the decomposition problem [
Detailed Description and Pseudocode of 8M (algorithm 1) To compute n × k and k × m Boolean matrices A and B form the given n × m Boolean matrix I, the prescribed number init of initial factors, the desired number k of factors, and the parameter cost , the algorithm 8M (algorithm 1) proceeds as follows. First, init initial factors are computed (l. 1) as explained below. Note at this point that by default, init = k − 2 but init is generally set by the user. The variable f storing the number of the currently computed factors is set accordingly (l. 2). The matrices A and B are then refined (l. 3) by the procedure RefineMatricesAB described below. The algorithm then enters a loop (l. 5–17) whose purpose is to add new factors and remove some of the previously generated ones until the desired number k of factors is reached for the second time or all 1s in I are covered
Input: Boolean n × m matrix I, desired number of factors k, number init of initial factors, number cost
Output: Boolean matrices A and B add column j of Δ+ with the largest count of 1s as new column to A add row of 0s as new row to B and set entry j of this row to 1 f ← f + 1 RefineMatricesAB(A, B, I, cost) if another two new factors were added then remove column A (f−2) from A and row B(f−2) from B f ← f − 1
RefineMatricesAB(A, B, I, cost) by A ◦ B, i.e. Iij ≤ (A ◦ B)ij for all i, j holds (l. 5). Whenever a factor is added or removed, A and B are refined. Adding and removing factors is performed according to the following scheme. One starts with f = init factors, adds two factors so that f + 2 factors are obtained, then removes the factor generated two steps back, i.e. the f th factor, adds another two factors, removes a factor generated two steps back, and so on. Hence, starting with init = 2 factors, one successively obtains 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, etc. factors. One stops when the desired number k of factors is obtained the second time. For instance, if k = 6 one computes the sequence 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6 of factors and the last six factors are the final factors output by the algorithm (provided the algorithm does not stop due to the second condition in l. 5).
The initial factors are computed by ComputeInitialFactors (algorithm 2) as follows. First, an m × m matrix C is computed in which Cij = 1 iff column i is included in column j in I (i.e. Iqi ≤ Iqj for each q). One then goes through the rows i of C, i = 1, 2, . . . , and adds them as new rows of B until init rows have been added: row i of C is added to B provided there exists j with Cij = 1 such that no row previously added to B contains 1 at position j.
Initialization of the factors is a key step in 8M in that the quality of the computed factorization depends on it. Below we propose a new way to initialize. At this point, let us point out an interesting observation. Computing the association matrix in the Asso algorithm is a kind of initialization. In particular,
Input: n × m Boolean matrix I and the number of initial factors init Output: init × m Boolean matrix B the vectors of the association matrix serve as the candidate B-parts of factors. Now, it is easy to observe that to select the rows of the association matrix, Asso uses basically the same strategy as 8M, only more general. Where 8M tests inclusion of columns i and j (l. 3 of algorithm 2), Asso tests whether the degree of partial inclusion of column i in column j exceeds a user-specified threshold τ (or whether the confidence of the association rule {i} ⇒ {j} exceeds τ in terms of Asso). Setting τ = 1 would yield the same vectors in the association matrix of Asso as what 8M uses as the initial factors. Even though we do not explore this observation in this paper, is shall be explored further.
Input: Boolean matrices A, B, I, number cost 1 repeat 2 RefineMatrixA(A, B, I, cost) 3 RefineMatrixB(A, B, I, cost) 4 until loop executed 3 times or A and B did not change
Refining of A and B by RefineMatricesAB (algorithm 3) consists in performing a cycle until A and B do not change but at most three times, in which A is computed from I, B, and the parameter cost by a so-called Boolean regression described in RefineMatrixA (algorithm 4), followed by computing symmetrically B using RefineMatrixB. A new factor is computed in l. 6–8 of 8M by computing first the positive part Δ+ of the discrepancy matrix Δ = I − A ◦ B, one adds to A as new column the column j of Δ+ containing the largest number of 1s, and adds to B a row of 0s with 1 at position j. For space reasons, we do not describe the meaning of Boolean regression further here; it shall be described in an extended version of this paper.
Input: Boolean matrices A, B, I and cost
Our evaluation involves the real-world datasets Apj [
We used in the experimental evaluation the algorithms: Tiling, Asso, GreConD, Hyper, and PaNDa (see section 1). 3.2
In our evaluation, we use the so-called coverage c of the input data I by the first l computed factors, i.e. the n × l and l × m matrices A and B, defined by c(l) = 1 − E(I, A ◦ B)/|I|, in which |I| is the number of 1s in I. For 8M we used the default recommendation cost = 1 and used various values for init .
Fig. 1 presents a comparison of the selected current BMF algorithms with the 8M method. The graphs depict the coverage c(l) of the first l factors generated by the algorithms. One may observe that 8M compares fairly well with the current algorithms. It even outperforms PaNDa on all these datasets and on most of those we experimented with. On some data, 8M outperforms Asso and very often it outperforms Hyper in its coverage by the first few factors.
Fig. 2 presents a comparison of the basic 8M algorithm with its enhanced version denoted 8M+, which consists in a simple improvement of the initialization step of 8M. Namely, since the purpose of initialization in 8M is to obtain some reasonably good factors and since the initialization of 8M is rather simplistic, we exploited the very fast strategy of the GreConD algorithm to compute the first init factors. These have the additional advantage of committing no overcovering error. One may observe from the graphs that the improvement is significant. Moreover, taking into account Fig. 1, one can see that this improvement makes the new algorithm an interesting rival to the current algorithms. 3.3
It turns out that the idea of revisiting the previously generated factors may easily be implemented in one of the currently best BMF algorithms, GreConD, and yields a significant improvement as regards exact and almost exact factorizations. In our modification of GreConD, we revisit—every time a new factor is generated as in the original GreConD—the previously generated factors. If removal of a factor under consideration would result in an increase in the error E not larger than p × |I|, where p is a parameter, we removed the factor. In Table 1, the columns represent the original GreConD and its modifications for p = 0, 0.01, . . . , 0.05, the rows labeled “k” represent the number of factors obtained by the particular algorithm on the given dataset, and the row labeled “c” contains the coverage of the computed factorization. Thus, for instance, when factorizing the Mushroom data, the original GreConD needs 120 factors to obtain exact factorization. Our modification with p = 0 requires only 113 factors for exact factorization and only 61 factors for computing a highly accurate factorization, namely with coverage 0.951. Since such behavior is typical, we find it (e) Set
X1
20 25 30 k (number of factors) (f ) Set
X2 5 10 15 35 40 45 50 5 10 15 35 40 45 50
Radim
Belohlavek
Chess 10 20 50 60 70 10 20
30 l (number of factors)
40 (b)
Firewall 1 40 50 60 70 l (number of factors) (c) Mushroom 10 20 30 80 90 100 110
50 8M 8M+ 8M 8M+ 8M 8M+ 120 of the first l factors on real data: 8M vs. 8M+. very interesting and find the idea of revisiting factors worth further exploration. Note that we did similar improvements with similar effects to Asso. In addition to the fact that a description and detailed experimental evaluation of 8M were long due, we believe that the most interesting finding for future research is the property of 8M to revisit and possibly drop the previously computed factors. This idea is appealing particularly for algorithms performing general BMF, i.e. those committing overcovering error because, unlike the symmetric undercovering error, overcovering error can only increase if an algorithm does not revisit and modify the previously computed factors. Our straightforward implementation of this idea to GreConD and Asso yields an improvement which represents a promising sign of a usefulness of this idea, which hence needs to be further explored. Another topic worth further investigation is the regression procedure of 8M. While we described how it works, it is not yet properly understood why this procedure, which is analogous to statistical regression, actually works and delivers reasonable results.
R. Belohlavek acknolwedges support by the ECOP (Education for Competitiveness Operational Programme) project No. CZ.1.07/2.3.00/20.0059, which was co-financed by the European Social Fund and the state budget of the Czech Republic (the present research has been conducted in the follow-up period of this project), and by grant IGA 2018 of Palacky´ University Olomouc, No. IGA PrF 2018 030.