  In supervised clustering, standard techniques for learning a pairwise
dissimilarity function often suffer from a discrepancy between the training and
clustering objectives, leading to poor cluster quality. Rectifying this
discrepancy necessitates matching the procedure for training the dissimilarity
function to the clustering algorithm. In this paper, we introduce a method for
training the dissimilarity function in a way that is tightly coupled with
hierarchical clustering, in particular single linkage. However, the appropriate
clustering algorithm for a given dataset is often unknown. Thus we introduce an
approach to supervised hierarchical clustering that smoothly interpolates
between single, average, and complete linkage, and we give a training procedure
that simultaneously learns a linkage function and a dissimilarity function. We
accomplish this with a novel Exponential Linkage function that has a learnable
parameter that controls the interpolation. In experiments on four datasets, our
joint training procedure consistently matches or outperforms the next best
training procedure/linkage function pair and gives up to 8 points improvement
in dendrogram purity over discrepant pairs.
