Similarity-based Hierarchical Clustering (HC) is a classical unsupervised
machine learning algorithm that has traditionally been solved with heuristic
algorithms like Average-Linkage. Recently, Dasgupta reframed HC as a discrete
optimization problem by introducing a global cost function measuring the
quality of a given tree. In this work, we provide the first continuous
relaxation of Dasgupta's discrete optimization problem with provable quality
guarantees. The key idea of our method, HypHC, is showing a direct
correspondence from discrete trees to continuous representations (via the
hyperbolic embeddings of their leaf nodes) and back (via a decoding algorithm
that maps leaf embeddings to a dendrogram), allowing us to search the space of
discrete binary trees with continuous optimization. Building on analogies
between trees and hyperbolic space, we derive a continuous analogue for the
notion of lowest common ancestor, which leads to a continuous relaxation of
Dasgupta's discrete objective. We can show that after decoding, the global
minimizer of our continuous relaxation yields a discrete tree with a (1 +
epsilon)-factor approximation for Dasgupta's optimal tree, where epsilon can be
made arbitrarily small and controls optimization challenges. We experimentally
evaluate HypHC on a variety of HC benchmarks and find that even approximate
solutions found with gradient descent have superior clustering quality than
agglomerative heuristics or other gradient based algorithms. Finally, we
highlight the flexibility of HypHC using end-to-end training in a downstream
classification task.

该研究提出了一种名为 HypHC 的方法，将传统的基于启发式算法的相似性层次聚类问题转化为一个离散优化问题，并通过连续松弛技术获得全局最优解，该方法通过超蜂窝嵌入实现了离散树到连续表示的映射，并采用解码算法通过叶节点嵌入到树状图的映射，实现了连续优化用于搜索离散二进制树的空间。

从树到连续嵌入再回归：双曲线分层聚类

From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical  Clustering

We propose an adaptive diffusion mechanism to optimize a global cost function
in a distributed manner over a network of nodes. The cost function is assumed
to consist of a collection of individual components. Diffusion adaptation
allows the nodes to cooperate and diffuse information in real-time; it also
helps alleviate the effects of stochastic gradient noise and measurement noise
through a continuous learning process. We analyze the mean-square-error
performance of the algorithm in some detail, including its transient and
steady-state behavior. We also apply the diffusion algorithm to two problems:
distributed estimation with sparse parameters and distributed localization.
Compared to well-studied incremental methods, diffusion methods do not require
the use of a cyclic path over the nodes and are robust to node and link
failure. Diffusion methods also endow networks with adaptation abilities that
enable the individual nodes to continue learning even when the cost function
changes with time. Examples involving such dynamic cost functions with moving
targets are common in the context of biological networks.

我们提出了自适应扩散机制，以分布式方式优化全局代价函数，并将其应用于分布式估计和定位问题。