7 ms·

Matrices as Tensor Network Diagrams

225 points by _Microft 7y ago

_Microft 7y ago
How would one write a cross-product with that? Using two vectors and the epsilon tensor (Levi-Chivita-symbol), I guess? Edit: So like this: two circles with one connection each as input, i.e. vectors (a and b), and a tensor with three connections, leaving one, meaning the result will be a vector again. a o \ o - (-o c) / b o Multiplying with another vector c gives the parallelepipedial product (a x b) c, a scalar (also = det(a,b,c)). Cool :)
- mathgenius 7y ago
  Yeah, and this works for any "algebra" (ie. vector space with a way of multiplying vectors.) The three legged thing is what they call the "structure constants" for the algebra.
  - _Microft 7y ago
    Would it make sense/work to do something like this ? (a x b )(c x d) => ??? o o o o \ / \ / o - o => o / \ / \ o o o o Would the circle in the middle of the cross be a tensor of order 4 then? Edit: It's been a while since I did that but wouldn't that be the following in sum notation? eps_ijk a_j b_k eps_ilm c_l d_m = (new tensor)_jklm a_j b_k c_l d_m
    - mathgenius 7y ago
      Yes it really is just like lego, you can make all kinds of bizarro shapes.
- kgwgk 7y ago
  “Chivita“ is written Civita. Chivita would be pronounced “Kivita”. :-)
- kmill 7y ago
  Yeah, cross product is the determinant with "one strand bent back." If you take a 3-regular planar graph and put the determinant/Levi-Civita tensor on each vertex, you get plus-or-minus the number of edge-3-colorings of that graph. The four-color theorem is merely to show this tensor contraction is always non-zero :-) (Nobody's managed to prove it this way, yet.) Here are some notes showing how to contract two Levi-Civita symbols together graphically: https://imgur.com/HmaLSaB.png https://imgur.com/HmaLSaB.png This is in Penrose's 1971 paper ("Applications of negative-dimensional tensors"). He went on to notice that you can do a "puff-up-and-contract" construction to completely get rid of all the Levi-Civita tensors: https://imgur.com/eK9ZCkc.png https://imgur.com/eK9ZCkc.png From here, he recognized that this sort of tensor network on 3-dimensional space was equivalent to an abstract tensor network on "(-2)-dimensional space", where there is an identity that let him remove all the places the strings cross https://imgur.com/65z0zov.png https://imgur.com/65z0zov.png (This element placed at each edge in (-2)-dimensional space is known as the "second Jones-Wenzl projector for the Temperley-Lieb algebra.") From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic).
  - _Microft 7y ago
    Negative-dimensional tensors... now that's wild. Thanks for the sketches, I'll have a look!
  - JadeNB 7y ago
    > From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic). Locally isomorphic, but not isomorphic: SL(2) is the simply connected double cover Spin(3) of SO(3). As you probably know, the non-simply-connectedness of SO(3) is what's witnessed by Dirac's belt trick (https://en.wikipedia.org/wiki/Plate_trick https://en.wikipedia.org/wiki/Plate_trick).
    - kmill 7y ago
      Thanks, that's right. (I had the Lie algebras in mind with that statement. The Lie brackets are placed at the vertices in the construction.)
stared 7y ago
The other time, during a discussion about Feynman diagrams (https://news.ycombinator.com/item?id=19909542 https://news.ycombinator.com/item?id=19909542) I mentioned some resources related to tensor diagrams (https://medium.com/@pmigdal/in-the-topic-of-diagrams-i-did-write-a-review-simple-diagrams-of-convoluted-neural-networks-6418a63f9281 https://medium.com/@pmigdal/in-the-topic-of-diagrams-i-did-w...). Happy this topic gets more mainstream, and this blog post by Tai-Danae Bradley is pure gold! Practical things: who want to co-write a library (JS I guess) for drawing such tensor diagrams? I think it has a lot of potential for representing formulae, form Markov Chains, through Quantum Computing to Deep Learning!
GorgeRonde 7y ago
In many different areas of scientific investigation, purely diagrammatic expressions have begun to be used as mathematical substitutes for the traditional symbolic expressions. These new languages reflect clear operational concepts such as ‘systems’ and ‘processes’, and ‘wires’ are used to represent information flow. Composition is built-in, as the act of connecting wires together. These diagrams are more intuitive, and easier to manipulate, than conventional symbolic models of reasoning. Examples of areas in which these techniques are being used include logic, for the study of propositions and deductions [43]; physics, for the study of space and spacetime [8, 32]; linguistics, to model the interaction of words within a sentence [21]; knowledge, to represent information and belief revision [22]; and computation, for the study of data and computer programs [1, 10]. These diagrams have been provided with a rigorous underpinning using category theory, a powerful branch of mathematics which relates these diagrammatic theories to algebraic structures. More deeply, this approach can also be applied to the study of diagrammatic theories themselves [12, 33]. As such, it is its own ‘metatheory’. One major goal of the project will be to understand to what extent this can serve as a foundation for mathematics itself, as a replacement for set theory. To work towards this, one goal will be to understand how various mathematical structures can be defined from this perspective, a rich line of enquiry for which some answers are already known, but much more is left to still be discovered. An interesting feature of categorical approaches to foundations is that standard limitative theorems, such as the incompleteness theorem of Godel, are no longer set in stone [7, 39]; instead, they become malleable, and can be directly ¨ controlled by changing the categorical universe in which one works. Switching to the field of artificial intelligence and automation — perhaps, so it seems, a world away from the abstraction of higher mathematics — the diagrammatic categories themselves have been implemented as the actual language and deduction mechanism of automated reasoning software packages. These tools make it possible to automatically explore the theories formulated in the diagrammatic language. For the case of the abstract mathematical expressions, the package quantomatic, currently in development at the Computing Laboratory at the University of Oxford, performs this function. For the particular case of diagrammatic models of language and meaning, parsers and tools for corpus exploration are currently under development. The study of each of these ‘diagrammatic theories’, each modelling a separate part of cognitive, physical, or mathematical reality, are currently separate. Our grand vision is to develop a fully integrated framework, in which all of the above can be comprehended and dealt with together. This would be a foundation for mathematics, not in isolation but in direct relation to the cognitive and physical worlds; not only as an exercise in abstract thought, but directly implemented computationally, with tools available for automatic calculation and deduction. The unique perspective given by categorical foundations on Godel-style theorems will allow their relevance to cognition to be rigorously studied. The strong mathematical similarities between the diagrammatic techniques used in these different fields, which have only recently begun to be appreciated, provides a good impetus for this research programme. Source: An integrated diagrammatic universe for knowledge, language and artificial reasoning. Abramsky & Coecke, Oxford. http://www.cs.ox.ac.uk/people/bob.coecke/JTFCats.pdf http://www.cs.ox.ac.uk/people/bob.coecke/JTFCats.pdf
layoutIfNeeded 7y ago
The computer graphics pioneer Jim Blinn has a nice lecture on tensor diagrams: https://www.youtube.com/watch?v=40TdlWURkS8 https://www.youtube.com/watch?v=40TdlWURkS8
- jacobolus 7y ago
  https://www.microsoft.com/en-us/research/wp-content/uploads/2002/01/UsingTensorDiagrams.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
whatshisface 7y ago
What bothers me about this is, all indices are not the same. You could draw a line connecting a 5-dimensional index to a 3-dimensional one. There should be some way of separating incompatible indices. Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive - although some go from 1 to 3. Conventionally, this is dealt with by using Greek letters for 4-vectors and regular letters for 3-vectors.
- Certhas 7y ago
  You put labels on lines. For example the diagram here works like that: https://en.wikipedia.org/wiki/6-j_symbol https://en.wikipedia.org/wiki/6-j_symbol
- jessriedel 7y ago
  > Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive These days physicists who do tensor-network analysis and simulations of many-body quantum systems (e.g., MPS in 1D) probably use the diagrams more than relativists, and in those cases the indices can come with arbitrary dimensions.
- tom-thistime 7y ago
  Normal matrix notation has the same problem. I can write AB even if A is 5x5 and B is 3x3.
pfortuny 7y ago
I am sad to bring sad tidings but... This is very beautiful, it just puts the burden of the proof on a more abstract setting, which may be more difficult to grasp. (This is just a comment on the "graphical proofs", they are beautiful but they cannot be "proofs" unless you provide the background).
- mathgenius 7y ago
  It's turtles all the way down: https://graphicallinearalgebra.net/2015/06/09/matrices-diagrammatically/ https://graphicallinearalgebra.net/2015/06/09/matrices-diagr...
- Certhas 7y ago
  These are not "graphical proofs" in the sense of pictures that suggest patterns in mathatical relations. This is (or can be) a formal graphical language for (a branch of) mathematics. Like any formal language it's not self evident how or why it works and needs to be rigourously defined.
gdubs 7y ago
If I remember correctly, Einstein struggled with Tensors and enlisted his friend Mercel Grossmann to help him develop the Tensor Calculus he needed for the General Theory of Relativity. Einstein was no mathematical slouch, obviously, but it’s nice to know that even the most brilliant sometimes need some help from their friends.
- mathgenius 7y ago
  Indeed, the "einstein summation convention" is a slightly more primitive version of this graphical tensor notation.
JWKennington 7y ago
Slight nit-pick, but matrix multiplication is not exclusively a contraction, but rather a contraction on the tensor product of the two matrices. See the next paragraph for why this is concerning. I find this notation great for simple applications, but potentially unwieldy for dim > 2. For instance, how would I represent the tensor (or outer) product of two matrices? the inputs would be two circles with two lines attached to each, the result would need to be a single circle with four lines attached. The natural attempt would be something like: a - o - / / | / \ | ab ---o--- | \ / | / / b - o - But I suspect the above diagram isn't correct because there are no "open" indices at the end of this. Rather, this diagram seems to represent the contraction of a 4D tensor with 2, 2D tensors. It seems we we would need a way of connecting circles without implying a contraction of a particular index. Anyone know how to annotate the outer product of two matrices in this diagrammatic convention?
- mcabbott 7y ago
  A tensor product of two matrices is just this, with 4 loose ends: ---A--- ---B--- A_ab B_cd = (A⊗B)_acbd. If a,c=1...N then you can think of (ac) as being an index with N^2 possible values, which is what the double line now means... if you like, you may compact it a bit: ===(A⊗B)===
  - JWKennington 7y ago
    But how am I supposed to know that AB is one mathematical object here instead of the 2 separate objects A, B? My point is that there should be a graphical way other than "put them arbitrarily close" to link them together I prefer your second notation, with the tensor product happening in parenthesis, but it kind of defeats the point of the graphical nature of the notation if we need to explictly write the tensor product I think..
    - kmill 7y ago
      Speaking as someone who uses this tensor notation quite a lot: putting multiple objects into the same diagram is what a tensor product is, and a great thing about the notation is that it reveals that a tensor product of two matrices is not an essential object in itself. If you wish, you can draw a circle around A and B to "factor out" that part of the diagram as a sub tensor product. Here might be a way to show that matrix multiplication is both "tensor product then contract" and "function composition": https://imgur.com/tcCycYj.png https://imgur.com/tcCycYj.png (though I didn't give this gray-circle notation much thought). Think about this: how is it in a product abcd of plain old numbers am I supposed to see the mathematical object ad without putting them arbitrarily close together? (Well, in standard notation, you do put them close together and write (ad)bc or something.)
outlace 7y ago
To those interested in machine learning, this idea naturally leads to “deep tensor networks” that are neural networks that can operate on and with high order tensors. I wrote a (non-rigorous) blog post about this: http://outlace.com/TensorNets1.html http://outlace.com/TensorNets1.html
- imcoconut 7y ago
  excellent post, thank you.
deleted 7y ago
[deleted]
mrcactu5 7y ago
here are some pages that might be relevant https://ncatlab.org/nlab/show/tensor+network https://ncatlab.org/nlab/show/tensor+network https://ncatlab.org/nlab/show/string+diagram https://ncatlab.org/nlab/show/string+diagram

225 points by _Microft 7y ago

How would one write a cross-product with that? Using two vectors and the epsilon tensor (Levi-Chivita-symbol), I guess? Edit: So like this: two circles with one connection each as input, i.e. vectors (a and b), and a tensor with three connections, leaving one, meaning the result will be a vector again. a o \ o - (-o c) / b o Multiplying with another vector c gives the parallelepipedial product (a x b) c, a scalar (also = det(a,b,c)). Cool :)

mathgenius 7y ago
Yeah, and this works for any "algebra" (ie. vector space with a way of multiplying vectors.) The three legged thing is what they call the "structure constants" for the algebra.
- _Microft 7y ago
  Would it make sense/work to do something like this ? (a x b )(c x d) => ??? o o o o \ / \ / o - o => o / \ / \ o o o o Would the circle in the middle of the cross be a tensor of order 4 then? Edit: It's been a while since I did that but wouldn't that be the following in sum notation? eps_ijk a_j b_k eps_ilm c_l d_m = (new tensor)_jklm a_j b_k c_l d_m
  - mathgenius 7y ago
    Yes it really is just like lego, you can make all kinds of bizarro shapes.
kgwgk 7y ago
“Chivita“ is written Civita. Chivita would be pronounced “Kivita”. :-)
kmill 7y ago
Yeah, cross product is the determinant with "one strand bent back." If you take a 3-regular planar graph and put the determinant/Levi-Civita tensor on each vertex, you get plus-or-minus the number of edge-3-colorings of that graph. The four-color theorem is merely to show this tensor contraction is always non-zero :-) (Nobody's managed to prove it this way, yet.) Here are some notes showing how to contract two Levi-Civita symbols together graphically: https://imgur.com/HmaLSaB.png https://imgur.com/HmaLSaB.png This is in Penrose's 1971 paper ("Applications of negative-dimensional tensors"). He went on to notice that you can do a "puff-up-and-contract" construction to completely get rid of all the Levi-Civita tensors: https://imgur.com/eK9ZCkc.png https://imgur.com/eK9ZCkc.png From here, he recognized that this sort of tensor network on 3-dimensional space was equivalent to an abstract tensor network on "(-2)-dimensional space", where there is an identity that let him remove all the places the strings cross https://imgur.com/65z0zov.png https://imgur.com/65z0zov.png (This element placed at each edge in (-2)-dimensional space is known as the "second Jones-Wenzl projector for the Temperley-Lieb algebra.") From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic).
- _Microft 7y ago
  Negative-dimensional tensors... now that's wild. Thanks for the sketches, I'll have a look!
- JadeNB 7y ago
  > From a more recent point of view, what he did was find a graphical way to go from an SO(3) tensor network to an SL(2) tensor network (which should be possible since both Lie groups are isomorphic). Locally isomorphic, but not isomorphic: SL(2) is the simply connected double cover Spin(3) of SO(3). As you probably know, the non-simply-connectedness of SO(3) is what's witnessed by Dirac's belt trick (https://en.wikipedia.org/wiki/Plate_trick https://en.wikipedia.org/wiki/Plate_trick).
  - kmill 7y ago
    Thanks, that's right. (I had the Lie algebras in mind with that statement. The Lie brackets are placed at the vertices in the construction.)

stared 7y ago

The other time, during a discussion about Feynman diagrams (https://news.ycombinator.com/item?id=19909542 https://news.ycombinator.com/item?id=19909542) I mentioned some resources related to tensor diagrams (https://medium.com/@pmigdal/in-the-topic-of-diagrams-i-did-write-a-review-simple-diagrams-of-convoluted-neural-networks-6418a63f9281 https://medium.com/@pmigdal/in-the-topic-of-diagrams-i-did-w...). Happy this topic gets more mainstream, and this blog post by Tai-Danae Bradley is pure gold! Practical things: who want to co-write a library (JS I guess) for drawing such tensor diagrams? I think it has a lot of potential for representing formulae, form Markov Chains, through Quantum Computing to Deep Learning!

GorgeRonde 7y ago

In many different areas of scientific investigation, purely diagrammatic expressions have begun to be used as mathematical substitutes for the traditional symbolic expressions. These new languages reflect clear operational concepts such as ‘systems’ and ‘processes’, and ‘wires’ are used to represent information flow. Composition is built-in, as the act of connecting wires together. These diagrams are more intuitive, and easier to manipulate, than conventional symbolic models of reasoning. Examples of areas in which these techniques are being used include logic, for the study of propositions and deductions [43]; physics, for the study of space and spacetime [8, 32]; linguistics, to model the interaction of words within a sentence [21]; knowledge, to represent information and belief revision [22]; and computation, for the study of data and computer programs [1, 10]. These diagrams have been provided with a rigorous underpinning using category theory, a powerful branch of mathematics which relates these diagrammatic theories to algebraic structures. More deeply, this approach can also be applied to the study of diagrammatic theories themselves [12, 33]. As such, it is its own ‘metatheory’. One major goal of the project will be to understand to what extent this can serve as a foundation for mathematics itself, as a replacement for set theory. To work towards this, one goal will be to understand how various mathematical structures can be defined from this perspective, a rich line of enquiry for which some answers are already known, but much more is left to still be discovered. An interesting feature of categorical approaches to foundations is that standard limitative theorems, such as the incompleteness theorem of Godel, are no longer set in stone [7, 39]; instead, they become malleable, and can be directly ¨ controlled by changing the categorical universe in which one works. Switching to the field of artificial intelligence and automation — perhaps, so it seems, a world away from the abstraction of higher mathematics — the diagrammatic categories themselves have been implemented as the actual language and deduction mechanism of automated reasoning software packages. These tools make it possible to automatically explore the theories formulated in the diagrammatic language. For the case of the abstract mathematical expressions, the package quantomatic, currently in development at the Computing Laboratory at the University of Oxford, performs this function. For the particular case of diagrammatic models of language and meaning, parsers and tools for corpus exploration are currently under development. The study of each of these ‘diagrammatic theories’, each modelling a separate part of cognitive, physical, or mathematical reality, are currently separate. Our grand vision is to develop a fully integrated framework, in which all of the above can be comprehended and dealt with together. This would be a foundation for mathematics, not in isolation but in direct relation to the cognitive and physical worlds; not only as an exercise in abstract thought, but directly implemented computationally, with tools available for automatic calculation and deduction. The unique perspective given by categorical foundations on Godel-style theorems will allow their relevance to cognition to be rigorously studied. The strong mathematical similarities between the diagrammatic techniques used in these different fields, which have only recently begun to be appreciated, provides a good impetus for this research programme. Source: An integrated diagrammatic universe for knowledge, language and artificial reasoning. Abramsky & Coecke, Oxford. http://www.cs.ox.ac.uk/people/bob.coecke/JTFCats.pdf http://www.cs.ox.ac.uk/people/bob.coecke/JTFCats.pdf

layoutIfNeeded 7y ago

The computer graphics pioneer Jim Blinn has a nice lecture on tensor diagrams: https://www.youtube.com/watch?v=40TdlWURkS8 https://www.youtube.com/watch?v=40TdlWURkS8

jacobolus 7y ago
https://www.microsoft.com/en-us/research/wp-content/uploads/2002/01/UsingTensorDiagrams.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...

whatshisface 7y ago

What bothers me about this is, all indices are not the same. You could draw a line connecting a 5-dimensional index to a 3-dimensional one. There should be some way of separating incompatible indices. Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive - although some go from 1 to 3. Conventionally, this is dealt with by using Greek letters for 4-vectors and regular letters for 3-vectors.

Certhas 7y ago
You put labels on lines. For example the diagram here works like that: https://en.wikipedia.org/wiki/6-j_symbol https://en.wikipedia.org/wiki/6-j_symbol
jessriedel 7y ago
> Granted this is less of an issue for physics where virtually every index goes from 0 to 3 inclusive These days physicists who do tensor-network analysis and simulations of many-body quantum systems (e.g., MPS in 1D) probably use the diagrams more than relativists, and in those cases the indices can come with arbitrary dimensions.
tom-thistime 7y ago
Normal matrix notation has the same problem. I can write AB even if A is 5x5 and B is 3x3.

pfortuny 7y ago

I am sad to bring sad tidings but... This is very beautiful, it just puts the burden of the proof on a more abstract setting, which may be more difficult to grasp. (This is just a comment on the "graphical proofs", they are beautiful but they cannot be "proofs" unless you provide the background).

mathgenius 7y ago
It's turtles all the way down: https://graphicallinearalgebra.net/2015/06/09/matrices-diagrammatically/ https://graphicallinearalgebra.net/2015/06/09/matrices-diagr...
Certhas 7y ago
These are not "graphical proofs" in the sense of pictures that suggest patterns in mathatical relations. This is (or can be) a formal graphical language for (a branch of) mathematics. Like any formal language it's not self evident how or why it works and needs to be rigourously defined.

gdubs 7y ago

If I remember correctly, Einstein struggled with Tensors and enlisted his friend Mercel Grossmann to help him develop the Tensor Calculus he needed for the General Theory of Relativity. Einstein was no mathematical slouch, obviously, but it’s nice to know that even the most brilliant sometimes need some help from their friends.

mathgenius 7y ago
Indeed, the "einstein summation convention" is a slightly more primitive version of this graphical tensor notation.

JWKennington 7y ago

Slight nit-pick, but matrix multiplication is not exclusively a contraction, but rather a contraction on the tensor product of the two matrices. See the next paragraph for why this is concerning. I find this notation great for simple applications, but potentially unwieldy for dim > 2. For instance, how would I represent the tensor (or outer) product of two matrices? the inputs would be two circles with two lines attached to each, the result would need to be a single circle with four lines attached. The natural attempt would be something like: a - o - / / | / \ | ab ---o--- | \ / | / / b - o - But I suspect the above diagram isn't correct because there are no "open" indices at the end of this. Rather, this diagram seems to represent the contraction of a 4D tensor with 2, 2D tensors. It seems we we would need a way of connecting circles without implying a contraction of a particular index. Anyone know how to annotate the outer product of two matrices in this diagrammatic convention?

mcabbott 7y ago
A tensor product of two matrices is just this, with 4 loose ends: ---A--- ---B--- A_ab B_cd = (A⊗B)_acbd. If a,c=1...N then you can think of (ac) as being an index with N^2 possible values, which is what the double line now means... if you like, you may compact it a bit: ===(A⊗B)===
- JWKennington 7y ago
  But how am I supposed to know that AB is one mathematical object here instead of the 2 separate objects A, B? My point is that there should be a graphical way other than "put them arbitrarily close" to link them together I prefer your second notation, with the tensor product happening in parenthesis, but it kind of defeats the point of the graphical nature of the notation if we need to explictly write the tensor product I think..
  - kmill 7y ago
    Speaking as someone who uses this tensor notation quite a lot: putting multiple objects into the same diagram is what a tensor product is, and a great thing about the notation is that it reveals that a tensor product of two matrices is not an essential object in itself. If you wish, you can draw a circle around A and B to "factor out" that part of the diagram as a sub tensor product. Here might be a way to show that matrix multiplication is both "tensor product then contract" and "function composition": https://imgur.com/tcCycYj.png https://imgur.com/tcCycYj.png (though I didn't give this gray-circle notation much thought). Think about this: how is it in a product abcd of plain old numbers am I supposed to see the mathematical object ad without putting them arbitrarily close together? (Well, in standard notation, you do put them close together and write (ad)bc or something.)

outlace 7y ago

To those interested in machine learning, this idea naturally leads to “deep tensor networks” that are neural networks that can operate on and with high order tensors. I wrote a (non-rigorous) blog post about this: http://outlace.com/TensorNets1.html http://outlace.com/TensorNets1.html

imcoconut 7y ago
excellent post, thank you.

deleted 7y ago

[deleted]

mrcactu5 7y ago

here are some pages that might be relevant https://ncatlab.org/nlab/show/tensor+network https://ncatlab.org/nlab/show/tensor+network https://ncatlab.org/nlab/show/string+diagram https://ncatlab.org/nlab/show/string+diagram