论文标题
通过随机跨越森林的反微量估计的差异降低
Variance Reduction for Inverse Trace Estimation via Random Spanning Forests
论文作者
论文摘要
跟踪$ \ tr（q（\ ma {l} + q \ ma {i}）^{ - 1}）$，其中$ \ ma {l} $是对称对角线的对称矩阵，是某些机器学习问题的兴趣数量。但是，如果矩阵尺寸较大，则其直接计算是不切实际的。最先进的方法包括Hutchinson的估计器与迭代求解器以及基于随机跨越森林的估计器（图上的随机过程）。 在这项工作中，我们展示了通过众所周知的差异技术来改善基于森林的估计器的两种方法，即控制变体和分层采样。实施这些技术很容易，并且相对于最先进的算法提供了实质性差异，从而产生可比或更好的性能。
The trace $\tr(q(\ma{L} + q\ma{I})^{-1})$, where $\ma{L}$ is a symmetric diagonally dominant matrix, is the quantity of interest in some machine learning problems. However, its direct computation is impractical if the matrix size is large. State-of-the-art methods include Hutchinson's estimator combined with iterative solvers, as well as the estimator based on random spanning forests (a random process on graphs). In this work, we show two ways of improving the forest-based estimator via well-known variance reduction techniques, namely control variates and stratified sampling. Implementing these techniques is easy, and provides substantial variance reduction, yielding comparable or better performance relative to state-of-the-art algorithms.
