Towards Dynamic Trend Filtering through Trend Point Detection with Reinforcement Learning

1 Introduction

Trend filtering emphasizes proximity to the original time series data while filtering out noise through smoothness [Leser, 1961]. Smoothness in trend filtering simplifies complex patterns within noisy and non-stationary time series data, making it effective for forecasting and anomaly detection [Park et al., 2020]. While smoothness achieves the property of noise filtering, an 'abrupt change' denotes a point in a time series where the trend experiences a sharp transition, signaling a change in slope. Given that abrupt changes determine the direction and persistence of the slope, it is crucial to incorporate them into the trend. Traditional trend filtering employs a sum-of-squares function to reflect abrupt changes while utilizing second-order differences as a regularization term to attain smoothness [Hodrick and Prescott, 1997; Kim et al., 2009]. However, we found that the constant nature of smoothness filters out abrupt changes, making it challenging to distinguish them from noise.

The issue of constant smoothness arises from the reliance on the property of 'approximateness.' Evidence presented by [Ding et al., 2019] suggests that the sum-of-squares function eliminates tail distribution as outliers since it approximates a Gaussian distribution with a light-tail shape. As both abrupt changes and noise reside within the tail distribution, filtering out only noise becomes challenging. This uniform filtering results in the loss of valuable abrupt changes that should be reflected in the trend [Wen et al., 2019].

In this paper, we propose Trend Point Detection formulated as a Markov Decision Process (MDP), aiming to identify essential points that should be reflected in the trend, departing from approximateness [Sutton and Barto, 2018]. These essential points are termed Dynamic Trend Points (DTPs), and trends are extracted by interpolating them. We utilize the Reinforcement Learning (RL) algorithm within a discrete action space to solve the MDP problem, referred to as a Dynamic Trend Filtering network (DTF-net) [Schulman et al., 2017]. RL can directly detect essential points through an agent without being constrained by fixed window sizes or frequencies within the time series data domain. This dynamic approach enables the adjustment of noise filtering levels for each subsequence within the time series.

Building on prior research regarding reward function learning based on Gaussian Process (GP) [Biyik et al., 2020], we define the reward function as the sum-of-squares loss function from Time Series Forecasting (TSF). This choice is supported by [Ding et al., 2019], which suggests that the sum-of-squares function approximates a Gaussian distribution and functions similarly to a Gaussian kernel. Note that using a Gaussian kernel function as a reward leverages RL to effectively optimize the agent while learning the full distribution of time series data. Through the TSF reward, temporal dependencies around DTPs can be captured, and the level of smoothness is controlled by adjusting the forecasting window size. Additionally, to address the overfitting issue, we apply a random sampling method to both the state and the reward.

We compare DTF-net with four categorized baselines: trend filtering (TF), change point detection (CPD), anomaly detection (AD), and time series forecasting (TSF) algorithms.

First, traditional TF approaches commonly rely on approximations achieved through optimizing sum-of-squares functions or employing decomposition methods, which often neglect abrupt changes as noise. Second, CPD methods are rooted in probabilistic frameworks, prioritizing the detection of changes in distribution while often disregarding extreme values as outliers. Third, AD methods concentrate heavily on identifying abnormal points, sometimes overlooking the significance of distribution shifts in the data. Lastly, TSF models are categorized into decomposition-based and patchingbased models, which also neglect abrupt changes. Contrary to all the aforementioned baselines, DTF-net focuses on point detection to reflect abrupt changes in the trend, enhancing the performance of trend filtering and forecasting. To the best of our knowledge, this is the first approach that employs MDP and RL for trend filtering, aiming to reflect both abrupt changes and smoothness simultaneously.

Therefore, our contributions are as follows:

• We identified the issue of 'approximateness,' which leads to constant smoothness in traditional trend filtering, filtering out both abrupt changes and noise.
• We introduce Trend Point Detection formulated as an MDP, aiming to identify essential trend points that should be reflected in the trend, including abrupt changes. Additionally, we propose DTF-net, an RL algorithm that predicts DTPs through agents.
• We employ the forecasting sum-of-squares cost function, inspired by reward function learning based on GP, which allows for the consideration of temporal dependencies when capturing DTPs. A sampling method is applied to prevent the overfitting issue.
• We demonstrate that DTF-net excels at capturing abrupt changes compared to other trend filtering methods and enhances performance in forecasting tasks.

2 RelatedWork

2.1 Trend Filtering

Traditional trend-filtering algorithms have employed various methods to capture abrupt changes. H-P [Hodrick and Prescott, 1997] and ℓ1 [Kim et al., 2009] optimize the sumof-squares function, a widely used cost function for trend filtering. However, they often face challenges in the delayed detection of abrupt changes due to the use of second-order difference operators for smoothness. To address this issue, the TV-denoising algorithm [Chan et al., 2001] was introduced, relying on first-order differences. Nevertheless, this strategy introduces delays in detecting slow-varying trends while overly focusing on abrupt changes. These methods encounter difficulties in handling heavy-tailed distributions due to the use of the sum-of-squares function [Wen et al., 2019].

Contrary to sum-of-squares function methods, alternative approaches to trend filtering exist. For example, frequencybased methods like Wavelet [Craigmile and Percival, 2002] are designed for non-stationary signals but are susceptible to overfitting. The Empirical Mode Decomposition (EMD) algorithm [Wu et al., 2007] decomposes a time series into a finite set of oscillatory modes, but it generates overly smooth trends. Lastly, the Median filter [Siegel, 1982] is a non-linear filter that selects the middle value from the sorted central neighbors; therefore, outlier values that deviate significantly from the center of the data are excluded.

2.2 Extreme Value Theorem

Abrupt changes in a time series reside in the tail of the data distribution, making them rare events. However, their impact is significant, as they can alter the slope of the time series and affect the consistency of trends. Once an abrupt change occurs, its effects are often permanent until the next one occurs. Therefore, detecting abrupt changes is crucial to minimize false negative rates and capture important information.

Real-world time series data commonly exhibit a longheavy tail distribution. Formally, the tail distribution is defined as follows:

where T random variables {y1, ..., yT} are i.i.d. sampled from distribution FY [von Bortkiewicz, 1921; Ding et al., 2019]. Furthermore, extreme values within the tail distribution can be modeled using Extreme Value Theory.

Theorem 1 (Extreme Value Theory [Fisher and Tippett, 1928; Ding et al., 2019]). If the distribution in Equation (1) is not degenerate to 0 under a linear transformation of y, the distribution of the class with the non-degenerate distribution G(y) should be as follows:

Extreme Value Theory (EVT) has demonstrated that extreme values exhibit a limited degree of freedom [Lorenz, 1963]. This implies that the occurrence patterns of extreme values are recursive and can be memorized by a model [Altmann and Kantz, 2005]. Essentially, a model with substantial capacity and temporal invariance can effectively learn abrupt changes, which are categorized as extreme values.

However, extreme values are typically either unlabeled or imbalanced, making them challenging to predict. In classification tasks, previous research [Raj et al., 2016] has highlighted the susceptibility of deep networks to the data im-

• (a) DTF-net Environment

(b) DTF-net Reward

Figure 2: DTF-net Architecture. DTF-net has three processes to detect DTPs: 1) The agent predicts actions within a discrete space; 2) With the predicted actions, trends are extracted by interpolating them; 3) The agent is updated through the forecasting sum-of-squares function as a reward; with time series data X and trend T as inputs. For the reward calculation, as demonstrated in (b)-Case 3, when DTF-net successfully identifies abrupt changes, the prediction outcomes significantly improve, resulting in the highest reward.

balance issue. In forecasting tasks, [Ding et al., 2019] provided evidence that minimizing the sum-of-squares loss presupposes a Gaussian distribution, which differs significantly from long-heavy-tail distributions. Motivated by these issues, we define Trend Point Detection as a problem formulation aimed at detecting essential points that should be reflected in the trend rather than smoothed out. This formulation identifies DTPs, which encompass abrupt changes, midpoints of distribution shifts, and other critical points influencing changes in the trend slope, occurring in both short and long intervals. As illustrated in Figure 1, Trend Point Detection is formulated as an MDP and utilizes RL to detect abrupt changes directly through the agent's action prediction. Note that we train the DNNs as a policy network of an RL agent to learn the pattern of extreme value occurrence, distinct from approximating abrupt changes as output.

2.3 Markov Decision Process and Reinforcement Learning

MDP is a mathematical model for decision-making when an agent interacts with an environment. It relies on the firstorder Markov property, indicating that the future state depends solely on the current state. MDP comprises components denoted as ⟨S,A, P,R, γ⟩. Here, S denotes the set of environment states, while A represents the set of actions undertaken by the agent at state S. The transition probability, P = Pr(S′ |S,A), signifies the probability of transitioning from the current state S to the next state S′ . The reward, R = E[R(S, A, S′ )|S, A], where R(S, A, S ′ ) represents the immediate reward obtained when transitioning from state S to S′ by taking action A. The discount factor γ ∈ (0, 1] governs the trade-off between current and future rewards [Sutton and Barto, 2018]. We can formulate any time series data with an MDP for Trend Point Detection, as detecting points always adheres to the first-order Markov property [Wu and Ortiz, 2021]. These points are determined solely by the current time step and remain unaffected by past observations, sharing properties similar to those of predicting stock trading points.

In RL, actions are predicted through a policy network denoted as π(A|S) = Pr(A|S) for each state, representing the probability of action A at state S. The state-value function vπ(S) = Eπ[G|S] estimates the expected reward value for a state S under policy π, where G = ∑∞k=0 γ kR′k denotes the expected sum of future rewards starting from the next reward R′ . In RL of discrete action spaces, methods like Advantage Actor-Critic (A2C) [Mnih et al., 2016] and Proximal Policy Optimization (PPO) [Schulman et al., 2017] directly train the policy π using the estimated state-value function v. In contrast, Deep Q-Network (DQN) [Mnih et al., 2015] finds the optimal action-value function, denoted as qπ(S,A) = Eπ[G|S,A]. This function represents the expected cumulative reward for taking action A in state S under policy π and is determined through the Bellman equation (Appendix B). DTF-net utilizes RL to extract flexible trends through dynamic action prediction from a deep policy network π, learning within the time series data environment formulated as an MDP of the Trend Point Detection problem.

3 Dynamic Trend Filtering Network

3.1 Trend Point Detection

Environment Definition

Time series data is defined as T = {(X1, y1), (X2, y2), . . . , (XN, yN)}, where X ∈ RD represents the input, y ∈ Rd represents the output, and the dataset comprises a total of N ∈ Z+ samples. Here, D and d denote the input and output dimensions, respectively, both of which are positive integers.

The Trend Point Detection problem formulation takes input X representing the environment and outputs DTPs, encompassing abrupt changes, midpoints of distribution shifts, and other critical points influencing trend slope changes occurring at both short and long intervals. The output consists of specific univariate time series y(i) labeled with binary values, where i ∈ d of target.

• State S = [Xt,At]: the positional encoded vector set of time series data X and action A with horizon t.

• Action A: a discrete set with (a = 1) for detecting DTP and (a = 0) for smoothing.
• RewardR(S,A, S ′ ): the change in forecasting sum-ofsquares function value when action A is taken at state S and results in the transition to the next state S′ .
• Policy π(A|S): the probability distribution of A at S.

The RL algorithm, named DTF-net, employs a policy network π within the defined MDP. It receives the state S as input and outputs the binary labeled target y(i) , also denoted as A, learned through the maximization of cumulative rewards R. DTF-net is designed to extract dynamic trends by interpolating detected essential trend points, referred to as DTPs and represented by the set {y(i) = 1} or {A|a=1}.

Episode and State for DTF-net

Previous studies in RL for time series [Liu et al., 2022a] have generally adopted a sequential approach. In contrast, DTFnet introduces dynamic segmentation with variable lengths comprising one episode through random sampling. The discrete uniform distribution is specifically chosen to ensure that all sub-sequences are considered equally:

where s represents the starting points of the sub-sequence, l denotes the sub-sequence length, h denotes the forecasting look-back horizon, p denotes the forecasting prediction horizon, and H represents the maximum length comprising one episode. With sampling, the length and starting point of the sub-sequence are defined, resulting in a non-sequential and random progression of the episode. This sampling approach mitigates the overfitting issue by allowing the model to use only a portion of the sequence.

Within a single episode, DTF-net cumulatively constructs the state S. To maintain a constant state length within an episode, we employ positional encoding as follows:

The cumulative state progression is achieved by gradually expanding the state representation St as the step unfolds as follows,

Through cumulative state construction, the agent can learn sequential information in the time series (Appendix D.1).

3.2 Reward Function of DTF-net

GP and Reward Function Learning

Traditional trend filtering methods utilize the sum-of-squares function, also known as the Mean Squared Error (MSE), to approximate abrupt changes when extracting trends. However, [Ding et al., 2019] provided evidence that minimizing the sum-of-squares function assumes that the model output distribution determined using the MSE cost function denoted

Algorithm 1 Reward Procedure of DTF-net

as ˆ P(Y ), follows a Gaussian distribution with variance τ, grounded in Bregman's theory [Banerjee et al., 2005].

where o ∈ Y represents the output from a model parameterized by θ. This also suggests that model θ operates in a manner similar to a Kernel Density Estimator (KDE) employing a Gaussian kernel [Rosenblatt, 1956].

Contrary to approximations, DTF-net utilizes a policy network π to predict DTPs, including abrupt changes. However, defining a reward function in general time series data is challenging but is the most crucial task in RL training for optimizing the policy network. To tackle this challenge, DTFnet draws inspiration from previous works, which employ the Gaussian Process (GP) for reward function learning [Kuss and Rasmussen, 2003; Biyik et al., 2020].

Formally, GP [Williams and Rasmussen, 1995] assumes noisy targets yi = f(xi) + ϵi that are jointly Gaussian with a covariance function k:

With a Gaussian covariance function,

where diagonal matrix Λ, v, and σ are hyperparameters in θ, the predictive distribution for input x∗ follows Gaussian:

The GP model inherently learns a full distribution of time series data, enabling RL to effectively optimize the policy network (Appendix B). Leveraging these insights, DTF-net's reward function is defined as the sum-of-squares function from Time Series Forecasting (TSF). This choice leads to more efficiency in calculating rewards compared to GP while achieving reward function learning within the Gaussian distribution. To incorporate captured abrupt changes into the forecasting model, DTPs are included as an additional input. As shown in Figure 2, when the forecasting model predicts upward or downward trends instead of smoothing them out, the agent receives a higher reward. Thus, DTF-net learns temporal dependencies when capturing DTPs.

Forecasting Reward Function of DTF-net

As shown in Algorithm 1, the reward process involves time series data Xt-(h+p):t and action At-(h+p):t in state St at time step t, both having a sequence length denoted as (h+p), where h denotes the past horizon and p denotes the forecasting horizon (under the condition t - (h + p) > 0). The trend T initiates with X values assigned only under the condition of action A|a=1, and linear interpolation is applied for the remaining values. Subsequently, forecasting is conducted with a prediction length p defined by a hyperparameter. The reward is computed as the negative sum-of-squares loss between the predicted ˆ y and the ground truth y.

DTF-net uses a penalty reward as a negative value from the Mean Squared Error (MSE) function, and there is a possibility of an overfitting issue. Therefore, DTF-net utilizes random sampling from a discrete uniform distribution, providing better control over model updates.

We empirically demonstrate that irregularly applying penalties through sampling can prevent overfitting rather than penalizing at every step in Section 4.2 (Appendix D.2).

In summary, DTF-net is designed to extract dynamic trends T by interpolating detected DTPs. A simple ML time series predictor ϕ is integrated into DTF-net to calculate the reward, with the input of [X, T ]. As shown in Figure 2, including the detected abrupt changes as an additional input to the forecasting model ensures that the forecasting output reflects both upward and downward trends, maximizing the reward.

4 Experiment

4.1 Trend Filtering Analysis

Experimental Settings

Analyzing trend filtering methods quantitatively poses two challenges: 1) defining a ground truth for the trend is challenging, and 2) labeling abrupt changes is challenging. To address these, as shown in Figure 3, we generate a synthetic trend signal with 1, 000 time points. This synthetic dataset contains 11 abrupt changes, including 1) a sudden drop to negative values around -2 and -5 at time points 100 and 800, respectively; 2) a mean shift from 0 to 4 with high variance occurring between time points 500 and 700; and 3) a sine wave starting from time point 800 to 1000, completing one cycle. We add Gaussian noise with a standard deviation of 0.2 to simulate real-world conditions.

To evaluate the trend filtering results, we set up the experiment as follows. We employ Mean Squared Error (MSE) and Mean Absolute Error (MAE) metrics to measure the proximity to the original data, which is a key aspect of trend filtering. For the ground truth, we use a linear signal with added noise to assess DTF-net's robustness to noisy data. In cases with added noise, we assume that filtering out at least 10%

(a) ℓ1(λ = 0.1)

(b) ℓ1(λ = 5e - 4)

of noise is necessary to confirm smoothness. We divide the proximity evaluation into two categories: full-sequence and sub-sequence. In the sub-sequence evaluation, a 30-window interval is set around labeled abrupt changes to assess temporal dependencies are well captured.

Performance Analysis

Table 1 emphasizes DTF-net's superior performance compared to CPD and AD algorithms. CPD algorithms are designed to identify shifts in data distribution and tend to capture the midpoint of these changes, treating extreme values as outliers. On the other hand, AD algorithms focus exclusively on pinpointing anomalous data points, often overlooking the midpoint of changes. For instance, DCdetector is particularly adept at identifying abnormal values, demonstrating superior performance across entire data sequences. However, its effectiveness diminishes when dealing with abrupt sub-sequences. This shortfall stems from its focus solely on detecting abnormal points and short intervals surrounding abrupt changes. Consequently, while it maintains commendable performance on full sequences, it falls short in accurately filtering trends within abrupt sub-sequences.In essence, the differing objectives of CPD and AD algorithms make them less suitable for trend-filtering (Figure 7 in Appendix A).

In comparison with other trend filtering methods, DTFnet outperforms all methods except those prone to overfitting. Decomposition-based methods like EMD and Median generate excessively smoothed trends. The frequency-based method, Wavelet, tends to overfit to noise. The ℓ1 method shows sensitivity to hyperparameter λ, as evident by λ = 5e-4 causing overfitting to noise. Therefore, DTF-net excels in capturing abrupt changes while reflecting temporal dependencies within noisy and complex time series data.

Nasdaq Dataset

To demonstrate the proficiency of DTF-net on complex realworld datasets, we perform additional analysis on the Nasdaq intraday dataset from July 30th to August 1st, 2019, characterized by rapid changes. Here, we arbitrarily set 6 abrupt changes and qualitatively analyze the results. As shown in Figure 4, it is evident that the ℓ1 trend filtering algorithm extracts trends that either underfit or overfit depending on the parameter λ due to constant smoothness. For point 3, in detail, ℓ1 with (λ = 0.1) filtered out noise, while (λ = 5e - 4) captured it as abrupt changes. In contrast, DTF-net accurately captures five abrupt changes and concurrently performs noise filtering for point 3. This accomplishment is attributed to the dynamic nature of trend extraction from DTF-net.

4.2 Trend Filtering in Time Series Forecasting

Experimental Settings

We analyze how DTF-net effectively captures abrupt changes and extend our evaluation to include a real-world dataset for a common time series task. Time Series Forecasting (TSF) models are expected to predict potential incidents associated with extreme values, providing valuable insights for critical decision-making [Van den Berg et al., 2008]. To assess the practicality of DTF-net in real-world scenarios, we apply it to TSF, incorporating the extracted trend as an additional input feature. Formally, the forecasting model receives input as X′ = [X,P] ∈ RD+1 , where P represents the trend from DTF-net. Under the same conditions, we compare this model to those using ℓ1 as additional inputs and only the original sequence X as inputs. We employ DTF-net with the TSF models NLinear and DLinear [Zeng et al., 2023], which are considered state-of-the-art yet simplest in the field of TSF. The experiment focuses on the univariate forecasting case to assess trend filtering effectiveness (Appendix C). Note that DTF-net is not directly linked with TSF models; instead, the extracted trend fromDTF-net is provided as additional input.

Performance Analysis

We choose three non-stationary datasets from the TSF benchmark dataset: Exchange Rate, ETTh1, and Illness (Appendix C.1). Table 2 indicates that DTF-net outperforms in most cases. Among the three datasets, the exchange rate dataset is the most intricate, exhibiting the least seasonality and the highest level of noise. Given the absence of periodicity in financial data, ℓ1 trend filtering encounters difficulties in extracting clear trends. However, DTF-net demonstrates robustness when dealing with non-stationary time series data.

However, models employing ℓ1 trend filtering have advantages when dealing with more stationary data that exhibits a recursive pattern. The piece-wise linearity assumption of ℓ1 is particularly pronounced in short-term predictions within ETTh1, as it is the least noisy and most stationary dataset among the three. As shown in Table 2, ℓ1 achieves the best results for 24- and 48-hour forecasting windows in ETTh1. While DTF-net also outperforms the single forecasting model, the linearity characteristic of ℓ1 is better suited for short-term predictions within ETTh1. In contrast, for longterm predictions, we demonstrate that DTF-net performs the best. In the case of Illness with a small dataset size, DTF-net also performs well without overfitting.

Ablation Study

How to prevent RL overfitting? To mitigate the risk of overfitting in RL-based trend filtering, we introduce a reward sampling method. As shown in Figure 9, we observe that reward sampling prevents overfitting, achieving optimal performance with a reward sampling (Appendix B.4).

Empirical analysis on extreme value DNNs often generate smooth and averaged predictions as they typically optimize forecasting performance through empirical risk minimization. However, by incorporating accurately captured abrupt changes as additional information into the model, predictions are enhanced while representing both upward and downward signals instead of providing solely smooth estimates. To qualitatively assess the impact of abrupt changes on forecasting tasks, we compare two different trends: the original trends from DTF-net (red) and a version where 10% of extreme values are excluded (blue). As shown in Figure 5, this comparison demonstrates how incorporating abrupt changes can enrich forecasting by providing more detailed and accurate predictions.

5 Conclusion

We propose DTF-net, a novel RL-based trend filtering method directly identifying trend points. Traditional trend filtering methods struggle to capture abrupt changes due to their inherent approximations. To address this, we formalize the Trend Point Detection problem as an MDP and utilize RL within a discrete action space. The reward function is defined as the sum-of-squares loss from forecasting tasks inspired by reward function learning within the Gaussian distribution, allowing for the capturing of temporal dependencies around DTPs. DTF-net also tackles overfitting issues through random sampling. Compared to other trend filtering methods, DTF-net excels in identifying abrupt changes. In forecasting tasks, DTF-net enhances predictive performance without compromising the prediction output to be smooth.

Acknowledgments

This work was partly supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 20220-00984, Development of Artificial Intelligence Technology for Personalized Plug-and-Play Explanation and Verification of Explanation; No. 2022-0-00184, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics; No. 2021-0-02068, Artificial Intelligence Graduate School Program (KAIST)).