Correlation Clustering with Asymmetric Classification Errors
Jul 12, 2020
Speakers
Jafar Jafarov
Speaker · 0 followers
Sanchit Kalhan
Speaker · 0 followers
Konstantin Makarychev
Speaker · 0 followers
Yury Makarychev
Speaker · 0 followers
About
In the Correlation Clustering problem, we are given a weighted graph G with its edges labelled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge e has weight w_e ∈ [ α w, w ] and every "dissimilar" edge e has weight w_e ≥α w (where α≤ 1 and w > 0 is a scaling parameter). We give a (3 + 2 log_e (1/α)) approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of Ω(log 1/α).In the Correlation Clustering problem, we are given a weighted graph G with its edges labelled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge e has weight w_e ∈ [ α w, w ] and every "dissimilar" edge e has weight w_e…
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
About ICML 2020
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
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
Adaptive Adversarial Multi-task Representation Learning
Watch later
Yuren Mao, …
Gradient Temporal-Difference Learning with Regularized Corrections
Watch later
Deep Graph Library an Update
Watch later
Few-shot Domain Adaptation by Causal Mechanism Transfer
Watch later
Planning to Explore via Self-Supervised World Models
Watch later
Superpolynomial Lower Bounds on Learning One-Layer Neural Nets with Gradient Descent
Watch later
Surbhi Goel, …