{"action":"created","comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/31751428","id":31751428,"diff_hunk":"@@ -0,0 +1,280 @@\n+from ..base import BaseEstimator, TransformerMixin\n+from ..utils.validation import check_is_fitted\n+\n+import numpy as np\n+import scipy as sp\n+import scipy.misc\n+import scipy.optimize\n+import time\n+\n+import sys\n+\n+\n+def nca_vectorized_oracle(X, y, n_components, loss, threshold=0.0):\n+    dx = X[:, np.newaxis, :] - X[np.newaxis, :, :]  # n_samples x n_samples x n_features\n+    outer = dx[:, :, np.newaxis, :] * dx[:, :, :, np.newaxis]  # n_samples x n_samples x n_features x n_features\n+\n+    n_samples, n_features = X.shape\n+\n+    def oracle(L):\n+        L = L.reshape((n_components, n_features))\n+\n+        Lx = np.dot(X, L.T)  # n_samples x n_components\n+        assert Lx.shape == (n_samples, n_components)\n+\n+        A = Lx[np.newaxis, :, :] - Lx[:, np.newaxis, :]  # n_samples x n_samples x n_components\n+        assert A.shape == (n_samples, n_samples, n_components)\n+\n+        logp = -(A * A).sum(axis=2)  # n_samples x n_samples\n+        np.fill_diagonal(logp, -np.inf)\n+        logp -= sp.misc.logsumexp(logp, axis=1)[:, np.newaxis]\n+        assert logp.shape == (n_samples, n_samples)\n+\n+        p = np.exp(logp)  # n_samples x n_samples\n+        assert p.shape == (n_samples, n_samples)\n+\n+        class_neighbours = y[:, np.newaxis] == y[np.newaxis, :]\n+\n+        p_i = (p * class_neighbours).sum(axis=1)\n+\n+        proba = np.copy(p)\n+        if loss == 'l1':\n+            proba *= p_i[:, np.newaxis]\n+        mask = proba > threshold\n+        proba *= mask\n+\n+        grad = np.einsum(\"ij,ijkl\", proba, outer)\n+        assert grad.shape == (n_features, n_features)\n+\n+        neighbours_proba = class_neighbours * p\n+        if loss == 'kl':\n+            neighbours_proba /= p_i[:, np.newaxis]\n+\n+        neighbours_mask = neighbours_proba > threshold\n+        neighbours_proba *= neighbours_mask\n+\n+        neighbours_term = np.einsum(\"ij,ijkl\", neighbours_proba, outer)\n+\n+        assert neighbours_term.shape == (n_features, n_features)\n+        grad -= neighbours_term\n+\n+        function_value = 0\n+        if loss == 'l1':\n+            function_value = p_i.sum()\n+        elif loss == 'kl':\n+            function_value = np.log(p_i).sum()\n+\n+        grad = 2 * np.dot(L, grad)\n+\n+        return [-function_value, -grad.flatten()]\n+\n+    return oracle\n+\n+\n+def nca_semivectorized_oracle(X, y, n_components, loss, threshold=0.0):\n+    n_samples, n_features = X.shape\n+\n+    def oracle(L):\n+        L = L.reshape((n_components, n_features))\n+\n+        Lx = np.dot(X, L.T)  # n_samples x n_components\n+        assert Lx.shape == (n_samples, n_components)\n+\n+        grad = np.zeros((n_features, n_features))\n+        function_value = 0\n+\n+        for i in range(n_samples):\n+            A = Lx[i, :] - Lx  # n_samples x n_components\n+            assert A.shape == (n_samples, n_components)\n+\n+            logp = -(A * A).sum(axis=1)  # n_samples\n+            logp[i] = -np.inf\n+            logp -= sp.misc.logsumexp(logp)\n+            assert logp.shape == (n_samples, )\n+\n+            p = np.exp(logp)  # n_samples\n+            assert p.shape == (n_samples, )\n+\n+            class_neighbours = y == y[i]\n+            p_i = (p * class_neighbours).sum()\n+\n+            if loss == 'l1':\n+                samples_proba = p * p_i\n+            elif loss == 'kl':\n+                samples_proba = p\n+            mask = samples_proba > threshold  # n_samples\n+\n+            Xij = X[i] - X[mask, :]  # n_relevant x n_features\n+            Xij_outer = (Xij[:, :, np.newaxis] * Xij[:, np.newaxis, :])\n+            grad += np.einsum(\"i,ijk\", samples_proba[mask], Xij_outer)\n+\n+            if loss == 'l1':\n+                neighbours_proba = p * (y == y[i])\n+            elif loss == 'kl':\n+                neighbours_proba = p / p_i * (y == y[i])\n+            mask = neighbours_proba > threshold  # n_samples\n+\n+            Xij = X[i] - X[mask, :]  # n_relevant x n_features\n+            Xij_outer = (Xij[:, :, np.newaxis] * Xij[:, np.newaxis, :])\n+            grad -= np.einsum(\"i,ijk\", neighbours_proba[mask], Xij_outer)\n+\n+            if loss == 'l1':\n+                function_value += p_i\n+            elif loss == 'kl':\n+                function_value += np.log(p_i)\n+\n+        grad = 2 * np.dot(L, grad)\n+\n+        return [-function_value, -grad.flatten()]\n+\n+    return oracle\n+\n+\n+def optimize_nca(X, y, learning_rate, n_components, loss, n_init, max_iter,\n+                 method, tol, random_state, cache_size, verbose):\n+    n_samples, n_features = X.shape\n+\n+    rng = np.random.RandomState(random_state)\n+    best_value = np.inf\n+    best_L = None\n+\n+\n+    threshold = 1e-3 / np.abs(X).max() ** 2\n+\n+    outer_products_size = (n_samples * n_features) ** 2\n+    memory_permits = outer_products_size < cache_size\n+    if memory_permits:","path":"sklearn/metric_learning/nca.py","position":130,"original_position":146,"commit_id":"187f66389ac391dfdf5e7524655be0dc8161c771","original_commit_id":"ea577c53033f6092ada6374b1b61aa104bff0e2a","user":{"login":"vene","id":241745,"avatar_url":"https://avatars.githubusercontent.com/u/241745?v=3","gravatar_id":"","url":"https://api.github.com/users/vene","html_url":"https://github.com/vene","followers_url":"https://api.github.com/users/vene/followers","following_url":"https://api.github.com/users/vene/following{/other_user}","gists_url":"https://api.github.com/users/vene/gists{/gist_id}","starred_url":"https://api.github.com/users/vene/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vene/subscriptions","organizations_url":"https://api.github.com/users/vene/orgs","repos_url":"https://api.github.com/users/vene/repos","events_url":"https://api.github.com/users/vene/events{/privacy}","received_events_url":"https://api.github.com/users/vene/received_events","type":"User","site_admin":false},"body":"> The problem with the name \"method\" is that it's already used by optimizer (adagrad, scipy, etc). Though we might want to throw all but one away.\r\n\r\nMaybe that one should be called \"solver\" as in Ridge, Logistic etc?\r\n\r\n> There's `cache_size` for SVM\r\n\r\nOh true, I never noticed that before. But that seems to be not by choice, but to match the libsvm API.  From what I know, scikit-learn's \"auto\" strategies just use heuristics based on n_samples/n_features, without trying to introspect memory usage or the like.  It would definitely be possible, it might just be unusual and add extra complication. This is not a priority anyway, so I'd say we stick with the manual way for now.","created_at":"2015-06-04T18:40:55Z","updated_at":"2015-06-04T18:40:55Z","html_url":"https://github.com/scikit-learn/scikit-learn/pull/4789#discussion_r31751428","pull_request_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789","_links":{"self":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments/31751428"},"html":{"href":"https://github.com/scikit-learn/scikit-learn/pull/4789#discussion_r31751428"},"pull_request":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789"}}},"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789","id":36520274,"html_url":"https://github.com/scikit-learn/scikit-learn/pull/4789","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/4789.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/4789.patch","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4789","number":4789,"state":"open","locked":false,"title":"[WIP] Metric Learning :: NCA","user":{"login":"Barmaley-exe","id":434122,"avatar_url":"https://avatars.githubusercontent.com/u/434122?v=3","gravatar_id":"","url":"https://api.github.com/users/Barmaley-exe","html_url":"https://github.com/Barmaley-exe","followers_url":"https://api.github.com/users/Barmaley-exe/followers","following_url":"https://api.github.com/users/Barmaley-exe/following{/other_user}","gists_url":"https://api.github.com/users/Barmaley-exe/gists{/gist_id}","starred_url":"https://api.github.com/users/Barmaley-exe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Barmaley-exe/subscriptions","organizations_url":"https://api.github.com/users/Barmaley-exe/orgs","repos_url":"https://api.github.com/users/Barmaley-exe/repos","events_url":"https://api.github.com/users/Barmaley-exe/events{/privacy}","received_events_url":"https://api.github.com/users/Barmaley-exe/received_events","type":"User","site_admin":false},"body":"GSoC 2015 project, Iteration 1: Neighborhood Component Analysis\r\n\r\nFor details refer to my GSoC blog, especially a post on [NCA](http://barmaley-exe.blogspot.ru/2015/05/nca.html).","created_at":"2015-05-29T16:07:10Z","updated_at":"2015-06-04T18:40:56Z","closed_at":null,"merged_at":null,"merge_commit_sha":"1dff8f17130039301e6afd91a03e0c52fcc2f2c2","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789/commits","review_comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789/comments","review_comment_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments{/number}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4789/comments","statuses_url":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/187f66389ac391dfdf5e7524655be0dc8161c771","head":{"label":"Barmaley-exe:metric-learning","ref":"metric-learning","sha":"187f66389ac391dfdf5e7524655be0dc8161c771","user":{"login":"Barmaley-exe","id":434122,"avatar_url":"https://avatars.githubusercontent.com/u/434122?v=3","gravatar_id":"","url":"https://api.github.com/users/Barmaley-exe","html_url":"https://github.com/Barmaley-exe","followers_url":"https://api.github.com/users/Barmaley-exe/followers","following_url":"https://api.github.com/users/Barmaley-exe/following{/other_user}","gists_url":"https://api.github.com/users/Barmaley-exe/gists{/gist_id}","starred_url":"https://api.github.com/users/Barmaley-exe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Barmaley-exe/subscriptions","organizations_url":"https://api.github.com/users/Barmaley-exe/orgs","repos_url":"https://api.github.com/users/Barmaley-exe/repos","events_url":"https://api.github.com/users/Barmaley-exe/events{/privacy}","received_events_url":"https://api.github.com/users/Barmaley-exe/received_events","type":"User","site_admin":false},"repo":{"id":30595741,"name":"scikit-learn","full_name":"Barmaley-exe/scikit-learn","owner":{"login":"Barmaley-exe","id":434122,"avatar_url":"https://avatars.githubusercontent.com/u/434122?v=3","gravatar_id":"","url":"https://api.github.com/users/Barmaley-exe","html_url":"https://github.com/Barmaley-exe","followers_url":"https://api.github.com/users/Barmaley-exe/followers","following_url":"https://api.github.com/users/Barmaley-exe/following{/other_user}","gists_url":"https://api.github.com/users/Barmaley-exe/gists{/gist_id}","starred_url":"https://api.github.com/users/Barmaley-exe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Barmaley-exe/subscriptions","organizations_url":"https://api.github.com/users/Barmaley-exe/orgs","repos_url":"https://api.github.com/users/Barmaley-exe/repos","events_url":"https://api.github.com/users/Barmaley-exe/events{/privacy}","received_events_url":"https://api.github.com/users/Barmaley-exe/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Barmaley-exe/scikit-learn","description":"scikit-learn: machine learning in Python","fork":true,"url":"https://api.github.com/repos/Barmaley-exe/scikit-learn","forks_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/forks","keys_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/teams","hooks_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/events","assignees_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/tags","blobs_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/subscription","commits_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/issues/comments{/number}","contents_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/merges","archive_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/downloads","issues_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/Barmaley-exe/scikit-learn/releases{/id}","created_at":"2015-02-10T14:27:11Z","updated_at":"2015-03-12T18:58:47Z","pushed_at":"2015-06-04T09:38:21Z","git_url":"git://github.com/Barmaley-exe/scikit-learn.git","ssh_url":"git@github.com:Barmaley-exe/scikit-learn.git","clone_url":"https://github.com/Barmaley-exe/scikit-learn.git","svn_url":"https://github.com/Barmaley-exe/scikit-learn","homepage":"http://scikit-learn.org","size":62627,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"scikit-learn:master","ref":"master","sha":"05ad7459f3bdf47be2a369ef71f4fa5aab5118b2","user":{"login":"scikit-learn","id":365630,"avatar_url":"https://avatars.githubusercontent.com/u/365630?v=3","gravatar_id":"","url":"https://api.github.com/users/scikit-learn","html_url":"https://github.com/scikit-learn","followers_url":"https://api.github.com/users/scikit-learn/followers","following_url":"https://api.github.com/users/scikit-learn/following{/other_user}","gists_url":"https://api.github.com/users/scikit-learn/gists{/gist_id}","starred_url":"https://api.github.com/users/scikit-learn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scikit-learn/subscriptions","organizations_url":"https://api.github.com/users/scikit-learn/orgs","repos_url":"https://api.github.com/users/scikit-learn/repos","events_url":"https://api.github.com/users/scikit-learn/events{/privacy}","received_events_url":"https://api.github.com/users/scikit-learn/received_events","type":"Organization","site_admin":false},"repo":{"id":843222,"name":"scikit-learn","full_name":"scikit-learn/scikit-learn","owner":{"login":"scikit-learn","id":365630,"avatar_url":"https://avatars.githubusercontent.com/u/365630?v=3","gravatar_id":"","url":"https://api.github.com/users/scikit-learn","html_url":"https://github.com/scikit-learn","followers_url":"https://api.github.com/users/scikit-learn/followers","following_url":"https://api.github.com/users/scikit-learn/following{/other_user}","gists_url":"https://api.github.com/users/scikit-learn/gists{/gist_id}","starred_url":"https://api.github.com/users/scikit-learn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/scikit-learn/subscriptions","organizations_url":"https://api.github.com/users/scikit-learn/orgs","repos_url":"https://api.github.com/users/scikit-learn/repos","events_url":"https://api.github.com/users/scikit-learn/events{/privacy}","received_events_url":"https://api.github.com/users/scikit-learn/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/scikit-learn/scikit-learn","description":"scikit-learn: machine learning in Python","fork":false,"url":"https://api.github.com/repos/scikit-learn/scikit-learn","forks_url":"https://api.github.com/repos/scikit-learn/scikit-learn/forks","keys_url":"https://api.github.com/repos/scikit-learn/scikit-learn/keys{/key_id}","collaborators_url":"https://api.github.com/repos/scikit-learn/scikit-learn/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/scikit-learn/scikit-learn/teams","hooks_url":"https://api.github.com/repos/scikit-learn/scikit-learn/hooks","issue_events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/events{/number}","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/events","assignees_url":"https://api.github.com/repos/scikit-learn/scikit-learn/assignees{/user}","branches_url":"https://api.github.com/repos/scikit-learn/scikit-learn/branches{/branch}","tags_url":"https://api.github.com/repos/scikit-learn/scikit-learn/tags","blobs_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/refs{/sha}","trees_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/trees{/sha}","statuses_url":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/{sha}","languages_url":"https://api.github.com/repos/scikit-learn/scikit-learn/languages","stargazers_url":"https://api.github.com/repos/scikit-learn/scikit-learn/stargazers","contributors_url":"https://api.github.com/repos/scikit-learn/scikit-learn/contributors","subscribers_url":"https://api.github.com/repos/scikit-learn/scikit-learn/subscribers","subscription_url":"https://api.github.com/repos/scikit-learn/scikit-learn/subscription","commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/commits{/sha}","git_commits_url":"https://api.github.com/repos/scikit-learn/scikit-learn/git/commits{/sha}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/comments{/number}","issue_comment_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments{/number}","contents_url":"https://api.github.com/repos/scikit-learn/scikit-learn/contents/{+path}","compare_url":"https://api.github.com/repos/scikit-learn/scikit-learn/compare/{base}...{head}","merges_url":"https://api.github.com/repos/scikit-learn/scikit-learn/merges","archive_url":"https://api.github.com/repos/scikit-learn/scikit-learn/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/scikit-learn/scikit-learn/downloads","issues_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues{/number}","pulls_url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls{/number}","milestones_url":"https://api.github.com/repos/scikit-learn/scikit-learn/milestones{/number}","notifications_url":"https://api.github.com/repos/scikit-learn/scikit-learn/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/labels{/name}","releases_url":"https://api.github.com/repos/scikit-learn/scikit-learn/releases{/id}","created_at":"2010-08-17T09:43:38Z","updated_at":"2015-06-04T18:36:24Z","pushed_at":"2015-06-04T17:50:18Z","git_url":"git://github.com/scikit-learn/scikit-learn.git","ssh_url":"git@github.com:scikit-learn/scikit-learn.git","clone_url":"https://github.com/scikit-learn/scikit-learn.git","svn_url":"https://github.com/scikit-learn/scikit-learn","homepage":"http://scikit-learn.org","size":130646,"stargazers_count":6271,"watchers_count":6271,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":3763,"mirror_url":null,"open_issues_count":678,"forks":3763,"open_issues":678,"watchers":6271,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789"},"html":{"href":"https://github.com/scikit-learn/scikit-learn/pull/4789"},"issue":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4789"},"comments":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/4789/comments"},"review_comments":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789/comments"},"review_comment":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/4789/commits"},"statuses":{"href":"https://api.github.com/repos/scikit-learn/scikit-learn/statuses/187f66389ac391dfdf5e7524655be0dc8161c771"}}}}