{"action":"created","issue":{"url":"https://api.github.com/repos/tensorflow/tensorflow/issues/13557","repository_url":"https://api.github.com/repos/tensorflow/tensorflow","labels_url":"https://api.github.com/repos/tensorflow/tensorflow/issues/13557/labels{/name}","comments_url":"https://api.github.com/repos/tensorflow/tensorflow/issues/13557/comments","events_url":"https://api.github.com/repos/tensorflow/tensorflow/issues/13557/events","html_url":"https://github.com/tensorflow/tensorflow/pull/13557","id":263671195,"node_id":"MDExOlB1bGxSZXF1ZXN0MTQ1MzA4MzU1","number":13557,"title":"Fix the gradient computation of dynamic stitch.","user":{"login":"codrut3","id":10788581,"node_id":"MDQ6VXNlcjEwNzg4NTgx","avatar_url":"https://avatars1.githubusercontent.com/u/10788581?v=4","gravatar_id":"","url":"https://api.github.com/users/codrut3","html_url":"https://github.com/codrut3","followers_url":"https://api.github.com/users/codrut3/followers","following_url":"https://api.github.com/users/codrut3/following{/other_user}","gists_url":"https://api.github.com/users/codrut3/gists{/gist_id}","starred_url":"https://api.github.com/users/codrut3/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/codrut3/subscriptions","organizations_url":"https://api.github.com/users/codrut3/orgs","repos_url":"https://api.github.com/users/codrut3/repos","events_url":"https://api.github.com/users/codrut3/events{/privacy}","received_events_url":"https://api.github.com/users/codrut3/received_events","type":"User","site_admin":false},"labels":[{"id":390482148,"node_id":"MDU6TGFiZWwzOTA0ODIxNDg=","url":"https://api.github.com/repos/tensorflow/tensorflow/labels/awaiting%20review","name":"awaiting review","color":"fef2c0","default":false},{"id":300136587,"node_id":"MDU6TGFiZWwzMDAxMzY1ODc=","url":"https://api.github.com/repos/tensorflow/tensorflow/labels/cla:%20yes","name":"cla: yes","color":"009800","default":false}],"state":"open","locked":false,"assignee":{"login":"aselle","id":326106,"node_id":"MDQ6VXNlcjMyNjEwNg==","avatar_url":"https://avatars1.githubusercontent.com/u/326106?v=4","gravatar_id":"","url":"https://api.github.com/users/aselle","html_url":"https://github.com/aselle","followers_url":"https://api.github.com/users/aselle/followers","following_url":"https://api.github.com/users/aselle/following{/other_user}","gists_url":"https://api.github.com/users/aselle/gists{/gist_id}","starred_url":"https://api.github.com/users/aselle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aselle/subscriptions","organizations_url":"https://api.github.com/users/aselle/orgs","repos_url":"https://api.github.com/users/aselle/repos","events_url":"https://api.github.com/users/aselle/events{/privacy}","received_events_url":"https://api.github.com/users/aselle/received_events","type":"User","site_admin":false},"assignees":[{"login":"aselle","id":326106,"node_id":"MDQ6VXNlcjMyNjEwNg==","avatar_url":"https://avatars1.githubusercontent.com/u/326106?v=4","gravatar_id":"","url":"https://api.github.com/users/aselle","html_url":"https://github.com/aselle","followers_url":"https://api.github.com/users/aselle/followers","following_url":"https://api.github.com/users/aselle/following{/other_user}","gists_url":"https://api.github.com/users/aselle/gists{/gist_id}","starred_url":"https://api.github.com/users/aselle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aselle/subscriptions","organizations_url":"https://api.github.com/users/aselle/orgs","repos_url":"https://api.github.com/users/aselle/repos","events_url":"https://api.github.com/users/aselle/events{/privacy}","received_events_url":"https://api.github.com/users/aselle/received_events","type":"User","site_admin":false}],"milestone":null,"comments":9,"created_at":"2017-10-07T20:50:05Z","updated_at":"2018-09-08T18:36:40Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/tensorflow/tensorflow/pulls/13557","html_url":"https://github.com/tensorflow/tensorflow/pull/13557","diff_url":"https://github.com/tensorflow/tensorflow/pull/13557.diff","patch_url":"https://github.com/tensorflow/tensorflow/pull/13557.patch"},"body":"Currently the gradient of tf.dynamic_stitch is not correct for duplicated indices. This is\r\nissue #7397. @drasmuss submitted a pull request for this issue, but it was ultimately not merged\r\ndue to a performance drop.\r\n\r\nWhile working on this, I realised that the problem is more complicated than what follows\r\nfrom the discussion in #7487. In fact, the solution proposed in #7487 is not correct, because\r\none can have duplicated indices in the same input tensor. The following example shows this:\r\n\r\n```\r\nimport tensorflow as tf\r\n\r\nx = tf.zeros((3,))\r\ny = tf.dynamic_stitch([[0, 1, 0]], [x])\r\n\r\nwith tf.Session() as sess:\r\n    print(\"y\")\r\n    print(sess.run(y))\r\n\r\n    analytic, numeric = tf.test.compute_gradient(x, (3,), y, (2,))\r\n    print(\"analytic\")\r\n    print(analytic)\r\n    print(\"numeric\")\r\n    print(numeric)\r\n```\r\n\r\nThe output (even with #7487) is\r\n\r\n```\r\ny\r\n[ 0.  0.]\r\nanalytic\r\n[[ 1.  0.]\r\n [ 0.  1.]\r\n [ 1.  0.]]\r\nnumeric\r\n[[ 0.          0.        ]\r\n [ 0.          0.99998707]\r\n [ 0.99998707  0.        ]]\r\n```\r\n\r\nMy fix is to add a new kernel op `GatherDisjoint`, that can handle all the inputs together.\r\nThis replaces the `n` calls to `gather` in `data_flow_grad._DynamicStitchGrads` with a\r\nsingle `gather_disjoint`.\r\n\r\nThe implementation is very similar to `gather`, I just zero out duplicated slices at the end.\r\nI've put this op in core/, if you would like I can move it to contrib/, just let me know where.\r\n\r\nI've also added tests for the op and new tests for the gradient of dynamic stitch. Here\r\nI inspired myself from @drasmuss pull request.\r\n\r\nI've run the script by @drasmuss again:\r\n\r\n```\r\nimport time\r\n\r\nimport numpy as np\r\nimport tensorflow as tf\r\n\r\nstitch_size = 1000\r\nn_inputs = 10\r\ninput_shape = (100, 50, 50)\r\nreps = 10\r\n\r\nwith tf.device(\"cpu:0\"):\r\n    idxs = [tf.constant(np.random.randint(stitch_size, size=input_shape[0]), dtype=tf.int32)\r\n            for _ in range(n_inputs)]\r\n    vals = [tf.constant(np.random.uniform(-1, 1, size=input_shape), dtype=tf.float32)\r\n            for _ in range(n_inputs)]\r\n    y = tf.dynamic_stitch(idxs, vals)\r\n    grad = tf.gradients(y, vals)\r\n\r\ntotal_time = 0.0\r\nfor _ in range(reps):\r\n    with tf.Session() as sess:\r\n        start = time.time()\r\n        sess.run(grad)\r\n        total_time += time.time() - start\r\n\r\nprint(total_time / reps)\r\n```\r\n\r\nThe results are as follows:\r\nwith my fix:\r\nCPU - 0.09455678462982178\r\nGPU - 0.09739606380462647\r\nwithout my fix:\r\nCPU - 0.11728813648223876\r\nGPU - 0.11805038452148438\r\n\r\nSo with the fix it runs faster. On GPU the slowdown is due to the memory copies from host to device\r\nand back, for input and output (I've checked with nvprof), and not because of my fix.\r\n\r\nI've run this script using local builds of the same master branch, with and without my patch.\r\n\r\nLet me know if the op should be moved somewhere else, or it should be made hidden."},"comment":{"url":"https://api.github.com/repos/tensorflow/tensorflow/issues/comments/419664115","html_url":"https://github.com/tensorflow/tensorflow/pull/13557#issuecomment-419664115","issue_url":"https://api.github.com/repos/tensorflow/tensorflow/issues/13557","id":419664115,"node_id":"MDEyOklzc3VlQ29tbWVudDQxOTY2NDExNQ==","user":{"login":"tensorflowbutler","id":28546240,"node_id":"MDQ6VXNlcjI4NTQ2MjQw","avatar_url":"https://avatars2.githubusercontent.com/u/28546240?v=4","gravatar_id":"","url":"https://api.github.com/users/tensorflowbutler","html_url":"https://github.com/tensorflowbutler","followers_url":"https://api.github.com/users/tensorflowbutler/followers","following_url":"https://api.github.com/users/tensorflowbutler/following{/other_user}","gists_url":"https://api.github.com/users/tensorflowbutler/gists{/gist_id}","starred_url":"https://api.github.com/users/tensorflowbutler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tensorflowbutler/subscriptions","organizations_url":"https://api.github.com/users/tensorflowbutler/orgs","repos_url":"https://api.github.com/users/tensorflowbutler/repos","events_url":"https://api.github.com/users/tensorflowbutler/events{/privacy}","received_events_url":"https://api.github.com/users/tensorflowbutler/received_events","type":"User","site_admin":false},"created_at":"2018-09-08T18:36:40Z","updated_at":"2018-09-08T18:36:40Z","author_association":"MEMBER","body":"Nagging Reviewer @aselle: You have been added as a reviewer to this pull request. Please add your review or reassign. It has been 262 days with no activity and the `awaiting review` label has been applied."}}
{"actor":{"display_login":"tensorflowbutler"}}