Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 28, № 3 (2021)
Скачать выпуск PDF

Algorithms 

220-233 53
Аннотация

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

Так как этот подход в литературе применяется для нахождения субоптимального синтеза в задачах оптимального управления с квадратичным функционалом с формально линейными системами, где все матрицы коэффициентов в дифференциальных уравнениях и в критерии могут содержать переменные состояния, то на конечном интервале времени здесь появляется необходимость решения усложненного матричного дифференциального уравнения Риккати, с матрицами коэффициентов зависящими от состояния. Это обстоятельство вследствие нелинейности системы, по сравнению с алгоритмом Калмана для линейно-квадратичных задач, значительно увеличивает количество вычислений для получения коэффициентов матрицы коэффициентов усиления в обратной связи и для получения синтеза с заданной точностью. Предложенный в работе алгоритм построения синтеза строится с помощью принципа расширения, предложенного В. Ф. Кротовым и развитого В. И. Гурманом, и позволяет не только расширить сферу использования подхода SDRE на нелинейные задачи управления с ограничениями на управление в виде замкнутых неравенств, но и предложить более эффективный вычислительный алгоритм нахождения матрицы коэффициентов усиления обратной связи в задачах управления на конечном интервале. В работе устанавливается корректность применения принципа расширения с помощью введения аналогов множителей Лагранжа, зависящих от состояния и времени, а также выводится формула субоптимального значения критерия качества. Приведенные теоретические результаты иллюстрируются на расчетах субоптимальных обратных связей в задачах управления трехсекторными экономическими системами.

234-237 46
Аннотация

В данной статье описывается алгоритм получения неотрицательного базисного решения системы линейных алгебраических уравнений. Эта задача, в частности, является наиболее трудоемким этапом знаменитого симплекс-метода решения задач линейного программирования, хотя бесспорно представляет и самостоятельный интерес. В отличии от метода искусственного базиса Ордена, применяемого в классическом симплекс-методе, предлагаемый алгоритм не использует искусственных переменных и экономно расходует вычислительные ресурсы.

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

Приводятся два правила выбора разрешающего элемента. Более примитивное из них допускает неоднозначность выбора и не исключает зацикливания (но в очень редких случаях). Использование второго правила гарантирует отсутствие зацикливания.

Theory of Computing 

238-249 97
Аннотация

В работе рассматриваются методы оценивания устойчивости с помощью функций Ляпунова, применяемые для нелинейных полиномиальных систем управления. Для оценивания устойчивости используется аппарат метода базисов Грёбнера. Приводится описание метода базисов Грёбнера. Для применения метода канонические соотношении нелинейной системы аппроксимируются полиномами компонент векторов состоянии и управления. Для вычисления базиса Грёбнера применяется алгоритм Бухбергера, который реализован в программах символьных вычислений для решения систем нелинейных полиномиальных уравнений. Рассматривается использование базиса Грёбнера при нахождения решений нелинейной системы полиномиальных уравнений аналогично применению метода Гаусса для решения системы линейных уравнений. Определяются равновесные состояния нелинейной полиномиальной системы как решения нелинейной системы полиномиальных уравнений. Приводится пример определения равновесных состояний нелинейной полиномиальной системы с использованием метода базисов Грёбнера. Приводится пример нахождения критических точек нелинейной полиномиальной системы с использованием метода базисов Грёбнера и прикладного программного обеспечения Wolfram Mathematica. При использовании прикладного программного обеспечения Wolfram Mathematica применяется функция определения редуцированного базиса Грёбнера. Рассматривается применение метода базиса Грёбнера для оценивания области притяжения нелинейной динамической системы относительно точки равновесия. Для определения скалярного потенциала векторное поле динамической системы декомпозируется на градиентную и вихревую компоненты. По градиентному компоненту скалярный потенциал и функция Ляпунова в полиномиальной форме определяются на основе применения оператора гомотопии. Рассмотрено использование базисов Грёбнера при градиентном методе нахождения функции Ляпунова нелинейной динамической системы. Рассмотрено согласование сигналов ввода-вывода системы на основе построения базисов Грёбнера.

Theory of Data 

250-259 37
Аннотация

В статье сравниваются характеристики уровней символов, слов и ритма для верификации авторства художественных текстов 19-21-го веков. Корпуса текстов содержат фрагменты романов, каждый фрагмент имеет размер около 50 000 знаков. Для каждого автора приводится 40 фрагментов. Рассматриваются по 20 авторов, писавших на английском, русском, французском языках, и 8 испаноязычных авторов.

Авторы статьи используют существующие алгоритмы для вычисления популярных в современной компьютерной лингвистике низкоуровневых характеристик и распространённых в художественной литературе ритмических характеристик. Низкоуровневые характеристики включают в себя n-граммы слов, частоты встречаемости букв и знаков пунктуации, среднюю длину слова и предложения и т. д. Ритмические характеристики основаны на лексико-грамматических средствах: анафоре, эпифоре, симплоке, апозиопезе, эпаналепсисе, анадиплозисе, диакопе, эпизевксисе, хиазме, многосоюзие, повторяющихся восклицательных и вопросительных предложениях. Данные характеристики включают в себя частоты появления отдельных ритмических средств на 100 предложений, количество уникальных слов в аспектах ритма, доли существительных, прилагательных, наречий и глаголов в аспектах ритма. Верификация авторов рассматривается как задача бинарной классификации: принадлежит текст конкретному автору или нет. В качестве алгоритмов классификации рассматриваются AdaBoost и нейросеть со слоем LSTM. Эксперименты демонстрируют эффективность ритмических характеристик при верификации конкретных авторов и превосходство комбинаций типов характеристик над отдельными типами характеристик в среднем. Лучшее значение точности, полноты и F-меры для классификатора AdaBoost превышает 90%, когда комбинируются все три типа характеристик.

260-279 38
Аннотация

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

Подсчёт всех стилометрических характеристик был выполнен автоматически с помощью программы ProseRhythmDetector. Такой подход позволил провести анализ произведений большого объёма и многих писателей одновременно. В ходе работы каждому тексту были сопоставлены векторы стилометрических характеристик уровня символов, слов и структуры. При проведении экспериментов наборы параметров этих трёх уровней были скомбинированы между собой всеми возможными способами. Полученные векторы стилометрических характеристик были поданы на вход различным классификаторам для выполнения верификации и выявления наиболее подходящего классификатора для решения поставленной задачи. Лучшие результаты были получены с помощью классификатора AdaBoost. Средняя F-мера для всех языков оказалась более 92%. Детальные оценки качества верификации приведены для каждого автора и проанализированы. Использование высокоуровневых стилометрических характеристик, в частности, частоты использования N-грамм POS-тегов открывает перспективу более детального анализа стиля того или иного автора. Результаты экспериментов показывают, что при соединении характеристик уровня структуры с характеристиками уровня слов и/или символов получаются наиболее точные результаты верификации авторства для художественных текстов на русском, английском и французском языках. Дополнительно авторам удалось сделать вывод о разной степени влияния стилометрических характеристик на качество верификации авторства для различных языков.

280-291 48
Аннотация

Статья посвящена анализу ритма текстов различных жанров: художественных романов, рекламы, научных статей, отзывов, твитов и политических статей. Авторы выделили в текстах лексико-грамматические средства: анафору, эпифору, диакопу, апозиопезу и т. п., которые являются маркерами ритма текста. На их основе были подсчитаны статистические характеристики, описывающие количественно и структурно данные ритмические средства.

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

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

292-311 43
Аннотация

Известно, что в задачах обработки естественного языка представление текстов векторами фиксированной длины с использованием word-embedding моделей оправдано в тех случаях, когда векторизуемые тексты являются короткими. Чем сравниваемые тексты длиннее, тем подход работает хуже. Такая ситуация обусловлена тем, что при использовании word-embedding моделей происходит потеря информации при преобразовании векторных представлений слов, составляющих текст, в векторное представление всего текста, имеющее обычно ту же размерность, что и вектор отдельного слова.

В настоящей работе предлагается альтернативный способ использования предобученных word-embedding моделей для векторизации текстов. Суть предлагаемого способа заключается в объединении семантически близких элементов словаря имеющегося корпуса текстов путем кластеризации их (элементов словаря) эмбеддингов, в результате чего формируется новый словарь размером меньше исходного, каждый элемент которого соответствует одному кластеру. Исходный корпус текстов переформулируется в терминах этого нового словаря, после чего на переформулированных текстах выполняется векторизация одним из словарных подходов (в работе применялся TF-IDF). Полученное векторное представление текста дополнительно может обогащаться с использованием векторов слов исходного словаря, полученных путем уменьшения размерности их эмбеддингов по каждому кластеру.

В работе описана серия экспериментов по определению оптимальных параметров предлагаемого подхода; для задачи ранжирования текстов приведено сравнение подхода с другими способами векторизации – усреднением эмбеддингов слов со взвешиванием по TF-IDF и без взвешивания, а также с векторизацией на основе TF-IDF коэффициентов.

Erratum 

312-313 37
Аннотация

В статье В.В. Васильчикова «Параллельный алгоритм решения задачи об изоморфизме графов» (Моделирование и анализ информационных систем, том 27, №1, с. 86–94, 2020; https://doi.org/10.18255/1818-1015-2020-1-86-94) при вёрстке была допущена опечатка. В таблице 1 в последнем столбце строки «Степень графа» должно быть значение 3000 (вместо 300). Исправленная «Таблица 1» приводится ниже. Редакция приносит извинения за доставленные неудобства.

314-316 36
Аннотация

В статье Ю. В. Косолапова «Об обнаружении эксплуатации уязвимостей, приводящей к запуску вредоносного кода» (Моделирование и анализ информационных систем, том 27, №2, с. 138–151, 2020; https://doi.org/10.18255/1818-1015-2020-2-138-151) допущена неточность в описании алгоритма CheckTrace. Корректное описание алгоритма CheckTrace приведено ниже. Автор приносит извинения за причинённые неудобства.



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)