(+). Лекции ИИС


Лекция 1. Эволюция обработки информации в компьютерных системах
Эволюция обработки информации в компьютерных системах
Прикладные области систем ИИ
Тест Тьюринга.
Интеллектуальные системы. Базовые функции.
Эволюция обработки информации в компьютерных системах
На первых этапах развития информационных технологий считалось, что компьютеры предназначены в основном для проведения математических расчетов.
Это нашло отражение и в термине, первоначально введенному для обозначения компьютеров: "Электронная вычислительная машина" (ЭВМ). Этот термин включает общее понятие: "Машина", а также два специфических признака: "Электронная" и "Вычислительная". Первый из этих признаков является характеристикой элементной базы, а второй является функциональным.
Сегодня ясно, что у компьютеров может быть неэлектронная основа, и что их функции далеко выходят за пределы собственно проведения вычислений. Поэтому более правильным, было бы такое определение компьютера: "Компьютер – это средство труда для обработки информации ".
Развитие автоматизированных технологий обработки информации идет по пути все более глубокой переработки "информационного сырья", в результате чего "информационный продукт" все в большей степени отличается от исходного состояния информации.
Многие виды умственной деятельности человека: такие, как написание программ для вычислительной машины, занятие математикой, ведение рассуждений на уровне здравого смысла и даже вождение автомобиля, — как говорят, требуют "интеллекта". В 80-90хх годах было построено несколько систем на вычислительных машинах, способных выполнять задачи, подобные этим. В частности, имеются системы, способные диагностировать заболевания, планировать синтез сложных органических соединений в химии, решать дифференциальные уравнения в символической форме, анализировать электронные схемы, понимать ограниченный объем человеческой речи и естественного языкового текста или написать небольшую программу для вычислительной машины, удовлетворяющую определенным формальным требованиям. Мы могли бы сказать, что такие системы обладают в некоторой степени искусственным интеллектом.
Работа по построению такого рода систем проводится, главным образом, в области, получившей название искусственный интеллект. Эта работа в значительной степени имеет эмпирическую и инженерную ориентации. Отталкиваясь от плохо структурированного, но все время увеличивающегося объема вычислительных приемов, системы ИИ испытываются и совершенствуются в экспериментальных ситуациях.
Прикладные области систем ИИ
Обработка естественного языка. Когда люди общаются между собой на естественном языке (ЕЯ), они практически без всяких усилий используют сложные и пока мало понятные процессы. Оказалось, что построить машины, способные «понимать» хотя бы фрагменты ЕЯ, чрезвычайно трудно. Одной из причин является то обстоятельство, что ЕЯ возник как средство общения интеллектуальных существ, которые располагают весьма большими и сходными «умственными структурами». При общении людей между собой эти структуры играют роль колоссальной общедоступной контекстуальной базы знаний, опираясь на которую участники обмена могут создавать и воспринимать чрезвычайно сжатые сообщения.
Техническая система, способная понимать сообщение на ЕЯ, как и человек нуждается в контекстуальных знаниях и механизмах, обеспечивающих логический вывод на основе полученного сообщения и этих контекстуальных знаний, поскольку «генератор сообщения на ЕЯ» — человек, посылая сообщение, уже предполагает наличие этих знаний и механизмов.
К настоящему времени в этом направлении достигнуты реальные результаты в решении задач синтеза и анализа письменных и устных фрагментов речи, а также задач машинного перевода с одного языка на другой с определенными ограничениями. Направление вошло в практическую стадию разработок прикладных систем.
Извлечение знаний из баз данных. Базы данных (БД) представляют собой электронные хранилища, в которых могут находиться большие объемы сведений, относящихся к определенным предметным областям. БД формируется таким образом, чтобы из нее можно было извлекать нужные сведения в виде ответов на запросы по данной предметной области. В настоящее время существует много разнообразных приемов построения БД и способов извлечения информации из них. В рамках ИИ интересна другая постановка вопроса, а именно - как извлечь из БД ответ на вопрос, который, хотя и содержится в БД в неявном виде на основе имеющихся в ней сведений, но его невозможно сформулировать в рамках стандартного запроса. Т.е. для получения ответа в явном виде необходимо провести некоторые дедуктивные рассуждения со сведениями, хранящимися в БД.
Это направление пока находится в стадии теоретических и экспериментальных исследований. В частности, известны попытки решения подобных задач с помощью ИНС .
Экспертные и консультирующие системы. Автоматические экспертные и консультирующие системы (АЭКС) призваны обеспечивать не очень квалифицированных специалистов компетентными заключениями, касающимися определенных предметных областей.
Ключевая проблема при построении АЭКС состоит в том, как представлять и использовать знания, которыми располагают и пользуются люди, являющими экспертами в предметных областях. Эта проблема осложняется тем, что экспертные знания часто являются неточными, неопределенными и плохо формализуемыми, что не мешает, тем не менее, экспертам делать правильные заключения.
Во многих АЭКС применяется метод ИИ, позволяющий строить логические выводы, основанные на правилах. В таких системах экспертные знания представлены в виде большого множества простых правил, которые применяются при организации диалога между системой и пользователем, а также для вывода заключений. Дедукция, основанная на правилах, является одним из плодотворных направлений в исследованиях по ИИ.
В настоящее время АЭКС - весьма динамично развивающаяся область. Известны и успешно эксплуатируются коммерческие АЭКС, диагностирующие заболевания, оценивающие потенциальные месторождения полезных ископаемых, предлагающие варианты возможных структур сложных органических соединений и многие другие.
Доказательство теорем. Поиск доказательства (или опровержения) некоторой математической теоремы, несомненно, может рассматриваться как интеллектуальная задача. Во-первых, потому что для доказательства требуется способность провести дедукцию, исходя из гипотез. Во-вторых, для построения доказательства необходимы интуитивные навыки, такие как построение догадки, о том, какие промежуточные леммы следует доказать, чтобы доказать основную теорему. Опытный математик, опираясь на некоторое собственное суждение, основанное на большом объеме специальных знаний, высказывает догадку, какие из ранее доказанных теорем в рассматриваемой предметной области будут полезны для искомого доказательства, а также выделяет в главной проблеме подзадачи, над которыми можно работать независимо друг от друга.
В рамках ИИ был разработан ряд программ, которые в какой-то степени обладали некоторыми из таких способностей. И хотя это не принесло большой практической пользы непосредственно для доказательства теорем, изучение приемов доказательства теорем сыграло большую роль в развитии методов ИИ. Оказалось, что многие неформальные задачи допускают их формализацию как задачи на доказательство теорем.
Робототехника. В настоящее время это самостоятельная область науки и техники, выделившаяся из ИИ. Ее задачей является решение теоретических и практических вопросов организации целесообразного поведения подвижных кибернетических систем - роботов, снабженных сенсорными и эффекторными (исполнительными) механизмами. Перед роботами обычно ставится некоторая глобальная цель, например - достижение некоторой точки в окружающем пространстве. Однако предполагается, что заранее невозможно полностью предсказать все возможные взаимодействия робота с окружающей средой. Поэтому многие проблемы своего поведения в окружающей среде робот должен решать самостоятельно (методами ИИ), учитывая конкретные условия и используя при этом бортовой компьютер.
Исследования по робототехнике оказали существенное влияние на развитие многих идей ИИ. В частности, они привели к созданию методов описания и моделирования состояния внешнего мира, дали лучшее понимание того, каким образом строить планы для последовательности действий робота и как управлять выполнением этих планов. Методы планирования действий робота стали строить как многоуровневые системы с высоким уровнем абстракции на верхнем уровне и все более детализированные на последующих уровнях.
Автоматическое программирование. Существующие компиляторы в некотором смысле уже осуществляют автоматическое программирование. Они воспринимают полную спецификацию во входном коде того, что программа должна делать, и пишут программу в объектном коде, которая это делает. Под автоматическим программированием понимается некий «суперкомпилятор», который мог бы воспринимать описание на очень высоком уровне вплоть до ЕЯ того, что требуется от искомой программы. При этом, учитывая высокий уровень входного описания, а, следовательно, и наличие большого числа неоднозначностей в этом описании, автоматическое программирование предполагает, дополнительный диалог между системой и пользователем для исключения этих неоднозначностей.
Задача автоматического написания программы для достижения заданного результата тесно связана с задачей доказательства того, что программа вообще достигнет этого результата. Последняя задача получила название верификации программы. Поэтому многие системы автоматического программирования включают верификацию выходной программы в качестве некоторой дополнительной возможности.
Важным вкладом в автоматическое программирование явилось заимствованное из робототехники представление об отладке программ как стратегии решения проблем. Установлено, в частности, что часто более эффективным оказывается создание недорогой, с большим количеством ошибок программы, с последующей ее модификацией, чем поиск с самого начала идеальной программы, лишенной дефектов.
Комбинаторные задачи и составление расписаний. Многие задачи из этой области исследуются методами ИИ. Классическим примером является задача коммивояжера, в которой требуется найти маршрут минимальной длины в пределах нескольких городов, начиная от некоторого исходного города, посещая каждый город один раз и возвращаясь в исходный город.
Такой же характер носят многие головоломки. Например, задача о восьми ферзях, которая состоит в том, что восемь ферзей надо разместить на обычной шахматной доске так, чтобы ни один из них не атаковал другого. В задачах такого типа область возможных комбинаций или последовательностей, из которых необходимо выбрать ответ, чрезвычайно велика. Простые попытки решения таких задач вскоре порождает комбинаторный взрыв вариантов, который быстро исчерпывает возможности современных компьютеров.
Некоторые из этих задач (включая задачу коммивояжера) математики относят к так называемым NP-полным (недетерминистки полиномиальным) задачам. Трудность их решения состоит в высокой степени возрастания числа комбинаций (числа шагов или времени решения), в зависимости от какой-либо характеристики объема задачи. В задаче коммивояжера такой характеристикой является число городов. Степень возрастания комбинаций в задачах может быть линейной, полиномиальной и экспоненциальной. В NP-полных задачах время решения растет экспоненциально с увеличением объема задачи, и пока еще не установлено, существует ли более быстрый, чем экспоненциальный метод решения NP-полных задач. Поэтому усилия специалистов, работающих над решением комбинаторных задач методами ИИ, сводятся к поиску квазиоптимальных решений, удовлетворяющих по точности, при существенно меньших затратах времени. Интересные результаты в решении NP-полных задач (в том числе и задачи коммивояжера) достигнуты, в частности, с помощью рекуррентных ИНС Хопфилда.
Зрительное восприятие. Попытки снабдить компьютеры «глазами» показали, что для интеллектуального восприятия и обработки столь сложных входных данных, какими являются зрительные сцены и образы, как и в случае с естественной речью, необходим компонент «понимания». В свою очередь, для моделирования этого компонента, как уже говорилось выше, необходима колоссальная база знаний об окружающей среде.
Смысл процесса машинного зрительного восприятия состоит в создании сжатого представления о реальных входных сценах и образах, с которыми машина не в состоянии работать из-за огромного объема описывающей их информации. При этом характер и качество окончательного представления зависит от целей воспринимающей системы (что является важным: цвета, пространственные соотношения, размеры, наличие определенных объектов, признаков и т.д.).
Основная трудность при восприятии сцен - невообразимое число возможных описаний. Одна из возможных плодотворных стратегий в этих условиях состоит в построении гипотез на различных уровнях описания с последующей их проверкой при помощи набора детекторов. В свою очередь, процесс формирования гипотез также нуждается в большом объеме знаний о сценах, которые ожидается увидеть.
В настоящее время зрительное машинное восприятие традиционно включает в себя следующие направления:
методы анализа трехмерных сцен;
методы представления информации о зрительных образах в базе знаний; методы перехода от зрительных сцен к их текстовому описанию и обратного перехода;
методы порождения зрительных сцен на основе внутренних представлений в системах ИИ;
методы и средства когнитивной графики.
Программное обеспечение систем ИИ. Инструментальные средства для разработки интеллектуальных систем включают в себя:
•специальные языки программирования, ориентированные на обработку символьной информации (LISP, SMALLTALK, РЕФАЛ);
•языки логического программирования (PROLOG);
• языки представления знаний (OPS 5, KRL, FRL);
•интегрированные программные среды, содержащие арсенал инструментальных средств создания систем ИИ (КЕ, ARTS, GURU, G2);
•оболочки экспертных систем (BUILD, EMYCIN, EXSYS Professional, Эксперт), которые позволяют создавать прикладные ЭС, не прибегая к программированию.
Тест Тьюринга.
В 1950 году в статье "Вычислительные машины и разум" (Computing machinery and intelligence) выдающийся английский математики и философ Алан Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос "может ли машина мыслить?" на более определённый.
Вместо того, чтобы отвлеченно спорить о критериях, позволяющих отличить живое мыслящее существо от машины, выглядящей как живая и мыслящая, он предложил реализуемый на практике способ установить это.
Судья-человек ограниченное время, например, 5 минут, переписывается в чате (в оригинале – по телеграфу) на естественном языке с двумя собеседниками, один из которых – человек, а другой – компьютер. Если судья за предоставленное время не сможет надёжно определить, кто есть кто, то компьютер прошёл тест.
Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. С целью сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями.
Переписка должна производиться через контролируемые промежутки времени, чтобы судья не мог делать заключения исходя из скорости ответов. (Тьюринг ввел это правило потому, что в его времена компьютеры реагировали гораздо медленнее человека. Сегодня же это правило необходимо, наоборот, потому что они реагируют гораздо быстрее, чем человек).
Идею Тьюринга поддержал Джо Вайзенбаум, написавший в 1966 году первую "беседующую" программу "Элиза". Программа всего в 200 строк лишь повторяла фразы собеседника в форме вопросов и составляла новые фразы из уже использованных в беседе слов. Тем ни менее этого оказалось достаточно, чтобы поразить воображение тысяч людей.
А.Тьюринг считал, что компьютеры в конечном счёте пройдут его тест, т.е. на вопрос: "Может ли машина мыслить?" он отвечал утвердительно, но в будущем времени: "Да, смогут!"
Против теста Тьюринга было выдвинуто несколько возражений. Самое интересное из них: Машина, прошедшая тест, может не быть разумной, а просто следовать какому-то хитроумному набору правил.
На что Тьюринг не без юмора отвечал: "А откуда мы знаем, что человек, который искренне считает, что он мыслит, на самом деле не следует какому-то хитроумному набору правил?"
По сообщению Университета Рединга , в тестировании 6 июня 2014 года, организованном Школой системной инженерии при университете и компаний RoboLaw под руководством профессора Кевина Уорика, полноценный тест Тьюринга впервые в истории был пройден с помощью программы «Eugene Goostman», разработанной в Санкт-Петербурге выходцем из России Владимиром Веселовым и выходцем из Украины Евгением Демченко. Всего в тестировании участвовали пять суперкомпьютеров. Испытание представляло собой серию пятиминутных письменных диалогов. Тест Тьюринга считался пройденным, если компьютеру удалось бы вводить собеседника (человека) в заблуждение на протяжении хотя бы 30 % суммарного времени. Программа Eugene c результатом 33 % и стала тем устройством, которое искусственным путём воссоздало человеческий интеллект — в данном случае, тринадцатилетнего подростка из Одессы, который «претендует на то, что знает всё на свете, но в силу своего возраста не знает ничего». Это вторая победа программы, однако в 2012 году на конкурсе в честь юбилея Алана Тьюринга (см. выше) она не добрала 0,8 % для полного прохождения теста.
CAPTCHA — это разновидность обратного теста Тьюринга. Перед тем как разрешить выполнение некоторого действия на сайте, пользователю выдается искаженное изображение с набором цифр и букв и предложение ввести этот набор в специальное поле.
Интеллектуальные системы. Базовые функции
Под интеллектуальными системами понимают любые биологические, искусственные или формальные системы, проявляющие способность к целенаправленному поведению. Последнее включает свойства (проявления) общения, накопления знаний, принятия решений, обучения, адаптации и т. д.
Можно выделить следующие типы интеллектуальных систем:
1. Автоматизированные системы распознавания образов.
2. Системы с интеллектуальной обратной связью.
3. Автоматизированные системы поддержки принятия решений
4. Экспертные системы (ЭС).
5. Системы на основе нейронных сетей.
Система считается интеллектуальной, если в ней реализованы следующие три базовые функции.
1. Функция представления и обработки знаний. Интеллектуальная система должна быть способна накапливать знания об окружающем мире, классифицировать и оценивать их с точки зрения прагматики и непротиворечивости, инициировать процессы получения новых знаний, соотносить новые знания со знаниями, хранящимися в базе знаний.
2. Функция рассуждения. Интеллектуальная система должна быть способна формировать новые знания с помощью логического вывода и механизмов выявления закономерностей в накопленных знаниях, получать обобщенные знания на основе частных знаний и логически планировать свою деятельность.
3. Функция общения. Интеллектуальная система должна быть способна общаться с человеком на языке, близком к естественному языку (ЕЯ) и получать информацию через каналы, аналогичные тем, которые использует человек при восприятии окружающего мира (прежде всего, зрительный и звуковой), уметь формировать «для себя» или по просьбе человека объяснения собственной деятельности (т. е. отвечать на вопросы типа «Как я это сделал?»), оказывать человеку помощь за счет знаний, которые хранятся в ее памяти, и логических средств рассуждения.

Рис. 1. Функциональная модель интеллектуальной системы.
Функциональная модель включает:
интеллектуальный интерфейс обеспечивает общение с внешней средой и преобразование информации из внешнего во внутреннее представление и обратно
подсистема логического вывода на основе анализа семантики входных сообщений и имеющихся знаний формулирует постановку задачи, осуществляет поиск вариантов ее решения и выбирает из них наилучшие;
генератор программ формирует программу решения, используя знания о методах решения задач;
интерпретатор задач обеспечивает выполнение сгенерированных программ;
база знаний обеспечивает хранение и доступ к различным видам знаний, используемым интеллектуальной автоматизированной системой (ИАС) при ее функционировании.
Выделяют следующие виды знаний:
• интерфейсные — знания о взаимодействии с окружающей средой (как можно это делать);
• проблемные — знания о предметной области (ПрО);
• процедурные — знания о методах решения задач;
• структурные — знания об операционной среде (о себе);
• метазнания — знания о свойствах знаний.
Лекция 2. OCR-системы. Информационно-поисковые системыТехнология автоматического распознавания образов.
Информационно-поисковые системы
История языка Пролог
Технология автоматического распознавания образов.
Человек давно задумывался над проблемой распознавания текста машинами. Трудно поверить, но первые машины для оптического распознавания знаков появились задолго до компьютерной эры. В 1914 году химик Эммануэль Голдберг (к слову, русский эмигрант, бежавший в Германию из-за антисемитских настроений в царской России), специалист по фотохимии и изобретатель ряда фотокамер, сконструировал прообраз оптической машины, способной переводить напечатанные буквы в телеграфный код. Примерно в то же время ирландский химик Эдмунд Фурнье д'Альбе создал и запатентовал «оптофон» - прибор, умеющий переводить написанное в систему низких и высоких звуков. Оптофон предназначался для того, чтобы слепые могли «читать».
Чуть позже, в 1929 году, австрийский электротехник Густав Таушек запатентовал метод оптического распознавания текста, за ним последовал Гендель в 1933. Машина Таушека представляла собой механическое устройство, которое использовало шаблоны и фотодетектор.
Коммерческое производство машин для распознавания текста начал в 1950 году Дэвид Х. Шепард военный специалист по криптоанализу. Его машина, запатентованная в 1953 году, понимала буквы латинского алфавита, азбуку Морзе и музыкальную нотацию. Первые машины Шепарда произведенные компанией IMR были куплены для перевода машинописных статей корреспондентов для перевода в общую базу с дальнейшей вёрсткой; чтения с печатных чеков информации о кредитных картах, и т. д.
С 1960-го года машины для оптического распознавания текста стали использоваться повсеместно в США и Канаде, то есть в их почтовых системах и правительственной структуре.
В 1974 году известный изобретатель и футуролог Рэймонд Курцвейл запатентовал систему, состоящую из OCR-машины и синтезатора человеческой речи, таким образом создав первый читающий вслух механизм. Надо сказать, что в те годы распознаватель чаще всего представлял собой именно отдельное устройство, а не программу-приложение для компьютера. Но компьютерная эра наступала неотвратимо.
Но все эти были лишь машины, а не привычные нам сейчас программы для распознавания текста.
Методы автоматического распознавания образов и их реализация в системах оптического чтения текстов (OCR-системах — Optical Character Recognition) — одна из самых плодотворных технологий ИИ.
В этом случае под OCR понимают устройство оптического распознавания символов или автоматического чтения текста. В настоящее время такие устройства при промышленном использовании обрабатывают до 100 тыс. документов в сутки. Промышленное использование предполагает ввод документов хорошего и среднего качества. Это соответствует задачам обработки бланков переписи населения, налоговых деклараций и т. п.
Отметим следующие особенности ПрО (предметной области), существенные с точки зрения OCR-систем:
шрифтовое и размерное разнообразие символов;
искажения в изображениях символов (разрывы образов символов, например, при увеличении изображения; слипание соседних символов и др.);
перекосы при сканировании;
посторонние включения в изображениях;
сочетание фрагментов текста на разных языках;
большое разнообразие классов символов, которые могут быть распознаны только при наличии дополнительной контекстной информации (дуальные символы, имеющие одно и то же начертание в строчном и прописном вариантах, например, «W» и «w», «S» и «s»; эквивалентные символы, принадлежащие разным алфавитам и имеющие одинаковое начертание, например, «О» в кириллице, латинице и ноль; толерантные символы, т. е. символы, близкие по начертанию, например, «ъ» и «ь», «/», «1» и «i»).
Графический образ символа на выходе сканера имеет вид шейпа, представляющего собой матрицу из точек, которую можно редактировать поэлементно. На рис. 2.3 приведен пример шейпа буквы «л» или «п». Он ближе к букве «л», но без контекстной обработки утверждать это со 100%-ной уверенностью нельзя. В простейшем случае контекстом служит слово.
-927106350Информация об отдельном слове не всегда достаточна для принятия решения. Например, в слове «сто*» в позиции звездочки может располагаться как «л», так и «п». В таких случаях анализируемый контекст уже должен включать в себя предложение или несколько предложений (фрагмент текста). Поэтому реализация соответствующих механизмов связана с решением проблемы понимания текста на естественном языке.
К наиболее известным OCR-системы относят:
Fine Reader ( фирмы ABBYY Software House ), позволяющие распознавать как печатные многоязычные тексты;
CuneiForm фирмы Cognitive Technologies;
Работа системы типа Fine Reader включает два крупных этапа.
1. Анализ графических изображений:
выделение таблиц, картинок;
определение областей распознавания;
выделение строк, символов.
2. Распознавание отдельных символов. Система распознавания отдельных символов реализуется как классификатор.
Существуют три типа классификаторов:
1) шаблонные (растровые);
2) признаковые;
3) структурные.
В схеме классификатора первого типа с помощью критерия сравнения определяется, какой из шаблонов выбрать из базы. К достоинствам шаблонного классификатора относятся хорошее распознавание дефектных символов («разорванных» или «склеенных»), простота и высокая скорость распознавания. Недостатком является необходимость настройки системы на типы и размеры шрифтов.
Наиболее распространены признаковые классификаторы. Анализ в них проводится только по набору чисел или признаков, вычисляемых по изображению. Таким образом, происходит распознавание не самого символа, а набора его признаков, т. е. производных данных от исследуемого символа. Это неизбежно вызывает некоторую потерю информации.
Структурные классификаторы переводят шеип символа в его топологическое (непрерывное, связанное) представление, отражающее информацию о взаимном расположении структурных элементов символа (Тополо́гия — раздел математики, изучающий в самом общем виде явление непрерывности, в частности свойства пространства, которые остаются неизменными при деформациях.). Эти данные могут быть представлены в графовой форме. Такой способ обеспечивает инвариантность (неизменность, постоянность) относительно типов и размеров шрифтов. Недостатками являются трудность распознавания дефектных символов и медленная работа.
В Fine Reader применяется так называемый структурно-пятенный(от слова пятно) эталон и его фонтанное (от англ. font — шрифт) представление .
Оно имеет вид набора пятен с попарными отношениями между ними. Подобную структуру можно сравнить со множеством шаров, нанизанных на резиновые шнуры, которые можно растягивать. При этом обеспечиваются все достоинства шаблонного и структурного классификаторов. Также данное представление нечувствительно к различным начертаниям и дефектам символов.

Рис. 2. Укрупненная схема работы Fine Reader .
Ну а если, в общем, то в современных OCR-системах обычно используются все три типа классификаторов. Основным является структурный, а для ускорения и повышения качества распознавания применяются растровый и признаковый классификаторы.
2. Информационно-поисковые системы
Информационный поиск — совокупность операций, методов и процедур, направленных на отбор данных, хранящихся в ИС и соответствующих заданным условиям.
Информация в информационных системах может быть представления с помощью гипертекста.
Гипертекст (ГТ) — одна из фундаментальных моделей представления знаний, выраженных в текстовом виде. Обычный (одномерный) текст рассматривается как длинная строка символов, читаемая в одном направлении. Многомерный текст (ГТ) включает точки ветвления, в которых чтение можно продолжать в нескольких направлениях в зависимости от информационных потребностей читателя.
В основе ГТ лежат следующие основные идеи.
1. Текст разбивается на фрагменты, представляющие его семантические единицы (сеты). Между ними устанавливаются связи, которые могут наделяться именами.
2. В отличие от обычного текста, который читается последовательно (в порядке, определенном его автором), ГТ можно читать, двигаясь по разным траекториям, образованным связанными сетами.
3. Активируемые переходы выбираются читателем (пользователем).
Гипертекстовая информационная технология (ГИТ) — технология обработки семантической информации, основанная на использовании гипертекста.
Области применения ГИТ весьма разнообразны:
информационные ресурсы и технологии Internet;
гипертекстовые информационно-поисковые системы;
гипертекстовые информационные модели экономических систем;
базы данных с гипертекстовой организацией;
представление электронной документации (в том числе, контекстнозависимой и ситуативно-зависимой справки по программным средствам);
электронные записные книжки;
электронные картотеки, словари, энциклопедии, справочники;
обучающие системы;
экспертные системы;
организация пользовательского интерфейса и др.
Гипертекстовая информационная технология используется при организации больших массивов текстовых документов и реализации методов поиска информации в них.
Информационно-поисковые системы (ИПС) подразделяются на три класса:
• документальные;
• фактографические;
• гипертекстовые (ГИПС).
Документальные ИПС хранят и выдают сведения о документах, основное содержимое которых представлено в виде связанного текста на естественном языке. Признаки документа, отражающие его содержание в ИПС, называют поисковым образом.
Первые ИПС были предназначены для поиска книг в библиотеках и получили название библиографических. Позже их стали применять и для поиска документов в больших хранилищах и стали называть документальными.
Документальный поиск относится к числу сложных информационных процессов, поскольку он связан с проблемой оценивания смыслового соответствия документа и запроса. Из-за субъективности и неоднозначности подобного оценивания этот вид поиска в принципе не может быть исчерпывающе точным и полным, в нем всегда будет присутствовать элемент нечеткости.
В фактографических ИПС хранятся не документы, а собственно сведения (факты) об объектах ПрО. Подобные ИПС реализуются, в частности, на основе реляционных БД. С точки зрения обеспечения релевантности результатов поиска (выборки данных) запросу фактографический поиск в отличие от документального является точным и полным.
В гипертекстовых ИПС кроме содержимого документов отражается их семантическая структура. Поэтому по глубине формализации ГИПС занимают промежуточное положение между документальными и фактографическими ИПС.
Эффективность информационного поиска документов, обеспечиваемая ИПС, оценивается по информационной полноте и информационному шуму. Названные показатели выражаются коэффициентами полноты кп шума кш соответственно. Коэффициенты кп и кш принимают значения в интервале от 0 до 1. В некоторых источниках эти коэффициенты выражают в процентах.
1. Идеальный вариант: полнота максимальна (кп = 1), а шум нулевой (кш = 0).
2. Имеет место неполнота (0 ≤ кп <1), а шум отсутствует (кш = 0).
3. Неполнота исключается ( кп = 1), но есть шум (0 < кш ≤ 1).
4. Худший вариант: нулевая полнота (ни один релевантный документ не найден; кп = 0) и максимальный шум (все, что выделено, не соответствует запросу; кш = 1).
5. Имеют место и неполнота (0< кп < 1), и шум (0 < кш < 1).
На практике принято использовать обратный показатель коэффициента шума коэффициент точности kт =1- кш
Интегральный показатель эффективности информационного поиска ИПС.
E1= eq \f(2kт kп;kт + kп )
Обобщенный комплексный показатель эффективности Eβ (мера Ван Ризбергена), позволяющий учитывать предпочтение, отдаваемое пользователем ИПС точности или полноте.
Eβ= eq \f((β2+1)kт kп; β2kт + kп )
где β — параметр, отражающий предпочтение пользователя ИПС одному из показателей эффективности, входящих в Eβ (точности, полноте), над другим.
При β = 1 точность и полнота одинаково важны. На интервале β ∈[0; 1] приоритет имеет точность, а на интервале β ∈ [1; ∞] — полнота.
Сравнение документальных, фактографических и гипертекстовых ИПС по показателям

История языка Пролог
На протяжении многих тысячелетий человечество занимается накоплением, обработкой и передачей знаний. Для этих целей непрерывно изобретаются новые средства и совершенствуются старые: речь, письменность, почта, телеграф, телефон и т. д. Большую роль в технологии обработки знаний сыграло появление компьютеров.
Основные вехи эволюции Пролога
1879 г. Фреже публикует работу "Концептуальный язык"
1965 г. Дж.Э. Робинсон "Машинно-ориентированная логика, основанная на принципе резолюции"
1968 г. Лавленд "Автоматическое доказательство теорем путем устранения моделей"
1971 г. Ковальски и Куэнер "Линейный отбор при помощи функции резолюции"
1973 г. Кольмерор в Марселе написал первую версию интерпретатора Пролога, пользуясь языком Фортран
1974 г. Ковальски "Логика предикатов как язык программирования"
1977 г. Уоррен и Перейра из Эдинбургского университета создали интерпретатор/компилятор языка Пролог для ЭВМ DEC-10
1980 г. В Империэл Колледже разработан интерпретатор языка микро- Пролог для персональных ЭВМ
1981 г. Проект создания ЭВМ пятого поколения, основанной на методах логического программирования - институт ICOT, Япония
В октябре 1981 года Японское министерство международной торговли и промышленности объявило о создании исследовательской организации — Института по разработке методов создания компьютеров нового поколения (Institute for New Generation Computer Technology Research Center). Целью данного проекта было создание систем обработки информации, базирующихся на знаниях. Предполагалось, что эти системы будут обеспечивать простоту управления за счет возможности общения с пользователями при помощи естественного языка. Эти системы должны были самообучаться, использовать накапливаемые в памяти знания для решения различного рода задач, предоставлять пользователям экспертные консультации, причем от пользователя не требовалось быть специалистом в информатике. Предполагалось, что человек сможет использовать ЭВМ пятого поколения так же легко, как любые бытовые электроприборы типа телевизора, магнитофона и пылесоса. Вскоре вслед за японским стартовали американский и европейский проекты.
Появление таких систем могло бы изменить технологии за счет использования баз знаний и экспертных систем. Основная суть качественного перехода к пятому поколению ЭВМ заключалась в переходе от обработки данных к обработке знаний. Японцы надеялись, что им удастся не подстраивать мышление человека под принципы функционирования компьютеров, а приблизить работу компьютера к тому, как мыслит человек, отойдя при этом от фон неймановской архитектуры компьютеров. В 1991 году предполагалось создать первый прототип компьютеров пятого поколения.
Теперь уже понятно, что поставленные цели в полной мере так и не были достигнуты, однако этот проект послужил импульсом к развитию нового витка исследований в области искусственного интеллекта и вызвал взрыв интереса к логическому программированию. Так как для эффективной реализации традиционная фон неймановская архитектура не подходила, были созданы специализированные компьютеры логического программирования PSI и PIM. В качестве основной методологии разработки программных средств для проекта ЭВМ пятого поколения было избрано логическое программирование, ярким представителем которого является язык Пролог. Думается, что и в настоящее время Пролог остается наиболее популярным языком искусственного интеллекта в Японии и Европе (в США, традиционно, более распространен другой язык искусственного интеллекта - язык функционального программирования Лисп). Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique во французском варианте и PROgramming in LOGic — в английском). Пролог основывается на таком разделе математической логики, как исчисление предикатов. Точнее, его базис составляет процедура доказательства теорем методом резолюции для хорновских дизъюнктов.
В истории возникновения и развития языка Пролог можно выделить следующие этапы. В 1965 году в работе "A machine oriented logic based on the resolution principle", опубликованной в 12 номере журнала "Journal of the ACM", Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название "принцип резолюции". На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров. Робинсон модифицировал этот метод так, что он стал пригоден для автоматического, компьютерного использования, и, кроме того, разработал эффективный алгоритм унификации, составляющий базис его метода.
В 1973 году "группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (от Programmation en Logique). Она и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алана Колмероэ. Программа была написана на Фортране и работала довольно медленно. Большое значение для развития логического программирования имела работа Роберта Ковальского "Логика предикатов как язык программирования" (Kowalski R. Predicate Logic as Programming Language. IFIP Congress, 1974), в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов. Кстати, известно, что Ковальский и Колмероэ работали вместе в течение одного лета. В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции.
В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, который послужил прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как "эдинбургская версия", фактически стала первым и единственным стандартом языка. Алгоритм, использованный при его реализации, послужил прототипом для многих последующих реализаций языка. Как правило, если современная Пролог-система и не поддерживает эдинбургский Пролог, то в ее состав входит подсистема, переводящая прологовскую программу в "эдинбургский" вид. Имеется, конечно, стандарт ISO/IEC 13211– 1:1995, но его поддерживают далеко не все Прологсистемы. В 1980 году Кларк и Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ. В 1981 году стартовал вышеупомянутый проект Института по разработке методов создания компьютеров нового поколения.
На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWI Prolog, UNSW Prolog и т. д.
В нашей стране были разработаны такие версии Пролога как Пролог-Д (Сергей Григорьев), Акторный Пролог (Алексей Морозов), а также Флэнг (А. Манцивода, Вячеслав Петухин). Стерлинг и Шапиро в книге "Искусство программирования на языке Пролог" пишут: "Зрелость языка означает, что он больше не является доопределяемой и уточняемой научной концепцией, а становится реальным объектом со всеми присущими ему пороками и добродетелями. Настало время признать, что хотя Пролог и не достиг высоких целей логического программирования, но, тем не менее, является мощным, продуктивным и практически пригодным формализмом программирования".
Prolog — это язык программирования для символических, нечисловых вычислений. Он особенно хорошо приспособлен для решения проблем, которые касаются объектов и отношений между объектами. Рассотрим пример: семейные отношения. Тот факт, что Том является одним из родителей Боба, можно записать на языке Prolog следующим образом:
19812061595parent( tom, bob).
В данном случае в качестве имени отношения выбрано слово parent а tom и bob являются параметрами этого отношения. По причинам, которые станут понятными позже, такие имена, как tom, записываются со строчной буквой в начале. Все дерево семейных отношений, показанное на рис. 1.1, определено с помощью следующей программы Prolog:
parent( pain, bob).
parent( tom, bob).
parent( tom, liz ).
parent( bob, ann).
parent( bob, pat).
parent( pat, jim).
Эта программа состоит из шести предложений, каждое из которых объявляет один факт об отношении parent. Например, факт parent ( tom, bob) представляет собой конкретный экземпляр отношения parent. Такой экземпляр называют также связью. В целом отношение определяется как множество всех своих экземпляров.
После передачи соответствующей программы в систему Prolog последней можно задать некоторые вопросы об отношении parent, например, является ли Боб одним из родителей Пэт? Этот вопрос можно передать системе Prolog, введя его на терминале:
?- parent( bob, pat).
Обнаружив, что это — факт, о существовании которого утверждается в программе, Prolog отвечает: «Да». А если задать другой вопрос, например ?- parent( bob, pat). Система ответит «нет» поскольку в программе нет упоминания о том, что Лиз является одним из родителей Пэт.
Кроме того, системе можно задать более интересные вопросы. Например, кто является родителями Лиз?
?- parent( X, liz ) .
На этот раз Prolog ответит не просто "yes" или "nо", а сообщит такое значение X, при котором приведенное выше утверждение является истинным. Поэтому ответ будет таковым:
X = tоm
Вопрос о том, кто является детьми Боба, можно сообщить системе Prolog следующим образом:
?- parent( bob, X).
На этот раз имеется больше одного возможного ответа. Система Prolog в начале выдаст в ответ одно решение:
X — ann
Теперь можно потребовать у системы сообщить еще одно решение (введя точку с запятой), и Prolog найдет следующий ответ:
X - pat
Если после этого будут затребованы дополнительные решения, Prolog ответит "nо", поскольку все решения уже исчерпаны.
Этой программе может быть задан еще более общий вопрос о том, кто является чьим родителем? Этот вопрос можно также сформулировать иным образом: Найти X и Y, такие, что X является одним из родителей Y.
Этот вопрос может быть оформлен на языке Prolog следующим образом:
?- parent ( х, Y) .
Можно задать еще более сложный вопрос, например, кто является дедушками и бабушками Джима. Поскольку в программе непосредственно не предусмотрено использование соответствующего отношения grandparent, этот запрос необходимо разбить на следующие два этапа (рис. 1.2).
1627743631. Кто является одним из родителей Джима? Предположим, что это — некоторый объект Y.
2. Кто является одним из родителей Y Предположим, что это — некоторый объект X.
Х = bob
Y = pat
Этот составной запрос можно прочитать таким образом: найти такие X и Y, которые удовлетворяют следующим двум требованиям:
parent ( Y, jim) и parert ( X, У)
Безусловно, такое же действие может быть выполнено и в программе Prolog, поэтому запрос:
?- parent(X, Y), parent( Y, jim).

Турбо Пролог (ТП) http://www.codingrus.ru/articles.php?cat_id=16 накладывает некоторые ограничения на имена объектов и предикатов, используемых в программах. Стандартные имена ТП должны состоять не более, чем из 250символов, среди которых допускаются буквы латинского алфавита (A,...,Z; a,...,z), цифры (1,...,9,0) и знак подчеркивания. Имена атомов и предикатов в ТП должны начинаться со строчной буквы, а имена объектов переменных -с прописной. Для атомов в ТП допустимы нестандартные имена, которые заключаются в двойные кавычки и могут содержать любые символы. Это позволяет использовать при именовании объектов-атомов прописные буквы (например, "Pentium","Moscow", "Peter"), символы национальных алфавитов(например, кириллицу - "Рязань", "компьютер") и разделительные пробелы (например, "Intel 80486","Manchester United", "Рязанская радиотехническая академия"). Среди объектов-переменных выделяется анонимная переменная, обозначаемая одним символом подчеркивания. Подобная переменная не требует выделения памяти подхранение ее значения и после выполнения текущей операции это значение теряется. Язык ТП допускает шесть стандартных типов объектов(данных), приведенных в табл.1. На базе этих стандартныхтипов пользователь может конструировать свои собственные типы данных (см. раздел domains). Символьные данные типов symbol и string отличаются способом хранения. При объявление типа данных symbol ТП-система выполняет построение в оперативной памяти ПЭВМ таблицы симовлов, что обеспечивает наиболее быстрый поиск информации. При использовании данных типа string построение подобной таблицы не выполняется.

В программах на ТП допускается использование комментариев, которые могут располагаться в произвольном месте. В ТП существуют два вида комментариев: многострочные и однострочные. Многострочный комментарий начинается с последовательности символов "/*" и заканчивается символами "*/". Однострочный комментарий начинается с символа "%", который может располагаться в любом месте строки. Информация, расположенная после этого символа до конца строки, воспринимается как комментарий. Основная часть программы на ТП (раздел clauses - см. п.2.2) состоит из предложений. Каждое предложение может включать в себя один или несколько предикатов, соединенных логическими операциями, и должно заканчиваться точкой. Предложение может располагаться на нескольких строках. Различают безусловные и условные предложения. Безусловное предложение называется фактом и состоит из единственного предиката, определяющего наличие указанного отношения между конкретными объектами-атомами, заданными в качестве аргументов предиката. Предложение-факт не зависит от каких-либо условий и является всегда истинными. Условное предложение, называемое правилом, описывает отношение, возникающее при наличии определенных условий. Правило представляет собой сложное предложение, которое состоит из заголовка и тела правила. В заголовке описывается предикат, для которого сформулировано правило, а тело правила описывает условия, при которых отношение, определяемое предикатом, существует (т.е. предикат истинен). Заголовок и тело правила соединяется при помощи ключевого слова if (если) или пары символов ":-". Тело правила может включать несколько предикатов, которые соединяются между собой при помощи логических операций or (и) и and (или). Ключевые слова or и and могут быть заменены символами ";" и "," соответственно. Сложные правила (например, рекурсивные) могут состоять из нескольких предложений.
Лекция 3. Введение в экспертные системы
Экспертные системы и предметная область
Элементы экспертной системы
Преимущества экспертных систем.
Представление знаний в экспертных системах
Примеры существующих экспертных систем
Наиболее подходящие области применения экспертных систем
1.Экспертные системы и предметная область
Экспертные системы были разработаны как научно-исследовательские инструментальные средства в 1960-х годах и рассматривались в качестве искусственного интеллекта специального типа, предназначенного для успешного решения сложных задач в узкой предметной области, такой как медицинская диагностика заболеваний. (Причем) Классическая задача создания программы искусственного интеллекта общего назначения, которая была бы способна решить любую проблему без конкретных знаний в предметной области (например, медицинской диагностики заболеваний), оказалась слишком сложной. Коммерческое внедрение экспертных систем произошло в начале 1980-х годов, и с того времени экспертные системы получили очень широкое распространение.
В качестве контрпримера можно указать, что многие специалисты пытались создавать экспертные системы для предсказания тенденций на фондовой бирже; фактически подобные системы постоянно применяются на Уолл-стрит. Однако, если они и способны отслеживать взлеты и падения, но все же действуют они не лучше по сравнению с их создателями. Значительным преимуществом экспертных систем является то, что они способны осуществлять торговлю в реальном времени в таких условиях, что критическими становятся задержки при совершении биржевых сделок на миллисекунды, поскольку система конкурента может обнаружить такую же тенденцию, как и ваша, и быстрее выдать ордера на покупку или продажу акций стоимостью в сотни миллионов долларов, притом что быстродействие обеих систем будет намного выше по сравнению с реакцией человека.
Эксперт – это личность, обладающая специальными знаниями и навыками, которые неизвестны или недоступны для большинства людей. Все экспертные системы основаны на знаниях. По своей структуре экспертная система подразделяется на два основных компонент – базу знаний и машину логического вывода. База знаний содержит знания, на основании которых машина логического вывода формирует заключения.
Экспертная система не является универсальным решателем задач, как знания эксперта относятся только к одной предметной области, так и экспертные системы в целом предназначены для использования в качестве экспертов в одной предметной области. Например, обычно нельзя рассчитывать на то, что эксперт в области шахмат будет обладать экспертными знаниями, относящимися к медицине. Экспертные знания в одной предметной области не переносятся автоматически на другую область.
Предметная область — это специальная проблемная область, такая как медицина, финансы, наука и техника, в которой может очень хорошо решать задачи лишь определенный эксперт.
Знания эксперта, касающиеся решения конкретных задач, называются областью знаний эксперта. Например, медицинская экспертная система, предназначенная для диагностирования инфекционных заболеваний, должна обладать большим объемом знаний об определенных симптомах, вызванных инфекционными заболеваниями. В этом случае областью знаний является медицина, а сами знания состоят из сведений о заболеваниях, симптомах и методах лечения.
В какой-либо конкретной экспертной системе, например, в системе диагностирования инфекционных заболеваний, обычно отсутствуют знания, относящиеся к другим областям, например, в данном случае к такой области медицины, как хирургия или педиатрия. Экспертная система может обладать знаниями об инфекционных заболеваниях, равными или превышающими знания отдельно взятого эксперта-человека, но эта экспертная система может не иметь никаких сведений из других областей знаний, если в нее не будут введены знания, относящиеся к одной из этих проблемных областей.
В области знаний, сведениями из которой располагает экспертная система, эта экспертная система проводит рассуждения или делает логические выводы по такому же принципу, как рассуждал бы эксперт-человек. Это означает, что на основании определенных фактов путем рассуждений формируется логичное, оправданное заключение, которое следует из этих фактов. Например, если ваш близкий родственник не разговаривал с вами месяц, вы могли бы прийти к выводу, что ему просто нечего вам сказать. Но это лишь один из нескольких возможных логических выводов.
2.Элементы экспертной системы
Элементы типичной экспертной системы показаны на рис ниже. В системе, основанной на правилах, знания в проблемной области, необходимые для решения задач, закодированы в форме правил и содержатся в базе знаний. Безусловно, для представления знаний наиболее широко применяются правила, но в экспертных системах других типов применяются также иные способы представления.
Экспертная система состоит из описанных ниже компонентов.
•Пользовательский интерфейс. Механизм, с помощью которого происходит общение пользователя и экспертной системы.
•Средство объяснения. Компонент, позволяющий объяснить пользователю ход рассуждений системы.
•Рабочая память. Глобальная база фактов, используемых в правилах.
•Машина логического вывода. Программный компонент, который обеспечивает формирование логического вывода (принимая решение о том, каким правилам удовлетворяют факты или объекты), располагает выполняемые правила по приоритетам и выполняет правило с наивысшим приоритетом.
•Рабочий список правил. Созданный машиной логического вывода и расположенный по приоритетам список правил, шаблоны которых удовлетворяют фактам или объектам, находящимся в рабочей памяти. Правила помещаются в рабочий список правил, если все его шаблоны удовлетворены, такое правило называется активизированным. Существует возможность в качестве условия указать отсутствие определенных фактов в рабочей области, это необходимо, например, когда горит зеленый и красный свет на светофоре одновременно, что служащий признаком неисправности, а не командой двигаться или стоять.
•Средство приобретения знаний. Автоматизированный способ, позволяющий пользователю вводить знания в систему, а не привлекать к решению задачи явного кодирования знаний инженера по знаниям.

Структура экспертной системы, основанной на правилах
Мы с вами уже знаем, что знания в экспертной системе представляются с помощью продукционных правил, выраженных в форме If - Then. Поэтому базу знаний по-другому называются
Каждое правило обозначается именем. Участок правила между частями IF и THEN правила упоминается под разными именами, такими как антецедент, условная часть или просто левая часть (left-hand-side — LHS).
Вслед за частью THEN правила находится список действий, которые должны быть выполнены после запуска правила. Эта часть правила называется консеквентом, или правой частью (Right-Hand Side — RHS).
В системе, основанной на правилах, машина логического вывода определяет, какие антецеденты правил (если таковые вообще имеются) выполняются согласно фактам. В качестве стратегий решения задач в экспертных системах обычно используются два общих метода логического вывода: прямой логический вывод и обратный логический вывод.
Прямой логический вывод представляет собой метод формирования рассуждений от фактов к заключениям, которые следуют из этих фактов. Например, если перед выходом из дома вы обнаружите, что идет дождь (факт), то должны взять с собой зонтик (заключение).
Обратный логический вывод предусматривает формирование рассуждений в обратном направлении — от гипотезы (потенциального заключения, которое должно быть доказано) к фактам, которые подтверждают гипотезу. Например, если вы не выглядываете наружу, но кто-то вошел в дом с влажными ботинками и зонтиком, то можно принять гипотезу, что идет дождь. Чтобы подтвердить эту гипотезу, достаточно спросить данного человека, идет ли дождь. В случае положительного ответа будет доказано, что гипотеза истинна, поэтому она становится фактом. Как уже было сказано выше, гипотеза может рассматриваться как факт, истинность которого вызывает сомнение и должна быть установлена. В таком случае гипотеза может интерпретироваться как цель, которая должна быть доказана.
Преимущества экспертных систем.
Как описано ниже, экспертные системы обладают многими привлекательными особенностями.
•Повышенная доступность. Для обеспечения доступа к экспертным знаниям могут применяться любые подходящие компьютерные аппаратные средства. В определенном смысле вполне оправдано утверждение, что экспертная система — это средство массового производства экспертных знаний.
•Уменьшенные издержки. Стоимость предоставления экспертных знаний в расчете на отдельного пользователя существенно снижается.
•Уменьшенная опасность. Экспертные системы могут использоваться в таких вариантах среды, которые могут оказаться опасными для человека.
•Постоянство. Экспертные знания никуда не исчезают. В отличие от экспертов-людей, которые могут уйти на пенсию, уволиться с работы или умереть, знания экспертной системы сохраняются в течение неопределенно долгого времени.
•Возможность получения экспертных знаний из многих источников. С помощью экспертных систем могут быть собраны знания многих экспертов и привлечены к работе над задачей, выполняемой одновременно и непрерывно, в любое время дня и ночи. Уровень экспертных знаний, скомбинированных путем объединения знаний нескольких экспертов, может превышать уровень знаний отдельно взятого эксперта-человека.
•Повышенная надежность. Применение экспертных систем позволяет повысить степень доверия к тому, что принято правильное решение, путем предоставления еще одного обоснованного мнения эксперту-человеку или посреднику при разрешении несогласованных мнений между несколькими экспертами-людьми. (Разумеется, такой метод разрешения несогласованных мнений не может использоваться, если экспертная система запрограммирована одним из экспертов, участвующих в столкновении мнений.) Решение экспертной системы должно всегда совпадать с решением эксперта; несовпадение может быть вызвано только ошибкой, допущенной экспертом, что может произойти, только если эксперт-человек устал или находится в состоянии стресса.
•Объяснение. Экспертная система способна подробно объяснить свои рассуждения, которые привели к определенному заключению. А человек может оказаться слишком усталым, не склонным к объяснениям или неспособным делать это постоянно. Возможность получить объяснение способствует повышению доверия к тому, что было принято правильное решение.
•Быстрый отклик. Для некоторых приложений может потребоваться быстрый отклик или отклик в реальном времени. В зависимости от используемого аппаратного и программного обеспечения экспертная система может реагировать быстрее и быть более готовой к работе, чем эксперт-человек. В некоторых экстремальных ситуациях может потребоваться более быстрая реакция, чем у человека; в таком случае приемлемым вариантом становится применение экспертной системы, действующей в реальном времени.
•Неизменно правильный, лишенный эмоций и полный ответ при любых обстоятельствах. Такое свойство может оказаться очень важным в реальном времени и в экстремальных ситуациях, когда эксперт-человек может оказаться неспособным действовать с максимальной эффективностью из-за воздействия стресса или усталости.
Кроме того, процесс разработки экспертной системы приносит и косвенное преимущество, так как знания экспертов-людей должны быть предварительно преобразованы в явную форму для ввода в компьютер. Поскольку знания затем становятся выраженными в явной форме, а не присутствуют неявно в мозгу эксперта, появляется возможность проверять знания на правильность, непротиворечивость и полноту. После такой проверки, возможно, придется откорректировать эти знания (за что эксперт вряд ли будет признателен!).
Первым успешным коммерческим применением экспертных систем стало создание системы XCON/R1 в компании Digital Equipment Corporation. Оказалось, что эта система обладает намного более широкими знаниями о том, как следует создавать конфигурации компьютерных систем, по сравнению с любым отдельно взятым экспертом-человеком.
Знания, необходимые для небольших систем, могут быть взяты из книг, журналов или любой другой общедоступной документации.
43180684530В отличие от этого классическая экспертная система воплощает в себе ранее не писанные знания, которые должны быть получены от эксперта с помощью обширных интервью, проводимых инженером по знаниям в течение длительного периода времени. Такой процесс создания экспертной системы называется инженерией знаний и осуществляется инженером по знаниям. Инженерией знаний называют получение знаний от эксперта-человека или из других источников и последующее представление знаний в экспертной системе.
Основные этапы разработки экспертной системы.
Вначале инженер по знаниям устанавливает диалог с экспертом-человеком, чтобы выявить знания эксперта. Этот этап аналогичен этапу работы, выполняемому системным проектировщиком при обычном программировании в ходе обсуждения требований к системе с клиентом, для которого создается программа. Затем инженер по знаниям представляет знания в явном виде для внесения в базу знаний. После этого эксперт проводит оценку экспертной системы и передает критические замечания инженеру по знаниям. Такой процесс повторяется снова и снова, до тех пор, пока эксперт не оценит результаты работы системы как удовлетворительные.
Формализация знаний экспертов в виде правил — нелегкая проблема, особенно если знания экспертов еще до сих пор систематически не исследовались. К тому же эксперты должны знать пределы своих знаний и объективно оценивать качество своего совета в тех условиях, когда задача по своей сложности достигает их границ незнания. Если в проект экспертной системы явно не заложены способности справляться с неопределенностью, то система будет выдавать рекомендации с прежней уверенностью, даже если предоставляемые ей данные являются слишком неточными или неполными. Рекомендации экспертной системы, как и рекомендации эксперта-человека, должны корректно показывать снижение своего качества по мере приближения к границам незнания, а не внезапно становиться ложными.
Представление знаний в экспертных системах
Знания могут быть представлены в экспертной системы многими способами. Одним из широко применяемых методов представления знаний являются правила в форме IF THEN.
Одним из наиболее значительных результатов, продемонстрированных Ньюэллом и Саймоном, оказалось то, что значительная часть человеческого понимания, или познания, можно представить в виде продукционных правил IF-THEN (ЕСЛИ-ТО). Например, IF "создается впечатление, что пойдет дождь" THEN "возьмите с собой зонтик". Правило соответствует небольшой, модульной коллекции знаний, называемой фрагментом. Фрагменты организованы в свободной форме и снабжены связями, которые ведут к относящимся к ним фрагментам знаний. В одной из теорий так и утверждается, что вся человеческая память организована в виде фрагментов. Ниже приведен пример правила, представляющего фрагмент знаний.
IF двигатель автомобиля не запускается и
бензиномер остановился на нуле
THEN заполните бак бензином
Ньюэлл и Саймон популяризировали использование правил для представления человеческих знаний и показали, как могут быть выполнены стандартные рассуждения с помощью правил. А психологи, специализирующиеся в области когнитивной психологии, использовали правила в качестве модели для объяснения процесса обработки информации человеком. Основная идея состоит в том, что мозг выделяет стимулы из сенсорной входной информации. Стимулы активизируют в долговременной памяти соответствующие правила, с помощью которых формируется соответствующий отклик. Долговременная память представляет собой место хранения постоянных знаний человека. Например, все люди усвоили примерно такие правила:
IF наблюдается пламя THEN возможно происходит пожар
IF наблюдается дым THEN где-то может происходить пожар
IF слышна пожарная сирена THEN где-то может происходить пожар
Долговременная память человека содержит много правил, имеющих простую структуру IF-THEN. В действительности шахматный гроссмейстер может хранить в своей памяти 50 тысяч или больше фрагментов знаний о шаблонах шахматных позиций, и не заниматься постоянным вычислением на семь шагов вперед. В отличие от долговременной памяти, кратковременная память используется для временного хранения знаний в период решения задачи. Хотя долговременная память может хранить сотни тысяч или даже больше фрагментов, емкость кратковременной, или рабочей, памяти мала — от четырех до семи фрагментов. В качестве простого примера, подтверждающего этот факт, попытайтесь мысленно представить себе визуально несколько цифр. Большинство людей способны одновременно видеть внутренним взглядом от четырех до семи цифр. Безусловно, люди способны запоминать гораздо больше, чем только цифры в количестве от четырех до семи. Но эти цифры и многие другие сведения успешно хранятся в долговременной памяти, причем для обеспечения их записи на постоянное хранение требуется время.
В одной из теорий предполагается, что кратковременная память представляет то количество фрагментов, которые могут быть активными одновременно; в этой теории процесс решения задач человеком рассматривается как перераспределение таких активизированных фрагментов в мозгу. В конечном итоге фрагмент может быть активизирован с такой интенсивностью, что будет выработана сознательная мысль.
Еще одним элементом, необходимым для решения задач человеком, является когнитивный процессор. Когнитивный процессор предпринимает попытки найти правила, которые должны быть активизированы с помощью соответствующих стимулов. Для этого недостаточно взять первое попавшееся правило. Например, одно правило указывает, когда следует заполнять бак бензином, а другое — как следует себя вести, услышав звук сирены, но вряд ли следует стремиться поскорее заполнить бак бензином, как только в воздухе раздастся звук сирены. Должно активизироваться только то правило, которое соответствует стимулу. Если имеется много правил, которые могут быть активизированы одновременно, то когнитивный процессор должен выполнить операцию разрешения конфликтов, чтобы определить, какое правило имеет наивысший приоритет. После этого должно быть выполнено соответствующее правило с наивысшим приоритетом.
В таком случае необходимо вначале выполнить действие одного правила, а затем — другого. В современных экспертных системах когнитивному процессору соответствует машина логического вывода.
Модель решения задач человеком, предложенная Ньюэллом и Саймоном и состоящая из долговременной памяти (правил), кратковременной памяти (рабочей памяти) и когнитивного процессора (машины логического вывода), представляет собой фундамент современных экспертных систем, основанных на правилах.
Примеры существующих экспертных систем
Коммерческие оболочки экспертных систем
Под "оболочками : (shells) понимают "пустые" версии существующих экспертных систем, т.е. готовые экспертные системы без базы знаний. Примером такой оболочки может служить EMYCIN (Empty MYCIN - пустой MYC1N), которая представляет собой незаполненную экспертную систему MYCIN. Достоинство оболочек в том, что они вообще не требуют работы программистов для создания готовой экспертной системы. Требуется только специалисты) в предметной области для заполнения базы знаний. Однако если некоторая предметная область плохо укладывается в модель, используемую в некоторой оболочке, заполнить базу знаний в этом случае весьма не просто.
ACQUIRE- - система обнаружения знаний и оболочка экспертной системы. Это - законченная среда для разработки и поддержки интеллектуальных прикладных программ. Система содержит в себя методологию пошагового представления знаний, что позволяет специалистам в проблемной области непосредственно участвовать в процессе приобретения, структурирования и кодирования знания. (Прямое участие специалиста в проблемной области улучшает качество, законченность и точность приобретенного знания, снижает время разработки и эксплуатационные расходы). Особенностью оболочки является структурированный подход к приобретению знаний; модель приобретения знаний основана на распознавании образов; знания представлены как объекты, продукционные правила и системы правил в табличной форме; оболочка позволяет выполнять обработку неопределенных качественных знаний; содержит средства вывода и документацию баз знаний в среде гипертекста. Web страница находится по адресу http://vvv.com/ai/
ACQUIRE - SDK - программное Средство разработки, снабженное встроенными библиотеками для Мs-Dos, и SCO Unix; DLL'S для Asmetrix TooBook, Windows, Windows NT, Windows 95 и WIN 32. Полный пакет (система обнаружения знания и оболочка экспертной системы) стоит $ 995 для Windows 3.1 и включает в себя справочник, обучающую программу. Дополнительную информацию можно получить по адресу http://vvv.com/ai/ Пример прикладной программы ACQUIRE приведен на странице http://vvv.com/ai/demos/whale.html
ACTIVATION FRAMEWORK работает на персональных компьютерах (под управлением операционных систем DOS, Windows) и на автоматизированных рабочих станциях UNIX. Это - не традиционная оболочка экспертной системы, а скорее инструмент для формирования прикладных программ обработки данных в реальном времени. Система конкурирует с оболочкой G2 фирмы GENSYM email rtis@world.std.com.
ActiveAgentX может применяться в системах поддержки принятия решений, содержащих правила , которые могут быть автоматически получены по корпоративным сетям при использовании WEB-браузеров Microsoft Windows 95 или NT. ActiveAgentX может быть также встроен внутрь Java аплетов, которые используются браузером Microsoft Internet Explorer или автономно, как прикладная программа Java, написанная на языке Microsoft Java или Visual J ++. При использовании в сети WWW ActiveAgentX предоставляет вполне развитые средства создания экспертных систем, которые используют интерактивные средства представления интеллектуальной информации на машинах клиента или в Web-браузерах. пакет создан в Haley Corporation. WEB - страница фирмы имеет адрес http://www.haley.com/
AION. Система разработки программ (ADS) выполняется на различных платформах, включая DOS, OS/2, SunOS, Microsoft Windows, и VMS. Она включает в себя объектно-ориентированное представление знаний, прямой, обратный, двунаправленный поиск решения, а также правила сопоставления с образцом, графику, запросы на\из других языков (C, Паскале, ...), а также графический интерфейс пользователя.
ANGOSS KNOWLEDGE SEEKER - то инструмент, основанный на данных, которые могут использоваться для получения базы знаний, состоящей из правил, связанных с базой данных причинно-следственными связями. Версия DOS стоит $ 799 и версия под Windows $ 899.
ART*Enterprise - самая последняя из сред разработки, основанных на правилах, ведущих начало от систем ИИ середины 1980-ых. Это - среда разработки прикладных программ широкого применения, объединяющая в себе правила, объектно-ориентированную систему, которая содержит такие особенности, которые в настоящее время не представлены ни в C++, ни в языке Smalltalk; и содержит большую совокупность классов объектов для разработки на различных платформах (от Windows до OS/2 и Unix),поддерживает доступ к базам данных (основанный SQL- и ODBC-запросах), и мультизадачный режим доступа. ART*ENTERPRISE среда поддерживает обратный поиск решения от фактов к цели; можно также реализовать поиск решения от цели к фактам. WEB-адрес http://www.brightware.com/
ARITY Expert Development Package - это экспертная система, которая интегрирует продукционное и фреймовое представления знаний с различного рода коэффициентами уверенности. OS/2 версия стоит $495 и DOS версия - $295. Компания CAM Sofware предлагает два инструментальных средства - экспертные системы DClass и LogicTree. email 73677.2614@compuserve.com.
CAM Software содержит два инструмента для создания экспертных систем: DClass и LogicTree Система DClass - использует дерево решений, предназначена для построения прикладных программ. LogicTree - система принятия решений, разработанная для использования профессионалами – непрограммистами
COMDALE/C, COMDALE/X и ProcessVision. COMDALE/C - экспертная система реального времени, предназначенная для наблюдения и контроля над процессами в условиях производства. . + COMDALE/C позволяет вырабатывать рекомендации, заключения об управляющих воздействиях в непрерывном процессе принятия решения. Она обрабатывает неопределенные знания и данные, и имеет открытую архитектуру. Другие особенности включают: объектно-ориентированную конфигурацию; возможности организации работы в сети; обработку прерываний; хранение и обработку данных; поддерживает работу с базой данных в реальном масштабе времени, и интерфейсы с системами передачи данных, такими как PLCs и другими устройствами ввода-вывода. + COMDALE/X - консультационная экспертная система, которая работает в режиме реального времени. Для принятия решения система организует диалог с пользователем. COMDALE/X совместно с системой COMDALE/C используется как инструмент разработки экспертных систем реального времени. COMDALE/X позволяет включить гипертекст в экспертную систему, что позволяет создавать hyper-справочники с удобным интерфейсом.
+ PROCESS Vision - пакет программ для управления процессами в реальном времени, базируется на открытой и модульной архитектуре. ProcessVision содержит графический интерфейс оператора; объектно-ориентированный дисплей, выполняет проверку правильности показаний датчиков и поддерживает связь с неограниченным количеством производственной контрольно-измерительной аппаратурой в одной глобальной среде. email info@comdale.com. WEB страница компании имеет адрес http://www.comdale.com/
C - PRS (Процедурно - ориентированная система рассуждений, написанная на языке C) реализует процедурное представление знаний. Это позволяет пользователю выражать и представить условные последовательности комплексных действий и гарантировать их выполнение в реальном времени в среде прикладной программы. Система C - PRS полезна в процессе контроля и управления технологическими процессами. PRS технология применялась в различных задачах и запросах в реальном времени, например, для контроля над несколькими спутниковыми системами NASA, в системах диспетчерского управления сетей электросвязи (Телесвязь Австралия), при управлении подвижными роботами (SRI, LAAS), в системе контроля над полетами и в системе обнаружения самолетов (Grumman). C - PRS работает на многочисленных платформах и операционных системах, включая SPARC, DECstation, Sony News, Hewlett Packard, VxWorks, и другие.
CPR CPR (Прикладная система, основанная на правилах) содержит библиотеку классов C++ и Help! CPR - службу поддержки клиентов и прикладную программу, основанную на знаниях, которая использует CPR. Адрес: The Haley Enterprise, Inc., 413 Orchard Street, Sewickley, PA 15143, телефон 800-233-2622 (412-741-6420), факс 412-741-6457, email info@haley.com. Смотрите WEB - страницу по адресу http://www.haley.com/
Crystal. Работает на персональных компьютерах и снабжен интеллектуальным интерфейсом. Поддерживает интерфейс с dBase, Lotus-1-2-3, ASCII-файлами, программами, написанными на языке С. Имеется возможность создания гибридных ЭС. В состав оболочки включена обширная библиотека встроенных функций. Интерфейс разработчика: меню, редактор баз знаний, графические средства, стердства подготовки текстовых файлов и экранов, стердства трассиловки и отладки. В базу знаний может входить не более 300 правил. Возможно построение иерархических баз знаний, взаимодействующих через файлы импорта и экспорта. Вследствие этого не накладывается ограничений на размер базы знаний.
The Easy Reasoner (TM) - Поисковая система, основанная на поиске подходящих рассуждений в адаптивной ассоциативной памяти. Система отыскивает в памяти событие, подобное новому событию, используя " Запрос на пример". Поддерживает базы данных xBase, ODBC, SQL. Система автоматически фильтрует помехи для упрощения решающих деревьев; эффективно отыскивает события, подобные новому в больших базах данных; поддерживает составные индексы в базе данных; классифицирует новую информацию, используя любое решающее дерево в автоматическом или интерактивном режиме. Выполняет адаптивное, контекстно-зависимое, заданное по умолчанию рассуждение; вычисляет адаптивную оценку, используя решающие деревья; восстанавливает (отыскивает) подобные записи по контексту; различает различные формы записи английских слов; автоматически определяет объем информации в слове. Easy Reasoner под 16- разрядный Windows стоит $ 249, Easy Reasoner под 32 разрядный Windows, стоит $ 499, версия для OS/2 стоит $ 499. WEB - страница фирмы имеет адрес http://www.haley.com/
ECLIPSE работает на персональных компьютерах (DOS, Windows), а также имеются версии для систем V Unix и POSIX. Синтаксис языка, используемого в пакете, совместим с языком системы CLIPS, разработанной для NASA. Отличия заключаются в управлении данными путем сопоставления с образцом, использовании прямого и обратного вывода, в поддержке множества целей, объектно-ориентированном представлении знаний и интегрировании с dBase. WEB - страница фирмы имеет адрес http://www.haley.com/ email info@haley.com. Стоимость пакета, работающего в среде 16 разрядного Windows - $499 и $999 для 32 разрядного Windows или OS/2 Стоимость пакета для работы в среде UNIX составляет $1,999.
Esteem - инструмент для работы в среде Windows, который интегрирует условные рассуждения с правилами.
EXSYS DEVELOPER работает в среде МС-ДОС, MS WINDOWS, Macintosh, SunOS, Solaris, Unix и Vax. Система поддерживает обратный вывод от фактов к цели, линейное программирование, нечеткую логику, нейронные сети, и имеет SQL интерфейс. Для получения дополнительной информации, посетите их страницу http://www.exsysinfo.com/Wren/wren.html. Демонстрационный пример приведен на странице http://inf.susu.ac.ru/~pollak/expert/commercial/www.multilogic.com. Email info@exsysinfo.com.
FLEX - гибридная экспертная система, работающая на различных платформах. Система предлагает фреймовое, процедурное и продукционное представление знаний. FLEX чередует прямой и обратный методы поиска решений, множественное наследование свойств, присоединенные процедуры, автоматическую систему вопросов и ответов. Правила, фреймы и вопросы написаны на естественном англо-подобном языке. Язык спецификаций (KSL) позволяет разрабатывать легко читаемые и простые в поддержке базы знаний. FLEX написан на языке Пролог. FLEX использовался в многочисленных коммерческих экспертных системах, например, в финансовых системах типа Администратор начисления пенсии. Цена системы для работы на персональном компьютере в среде Windows в пределах $1,000. Дополнительную информацию можно получить по http://www.lpa.co.uk/ Email: lpa@cix.compulink.co.uk.
G2 Фирма Gensym предлагает графическую, объектно-ориентированную среду для создания интеллектуальных прикладных программ, которые контролируют, диагностируют, и управляют динамическими событиями в сетевых и моделируемых средах. G2 для создания правил, моделей, и процедур использует структурированный естественный язык. Экспертная система G2 является основой всех прикладных программ фирмы Gensym. Программы включают в себя G2, видеоадаптер, который позволяет использовать визуальную среду программирования для создания интеллектуальных прикладных программ управления. NeurOn-Line и другие программы фирмы позволяют пользователям легко создавать нейросетевые прикладные программы. G2 совмещает выполнение правил и процедур в текущий момент времени со способностями рассуждений спустя некоторое время. РУКОВОДСТВО по G2 позволяет пользователям, легко создавать графические интерфейсы и системы диагностирования в реальном масштабе времени. Компания Telewindows Gensym's создала мощную более универсальную среду клиент/сервер, которая позволяет пользователям совместно использовать прикладные программы на G2. Gensym также предлагает мосты (программы) для связи с другими программам (на C и АДА) и системы передачи и обработки данных о движущихся объектах в реальном времени, включая реляционные базы данных, распределенные системы управления, и программируемые логические системы. Домашняя страница фирмы расположена по адресу http://www.gensym.com./
GBB - поддерживает фреймовые рабочие области, содержит высокоэффективный транслятор, фреймовые базы данных и библиотеку, которые поддерживают многомерные алгоритмы поиска целей;KS языки представлений знаний; Универсальные оболочки управления и утилиты администрирования порядком выполнения операторов; интерактивные, графические дисплеи для контроля и исследования; компоненты управления и рабочие области. Эти компоненты составляют инфраструктуру, необходимую для формирования прикладных программ. WWW страница имеет адрес: http://inf.susu.ac.ru/~pollak/expert/commercial/. Страница содержит демонстрационную версию. Адрес Blackboard Technology Group, Inc., 401 Main Street, Amherst, MA 01002, телефон 800-KSS-8990 or 413-256-8990, факс 413-256-3179. E-mail gbb-user-request@bn.cs.umass.edu.
GURU - оболочка экспертной системы, в который предлагается широкое разнообразие инструментальных средств обработки информации, объединенных с возможностями, основанными на знаниях, такими, вывод решения от фактов к цели, вывода решения от цели к фактам, смешанное формирование цепочки вывода, многозначные переменные и нечеткие рассуждения. email info@mdbs.com.
HUGIN - пакет программ для конструирования моделей, основанных на системах экспертных оценок в областях, характеризующихся существенной неопределенностью. Hugin система содержит удобную для использования дедуктивную систему вывода, основанную на вероятностных оценках, которую можно применить к сложным сетям с причинно-следственными вероятностными связями между объектами. WWW- страница HUGIN доступна по адресу http://inf.susu.ac.ru/~pollak/expert/commercial/ .Страница содержит демонстрационный пример экспертной системы. Email: info@hugin.dk.
Icarus - инструмент разработки экспертных систем для персональных компьютеров. Он включает интерфейс с Lotus и dBASE файлами, прямой и обратный выводы и Байесовские коэффициенты доверия. Адрес: Icarus, 11300 Rockville Pike, Rockville, MD 02852-3088, телефон 301-881-9350, факс 301-881-2542.
ILOG RULES - содержит высоко эффективный механизм логического вывода, основанный на правилах. Это - инструмент вывода от фактов к цели, написанный на языке C++ ( следовательно это объектно-ориентированный и поддерживающий передачу наследственных характеристик механизм). Система также снабжена библиотекой C++. Она выполняется фактически на любой Unix платформе, а также на персональных компьютерах, работающих в среде DOS или OS/2. Система позволяет транслировать правила в C / C ++ код, и строить объектно-ориентированную модель данных в C++. C / C ++ код может быть включен в условия правил и действия, связанные с правилами. e-mail info@ilog.com, info@ilog.fr. http://www.ilog.fr/
KEE, ProKappa, Kappa - это - средства разработки экспертных систем, которые выполняются на персональных компьютерах, автоматизированных рабочих станциях и Лисп-машинах. Особенностями сред являются: асинхронная передача данных; рассуждения, основанные на правилах.
Knowledge Craft - комплект инструментов для разработки экспертных систем, используемых в календарном планировании проекта, и конфигурации прикладных программ.
OPERATION EXPERT - графическое программное средство для определения повреждений в Интеллектуальных сетях связи. Система создана на основе программных средств фирмы Gensym (оболочки G2). Система использует модель сети и связанные с ней прикладные программы для отображения объектов и для описания их поведения и характеристик. Систем аподдерживает архитектуру клиент-сервер, учитывает параллельную обработку данных в реальном масштабе времени.
PROSPECT EXPLORER -экспертная система, использующая нейросетевые вычислительные технологии для помощи геологам в обнаружении горных аномалий. MIT - пакет программ для улучшения эффективности и снижения затрат в процессе выделения минералов. Использует различные факторы, начиная от параметров процесса выделения минерала и кончая климатическими факторами для создания нейросетевых моделей процесса. Программы созданы фирмой NMS (Австралия).Дополнительная информация:neuralmining@bigpond.com.
ReThink фиры Gensym - программный инструмент для графического проектирования, моделирования и оперативного управления бизнес - процессами. Опирается на пакет G2.






Наиболее подходящие области применения экспертных систем
Прежде чем приступать к созданию экспертной системы, очень важно определить, является ли приемлемым для решения рассматриваемой задачи подход, который основан на использовании экспертной системы. В частности, необходимо определить, должна ли экспертная система применяться вместо такого альтернативного подхода, как обычное программирование. Для выявления области применения, подходящей для использования экспертной системы, необходимо руководствоваться множеством факторов, перечисленных ниже, и найти ответы на указанные вопросы.
1.Может ли задача быть успешно решена с помощью обычного программирования? Если ответ на этот вопрос является положительным, то экспертную систему нельзя назвать наилучшим выбором.
2.Достаточно ли тщательно определены границы предметной области? Очень важно определить тщательно заданные пределы, в которых экспертная система должна обнаруживать свои знания и в которых должны проявляться ее возможности. Например, предположим, что требуется создать экспертную систему для диагностирования причин головной боли. Очевидно, что в базу знаний такой экспертной системы необходимо ввести медицинские знания врача-терапевта. Но для обеспечения глубокого понимания причин головной боли может также потребоваться ввести в базу знания о биохимии нервной системы, затем о той области биохимии, в рамках которой накапливаются знания о нервной системе человека, затем о химии, молекулярной биофизике и т.д., причем, возможно, даже о физике элементарных частиц. Знания, касающиеся причин головной боли, могут также присутствовать в других научных областях, таких как рефлексология, психология, психиатрия, физиология, наука о спорте. Общий вывод из этих рассуждений таков: начав перечислять научные дисциплины, касающиеся любой темы, остановиться просто невозможно. А чем больше знаний из различных научных областей введено в экспертную систему, тем она сложнее. При этом особенно затрудняется решение задачи координации всех экспертных знаний. Практический опыт показывает, насколько сложно бывает координировать работу групп экспертов разных специальностей, работающих над одними и теми же задачами, особенно если эти группы выдвигают противоречащие друг другу рекомендации. Впервые попытки координировать работу многочисленных экспертных систем были предприняты при создании систем HEARSAY II и HEARSAY III. Такие проекты стали наглядной демонстрацией сложности указанной задачи.
3.Есть ли необходимость и потребность в создании экспертной системы? Безусловно, создание экспертной системы — очень увлекательное занятие, но оно теряет смысл, если никто не собирается ее использовать. Например, если на предприятии уже имеется много экспертов-людей, то трудно обосновать необходимость создания экспертной системы по причине нехватки экспертных знаний людей.
4.Есть ли по крайней мере один эксперт-человек, желающий участвовать в этой работе? На предприятии должен быть хотя бы один эксперт, готовый принять участие в проекте, причем даже лучше, если он будет относиться к проекту создания экспертной системы с энтузиазмом. Далеко не все эксперты согласны подвергнуть свои знания проверке на наличие ошибок, а затем перенести их в компьютер. Причем, даже если многие эксперты желают участвовать в разработке, может оказаться целесообразным ограничить количество экспертов, участвующих в создании системы. Разные эксперты могут применять различные способы решения задачи, например, запрашивать разные диагностические тесты. Иногда эксперты могут даже приходить к несовпадающим заключениям. Попытка одновременно закодировать многочисленные методы решения задачи в одной базе знаний может привести к появлению внутренних конфликтов и несовместимостей.
5.Может ли эксперт дать пояснения к формулируемым им знаниям таким образом, чтобы это было понятно для инженера по знаниям? Даже если эксперт готов сотрудничать, могут возникнуть трудности при попытке выразить знания в явных терминах. В качестве простого примера возникающих при этом сложностей предлагаем читателю объяснить словами, как происходит движение пальцем. Безусловно, можно сказать, что движение осуществляется путем сокращения мускулов пальца. В таком случае возникает вопрос о том, как происходит сокращение мускулов пальца, и т.д. Еще одна сложность, возникающая в процессе общения эксперта и инженера по знаниям, заключается в том, что инженер по знаниям может не владеть всей технической терминологией, которой пользуется эксперт. Эта проблема становится особенно острой, когда речь идет о медицинской терминологии. Можно потратить целый год или даже больше на то, чтобы инженер по знаниям просто научился понимать, о чем вообще говорит эксперт, не считая того, чтобы преобразовать знания эксперта в явно заданный компьютерный код.
Лекция 4.1. Представление знаний в интеллектуальных системах.
1.Марковские алгоритмы
2. Семантические сети
1.Марковские алгоритмы
Любая система математики или логики может быть оформлена в виде системы продукционных правил определенного типа.
Марковский алгоритм — это упорядоченная группа продукций, которые применяются в порядке приоритета к входной строке. Если правило с наивысшим приоритетом является неприменимым, то используется следующее правило в порядке приоритета, и т.д. Марковский алгоритм завершает свою работу после обнаружения одного из следующих условий: во-первых, последняя продукция не применима к строке или, во-вторых, применена продукция, которая заканчивается точкой.
Марковские алгоритмы могут также применяться к подстрокам строк, начиная слева. Например, есть правило:
АВ→HIJ
после ее применения к входной строке GABKAB вырабатывает новую строку GHIJKAB. Поскольку теперь продукция применяется к новой строке, окончательным результатом становится строка GHIJKHIJ.
Специальный символ ˄ обозначает пустую строку, не содержащую символов. Например, следующая продукция удаляет все вхождения символа А в строке:
А→˄
Другие специальные символы могут представлять любой отдельный символ и обозначаются строчными буквами а, b, с, ..., х, у, z. Эти символы представляют собой односимвольные переменные и являются важной частью современных языков экспертных систем. Например, следующее правило меняет местами символы А и В в строке, где х — любой единственный символ:
АхВ→ВхА
Греческие буквы α, β и т.д. используются в строках в качестве специальных знаков пунктуации. Греческие буквы применяются потому, что их можно легко отличить от обычных букв алфавита.
Ниже приведен пример марковского алгоритма, который переводит первую букву входной строки в конец выходной строки. Правила упорядочены с учетом того, что правило (1) имеет высший приоритет, правило (2) — приоритет, который
следует за высшим приоритетом, и т.д. Приоритет правил задан в соответствии с порядком ввода правил, как показано ниже.
αху → уαх
α →˄
˄→ α
В табл. 1.11 показана трассировка выполнения алгоритма применительно к входной строке ABC.
Трассировка выполнения марковского алгоритма
Правило Успех (S) или
неудача (F) Строка
1 F ABC
2 F ABC
3 S α АВС
1 S В α АС
1 S ВС α А
1 S ВСА α
2 S ВСА
Обратите внимание на то, что символ α действует аналогично временной переменной в обычном языке программирования. Но символ α не хранит значение, а используется как метка-заполнитель для обозначения места внесения изменений во входной строке. После выполнения задачи символ α удаляется с помощью правила 2.
2. Семантические сети
Семантические сети, или просто сети, — это классический способ представления пропозициональной информации, используемый в искусственным интеллекте, поэтому семантические сети иногда называют пропозициональными сетями.
Пропозициональным утверждением (или высказыванием) называется предложение, которое может быть либо истинным, либо ложным, такое как "все собаки — млекопитающие" и "треугольник имеет три стороны".
Высказывания имеют форму декларативных знаний, поскольку в них утверждаются факты. С точки зрения математики семантическая сеть представляет собой помеченный ориентированный граф. Высказывание всегда является либо истинным, либо ложным и называется атомарным, так как его истинностное значение не подлежит дальнейшей декомпозиции (т.е. нельзя исследовать внутреннюю структуру)
Семантические сети впервые были разработаны для исследований в области искусственного интеллекта как способ описания человеческой памяти и языка Квиллианом (Quillian) в 1968 году. Квиллиан использовал семантические сети для анализа смысла слов в предложениях, которое не сводится синтаксическому анализу и разбиению предложения на лексемы и лексические структуры.
Структура семантической сети отображается графически с помощью узлов и соединяющих их дуг. Узлы иногда именуются объектами а дуги — связями, или ребрами.
Связи в семантической сети применяются для представления отношений, а узлы, как правило, служат для представления физических объектов, концепций или ситуаций. На представленном ниже рис., а показана обычная сеть (фактически ориентированный граф), в которой связи обозначают авиационные маршруты, проложенные между городами. Узлы обозначены кружками, а связи — линиями, соединяющими узлы. Стрелки показывают направление, или ориентацию, самолетов, совершающих полеты (именно поэтому граф, на котором указаны направления, называется ориентированным).
На представленном ниже рис., б связи показывают отношения между членами некоторой семьи. Отношения имеют для семантических сетей исключительно важное значение, поскольку предоставляют базовую структуру для организации знаний. Знания, заданные без учета отношений, превращаются просто в коллекцию несвязанных фактов. А если заданы отношения, то знания приобретают связную структуру, исследование которой позволяет выводить логическим путем другие знания. Например, на основании представленном ниже рис., б можно сделать вывод, что Анна и Билл — бабушка и дедушка Джона, даже несмотря на то, что на этом рисунке нет явно заданной связи, обозначенной как "grandfather-of".

Семантические сети иногда называют ассоциативными сетями, поскольку одни узлы в таких сетях ассоциированы, или связаны, с другими. В действительности в оригинальной работе Квиллиана человеческая память моделировалась как ассоциативная сеть, в которой понятия были представлены в виде узлов, а связи показывали, как соединены эти понятия друг с другом. Согласно указанной модели, если происходит стимуляция одного узла в результате чтения слов в предложении, то происходит активизация связей этого узла с другими узлами, и такая активность распространяется по сети. Если же достаточную активизацию получает другой узел, то в обладающем сознанием разуме всплывает концепция, представленная этим узлом.
Как оказалось, во многих разных способах представления знаний особенно полезными являются отношения определенных типов. Поэтому при изучении различных задач принято использовать именно эти типы, а не определять каждый раз новые отношения. К тому же применение общепринятых типов позволяет другим людям проще понять, что описано в незнакомой для них сети.
К двум таким связям широко используемых типов относятся связи IS-А и A-KIND-OF (связь последнего типа иногда записывается как АКО). На представленном ниже рис. показана семантическая сеть, в которой используются такие связи. На данном рисунке связь IS-A означает "является экземпляром" данного класса и указывает на конкретный экземпляр некоторого класса. Класс это группы объектов. Дирижабль это вид воздушного шара, воздушный шар это вид воздушного судна.

Рис. Семантическая сеть со связями.
Все объекты класса должны иметь один или несколько общих атрибутов.
Каждый атрибут имеет значение. Комбинация атрибута и значения называется свойством. Например, дирижабль имеет такие атрибуты, как размеры, вес, форма и цвет. Значением атрибута формы является эллипсоид. Иными словами, дирижабль имеет такое свойство, как эллипсоидальная форма. В семантических сетях можно также найти связи других типов. Связь IS-A определяет значение.
Связь CAUSE выражает причинные знания. Например, горячий воздух CAUSE (становится причиной) того, что воздушный шар поднимается.
Рекламный дирижабль компании Goodyear является дирижаблем, а дирижабли имеют эллипсоидальную форму; из этого следует, что дирижабль Goodyear является эллипсоидальным. Повторение характеристик узла в его потомках называется наследованием. Если нет более определенною свидетельства, позволяющего утверждать обратное, то предполагается, что все элементы некоторого класса наследуют все свойства суперклассов этого класса. Например, воздушные шары имеют круглую форму. Но класс дирижаблей имеет связь, указывающую на узел, обозначающий эллипсоидальную форму, поэтому явно заданная связь рассматривается как имеющая более высокий приоритет. Наследование представляет собой полезное средство в представлении знаний, поскольку позволяет избавиться от необходимости повторно указывать общие характеристики. Связи и наследование являются основой эффективных способов представления знаний, поскольку дают возможность показывать многие сложные отношения с помощью нескольких узлов и связей.
Лекция 4.2. Представление знаний в интеллектуальных системах.
Схемы. Концептуальные схемы.
Фреймы.
Трудности, связанные с использованием фреймов.
Проблема классификации и категоризации.
1.Схемы. Концептуальные схемы.
Структура семантической сети слишком проста, поэтому с ее помощью невозможно представить знания многих типов, применяемые в реальном мире. Для лучшего представления сложных структур знаний требуются более сложные структуры представления. В искусственном интеллекте для описания более сложных структур знаний, чем семантические сети, используется термин схема (schema). Термин схема заимствован из психологии, где он обозначает непрерывную организацию знаний или реакций живого существа, вырабатываемых в ответ на стимулы. Это означает, что живые существа, изучая причинные отношения между стимулом и результатом, стремятся повторно испытать приятные стимулы и избежать неприятных.
Важным типом схем являются концептуальные схемы, с помощью которых в мозгу человека складываются концепции. Например, допустим, что человек овладел концептуальным представлением о том, что такое животное. Но большинство людей, которых просят объяснить, что представляет собой животное, скорее всего, будут описывать его в таких терминах, что животное — существо с четырьмя ногами, заросшее мехом. К тому же, безусловно, сложившаяся у человека концепция животного будет зависеть от того, вырос ли он в сельской местности, в городе или на берегу реки. Тем не менее все люди имеют в своем сознании, складывающемся из концепций, определенные стереотипы. Безусловно, в обыденной речи термин стереотип может иметь отрицательную окраску, но в искусственном интеллекте он обозначает типичный пример. Поэтому для большинства людей стереотипом животного может быть собака.
Концептуальная схема — это абстракция, в которой конкретные объекты классифицируются по их общим свойствам. Например, если вы увидите рисунок с надписью "Искусственный фрукт", на котором изображен небольшой круглый объект красного цвета с зеленым черенком, то, по-видимому, распознаете его как искусственное яблоко. Этот объект обладает свойствами принадлежности к яблокам, которые могут быть поставлены в соответствие с концептуальной схемой яблока.
Концептуальная схема настоящего яблока может охватывать такие общие свойства яблок, как размеры, цвет, вкус, назначение и т.д. Эта схема не будет включать подробных сведений о том, где именно было сорвано яблоко, на каком грузовике оно доставлено в супермаркет и как зовут человека, положившего его на полку. Эти подробности не имеют значения при анализе тех свойств, из которых складывается абстрактная концепция яблока. Кроме того, следует учитывать, что, например, слепой человек может иметь совсем другую концептуальную схему яблока, в которой наибольшую важность имеет текстура поверхности и запах.
Сосредоточение на общих свойствах объекта позволяет упростить проведение рассуждений об этих свойствах, поскольку при этом не приходится отвлекаться на незначащие подробности. Как правило, схемы имеют структуру, внутреннюю по отношению к применяемым в них узлам, а семантические сети не имеют такой структуры. Все знания о некотором узле, применяемом в семантической сети, заключены в надписи на этом узле
2.Фреймы
Одним из типов схем, который используется во многих приложениях искусственного интеллекта, является фрейм. Еще один тип схемы представляет собой сценарий, который по существу является упорядоченной во времени последовательностью фреймов. Фреймы предложены для использования в качестве метода понимания особенностей зрения, естественных языков и других областей и предоставляют удобную структуру для описания объектов, типичных для какой-то конкретной ситуации, в частности, стереотипов объектов.
Фреймы являются особенно полезным средством моделирования знаний, основанных на здравом смысле, а эта область знаний с большим трудом поддается освоению с помощью компьютеров. Безусловно, семантические сети по существу можно рассматривать как двумерное представление знаний, а фреймы добавляют третье измерение, поскольку позволяют использовать узлы, имеющие внутреннюю структуру. В качестве таких структур могут применяться простые значения или другие фреймы.
Основная характерная особенность фрейма состоит в том, что он представляет взаимосвязанные знания по узкой теме, значительная часть которых — это знания, заданные по умолчанию. Система фреймов может оказаться весьма подходящей для описания механического устройства, например автомобиля. Такие компоненты автомобиля, как двигатель, корпус, тормозная система и т.д., должны рассматриваться в сочетании, чтобы можно было получить общее представление о связях между этими компонентами. Дополнительные сведения о компонентах могут быть получены с помощью изучения структуры фреймов. Безусловно, автомобили разных моделей отличаются друг от друга, но большинство автомобилей, как правило, имеют такие аналогичные компоненты, как колеса, двигатель, корпус и передаточный механизм. В этом состоит отличие фрейма от семантической сети, поскольку сеть, как правило, используется для общего представления знаний. Тем не менее, как и в случае семантических сетей, стандарты определения систем на основе фреймов отсутствуют. Для работы с фреймами создан целый ряд языков специального назначения, таких как FRL, SRL, KRL, KEE, HP-RL; кроме того, предусмотрены такие усовершенствованные средства работы с фреймами языка LISP, как LOOPS и FLAVORS.
Фрейм аналогичен структуре записи на языке высокого уровня. В свою очередь, полям и значениям записи соответствуют такие компоненты фрейма, как слоты и заполнители слотов. Фрейм по существу представляет собой группу слотов и заполнителей, которые определяют объект, рассматриваемый в качестве стереотипа.
Фреймы обнаруживают свою значимость в составе иерархических систем фреймов и в условиях применения наследования. Использование фреймов в виде заполнителей слотов и ввод в действие отношения наследования позволяет создавать очень мощные системы представления знаний. В частности, как оказалось, экспертные системы на основе фреймов являются очень полезным средством представления причинных знаний, поскольку хранимая в них информация организована с учетом причин и следствий. В отличие от этого, экспертные системы, основанные на правилах, обычно опираются на неорганизованные знания, которые не являются причинными.
В слотах можно хранить самые разнообразные элементы, в частности, правила, графику, комментарии, отладочную информацию, вопросы для пользователей, гипотезы, касающиеся той или иной ситуации, или другие фреймы.
6985399415На рис. показан универсальный фрейм, предназначенный для представления концепции собственности, которой может владеть человек. (конкретным фреймом будет описание экземпляра фрейма)
Заполнителями могут быть значения, такие как название собственности в слоте name, или ряд значений, например, как в слотах types (автомобмль, судно, дом) , status(потерян, плохой-бедный, хороший) или under_warranty= «под гарантией». Сами слоты могут также содержать процедуры, закрепленные за слотами и называемые процедурными вложениями. Сами процедуры, как правило, подразделяются на три типа. Процедура типа if-needed выполняется, если требуется значение заполнителя, но первоначально это значение не присутствует в слоте или является неприменимым значение default, предусмотренное по умолчанию. Применяемые по умолчанию значения соответствуют ожиданиям человека в отношении некоторой ситуации, которые складываются на основании опыта. А после того как обнаруживается новая ситуация, осуществляется модификация наиболее подходящего фрейма, что позволяет проще приспособиться к ситуации. Люди не начинают с пустого места, сталкиваясь с каждой новой ситуацией. Вместо этого они модифицируют в существующих фреймах заданные по умолчанию значения или другие заполнители. Заданные по умолчанию значения часто используются для представления знаний, основанных на здравом смысле. Знания, основанные на здравом смысле, могут рассматриваться как общеизвестные знания. Мы используем здравый смысл, если недоступны знания, более соответствующие конкретной ситуации.
Процедура типа if-added вызывается на выполнение, если в слот должно быть введено какое-либо дополнительное значение. Например, в слоте types процедура if-added вызывает на выполнение в случае необходимости процедуру ADD-PROPERTY для добавления собственности нового типа. Например, эта процедура может быть вызвана после приобретения телевизора, компьютера или собственности другого типа, поскольку указанные значения не содержатся в слоте types.
Процедура типа if-removal вызывается на выполнение каждый раз, когда возникает необходимость удалить из слота какое-либо значение. В частности, процедура такого типа выполняется, если данные, представленные каким-то значением, устаревают.
Объект, обладающий всеми типичными характеристиками, принято называть прототипом; этот термин буквально означает первичный тип.
Кроме того, классификация фреймов может проводиться на основании того, в какой области они применяются. Ситуативные фреймы содержат знания о том, чего можно ожидать в какой-то конкретной ситуации, например, на вечеринке по случаю дня рождения. С другой стороны, фреймы действия содержат слоты, которые определяют действия, подлежащие выполнению в какой-то конкретной ситуации. Это означает, что заполнителями слотов являются процедуры, предназначенные для выполнения определенных действий, таких как удаление дефектной детали с конвейера. Фрейм действия представляет процедурные знания.
А для описания причинно-следственных отношений могут применяться фреймы причинных знаний, представляющие собой сочетания ситуативных фреймов и фреймов действия.
3.Трудности, связанные с использованием фреймов
Первоначально фреймы предназначались для использования в качестве способа представления стереотипных знаний. Важной особенностью любого стереотипа является то, что он имеет вполне определенные характеристики, поэтому позволяет предоставить для многих своих слотов значения, заданные по умолчанию.
-29210269875Тем не менее при использовании систем фреймов обнаруживаются существенные недостатки, связанные с тем, что в этих системах допускается неограниченная модификация или уничтожение слотов. Классическим примером этой проблемы является фрейм elephant с описанием слонов. На первый взгляд создается впечатление, что фрейм elephant представляет собой приемлемое общее описание слонов. Однако предположим, что существует конкретный трехногий слон по кличке Клайд. Возможно, Клайд потерял ногу из- за несчастного случая на охоте. Но важно то, что во фрейме elephant содержится утверждение, будто любой слон имеет четыре ноги, а не три. Поэтому мы не можем рассматривать фрейм elephant как действительное определение любого слона.
Безусловно, этот фрейм можно модифицировать таким образом, чтобы он допускал в качестве исключения наличие трехногих, двуногих, одноногих или даже безногих слонов. Но в результате этого определение становится не очень качественным. Дополнительные проблемы могут возникать и при использовании других слотов. Предположим, что Клайд переболел желтухой в тяжелой форме и его кожа стала желтой. Но разве из-за этого он перестал быть слоном?
В большинстве систем фреймов не предусмотрены способы определения неизменных слотов. А поскольку в связи с этим может подвергнуться изменениям любой слот, то свойства, наследуемые одним фреймом от другого, могут быть изменены или исключены на любом уровне иерархии. Это означает, что любой фрейм по существу является примитивным, исходным фреймом, так как нет никаких гарантий того, что заданные в нем свойства будут общими. Каждый фрейм складывается из собственных правил и поэтому каждый фрейм является изначальным.
4. Классификация и кластеризация.
Задача классификации
Классификация является наиболее простой и одновременно наиболее часто решаемой задачей Data Mining. Ввиду распространенности задач классификации необходимо четкое понимания сути этого понятия.
Приведем несколько определений.
Классификация - системное распределение изучаемых предметов, явлений, процессов по родам, видам, типам, по каким-либо существенным признакам для удобства их исследования; группировка исходных понятий и расположение их в определенном порядке, отражающем степень этого сходства.
Классификация - упорядоченное по некоторому принципу множество объектов, которые имеют сходные классификационные признаки (одно или несколько свойств), выбранных для определения сходства или различия между этими объектами.
Классификация требует соблюдения следующих правил:
в каждом акте деления необходимо применять только одно основание;
деление должно быть соразмерным, т.е. общий объем видовых понятий должен равняться объему делимого родового понятия;
члены деления должны взаимно исключать друг друга, их объемы не должны перекрещиваться;
деление должно быть последовательным.
Различают:
вспомогательную (искусственную) классификацию, которая производится по внешнему признаку и служит для придания множеству предметов (процессов, явлений) нужного порядка;
естественную классификацию, которая производится по существенным признакам, характеризующим внутреннюю общность предметов и явлений. Она является результатом и важным средством научного исследования, т.к. предполагает и закрепляет результаты изучения закономерностей классифицируемых объектов.
В зависимости от выбранных признаков, их сочетания и процедуры деления понятий классификация может быть:
простой - деление родового понятия только по признаку и только один раз до раскрытия всех видов. Примером такой классификации является дихотомия, при которой членами деления бывают только два понятия, каждое из которых является противоречащим другому (т.е. соблюдается принцип: "А и не А");
сложной - применяется для деления одного понятия по разным основаниям и синтеза таких простых делений в единое целое. Примером такой классификации является периодическая система химических элементов.
Под классификацией будем понимать отнесение объектов (наблюдений, событий) к одному из заранее известных классов.
Классификация - это закономерность, позволяющая делать вывод относительно определения характеристик конкретной группы. Таким образом, для проведения классификации должны присутствовать признаки, характеризующие группу, к которой принадлежит то или иное событие или объект (обычно при этом на основании анализа уже классифицированных событий формулируются некие правила).
Классификация относится к стратегии обучения с учителем (supervised learning), которое также именуют контролируемым или управляемым обучением.
Задачей классификации часто называют предсказание категориальной зависимой переменной (т.е. зависимой переменной, являющейся категорией) на основе выборки непрерывных и/или категориальных переменных.
Например, можно предсказать, кто из клиентов фирмы является потенциальным покупателем определенного товара, а кто - нет, кто воспользуется услугой фирмы, а кто - нет, и т.д. Этот тип задач относится к задачам бинарной классификации, в них зависимая переменная может принимать только два значения (например, да или нет, 0 или 1).
Другой вариант классификации возникает, если зависимая переменная может принимать значения из некоторого множества предопределенных классов. Например, когда необходимо предсказать, какую марку автомобиля захочет купить клиент. В этих случаях рассматривается множество классов для зависимой переменной.
Классификация может быть одномерной (по одному признаку) и многомерной (по двум и более признакам).
Многомерная классификация была разработана биологами при решении проблем дискриминации для классифицирования организмов. Одной из первых работ, посвященных этому направлению, считают работу Р. Фишера (1930 г.), в которой организмы разделялись на подвиды в зависимости от результатов измерений их физических параметров. Биология была и остается наиболее востребованной и удобной средой для разработки многомерных методов классификации.
Процесс классификации
Цель процесса классификации состоит в том, чтобы построить модель, которая использует прогнозирующие атрибуты в качестве входных параметров и получает значение зависимого атрибута. Процесс классификации заключается в разбиении множества объектов на классы по определенному критерию.
Классификатором называется некая сущность, определяющая, какому из предопределенных классов принадлежит объект по вектору признаков.
Для проведения классификации с помощью математических методов необходимо иметь формальное описание объекта, которым можно оперировать, используя математический аппарат классификации. Таким описанием в нашем случае выступает база данных. Каждый объект (запись базы данных) несет информацию о некотором свойстве объекта.
Набор исходных данных (или выборку данных) разбивают на два множества: обучающее и тестовое.
Обучающее множество (training set) - множество, которое включает данные, использующиеся для обучения (конструирования) модели.
Такое множество содержит входные и выходные (целевые) значения примеров. Выходные значения предназначены для обучения модели.
Тестовое (test set) множество также содержит входные и выходные значения примеров. Здесь выходные значения используются для проверки работоспособности модели.
Процесс классификации состоит из двух этапов: конструирования модели и ее использования.
1. Конструирование модели: описание множества предопределенных классов.
Каждый пример набора данных относится к одному предопределенному классу.
На этом этапе используется обучающее множество, на нем происходит конструирование модели.
Полученная модель представлена классификационными правилами, деревом решений или математической формулой.
2. Использование модели: классификация новых или неизвестных значений.
Оценка правильности (точности) модели.
Известные значения из тестового примера сравниваются с результатами использования полученной модели.
Уровень точности - процент правильно классифицированных примеров в тестовом множестве.
Тестовое множество, т.е. множество, на котором тестируется построенная модель, не должно зависеть от обучающего множества.
Если точность модели допустима, возможно использование модели для классификации новых примеров, класс которых неизвестен.
Методы, применяемые для решения задач классификации
Для классификации используются различные методы. Основные из них:
классификация с помощью деревьев решений;
байесовская (наивная) классификация;
классификация при помощи искусственных нейронных сетей;
классификация методом опорных векторов;
статистические методы, в частности, линейная регрессия;
классификация при помощи метода ближайшего соседа;
классификация CBR(Case Based Reasoning)-методом;
классификация при помощи генетических алгоритмов.
Точность классификации: оценка уровня ошибок
Оценка точности классификации может проводиться при помощи кросс-проверки. Кросс-проверка (Cross-validation) - это процедура оценки точности классификации на данных из тестового множества, которое также называют кросс-проверочным множеством. Точность классификации тестового множества сравнивается с точностью классификации обучающего множества. Если классификация тестового множества дает приблизительно такие же результаты по точности, как и классификация обучающего множества, считается, что данная модель прошла кросс-проверку.
Разделение на обучающее и тестовое множества осуществляется путем деления выборки в определенной пропорции, например обучающее множество - две трети данных и тестовое - одна треть данных. Этот способ следует использовать для выборок с большим количеством примеров. Если же выборка имеет малые объемы, рекомендуется применять специальные методы, при использовании которых обучающая и тестовая выборки могут частично пересекаться.
Оценивание классификационных методов
Оценивание методов следует проводить, исходя из следующих характеристик: скорость, робастность, интерпретируемость, надежность.
Скорость характеризует время, которое требуется на создание модели и ее использование.
Робастность, т.е. устойчивость к каким-либо нарушениям исходных предпосылок, означает возможность работы с зашумленными данными и пропущенными значениями в данных.
Интерпретируемость обеспечивает возможность понимания модели аналитиком.
Свойства классификационных правил:
размер дерева решений;
компактность классификационных правил.
Надежность методов классификации предусматривает возможность работы этих методов при наличии в наборе данных шумов и выбросов.
Интересной задачей из геологической области была задача таксономии территорий северо-востока Чукотки. Изучаемая местность была разделена геологами на 1992 ячейки в виде квадратов 10 х 10 км. Каждый квадрат был описан 45 двоичными признаками, отражающими наличие или отсутствие различных геологических свойств: шлиховые ореолы ртути, глубина залегания мезозоид 3-4 км, геосинклинальные прогибы и пр.
Таксономия этих участков делалась разновидностью алгоритма FOREL (FOREL-5), предназначенной для таксономии двоичных данных. Из разных вариантов таксономии заказчики выбрали вариант, содержавший 318 таксонов. Этот вариант привлек их внимание тем, что 46 из 318 таксонов включали в свой состав участки, которые были раньше хорошо изучены и на которых имелись золотоносные месторождения. И если планировать экспедиционные работы по поиску золота, то в первую очередь целесообразно обратить внимание на те неизученные участки, которые также оказались в составе этих «золотых» таксонов. Результаты экспедиций подтвердили высокую эффективность такого способа планирования геологоразведки. Таким же образом были разработаны рекомендации по поиску месторождений и ряда других минералов.[Загоруйко]
Задача кластеризации
Только что мы изучили задачу классификации, относящуюся к стратегии "обучение с учителем".
В этой части лекции мы введем понятия кластеризации, кластера, кратко рассмотрим классы методов, с помощью которых решается задача кластеризации, некоторые моменты процесса кластеризации, а также разберем примеры применения кластерного анализа.
Задача кластеризации сходна с задачей классификации, является ее логическим продолжением, но ее отличие в том, что классы изучаемого набора данных заранее не предопределены.
Синонимами термина "кластеризация" являются "автоматическая классификация", "обучение без учителя" и "таксономия" (Таксоно́мия(от греч. taxis — расположение, строй и nomos — закон) — учение о принципах и практике классификации и систематизации).
Кластеризация предназначена для разбиения совокупности объектов на однородные группы (кластеры или классы). Если данные выборки представить как точки в признаковом пространстве, то задача кластеризации сводится к определению "сгущений точек".
Цель кластеризации - поиск существующих структур.
Кластеризация является описательной процедурой, она не делает никаких статистических выводов, но дает возможность провести разведочный анализ и изучить "структуру данных".
Само понятие "кластер" определено неоднозначно: в каждом исследовании свои "кластеры". Переводится понятие кластер (cluster) как "скопление", "гроздь".
Кластер можно охарактеризовать как группу объектов, имеющих общие свойства.
Характеристиками кластера можно назвать два признака:
внутренняя однородность;
внешняя изолированность.
Вопрос, задаваемый аналитиками при решении многих задач, состоит в том, как организовать данные в наглядные структуры, т.е. развернуть таксономии.
Наибольшее применение кластеризация первоначально получила в таких науках как биология, антропология, психология. Для решения экономических задач кластеризация длительное время мало использовалась из-за специфики экономических данных и явлений.
Кластеры могут быть непересекающимися, или эксклюзивными (non-overlapping, exclusive), и пересекающимися (overlapping) [22]. Схематическое изображение непересекающихся и пересекающихся кластеров дано на рис. ниже.

Рис. Непересекающиеся и пересекающиеся кластеры
Следует отметить, что в результате применения различных методов кластерного анализа могут быть получены кластеры различной формы. Например, возможны кластеры "цепочного" типа, когда кластеры представлены длинными "цепочками", кластеры удлиненной формы и т.д., а некоторые методы могут создавать кластеры произвольной формы.
Различные методы могут стремиться создавать кластеры определенных размеров (например, малых или крупных) либо предполагать в наборе данных наличие кластеров различного размера.
Некоторые методы кластерного анализа особенно чувствительны к шумам или выбросам, другие - менее.
В результате применения различных методов кластеризации могут быть получены неодинаковые результаты, это нормально и является особенностью работы того или иного алгоритма.
Данные особенности следует учитывать при выборе метода кластеризации.
Подробнее обо всех свойствах кластерного анализа будет рассказано в лекции, посвященной его методам.
На сегодняшний день разработано более сотни различных алгоритмов кластеризации. Некоторые, наиболее часто используемые, будут подробно описаны во втором разделе курса лекций.
Приведем краткую характеристику подходов к кластеризации [21].
Алгоритмы, основанные на разделении данных (Partitioning algorithms), в т.ч. итеративные:
разделение объектов на k кластеров;
итеративное перераспределение объектов для улучшения кластеризации.
Иерархические алгоритмы (Hierarchy algorithms):
агломерация: каждый объект первоначально является кластером, кластеры, соединяясь друг с другом, формируют больший кластер и т.д.
Методы, основанные на концентрации объектов (Density-based methods):
основаны на возможности соединения объектов;
игнорируют шумы, нахождение кластеров произвольной формы.
Грид-методы (Grid-based methods):
квантование объектов в грид-структуры.
Модельные методы (Model-based):
использование модели для нахождения кластеров, наиболее соответствующих данным.
Оценка качества кластеризации
Оценка качества кластеризации может быть проведена на основе следующих процедур:
ручная проверка;
установление контрольных точек и проверка на полученных кластерах;
определение стабильности кластеризации путем добавления в модель новых переменных;
создание и сравнение кластеров с использованием различных методов. Разные методы кластеризации могут создавать разные кластеры, и это является нормальным явлением. Однако создание схожих кластеров различными методами указывает на правильность кластеризации.
Процесс кластеризации
Процесс кластеризации зависит от выбранного метода и почти всегда является итеративным. Он может стать увлекательным процессом и включать множество экспериментов по выбору разнообразных параметров, например, меры расстояния, типа стандартизации переменных, количества кластеров и т.д. Однако эксперименты не должны быть самоцелью - ведь конечной целью кластеризации является получение содержательных сведений о структуре исследуемых данных. Полученные результаты требуют дальнейшей интерпретации, исследования и изучения свойств и характеристик объектов для возможности точного описания сформированных кластеров.
Применение кластерного анализа
Кластерный анализ применяется в различных областях. Он полезен, когда нужно классифицировать большое количество информации. Обзор многих опубликованных исследований, проводимых с помощью кластерного анализа, дал Хартиган (Hartigan, 1975).
Так, в медицине используется кластеризация заболеваний, лечения заболеваний или их симптомов, а также таксономия пациентов, препаратов и т.д. В археологии устанавливаются таксономии каменных сооружений и древних объектов и т.д. В маркетинге это может быть задача сегментации конкурентов и потребителей. В менеджменте примером задачи кластеризации будет разбиение персонала на различные группы, классификация потребителей и поставщиков, выявление схожих производственных ситуаций, при которых возникает брак. В медицине - классификация симптомов. В социологии задача кластеризации - разбиение респондентов на однородные группы.
Кластерный анализ в маркетинговых исследованиях
В маркетинговых исследованиях кластерный анализ применяется достаточно широко - как в теоретических исследованиях, так и практикующими маркетологами, решающими проблемы группировки различных объектов. При этом решаются вопросы о группах клиентов, продуктов и т.д.
Так, одной из наиболее важных задач при применении кластерного анализа в маркетинговых исследованиях является анализ поведения потребителя, а именно: группировка потребителей в однородные классы для получения максимально полного представления о поведении клиента из каждой группы и о факторах, влияющих на его поведение. Эта проблема подробно описана в работах Клакстона, Фрая и Портиса (1974), Киля и Лэйтона (1981).
Важной задачей, которую может решить кластерный анализ, является позиционирование, т.е. определение ниши, в которой следует позиционировать новый продукт, предлагаемый на рынке. В результате применения кластерного анализа строится карта, по которой можно определить уровень конкуренции в различных сегментах рынка и соответствующие характеристики товара для возможности попадания в этот сегмент. С помощью анализа такой карты возможно определение новых, незанятых ниш на рынке, в которых можно предлагать существующие товары или разрабатывать новые.
Кластерный анализ также может быть удобен, например, для анализа клиентов компании. Для этого все клиенты группируются в кластеры, и для каждого кластера вырабатывается индивидуальная политика. Такой подход позволяет существенно сократить объекты анализа, и, в то же время, индивидуально подойти к каждой группе клиентов.
Практика применения кластерного анализа в маркетинговых исследованиях
Приведем некоторые известные статьи, посвященные применению кластерного анализа для маркетинговых исследований.
В 1971 году была опубликована статья о сегментации клиентов по сфере интересов на основе данных, характеризующих предпочтения клиентов.
В 1974 году была опубликована статья Секстона (Sexton), целью которой была идентификация групп семей - потребителей продукта, в результате были разработаны стратегии позиционирования бренда. Основой для исследований были рейтинги, которые респонденты присваивали продуктам и брендам.
В 1981 году была опубликована статья, где проводился анализ поведения покупателей новых автомобилей на основе данных факторных нагрузок, полученных при анализе набора переменных.
Выводы
Hами были подробно рассмотрены задачи классификации и кластеризации. Несмотря на кажущуюся похожесть этих задач, решаются они разными способами и при помощи разных методов. Различие задач прежде всего в исходных данных.
Классификация, являясь наиболее простой задачей Data Mining, относится к стратегии "обучение с учителем", для ее решения обучающая выборка должна содержать значения как входных переменных, так и выходных (целевых) переменных. Кластеризация, напротив, является задачей Data Mining, относящейся к стратегии "обучение без учителя", т.е. не требует наличия значения целевых переменных в обучающей выборке.
Задача классификации решается при помощи различных методов, наиболее простой - линейная регрессия. Выбор метода должен базироваться на исследовании исходного набора данных. Наиболее распространенные методы решения задачи кластеризации: метод k-средних (работает только с числовыми атрибутами), иерархический кластерный анализ (работает также с символьными атрибутами), метод SOM. Сложностью кластеризации является необходимость ее оценки.
Лекция 5. Методы логического вывода. Дедуктивная логика
Деревья решетки и графы
Пространства состояний и пространства задач
Дедуктивная логика и силлогизмы
Деревья решетки и графы
Деревья и решетки имеют иерархическую структуру, поэтому являются удобным средством классификации объектов. Но еще одной областью применения деревьев и решеток является принятие решений; используемые при этом структуры называются деревьями решений, или решетками решений, и очень широко применяются для формирования простых рассуждений.
Дерево — это иерархическая структура данных, состоящая из узлов, хранящих информацию (или знания), и ребер, соединяющих узлы. Ребра иногда называют связями, или дугами, а узлы — вершинами. На рис. показано бинарное дерево общего вида, в котором имеются нуль, одно или два ребра в расчете на каждый узел. В ориентированном дереве на самом верхнем уровне иерархии находится корневой узел, а на самых нижних уровнях — листовые узлы.
Бинарное дерево обычного типа может содержать не больше двух дочерних узлов в расчете на каждый узел. Если узел имеет больше одного родительского узла, то он находится не в дереве, а в сети.
Дерево — это частный случай общей математической структуры, называемой графом. В графе допускается наличие от нуля и больше связей между узлами, а родительские и дочерние узлы не различаются. Простым примером графа является карта автомобильных дорог, на которой города представляют собой узлы, а дороги — связи. Со связями могут быть ассоциированы направления, обозначенные стрелками, и весовые коэффициенты, характеризующие некоторые аспекты анализа связей.
Контуром, или циклом, называется путь через граф, который начинается и оканчивается в одном и том же узле; в качестве примера можно указать путь АВСА. Ациклическим графом называется граф, не имеющий циклов. Связный граф — это граф, в котором имеются связи, протянувшиеся ко всем узлам. Граф с ориентированными связями, называется ориентированным графом, в котором имеется также петля. Ориентированный ациклический граф называется решеткой. Дерево с единственным путем от корня к его единственному листовому узлу называется вырожденным деревом. Как правило, в дереве стрелки явно не показаны, поскольку подразумевается, что стрелки всегда направлены вниз.

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

Как видно это удобный способ организации процесса принятия решений с точки зрения затрат времени и усилий для проведения все более детальных наблюдений.
Один вопрос позволяет принять решение о выборе одного из двух возможных ответов, с помощью двух вопросов вырабатывается решение о выборе одного из четырех возможных ответов, три вопроса позволяют выбрать один из восьми возможных ответов и т.д. Если бинарное дерево сконструировано таким образом, что во всех листовых узлах представлены ответы, а на всех ребрах, ведущих вниз, заданы вопросы, то дерево решений позволяет представить с помощью N вопросов, равное 2N ответов. Например, десять вопросов позволяют классифицировать одно из 1024 животных, а двадцать — находить один из 1 048 576 возможных ответов.
Пространства состояний и пространства задач
Для решения многих практических задач могут применяться графы. Один из удобных методов описания поведения некоторого объекта состоит в определении графа, называемого пространством состояний. Состояние — это коллекция характеристик, которые могут использоваться для определения состояния, или статуса, объекта. Пространство состояний — это множество состояний, с помощью которого представляются переходы между состояниями, которым подвергается объект. В результате перехода объект попадает из одного состояния в другое.
Пример пространств состояний. В качестве простого примера использования пространства состояний рассмотрим покупку кофе в автомате. По мере того как в автомат вкладывают монеты, происходит переход из одного состояния в другое. Рассмотрим диаграмму пространства состояний, подготовленная на основе того предположения, что в распоряжении покупателя имеются только 25-центовые монеты (Q) и 5-центовые монеты (N), а для приобретения напитка необходимо опустить 55 центов.

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

Дедуктивная логика и силлогизмы
Дедукция - выведение следствий из посылок в соответствии с законами логики.
Индукция – это вид обобщения, в к-ром осуществляется переход от частного знания к более общему.
Силлогизм – это высказывание содержащие две посылки и одно заключение.
Посылка. Все люди смертны
Посылка. Сократ человек
Заключение. Сократ смертен
Посылки – антецеденты, заключения – консеквент. Для большей компактности подобное высказывание принято записывать следующим образом:
Все люди смертны
Сократ человек
∴ Сократ смертен
где троеточие ∴ обозначает «следовательно»
Силлогизмом считается любое действительное дедуктивное доказательство, имеющее две посылки и одно заключение. Классически считается силлогизм специального типа, называемый категорическим силлогизмом. В таком силлогизме посылки и заключения определяются как категорические утверждения, имеющие одну из четырех форм
Категорические утверждения
Форма Схема Значение
А Все S есть Р общее утвердительное
Е Никакие S не есть Р общее отрицательное
I Некоторые S есть Р частное утвердительное
О Некоторые S не есть Р частное отрицательное
Все М есть Р
Все S есть М
∴ Все S есть Р
Субъект этого заключения, S, называется младшим членом, а предикат заключения, Р, — старшим членом. Посылка, содержащая старший член, называется большей посылкой, а посылка, содержащая младший член, — меньшей посылкой. Если в силлогизме, например, как показано ниже, выделены большая и меньшая посылки, то силлогизм рассматривается как представленный в стандартной форме.
Большая посылка. Все М есть Р
Меньшая посылка. Все S есть М
Заключение. Все S есть Р
Третий член силлогизма, М, называется средним членом и становится общим для обеих посылок. Средний член очень важен, поскольку силлогизм определен таким образом, что заключение нельзя вывести из любой отдельно взятой посылки. Поэтому следующее доказательство не представляет собой действительный силлогизм, поскольку следует только из первой посылки:
Все А есть В
Все В есть С
∴ Все А есть В
Субъект представляет собой то, о чем говорится в силлогизме, а предикат служит для описания некоторого свойства субъекта. Например, в следующем высказывании субъект обозначается словом "микрокомпьютеры", а предикатом является слово "компьютеры":
«Все микрокомпьютеры являются компьютерами»
Предика́т - это то, что утверждается о субъекте.
Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z ) для отношения «x проживает в городе y на улице z»
Формы категорических утверждений обозначаются буквами А, Е, I и О. Буквами А и I обозначаются утвердительные высказывания; принято считать, что эти буквы происходят от первых двух гласных латинского слова affirmo (утверждаю); с другой стороны, буквы Е и О взяты из слова nego (отрицаю).
Формы А и I называются утвердительными по качеству, поскольку в них утверждается, что субъекты включены в класс, описываемый предикатом.
Формы Е и О являются отрицательными по качеству, поскольку указывают, что субъекты исключены из класса предиката.
Обратимся еще раз к категориям утверждений, и внимательнее рассмотрим схему утверждений. В схеме присутствует количественны указатель или квантор, который указывает, какая часть класса рассматривается в посылке. Кванторы "все" и "ни один" являются общими, поскольку распространяются на целые классы. А квантор "некоторые" называется частным, поскольку он распространяется только на часть класса.
Модус силлогизма определяется тремя буквами, которые указывают соответственно форму большей посылки, меньшей посылки и заключения. Например, следующий силлогизм имеет модус AAA:
Все М есть Р
Все S есть М
∴ Все S есть Р
Как показано в табл. 3.3, для размещения термов S, Р и М могут использоваться четыре возможных шаблона. Каждый шаблон называется фигурой, а номер фигуры определяет ее тип.
Шаблоны категорических утверждений

Итак, приведенный выше пример можно полностью описать как силлогизм типа ААА-1. Но лишь из того, что доказательство имеет силлогистическую форму, отнюдь не следует, что оно представляет собой действительный силлогизм. Рассмотрим следующий силлогизм, представленный в форме АЕЕ-1:
Все М есть Р
Ни один S не есть М
∴ Ни один S не есть Р
Как показывает следующий пример, этот силлогизм нельзя считать действительным:
Все микрокомпьютеры являются компьютерами
Ни один мэйнфрейм не является микрокомпьютером
∴ Ни один мэйнфрейм не является компьютером
Безусловно, для того чтобы проверить обоснованность силлогистических доказательств, можно попытаться воспользоваться примерами, но для этой цели проще применить процедуру принятия решений. Процедурой принятия решений называется метод доказательства обоснованности. В основе которого лежит некоторый общий механический метод или алгоритм, позволяющий автоматизировать процесс определения обоснованности.
Процедура принятия решений для высказываний состоит в построении истинностной таблицы и проверке ее на наличие тавтологии. А процедура принятия решений в отношении силлогизмов может быть осуществлена с использованием диаграмм Венна с тремя перекрывающимися кружками, представляющими члены S, Р и М.
Проверим обоснованность силлогистического доказательства с помощью диаграмм Венна.
Все М есть Р
Ни один S не есть М
∴ Ни один S не есть Р

Заштрихуем область, которая не имеет значений.
Из большей посылки следует, что не существуют элементы множества М за пределами множества Р
Из меньшей посылки следует, что не существуют элементы, принадлежащие одновременно множеству М и множеству S.
В заключении говорится, что отсутствует общие элементы у множеств P и S, что не соответствует истине.
Задача построения диаграмм Венна для силлогизмов, включающих кванторы "некоторые", становится немного более сложной. Ниже приведены общие правила построения диаграмм для категорических силлогизмов в соответствии с булевым представлением, согласно которому в множествах, соответствующих высказываниям А и Е, может не быть элементов.
1.Если класс пуст, соответствующий ему кружок заштриховывается.
2.Общие утверждения, А и Е, всегда представляются на диаграмме перед частными.
3.Если класс включает по меньшей мере один элемент, он обозначается звездочкой (*).
4.Если некоторое высказывание не позволяет определить, в каком из двух смежных классов существует объект, то символ * изображается на линии, разделяющей классы.
5.Если некоторая область заштрихована, то в нее нельзя помещать символ *.
81915315595В качестве примера рассмотрим следующий силлогизм в форме IAI-4 таким образом:
Некоторые Р есть М
Все М есть S
∴ Некоторые S есть Р
В соответствии с правилами 2 и 1 построения диаграмм Венна начнем с общего высказывания, относящегося к меньшей посылке, и заштрихуем соответствующий кружок, Затем применим правило 3 к частной большой посылке и поставим символ *. Заключение не содержит противоречий, значит, доказательство в форме IAI-4 представляет собой действительный силлогизм.
Лекция 6. Рассуждения в условиях неопределенности.
Формирование рассуждений в условиях неопределенности
Тема о методах формирования рассуждений в условиях неопределенности очень важна, поскольку одной из самых сильных сторон любой экспертной системы является ее способность справляться с неопределенностью так же успешно, как это делают настоящие эксперты. Дело в том, что если известен приемлемый алгоритм или дерево решений, то не требуется вся мощь экспертной системы. Способность справляться с неопределенностью представляет собой одно из основных преимуществ экспертной системы над простым деревом решений, в котором все факты должны быть известны заранее, чтобы можно было достичь результата.
Неопределенность может рассматриваться как нехватка адекватной информации для принятия решения. Неопределенность становится проблемой, поскольку может помешать выработке наилучшего решения и даже стать причиной того, что будет принято некачественное решение. В медицине из-за неопределенности может быть не обнаружен наиболее подходящий способ лечения пациента или выбраны не совсем подходящие терапевтические средства, а в бизнесе неопределенность может привести вместо прибыли к финансовым убыткам.
Разработан целый ряд теорий, позволяющих успешно действовать в условиях неопределенности. К ним относятся теории, основанные на классическом определении вероятностей и на байесовской вероятности; теория Хартли, основанная на классическом определении множеств; теория Шеннона, основанная на понятии вероятности; теория Демпстера-Шефера; марковские модели; а также теория нечетких множеств Заде. В частности, теория байесовских вероятностей и теория нечетких множеств оказались весьма широко применимыми во многих областях, таких как биология, психология, музыка и физика. Нечеткая логика применяется также во многих потребительских приборах, начиная со стиральных машин, способных стирать бельё, измеряя по ходу дела чистоту ткани, а не отсчитывая время по электрическому таймеру, изобретенному еще в XIX веке, и заканчивая фотокамерами, позволяющими автоматически получать великолепные изображения.
Все живые существа являются настоящими экспертами в области учета неопределенности, поскольку в противном случае они не смогли бы выжить в реальном мире. А людям приходится справляться с неопределенностью, касающейся дорожного трафика, погоды, работы, учебы и в целом своей жизни. После небольшого опыта мы становимся экспертами по вождению в различных условиях, начинаем понимать, как бороться с холодом, и выбираем самый легкий способ усвоения знаний. Некоторые люди умудряются даже стать экспертами по выбору самого легкого пути во всем. Для того чтобы уметь справляться с неопределенностью, человек должен научиться рассуждать в условиях неопределенности и иметь много здравого смысла. Единственным недостатком здравого смысла является то, что он не обязательно означает истинную прозорливость, а позволяет лишь определить, что следует делать в обычных ситуациях. Но иногда обычный способ — это не лучший способ, поэтому так важно уметь рассуждать в условиях неопределенности. Например, если вы до сих пор никогда не играли на игорном автомате и вдруг выиграли немного денег, а затем начали проигрывать, здравый смысл шепнет вам на ухо, что если вы будет играть достаточно долго, то в конечном итоге обязательно снова выиграете. К сожалению, здравый смысл ничего не говорит о том, что вы проиграете все наличные, исчерпаете все возможности своих кредитных карточек, продадите свой автомобиль и заложите обручальное кольцо своей супруги, прежде чем вам снова удастся выиграть.
Дедуктивный метод формирования рассуждений называется строгими рассуждениями, поскольку он распространяется на точные факты и точные заключения, которые следуют из этих фактов.
Безусловно, многие приложения экспертных систем могут быть основаны на использовании строгих рассуждений, но для значительного количества других приложений требуются нестрогие рассуждения, поскольку сами факты или знания точно не известны. В качестве одного из наиболее ярких примеров можно указать коммерческую медицину. Для оптимизации прибыли необходимо стремиться к такой цели — найти приемлемый способ лечения с помощью минимального количества анализов, поскольку анализы стоят денег. В экспертных системах могут применяться неопределенные факты, правила, или то и другое. Классическими примерами экспертных систем, успешно действующих в условиях неопределенности, являются система MYCIN, предназначенная для медицинской диагностики, и система PROSPECTOR, применяемая для разведки полезных ископаемых.
Основная причина, по которой эти системы так часто упоминаются в литературе, состоит в том, что они имели очень качественную документацию и предназначались для демонстрации применимости экспертных систем в качестве консультантов, эквивалентных или лучших по сравнению с экспертами-людьми, что и было достигнуто в обеих системах. Это было давно, а в наши дни вы не сможете получить доступ к точным правилам, по которым экспертные системы бюро кредитования определяют вашу оценку кредитоспособности, а также не узнаете, почему в обслуживании вашей кредитной карточки было отказано тем же банком, который недавно выдал вам разрешение на крупную ссуду. К тому же экспертные системы — это прежде всего программы, поэтому разве не может быть шансов, что в коде самих этих программ имеются ошибки? Тем не менее вам все равно не позволят ознакомиться с кодом, чтобы определить, не была ли причиной того, что вам отказали в кредите или ссуде, сама программа.
В системах MYCIN и PROSPECTOR предусмотрена возможность выработки заключений даже в тех случаях, если не известны все факты, необходимые для абсолютно надежного доказательства каждого заключения. Безусловно, если речь идет о медицине, то было бы возможно получить более надежное заключение, выполнив больший объем анализов, но при этом возникает проблема, связанная с увеличением затрат времени и денег на выполнение анализов. Ограничения, касающиеся времени и денег, особенно важны в случае медицинского обслуживания. Задержка в предоставлении лечения в целях проведения дополнительных анализов приводит к существенному увеличению затрат; между тем пациент, не дождавшись помощи, может умереть. А если речь идет о разведке полезных ископаемых, то стоимость дополнительных исследований также является существенным фактором. Может оказаться, что более экономически выгодное решение состоит в том, чтобы приступить к бурению скважины, если вы уверены в успехе на 95%, чем потратить еще сотни тысяч долларов, чтобы добиться 98%-ной уверенности
Классическая вероятность
Одним из самых старых и все еще очень важных инструментальных средств решения задач искусственного интеллекта является вероятность. Вероятность — это количественный способ учета неопределенности. Понятие вероятности зародилось в XVII веке, после того как некоторые азартные игроки во Франции обратились за помощью к ведущим математикам, таким как Паскаль, Ферма и др. В то время азартные игры нашли очень широкое распространение, а поскольку в ходе игры привлекались крупные суммы денег, игроки стремились овладеть методами, позволяющими вычислять шансы на выигрыш. В действительности классическая задача разорения игрока — это доказательство с помощью теории вероятностей эмпирического факта, замеченного игроками: игорный дом всегда выигрывает, если вы состязаетесь с ним достаточно долго.
Классическая вероятность рассматривалась в теории, которая была впервые предложена Паскалем и Ферма в 1654 году. С того времени была проведена большая работа в области изучения вероятностей и создано несколько новых научных направлений. Многочисленные приложения вероятностей обнаруживаются в науке, технике, бизнесе, экономике и практически во всех других областях.
События, не являющиеся взаимоисключающими, влияют друг на друга. Узнав о том, что произошло одно событие, мы можем оказаться вынужденными пересмотреть оценку вероятности возникновения другого события. Вероятность возникновения события А, определяемая с учетом того, что произошло событие В, называется условной вероятностью и обозначается Р(А | В)
Понятие нечетких множеств
Понятие нечетких множеств (англ.: fuzzy sets) как обобщение обычных (четких) множеств было введено Л. Заде в 1965 г. В качестве одной из предпосылок возникновения идеи нечеткого множества Заде выдвигает так называемый принцип несовместимости, который заключается в том, что с увеличением размеров и сложности системы существенно усложняется ее моделирование с помощью известных математических выражений. Другими словами, при использовании формул существенно возрастает число переменных и параметров, измерение отдельных переменных и определение параметров сильно затрудняется, и создание полностью адекватной модели становится практически невозможным. Вместо этого Заде предложил лингвистическую модель, которая использует не математические выражения, а слова, отражающие качество. Применение этих слов не обеспечивает такую же точность, какой обладают математические модели, но дает возможность создать хорошую, качественную модель системы. В числе основных промышленных применений теории можно назвать управление, диагностику неисправностей, распознавание образов, обработку изображений, анализ надежности, проектирование систем, компьютеры и т. д. Традиционный способ представления элемента множества А состоит в применении характеристической функции μА(х), которая равна 1, если этот элемент принадлежит к множеству А, или равна 0 в противном случае. В нечетких системах элемент может частично принадлежать к любому множеству. Степень принадлежности к множеству А, представляющая собой обобщение характеристической функции, называется функцией принадлежности μА(х), причем μА(х) [0, 1]. Значения функции принадлежности являются рациональными числами из интервала [0,1], где 0 означает отсутствие принадлежности к множеству, а 1 - полную принадлежность. Конкретное значение функции принадлежности называется степенью или коэффициентом принадлежности. Эта степень может быть определена явным образом в виде функциональной зависимости (например, ) μА(х) = ехр (— ((х-3)/0,2)2) либо дискретно - путем задания конечной последовательности значений х {xn} в виде

Например, для последовательности дискретных значений переменной х, равных x1 = 7, x2 = 8, х3 = 9, х4 = 10, х5 = 11, x6 = 12, x7 = 13, их коэффициент принадлежности к числам, близким 10, может быть определен в виде

Каждое нечеткое множество имеет определенный носитель (англ.: support). Носителем множества Supp(A) является подмножество тех элементов А, для которых коэффициент принадлежности к А не равен нулю, т.е. Supp(A) = {х, μА(х)> 0}.Например носителем множества "близкая к нулю" может являться множество температур в интервале от -4°С до +4°С.
Два множества А(х) и В(х) равны между собой, когда μА(х) = μB (х) для каждого элемента обоих множеств. Кардинальное число нечеткого множества А равно сумме коэффициентов принадлежности всех элементов к этому множеству, М(А) = ∑ μА(х). Это обобщение аналогичного понятия, относящегося к обычным множествам, для которых кардинальное число равно сумме элементов множества. Нечеткое множество является нормальным, если хотя бы один элемент этого множества имеет коэффициент принадлежности, равный 1. Сечение α нечеткого множества А образуется подмножеством Аа, содержащим те элементы множества А, для которых μА(х) > α (слабое сечение) или μА(х) ≥ α (сильное сечение), причем α [0,1].
Операции на нечетких множествах
На нечетких множествах, рассматриваемых как обобщение обычных множеств, можно определить ряд математических операций, являющихся обобщением аналогичных операций, выполняемых на "четких" множествах. К ним среди прочих относятся:
1. Логическая сумма множеств AB

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

Логическая сумма этих множеств С = А В равна:

2. Логическое произведение множеств А В

где знак обозначает оператор Min. Для данных из примера приведенного выше множество С, являющееся логическим произведением множеств А и В, будет иметь вид

3. Отрицание множества А

В отличие от обычных (четких) множеств, где отрицание элементов, принадлежащих к множеству, дает пустое множество, отрицание нечеткого множества определяет непустое множество, состоящее из элементов, функции принадлежности которых также определены на интервале [0,1].
4. Равенство множеств А и В
Нечеткие множества А(х) и В(х) равны между собой, когда для всех элементов xi обоих множеств выполняется условие μА(х) = μB (х)
5. Операция концентрации CON (А)

Эта операция весьма часто выполняется при действиях с лингвистической переменной, в которых она отождествляется с интенсификатором "очень".
6. Операция растяжения DIL(A)

Лингвистическое значение этой операции формулируется как "примерно" либо "приблизительно".
7. Алгебраическое произведение двух множеств А *В

8. Ограниченная сумма двух нечетких множеств А| + |В

9. Ограниченная разница двух нечетких множеств А| - |В

10. Ограниченное произведение двух нечетких множеств А| | В

11. Нормализация множества NORM (A)

Следует отметить, что множество А считается подмножеством множества B, т.е. А В, когда для всех элементов выполняется неравенство μА(хi) ≤ μB (хi). Например, если А = {0,5 / х1, 0,3/ х2, 0,1/ x3} и B = {0,6/x1, 0,5x2, 0,4/ х3}, то А В.
Меры нечеткости нечетких множеств
Для определения степени нечеткости множества введено понятие меры нечеткости, отвечающей так называемым условиям А. ДеЛуки и С.Термини, сводящейся к измерению уровня различия между множеством А и его отрицанием В.
Наиболее популярна мера Р.Егера, в соответствии с которой степень нечеткости множества А в метрике р, обозначаемая FUZp (А), определяется выражением

где Dp(A, А )- это мера расстояния между множествами А и А , содержащими п элементов. Значение р= 1 соответствует метрике Хемминга, в которой

а значение р = 2 соответствует метрике Евклида, в которой

Пример:

в соответствии с мерой Егера получаем


Другую меру нечеткости (энтропийную) предложил Б.Коско. Она основана на понятии кардинального числа множества. В соответствии с этой мерой

где M(F) обозначает кардинальное число множества F. Для множества А из приведенного выше примера получаем меру Коско, равную

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


Поскольку допускается применение множества нечетких правил, в ней также предусмотрен блок агрегирования, чаще всего реализуемый в виде логического сумматора (оператор Мах). Описываемая система вывода называется системой Мамдани-Заде. Она очень популярна в обычных (неадаптивных) нечетких системах. Как правило, в модели Мамдани-Заде присутствуют следующие операторы:
оператор логического или арифметического произведения для определения результирующего уровня активации, в котором учитываются все компоненты вектора х условия;
оператор логического или арифметического произведения для определения значения функции принадлежности для всей импликации A → В;
оператор логической суммы как агрегатор равнозначных результатов импликации многих правил;
оператор дефуззификации, трансформирующий нечеткий результат μА(у) в четкое значение выходной переменной у
Необходимо отметить, что также существуют системы нечеткого вывода, в которых исполнительный механизм непосредственно генерирует четкие значения, которые уже не требуется подвергать дефуззификации. В качестве примера назовем систему Такаги-Сугено-Канга.
Лекция 7. Автоматическое доказательство теорем
Автоматическое доказательство теорем ведет свое начало от основополагающих работ Эрбрана, который еще в 30-х годах XX в. предложил механическую процедуру дедуктивного вывода. В 60-е годы усилиями Ньюэлла и Саймона был создан общий решатель проблем, доказывающий теоремы формальной логики, разработанной Расселом и Уайтхедом, которые считали, что для математики достаточно иметь формальный вывод теорем из основных аксиом.
Однако результаты Чёрча и Тьюринга о неразрешимости логики предикатов первого порядка в какой-то степени оттеснили работы Эрбрана на задний план. Интерес к ним возрос лишь в 60-е годы, когда Гилмор реализовал эрбрановскую процедуру вывода на компьютере. Действительно, если нет процедуры для проверки противоречивости (общезначимости) формул логики предикатов первого порядка, то самое большее, что можно сделать — это проверить противоречивость (общезначимость) формулы, если она на самом деле таковой и является. Гилмору удалось доказать с помощью процедуры Эрбрана ряд простых теорем из логики высказываний и логики предикатов первого порядка, но его программа столкнулась с неразрешимыми трудностями при доказательстве более сложных теорем логики предикатов.
Ненамного эффективнее был метод Девиса и Патнема, с помощью которого были доказаны некоторые теоремы из логики предикатов первого порядка, не доказанные Гилмором. В 1964-1965 гг. независимо друг от друга появились обратный метод установления выводимости Маслова и принцип резолюции Робинсона. В те же годы Шаниным и его коллегами было разработано несколько версий алгоритма машинного поиска естественного логического вывода в исчислении высказываний (АЛПЕВ). Разработка версий системы АЛПЕВ и машинных алгоритмов вывода на основе обратного метода и принципа резолюции показала принципиальную возможность машинных доказательств теорем.
Сейчас принято считать, что автоматические рассуждения на основе формальной логики относятся к слабым (weak) методам доказательства теорем, и чисто синтаксические методы управления поиском не способны обрабатывать огромное пространство поиска при решении задач практической сложности. Поэтому альтернативой являются неформальные методы поиска, ad hoc стратегии, эвристики и рассуждения здравого смысла, которые человек использует при решении проблем.
Однако методы доказательства теорем, основанные на формальной логике типа логики предикатов первого порядка, остаются все еще сильным оружием при манипулировании знанием и их нельзя игнорировать. Продолжающийся интерес к автоматическому доказательству теорем заключается в симбиозе человека и машины при решении сложных проблем, когда на долю человека остаются задачи декомпозиции сложной проблемы на ряд подпроблем, поиска нужных эвристик для сокращения пространства поиска, а автоматическому решателю доводится выполнять формальные манипуляции со знанием на основе методов вывода. Ярким примером использования этого симбиоза являются экспертные системы, основанные на правилах, нашедшие широкое применение в медицине, геологии, управлении производством, транспортом, тепловыми и атомными станциями и т. п.
Конечно, доминирующий в автоматическом доказательстве теорем метод резолюции не является панацеей от всех бед, сопровождающих процедуры доказательства теорем, и мы вправе надеяться на появление более совершенных процедур дедуктивного вывода. Это касается и языка Пролог, неплохо зарекомендовавшего себя при решении логических проблем. Здесь можно согласиться с точкой зрения Н. Н. Непейводы, утверждавшего, что «есть смысл использовать Пролог для кусков программ, обладающих исключительно сложной логикой при явном задании вариантов. Все вычислительные части программ при этом стоит писать на других языках и иметь либо Пролог-программу, вызывающую вычислительные модули, либо (скажем) Паскаль-программу с внешней Пролог-подпрограммой».
Язык логики предикатов
Будем считать логику предикатов расширением логики высказываний за счет введения предикатов, квантора общности и квантора существования . Простые высказывания в логике высказываний будем называть атомами, принимающими два значения: истина (И) или ложь (Л). Символы И и JI называются истинностными значениями.
Сложные высказывания (формулы) будут образовываться из простых с помощью логических связок (не), & (конъюнкция), ˅ (дизъюнкция), →(импликация), ↔(эквивалентность).
(из книги Введение в теорию интеллектуальных систем// Кудрявцев)
В случае языка логики предикатов наш алфавит будет состоять из следующих групп символов:
счетный список предметных переменных х1,х2,...;
счетный список предметных констант а1, а2...;
счетный список функциональных символов f1, f2,...;
счетный список предикатных символов P1, Р2 ;
логические константы И, JI;
логические связки , ˅, &, →, ↔
кванторы и ;
скобки "(", ")" и запятая ", "
Каждый функциональный либо предикатный символ характеризуется своей арностью — некоторым натуральным числом. При этом предполагается, что для каждого натурального п имеется бесконечно много как предикатных, так и функциональных символов арности п.
Правильные выражения языка логики предикатов разбиваются на два непересекающихся множества — множество термов и множество формул. Дадим сначала индуктивное определение множества термов.
Т1) Однобуквенное слово, состоящее из предметной переменной либо, предметной константы, есть терм.
Т2) Если t1,..., tn — термы и g — функциональный символ арности п, то слово g(t1,..., tn) — есть терм.
Правила образования атомов (атомарных формул):
А1) всякое переменное высказывание X есть атом;
А2) если Pi — предикатная буква, a t1,..., tn — термы, то Рi(t1,..., tn) есть атом;
А3) других правил образования атомов нет.
Атом или его отрицание будем называть литерой.
Индуктивное определение формул логики предикатов опирается на уже введенное понятие терма.
Ф1) Однобуквенное слово состоящее из логической константы И либо JI, есть формула логики предикатов.
Ф2) Если t1,..., tn — термы и g — предикатный символ арности п, то слово g(t1,..., tn) есть формула логики предикатов.
Ф3) Если f и g — формулы логики предикатов, то слова (f),(f ˅ g),(f & g), (f →g) (f ↔g)суть формулы логики предикатов (такие формулы будем называть атомарными или атомами).
Ф4) Если f — формула логики предикатов их — предметная переменная, то слова (xf) и (xf) суть формулы логики предикатов.
Интерпретацией языка логики предикатов называем четверку (M,F1,F2,F3), такую что:
а)М — непустое множество, называемое областью интерпретации;
б)F1 — функция, сопоставляющая каждой предметной константе некоторый элемент из М;
в)F2 — функция, сопоставляющая каждому функциональному символу f арности п некоторую n-местную функцию, определенную на М и принимающую значения из М.
г)F3 — функция, сопоставляющая каждому предикатному символу Р арности п некоторой n-местный предикат определенный на М (функцию со значениями И, JI).
Если задана интерпретация I = (M,F1,F2,F3), то каждый терм t языка логики предикатов определяет в этой интерпретации некоторую функцию (t)I, определенную на М и принимающую значения из М, а каждая формула f — предикат (f)I, определенный на М (в вырожденных случаях (t)I может отождествляться с элементом М, а (f)I с логической константой).
Здесь используется следующее индуктивное определение:
Если х — предметная переменная, то (x)I есть тождественная функция от переменной х определенная на М.
Если а — предметная константа, то (а) I есть элемент F1(а) из М.
Если для термов t1,..., tn уже определены (t1)I,..., (tn)I f— функциональный символ арности п и ϕ = F2(f) — функция от п переменных, отображающая Мп в М, то

(И)I = И, (Л) I = Л.
Если для термов t1,..., tn уже определены (t1)I,..., (tn)I Р — предикатный символ арности п и π = F3(P) — предикат от п переменных, отображающий Мп в {И, JI}, то

Если для f и g уже определены (f)I и (g) I, то (f)I,(f ˅ g) I ,(f & g ) I, (f →g)I (f ↔g ) I получаются применением истинностных функций для , ˅,&, → ↔ к (f)I и (g) I.
Если уже определен предикат (f)I =ϕ(x1,..., xn), то (xif)I=ψ(x1,..., xi-1,..., xi+1,..., xn) - предикат, принимающий значение И на таких наборах α1,..., α i-1,..., α i+1,..., α n элементов М, что для каждого α i из М значение ϕ(α 1,..., α n) есть И. Аналогично, (xif)I = ξ(x1,..., xi-1,..., xi+1,..., xn)— предикат, принимающий значение И на таких наборах α1,..., α i-1,..., α i+1,..., α n элементов M, что существует α i из М, что значение ϕ(α 1,..., α n) есть И.
Вхождение переменной х в формулу f логики предикатов, расположенное внутри подформул вида (xg)I либо (xg), называется связанным, вхождения переменных не являющиеся связанными, называются свободными. Переменная имеющая хотя бы одно свободное вхождение в формулу либо терм f, называется свободной переменной f. Как нетрудно видеть, функция либо предикат (f)I, определенная выше, зависит лишь от свободных переменных f. Формула без свободных переменных называется замкнутой.
В формуле x1((x2P1(x2, x1)) ˅P2(x2,x1)) первое вхождение переменной х2 связанное, а второе — свободное, оба вхождения переменной х1 связанные. Тем самым, у этой формулы одна свободная переменная — х2. Формула ((x1P1(x1)) → (x2P2(x2))) — пример замкнутой формулы.
Терм t называется свободным для переменной хi в формуле логики предикатов f, если никакое свободное вхождение хi, в f не лежит в области действия никакого квантора Qxj, где Q {, }, xj — переменная, входящая в терм t.
Например, терм fi(x1,x3) свободен для х1 в формуле
((x2P1(x1,x2))→P2(x1)),
но не свободен для x1 в формуле
(x3(x2(P1(x1,x2)→P2(x1)))).
Если f — есть формула логики предикатов, х — свободная предметная переменная формулы f и t — терм, то через обозначим результат подстановки в f терма t вместо всех свободных вхождений переменной х.
Лемма (об интерпретациях). Если f — есть формула логики предикатов, х — свободная предметная переменная формулы f и t — терм, свободный для переменной х в f, то для любой интерпретации I формула ()I определяет предикат, получающийся подстановкой в (f)I функции (t)I вместо переменной х.
Если формула f определяет в интерпретации I предикат, тождественно равный И, то она называется истинной в I, а I в этом случае называется моделью для f
Формулу логики предикатов f называем общезначимой, если она истинна во всех интерпретациях формула логики высказываний (предикатов), которая ложна во всех интерпретациях, называется противоречием, и выполнимой, если хотя бы в одной интерпретации она определяет не тождественно ложный предикат и аналогично, формула называется опровержимой, если она ложна по крайней мере в одной интерпретации.
Если формула f1&... &fп → f0 общезначима, то f0 называется логическим следствием формул f1,..., fп, если формула f1 ↔ f2 общезначима, то формулы f1 и f2 называются эквивалентными.
Формула ((P1(x1)) ˅ P1(x1)) есть пример общезначимой формулы. Формула ((P1(x1)) ˅ P1(f1(x1))) — выполнима, но не общезначима.
Для того чтобы сократить количество скобок в формуле, используем правила силы операций:

Две формулы F и Ф равносильны, т. е. F = Ф, тогда и только тогда, когда истинностные значения этих формул совпадают при любой интерпретации F и Ф.
Нормальные и стандартные формы
(Достоверный и правдоподобный вывод в интеллектуальных системах // Головина)
При разработке методов автоматического доказательства теорем необходимо представить все формулы, как логики высказываний, так и логики предикатов первого порядка, в некотором стандартном виде.
Говорят, что формула логики высказываний f представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет форму f = f1 & f2 & ... & fп, где каждая из fi (i = 1, n) есть дизъюнкция литер. Например,
f= (X1 ˅ Х2) & (X1 ˅Х2 ˅Х3) & Х3
представлена в КНФ.
Аналогично говорят, что формула логики высказываний f представлена в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет форму f=  f1 ˅ f2 ˅ ... ˅ fп, где каждая из fi (i = 1, n) есть конъюнкция литер. Например,
f= (X1 & Х2&Х3) ˅ (X1 &Х2) ˅ Х3
представлена в ДНФ.
В логике предикатов также имеется нормальная форма, называемая пренексной нормальной формой (ПНФ). Необходимость введения ПНФ будет обусловлена в дальнейшем упрощением процедуры доказательства теорем.
Определение ПНФ. Говорят, что формула F логики предикатов находится в ПНФ тогда и только тогда, когда ее можно представить в форме
1x1 2х2 ... nxn М,
где Ǩi xi I = 1, n, есть либо xi, либо xi
М — бескванторная формула.
Иногда 1x1 2х2 ... nxn называют префиксом, а М — матрицей формулы F.
Например, формула F1 = ху (Q(x,y) ˅ P(f(x)) → R(x,g(y))) находится в ПНФ, а формула F2 = х(Р(х) → yQ(x, у)) — не в ПНФ.
Существует алгоритм, преобразующий произвольную заданную формулу в равносильную ей формулу, имеющую пренексный вид. Алгоритм состоит из следующих шагов.
Шаг 1. Исключение логических связок ↔и →. Многократно (пока это возможно) делаем замены: F↔Ф = (F ˅ Ф) & (F ˅Ф), F →Ф = F ˅ Ф. Результатом этого шага будет формула, равносильная исходной и не содержащая связок ↔и →
Шаг 2. Продвижение знака отрицания до атома. Многократно (пока это возможно) делаем замены:

Шаг 3. Переименование связанных переменных. Многократно (пока это возможно) применяется следующее правило: найти самое левое вхождение переменной, такое, что это вхождение связано (некоторым квантором), но существует еще одно вхождение этой же переменной; затем сделать замену связанного вхождения на вхождение новой переменной.
Шаг 4. Вынесение кванторов. Для этого используем следующие равносильности:

где – кванторы либо
Пример




Можно рассматривать еще более узкий класс формул, так называемых -формул.
Формула F называется -формулой, если она представлена в ПНФ, причем кванторная часть состоит только из кванторов общности, т. е. F = x1 х2 ... xn М, где М — бескванторная формула.
Отсюда возникает задача устранения кванторов существования в формулах, представленных в ПНФ. Это можно сделать путем введения сколемовских функций.
Пусть формула F представлена в ПНФ. F = 1x1 2х2 ... nxn М где j {, }, j = l,n.
Пусть j (1 ≤ i ≤ n) — квантор существования в префиксе 1x1 2х2 ... nxn. Если i = 1, т.е. ни один квантор общности не стоит впереди квантора существования, то выбираем константу с из области определения М, отличную от констант, встречающихся в М, и заменяем х1на с в М. Вычеркиваем из префикса квантор существования 1x1.Если перед квантором существования стоит j1 j2 ... jm кванторов общности, то выбираем m-местный функциональный символ f, отличный от функциональных символов в М, и заменяем xi на f(xj1,..., xjm)называемую сколемовской функцией, в М. Квантор существования I xi вычеркиваем из префикса. Аналогично удаляются и другие кванторы существования в ПНФ. В итоге получаем -формулу. Опишем алгоритм последовательного исключения кванторов существования.
Алгоритм Сколема
Шаг 1. Формулу представить в ПНФ.
Шаг 2. Найти наименьший индекс i такой, что1 2 ... i-1 все равны , но I= . Если i = 1, т.е. квантор стоит на первом месте, то вместо x1 в формулу М подставить константу с, отличную от констант, встречающихся в М, и квантор удалить из префикса. Если такого i нет, то СТОП: формула F является -формулой.
Шаг 3. Взять новый (i — 1)-местный функциональный символ fi не встречающийся в F. Заменить F на формулу

Шаг 4. Перейти к шагу 2.
Пример

Рассмотрим теперь преобразование бескванторной части (матрицы) к виду так называемых дизъюнктов (clauses). Дизъюнктом называется формула вида L1˅L2 ˅ ... ˅Lk, где Li (г = 1, k) — произвольная литера.
Дизъюнкт, не имеющий литер, называется пустым дизъюнктом. По определению он всегда ложен.
Формула, представленная набором дизъюнктов, объединенных кванторами общности находится в Сколемовской стандартной форме (ССФ):
x1x2 ... xn[D1 & D2 & ... & Dk],
где D1 , D2 , ... & Dk — дизъюнкты, a x1, х2,..., хn — различные переменные, входящие в эти дизъюнкты.
Процедура вывода Эрбрана
Как известно множество дизъюнктов S невыполнимо тогда и только тогда, когда оно принимает значение «ложь» при всех интерпретациях на любых областях. Однако в силу невозможности рассмотрения подобных интерпретаций хорошо было бы найти такую специальную область интерпретации, установив на которой факт невыполнимости множества дизъюнктов, можно было бы сделать вывод о невыполнимости этого множества на любых других областях интерпретаций. Такая область, к счастью, имеется, и она называется универсумом Эрбрана. Определим его.
Пусть Н0 — множество констант, появляющихся во множестве дизъюнктов S. Если в S нет констант, то в Н0 включается некоторая константа, например, Н0 = {а}. Для i = 1,2,... Hi+1 = H i {fn(t1,t2, ..., tn)}, где fn — все n-местные функциональные символы, встречающиеся в S, а t1,t2, ..., tn — элементы множества Hi. Тогда будем Н = Н называть универсумом Эрбрана для S, а Hi — его уровнем i.
Пример

Лекция 8. Искусственные нейронные сети
Биологический нейрон
Нейрон (нервная клетка) является особой биологической клеткой, которая обрабатывает информацию. Он состоит из тела (cell body), или сомы (soma), и отростков нервных волокон двух типов - дендритов (dendrites), по которым принимаются импульсы, и единственного аксона (axon), по которому нейрон может передавать импульс. Тело нейрона включает ядро (nucleus), которое содержит информацию о наследственных свойствах, и плазму, обладающую молекулярными средствами для производства необходимых нейрону материалов. Нейрон получает сигналы (импульсы) от аксонов других нейронов через дендриты (приемники) и передает сигналы, сгенерированные телом клетки, вдоль своего аксона (передатчика), который в конце разветвляется на волокна (strands). На окончаниях этих волокон находятся специальные образования - синапсы (synapses), которые влияют на величину импульсов.

Схема синапса, включает в себя:
предсинаптическую клетку,
синаптические пузырьки,
синаптическую щель
постсинаптическую клетку.

Рис. Схема синапса.
Передача сигнала происходит с помощью химических трансмиттеров (передатчики), которые, пересекая синаптическую щель, достигают нейрона-приемника, усиливая или ослабляя его тенденцию к возбуждению.
Кора головного мозга человека содержит около 1011 нейронов. Каждый нейрон связан с 103-104 другими нейронами. В целом мозг человека содержит приблизительно от 1014 до 1015 взаимосвязей
Нейроны взаимодействуют короткими сериями импульсов продолжительностью, как правило, несколько миллисекунд. Сообщение передается посредством частотно-импульсной модуляции. Частота может изменяться от нескольких единиц до сотен герц, что в миллион раз медленнее, чем быстродействующие переключательные электронные схемы. Тем не менее сложные задачи распознавания человек решает за несколько сотен миллисекунд. Эти решения контролируются сетью нейронов, которые имеют скорость выполнения операций всего несколько миллисекунд. Это означает, что вычисления требуют не более 100 последовательных стадий. Другими словами, для таких сложных задач мозг «запускает» параллельные программы, содержащие около 100 шагов. Рассуждая аналогичным образом, можно обнаружить, что количество информации, посылаемое от одного нейрона другому, должно быть очень малым (несколько бит). Отсюда следует, что основная информация не передается непосредственно, а захватывается и распределяется в связях между нейронами.
Историческая справка о развитии в области искусственных нейронных сетей
Под нейронными сетями (Artificial Neural System (ANS) - Искусственные нейронные системы) подразумеваются вычислительные структуры, которые моделируют простые биологические процессы, обычно ассоциируемые с процессами человеческого мозга. Они представляют собой распределенные и параллельные системы, способные к адаптивному обучению путем анализа положительных и отрицательных воздействий. Элементарным преобразователем в данных сетях является искусственный нейрон или просто нейрон, названный так по аналогии с биологическим прототипом.
Приведем краткую историческую справку.
1943 г. У. Маккалох (W. McCulloch) и У. Питтс (W. Pitts) предложили модель нейрона и сформулировали основные положения теории функционирования головного мозга.
1949 г. Д. Хебб (D. Hebb) высказал идеи о характере соединений нейронов мозга и их взаимодействии (клеточные ансамбли, синаптическая пластичность). Впервые предложил правила обучения нейронной сети
1957 г. Ф. Розенблатт (F. Rosenblatt) разработал принципы организации и функционирования персептронов, предложил вариант технической реализации первого в мире нейрокомпьютера Mark.
1959 г. Д. Хьюбел (D. Hubel) и Т. Визель (Т. Wiesel) показали распределенный и параллельный характер хранения и обработки информации в биологических нейронных сетях.
1960-1968 гг. Активные исследования в области искусственных нейронных сетей, например, АДАЛИНА и МАДАЛИНА В. Уидроу (W. Widrow) (1960-1962 гг.), ассоциативные матрицы К. Штайнбуха (К. Steinbuch) (1961 г.).
1969 г. Публикация книги М. Минского (М. Minsky) и С. Пейперта (S. Papert) «Персептроны», в которой доказывается принципиальная ограниченность возможностей персептронов. Угасание интереса к искусственным нейронным сетям. Потеря интереса к этой теме на Западе.
1970-1976 гг. Активные разработки в области персептронов в СССР (основные заказчики - военные ведомства).
Конец 1970-х гг. Возобновление интереса к искусственным нейронным сетям как следствие накопления новых знаний о деятельности мозга, а также значительного прогресса в области микроэлектроники и компьютерной техники.
1982-1985 гг. Дж. Хопфилд (J. Hopfield) предложил семейство оптимизирующих нейронных сетей, моделирующих ассоциативную память.
1982 работа Кохонена просвещенная самоорганизующимся картам, использующим одно- или двухмерную структуру пространственной решетки. Это метод проецирования многомерного пространства наблюдений на пространство более низкой размерности (чаще всего, двухмерное) – карту. Основные направления применения самоорганизующихся карт – поиск и анализ взаимосвязей и закономерностей во входных данных: 1)Кластеризация – нахождение групп похожих объектов. 2) Визуализация данных. На рисунках цветом обозначают, насколько велико значение рассматриваемой компоненты вектора весов в том или ином узле.
1985 г. Появление первых коммерческих нейрокомпьютеров, например, Mark III фирмы TRW (США).
1987 г. Начало широкомасштабного финансирования разработок в области ИНС и НК в США, Японии и Западной Европе (японская программа «Human Frontiers» и европейская программа «Basic Research in Adaptive Intelligence and Neurocomputing»).
1989 г. Разработки и исследования в области ИНС и НК ведутся практически всеми крупными электротехническими фирмами. Нейрокомпьютеры становятся одним из самых динамичных секторов рынка (за два года объем продаж вырос в пять раз). Агентством DARPA (Defence Advanced Research Projects Agency) министерства обороны США начато финансирование программы по созданию сверхбыстродействующих образцов НК для разнообразных применений.
1990 г. Активизация советских исследовательских организаций в области ИНС и НК (Институт кибернетики им. Глушкова в Киеве, Институт многопроцессорных вычислительных систем в Таганроге, Институт нейрокибернетики в Ростове-на-Дону). Общее число фирм, специализирующихся в области ИНС и НК, достигает трехсот.
1991 г. Годовой объем продаж на рынке ИНС и НК приблизился к 140 млн. долларам. Создаются центры нейрокомпьютеров в Москве, Киеве, Минске, Новосибирске, С.-Петербурге.
1992 г. Работы в области ИНС находятся стадии интенсивного развития. Ежегодно проводится десятки международных конференций и форумов по нейронным сетям, число специализированных периодических научных изданий по указанной тематике достигло двух десятков наименований.
1997 г. Годовой объем продаж на рынке ИНС и НК превысил 2 млрд. долларов, а ежегодный прирост составил 50%.
2000 г. Переход на субмикронные и нанотехнологии, а также успехи молекулярной и биомолекулярной технологии приводят к принципиально новым архитектурным и технологическим решениям по созданию нейрокомпьютеров.
Структура искусственного нейрона и его математическая модель.
Он состоит из элементов трех типов: умножителей (синапсов), сумматора и нелинейного преобразователя. Синапсы осуществляют связь между нейронами, умножают входной сигнал на число, характеризующее силу связи, (вес синапса). Сумматор выполняет сложение сигналов, поступающих по синаптическим связям от других нейронов, и внешних входных сигналов. Нелинейный преобразователь реализует нелинейную функцию одного аргумента - выхода сумматора. Эта функция называется функцией активации или передаточной функцией нейрона.
Математическая модель нейрона

где wi - вес (weight) синапса, i = 1...n; b - значение смещения (bias), s - результат суммирования (sum); хi - компонент входного вектора (входной сигнал), i = 1 ...n; у - выходной сигнал нейрона; n - число входов нейрона; f - нелинейное преобразование (функция активации).

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





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

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

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

Рис. Примеры активационных функций.
а - функция единичного скачка, б - линейный порог(гистерезис) в- сигмоид (логистическая функция), г - сигмоид (гиперболический тангенс)
Лекция 9. Классификация нейронных сетей и их свойства
Нейронная сеть представляет собой совокупность нейроподобных элементов, определенным образом соединенных друг с другом и с внешней средой с помощью связей, определяемых весовыми коэффициентами. В зависимости от функций, выполняемых нейронами в сети, можно выделить три их типа
•входные нейроны, на которые подается вектор, кодирующий входное воздействие или образ внешней среды; в них обычно не осуществляется вычислительных процедур, а информация передается с входа на выход путем изменения их активации;
•выходные нейроны, выходные значения которых представляют выходы нейронной сети; преобразования в них осуществляются по активационной функции ;
•промежуточные нейроны. составляющие основу нейронных сетей, преобразования в которых выполняются также по активационной функции.
С точки зрения топологии можно выделить три основных типа нейронных сетей:
•полносвязные;
•многослойные или слоистые;
•слабосвязные (с локальными связями).
-1905447040В полносвязных нейронных сетях каждый нейрон передает свой выходной сигнал остальным нейронам, в том числе и самому себе. Все входные сигналы подаются всем нейронам. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети.
В многослойных нейронных сетях нейроны объединяются в слои. Слой содержит совокупность нейронов с едиными входными сигналами. Число нейронов в слое может быть любым и не зависит от количества нейронов в других слоях. В общем случае сеть состоит из Q слоев, пронумерованных слева направо. Внешние входные сигналы подаются на входы нейронов входного слоя (его часто нумеруют как нулевой), а выходами сети являются выходные сигналы последнего слоя. Кроме входного и выходного слоев в многослойной нейронной сети есть один или несколько скрытых слоев. Связи от выходов нейронов некоторого слоя q к входам нейронов следующего слоя (q+1) называются последовательными.
В свою очередь, среди многослойных нейронных сетей выделяют следующие типы.
1) Монотонные.
Это частный случай слоистых сетей с дополнительными условиями на связи и нейроны. Каждый слой кроме последнего (выходного) разбит на два блока: возбуждающий и тормозящий. Связи между блоками тоже разделяются на тормозящие и возбуждающие. Если от нейронов блока А к нейронам блока В ведут только возбуждающие связи, то это означает, что любой выходной сигнал блока является монотонной неубывающей функцией любого выходного сигнала блока А Если же эти связи только тормозящие, то любой выходной сигнал блока В является невозрастающей функцией любого выходного сигнала блока А. Для нейронов монотонных сетей необходима монотонная зависимость выходного сигнала нейрона от параметров входных сигналов
539755060952)Сети без обратных связей. В таких сетях нейроны входного слоя получают входные сигналы, преобразуют их и передают нейронам первого скрытого слоя, и так далее вплоть до выходного, который выдает сигналы для интерпретатора и пользователя. Если не оговорено противное, то каждый выходной сигнал q-го слоя подается на вход всех нейронов (q+1)-го слоя; однако возможен вариант соединения q-го слоя с произвольным (q+р)-м слоем
Среди многослойных сетей без обратных связей различают полносвязанные (выход каждого нейрона q-го слоя связан с входом каждого нейрона (q+1)-го слоя) и частично полносвязанные. Классическим вариантом слоистых сетей являются полносвязанные сети прямого распространения.
3)Сети с обратными связями. В сетях с обратными связями информация с последующих слоев передается на предыдущие. Среди них, в свою очередь, выделяют следующие:

Рис. Частично-рекуррентные сети
а- Элмана б- Жордана.
• слоисто-циклические, отличающиеся тем, что слои замкнуты в кольцо, последний слой передает свои выходные сигналы первому; все слои равноправны и могут как получать входные сигналы, так и выдавать выходные;
•слоисто-полносвязанные состоят из слоев, каждый из которых представляет собой полносвязную сеть, а сигналы передаются как от слоя к слою, так и внутри слоя; в каждом слое цикл работы распадается на три части, прием сигналов с предыдущего слоя, обмен сигналами внутри слоя, выработка выходного сигнала и передача к последующему слою,
•полносвязанно-слоистые, по своей структуре аналогичные слоисто-полносвязанным, но функционирующим по-другому: в них не разделяются фазы обмена внутри слоя и передачи следующему, на каждом такте нейроны всех слоев принимают сигналы от нейронов, как своего слоя, так и последующих.
В слабосвязных нейронных сетях нейроны располагаются в узлах прямоугольной или гексагональной решетки. Каждый нейрон связан с четырьмя (окрестность фон Неймана), шестью (окрестность Голея) или восемью (окрестность Мура) своими ближайшими соседями.
Известные нейронные сети можно разделить по типам структур нейронов на гомогенные (однородные) и гетерогенные. Гомогенные сети состоят из нейронов одного типа с единой функцией активации, а в гетерогенную сеть входят нейроны с различными функциями активации.
Существуют бинарные и аналоговые сети. Первые из них оперируют только двоичными сигналами, и выход каждого нейрона может принимать значение либо логического ноля (заторможенное состояние) либо логической единицы (возбужденное состояние).
Еще одна классификация делит нейронные сети на синхронные и асинхронные. В первом случае в каждый момент времени лишь один нейрон меняет свое состояние, во втором - состояние меняется сразу у целой группы нейронов, как правило, у всего слоя. Алгоритмически ход времени в нейронных сетях задается итерационным выполнением однотипных действий над нейронами.
Сети можно классифицировать также по числу слоев. Теоретически число слоев и число нейронов в каждом слое может быть произвольным, однако фактически оно ограничено ресурсами компьютера или специализированных микросхем, на которых обычно реализуется нейронная сеть. Чем сложнее сеть, тем более сложные задачи она может решать.
Выбор структуры нейронной сети
Выбор структуры нейронной сети осуществляется в соответствии с особенностями и сложностью задачи. При этом необходимо руководствоваться следующими основными правилами:
•возможности сети возрастают с увеличением числа нейронов сети, плотности связей между ними и числом слоев;
•введение обратных связей наряду с увеличением возможностей сети поднимает вопрос о динамической устойчивости сети;
•сложность алгоритмов функционирования сети, введение нескольких типов синапсов способствует усилению мощности нейронной сети.
Вопрос о необходимых и достаточных свойствах сети для решения задач того или иного рода представляет собой целое направление нейрокомпьютерной науки.
Работы Колмогорова-Арнольда и теорема Хехт-Нильсена.
Работы Колмогорова-Арнольда:
•теорема о возможности представления непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (1956 г),
•теорема о представлении любой непрерывной функции трех переменных в виде суммы функций не более двух переменных (1957 г),
•теорема о представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одного переменного и сложения (1957 г)
Теорема Хехт-Нильсена доказывает решаемость задачи представления функции произвольного вида (функции многих переменных) с помощью двухслойной нейронной сети с прямыми полными связями с n нейронами входного слоя, (2n+1) нейронами скрытого слоя с заранее известными ограниченными функциями активации (например, сигмоидальными) и m нейронами выходного слоя с нелинейными монотонно возрастающими функциями активации. Тем самым для любого множества пар (X, Y) существует двухслойная однородная (с одинаковыми функциями активации) нейронная сеть первого порядка с последовательными связями и с конечным числом нейронов, которая выполняет отображение X → У, выдавая на каждый входной сигнал Х правильный выходной сигнал Y.
Лекция 10. Однослойный и многослойный персептрон
Персептроны.
-83820461645В качестве научного предмета искусственные нейронные сети впервые заявили о себе в 40-е годы. Стремясь воспроизвести функции человеческого мозга, исследователи создали простые аппаратные (а позже программные) модели биологического нейрона и системы его соединений.
Первое систематическое изучение искусственных нейронных сетей было предпринято Маккалохом и Питтсом в 1943 г. Позднее они исследовали сетевые парадигмы для распознавания изображений, подвергаемых сдвигам и поворотам, используя при этом простую нейронную модель. Элемент ∑ умножает каждый вход хi на вес wi и суммирует взвешенные входы.
Если эта сумма больше заданного порогового значения, выход равен единице, в противном случае — нулю. Эти системы получили название персептронов. Они состоят из одного слоя искусственных нейронов, соединенных с помощью весовых коэффициентов с множеством входов
Алгоритм обучения
Шаг 1. Проинициализировать элементы весовой матрицы (обычно небольшими случайными значениями).
Шаг 2. Подать на входы один из входных векторов, которые сеть должна научиться различать, и вычислить ее выход.
Шаг 3. Если выход правильный, перейти на шаг 4.
Иначе — вычислить разницу между идеальным d и полученным Y значениями выхода:
δ = d-Y.
Модифицировать веса в соответствии с формулой
W i j(t + 1) = Wi j(t) + η δ xi,
где t и (t + 1) — номера соответственно текущей и следующей итераций;
η — коэффициент скорости обучения, 0 < η < 1;
i — номер входа;
j — номер нейрона в слое.
Очевидно, что если d > Y, то весовые коэффициенты будут увеличены и, тем самым, уменьшат ошибку. В противном случае они будут уменьшены, и Y тоже уменьшится, приближаясь к d.
Шаг 4. Цикл с шага 2, пока сеть не перестанет ошибаться.
На втором шаге на разных итерациях поочередно в случайном порядке предъявляются все возможные входные векторы. К сожалению, нельзя заранее определить число итераций, которые потребуется выполнить, а в некоторых случаях и гарантировать полный успех.

Рис. Двухслойный персептрон
Ограниченность возможности одного нейрона
Выходной сигнал у при фиксированных значениях весов зависит от расположения входного вектора х, который определяет гиперплоскость, разделяющую многомерное пространство на два подпространства.
Продемонстрируем ограниченность возможностей однослойных сетей на примере реализации двухвходовой логической функции XOR. Для упрощения будем использовать функцию активации в виде одноступенчатого порога. Множество данных для обучения логической функции XOR представлено в табл.
-9652033655Множество для обучения функции XOR

Легко показать, что в этом случае невозможно провести единственную линию, разделяющую пространство данных на два подпространства, из которых одно соответствовало бы входному сигналу 1, а другое - 0 (на рис. заштрихованная область относится к одному классу, а незаштрихованная - ко второму). Внутри заштрихованной области выходной сигнал нейроиа должен быть равен 1, а за ее пределами - 0. Такое условие не может быть выполнено при использовании для разделения пространства единственной прямой (одного нейрона) независимо от значений параметров этой прямой ( весов w10, w11, w12). Таким образом, однослойный персептрон не в состоянии реализовать даже такую несложную функцию, как XOR. Эту проблему легко разрешить путем расширения искусственной нейронной сети. С этой целью добавим в слой еще один нейрон и подберем веса обоих нейронов таким образом, чтобы они разделяли пространство на две части в зависимости от входного вектора х = [х1, x2]т:
60960118110(первый нейрон)
u1 = w11 х1 + w12 х2 + w10 >0
u1 = w11х1 + w12 х2 + w10 < 0
(второй нейрон)
u 2 = w21 х1+ + w22 x2 + w20 >0
u 2 = w21 х1 + w22 x2 + w20 < 0.
Подбор весов должен обеспечить разделение пространства, как показано на следующем рисунке.
Решение проблемы нелинейного разделения путем применения двух линейных разделителей
Общая часть подмножеств, соответствующая условиям u1>0, u1>0, определила область, отделенную от остального пространства, соответствующего условиям u1 < 0 u1 < 0.
Добавлением на выходе сети еще одного слоя, состоящего из единственного нейрона, можно реализовать функцию логического суммирования, выделяющую общую часть подмножеств ui > 0, ui >0. Окончательная структура ИНС, выполняющей функцию XOR, представлена на рис. 3.4. Следует отметить, что добавление в сеть дополнительного слоя позволило разрешить проблему невозможности линейного разделения данных. Каждый нейрон скрытого слоя осуществляет дополнительное линейное разделение плоскости, причем граница такого раздела на области ui >0 и ui < 0 зависит от значений весов нейрона. Выходной слой выполняет соответствующую линейную комбинацию (например, логическую с сумму) подобластей, на которые множество входных данных было разделено нейронами скрытого слоя функцию XOR.



Лекция 11. Алгоритмы обучения нейронных сетей
Способность к обучению является фундаментальным свойством мозга. Наличие этого свойства в ИНС является наиболее характерной, и привлекательной чертой, сближающей их с мозгом и отличающей от других вычислительных систем.
В ИНС обучение рассматривается как настройка параметров сети для решения поставленной задачи. В качестве таких параметров обычно выступают синаптические коэффициенты (веса связей). Кроме весов связей в параметры сети могут включаться также пороги (смещения). Цель обучения ИНС - достичь желаемой выходной реакции сети на некоторое множество входных сигналов называемое обучающей выборкой. Входное и выходное множества сигналов удобно интерпретировать как вектора. Процесс обучения ИНС осуществляется путем последовательного предъявления входных векторов из обучающей выборки с одновременной подстройкой параметров сети в соответствии с некоторой процедурой, называемой алгоритмом обучения. Процедура обучения производится до тех пор, пока не будет достигнута желаемая выходная реакция ИНС для всей обучающей выборки.
В математическом смысле обучение ИНС представляет собой итерационную процедуру, направленную на такую подстройку параметров сети, чтобы некоторый функционал качества обращался в оптимум для всей обучающей выборки. В роли такого функционала обычно используется функция ошибки, характеризующая степень близости отображения входного вектора в желаемый выходной. В общем случае функционал качества (функция ошибки) может иметь произвольный вид, поэтому обучение ИНС превращается в задачу многоэкстремальной невыпуклой многомерной оптимизации.
Для формирования процесса обучения необходимо, прежде всего, иметь модель внешней среды, в которой функционирует ИНС, т.е. определить доступную для сети информацию. Эта модель определяет парадигму обучения. В рамках определенной парадигмы обучения далее конструируются правила подстройки параметров, т.е. конкретный алгоритм обучения.
Для управляемого обучения сети пользователь должен подготовить набор обучающих данных. Эти данные представляют собой примеры входных данных и соответствующих им выходов. Сеть учится устанавливать связь между первыми и вторыми. Обычно обучающие данные берутся из исторических сведений. В рассмотренных выше примерах это могут быть предыдущие значения цен акций и индекса FTSE, сведения о прошлых заемщиках - их анкетные данные и то, успешно ли они выполнили свои обязательства, примеры положений робота и его правильной реакции.
Затем нейронная сеть обучается с помощью того или иного алгоритма управляемого обучения (наиболее известным из них является метод обратного распространения, предложенный в работе Rumelhart, 1986), при котором имеющиеся данные используются для корректировки весов и пороговых значений сети таким образом, чтобы минимизировать ошибку прогноза на обучающем множестве. Если сеть обучена хорошо, она приобретает способность моделировать (неизвестную) функцию, связывающую значения входных и выходных переменных, и впоследствии такую сеть можно использовать для прогнозирования в ситуации, когда выходные значения неизвестны.
Сбор данных для нейронной сети
Если задача будет решаться с помощью нейронной сети, то необходимо собрать данные для обучения. Обучающий набор данных представляет собой ряд наблюдений, для которых указаны значения входных и выходных переменных. Первый вопрос, который нужно решить, - какие переменные использовать и сколько (и каких) наблюдений собрать.
Выбор переменных (по крайней мере, первоначальный) осуществляется интуитивно. Ваш опыт работы в данной предметной области поможет определить, какие переменные являются важными
Вопрос о том, сколько наблюдений нужно иметь для обучения сети, часто оказывается непростым. Известен ряд эвристических правил, увязывающих число необходимых наблюдений с размерами сети. Простейшее из них гласит, что число наблюдений должно быть в десять раз больше числа связей в сети. На самом деле это число зависит также от (заранее неизвестной) сложности того отображения, которое нейронная сеть стремится воспроизвести. С ростом количества переменных количество требуемых наблюдений растет нелинейно, так что уже при довольно небольшом числе переменных (например, 50) может потребоваться огромное число наблюдений. Эта трудность известна как «проклятие размерности», и мы обсудим ее дальше в этой главе.
Для большинства реальных задач, как правило, достаточно нескольких сотен или тысяч наблюдений. Для особо сложных задач может потребоваться еще большее количество, однако очень редко может встретиться (даже тривиальная) задача, где хватило бы менее сотни наблюдений. Если данных меньше, чем здесь сказано, то на самом деле у вас недостаточно информации для обучения сети и лучшее, что можно сделать в такой ситуации, это попробовать подогнать к данным некоторую линейную модель.
Три парадигмы обучения
Существуют три парадигмы обучения: «с учителем», «без учителя» (самообучение) и смешанная.
Обучение с учителем (supervised learning) предполагает, что ИНС располагает правильными ответами (выходными векторами) на каждый входной образ (входной вектор). При обучении каждому входному вектору обучающей выборки учитель ставит в соответствие целевой вектор, т.е. правильную реакцию сети. Пара входного и целевого вектора называется обучающей парой. Параметры сети подстраиваются так, чтобы ответы были максимально близкими к правильным.
Обучить нейросеть — значит, сообщить ей, чего мы от нее добиваемся. Этот процесс очень похож на обучение ребенка алфавиту. Показав ребенку изображение буквы «А», мы спрашиваем его: «Какая это буква?» Если ответ неверен, мы сообщаем ребенку тот ответ, который мы хотели бы от него получить: «Это буква А». Ребенок запоминает этот пример вместе с верным ответом, т.е. в его памяти происходят некоторые изменения в нужном направлении. Мы будем повторять процесс предъявления букв снова и снова до тех пор, когда все буквы будут твердо запомнены. Такой процесс называют «обучение с учителем»
Процесс обучения начинается после задания начальных значений весов сети. В общем случае они могут быть произвольными, например, нулевыми. При наличии априорной информации об особенностях процесса обучения, начальные значения весов могут выбираться из каких-либо дополнительных соображений. При предъявлении очередного входного вектора обучающей выборки выходной вектор сравнивается с целевым вектором, и по разности этих векторов алгоритм обучения производит коррекцию весов (а возможно и порогов), с целью минимизировать эту разность (ошибку). Процедура повторяется для всего обучающего множества до тех пор, пока ошибка по всему обучающему множеству не достигнет приемлемо низкого уровня. Функция ошибки численно определяет сходство фактических и целевых выходных векторов сети для всей обучающей выборки. Наиболее распространенной функцией ошибки является среднеквадратичное отклонение:

где zAik - фактический выходной сигнал нейрона i;
zTik - желаемый (целевой, терминальный) выходной сигнал нейрона i;
i = 1,N - число нейронов выходного слоя;
k = 1, L - размер обучающей выборки.
Используются также и другие функции ошибки.
Разновидностью обучения с учителем является критическая оценка учителем правильности выходного сигнала сети без знания самого выходного сигнала.
В зависимости от решаемой задачи в обучающей выборке используются те или иные группы данных с различной размерностью. Входными данными обучающей выборки могут быть, например, таблицы чисел, сигналы, изображения, распределения случайных величин и др. По типу входные и выходные данные могут быть: бинарные (0 и 1), биполярные (-1 и 1), целые и действительные числа из некоторого диапазона. Для решения практических задач часто используются обучающие выборки большого объема и большой размерности. Из-за ограниченного объема оперативной памяти компьютера разместить в ней такие обучающие выборки может оказаться невозможным. В этих случаях обучающая выборка делится на страницы - группы примеров. В каждый отрезок времени лишь одна страница примеров располагается в оперативной памяти компьютера, остальные — во внешней памяти. Страницы последовательно загружаются в оперативную память компьютера. Обучение сети происходит по всей совокупности страниц-примеров, т.е. по всей обучающей выборке.
В настоящее время отсутствует универсальная методика построения обучающих выборок. Они формируются обычно по усмотрению пользователя для каждой конкретной решаемой задачи.
Обучение без учителя (самообучение) (unsupervised learning) по своей природе ближе к биологическому прототипу - мозгу. Самообучение не предполагает наличия правильных ответов ИНС, т.е. целевого вектора. Располагая только информацией из обучающей выборки, алгоритм самообучения «самостоятельно» выявляет внутреннюю структуру входных данных или корреляцию обучающих и выходных данных. Алгоритм самообучения подстраивает веса связей так, чтобы определенные входные сигналы вызывали согласованные с ними выходные сигналы. Другими словами, при предъявлении достаточно близких входных векторов сеть должна выдавать достаточно близкие выходные вектора. Таким образом, процесс самообучения выявляет статистические свойства обучающего множества и группирует сходные входные вектора в классы. Предъявление вектора из данного класса дает определенный выходной вектор, характерный для данного класса.
Характерной чертой процесса самообучения является то, что вид откликов сети на каждый класс входных образов заранее не известен и представляет собой произвольное сочетание возбуждений нейронов выходного слоя, обусловленное случайным распределением начальных значений весов на стадии инициализации и структурой обучающей выборки. Определение топологии классов в картине выходных реакций осуществляется путем тестирования уже обученной сети. Для приведения откликов обученной сети к удобному представлению, сеть обычно дополняют одним выходным слоем, который обучают классическим методом «с учителем». При этом выходные вектора, образованные на стадии самообучения трансформируются в понятную, обусловленную учителем форму.
Детерминированные и стохастические методы обучения. Используя другой принцип классификации, все существующие методы обучения можно разделить на два класса: детерминированные и стохастические.
Детерминированные методы обучения шаг за шагом осуществляют процедуру коррекции весов сети, основанную на использовании их текущих значений, величин входных сигналов, а также фактических и желаемых выходных сигналов. Преимущество детерминированных методов обучения заключается в высокой скорости обучения. Недостаток - возможность нахождения только локальных минимумов функции ошибки. При попадании процесса обучения в локальный минимум сеть стабилизируется в нем, не имея возможности самостоятельно из него выйти, чтобы достичь глобального минимума.
Стохастические методы обучения выполняют псевдослучайные изменения весов, сохраняя те изменения, которые ведут к улучшениям. Несмотря на то, что в общем случае стохастическое обучение также сводится к многоэкстремальной оптимизации, его преимущество состоит в возможности выхода из тупиков локальных экстремумов, путем случайного изменения искомых параметров сети (весов связей) в заданном диапазоне. Такую процедуру называют «выбиванием» сети из локального экстремума. Существенный недостаток стохастического обучения состоит в очень низкой скорости, что делает его непригодным для обучения сетей большой размерности.
Правила обучения
Известны четыре основных типа правил обучения (самообучения):
коррекция по ошибке;
стохастическое обучение;
правило Хебба;
метод соревнований (Кохонена).
Первые два типа правил применяются в алгоритмах обучения с учителем, а вторые два - при самообучении.
Правило коррекции по ошибке. Для каждого входного сигнала обучающей выборки учителем задается правильный (целевой, терминальный, желаемый) выходной сигнал ZT. После подачи входного сигнала сеть выдает реальный выходной сигнал ZA, который может совпадать или не совпадать с целевым. Сигнал разности или ошибки (ZT-ZA) используется для модификации весов с целью уменьшения этой ошибки. Известны различные модификации этого правила, на основе которых конструируются градиентные алгоритмы обучения. Все градиентные алгоритмы обучения сетей основаны на вычислении частных производных функций ошибки по параметрам сети (градиентный спуск по поверхности ошибки).
Стохастическое обучение. Целью стохастического обучения является такая подстройка весов связей, при которой состояния нейронов удовлетворяют желаемому распределению вероятностей. Стохастическое обучение может рассматриваться как специальный случай коррекции по ошибке.
К стохастическим алгоритмам обучения относятся: поиск в случайном направлении, имитация отжига (машина Больцмана и машина Коши), методы генетической эволюции.
При поиске в случайном направлении полученный на выходе ИНС вектор Zа сравнивается покомпонентно с желаемым выходным вектором сети ZT. При однократном предъявлении образца (размер обучающей выборки L= 1) Сравнение обычно осуществляется по формуле

где zAi - фактический выходной сигнал нейрона i;
zTi - желаемый выходной сигнал нейрона i;
S - целевая функция.
Цель обучения - минимизация целевой функции S. Процедура коррекции весов некоторого нейрона сводится к случайному выбору весового коэффициента этого нейрона и случайному его изменению. Если коррекция помогает (уменьшает S), то она сохраняется, в противном случае происходит возврат к прежнему значению весового коэффициента. Итерации повторяются до тех пор, пока сеть не будет обучена в достаточной степени.
Имитация отжига (машина Больцмана и машина Коши). Отличие этого алгоритма от предыдущего заключается в возможности постепенного уменьшения случайной коррекции весовых коэффициентов, что позволяет выйти сети из тупиков локальных экстремумов и достичь глобального экстремума целевой функции. Этот процесс напоминает отжиг металла, поэтому для его описания и применяется термин «имитация отжига».
Цель обучения, по-прежнему, - минимизация целевой функции S. Процедура коррекции весов некоторого нейрона сводится к случайному выбору весового коэффициента этого нейрона и случайному его изменению. Если коррекция помогает (уменьшает 5), то она сохраняется, в противном случае вероятность сохранения изменения веса вычисляется в соответствии с распределением Больцмана

где P(w) - вероятность изменения веса w в целевой функции S;
k- константа, аналогичная константе Больцмана (выбирается в зависимости от задачи);
Т- искусственная температура.
Случайное изменение веса и вычисление вероятности P(w) повторяют для каждого веса сети, постепенно уменьшая температуру Т, пока не будет достигнуто допустимо низкое значение целевой функции S. Потом предъявляется другой входной вектор из обучающей выборки и процесс обучения повторяется. Обучение последовательно повторяется для всех векторов обучающей выборки, пока целевая функция S не станет допустимой для всех из них.
ИНС, использующую имитацию отжига на основе распределения Больцмана, называют машиной Больцмана.
Чтобы достигнуть сходимости ИНС типа машины Больцмана к глобальному минимуму требуется очень медленная скорость «охлаждения» - уменьшения искусственной температуры Т, что приводит соответственно к длительному процессу обучения. Для ускорения обучения вместо распределения Больцмана часто используют распределение Коши, имеющее более высокую скорость «охлаждения»:

ИНС, использующую имитацию отжига на основе распределения Коши, называют машиной Коши.
Для вычисления вероятности изменения весовых коэффициентов P(w), независимо от вида распределения, используется метод Монте-Карло. В соответствии с этим методом распределения Больцмана часто используют распределение Коши, имеющее более высокую скорость «охлаждения»: генерируется случайное равномерно распределенное в диапазоне (0,1) число R и сравнивается с величиной P(w). Если P(w)>R, то изменение сохраняется, в противном случае величина веса возвращается к предыдущему значению.
Обучение нейронных сетей методами генетического поиска. При использовании генетических алгоритмов параметры ИНС фиксированной архитектуры - синаптические веса (W) и смещения (В) рассматриваются в виде вектора H=(W, В), который трактуется как хромосома. Возможны и другие более сложные способы кодирования информации.
В отличие от большинства других алгоритмов обучения, для работы генетического алгоритма требуется не один набор начальных значений параметров, а несколько наборов, которые составят популяцию хромосом. Популяция затем обрабатывается с помощью генетических операторов. Получившиеся новые особи оцениваются в соответствии с заданной целевой функцией и помещаются в популяцию. В результате на каждой стадии эволюции получаются популяции со все более совершенными индивидами.
Процесс обучения ИНС рассматривается как адаптивный процесс, связанный с минимизацией целевой функции

где zAi - фактический выходной сигнал нейрона i;
zTi - желаемый выходной сигнал нейрона i.
8699545085Структура процесса эволюционной адаптации ИНС показана на рис. слева.
После определения принципов кодирования и декодирования хромосом определяют перечень необходимых генетических операторов и общую структуру процесса генетического поиска. Для разных задач и типов ИНС они могут быть различными. В итоге формируется ГА (генетический алгоритм) для подстройки весов и смещений ИНС
В простейшем случае ГА, имитирующий обучение ИНС, работает следующим образом.
1°. Конструирование начальной популяции.
2°. Оценка хромосом в популяции и построение целевой функции S.
3°. Выбор пар хромосом из популяции.
4°. Применение оператора селекции.
5°. Применение оператора кроссинговера.
6°. Применение оператора мутации к каждой новой хромосоме с некоторой заданной вероятностью Р.
7°. Проверка целевой функции S. Если S удовлетворительна, то переход к п. 8°, иначе - переход к п. 3°.
8°. Конец работы алгоритма.
Применение механизма случайных мутаций позволяет генетическому алгоритму избежать ловушек локальных минимумов целевой функции S.
Правило Хебба является самым старым обучающим правилом, основанным на постулате американского ученого Д. Хебба. В результате нейрофизиологических исследований ассоциативной памяти Хебб в 1949 г. выявил следующую закономерность: если нейроны с обеих сторон синапса активизируются одновременно и регулярно, то сила синаптической связи возрастает. Эта физиологическая закономерность, отражающая феномен обучения через повторение, была сформулирована Хеббом в виде формального правила обучения, которое заключается в усилении весов связей между возбужденными нейронами - источником и приемником:
(1)
где wpq(ti-1), wpq(ti)- вес связи с нейрона р слоя (s-1) на нейрон q слоя s до и после коррекции;
η - коэффициент скорости обучения;
- выходной сигнал нейрона р слоя (s-1);
- выходной сигнал нейрона q слоя s.
Известно также обратное правило Хебба (antihebbian learning):

Правило обучения Хебба является исключительно локальным, охватывающим взаимодействие только двух нейронов, находящихся с обеих сторон синапса. По этой причине оно универсально и может применяться для обучения нейрона, как без учителя, так и с учителем. В первом случае используется фактическое значение выходного сигнала нейрона . Во втором случае вместо значения используется желаемая выходная реакция .
Особенностью правила Хебба является то, что в результате его применения веса могут принимать произвольно большие значения, поскольку в каждом цикле обучения происходит суммирование текущего значения веса и его приращения. Один из способов стабилизации процесса обучения по правилу Хебба состоит в учете для уточнения веса последнего значения веса wpq(ti-1),
уменьшенного с помощью коэффициента забывания γ:
(2)
Значение коэффициента γ в этой формуле выбирается обычно из интервала (0, 1) и чаще всего составляет некоторый процент от коэффициента скорости обучения η. При больших значениях γ нейрон «забывает» значительную часть того, чему он обучился в прошлом. Рекомендуемые значения γ < 0,1, при которых нейрон сохраняет большую часть информации, накопленной в процессе обучения и получает возможность стабилизировать значения весов на определенном уровне.
Правило Хебба может применяться для нейронных сетей различных типов с разнообразными активационными функциями. При использовании линейной активационной функции и правила Хебба стабилизация значений весов нейрона вообще не наступает. Процесс становится расходящимся, и значения весов стремятся к бесконечности даже при использовании правила (2). Чтобы стабилизировать процесс для такого случая Е. Ойя предложил модифицировать правило Хебба следующим образом :

Доказано, что применение модифицированного правила (6.3) приводит к сходящемуся процессу, при котором модуль вектора весов нейрона стремится к единице.
Если в сети используется сигмоидальная активационная функция

и правило обучения Хебба, то метод обучения сети с использованием правила (1) принято называть сигнальным методом обучения Хебба. Этот метод предполагает вычисление свертки предыдущих изменений выходных значений для определения изменения весов:

Существует также дифференциальный метод обучения Хебба, который заключается в усилении весов связей между нейронами, которые увеличили свои выходные сигналы между итерациями ti-1 и ti.


Метод соревнований (Кохонена). В отличие от методов Хебба, в которых в некотором слое s могут возбуждаться одновременно множество нейронов, при обучении методом соревнований нейроны некоторого слоя s соревнуются между собой за право активизации. Это явление известно, как правило «победитель забирает все» (Winner Takes All - WTA) и также имеет нейрофизиологическую аналогию. Обучение этим методом сводится к минимизации разницы между входными сигналами данного нейрона, поступающими с выходов нейронов предыдущего слоя, и весовыми коэффициентами данного нейрона

Подстройка весов связей по вышеприведенной формуле осуществляется не для всех нейронов слоя, а только для одного «нейрона-победителя», выходной сигнал которого в слое является максимальным. В свою очередь, из формулы обучения следует, что максимальный сигнал будет иметь тот нейрон, веса связей которого максимально близки к входному образу слоя.
Метод соревнований Кохонена впоследствии получил множество различных модификаций, позволяющих для конкретных конфигураций ИНС и конкретных задач существенно улучшить качество самообучения.
Лекция 12. Применение искусственных нейронных сетей
Возникает следующий важный вопрос: как применить нейронную сеть к решению конкретной задачи? Класс задач, которые можно решить с помощью нейронной сети, определяется тем, как сеть работает и как она обучается.
Таким образом, сеть можно применять в ситуации, когда имеется определенная известная информация, и вы хотите из нее получить некоторую пока неизвестную информацию (Patterson, 1996; Fausett, 1994).
Вот некоторые важные примеры задач, в которых были успешно реализованы нейросетевые методы.
Распознавание состояния больного
Применение классических статистических методов для решения этой задачи описано еще в работах Неймана. С помощью медицинской аппаратуры можно наблюдать за различными показателями состояния здоровья человека (например, частотой пульса, содержанием различных веществ в крови, частотой дыхания). Стадии возникновения некоторой болезни может соответствовать определенная и весьма сложная (например, нелинейная и взаимозависимая) комбинация изменений наблюдаемых переменных, которая может быть обнаружена с помощью нейросетевой модели.
Прогнозирование на фондовом рынке
Колебания цен на акции и фондовых индексов - еще один пример сложного, многомерного, но в определенных ситуациях частично прогнозируемого явления. Многие финансовые аналитики используют нейронные сети для прогнозирования цен акций на основе многочисленных факторов, например, прошлого поведения цен этих и других акций в совокупности с различными другими экономическими показателями. В качестве альтернативных вариантов здесь применяются модели авторегрессии и технический анализ.
Предоставление кредита
Как правило, у банка имеется большой набор сведений о человеке, обратившемся с просьбой о предоставлении кредита. Это может быть его возраст, образование, род занятий и многие другие данные. Обучив нейронную сеть на уже имеющихся данных, аналитик определяет наиболее существенные характеристики и на их основе относит данного клиента к категории с высоким или низким кредитным риском. Заметим, что для решения подобных задач можно параллельно использовать и классические статистические методы, такие как дискриминантный анализ и деревья классификации.
Системы слежения за состоянием оборудования
Нейронные сети оказались полезны как средство контроля состояния производственного процесса и состояния оборудования. Нейронная сеть может быть обучена так, чтобы отличать шум, который издает машина при нормальной работе («ложная тревога») от того, который является предвестником неполадок. После такого обучения нейронная сеть может предупреждать инженеров об угрозе поломки до того, как она случится, и тем самым исключать неожиданные и дорогостоящие простои.
Управление работой двигателя
Нейронные сети используются для анализа сигналов от датчиков, установленных на двигателях. С помощью нейронной сети можно управлять различными параметрами работы двигателя, чтобы достичь определенной цели, например, уменьшить потребление горючего.
Сжатие информации
Проиллюстрируем применение многослойных персептронов на примере решения задачи сжатия информации для представления исходных данных в компактной и удобной форме. Результаты этапа сжатия зачастую определяют успех решения задачи распознавания в целом.
Популярный метод сжатия информации был предложен в 1987 г. G Cottrell, P. Munro, D. Zipser. Рассмотрим трехслойный персептрон, у которого число нейронов входного и выходного слоев одинаково, а число нейронов скрытого слоя значительно меньше. Предположим, что в результате обучения персептрон может воспроизводить на выходе тот же самый вектор X, который подается на входной слой. Такой персептрон автоматически осуществляет сжатие (компрессию) информации: на нейронах скрытого слоя возникает представление каждого вектора, которое значительно короче, чем длина вектора, подаваемого на вход. Предположим, что некоторый набор векторов нужно передавать по линии связи, предварительно сжимая информацию и, тем самым, уменьшая число каналов, необходимых для ее передачи. Поместим на одном конце линии входной и скрытый слои персептрона, а результат работы нейронов скрытого слоя (короткие векторы) будем передавать по линии связи. На другом конце линии поместим копию скрытого слоя и выходной слой, тогда переданный короткий вектор с нейронов скрытого слоя перейдет на нейроны выходного слоя, где и будет воспроизведен входной вектор (декомпрессия).
Обработка видеоизображений
Одной из наиболее сложных и актуальных проблем обработки видеоизображений, представленных последовательностью оцифрованных кадров, является проблема выделения и распознавания движущихся объектов в условиях действия различного рода помех и возмущений. Для этого должны быть решены задачи выделения изображений движущихся объектов на сложном зашумленном фоне, фильтрации помех, скоростной фильтрации, отделения объектов от фона, оценки скорости каждого объекта, его идентификации и сопровождения Системы обработки видеоизображений, построенные с применением нейросетевых методов, представляют собой, как правило, программно-аппаратные комплексы на персональных компьютерах, позволяющие работать с данными телевизионной системы в реальном времени (не менее 25 кадров/с, 320x200 пикселей).
Выделение изображений движущихся объектов осуществляется путем построения оценки поля скоростей с помощью многослойной локально-связной нейронной сети. Размерность сети для изображения 320x200 пикселей составляет несколько миллионов нейронов и примерно вчетверо больше синапсов.
Распознавание выделенных силуэтов производится на самоорганизующейся нейронной сети, предварительно обученной на изображениях объектов рассматриваемых классов. Обеспечивается инвариантность к произвольному движению фона, устойчивость к зашумлению до 10%. Вероятность правильного распознавания не менее 90%.
Обработка статических изображений
Не менее сложными являются задачи выделения и распознавания объектов на статическом тоновом изображении. В частности, подобные задачи возникают при автоматической обработке спутниковых изображений земной поверхности. Для их решения разработан и реализован на персональных компьютерах ряд автоматизированных систем анализа изображений земной поверхности. Системы в автоматическом режиме обеспечивает выделение на обрабатываемых изображениях объектов заданных классов: дорожной сети, кварталов с характерной застройкой, аэродромов и стоящих на них самолетов. Нейросетевые принципы, заложенные в их основу, обеспечивают инвариантность к яркостным характеристикам выделяемых и распознаваемых объектов, а также позволяют проводить обучение и адаптацию систем.
Обнаружение и классификация объектов по звуковым и гидроакустическим сигналам
Использование нейросетевых технологий для анализа акустического излучения демонстрируют системы обнаружения и распознавания летательных аппаратов по звуку, а также надводных и подводных объектов по гидроакустическим сигналам. Сигналы от объектов подвергаются предобработке и в оцифрованном виде подаются на вход предварительно обученной нейронной сети для распознавания. Исследования систем показали высокую вероятность правильного распознавания (до 90%).
Задачи комбинаторной оптимизации
Высокая степень распараллеленности обработки информации позволяет успешно применять нейросетевые технологии для решения задач комбинаторной оптимизации, к которым, в первую очередь следует отметить задачи транспортно-ориентированной оптимизации (например, задача коммивояжера и ее модификации) и задачи распределения ресурсов (задача о назначениях, задача целераспределения и другие).
Решение таких задач традиционными методами математического программирования, большинство из которых изначально ориентировано на вычислительную технику с последовательной архитектурой, сопряжено с большими временными затратами, неприемлемыми для многих приложений. При соответствующей аппаратной поддержке нейросетевые методы позволяют значительно повысить оперативность решения данного класса задач, сохраняя высокую точность результата.
Прогнозирование потребления энергии
Фирма ZSolutions разработала нейросетевую систему анализа данных об энергопотреблении, фиксирующую измерение потребляемой энергии для каждого клиента через каждые 15 минут, с учетом того, что некоторые из измерений ошибочны. Система позволяет выявлять ошибочные измерения, а также прогнозировать потребление энергии в каждый момент времени. Знание точного прогноза позволило энергетической компании использовать гибкую тарифную политику и увеличить свою прибыль.
Оценка недвижимости
Стоимость дома или квартиры зависит от большого числа факторов, таких как общая площадь, удаленность от центра, экологическая обстановка, престижность, тип дома. Так как вид этой зависимости неизвестен, то стандартные методы анализа, как правило, неэффективны. Обычно эта задача решается экспертами, работающими в агентстве по недвижимости. Недостатком такого подхода является субъективность оценщиков, а также возможные разногласия между ними. Существуют успешные примеры решения задачи объективной оценки с помощью нейронной сети. В частности, фирма Attrasoft приводит пример оценки стоимости домов в Бостоне с учетом 13 параметров.
Обнаружение фальсификаций
В США введена в действие система обнаружения мошенничеств в области здравоохранения. Подсчитано, что потери бюджета от такого рода фальсификаций составляют около 730 млн. долларов в год. Создание нейросетевой специализированной системы заняло у фирмы ITC более года и обошлось в 2,5 млн. долларов. Тестирование показало, что нейронная сеть позволяет обнаруживать 38% мошеннических случаев, в то время как существующая экспертная система - только 14%. Для настройки системы были использованы также методы нечеткой логики и генетической оптимизации.
Оценка применимости нейронной сети для решения конкретной задачи
Разумеется, вовсе не любую задачу можно решить с помощью нейронной сети. Если вы хотите определить результаты лотереи, тираж которой состоится через неделю, зная свой размер обуви, то едва ли это получится, поскольку эти показатели никак не связаны друг с другом. Многие финансовые структуры уже используют нейронные сети или экспериментируют с ними с целью прогнозирования ситуации на фондовом рынке, и похоже, что любой тренд, прогнозируемый с помощью нейронных методов, всякий раз уже бывает «дисконтирован» рынком, и поэтому (к сожалению) эту задачу вам тоже вряд ли удастся решить.
Итак, мы приходим ко второму важному условию применения нейронных сетей: вы должны знать (или хотя бы иметь серьезные подозрения), что между известными входными значениями и неизвестными выходами имеется связь. Эта связь может быть искажена шумом, но она должна существовать (так, едва ли можно ожидать, что по данным из примера с прогнозированием цен акций можно построить абсолютно точный прогноз, поскольку на цену влияют и другие факторы, не представленные во входном наборе данных, и кроме того, в задаче присутствует элемент случайности).
Как правило, нейронная сеть используется тогда, когда неизвестен точный вид связей между входами и выходами, - если бы он был известен, то связь можно было бы моделировать непосредственно. Другая существенная особенность нейронных сетей состоит в том, что зависимость между входом и выходом находится в процессе обучения сети.
Программное обеспечение для моделирования искусственных нейронных сетей
Matlab_Neural_Network    Один из лучших, математических пакетов для моделирования нейросетей. Пакет Matalb ориентирован на решение широкого круга математических задач. Содержит большое количество надстроек для расширения возможностей. Одним из таких расширений является toolbox Neural Network позволяющий работать с нейронными сетями практически любой структуры. Пакет работает под управлением ОС Windows. Более подробное описание можно получить на сайте www.matlab.ru
Statistica_Neural_Networks    Пакет нейросетевого анализа для конструирования и применения нейронных сетей. Второй по распространенности на постсоветском пространстве после Matlabа нейропакет. Производитель: StatSoft
ModelQuest    Интегральная среда для прогнозирования, принятия решений и управления. В основе лежит концепция «статистических сетей» (Statistical Networks) как сплава нейронных сетей и статистических методов обработки. Программа работает под управлением ОС Windows. Производитель: AbTech (Шалетсвилл, шт. Вайоминг, США); http://www.abtech. com/ MQI.HTM
Neuro_Office    Пакет для проектирования интеллектуальных программных модулей на основе нейронных сетей с ядерной организацией. Программа работает под управлением ОС Windows. Производитель: АОЗТ «Альфа Систем» (ЛЭТИ, С.- Петербург); dorv@actor.ru
NeuroPro    Нейропакет для извлечения знаний из таблиц данных. Один из первых отечественных симуляторов нейронных сетей Программа работает под управлением ОС Windows. Производитель: Институт вычислительного моделирования СО РАН, Красноярск. Россия; Царегородцев В. Г. tsar@cc.krascience. rssi.ru
Excel_Neural_Package    Нейропакет для статистического прогнозирования анализа многомерных данных ООО «НейрОК» (МГУ, Москва, Россия): www.neurok.ru
Глаз    Распознавание визуальных образов. Используется для обработки аэрокосмической информации. Производитель: НейроКомп (ВЦ СО РАН, Красноярск, Россия); amse@cc. kras - cience. rssi.ru
Клаб    Среда для решения задач классификации, в том числе в медицинской, психологической и технической диагностике. Производитель: НейроКомп (ВЦ СО РАН, Красноярск, Россия); amse@cc.krascience. rssi.ru
MultiNeuron    Программный нейроимитатор для решения задач из различных предметных областей. Может работать под DOS и Windows. Производитель: НейроКомп (ВЦ СО РАН, Красноярск, Россия); arnse@cc.krasci-ence. rssi.ru
«Нейроимитатор»    Пакет программ моделирования биологических нейронных сетей. Производитель: АО «Нейрома-РД» (Москва, Россия); http:// www.nbdatyner. com/nbd 
NeuralMake    Пакет для разработки прикладных нейронных сетей. Производитель: СНИЦ Нейросистемы АН Татарстана
Neuroline    Инструментальная сред на основе нейронных сетей. Производитель: Аргусофт (Москва, Россия)
SNNS (Stuttgart Neural Network Simulator) Симулятор нейронных сетей, первоначально разработанный в университете Штутгарта. В нем реализована поддержка классических нейросетевых парадигм и алгоритмов обучения. Его функциональность также может быть расширена за счет пользовательских модулей. Кроме того, для изучения и модификации доступны исходные коды этой программы.
NeuroSolutions. Очень мощный симулятор нейронных сетей. Поддерживает большое количество механизмов ввода информации, обработки данных, является хорошим конструктором сетей, стабилен, поддерживает расширение за счет пользовательских модулей. К недостаткам можно отнести высокую стоимость, отсутствие русскоязычного интерфейса и справки, что усложняет освоение этого продукта (http://www.neurosolutions.com).
TRAJAN – программный продукт для моделирования нейронных сетей от компании Trajan Software Co. (Великобритания).

Приложенные файлы

  • docx 8896257
    Размер файла: 3 MB Загрузок: 1

Добавить комментарий