C Extending the function network compression algorithm - OCCAM

Extending the function network compression algorithm

So, what are the next steps? We should expand our attempts with the function network. That, it seems, is the best path. One thing that we could estimate is the complexity of that line drawing world that we would like to analyse. Yes! Since, after all, we know the level of complexity that we are at now. Currently, we are at 20 bits for 2 state machines and 33 bits for 3 state machines. The next are 47 bits and 62 bits. For a line drawing of a house we need 1 bit for the background color and 5 points, which are 10 numbers in an N x N image. Lets say, N=128, so we need 7 bits for one number. Hence, we get 35 bits for the house. For more complex objects there may be some more bits necessary. Say 50-60. In any case, we are at the level where this sort of compression is well possible! It only has to be general enough! On the other hand, a single line would need 2 points, ergo 4 numbers, ergo 28 bits. It could be sufficient already now to represent lines. However, for this we have to implement exceptions, and positions, since lines are regularities in the position. But that’s about it! Then we can already proceed!

So, let’s summarize the drawbacks of the current state of the system.

1. Partition selection, interpretation rivalry.

2. Remove assumption of the concatenation of inputs.

3. Dealing with exceptions

4. Dealing with the position variable

5. Resolve primitives into arithmetic operations

6. Remove layers / execution levels

7. Interaction / regularities between inputs

8. Repeating strings

9. Function building

The most important restructuring is the introduction of the position variable and the successive execution that it requires. It could be achieved with a recursive node with two inputs one of which receives the output. How is this related to the position variable? Also, since we are removing concatenation, the system has to know somehow, where to write its outputs, which is also related to position. The positions could be generated as well. They should be, since they are just data, after all. Hence, we only need a new connection type, “entry taking”. Every output needs a position sequence to write into. But a different node may be computing it. Hence, those nodes should be paired somehow. No, not the nodes should be paired, but the final output strings. No. The position sequence could be complex itself. E.g. one may want it to write on positions 1, 4, 3, 8, 5, 12, 7, 16 which are interwoven themselves. But ultimately, a sequence has to be produced which has to be paired with the output of a node. Executing input tuples successively can be kept. We can just introduce a sequence class which contains a list of position-list / content-list pairs. The pairs are executed successively. To execute a pair, just write the content at the specified positions. This way, the representation of exceptions can be implemented, since exception pairs can be executed after the regular pairs. One such sequence feeds into one input of the child. Or a node just saves the pointers to sequences where it gets its inputs from.

And how about recursive sequences? Especially, what if two or more previous inputs are used in the computation such as in the Fibonacci sequence? Fuck it, let’s just skip that. We have found such a nice representation through the recursive node. What would be the alternative? Several previous sequence entries would have to be present as inputs. No, we don’t want to deal with that and it would also be useless for our purposes, presumably.

It looks fairly clear to us now, how to solve points 2, 3, 4 and 6. How would the primitives be resolved into arithmetic nodes? Let’s say, we have a PLUS node. It takes two inputs, adds them and gives one output. The special number is just a specialization of the PLUS node with a zero as a summand. The constant is the same as a special number, but just with n inputs fed in. We think, the constant needs to be a primitive though, since parametrizing n outputs with a single number is the seed of a 1-to-n map. Then combining a constant nodes (d, n) with a recursive plus node taking d in one input and its own output at the second input, with c being a starting value.

Thinking through the limitations of the previous model

So, resolving the incremental sequence is possible, albeit not so necessary. What about the alternating sequence? It is just a special case of repeating a subsequence. Or writing a constant every two positions. Hence, it could be a constant written on positions, whose sequence is described by an incremental sequence. This is something, that really should be dissolved. Or maybe not. We could first keep it, try to learn new functions and then dissolve it. It’s not essential anyway.

Point 8. A repeating sequence is just a generalization of the alternating sequence but with larger position increments. An entry then does not repeat every second position, but every n-th position. That’s all doable once positions are handled.

The concatenation of various outputs becomes non-trivial now and one has to compute positions. Let’s say, there are two nodes feeding into the same sequence in a concatenating way. The second one has to pay attention to where the first one ended, in order to compress optimally. As a first approximation, the first may write to positions 0-13 and the second to 13-37 and the third to 37-52, having to save 5 large numbers (13, 13, 37, 37 and 52). The position sequences will be incremental, thus being represented by (0, 1, 13), (13, 1, 37) and (37, 1, 52). Those would be listed into the same incremental node, which would create those position intervals. Therefore, we would get the input lists: [0, 13, 37], [1, 1, 1] and [13, 37, 52]. That’s where it’d be time to correlate different sequences. Hence, we conclude, if different sequences / inputs (point 7) can be solved, then the concatenation story is solved as well.

Point 7. The type of interaction that appeared here was is copy with a shift. One sequence can serve as a source. Then, we just need the specific number node. Which takes the first sequence as input and produces the second sequence as output. Its funny, that input and output are not at different levels now, but are both inputs to a single node! It’s just using the first input to compute the second one. Since we have got positions now, the SN node now also needs to know the position where to write its output. Therefore, we need both the position (0, 1, 2) and the content (0, 13, 37) of the source sequence. The positions are subjected to a subtraction of 1 while the content is copied. Negative positions are suppressed, so we get positions (0, 1) with the content (13, 37) which explains the first two numbers of the second input. The number 52 is then just invented by another SN. Yes!!! The representation capacity is strong enough to support that!

Point 9. Function building is fairly clear how to do that. We have worked on it already.

Point 1 is left. How to choose simple partitions. Partitions are nothing but the division of positions into subsets. The interval partition has been explained and represented above already. Similarly, the partition into (0, 2, 4, 6) and (1, 3, 5, 7) can be explained by two incremental sequences with parameters [[0, 1], [2, 2], [4, 4]] which can be compressed further.

Sounds good. The representation is coherent and consistent.