2019 год, том 23, выпуск 4 (PDF)
Интерпретируемость, линейное увеличение сложности с ростом данных, масштабируемость сделали тематическое моделирование одним из наиболее популярных инструментов статистического анализа текстов. Однако есть и ряд недостатков, вызванных зависимостью решения от инициализации. Известно, что построение тематической модели сводится к решению некорректно поставленной задачи неотрицательного матричного разложения. Множество её решений в общем случае бесконечно. Всякий раз модель находит локальный экстремум. Многократное обучение модели по одной и той же коллекции может приводить к обнаружению всё новых и новых тем. На практике часто требуется определить все темы корпуса. Для решения этой задачи в статье предложен и исследован новый алгоритм нахождения полного набора тем, который основан на построении выпуклой оболочки. Экспериментально показано, что за конечное число моделей можно построить базис тем. Правдоподобие базиса тем выше, чем одной модели с аналогичным числом тем. Сравнение базисов моделей LDA (latent Dirichlet allocation) и ARTM (additive regularization for topic modeling) позволяет сделать вывод, что темы наборов совпадают с высокой точностью.
Ключевые слова: вероятностное тематическое моделирование, устойчивость тематических моделей, полный набор тем тематических моделей, латентное размещение Дирихле, LDA, регуляризация, ARTM, BigARTM.
Известно, что язык, задаваемый регулярным выражением вида ∪_{i=1}^n . * α_i . * β_i .*, где α_i , β_i — слова над некоторым алфавитом, в общем случае для распознавания конечным детерминированным автоматом требует экспоненциальное по n число состояний. В работе предлагается конструкция структурного автомата, распознающего языки из данного класса и имеющего полиномиальную пространственную сложность.
Ключевые слова: ДКА, структурный автомат, регулярный язык, экспоненциальный взрыв.
Рассматривается метод поиска вывода в односукцедентном секвенциальном варианте классического исчисления предикатов. В этом алгоритме используются метапеременные и частичная скулемизация. Для рассматриваемого алгоритма доказываются теоремы о корректности и полноте.
Ключевые слова: автоматическое доказательство теорем, поиск вывода, язык первого порядка, исчисление предикатов, исчисление секвенций, продукционная система, искусственный интеллект.
В настоящей статье исследуется проблема полноты для полиномиальных функций с рациональными коэффициентами, а также задачи функционального характера, порожденные ее решением, а именно: изучение структуры замкнутых и предполных классов, задача о базисах полных систем. В частности, доказано, что 1) система функций является полной тогда и только тогда, когда она целиком не содержится ни в одном предполном классе; 2) мощность множества всех предполных классов равна континууму. 3) существует полная система, не имеющая базиса.
Ключевые слова: полином, функциональная система, проблема полноты, рациональная функция, замкнутые классы.
В работе рассматривается задача точной параметро-эффективной расшифровки функций из замкнутых классов Поста при помощи запросов на сравнение. Показано, что сложность расшифровки с помощью этих запросов не хуже, а для некоторых классов по порядку лучше, чем таковая для случая запросов на значение.
Ключевые слова: точная расшифровка, параметро-эффективная расшифровка, запросы на значение, запросы на сравнение, замкнутые классы Поста.
Представлено краткое изложение результатов, полученных при исследовании проблемы A-полноты систем линейных автоматов, функционирующих над кольцом двоично-рациональных чисел. Описаны условия A-полноты систем, содержащих все одноместные линейные автоматы и конечную добавку, а так же конечных систем, содержащих сумматор.
Ключевые слова: конечные автоматы,линейные автоматы, двоично-рациональные числа, А-полнота, предполный класс.
2019 год, том 23, выпуск 3 (PDF)
Данная работа относится к области семантического анализа юридических документов. В статье приводится один из возможных подходов по моделированию правил движения. Описаны основные этапы семантического разбора некоторого класса предложений.
Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение семантической модели текста.
В работе описывается новое расширение метода резолюции, использующее графовое представление опровержений булевых формул в конъюнктивной нормальной форме. Доказывается, что невыполнимость булевой формулы равносильна существованию для неё графового опровержения.
Ключевые слова: Метод резолюции, графовые опровержения, невыполнимость, булевы формулы.
Рассматривается множество функций, заданных бесповторными формулами с бинарными операциями конъюнкции (логического И) и дизъюнкции (логического ИЛИ). Для функций, заданных формулами с фиксированным числом операций, исследуются значения весов — числа наборов, на которых функция принимает значение 1. Найдены асимптотические оценки для числа бесповторных формул, задающих функции с весом из определенных диапазонов, в частности, — числа формул, задающих функции, у которых доля единиц среди значений не превышает четверти.
Ключевые слова: булева функция, бесповторная формула, вес функции, асимптотическая оценка.
В работе представлены коды, задающие изображения с точностью до аффинных преобразований, в том числе некоторый новый код.
Ключевые слова: распознавание образов, изображения, коды изображения.
В данной статье рассматривается модель прямоугольных многомерных схем. Элементы схем расположены в ячейках d-мерной прямоугольной решетки. Каждая пара соседних ячеек решетки соединена шиной, в которой может быть до k проводов. Доказана верхняя оценка функции Шеннона для сложности данного вида схем 2^n / min(n,d log k).
Ключевые слова: многомерные схемы, многослойные схемы, асимптотика функции Шеннона, сложность схем.
Уточнены перечни предполных классов в классах линейных автоматов над конечными полями. Найден критерий конечности числа предполных надклассов для заданного множества линейных автоматов.
Ключевые слова: конечный автомат, линейный автомат, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.
Рассматривается проблема полноты системы автоматных функций с линейными переходами относительно операции суперпозиции. Эта система не является полной, более того, любая дополняющая ее до базиса система автоматов бесконечна.
Ключевые слова: конечный автомат, полнота, суперпозиция, замкнутый класс.
Рассматривается задача реализации булевых функций неизбыточными двухполюсными контактными схемами, допускающими короткие единичные проверяющие тесты относительно обрывов и замыканий контактов. Описаны все функции, для которых минимальная длина указанного теста равна 0, 1, 2 и 3. Доказано, что для почти всех булевых функций от n переменных эта длина равна 4.
Ключевые слова: контактная схема, булева функция, обрыв контакта, замыкание контакта, единичный проверяющий тест.
Исследуется вопрос о корректности аксиом интуиционистской теории множеств относительной семантики реализуемости, основанной на гиперарифметических видах.
Ключевые слова: конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.
Для классов передаточных функций линейных автоматов над конечным полем с операциями, индуцированными операциями композиции над этими автоматами, найдены все максимальные подалгебры.
Ключевые слова: конечный автомат, линейный автомат, передаточная функция, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.
2019 год, том 23, выпуск 2 (PDF)
В данной работе рассматривается восстановление нот из одновременного звучания двух нот в терминах амплитуд и частот. Приведены методы восстановления амплитуд двух нот, которые были одновременно сыграны двумя различными музыкальными инструментами. Описаны случаи существования и не существования одновременно двух решений для задачи восстановления нот.
Ключевые слова: основной тон, обертон, амплитуда, частота, огибающая ноты, суммарная спектрограмма.
В работе предложен новый метод введения персистентных топологических инвариантов для марковских цепей. Продемонстрирован пример использования этих инвариантов для прикладной задачи классификации текстов.
Ключевые слова: Топологический анализ данных, персиcтентные гомологии, марковские цепи, текст на естественном языке
В работе исследуется возможность надежной передачи информации в ситуации, когда противник в каждой момент времени может блокировать некоторое подмножество символов алфавита. Показано, что гарантированно надежный канал существует тогда и только тогда, когда мощность алфавита n и число разрешенных символов k удовлетворяют неравенству n ≤ 2k − 2.
Ключевые слова: скрытые каналы, блуждания по плоскости, запрещения алфавитных символов, передаваемый язык
Изображением в работе называем конечное ( непустое) множество точек в евклидовых пространствах разной размерности. Кратко работа состоит в том, чтобы имея изображение, принадлежащую некоторому образу, извлечь из этого изображения то, что можно было бы назвать описанием этого образа.
Ключевые слова: математическое определение изображения, описание зрительного образа, распознавание изображений.
В работе исследуются свойства так называемой перестановочной конструкции, введенной ранее. Выясняется, что конструкция несколько избыточна, но в результате ее улучшения, она оказывается инъективной для случая линейных правильных семейств булевых функций, и, возможно, инъективной в общем.
Ключевые слова: квазигруппы, правильные семейства булевых функций, латинские квадраты, параметрическое задание
Рассматривается алгоритм проверки наличия подквазигруппы в квазигруппе. Сравнивается скорость выполнения его последовательной и параллельной версий на вычислительной архитектуре CUDA.
Ключевые слова: квазигруппа, подквазигруппа, GPU, CUDA.
Автомат прогнозирует следующий символ входного сверхслова, если он выдает этот символ на выходе в предыдущий момент времени. В работе для произвольного сверхслова в многозначном алфавите исследуется вопрос его почти полного прогнозирования, т.е. когда прогноз правильный почти всегда. Получен результат, позволяющий сузить класс автоматов, которыми прогнозируется сверхслово, а также доказан критерий почти полной прогнозируемости сверхслова.
Ключевые слова: почти полное прогнозирование, прогнозирующий автомат, автоматное прогнозирование сверхслов, критерий прогнозируемости.
В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы операторы. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любой оператор от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(m · 2n/3 ), если m ≤ n, и √ O( m n · 3 n · 2n/3 ), если m > n.
Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.
В настоящей работе рассматривается 2-полнота в классе P согласованных функций. Данный класс был рассмотрен ранее в работах [3, 4]. Он является предполным в классе P L кусочно-линейных функций. В нем было найдено два 2-предполных класса: класс CP L непрерывных функций, класс P F согласованных финитных функций.
Ключевые слова: Класс кусочно-линейных функций, класс кусочно-линейных непрерывных функций, класс согласованных функций, класс финитных функций, класс согласованных финитных функций, 2-предполнота, функция Хэвисайда.
В математике часто новые понятия вводятся с помощью некоторых кванторных определений. При наличии достаточно большого запаса таких понятий они могут позволить переформулировать новые кванторные определения бескванторным образом. Это делает заслуживающей рассмотрения задачу отыскания базисных понятий в заданной предметной области, которые делают избыточным дальнейшее кванторное определение. Интересной также является задача создания компьютерных программ, автоматически вводящих такие базисы. В данной работе рассматриваются 3 простых случая сведения кванторной выразимости к бескванторной. Исследуются предикаты и функции, определенные через ∈ и заданные на множестве Z ∪ 2Z , где Z — множество целых чисел. Кроме того, рассматриваются предикаты, выразимые через тот же предикат на множестве точек плоскости и прямых, лежащих в ней. Также рассмотрены предикаты, выразимые на множестве натуральных чисел с отношением делимости на нем. Во всех случаях удалось найти базисы бескванторной выразимости.
Ключевые слова: кванторная выразимость, логика предикатов.
Определяется семантика реализуемости для формул языка теории множеств, основанная на гиперарифметических видах. Исследуется вопрос о корректности аксиом теории множеств Цермело-Френкеля относительной этой семантики.
Ключевые слова: конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.
2019 год, том 23, выпуск 1 (PDF)
Разработан алгоритм обучения для задачи позиционирования систем с дискретным управлением, основанный на методе обобщения проб и ошибок, сохраняющихся в базе данных, с помощью глобальной интерполяции и градиентного спуска. Оптимизация алгоритма производится по критерию сокращения времени обучения (числа попыток). Алгоритм был протестирован на симуляторе для моделей систем, действующих на плоскости, двух разных типов: для мобильного робота с двумя ведущими гусеницами и для открытой кинематической цепи с вращательными и призматическими сочленениями.
Ключевые слова: позиционирование, алгоритм обучения, робот, интерполяция, аппроксимация.
Данная работа относится к области семантического анализа юридических документов. Под семантикой нормативно-правовых актов будем понимать отображение, на вход которого поступает текст нормативно-правового акта, а на выходе получается его формальная модель. В статье описывается один из возможных подходов построения формальной модели правил дорожного движения.
Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение формальных моделей.
В работе рассматривается задача конечного представления логических систем пропозициональными исчислениями. Исследуются три типа логических систем: линейные, монотонные и импликативные. Для каждого из этих типов логических систем доказаны достаточные условия их конечного задания. Кроме того, доказан критерий конечного задания произвольной логической системы множества классических тавтологий.
Ключевые слова: логические системы, пропозициональные исчисления, конечное задание, правила вывода.
Приводится обзор результатов, связанных с проверкой полиномиальной полноты конечных квазигрупп. Работа подготовлена по материалам доклада на семинаре “Теория автоматов”.
Ключевые слова: квазигруппа, латинский квадрат, полиномиальная полнота, простота, аффинность
В статье изучается множество K(n) := N \ (n, n), исследуется его представление в виде объединения как можно меньшего количества арифметических прогрессий с ограничением на начало или шаг. В каждом из двух случаев найдены соответствующие точные оценки.
Ключевые слова: арифметическая прогрессия, натуральный ряд, проблема минимизации, типы ограничений.
Определяются различные варианты понятия V -реализуемости для формул языка логики предикатов, основанные на использовании функций из множества V для интерпретации импликации и квантора всеобщности. Устанавливается, что принцип Маркова является слабо V -реализуемым, не является равномерно V - реализуемым и является V -реализуемым равномерно в области M , если множество M ⊆ N является V -перечислимым.
Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, обобщенная реализуемость, принцип Маркова.
В настоящей статье рассматривается класс нейронных кусочно- параллельных функций с двоично-рациональными коэффициентами(BPP). Приводится доказательство существования в нем минимальной Шефферовой функции. Под минимальной Шефферовой функцией в рассматриваемом классе, понимается функция этого класса, порождающая этот класс по операциям суперпозиции и содержащая минимально возможное количество переменных и пороговых функций. Было установлено, что в данном классе минимальная Шефферова функция содержит две переменных и одну пороговую функцию. Также в статье приводится одно из необходимых условий Шефферовости функции, принадлежащей BPP.
Ключевые слова: класс, кусочно-параллельные функции, нейронные функции, двоично-рациональные коэффициенты, операции суперпозици, Шефферова функция.
В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы функции. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любую функцию от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(2n/3 ).
Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.
Пусть L — некоторое расширение языка арифметики, V — некоторый класс числовых функций. Определяется понятие V - реализуемости для предикатных формул, основанное на оценке предикатных переменных формулами языка L. Устанавливается корректность и полнота классической логики относительно семантики V -реализуемости в случае, когда класс V содержит все функции, определимые в языке L.
Ключевые слова: конструктивная семантика, реализуемость, обобщенная реализуемость, формальная арифметика.
Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида Φ ∪ ν, где Φ ⊆ Pk , ν - конечно. При k = 2 решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При k = 2 эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обощения этой задачи, а также некоторые результаты для Pk , k > 2.
Ключевые слова: булева функция, конечный автомат, алгоритмическая разрешимосить.