Системы искусственного интеллекта.

Системы искусственного интеллекта. Лекция 1. Искусственный интеллект. Введение. Целью данного курса является рассмотрение такого понятия как «Искусственный интеллект» (ИИ), а если быть конкретней - основных направлений развития систем искусственного интеллекта (СИИ) и задач, которые данные системы способны решать. Прежде чем пытаться раскрыть понятие ИИ, необходимо разобраться с вопросом «А что же такое интеллект?» ИНТЕЛЛЕКТ (от лат. intellectus познание, понимание, рассудок) – это способность мышления, рационального познания. Но данное определение слишком расплывчатое, не дающее конкретного понимания этого слова. Поэтому введем более конкретную для нашего случая фразу, определяющую понятие данного термина: Интеллект – это способность решать ранее неизвестные задачи. Если рассматривать в качестве обладателя интеллекта человека, то несложно заметить, что мы непрерывно на протяжении всей своей жизни решаем задачи: от самых маленьких и простых, казалось бы, незаметных, таких как обойти или перескочить лужу, попытаться угнаться за трамваем или подождать следующий, до более глобальных и сложных, таких как спроектировать и построить уникальный космический корабль или провести выгодную военную компанию. Как видно из примеров, задачи бывают достаточно различными, но можно попытаться раскрыть общую модель. Известно, что задачи возникают при взаимодействии объекта с субъектом. Объект (в нашем случае) – это нечто, обладающее определенными свойствами и характеристиками. Субъект – нечто, способное воспринимать свойства и характеристики объекта, и возможно изменять их. Взаимодействие субъекта с объектом и определяет задачу субъекта. Понятие "решать" подразумевает нахождение решения, верного в некотором приближении, которое устраняет (разрешает) данную проблемную ситуацию полностью либо частично (приемлемую ее часть), постоянно или временно (на приемлемый срок). Задачу можно разбить на ряд подзадач: 1. Сбор информации об объекте. 2. Восприятие информации. 3. Анализ информации. 4. Постановка задачи. 5. Поиск решений задачи. 6. Выбор оптимального решения. 7. Осуществление действий, направленных на объект. Рассмотрим небольшой пример. Предположим ситуацию: мы управляем транспортным средством и догнали впереди идущий автомобиль, навстречу едет другой автомобиль. Возникает вопрос: Что делать? В данном случае объектом воздействия является не только наш автомобиль, а вся среда целиком, включая встречный и попутный автомобили, на которые мы можем повлиять коренным образом, а также погодные условия и дорогу, которые только лишь информируют нас о среде. Субъектом данной ситуации являемся мы. Теперь решаем нашу задачу: 1. Собираем информацию. За сбор информации у нас отвечают органы чувств. В данном случае зрение. Мы примерно определяем скорость и габариты впереди идущего автомобиля, скорость и расстояние до встречного автомобиля, скорость и мощность своего автомобиля, состояние дороги и погодные условия. 2. Следующий этап – восприятие информации. Полученную информацию мы описываем в удобных для нас терминах исходя из своего опыта: Быстро или медленно, далеко или близко, ухабистая дорога или ровная, с поворотом или без, скользко, мокро или сухо и т.д. 3. Далее мы анализируем информацию, определяем наиболее важные показатели объекта. 4. За тем ставим перед собой задачу: определить наши действия в данной ситуации. 5. Выполняя поиск возможных решений задачи в нашем случае, мы получаем три возможных решения: не обгонять впереди идущий автомобиль, обогнать, но только после проезда встречного автомобиля и выполнить маневр обгона, не дожидаясь встречного транспорта. 6. Теперь у нас есть множество решений, из которых мы выбираем оптимальное. 7. Далее остается осуществить выбранный маневр. Стоит обратить внимание на то, что каждая из рассмотренных подзадач, может быть выделена как отдельная независимая задача с определенным набором входных и выходных параметров. Подобный системный подход существенно упрощает решение сложных, глобальных задач. Немаловажными являются такие показатели решения задачи, как качество и стоимость. Качество решения определяет собственно характеристики полученного результата. Простыми словами - выгоду полученного решения. Стоимость решения определяет затраты на полученный результат. Стоимость может определяться затратами времени, памяти, интеллектуального или физического напряжения, денежными затратами и т.д. Соотношение Стоимость/Качество - это немаловажный показатель при решении задач. Самым распространенным примером являются покупки. Мы всегда задаем вопрос: стоит ли платить такие большие деньги за этот качественный товар? А может взять чуточку менее качественный, но на много дешевле? Теперь можно дать наиболее полное определение интеллекта. Интеллект - это способность самостоятельно, эффективно (верно, с возможно меньшими затратами ресурсов) находить качественные (верные, простые, требующие как можно меньших затрат ресурсов) решения (в том числе новые, ранее неизвестные) разнообразных сложных "задач", в том числе новых, ранее неизвестных (в идеале - любых возможных "задач"). Искусственный интеллект – это раздел информатики, включающий разработку методов моделирования и воспроизведения с помощью ЭВМ отдельных функций творческой деятельности человека, решение проблемы представления знаний в ЭВМ и построение баз знаний, создание экспертных систем, разработку интеллектуальных роботов и т.д.. Интеллект характеризуется уровнем и величиной (величинами). Интеллект обычно подразделяют на 4 уровня: • Интеллект уровня 0 - это способность субъекта решать известные "задачи" известными, неизменными методами. Характеризуется скоростью нахождения решений и качеством известных методов (решений). Примеры: инстинкт, программа, алгоритм, прошивка ПЗУ. Сложность построения искусственного интеллекта уровня 0 определяется только сложностью целевого класса задач. Системы ИИ уровня 0 для классов простых задач обычно не считаются интеллектуальными. • Интеллект уровня 1 - это способность субъекта улучшать, оптимизировать известные решения задач известных классов. Это способность обучаться, совершенствоваться эволюционным путем. Характеризуется обучаемостью - скоростью обучения и эффективностью - количественным увеличением величины интеллекта уровня 0. Прямые измерения величины интеллекта уровня 1 затруднены. Примеры: адаптация живых организмов; генетические алгоритмы. Рассмотрение класса задач оптимизации приводит к возможности эмуляции интеллекта уровня 1 системами, с интеллектом уровня 0. Пример: программные пакеты, решающие задачи оптимизации математического программирования. Системы ИИ уровня 1 обычно называют интеллектуальными. • Интеллект уровня 2 - это способность субъекта находить новые решения задач известных классов. Его реализация во многом зависит от внешних условий, от того, существуют ли, в принципе, новые, более эффективные решения этих классов задач. Находит себе новые применения по мере возрастания величины интеллекта уровня 0. Трудноизмерим. Возможны численные описания через частоту его применения и эффективность (насколько новые решения лучше известных?). Представляет собой революционный путь совершенствования. Близкие понятия: креативность, относительная новизна, изобретательность. Интеллект уровня 2 иногда проявляется у высших животных при решении простых задач. При решении сложных классов задач проявляется далеко не у всех людей. • Интеллект уровня 3 - это способность субъекта находить (создавать) решения для ранее неизвестных классов задач. Способность решать любые новые задачи. Важнейшая составляющая - это способность к обнаружению новых задач и формулировки их условий. Трудноизмерим. Возможно описание через измерение новизны классов задач (необходим учет топологии и метрики пространства классов задач). Наличие интеллекта уровня 3 есть безграничность интеллекта, потенциальная бесконечность возможных классов разрешимых задач, потенциальная бесконечность самосовершенствования объекта. Дополнительное качественное отличие: если для предыдущих уровней, все сводилось к увеличению интеллекта уровня 0, то для интеллекта уровня 3 это маловажно. Освоение новых классов задач на много порядков лучше (эффективнее, ценнее, выгоднее, интереснее...), чем совершенствование способностей по решению старых задач. Объект с интеллектом уровня 3 может существенно уступать каким-либо другим объектам с интеллектом уровня 0 на каком-либо (или даже на любом) отдельном классе известных задач. Близкие понятия: абсолютная новизна, научное открытие, изобретение, гениальность. Следует полагать, что системы ИИ уровня 3 не могут быть разработаны в обозримом будущем и этот уровень интеллектуальной деятельности останется для человека, точнее для лучших (гениальных) представителей человечества. Интеллект необходим для функционирования в сложной среде, для достижения объектом своих целей (в первую очередь для гомеостаза, выживания, продолжение рода). Интеллект не требует наличия сознания. Сознание - это производная интеллекта. Можно считать, что интеллект заключен (и) в бессознательном. Общепринятая концепция обучения требует от учащихся наличия интеллекта лишь 0-го и, отчасти, 1-го уровня. Современная система среднего и, де-факто, высшего образования направлена на развитие только 0-го уровня интеллекта. Важнейшей задачей человечества является переориентация обучения на развитие 2-го и 3-го уровня интеллекта. Лекция 2. Краткий исторический обзор развития работ в области ИИ. 1. Начало исследований в области ИИ (конец 50-х годов) связывают с работами Ньюэлла, Саймана и Шоу, исследовавших процессы решения различных задач. Результатами их работ явились такие программы как "ЛОГИК-ТЕОРЕТИК", предназначенная для доказательства теорем в исчислении высказываний, и "ОБЩИЙ РЕШАТЕЛЬ ЗАДАЧ". Эти работы положили начало первому этапу исследований в области ИИ, связанному с разработкой программ, решающих задачи на основе применения разнообразных эвристических методов. Эвристический метод решения задачи при этом рассматривался как свойственный человеческому мышлению "вообще", для которого характерно возникновение догадок о пути решения задачи с последующей их проверкой. Ему противопоставлялся используемый в ЭВМ алгоритмический метод, который интерпретировался как механическое осуществление заданной последовательности шагов, детерминировано приводящей к правильному ответу. Трактовка эвристических методов решения задач как сугубо человеческой деятельности и обусловила появление и дальнейшее распространение термина ИИ. Так, при описании своих программ Ньюэлл и Саймон приводили в качестве доводов, подтверждающих, что их программы моделируют человеческое мышление, результаты сравнения записей доказательств теорем в виде программ с записями рассуждения <думающего вслух> человека. В начале 70-х годов они опубликовали много данных подобного рода и предложили общую методику составления программ, моделирующих мышление. 2. Примерно в то время, когда работы Ньюэлла и Саймона стали привлекать к себе внимание, в Массачусетсском технологическом институте, Стэнфордском университете и Стэнфордском исследовательском институте также сформировались исследовательские группы в области ИИ. В противоположность ранним работам Ньюэлла и Саймона эти исследования больше относились к формальным математическим представлениям. Способы решения задач в этих исследованиях развивались на основе расширения математической и символической логики. Моделированию же человеческого мышления придавалось второстепенное значение. 3. На дальнейшие исследования в области ИИ большое влияние оказало появление метода резолюций Робинсона, основанного на доказательстве теорем в логике предикатов и являющегося исчерпывающим методом доказательства. При этом определение термина ИИ претерпело существенное изменение. Целью исследований, проводимых в направлении ИИ, стала разработка программ, способных решать "человеческие задачи". Так, один из видных исследователей ИИ того времени Р. Бенерджи в 1969 году писал: "Область исследований, обычно называемую ИИ, вероятно, можно представить как совокупность методов и средств анализа и конструирования машин, способных выполнять задания, с которыми до недавнего времени мог справиться только человек. При этом по скорости и эффективности машины должны быть сравнимы с человеком". Функциональный подход к направленности исследований по ИИ сохранился в основном до настоящего времени, хотя еще и сейчас ряд ученых, особенно психологов, пытаются оценивать результаты работ по ИИ с позиций их соответствия человеческому мышлению. Этапы исследований в рамках ИИ. Исследовательским полигоном для развития методов ИИ на первом этапе явились всевозможные игры, головоломки, математические задачи. Некоторые из этих задач стали классическими в литературе по ИИ (задачи об обезьяне и бананах, миссионерах и людоедах, Ханойской башне, игра в 15 и другие). Выбор таких задач обуславливался простотой и ясностью проблемной среды (среды, в которой разворачивается решение задачи), ее относительно малой громоздкостью, возможностью достаточно легкого подбора и даже искусственного конструирования "под метод". Основной расцвет такого рода исследований приходится на конец 60-х годов, после чего стали делаться первые попытки применения разработанных методов для задач, решаемых не в искусственных, а в реальных проблемных средах. Необходимость исследования систем ИИ при их функционировании в реальном мире привело к постановке задачи создания интегральных роботов. Проведение таких работ можно считать вторым этапом исследований по ИИ. В Стэнфордском университете, Стэнфордском исследовательском институте и некоторых других местах были разработаны экспериментальные роботы, функционирующие в лабораторных условиях. Проведение этих экспериментов показало необходимость решения кардинальных вопросов, связанных с проблемой представления знаний о среде функционирования, и одновременно недостаточную исследованность таких проблем, как зрительное восприятие, построение сложных планов поведения в динамических средах, общение с роботами на естественном языке. Эти проблемы были более ясно сформулированы и поставлены перед исследователями в середине 70-х гг., связанных с началом третьего этапа исследований систем ИИ. Его характерной чертой явилось смещение центра внимания исследователей с создания автономно функционирующих систем, самостоятельно решающих в реальной среде поставленные перед ними задачи, к созданию человеко-машинных систем, интегрирующих в единое целое интеллект человека и способности ВМ для достижения общей цели - решения задачи, поставленной перед интегральной человеко-машинной системой. Такое смещение обуславливалось двумя причинами: • К этому времени выяснилось, что даже простые на первый взгляд задачи, возникающие перед интегральным роботом при его функционировании в реальном времени, не могут быть решены методами, разработанными для экспериментальных задач в специально сформированных проблемных средах; • Стало ясно, что сочетание дополняющих друг друга возможностей человека и ЭВМ позволяет обойти острые углы путем перекладывания на человека тех функций, которые пока еще не доступны для ЭВМ. На первый план выдвигалась не разработка отдельных методов машинного решения задач, а разработка методов и средств, обеспечивающих тесное взаимодействие человека и вычислительной системы в течение всего процесса решения задачи с возможностью оперативного внесения человеком изменений в ход этого процесса. Четвертый этап исследований в рамках ИИ связан с искусственным воспроизведением эволюции. Этот подход основан на гипотезе, что человеческий интеллект, в своем развитии эволюционировал, благодаря процессу, включающему мутации и естественный отбор. При таком подходе систему ИИ, моделируемую на компьютере, заставляют эволюционировать путем мутаций и отбора. При этом предполагается, что компьютерная эволюция должна быть существенно более быстрой, чем естественная. На этом пути первоначально удалось добиться того, что системы ИИ эволюционировали до уровня способности решать простейшие задачи. Недостаточные познания в механизмах естественной эволюции и скромные успехи по ее моделированию, как и в случае с нейронными сетями, обусловили на многие годы весьма слабый интерес исследователей к этому направлению ИИ. В 90-е годы на новом витке спирали опять резко возрастает интерес к эволюционным методам ИИ. Теперь эти методы обычно дополняются т.н. генетическими алгоритмами и уже позволяют решать многие прикладные задачи, основанные на поиске и оптимизации. В частности, весьма перспективным представляется объединение эволюционного и нейронного подхода, при котором важную задачу эффективного обучения нейронных сетей принимают на себя эволюционные алгоритмы. Развитие исследований в рамках ИИ в данном направлении обусловливалось также резким ростом производства средств вычислительной техники и резким их удешевлением, делающим их потенциально доступными для более широких кругов пользователей. КЛАССИФИКАЦИЯ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ Интеллектуальная информационная система (ИИС) основа­на на концепции использования базы знаний для генерации ал­горитмов решения прикладных задач различных классов в зави­симости от конкретных информационных потребностей пользо­вателей. Для ИИС характерны следующие признаки: • развитые коммуникативные способности; • умение решать сложные плохо формализуемые задачи; • способность к самообучению; • адаптивность. Каждому из перечисленных признаков условно соответствует свой класс ИИС. Различные системы могут обладать одним или несколькими признаками интеллектуальности с различной сте­пенью проявления. Рис. 2.1 Класси­фикация ИИС Средства ИИ могут использоваться для реализации различ­ных функций, выполняемых ИИС. На рисунке приведена класси­фикация ИИС, признаками которой являются следующие интел­лектуальные функции: коммуникативные способности — способ взаимодействия ко­нечного пользователя с системой; решение сложных плохо формализуемых задач, которые требу­ют построения оригинального алгоритма решения в зависимости от конкретной ситуации, характеризующейся неопределеннос­тью и динамичностью исходных данных и знаний; способность к самообучению — умение системы автоматичес­ки извлекать знания из накопленного опыта и применять их для решения задач; адаптивность — способность системы к развитию в соответ­ствии с объективными изменениями области знаний. 1) Системы с интеллектуальным интерфейсом Применение ИИ для усиления коммуникативных способнос­тей информационных систем привело к появлению систем с ин­теллектуальным интерфейсом, среди которых можно выделить следующие типы. Интеллектуальные базы данных. Позволяют в отличие от традиционных БД обеспечивать выборку необходимой информа­ции, не присутствующей в явном виде, а выводимой из совокуп­ности хранимых данных. Естественно-языковой интерфейс. Применяется для досту­па к интеллектуальным базам данных, контекстного поиска до­кументальной текстовой информации, голосового ввода команд в системах управления, машинного перевода с иностранных язы­ков. Для реализации ЕЯ интерфейса необходимо решить пробле­мы морфологического, синтаксического и семантического ана­лиза, а также задачу синтеза высказываний на естественном язы­ке. При морфологическом анализе осуществляются распознавание и проверка правильности написания слов в словаре. Синтак­сический контроль предполагает разложение входных сообще­ний на отдельные компоненты, проверку соответствия граммати­ческим правилам внутреннего представления знаний и выявле­ние недостающих частей. Семантический анализ обеспечивает установление смысловой правильности синтаксических конст­рукций. В отличие от анализа синтез высказываний заключается в преобразовании цифрового представления информации в пред­ставление на естественном языке. Гипертекстовые системы. Используются для реализации поиска по ключевым словам в базах данных с текстовой инфор­мацией. Для более полного отражения различных смысловых от­ношений терминов требуется сложная семантическая организа­ция ключевых слов. Решение этих задач осуществляется с помо­щью интеллектуальных гипертекстовых систем, в которых меха­низм поиска сначала работает с базой знаний ключевых слов, а затем - с самим текстом. Аналогичным образом проводится по­иск мультимедийной информации, включающей кроме текста графическую информацию, аудио и видео образы. Системы контекстной помощи. Относятся к классу систем распространения знаний. Такие системы являются, как правило, приложениями к документации. Системы контекстной помощи – частный случай гипертекстовых и ЕЯ-систем. В них пользователь описывает проблему, а система на основе дополнительного диа­лога конкретизирует ее и выполняет поиск относящихся к ситуации рекомендаций. В обычных гипертекстовых системах, наоборот, компьютерные приложения навязывают пользователю схему поиска требуемой информации. Системы когнитивной графики. Ориентированы на общение с пользователем ИИС посредством графических образов, которые генерируются в соответствии с изменениями параметров моде­лируемых или наблюдаемых процессов. Когнитивная графика позволяет в наглядном и выразительном виде представить множе­ство параметров, характеризующих изучаемое явление, освобож­дает пользователя от анализа тривиальных ситуаций, способствует быстрому освоению программных средств и повышению конку­рентоспособности разрабатываемых ИИС. Применение когнитив­ной графики особенно актуально в системах мониторинга и опера­тивного управления, в обучающих и тренажерных системах, в опе­ративных системах принятия решений, работающих в режиме ре­ального времени. 2) Экспертные системы Экспертные системы как самостоятельное направление в ис­кусственном интеллекте сформировалось в конце 1970-х гг. Исто­рия ЭС началась с сообщения японского комитета по разработке ЭВМ пятого поколения, в котором основное внимание уделялось развитию «интеллектуальных способностей» компьютеров с тем, чтобы они могли оперировать не только данными, но и знания­ми, как это делают специалисты (эксперты) при выработке умо­заключений. Группа по экспертным системам при Комитете British Computer Society определила ЭС как «воплощение в ЭВМ компоненты опыта эксперта, основанной на знаниях, в такой форме, что машина может дать интеллектуальный совет или при­нять решение относительно обрабатываемой функции». Одним из важных свойств ЭС является способность объяснить ход своих рассуждений понятным для пользователя образом. Область исследования ЭС называют «инженерией знаний». Этот термин был введен Е.Фейгенбаумом и в его трактовке озна­чает «привнесение принципов и инструментария из области ис­кусственного интеллекта в решение трудных прикладных про­блем, требующих знаний экспертов». Другими словами, ЭС при­меняются для решения неформализованных проблем, к которым относят задачи, обладающие одной (или несколькими) из следу­ющих характеристик: задачи не могут быть представлены в числовой форме; исходные данные и знания о предметной области обладают неоднозначностью, неточностью, противоречивостью; цели нельзя выразить с помощью четко определенной целе­вой функции; не существует однозначного алгоритмического решения задачи; алгоритмическое решение существует, но его нельзя исполь­зовать по причине большой размерности пространства решений и ограничений на ресурсы (времени, памяти). Главное отличие ЭС и систем искусственного интеллекта от систем обработки данных состоит в том, что в них используется символьный, а не числовой способ представления данных, а в ка­честве методов обработки информации применяются процедуры логического вывода и эвристического поиска решений. ЭС охватывают самые разные предметные области, среди которых лидируют бизнес, производство, медицина, про­ектирование и системы управления. Во многих случаях ЭС являются инструментом, усиливаю­щим интеллектуальные способности эксперта. Кроме того, ЭС может выступать в роли: • консультанта для неопытных или непрофессиональных пользователей; • ассистента эксперта-человека в процессах анализа вариан­тов решений; • партнера эксперта в процессе решения задач, требующих привлечения знаний из разных предметных областей. Для классификации ЭС используются следующие признаки: • способ формирования решения; • способ учета временного признака; • вид используемых данных и знаний; • число используемых источников знаний. По способу формирования решения ЭС можно разделить на ана­лизирующие и синтезирующие. В системах первого типа осуще­ствляется выбор решения из множества известных решений на основе анализа знаний, в системах второго типа решение синте­зируется из отдельных фрагментов знаний. В зависимости от способа учета временного признака ЭС де­лят на статические и динамические. Статические ЭС предназ­начены для решения задач с неизменяемыми в процессе реше­ния данными и знаниями, а динамические ЭС допускают такие изменения. По видам используемых данных и знаний различают ЭС с детерминированными и неопределенными знаниями. Под неопреде­ленностью знаний и данных понимаются их неполнота, ненадеж­ность, нечеткость. ЭС могут создаваться с использованием одного или несколь­ких источников знаний. В соответствии с перечисленными признаками можно выде­лить четыре основных класса ЭС: классифицирующие, доопределяющие, трансформирующие и мультиагентные. Классифицирующие ЭС решают задачи распознавания ситуа­ций. Основным методом формирования решений в таких систе­мах является дедуктивный логический вывод. Доопределяющие ЭС используются для решения задач с не полностью определенными данными и знаниями. В таких ЭС возникают задачи интерпретации нечетких знаний и выбора аль­тернативных направлений поиска в пространстве возможных ре­шений. В качестве методов обработки неопределенных знаний могут использоваться байесовский вероятностный подход, коэф­фициенты уверенности, нечеткая логика. Трансформирующие ЭС относятся к синтезирующим динами­ческим экспертным системам, в которых предполагается повто­ряющееся преобразование знаний в процессе решения задач. В ЭС данного класса используются различные способы обработки знаний: • генерация и проверка гипотез; • логика предположений и умолчаний (когда по неполным данным формируются представления об объектах определенного класса, которые впоследствии адаптируются к конкретным усло­виям изменяющихся ситуаций); • использование метазнаний (более общих закономерностей) для устранения неопределенностей в ситуациях. Мультиагентные системы — это динамические ЭС, основан­ные на интеграции нескольких разнородных источников знаний. Эти источники обмениваются между собой получаемыми резуль­татами в ходе решения задач. Системы данного класса имеют сле­дующие возможности: • реализация альтернативных рассуждений на основе исполь­зования различных источников знаний и механизма устранения противоречий; • распределенное решение проблем, декомпозируемых на па­раллельно решаемые подзадачи с самостоятельными источниками знаний; • применение различных стратегий вывода заключений в за­висимости от типа решаемой проблемы; • обработка больших массивов информации из баз данных; • использование математических моделей и внешних про­цедур для имитации развития ситуаций. 3) Самообучающиеся системы Самообучающиеся интеллектуальные системы основаны на методах автоматической классификации ситуаций из реальной практики, или на методах обучения на примерах. Примеры ре­альных ситуаций составляют так называемую обучающую выбор­ку, которая формируется в течение определенного исторического периода. Элементы обучающей выборки описываются множест­вом классификационных признаков. Стратегия «обучения с учителем» предполагает задание спе­циалистом для каждого примера значений признаков, показыва­ющих его принадлежность к определенному классу ситуаций. При обучении «без учителя» система должна самостоятельно вы­делять классы ситуаций по степени близости значений класси­фикационных признаков. В процессе обучения проводится автоматическое построение обобщающих правил или функций, описывающих принадлеж­ность ситуаций к классам, которыми система впоследствии будет пользоваться при интерпретации незнакомых ситуаций. Из обоб­щающих правил, в свою очередь, автоматически формируется ба­за знаний, которая периодически корректируется по мере накоп­ления информации об анализируемых ситуациях. Построенные в соответствии с этими принципами самообу­чающиеся системы имеют следующие недостатки: относительно низкую адекватность баз знаний возникаю­щим реальным проблемам из-за неполноты и/или зашумленнос­ти обучающей выборки; низкую степень объяснимости полученных результатов; поверхностное описание проблемной области и узкую на­правленность применения из-за ограничений в размерности признакового пространства. Индуктивные системы позволяют обобщать примеры на ос­нове принципа индукции «от частного к общему». Процедура обобщения сводится к классификации примеров по значимым признакам. Алгоритм классификации примеров включает следу­ющие основные шаги. 1. Выбор классификационного признака из множества за­данных. 2. Разбиение множества примеров на подмножества по значе­нию выбранного признака. 3. Проверка принадлежности каждого подмножества приме­ров одному из классов. 4. Проверка окончания процесса классификации. Если ка­кое-то подмножество примеров принадлежит одному подклассу, т.е. у всех примеров этого подмножества совпадает значение классификационного признака, то процесс классификации за­канчивается. 5. Для подмножеств примеров с несовпадающими значения­ми классификационных признаков процесс распознавания про­должается, начиная с первого шага. При этом каждое подмноже­ство примеров становится классифицируемым множеством. Нейронные сети представляют собой классический пример технологии, основанной на примерах. Нейронные сети - обоб­щенное название группы математических алгоритмов, обладаю­щих способностью обучаться на примерах, «узнавая» впоследст­вии черты встреченных образцов и ситуаций. Благодаря этой способности нейронные сети используются при решении задач обработки сигналов и изображений, распознавания образов, а также для прогнозирования. Нейронная сеть - это кибернетическая модель нервной сис­темы, которая представляет собой совокупность большого числа сравнительно простых элементов — нейронов, топология соеди­нения которых зависит от типа сети. Чтобы создать нейронную сеть для решения какой-либо конкретной задачи, следует вы­брать способ соединения нейронов друг с другом и подобрать значения параметров межнейронных соединений. В системах, основанных на прецедентах, БЗ содержит описа­ния конкретных ситуаций (прецеденты). Поиск решения осуще­ствляется на основе аналогий и включает следующие этапы: • получение информации о текущей проблеме; • сопоставление полученной информации со значениями признаков прецедентов из базы знаний; • выбор прецедента из базы знаний, наиболее близкого к рас­сматриваемой проблеме; • адаптация выбранного прецедента к текущей проблеме; • проверка корректности каждого полученного решения; • занесение детальной информации о полученном решении в БЗ. Прецеденты описываются множеством признаков, по кото­рым строятся индексы быстрого поиска. Однако в системах, основанных на прецедентах, в отличие от индуктивных систем до­пускается нечеткий поиск с получением множества допустимых альтернатив, каждая из которых оценивается некоторым коэф­фициентом уверенности. Наиболее эффективные решения адап­тируются к реальным ситуациям с помощью специальных алго­ритмов. Системы, основанные на прецедентах, применяются для рас­пространения знаний и в системах контекстной помощи. Информационные хранилища отличаются от интеллектуальных баз данных, тем, что представляют собой хранилища значимой информации, регулярно извлекаемой из оперативных баз дан­ных. Хранилище данных - это предметно-ориентированное, ин­тегрированное, привязанное ко времени, неизменяемое собра­ние данных, применяемых для поддержки процессов принятия управленческих решений. Предметная ориентация означает, что данные объединены в категории и хранятся в соответствии с теми областями, которые они описывают, а не с приложениями, которые их используют. В хранилище данные интегрируются в целях удовлетворения требований предприятия в целом, а не от­дельной функции бизнеса. Привязанность данных ко времени выражает их «историчность», т.е. атрибут времени всегда явно присутствует в структурах хранилища данных. Неизменяемость означает, что, попав однажды в хранилище, данные уже не изме­няются в отличие от оперативных систем, где данные присутст­вуют только в последней версии, поэтому постоянно меняются. Технологии извлечения знаний из хранилищ данных основа­ны на методах статистического анализа и моделирования, ориен­тированных на поиск моделей и отношений, скрытых в совокуп­ности данных. Эти модели могут в дальнейшем использоваться для оптимизации деятельности предприятия или фирмы. Для извлечения значимой информации из хранилищ данных имеются специальные методы (OLAP-анализа, Data Mining или Knowledge Discovery), основанные на применении методов мате­матической статистики, нейронных сетей, индуктивных методов построения деревьев решений и др. Технология OLАР (On-Line Analytical Processing — оператив­ный анализ данных) предоставляет пользователю средства для формирования и проверки гипотез о свойствах данных или отно­шениях между ними на основе разнообразных запросов к базе данных. Они применяются на ранних стадиях процесса извлечения знаний, помогая аналитику сфокусировать внимание на важ­ных переменных. Средства Data Mining отличаются от ОLАР тем, что кроме проверки предполагаемых зависимостей они спо­собны самостоятельно (без участия пользователя) генерировать гипотезы о закономерностях, существующих в данных, и строить модели, позволяющие количественно оценить степень взаимного влияния исследуемых факторов на основе имеющейся информации. 4) Адаптивные информационные системы Потребность в адаптивных информационных системах возникает в тех случаях, когда поддерживаемые ими проблемные об­ласти постоянно развиваются. В связи с этим адаптивные системы должны удовлетворять ряду специфических требований», а именно: • адекватно отражать знания проблемной области в каждый момент времени; • быть пригодными для легкой и быстрой реконструкции при изменении проблемной среды. Адаптивные свойства информационных систем обеспечиваются за счет интеллектуализации их архитектуры. Ядром таких систем является постоянно развиваемая модель проблемной области, поддерживаемая в специальной базе знаний - репозитории. Ядро системы управляет процессами генерации или переконфигурирования программного обеспечения. В процессе разработки адаптивных информационных систем применяется оригинальное или типовое проектирование. Ориги­нальное проектирование предполагает разработку информационной системы с «чистого листа» на основе сформулированных требований. Реализация этого подхода основана на использова­нии систем автоматизированного проектирования, или САSЕ-технологии (Designer 2000, SilverRun и др.). При типовом проектировании осуществляется адаптация новых разработок к особенностям проблемной области. Для реализации этого подхода применяются инструментальные средства компонентного (сборочного) проектирования информационных систем (R/3, ВААN IV, Рrodis и др.). Главное отличие подходов состоит в том, что при использова­нии САSЕ-технологии на основе репозитория при изменении проблемной области каждый раз выполняется генерация про­граммного обеспечения, а при использовании сборочной техно­логии — конфигурирование программ и только в редких случаях — их переработка. Лекция 3. Задачи и области применения систем ИИ Области приме­нения систем искусственного интеллекта (практический аспект) Обработка естественного языка. Когда люди общаются между собой на естественном языке (ЕЯ), они практически без всяких усилий используют сложные и пока малопонятные процессы. Оказалось, что построить машины, способные “понимать” хотя бы фрагменты ЕЯ, чрезвычайно трудно. Одной из причин является то обстоятельство, что ЕЯ возник как средство общения интеллектуальных существ. При таком общении происходит как бы передача некоторой порции “умственной структуры” от одного мозга к другому в условиях, когда каждый мозг располагает большими и весьма подобными друг другу “умственными структурами”, служащими в качестве общего контекста. Это позволяет участникам разговора использовать колоссальные интеллектуальные ресурсы и совместные знания для создания и восприятия чрезвычайно сжатых сообщений. Вычислительная система, способная понимать сообщение на ЕЯ, нуждается, как и человек и в контекстуальных знаниях и в механизмах, обеспечивающих логический вывод из этих контекстуальных знаний и сообщений, так как генератор сообщения на ЕЯ уже предполагает наличие этих ресурсов и механизмов. К настоящему времени, благодаря некоторым представлениям из ИИ, есть реальные результаты в решении задач синтеза и анализа письменных и устных фрагментов речи, задач машинного перевода с одного языка на другой с определенными ограничениями. Направление вошло в практическую стадию разработок прикладных систем. Вместе с тем, и дальнейший прогресс в этой области, по-видимому, будет тесно связан с общим развитием теории ИИ. Извлечение информации из баз данных. Базы данных (БД) представляют собой программные пакеты, в которых хранятся большие объемы сведений, относящихся к определенной предметной области. БД формируется таким образом, чтобы из нее можно было извлекать нужные сведения в виде ответов на вопросы по данной предметной области. В настоящее время существует много разнообразных приемов построения БД и способов извлечения информации из них. В рамках дисциплины ИИ нас интересует постановка вопроса по БД, а именно - как извлечь из БД ответ на вопрос, для которого необходимо провести дедуктивные рассуждения со сведениями, хранящимися в БД. Здесь возникает несколько проблем. Проблема 1. Построение системы, способной воспринимать вопросы на ЕЯ. (Об этом только что шла речь по первой прикладной области ИИ). Частичное, обходное решение этой проблемы состоит в создании некоторого формального, понятного машине языка запросов из БД. Проблема 2. Логический дедуктивный вывод ответа на поставленный вопрос, исходя из хранящихся в БД сведений. Проблема 3. Для понимания вопроса и вывода ответа может потребоваться информация, выходящая за рамки той, которая в явном виде представлена в БД предметной области. Пример. В БД отдела кадров некоторой фирмы среди прочих имеются следующие сведения: 1. Джон Смит работает в отделе закупок. 2. Джон Смит поступил на работу 8 октября 1997 г. 3. В отделе закупок 17 сотрудников. 4. Роберт Стейк является главой отдела закупок. В систему поступает вопрос: “Кто является боссом Джона Смита?” Для того чтобы правильно ответить на поставленный вопрос: “Роберт Стейк” система должна каким-то образом знать, что глава некоторого отдела является боссом для людей, работающих в этом отделе. Каким образом представлять и извлекать необходимые знания, является одной из важнейших задач, для решения которой могут быть привлечены методы ИИ. Экспертные и консультирующие системы. Автоматические экспертные и консультирующие системы (АЭКС) призваны обеспечивать пользователя компетентными заключениями, касающимися определенных предметных областей. Известны АЭКС, диагностирующие заболевания, оценивающие потенциальные месторождения полезных ископаемых, предлагающие варианты возможных структур сложных органических соединений и многие другие. Ключевая проблема при построении АЭКС состоит в том, как представлять и использовать знания, которыми, очевидно, располагают и пользуются люди, являющими экспертами в предметных областях. Эта проблема осложняется еще и тем, что экспертные знания часто являются неточными, неопределенными и плохо формализуемыми. Тем не менее, эксперты успешно пользуются этими знаниями, делая полезные заключения. Во многих АЭКС применяется метод ИИ, связанный с логическим выводом, основанным на правилах. В таких системах экспертные знания представлены в виде большого множества простых правил, которые применяются при организации диалога между системой и пользователем, а также для вывода заключений. Дедукция, основанная на правилах, является одним из главных вопросов в исследованиях по ИИ. Доказательство теорем. Поиск доказательства (или опровержения) для некоторой математической теоремы, несомненно, может рассматриваться как пример интеллектуальной задачи. Во-первых, потому что для доказательства требуется способность провести дедукцию, исходя из гипотез. Во-вторых, для построения доказательства необходимы интуитивные навыки, такие как построение догадки о том, какие промежуточные леммы следует доказать, чтобы способствовать доказательству основной теоремы. Опытный математик, опираясь на некоторое собственное суждение, основанное на большом объеме специальных знаний, высказывает точную догадку, какие из ранее доказанных теорем в рассматриваемой предметной области будут полезны для искомого доказательства, выделяет в главной проблеме подзадачи, над которыми можно работать независимо друг от друга. В рамках ИИ был разработан ряд программ, которые в какой-то степени обладают некоторыми из таких способностей. Изучение приемов доказательства теорем сыграло большую роль в развитии методов ИИ. Многие неформализуемые задачи, включая медицинскую диагностику и извлечение информации, допускают их формализацию как задачу на доказательство теорем. Робототехника. В настоящее время это самостоятельная область науки и техники, выделившаяся из ИИ. Ее задачей является решение теоретических и практических вопросов организации целесообразного поведения подвижных роботов, снабженных сенсорными и эффекторными (исполнительными) механизмами. Перед такими роботами обычно ставится некоторая глобальная цель (например, для автономного подвижного робота-планетохода - достижение некоторой точки на поверхности другой планеты). Однако предполагается, что заранее невозможно полностью предсказать все возможные реакции со стороны окружающей среды робота. Поэтому многие проблемы своего поведения в окружающей среде робот должен решать самостоятельно, учитывая конкретные условия и используя при этом бортовую ЭВМ. На первый взгляд может показаться, что управление действиями мобильного робота не требует большого интеллекта и даже маленькие дети способны успешно находить дорогу в окружающей обстановке, манипулировать различными предметами (игрушками, кубиками, столовыми приборами, выключателями света и т.п.). Однако многие из этих задач, практически бессознательно выполняемые людьми, требуют для их решения способностей, присущих большому интеллекту. Исследования по робототехнике оказали существенное влияние на развитие многих идей ИИ. В частности они привели к созданию методов моделирования состояния мира и описания процесса воздействия одного состояния внешнего мира на другое, дали лучшее понимание того, каким образом строить планы для последовательности действий и как управлять выполнением этих планов. Методы планирования действий робота стали строить как многоуровневые системы с высоким уровнем абстракции на верхнем уровне и все более детализированные на последующих уровнях. Примером разработки систем такого рода являются работы по созданию системы управления автономным мобильным роботом-марсоходом. Автоматическое программирование. Существующие компиляторы в некотором смысле уже осуществляют автоматическое программирование. Они воспринимают полную спецификацию того, что программа должна делать, во входном коде и пишут программу в объектном коде. Под автоматическим программированием понимается некий “суперкомпилятор”, или программа, которая могла бы воспринимать описание на очень высоком уровне, вплоть до ЕЯ, того, что требуется от искомой программы. При этом, учитывая высокий уровень входного описания, и, следовательно, наличие неоднозначностей в этом описании, автоматическое программирование потребует, очевидно, дополнительного диалога между системой и пользователем для исключения неоднозначностей. Задача автоматического написания программы для достижения заданного результата тесно связана с задачей доказательства того, что программа достигнет этого результата. Эта задача получила название верификация программы. Многие системы автоматического программирования включают верификацию выходной программы в качестве некоторой дополнительной возможности. Важным вкладом в автоматическое программирование явилось заимствованное из робототехники представления об отладке программ как стратегии решения проблем. Установлено, что часто более эффективным оказывается создание недорогого, полного ошибок решения задачи написания программы, с последующей его модификацией, а не поиск с самого начала идеального, лишенного дефектов решения. Комбинаторные задачи и составление расписаний. Многие задачи из этой области исследуются методами ИИ. Классическим примером является задача коммивояжера, в которой требуется найти маршрут минимальной длины в пределах нескольких городов, начиная от некоторого исходного города, посещая каждый город один раз и возвращаясь в исходный город. Такой же характер носят многие головоломки. Например, задача о восьми ферзях, которая состоит в том, что восемь ферзей надо разместить на обычной шахматной доске так, чтобы ни один из них не атаковал другого. Иными словами, на каждой вертикали, горизонтали и диагонали должно быть не более одного ферзя. В задачах такого типа область возможных комбинаций или последовательностей, из которых необходимо выбрать ответ, чрезвычайно велика. Простые попытки решения таких задач вскоре порождает комбинаторный взрыв вариантов, которые быстро исчерпывают возможности обычных компьютеров. Некоторые из этих задач (включая задачу коммивояжера) относятся теоретиками к NP-полным. Так, в задаче коммивояжера характеристикой объема задачи является число городов. Степень возрастания комбинаций в задачах может быть линейной, полиномиальной и экспоненциальной. Так вот, время решения NP-полных задач растет экспоненциально с увеличением объема задачи. Пока еще не установлено, существует ли более быстрый, чем экспоненциальный метод решения NP-полных задач, но установлено, что если он существует хотя бы для одной NP-полной задачи, то аналогичные методы можно найти и для других NP-полных задач. Таким образом, усилия специалистов по ИИ, работающих над решением комбинаторных задач, сводятся пока к борьбе с экспоненциальным ростом времени решения, хотя бы даже в пределах его экспоненциального характера. Интересные результаты в решении NP-полных задач достигнуты с помощью полносвязных нейронных сетей Хопфилда. Проблемы машинного восприятия. Попытки снабдить вычислительные машины органами восприятия показали, что для полезной (интеллектуальной) обработки столь сложных входных данных необходимо “понимание”. В свою очередь для такого понимания необходима огромная база знаний об окружающей среде. Смысл процесса машинного восприятия состоит в создании сжатого представления о реальных входных сценах и образах, с которыми машина не в состоянии работать из-за громадного объема описывающей их информации. Характер и качество окончательного представления зависит от целей воспринимающей системы: (что является важным: цвета, пространственные соотношения и размеры, наличие определенных признаков и т.д.). Основная трудность при восприятии сцен - невообразимое число возможных ее описаний. Одна из возможных плодотворных стратегий в этих условиях состоит в построении гипотез на различных уровнях описания и последующей их проверки с помощью набора детекторов. В свою очередь, процесс формирования гипотез нуждается в большом объеме знаний о сценах, которые ожидается увидеть. В настоящее время зрительное машинное восприятие традиционно включает в себя следующие направления: проблемы анализа трехмерных сцен; разработку методов представления информации о зрительных образах в базе знаний; создание методов перехода от зрительных сцен к их текстовому описанию и обратного перехода; разработку процедур когнитивной графики создание средств для порождения зрительных сцен на основе внутренних представлений систем ИИ. Еще более сложной является проблема восприятия звуков. В контексте систем ИИ речь идет о восприятии речи. Причем под машинным восприятием речи понимается далеко не тривиальная задача идентификации лексических компонент речи и ее последующего семантического анализа. В конечном итоге решение проблемы позволит общаться с машиной на ЕЯ. Открывающиеся при этом возможности трудно переоценить. Представленный перечень приложений ИИ является далеко не полным и имеет тенденцию быстро расширяться. Задачи интеллектуальных информационных систем (теоретический аспект) 1. Представление знаний 2. Манипулирование знаниями 3. Общение 4. Восприятие 5. Обучение Такой подход можно также интерпретировать как определенный набор способностей некой целостной, интегральной, интеллектуальной системы (ИС). Понятно, что указанный набор способностей ИС следует рассматривать лишь как гипотетический. В различных практических областях применения систем ИИ может потребоваться только часть из этого перечня. Примером необходимости наличия, у искусственной ИС большинства из перечисленных способностей являются интегральные роботы, предназначенные для выполнения широкого (полностью не определенного) круга задач в естественной внешней среде. Причем в качестве ИС может рассматриваться не один робот, а коллектив подобных роботов. Такие работы сейчас весьма интенсивно ведутся (роботы-исследователи, микро-роботы и др.). Остановимся кратко на каждом из перечисленных понятий. 1. Представление знаний. В рамках этого направления решаются задачи, связанные с формализацией и представлением знаний в памяти интеллектуальной системы (ИС). Для этого разрабатываются специальные модели представления знаний и языки для описания знаний, выделяются различные типы знаний. Изучаются источники, из которых ИС могут черпать знания, создаются процедуры и приемы, с помощью которых возможно приобретение знаний для ИС. Проблема представления знаний для ИС чрезвычайно актуальна, т.к. ИС - это система, функционирование которой опирается на знания о проблемной области. 2. Манипулирование знаниями. Для того чтобы знаниями можно было пользоваться при решении задач, надо научить ИС оперировать ими. В рамках данного направления строятся способы пополнения знаний на основе их неполных описаний, изучаются системы классификации хранящихся в ИС знаний, разрабатываются процедуры обобщения знаний и формирования на их основе абстрактных понятий, создаются методы достоверного и правдоподобного вывода на основе имеющихся знаний, предлагаются модели рассуждений, опирающихся на знания и имитирующих способности человеческих рассуждений. Манипулирование знаниями тесно связано с представлением знаний. Многие исследователи считают, что эти направления можно разделить только условно. Создающаяся в настоящее время теория баз знаний включает оба этих направления. 3. Общение. В круг задач этого направления входят: проблема понимания связных текстов на ограниченном и неограниченном ЕЯ, синтез связных текстов, понимание речи и синтез речи, теория моделей коммуникации между человеком и ИС. К этому же кругу проблем примыкают задачи формирования объяснений действий ИС, которые она должна уметь порождать по просьбе человека; комплекс задач, связанных с интеграцией в единый внутренний образ сообщений различной модальности (текстовых, речевых, зрительных и т.п.), полученных в процессе коммуникации. На основе исследований в этом направлении формируются методы построения лингвистических процессоров, вопросно-ответных систем, диалоговых систем и других ИС, целью которых является обеспечение комфортных условий для общения человека с ИС. 4. Восприятие. Об этом направлении уже упоминалось в контексте прикладных областей. Как видите, в ИИ тесно переплетены и теоретические прикладные направления. 5. Обучение. Предполагается, что ИС подобно человеку будут способны к обучению - решению задач, с которыми они ранее не встречались. Для того, чтобы это стало возможным, необходимо: создать методы формирования условий задачи по описанию проблемной ситуации или по наблюдению за этой ситуацией, научиться переходу от известного решения частных задач (примеров) к решению общей задачи, создать приемы декомпозиции исходной для ИС задачи на более мелкие так, чтобы они оказались для ИС уже известными, разработать нормативные и декларативные модели самого процесса обучения, создать теорию подражательного поведения. И перечень таких задач можно еще продолжать. 6. Поведение. ИС должны действовать в некоторой окружающей среде. Поэтому возникает задача разработки специальных поведенческих процедур, которые позволили бы ИС адекватно взаимодействовать с окружающей средой, другими ИС (коллективы роботов) и людьми. Для достижения такого взаимодействия необходимо провести исследование в ряде направлений и создать: модели целесообразного поведения, нормативного поведения, ситуационного поведения, специальные методы многоуровневого планирования и коррекции планов в динамических ситуациях. Лишь после этого можно будет говорить о возможности привычного взаимодействия между людьми и ИС. Лекция 4. Экспертные системы: Определения и классификация Одним из наиболее значительных достижений искусственного интеллекта стала разработка мощных компьютерных систем, получивших название «экспертных» или основанных на «знаниях» систем. В современном обществе при решении задач управления сложными многопараметрическими и сильносвязанными системами, объектами, производственными и технологическими процессами приходится сталкиваться с решением неформализуемых либо трудноформализуемых задач. Такие задачи часто возникают в следующих областях: авиация, космос и оборона, нефтеперерабатывающая промышленность и транспортировка нефтепродуктов, химия, энергетика, металлургия, целлюлозно-бумажная промышленность, телекоммуникации и связь, пищевая промышленность, машиностроение, производство цемента, бетона и т.п., транспорт, медицина и фармацевтическое производство, административное управление, прогнозирование и мониторинг. Наиболее значительными достижениями в этой области стало создание систем, которые ставят диагноз, предсказывают месторождения полезных ископаемых, помогают в проектировании электронных устройств, машин и механизмов, решают задачи управления реакторами и другие задачи. Под экспертной системой (ЭС) будем понимать информационную систему, которая использует знания специалистов (экспертов) о некоторой конкретной узкоспециализированной предметной области и в пределах этой области способна принимать решения на уровне эксперта-профессионала. Осознание полезности систем, которые могут копировать дорогостоящие или редко встречающиеся человеческие знания, привело к широкому внедрению и расцвету этой технологии в 80-е, 90-е годы прошлого века. Основу успеха ЭС составили два важных свойства, отмечаемые рядом исследователей: • в ЭС знания отделены от данных, и мощность экспертной системы обусловлена в первую очередь мощностью базы знаний и только во вторую очередь используемыми методами решения задач; • решаемые ЭС задачи являются неформализованными или слабоформализованными и используют эвристические, экспериментальные, субъективные знания экспертов в определенной предметной области. Основными категориями решаемых ЭС задач являются: диагностика, управление (в том числе технологическими процессами), интерпретация, прогнозирование, проектирование, отладка и ремонт, планирование, наблюдение (мониторинг), обучение. Обобщенная схема ЭС Обобщенная схема ЭС приведена рисунке 4.1. Основу ЭС составляет подсистема логического вывода, которая использует информацию из базы знаний (БЗ), генерирует рекомендации по решению искомой задачи. Чаще всего для представления знаний в ЭС используются системы продукций и семантические сети. Допустим, БЗ состоит из фактов и правил (если <посылка> то <заключение>). Если ЭС определяет, что посылка верна, то правило признается подходящим для данной консультации и оно запускается в действие. Запуск правила означает принятие заключения данного правила в качестве составной части процесса консультации. Обязательными частями любой ЭС являются также модуль приобретения знаний и модуль отображения и объяснения решений. В большинстве случаев, реальные ЭС в промышленной эксплуатации работают также на основе баз данных (БД). Только одновременная работа со знаниями и большими объемами информации из БД позволяет ЭС получить неординарные результаты, например, поставить сложный диагноз (медицинский или технический), открыть месторождение полезных ископаемых, управлять ядерным реактором в реальном времени. Типичная статическая ЭС состоит из следующих основных компонентов: • решателя (подсистема логического вывода); • рабочей памяти (РП), называемой также базой данных (БД); • базы знаний (БЗ); • компонентов приобретения знаний; • объяснительного компонента (подсистема объяснения решений); • диалогового компонента (интерфейс пользователя). Рис. 4.1.  Структура экспертной системы 1) База данных (рабочая память) предназначена для хранения исходных и промежуточных данных решаемой в текущий момент задачи. Этот термин совпадает по названию, но не по смыслу с термином, используемым в информационно-поисковых системах (ИПС) и системах управления базами данных (СУБД) для обозначения всех данных (в первую очередь долгосрочных), хранимых в системе. 2) База знаний (БЗ) – ядро ЭС, совокупность знаний о предметной области, записанная на машинный носитель в форме, понятной эксперту и пользователю (обычно на некотором языке, приближенном к естественному). Параллельно такому «человеческому» представлению существует БЗ во внутреннем «машинном» представлении. 3) Решатель (подсистема логического вывода) – программа, моделирующая ход рассуждений эксперта на основании знаний, имеющихся в БЗ. Синонимы: дедуктивная машина, машина вывода, блок логического вывода. Это программная компонента экспертных систем, реализующая процесс ее рассуждений на основе базы знаний и рабочего множества. Она выполняет две функции: во-первых, просмотр существующих фактов из рабочего множества и правил из базы знаний и добавление (по мере возможности) в рабочее множество новых фактов и, во-вторых, определение порядка просмотра и применения правил. Эта подсистема управляет процессом консультации, сохраняет для пользователя информацию о полученных заключениях, и запрашивает у него информацию, когда для срабатывания очередного правила в рабочем множестве оказывается недостаточно данных. Цель ЭС – вывести некоторый заданный факт, который называется целевым утверждением (то есть в результате применения правил добиться того, чтобы этот факт был включен в рабочее множество), либо опровергнуть этот факт (то есть убедиться, что его вывести невозможно, следовательно, при данном уровне знаний системы он является ложным). Целевое утверждение может быть либо «заложено» заранее в базу знаний системы, либо извлекается системой из диалога с пользователем. Работа системы представляет собой последовательность шагов, на каждом из которых из базы выбирается некоторое правило, которое применяется к текущему содержимому рабочего множества. Цикл заканчивается, когда выведено либо опровергнуто целевое утверждение. Цикл работы экспертной системы иначе называется логическим выводом. Логический вывод может происходить многими способами, из которых наиболее распространенные – прямой порядок вывода и обратный порядок вывода. Прямой порядок вывода – от фактов, которые находятся в рабочем множестве, к заключению. Если такое заключение удается найти, то оно заносится в рабочее множество. Прямой вывод часто называют выводом, управляемым данными. Обратный порядок вывода – заключения просматриваются до тех пор, пока не будет обнаружены в рабочей памяти или получены от пользователя факты, подтверждающие одно из них. В системах с обратным выводом вначале выдвигается некоторая гипотеза, а затем механизм вывода в процессе работы как бы возвращается назад, переходя от нее к фактам, и пытается найти среди них те, которые подтверждают эту гипотезу. Если она оказалась правильной, то выбирается следующая гипотеза, детализирующая первую, являющаяся по отношению к ней подцелью. Далее отыскиваются факты, подтверждающие истинность подчиненной гипотезы. Вывод такого типа называется управляемым целями. Обратный поиск применяется в тех случаях, когда цели известны и их сравнительно немного. 4) Подсистема объяснения решения – программа, позволяющая пользователю получить ответы на вопросы: «Как была получена та или иная рекомендация?» и «Почему система приняла такое решение?» Ответ на вопрос «как» – это трассировка всего процесса получения решения с указанием использованных фрагментов БЗ, то есть всех шагов цепи умозаключений. Ответ на вопрос «почему» – ссылка на умозаключение, непосредственно предшествовавшее полученному решению, то есть отход на один шаг назад. Развитые подсистемы объяснений поддерживают и другие типы вопросов. 5) Интеллектуальный редактор БЗ – программа, представляющая инженеру по знаниям возможность создавать БЗ в диалоговом режиме. Включает в себя систему вложенных меню, шаблонов языка представления знаний, подсказок («help» – режим) и других сервисных средств, облегчающих работу с базой. Компонент приобретения знаний автоматизирует процесс наполнения ЭС знаниями, осуществляемый экспертом. 6) Диалоговый компонент ориентирован на организацию дружественного общения с пользователем как в ходе решения задач, так и в процессе приобретения знаний и объяснения результатов работы. Поскольку системы, основанные на знаниях, реализуются на персональных компьютерах, то и входная информация должна восприниматься в виде, понятном компьютеру. Однако для того чтобы с ЭС мог взаимодействовать неподготовленный пользователь, в нее требуется включить средства общения на естественном языке. Подавляющее большинство систем, основанных на знаниях, обладают интерфейсом на естественном языке. Допустимые входные сообщения пользователя содержатся в базе знаний. Итак, на примере простой ЭС и базы знаний диалог пользователя с системой можно представить себе следующим образом: Система: Вы хотите узнать, нужно ли взять с собой зонтик? Пользователь: Да. Система: Верно ли, что небо покрыто тучами? Пользователь: Да. Система: Верно ли, что барометр падает? Пользователь: Да. Система: Нужно взять с собой зонтик. Как видно из этого примера, в ходе консультации инициатива диалога принадлежит системе, а сама консультация у ЭС выглядит так же, как и консультация у эксперта – человека, – задается ряд вопросов и на основании их анализа выдается экспертное заключение. Однако в отличие от беседы со специалистом, диалог с ЭС имеет свои психологические особенности: большинство пользователей (по вполне понятным причинам, таким, как отсутствие опыта работы на компьютерах, лаконичность диалога с ЭС, отсутствие пояснений в ходе консультации и другим) склонны меньше доверять “мнению” ЭС, чем мнению “живого” эксперта. Коллектив разработчиков ЭС Эксперт определяет знания (данные и правила), характеризующие проблемную область, обеспечивает полноту и правильность введенных в ЭС знаний. Инженер по знаниям помогает эксперту выявить и структурировать знания, необходимые для работы ЭС; осуществляет выбор той модели представления знаний, которая наиболее подходит для данной проблемной области, и определяет набор инструментальных средств; выделяет и программирует (традиционными средствами) стандартные функции (типичные для данной проблемной области), которые будут использоваться в правилах, вводимых экспертом. Фактически инженер по знаниям ИЗВЛЕКАЕТ знания из эксперта. Извлечение знаний – получение инженером по знаниям наиболее полного из возможных представлений о предметной области и способах принятия решения в ней. Необходимо отметить, что отсутствие среди участников разработки инженеров по знаниям (т.е. их замена программистами) либо приводит к неудаче процесс создания ЭС, либо значительно удлиняет его. Программист разрабатывает интеллектуальную систему, содержащую в пределе все основные компоненты ЭС, и осуществляет ее сопряжение с той средой, в которой она будет использована. Важную роль при создании ЭС играют инструментальные средства. Среди инструментальных средств для создания ЭС наиболее популярны такие языки программирования, как LISP и PROLOG, а также экспертные системы-оболочки (ЭСО): KEE, CENTAUR, G2 и GDA, CLIPS, АТ_ТЕХНОЛОГИЯ, предоставляющие в распоряжение разработчика-инженера по знаниям широкий набор для комбинирования систем представления знаний, языков программирования, объектов и процедур. Режимы работы ЭС Экспертная система работает в двух режимах: режиме приобретения знаний и в режиме решения задачи (называемом также режимом консультации или режимом использования ЭС). В режиме приобретения знаний общение с ЭС осуществляет (через посредничество инженера по знаниям) эксперт. В этом режиме эксперт, используя компонент приобретения знаний, наполняет систему знаниями, которые позволяют ЭС в режиме решения самостоятельно (без эксперта) решать задачи из проблемной области. Эксперт описывает проблемную область в виде совокупности данных и правил. Данные определяют объекты, их характеристики и значения, существующие в области экспертизы. Правила определяют способы манипулирования с данными, характерные для рассматриваемой области. Отметим, что режиму приобретения знаний в традиционном подходе к разработке программ соответствуют этапы алгоритмизации, программирования и отладки, выполняемые программистом. Таким образом, в отличие от традиционного подхода в случае ЭС разработку программ осуществляет не программист, а эксперт (с помощью ЭС), не владеющий программированием. В режиме консультации общение с ЭС осуществляет конечный пользователь, которого интересует результат и (или) способ его получения. Необходимо отметить, что в зависимости от назначения ЭС пользователь может не быть специалистом в данной проблемной области (в этом случае он обращается к ЭС за результатом, не умея получить его сам), или быть специалистом (в этом случае пользователь может сам получить результат, но он обращается к ЭС с целью либо ускорить процесс получения результата, либо возложить на ЭС рутинную работу). Следует подчеркнуть, что термин «пользователь» является многозначным, так как использовать ЭС кроме конечного пользователя может и эксперт, и инженер по знаниям, и программист. Поэтому, когда хотят подчеркнуть, что речь идет о том, для кого делалась ЭС, используют термин «конечный пользователь». Классификация ЭС. Рис.4.2 Классификация ЭС Рассмотрим различные способы классификации ЭС. Классификация по решаемой задаче: Интерпретация данных – это одна из традиционных задач для ЭС, процесс определения смысла данных, результаты которого должны быть согласованными и корректными. Предусматривается многовариантный анализ данных. (Обнаружение и идентификация различных типов океанских судов по результатам аэрокосмического сканирования, определение свойств личности по результатам тестирования АВАНТЕСТ, МИКРОЛЮШЕР); Диагностика – процесс соотнесения объекта с некоторым классом объектов и обнаружение отклонения от нормы. Диагностика и терапия сужения коронарных сосудов, диагностика ошибок в аппаратуре и математическом обеспечении ЭВМ; Мониторинг. Основная задача мониторинга – непрерывная интерпретация данных в реальном масштабе времени и сигнализация о выходе тех или иных параметров за допустимые пределы. Контроль за работой электростанций СПРИНТ, помощь диспетчерам атомного реактора, контроль аварийных датчиков на химическом заводе – FALCON. Проектирование – подготовка спецификаций на создание «объектов» с заранее определенными свойствами. Под спецификацией понимается полный набор документов. В задачах проектирования тесно связаны два основных процесса ЭС: процесс вывода решения и процесс объяснения. Проектирование конфигураций ЭВМ, синтез электрических цепей. Прогнозирование – позволяет предсказывать события на основании имеющихся данных, логически выводить вероятные следствия из данных ситуаций. Предсказание погоды – WILLARD; оценки будущего урожая – PLANT; прогнозы в экономике - ECON. Планирование – нахождение планов действий объектов, способных выполнять некоторые функции. Для выведения логических последствий планируемой деятельности используются модели поведения реальных объектов. Планирование поведения робота – STRIPS, планирование промышленных заказов – ISIS, эксперимента – MOLGEN. Обучение – системы обучения с помощью компьютера диагностируют ошибки и подсказывают правильные решения. Они аккумулируют знания о гипотетическом ученике, о его характерных ошибках и способны диагностировать слабости в познаниях обучаемых и находить средства их ликвидации. Управление – функция организованной системы, поддерживающая определенный режим деятельности. Такого рода ЭС осуществляют управление поведением сложных систем в соответствии с заданными спецификациями. Управление газовой котельной GAS, управление системой календарного планирования Project Assistant. Поддержка принятия решений – это совокупность процедур, обеспечивающая лицо, принимающее решение, необходимой информацией и рекомендациями. Выбор стратегии выхода фирмы из кризисной ситуации Crisis, выбор страховой компании Choice. В общем случае все системы, основанные на знаниях, можно подразделить на системы, решающие задачи анализа, и на системы, решающие задачи синтеза. Задачи анализа: интерпретация данных, диагностика, поддержка принятия решения. Задачи синтеза: проектирование, планирование, управление. Комбинированные задачи: обучение, мониторинг, прогнозирование. Классификация по связи с реальным временем: Статические ЭС разрабатываются в предметных областях, в которых база знаний и интерпретируемые данные не меняются во времени. Они стабильны. (Диагностика автомобиля). Квазидинамические ЭС интерпретируют ситуацию, которая меняется с некоторым фиксированным интервалом во времени. Динамические ЭС работают в сопряжении с датчиками объектов в режиме реального времени и непрерывной интерпретацией поступающих в систему данных. (Управление гибкими производственными комплексами, мониторинг в реанимационных палатах). Классификация по степени интеграции с другими программами: Автономные ЭС работают непосредственно в режиме консультаций с пользователем для специфических «экспертных» задач; Гибридные ЭС представляют программный комплекс, агрегирующий стандартные пакеты прикладных программ (мат. статистику, линейное программирование, СУБД) и средства манипулирования знаниями. Следует отметить, что разработка гибридных систем являет собой задачу на порядок более сложную, чем разработка автономной ЭС. Стыковка не просто разных пакетов, а разных методологий порождает целый комплекс теоретических и практических трудностей. Классификация по сложности решаемых задач различают: 1. Простые ЭС - до 1000 простых правил. 2. Средние ЭС - от 1000 до 10000 структурированных правил. 3. Сложные ЭС - более 10000 структурированных правил. Классификация по стадии создания: 1. Исследовательский образец ЭС, разработанный за 1-2 месяца с минимальной БЗ. 2. Демонстрационный образец ЭС, разработанный за 2-4 месяца, например, на языке типа LISP, PROLOG, CLIPS. 3. Промышленный образец ЭС, разработанный за 4-8 месяцев, например, на языке типа CLIPS с полной БЗ. 4. Коммерческий образец ЭС, разработанный за 1,5-2 года, например, на языке типа С++, Java с полной БЗ. Трудности при разработке экспертных систем Разработка ЭС связана с определенными трудностями, которые необходимо хорошо знать, так же как и способы их преодоления. Рассмотрим подробнее эти проблемы. • Проблема извлечения знаний из экспертов. Ни один специалист никогда просто так не раскроет секреты своего профессионального мастерства, свои сокровенные знания в профессиональной области. Он должен быть заинтересован материально или морально, причем хорошо заинтересован. Никто не хочет рубить сук, на котором сидит. Часто такой специалист опасается, что, раскрыв все свои секреты, он будет не нужен компании. Вместо него будет работать экспертная система. Избежать этой проблемы поможет выбор высококвалифицированного эксперта, заинтересованного в сотрудничестве. • Проблема формализации знаний экспертов. Эксперты-специалисты в определенной области, как правило, не в состоянии формализовать свои знания. Часто они принимают правильные решения на интуитивном уровне и не могут аргументировано объяснить, почему принято то или иное решение. Иногда эксперты не могут прийти к взаимопониманию (фраза «встретились два геолога, у них было три мнения» - не шутка, а реальная жизнь). В таких ситуациях поможет выбор эксперта, умеющего ясно формулировать свои мысли и легко объяснять другим свои идеи. • Проблема нехватки времени у эксперта. Выбранный для разработки эксперт не может найти достаточно времени для выполнения проекта. Он слишком занят. Он всем нужен. У него есть проблемы. Чтобы избежать этой ситуации, необходимо получить от эксперта, прежде чем начнется проект, согласие тратить на проект время в определенном фиксированном объеме. • Правила, формализованные экспертом, не дают необходимой точности. Проблему можно избежать, если решать вместе с экспертом реальные задачи. Не надо придумывать «игрушечных» ситуаций или задач. В условиях задач нужно использовать реальные данные, такие как лабораторные данные, отчеты, дневники и другую информацию, взятую из практических задач. Постарайтесь говорить с экспертом на одном языке, используя единую терминологию. Эксперт, как правило, легче понимает правила, записанные на языке, близком к естественному, а не на языке типа LISP или PROLOG. • Недостаток ресурсов. В качестве ресурсов выступают персонал (инженеры знаний, разработчики инструментальных средств, эксперты) и средства построения ЭС (средства разработки и средства поддержки). Недостаток благожелательных и грамотных администраторов порождает скептицизм и нетерпение у руководителей. Повышенное внимание в прессе и преувеличения вызвали нереалистические ожидания, которые приводят к разочарованию в отношении экспертных систем. ЭС могут давать не самые лучшие решения на границе их применимости, при работе с противоречивыми знаниями и в рассуждениях на основе здравого смысла. Могут потребоваться значительные усилия, чтобы добиться небольшого увеличения качества работы ЭС. Экспертные системы требуют много времени на разработку. Так, создание системы PUFF для интерпретации функциональных тестов легких потребовало 5 человеко-лет, на разработку системы PROCPECTOR для разведки рудных месторождений ушло 30 человеко-лет, система XCON для расчета конфигурации компьютерных систем на основе VAX 11/780 потребовала 8 человеко-лет. ЭС последних лет разрабатываются более быстрыми темпами за счет развития технологий ЭС, но проблемы остались. Удвоение персонала не сокращает время разработки наполовину, потому что процесс создания ЭС - это процесс со множеством обратных связей. Все это необходимо учитывать при планировании создания ЭС. • Неадекватность инструментальных средств решаемой задаче. Часто определенные типы знаний (например, временные или пространственные) не могут быть легко представлены на одном ЯПЗ, так же как и разные схемы представления (например, фреймы и продукции) не могут быть достаточно эффективно реализованы на одном ЯПЗ. Некоторые задачи могут быть непригодными для решения по технологии ЭС (например, отдельные задачи анализа сцен). Необходим тщательный анализ решаемых задач, чтобы определить пригодность предлагаемых инструментальных средств и сделать правильный выбор. Примеры экспертных систем Для начала совершим краткий экскурс в историю создания ранних и наиболее известных ЭС. В большинстве этих ЭС в качестве модели представления знаний использовались системы продукций (правила) и прямая цепочка рассуждений. Медицинская ЭС MYCIN разработана в Стэнфордском университете в середине 70-х годов для диагностики и лечения инфекционных заболеваний крови. MYCIN в настоящее время используется для обучения врачей. ЭС DENDRAL разработана в Стэнфордском университете в середине 60-х годов для определения топологических структур органических молекул. Система выводит молекулярную структуру химических веществ по данным масс-спектрометрии и ядерного магнитного резонанса. ЭС PROSPECTOR разработана в Стэнфордском университете в 1974-1983 годах для оценки геологами потенциальной рудоносности района. Система содержит более 1000 правил и реализована на INTERLISP. Программа сравнивает наблюдения геологов с моделями разного рода залежей руд. Программа вовлекает геолога в диалог для извлечения дополнительной информации. В 1984 году она точно предсказала существование молибденового месторождения, оцененного в многомиллионную сумму. Среди современных коммерческих систем хочется выделить экспертную систему - оболочку G2 американской фирмы Gensym (USA) как реализованную на достаточно высоком уровне экспертную коммерческую систему для работы с динамическими объектами. Работа в реальном времени с малыми временами ответа часто необходима при анализе ситуаций в корпоративных информационных сетях, на атомных реакторах, в космических полетах и множестве других задач. В этих задачах необходимо принимать решения в течение миллисекунд с момента возникновения критической ситуации. ЭС G2, предназначенная для решения таких задач, отличается от большинства динамических ЭС такими характерными свойствами, как: 1. работа в реальном времени с распараллеливанием процессов рассуждений; 2. структурированный естественно-языковый интерфейс с управлением по меню и автоматической проверкой синтаксиса; 3. обратный и прямой вывод, использование метазнаний, сканирование и фокусирование; 4. интеграция подсистемы моделирования с динамическими моделями для различных классов объектов; 5. структурирование БЗ, наследование свойств, понимание связей между объектами; 6. библиотеки знаний являются ASCII-файлами и легко переносятся на любые платформы и типы ЭВМ; 7. развитый редактор для сопровождения БЗ без программирования, средства трассировки и отладки БЗ; 8. управление доступом с помощью механизмов авторизации пользователя и обеспечения желаемого взгляда на приложение; 9. гибкий интерфейс оператора, включающий графики, диаграммы, кнопки, пиктограммы и т.п.; 10. интеграция с другими приложениями (по TCP/IP) и базами данных, возможность удаленной и многопользовательской работы. Лекция 5. Деревья решений. Общие принципы работы Стремительное развитие информационных технологий, в частности, прогресс в методах сбора, хранения и обработки данных позволил многим организациям собирать огромные массивы данных, которые необходимо анализировать. Объемы этих данных настолько велики, что возможностей экспертов уже не хватает, что породило спрос на методы автоматического исследования (анализа) данных, который с каждым годом постоянно увеличивается. Деревья решений – один из таких методов автоматического анализа данных. Первые идеи создания деревьев решений восходят к работам Ховленда (Hoveland) и Ханта(Hunt) конца 50-х годов XX века. Однако, основополагающей работой, давшей импульс для развития этого направления, явилась книга Ханта (Hunt, E.B.), Мэрина (Marin J.) и Стоуна (Stone, P.J) «Experiments in Induction», увидевшая свет в 1966г. Терминология Введем основные понятия из теории деревьев решений, которые будут употребляться в этой лекции. Название Описание Объект Пример, шаблон, наблюдение Атрибут Признак, независимая переменная, свойство Метка класса Зависимая переменная, целевая переменная, признак определяющий класс объекта Узел Внутренний узел дерева, узел проверки Лист Конечный узел дерева, узел решения Проверка (test) Условие в узле Что такое дерево решений и типы решаемых задач Деревья решений – это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. Под правилом понимается логическая конструкция, представленная в виде «если … то …» Область применения деревья решений в настоящее время широка, но все задачи, решаемые этим аппаратом, могут быть объединены в следующие три класса: • Описание данных: Деревья решений позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов. • Классификация: Деревья решений отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения. • Регрессия: Если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от независимых (входных) переменных. Например, к этому классу относятся задачи численного прогнозирования (предсказания значений целевой переменной). Как построить дерево решений? Пусть задано некоторое обучающее множество T, содержащее объекты (примеры), каждый из которых характеризуется m атрибутами, причем один из них указывает на принадлежность объекта к определенному классу. Идею построения деревьев решений из множества T, впервые высказанную Хантом, приведем по Р. Куинлену (R. Quinlan). Пусть через {C1, C2, … Ck} обозначены классы (значения метки класса), тогда существуют 3 ситуации: 1. множество T содержит один или более примеров, относящихся к одному классу Ck. Тогда дерево решений для Т – это лист, определяющий класс Ck; 2. множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем; 3. множество T содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O1, O2, … On. T разбивается на подмножества T1, T2, … Tn, где каждое подмножество Ti содержит все примеры, имеющие значение Oi для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу. Вышеописанная процедура лежит в основе многих современных алгоритмов построения деревьев решений, этот метод известен еще под названием разделения и захвата (divide and conquer). Очевидно, что при использовании данной методики, построение дерева решений будет происходит сверху вниз. Поскольку все объекты были заранее отнесены к известным нам классам, такой процесс построения дерева решений называется обучением с учителем (supervised learning). Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction). На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, NewId, ITrule, CHAID, CN2 и т.д. Но наибольшее распространение и популярность получили следующие два: • CART (Classification and Regression Tree) – это алгоритм построения бинарного дерева решений – дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии. • C4.5 – алгоритм построения дерева решений, количество потомков у узла не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации. Большинство из известных алгоритмов являются «жадными алгоритмами». Если один раз был выбран атрибут, и по нему было произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. И поэтому на этапе построения нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение. Этапы построения деревьев решений При построении деревьев решений особое внимание уделяется следующим вопросам: выбору критерия атрибута, по которому пойдет разбиение, остановки обучения и отсечения ветвей. Рассмотрим все эти вопросы по порядку. Правило разбиения. Каким образом следует выбрать признак? Для построения дерева на каждом внутреннем узле необходимо найти такое условие (проверку), которое бы разбивало множество, ассоциированное с этим узлом на подмножества. В качестве такой проверки должен быть выбран один из атрибутов. Общее правило для выбора атрибута можно сформулировать следующим образом: выбранный атрибут должен разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. количество объектов из других классов («примесей») в каждом из этих множеств было как можно меньше. Были разработаны различные критерии, но рассмотрим только два из них: 1) Теоретико-информационный критерий Алгоритм C4.5, усовершенствованная версия алгоритма ID3 (Iterative Dichotomizer), использует теоретико-информационный подход. Для выбора наиболее подходящего атрибута, предлагается следующий критерий: (5.1) где, Info(T) – энтропия множества T  – количество примеров из некоторого множества S, относящихся к одному и тому же классу Cj. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу Cj Согласно теории информации количество содержащейся в сообщении информации зависит от ее вероятности Поскольку используется логарифм с двоичным основанием, то выражение дает количественную оценку в битах. (5.2) Выбирается один из атрибутов Х. По нему проводится разбиение текущей обучающей выборки Т на подмножества T1, T2, ... Tn. Для каждого из них вычисляется , а затем определяется следующий показатель (апостериорная энтропия): (5.3) Такая мера вычисляется для каждого атрибута. Выбирается атрибут, дающий максимальное значение по критерию (1). Впервые эта мера была предложена Р. Куинленом в разработанном им алгоритме ID3. Кроме вышеупомянутого алгоритма C4.5, есть еще целый класс алгоритмов, которые используют этот критерий выбора атрибута. 2) Статистический критерий Алгоритм CART использует так называемый индекс Gini (в честь итальянского экономиста Corrado Gini), который оценивает "расстояние" между распределениями классов. (5.4) Где c – текущий узел, а pj – вероятность класса j в узле c. CART был предложен Л.Брейманом (L.Breiman) и др. Правило остановки. Разбивать дальше узел или отметить его как лист? В дополнение к основному методу построения деревьев решений были предложены следующие правила: • Использование статистических методов для оценки целесообразности дальнейшего разбиения, так называемая «ранняя остановка» (prepruning). В конечном счете «ранняя остановка» процесса построения привлекательна в плане экономии времени обучения, но здесь уместно сделать одно важное предостережение: этот подход строит менее точные классификационные модели и поэтому ранняя остановка крайне нежелательна. Признанные авторитеты в этой области Л.Брейман и Р. Куинлен советуют буквально следующее: «Вместо остановки используйте отсечение». • Ограничить глубину дерева. Остановить дальнейшее построение, если разбиение ведет к дереву с глубиной превышающей заданное значение. • Разбиение должно быть нетривиальным, т.е. получившиеся в результате узлы должны содержать не менее заданного количества примеров. Этот список эвристических правил можно продолжить, но на сегодняшний день не существует такого, которое бы имело большую практическую ценность. К этому вопросу следует подходить осторожно, так как многие из них применимы в каких-то частных случаях. Правило отсечения. Каким образом ветви дерева должны отсекаться? Очень часто алгоритмы построения деревьев решений дают сложные деревья, которые «переполнены данными», имеют много узлов и ветвей. Такие «ветвистые» деревья очень трудно понять. К тому же ветвистое дерево, имеющее много узлов, разбивает обучающее множество на все большее количество подмножеств, состоящих из все меньшего количества объектов. Ценность правила, справедливого скажем для 2-3 объектов, крайне низка, и в целях анализа данных такое правило практически непригодно. Гораздо предпочтительнее иметь дерево, состоящее из малого количества узлов, которым бы соответствовало большое количество объектов из обучающей выборки. И тут возникает вопрос: а не построить ли все возможные варианты деревьев, соответствующие обучающему множеству, и из них выбрать дерево с наименьшей глубиной? К сожалению, это задача является NP-полной, это было показано Л. Хайфилем (L. Hyafill) и Р. Ривестом (R. Rivest), и, как известно, этот класс задач не имеет эффективных методов решения. Для решения вышеописанной проблемы часто применяется так называемое отсечение ветвей (pruning). Пусть под точностью (распознавания) дерева решений понимается отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества, а под ошибкой – количество неправильно классифицированных. Предположим, что нам известен способ оценки ошибки дерева, ветвей и листьев. Тогда, возможно использовать следующее простое правило: • построить дерево; • отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки. В отличии от процесса построения, отсечение ветвей происходит снизу вверх, двигаясь с листьев дерева, отмечая узлы как листья, либо заменяя их поддеревом. Хотя отсечение не является панацеей, но в большинстве практических задач дает хорошие результаты, что позволяет говорить о правомерности использования подобной методики. Правила Иногда даже усеченные деревья могут быть все еще сложны для восприятия. В таком случае, можно прибегнуть к методике извлечения правил из дерева с последующим созданием наборов правил, описывающих классы. Для извлечения правил необходимо исследовать все пути от корня до каждого листа дерева. Каждый такой путь даст правило, где условиями будут являться проверки из узлов встретившихся на пути. Преимущества использования деревьев решений Рассмотрев основные проблемы, возникающие при построении деревьев, было бы несправедливо не упомянуть об их достоинствах: • быстрый процесс обучения; • генерация правил в областях, где эксперту трудно формализовать свои знания; • извлечение правил на естественном языке; • интуитивно понятная классификационная модель; • высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети); • построение непараметрических моделей. В силу этих и многих других причин, методология деревьев решений является важным инструментом в работе каждого специалиста, занимающегося анализом данных, вне зависимости от того практик он или теоретик. Области применения деревьев решений Деревья решений являются прекрасным инструментом в системах поддержки принятия решений, интеллектуального анализа данных (data mining). В состав многих пакетов, предназначенных для интеллектуального анализа данных, уже включены методы построения деревьев решений. В областях, где высока цена ошибки, они послужат отличным подспорьем аналитика или руководителя Деревья решений успешно применяются для решения практических задач в следующих областях: • Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов. • Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т.д. • Медицина. Диагностика различных заболеваний. • Молекулярная биология. Анализ строения аминокислот. Это далеко не полный список областей где можно использовать деревья решений. Не исследованы еще многие потенциальные области применения. Лекция 6. Нечеткая логика Человек мыслит нечеткими понятиями: погода хорошая, скорость низкая, настроение хорошее. Очевидно, что каждый может вкладывать в эти понятия совершенно разный смысл: что хорошо для одного, может быть совершенно неприемлемо для другого. Четкая логика (в рамка которой переменная может принимать всего два значения: истина и ложь, 0 и1) учет этого фактора совершенно невозможен. Поэтому в середине XX века Л.Заде была предпринята попытка создания математического аппарата, позволяющего учесть эту особенность мыслительной деятельности человека. Лингвистическая переменная (ЛП) – это переменная, значение которой определяется набором вербальных (то есть словесных) характеристик некоторого свойства. Например, ЛП «рост» определяется через набор {карликовый, низкий, средний, высокий, очень высокий}. Введя понятие лингвистической переменной и допустив, что в качестве ее значений (термов) выступают нечеткие множества, был предложен аппарат для описания процессов интеллектуальной деятельности, включая нечеткость и неопределенность выражений. Это позволило создать фундамент теории нечетких множеств и нечеткой логики, а также предпосылки для внедрения методов нечеткого управления в инженерную практику. Основы теории нечетких множеств Значения лингвистической переменной (ЛП) определяются через так называемые нечеткие множества (НМ), которые в свою очередь определены на некотором базовом наборе значений или базовой числовой шкале, имеющей размерность. Каждое значение ЛП определяется как нечеткое множество (например, НМ «низкий рост»). Нечеткое множество определяется через некоторую базовую шкалу В и функцию принадлежности НМ – µ(х), хВ, принимающую значения на интервале [0...1]. Таким образом, нечеткое множество В – это совокупность пар вида (х, µ(х)), где хВ. Часто встречается и такая запись: (6.1) где х – i-e значение базовой шкалы. Функция принадлежности определяет субъективную степень уверенности эксперта в том, что данное конкретное значение базовой шкалы соответствует определяемому НМ. Эту функцию не стоит путать с вероятностью, носящей объективный характер и подчиняющейся другим математическим зависимостям. Например, для двух экспертов определение НМ «высокая» для ЛП «цена автомобиля» в условных единицах может существенно отличаться в зависимости от их социального и финансового положения. «Высокая_цена_автомобиля_1» = {50000/1 + 25000/0.8 + 10000/0.6 + 5000/0.4}; «Высокая_цена_автомобиля_2» = {25000/1 + 10000/0.8 + 5000/0.7 + 3000/0.4}. Пример.6.1 Пусть перед нами стоит задача интерпретации значений ЛП «возраст», таких как «молодой» возраст, «преклонный» возраст или «переходный» возраст. Определим «возраст» как ЛП (рис.6.1.). Тогда «молодой», «преклонный», «переходный» будут значениями этой лингвистической переменной. Более полно базовый набор значений ЛП «возраст» следующий: В – {младенческий, детский, юный, молодой, зрелый, преклонный, старческий}. Для ЛП «возраст» базовая шкала – это числовая шкала от 0 до 120, обозначающая количество прожитых лет, а функция принадлежности определяет, насколько мы уверены в том, что данное количество лет можно отнести к данной категории возраста (от 0 до 1). На рис.6.2 отражено, как одни и те же значения базовой шкалы могут участвовать в определении различных НМ. Рис. 6.1. Лингвистическая переменная «возраст» и нечеткие множества, определяющие ее значения Например, определить значение НМ «младенческий возраст» можно так: Рис. 6.2. Формирование нечетких множеств Рис.6.3 иллюстрирует оценку НМ неким усредненным экспертом, который ребенка до полугода с высокой степенью уверенности относит к младенцам (m=1). Дети до четырех лет причисляются к младенцам тоже, но с меньшей степенью уверенности (0.50, т.е. носитель . Элементы хЕ, для которых µА(х) = 0.5, называются точками перехода множества А. Нечеткие числа – нечеткие переменные, определенные на числовой оси, т.е. нечеткое число определяется как нечеткое множество А на множестве действительных чисел R с функцией принадлежности , где . Нечеткое число А нормально, если , и выпуклое, если для любых выполняется Рис. 6.4. Функции принадлежности нечетких множеств: А1 – «малая толщина»; А2 – «средняя толщина»; А3 – «большая толщина» Нечеткие правила вывода Базовое правило вывода типа "если - то" (англ.: if- then rule) называется также нечеткой импликацией, принимающей форму если х это А, то у это В (6.1) где А и В - это лингвистические значения, идентифицированные нечетким способом через соответствующие функции принадлежности для переменных х и у. Часть "х это А" называется условием (предпосылкой), а "у это В" - следствием (заключением). Импликацию (6.1) можно записать в сокращенном виде А → В. Нечеткое рассуждение - это процедура, которая позволяет определить заключение, вытекающее из множества правил "если - то". Такое множество при N переменных х может принять вид если x1 это А1 и х2 это А2 и ... и xN это AN , тo у это В (6.2) Переменные x1, x2, …, xN образуют N-мерный входной вектор x, составля­ющий аргумент условия, в котором А1, А2 , ..., An и В обозначают величины соответствующего коэффициента принадлежности , . Необходимо обратить внимание, что здесь присутствуют индивидуальные функции принадлежности для каждой переменной хi , и отдельно для y. Случайное значение функции принадлежности , где х - это вектор х = [ x1, x2, …, xN ] отно­сящееся к условию импликации (уровень активации правила), должно в последующем интерпретироваться с использованием введенных ранее нечетких операций. Возможна интерпретация (то есть определение уровня активации (нечеткого значения) переменной, указанной в следствии правила) в форме логического произве­дения множеств либо в форме алгебраического произведения: 1. интерпретация в форме логического произведения (из всех нечетких значений переменных условия правила берется минимальное): (6.3) 2. интерпретация в форме алгебраического произведения (в качестве нечеткого значения переменной следствия правила берется значение, полученное путем перемножения нечетких значений переменных условия правила): (6.4) Приписывание единственного значения функции принадлежности, описы­вающей многомерное условие, будем называть агрегированием предпосылки. Каждой импликации А → В, определенной выражением (6.2), можно приписать также единственное значение функции принадлежности . Наиболее популярные интерпретации этой функции также имеют форму логического или алгебраического произведения: • форма логического произведения (6.5) • форма алгебраического произведения (6.6) Приписывание единственного значения функции принадлежности всей импликации будем называть процедурой агрегирования на уровне импликации. Нечеткий логический вывод Системы нечеткого вывода Мамдани-Заде Элементы теории нечетких множеств, правила импликации и нечетких рассуждений образуют систему нечеткого вывода. В ней можно выделить множество используемых в системе нечетких правил, базу данных, содер­жащую описания функций принадлежности, а также механизм вывода и агрегирования, который формируется применяемыми правилами импликации. Следует упомянуть, что в случае технической реализации в качестве вход­ных и выходных сигналов выступают измеряемые величины, однозначно сопоставляющие входным значениям соответствующие выходные зна­чения. Для обеспечения взаимодействия множеств этих двух видов вводится нечеткая система с так называемыми фазификатором (преобразо­вателем множества входных данных в нечеткое множество) на входе и дефазификатором (преобразователем нечетких множеств в конкретное значение выходной переменной) на выходе. Структура такой системы представлена на рис.6.5. Рис. 6.5. Структура нечеткой системы с фазификатором и дефазификатором Используемый в различного рода экспертных и управляющих системах механизм нечетких выводов в своей основе имеет базу знаний, формируемую специалистами предметной области в виде совокупности нечетких предикатных правил вида: П1: если х есть A1, то у есть В1 П2: если х есть А2, то у есть В2 …………………… Пn: если х есть Аn, то у есть Вn , где х – входная переменная (имя для известных значений данных); у – переменная вывода (имя для значения данных, которое будет вычислено); А и В – функции принадлежности, определенные соответственно на х и у. Приведем более детальное пояснение Знание эксперта A → В отражает нечеткое причинное отношение предпосылки и заключения, поэтому его можно назвать нечетким отношением и обозначить через R: R = A → В, где «→» называют нечеткой импликацией. Отношение R можно рассматривать как нечеткое подмножество прямого произведения X × Y полного множества предпосылок X и заключений Y. Таким образом, процесс получения (нечеткого) результата вывода B' с использованием данного наблюдения А' и знания А→В можно представить в виде композиционного правила нечеткий «modus ponens»: В' = А' • R = А' • (А → В), где «•» – операция свертки. Как операцию композиции, так и операцию импликации в алгебре нечетких множеств можно реализовывать по-разному (при этом будет отличаться и получаемый результат), но в любом случае общий логический вывод осуществляется за следующие пять этапов. 1) Введение нечеткости (фаззификация, fuzzification). Функции принадлежности, определенные на входных переменных, применяются к их фактическим значениям для определения степени истинности каждой предпосылки каждого правила. Четким значениям входных переменных ставятся в соответствие нечеткие значения с помощью функций принадлежности конкретной переменной. 2) Агрегирование. Вычисленное значение истинности для предпосылок каждого правила применяется к заключениям каждого правила. Это приводит к одному нечеткому подмножеству, которое будет назначено каждой переменной вывода для каждого правила. 3) Активизация. В качестве правил логического вывода обычно используются только операции min (МИНИМУМ) или prod (УМНОЖЕНИЕ). В логическом выводе МИНИМУМА функция принадлежности вывода «отсекается» по высоте, соответствующей вычисленной степени истинности предпосылки правила (нечеткая логика «И», то есть для правила берется минимальное значение степени истинности предпосылок). В логическом выводе УМНОЖЕНИЯ функция принадлежности вывода масштабируется при помощи вычисленной степени истинности предпосылки правила. 4) Аккумуляция. Все нечеткие подмножества, назначенные к каждой переменной вывода (во всех правилах), объединяются вместе, чтобы сформировать одно нечеткое подмножество для всех переменных вывода. При подобном объединении обычно используются операции max (МАКСИМУМ) или sum (СУММА) При композиции МАКСИМУМА комбинированный вывод нечеткого подмножества конструируется как поточечный максимум по всем нечетким подмножествам (нечеткая логика «ИЛИ»). При композиции СУММЫ комбинированный вывод нечеткого подмножества формируется как поточечная сума по всем нечетким подмножествам, назначенным переменной вывода правилами логического вывода. 5) Приведение к четкости (дефаззификация, defuzzification) используется, если требуется преобразовать нечеткий набор выводов в четкое число. Существует большее количество методов приведения к четкости, некоторые из которых рассмотрены ниже. Фазификатор Рассмотрим подробнее первый этап процедуры нечеткого вывода. Фазификатор преобразует N-мерный входной вектор х = [ x1, x2, …, xN ] в нечеткое множество А, характеризуемое функцией принадлежности с четкими переменными. Несмотря на то, что нечеткие системы могут иметь функции принадлежности произвольной структуры, с практической точки зрения наибольшей популярностью пользуются функции гауссовского типа, а также треугольные и трапецеидальные функции. Рис. 6.5 Иллюстрация влияния параметров гауссовской функции на ее форму: а) влияние размещения центра с при σ = 1; б) влияние значения σ при постоянном значении с = 1 Общая форма гауссовой функции для переменной х с центром с и вариацией σ для множества F имеет вид: (6.7) На рис. 6.5. представлена форма типовых гауссовских функций при различ­ных параметрах с и σ , причем на рис. 6.5а показано влияние размещения центра с при неизменном значении σ, а на рис. 6.5б - влияние значения σ при фиксиро­ванном положении с. Параметр с обозначает центр нечеткого множества, а его из­менение соответствует смещению функции принадлежности по горизонтальной оси. Праметр σ, иногда называемый коэффициентом широты, отвечает за форму функции. Чем меньше его значение, тем больше крутизна функции. Следует отме­тить, что при соответствующем смещении центра гауссовская функция может реализовать и сигмоидальную функцию (чаще всего при смещении вправо с с =4). Помимо гауссовской функции принадлежности, на практике часто приме­няется симметричная треугольная функция, которую можно записать в виде (6.8) Интерпретация центральной точки с и ширины d для треугольной функции представлена на рис.6.6. Рис. 6.6 Треугольная форма функции Эта функция тоже нормирована и принимает единичное значение в центральной точке с. Обобщением треугольной функции является трапецеидальная функция принадлежности, форма и обозначения кото­рой показаны на рис. 6.7. Рис. 6.7 Трапецеидальная форма функции принадлежности Если определить, , где s обозначает угол наклона, то трапецеидальная функция описывается зависимостью (6.9) Выбор значения t = 0 редуцирует трапецеидальную функцию до треугольной формы. Дефазификатор Рассмотрим подробнее последний этап процедуры нечеткого вывода. Дефазификатор трансформирует нечеткое множество в полностью детерми­нированное точечное решение у. Нечеткое множество представляет зависимость как функцию от выходной переменной у. Преобразование этого множества в единственное точечное решение возможно многими способами. Наиболее известны среди них: 1) центроидный. В общем случае: ; (6.10) для дискретного варианта: (6.11) 2) Первый максимум (First-of-Maxima). Четкая величина вывода находится как наименьшее значение, при котором достигается максимум итогового нечеткого множества (рис. 6.8, a). 3) Средний максимум (Middle-of-Maxima). Четкое значение находится по формуле: (6.12) где G − подмножество элементов, максимизирующих С (рис.6.8,б). Для дискретного варианта (С дискретно): (6.13) Рис. 6.8. Иллюстрация к методам приведения к четкости: а - первый максимум; б - средний максимум (6.14) 4) Критерий максимума (Max-Criterion). Четкое значение выбирается произвольно среди множества элементов, для которых С достигает максимума: (6.15) 5) Высотная дефаззификация (Height defuzzification). Элементы области определения Ω, для которых значения функции принадлежности меньше, чем некоторый уровень α, в расчет не принимаются, и четкое значение рассчитывается в соответствии с выражением: (6.16) где Сα – нечеткое множество α-уровня (см. выше). Преимущества использования нечеткой логики Операторы нечеткой логики очень схожи с обычными булевыми операторами. Функции принадлежности и правила нечеткой логики, подвергнутые лингвистической модификации, позволяют значительно расширить возможности системных операторов. Разработчики могут намного упростить сложность систем, используя нечеткую логику, поскольку она позволяет моделировать комплексные программы с большим количеством входов и выходов. С помощью нечеткой логики можно добиться снижения системных требований, а значит, сократить расходы на аппаратные средства. Во многих случаях сложное математическое моделирование предпочтительнее заменить функциями принадлежности и правилами нечеткой логики и с их помощью управлять системой. При сокращении объемов информации размеры кода уменьшаются, поэтому система работает быстрее. Кроме того, это позволяет использовать менее совершенные аппаратные средства. Кроме того, нечеткие понятия позволяют «говорить с экспертом на одном языке». Как было описано выше, степень успешности взаимодействия с экспертом во многом определяет успех всего проекта. Нечеткая логика используется в самых разнообразных приложениях. Наиболее очевидная область ее применения – системы управления, которым нечеткая логика уже обеспечила коммерческий успех. Нечеткая логика используется в устройстве видеокамер и фотоаппаратов с автофокусом, системах смешивания цемента, автомобильных системах (например, системах АБС) и даже системах, основанных на правилах. Наверное, самые полезные области применения все еще остаются неизвестными. Само название «нечеткая логика» не внушает особого доверия, хотя давно известно, что это надежный метод. Как и многие другие методики ИИ, нечеткая логика в настоящее время все чаще используется в устройствах повседневного применения, где она больше не ассоциируется с искусственным интеллектом. Лекция 7. НЕЙРОННЫЕ СЕТИ Особенностью интеллектуальных систем является способ­ность решать слабоструктурированные и плохо формализован­ные задачи. Эта способность основана на применении различных методов моделирования рассуждений для обработки символьной информации. Традиционным подходом к построению механиз­мов рассуждения является использование дедуктивного логичес­кого вывода на правилах (rule-based reasoning), который приме­няется в экспертных системах продукционного и логического ти­па. При таком подходе необходимо заранее сформу­лировать весь набор закономерностей, описывающих предмет­ную область. Альтернативный подход основан на концепции обу­чения по примерам (case-based reasoning). В этом случае при по­строении интеллектуальной системы не требуется заранее знать обо всех закономерностях исследуемой области, но необходимо располагать достаточным количеством примеров для настройки разрабатываемой адаптивной системы, которая после обучения будет способна получать требуемые результаты с определенной степенью достоверности. В качестве таких адаптивных систем применяются искусственные нейронные сети. МОДЕЛЬ ИСКУССТВЕННОГО НЕЙРОНА Искусственная нейронная сеть (ИНС) - это упрощенная мо­дель биологического мозга, точнее нервной ткани. Ес­тественная нервная клетка (нейрон) состоит из тела (сомы), со­держащего ядро, и отростков — дендритов, по которым в нейрон поступают входные сигналы. Один из отростков, ветвящийся на конце, служит для передачи выходных сигналов данного нейрона другим нервным клеткам. Он называется аксоном. Соединение аксона с дендритом другого нейрона называется синапсом. Ней­рон возбуждается и передает сигнал через аксон, если число при­шедших по дендритам возбуждающих сигналов больше, чем чис­ло тормозящих. Сеть ИНС представляет собой совокупность простых вычис­лительных элементов - искусственных нейронов, каждый из ко­торых обладает определенным количеством входов (дендритов) и единственным выходом (аксоном), разветвления которого под­ходят к синапсам, связывающим его с другими нейронами. На входы нейрона поступает информация извне или от других ней­ронов. Каждый нейрон характеризуется функцией преобразова­ния входных сигналов в выходной (функция активации нейро­на). Нейроны в сети могут иметь одинаковые или разные функ­ции активации. Сигналы, поступающие на вход нейрона, не­равнозначны в том смысле, что информация из одного источни­38А может быть более важной, чем из другого. Приоритеты входов задаются с помощью вектора весовых коэффициентов, модели­рующих синаптическую силу биологических нейронов. Нейрон (нервная клетка) особая биологическая клетка, которая обрабатывает информацию. Искусственный нейрон На рис.7.1 показана структура нейрона. Нейрон состоит из элементов трех ти­пов: умножителей (синапсов), сумматора и нелинейного преобра­зователя. Синапсы осуществляют связь между нейронами, умно­жают входной сигнал на число, характеризующее силу связи (вес синапса). Сумматор выполняет сложение сигналов, поступающих по синаптическим связям от других нейронов, и внешних входных сигналов. Нелинейный преобразователь реализует нелинейную функцию одного аргумента – выхода сумматора. Рис. 7.1 Структура искусственного нейрона Эта функция на­зывается функцией активации нейрона. Нейрон реализует скалярную функцию векторного аргумента. Математическая модель нейрона: (7.1) где wi – вес синапса, i = 1...n; b - значение смещения; s - результат суммирования; xi - компонент входного вектора (входной сигнал), i = 1...n; у - выходной сигнал нейрона; п - число входов нейрона; f - нелинейное преобразование (функ­ция активации). В общем случае входной сигнал, весовые коэффициенты и смещение могут принимать действительные значения, а во многих практических задачах - лишь некоторые фиксированные значения. Выход (у) определяется видом функции активации и может быть как действительным, так и целым. Синаптические связи с положительными весами называют возбуждающими, с отрицательными весами - тормозящими. Функции активации Одной из наиболее распространенных функций активации является нелинейная функция активации с насыщением, так называемая логистическая функция или сигмоид (функция S-бразного вида): При уменьшении а сигмоид становится более пологим, в пределе при а = 0 вырождаясь в горизонтальную линию на уровне 0,5, при увеличении а сигмоид приближается к виду функции единичного скачка с порогом Т. Из выражения для сигмоида очевидно, что выходное значение нейрона лежит в диапазоне (0, 1). Одно из ценных свойств сигмоидальной функции - простое выражение для ее производной: Следует отметить, что сигмоидальная функция дифферен­цируема на всей оси абсцисс, что используется в некоторых алго­ритмах обучения. Кроме того, она обладает свойством усиливать слабые сигналы лучше, чем большие, и предотвращает насыще­ние от больших сигналов, так как они соответствуют областям ар­гументов, где сигмоид имеет пологий наклон. Таблица 7.1 Функции активации нейронов Название Формула Область значений Линейная f (s) = k s (-∞, ∞) Полулинейная (0, ∞) Логистическая (сигмоидальная) (0, 1) Гиперболический тангенс (сигмоидальная) (-1, 1) Экспоненциальная (0, ∞) Синусоидальная (-1, 1) Сигмоидальная (рациональная) (-1, 1) Шаговая (линейная с насыщением) (-1, 1) Пороговая (0, 1) Модульная (0, ∞) Знаковая (сигнатурная) (-1, 1) Квадратичная (0, ∞) Рис. 7.2. Примеры активационных функций: а - функция единичного скачка; б - линейный порог (гистерезис); в - сигмоид (логистическая функция); г - сигмоид (гиперболический тангенс) Тип функции активации выбирается с учетом конкретной зада­чи, решаемой с применением нейронных сетей. Например, в за­дачах аппроксимации и классификации предпочтение отдают логистической (сигмоидальной) кривой. Чтобы построить ИНС для решения конкретной задачи, нужно выбрать тип соединения нейронов, опреде­лить вид передаточных функций элементов и подобрать весовые коэффициенты межнейронных связей. При всем многообразии возможных конфигураций ИНС на практике получили распространение лишь некоторые из них. Классические модели нейронных сетей рассмотрены ниже. Классификация нейронных сетей и их свойства Нейронная сеть представляет собой совокупность нейроподобных элементов, определенным образом соединенных друг с другом и с внешней средой с помощью связей, определяемых весовыми коэффициентами. В зависимости от функций, выполняемых нейронами в сети, можно выделить три их типа: • входные нейроны, на которые подается вектор, кодирующий входное воздействие или образ внешней среды, в них обычно не осуществляется вычислительных процедур, а информация передается с входа на выход путем изменения их активации; • выходные нейроны, выходные значения которых представляют выходы нейронной сети; преобразования в них осуществляются по выражениям (7.1). Несут важную функцию приведения значения выхода сети в требуемый промежуток (осуществляется это с помощью функции активации); • промежуточные нейроны, составляющие основу нейронных сетей, преобразования в которых выполняются также по выражениям (7.1). В большинстве нейронных моделей тип нейрона связан с его расположением в сети. Если нейрон имеет только выходные связи, то это входной нейрон, если наоборот – выходной нейрон. Однако возможен случай, когда выход топологически внутреннего нейрона рассматривается как часть выхода сети. В процессе функционирования сети осуществляется преобразование входного вектора в выходной, некоторая переработка информации. Конкретный вид выполняемого сетью преобразования данных обусловливается не только характеристиками нейроподобных элементов, но и особенностями ее архитектуры, а именно топологией межнейронных связей, выбором определенных подмножеств нейроподобных элементов для ввода и вывода информации, способами обучения сети, наличием или отсутствием конкуренции между нейронами, направлением и способами управления и синхронизации передачи информации между нейронами. С точки зрения топологии можно выделить три основных типа нейронных сетей: • полносвязные (рис.7.3, а); • многослойные или слоистые (рис. 7.3, б); • слабосвязные (с локальными связями) (рис. 7.3, в). Рис. 7.3. Архитектуры нейронных сетей: а - полносвязная сеть, б - многослойная сеть с последовательными связями, в - слабосвязные сети В полносвязных нейронных сетях каждый нейрон передает свой выходной сигнал остальным нейронам, в том числе и самому себе. Все входные сигналы подаются всем нейронам. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети. В многослойных нейронных сетях нейроны объединяются в слои. Слой содержит совокупность нейронов с едиными входными сигналами. Число нейронов в слое может быть любым и не зависит от количества нейронов в других слоях. В общем случае сеть состоит из Q слоев, пронумерованных слева направо. Внешние входные сигналы подаются на входы нейронов входного слоя (его часто нумеруют как нулевой), а выходами сети являются выходные сигналы последнего слоя. Кроме входного и выходного слоев в многослойной нейронной сети есть один или несколько скрытых слоев. Связи от выходов нейронов некоторого слоя q к входам нейронов следующего слоя (q+1) называются последовательными. Внутри одного слоя используется одна и та же функция активации. В свою очередь, среди многослойных нейронных сетей выделяют следующие типы. 1) Монотонные. Это частный случай слоистых сетей с дополнительными условиями на связи и нейроны. Каждый слой, кроме последнего (выходного), разбит на два блока: возбуждающий и тормозящий. Связи между блоками тоже разделяются на тормозящие и возбуждающие. Если от нейронов блока А к нейронам блока В ведут только возбуждающие связи, то это означает, что любой выходной сигнал блока является монотонной неубывающей функцией любого выходного сигнала блока А. Если же эти связи только тормозящие, то любой выходной сигнал блока В является невозрастающей функцией любого выходного сигнала блока А. Для нейронов монотонных сетей необходима монотонная зависимость выходного сигнала нейрона от параметров входных сигналов. 2) Сети без обратных связей. В таких сетях нейроны входного слоя получают входные сигналы, преобразуют их и передают нейронам первого скрытого слоя, и так далее вплоть до выходного, который выдает сигналы для интерпретатора и пользователя. Если не оговорено противное, то каждый выходной сигнал q-го слоя подастся на вход всех нейронов (q+1)-го слоя; однако возможен вариант соединения q-гo слоя с произвольным (q+p)-м слоем. Среди многослойных сетей без обратных связей различают полносвязные (выход каждого нейрона q-гo слоя связан с входом каждого нейрона (q+1)-го слоя) и частично полносвязные. Классическим вариантом слоистых сетей являются полносвязные сети прямого распространения (рис.7.4). 3) Сети с обратными связями. В сетях с обратными связями информация с последующих слоев передается на предыдущие. Среди них, в свою очередь, выделяют следующие: • слоисто-циклические, отличающиеся тем, что слои замкнуты в кольцо: последний слой передает свои выходные сигналы первому; все слои равноправны и могут как получать входные сигналы, так и выдавать выходные; • слоисто-полносвязанные состоят из слоев, каждый из которых представляет собой полносвязную сеть, а сигналы передаются как от слоя к слою, так и внутри слоя; в каждом слое цикл работы распадается на три части: прием сигналов с предыдущего слоя, обмен сигналами внутри слоя, выработка выходного сигнала и передача к последующему слою; • полносвязанно-слоистые, по своей структуре аналогичные слоисто-полносвязанным, но функционирующие по-другому: в них не разделяются фазы обмена внутри слоя и передачи следующему, на каждом такте нейроны всех слоев принимают сигналы от нейронов как своего слоя, так и последующих. Рис. 7.4. Многослойная (двухслойная) сеть прямого распространения В качестве примера сетей с обратными связями на рис.7.5 представлены частично-рекуррентные сети Элмана и Жордана. В слабосвязанных нейронных сетях нейроны располагаются в узлах прямоугольной или гексагональной решетки. Каждый нейрон связан с четырьмя (окрестность фон Неймана), шестью (окрестность Голея) или восемью (окрестность Мура) своими ближайшими соседями. Известные нейронные сети можно разделить по типам структур нейронов на гомогенные (однородные) и гетерогенные. Гомогенные сети состоят из нейронов одного типа с единой функцией активации, а в гетерогенную сеть входят нейроны с различными функциями активации. Существуют бинарные и аналоговые сети. Первые из них оперируют только двоичными сигналами, и выход каждого нейрона может принимать значение либо логического ноля (заторможенное состояние), либо логической единицы (возбужденное состояние). Еще одна классификация делит нейронные сети на синхронные и асинхронные. В первом случае в каждый момент времени лишь один нейрон меняет свое состояние, во втором – состояние меняется сразу у целой группы нейронов, как правило, у всего слоя. Алгоритмически ход времени в нейронных сетях задается итерационным выполнением однотипных действий над нейронами. Далее будут рассматриваться только синхронные сети. Рис. 7.5. Частично-рекуррентные сети: а – Элмана, б – Жордана Сети можно классифицировать также по числу слоев. Теоретически число слоев и число нейронов в каждом слое может быть произвольным, однако фактически оно ограничено ресурсами компьютера или специализированных микросхем, на которых обычно реализуется нейронная сеть. Чем сложнее сеть, тем более сложные задачи она может решать. Выбор структуры нейронной сети осуществляется в соответствии с особенностями и сложностью задачи. Для решения отдельных типов задач уже существуют оптимальные конфигурации. Если же задача не может быть сведена ни к одному из известных типов, приходится решать сложную проблему синтеза новой конфигурации. При этом необходимо руководствоваться следующими основными правилами: • возможности сети возрастают с увеличением числа нейронов сети, плотности связей между ними и числом слоев; • введение обратных связей наряду с увеличением возможностей сети поднимает вопрос о динамической устойчивости сети; • сложность алгоритмов функционирования сети, введение нескольких типов синапсов способствует усилению мощности нейронной сети. Вопрос о необходимых и достаточных свойствах сети для решения задач того или иного рода представляет собой целое направление нейрокомпьютерной науки. Так как проблема синтеза нейронной сети сильно зависит от решаемой задачи, дать общие подробные рекомендации затруднительно. В большинстве случаев оптимальный вариант получается на основе интуитивного подбора, хотя в литературе приведены доказательства того, что для любого алгоритма существует нейронная сеть, которая может его реализовать. Остановимся на этом подробнее. Многие задачи распознавания образов (зрительных, речевых), выполнения функциональных преобразований при обработке сигналов, управления, прогнозирования, идентификации сложных систем сводятся к следующей математической постановке. Необходимо построить такое отображение X→Y, чтобы на каждый возможный входной сигнал X формировался правильный выходной сигнал Y. Отображение задается конечным набором пар (<вход>, <известный выход>). Число этих пар (обучающих примеров) существенно меньше общего числа возможных сочетаний значений входных и выходных сигналов. Совокупность всех обучающих примеров носит название обучающей выборки. В задачах распознавания образов X – некоторое представ­ление образа (изображение, вектор), Y – номер класса, к которому принадлежит входной образ. В задачах управления X – набор контролируемых параметров управляемого объекта, Y – код, определяющий управляющее воздействие, соответствующее текущим значениям контролируемых параметров. В задачах прогнозирования в качестве входных сигналов используются временные ряды, представляющие значения контролируемых переменных на некотором интервале времени. Выходной сигнал – множество переменных, которое является подмножеством переменных входного сигнала. При идентификации X и Y представляют входные и выходные сигналы системы соответственно. Вообще говоря, большая часть прикладных задач может быть сведена к реализации некоторого сложного функционального многомерного преобразования. В результате отображения X → Y необходимо обеспечить формирование правильных выходных сигналов в соответствии: • со всеми примерами обучающей выборки; • со всеми возможными входными сигналами, которые не вошли в обучающую выборку. Второе требование в значительной степени усложняет задачу формирования обучающей выборки. В общем виде эта задача в настоящее время еще не решена, однако во всех известных случаях может быть найдено частное решение. Лекция 8. Нейронные сети. Типы НС. Обучение НС. Применение НС. Рекуррентные нейронные сети Рекуррентными нейронными сетями называются такие сети, в ко­торых выходы нейронных элементов последующих слоев имеют синаптические соединения с нейронами предшествующих слоев. Это приво­дит к возможности учета результатов преобразования нейронной сетью информации на предыдущем этапе для обработки входного вектора на следующем этапе функционирования сети. Рекуррентные сети могут использоваться для решения задач прогнозирования и управления. Архитектура рекуррентных сетей Существуют различные варианты архитектур рекуррентных ней­ронных сетей. Сеть Джордана: В 1986 г. Джордан (Jordan) предложил рекур­рентную сеть (рис.8.1), в которой выходы нейронных элементов по­следнего слоя соединены посредством специальных входных нейронов с нейронами промежуточного слоя. Такие входные нейронные эле­менты называются контекстными нейронами (context units). Они рас­пределяют выходные данные нейронной сети на нейронные элементы промежуточного слоя. Рис. 8.1 Архитектура рекуррентной ней­ронной сети с обратными связями от нейро­нов выходного слоя Число контекстных нейронов равняется числу выходных ней­ронных элементов рекуррентной сети. В качестве выходного слоя та­ких сетей используются нейронные элементы с линейной функцией активации. Тогда выходное значение j-го нейронного элемента последнего слоя определяется по формуле (8.1) где vij - весовой коэффи­циент между i-м нейроном промежуточного и j-м ней­роном выходного слоев; Pi(t)- выходное значение i-го нейрона промежуточ­ного слоя; tj - пороговое значение j-го нейрона вы­ходного слоя. Взвешенная сумма i-гo нейронного элемента промежуточного слоя определяется следующим образом: (8.2) где wij – весовой коэффициент между j-м нейроном входного и i-м нейроном промежуточного слоев; р – число нейронов выходного слоя; wki – весовой коэффициент между k-м контекстным нейроном и i-м нейроном промежуточного слоя; T – пороговое значение i-го нейрона промежуточного слоя; n – размерность входно­го вектора. Тогда выходное значение i-го нейрона скрытого слоя: (8.3) В качестве функции не­линейного преобразования F обычно используется гипер­болический тангенс или сигмоидная функция. Для обучения рекуррентных нейронных сетей применяется алго­ритм обратного распространения ошибки (будет рассмотрен ниже). Алгоритм обучения рекуррентной нейронной сети в общем слу­чае состоит из следующих шагов: 1. В начальный момент времени t = 1 все контекстные нейроны устанавливаются в нулевое состояние – выходные значения прирав­ниваются нулю. 2. Входной образ подается на сеть и происходит прямое распро­странение его в нейронной сети. 3. В соответствии с алгоритмом обратного распространения ошибки модифицируются весовые коэффициенты и пороговые значе­ния нейронных элементов. 4. Устанавливается t = t+1 и осуществляется переход к шагу 2. Обучение рекуррентной сети производится до тех пор, пока сум­марная среднеквадратичная ошибка сети не станет меньше заданной. Рециркуляционные нейронные сети Рециркуляционные сети характеризуются как прямым Y = f(X), так и обратным X = f(У) преобразованием информации. Задача тако­го преобразования – достижение наилучшего автопрогноза или само­воспроизводимости вектора X. Рециркуляционные нейронные сети применяются для сжатия (прямое преобразование) и восстановления исходной (обратное преобразование) информации. Такие сети явля­ются самоорганизующимися в процессе работы, где обучение произ­водится без учителя. Архитектура рециркуляционной нейронной сети Рециркуляционная нейронная сеть представляет собой совокупность двух слоев нейронных элементов, которые соединены между собой двунаправленными связями (рис.8.2). Рис.8.2 Архитектура рециркуляцион­ной нейронной сети Каждый из слоев нейрон­ных элементов может использо­ваться в качестве входного или выходного. Если слой нейрон­ных элементов служит в качест­ве входного, то он выполняет распределительные функции. Иначе нейронные элементы слоя являются обрабатывающи­ми. Весовые коэффициенты, соответствующие прямым и обратным связям, характери­зуются матрицей весовых коэффициентов W и W'. Для наглядности рециркуляционную сеть можно представить в развер­нутом виде, как показано на рис.8.3. Такое представление сети является эквивалентным и характеризует полный цикл преобразования информации. При этом промежуточный слой нейронных элементов производит кодирование (сжатие) входных данных X, а последний слой – восстановление сжатой информации Y. Слой нейронной сети, соответствующий матрице связи W, назовем пря­мым, а соответствующий матрице связей W' – обратным. Рис. 8.3 Эквивалентное представление ре­циркуляционной сети В качестве функции активации нейронных элементов F может использоваться как линейная, так и нелинейная функции. Релаксационные НС Релаксационные нейронные сети характеризуются прямым и обратным распро­странением информации между слоями нейронной сети. В основе функционирования лежит итеративный принцип работы. На каждой итерации процесса происходит обработка данных, полученных на предыдущем шаге. Такая циркуляция информации продолжается до тех пор, пока не установится состоя­ние равновесия. При этом состояния нейронных элементов перестают изменяться и ха­рактеризуются стационарными значениями. Нейронные сети Хопфилда Нейронная сеть Хопфилда реализует существенное свойст­во автоассоциативной памяти – восстановление по искаженному (зашумленному) образу ближайшего к нему эталонного. Входной вектор используется как начальное состояние се­ти, и далее сеть эволюционирует согласно своей динамике. При­чем любой пример, находящийся в области притяжения хранимого образца, может быть использован как указатель для его восста­новления. Выходной (восстановленный) образец устанавливается, когда сеть достигает равновесия. Обучение сети Хопфилда производится по правилу Хебба. Структура сети Хопфилда (рис.8.4) состо­ит из одного слоя нейронов, число которых определяет число вхо­дов и выходов сети. Выход каждого нейрона соединен с входами всех остальных нейронов. Выходные сигналы нейронов являются одновременно входными сигналами сети: Xi(k)=Yi(k-1) Основные зависимости, определяющие сеть Хопфилда, можно представить в виде (8.4) с начальным условием yi(0) = xj. В процессе функционирования сети Хопфилда можно выделить два режима: обучения и классификации. В режиме обучения на основе известных обучающих выборок х подбираются весовые коэффициенты wij. В режиме классификации при зафиксированных зна­чениях весов и вводе конкретного начального состояния нейронов у(0) = х возникает переходный процесс, протекающий в соответствии с выраже­нием (Формула выше) и завершающийся в одном из локальных минимумов, для которого y(k) = y(k-l). Для безошибочной работы сети Хопфилда число запоми­наемых эталонов N не должно превышать 0,15n (n-число нейронов). Рис. 8.4 Структура нейронной сети Хопфилда ПОСТРОЕНИЕ НЕЙРОННОЙ СЕТИ При построении модели ИНС прежде всего необходимо точ­но определить задачи, которые будут решаться с ее помощью. В настоящее время нейросетевые технологии успешно применяют­ся для прогнозирования, распознавания и обобщения. Первым этапом построения нейросетевой модели является тщательный отбор входных данных, влияющих на ожидаемый ре­зультат. Из исходной информации необходимо исключить все сведения, не относящиеся к исследуемой проблеме. В то же вре­мя следует располагать достаточным количеством примеров для обучения ИНС. Существует эмпирическое правило, которое ус­танавливает рекомендуемое соотношение X между количеством обучающих примеров, содержащих входные данные и правиль­ные ответы, и числом соединений в нейронной сети: X <10. Для факторов, которые включаются в обучающую выборку, целесообразно предварительно оценить их значимость, проведя корреляционный и регрессионный анализ, и проанализировать диапазоны их возможных изменений. На втором этапе осуществляется преобразование исходных данных с учетом характера и типа проблемы, отображаемой ней­росетевой моделью, и выбираются способы представления ин­формации. Эффективность нейросетевой модели повышается, если диапазоны изменения входных и выходных величин приве­дены к некоторому стандарту, например [0,1] или [-1,1]. Третий этап заключается в конструировании ИНС, т.е. в проектировании ее архитектуры (число слоев и число нейронов в каждом слое). Структура ИНС формируется до начала обуче­ния, поэтому успешное решение этой проблемы во многом определяется опытом и искусством аналитика, проводящего ис­следования. Четвертый этап связан с обучением сети, которое может проводиться на основе конструктивного или деструктивного подхода. В соответствии с первым подходом обучение ИНС на­чинается на сети небольшого размера, который постепенно уве­личивается до достижения требуемой точности по результатам тестирования. Деструктивный подход базируется на принципе «прореживания дерева», в соответствии с которым из сети с заве­домо избыточным объемом постепенно удаляют «лишние» ней­роны и примыкающие к ним связи. Этот подход дает возмож­ность исследовать влияние удаленных связей на точность сети. Процесс обучения нейронной сети представляет собой уточне­ние значений весовых коэффициентов для отдельных узлов на основе постепенного увеличения объема входной и выходной информации. Началу обучения должна предшествовать про­цедура выбора функции активации нейронов, учитывающая ха­рактер решаемой задачи. В частности, в трехслойных перцептронах на нейронах скрытого слоя применяется в большинстве слу­чаев логистическая функция, а тип передаточной функции ней­ронов выходного слоя определяется на основе анализа результа­тов вычислительных экспериментов на сети. Индикатором обу­чаемости ИНС может служить гистограмма значений межней­ронных связей. На пятом этапе проводится тестирование полученной модели ИНС на независимой выборке примеров. ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ Важнейшим свойством нейронных сетей является их способ­ность к обучению, что делает нейросетевые модели незаменимы­ми при решении задач, для которых алгоритмизация является не­возможной, проблематичной или слишком трудоемкой. Обучение нейронной сети заключается в изменении внутренних параметров модели таким образом, чтобы на выходе ИНС генерировался век­тор значений, совпадающий с результатами примеров обучающей выборки. Изменение параметров нейросетевой модели может вы­полняться разными способами в соответствии с различными алгоритмами обучения. Парадигма обучения определяется доступ­ностью необходимой информации. Выделяют три парадигмы: • обучение с учителем (контролируемое); • обучение без учителя (неконтролируемое); • смешанное обучение. При обучении с учителем все примеры обучающей выборки содержат правильные ответы (выходы), соответствующие исход­ным данным (входам). В процессе контролируемого обучения синаптические веса настраиваются так, чтобы сеть порождала отве­ты, наиболее близкие к правильным. Обучение без учителя используется, когда не для всех приме­ров обучающей выборки известны правильные ответы. В этом случае предпринимаются попытки определения внутренней структуры поступающих в сеть данных с целью распределить об­разцы по категориям (модели Кохонена). При смешанном обучении часть весов определяется посредст­вом обучения с учителем, а другая часть получается с помощью алгоритмов самообучения. Обучение по примерам характеризуется тремя основными свойствами: емкостью, сложностью образцов и вычислительной сложностью. Емкость соответствует количеству образцов, кото­рые может запомнить сеть. Сложность образцов определяет спо­собности нейронной сети к обучению. В частности, при обуче­нии ИНС могут возникать состояния «перетренировки», в кото­рых сеть хорошо функционирует на примерах обучающей выбор­ки, но не справляется с новыми примерами, утрачивая способ­ность обучаться. Рассмотрим известные правила обучения ИНС. Правило коррекции по ошибке. Процесс обучения ИНС состо­ит в коррекции исходных значений весовых коэффициентов межнейронных связей, которые обычно задаются случайным об­разом. При вводе входных данных запоминаемого примера (сти­мула) появляется реакция, которая передается от одного слоя нейронов к другому, достигая последнего слоя, где вычисляется результат. Разность между известным значением результата и ре­акцией сети соответствует величине ошибки, которая может ис­пользоваться для корректировки весов межнейронных связей. Корректировка заключается в небольшом (обычно менее 1%) увеличении синаптического веса тех связей, которые усиливают правильные реакции, и уменьшении тех, которые способствуют ошибочным. Это простейшее правило контролируемого обуче­ния (дельта-правило) используется в однослойных сетях с одним уровнем настраиваемых связей между множеством входов и мно­жеством выходов. Оптимальные значения весов межнейронных соединений можно определить путем минимизации среднеквадратичной ошибки с использованием детерминированных или псевдослу­чайных алгоритмов поиска экстремума в пространстве весовых коэффициентов. При этом возникает традиционная проблема оптимизации, связанная с попаданием в локальный минимум (будет рассмотрена ниже). Правило Хебба. Оно базируется на следующем нейрофизи­ологическом наблюдении: если нейроны по обе стороны синапса активизируются одновременно и регулярно, то сила их синаптической связи возрастает. При этом изменение веса каждой меж­нейронной связи зависит только от активности нейронов, обра­зующих синапс. Это существенно упрощает реализацию алгорит­мов обучения. Обучение методом соревнования. В отличие от правила Хебба, где множество выходных нейронов может возбуждаться одновре­менно, в данном случае выходные нейроны соревнуются (конкурируют) между собой за активизацию. В процессе сорев­новательного обучения осуществляется модификация весов свя­зей выигравшего нейрона и нейронов, расположенных в его окрестности («победитель забирает все»). Рассмотрим один из наиболее распространенных алгоритмов обучения с учителем, относящийся к правилу коррекции по ошибке. Алгоритм обратного распространения ошибки В многослойных нейронных сетях оптимальные выходные значения нейронов всех слоев, кроме последнего, как правило, неизвестны. Трех- или более слойный персептрон уже невозможно обучить, руководствуясь только величинами ошибок на выходах сети. Один из вариантов решения этой проблемы – разработка наборов выходных сигналов, соответствующих входным, для каждого слоя нейронной сети, что, конечно, является очень трудоемкой операцией и не всегда осуществимо. Второй вариант – динамическая подстройка весовых коэффициентов синапсов, в ходе которой выбираются, как правило, наиболее слабые связи и изменяются на малую величину в ту или иную сторону, а сохраняются только те изменения, которые повлекли уменьшение ошибки на выходе всей сети. Очевидно, что данный метод, несмотря на кажущуюся простоту, требует громоздких рутинных вычислений. И, наконец, третий, более приемлемый вариант – распространение сигналов ошибки от выходов нейронной сети к ее входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы. Этот алгоритм обучения получил название процедуры обратного распространения ошибки (error back propagation). Именно он рассматривается ниже. Алгоритм обратного распространения ошибки – это итеративный градиентный алгоритм обучения, который используется с целью минимизации среднеквадратичного отклонения текущих от требуемых выходов многослойных нейронных сетей с последовательными связями. Согласно методу наименьших квадратов, минимизируемой целевой функцией ошибки нейронной сети является величина: (8.5) где – реальное выходное состояние нейрона у выходного слоя нейронной сети при подаче на ее входы k-го образа; dj,k – требуемое выходное состояние этого нейрона. Суммирование ведется по всем нейронам выходного слоя и по всем обрабатываемым сетью образам. Минимизация методом градиентного спуска обеспечивает подстройку весовых коэффициентов следующим образом: (8.6) где wij – весовой коэффициент синаптической связи, соединяющей i-й нейрон слоя (q-1) с j-м нейроном слоя q; η – коэффициент ско­рости обучения, 0 < η <1. В соответствии с правилом дифференцирования сложной функции: , (8.7) где sj – взвешенная сумма входных сигналов нейрона j, т.е. аргумент активационной функции. Так как производная активационной функции должна быть определена на всей оси абсцисс, то функция единичного скачка и прочие активационные функции с неоднородностями не подходят для рассматриваемых нейронных сетей. В них применяются такие гладкие функции, как гиперболический тангенс или классический сигмоид с экспонентой (см. табл.7.1). Например, в случае гиперболического тангенса: (8.8) Третий множитель ∂sj / ∂wij равен выходу нейрона предыдущего слоя . Что касается первого множителя в (8.7), он легко раскладывается следующим образом: (8.8) Здесь суммирование по r выполняется среди нейронов слоя (q+1). Введя новую переменную (8.9) получим рекурсивную формулу для расчетов величин слоя q из величин более старшего слоя (q+1): (8.10) Для выходного слоя: (8.11) Теперь можно записать (8.6) в раскрытом виде: (8.12) Иногда для придания процессу коррекции весов некоторой инерционности, сглаживающей резкие скачки при перемещении по поверхности целевой функции, (8.12) дополняется значением изменения веса на предыдущей итерации: (8.13) где µ – коэффициент инерционности; t – номер текущей итерации. Таким образом, полный алгоритм обучения нейронной сети с помощью процедуры обратного распространения строится следующим образом. ШАГ 1. Подать на входы сети один из возможных образов и в режиме обычного функционирования нейронной сети, когда сигналы распространяются от входов к выходам, рассчитать значения последних. Напомним, что: (8.14) где L – число нейронов в слое (q-1) с учетом нейрона с постоянным выходным состоянием +1, задающего смещение; – i-й вход нейрона j слоя q. (8.15) где f(•)-сигмоид, , (8.16) где хr – r-я компонента вектора входного образа. ШАГ 2. Рассчитать δ(Q) для выходного слоя по формуле (8.11). Рассчитать по формуле (8.12) или (8.13) изменения весов ∆w(Q) слоя Q (последнего слоя). ШАГ 3. Рассчитать по формулам (8.10) и (8.12) соответственно δ(Q) и ∆w(Q) для всех остальных слоев, q = (Q – 1)…1. ШАГ 4. Скорректировать все веса в нейронной сети: (8.17) ШАГ 5. Если ошибка сети существенна, перейти на шаг 1. В противном случае – конец. Сети на шаге 1 попеременно в случайном порядке предъявляются все тренировочные образы, чтобы сеть, образно говоря, не забывала одни по мере запоминания других. Из выражения (8.12) следует, что когда выходное значение стремится к нулю, эффективность обучения заметно снижается. При двоичных входных векторах в среднем половина весовых коэффициентов не будет корректироваться, поэтому область возможных значений выходов нейронов (0, 1) желательно сдвинуть в пределы (-0,5, 0,5), что достигается простыми модификациями логистических функций. Например, сигмоид с экспонентой преобразуется к виду: (8.18) Рассмотрим вопрос о емкости нейронной сети, т.е. числа образов, предъявляемых на ее входы, которые она способна научиться распознавать. Для сетей с числом слоев больше двух этот вопрос остается открытым. Для сетей с двумя слоями детерминистская емкость сети Cd оценивается следующим образом: (8.19) где Lw - число подстраиваемых весов, т - число нейронов в выходном слое. Данное выражение получено с учетом некоторых ограничений. Во-первых, число входов n и нейронов в скрытом слое L должно удовлетворять неравенству (n+L) > m. Во-вторых, Lw/m > 1000. Однако приведенная оценка выполнена для сетей с пороговыми активационными функциями нейронов, а емкость сетей с гладкими активационными функциями, например (8.18), обычно больше. Кроме того, термин детерминистский означает, что полученная оценка емкости подходит для всех входных образов, которые могут быть представлены n входами. В действительности распределение входных образов, как правило, обладает некоторой регулярностью, что позволяет нейронной сети проводить обобщение и, таким образом, увеличивать реальную емкость. Так как распределение образов, в общем случае, заранее неизвестно, можно говорить о реальной емкости только предположительно, но обычно она раза в два превышает детерминистскую емкость. Проблема локального минимума. Рассматриваемая нейронная сеть имеет несколько «узких мест». Во-первых, в процессе большие положительные или отрицательные значения весов могут сместить рабочую точку на сигмоидах нейронов в область насыщения. Малые величины производной от логистической функции приведут в соответствии с (8.10) и (8.12) к остановке обучения, что парализует сеть (). Во-вторых, применение метода градиентного спуска не гарантирует нахождения глобального минимума целевой функции (в данном случае – функции ошибки). Находя на функции ошибки минимум, обучение останавливается. Но этот минимум по своему значению может быть слишком велик. Например, необходима ошибка в 0.01, а обучение остановилось на ошибке 0.1. Нужно искать глобальный минимум. Это тесно связано вопросом выбора скорости обучения. Приращения весов и, следовательно, скорость обучения для нахождения экстремума должны быть бесконечно малыми, однако в этом случае обучение будет происходить неприемлемо медленно, и с другой стороны, слишком большие коррекции весов могут привести к постоянной неустойчивости процесса обучения. Поэтому в качестве коэффициента скорости обучения η обычно выбирается число меньше 1 (например, 0,1), которое постепенно уменьшается в процессе обучения. Кроме того, для исключения случайных попаданий сети в локальные минимумы иногда, после стабилизации значений весовых коэффициентов, η кратковременно значительно увеличивают, чтобы начать градиентный спуск из новой точки. Если повторение этой процедуры несколько раз приведет сеть в одно и то же состояние, можно предположить, что найден глобальный минимум. Обобщение и переобучение Рассмотрим проблемы обобщения и переобучения нейронной сети более подробно. Обобщение – это способность нейронной сети делать точный прогноз на данных, не принадлежащих исходному обучающему множеству. Переобучение же представляет собой чрезмерно точную подгонку, которая имеет место, если алгоритм обучения работает слишком долго, а сеть слишком сложна для такой задачи или для имеющегося объема данных Продемонстрируем проблемы обобщения и переобучения на примере аппроксимации некоторой зависимости не нейронной сетью, а посредством полиномов, при этом суть явления будет абсолютно та же. Графики полиномов могут иметь различную форму, причем, чем выше степень и число членов, тем более сложной может быть эта форма. Для исходных данных можно подобрать полиномиальную кривую (модель) и получить, таким образом, объяснение имеющейся зависимости. Данные могут быть зашумлены, поэтому нельзя считать, что лучшая модель в точности проходит через все имеющиеся точки. Полином низкого порядка может лучше объяснять имеющуюся зависимость, однако, быть недостаточно гибким средством для аппроксимации данных, в то время как полином высокого порядка может оказаться чересчур гибким, но будет точно следовать данным, принимая при этом замысловатую форму, не имеющую никакого отношения к настоящей зависимости. Емкость сети Вопрос о емкости нейронной сети тесно связан с вопросом о требуемой мощности выходного слоя сети, выполняющего окончательную классификацию образов. Например, для разделения множества входных образов по двум классам достаточно одного выходного нейрона. При этом каждый логический уровень («1» и «0») будет обозначать отдельный класс. На двух выходных нейронах с пороговой функцией активации можно закодировать уже четыре класса. Для повышения достоверности классификации желательно ввести избыточность, путем выделения каждому классу одного нейрона в выходном слое или, что еще лучше, нескольких, каждый из которых обучается определять принадлежность образа к классу со своей степенью достоверности, например, высокой, средней и низкой. Такие нейронные сети позволяют проводить классификацию входных образов, объединенных в нечеткие (размытые или пересекающиеся) множества. Это свойство приближает подобные сети к реальным условиям функционирования биологических нейронных сетей. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ НЕЙРОСЕТЕВЫХ ТЕХНОЛОГИЙ Применение нейросетевых технологий целесообразно при решении задач, имеющих следующие признаки: • отсутствие алгоритмов решения задач при наличии достаточно большого числа примеров; • наличие большого объема входной информации, характеризующей исследуемую проблему; • зашумленность, частичная противоречивость, неполнота или избыточность исходных данных. Нейросетевые технологии нашли широкое применение в таких направлениях, как распознавание печатного текста, контроль качества продукции на производстве, идентификация событий в ускорителях частиц, разведка нефти, борьба с наркотиками, медицинские и военные приложения, управление и оптимизация, финансовый анализ, прогнозирование и др. В сфере экономики нейросетевые технологии могут использоваться для классификации и анализа временных рядов путем аппроксимации сложных нелинейных функций. Экспериментально установлено, что модели нейронных сетей обеспечивают большую точность при выявлении нелинейных закономерностей на фондовом рынке по сравнению с регрессионными моделями. Рассмотрим решение задачи прогнозирования цены закрытия на завтра по акциям некоторого предприятия X. Для моделирования воспользуемся данными наблюдений за месяц. В качестве исходных данных можно использовать индикаторы Dow Jones, NIKKEI, FTSE100, индексы и акции российских компаний, «сезонные» переменные и др. Относительный показатель однодневной доходности предприятия можно определить из соотношений: (8.20) где ∆Pi – оценка операции «вчера купил, сегодня продал»; -∆Pi – оценка операции «вчера продал, сегодня купил»; Рi – значение выбранного показателя доходности в i-й день; Pi-1 – значение показателя в (i-1)-й день. Итоговая доходность за установленный интервал времени (n дней) рассчитывается по формуле (8.21) Результаты оценки доходности предприятия с использованием различных моделей ИНС, а также доходов «идеального» трейдера приведены ниже. Индикаторы Доходность 30 дней Стандартная трехслойная сеть …………………………………. 0,1919 Стандартная четырехслойная сеть …………………………….. -0,1182 Рекуррентная сеть с обратной отрицательной связью от скрытого слоя ………………………………………… 0,1378 Рекуррентная сеть с отрицательной обратной связью ……….. 0,4545 Сеть Ворда: с тремя скрытыми блоками, с разными передаточными функциями…………………. 0,2656 Трехслойная сеть с обходным соединением …………………. -0,1889 Четырехслойная сеть с обходными соединениями …………… 0,0003 Сеть с общей регрессией ...……………………………………... 0,3835 Сеть метода группового учета аргументов …………………… 0,1065 Сеть Ворда: с тремя скрытыми блоками, с разными передаточными функциями, с обходным соединением………. -0,1166 «Идеальный» трейдер …………………………………………… 1,1448 «Идеальный трейдер» знает цену закрытия на следующий день и поэтому получает максимально возможную прибыль. Трейдер пользуется значением нейросетевого индикатора следующим образом: на основе прогнозируемого в (i-1-й) день значения ∆Pi (величина относительно изменения цены закрытия по акциям рассматриваемого предприятия X на завтрашний i-й день) трейдер принимает решение о покупке (∆Pi >0) или продаже (∆Pi <0) акций. Анализ результатов моделирования показывает, что лучшую доходность обеспечила рекуррентная сеть с отрицательной обратной связью (45% за 30 дней). Динамика изменения однодневных показателей доходности, полученных с помощью этой ИНС, приведена на рис.8.5. Нейросетевые технологии активно используются в маркетинге для моделирования поведения клиентов и распределения долей рынка. Нейросетевые технологии позволяют отыскивать в маркетинговых базах данных скрытые закономерности. Моделирование поведения клиентов позволяет определить характеристики людей, которые будут нужным образом реагировать на рекламу и совершать покупки определенного товара или услуги. Сегментирование и моделирование рынков на основе нейросетевых технологий дает возможность построения гибких классификационных систем, способных осуществлять сегментирование рынков с учетом многообразия факторов и особенностей каждого клиента. Технологии ИНС имеют хорошие перспективы при решении задач имитации и предсказания поведенческих характеристик менеджеров и задач прогнозирования рисков при выдаче кредитов. Не менее актуально применение ИНС при выборе клиентов для ипотечного кредитования, предсказания банкротства клиентов банка, определения мошеннических сделок при использовании кредитных карточек, составления рейтингов клиентов при займах с фиксированными платежами и т.п. Следует помнить о том, что применение нейросетевых технологий не всегда возможно и сопряжено с определенными проблемами и недостатками. 1. Необходимо как минимум 50, а лучше 100 наблюдений для создания приемлемой модели. Это достаточно большое число данных, и они далеко не всегда доступны. Например, при производстве сезонного товара истории предыдущих сезонов недостаточно для прогноза на текущий сезон из-за изменения стиля продукта, политики продаж и т.д. Даже при прогнозировании спроса на достаточно стабильный продукт на основе информации о ежемесячных продажах трудно накопить исторические данные за период от 50 до 100 месяцев. Для сезонных товаров проблема еще более сложна, так как каждый сезон фактически представляет собой одно наблюдение. При дефиците информации модели ИНС строят в условиях неполных данных, а затем проводят их последовательное уточнение. 2. Построение нейронных сетей требует значительных затрат труда и времени для получения удовлетворительной модели. Необходимо учитывать, что излишне высокая точность, полученная на обучающей выборке, может обернуться неустойчивостью результатов на тестовой выборке – в этом случае происходит «переобучение» сети. Чем лучше система адаптирована к конкретным условиям, тем меньше она способна к обобщению и экстраполяции и тем скорее может оказаться неработоспособной при изменении этих условий. Расширение объема обучающей выборки позволяет добиться большей устойчивости, но за счет увеличения времени обучения. 3. При обучении нейронных сетей могут возникать «ловушки», связанные с попаданием в локальные минимумы. Детерминированный алгоритм обучения не в силах обнаружить глобальный экстремум или покинуть локальный минимум. Одним из приемов, который позволяет обходить ловушки, является расширение размерности пространства весов за счет увеличения числа нейронов скрытых слоев. Некоторые возможности для решения этой проблемы открывают стохастические методы обучения. При модификации весов сети только на основе информации о направлении вектора градиента целевой функции в пространстве весов можно достичь локального минимума, но невозможно выйти из него, поскольку в точке экстремума «движущая сила» (градиент) обращается в нуль и причина движения исчезает. Чтобы покинуть локальный экстремум и перейти к поиску глобального, нужно создать дополнительную силу, которая будет зависеть не от градиента целевой функции, а от каких-то других факторов. Один из простейших методов состоит в том, чтобы просто создать случайную силу и добавить ее к детерминистической. 4. Сигмоидальный характер передаточной функции нейрона является причиной того, что если в процессе обучения несколько весовых коэффициентов стали слишком большими, то нейрон попадает на горизонтальный участок функции в область насыщения. При этом изменения других весов, даже достаточно большие, практически не сказываются на величине выходного сигнала такого нейрона, а значит, и на величине целевой функции. 5. Неудачный выбор диапазона входных переменных – достаточно элементарная, но часто совершаемая ошибка. Если xi – двоичная переменная со значениями 0 и 1, то примерно в половине случаев она будет иметь нулевое значение: xi = 0. Поскольку xi входит в выражение для модификации веса в виде сомножителя, то эффект будет тот же, что и при насыщении: модификация соответствующих весов будет блокирована. Правильный диапазон для входных переменных должен быть симметричным, например от +1 до -1. 6. Процесс решения задач нейронной сетью является «непрозрачным» для пользователя, что может вызывать с его стороны недоверие к прогнозирующим способностям сети. 7. Предсказывающая способность сети существенно снижается, если поступающие на вход факты (данные) имеют значительные отличия от примеров, на которых обучалась сеть. Этот недостаток ярко проявляется при решении задач экономического прогнозирования, в частности при определении тенденций котировок ценных бумаг и стоимости валют на фондовых и финансовых рынках. 8. Отсутствуют теоретически обоснованные правила конструирования и эффективного обучения нейронных сетей. Этот недостаток приводит, в частности, к потере нейронными сетями способности обобщать данные предметной области в состояниях переобучения (перетренировки). Лекция 9. Генетические алгоритмы Идея генетических алгоритмов была предложена Дж. Холландом в 70-х годах XX в, а их интенсивное развитие и практическая реализация для численных оптимизационных расчетов были инициированы Д. Гольдбергом. Эти алгоритмы имитируют процессы наследования свойств живыми организмами и генерируют последовательности новых векторов w, содержащие оптимизированные переменные: w = [w1, w2,...,wn]T. При этом выполняются операции трех видов: селекция, скрещивание и мутация. Генетический алгоритм — это поисковый алгоритм, основан­ный на природных механизмах селекции и генетики. Эти алго­ритмы обеспечивают выживание сильнейших решений из мно­жества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции реше­ний. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фраг­менты исходных решений, к которым добавляются новые эле­менты, обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генети­ческие алгоритмы используют информацию, накопленную в процессе эволюции. Основные понятия генетических алгоритмов При описании генетических алгоритмов используются определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, аллель. Также используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура. Популяция – это конечное множество особей. Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированными в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами. Хромосомы (другие названия – цепочки или кодовые последовательности) – это упорядоченные последовательности генов. Ген (также называемый свойством, знаком или детектором) – это атомарный элемент генотипа, в частности, хромосомы. Генотип или структура – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы). Фенотип – это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска). Аллель – это значение конкретного гена, также определяемое как значение свойства или вариант свойства. Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов – это локи. Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр – стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации. Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков». Пример 9.1 Рассмотрим функцию (9.1) и допустим, что х принимает целые значения из интервала от 0 до 15. Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 16 точек со значениями 0, 1.....15 для обнаружения той точки, в которой функция принимает максимальное (или минимальное) значение. В этом случае в качестве параметра задачи выступает переменная х. Множество {0, 1, ..., 15} составляет пространство поиска и одновременно – множество потенциальных решений задачи. Каждое из 16 чисел, принадлежащих к этому множеству, называется точкой пространства поиска, решением, значением параметра, фенотипом. Следует отметить, что решение, оптимизирующее функцию, называется наилучшим или оптимальным решением. Значения параметра х от 0 до 15 можно закодировать следующим образом: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Это широко известный способ двоичного кодирования, связанный с записью десятичных цифр в двоичной системе. Представленные кодовые последовательности также называются цепями или хромосомами. В рассматриваемом примере они выступают и в роли генотипов. Каждая из хромосом состоит из 4 генов (иначе можно сказать, что двоичные последовательности состоят из 4 битов). Значение гена в конкретной позиции называется аллелью, принимающей в данном случае значения 0 или 1. Популяция состоит из особей, выбираемых среди этих 16 хромосом. Примером популяции с численностью, равной 6, может быть, например, множество хромосом {0010, 0101, 0111, 1001, 1100, 1110}, представляющих собой закодированную форму следующих фенотипов: {2, 5, 7, 9, 12, 14}. Функция приспособленности в этом примере задается выражением (6.l). Приспособленность отдельных хромосом в популяции определяется значением этой функции для значений х, соответствующих этим хромосомам, т.е. для фенотипов, соответствующих определенным генотипам. При разработке генетических алгоритмов преследуются две главные цели: • абстрактное и формальное объяснение процессов адапта­ции в естественных системах; • проектирование искусственных программных систем, вос­производящих механизмы функционирования естественных систем. Основные отличия ГА от других алгоритмов оптимизации: • используются не параметры, а закодированныя множества параметров; • поиск осуществляется не из единственной точки, а из попу­ляции точек; • в процессе поиска используются значения целевой функ­ции, а не ее приращения; • применяются вероятностные, а не детерминированные пра­вила поиска и генерации решений; • выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение но­вых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций. Классический генетический алгоритм Основной (классический) генетический алгоритм (также назы­ваемый элементарным или простым генетическим алгоритмом) со­стоит из следующих шагов: 1) инициализация, или выбор исходной популяции хромосом; 2) оценка приспособленности хромосом в популяции; 3) проверка условия остановки алгоритма; 4) селекция хромосом; 5) применение генетических операторов; 6) формирование новой популяции; 7) выбор «наилучшей» хромосомы. Блок-схема основного генетического алгоритма изображена на рис.9.1. Рассмотрим конкретные этапы этого алгоритма более по­дробно. Инициализация, т.е. формирование исходной популяции, заключается в случайном выборе заданного количества хромосом (особей), представляемых двоичными последовательностями фиксированной длины. Рис. 9.1. Блок-схема генетического алгоритма Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «качество» хромосомы. Форма функции приспособленности зависит от характера решаемой задачи. Предполагается, что функция приспособленности всегда принимает неотрицательные значения и, кроме того, что для решения оптимизационной задачи требуется максимизировать эту функцию. Если исходная форма функции приспособленности не удовлетворяет этим условиям, то выполняется соответствующее преобразование (например, задачу минимизации функции можно легко свести к задаче максимизации). Проверка условия остановки алгоритма. Определение условия остановки генетического алгоритма зависит от его конкретного применения. В оптимизационных задачах, если известно максимальное (или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно – с заданной точностью. Остановка алгоритма также может произойти в случае, когда его выполнение не приводит к улучшению уже достигнутого значения. Алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций. Если условие остановки выполнено, то производится переход к завершающему этапу выбора «наилучшей» хромосомы. В противном случае на следующем шаге выполняется селекция. Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой chi для i = 1, 2, .... N (где N обозначает численность популяции) соответствует сектор колеса v(chi), выраженный в процентах согласно формуле (9.2) где (9.3) причем F(chi) – значение функции приспособленности хромосомы chi, a ps(chi) – вероятность селекции хромосомы chi. Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала [а, b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что 0 ≤ а < b ≤ 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса. Существуют и другие методы проведения селекции: турнирный метод, ранговая селекция и др. В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью N, равной численности текущей популяции. Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской по­пуляции. В классическом генетическом алгоритме применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация – достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно 0,5 ≤ рс ≤ 1), тогда как вероятность мутации устанавливается весьма малой (чаще всего 0 ≤ рт ≤ 0,1). Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко. В генетическом алгоритме мутация хромосом может выполняться на популяции родителей перед скрещиванием либо на популяции потомков, образованных в результате скрещивания. 1. Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания рс. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из L генов, то очевидно, что точка скрещивания lk представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L-1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков: 1) потомок, хромосома которого на позициях от 1 до lk состоит из генов первого родителя, а на позициях от lk + 1 до L – из генов второго родителя; 2) потомок, хромосома которого на позициях от 1 до lk состоит из генов второго родителя, а на позициях от lk + 1 до L – из генов первого родителя. 2. Оператор мутации с вероятностью рт изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Например, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0, что приводит к образованию хромосомы [100110001010]. Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность рт мутации может эмулироваться, например, случайным выбором числа из интервала [0, 1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению рт. Формирование новой популяции. Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности, либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков, имеющей ту же численность. Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности. В завершение следует признать, что генетические алгоритмы унаследовали свойства естественного эволюционного процесса, состоящие в генетических изменениях популяций организмов с течением времени. Главный фактор эволюции – это естественный отбор (т.е. природная селекция), который приводит к тому, что среди генетически различающихся особей одной и той же популяции выживают и оставляют потомство только наиболее приспособленные к окружающей среде. В генетических алгоритмах также выделяется этап селекции, на котором из текущей популяции выбираются и включаются в родительскую популяцию особи, имеющие наибольшие значения функции приспособленности. На следующем этапе, который иногда называется эволюцией, применяются генетические операторы скрещивания и мутации, выполняющие рекомбинацию генов в хромосомах. Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности рс. Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью N, то рс = 2/N. Аналогично, если из родительской популяции численностью N выбирается 2z хромосом (z ≤ N/2), которые образуют z пар родителей, то рс = 2z/N. Обратим внимание, что если все хромосомы текущей популяции объединены в пары до скрещивания, то рс = 1. После операции скрещивания родители в родительской популяции замещаются их потомками. Операция мутации изменяет значения генов в хромосомах с за­данной вероятностью рт способом, представленным при описании соответствующего оператора. Это приводит к инвертированию значений отобранных генов с 0 на 1 и обратно. Значение рт, как правило, очень мало, поэтому мутации подвергается лишь небольшое количество генов. Скрещивание – это ключевой оператор генетических алгоритмов, определяющий их возможности и эффективность. Мутация играет более ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания. Основной (классический) генетический алгоритм известен в литературе в качестве инструмента, в котором выделяются три вида операций: репродукции, скрещивания и мутации. Термины селекция и репродукция в данном контексте используются в качестве синонимов. При этом репродукция в данном случае связывается скорее с созданием копий хромосом родительского пула, тогда как более распространенное содержание этого понятия обозначает процесс формирования новых особей, происходящих от конкретных родителей. Если мы принимаем такое толкование, то операторы скрещивания и мутации могут считаться операторами репродукции, а селекция – отбором особей (хромосом) для репродукции. Иллюстрация выполнения классического генетического алгоритма Рассмотрим выполнение описанного в предыдущем разделе классического генетического алгоритма на как можно более простом примере. Проследим последовательность выполнения его этапов, соответствующих блок-схеме на рис.9.1. Пример 9.2 Рассмотрим сильно упрощенный и довольно искусственный пример, состоящий в нахождении хромосомы с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Посмотрим, как протекает процесс решения этой весьма тривиальной задачи с помощью генетического алгоритма. Инициализация, или выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной 12 битов. Это можно достигнуть, например, подбрасыванием монеты (96 раз, при выпадении «орла» приписывается значение 1, а в случае «решки» – 0). Таким образом, можно сформировать исходную популяцию сh1 = [111001100101] ch5 = [010001100100] ch2 = [001100111010] ch6 = [010011000101] ch3 = [011101110011] ch7 = [101011011011] ch4 = [001000101000] ch8 = [000010111100] Оценка приспособленности хромосом в популяции. В рассматриваемом упрощенном примере решается задача нахождения такой хромосомы, которая содержит наибольшее количество единиц. Поэтому функция приспособленности определяет количество единиц в хромосоме. Обозначим функцию приспособленности символом F. Тогда ее значения для каждой хромосомы из исходной популяции будут такие: F(ch1) = 7 F(ch5) = 4 F(ch2) = 6 F(ch6) = 5 F(ch3) = 8 F(ch7) = 8 F(ch4) = 3 F(ch8) = 5 Хромосомы ch3 и ch7 характеризуются наибольшими значениями функции принадлежности. В этой популяции они считаются наилучшими кандидатами на решение задачи. Если в соответствии с блок-схемой генетического алгоритма (рис.9.1) условие остановки алгоритма не выполняется, то на следующем шаге производится селекция хромосом из текущей популяции. Селекция хромосом. Селекция производится методом рулетки. На основании формул (9.2) и (9.3) для каждой из 8 хромосом текущей популяции (в нашем случае – исходной популяции, для N = 8) получаем секторы колеса рулетки, выраженные в процентах (рис.9.2). v(ch1) = 15,22 v(ch5) = 8,70 v(ch2) = 13,04 v(ch6) = 10,87 v(cn3) = 17,39 v(ch7) = 17,39 v(ch4) = 6,52 v(ch8) = 10,87 Рис. 9.2. Колесо рулетки для селекции в примере 6.4. Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел: 79 44 9 74 44 86 48 23 Это означает выбор хромосом ch7 ch3 ch1 ch7 ch3 ch7 ch4 ch2 Как видно, хромосома ch7 была выбрана трижды, а хромосома ch3 – дважды. Заметим, что именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана и хромосома ch4 с наименьшим значением функции приспособленности. Все выбранные таким образом хромосомы включаются в так называемый родительский пул. Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания рс = 1, а вероятность мутации рm = 0. Допустим, что из этих хромосом случайным образом сформированы пары родителей ch2 и ch7 ch1 и ch7 ch3 и ch4 ch3 и ch7 Для первой пары случайным образом выбрана точка скре­щивания lk = 4, для второй – lk = 3, для третьей – lk = 11, для четвертой – lk = 5. В результате выполнения оператора скрещивания получаются 4 пары потомков. Если бы при случайном подборе пар хромосом для скрещива­ния были объединены, например, ch3 с ch3 и ch4 с ch7 вместо ch3 с ch4 и ch3 с ch7, а другие пары остались без изменения, то скрещивание ch3 с ch3 дало бы две такие же хромосомы независимо от разыгранной точки скрещивания. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация наиболее вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию. Формирование новой популяции. После выполнения операции скрещивания мы получаем следующую популяцию потомков: Ch1 = [001111011011] Ch5 = [011101110010] Ch2 = [101000111010] Ch6 = [001000101001] Ch3 = [111011011011] Ch7 = [011101011011] Ch4 = [101001100101] Ch8 = [101011110011] Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с заглавной буквы С. Согласно блок-схеме генетического алгоритма (рис.9.1) производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей. Значения функций приспособленности хромосом этой попу­ляции составляют F(Ch1) = 8 F(Ch5) = 7 F(Ch2) = 6 F(Ch6) = 4 F(Ch3) = 9 F(Ch7) = 8 F(Ch4) = 6 F(Ch8) = 8 Заметно, что популяция потомков характеризуется гораздо более высоким средним значением функции приспособленности, чем популяция родителей. Обратим внимание, что в результате скрещивания получена хромосома Сh3 с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из родительской популяции. Однако могло произойти и обратное, поскольку после скрещивания на первой итерации хромосома, которая в родительской популяции характеризовалась наибольшим значением функции приспособленности, могла просто «потеряться». Помимо этого «средняя» приспособленность новой популяции все равно оказалась бы выше предыдущей, а хромосомы с большими значениями функции приспособленности имели бы шансы появиться в следующих поколениях. ПРИМЕРЫ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Генетические алгоритмы нашли широкое практическое применение в менеджменте и управлении для решения задач поиска оптимальных решений, формирования моделей и прогнозирования значений различных показателей. Они осуществляют поиск лучших решений на основе заданной целевой функции. Значение целевой функции для многих задач весьма непросто вычислить, поэтому в ряде случаев при исследовании плохо обусловленных проблем с этой целью применяются нейронные сети, позволяющие найти решение при отсутствии явной модели. Кроме того, для вычисления целевых функций в условиях неопределенности применяются статистические методы и методы логического вывода в четкой или нечеткой среде. Формирование системы прогнозирующих правил. Генетические алгоритмы могут использоваться для нахождения оптимального набора правил, позволяющих прогнозировать страховые риски с учетом ряда определяющих его факторов. Для решения этой задачи необходимо иметь базу данных, содержащую фактические значения переменных, влияющих на страховой риск. Рассмотрим пример использования генетического алгоритма. Для оптимизации экспертных правил в сфере страхования. Допустим, что компания, занимающаяся страхованием автомобилей, использует базу данных, которая помимо прочих включает следующие факторы: максимальную скорость автомобиля (км/час), возраст автомобиля (лет), возраст водителя (лет) и риск, определенный экспертно по некоторой шкале на основе анализа обращений клиентов о выплате компенсации по страховым случаям. Правила, задающие оценку страхового риска, сконструированы в виде: ЕСЛИ максимальная скорость автомобиля лежит в диапазоне [Ai] И возрастной диапазон автомобиля [Bi] И возраст водителя находится в диапазоне [Сi], ТО страховой риск имеет значение [Di]. Для конкретной выборки из БД это правило может иметь следующий вид: ЕСЛИ максимальная скорость [91 − 100 км/час] И возраст автомобиля [11 − 15 лет] И возраст водителя [31 − 40 лет], ТО риск [3]. Здесь уровень риска отображается на интервал [1, 5], при этом высокие значения соответствуют большим страховым рискам. Подобные правила, основанные на фактических значениях переменных, случайным образом выбранных из БД, составляют исходную популяцию. Для каждой из переменных, входящих в популяцию, предварительно задается диапазон состояний. Например, переменная «возраст автомобиля», может иметь пять возможных состояний: 1 − 5, 6 − 10, 11 − 15, 16 − 20, 21 − 25 лет. Далее сформированная популяция обрабатывается генетическими операторами с учетом специфики рассматриваемой задачи. Целевая функция должна показывать, насколько точно сгенерированные правила описывают реальные страховые случаи, хранящиеся в БД. Например, если какое-то правило описывает 4 случая из 5, то значение целевой функции будет 4/5, или 80%. Новые члены популяции образуются в результате скрещивания и мутации начального набора правил. В данном случае при скрещивании двух правил происходит обмен парами «атрибут − значение» на участке строки после точки кроссинговера. В результате образуются два новых правила, жизнеспособность которых оценивается по тому, насколько удачно они описывают страховые случаи, которые имели место в прошлом. Мутация правил обеспечивает необходимое разнообразие признаков и заключается в изменении значений атрибутов с заданной вероятностью. Таким образом, первоначально сформированный набор правил преобразуется случайно направленным способом в другой набор, который лучше остальных описывает накопленную статистику страховых случаев. Результирующая система правил в дальнейшем используется для прогнозирования страховых рисков. Следует отметить, что подобный подход к формированию системы правил может приводить к некорректным правилам продукций. В то же время он освобождает разработчиков и экспертов от трудоемкой работы по формулированию и оценке правил, так как некорректные результаты отбрасываются при сопоставлении сгенерированных продукций с реальными страховыми ситуациями. Привлечение прошлого опыта для оценки пригодности прогнозирующих правил не позволяет предвидеть новые ситуации, которые не имели места в прошлом. Поэтому при решении задач описанным способом очень важно следить за своевременным пополнением и модификацией информации в БД, которая отражает появление новых фактов, атрибутов и тенденций. Классифицирующие системы. На основе генетических алгоритмов Дж.Холланд предложил классифицирующие системы, которые можно использовать для целей управления. Классифицирующая система состоит из трех вложенных друг в друга подсистем (рис.9.3): классификатора, системы обучения и генетического алгоритма. В классификатор поступают внешние сообщения и положительные оценки (поощрения) его действий. Классификатор содержит правила вида ЕСЛИ <условие>, ТО <сообщение>, с помощью которых формируются выходные сообщения. Обучающая система выполняет оценку используемых правил. Генетический алгоритм предназначен для случайно направленной модификации правил. Схема обработки правил представлена на рис.9.4. Каждому правилу приписывается численная оценка силы правила. Сообщения и условные части правил (антецеденты) формулируются в одних и тех же терминах. Список сообщений содержит все текущие сообщения − поступающие из внешней среды и те, что формируются внутри системы. В процессе работы КС все сообщения из списка сравниваются с условиями всех правил. Классификатор выполняет следующие действия. Рис. 9.3. Схема классифицирующей системы Шаг 1. В список сообщений (рабочую память) добавляются, все сообщения, поступившие извне. Шаг 2. Проводится сравнение всех сообщений из списка с антецедентами всех правил. Все правила, антецеденты которых совпадают с присутствующими в рабочей памяти сообщениями, записываются в список правил М. Шаг 3. Выполняются правила из списка М, при этом сообщения каждого правила посылаются в список новых сообщений. Шаг 4. Обновление списка сообщений. Шаг 5. Сообщения из списка посылаются в выходной интерфейс. Вероятность выдачи сообщения зависит от силы правила: не каждое сообщение выдается на управляемый объект, часть их может быть связана с изменением внутренней структуры системы (правил). Шаг 6. Возврат к шагу 1. Рис. 9.4. Схема обработки правил в классифицирующей системе В процессе обучения каждому правилу присваивается численное значение силы, а алгоритм обучения регулирует это значение с учетом полезности правила для системы. На шаге 3 описанного алгоритма для каждого отобранного правила С вычисляется цена по формуле В(С, t)=bR(C)s(С, t), где s(C, t) − сила правила С в момент t; R(С) − специфичность условия в правиле, равная числу символов, отличающихся от символа * в условии, деленному на длину условия; b − коэффициент, который обычно принимают равным 1/8 или 1/6. Цена В определяет вероятность того, что правило пошлет сообщение в список новых сообщений. Вероятностный подход позволяет аутсайдерам тоже изредка посылать сообщения, что при благоприятных условиях может сделать их лидерами. Послать сообщение могут все правила с допустимым значением В, т.е. такие, у которых В превышает определенный порог. Правило, пославшее сообщение в новый список, расплачивается за это уменьшением своей силы: s(C,t + 1) = s(C,t) − B(C,t). Для правил С, пославших сообщения, которые на следующем шаге работы оказались полезными (совпали с условиями правила-победителя, имеющего высокую цену), оценка силы возрастает на долю В: s(C', t + 1) = s(C,t) + aB(C,t), где a = 1/К, К − число правил С', т.е. каждый поставщик получает равную долю В. Правило полезно только тогда, когда его потребители в своих локальных действиях тоже получают выигрыш. В противном случае правило обесценивается, так как его цена s уменьшается при отсылке сообщения. В свою очередь, полезность потребителей зависит от их потребителей и т.д. Цепочка приводит к конечным потребителям, достигающим цели и получающим поощрения от внешней среды. Классификатор и обучающая система не порождают новых правил. Эту функцию выполняет генетический алгоритм, который работает с учетом силы правил, определенной в системе обучения. Работа генетического алгоритма рассмотрена в предшествующем примере. Комбинированные методы и интеллектуальные системы. В настоящее время активно развиваются методы, основанные на объединении технологий инженерии знаний и генетических алгоритмов. В области ГА разрабатываются операторы, ориентированные на обработку знаний. Генетические алгоритмы используют в теории нечетких систем для настройки параметров функций принадлежности. Интеграция четких и нечетких нейронных сетей и генетических алгоритмов обеспечивает реализацию оптимизационной задачи. Средства fuzzy-neuro-genetic используются в интеллектуальных системах и содержат следующие процедуры: • преобразование входных примеров в нечеткое представление; • извлечение знаний, представленных в виде продукций ЕСЛИ-ТО, из нечеткой обучающей выборки с помощью нейронной сети; • оптимизацию структуры продукционных правил с помощью генетического алгоритма. Активно развивается направление, ориентированное на использование генетических алгоритмов для обучения нейронных сетей и корректировки структуры уже обученной сети. В отличие от метода обратного распространения ошибки генетические алгоритмы мало чувствительны к архитектуре сети. Напомним, что основными характеристиками нейронной сети являются следующие: • HLN − количество скрытых слоев; • Nk − число нейронов в каждом слое; • wij − весовые коэффициенты межнейронных связей; • Fj(X, W) − передаточные функции нейронов скрытых слоев, а также нейронов выходного слоя. Сформулируем общую задачу оптимизации сети: при заданных количествах входных и выходных нейронов на основе заданного множества обучающих примеров определить оптимальное значение HLN, Nk, k = I,..., HLN, значения всех весовых коэффициентов межнейронных связей wij, где j − индекс нейрона; i − индекс межнейронной связи (синапса), Fj(X, W) − передаточные функции всех нейронов, за исключением нейронов входного слоя. Критерием оптимизации является максимальное отклонение выходного вектора сети Y' от эталонного значения выхода, полученное в результате обработки всех примеров, т.е. необходимо найти (9.4) где δ = Y' − Y; Q − множество обучающих примеров, содержащих значения X, Y; Y' = F(HLN, Nk, X, W); F(HLN, Nk, X,W) − передаточная функция ИНС, которая строится на основе частных функций отдельных нейронов Fj(X, W). Даже для простых сетей эта задача является очень сложной, поэтому для ее решения применяется декомпозиция, т.е. сеть оптимизируется в процессе последовательного решения частных задач оптимизации. Например, на первом шаге подбираются оптимальные значения HLN и Nk, затем определяется оптимальный вид передаточных функций нейронов, а на конечной стадии подбираются веса межнейронных связей. Генетические алгоритмы чаще всего применяются для улучшения характеристик ИНС, уже созданных и обученных с применением других методов. Лекция 10. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АГЕНТОВ Интеллектуальные мультиагентные системы – одно из новых перспективных направлений искусственного интеллекта, которое сформировалось на основе результатов исследований в области распределенных компьютерных систем, сетевых технологий решения проблем и параллельных вычислений. В мультиагентных технологиях заложен принцип автономности отдельных частей программы (агентов), совместно функционирующих в распределенной системе, где одновременно протекает множество взаимосвязанных процессов. Под агентом подразумевают автономный искусственный объект (компьютерную программу), обладающий активным мотивированным поведением и способный к взаимодействию с другими объектами в динамических виртуальных средах. Каждый агент может принимать сообщения, интерпретировать их содержание и формировать новые сообщения, которые либо передаются на «доску объявлений», либо направляются другим агентам. Агентно-ориентированный подход уже нашел применение в таких областях, как распределенное решение сложных задач, реинжиниринг предприятий, электронный бизнес и т.п. Важной областью применения мультиагентных технологий является моделирование. В этой области Д.А.Поспелов выделяет два класса задач. К первому классу он относит задачи распределенного управления и задачи планирования достижения целей, где усилия разных агентов направлены на решение общей проблемы и необходимо обеспечение эффективного способа кооперации их деятельности. В задачах второго класса агенты самостоятельно решают свои локальные задачи, используя общие, как правило, ограниченные ресурсы. Понятие агент соответствует аппаратно или программно реализованной сущности, которая способна действовать в интересах достижения целей, поставленных перед ней владельцем и/или пользователем. В мультиагентных системах (MAC) множество автономных агентов действуют в интересах различных пользователей и взаимодействуют между собой в процессе решения определенных задач. Примерами таких задач являются: управление информационными потоками и сетями, управление воздушным движением, поиск информации в сети Интернет, электронная коммерция, обучение, электронные библиотеки, коллективное принятие многокритериальных управленческих решений и другие. Идея мультиагентных систем появилась в конце 1950-х гг. в научной школе М.Л.Цетлина, которая занималась исследованиями коллективного поведения автоматов. Агентами (маленькими животными) были названы искусственные существа, обладающие свойством реактивности, т.е. способные воспринимать и интерпретировать сигналы, поступающие из внешней среды, и формировать ответные сигналы. В роли маленьких животных выступали конечные автоматы, которые не имели априорных знаний о свойствах окружающей среды и о наличии в ней других существ. Единственным знанием, которым они обладали, была цель их деятельности и способность оценивать поступающие сигналы относительно достижения этой цели. Оказалось, что даже такие простые структуры, как конечные автоматы, демонстрируют хорошие способности к адаптации в стационарных вероятностных средах. Одной из главных характеристик агентов-автоматов была рациональность, которая определялась как сумма положительных откликов среды, накопленных агентом за некоторый период его существования. В дальнейших исследованиях структура маленьких животных усложнялась. Сначала появились вероятностные автоматы с переменной структурой, адаптирующейся к характеристикам среды, затем появились агенты, способные изменять свои реакции на основании предыстории и анализа состояния окружения. Серьезным шагом в развитии мультиагентных технологий стала реализация способности агентов к рассуждениям. Простейшие модели взаимодействия агентов предусматривали их общение через среду. При этом на каждом шаге функционирования агенты совершают выбор возможных для них действий. Множество действий всех агентов обусловливает распределение откликов среды для всех участников, которые могут его использовать либо не использовать при формировании своих ответных реакций. Новый шаг к современному пониманию агентов был сделан при переходе к коллективной работе в распределенных компьютерных системах. Этот шаг стал началом бурного развития мультиагентных технологий. К настоящему времени в данном направлении накоплен определенный опыт. Предложены разнообразные модели агентов и способы их реализации, решены практические задачи и созданы инструментальные средства для разработки мультиагентных систем, сформулированы различные принципы взаимодействия агентов и т.п. В этой главе мы остановимся на вопросах, связанных с построением и применением интеллектуальных MAC. Одна из возможных классификаций агентов приведена в табл.10.1, из которой следует, что для интеллектуальных агентов характерно целесообразное поведение, которое предполагает наличие у агента целей функционирования и способностей использовать знания об окружающей среде, партнерах и о своих возможностях. Таблица 10.1 Классификация агентов Признак Тип агента простой смышленый интеллектуальный действи­тельно интеллектуальный Автономность + + + Взаимодействие с другими агентами и/или пользователями + + + + Реактивность + + + + Способность использования абстракции + + + Адаптивное поведение + + + Обучение на основе взаимодействия с окружением + + Толерантность к ошибкам и/или неверным входным сигналам + Функционирование в режиме реального времени + Взаимодействие на естественном языке + Характеристики интеллектуальных агентов Интеллектуальным агентам присущи следующие основные свойства: • автономность – способность функционировать без вмешательства со стороны своего владельца и осуществлять контроль собственных действий и внутреннего состояния. Автономность предполагает относительную независимость агента от окружающей среды, т.е. наличие «свободы воли», обусловливающей собственное поведение, которое должно быть обеспечено необходимыми ресурсами; • активность – способность к организации и реализации действий; • общительность − взаимодействие и коммуникация с другими агентами; • реактивность − адекватное восприятие состояния среды и реакция на его изменение; • целенаправленность, предполагающая наличие собственных источников мотивации; • наличие базовых знаний о себе, о других агентах и об окружающей среде; • убеждения − переменная часть базовых знаний, меняющихся во времени; • желания − стремление к определенным состояниям; • намерения − действия, которые планируются агентом для выполнения своих обязательств и/или желаний; • обязательства − задачи, которые выполняет один агент по просьбе и/или поручению других агентов. Иногда к этому списку добавляются другие качества, в том числе: • правдивость − неспособность к подмене истинной информации заведомо ложной; • благожелательность − готовность к сотрудничеству с другими агентами в процессе решения собственных задач, что обычно предполагает отсутствие конфликтующих целей, поставленных перед агентами; • альтруизм − приоритетность общих целей по сравнению с личными; • мобильность − способность агента мигрировать по сети в поисках необходимой информации. В работе для классификации агентных программ используются два основных признака: 1) степень развития внутреннего представления о внешнем мире; 2) способ поведения. По первому признаку выделяются интеллектуальные (когнитивные, рассуждающие) и реактивные агенты. Интеллектуальные агенты обладают хорошо развитой и пополняемой символьной моделью внешнего мира благодаря наличию у них БЗ, механизмов рассуждения и анализа действий. Реактивные агенты не имеют развитого представления о внешней среде. Они не используют рассуждений и могут не иметь собственных ресурсов. Их поведение определяется целью, в соответствии с которой формируются реакции на предъявляемые ситуации. В связи с этим реактивные агенты не имеют внутренних источников мотивации и не способны планировать свои действия (реактивность в чистом виде − это обратная связь без прогноза). Архитектуры мультиагентных систем Интеллектуальная мультиагентная система представляет собой множество интеллектуальных агентов, распределенных в сети, которые мигрируют по ней в поисках релевантных данных, знаний, процедур и кооперируются для достижения поставленных перед ними целей. В зависимости от концепции, принятой при разработке MAC, возможны различные варианты ее архитектуры, среди которых выделяют три базовых типа: 1) архитектуры, основанные на методах работы со знаниями; 2) архитектуры, в которых используются поведенческие модели «стимул-реакция»; 3) гибридные архитектуры. В архитектурах первого типа для представления и обработки знаний используются традиционные модели, методы и средства искусственного интеллекта, а принятие решений осуществляется на основе механизмов формальных рассуждений. В самых первых системах такого типа для представления и обработки знаний использовалась логика предикатов первого порядка. Развитие исследований в этой области привело к появлению специальных расширений логических исчислений, ориентированных на учет таких свойств агентов, как убеждения, желания, намерения и обязательства. Основной недостаток архитектур первого типа − сложность или принципиальная невозможность построения достаточно полных баз знаний, которые являются необходимой частью создаваемых систем. В частности, интеллектуальный агент может иметь архитектуру типичной продукционной системы, которая способна воспринимать информацию из внешней среды и осуществлять те или иные действия в результате обработки этой информации. Главные отличия агентной программы от обычной продукционной ЭС связаны с наличием механизма формирования целей и модуля коммуникации, который обеспечивает взаимодействие с другими агентами. Агент с такой архитектурой способен к рассуждениям, но не способен к обучению. Адаптивное поведение агента позволяет реализовать архитектура на основе классифицирующих систем Дж.Холланда. Важнейшими отличиями классифицирующих систем от продукционных являются: 1) возможность формирования новых правил с применением генетического алгоритма; 2) наличие механизма поощрений. В архитектурах второго типа, которые называют реактивными, не используются традиционные для ИИ символьные модели представления знаний. Модели поведения агентов представлены либо наборами правил, которые позволяют выбрать действие, соответствующее ситуации, либо конечными автоматами, либо другими средствами, обеспечивающими формирование адекватных реакций агента на возникающие в системе стимулы. Системы этого типа, как правило, имеют высокую степень специализации и строгие ограничения на сложность решаемых задач. Наиболее перспективными считаются гибридные интеллектуальные мультиагентные системы, которые позволяют использовать возможности интеллектуальных и реактивных архитектур. Примером может служить архитектура с иерархической базой знаний, которая содержит структурированную БЗ, рабочую память, модуль управления коммуникацией и человеко-машинный интерфейс. Агент с подобной архитектурой обладает способностью к рассуждениям и к реактивному поведению. Его БЗ содержит три уровня: 1) знания предметной области; 2) знания о взаимодействии, которые позволяют принимать решения в условиях неопределенности; 3) управляющие знания. Интеллектуальное поведение агента обеспечивается способностью принимать решения, а реактивное − системой контроля за содержимым рабочей памяти, которая функционирует по принципу глобальной доски объявлений. Агент взаимодействует с пользователем, используя человеко-машинный интерфейс. В общем случае гибридные архитектуры являются многоуровневыми и отличаются друг от друга структурой и содержанием уровней, которые могут соответствовать различным уровням управления, абстракции либо отдельным функциональным свойствам агента. Одно из новых направлений − применение нейронных сетей для реализации MAC. Коннекционистские архитектуры (на основе ИНС) позволяют создавать самообучающихся агентов, знания которых формируются в процессе решения практических задач. Хорошие перспективы для реализации самообучающихся агентов имеют сети с обратными связями и нечеткие ИНС. Коллективное поведение агентов Главная черта MAC, отличающая их от других интеллектуальных систем, − взаимодействие между агентами. Взаимодействие означает установление двусторонних и многосторонних динамических отношений между субъектами. Оно является не только следствием деятельности агентов, но и необходимым условием формирования виртуальных сообществ. Взаимодействие − не просто связь между сосуществующими агентами, но и предпо­сылка для взаимных превращений самих агентов и отношений между ними. Главными характеристиками любого взаимодействия являются направленность, избирательность, интенсивность и динамичность. В контексте MAC эти понятия можно интерпретировать следующим образом: • направленность − положительная или отрицательная; кооперация или конкуренция; сотрудничество или конфронтация; координация или субординация и т. п.; • избирательность − взаимодействие происходит между агентами, которые каким-либо образом соответствуют друг другу и поставленной задаче. При этом агенты могут быть связаны в одном отношении и независимы − в другом; • интенсивность − взаимодействие между агентами не сводится к наличию или отсутствию, а характеризуется определенной силой; • динамичность − наличие, сила и направленность взаимодействий могут изменяться с течением времени. Общая проблема анализа взаимодействия между агентами включает следующие задачи: 1) идентификацию ситуации взаимодействия агентов; 2) выделение основных ролей и их распределение между агентами; 3) определение числа и типов взаимодействующих агентов; 4) построение формальной модели взаимодействия; 5) определение набора возможных стратегий поведения агентов; 6) формирование множества коммуникативных действий. Способы и причины взаимодействия между агентами К базовым видам взаимодействия между агентами относятся: • кооперация (сотрудничество); • конкуренция (конфронтация, конфликт); • компромисс (учет интересов других агентов); • конформизм (отказ от своих интересов в пользу других); • уклонение от взаимодействия. Интеллектуальные агенты сотрудничают с другими агентами «сознательно», преследуя при этом определенные цели. Кооперацию в сообществе реактивных агентов можно назвать непреднамеренной, поскольку она базируется на естественных реакциях отдельных агентов, направленных на выживание вида. Показатели выживания отражают способность особи или группы сохранять свою целостность при воздействиях факторов, которые могут ее разрушить. Кооперация между агентами может возникать на принудительных началах (директивная кооперация) или на основе добровольных отношений (ситуативная кооперация). Эти два вида сотрудничества часто представлены так называемой контрактной формой кооперации, когда взаимодействие агентов регламентируется набором формальных или неформальных соглашений между ними. Взаимодействие агентов обусловлено целым рядом причин, важнейшими среди которых являются следующие. Совместимость целей (общая цель). Эта причина обычно порождает взаимодействие по типу кооперации или сотрудничества. При этом следует выяснить, не ведет ли взаимодействие к снижению жизнеспособности отдельных агентов. Несовместимость целей или убеждений обычно порождает конфликты, позитивная роль которых заключается в стимулировании процессов развития. Известная модель хищник-жертва представляет собой пример одновременного взаимодействия по двум типам кооперация-конфронтация. Отношение к ресурсам. Ресурсами будем называть любые средства, используемые для достижения агентами своих целей. Задачи распределения долей рынка, затрат и прибылей совместных предприятий можно рассматривать как примеры взаимодействия, обусловленного общими ресурсами. Ограниченность ресурсов, которые используются многими агентами, обычно порождает конфликты. Одним их самых простых и эффективных способов разрешения подобных конфликтов является право сильного − сильный агент отбирает ресурсы у слабых. Более тонкие способы разрешения конфликтов обеспечивают переговоры, направленные на достижение компромиссов, в которых учитываются интересы всех агентов. Необходимость привлечения недостающего опыта. Каждый агент обладает ограниченным набором знаний, необходимых ему для реализации собственных и общих целей. В связи с этим ему приходится взаимодействовать с другими агентами. При этом возможны различные ситуации: а) агент способен выполнить задачу самостоятельно; б) агент может обойтись без посторонней помощи, но кооперация позволит решить задачу более эффективным способом; в) агент не способен решить задачу в одиночку. В зависимости от ситуации агенты выбирают тип взаимодействия и могут проявлять разную степень заинтересованности в сотрудничестве. Взаимные обязательства. Обязательства являются одним из инструментов, позволяющих упорядочить хаотические взаимодействия агентов. Они позволяют предвидеть поведение других агентов, прогнозировать будущее и планировать собственные действия. Можно выделить следующие группы обязательств: а) обязательства перед другими агентами; б) обязательства агента перед группой; в) обязательства группы перед агентом; г) обязательства агента перед самим собой. Формальное представление целей, обязательств, желаний и намерений, а также всех остальных характеристик составляет основу ментальной модели интеллектуального агента, которая обеспечивает его мотивированное поведение в автономном режиме. Перечисленные причины в различных сочетаниях могут приводить к разным формам взаимодействия между агентами, например: • простое сотрудничество, которое предполагает интеграцию опыта отдельных агентов (распределение задач, обмен знаниями и т.п.) без специальных мер по координации их действий; • координируемое сотрудничество, когда агенты вынуждены согласовывать свои действия (иногда привлекая специального агента-координатора) для того, чтобы эффективно использовать ресурсы и собственный опыт; • непродуктивное сотрудничество, когда агенты совместно используют ресурсы или решают общую проблему, не обмениваясь опытом и мешая друг другу (как лебедь, рак и щука в басне И.А.Крылова). Моделирование взаимодействия в мультиагентных системах Рассматривая проблему моделирования взаимодействия агентов друг с другом и с окружающей средой, Д.А.Поспелов выделил следующие основные признаки естественных систем, которые необходимо учитывать при моделировании виртуальных сред. 1. Конечность времени существования любого агента. Длительность жизни агента зависит от различных обстоятельств, в частности от поставленной перед ним задачи, от величины доступных ресурсов и т.п. 2. Использование механизма биологического отбора в моделях искусственной жизни. Естественный отбор эффективных агентов может осуществляться в адаптивных системах с использованием различных эволюционных механизмов (обучаемых нейронных сетей, генетических алгоритмов, автоматов с перестраиваемой структурой и т.д.). 3. Учет уровня организации сообщества агентов. Если модель описывает взаимодействие сложных организмов, имеющих социальную организацию, то помимо реактивности, активности и когнитивности (способность к рассуждениям) агенты приобретают еще одно свойство_– социальность. В таких моделях возникает необходимость учета социального статуса и социальных отношений. Распределение труда в обществе служит основой для выделения классов агентов, выполняющих специализированные функции, в том числе функции управления искусственной средой. Задача распределения функций приводит к необходимости реализации механизма социального отбора, который принципиально отличается от биологического принципа. Вопросы организации сообщества искусственных организмов по образу и подобию человеческого общества связывают теорию MAC с системным анализом, теорией организаций, теорией административного управления и т.п. Серьезной и пока не решенной проблемой является морально-этическая основа организации мультиагентных систем, связанная с формированием понятий об основных ценностях и нормах, принятых в обществе. Ориентация на модели нормативного поведения агентов вызывает дискуссии, так как наряду с нормативным в реальном обществе имеет место и ненормативное поведение. Коллективное поведение агентов в MAC предполагает кооперацию агентов при коллективном решении задач. В процессе работы мультиагентной системы агент может обращаться за помощью к другим агентам, если не в состоянии решить поставленную перед ним задачу самостоятельно. При этом агенты могут строить планы совместных действий, не только полагаясь на свои возможности, но анализируя планы и намерения других членов коллектива. Моделирование коллективного поведения необходимо также в случаях, когда агенты для решения своих задач используют общий ограниченный ресурс. Каждый агент вынужден учитывать наличие других агентов, а выбор стратегии действий одного агента обычно зависит от поведения остальных. Проблемы коллективного поведения рассматриваются в теории систем, в теории управления и в теории игр. Основной идеей системного анализа является применение декомпозиции исходной задачи на более простые, из решения которых может быть найдено решение задачи в целом. В мультиагентных системах идея декомпозиции воплотилась в принцип распределенного решения подзадач с их координацией для получения стратегии коллективного поведения. В процессе моделирования коллективной работы агентов возникает множество проблем: • распознавание необходимости кооперации; • выбор подходящих партнеров; • возможность учета интересов партнеров; • организация переговоров о совместных действиях; • формирование планов совместных действий; • синхронизация совместных действий; • декомпозиция задач и разделение обязанностей; • выявление конфликтующих целей; • конкуренция за совместные ресурсы; • формирование правил поведения в коллективе; • обучение поведению в коллективе и т. д. Особенностью коллективного поведения агентов является то, что их взаимодействие в процессе решения частных задач (или одной общей) порождает новое качество решения этих задач. При этом в моделях координации поведения агентов используются следующие основные идеи. 1. Отказ от поиска наилучшего решения в пользу «хорошего», что приводит к переходу от процедуры строгой оптимизации к поиску приемлемого компромисса, реализующего тот или иной принцип координации. 2. Использование самоорганизации в качестве устойчивого механизма формирования коллективного поведения. 3. Применение рандомизации (случайно-вероятностного способа выбора решений) в механизмах координации для разрешения конфликтов. 4. Реализация рефлексивного управления, сущность которого заключается в том, чтобы заставить субъекта осознанно подчиняться влиянию извне, т.е. сформировать у него такие желания и намерения (интенции), которые совпадают с требованиями окружения. Координация поведения агентов в мультиагентной системе Наиболее известными моделями координации поведения агентов являются: теоретико-игровые модели, модели коллективного поведения автоматов, модели планирования коллективного поведения, модели на основе BDI-архитектур (Belief – Desire – Intention), модели координации поведения на основе конкуренции. Теоретико-игровые модели. Предметом теории игр являются задачи выбора решений в условиях неопределенности и конфликта. Наличие конфликта предполагает существование как минимум двух участников, которых называют игроками. Множество решений, возможных для выбора каждым игроком, называется стратегией. Равновесными точками игры (оптимальными решениями) называют такие состояния, когда ни одному из игроков невыгодно менять свою позицию. Понятие равновесия оказалось весьма полезным в теории MAC, поскольку механизм поиска равновесных ситуаций может использоваться как средство самоорганизации коллективного поведения агентов. Следствием подобной интерпретации является подход, в котором необходимые атрибуты коллективного поведения агентов обеспечиваются путем конструирования правил игры. Кроме того, на основе развития теории игр в области MAC предпринимаются попытки построения эффективных, устойчивых, полностью распределенных протоколов переговоров, направленных на координацию коллективного поведения агентов. Множество возможных ситуаций выбора поведе­ния пары агентов классифицируется следующим образом. 1. Симметричная кооперация, когда существует непустое мно­жество стратегий (переговорное множество), при использовании которых оба агента достигают своих целей и получают больший эффект, чем в ситуациях, когда они действуют поодиночке. 2. Симметричный компромисс, когда достижение цели в одиночку более выгодно для каждого агента, однако невозможно в присутствии другого агента. 3. Несимметричная кооперация или несимметричный компромисс_– один из агентов может самостоятельно достичь своей цели в присутствии другого агента, а другой – только засчет кооперации с первым. 4. Конфликт – переговорное множество пусто, т.е. не существует стратегий, обеспечивающих достижение целей обоих агентов. Теоретико-игровые модели позволяют для всех перечисленных случаев сконструировать наборы правил переговоров, следуя которым агенты придут к некоторому соглашению, отвечающему состоянию равновесия. Это достигается засчет использования множества дополнительных предположений и специальных приемов. Например, кроме стоимости цели в рассмотрение вводится понятие ценности цели, а в качестве одной из возможных стратегий может выступать стратегия манипулирования информацией о ценности целей (т.е. агенты могут сообщать друг другу заведомо ложные значения). При этом «нечестные» агенты могут либо увеличить свой доход, либо освободиться от части своей работы. Модели коллективного поведения автоматов. Они основаны на идеях рандомизации, самоорганизации и полной распределенности. Модели этого типа подходят для построения протоколов переговоров в задачах, которые характеризуются большим количеством очень простых взаимодействий с неизвестными характеристиками. Модели планирования коллективного поведения. Планирование может быть централизованным, частично централизованным или распределенным (децентрализованным). В последнем случае агенты сами принимают решения о выборе своих действий в процессе координации частных планов, всвязи с чем возникают вопросы о рациональной децентрализации, о возможности изменения целей при возникновении конфликтов, а также проблемы вычислительной сложности. Модели на основе BDI-архитектур. В моделях этого класса применяются аксиоматические методы теории игр и логической парадигмы искусственного интеллекта. Для описания агентов используются логические средства, в том числе темпоральные и модальные логики. Акцент делается на описании интенсиональных понятий, таких, как убеждения (belief), желания (desire) и намерения (intention). Задача координации поведения агентов решается путем согласования результатов логического вывода в базах знаний отдельных агентов, полученных для текущего состояния внешней среды, в которой действуют агенты. Логический вывод осуществляется непосредственно в процессе функционирования агентов, что приводит к высокой сложности моделей, вычислительным трудностям и к проблемам, связанным с аксиоматическим описанием нетривиальных ситуаций, например, когда перед агентом возникает выбор между решением собственной задачи и выполнением обязательств по отношению к партнерам. Модели на основе конкуренции. В моделях данного класса используется понятие аукцион в качестве механизма координации поведения агентов. Использование механизма аукциона основано на предположении о возможности явной передачи «полезности» от одного агента к другому или к агенту-аукционеру, причем эта полезность обычно имеет смысл денег. Аукционы принято разделять на открытые и закрытые. В первом случае предлагаемые цены объявляются всем участникам. В закрытом аукционе о предлагаемых ценах знает только аукционер. Открытые аукционы различаются по способу проведения. В так называемых английских аукционах обычно задается стартовая цена, которая может увеличиваться участниками в ходе торгов. Побеждает тот, кто даст максимальную цену. Голландский аукцион начинается с верхней цены, которая постепенно снижается. Победителем считается тот, кто дал наибольшую текущую цену. Закрытые аукционы разделяют на аукционы первой и второй цены. В аукционах первой цены побеждает тот, кто предложил самую высокую цену, известную только аукционеру. В аукционах второй цены победитель определяется таким же способом, но платит за товар не свою цену, а вторую по величине. Теоретически доказано, что все разновидности аукционов эквивалентны для аукционера, однако практика показывает иное. Например, если участники аукциона не склонны к риску, то аукционер стимулирует повышение цены продажи при проведении голландского аукциона первой цены. Существуют варианты «групповых» аукционов, когда один или несколько участников представляют интересы группы, и в случае выигрыша проводится аукцион внутри группы. При этом на внутреннем аукционе товар продается по более высокой цене по сравнению с ценой внешнего аукциона. Полученная разница делится между участниками группы. Сам по себе механизм аукциона не затрагивает способов принятия решений участниками. Решения могут приниматься на основе некоторой модели рассуждений, которая может использовать различные типы знаний, доступных агентам, и разнообразные способы их обработки. Аукцион всегда должен заканчиваться. Для этого в стратегии его проведения должны быть заложены средства для разрешения возможных конфликтов (например, при наличии нескольких победителей). Одним из самых простых способов разрешения конфликтов является рандомизация, когда применяется случайный механизм выбора. Примеры мультиагентных систем Координация поведения на основе модели аукциона Электронный магазин. Рассмотрим типичную задачу электронной коммерции, в которой участвуют агенты-продавцы и агенты-покупатели (рис.10.1). Торговля осуществляется в электронном магазине, который представляет собой программу, размещенную на сервере. Ее основным назначением является организация взаимодействия агентов, интересы которых совпадают. Агенты действуют по поручению своих персональных пользователей. При этом агенты-продавцы стремятся продать свой товар по максимально возможной цене, а агенты-покупатели стремятся купить нужный товар по минимальной цене. Оба вида агентов действуют автономно и не имеют целей кооперации. Электронный магазин регистрирует появление и исчезновение агентов и организует контакты между ними, делая их «видимыми» друг для друга. Рис. 10.1. Схема электронного магазина Поведение агента-продавца характеризуется следующими параметрами: • желаемая дата, до наступления которой необходимо продать товар; • желаемая цена, по которой пользователь хочет продать товар; • самая низкая допустимая цена, ниже которой товар не продается; • функция снижения цены во времени (линейная, квадратичная и др.); • описание продаваемого товара. Агент-покупатель имеет «симметричные» параметры: • крайний срок покупки товара; • желаемая цена покупки; • самая высокая приемлемая цена; • функция роста цены во времени; • описание покупаемого товара. Торги ведутся по схеме закрытого аукциона первой цены. Поведение агентов описывается простой моделью, в которой не используются знания и рассуждения. Агент-продавец, получив от электронного магазина информацию о потенциальных покупателях своего товара, последовательно опрашивает их всех с целью принять решение о возможности совершения сделки. Сделка заключается с первым агентом-покупателем, который готов дать за товар запрашиваемую цену. Продавец не может вторично вступить в контакт с любым покупателем до тех пор, пока не опросит всех потенциальных покупателей. При каждом контакте агент-продавец ведет переговоры, предлагая начальную цену либо снижая ее. Агент-покупатель действует аналогичным образом, отыскивая продавцов нужного товара и предлагая им свою цену покупки, которую он может увеличить в процессе переговоров. Любая сделка завершается только в случае ее одобрения пользователем агента. Данная схема переговоров представляет собой простейший случай взаимодействия автономных агентов, действующих реактивно. Тем не менее, итоговое поведение системы вполне адекватно реальности. Системы для поиска информации В связи с быстрым развитием интернет-технологий возникла необходимость применения средств искусственного интеллекта для поиска и обработки интернет-ресурсов. Применение интеллектуальных MAC для решения задач сбора, поиска и анализа информации в глобальных сетях дает следующие существенные преимущества перед традиционными средствами обработки информации: • обеспечение доступа пользователя к сетевым протоколам в сети Интернет; • параллельное решение нескольких задач; • выполнение поиска информации после отключения пользователя от сети; • увеличение скорости и точности поиска, а также уменьшение загрузки сети засчет поиска информации непосредственно на сервере; • создание собственных баз информационных ресурсов, постоянно обновляемых и расширяемых; • реализация возможности сотрудничества между агентами, которая позволяет использовать накопленный опыт; • возможность автоматически корректировать и уточнять запросы, используя контекст и применяя модели пользователей. Недостатком современных систем интеллектуального поиска и обработки информации является их слабая способность к обучению. Поэтому основные усилия по совершенствованию интеллектуальных систем информационного поиска в сети Интернет направлены на развитие моделей представления знаний, механизмов вывода новых знаний, моделей рассуждения и способов обучения агентов. Лекция 11 ИММУННЫЕ СЕТИ Введение в иммунные системы Естественная иммунная система представляет собой сложную систему, состоящую из нескольких функционально различных компонентов. Иммунная система использует многоуровневую защиту против внешних антигенов, включая действие неспецифических (врожденных) и специфических (приобретенных) защитных механизмов. Основная роль иммунной системы заключается в распознавании всех клеток (или молекул) организма и классификации их как «своих» или «чужих». Чужеродные клетки подвергаются дальнейшей классификации с целью стимуляции защитного механизма соответствующего типа. В процессе эволюции иммунная система обучается различать внешние антигены (например, бактерии и вирусы) и собственные клетки или молекулы организма. Установлено, что в организме человека поддерживается большое количество иммунокомпетентных клеток, которые циркулируют по всему телу. Основным типом клеток, участвующих в иммунном ответе и обладающих свойствами специфичности, разнообразия, памяти и адаптивности, являются лимфоциты. Другие клетки, имеющие название фагоцитов, – нейтрофилы, эозинофилы, базофилы и моноциты – это вспомогательные клетки, основная функция которых заключается в обеспечении способности иммунной системы к уничтожению антигенов. В организме имеется два основных типа лимфоцитов – Т- и В-лимфоциты. Указанные два типа лимфоцитов играют в иммунном ответе разную роль, хотя и могут взаимодействовать, контролируя, таким образом, свои функции. При попадании антигена в организм лишь малая часть клеток иммунной системы способна к его распознаванию. Такое распознавание стимулирует процессы размножения и дифференцировки лимфоцитов, приводящие к образованию клонов идентичных клеток (или антител). Этот процесс, называемый размножением клона, формирует многочисленную популяцию специфичных к антигену антителопродуцирующих клеток. Размножение клона иммунокомпетентных клеток приводит к разрушению или нейтрализации антигена. Часть образовавшихся клеток сохраняется для иммунной памяти. В результате, последующее воздействие похожего антигена приводит к более быстрой иммунной реакции (вторичному ответу). Процесс циркуляции В- и Т-лимфоцитов в первичных и вторичных лимфоидных органах тщательно контролируется, что обеспечивает попадание соответствующих клеточных популяций – наивных («необученных») и эффекторных клеток, а также клеток памяти – в разные места назначения. Избирательная миграция лимфоцитов в различные органы и ткани имеет название хоуминга (самонаведения). В этих органах имеется специализированная среда для поддержания процессов размножения активированных антигеном лимфоцитов и их дифференцировки в эффекторные клетки и клетки памяти. Интересно, что клетки памяти оказывают избирательное предпочтение тому типу тканей, в котором они впервые встретились с антигеном. Вероятно, это обеспечивает возврат каждой конкретной клетки памяти в тот участок тела, где она, скорее всего, снова встретится с антигеном. Существует два основных варианта иммунного ответа: гуморальный, опосредованный В-клетками и их продуктами, и клеточный, в котором участвуют Т-клетки. Обоим вариантам иммунных реакций соответствуют сходные последовательности этапов защиты организма: активация, деление, дифференцировка, секреция, иммунная атака, супрессия и память, однако они осуществляются различными способами. В регуляции как гуморального, так и клеточного иммунитета участвуют популяции Т-клеток, называемые хелперными или супрессорными клетками, которые усиливают либо, соответственно, подавляют иммунный ответ. Вычислительные аспекты иммунной системы Иммунная система представляет большой интерес как система, способная эффективно обрабатывать значительные объемы данных. В частности, она выполняет большой объем сложных высокопараллельных распределенных вычислений. Поведение иммунной системы в целом определяется всей совокупностью локальных взаимодействий. Иммунная система функционирует как «второй мозг», поскольку способна хранить информацию об интенсивности предыдущих контактов составляющих ее клеток и отвечать на новые, ранее не встречавшиеся, структуры (антигены). Описание закономерностей развития иммунного ответа представляет собой интересную задачу теории динамических систем. В отношении возможных приложений для обработки информации перспективны следующие свойства иммунной системы. • Распознавание. Иммунная система способна распознавать и классифицировать различные молекулярные структуры и избирательно на них реагировать. Распознавание происходит в ходе межклеточных контактов, при этом сила образующихся связей определяется формой молекул и величиной электростатического заряда. Распознавание своего и чужого является одной из основных задач, которую решает иммунная система. • Выделение особенностей. Антиген – презентирующие клетки (АПК) интерпретируют антигенное окружение и выделяют особенности путем обработки антигенов и представления антигенных пептидов на своей поверхности. Каждая АПК служит в качестве «фильтра», подавляющего молекулярный шум, и «увеличительного стекла», фокусирующего внимание лимфоцитов-рецепторов. • Разнообразие. Иммунная система использует комбинаторный механизм (генетически-обусловленный процесс) для образования множества различных рецепторов лимфоцитов с тем, чтобы гарантировать, что хотя бы один лимфоцит из всей совокупности сможет провзаимодействовать с любым наперед заданным (известным или неизвестным) антигеном. • Обучение. Иммунная система оценивает структуру конкретного антигена, используя его случайные контакты с составляющими эту систему клетками. Обучение состоит в изменении концентрации лимфоцитов, которое происходит при первичном ответе (в результате первого контакта с антигеном). Следовательно, способность иммунной системы к обучению заложена, главным образом, в механизме пополнения клонов, приводящем к образованию новых иммунокомпетентных клеток с учетом текущего состояния системы (этот процесс имеет название размножения клона). • Память. Небольшая часть лимфоцитов, находящихся в активированном состоянии, становится клетками памяти (ассоциативная память). Считается, что время жизни клеток памяти является динамической величиной и определяется частотой стимуляции антигенами. Используя кратковременные и долгосрочные механизмы иммунной памяти, иммунная система поддерживает идеальный баланс между экономией ресурсов и исполнением функции засчет сохранения минимально необходимой, но достаточной памяти о предыдущих контактах с антигеном. • Распределенный поиск. По своей сути иммунная система – это распределенная система. Клетки иммунной системы, главным образом лимфоциты, непрерывно рециркулируют через кровь, лимфу, лимфоидные органы и остальные ткани. В случае встречи с антигеном они осуществляют специфический иммунный ответ. • Саморегуляция. Иммунная защита обладает свойством саморегуляции. Центрального органа, контролирующего функции иммунной системы, не существует. В зависимости от способа проникновения в организм и других свойств антигена, регуляция иммунного ответа может быть как локальной, так и системной. • Пороговый механизм. Иммунный ответ и размножение иммунокомпетентных клеток происходят лишь после преодоления некоторого порога, зависящего от силы химических связей. • Совместная стимуляция. Активация В-лимфоцитов жестко регулируется при помощи дополнительного стимулирующего сигнала. Второй сигнал (от хелперных Т-лимфоцитов) помогает обеспечивать толерантность и проводить различие между серьезной угрозой и «ложным звонком» (т.е. опасными и неопасными антигенами). • Динамическая защита. Клональное размножение и соматическое гипермутирование позволяют иммунной системе продуцировать высокоаффинные иммунокомпетентные клетки (этот процесс называется увеличением аффинности), что создает динамический баланс между изучающей и защитной функцией адаптивного иммунитета. Наличие динамической защиты постепенно приводит к расширению зоны наблюдения, контролируемой иммунной системой. • Вероятностное обнаружение. Перекрестные реакции в ходе иммунного ответа – это процесс стохастический. К тому же обнаружение антигена всегда неизбежно происходит приблизительным образом; следовательно, лимфоцит может взаимодействовать с несколькими структурно сходными антигенами. В иммунном ответе на антиген важную роль играют и другие характеристики иммунной системы, такие как адаптируемость, специфичность, самотолерантность, дифференцировка и другие. Все эти свойства, имеющие отношение к обработке информации, создают ряд интересных возможностей с вычислительной точки зрения. Иммунная система с точки зрения организации обработки данных С точки зрения организации обработки данных иммунная система_– это высокопараллельная структура. В ней реализованы механизмы обучения, памяти и ассоциативного поиска для решения задач распознавания и классификации. В частности, иммунная система способна обучаться распознаванию важных структур (антигенных пептидов); запоминанию уже встречавшихся структур и использованию законов комбинаторики в рамках генных библиотек для эффективной генерации детекторов структур (вариабельных участков молекул антител), взаимодействующих с внешними антигенами и собственными клетками организма. При этом реакция на антиген происходит не только на уровне отдельных распознающих единиц, но и на системном уровне путем взаимного распознавания клонов лимфоцитов в реакциях антиген-антитело. Таким образом, поведение иммунной системы определяется всей совокупностью локальных сетевых взаимодействий. Система иммунитета вызывает большой интерес вследствие ее важной роли в поддержании целостности организма. Свойства иммунной системы служат замечательным примером локальных адаптивных процессов, реализующих эффективные глобальные реакции. Для объяснения механизмов иммунитета существует несколько различных теорий (которые иногда противоречат друг другу). Опубликован ряд имитационных моделей, описывающих реакции различных компонентов иммунной защиты. Происходит расширение сферы применения новых методов решения прикладных задач, основанных на принципах иммунологии. Эти методы имеют различные названия: искусственные иммунные системы; системы, основанные на принципах иммунитета; иммунологические вычисления, и т.д. Сфера их применения включает следующие области (но не ограничивается ими): • методы вычислений, • когнитивные модели, • искусственные иммунные системы для распознавания образов, • методы обнаружения аномалий и неисправностей, • мультиагентные системы, • модели самоорганизации, • модели коллективного интеллекта, • системы поиска и оптимизации, • модели автономных распределенных систем, • модели искусственной жизни, • системы компьютерной и интернет-безопасности, • модели обучающихся систем, • методы извлечения информации, • искусственные иммунные системы для выявления подделок, • методы обработки сигналов и изображений. По мере развития рассматриваемой области возникла идея организации научных конференций и семинаров для обмена информацией и представления результатов текущих исследований. Первый международный семинар «Методы, основанные на принципах иммунной системы» состоялся 10 декабря 1996г. в Японии. Впоследствии была организована отдельная секция «Искусственные иммунные системы и их применение» на международной конференции Института инженеров по электротехнике и электронике (IEEE) «Системы, человек и кибернетика» (SMC97), проходившей с 12 по 15 октября 1997г. в Орландо (США). Модели, основанные на принципах функционирования иммунной системы Для объяснения иммунологических механизмов существуют разные теории и математические модели. Также имеется растущее число компьютерных моделей для имитации динамики различных компонентов иммунной системы и ее поведения в целом. Эти подходы включают модели, сформулированные в виде систем дифференциальных и стохастических уравнений, клеточно-автоматные модели, модели пространства конфигураций и другие. Вместе с тем, естественная иммунная система служит источником новых идей для развития интеллектуальных методов решения сложных задач, но работ в этой области пока немного. Необходимо проводить больше исследований, в частности, для изучения механизмов обработки информации в иммунной системе, что может иметь большое практическое значение. К сожалению, в настоящее время существует лишь небольшое число вычислительных моделей, основанных на принципах работы иммунной системы. По-видимому, это связано с сохраняющейся неопределенностью основных положений, предложенных для ее описания. Среди таких моделей часто используются следующие. 1. Модель иммунной сети Ерне предложил гипотезу, согласно которой иммунная система представляет собой регулируемую сеть молекул и клеток, распознающих друг друга даже при отсутствии антигена. Такие структуры часто называют идиотипическим сетями, они служат математической основой для изучения поведения иммунной системы. Теория Ерне интерпретируется в виде системы дифференциальных уравнений, описывающей динамику концентрации клонов лимфоцитов и соответствующих молекул иммуноглобулинов. Теория идиотипической регуляции основана на предположении, что различные клоны лимфоцитов друг от друга не изолированы, а поддерживают связь путем взаимодействий между своими рецепторами и антителами. Следовательно, распознавание антигена осуществляется не единичным клоном клеток, а скорее на системном уровне, с участием различных клонов, взаимодействующих по типу реакций антиген-антитело как единая сеть. Ерне считал, что в ходе иммунного ответа сам антиген вызывает лишь выработку первого набора антител Аb1. Затем эти антитела, действуя в качестве антигена, вызывают выработку второго набора «антиидиотипических» антител Ab2, распознающих идиотипы на антителах Аb1. Аналогично осуществляется выработка третьего набора антител, Ab3, распознающих антитела Ab2, и так далее. Ключевой постулат теории Ерне заключается в том, что единичная клетка продуцирует лишь один тип антител; отсюда следует несколько выводов: 1) существует аллельное исключение, 2) все антитело-подобные рецепторы на поверхности лимфоцита должны быть идентичными или, по крайней мере, иметь идентичные легкие цепи и вариабельные области тяжелых цепей; а также что 3) все антитела, продуцируемые данной клеткой, и ее потомки должны иметь одинаковый идиотип. Формулируя основы своей теории, Ерне ввел понятия формальных и функциональных сетей. Формальные сети служат для изучения вопросов репертуара, дуализма и супрессии. При рассмотрении функциональных сетей представлена количественная картина теории. Вероятностный подход к изучению идиотипических сетей на основе работы Ерне предложил Перельсон. Данный подход предельно математизирован и, в основном, связан с описанием фазовых переходов. Перельсон разделил плоскость фазовых переменных рассматриваемой системы уравнений на докритическую область, область перехода и посткритическую область. Последние 20 лет предложенной Ерне теории иммунной сети уделялось значительное внимание, что привело к подробному изучению многих вычислительных аспектов соответствующих математических моделей. 2. Алгоритм отрицательного отбора Форрест и др. предложили алгоритм отрицательного отбора для обнаружения изменений, построенный на основе принципов распознавания своего и чужого в системе иммунитета. В иммунной системе такое распознавание обеспечивается Т-лимфоцитами и другими клетками, имеющими на своей поверхности рецепторы, способные обнаруживать чужеродные белки (антигены). Рецепторы создаются на основе псевдослучайного генетически обусловленного процесса перегруппировки в ходе образования Т-клеток. Попадая в тимус, Т-клетки подвергаются цензурированию, называемому отрицательным отбором, при этом клетки, вступившие в реакцию с собственными белками, уничтожаются, а остальные (не образующие с ними связей) получают возможность покинуть тимус. Затем эти Т-клетки циркулируют по всему организму и выполняют функцию защиты от чужеродных антигенов. Аналогично действует алгоритм отрицательного отбора, случайным образом создавая детекторы и удаляя те из них, которые распознают свое, так что остающиеся детекторы могут обнаруживать любое не свое. Этот подход можно формализовать следующим образом. • Определим свое как совокупность S строк длины l над конечным алфавитом, которую необходимо защищать или контролировать. Например, в качестве S могут выступать программа, файл данных (любое программное обеспечение) или нормальная форма активности, подразделяемые на подстроки равной длины. • Образуем набор детекторов R, каждый из которых не должен соответствовать любой строке в S. Вместо точного, или идеального, соответствия используем правило частичного соответствия, при котором две строки соответствуют друг другу, если и только если они совпадают, по крайней мере, в r следующих друг за другом позициях, где r – некоторый целочисленный параметр. • Проверим S на предмет изменений путем непрерывного сравнения детекторов из R с элементами S. Если хотя бы один из детекторов окажется соответствующим, значит, произошло изменение, поскольку детекторы по определению отобраны так, чтобы не соответствовать любой строке из S. В исходном описании алгоритма кандидаты в детекторы генерировались случайно и затем проверялись (подвергались цензурированию) на соответствие любой строке своего. Если соответствие имело место, то такой кандидат отвергался. Процедура повторялась до тех пор, пока не создавалось нужное количество детекторов, необходимое для обеспечения определенного уровня надежности, которое оценивалось с использованием статистических методов. Главное ограничение подхода со случайной генерацией детекторов, по-видимому, состоит в вычислительной сложности их создания, так как количество детекторов растет экспоненциально по мере увеличения размерности своего. Впоследствии Хелман и Форрест предложили более эффективный алгоритм генерации детекторов с линейной зависимостью от размерности своего. Также были предложены другие методы генерации детекторов, имеющие разную степень вычислительной сложности. Приведенный алгоритм опирается на три важных принципа: 1) каждый вариант алгоритма уникален, 2) процесс выявления изменений имеет вероятностный характер и 3) надежная система должна обнаруживать не только заранее известные варианты изменений, но и любую чужеродную активность. Дальнейшие исследования показали большие возможности алгоритма. 3. Другие модели Существуют и другие вычислительные модели, имитирующие различные иммунологические явления, например, способность иммунной системы находить общие структуры в зашумленной среде, возможность обнаруживать и поддерживать охват структур, принадлежащих различным классам, а также способность к эффективному обучению даже в том случае, если экспрессированы не все молекулы иммуноглобулинов и не все антигены присутствуют. В нескольких работах для моделирования процесса соматических мутаций (при котором образуются антитела для распознавания конкретного антигена) применялись генетические алгоритмы. Хаффман сопоставил иммунную систему с нервной системой, показал ряд аналогий, имеющихся на уровне общего поведения этих систем. Еще можно упомянуть про алгоритмы муравья и отжига, если останется время, разумеется.