В области искусственного интеллекта машина вывода — это программный компонент интеллектуальной системы, который применяет логические правила к базе знаний для вывода новой информации. Первые машины вывода были компонентами экспертных систем . Типичная экспертная система состояла из базы знаний и машины вывода. База знаний хранила факты о мире. Машина вывода применяла логические правила к базе знаний и выводила новые знания. Этот процесс повторялся, поскольку каждый новый факт в базе знаний мог вызывать дополнительные правила в машине вывода. Машины вывода работают в основном в одном из двух режимов: либо специальное правило, либо факты: прямая цепочка и обратная цепочка . Прямая цепочка начинается с известных фактов и утверждает новые факты. Обратная цепочка начинается с целей и работает в обратном направлении, чтобы определить, какие факты должны быть утверждены, чтобы цели могли быть достигнуты. [1]
Кроме того, понятие «вывод» расширилось и теперь включает в себя процесс, посредством которого обученные нейронные сети генерируют прогнозы или решения. В этом контексте «машина вывода» может относиться к определенной части системы или даже к оборудованию, которое выполняет эти операции. Этот тип вывода играет решающую роль в различных приложениях, включая (но не ограничиваясь) распознавание изображений , обработку естественного языка и автономные транспортные средства . Фаза вывода в этих приложениях обычно характеризуется большим объемом входных данных и требованиями к обработке в реальном времени.
Логика, которую использует машина вывода, обычно представлена в виде правил ЕСЛИ-ТО. Общий формат таких правил — ЕСЛИ <логическое выражение> ТО <логическое выражение>. До разработки экспертных систем и машин вывода исследователи искусственного интеллекта сосредоточились на более мощных средах доказательства теорем , которые предлагали гораздо более полные реализации логики первого порядка . Например, общие утверждения, которые включали универсальную квантификацию (для всех X некоторое утверждение истинно) и экзистенциальную квантификацию (существует некоторое X такое, что некоторое утверждение истинно). Исследователи обнаружили, что сила этих сред доказательства теорем была также их недостатком. Еще в 1965 году было слишком легко создавать логические выражения, которые могли занять неопределенное или даже бесконечное время для завершения. Например, в универсальной квантификации принято делать утверждения над бесконечным множеством, таким как множество всех натуральных чисел. Такие утверждения совершенно разумны и даже требуются в математических доказательствах, но при включении в автоматизированную машину доказательства теорем, работающую на компьютере, это может привести к тому, что компьютер попадет в бесконечный цикл. Сосредоточение на утверждениях IF-THEN (то, что логики называют modus ponens ) все еще давало разработчикам очень мощный общий механизм для представления логики, но такой, который можно было бы эффективно использовать с вычислительными ресурсами. Более того, есть некоторые психологические исследования, которые указывают, что люди также склонны отдавать предпочтение представлениям IF-THEN при хранении сложных знаний. [2]
Простой пример modus ponens, часто используемый в вводных книгах по логике, — «Если ты человек, то ты смертен». Это можно представить в псевдокоде так:
Правило 1: Человек(x) => Смертный(x)
Вот тривиальный пример того, как это правило будет использоваться в машине вывода. В прямой цепочке машина вывода найдет любые факты в базе знаний, которые соответствуют Human(x), и для каждого найденного факта добавит новую информацию Mortal(x) в базу знаний. Таким образом, если она найдет объект с именем Socrates, который является человеком, она выведет, что Сократ был смертен. В обратной цепочке системе будет дана цель, например, ответить на вопрос, смертен ли Сократ? Она будет искать в базе знаний и определять, был ли Сократ человеком, и, если да, утверждать, что он также смертен. Однако в обратной цепочке распространенной техникой была интеграция машины вывода с пользовательским интерфейсом. Таким образом, вместо того, чтобы быть просто автоматизированной, система теперь могла быть интерактивной. В этом тривиальном примере, если системе была дана цель ответить на вопрос, смертен ли Сократ, и она еще не знала, был ли он человеком, она сгенерирует окно, чтобы задать пользователю вопрос «Является ли Сократ человеком?» и затем использовал бы эту информацию соответствующим образом.
Это нововведение интеграции механизма вывода с пользовательским интерфейсом привело ко второму раннему продвижению экспертных систем: возможностям объяснения. Явное представление знаний в виде правил, а не кода, позволило генерировать объяснения для пользователей: как объяснения в реальном времени, так и постфактум. Так что если система спросила пользователя «Сократ — человек?», пользователь мог задаться вопросом, почему ему задали этот вопрос, и система использовала бы цепочку правил, чтобы объяснить, почему она в данный момент пытается установить эту часть знания: то есть ей нужно определить, смертен ли Сократ, а для этого нужно определить, человек ли он. Сначала эти объяснения не сильно отличались от стандартной отладочной информации, с которой разработчики имеют дело при отладке любой системы. Однако активной областью исследований было использование технологии естественного языка для того, чтобы задавать, понимать и генерировать вопросы и объяснения с использованием естественных языков, а не компьютерных формализмов. [3]
Механизм вывода циклически проходит три последовательных шага: сопоставление правил , выбор правил и выполнение правил . Выполнение правил часто приводит к добавлению новых фактов или целей в базу знаний, что запускает повторение цикла. Этот цикл продолжается до тех пор, пока не будет найдено ни одного нового правила.
На первом этапе, match rules , механизм вывода находит все правила, которые запускаются текущим содержимым базы знаний. В прямой цепочке механизм ищет правила, в которых антецедент (левая часть) соответствует некоторому факту в базе знаний. В обратной цепочке механизм ищет антецеденты, которые могут удовлетворить одну из текущих целей.
На втором этапе, select rules , механизм вывода устанавливает приоритеты для различных сопоставленных правил, чтобы определить порядок их выполнения. На последнем этапе, execute rules , механизм выполняет каждое сопоставленное правило в порядке, определенном на втором этапе, а затем снова возвращается к первому этапу. Цикл продолжается до тех пор, пока не будут сопоставлены новые правила. [4]
Ранние механизмы вывода были сосредоточены в основном на прямом выводе. Эти системы обычно реализовывались на языке программирования Lisp . Lisp часто использовался в качестве платформы для ранних исследований ИИ из-за его мощных возможностей для символической манипуляции. Кроме того, как интерпретируемый язык, он предлагал продуктивные среды разработки, подходящие для отладки сложных программ. Неизбежным следствием этих преимуществ было то, что программы на Lisp, как правило, были медленнее и менее надежными, чем компилируемые языки того времени, такие как C. Распространенным подходом в те ранние дни было взять приложение экспертной системы и переупаковать механизм вывода, используемый для этой системы, в качестве повторно используемого инструмента, который другие исследователи могли бы использовать для разработки других экспертных систем. Например, MYCIN была ранней экспертной системой для медицинской диагностики, а EMYCIN была механизмом вывода, экстраполированным из MYCIN и предоставленным другим исследователям. [1]
По мере того, как экспертные системы переходили от исследовательских прототипов к развернутым системам, все больше внимания уделялось таким вопросам, как скорость и надежность. Одним из первых и самых популярных движков прямой цепочки был OPS5 , который использовал алгоритм Rete для оптимизации эффективности срабатывания правил. Другой очень популярной технологией, которая была разработана, был язык логического программирования Prolog . Prolog в первую очередь фокусировался на обратной цепочке, а также имел различные коммерческие версии и оптимизации для эффективности и надежности. [5]
Поскольку экспертные системы вызвали значительный интерес со стороны делового мира, различные компании, многие из которых были созданы или руководимы выдающимися исследователями ИИ, создали товарные версии механизмов вывода. Например, Intellicorp изначально руководил Эдвард Фейгенбаум . Эти продукты механизмов вывода также часто разрабатывались на Lisp поначалу. Однако спрос на более доступные и коммерчески жизнеспособные платформы в конечном итоге сделал платформы персональных компьютеров очень популярными.
ClipsRules и RefPerSys (вдохновленные CAIA [6] и работой Жака Питрата ). Статический анализатор исходного кода Frama-C также использует некоторые методы механизма вывода.