Events Calendar

O grupo de Grafos e Algoritmos da UFRJ convida a todos para o seminário a ser realizado em 29/05/2019 (quartafeira). Local  Coppe/Sistemas, Sala H324B, 13:30h.
Palestrante:
Eduardo S. Laber
Título:
On the approximability of Information Theoretic Clustering
Resumo:
An impurity measure is a function that assigns a ddimensional vector v, with nonnegative components, to a nonnegative value so that the more homogeneous v with respect to the values of its components, the larger its impurity. Well known examples of impurity measures are the Entropy and the Gini impurities. We study the problem of clustering based on impurity measures. Given a collection V of n many ddimensional vectors, an impurity measure I and an integer k, the goal is to find a partition P of V into k groups V_1,...,V_k so as to minimize the sum of the impurities of the groups in P, where the impurity of a group U is the impurity of the vector \sum_{v \in U } v. Impurity minimization has been widely used as quality assessment measure in probability distribution clustering (KLdivergence) as well as in categorical clustering. However, in contrast to the case of metric based clustering, the current knowledge of impurity measure based clustering in terms of approximation and inapproximability results is much more limited.
In this talk we discuss some results that contribute to narrow this gap. Among them we highlight (i) a proof that the problem, for Entropy impurity, does not admit a PTAS even when all vectors of V have the same \ell_1 norm and (ii) a polynomial time O(log^2(min{k,d})approximation algorithm. The former solves a problem that remained open in previous work [Chaudhuri and McGregor COLT 08; Ackermann et. al. ECCC 11] while the latter is the first polynomial time algorithm with approximation guarantee independent of the number of points/vector and not relying on any restriction on the components of the vectors for producing partitions with minimum entropy.
In order to assess the practical applicability of our theoretical findings we show that a new method that relies on these findings obtains clustering with impurity close to a kmeans based method, with the advantage of being 23 orders of magnitude faster.
The main results from our research were/will be presented in the international Conference on Machine Learning (ICML 2018, 2019)
Observações:
Consulte também a nossa página de seminários: http://grafos.cos.ufrj.br/grafos/seminarios.php