×

LUNAR: cellular automata for drifting data streams. (English) Zbl 1475.68198

Summary: With the advent of fast data streams, real-time machine learning has become a challenging task, demanding many processing resources. In addition, they can be affected by the concept drift effect, by which learning methods have to detect changes in the data distribution and adapt to these evolving conditions. Several emerging paradigms such as the so-called Smart Dust, Utility Fog, or Swarm Robotics are in need for efficient and scalable solutions in real-time scenarios, and where usually computing resources are constrained. Cellular automata, as low-bias and robust-to-noise pattern recognition methods with competitive classification performance, meet the requirements imposed by the aforementioned paradigms mainly due to their simplicity and parallel nature. In this work we propose , a streamified version of cellular automata devised to successfully meet the aforementioned requirements. is able to act as a real incremental learner while adapting to drifting conditions. Furthermore, is highly interpretable, as its cellular structure represents directly the mapping between the feature space and the labels to be predicted. Extensive simulations with synthetic and real data will provide evidence of its competitive behavior in terms of classification performance when compared to long-established and successful online learning methods.

MSC:

68Q80 Cellular automata (computational aspects)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Laney, D., 3d data management: Controlling data volume, velocity and variety, META Group Research Note, 6, 70, 1 (2001)
[2] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, A. Bouchachia, A survey on concept drift adaptation, ACM Computing Surveys (CSUR) 46 (4) (2014) 44. · Zbl 1305.68141
[3] Lu, J.; Liu, A.; Dong, F.; Gu, F.; Gama, J.; Zhang, G., Learning under concept drift: A review, IEEE Transactions on Knowledge and Data Engineering (2018)
[4] De Francisci Morales, G.; Bifet, A.; Khan, L.; Gama, J.; Fan, W., Iot big data stream mining, (Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016), ACM), 2119-2120
[5] Bifet, A.; Gavaldà, R.; Holmes, G.; Pfahringer, B., Machine Learning for Data Streams with Practical Examples in MOA (2018), MIT Press
[6] Losing, V.; Hammer, B.; Wersing, H., Incremental on-line learning: A review and comparison of state of the art algorithms, Neurocomputing, 275, 1261-1274 (2018)
[7] A. Barredo Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik, A. Barbado, S. García, S. Gil-López, D. Molina, R. Benjamins, R. Chatila, F. Herrera, Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI, Information Fusion 58 (2020) 82-115.
[8] Khamassi, I.; Sayed-Mouchaweh, M.; Hammami, M.; Ghédira, K., Discussion and review on evolving data streams and concept drift adapting, Evolving Systems, 9, 1, 1-23 (2018)
[9] Wolfram, S., A new kind of science, 5 (2002), Wolfram Media Champaign: Wolfram Media Champaign IL · Zbl 1022.68084
[10] Fawcett, T., Data mining with cellular automata, ACM SIGKDD Explorations Newsletter, 10, 1, 32-39 (2008)
[11] J. Neumann, A.W. Burks, et al., Theory of Self-Reproducing Automata, vol. 1102024, University of Illinois Press Urbana, 1966.
[12] Games, M., The fantastic combinations of John Conway’s new solitaire game “life” by Martin Gardner, Scientific American, 223, 120-123 (1970)
[13] Wolfram, S., Cellular automata as models of complexity, Nature, 311, 5985, 419 (1984)
[14] Bhattacharjee, K.; Naskar, N.; Roy, S.; Das, S., A survey of cellular automata: types, dynamics, non-uniformity and applications, Natural Computing, 1-29 (2016)
[15] Nebro, A. J.; Durillo, J. J.; Luna, F.; Dorronsoro, B.; Alba, E., Mocell: A cellular genetic algorithm for multiobjective optimization, International Journal of Intelligent Systems, 24, 7, 726-746 (2009) · Zbl 1176.90552
[16] Xhafa, F.; Alba, E.; Dorronsoro, B.; Duran, B.; Abraham, A., Efficient batch job scheduling in grids using cellular memetic algorithms, (Metaheuristics for Scheduling in Distributed Computing Environments (2008), Springer), 273-299 · Zbl 1153.68344
[17] Cook, M., Universality in elementary cellular automata, Complex Systems, 15, 1, 1-40 (2004) · Zbl 1167.68387
[18] R. Vafashoar, H. Morshedlou, A. Rezvanian, M.R. Meybodi, Cellular Learning Automata: Theory and Applications.
[19] Ilyas, M.; Mahgoub, I., Smart Dust: Sensor Network Applications, Architecture and Design (2018), CRC Press
[20] Dastjerdi, A. V.; Buyya, R., Fog computing: Helping the internet of things realize its potential, Computer, 49, 8, 112-116 (2016)
[21] Judy, J. W., Microelectromechanical systems (mems): fabrication, design and applications, Smart Materials and Structures, 10, 6, 1115 (2001)
[22] Del Ser, J.; Osaba, E.; Molina, D.; Yang, X.-S.; Salcedo-Sanz, S.; Camacho, D.; Das, S.; Suganthan, P. N.; Coello, C. A.C.; Herrera, F., Bio-inspired computation: Where we stand and what’s next, Swarm and Evolutionary Computation, 48, 220-250 (2019)
[23] D. López-de Ipiña, L. Chen, N. Mitton, G. Pan, Ubiquitous intelligence and computing for enabling a smarter world (2017).
[24] Feynman, R. P., Quantum mechanical computers, Foundations of Physics, 16, 6, 507-531 (1986)
[25] A. Adamatzky, Cellular Automata: A Volume in the Encyclopedia of Complexity and Systems Science, Springer, 2018. · Zbl 1484.68001
[26] Kari, J., Theory of cellular automata: A survey, Theoretical Computer Science, 334, 1-3, 3-33 (2005) · Zbl 1080.68070
[27] Jen, E., Invariant strings and pattern-recognizing properties of one-dimensional cellular automata, Journal of Statistical Physics, 43, 1-2, 243-265 (1986)
[28] Raghavan, R., Cellular automata in pattern recognition, Information Sciences, 70, 1-2, 145-177 (1993)
[29] A. Ultsch, Data mining as an application for artificial life, in: Proc. Fifth German Workshop on Artificial Life, Citeseer, 2002, pp. 191-197.
[30] Domingos, P.; Hulten, G., A general framework for mining massive data streams, Journal of Computational and Graphical Statistics, 12, 4, 945-949 (2003)
[31] J. Gama, P. Medas, G. Castillo, P. Rodrigues, Learning with drift detection, in: Brazilian Symposium on Artificial Intelligence, Springer, 2004, pp. 286-295. · Zbl 1105.68376
[32] S. Hashemi, Y. Yang, M. Pourkashani, M. Kangavari, To better handle concept change and noise: a cellular automata approach to data stream classification, in: Australasian Joint Conference on Artificial Intelligence, Springer, 2007, pp. 669-674.
[33] Pourkashani, M.; Kangavari, M. R., A cellular automata approach to detecting concept drift and dealing with noise, (2008 IEEE/ACS International Conference on Computer Systems and Applications (2008), IEEE), 142-148
[34] Bach, S. H.; Maloof, M. A., Paired learners for concept drift, (2008 Eighth IEEE International Conference on Data Mining (2008), IEEE), 23-32
[35] Dawid, A. P.; Vovk, V. G., Prequential probability: Principles and properties, Bernoulli, 5, 1, 125-162 (1999) · Zbl 0929.60001
[36] Gama, J.; Sebastião, R.; Rodrigues, P. P., On evaluating stream learning algorithms, Machine Learning, 90, 3, 317-346 (2013) · Zbl 1260.68329
[37] Minku, L. L.; White, A. P.; Yao, X., The impact of diversity on online ensemble learning in the presence of concept drift, IEEE Transactions on Knowledge and Data Engineering, 22, 5, 730-742 (2009)
[38] Gama, J., Knowledge Discovery from Data Streams (2010), Chapman and Hall/CRC · Zbl 1230.68017
[39] Montiel, J.; Read, J.; Bifet, A.; Abdessalem, T., Scikit-multiflow: a multi-output streaming framework, The Journal of Machine Learning Research, 19, 1 (2018), 2915-2914 · Zbl 07008328
[40] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al., Scikit-learn: Machine learning in python, Journal of Machine Learning Research 12 (Oct) (2011) 2825-2830. · Zbl 1280.68189
[41] L. Bottou, Large-scale machine learning with stochastic gradient descent, in: Proceedings of COMPSTAT’2010, Springer, 2010, pp. 177-186. · Zbl 1436.68293
[42] P. Domingos, G. Hulten, Mining high-speed data streams, in: Kdd, vol. 2, 2000, p. 4.
[43] Crammer, K.; Dekel, O.; Keshet, J.; Shalev-Shwartz, S.; Singer, Y., Online passive-aggressive algorithms, Journal of Machine Learning Research, 7, Mar, 551-585 (2006) · Zbl 1222.68177
[44] Read, J.; Bifet, A.; Pfahringer, B.; Holmes, G., Batch-incremental versus instance-incremental learning in dynamic and evolving data, (International Symposium on Intelligent Data Analysis (2012), Springer), 313-323
[45] Giraud-Carrier, C., A note on the utility of incremental learning, AI Communications, 13, 4, 215-223 (2000) · Zbl 0967.68087
[46] S. Lange, S. Zilles, Formal models of incremental learning and their analysis, in: Proceedings of the International Joint Conference on Neural Networks, 2003, vol. 4, IEEE, 2003, pp. 2691-2696.
[47] L.I. Kuncheva, Classifier ensembles for changing environments, in: International Workshop on Multiple Classifier Systems, Springer, 2004, pp. 1-15.
[48] Ditzler, G.; Polikar, R., Incremental learning of concept drift from streaming imbalanced data, IEEE Transactions on Knowledge and Data Engineering, 25, 10, 2283-2301 (2012)
[49] Demšar, J., Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research, 7, Jan, 1-30 (2006) · Zbl 1222.68184
[50] Rudin, C., Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead, Nature Machine Intelligence, 1, 5, 206-215 (2019)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.