Greedy algorithms & Balance algorithms

온라인 알고리즘 (online algorithm) vs 오프라인 알고리즘 (offline algorithm)

온라인 알고리즘: 입력이 들어오기 전까지는 어떤 입력이 들어올지 알 수 없을 때 사용하는 알고리즘

오프라인 알고리즘: 필요한 데이터(입력 값)를 모두 알고있는 상태에서 사용하는 알고리즘

오프라인 알고리즘의 경우에는 정보를 모두 알고있기 때문에 어떤 답이 나오는지 예측 할 수 있지만, 온라인 알고리즘의 경우에는 미래에 대해서 전혀 알지 못하기 때문에 여러가지 가능한 경우들을 많이 고려해봐야한다.

---

Greedy algorithms

위 온,오프라인 알고리즘을 광고 노출과 관련지어서 설명해보자.

광고 노출의 경우에는 검색어와 함께 노출된다. 하지만 사람들이 어떤 검색어로 검색을 할지 예측할 수 없기때문에, 온라인 알고리즘을 사용해야한다.

(그래도 과거에 광고 예산이나 광고의 클릭률을 사용할 수는 있지만, 나중에 어떤 검색어가 많이 생길지는 또 알 수 없다.)

나중에 어떤 검색어가 많아질지 예측하는 것이 어떻게 도움되는지 예시를 보면,

- 제조사A는 'a' 라는 검색어에 10 cent의 예산을 책정했다.

- 제조사B는 'a', 'b' 두 검색어에 20 cent의 예산을 책정했다.

- 두 제조사의 총 예산은 똑같이 $100 이다.

이 때 'a' 라는 검색어가 생기게 되면, 미래를 알 수 없는 경우 예산이 더 높은 B 제조사의 광고가 노출될 것이다.

하지만 지금은 'a' 가 왔지만 이번 달 전체 검색량을 봤을 때 'b'가 많고, 'a'는 적을 것이라고 예상 할 수 있으면 나중에 어차피 B 제조사는 노출이 많이 될 것이기 때문에, 이번 'a' 검색에서는 A 제조사의 광고를 노출시키는게 더 나을 것이다.

이러한 방법은 Greedy algorithms을 따르는 것인데, Greedy 알고리즘은 현재 입력 요소과 과거의 데이터를 바탕으로 결정을 내리는 알고리즘으로 많은 온라인 알고리즘이 이 알고리즘을 따른다.

최악의 경우에는 'a' 검색어가 500번 들어온 후 'b' 검색어가 500번 들어온다고 가정하면, 'a' 검색어가 500번 들어올 때 모두 B 제조사의 광고를 노출시켜 $100를 다 채우게 되면, 'b' 검색어가 올 때는 아무런 광고도 노출되지 않게 된다.

반면에 오프라인 알고리즘이었을 경우, 'a' 검색어 500 번 모두 A 제조사의 광고를 노출시키면 $50의 광고비를 얻을 수 있고, 'b' 검색어에서 B 제조사의 광고를 노출시키면 $100의 광고비를 얻을 수 있어 총 $150의 광고비가 들어오게 된다.

이 때문에 Greedy algorithms 는 큰 단점이 생기게 된다.

---

The balance algorithm

Greedy algorithm의 단점을 보완해주기 위해 나온것이 balance algorithm 이다.

원리는 간단한데, 검색어가 들어왔을 때 해당 검색어에 예산을 책정한 제조사들 중에서 예산이 많이 남은 제조사의 광고를 먼저 내보내는 방법이다.

이때 Optimal solution 대비 balance algorithm으로 선택된 광고는 3/4 이다. 이때 3/4를 competitive ratio라고 한다.

(광고주가 많아지면 competitive ratio는 0.63(=1-1/e)까지 낮아질 수 있다.)

여기서 증명은 하지 않겠지만, 이 방법을 사용하면, 제조사 모두 예산의 절반 이상씩 사용할 수 있게 된다.

광고주와 검색어(query) 가 많아지면 어떻게 될까?

Optimal case

Balance algorithm

An의 광고주가 있고, 많은 검색어가 있으며 Optimal case의 경우 모든 예산을 다 소모할 수 있다고 가정하자.

Balance algorithm을 사용하게 되면, 위 그림처럼 광고가 배정될 것이다.

이 때 광고 예산 할당은 q1 은 전체예산을 광고주의 수로 나눈 B/n 이고, q2는 A1에 할당되지 않으므로, A1을 제외한 광고주 수인 n-1로 나눈 수 B/(n-1) 이며 나머지도 같은 방법으로 값이 증가한다.

An 광고주의 예산이 바닥나려면

를 만족해야한다. Euler 근사에 의해 다음을 만족한다.

따라서 

일 때 An 광고주의 예산이 전부 소진되게 된다.

j는 An에 할당된 검색어(query)의 개수와 대응하기 때문에, 총 소요 예산은 B x N(1-1/e) 라고 생각할 수 있다.

따라서 Optimal 케이스는 총 소요 예산이 B x N 이므로 이 경우 competitive ratio는 (1-1/e ~ 0.63) 라고 볼 수 있다.

 

*stanford/mining massive data sets 교재 참고