Possibility for a tt conversion of a sparse tensor

[faysou]

This is useful in a CG optimization. For now I need to do this in order to compute the gradient, with m_masked and sparsity_mask as full tensors:

diff = t3f.to_tt_tensor(m_masked - sparsity_mask * t3f.full(X).numpy(), sparse_rank)

If I could convert them efficiently to tensor trains, I wouldn't need to go to the full format as an intermediate step.

This article could maybe be used. https://arxiv.org/abs/1908.02721

Or is there another way to do what I'm doing ? (I'm asking as this package is maintained by experts in the field of TT).

Thank you

[Bihaqo]

You can use these two lines to convert a sparse tensor into TT without touching the full tensor (by analytically representing each non-zero element individually with TT-rank 1 and then summing them up).

However, the problem with this approach is that the TT-rank of this mask equals to the number of non-zero element. Then, when you multiply it by your tensor the TT-ranks get multiplied and the final TT-rank is really big.

Alternatively, you can just index the tensor and compute the loss only on the non-zero elements, something like loss = tf.reduce_sum((tensor[non_zero_indices] - target_values)**2) Actually it's a bit more complicated and you have to use t3f.gather_nd. See example of doing this at the end of the completion tutorial.

Also, if you fancy Riemannian optimization, check out the Riemannian autodiff functionality :)

[faysou]

Interesting thank you. As a note the article above possibly has a place in your library as its goal is to make the representation of sparse tensors in tt format more efficient.

[Bihaqo]

Not sure what exactly do you mean, the algorithm of converting a sparse tensor to TT (first link) or something from the tutorial? I think that in most cases converting a sparse tensor into TT is not the best idea and there is an alternative better way. Do you know any good examples when it's not the case?

On Thu, 7 Nov 2019 at 23:09, faysou notifications@github.com wrote:

Interesting thank you. As a note the article above is to control the rank of sparse tensors, such algorithm has possibly a place in your library.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/Bihaqo/t3f/issues/192?email_source=notifications&email_token=ABK6V2OAKJNIMRATNAT6BELQSSNZHA5CNFSM4JKLHYV2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEDOEXBY#issuecomment-551308167, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABK6V2KJUHZJOFFPWT2LZPDQSSNZHANCNFSM4JKLHYVQ .

[faysou]

Actually what you're saying makes sense in the line below, a list of rank 1 tensors is expected to do the projection of the gradient, so a sparse tensor of all values at the same time is not required for tensor completion. https://github.com/Bihaqo/t3f/blob/autodiff_benchmark/docs/benchmark/utils.py#L140

Regarding the article, it just seemed interesting to me as they have an algorithm for rounding the sparse tensor (and I didn't realize at the time of my question I didn't need a sparse tensor with all the data at the same time).

Sorry if my questions seem naive, I discovered TT tensors only a few weeks ago, and I really enjoy reading about it. I've just managed to implement this paper: https://arxiv.org/abs/1902.04367

[Bihaqo]

No worries at all, keep up exploring and don't hesitate to ask questions :)

Note that if you need Riemannian gradient, using smart_grad is probably less efficient than autodiff:

task = Completion(n, d, rank)
riemannian_grad = t3f.gradients(task.loss, task.x)

[faysou]

I managed to make your last idea work, but my code was slower. Maybe I'm misusing tensorflow, I'll try more. I was using eager mode before.

[faysou]

Alexander, could you please give an example of t3f.gradients with tf.session and how to evaluate a TensorTrain to see its cores ? Thank you

[Bihaqo]

You mean how to get TT-cores of Riemannian gradient for tensor completion?

Here is an example.

def loss(x):
    estimated_vals = t3f.gather_nd(x, observed_idx)
    return 0.5 * tf.reduce_sum((estimated_vals - observations) ** 2)
riemannian_grad = t3f.gradients(loss, x)
with tf.Session() as sess:
  print(sess.run(riemannian_grad.tt_cores))

[faysou]

It works thank you. And indeed autodiff is much faster (about two times). Now I need to change my code to use this feature.

That's really good, now no need for a sparse tensor representation for the projection anymore.

It's going to be interesting too to understand how all this works. Your library is helpful as an abstraction layer, there's tons of knowledge inside it.

I used this code to compare the speeds:

tf.reset_default_graph() 

n, d, rank = 5,10,7
task = Completion(n, d, rank)

riemannian_grad = t3f.gradients(task.loss, task.x, runtime_check=False)
riemannian_grad2 = task.smart_grad()

with tf.Session() as sess:
    sess.run(tf.global_variables_initializer())

    for _ in range(5):
        sess.run(riemannian_grad.tt_cores)
        #sess.run(riemannian_grad2.tt_cores)

[Bihaqo]

Nice! A few more tips for benchmarking: 1) use sess.run(riemannian_grad.op) to measure the time to compute something without fetching fetching the value (espessially important if working on a GPU: .tt_cores would transfer the data from the GPU memory to CPU which is slow, while .op will just measure the computation time) 2) use tf utils for benchmarking (tf.test.benchmark_config() like here and tf.test.Benchmark().run_op_benchmark like here) to make sure that tensorflow doesn't discard ops it thinks are "redundant" and that the device you're using is ready (e.g. the first op ran on a GPU is always slow because the GPU has to come back from it's "sleep" state first).

To summarize:

n, d, rank = 5,10,7
task = Completion(n, d, rank)

riemannian_grad = t3f.gradients(task.loss, task.x, runtime_check=False)
riemannian_grad2 = task.smart_grad()

with tf.Session(config=tf.test.benchmark_config()) as sess:
    sess.run(tf.global_variables_initializer())
    benchmark = tf.test.Benchmark()
    print(benchmark.run_op_benchmark(sess, riemannian_grad.op)['wall_time'])
    print(benchmark.run_op_benchmark(sess, riemannian_grad2.op)['wall_time'])

[faysou]

Ok, thanks a lot for your help.