Informatics and Applications
2023, Volume 17, Issue 1, pp 3542
OPTIMAL SPANNING TREE RECONSTRUCTION IN SYMBOLIC REGRESSION
 R. G. Neychev
 I. A. Shibaev
 V. V. Strijov
Abstract
The paper investigates the problem of regression model generation. A model is a superposition of primitive functions. The model structure is described by a weighted colored graph. Each graph vertex corresponds to a primitive function. An edge assigns a superposition of two functions. The weight of an edge is equal to the probability of superposition. To generate an optimal model, one has to reconstruct its structure from its graph adjacency matrix. The proposed algorithm reconstructs the minimum spanning tree from the weighted colored graph. The paper presents a novel solution based on the prizecollecting Steiner tree algorithm. This algorithm is compared with its alternatives.
[+] References (11)
 Koza, J. R. 1994. Genetic programming as a means for programming computers by natural selection. Stat. Com put. 4:87112.
 Searson, D.P., D. E. Leahy, and M.J. Willis. 2010. GPTIPS: An open source genetic programming toolbox for multigene symbolic regression. Multiconference (International) of Engineers and Computer Scientists Proceedings. 1:7780.
 Stanley, K. O., and R. Miikkulainen. 2002. Evolving neural networks through augmenting topologies. Evol. Comput. 10(2):99127.
 Bochkarev, A.M., I. L. Sofronov, and V. V. Strijov. 2017. Porozhdenie ekspertnointerpretiruemykh modeley dlya prognoza pronitsaemosti gornoy porody [Generation of expertlyinterpreted models for prediction of core permeability], Sistemy i Sredstva Informatiki  Systems and Means of Informatics 27(3):7487.
 Ravi, R., R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi. 1996. Spanning trees  short or small. SIAMJ. Discrete Math. 9(2):178200.
 Chudak, F.A., T. Roughgarden, and D. P. Williamson. 2004. Approximate kMSTS and kSteiner trees via the primaldual method and Lagrangean relaxation. Math. Program. 100(2):411421.
 Awerbuch, B., Y. Azar, A. Blum, and S. Vempala. 1998. New approximation guarantees for minimumweight ktrees and prizecollecting salesmen. SIAM J. Comput. 28(1):254262.
 Arora, S., and G. Karakostas. 2006. A 2 + e approximation algorithm for the kMST problem. Math. Program. 107(3):491504.
 Hegde, C., P. Indyk, and L. Schmidt. 2014. Afast, adaptive variant of the GoemansWilliamson scheme for the prize collecting Steiner tree problem. 11th DIMACS Implementation Challenge Workshop Proceedings. 132. Available at: http://people.csail.mit.edu/ludwigs/papers/ dimacsl4_fastpcst.pdf (accessed January 10, 2023).
 Ras, C., K. Swanepoel, and D.A. Thomas. 2017. Approximate Euclidean Steiner trees. J. Optimiz. Theory App. 172(3):845873.
 Goemans, M.X., and D. P. Williamson. 1995. A general approximation technique for constrained forest problems. SIAMJ. Comput. 24(2):296317.
[+] About this article
Title
OPTIMAL SPANNING TREE RECONSTRUCTION IN SYMBOLIC REGRESSION
Journal
Informatics and Applications
2023, Volume 17, Issue 1, pp 3542
Cover Date
20230410
DOI
10.14357/19922264230105
Print ISSN
19922264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
symbolic regression; linear programming; superposition; minimum spanning tree; adjacency matrix
Authors
R. G. Neychev , I. A. Shibaev , and V. V. Strijov
Author Affiliations
Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 442 Vavilov Str., Moscow 119333, Russian Federation
