RobustTrend:

A Huber Loss with a Combined First and Second Order Difference Regularization for Time Series Trend Filtering

Qingsong Wen, Jingkun Gao, Xiaomin Song, Liang Sun, Jian Tan

​

Machine Intelligence Technology,

Alibaba DAMO Academy

Bellevue, WA, USA

​

Outline

• Background
• Proposed RobustTrend Algorithm
• Experiments and Comparisons
• Conclusions

Background: Real-World Time Series

• Time series
• Widely applied in science and engineering
• Crucial in many machine learning tasks, forecasting and anomaly detection
• Real-world challenges
• Lots of noise
• Outliers like spikes and dips
• Abrupt trend changes

​

Background: Time Series Trend Filtering

• Time series trend filtering

​

​

• Why need trend filtering
• Reveal insights from different components (trend, remainder)
• Utilize different components for different tasks
• E.g.: anomaly detection

​

Framework of Proposed RobustTrend Filter

• Proposed RobustTrend filter for time series
• Huber loss: robust to outliers
• 1st order L1 regularization: abrupt trend changes
• 2nd order L1 regularization: slow trend changes and can effectively reduce staircasing effect

where

ADMM for RobustTrend Filter

where

• Alternating direction method of multipliers (ADMM) for RobustTrend filter
• Optimization formulation

​

• Updating steps: (Tau−minimization step is not efficient)

Not efficient, no closed form

Efficient by soft thresholding

Efficient MM Algorithm for Tau−Minimization

• One-iteration majorization minimization (MM) for Tau−minimization step

​

​

• Now the approximated Tau−minimization step

​

• Theoretical motivation [Eckstein and Bertsekas, 1992]
• ADMM can still converge when the updating steps are carried out approximately

efficient with closed form

where

and

Experiments: Data and Baseline Algorithms

• Complex synthetic and real-world data
• Synthetic data: trend signal (sin, triangle, and square waves) with noise and outliers
• Real data: Yahoo’s anomaly detection dataset

• Baseline: 9 state-of-art trend filters
• Perform a relative comprehensive evaluation
• Baseline: H-P, L1, TV denoising, Mixed-trend, Wavelet trend, Repeated median, robfilter, EMD/EEMD trend filters.

Experiments on Synthetic Data

• Different trend filters on synthetic data with 1%-20% outliers

Overall, the RobustTrend filter has better performance than others.

Experiments on Synthetic Data

• Contributions of different components of the RobustTrend filter

Huber loss with 1st and 2nd order regularization has best results (i.e., RobustTrend filter).

Experiments: Online Mode on Real-World Data

​

• Compare trend filters of top performance
• Performance highlights
• L1 trend filter: sensitive to the outliers
• Robfilter: some delay when trend changes
• Repeated median filter: overshoots trend estimation
• RobustTrend filter: best tradeoff under outliers and abrupt trend changes

Conclusions

• Proposed a RobustTrend filtering for time series
• Adopt Huber loss with 1st and 2nd order L1 difference regularization
• Design an MM-ADMM algorithm to solve RobustTrend filtering
• Deal with noisy time series with outliers and abrupt trend changes
• Future work:
• Integrate it with anomaly detection
• Integrate it with long-term forecasting

Thanks!

Q&A