English
2019 год, том 23, выпуск 4 (PDF)
Интерпретируемость, линейное увеличение сложности с ростом данных, масштабируемость сделали тематическое моделирование одним из наиболее популярных инструментов статистического анализа текстов. Однако есть и ряд недостатков, вызванных зависимостью решения от инициализации. Известно, что построение тематической модели сводится к решению некорректно поставленной задачи неотрицательного матричного разложения. Множество её решений в общем случае бесконечно. Всякий раз модель находит локальный экстремум. Многократное обучение модели по одной и той же коллекции может приводить к обнаружению всё новых и новых тем. На практике часто требуется определить все темы корпуса. Для решения этой задачи в статье предложен и исследован новый алгоритм нахождения полного набора тем, который основан на построении выпуклой оболочки. Экспериментально показано, что за конечное число моделей можно построить базис тем. Правдоподобие базиса тем выше, чем одной модели с аналогичным числом тем. Сравнение базисов моделей LDA (latent Dirichlet allocation) и ARTM (additive regularization for topic modeling) позволяет сделать вывод, что темы наборов совпадают с высокой точностью.
Ключевые слова: вероятностное тематическое моделирование, устойчивость тематических моделей, полный набор тем тематических моделей, латентное размещение Дирихле, LDA, регуляризация, ARTM, BigARTM.
Известно, что язык, задаваемый регулярным выражением вида \(\cup_{i=1}^n . * \alpha_i . * \beta_i . * \), где \(\alpha_i\), \(\beta_i\) — слова над некоторым алфавитом, в общем случае для распознавания конечным детерминированным автоматом требует экспоненциальное по n число состояний. В работе предлагается конструкция структурного автомата, распознающего языки из данного класса и имеющего полиномиальную пространственную сложность.
Ключевые слова: ДКА, структурный автомат, регулярный язык, экспоненциальный взрыв.
Рассматривается метод поиска вывода в односукцедентном секвенциальном варианте классического исчисления предикатов. В этом алгоритме используются метапеременные и частичная скулемизация. Для рассматриваемого алгоритма доказываются теоремы о корректности и полноте.
Ключевые слова: автоматическое доказательство теорем, поиск вывода, язык первого порядка, исчисление предикатов, исчисление секвенций, продукционная система, искусственный интеллект.
В настоящей статье исследуется проблема полноты для полиномиальных функций с рациональными коэффициентами, а также задачи функционального характера, порожденные ее решением, а именно: изучение структуры замкнутых и предполных классов, задача о базисах полных систем. В частности, доказано, что 1) система функций является полной тогда и только тогда, когда она целиком не содержится ни в одном предполном классе; 2) мощность множества всех предполных классов равна континууму. 3) существует полная система, не имеющая базиса.
Ключевые слова: полином, функциональная система, проблема полноты, рациональная функция, замкнутые классы.
В работе рассматривается задача точной параметро-эффективной расшифровки функций из замкнутых классов Поста при помощи запросов на сравнение. Показано, что сложность расшифровки с помощью этих запросов не хуже, а для некоторых классов по порядку лучше, чем таковая для случая запросов на значение.
Ключевые слова: точная расшифровка, параметро-эффективная расшифровка, запросы на значение, запросы на сравнение, замкнутые классы Поста.
Представлено краткое изложение результатов, полученных при исследовании проблемы A-полноты систем линейных автоматов, функционирующих над кольцом двоично-рациональных чисел. Описаны условия A-полноты систем, содержащих все одноместные линейные автоматы и конечную добавку, а так же конечных систем, содержащих сумматор.
Ключевые слова: конечные автоматы,линейные автоматы, двоично-рациональные числа, А-полнота, предполный класс.