tag:blogger.com,1999:blog-31953525109246115042018-07-13T04:19:16.323-04:00Sergey Babkin on CEPMy thoughts on the field of Complex Event Processing. Since I'm a technical guy, they go mostly on the technical side. And mostly about my OpenSource project Triceps. To read the Triceps documentation, please follow from the oldest posts to the newest ones.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.comBlogger367125tag:blogger.com,1999:blog-3195352510924611504.post-39070665626975366422018-07-01T15:29:00.002-04:002018-07-06T19:34:19.730-04:00graph equivalence 6: optimizations<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-5-resolving-hash.html"><<Prev</a> <br /><br />I've already mentioned some possible optimizations but let's have another look at them.<br /><br />The <b>first optimization</b> is that whenever a node gets assigned an ID, this ID can also be used as its hash H(0), or more exactly, since IDs start with 0, H(0) = ID+1, to avoid having the hash value of 0. It's not a very good hash but this sidesteps the whole problem of making sure that H(0) of each node with the assigned ID is unique. It also makes easy the checking that the hashes of the other nodes don't collide with the hashes of the nodes with the assigned IDs, just by checking that their value is greater than N.<br /><br />The <b>second optimization</b> is something I've already talked about: the simplified computation of H(D+1) that goes like this:<br /><br />1. Combine S(D) of this node and of all the directly connected nodes to produce S(D+1).<br />2. If the node has an ID assigned, assume H(D+1) = H(0) and stop. Otherwise continue with the next steps.<br />3. Include the hash H(0) at distance 0 of the node itself into H(D+1).<br />4. Iterate through the links connected to this node in the order of their tags (pre-sort them at the start of the algorithm). Within the links of the same tag, combine the previous hashes H(D) of the nodes at the other end of the links in a commutative way, such as by adding them together. Then include the tag of the link and the combined hashes of the nodes into H(D+1).<br /><br /><br />Skipping the sorting of the nodes on the links with the same tag reduces the time to O(N). Then the main algorithm can be re-shuffled a bit by moving the search for the unique nodes into the outer loop:<br /><br />1. While there are any nodes with unassigned ID: <br /> 1.1. Repeat for D=0...N+1<br /> 1.1.1. For each node, compute H(D), S(D).<br /> 1.1.2. If all S(D)==S(D-1), break out of the loop (it means that the whole topology is included).<br /> 1.2. Order nodes in the ascending order by (ID, H(D)), the unassigned IDs go after all the assigned IDs.<br /> 1.3. See if any of the nodes with unassigned ID have unique H(D). If any of them do, assign the IDs for them, continuing from the last assigned ID, and going in the order of their H(D). <br /> 1.4. If there still are any nodes with unassgined ID, take one arbitrary node with the lowest H(D) and assign the next ID in sequence to it.<br /><br />This way the computation of the loop in 1.1 would take O(N^2),. The sorting in 1.2 would take O(N*log(N)), the iteration in 1.3 will take O(N), and 1.4 is O(1). The largest one there is O(N^2). Then we multiply it by the outer loop executing N times and get O(N^3). So this optimization saved the factor of log(N) at the run time.<br /><br />The <b>third optimization</b> is kind of straightforward: when sorting the nodes by H(D), there is really no need to include the nodes with the assigned IDs into the sort, they will stay first anyway. It's not a very might optimization but saves a little.<br /><br />The <b>fourth optimization</b> is that the signatures for the graphs can be computed in parallel before comparison. So if you have a million graphs, that allows for some impressive parallelism.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-5-resolving-hash.html"><<Prev</a> Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-65631780081506391012018-06-16T12:48:00.000-04:002018-07-01T15:45:55.005-04:00graph equivalence 5: resolving the hash collisions<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-4-why-it-works.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/07/graph-equivalence-6-optimizations.html">Next>> </a><br /><br />Here is the version with the hash collision resolution: <br /><br />1. While there are any nodes with unassigned ID: <br /> 1.1. Repeat for D=0...N+1<br /> 1.1.1. For each node, compute H(D), S(D).<br /> 1.1.2. Order nodes in the ascending order by (ID, H(0)), the unassigned IDs go after all the assigned IDs.<br /> 1.1.3. If there are multiple nodes with the same H(D), compare their topology:<br /> 1.1.3.1. Pick the first node with this H(D): if there is a node with an assigned ID and this H(D), pick it, otherwise pick a random one.<br /> 1.1.3.2. Compare the second and following nodes with the first node for equality: first the assigned ID, then the tags on the nodes themselves, then the number of links, then the tags on the links and hashes H(D-1) of the nodes they lead to (using the ordering of the links from the hash computation).<br /> 1.1.3.3. If the comparison had shown a difference, rehash H(D) of that node, find if there are any of the nodes with that ID, and repeat the comparison and rehashing until this node is either unique or finds a match.<br /> 1.1.4. If all S(D)==S(D-1), break out of the loop (it means that the whole topology is included).<br /> 1.1.5. See if any of the nodes with unassigned ID have unique H(D). If any of them do, assign the IDs for them, continuing from the last assigned ID, and going in the order of their H(D). Re-compute their H(0...D) based on the newly assgined ID.<br /> 1.1.5.1. Compare the H(D) of the nodes with the newly assigned IDs with the H(D) of all the other nodes. If a collision is detected, rehash and compare again, until the collision disappears.<br /> 1.2. If there are still any nodes with unassgined ID, take one arbitrary node with the lowest H(D) and assign the next IDs in sequence to it.<br /><br />Why this works: On each iteration of the inner loop we guarantee that by the end of it the nodes with different topologies have different hashes. So at the next iteration we can use this property in the comparisons of the nodes: it's enough to compare only one link deep to find all the differences.<br /><br /><br />Let's estimate the run time: The two loops outside the main logic will still be O(N^2). Now let's look inside the loops. Since the hash collisions should be quite rare, we can compute the complexity of the collision resolution based on the case when the collisions are not detected. The worst case would be when all the nodes have the same hash, so up to (N-1) nodes will be compared with the first node. The complexity of comparing two nodes is proportional to the number of links on them, EperN. So we'd get O(N*EperN). We can assume a bit pessimistically that EperN is proportional to N, and then it will become O(N^2). The collision resolution of the nodes with the newly assigned IDs still requires comparison with all the other nodes but the comparison is cheap, only the hashes are compared. The total complexity of that would be O(N) per node, and if all nodes get assigned in one go then up to O(N^2) for all of them. But hey, it turns out that the computation of the hashes in the first place is still more expensive, taking O(N^2 * log(N)). So the totals would not change from the algorithm without the hash conflict resolution! It will still be O(N^4 * log(N)). Though of course the proportionality constant would change and the algorithm will become slower, and the optimization that skips the sorting to reduce the power of N won't be available any more.<br /><br />When collating a large number of graphs, it's possible to optimize by running the version without collection detection first, and doing the first collation based on it. What if a collision happens? A different node might be picked to be assigned the same ID, so two equivalent graphs will end up with the different signatures. However since the signature of the graph includes its full topology, two different graphs will never get the same signature. The worst that can happen is that the equivalent graphs will be split between multiple buckets. So then the second pass can be run, computing the signatures with the hash collision resolution. This second run will combine the buckets that have been improperly split by the first pass. The benefit here is that instead of computing the more complex signature for each original graph, we would be computing it only once per bucket from the first pass. And the number of buckets can easily be a few orders of magnitude lower than the number of graphs.<br /><br />If we're interested only in the top few buckets, we could even skip the whole long tail. But then we have to guard against the case of a popular graph being split into multiple buckets by the collisions. This can be resolved with 2-level bucketing. Along with the collision-agnostic signature, compute the "simple hash" of the graph by taking H(0) of all its nodes, ordering them and combining them. This simple hash will have the properties opposite to the collision agnostic signature: it would never split the equivalent graphs but it might combine the different graphs. So the simple hash is "optimistic" while the collision-agnostic signature is "pessimistic". Make the first level of bucketing optimistic and the second level of bucketing pessimistic. Then we can start by throwing away the long tail based on the optimistic bucketing. Then compute the exact signatures with collision resolution for each pessimistic class, combining them when necessary, and pick the final top elements.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-4-why-it-works.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/07/graph-equivalence-6-optimizations.html">Next>> </a><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-24644741433972422422018-06-11T04:28:00.000-04:002018-07-01T15:44:48.683-04:00graph equivalence 4: why it works<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-3-why-it-works.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-5-resolving-hash.html">Next>> </a><br /><br />The general graphs are worse, the "redundant links" in them that aren't in the tree present a major problem. Take a look at the "bowtie" graph from the part 3:<br /><br /><pre>.<br />A D<br />|\ /|<br />| C |<br />|/ \|<br />B E<br /></pre><br />If we try to follow the algorithm for the tree, start from the root C and go into the subtree rooted at A, then we would have to go to the 2nd-level subtree rooted at B, then to the 3rd-level subtree rooted at C, and get stuck in an endless recursion. This is not good.<br /><br />So my first successful attempt at solving this was:<br /><br /><ul><li>For each node, find a spanning tree with this node as root. Build the tree from the shortest paths from the root to each node (not only in terms of the number of links in the path but also in terms of the sorting of the tags on the path). </li><li>Build the root node's signature from this spanning tree.</li><li>Then append the information about the redundant links that are not included in the tree:</li><ul><li> Each redundant link can be described as the tag on it plus the paths from both of its ends to the root. For two redundant links to be equivalent, their tags must be equal and all the subtrees rooted at every node included in these paths from the end to the root have to be equivalent.</li><li>So build the lists of such subtrees for paths from both sides of the link, and order these two lists by the usual subtree comparison criteria.</li><li>Then build the signature of the redundant link from its tag and two lists of subtrees, lists ordered between themselves by the subtree order.</li><li>Then order the redundant links according to their signatures.</li><li>Then add the signatures of the redundant links in this order to the end of root node's signature.</li></ul><li>And then the nodes can be compared by these signatures as before, and the rest of the algorithm is the same.</li></ul><br />I believe this would work but in a kind of slow and painful way, even slower than the algorithm for the trees (although for all I can tell, it's still better than the factorial complexity, just the power of the polynome is kind of high).<br /><br />Then I've come up with the hash-based version that I described first, and then I've found the explanation of how it works.<br /><br />Basically, the problem with the algorithm for the tree is that it recurses in depth, and with loops present this depth goes to infinity. The alternative is to limit the depth and to build the signatures of all the nodes in parallel.<br /><br />We start with the signatures of depth 0 for each node, formed of the tag on the node and of the sorted tags of the links connected to it.<br /><br />The signatures of depth 1 are formed from the tag on the node, followed by the sorted links <i>and</i> signatures of depth 0 of the nodes from the other ends of these links.<br /><br />The signatures of depth 2 are formed from the tag on the node, followed by the sorted links <i>and</i> signatures of depth 1 of the nodes from the other ends of these links.<br /><br />And so on. We stop when all the signatures include all the nodes and all the links. But when we include all the nodes and do one more step, this guarantees that all the remaining links get included too, so this can be used as an equivalent stopping condition.<br /><br />The signatures we get from this fully represent the topology of the graph, and are dependent only on the topology. So when we order the nodes according to these signatures, we can use the rest of the algorithm from the tree unchanged, assigning the IDs to the unique nodes in this order, and then picking one node from the first equivalency class.<br /><br />Well, the hashes are the short and efficient way to represent these node signature strings, and ignoring the hash collisions, these algorithms are the same.<br /><br />I'll describe the solution for the hash collisions in the next part.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-3-why-it-works.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-5-resolving-hash.html">Next>> </a><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-30681809615982699992018-06-11T02:32:00.000-04:002018-07-01T15:43:28.349-04:00graph equivalence 3: why it works, simplified<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-part-2-comparing.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-4-why-it-works.html">Next>> </a><br /><br />To understand why the algorithm in part 1 works, let's take a step back and think, what would the topology of a node in a graph mean? If we have 2 nodes in the same graph, how can we tell that their topology is the same? And if it's not the same, how can we order them by topology? When this problem is solved, the signature generation becomes obvious: just find the topology of every node in the graph and order the nodes by topology.<br /><br />Let's start with the simpler case, if the graph s a tree.Then the problem of the topological equivalency, or more exactly, of the ordering based on the topology, of two nodes is kind of easy. Obviously, first order them by the tags of the nodes themselves. Then for each node take all their subtrees and order them: first by the tag on the link that leads to the root of the subtree, then applying the same ordering logic recursively in the subtrees (to make the comparison faster, can also compare the number of nodes in the subtrees at some early point). After all the subtrees of each node are ordered, we can compare these lists of subtrees using the same order.<br /><br />Then we can start writing the nodes into the signature based on this order. If all the nodes have a unique topology, the problem is solved: no matter in which order the nodes came in, they will be always sorted to the same order.<br /><br />If some nodes are equivalent but there is only one class of equivalent nodes with multiple members, the problem is still solved: this means that any node that links to one of them must be linked to all of them. So these nodes can be listed sequentially in any order, and the signature checking logic will order the links to them according to that order. To give an example, let's look at a small version of the cross-shaped graph:<br /><br /><pre>.<br /> E<br /> |<br />D--A--B<br /> |<br /> C<br /></pre><br />The node A is unique (or in other words, forms an equivalency class of one node), nodes (B, C, D, E) are equivalent. So we can order them in multiple ways:<br /><br /><pre>0 1 2 3 4<br />A B C D E<br />A E D B C<br />A C D E B<br /></pre>and so on<br /><br />Either way the ordered list of links for the node A will be (1, 2, 3, 4) and the ordered lists of links for nodes B, C, D E will be (0), so the signature is the same in any case.<br /><br />But if there are multiple classes with multiple elements, we can't just pick all of them in any order. Let's have another look at the full cross-shaped graph from the part 1:<br /><br /><pre>.<br /> I<br /> |<br /> H<br /> |<br />E--D--A--B--C<br /> |<br /> F<br /> |<br /> G<br /></pre><br />The node A is unique (or in other words, forms an equivalency class of one node), nodes (B, D, F, H) are equivalent, and nodes (C, E, G, I) are equivalent. If we order the nodes<br /><br /><pre>0 1 2 3 4 5 6 7 8<br />A B D F H C E G I<br /></pre><br />then the signature will be:<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 5)<br />2: (0, 6)<br />3: (0, 7)<br />4: (0, 8)<br />5: (1)<br />6: (2)<br />7: (3)<br />8: (4)<br /></pre><br />If we order the nodes differently:<br /><br /><pre>0 1 2 3 4 5 6 7 8<br />A B D F H I G E C<br /></pre><br />then the signature will be:<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 8)<br />2: (0, 7)<br />3: (0, 6)<br />4: (0, 5)<br />5: (4)<br />6: (3)<br />7: (2)<br />8: (1)<br /></pre><br />Which is a different signature, so something went wrong. The root of the problem is that as soon as we assign an index to a node, it becomes different from the nodes with the yet undefined indexes. The index sets it apart. So we can pick any node from the first class and assign an index to it, but after that we've got to re-compute the ordering of all the subtrees. The comparison function then must differentiate between the nodes with indexes assigned at the previous pass. So when comparing the (sub)trees, even before comparing the tags on the root nodes, it must compare the indexes of the root nodes. The node with the lowest index would go first, and the nodes without assigned indexes would go after all the nodes with the assigned indexes.<br /><br />So after we pick the node B for index 1 (and thus place it into its own equivalency class), our equivalency classes change: (A), (B), (C), (D, F, H), (E, G, I). C falls into its own class because it's the only node whose direct subtrees include only the one rooting at B. After we follow through all of the equivalence classes, this produces<br /><br /><pre>0 1 2 3 4 5 6 7 8<br />A B C D E F G H I<br /></pre><br />with the signature<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 2)<br />2: (1)<br />3: (0, 4)<br />4: (3)<br />5: (0, 6)<br />6: (5)<br />7: (0, 8)<br />8: (7)<br /></pre><br />If we picked the node D instead of B from the first class, the node E would become special, and the resulting indexes might be:<br /><br /><pre>0 1 2 3 4 5 6 7 8<br />A D E F G H I B C<br /></pre><br />But the signature will still be the same!<br /><br />So, to summarize:<br /><br /><ul><li>Ordering the nodes based on the comparison of their subtrees imposes a partial order of the nodes that is based only on the topology.</li><li>We can then assign the indexes to all the unique nodes, in this order. </li><li>Whenever there are equivalency classes of more than one node, an arbitrary node from the first such class can be separated by assigning the next index to it. Any of the nodes that are already unique would have links to either none or all of the nodes of this equivalence class, this is guaranteed by the equivalence, so the choice of the node from this class would not affect the links in the already-indexed nodes in any way.</li><li>If there are other multi-way equivalence classes left, repeat the computation, now taking the previously assigned indexes into account when comparing the trees. If the nodes in these equivalence classes have an asymmetrical relation to the members of the split equivalence class, these nodes will become unique (or at least members of smaller equivalence classes). If their relations are symmetrical to all the nodes of the previously broken up class, they would stay together. But any remaining equivalence classes will be broken up on the following iterations.</li><li>The resulting order of the nodes in the signature is only affected by the topological properties of the nodes, so the equivalent graphs are guaranteed to have the same signature.</li></ul><br />It also had been occurring to me repeatedly that not only the first node from the first equivalence class can be assigned an index, but all of them can be assigned indexes at the same time. And as I just as repeatedly discover, this idea would work for a tree-shaped graph but not for the general graph. The reason for this is that although all the unique (and thus previously indexed) nodes are guaranteed to have links to all or none node of this class, the nodes inside this class aren't. They might be connected to only a subset of the other nodes in the same class. To the same number of them, to be sure, but to the different subsets. So the indexes can't be assigned to them in a random order, they have to take into account the cross-links within this class. That is, for a general graph. If the graph is a tree, the absence of the loops in it means that the only way for the equivalent nodes to be connected between themselves is if there are only two of them, and then they both are either connected to each other or not.<br /><br />For an example of a graph with loops that would have this problem, consider this one (for now sidestepping the problem of how the ordering of the nodes is computed, it can be seen in such a small graph in an intuitive way):<br /><br /><pre>.<br />A D<br />|\ /|<br />| C |<br />|/ \|<br />B E<br /></pre><br />The equivalence classes after the first iteration are (C), (A, B, D, E). But if we choose the order<br /><br /><pre>0 1 2 3 4<br />C A B D E<br /></pre><br />we get the signature:<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 2)<br />2: (0, 1)<br />3: (0, 4)<br />4: (0, 3)<br /></pre><br />And with the order<br /><br /><pre>0 1 2 3 4<br />C A D B E<br /></pre><br />we get the signature:<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 3)<br />2: (0, 4)<br />3: (0, 1)<br />4: (0, 2)<br /></pre><br />Which is wrong. But if we choose to assign the index 1 to A, then on the next iteration the node B becomes distinct from D and E, with the classes (C), (A), (B), (D, E). And after splitting the (D, E), eventually the signature is guaranteed to become<br /><br /><pre>0: (1, 2, 3, 4)<br />1: (0, 2)<br />2: (0, 1)<br />3: (0, 4)<br />4: (0, 3)<br /></pre><br />no matter which of the 4 nodes we picked on the first split-off, and which of the 2 remaining nodes we picked on the second split-off.<br /><br />This part describes the algorithm and its informal proof of how to handle the tree-shaped graphs. The next installment will generalize to the arbitrary graphs.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-part-2-comparing.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-4-why-it-works.html">Next>> </a><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-14540469294061041212018-06-10T19:02:00.001-04:002018-07-01T15:42:15.897-04:00graph equivalence part 2: comparing the graph signatures<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-1-overall-algorithm.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-3-why-it-works.html">Next>> </a><br /><br />In the part 1 I've told how to build the signatures but haven't told how to compare them.<br /><br />So, a signature of the graph is essentially the list of its nodes ordered in a specific way, by the algorithm from the part 1. The basic idea of comparing the signatures is to compare the first node, if they are equal then the next node, and so on. But how do we compare the nodes?<br /><br />Obviously, first we compare the tags of the nodes. Then we've got to compare the links. But we've got to compare the links. We've got to check that the links with the same tags lead to the nodes at the same indexes in the list. The easy way to do this is to order the links by their tags in advance. And this happens to be the same order that was used during the signature building, so it can be just kept from there. But there still is the problem of what to do when the links have the same tags. In this case we've got to check that these links lead to the sets of the same nodes in both graphs. The easy way to do it is to sort these links by the indexes of the nodes they point to, which can also be done in advance.<br /><br />So after these pre-computations the comparisons can be done pretty fast, maybe even as a simple byte-string comparison. And the computed node hashes can be checked up front to make the comparison faster. And these hashes can be further combined into one value to produce a hash for the hash map.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-1-overall-algorithm.html"><<Prev</a> <a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-3-why-it-works.html">Next>> </a><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-29051631616794843432018-06-09T15:49:00.001-04:002018-07-01T15:40:02.081-04:00graph equivalence 1: the overall algorithm<a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-part-2-comparing.html">Next>></a><br /><br />I want to talk about some interesting graph processing I've done recently. As a part of a bigger problem, I needed to collate a few millions of (not that large) graphs, replacing every set of equivalent graphs with a single graph and a count. I haven't found much on the internets about the graph equivalency, all I've found is people asking about it and other people whining that it's a hard problem. Well, yeah, if you brute-force it, it's obviously a factorial-scale problem. But I believe I've found a polynomial solution for it, with not such a high power, and I want to share it. It's kind of simple in the hindsight but it took me four versions of the algorithm and a couple of months of background thinking to get there, so I'm kind of proud of it.<br /><br />But first, the kind of obvious thing that didn't take me any time to think about at all: if you're going to collate a large number of values that have a large degree of repeatability among them, you don't want to compare each one to each one. You want to do at least a logarithmic search, or even better a hash table. Which means that you need to not just compare for equality or inequality but to impose an order, and/or generate a value that can be used as a hash. If you do the factorial-complexity comparison of two graphs, you get neither, all you know is whether they are equal but you don't have any order between the unequal graphs, nor anything you can use as a hash. Instead, you need a signature: something that would serve as a "standard representation" of an equivalency class of graphs and that can be compared in a linear time (you could even represent the signatures as strings, and compare them as strings if you want). And then you can easily impose order and compute hashes on these signatures.<br /><br />The real problem then is not to compare the graphs but to find such signatures of the graphs. What should these signatures be? If we can order the nodes of a graph based purely on their place in the topology of the graph, that would work as a signature. A graph might have multiple nodes with the same topology (i.e. belonging to the same equivalence class), then any reordering of these nodes would provide the same signature. In a graph with N nodes (vertices) and L links (edges), this signature could be represented as a string of N+L elements, and thus compared in a linear time.<br /><br />The complication is that if there are multiple equivalence classes, there might be interdependencies between there classes. For example, consider an untagged graph in the shape of a cross (A...I here are not the proper tags on the nodes but some temporary random names that we assign for the sake of discussion):<br /><br /><pre>.<br /> I<br /> |<br /> H<br /> |<br />E--D--A--B--C<br /> |<br /> F<br /> |<br /> G<br /></pre><br />The nodes (B, D, F, H) are equivalent among themselves, and the nodes (C, E, G, I) are also equivalent among themselves. So we could interchange their positions within each equivalence class. But once we pick the positions for nodes of one class, the positions of the other class become fixed. Once we assign a certain position in the signature to the node B, we have to assign a certain related position to the node C. We could swap the positions of nodes B and D, but then we have to also swap the positions of nodes C and E accordingly.<br /><br /><br />First let me tell the final algorithm I came up with, and then I'll explain why it works. The algorithm uses hashes, so let's also initially pretend that there are no such things as hash collisions, and then I'll show how such collisions can be resolved.<br /><br />The algorithm works on the graphs that may have tags (or labels, whatever term you prefer) on the nodes and links. The links may be directional, and this can also be expresses as a tag on them. The nodes might have some tags on the "ports" where the links attach, such tags can also be "moved" to the links. The algorithm uses the "node-centric" view of the tags on the links, i.e. the specific tag used by it depends on which node is used as a viewpoint. For example, suppose we have nodes A and B and a directional link with tag X that goes from port 1 on A to port 2 on B:<br /><br /><pre>.<br /> X <br />A[1] -------->[2]B<br /></pre><br />When looking from the node A, such a link can be seen as having the tag "O, 1, X, 2". "O" stands for "outgoing", then the local port, tag of the link itself, the remote port. When looking from the node B, the same link will have the tag "I, 2, X, 1".<br /><br />The nodes get ordered into the signature by assigning them the sequential IDs starting from 0. The algorithm starts with no IDs assigned, and assigns them as it works.<br /><br />The algorithm computes the hashes of the graph's topology around each node, up to the distance (you can also think of it as radius) D. The distance 0 includes the tag on the node itself and the tags on the links directly connected to it. The distance 1 also includes the immediately neighboring nodes and links connected to them, and so on. For each node, we keep growing the distance by 1 and computing the new hashes. It's easy to see that when we get to the distance D=N, we're guaranteed to include the topology of the graph to all the nodes. But a general graph is not a tree, it also contains the "redundant" links, and to include the nodes on the other side of all the redundant links, one more step would be necessary, to D=N+1. The inclusion of these nodes for the second time is needed to include the full topology of these redundant links.<br /><br />However for most graphs the maximal radius will be smaller. If each node is connected to each node, the whole graph will be included at D=1. So we don't have to iterate all the way to N, instead we can keep the set of the included nodes for each hash, and we can stop growing when this set includes all the nodes in the graph.<br /><br />Let's call these hashes H, and the node sets S. <br /><br />The hash H(0) and set of nodes S(0) for the distance 0 around a node is computed as follows:<br /><br />1. Include this node itself into the set of nodes S(0).<br />2. If the node has an ID assigned, include this ID into the hash and stop. Otherwise continue with the next steps.<br />3. Include the tag of the node itself into the hash H(0).<br />4. Order the links connected to this node in some fixed way (for example, by comparing the components of their tags in the order shown in the example above: the direction, local port, tag of the link itself, remote port).<br />5. Include the tags of the links in this order into the hash H(0).<br /><br />The hash H(D+1) and set of nodes S(D+1) for the distance D+1 around a node is computed by induction as follows:<br /><br />1. Combine S(D) of this node and of all the directly connected nodes to produce S(D+1).<br />2. If the node has an ID assigned, assume H(D+1) = H(0) and stop. Otherwise continue with the next steps.<br />3. Include the hash H(0) at distance 0 of the node itself into H(D+1).<br />4. Order the links connected to this node in the same way by the tags, but with an addition of the information about the nodes at the other end of the link: if some links have equal tags, order them according to the previous hash H(D) of the nodes at the other ends of these links.<br />5. Include the tags of the links and H(D) of the nodes at the other ends of the links into H(D+1).<br /><br />The rest of the algorithm then is:<br /><br />1. While there are any nodes with unassigned ID: <br /> 1.1. Repeat for D=0...N+1<br /> 1.1.1. For each node, compute H(D), S(D).<br /> 1.1.2. Order nodes in the ascending order by (ID, H(D)), the unassigned IDs go after all the assigned IDs.<br /> 1.1.3 If all S(D)==S(D-1), break out of the loop (it means that the whole topology is included).<br /> 1.1.4. See if any of the nodes with unassigned ID have unique H(D). If any of them do, assign the IDs for them, continuing from the last assigned ID, and going in the order of their H(D). Re-compute their H(0...D) based on the newly assgined ID.<br /> 1.2. If there are still any nodes with unassgined ID, take one arbitrary node with the lowest H(D) and assign the next ID in sequence to it.<br /><br />Let's estimate the run time:<br /><br />At least one ID gets assigned on each iteration of the outer loop, so there would be at most N iterations. The inner loop would also have at most N+1 iterations. The most expensive operations in it are the computation of the next H(D) and the sorting. The computation of H(D) would go through N nodes and would do the sorting of the links connected to this node that would take O(EperN*log(EperN)) steps. The sorting of the nodes would take O(N*log(N)) steps. So to cover both these cases, let's take O(N*N*log(N)) as the worst case that would cover them both. So the total comes to O(N^4 * log(N)), which is much better than the factorial.<br /><br />The resolution of the hash collisions would add to this but on the other hand, some optimizations are possible.<br /><br />When we compute H(D+1), the links can be sorted by their tags only once, with the further sorting only among the links with the same tags. This sorting is needed to make sure that these links are treated as a set, that no matter in which order the remote nodes are originally seen, the set of remote nodes with the matching H(D) would produce the same H(D+1). But there is another, more hacky but faster way to achieve that: combine the hashes of nodes at equivalent links in a commutative way, such as by addition, before including them into H(D+1). This would remove one power of N, and the total would be O(N^3 * log(N)).<br /><br />Also, as soon as a node gets its ID, its hash becomes fixed, so there is no need to compute it any more. And we can skip computing the set S for them too. This means that the other nodes would not necessarily include the whole graph into their set S, since the propagation would stop at the nodes with the assigned IDs. But that's fine, because the inner loop would stop anyway when all the sets S stop changing. So the inner loop has to work only on the nodes that have no ID assigned yet. <br /><br />More on the hash collision resolution, and on why this works at all, in the next installment(s).<br /><br />P.S. The description of how to compare signatures is also in the next installment.<br /><br /><a href="http://babkin-cep.blogspot.com/2018/06/graph-equivalence-part-2-comparing.html">Next>></a> Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-18953290808128377312018-05-29T21:00:00.002-04:002018-05-29T21:00:13.505-04:00SQL "With" statementI've recently learned about the WITH statement in SQL that had apparently been there since the 1999 standard. It pretty much allows you to define the "temporary variables" (or "temporary views") in the SQL query for common sub-expressions, like this:<br /><br /><pre>WITH<br /> name1 AS (SELECT ...),<br /> name2 AS (SELECT ...)<br />SELECT... FROM name1, name2, whatever ...<br /></pre><br />This solves a major problem with the SQL statements, especially for self-joins on such pre-computed data, and lets you do fork-and-join in a single statement. I'm surprised that it wasn't used all over the place for the CEP systems.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-47884531928875116402018-03-19T19:15:00.002-04:002018-03-19T22:19:52.667-04:00Comments and namesI've read an opinion that if the names of the methods are self-explanatory, the comments describing these methods are not needed.<br /><br />Well, sometimes it's so, but in general I strongly disagree with this idea. The names and comments have differnt purposes. The point of the name is to give the method a designation that is difficult to confuse with the other methods. The point of the comment is to explain the meaning of a method. Mixing them doesn't do well.<br /><br />The attempts to make the names more self-explanatory back-fire in two ways: the code becomes longer, and the names become less distinct. And the worst part, it still doesn't explain enough, you can't understand such an uncommented method until you read its implementation. A good comment must explain the various considerations that went into the development of the method, its pre-conditions and post-conditions, and the exact meaning of parameters. There is simply no way to fit it into a name.<br /><br />In a way, a method name is similar to an acronym in the texts. Or, well, not necessarily an acronym but some short meaningful name. The first time you use this acronym or word, you explain what it means. When you define a method, you define what it means in the comment, and give it a short name. Then, as you use the word in the rest of the text, you use the method name in the program. And if the reader forgets what it means, he can always look up the explanation. If you used the full multi-word definition throughout your text, it would grow completely unreadable.<br /><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-28897650257006403942017-12-17T12:50:00.002-05:002017-12-17T12:50:51.272-05:00waiting for a condition: another wayI've recently encountered another way of doing synchronization without condition variables in the <a href="https://abseil.io/docs/cpp/guides/synchronization#mutexes">Abseil library</a>: their mutex has the method Await(). It provides an alternative to the construction (copied from their description):<br /><br /><pre>mu.Lock();<br />... // arbitrary code A<br />while (!f(arg)) {<br /> mu.cv.Wait(&mu);<br />}<br />... // arbitrary code B<br />mu.Unlock();<br /></pre><br />as<br /><br /><pre>mu.Lock();<br />... // arbitrary code A<br />mu.Await(Condition(f, arg));<br />... // arbitrary code B<br />mu.Unlock();<br /></pre><br />Here the condition is given in the argument of Await() as a functor, an object that keeps the related context and executes a function in this context, in the new-fangled C++14 code that's usually given as a lambda.<br /><br />This works by evaluating all the currently requested conditions on unlock, and if one of them becomes true, waking up the appropriate thread. Looks kind of wasteful on the first sight but there are good sides to it too.<br /><br />One of the typical problems with the classic condition variables is "how fine-grained should they be made"? Should there be a separate condition variable for every possible condition or can the conditions be mixed sometimes on the same variable? The Await() solves this problem: it can easily allocate a separate variable per condition, and do it right on the stack in Await(). The obvious problem with multiple conditions sharing the same condition variable is that then on a signal multiple threads would wake up, some of them will find their condition and continue, some will not find it and go back to sleep, creating the churn. Await() clearly solves this problem.<br /><br />But it can do one better too. Another problem is when the right thread wakes up but has to go back to sleep because before it woke up some other thread snuck in, got the mutex and ruined the condition. Await() can guarantee that it won't happen by simply keeping the mutex locked but passing its ownership to the waiting thread. Then when the waiting thread wakes up, it doesn't even need to check the condition again, because it's been already checked for it. This is one of those times where having your own low-level thread library pays off, you couldn't do such a trick with a Posix mutex.<br /><br />So when they say that it about evens out on performance with the classic condition variables, I think there are good reasons to believe that.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-27386240974536789192017-09-30T15:26:00.002-04:002017-10-04T17:06:35.069-04:00removing the duplication in Bayesian & AdaBoostI've been thinking some more on how to <a href="http://babkin-cep.blogspot.com/2017/09/adaboost-10-better-metric.html">remove the duplication</a> between the Bayesian events/AdaBoost partial hypotheses. Here are some notes. They're not some final results, just some thinking aloud.<br /><br />I think the problem of removing the commonality can be boiled down to the following: Suppose we have an event A that gives the prediction with some effect <i>a</i> on the training cases, and an event B that gives the prediction <i>b</i> on the training cases. These predictions have some part <i>ab</i> (that's a 2-letter identifier, not multiplication of <i>a</i> and <i>b</i>) in common. Then the effects can be written as:<br /><br />A: a = a' + ab<br />B: b = b' + ab<br /><br />Where <i>a'</i> and <i>b'</i> are the differences between the original <i>a</i> and <i>ab</i>, and <i>b</i> and <i>ab</i>. Here the operator "+" means not the addition but application of the events in the deduction one after another. So "a + b" means "apply a, then apply b". The reason why I chose the sign "+" is that this combined application should act like addition. I.e. have the commutative and distributive properties like<br /><br />x + y = y + x<br />(x + y) + z = x + (y + z)<br /><br />No, I don't have a proof why they do. But the problem with the AdaBoost hypotheses that I'm trying to solve is that the result there depends on the order of partial hypotheses (i.e. Bayesian events). I want to be able to decompose these events in such a way as to make the result independent of the order, hence the commutative requirement. The exact operation that satisfies these rules will need to be found but for now we can follow through the results of these rules.<br /><br />So, going by these rules, if we apply both events, that will be:<br /><br />a + b = a' + ab + b' + ab = a' + b' + 2*ab<br /><br />The part <i>ab</i> gets applied twice. To remove this duplication we've got rid of one copy of <i>ab</i>. We can do this by splitting the original two events into three events A', B' and AB (again, that's a 2-letter identifier, not a multiplication):<br /><br />A': a'<br />B': b'<br />AB:ab<br />a = a' + ab; b = b' +ab<br /><br />The new event AB gets the common part, while A and B lose it and become A' and B'. Then with all events applied we get the result without duplication:<br /><br />a' + b' +ab<br /><br />If we want to add the fourth event C, we've got to get its overlap with all 3 previous events. This requires a whole bunch of multi-letter identifiers:<br /><br />a'c would be the overlap between a' andc<br />b'c would be the overlap between b' and c<br />abc would be the overlap between ab and c<br /><br />And the double-primes would be the "remainders": <br /><br />a' = a'' + a'c<br />b' = b'' + b'c<br />ab = ab' +abc<br />c = c' + a'c + b'c +abc<br /><br />Then the result of applying all these events without duplication will be:<br /><br />a'' + a'c + b'' + b'c + ab' + abc + c'<br /><br />This gives the outline of the solution but it still has two problems: the number of events after splitting grows exponentially (a power of 2) with the number of the original events, and the concrete meaning of the operation "+" needs to be defined. And actually there is one more operation that needs to be defined: what does the "overlap" mean and how do we compute the value of <i>ab</i> from the values of <i>a</i> and <i>b</i>?<br /><br />The answers to both problems might be connected. One way to define the overlap would be to associate each training case with exactly one event that predicts it well. Then when we split <i>a</i> and <i>b</i> into <i>a'</i>, <i>b'</i>, and <i>ab</i>, we would be splitting the whole set of training cases into 3 parts: one part gets predicted well by both A and B, one only by A, and one only by B.<br /><br />Then the problem with the exponential growth can be answered in a two-fold way. First, the number of the events after splitting can't grow higher than the number of the training cases. Second, we can put an artificial cap on the number of events that we're willing to use (Emax), and select up to this many events, ones that predict the most training cases each. We can then either sweep the remaining training cases under the carpet, saying that they are one-offs that would cause overfitting, or split them somehow with partial strength among the events that get included.<br /><br />The last sentence also suggests the third way of tackling the growth: if we define some way to do the splitting, instead of multiplying the events we could just split the power they have on a particular training case. But I think this would create issues in case of the <a href="http://babkin-cep.blogspot.com/2017/03/bayes-25-adaboost-partial-confidence.htmlhttp://babkin-cep.blogspot.com/2017/03/bayes-25-adaboost-partial-confidence.html">partial confidence</a> during the execution of the model that can be handled better with the combined events.<br /><br />Returning to the definition of "+", I couldn't figure out yet how to make such an operation directly in AdaBoost. Maybe it can be done through logarithms, that will need some more thinking. It requires the ability to say that some training case doesn't get affected by a partial hypothesis/event. But there seems to be an easy way to do it in the Bayesian way: mark the confidence of that event for that training case as 0.5. And then these transformed events/partial hypotheses can be fed into AdaBoost too.<br /><br />This fits very well with the underlying goal of boosting: to find the approximately equal rate of the predominantly correct votes for each training case. After the transformation there will be exactly one right vote for each training case, and the rest of votes will be "undecided" (or at least sort of, subject to the limitations introduced by the mixing of training cases).<br /><br />Another consequence is that such splitting would make the produced events fully independent of each other: each event would have an exactly 50% correlation with each other event, meaning that they can be applied in any order. And this is exactly what we've been aiming for.<br /><br />So it all looks good and simple but I'm not sure yet if I've missed something important that will take the whole construction apart. There might well be.<br /><br />P.S. After a little thinking I've realized that the idea of number of events being limited by the number of training cases is pretty much equivalent to the computation directly on the training cases by weight.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-5481325842515952482017-09-30T12:53:00.002-04:002017-09-30T12:53:46.777-04:00AdaBoost conjunctions & XORI've been thinking recently about the better ways to extract the commonality from two Bayesian events (hope to find time to write about that soon), and that brought me back to the <a href="http://babkin-cep.blogspot.com/2017/01/bayesian-networks-neural-networks.html">XOR problem</a>: how to handle the situation when two events indicate a certain hypothesis when they are the same and another hypothesis when they are different.<br /><br />BTW, I took a class on machine learning recently, and it turns out that even with the neural network this problem doesn't have a great solution. The neural networks are subject to the random initial state before the training, and sometimes they do find the good combinations and sometimes they don't. This tends to get solved more reliably by the human intervention: a data scientist stares at the data, maybe does a few training attempts to see what happens, and then manually adds a new event that represents the XOR of the original events.<br /><br />So, thinking about it, I've remembered again about the concept of conjunctions that I've read in the AdaBoost book. I picked up the book and tried to find the conjunctions but couldn't: they're not anywhere in the index. Fortunately, an Internet search turned up the online copy of the book, and the conjunctions are in the <a href="https://mitpress.mit.edu/sites/default/files/titles/content/boosting_foundations_algorithms/chapter009.html">chapter 9</a>.<br /><br />The idea there is that the quality of AdaBoost partial hypotheses can be improved by forming them as conjunctions of two or more raw partial hypotheses. The idea is to take the two best choices and try a conjunction on them. If it gets better, try adding the third one.<br /><br />For a simple example, consider the data with two parameters, with values 1 collected in the upper-right quarter, and 0 in the remaining three quarters:<br /><br /><pre>.<br /> ^y<br /> 0 | 1<br /> |<br /> -------+------><br /> | x<br /> 0 | 0<br /></pre><br />The two partial hypotheses (x > 0) and (y > 0) taken together but separately will identify the upper right quarter quite decently. Each of them will have a 75% success rate. But the values in the upper-left and lower-right corner will get one vote "for" and one vote "against" from these hypotheses and will be left undecided. I actually think that the classic AdaBoost would not be able to decide well for them. It would probably crowd the field with the extra hypotheses in the upper-right corner like (x > 1), (y > 1), (x > 2), (y > 2) and so on so that the upper-left and lower-right quarters would get better but the parts of the upper-right close to the boundary would get worse. If we take the classic Bayesian approach and consider that the prior probability of encountering a 0 is 75% (assuming that all the quarters are filled at the same density), the "undecided" result would leave the probability of 0 at the same 75%, and it would be a vote for 0. So this is probably a good example of how AdaBoost could benefit from using the prior probabilities.<br /><br />The conjunctions are good at handling such situations: if these partial hypotheses are combined into one conjunction (x > 0) & (y > 0), we get a hypothesis with 100% success.<br /><br />They can be used to handle the XOR situation as well. Let's look at the situation with 1s in upper-right and lower-left corners:<br /><br /><pre>.<br /> ^y<br /> 0 | 1<br /> |<br /> -------+------><br /> | x<br /> 1 | 0<br /></pre><br />The two partial hypotheses formed by conjunctions, ((x > 0) & (y > 0)) and ((x < 0) & (y < 0)), would each give the 75% success rate. The quadrants with 0s would get correctly voted by both hypotheses but 1s would get one vote for and one vote against. But the similar hypotheses can be added for the other two quarter: !((x > 0) & (y < 0)), !((x < 0) & (y > 0)). These would add two correct votes for the quadrants with 1s, and two opposite voted canceling each other for the 0s, and taken together these 4 hypotheses can identify everything correctly.<br /><br />An interesting thing to note here is that the raw hypotheses like (x > 0) aren't the best ones at selectivity in this example. They're actually the worst ones, having the exact 50% correctness. But then again, pretty much all the hypotheses with vertical and horizontal boundaries here will have about 50% selectivity. Hunting for slightly better than 50% by selecting boundaries that fit the random density fluctuations would actually make things worse, not hitting the right center. I actually see no way to select the right boundaries by choosing the raw hypotheses independently. Only taken together in a conjunction they become optimizable.<br /><br />The other way to do it would be to use XORs instead of conjunctions. The case with two diagonal quadrants of 1s is trivial with XORs, since it can be described perfectly by one XOR, just as the case with one quadrant of 1s is trivial with conjunctions. Let's look at the one quadrant with XOR:<br /><br /><pre>.<br /> ^y<br /> 0 | 1<br /> |<br /> -------+------><br /> | x<br /> 0 | 0<br /></pre><br />If we use one XORed hypotheses, !((x > 0) XOR (y > 0)) and two simple ones (x > 0) and (y > 0), each of the three will have the 75% success rate. The upper-right corner will get all three votes for 1, and the rest of the quadrants will get two votes for the right value 0 and one against it, so the right vote would win in them too.<br /><br />The way I described it, it looks like the XORed hypothesis in this example isn't clearly better than the simple ones. But that's not how it will work with AdaBoost. After the two simple hypotheses are picked, the relative weights of the upper-left and lower-right quadrants would grow, and the XOR clearly is better at fitting them.<br /><br />Overall, it looks like XORing is better at producing the useful combined hypotheses than conjunctions: the conjunctions required 4 complex hypotheses to fit the XOR case but XOR required only 3 hypotheses to fit the conjunction case, 2 of them simple hypotheses.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-84256610292175709762017-09-25T17:52:00.002-04:002017-09-25T17:52:39.870-04:00Boosting book referenceI've accidentally found the Freund and Schapire's book on AdaBoost online:<br /><br />https://mitpress.mit.edu/sites/default/files/titles/content/boosting_foundations_algorithms/toc.html<br /><br />Great for searching.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-48612191164925422422017-09-19T04:23:00.000-04:002017-09-19T14:30:23.568-04:00Reversible computingI've read an article in the IEEE magazine about he reversible computing: <a href="https://spectrum.ieee.org/computing/hardware/the-future-of-computing-depends-on-making-it-reversible">https://spectrum.ieee.org/computing/hardware/the-future-of-computing-depends-on-making-it-reversible</a><br /><br />I've never thought about it before, that the normal switching in the circuits dissipates the energy continuously, and the way to fix it would be to make sure that the energy is always shuffled around and never dissipated (although of course there will always be the "friction losses"). I haven't found that much other information on the Internet. So I've started thinking about how such a reversible computing can be implemented, based on the example from the article. And I think I've come up with a decently simple implementation on the digital level, not sure why the article says that it's complicated. Of course, it might end up extremely complicated in the implementation, I know nothing about that. So, here is what I've come up with:<br /><br />The first obvious problem was how do the values ("billiard balls" from the mechanical analogy) get returned back? That has a kind of obvious fundamental solution: in all the digital automata the information fundamentally goes in circles like this:<br /><br /><pre>.<br /> +-----+ <br /> | |---> output <br /> | | <br /> | | +------+<br /> | | | |<br />input --->|logic|--->|memory|--+<br /> | | | | |<br /> +-->| | +------+ |<br /> | +-----+ | <br /> +------------------------+<br /></pre><br />Well, <i>mostly</i> goes in circles, there are inputs and outputs. So the next problem is how to make the inputs and outputs work. Note that the inputs don't come from nowhere, and outputs don't go into nowhere, instead they connect to the other circuits. So the inputs and outputs can be also made in the form of cycles, with the interaction between the output of one circuit and input of another circuit:<br /><br /><br /><pre>.<br />output --->-+ | +-<-- recycle<br /> | > |<br />recycle <---+ | +---> input<br /></pre><br /><br /><br />The output/input interaction can be represented as a function with the inputs:<br /><br />x - the output value<br />1 - the constant 1<br /><br />and outputs:<br /><br />rx - recycling of the output value<br />i - the input sent to the circuit<br />ri - recycling of the input value<br /><br />The truth table for this function will be:<br /><br /><pre>x 1 | rx i ri<br />==================<br />0 1 | 0 0 1<br />1 1 | 1 1 0<br /></pre><br />As you can see, the number of 1s in the output always matches the number of 1s in the inputs. If x=1, the constant 1 gets shipped to the input, otherwise it goes to the recycling and back into the constant. <br /><br />The next problem is the memory: it has to store a value that might be 0 or 1, which is obviously not symmetric. But it looks like the basic solution for that is easy: for each memory cell keep 2 sub-cells, one of them storing the value, and another one its complement. So there will always be one packet of energy stored, and the value would be determined by the sub-cell where it's stored. Then the contents of one sub-cell would be sent out for the next step of computations, and the other sub-cell will stay until the new value gets stored. I guess this could also be expressed equivalently as a constant 1 that gets connected to one or another output of the memory unit.<br /><br />How would the recycling be done? For that we've got to connect the 1s in the results back to where they came from. And ultimately they all come from the constant 1s, either introduced in the computations or use din the logic of the inputs. For all I can tell, by the time the bits get recycled, they get really mixed up, and there is no easy way to put it back. The only universal way I see to put them back would be to order all the original "constant 1s" and all the recycled values (the specific order doesn't matter, just there has to be some order) and then do the logic like this:<br /><br />If the 1st recycled value is 1, put it into the 1st "constant 1".<br />If the 2nd recycled value is 1 { <br /> If the 1st "constant 1" is still 0, put the 2nd recycled value into it,<br /> else put the 2nd recycled value into the 2nd "constant 1".<br />}<br />If the 3rd recycled value is 1 { <br /> If the 1st "constant 1" is still 0, put the 3rd recycled value into it,<br /> else if the 2nd "constant 1" is still 0, put the 3rd recycled value into it,<br /> else put the 3rd recycled value into the 3rd "constant 1".<br />}<br /><br />and so on. As you can see, the logic can be parallelized to some extent but still will require as many steps as there are input values. So for the large circuits it becomes quite slow. Maybe this can be optimized in some way for some specific applications but that would be quite difficult. Maybe that's what they mean when they say that the design of the reversible circuits is difficult.<br /><br />But I think that there is a simple solution: make each individual circuit small. Maybe limit it to 2 inputs and possibly one additional constant 1. That would limit the recycling to 3 steps, which is reasonably fast. Then use the input/output method described above to connect these small circuits into the large circuits. Then as the inputs propagate through the layers of these simple circuits, the early layers would compute their recycling in parallel with that propagation, so overall there will be very little penalty.<br /><br />Note that there would be no memory between these layers of small circuits, it would be mostly layers of the small circuits, with one memory layer at the end. <br /><br />The classic digital electronics has the implementation of functions like AND and OR with a large number of inputs, not just 2, that get computed in the same time as a function with 2 inputs, which comes quite handy. This won't be that easy for the reversible circuits. But there probably is no point in trying to do this for the reversible circuits in the first place: even if a function of N arguments would get computed in one step, then it would still have to do the recycling in N steps. On the other hand, such a function of N arguments can be built as a tree hierarchy of 2-argument functions, of the depth log2(N). This tree would be computed in log2(N) steps and the recycling of the last element will take 5 steps (the recycling of the previous elements could be done in parallel). The number 5 comes from a logical operation on 2 inputs producing 3 outputs to stay reversible, as given in an example in the article (and I suspect that it's an universal property of such operations), plus 2 inputs having 1 recycling output each. So the total time would be (log2(N)+5) which is better than N. Even if we include the I/O overhead, that would still be (2*log2(N)+5) which is still better than N.<br /><br />Thus I think that the basic design of the reversible circuits on the digital level with the "billiard ball analogs" looks not that difficult. It might be that I've missed something and got everything wrong. And of course, the implementation on the level of the underlying electronic elements like transistors might be very difficult. I'm still trying to figure out how it could be done, and since my knowledge about the transistors is fairly limited, it's difficult for me. I have some ideas but I'd need to think some more about them before writing them down (and they might be completely wrong anyway).<br /><br />A bit on a side subject, about the logic. In the article they use the the example of function [(NOT A) AND B] which looks kind of unconventional (but maybe they have some good reasons, one of them being the convenience of producing both the result and its complement). Well, there is more than one way to create a set of operations that can represent all the boolean functions. One is the set of (AND, OR, NOT), then (AND-NOT) and (OR-NOT) do everything in one operation(and perhaps the [(NOT A) AND B] does that too, I forgot how to check that), and yet another set is (XOR, constant 1). The XOR gate looks more straightforward to me, it was the first one I've thought of. And it turns out that XOR is quite popular in the reversible computing, it's known as the Toffoli gate. But in the end it probably doesn't matter much. Or maybe the best way is to use the set of (AND, OR, NOT). The reason for that being that I think OR of 2 arguments can get by with only 2 outputs, and so does NOT, only AND requiring 3 outputs. Which means one fewer recycling step after the OR, which means a slightly higher performance and about 10% (half of the saved 20%) simpler recycling circuitry compared to the situation when all the circuitry is built of one universal function like (AND-NOT) or (OR-NOT) or (XOR).Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-16640625597196955622017-09-06T13:29:00.001-04:002017-09-06T13:29:36.543-04:00AdaBoost 10: a better metric?Here is one more consequence I've noticed from the application of AdaBoost approach to the Bayesian one: it can be applied the other way around too.<br /><br />I.e. AdaBoost provides the list of partial hypotheses and weights for them. But at some point it tends to start repeating the same hypotheses over and over again, because a set of hypotheses taken together gives some gain, and applying it multiple times seemingly increases this gain. This gain is subject to the same problems as the Bayesian computations with the duplicate events: it increases the confidence only seemingly. So the same solution can be applied to it:<br /><br />After the set of partial AdaBoost hypotheses has been computed, they can be re-ordered in such a way as to remove the duplication, by selecting on every step the partial hypotheses with the <i>smallest</i> effect. This "run order" can be kept and updated on every step, instead of the AdaBoost's "selection order". So when the sequence will start repeating, a duplicate hypothesis would add nothing to the cumulative effect of the "run order", and at this point the selection algorithm should try a different hypothesis (or simply stop).<br /><br />I guess, in case if the selection algorithm doesn't stop but tries to do the next best pick (and then maybe another one if the second choice is no good either), it becomes fundamentally more complicated: on each iteration of AdaBoost it should select not simply the hypotheses that maximizes the effect of the whole sequence when appended to the end of it but one that maximizes the effect of the whole sequence when inserted at the position in the sequence where it adds the least effect. Each such insert could also cause a re-ordering of the part of the sequence that follows it.<br /><br />Which sounds even more heavy-weight than the original AdaBoost selection of the hypothesis. On the other hand, since the AdaBoost selection is already so heavy-weight, maybe this would make little extra overhead. I don't know how to analyze it yet.<br /><br /><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-13868519165132836432017-08-01T01:34:00.000-04:002017-08-01T01:34:15.516-04:00Bayes 27 & AdaBoost: another problem with partial confidenceThe solution from the previous installment can handle the partial confidence but it has its own issue. To demonstrate it, let's look at a run with the table from the part 26 but where both of the fully-correlated events E1 and E2 get a confidence of 0.7:<br /><br /><pre>$ perl <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex26_01run.pl">ex26_01run.pl</a> -n -p 1 tab24_01.txt in27_01_02.txt <br />Original training cases:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.66667^0.66667,0.40000^0.33333,<br />+ , , ,0.50000^0.50000,0.40000^0.33333,<br />hyp2 ,3.00000,0.33333^0.33333,0.33333^0.33333,0.60000^0.66667,<br />+ , , ,0.50000^0.50000,0.60000^0.66667,<br />--- Initial weights<br />hyp1 w=3.00000 p=0.50000<br />hyp2 w=3.00000 p=0.50000<br />--- Applying event E1, c=0.700000<br />hyp1 w=1.70000 p=0.56667<br />hyp2 w=1.30000 p=0.43333<br />--- Applying event E2, c=0.700000<br />hyp1 w=0.91800 p=0.60554<br />hyp2 w=0.59800 p=0.39446<br />--- Applying event E3, c=1.000000$ perl ex27_01run.pl -n -p 1 tab24_01.txt in27_01_02.txt<br />hyp1 w=0.36720 p=0.50579<br />hyp2 w=0.35880 p=0.49421<br /></pre><br />The probabilities move after applying E1, after E2 they move again. The interesting question is, should have they moved after E2? It really depends on how E1 and E2 have been measured: are their confidences derived independently or tracking back to the same measurement?<br /><br />The code assumes that they are independent, so if both are independently measured at the confidence of 0.7, together they provide a higher confidence. But if they both come from the same test, this assumption is wrong.<br /><br />If they came from the same test then E2 carries no additional information after E1 has been processed. In this case we should have treated the value C(E2)=0.7 (i.e. C(E2)=C(E1)) as having the meaning "I don't know", and then the differences from it would carry the new information.<br /><br />But this approach has its own problems. First of all, it's fine if the confidence values C(E) represent the measured probabilities. But if they represent some expert estimation then an expert saying "I don't know" and giving the confidence of 0.5 would shift the probabilities instead of leaving them unchanged. Well, it it could be re-scaled automatically but then how do we know that the expert means "I don't know" and not "I've carefully considered everything and I think that it's a 50-50 chance"? So it sounds like getting it right would require using two separate numbers: the absolute confidence that tells how sure we are of the estimation, and separately the estimation. Which would create all kinds of messes.<br /><br />The second problem, if we want to do such a re-scaling, to which value do we re-scale? It's reasonably easy if two events are copies of each other but what if the correlation is only partial? There actually is an a rather easy answer to the problem: the needed value would be P(E), the probability that the event is true at that point (after the previous events have been considered). I've actually went and modified the code to compute the P(E) based on the weights only to find out that I've forgotten an important property of the AdaBoost logic. Let me show its output:<br /><br /><pre>$ perl <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex27_01run.pl">ex27_01run.pl</a> -n -p 1 tab24_01.txt in27_01_02.txt<br />Original training cases:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,3.00000,0.66667^0.66667@0.66667,0.66667^0.66667@0.66667,0.40000^0.33333@0.50000,<br />+ , , ,0.50000^0.50000@0.50000,0.40000^0.33333@0.50000,<br />hyp2 ,3.00000,0.33333^0.33333@0.33333,0.33333^0.33333@0.33333,0.60000^0.66667@0.75000,<br />+ , , ,0.50000^0.50000@0.50000,0.60000^0.66667@0.75000,<br />--- Initial weights<br />hyp1 w=3.00000 p=0.50000<br />hyp2 w=3.00000 p=0.50000<br />--- Applying event E1, c=0.700000<br />Expected P(E)=0.500000<br />hyp1 w=1.70000 p=0.56667<br />hyp2 w=1.30000 p=0.43333<br />--- Applying event E2, c=0.700000<br />Expected P(E)=0.513333<br />hyp1 w=0.91800 p=0.60554<br />hyp2 w=0.59800 p=0.39446<br />--- Applying event E3, c=1.000000<br />Expected P(E)=0.598615<br />hyp1 w=0.36720 p=0.50579<br />hyp2 w=0.35880 p=0.49421<br /></pre><br />The computation table now has one more element printed after "@", the estimation of event's probablity for the particular branch based on the previous events. During the computation these values get mixed together based on the weight of the branches. But notice that when applying E2, the message says:<br /><br /><pre>Expected P(E)=0.513333</pre><br />It's 0.513333, not 0.7! The reason is two-fold. First, AdaBoost works by adjusting the weights of the training cases such as to bring the probability of the last seen event to 0.5. It just does the correction opposite to what I was trying to achieve. Second, these are the wrong probabilities in the table. These probabilities are computed per-branch based on the <i>absolute</i> confidence. They don't care if the actual confidence was 0.7 or 0.3, these values are the same from the standpoint of the absolute confidence. But this difference matters a lot when trying to predict P(E)!<br /><br />Instead we need to honestly compute the P(E) based on the previous events, not per the AdaBoostian table but per the original training cases. But if we do that, we end up again with a table of exponential size. The trick with ignoring all the events but the last few might still work though. The idea would be similar: since we try to order the closely-correlated events close to each other, the previous few events would be the ones with the strongest effects. And if the farther events aren't closely correlated, they won't have a big effect anyway, so they can be ignored. Maybe I'll try this next. Or maybe it's simply not worth the trouble.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-52061517803800109112017-07-10T02:43:00.000-04:002017-07-10T02:43:01.875-04:00Bayes 26 & AdaBoost: more on the partial confidenceI think I've found at least a partial solution to the <a href="http://babkin-cep.blogspot.com/2017/03/bayes-25-adaboost-partial-confidence.html">problem of partial confidence</a> that avoids going exponential.<br /><br />It grows right out of the problem definition: the problem really exists only for the closely related events. If two events are unrelated, then the confidence of one wouldn't affect the other in any noticeable way. But for the related events, the first one takes up the bulk of the effect, and then the effect of the following events becomes greatly diminished. If two events are actually the same (like E1 and E2 in tab24_01.txt in the <a href="http://babkin-cep.blogspot.com/2017/03/bayes-24-adaboost-as-solution-to.html">part 24</a>), the second event gets stripped of any effect whatsoever. But if at the execution time we find that we have no information about the first event and good information about the second event, it's too late to make use of the second event because its probabilities are already hardcoded in the table and condemn it to having no effect. But if we could change the probability at run time then we could use the second event instead. Better yet, the probabilities of the following events would be unaffected because they don't care which one of the duplicate events provided the information. For a sequence of not equal but closely correlated events, if the first one is excluded from the table preparation, the others still seem to converge in their effects to something close to the original sequence, and the following events don't get affected that much.<br /><br />Since the logic in the <a href="http://babkin-cep.blogspot.com/2017/03/bayes-24-adaboost-as-solution-to.html">part 24</a> assumes that the closely-related events would be placed in the sequence next to each other, the solution might be to compute an event's table entry in multiple versions, depending on whether the values of a limited number of the previous events are known or not. It would still be exponential for this number of previous events. But since we expect a fast convergence and hope that not too many event values will be unknown, this number of previous events can be small, and the exponent of it would be reasonably small too.<br /><br />By the way, I've come up with a name for the K(E) described in the previous part: the "absolute confidence". The confidence C(E) has the range from 0 showing that we're completely sure that the event is false, though 0.5 showing that we have no idea, to 1 showing that the event is true. The absolute confidence<br /><br />K(E) = abs(2*C(E) - 1)<br /><br />has the range from 0 showing that we have no idea to 1 showing that we're completely sure that the event is true or false.<br /><br />I had to draw a picture to figure it out how it would work. Suppose that we want to take 3 previous events into the consideration. The datapoints with the probability values for these events can then be seen as nodes of a tree, with the nodes for each event aligned vertically under the event name:<br /><br /><pre>E1 E2 E3 E4 E5<br /> +------o<br /> 0/<br /> +-----o<br /> 0/ 1\<br /> / +------o<br /> +----o<br /> / \ +------o<br /> 0/ 1\ 0/<br /> / +-----o<br /> / 1\<br /> / +------o <br />o <br /> \ 0+-------o<br /> \ +------o<<br /> \ 0/ 1+-------o<br /> 1\ +----o<br /> \ / 1\ 0+-------o<br /> \ 0/ +------o<<br /> \ / 1+-------o<br /> +--o <br /> \ 0+-------o<br /> 1\ +------o<<br /> \ 0/ 1+-------o<br /> +----o<br /> 1\ 0+-------o<br /> +------o<<br /> 1+-------o<br /></pre><br />E1 still has only one probability value because it has no preceding events. But E2 has two possible probabilities, depending on whether E1 was known (K(E1)=0) or unknown (K(E1)=1). E3 has four probabilities, depending on the possible combinations of E1 and E2. And E4 has eight probabilities.<br /><br />When we come to E5, it can't just continue branching exponentially.It should depend on only three previous events, so we drop the dependency on E1. This is done by abandoning the subtree with K(E1)=0 and continuing branching the subtree with K(E1)=1. This is a reasonable thing to do because we assume that the combination {0, 0, 0} "should never happen" (i.e no more than 3 events in a row would be unknown, otherwise use a higher value of depth), and the other mirroring pairs of branches of {0, b, c} and {1, b, c} would converge to about the same probability value. Thus the events starting from E5 would also have 8 probability values each.<br /><br />Then when we do the computation on the built table, we can have any K(E) in range [0, 1], so we do an interpolation between the branches. Suppose we're computing E4, and have 8 branches {E1, E2, E3} to interpolate. We do it by adding them up with the following weights:<br /><br />W{0, 0, 0} = (1-K(E1))*(1-K(E2))*(1-K(E3))<br />W{0, 0, 1} = (1-K(E1))*(1-K(E2))*K(E3)<br />W{0, 1, 0} = (1-K(E1))*K(E2)*(1-K(E3))<br />W{0, 1, 1} = (1-K(E1))*K(E2)*K(E3)<br />W{1, 0, 0} = K(E1)*(1-K(E2))*(1-K(E3))<br />W{1, 0, 1} = K(E1)*(1-K(E2))*K(E3)<br />W{1, 1, 0} = K(E1)*K(E2)*(1-K(E3))<br />W{1, 1, 1} = K(E1)*K(E2)*K(E3)<br /><br />Or the other way to look at it is that we start with the weight of 1 for every branch, then for E1 multiply the weight of every branch where K(E1)=0 by the actual 1-K(E1), and where K(E1)=1 by the actual K(E1). Then similarly for E2, multiply the weight of every branch where K(E2)=0 by the actual 1-K(E2), and where K(E2)=1 by the actual K(E2). And so on. The sum of all the weights will always be 1.<br /><br />The physical meaning of this interpolation is that we split the computation into multiple branches and finally add them up together. Since the computation is additive, we can put them back together right away rather than waiting for the end.<br /><br />And since I was implementing the partial confidences in the final computation, I've also implemented the support for the partial confidences in training: it's done by logically splitting the training case into two weighted sub-cases with the event values of 0 and 1.<br /><br />All this is implemented in the script <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex26_01run.pl">ex26_01run.pl</a>, as a further modification of ex24_01run.pl. Without the extra parameters it works just as ex24_01 does. The new parameter -p sets the number of previous events whose absolute confidence affect the current event. Here is an example of a run with <a href="http://babkin-cep.blogspot.com/2017/03/bayes-24-adaboost-as-solution-to.html">the same training table as before</a> and the same input:<br /><br /><pre>$ perl ex26_01run.pl -n tab24_01.txt in24_01_01.txt <br />Original training cases:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.50000^0.50000,0.40000^0.33333,<br />hyp2 ,3.00000,0.33333^0.33333,0.50000^0.50000,0.60000^0.66667,<br />--- Initial weights<br />hyp1 w=3.00000 p=0.50000in a row <br />hyp2 w=3.00000 p=0.50000<br />--- Applying event E1, c=1.000000<br />hyp1 w=2.00000 p=0.66667<br />hyp2 w=1.00000 p=0.33333<br />--- Applying event E2, c=1.000000<br />hyp1 w=1.00000 p=0.66667<br />hyp2 w=0.50000 p=0.33333<br />--- Applying event E3, c=1.000000<br />hyp1 w=0.40000 p=0.57143<br />hyp2 w=0.30000 p=0.42857<br /></pre><br />The option -n disables the normalization of the weight of the hypotheses, just as before. The output is the same as ex24_01 produced. In the training data E1 and E2 are duplicates, so the probabilities computed for E2 in the adaboostian table (P(H|E) and P(~H|~E), they are separated by "^") are at 0.5, meaning that it has no effect.<br /><br />And here is the same training data but with support for one previous unknown event, and the input data having E1 unknown (i.e. C(E1) = 0.5):<br /><br /><pre>$ perl ex26_01run.pl -n -p 1 tab24_01.txt in26_01_01.txt </pre><pre>Original training cases:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.66667^0.66667,0.40000^0.33333,<br />+ , , ,0.50000^0.50000,0.40000^0.33333,<br />hyp2 ,3.00000,0.33333^0.33333,0.33333^0.33333,0.60000^0.66667,<br />+ , , ,0.50000^0.50000,0.60000^0.66667,<br />--- Initial weights<br />hyp1 w=3.00000 p=0.50000<br />hyp2 w=3.00000 p=0.50000<br />--- Applying event E1, c=0.500000<br />hyp1 w=1.50000 p=0.50000<br />hyp2 w=1.50000 p=0.50000<br />--- Applying event E2, c=1.000000<br />hyp1 w=1.00000 p=0.66667<br />hyp2 w=0.50000 p=0.33333<br />--- Applying event E3, c=1.000000<br />hyp1 w=0.40000 p=0.57143<br />hyp2 w=0.30000 p=0.42857</pre><br />Here E2 and E3 have not one pair of probabilities in the adaboostian table but two pairs, as shown in the branching picture above. The extra branches are shown on the continuation lines that start with a "+". The branches for E2 show that if E1 is known (the second branch), E2 will have no effect as in the previous example, but if E1 is unknown (the first branch), E2's probabilities would be the same as for E1, so E2 would replace it and converge to the same values.<br /><br />As you can see in the run log, after E1 with confidence 0.5 (i.e. absolute confidence 0) is applied, both hypotheses still have the equal weight. But then after E2 gets applied, the weights and probabilities of hypotheses become the same as in the previous example, thus the knowledge of E2 compensating for the absent knowledge of E1.<br /><br />An interesting thing to notice is that the probabilities for E3 are the same in either case. This is because this table can handle only one unknown event in a row, which means that at least one of E1 or E2 should be known, and E2 is able to fully compensate for the unknown E1, so both ways converge to the same probabilities of E3.<br /><br />Now some information about how it all is implemented:<br /><br />Some of the arrays have gained an extra dimensions, to be able to keep track of the multiple branches.The weight of the training case {wt} has become an array instead of a scalar, and the probabilities {ppos} and {pneg} of the hypotheses became 2-dimensional arrays.<br /><br />The function compute_abtable() that computes the adaboostean table had gained an extra nested loop that goes through all the branches. As the final step of processing every event it prunes the branches coming from the previous event and then splits each of these branches in two. The support of the partial confidence in the training data is done by replacing the statement<br /><br /><pre>if ($c->{tc}[$i] >= 0.5) {<br /> $c->{wt} /= $abhyp{$hyp}->{ppos}[$i];<br />} else {<br /> $c->{wt} /= (1. - $abhyp{$hyp}->{pneg}[$i]);<br />} <br /></pre><br />with<br /><br /><pre>push @{$c->{wt}}, <br /> $c->{tc}[$i] * $oldwt->[$br] / $abhyp{$hyp}->{ppos}[$i][$br]<br /> + (1. - $c->{tc}[$i]) * $oldwt->[$br] / (1. - $abhyp{$hyp}->{pneg}[$i][$br]);<br /></pre><br />The function apply_abevent() that does the computation based on the table has been updated to manage the branches during this step. It had gained the extra argument of an array that keeps the history of the absolute confidence of the few previous events. This history is used to compute the weights of the branches:<br /><br /><pre>for (my $br = 0; $br <= $maxbr; $br++) {<br /> my $w = 1.; <br /> for (my $bit = 0; $bit <= $#$evhist; $bit++) {<br /> if ($br & (1 << $bit)) {<br /> $w *= $evhist->[$bit];<br /> } else {<br /> $w *= 1. - $evhist->[$bit];<br /> } <br /> } <br /> push @brwt, $w; <br />} <br /></pre><br />Then an update based on the current event is computed for each branch, and the weight of the hypothesis is updated per these weighted bracnhes:<br /><br /><pre>my $p = 0.; <br /><br /># each branch is weighed per the observed history<br />for (my $br = 0; $br <= $maxbr; $br++) {<br /> $p += $brwt[$br] * ( <br /> $conf * $hyp->{ppos}[$evi][$br]<br /> + (1. - $conf) * (1. - $hyp->{pneg}[$evi][$br])<br /> ); <br />} <br /><br />$hyp->{cwt} *= $p; <br /></pre><br />And of course the functions that print the tables and normalize the data have been updated too.<br /><br />All this stuff works on the small examples. I'm not sure yet if it would work well in the real world, I'd need a bigger example for that, and I don't have one yet. Also, I've noticed one potential issue even on the small examples but more about it in the next installment.<br /><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-68330065314416444032017-06-04T15:04:00.001-04:002017-06-04T15:04:13.199-04:00Neuron in the Bayesian terms, part 3I want to elaborate on why the second trick is so important. Basically, because in general the necessary condition of the chances changing on an event in the opposite way (by dividing or multiplying by the same number) is not true. It takes a specifically defined event to make it true.<br /><br />In general if an event is true, the chance of a hypothesis after applying this event is:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H|E) = P(H/E) / P(~H|E)</span><br /><br />The probabilities change on an event as follows:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(H|E) = P(H) * P(E|H) / P(E)</span><br /><span style="font-family: "Courier New",Courier,monospace;">P(~H|E) = P(~H) * P(E|~H) / P(E)</span><br /><br />So then the chance changes (after substituting and reducing the formula):<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H|E) = Chance(H) * P(E|H) / P(E|~H)</span><br /><br />If an event is false, the chance changes in a similar but different way:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H|~E) = P(H/~E) / P(~H|~E)</span><br /><span style="font-family: "Courier New",Courier,monospace;">= Chance(H) * P(~E|H) / P(~E|~H) </span><br /><br />Being able to do the "opposites" requires that<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H|E) / Chance(H) = 1/ ( Chance(H|~E) / Chance(H) )</span><br /><span style="font-family: "Courier New",Courier,monospace;"></span><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H|E) / Chance(H) = Chance(H) / Chance(H|~E)</span><br /><span style="font-family: "Courier New",Courier,monospace;"></span><br /><br />Which then means after doing the substitution:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|H) / P(E|~H) = P(~E|~H) / P(~E|H)</span><br /><br />Which is not always true. But if we take a page from the AdaBoost's book and define an event such that <br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|H) = P(~E|~H)</span><br />and<br /><span style="font-family: "Courier New",Courier,monospace;">P(E|~H) = P(~E|H)</span><br /><br />Then it all magically works. Again, this magic is not needed for the Bayesian computation in general, it's needed only to fit it to the formula used in the neural networks and in AdaBoost.<br /><br />There are versions of AdaBoost that use the different multipliers for when x[i] < 0 and x[i] > 0. Which means that<br /><br /><span style="font-family: "Courier New",Courier,monospace;">l[i]^x[i]</span><br /><br />gets replaced with<br /><br /><span style="font-family: "Courier New",Courier,monospace;">if (x[i] > 0) {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> lpos[i]^x[i]</span><br /><span style="font-family: "Courier New",Courier,monospace;">} else {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> lneg[i]^x[i]</span><br /><span style="font-family: "Courier New",Courier,monospace;">}</span><br /><br />AdaBoost in this situation still uses the same definition of E=(x == y) for the reasons of its internal logic, but if we don't require this logic then we can define E=(x > 0) and easily implement the chance computation for it, since the requirement of both multipliers being the opposites would disappear.<br /><br />This opens two possibilities for variations of the neurons:<br /><br />(1) One with still the definition E=(x==y) but different multipliers for x[i] of different sign.<br />(2) One with the definition E=(x > 0)<br /><br />A network with such neurons would obviously take twice the memory space for its trained multipliers (but not for the data being computed). I'm not even sure if it would be trainable at all, especially the version (2), since AdaBoost has good reasons to keep its definition of E for the convergence. But maybe it would, and considering that AdaBoost in this modification converges faster, maybe the training of the neural network would converge faster too. Might be worth a try.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-35194408285429322262017-06-04T12:54:00.000-04:002017-06-04T12:54:01.238-04:00emergentsI've attended a talk about the commercial use of the pre-trained neural networks. The idea is that you take a pre-trained network, throw away the top couple of layers, then put the blank layers on top instead and train only these new layers for your purpose.<br /><br />The presenter gave an example of taking the Google's general image classifier network and teaching it to recognize your specific images instead: "huggable" vs "non-huggable". It was smart enough to recognize that a knitted cactus is huggable while a real one is not.<br /><br />Well, it's kind of not surprising: the top layers of the classifier network are trained to recognize the various kinds of images but to do that the layer below it must produce the characteristics that allow to recognize these various kinds of images. If the original classifier has the wide knowledge (and it does), the previous layer would know what is important to recognize a very wide rage of images. They call the output of that previous layer "the emergents". And then when you use them as inputs, the new top layer would have an easy job classifying them for the new goal. You could probably even do a Bayesian classifier on top of them without much difference.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-5453276912363570492017-06-03T05:14:00.000-04:002017-06-03T05:14:50.559-04:00Neuron in the Bayesian terms, part 2I've been trying to describe in proper formulas my <a href="http://babkin-cep.blogspot.com/2017/01/bayesian-networks-neural-networks.html">insight that a neuron in neural networks is a kind of a Bayesian machine</a>(OK, this is apparently known to the people who do the neural networks professionally but it was an insight for me), and I think that I've finally succeeded. Let's start from the beginning:<br /><br />A neuron implements the function<br /><br /><span style="font-family: "Courier New",Courier,monospace;">y = nonlinear(sum(w[i] * x[i]))</span><br /><br />Here y is the output of the neuron, x[i] is the array of its inputs, w[i] is the array of some weights determined by training. Let's define the range of y and x[i] as [-1, 1] (if the values are in the other ranges, they can be trivially scaled to the range [-1, 1] by adjusting the weights w[i]).<br /><br />The nonlinear function is generally some kind of a sigmoid function that matches what we do at the end of the Bayesian computations: if the probability of a hypothesis is above some level, we accept it as true, i.e. in other words pull it up to 1, if it's below some equal or lower level we reject it, i.e. pull it down to 0, and if these levels are not the same and the probability is in the middle then we leave it as some value in the middle, probably modified in some way from the original value. Except of course that this nonlinear function deals not with the probabilities in range [0, 1] but with the values in range [-1, 1], -1 meaning "false" and 1 meaning "true".<br /><br />The Bayesian formula uses the multiplication, not addition, so the first trick here is that one can be converted into another using a logarithm. To do that let's introduce a new value l[i], of which w[i] will be the logarithm:<br /><br /><br /><span style="font-family: "Courier New",Courier,monospace;">l[i] = exp(w[i])</span><br /><span style="font-family: "Courier New",Courier,monospace;">w[i] = ln(l[i])</span><br /><br /><br />This can be substituted into the expression for the sum:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">sum (w[i] * x[i]) = sum( ln(l[i]) * x[i] )</span><br /><br />Using the rule <span style="font-family: "Courier New",Courier,monospace;">ln(a)*b = ln(a^b)</span>, the sum can be converted further:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">sum( ln(l[i]) * x[i] ) = sum( ln(l[i]^x[i]) )</span><br /><br />Then using the rule <span style="font-family: "Courier New",Courier,monospace;">ln(a) </span><complete id="goog_1225579626"><span style="font-family: "Courier New",Courier,monospace;">+ln(b) = ln(a * b)</span> the sum can be converted into a product:</complete><br /><complete id="goog_1225579626"><span id="goog_1225579627"></span><span id="goog_1225579628"></span></complete><br /><span style="font-family: "Courier New",Courier,monospace;">sum( ln(l[i]^x[i]) ) = ln( product( l[i]^x[i] ) )</span><br /><br />Now let's see how this product can be connected to the Bayesian computation. The <a href="http://babkin-cep.blogspot.com/2015/10/bayes-3-magic-formula.html">classic Bayesian formula</a> for probabilities is:<br /><br /> <span style="font-family: "Courier New",Courier,monospace;">P(H|E) = P(H) * P(E|H) / P(E)</span><br /><br /><span style="font-family: inherit;">So as each Bayesian event E[i] gets applied, we can say that the final probability will be:</span><br /><br /><span style="font-family: inherit;"><span style="font-family: "Courier New",Courier,monospace;">P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )</span></span><br /><br />Well, technically I maybe should have used another letter instead of i for the index, maybe j, but since the i in both formulas will be soon connected to each other, I'll just use it in both places from the start.<br /><br />Instead of computing with probabilities we will be computing with chances. In case if you haven't used the chances before nor seen my mentioning of them in the previous posts, a chance is a relation of the probability of the hypothesis being true to the probability of it being false. For a simple example, if we have 5 doors, with prizes behind 2 of them and no prizes behind the remaining 3, then the chance of getting a prize by opening a random door is 2 to 3, or 2/3 (but the probability is 2/5). In a formula this gets expressed as:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = P(H) / P(~H) = P(H) / (1 - P(H))</span><br /><br />So if we have two mutually exclusive hypotheses H and ~H, the probabilities for them will be:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )</span><br /><span style="font-family: "Courier New",Courier,monospace;">P(~H) = P0(~H) * product( P(E[i]|~H) / P(E[i]) )</span><br /><span style="font-family: inherit;"><br /></span><br /><span style="font-family: inherit;">And the chances will be:</span><br /><span style="font-family: inherit;"><br /></span><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = P(H) / P(~H) </span><br /><span style="font-family: "Courier New",Courier,monospace;">= ( P0(H) * product( P(E[i]|H) / P(E[i]) ) ) / ( P0(~H) * product( P(E[i]|~H) / P(E[i]) ) )</span><br /><span style="font-family: "Courier New",Courier,monospace;">= (P0(H)/P0(~H)) * product( P(E[i]|H) / </span><span style="font-family: inherit;"><span style="font-family: "Courier New",Courier,monospace;">P(E[i]|~H) )</span> </span><br /><span style="font-family: inherit;"><br /></span><br /><span style="font-family: inherit;">If the initial probabilities of both hypotheses are equal, P0(H) = P0(~H) = 0.5, then their relation will be 1 and can be thrown out of the formula:</span><br /><span style="font-family: inherit;"> </span><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = product( P(E[i]|H) / P(E[i]|~H) )</span><br /><br /><span style="font-family: inherit;">Well, almost. The consideration above glanced over the question of what do we do if the event is false? The answer is that in this case the factor in the product should use the probabilities of ~E instead of E: </span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = product( </span><br /><span style="font-family: "Courier New",Courier,monospace;"> if (E is true) {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> P(E[i]|H) / P(E[i]|~H)</span><br /><span style="font-family: "Courier New",Courier,monospace;"> } else {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> P(~E[i]|H) / P(~E[i]|~H)</span><br /><span style="font-family: "Courier New",Courier,monospace;"> } </span><br /><span style="font-family: "Courier New",Courier,monospace;">)</span><br /><br />Now comes the turn of the second major trick: what kind of events to use for the Bayesian formula. We'll use the same kind of events as for AdaBoost, the event being "x[i] accurately predicts y", so if H is "y > 0" and thus ~H is "y < 0", the conditional probability will be:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E[i]|H) = P(y == x[i])</span><br /><span style="font-family: "Courier New",Courier,monospace;">P(~E[i]|~H) = P(y == x[i])</span> <br /><br />An interesting property of this definition is that the conditional probabilities of these events get computed across the whole range of the training data, without differentiation between x[i] < 0 and x[i] > 0. This means that<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|H) = P(~E|~H)</span><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|~H) = P(~E|H)</span><br /><br />We then use the general property that<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|H) = 1 - P(~E|H)</span><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|H~) = 1 - P(~E|~H)</span><br /><br />and get<br /><br /><span style="font-family: "Courier New",Courier,monospace;">P(E|~H) = P(~E|H) = 1 - P(E|H)</span><br /><br />So after substituting all these equivalencies the computation of the chances becomes nicely symmetrical: <br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = product( </span><br /><span style="font-family: "Courier New",Courier,monospace;"> if (E is true) {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> P(E[i]|H) / (1 - P(E[i]|H))</span><br /><span style="font-family: "Courier New",Courier,monospace;"> } else {</span><br /><span style="font-family: "Courier New",Courier,monospace;"> (1 - P(E[i]|H)) / P(E[i]|H)</span><br /><span style="font-family: "Courier New",Courier,monospace;"> } </span><br /><span style="font-family: "Courier New",Courier,monospace;">)</span><br /><br />When x[i] is in range [-1, 1], and especially if x[i] is in the set {-1, 1}, the if/else can be replaced by the power of x[i]: when x[i]==1, it will leave the expression as-is, when x==-1, the expression will be "turned over":<br /><br /><span style="font-family: "Courier New",Courier,monospace;">Chance(H) = product( ( P(E[i]|H) / (1 - P(E[i]|H)) )^x[i] )</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">We can now interpret the original formula in terms of the chances. That formula was:</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: "Courier New",Courier,monospace;">y = nonlinear(sum(w[i] * x[i]))</span><br /><span style="font-family: "Courier New",Courier,monospace;">= </span><span style="font-family: "Courier New",Courier,monospace;">nonlinear( </span><span style="font-family: "Courier New",Courier,monospace;">ln( product( l[i]^x[i] ) ) )</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">Here we can substitute the product:</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;"><span style="font-family: "Courier New",Courier,monospace;">y = nonlinear( ln( Chance(y > 0) ) )</span></span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: inherit;">A logarithm is a very convenient thing to apply on the chance to obtain a symmetric range of values (-infinity, +infinity) centered at 0 instead of [0, +infinity) "centered" at 1. And if the weights are properly selected, the actual range of y will be not </span><span style="font-family: inherit;">(-infinity, +infinity) but [-1, 1].</span><br /><br /><span style="font-family: inherit;">This substitution of the product will mean:</span><br /><span style="font-family: inherit;"><br /></span><span style="font-family: "Courier New",Courier,monospace;">l[i] = P(E[i]|H) / (1 - P(E[i]|H))</span><br /><span style="font-family: "Courier New",Courier,monospace;">w[i] = ln( P(E[i]|H) / (1 - P(E[i]|H)) )</span><br /><span style="font-family: inherit;"><span style="font-family: inherit;"><br /></span></span><span style="font-family: inherit;"><span style="font-family: inherit;">So the original weights in the neuron have the "physical meaning" of the logarithms of the chance multipliers.</span></span><br /><span style="font-family: inherit;"></span>Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-72102313079948741002017-03-08T15:54:00.003-05:002017-03-08T15:54:59.979-05:00OS support for thread stoppingI've recently had done some thinking about how can an OS make the shutdown of a multithreaded application or its part easier, to stop the threads quickly but relatively nicely on request. I think a very helpful support can be pretty easy to implement:<br /><br /><ul><li>Have system call to request the shutdown of an OS-level thread.</li><li>This call would make any system calls that could block non-blocking (except for the thread synchronization calls, like mutex or condition variable operations), would interrupt any current such blocking calls, and return an error. This includes the timed sleeps, and even the thread synchronization calls with timeouts would return an error immediately instead of sleeping. Optionally, it might also just fail any file operations altogether, possibly except for close(). Note that the file descriptors as such wouldn't be revoked altogether, they would just kind of stop working in one thread, but the other threads would still work.</li><li>A problem with this might be in such things as logging: when your thread is stopping, it might still write the useful log files. Revoking these log files would be Well, one solution for this would be to buffer the logs in memory and write from a separate thread. Another might be to keep some kind of exception list.</li><li>The threads might also beget threads, and keeping track of all of them is complicated. So there is a need for grouping them, like the process groups in the OS, or Triceps Triead fragments, and then stopping the whole group.</li></ul>Yet another separate approach might be to say "but if you want the ability to stop something, why don't you run it as a separate process and kill if when needed?". This would make a lot of sense for such things as PAM authentication modules.<br /><br />There are problems with the separate processes too. But after some thinking, they seem to be fairly easy to solve.<br /><br />When you think about processes, usually a separate binary comes to mind but it doesn't have to. You can just do a fork() and run from the same binary, and you even get the whole address space copy-on-write out of the box. Though I guess it might be interesting to NOT copy-on-write the whole address space. Instead just allocate some communication area for passing the arguments and results, and get rd of the rest, maybe even re-running the run-time loader from scratch in the new context (that would be kind of like the Java class loader spaces).<br /><br />Communication with a separate process is kind of painful. But if you map an anonymous memory segment, that segment can be inherited by the child process. Indeed, should be inherited to act as the communication region (truly shared, not COW) even if the rest of address space is dropped. And then you can happily create the mutexes and condition variables in it for synchronization. The arguments and results would have to be serialized to pass through this region but it shouldn't be such a big deal. It would be also possible to keep some large data dictionaries in this communication space.<br /><br />Of course the callbacks wouldn't work across the process boundary. But there is a solution for this too: create a local thread pool (or simply a thread) for callbacks that would get the requests from the remote process though a portion of the same communications region, execute the callback, and return the results back there.<br /><br />I think this looks feasible even without any new technology needed, just needs a helper library to implement the interface. This isn't even a new concept, it's a classic microkernel architecture without the common memory space. Yeah, copying the data in the serialized form adds an overhead but it's not that much overhead compared to say JVM, and people use Java and .NET all over the place with no regrets.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-24482752653729421082017-03-05T21:41:00.000-05:002017-03-05T21:41:27.421-05:00Bayes 25 & AdaBoost: the partial confidence problemThe code in the previous example works only with the full-confidence events, those that have the confidence of 0 or 1. Unfortunately I haven't found a good way to handle the partial confidence yet. I've found <i>a</i> way but it has problems. Let me show you.<br /><br /><a href="http://babkin-cep.blogspot.com/2015/10/bayes-4-fuzzy-logic.html">Previously</a> I was treating the partial confidence as a superposition of 0 and 1. This approach cannot be properly used here because it doesn't cover the connections between the events. To give an example, in the <a href="http://babkin-cep.blogspot.com/2017/03/bayes-24-adaboost-as-solution-to.html">previous post</a> the code had correctly found that in tab24_01.txt the events E1and E2 are the same, so after E1 is applied, E2 becomes ignored (it's AdaBoost probabilities become 0.5). So now if we then do a computation and find that E1 is unknown (i.e. its confidence is 0.5) but E2 is known, E2 will still be ignored because its table entry says to always ignore it.<br /><br />The correct way should handle this situation properly: if E1 is unknown, this should bring up the table values for E2 to compensate for it and treat E2 as E1 was formerly.<br /><br />The obvious way to do it is to treat the partial confidence as a superposition of "the event is unknown" and "the event is known". So if the event is known, we process it as before. If the event is unknown, we would follow the unknown branch and then apply all the following events as if this events wasn't there. And if the event is partially known, we would split the weights of all the outcomes proportionally and handle one part with the known branch and another one with the unknown branch.<br /><br />So the confidence of 0.7 would mean a superposition of 0.4 of unknown and 0.6 of the known value "1". The confidence 0.1 would mean a superposition of 0.8 of unknown and 0.2 of the known value "0". So if we denote C(E) as the event confidence, K(E) as the known weight in the superposition, and U(E) as the unknown weight in the superposition, we can write them as:<br /><br />K(E) = abs(C(E) - 0.5) * 2<br />U(E) = 1 - K(E)<br /><br />The downside of this obvious approach is that the table and computation becomes more complex. As we go through more events, two branches become four, then eight, then sixteen, and so on. The formerly quadratic complexity O(Noutcomes * Nevents) becomes exponential O(Noutcomes*Nevents*2^Nevents). I don't know yet if there is a better way.<br /><br />Maybe it would be possible to build a table of "gradients" between the events: i.e. if the confidence of the event A changes, how are the probabilities of another event B affected. The problem though is that this gradient depends on all the events in the sequence between A and B, so tis idea doesn't seem to really fly.<br /><br />Maybe another idea is workable, that would reduce the exponential cost to a cubic one: after splitting the superposition, instead of following two branches, just take the probabilities for each following event from both branches and mix them by the weight of the branches:<br /><br />P(H|Ei) = K(Ej) * P(H|KjEi) + U(Ej) * P(H|UjEi)<br /><br />It's better than exponential but still not great, with the run time O(Noutcomes*Nevents*Nevents). And the table of these pre-computed values would still seem to be exponential, each event depending on all the possible combinations of the previous events. Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-88190786169127206932017-03-01T02:37:00.000-05:002017-03-01T02:37:32.916-05:00Bayes 24: AdaBoost as a solution to the correlated eventsWhen writing the <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/whitepapers/AdaboostBayes.pdf?format=raw">whitepaper</a>, I've realized that AdaBoost is very good at finding the cross-correlation of its partial hypotheses (that map to the Bayesian events), and it always picks the next step with the minimal cross-correlation. The Bayesian computations do have an issue with cross-correlation, as described in the whitepaper and near the end of <a href="http://babkin-cep.blogspot.com/2015/10/bayes-8-impossible.html">Part 8 of my notes</a>: if there are multiple events that duplicate or mirror each other, all of them are treated as independent and drive the probabilities off. This looked like AdaBoost could give a hint of how to solve this problem, so I've started thinking about it, and I think I've found a solution.<br /><br />In retrospect the solution is pretty obvious: instead of computing the Bayesian model directly, treat it as an AdaBoost model whose set of the partial hypotheses equals to the set of the Bayesian events, with an extra limitation that each one of them must be used exactly once. If there are multiple equivalent events and they happen to go one after another, AdaBoost will treat the first one as real, and the following ones will get their error rate of 0.5 and will be effectively no-ops.<br /><br />Well, if there are other events interspersed in between these equivalent copies, they won't be no-ops. These other events will shift the weights of the training cases, so that the second an further copies will find themselves drifted away from 0.5. The good news here is that AdaBoost is pretty good at removing the partial correlation too but the bad news is that the order matters, to fully remove the duplication the equivalent events should go one after another. And in general, it looks like the best removal of the cross-correlation happens when the closely related events follow closely one after another. This kind of order can be implemented if we reverse the AdaBoost preference of the partial hypotheses and make it always pick the one that has its training error rate closest to 0.5. Since (unlike the classic AdaBoost) the set of partial hypotheses is limited and each element from it must be used only once, the better ones will eventually be used as well.<br /><br />To experiment with these ideas, I wrote the code example <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex24_01run.pl">ex24_01run.pl</a>. It doesn't reorder the events, just computes the AdaBoost values for whatever order it's given, allowing to experiment with the various orders. But it has a couple of advanced features from the later chapters of the book on AdaBoost: it does the multi-class (but single-label) version that also partitions the error rate computation for the sign of the value of the partial hypothesis.<br /><br />The multi-class means that it can work not only with two outcomes (a yes/no decision) but with multiple possible outcomes (i.e. Bayesian hypotheses), just like the normal Bayesian table. And just like the normal Bayesian table, these outcomes must be mutually exclusive, so each case may have only one outcome (single-label). The multi-class logic works in the way that is similar to the one described in <a href="http://babkin-cep.blogspot.com/2015/10/bayes-10-independence-and-relevance.html">Part 10</a>: the resulting table is just a combination of the individual per-outcome tables. From the standpoint of each outcome, the single-label property means that the rest of the rows of the table taken together represent the opposite of this outcome, so there is no need to compute that opposite explicitly.<br /><br />The partitioning of the error rate computation not only makes the result better but also comes very handy to prove that the opposite of one outcome is equivalent to the rest of the rows of the table. The AdaBoost training error <i>e</i> is the ratio of the total weights of the training cases where the value of the event E (that is, the Bayesian event, in AdaBoost terms it's a partial hypothesis) is not equal to the value of the outcome (Bayesian hypothesis) H. And we'll compute it separately for E (i.e. E=1) and ~E (i.e. E=0). It ends up expressable as probabilities that can be computed by summing and dividing weights W of the training cases:<br /><br />e(H,E) = P(~H|E) = (sum for cases i where H(i)=0 and E=1 (Wi))/(sum for cases j where E=1 (Wj))<br />e(H,~E) = P(H|~E) = (sum for cases i where H(i)=1 and E=0 (Wi))/(sum for cases j where E=0 (Wj))<br /><br />So if we pick a particular outcome and denote it H1, we can show that its opposite ~H1 is equivalent to the sum of the rest of hypotheses H2...HN by showing that<br /><br />P(~H1|E) = sum for i in [2, N] (P(Hi|E))<br /><br />which after removing the common denominator means <br /><br />(sum for cases j where H1(E)=0 and E=1 (Wj)) = (sum for i in [2, N] (sum for cases k where Hi(E)=1 and E=1 (Wk))<br /><br />The single-label property means that each case is marked with exactly one outcome, and all the cases where the outcome H1 is absent must have some other outcome Hi present, so these sums are indeed equal.<br /><br />So it is all self-consistent. The key part of the computation is:<br /><br /><pre>for my $hyp (values %abhyp) {<br /> if ($conf) {<br /> $hyp->{wt} *= $hyp->{ppos}[$evi];<br /> } else {<br /> $hyp->{wt} *= (1. - $hyp->{pneg}[$evi]);<br /> }<br /> }<br /></pre><br />And the matching part of the table building is:<br /><br /><pre>foreach my $c (@case) {<br /> my $hyp = $c->{hyp}[0];<br /> # this code really handles only the TC values of 0 and 1,<br /> # for the arbitrary values it would have to do an interpolation<br /> if ($c->{tc}[$i] >= 0.5) {<br /> $c->{wt} /= $abhyp{$hyp}->{ppos}[$i];<br /> } else {<br /> $c->{wt} /= (1. - $abhyp{$hyp}->{pneg}[$i]);<br /> } <br /> } <br /></pre><br />The training undoes the weight change that will be done in the computation.<br /><br />Now let's try some examples. Here is the example that I used in the whitepaper:<br /><br /><pre>$ perl <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex24_01run.pl">ex24_01run.pl</a> -n <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/tab24_01.txt">tab24_01.txt</a> <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/in24_01_01.txt">in24_01_01.txt</a><br />Original training cases:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E2 ,E3 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.50000^0.50000,0.40000^0.33333,<br />hyp2 ,3.00000,0.33333^0.33333,0.50000^0.50000,0.60000^0.66667,<br />--- Applying event E1, c=1.000000<br />hyp1 w=2.00000 p=0.66667<br />hyp2 w=1.00000 p=0.33333<br />--- Applying event E2, c=1.000000<br />hyp1 w=1.00000 p=0.66667<br />hyp2 w=0.50000 p=0.33333<br />--- Applying event E3, c=1.000000<br />hyp1 w=0.40000 p=0.57143<br />hyp2 w=0.30000 p=0.42857<br /></pre><br />Here the option "-n" means "don't normalize the weights" (or when normalized to the sum of 1 they will be the same as probabilities). The two values printed in the AdaBoostian table separated by a "^" are the P(H|E) and P(~H|~E).<br /><br />As you can see, the result is not correct either (because of the XOR problem) but it's better than with the plain Bayes version that gave hyp1 the probability 0.667. And since E1 and E2 are the same, E2 ended up with the values of 0.5 in the table, and applying it didn't change the weight.<br /><br />If we change the order of events, E2 gains some use back:<br /><br /><pre>$ perl <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex24_01run.pl">ex24_01run.pl</a> -n <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/tab24_02.txt">tab24_02.txt</a> <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/in24_01_01.txt">in24_01_01.txt</a> <br />Original training cases:<br />! , ,E1 ,E3 ,E2 ,<br />hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E1 ,E3 ,E2 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.40000^0.33333,0.47368^0.48276,<br />hyp2 ,3.00000,0.33333^0.33333,0.60000^0.66667,0.52632^0.51724,<br />--- Applying event E1, c=1.000000<br />hyp1 w=2.00000 p=0.66667<br />hyp2 w=1.00000 p=0.33333<br />--- Applying event E3, c=1.000000<br />hyp1 w=0.80000 p=0.57143<br />hyp2 w=0.60000 p=0.42857<br />--- Applying event E2, c=1.000000<br />hyp1 w=0.37895 p=0.54545<br />hyp2 w=0.31579 p=0.45455<br /></pre><br />Rather surprisingly, the result ended up more correct. Or maybe it's not that surprising: after all, AdaBoost is designed to gain more information from available data.<br /><br />Yet another interesting result get produced from repeating the same pair of events multiple times:<br /><br /><pre>$ perl <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/ex24_01run.pl">ex24_01run.pl</a> -n <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/tab24_03.txt">tab24_03.txt</a> <a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/in24_03_01.txt">in24_03_01.txt</a> <br />Original training cases:<br />! , ,E01 ,E02 ,E11 ,E12 ,E21 ,E22 ,E31 ,E32 ,E41 ,E42 ,E51 ,E52 ,E61 ,E62 ,E71 ,E72 ,E81 ,E82 ,E91 ,E92 ,<br />hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,<br />hyp1 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,<br />hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,<br />AdaBoostian table:<br />! , ,E01 ,E02 ,E11 ,E12 ,E21 ,E22 ,E31 ,E32 ,E41 ,E42 ,E51 ,E52 ,E61 ,E62 ,E71 ,E72 ,E81 ,E82 ,E91 ,E92 ,<br />hyp1 ,3.00000,0.66667^0.66667,0.40000^0.33333,0.47368^0.48276,0.49694^0.49526,0.49916^0.49946,0.49990^0.49985,0.49997^0.49998,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,<br />hyp2 ,3.00000,0.33333^0.33333,0.60000^0.66667,0.52632^0.51724,0.50306^0.50474,0.50084^0.50054,0.50010^0.50015,0.50003^0.50002,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,<br />--- Applying event E01, c=1.000000<br />hyp1 w=2.00000 p=0.66667<br />hyp2 w=1.00000 p=0.33333<br />--- Applying event E02, c=1.000000<br />hyp1 w=0.80000 p=0.57143<br />hyp2 w=0.60000 p=0.42857<br />--- Applying event E11, c=1.000000<br />hyp1 w=0.37895 p=0.54545<br />hyp2 w=0.31579 p=0.45455<br />--- Applying event E12, c=1.000000<br />hyp1 w=0.18831 p=0.54242<br />hyp2 w=0.15886 p=0.45758<br />--- Applying event E21, c=1.000000<br />hyp1 w=0.09400 p=0.54159<br />hyp2 w=0.07956 p=0.45841<br />--- Applying event E22, c=1.000000<br />hyp1 w=0.04699 p=0.54149<br />hyp2 w=0.03979 p=0.45851<br />--- Applying event E31, c=1.000000<br />hyp1 w=0.02349 p=0.54147<br />hyp2 w=0.01990 p=0.45853<br />--- Applying event E32, c=1.000000<br />hyp1 w=0.01175 p=0.54146<br />hyp2 w=0.00995 p=0.45854<br />...<br /><br />--- Applying event E92, c=1.000000<br />hyp1 w=0.00000 p=0.54146<br />hyp2 w=0.00000 p=0.45854<br /></pre><br />AdaBoost converges pretty quickly to the weights that make both events get the probability 0.5 and stop the further changes.<br /><br />This seems to work, although it needs more testing. One more limitation of this implementation is that it works only with the events that have the value of either 0 or 1, not anything in between. I'll talk more about this in the next post.Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-11383816463495882842017-02-22T09:51:00.001-05:002017-02-22T09:51:22.265-05:00a better explanation of Bayes-AdaBoost connectionAfter some re-reading, my previous posts on the Bayesian interpretation of AdaBoost have been kind of cryptic. It's no wonder because I've been writing them as I was understanding things, so they came out as more of a personal reminder rather than the general explanation. But I've got around and wrote another version as a whitepaper, that goes all the way from scratch and hopefully is much more understandable:<br /><br /><a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/whitepapers/AdaboostBayes.pdf?format=raw">https://sourceforge.net/p/exbayes/code/HEAD/tree/whitepapers/AdaboostBayes.pdf?format=raw</a><br /><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-36199880819210511012017-02-20T13:21:00.003-05:002017-02-21T01:37:50.507-05:00Bayesian examples now on SourceForgeI've been working on one more post on the Bayes-AdaBoost cross-over, and I've finally got tired of pasting the substantial examples right in the post. So I've created a SourceForge project for them and uploaded all the examples there:<br /><br /><a href="https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/">https://sourceforge.net/p/exbayes/code/HEAD/tree/v1/</a><br /><br />The proper SVN checkout recipe from there is:<br /><br />svn checkout svn://svn.code.sf.net/p/exbayes/code/ exbayesSergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com0tag:blogger.com,1999:blog-3195352510924611504.post-59640407711855512572017-02-04T20:08:00.001-05:002017-02-28T13:45:27.569-05:00The mythical 10x programmer, or the silver bullet explainedRecently I've been talking about some of the experiences from Aleri times when my interlocutor responded "so I guess you're one of those 10x programmers". This made me pause. Like any programmer per Larry Wall's recipe, I have a good amount of hubris but can I really say that I'm a 10x programmer? After some thinking, I guess sometimes I am and sometimes I'm not. This got me thinking further, about what was different between the situations when I was and when I wasn't. And I think the difference is very much about the organization and methodology, and thus can probably be applied to any programmers to improve their productivity. I've tried to distill the knowledge, and here it goes. By the way, Fred Brooks also called the goal of 10x productivity increase the "silver bullet", so here is maybe your silver bullet. Maybe. I'm not entirely sure that the recipe will work out of the box, it will probably need at least some debugging. Or maybe it won't work but it's still worth a try.<br /><br />Let me start with describing a couple of cases when I could fairly be said to have been a 10x programmer. There were some other good cases too but on a couple of occasions I've actually had a benchmark.<br /><br />One case was at Aleri, working on the CEP system. Here is the real short version of the events: At the time there were 3 main players in the CEP world: StreamBase, Aleri and Coral8, all having an approximate parity in their products. Around 2009 Coral8 apparently ran out of money, so Aleri used it this opportunity to consume it. And then it had two approximately equal products and set about merging them. The merging didn't go that great and Aleri ran out of money too, eventually consumed in 2010 by Sybase. See, even though the Coral8 product was about the same from the functional standpoint, it had the code base about 10x the size, and had maybe not quite 10x but a lot more people working on it. Since the Coral8 code base was so much larger and there were many more people familiar with it, it was taken as the foundation of the merged product. And this merging then crashed and burned. Another merging attempt was then done under Sybase, this time doing it the other way around, and it worked much better. So it's an interesting example where the 10x was there, then it wasn't, and then it was again.<br /><br />Another case was the UnitedLinux. The full history of UnitedLinux is an interesting story of dog-eat-dog in the world of the Linux vendors but I won't go into the full funny details, just touch up on the important parts. One of conditions of the UnitedLinux consortium set by SuSE was that SuSE does all the general development. Everyone else does just their branding customizations and additional packages. So Caldera where I worked at the time (soon to be renamed SCO, with the SCO Linux brand of UnitedLinux) had closed the Linux development office in Germany, with most of the people heading to SuSE. When UnitedLinux was released, the various consortium members (I remember Connectiva, and whoever else) held their release parties and posted pictures with great many people. We didn't have any party at SCO: see, the SCO Linux was done by only two developers and half a tester (and a bit of a graphical artist), and Ron was in California while I was in New Jersey, so having a party would have been difficult. And we've had it ready earlier: the final image was sent to testing about 20 minutes after downloading the drop from SuSE. I think I still have the commemorative t-shirt somewhere, one thing Caldera was big on was the t-shirts.<br /><br />So what was special in these cases? In a very short summary, I'd say that it was the compact code done with the familiar technologies, incrementally, with low interdependencies, and with high level of script automation. Oh, and you need to have the good engineers as well. But just the good engineers aren't enough: I wouldn't say that the engineers at Coral8 were any worse than at Aleri, just they've got mired in the slow methodologies.<br /><br />Let's look at the details.<br /><br />The compact code pretty much means the straightforward and to-the-point code. There is a classic book "The practice of programming" (and I liked it so much that I've patterned the name of my book after it) that shows the code like this: when you have a problem, solve it in the most straightforward way. There are lots of published systems of various code decorations, and all of them are wrong. The decorations don't make the code better, they make it worse, more difficult to read and modify. The extra layers of abstractions don't help anything either, they make the code more difficult to both understand and modify (not to mention writing it in the first place). There is an article about "worse is better" written by Richard Gabriel from the MIT AI labs when he discovered that the simpler Unix code worked better than his "better" over-abstracted code. But this phrase is misleading, better is better, it's just that the over-abstractions are worse, not better. This absolutely doesn't mean that the code should be flat abstraction-wise. The code that is too flat is also an unmaintainable spaghetti mess. The abstraction layers are needed. But they have to be introduced for a good reason, not on a whim and not by the bureaucratic rules. The good functions are usually pretty large. The good classes are usually pretty large. The good rule of thumb for making a chunk of code into a new abstraction is to notice when you do the same thing over and over again. Then it's time to put this code into one place and call it from the other places. A good abstraction reduces the size of code, does not increase it.<br /><br />The problem with the overly-abstracted code is really the same as with the under-abstracted flat code: there are only so many things you can keep in your head at a time. In the code that is too flat you need to keep too many interdependencies of that flat level in your head. In the code that is too abstracted you need to keep too many abstractions and their APIs and calling patterns in your head. The optimal spot is in the middle.<br /><br />A lot of things are easier to just do than to use a library. If you do the logging from a shell script, a 10-line shell function will not only work much better than a shell version of log4j but will also be a lot easier to call (not to mention avoiding an extra dependency). Or an iteration over a container with a plain for-loop is not only easier to write and understand but also much easier to remember than the STL templates for that.<br /><br />An important thing is to keep the documentation close to the code. This means both the good comments in the code and the user documentation.<br /><br />The basic rule behind the good comments is very simple: the comments must be one (or sometimes more) step more abstract than the code. A comment should be explaining either why something is done (or not done), especially if the reasoning is not obvious, or telling what is done as a short summary in the higher-level terms. As long as this rule is followed, the more comments is pretty much the better (but there is only so much you can write without breaking this rule).<br /><br />Keeping the user documentation together with the code, in the same versioning system and in the same tree hierarchy is very important. This way the documentation can be updated in parallel with the code and will never become obsolete. And at the end of the release cycle all the changes can be found and re-edited. This principle implies that the documentation must be kept in a text-based format that is easy to diff, just as the code is, and that the tools used on it must not change that exact text format at random. Which generally means that the editing should be done with a normal text editor, and the WYSIWYG tools should go into the garbage bucket. The pain inflicted by them is much greater than the gain. The ease of versioning and diffing is much more important than the ease of visual formatting. While on the subject of documentation, the technical writers need to either really be technical or be kept in check. The precise meaning of documentation is important, and I've seen too often an edit to make a sentence smoother also making it ambiguous or entirely meaningless. And "smoother" is not always "better" either. I've bought a book of Richard Feynman's letters, more for the collection purposes since the letters are usually fairly boring but unexpectedly it also turned out to be a great reading. Except for the part where it included the magazine articles about his Nobel prize. The style of these articles was completely different from Feynman's, it was the usual unreadable journalist drivel. Don't turn your documentation into the journalist drivel.<br /><br />To give another example of where I think smooth is bad, the sentence above "An important thing is to keep the documentation close to the code" is better in that place than "Keeping the documentation close to the code is important". The complex sentence slows you down and gives you a breather before the text switches to a new subject, emphasizing that switch. Also, it brings the word "important" closer to the start of the sentence where it's more noticeable.<br /><br />Next principle, the familiar technologies, affects the speed of development a lot. It's kind of obvious but the counter-point is "if we use that latest and greatest new tool, we'll be done much faster". And sometimes the latest and greatest tool really does that. But most of the time the familiarity is much more important. If you have an idea of how the goal can be straightforwardly achieved with the familiar tools, that's usually the best bet by a wide margin. If not, learn the new tool. Sometimes this would also give you an idea of how the goal can be achieved easier with your old tools. And a lot of technologies are just crap anyway. So the overall priority should be not "the goal for the tool" but "the tool for the goal".<br /><br />This doesn't mean that the new tools shouldn't be learned or that everyone has to be familiar with every tool to be used. Usually one person having the familiarity with a tool is enough to frame the code around it, giving everyone else a big head start in learning it. It's much easier to add code to an existing unfamiliar framework than to build a new framework with an unfamiliar tool. And there are the times to use the familiar tools and times to learn the new ones. There is the cadence of development when the things start amorphous and slow, and then as the solutions for various items start falling together the project starts crystallizing and picking up the pace until it rolls at full steam to the goal. Then the next cycle starts. The slow part of the cycle is a good time to learn the new tools. But things tend to go a lot faster when only one thing is new: a new tool for an old purpose or an old tool for a new purpose. Of course sometimes a bullet has to be bitten and a new tool learned together with the new purpose but that goes slower.<br /><br /><br />On to the incrementality. It's nothing new, Eric Raymond wrote about it in "The Cathedral and the Bazaar". But it still gets lost surprisingly often, even in the "agile methodologies". Instead of "we'll make this great new thing to replace that dingy old thing" the right approach is "we'll transform this dingy old thing into this great new thing". The programs are not physical objects, they're more like blueprints for the physical objects. It's not like you have to raze a bridge to build a new bridge in its place. Instead a program's <i>run</i> is more like a physical object. Every time you restart a program an old bridge gets razed and a new one gets built for you according to the new plan. Or I guess another good example from the world of the physical things is the automobile manufacturing: the car models might stay but their internal mechanics is updated pretty regularly. At some point the cars would look the same but the new cars from that point on would get say a better alternator. The Chevy small block V8 engine has been around for more than 50 years. The only item that stayed for all this time is the dimensions of the cylinders. Everything else has been replaced. But it hasn't been replaced in one go, it has been a product of a long evolution with many gradual small changes.<br /><br />Every time you hear about an order of magnitude budget and time overruns, it's when someone tried to re-do a program from scratch. Fred Brooks talks about this in his "Mythical man-month", so the effect has been known since at least 1970s, and yet it keeps being repeated. And guess what, that's not limited to software either. Have you ever heard of Tucker? It was a new automobile company in 1940s that decided to design its car completely from scratch, with all the newest and greatest technology. They've never got the cars working, they kept falling apart until the company ran out of money, and its founder got sued by the government for all the dubious financial activities he'd done to delay the running out of money. Here someone might ask "but what about the iPhone, what about Tesla?" They are actually the examples of the evolutionary development. iPhone was built around the clever idea of a big-screen phone used as an application platform but it wasn't developed all at once, and Apple didn't try to reinvent the cell communications chipsets at the same time. Some of the evolutionary moments of iPhone are widely known: such as, they started with a stylus as was then typical, and then Steve Jobs said "screw this, use the fingers instead". And the last-moment decision of replacing the plastic screens with glass had been a subject of many moralizing articles. Tesla is best seen in the contrast to GM's EV1. GM tried to develop the whole technology chain from scratch, spent a huge amount of time and money, and failed. While Tesla piggybacked on the already existing technologies and packaged them together into a car (that they also took off the Lotus's shelf). Even then Tesla's path wasn't easy, they've had their tuckeresque moments with the failing transmissions (which they eventually simply got rid of) and with the battery cooling for a few years before they were able to release their first car.<br /><br />One of the worst statements I've heard about why a system needed to be rewritten from scratch went like this: "it has accumulated all these little features that make making changes without breaking them difficult, so we have to re-write everything to get rid of them and make the changes simple again". It completely misses the point: it's these little features that make the product worthwhile. Doing the 80% of the functionality is easy but nobody needs only 80% of the functionality (and in reality that particular project overran by years). The code is a living document that preserves the knowledge of the subject area. Discarding the code means discarding this knowledge which then has to be re-learned. This doesn't mean that the best solution isn't sometimes to throw away the old code and re-write it from scratch. But it's usually done by replacing the code in small chunks and checking that the functionality is preserved after the move of every chunk. To give an analogy from biology, the human (and animal) organs develop by growing the new cells within a scaffolding of the other neighboring cells that shapes them and makes them properly differentiate for the function. The old code provides such a scaffolding for the new chunks.<br /><br />I want to illustrate this last point with a couple of examples. I'll leave the company and all the details in the first example unnamed, since the example is kind of embarassing. This company decided to make an appliance with its software. It had all the software bits and pieces that it has been selling to the customers, so the only thing that needed to be done was put it all together, like the customers do. Simple, right? Turns out, no, the bits and pieces would not work together, and no customer had actually put them all together because they didn't work. Each piece worked in a way, so each responsible team was happy, but not together. And getting them to work together took a large amount of time and work. Another similar example comes from Microsoft where I've seen a very similar issue with the <a href="https://blogs.msdn.microsoft.com/sergey_babkins_blog/2016/02/26/powershell-windows-clusters/">PowerShell support in the Windows clusters</a>: there are many components involved and each one has its own PowerShell commandlets for management but they don't mesh well together with each other, need to be combined in the very non-obvious ways with no big goal-oriented commandlets, and some things turn out to be not really doable at all.<br /><br />The obvious objection is "but how do we test all these changes"? This is where the automated testing comes in, and it's such a big subject that I wrote a <a href="http://babkin-cep.blogspot.com/2016/12/on-testing.html">whole separate post about that</a>. But it's really a bogus question. When you write a completely new system,you still test each chunk of code as you write it, and if you don't have the automated testing then you just test it manually. The difference is that in an incomplete system your chunk will have only the limited interactions, so you would be able to test only some of its effects. In a complete system you get a much more complete coverage. And if the old system doesn't have any automated tests then it's a good way to start them: for each chunk write the tests before replacing it, and then use them to check that the the replaced chunk still works in the same way. Another important point, a chunk doesn't have to be all in one place, it might be distributed, such as an one-line change in a thousand files.<br /><br />The small changes don't have to go together with the frequent releases. But every time you do a release one way or another, you get the issue "we have to complete all the changes before the release!" and it gets worse if you want to do the more frequent releases. Well, you definitely do want to make sure that the things don't get accidentally broken at the last moment, so the commits have to slow down just before the release. But it doesn't mean that you can't include the changes at all. Any change is fine to include as long as it doesn't break the existing functionality. The new functionality doesn't have to work, as long as it doesn't get called in the production environment nobody cares about that, it only has to not break the old functionality. This way you can integrate the changes a lot earlier, and then spend a lot less effort merging them together.<br /><br />In the <a href="http://babkin-cep.blogspot.com/2016/12/on-testing.html">post on testing</a> I've already said that an important part of the incrementality is the incremental tests, being ability to run easily the immediate subset of tests affected by a change. But a prerequisite for it is the incrementality of the build: the ability to build quickly all the components dependent on the change, all the way to the final package, while skipping the build of the unchanged parts of the tree. "Quickly" here means right away, not in some kind of a nightly build. This does wonders for the turnaround time. Obviously, in some cases, like a fundamental library, pretty much all of the tree will depend on it. But then the incrementality should be interpreted as the ability to build a few of the representative projects based on it to test that they didn't break. If the full nightly test shows that some dependent components got broken, the ability to rebuild them quickly also makes wonders for the turnaround of the investigation.<br /><br />Another thing about the build is that I think the purely rules-based builds are bad. It's not that having the common rules is bad, they're actually quite convenient. But the build system must also allow to do the quick one-offs. These one-offs are very important for the automation of the build. They allow to write quickly say a small Perl script that would do some kind of transformation or code generation. A build system without such one-offs turns the hour-long tasks into the week-long ones. So just please do support the full proper make and the scripting environment, not some crap like Cmake. The counter-argument is of course "but we need to build on multiple platforms including Windows". Yeah, building on Windows sucks, and the only decent solution I see it to bring a decent environment of the portable tools to each of your build platforms.<br /><br />Another very simple but important thing about the build is that it must detect the errors. The Java-based tools in particular are notorious for ignoring the status codes, so when something breaks, the only way you know it is by the result files being absent. Or not even by them being absent but them failing in the tests. This is bad. All the errors have to be detected as early as possible.<br /><br />This looks like a good place for another related rant, on reliability. Basically, when something works it should work reliably. Einstein said "The definition of insanity is doing the same thing over and over again and expecting different results." But in reality we don't control everything, and when these hidden changes cause a different result of the same actions, it's just maddening and time-consuming. The good code, including the tests and build, should work reliably. If the underlying systems are known to have outages, it should retry and still work reliably on top of them and not propagate this unreliability up. Every step the unreliability propagates makes it more difficult to fix, so it's best nipped in the bud. There of course are the reasonable limits too, the calls should not get stuck retrying forever, and probably not ever for an hour. Although retrying for an hour might be fine for a scheduled nightly run, but for a manual run it's way too long. And when a program is retrying it should not be silent, it should be telling what its is doing.<br /><br />Next item is the low interdependencies. Basically, it means that the people should be able to work without stepping too much on each other. You might ask: but doesn't the principle of the small code base go against it? More code should allow more people to work on its part, right? No, it doesn't work like this. The catch is that if you have more code solving the same problem, any changes to it mean that you have to change about the same <i>percentage</i> of the code. This is why a sprawling code base is slow in development, because any change requires changing a lot of code. But this is also why it doesn't allow more people to work on it in parallel. So the corollary is that if you add too many people to a project, they will start stepping on each other a lot and the productivity will drop.<br /><br />The other major kind of interaction is between the people in general. If you need to do a 5-minute task, it takes you 5 minutes. But if you need someone else to do a 5-minute task, it's likely to take you a day of interaction. Which still might be faster than learning how to do it yourself but if the task is repetitive then this becomes a major drag. To work fast, this drag has to be reduced and eliminated whenever possible. One of the consequences is that the posessive code ownership is bad. Now, having someone knowledgeable available to talk about a part of code is good, and it also helps to discuss the general directions of the code to avoid breaking things for other people. But there should not be a single-person or single-team bottleneck for changes to a certain part of code, nor any single person controlling what is allowed to go in. There are other reasons to avoid these things too but even the speed of development should be a sufficient reason. Another corollary is that the strict code style requirements are bad. The small style variations just don't matter, and the enforcement is a lot of pain with no gain whatsoever.<br /><br />Another case where the excessive interaction shows is planning. Have you seen these beautiful Gantt charts and critical path diagrams, with the carefully planned moments of interdependencies? Well, they're all garbage. They might be an interesting exercise on the way to the better understanding of the project but things never work out like this in reality. In reality all the interdependency points end up as a mess. So there is no point in overplanning. Instead I really like the saying of my past manager: "We can plan an aggressive schedule because we don't mind it slipping once in a while". When combined with the idea of the incrementality, this points to the following concept: the detail level of the plans must be tied to their distance. A detailed planning of the far-off items doesn't make sense because they are sure to change before we get there. These items should be on the list, so that we can keep track of the direction, but only in the general terms. Only the very near-term items need to be planned in detail, and the farther in the future the less detail is needed. Though the very near-term items have their Heisenbergian uncertainty as well. In my experience the minimal unit of time for planning is a week. If you have five items that you expect to take one day each, they will never work out like this. Some of them will take an hour and some will take three days. But if you lump all five together, they will take together a week with a decent amount of certainty.<br /><br />Since I've already talked about the scripted automation throughout the text, this is a wrap for this post. The things I've described look kind of small but they really are important, and I believe that taken together the do amount to the 10x difference in productivity. What do you think?<br /><br />P.S. Someone else's thoughts on the subject of 10x: <a href="http://antirez.com/news/112">http://antirez.com/news/112</a><br /><br /><br />Sergey Babkinhttp://www.blogger.com/profile/06686909700446011233noreply@blogger.com3