{"action":"created","comment":{"url":"https://api.github.com/repos/oppia/oppia/pulls/comments/41113201","id":41113201,"diff_hunk":"@@ -0,0 +1,322 @@\n+# coding: utf-8\n+#\n+# Copyright 2015 The Oppia Authors. All Rights Reserved.\n+#\n+# Licensed under the Apache License, Version 2.0 (the \"License\");\n+# you may not use this file except in compliance with the License.\n+# You may obtain a copy of the License at\n+#\n+#      http://www.apache.org/licenses/LICENSE-2.0\n+#\n+# Unless required by applicable law or agreed to in writing, software\n+# distributed under the License is distributed on an \"AS-IS\" BASIS,\n+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+# See the License for the specific language governing permissions and\n+# limitations under the License.\n+\n+import copy\n+import operator\n+\n+import numpy\n+\n+\n+class StringClassifier(object):\n+    \"\"\"Handles math-y internals for classifying strings.\n+    https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation\"\"\"\n+\n+    # Learning rates\n+    _DEFAULT_ALPHA = 0.1\n+    _DEFAULT_BETA = 0.001\n+\n+    def __init__(self):\n+        \"\"\"\n+        Hieroglyph decoder:\n+        b - boolean\n+        c - count\n+        i - id\n+        l - label\n+        w - word\n+        d - doc\n+\n+        Internal (private) model representation:\n+        _w_dc - word (id) given doc and count\n+            (list of word ids which represent a doc)\n+        _b_dl - boolean given doc and label\n+            (boolean of whether a doc has a label)\n+        _l_dc - label given doc and count\n+            (assigned label of each word in a doc)\n+        _c_dl - count given doc and label\n+            (count of each label per doc)\n+        _c_lw - count given label and word\n+            (count of labels per word)\n+        _c_l - count given label (count of each label)\n+        \"\"\"\n+        # Ensure that results are deterministic\n+        # There is nothing special about the value 4\n+        numpy.random.seed(seed=4)\n+\n+        self._alpha = self._DEFAULT_ALPHA\n+        self._beta = self._DEFAULT_BETA\n+\n+    def _get_word_id(self, word):\n+        \"\"\"Returns a word's id if it exists, otherwise assigns\n+        a new id to the word and returns it.\"\"\"\n+        try:\n+            return self._word_to_id[word]\n+        except KeyError as ke:\n+            self._word_to_id[word] = self._word_count\n+            self._word_count += 1\n+        return self._word_to_id[word]\n+\n+    def _get_label_id(self, label):\n+        \"\"\"Returns a word's id if it exists, otherwise assigns\n+        a new id to the label and returns it.\"\"\"\n+        try:\n+            return self._label_to_id[label]\n+        except KeyError as ke:\n+            self._label_to_id[label] = self._label_count\n+            self._label_count += 1\n+        return self._label_to_id[label]\n+\n+    def _get_record(self, d):\n+        \"\"\"Given a doc id, return the doc and labels.\"\"\"\n+        return self._w_dc[d], self._b_dl[d]\n+\n+    def _get_label_vector(self, labels):\n+        \"\"\"Returns a vector specifying which labels\n+        are specified in the training set.\"\"\"\n+        if len(labels) == 0:\n+            return numpy.ones(self._label_count)\n+        label_vector = numpy.zeros(self._label_count)\n+        for label in labels:\n+            label_vector[self._get_label_id(label)] = 1\n+        # Always set default label\n+        label_vector[self._label_to_id['_default']] = 1\n+        return label_vector\n+\n+    def _update_counting_matrices(self, d, w, l, val):\n+        \"\"\"Update counting matrices given doc/word/label indices.\"\"\"\n+        self._c_dl[d, l] += val\n+        self._c_lw[l, w] += val\n+        self._c_l[l] += val\n+\n+    def _get_doc_ids(self, doc_ids):\n+        if doc_ids is None:\n+            doc_ids = xrange(self._doc_count)\n+        return doc_ids\n+\n+    def _init_docs(self, doc_ids=None):\n+        \"\"\"Initialize data for given docs (defaults to all).\"\"\"\n+        doc_ids = self._get_doc_ids(doc_ids)\n+\n+        for d in doc_ids:\n+            doc, labels = self._get_record(d)\n+            l_c = [\n+                numpy.random.multinomial(1, labels / labels.sum()).argmax()\n+                for i in xrange(len(doc))\n+            ]\n+            self._l_dc.append(l_c)\n+            for w, l in zip(doc, l_c):\n+                self._update_counting_matrices(d, w, l, 1)\n+\n+    def _infer_docs(self, doc_ids):\n+        \"\"\"Runs iterative inference on given docs (default all).\"\"\"\n+        doc_ids = self._get_doc_ids(doc_ids)\n+\n+        statez = {\n+            'updates': 0,\n+            'computes': 0\n+        }\n+\n+        for d in doc_ids:\n+            doc, labels = self._get_record(d)\n+            for c in xrange(len(doc)):\n+                w = doc[c]\n+                l = self._l_dc[d][c]\n+\n+                self._update_counting_matrices(d, w, l, -1)\n+\n+                # Gibbs update of labels\n+                coeff_a = 1 / (\n+                    self._c_dl[d].sum() + self._label_count * self._alpha)\n+                coeff_b = 1 / (\n+                    self._c_lw.sum(axis=1) + self._word_count * self._beta)\n+                prob_l = (\n+                    labels *\n+                    coeff_a * (self._c_dl[d] + self._alpha) *\n+                    coeff_b * (self._c_lw[:, w] + self._beta))\n+                new_l = numpy.random.multinomial(\n+                    1, prob_l / prob_l.sum()\n+                    ).argmax()\n+\n+                statez['computes'] += 1\n+                if l != new_l:\n+                    statez['updates'] += 1\n+\n+                self._l_dc[d][c] = new_l\n+                self._update_counting_matrices(d, w, new_l, 1)\n+\n+        return statez\n+\n+    def _get_probabilities(self, d):\n+        \"\"\"Returns the probability of a document having a label.\"\"\"\n+        probs_i = self._c_dl[d] + (self._b_dl[d] * self._alpha)\n+        probs_i = probs_i / probs_i.sum(axis=0)[numpy.newaxis]\n+        return probs_i\n+\n+    def _get_probabilities_with_label(self, d):\n+        \"\"\"Includes human readable labels with document probabilities.\"\"\"\n+        probs_i = self._get_probabilities(d)\n+        probs_l = {}\n+        for label, l in self._label_to_id.iteritems():\n+            probs_l[label] = probs_i[l]\n+        return probs_l\n+\n+    def _predict(self, d, threshold=0.5):\n+        \"\"\"Calculates prediction data for a doc\"\"\"\n+        probs_l = self._get_probabilities_with_label(d)\n+        default_prob = probs_l['_default']\n+        for l in sorted(probs_l, key=probs_l.get, reverse=True):\n+            prob_l = probs_l[l]\n+            if l != '_default' and prob_l / (1 - default_prob) > threshold:\n+                return l, prob_l / (1 - default_prob), probs_l\n+        return '_default', default_prob / (1 - default_prob), probs_l\n+\n+    def _validate_label(self, label):\n+        \"\"\"Checks that labels don't begin with underscore.\"\"\"\n+        if label[0] == '_':\n+            raise Exception('Label %s cannot begin with underscore.' % label)\n+\n+    def _parse_examples(self, examples):\n+        \"\"\"Splits examples into docs (split on spaces) and labels.\"\"\"","path":"core/domain/classifier_services.py","position":191,"original_position":191,"commit_id":"7709a5b05e665b42e60d0d4d072e7d02f1aa2fe4","original_commit_id":"7709a5b05e665b42e60d0d4d072e7d02f1aa2fe4","user":{"login":"stephenchiang","id":3666806,"avatar_url":"https://avatars.githubusercontent.com/u/3666806?v=3","gravatar_id":"","url":"https://api.github.com/users/stephenchiang","html_url":"https://github.com/stephenchiang","followers_url":"https://api.github.com/users/stephenchiang/followers","following_url":"https://api.github.com/users/stephenchiang/following{/other_user}","gists_url":"https://api.github.com/users/stephenchiang/gists{/gist_id}","starred_url":"https://api.github.com/users/stephenchiang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stephenchiang/subscriptions","organizations_url":"https://api.github.com/users/stephenchiang/orgs","repos_url":"https://api.github.com/users/stephenchiang/repos","events_url":"https://api.github.com/users/stephenchiang/events{/privacy}","received_events_url":"https://api.github.com/users/stephenchiang/received_events","type":"User","site_admin":false},"body":"Good point.","created_at":"2015-10-05T06:19:44Z","updated_at":"2015-10-05T06:19:44Z","html_url":"https://github.com/oppia/oppia/pull/1008#discussion_r41113201","pull_request_url":"https://api.github.com/repos/oppia/oppia/pulls/1008","_links":{"self":{"href":"https://api.github.com/repos/oppia/oppia/pulls/comments/41113201"},"html":{"href":"https://github.com/oppia/oppia/pull/1008#discussion_r41113201"},"pull_request":{"href":"https://api.github.com/repos/oppia/oppia/pulls/1008"}}},"pull_request":{"url":"https://api.github.com/repos/oppia/oppia/pulls/1008","id":46720584,"html_url":"https://github.com/oppia/oppia/pull/1008","diff_url":"https://github.com/oppia/oppia/pull/1008.diff","patch_url":"https://github.com/oppia/oppia/pull/1008.patch","issue_url":"https://api.github.com/repos/oppia/oppia/issues/1008","number":1008,"state":"open","locked":false,"title":"StringClassifier","user":{"login":"stephenchiang","id":3666806,"avatar_url":"https://avatars.githubusercontent.com/u/3666806?v=3","gravatar_id":"","url":"https://api.github.com/users/stephenchiang","html_url":"https://github.com/stephenchiang","followers_url":"https://api.github.com/users/stephenchiang/followers","following_url":"https://api.github.com/users/stephenchiang/following{/other_user}","gists_url":"https://api.github.com/users/stephenchiang/gists{/gist_id}","starred_url":"https://api.github.com/users/stephenchiang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stephenchiang/subscriptions","organizations_url":"https://api.github.com/users/stephenchiang/orgs","repos_url":"https://api.github.com/users/stephenchiang/repos","events_url":"https://api.github.com/users/stephenchiang/events{/privacy}","received_events_url":"https://api.github.com/users/stephenchiang/received_events","type":"User","site_admin":false},"body":"Supervised string classifier to be used as a black box to predict student free form responses.\r\n\r\n/cc @seanlip @BenHenning \r\n","created_at":"2015-10-04T07:00:13Z","updated_at":"2015-10-05T06:19:44Z","closed_at":null,"merged_at":null,"merge_commit_sha":"9c1a507e47231f59a4c724c12cb49656240dbe59","assignee":{"login":"seanlip","id":10575562,"avatar_url":"https://avatars.githubusercontent.com/u/10575562?v=3","gravatar_id":"","url":"https://api.github.com/users/seanlip","html_url":"https://github.com/seanlip","followers_url":"https://api.github.com/users/seanlip/followers","following_url":"https://api.github.com/users/seanlip/following{/other_user}","gists_url":"https://api.github.com/users/seanlip/gists{/gist_id}","starred_url":"https://api.github.com/users/seanlip/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/seanlip/subscriptions","organizations_url":"https://api.github.com/users/seanlip/orgs","repos_url":"https://api.github.com/users/seanlip/repos","events_url":"https://api.github.com/users/seanlip/events{/privacy}","received_events_url":"https://api.github.com/users/seanlip/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/oppia/oppia/pulls/1008/commits","review_comments_url":"https://api.github.com/repos/oppia/oppia/pulls/1008/comments","review_comment_url":"https://api.github.com/repos/oppia/oppia/pulls/comments{/number}","comments_url":"https://api.github.com/repos/oppia/oppia/issues/1008/comments","statuses_url":"https://api.github.com/repos/oppia/oppia/statuses/7709a5b05e665b42e60d0d4d072e7d02f1aa2fe4","head":{"label":"stephenchiang:classifier-services","ref":"classifier-services","sha":"7709a5b05e665b42e60d0d4d072e7d02f1aa2fe4","user":{"login":"stephenchiang","id":3666806,"avatar_url":"https://avatars.githubusercontent.com/u/3666806?v=3","gravatar_id":"","url":"https://api.github.com/users/stephenchiang","html_url":"https://github.com/stephenchiang","followers_url":"https://api.github.com/users/stephenchiang/followers","following_url":"https://api.github.com/users/stephenchiang/following{/other_user}","gists_url":"https://api.github.com/users/stephenchiang/gists{/gist_id}","starred_url":"https://api.github.com/users/stephenchiang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stephenchiang/subscriptions","organizations_url":"https://api.github.com/users/stephenchiang/orgs","repos_url":"https://api.github.com/users/stephenchiang/repos","events_url":"https://api.github.com/users/stephenchiang/events{/privacy}","received_events_url":"https://api.github.com/users/stephenchiang/received_events","type":"User","site_admin":false},"repo":{"id":43627434,"name":"oppia","full_name":"stephenchiang/oppia","owner":{"login":"stephenchiang","id":3666806,"avatar_url":"https://avatars.githubusercontent.com/u/3666806?v=3","gravatar_id":"","url":"https://api.github.com/users/stephenchiang","html_url":"https://github.com/stephenchiang","followers_url":"https://api.github.com/users/stephenchiang/followers","following_url":"https://api.github.com/users/stephenchiang/following{/other_user}","gists_url":"https://api.github.com/users/stephenchiang/gists{/gist_id}","starred_url":"https://api.github.com/users/stephenchiang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stephenchiang/subscriptions","organizations_url":"https://api.github.com/users/stephenchiang/orgs","repos_url":"https://api.github.com/users/stephenchiang/repos","events_url":"https://api.github.com/users/stephenchiang/events{/privacy}","received_events_url":"https://api.github.com/users/stephenchiang/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/stephenchiang/oppia","description":"Tool for collaboratively building interactive tutors.","fork":true,"url":"https://api.github.com/repos/stephenchiang/oppia","forks_url":"https://api.github.com/repos/stephenchiang/oppia/forks","keys_url":"https://api.github.com/repos/stephenchiang/oppia/keys{/key_id}","collaborators_url":"https://api.github.com/repos/stephenchiang/oppia/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/stephenchiang/oppia/teams","hooks_url":"https://api.github.com/repos/stephenchiang/oppia/hooks","issue_events_url":"https://api.github.com/repos/stephenchiang/oppia/issues/events{/number}","events_url":"https://api.github.com/repos/stephenchiang/oppia/events","assignees_url":"https://api.github.com/repos/stephenchiang/oppia/assignees{/user}","branches_url":"https://api.github.com/repos/stephenchiang/oppia/branches{/branch}","tags_url":"https://api.github.com/repos/stephenchiang/oppia/tags","blobs_url":"https://api.github.com/repos/stephenchiang/oppia/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/stephenchiang/oppia/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/stephenchiang/oppia/git/refs{/sha}","trees_url":"https://api.github.com/repos/stephenchiang/oppia/git/trees{/sha}","statuses_url":"https://api.github.com/repos/stephenchiang/oppia/statuses/{sha}","languages_url":"https://api.github.com/repos/stephenchiang/oppia/languages","stargazers_url":"https://api.github.com/repos/stephenchiang/oppia/stargazers","contributors_url":"https://api.github.com/repos/stephenchiang/oppia/contributors","subscribers_url":"https://api.github.com/repos/stephenchiang/oppia/subscribers","subscription_url":"https://api.github.com/repos/stephenchiang/oppia/subscription","commits_url":"https://api.github.com/repos/stephenchiang/oppia/commits{/sha}","git_commits_url":"https://api.github.com/repos/stephenchiang/oppia/git/commits{/sha}","comments_url":"https://api.github.com/repos/stephenchiang/oppia/comments{/number}","issue_comment_url":"https://api.github.com/repos/stephenchiang/oppia/issues/comments{/number}","contents_url":"https://api.github.com/repos/stephenchiang/oppia/contents/{+path}","compare_url":"https://api.github.com/repos/stephenchiang/oppia/compare/{base}...{head}","merges_url":"https://api.github.com/repos/stephenchiang/oppia/merges","archive_url":"https://api.github.com/repos/stephenchiang/oppia/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/stephenchiang/oppia/downloads","issues_url":"https://api.github.com/repos/stephenchiang/oppia/issues{/number}","pulls_url":"https://api.github.com/repos/stephenchiang/oppia/pulls{/number}","milestones_url":"https://api.github.com/repos/stephenchiang/oppia/milestones{/number}","notifications_url":"https://api.github.com/repos/stephenchiang/oppia/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/stephenchiang/oppia/labels{/name}","releases_url":"https://api.github.com/repos/stephenchiang/oppia/releases{/id}","created_at":"2015-10-04T06:32:57Z","updated_at":"2015-10-04T06:33:01Z","pushed_at":"2015-10-04T21:40:25Z","git_url":"git://github.com/stephenchiang/oppia.git","ssh_url":"git@github.com:stephenchiang/oppia.git","clone_url":"https://github.com/stephenchiang/oppia.git","svn_url":"https://github.com/stephenchiang/oppia","homepage":"https://www.oppia.org","size":37373,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_downloads":false,"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":"develop"}},"base":{"label":"oppia:develop","ref":"develop","sha":"5fa6f6cd812d26613919d68f0b1d7b9aa0f8a48b","user":{"login":"oppia","id":11620230,"avatar_url":"https://avatars.githubusercontent.com/u/11620230?v=3","gravatar_id":"","url":"https://api.github.com/users/oppia","html_url":"https://github.com/oppia","followers_url":"https://api.github.com/users/oppia/followers","following_url":"https://api.github.com/users/oppia/following{/other_user}","gists_url":"https://api.github.com/users/oppia/gists{/gist_id}","starred_url":"https://api.github.com/users/oppia/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oppia/subscriptions","organizations_url":"https://api.github.com/users/oppia/orgs","repos_url":"https://api.github.com/users/oppia/repos","events_url":"https://api.github.com/users/oppia/events{/privacy}","received_events_url":"https://api.github.com/users/oppia/received_events","type":"Organization","site_admin":false},"repo":{"id":40687563,"name":"oppia","full_name":"oppia/oppia","owner":{"login":"oppia","id":11620230,"avatar_url":"https://avatars.githubusercontent.com/u/11620230?v=3","gravatar_id":"","url":"https://api.github.com/users/oppia","html_url":"https://github.com/oppia","followers_url":"https://api.github.com/users/oppia/followers","following_url":"https://api.github.com/users/oppia/following{/other_user}","gists_url":"https://api.github.com/users/oppia/gists{/gist_id}","starred_url":"https://api.github.com/users/oppia/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oppia/subscriptions","organizations_url":"https://api.github.com/users/oppia/orgs","repos_url":"https://api.github.com/users/oppia/repos","events_url":"https://api.github.com/users/oppia/events{/privacy}","received_events_url":"https://api.github.com/users/oppia/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/oppia/oppia","description":"Tool for collaboratively building interactive tutors.","fork":false,"url":"https://api.github.com/repos/oppia/oppia","forks_url":"https://api.github.com/repos/oppia/oppia/forks","keys_url":"https://api.github.com/repos/oppia/oppia/keys{/key_id}","collaborators_url":"https://api.github.com/repos/oppia/oppia/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/oppia/oppia/teams","hooks_url":"https://api.github.com/repos/oppia/oppia/hooks","issue_events_url":"https://api.github.com/repos/oppia/oppia/issues/events{/number}","events_url":"https://api.github.com/repos/oppia/oppia/events","assignees_url":"https://api.github.com/repos/oppia/oppia/assignees{/user}","branches_url":"https://api.github.com/repos/oppia/oppia/branches{/branch}","tags_url":"https://api.github.com/repos/oppia/oppia/tags","blobs_url":"https://api.github.com/repos/oppia/oppia/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/oppia/oppia/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/oppia/oppia/git/refs{/sha}","trees_url":"https://api.github.com/repos/oppia/oppia/git/trees{/sha}","statuses_url":"https://api.github.com/repos/oppia/oppia/statuses/{sha}","languages_url":"https://api.github.com/repos/oppia/oppia/languages","stargazers_url":"https://api.github.com/repos/oppia/oppia/stargazers","contributors_url":"https://api.github.com/repos/oppia/oppia/contributors","subscribers_url":"https://api.github.com/repos/oppia/oppia/subscribers","subscription_url":"https://api.github.com/repos/oppia/oppia/subscription","commits_url":"https://api.github.com/repos/oppia/oppia/commits{/sha}","git_commits_url":"https://api.github.com/repos/oppia/oppia/git/commits{/sha}","comments_url":"https://api.github.com/repos/oppia/oppia/comments{/number}","issue_comment_url":"https://api.github.com/repos/oppia/oppia/issues/comments{/number}","contents_url":"https://api.github.com/repos/oppia/oppia/contents/{+path}","compare_url":"https://api.github.com/repos/oppia/oppia/compare/{base}...{head}","merges_url":"https://api.github.com/repos/oppia/oppia/merges","archive_url":"https://api.github.com/repos/oppia/oppia/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/oppia/oppia/downloads","issues_url":"https://api.github.com/repos/oppia/oppia/issues{/number}","pulls_url":"https://api.github.com/repos/oppia/oppia/pulls{/number}","milestones_url":"https://api.github.com/repos/oppia/oppia/milestones{/number}","notifications_url":"https://api.github.com/repos/oppia/oppia/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/oppia/oppia/labels{/name}","releases_url":"https://api.github.com/repos/oppia/oppia/releases{/id}","created_at":"2015-08-14T00:16:14Z","updated_at":"2015-10-03T22:14:51Z","pushed_at":"2015-10-05T05:30:20Z","git_url":"git://github.com/oppia/oppia.git","ssh_url":"git@github.com:oppia/oppia.git","clone_url":"https://github.com/oppia/oppia.git","svn_url":"https://github.com/oppia/oppia","homepage":"https://www.oppia.org","size":43656,"stargazers_count":42,"watchers_count":42,"language":"Python","has_issues":true,"has_downloads":false,"has_wiki":true,"has_pages":false,"forks_count":51,"mirror_url":null,"open_issues_count":175,"forks":51,"open_issues":175,"watchers":42,"default_branch":"develop"}},"_links":{"self":{"href":"https://api.github.com/repos/oppia/oppia/pulls/1008"},"html":{"href":"https://github.com/oppia/oppia/pull/1008"},"issue":{"href":"https://api.github.com/repos/oppia/oppia/issues/1008"},"comments":{"href":"https://api.github.com/repos/oppia/oppia/issues/1008/comments"},"review_comments":{"href":"https://api.github.com/repos/oppia/oppia/pulls/1008/comments"},"review_comment":{"href":"https://api.github.com/repos/oppia/oppia/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/oppia/oppia/pulls/1008/commits"},"statuses":{"href":"https://api.github.com/repos/oppia/oppia/statuses/7709a5b05e665b42e60d0d4d072e7d02f1aa2fe4"}}}}