soi11_1

Содержание

Кривоконь Д.С. (СПбГУ) Система оценки положений движущихся объектов с использованием рандомизации                         3

Понятский В.М. (ГУП “КБП”, Тула) Использование рандомизированных алгоритмов обработки информационных сигналов при управлении летательным аппаратом               20

Проданов Т.П. (СПбГУ) Адаптивные рандомизированные алгоритмы выделения сообществ в графах                  29

Барковский Е. А. (ИПМИ КарНЦ РАН) Математические модели и ме­тоды оптимального управления Work-stealing деками в общей памяти        55

Долгов В. Н. (ТГУ), Софонова Н. В. (ТГУ) О дугах конечных автоматов для описания алгоритмов построения Ватерлоо-подобных автоматов    65

Калитеевский В. Н. (СПбГУ) Метод коммуникации в децентрализованной сети автономной группы мобильных роботов                   77

Сенов А. А. (СПбГУ) Улучшение оценки распределенного стохастиче­ского градиентного спуска через аппроксимацию функции потерь  103

 

Abstracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Krivokon D.S.  (SPbSU)  Randomization-based position estimation system for moving objects using camera motion. . . . . . . . . . .127

Ponyatskiy V. M. (KBP, Tula) Use of randomized algorithms for processing information signals in aircraft control      . . . . . . . . . . . . . .           128

Prodanov T.P. (SPbSU) Adaptive Randomized Algorithms for Community Detection in Graphs. . . . . . . . . . . . . . 129

Barkovsky   E.   A.   (Petrozavodsk)   Mathematical   models   and   methods   of optimal control of Work-stealing deques in shared memory. . . 130

Dolgov V. N. (TSU), Sofonova N. V.(TSU) Edges of finite automata as a tool for the description of algorithms for constructing Waterloo-like automata. . . . . . . . . . . .   131

Kaliteevskiy V. N. (SPbSU) Communication method for decentralized network of autonomous group of mobile robots. . . . . . . . . . . . . . 132

Senov A.  A.   (SPbSU)   Improving distributed  stochastic gradient descent estimate via loss function approximation. . . . . . . . . . . . . . 133

 

 

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 11

Выпуск 1

Издательство С.-Петербургского университета, 2 0 1 5

УДК 519.712 ВКК 32.811.7

С82

Ответственный редактор: д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия:           

Б. Т. Поляк (ипу ран),

А. В. Соколов  (ИПМИ КарНЦРАН),

П. С. Щербаков (ипу ран)

Стохастическая оптимизация в информатике. Том 11 (Вып. 1) / Под ред. О. Н. Граничина — СПб.: Издательство С.-Петербургского университета, 2014. — 160 с.

 ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2—10 — в 2006—14 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск десятого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2014 г. на математико-механическом факультете С.-Петербургского университе­та под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №13-07-00250-а.

Издание предназначено для специалистов в области информатики, сту­дентов старших курсов и аспирантов, обучающихся на специальностях, связанных с обработкой информации.

ББК 32.811.7

©   Авторы статей, 2015

 

Рандомизированные алгоритмы

Система оценки положений движущихся объектов с использованием рандомизации

Д. С. Кривоконь,

Санкт-Петербургский государственный университет

dmitry00@gmail.com

В статье предлагается система оценки положения движущегося объекта на основе использования видеокамеры. В ее основе лежат алгоритмы, кото­рые за счет рандомизации положения камеры, позволяют решать задачу в условиях, в которых стандартные алгоритмы неприменимы. Статья содер­жит описание системы, результаты ее тестирования, а также обоснование ал­горитмов.

Ключевые слова: рандомизация, оценка глубины точки, динамические систе­мы.

Список литературы

[1] Sturm P. Structure and motion for dynamic scenes the case of points moving in planes // In: Proc. of the European Conference on Computer Vision. 2002. PP. 507–509.

[2] Han M., Kanade T. Reconstruction of a scene with multiple linearly moving objects // In: Proc. of IEEE Conference on the Computer Vision and Pattern Recognition. 2000. PP. 542–549.

[3] Кривоконь Д.С. Методы оценки положения объекта при по­мощи случайных движений камеры // Компьютерные инстру­менты в образовании. 2014. Вып. 4. С. 46–54.

[4] Кривоконь Д.С., Вахитов А.Т. Рандомизация в задаче оцен­ки глубины точки при помощи одной камеры на основе идеи асимптотического наблюдателя // Стохастическая оптимизация в информатике. 2012. Т. 8. Вып. 2. С. 49-59.

[5] Krivokon D.S., Vakhitov A.T. Randomized algorithm for estimation of moving point position using single camera // Proc. of the IEEE 53rd Annual Conference on Decision and Control (CDC). 2014. PP. 5189-5194. .

[6] Кривоконъ Д.С, Вахитов А.Т., Граничин О.Н. Оценка поло­жения движущегося объекта на основе пробного возмущения камеры // Автоматика и телемеханика. 2015. №11 (в печати).

[7] Граничин О. Н. Об одной стохастической рекуррентной проце­дуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. Вып. 1(4). С. 19-21.

[8] Граничин О. Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

[9] Граничин О. Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Пробле­мы передачи информации. 1992. №2. С. 16-20.

[10] Spall J. С. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. PP. 332-341.

[11] Granichin O., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // 48th Conf. Decision Control. Shanghai. China. 2009. PP. 5763-5767.

[12] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. — Heidelberg New York Dordrecht London: Springer-Verlag, 2015.

[13] Vakhitov A., Granichin O., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // In: Proc. of the American Control Conference. 2010. PP. 4004-4009.


[14] Brown D. Decentering distortion of lenses // Photometric Engineering. 1966. PP. 444-462.

[15] Lowe D. G. Distinctive image features from scale-invariant keypoints. // International Journal of Computer Vision. 2004. Vol. 60. No. 2. PP. 91-110.

[16] Bay H., Tuytelaars Т., Luc Van Gool Surf: Speeded up robust features. // In: Computer Vision ECCV. 2006. PP. 404-417. Springer Berlin Heidelberg.

[17] Harris G, Stephens M. A combined corner and edge detector. // In: Alvey Vision Conference. 1988. Vol. 15. P. 50

[18] Fischler M. A., Bolles R. G Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography // Communications of the ACM. 1982. Vol. 24. No. 6. PP. 381-395

[19] Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. — Cambridge University Press. 2003.

[20] Граничин О. Н. Поисковые алгоритмы стохастической аппрок­симации с рандомизацией на входе // Автоматика и телемеха­ника. 2015. №5. С. 43-59.

[21] Granichin О. N., Amelina N. О. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances // IEEE Trans. Automat. Contr. 2015. V. 60. No. 6. PP. 1653-1658.

[22] Barron J., Fleet D, Beauchemin S. Performance of optical flow techniques // Int. J. Comput. Vision. 1994. V. 12. No. 1. PP. 43-77.

 

 

 

Использование рандомизированных алгоритмов обработки информационных сигналов при управлении летательным аппаратом

В. М. Понятский,

к. т. н., доцент АО “Конструкторское бюро приборостроения имени академика А.Г. Шипунова”,

Тула

kbkedr@tula.net, pwmru@rambler.ru

Рассматриваются системы управления летательным аппаратом, в ко­торых формирование управляющих воздействий осуществляется на осно­ве измеряемых информационных сигналов. Для фильтрации гауссовских шумов широко используются алгоритмы фильтрации Калмана. В работах О.Н. Граничина рассматривается использование рандомизированных алго­ритмов фильтрации случайного процесса при измерениях со смещением. В работе предлагаются непрерывный и дискретный алгоритмы обработки и экс­траполяции измеряемых координат, полученные в рамках методов фильтра­ции Калмана и предназначенные для использования в замкнутых системах управления. Проведенные исследования в среде Matlab и анализ полученных результатов показывают, что система с разработанным рандомизированным алгоритмом отрабатывает входной сигнал и не чувствительна к помехам, в отличие от системы с фильтром Калмана, в которой выходная координата отслеживает не только входной сигнал, но и низкочастотную составляющую помехи измерения.

Ключевые слова: фильтр Калмана, система, автоматическое сопровождение.

Список литературы

[1] Сейдж Э.П., Мелса Дж.Л. Теория оценивания и ее примене­ние в связи и управлении. – М.: Связь, 1976.

[2] Понятский   В.М.   Повышение   помехоустойчивости   системы управления вращающегося летательного аппарата // Проблемы совершенствования робототехнических и интеллектуаль­ных систем летательных аппаратов - М.: МАИ. 2005. С. 229-234.

[3] Понятский В.М., Петрушин В.В. Повышение динамической точности и помехоустойчивости в системах телеуправления // Изв. ТулГУ. Сер. “Проблемы проектирования и производства систем и комплексов”. — Тула: ТулГУ, 2003, Вып. 6. С. 333-335.

[4] Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. - М.: Наука, 2003. - 291 с.

 

[5] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. — Springer-Verlag: Heidelberg New York Dordrecht London. 2015. 251p.

[6] Понятский В.М. Способ повышения помехоустойчивости ро-бототехнической системы // Труды XII Международного се­минара “Супервычисления и математическое моделирование”. Под ред. Р. М. Шагалиева. - Саров: ФГУП “РФЯЦ-ВНИИЭФ”. 2010. С. 288-300.

[7] Понятский В.М. Исследование способов реализации адаптив­ной системы управления с фильтром Калмана // Стохастиче­ская оптимизация в информатике. 2008. Вып. 4. С. 186-200.

 

 

Адаптивные рандомизированные алгоритмы выделения сообществ в графах

Т.П.Проданов

Санкт-Петербургский Государственный Университет

timofey.prodanov@gmail.com

Последние семнадцать лет активно развивается изучение сложных сетей и находит большое применение выделение тесно связанных групп узлов, или сообществ, в сложных сетях.

Эффективными оказались рандомизированные алгоритмы выделения сооб­ществ, однако не существует набора параметров, при котором эти алгорит­мы давали бы хороший результат на всех сложных сетях. Для решения этой проблемы в статье описывается применение алгоритма одновременно возму­щаемой стохастической аппроксимации к рандомизированным алгоритмам для создания приспосабливающихся к входным данным адаптивных моди­фикаций. Целью является создание алгоритмов, дающих хорошие значения на большем количестве сложных сетей.

Ключевые слова: выделение сообществ, сложные сети, стохастическая ап­проксимация.

Список литературы

[1] Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8:128–140, 1741.

[2] Max Weber. Economy and society: An outline of interpretive sociology, volume 1. Univ of California Press, 1978.

[3] Agner Krarup Erlang. Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. Elektrotkeknikeren, 13:5–13, 1917.

[4] Cristopher Moore and Mark EJ Newman. Epidemics and percolation in small-world networks. Physical Review E, 61(5):5678, 2000.

[5] Jing Zhao, Hong Yu, Jianhua Luo, ZW Cao, and Yixue Li. Complex networks theory for analyzing metabolic networks. Chinese Science Bulletin, 51(13):1529–1537, 2006.

[6] Wang Hong, Wang Zhao-wen, Li Jian-bo, and Qiu-hong Wei. Criminal behavior analysis based on complex networks theory. In IT in Medicine & Education, 2009. ITIME’09. IEEE International Symposium on, volume 1, pages 951–955. IEEE, 2009.

[7] John Scott. Social network analysis. Sage, 2012.

[8] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. In ACM SIGCOMM Computer Communication Review, volume 29, pages 251–262. ACM, 1999.

[9] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the web. Computer networks, 33(1):309–320, 2000.

[10] Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D-U Hwang. Complex networks: Structure and dynamics. Physics reports, 424(4):175–308, 2006.

[11] Math¨aus Dejori, Anton Schwaighofer, Volker Tresp, and Martin Stetter. Mining functional modules in genetic networks with decomposable graphical models. Omics: a journal of integrative biology, 8(2):176–188, 2004.

[12] Michael Ovelg¨onne and Andreas Geyer-Schulz. Cluster cores and modularity maximization. In Data Mining Workshops (ICDMW), 2010 IEEE International Conference on, pages 1204–1213. IEEE, 2010.

[13] Michael Ovelg¨onne and Andreas Geyer-Schulz. An ensemble learning strategy for graph clustering. Graph Partitioning and Graph Clustering, 588:187, 2012.


[14] Mark E. J. Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, Feb 2004.

[15] Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. Knowledge and Data Engineering, IEEE Transactions on, 20(2):172–188, 2008.

[16] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400–407, 1951.

[17] Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. The Annals of Mathematical Statistics, 23(3):462–466, 1952.

[18] Julius R Blum. Multidimensional stochastic approximation methods. The Annals of Mathematical Statistics, pages 737–744, 1954.

[19] Олег Николаевич Граничин. Об одной стохастической рекур­рентной процедуре при зависимых помехах в наблюдении, ис­пользующей на входе пробные возмущения. Вестник Ленингр. ун-та, сер, 1:19–21, 1989.

[20] Борис Теодорович Поляк и Александр Борисович Цыбаков. Оптимальные порядки точности поисковых алгоритмов сто­хастической оптимизации. Проблемы передачи информации, 26(2):45–53, 1990.

[21] James C Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3):332–341, 1992.

[22] James C. Spall. Introduction to stochastic search and optimization: estimation, simulation, and control, volume 65. John Wiley & Sons, 2005.

[23] Boris T. Polyak. Introduction to optimization. Optimization Software New York, 1987.


[24] Harold J Kushner and George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.

[25] Vivek S Borkar et al. Stochastic approximation. Cambridge Books, 2008.

[26] Oleg Granichin and Natalia Amelina. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances. IEEE Transactions on Automatic Control, 60(6):1653–1658, 2015.

 

 

Дискретные системы

Математические модели и методы оптимального управления Work-stealing деками в общей памяти

Е. А. Барковский

barkevgen@gmail.com

Институт прикладных математических исследований Карельского научного центра Российской академии наук

В статье предлагаются математические модели и решаются задачи опти­мального разделения общей памяти для work-stealing деков и поиска опти­мального количества элементов для “кражи”. Операции, производимые с де­ками, имеют вероятностные характеристики и, наряду с последовательным, возможно и параллельное выполнение операций.

Ключевые слова: work-stealing, деки, структуры данных, марковские цепи,

случайные блуждания.

 

Список литературы

[1] Blumofe R.D., Leiserson C.E. Scheduling multithreaded computations by work stealing // Journal of the ACM. 1999. No. 46. P. 720–748.

[2] Herlihy M., Shavit N. The Art of Multiprocessor Programming. Elsevier. 2008.

[3] Knuth D. The Art of Computer Programming. Vol. 1. Addison-Wesley. 2001.

[4] Hendler D., Shavit N. Non-blocking Steal-half Work Queues // The Twenty-first Annual ACM Symposium on Principles of Distributed Computing. 2002. P. 280–289.

[5] Sokolov A.V., Drac A.V. The Linked List Representation of n LIFO-stacks and/or FIFO-queues in The Single-level Memory // Information Processing Letters. 2013. Vol. 13. No. 19–21. P. 832– 835.

[6] Аксенова Е.А., Лазутина А.А., Соколов А.В. Об оптималь­ных методах представления динамических структур данных // Обозрение прикладной и промышленной математики. 2003. Vol. 10. No. 2. P. 375–376.

[7] Hendler D., Lev Y., Moir M., Shavit N. A Dynamic-Sized Nonblocking Work Stealing Deque // Distributed Computing. Special issue: DISC 04. 2006. Vol. 18. No. 3. P. 189–207.

[8] Mitzenmacher M. Analyses of Load Stealing Models Based on Differential Equations // 10th ACM Symposium on Parallel Algorithms and Architectures. 1998. P. 212–221.

[9] Chase D., Lev Y. Dynamic Circular Work-Stealing Deque // 17th ACM Symposium on Parallelism in Algorithms and Architectures. 2005. P. 21–28.

[10] Aksenova E.A., Lazutina A.A., Sokolov A.V. Study of a Non-Markovian Stack Management Model in a Two-Level Memory // Programming and Computer Software. 2004. Vol. 30. No. 1. P. 25– 33.


[11] Aksenova E.A., Lazutina A.A., Sokolov A.V. The optimal implementation of two FIFO-queues in single-level memory // Applied Mathematics. 2011. Vol. 2. No. 10. P. 1297-1302.

[12] Соколов А.В., Драц А.В. Моделирование некоторых методов представления n FIFO очередей в памяти одного уровня // Эв­ристические алгоритмы и распределенные вычисления. 2014. Vol. 1. No. 1. P. 40-52.

[13]  Калачев А.В. Многоядерные процессоры. — М.: Бином. 2010.

[14] Wimmer M., Cederman D., Traff J.L., Tsigas P. Work-stealing with Configurable Scheduling Strategies // 18th ACM Symposium on Principles & Practice of Parallel Programming. 2013. P. 315– 316.

 

О дугах конечных автоматов для описания алгоритмов построения Ватерлоо-подобных автоматов

В. Н. Долгов, аспирант

Тольяттинский государственный университет

terenga74@mail.ru

Н. В. Софонова, аспирант

Тольяттинский государственный университет

natashamilkova@yandex.ru

Алгоритмы минимизации недетерминированных конечных автоматов, как известно, усложняет существование для некоторых автоматов конструк­ций как из примера найденного Камедой и Вайнером и названного Ватерлоо. До применения практических алгоритмов вершинной минимизации недетер­минированных конечных автоматов на основе автомата Ватерлоо, а также т.н. полного автомата для соответствующего языка, желательно строить по­добную конструкцию автоматически. В настоящей статье рассматривается необходимое для этого построения сравнение дуг полного автомата с дугами универсального автомата и с дугами базисного автомата.

Ключевые слова: недетерминированные конечные автоматы, алгоритмы ми­нимизации, универсальный автомат, базисный автомат, полный автомат.

Список литературы

[1] Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics. 2002. Vol. 9. №. 1. P. 131–150.

[2] Долгов В.Н., Мельников Б.Ф. Построение универсального ко­нечного автомата. I. От теории к практическим алгоритмам // Вестник Воронежского государственного университета. Серия: Физика. Математика. 2013. №. 2. C. 173–181.

[3] Melnikov B., Melnikova A. Some more on the basis finite automaton // Acta Informatica, Univ. Sapientiae. 2013. Vol. 5. №. 2 P. 227–244.

[4] Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press. 2008. P. 457–504.

[5] Jiang T., Ravikumar B. Minimal NFA problems are hard // SIAM J. Comput. 1993. Vol. 22. No. 6. P. 1117–1141.

[6] Melnikov B. Once more about the state-minimization of the nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. 2000. Vol. 7. No. 3. P. 655–662.

[7] Pol´ak L. Minimalizations of NFA using the universal automaton // Int. J. Found. Comput. Sci. 2005. Vol. 16. No. 5. P. 999–1010.

[8] Geldenhuys J., van der Merwe B., van Zijl L. Reducing nonde-terministic finite automata with SAT solvers // Springer. Finite-State Methods and Natural Language Processing. Lecture Notes in Computer Science. 2010. Vol. 6062. P. 81–92.


[9] Yo-Sub Han. State elimination heuristics for short regular expressions // Fundamenta Informaticae. 2013. Vol. 128. P. 445-462.

[10] Kameda Т., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Trans. on Comp. 1970. Vol. 19. No. 7. P. 617-627.

[11] Долгов В. Н., Мельников Б. Ф. Об алгоритмах автоматического построения Ватерлоо-подобных конечных автоматов на основе полных автоматов // Эвристические алгоритмы и распреде­ленные вычисления. 2014. Vol 1. No. 4. C. 24-45.

[12] Melnikov В. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol 104. No. 3. P. 267-283.

[13] Мельников Б. Ф. О зв¨ездной высоте регулярного языка. Часть I: Основные определения // Эвристические алгоритмы и рас­предел¨енные вычисления. 2014. Т. 1. №. 1 C. 74-87.

[14] Мельников Б. Ф. Недетерминированные конечные автоматы. — Тольятти: Изд-во ТГУ. 2009. 160 с.

 

 

Мультиагентные системы

Метод коммуникации в децентрализованной сети автономной группы мобильных роботов

В. Н. Калитеевский

Санкт-Петербургский государственный университет

vkalit@gmail.com

В статье рассматривается задача сохранения целостности данных в децен­трализованной сети автономных мобильных роботов, а также программно-аппаратная возможность реализации такой сети. Для коллективного хране­ния информации в группе мобильных роботов предлагается использовать алгоритмы подсчета контрольных сумм и балансировки загрузки вычисли­тельных узлов. Для программной реализации передачи данных применяются мультиагентные технологии. В качестве мобильного робота рассматривается сверхлегкий беспилотный летательный аппарат (БПЛА).

Ключевые слова: мультиагентные системы, групповое взаимодействие, ба­лансировка загрузки вычислительных узлов, подсчет контрольных сумм, средства связи, архитектура мобильного робота.

Список литературы

[1] Сечин А.Ю., Дракин М.А., Киселева А.С. Беспилотный ле­тательный аппарат: применение в целях аэрофотосъемки для картографирования. — М.: “Ракурс”. 2011.

[2] Howard A., Smith В., Egerstedt M. Realization of the sensor web concept for Earth science using mobile robotic platforms // Aerospace Conference. 2007. IEEE. PP. 1-6.

[3] Амелин К.С. Легкий беспилотный летательный аппарат для автономной группы // Стохастическая оптимизация в инфор­матике. №6. C. 117-126.

[4] Chao H. Cooperative Remote Sensing And Actuation Using Networked Unmanned Vehicles. — Diss. Џ Utah State University. 2010.

[5] Рыжова Т.С. Система управления коллективом мобильных ро­ботов // Мехатроника, автоматизация, управление. №4. С. 45-50. 2014.

[6] Vasarhelyi G., Viragh Cs., Somorjai G., Tarcai N., Nepusz Т., Vicsek T. Outdoor flocking and formation flight with autonomous aerial robots // IROS c. 3866-3873. 2014.

[7] Юревич Е.И. Управление роботами и робототехническими си­стемами. — СПб.: Изд. СПбГПУ. 2001.

[8] Vasarhelyi G., Viragh Cs., Abel D., Tarcai N., Nagy M., Vicsek T. Varkonyi P Patterns, transitions and the role of leaders in the collective dynamics of a simple robotic flock // Journal of Statistical Mechanics: Theory and Experiment. P04010. 2011.

[9] Каляев И.А., Шеремет И.А. Военная робототехника: выбор пути // Мехатроника, автоматизация, управление. 2008. №2. C. 32-34.

[10] Скобелев П.О., Царев А.В. Сетецентрический подход к созда­нию больших мультиагентных систем для адаптивного управ­ления ресурсами в реальном времен // Материалы межд. науч­но - практической мультиконференции “Управление большими системами” Москва, 14-16 ноября c. 263-267. 2011.

[11] Амелин К.С, Граничин О.Н. Мультиагентное сетевое управле­ние группой легких БПЛА. — Нейрокомпьютеры: разработка, применение. №6. C. 64-72. 2011.

[12] Тюшев К.И. Мультиагентные технологии для построения RAID-подобных распределенных систем хранения данных. — “СПИСОК-2014”. СПб. C. 477-481. 2014.

[13] Digi International [Official website]. http://www.digi.com/

[14] Amelin К., Amelina N., Granichin O., Putov V. Task distribution algorithm for the cooperating group of light autonomous unmanned aerial vehicles // In: Proc. of the 2nd IFAC Workshop on Research, Education and Development of Unmanned Aerial Systems, RED-UAS, Compiegne, France, November 20-22, 2013. P. 152-155.

[15] Амелин К.С, Антал Е.И., Васильев В.И., Амелина И.О. Адаптивное управление автономной группой беспилотных ле­тательных аппаратов. — Стохастическая оптимизация в ин­форматике. №5. C. 157-166. 2009.


[16] KQML specifications [Electronic resource]. http://www.csee. umbc.edu/csee/research/kqml

[17] FIPA specifications [Electronic resource]. http://www.fipa.org/ specs

[18] JADE documentation [Electronic resource]. http://jade.tilab. com/doc/programmersguide.pdf

[19] Raspberry Pi [Official website]. http://www.raspberrypi.org/

[20] RAID specifications [Electronic resource]. http://www.snia.org/ tech_activities/ standards/curr_standards/ddf

[21] Amelina N., Fradkov A., Vergados D., Jiang Y. Approximate Consensus in Stochastic Networks with Application to Load Balancing. — IEEE Transactions on Information Theory. April 2015. Vol. 61. Issue 4. PP. 1739-1752. 2015.

 

Улучшение оценки распределенного стохастического градиентного спуска через аппроксимацию функции потерь

А. А. Сенов, аспирант

Санкт-Петербургский государственный университет

alexander.senov@gmail.com

Проблемы обучения и оптимизации в контексте больших объемов дан­ных в настоящее время играют важную роль. К сожалению, даже методы параллельной и онлайн оптимизации не справляются с обработкой большие объемов данных из-за временных и технических ограничений. В этом слу­чае распределенные методы оптимизации могут быть единственным решени­ем проблемы. В статье рассмотрены некоторые современные методы распре­деленной оптимизации и исследован частный случай задачи оптимизации с разделимой стохастической квадратичной функцией потерь, предложены два новых алгоритма распределенной оптимизации, развивающие работы других авторов. Преимущества алгоритмов продемонстрированы экспериментально.

Ключевые слова: стохастическая оптимизация, оценка параметров, парал­лельные вычисления, распределенные вычисления, распределенная оптими­зация, взвешенный метод наименьших квадратов.

Список литературы

[1] Boyd S. Global optimization in control system analysis and design // Control and Dynamic Systems V53: High Performance Systems Techniques and Applications: Advances in Theory and Applications. 2012. Vol. 53.

[2] Bottou L. Online learning and stochastic approximations On-line learning in neural networks. 1998. Vol. 17. No. 9. 142 p.

[3] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms In Automatic Control And Data Mining. — Springer-Verlag: Heidelberg, New York, Dordrecht, London. 2015. 251p.

[4] Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. — М.: Наука. 2003. 293 с.

[5] Boyd S., Parikh N., Chu E., Peleato В., Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers // Foundations and Trends in Machine Learning. 2011. Vol. 3. No. 1. pp. 1-122.

[6] Поляк Б.Т. Введение в оптимизацию. — М.: Наука. 1983. 384 с.

[7] Boyd S., Vandenberghe L. Convex Optimization. — Cambridge university press. 2004.

[8] Нестеров Ю.Е. Введение в выпуклую оптимизацию. — М.: МЦНМО. 2010. 274 c.

[9] Cauchy A. Methode generale pour la resolution des systemes d’equations simultanees // Comp. Rend. Sci. Paris. 1847. Vol. 25. pp. 536-538.

[10] Davidon W.C. New least-square algorithms // Journal of Optimization Theory and Applications. 1976. Vol. 18. No. 2. pp. 187-197.

[11] Yann L.C., Bottou L. Large scale online learning // Advances in neural information processing systems. 2004. Vol. 16. 217. p.

[12] Bertsekas D. P. Parallel and Distributed Computation: Numerical Methods. — Athena Scientific. 1997.

[13] Chu C, Kim S.K., Lin Y.A., Yu Y., Bradski G., Ng A.Y., Olukotun K. Map-reduce for machine learning on multicore // Advances in neural information processing systems. 2007. Vol. 19.

[14] Zinkevich M., Weimer M., Li L., Smola A.J. Parallelized stochastic gradient descent // In: Advances in Neural Information Processing Systems. 2010. pp. 2595-2603.

[15] Dean J., Sanjay G. Mapreduce: simplified data processing on large clusters // In: OSDI’04, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation. 2004. USENIX Association. pp. 10-10.

[16] Mann G., McDonald R., Mohri M., Silberman N., Walker D. Efficient large-scale distributed training of conditional maximum entropy models // In: Advances in Neural Information Processing Systems. 2009. Vol. 22. pp. 1231-1239.

[17] Dekel O., Gilad-Bachrach R., Shamir R., Xiao L. Optimal distributed online prediction using mini-batches // The Journal of Machine Learning Research. 2002. Vol. 13. No. 1. pp. 165-202.

[18] White H. A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity // Econometrica: Journal of the Econometric Society. 1980. pp. 817-838.

[19] Senov A., Amelin K., Amelina N., Granichin O. Exact confidence regions for linear regression parameter under external arbitrary noise // In: Proc. of the 2014 American Control Conference (ACC). 2014. Portland, USA, 4-6 June. pp. 5097-5102.

[20] Сенов А.А., Граничин О.Н. Идентификация параметров ли­нейной регрессии при произвольных внешних помехах в на­блюдениях // В сб. трудов XII Всероссийское совещание по проблемам управления (ВСПУ-2014). 2014. С. 2708–2719.

 

 

 

Научное    издание

Стохастическая оптимизация в информатике

Том 11

Выпуск 1

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой

Оригинал-макет О. Н. Граничина

Подписано в печать 01.06.15. Формат 60 х 84/16-

Бумага офсетная. Печать офсетная.

Усл. печ. л. 10,0. Тираж 100 экз.

Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

Тел. (812) 328-96-17; факс (812) 328-44-22

E-mail: editor@unipress.ru

www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328-77-63, 325-31-76

E-mail: post@unipress.ru

Типография Издательства СПбГУ

199061, С.-Петербург, Средний пр., 41