henrikingo commented on PR #154: URL: https://github.com/apache/otava/pull/154#issuecomment-4396930354
For reference, here's the tigerbeetle demo data set, with the hunter split-merge and weak change points. (What is the default in current Otava) <img width="2020" height="489" alt="image" src="https://github.com/user-attachments/assets/2f79d033-ea06-4c69-8ac7-706039bd6c78"; /> I will also attach a text file with diffs between the different pytest files (that are in this PR) *** Ok, so here's my analysis of 3 different variations against the tigerbeetle demo dataset: The deterministic variant finds much less change points for the same p-values. It is closer to original edivisive in behavior than to the hunter variant. To some extent this is a matter of perspective too: Who's to say we should compare them with constant p-values. Another way to look at it is that p<=0.01 for deterministic variant is closer to p<=0.001 in the hunter variation. The deterministic+skipped change points otoh is similar to the hunter variation, which of course was the intent all along. Even so, for same p-values, the hunter variation produces more change points than either of the deterministic one. Note that with p >= 0.1 they both find dozens of points, more than 10% of the total data sample, so those results are mostly noise and whether one alogrithm finds more noise than the other is perhaps not the most important aspect. Nevertheless, it is clear that Both of the new alternatives flag less change points than the hunter variant. Also worth noting that they find different change points, one is not a superset of the other. The deterministic variant produces the same result set at both extremes of p-values. For 0.00001 <= p <= 0.001 we get [15, 61, 71, 192, 260] or [15, 61, 71, 192, 212, 260]. Similarly for 0.01 <= p <= 0.05 the result set is the same but for one addition. This made me suspicious that I was observing the same phenomenon that lead to the introduction of weak change points in hunter. (Basically that the algorithm stops too early by selecting a change point candidate that has a high p-value, even if it would have found more change points with low p-values if it only continued. The skipped change points is an attempt at doing the same thing more directly inside the alogrithm, rather than doing 2 passes with two different p-values. For convenience, here's the ascii-art from the source code comments: """ This is the Tigerbeetle dataset used for demo purposes at Nyrkiö. It has a couple distinctive ups and down, anomalous drop, then an upward slope and the rest is just normal variance. ^ .' | ... ,..''.'...,......''','....'''''.......'...'.....,,,..'' |.. .. | |....'' | || |,,+-' | || | ; +-------------------------------------------------------------------------------------> 10 15 60 71 95 131 142 192 212 """ Qualitatively then, in the tigerbeetle demo data set, the benchmark I'd really like an algorithm to find is the following: * NOT flag point 10 or 11, which is an individual outlier. * Find at least points 15, 71, 95 and ideally also 60 or 61. * Beyond point 95 it is probably correct to find a couple more, but for the purposes of this benchmark, let's say the goal there is to find as few additional points as possible. * The difficult change point above is 95. It is a clear step down, but as it is immediately followed by an upward slope, it is often missed by current Otava if p-value is too small. When looking at it with the above goals: * hunter variant flags 10 much more eagerly than both of the deterministic variants. In their attempt to make e-divisive more sensitive to find two nearby change points, the datastax team also made the algorithm more sensitive to single outliers, if the deviation is large enough. It is worth emphasizing that resistance to these false positives was a huge advantage originally in the by-the-book e-divisive. * For deterministic variant, it only starts flagging 10 with p > 0.125. This is a large p-value that would almost never be used in production. * For deterministic + skipped, the behavior around 10 is more or less the same. * hunter finds the set [15, 61, 71, 95] with p=0.001. At that level it also finds 7 additional points, all > 95. * For hunter, the last point if finds out of the desired set is 15. This is odd as it is the largest change in terms of difference before and after. The explanation must be that the presence of a large outlier at 10 is "masking" the valid change point close to it. (Within the same window, in the hunter variant.) * For both of the deterministic alternatives, 95 is the last point they find out of the desired set. As explained above, this is understandable and due to the surrounding landscape. * deterministic+skipped variant finds all of the desired set at p<=0.01. At that point it also finds 82, plus 7 additional points and all at indexes > 95. So in this regard it looks very similar to the hunter variant, but as explained in previous points, they actually arrive at this finding from opposite directions. * The deterministic variant finds the desired set at p<=0.02, with 61 and 95 being the last ones it finds out of the desired set. * Interestingly however, the deterministic variant at p<=0.01 found [15, 71, 95, 131, 192]. This has the desired set, except for 61, which is the smallest change point in the set and arguably a borderline case. The fact that this variant finds both 15 and 95 before 61 (or many other points) feels very correct. Note that it only finds 2 additional points after > 95. * As a final nice touch, a p value of 0.01 seems in-line with what is commonly used as a p-value for any use case. So it is a natural default or typical value much more than 0.001. Based on the above analysis I feel like deterministic without skipping change points is actually the winner. This rewards the intuition that as the new implementation of the algorithm fixes a bug that caused Otava to miss valid change points, then now is a good time to go back to the by-the-book implementation or at least very close to it. I will add another push after this which puts on top a variant with deterministic student t significant test, but no other changes to orig_edivisive. I will however intentionally leave the patch with the skipped variant too, so that you can either browse the results it produces (by looking at the asserts in deterministic_tigerbeetle.py) or you can try it on your own data set. [comparison of tigerbeetle results.txt](https://github.com/user-attachments/files/27478338/comparison.of.tigerbeetle.results.txt) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
