docs/cpta/methodology/trend_analysis.rst

   1 Trend Analysis
   2 --------------
   3
   4 All measured performance trend data is treated as time-series data that
   5 can be modelled as concatenation of groups, each group modelled
   6 using normal distribution. While sometimes the samples within a group
   7 are far from being distributed normally, currently we do not have a
   8 better tractable model.
   9
  10 Here, "sample" should be the result of single trial measurement,
  11 with group boundaries set only at test run granularity.
  12 But in order to avoid detecting causes unrelated to VPP performance,
  13 the default presentation (without /new/ in URL)
  14 takes average of all trials within the run as the sample.
  15 Effectively, this acts as a single trial with aggregate duration.
  16
  17 Performance graphs always show the run average (not all trial results).
  18
  19 The group boundaries are selected based on `Minimum Description Length`_.
  20
  21 Minimum Description Length
  22 ``````````````````````````
  23
  24 `Minimum Description Length`_ (MDL) is a particular formalization
  25 of `Occam's razor`_ principle.
  26
  27 The general formulation mandates to evaluate a large set of models,
  28 but for anomaly detection purposes, it is useful to consider
  29 a smaller set of models, so that scoring and comparing them is easier.
  30
  31 For each candidate model, the data should be compressed losslessly,
  32 which includes model definitions, encoded model parameters,
  33 and the raw data encoded based on probabilities computed by the model.
  34 The model resulting in shortest compressed message is the "the" correct model.
  35
  36 For our model set (groups of normally distributed samples),
  37 we need to encode group length (which penalizes too many groups),
  38 group average (more on that later), group stdev and then all the samples.
  39
  40 Luckily, the "all the samples" part turns out to be quite easy to compute.
  41 If sample values are considered as coordinates in (multi-dimensional)
  42 Euclidean space, fixing stdev means the point with allowed coordinates
  43 lays on a sphere. Fixing average intersects the sphere with a (hyper)-plane,
  44 and Gaussian probability density on the resulting sphere is constant.
  45 So the only contribution is the "area" of the sphere, which only depends
  46 on the number of samples and stdev.
  47
  48 A somehow ambiguous part is in choosing which encoding
  49 is used for group size, average and stdev.
  50 Different encodings cause different biases to large or small values.
  51 In our implementation we have chosen probability density
  52 corresponding to uniform distribution (from zero to maximal sample value)
  53 for stdev and average of the first group,
  54 but for averages of subsequent groups we have chosen a distribution
  55 which disourages delimiting groups with averages close together.
  56
  57 Our implementation assumes that measurement precision is 1.0 pps.
  58 Thus it is slightly wrong for trial durations other than 1.0 seconds.
  59 Also, all the calculations assume 1.0 pps is totally negligible,
  60 compared to stdev value.
  61
  62 The group selection algorithm currently has no parameters,
  63 all the aforementioned encodings and handling of precision is hardcoded.
  64 In principle, every group selection is examined, and the one encodable
  65 with least amount of bits is selected.
  66 As the bit amount for a selection is just sum of bits for every group,
  67 finding the best selection takes number of comparisons
  68 quadratically increasing with the size of data,
  69 the overall time complexity being probably cubic.
  70
  71 The resulting group distribution looks good
  72 if samples are distributed normally enough within a group.
  73 But for obviously different distributions (for example `bimodal distribution`_)
  74 the groups tend to focus on less relevant factors (such as "outlier" density).
  75
  76 Anomaly Detection
  77 `````````````````
  78
  79 Once the trend data is divided into groups, each group has its population average.
  80 The start of the following group is marked as a regression (or progression)
  81 if the new group's average is lower (higher) then the previous group's.
  82
  83 In the text below, "average at time <t>", shorthand "AVG[t]"
  84 means "the group average of the group the sample at time <t> belongs to".
  85
  86 Trend Compliance
  87 ````````````````
  88
  89 Trend compliance metrics are targeted to provide an indication of trend
  90 changes over a short-term (i.e. weekly) and a long-term (i.e.
  91 quarterly), comparing the last group average AVG[last], to the one from week
  92 ago, AVG[last - 1week] and to the maximum of trend values over last
  93 quarter except last week, max(AVG[last - 3mths]..ANV[last - 1week]),
  94 respectively. This results in following trend compliance calculations:
  95
  96 +-------------------------+---------------------------------+-----------+-------------------------------------------+
  97 | Trend Compliance Metric | Trend Change Formula            | Value     | Reference                                 |
  98 +=========================+=================================+===========+===========================================+
  99 | Short-Term Change       | (Value - Reference) / Reference | AVG[last] | AVG[last - 1week]                         |
 100 +-------------------------+---------------------------------+-----------+-------------------------------------------+
 101 | Long-Term Change        | (Value - Reference) / Reference | AVG[last] | max(AVG[last - 3mths]..AVG[last - 1week]) |
 102 +-------------------------+---------------------------------+-----------+-------------------------------------------+
 103
 104 .. _Minimum Description Length: https://en.wikipedia.org/wiki/Minimum_description_length
 105 .. _Occam's razor: https://en.wikipedia.org/wiki/Occam%27s_razor
 106 .. _bimodal distribution: https://en.wikipedia.org/wiki/Bimodal_distribution