티스토리 뷰

반응형

1. E-Greedy Algorithm(입실론 그리디 알고리즘)이란?


[ Greedy Algorithm(그리디 알고리즘) ]

Greedy Algorithm은 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 즉, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다. 물론 당연히 미래의 가치를 고려하지 않기 때문에 항상 최선의 결과를 반환하지는 않는다.

예를 들어 주사위 3개를 굴린 결과가 아래와 같고, 가장 높은 숫자를 반환할 주사위를 선택한다고 가정하자.

  • 주사위1: 5

  • 주사위2: 3

  • 주사위3: 1

  • 주사위4: 6

 

 

Greedy Algorithm에 따르면 우리는 주사위 4를 선택해야한다. 하지만 다음에 주사위4를 골라도 최상의 결과가 반환될 것이라는 확신을 가질수는 없는데, 그러한 이유는 이 주사위를 한번씩 테스트했기 때문이다. 즉, 탐험(Exploration)이 충분히 이루어지지 않았기 때문이다.

 

[ Greedy Algorithm(그리디 알고리즘) 한장 요약 ]

 

 

 

[ E-Greedy Algorithm(입실론 그리디 알고리즘) ]

탐험이 부족했던 Greedy Algorithm을 개선시킨 전략으로, 일정한 확률로 랜덤으로 주사위를 선택하도록 하는 것이다. 예를 들어 일정한 확률을 위한 도구로 동전을 사용한다고 할 때, 동전의 앞면이 나오면 랜덤으로 주사위를 선택하고 동전의 뒷면이 나오면 이전에 최선의 결과를 냈던 주사위를 선택하는 것이다. 이러한 알고리즘은 Epsilon-Greedy(E-Greedy) 알고리즘이라고 부르며, 판단을 위해 사용된 동전의 앞면이 나올 확률 50%는 Epsilon이라는 HyperParameter가 된다. Epsilon이라는 HyperParameter는 0~1 사이의 변수로, 위의 예제에서는 e가 0.5에 해당되며 50%의 확률로는 주사위 6을 선택하고, 50%의 확률로는 무작위로 주사위를 선택하게 된다.

 

[ E-Greedy Algorithm(입실론 그리디 알고리즘) 한장 요약 ]

 

 

 

 

 

 

 

참고 자료

반응형
댓글
댓글쓰기 폼
  • 준하 epsilon = 0.5일 때를 예로 드시면 epsilon이 만큼의 확률로 무작위 선택을 하는 건지 아니면 특정값을 선택하는 건지 헷갈리지 않을까요 2020.04.03 19:14
  • 망나니개발자 제가 정확히 어떻게 헷갈릴 수 있는지 이해를 못했습니다ㅜㅜ 자세히 설명해주실 수 있을까요!??!? 2020.04.06 12:43 신고
반응형
공지사항
Total
1,765,501
Today
382
Yesterday
4,771
TAG more
«   2021/12   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
글 보관함