In this paper we study certain properties of the GreConD algorithm for Boolean matrix factorisation, a popular technique in Data Mining with binary relational data. This greedy algorithm was inspired by the fact that the optimal number of factors for the Boolean matrix factorisation can be chosen among the formal concepts of the corresponding formal context. In particular, we consider one of the hardest cases (in terms of the numerous of possible factors), the so-called contranominal scales, and show that the output of GreConD is not optimal in this case. Moreover, we formally analyse its output by means of recurrences and generating functions and provide the reader with the closed form for the returned number of factors. An algorithm generating the optimal number of factors and the corresponding product matrices P and Q is also provided by us for the case of contranominal scales.
Boolean data analysis and Formal Concept Analysis are closely related [
quality metrics [
Another fruitful property of Boolean matrices is their cheap bit
representation and related bit operations. The only obstacle for Boolean Matrix
Factorisation to be widely adopted technique so far is that of determination of the
optimal number factors k for Boolean matrices or Schein rank is NP-hard
problem [
One of the earlier proposed algorithm for BMF is GreConD. It follows a
greedy strategy adding attributes one-by-one with subsequent computation of
their closures and is not optimal in general. In this paper we address one very
important for practice case of the input for this algorithm, the contranominal
scale of arbitrary size n, i.e. square Boolean matrix with all ones except the main
diagonal [
The paper is organised as follows. In Section 2, we recall the reader the basic definitions of FCA and BMF and describe GreConD algorithm. In Section 3, we shortly describe GreConD with its pseudocode. In Section 4, we provide the reader with our experimental and theoretical analyses of the algorithm’s suboptimality. The penultimate section, Section 5, presents the optimal algorithm to find BMF for formal contexts of contranominal scales. Finally, Section 6 briefly discusses future prospects and concludes the paper. 2 2.1
Basic FCA definitions. Formal Concept Analysis (FCA) is a branch of
applied algebra and it studies (formal) concepts and their hierarchies [
Definition 1. Formal context K is a triple (G, M, I), where G is a set of objects, M is a set of attributes, and I ⊆ G × M is an incidence binary relation.
The binary relation I is interpreted as follows: for g ∈ G, m ∈ M we write gIm if the object g has the attribute m.
For a formal context K = (G, M, I) and any A ⊆ G and B ⊆ M a pair of mappings is defined:
A↑ = {m ∈ M | gIm for all g ∈ A}, B↓ = {g ∈ G | gIm for all m ∈ B},
these mappings define Galois connection between partially ordered sets (2G, ⊆)
and (2M , ⊆) on disjunctive union of G and M . The set A is called closed set, if
A↑↓ = A [
Definition 2. A formal concept of the formal context K = (G, M, I) is a pair (A, B), where A ⊆ G, B ⊆ M , A↑ = B and B↓ = A. The set A is called the extent, and B is the intent of the formal concept (A, B).
It is evident that the extent and intent of any formal concept are closed sets. The set of all formal concepts of a context K is denoted by B(G, M, I).
The state-of-the-art surveys on advances in FCA theory and its applications
can be found in [
Description of FCA-based BMF. Boolean Matrix Factorisation is a decomposition of the original matrix I ∈ {0, 1}n×m, where Iij ∈ {0, 1}, into a Boolean matrix product P ◦ Q of binary matrices P ∈ {0, 1}n×k and Q ∈ {0, 1}k×m for the smallest possible number of k. We define Boolean matrix product as follows: k (P ◦ Q)ij = _ Pil · Qlj ,
l=1 where W denotes disjunction, and · conjunction.
For example, in collaborative filtering, matrix I can be considered as a matrix of binary relation between set X of objects (users), and a set Y of attributes (items that users have evaluated). In this case, we assume that xIy iff the user x evaluated object y. The triple (X, Y, I) naturally forms a formal context.
Consider a set F ⊆ B(X, Y, I), a subset of all formal concepts of context
(X, Y, I), and introduce matrices PF and QF :
(PF )il =
1, i ∈ Al,
0, i ∈/ Al,
(QF )lj =
1, j ∈ Bl, ,
0, j ∈/ Bl.
where (Al, Bl) is a formal concept from F . We can consider decomposition of
the matrix I into binary matrix product PF and QF as described above. The
following theorems are proved in [
Theorem 1. (Universality of formal concepts as factors). For every I there is F ⊆ B(X, Y, I), such that I = PF ◦ QF .
Theorem 2. (Optimality of formal concepts as factors). Let I = P ◦ Q for n×k and k ×m binary matrices P and Q. Then there exists a F ⊆ B(X, Y, I) of formal concepts of I such that |F | ≤ k and for the n × |F | and |F | × m binary matrices PF and QF we have I = PF ◦ QF .
There are several algorithms for finding PF and QF by calculating formal
concepts based on these theorems [
There are several algorithms for finding PF and QF by calculating formal
concepts based on aforementioned theorems [
Define U = {hi, ji|Ii,j = 1} for a Boolean matrix I. The main idea of the algorithm is to maximize the set
D ⊕ y := ((D ∪ {y})↓ × (D ∪ {y})↓↑) ∩ U successively adding columns to intent D of formal concept (C, D).
Below we provide pseudocode for GreConD.
Algorithm 3.1 GreConD
The set U contains not yet covered object-attribute pairs by any of the previously found factors. When the newly found factor (C, D) is added to F , all the pairs from C × D should be deleted from U (lines 15-18). When U is empty, the GreConD terminates (line 6, the main loop). The inner loop (lines 9–13) maximizes the cardinality D ⊕ j while it is still possible by examining attributes not in D.
In this section we show that GreConD is optimal for ordinal and nominal scales, but not optimal on contranominal scale. We also construct an optimal algorithm for contranominal scale. 4.1
In FCA, scales are used to represent the so-called multi-valued contexts (cf. relational tables in databases) as one-valued contexts; the latter we also consider here as Boolean matrices.
First, let us consider two elementary scales. The nominal scale is defined as a formal context Nn = ({1, . . . , n}, {1, . . . , n}, =) and is used to scale mutually exclusive attributes like traffic light signals (red, green, yellow). The ordinal scale is defined as On = ({1, . . . , n}, {1, . . . , n}, ≤) and is applied in cases where the values are ordered like university grades (poor, normal, good, excellent).
It follows from our experiment that the number of factors obtained by GreConD on ordinal and nominal scales are equal to the size of scales. We can prove that these numbers are optimal.
Proposition 1. The number of factors n obtained by GreConD for a nominal scale Nn is optimal.
Proof. Note that for a nominal scale of size n any concept with nonempty extent and intent has the form ({i}, {i}) (i ∈ {1, . . . , n}). Furthermore, the number of formal concepts is equal to the number of factors by definition. tu Proposition 2. The number of factors n obtained by GreConD for an ordinal On is optimal.
Proof. Note that for the ordinal scale of size n and for any nonempty A ⊆ {max(A), . . . , n} it holds that A↑ = {1, . . . , n}. Besides, {max(A), . . . , n}↓ = {1, . . . , max(A)}. Therefore, concepts for the ordinal scale are ({1, . . . , k}, {k, . . . , n}) for k ∈ {1, . . . , n}. Since GreConD needs to cover every object-attribute pair, each pair ({i}, {i}) for i ∈ {1, . . . , n} should be covered as well, which requires exactly n concepts ({1, . . . , i}, {i, . . . , n}). tu 4.2
For every set S the contranominal scale is defined as NcS = (S, S, 6=). In what follows, we consider Ncn with S = {1, . . . , n} without loss of generality.
Factorizing contranominal scales of sizes from 1 to 128 by GreConD3 we obtain a sequence of the number of factors an (n is the size of a scale): a1 = 0, a2 = 2, a3 = 3, a4 = 4, 3 Our Python implementation of GreConD for these experiments: https://bit.ly/
GreConDsub an = 2 log2 n if ∃k : n = 2k, an = a2blog2 nc + 1 for other n.
Thus analytic form for the sequence is the following.
Conjecture. The number of factors obtained by GreConD on contranominal scale is described by the sequence
an = 2 · blog2 nc + 1 − [n = 2blog2 nc], n being the size of a scale.
One way to obtain a simpler closed form of the considered sequence is to
analyse its generating function [
Let G(z) = P anzn is the associated generating function for the sequence n an. The sequence an can be rewritten in the following way: a1 = 0, a2 = 2, while an = an−1 +blog2 nc−blog2(n−1)c+dlog2 ne−dlog2(n−1)e. One can check that one of the respective differences of rounded logarithms takes on 1 when n = 2k or n − 1 = 2k for some k > 0.
Let us sum anzn as follows: X anzn = n≥2
X an−1zn + X(blog2 nc−blog2(n−1)c+dlog2 ne−dlog2(n−1)e)zn n≥2 n≥2 Let Un = dlog2ne and Ln = blog2nc, then
G(z) = zG(z) +
X Ln−1zn +
X Un−1zn . n≥2 n≥2 n≥2 n≥2 Now, let L(z) = P Lnzn and U (z) P Unzn, then
n≥2 n≥2 G(z) = zG(z) + L(z) − zL(z) + U (z) − zU (z) or
G(z)(1 − z) = (L(z) + U (z))(1 − z) .
For z 6= 1 we have
an = [zn]G(z) = blog2 nc + dlog2 ne .
Next, we show that the number of factors obtained by GreConD on contranominal scale is not optimal.
First, we provide the definition of Schein rank.
Definition 3. [
Note that for contranominal scales of sizes 2, 3, 4, 7 GreConD does find Schein rank, i.e. optimal number of factors. However, for the remaining sizes (n > 1) GreConD finds suboptimal number of factors. 5
Let us construct an algorithm that would factorize contranominal scale with optimal number of factors. We use Sperner’s theorem.
Definition 5. A family of incomparable (with respect to set inclusion) sets is called a Sperner family, or an antichain of sets.
Theorem 4. [
Equality holds iff an antichain consists of all subsets of size dn/2e or all subsets of size bn/2c.
Theorem 3 [
Let us find all combinations of elements from the set {1, . . . , N (n)} by bN (n)/2c
elements (for example, by Algorithm T from [
Based on the constructed object-factor matrix, we find the factor-attribute matrix. We apply the derivation operator ↓ to every factor f in the objectfactor matrix, then we apply the derivation operator operator ↑ to the set of the obtained objects in object-attribute matrix. Finally, we make binary row for the obtained set of attributes and place it in f -row in factor-attribute matrix.
Thus, we get optimal BMF for contranominal scale.
Note that we can simplify the procedure of construction of the factor-attribute matrix using the following property.
Property 1. For contranominal scale of size n and any subsets A and B of sets of objects and attributes respectively it holds that
A↑ = {1, . . . , n}\A; B↓ = {1, . . . , n}\B.
Proof. Using the definition of contranominal scale and the derivation operator(s) we get: A↑ = ∩a∈A({1, . . . , n}\a) = {1, . . . , n}\A.
The proof for B is similar. tu
Now we can remake the recovering of factor-attribute B matrix from objectfactor matrix A. If Ak is the k-th column in the matrix A, then ∼ Ak (here ∼ is a logical negation) is a k-th row in the matrix B.
Example. Let us demonstrate our algorithm on contranominal scale of size
N (5) = 4, hence BMF has 4 factors. Generate 5 different combinations from the set {1, 2, 3, 4}: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}. Therefore, we obtain the object-factor matrix A: 1 1 0 0 1 0 1 0 A = 1 0 0 1. The first column of matrix A consists of vector 1, 1, 1, 0, 0 T , 0 1 1 0
0 1 0 1 so vector 0, 0, 0, 1, 1 is the first row of factor-attribute matrix. Similarly, we fill the rest of the rows in matrix B and obtain the optimal BMF: 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 = 1 0 0 1 ◦ 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 0 0 1 0 1 Proposition 3. The number of optimal BMFs (found by the proposed algorithm) of the contranominal scale of size n > 0 is n! nq , where q = bNN(n( n)/)2c . Proof. Recall that we choose an n-element set from all the combinations of numbers from the set {1, . . . , N (n)} by bN (n)/2c elements in order to get rows of an object-factor matrix. Further, there are n! ways to arrange every obtained n-element set of combinations as rows of object-factor matrix.
We conclude the proof noting that there is a unique way to build the factorattribute matrix having the object-factor matrix. tu
Note that the case n = 1, i.e. when I = (0), has two more solutions in addition to P ◦ Q = (1) ◦ (0); namely, (0) ◦ (1) = (0) ◦ (0). 6
In the paper we considered important case for Boolean matrix factorisation based on our experimental and theoretical analyses of the behaviour of the GreConD algorithm. We hypothesise that the number of output factors for the contranominal scales in case of GreConD is blog2 nc + dlog2 ne based on the substantial observed fragment of its output for different values of the scale size n.
We have also proposed an optimal algorithm w.r.t. Schein rank to find one out of n! nq optimal Boolean matrix factorisation for this case, where q = bNN(n( n)/)2c .
As a future research direction we would like to continue our previous
investigations of Boolean matrix factorisation for collaborative filtering problems [
Acknowledgments. The paper was prepared within the framework of the HSE University Basic Research Program and was also supported in part through computational resources of HPC facilities at HSE University. The first author was also supported by Russian Science Foundation under grant 17-11-01276 at St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, Russia and by RFBR (Russian Foundation for Basic Research) according to the research project No 19-29-01151. The foundations had no role in study design, data collection and analysis, writing the manuscript, and decision to publish.
We would like to thank Profs. Radim Belohlavek, Jan Outrata, Martin
Trnecka, and Vilem Vychodil for lasting collaboration and Prof. Donald Knuth
for personal written explanation of a nontrivial piece from Concrete
Mathematics [