{"action":"created","issue":{"url":"https://api.github.com/repos/ydwen/caffe-face/issues/1","repository_url":"https://api.github.com/repos/ydwen/caffe-face","labels_url":"https://api.github.com/repos/ydwen/caffe-face/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/ydwen/caffe-face/issues/1/comments","events_url":"https://api.github.com/repos/ydwen/caffe-face/issues/1/events","html_url":"https://github.com/ydwen/caffe-face/pull/1","id":184466120,"number":1,"title":"Optimize Backward Time Complexity to O(MK)","user":{"login":"mfs6174","id":773810,"avatar_url":"https://avatars.githubusercontent.com/u/773810?v=3","gravatar_id":"","url":"https://api.github.com/users/mfs6174","html_url":"https://github.com/mfs6174","followers_url":"https://api.github.com/users/mfs6174/followers","following_url":"https://api.github.com/users/mfs6174/following{/other_user}","gists_url":"https://api.github.com/users/mfs6174/gists{/gist_id}","starred_url":"https://api.github.com/users/mfs6174/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mfs6174/subscriptions","organizations_url":"https://api.github.com/users/mfs6174/orgs","repos_url":"https://api.github.com/users/mfs6174/repos","events_url":"https://api.github.com/users/mfs6174/events{/privacy}","received_events_url":"https://api.github.com/users/mfs6174/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":91,"created_at":"2016-10-21T11:44:30Z","updated_at":"2016-12-21T02:19:03Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/ydwen/caffe-face/pulls/1","html_url":"https://github.com/ydwen/caffe-face/pull/1","diff_url":"https://github.com/ydwen/caffe-face/pull/1.diff","patch_url":"https://github.com/ydwen/caffe-face/pull/1.patch"},"body":"In the original implementation, the time complexity of the backward process of the center loss layer is O(MK+NM). It will be very slow when training with a large number of classes since the running time of the backward pass is related to the class number (N). Unfortunately, it is a common case when training face recognition model (e.g. 750k unique persons).\n\nThis pull request rewrites the backward code. The time complexity is optimized to O(MK) with additional O(N) space.  Because M (batch size) << N and K (feature length) << N usually hold for face recognition problem, this modification will improve the training speed significantly.\n\nFor a Googlenet v2 model trained with Everphoto's 750k unique person dataset, on a single Nvidia GTX Titan X, with 24 batch size and iter_size = 5, the average backward iteration time for different cases is:\n1. Softmax only: 230ms\n2. Softmax + Center loss, original implementation: 3485ms, center loss layer: 3332ms\n3. Softmax + Center loss,  implementation in this PR: 235.6ms, center loss layer: 5.4ms\n\nThere is more than 600x improvement.\n\nFor the paper author's \"minit_example\", running on a single GTX Titan X, training time of the original implementation and the PR is  4min20s  V.S. 3min50s. It is shown that even when training with small dataset with only 10 classes, there still is some improvement.\n\nThe PR also fix the code style to pass the Caffe's lint test (make lint).\n"},"comment":{"url":"https://api.github.com/repos/ydwen/caffe-face/issues/comments/268416080","html_url":"https://github.com/ydwen/caffe-face/pull/1#issuecomment-268416080","issue_url":"https://api.github.com/repos/ydwen/caffe-face/issues/1","id":268416080,"user":{"login":"kli-nlpr","id":13194870,"avatar_url":"https://avatars.githubusercontent.com/u/13194870?v=3","gravatar_id":"","url":"https://api.github.com/users/kli-nlpr","html_url":"https://github.com/kli-nlpr","followers_url":"https://api.github.com/users/kli-nlpr/followers","following_url":"https://api.github.com/users/kli-nlpr/following{/other_user}","gists_url":"https://api.github.com/users/kli-nlpr/gists{/gist_id}","starred_url":"https://api.github.com/users/kli-nlpr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kli-nlpr/subscriptions","organizations_url":"https://api.github.com/users/kli-nlpr/orgs","repos_url":"https://api.github.com/users/kli-nlpr/repos","events_url":"https://api.github.com/users/kli-nlpr/events{/privacy}","received_events_url":"https://api.github.com/users/kli-nlpr/received_events","type":"User","site_admin":false},"created_at":"2016-12-21T02:19:03Z","updated_at":"2016-12-21T02:19:03Z","body":"@louielu1027  \r\nI am not sure,  I think the suspicious part is\r\n```\r\n/(count + (Dtype)1.)\r\n```\r\nThe ```count``` is not same at different batches."}}
{"actor":{"display_login":"kli-nlpr"}}