Agglomerative Info-Clustering
This is an incremental improvement for researchers in information theory and clustering, offering computational benefits over previous methods.
The paper tackles the problem of clustering random variables by merging those with the highest multivariate mutual information, enabling early stopping for desired cluster size and accuracy. It results in an efficient algorithm based on submodularity and duality principles.
An agglomerative clustering of random variables is proposed, where clusters of random variables sharing the maximum amount of multivariate mutual information are merged successively to form larger clusters. Compared to the previous info-clustering algorithms, the agglomerative approach allows the computation to stop earlier when clusters of desired size and accuracy are obtained. An efficient algorithm is also derived based on the submodularity of entropy and the duality between the principal sequence of partitions and the principal sequence for submodular functions.