Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Страбыкин Д.А. 1 Долженкова М.Л. 1

---

1 ФГБОУ ВО «Вятский государственный университет»

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

Статья в формате PDF

0 KB

логическое прогнозирование развития ситуаций

вывод следствий

исчисление высказываний

1. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Поспелов Д.А. Достоверный и правдоподобный вывод в интеллектуальных системах. – 2-е изд., испр. и доп. – М.: Физматлит, 2008.

2. Вагин В.Н., Загорянская А.А. Системы аргументации и абдуктивный вывод // Изв. РАН. ТиСУ. – 2004. – № 1. – С. 125–137.

3. Вагин В.Н., Хотимчук К.Ю. Методы абдуктивного вывода в задачах планирования работы в сложных объектах // Изв. РАН. ТиСУ. – 2010. – № 5. – С. 95–113.

4. Витяев Е.Е. Предсказание как вычисление // Философские науки. – 2007. – № 1 (32). – С. 81–101.

5. Долженкова М.Л., Страбыкин Д.А. Задача абдуктвного вывода следствий // Научно-технический вестник Поволжья. – 2015. – № 1. – С. 74–77.

6. Кузнецов О.П. Интеллектуализация поддержки управляющих решений и создание интеллектуальных систем // Проблемы управления. – 2009. – № 3. – С. 64–72.

7. Кулинич А.А. Компьютерные системы анализа ситуаций и поддержки принятия решений на основе когнитивных карт: подходы и методы // Проблемы управления. – 2011. – № 4. – С. 31–45.

8. Страбыкин Д.А. Метод логического прогнозирования развития ситуаций на основе абдуктивного вывода // Изв. РАН. ТиСУ. – 2013. – № 5. – С. 98–92.

9. Финн В.К. Индуктивные методы Д.С. Милля в системах искусственного интеллекта // Искусственный интеллект и принятие решений. – 2010. – № 4. – С. 14–40.

Важной функцией интеллектуальных систем управления можно считать прогнозирование. Для прогнозирования применяется большое число подходов и методов. Представляет интерес логическое прогнозирование. К методам логического прогнозирования обычно относят создание прогнозного сценария, морфологический анализ, метод исторических аналогий, прогнозирование по образцу (эталону) и др. Перспективным подходом при построении методов логического прогнозирования является использование моделирования рассуждений. Методологической базой для исследования методов прогнозирования, основанных на моделировании рассуждений, в частности логическом выводе на знаниях, можно считать работу [4]. В работе рассмотрен вывод предсказания, описываемого покрывающими моделями (Covering Law Models), состоящими в том, чтобы вывести факт, как частный случай закона. При этом используется дедуктивно-номологическая модель (Deductive Nomological Model), основанная на фактах и дедуктивных законах. Теория логического вывода успешно развивается в работах [1, 9]. Большое внимание уделяется не только дедуктивному, но и абдуктивному выводу [2, 3].

Целый ряд важных теоретических и практических результатов получен в Институте проблем управления РАН в рамках решения проблемы управления плохо определенными динамическими ситуациями с использованием формального описания происходящих процессов в виде когнитивных карт [6, 7]. В работе [8] предложен метод логического прогнозирования на основе абдуктивного вывода заключений. Метод благодаря нахождению недостающих в описании ситуации фактов и правил позволяет строить прогнозы в тех случаях, когда на базе дедукции они невозможны. Метод прогнозирует развитие ситуации от заданной начальной до конечной фазы. Однако на практике возникает потребность в прогнозе в условиях, когда известна только одна – начальная фаза. Эта потребность и привела к разработке рассматриваемого далее метода прогнозирования развития ситуации из заданной фазы на основе вывода следствий при не полностью определенной базе знаний.

Для содержательной постановки задачи логического прогнозирования развития ситуаций воспользуемся основными понятиями из работы [8]. Событие в предметной области характеризуется множеством простейших утверждений – фактов, зафиксированных в определенный момент времени. Наступление события происходит в тех случаях, когда определенные подмножества этих фактов становятся истинными. В простейшем случае событие может представляться одним фактом. Ситуация в предметной области характеризуется совокупностью событий и отношений между ними. Ситуация складывается тогда, когда наступают характеризующие её события и устанавливаются необходимые отношения между ними. В простейшем случае ситуация может представляться одним событием. Фаза развития (состояние) ситуации представляется подмножеством событий и отношений, описывающих ситуацию. Ситуация входит в некоторую фазу, как только наступают характеризующие её события и устанавливаются необходимые отношения между ними. Траектория развития ситуации – последовательность фаз, через которые проходит развитие ситуации. Предсказание траектории развития ситуации – определение для ситуации, находящейся в текущей фазе (состоянии), одной или нескольких фаз (состояний), в которые перейдет ситуация в последующие моменты времени. Введённые понятия позволяют сформулировать основную задачу прогнозирования развития ситуаций как задачу предсказания траектории (траекторий) развития ситуации.

Формальное описание задачи прогнозирования как задачи логического вывода следствий

Формальное описание задачи P логического прогнозирования развития ситуации из заданной фазы может быть определено следующим образом:

P = <mC, mS, mP, r>,

где mC – множество новых событий; mS – множество текущих событий и ситуаций с отношениями между ними; mP – множество прогнозируемых фаз (состояний) развития ситуации; r – множество результатов прогнозирования, которое может содержать схему логического прогнозирования S, а также прогнозируемые в следующий момент времени фазы (состояния) m1 и последовательности фаз (состояний) mL. Для упрощения описания задачи прогнозирования как задачи логического вывода введем ряд определений.

Определение 1. Задача дедуктивного вывода следствий формулируется следующим образом: при заданном множестве исходных посылок MP для некоторого (нового) набора фактов MF определить множество следствий MS (утверждений, которые будут следовать из новых фактов при использовании исходных посылок). При этом если вывод успешен, то могут быть определены логические цепочки вывода, объясняющие нити рассуждений.

Определение 2. Задача вывода следствий при не полностью определенной базе знаний формулируется следующим образом: при заданном множестве исходных посылок MP для некоторого (нового) набора фактов MF определить множество следствий MS (утверждений, которые будут следовать из новых фактов при использовании исходных посылок) и множество дополнительных фактов MD, необходимых для успешного вывода следствий и не противоречащих исходным посылкам.

Определение 3. Формула

X₁ & X₂ &…& X_K → Y

называется формулой непосредственного логического следования, символы X1, X2, …, X_K, Y – литералами, а символ «>» – знаком логического следования, который разделяет формулу на левую (антецедент) и правую (консеквент) части. Знаки конъюнкции в формуле могут быть опущены.

Определение 4. Выражение X, X → Y ⇒ Y интерпретируется как вывод из факта X с помощью правила X → Y следствия Y.

Определение 5. Схемой логического вывода называется ориентированный граф, вершинам которого сопоставлены формулы (номера формул) посылок, причем, входящие дуги помечены литералами из левых, а исходящие – из правых частей формул, и вершины соединены между собой в соответствии с суперпозицией их формул в выводе; литералы свободных исходящих дуг графа соответствуют конечным следствиям. Следствие считается конечным, если из него не следует ни одно утверждение.

Пример 1. Задачу вывода следствий при не полностью определенной базе знаний можно проиллюстрировать на следующем простейшем примере [9]. Исходные посылки:

1) A;

2) ABX → C;

3) CY → E.

Новый факт:

4) B.

Дедуктивный вывод следствий из факта B завершается неудачно: из факта В с помощью заданных исходных посылок не выводится ни одного следствия.

Вывод следствий при не полностью определенной базе знаний позволяет вычислить дополнительные факты 5) X и 6) Y, благодаря которым из факта В с помощью заданных исходных посылок будут выводиться следствия C и E. Следствие E является конечным, так как из него не следует утверждений. Схема логического вывода для данного примера приведена на рис. 1. Номера вершин в схеме соответствуют номерам формул посылок, а соединение вершин выполнено в соответствии с суперпозицией формул в выводе. Вершина нового факта выделена жирной линией, а вершины дополнительных фактов – пунктиром.

Рис. 1. Схема логического вывода следствий C, E из нового факта B

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

Формальное описание задачи DA вывода следствий при не полностью определенной базе, соответствующее задаче логического прогнозирования P, можно представить следующим образом: D_A = <M^F, M^P, M^D, M^S, R>, где M^F – множество новых фактов; M^P – множество текущих фактов и правил; M^D – множество дополнительных фактов, формируемых при успешном выводе; M^S – множество следствий; R – множество результатов логического вывода, которое может содержать: схему логического вывода S (используемую в качестве схемы прогнозирования), литералы утверждений (фаз, состояний), непосредственно следующих из фактов текущего шага M1 и последовательности литералов утверждений (фаз, состояний) ML. Формальное описание задачи прогнозирования как задачи вывода следствий при не полностью определенной базе знаний позволяет строить метод прогнозирования, который дает возможность в процессе прогнозирования вычислять недостающие в базе знаний факты.

Метод логического прогнозирования на основе вывода следствий при не полностью определенной базе знаний

Логическое прогнозирование представляет собой циклический процесс, состоящий из ряда шагов. Перед началом этого процесса задача логического прогнозирования формулируется как задача логического вывода следствий при не полностью определенной базе знаний:

D_A = <M^F(t), M^P(t), M^D(t), M^S,R>,

где MF(t) – множество новых фактов; MP(t) – множество текущих фактов и правил; MD(t) – множество дополнительных фактов, сформированных в процессе логического вывода, MF(t) – множество фактов, поступивших на шаге t. Первоначально t = 1. Предполагается, что объединение множеств MF(1) и MP(1) образует непротиворечивое множество, а M^D(1) = Ø. В процессе прогнозирования выполняются следующие действия.

1. Принимается новое множество фактов MF(t). Если последнее конечное следствие совпадает с одним из принятых фактов, то прогнозирование завершается (выполняется пункт 9), иначе при t = 1 выполняется пункт 3, а при t > 1 – следующий пункт.

2. Проверяется успешность прогноза: совпадение состояний, определяемых новым множеством фактов MF(t) и ранее спрогнозированных состояний. Если прогноз успешен, то выполняется пункт 6, иначе следующий пункт.

3. Производится решение задачи дедуктивного вывода следствий M^F(t) & M^P(t) ⇒. Если логический вывод завершается успешно, то выполняется пункт 5, иначе следующий пункт.

4. В том случае, когда прогнозирование с помощью дедуктивного вывода невозможно, выполняется вывод следствий при не полностью определенной базе знаний [5]. Если этот вывод следствий успешен: сформировано такое множество дополнительных фактов MD(t), которое обеспечивает дедуктивный вывод следствий Ms, и объединенное множество M^D(t) ∪ M^P(t) ∪ M^F(t) непротиворечиво, то выполняется следующий пункт, иначе – пункт 9 (прогнозирование с помощью вывода при не полностью определенной базе знаний невозможно).

5. Строится схема успешного логического вывода S.

6. По схеме S для множества фактов M^F(t) определяются прогнозируемые состояния (фазы ситуации) M¹(t), которые ожидаются на следующем шаге.

7. По схеме S для множества фактов M^F(t) формируются цепочки вывода M^L(t) от текущего состояния (состояний) до состояний, соответствующих конечным следствиям, которые представляют собой долгосрочные прогнозы.

8. Осуществляется переход к следующему шагу: значение шага t увеличивается на единицу и производится переход к пункту 1.

9. Конец. Прогнозирование завершается.

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

Пример прогнозирования с использованием исчисления высказываний

Рассмотрим прогнозирование на примере задачи диагностики автомобиля [10, с. 283]. Зададим предметную область следующим набором событий:

1) ТД – Топливо поступает в двигатель;

2) ДНВ – Двигатель не вращается;

3) ФГ – Фары горят;

4) ТБ – Топливо есть в баке;

5) ТК – Топливо поступает в карбюратор;

6) ПСЗ – Проблема в свечах зажигания;

7) ПСТ – Проблема в стартере.

Каждому событию соответствует факт, который принимает значение «ИСТИНА», как только становится известно о наступлении соответствующего ему события.

Отношения, определяемые на множестве событий предметной области, могут быть представлены базой знаний:

8) ТД & ДНВ > ПСЗ;

9) ДНВ & ФГ > ПСТ;

10) ТБ & ТК > ТД.

Начальная фаза F1 ситуации, развитие которой прогнозируется, задана событиями ТБ и ДНВ.

Формальное описание задачи логического вывода, соответствующей задаче прогнозирования, имеет следующий вид:

D_A = <M^F(t), M^P(t), M^D(t), M^S, R>.

Первоначально t = 1. Множество новых фактов M^F(1) = {ТБ, ДНВ}. Исходное множество посылок (M^P): (8–10). Множество дополнительных фактов M^D(1) = Ø.

В процессе прогнозирования выполняются следующие действия.

Шаг 1. При выполнении первого шага дедуктивный вывод следствий завершается неудачно.

1. Принимается новое множество фактов M^F(1) = {ТБ, ДНВ}. Поскольку t = 1, то выполняется пункт 3.

3. Производится решение задачи дедуктивного вывода следствий M^F(1) & M^P(1) ⇒. Дедуктивный вывод следствий завершается неудачно, поэтому выполняется следующий пункт.

4. Выполняется вывод следствий при не полностью определенной базе знаний. Этот вывод следствий успешен. Формируется множество дополнительных фактов MD(1) = {ТК}, которое обеспечивает успешный дедуктивный вывод следствий. Объединенное множество MD(1) ∪ MP(1) ∪ MF(1) непротиворечиво. Формируется множество следствий MS = {ТД, ПСЗ}, в котором следствие ПСЗ является конечным. Выполняется следующий пункт.

5. Строится схема успешного логического вывода S (рис. 2).

6. По схеме S для множества фактов MF(1) определяются прогнозируемые состояния (фазы ситуации), которые ожидаются на следующем шаге (таблица, строка 1).

Рис. 2. Схема логического вывода следствий ТД, ПСЗ из новых фактов ДНВ и ТБ

Прогноз и его уточнение по шагам

7. По схеме S для множества фактов MF(1) формируется цепочка вывода от текущего состояния до состояния, соответствующего конечному следствию, которая представляет собой долгосрочный прогноз (таблица, строка 1).

8. Осуществляется переход к следующему шагу: значение шага t увеличивается на единицу и производится переход к пункту 1.

Шаг 2. При выполнении второго шага подтверждается успешность прогноза, сформированного на первом шаге.

1. Принимается новое множество фактов MF(2) = {ТК, ТД}. Поскольку t ≠ 1, то выполняется пункт 2.

2. Проверяется успешность прогноза: совпадение состояний, определяемых новым множеством фактов MF(2) и ранее спрогнозированных состояний. Поскольку прогноз успешен, то выполняется пункт 6.

6. По схеме S для множества фактов MF(2) определяются прогнозируемые состояния (фазы ситуации), которые ожидаются на следующем шаге (таблица, строка 2).

7. По схеме S для множества фактов MF(2) формируется цепочка вывода от текущего состояния до состояния, соответствующего конечному следствию, которая представляет собой долгосрочный прогноз (таблица, строка 2).

8. Осуществляется переход к следующему шагу: значение шага t увеличивается на единицу и производится переход к пункту 1.

Шаг 3. При выполнении третьего шага подтверждается успешность прогноза, сформированного на втором шаге.

1. Принимается новое множество фактов MF(3) = {ПЗС}. Поскольку принятый факт совпадает с единственным конечным следствием, то производится переход к пункту 9.

9. Конец. Прогнозирование завершается.

Прогнозирование осуществляется на основе схемы логического вывода на каждом шаге развития ситуации с учётом поступающих фактов. Прогноз завершается на шаге 3, так как поступивший факт совпадает с единственным конечным следствием. В процессе прогнозируемого развития ситуации выделяются три фазы: F1, F2, F3 (рис. 2).

Заключение

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

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

Успешность реализации логического прогнозирования определяется успешностью реализации логического вывода. До недавнего времени главным аргументом против использования методов логического вывода на знаниях, представленных в виде формул исчисления высказываний и предикатов первого порядка, был большой объем вычислений, обусловленный комбинаторным характером задач логического вывода. Однако разработка и применение параллельных методов логического вывода, ориентированных на современные параллельные вычислительные платформы, и технологии параллельного программирования позволяют решать задачи логического вывода за приемлемое время.

Работа выполнена при финансовой поддержке РФФИ (проект № 15-01-02818 а).

Библиографическая ссылка