Clustering by transitive propagation
We present a global optimization algorithm for clustering data given the ratio of likelihoods that each pair of data points is in the same cluster or in different clusters. To define a clustering solution in terms of pairwise relationships, a necessary and sufficient condition is that belonging to the same cluster satisfies transitivity. We define a global objective function based on pairwise likelihood ratios and a transitivity constraint over all triples, assigning an equal prior probability to all clustering solutions. We maximize the objective function by implementing max-sum message passing on the corresponding factor graph to arrive at an O(N^3) algorithm. Lastly, we demonstrate an application inspired by mutational sequencing for decoding random binary words transmitted through a noisy channel.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringglobal-optimizationSimilar Papers 제목 키워드 기반
Real World Games Look Like Spinning Tops
This paper investigates the geometrical properties of real world games (e.g. Tic-Tac-Toe, Go, StarCraft II). We hypothesise that their geometrical structure resemble a spinning top, with the upright axis representing tra…
ClusteringStarcraftStarcraft IIThe blessing of transitivity in sparse and stochastic networks
The interaction between transitivity and sparsity, two common features in empirical networks, implies that there are local regions of large sparse networks that are dense. We call this the blessing of transitivity and it…
ClusteringTransitive Distance Clustering with K-Means Duality
We propose a very intuitive and simple approximation for the conventional spectral clustering methods. It effectively alleviates the computational burden of spectral clustering - reducing the time complexity from O(n^3) …
ClusteringImage SegmentationSemantic SegmentationA Generic Framework for Clustering Vehicle Motion Trajectories
The development of autonomous vehicles requires having access to a large amount of data in the concerning driving scenarios. However, manual annotation of such driving scenarios is costly and subject to the errors in the…
Autonomous VehiclesClusteringGenerative Adversarial NetworkTrajectory ClusteringAnalysis of Argument Structure Constructions in the Large Language Model BERT
This study investigates how BERT processes and represents Argument Structure Constructions (ASCs), extending previous LSTM analyses. Using a dataset of 2000 sentences across four ASC types (transitive, ditransitive, caus…
ClusteringLanguage ModelingLanguage ModellingLarge Language Model