Jul 12, 2020
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/α).
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.
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind