布尔矩阵分解（BMF）--MEBF论文阅读及代码实现

关于布尔矩阵分解

最近在做有关布尔矩阵分解方面的研究，因为自己的方向需要，找了有关布尔矩阵分解的一干论文看了看。
关于布尔矩阵分解，实际就是对于一个布尔矩阵 A m ∗ n A_{m*n} Am∗n​（其中元素非0即1）来分解成 B m ∗ k B_{m*k} Bm∗k​与 C k ∗ n C_{k*n} Ck∗n​，其中B与C也同样是布尔矩阵（其中元素非0即1），也就是将一个大型的布尔矩阵给分解为两个低秩矩阵的乘积。
其英文为Boolean Matrix Factorization，或者Boolean Matrix decomposition也行，前者用的更多更普遍。其有着很重要的应用，对于一些数据分析方面有着很大的帮助。
不过布尔矩阵分解本身就是一个np难的问题，它不像普通矩阵分解，可以用浮点数，其中方法比如SVD，能够很快的得到可以说是非常准确的分解结果。布尔矩阵分解成布尔矩阵的乘积，势必会有误差，难以准确的分解，同时，很多算法运行起来效率也是非常的低。
可以说，现在应该是没有如同SVD在非布尔矩阵分解方向如此高效准确的布尔矩阵分解方法的，布尔矩阵分解方向的方法可能说只是尽量去提高分解速度以及降低分解误差，根本就达不到说有一个公认的完美的方法。同时，对于稀疏程度不同，规模不同的布尔矩阵的分解，不同方法又会显示出不同的效果，所以该方向可以说还在努力的发展中。
关于布尔矩阵的分解方法，现在提出的有不少，比如ASSO，PANDA以及其plus版本，还有NMF等，本文中介绍的是2019年普渡大学出的一篇文章《Fast and Efficient Boolean Matrix Factorization by Geometric Segmentation》中提出的MEBF方法。

布尔矩阵分解的思路

下面就直接来介绍该方法的思想及算法流程。
首先所谓布尔矩阵分解，实际上就可以等价理解为去在原布尔矩阵上去确定有哪些1稠密的子矩阵。
我们举下面一个例子：

对于这样一个布尔矩阵，我们找它的1稠密子矩阵，很明显，这个矩阵比较规律也比较简单，我们可以进行一个近似，将它看做是两个矩形的叠加。

如上图所示，是红矩形与黑矩形的叠加，我们可以将该矩阵给分解成两个子矩阵的和。

我们将这两个矩阵分别分解为列向量与行向量的乘积（这个很好做到，因为矩形嘛，很均匀），所以便得到了原布尔矩阵的一个分解结果。
结果如下图所示。

如此便是布尔矩阵分解的思路，当然这里的例子十分的简单，所以可以这样简单的理解，实际上，并不可能这样的做。

MEBF思路

介绍完了布尔矩阵分解的大致思路，下面来具体讲讲论文中提出的MEBF。
MEBF的全称是Median Expansion for Boolean Factorization，姑且翻译为中位数扩展balabala，等你看玩整个算法，基本就理解了中位数扩展的含义。

其大致基于这样一些引理：

• 首先我们的问题可以刻画为这样一个表达式： a r g m i n A ∈ { 0 , 1 } n ∗ k , B ∈ { 0 , 1 } k ∗ m ∣ X − A ∗ B ∣ arg min_{A\in\{0,1\}^{n*k},B\in \{0,1\}^{k*m}}|X-A*B| argminA∈{0,1}n∗k,B∈{0,1}k∗m​∣X−A∗B∣这样一个问题，其中A有k列，而B有k行，A中的列向量与B中相对于的行向量的乘积便是一个子矩阵 X I j X_{I_{j}} XIj​​，这k个子矩阵累加起来便是与原矩阵一个最接近的近似。当然，这里的子矩阵因为布尔乘积的问题，一定是矩形。所以根据此引理，我们的任务就是找子矩阵们。
• 然后本文中一个比较重要的引理，就是UTLmatrix with direct SC1P。
  首先说说什么是C1P，C1P就是一个矩阵的的所有行向量中的1都是连续的。而SC1P则是C1P的升级版，不仅对行向量如此，对列向量也是一样。然后UTL是说，一个矩阵，它的列和和行和满足从左到右列和逐渐增加，从上到下，行和逐渐减小的的一个规律。
  引理是当一个矩阵满足UTL和directSC1P且没有全零行或者全零列时，则该矩阵中全1的的子区域由该矩阵的中位数列或中位数行来确定。

基于上面的引理，下面就进行介绍MEBF算法：

我们针对论文中的例子来进行讲解。

对于一个矩阵，我们需要尽可能的去找其median列或者行来去找到（覆盖）最大的稠密的矩形区域。（这是我们的思想）

给定一个Original矩阵 A 11 ∗ 11 A_{11*11} A11∗11​。目标将其分解成 B 11 ∗ 3 B_{11*3} B11∗3​和 C 3 ∗ 11 C_{3*11} C3∗11​的乘积。

根据引理，我们将该矩阵构建成UTL矩阵，即对行与列进行排序，按照行和与列和来排序，将1s集中到矩阵的右上角去。

这其中的黄色列便是此时的median列，明显，这一列有6个1。
然后用这一列去覆盖其他列（即找到长为median列，宽尽可能大的，1尽量多的矩形）
很清晰，这个很好找。

这里整个红色与黄色部分就是我们找到的矩形（可能不连续，因为实际矩阵重排序之后也不一定是连续的，这个没办法，但是总体上是矩形，这就可以了，毕竟是重排序过的，原始矩阵也基本不是连续的，这个不影响），黄色的列是median列。
所以这就是我们找到的第一个子矩阵了（可以说是subMatrix，也可以说是patterns）。
这个子矩阵是一个矩形，那我们就可以得到B的第一列和C的第一行。
明显B的第一列就是我们的median列，而C的第一行就是这个矩形覆盖了哪些列，覆盖了为1，未覆盖为0。


在提取了第一个subMatrix或者说是patterns之后，我们要对矩阵进行一个更新，用原矩阵减去subMatrix，（这里因为我们得到的矩形是一个近似的嘛，可能将0的位置也覆盖到了，所以我们做减法的时候可能会得到负值，所以我们需要将负数置为0）。
然后就会得到一个新的矩阵，我们将它称为residual Matrix，我们就将其看做是新一轮迭代的original matrix。然后重新进行排序，形成UTL矩阵。



如此迭代下去，如果得到的patterns不能让整个矩阵的值变得更小，那么就需要进行weak signal detection，来发现patterns。（这里我们下面介绍具体算法的时候说）

最终的分解结果是这样，彩色的是分解正确覆盖到的，黑色的是未覆盖到的，可以说是误差。

然后分解的两个矩阵是：

MEBF算法流程及分析

下面介绍以下算法流程

首先输入是Original矩阵X，然后t是用于是该列（行）是否覆盖的一个标准，还有一个字母是收敛的一个判定（这个在代码中比较好理解）
输出自然不用说，两个布尔矩阵。

进入循环，当不收敛时一直继续，
首先是使用Bidirectional_growth算法来获取subMatrix的分解结果列向量a和行向量b（结合上面讲的MEBF的思路，应该就知道这里a是什么，b是什么了）。（Bidirectional_growth就是Median expansion）
然后下面就是算一下这里的提取出来的这个patterns是否能让矩阵的误差减小，如果减小的话，便更新，如果不能减小的话，则说明，目前矩阵的信号很小了，需要用weak signal detection来处理。
之后对矩阵进行一个更新。

这便是MEBF整体的一个逻辑。
下面来讲Bidirectional_growth算法。
这个算法就是median expansion操作

这里，很明显，首先对传入的矩阵进行一个重排序操作，使之UTL。然后我们这里分别找median row和median column来覆盖，看看哪个覆盖的效果更好就采用哪个（覆盖的意思就是，我们要用median列去构造一个矩形，尽可能的多包含原矩阵中的1，就相当于我们以median column为刷子，向右刷，尽可能多刷到1，这就是覆盖，也就是expansion）。
举个例子：对于median column，
这里是取引进UTL过的矩阵X的中位数列，即median column赋给d，然后以d来去覆盖其他列，怎么判断d能不能覆盖某一列呢，这里的操作是计算该列与d的相似性，如果相似性高于t，则便是能覆盖，否则便是不能覆盖，所以这里的t等于就是判断两列是否能够近似等价的一个阈值。
明显 t ∈ ( 0 , 1 ] t\in(0,1] t∈(0,1]，t越大，覆盖的越少，但结果越准确，t越小，覆盖的越多，结果越粗糙。
如此e便是一个形如[0,0,0,0,0,1,1,1,1,0]的一个向量。
在判断完这两个向量的乘积是否都能让矩阵的误差便小，判断其与median行的误差谁小之后，边会输出一个误差最小对应的两个向量了。

当信号微弱，不足以使得误差下降时，就会启用weak signal detection算法

Bidirectional_growth不能保证整体的误差能够连续的变小，所以此时需要weak signal detection算法，to identify from a residual matrix，这是原话。
分别从行与列入手，看谁误差小。
以列举例，找出两个列和最大的列，让它们做与运算，则得出一个新的列d，用这个d来去expansion，从而得到e。
如此便是weak detection。

以上便是对于MEBF的介绍与分析。

代码

代码暂时有点问题，能够简单的跑通，但是结果不是太理想，我还在努力修改中，之后放上来一个比较好的版本。

参考文献

Wan C, Chang W, Zhao T, et al. Fast And Efficient Boolean Matrix Factorization By Geometric Segmentation[J]. arXiv, 2019: arXiv: 1909.03991.