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

Размещено на http://www.allbest.ru/

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

Серов В.В.

Представлена теория и методы формализации знаний прикладного характера и показана возможность формального решения качественных задач

Ключевые слова: логическое программирование; концепция; методы формализации; теория нечётких множеств; резольвирование; теория Демпстера-Шафера.

Введение

При аналитическом исследовании объектов (в рамках поставленной цели) в формализованных моделях рассматриваются макроструктуры, такие как проблема, система, информационное пространство и т.п., но так или иначе все сводится к решению конкретных прикладных задач.

Существует много формальных и неформальных определений понятия задача, хотя до сих пор не выработано общепринятого. Пойа [1] определяет задачу следующим образом: «Задача предполагает необходимость сознательного поиска соответствующего средства для достижения непосредственно недоступной цели». По Пойа существует два общих типа задач: задачи на нахождение и задачи на доказательство.

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

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

Возможна следующая классификация типов задач:

Класс 1. Задачи, для которых существует формальная схема решений, представленная на неком формальном языке. Решение задач осуществляется по имеющейся схеме (детерминированной или вероятностной).

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

Класс II. Задачи, для которых не существует заранее готовой схемы решения. Для построения схемы решения задач этого класса привлекаются знания о предметной области. Обычно в этом случае человек сам формирует схему решения и в этом состоит его творческая деятельность. После того, как человек построил схему решения, задачи перестают быть интеллектуальными, и дальнейший поиск их решений человеком или с помощью машины не представляет проблемы.

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

В работе [2] проблемы решения задач в теоретико-множественных представлениях формулируется в самом общем виде следующим образом. Пусть любая система описывается тройкой W,Y,N , где W Z область определения отображения T WY, X - множество входных сигналов, Z - множество состояний и Y - множество выходных сигналов системы. Тогда проблема заключается в том, чтобы по заданным множествам W и Y найти требуемые отображения T.

В настоящее время продолжает успешно развиваться концепция, получившая название логического программирования. Важным практическим шагом в указанном направлении было создание языка ПРОЛОГ (PROgramming in LOGic). Основная идея этого языка состояла в том, что нужно на логическом языке описать условие задачи, а решение ее получается как результат некоего рутинного процесса, который исполняется на компьютере. Условие задачи представляет собой множество формул специального вида в языке логики предикатов первого порядка, одна из формул выделена и называется целью, остальные - посылками. Тогда упомянутый процесс состоит в построении доказательства цели из посылок в исчислении, единственным правилом вывода которого является правило резолюции.

Немного о природе знаний

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

Общеизвестно, что в качестве одной из сторон знаний, присущих человеческой природе, является их свойство, характеризующееся в таких понятиях, как нечеткость, случайность, возможность, неясность, правдоподобность. Систематизация представлена в табл.1.

Таблица 1

Методологии исследования

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

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

Фундаментальным понятием в теории нечетких множеств является понятие функции принадлежности.

Пусть М - множество, x - элемент М, тогда нечеткое подмножество А множества М определяется как множество упорядоченных пар {(x,А(x)}, хM, где А(х) - характеристическая функция принадлежности, принимающая свои значения во вполне упорядоченном множестве Е, которая указывает степень или уровень принадлежности элемента х подмножеству А. Множество Е называется множеством принадлежности. Если Е = {0,1}, то нечеткое подмножество А рассматривается как обычное подмножество.

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

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

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

Систематизация прикладных задач качественного характера

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

Ограничимся рассмотрением прикладных знаний, для которых существует область посылок (причин) и область результатов (следствий). Связи между посылками и результатами могут быть логическими и структурными, конкретными и опосредованными, явными и скрытыми, объективными и субъективными, определенными и нечеткими.

Представим описанную модель следующим образом: P R, где Р- область посылок, R- область результатов, - обобщенный оператор причинно-следственных связей. Будем считать, что задача включает в себя формулировку F и условия решения C. Очевидно, что Р, R, F и С могут содержать известные и неизвестные величины, условно назовем их константами и переменными. В рамках предлагаемой модели возможна следующая классификация прикладных задач качественного характера:

1. Формулировка задачи включает в себя преимущественно переменные и относится к области результатов, FR. Условия задачи включают в себя константы и относятся к области посылок, CР. Такую задачу отнесем к классу задач прогнозирования. В результате решения задачи устанавливаются значения переменных, содержащихся в формулировке задачи F.

2. Формулировка задачи включает в себя преимущественно константы и относится к области результатов, FR. Условия задачи включают в себя преимущественно константы и относятся к области посылок, CР. Такую задачу отнесем к классу задач интерпретации. В результате решения задачи устанавливаются значения переменных, содержащихся в формулировке задачи F и, возможно, в условиях C.

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

Области задач прогнозирования и интерпретации пересекаются и между ними нельзя провести четкую границу (вчерашний прогноз погоды сегодня может использоваться для интерпретации условий его составления).

3. Формулировка задачи включает в себя преимущественно переменные и относится к области посылок, FР. Условия задачи включают в себя преимущественно константы и относятся к области результатов, CR. Такую задачу отнесем к классу задач идентификации. В результате решения задачи устанавливаются значения переменных, содержащихся в формулировке задачи F и, возможно, в области посылок Р.

В формализме исчисления нечетких предикатов задача идентификации не имеет решения, т.к. дизъюнкты из пар F и P, R и С имеют одинаковую форму и одинаковые знаки, - при резольвировании невозможно сформировать пустой дизъюнкт.

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

Системные вопросы решения задач качественного характера

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

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

Второй уровень - осознанные (рефлексные) знания специалиста Кr. К ним относятся понятия и представления, теории, методы расчетов и решения задач, известные соотношения, эмпирические закономерности.

Знания первого и второго уровней Ко и Кr описанные в научной и технической литературе, специалист получает и уточняет в процессе обучения и в практической работе.

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

Для того чтобы успешно решать задачи, специалист должен владеть знаниями первого и второго уровней и быть достаточно подготовленным к общению с ФРС. В свою очередь, ФРС должна содержать в себе знания третьего уровня Кf, адекватные знаниям Ко и Кr, иметь возможность их пополнять, уточнять, информировать специалиста, понимать его цели, анализировать умение пользоваться ФРС и, в случае необходимости, обучать знаниям Кf .

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

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

Выделим в знаниях следующие категории: предмет, свойство, операция, отношение.

Определим предмет А как объект, который может быть назван, представлен, воспринят, использован.

Предмет может находиться в различных состояниях, каждое из которых определяется множеством значений его свойств {Hi}.

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

Определим изменение как процесс или переход предмета из одного состояния в другое. Под операцией будем понимать любое воздействие на предмет, приводящее к его изменению.

Как предметы, так и операции находятся в различных отношениях друг к другу. Отношения могут быть формальными и неформальными. Определение формального отношения обычно вводится через декартово произведение множеств. Пусть заданы множества М1,М2,...Мn предметов, свойств, операций. Тогда R является n - местным отношением на этих n множествах, если R есть подмножество декартова произведения М1М2...Мn, т.е. множество упорядоченных последовательностей (m1,m2,...,mn), при этом m1М1, m2М2,...,mnМn. Из множества формальных отношений выделим базовые отношения ФРС - предикаты. Для объектных и рефлексных знаний кроме формального характерно неформальное понятие отношения, отражающее взаимосвязь элементов множеств без привязки к конкретному множеству. Примеры таких отношений - часть, больше. В процессе общения РРС и ФРС осуществляют взаимные преобразования формальных и неформальных отношений.

Определим систему S как множество совместно рассматриваемых предметов, свойств, операций, отношений, т.е. S={{A},{H},{D},{R}}. Систему S={{A},{H},{D},{R}} будем называть подсистемой S, если справедливы выражения {A}{A},{H}{H},{D}{D},{R}{R}.

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

Определим предметную область как тройку К=(Кo,К2,Кf), где Кo - объектные знания, К2 - осознанные (рефлексные) знания, Кf - формальные знания компьютера. Знания для каждого из трех рассмотренных уровней определим как четверку К=({Ai},{Hi},{Pi},{Ri}), где {Ai},{Hi, {Pi},{Ri} множества предметов, свойств, процедур, отношений.

Прикладную качественную задачу определим как тройку Т=(Кin, ,Kcres), где Кin и Кres - исходное и результирующее состояние предметной области, а - активизированное подмножество знаний, включающее в себя элементы множеств {Ai},Hi},{Pi},{Ri}, значения которых в исходном положении неизвестны, а в результатирующим определены, а также все элементы рассмотренных множеств, необходимые для решения задачи.

Двойку Тr=(Кres,act) назовем результатом решения, двойку Тi=(Кin,act) - постановкой (формулировкой) задачи. Процесс решения задачи - это изменение исходного состояния предметной области в результирующее, т.е. Кin в Кres. Систему, обеспечивающую решение задачи, будем называть решающей системой (РС). В рамках рассматриваемой теории процесс решения происходит во взаимодействии рефлексной (специалист) и формальной (ЭВМ) решающих систем.

Локальной задачей (подзадачей) Tl задачи Т будем называть тройку Тl=(Кin,act,Klres), где act является подмножеством res, Кin- исходное состояние предметной области, Кlres - результирующее состояние после решения локальной задачи, при этом задачу Т можно представить как Т=(Кin, res, act, Кres).

Будем называть определенной задачу, у которой в активизированном подмножестве знаний act содержатся все элементы, необходимые для ее решения. В противном случае задачу будем считать неопределенной.

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

В зависимости от того, какой РС или ее подсистемой решается задача, она может быть внутренней или внешней. Например, для ФРС внешней является задача обучения специалистов, внутренней - формирование сети декларативных знаний.

Заключение

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

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

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

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

1. Polya G. Mathematics and plausidle reasoning (2 vols). Princeton, 1954. Рус. пер.: Математика и правдоподобные рассуждения. М.: Наука, 1975.

2. Мesarovic M.D. Foundations for general system theory. In: Views on Gen. Syst. Theory. New York; London; Sydney: Wiley, 1964. Рус.пер.: Общая теория систем. М.: Мир, 1966.

3. Серов В. В. Логическое представление нечетких знаний и его применение для решения прикладных задач качественного характера. М.: РосЗИТЛП, 2001.

4. Тэрано Т. Введение в нечеткие системы. / Сб. Прикладные нечеткие системы. Под ред. Тэрано Т., Асаи К., Сугэно М. М.:Мир, 1993.

Размещено на Allbest.ru