НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
doi: 10.17586/2226-1494-2015-15-1-107-114
УДК 004.855
ИССЛЕДОВАНИЕ ВЛИЯНИЯ ЯЗЫКА ПРЕДСТАВЛЕНИЯ РЕШЕНИЙ НА ЭФФЕКТИВНОСТЬ ПРЕДСКАЗАНИЯ ЦЕЛОЧИСЛЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Читать статью полностью
Ссылка для цитирования: Потапов А.С., Батищева В.В., Воропай А.Ю. Исследование влияния языка представления решений на эффективность предсказания целочисленных последовательностей // Научно-технический вестник информационных технологий, механики и оптики. 2015. Том 15. № 1. С. 107–114
Аннотация
Предметом исследования в работе являются методы генетического программирования при решении задач экстраполяции целочисленных последовательностей. В целях проверки гипотезы о влиянии выразительности языка представления программ на эффективность предсказания был реализован метод генетического программирования на основе нескольких ограниченных языков для представления рекуррентных последовательностей. На одной выборке последовательностей реализованный метод с использованием наиболее полного языка показал результаты, существенно превосходящие один из представленных в литературе современных методов на основе искусственных нейронных сетей. Анализ результатов экспериментального сравнения разработанного метода с использованием различных языков показал, что расширение языка, делая доступными для предсказания новые классы последовательностей, в то же время увеличивает сложность поиска закономерностей для последовательностей, доступных для предсказания в более простом языке. Данный эффект может быть ослаблен, но не устранен полностью, при расширении языка конструкциями, делающими решения наиболее компактными. На основе проведенных исследований сделан вывод, что, хотя с использованием генетического программирования могут быть получены практически применимые методы, одного только выбора адекватного языка представления решений недостаточно для полного решения задачи предсказания целочисленных последовательностей (и, тем более, проблемы универсального предсказания).
Благодарности. Работа выполнена при поддержке Министерства образования и науки Российской Федерации (проект №2323 в рамках базовой части государственного задания) и частично при государственной финансовой поддержке ведущих университетов Российской Федерации (субсидия 074-U01).
Список литературы
1. Hutter M. Universal algorithmic intelligence: a mathematical top→down approach // Cognitive Technologies. 2007. V. 8. P. 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. P. 151–157.
3. Schmidhuber J. The new AI: general & sound & relevant for physics // Cognitive Technologies. 2007. V. 8. P. 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. V. 7526. P. 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. V. 7999. P. 130–139. doi: 10.1007/978-3-642- 39521-5_
7. Strannegard C., Amirghasemi M., Ulfsbacker S. An anthropomorphic method for number sequence problems // Cognitive Systems Research. 2013. V. 22–23. P. 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. V. 7006. P. 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. V. 7. N 1. P. 1–22.
10. Solomonoff R.J. A formal theory of inductive inference. Part II // Information and Control. 1964. V. 7. N 2. P. 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. V. 7716. P. 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. V. 16. N 2. P. 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. V. 7999. P. 88–97. doi: 10.1007/978-3-642-39521-5_10
14. Царев Ф.Н. Совместное применение генетического программирования, конечных автоматов и искус- ственных нейронных сетей для построения системы управления беспилотным летательным аппаратом // Научно-технический вестник СПбГУ ИТМО. 2008. № 53. С. 42–60.
15. Бондаренко И.Б., Гатчин Ю.А., Гераничев В.Н. Синтез оптимальных искусственных нейронных сетей с помощью модифицированного генетического алгоритма // Научно-технический вестник информаци- онных технологий, механики и оптики. 2012. № 2 (78). С. 51–55.