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 ee150b376cbf190ca73f7495260493f95483786a..195ebd3c9f3c2b2b4cf8d23d0f697c21bada8865 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 58f8288c0c8ad5b7af542fa798f11a7deb00c051..4595f10e68935f856f630982011211a026c8144f 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 8e5bf8cf9c394363cfdbd64beca8625af9f64ac5..18e25f2204b11980a576b0c0f746f3aa126ea68d 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 e6d92507bff1110fb89ebd8860d85de4b86a2784..a62db5dd2c9516a693a177177e78fb5fe7c64031 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 c32eb657f8246545ed56871310d16ea8c02c2021..da30e1d37db371ab9a3a30dae4daa9569ae334a3 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') {