For the max recursion, this is a know issue in Theano. If Adam updates fix work while raising the max recursion limit use that.
Otherwise, you could help us fix the issue. Or make an op that does part of the work to make the graph even smaller, but it would need a GPU version if you want it to run on the GPU. Fred On Thu, Feb 16, 2017 at 9:58 AM Adam Becker <[email protected]> wrote: > My bad, that one gives wrong result, fixed version: > > def recursive_dot_reduce(A_, K_): > if K_<=1: return A_ > if K&1: > return recursive_dot_reduce(T.dot(T.batched_dot(A_[:-1:2], A_ > [::2]), A_[-1]), K_//2) > else > return recursive_dot_reduce(T.batched_dot(A_[::2], A_[1::2]), > K_//2) > > > On Thursday, February 16, 2017 at 10:52:28 PM UTC+8, Adam Becker wrote: > > Just for the dot reduction part, using batched_dot should give a O(log(n)) > graph depth: > > # assumes K > 1 > B = A > for i in reversed(bin(K)[3:]): > if not int(i): > B = T.batched_dot(B[::2], B[1::2]) > else: > B = T.dot(T.batched_dot(B[:-1:2], B[1::2]), B[-1]) > > This works if K is known in advance. > > An efficient way to construct A is still needed. > > Thursday, February 16, 2017 at 10:16:09 PM UTC+8, Oussama Souihli wrote: > > P.S. > If it helps, yes the indices are exactly the ones I have in the code. > > Thanks > Oussama > > On 16 February 2017 at 23:00, Oussama Souihli <[email protected]> wrote: > > Hi Fred, > > Thank you for the quick reply and clever suggestions, you really hit the > nail on the head ! > > I tried the suggested vectorized code, but unfortunately still experienced > the max recursion limit exception. > I also tried the workaround, but still get the max recusion limit until I > set it to 20K and I get a segmentation fault: > > Process finished with exit code 139 (interrupted by signal 11: SIGSEGV) > > > Can you think of other suggestions that I could try ? > If for-loop approach is doomed because of the max recursion issue, is > there perhaps a way I could rewrite my code such that scan becomes > reasonably faster ? > > > > On 16 February 2017 at 22:22, Frédéric Bastien <[email protected]> > wrote: > > Is the indices exatly the one you have in your code? If so, you can > probably take advantage of this to vectorize the code and make the for loop > case work. > > The size are so small then using scan will be super slow. Each iteration > of scan have big overhead and you only work on scalar mostly at each > iteration. So it is normal that it is slow with scan. > > For the for loop, there was a problem of indices. I fixed it. Here is a > partial vectorization of the code that will make it faster to execute and > make a smaller graph: > > coss = tt.cos(theta) > sins = tt.sin(theta) > > for k in range(0, K): > A = tt.set_subtensor(A[indices[k, 0], indices[k, 0]], coss[k]) > A = tt.set_subtensor(A[indices[k, 1], indices[k, 1]], coss[k]) > A = tt.set_subtensor(A[indices[k, 0], indices[k, 1]], sins[k]) > A = tt.set_subtensor(A[indices[k, 1], indices[k, 0]], -sins[k]) > B = tt.dot(A, B) > > The call to cos and sin are only done once. This make the graph smaller. > > You can also do the indexing call only once. THis make the graph still > smaller: > > coss = tt.cos(theta) > sins = tt.cos(theta) > > for k in range(0, K): > idx0 = indices[k, 0] > idx1 = indices[k, 1] > A = tt.set_subtensor(A[idx0, idx0], coss[k]) > A = tt.set_subtensor(A[idx1, idx1], coss[k]) > A = tt.set_subtensor(A[idx0, idx1], sins[k]) > A = tt.set_subtensor(A[idx1, idx0], -sins[k]) > B = tt.dot(A, B) > > The if the indices is exactly what you created and don't change, it can > become that is even smaller: > > for k in range(0, K): > idx0 = K//(N-1) > idx1 = indices[k, 1] > A = tt.set_subtensor(A[idx0, idx0], coss[k]) > A = tt.set_subtensor(A[idx1, idx1], coss[k]) > A = tt.set_subtensor(A[idx0, idx1], sins[k]) > A = tt.set_subtensor(A[idx1, idx0], -sins[k]) > B = tt.dot(A, B) > > You can do similar with j. > > If with that, you still have the max recursion limit, try the work around > in this issue. > > https://github.com/Theano/Theano/issues/3607 > > Fred > > On Thu, Feb 16, 2017 at 7:53 AM Oussama Souihli <[email protected]> > wrote: > > Hi Fred, Adam, Kiuhnm, all > > Thank you for the detailed and quick replies and multiple suggestions. > I tried bacthed_dot but still experienced both issues (maximum depth > recursion when using a for loop and very slow epochs when using > theano.scan), > so now I'm thinking the problem is also possibly due to the way I > populate the array A (using sub_tensor). > > Sorry for imposing on your kindness, but would you mind taking a look at > the attached, *very short*, minimal examples reproducing what I'm trying > to achieve ? > The examples are self-contained and only require python with numpy and > theano packages, nothing else. > > - *Issue_with_for_loop.py*: > - Reproduces the for-loop maximum recursion issue. > - if you run it as is, it will throw the exception on B.eval() > > - *Issue_with_scan.py*: > - This one shows the alternative way of implementing the logic using > scan. > - Unfortunately in this case it returns a result and gives the > impression like it works fine, but if I run it in Keras the epoch > duration > becomes prohibitively large (400,000 seconds per epoch !!) > > > If you can think of a way that can achieve the logic implemented in either > sheets with maximum efficiency theano-wise, I'd really appreciate it. > > > With gratitude, > Oussama > > -- > > --- > You received this message because you are subscribed to the Google Groups > "theano-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > > -- > > --- > You received this message because you are subscribed to a topic in the > Google Groups "theano-users" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/theano-users/Yz8g-cejB8c/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > [email protected]. > For more options, visit https://groups.google.com/d/optout. > > > > -- > > --- > You received this message because you are subscribed to the Google Groups > "theano-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- --- You received this message because you are subscribed to the Google Groups "theano-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
