Case-based Reasoning

 

........ 사례기반 추론 (Case-based reasoning) 은 귀납법 (Induction)유추 (Analogy) 와 유사한 개념이다. ........

광범위하게 해석하면, Case-based reasoning (CBR) 은 유사한 과거 문제의 해결에 기초해서 새로운 문제를 해결하는 과정이다. 자동차 정비사가 차를 수리할때 유사한 증상을 보였던 자동차를 회상하여 (recall) 해결을 시도하는 것은 Case-based reasoning 를 사용하고 있는 것이다. 법적 판례 (precedents) 에 기초해서 재판에 임하는 변호사나 case law 를 창조하려는 판사는 Case-based reasoning 를 사용하고 있는 것이다. 마찬가지로, 자연의 요소들의 작동을 복사하려는 (생물모방 (biomimicry)) 엔지니어는 자연을 문제해결을 위한 데이타베이스로서 취급하고 있는 것이다.

paper

Case-based reasoning 은 컴퓨터추론을 위한 강력한 방법일 뿐만 아니라, 일상의 인간의 문제해결에 널리 사용되는 하나의 행동이라고 주장되어 왔다. 더 심하게 표현하면, 인지과학 (Cognitive Science) 에서 인간을 깊이있게 탐구할때의 원형이론 (prototype theory), 즉 모든 추론 (Reasoning) 은 과거에 경험한 것 또는 열심히 연습해서 받아들여진 과거의 사례에 기초해서 이루어진다는 것이다 .

Case-based reasoning 이 컴퓨터추론 목적으로 형식화될때는 다음의 4 단계 과정을 거친다.

  1. 검색 (Retrieve) : 대상 문제 (target problem) 가 주어지면, 메모리에서 그것을 풀기에 적절한 사례들을 검색한다. 하나의 사례 (case) 는 문제와 그 해 그리고 그 해가 어떻게 유도되었는지에 대한 설명 등으로 구성된다. 예를들어 철수가 딸기 케익를 만들려고 준비한다고 가정하자. 초보 요리사로서 그가 회상할 수 있는 가장 적절한 경험은 그가 쉬운 케익을 성공적으로 만들었던 것이다. 그가 그 케익을 만들었던 과정이, 의사결정을 통해 판결이 이루어지는 것과 같이, 철수가 검색한 사례 (case) 가 되는 것이다.
  2. 재사용 (Reuse) : 이전의 사례로부터 대상문제의 해를 연결한다 (map). 이것은 새로운 상황에 맞추기위해 필요한 만큼 해를 적응시키는 (adapting) 것을 포함한다. 케익 예에서, 철수는 그가 검색한 해법에 딸기를 추가한 것을 포함시켜 적응해야 한다.
  3. 수정 (Revise) : 이전의 해법을 대상의 상황에 연결시킨후, 그 새로운 해법을 실세계에서 (또는 simulation 에서) 테스트하고, 필요하다면 수정한다. 철수가 밀가루반죽에 딸기를 첨가하여 케익 해법을 적응시켰다고 가정하자. 물에 섞은 후에 그는 그 반죽이 적색으로 바뀌는 바람직하지 않은 결과가 생기는 것을 발견한다. 이것은 다음의 수정을 하게 만든다 : 즉 반죽을 후라이팬에 퍼낸후에야 딸기를 첨가한다는 것이다.
  4. 유지 (Retain) : 해법이 성공적으로 대상문제에 적용된 후에, 그러한 새로운 경험이 메모리에 새로운 사례로서 저장된다. 따라서 철수는 그가 딸기 케익을 만드는 과정에서 새로이 발견한 것을 기록하고, 그럼으로써 축적된 경험이 많아지고, 앞으로 케익을 만들때에는 더 잘 준비하게 될것이다.

대강 보면, CBR 은 기계학습 (Machine Learning) 의 rule-induction algorithm 과 유사하게 보일수 있다. rule-induction algorithm 처럼, CBR 은 일련의 사례 (case) 또는 훈련예 (training example) 를 가지고 시작한다 ; 검색된 사례와 대상 문제 (target problem) 의 공통점을 인식함으로써, 비록 암묵적인 (implicit) 것이라도, 이러한 예들을 일반화한다.

예를들면 철수가 쉬운 케익을 만드는 과정을 딸기 케익에 연결시킬때 (mapped), 똑같이 기본적인 반죽해서 굽는 방법 (batter and frying method) 을 사용하기로 결정했다면, 그러한 쉬운 케익을 만드는 상황에서는 그러한 방법이 사용될수 있다는 것을 암묵적으로 일반화 한다. 그러나 CBR 에서의 암묵적인 일반화 (implicit generalization) 와 rule induction 에서의 일반화 간의 핵심적인 차이는, 일반화가 이루어질때 발생한다. rule-induction algorithm 은 대상문제 (target problem) 를 알기도 전에 일련의 훈련예 로부터 일반화를 이끌어낸다 ; 즉 강렬한 (eager) 일반화를 수행한다. 예를들면, 만일 rule-induction algorithm 으로 쉬운 케익을 만드는 조리법을 이끌어 낸다면, 애플 케익과 바나나 케익 같은 것이 훈련예로 주어지고, 훈련할때에 (training time) 모든 종류의 케익을 만드는 일반적인 규칙을 유도해 낼것이다. 말하자면 딸기 케익을 조리하는 작업이 주어지는 testing time 에 일반화가 이루어지는 것이 아니라는 것이다.

rule-induction algorithm 의 어려움은 그 훈련예를 일반화 하는것이 예상과는 다른 방향으로 시도될때 발생한다. 이것은 CBR 과 대조적인 것으로, CBR 에서는 대상문제에 대한 testing time 때까지 그 사례들의 (암묵적인) 일반화를 지연시킨다 - 이것은 늦은 일반화 전략 (strategy of lazy generalization) 이라 한다. 케익 예에서, CBR 은 딸기 케익을 조리한다고 하는 대상 문제가 이미 주어졌다 ; 따라서 이러한 상황을 적용하기 위해 필요한 대로 정확하게 그 사례들을 일반화 할수 있다. 따라서 CBR 은 하나의 사례를 일반화 하는 무수히 많은 방법이 있는 복잡한 영역에서는 훌륭한 접근방법인 것이다.  

CBR 은 1980 년대 초에 Yale 대학에서 Roger Schank 와 그의 제자들의 작업에서 기원한다. Schank 의 dynamic memory 는 최초의 CBR 시스템들 즉 Janet Kolodner 의 CYRUS 와 Michael Lebowitz 의 IPP 의 기초가 되었다. 법률추론에서의 CBR 과 같이,  memory-based reasoning (대용량 병렬머신에서 예 (examples) 들로부터 추론하는 방법), CBR 과 다른 추론방법의 조합, 등등의  CBR 의 분파 또는 밀접한 분야가 1980 년대에 등장하였다.

1990 년대에 CBR 에 대한 국제적 관심이 늘어 1995 년에 International Conference on Case-Based Reasoning (ICCBR) 이 설립되었다. CBR 기술은  가장 초기의 Lockheed 의 CLAVIER (산업용 오븐에 굽기위해 복잡한 부분을 레이아웃 하는 시스템) 과 같은 많은 성공적인 시스템들이 출시되었다. CBR 은 Compaq SMART 시스템과 같은 help-desk 응용에서 광범위하게 사용되어 왔다. CBR 의사결정 지원 툴들이 상업적으로 이용가능한데, eGain (이전의 Inference Corporation) 의 k-Commerce 와 Kaidara (이전의 AcknoSoft) 의 Kaidara Advisor 등이 있다. ..... (Wikipedia : Case-based reasoning)

법관이 지난 사건에 대한 판례 (Case) 를 통해 당면한 사건에 대해 판단을 내리듯이, 인간은 과거의 사례나 경험에 비추어 현재의 문제를 인식하고 유형화하여 해결책을 내놓을 수 있다. 이를 위해서는 현재의 당면문제가 과거에 나타났던 사례나 경험과 일치하는지 여부를 살피고 일치하면 과거의 해결책에 비추어 답을 낸다. 만약 정확히 일치하지 않더라도 과거의 사례나 경험은 현재의 문제에 부분적인 해결책을 제시할 수 있다. 사례기반 추론은 이러한 인간의 지적 활동을 모델화한 것으로, 과거문제로부터 얻은 상황 경험이나 지식을 사례 데이터베이스로 구축하여 어떠한 상황이나 문제가 발생하면 기존의 사례 데이터베이스에서 가장 똑같거나 또는 가장 유사한 사례를 선택하여 그 사례가 제시하는 해결책으로 현 문제에 대한 답을 제시한다 ..... (이재규 1996)

term :

사례기반 추론 (Case Based Reasoning)    학습 (Learning)   사례에 의한 학습 (Learning from Examples)   추론 (Reasoning)   의사결정 트리 (Decision Tree)   유전알고리즘 (Genetic Algorithm)   Pattern matching

site :

Wikipedia : Case-based reasoning    위키백과 : 사례기반추론

AI Topics : Case-Based Reasoning     AI Topics : Memory-Based Learning

Case-Based Reasoning Resources : David W. Aha

International Conference on Case-Based Reasoning (ICCBR)

video :

CBR for Game AI : GoogleTechTalks : Ashwin Ram, 20008/04/03