Содержание
Ерофеева В. А. (СПбГУ) Оптимизация распределения целей между наблюдателями и
оценивание состояний с помощью циклического подхода 3
Кижаева Н. А. (СПбГУ) Динамическая модель процесса эволюции текстовых
документов 31
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯВИНФОРМАТИКЕ
Издается с 2005 года
ТОМ 14
Выпуск 1
Издательство С.-Петербургского университета
2 0 1 8
УДК 519.712
БКК 32.811.7
С82
Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин
Редакционная коллегия: Б. Т. Поляк (ИПУ РАН),
А. В. Соколов (ИПМИ КарНЦ РАН),
П. С. Щербаков (ИПУ РАН)
С82 Стохастическая оптимизация в информатике. Том 14 (Вып. 1) / Под ред. О. Н. Граничина — СПб.:
Издательство С.-Петербургского университета, 2018. — 50 с. ISSN 1992–2922
Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2–13 — в 2006–17 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск двенадцатого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2017–18 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №16-07-00890-а.
Издание предназначено для специалистов в области информатики, студентов старших курсов и аспирантов, обучающихся на специальностях, связанных с обработкой информации.
ББК 32.811.7
© Авторы статей, 2018
Оптимизация распределения целей между наблюдателями и оценивание состояний с помощью циклического подхода[1]
В. А. Ерофеева[2], аспирант
Санкт-Петербургский государственный университет victoria@grenka.net
Благодаря значительным успехам в развитии встроенных систем, компонентов сенсорики и средств беспроводной коммуникации сенсорные сети привлекли широкое внимание в различных областях практического применения. Трудность управления подобными распределенными системами заключается в наличии ряда неопределенностей, таких как ограниченная пропускная способность сети, получение зашумленных данных, необходимость в асинхронной передаче сообщений, энергоэффективность. В условиях неопределенностей хорошо зарекомендовали себя алгоритмы стохастической аппроксимации и техника линейных матричных неравенств, которые являются основными объектами исследования рассматриваемой статьи. В работе проанализирована возможность применения техники линейных матричных неравенств для оптимизации распределения объектов между наблюдателями. Кроме этого, для метода циклической поисковой стохастической аппроксимации получены свойства доставляемых им оценок при линейных ограничениях, а также описано применение метода для задачи отслеживания траекторий движущихся объектов.
Ключевые слова: линейные матричные неравенства,
стохастическая оптимизация, отслеживание параметров, нестационарный функционал,
мультиагентный подход, распределение заданий.
Работа
выполнена при поддержке РФФИ, проект № 16-07-00890.
Список литературы
[1] Dargie W., Poellabauer C. Fundamentals of wireless sensor networks: theory and practice. John Wiley & Sons, 2010.
[2] Hanif A., Mansoor A.B., Imran A.S. Deep multi-view correspondence for identity-aware multi-target tracking // In Proc. of 2017 International Conference on Digital Image Computing: Techniques and Applications (DICTA). 2017. P. 1–8.
[3] Thite A., Mishra A. Optimized multi-sensor multi-target tracking algorithm for air surveillance system // In Proc. of 2016 2nd International Conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics (AEEICB). 2016. P. 637–642.
[4]
Jia
B., Pham K.D., Blasch E., Shen D., Wang Z., Chen G.
Cooperative space object tracking using space-based optical sensors via consensus-based filters // IEEE Transactions on Aerospace and Electronic Systems. 2016. V. 52. No. 4. P. 1908–1936.
[5] Wei B., Nener B., Liu W., Ma L. Centralized multi-sensor multitarget tracking with labeled random finite sets // In Proc. of International Conference on Control, Automation and Information Sciences (ICCAIS). 2016. P. 82–87.
[6] Kalman R.E. et al. (1960). A new approach to linear filtering and prediction problems // Journal of basic Engineering. 1960. V. 82. No. 1. P. 35–45.
[7] Uhlmann J.K. Algorithms for multiple-target tracking // American Scientist. 1992. V. 80. №2. P. 128–141.
[8] Olfati-Saber R. Distributed kalman filtering for sensor networks // In Proc. of 46th IEEE Conference on Decision and Control. 2007. P. 5492–5498.
[9] Cattivelli F.S., Sayed A.H. Diffusion strategies for distributed Kalman filtering and smoothing // IEEE Transactions on automatic control. 2010. V. 55. No. 9. P. 2069–2084.
[10] Olfati-Saber R., Sandell N.F. Distributed tracking in sensor networks with limited sensing range // In Proc. of American Control Conference. 2008. P. 3157–3162.
[11] Petitti A., Di Paola D., Rizzo A., Cicirelli G. Consensus-based distributed estimation for target tracking in heterogeneous sensor networks // In Proc. of 50th IEEE Conference on Decision and Control and European Control Conference. 2011. P. 6648–6653.
[12] Giannini S., Petitti A., Di Paola D., Rizzo A. Consensus-based distributed target tracking with asynchronous measurements // In Proc. of 52th IEEE Conference on Decision and Control. 2013.
[13] Yang, W., Shi, H. Sensor selection schemes for consensus based distributed estimation over energy constrained wireless sensor networks // Neurocomputing. 2012. V. 87. P. 132–137.
[14] Граничин О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленинградского университета. 1989. Сер. 1. №1(4). С. 19–21.
[15] Граничин О.Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. C.
97–104.
[16] Поляк Б.Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. Т. 26. С. 126–133.
[17] Polyak B.T., Tsybakov A.B. On stochastic approximation with arbitrary noise (the KW case) / In: Topics in Nonparametric Estimation // Topics in Nonparametric Estimation. Adv. in Soviet Mathematics. Am. Math. Soc. 1992. No. 12. P. 107–113.
[18] Spall J.C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Transactions on Automatic Control. 1992. V. 37. No. 3. P. 332–341.
[19] Spall J.C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. 1997. V. 33. P. 109–112.
[20] Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. New York: Springer-Verlag, 2002.
[21]
Borkar
V.S. Stochastic Approximation. A Dynamical Systems Viewpoint. Cambridge
University Press, 2008.
[22] Granichin O., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // In Proc. of 48th IEEE Conference on Decision and Control. 2009. P. 5763–5767.
[23] Granichin O.N., Amelina N.O. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances // IEEE Transactions on Automatic Control. 2015. V. 60. No. 5. P. 1653–1658.
[24] Граничин О. Н. Поисковые алгоритмы стохастической аппроксимации с рандомизацией на входе // Автоматика и телемеханика. 2015. №5. С. 43–59.
[25] Spall J.C. Cyclic seesaw process for optimization and identification // Journal of optimization theory and applications. 2012. V. 154. No. 1. P. 187–208.
[26] Spall J.C. Identification for systems with binary subsystems // IEEE Transactions on Automatic Control. 2014. V. 59. No. 1. P. 3–17.
[27] Hernandez K., Spall J.C. Cyclic stochastic optimization with noisy function measurements // In: Proc. of American Control Conference. 2014. P. 5204–5209.
[28] Hernandez K. Cyclic stochastic optimization via arbitrary selection procedures for updating parameters // In: Proc. of 2016 Annual Conference on Information Science and Systems. 2016. P. 349–354.
[29] Hernandez K., Spall J.C. Asymptotic normality and efficiency analysis of the cyclic seesaw stochastic optimization algorithm // In: Proc. of American Control Conference. 2016. P. 7255–7260.
[30] Hernandez K. Cyclic stochastic optimization: generalizations, convergence, and applications in multi-agent systems. Ph.D. Thesis. 2017.
[31] Граничин О.Н., Ерофеева В.А. Циклическая стохастическая аппроксимация с возмущением на входе в задаче отслеживания параметров на основе мультиагентного алгоритма // Автоматика и телемеханика. 2018. №6.
[32] Амелина Н.О., Фрадков А.Л. Приближенный консенсус в стохастической динамической сети с неполной информацией и задержками в измерениях // Автоматика и телемеханика. 2012. №11. С.
6-29.
[33] Amelina N., Erofeeva V., Granichin O., Malkovskii N. Simultaneous perturbation stochastic approximation in decentralized load balancing problem // IFAC-PapersOnLine. 2015. V. 48. No. 11. P. 936–941.
[34] Amelina N., Fradkov A., Jiang Y., Vergados D. J. Approximate consensus in stochastic networks with application to load balancing // IEEE Transactions on Information Theory. 2015. V. 61. No. 4. P. 1739–1752.
[35] Botts C.H., Spall J.C., Newman A.J. Multi-agent surveillance and tracking using cyclic stochastic gradient // In: Proc. of American Control Conference. 2016. P. 270–275.
[36] Барабанов А.Е., Граничин О.Н. Оптимальный регулятор линейного объекта с ограниченной помехой // Автоматика и телемеханика. 1984. №5. C. 39–46.
[37] Dahleh M., Pearson J. l1-optimal feedback controllers for MIMO discrete-time systems //IEEE Transactions on Automatic Control. 1987. V. 32. No. 4. P. 314–322.
[38] Якубович В. А. Метод матричных неравенств в теории устойчивости нелинейных регулируемых систем. I. Абсолютная устойчивость вынужденных колебаний // Автоматика и телемеханика. 1964. Т. 25. №7. С. 1017–1029.
[39] Якубович В. А. Метод матричных неравенств в теории устойчивости нелинейных регулируемых систем. II // Автоматика и телемеханика. 1965. Т. 26. №4. С. 577–590.
[40] Boyd S., El Ghaoui L., Feron E., Balakrishnan V. Linear matrix inequalities in system and control theory. Siam, 1994. V. 15.
[41] Calafiore G., Polyak B. T. Stochastic algorithms for exact and approximate feasibility of robust LMIs //IEEE Transactions on Automatic Control. 2001. V. 46. No. 11. P. 1755–1759.
[42] Поляк Б. Т., Щербаков П. С. Робастная устойчивость и управление. М : Наука, 2002.
[43] Поляк Б. Т., Щербаков П. С. Техника D-разбиения при решении линейных матричных неравенств // Автоматика и телемеханика. 2006. №11. P. 159–174.
[44]
Polyak
B., Khlebnikov M., Shcherbakov P. An LMI approach to structured sparse feedback
design in linear control systems // In Proc.
of 2013 European Control Conference (ECC). 2013. P. 833–838.
[45] Поляк Б. Т., Хлебников М. В., Щербаков П. С. Управление линейными системами при внешних возмущениях: Техника линейных матричных неравенств. М.: ЛЕНАНД, 2014.
[46] Polyak B. T., Khlebnikov M. V., Shcherbakov P. S. Sparse feedback in linear control systems // Automation and Remote Control. 2014. V. 75. No. 12. P. 2099–2111.
[47] Железнов К. О., Хлебников М. В. Синтез обратной связи для линейной системы управления с возмущением на входах и выходах: робастная постановка // Проблемы управления. 2017. Т. 3. №0. С. 11–16.
[48] Slotani M. Tolerance regions for a multivariate normal population // Annals of the Institute of Statistical Mathematics. 1964. V. 16. No. 1. P. 135–153.
[49]
Поляк Б. Т., Хлебников М. В., Щербаков П. С.
Разреженная обратная связь в линейных системах управления // Автоматика и
телемеханика. 2014. №12. P. 13–27.
Динамическая модель процесса эволюции текстовых документов[3]
Н. А. Кижаева[4], аспирант
Санкт-Петербургский государственный университет natalia.kizhaeva@gmail.com
В статье предложен метод построения динамической модели текстовых документов. На основе предложенной динамической модели разработаны и обоснованы два метода классификации документов и их фрагментов. Первый метод основан на кластеризации периодограмм, второй использует кластеризацию с помощью расстояния, основанного на ядрах.
Ключевые слова: интеллектуальный
анализ текстов, динамическая модель, классификация, кластеризация.
Работа выполнена при поддержке РФФИ, проект № 17-51-53053.
Список литературы
[1] Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности — М.: Финансы и статистика, 1989, 607 с.
[2] Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — 1970.
[3] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов: статистические проблемы обучения — М.: Наука, 1974. — 416 с.
[4]
Rosenblatt
F. Principles of Neurodynamics. — New York: Spartan Press. — 1962. — 616 p.
[5] Фишер Р.А. Статистические методы для исследователей. М.: Госстатиздат, 1954, 267 с.
[6] Фомин В.Н.Математическая теория обучаемых опознающих систем — Л.: ЛГУ, 1976, 236 c.
[7]
Forgy
E.W. Cluster analysis of multivariate data - efficiency vs interpretability of
classifications // Biometrics. — 1965. — No. 21. — P. 768–769.
[8]
Fukunaga
K. Introduction to Statistical Pattern Recognition. — New York: Academic Press.
— 1972. — 618 p.
[9] Цыпкин Я.З. Адаптация и обучение в автоматических системах. — М.: Hаука. — 1968. — 400 с.
[10] Цыпкин Я.З. Основы теории обучающихся систем. — М.: Наука. — 1970. — 252 с.
[11]
Hartigan
J. A. Clustering Algorithms (Probability & Mathematical Statistics). — New
York: Wiley, 1975, 351 p.
[12] Hopfield J. Neurons with graded
response have collective computational properties like those of two-state
neurons // In:
Proc.
of the National Academy of Sciences. — 1984. — No. 81. — P. 3088–3092.
[13]
Vidyasagar
M. Randomized algorithms for robust controller synthesis using statistical
learning theory // Automatica. — 2001. — Vol. 37. — No. 10. — P. 1515–1528.
[14] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. Springer-Verlag: Heidelberg New York Dordrecht London. — 2015. — 251 p.
[15]
M.
Campi Classification with guaranteed probability of error // Machine learning.
— 2010. — Vol. 80. — No. 1. — P. 63–84.
[16]
Popkov
Yu. S., Dubnov Yu. A., Popkov A. Yu. Randomized machine learning: statement,
solution, applications // IEEE 8th International Conference on Intelligent
Systems (IS). — 2016. — P. 27–39.
[17] Поляк Б. Т., Хлебников М. В. Метод главных компонент: робастные версии // Автоматика и телемеханика. — 2017. — є 3. — С.
130–148.
[18]
Martin
J. H., Jurafsky D. Speech and language processing: An introduction to natural
language processing, computational linguistics, and speech recognition. —
Pearson/Prentice Hall, 2009.
[19] Шахтарин Б., Ковригин В.А. Методы спектрального оценивания случайных процессов. — Гелиос АРВ, 2005.
[20]
Dunn
J. C. Well-separated clusters and optimal fuzzy partitions // Journal of
cybernetics. — 1974. — Vol. 4. — No. 1. — P. 95–104.
[21]
Hubert
L., Schultz J. Quadratic assignment as a general data analysis strategy //
British journal of mathematical and statistical psychology. — 1976. — Vol. 29.
— No. 2. — P. 190–241.
[22]
Calinski
T., Harabasz J. A dendrite method for cluster analysis // Communications in
Statistics-theory and Methods. — 1974. — Vol. 3. — No. 1. — P. 1–27.
[23]
Hartigan
J. A. Clustering Algorithms (Probability & Mathematical Statistics). — New
York: Wiley, 1975, 351 p.
[24]
Krzanowski
W. J., Lai Y. T. A criterion for determining the number of groups in a data set
using sum-of-squares clustering // Biometrics. — 1988. — P. 23–34.
[25]
Sugar
C. A., James G. M. Finding the number of clusters in a dataset: An
information-theoretic approach // Journal of the American Statistical
Association. — 2003. — Vol. 98. — No. 463. — P. 750–763.
[26]
Gordon
A. D. Identifying genuine clusters in a classification // Computational
Statistics & Data Analysis. — 1994. — Vol. 18. — No. 5. — P. 561–581.
[27]
Dudoit
S., Fridlyand J. A prediction-based resampling method for estimating the number
of clusters in a dataset // Genome biology. — 2002. — Vol. 3. — No. 7. —
P.‘112–129.
[28]
Milligan
G. W., Cooper M. C. An examination of procedures for determining the number of
clusters in a data set // Psychometrika. — 1985. — Vol. 50. — No. 2. — P.
159–179.
[29] Садовничий В. А. Теория операторов. — 1986.
[30]
Schoenberg
I. J. Metric spaces and positive definite functions // Transactions of the
American Mathematical Society. — 1938. — Vol. 44. — No. 3. — P. 522–536.
[31]
Amelin
K., Granichin O., Kizhaeva N., Volkovich Z. Patterning of writing style
evolution by means of dynamic similarity // Pattern Recognition. — Vol 77. — P.
45–64.
[32]
Kizhaeva
N., Volkovich Z., Granichin O., Granichina O., Kiyaev V. Spectral profiling of
writing process // In: Proc. of the 2017 IEEE Conference on Control Technology
and Applications. — Coast, Hawaii, USA, 2017. — August 27–30. — P. 2063–2068.
ABSTRACTS
State Estimation and Task Distribution Optimization
in Sensor Networks Based on Cyclic Approach[5]
V. A. Erofeeva
St. Petersburg State University victoria@grenka.net
Key words: linear matrix inequalities,
stochastic optimization, parameter tracking, nonstationary functional,
multi-agent technologies, task distribution.
Due to significant advancements in embedded
systems, sensor devices and wireless communication technology, sensor networks
have attracted widespread attention in various areas of practical application.
Such networks are difficult to control because of uncertainties among which are
limited network throughput, measurement noise, asynchronous messaging, and
energy efficiency. Under uncertain conditions, the stochastic approximation
algorithms and linear matrix inequalities have proved to be very useful. In
this paper we propose an approach for solving the task distribution
optimization problem using linear matrix inequalities. Besides of that, we
generalize the cyclic stochastic approximation algorithm and obtain the
estimation properties. In addition, the cyclic stochastic approximation
algorithm is applied to the distributed state estimation problem.
Bibliogr.:
49 refs.
Dynamic Models of Text Documents [6]
N. A. Kizhaeva
St. Petersburg State University natalia.kizhaeva@gmail.com
Key words: text mining, classification
algorithms, clustering algorithmns.
A method for dynamic modeling of texts is
introduced. Based on the proposed model two classification algorithms of text
documents are designed. First classification rule is based on clustering of
text documents using periodograms of times series constructed for each
document. Second classification rule applies clustering with kernel based
distances.
Bibliogr.:
32 refs.