Основные понятия и определения теории нечетких множеств

Основные понятия и определения теории нечетких множеств При помощи нечетких множеств можно формально определить неточные и многозначные понятия, такие как «высокая температура», «молодой человек», «средний рост» либо «большой город». Перед формулированием определения нечеткого множества необходимо задать так называемую область рассуждений (universe of discourse). В случае неоднозначного понятия «много денег» большой будет признаваться одна сумма, если мы ограничимся диапазоном [0, 1000 руб] и совсем другая - в диапазоне [0, 1000000 руб]. Область рассуждений, называемая в дальнейшем пространством или множеством, будет чаще всего обозначаться символом . Необходимо помнить, что  - четкое множество. Определение 3.1 Нечетким множеством  в некотором (непустом) пространстве , что обозначается как , называется множество пар ,                    (3.1) где                         (3.2) - функция принадлежности нечеткого множества . Эта функция приписывает каждому элементу  степень его принадлежности к нечеткому множеству , при этом можно выделить три случая: 1)  означает полную принадлежность элемента  к нечеткому множеству , т.е. ; 2)  означает отсутствие принадлежности элемента  к нечеткому множеству , т.е.; 3)  означает частичную принадлежность элемента  к нечеткому множеству . В литературе применяется символьное описание нечетких множеств. Если  - это пространство с конечным количеством элементов, т.е. , то нечеткое множество  записывается в виде .                        (3.3) Если  - это пространство с бесконечным количеством элементов, то нечеткое множество  символически записывается в виде .                     (3.8) Пример 3.1 Допустим, что  - множество натуральных чисел. Определим понятие множества натуральных чисел, «близких числу 7». Это можно сделать определением следующего нечеткого множества : .               (3.9) Пример 3.2 Если , где  - множество действительных чисел, то множество действительных чисел, «близких числу 7», можно определить функцией принадлежности вида .                        (3.10) Поэтому нечеткое множество действительных чисел, «близких числу 7», описывается выражением .                  (3.11) 1. Функция принадлежности класса  (рис. 3.2) определяется как                        (3.15) где . Функция принадлежности, относящаяся к этому классу, имеет графическое представление (рис. 3.2), напоминающее букву «», причем ее форма зависит от подбора параметров ,  и . В точке  функция принадлежности класса  принимает значение, равное 0,5. Рис. 3.2. Функция принадлежности класса . 2. Функция принадлежности класса  (рис. 3.3) определяется через функцию принадлежности класса :                   (3.16) Функция принадлежности класса  принимает нулевые значения для  и . В точках  ее значение равно 0,5. Рис. 3.3. Функция принадлежности класса . 3. Функция принадлежности класса  (рис. 3.4) задается выражением              (3.17) Рис. 3.4. Функция принадлежности класса . 4. Функция принадлежности класса  (рис. 3.5) определяется в виде                         3.18) Рис. 3.5. Функция принадлежности класса . 5. Функция принадлежности класса  (рис. 3.6) определяется выражением                (3.19) Рис. 3.6. Функция принадлежности класса . Пример 3.5 На рис. 3.8 показана функция принадлежности нечеткого множества «большие деньги». Это функция класса , причем , , . Рис. 3.8. Иллюстрация к примеру 3.5: Функция принадлежности нечеткого множества «большие деньги». Следовательно, суммы, превышающие 10000 руб, можно совершенно определенно считать «большими», поскольку значения функции принадлежности при этом становятся равными 1. Суммы, меньшие чем 1000 руб, не относятся к «большим», так как соответствующие им значения функции принадлежности равны 0. Определение 3.2 Множество элементов пространства , для которых , называется носителем нечеткого множества  и обозначается  (support). Формальная его запись имеет вид .                    (3.20) Определение 3.3 Высота нечеткого множества  обозначается  и определяется как .              (3.21) Пример 3.6 Если  и ,  то . Если  и , то . Определение 3.4 Нечеткое множество  называется нормальным тогда и только тогда, когда . Если нечеткое множество  не является нормальным, то его можно нормализовать при помощи преобразования ,                 (3.24) где  - высота этого множества. Определение 3.5 Нечеткое множество  называется пустым и обозначается  тогда и только тогда, когда  для каждого . Определение 3.6 Нечеткое множество  содержится в нечетком множестве , что записывается как , тогда и только тогда, когда                      (3.27) для каждого . Пример включения (содержания) нечеткого множества  в нечетком множестве  иллюстрируется на рис. 3.9. В литературе встречается также понятие степени включения нечетких множеств. Степень включения нечеткого множества  в нечеткое множество  на рис. 3.9 равна 1 (полное включение). Нечеткие множества, представленные на рис. 3.10, не удовлетворяют зависимости (3.27), следовательно, включение в смысле определения (3.6) отсутствует. Однако нечеткое множество  содержится в нечетком множестве  в степени ,                    (3.28) где . Рис. 3.9. Включение нечеткого множества  в нечеткое множество . Рис. 3.10. Содержание нечеткого множества  в нечетком множестве  в степени . Определение 3.7 Нечеткое множество  равно нечеткому множеству , что записывается как , тогда и только тогда, когда                     (3.29) для каждого . Приведенное определение, также как и определение 3.6, нельзя считать «эластичным», поскольку оно не учитывает случай, когда значения функций принадлежности  и  почти равны между собой. В такой ситуации можно ввести понятие степени равенства нечетких множеств  и , например, в виде ,                      (3.30) где . Определение 3.8 -разрезом нечеткого множества , обозначаемым как , называется следующее четкое множество: ,                 (3.31) т.е. множество, определяемое характеристической функцией               (3.32) Определение -разреза нечеткого множества иллюстрирует рис. 3.11. Легко заметить истинность импликации .                      (3.33) Рис. 3.11. Иллюстрация определения -разреза нечеткого множества . Пример 3.8 Рассмотрим нечеткое множество                        (3.34) причем . В соответствии с определением 3.8 конкретные -разрезы определяются в виде ,                , ,              , ,                 . Определение 3.9 Нечеткое множество  является выпуклым тогда и только тогда, когда для произвольных  и  выполняется условие .                      (3.35) Определение 3.10 Нечеткое множество  является вогнутым тогда и только тогда, когда для произвольных  и  выполняется условие .                     (3.36) Легко проверить, что нечеткое множество  является выпуклым (вогнутым) тогда и только тогда, когда являются выпуклыми (вогнутыми) все его -разрезы. Операции на нечетких множествах Определение 3.11 Пересечением нечетких множеств  называется нечеткое множество  с функцией принадлежности                        (3.37) для каждого . Графическая интерпретация этой операции представлена на рис. 3.14. Пересечение нечетких множеств  определяется функцией принадлежности                                     (3.38) для каждого . Рис. 3.14. Графическое представление операции пересечения нечетких множеств. Рис. 3.15. Графическое представление операции алгебраического произведения. Замечание 3.2 В литературе помимо определения понятия «пересечение» (intersection) нечетких множеств также встречается определение понятия «алгебраическое произведение» (algebraic product) этих множеств. Алгебраическое произведение нечетких множеств  и  - это нечеткое множество , определенное как .                  (3.39) Графическая интерпретация этой операции представлена на рис. 3.15. Определение 3.12 Сумма нечетких множеств  и  - нечеткое множество , определенное функцией принадлежности                        (3.40) для каждого . Графическая интерпретация этой операции представлена на рис. 3.16. Функция принадлежности суммы нечетких множеств  выражается зависимостью                       (3.41) для каждого . Рис. 3.16. Графическое представление операции суммирования нечетких множеств. Следует помнить, что свойство выпуклости нечетких множеств сохраняется для их пересечения, а свойство вогнутости - для их суммы, т.е. 1) если  и  - выпуклые нечеткие множества, то  - выпуклое нечеткое множество; 2) если  и  - вогнутые нечеткие множества, то  - вогнутое нечеткое множество. Пример 3.9 Допустим, что  и                   (3.42)                   (3.43) В соответствии с определением 3.11 получаем .                (3.44) В силу определения 3.12 имеем .                (3.45) В то же время алгебраическое произведение нечетких множеств  и , заданное выражением (3.39), принимает вид .              (3.46) В литературе известна так называемая теорема о декомпозиции. Она позволяет представить произвольное нечеткое множество  в виде суммы нечетких множеств, генерируемых -разрезами множества . Теорема 3.1 Любое нечеткое множество  можно представить в виде ,                     (3.47) где  означает нечеткое множество, элементам которого приписаны следующие степени принадлежности:                   (3.48) Замечание 3.3 В литературе известны и другие, отличающиеся от 3.11 и 3.12 определения пересечения и суммы нечетких множеств. б)                              (3.50), (3.51) в)                                    (3.52), (3.53) г)                    (3.54)                     (3.55) д) ,                     (3.56)                                       (3.57) для . Как станет ясно из п. 3.7, операцию пересечения нечетких множеств можно определить с помощью так называемой -нормы, тогда как операцию суммирования - с помощью так называемой -нормы. Таким образом, формулы (3.37), (3.50), (3.52), (3.54) и (3.56) - это примеры реализации -нормы (операция пересечения), тогда как формулы (3.40), (3.51), (3.53), (3.55) и (3.57) - это примеры реализации -нормы (операция суммирования). Определение 3.3 Дополнением нечеткого множества  называется нечеткое множество  с функцией принадлежности                 (3.62) для каждого . Графическая интерпретация операции дополнения представлена на рис. 3.18. Рис. 3.18. Графическое представление операции дополнения нечеткого множества. Пример 3.11 Допустим, что , а также .                   (3.63) В соответствии с определением 3.13 дополнением множества  считается множество .              (3.64) Определение 3.14 Декартово произведение нечетких множеств  и  обозначается  и определяется как                     (3.71) или               (3.72) для каждого  и . Декартово произведение нечетких множеств   будем обозначать  и определим как                     (3.73) либо                        (3.74) для каждого . Пример 3.12 Допустим, что ,  и ,                       (3.75) .              (3.76) При использовании для декартова произведения нечетких множеств  и  формулы (3.71) получаем .                   (3.77) Другие алгебраические операции на нечетких множествах играют важную роль в семантике лингвистических переменных (см. пункт 3.8). Определение 3.15 Концентрация нечеткого множества  обозначается  и определяется как                   (3.78) для каждого . Определение 3.16 Разбавление нечеткого множества  обозначается  и определяется как                   (3.79) для каждого . Графическая интерпретация операции концентрации и разбавления представлена на рис. 3.20. Рис. 3.20. Графическое представление операций концентрации и разбавления нечеткого множества. Пример 3.13 Если  и ,                (3.80) то в соответствии с определениями (3.15) и (3.16) получаем ,             (3.81) .               (3.82) Нечеткое отношение  между двумя непустыми множествами (четкими)  и  будем называть нечеткое множество, определенное на декартовом произведении , т.е. .                          (3.157) Другими словами, нечеткое отношение - множество пар ,                     (3.158) где                       (3.159) - это функция принадлежности, которая каждой паре  приписывает ее степень принадлежности , которая интерпретируется как сила связи между элементами  и . В соответствии с принятым соглашением (п. 3.2) нечеткое отношение можно представить в виде                  (3.160) или .                (3.161) Пример 3.22 Применим определение 3.26 для формализации неточного утверждения « примерно равно ». Пусть  и . Отношение  можно определить следующим образом: .                        (3.162) Следовательно, функция принадлежности  отношения  имеет вид                        (3.163) Отношение  можно также задать в виде матрицы ,                                  (3.164) где , , , а , , . Следует подчеркнуть, что нечеткое отношение  - это нечеткое множество, поэтому сохраняют силу введенные в п. 3.3 определения операций пересечения, суммирования и дополнения: ,                 (3.166) ,                (3.167) .                   (3.168) В теории нечетких множеств важную роль играет понятие комбинации двух нечетких отношений. Рассмотрим три четких множества , ,  и два нечетких отношения  и  c функциями принадлежности  и . Определение 3.27 Комбинацией типа  нечетких отношений  и  называется нечеткое отношение с функцией принадлежности .                       (3.169) Конкретная форма функции принадлежности  комбинации  зависит от -нормы, используемой в формуле (3.169). Если в качестве -нормы применяется , т.е. , то равенство (3.169) можно представить в виде .                    (3.170) Формула (3.170) известна в литературе под названием «комбинация типа sup-min». Если множество  имеет конечное количество элементов, то комбинация типа sup-min сводится к комбинации типа max-min в форме .                   (3.171) В таблице 3.2 собраны важнейшие свойства нечетких отношений, причем  означает единичную матрицу, а  - нулевую матрицу. Таблица 3.2. Важнейшие свойства нечетких отношений 1 2 3 4 5 6 7 8 Нечеткий вывод В традиционной (двоичной) логике решения об истинности одних суждений выводятся на основании истинности других суждений. Подобный вывод задается в виде схемы: над горизонтальной чертой записываются все суждения, на основании которых принимается решение, а под чертой - полученный результат. Схема корректного вывода обладает тем свойством, что поскольку истинны все суждения над чертой, то истинно также и суждение под чертой, так как из истинных суждений может выводиться только истинный результат. В настоящем разделе заглавными буквами  и  будут записываться суждения, а не нечеткие множества. Пусть  и  - это суждения, причем запись  () означает, что логическим значением суждения  () считается «истина», тогда как запись  () означает, что логическим значением суждения  () считается «ложь». Представим теперь два правила вывода, применяемых в двоичной логике. Определение 3.29 Правило вывода modus ponens (первая форма гипотетического силлогизма) определяется следующей схемой вывода: Условие Импликация (3.187) Вывод Пример 3.26 Пусть суждение  имеет вид «Ян является водителем», а суждение  - «У Яна есть водительское удостоверение». В соответствии с правилом modus ponens, если ,то и , поскольку если истинно, что «Ян является водителем», то также истинно, что «У Яна есть водительское удостоверение». Другими словами, из истинности предпосылки и импликации (суждения над чертой) следует истинность вывода (суждения под чертой). Определение 3.30 Правило вывода modus tollens (вторая форма гипотетического силлогизма) определяется следующей схемой вывода: Условие Импликация             (3.188) Вывод Пример 3.27 Продолжая пример 3.26, можно понять, что если «У Яна нет водительского удостоверения», т.е.  (), то «Ян не является водителем», т.е.  (). В этом примере тоже из истинности предпосылки и импликации следует истинность вывода. Мы представили всего два правила вывода в двоичной логике, которые будут обобщаться на случай нечеткости. Расширим теперь основные правила вывода в двоичной логике на случай нечеткости. Допустим, что присутствующие в правилах modus ponens (3.187) и modus tollens (3.188) суждения характеризуются некоторыми нечеткими множествами. Таким способом мы получаем обобщенное правило вывода modus ponens и обобщенное правило вывода modus tollens. В последующем изложении зависимости типа «Если , то » будем записывать в символике классического языка программирования ALGOL в виде IF A THEN В. Обобщенное нечеткое правило modus ponens Определение 3.31 Обобщенное (нечеткое) правило вывода modus ponens определяется следующей схемой вывода: Условие Импликация  это  IF  это  THEN  это  (3.189) Вывод  это  где  и  - нечеткие множества, в то время как  и  - так называемые лингвистические переменные. Пример 3.28 Рассмотрим следующую схему вывода: Условие Импликация   Скорость автомобиля большая Если скорость автомобиля очень большая, то уровень шума высокий (3.190) Вывод Уровень шума в автомобиле не очень высокий В приведенной схеме условие, импликация и вывод - неточные утверждения. В качестве лингвистических переменных выделим:  - скорость автомобиля,  - уровень шума. Множество {«малая», «средняя», «большая», «очень большая»} - множество значений лингвистической переменной . Аналогично множество {«малый», «средний», «не очень высокий», «высокий»} - множество значений лингвистической переменной . Каждому элементу множеств  и  можно приписать соответствующее нечеткое множество. В результате анализа схем вывода (3.189) и (3.190) получаем следующие нечеткие множества: «очень большая скорость автомобиля», «большая скорость автомобиля» и «высокий уровень шума», «не очень высокий уровень шума». Рассмотрим различия между четким (3.187) и нечетким (3.189) правилами. В обоих случаях импликация имеет один и тот же вид , где  и  - это суждения (правило 3.187) либо нечеткие множества (правило 3.189). Нечеткая импликация  равнозначна некоторому нечеткому отношению  с функцией принадлежности . Поэтому функцию принадлежности нечеткого множества  можно представить с помощью формулы (3.176), которая записывается в виде ,                   (3.192) причем . В частном случае, когда -норма имеет тип min, формула (3.192) принимает вид .                       (3.193) Теперь допустим, что применяется импликация  из схемы (3.189), а нечеткое множество  (условие) последовательно принимает значения: ; «очень », причем ; «почти », причем ; «не », причем . Нечеткое множество «очень » определяется при помощи операции концентрации (3.78), нечеткое множество «почти » - при помощи операции разбавления (3.79), а нечеткое множество «не » - при помощи операции дополнения (3.62). Обобщенное нечеткое правило modus tollens Определение 3.32 Обобщенное (нечеткое) правило вывода modus tollens определяется следующей схемой вывода: Условие Импликация  это  IF  это  THEN  это              (3.195) Вывод  это  где  и  - это нечеткие множества, в то время как  и  - это лингвистические переменные. Пример 3.29 Данный пример следует из примера (3.28), причем сохраняет силу описание, соответствующее схеме (3.190): Условие Импликация   Уровень шума в автомобиле не очень высокий Если скорость автомобиля очень большая, то уровень шума высокий                         (3.196) Вывод Скорость автомобиля большая Нечеткое множество  в выводе схемы (3.195) определяется комбинацией отношений ,                 (3.197) причем .                  (3.198) Если -норма имеет тип min, то формула (3.198) принимает вид .                       (3.199) Правила нечеткой импликации В предыдущем пункте мы обсуждали обобщенные нечеткие схемы вывода modus ponens и modus tollens. Функции принадлежности (3.198) и (3.192) в выводах этих схем зависят от функции принадлежности  нечеткой импликации , которая равнозначна некоторому нечеткому отношению . Представим различные способы задания функции  на основе известных функций принадлежности  и . Определение 3.33 Пусть  и  - это нечеткие множества,  и . Нечеткой импликацией  называется отношение , определенное на  и удовлетворяющее следующим правилам: 1. Правило типа minimum .                    (3.201) Это правило называется «правилом Мамдани». 2. Правило типа «произведение» .               (3.202) Это правило известно под названием «правило Ларсена». 3. Правило Лукашевича .            (3.203) 4. Правило типа max-min              (3.204) Это правило известно под названием «правило Заде». 5. Бинарное правило         (3.205) 6. Правило Гогуэна .                (3.206) 7. Правило Шарпа              (3.207) 8. Правило Гёделя              (3.208) 9. Вероятностное правило                       (3.209) 10. Правило ограниченной суммы                   (3.210) Набор этих десяти правил не исчерпывает все известные из литературы определения нечеткой импликации. Нечеткое управление Для многих приложений, связанных с управлением технологическими процессами, необходимо построение модели рассматриваемого процесса. Знание модели позволяет подобрать соответствующий регулятор (модуль управления). Однако часто построение корректной модели представляет собой трудную проблему, требующую иногда введения различных упрощений. Применение теории нечетких множеств для управления технологическими процессами не предполагает знания моделей этих процессов. Следует только сформулировать правила поведения в форме нечетких условных суждений типа IF ... THEN. Классический модуль нечеткого управления На рис. 3.26 представлена типовая структура модуля нечеткого управления. Он состоит из следующих компонентов: базы правил, блока фуззификации (fuzzification), блока выработки решения, блока дефуззификации. База правил База правил, иногда называемая лингвистической моделью, представляет собой множество нечетких правил , , вида : IF ( это  AND  это  … AND  это ) THEN ( это  AND  это  … AND  это ),           (3.224) где - количество нечетких правил,  - нечеткие множества , ,                   (3.225)  - нечеткие множества , ,                (3.226)  - входные переменные лингвистической модели,     причем ,                    (3.227)  - выходные переменные лингвистической модели, причем .                   (3.228) Символами ,  и ,  обозначаются соответственно пространства входных и выходных переменных. Для дальнейших рассуждений примем, что конкретные правила ,  связаны между собой логическим оператором «ИЛИ». Кроме того, допустим, что выходы  взаимно независимы. Поэтому без утраты общности будем использовать нечеткие правила со скалярным выходом в форме : IF ( это  AND  это  … AND  это ) THEN ( это ),                     (3.229) где  и . Заметим, что каждое правило вида (3.229) состоит из части IF, называемой посылкой (antecedent), и части THEN, называемой следствием (consequent). Посылка правила содержит набор условий, тогда как следствие содержит вывод. Переменные  и  могут принимать как лингвистические (например, «малый», «средний», «большой»), так и числовые значения. Блок фуззификации Система управления с нечеткой логикой оперирует нечеткими множествами. Поэтому конкретное значение  входного сигнала модуля нечеткого управления подлежит операции фуззификации, в результате которой ему будет сопоставлено нечеткое множество . В задачах управления чаще всего применяется операция фуззификации типа синглетон (singleton):                   (3.234) Нечеткое множество  подается на вход блока выработки решения. Если входной сигнал поступает зашумленным, то нечеткое множество  можно определить функцией принадлежности ,                     (3.235) где . В этом случае операция фуззификации имеет тип non-singleton. Блок выработки решения Допустим, что на вход блока выработки решения подано нечеткое множество . На выходе этого блока также появится соответствующее нечеткое множество. Рассмотрим два случая, которым будут соответствовать различные методы дефуззификации (п. 3.9.1.4). Случай 1 На выходе блока выработки решения в соответствии с обобщенным нечетким правилом modus ponens получаем  нечетких множеств . Условие     Импликация    это  ,              (3.236) Вывод  это ,  Нечеткое множество  определяется комбинацией нечеткого множества  и отношения , т.е. , .               (3.237) При использовании определения 3.28 можно задать функцию принадлежности нечеткого множества  в виде .              (3.238) Случай 2 На выходе блока выработки решения получаем одно нечеткое множество  по обобщенному нечеткому правилу modus ponens, которое принимает вид Условие     Импликация    это  ,              (3.245) Вывод  это  При использовании комбинированного правила вывода получаем ,                  (3.246) где . В силу определений 3.12 и 3.28 получаем .                      (3.247) Заметим, что вывод по схеме (3.245) - это результат комбинирования посылки  и глобального правила (отношения) , которое представляет собой обобщение отдельных правил , . Будем называть такой прием глобальным подходом к проблеме синтеза блока выработки решения. Пример 3.35 Рассмотрим модуль нечеткого управления с базой правил : IF ( это  AND  это ) THEN ( это ),             (3.250) : IF( это  AND  это ) THEN ( это ).                        (3.251) На его вход подан сигнал . После выполнения фуззификации типа синглетон на входе блока выработки решения получаем нечеткие множества  и , причем , .                    (3.252) Обозначим выходной сигнал модуля нечеткого управления символом . Воспользуемся выражением (3.238), которое принимает вид .                 (3.253) В качестве -нормы будем применять операцию minimum. Кроме того, допустим, что                   (3.254) В этом случае                        (3.255) В качестве нечеткой импликации                  (3.256) можно применить одно из десяти правил, представленных в п. 3.8.3. При использовании правила типа minimum получаем .               (3.257) Кроме того, .                       (3.258) В результате                      (3.259) .                       (3.260) На рис. 3.27 представлена графическая интерпретация нечеткого вывода. Рис. 3.27. Иллюстрация к примеру 3.35. Блок дефуззификации На выходе блока выработки решения формируется либо  нечетких множеств  (случай 1, п. 3.9.1.3) с функциями принадлежности , , либо одно нечеткое множество  (случай 2, п. 3.9.1.3) с функцией принадлежности . Встает задача отображения нечетких множеств  (либо нечеткого множества ) в единственное значение , которое представляет собой управляющее воздействие, подаваемое на вход объекта. Такое отображение называется дефуззификацией (defuzzification), и реализуется оно в одноименном блоке. Если на выходе блока выработки решения формируется  нечетких множеств , то значение  можно рассчитать с помощью различных методов. 1. Метод дефуззификации по среднему центру (сenter average defuzzification). Значение  рассчитывается по формуле ,             (3.269) где  - это точка, в которой функция  принимает максимальное значение, т.е. .                  (3.270) Точка  называется центром (center) нечеткого множества . На рис. 3.33 представлена идея этого метода для . Обратим внимание, что значение  не зависит от формы и носителя функции принадлежности . Рис. 3.33. Иллюстрация метода дефуззификации по среднему центру. 2. Метод дефуззификации по сумме центров (center of sums defuzzification). Значение  рассчитывается следующим образом: .                       (3.271) Если выходное значение блока выработки решения представляет собой единственное нечеткое множество , то значение  можно определить с применением следующих двух методов. 3. Метод центра тяжести (center of gravity method, center of area method). Значение  рассчитывается как центр тяжести функции принадлежности , т.е.                   (3.272) при условии, что оба интеграла в приведенном выражении существуют. На рис. 3.34 иллюстрируется способ определения значения  по методу центра тяжести. Рис. 3.34. Иллюстрация метода центра тяжести. 4. Метод максимума функции принадлежности. Значение  рассчитывается в соответствии с формулой                         (3.273) при условии, что  - это унимодальная функция. Этот метод не учитывает форму функции принадлежности, что иллюстрируется на рис. 3.35. Рис. 3.35. Иллюстрация метода максимума функции принадлежности Нечетким числом называется нечеткое множество , определенное на множестве действительных чисел , функция принадлежности которого отвечает условиям: 1)      , т.е. нечеткое множество  нормализовано; Точной (наименьшей) верхней гранью (границей), или супре́мумом (лат. supremum — самый высокий) подмножества упорядоченного множества (или класса) , называется наименьший элемент , который равен или больше всех элементов множества . Другими словами, супремум — это наименьшая из всех верхних граней. Обозначается . Точной (наибольшей) нижней гранью (границей), или и́нфимумом (лат. infimum — самый низкий) подмножества упорядоченного множества (или класса) , называется наибольший элемент , который равен или меньше всех элементов множества . Другими словами, инфимум — это наибольшая из всех нижних граней. Обозначается . 2)      ,  т.е. множество  выпуклое. В теории нечетких систем различаются положительные и отрицательные нечеткие числа. Определение 3.20 Нечеткое число  положительно, если  для всех . Нечеткое число  отрицательно, если  для всех . Определение 3.21 Основные арифметические операции на нечетких числах  определяются следующим образом: а) суммирование двух нечетких чисел  и  обозначается ,                        (3.102) причем функция принадлежности суммы (3.102) задается выражением (3.94) в виде ,               (3.103) б) вычитание двух нечетких чисел  и  обозначается ,            (3.104) причем функция принадлежности разности (3.104) задается выражением (3.94) в виде ,               (3.105) в) умножение двух нечетких чисел  и  обозначается ,                        (3.106) причем функция принадлежности произведения (3.106) задается выражением (3.94) в виде ,                (3.107) г) деление двух нечетких чисел  и  обозначается ,             (3.108) причем функция принадлежности частного (3.108) задается выражением (3.94) в виде .                (3.109) Пример 3.18 Сложим и перемножим два нечетких числа, имеющих вид ,               (3.110) .               (3.111) В соответствии с формулой (3.103) получаем     (3.112) На основании выражения (3.107) получаем        (3.113) В приведенном примере мы сложили и перемножили два нечетких числа (3.110) и (3.111), получив в качестве суммы нечеткое множество (3.112), а в качестве произведения - нечеткое множество (3.113). Легко проверить, что нечеткие множества (3.112) и (3.113) являются нормальными и выпуклыми, и что они представляют собой нечеткие числа. Однако результатом арифметических операций над нечеткими числами не всегда оказывается нечеткое число, поскольку получается нечеткое множество (3.98), которое не является нечетким числом, т.к. оно не отвечает условию выпуклости. Эта проблема устраняется тогда, когда операции выполняются над нечеткими числами, имеющими непрерывные функции принадлежности, что утверждается следующей теоремой: Теорема 3.2 (Дюбуа и Прейда [9]) Если нечеткие числа  и  имеют непрерывные функции принадлежности, то результатом арифметических операций суммирования, вычитания, умножения и деления будут нечеткие числа. Мы обсудили основные двухаргументные (бинарные) операции на нечетких множествах. Одноаргументные (унарные) операции определяются также с помощью принципа расширения. Если - отображение                  (3.114) и , , то в соответствии с формулой (3.90) получаем ,                     (3.115) где . Приведем теперь несколько примеров унарных операций на нечетких числах. 1. Операция изменения знака. В результате операции  получаем нечеткое число, противоположное нечеткому числу . Это число обозначается - , а его функция принадлежности равна .               (3.116) Нечеткие числа  и  симметричны относительно оси . 2. Операция обращения. В результате операции , , получаем нечеткое число, обратное нечеткому числу . Это число обозначается , а его функция принадлежности равна .             (3.117) Предполагается, что нечеткое число  положительно или отрицательно. Если  таковым не является, то нечеткое множество  не выпукло и, следовательно,  не может считаться нечетким числом. 3. Операция масштабирования. В результате операции , , получаем нечеткое число, масштабированное относительно нечеткого числа . Это число обозначается , а его функция принадлежности равна .                        (3.118) 4. Операция экспонирования. В результате операции , , получаем степень нечеткого числа . Это число обозначается , а его функция принадлежности равна                        (3.119) поэтому  - положительное нечеткое число. 5. Операция расчета абсолютного значения. Абсолютное значение нечеткого числа  обозначается  и определяется как                        (3.120) Очевидно, что  - положительное нечеткое число. Пример 3.19 Если ,                (3.121) то нечеткое число  имеет вид ,                        (3.122) тогда как нечеткое число  записывается в виде .                      (3.123) Арифметические операции над нечеткими числами требуют проведения достаточно сложных вычислений. Поэтому Дюбуа и Прейд [8] предложили некоторую частную форму представления нечетких чисел при помощи трех параметров, что значительно упрощает нечеткую арифметику. Пусть  и  - функции, выполняющие отображение                     (3.126) и удовлетворяющие условиям: 1) , , 2) , , 3)  и  - функции, невозрастающие на интервале . В качестве примеров функций  и  можно привести , ,                        (3.127) , ,                     (3.128) , ,                   (3.129)                    (3.130) Приведем теперь определение нечеткого числа типа . Определение 3.22 Нечеткое число  будет унимодальным нечетким числом типа  тогда и только тогда, когда его функция принадлежности имеет вид             (3.131) где  - действительное число, называемое средним значением нечеткого числа ,  - положительное действительное число, называемое левосторонним разбросом,  - положительное действительное число, называемое правосторонним разбросом. Заметим, что при увеличении разбросов  и  число  становится «более» нечетким. Нечеткое число типа  можно сокращенно записать в виде .             (3.132) Лингвистическими называются переменные, значения которых представляют собой слова или суждения на естественном языке. В качестве примеров можно привести выражения типа «малая скорость», «умеренная температура» или «молодой человек». Подобные выражения можно формализовать приписыванием им некоторых нечетких множеств. Следует подчеркнуть, что лингвистические переменные помимо словесных значений могут иметь и численные значения - также, как обычные математические переменные. Арифметические операции над нечеткими числами типа  сводятся к операции над тремя параметрами. Нечеткое число, противоположное нечеткому числу (3.132), равно .             (3.135) Сумма нечетких чисел  и  имеет вид .               (3.136) Другие арифметические операции (например, умножение и деление) над нечеткими числами типа  более сложны. Функция принадлежности  нечеткого числа типа  принимает значение 1 только в точке . Модифицируем теперь определение 3.22 так, чтобы  не только в единственной точке , но и во всех точках на интервале , где  и . В этом случае мы получаем определение так называемого плоского (двумодального) нечеткого числа. Это определение можно использовать для моделирования нечетких интервалов. Определение 3.23 Плоским нечетким числом типа  называется нечеткое число с функцией принадлежности               (3.137) Плоское нечеткое число  можно отождествить с нечетким интервалом  вида .                        (3.138) Пример 3.21 Рассмотрим неточное утверждение «стоимость велосипеда в этом магазине составляет от 3 до 6 тысяч рублей». Адекватной формализацией этого утверждения может считаться нечеткий интервал  вида .                             (3.139) На рис. 3.24 представлен примерный график функции принадлежности нечеткого интервала (3.139). Рис. 3.24. Иллюстрация к примеру 3.21: нечеткий интервал «от 3 до 6 тысяч рублей». Треугольные нормы В пункте 3.3 операции пересечения и суммирования нечетких множеств были определены как , . Вместе с тем подчеркивалось, что это не единственные определения указанных операций. Пересечение нечетких множеств можно задать в более общем виде как ,                    (3.140) где функция  - это так называемая -норма. Поэтому  можно считать примером действия -нормы. Аналогично, сумму нечетких множеств можно определить следующим образом: ,                    (3.141) где функция  - это так называемая -норма. В этом случае  можно считать примером действия -нормы. - и -нормы относятся к классу так называемых треугольных норм. Определение 3.24 Функция  двух переменных                        (3.142) называется -нормой, если: 1) функция  является невозрастающей относительно обоих аргументов  для , ,             (3.143) 2) функция  удовлетворяет условию коммутативности ,                  (3.144) 3) функция  удовлетворяет условию связности ,                      (3.145) 4) функция  удовлетворяет граничным условиям , ,                   (3.146) где . Произвольная -норма ограничивается следующим образом: ,                    (3.147) где  - это -норма вида                  (3.148) В последующем описании реализацию -нормы на аргументах  и  будем обозначать .                    (3.149) Если, например,  и  отождествить с функциями принадлежности нечетких множеств  и , то равенство (3.140) можно представить в виде .             (3.450) Определение 3.25 Функция  двух переменных                        (3.151) называется -нормой, если она является невозрастающей относительно обоих аргументов, удовлетворяет условию коммутативности и связности, а также граничным условиям .                      (3.152) Функция  также называется ко-нормой либо дополняющей нормой относительно -нормы. Произвольная норма ограничивается следующим образом: ,                   (3.153) где  есть - норма вида                 (3.154) Реализацию -нормы на аргументах  и  будем обозначать .                    (3.155) Следует подчеркнуть, что каждой -норме соответствует -норма, а зависимость между ними выражается равенством .                      (3.156) В таблице 3.1 представлены наиболее часто встречающиеся - и -нормы. Таблица 3.1. Треугольные нормы № Параметры 1   2   3   4   5 6 Биологический прототип Развитие искусственных нейронных сетей вдохновляется биологией. Это проявляется в том, что, рассматривая сетевые конфигурации и алгоритмы, исследователи мыслят их в терминах организации мозговой деятельности. Нервная система человека, построенная из элементов, называемых нейронами. Каждый нейрон обладает способностью принимать, обрабатывать и передавать электрохимические сигналы по нервным путям, которые образуют коммуникационную систему мозга. Рис. 1. Биологический нейрон На рис. 1 показана структура пары типичных биологических нейронов. Дендриты идут от тела нервной клетки к другим нейронам, где они принимают сигналы в точках соединения, называемых синапсами. Принятые синапсом входные сигналы подводятся к телу нейрона. Здесь они суммируются, причем одни входы стремятся возбудить нейрон, другие – воспрепятствовать его возбуждению. Когда суммарное возбуждение в теле нейрона превышает некоторый порог, нейрон возбуждается, посылая по аксону сигнал другим нейронам. Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом другого нейрона. Каждый вход умножается на соответствующий вес, аналогичный синапсической силе, и все произведения суммируются, определяя уровень активации нейрона. Рис. 1.2. Искусственный нейрон Здесь множество входных сигналов, обозначенных х1, х2,..., хn поступает на искусственный нейрон. Эти входные сигналы соответствуют сигналам, приходящим в синапсы биологического нейрона. Каждый сигнал умножается на соответствующий вес w1, w2,..., wm и поступает на суммирующий блок. Каждый вес соответствует «силе» одной биологической синапсической связи. Суммирующий блок, соответствующий телу биологического элемента, складывает взвешенные входы алгебраически, создавая выход. В векторных обозначениях это может быть компактно записано следующим образом: NET = XW. Активационные функции Сигнал NET, как правило, преобразуется активационной функцией F и дает выходной нейронный сигнал OUT. Активационная функция может быть обычной линейной функцией OUT = К(NET), где К - постоянная, пороговой функции OUT = 1, если NET > Т, OUT = 0 в остальных случаях, где Т - некоторая постоянная пороговая величина. Рис. 3. Искусственный нейрон с активационной функцией На рис. 3 блок, обозначенный F, принимает сигнал NET и выдает сигнал OUT. Если блок F сужает диапазон изменения величины NET так, что при любых значениях NET значения OUT принадлежат некоторому конечному интервалу, то F называется «сжимающей» функцией. В качестве «сжимающей» функции часто используется логистическая или «сигмоидальная» (S-образная) функция. Эта функция математически выражается как F(x) = 1/(1 + е-х). Таким образом, По аналогии с электронными системами активационную функцию можно считать нелинейной усилительной характеристикой искусственного нейрона. Центральная область логистической функции, имеющая большой коэффициент усиления, решает проблему обработки слабых сигналов, в то время как области с падающим усилением на положительном и отрицательном концах подходят для больших возбуждений. Рис. 4. Сигмоидальная логистическая функция Другой широко используемой активационной функцией является гиперболический тангенс: Рис. 5. Функция гиперболического тангенса Подобно логистической функции гиперболический тангенс является S-образной функцией, но он симметричен относительно начала координат и в точке NET = 0 значение выходного сигнала OUT равно нулю. Многослойные искусственные нейронные сети Хотя один нейрон и способен выполнять простейшие процедуры распознавания, сила нейронных вычислений проистекает от соединения нейронов в сетях. Простейшая сеть состоит из группы нейронов образующих слой. Отметим, что вершины-круги слева служат лишь для распределения входных сигналов. Они не выполняют каких-либо вычислений, и поэтому не будут считаться слоем. По этой причине они обозначены кругами, чтобы отличать их от вычисляющих нейронов, обозначенных квадратами. Каждый элемент из множества входов X отдельным весом соединен с каждым искусственным нейроном. А каждый нейрон выдает взвешенную сумму входов в сеть. Рис. 6. Однослойная нейронная сеть Удобно считать веса элементами матрицы W. Матрица имеет m строк и n столбцов, где m - число входов, a n- число нейронов. Таким образом, вычисление выходного вектора N, компонентами которого являются выходы OUT нейронов, сводится к матричному умножению N = XW, где N и X - векторы-строки. Более крупные и сложные нейронные сети обладают, как правило, и большими вычислительными возможностями. Многослойные сети обладают большими возможностями, чем однослойные. Многослойные сети могут образовываться каскадами слоев. Выход одного слоя является входом последующего слоя. Многослойные сети могут привести к увеличению вычислительной мощности по сравнению с однослойной сетью лишь в том случае, если активационная функция между слоями будет нелинейной. Многослойные нейронные сети, где все связи направлены строго от входных нейронов к выходным, называют сетями прямого распространения. Сети более общего вида, имеющие соединения от выходов к входам, называются сетями с обратными связями или реккурентными нейронными сетями. У сетей без обратных связей нет памяти, их выход полностью определяется текущими входами и значениями весов. В некоторых конфигурациях сетей с обратными связями предыдущие значения выходов возвращаются на входы; выход, следовательно, определяется как текущим входом, так и предыдущими выходами. По этой причине сети с обратными связями могут обладать свойствами, сходными с кратковременной человеческой памятью, сетевые выходы частично зависят от предыдущих входов. Рис. 7. Двухслойная нейронная сеть Помимо этого существуют радиально базисные функции – это вид нейронной сети, имеющий скрытый слой из радиальных элементов и выходной слой из линейных элементов. Сети этого типа довольно компактны и быстро обучаются. Предложены в работах Broomhead and Lowe (1988) и Moody and Darkin (1989). Общий вид радиально-базисной функции: , например, функция Гаусса, где  - вектор входных сигналов нейрона,  - ширина окна функции,  - убывающая функция (чаще всего, равная нулю вне некоторого отрезка). Радиально-базисная сеть характеризуется тремя особенностями: 1. Единственный скрытый слой; 2. Только нейроны скрытого слоя имеют нелинейную активационную функцию; 3. Синаптические веса связей входного и скрытого слоев равны единице. Выходом сети является линейная комбинация радиальных базисных функций входов и параметров нейрона. Сети радиальных базисных функций имеют множество применений, в том числе функции приближения, прогнозирования временных рядов, классификации и системы управления. Самоорганизующиеся карты или Сети Кохонена – сети такого класса способны выявлять новизну во входных данных: если после обучения сеть встретится с набором данных, непохожим ни на один из известных образцов, то она не сможет классифицировать такой набор и тем самым выявит его новизну. Сеть Кохонена имеет всего два слоя: входной и выходной, составленный из радиальных элементов. Классификация нейронных сетей Классификация нейронных сетей по настройке весов делит их на: • сети с фиксированными связями – весовые коэффициенты нейронной сети выбираются сразу, исходя из условий задачи; • сети с динамическими связями – для них в процессе обучения происходит настройка синаптических весов. По типу входной информации различают сети: • аналоговая – входная информация представлена в форме действительных чисел; • двоичная – вся входная информация в таких сетях представляется в виде нулей и единиц. Классификация нейронных сетей по характеру обучения делит их на: • нейронные сети, использующие обучение с учителем; • нейронные сети, использующие обучение без учителя. Нейронные сети, использующие обучение с учителем. Обучение с учителем предполагает, что для каждого входного вектора существует целевой вектор, представляющий собой требуемый выход. Вместе они называются обучающей парой. Обычно сеть обучается на некотором числе таких обучающих пар. Предъявляется выходной вектор, вычисляется выход сети и сравнивается с соответствующим целевым вектором. Далее веса изменяются в соответствии с алгоритмом, стремящимся минимизировать ошибку. Векторы обучающего множества предъявляются последовательно, вычисляются ошибки и веса подстраиваются для каждого вектора до тех пор, пока ошибка по всему обучающему массиву не достигнет приемлемого уровня. Нейронные сети, использующие обучение без учителя. Обучение без учителя является намного более правдоподобной моделью обучения с точки зрения биологических корней искусственных нейронных сетей. Развитая Кохоненом и многими другими, она не нуждается в целевом векторе для выходов и, следовательно, не требует сравнения с предопределенными идеальными ответами. Обучающее множество состоит лишь из входных векторов. Обучающий алгоритм подстраивает веса сети так, чтобы получались согласованные выходные векторы, т.е. чтобы предъявление достаточно близких входных векторов давало одинаковые выходы. Процесс обучения, следовательно, выделяет статистические свойства обучающего множества и группирует сходные векторы в классы. Алгоритм решения задач с помощью многослойной нейронной сети Чтобы построить МНС, необходимо выбрать ее параметры. Общий алгоритм решения: 1. Определить, какой смысл вкладывается в компоненты входного вектора. Входной вектор должен содержать формализованные условия задачи, т.е. всю информацию, необходимую для получения ответа. 2. Выбрать выходной вектор таким образом, чтобы его компоненты содержали полный ответ поставленной задачи. 3. Выбрать вид нелинейности в нейронах (функцию активации). При этом желательно учесть специфику задачи, т.к. правильный или удачный выбор существенно сократит время обучения. 4. Выбрать число слоев и нейронов в слое. 5. Задать диапазон изменения входов, выходов, весов и пороговых уровней, учитывая множество значений выбранной функции активации. 6. Присвоить начальные значения весовым коэффициентам и пороговым уровням и дополнительным параметрам. Начальные значения не должны быть большими, чтобы нейроны не оказались в насыщении, иначе обучение будет очень медленным. Начальные значения не должны быть и слишком малыми, чтобы выходы большей части нейронов не были равны нулю, иначе обучение также замедлится. 7. Провести обучение, т.е. подобрать параметры сети так, чтобы задача решалась наилучшим образом. По окончании обучения сеть готова решить задачи того типа, которым она обучена. 8. Подать на вход сети условия задачи в виде вектора. Рассчитать выходной вектор, который дает формализованное решение задачи. Задачи, решаемые искусственными нейронными сетями Решаемые нейронными сетями задачи весьма разнообразны. Неудивительно, что этот метод нашел применение в таких сферах, как медицина, финансовый менеджмент и политическая наука. В целом можно свести основную часть решаемых с помощью ИНС проблем к нескольким категориям задач. Классификация. Задачей нейронной сети является распределение объектов по нескольким заранее установленным непересекающимся классам. Пример с распознаванием рукописных цифр относится именно к этой категории задач: ИНС устанавливает соответствие объекта одному из десяти классов (цифры от 0 до 9). Известны компьютерные программы ИНС, выполняющие функции распознавания текста, речи, отнесения предприятия к классу «перспективных» или «убыточных», классификации клеток крови и сигналов электрокардиограммы, установления подлинности подписи и многие другие. Задачи классификации наиболее близки к дискриминантному анализу, который также определяет принадлежность объекта к одной из заранее заданных групп. В то же время нейронные сети и дискриминантный анализ ведут к достижению этой цели разными путями: дискриминантный анализ строит линейную дискриминантную функцию, тогда как нейронные сети нелинейны по своей природе. Соответственно, они могут «схватывать» связи между переменными, не поддающиеся описанию с помощью линейных функций. Кластеризация. Кластеризация представляет собой распределение объектов по группам сходства/различия. Основное отличие этой категории задач от классификации состоит в том, что кластеры не задаются заранее. Различия между категориями задач классификации и кластеризации иллюстративны с точки зрения выбора метода обучения сети. Так, если целью исследования является классификация объектов, абсолютно логичным является обучение «с учителем». Чтобы сеть «поняла» правила отнесения объектов к заранее определенным классам, необходимо во всех случаях четко показывать принадлежность объекта из обучающей выборки к определенному классу. Задача кластеризации, напротив, предполагает обучение «без учителя». Алгоритм ее основан на подобии образов и размещает близкие образы в один кластер. Кластеризация позволяет представить неоднородные данные в более наглядном виде и использовать далее для исследования каждого кластера различные методы. Помимо этого искусственные нейронные сети успешно используются для аппроксимация многомерных функций, задача распознавания образов и прогнозирования. Области применения искусственных нейронных сетей Экономика и бизнес: прогнозирование временных рядов (курсов валют, цен на сырьё, объемов продаж и т.д.), автоматический трейдинг (торговля на валютной, фондовой или товарной бирже), оценка рисков невозврата кредитов, предсказание банкротств, оценка стоимости недвижимости, выявление переоцененных и недооцененных компаний, рейтингование, оптимизация товарных и денежных потоков, считывание и распознавание чеков и документов, безопасность транзакций по пластиковым картам. Медицина: постановка диагноза, обработка медицинских изображений, мониторинг состояния пациента, анализ эффективности лечения, очистка показаний приборов от шумов. Авионика: обучаемые автопилоты, распознавание сигналов радаров, адаптивное пилотирование сильно поврежденного самолета, беспилотные летательные аппараты. Связь: сжатие видеоинформации, быстрое кодирование-декодирование, оптимизация сотовых сетей и схем маршрутизации пакетов. Интернет: ассоциативный поиск информации, электронные секретари и автономные агенты в интернете, фильтрация и блокировка спама, автоматическая рубрикация сообщений из новостевых лент, адресные реклама и маркетинг для электронной торговли. Автоматизация производства: оптимизация режимов производственного процесса, контроль качества продукции, мониторинг и визуализация многомерной диспетчерской информации, предупреждение аварийных ситуаций. Робототехника: распознавание сцены, объектов и препятствий перед роботом, прокладка маршрута движения, управление манипуляторами, поддержание равновесия. Политологические и социологические технологии: предсказание результатов выборов, анализ опросов, предсказание динамики рейтингов, выявление значимых факторов, кластеризация электората, исследование и визуализация социальной динамики населения. Безопасность и охранные системы: распознавание лиц; идентификация личности по отпечаткам пальцев, голосу, подписи или лицу; распознавание автомобильных номеров, анализ аэрокосмических снимков, мониторинг информационных потоков в компьютерной сети и обнаружение вторжений, обнаружение подделок. Ввод и обработка информации: распознавание рукописных текстов, отсканированных почтовых, платежных, финансовых и бухгалтерских документов. Геологоразведка: анализ сейсмических данных, ассоциативные методики поиска полезных ископаемых, оценка ресурсов месторождений. ПРОЦЕУРА ОБРАТНОГО РАСПРОСТРАНЕНИЯ Рис. 1. Двухслойная сеть обратного распространения (ε - желаемый сигнал) На рис. 1 изображена многослойная сеть, которая может обучаться с помощью процедуры обратного распространения. Первый слой нейронов (соединенный с входами) служит лишь в качестве распределительных точек, суммирования входов здесь не производится. Входной сигнал просто проходит через них к весам на их выходах. А каждый нейрон последующих слоев выдает сигналы NET и OUT. Процедура обратного распространения применима к сетям с любым числом слоев. Однако для того, чтобы продемонстрировать алгоритм, достаточно двух слоев. Целью обучения сети является такая подстройка ее весов, чтобы приложения некоторого множества входов приводило к требуемому множеству выходов. Для краткости эти множества входов и выходов будут называться векторами. При обучении предполагается, что для каждого входного вектора существует парный ему целевой вектор, задающий требуемый выход. Вместе они называются обучающей парой. Как правило, сеть обучается на многих парах. Например, входная часть обучающей пары может состоять из набора нулей и единиц, представляющего двоичный образ некоторой буквы алфавита. Выход может быть числом, представляющим букву «А», или другим набором из нулей и единиц, который может быть использован для получения выходного образа. При необходимости распознать с помощью сети все буквы алфавита, потребовалось бы 33 обучающие пары (для русского алфавита). Такая группа обучающих пар называется обучающим множеством. Перед началом обучения всем весам должны быть присвоены небольшие начальные значения, выбранные случайным образом. Это гарантирует, что в сети не произойдет насыщения большими значениями весов, и предотвращает ряд других патологических случаев. Например, если всем весам придать одинаковые начальные значения, а для требуемого функционирования нужны неравные значения, то сеть не сможет обучиться. Обучающий алгоритм обратного распространения: 1. Выбрать очередную обучающую пару из обучающего множества, подать входной вектор на вход сети. 2. Вычислить выход сети. 3. Вычислить разность между выходом сети и требуемым выходом (целевым вектором обучающей пары). 4. Подкорректировать веса сети так, чтобы минимизировать ошибку. 5. Повторять шаги с 1 по 4 для каждого вектора обучающего множества пар, пока ошибка на всем множестве не достигнет приемлемого уровня. На шаги 1 и 2 можно смотреть как на «проход вперед», так как сигнал распространяется по сети от входа к выходу. Шаги 3, 4 составляют «обратный проход», здесь вычисляемый сигнал ошибки распространяется обратно по сети и используется для подстройки весов. Проход вперед. Шаги 1 и 2 могут быть выражены в векторной форме следующим образом: подается входной вектор Х, и на выходе получается вектор Y. Векторная пара вход-цель X и Т берется из обучающего множества. Вычисления проводятся над вектором X, чтобы получить выходной вектор Y. Веса между нейронами могут рассматриваться как матрица W. Например, вес от нейрона 8 в слое 2 к нейрону 5 слоя 3 обозначается w8,5. Тогда NET-вектор слоя N может быть выражен не как сумма произведений, а как произведение X и W. В векторном обозначении N = XW. Покомпонентным применением функции F к NET-вектору N получается выходной вектор O. Таким образом, для данного слоя процесс описывается следующим выражением: O = F(XW). (1) Выходной вектор одного слоя является входным вектором для следующего, поэтому вычисление выходов последнего слоя требует применения уравнения (1) к каждому слою от входа сети к ее выходу. Обратный проход. Подстройка весов выходного слоя. Так как для каждого нейрона выходного слоя задано целевое значение, то подстройка весов легко осуществляется с использованием модифицированного дельта-правила. Внутренние слои называют «скрытыми слоями», для их выходов не имеется целевых значений для сравнения. Поэтому обучение усложняется. Здесь показан процесс обучения для одного веса от нейрона p в скрытом слое j к нейрону q в выходном слое k. Выход нейрона слоя k, вычитаясь из целевого значения (Target), дает сигнал ошибки. Он умножается на производную сжимающей функции [OUT(1 - OUT)], вычисленную для этого нейрона слоя k, давая, таким образом, величину δ. δ = OUT(1 - OUT)(Target-OUT). (2) Затем δ умножается на величину OUT нейрона j, из которого выходит рассматриваемый вес. Это произведение в свою очередь умножается на коэффициент скорости обучения η (обычно от 0,01 до 1,0) и результат прибавляется к весу. Такая же процедура выполняется для каждого веса от нейрона скрытого слоя к нейрону в выходном слое. Следующие уравнения иллюстрируют это вычисление: Δwpq,k = η δq,k OUT (3) wpq,k(n+1) = wpq,k(n) + Δwpq,k, (4) где wpq,k(n) - величина веса от нейрона p в скрытом слое к нейрону q в выходном слое на шаге n (до коррекции); отметим, что индекс k относится к слою, в котором заканчивается данный вес, т.е. с которым он объединен; wpq,k(n+l) величина веса на шаге (n + 1) (после коррекции); δq,k - величина δ для нейрона q, в выходном слое k; OUTp,j - величина OUT для нейрона р скрытом слое j. Подстройка весов скрытого слоя. Рассмотрим один нейрон в скрытом слое, предшествующем выходному слою. При проходе вперед этот нейрон передает свой выходной сигнал нейронам в выходном слое через соединяющие их веса. Во время обучения эти веса функционируют в обратном порядке, пропуская величину δ от выходного слоя назад к скрытому слою. Каждый из этих весов умножается на величину δ нейрона, к которому он присоединен в выходном слое. Величина δ, необходимая для нейрона скрытого слоя, получается суммированием всех таких произведений и умножением на производную сжимающей функции: (5) Когда значение δ получено, веса, относящиеся к первому скрытому слою, могут быть подкорректированы с помощью уравнений (3) и (4), где индексы модифицируются в соответствии со слоем. Для каждого нейрона в данном скрытом слое должно быть вычислено δ и подстроены все веса, ассоциированные с этим слоем. Этот процесс повторяется слой за слоем по направлению к входу, пока все веса не будут подкорректированы. С помощью векторных обозначений операция обратного распространения ошибки может быть записана значительно компактнее. Обозначим множество величин δ выходного слоя через Dk и множество весов выходного слоя как массив Wk. Чтобы получить Dj, δ-вектор выходного слоя, достаточно следующих двух операций: 1. Умножить δ-вектор выходного слоя Dk на транспонированную матрицу весов W’k, соединяющую скрытый уровень с выходным уровнем. 2. Умножить каждую компоненту полученного произведения на производную сжимающей функции соответствующего нейрона в скрытом слое. В символьной записи , (6) где оператор здесь обозначает покомпонентное произведение векторов, Oj - выходной вектор слоя j и 1 – вектор, все компоненты которого равны 1. Иллюстрации ниже показывают, как сигнал распространяется по сети в процессе алгоритма обратного распространения ошибки. Символы w(xm)n представляют вес связи между сетевым входом xm и нейрона n во входном слое. Символы y(n) представляют выходной сигнал нейрона n. Распространение сигнала через скрытый слой. Символы wmn представляют весовые множители связей между выходом нейрона m и входом нейрона n в следующем слое. Распространение сигнала через выходной слой. На следующем шаге алгоритма, выходной сигнала сети y сравнивается с желаемым выходным сигналом z, который хранится в обучающей выборке. Разница между этими двумя сигналами называется ошибкой δ выходного слоя сети. Невозможно непосредственно вычислить сигнал ошибки для внутренних нейронов, потому что выходные значения этих нейронов, неизвестны. Идея алгоритма обратного распространения ошибки заключается в распространении сигнала ошибки δ (вычисленного в шаге обучения) обратно на все нейроны, чьи выходные сигналы были входящими для последнего нейрона. Весовые коэффициенты wmn, используемые для обратного распространения ошибки, равны тем же коэффициентам, что использовались во время вычисления выходного сигнала. Только изменяется направление потока данных (сигналы передаются от выхода к входу). Этот процесс повторяется для всех слоёв сети. Если ошибка пришла от нескольких нейронов – она суммируются: Когда вычисляется величина ошибки сигнала для каждого нейрона – можно скорректировать весовые коэффициенты каждого узла ввода (дендрита) нейрона. Коэффициент η влияет на скорость обучения сети. Есть несколько методов для выбора этого параметра. Первый способ – начать обучающий процесс с большим значением параметра η. Во время коррекции весовых коэффициентов параметр постепенно уменьшают. Второй – более сложный метод обучения начинается с малым значением параметра η. В процессе обучения параметр увеличивается, а затем снова уменьшается на завершающей стадии обучения. Добавление нейронного смещения. Во многих случаях желательно наделять каждый нейрон обучаемым смещением. Это позволяет сдвигать начало отсчета логистической функции, давая эффект, аналогичный подстройке порога персептронного нейрона, и приводит к ускорению процесса обучения. Эта возможность может быть легко введена в обучающий алгоритм с помощью добавляемого к каждому нейрону веса, присоединенного к +1. Этот вес обучается так же, как и все остальные веса, за исключением того, что подаваемый на него сигнал всегда равен +1, а не выходу нейрона предыдущего слоя. Модификации алгоритма. Существует метод ускорения обучения для алгоритма обратного распространения, увеличивающий также устойчивость процесса. Этот метод, названный импульсом, заключается в добавлении к коррекции веса члена, пропорционального величине предыдущего изменения веса. Как только происходит коррекция, она «запоминается» и служит для модификации всех последующих коррекций. Уравнения коррекции модифицируются следующим образом: Δwpq,k (n+1)= η δq,k OUTp,j + α Δwpq,k (n) (7) wpq,k(n+1) = wpq,k(n) + Δwpq,k(n+1), (8) где α - коэффициент импульса, обычно устанавливается около 0,9. Используя метод импульса, сеть стремится идти по дну узких оврагов поверхности ошибки (если таковые имеются), а не двигаться от склона к склону. Еще один сходный метод основан на экспоненциальном сглаживании, который может иметь преимущество в ряде приложений. Δwpq,k (n+1)= (1-α) δq,k OUTp,j + α Δwpq,k (n) Затем вычисляется изменение веса wpq,k(n+1) = wpq,k(n) + ηΔwpq.k(n+1), где α коэффициент сглаживания, варьируемый в диапазоне от 0,0 до 1,0. Если α равен 1,0, то новая коррекция игнорируется и повторяется предыдущая. В области между 0 и 1 коррекция веса сглаживается величиной, пропорциональной α. Дальнейшие алгоритмические разработки. Многими исследователями были предложены улучшения и обобщения описанного выше основного алгоритма обратного распространения. Например, алгоритм обратного распространения второго порядка, предложенный в 1987 г. Паркером, использует вторые производные для более точной оценки требуемой коррекции весов. Этот алгоритм дает быструю сходимость, когда функция зависимости ошибки от параметров сети близка к квадратичной. Было также доказано, что использование производных высших порядков не дает выигрыша в обучении. В одной из работ Сторнетт и Хьюберман описали метод улучшения характеристик обучения сетей обратного распространения. В работе указывается, что общепринятый от 0 до 1 динамический диапазон входов и выходов скрытых нейронов неоптимален. Так как величина коррекции веса Δwpq,k пропорциональна выходному уровню нейрона, порождающего OUTp,j, то нулевой уровень ведет к тому, что вес не меняется. При двоичных входных векторах половина входов в среднем будет равна нулю, и веса, с которыми они связаны, не будут обучаться. Решение состоит в приведении входов к значениям ±½ и добавлении смещения к сжимающей функции, чтобы она также принимала значения ±½. Новая сжимающая функция выглядит следующим образом: . С помощью таких простых средств время сходимости сокращается в среднем от 30 до 50%. Это является одним из примеров практической модификации, существенно улучшающей характеристику алгоритма. Существует методика применения обратного распространения к сетям с обратными связями, т.е. к таким сетям, у которых выходы подаются через обратную связь на входы. Обучение в подобных системах может быть очень быстрым и критерии устойчивости легко удовлетворяются. Динамическое добавление нейронов. Адекватный выбор количества нейронов и слоев серьезная и нерешенная проблема для нейронных сетей. Основным способом выбора остается прямой перебор различного количества слоев и определение лучшего. Для этого требуется каждый раз по-новому создавать сеть. Информация, накопленная в предыдущих сеансах обучения, теряется полностью. Начинать перебор количества нейронов можно как с заведомого избыточного, так и с недостаточного. Независимо от этого, новая созданная сеть с другим количеством нейронов требует полного переобучения. Динамическое добавление нейронов состоит во включении нейронов в действующую сеть без утраты ее параметров и частично сохраняет результаты, полученные в предыдущем обучении. Сеть начинает обучение с количества нейронов, заведомого недостаточным для решения задачи. Для обучения используются стандартные методы. Обучение происходит до тех пор, пока ошибка не перестанет убывать, и не выполняются условия где t – время обучения; Δ – пороговое значение убыли ошибки; δ – минимальный интервал времени обучения между добавлением новых нейронов; t0 – момент последнего добавления нового нейрона. Когда выполняются оба условия, добавляется новый нейрон. Вес нейрона инициализируется небольшим случайным числом. Обучение снова повторяется до тех пор, пока не будут выполняться приведенные ранее условия. Здесь приведена типичная зависимость ошибки от времени обучения. Моменты добавления новых нейронов отмечены пунктиром. После каждого добавления ошибка сначала резко возрастает, т.к. параметры нейрона случайны, а затем быстро сходится к меньшему значению. Общее время обучения обычно оказывается лишь в 1,4 раза больше, чем, если бы в сети сразу было нужное количество нейронов. Сеть с линейным поощрением. Созданы сети, промежуточные по отношению к обучению с учителем и без него. В качестве такой модели рассмотрим сеть с линейным поощрением. Эта модель обучается с учителем, т.е. требует зна­ния и выходных, и входных векторов при обучении. Однако в обратном направлении распространя­ется ограниченный объем информации, меньший, чем при обратном распространении. Все сигналы в сети лежат в интервале [0,1]. Сеть послойно-полносвязная, как и многослойный персептрон, и содержит три слоя нейронов. Последний, третий слой состоит из обычных формальных нейронов с детерминированным пове­дением и непрерывными выходными сигналами: Скрытый слой состоит из стохастических нейронов с двумя значениями выхода, 0 и 1. Каждое из выходных значений принимается с вероятностями: Первый слой не выполняет вычислений, а лишь распределяет входные сигналы по нейронам вто­рого слоя. Обучающее множество содержит s известных пар выходных и входных векторов. Функ­цию ошибки выберем нормированной и линейной, чтобы ее можно было трактовать как вероят­ность: где N0 – количество выходов сети. Выходной слой обучается и корректирует веса обычным способом. Второй слой обучается с поощрением и наказанием. Введем градационный сигнал r, характеризую­щий качество выходного результата. Тогда возможны два варианта: 1. Дискретный градационный сигнал с двумя возможными значениями, 0 и 1, с вероятностями . 2. Непрерывный градационный сигнал, . В обратном направлении распространяется только градационный сигнал, а не полная информа­ция об ошибке по каждому выходу, как в обратном распространении. Применения. Обратное распространение было использовано в широкой сфере прикладных исследований. Фирма NEC в Японии объявила, что обратное распространение было ею использовано для визуального распознавания букв, причем точность превысила 99%. Это улучшение было достигнуто с помощью комбинации обычных алгоритмов с сетью обратного распространения, обеспечивающей дополнительную проверку. Достигнут также впечатляющий успех с Net-Talk, системой, которая превращает печатный английский текст в высококачественную речь. Для преобразования текста в фонемы применялся многослойный перцептрон с одним скрытым слоем из 80 нейронов. На вход одновременно подавалась последовательность из 7 букв, каждая из которых кодировалась группой из 29 входов (26 букв алфавита + знаки препинания). Сеть имела 26 выходов для представления одной из 26 фонем с различной окраской звучания, сюда же относились фонемы-паузы. Сеть прошла 50 циклов обучения по обучающему множеству из 1024 английских слов, и достигла 95% вероятности правильного произношения для слов из этого множества, и вероятности 80% на неизвестных сети словах. Обратное распространение использовалось в машинном распознавании рукописных английских слов. Буквы, нормализованные по размеру, наносились на сетку, и брались проекции линий, пересекающих квадраты сетки. Эти проекции служили затем входами для сети обратного распространения. Сообщалось о точности 99,7% при использовании словарного фильтра. Также есть информация об успешном применении обратного распространения к сжатию изображений, когда образы представлялись одним битом на пиксель, что было восьмикратным улучшением по сравнению с входными данными. В сложных задачах для обучения нейронной сети могут потребоваться дни или даже недели, или она может вообще не обучиться. Длительное время обучения может быть результатом неоптимального выбора длины шага. Неудачи в обучении обычно возникают по двум причинам: паралича сети и попадания в локальный минимум. Паралич сети. В процессе обучения сети значения весов могут в результате коррекции стать очень большими величинами. Это может привести к тому, что все или большинство нейронов, будут функционировать при очень больших значениях OUT, в области, где производная сжимающей функции очень мала. Так как посылаемая обратно в процессе обучения ошибка пропорциональна этой производной, то процесс обучения может практически замереть. В теоретическом отношении эта проблема плохо изучена. Обычно этого избегают уменьшением размера шага η, но это увеличивает время обучения. Различные эвристики использовались для предохранения от паралича или для восстановления после него, но пока что они могут рассматриваться лишь как экспериментальные. Локальные минимумы. Обратное распространение использует разновидность градиентной спуска, т.е. осуществляет спуск вниз по поверхности ошибки, непрерывно подстраивая веса в направлении минимума. Поверхность ошибки сложной сети сильно изрезана и состоит из холмов, долин, складок оврагов в пространстве высокой размерности. Сеть может попасть в локальный минимум (неглубокую долину), когда рядом имеется более глубокий минимум. В точке локального минимума все направления ведут вверх, и сеть неспособна из него выбраться. Статистические методы обучения могут помочь избежать этой ловушки, но они медленны. Был предложен метод, объединяющий статистические методы машины Коши с градиентным спуском обратного распространения и приводящий к системе, которая находит глобальный минимум, сохраняя высокую скорость обратного распространения. Размер шага. Внимательный разбор доказательства сходимости показывает, что коррекции весов предполагаются бесконечно малыми. Ясно, что это неосуществимо на практике, так как ведет к бесконечному времени обучения. Размер шага должен выбраться конечным, и в этом вопросе приходится опираться только на опыт. Если размер шага очень мал, то сходимость слишком медленная, если же очень велик, то может возникнуть паралич или постоянная неустойчивость. Здесь может помочь адаптивный алгоритм выбора шага, автоматически корректирующий размер шага в процессе обучения. Или обучение с шумом, когда коррекция весов содержит в себе случайную величину, имеющую нулевое математическое ожидание и небольшую дисперсию (часто используется гауссовское распределение). Добавление шума снижает скорость обучения, но шум уменьшает и вероятность остановки алгоритма в неглубоком локальном минимуме целевой функции. Временная устойчивость. Алгоритм требует, чтобы все обучающие образы предъявлялись перед каждой коррекцией параметров. Это следует из необходимости суммировать функцию ошибки по всем образам из обучающего множества. В этом случае алгоритм всегда сходится, хотя количество итераций для сходимости может оказаться сколь угодно большим. Если суммирования по всем образам нет, и коррекция параметров проводится после предъявления каждого образа, то алгоритм может не сойтись вообще, если: 1. Образы предъявляются не в случайном порядке. 2. Обучающее множество постоянно меняется, и каждый образ предъявляется малое количество раз, это встречается в системах, работающих в реальном времени, например, системах управления или прогнозирования. Расходимость в этом случае называется временной неустойчивостью. Проблема решается случайным предъявлением образов либо выбором другого алгоритма обучения или другой модели нейронной сети. Генетические алгоритмы Генетические алгоритмы возникли в результате наблюдений и попытки копировать естественные процессы в мире живых организмов. Первым, кто высказал идею использования генетических алгоритмов в технических системах, был Холланд (“Adaption in natural and artificial system” 1975, Дж. Холланд). В генетических алгоритмах применяется ряд терминов, которые были заимствованы из биологии: ген, хромосома, популяция, особь, аллель, генотип, фенотип. Помимо взаимодействия генетических алгоритмов с искусственными нейронными сетями они могут применяться совместно с нечеткими системами. Генетические алгоритмы (ГА) – процедуры поиска, основанные на механизме естественного отбора и наследования. Отметим отличие ГА от традиционных методов оптимизации: 1. ГА обрабатывают не значения параметров самой задачи, а их закодированную форму. 2. ГА осуществляют поиск решения исходя не из единственной точки, а из целой популяции точек. 3. ГА используют только целевую функцию без производных и дополнительной информации. 4. ГА используют вероятностные методы выбора. Основные понятия ГА Популяция – конечное множество особей. Особь – структура в виде хромосом с закодированным в них множеством параметров задач. В биологии употребляется “организм”. Хромосома – упорядоченная последовательность генов. Ген – атомарный элемент генотипа (в частности хромосомы). Генотип – набор хромосом данной особи из той или иной популяции. Особями популяции могут быть генотипы либо единичные хромосомы. Фенотип – набор значений, соответствующих данному генотипу. Аллель – значение конкретного гена, определяемое как значение свойства или вариант свойства. Локус – указывает место размещения гена в хромосоме. Множество позиций гена называется локк. Важным определением в ГА является функция приспособленности ff (fitness function) – функция оценки (целевая функция, стоимостная, функция погрешности). Пример 1: Пусть дана функция при условиях: х принимает целые значения Є{0..15}- пространство поиска каждого из 16 чисел называется фенотипом; х можно закодировать в виде 4-х бит слов Такая двоичная комбинация будет называться хромосомой. Каждая из хромосом состоит из 4-х ген. Значение гена в конкретной позиции называется аллелью. Аллель может быть либо 0, либо 1. Классический ГА Блок схема ГА имеет вид (см. ниже) Селекция хромосом заключается в выборе тех хромосом, которые будут участвовать в создании потомков для следующей популяции. Такой выбор производится согласно принципу естественного отбора с использованием функции приспособленности. Наиболее популярным является метод рулетки (roulette wheel selection). Каждой хромосоме в этом случае соответствует сектор колеса рулетки, величина которого устанавливается пропорционально значению функции приспособленности данной хромосомы. Каждой хромосоме chi (i =1,N, где N – численность популяции) соответствует сектор V колеса рулетки: (*) ps(chi)- вероятность селекции хромосомы. Селекция хромосомы представляется как результат поворота колеса рулетки и выбранная хромосома будет относиться к выигравшему сектору этого колеса. Чем больше сектор, тем больше вероятность выбора соответствующей хромосомы. В результате селекции создается родительская популяция. Численность новой популяции (mating pool – родительский пул) равна N. В классическом ГА применяются два основных генетических оператора: 1. операция скрещивания (cross over) 2. операция мутации (mutation) Операция мутации имеет второстепенную роль. 0,5 ≤ pc ≤ 1 0 ≤ pm ≤ 0,1 Эти данные соответствуют миру живых организмов. Рассмотрим операцию скрещивания. Первый его этап это выбор, деление популяции родителей на пары. Это производится случайным способом в соответствии с вероятностью скрещивания рс. Для каждой пары отдельно разыгрывается случайным образом локус, который определяет точку скрещивания (локус – указывает место размещения данного гена в хромосоме). Допустим, локус = lk 10 .. 01 1 00 … 11 01 .. 11 1 01 … 10 lk В результате скрещивания получится следующая пара потомков: потомок 1, на позиции которого от 1 до lk будут стоять гены 1-го родителя, а от lk+1 до L гены второго родителя. 10 … 01 1 01 … 01, а потомок 2 наоборот 01 … 11 1 00 … 11. Мутация с вероятностью pm изменяет значение гена в хромосоме на противоположное. Лучшим решением считается хромосома с наибольшим значением функции приспособленности. Вернемся к примеру. Пусть дана функция при следующих условиях: х принимает значения целые значения. Пусть необходимо найти максимум функции переменной х, принимающей целочисленное значение от 0 до 31. Для применения ГА производим кодировку х в виде двоичной последовательности и случайным образом формируем исходную популяцию. Пусть получилось 6 хромосом. ch1 =10011 19 ch4 =10101 ch2 =00011 3 ch5 =01000 8 ch3 =00111 5 ch6 =11101 По формуле (*) рассчитаем ff(x) функции приспособленности хромосом: F(ch1)=723 F(ch4)=883 F(ch2)=19 F(ch5)=129 F(ch3)=99 F(ch6)=1683 Воспользуемся методом рулетки: v(ch3) v(ch2) 97; 26; 54; 13; 31; 88 ch6; ch4; ch6; ch1; ch4; ch6; v(ch1) v(ch4) v(ch5) v(ch6) Допустим скрещивание выполняется с вероятностью равной 1 и в качестве пар получились следующие: ch1, ch4 ch4, ch6 ch6, ch6 При вероятности мутации равной 0 получаем следующий набор хромосом F F ch1 =10001 579 ch4 =11101 1683 ch2 =10111 1058 ch5 =11101 1683 ch3 =10101 883 ch6 =11101 1683 В результате среднее значение функции приспособленности увеличилось с 589 до 1262. Пример Рассмотрим пример, состоящий в нахождении хромосомы с максимальным коли­чеством единиц. Допустим, что хромосомы состоят из 12 генов, а по­пуляция насчитывает 8 хромосом. Понятно, что наилучшей будет хро­мосома, состоящая из 12 единиц. Посмотрим, как протекает процесс решения этой весьма тривиальной задачи с помощью генетического алгоритма. Инициализация, или выбор исходной популяции хромо­сом. Пусть имеем исходную популяцию ch1 = [111001100101] ch5 = [010001100100] ch2 = [001100111010] ch6 = [010011000101] ch3 = [011101110011] ch7 = [101011011011] ch4 = [001000101000] ch8 = [000010111100] Оценка приспособленности хромосом в популяции. В рас­сматриваемом примере функция приспособленности определяет количество единиц в хромосоме. Тогда ее значения для каждой хромосомы из исходной популяции бу­дут такие: = 7 = 4 = 6 = 5 = 8 = 8 = 3 = 5 Селекция хромосом. Селекция производится методом рулет­ки. На основании формул (*) для каждой из 8 хромосом теку­щей популяции получаем секторы колеса рулетки, выраженные в процентах (рис. 1). (*) = 15,22 = 8,70 = 13,04 = 10,87 = 17,39 = 17,39 = 6,52 = 10,87 Колесо рулетки для селекции Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствую­щий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел: 79 44 9 74 44 86 48 23 . Все выбранные таким образом хромосомы включаются в так называемый родительский пул. Применение генетических операторов. Допустим, что ни од­на из отобранных в процессе селекции хромосом не подвергается му­тации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания , а вероятность мутации . Допустим, что из этих хромосом слу­чайным образом сформированы пары родителей и , и , и , и . Для первой пары случайным образом выбрана точка скре­щивания , для второй , для третьей , для четвертой . При этом процесс скрещивания протекает так, как показано на рис. В результате выполнения оператора скрещивания получают­ся 4 пары потомков. Процесс скрещивания хромосом Формирование новой популяции. После выполнения опера­ции скрещивания мы получаем следующую попу­ляцию потомков: = [001111011011] = [011101110010] = [101000111010] = [001000101001] = [111011011011] = [011101011011] = [101001100101] = [101011110011] Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с заглавной буквы . Согласно блок-схеме генетического алгоритма произ­водится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей. Значения функций приспособленности хромосом этой попу­ляции составляют = 8 = 7 = 6 = 4 = 9 = 8 = 6 = 8 Заметно, что популяция потомков характеризуется гораздо бо­лее высоким средним значением функции приспособленности, чем популяция родителей. Обратим внимание, что в результате скрещи­вания получена хромосома с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из ро­дительской популяции. Модификация классического ГА В классическом ГА рассматривали: 1. двоичное представление хромосом 2. селекция методом рулетки 3. точечное скрещивание Для повышения эффективности этого алгоритма было создано множество его модификаций. Они связаны с применением: 1. других методов селекции 2. модификации генетических операторов 3. преобразованием функции приспособленности 4. с другими способами кодирования хромосом Существуют версии ГА, позволяющие находить наряду с глобальными локальные оптимумы. Специальные версии ГА, созданные для решения проблем, называются генетическими микроалгоритмами. Эволюционные алгоритмы Эволюционные программы можно считать обобщением ГА. Классический ГА выполняется при фиксированной длине двоичных последовательностях и использовании операций скрещивания и мутации. В отличие от них эволюционные программы обрабатывают более сложные структуры (не только двоичные коды, обычно используют десятичное кодирование) и могут выполнять другие генетические операции. В последнее время стала популярна следующая эволюционная стратегия: • хромосомы представляются десятичным вещественными числами; • мутация используется как единственный генетический оператор. Рассмотрим пример эволюционной программы. Найти граф, который удовлетворяет определенным ограничениям. Например, производится поиск топологии коммуникационной сети оптимальной по конкретным критериям (по стоимости передачи сообщений). Каждая особь в эволюционной программе представляет некоторый граф. Исходная популяция графов Р(0) формируется случайным образом (или допускается реализация эвристического процесса) и является отправной точкой эволюционной программы k=0. В качестве мутации можно предложить несколько операторов. Если ищется граф типа дерева, то используется оператор мутации, который удаляет ветвь из одного графа и добавляет новую ветвь, объединяющую 2 отдельных подграфа. Можно использовать функцию штрафов для тех графов, которые не являются деревьями. Таким образом, ГА могут использоваться как в узком смысле, то есть для обозначения классического ГА и их существующих модификаций, так и в широком смысле подразумевая любые эволюционные алгоритмы, значительно отличающиеся от классики. Эволюционные алгоритмы в нейронных сетях (НС) Объединение эволюционных алгоритмов и нейронных сетей получило аббревиатуру COGANN. Это объединение может быть 2-х видов: 1. вспомогательное 2. равноправное Классификацию этих типов объединений представим таблицей: Вид объединения Характеристика объединения Примеры использования Графические изображения Независимое ГА и НС независимо применяются для одной и той же задачи Однонаправленные НС, сети Кохонена (самоорганизующиеся) и ГА как самостоятельный вид в задачах классификации Вспомогательный НС для обеспечения ГА Формирование исходной популяции для ГА ГА для обеспечения НС Анализ НС. Подбор параметров или преобразование пространства параметров. Подбор параметров или эволюция правил обучения Равноправное ГА для обучения НС ГА для выбора топологии НС Системы, объединяющие адаптивные стратегии ГА и НС Эволюционное обучение сети и эволюция весов связи Эволюция сетевой архитектуры, подбор топологии сети НС для решения оптимизации задач с применением ГА для подбора весов Реализация ГА с помощью НС Применение НС для реализации операции скрещивания в ГА Приведем примеры практического использования независимых и равноправных объединений. Рассмотрим равноправные объединения ГА и ИНС. 1. ГА для обучения НС связан с задачей оптимизации весов НС, при этом топология сети задается априорно 2. связь с задачей закодирования в генотипе топологию объекта (НС) с указанием количества нейронов и связей между ними 3. задачи, в которых осуществляется комбинация адаптивных стратегий первых двух методов, составляющих единую адаптивную систему. В результате получается наилучшее множество весов, архитектур НС и правил. Рассмотрим эволюцию связей и весов. Блок-схема ГА поиска наилучшего набора весов НС имеет следующий вид. Глядя на блок-схему, отметим необходимость выбора между бинарным представлением генотипа и кодирования весов действительными числами. Помимо традиционного двоичного кода могут применяться код Грэя, логарифмическое кодирование, либо другие более сложные формы записи данных. В этом процессе в роли ограничителя выступает требуемая точность представления значения весов. Если для записи каждого веса использовать слишком мало бит, то обучение может продолжаться слишком долго и не принести никакого эффекта, поскольку точность аппроксимации отдельных комбинаций оказывается недостаточной. C другой стороны, если используется слишком много бит, то двоичные последовательности, представляющие НС большой размерности, оказываются очень длинными, что сильно удлиняет процесс эволюции, делая его нерациональным с практической точки зрения. Вопрос оптимизации количества бит для представления весов остается открытым. Стандартные генетические операторы разрабатываются в основном для схем двоичного представления данных, могут применяться и в случае задания весов действительными числами, однако в этом случае для повышения эффективности и ускорения его действия создаются специальные генетические операторы. Рассмотрим эволюцию архитектуры сети. В предыдущем рассмотрении предполагалось, что топология задается априори, но возникает вопрос, а как выбрать архитектуру сети? В настоящее время существует два способа кодирования архитектуры сети. Согласно первому полная информация об архитектуре непосредственно кодируется в виде двоичных последовательностей. В этом случае каждая связь и каждый узел прямо специфицируются определенным количеством бит. Такой способ широко распространен – схемы непосредственного кодирования. Рассмотрим сеть: Хромосома . С другой стороны может представляться только важнейшие параметры или свойства архитектуры – схемы косвенного кодирования. Второй способ выглядит более обоснованным с биологической точки зрения. Согласно современной нейрологии невозможно прямо и независимо описать закодированную в хромосомах генетическую информацию, всю нервную систему человека. Блок-схема ГА для наилучшей архитектуры имеет следующий вид: Если для оценивания приспособленности использовать результаты тестирования вместо традиционных результатов вычисления ошибки, то получиться сеть, обладающая лучшей способностью к обобщению. Поиск оптимального решения, как правило, происходит методом “проб и ошибок” (методом экспертных знаний). Поэтому перспективным считается развитие автоматических методов автоматизации правил обучения ИНС. Развитие человеческих способностей к обучению от относительно слабых до весьма сильных свидетельствует о потенциальных возможностях применения эволюционного подхода в процессе обучения ИНС. Схема хромосомного представления в случае эволюции правил должна отражать динамические характеристики. В предыдущих 2-х алгоритмах статические параметры, такие как архитектура и веса, кодировать значительно проще, чем динамические. Попытка создания универсальной схемы представления, которая позволяла бы описывать произвольные виды динамических характеристик ИНС, предполагает неоправданно большой объем вычислений, требуемых для просмотра всего пространства правил обучения. Поэтому на тип динамических характеристик налагают ряд определенных ограничений. Предполагается, что для всех связей ИНС должно быть задано одно правило обучения. Общий вид правила: t-текущее время -приращение веса -локальные переменные -вещественные коэффициенты Главная цель эволюционных правил обучения заключается в подборе соответствующих значений коэффициентов . Для реализации этой цели может быть предложен типовой цикл эволюции правил обучения. Типовой цикл: 1. декодирование каждой особи текущей популяции используется для получения правил обучения; 2. формирование множества НС; 3. расчет значений функции приспособленности; 4. репродукция особей с вероятностью, соответствующей их приспособленности или рангу в зависимости от использованного метода селекций; 5. формирование новой популяции и возврат в этап 1. Блок-схема, иллюстрирующая архитектуру эволюции, имеет вид: Экспертные системы. Классификация и структура ЭС – это программа, в которой включены знания специалистов о некоторой предметной области и которая в пределах этой области способна принимать экспертные решения, т.е. заменять эксперта-человека. Наибольший прогресс в области ИИ связан именно с созданием ЭС, которые получили достаточно широкое распространение и используются при решении практических задач. Экспертная система является системой, использующей суждения. Как только записана команда «сравнить одну величину с другой и затем осуществить определенное действие, зависящее от результата сравнения» – это и есть суждение. При проектировании ЭС суждениям принадлежит ведущая роль. ЭС применимы в достаточно широком спектре предметных областей, которые классифицируют по следующим типам. 1. Интерпретация (вывод описаний ситуаций из наблюдаемых данных). 2. Прогнозирование (вывод вероятных следствий из заданных ситуаций). 3. Диагностика (суждение о нарушениях в работе технической системы или организма человека по наблюдениям). 4. Проектирование (построение конфигурации объектов, которая удовлетворяет заданным ограничениям). 5. Планирование (построение плана действий для достижения заданной цели). 6. Контроль (предупреждение об «опасности», или нештатной ситуации). 7. Отладка (выдача рекомендаций по ликвидации плохого функционирования). 8. Ремонт (выполнение план устранения некоторого обнаруженного дефекта). 9. Обучение. 10. Управление (адаптивное управление поведением некоторой системы). Последнее совпадает с понятием ситуационного управления. Основные типы задач, в которых применяются ЭС, представлены на рис. 10. Рис. 10 Уточним терминологию, взяв за основу классические работы по ИИ. Представление (representation) – это множество синтаксических и семантических соглашений, которые делают возможным описание предмета. Предмет – состояние в некоторой проблемной области, например, объекты, их свойства, отношения, существующие между объектами. Описание (description) – позволяет использовать соглашения из представления для описания определенных предметов (Winston). Синтаксис представления специфицирует набор правил, регламентирующих объединение символов для формирования выражений на языке представления. Синтаксис представляется в виде конструкций «предикат – аргумент», который имеет форму <фраза>::=<предикат>(<аргумент 1>…<аргумент N>). Семантика представления специфицирует, как должно интерпретироваться выражение, построенное в соответствии с синтаксическими правилами, то есть, как из его формы можно извлечь какой-то смысл. Главное отличие ЭС от обычных программ, способных принимать экспертные решения состоит в отделении декларативных знаний от процедурного компонента, манипулирующего ими. Другими словами, цель большинства экспертных систем: осуществлять общую экспертизу в широкой области путем «очерчивания» различия между знаниями, которые они используют и механизмами, манипулирующими этими знаниями. В ходе изменения природы специфического знания такая система становится затем способной выполнять свои манипуляции, чтобы стать экспертом в новой области. Например, ЭС, построенная для осуществления диагностики заболеваний, при замене медицинских знаний на знания, скажем, об инженерных сооружениях становится экспертом по инженерным сооружениям. Области применения ЭС, в которых доказана их эффективность: ◦ медицина; ◦ финансовая деятельность; ◦ юриспруденция; ◦ геология; ◦ химия; ◦ электроника; ◦ математика; ◦ вычислительная техника; ◦ машиностроение; ◦ метеорология; ◦ космические исследования; ◦ управление; ◦ сельское хозяйство; ◦ физика; ◦ военное дело. Структура ЭС представлена на рис. 11. Знания эксперта Ядро ЭС Запрос от П ответ П объяснение П Рис. 11 Модуль вывода (МВ, решатель) – по запросу от пользователя, используя имеющиеся знания, осуществляет поиск ответа, причем этот поиск, как правило, сопровождается диалогом между пользователем и ЭС. Если ответ вызывает сомнения у пользователя (нормальная ситуация), то он может потребовать объяснений. Пунктиром обозначены блоки, которые присутствуют не во всех ЭС. Архитектура реальных ЭС различается по следующим характеристикам: 1. Способ представления данных и знаний. 2. Состав используемых знаний. 3. Методы работы интерпретатора. Большинство ЭС базируется на понятии «формальная продукционная система», рассмотренном в предыдущей лекции. Лекция №14-15. Инструментальные средства проектирования, разработки и отладки экспертных систем Проектирование ЭС имеет существенные отличия от проектирования обычного программного продукта. Опыт разработки первых ЭС показал, что использование при их проектировании методологии, принятой в традиционном программировании, либо чрезмерно затягивает процесс создания ЭС, либо вообще приводит к отрицательному результату. В настоящее время выделяют 7 парадигм. В скобках указаны присущие им абстракции. 1. Процедурно-ориентированные языки (алгоритмы). 2. Объектно-ориентированные (классы, объекты). 3. Логически ориентированные языки (цели, выраженные в исчислении предикатов). 4. Языки, ориентированные на правила (продукция ЕСЛИ … ТО). 5. Языки программирования, ориентированные на ограничения (инвариантные соотношения). 6. Параллельное программирование (потоки данных). 7. Визуальное программирование (элементы диалога и части разных программ). Неформализованность задач, решаемых ЭС, отсутствие завершенной теории ЭС и методологии их проектирования приводит к необходимости модифицировать принципы и способы построения ЭС в ходе процесса проектирования по мере того, как увеличиваются знания разработчиков о ПО. Учитывая это, при проектировании ЭС используется концепция быстрого прототипа. Разработчики не пытаются сразу построить конечный продукт. На начальном этапе они создают прототип ЭС - такой продукт, который за минимальное время разработки мог бы решать поставленные задачи. Еще раз отметим два противоречивых требования, которым должен удовлетворять прототип: 1. Он должен решать типичные задачи конкретного приложения. 2. Трудоемкость его разработки должна быть минимальным. Прототип должен продемонстрировать пригодность методов инженерии знаний для конкретного приложения. Для удовлетворения указанным требованиям при создании прототипа используются разнообразные средства, ускоряющие процесс проектирования. Эти средства в обобщенном виде называют инструментальными (или инструментарием). Существуют различные классификации инструментария в инженерии знаний, например: 1. Процедурные языки программирования, ориентированные на обработку символьной информации (LISP, INTERLISP и др.). 2. Языки инженерии знаний, то есть языки, ориентированные на разработку ЭС (PROLOG, OPS_5 и др.). 3. Средства автоматизации процесса конструирования, использования и модификация ЭС (RLL, HEARSAY–III, TEIRESIAS и др.). 4. Пустые (скелетные) экспертные системы, не содержащие знаний ни о какой ПО (цель: убрать знания одной системы и загрузить знания другой) (EMYCIN, KAS и др.). В приведенной классификации инструментальные средства расположены в порядке убывания трудоемкости, требуемой для создания с их помощью прототипа. Инструментальные средства третьей группы позволяют не программировать некоторые или даже все компоненты экспертной системы, а выбрать их из заранее составленного набора. Обычно инструментарий этого типа подразделяют на средства, автоматизирующие построение ЭС (RLL, HEARSAY–III), и средства, автоматизирующие процесс приобретения знаний (TEIRESIAS). При использовании инструментария 4 может возникнуть следующая проблема. Управляющие стратегии, заложенные в процедуры выбора базовой системы, могут не соответствовать методам решения, которые использует эксперт. Часто в понятие инструментария включают не только программные продукты, но и аппаратные средства. Инструментальные средства проектирования, разработки и отладки экспертных систем. Язык LISP LISP( LIST PROCESSING) - универсальный высокоуровневый язык программирования, основанный на понятии списка. Все объекты языка рассматриваются как списки. Особенности языка LISP: • функции записываются в префиксной форме; • функции заключаются в круглые скобки. (-5 2) : 3 (*5 4) : 20 (max 5 9 2) : 9 Список: |(БОБ ТОМ МЕЙ СЬЮ) |(20 30 40). CAR – выбирает первый элемент из списка. CDR – удаляет первый элемент из списка. CONS – первый становится последним. Базовым блоком в структуре данных языка LISP является символическое выражение. Простое символическое выражение использует атомарные символы, или атомы — строки буквенно-цифровых символов, которые начинаются с буквы, например WOMBAT. (Допустимая длина строки варьируется в зависимости от версии исполняющей системы.) Во внутренней структуре данных атом представлен ячейкой памяти. Отдельным атомом является символ Т, которым представляется константа «True» — истина. Другой специальный атом, NIL, представляет, с одной стороны, константу «False»—ложь, а с другой — пустой список. Составные выражения объединяются в древовидной структуре, при этом используется очевидное соответствие между символическими выражениями и представлением конечных деревьев. Списки представляют собой довольно гибкие структуры данных, поскольку могут объединять элементы разных типов и иметь произвольную длину и размерность (вложенность). Например, в LISP возможен такой список: («а» (9) () N (? (WOMBAT)) (A . В) NIL 0.9) Этот список содержит элементы разных типов — строки, числа с фиксированной и плавающей точкой, атомы, булевы значения, точечные пары и другие списки. Но списки имеют и определенные недостатки, из-за которых в LISP были включены и другие структуры данных. Списки в LISP представляют собой стеки, т.е. доступ к ним возможен только с одного конца списка. Манипулируя только таким списком, невозможно обратиться к элементу списка по его позиции, как это делается с элементом массива. Поэтому для представления больших совокупностей относительно постоянных или редко меняющихся данных в LISP были включены другие типы структур. В современных версиях LISP поддерживаются массивы, хэш-таблицы и структуры, подобные записям, которые позволяют эффективнее использовать пространство памяти и повысить скорость доступа. Совершенно ясно, что среда символических вычислений весьма подходит для реализации структур, необходимых для представления знаний, но символический уровень анализа ничего не говорит нам о том, чем должны быть такие структуры. Нужен еще один уровень анализа, расположенный выше символического, который будет ограничивать набор возможных представлений при решении некоторой проблемы. Ньюэлл [Newell] назвал его уровнем знаний и предположил, что знания должны быть охарактеризованы функционально, т.е. в терминах действия, а не в терминах структурной организации. Из предложения Ньюэлла следует, что нельзя адекватно представлять знания, не располагая сведениями о том, как они могут быть использованы. Возможно, это одна из причин, которая побуждает нас разделить факты и знания. То, что норманны в 1066 году захватили Англию, — это только факт. Но мое знание этого факта может быть использовано совершенно по-разному. В частности, это в равной степени позволит мне успешно сдать экзамен по истории или спровоцировать драку между англичанами и французами. Если цель состоит именно в том, чтобы получить более высокую оценку на экзамене, то представление знаний лучше связать с другими фактами, например сведениями о короле Гарольде или короле Вильяме. Если же цель — разжечь ненависть между англичанами и французами, то лучше воспользоваться такими фактами, как вандализм английский футбольных фанатов или эксцентричная манера вести себя на дорогах, присущая французским мотоциклистам. Таким образом, не существует «правильного» способа представить какой-то факт, но существует более или менее полезное представление знания некоторыми фактами. В синтаксисе и семантике языка LISP нет ничего такого, что подсказало бы, как организовать знания. Список — это удобная, но иногда неэффективная в работе структура данных, но он не имеет никаких преимуществ с точки зрения представления знаний по сравнению с массивом в языке FORTRAN и менее удобен, чем класс в языке C++. Утверждение о широких возможностях LISP имеет скорее отношение к тому, что для опытного программиста довольно легко создать на его основе производный язык по своему выбору. Но такой специализированный интерпретатор, функционирующий в среде LISP, оказывается очень непроизводительным, и в этом его основной недостаток. Язык инженерии знаний OPS_5 OPS_5 (Official Production System, Version 5) является языком для представления знаний, использующим правила. Знания в OPS_5 состоят из элементов данных и правил. Элемент данных является вектором (списком значений) или объектом, с которым связываются пары «атрибут-значение». Правила имеют вид «условие-действие». В ранних моделях систем, основанных на порождающих правилах, до 90% времени работы уходило на выполнение операций сопоставления условий. Но позднее Форджи [Forgy] обратил внимание на возможные источники низкой эффективности такого упрощенного подхода. Алгоритм сопоставления RETE, предложенный Форджи и реализованный в языках описания порождающих правил семейства OPS, базируется на двух наблюдениях. • В левых частях порождающих правил, которые размещаются в рабочей памяти, часто встречаются повторяющиеся условия. Если одно и то же условие встречалось в N правилах, то при прежнем упрощенном подходе выполнялось N операций сопоставления. Это пример внутрицикловой итерации (within-cycle iteration). • Простейший подход при сопоставлении условий предполагает просмотр в каждом цикле всех элементов рабочей памяти, хотя содержимое рабочей памяти от цикла к циклу изменяется очень мало. Форджи назвал это межцикловой итерацией (between-cycle iteration). Предложенный Форджи алгоритм значительно снижает количество внутрицикловых итераций за счет использования сети сортировки, имеющей древовидную структуру. Выражения в левой части порождающих правил компилируются и включаются в эту сеть, а алгоритм сопоставления довольно просто определяет конфликтующее множество, просматривая состояние сети в текущем цикле. Количество межцикловых итераций сокращается за счет обработки множества лексем, которые являются индикаторами удовлетворения условий, размещенных в рабочей памяти. Это множество лексем отображает изменения, происходящие в рабочей памяти от цикла к циклу, и таким образом позволяет выявить те условия, которые подлежат проверке. Поскольку никаких других процессов управления, кроме цикла распознавание-действие, в системе не существует, то обработать полученное в результате конфликтующее множество не представляет особого труда. Механизм разрешения конфликтов выполняет это, не обращая внимания на другие аспекты текущего контекста вычислений. Совершенно очевидно, что попытка использовать рекурсивные структуры данных потребует серьезного усложнения описанного процесса обработки правил. Точно также и изменение режима управления приведет к тому, что механизм разрешения конфликтов вынужден будет анализировать дополнительную информацию. Разработчики языков, подобных OPS, всегда вынуждены искать компромисс между мощностью выразительных средств языка и эффективностью выполнения программного кода. До сих пор в среде исследователей предметом оживленных дискуссий является вопрос о том, удалось ли разработчикам OPS_5 найти такой компромисс. Разработанные позже языки КЕЕ, КАРРА и CLIPS унаследовали от OPS_5 синтаксис и механизм активизации правил. Все эти языки используют различные версии алгоритма RETE при формировании множества конфликтующих правил. Преодоление недостатков программирования порождающих правил лежит не на пути усложнения существующих языков программирования, а скорее на пути объединения их с другими парадигмами программирования, позволяющими использовать рекурсивные структуры данных и управления. Примером такого объединения может служить комбинирование порождающих правил и фреймов, что позволяет сопоставлять условия, специфицированные в правилах, с содержимым слотов фреймов. Для решения проблем управления в последнее время все чаще используется включение наборов правил в более мощную вычислительную среду, которая позволяет работать со списками заявок и с множеством источников знаний. Опыт применения OPS_5. Экспертная система R1/XCON Характеристика, отличительные особенности Система R1 была одной из первых успешных попыток применения экспертных систем в промышленности в начале 1980-х годов [McDermott]. Эта система предназначена для помощи разработчикам при определении конфигурации вычислительной системы на базе вычислительных устройств и блоков семейства VAX. Сначала программа проверяет полноту спецификации требований к проектируемой системе, которая представлена заказчиком. На втором этапе программа определяет конфигурацию системы, соответствующую этим требованиям. Коммерческая версия системы, разработанная совместно университетом Карнеги—Меллон и корпорацией Digital Equipment, получила наименование XCON. В литературе обращается внимание на отличия между начальным проектом и его коммерческой версией. Первым практическим применением системы XCON была разработка конфигурации вычислительного комплекса VAX-11/780 на заводе фирмы DEC в Салеме, шт. Нью-Гэмпшир. Затем последовала разработка конфигураций других типов вычислительных комплексов, таких как VAX-11/750 и последующих модификаций продукции DEC. ЭС продемонстрировала, чего можно достичь при использовании даже относительно слабого метода решения проблем, если имеется достаточно знаний о предметной области. История развития этой системы также показывает, как расширяется сфера применения коммерческой экспертной системы при правильном менеджменте и как системы такого типа «врастают» в производственную среду. Задачу системы R1 нельзя отнести к типу тривиальных. Типовой вычислительный комплекс включает 50-100 компонентов, главными из которых являются центральный процессор, устройство управления оперативной памятью, блоки управления интерфейсом по шинам UNIBUS и MASSBUS, причем все эти компоненты подключены к единой плате синхронизации. Шинные интерфейсы поддерживают обмен с широкой номенклатурой периферийных устройств — устройствами внешней памяти на магнитных лентах и дисках, принтерами и т.п. В результате имеется возможность строить системы самой различной конфигурации. Получив заказ со спецификацией характеристик вычислительного комплекса, система R1 должна принять решение о том, какие устройства нужно включить в состав комплекса и как их объединить в единую систему. Принять решение о том, соответствует ли определенная конфигурация тем характеристикам, которые представлены в заказе, не так просто, поскольку для этого нужно обладать знаниями о возможностях и характеристиках всех компонентов и отношениях между разными компонентами. Не менее сложна и задача оптимальной компоновки комплекса из выбранного набора компонентов, поскольку при ее решении нужно принимать во внимание множество ограничений на взаимное расположение компонентов в структуре комплекса. Например, подключение модулей расширения UNIBUS к устройству синхронизации требует учитывать ограничения по токовой нагрузке, существующие для устройства синхронизации, и распределение приоритетов прерываний для подключаемых модулей расширения. Таким образом, задачу выбора конфигурации можно с полным правом считать классической конструктивной проблемой, которая требует для своего решения значительного объема экспертных знаний. В системе R1 главным является подход, предполагающий, что процесс решения направляется данными (data-driven). Сначала программа определяет множество компонентов и далее пытается сконструировать такую конфигурацию этих компонентов, которая удовлетворяла бы ограничениям, вытекающим как из характеристик отдельных компонентов, так и из отношений и связей между ними. Для успешной работы программа R1 нуждается в знаниях двух видов: • о характеристиках компонентов — электрических (напряжение питания, потребляемая мощность, параметры выходных сигналов и т.п.), механических (габариты, тип и количество разъемов), структурных (количество портов) и т.п.; • об ограничениях, накладываемых на «совместимость» компонентов, — правилах формирования частичных конфигураций и их расширения. Знания о компонентах хранятся в базе данных отдельно как от памяти системы порождающих правил, так и от рабочей памяти транзитных элементов данных. Таким образом, база данных имеет статическую структуру, в то время как рабочая память является динамической, В отличие от памяти порождающей системы, которая организована в виде набора модулей, управляемых по определенной схеме, база данных состоит из записей обычной структуры, которые для каждого компонента хранят информацию о его классе, типе и множестве характеристик. Например, ниже представлен фрагмент записи о контроллере накопителя на магнитных дисках типа RK611 CLASS: UNIBUS MODULE TYPE: DISK DRIVE SUPPORTED: YES PRIORITY LEVEL: BUFFERED NPR TRANFER RATE: 212 … Знания об ограничениях сохраняются в виде правил в памяти продукционной системы программы R1. Левая часть правил описывает условия (ситуацию), при соблюдении которых возможно расширение частичной конфигурации, а правая часть описывает, как выполняется расширение. В начале сеанса работы с системой рабочая память пуста, а в конце сеанса в ней содержится описание сформированной конфигурации. Компоненты в этом описании представлены в виде лексем, имеющих вид векторов, состоящих из элементов «атрибут-значение». С информацией, хранящейся в базе данных компонентов, система R1 может выполнять пять видов операций: генерировать новую лексему, отыскивать лексему, отыскивать подстановку для заданной лексемы, извлекать атрибуты, связанные с заданной лексемой, и извлекать шаблон, который в дальнейшем должен быть заполнен. Помимо лексем компонентов, рабочая память содержит элементы, которые представляют частичные конфигурации оборудования, результаты вычислений и символьное описание текущей задачи. Система R1 хранит порядка 10 000 правил, значительная часть которых определяет, какое следующее действие должна выполнить программа. Пример одного из таких правил приведен ниже. DISTRIBUTE-MB-DEVICES-3 ЕСЛИ: предыдущим активным контекстом является расширение количества устройств, подключаемых к шине MASSBUS, & имеется однопортовый НМД, не подключенный к MASSBUS, & отсутствуют двухпортовые НМД, еще не подключенные к MASSBUS, & количество устройств, которое можно подключить к расширителю MASSBUS, известно & существует расширитель MASSBUS, к которому подключен по крайней мере один НМД и который может поддерживать дополнительные НМД, & известен тип кабеля, которым должен быть связан НМД с ранее установленным устройством, ТО: подключить НМД к MASSBUS. Такие управляющие знания о предметной области (domain-specific control knowledge) позволяют программе R1 принимать решение о том, с чего начинать и как расширять структуру комплекса, не используя при этом сложной процедуры поиска. Как мы увидим далее, программа R1, как правило, не нуждается в обратном прослеживании неудовлетворительных решений, которое можно было бы использовать для отмены сформированной частичной конфигурации и замены ее новой. Использованные в R1 управляющие знания малочувствительны к очередности применения отдельных правил. Этим она отличается от систем, в которых общая задача конфигурирования решается разделением на подзадачи и выбором групп правил, соответствующих определенной подзадаче. В результате процесс решения проблемы в R1 направляется последовательностью правил, активизированных последними. Особенность процедур вывода в системе R1 состоит в том, что поиск решения осуществляется методом сопоставления, а не методом «генерация и проверка». То есть используется безвозвратная технология. При безвозвратном управлении применимое правило используется необратимо. Метод составления применим, когда знания, используемые на каждом шаге, достаточны для того, чтобы отличить приемлемое решение от неприемлемого. Почти все задачи, решаемые системой R1, удовлетворяют этому требованию, что и позволило избежать перебора при поиске решения. R1 превосходила эксперта-человека по качеству работы и по времени решения задачи. ЭС R1 безошибочно определяла конфигурацию за 2,5 мин., а эксперт затрачивал на работу несколько часов, допуская ошибки. Обнаруживаемые только после установки системы. Инструментальная система HEARSAY-III HEARSAY-III (Н-3) - комплекс программных средств, независимых от предметной области и предназначенных для построения ЭС. Н-3 управляет взаимодействием независимых источников знаний. Взаимодействие между модулями и правилами в Н-3 осуществляется через общую область памяти, которую назвали «классной доской» (blackboard) [Corkill]. • Представьте себе группу экспертов, которые сидят возле классной доски (или большой доски объявлений) и пытаются решить какую-либо проблему. • Каждый эксперт является специалистом в какой-то определенной области, имеющей отношение к решению проблемы. • Формулировка проблемы и исходные данные записаны на доске. • Эксперты пытливо вглядываются в то, что написано на доске, и каждый из них думает над тем, чем он может помочь в решении проблемы. • Если кто-либо из экспертов чувствует, что ему есть что сказать по этому поводу, он выполняет соответствующие вычисления и записывает результат все на той же доске. • Этот новый результат может позволить и другим экспертам внести определенный вклад в решение проблемы. • Процесс прекращается (а эксперты расходятся по домам), когда проблема будет решена. Такая методика совместного решения проблем будет эффективна, если соблюдаются определенные соглашения, а именно: • все эксперты должны говорить на одном и том же языке, хотя при записи результатов на доске могут использоваться и разные схемы обозначений; • должен существовать какой-то протокол определения очередности «выступлений», который вступает в силу в ситуации, когда сразу несколько экспертов хватаются за мел и направляются к доске. Если рассматривать работающую по такому принципу систему с точки зрения организации процесса вычислений, то в системе можно выделить следующие структурные компоненты. Знания о предметной области разделены между независимыми источниками знаний (KS— knowledge sources), которые работают под управлением планировщика (scheduler). Решение формируется в некоторой глобально доступной структуре, которую мы будем также называть доской объявлений (blackboard). Таким образом, в этой системе все знания «как поступить» будут представлены не в виде единственного набора правил, а в виде набора программ. Каждый из компонентов этого набора может располагать собственным набором правил либо смесью правил и процедур. Функции доски объявлений во многом сходны с функциями рабочей памяти в продукционных системах, но ее организационная структура значительно сложнее. Как правило, доска объявлений разделяется на несколько уровней описания, причем каждый уровень соответствует определенной степени детализации. Данные в пределах отдельных уровней доски объявлений представляют иерархии объектов или графы, т.е. структуры более сложные, чем векторы, которые использовались в рабочей памяти продукционных систем. В самых современных системах может быть даже несколько досок объявлений. Источники знаний формируют объекты на доске объявлений, но это выполняется посредством планировщика. Обычно записи активизации источников знаний (knowledge source activation records) помещаются в специальный список выбора (agenda), откуда их извлекает планировщик. Источники знаний общаются между собой только через доску объявлений и не могут непосредственно передавать данные друг другу или запускать выполнение каких-либо процедур. Здесь есть определенная аналогия с организацией работы продукционных систем, в которых правила также не могут непосредственно активизировать друг друга: все должно проходить через рабочую память. Архитектура на основе доски объявлений «выросла» из разработанной в конце 70-х годов системы распознавания речи HEARSAY-II [Erman et al.]. Программирование компьютера с целью распознавания речи — это одна из наиболее сложных задач, за которые когда-либо брались специалисты в области искусственного интеллекта. Ее решение требует: • сложной обработки сигналов; • сопоставления физических характеристик звуковых сигналов с символическими элементами естественного языка; • выполнения поиска в большом пространстве возможных интерпретаций, в котором объединены эти разные по своей природе элементы. Для решения этой проблемы была выбрана методика, основанная на выделении нескольких уровней абстракции описания анализируемых данных. Самым нижним является уровень физических акустических сигналов, на котором формируется звуковой спектр анализированных сигналов. На последующих уровнях информация проходит через напластование лингвистических абстракций со все более увеличивающимся уровнем общности понятий — фонемы, силлабы (созвучия), морфемы, слова, выражения и предложения. Приступая к разработке системы, ее создатели прекрасно понимали, что с каждым уровнем анализа связана отдельная отрасль знаний — анализ звуковых сигналов, фонетика, лексический анализ, грамматика, семантика, ораторское искусство. Ни одна из этих отраслей по отдельности не способна предоставить достаточно информации для того, чтобы решить проблему. Представим, например, что, пользуясь методами обработки акустических сигналов, мы смогли разложить исходный звук на фонемы. Но без дополнительной информации все равно не удастся выделить смысл выражений, подобных следующим: l scream (я восклицаю) и ice cream (мороженое) или please let us know (пожалуйста, дайте нам знать) и please lettuce no (пожалуйста,- без салата). Таким образом, хотя каждый отдельный вид (набор) знаний играет существенную роль в решении проблемы и каждый из них может быть представлен в программе более или менее независимо от остальных, автоматическое распознавание речи требует использования всех этих знаний совместно. При распознавании речи исследователям приходится сталкиваться еще с одной проблемой, которую также можно отнести к числу ключевых, — проблемой неопределенности. Она проявляется на всех уровнях представления информации: • данные неполные и зашумлены; • отсутствует однозначное соответствие между данными на соседних уровнях; примером может служить соответствие между уровнями фонем и лексических единиц при анализе фраз / scream и ice cream; • важную роль играют лингвистический и смысловой контексты; интерпретация соседних элементов делает более или менее вероятными разные варианты интерпретации текущего сегмента. Более традиционные подходы к распознаванию речи основаны на использовании статистических моделей из теории передачи информации для определения корреляционной связи между сегментами. Подход, базирующийся на знаниях, потребовал существенного пересмотра методов обработки неопределенности. Перечислим следующие требования, которым должна удовлетворять эффективно работающая система распознавания речи, основанная на знаниях [Erman et al., 1980]. 1. Из всех возможных последовательностей операций (частных решений) хотя бы одна должна приводить к корректной интерпретации. 2. Процедура анализа имеющихся вариантов интерпретации должна давать корректному варианту более высокую оценку, чем другим конкурирующим вариантам. Другими словами, правильная интерпретация с учетом произношения должна быть оценена выше, чем другие варианты интерпретации, не учитывающие особенностей индивидуальной дикции. 3. Вычислительные ресурсы (память и время вычислений), необходимые для отыскания правильной интерпретации, не должны превышать определенный порог. Система распознавания, которая через пару дней выдаст результат, пусть и правильный, и потребует памяти объемом несколько гигабайт, вряд ли кому-нибудь будет нужна. В приведенном списке первое и третье требования в определенной мере противоречат друг другу. Для того чтобы корректное решение изначально присутствовало в пространстве гипотез, на стадии формирования гипотез поневоле приходится быть довольно расточительным, что при большом словаре может привести к комбинаторному взрыву элементов решений. Выход может быть найден только при использовании чрезвычайно остроумных эвристик. Таким образом, важнейшей предпосылкой достижения успеха в создании такой системы является разработка подходящей процедуры оценки вариантов (второе из перечисленных выше требований). Для генерации, комбинирования и развития гипотез интерпретации в системе HEARSAY-II используется несколько источников знаний. Созданные гипотезы (интерпретации) разного уровня абстракции сохраняются на доске объявлений. Каждый источник знаний можно считать в первом приближении набором пар «условие-действие», хотя они могут быть реализованы и в форме, отличной от порождающих правил (например, условия и действия могут быть в действительности произвольными процедурами). Поток управления в этой системе также отличается от потока управления в продукционных системах. Вместо того чтобы в каждом цикле интерпретатор анализировал выполнение условий, специфицированных в источниках знаний, источники знаний загодя объявляют об активизированных в них условиях, извещая, какой вид модификации данных будет влиять на выполнение этих условий. В результате система управляется прерываниями, а этот режим управления значительно эффективнее, чем режим циклического просмотра состояния, который является основным для продукционных экспертных систем. Такой режим напоминает использование демонов во фреймовых системах, где поток управления регулируется обновлением данных. Источники знаний связываются с уровнями доски объявлений следующим образом. Условия, специфицированные в источнике знаний, будут удовлетворяться в результате обновления данных на определенном уровне доски объявлений. Источник знаний также может записывать данные в определенный уровень, причем не обязательно в тот же, который влияет на выполнение условий. Большинство источников знаний в системе HEARSAY-II организовано так, что они распознают данные на определенном уровне лингвистического анализа, а выполняемые ими операции относятся к следующему по порядку уровню. Например, некоторый источник активизируется данными на силлабическом уровне и формирует лексическую гипотезу на уровне слов. В несколько упрощенном виде архитектура системы HEARSAY-II представлена на рис. 12. Рис. 12 Стрелки, направленные от уровней доски объявлений к источникам знаний, указывают, данные какого уровня изменяют выполнение условий, специфицированных в источнике знаний. Стрелки в обратном направлении указывают, на какой уровень помещает данные тот или иной источник знаний. Ответвление от стрелки «действия» источника знаний к монитору доски объявлений означает, что изменение данных, выполненное одним источником знаний, фиксируется в мониторе и затем используется планировщиком для активизации другого источника знаний. Самое главное отличие архитектуры с доской объявлений заключается в том, что такая система не диктует проектировщику определенный режим управления знаниями в системе, например нисходящую или восходящую стратегию построения рассуждений. Например, в той области, для которой создавалась система HEARSAY-II, можно применять и нисходящую стратегию — строить гипотезы о словах, а затем искать подтверждения этим гипотезам на уровне фонем, а можно и восходящую — собирать гипотезы о фонемах и формировать по ним гипотезы о словах. Какой источник знаний будет активизирован, определяется монитором и планировщиком системы, а это решение можно сделать или независимым от предметной области, т.е. от соответствующих источников знаний, или зависимым от них. Здесь архитектура системы никак не связывает разработчика в выборе проектного решения. Система HEARSAY-III — это оболочка системы с доской объявлений, созданная на базе HEARSAY-II точно так же, как оболочка продукционной системы EMYCIN была создана на базе MYCIN [Erman et al]. В структуру HEARSAY-III, помимо источников знаний и доски объявлений, включена еще и реляционная база данных, с помощью которой выполняется обслуживание объектов доски объявлений и планирование. Это позволило существенно упростить механизм выбора записей активизации источников знаний. Язык управления базой данных АРЗ основан на языке InterLISP и позволяет программировать выполнение ряда функций оболочки [Goldman]. • Структурные компоненты доски объявлений— это объекты языка АРЗ. Такой объектно-ориентированный подход упрощает представление и операции с данными и частными решениями. • Активизация источников знаний реализуется с помощью управляемых образцами демонов АРЗ. • АРЗ поддерживает и операции с базой данных контекстов, а условия превращения контекста в «отравленный» представлены в виде ограничений языка. Контексты можно использовать для организации набора альтернативных способов продолжения вычислений. Источник знаний в экспертной системе, создаваемой на базе оболочки HEARSAY-I1I, должен состоять из пускового образца (trigger), первичной программы (immediate code) и тела (body). Обнаружив соответствие между текущим содержимым доски объявлений и пусковым образцом, оболочка создает узел записи активизации для этого источника знаний и запускает на выполнение первичную программу. Спустя некоторое время запись активизации источника знаний выбирается планировщиком и тогда запускается на выполнение тело источника знаний, которое представляет собой программу на языке LISP. В состав HEARSAY-III входит простейший планировщик, который выполняет базовые функции планирования в экспертной системе: выбор очередной записи в списке актуальных и запуск на выполнение программного кода соответствующего источника знаний. Пусковой образец имеет вид шаблона на языке АРЗ и представляет собой предикат, примитивами которого являются шаблоны фактов и произвольные предикаты языка LISP. Всякий раз, когда база данных модифицируется и оказывается, что текущие данные в ней сопоставимы со всеми шаблонами в образце, создается узел записи активизации, который хранит название источника знаний, пусковой контекст и значения переменных, полученные в результате сопоставления. При создании записи активизации выполняется первичная программа источника знаний. Эта программа, написанная на языке LISP, может связывать с узлом записи активизации некоторую информацию, которая позже может быть использована при выполнении тела источника. Первичная программа выполняется в пусковом контексте и в ней могут использоваться конкретизированные в этом контексте переменные образца. Значение, возвращаемое первичной программой после завершения, — это имя какого-либо из классов узлов доски объявлений. Затем запись активизации помещается на доску объявлений в качестве узла этого класса. Некоторое время спустя базовый планировщик системы, который входит в состав оболочки HEARSAY-III, инициирует выполнение какой-либо операции с записью активизации. Как правило, это выполнение тела источника знаний в пусковом контексте с означенными переменными. Каждый сеанс выполнения тела источника знаний неделим — это аналог транзакции в системах управления базами данных. Сеанс продолжается до полного завершения и не может быть прерван для активизации любого другого источника знаний. При проектировании прикладной экспертной системы на базе оболочки HEARSAY-III нужно самостоятельно разработать процедуру базового планировщика, которая будет вызываться оболочкой после запуска. Эта процедура может быть достаточно простой, поскольку большая часть знаний о планировании может быть включена в планирующие источники знаний. Например, базовый планировщик может представлять собой простейшую циклическую процедуру, которая извлекает первый элемент из очереди, организованной планирующими источниками знаний, и запускает его выполнение. Если обнаруживается, что очередь пуста, базовый планировщик завершает работу системы. Основные достоинства среды HEARSAY-III — это, во-первых, использованный в ней режим управления, который предоставляет разработчикам прикладных экспертных систем большую свободу в выборе способов представления и применения эвристик отбора активизируемых записей источников знаний, а во-вторых, структуризация множества объектов доски объявлений. Инструментально исследовательская система RLL. Характеристика, отличительные особенности Данная система предусматривает структурированный набор программных средств, предназначенных для конструирования, использования и модификации экспертных систем. RLL – экспертная система, предметной областью которой является построение экспертных систем. База знаний RLL содержит общую информацию о программировании и конкретную информацию о разрабатываемой системе. Факты в системе RLL представляются в виде фреймов. В виде фреймов представляются также все понятия, слоты, механизмы наследования, управляющие структуры и правила. Кроме слотов соответствующих «условию» и «действию» в правилах имеются слоты, задающие различную метаинформацию, которая используется при работе системы. Например: «приоритет», «среднее время работы», «дата создания правил» и так далее. Система RLL содержит набор полезных конструкций (различные типы управляющих механизмов, слотов, схем наследования и методов ассоциаций). RLL организует свои конструкции в библиотеку и представляет пользователю средства для работы с этой библиотекой. Сила RLL обусловлена общностью используемых информационных структур и алгоритмов. Система может рассуждать о своих собственных действиях и данных. За достигнутую гибкость RLL расплачивается памятью, а не временем.