×

zbMATH — the first resource for mathematics

Learning temporal causal sequence relationships from real-time time-series. (English) Zbl 07299932
Summary: We aim to mine temporal causal sequences that explain observed events (consequents) in time-series traces. Causal explanations of key events in a time-series have applications in design debugging, anomaly detection, planning, root-cause analysis and many more. We make use of decision trees and interval arithmetic to mine sequences that explain defining events in the time-series. We propose modified decision tree construction metrics to handle the non-determinism introduced by the temporal dimension. The mined sequences are expressed in a readable temporal logic language that is easy to interpret. The application of the proposed methodology is illustrated through various examples.
MSC:
68T Artificial intelligence
Software:
C4.5
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggarwal, C. C. (2015).Data Mining: The Textbook. Springer Publishing Company, Incorporated. · Zbl 1311.68001
[2] Asarin, E., et al. (2012). Parametric identification of temporal properties. InProc. of the 2nd International Conference on Runtime Verification, pp. 147-160.
[3] Bakhirkin, A., et al. (2018). Efficient parametric identification for stl. InHSCC, HSCC ’18, pp. 177-186. ACM. · Zbl 1409.68166
[4] Chakrabarti, K., et al. (2002). Locally adaptive dimensionality reduction for indexing large time series databases.ACM Trans. Database Syst.,27(2), 188-228.
[5] Chang, P. H., & Wang, L. C. (2010). Automatic assertion extraction via sequential data mining of simulation traces. InASP-DAC, pp. 607-612.
[6] Chockler, H., et al. (2020). Learning the language of software errors.J. Artif. Intell. Res., 67, 881-903. · Zbl 1437.68071
[7] Danese, A., et al. (2015a). Automatic extraction of assertions from execution traces of behavioural models. InProc. of DATE, pp. 67-72.
[8] Danese, A., et al. (2015b). A time-window based approach for dynamic assertions mining on control signals. InProc. of VLSI-SoC, pp. 246-251.
[9] Esling, P., & Agon, C. (2012). Time-series data mining.ACM Comput. Surv.,45(1), 12:1-12:34. · Zbl 1293.68104
[10] Evans, R., & Grefenstette, E. (2018). Learning explanatory rules from noisy data.J. Artif. Int. Res.,61(1), 1-64. · Zbl 1426.68235
[11] Faloutsos, C., et al. (1994). Fast subsequence matching in time-series databases. InProceedings of the 1994 ACM SIGMOD International Conference on Management of Data, SIGMOD ’94, pp. 419-429. ACM.
[12] Guo, R., et al. (2018). A survey of learning causality with data: Problems and methods. CoRR,abs/1809.09337.
[13] IEEE (2010). 1850-2010 - IEEE Standard for Property Specification Language (PSL) (https://standards.ieee.org/findstds/standard/1850-2010.html)..
[14] IEEE (2012). 1800-2012 - IEEE Standard for SystemVerilog-Unified Hardware Design, Specification, and Verification Language(http://standards.ieee.org/findstds/ standard/1800-2012.html)..
[15] Indyk, P., et al. (2000). Identifying representative trends in massive time series data sets using sketches. InProceedings of the 26th International Conference on Very Large Data Bases, VLDB ’00, pp. 363-372, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
[16] J. R. Quinlan (1993).C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
[17] Jin, X., et al. (2015). Mining requirements from closed-loop control models.IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems,34(11), 1704- 1717.
[18] Lemieux, C., et al. (2015). General ltl specification mining (t). InProc. of ASE.
[19] Ma, J., & Perkins, S. (2003). Online novelty detection on temporal sequences. InProceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, pp. 613-618, New York, NY, USA. ACM.
[20] Maler, O., & Nickovic, D. (2004). Monitoring temporal properties of continuous signals. InProceedings of Formal Modeling and Analysis of Timed Systems (FORMATSFTRTFT). Volume 3253 of LNCS, pp. 152-166. Springer. · Zbl 1109.68518
[21] Mitchell, T. M. (1997).Machine Learning(1 edition). McGraw-Hill, Inc., New York, NY, USA. · Zbl 0913.68167
[22] Ott, R. L., & Longnecker, M. T. (2006).Introduction to Statistical Methods and Data Analysis (with CD-ROM). Duxbury Press, Boston, MA, USA.
[23] Pearl, J. (1995). Causal diagrams for empirical research.Biometrika,82(4), 669-688. · Zbl 0860.62045
[24] Pearl, J. (2000).Causality: Models, Reasoning, and Inference. Cambridge University Press, New York, NY, USA. · Zbl 0959.68116
[25] Pearl, J. (2019). The seven tools of causal inference, with reflections on machine learning. Commun. ACM,62(3), 54-60.
[26] Pearl, J., et al. (2009). Causal inference in statistics: An overview.Statistics surveys,3, 96-146. · Zbl 1300.62013
[27] Pnueli, A. (1977). The temporal logic of programs. InProceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77, pp. 46-57, Washington, DC, USA. IEEE Computer Society.
[28] Quinlan, J. R. (1986). Induction of decision trees.Mach. Learn.,1(1), 81-106.
[29] Ralanamahatana, C. A., et al. (2005).Mining Time Series Data, pp. 1069-1103. Springer US.
[30] Vasudevan, S., et al. (2010). GoldMine: Automatic assertion generation using data mining and static analysis. InProc. of DATE, pp. 626-629.
[31] Yang, H., et al. (2012). Querying parametric temporal logic properties on embedded systems. InProf. of ICTSS.
[32] Ypma, A., et al. (1997). Novelty detection using self-organizing maps. InIn Proc. of ICONIP’97, pp. 1322-1325. Springer.
[33] Zhong, S.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.