Active Learning Convex Halfspaces on Graphs
Dec 6, 2021
Speakers
Maximilian Thiessen
Speaker · 0 followers
Thomas Gärtner
Speaker · 0 followers
About
We systematically study the query complexity of learning geodesically convex halfspaces on vertex-labelled graphs. Geodesic convexity is a natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We prove upper bounds on the query complexity linear in the treewidth and the minimum hull set size but only logarithmic in the diameter. We show tight lower bounds corresponding to well-established separation axioms. Additionally, we identify the Radon number as a central parameter bounding the query complexity and the VC dimension. While previous bounds typically depend on the cut size of the labelling, all parameters in our bounds can be computed from the unlabelled graph. We empirically compare our proposed approach with other active learning algorithms and provide evidence that ground-truth communities in real-world graphs are often convex.We systematically study the query complexity of learning geodesically convex halfspaces on vertex-labelled graphs. Geodesic convexity is a natural generalisation of Euclidean convexity and allows the definition of convex sets and halfspaces on graphs. We prove upper bounds on the query complexity linear in the treewidth and the minimum hull set size but only logarithmic in the diameter. We show tight lower bounds corresponding to well-established separation axioms. Additionally, we identify the…
Organizer
NeurIPS 2021
Account · 1.9k followers
About 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.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Data Centric AI
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
SketchGen: Generating Constrained CAD Sketches
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Data-Centric AI with Programmatic Supervision
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Manifold Sampler: Function-guided protein design by deep manifold sampling
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Generalized and Discriminative Few-Shot Object Detection via SVD-Dictionary Enhancement
Watch later
Aming Wu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Probability Paths and the Structure of Predictions over Time
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%