doi: 10.17586/2226-1494-2015-15-1-107-114


STUDY OF SOLUTION REPRESENTATION LANGUAGE INFLUENCE ON EFFICIENCY OF INTEGER SEQUENCES PREDICTION

A. S. Potapov, V. V. Batishcheva, A. Y. Voropay


Read the full article  ';
Article in Russian

For citation: Potapov A.S., Batishcheva V.V., Voropay A.Yu. Study of solution representation language influence on efficiency of integer sequences prediction. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2015, vol. 15, no. 1, pp. 107–114

Abstract

Methods based on genetic programming for the problem solution of integer sequences extrapolation are the subjects for study in the paper. In order to check the hypothesis about the influence of language expression of program representation on the prediction effectiveness, the genetic programming method based on several limited languages for recurrent sequences has been developed. On the single sequence sample the implemented method with the use of more complete language has shown results, significantly better than the results of one of the current methods represented in literature based on artificial neural networks. Analysis of experimental comparison results for the realized method with the usage of different languages has shown that language extension increases the difficulty of consistent patterns search in languages, available for prediction in a simpler language though it makes new sequence classes accessible for prediction. This effect can be reduced but not eliminated completely at language extension by the constructions, which make solutions more compact. Carried out researches have drawn to the conclusion that alone the choice of an adequate language for solution representation is not enough for the full problem solution of integer sequences prediction (and, all the more, universal prediction problem). However, practically applied methods can be received by the usage of genetic programming.


Keywords: genetic programming, universal prediction, integer sequences, algorithmic complexity.

Acknowledgements. Работа выполнена при поддержке Министерства образования и науки Российской Федерации (проект №2323 в рамках базовой части государственного задания) и частично при государственной финансовой поддержке ведущих университетов Российской Федерации (субсидия 074-U01).

References

1. Hutter M. Universal algorithmic intelligence: a mathematical top→down approach. Cognitive Technologies, 2007, vol. 8, pp. 227–290. doi: 10.1007/978-3-540-68677-4_8

2. Solomonoff R. Algorithmic probability, heuristic programming and AGI. Proc. 3rd Conf. on Artificial General Intelligence, AGI 2010. Lugano, Switzerland, 2010, pp. 151–157.

3. Schmidhuber J. The new AI: general & sound & relevant for physics. Cognitive Technologies, 2007, vol. 8, pp. 175–198. doi: 10.1007/978-3-540-68677-4_6

4. Stern W., Whipple G. The Psychological Methods of Testing Intelligence. Baltimore, Warwick & York, 1914, 160 p.

5. Siebers M., Schmid U. Semi-analytic natural number series induction. Lecture Notes in Computer Science, 2012, vol. 7526, pp. 249–252. doi: 10.1007/978-3-642-33347-7_25

6. Strannegard C., Nizamani A.R., Sjoberg A., Engstrom F. Bounded Kolmogorov complexity based on cognitive models. Lecture Notes in Computer Science, 2013, vol. 7999, pp. 130–139. doi: 10.1007/978-3-642- 39521-5_14 

7. Strannegard C., Amirghasemi M., Ulfsbacker S. An anthropomorphic method for number sequence problems. Cognitive Systems Research, 2013, vol. 22–23, pp. 27–34. doi: 10.1016/j.cogsys.2012.05.003

8. Ragni M., Klein A. Predicting numbers: an AI approach to solving number series. Lecture Notes in Computer Science, 2011, vol. 7006, pp. 255–259. doi: 10.1007/978-3-642-24455-1_24

9. Solomonoff R.J. A formal theory of inductive inference. Part I. Information and Control, 1964, vol. 7, no. 1, pp. 1–22.

10. Solomonoff R.J. A formal theory of inductive inference. Part II. Information and Control, 1964, vol. 7, no. 2, pp. 224–254.

11. Potapov A., Svitenkov A., Vinogradov Y. Differences between Kolmogorov complexity and Solomonoff probability: consequences for AGI. Lecture Notes in Computer Science, 2012, vol. 7716, pp. 252–261. doi: 10.1007/978-3-642-35506-6_26

12. Poland J., Hutter M. MDL convergence speed for Bernoulli sequences. Statistics and Computing, 2006, vol. 16, no. 2, pp. 161–175. doi: 10.1007/s11222-006-6746-3

13. Potapov A., Rodionov S. Universal induction with varying sets of combinators. Lecture Notes in Computer Science, 2013, vol. 7999, pp. 88–97. doi: 10.1007/978-3-642-39521-5_10

14. Tsarev F. Sovmestnoe primenenie geneticheskogo programmirovaniya, konechnykh avtomatov i iskusstvennykh neironnykh setei dlya postroeniya sistemy upravleniya bespilotnym letatel'nym apparatom [Application of genetic programming, finite state machines and neural nets for construction of control system for unnmaned aircraft]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2008, no. 53, pp. 42–60.

15. Воndarenko I .B., Gatchin Yu.A., Geranichev V.N. Sintez optimal'nykh iskusstvennykh neironnykh setei s pomoshch'yu modifitsirovannogo geneticheskogo algoritma [Synthesis of optimal artificial neural networks by modified genetic algorithm]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 2 (78), pp. 51–55. 



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2021 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика