휴리스틱(Heuristic)

머신러닝을 공부하다보면 이따금 휴리스틱(Heuristic)이라는 단어를 접하곤 합니다.
때문에 이번에는 휴리스틱이 무엇인지, 어떻게 쓰이고 있는지에 대해 정리해보고자 합니다.

휴리스틱?

찾아내다(find out) 그리고 발견하다(discover) 라는 의미를 가진 휴리스틱이라는 단어는 다른말로 발견법이라고도 불립니다.
휴리스틱이란 어떤 문제가 있을 경우,
해당 문제를 해결할 수 있는 방법이 증명되지 않았을 때, 시행착오를 거쳐가며 경험 또는 직관을 활용해 충분히 효율적인 해답을 유추해나가는 기법을 의미합니다. (말인 즉슨 누군가 어떤 문제에 대한 해결책을 제시하였지만, 올바른 것인지에 대한 수학적 증명이 없다면 그것은 휴리스틱한 것이고, 증명이 된다면 그것은 휴리스틱하지 않은 것입니다.)

이는 사실 인간의 가장 기본적인 문제 해결 방식 중 하나인데, 아래는 수학자 George Polya 의 저서 "How to solve it" 에 나온 예시입니다.

• 만일 이해하기 어려운 문제를 만났다면, 그림을 그려라
• 만일 문제가 추상적이라면, 구체적인 예를 검사해라
• 훨씬 더 일반적인 문제를 먼저 풀어라

나아가서 위키에 따르면 휴리스틱하다는 것은 심리학, 경제학 등 각 분야마다 비슷하면서도 조금씩 다른 의미를 가지게 되나, 저희가 집중하고 싶은 컴퓨터 공학에서의 휴리스틱은 다음과 같습니다.

컴퓨터 공학에서 발견법은 해결법이 정확히 해결되는가에 대한 문제를 배제하고, 경험과 직관을 통해, 일반적으로 좋은 해결법이나, 보다 간단한 해결법을 찾고자 하는 방법이다. 예를 들어 상업적인 컴퓨터 바이러스 검색 엔진들은 발견법으로 특정 속성또는 특징을 찾아 바이러스를 찾아낸다. 그러나 잠재적으로 정확도가 떨어질 수 있다.

다르게는, 일상생활 또는 자연에서 나타나는 현상을 모티브로 한 알고리즘을 휴리스틱하다고 표현합니다. 개미가 군집을 이루는 과정 등이 그러합니다.

휴리스틱의 그리스 어원은 우리가 잘 알고있는 유레카와 비슷하다고 합니다. 어쩌다 발견한 해결책이란 뜻이겠지요. 그러니까 휴리스틱한 알고리즘이라는 건, 왜인지는 잘 모르겠는데 이렇게 하다보면 답은 대충 맞더라.. 정도가 되지 않나 싶습니다.

결국 이러한 내용은, 블랙박스라는 특성을 가진 머신러닝에 잘 부합되는 내용이라는 생각이 듭니다.
실제로 인공지능에서의 많은 알고리즘은 본질적으로 휴리스틱이거나, 휴리스틱 규칙을 사용합니다. 제가 접한 페이스북의 예측 패키지 Prophet 이 그러했고, 머신러닝의 대표적 예시중 하나인 스팸 메일 분류기(중 SpamAssassin)가 그러합니다.

마지막으로 캐글의 코드를 읽다보면 자주 만나게 되는 유전자 알고리즘(Genetic Algorithm)은 정말 대표적인 휴리스틱 알고리즘입니다. 일반적으로 자연의 생명체는 유전자 결합을 통해 진화합니다. 결합 도중 더 우월한 유전자가 생성되기도 하고, 더 열등한 유전자가 생성되기도 합니다.
이러한 컨셉에 걸맞게 유전자 알고리즘은

1. 해결하기 어려운 문제에
2. 확률 모형에 기반한 다양한 집단을 생성하고
3. 조합과 변이를 통해 근사한 답을 찾습니다.

최고의 해답을 찾는 것이 아닌, 해결하기 어려운 문제에 대한 적당한 답을 찾는다는 컨셉이 그대로 구현되었음을 확인할 수 있을 것같습니다. 구체적인 유전자 알고리즘에 대한 이야기는 다음 기회에 정리하겠습니다.

당연히 어떤 문제를 해결할 때에 최고의 방법은 가장 빠르고, 가장 정확한, 증명된 알고리즘을 만들어 내는 것입니다. 그러나 실제로는 너무나 당연하지만 증명하기 힘든 문제 또는 너무나 어려워서 증명할 수 없는 문제, 그리고 증명할 수 있지만 오랜 시간이 걸릴 것으로 생각되는 문제들이 너무 즐비합니다. 때문에 인공지능, 사람과 같은 컴퓨터를 만들기 위해서 이런 휴리스틱한 접근법이 많이 시도되는 것 같습니다.