ASSO 布尔矩阵分解算法 详细分析

布尔矩阵分解是：将布尔矩阵输入，分解成多个结果矩阵的乘积，结果矩阵都是布尔型
ASSO的话，是一个比较经典的算法，其目标为$A\approx B?X$，其中$B$是basis matrix，可以理解为模式，也可以看做ksvd的字典矩阵，而$X$可以看做稀疏码矩阵
ASSO是一个贪心的算法，和KSVD、MEBF一样，都是选取 当前最大误差下降的候选列 来下降误差，最终选择出所有的basis vector

ASSO 算法流程

整体是比较简单的，和MEBF很像，可以去看看我的MEBF的博客（布尔矩阵分解 代码实现（BMF）–MEBF论文阅读）
下面我就按照论文中的逻辑来介绍

主要分为下面两个步骤

find the candidate

这一步是来提前构建 候选列向量
在之后进行构建B时，其所有的列向量都来自于我们现在构建的 候选列向量

• 对于输入矩阵$A$，我们取它的任意两行$a_i,a_j$，那么我们就可以判断这两个行向量是否关联
  • 关联是单向的，$i=>j$
  • 关联：$(i=>j)=(a_i?a_j)/(a_i?a_i)>\tau$
  • $\tau$是一个预先设定的参数
  • 即当$a_i$大部分都包含在$a_j$中时，则可以判定$a_i$到$a_j$是关联的
• 建立 关联矩阵$C$，其中$c_{ij}=1or0$，当$a_i$到$a_j$是关联时，其值为1
  • 需要注意的是，关联是单向的，反向不一定成立
• 这里的时间复杂度为$O(n^{2}m)$，$A$的维度是$n?m$，$C$的维度是$n?n$
• 这里可以通过剪枝，将时间开销降低一半，因为本身相异的向量积只需要计算一次嘛，矩阵是对称的
• 关联矩阵只需要构建一次

construction the matrix B

此时就是来进行实际的矩阵分解，也就是来构建B，B构建好了，X也就构建好了
本步骤的目标就是，从C中选择出k个列向量，作为B，从而实现$A_{n?m}\approx B_{n?k}?X_{k?m}$

• ASSO采样的是贪心的算法，就是迭代k次，从C的所有列向量中选择k个出来，每一次迭代，都找能够使当前误差下降最大的那个列向量
• 如何计算当前误差最大：
  • $cover(A,B,X,w)=w|(i,j):a_{ij}=1\wedge (B?X{)}_{ij}=1|?|(i,j):a_{ij}=0\wedge (B?X{)}_{ij}=1|$
  • 原文中的公式，挺唬人的，实际上就是把B和X相乘的结果与原矩阵A进行比较，A中为1且乘积矩阵为1的统计出来（恢复正确的个数），A中为0且乘积为1的统计出来（恢复错误的个数），二者做差
  • w是一个参数，作为一个权重，因为我们的目标肯定是 恢复正确的要比恢复错误的多的多才行嘛，所以w一般在$(0,1]$才行
  • 该公式就可以计算误差了，该值越大，说明误差下降越多，恢复越好
• 如何实际的去计算误差呢？
  • 公式中是出现B和X的，说明我们至少需要$b_l$和$x_l$的，这两怎么生成
  • $b_l$比较简单，挨个的去尝试$C$中的所有列向量$c_l$
  • 而$x_l$则是利用$b_l$去在A中找出的，用$b_l$去与A中的每个列向量进行比较，将上面的cover公式改一改，$cover(a_j,b_l,x_{l}j,w)=w|(i):a_{ij}=1\wedge b_{lj}=1|?|(i):a_{ij}=0\wedge B_{lj}=1|$。即看$b_l$能否覆盖$a_j$（正确超过错误的，和矩阵cover是一样的）
  • 这里原文中是这样写的： if b1 covers more 1s in aj than it covers 0s, b1 is used to cover aj (i.e. x1j is set to 1)
  • 这样的话就可以计算出列向量与行向量，再把它们加进矩阵中，计算误差下降，选入最大的那个
• 如此，选出最大的，将$b_l$和$x_l$加入矩阵B、X，然后再重复，直到重复k次为止
• 这里，实际上，某一个$c_l$如果被选择了，就不会被再次选择了，所以这个也可以略微剪枝跳过，可以平均跳过$k^2/2$个次数

思路分析

• 主要在于关联矩阵的构建，其他都比较easy
  • 与MEBF相比，MEBF是直接选取的中位数列
  • 而ASSO是选择的关联矩阵
  • 关联矩阵的每一个列向量$c_s$，实际上意义为：
    • 矩阵A的行向量$a_i$，与其他行向量的关联情况
    • 既然行向量之间是关联的，那么$a_{i}j=1$，其他行向量$a_{x}j$为1的可能性非常大
    • 那么这样，就能轻易的构建出矩形
• 所以ASSO对于basis列向量一定要存在A中的这个 列利用条件 并不是很严格，甚至不需要，相比来说MEBF则是一定的，因为它是中位数列
  • 中位数列会存在说，当前矩阵有矩形，但是照不出来的情况

时间复杂度

• find candidate阶段
  • 时间复杂度很好算因为n个行向量，计算两两关联关系，再加上关联关系是比较行向量，所以是$O(n^{2}m)$
• construction matrix B阶段
  • 首先，需要k次迭代
  • 其次，每次迭代要遍历所有的$c_l$，这需要n次
  • 然后，对于每个$c_l$需要进行误差下降的计算，这实际是矩阵的乘法和矩阵的加减，为$O(nm)$
  • 所以总的时间复杂度为$O(k{n}^{2}m)$
• 综上，总的时间复杂度为 $O(k{n}^{2}m)$

剪枝思路

• 首先，在上文中有提到，每次选择了$c_l$之后，后面就不会再用了，所以实际是只被使用了一次，所以这里用set保存已经选择的l，每次用$O(1)$来判断一下，可以减少$O(nm{k}^2/2)$的时间
• 其次，矩阵中可能会存在相同的列向量，or行向量，那么它们的计算结果肯定是一样的，那么就可以去重
  • 值的注意的是，这里的去重涉及到了hash，无法对向量进行散列，所以需要对向量进行编码，我是将向量转换为字符串的形式，实际上挺快的，可以参考

原文链接

https://helda.helsinki.fi/bitstream/handle/10138/21376/matrixde.pdf?sequence=1&isAllowed=y
ASSO算法部分在p60左右

代码复现

• 目前打算是复现一下的，毕竟MEBF我也复现过了
• 看用不用的上，有没有时间，有必要的话我会用python写一遍，然后上传到github上