Perf dashboard should have UI to test out anomaly detection strategies
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 3 Apr 2015 01:07:02 +0000 (01:07 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 3 Apr 2015 01:07:02 +0000 (01:07 +0000)
https://bugs.webkit.org/show_bug.cgi?id=143290

Reviewed by Benjamin Poulain.

Added the UI to select anomaly detection strategies. The detected anomalies are highlighted in the graph.

Implemented the Western Electric Rules 1 through 4 in http://en.wikipedia.org/wiki/Western_Electric_rules
as well as Welch's t-test that compares the last five points to the prior twenty points.

The latter is what Mozilla uses (or at least did in the past) to detect performance regressions on their
performance tests although they compare medians instead of means.

All of these strategies don't quite work for us since our data points are too noisy but this is a good start.

* public/v2/app.js:
(App.Pane.updateStatisticsTools): Clone anomaly detection strategies.
(App.Pane._updateMovingAverageAndEnvelope): Highlight anomalies detected by the enabled strategies.
(App.Pane._movingAverageOrEnvelopeStrategyDidChange): Observe changes to anomaly detection strategies.
(App.Pane._computeMovingAverageAndOutliers): Detect anomalies by each strategy and aggregate results.
Only report the first data point when multiple consecutive data points are detected as anomalies.
* public/v2/chart-pane.css: Updated styles.
* public/v2/index.html: Added the pane for selecting anomaly detection strategies.
* public/v2/js/statistics.js:
(Statistics.testWelchsT): Added. Implements Welch's t-test.
(.sampleMeanAndVarianceForValues): Added.
(.createWesternElectricRule): Added.
(.countValuesOnSameSide): Added.
(Statistics.AnomalyDetectionStrategy): Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@182302 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Websites/perf.webkit.org/ChangeLog
Websites/perf.webkit.org/public/v2/app.js
Websites/perf.webkit.org/public/v2/chart-pane.css
Websites/perf.webkit.org/public/v2/index.html
Websites/perf.webkit.org/public/v2/js/statistics.js

index ee150b3..195ebd3 100644 (file)
@@ -1,3 +1,35 @@
+2015-04-02  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Perf dashboard should have UI to test out anomaly detection strategies
+        https://bugs.webkit.org/show_bug.cgi?id=143290
+
+        Reviewed by Benjamin Poulain.
+
+        Added the UI to select anomaly detection strategies. The detected anomalies are highlighted in the graph.
+
+        Implemented the Western Electric Rules 1 through 4 in http://en.wikipedia.org/wiki/Western_Electric_rules
+        as well as Welch's t-test that compares the last five points to the prior twenty points.
+
+        The latter is what Mozilla uses (or at least did in the past) to detect performance regressions on their
+        performance tests although they compare medians instead of means.
+
+        All of these strategies don't quite work for us since our data points are too noisy but this is a good start.
+
+        * public/v2/app.js:
+        (App.Pane.updateStatisticsTools): Clone anomaly detection strategies.
+        (App.Pane._updateMovingAverageAndEnvelope): Highlight anomalies detected by the enabled strategies.
+        (App.Pane._movingAverageOrEnvelopeStrategyDidChange): Observe changes to anomaly detection strategies.
+        (App.Pane._computeMovingAverageAndOutliers): Detect anomalies by each strategy and aggregate results.
+        Only report the first data point when multiple consecutive data points are detected as anomalies.
+        * public/v2/chart-pane.css: Updated styles.
+        * public/v2/index.html: Added the pane for selecting anomaly detection strategies.
+        * public/v2/js/statistics.js:
+        (Statistics.testWelchsT): Added. Implements Welch's t-test.
+        (.sampleMeanAndVarianceForValues): Added.
+        (.createWesternElectricRule): Added.
+        (.countValuesOnSameSide): Added.
+        (Statistics.AnomalyDetectionStrategy): Added.
+
 2015-03-31  Ryosuke Niwa  <rniwa@webkit.org>
 
         REGRESSION: Searching commits can highlight wrong data points
index 58f8288..4595f10 100755 (executable)
@@ -464,6 +464,9 @@ App.Pane = Ember.Object.extend({
         var envelopingStrategies = Statistics.EnvelopingStrategies.map(this._cloneStrategy.bind(this));
         this.set('envelopingStrategies', [{label: 'None'}].concat(envelopingStrategies));
         this.set('chosenEnvelopingStrategy', this._configureStrategy(envelopingStrategies, this.get('envelopingConfig')));
+
+        var anomalyDetectionStrategies = Statistics.AnomalyDetectionStrategy.map(this._cloneStrategy.bind(this));
+        this.set('anomalyDetectionStrategies', anomalyDetectionStrategies);
     }.on('init'),
     _cloneStrategy: function (strategy)
     {
@@ -504,8 +507,11 @@ App.Pane = Ember.Object.extend({
 
         var envelopingStrategy = this.get('chosenEnvelopingStrategy');
         this._updateStrategyConfigIfNeeded(envelopingStrategy, 'envelopingConfig');
-
-        chartData.movingAverage = this._computeMovingAverageAndOutliers(chartData, movingAverageStrategy, envelopingStrategy);
+        
+        var anomalyDetectionStrategies = this.get('anomalyDetectionStrategies').filterBy('enabled');
+        var anomalies = {};
+        chartData.movingAverage = this._computeMovingAverageAndOutliers(chartData, movingAverageStrategy, envelopingStrategy, anomalyDetectionStrategies, anomalies);
+        this.set('highlightedItems', anomalies);
     },
     _movingAverageOrEnvelopeStrategyDidChange: function () {
         this._updateMovingAverageAndEnvelope();
@@ -519,8 +525,9 @@ App.Pane = Ember.Object.extend({
         this.set('chartData', newChartData);
 
     }.observes('chosenMovingAverageStrategy', 'chosenMovingAverageStrategy.parameterList.@each.value',
-        'chosenEnvelopingStrategy', 'chosenEnvelopingStrategy.parameterList.@each.value'),
-    _computeMovingAverageAndOutliers: function (chartData, movingAverageStrategy, envelopingStrategy)
+        'chosenEnvelopingStrategy', 'chosenEnvelopingStrategy.parameterList.@each.value',
+        'anomalyDetectionStrategies.@each.enabled'),
+    _computeMovingAverageAndOutliers: function (chartData, movingAverageStrategy, envelopingStrategy, anomalyDetectionStrategies, anomalies)
     {
         var currentTimeSeriesData = chartData.current.series();
         var movingAverageIsSetByUser = movingAverageStrategy && movingAverageStrategy.execute;
@@ -542,6 +549,20 @@ App.Pane = Ember.Object.extend({
         if (!envelopeIsSetByUser)
             envelopeDelta = null;
 
+        var isAnomalyArray = new Array(currentTimeSeriesData.length);
+        for (var strategy of anomalyDetectionStrategies) {
+            var anomalyLengths = this._executeStrategy(strategy, currentTimeSeriesData, [movingAverageValues, envelopeDelta]);
+            for (var i = 0; i < currentTimeSeriesData.length; i++)
+                isAnomalyArray[i] = isAnomalyArray[i] || anomalyLengths[i];
+        }
+        for (var i = 0; i < isAnomalyArray.length; i++) {
+            if (!isAnomalyArray[i])
+                continue;
+            anomalies[currentTimeSeriesData[i].measurement.id()] = true;
+            while (isAnomalyArray[i] && i < isAnomalyArray.length)
+                ++i;
+        }
+
         if (movingAverageIsSetByUser) {
             return new TimeSeries(currentTimeSeriesData.map(function (point, index) {
                 var value = movingAverageValues[index];
index 8e5bf8c..18e25f2 100755 (executable)
@@ -64,6 +64,7 @@
 
 .popup-pane {
     position: absolute;
+    z-index: 10;
     top: 1.7rem;
     border: 1px solid #bbb;
     font-size: 0.8rem;
@@ -93,6 +94,7 @@
     margin: 0;
     padding: 0;
     font-size: 0.8rem;
+    max-width: 17rem;
 }
 
 .stat-option h1 {
     margin: 0.1rem 0.5rem 0.1rem 1rem;
 }
 
-.stat-option input {
+.stat-option input[type=number] {
     width: 4rem;
 }
 
-.stat-option p {
-    max-width: 15rem;
-}
-
 .analysis-pane {
     right: 1.3rem;
 }
 
 .chart {
     position: relative;
-    overflow: hidden;
 }
 
 .chart svg {
index e6d9250..a62db5d 100755 (executable)
                     {{/each}}
                 </section>
             {{/if}}
+            {{#if chosenEnvelopingStrategy.execute}}
+                <section class="stat-option">
+                    <h1>Anomaly Detection</h1>
+                    {{#each anomalyDetectionStrategies}}
+                        <label {{bind-attr title=description}}>{{input type="checkbox" name=id checked=enabled}}{{label}}</label>
+                    {{/each}}
+                </section>
+            {{/if}}
         </section>
     </script>
 
index c32eb65..da30e1d 100755 (executable)
@@ -56,6 +56,37 @@ var Statistics = new (function () {
         return [mean - delta, mean + delta];
     }
 
+    // Welch's t-test (http://en.wikipedia.org/wiki/Welch%27s_t_test)
+    this.testWelchsT = function (values1, values2, probability) {
+        var stat1 = sampleMeanAndVarianceForValues(values1);
+        var stat2 = sampleMeanAndVarianceForValues(values2);
+        var sumOfSampleVarianceOverSampleSize = stat1.variance / stat1.size + stat2.variance / stat2.size;
+        var t = (stat1.mean - stat2.mean) / Math.sqrt(sumOfSampleVarianceOverSampleSize);
+
+        // http://en.wikipedia.org/wiki/Welch–Satterthwaite_equation
+        var degreesOfFreedom = sumOfSampleVarianceOverSampleSize * sumOfSampleVarianceOverSampleSize
+            / (stat1.variance * stat1.variance / stat1.size / stat1.size / stat1.degreesOfFreedom
+                + stat2.variance * stat2.variance / stat2.size / stat2.size / stat2.degreesOfFreedom);
+
+        // They're different beyond the confidence interval of the specified probability.
+        return Math.abs(t) > tDistributionQuantiles[probability || 0.9][Math.round(degreesOfFreedom - 1)];
+    }
+
+    function sampleMeanAndVarianceForValues(values) {
+        var sum = Statistics.sum(values);
+        var squareSum = Statistics.squareSum(values);
+        var sampleMean = sum / values.length;
+        // FIXME: Maybe we should be using the biased sample variance.
+        var unbiasedSampleVariance = (squareSum - sum * sum / values.length) / (values.length - 1);
+        return {
+            mean: sampleMean,
+            variance: unbiasedSampleVariance,
+            size: values.length,
+            degreesOfFreedom: values.length - 1,
+        }
+    }
+
+    // One-sided t-distribution.
     var tDistributionQuantiles = {
         0.9: [
             3.077684, 1.885618, 1.637744, 1.533206, 1.475884, 1.439756, 1.414924, 1.396815, 1.383029, 1.372184,
@@ -198,6 +229,70 @@ var Statistics = new (function () {
             }
         },
     ];
+
+    function createWesternElectricRule(windowSize, minOutlinerCount, limitFactor) {
+        return function (values, movingAverages, deviation) {
+            var results = new Array(values.length);
+            var limit = limitFactor * deviation;
+            for (var i = 0; i < values.length; i++)
+                results[i] = countValuesOnSameSide(values, movingAverages, limit, i, windowSize) >= minOutlinerCount ? windowSize : 0;
+            return results;
+        }
+    }
+
+    function countValuesOnSameSide(values, movingAverages, limit, startIndex, windowSize) {
+        var valuesAboveLimit = 0;
+        var valuesBelowLimit = 0;
+        var center = movingAverages[startIndex];
+        for (var i = startIndex; i < startIndex + windowSize && i < values.length; i++) {
+            var diff = values[i] - center;
+            valuesAboveLimit += (diff > limit);
+            valuesBelowLimit += (diff < -limit);
+        }
+        return Math.max(valuesAboveLimit, valuesBelowLimit);
+    }
+    window.countValuesOnSameSide = countValuesOnSameSide;
+
+    this.AnomalyDetectionStrategy = [
+        // Western Electric rules: http://en.wikipedia.org/wiki/Western_Electric_rules
+        {
+            id: 200,
+            label: 'Western Electric: any point beyond 3σ',
+            description: 'Any single point falls outside 3σ limit from the moving average',
+            execute: createWesternElectricRule(1, 1, 3),
+        },
+        {
+            id: 201,
+            label: 'Western Electric: 2/3 points beyond 2σ',
+            description: 'Two out of three consecutive points fall outside 2σ limit from the moving average on the same side',
+            execute: createWesternElectricRule(3, 2, 2),
+        },
+        {
+            id: 202,
+            label: 'Western Electric: 4/5 points beyond σ',
+            description: 'Four out of five consecutive points fall outside 2σ limit from the moving average on the same side',
+            execute: createWesternElectricRule(5, 4, 1),
+        },
+        {
+            id: 203,
+            label: 'Western Electric: 9 points on same side',
+            description: 'Nine consecutive points on the same side of the moving average',
+            execute: createWesternElectricRule(9, 9, 0),
+        },
+        {
+            id: 210,
+            label: 'Mozilla: t-test 5 vs. 20 before that',
+            description: "Use student's t-test to determine whether the mean of the last five data points differs from the mean of the twenty values before that",
+            execute: function (values, movingAverages, deviation) {
+                var results = new Array(values.length);
+                var p = false;
+                for (var i = 20; i < values.length - 5; i++)
+                    results[i] = Statistics.testWelchsT(values.slice(i - 20, i), values.slice(i, i + 5), 0.99) ? 5 : 0;
+                return results;
+            }
+        },
+    ]
+
 })();
 
 if (typeof module != 'undefined') {