Лекции - Искусственный интеллект
Подождите немного. Документ загружается.
3) обеспечивать естественный способ выражения
необходимых знаний.
Задачи ИИ не решают путем их упрощения и «подгонки» к
уже имеющимся понятиям, предлагаемым традиционными
формальными системами, например массивом. Эти задачи
связаны скорее с качественными, а не количественными
проблемами, с аргументацией, а не вычислениями, с
организацией больших объемов знаний, а не реализацией
отдельного четкого алгоритма. Чтобы удовлетворять этим
требованиям, язык представлений ИИ должен обладать
следующими свойствами:
1) обрабатывать знания, выраженные в качественной
форме;
2) получать новые знания из набора фактов и правил;
3) отображать общие принципы и конкретные ситуации;
4) передавать сложные семантические значения;
5) обеспечивать рассуждения на макроуровне.
Рассмотрим эти свойства подробно.
Исчисление предикатов непосредственно фиксирует эту
информацию. В исчислении предикатов мир блоков (рисунок)
может быть описан логическими утверждениями:
clear (c)
clear (a)
ontable (a)
ontable (b)
on (c, b)
cube (a)
cube (b)
pyramid (c)
Мир блоков
Логическое получение новых знаний из набора фактов и
правил. Любой интеллектуальный объект должен обладать
53
a b
c
способностью логически получать дополнительные знания из
имеющегося описания реального мира.
В примере из мира блоков можно определить тест,
устанавливающий, является ли блок открытым, т.е. не
располагается на его верхней грани другой объект.
Можно определить общее правило, позволяющее системе
делать логические выводы из имеющихся фактов. В исчислении
предикатов это правило может выглядеть так:
)(),( XclearXYYonX
Оно означает следующее: для любого элемента Х элемент
Х является открытым, если не существует такого Y, что Y
находится на Х. Это правило может применяться в различных
ситуациях при замене значения Х и Y. Позволяя программисту
формулировать обобщенные правила вывода, исчисление
предикатов предоставляет большие удобства в выражении
знания. Кроме того, исчисление предикатов дает возможность
проектировать гибкие и достаточно общие системы, умеющие
действовать разумно в различных ситуациях.
Нейтронные сети тоже выводят новые знания из
имеющихся фактов, хотя правила, используемые ими, скрыты.
Классификация – это общепринятая форма логического вывода,
выполняемого такими системами.
Отображение общих принципов наряду с конкретными
ситуациями. ИС должна быть максимально общей, любой
хороший язык представления нуждается в переменных.
Необходимость качественных рассуждений делает
использование и реализацию переменных сложной задачей по
сравнению с их трактовкой в традиционных языках
программирования. Значение, типы и правила обработки
данных в языках программирования, ориентированных на
вычисления, ограничены и не годятся для реализации ИС. Для
обработки связанных переменных и объектов существуют
специальные языки представления знаний. Высокая
способность обобщения – это ключевое свойство нейронных
сетей, систем обучения и других адаптивных систем.
54
Передача сложных семантических знаний. Во многих
областях ИИ решение задачи требует использования
высокоструктурированных взаимосвязанных знаний.
Семантические отношения также необходимы для описания
причинных связей между событиями. Они позволяют понять
простые рассказы или представить план действий робота как
последовательность элементарных действий, которые должны
быть выполнены в определенном порядке.
Хотя все ситуации могут быть представлены в виде
совокупности предикатов, для программиста, имеющего дело со
сложными понятиями, необходимо высокоуровневое
представление структуры процесса. Предикатное описание
можно представить графически, используя для отображения
предикатов, определяющих отношения, дуги или связи графа.
Такое описание, называемое семантической сетью, является
фундаментальной методикой представления семантического
значения.
Кроме того знания могут быть организованы так, чтобы
отражать естественную структуру экземпляра класса из данной
предметной области. Некоторые связи указывают на
принадлежность к классу и задают свойства, характерные для
описания данного класса, которые наследуют все члены класса.
Наследование – инструмент представления классифициро-
ванной структурированной информации, который гарантирует,
что все члены класса обладают общими свойствами.
Теория графов эффективно и естественно выражает
сложные семантические знания. Кроме того, она позволяет
описать структурную организацию базы знаний. Семантические
сети – это достойная альтернатива исчислению предикатов.
Рассуждения на метауровне. ИС должна не только знать
предмет, но также знать о том, что она знает этот предмет. Она
должна быть способна решать задачи и объяснять эти решения.
Система должна описывать свои знания, как в конкретных, так
и в обобщенных терминах, узнавать их ограничения и учиться в
процессе взаимодействия с миром. Это «осведомленность о
своих знаниях» составляет более высокий уровень знаний,
55
называемых метазнаниями, необходимых для проектирования и
адекватного описания ИС.
Решение задачи ИИ можно свести к выбору представления
знаний среди возможных альтернатив. Выбор подходящего
представления очень важен для разработчиков компьютерных
программ, обеспечивающих решение задач ИИ. Не смотря на
большое разнообразие языков представления, используемых в
ИИ, все они должны удовлетворять общим требованиям
выразительности, эффективности и правильности дедуктивных
выводов.
Решение задачи методом поиска. Вторым аспектом
гипотезы о символьной системе Ньюэлла и Саймона является
поиск решения задачи среди альтернативных вариантов. С
точки зрения простого здравого смысла это выглядит разумно,
поскольку именно так задачи решает человек. Рассматривая ряд
альтернативных вариантов, мы пытаемся решить задачу.
В качестве простого примера рассмотрим игру «крестики-
нолики». Для любой заданной ситуации всегда существует
только конечное число допустимых ходов игрока. Первый игрок
может разместить крестик в любой из девяти клеточек пустой
игровой доски. Каждый из таких шагов порождает различные
варианты заполнения игровой доски, которые позволяют
противнику сделать восемь возможных ответных ходов и т.д.
Эту совокупность можно представить в виде вершин графа.
Дуги графа представляют разрешенные ходы, приводящие от
одной конфигурации игровой доски к другой. Вершины графа
соответствуют различным состояниям игрового поля.
Результирующая структура называется графом пространства
состояний. Значение этого графа состоит в том, что он дает
возможность проследить последовательность шагов в любой
игре. Проход начинается с вершины, соответствующей пустой
игровой доске, а движения по дугам приводят к вершинам-
состояниям, представляющим очередной ход или победу.
Представление в пространстве состояний, таким образом,
позволяет рассматривать все возможные варианты игры
56
«крестики-нолики» как различные пути на графе пространства
состояний.
Формализация теории графов также сделала возможным
поиск в пространстве состояний – основной концептуальный
инструмент ИИ. Графы можно использовать для моделирования
скрытой структуры задачи. Вершины графа состояний
представляют собой возможные стадии решения задачи; ребра
графа отражают умозаключения, ходы в игре или другие шаги в
решении. Решение задачи – это процесс поиска пути к решению
на графе состояний. Описывая все пространство решений,
графы состояний представляют мощный инструмент для
измерения структурированности и сложности проблем, анализа
эффективности, корректности и общности стратегий решения.
Описав игру, таким образом, можно с помощью поиска на
графе найти эффективную игровую стратегию. Возможность
выбора эффективной стратегии – это не единственное
преимущество графа. Регулярность и точность представления
пространства состояний позволяют непосредственно
реализовать игру на компьютере.
Нейронные сети и другие адаптивные системы также
выполняют поиск, особенно во время обучения и адаптации.
Всевозможные обобщения данных, которые самообучающаяся
программа может сформировать в процессе обучения, можно
представить себе как элементы пространства. Задача алгоритма
обучения состоит в использовании обучающих данных для
поиска в этом пространстве. В нейронной сети, например,
пространством поиска является множество всех наборов весов
связей сети. В процессе поиска набора связей, которые
максимально соответствуют обучающим данным, эти веса
изменяются.
Не смотря на эту очевидную универсальность, поиска в
пространстве состояний не достаточно для автоматизации
интеллектуального поведения, обеспечивающего
автоматическое решение задач. Но это важный инструмент для
проектирования интеллектуальных программ. Если бы поиска в
пространстве состояний было достаточно, то было бы довольно
57
просто написать программу для игры в шахматы. Для
определения последовательности ходов, ведущих к победе, на
каждом этапе игры нужно было бы осуществлять полный поиск
по всему пространству состояний. Этот метод решения задач
известен как поиск методом полного перебора. Хотя полный
перебор может применяться в любом пространстве состояний,
огромный размер пространства делает этот подход практически
неприемлемым. Игре в шахматы, например, соответствует
приблизительно
120
10
различных состояний игровой доски.
Поиск в таком пространстве состояний выходит за рамки
возможностей любого вычислительного устройства.
Решение задачи человеком основано на субъективных
правилах, направляющих поиск к тем частям пространства
состояний, которые по каким-то причинам кажутся
«обещающим». Эти правила известны под названием эвристик.
Они составляют одну из центральных тем исследований в
области ИИ. Эвристика (термин возник от греческого слова
«находить») – этот стратегия для выборочного поиска в
пространстве состояний.
Эвристика не абсолютно надежна. Нет гарантий, что
хороший эвристический подход может и должен приблизить нас
к верному оптимальному решению задачи. Наиболее важно то,
что эвристика использует знания о природе задачи для
эффективного поиска решения.
Поиск в пространстве состояний обеспечивает средства
формализации процесса решения задачи, а эвристики позволяют
привносить интеллект в этот формализм. Поиск в пространстве
состояний – это формализм, независимый от каких-либо особых
стратегий поиска, и используемый как отправная точка во
многих подходах к решению задач.
58
4.1. Представление задачи в пространстве состояний
Чтобы разрабатывать и внедрять алгоритмы поиска,
разработчик должен уметь анализировать и прогнозировать их
поведение. При этом перед ним стоят следующие вопросы:
1. Гарантированно ли нахождение решения в процессе
поиска?
2. Является ли поиск конченным, или в нем
возможно зацикливание?
3. Если решение найдено, является ли оно
оптимальным?
4. Как процесс поиска зависит от времени выполнения и
используемой памяти?
5. Как разработать интерпретатор для наиболее
эффективного
использования языка представления?
Теория поиска в пространстве состояний лает ответы на
эти вопросы. Представив задачу в виде графа пространства
состояний, можно использовать теорию графов для анализа
структуры и сложности, как самой задачи, так и процедуры
поиска ее решения.
В пространстве состояний задачи вершины графа
соответствуют состояниям решения частных задач, а дуги -
этапам решения задач. Одно или несколько начальных
состояний, соответствующих исходной информации
поставленной задачи, образуют корень дерева. Граф также
включает одно или несколько целевых условий, которые
соответствуют решениям исходной задачи. Поиск в
пространстве состояний характеризует решение задачи как
процесс нахождения пути решения (цепочки, ведущей к
решению задачи) от исходного состояния к целевому.
Определим постановку задачи в пространстве состояний
более формально.
Пространство состояний представляется четверкой {N, A,
S, GD}, где N - множество вершин графа или состояний в
процессе решения задачи, A - множество дуг между вершинами,
59
соответствующих шагам в процессе решения задачи, S - это
непустое множество начальных состояний, которые
описываются одним из следующих способов:
1) измеряемыми свойствами состояний,
встречающихся в
процессе поиска;
2) свойствами путей, возникающих в процессе
поиска, например, «стоимостью» перемещения по дугам пути.
Допустимый путь - это путь из вершины множества S в
вершину из множества GD.
GD - непустое подмножество N, состоящие из целевых
состояний.
Цель может описывать состояние, например, выигрышную
конфигурацию в игре «крестики-нолики». С другой стороны,
цель может описывать некоторые свойства допустимых путей.
В задаче о коммивояжере поиск заканчивается при нахождении
кратчайшего пути через вершины графа.
Дуги в пространстве состояний соответствуют шагам
процесса решения, а пути - решения на различной стадии
завершения. Путь является целью поиска. Он начинается из
исходного состояния и продолжается до тех пор, пока не будет
достигнуто условие цели. Порождение новых состояний вдоль
пути обеспечиваются такими операторами, как «допустимые
ходы» в игре или правила вывода в логической задаче или
экспертной системе.
Одна из общих особенностей графа и одна из проблем,
возникающих при создании алгоритма поиска на графе, состоит
в том, что состояния иногда могут быть достигнуты
различными путями. Важно в этом случае выбрать
оптимальный путь решения задачи. Кроме того, множественные
пути к состоянию могут привести к петлям или циклам. Тогда
алгоритм никогда не достигнет цели.
Если пространство поиска оказывается деревом, то
проблема зацикливания не возникает. Именно поэтому важно
отличать задачи поиска на деревьях от задач поиска на графах с
петлями. Алгоритмы поиска на произвольных графах должны
60
обнаруживать и устранять петли в допустимых путях. При этом
алгоритмы поиска на деревьях выигрывают в эффективности за
счет отсутствия этих тестов и затрат на них.
Игра «крестики-нолики» может использоваться для
иллюстрации поиска в пространстве состояний, поясняя смысл
условия 1 в определении поиска в пространстве состояний. В
задаче о коммивояжере цель описывается условием 2.
4.2. Стратегии поиска в пространстве состояний
Поиск в ПС можно вести в двух направлениях: от
исходных данных задачи к цели и в обратном направлении от
цели к исходным данным.
При поиске на основе данных, которых иногда называют
прямой цепочкой, исследователь начинает процесс решения
задачи, анализируя ее условие, а затем применяет допустимые
ходы или правила измерения состояния. В процессе поиска
правила применяются к известным фактам для получения новых
фактов, которые, в свою очередь, используются для генерации
новых фактов. Этот процесс продолжается до тех пор, пока,
если повезет, не достигнем цели.
Возможен альтернативный подход. Рассмотрим цель,
которую мы хотим достичь. Проанализируем правила или
допустимые ходы, ведущие к цели, и определим условия их
применения. Эти условия становятся новыми целями, или
подцелями, поиска. Поиск продолжается в обратном
направлении от достигнутых целей до тех пор, пока (если
повезет) мы не достигнем исходных данных задачи. Таким
образом, определяется путь от данных к цели, который на самом
деле строится в обратном направлении. Этот подход называется
поиском от цели или обратной цепочкой.
В обоих случаях исследователь работает с одним и тем же
графом ПС, однако порядок и число состояний в процессе
поиска могут различаться. Какую стратегию поиска
предпочесть зависит от самой задачи. При этом следует
учитывать сложность правил, природу и доступность данных
61
задачи. Выбор зависит также от структуры решаемой задачи.
Процесс поиска от цели рекомендован в следующих случаях:
1. Цель поиска явно присутствует в постановке задачи или
может быть легко сформулирована.
2. Имеется большое число правил, которые на основе
полученных данных позволяют генерировать возрастающее
число заключений или целей. Своевременный отбор целей
позволяет отсеять множество возможных ветвей, что делает
процесс поиска в ПС более эффективным.
3. Исходные данные не приводятся в задаче, но
подразумевается, что должны быть известны исследователю. В
этом случае поиск от цели может служить руководством для
правильной постановки задачи.
Поиск на основе данных применим к решению задачи в
следующих случаях:
1. Все или большинство исходных данных заданы в
постановке задачи
2. Существует большое число потенциальных целей, но
всего лишь несколько способов применения фактов и
предоставления информации о конкретном примере задачи.
3. Сформировать цель или гипотезы очень сложно.
Реализация поиска на графах.
Поиск с возвратом - это метод систематической проверки
различных путей в ПС. Алгоритм поиска с возвратом
запускается из начального состояния и следует по некоторому
пути до тех пор, пока не достигнет цели или не упрется в тупик.
Если поиск привел в тупиковую вершину, но алгоритм
возвращается в ближайшую из пройденных вершин и исследует
все ее вершины - братья, а затем спускается по одной из ветвей,
ведущих от вершины брата. Если цель достигнута, то поиск
завершается, и в качестве решения задачи возвращается путь к
цели. Алгоритм работает до тех пор, пока не достигнет цели или
не исследует все ПС.
Поиск в глубину. При поиске в глубину после
исследования состояния сначала необходимо оценить все его
потомки и его потомки, а затем исследовать любую из вершин-
62