Implements Cumprod function for autograd by martinarjovsky · Pull Request #1439 · pytorch/pytorch

martinarjovsky · 2017-05-02T17:22:56Z

In reference to #1095 :)

The algorithm for nonzero elements is straightforward and pretty fast, but when zero elements
are present is pretty hard to do vectorized (and O(n^2) with n elements in the dimension of the input where the cumprod is done), hence the code is a bit complex.

A set of extra tests passed is present here https://gist.github.com/martinarjovsky/1d4679c54b2fc5cddf73cdd45b359c9f

torch/autograd/_functions/tensor.py

+
+        if (input == 0).any():
+            ones = input.index_select(self.dim,
+                    LT(range(1))).fill_(1).clone()


torch/autograd/_functions/tensor.py

+            LT = torch.LongTensor
+
+        if (input == 0).any():
+            ones = input.index_select(self.dim,


torch/autograd/_functions/tensor.py

+                # At this point ommitted_products is the same size
+                # as input, except on the dimension dim where it's
+                # dim_size - k
+                assert ommitted_products.size()[self.dim] == dim_size - k, \


torch/autograd/_functions/tensor.py

+                        torch.sum(grad_output * ommitted_products, dim=self.dim))

+        else:
+            output = torch.cumprod(input, dim=self.dim)


torch/autograd/_functions/tensor.py

+
+class Cumprod(Function):
+
+    def __init__(self, dim):


torch/autograd/_functions/tensor.py

+                        LT(range(k))), dim=self.dim)
+
+                    prods_from_k_plus_1 = torch.cumprod(input.index_select(
+                        self.dim, LT(range(k+1, dim_size))), dim=self.dim)


torch/autograd/_functions/tensor.py

+                        LT(range(k))), dim=self.dim)
+
+                    ommitted_products = prods_until_k
+                else: #k == 0


torch/autograd/_functions/tensor.py

+        else:
+            LT = torch.LongTensor
+
+        if (input == 0).any():


torch/autograd/_functions/tensor.py

+                    prods_from_k_plus_1 = torch.cumprod(input.index_select(
+                        self.dim, LT(range(k+1, dim_size))), dim=self.dim)
+
+                    ommitted_products = prods_until_k.expand_as(


torch/autograd/_functions/tensor.py

+                # as input, except on the dimension dim where it's
+                # dim_size - k
+                assert ommitted_products.size()[self.dim] == dim_size - k, \
+                    "Dimension error"


torch/autograd/_functions/tensor.py

+                    "Dimension error"
+
+                if k != 0:
+                    size_to_expand = [l for l in input.size()]


torch/autograd/_functions/tensor.py

+                    size_to_expand = [l for l in input.size()]
+                    size_to_expand[self.dim] = k # Adding zeros to missing dimensions
+                    size_to_expand = torch.Size(size_to_expand)
+                    expanded_zeros = zeros.expand(size_to_expand)


fmassa · 2017-05-02T23:06:19Z

Did we consider using the implementation of cumsum to compute cumprod? We could writesomething like

def cumprod(x):
    return exp(cumsum(log(x)))

Maybe it's very unstable computing it like that?

apaszke · 2017-05-02T23:10:36Z

@fmassa I'd expect it to be very very unstable for x close to 0 (+ cumprod is well defined when some values are 0, but your definition doesn't handle that case - log will give you -infs)

fmassa · 2017-05-03T18:14:17Z

@apaszke I'm not so sure that it would be very very unstable for x close to 0, the forward pass doesn't seem to be that sensitive.
My implementation doesn't handle the cases where x <= 0, but that can be easily fixed I think.
Anyway, those are my 2 cents on the matter. :)

martinarjovsky · 2017-05-04T15:18:00Z

@fmassa This would have two problems.

It wouldn't support negative inputs.
It wouldn't support zero inputs.

The case with nonzero inputs (including x < 0) is handled in two lines already by doing

output = torch.cumprod(input, dim=self.dim)
return reverse_cumsum(output * grad_output, dim=self.dim) / input

It's the case with zeros that's hard :)

martinarjovsky · 2017-05-04T20:57:02Z

Just fixed (or at least attempted) the issues. I added a detailed comment of the algorithm for the backward pass but it's likely way to much. Should I take it out and put it in the PR instead?

torch/autograd/_functions/tensor.py

+            idx = torch.LongTensor(range(dim_size))
+
+        ones = input.select(self.dim, 0).unsqueeze(self.dim).clone().fill_(1)
+        zeros = ones.clone().fill_(0)


torch/autograd/_functions/tensor.py

+    ret = torch.cumsum(-x, dim=dim)
+
+    end_idx = ret.size(dim) - 1
+    ret_sum = ret.narrow(dim, end_idx, 1)


torch/autograd/_functions/tensor.py

        return grad_input


+def reverse_cumsum(x, dim):


torch/autograd/_functions/tensor.py

+                    self.dim
+                )
+
+            grad_input.index_copy_(


torch/autograd/_functions/tensor.py

+        else:
+            idx = torch.LongTensor(range(dim_size))
+
+        ones = input.select(self.dim, 0).unsqueeze(self.dim).clone().fill_(1)


torch/autograd/_functions/tensor.py

+        if input.is_cuda:
+            idx = torch.cuda.LongTensor(range(dim_size))
+        else:
+            idx = torch.LongTensor(range(dim_size))


torch/autograd/_functions/tensor.py

+                ommitted_products = torch.cat(
+                    (zeros.expand(size_to_expand), ommitted_products),
+                    self.dim
+                )


colesbury · 2017-05-24T18:57:09Z

@pytorchbot add to whitelist

martinarjovsky · 2017-06-09T12:16:27Z

@apaszke Anything else I should do? :)

apaszke · 2017-06-09T14:28:42Z

Sorry, we're all busy with v0.2 features. I'll try to review it soon and let you know, but it should be good.

torch/autograd/_functions/tensor.py

+        input, = self.saved_tensors
+        dim_size = input.size(self.dim)
+        if dim_size == 1:
+            return grad_output.clone()


torch/autograd/_functions/tensor.py

+
+        ones_size = list(input.size())
+        ones_size[self.dim] = 1
+        ones = input.new().resize_(ones_size).fill_(1)


torch/autograd/_functions/tensor.py

+        ones_size = list(input.size())
+        ones_size[self.dim] = 1
+        ones = input.new().resize_(ones_size).fill_(1)
+        zeros = ones * 0


torch/autograd/_functions/tensor.py

+
+            grad_input.select(self.dim, k).copy_(torch.sum(
+                grad_output[dim_padding + (slice(k, None),)] * omitted_products,
+                dim=self.dim).squeeze())


apaszke · 2017-06-13T15:48:35Z

Thank you!

* initial volta support * mma parallel type && cleanup * cleanup * alignment * comment * change request * fix same parallel type * move validation pass * comment and cleanup * lint * comment and cleanup * comment and format

* SWDEV-469009 - skips for flaky distributed tests * Missed a file

Martin Arjovsky added 5 commits April 5, 2017 22:59

Initial setup for cumprod

e0327b4

[WIP] implemented backward for cumprod when input is nonzero

ee2f389

Finishing implementation of cumprod, tests passed but not included

0862591

adding tests

b0e2072

Fixing final bugs, all tests passed

fd08916

albanD reviewed May 2, 2017

View reviewed changes

apaszke reviewed May 2, 2017

View reviewed changes

Fixing linting issues + the ones in the review

746bc60

adding clone when returning grad_output

b56318d

apaszke reviewed May 7, 2017

View reviewed changes

Martin Arjovsky and others added 3 commits May 23, 2017 08:42

Adding efficiency and style changes

09c43bb

Merge branch 'master' into master

10d92fa

Fixing linting issue

d235103

apaszke reviewed Jun 10, 2017

View reviewed changes

martinarjovsky and others added 4 commits June 12, 2017 18:53

Merge branch 'master' into master

870381a

[WIP] Finished merging with master

00a8af9

Removing extra zero tensor

456d296

Finished, adding expand for ones

0764d73

apaszke approved these changes Jun 13, 2017

View reviewed changes

apaszke merged commit 7c024e9 into pytorch:master Jun 13, 2017

jagadish-amd pushed a commit to jagadish-amd/pytorch that referenced this pull request Sep 5, 2024

SWDEV-469009 - skips for flaky distributed tests (pytorch#1439)

95a9338

* SWDEV-469009 - skips for flaky distributed tests * Missed a file

Conversation

martinarjovsky commented May 2, 2017

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

fmassa commented May 2, 2017

Uh oh!

apaszke commented May 2, 2017

Uh oh!

fmassa commented May 3, 2017

Uh oh!

martinarjovsky commented May 4, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

martinarjovsky commented May 4, 2017

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

This comment was marked as off-topic.

Uh oh!

martinarjovsky commented May 4, 2017 •

edited

Loading