Heuristic 이란 무엇인가?

 

컴퓨터과학에서는  두가지 근본적인 목표가 있는데, 그것은 증명가능하면서도 좋은 실행시간 (runtime) 을 가지는 알고리즘을 찾는것이며 또한 증명가능하면서도 (보통은 최적인) 좋은 질의 해 (solution quality) 를 가지는 알고리즘을 찾는것이다. 휴리스틱은 이러한 목표중의 하나 또는 둘 모두를 포기하는 알고리즘이다. 즉 예를들면 휴리스틱은 보통 아주 좋은 해를 찾지만 그것이 임의로 나쁜 해를 찾지 않는다는 것에 대한 증명은 없다. 또한 휴리스틱은 보통 합리적인 실행 시간을 가지지만 그것이 항상 그렇다는 어떠한 추론과정도 없다.

특별히 어려운 문제의 경우에 가끔 휴리스틱이 실제로 나쁜 결과를 낳고 매우 느리게 실행하는 경우가 있을 수 있다. 그러나 이러한 경우는 그 특별한 구조때문이지 실제로는 결코 발생하지 않을 것이다. 그러므로 휴리스틱의 사용은 실세계 에서는 매우 흔하게 발생한다.

Shortest-path problem 에서의 휴리스틱

Shortest-path problem 의 경우에 휴리스틱은 많은 특별한 의미를 갖는다. 그 문제의 경우 휴리스틱은 탐색트리의 노드에 정의된 함수 h(n) 로서 그 노드에서 목표 노드까지의 가장 비용이 적게드는 경로를 찾아 그 비용을 추정하는데 사용한다. 휴리스틱은 탐색하기에 가장 좋은 노드를 선택하기 위해 Greedy best-first search and A* 같은 informed search algorithm 에 사용된다. Greedy best-first search 는 휴리스틱 함수가 가장 값싼 비용을 가지는 노드를 선택할 것이다.  A* 는 g(n) + h(n) 이 가장 값싼 비용을 가지는 노드를 확장할 것이다. 여기서 g(n) 은 최초의 상태에서 현재 노드까지의 경로의 정확한 (exact) 비용이다. 여기서 h(n) 이 받아들일만 하다면 (즉 h(n) 이 목표에 이르는 비용을 결코 과장되게 추정하지 않는다면) A* 는 최적 (optimal) 이라고 증명될수 있다.

휴리스틱을 포함하는 전통적인 문제는 n-puzzle 이다. 이 문제에 흔히 사용되는 휴리스틱은 위치가 틀린 tiles 갯수를 세는것과 각 block 간의 Manhattan distances 의 합과 목표 상황에서의 그 위치를 찾는것이다. 둘다 허용가능하다 (admissible) 는 것을 주목하라.

Computational performance 에서의 휴리스틱의 효과

탐색문제에서 각 노드에 대해 b 개의 선택이 가능하고 d 의 깊이에 목표노드가 있다고 하면, 순진한 탐색 알고리즘에서는 해를 찾기위해 bd 개의 노드들을 아마도 탐색해야 할것이다. 휴리스틱은 branching factor 를 b 에서 (이상적으로는) low constant b* 까지 감소시켜서 탐색 알고리즘의 효율성을 증진시킨다.

허용가능한 어떠한 휴리스틱도 적절한 (optimal) 의 답을 주겠지만, lower branching factor 를 가진 휴리스틱은 특별한 문제에 대해 훨씬 더 효율적으로 계산한다. 그것은 h2(n) 이 h1(n) 를 좌우한다면, 즉

휴리스틱 찾기

보통의 탐색 작업에서 low branching factor 를 가지는 허용가능한 휴리스틱을 찾는 문제는 AI 학계에서는 널리 연구되어 왔다. 흔히 사용되는 많은 기술들이 있다 :

이러한 기술을 사용해서 A.E. Prieditis 가 만든 ABSOLVER (1993) 라는 프로그램은 주어진 문제에 대해 휴리스틱을 자동적으로 생성하였다. ABSOLVER 는 8-puzzle 문제에 대해 어떤 기존의 휴리스틱보다도 새로운 휴리스틱을 생성했으며 Rubik's Cube 를 풀기위해 최초로 유용한 휴리스틱을 찾았다.

AI 에서의 휴리스틱

AI 에서의 많은 알고리즘들은 본질적으로 휴리스틱이거나 휴리스틱 규칙을 사용한다. 이것의 최근의 예는 e-mail 이 spam or ham e-mail 인지를 결정하기 위해 다양한 휴리스틱 규칙을 사용하는 SpamAssassin 이다. 그 규칙중의 어떤 것만을 사용하면 틀린 분류를 할수도 있지만, 동시에 여러개의 휴리스틱 규칙들이 결합되면 그 해는 훨씬 견고하고 믿을만한 것이 된다. 이것은 패턴인식에서는 높은 신뢰도 (confidence, 배경이론인 통계학에서 따온 용어) 라고 불린다. 휴리스틱이란 용어가 rule-based language processing (stemming : 주어진 단어의 형태적 근원을 결정하는 프로그램 또는 알고리즘, 예를들면 cats, catty, catlike 는 cat 이라는 단어에서 나온것), pattern recognition (특징 (features) 가 휴리스틱이다) 또는 image processing 에서 사용될때 휴리스틱은 규칙들 그 자체를 언급하는 것으로 사용되기도 하며, 실무자들은 휴리스틱을 ad hoc 을 의미하는 것으로 사용하기도 한다. ....................... (Wikipedia : Heuristic (Computer Science))

휴리스틱은 발견과 발명의 기술과 과학이다 (art and science of discovery and invention). Heuristic 은 그리스어 "eureka" 가 어원이며 "I find" 라는 의미다. 휴리스틱은 "당신의 관심사항 (attention) 을 결실이 있게 어떤 방향으로 이끌어나가는 방법의 일종" 이다.

수학자 George Polya 는 20 세기에 그의 저서 'How to solve it' 에서 휴리스틱이란 말을 사용했다. 그는 학생으로서 수학적 증명 (proof) 을 배웠지만, 수학자들이 증명에 대해 어떻게 생각하는지도 몰랐고 어떻게 배웠는지도 몰랐다. 그의 저서는 수학을 학생들에게 가르치면서, 문제를 보고 해를 던져주는 방법으로서의 휴리스틱에 대한 생각들을 모아놓은 것이다. 그 책에 나오는 틀에박힌 휴리스틱이라는 것은 다음과 같다. 만일 이해하기 어려운 문제를 만났다면 그림을 그려라 ; 만일 해를 찾을수 없다면 하나의 해를 가지고 있다고 가정하고 그것이 무엇으로부터 유도될수 있는지를 보여라 ("working backward") ; 만일 문제가 추상적이라면 구체적인 예를 검사해라 ; 훨씬 더 일반적인 문제를 먼저 풀어라 ("발명가의 파라독스 (inventor's paradox)" : 더 큰 야망이 있다면 더 큰 성공의 확률을 가질수 있다)

문법 : 하나의 heuristic (heuristics 가 아니라) 이라는 것은 "발견 (discovery) 을 향해서 당신의 관심사항 (attention) 을 어떤 방향으로 정하는 특별한 기술" 이며, 그것의 복수형이 heuristics 이고, "어떤것이 발견되는 방법과 관련되는" 라는 뜻의 형용사는 heuristic 이다.

심리학

심리학에서 heuristics 은 "복잡한 문제나 불완전한 정보에 직면해서 의사결정을 하고 판단을 내리고 문제를 해결하는 방법을 설명하기 위해 제안되어 왔던 간단하고 효율적인 주먹구구의 규칙들" 이다. 이러한 규칙들은 어떤 환경에서는 잘 작동하지만 어떤 경우에는 시스템적 인지 편견 (systematic cognitive biases) 으로 이끈다.

예를들면 사람들은 값비싼 맥주를 값싼 맥주보다 더 맛있는 것으로 지각하는 경향이 있다. 이것은 가격과 브랜드를 바꿨을 때에도 발견되는데, 즉 상대적으로 값싼 브래드에 비싼 가격을 매기면 실험에 참가한 사람들은 상대적으로 원래 비싼 맥주보다 더 맛있는 것으로 지각하기에 충분하다는 것이다. 이러한 현상을 "가격이 질을 결정하는 (price implies quality)" 편견 이라고 부른다.

인간의 의사결정에서 휴리스틱을 발견하는 많은 작업이 Amos Tversky and Daniel Kahneman 에 의해 촉발되었으며 그들은 behavioral finance 에 중요한 영향을 미치던 인물이다. Gerd Gigerenzer 가 주도한 비판은 휴리스틱이 인지과정의 편견 (cognitive biases) 을 낳지않고 정확한 판단을 하는데 사용될수 있는지 에 촛점을 맞추었다 - 휴리스틱은 "빠르고 비용이 적게든다 (fast and frugal)"

심리학에서의 휴리스틱에 대한 이론

Well-known:

Lesser-known:

철학

철학에서는, 특히 대륙 유럽철학에서는, 형용사 "heuristic" (또는 heuristic device) 은 어떤 실체 (entity) X 가 다른 실체 Y (X 와 동일하지 않은) 를 이해하거나 발견하기위해 (to understand or to find out) 존재할 때 사용된다. 좋은 예가 하나의 모델 (model) 로서 그것은 그것이 모델링 하는 것과는 전혀 같은 것이 아니며 단지 후자를 이해하기 위한 휴리스틱 장치이다. 이야기 (stories), 상징 (metaphors) 등등이 그러한 의미에서 heuristics 라고 이름붙일수 있다. 고전적인 예는 Plato 의 유명한 작품인 Politeia 에 묘사되는 utopia 의 개념이다. 그 개념은 Politeia 에 묘사된 대로 "이상적인 도시 (ideal city)" 의 목적은 그 개발을 위한 지향점 (orientation-point) 을 추구하거나 보여주는 것이 아니라, 만일 어떤 원리를 선택하고 그것을 엄격하게 수행하려 한다면, 사물들이 어떻게 서로 연결되어야 하고, 또한 사물들이 어떻게 많은 문제를 가지게 되는 또다른 사물로 이르게 되는지를 보여주는 것이다.  

법률

법률이론에서, 특히 법과 경제이론에서, heuristics 는 법에서 case-by-case 분석이 불가능할때 사용된다. 예를들면 미국에서 법적인 음주연령은 21 세이다. 왜냐하면 알콜 남용의 위험을 포함해서 의사결정을 할수 있을 만큼 충분히 성숙할 필요가 있다는 주장때문이다. 그러나 사람들이 다른 속도로 성숙한다고 가정하면 21 세라는 나이는 너무 늦을수도 있고 빠를수도 있다. 이런 경우에 다소 임의적인 데드라인을 사용하는데, 그것은 한 인간이 책임감을 가졌다고 사회가 믿을수 있을만큼 충분히 성숙했는지를 말하는 것이 불가능하기 때문이다.

같은 추론이 특허법에도 적용된다. 특허는 발명가에게 그 발명에 대한 인센티브를 가지게 하여 보호할 필요가 있기때문에 정당성을 갖는다 (또는 어떤이가 그들의 아이디어를 사용한다면 tragedy of the commons 를 겪을 것이기 때문에). 따라서 발명가에게 그들의 제품에 임시로 정부가 부여하는 독점권 (monopoly) 를 부여하여 그들의 투자비용을 보상하고 (recoup) 제한된 기간동안 경제적 이득을 취할수 있게 해야한다. 미국에서 이러한 임시 독점권의 기간은 특허를 신청한 날로부터 20 년이다 (비록 신청하여 특허를 얻을때까지는 실제로 독점권이 시작되지는 않지만). 그러나 위에서 언급한 음주연령의 경우처럼, 그 기간은 효율성을 위해 제품마다 달라야할 필요가 있을 것이지만, 20 년이 사용되는 이유는 그 숫자가 어떤 개별적인 특허를 위한 것이어야 하는지를 말하기가 어렵기 때문이다. 최근에는 Lawrence Lessig 같은 이들은 소프트웨어 같은 다른 종류의 산업의 특허 기간은 다르게 해서 보호받아야 한다고 주장해왔다. .................. (Wikipedia : Heuristic)

paper :