메타휴리스틱
최적화를 위한 짬에서 나오는 바ㅇ.. 법론
개요: 최적화란?
데이터 분석가들이 하는 업무에는 여러가지가 있지만, 그 중 하나는 (있어보이는 말로) 최적화입니다.
저는 데이터 분석가의 JD에서는 자주 보지 못했던 단어인데, (그러나 실제로 해야했던 !) 이 최적화는 뭘까요? 혹시나 유튜브에서 쉽게 설명해주지 않을까 싶어서 검색을 해보았는데 그 결과는 아래와 같습니다.
오늘 다루는 메타휴리스틱은 여러 최적화 방법론 중 한 방법이기 때문에, 최소한의 이해를 하기 위해 최적화에 대한 이야기를 조금 더 해보면 좋을 것 같은데요.
결론만 먼저 말하면 최적화는 특정 값을 최대 (혹은 최소)로 하는 포인트를 찾는 것이라고 이해해도 충분합니다.
(뇌피셜이지만) 예를 한번 들어보겠습니다.
제가 최근에 애용하고 있는 서비스 중 하나인 챌린저스 의 데이터 분석팀 의 목적은 여러 가지가 있겠지만 매출도 주요 지표 중 하나에 있을 겁니다. (서비스 설명은 생략하겠습니다)
(실제와는 다르겠지만, 외부인의 입장에서) 챌린지가 끝났을때 환급금을 제하고 90%는 상금으로 분배하고, 10%만 수수료의 형태로 (수수료 수익) 가져간다 라고 전제를 해보겠습니다.
이 경우 챌린저스에서 규칙으로 조절할 수 있는 값들이 여러 개가 있지만, 챌린지의 성공을 간주하는 기준과 (85%), 두번째로 챌린지의 최소 참가금액 (10000원), 마지막으로는 챌린지의 기간이라는 (2주) 3가지를 우선 생각해 볼 수 있습니다.
만약 성공 기준이 너무 낮다면 (ex. 1%, 100번 중 1번만 해도 인정) 그만큼 환급을 받기 쉽기 때문에 많은 수의 챌린지가 생기겠지만, 동시에 챌린지 당 수수료 수익은 줄어들게 됩니다.
그렇다면 성공 기준을 높이는 것이 좋지 않을까? 라는 생각을 해볼 수 있는데요. 만약 92%라면 (14일 중 13일) 환급을 받기가 상대적으로 더 어려워 지기 때문에 챌린지의 수가 줄어들 수 있다고 생각해볼 수 있습니다. 챌린지 당 수수료 수익은 늘어나겠지만 챌린지의 수가 줄어들기 때문에 수익이 무작정 늘어나지는 않겠죠.
최소참가금액과 기간도 유사하게 (방향은 다를 수 있지만) 성공율과 참가자 수, 챌린지당 수수료 수익, 그리고 결과적으로는 수수료 수익에 영향을 미치게 됩니다. 심지어 이 3개의 요인들끼리도 영향을 주고 받을 수 있음을 고려하면 상당히 머리가 아파지게 됩니다.
이러한 상태에서 수익을 가장 최대화 하는 기준과 금액, 기간의 조합을 찾는 문제를 최적화 라고 표현할 수 있습니다. 특정한 x, y, z 에 따른 f(x)의 값을 시각화 하면 아래와 같이 나온다고 할때 가장 높은 (빨간색이 되는) x, y, z를 찾는 것이죠.
이 빨간색을 찾기 위한, 가장 좋은 방법은 뭘까요?
이미 스포일러를 하긴 했지만 모든 조합에 대해서 수익을 알고 있다면 가장 높게 나오는 조합을 선택만 하면 되기 때문에 상당히 간편합니다.
그렇다면 문제는 f(기준, 금액, 기간) = 수익 이라는 함수를 찾는 것으로 바뀌는데요 (모델링이라고 표현하기도 합니다)
모델링은 상당히 유용하고, 매력적인 방법이지만 사람의 심리를 포함한 정말 많은 요인들을 고려 할 수 있어야 모델링을 할 수 있다는 점에서 개인적으로는 어려운 접근법이라고 생각합니다. (그렇지만 ML / DL engineer 들은 풀어내기도 합니다!)
특정 조합에 따라 수익을 찾는 다른 방법으로는 실험이 있습니다. 마치 A/B 테스트처럼 그룹을 나누어 한 곳에는 10,000원, 다른 한 곳에는 20,000원 등으로 나누어 챌린지를 개설하고 이에 따른 수익을 실제로 확인하는 것이죠.
이러한 실험은 기준, 금액, 기간 마다 ("솔루션”) 수익 ("평가값") 을 알 수 있지만 요인에 정해질 수 있는 값의 범위가 넓은 경우 (가령 1일, 3일, 5일, 일주일 … 1달) 모든 조합들을 실험하는 것이 오래 걸리기도 하고, 실험 설계 와 효과 분석 자체를 위한 리소스를 많이 할당해야한다는 문제가 있습니다.
저는 예시를 챌린저스로 들었지만, 랜딩페이지의 디자인, 문구, 크기, 배치 등 여러 요인의 조합을 통해 전환율 이라는 지표를 본다라고 가정하면 이 또한 최적화의 문제가 됩니다.
휴리스틱
이러한 최적의 솔루션을 찾는 또 다른 방법은 휴리스틱입니다 (드디어!).
휴리스틱이 어떤것인지 표현하는 것은 개인적으로 매번 어려운 일인데요. 이번 글에서는 사람의 도메인 혹은 경험, 주관적인 근거로 솔루션에 접근하는 방법이라고 생각해도 좋을 것 같습니다.
제가 참고한 책에서는 휴리스틱을 어떤 문제를 해결하기 어려울때 성능을 보증할 순 없지만 경험적으로 좋다고 알려진 방법 이라고 표현하고 있습니다.
가령. 아래와 같이 버튼 디자인을 바꾸기 위해 3가지 배경색과 글자색의 조합에 대해 각 색상에 따른 모델을 만들거나, 실험을 해볼 수 있지만 “하지 않아도” 될 이유가 있다면 (그러나 안한 것이 최적일 수도 있습니다) 해당 솔루션은 배제하고 다른 솔루션에 집중하는 방법도 있을 겁니다. (좋은 예시인지는 잘 모르겠습니다)
여기서 만약 3 by 3이 아닌 10 by 10 이라면, 100개의 솔루션을 전부 해보는 것은 문제를 풀기 위한 가장 좋은 접근법은 절대 아닐겁니다. 그러나 가지 수를 줄이며, 가장 높은 퍼포먼스를 갖는 솔루션을 찾기 위해 할 수 있는 방법 중 하나는 하나의 방법에 대해 결과를 확인하고, 솔루션 공간의 “주변에 있는” 솔루션들의 결과를 확인해보고 가장 높은 것으로 솔루션을 정하는 과정…을 반복 하는 것입니다. (말이 어렵지만, 아래에서 예시를 다루고 있습니다.)
메타휴리스틱
오늘 글의 주제였던 메타휴리스틱은 (다시 한번. 책에서는), 특정한 문제에 한정되지 않는 유용한 휴리스틱을 제공하는 프레임워크를 표현할때 사용하고 있습니다.
아무튼 휴리스틱 / 메타휴리스틱은 모델을 가정하지 않는 최적화 방법입니다. 조합을 구성하는 요인들의 구체적인 효과나 영향은 알 수 없지만, 동시에 이를 가정 할 필요가 없기 때문에 요인들의 상호작용이나 최적 변수 선택을 고려하지 않아도 된다는 장점이 있습니다. 이보다 더 좋은 휴리스틱의 장점은, 도메인 경험이 없어도 문제를 풀 수 있다는 점 이라고 생각해요.
(말이 진짜 어렵네요)
언덕오르기
이러한 솔루션들과 그에 따른 평가치를 이루고 있는 공간을 생각해볼 때, 가장 높은 “기둥” 으로 가기 위해서 가장 좋은 방법은 전체의 뷰를 헬기를 통해 보는, 다시 말해 모델링이나 측정을 통해 얻은 모든 솔루션, 그리고 그 결과를 보고 높은 것을 선택하는 것이지만 각각 나름의 어려운 이유들이 있습니다. (그리고 휴리스틱은 이를 우회하는 방법입니다.)
이에 대해 휴리스틱의 관점으로 접근하는 방법은 아래와 같습니다.
- 초기 위치의 솔루션 값을 평가한다.
- 현재 솔루션 근처의 값을 평가한다.
- 지금 솔루션보다 높은 것이 있다면 솔루션을 해당 솔루션으로 업데이트한다.
- 주변 솔루션보다 높을때까지 2 ~ 3 을 반복한다.
- 최종 솔루션으로 선택한다.
글로 보면 어렵기 때문에 이미지를 첨부하겠습니다.
특정 솔루션이 아래의 수식과 같은 결과값을 갖는다고 할때 솔루션 공간은 아래 블록그림과 같이 표현 됩니다. (모델링은 어려운 상황이라 가정합니다)
자 이제 앞에서 말한 방법을 적용하려고 하는데요, 첫 솔루션을 (0, 0)으로 시작하면 그때의 솔루션 탐색 이력은 아래 테이블과 같습니다.
25개의 솔루션을 테스트 하는 것이 아닌 10개만 하고도 가장 높은 솔루션을 찾을 수 있습니다. (DA 로써 최적화를 이루어 냈습니다 !)
한편, 초기 지점이 (0, 0) 이 아닌 (4, 2) 일 경우의 탐색 이력은 아래와 같습니다.
이번에는 더 적은 7번을 탐색하고 최적의 솔루션을 찾았지만, 전체에서의 최적 값은 아닙니다.
이러한 상황을 표현하기 위해 로컬 맥시마 / 글로벌 맥시마 (한글로는 국소 / 전역 최대값) 라는 표현을 쓰기도 하는데요. 해당 근처에서 최적인 값을 로컬, 전체에서 최적인 값을 글로벌 맥시마 라고 표현합니다.
아무튼, 이러한 기본 언덕오르기 방법은 첫 시작을 어디서 하느냐에 따라 로컬 맥시마는 찾을 수 있지만 글로벌을 보장하지는 않는 다는 문제가 있습니다.
그렇기 때문에 (수많은 사람들이 연구를 통해) 솔루션 탐색을 마친 이후, 다시 무작위로 초기 솔루션을 선택한 다음 재시작 하는 방법, 혹은 여러 개의 초기 솔루션을 갖고 탐색하는 방법으로 개선을 이루어 냈습니다. 책에서는 다중시작언덕오르기 라는 표현을 쓰고 있습니다.
그러나 여전히 최적화의 결과가 랜덤한 시작 시점에 영향을 받는 것은 동일합니다.
확률적 알고리즘 (Randomized Algorithm)
우리가 이전까지 했던 방법은 근처의 “모든” 솔루션 중 제일 높은 것을 선택하는 “결정적” 알고리즘 (Deterministic Algorithm) 인데요.
이번에는 모든 솔루션이 아닌 근방의 솔루션 중 무작위로 선택된 솔루션만을 탐색하는 방법을 사용할때의 탐색 이력입니다. 이전과 동일한 (4, 2)에서 시작했지만 글로벌 맥시마에 도달한 모습을 확인 할 수 있습니다. (그러나 여전히 랜덤에 영향을 받습니다)
시뮬레이티드 어닐링 (담금질)
이번 방법은 여러 개의 초기 솔루션을 사용 하거나, 근처 솔루션을 랜덤하게 선택하여 최대로 업데이트 하는 방법들과는 다르게 주변 솔루션이 현재 솔루션보다 작더라도 리스크를 감수하고 받아들이는, (랜덤성을 배제한) 방법입니다. 특정한 확률로 지금 솔루션보다 좋지 않아도 솔루션을 업데이트 하는 것이죠.
아무튼 이 어닐링 방법에서 “확률”은 온도 (Temperature)라는 τ 로 표기 하며, 온도가 높을 수록 현재보다 좋지 않은 것도 받아들이게 됩니다. (당연히 온도가 낮으면 기본 언덕오르기와 동일한 방법이 됩니다)
TMI:
담금질혹은시뮬레이티드 어닐링은 금속을 가열한 후, 냉각하는 과정을 통해 강한 소재를 얻는 금속공학에서 착안된 방법이며, 처음에는 격하게 움직이며 다양한 솔루션, 점점 유망한 솔루션으로 수렴하는 방법을 표현합니다.
어닐링을 활용하면, 랜덤을 배제하고 최적 솔루션으로 갈 수 있는 길이 열려 있지만 동시에 아래와 같은 새로운 문제가 3가지 발생하게 됩니다.
- 온도의 초기값은 어떻게 정할 것인가
- 온도를 어떻게 감소시킬 것인가 (
냉각 스케줄) - 온도를 어떻게 받아들이는 확률에 반영할 것인가
물론 이는 이번 글의 목적은 아니기 때문에 다루지 않겠습니다.
아무튼, 이 어닐링 방법을 특정 파라미터를 이용해서 탐색한 결과는 아래와 같습니다. (그냥 이런 방법도 있다 정도만 기억하셔도 이 글의 목적으로는 충분합니다)
유전 알고리즘 Genetic Algorithm
이 방법에서는 각 솔루션을 하나의 생명체로 간주합니다. 즉, 생명체가 번성하는 과정을 묘사하여 자연선택 (도태), 유전자 교차, 유전자 돌연변이 등의 방법을 솔루션에 적용하게 됩니다.
이 유전 알고리즘은 강화학습이나 최적화를 하시는 분들이 작성한, 더 잘 설명된 글들이 충분히 많이 있기 때문에 서술하지 않겠습니다.
정리
특정한 요소들의 조합인 솔루션 들 중 가장 좋은 솔루션을 찾아가는 “최적화” 중 언덕오르기 -> 로컬 솔루션 -> 난수 -> 시뮬레이티드 어닐링 의 흐름으로 간단히 다루어 봤습니다.
저는 처음에 이 개념을 접했을때 와 신세계다 수익 최적화 딱대!! 이런 생각을 했지만… 아쉽게도 모든 문제에 이러한 메타휴리스틱을 적용할 수 있는 것은 아닙니다.
평가함수가 근접최적성 (proximate optimality principle) 을 만족해야만 하는데요. 쉽게 말하면 좋은 솔루션끼리 비슷한 특징을 갖는다라는 의미이며, 특정 솔루션은 근접 솔루션들에 비하여 완전 극과극을 달리지 않고 어느 정도 예측이 되는 경향성이 있어야 한다라고 생각해도 좋을 것 같습니다.
또한 다른 여러 인생의 문제들도 그러하듯 메타휴리스틱 또한 최적의 솔루션 주변으로 탐색을 모으는 “집중화” 와 탐색하지 않은 솔루션을 시험하는 “다양화” 의 균형을 잘 조절해가며 탐색해야합니다.
이 집중화와 다양화를 이전에 MAB와 톰슨샘플링 글에서 언급한 적이 있는데요, 관심 있다면 참고하셔도 좋습니다.
어쩌다 보니 어려운 단어들도 잔뜩 들어가고 내용도 길어졌는데요. 최적화가 그렇게 막 어려운 개념은 아니구나, 그리고 이러한 방법들이 있구나 정도만 기억하셔도 저는 충분히 만족할 것 같습니다. 긴글 읽어주셔서 감사합니다.
번외
데이터 직군에 있었지만, A/B 테스트 혹은 데이터에 기반한 의사결정이 만능은 아니라고 생각합니다. 개인적인 생각으로 데이터는 임팩트에 곱하기를 만드는 방법으로, 프로덕트나 서비스, 인프라, 상황에 따라 데이터에 집중하는 것보다 고객의 니즈와 질문에 집중하는 (더하기) 것이 어쩌면 더 큰 임팩트를 만들어 낼 수 있다고 생각합니다. (데이터가 중요하지 않다는 것 또한 아닙니다)
전 세계 시총 1위, 애플은 A/B 테스트를 안했다고도 하죠. (물론, 그렇기 때문에 기상천외한 솔루션이 나오기도 합니다)
광고는 아닙니다만) 아래 책은 이번 글을 작성하며 많이 참고했던 책인데요 베이지안부터 머신러닝까지 최적화를 다루는 많은 주제를 담고 있는 책으로 Python 코드도 포함되어 있어 꽤 괜찮은 책이라고 생각합니다. 강추
실제 챌린저스의 이용약관을 통해 살펴본 “수수료”는 제가 가정했던 미환급금액의 10%보다 훨씬 ! 더 크다는 것을 알 수 있습니다.
언덕오르기를 포함한 여러 탐색 알고리즘을 잘 설명한 블로그를 첨부합니다.
유전 알고리즘을 제가 제일 직관적으로 이해했던 영상…을 해설한 글을 첨부합니다.
