Аннотация результатов, полученных в 2017 году
М. Захарьящев: Мы работаем над разработкой и исследованием языков, подходящих для доступа к данным с учетом онтологий (OBDA). Основной целью OBDA является предоставить конечным пользователям - экспертам в своих областях (инженеры, геологи, метеорологи, историки и т. д.), но не ИТ-специалистам - удобный способ формулирования запросов к различным релевантным источникам данных. Ниже приводятся типичные сценарии, в которых требуется OBDA. (i) Для принятия решений о бурении скважин для добычи газа и нефти геолог должен исследовать имеющуюся информацию, которая была собрана компанией относительно структуры земной коры в регионе, измерений из предыдущих скважин, сейсмических данные и т. д. Запросы реляционных баз данных компании, разработанные в течение десятилетий, могут быть сложными даже для ИТ-специалиста знающего структуру баз данных, не говоря уже о геологах, которые не знакомы со структурой данных. В парадигме OBDA геологам предоставляется онтология, которая определяет классы и свойства, обычно используемые в их потребностях представления информации на естественном языке; теперь они могут сформулировать свои запросы в терминах этой онтологии, возможно, используя графический интерфейс. Онтология также дополняет данные с помощью фоновых геологических знаний. Задачей OBDA системы является преобразование пользовательских запросов в правильные SQL-запросы по исходным данным и делегирование их выполнение в стандартной системе управления базами данных. Однако это возможно только в том случае, если онтология и языки запросов тщательно отобраны. В настоящее время стандартным онтологическим языком OBDA стандарта W3C является OWL 2 QL, а языком запросов является SPARQL. К сожалению, онтологии, разработанные экспертами в прикладной области, часто содержат аксиомы, которые не выражаются в OWL 2 QL, например, аксиома покрытия, такая как "каждый человек является мужчиной или женщиной". Одна из общих проблем, над которыми мы работаем в этом проекте, заключается в том, чтобы понять, какие типы аксиом (не включенных в OWL 2 QL) требуются для практических применений онтологий и как справляться с ними в контексте OBDA. В частности, мы пытаемся классифицировать онтологические запросы с аксиомой покрытия в соответствии с вычислительной сложностью ответа на них (относительно входных данных) и в соответствии с их сводимостью (или переписываемостью) к SQL-запросам, (линейным) datalog программам и т. д. Мы нашли такие классификации - как синтаксические, так и семантические - для нескольких классов запросов, которые часто используются на практике, и работаем над обобщением конструкций на более общие классы. Результаты были представлены на двух международных конференциях DL-17 и KESW-17 (совместно с О.А. Герасимовой). (ii) Второй сценарий OBDA, над которым мы работаем, - это запрос данных от различных типов датчиков. Например, каждая современная газовая турбина оснащена датчиками, измеряющими температуру их лопастей, скоростью вращения, мощностью и других показателях. Сервисные инженеры заинтересованы в определении различных событий, которые важны для обнаружения, чтобы предотвратить неисправность, проанализировать эффективность услуг и т. д. В отличие от предыдущего сценария (i), рассмотренного выше, стандартный язык онтологии OWL 2 QL и язык запросов SPARQL не подходят в этой настройке, поскольку данные содержат временные и другие числовые параметры. Наша задача в этом проекте заключается в разработке новых онтологий и языков запросов, которые позволили бы формулировать предикаты, которые в значительной степени зависят от таких числовых параметров, как время, температура, скорость. До сих пор мы проанализировали большое количество конкретных запросов на естественном языке о поведении турбины, исторических и метеорологических данных. Мы также провели несколько экспериментов с нерекурсивными онтологическими запросами, расширенными различными типами временных операторов (а именно, стандартными операторами из линейной временной логики, временной логики Халперна-Шохама и метрической временной логикой). Результаты экспериментов выглядят очень многообещающими. В университете Больцано (Италия) внедряется прототип временной системы OBDA, основанной на нашей работе. С.О. Кузнецов Майнинг выпуклых многоугольных паттернов на основе Анализа Формальных Понятий. https://www.ijcai.org/proceedings/2017/ Задача выявления интересных обобщений описаний объектов (подмножеств, подпоследовательностей, подгруп) – одно из важных направлений в искусственном интеллекте (ИИ). В ситуации обучения с учителем (когда объекты обучающей выборки сопровождаются метками классов), дискриминационные шаблоны позволяют извлекать гипотезы из данных и строить понятные классификаторы. Анализ пространственно-временных данных по-прежнему является сложной задачей. Полное и неизбыточное перечисление конкретных форм до настоящего времени не привлекали особого исследовательского интереса. Числовые (в том числе пространственные) признаки обычно дискретизируются либо при предварительной обработке, либо в ходе выполнения алгоритма перечисления паттернов (узоров, шаблонов), вследствие чего признаки рассматриваются по отдельности и возникают паттерны прямоугольной формы. Тем не менее, такие модели были успешно использованы для майнинга числовых данных (например, пространственных городских данных и данных о мобильности). Интересная закономерность может быть, например, географическим районом, в котором есть достаточное количество исследуемых объектов, высокая плотность, и высокая доля объектов одного классов. Такой район может иметь любую форму, однако методы, применявшиеся ранее, были основаны на прямоугольниках со сторонами, параллельными осям координат, которые могут охватывать как плотные, так и разреженные области. Использование произвольных многоугольников в качестве паттернов может приводить к переобученности (то есть слишком точной подгонке к обучающей выборке), и такие паттерны подчас трудно интерпретировать. Выпуклые многоугольники дают хороший компромис между интересностью паттернов и сложностью их вычисления. В нашей работе был введен новый тип паттернов (узоров, шаблонов) - выпуклые многоугольники, которые анализировались с помощью инструментов Анализа Формальных Понятий (АФП). Компьютерные эксперименты, представленные в работе, показывают, что выпуклые многоугольники, с некоторыми дополнительными естественными ограничениями, дают лучшие приближения чем прямоугольники со сторонами, параллельными осям координат в смысле покрываемой площади, плотности и однородности областей. Предлагаемые нами средства дают базовые инструменты для произвольных алгоритмов майнинга пространственных паттернов. Основная трудность при этом – вычислительная сложность, поскольку паттернов может быть экспоненциально много, и исчерпывающий перебор захлебывается уже на 100 объектах. Поэтому мы используем известную технику семплирования (Monte Carlo Tree Search), которая позволяет масштабировать наш подход. Эффективный майнинг графовых паттернов, устойчивых к взятию подвыборок. http://www.ucs.louisiana.edu/~sxk6389/Program Идея майнинга интересных паттернов (узоров, шаблонов) лежит в основе методов открытия знаний. Меры интересности паттернов, позволяющие эффективно вычислять наиболее интересные графовые паттерны имеют большое значение. В нашей статье мы занимаемся майнингом интересных замкнутых графов, которые очень важны для поиска ассоциативных правил на графах (правилах типа «если есть паттерн А, то с высокой вероятностью есть паттерн В»). В предыдущих исследованиях было показано, что эффективный майнинг (т.е. алгоритмы с полиномиальной задержкой) возможен для антимонотонных мер, таких как поддержка и предикат «быть минимальным генератором», а также для локальных антимонотонных мер. Тем не менее, многие меры интересности не антимонотонны в обычном смысле, в том числе меры устойчивости и робастности, которые выражают инвариантность паттерна по отношению к взятию подвыборки. В нашей работе мы расширяем класс антимонотонных ограничений, вводя антимонотонность по отношению к цепочки проекций, то есть последовательности приближенных описаний графов. Предложенный нами эффективный алгоритм определяет, какие графы нужно строить и сохранять, чтобы в итоге отобрать фиксированное количество подграфов самых устойчивых к взятию подвыборки. Данный подход имеет приложения в анализе графовых данных в таких областях как химическая информатика и обработка текстов на естественном языке. А. Щедров, М. Канович Знания о предметной области, необходимые для построения онтологий, могут быть получены из прямого диалога с экспертами или же из текстовых источников в естественном языке: научных статей, патентов, аналитических отчетов и т.п. Последнее требует наличия эффективных алгоритмических средств, разработанных на основе логико-математических методов, позволяющих извлекать смысл из коллекций текстов в виде некоторой формализованной семантической интерпретации, представленной в человеко-читаемом и машинно-читаемом виде. В процессе извлечения знаний из текста мы следуем известной теории Мельчука «Смысл ⇔ Текст», согласно которой переход от текста к смыслу осуществляется на основе процесса построения синтактико-грамматической структуры текста. Эта структура впоследствии является основой для интерпретации данного текста в виде семантических сетей, ламбда-выражений, графов зависимостей и т.п. Формальные лингвистические модели синтаксического и семантического анализа текстов можно разбить на два основных класса: 1. Порождающие грамматики Хомского, где правильно построенные тексты порождается с помощью правил в виде продукций. Данный текст признается грамматически корректным в том и только в том случае, когда его можно сгенерировать по правилам данной грамматики Хомского. Для теории и практики компьютерных наук, самый важный класс составляют так называемые бесконтекстные языки, порождаемые бесконтекстными продукциями. 2. Логические исчисления (Бар-Хиллель, Айдукевич, Ламбек). Данный текст описывается на абстрактно-символическом уровне формулой в языке исчисления и признается грамматически корректным в том и только в том случае, когда соответствующая формула, представляющая синтаксическую структуру текста, выводима в данном исчислении. Например, рассмотрим предложение "John walks". На символическом уровне, пусть John имеет тип N (существительное), а непереходный глагол walks получает тип N\S: непереходный глагол принимает существительное (субъект) слева, выдавая предложение S. Это предложение считается грамматически корректным, потому что N, (N \ S) -> S является теоремой в исчислении Ламбека (и даже в исчислении, Бар-Хиллель, Айдукевич, для основных категориальных грамматик). Здесь N\S выступает в роли левой импликации. Перечислим основные "лингвистические особенности" исходных исчислений: 1) Некоммутативность: "John walks" не тоже самое что "walks John". 2) Правило сокращения недопустимо : "John walks walks" не тоже самое что "John walks". В дополнение поддерживается проективность синтаксической структуры – не допускается разрыв и перемещение составляющих с нарушениями зависимостей. Исчисление Ламбека является логической основой категориальной грамматики в рамках лингвистической парадигмы: грамматики как формально-логической системы, и синтаксического анализа как формального доказательства (вывода). Класс языков выразимых в этих системах составляют в точности бесконтекстные языки - то есть языки порождаемые бесконтекстными грамматиками Хомского (Пентус). Подавляющее большинство лингвистических проблем можно объяснить в рамках бесконтекстных грамматик. Например, в огромном тексте "Евгений Онегин" Пушкина можно найти только ДВА случая нарушения бесконтекстности: 1) "Он из Германии туманной Привез учености плоды." Правильная бесконтекстная структура: "Он из Германии привез туманной учености плоды." Германия никогда не была туманной - туманным был Альбион! 2) "Или разыгранный Фрейшиц Перстами робких учениц." Правильная бесконтекстная структура: "Или Фрейшиц разыгранный Перстами робких учениц." Хотя подавляющее большинство лингвистических проблем можно объяснить в рамках бесконтекстных грамматик, для ряда более тонких явлений естественных языков требуется более выразительный формализм. Например, для анализа выражения вида "the paper John signed yesterday without reading" требуется дополнительный логический механизм для пустых узлов известного типа для "the paper", которые неявно присутствуют после "signed" и после "reading". Чтобы обратиться к более тонким языковым вопросам, мы рассмотрели исчисление Ламбека, обогащенное субэкспоненциальными модальностями. С помощью экспоненциальной модальности мы обеспечиваем ограниченный вариант правила сокращения, что позволяет копирование необходимого контекста. Получены точные нижние границы сложностных оценок для исчисления Ламбека и его вариантов, обогащенных субэкспоненциальными модальностями. Установлено, что имеют место аналогичные сложностные оценки даже в предельном случае, когда используется только один синтаксический тип. В процессе было налажено сотрудничество с одним из ведущих компьютерных лингвистов, Моррилл. Его система CatLog3 - это пример эффективной практической системы. Однако некоторые примеры обрабатываются слишком долго. Нам удалось добиться ускорения его системы для некоторого класса интересных проблем. В частности, Моррилл и Валентин (2015) вводят расширение исчисления Ламбека посредством так называемых экспоненциальных и скобочных модальностей. Их расширение основано на нестандардном правилe сокращения, где обе модальности взаимодействуют весьма нетривиальным образом. Мы доказываем неразрешимость проблемы выводимости в их исчислении (открытая проблема). Мы также изучаем разрешимые фрагменты, рассмотренные Моррилом и Валентином, и мы показываем что эти фрагменты принадлежат классу NP. Для оригинального исчисления Ламбека, Pentus (2010) разработал алгоритм, работающий в полиномиальноe время, для определения доказуемости формул ограниченной глубины. Мы показали, что имеется алгоритм, работающий в полиномиальноe время, даже для исчисления Ламбека, обогащенного скобочными модальностями, когда глубина формулы и глубина вложения скобок ограничены некоторой константой. И.А. Макаров Получены новые способы решения классических задач обнаружения знаний в сложно структурированных данных: - предложен новый метод интерполяции и повышения разрешения карты глубины на основе глубокого обучения с перцептуальной функцией потерь; - проанализированы возможности прогнозирования победы команды в киберспортивных матчах на основе индивидуального вклада игроков и специальных рейтингов, учитывающих данный вклад (совместно с Д.И. Игнатовым); - разработана рекомендательная система по поиску соавторов, использующая скрытые зависимости и графовые признаки на основе анализа публикаций, написанных в соавторстве, а также выделения научных интересов ученых средствами текстового анализа; - получены новые результаты на применение алгоритмов обучения с подкреплением при обучении компьютера игре по видео-ряду с учетом алгоритма эпизодического контроля; - рассмотрены особенности применения квантовой логики при моделировании близости предложений с учетом грамматической структуры предложений. Д.И. Игнатов В работе "Behavior Mining in h-index Ranking Game" проводится исследование одной из самых больших библиографических баз по компьютерных наукам (DBLP). Предварительно были сформулированы теоретико-игровые гипотезы об типах авторов и их стратегии по числу публикаций и цитирования. По массиву 3,8 миллионов публикаций, проиндексированных в DBLP проведено исследование, позволившее не только кластеризовать авторов по типу публикационной активности (один из признаков – количество публикаций в год, приходящееся на всех соавторов), исследовать ее связь с h-индексом, но и благодаря анализу данных показать, что поведение авторов действительно близко к обсуждаемому теоретико-игровому равновесию. В работе "Predicting Winning Team and Probabilistic Ratings in "Dota 2" and "Counter-Strike: Global Offensive" Video Games" (совместно с И.А. Макаровым) изучается подход на основе алгоритмов машинного обучения к оценке вклада игроков в победу команды на примере двух видеоигр с возможностью командной игры. Экспериментально показано, что такая модель как TrueSkill, созданная для ранжирования игроков, но используемая для оценка вклада участников команды в ее победу, уступает место модели, предложенной авторами работы (0.92 точности против 0.72 у TrueSkill). Модель авторов основана на оценке вероятности вклада игрока в победу команды с помощью формулы полной вероятности по командам, игрокам и матчам. Для финальных вычислений используется оценка отдельных ее компонент на основе логистического преобразования и оценки параметров по данным. Подобная модель, по откликам опробовавших ее игроков, действительно способствует не только извлечению занимательных знаний по историческим данным игрового процесса, но и позволяет учесть слабые места команды и подготовиться (имеются в виду тренировки) к будущим матчам, что несомненно важно для киберспортсменов, стремящихся к победе. Д. Ильвовский Разработан чат-бот (демо-версия), ориентированный на общение и предоставление содержательных ответов пользователю, интересующемуся финансовой тематикой. Чат-бот анализирует информацию из интернета, принимая во внимание тематику и логическую структуру вопроса, и предлагает пользователю различные варианты ответов в интерактивном режиме. Т. Махалова Были рассмотрены подходы к вычислению замкнутых множеств признаков - объектов, позволяющих сжатым образом представлять импликативные зависимости. В рамках данного исследования был также предложен инкрементальный алгоритм вычисления замкнутых множеств признаков, который может использоваться как для нахождения импликативных зависимостей в одномерном пространстве признаков, так и в многомерных (то есть импликативные зависимости при дополнительных условиях). Полученный алгоритм может использоваться для обнаружения структур в данных, т.е. кластеризации. Для оценки результатов кластеризации были рассмотрены существующие индексы, исследованы особенности их поведения и предложен новый индекс, лишенный недостатков существующих индексов.

Аннотация результатов, полученных в 2018 году
Онтологическое управление данными (ОУД) - это семантическая технология, которая разрабатывается в течение последнего десятилетия с целью облегчения доступа к различным типам данных. Он рассматривается как ключевой компонент информационных систем следующего поколения. Онтологии в ОУД важны втройне, а именно с точки зрения объединения распределенных и разнородных источников данных, дополнения неполных данных с помощью общих знаний и предоставления удобного для пользователя языка запросов. W3C стандартизовал языки онтологий и запросов для ОУД, которые обеспечивают сводимость ОУД к традиционной оценке запросов системами управления реляционными базами данных (СУБД) или datalog инструментами. Однако, эти языки имеют ряд серьезных ограничений для преодоления, что является одной из главных целей нашего проекта. Одна из наших конкретных задач - выявить случаи, когда покрывающие аксиомы, такие как «каждый человек является мужчиной или женщиной», которые не допускаются в стандарте W3C для онтологического языка OWL 2 QL ОУД, не разрушают ключевое свойство сводимости задачи поиска ответов на онтологические запросы к оценке запросов СУБД. Мы получили ряд сильных достаточных и необходимых условий с точки зрения структуры конъюнктивных запросов, которые гарантируют СУБД и datalog сводимость запросов с учетом одной аксиомы покрытия. Другая задача - расширить парадигму ОУД до числовых данных и онтологий. Опять же, текущий стандарт W3C для онтологического языка OWL 2 QL ОУД не разрешает этот сценарий. Мы предложили новый подход для временного ОУД, который обеспечивает доступ к различным типам временных данных, а также разработали соответствующие онтологии и языки запросов. В рамках исследования также изучаются существующие методы майнинга паттернов: был проведён сравнительных анализ с целью определения ключевых характеристик методов, а также анализ их теоретической сложности. На основе экспериментов на реальных наборах данных были выявлены методы, дающие схожие результаты. Данные о теоретической сложности, экспериментального и концептуального анализа методов позволили выявить группы эквивалентных методов и определить наиболее эффективные среди них. Применение принципа минимальной длины описания позволило разработать теоретически обоснованный подход к созданию ансамблевых классификаторов на основе замкнутых описаний (элемент пространства версий, однозначно его определяющий), обладающих хорошей обобщающей способностью (т.е., не склонных к переобучению). С точки зрения извлечения знаний из естественного языка, Ламбеком была предложена полная логическая система для анализа простых предложений. Мы расширяем исчисление Ламбека специальными "субэкспоненциальными модальностями", достаточными для извлечения смысла из сложноподчиненных и сложносочиненных (придаточных) предложений естественного языка, где некоторые языковые единицы появляются имплицитно в неявной форме. Например, в типичной придаточной фразе "отчет, который он послал вчера вечером", с помощью субэкспоненциальной модальности, мы получаем дополнительную копию "отчета", чтобы заполнить лакуну - восстановить "пропущенное" прямое дополнение ("отчет") к переходному глаголу "послал". Основная проблема, которую мы пытаемся решить, - это обеспечить разумный баланс между выразительными возможностями предлагаемой логической оболочки и сложностью алгоритмической реализации. Нами предпринята попытка изучить связь между двумя популярными и распространенными формализмами, позволяющими представлять семантику (т.е. смысл) текстов: теорией аргументации и теорией дискурса. Интуитивная близость этих теорий была известна уже давно, а в данном исследовании удалось экспериментальным путем показать, что анализ дискурсивных (логических) связей внутри текста позволяет судить о том, есть ли в конкретных предложениях или фрагментах аргументированная точка зрения. Кроме того, можно также определять, к каким приемам прибегал автор данного текста, чтобы донести свою точку зрения: был эмоционален, сдержан, использовал логические подтасовки и т.д. Предложен алгоритм обучения хорновской оболочки произвольной пропозициональной теории предметной области с использованием эксперта (или оракула), способного отвечать на вопросы определенных типов относительно этой предметной области. Для решения этой задачи ранее была разработана процедура исследования признаков из формального анализа понятий, однако число запросов к эксперту в этой процедуре в худшем случае экспоненциально от размера итоговой хорновской формулы. Модифицировав известный полиномиальный алгоритм обучения хорновским формулам с запросами на принадлежность и эквивалентность, мы разработали полиномиальный “вероятно приближенно корректный” алгоритм обучения хорновской оболочке произвольной пропозициональной теории. Для того чтобы пользователю информационной системы рекомендовать релевантные товары и услуги необходимо иметь информацию о его вкусовых предпочтениях. Часто такая информация неявно выражено в истории покупок или в виде явных оценок (например, для просмотренного фильма или книги). В нашей работе мы сосредоточились на способах поиска ближайших соседей c похожими вкусами на основе матриц просмотров или оценок. Предложены специальные алгебраические операторы поиска соседей и исследованы как теоретически, так и в экспериментах на данных рекомендательного сервиса MovieLens. Согласно экспериментам, оценивающим точность и полноту таких рекомендаций на отложенных данных, лучшим оказался подход, представляющий собой “золотую середину” между теми соседями, кто купил точно такие же товары и купившими хотя бы один товар, что и целевой пользователь. Вторая часть исследования по рекомендательным системам посвящена встраиванию дополнительной информации об изображениях товаров в качестве их описания для поиска сходства. На открытом наборе данных Амазон для категории товаров одежда (clothes) с помощью гибридной архитектуры на основе предобученной глубокой нейросети ResNet101 и неглубокой сверточной сети удалось добиться не только качества превышающего качества матричных разложений на основе чередующихся наименьших квадратов в терминах полноты и меры AUC, но высокого визуального сходства рекомендуемых товаров. Разработаны эффективные методы поиска т.н. квазибиклик на основе смешанного целочисленного программирования, что означает для практики возможность эффективного поиска максимальных сообществ в соцсетях, например, групп людей, которые почти все состоят друг с другом в отношении быть друзьями, что делает возможным его дальнейшее использование в маркетинговых задачах телекомунникационного сектора или социологических исследованиях. Методы трикластеризации успешно применены для порождения т.н. семантических фреймов по тройкам субъект-глагол-объект (subject-verb- object), извлеченных из больших текстовых коллекций, в частности набор данных DepCC. Получены новые результаты в области восстановления карты глубины на основе скрытого представления знаний о разреженной карты глубины, а также новые методы повышения разрешения карты глубины. Предложены новые модели извлечения признаков из сетей соавторства как на основе центральностей, так и на основе векторных моделей графов, что позволило научиться прогнозировать будущие коллаборации и рекомендовать их на основе имеющейся информации по публикационной активности исследователей. Представленные результаты предлагают качественно новые методы представления, обработки и обнаружения знаний, результаты исследований опубликованы в ведущих международных журналах и конференциях.

Аннотация результатов, полученных в 2019 году
В теоретическом представлении знаний и рассуждениях мы исследовали проблему идентификации сложности данных при ответе на запросы, связанные с онтологией с аксиомой покрытия и линейными конъюнктивными запросами. Более конкретно, мы исследовали связь этой проблемы с классическими проблемами удовлетворения ограничениям (CSP) для понимания дихотомии P / coNP и связь этой проблемы с линейным монадическим даталогом, чтобы понять структуру тех конъюнктивных запросов, которые приводят к запросам с учетом онтологии в классе сложности NL. Мы разработали и внедрили алгоритм для определения того, может ли ответ на заданный запрос с онтологией с аксиомой покрытия и линейным конъюнктивным запросом быть найден за полиномиальное время относительно сложности по данным или сложность составляет coNP. Алгоритм использует программное обеспечение Polyanna для поиска полиморфизмов для CSP, которое было разработано в Оксфордском университете. Для представления практических знаний мы разработали новый двумерный язык онтологий для доступа к данным, основанным на онтологиях к потоковым данных, полученным в результате измерений датчиков и сохраненных в реляционной базе данных. В языке представлены правила регистрации данных с метрическими временными операторами, интервальные операторы Аллена и широкий спектр функций агрегирования. Мы разработали и внедрили алгоритм, сводящий ответы на нерекурсивные запросы, связанные с онтологией на этом языке, к стандартным запросам SQL к данным. Язык и алгоритм были протестированы в двух реальных случаях использования, в которых мы обнаружили интересующие события на основе данных датчиков от газовых турбин Siemens и бурового оборудования. Результаты экспериментов показали, что наш новый подход хорошо масштабируется на больших реальных наборах данных. Был разработан новый подход (и алгоритм) к майнингу численных паттернов (без предварительной обработки, в том числе бинаризации). Подход может быть расширен для майнинга данных более сложной структуры, например, последовательностей, деревьев, графов, и пр. Также были предложены теоретическая модель LO-паттернов, позволяющая существенно сократить пространство поиска паттернов и повысить эффективность подходов к их майнингу на основе принципа минимальной длины описания (МДО), и новый МДО-подход к майнингу паттернов в контексте задачи факторизации булевых матриц. В рамках проекта исследуются алгоритмически эффективные средства, на основе логико-математических методов и техник, для извлечения из текстов их смысла, представленного в виде формализованной семантической интерпретации, как в человеко-читаемой, так и в машиночитаемой форме. Таким образом, из текстовых источников на естественном языке, таких как научные статьи, патенты, аналитические отчёты и проч., могут быть извлечены знания, необходимые для построения онтологии данной предметной области. В процессе извлечения знаний из текста, мы следуем широко известной модели “смысл ⇔ текст” Мельчука, согласно которой переход от текста к значению происходит, прежде всего, посредством получения синтаксически-грамматической структуры текста. Далее эта структура используется для построения интерпретаций текста в формах семантических сетей, лямбда-выражений, графов зависимостей и т.д. Формальные лингвистические модели синтаксического и семантического анализа текстов берут своё начало в работах Хомского о порождающих грамматиках, в которых “правильные” тексты порождаются с помощью системы правил-продукций. Текст принимается как грамматически правильный, если и только если он может быть порождён по правилам данной грамматики Хомского. Основополагающая работа Ламбека, в которой было введено синтаксическое исчисление Ламбека, дала возможность поставить исследование и разработку формальных грамматик на рельсы стандартов математической логики. Серия программ CatLog, разрабатываемая Морриллом, включает реализацию, на языке Prolog, систем автоматического вывода и синтаксического разбора для логической категориальной грамматики. Наиболее современная версия программы, CatLog3, разработанная Морриллом в 2018, частично основана на наших работах 2017-18 гг., выполненных в рамках данного проекта РНФ. В свою очередь, субструктурное исчисление, используемое в CatLog3, поднимает и мотивирует ряд важных алгоритмических и логико-математических проблем и вопросов. Эти проблемы решены в нашей более новых работах 2019 г., написанной в рамках данного проекта, и включают алгоритмическую неразрешимости фрагмента исчисления, содержащего субэкспоненциальную и скобочные модальности и нижнюю оценку PSPACE и семантическую неполноту для очень ограниченных фрагментов, таких как фрагмент, содержащий только одну мультипликативную операцию деления и аддитивную конъюнкцию (или дизъюнкцию). Мы также установили алгоритмическую неразрешимость для любого расширения исчисления Ламбека с аддитивной конъюнкцией и мультипликативной единицей, корректного относительно языковых моделей (L-моделей), при условии, что это расширение включает определённый набор правил для мультипликативной единицы, которые выражают естественные алгебраические свойства пустого слова. Предложен “концептуальный” фреймворк, реализующий модель диалогового агента (чат-бота). Чат-бот ориентирован на выполнение запросов человека и в процессе диалога использует базы знаний, представляемые в виде онтологий и формальных контекстов. Благодаря применению аппарата Анализа Формальных Понятий (АФП), диалоговый агент обеспечивает одновременно максимально быстрое и полное удовлетворение запросов пользователей (например, поиск товара, отвечающего нужным характеристикам). Выполнены исследования в области интеллектуального информационного поиска. Предложена поисковая модель, позволяющая избежать обращений к структурированным базам знаний в случае их отсутствия или неполноты. Вместо этого выполняется обычный текстовый поиск, "улучшенный” и дополненный благодаря использованию дискурсивного представления текстовых данных. Были рассмотрены вычислительные проблемы, связанные с поиском импликаций в явно заданном формальном контексте или с помощью запросов к оракулу. Они включали два типа проблем: перечисление импликаций (или ассоциативных правил) и поиск единственной импликации, удовлетворяющей определенным условиям. Результаты сложности для некоторых из этих проблем были представлены, в то время как другие были заявлены как открытые проблемы. Был предложен подход для приблизительного дополнения TBox относительно фиксированной модели. Задавая импликативные вопросы эксперту в предметной области, метод аппроксимирует отношения поглощения, которые содержатся в модели эксперта, и обогащает TBox недавно обнаруженными взаимосвязями между заданным набором понятий. Подход основан на точной системе обучения Angluin и на методе исследования атрибутов из формального анализа понятий. Он объединяет лучшее из обоих подходов, чтобы задать не более чем полиномиальное число вопросов эксперту в предметной области. Завершена разработка программного обеспечения Triclusteting Toolbox, реализующее несколько методов трикластеризации как для булевых, так и числовых тензоров. Модели на основе смешанного целочисленного программирования были разработаны для поиска квази-биклик и больших плотных трикластеров. Множественная классификация совместных временных рядов для предсказания продуктивности скважин (включая конкретное подмножество источников) была улучшена благодаря извлечению значимых признаков, каскадам классификатров и ансамблевому обучению. Разработан открытый фреймворк по реконструкции и повышению разрешения разреженной карты глубины в рамках Reproducibility Challenge. Разработаны и валидированы новые модели векторизации графа для неориентированных сетей с учетом весов, нескольких слоев, атрибутов вершин и ребер, и трансдуктивного и индуктивного подхода к обучению моделей. Разработана модель предсказания длительности перевозок на основе сетевого подхода, выделенный метод протестирован относительно справочника перевозок, используемого РЖД, показано улучшение в полтора раза относительно бейзлайна. Предложен новый метод генерации изображения людей в одежде на основе генеративных состязательных сетей и ограничениями, накладываемыми сегментацией и позой человека, таким образом добавляя обуславливающие конструкции в архитектуру нейронных сетей. Построены прототипы систем машинного перевода для дактиля жестовых языков с учетом логической агрегации покадрового перевода, и для генерации жестов на основе текстовой информации, обогащенной семантикой. Получены новые результаты в области глубокого обучения с подкреплением на основе комбинации различных подходов к обучению частично-наблюдаемого Марковского процесса. Сформулирована новая проблема в области применения глубокого обучения с подкреплением в классической задаче оценки сложности игровых уровней на примере игры “три в ряд”. Предложен метод, позволяющий заменить оценку классических логических решателей и человеческий труд на измерение метрик самообучаемого агента для тестирования игровых уровней.