На главную страницу

Донецкий Национальный Технический Университет

Сметанин Павел Юрьевич

«Абдуктивный подход при построении нового знания в базе знаний»

Специальность: программное обеспечение автоматизированных систем

Автореферат магистерской выпускной работы

Руководитель: доцент, к.т.н. Андрюхин А.И.

 

 

Общая характеристика работы

 

 

            Бурное развитие аппаратного обеспечения ЭВМ и, в частности, появление новых периферийных устройств, расширило возможности применения компьютеров для целого ряда областей человеческой деятельности. Переживают период активного роста технологии, ориентированные на использование глобальных информационных сетей. Ежегодно создается и включается в мировую сеть для свободного доступа сотни баз данных различного типа и назначения, десятки фирм осуществляют переход на безбумажную технологию ведения документации. Параллельно этим процессам растет нагрузка на рядового пользователя компьютера. Объем информации, который ему приходится обрабатывать зачастую превышает скромные человеческие возможности. Здесь уместно привести высказывание Э.Дейкстры, специалиста, чья деятельность тесно связана с информатикой, одного из основоположников структурного программирования: "... человек соображает медленно, а емкость его памяти очень мала, и ему следует получше научиться жить в таких условиях...". Одним из способов облегчения процесса поиска и обработки информации, скрытия сложности управления комплексными автоматизированными объектами, поддержки процесса принятия решений является создание и использование интеллектуальных программных агентов. Они представляют собой новое поколение интеллектуальных систем, которым, однако, предъявляются требования гораздо более жесткие, чем к их предшественникам - первым экспертным системам. Характеризуя этот факт, западные специалисты по искусственному интеллекту отмечают, что произошла смена взгляда на интеллектуальные системы и моделирование знаний.

            Целью данной работы является исследование методологий и возможностей инженерного творчества с использованием ЭВМ, что является насущной проблемой в условиях увеличивающихся темпов научно-технического прогресса. Перечислим основные задачи, поставленные для исследования:

-         Исследование характеристик и возможностей физико-технических эффектов в форме различного вида цепочек триад;

-         Применение в качестве дополнения приборов, меняющих и измеряющих параметры объектов.

-         Анализ различных возможностей вывода конечной цели;

-         Использование абдуктивного логического вывода.

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

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

Реализация результатов работы заключается в реализации механизма абдуктивного логического вывода с применением фонда ФТЭ и приборов.

 

Содержание работы

 

 

Синтез физических принципов действия

 

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

            Основная трудность состоит в том, что инженер обычно знает до 200, а достаточно свободно использует не более 100 ФТЭ, хотя в научно-технической литературе их описано более 3000. Кроме того, в связи с возрастающими темпами развития науки и техники, число ФТЭ постоянно увеличивается. Поэтому в наше время у разработчиков новой техники существует очень большой и постоянно возрастающий дефицит информации, необходимой для решения задач поиска новых ФПД.

 

Фонд физико-технических эффектов

 

В основе автоматизированного синтеза ФПД лежит база данных, в которой каждый ФТЭ имеет трёхуровневое описание. На первом уровне даётся самое короткое качественное описание ФТЭ. На втором уровне приводится стандартная карта описания ФТЭ размером в одну страницу, где даётся наиболее важная и легко обозримая информация о ФТЭ и его использование в технике. Третий уровень описания совместно с информацией второго уровня даёт более подробное описание ФТЭ, объём которого обычно составляет 5-10 страниц. Он имеет следующие рубрики:

1.      Наименование ФТЭ.

2.      Наименование физических законов и явлений, на которых основан ФТЭ.

3.      Вход А.

4.      Объект В.

5.      Выход С.

6.      Сущность и схема ФТЭ.

7.      Математическая модель ФТЭ.

8.      Существование обратного ФТЭ.

9.      Применение ФТЭ в технике.

10.  Инженерно-технические характеристики ФТЭ.

11.  Дополнительная полезная информация.

12.  Карта описания ФТЭ.

13.  Список литературы.

 

 

Структурное представление

 

          Технический объект имеет назначение или цель создания, называемые потребностью. Описание потребности формализовано можно представить в виде трёх компонент:

            P = (D, G, H),

где D – указание действия, производимого рассматриваемым ТО и приводящего к необходимому результату; G – указание объекта или предмета обработки; H – указание особых условий или ограничений.

            Для реализации ФПД необходима техническая функция (ТФ), описание которой состоит из двух частей:

            F = (P, Q),

где P – удовлетворяемая потребность; Q – физическая операция, с помощью которой реализуются потребности.

            Описание физической операции  (ФО) формализовано можно представить состоящим из трёх компонент:

            Q = (A_T, E, C_T),          или      Q = (A_T → E → C_T),

где A_T, C_T – входной и выходной поток вещества, энергии или информации, E – наименование операции Коллера по превращению или преобразованию A_T в C_T . Это описание  отвечает на вопросы “что” (A_T), “как” (E), “во что” (C_T) преобразуется с помощью описываемого ТО.

            Большинство технических объектов (ТО) состоит из нескольких элементов и могут быть естественным образом разделены на части. Каждый элемент как самостоятельный ТО выполняет определённую функцию и реализует определённую физическую операцию, т. е. Между элементами имеют место два вида связей и соответственно два вида их структурной организации.

            Во-первых, элементы имеют определённые функциональные связи друг с другом, которые образуют конструктивную функциональную структуру. Конструктивная ФС представляет собой ориентированный граф, вершинами которого  являются наименования элементов, а рёбрами – функции элементов.

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

            Взаимосвязанный набор ФО, реализующих один определённый поток, преобразований вещества, энергии или информации, или несколько взаимосвязанных потоков является потоковой функциональной структурой. Потоковая ФС представляет собой граф, вершинами которого являются наименования элементов ТО или наименования операций Коллера E, а рёбрами – входные A_T и выходные C_T потоки.

            Различают две разновидности потоковой ФС: конкретизированная потоковая ФС, у которой в вершинах графа указаны наименования элементов; абстрагированная потоковая ФС, у которой в вершинах указаны наименования операций Коллера. Абстрагированную потоковую ФС называют также структурой физических операций.

            Конструктивная ФС и потоковая ФС дополняют друг друга. При решении различных прикладных задач используют или только конструктивную ФС, или потоковую ФС, или одновременно обе разновидности.

            В потоковой ФС каждый элемент реализует определённую физическую операцию. Такая реализация происходит на основе одного или нескольких физико-технических эффектов (ФТЭ).

            ФТЭ – это различные приложения физических законов, закономерностей и следствий из них, физические эффекты и явления, которые могут быть использованы в технических устройствах. Как правило, в физико-технических эффектах имеется определённая причинно-следственная связь между «входом» и «выходом». Физико-технический эффект должен иметь стандартное формализованное описание, удобное для технических приложений и машинной обработки. Наиболее обобщённое качественное описание физико-технического эффекта состоит из трёх компонент:

            (A, B, C),         или      (A → B → C),

где A – входной поток вещества, энергии или информации; C – выходной поток; B – физический объект, обеспечивающий или осуществляющий преобразование A в C. Например, ФТЭ “Закон Джоуля – Ленца” имеет вид:

электрический ток → проводник → теплота.

 

 

Модель поиска новых технических решений

 

Для поиска ФПД (или новых технических решений) необходимо использовать некоторую модель представления и хранения знаний, в которой учитывают:

-         физико-технические эффекты ФТЭ;

-         физические операции ФО;

-         базу параметров;

-         приборы измерения параметров;

-         приборы изменения параметров, которые фактически представляют собой реализованные технические решения;

Имеется прямое соответствие между операцией Коллера в ФО и объектом в ФТЭ. Для большего удобства операцию Коллера E и объект B следует заключить в одну структуру, объединив таким образом ФО и ФТЭ.

Поиск представляет собой перебор возможных вариантов в цепочке из нескольких преобразований с учётом качественных и/или количественных ограничений входных и выходных потоков. Следует также отметить комбинаторную сложность поставленной задачи. Ведь при глубине поиска 5 и более задача представляется трудноразрешимой при прямом переборе вариантов решения.

Покажем общую структуру поиска, представленную на следующем рисунке.

 

 

 

 

Рисунок 1. Поиск цепочек при известных ФТЭ

 

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

 

Абдукция

 

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

Пусть ABD и OBS - некоторые множества формул пропозициональных формул. Элементы ABD представляют собой те формулы, которые могут быть результатами абдукции; они называ­ются абдуцентами. Элементами OBS служат те формулы, которые могут представлять результа­ты наблюдений. Пусть KB - некоторое конечное множество формул, называемое базой знаний; КВ = {α₁, α₂, … , α_n}.

Задача абдукции заключается в поиске таких формул X  Î ABD, что множество KB и {X} вы­полнимо (логически непротиворечиво) и что из KB u {X} логически следует данное наблюдение δ Î OBS. (При этом предполагается, что наблю­дение δ не следует из КВ). Ясно, что следует пред­почитать кратчайшие и логически минимальные формулы X.

Задачу абдукции можно сформулировать так:

            Найти все кратчайшие логически сильнейшие решения X  Î ABD уравнения

            α₁ & α₂, …  α_n & X & ~δ ==0,

не являющийся решением уравнения

            α₁ & α₂, …  α_n & X ==0

            Рассмотрим также задачу дедукции в следую­щей форме. Пусть KB = { α₁, α₂, … , α_n } - база зна­ний и GL - некоторое множество формул, рассма­триваемых как цели дедукции. Нужно найти все кратчайшие и логически минимальные формулы X Î GL, которые логически следовали бы из КВ. Переформулируем задачу:

                Найти все кратчайшие и логически сильнейшие решения X  Î GL уравнения

            α₁ & α₂, …  α_n & ~X ==0

            Этих два примера имеют общую форму:

            Пусть Φ[Х] и Ψ[X] - какие-либо формулы, составленные из обычных логических свя­зок и пропозициональных переменных, а также с использованием метапеременной X, значениями которой служат формулы от пропозициональных переменных, входящих в формулы Φ и Ψ. Пусть C- некоторое мно­жество формул (от тех же пропозицио­нальных переменных). Нужно найти все кратчайшие и логически сильнейшие фор­мулы из C, которые служат решениями уравнения Ф[Х] = = 0, но не являются реше­ниями уравнения Ψ [Х] = = 0.

                Эту общую задачу обозначим Z(Φ, Ψ, C). Рассмотрим некоторые подходы к решению этой задачи.

1.                Уравнение Ф[Х]==0. Формулу Ф[Х] можно разложить по переменной X: .

Ф[Х] = = Ф[1] & X v Ф[0] & ~X.

где Ф[0] и Ф[1] - формулы, полученные из Ф[Х] подстановками X=0 и X=1.

Доказывая справедливость логической экви­валентности, заметим, что в произвольной интерпретации I будем иметь

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & I(X) v I(Ф[0]) & ~I(X)

Возможны два случая: I(X)=0, I(X)=1. В первом случае имеем

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & 0 v I(Ф[0]) & 1 = I(Ф[0]) = I(Ф[X]),

а во втором

I(Ф[1] & X v Ф[0] & ~X) = I(Ф[1]) & 1 v I(Ф[0]) & 0 = I(Ф[1]) = I(Ф[X]).

Таким образом, в обоих случаях Ф[Х] и Ф[1] & X v Ф[0] & ~X имеют одинаковые значения в интерпретации I.

            2. Решение задачи Z(Φ, Ψ, C). Мы рассматриваем здесь эту задачу в самом общем случае, ког­да Ф и Ψ - произвольные формулы, содержащие
метапеременную X, а С- множество всех формул. Метод решения этой задачи включает 5 этапов.

                Этап 1. Подставляя 0 и 1 вместо X в формулу Ф[Х], получаем Ф[0] и Ф[1], которые затем упрощаем, применяя правила замены ~~αÞα; α& 0Þ0; α & 1Þα; α  v 0Þα; α v 1Þ1; 0→α =1; α ↔ 0Þ ~α; α ↔ 0Þα. Пусть Ф` и Ф`` - формулы, полученные в результате этих упрощений.

            Этап 2. Проверяем, верно ли, что Ф` ╞ Ф``. Если неверно, то задача не имеет решения.

                Этап 3. Приводим формулы Ф` и ~Ф`` к СДНФ. Пусть D(Ф`) и D(Ф``) – полученные СДНФ. Найдём все СДНФ Y такие, что D(Ф`) :< Y :< D(Ф``). Пусть Y₁, Y₁,…, Y_m, - найденные СДНФ.

            Этап 4. Находим среди Y_i такие, что формула Ψ[Y_i] не является тождественно ложной. Из найденных формул выбираем минимальные по отношению :<. Пусть Z₁, Z₂,…, Z_r – отобранные формулы. Таким образом, не верно, что Z_i ╞ Z_j, если i ≠ j, и для каждой формулы Y_k, такой, что Ψ[Y_k] нетождественно ложна, существует форму­ла Z_i, такая, что Z_i  ╞ Y_k .

                Этап 5. Для каждой формулы Z_i находим кратчайшую формулу X_i, эквивалентную Z_i. Мно­жество {X₁, X₂, ..., X_r} представляет все кратчай­шие и логически сильнейшие формулы, которые являются решениями уравнения Ф[Х] == 0, но не являются решениями уравнения Ψ[Х] = = 0.

3. Задача абдукции. Мы рассматриваем задачу абдукции следующего типа. Пусть множество используемых в задаче пере­менных разбито на два подмножества: P = {p₁, p₂, ..., p_m} и Q = {q₁, q₂, ..., q_n}. Переменные p_i назы­ваются абдуцируемыми, а переменные q_j - наблюдаемыми. Любую конъюнкцию из абдуцируемых переменных или их отрицаний будем счи­тать абдуцентом, а любую конъюнкцию из наблюдаемых переменных или их отрицаний бу­дем считать наблюдением. Множество всех абдуцентов и всех наблюдений обозначаем через ABD и OBS соответственно. Пусть КВ = {α₁, α₂, … , α_n} – база знаний из произвольных формул α_j, состав­ленных из переменных p_i и q_j .

Фрейм абдукции – это F = (P, Q, ABD, OBS, KB). При заданном наблюдении δ Î OBS задача абдук­ции <F, δ> во фрейме F заключается в нахождении кратчайших и логически сильнейших абдуцентов X Î ABD, таких, что KB, X ╞ δ, но не верно, что KB╞  δ. Ясно, что задача абдукции <F, δ> совпада­ет с задачей Z(Φ, Ψ, ABD), где

Ф = α₁ & α₂ & … & α_k & ~δ & X,

Ψ = α₁ & α₂ & … & α_k & X.

 

 

 

Основные результаты работы

 

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

 

 

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

 

1.        Автоматизация поискового конструирования/ Под ред. А.И. Половинкина. М.: Радио и связь, 1981. 344 с.

2.        Альтшуллер Г.С. Алгоритм изобретения. М.: Московский рабочий, 1973. 296 с.

3.        Водяхо А.И., Мельцов В.Ю., Страбыкин Д.А. и др. Формальная система дедуктивного логического вывода в рамках логики высказываний // Изв. ГЭТУ. Сб. научн. тр. Вып. 458. С.-Пб.: ГЭТУ,     1993.

4.        Плесневич Г.С. Логические уравнения и задачи дедукции и абдукции // Известия академии наук. Теория и системы управления, 2000, №5, с. 75-82.

5.        Плесневич Г.С., Сапаров М.С. Алгоритмы в теории графов. Ашхабад. Ылым, 1981.

6.        Половинкин А.И. Законы строения и развития техники/ Учеб. пособие. Волгоград: ВолгПИ, 1985. 202 с.

7.        Половинкин А.И. Основы инженерного творчества/ Учеб. пособие. М.: Машиностроение, 1988. – 368 с.