НАУЧНЫЙ ВЕСТНИК


НОВОСИБИРСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

ISSN (печатн.): 1814-1196          ISSN (онлайн): 2658-3275
English | Русский

Последний выпуск
№3(72) Июль - Сентябрь 2018

Сортировка массива целых чисел с использованием нейронной сети

Выпуск № 2 (63) Апрель - Июнь 2016
Авторы:

А.А. ВОЕВОДА,
В.Л. ПОЛУБИНСКИЙ,
Д.О. РОМАННИКОВ
DOI: http://dx.doi.org/10.17212/1814-1196-2016-2-151-157
Аннотация


На сегодняшний момент существует достаточно большое количество различных алгоритмов и структур данных, на основании которых построены все современные программные системы. Но, с другой стороны, данные алгоритмы плохо подходят для решения задач распознавания образов, классификации и регрессии, для которых существуют специальные методы и/или применяются решения, построенные на основании нейронных сетей. Нейронные сети, по своей сущности, являются универсальными аппроксиматорами, т. е. могут с большой степенью точности повторить, например, заданную кривую. Также из этого следует, что в отличие от классических алгоритмов системы, основанные на нейронных сетях, будут всегда иметь какой-то процент ошибок из-за своей вероятностной природы. В данной работе предлагается алгоритм сортировки массива целых чисел с использованием нейронной сети. Данный алгоритм представляет собой симбиоз нейронной сети и классических алгоритмов. Приводится структурная схема алгоритма, на которой представлено несколько составных частей: нейронная сеть для поиска минимального элемента входного вектора; часть системы, которая переставляет найденный минимальный элемент на место в сортированной части массива. Последняя часть системы реализована в форме классических алгоритмов, но может быть заменена вырожденным вариантом нейронной сети, в которой веса представляют варианты замены элементов массива. В работе была проведена проверка предлагаемого алгоритма. В результате из 10 000  тестов 248 оказались ошибочными, что соответствует 2,48 % ошибки. Приведены рассуждения о возможных причинах возникновения ошибок.
Ключевые слова: нейронная сеть, алгоритмы, сортировка, классификация, Matlab, вероятностные системы, обучение, вероятностные алгоритмы, персептрон

Список литературы
1. Introduction to algorithms / T. Cormen, C. Leiserson, R. Rivest, C. Stein. – 3rd ed. – Cambridge, MA: MIT Press, 2009. – 1328 p.

2. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. – М.: Вильямс, 2016. – 400 с.

3. Haykin S. Neural networks and learning machines. – 3rd ed. – New York: Pearson Education, 2009. – 938 p.

4. Bishop C. Pattern recognition and machine learning. – New York: Springer, 2007. – 729 p.

5. Richert W., Coelho L.P. Building machine learning systems with Python. – 2nd ed. – Birmingham, UK: Packt, 2015. – 290 p.

6. Mohri M., Rostamizadeh A., Talwalkar A. Foundations of machine learning. – Cambridge, MA: MIT Press, 2012. – 427 p.

7. Hastie T., Tibshirani R., Friedman J. The elements of statistical learning. – 2nd ed. – New York: Springer, 2009. – 764 p.

8. Ackley D.H., Hinton G.E., Sejnowski T.J. A learning algorithm for Boltzmann machines // Cognitive Science. – 1985. – Vol. 9. – P. 147–169.

9. Bahdanau D., Cho K., Bengio Y. Neural machine translation by jointly learning to align and translate // 3rd International Conference on Learning Representations ICLR’2015: conference paper. – San Diego, 2015. – P. 1–15.

10. Behnke S. Learning iterative image reconstruction in the neural abstraction pyramid // International Journal Computational Intelligence and Applications. – 2015. – Vol. 1 (4). – P. 427–438.

11. Gated feedback recurrent neural networks / J. Chung, Ç. Gülçehre, K. Cho, Y. Bengio // Proceedings of the 32nd International Conference on Machine Learning ICML’15. – Lille, France, 2015. – P. 2067–2075.

12. Deep generative image models using a Laplacian pyramid of adversarial networks / E. Denton, S. Chintala, A. Szlam, R. Fergus // NIPS Proceedings. – Montreal, Canada, 2015. – P. 1–9.

13. Frey B.J. Graphical models for machine learning and digital communication. – Cambridge, MA: MIT Press, 1998. – 195 p.

14. Goodfellow I.J., Courville A., Bengio Y. Scaling up spike-and-slab models for unsupervised feature learning // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2013. – Vol. 35 (8). – P. 1902–1914.

15. Block H.D. The Perceptron: a model for brain functioning // Reviews of Modern Physics. – 1962. – Vol. 34 (1). – P. 123–135.

 
Просмотров: 1036