Понятие об искусственном интеллекте. Основные направления разработок в области ии. Искусственный интеллект
 Скачать 142.29 Kb.
|
|
Понятие об искусственном интеллекте. Основные направления разработок в области ИИ. Искусственный интеллект – это область информатики, предметом которой является разработка компьютерных систем, обладающих возможностями, традиционно связываемыми со способностями естественного интеллекта. Поиски ответа на вопрос о том, что такое естественный интеллект, привели к ряду замечательных открытий в различных областях знаний: математике, биологии, инженерии, психологии, медицине и др. Одним из способов понимания того, что собой представляет естественный интеллект, является изучение разумного поведения животных и, в особенности, человека. К специфическим особенностям человека (и не только человека), отличающим его от машины, обычно относят: - способность распознавать сложные зрительные и слуховые образы, - понимать язык (естественный), - способность обучаться, рассуждать и делать логические выводы. Артур Тьюринг, которого многие ученые считают основоположником направления искусственный интеллект, в процессе доказательства неразрешимости формальной арифметики (второй проблемы Гильберта) создал, как сказали бы сегодня, виртуальный компьютер – понятие о вычислительной машине, ставшее одним из математических определений алгоритма. В 1950 г. в английском журнале «Mind», в статье под названием «Computting Machinery and Intelligence» (в русском переводе статья вышла под названием «Может ли машина мыслить?»), Артур Тьюринг предложил критерий, позволяющий определить, обладает ли машина (программа) мыслительными способностями. Этот эксперимент получил название теста Тьюринга. Технологии с использованием ИИ применяются сегодня во многих прикладных областях. В последние годы информационные технологии совершили резкий скачок вперед, в основном за счет повышения производительности процессоров и стремительного удешевления памяти. Это привело к появлению приложений, в которых воплощены серьезные теоретические наработки ИИ. При этом можно выделить две тенденции: «военную» и «гражданскую». Если вспомнить теперь уже далекие 80-е годы 20-го века, то одним из несомненных признаков того времени было стремление обозначить конкретными датами определенные вехи в прогрессе общества. И этим грешил не только Советский Союз. США называли точную дату высадки экспедиции на Марс, а Япония провозглашала создание компьютера пятого поколения. Им должен был стать «эпохальный компьютер» с производительностью суперкомпьютера и мощными функциями искусственного интеллекта. Начало разработок — 1982 год, конец разработок — 1992 год, стоимость разработок — 57 млрд ? (порядка 500 млн $). Программа закончилась провалом. И сама программа, и причины ее провала давно проанализированы. По этому поводу проведено огромное количество исследований, написано немало научных и научно-популярных статей. Но все исследователи и аналитики единодушны в одном – проект обогнал время. В то время не было достаточной аппаратной, технологической и программной мощности, не было Интернета с его идеями параллелизации и распределенных процессов. Какие же задачи должен был решать компьютер пятого поколения? Ожидалось добиться существенного прорыва в области решения прикладных задач искусственного интеллекта. В частности, должны были быть решены следующие задачи: печатная машинка, работающая под диктовку; автоматический портативный переводчик с языка на язык (разумеется, непосредственно с голоса); автоматическое реферирование статей, поиск смысла и категоризация; другие задачи распознавания образов — поиск характерных признаков, дешифровка, анализ дефектов и т. п. Идея суперкомпьютера, наделенного искусственным интеллектом, базируется на воспроизведении в данном устройстве функций естественного интеллекта человека. А что есть интеллект? Это способность человека на основе знаний и жизненного опыта рассуждать, сопоставлять, думать, делать выводы и поступать согласно им (+ то, что мы называем интуицией). Средством реализации этих функций в теории информатики как раз и является логическое программирование. Проблемная область искусственного интеллекта. Типы задач, решаемых в области ИИ. Формализованное представление знаний о предметной области. Сущность и понятие. Омонимия, синонимия. Сущность – это объект произвольной природы, принадлежащий реальному или воображаемому (виртуальному) миру. К сущностям можно отнести предмет, свойство или атрибут, состояние, процесс, событие, оценку и т.п. Понятие – это класс сущностей, объединенных на основе каких-либо признаков. Понятия могут быть простыми и составными: - простое характеризуется именем, содержанием и объемом; - сложные образованы из простых при помощи некоторых правил. Для представления понятия в естественном языке используется слово или словосочетание, называемое именем. Одно и то же понятие может быть выражено разными именами. Например, булева алгебра и алгебра логики. Такая ситуация называется синонимией. Иногда одно и то же имя может обозначать совершенно разные понятия. Такая ситуация называется омонимией или полисемией. Любое понятие можно выразить в виде логической формулы, в которой элементы, образующие понятия, представлены предикатами и соединены логическими операциями конъюнкции, дизъюнкции и отрицания. При решении конкретной задачи необходимо выделить существенные признаки и связи понятий и игнорировать несущественные. Такой прием называется абстрагированием. Абстрагирование обеспечивает упорядочение, структуризацию и понимание информации о реальном мире. Поэтому методы абстракции широко используются в формальном описании предметной области. К основным типам абстрагирования понятий можно отнести агрегацию, обобщение, типизацию и ассоциацию. Модели представления знаний. Логическая и продукционная модели представления знаний. 2. Процедурные модели представления знаний. 2.1. Логическая модель. В основе логического способа представления знаний лежит идея описания знаний о предметной области в виде некоторого множества утверждений, выраженных в виде логических формул, и получение решения построением вывода в некоторой формальной (дедуктивной) системе. Логическая модель представления знаний обычно представляет собой совокупность правил, определяющих понятия и отношения между ними. 2.2. Продукционная модель. Продукционная модель представления знаний является развитием логических моделей в направлении эффективности представления и вывода знания. Продукция – это выражение, содержащее: 1) ядро, интерпретируемое фразой «Если А, то В» (A ® B), 2) имя продукции, с помощью которого продукция выделяется из множества продукций; 3) сферу применения, которая описывает предметную область или ситуацию; 4) условие применимости ядра продукции, т.е. предикат, в случае истинности которого активизируется ядро продукции; 5) постусловие, представляющее собой процедуру, которую следует выполнить после успешной реализации ядра. Модели представления знаний. Сетевая модель представления знаний. Модели представления знаний. 1. Декларативные модели представления знаний. 1.1. Семантическая модель представления знаний. Совокупность взаимосвязанных понятий образует семантическую сеть понятий. Эта сеть является концептуальной моделью предметной области. Обычно она состоит из понятий различных категорий: объектов, свойств, операций, событий и т. д. Связь между понятиями семантической сети выражает минимальный объем знаний, простейший факт, относящийся к двум понятиям. В каждый момент времени предметная область может быть представлена в виде совокупности сущностей, понятий и ситуаций, называемой состоянием предметной области. Любое изменение состояния связывается с некоторым событием в предметной области. Возникновению события способствует ситуация, которая складывается в определенный момент времени. События в системе делятся на характеризуемые и характеризующие (события-признаки). Модели представления знаний. Фреймовая модель представления знаний. 1.2. Фреймовая модель представления знаний. Фрейм – это некоторая структура для представления знаний, которая при ее заполнении соответствующими значениями превращается в описание конкретного факта, события или ситуации. Основа фреймовой модели – слот, который состоит из имени некоторого признака, значений этого признака и связи с другими слотами. Фрейм можно представить в виде таблицы. Поля этой таблицы являются слотами, а ее название трактуется как имя фрейма. В отличие от реляционной модели данных у таблицы фреймовой модели есть ряд особенностей: ? возможность смешанного заполнения слотов константами и переменными; ? возможность наличия пустых слотов; ? размещение в слотах указателей на другие фреймы для создания сети; ? размещение в слотах имен выполняемых процедур. Приобретение знаний. Методы получения знаний. Приобретением знаний называется выявление знаний из источников, преобразование их в нужную форму и перенос их в базу знаний интеллектуализированной информационной системы. Источниками знаний могут быть: а) формализованные знания об объектах: различные документы: книги, архивные документы, содержимое других баз знаний и т.п.; б) экспертные знания специалистов: субъективные, не зафиксированные во внешних хранилищах; в) эмпирические знания: субъективные, полученные опытным путем или путем наблюдения за окружающей средой. Схема приобретения знаний может быть представлена следующим образом: Носитель информации® Посредник® Модель знания Все методы приобретения знаний можно условно разбить на две большие группы: коммуникативные и текстологические. Рассмотрим методы приобретения знаний. Наблюдение. Анализ протоколов «мыслей вслух». Лекции. Анкетирование. Интервью. Свободный диалог. Игры с экспертом. Круглый стол. Мозговой штурм. Текстологические методы. Задачи компьютерной лингвистики. Уровни понимания текста. Интеллектуальные технологи. Нечеткая логика. Интеллектуальные технологи. Генетические алгоритмы. Интеллектуальные технологи. Нейронные сети. Экспертные системы. Общая характеристика экспертной системы. Области создания и применения экспертных систем. Общее представление об экспертных системах. В течение последних десятилетий в рамках исследований по искусственному интеллекту сформировалось самостоятельное направление – экспертные системы (ЭС), или инженерия знаний. В задачу этого направления входят исследование и разработка программ (устройств), использующих знания и процедуры вывода для решения задач, являющихся трудными для людей-экспертов. Особенно широкое распространение ЭС получили в проектировании интегральных микросхем, в поиске неисправностей, в военных приложениях и автоматизации программирования. ПРОграммирование в ЛОГике. Факты и правила. Запросы. В Прологе решение задачи получается логическим выводом из ранее известных положений. Программа на Прологе представляет собой набор фактов и правил, обеспечивающих получение заключений на основе этих фактов. Поэтому Пролог известен как декларативный язык. Пролог базируется на предложениях Хорна, являющихся подмножеством формальной системы, называемой логикой предикатов и использует упрощенную версию синтаксиса логики предикатов. Пролог включает механизм вывода, который основан на сопоставлении образцов. С помощью подбора ответов на запросы он извлекает хранящуюся (известную) информацию. Пролог пытается проверить истинность гипотезы (другими словами – ответить на вопрос), запрашивая для этого информацию, о которой уже известно, что она истинна. "Прологовское" знание о мире – это ограниченный набор фактов и правил, заданных в программе. 1.1 Факты и правила При составлении программы на языке Пролог необходимо описать объекты (objects) и отношения (relations), а затем – правила (rules), при условии соблюдения которых эти отношения являются истинными. Программа на языке Пролог состоит из предложений (clauses), которые могут быть отнесены к одному из двух типов фраз: факты и правила. Отношение в Прологе называется предикатом. Аргументы – это объекты, которые связываются этим отношением. Предикаты могут не иметь аргументов, но использование таких предикатов ограничено. Факты Отношение между объектами называется фактом. Факты –это отношения или свойства, о которых известно, что они имеют значение «истина». Факт самодостаточен. Прологу не требуется дополнительных сведений для подтверждения факта, и факт может быть использован как основа для логического вывода. Отношение состоит из имени отношения и объекта или объектов, заключенных в круглые скобки. Как и предложение, факт заканчивается точкой. Правила Правила позволяют вывести один факт из других фактов. Правило – это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Правила – это связанные отношения. Они позволяют Прологу логически выводить одну порцию информации из другой. Правило принимает значение «истина», если доказано, что заданный набор условий является истинным. Символ «: -» имеет смысл «если», и служит для разделения двух частей правила: заголовка и тела. В качестве предикатов, составляющих тело правила, могут выступать: предикаты, фигурирующие в базе фактов; предикаты, совпадающие с заголовком других правил; встроенные предикаты систем программирования Пролог . 1.2 Запросы (цели) Однократная запись фактов в программе позволяет нам задавать вопросы, касающиеся отношений между ними. Этот процесс называется запросом (query) системы языка Пролог. Пролог всегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты, пока они не закончатся. Запросы (цели) могут быть простыми или сложными. Сложными называются цели, состоящие из двух или более частей. А каждая часть сложной цели – подцелью. Возможно использование конъюнктивной и дизъюнктивной формы объединения подцелей. В качестве разделителей используются знаки «,» и «;» соответственно. Составные цели можно использовать для поиска решения, в котором: обе подцели A и B истинны (конъюнкция), разделяя подцели запятой; истинна либо подцель A , либо подцель B (дизъюнкция), разделяя подцели точкой с запятой. ПРОграммирование в ЛОГике. Переменные. Анонимные переменные. 1.3 Переменные Переменные в Прологе всегда начинаются с заглавной буквы или символа подчеркивания. Пролог не имеет оператора присваивания, но обеспечивает связывание переменной с конкретным значением при сопоставлении с константами в фактах или правилах. Переменные в Прологе инициализируются (или конкретизируются). До инициализации переменная свободна. После получения ею значения, она становится связанной. Конкретизация переменной обеспечивает возврат искомых значений переменных по запросам. Переменная остается связанной только то время, которое необходимо для получения решения по запросу. Затем Пролог освобождает ее и ищет другое решение. Нельзя сохранить информацию, присвоив значение переменной. Переменные используются как часть процесса поиска решения, а не как хранилище информации. Анонимные переменные Переменные данного вида используются в том случае, когда необходимо использовать не полную, а определенную информацию из запроса, проигнорировав ненужные значения. Обозначаются такие переменные символом подчеркивания и сопоставляются с любыми данными. 1.4 Комментарии Многострочные к омментарии должны начинаться с символов «/*» и заканчиваться символами «*/». Одно строчные комментарии можно начинать с символа «%». Программа на языке Пролог. Основные разделы программы. Стандартные домены.  Программа на языке Пролог. Предикаты и предложения. Предикаты разных арностей. 1. Предикат fail Предикат fail используется для инициализации поиска с возвратом. Предикат fail всегда неуспешен, т.е. он не может быть согласован. Поэтому, как только после согласования предыдущих предикатов Пролог обращается к предикату fail, осуществляется поиск с возвратом. При этом Пролог возвращается в ту точку программы, после которой возможны множественные решения. Такое обращение называется недетерминированным. В отличие от недетерминированного, детерминированное обращение может произвести только одно решение. Помещать подцель после fail в теле правила бесполезно, т.к. такая подцель никогда не будет достигнута. 2. Отсечение ( cut ) Отсечение cut (обозначается !) используется для запрета возможности возврата. Через отсечение невозможно совершить откат (поиск с возвратом). Отсечение применяется в одном из двух основных случаев: если заранее известно, что определенные посылки никогда не приведут к осмысленным решениям – это зеленое отсечение; если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей – это красное отсечение. Программа на языке Пролог. Унификация и сопоставление. Предикат not. Программа на языке Пролог. Поиск с возвратом. Основные правила поиска с возвратом. Основные правила поиска с возвратом Подцели должны быть согласованы по порядку, сверху вниз. Предикатные предложения проверяются в том порядке, в каком они появляются в программе, сверху вниз. Когда подцель соответствует заголовку правила, далее должно быть согласовано тело этого правила: тело правила теперь образует новое множество подцелей для согласования. Целевое утверждение является согласованным, когда соответствующий факт найден для каждой оконечности (листа) целевого дерева. При помощи поиска с возвратом в режиме Test Goal будут найдены все возможные решения задачи. Управление поиском решений В Прологе имеются два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: включение поиска с возвратом при его отсутствии, и отключение поиска с возвратом при его наличии. Программа на языке Пролог. Управление поиском решений. Предикат неудачи. Отсечения. Программа на языке Пролог. Арифметические выражения. Сравнения. Программа на языке Пролог. Простые и составные объекты. Функторы. Простой объект данных – это переменная или константа. Переменные Пролога локальны. Если два предложения содержат переменную, названную X, то это две различные переменные. Они могут быть связаны друг с другом, если совпадут во время унификации, но обычно они не оказывают влияния друг на друга. В Прологе переменная может быть связана с любым допустимым аргументом или объектом данных. Константы включают символы (char), числа (integer или real) и атомы (symbol или string). Символьные константы записываются в апострофах. Если перед константой стоит символ «\» (обратный слэш), то такая константа представляет собой специальную функцию. Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними заключается в машинном представлении и реализации и, в основном, синтаксически незаметно. Пролог автоматически преобразует типы между доменами symbol и string , поэтому можно использовать атомы symbol в доменах string и наоборот. Принято считать, что объект в двойных кавычках принадлежит домену string , а объект, не нуждающийся в кавычках, домену symbol . Составные объекты данных и функторы Составные объекты данных позволяют интерпретировать некоторые части информации как единое целое таким образом, чтобы затем можно было легко разделить их вновь. Функтор в языке Пролог – просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы. Функтор не обозначает, что будут выполнены какие-либо вычисления, и не имеет ничего общего с функциями в других языках программирования, кроме внешнего вида. Составные объекты состоят из функтора и объектов, принадлежащих этому функтору: functor ( object 1, object 2,…, objectN ). Составной объект можно унифицировать с простой переменной или с составным объектом, который ему соответствует. Это означает, что составной объект можно использовать для того, чтобы передавать целый набор значений как единый объект, и затем применять унификацию для их разделения. Аргументы составного объекта данных сами могут быть составными объектами. Правило декларирования доменов для составных объектов В разделе domains необходимо дать описание нового домена в виде: Nazvanie_domena = alternative1(D1 Name, D2 Name, …);alternative2(D3 Name, D4 Name, …);… alternative # – допустимые , но различные функторы; D# – стандартные, или объявленные в программе домены; Name – комментарии. Альтернативы разделяются точкой с запятой, при этом каждая альтернатива состоит из функтора и списка доменов соответствующих аргументов. Если функтор не имеет аргументов, то можно записать в программе alternativeN или alternativeN (). Программа на языке Пролог. Повтор и рекурсия. В языке Пролог не существует прямого способа выражения повтора. Здесь возможны только два вида повторения – откат, с помощью которого осуществляется поиск многих решений в одном запросе, и рекурсия, в которой процедура вызывает сама себя. блемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура), могла после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно. Стек на платформе DOS ограничен 64 Kb , на платформе Windows размеры стека не ограничены, но есть ряд других существенных проблем. В ряде специальных случаев процедура может вызывать себя без сохранения информации о своем состоянии. Допустим, что процедура A вызывает процедуру B, а B – C в качестве своего последнего шага. Когда B вызывает C, B не должна больше ничего делать. Поэтому, вместо того, чтобы сохранить в стеке информацию о текущем состоянии C , можно переписать старую сохраненную информацию о состоянии B на текущую информацию состоянии C . Когда C закончит выполнение, она будет считать, что она вызвана непосредственно процедурой A . С процедурной точки зрения данный процесс очень похож на всего лишь обновление управляющих переменных в цикле. Эта операция называется оптимизацией хвостовой рекурсии. Оптимизация хвостовой рекурсии нарушается, если: Рекурсивный вызов не является самым последним шагом процедуры; Имеются в наличии непроверенными к моменту выполнения рекурсивного вызова некоторые возможные альтернативы; К моменту выполнения рекурсивного вызова непроверенная альтернатива имеется в любом вызываемом предикате. Программа на языке Пролог. Списки. Определение списка. Печать списка. Программа на языке Пролог. Списки. Вычисления в списках. Редактирование списков. Программа на языке Пролог. Списки. Поиск всех решений для цели (предикат findall). Программа на языке Пролог. Списки. Принадлежность элемента списку. Добавление списка к списку. Программа на языке Пролог. Списки. Теоретико-множественные операции объединения и пересечения списков. Программа на языке Пролог. Списки. Генерация элементов списка случайным образом. Сортировка списка. Программа на языке Пролог. Организация циклов. Программа на языке Пролог. Деревья. Описание дерева. Программа на языке Пролог. Деревья. Обход дерева. Создание дерева. Программа на языке Пролог. Деревья. Бинарные поисковые деревья. Программа на языке Пролог. Внутренняя база фактов. Объявление ВБФ. Обновление ВБФ. Программа на языке Пролог. Внутренняя база фактов. Обмен данными между ВБФ и внешними файлами. |