General classifier and HMM code for tensor networks

[jsalsman]

@sleichen @Thenerdstation thank you both for your fantastic work; I was so glad to meet you at your afternoon talk on Monday October 7, 2019. I have made no progress to speak of on my attempt at a tensor contraction-based gradient descent classifier, but I did find this:

https://github.com/glivan/tensor_networks_for_probabilistic_modeling

which is for: https://arxiv.org/pdf/1907.03741.pdf

They include model fitting, and measurement of the model, but not, as far as I can tell, any sort of classification methods. However this is no doubt in my mind that this will help you far more than the minimal classifier I attempted.

Best regards, Jim Salsman

[jsalsman]

So, if you use the above .fit() on a vector X = [v1 ... vn] can v1 be the dependent variable into which you are trying to fit? If so, how do you ask for the v1 given a [v2 .. vn]? This is essentially the same question I got to on the code I was attempting for you:

def gradient_decent(av=np.array([1,1,1,1,1,1,1,1,1,1], dtype=np.float32), 
                    bv=np.array([1,1,1,1,1,1,1,1,1,1], dtype=np.float32)):
      atv=tf.convert_to_tensor(av)
      btv=tf.convert_to_tensor(bv)
      a = tn.Node(tf.Variable(atv), backend="tensorflow")
      b = tn.Node(btv, backend="tensorflow")
      e = tn.connect(a[0], b[0])
      final_tensor = tn.contract(e).get_tensor()
      opt = tf.compat.v1.train.GradientDescentOptimizer(0.001)
      train_op = opt.minimize(final_tensor)
      sess = tf.compat.v1.Session()
      sess.run(tf.compat.v1.global_variables_initializer())
      sess.run(train_op)

It would seem that is a regression question, not classification, which uses discrete dependent classes (e.g, 0 or 1) but still ideally would produce [0,1] float as a probability in that case -- that is not generalizable to two or more dimensions, is it?

@sleichen @Thenerdstation Thanks again; moving the ping because edited the comment.

[jsalsman]

Oh, here, they use the classifier interface from the pomegranate library they adapt: https://pomegranate.readthedocs.io/en/latest/NaiveBayes.html

@Thenerdstation the question remains, can we easily port this to use TN? I'm guessing it's at least one if not two orders of magnitude easier for you and/or your team's resources, so I'm punting unless mistaken about that, and very glad to have found this before more than a few people had forked it.

@glivan fantastic work!

[chaserileyroberts]

Thank you for your inputs!

Closing this now as I'm not sure there is much we can add.

[jsalsman]

@Thenerdstation I was going to try to do this at the Developer Sprint in San Mateo. It's MIT licensed -- https://github.com/glivan/tensor_networks_for_probabilistic_modeling/blob/master/LICENSE -- do you have additional code review requirements?

[chaserileyroberts]

Nothing specific other than standard Google code review.

[jsalsman]

Please assign it to me and I will write up copious notes and copy over the minimal parts to do a native bayes classifier, hopefully well before the sprints next Wednesday and Thursday, in an ordinary pull request, and if you like it you can add the HMM parts later on. The simple classifier should be easy given the work the Germans have already done in their very similar library.

[jsalsman]

fit(): https://github.com/glivan/tensor_networks_for_probabilistic_modeling/blob/master/tensornetworks/MPSClass.py#L305

https://pomegranate.readthedocs.io/en/latest/NaiveBayes.html#prediction needs predict*()s from factoring; is that split_node() SVD? https://github.com/google/TensorNetwork/blob/master/tensornetwork/network_operations.py#L202

Reviewing https://www.nature.com/articles/s41534-018-0116-9#Sec1

[chaserileyroberts]

Yes, split node does SVD. What it does is it makes 2 tensors, One with value U sqrt(S) and another Vhat sqrt(S).

If you want a node with just the singular values, do split_node_full_svd

[jsalsman]

Great, that will work with the algorithm in Section 3.1.1 of http://files.grouplens.org/papers/webKDD00.pdf

I want to study the sparse case before making any serious implementation decisions https://www.researchgate.net/profile/Dawit_Tadesse2/publication/322854540_A_method_for_selecting_the_relevant_dimensions_for_high-dimensional_classification_in_singular_vector_spaces/links/5a7c658baca272669a2cd4da/A-method-for-selecting-the-relevant-dimensions-for-high-dimensional-classification-in-singular-vector-spaces.pdf

[jsalsman]

Trying to allow for privacy at least down the road http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.448.8246&rep=rep1&type=pdf

Hardware: https://github.com/quantumlib/Cirq/tree/master/examples see also: https://www.youtube.com/watch?v=kblpyvpYQKg

[glivan]

Hi @jsalsman , Ivan here. I don't know exactly what you are trying to do, but if you have any questions related to what we do in our paper or how to implement it feel free to ask. @Thenerdstation : will there be any of the people involved in TensorNetwork at NeurIPS in Vancouver next week? I will be presenting our paper there, and I am happy to chat about tensor networks and your library.

[jsalsman]

@glivan thanks, Ivan! I want to implement the predict_log_proba() method as per https://pomegranate.readthedocs.io/en/latest/api.html#compositional-methods Do you have that yet? There is C for it at https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/svm/src/libsvm/svm.cpp#L2888

I'm also interested in porting the fit() method to Google's new Sycamore chip quantum computers, as per https://arxiv.org/pdf/1611.09347.pdf starting around p. 4. I see there is a phase estimator at https://cirq.readthedocs.io/en/stable/examples.html#phase-estimator but I don't know how to use QRAM.

@Thenerdstation does Sycamore even have QRAM yet? Please see also https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.114.140504 and https://www.sciencedirect.com/science/article/pii/S2095927317303250 as I am sure you would prefer the distributed, privacy-protecting version.

[chaserileyroberts]

Yes! My team will be at neurips. Infact, we'll be holding a workshop on the library on Sunday.

[jsalsman]

Happy to proceed with Principal Component Analysis-based classification which per p. 4 of arxiv:1611.09347 can be done without QRAM.

I am considering some documentation claiming that predict_proba() uses cross-validation on predict(), at least for scikit-learn's SVMs. Since I want to produce a probability distribution function instead of a probability, which is a pair instead of a scalar, and because I want the routine to operate well cross-platform on traditional and quantum hardware, it will take me more than next week to propose some code. It also seems courteous to pause for @glivan's comments -- i.e., would you like this assigned to you, Ivan?

[jsalsman]

In any case, please see https://acadgild.com/blog/logistic-regression-with-pca-algorithm

and https://www.cs.cmu.edu/~ggordon/10601/recitations/rec07/rec07.pdf by ggordon dot cs at gmail dot com https://www.youtube.com/playlist?list=PL7y-1rk2cCsAqRtWoZ95z-GMcecVG5mzA

[jsalsman]

I've decided to use the "quest recommendation game" as an example application for writing the initial test: https://www.aaai.org/ocs/index.php/AIIDE/AIIDE18/paper/viewFile/18124/17229

See also https://link.springer.com/article/10.1007/s13218-019-00620-2

[jsalsman]

@glivan out of an abundance of caution, I am suggesting this should be assigned to you, to whomever you or Chase prefers, or me.

[jsalsman]

@sleichen @Thenerdstation @glivan I hope you are all well. I am going to resume work on this since it's been 25 days and none of you have said anything.

I want to apologize for suggesting overly narrow confidence intervals in the deleted postscript, and have switched to one sigma and included a 2-D example here: https://colab.research.google.com/drive/1sS3FK9q3rOIhIfNaohYhojNlssZWVWQX

Ivan do you want to tell me anything about https://github.com/glivan/tensor_networks_for_probabilistic_modeling/blob/master/poster.png before I move on to trying to perform simple logistic regression?

[jsalsman]

@MrChrisJohnson, as the author of http://stanford.edu/~rezab/nips2014workshop/submits/logmat.pdf, have you been using any tensor libraries to perform logistic regression for recommendation engines?

[chaserileyroberts]

I'm taking the executive decision to lock this thread as I see no goal state or reason to keep this open.