Решение новых задач на основе опыта прошлых решений.

Введение

Процесс решения новых проблем на основе решений аналогичных прошлых проблем.

В искусственном интеллекте и философии рассуждение на основе прецедентов (CBR), в широком смысле, — это процесс решения новых проблем, опираясь на решения похожих задач из прошлого. В повседневной жизни автомеханик, который ремонтирует двигатель, вспоминая другую машину с аналогичными симптомами, использует рассуждение на основе прецедентов. Адвокат, отстаивающий определенный исход дела, опираясь на юридические прецеденты, или судья, создающий прецедентное право, также используют рассуждение на основе прецедентов. Инженер, копирующий эффективные элементы природы (занимающийся биомимикрией), рассматривает природу как базу данных решений проблем. Рассуждение на основе прецедентов — заметный тип решения задач посредством аналогии. Утверждается, что рассуждение на основе прецедентов — это не только мощный метод компьютерного рассуждения, но и широко распространенное поведение при решении повседневных задач человеком; или, более радикально, что все рассуждения основаны на лично пережитых прошлых случаях. Эта точка зрения связана с теорией прототипов, наиболее глубоко изучаемой в когнитивной науке.

Сравнение с другими методами

На первый взгляд, CBR может показаться похожим на алгоритмы индукции правил машинного обучения. Как и алгоритм индукции правил, CBR начинается с набора случаев или обучающих примеров; он формирует обобщения этих примеров, хотя и неявные, путем выявления общих черт между извлеченным случаем и целевой проблемой. Если, например, процедура приготовления обычных блинчиков применяется к блинчикам с черникой, принимается решение использовать тот же базовый рецепт теста и метод жарки, тем самым неявно обобщая набор ситуаций, в которых можно использовать этот рецепт теста и метод жарки. Однако ключевое различие между неявным обобщением в CBR и обобщением в индукции правил заключается во времени, когда это обобщение происходит. Алгоритм индукции правил формирует свои обобщения на основе набора обучающих примеров до того, как целевая проблема становится известной; то есть он выполняет немедленное обобщение. Например, если алгоритму индукции правил предоставить рецепты обычных блинчиков, голландских яблочных блинчиков и банановых блинчиков в качестве обучающих примеров, он должен вывести, в процессе обучения, набор общих правил для приготовления всех видов блинчиков. Только на этапе тестирования ему будет поставлена задача, скажем, приготовить блинчики с черникой. Сложность для алгоритма индукции правил заключается в предвидении различных направлений, в которых он должен попытаться обобщить свои обучающие примеры. Это контрастирует с CBR, который откладывает (неявное) обобщение своих случаев до этапа тестирования – стратегия ленивого обобщения. В примере с блинчиками, CBR уже поставлена задача приготовить блинчики с черникой; таким образом, он может обобщить свои случаи именно так, как это необходимо для решения этой задачи. Поэтому CBR, как правило, является хорошим подходом для богатых и сложных областей, в которых существует множество способов обобщения случая. В юриспруденции часто наблюдается явное делегирование CBR судам, признающее ограничения рассуждений, основанных на правилах: ограничение сроков, ограниченное знание будущего контекста, ограниченность достигнутых соглашений и т.д. Хотя CBR в юриспруденции и CBR, вдохновленный когнитивными науками, долгое время связаны, первый скорее представляет собой интерполяцию рассуждений и суждений, основанных на правилах, в то время как второй теснее связан с вспоминанием и адаптацией процессов. Разница очевидна в их отношении к ошибкам и апелляционному обзору. Другое название для рассуждений на основе случаев при решении проблем – симптоматические стратегии. Для этого требуются априорные знания, полученные из прошлого опыта, который установил связи между симптомами и причинами. Эти знания называют поверхностными, скомпилированными, основанными на доказательствах, историческими, а также знаниями, основанными на конкретных случаях. Эта стратегия наиболее тесно связана с диагностикой, выполняемой экспертами. Диагностика проблемы происходит как быстрый процесс распознавания, в котором симптомы вызывают соответствующие категории ситуаций. Эксперт знает причину, поскольку ранее сталкивался с подобными случаями. Рассуждения на основе случаев – наиболее мощная и часто используемая стратегия. Однако эта стратегия не будет работать самостоятельно с принципиально новыми проблемами или когда требуется более глубокое понимание происходящего. Альтернативный подход к решению проблем – топографическая стратегия, которая относится к категории глубоких рассуждений. При глубоких рассуждениях используются глубокие знания о системе. Топография в данном контексте означает описание или анализ структурированного объекта, показывающий взаимосвязи между его элементами. Также известное как рассуждение от первопричин, глубокое рассуждение применяется к новым неисправностям, когда подходы, основанные на опыте, нецелесообразны. Следовательно, топографическая стратегия связана с априорными знаниями в области, которые развиваются на основе более фундаментального понимания системы, возможно, с использованием знаний о первопричинах. Такие знания называют глубокими, причинными или основанными на моделях знаниями. Хок и Карлье отметили, что симптоматические подходы могут нуждаться в поддержке топографических подходов, поскольку симптомы могут быть определены различными способами. Обратное также верно – поверхностные рассуждения могут использоваться абдуктивно для генерации причинных гипотез и дедуктивно для оценки этих гипотез в рамках топографического поиска.

At first glance, CBR may seem similar to the rule induction algorithms of machine learning. Like a rule induction algorithm, CBR starts with a set of cases or training examples; it forms generalizations of these examples, albeit implicit ones, by identifying commonalities between a retrieved case and the target problem. If for instance a procedure for plain pancakes is mapped to blueberry pancakes, a decision is made to use the same basic batter and frying method, thus implicitly generalizing the set of situations under which the batter and frying method can be used. The key difference, however, between the implicit generalization in CBR and the generalization in rule induction lies in when the generalization is made. A rule induction algorithm draws its generalizations from a set of training examples before the target problem is even known; that is, it performs eager generalization. For instance, if a rule induction algorithm were given recipes for plain pancakes, Dutch apple pancakes, and banana pancakes as its training examples, it would have to derive, at training time, a set of general rules for making all types of pancakes. It would not be until testing time that it would be given, say, the task of cooking blueberry pancakes. The difficulty for the rule induction algorithm is in anticipating the different directions in which it should attempt to generalize its training examples. This is in contrast to CBR, which delays (implicit) generalization of its cases until testing time – a strategy of lazy generalization. In the pancake example, CBR has already been given the target problem of cooking blueberry pancakes; thus it can generalize its cases exactly as needed to cover this situation. CBR therefore tends to be a good approach for rich, complex domains in which there are myriad ways to generalize a case. In law, there is often explicit delegation of CBR to courts, recognizing the limits of rule based reasons: limiting delay, limited knowledge of future context, limit of negotiated agreement, etc. While CBR in law and cognitively inspired CBR have long been associated, the former is more clearly an interpolation of rule based reasoning, and judgment, while the latter is more closely tied to recall and process adaptation. The difference is clear in their attitude toward error and appellate review. Another name for cased based reasoning in problem solving is symptomatic strategies. It does require à priori domain knowledge that is gleaned from past experience which established connections between symptoms and causes. This knowledge is referred to as shallow, compiled, evidential, history based as well as case based knowledge. This is the strategy most associated with diagnosis by experts. Diagnosis of a problem transpires as a rapid recognition process in which symptoms evoke appropriate situation categories. An expert knows the cause by virtue of having previously encountered similar cases. Cased based reasoning is the most powerful strategy, and that used most commonly. However, the strategy won't work independently with truly novel problems, or where deeper understanding of whatever is taking place is sought. An alternative approach to problem solving is the topographic strategy which falls into the category of deep reasoning. With deep reasoning, in depth knowledge of a system is used. Topography in this context means a description or an analysis of a structured entity, showing the relations among its elements. Also known as reasoning from first principles, deep reasoning is applied to novel faults when experience based approaches aren't viable. The topographic strategy is therefore linked to à priori domain knowledge that is developed from a more a fundamental understanding of a system, possibly using first principles knowledge. Such knowledge is referred to as deep, causal or model based knowledge. Hoc and Carlier noted that symptomatic approaches may need to be supported by topographic approaches because symptoms can be defined in diverse terms. The converse is also true – shallow reasoning can be used abductively to generate causal hypotheses, and deductively to evaluate those hypotheses, in a topographical search.

Критика

Критики CBR утверждают, что это подход, который принимает отдельные случаи и непроверенные свидетельства в качестве основного принципа работы. Без статистически значимых данных в поддержку и неявного обобщения нет никакой гарантии, что обобщение верно. Однако все индуктивные рассуждения, когда данных недостаточно для статистической значимости, по своей сути основаны на доказательствах, полученных из отдельных случаев.

История

CBR берет свое начало в работах Роджера Шенка и его студентов в Йельском университете в начале 1980-х годов. Модель динамической памяти Шенка послужила основой для самых ранних систем CBR: CYRUS, разработанной Джанет Колоднер, и IPP Майкла Лебовица. В 1980-х годах возникли и другие направления CBR и тесно связанные с ними области, посвященные таким темам, как юридическое рассуждение, рассуждение на основе памяти (метод рассуждения на примерах с использованием массивно-параллельных машин) и комбинации CBR с другими методами рассуждения. В 1990-х годах интерес к CBR возрос в международном масштабе, что подтверждается проведением Международной конференции по рассуждению на основе конкретных случаев в 1995 году, а также европейских, немецких, британских, итальянских и других семинаров по CBR. Технология CBR привела к внедрению ряда успешных систем, первой из которых была CLAVIER от Lockheed – система для компоновки деталей перед выпечкой в промышленной конвекционной печи. CBR широко применялась в таких системах, как Compaq SMART, и нашла широкое применение в области здравоохранения, а также в управлении структурной безопасностью. В последнее время ведутся работы по развитию CBR в рамках статистического подхода и формализации вывода на основе случаев как специфического типа вероятностного вывода. Это позволяет создавать прогнозы на основе конкретных случаев с определенной степенью достоверности. Одно из описаний различий между CBR и индукцией из примеров заключается в том, что статистический вывод стремится выявить факторы, делающие случаи похожими, в то время как CBR направлена на кодирование условий, достаточных для установления их схожести.