Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck
At the heart of both lossy compression and clustering is a trade-off between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this trade-off. We focus on the optimization of the Deterministic Information Bottleneck (DIB) object...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-05-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/6/771 |
| _version_ | 1827660459993464832 |
|---|---|
| author | Andrew K. Tan Max Tegmark Isaac L. Chuang |
| author_facet | Andrew K. Tan Max Tegmark Isaac L. Chuang |
| author_sort | Andrew K. Tan |
| collection | DOAJ |
| description | At the heart of both lossy compression and clustering is a trade-off between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this trade-off. We focus on the optimization of the Deterministic Information Bottleneck (DIB) objective over the space of hard clusterings. To this end, we introduce the <i>primal</i> DIB problem, which we show results in a much richer frontier than its previously studied Lagrangian relaxation when optimized over discrete search spaces. We present an algorithm for mapping out the Pareto frontier of the primal DIB trade-off that is also applicable to other two-objective clustering problems. We study general properties of the Pareto frontier, and we give both analytic and numerical evidence for logarithmic sparsity of the frontier in general. We provide evidence that our algorithm has polynomial scaling despite the super-exponential search space, and additionally, we propose a modification to the algorithm that can be used where sampling noise is expected to be significant. Finally, we use our algorithm to map the DIB frontier of three different tasks: compressing the English alphabet, extracting informative color classes from natural images, and compressing a group theory-inspired dataset, revealing interesting features of frontier, and demonstrating how the structure of the frontier can be used for model selection with a focus on points previously hidden by the cloak of the convex hull. |
| first_indexed | 2024-03-09T23:52:01Z |
| format | Article |
| id | doaj.art-d6d08c4552c04db3ac41992cd5200ac8 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T23:52:01Z |
| publishDate | 2022-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-d6d08c4552c04db3ac41992cd5200ac82023-11-23T16:32:52ZengMDPI AGEntropy1099-43002022-05-0124677110.3390/e24060771Pareto-Optimal Clustering with the Primal Deterministic Information BottleneckAndrew K. Tan0Max Tegmark1Isaac L. Chuang2Department of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USADepartment of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USADepartment of Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USAAt the heart of both lossy compression and clustering is a trade-off between the fidelity and size of the learned representation. Our goal is to map out and study the Pareto frontier that quantifies this trade-off. We focus on the optimization of the Deterministic Information Bottleneck (DIB) objective over the space of hard clusterings. To this end, we introduce the <i>primal</i> DIB problem, which we show results in a much richer frontier than its previously studied Lagrangian relaxation when optimized over discrete search spaces. We present an algorithm for mapping out the Pareto frontier of the primal DIB trade-off that is also applicable to other two-objective clustering problems. We study general properties of the Pareto frontier, and we give both analytic and numerical evidence for logarithmic sparsity of the frontier in general. We provide evidence that our algorithm has polynomial scaling despite the super-exponential search space, and additionally, we propose a modification to the algorithm that can be used where sampling noise is expected to be significant. Finally, we use our algorithm to map the DIB frontier of three different tasks: compressing the English alphabet, extracting informative color classes from natural images, and compressing a group theory-inspired dataset, revealing interesting features of frontier, and demonstrating how the structure of the frontier can be used for model selection with a focus on points previously hidden by the cloak of the convex hull.https://www.mdpi.com/1099-4300/24/6/771multi-objectiveoptimizationParetofrontierinformationbottleneck |
| spellingShingle | Andrew K. Tan Max Tegmark Isaac L. Chuang Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck Entropy multi-objective optimization Pareto frontier information bottleneck |
| title | Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck |
| title_full | Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck |
| title_fullStr | Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck |
| title_full_unstemmed | Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck |
| title_short | Pareto-Optimal Clustering with the Primal Deterministic Information Bottleneck |
| title_sort | pareto optimal clustering with the primal deterministic information bottleneck |
| topic | multi-objective optimization Pareto frontier information bottleneck |
| url | https://www.mdpi.com/1099-4300/24/6/771 |
| work_keys_str_mv | AT andrewktan paretooptimalclusteringwiththeprimaldeterministicinformationbottleneck AT maxtegmark paretooptimalclusteringwiththeprimaldeterministicinformationbottleneck AT isaaclchuang paretooptimalclusteringwiththeprimaldeterministicinformationbottleneck |