Spanning trees are an important primitive in many data analysis tasks, when a
data set needs to be summarized in terms of its "skeleton", or when a
tree-shaped graph over all observations is required for downstream processing.
Popular definitions of spanning trees include the minimum spanning tree and the
optimum distance spanning tree, a.k.a. the minimum routing cost tree. When
searching for the shortest spanning tree but admitting additional branching
points, even shorter spanning trees can be realized: Steiner trees.
Unfortunately, both minimum spanning and Steiner trees are not robust with
respect to noise in the observations; that is, small perturbations of the
original data set often lead to drastic changes in the associated spanning
trees. In response, we make two contributions when the data lies in a Euclidean
space: on the theoretical side, we introduce a new optimization problem, the
"(branched) central spanning tree", which subsumes all previously mentioned
definitions as special cases. On the practical side, we show empirically that
the (branched) central spanning tree is more robust to noise in the data, and
as such is better suited to summarize a data set in terms of its skeleton. We
also propose a heuristic to address the NP-hard optimization problem, and
illustrate its use on single cell RNA expression data from biology and 3D point
clouds of plants.

基于欧几里得空间中的数据，本研究提出了一个新的优化问题 ——“（分支）中心生成树”，它包含了之前提到的所有定义作为特例，并从理论和实践两个方面证明了（分支）中心生成树相对于数据中的噪声更具鲁棒性，并更适合以其骨架来总结数据集。此外，本研究还提出了一种应对 NP 难优化问题的启发式方法，并在生物学的单细胞 RNA 表达数据和植物的 3D 点云数据上进行了展示。

中央生成树问题

The Central Spanning Tree Problem

We investigate the problem of active learning on a given tree whose nodes are
assigned binary labels in an adversarial way. Inspired by recent results by
Guillory and Bilmes, we characterize (up to constant factors) the optimal
placement of queries so to minimize the mistakes made on the non-queried nodes.
Our query selection algorithm is extremely efficient, and the optimal number of
mistakes on the non-queried nodes is achieved by a simple and efficient mincut
classifier. Through a simple modification of the query selection algorithm we
also show optimality (up to constant factors) with respect to the trade-off
between number of queries and number of mistakes on non-queried nodes. By using
spanning trees, our algorithms can be efficiently applied to general graphs,
although the problem of finding optimal and efficient active learning
algorithms for general graphs remains open. Towards this end, we provide a
lower bound on the number of mistakes made on arbitrary graphs by any active
learning algorithm using a number of queries which is up to a constant fraction
of the graph size.

本研究通过研究树上的主动学习问题，分析了一种查询选择算法，提出了一种简单而高效的 mincut 分类器，并使用生成树设计了一种高效的算法，关键词包括：主动学习、二进制标签、查询选择算法、mincut 分类器、生成树。

树和图上的主动学习

Active Learning on Trees and Graphs

In this paper we present decomposable priors, a family of priors over
structure and parameters of tree belief nets for which Bayesian learning with
complete observations is tractable, in the sense that the posterior is also
decomposable and can be completely determined analytically in polynomial time.
This follows from two main results: First, we show that factored distributions
over spanning trees in a graph can be integrated in closed form. Second, we
examine priors over tree parameters and show that a set of assumptions similar
to (Heckerman and al. 1995) constrain the tree parameter priors to be a
compactly parameterized product of Dirichlet distributions. Beside allowing for
exact Bayesian learning, these results permit us to formulate a new class of
tractable latent variable models in which the likelihood of a data point is
computed through an ensemble average over tree structures.

本文提出了可分解先验，一种针对树形信念网络的先验族。在完整观测数据下，可以通过贝叶斯学习来确定结构和参数，后验概率也是可分解的，并且可以在多项式时间内完全确定。