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.



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

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