TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Scalable optimization of neighbor embedding for visualization

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko30th International Conference on Machine Learning, ICML 2013
KustantajaInternational Machine Learning Society (IMLS)
Sivut786-794
Sivumäärä9
PainosPART 1
TilaJulkaistu - 2013
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
Tapahtuma30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, Yhdysvallat
Kesto: 16 kesäkuuta 201321 kesäkuuta 2013

Conference

Conference30th International Conference on Machine Learning, ICML 2013
MaaYhdysvallat
KaupunkiAtlanta, GA
Ajanjakso16/06/1321/06/13

Tiivistelmä

Neighbor embedding (NE) methods have found their use in data visualization but are limited in big data analysis tasks due to their O(n2) complexity for n data samples. We demonstrate that the obvious approach of subsampling produces inferior results and propose a generic approximated optimization technique that reduces the NE optimization cost to O(n log n). The technique is based on realizing that in visualization the embedding space is necessarily very low-dimensional (2D or 3D), and hence efficient approximations developed for n-body force calculations can be applied. In gradient-based NE algorithms the gradient for an individual point decomposes into "forces" exerted by the other points. The contributions of close-by points need to be computed individually but far-away points can be approximated by their "center of mass", rapidly computable by applying a recursive decomposition of the visualization space into quadrants. The new algorithm brings a significant speed-up for medium-size data, and brings "big data" within reach of visualization.