Основные понятия и определения

ВВЕДЕНИЕ

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

Идея создания искусственного подобия человеческого разума для решения сложных задач и моделирования мыслительной способности человека волновала человечество с древнейших времен. Впервые ее выразил Р. Луллий (ок.1235 – ок.1315), который еще в XIV в. пытался создать машину для решения различных задач на основе всеобщей классификации понятий.

В XVIII в. Г. Лейбниц (1646 – 1716) и Р. Декарт (1596 – 1650) независимо друг от друга развили эту идею, предложив универсальные языки классификации всех наук. Эти работы можно считать первыми теоретическими разработками в области искусственного интеллекта.

Окончательное рождение искусственного интеллекта как научного направления произошло только после создания ЭВМ в 40-х годах XX века. В это же время Норберт Винер создал свои основополагающие работы по новой науке – кибернетике.

Основные понятия и определения

Понятие искусственного интеллекта

Существует множество определений искусственного интеллекта (ИИ). Приведем примеры некоторых высказываний, раскрывающих содержание этого термина. Тест Тьюринга (Тьюринг А. Может ли машина мыслить? 1960 г.) О наличии интеллекта можно судить по результатам игры в имитацию: испытатель задает вопрос двум системам А и В, одна…

Международный Комитет по ИИ (1969 г.)

ИИ – это область, покрываемая названиями секций Международного конгресса по ИИ. В 1972 г. участниками Международного семинара по робототехнике был составлен список проблем ИИ:

1. Шахматные программы;

2. Машинное творчество в области музыки, поэзии, живописи;

3. Программы, выдерживающие тест Тьюринга;

4. Машинное доказательство теорем;

5. Программы индуктивного вывода;

6. Вопросно-ответные системы (в том числе системы автоматического реферирования);

7. Автоматический перевод;

8. Распознавание и синтез речи;

9. Автоматическая проверка правильности программ;

10. Автоматическое вождение автомобилей;

11. Роботы - сборщики, роботы - строители;

12. Робот - планетоход для автономной работы в новых условиях.

Грегори Р. Л. (Глаз и мозг, 1971 г.)

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

Бенерджи Р. (Теория решения задач, 1972 г.)

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

Слэйгл Дж. (Искусственный интеллект, 1973 г.)

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

«Интеллект» – ум, разум, способность к умственной деятельности.

Мики Д. (Формирование и выполнение планов вычислительной машиной. 1975 г.)

Программа для ЭВМ является интеллектуальной, если в ней содержатся два процесса: построение моделей и формирование планов, а также положительные ответы на следующие вопросы:

1. Строит ли программа модель проблемной ситуации? Эта модель должна обладать предсказательной силой – она должна давать возможность вычислять соответствующие действия.

2. Использует ли программа эту модель для формирования планов действия, которые будут испытываться в проблемной ситуации?

3. Включают ли в себя эти планы направленное опробование проблемной ситуации в виде движения по условным ветвям плана?

4. Может ли программа изменять план, если испытания приводят к состоянию, которое не было предсказано программой?

5. Может ли программа использовать знание удач и неудач последних планов для пересмотра и индуктивного расширения модели?

Обзорный доклад о проблеме ИИ (АН СССР Рабочая группа под председательством академика Г. С. Поспелова 1982 г.)

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

Левин Р. и др. (Практическое введение в технологию ИИ и ЭС, 1990 г.)

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

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

2.Выделить основные части этого процесса;

3.Разработать программные средства, воспроизводящие их на компьютере.

Лорьер Ж.-Л. (Системы искусственного интеллекта, 1991 г.)

«Всякая задача, для которой неизвестен алгоритм решения, относится к ИИ».

Попов Э.В., Фирдман Г.Р. (Алгоритмические основы интеллектуальных роботов и искусственный интеллект, 1992 г.)

Макарова Н.В. («Информатика», 2001 г.) Искусственный интеллект – это одно из направлений информатики, цель которого –… 1.2. История развития искусственного интеллекта за рубежом

Ведутся разработки по созданию интеллектуальных роботов, новых аппаратных решений и архитектур, направленных на обработку символьных и логических данных. Создаются Пролог- и Лисп-машины, компьютеры V и VI поколений. Последние разработки посвящены компьютерам баз данных и параллельным компьютерам. Ведущими разработчиками в области искусственного интеллекта считаются США и Япония.

1.3. История развития искусственного интеллекта в России

В 1954 г. в МГУ под руководством профессора А.А. Ляпунова (1911– 1973) начал свою работу научный семинар «Автоматы и мышление». В этом семинаре принимали участие крупнейшие физиологи, лингвисты, психологи, математики.

Принято считать, что именно в это время родился искусственный интеллект в России. Как и за рубежом, выделились направления нейрокибернетики и кибернетики «черного ящика». В 1954 – 1964 гг. исследуются и создаются отдельные программы для поиска решения логических задач.

В Ленинграде в ЛОМИ (Ленинградское отделение математического института им. Стеклова) создается программа, автоматически доказывающая теоремы (АЛПЕВ ЛОМИ). Она основана на оригинальном обратном выводе С. Ю. Маслова, аналогичном методу резолюций Робинсона.

В 60-е гг. создается алгоритм «Кора» М. Бонгарда, моделирующий деятельность человеческого мозга при распознавании образов.

Большой вклад в становление российской школы ИИ внесли выдающиеся ученые Цетлин М. Л., Пушкин В. Н., Гаврилов М. А., чьи ученики явились пионерами этой науки в России (например, знаменитая Гавриловская школа).

В 1965 – 1980 гг. получает развитие новая наука – ситуационное управление (соответствует представлению знаний в западной терминологии), разрабатываются специальные модели представления ситуаций – представление знаний. Основателем этой научной школы стал профессор Поспелов Д. А.

Огромную роль в признании искусственного интеллекта в нашей стране сыграли академики Берг А. И. и Поспелов Г. С.

В 1974 г. при Комитете по системному анализу при президиуме АН СССР был создан Научный совет по проблеме «Искусственный интеллект», который возглавил Г. С. Поспелов, его заместителями были избраны Д. А. Поспелов и Л. И. Микулич. По инициативе Совета были созданы пять комплексных научных проектов, которые были возглавлены ведущими специалистами в этой области.

Проекты объединяли исследования в различных коллективах страны: «Диалог» – работы по пониманию естественного языка (руководители Ершов А. П., Нариньяни А. С.); «Ситуация» – ситуационное управление (Поспелов Д. А.); «Банк» – банки данных (Кузин Л. Т.); «Конструктор» – поисковое конструирование (Половинкин А. И.); «Интеллект робота» – создание интеллектуальных роботов (Охоцимский Д. Е.).

В 1980 – 1990 гг. проводятся активные исследования в области представления знаний, разрабатываются языки представления знаний, экспертные системы (более 300). В МГУ создается язык РЕФАЛ.

В 1988 г. создается АИИ – Ассоциация искусственного интеллекта. Ее членами являются более 300 исследователей. Президентом Ассоциации избирается Поспелов Д. А. Крупнейшие центры – в Москве, Петербурге, Новосибирске, Переславле-Залесском и др. В научный совет Ассоциации входят ведущие исследователи в области искусственного интеллекта: Гладун В. П., Городецкий В. И., Осипов Г. С., Попов Э. В., Стефанюк В. Л., Хорошевский В. Ф., Финн В. К., Цейтин Г. С., Эрлих А. С. и др. В рамках Ассоциации проводятся большое количество исследований, организуются школы для молодых специалистов, семинары, симпозиумы, раз в два года собираются объединенные конференции, издается научный журнал.

Уровень теоретических исследований по искусственному интеллекту в России ничуть не ниже мирового. К сожалению, начиная с 80-х гг. на прикладных работах начинает сказываться постепенное отставание в технологии. На данный момент отставание в области разработки промышленных интеллектуальных систем составляет порядка 5-7 лет.

Цели и задачи искусственного интеллекта

1. Обработка зрительных сцен: - обработка изображения; - распознавание и понимание образов;

Основные направления исследований по ИИ

    А В С D

Истоки формальных рассуждений

Как известно, мозг человека состоит из двух полушарий, каждое из которых по-своему преобразует информацию. Весь окружающий мир делится на два пространства «Я» и «не –Я». Между этими… Функции анализа, декомпозиции целого на части – прерогатива левого полушария. Это расчленение происходит благодаря…

Типы мышления

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

Контрольные вопросы и упражнения

1. Какие типы мышления Вы знаете?

2. За что отвечает правополушарное мышление?

3. За что отвечает левополушарное мышление?

4. Что такое оппозиционные шкалы? Приведите примеры оппозиционных шкал.

5. В чем суть трансакционного анализа?

3.Формальные системы

В формальной логике разрабатываются методы правильных рассуждений, представляющих собой цепь умозаключений в логически последовательной форме. Рассуждения в ней изучаются с точки зрения формы, а не смысла, и с этой целью в обычных рассуждениях выделяются определенные элементы, которые могут замещаться в них произвольным образом какими-то другими элементами. Например, в хорошо известном силлогизме (обычно приписываемом Аристотелю, но в действительности принадлежащему Г. Оккаму (1349 г.)) «Люди – смертны. Сократ – человек, следовательно, Сократ – смертен» в обоих случаях вхождения слов «человек (люди)», «смертен (смертны)», «Сократ» могут быть заменены любыми другими словами, и при этом само рассуждение останется формально допустимым. Таким образом, уже простая замена таких слов в рассуждениях символьными обозначениями позволяет строить обобщенные суждения на основе подобных рассуждений. Так, в приведенном примере абстрактная модель этого рассуждения принимает следующий вид: «Если все x есть суть y и если z есть x, то z есть y».

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

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

Отметим, что в обычном языке союз «или» может принимать различные значения. Иногда он означает «или то или другое, или то и другое вместе (или – включительное), а иногда «одно из двух» (или – исключительное). Аналогично глагол «есть, является» означает иногда включение, иногда равенство, а иногда принадлежность. В связи с этим возникает необходимость использовать различные символы для обозначения и отражения различных значений оттенков подобных слов.

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

Став составной частью философии и имея в числе своих создателей таких великих ученых, как Аристотель, Авиценна, Абеляр, Кант, Лейбниц, формальная логика с течением времени приобретает все более математический характер. Благодаря результатам, которые были получены в этой области Д. Венном, Г. Булем, А. Морганом и затем стали использоваться в других научных дисциплинах, начинает осуществляться мечта Лейбница о разработке и практической реализации универсальной символики.

Однако лишь начиная с трудов Г. Фрегге, Г. Пеано и, наконец, с монументального труда Б.Рассела и А. Уайтхэда «Основания математики» (1913 г.), формальная логика полностью отделилась от разговорного языка и выделилась в самостоятельную дисциплину, базирующуюся на собственной знаковой системе.

Понятие формальной системы

В формальной системе (ФС), оперирующей теми или иными символами, эти символы воспринимаются просто как элементы, с которыми обращаются согласно… Формальные системы – это аксиоматические системы, т.е. системы с наличием… Формальную систему называют также аксиоматикой, или формальной теорией, еще проще – множеством формул. Формальная…

Разрешимость формальной системы

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

Интерпретация формальной системы

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

Доказательство и истинность

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

Возможны формальные системы, в которых

· существуют формулы m, такие, что ни m ни Ø m не являются доказуемыми (теорема Геделя);

· во всякой их интерпретации найдутся выражения, истинные, но недоказуемые (теорема Тарского);

· не существует алгоритма, чтобы отличать теоремы от не-теорем (теорема Черча).

Контрольные вопросы и упражнения

1. Дайте определение формальной системы.

2. Сформулируйте основные теоремы о формальных системах.

3. Может ли выражение baab • abba быть допустимой формулой в формальной системе JP?

 

 

4. Силлогистика Аристотеля

Основные принципы силлогистики

В «Категориях» излагается учение о высших родах всех вещей. Высший род – это класс предметов с наиболее общими признаками. Такой класс отображается… В книге «Об истолковании» суждение рассматривается как нечто целое. Суждение –… В книгах «Первая Аналитика»и«Вторая Аналитика» излагается теория силлогизмов. Силлогизм – это умозаключение, в котором…

Базовые высказывания силлогистики

Здесь S ­– класс сущностей, о котором что-либо утверждается (субъект), P – класс сущностей, определяющий, что именно говорится о субъекте (свойство… С использованием базовых высказываний законы силлогистики могут быть… 1) закон тождества – Аss ;

Решение силлогизмов

                 

Правильные силлогизмы

Наименование фигуры	Правильные силлогизмы
Первая	AAA, EAE, EIO, AII, AAI, EAO
Вторая	EAE, AEE, EIO, AOO, EAO, AEO
Третья	AAI, IAI, AII, EAO, OAO, EIO
Четвертая	AAI, AEE, IAI, EAO, EIO, AEO

Алгоритм решения силлогизмов

1. Формализация понятий.

1.1. Выделение универсума (наиболее общего класса для всех посылок).

1.2. Выделение классов.

2. Приведение посылок к нормальной форме.

3. Выбор фигуры силлогистики.

4. Выбор правильного силлогизма по видам посылок.

5. Словесная интерпретация.

Расширенная силлогистика

Для перехода к негативным утверждениям необходимо ввести отрицание класса сущностей. Пусть выделен некоторый класс сущностей W. Вводится новый класс… Расширенная силлогистика может быть сведена к первоначальной при помощи… Другое расширение силлогистики – увеличение числа посылок, т.е. переход к выводам ранга 3 (соритам). Для получения…

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

   

Контрольные вопросы и упражнения

1. Сформулируйте основные принципы силлогистики Аристотеля.

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

3. Как решаются силлогизмы?

4. Придумайте и решите силлогизм.

5. Как решаются сориты?

6. В чем заключается расширение силлогистики?

7. Проверьте правильность силлогизма ААЕ для первой фигуры.

8. Даны две посылки: «Свиньи не летают» и «Свиньи прожорливы». Построить и решить силлогизм.

9. Придумайте сорит, состоящий из четырех посылок, и решите его.

10. Дайте определение силлогистики Аристотеля как формальной системы.

 

5. Исчисление высказываний

Синтаксис исчисления высказываний

Синтаксис исчисления высказываний составляют: 1. Словарь (пропозициональный логический словарь) – бесконечное счетное… 2. Правила построения синтаксически правильных выражений: а) всякое высказывание есть формула; б) всякая комбинация…

Классы формул исчисления высказываний

Формула семантически выполнима (выполнима), если ее можно интерпретировать со значением Т. Например, ( рÙq) – выполнима, т.к. принимает значение Т, если p и q принимают значение Т.

Формула, не являющаяся выполнимой, называется невыполнимой.

Формула общезначима, если она истинна (принимает значение Т) независимо от истинностных значений, приписанных составляющим ее высказываниям. Общезначимые формулы часто называются тавтологиями.

Формула, содержащая К высказываний, допускает 2^к интерпретаций. Самый простой способ определения класса формулы – метод полного перебора, основанный на проверке истинности формулы на всех 2^к интерпретациях. Это можно сделать, используя таблицы истинности. Однако существуют другие, более эффективные методы, позволяющие избежать полного перебора.

Понятие семантического дерева

1) каждая дуга помечена негативной или позитивной литерой из множества Р; 2) литеры, которыми помечены две дуги, выходящие из одного узла, должны быть… 3) никакая ветвь (путь) на дереве не содержит более одного вхождения каждой литеры;

Алгоритм Куайна

Пример.Проверить общезначимость формулы(((pÙq)Ér)Ù (pÉq))É(pÉr). 1. Упорядочим множества элементов высказываний: {p, q, r}. Это эквивалентно… 2. Рассмотрим те интерпретации, при которых р есть Т. При этом исходная формула сводится к формуле ((qÉr)…

Алгоритм редукции

Пример.Проверить общезначимость формулы ((p Ùq) Ér) É(pÉ(qÉr)). Предположим, при некоторой интерпретации формула принимает значение F. По… Аналогично для следующего шага: I(p)=T, а I(qÉr)=F.

Алгебраический подход к определению класса формул

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

Для формул исчисления высказываний справедливы следующие законы преобразования:

1. Законы дистрибутивности

((xÙy)Úz)»((xÚz)Ù(yÚz)

((xÚy)Ùz)»((xÙz)Ú(yÙz)

2. Закон исключения третьего

(xÚ┐ x)»T, (xÙ┐ x)»F

3. Законы де Моргана

┐(xÙy)»( ┐xÚ┐y)

┐(xÚy)»( ┐xÙ┐y)

4. Преобразование импликации

xÉy»(┐xÚy)

5. Двойное отрицание

┐┐x»X

Нормальные формы и алгоритм нормализации

Конъюнктивная нормальная форма – это конъюнкция конечного числа дизъюнкций, т. е. формула вида (L1Ù¼ÙLn)= ÙLi , где Li –… Дизъюнктивная нормальная форма – это дизъюнкция конечного числа конъюнкций, т.… В исчислении высказываний доказана теорема о том, что любая формула имеет логически эквивалентную ей нормальную форму.…

Алгоритм Куайна для ДНФ

Пусть р – элементарное высказывание, а S – приведенная ДНФ, которая может быть представлена в виде: S= SpÈ Sù p È (Sр\ S||p), где Sp – дизъюнкты, содержащие высказывание р;

Принцип резолюций

Множество дизъюнктов S не выполнимо тогда и только тогда, когда логическое следствие из него есть пустой дизъюнкт, т. е. дизъюнкт, всегда… Для порождения логических следствий используется следующая схема рассуждений.… То есть, {АÚ Х, ВÚùХ} ├ АÚВ, или {ùХ ÉА, Х ÉВ}├…

Алгоритм доказательства невыполнимости логической формулы

2. Строится резольвента r. 3. Заменяется S на SÈ{r}. 4. Процесс повторяется до порождения пустого дизъюнкта, это означает, что формула невыполнима.

Хорновские дизъюнкты

Хорновский дизъюнкт – это дизъюнкт, который содержит не более одной позитивной литеры. Например, {ù p, ù q, ù r, s} –… Хорновский дизъюнкт называется точным, если он содержит позитивную литеру,… Точный дизъюнкт выражает некоторое правило: негативные литеры соответствуют гипотезам, позитивные литеры –…

Применение исчисления высказываний

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

Пример базы знаний на основе логических высказываний

Пусть необходимо формализовать знания о различных животных. База знаний на основе исчисления высказываний должна состоять из фактов – единичных высказываний и формул исчисления высказываний, которые выражают логические связи между фактами (табл. 7).

 

Таблица 7

База знаний на основе исчисления высказываний

Применение исчисления высказываний в конструировании релейно-контактных схем

  Последовательное соединение «контактов» соответствует логической операции «и», а параллельное соединение – «или»:

Исчисление предикатов

Чтобы выразить этот силлогизм в формализованном виде, необходимо использовать более мощную формальную систему, чем исчисление высказываний. В данном… ("х) (человек (х) É смертен (х)), где х является квантифицированной или связанной переменной, а выражения «человек» и «смертен» являются предикатами.…

Определение исчисления предикатов первого порядка

Предикат на множестве M есть логическая функция, определенная на M, при фиксировании аргументов которой она превращается в высказывание со… В общем случае через P(x1, x2, …, xn) обозначим n-местный предикат, обладающий… Важную роль в исчислении предикатов играют кванторы существования ($) и всеобщности ("). Для предиката Р(х)…

Операции над предикатами

1. Пусть заданы два предиката P(x), Q(x) (xÎ M). Конъюнкцией этих предикатов называется предикат, который принимает значение «истина» только для тех значений x, для которых каждый из предикатов P и Q принимает значение «истина»:

 

J_PÙQ = J_P Ç J_Q

 

2. Пусть заданы два предиката P(x), Q(x) (xÎ M). Дизъюнкцией этих предикатов называется предикат, который принимает значение «ложь» только для тех значений x, для которых каждый из предикатов P и Q принимают значение «ложь»:

J_PÚQ = J_P È J_Q

3. Пусть заданы два предиката P(x), Q(x) (xÎ M). Отрицанием одноместного предиката называется предикат ¬Р(x), который принимает значение «истина» для всех значений x, для которых Р(x) ложно:

J_¬P = M - J_P

 

4. Пусть заданы два предиката P(x), Q(x) (xÎ M).

Импликацией Р(x) в Q(x) называется предикат, для всех x которого Р(x) истинно, а Q(x) ложно:

J_P®Q = J_P \ (J_Р & J_Q)

5. Пусть заданы два предиката P(x), Q(x) (xÎ M). Эквивалентностью Р(x) и Q(x) называется предикат, для всех x которого истинна конъюнкция предикатов Р(х) и Q(x) или истинна конъюнкция предикатов ¬Р(х) и ¬Q(x):

J_P«Q = (J_Р & J_Q) È ( J_¬Р & J_¬Q)

Общезначимость и выполнимость формул исчисления предикатов

Формула исчисления предикатов называется выполнимой в области М, если существуют значения xÎМ, при которых формула принимает значение… Формула исчисления предикатов называется выполнимой, если существует область,… Формула исчисления предикатов называется тождественно истинной в области М, если она принимает истинные значения для…

Исчисление предикатов как формальная система

1. Алфавит: а) счетное множество предметных переменных x1, x2, …, xn …; б) конечное (может быть и пустое) или счетное множество предметных констант а1, а2, …;

Пренексные нормальные формы исчисления предикатов

Говорят, что формула F исчисления предикатов находится в ПНФ тогда и только тогда, когда ее можно представить в форме z1х1z2х2 … zrхr М, где каждый… Например, формула F1= $x"y(Q(x,y)ÚØP(f(x))®R(x,g(y)))… Существует простой алгоритм, преобразующий произвольную заданную формулу в равносильную ей формулу, имеющую пренексный…

Сколемовские стандартные формы исчисления предикатов

Формула F называется "-формулой, если она представлена в ПНФ, причем кванторная часть состоит только из кванторов всеобщности, т. е. F = "x1"x2 …"xr M, где М – бескванторная формула. Таким образом, возникает задача устранения кванторов существования в формулах, представленных в ПНФ. Это можно сделать…

Процедура вывода Эрбрана

Пусть Hо – множество констант, появляющихся в множестве дизъюнктов S. Если в S нет констант, то в Hо включается некоторая константа, например Hо =… Тогда множество H = H¥ называется универсумом Эрбрана для S, а Hi – его… Пример. Пусть S = { P(x, a, g(y)) Ú ¬Q(х)), ¬P(f(x), a, y) Ú Q(a)}. Тогда

Принцип резолюции для логики предикатов

C1: P(x) ÚØR(x), C2: ØP(g(x)) ÚQ(y), то резольвента может быть получена только после применения к C1 подстановки g(x) вместо x. После такой подстановки…

Контрольные вопросы и упражнения

1. Определите исчисление предикатов как формальную систему.

2. Сформулируйте основные теоремы исчисления предикатов.

3. Что такое пренексная нормальная форма и сколемовская стандартная форма в исчислении предикатов?

4. Какие процедуры вывода существуют в исчислении предикатов?

5. В чем заключается процедура вывода Эрбрана?

6. Сформулируйте принцип резолюций в исчислении предикатов.

7. Привести формулу к ПНФ F = "x(P(x)«$xR(x))®"yQ(y).

8. Привести формулу упражнения 7 к ССФ.

9. Найти фактор дизъюнкта С = P(x)ÚP(g(y)) ÚØR(x).

 

 

Индуктивные рассуждения

По определению Брокгауза: «Индукция – это такой процесс мышления, посредством которого мы, опираясь мысленно на принцип единообразия природы,… Индуктивное мышление обычно противопоставляется дедуктивному мышлению, при… Так, известный математик и теоретик науки Пойа в своей книге «Математика и правдоподобные рассуждения» приводит…

Схема индуктивных рассуждений

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

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

Ключевой вопрос индуктивных рассуждений – сколько должно быть рассмотрено конкретных элементов класса, чтобы индуктивный шаг стал оправданным.

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

7.2. Индукция Милля

Одним из основоположников индуктивных рассуждений является Джон Стюарт Милль. Джон Стюарт Милль (1806 – 1873 гг.) – английский философ, экономист, общественный деятель. В сочинении «Система логики силлогической и индуктивной» (1843 г.) Милль рассматривает индуктивную логику как общую методологию наук. Главный интерес Милля – исследовать индукцию, которая, по его мнению, заключается в том, что мы переходим от знания известного к знанию неизвестному, а не от прошлого – к будущим событиям.

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

Эти отношения могут быть как наблюдаемыми непосредственно, с помощью наших органов чувств (отношение «субъект – действие», «быть раньше»), так и достраиваемыми на основании некоторой логики знаний (отношения типа «причина – следствие», «цель – средство»).

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

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

Были установлены три основные принципа, основанные на идеях выделения сходства и различия в наблюдаемых ситуациях внешнего мира.

Принцип единственного различия

Схема рассуждений: a, b, c ® d n экспериментов … – положительные примеры для явления d.

Принцип единственного сходства

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

Схема рассуждений:

a, b, c ® d

n экспериментов …

a, b, c ® d

Удаляется фактор с:

а, b ® d

m экспериментов …

а, b ® d

Удаляется фактор b:

а ® d

р экспериментов …

а ® d

Если число экспериментов достаточно для выявления устойчивости, то можно сказать, что а – причина d, т. е. a и d связаны причинно-следственными отношениями.

Принцип единственного остатка

«Если вычесть из какого-либо явления ту часть его, которая согласно прежним исследованиям оказывается следствием известных причин, то остаток явления есть следствие остальных причин».

Схема рассуждений:

a, b, c ® d, e

n экспериментов …

a, b, c ® d, e

Удаляется фактор а:

b, c ® e

m экспериментов …

b, c ® e

Если число экспериментов достаточно для выявления устойчивости, то можно сказать, что а – причина d, т. е. a и d связаны причинно-следственными отношениями.

Особенности индуктивных схем рассуждений

Например, нужно выявить причины положительных эмоций при наблюдении некоторых объектов. Пусть некто наблюдает птичек, при этом часть объектов…      

Метод пятизначной логики

Этот метод является одной из разновидностей ДСМ-метода и применяет для оценки истинности высказываний расширенную границу шкалирования.

Традиционно в ДСМ–логике используется четыре типа истинностных значений для оценки: +1 – истина, -1 – ложь, 0 – противоречие, t – неопределенность.

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

Алгоритм древ

В основе метода используется дерево решений – один из способов разбиения множества данных на классы или категории. Решающее дерево классифицирует… Идея алгоритма состоит в следующем: ставится задача построения обобщенного… На первом этапе работы алгоритма делается попытка сформировать обобщенное конъюнктивное понятие на основе поиска…

Алгоритм АМХ (алгоритм, основанный на метрике Хемминга)

Дерево решений – это алгоритм, представленный в специальной форме. Алгоритм АМХ – это алгоритм, который строит бинарное дерево решений на основе поиска существенного (разделяющего) признака. Каждой вершине приписывается вопрос «Обладает ли пример данным значением признака?», а дуги взвешиваются ответами «Да» и «Нет». Конечные вершины дерева будут помечены утверждениями, соответствующим решениям.

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

Рассмотрим рекурсивный алгоритм построения бинарного дерева на основе обучающей выборки S.

Для предъявляемой обучающей выборки S ищется наиболее важный вопрос, который помещается в корневую вершину дерева. Обучающее множество S в соответствии с ответами («Да, «Нет») делится на две подвыборки. Далее для каждой подвыборки снова ищется наиболее важный вопрос, и порождаются по две новые ветви. Процесс завершается, когда использованы все вопросы.

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

Для каждого вопроса Q строится К-арный кортеж, где j-е значение в кортеже имеет значение:

1, если j-й пример из S дает ответ «Да» на вопрос Q,

j =

0 – в противном случае.

 

Расстояние между двумя вопросами определяется как расстояние между двумя двоичными векторами по Хеммингу. Обозначим такое расстояние между векторами X и Y как H_d(X,Y). При этом из рассмотрения исключаются вопросы, на которые все примеры из S дают одинаковый ответ. Для искомого свойства Р строится К-арный кортеж на всех объектах S по правилу: j-е значение в кортеже Р равно 1, если j-й пример из S обладает искомым свойством Р, и 0 – если не обладает. Чтобы выбрать наиболее важный вопрос, необходимо найти среди всех подходящих вопросов Q такой, чья связь со свойством Р наиболее тесная. Для этого используется следующее правило: p_m=min(H_d(P,Q), K–H_d(P,Q)), т.е. берется наименьшее расстояние по Хеммингу от Q до P и от Q до –P.

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

Индукция решающих деревьев (ID3)

Предыдущие алгоритмы (древ и АМХ) строят только бинарное дерево решений, тогда как каждый узел в дереве, построенном алгоритмом ID3, может иметь… Алгоритм строит такое решающее дерево, в котором с каждым узлом ассоциирован… Если имеется n равновероятных значений атрибута, то вероятность р каждого из них равна 1/n и информация, сообщаемая…

Метод фокусирования

В методе фокусирования предполагается, что над значениями каждого из атрибутов Аi построена иерархия типа «класс – подкласс». Элементы нижнего… Важным требованием к подобной иерархии будет то, что каждые два элемента… Каждому элементу иерархии соответствует конъюнкт вида AiÎSij в формируемых правилах, причем правило содержит в…

Контрольные вопросы и упражнения

1. Что такое индукция? Индуктивные рассуждения?

2. В чем отличие индуктивных рассуждений от дедуктивных?

3. Приведите примеры индуктивных рассуждений.

4. Какие методы, использующие индуктивные рассуждения, Вы знаете?

5. В чем суть ДСМ-метода?

6. Дайте сравнительный анализ методам и алгоритмам, использующим индуктивные рассуждения.

Рассуждения по аналогии

Аналогия в общепринятом смысле – это равенство соотношений частей двух предметов, сходство их структур. Мышление по аналогии заключается в… Мышление по аналогии – один из важнейших источников новых научных гипотез.… 8.1. Виды аналогий и приемы работы с ними

Простая аналогия

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

Модальные логики

1. Алетические логики – вводятся операторы «возможность», «необходимость»: □ – необходимость. ◊ – возможность.

Применение нечеткой математики

1. Элемент принадлежит данному множеству. 2. Элемент не принадлежит данному множеству. 3. Элемент принадлежит данному множеству со степенью уверенности mÎ(0, 1).

Нечеткая силлогистика

1. Среди тех, кто носит цилиндр, почти все ходят с тросточкой. 2. Среди тех, кто ходит с тросточкой, почти все пьют мартини. Возможно два варианта вывода в этом силлогизме:

Возможные схемы нечетких рассуждений

Вероятностная схема рассуждений

Возможно несколько вероятностных схем рассуждений.

1. P(A ® B) > q

P(A) > r

P(B) > min (0, q + r - 1)

 

2. P(A ® B) > q

P(A) > r

P(A) < min (1, 1 - q + r)

 

3. P(A Ç B) > q

P(A) > r

P(B) > q * r

 

4. P(A Ç B) > q

P(A) < r

P(B) < min (1, q / 2)

Моделирование необходимых и достаточных условий

q, r – отметки на лингвистических шкалах.

1. □ (A ® B) > q

□ (A) > r

□ (B) > min (q, r)

2. □ (A ® B) > q

□ (B) < r

□ (A) < c

c = 1, при q £ r,

c = r, при q > r.

Учет необходимости и возможности

1. □ (A ® B) > q

◊ (A) > r

□ (B) > c

c = 0, при q + r £ 1,

c = r, при q + r > 1.

 

2. ◊ (A ® B) > q

□ (B) > r

◊ (B) > c

c = 0, при q + r £ 1,

c = q, при q + r > 1.

Учет взаимосвязи между событиями (схема правдоподобных рассуждений)

1. A ® B

В – само по себе почти невероятно

В – истинно

А — весьма правдоподобно

2. В без А – практически не происходит

В – истинно

A – B

А – весьма правдоподобно

3. А – весьма похоже на В

С ® B

С – истинно

А – весьма правдоподобно

Контрольные вопросы и упражнения

1. Дайте определение монотонных и немонотонных логик.

2. Что такое модальные логики?

3. Перечислите классы модальных логик.

4. Какие существуют способы автоматизации нечетких рассуждений?

10. Представление задач в пространстве состояний

Смысл слова «задача» как синоним слову «проблема» происходит от значения греческого слова «баллейн» – бросать (задача – «объект, брошенный вперед»). Большинство задач, которые встречаются в реальной жизни, не являются полностью определенными, основным способом передачи информации при формулировке таких задач служит естественный язык. Однако с точки зрения решения задач он обладает четырьмя существенными недостатками: естественный язык неполон, избыточен, неоднозначен и неточен.

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

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

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

Пример. Преобразовать алгебраическое выражение:

(АВ + СD) / BC « A/C + D/B.

В качестве состояний в этой задаче должны выступать алгебраические выражения, но нужно также выбрать форму описания состояния. Можно использовать двоичные деревья, в которых неконцевые вершины – алгебраические операции, а концевые вершины – постоянные или переменные (символы А, В, С, D, которые появляются в выражении). Законы алгебраических преобразований – это операторы в пространстве состояний. Применение этих законов приведет к преобразованию этого описания в другие описания, например, в описание состояния АВ/BС + CD/BC:

 

 

и далее в состояние A/C + D/B:

Можно использовать другую форму представления для этой задачи – линейную строку: / + * AB * CD * BC. Так как все операции двуместные, то по этой строке можно восстановить дерево. Таким образом, в задаче необходимо преобразовать исходную линейную строку в строку + / AC / DB.

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

Таблица 8

Операторные функции в пространстве состояний

Входное описание	Выходное описание
Si1	Sj1
Si2	Sj2
…	…

Для больших задач представление в виде таблицы становится практически непригодным, поэтому в общем случае операторы – это вычисления, преобразующие одни описания в другие. Для описания состояния в форме строки имеется удобный способ представления операторных вычислений – правила переписывания, которые имеют вид: S_i ® S_j (строка S_i может быть преобразована в строку S_j).

Например, правило переписывания может иметь вид: A$ ® B$, где А – первый символ некоторой строки, который заменяется на В, $ – произвольная строка.

Представление правил в виде правил переписывания не ограничивается строковыми описаниями состояний. Рассмотрим другую форму правил переписывания на примере.

Пример. «Игра в восемь» – восемь пронумерованных фишек расположены в клетках таблицы 3´3. Одна клетка всегда пустая, на нее можно передвинуть одну из соседних с ней фишку. Нужно перевести некоторое начальное состояние в целевое (упорядоченное).

Пусть начальное состояние имеет вид:

Целевое состояние:

 

Правила переписывания для этой игры.

Описание множества состояний: x_i Î {1,2,…,8}, x_i ¹ x_j (i¹j).

 

х1	х2	х3
х4		х5
х6	х7	х8

 

Для фиксированного расположения пустой клетки возможно 8! расположений фишек 1... 8. Всего состояний 9*8! = 9! = 362880.

 

Правила переписывания:

 

и т.д. Например:

 

 

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

Существуют следующие стандартные задачи поиска:

1. Найти по заданным начальному и конечному состояниям путь на графе.

2. Усложнение первой задачи – дугам приписывается стоимость (стоимость применения соответствующего оператора) и нужно найти путь из начального состояния в конечное, имеющий минимальную стоимость.

3. Найти путь из начального состояния в любое состояние задачи.

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

При неявном способе задания графа определяется некоторое конечное множество {S_i} вершин (начальные вершины) и оператор Г, который применением к некоторой вершине дает все ее дочерние вершины и стоимости дуг.

Неявному заданию графа соответствует еще один способ представления пространства состояний – недетерминированная программа:

 

 

где х, у – произвольные совокупности данных; Г(у) – сыновья вершины у; ВЫБОР – выбор одной из вершин из множества Г(у).

Пример.Представление «Игры в восемь» с помощью недетерминированной программы.

 

Если в результате получено целевое состояние – успех, если нет, то возврат.

Примеры представления задач в пространстве состояний

Задача коммивояжера

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

 

 

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

Операторы. Операторы – вычисления, соответствующие следующим действиям: FA – направиться в город А; FB – направиться в город B; FC – направиться в город С; FE – направиться в город Е; FD – направиться в город D. Оператор неприменим к некоторому описанию состояния, если он не преобразует его в некоторое допустимое состояние. Например, F(A) применим только к списку, содержащему все города. Целевое состояние – любое описание, начинающееся и оканчивающееся городом А и перечисляющее все остальные города один раз.

Фрагмент пространства состояний:

 

 

 

Задача распределения

Пусть имеются два источника жидкости А и В, А дает 100 л/мин, В – 50 л/мин. Источники должны снабжать бассейны C и D (потребность бассейнов по 75 л/мин). Максимальная пропускная способность труб составляет 75 л/мин. Соединение труб допускается только в местах расположения труб и бассейна. Как провести трубы, чтобы их длина была наименьшей.

Состояние – список величин избыточного расхода жидкости, который имеется в точках А,В,С,D.

Начальное состояние – {100, 50, 0, 0}.

Операторы – передача избытка жидкости в минуту из одной точки в другую.

Подходящий избыток – наибольший общий делитель пропускных способностей и потребностей в жидкости в различных точках.

Операторы:

1. Передать 25 литров из А в В.

2. Передать 25 литров из А в С.

3. …

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

Целевое состояние – {0, 0, 75, 75}.

 

 

Задача об обезьяне и банане

В комнате с обезьяной имеется ящик, и к потолку подвешена связка бананов.

Состояние – (w, x, y, z), где w – координаты обезьяны; х – единица или ноль (находится обезьяна на ящике или нет); у – координаты ящика; z – единица или ноль (достала обезьяна банан или нет).

Операторы: (1) подойти в точку (U);

(2) передвинуть ящик в точку (V);

(3) взобраться;

(4) схватить.

Целевое состояние – любое состояние при z =1.

Условия применимости операторов:

(1)

(w, 0, y, z) (U, 0, y, z);

(2)

(w, 0, w, z) (V, 0, V, z);

(3)

(w, 0, w, z) (w, 1, w, z);

(4)

(c, 1, c, 0) (c, 1, c, 1);

где с – координаты банана.

Начальное состояние – (a, 0, b, 0),

где а – координаты обезьяны; b – координаты ящика.

Задача управления

Требуется поддерживать значения переменных: Х – координата тележки, a – угол наклона, a¢ – производная по времени, в определенных пределах.

Управляемая переменная v – скорость тележки, которая принимает значения (+v, -v), значения меняются мгновенно.

 

Задача – принятие решения о том, как следует перемещать тележку (со скоростью +v или со скоростью -v).

Состояние – вектор (Х, a, a¢), переменные принимают дискретные значения с мелким шагом. Пространство состояний – решетка в трехмерном пространстве. Состояние, возникающее после применения оператора, описывается вектором (Х, a, a¢) по истечении Dt c.

Целевое состояние – (Х = 0, a = 0, a¢ = 0). Нужно найти последовательность операторов, которая преобразует любое состояние в целевое. Действия операторов могут быть представлены с помощью дифференциальных уравнений.

Методы поиска в пространстве состояний

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

Метод полного перебора

1. Начальную вершину поместить в список «ОТКРЫТ».

2. Если «ОТКРЫТ» = Æ, то «неудача».

3. Взять первую вершину из списка «ОТКРЫТ» и перенести в список «ЗАКРЫТ». Обозначим эту вершину n.

4. Раскрыть вершину n, образовав всех ее «сыновей». Если «сыновей» нет, то перейти на шаг 2. Поместив всех «сыновей» в конец списка «ОТКРЫТ», построить указатели, идущие назад от них к вершине n.

5. Если какой-то «сын» – цель, то выдать решение, отследив обратный путь по указателям. Иначе – перейти на шаг 2.

Метод равных цен

На дугах заданы цены С(n_i, n_j).

1. Поместить начальную вершину в список «ОТКРЫТ» и положить g(s)=0.

2. Если «ОТКРЫТ» = Æ, то «неудача».

3. Из списка «ОТКРЫТ» взять вершину с минимальной стоимостью (n) и поместить ее в список «ЗАКРЫТ».

4. Если n – цель, то выход с отслеживанием пути.

5. Раскрыть n. Если «сыновей» нет, то перейти на шаг 2. Для каждого «сына» вычислить g(n_i) = g(n) + С(n_i, n_j). Поместить эти вершины со значениями g в список «ОТКРЫТ» и построить указатели. Перейти к шагу 2.

Метод перебора в глубину

1. Начальную вершину поместить в список «ОТКРЫТ».

2. Если «ОТКРЫТ» = Æ, то «неудача».

3. Взять первую вершину из списка «ОТКРЫТ» и перенести в список «ЗАКРЫТ». Обозначим эту вершину n.

4. Если глубина вершины n равна граничной глубине, то перейти к шагу 2, иначе перейти к шагу 5.

5. Раскрыть n. Поместить ее в начало списка «ОТКРЫТ» и построить указатели.

6. Если «сын» – цель, то успех, иначе – перейти на шаг 2.

Контрольные вопросы и упражнения

1. Дайте определения состояния и пространства состояний.

2. Перечислите задачи поиска в пространстве состояний.

3. Постройте фрагмент пространства состояний в задаче управления.

4. Какие существуют методы поиска в пространстве состояний?

11. Распознавание образов

Образ – это структурированное приближенное описание объекта или ситуации. Описания служат для установления соответствия между образами, т.е. установления их идентичности, аналогичности и т. д. В классических моделях образ описывается вектором признаков объекта. В структурных моделях образ – это высказывание, порождаемое грамматикой, соответствующей классу образа. Понятие «распознавание образов» включает два основных процесса: процесс восприятия сознания, свойственный живым организмам; создание механических систем восприятия и познания.

Целью автоматизированных систем распознавания образов является поиск, выделение, идентификация, классификация при описании образов на основе реальных объектов. В общем случае разработка автоматизированных систем распознавания образов состоит из трех этапов: анализ объекта; выбор набора признаков; анализ и классификация.

Основная цель распознавания образов – построение на основе систематических, теоретических и экспериментальных исследований вычислительных средств для отнесения формализованных ситуаций и объектов к соответствующим классам. Задачам распознавания образов присущи следующие характерные особенности:

1. Эти задачи решаются применением двух процедур: приведение исходного объекта к стандартному виду; указание принадлежности или непринадлежности объекта к определенному классу.

2. В этих задачах можно вводить понятие подобия между описаниями объекта, на основе этого формулировать понятия близости объектов.

3. В этих задачах часто оперируют прецедентами, т.е. примерами классификаций, которые известны. Эти примеры предъявляются алгоритму распознавания образов для настройки в процессе обучения.

Выделяются следующие основные типы задач распознавания образов:

1. Классическая задача – распознавание или обучение с учителем, т. е. отнесение предъявленного объекта по его описанию к определенному классу.

2. Автоматическая классификация (обучение без учителя), т. е. разбиение множества объектов по их описаниям на непересекающиеся подмножества – классы;

3. Задача выбора информативного набора признаков объекта, т. е. выбор признаков для описания объекта и оценка их информативности.

4. Задача формализации исходного объекта для построения формализованного описания объекта.

5. Классическая задача с учетом динамики объекта.

6. Задача автоматической классификации с учетом динамики объекта.

7. Задача прогнозирования.

Формы задания исходного объекта для задач могут быть различны: изображения, полученные в различных частях спектра и различными способами и преобразованные в цифровую форму; сигналы; серии изображений (фильмы).

Разработаны различные модели распознавания:

· Р-модели, основанные на принципе разделения, т.е. задаются классы поверхностей, среди них выбирается такая, которая лучше всего разделяет классы объектов;

· С-модели (статистические модели). В них используется аппарат математической статистики, такие модели применяются, если известны вероятностные характеристики классов;

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

· Г-модели, модели голосования или вычисления оценок. Анализируется близость между описаниями ранее классифицированных объектов и объекта распознавания по набору оценок близости, вырабатывается общая схема распознавания объектов данного класса;

· Л-модели, основанные на алгебре логики. В них классы и признаки – логические переменные, а описание классов производится на языке булевой алгебры.

Искусственный нейрон

Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество… На рис. 7 представлена модель, реализующая эту идею. Здесь множество входных… Суммирующий блок, соответствующий телу биологического элемента, складывает взвешенные входы алгебраически, создавая…

Персептроны

Рис. 13. Персептронный нейрон Первое систематическое изучение искусственных нейронных сетей было предпринято… В 60-е годы персептроны вызвали большой интерес и оптимизм. Розенблатт доказал замечательную теорему об обучении…

Преодоление ограничения линейной разделимости

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

Чтобы уточнить требование выпуклости, рассмотрим простую двухслойную сеть с двумя входами, подведенными к двум нейронам первого слоя, соединенными с единственным нейроном в слое 2 (см. рис. 19).

Рис. 18. Выпуклые ограниченные и неограниченные области

Пусть порог выходного нейрона равен 0,75, а оба его веса равны 0,5. В этом случае для того, чтобы порог был превышен и на выходе появилась единица, требуется, чтобы оба нейрона первого уровня на выходе имели единицу. Таким образом, выходной нейрон реализует логическую функцию «и». На рис. 19 каждый нейрон слоя 1 разбивает плоскость х-у на две полуплоскости, один обеспечивает единичный выход для входов ниже верхней линии, другой – для входов выше нижней линии. На рис. 19 показан результат такого двойного разбиения, где выходной сигнал нейрона второго слоя равен единице только внутри V-образной области. Аналогично во втором слое может быть использовано три нейрона с дальнейшим разбиением плоскости и созданием области треугольной формы. Включением достаточного числа нейронов во входной слой может быть образован выпуклый многоугольник любой желаемой формы. Так как они образованы с помощью операции «и» над областями, задаваемыми линиями, то все такие многогранники выпуклы, следовательно, только выпуклые области и возникают. Точки, не составляющие выпуклой области, не могут быть отделены от других точек плоскости двухслойной сетью.

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

Имеется 16 двоичных функций от двух переменных. Если выбирать подходящим образом веса и порог, то можно воспроизвести 14 из них (все, кроме «исключающее или» и «исключающее нет»).

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

Рис. 0.9. “Вогнутая” область решений, задаваемая трехслойной сетью

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

Трехслойная сеть, однако, является более общей. Ее классифицирующие возможности ограничены лишь числом искусственных нейронов и весов. Ограничения на выпуклость отсутствуют. Теперь нейрон третьего слоя принимает в качестве входа набор выпуклых многоугольников, и их логическая комбинация может быть невыпуклой. На рис. 20 иллюстрируется случай, когда два треугольника A и B, скомбинированные с помощью функций «A и не B», задают невыпуклую область. При добавлении нейронов и весов число сторон многоугольников может неограниченно возрастать. Это позволяет аппроксимировать область любой формы с любой точностью. Вдобавок не все выходные области второго слоя должны пересекаться.

 

Рис. 20. «Вогнутая» область решений, задаваемая трехслойной сетью

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

Несмотря на то, что возможности многослойных сетей были известны давно, в течение многих лет не было теоретически обоснованного алгоритма для настройки их весов.

Обучение персептрона

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

ЗАКЛЮЧЕНИЕ

В учебном пособии изложены важнейшие положения классической теории формальных систем, современные методы и алгоритмы искусственного интеллекта, а также вопросы терминологии и истории развития направления «искусственный интеллект» в России и за рубежом. Все модели и алгоритмы изложены с точки зрения возможности их автоматизации и применения к созданию систем искусственного интеллекта, что делает учебное пособие особенно полезным при изучении курсов «Искусственный интеллект», «Экспертные системы», «Современные проблемы автоматизации синтеза проектных решений», «Разработка САПР» для студентов специальностей «Системы автоматизированного проектирования» и «Автоматизированные системы обработки информации и управления».

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Девятков В.В. Системы искусственного интеллекта. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001.

2. Логический подход к искусственному интеллекту. От классической логики к логическому программированию / А. Тэйс, П. Грибомонт, Ж.- Луис и др.: Пер. с фр.- М.: Мир, 1990.

3. Логический подход к искусственному интеллекту. От модальной логики к логике баз данных / А. Тэйс, П. Грибомонт, Г. Халин и др.: Пер. с фр.- М.: Мир, 1998.

4. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с фр.- М.: Мир, 1991.

5. Нильсон Н. Д. Искусственный интеллект. Методы поиска решений.- М.: Мир, 1973.

6. Собрание литературы, библиографий и указателей по нейронным сетям. // Internet, ftp:\\archive.cis.ohio-state.edu.

7. Справочник по искусственному интеллекту в 3-х т. / Под ред. Попова Э.В. и Поспелова Д.А. М.: Радио и связь, 1990.

8. Уотермен Ф. Нейрокомпьютерная техника: теория и практика: Пер. с англ.- М.: Радио и связь, 1992.

9. Minsky M., and Papert S., 1969. Perseptrons. Cambridge, MA: MIT Press. (Русский перевод: Минский М. Л., Пейперт С. Персептроны. –М. Мир. – 1971.

10. Nilson N.J. Principles of Artificial intelligence.– Palo Alto, California: Tioga Press, 1980 (В 1985г. русский перевод книги вышел в издательстве "Радио и связь").

11. Rich E., Knight K. Artificial Intelligence. McGraw-Hill, New York, 1991.

12. Winston P.H. Artificial Intelligence. Addison-Wesley, Reading, Massachusetts, Third Edition, 1992.