[번역] 더 많은 데이터가 더 좋은 알고리즘을 이긴다 #2

[번역] 더 많은 데이터가 더 좋은 알고리즘을 이긴다 #2

제가 적은 블로그 포스트 ‘더 많은 데이터가 더 좋은 알고리즘을 이긴다’가 많은 사람들의 관심을 이끌었습니다. 많은 의견들을 개인적으로 다 대답하기 힘들기 때문에, 몇몇은 여기 이 포스트에 남깁니다.

1. 왜 데이터와 알고리즘 중에 하나를 선택해야 하나요? 많은 데이터와 좋은 알고리즘을 같이 사용할 순 없나요?

A. 두가지 대답을 할 수 있겠습니다. 첫번째는 자원의 한정 때문입니다. 예를 들어, 당신이 스타트업을 할때, 어떤 자원에 투자를 할지 결정해야 합니다. – 데이터를 모으거나 허가 받거나, 아니면 박사급 인력을 고용하거나 – 그렇게 되면 일정 수준 전까지는 데이터를 더 많이 모으는 것이 좋을 것 같습니다. 만약 당신의 스타트업이 이러한 결정을 내릴 필요가 없다면, 더 많은 힘을 가질 것입니다.

두번째 이유는 조금 더 미묘합니다. 이것은 좀 더 구조적이고 알고리즘의 계산 복잡도와 연관이 있습니다. 첫 번째 근사치에서 간단한 데이터 마이닝 알고리즘(예를 들어, 페이지 랭크, 마켓 바스켓(연관 데이터 집합 분석), 클러스터링)은 입력값에 대비하여 대략적으로 선형적인 시간이 걸립니다. 반면에 복잡한 기계학습 알고리즘은 제곱, 심지어 세제곱의 시간이 걸립니다.(예를 들어, SVM, SVD) 이처럼 간단한 법칙으로써(Rule of thumb), 큰 데이터 셋(몇 백 기가바이트에서 몇 백 테라바이트까지)에 선형 시간이 걸리는 간단한 알고리즘을 적용하십시오. 반면에 제곱, 세제곱의 계산 시간이 걸리는 알고리즘은 적용이 불가능하기 때문에 연산을 하기 전에 크기를 줄여서 사용해야 합니다.

컴퓨터 공학의 기초적인 부분을 아시는 분들을 위해 설명해 드리자면, 확장 가능한 알고리즘은 정해진 횟수의 순차적인 접근과 데이터 분류가 가능해야만 합니다.(큰 데이터 집합은 반드시 메모리 위에 올라와 있지 않고 디스크에 존재하기 때문에) 랜덤 접근이 필요하거나 N*logN 이상의 계산 복잡도를 가진 대부분의 알고리즘은 큰 데이터 집합에 확장하여 사용하기 힘듭니다. 예를 들어, 맵리듀스와 같은 기법을 사용하여 구현하기가 힘듭니다. 이러한 이유 때문에, 적어도 테라바이트의 램과 같이 비현실적인 비용을 사용하지 않는 이상, 복잡한 알고리즘을 큰 데이터 집합에 적용하는 것은 힘듭니다.

2. 당신의 주장은 단지 독립적인 데이터를 추가하는 것에만 해당이 되나요? (넷플릭스 대회에서 IMDB를 사용한 것처럼) 아니면 똑같은 종류의 데이터의 양만 추가하는 것도 해당하나요? (넷플릭스 대회에서 사용자 평점 데이터를 추가하는 것)

독립적인 데이터를 추가하는 것은 큰 차이를 낳습니다. 예를 들어, 웹 검색의 경우를 보자면, 구글은 웹 페이지에서의 독립적인 데이터인 링크와 앵커 텍스트를 추가함으로써 큰 도약을 이루었습니다. AdWords의 경우에서 보자면, 입찰 정보 중에서 CTR 정보가 독립적인 데이터였습니다. 구글은 거기서 더 나아갔습니다: 그들은 광고 시장의 지배자가 되었고 그렇기 때문에 더 많은 광고 시장 정보를 추가할 수 있었고 그것을 랭킹 시스템에 적용할 수 있었습니다. 구글은 지속적으로 더 많은 데이터를 의지하였고 그러는 동안 그들의 알고리즘의 우수성을 자랑하였습니다.

당신은 같은 종류의 데이터를 추가하는 것은 그리 도움이 되지 않는다고 생각할 수 있습니다. 왜냐하면 수확 체감이 일어날 수 있기 때문입니다. 이것은 어떤 상황에서는 맞을 수 있습니다. 하지만 많은 경우에서는 같은 종류의 데이터를 추가하는 것이 당신이 생각한 것보다 더 큰 차이를 낼 수 있습니다. 데이터가 매우 높은 차원의 공간에 있는 경우가 그렇습니다. 예를 들어 봅시다. 넷플릭스의 경우, 사용자들(혹은 영화)를 차원으로 생각할 수 있고 웹 검색 분야에서는 단어의 k개 gram이 차원이 될 수 있습니다.

어떤 경우에는, 사용 가능한 데이터가 보통 매우 드문드문 있거나 꼬리가 긴 분포를 가집니다. 예를 들어, 넷플릭스의 경우, 영화-사용자 쌍에서 1% 미만 정도만이 평점이 매겨져 있습니다.(한 사용자가 존재하는 많은 영화들에 비해 적은 수의 영화만을 평가하기 때문에) 우리는 수확 체감이 실제로 문제가 되기 전까지는 많은 평점 데이터를 추가할 수 있습니다. – 10배를 더 추가한다고 합시다. 어떤 경우에는 같은 종류의 데이터를 더 많이 추가하는 것이 큰 차이를 보일 수가 있습니다.

3. 학생들이 프로젝트에서 사용한 알고리즘을 조금 더 자세히 설명해 줄 수 있나요?

현재로서는 그럴 계획이 없습니다. 왜냐하면 그 팀들로부터 허락을 받지 못했기 때문입니다. 또한 넷플릭스 대회에서 우승할 기회를 망치고 싶지 않습니다.