N	Оглавление	Страницы
1	Стохастическая оптимизация для обучения признаков без учителя Бояров А. А.	3-16
2	Вспомогательные алгоритмы для проблемы вершинной минимизации недетерминированных конечных автоматов Зубова М. А., Мельников Б. Ф.	17-29
3	О числе Фидлера и асимптотической скорости сходимости лапласиановых систем Мальковский Н. В.	30-35
4	Использование рандомизированных алгоритмов для идентификации параметров модели динамического объекта Понятский В.М.	36-44

Стохастическая оптимизация для обучения признаков без учителя

Бояров А. А.

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

a.boiarov@spbu.ru

Одной из важнейших задач машинного обучения является обучение глубокой иерархии признаков для других задач, что позволяет хорошо описать внутреннюю структуру данных, и значительно улучшает классификацию. В последнее время для этого активно применяются алгоритмы обучения признаков без учителя (unsupervised feature learning). Однако не все эти алгоритмы можно легко настроить. В данной работе рассматривается модифицированный с помощью стохастической оптимизации метод обучения признаков, основанный на методе K-средних. Полученный алгоритм представляет собой реализацию идеи online-обучения, позволяет добиться значительного прироста в скорости работы и является устойчив к помехам. В статье рассматривается успешный пример использования модифицированного метода в системе распознавания рукописных символов. Построенная система имеет тесную связь со сверточными нейронными сетями (convolutional neural networks).

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

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

[1] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning Data Mining, Inference and Prediction — Springer-Verlag. 2009. 763 P.

[2] Bishop C.M. Pattern Recognition and Machine Learning — Springer. 2006. 738 P.

[3] Bengio Y., Goodfellow I.J., Courville A. Deep Learning — Book in preparation for MIT Press. 2015. http://www.iro.umontreal.ca/ bengioy/dlbook.

[4] LeCun Y., Bengio Y., Hinton G. Deep Learning // Nature. 2015. Vol 521. P. 436–444.

[5] Krizhevsky A., Sutskever I., Hinton G. Imagenet classification with deep convolutional neural networks // Proc. Advances in Neural Information Processing Systems. 2012. Vol 25. P. 1090–1098.

[6] LeCun Y., Bottou L., Bengio Y., Haffner P. Gradient-based learning applied to document recognition // Proc. IEEE. 1998. Vol 86. P. 2278–2324.

[7] Taigman Y., Yang M., Ranzato M., Wolf L. DeepFace: closing the gap to human-level performance in face verification // Proc. Conference on Computer Vision and Pattern Recognition. 2014. P. 1701–1708.

[8] 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.

[9] Lloyd S. Least Square Quantization in PCM. Bell Telephone Laboratories Paper. 1957.

[10] Coates A., Carpenter B., Case C., Satheesh S., Suresh B., Wang T., Wu D.J., Ng A.Y. Text detection and character recognition in scene images with unsupervised feature learning // ICDAR. 2011. P. 440–445.

[11] Coates A., Ng A.Y. Learning feature representations with K-means // Neural Networks: Tricks of the Trade. LNCS. Springer. 2012. Vol. 7700. P. 561–580.

[12] Spall J.C. Introduction to Stochastic Search and Optimization — Wiley-Interscience. 2003. 618 P.

[13] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. №8. С. 52–63.

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

[15] Граничин О.Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. №2. С. 88–99.

[16] Digit Recognizer https://www.kaggle.com/c/digit-recognizer/data.

Вспомогательные алгоритмы для проблемы вершинной минимизации недетерминированных конечных автоматов

М. А. Зубова, аспирант

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

ma.zubova@gmail.com

Б. Ф. Мельников, профессор

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

bf-melnikov@yandex.ru

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

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

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

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

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

[3] Долгов В. Н., Софонова Н. В. О дугах конечных автоматов для описания алгоритмов построения Ватерлоо-подобных автоматов // Стохастическая оптимизация в информатике. 2015. Т. 11. №. 1. С. 65–76.

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

[5] Зубова М. А., Мельников Б. Ф. Об одном алгоритме построения универсального автомата Конвея // Вестник Воронежского государственного университета. Серия: Физика. Математика. 2012. № 1. C.135–137.

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

[7] Мельников Б. Ф., Мельникова Е. А. Некоторые эвристические алгоритмы в задаче вершинной минимизации недетерминированных конечных автоматов // Стохастическая оптимизация в информатике. 2013. Т. 9. №. 2. С. 73-87.

[8] Melnikov B. F., Tsyganov A. V., Bulychov O. I. A multi-heuristic algorithmic skeleton for hard combinatorial optimization problems // Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization. Sanya, Hainan. 2009. P.33–36.

[9] Melnikov B. F., Tsyganov A. V. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // Proceedings of 5th International Symposium on Parallel Architectures, Algorithms and Programming. Taipei, Taiwan. 2012. P.194–201.

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

[11] Melnikov B. Discrete optimization problems – some new heuristic approaches // 8th Int. Conf. on High Performance Computing and Grid. IEEE Comp. Soc. Press Ed. 2005. P.73–80.

[12] Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Systems. 2006. P.91–95.

[13] Мельников Б.Ф., Пивнева С.В., Рогова О.А. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике. 2010. Т. 6. №. 1. С. 74-82.

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

[15] Melnikov B., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean Journal of Computational and Applied Mathematics. 2002. Vol. 9. No. 2. P.475–485.

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

[17] Мельников Б. Ф., Мельникова А. А. Многоаспектная минимизация недетерминированных конечных автоматов (Часть I. Вспомогательные факты и алгоритмы) // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2011. №. 4. С.59–69.

[18] Мельников Б. Ф., Мельникова А. А. Многоаспектная минимизация недетерминированных конечных автоматов (Часть II. Основные алгоритмы) // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2012. №. 1. С.31–43.

[19] Кукеев М. В., Мельников Б. Ф. Некоторые подзадачи задачи вершинной минимизации недетерминированных конечных автоматов // Современные информационные технологии и ИТ-образование. 2011. №. 7. С. 995–1008.

[20] Мельников Б. Ф. Научим машину надежде? // Философские проблемы информационных технологий и киберпространства. 2013. №. 1. С.51–64.

О числе Фидлера и асимптотической скорости сходимости лапласиановых систем

Н. В. Мальковский, аспирант

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

malkovskynv@gmail.com

В этой статье приводится анализ асимптотической сходимости лапласиановых динамических систем, основанный на достаточно известных результатах из алгебры и алгебраической теории графов. Во многих статьях, рассматривающих применение лапласиановых систем, в стандартную оценку скорости сходимости входит так называемое число Фидлера – наименьшее по модулю (кроме нуля) собственное число соответствующей матрицы лапласиана. При подробном рассмотрении оказывается, что число Фидлера можно раскрыть для получение более точной оценки асимптотической сходимости в худшем случае. В итоге мы получаем, что число Фидлера прячет в себе скрытый множитель n^2, где n – размер системы.

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

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

[1] Ren W., Beard R. W., Atkins E. M. Information consensus in multivehicle cooperative control // IEEE Control Systems. Vol. 27. No. 2. PP. 71–82. 2007.

[2] Fax J. A., Murray R. M. Information flow and cooperative control of vehicle formations // IEEE Transactions on Automatic Control. Vol. 49. No. 9. PP. 1465–1476. 2004.

[3] Amelina N., Granichin O., Granichina O., Jiang Y. Differentiated consensuses in decentralized load balancing problem with randomized topology, noise, and delays // In: Proc. of the 53th Conference of Desision and Control. PP. 6969–6974. 2014.

[4] Boyd S., Ghosh A., Prabhakar B., Shah D. Randomized gossip algorithms // IEEE Transactions on Information Theory. Vol. 52. No. 6. PP. 2508–2530. 2006.

[5] Shah D. Gossip Algorithms. Now Publishers Inc, 2009.

[6] Rikos A. I., Charalambous T., . Hadjicostis C. N. Distributed weight balancing over digraphs // IEEE Transactions on Control of Network Systems. Vol. 1. No. 2. PP. 190–201. 2014.

[7] Haghighi R., Cheah C. C. Distributed average consensus based on structural weight-balanceability // IET Control Theory & Applications. Vol. 9. No. 2. PP. 176–183. 2014.

[8] Fiedler M. Algebraic connectivity of graphs // Czechoslovak Mathematical Journal. Vol. 23. No. 2. PP. 298–305. 1973.

[9] Olfati-Saber R., Murray R. M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. Vol. 49. No. 9. PP. 1520–1533. 2004.

[10] Чеботарев П. Ю., Агаев Р. П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика. № 3. С. 136–151. 2009.

[11] Fiedler M. Bounds for eigenvalues of doubly stochastic matrices // Linear Algebra and Its Applications. Vol. 5. No. 3. PP. 299–310. 1972.

[12] Mohar B., Alavi Y., Chartrand G., Oellermann O. The laplacian spectrum of graphs // Graph Theory, Combinatorics, and Applications. Vol. 2. PP. 871–898. 1991.

[13] Gharesifard B., Cort´es J. Distributed strategies for generating weight-balanced and doubly stochastic digraphs // European Journal of Control. Vol. 18. No. 6. PP. 539–557. 2012.

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

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

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

kbkedr@tula.net, pwmru@rambler.ru

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

Ключевые слова: динамический объект, модель, сигнал, помеха, оценка, коэффициент передачи.

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

[1] Сейдж Э.П., Мелса Дж.Л. Идентификация систем управления. – М.: Наука, 1974.

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

[3] Эйпховф П. Основы идентификации систем управления. – Мир, 1976.

[4] Льюнг Л. Идентификация систем. Теория для пользователя. – М.: Наука, 1991. – 432 с.

[5] Понятский В.М. Компьютерная технология идентификации методом фильтрации Калмана параметров линейной нестационарной модели динамического объекта // Труды международной конференции “Третьи Окуневские чтения” Ч.3. – СПб.:БГТУ, 2003. – С.146 – 150.

[6] Фатуев В.А., Юдаев А.В., Понятский В.М., Каргин А.В., Оберман М.С. Структурно-параметрическая идентификация многомерных нестационарных динамических систем // Материалы III Международной конференции “Идентификация систем и задачи управления”. – М.: ИПУ, 2004.

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

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

[9] Понятский В.М., Замотаев И.В., Киселев В.Б. Идентификация нестационарного динамического Объекта с использованием метода инвариантного погружения // Материалы VI Международной конференции “Идентификация систем и задачи управления”. – М.: ИПУ, 2007.