Introduction
In the field of qualitative reasoning, system behaviors are often described using non-numerical terms such as "increasing," "steady," or "decreasing." Identifying these monotonic trends is essential for building robust models like Model-Based Diagnosis (MBD). However, real-world sensor data is frequently contaminated with noise and insignificant fluctuations, making simple derivative-based methods unreliable.
The standard approach of segmenting data at every local extremum leads to an explosion of meaningless segments in noisy environments. Conversely, traditional curve-fitting methods like linear splines focus on minimizing geometric distance rather than capturing the underlying qualitative trends. This paper addresses this gap by introducing a mathematically sound framework to ignore small-scale noise while capturing significant large-scale trends.
Scale-Based Monotonicity
The authors propose Scale-Based Monotonicity, where a trend's monotonicity is defined relative to a specific tolerance or scale ($\delta$). This approach allows the algorithm to naturally filter out noise without the need for pre-processing filters that might distort the signal.
Key technical concepts include:
- δ-Monotonicity: A sequence is "upward δ-monotone" if it never drops by more than δ and contains at least one increase of at least δ.
- δ-Pairs and Singletons: The framework identifies pairs of extrema that "cancel each other out" at a certain noise scale (δ-pairs), while features that persist across scales are identified as "singletons."
- OPMAFE: The Optimal Piecewise Monotonic Approximation Function Error (OPMAFE) is introduced as a metric to measure the distance between a function and its perfectly piecewise monotonic approximation.
Algorithmic Approach
The paper details two primary algorithms for data processing:
- Labeling Algorithm ($O(n)$): A linear-time method that labels every peak and valley with its "delta-scale" ($\Delta(x)$), representing the largest noise threshold at which that feature remains significant.
- Segmentation Algorithm ($O(nK \log K)$): This algorithm uses the labeled data to find the $K$ most significant segments. Its complexity is effectively linear when the number of segments $K$ is small compared to the number of data points $n$.
Additionally, the authors introduce Scale-Based Flatness, allowing for the identification of "steady" segments where the optimal monotonic approximation remains constant over an interval.
Experimental Evaluation
The approach was evaluated using synthetic data from a Cascade Tank system. This two-tank model simulates water levels governed by differential equations, with added white noise to test robustness. The proposed "Optimal" algorithm was benchmarked against the standard top-down linear spline approximation algorithm.
Key Results
The experimental results demonstrate two major advantages of the scale-based approach:
- Superior Accuracy: The optimal algorithm consistently achieved lower OPMAFE (error) than the top-down linear spline method across various numbers of segments ($K$). This indicates a more faithful capture of the qualitative "shape" of the data.
- Computational Efficiency: With a complexity of $O(nK \log K)$, the proposed method is significantly faster than the $O(nK^2)$ complexity typical of top-down spline algorithms, especially as the desired model complexity ($K$) increases.
Conclusion and Future Work
By treating monotonicity as a scale property, the authors provide a robust method for qualitative modeling that is both fast and accurate. The framework provides a predictable link between the chosen noise scale and model accuracy, with a proven error bound of at most $\delta/2$ for any $\delta$-segmentation.
While currently limited to one-dimensional time series, future work aims to extend this scale-based logic to multidimensional qualitative modeling. This would enable the analysis of complex systems where multiple variables interact monotonically, further expanding the utility of the method in real-world diagnostic applications.
Summary updated