BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.2.3.1//EN TZID:Europe/Paris X-WR-TIMEZONE:Europe/Paris BEGIN:VEVENT UID:3128@i2m.univ-amu.fr DTSTART;TZID=Europe/Paris:20191025T140000 DTEND;TZID=Europe/Paris:20191025T150000 DTSTAMP:20191010T120000Z URL:https://www.i2m.univ-amu.fr/evenements/luc-giffon-quick-means-accelera tion-of-k-means-by-learning-a-fast-transform/ SUMMARY: (...): Luc GIFFON - QuicK-means: Acceleration of K-means by learni ng a fast transform DESCRIPTION:: Luc GIFFON (LIS\, Aix-Marseille Université)K-means -- and th e celebrated Lloyd algorithm -- is more than the clustering method it was originally designed to be. It has indeed proven pivotal to help increase t he speed of many machine learning and data analysis techniques such as ind exing\, nearest-neighbor search and prediction\, data compression\, Radial Basis Function networks\; its beneficial use has been shown to carry over to the acceleration of kernel machines (when using the Nyström method). Here\, we propose a fast extension of K-means\, dubbed QuicK-means\, that rests on the idea of expressing the matrix of the 𝐾\; centroids as a product of sparse matrices\, a feat made possible by recent results devo ted to find approximations of matrices as a product of sparse factors. Usi ng such a decomposition squashes the complexity of the matrix-vector produ ct between the factorized 𝐾\;×𝐷\; centroid matrix 𝐔\ ; and any vector from O(𝐾\;𝐷\;) to O(𝐴\;log𝐴\; +𝐵\;)\, with 𝐴\;=min(𝐾\;\,𝐷\;) and 𝐵\;= max(𝐾\;\,𝐷\;)\, where 𝐷\; is the dimension of the tra ining data. This drastic computational saving has a direct impact in the a ssignment process of a point to a cluster\, meaning that it is not only ta ngible at prediction time\, but also at training time\, provided the facto rization procedure is performed during Lloyd's algorithm. We precisely sho w that resorting to a factorization step at each iteration does not impair the convergence of the optimization scheme and that\, depending on the co ntext\, it may entail a reduction of the training time. Finally\, we provi de discussions and numerical simulations that show the versatility of our computationally-efficient QuicK-means algorithm. https://pageperso.lis-lab .fr/luc.giffon/ END:VEVENT BEGIN:VTIMEZONE TZID:Europe/Paris X-LIC-LOCATION:Europe/Paris BEGIN:DAYLIGHT DTSTART:20190331T030000 TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST END:DAYLIGHT END:VTIMEZONE END:VCALENDAR