1 Introduction
2 Background and adaptive estimation
2.1 Problem definition
2.2 Forgetting factor framework
2.2.1 Formulation
2.2.2 A temporally adaptive likelihood function
2.2.3 Adaptive parameter updates
2.2.4 Interpreting the forgetting factors
3 Adaptively tuning the forgetting factors
4 Change detection methods
4.1 ADEPT-M
Notation | Description |
---|---|
\(x_t\) | Observed state |
\({\mathcal {S}}\) | State-space |
\(\tau _k\) | Changepoint location |
\(B_t^{(i)}\) | Multiset of state transitions |
\(\lambda ^{(i)}_t\) | Adaptive FF |
\(\tilde{{\varvec{P}}}_t\) | Adaptive transition matrix |
\({\tilde{p}}_t^{(j|i)}\) | \(ij^{\text {th}}\) element of \(\tilde{{\varvec{P}}}_t\) |
\(w_k^{(i)}\) | Weight assigned to \(B_t^{(i)}[k]\) |
\(n_t^{(i)}\) | Effective sample size |
\(L_t^{(j|i)}, U_t^{(j|i)}\) | Control limits for ADEPT-M |
\(a_t^{(j|i)}, b_t^{(j|i)}\) | Parameters used to construct control limits |
B, G | Length of burn-in and grace period |
\(\alpha \) | Significance level |
4.2 Commonly used control charts
4.2.1 CUSUM
4.2.2 EWMA
CUSUM | \((k_1,h_1)\) | \((k_2,h_2)\) | \((k_3,h_3)\) |
(k, h) values: | (0.250, 8.010) | (0.500, 4.770) | (0.750, 3.340) |
EWMA | \((r_1,L_1)\) | \((r_2,L_2)\) | \((r_3,L_3)\) |
(r, L) values: | (1.000, 3.090) | (0.250, 2.998) | (0.03, 2.437) |
4.3 Additional detectors
4.3.1 ADWIN
4.3.2 PELT
4.4 Extending to transition matrices
5 Performance measures
5.1 The average run lengths
5.2 CCD and DNF
5.3 ARL adjustments
6 Simulation study
6.1 Experimental framework
6.2 Results
\((\alpha ,\eta )\) | \(10^{-1}\) | \(10^{-2}\) | \(10^{-3}\) | \(10^{-4}\) | \(10^{-5}\) | \(10^{-6}\) | |
---|---|---|---|---|---|---|---|
\({ARL}_0\) | |||||||
\(10^{-2}\) | 22.75 | 46.35 | 111.74 | 337.39 | 1866.39 | 6519.52 | |
\(10^{-3}\) | 24.11 | 49.43 | 128.79 | 496.59 | 3463.98 | 8441.14 | |
\(10^{-4}\) | 25.22 | 51.87 | 145.88 | 702.97 | 4974.52 | 9509.45 | |
\({ARL}_1\) | |||||||
\({G=25}\) | \(10^{-2}\) | 222.79 | 204.45 | 217.72 | 51.63 | 22.39 | 44.56 |
\(10^{-3}\) | 410.05 | 371.08 | 209.19 | 42.28 | 24.73 | 50.64 | |
\(10^{-4}\) | 569.17 | 439.91 | 257.25 | 49.18 | 26.09 | 53.44 | |
\({G=50}\) | \(10^{-2}\) | 238.03 | 244.62 | 344.44 | 85.48 | 24.74 | 44.69 |
\(10^{-3}\) | 403.03 | 321.89 | 361.22 | 123.74 | 44.52 | 50.22 | |
\(10^{-4}\) | 588.31 | 468.72 | 368.19 | 149.22 | 47.23 | 53.06 | |
\({G=75}\) | \(10^{-2}\) | 261.89 | 204.55 | 610.98 | 214.40 | 36.80 | 44.88 |
\(10^{-3}\) | 460.06 | 360.89 | 537.13 | 250.02 | 49.01 | 51.23 | |
\(10^{-4}\) | 626.16 | 409.03 | 436.91 | 275.18 | 66.48 | 54.36 | |
\({G=100}\) | \(10^{-2}\) | 251.31 | 219.28 | 624.18 | 268.86 | 45.15 | 45.27 |
\(10^{-3}\) | 407.04 | 380.72 | 704.59 | 355.31 | 73.40 | 52.16 | |
\(10^{-4}\) | 584.80 | 441.23 | 574.10 | 393.67 | 130.01 | 57.27 |
\(\text {EWMA}_1\) | \(\text {EWMA}_2\) | \(\text {EWMA}_3\) | \(\text {CUSUM}_1\) | \(\text {CUSUM}_2\) | \(\text {CUSUM}_3\) | ||
---|---|---|---|---|---|---|---|
\({m=0}\) | |||||||
\({ARL}_0\) | 8795.49 | 4153.88 | 739.97 | 981.33 | 2518.27 | 3481.03 | |
\({m=1}\) | |||||||
\({G = 25}\) | \({ARL}_1\) | 2838.82 | 942.42 | 83.76 | 89.24 | 434.20 | 700.17 |
\({G=50}\) | \({ARL}_1\) | 2791.25 | 801.72 | 73.14 | 103.01 | 407.70 | 660.62 |
\({G=75}\) | \({ARL}_1\) | 2466.87 | 753.27 | 93.15 | 99.88 | 428.81 | 612.61 |
\({G=100}\) | \({ARL}_1\) | 2499.27 | 743.55 | 98.99 | 98.25 | 372.02 | 588.76 |
\({m=10}\) | |||||||
\({G = 25}\) | \(F_1\) | 0.05 | 0.15 | 0.23 | 0.21 | 0.22 | 0.19 |
\({G=50}\) | \(F_1\) | 0.08 | 0.19 | 0.29 | 0.27 | 0.29 | 0.24 |
\({G=75}\) | \(F_1\) | 0.09 | 0.22 | 0.34 | 0.33 | 0.33 | 0.26 |
\({G=100}\) | \(F_1\) | 0.10 | 0.23 | 0.38 | 0.37 | 0.36 | 0.29 |
\({m=50}\) | |||||||
\({G = 25}\) | \(F_1\) | 0.02 | 0.09 | 0.54 | 0.54 | 0.48 | 0.32 |
\({G=50}\) | \(F_1\) | 0.02 | 0.09 | 0.61 | 0.62 | 0.54 | 0.34 |
\({G=75}\) | \(F_1\) | 0.02 | 0.10 | 0.64 | 0.65 | 0.56 | 0.34 |
\({G=100}\) | \(F_1\) | 0.04 | 0.11 | 0.65 | 0.66 | 0.57 | 0.33 |
\({m=100}\) | |||||||
\({G = 25}\) | \(F_1\) | 0.02 | 0.04 | 0.64 | 0.66 | 0.55 | 0.33 |
\({G=50}\) | \(F_1\) | 0.02 | 0.06 | 0.67 | 0.69 | 0.57 | 0.32 |
\({G=75}\) | \(F_1\) | 0.02 | 0.06 | 0.67 | 0.68 | 0.56 | 0.30 |
\({G=100}\) | \(F_1\) | 0.02 | 0.06 | 0.64 | 0.65 | 0.56 | 0.28 |
m | PELT | ADWIN(0.002) | ADWIN(0.05) | ADWIN(0.1) | ADWIN(0.3) |
---|---|---|---|---|---|
0 | 11100.78 | 9089.53 | 7644.70 | 7076.12 | 5850.25 |
1 | 1440.22 | 326.36 | 265.76 | 246.10 | 209.82 |
10 | 0.47 | 0.29 | 0.28 | 0.28 | 0.27 |
50 | 0.30 | 0.43 | 0.41 | 0.40 | 0.39 |
100 | 0.20 | 0.45 | 0.46 | 0.46 | 0.46 |
\({(\alpha ,\eta )}\) | \(10^{-1}\) | \(10^{-2}\) | \(10^{-3}\) | \(10^{-4}\) | \(10^{-5}\) | \(10^{-6}\) | ||
---|---|---|---|---|---|---|---|---|
\({m=10}\) | \({G=25}\) | \(10^{-2}\) | 0.25 | 0.32 | 0.63 | 0.63 | 0.41 | 0.34 |
\(10^{-3}\) | 0.45 | 0.48 | 0.73 | 0.74 | 0.68 | 0.62 | ||
\(10^{-4}\) | 0.55 | 0.59 | 0.74 | 0.72 | 0.75 | 0.74 | ||
\({{G=50}}\) | \(10^{-2}\) | 0.27 | 0.31 | 0.57 | 0.64 | 0.45 | 0.38 | |
\(10^{-3}\) | 0.45 | 0.44 | 0.70 | 0.75 | 0.72 | 0.66 | ||
\(10^{-4}\) | 0.54 | 0.53 | 0.73 | 0.72 | 0.79 | 0.78 | ||
\({{G=75}}\) | \(10^{-2}\) | 0.29 | 0.33 | 0.54 | 0.65 | 0.48 | 0.40 | |
\(10^{-3}\) | 0.46 | 0.45 | 0.66 | 0.73 | 0.74 | 0.68 | ||
\(10^{-4}\) | 0.55 | 0.53 | 0.71 | 0.71 | 0.79 | 0.79 | ||
\({G=100}\) | \(10^{-2}\) | 0.31 | 0.36 | 0.53 | 0.65 | 0.49 | 0.42 | |
\(10^{-3}\) | 0.47 | 0.46 | 0.64 | 0.73 | 0.74 | 0.68 | ||
\(10^{-4}\) | 0.55 | 0.53 | 0.69 | 0.71 | 0.79 | 0.79 | ||
\({m=50}\) | \({G=25}\) | \(10^{-2}\) | 0.52 | 0.63 | 0.77 | 0.69 | 0.65 | 0.63 |
\(10^{-3}\) | 0.62 | 0.69 | 0.76 | 0.74 | 0.76 | 0.75 | ||
\(10^{-4}\) | 0.63 | 0.69 | 0.68 | 0.69 | 0.78 | 0.78 | ||
\({G=50}\) | \(10^{-2}\) | 0.54 | 0.61 | 0.74 | 0.71 | 0.68 | 0.68 | |
\(10^{-3}\) | 0.61 | 0.66 | 0.72 | 0.73 | 0.76 | 0.76 | ||
\(10^{-4}\) | 0.61 | 0.66 | 0.67 | 0.67 | 0.77 | 0.78 | ||
\({G=75}\) | \(10^{-2}\) | 0.55 | 0.62 | 0.71 | 0.70 | 0.69 | 0.68 | |
\(10^{-3}\) | 0.61 | 0.65 | 0.69 | 0.70 | 0.74 | 0.74 | ||
\(10^{-4}\) | 0.60 | 0.65 | 0.65 | 0.64 | 0.73 | 0.74 | ||
\({G=100}\) | \(10^{-2}\) | 0.56 | 0.61 | 0.68 | 0.69 | 0.68 | 0.67 | |
\(10^{-3}\) | 0.60 | 0.63 | 0.66 | 0.67 | 0.71 | 0.71 | ||
\(10^{-4}\) | 0.59 | 0.63 | 0.63 | 0.62 | 0.69 | 0.71 | ||
\({ m=100}\) | \({G=25}\) | \(10^{-2}\) | 0.60 | 0.69 | 0.75 | 0.72 | 0.71 | 0.71 |
\(10^{-3}\) | 0.63 | 0.69 | 0.70 | 0.74 | 0.76 | 0.76 | ||
\(10^{-4}\) | 0.60 | 0.64 | 0.59 | 0.71 | 0.75 | 0.76 | ||
\({G=50}\) | \(10^{-2}\) | 0.59 | 0.64 | 0.69 | 0.70 | 0.69 | 0.70 | |
\(10^{-3}\) | 0.60 | 0.64 | 0.64 | 0.69 | 0.71 | 0.72 | ||
\(10^{-4}\) | 0.57 | 0.61 | 0.57 | 0.65 | 0.68 | 0.71 | ||
\({G=75}\) | \(10^{-2}\) | 0.58 | 0.61 | 0.65 | 0.66 | 0.66 | 0.66 | |
\(10^{-3}\) | 0.58 | 0.61 | 0.61 | 0.64 | 0.65 | 0.66 | ||
\(10^{-4}\) | 0.55 | 0.58 | 0.55 | 0.60 | 0.63 | 0.65 | ||
\({G=100}\) | \(10^{-2}\) | 0.56 | 0.59 | 0.60 | 0.62 | 0.62 | 0.62 | |
\(10^{-3}\) | 0.55 | 0.57 | 0.57 | 0.59 | 0.61 | 0.62 | ||
\(10^{-4}\) | 0.52 | 0.55 | 0.53 | 0.56 | 0.58 | 0.60 |
7 Real data illustrations
7.1 HTTP web requests
7.1.1 The data
PUT
request pushes information to a server, and a \(\mathtt {POST}\) request sends a client’s data to a server for processing. The other requests have similar meanings; see Gourley and Totty (2002) for more details on HTTP requests.7.1.2 Results
\({(\alpha ,\eta )}\) | \(10^{-4}\) | \(10^{-5}\) | \(10^{-6}\) | |
---|---|---|---|---|
\({\delta = 0.25}\) | \(10^{-3}\) | 1.83 | 1.83 | 1.83 |
\(10^{-4}\) | 1.91 | 1.92 | 1.92 | |
\(10^{-5}\) | 2.89 | 2.90 | 2.91 | |
\({\delta =0.50}\) | \(10^{-3}\) | 1.82 | 1.83 | 1.83 |
\(10^{-4}\) | 1.88 | 1.90 | 1.91 | |
\(10^{-5}\) | 1.90 | 1.92 | 3.22 | |
\({\delta = 1.00}\) | \(10^{-3}\) | 1.86 | 1.86 | 1.86 |
\(10^{-4}\) | 1.91 | 1.92 | 1.96 | |
\(10^{-5}\) | 1.96 | 3.22 | 3.22 | |
\({\delta =2.00}\) | \(10^{-3}\) | 1.87 | 1.88 | 1.89 |
\(10^{-4}\) | 1.90 | 1.92 | 1.93 | |
\(10^{-5}\) | 1.90 | 1.92 | 3.25 |