Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 10
Текст из файла (страница 10)
Предложенная им Ж теорема о неполноте показывает, что в любом языке, достаточно выразительном для описания свойств натуральных чисел, существуют истинные высказывания, которые являются недоказуемыми, в том смысле, что их истинность невозможно установить с помощью какого-либо алгоритма. Этот фундаментальный результат может также рассматриваться как демонстрация того, что имеются некоторые функции от целых чисел, которые не могут быть представлены с помощью какого-либо алгоритма, т.е. они не могут быть вычислены. Это побудило Алана Тьюринга (1912 — 1954) попытаться точно охарактеризовать, какие функции способны быть вычисленными. Этот подход фактически немного проблематичен, поскольку в действительности понятию вычисления, или эффективной процедуры вычисления, не может быть дано формальное определение.
Но общепризнано, что вполне удовлетворительное определение дано в тезисе Черча — Тьюринга, который указывает, что машина Тьюринга [15!8) способна вычислить любую вычислимую функцию. Кроме того, Тьюринг показал, что существуют некоторые функции, которые не могут быть вычислены машиной Тьюринга. Например, вообще говоря, ни одна машина не способна определить, возвратит ли данная конкретная программа ответ на конкретные входные данные или будет работать до бесконечности. Хотя для понимания возможностей вычисления очень важны понятия недоказуемости и невычислимости, гораздо большее влияние на развитие искусственного интеллекта оказало понятие Ъ. неразрешимости. Грубо говоря, задача называется неразрешимой, если время, требуемое для решения отдельных экземпляров этой задачи, растет экспоненциально с увеличением размеров этих экземпляров.
Различие между полиномиальным и экспоненциальным ростом сложности было впервые подчеркнуто в середине 1960-х годов в работах Кобхэма [272[ и Эдмондса [430[. Важность этого открытия состоит в следующем: экспоненциальный рост означает, что даже экземпляры задачи умеренной величины не могут быть решены за какое- либо приемлемое время. Поэтому, например, приходится заниматься разделением общей задачи выработки интеллектуального поведения на разрешимые подзадачи, а не пытаться решать неразрешимую задачу.
Как можно распознать неразрешимую проблему? Один из приемлемых методов такого распознавания представлен в виде теории ъ. МР-полноты, впервые предложенной Стивеном Куком [289[ и Ричардом Карпом [772). Кук и Карп показали, что существуют большие классы канонических задач комбинаторного поиска и формирования рассуждений, которые являются ХР-полными. Существует вероятность того, что любой класс задач, к которому сводится этот класс гч Р-полных задач, является неразрешимым. (Хотя еще не было доказано, что ХР-полные задачи обязатель- 45 Глава 1.
Введение но являются неразрешимыми, большинство теоретиков считают, что дело обстоит именно так.) Эти результаты контрастируют с тем оптимизмом, с которым в популярных периодических изданиях приветствовалось появление первых компьютеров под такими заголовками, как "Электронные супермозги", которые думают "быстрее Эйнштейна!" Несмотря на постоянное повышение быстродействия компьютеров, характерной особенностью интеллектуальных систем является экономное использование ресурсов. Грубо говоря, наш мир, в котором должны освоиться системы ИИ, — это чрезвычайно крупный экземпляр задачи. В последние годы методы искусственного интеллекта помогли разобраться в том, почему некоторые экземпляры ХР-полных задач являются сложными, а другие простыми ]244].
Кроме логики и теории вычислений, третий по величине вклад математиков в искусственный интеллект состоял в разработке 'т. теории вероятностей. Идея вероятности была впервые сформулирована итальянским математиком Джероламо Кардано (1501 — 1576), который описал ее в терминах результатов событий с несколькими исходами, возникающих в азартных играх. Теория вероятностей быстро стала неотъемлемой частью всех количественных наук, помогая использовать недостоверные результаты измерений и неполные теории.
Пьер Ферма (160!— 1665), Блез Паскаль (1623 — 1662), Джеймс Бернулли (1654 — 1705), Пьер Лаплас (1749 — 1827) и другие ученые внесли большой вклад в эту теорию и ввели новые статистические методы. Томас Байес (1702 — 1761) предложил правило обновления вероятностей с учетом новых фактов. Правило Байеса и возникшее на его основе научное направление, называемое байесовским анализом, лежат в основе большинства современных подходов к проведению рассуждений с учетом неопределенности в системах искусственного интеллекта. Экономика (период с 1776 года по настоящее время) ° Как следует организовать принятие решений для максимизации вознаграждения? ° Как действовать в таких условиях, когда другие могут препятствовать осуществлению намеченных действий? ° Как действовать в таких условиях, когда вознаграждение может быть предоставлено лишь в отдаленном будущем? Экономика как наука возникла в 1776 году, когда шотландский философ Адам Смит (1723 — 1790) опубликовал свою книгу Ап ?пци!гуотпо йе Ха!иге апг? Саизез оГйе И~еа1й оГАгаяопз (Исследование о природе и причинах богатства народов).
Важный вклад в экономику был сделан еще древнегреческими учеными и другими предшественниками Смита, но только Смит впервые сумел оформить эту область знаний как науку, используя идею, что любую экономику можно рассматривать как состоящую из отдельных агентов, стремящихся максимизировать свое собственное экономическое благосостояние. Большинство людей считают, что экономика посвящена изучению денежного оборота, но любой экономист ответит на это, что в действительности он изучает то, как люди делают выбор, который ведет к предпочтительным для них результатам. Математическая трактовка понятия "предпочтительных результатов'*, или полезности, была впервые формализована Леоном Валрасом (1834 — 1910), уточнена Фрэнком Рамсеем ]1265], а затем усовершенствована Джоном фон Нейманом и Оскаром Моргенштерном в книге Тпе Тпеогу оГбатез апг? Есопотк Вепаиог (Теория игр и экономического поведения) ]1546].
46 Часть!. Искусственный интеллект ~к Теория решений, которая объединяет в себе теорию вероятностей и теорию полезности, предоставляет формальную и полную инфраструктуру для принятия решений (в области экономики или в другой области) в условиях неопределенности, т.е. в тех случаях, когда среда, в которой действует лицо, принимающее решение, наиболее адекватно может быть представлена лишь с помощью вероятностных описаний.
Она хорошо подходит для "крупных" зкономических образований, где каждый агент не обязан учитывать действия других агентов как индивидуумов. А в "небольших" экономических образованиях ситуация в большей степени напоминает игру, поскольку действия одного игрока могут существенно повлиять на полезность действий другого (или положительно, или отрицательно). Ъ.
Теория игр, разработанная фон Нейманом и Моргенштерном (см. также !963)), позволяет сделать неожиданный вывод, что в некоторых играх рациональный агент должен действовать случайным образом или, по крайней мере, таким образом, который кажется случайным для соперников. Экономисты чаще всего не стремятся найти ответ на третий вопрос, приведенный выше, т.е, не пытаются выработать способ принятия рациональных решений в тех условиях, когда вознаграждение в ответ на определенные действия не предоставляется немедленно, а становится результатом нескольких действий, выполненных в определенной последовательности. Изучению этой темы посвящена область ъ. исследования операций, которая возникла во время Второй мировой войны в результате усилий, которые были предприняты в Британии по оптимизации работы радарных установок, а в дальнейшем нашла применение и в гражданском обществе при выработке сложных управленческих решений.
В работе Ричарда Беллмана )97) формализован определенный класс последовательных задач выработки решений, называемых марковскими процессами принятия решений (Магкоч Оес(з(оп Ргосезз — М!)Р), которые рассматриваются в главах 17 и 21. Работы в области экономики и исследования операций оказали большое влияние на сформулированное в этой книге понятие рациональных агентов, но в течение многих лет исследования в области искусственного интеллекта проводились совсем по другим направлениям. Одной из причин этого была кажущаяся сложность задачи выработки рациональных решений. Тем не менее Герберт Саймон (1916 — 2001) в некоторых из своих ранних работ показал, что лучшее описание фактического поведения человека дают модели, основанные на ъ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
