论文标题
通过随机跨越森林的图形tikhonov正则化和插值
Graph Tikhonov Regularization and Interpolation via Random Spanning Forests
论文作者
论文摘要
提出了新型的蒙特卡洛估计量来解决图表正则化（TR）和图表上的插值问题。这些估计器基于随机跨越森林（RSF），其理论特性使得可以分析估计量的理论平均值和方差。我们还展示了如何为这些基于RSF的估计器执行高参数调整。 TR是许多众所周知的算法中的一个组成部分，我们展示了如何轻松适应所提出的估计器，以避免使用普遍的半监督学习，标签传播，牛顿的方法和迭代重新重量最小二乘的昂贵中间步骤。在实验中，我们说明了关于几个问题的建议方法，并提供了有关其运行时间的观察。
Novel Monte Carlo estimators are proposed to solve both the Tikhonov regularization (TR) and the interpolation problems on graphs. These estimators are based on random spanning forests (RSF), the theoretical properties of which enable to analyze the estimators' theoretical mean and variance. We also show how to perform hyperparameter tuning for these RSF-based estimators. TR is a component in many well-known algorithms, and we show how the proposed estimators can be easily adapted to avoid expensive intermediate steps in generalized semi-supervised learning, label propagation, Newton's method and iteratively reweighted least squares. In the experiments, we illustrate the proposed methods on several problems and provide observations on their run time.
