Kaggle

Kaggle : Santa’s Stolen Sleigh

두 번째로 참여하게 된 Kaggle 대회는 Santa’s Stolen Sleigh 라는 대회이다. 이 대회는 다소 이벤트성 대회의 성격을 띠고 있는 것이, 크리스마스 기간에 맞추어 크리스마스 컨셉으로 나온 문제이기 때문이다. 제목만 봐도 그래보이지 않는가? 그러나 이 대회는 이벤트성 대회임에도 불구하고 실제 상금이 걸려있는 대회이다. 최종 1위 팀 / 리더보드 1위를 가장 길게 유지하고 있던 팀 / 제공된 Optimization Tool 을 이용한 팀 중 가장 점수가 높은 팀 에게 각각 1만불, 5천불, 5천불의 상금이 지급된다. 물론 나는 저 상금과는 상당히 거리가 멀었지만..

여하튼 이 대회는 다른 Kaggle 대회와는 다소 성격이 다른 대회이다. 다른 대회들이 정말 Data Science 스러운 문제들을 내놓고 있다면, 이 대회는 그보다는 조금더 PS적인 느낌이나 Optimization 느낌이 나는 문제를 제공했다고 할 수 있다. 과연 어떤 문제인지, 그리고 내가 어떤 방식으로 접근했는지 정리해보겠다.

Problem Description

크리스마스를 맞이하여 산타할아버지가 전 세계에 선물을 나누어주려고 한다. 세계 방방곡곡에 10만개의 선물을 배달해야하는데, 각각의 선물이 배달되어야 하는 위도-경도 좌표와 그 선물의 무게가 주어져있다. 산타할아버지는 루돌프가 끄는 썰매를 타고 North Pole에서부터 선물을 배달해야 한다. 그런데 한 번의 Trip에서 싣는 선물들의 무게의 합이 1000을 넘으면 안되고, Trip 한번이 끝나면 다시 North Pole로 돌아와서 남은 선물들을 담은 뒤 다음 Trip을 떠나야 한다. 썰매 자체의 무게는 10이다.

이 문제의 최종적인 목적은, 루돌프들이 너무 힘들지 않도록 배달하는 과정을 최대한 최적화시키는 것이다. 루돌프들이 힘든 정도는 ‘Weighted Raindeer Weariness – WRW’ 라고 해서, 다음과 같은 방식으로 계산한다.

WRW
w_kj = j번째 trip에서 k번째로 배달하는 gift의 무게, Loc_i = i번째로 배달하는 gift의 위치

즉, 어떤 지점에서 다른 지점으로 이동할 때의 그 거리와 그 거리를 이동할 때의 썰매+선물의 총 무게가 있을텐데, 이 값을 곱한 것을 모든 이동에 대해 다 더한 값을 WRW라고 하는 것이다. 이 때 거리는 haversine 이라는 방식을 이용하여, 위도와 경도를 이용하여 실제 지구상에서의 거리를 계산한 거리를 사용한다.

더 자세한 설명은 대회 페이지의 Description, Evaluation 항목에서 확인할 수 있다.

Approach

기본적으로 이 문제는 TSP 느낌이 나는 문제이다. 결국 주어진 지점들을 어떤 순서로 이동하느냐에 따라 점수가 달라지는 형태의 문제이기 때문이다. 물론 한 Trip에 대한  Weight limit이 있고, 점수 계산법도 크게 다르기 때문에 TSP와는 매우 다르면서도 훨씬 어려운 문제이기는 하지만 기본적으로 완전 그래프 위에서 경로를 최적화시켜나간다는 컨셉은 같기 때문에 전체적인 접근의 틀은 유사하게 가져갈 수 있을 것이다.

나는 기본적으로 이 문제에 대한 해결책을 크게 두 개의 단계로 나눠야 한다고 생각했다. 일단, 문제에서 각각의 Trip들에 대해 어떤 Gift들이 들어가야 하는지를 정해준다면, 각각의 Trip이 몇 번째로 진행되는가와는 상관 없이 Trip 하나하나에 대해 독립적으로 최적화를 시켜줄 수 있을 것이다. 즉, 문제를 크게 (1) Trip에 들어갈 Gift를 나누는 과정, (2) 각 Trip에서 선물을 배정하는 순서를 결정하는 과정 으로 나누어 진행할 수 있는 것이다.

이 문제를 진행하는 과정에서 가장 크게 유의해야할 점은 ‘계산량’ 이다. 먼저 선물의 갯수가 10만개나 되어, 안일하게 알고리즘을 세웠다가는 생각보다 계산량이 너무 많아져서 진행 속도가 너무 느려질 수 있다. 또한, 각 지점들 사이의 거리를 ‘haversine’ 으로 계산하는데, 이 계산에 sin, cos 뿐만 아니라 atan 등의 함수도 들어가기 때문에 거리 연산에 생각보다 많은 시간이 든다 (실험환경 기준으로 100000개의 haversine 연산을 하는 데에 0.31초 정도가 소요된다). 따라서, 최대한 계산량을 최적화하는 방향으로 문제를 해결해야 한다.

Stage #1 : Grouping Gifts (1)

문제를 Stage 1과 2로 나누어서 Grouping 과정과 Trip 순서 Optimization 과정으로 나누었지만, 실질적으로 대부분의 시간은 이 Stage 1 과정에서 소모하였다. 정말 엄청난 삽질과 멘붕, 그리고 시간소모를 하면서 결국 처음 예상했던 것과 너무 다른 방향으로 문제에 접근하게 되었고, 결국 정말 불만족스러운 결과를 얻게되었다. 여기에서는 처음부터 끝까지 내가 어떤 방식으로 문제에 매달렸는지에 대한 기록을 의식의 흐름대로 적어보려고 한다.

첫 번째 단계에서는 먼저 선물들을 묶어서 Trip에 들어갈 선물들을 선별해야한다. 이 때 대략적으로 초기해를 잡고 시작하려 했는데, 나는 처음 문제에 접근할 때 가장 좋은 방법이 ‘가까이 있는 선물들을 묶어서 한 Trip에서 같이 배달하는 것’ 이라고 생각하였다. 따라서 k-means를 구현하여 대충 가까이 있는 선물들을 묶어놓은 초기해를 만들었다. 이렇게 한 문장으로 적어놓으니 굉장히 간단하게 한 것 같지만, 이 k-means를 하는 데에도 나름 시행착오가 많이 들어갔다. haversine 연산의 시간이 오래 걸리기는 하지만 이를 기준으로도 충분히 계산할 수 있을 것이라고 생각하여, k-means를 할 때 위/경도 기반으로 계산을 진행했다. 그런데 이렇게 할 경우 클러스터의 중심점을 옮기는 과정에서 단순히 평균을 낼 수가 없어서, 단위구 위의 실제 좌표로 변환하여 평균을 낸 뒤 다시 위, 경도 기반 좌표로 바꾸는 식으로 계산을 진행했다. 또한, weight limit 조건을 만족하기 위해 가장 가까운 클러스터의 무게가 초과될 경우 다음으로 가까운 클러스터를 보는 방식으로 assign을 진행하였다.

대회 Forum을 보니 대부분의 사람들의 Trip의 수가 1200~1500 정도인 것 같아서, k를 1800으로 잡고 클러스터링을 진행하였다. 이 k-means의 경우 haversine 연산을 사용하기 때문에 numpy를 이용한 최적화를 하기가 힘들어서 실행 시간이 굉장히 오래 걸렸지만, 실행시켜놓고 일어나보니 얼추 클러스터링 된 결과를 얻을수가 있었다.

다음은 이 초기해를 바탕으로 Optimization을 진행하여, 더 좋은 Trip들을 얻는 과정이 필요하다. 이 과정이 문제 해결에 주가 되는 과정이므로 이 과정을 해결하는 알고리즘을 설정하는 것이 굉장히 중요하다. 결국 이러한 문제를 푸는 과정은 ‘방대한 해 공간을 탐색해가면서 가장 좋은 해를 찾는 것’ 이라고 요약할 수 있을 것이다. Machine Learning 분야에서는 이러한 ‘해공간의 탐색’ 이 Gradient Descent라는 이름으로, 기울기를 따라 조금씩 이동해가면서 해공간을 탐색하는 방식으로 사용되고 있다. 그러나 이번 대회와 같은 문제에서는 목적 함수가 Discrete하기 때문에, 함수에 기울기라는 것이 존재하지 않아서 다른 방법을 적용할 필요가 있다.

해공간을 탐색하는 기법들은 정말 다양하다. GA, SA 등 이미 수많은 메타휴리스틱 기법들이 발견되어 사용되고 있고, ACO 등의 집단지성 최적화 기법도 있다. 이러한 수많은 방법들 중, 나는 이 문제에 가장 적합해보이고 내가 일전의 프로젝트에 사용해보아 가장 익숙한 Tabu Search라는 방법을 이용하여 문제에 접근하기로 하였다(사실, 대부분의 상위권 팀들은 Simulated Annealing 을 사용한 듯 하다. 그래도 기본적으로는 비슷한 흐름을 가진 기법이니..).

Tabu Search는 기본적으로 특정 해에 대해 이웃한 ‘이웃해’를 정의하여 그 이웃해들 중 가장 좋은 해로 이동하는 Local Search 기법에다가 Local Minima에 빠지지 않도록 이동 금지 목록인 Tabu List를 관리하면서 탐색하는 기법이다. 즉, 기본적으로 특정 해 상황이 있을 때 그 해와 유사한 해인 이웃해를 정의해주어야 한다. 이 문제에서는 이웃을 (1) 특정 선물을 현재 Trip에서 다른 Trip으로 옮긴 해, (2) 가까이 위치한 특정 선물 2개의 Trip을 서로 맞바꾼 해 로 정하고, 구현하였다.

여기서 문제는, Tabu Search를 행하기 위해서는 현재 해가 얼마나 좋은 해인지 그 점수를 평가하는 기준이 있어야 한다는 것이다. 문제의 첫 번째 단계에서는 단순히 선물을 여러개의 Trip으로 나누는 일만을 하기 때문에 직접적으로 이 해가 좋은 해라는 기준을 세우기가 굉장히 어렵다. 그래서 간접적으로, ‘각 나눠진 Trip들에 대해 Greedy하게 (Weight이 큰 Gift를 먼저 배달하고, Weight이 같을 경우 위도 내림차순으로 배달) 배달했을 때의 총 WRW’ 를 평가 기준으로 삼아 Tabu Search를 진행하였다.

이웃해와 평가 함수가 정해졌으니 이를 바탕으로 Tabu Search를 진행하면 되지만, 정말 Naive하게 구현할 경우 계산량이 폭발해버리고 말 것이다. 기본적으로 이웃해를 본다는 것은 정의한 이웃해에 대해 가능한 해를 다 보아야 하는데, 이웃 (1)만 봤을 때도 모든 이웃해를 다 보기 위해서는

  •  Cluster 두개를 정하는 갯수 1800P2
  •  x 이동할 선물을 정하는 갯수 평균 50개
  •  x (이동한 후의 선물 위치 찾기 O(50) + 이동한 후의 WRW 변화량 계산 O(50 * haversine 연산) )

 으로,  한 단계에서 대충 O(81억 * haversine 연산) 이 필요한데, 최소 몇천에서 몇만 단계를 이동해야 하는 탐색에서 한 단계에서 저렇게 많은 연산이 필요하면 제대로 탐색을 진행할 수조차 없다. 따라서 여기에서 계산량을 줄이기 위해서 여러 가지 방법을 사용했는데,

(1) 이동한 후의 WRW 변화량을 직접 이동시켜서 계산하는 것이 아니라, 이웃이 된 후의 변화량을 예측하여 WRW 변화량 계산을 O(1)로 줄였다. 사실 이 과정에서 삽질을 많이 해서, 디버깅 하는데 애를 좀 먹었다.

(2) 한 단계에서 모든 클러스터 선택 가능성을 보는 것이 아니라, 첫 번째 클러스터를 정할 때에는 일정 갯수의 클러스터만 랜덤하게 선택해서 보았다. 또한, 두 번째 클러스터를 정할 때 현재 선택한 선물과 두 번째 클러스터의 첫번째 선물이 너무 멀리 떨어져있을 경우 탐색하지 않았다.

(3) 앞에서 소개한 Greedy한 방법의 중요한 점은, 선물들을 모두 Comparable 하게 만들 수 있다는 점이다. 따라서 각 Trip의 선물을 정렬해놓고 List의 형태로 가지고 있었고, 새로운 선물이 들어갈 위치를 찾을 때 이분 탐색을 이용하여 들어갈 위치를 찾았다. 이를 이용하면 새로운 선물이 들어갈 위치를 찾는데에 걸리는 시간이 O(50)에서 O(ln 50) 으로 줄어든다.

(4) 이웃 (2) 에서 ‘서로 가까운 선물 두 쌍을 골라서 바꾼다’ 는 식으로 되어있는데, 여기서 선물을 선택할 때마다 가까운 선물이 뭐가 있는지를 계산한다면 어마어마하게 시간이 많이 투자될 것이다. 따라서 이는 미리 전처리를 해놓아서 특정 선물에서 가장 가까운 선물들의 목록이 담긴 배열을 만들어놓고, 필요할 때 이를 불러서 사용하였다.

Stage #1 : Grouping Gifts (2)

이렇게 Tabu Search를 구현하였으니 이제 돌리면서 점수가 줄어들기만을 기다리면 될 것이다. 그런데 문제가, 너무 수렴하는 속도가 느렸다. 처음 k-means만을 돌린 초기해의 WRW가 15.55B였는데, 반나절 넘게 돌리니 13.XXB 정도가 되었지만 수렴 속도가 너무 느려져서 더 낮아지길 기대하기 힘들었다. 당시 대회 1등의 점수가 12.38B였고, 100등 안에 들기 위해서는 12.45~6B 정도까진 점수를 내려야 했기 때문에 변화의 필요성을 느꼈다. 이 때 대회 Forum을 찾아봤는데, 이 링크에서 발견한 코드에서 단순히 k=4000으로 잡고, haversine도 아니고 위/경도를 가지고 단순히 k-means를 돌린 결과임에도 불구하고 돌린 결과가 13.7B 정도였다 (아무래도 내가 k를 작게 잡고, weight limit을 주어서 돌렸다는 점에서 점수가 많이 높여진듯 하다). 따라서, 초기해를 이 링크에서 주어진 submission으로 바꾸어준 후 새롭게 Tabu Search를 돌렸다. 확실히, 초기해가 낮아지니 더 많이 내려가는 양상을 확인할 수 있었다.

그런데 여기에서도 문제가 있었다. 일단 여기서 k=4000 이었기 때문에 Tabu Search를 진행하면서 점점 Trip들이 합쳐지고 Trip의 숫자가 줄어야 했는데, Trip이 서로 합쳐지는 일은 일어나지 않았다. 확실히 Tabu Search는 각 단계에서 이웃해들 중 가장 좋은 해로 이동하기 때문에, Trip이 줄어들기 위해서는 임시적으로 점수가 오르는 방향으로 진행되어야 할 것이므로 그 방향으로 진행하지 않을 수 있다는 생각이 들었다. 그래서 기존 점수에 더해서 Trip의 선물 갯수가 줄어드는 방향으로 이동할 경우 Bonus 점수를 주는 식으로 점수를 더해보았지만, 크게 상황이 나아지지는 않았다. 지금 와서 생각해보면, 강제로 하나의 Trip을 없애고 다른 Trip들로 분배하는 operation을 추가했으면 어땠을까 싶다.

또한, 어느정도 수렴이 된 결과를 가지고 Stage 2를 구현하여 돌려보았는데, 돌아가는 양상을 보니 Stage 2를 다 돌려도 결과가 잘해야 12.6~7B밖에 나오지 않을 것 같았다. 이렇게 되면, 좋은 점수를 얻지 못할 것 같다는 생각이 들었다.

이렇게 되어, 초기해를 clustering으로 정하는 방식을 폐기하고 이 링크에 있는 Submission으로 바꾸었다. 이 Submission의 경우 초기 점수가 12.52B 정도 되었는데, 이 방식은 선물들을 Longitude 기준으로 묶어서 North Pole 에서 시작하여 수직으로 내려오는 방식으로 진행하였다. 사실 모든 상위권 팀들은 이러한 방식으로 접근을 한 듯 하다. 이 방법을 가져와서 Gift 비교 기준 등을 수정하여 며칠 간 돌려본 결과, 12.52B에서 12.459B 정도까지 점수를 내릴 수 있었다.

Stage #2 : Trip Optimization

두 번째 단계에서는 분류한 선물들을 가지고 각각의 Trip 자체를 Optimize 하였다. Trip이 2천개 정도 있을 경우 각각의 선물은 평균적으로 50개 정도밖에 없기 때문에, 이 단계에서 빠르고 쉽게 점수를 내릴 수 있을 것이라고 기대했다.

두 번째 단계에서도 마찬가지로 Tabu Search를 이용하여 최적화를 진행했다. 이웃해는 (1) 두 선물의 배달 순서를 바꾼다 (2) 한 선물을 빼고, 다른 순서로 배달한다 로 정의하였다. 먼저 구현해놓은 Tabu Search가 있었기에, 이 단계에서는 상대적으로 쉽게 구현을 끝낼 수가 있었다.

문제는,  Stage #2가 생각보다 의미가 없는 단계였다는 것이다. 비슷한 위치 기준으로 클러스터링하여 생각한 해의 경우 확실히 처음 생각한 Greedy한 방법이 정말 ‘Greedy 할 뿐인’ 방법이었기 때문에 이 단계에서 최적화될만한 요소가 많았고, 다 돌려보지는 않았지만 대충 점수를 13.15B에서 0.4B정도는 내릴 수 있을거라는 생각이 들었다. 반면, Longitude 기준으로 진행했을 경우 위에서 생각한 Greedy한 방법이 최적해와 상당히 유사한 방법이었기 때문에 Stage #2에서 내려가는 점수가 정말 적어서 의미가 없는 수준이었다. 따라서 여기서 의욕을 잃은데다가 설상가상으로 계절학기 시험까지 겹쳐서 포기하고, 최종적으로 Stage #1에서 만든 12.459B 정도의 Submission을 제출하였다.

Result & Discussion

확실히 이 대회는 정말 재미있는 대회이기는 했지만, 개인적으로 너무 멘붕과 삽질을 한 대회여서 정신적으로 피해가 컸다. 나름 생각을 많이 하고 여러가지 시도를 해보았지만, 아직 다른 사람들과 비교해보았을 때 많이 모자란게 아닌가 싶다. 나의 최종적인 점수는 12.459B였고, 1위 팀의 점수는 12.384B였다. 나는 1127개의 팀중 최종적으로 175위를 하였다.

대회 최종적으로 1위2위를 한 팀의 결과를 링크에서 확인할 수 있다. 두 팀은 모두 SA를 기반으로 탐색을 진행한 듯 하며, 1위 팀은 SA 기반으로 가장 좋은 parameter를 찾는 데에 많은 시간을 소모한듯 하다.

아.. Kaggle 정말 너무 어려운거 같다. ㅋㅋㅋㅋ 앞으로 공부해야할 것도 너무 많고… 더 잘 하고 싶다. 공부에 대한 의욕만 불타오르게 만들어준 대회였다.

모든 실험은 python으로 구현하여 진행하였고, 구현 결과는 내 Github Repo에서 확인할 수 있다.

Advertisements
Kaggle

Kaggle : What’s Cooking?

Kaggle에 대해 알게 된건 올해 초 쯤이었던 것 같다. Kaggle은 일종의 데이터 사이언스 대회 사이트인데, 특정 문제가 주어지면 그 문제를 해결하기 위해 전 세계의 데이터 과학자들이 각자 가지각색의 알고리즘을 통해 문제를 해결하고, 그 성능을 경쟁한다. PS 분야에 Codeforces가 있다면, 데이터 사이언스 분야에서 이 사이트가 비슷한 역할을 하고 있다고 할 수 있겠다. 과제로 주어지는 문제의 종류는 굉장히 다양하며, 개중에는 데이터 분석이 필요한 기업들에서 상금을 걸고 대회를 주최하는 경우도 있다. 이 대회들에 참가하는 사람들은 처음 데이터 사이언스 공부를 시작하는 학생들뿐만 아니라, 관련 대학원생들이나 실제 현장에서 일하는 전문가들까지 굉장히 다양한 사람들이 대회에 참여하고 있다.

Kaggle에 대해 처음 알았을 때부터 굉장히 흥미가 생겼던 것이, 고등학교 때부터 내가 이 분야에 대해 공부하면서 최종적으로 하고싶었던 것들이 이렇게 ‘언뜻 보면 어떻게 해결해야할 지 모르겠는 고난도의 real-life 문제들’ 을  기계 학습 등의 방법을 통해 분석하고, 해결하는 것이었기 때문이다. Kaggle에서 주어지는 문제들은 이러한 나의 흥미에 딱 들어맞았다. 처음 Kaggle에 대해 알게 되었을 때는 관련 지식이 전혀 없었기 때문에, 문제를 풀 방법이 없었다. 그러나 1년간 기계 학습에 대해 공부하면서 이 분야에 대해 아직 미흡하지만 문제들에 도전은 해볼 정도의 지식은 생긴 만큼,  이제 갖가지 Kaggle 대회들에 실제로 참여해보면서 실제 문제들을 해결해보려고 한다.

처음으로 참여한 Kaggle 대회는 ‘What’s Cooking?‘ 이라는 대회이다.  이 대회는 얼마 전인 12월 20일에 종료되었는데, 이 대회에 대해 알게 되고 실제로 참여한 것이 12월 17일이었다. 4일이라는 시간이 다소 짧아 많은 것을 시도해보거나 좋은 성과를 이루어내지는 못했지만, 그래도 이 동안 어떤 식으로 문제에 접근했는지 정리해보고자 한다.

Problem Description

이 문제에 대한 자세한 설명은 위에 첨부한 대회 페이지에서 자세하게 볼 수 있다.
문제의 전체적인 개요는 ‘어떤 음식을 만들기 위한 재료의 목록이 입력되었을 때, 이 음식이 어느 나라(지역)의 음식인지 분류하는’ 것이다. 재료는 양이나 넣는 순서 등은 주어지지 않고 단순히 재료의 이름만이 주어지며, 재료들의 이름이 깔끔하게 주어지지도 않는다(‘salt’, ‘sugar’, ‘eggs’ 등의 단순한 이름도 있지만, ‘eggland’s best® eggs’, ‘reduced-fat sour cream’ 등 브랜드나 부가적 설명이 붙은 재료들도 있고 typo가 있는 재료들도 있다). 이 재료들의 목록을 바탕으로 음식의 ‘cuisine(특정 지역, 나라의 음식)’ 을 분류해야 하는데, cuisine은 southern-us, spanish, french, korean, japanese, brazilian .. 등 20 종류가 있다. 문제를 해결하기 위해 약 4만 개의 음식에 대한 재료 정보를 담은 training data가 주어진다.

Methodology Part #1

이 문제를 보고 가장 기본적으로 떠오르는 접근법은 training data를 돌면서 ingredient의 dictionary를 만든 뒤, 재료 목록을 bag-of-ingredients 등으로 표현한 뒤 Naive Bayes나 Neural Network 등의 분류기를 사용하는 방법일 것이다. 그러나 나는 보다 재료들의 ‘본질적인 특성’ 에 대해 알 수 있는 방법이 있을 것이라고 생각했고, 재료들의 특성을 보다 수치적으로 표현할 수 있다면 이 정보를 이용하여 보다 정교한 분류가 가능할 것이라고 생각했다. 이에 분류에 앞서 각 ingredient의 정보를 수치화하는 방법이 필요하였고, 여기서 떠오른 것이 word2vec 이었다.

word2vec은 자연어처리(NLP)에서 사용되는 방법으로, 특정 단어의 직접적인 의미를 파악할 수 없었던 기존 자연어처리 기법을 비약적으로 발전시킨 방법이다. 이 방법에서는 각각의 단어들을 고차원의 숫자 벡터로 나타내어 단어 자체를 ‘특성화’ 시킨다. 이 방법을 이용하면 이 벡터들을 가지고 더하고 빼는 등 하면서 단어에 대한 추론이나 단어 사이의 관계도 쉽게 다룰 수가 있게 된다. word2vec에 대한 정보를 더 알고싶다면 이 블로그를 참조하면 될 것 같다.

word2vec이 단어 자체를 특성화하듯이, 나도 같은 방법으로 재료 자체를 특성화할 수 있다. 특히 이 문제에서 요리라는 것은 결국 재료의 선형적인 결합이라고 근사화할 수 있다고 생각하였기 때문에, 이렇게 재료를 수치화하여 분석한다면 좋은 결과를 얻을 수 있을 것이라고 생각하였다. 이를 ingredient를 vector로 바꾸는 과정이므로 ing2vec이라고 부르겠다. ing2vec의 학습에는 word2vec의 학습 방법 중 skip-gram을 이용하였는데, word2vec의 학습 자료인 ‘글’과는 달리 요리의 재료에는 딱히 정해진 순서가 없다. 따라서 특정 요리의 특정 재료에 대해 함께 등장하는 재료들을 랜덤하게 고른 다음, 이를 이용하여 학습을 진행하는 방법을 사용하였다. 또한 word2vec 학습에서의 ‘글’과 이 training data가 다른 점은, 글을 학습하는 과정에서는 실제 의미를 알 수 없는 반면 이 training data의 경우에는 cuisine이 무엇인지에 대한 답이 주어진다는 점이다. 이에 착안하여, skip-gram의 중간 hidden layer에 별개로 hidden layer #2 – output layer를 달아주어 cuisine classifying layer를 따로 달아주었다. 이를 이용하면, 각각의 ingredient의 unsupervised feature 말고도 각각의 재료의 ‘cuisine’ 의 특성을 반영하는 요소도 넣어줄 수 있을 것이라고 생각하였다. 결국 ing2vec에서 사용한 네트워크 구조와 학습법은 대충 다음과 같다.

Diagram
– Layer Structure and Cost Definition for ing2vec training.

 레이어 구조와 학습은 theano를 이용하여 구현했는데, 나는 네트워크 크기가 그렇게 크지 않고 학습 데이터도 word2vec의 데이터 사이즈에 비하면 굉장히 작기 때문에 학습이 빠르게 진행될 것이라고 생각하여 negative sampling 등의 방법을 사용하지 않고 굉장히 naive하게 구현하였다. 그런데 생각보다 학습 속도가 느려서, 밤새 학습을 진행했는데도 5 epoch밖에 진행하지 못했다 (물론 실험을 진행한 환경이 열악하기도 했지만).

 이렇게 naive하게 구현하게 ing2vec을 구현하였고, 학습이나 hyperparameter 선정도 제대로 진행되지 못하여 과연 vectorize가 제대로 되었을 지 의문이 들었지만 학습된 결과를 가지고 몇 가지 실험을 진행해보니 어느 정도는 학습이 제대로 진행된 것을 확인할 수 있었다.

coffee, gochujang
Top 10 Closest Ingredients to Target : (1) Coffee, (2) Gochujang Base

 위는 ‘coffee’ 와 ‘gochujang base’ 재료에 대해 가장 가까운 10개의 재료들을 나열한 결과이다. 가깝다는 기준으로는 cosine similarity를 사용하였다. 보다시피 두 결과 모두 유사한 느낌의 재료들이 모여있는 것을 확인할 수 있다. coffee의 경우 espresso, coffee liqueur 등이 있으며, gochujang base의 경우 gochugaru, kimchi, korean chile flakes 등이 있다. 특히 이 ing2vec training은 cuisine의 정보를 가지고도 training 된 만큼, 많은 나라의 음식에서 등장할 수 있는 coffee보다 거의 korean cuisine에만 등장할 gochujang base와 관련 재료들이 훨씬 높은 cosine similarity를 가지고 잘 모여있는 것을 확인할 수 있다.

icecream+coffee
Top 10 Closest Ingredients to ‘Ice cream + Brewed Coffee’

 위 결과는 ice cream과 brewed coffee의 벡터 두개를 합친 벡터에 대해 가장 가까운 10개의 ingredient를 확인한 결과이다. 원래의 두 재료가 1, 2위이며, 3위에는 ‘coffee ice cream’ 재료가 있다. 즉, 벡터를 수치화하여 더해서 새로운 벡터를 만들어도 새로운 재료의 특징을 잘 나타낼 수 있다는 결과를 확인한 것이다(물론 모든 경우에 대해 좋은 결과가 표현되는 것은 아니었다).

Methodology Part #2

ing2vec을 통해 ingredient 자체를 벡터화하는 데에 성공하였으니, 남은 과제는 이를 이용하여 요리를 분류하는 것이다. 문제는 각각의 재료의 특성을 반영하여 어떤 ‘재료의 목록’에 대한 일정한 길이의 벡터를 만들어야 하는데, 이를 정확하게 표현할 수 있는 방법에 대해 고민하고 이것저것 실험해보았지만 딱히 좋은 결과를 얻지는 못했다. 랜덤하게 특정 갯수의 재료를 뽑아서 긴 벡터를 만들고, 이를 이용하여 Simple Deep Layer Network를 만들고 실험해보았으나 이 모델은 학습 시간이 너무 길었고, 기대에 비해 좋은 결과를 얻지 못했다. 그렇다고 각 재료들에 대한 weight를 산정하여 선형적으로 더하기에는 각 재료들에 대한 weight를 얻을 적절한 방법이 떠오르지 않았으며, 각 음식마다 재료가 차지하는 비중이 크게 다를 수 있기 때문에 이 방법은 일단 배제하였다. 결국 최종적으로는 단순히 들어가는 재료들의 벡터들을 다 더하되, 너무 자주 나타나거나 sugar, salt 등의 단순한 조미료, 향신료 등은 weight를 작게 주었다. 또한, 특정 cuisine에서 자주 나타나는 일부 재료들은 weight를 크게 주어서 더해주었다. 이 vector를 같은 norm을 가지도록 normalize해준 벡터를 가지고 특정 ‘재료의 목록의 벡터’를 만들어서, 이를 이용하여 분류를 진행하였다.

분류기로 처음에 사용한 방법은 Deep Layer Network로서, 3-hidden layer짜리 Deep Network를 만들어준 뒤 Leaky ReLU, DropConnect를 적용하여 학습을 시켜주었다. 반면, 40 epoch 정도 지났음에도 불구하고 성능이 72.3%정도밖에 나오지 않았다. 이에 접근법을 달리 생각해보았는데, 이 문제가 결국 확연히 특징이 나누어지는 그룹들을 분류하는 문제인 만큼 단순한 Deep Network보다는 localization 성향이 강한 모델이 성능이 잘 나올 수 있을것 같다고 생각되어 RBFN을 사용해보기로 하였다.

RBFN에서 커널로 Gaussian Kernel을 사용하고 실험해본 결과 커널의 수가 적었음에도 불구하고 Deep Network의 결과보다 좋은 성능을 얻을 수 있었다. 이에 커널의 수를 최대한으로 늘리고 실험하여, RBFN으로 얻을 수 있었던 최대의 결과를 마지막으로 제출하였다.

Result & Discussion

내가 얻을 수 있었던 최고의 성능은 78.8%로서, 총 1416개의 팀 중 560위를 하였다. 1위 팀의 성능은 83.2%로, 나의 성능과 4.4% 정도의 차이가 난다. 솔직히 생각했던 것에 비해 성능이 많이 나오지 않아 다소 실망하긴 했다. 80% 이상의 성능을 얻고 싶었는데, 열심히 이것저것 실험해보았지만 결국 실패했다. 시간이 더 있었고 더 여유롭게 실험할 수 있었다면 80% 정도 성능은 얻을 수 있지 않았을까라고 위로를 하고싶다.

내가 진행한 것 중에 가장 미흡한 부분이 Preprocessing 부분이었던 것 같다. 시간이 많이 없다는 촉박한 느낌에 일단 모델부터 생각해야한다는 마음가짐으로 임했었는데, 일부 상위 순위를 얻은 참가자들의 방법을 보니 재료 이름을 정리하고, 세공하는 데에 많은 공을 들이고 실질적인 분류는 이미 있는 패키지들로 진행하는 방식을 사용했다. 나는 실질적으로 거의 Preprocessing을 진행하지 않아서, 이 부분에서 공을 들였다면 보다 성능이 나아지지 않았을까 싶다.

또 다른 참가자들이 분류기로 xgboost를 많이 이용하던데, 어딘가에서 분류 문제에서 실질적으로 성능이 가장 잘 나오고 가장 많이 이용하는 방법이 random forest라는 말을 얼핏 들은 것 같다. 다음에 분류 문제를 사용하는 대회에 참여할 일이 있다면 xgboost를 한번 사용해볼 계획이다.

이번 대회 및 다른 대회들의 결과를 보면서 느낀 점은 결국 어느 한계까지 이르렀을 때부터는 ensemble 방법을 이용하는 참가자가 많았다는 것이다. 내 개인적으로는 ensemble 하는 것은 아이디어나 아름다움이 있다기 보다는 계산량이나 물량으로 성능을 억지로 올리는 느낌이 들어서 싫지만 현장에선 이러한 방식으로 많이들 사용하는 것 같다. 또 ensemble 하기에는 현재 노트북으로 실험하고 있는 내 실험 환경이 따라주지가 않는데.. 본격적으로 데이터 사이언스를 제대로 해보기 위해서는 좋은 스펙을 갖춘 데스크탑을 사야되는 것인지 고민이 되기도 한다.

구현 코드는 Github의 내 Repository에서 확인할 수 있다.