Лекция 7. Нечеткие знания и способы их обработки

 

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

Работа с нечеткостью.

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

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

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

В алгоритме используются оценочные функции, построенные на основе априорных оценок стоимости пути до целевого состояния. Для поиска в пространстве состояний используются дерево поиска и методы горизонтального (в ширину) и вертикального (в глубину) поиска на этом дереве. Основные шаги и понятия алгоритма рассмотрим на примере игры в «8», являющейся усеченной версией игры в «15». Целью игры является переход из некоторого начального состояния в конечное состояние, как показано на рис. 22.

 

Рис. 22. Переход из начального в конечное состояние при игре в «8».

 

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

· перемещение пустого квадрата влево;

·  перемещение пустого квадрата вверх;

· перемещение пустого квадрата вниз;

· перемещение пустого квадрата вправо.

Оценочная функция f(n) будет формироваться как стоимость оптимального пути к цели из начального состояния через nвершин дерева поиска. Дерево поиска для данного примера показано на рис. 23. Значение оценочной функции в n-й вершине можно представить как сумму двух составляющих f(n) = g(n) + h(n), где g(n) - стоимость оптимального пути от первой вершины до n -й; h(n) - стоимость оптимального пути от n -й вершины до цели.

 Для простоты будем считать, что стоимость перемещения пустого квадрата равна 1. Оптимальным будет путь, имеющий минимальную стоимость. Точное значение f(n) в процессе поиска неизвестно, поэтому введем априорную оценку значения функции: , где  - глубина пройденного пути на дереве поиска от первой до n -ой вершины;  - априорное значение h(n).

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

 

 

Рис. 23. Дерево поиска для игры «8»

 

Основные шаги алгоритма:

1. Определяются все возможные операторы над пустым квадратом в начальном состоянии и выбирается вариант с наименьшим значением ;

2. Применяется выбранный оператор и при его использовании получается новое состояние;

3. Создаются вершины следующего уровня иерархии, исходя из анализа всех возможных операторов для перехода в новое состояние;

4. Выбирается состояние с наименьшим значением ;

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

При разработке алгоритма на игре в «8» важно, чтобы . Если априорная оценка стоимости оптимального пути не превышает истинной стоимости, то нахождение оптимального пути гарантировано. Это условие можно интерпретировать следующим образом: цель поиска не будет достигнута, пока число шашек, находящихся не на своих местах, больше числа перемещений. Если  выбрать по-другому, например , то будет осуществляться горизонтальный поиск на дереве состояний задачи, при котором раскрываются все вершины нижеследующего уровня.

В области некорректных задач точные знания о проблеме получить невозможно, поэтому приходиться сталкиваться с неточными знаниями, которые не могут быть интерпретированы как полностью истинные или ложные. Для оценки их достоверности также нельзя применить двухбалльную шкалу: логические true/false или 0/1. Существуют знания, достоверность которых выражается некоторой промежуточной цифрой, которая может изменяться от 0 до 1. Для учета нечетких знаний при разработке ИИС используется формальный аппарат нечеткой(fuzzy) алгебры и нечеткой логики, предложенный математиком Л. Заде.

Одно из главных понятий в нечеткой логике - это понятие лин­гвистической переменной (ЛП), значение которой определяется набором словесных (вербальных) характеристик некото­рого свойства. Например, ЛП «рост» соответствуют следующие характеристики карликовый, низкий, средний, высокий, очень высокий. Значения лингвистической переменной (ЛП) находится через нечеткие множества(НМ), определяемые на некотором базовомнаборе значений или базовой числовой шкале, имеющей размерность. Для определения НМ рассмотрим пример: пусть имеется нечеткое множество Т всех высокихлюдей, входящих во множество людей S. Введем для каждого человека степень его принадлежно­сти множеству Т. Функцию принадлежности ,оп­ределяющую в какой степени можно считать высоким человека ростом hсан­тиметров, представим в виде:

 

где h - рост конкретного человека в сантиметрах.

Если рост человека h =163 см, тогда истинность высказывания, что этот человек высок будет = 0.21. Использованная в данном случае функция принад­лежности тривиальна. При решении большинства реальных задач подобные функции имеют более сложный вид и содержат большое число аргументов. Методы построения функций принадлежности для нечетких множеств довольно разнообразны. В большинстве случаев функция принадлежности определяет субъективную степень уверенностиэксперта в том, что данное конкретное значение базовой шкалы соответст­вует определяемому НМ. Эту функцию не стоит путать с вероятностью, но­сящей объективный характер и подчиняющейся другим математическим зависимостям.

Экспертные системы, основанные на нечеткой логике.

Правила нечеткого вывода в ЭС описываются в терминах теории НМ (нечётких множеств). Как правило, они имеют вид: «если ценавелика и спроснизкий, то оборотмал». Здесь «цена» и «спрос» используются в качестве входных переменных, «оборот» - как выходное значение. Характеристики «велик», «низкий» и «мал» являются функциями принадлежности НМ. Эти функции определяются на множествах значений «цены», «спроса»и «оборота» соответственно. Нечеткие правила вывода образуют базу правил. В нечеткой экспертной системе все правила работают одновременно, однако степень их влияния на выход может быть различной. Принцип вычисления суперпозиции многих влияний на окончательный результат лежит в основе нечетких экспертных систем. Процесс обработки нечетких правил вывода в экспертной системе состоит из четырех этапов:

1. Определение степени принадлежности входных значений НМ, указанным в левой части правил вывода;

2. Модификация НМ, указанных в правой части правил вывода в соответствии со значениями истинности, получен­ными на первом этапе;

3. Объединение (суперпозиция) модифицированных множеств;

4. Скаляризация результата суперпозиции, то есть переход от НМ к скалярным значениям.

Для определения степени истинности левой части каждого правила нечеткая экспертная система вычисляет значения функций принадлежности НМ от соответствующих значений входных переменных. Например, для правила «если ценавелика и спроснизкий, то оборотмал» определяется степень вхождения конкретного значения переменной «цена»в нечеткое множество «велика», то есть истинность предиката «цена велика». К вычисленным значениям истинности могут применяться логические операции. Наиболее часто используются следующие определения операций нечеткой логики:

truth (НЕ x) = 1 - truth (x),

truth(x И у) = min [truth(x), truth(y)],

truth(x ИЛИ у)  = max[truth(x), truth(y)],

 

где x и у - высказывания; truth (z) - степень истинности высказывания z.

 

Полученное значение истинности используется для модификации НМ, указанного в правой части правила. Для выполнения такой модификации используют один из двух методов: «минимума» и «произведения» Метод «минимума» (рис. 24 а) огра­ничивает функцию принадлежности для множества, указанного в правой части правила, значением истинности левой части. Метод «произведение» (рис. 24 б) использует значение истинности левой части как коэффи­циент, на который умножаются значения функции принадлежности. Результат выполнения правила - нечеткое множество, то есть происходит ассоциирование переменной и функции принадлежности, указанных в правой части. Выходы всех правил вычисляются нечеткой экспертной системой отдель­но, однако в правой части нескольких из них может быть указана одна и та же нечеткая переменная. При определении обобщенного результата необходимо учитывать все правила. Для этого система производит суперпозицию нечетких множеств, связанных с каждой из таких переменных. Эта операция называется нечетким объединением правил вывода.

                       а)

 

                        б)

Рис. 24 а,б. Модификация НМ. а – Метод «минимума». б – Метод «произведение».

 

 

Процесс обработки нечетких правил вывода поясним на примере. Правая часть правил:  

содержит одну и ту же переменную - «спрос». Два нечетких множества, получаемые при выполнении этих правил, должны быть объединены экспертной системой. Традиционно суперпозиция функций принадлежности нечетких множеств , ,…,   определяется как:

             "x, i Î [1, n].

Графическое представление подобной суперпозиции приведено на рис. 25.

 

 

                          Рис. 25. Метод «Max Combination».

Другой метод суперпозиции состоит в суммировании значений всех функ­ций принадлежности. Графическая интерпретация метода приведена на рис. 26.

 

Рис. 26. Метод "Sum Combination".

Самым простым, но и наименее часто используемым, является подход, когда суперпозиция не производится. Выбирается одно из правил вывода, результат которого используется в качестве интегрального результата. Конечный этап обработки базы правил вывода - это переход от нечетких значений к конкретным скалярным. Процесс преобразования нечеткого множества в единственное значение называется скаляризацией. В качестве такого значения часто используется «центр тяжести» функции принадлежности нечеткого множества (рис. 27).

Рис. 27. Скаляризация методом «центра тяжести».

Другой распространенный подход - использование максимального значения функции принадлежности (рис. 28). Конкретный выбор методов суперпозиции и скаляризации осуществляется в зависимости от желаемого поведения нечеткой экспертной системы.

Рис. 28. Скаляризация методом «максимума».

Рассмотрим пример того, как обрабатываются нечеткие правила вывода в экспертной системе, управляющей вентилятором комнатного кондиционера. Задача кондиционера - поддерживать оптимальную температуру воздуха в комнате, охлаждая его, когда жарко, и нагревая, когда холодно. Алгоритм работы кондици­онера может быть задан следующими правилами:

1. Если температура воздуха в комнате высокая, то скорость вращения вентилятора высокая;

2. Если температура воздуха в комнате средняя, то скорость вращения вентилятора средняя;

3. Если температура воздуха в комнате низкая, то скорость вращения вентилятора низкая.

Для того чтобы система могла обрабатывать эти правила, надо задать функции принадлежности для нечетких множеств, определенных на значениях температуры () и скорости вращения вентилятора (). Пусть температура воздуха в комнате находится в пределах от 0 °С до 60 °С. В противном случае кондиционер вряд ли поможет, функцию принадлежности для нечеткого множества «низкая»,определенную на интервале изменения температуры, можно задать как показано на рис. 29. Если температура меньше 12 °С, то это определенно низкая температура для комнаты = 1 при t < 12 °С. Температуру выше 20 °С никак нельзя назвать низкой, поэтому   при  t > 20 °С. В промежутке между этими значениями функция принадлежности линейно убывает, то есть с увеличением температуры уменьшается истинность утверждения «температура воздуха в комнате низкая».

 

                                                                                           

 

 

Рис. 29. Нечеткое подмножество «низкая», определенное на множестве значений

температуры.

Сходные рассуждения позволяют задать функции принадлежности для оставшихся множеств: «средняя» (рис.30) и «высокая» (рис. 31).

 

Рис. 30. Нечеткое подмножество «средняя», определенное на множестве значений

температуры.

 

 

                                                                      

Рис. 31. Нечеткое подмножество «высокая», определенное на множества

значений температуры.

Определим нечеткие подмножества для скорости вращения вентилятора. Пусть скорость может изменяться от 0 до 1000 об/мин. Допустимым будет следующий вариант определения функций принадлежности для нечетких множеств скорости «низкая», «средняя» и «высокая» (рис. 32 - 34).

 

 

 

Рис. 32. Нечеткое множество «низкая», определенное на множестве значении скорости вращения вентилятора.

 

                                                                       

Рис. 33. Нечеткое подмножество «средняя», определенное на множестве значений скорости вращения вентилятора.

 

 

Рис. 34. Нечеткое множество «высокая», определенное на множестве значений скорости вращения вентилятора.

Рассмотрим теперь, как нечеткая экспертная система определяет скорость вращения вентилятора в зависимости от температуры воздуха в комнате. Пусть эта температура равна 22 °С. Сначала экспертной системе надо определить истинность левых частей правил вывода при подстановке в них текущего значения температуры. Для этого она должна найти степень вхождения t = 22 °С в каждое из указанных слева нечетких множеств. В левых частях правил указаны три множества, заданных на интервале значений температуры: «высокая», «низкая» и «средняя». Степень вхождения находим, вычисляя значение функций принадлежности каждого множеств от t = 22 °С: .

Значения истинности левой части каждого правила используются для модификации нечеткого множества, указанного в его правой части. Модификацию будем производить методом «произведения» На рис. 35 изображено, как трансформируются находящиеся в правых частях правил нечеткие подмножества «высокая», «средняя» и «низкая». Нечеткой экспертной системе необходимо обобщить результаты действия всех правил вывода, то есть произвести суперпозицию полученных нечетких множеств. Воспользуемся методом «Max Combination» (рис. 25). Результат объединения нечетких множеств показан на рис. 36. Осуществим переход от суперпозиции множеств к скалярному значению. Скаляризацию произведем методом «центра тяжести». Иллюстрация того, как получается результат, представлена на рис. 37. Центр тяжести фигуры на рис. 37 находится в точке v = 560.5691. Следовательно экспертная система при температуре воздуха в комнате равной 22 °С определит до целой части значение скорости вращения вентилятора v = 561 об/мин. При других значениях температуры функция принадлежности обобщенного результата выполнения всех правил, изображенная на рис. 37, будет меняться. Если на вход экспертной системы поступит значение t = 28 °С (рис. 38), то центр тяжести в этом случае будет находится в точке           v = 746.6667, что составляет скорость вентилятора 747 об/мин.

 

Рис. 35. Модификация нечетких подмножеств, определенных на интервале изменения скорости вращения вентилятора,

              Рис. 36. Результат суперпозиции нечетких множеств.

 

Рис. 37. Получение скалярного значения скорости вращения вентилятора

методом «центра тяжести» для t = 22 °С.

 

Рис. 38. Получение скалярного значения скорости вращения вентилятора методом «центра тяжести» для температуры t = 28 °С.

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

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

 

 

 

Лекция 8. Основные понятия теории искусственных нейронных сетей.

 

В лекции представлен альтернативный подход к разработке ИИС, основанный на концепции обучения искусственных нейронных сетей. Рассмотрены основные типы и архитектура нейронных сетей, методы адаптации, обучения и настройки параметров.