On Margin-Based Cluster Recovery with Oracle Queries
6. prosince 2021
Řečníci
Marco Bressan
Speaker · 0 followers
Nicolò Cesa-Bianchi
Speaker · 0 followers
Silvio Lattanzi
Speaker · 0 followers
Andrea Paudice
Speaker · 0 followers
O prezentaci
We study an active cluster recovery problem where, given a set of n points and an oracle answering queries like "are these two points in the same cluster?", the task is to recover exactly all clusters using as few queries as possible. We begin by introducing a simple but general notion of margin between clusters that captures, as special cases, the margins used in previous work, the classic SVM margin, and standard notions of stability for center-based clusterings. Then, under our margin assumptions we design algorithms that, in a variety of settings, recover all clusters exactly using only O(log n) queries. For the Euclidean case, ℝ^m, we give an algorithm that recovers arbitrary convex clusters, in polynomial time, and with a number of queries that is lower than the best existing algorithm by Θ(m^m) factors. For general pseudometric spaces, where clusters might not be convex or might not have any notion of shape, we give an algorithm that achieves the O(log n) query bound, and is provably near-optimal as a function of the packing number of the space. Finally, for clusterings realized by binary concept classes, we give a combinatorial characterization of recoverability with O(log n) queries, and we show that, for many concept classes in Euclidean spaces, this characterization is equivalent to our margin condition. Our results show a deep connection between cluster margins and active cluster recoverability.We study an active cluster recovery problem where, given a set of n points and an oracle answering queries like "are these two points in the same cluster?", the task is to recover exactly all clusters using as few queries as possible. We begin by introducing a simple but general notion of margin between clusters that captures, as special cases, the margins used in previous work, the classic SVM margin, and standard notions of stability for center-based clusterings. Then, under our margin assumpt…
Organizátor
NeurIPS 2021
Account · 1.9k followers
O organizátorovi (NeurIPS 2021)
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Tight Accounting in the Shuffle Model of Differential Privacy
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Variable Importance on Medical Images and Socio-Demographic Data
Watch later
Ahmad Chamma, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Neural Network Ensemble Approach to System Identification
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
FLEX: Unifying Evaluation for Few-Shot NLP
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
The Effect of Algorithmic Tools on Child Welfare Decision Making: A Preliminary Evaluation
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Multiple Descent: Design Your Own Generalization Curve
Watch later
Lin Chen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%