Представление и рассуждения о знаниях в искусственном интеллекте.

Введение

Представление знаний и рассуждения (KRR, KR&R, KR²) – это область искусственного интеллекта (ИИ), посвященная представлению информации о мире в форме, которую компьютерная система может использовать для решения сложных задач, таких как диагностика медицинского состояния или ведение диалога на естественном языке. Представление знаний включает в себя достижения психологии, касающиеся того, как люди решают проблемы и представляют знания, с целью разработки формализмов, упрощающих проектирование и создание сложных систем. Представление знаний и рассуждения также использует достижения логики для автоматизации различных видов логических выводов. Примеры формализмов представления знаний включают семантические сети, фреймы, правила, логические программы и онтологии. Примеры автоматизированных механизмов рассуждения включают машины логического вывода, системы доказательства теорем, генераторы моделей и классификаторы.

История

Самые ранние работы в области компьютерного представления знаний были сосредоточены на общих решателях задач, таких как система General Problem Solver (GPS), разработанная Алленом Ньюэллом и Гербертом А. Саймоном в 1959 году, и Advice Taker, предложенный Джоном Маккарти также в 1959 году. GPS включал структуры данных для планирования и декомпозиции. Система начинала с цели, затем разлагала ее на подцели и приступала к разработке стратегий для достижения каждой подцели. Advisor Taker, с другой стороны, предложил использовать предикатное исчисление для представления здравого смысла. Многие из ранних подходов к представлению знаний в ИИ использовали графовые представления и семантические сети, подобные современным графам знаний. В таких подходах решение задач представляло собой форму обхода графа или поиска пути, как в алгоритме A*. Типичные приложения включали формирование планов для роботов и игры. Другие исследователи сосредоточились на разработке автоматических доказателей теорем для логики первого порядка, мотивированные использованием математической логики для формализации математики и автоматизации доказательства математических теорем. Важным шагом в этом направлении стала разработка метода резолюции Джоном Аланом Робинсоном. Тем временем Джон Маккарти и Пэт Хейс разработали ситуационное исчисление как логическое представление здравого смысла о законах причины и следствия. Корделл Грин, в свою очередь, показал, как формировать планы для роботов, применяя резолюцию к ситуационному исчислению, а также как использовать резолюцию для ответов на вопросы и автоматического программирования. В отличие от этого, исследователи из MIT отвергли парадигму унифицированной процедуры доказательства и выступали за процедурное встраивание знаний. Конфликт между использованием логических и процедурных представлений был разрешен в начале 1970-х годов с развитием логического программирования и Prolog, использующих SLD-разрешение для обработки Horn-клауз как процедур редукции целей. Раннее развитие логического программирования было в значительной степени европейским явлением. В Северной Америке исследователи ИИ, такие как Эд Файгенбаум и Фредерик Хейс Рот, выступали за представление знаний, специфичных для предметной области, а не рассуждений общего назначения. Эти усилия привели к когнитивной революции в психологии и к фазе ИИ, ориентированной на представление знаний, что привело к созданию экспертных систем в 1970-х и 80-х годах, продукционных систем, языков фреймов и т.д. Вместо общих решателей задач ИИ переключил свое внимание на экспертные системы, способные соответствовать человеческой компетенции в конкретной задаче, такой как медицинская диагностика. Экспертные системы дали нам терминологию, которая используется и сегодня: системы ИИ делятся на базу знаний, включающую факты и правила о проблемной области, и механизм логического вывода, который применяет знания из базы знаний для ответов на вопросы и решения проблем в этой области. В этих ранних системах факты в базе знаний, как правило, имели довольно плоскую структуру, по сути, представляя собой утверждения о значениях переменных, используемых правилами. Тем временем Марвин Минский разработал концепцию фрейма в середине 1970-х годов. Фрейм похож на класс объекта: это абстрактное описание категории, описывающее вещи в мире, проблемы и потенциальные решения. Фреймы первоначально использовались в системах, ориентированных на взаимодействие с человеком, например, для понимания естественного языка и социальных ситуаций, в которых различные ожидания по умолчанию, такие как заказ еды в ресторане, сужают пространство поиска и позволяют системе выбирать соответствующие ответы на динамические ситуации. Вскоре сообщества, работающие с фреймами, и исследователи, использующие правила, осознали синергию между своими подходами. Фреймы хорошо подходили для представления реального мира, описываемого как классы, подклассы, слоты (значения данных) с различными ограничениями на возможные значения. Правила хорошо подходили для представления и использования сложной логики, такой как процесс постановки медицинского диагноза. Были разработаны интегрированные системы, объединяющие фреймы и правила. Одной из самых мощных и известных была среда Knowledge Engineering Environment (KEE) 1983 года от Intellicorp. KEE имела полноценный механизм правил с прямым и обратным распространением. Она также имела полноценную базу знаний, основанную на фреймах, с триггерами, слотами (значениями данных), наследованием и передачей сообщений. Хотя передача сообщений возникла в объектно-ориентированном сообществе, а не в ИИ, она была быстро принята исследователями ИИ в таких средах, как KEE, и в операционных системах для машин Lisp от Symbolics, Xerox и Texas Instruments. Интеграция фреймов, правил и объектно-ориентированного программирования была значительно стимулирована коммерческими предприятиями, такими как KEE и Symbolics, выросшими из различных исследовательских проектов. В то же время существовала и другая линия исследований, менее ориентированная на коммерцию и движимая математической логикой и автоматическим доказательством теорем. Одним из самых влиятельных языков в этих исследованиях был язык KL-ONE середины 80-х годов. KL-ONE был языком фреймов с строгой семантикой и формальными определениями для таких понятий, как отношение "Is A". KL-ONE и языки, на него повлиявшие, такие как Loom, имели механизм логического вывода, основанный на формальной логике, а не на правилах "IF-THEN". Этот механизм вывода называется классификатором. Классификатор может анализировать набор деклараций и выводить новые утверждения, например, переопределять класс как подкласс или надкласс другого класса, который не был формально указан. Таким образом, классификатор может функционировать как механизм логического вывода, выводя новые факты из существующей базы знаний. Классификатор также может обеспечивать проверку согласованности базы знаний (которая в случае языков KL-ONE также называется онтологией). Другой областью исследований представления знаний была проблема здравого смысла. Одним из первых уроков, извлеченных из попыток создания программного обеспечения, способного функционировать с использованием естественного языка, было то, что люди регулярно опираются на обширную базу знаний о реальном мире, которую мы просто принимаем как должное, но которая совершенно не очевидна для искусственного агента. Основные принципы здравого смысла о физике, причинности, намерениях и т.д. Примером является проблема фрейма, заключающаяся в том, что в логике, управляемой событиями, должны быть аксиомы, утверждающие, что вещи сохраняют свое положение с одного момента времени на другой, если их не перемещает какая-либо внешняя сила. Чтобы создать настоящий искусственный интеллект, способный общаться с людьми на естественном языке и обрабатывать основные утверждения и вопросы о мире, необходимо представлять эти знания. Помимо ситуационного исчисления Маккарти и Хейса, одной из самых амбициозных программ по решению этой проблемы был проект Cyc Дуга Лената. Cyc разработал свой собственный язык фреймов и привлек большое количество аналитиков для документирования различных областей здравого смысла на этом языке. Знания, записанные в Cyc, включали модели здравого смысла времени, причинности, физики, намерений и многих других. Отправной точкой для представления знаний является гипотеза о представлении знаний, впервые формализованная Брайаном Смитом в 1985 году:

The earliest work in computerized knowledge representation was focused on general problem solvers such as the General Problem Solver (GPS) system developed by Allen Newell and Herbert A. Simon in 1959 and the Advice Taker proposed by John McCarthy also in 1959. GPS featured data structures for planning and decomposition. The system would begin with a goal. It would then decompose that goal into sub goals and then set out to construct strategies that could accomplish each subgoal. The Advisor Taker, on the other hand, proposed the use of the predicate calculus to represent common sense reasoning. Many of the early approaches to knowledge represention in AI used graph representations and semantic networks, similar to knowledge graphs today. In such approaches, problem solving was a form of graph traversal or path finding, as in the A* search algorithm. Typical applications included robot plan formation and game playing. Other researchers focused on developing automated theorem provers for first order logic, motivated by the use of mathematical logic to formalise mathematics and to automate the proof of mathematical theorems. A major step in this direction was the development of the resolution method by John Alan Robinson. In the meanwhile, John McCarthy and Pat Hayes developed the situation calculus as a logical representation of common sense knowledge about the laws of cause and effect. Cordell Green, in turn, showed how to do robot plan formation by applying resolution to the situation calculus. He also showed how to use resolution for question answering and automatic programming. In contrast, researchers at MIT rejected the resolution uniform proof procedure paradigm and advocated the procedural embedding of knowledge instead. The resulting conflict between the use of logical representations and the use of procedural representations was resolved in the early 1970s with the development of logic programming and Prolog, using SLD resolution to treat Horn clauses as goal reduction procedures. The early development of logic programming was largely a European phenomenon. In North America, AI researchers such as Ed Feigenbaum and Frederick Hayes Roth advocated the representation of domain specific knowledge rather than general purpose reasoning. These efforts led to the cognitive revolution in psychology and to the phase of AI focused on knowledge representation that resulted in expert systems in the 1970s and 80s, production systems, frame languages, etc. Rather than general problem solvers, AI changed its focus to expert systems that could match human competence on a specific task, such as medical diagnosis. Expert systems gave us the terminology still in use today where AI systems are divided into a knowledge base, which includes facts and rules about a problem domain, and an inference engine, which applies the knowledge in the knowledge base to answer questions and solve problems in the domain. In these early systems the facts in the knowledge base tended to be a fairly flat structure, essentially assertions about the values of variables used by the rules. Meanwhile, Marvin Minsky developed the concept of frame in the mid 1970s. A frame is similar to an object class: It is an abstract description of a category describing things in the world, problems, and potential solutions. Frames were originally used on systems geared toward human interaction, e. g. understanding natural language and the social settings in which various default expectations such as ordering food in a restaurant narrow the search space and allow the system to choose appropriate responses to dynamic situations. It was not long before the frame communities and the rule based researchers realized that there was a synergy between their approaches. Frames were good for representing the real world, described as classes, subclasses, slots (data values) with various constraints on possible values. Rules were good for representing and utilizing complex logic such as the process to make a medical diagnosis. Integrated systems were developed that combined frames and rules. One of the most powerful and well known was the 1983 Knowledge Engineering Environment (KEE) from Intellicorp. KEE had a complete rule engine with forward and backward chaining. It also had a complete frame based knowledge base with triggers, slots (data values), inheritance, and message passing. Although message passing originated in the object oriented community rather than AI it was quickly embraced by AI researchers as well in environments such as KEE and in the operating systems for Lisp machines from Symbolics, Xerox, and Texas Instruments. The integration of frames, rules, and object oriented programming was significantly driven by commercial ventures such as KEE and Symbolics spun off from various research projects. At the same time, there was another strain of research that was less commercially focused and was driven by mathematical logic and automated theorem proving. One of the most influential languages in this research was the KL ONE language of the mid '80s. KL ONE was a frame language that had a rigorous semantics, formal definitions for concepts such as an Is A relation. KL ONE and languages that were influenced by it such as Loom had an automated reasoning engine that was based on formal logic rather than on IF THEN rules. This reasoner is called the classifier. A classifier can analyze a set of declarations and infer new assertions, for example, redefine a class to be a subclass or superclass of some other class that wasn't formally specified. In this way the classifier can function as an inference engine, deducing new facts from an existing knowledge base. The classifier can also provide consistency checking on a knowledge base (which in the case of KL ONE languages is also referred to as an Ontology). Another area of knowledge representation research was the problem of common sense reasoning. One of the first realizations learned from trying to make software that can function with human natural language was that humans regularly draw on an extensive foundation of knowledge about the real world that we simply take for granted but that is not at all obvious to an artificial agent. Basic principles of common sense physics, causality, intentions, etc. An example is the frame problem, that in an event driven logic there need to be axioms that state things maintain position from one moment to the next unless they are moved by some external force. In order to make a true artificial intelligence agent that can converse with humans using natural language and can process basic statements and questions about the world, it is essential to represent this kind of knowledge. In addition to McCarthy and Hayes' situation calculus, one of the most ambitious programs to tackle this problem was Doug Lenat's Cyc project. Cyc established its own Frame language and had large numbers of analysts document various areas of common sense reasoning in that language. The knowledge recorded in Cyc included common sense models of time, causality, physics, intentions, and many others. The starting point for knowledge representation is the knowledge representation hypothesis first formalized by Brian C. Smith in 1985:

Любой механически воплощенный интеллектуальный процесс будет иметь структурные ингредиенты, которые а) мы, как внешние наблюдатели, естественно воспринимаем как пропорциональный учет знаний, которыми обладает весь процесс, и b) независимо от такой внешней семантической атрибуции, играют формальную, но причинную и существенную роль в порождении поведения, которое проявляет эти знания. Одной из наиболее активных областей исследований представления знаний является Semantic Web. Semantic Web стремится добавить слой семантики (значения) поверх существующего Интернета. Вместо индексации веб-сайтов и страниц по ключевым словам Semantic Web создает большие онтологии понятий. Поиск понятия будет более эффективным, чем традиционный...

Онтологическая инженерия

В первые годы развития систем, основанных на знаниях, базы знаний были относительно небольшими. Базы знаний, предназначенные для решения реальных задач, а не для демонстрации концепций, должны были фокусироваться на чётко определённых проблемах. Например, не медицинская диагностика в целом, а диагностика определённых видов заболеваний. По мере масштабирования технологий, основанных на знаниях, стала очевидной потребность в более крупных и модульных базах знаний, способных взаимодействовать и интегрироваться друг с другом. Это привело к возникновению дисциплины онтологической инженерии – проектированию и созданию больших баз знаний, которые могли бы использоваться в нескольких проектах. Одним из ведущих исследовательских проектов в этой области был проект Cyc. Cyc представлял собой попытку создать огромную энциклопедическую базу знаний, содержащую не только экспертные знания, но и знания здравого смысла. При разработке агента искусственного интеллекта вскоре стало понятно, что представление знаний здравого смысла, знаний, которые люди принимают как должное, необходимо для создания ИИ, способного взаимодействовать с людьми на естественном языке. Cyc был призван решить эту проблему. Язык, который они разработали, получил название CycL. После CycL было разработано множество онтологических языков. Большинство из них являются декларативными, и либо языками фреймов, либо основаны на логике первого порядка. Модульность – способность определять границы для конкретных областей и проблемных пространств – имеет важное значение для этих языков, поскольку, как отмечал Том Грубер, «каждая онтология – это договор, социальное соглашение между людьми, объединёнными общей целью обмена знаниями». Всегда существует множество конкурирующих и различных точек зрения, что делает создание онтологии общего назначения невозможным. Онтология общего назначения должна быть применима в любой области, а различные области знаний должны быть унифицированы. Существует длительная история попыток создания онтологий для различных предметных областей, например, онтология для жидкостей, широко используемая модель сосредоточенных элементов для представления электронных схем (например), а также онтологии для времени, убеждений и даже самого программирования. Каждая из них предлагает способ взглянуть на определённую часть мира. Например, модель сосредоточенных элементов предполагает, что мы рассматриваем схемы с точки зрения компонентов, соединённых между собой, с сигналами, мгновенно распространяющимися по соединениям. Это полезный взгляд, но не единственный возможный. Другая онтология возникает, если необходимо учитывать электродинамику в устройстве: здесь сигналы распространяются с конечной скоростью, и объект (например, резистор), который ранее рассматривался как единый компонент с входными и выходными характеристиками, теперь может рассматриваться как расширенная среда, через которую распространяется электромагнитная волна. Онтологии, конечно, могут быть записаны на самых разных языках и в различных форматах (например, логика, LISP и т. д.); существенной информацией является не форма языка, а его содержание, то есть набор концепций, предлагаемых как способ мышления о мире. Проще говоря, важны такие понятия, как связи и компоненты, а не выбор между их представлением в виде предикатов или конструкций LISP. Выбор той или иной онтологии может привести к принципиально иному взгляду на задачу. Рассмотрим разницу, возникающую при выборе модели сосредоточенных элементов для схемы по сравнению с электродинамической моделью того же устройства. В качестве второго примера, медицинская диагностика, рассматриваемая с точки зрения правил (например, MYCIN), существенно отличается от той же задачи, рассматриваемой с точки зрения фреймов (например, INTERNIST). В то время как MYCIN рассматривает медицинский мир как состоящий из эмпирических ассоциаций, связывающих симптомы с заболеваниями, INTERNIST видит набор прототипов, в частности, прототипических заболеваний, которые необходимо сопоставить с конкретным случаем.

In the early years of knowledge based systems the knowledge bases were fairly small. The knowledge bases that were meant to actually solve real problems rather than do proof of concept demonstrations needed to focus on well defined problems. So for example, not just medical diagnosis as a whole topic, but medical diagnosis of certain kinds of diseases. As knowledge based technology scaled up, the need for larger knowledge bases and for modular knowledge bases that could communicate and integrate with each other became apparent. This gave rise to the discipline of ontology engineering, designing and building large knowledge bases that could be used by multiple projects. One of the leading research projects in this area was the Cyc project. Cyc was an attempt to build a huge encyclopedic knowledge base that would contain not just expert knowledge but common sense knowledge. In designing an artificial intelligence agent, it was soon realized that representing common sense knowledge, knowledge that humans simply take for granted, was essential to make an AI that could interact with humans using natural language. Cyc was meant to address this problem. The language they defined was known as CycL. After CycL, a number of ontology languages have been developed. Most are declarative languages, and are either frame languages, or are based on first order logic. Modularity—the ability to define boundaries around specific domains and problem spaces—is essential for these languages because as stated by Tom Gruber, "Every ontology is a treaty a social agreement among people with common motive in sharing." There are always many competing and differing views that make any general purpose ontology impossible. A general purpose ontology would have to be applicable in any domain and different areas of knowledge need to be unified. There is a long history of work attempting to build ontologies for a variety of task domains, e. g., an ontology for liquids, the lumped element model widely used in representing electronic circuits (e. g.,), as well as ontologies for time, belief, and even programming itself. Each of these offers a way to see some part of the world. The lumped element model, for instance, suggests that we think of circuits in terms of components with connections between them, with signals flowing instantaneously along the connections. This is a useful view, but not the only possible one. A different ontology arises if we need to attend to the electrodynamics in the device: Here signals propagate at finite speed and an object (like a resistor) that was previously viewed as a single component with an I/O behavior may now have to be thought of as an extended medium through which an electromagnetic wave flows. Ontologies can of course be written down in a wide variety of languages and notations (e. g., logic, LISP, etc. ); the essential information is not the form of that language but the content, i. e., the set of concepts offered as a way of thinking about the world. Simply put, the important part is notions like connections and components, not the choice between writing them as predicates or LISP constructs. The commitment made selecting one or another ontology can produce a sharply different view of the task at hand. Consider the difference that arises in selecting the lumped element view of a circuit rather than the electrodynamic view of the same device. As a second example, medical diagnosis viewed in terms of rules (e. g., MYCIN) looks substantially different from the same task viewed in terms of frames (e. g., INTERNIST). Where MYCIN sees the medical world as made up of empirical associations connecting symptom to disease, INTERNIST sees a set of prototypes, in particular prototypical diseases, to be matched against the case at hand.