Informatics and Applications
2023, Volume 17, Issue 1, pp 35-42
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 prize-collecting 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:87-112.
- 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:77-80.
- Stanley, K. O., and R. Miikkulainen. 2002. Evolving neural networks through augmenting topologies. Evol. Comput. 10(2):99-127.
- Bochkarev, A.M., I. L. Sofronov, and V. V. Strijov. 2017. Porozhdenie ekspertno-interpretiruemykh modeley dlya prognoza pronitsaemosti gornoy porody [Generation of expertly-interpreted models for prediction of core per-meability], Sistemy i Sredstva Informatiki - Systems and Means of Informatics 27(3):74-87.
- 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):178-200.
- Chudak, F.A., T. Roughgarden, and D. P. Williamson. 2004. Approximate k-MSTS and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Math. Program. 100(2):411-421.
- Awerbuch, B., Y. Azar, A. Blum, and S. Vempala. 1998. New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Comput. 28(1):254-262.
- Arora, S., and G. Karakostas. 2006. A 2 + e approximation algorithm for the k-MST problem. Math. Program. 107(3):491-504.
- Hegde, C., P. Indyk, and L. Schmidt. 2014. Afast, adaptive variant of the Goemans-Williamson scheme for the prize- collecting Steiner tree problem. 11th DIMACS Imple-mentation Challenge Workshop Proceedings. 1-32. Avail-able at: http://people.csail.mit.edu/ludwigs/papers/ dimacsl4_fastpcst.pdf (accessed January 10, 2023).
- Ras, C., K. Swanepoel, and D.A. Thomas. 2017. Ap-proximate Euclidean Steiner trees. J. Optimiz. Theory App. 172(3):845-873.
- Goemans, M.X., and D. P. Williamson. 1995. A general approximation technique for constrained forest problems. SIAMJ. Comput. 24(2):296-317.
[+] About this article
Title
OPTIMAL SPANNING TREE RECONSTRUCTION IN SYMBOLIC REGRESSION
Journal
Informatics and Applications
2023, Volume 17, Issue 1, pp 35-42
Cover Date
2023-04-10
DOI
10.14357/19922264230105
Print ISSN
1992-2264
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, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|