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