{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4025","id":53022850,"number":4025,"title":"[MRG] Cemoody/bhtsne Barnes-Hut t-SNE","user":{"login":"cemoody","id":3419930,"avatar_url":"https://avatars.githubusercontent.com/u/3419930?v=3","gravatar_id":"","url":"https://api.github.com/users/cemoody","html_url":"https://github.com/cemoody","followers_url":"https://api.github.com/users/cemoody/followers","following_url":"https://api.github.com/users/cemoody/following{/other_user}","gists_url":"https://api.github.com/users/cemoody/gists{/gist_id}","starred_url":"https://api.github.com/users/cemoody/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cemoody/subscriptions","organizations_url":"https://api.github.com/users/cemoody/orgs","repos_url":"https://api.github.com/users/cemoody/repos","events_url":"https://api.github.com/users/cemoody/events{/privacy}","received_events_url":"https://api.github.com/users/cemoody/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":32,"created_at":"2014-12-29T06:37:30Z","updated_at":"2015-01-20T15:33:49Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4025","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4025","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/4025.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/4025.patch"},"body":"## Introduction\r\n\r\nThis PR presents the Barnes-Hut implementation of t-SNE. t-SNE is used to visualize high-dimensional data in a low dimensional space that attempts preserve the pairwise high-dimensional similarities in a low-dimensional embedding. The Barnes-Hut algorithm, which is used by astrophysicists to perform N-body simulations, allows the calculation of the t-SNE embedding in O(NlogN) time instead of O(N^2). \r\n\r\nThis effectively allows us to learn embeddings of data sets with millions of elements instead of tens of thousands.\r\n\r\n## Example\r\n\r\nAn IPython Notebook is available where we've put together simple install instructions & a demo of both methods:\r\nhttp://nbviewer.ipython.org/urls/gist.githubusercontent.com/cemoody/01135ef2f26837548360/raw/76ce7f0bac916a516501ead719b513b22430cad0/Barnes-Hut%20t-SNE%20Demo.ipynb\r\n\r\n![bhtsne](https://cloud.githubusercontent.com/assets/3419930/5566392/24d8b7dc-8edb-11e4-9e67-4f319fc6dc59.png)\r\n\r\n## Performance\r\nThis compares the timings for the Barnes-Hut approximation against the current method (note the log y-axis).\r\n\r\n![timing](https://cloud.githubusercontent.com/assets/3419930/5566592/9f8ba956-8ee2-11e4-88e9-2504485f06c2.png)\r\n\r\nThe following diagram shows the relative speedup between both versions:\r\n![speedup](https://cloud.githubusercontent.com/assets/3419930/5566360/f4802f94-8ed9-11e4-891c-da999a0426e8.png)\r\n\r\n## TODO \r\n\r\n- [x] Create fit & transform methods to update using new data\r\n- [x] Add test for transform called before fit\r\n- [x] Add test for skip_num_points\r\n- [x] Raise error if method='barnes_hut' and using sparse data\r\n- [x] Raise error if method='barnes_hut' and embedding dim > 3 \r\n- [x] Transform 64bit input floats to 32bit\r\n- [x] Update the narrative documentation in doc/modules/manifold.rst\r\n- [x] Add toy data to test perplexity\r\n- [x] Fix failing tests\r\n- [x] Expose tree consistency checks as unit tests\r\n- [x] Fix memory leaks\r\n- [x] Segfaults on data larger than 50k elements\r\n- [x] PEP8 the code\r\n- [x] Include usage documentation\r\n- [x] Remove extra imports, print statements, pdb statements\r\n- [x] Ensure python 3 works\r\n- [x] Ensure output dimensionality works for 2D or 3D\r\n- [x] Am I using memviews or returning full arrays appropriately?\r\n- [x] Incorporate into SKLearn\r\n- [x] Remove GIL as much as possible in Cython code\r\n- [x] Add answer tests\r\n- [x] Ensure old t-SNE tests works\r\n- [x] Changed perplexity calculation to nearest neighbors\r\n- [x] Changed positive gradient calc to nearest neighbors\r\n\r\n## Learn\r\n\r\n- You can read more about the technique in general here:\r\n\r\nhttp://lvdmaaten.github.io/tsne/\r\n\r\n- The Barnes-Hut approximation is here:\r\n\r\nhttp://lvdmaaten.github.io/publications/papers/JMLR_2014.pdf\r\n"},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/70672355","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4025#issuecomment-70672355","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4025","id":70672355,"user":{"login":"ogrisel","id":89061,"avatar_url":"https://avatars.githubusercontent.com/u/89061?v=3","gravatar_id":"","url":"https://api.github.com/users/ogrisel","html_url":"https://github.com/ogrisel","followers_url":"https://api.github.com/users/ogrisel/followers","following_url":"https://api.github.com/users/ogrisel/following{/other_user}","gists_url":"https://api.github.com/users/ogrisel/gists{/gist_id}","starred_url":"https://api.github.com/users/ogrisel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ogrisel/subscriptions","organizations_url":"https://api.github.com/users/ogrisel/orgs","repos_url":"https://api.github.com/users/ogrisel/repos","events_url":"https://api.github.com/users/ogrisel/events{/privacy}","received_events_url":"https://api.github.com/users/ogrisel/received_events","type":"User","site_admin":false},"created_at":"2015-01-20T15:33:49Z","updated_at":"2015-01-20T15:33:49Z","body":"The example `plot_tsne.py` could be renamed `plot_tsne_faces.py` to be more explicit. I think it would also be interesting to take one of the tsne on faces plot for inclusion as figure in the narrative documentation in addition to the digits plot."}}