1.2.Место представления знаний в искусственном интеллекте
В интеллектуальной области невозможно создать универсальный алгоритм, подходящий для решения любой задачи. Этим интеллектуальные области отличаются от неинтеллектуальных, в которых существуют алгоритмы "делай раз, делай два, делай три…". Метод решения задачи в интеллектуальной области —– это всегда поиск новых подходов, новых путей, в конце концов, если ничего не удается придумать —– банальный перебор всех возможностей в поисках решения.
1.2.1.Итеративный характер решения задач
Общая схема решения проблемы с помощью компьютера изображена на Рис. 8. Стрелочки сверху вниз —– детерминированный процесс, стрелочки снизу вверх —– недетерминированный. Решение проблемы всегда носит, в целом, недетерминированный характер. Это метод проб и ошибок, метод поиска, в результате которого часто приходится возвращаться на предыдущие шаги.
Если обратная связь в таком процессе (стрелочки снизу вверх) реализуется через человека (а это происходит достаточно часто), то такой процесс не может называться обработкой знаний. Для того чтобы можно было говорить именно о компьютерной обработке знаний, каждая петля обратной связи должна замыкаться, соответственно, через компьютер. И тогда данные, с которыми работает такая программа, вправе называться знаниями.
Рис. 8. Схема процесса решения задачи на компьютере
При традиционном процедурном программировании (сверху вниз), решение целиком зависит от задачи. Каждая задача имеет свое решение, и решение одной задачи не может быть непосредственно, без дополнительной работы, использовано для решения другой. В ИИ (непроцедурное программирование) один и тот же метод поиска может применяться к целому набору проблем.
Наше резюме таково. Если задача не имеет прямого алгоритма решения, решается перебором, и возвраты осуществляются не через голову программиста, а через саму программу, то это прикладная система с элементами искусственного интеллекта. Если же задача имеет прямой алгоритм решения, который находит программист (может быть, за несколько попыток), но не сама программа, то искусственный интеллект отсутствует (возможно, присутствует естественный интеллект программиста). Но, фактически, непроходимой границы между этими случаями нет.
1.2.2.Знание и незнание
Явно выраженную границу между знанием и незнанием указать невозможно. На самом деле точной границы для представления знаний в компьютере нет —– всякая программа и всякие данные представляют какие-то знания. С другой стороны, самые тонкие философские соображения можно (на естественном языке) записать в компьютер, и они будут там представлены бессмысленной последовательностью байтов. Байты присутствовать в компьютере будут, но философские знания?... Точнее говоря, ничто в компьютере не есть знания без нашей собственной интерпретации, и почти из всего можно извлечь знание, если как следует постараться. Рассмотрим это на модельном примере.
Допустим, мы хотим, чтобы компьютер отсортировал набор чисел в порядке их возрастания. Мы, люди, несомненно, знаем, как это сделать. Рассмотрим, можем ли мы научить это делать компьютер, то есть, можем ли мы представить необходимые знания в компьютере? Пусть нам заранее известно, что этих чисел три и они равны 3, 5 и 7. Можно научить компьютер решать данную задачу, написав всего один оператор:
Write (3, 5, 7)
Таким образом, мы представили в компьютер знания, достаточные для решения этой отдельной частной задачи. Знания представлены в форме одного оператора языка программирования.
Усложним задачу. Пусть чисел по-прежнему три, но при этом значение их произвольное. Составим процедуру, способную отсортировать эти числа по возрастанию:
proc Sort3 (x, y, z)
if x > y then x :=: y end if
if y > z then y :=: z end if
if x > y then x :=: y end if
Write (x, y, z)
end proc
Таким образом, мы научили компьютер решать довольно большое множество задач, связанных с сортировкой трех чисел по возрастанию, не слишком удлинив при этом запись. Во всяком случае, данная запись намного меньше, чем все возможные операторы Write со всеми возможными комбинациями аргументов12. Знания представлены в форме процедуры с параметрами. Другими словами, механизм процедур в языках программирования —– это уже метод представления знаний. Просто это достаточно старый метод, мы к нему привыкли, и не воспринимаем как механизм представления знаний.
Возникает еще один вопрос: откуда взялась процедура Sort3?
Можно сказать, что, как обычно, ее придумал программист. Но мы дадим не совсем привычный ответ, показав, как можно представить в программе знания, достаточные для того, чтобы компьютер сам придумал процедуру, подобную Sort3.
Так как в процедуре Sort3 есть фрагменты кода, похожие друг на друга, и их больше двух, следует применить специальный рефакторинг (преобразование текста программы, не меняющее выполняемую программой функцию), который называется запроцедуривание. Запроцедуривание – это такой рефаторинг, при котором повторяющиеся или похожие фрагменты программы заменяются вызовом вновь введенной процедуры. Переписав процедуру Sort3, введя процедуру Sort2, получаем процедуру Sort3'.
proc Sort3’ (x, y, z)
Sort2(x, y)
Sort2(y, z)
Sort2(x, y)
Write (x, y, z)
end proc
proc Sort2(u, v)
if u > v then u :=: v end if
end proc
Но процедуру Sort2 нетрудно специфицировать формально:
x, y { Sort2(x, y) } x < y
Здесь перед заголовком процедуры (который заключен в фигурные скобки) выписано предусловие, а после заголовка —– постусловие. Процедура Sort2 очень проста и очевидно полезна во многих случаях. Можно допустить, что эта процедура вместе со спецификацией (предусловие и постусловие) содержится в библиотеке готовых процедур, доступной транслятору.
Предусловие —– формальное утверждение о входных параметрах процедуры, которое должно быть выполнено до начала вызова процедуры для того, чтобы процедура работала правильно.
Постусловие —– формальное утверждение о входных и выходных параметрах процедуры, выполнение которого гарантируется после окончания вызова процедуры в случае, если было выполнено предусловие.
Тогда, используя эту спецификацию, транслятор может логически вывести процедуру Sort3':
{x, y, z}
Sort2(x, y) {x < y, z}
Sort2(y, z) {y < z, x < z}
Sort2(x, y) {x < y < z}.
Таким образом, мы немного усложнили механизм транслятора (допустив возможность логического вывода при трансляции) и получили систему автоматического синтеза программ. Другими словами, мы компактно записали не одну процедуру Sort3, а целый класс процедур. В этом случае знания представлены в виде специфицированной процедуры и алгоритма логического вывода, встроенного в транслятор.
Кажется, что понятия «знание» и «процедура» ортогональны. Если есть процедура, никакие знания не нужны —– делай, как сказано в процедуре, и задача будет решена. Приведенный пример показывает, что понятия «знание» и «процедура» (или, лучше сказать, алгоритм) не только не противоположны, но даже, можно сказать, неразделимы. Любой алгоритм обязательно содержит знания, а любые знания представляются, в конечном счете, алгоритмами.
1.2.3.Алгоритмы поиска решения и представление знаний
Первый этап развития ИИ был связан с разработкой методов решения задач —– алгоритмов поиска решения и построения логического вывода. В настоящее время это уже достаточно проработанный и изученный вопрос. Основные классические результаты изложены в третьей лекции.
УНИВЕРСАЛЬНЫЙ РЕШАТЕЛЬ ЗАДАЧ
Первые исследования, относимые к искусственному интеллекту были предприняты почти сразу же после появления первых вычислительных машин.
В 1954 году американский исследователь А. Ньюэлл (A. Newel) решил написать программу для игры в шахматы. К работе была привлечена группа голландских психологов под руководством А. Де Гроота (A. De Groot), изучавших стили игры выдающихся шахматистов. Через два года совместной работы этим коллективом был создан язык программирования IPL (Information Processing Language) – по-видимому, первый символьный язык обработки списков. Вскоре была написана и первая программа, которую можно отнести к достижениям в области искусственного интеллекта. Эта была программа "Логик-Теоретик" (1956 г.), предназначенная для автоматического доказательства теорем в исчислении высказываний.
Собственно же программа для игры в шахматы, NSS, была завершена в 1957 г. В основе ее работы лежали так называемые эвристики (правила, которые позволяют сделать выбор при отсутствии точных теоретических оснований) и описания целей. Управляющий алгоритм пытался уменьшить различия между оценками текущей ситуации и оценками цели или одной из подцелей. Шахматная сила программы была невелика.
В 1960 г. той же группой, на основе принципов, использованных в NSS, была написана программа, которую ее создатели назвали GPS (General Problem Solver ) – универсальный решатель задач. Программа GPS могла справляться с рядом головоломок, вычислять неопределенные интегралы, решать некоторые другие задачи.
Название «Универсальный решатель задач» обусловлено тем фактом, что это была едва ли не первая система для решения задач (problem-solving system), в которой общие методы решения были отделены от знаний, определяющих конкретную задачу. Часть программы, осуществлявшая поиск решения, не обладала информацией о конкретной задаче, с которой она работала. Специфичные для конкретной задачи знания организовывались в отдельные структуры: объекты и операторы преобразования объектов. Задача для системы GPS ставилась в виде пары, состоящей из начального объекта и целевого объекта, в который начальный объект должен быть преобразован.
Методология поиска, использованная в GPS, отличалась от предшествующих методов поиска в пространстве состояний тем, что она динамически выбирала путь, по которому продолжить поиск. Т.е. система пыталась искать решение в первую очередь в «наиболее перспективных» ветвях поиска. Такая методология была названа «анализ средств и целей» (means-ends analysis). Ее суть заключалась в том, что сначала отыскивалось различие между текущим объектом и объектом, который мы хотим получить. Это различие относилось к одному из ряда классов различий. С каждым классом был сопоставлен набор операторов, способных уменьшить различие между текущим и целевым объектами.
На каждом шаге поиска программа GPS определяла различие объектов и выбирала один из релевантных операторов, который и пыталась затем применить к текущему объекту. Поиск подходящей последовательности операторов выполнялся в глубину до тех пор, пока операторы оказывались применимы, а ветвь поиска «выглядела перспективной». Если ветвь поиска была бесперспективной, то выполнялся возврат. Важной особенностью анализа средств и целей является то, что всегда выбирается релевантный оператор, уменьшающий различие объектов, даже если он и не применим к текущему объекту. Вместо того чтобы отказаться от неприменимого к текущему объекту оператора, программа GPS пыталась преобразовать текущий объект в объект, пригодный для применения выбранного оператора.
Наилучшим алгоритмом для поиска оптимальных путей в различных пространствах является A* (читается как "А-звездочка"). Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. В их работе он упоминается как «алгоритм A». Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута, идущего через этот узел. Типичная формула эвристики выражается в виде:
f(n) = g(n) + h(n)
где:
f(n) значение оценки, назначенное узлу n
g(n) наименьшая стоимость прибытия в узел n из точки старта
h(n) эвристическое приближение стоимости пути к цели от узла n
Таким образом, этот алгоритм сочетает в себе учет длины предыдущего пути из алгоритма Дийкстры с эвристикой из алгоритма "лучший-первый". Алгоритм хорошо отражен в листинге 3. Так как некоторые узлы могут обрабатываться повторно (для поиска оптимальных путей к ним позднее) необходимо ввести новый список Closed для их отслеживания.
A* имеет множество интересных свойств. Он гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h(n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью.
Однако для нетривиальных случаев трудоемкость поиска решения очень велика. Трудоемкость поиска решения —– это быстрорастущая функция (в большинстве случаев растущая как экспонента или быстрее), аргументом которой является общий объем базы знаний. Рассматривая ниже конкретные алгоритмы, мы доказываем точные оценки, но здесь, на неформальном уровне, хотим убедить читателя в справедливости этого замечания. Пусть искомое решение является комбинацией конечного числа заранее заданных элементов, которых n. Тогда всего существует 2n–1 непустых комбинаций13, если брать элементы без повторений, а если с повторениями, то еще больше. Заранее мы не знаем, какая комбинация является решением, в этом и состоит поисковый характер алгоритма, а значит, в худшем случае нам придется перебрать все комбинации!
Один из способов уменьшения трудоемкости поиска решения является изменение алгоритмов поиска с целью повышения их внутренней эффективности, не зависящей от решаемой задачи. Однако для очень многих задач, типичных для ИИ, доказана их NP-полнота14. Построение эффективного (более эффективного, чем экспонента) алгоритма для них совершенно невероятно. Если для какой-то еще не исследованной задачи ИИ вдруг обнаруживается эффективный (скажем, полиномиальный) алгоритм, то задачу перестают квалифицировать как задачу ИИ, и переносят в область обычного программирования. Таким образом, в настоящий момент существенного улучшения в повышении внутренней эффективности алгоритмов поиска ожидать трудно.
Гораздо более продуктивным методом, позволяющим уменьшить трудоемкость поиска решения, является повышение эффективности представление знаний. Если выбор изощренного представления позволяет уменьшить объем базы знаний, то тот же стандартный алгоритм поиска становится значительно эффективнее в том смысле, что расширяются границы его применимости. Поясним это модельным числовым примером, сравнивающим два гипотетических способа представления знаний. Пусть одна и та же задача в первом представлении имеет размер n, а во втором – n/2. Пусть переборный алгоритм один и тот же, и имеет трудоёмкость 2k, где k – размер задачи. Пусть, при этом, более компактное представление дается не даром: каждый шаг перебора выполняется в десять раз дольше и еще 100 единиц времени безвозвратно теряется на предварительную обработку. Фактически, мы сравниваем две функции: 2n и 100 + 10*2n/2. При малых n первая функция меньше, но после n=8 вторая функция становится меньше, и ее преимущество только возрастает с ростом n. Даже небольшой выигрыш в значении аргумента показательной функции перевешивает все другие проигрыши!
Рис. 9. Сравнение трудоемкости поиска в зависимости от компактности базы знаний
Компактность базы знаний —– определяющий фактор эффективности системы и, следовательно, границ применимости ПСИИ. Именно это обстоятельство определяет структуру данного курса. Курс структурирован по методам представления знаний, а не по методам поиска решения. При решении любой задачи в интеллектуальной области сначала следует выбрать представление знаний, потом подобрать подходящий алгоритм поиска решения. Дело в том, что если выбрано неудачное представление знаний, то никакие ухищрения с алгоритмами не помогут. Если же изобретено особо удачное представление знаний, то, скорее всего, самый обычный алгоритм поиска решения даст вполне удовлетворительные результаты.
|
