Since AI interpretability is a big issue for AI safety, let’s completely interpret the results of evolutionary computation.
Disclaimer: This interpretation of the results of AI does not generalize to interpreting deep neural networks. This is a result for interpreting a solution to a very specific problem that is far less complicated than deep learning, and by interpreting, I mean that we iterate a mathematical operation hundreds of times to get an object that is simpler than our original object, so don’t get your hopes up too much.
A basis matroid is a pair (X,M) where X is a finite set, and M⊆P(X) where M denotes the power set of X that satisfies the following two properties:
If A,B∈M, then |A|=|B|.
if A,B∈M,A≠B,a∈A∖B, then there is some b∈B∖A with (A∖{a})∪{b}∈M (the basis exchange property).
I ran a computer experiment where I obtained a matroid (X,M) where |X|=9|M|=68 and where each element in M has size 4 through evolutionary computation, but the population size was kept so low that this evolutionary computation mimicked hill climbing algorithms. Now we need to interpret the matroid (X,M).
The notion of a matroid has many dualities. Our strategy is to apply one of these dualities to the matroid (X,M) so that the dual object is much smaller than the original object (X,M). One may formulate the notion of a matroid in terms of closure systems (flats),hyperplanes, closure operators, lattices, a rank function, independent sets, bases, and circuits. If these seems to complicated, many of these dualities are special cases of other dualities common with ordered sets. For example, the duality between closure systems, closure operators, and ordered sets applies to contexts unrelated to matroids such as in general and point-free topology. And the duality between the basis, circuit, and the hyperplanes may be characterized in terms of rowmotion.
If (Z,≤) is a partially ordered set, then a subset A⊆Z is said to be an antichain if whenever a,b∈A,a≤b, then a=b. In other words, an antichain is a subset A of Z where the restriction of ≤ to A is equality. We say that a aubset L of Z is downwards closed if whenever x≤y and y∈L, then x∈L as well. If A⊆Z, then let L(A) denote the smallest downwards closed subset of Z containing A. Suppose that Z is a finite poset. If A is an antichain in Z, then let A′ denote the set of all minimal elements in Z∖L(A). Then A′ is an antichain as well, and the mapping A↦A′ is a bijection from the set of all antichains in Z to itself. This means that if A is an antichain, then we may define A(n) for all integers n by setting A(0)=A,A(n+1)=(A(n))′.
If (X,M) is a basis matroid, then M is an antichain in P(X), so we may apply rowmotion, so we say that (X,M(n)) is an n-matroid. In this case, the 1
-matroids are the circuit matroids while the −1-matroids are the hyperplane matroids. Unfortunately, the n-matroids have not been characterized for |n|>1. We say that the rowmotion order of (X,M) is the least positive integer n where M(n)=M. If (X,M) is a matroid of order n, then my computer experiments indicate that gcd(|X|+2,n)>1 whichs lends support to the idea that the rowmotion of a matroid is a sensible mathematical notion that may be satisfied mathematically. The notion of rowmotion of a matroid also appears to be a sensible mathematical notion for other reasons; if we apply iteratively apply a bijective operation g (such as a reversible cellular automaton) to a finite object x, then that bijective operation will often increase the entropy in the sense that if x has low entropy, then g(n)(x) will typically have a high amount of entropy and look like noise. But this is not the case with matroids as n-matroids do not appear substantially more complicated than basis matroids. Until and if there is a mundane explanation for this behavior of the rowmotion of matroids, I must consider the notion of rowmotion of matroids to be a mathematically interesting notion even though it is currently not understood by anyone.
With the matroid (X,M) obtained from evolutionary computation, I found that (X,M) has order 1958 which factorizes as 1958=2⋅79⋅11. Set X={1,…,9}. By applying rowmotion to this matroid, I found that M(342)={{1, 8, 9},{2, 3, 6, 8},{2, 3, 7, 9},{4, 5},{4, 6, 9},{4, 7, 8},{5, 6, 9},{5, 7, 8}}. If (X,M(m)) is a basis matroid, then M(m)=M, so the set M(342) is associated with a unique basis matroid. This is the smallest way to represent (X,M) in terms of rowmotion since if |M(n)|≤8, then M(n)=M(342).
I consider this a somewhat satisfactory interpretation of the matroid (X,M) that I have obtained through evolutionary computation, but there is still work to do because nobody has researched the rowmotion operation on matroids and because it would be better to simplify a matroid without needing to go through hundreds of layers of rowmotion. And even if we were to understand matroid rowmotion better, this would not help us too much with AI safety since here this interpretability of the result of evolutionary computation does not generalize to other AI’s and it certainly does not apply to deep neural networks.
I made a video here where one may see the rowmotion of this matroid and that video is only slightly interpretable.
It turns out that evolutionary computation is not even necessary to construct matroids since Donald Knuth has produced an algorithm that can be used to construct an arbitrary matroid in his 1975 paper on random matroids. But I applied the rowmotion to the matroid in his paper and the resulting 10835-matroid B(10835)={{1, 2, 4, 5},{1, 2, 6, 10},{1, 3, 4, 6},{1, 3, 4, 7, 9},{1, 3, 6, 7, 9},{1, 4, 6, 7},{1, 4, 6, 9},{1, 4, 8, 10},{2, 3, 4, 5, 6, 7, 8, 9, 10}}. It looks like the rowmotion operation is good for simplifying matroids in general. We can uniquely recover the basis matroid from the 10835 matroid since B(m) is not a basis matroid whenever 0<m≤10835.
Since AI interpretability is a big issue for AI safety, let’s completely interpret the results of evolutionary computation.
Disclaimer: This interpretation of the results of AI does not generalize to interpreting deep neural networks. This is a result for interpreting a solution to a very specific problem that is far less complicated than deep learning, and by interpreting, I mean that we iterate a mathematical operation hundreds of times to get an object that is simpler than our original object, so don’t get your hopes up too much.
A basis matroid is a pair (X,M) where X is a finite set, and M⊆P(X) where M denotes the power set of X that satisfies the following two properties:
If A,B∈M, then |A|=|B|.
if A,B∈M,A≠B,a∈A∖B, then there is some b∈B∖A with (A∖{a})∪{b}∈M (the basis exchange property).
I ran a computer experiment where I obtained a matroid (X,M) where |X|=9 |M|=68 and where each element in M has size 4 through evolutionary computation, but the population size was kept so low that this evolutionary computation mimicked hill climbing algorithms. Now we need to interpret the matroid (X,M).
The notion of a matroid has many dualities. Our strategy is to apply one of these dualities to the matroid (X,M) so that the dual object is much smaller than the original object (X,M). One may formulate the notion of a matroid in terms of closure systems (flats),hyperplanes, closure operators, lattices, a rank function, independent sets, bases, and circuits. If these seems to complicated, many of these dualities are special cases of other dualities common with ordered sets. For example, the duality between closure systems, closure operators, and ordered sets applies to contexts unrelated to matroids such as in general and point-free topology. And the duality between the basis, circuit, and the hyperplanes may be characterized in terms of rowmotion.
If (Z,≤) is a partially ordered set, then a subset A⊆Z is said to be an antichain if whenever a,b∈A,a≤b, then a=b. In other words, an antichain is a subset A of Z where the restriction of ≤ to A is equality. We say that a aubset L of Z is downwards closed if whenever x≤y and y∈L, then x∈L as well. If A⊆Z, then let L(A) denote the smallest downwards closed subset of Z containing A. Suppose that Z is a finite poset. If A is an antichain in Z, then let A′ denote the set of all minimal elements in Z∖L(A). Then A′ is an antichain as well, and the mapping A↦A′ is a bijection from the set of all antichains in Z to itself. This means that if A is an antichain, then we may define A(n) for all integers n by setting A(0)=A,A(n+1)=(A(n))′.
If (X,M) is a basis matroid, then M is an antichain in P(X), so we may apply rowmotion, so we say that (X,M(n)) is an n-matroid. In this case, the 1
-matroids are the circuit matroids while the −1-matroids are the hyperplane matroids. Unfortunately, the n-matroids have not been characterized for |n|>1. We say that the rowmotion order of (X,M) is the least positive integer n where M(n)=M. If (X,M) is a matroid of order n, then my computer experiments indicate that gcd(|X|+2,n)>1 whichs lends support to the idea that the rowmotion of a matroid is a sensible mathematical notion that may be satisfied mathematically. The notion of rowmotion of a matroid also appears to be a sensible mathematical notion for other reasons; if we apply iteratively apply a bijective operation g (such as a reversible cellular automaton) to a finite object x, then that bijective operation will often increase the entropy in the sense that if x has low entropy, then g(n)(x) will typically have a high amount of entropy and look like noise. But this is not the case with matroids as n-matroids do not appear substantially more complicated than basis matroids. Until and if there is a mundane explanation for this behavior of the rowmotion of matroids, I must consider the notion of rowmotion of matroids to be a mathematically interesting notion even though it is currently not understood by anyone.
With the matroid (X,M) obtained from evolutionary computation, I found that (X,M) has order 1958 which factorizes as 1958=2⋅79⋅11. Set X={1,…,9}. By applying rowmotion to this matroid, I found that M(342)={{1, 8, 9},{2, 3, 6, 8},{2, 3, 7, 9},{4, 5},{4, 6, 9},{4, 7, 8},{5, 6, 9},{5, 7, 8}}. If (X,M(m)) is a basis matroid, then M(m)=M, so the set M(342) is associated with a unique basis matroid. This is the smallest way to represent (X,M) in terms of rowmotion since if |M(n)|≤8, then M(n)=M(342).
I consider this a somewhat satisfactory interpretation of the matroid (X,M) that I have obtained through evolutionary computation, but there is still work to do because nobody has researched the rowmotion operation on matroids and because it would be better to simplify a matroid without needing to go through hundreds of layers of rowmotion. And even if we were to understand matroid rowmotion better, this would not help us too much with AI safety since here this interpretability of the result of evolutionary computation does not generalize to other AI’s and it certainly does not apply to deep neural networks.
I made a video here where one may see the rowmotion of this matroid and that video is only slightly interpretable.
Deep matroid duality visualization: Rowmotion of a matroid
It turns out that evolutionary computation is not even necessary to construct matroids since Donald Knuth has produced an algorithm that can be used to construct an arbitrary matroid in his 1975 paper on random matroids. But I applied the rowmotion to the matroid in his paper and the resulting 10835-matroid B(10835)={{1, 2, 4, 5},{1, 2, 6, 10},{1, 3, 4, 6},{1, 3, 4, 7, 9},{1, 3, 6, 7, 9},{1, 4, 6, 7},{1, 4, 6, 9},{1, 4, 8, 10},{2, 3, 4, 5, 6, 7, 8, 9, 10}}. It looks like the rowmotion operation is good for simplifying matroids in general. We can uniquely recover the basis matroid from the 10835 matroid since B(m) is not a basis matroid whenever 0<m≤10835.