1

我正在尝试确定是否可以并行化机器学习算法的训练方面。训练中计算量大的部分涉及 Cholesky 分解正定矩阵（协方差矩阵）。我将尝试纯粹根据矩阵代数来构建这个问题。如果您需要更多信息，请告诉我。

假设我们有一个块矩阵（协方差矩阵，但这与问题无关）

 
M = AB  
    B* C

其中 A 和 C 与来自两个不同集合的训练数据相关。A 和 B 都是正定的。为简单起见，我们还假设 A 和 C 的大小为 nxn。

有一个用于执行块 Cholesky 分解的公式。请参阅http://en.wikipedia.org/wiki/Block_LU_decomposition。总结一下，我们有以下结果。

M = 卢

其中（* 表示转置）

L = A^{1/2} 0
    B*A^{-*/2} Q^{1/2}

在哪里

Q = C - B*A^{-1}B

现在假设已经进行了与矩阵 A 和 C 相关的训练，因此我们对 A 进行了 Cholesky 分解，并且 C 给出 A^{1/2} 和 C^{1/2}（因此可以直接使用前向替换计算逆 A^{-1/2} 和 C^{-1/2}）。

用我们现在拥有的这些数量重写 Q。

Q = Q^{1/2} Q^{*/2} = C^{1/2} C^{*/2} - B* A^{-*/2}A^{-1/2}乙

我的问题是：鉴于这种设置，是否可以代数计算 Q^{1/2} 而无需对 Q 应用 cholesky 分解。或者换句话说，我可以使用 C^{1/2} 来帮助我Q^{1/2} 的计算。如果这是可能的，那么就可以轻松地并行化培训。

提前感谢您的任何回复。对不起矩阵排版。特别是排版数学或矩阵有什么明智的方法吗？

马特。

4

2 回答 2

3

您可以通过一系列 cholesky 更新来做到这一点：

（下面我使用 ' 进行转置以避免与乘法混淆）

如果 A 的 Cholesky 因子是 a，C 是 c，那么 Q 的方程可以写成

Q = c*c' - beta'*beta 其中 beta = inverse(a) B （即解 a beta = B for beta）

如果我们为 beta 的第 i 列写 b[i]，那么

Q = c*c' - 和 b[i]*b[i]'

找到cholesky分解

c c' - x x'（其中 x 是向量，c 是下三角形）

被称为 1 级 Cholesky 降级。Golub 和 van Loan有一个稳定的算法

于 2010-07-14T19:46:06.417 回答
1

我想我已经找到了答案，尽管它并不完全像我希望的那样。

除去机器学习上下文，我的问题归结为知道 C^{1/2} 是否有助于计算 Q^{-1/2}。我将在下面详细介绍，但为了避免追逐，答案是肯定的，但仅关于稳定性而不是计算（目前无法证明是这种情况，但相当肯定）。

对于为什么对稳定性的回答是肯定的，我们看一下原始问题中的定义 Q 已重新排列如下。

Q = C - B* A^{-1} B = (C^{1/2} + B*A^{-*/2})(C^{1/2} - B*A^{-* /2})*

通过事先知道 C^{1/2}，我们可以计算 Q 而无需直接反转 A。直接反演在数值上不稳定。

遗憾的是，尽管我对这个主题进行了大量研究，但似乎 $C^{1/2}$ 并不能帮助精确计算 Q^{-1/2}。最好的方法似乎是使用上面的 C^{1/2} 计算 Q，然后使用 Cholesky 将 Q 分解为 Q^{1/2}，然后向前替换以计算 Q^{-1/2}。

进一步的研究

我没有详细研究的一个领域是是否可以使用 C^{1/2} 来近似 Q^{-1/2}。类似于使用 C^{1/2} 作为起点的迭代方法。我不知道任何这样的迭代近似过程，但我会继续搜索。我什至可以以此为中心开始一个新的问题。

如果我有任何重大突破，我会为大家更新。

于 2010-07-07T18:20:12.080 回答