{"action":"created","comment":{"url":"https://api.github.com/repos/allenai/ml/pulls/comments/30086837","id":30086837,"diff_hunk":"@@ -0,0 +1,96 @@\n+package com.allenai.ml.optimize;\n+\n+import com.allenai.ml.linalg.Vector;\n+import com.gs.collections.api.tuple.Pair;\n+import com.gs.collections.impl.tuple.Tuples;\n+\n+import java.util.ArrayList;\n+import java.util.List;\n+\n+/**\n+ * Interface for how to approximate `H^{-1} dir`, where `H^{-1}` is an approximation for the inverse hessian and\n+ * dir is the current search direction. If we use `H^{-1}` as the identity matrix, you get standard gradient descent.\n+ * If you remember some history, you get LBFGS.\n+ */\n+@FunctionalInterface\n+public interface QuasiNewton {\n+\n+    /**\n+     * @return Approximation of inverse hessian matrix times `dir`\n+     */\n+    Vector implictMultiply(Vector dir);\n+\n+    /**\n+     * Update the approximation\n+     * @param xDelta The delta from the last guess\n+     * @param gradDelta The delta from the function gradient at last guess\n+     */\n+    default void update(Vector xDelta, Vector gradDelta) {\n+        // intentional no-op\n+    }\n+\n+    /**\n+     * Approximate inverse hessian with the identity\n+     */\n+    static QuasiNewton gradientDescent() {\n+        return dir -> dir;\n+    }\n+\n+    /**\n+     * LBFGS inverse hessian approximation\n+     */\n+    static QuasiNewton lbfgs(final int maxHistorySize) {\n+        return new QuasiNewton() {\n+            // Store (xDelta, gradDelta) pairs\n+            private final List<Pair<Vector, Vector>> history = new ArrayList<>();\n+\n+            private double initialScale() {\n+                if (history.isEmpty()) {\n+                    return 1.0;\n+                }\n+                Vector lastInputDiff = history.get(0).getOne();\n+                Vector lastGradDiff = history.get(0).getTwo();\n+                double numer = lastGradDiff.dotProduct(lastInputDiff);\n+                double denom = lastGradDiff.l2NormSquared();\n+                if (denom == 0.0) {\n+                    throw new RuntimeException(\"Can't have zero curvature\");","path":"src/main/java/com/allenai/ml/optimize/QuasiNewton.java","position":56,"original_position":56,"commit_id":"217c7dc6c44aa2bd2520eb23e72d7d995c0b3e5b","original_commit_id":"217c7dc6c44aa2bd2520eb23e72d7d995c0b3e5b","user":{"login":"jakemannix","id":69129,"avatar_url":"https://avatars.githubusercontent.com/u/69129?v=3","gravatar_id":"","url":"https://api.github.com/users/jakemannix","html_url":"https://github.com/jakemannix","followers_url":"https://api.github.com/users/jakemannix/followers","following_url":"https://api.github.com/users/jakemannix/following{/other_user}","gists_url":"https://api.github.com/users/jakemannix/gists{/gist_id}","starred_url":"https://api.github.com/users/jakemannix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jakemannix/subscriptions","organizations_url":"https://api.github.com/users/jakemannix/orgs","repos_url":"https://api.github.com/users/jakemannix/repos","events_url":"https://api.github.com/users/jakemannix/events{/privacy}","received_events_url":"https://api.github.com/users/jakemannix/received_events","type":"User","site_admin":false},"body":"Yeah, I'm just imagining that if this only happens when someone uses the code wrong, then it'll be hard if someone is unfamiliar with the code to know what to do if they run it, and then suddenly their code dies with \"Can't have zero curvature\".  They're like - \"What?  Yeah, we probably shouldn't, but why do we?\"","created_at":"2015-05-11T21:56:55Z","updated_at":"2015-05-11T21:56:55Z","html_url":"https://github.com/allenai/ml/pull/3#discussion_r30086837","pull_request_url":"https://api.github.com/repos/allenai/ml/pulls/3","_links":{"self":{"href":"https://api.github.com/repos/allenai/ml/pulls/comments/30086837"},"html":{"href":"https://github.com/allenai/ml/pull/3#discussion_r30086837"},"pull_request":{"href":"https://api.github.com/repos/allenai/ml/pulls/3"}}},"pull_request":{"url":"https://api.github.com/repos/allenai/ml/pulls/3","id":34978235,"html_url":"https://github.com/allenai/ml/pull/3","diff_url":"https://github.com/allenai/ml/pull/3.diff","patch_url":"https://github.com/allenai/ml/pull/3.patch","issue_url":"https://api.github.com/repos/allenai/ml/issues/3","number":3,"state":"open","locked":false,"title":"Numerical optimization and Batch dataset objective","user":{"login":"aria42","id":31170,"avatar_url":"https://avatars.githubusercontent.com/u/31170?v=3","gravatar_id":"","url":"https://api.github.com/users/aria42","html_url":"https://github.com/aria42","followers_url":"https://api.github.com/users/aria42/followers","following_url":"https://api.github.com/users/aria42/following{/other_user}","gists_url":"https://api.github.com/users/aria42/gists{/gist_id}","starred_url":"https://api.github.com/users/aria42/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aria42/subscriptions","organizations_url":"https://api.github.com/users/aria42/orgs","repos_url":"https://api.github.com/users/aria42/repos","events_url":"https://api.github.com/users/aria42/events{/privacy}","received_events_url":"https://api.github.com/users/aria42/received_events","type":"User","site_admin":false},"body":"There are two key things in this PR\r\n\r\n* Standard numerical optimization interfaces and a Newton's method implementation. I could've used another implementation, but from experience with non-convex applications, I know I'm going to want control over how the history is handled. \r\n* A batch objective function abstraction I've used in the past. The best entry-point is the test `BatchObjectiveFnTest` which shows how you optimize simple linear regression. The interface here is pretty simple and you get per-machine parallelism. You can have a `SparkBatchObjectiveFn` which still utilizes the same `ExampleObjectiveFn` interface, but until that's needed not bothering.\r\n\r\nAfter this PR, I'll submit one which trains a CRF model using these modules; the only work is CRF-specific objective value and gradient (the logZ from forward-backwards as well as the node/edge marginals). ","created_at":"2015-05-08T03:35:54Z","updated_at":"2015-05-11T21:56:55Z","closed_at":null,"merged_at":null,"merge_commit_sha":"18c1e8e1abdb85f3b9f4a2aa7dc951fe77e4c21a","assignee":{"login":"jakemannix","id":69129,"avatar_url":"https://avatars.githubusercontent.com/u/69129?v=3","gravatar_id":"","url":"https://api.github.com/users/jakemannix","html_url":"https://github.com/jakemannix","followers_url":"https://api.github.com/users/jakemannix/followers","following_url":"https://api.github.com/users/jakemannix/following{/other_user}","gists_url":"https://api.github.com/users/jakemannix/gists{/gist_id}","starred_url":"https://api.github.com/users/jakemannix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jakemannix/subscriptions","organizations_url":"https://api.github.com/users/jakemannix/orgs","repos_url":"https://api.github.com/users/jakemannix/repos","events_url":"https://api.github.com/users/jakemannix/events{/privacy}","received_events_url":"https://api.github.com/users/jakemannix/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/allenai/ml/pulls/3/commits","review_comments_url":"https://api.github.com/repos/allenai/ml/pulls/3/comments","review_comment_url":"https://api.github.com/repos/allenai/ml/pulls/comments{/number}","comments_url":"https://api.github.com/repos/allenai/ml/issues/3/comments","statuses_url":"https://api.github.com/repos/allenai/ml/statuses/217c7dc6c44aa2bd2520eb23e72d7d995c0b3e5b","head":{"label":"allenai:origin/ariah/numerical-optimization","ref":"origin/ariah/numerical-optimization","sha":"217c7dc6c44aa2bd2520eb23e72d7d995c0b3e5b","user":{"login":"allenai","id":5667695,"avatar_url":"https://avatars.githubusercontent.com/u/5667695?v=3","gravatar_id":"","url":"https://api.github.com/users/allenai","html_url":"https://github.com/allenai","followers_url":"https://api.github.com/users/allenai/followers","following_url":"https://api.github.com/users/allenai/following{/other_user}","gists_url":"https://api.github.com/users/allenai/gists{/gist_id}","starred_url":"https://api.github.com/users/allenai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/allenai/subscriptions","organizations_url":"https://api.github.com/users/allenai/orgs","repos_url":"https://api.github.com/users/allenai/repos","events_url":"https://api.github.com/users/allenai/events{/privacy}","received_events_url":"https://api.github.com/users/allenai/received_events","type":"Organization","site_admin":false},"repo":{"id":35112898,"name":"ml","full_name":"allenai/ml","owner":{"login":"allenai","id":5667695,"avatar_url":"https://avatars.githubusercontent.com/u/5667695?v=3","gravatar_id":"","url":"https://api.github.com/users/allenai","html_url":"https://github.com/allenai","followers_url":"https://api.github.com/users/allenai/followers","following_url":"https://api.github.com/users/allenai/following{/other_user}","gists_url":"https://api.github.com/users/allenai/gists{/gist_id}","starred_url":"https://api.github.com/users/allenai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/allenai/subscriptions","organizations_url":"https://api.github.com/users/allenai/orgs","repos_url":"https://api.github.com/users/allenai/repos","events_url":"https://api.github.com/users/allenai/events{/privacy}","received_events_url":"https://api.github.com/users/allenai/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/allenai/ml","description":"Re-usable low-level ML components","fork":false,"url":"https://api.github.com/repos/allenai/ml","forks_url":"https://api.github.com/repos/allenai/ml/forks","keys_url":"https://api.github.com/repos/allenai/ml/keys{/key_id}","collaborators_url":"https://api.github.com/repos/allenai/ml/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/allenai/ml/teams","hooks_url":"https://api.github.com/repos/allenai/ml/hooks","issue_events_url":"https://api.github.com/repos/allenai/ml/issues/events{/number}","events_url":"https://api.github.com/repos/allenai/ml/events","assignees_url":"https://api.github.com/repos/allenai/ml/assignees{/user}","branches_url":"https://api.github.com/repos/allenai/ml/branches{/branch}","tags_url":"https://api.github.com/repos/allenai/ml/tags","blobs_url":"https://api.github.com/repos/allenai/ml/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/allenai/ml/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/allenai/ml/git/refs{/sha}","trees_url":"https://api.github.com/repos/allenai/ml/git/trees{/sha}","statuses_url":"https://api.github.com/repos/allenai/ml/statuses/{sha}","languages_url":"https://api.github.com/repos/allenai/ml/languages","stargazers_url":"https://api.github.com/repos/allenai/ml/stargazers","contributors_url":"https://api.github.com/repos/allenai/ml/contributors","subscribers_url":"https://api.github.com/repos/allenai/ml/subscribers","subscription_url":"https://api.github.com/repos/allenai/ml/subscription","commits_url":"https://api.github.com/repos/allenai/ml/commits{/sha}","git_commits_url":"https://api.github.com/repos/allenai/ml/git/commits{/sha}","comments_url":"https://api.github.com/repos/allenai/ml/comments{/number}","issue_comment_url":"https://api.github.com/repos/allenai/ml/issues/comments{/number}","contents_url":"https://api.github.com/repos/allenai/ml/contents/{+path}","compare_url":"https://api.github.com/repos/allenai/ml/compare/{base}...{head}","merges_url":"https://api.github.com/repos/allenai/ml/merges","archive_url":"https://api.github.com/repos/allenai/ml/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/allenai/ml/downloads","issues_url":"https://api.github.com/repos/allenai/ml/issues{/number}","pulls_url":"https://api.github.com/repos/allenai/ml/pulls{/number}","milestones_url":"https://api.github.com/repos/allenai/ml/milestones{/number}","notifications_url":"https://api.github.com/repos/allenai/ml/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/allenai/ml/labels{/name}","releases_url":"https://api.github.com/repos/allenai/ml/releases{/id}","created_at":"2015-05-05T17:05:28Z","updated_at":"2015-05-07T20:48:24Z","pushed_at":"2015-05-08T03:44:52Z","git_url":"git://github.com/allenai/ml.git","ssh_url":"git@github.com:allenai/ml.git","clone_url":"https://github.com/allenai/ml.git","svn_url":"https://github.com/allenai/ml","homepage":null,"size":0,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":2,"forks":0,"open_issues":2,"watchers":0,"default_branch":"master"}},"base":{"label":"allenai:master","ref":"master","sha":"b305612c0345df1e3133fcaff58ecee27b3e4730","user":{"login":"allenai","id":5667695,"avatar_url":"https://avatars.githubusercontent.com/u/5667695?v=3","gravatar_id":"","url":"https://api.github.com/users/allenai","html_url":"https://github.com/allenai","followers_url":"https://api.github.com/users/allenai/followers","following_url":"https://api.github.com/users/allenai/following{/other_user}","gists_url":"https://api.github.com/users/allenai/gists{/gist_id}","starred_url":"https://api.github.com/users/allenai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/allenai/subscriptions","organizations_url":"https://api.github.com/users/allenai/orgs","repos_url":"https://api.github.com/users/allenai/repos","events_url":"https://api.github.com/users/allenai/events{/privacy}","received_events_url":"https://api.github.com/users/allenai/received_events","type":"Organization","site_admin":false},"repo":{"id":35112898,"name":"ml","full_name":"allenai/ml","owner":{"login":"allenai","id":5667695,"avatar_url":"https://avatars.githubusercontent.com/u/5667695?v=3","gravatar_id":"","url":"https://api.github.com/users/allenai","html_url":"https://github.com/allenai","followers_url":"https://api.github.com/users/allenai/followers","following_url":"https://api.github.com/users/allenai/following{/other_user}","gists_url":"https://api.github.com/users/allenai/gists{/gist_id}","starred_url":"https://api.github.com/users/allenai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/allenai/subscriptions","organizations_url":"https://api.github.com/users/allenai/orgs","repos_url":"https://api.github.com/users/allenai/repos","events_url":"https://api.github.com/users/allenai/events{/privacy}","received_events_url":"https://api.github.com/users/allenai/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/allenai/ml","description":"Re-usable low-level ML components","fork":false,"url":"https://api.github.com/repos/allenai/ml","forks_url":"https://api.github.com/repos/allenai/ml/forks","keys_url":"https://api.github.com/repos/allenai/ml/keys{/key_id}","collaborators_url":"https://api.github.com/repos/allenai/ml/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/allenai/ml/teams","hooks_url":"https://api.github.com/repos/allenai/ml/hooks","issue_events_url":"https://api.github.com/repos/allenai/ml/issues/events{/number}","events_url":"https://api.github.com/repos/allenai/ml/events","assignees_url":"https://api.github.com/repos/allenai/ml/assignees{/user}","branches_url":"https://api.github.com/repos/allenai/ml/branches{/branch}","tags_url":"https://api.github.com/repos/allenai/ml/tags","blobs_url":"https://api.github.com/repos/allenai/ml/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/allenai/ml/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/allenai/ml/git/refs{/sha}","trees_url":"https://api.github.com/repos/allenai/ml/git/trees{/sha}","statuses_url":"https://api.github.com/repos/allenai/ml/statuses/{sha}","languages_url":"https://api.github.com/repos/allenai/ml/languages","stargazers_url":"https://api.github.com/repos/allenai/ml/stargazers","contributors_url":"https://api.github.com/repos/allenai/ml/contributors","subscribers_url":"https://api.github.com/repos/allenai/ml/subscribers","subscription_url":"https://api.github.com/repos/allenai/ml/subscription","commits_url":"https://api.github.com/repos/allenai/ml/commits{/sha}","git_commits_url":"https://api.github.com/repos/allenai/ml/git/commits{/sha}","comments_url":"https://api.github.com/repos/allenai/ml/comments{/number}","issue_comment_url":"https://api.github.com/repos/allenai/ml/issues/comments{/number}","contents_url":"https://api.github.com/repos/allenai/ml/contents/{+path}","compare_url":"https://api.github.com/repos/allenai/ml/compare/{base}...{head}","merges_url":"https://api.github.com/repos/allenai/ml/merges","archive_url":"https://api.github.com/repos/allenai/ml/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/allenai/ml/downloads","issues_url":"https://api.github.com/repos/allenai/ml/issues{/number}","pulls_url":"https://api.github.com/repos/allenai/ml/pulls{/number}","milestones_url":"https://api.github.com/repos/allenai/ml/milestones{/number}","notifications_url":"https://api.github.com/repos/allenai/ml/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/allenai/ml/labels{/name}","releases_url":"https://api.github.com/repos/allenai/ml/releases{/id}","created_at":"2015-05-05T17:05:28Z","updated_at":"2015-05-07T20:48:24Z","pushed_at":"2015-05-08T03:44:52Z","git_url":"git://github.com/allenai/ml.git","ssh_url":"git@github.com:allenai/ml.git","clone_url":"https://github.com/allenai/ml.git","svn_url":"https://github.com/allenai/ml","homepage":null,"size":0,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":2,"forks":0,"open_issues":2,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/allenai/ml/pulls/3"},"html":{"href":"https://github.com/allenai/ml/pull/3"},"issue":{"href":"https://api.github.com/repos/allenai/ml/issues/3"},"comments":{"href":"https://api.github.com/repos/allenai/ml/issues/3/comments"},"review_comments":{"href":"https://api.github.com/repos/allenai/ml/pulls/3/comments"},"review_comment":{"href":"https://api.github.com/repos/allenai/ml/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/allenai/ml/pulls/3/commits"},"statuses":{"href":"https://api.github.com/repos/allenai/ml/statuses/217c7dc6c44aa2bd2520eb23e72d7d995c0b3e5b"}}}}