docs/cpta/methodology/trend_analysis.rst

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