끄적끄적

 여기서는 앞의 MDP와는 달리, 우리의 전략이 자신의 state $s$ 뿐 아니라, 상대 플레이어들의 전략으로부터도 영향을 받는다. 여기서는 플레이어가 둘(나 agent와 상대 opp)인 제로섬 게임(내가 $10을 따면, 상대는$10을 잃는다는 의미에서의)을 예로 설명한다.

Game

 기본적인 접근법은 searching problem과 MDP와 유사하다. searching problem은, 현재 나의 state $s$ 노드가 $succ(s,a)$들을 자식노드로 같는 식으로 트리를 만들고 그 트리를 탐사함으로써 최적의 선택(action $a$)를 찾는다는 것을 의미하며, MDP처럼 state $s$에서 취할 수 있는 actions $a$들이 존재한다. 단지 여기서는 state $s$가 $Players(s)$에 속해있다. 또한, MDP에서는 $a$를 취할 때마다 cost가 존재했다면, 여기서는 $s$가 end state에 도달해야 Utility(s)가 존재한다( 게임이 끝나야 내가 내가 이겼는지 졌는지 알고 그에 대한 보상을 받는다). 또한, agent와 opp가 번갈아가며 $s$를 결정하고 둘의 $s$는 서로에게 fully observable하다.

 이 강의에서 사용한 예시는 다음과 같다. A박스에는 -50과 50이, B박스에는 1과 3이, C박스에는 -5와 15가 들어있으며, agent는 A, B, C 중에서 하나를 고르며, opp는 agent가 고른 박스에 들어있는 2개의 공 중 하나를 고른다. 따라서 당연히 공에 써있는 값을 최대화하기 위한 agent의 전략은 opp의 전략에 의존할 것이다. opp가 둘 중 아무거나 고른다면 박스안의 공의 평균이 가장 높은 C박스를 고르는 것이 최선의 전략일 것이고, opp가 둘 중 낮은 값의 공을 뽑는다면 들어있는 공의 최솟값이 가장 큰 B박스를 고르는 것이 최선일 것이다. 이 강의의 목적은 이러한 전략을 모델링하고 컴퓨팅을 통해서 최적의 전략을 찾는것이다.

 이 게임에서의 Value $V_{eval}$은 다음과 같다.

 $V_{eval}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \sum_{a \in Actions(s)} \pi_{agent}(s,a)V_{eval}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{eval}(Succ(s,a)), & Player(s) = opp \end{cases}$

 2, 3번째 조건은, 누구의 턴이냐에 따라 누구의 policy를 기반으로 V값을 계산해야 하는지 나타낸다.

Expectimax

 agent가 자신의 전략을 정할 때, 가장 기본적인 전략은 내 이득을 최대화하는 선택을 하는 것이다. 이러한 선택을 하는 노드를 max노드라 한다. 이러한 max노드에서는 가장 큰 값을 같는 자식 노드를 취한다. 즉, MDP의 예제에서처럼 가능한 모든 자식노드들에 대한 평균값을 V 값으로 취하는 것이 아닌, 최댓값을 갖는 자식 노드를 취하며, 이러한 방식에 의해 얻어진 V값을 expectimax value $V_{exptmax}(s)$라 한다. 위의 예제에서 상자를 고르면 안의 두 공 중 랜덤하게 하나가 선택된다면 $V_{exptmax}(s) = 5$ 가 된다(두 공 중 하나가 임의로 선택되므로 평균값이 가장 높은 상자를 취한다). Expectimax를 취하는 경우의 V 값은 다음과 같다.

 $V_{exptmax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{exptmax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{exptmax}(Succ(s,a)), & Player(s) = opp \end{cases}$

  이 경우의 전략을 나타내면 아래와 같다.

$\pi_{exptmax(r)} = arg \max_{a \in Actions(s)}mean_{a \in Actions(s)} V_{eval}(Succ(s,a))$ (agent의 전략)

$\pi_{r} = \begin{cases} \min_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \\ \max_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \end{cases}$ (opp의 전략)

 즉, opp는 아무거나 뽑고, agent의 경우에는 공들의 평균값이 가장 높은 것을 고른다.

 이러한 접근의 문제점은 상대방의 전략이 $\pi_r$이 아니면 제대로 대처할 수 없다는 것이다. 위의 예제를 예로 들면, 상대가 두 공 중 임의로 공을 뽑지 않고 두 공 중 값이 낮은 공만을 뽑을 경우 제대로 대처할 수 없다.

Minimax

 위의 문제를 해결하기 위한 전략이 Minimax 이다. 즉, 최악의 경우만을 상정하여 내가 취할 전략을 정하는 것이다. 위의 예제에서는 상대가 값이 낮은 공만을 뽑을거라고 생각하며 $a$를 취하게 되므로 공의 값들 중 낮은 값이 가장 큰 B 상자를 택하게 될 것이다$V_{minimax}(s) = 1$. 이러한 경우의 V값은 아래와 같이 주어진다.

 $V_{minimax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{minimax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \min_{a \in Actions(s)} \pi_{opp}(s,a)V_{minimax}(Succ(s,a)), & Player(s) = opp \end{cases}$

 즉, 상대는 최솟값만 선택하므로, 나는 최솟값이 가장 큰 상자를 선택하는 것이다. minimax에서의 전략 $\pi$는 다음과 같이 주어진다.

$\pi_{max} = arg \max_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (agent의 전략)

$\pi_{min} = arg \min_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (opp의 전략)

비교

 이제 agent와 opp의 전략에 따라 $V$가 어떻게 달라지는지 보겠다. 먼저, $\pi_{opp} = \pi_{r}$ 인 경우에는

$V(\pi_{exptmax{r}},\pi_r) = 5, V(\pi_{max},\pi_r) = 2$ 가 된다. 또한, $\pi_{opp} = \pi_{min}$ 인 경우에는, $V(\pi_{exptmax{r}},\pi_{min}) = -5, V(\pi_{max},\pi_{min}) = 1$ 가 되다. 즉, agent가 opp의 전략을 제대로 알지 못하는 경우에는 손해를 볼 수 있다.   

Computation

 위와 같은 단발성 게임이 아닌 체스 등과 같이 상대와 내가 계속해서 Action을 취하는 경우 나의 최적의 선택을 찾기 위해서는 위와 같은 트리를 만든 후, 가장 최적의 해를 주는 branch를 찾으면 될 것이다. 하지만, 여기서 문제는 tree가 너무 커지면 모든 가능성에 대해서 탐사하는 것이 현실적으로 불가능하거나 너무 비효율적이라는 것이다. 선택지가 b개이고, 트리의 깊이가 d까지 내려갈 경우에 완전탐색을 하게 되면 시간복잡도는 $O(b^{2d})$이 된다. 여기서 해결책이 두가지가 있는데, 첫번째는 내가 게임에 대하여 잘 알고 있을 경우, 트리를 탐색하지 않고, 현 상황을 분석하여 적절한 점수를 주어 결괏값을 예측하는 것이다. 예를 들어 체스의 경우, 왕의 안전성, 가지고 있는 말의 개수, 움직일 수 있는 말의 개수 등을 이용하여 각 $a$에 대한 Reward를 계산하는 방법이 있다. 두번째는 tree의 필요없는 가지들을 쳐내는 것이다.

유형 : 이분탐색

문제풀이:

 모든 요소 i*j를 리스트에 넣고 정렬해서 K번째를 반환하면 시간복잡도가 O(N^2)이 되어 시간초과가 뜬다. 따라서 다른 방법을 생각해야 한다.

1. N*N행렬이라 하면, 1번째 행(1부터)의 요소는 [1, 2, ... , N]이 되고, 2번째 행의 요소는 [2*1, 2*2, ..., 2*N]이 된다. 즉, i번째 행의 요소는 [i*1, i*2, ... i*N]이 되고, i번째 행에는 어떤 값 x보다 작은 값이 x//i개 (x가 i*N보다 큰 경우에는 N개) 존재하게 된다.

2. 따라서 N*N행렬에서 x보다 작은 값은 모든 i(1~N)에 대한 x//i의 합이 된다.

3. 이 값을 check(x)라 하면, x를 1과 N^2 사이에서 이분탐색하며 check(x)가 K보다 크거나 같은 가장 작은 값을 반환한다.

Python Code

문제 링크

문제풀이

1. start를 전에 "+" 또는 "-" 연산자의 인덱스라고 하면, end는 start 이후의 첫 "+" 또는 "-" 연산자가 있는 인덱스입니다.

2. start부터 end까지의 sub string을 term 이라 하면, terms에서 x의 개수와 계수를 찾아줍니다. 계수는 맨앞에서부터 term의 length에서 x의 개수를 빼준 값까지의 term의 sub string이 됩니다. 예를들면, 6xx라 하면 len(term)은 3이고, xx는 2 이므로 term[:3-2]를 해준 후 정수로 파싱해주면 됩니다. x의 개수의 경우, 저는 collections.Counter를 사용하였습니다. 계수가 존재하지 않는 경우에는 1이 됩니다.

3. 적분한 값의 계수는 원래 계수를 x의 개수에서 1을 더해준 값으로 나누어준 값이 됩니다. 또한, 적분한 계수가 1이라면 생략해주어야합니다. 또한 뒤에 x를 하나 더 붙여주면 됩니다.

Python Code

line 15 : 주어진 식이 "-"로 시작하는 경우입니다.

line 30 : term으로 주어지는 eq[start:end]는 부호를 제외한 숫자와 x만으로 구성된 항입니다. 부호의 경우 line 32에서 뒤의 부호를 붙여주게 됩니다.

line 35 : 저처럼 풀 경우에는 마지막 항이 while문에서 처리되지 않으므로, 따로 처리해주어야합니다.

line 23 : 0이 입력값으로 주어지는 경우 0x+W로 반환되는 것에 대한 예외처리입니다.

문제링크

요약

 LMS 알고리즘은 가장 유명한 학습법 중 하나이며, LMS 알고리즘은 성능이 좋으면서도, 빠르고 효율적이며 코드 짜기도 쉽다. 본 포스트에서는 선형회귀만을 다룹니다.

Adpative Filter

 LMS 알고리즘은 adaptive filter라고 할 수 있으며 filtering process와 adaptive process가 합쳐져 있다. $w$와 i번째 샘플 $x(i)$로부터 예상된 결과가 $y(i)$라 할때, $y(i)$와 실제 정답 $d(i)$를 비교함으로써 error $e(i)$를 얻는 과정이 filtering process이고, $e(i)$로부터 $w$를 적절하게 수정해 나가는 과정이 adaptive process이다.

 어떤 이상적인 분류기의 모델로서 optimal solution $w*$가 있다고 할때, 실제 $w*$는 알 수가 없으므로, 우리의 목표는 가지고 있는 sample들로부터 error를 가장 작게 만드는 $w$를 찾는 것이다. $w$에 관한 error를 $\mathcal{E}$라 하면, $\mathcal{E}(w*) <= \mathcal{E}(w)$ 일 것이며, $w*$가 optimal solution일 조건은 $\triangledown\mathcal{E}(w*) = 0$ 이다.

 $w$가 $w*$에 가까워지도록 하는 adaptive filter는 iterative descent의 방식으로 진행된다. 즉 i번째 iteration에서의 error를 $\mathcal{E}(w(n))$라 하면 $\mathcal{E}(w(n+1)) < \mathcal{E}(w(n))$가 된다.

Steepest Decsent Algorithm

 말그대로 가장 가파른 곳으로 내려가는 알고리즘으로, $w$에 대한 에러 $\mathcal{E}(w)$의 경사가 가장 가파른 곳으로 내려가는 알고리즘으로, 

 $w(n+1) = w(n) - \eta$\triangledown\mathcal{E}(w)$

 $\triangle w(n) = w(n+1) = w(n) = - \eta$\triangledown\mathcal{E}(w) = -\eta g(n)$

가 된다. 이러한 방식을 통해 $w$가 $w*$에 가까워지는 이유는 다음과 같이 error를 테일러 전개 함으로써 알 수 있다.

 $\mathcal{E}(w(n+1)) = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \mathcal{O}((\triangle w(n))^2) \simeq \mathcal{E}(w(n)) - \eta g^T(n)g(n) = \mathcal{E}(w(n)) - \eta \parallel g(n) \parallel^2$

 $\therefore \mathcal{E}(w(n+1)) < \mathcal{E}(w(n))$

Newton's Method

 이번에는 에러 함수를 이차항까지 테일러전개를 하면 아래와 같다.

 $\triangle(\mathcal{E}(w(n))) = \mathcal{E}(w(n+1)) - \mathcal{E}(w(n))$

        $= \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \frac{1}{2} \triangledown^2 \mathcal{E}(w(n))^T (\triangle w(n))^2 + \mathcal{O}((\triangle w(n))^3) - \mathcal{E}(w(n))$

        $= g^T(n) \triangle w(n) + \frac{1}{2} \triangle w^T(n) H(n) \triangle w(n)$, H(n)은 헤세 행렬 ( H(n) = \triangledown^2 \mathcal{E}(w(n))

 즉, $g(n) + H(n) \triangle w(n) =0$ 일때 에러의 차가 최소가 된다.

$\therefore w(n+1) = w(n) - H^{-1}(n)g(n)$

Gauss-Newton Method

 Todo

The Least Mean Square Algorithm

 에러 함수를 다음과 같이 정의하면

 $\mathcal{E}(w) = \frac{1}{2} e^2(n)$,

 gradient vector는 다음과 같다.

 $g(n) = \frac{\partial \mathcal{E}(w)}{\partial w} = e(n) \frac{\partial e(n)}{\partial w} = - e(n)x(n)$

 여기서 Steepest Descent를 활용하여 $w$를 업데이트 시키면 다음과 같다.

 $w(n+1) = w(n) + \eta x(n)e(n)$

LMS 알고리즘은 environment에 대한 정보가 하나도 없어도 적용이 가능하다.

코드로 구현한 내용은 전에 작성한 포스트에 있습니다.

13199 치킨 먹고 싶다 문제가 안풀려서 고생하다가 이 문제의 어려운 버전이라는 글이 있어서 이 문제부터 풀어보았는데, 이 문제는 너무 쉬웠다...

문제풀이

1일차 잠들기 전 높이는 A

2일차 잠들기 전 높이는 2A-B

3일차 잠들기 전 높이는 3A-2B

즉, N일차 잠들기 전의 높이는 NA-(N-1)B이고 NA-(N-1)B>V인 N의 최솟값을 찾으면 된다.

위의 식을 N에 대하여 정리하면 

N = (V-B)/(A-B)

Python Code

문제링크

유형 : dp

 처음에는 dfs를 이용하여 모든 경로를 탐색했으나 당연히 시간초과가 나왔다.

문제풀이

1. dp를 활용해야 하는데, dp[r][c]는 (r,c)에 올 수 있는 경우의 수이다. (r,c)에서 갈 수 있는 길이가 a라 하면, (r+a,c), (r,c+a) 두 가지 경우가 가능하다. 두 경우 가능한 경우의 dp 값에 dp[r][c]를 더해주면 된다.

2. 1의 과정을 (0,0)부터 (n-1,n-1)까지 반복한다.

요약

 모든 경로를 다 고려할 필요 없이, dp를 이용하여 (r,c)에서 (r',c')으로 이동한다고 하면, dp[r'][c'] += dp[r][c]를 해주면 중복되는 경로들을 다시 탐색하지 않아도 된다.

Python Code

line 3 : 0,0에서 시작할 것이니, dp[0][0]은 0이 아닌 1로 해주어야한다.

line 7 : (r,c)에서 갈 수 있는 경우가 0이거나 (r,c)에 도착 할 수 있는 경우의 수가 0이라면 고려할 필요가 없다.

line 12, 14 : 위에서 언급한 dp[r'][c'] += dp[r][c] 과정.

 길이가 N인 정사각형에 대하여 이중 포문을 도므로 시간복잡도는 O(N^2)이 된다.

문제 링크

재귀함수

 함수 안에서 자기 자신을 다시 호출하는 함수로, 무한 루프에 빠지지 않기 위해서는 더이상 자기자신을 호출하지 않는 종료 조건을 잘 정해야 한다.

문제풀이

 입력받은 N만큼 자기 자신을 호출하면 되므로, 재귀함수의 파라미터로 목표 depth와 현재 depth를 준 후, 자기 자신을 호출할 때는 depth에 1을 더해서 호출한다.

 depth가 N보다 작은 경우에는 아래의 글들을 프린트하되, 각 문장 앞에 ____를 depth번 반복하여 프린트 한 후, depth에 1을 더해서 자기자신을 다시 호출한다.

"재귀함수가 뭔가요?"

"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.

마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.

그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."

 반면 depth가 N일 경우에는 아래의 문장 앞에 ____를 depth번 반복하여 프린트하고, 함수 호출은 하지 않는다.

"재귀함수가 뭔가요?"

"재귀함수는 자기 자신을 호출하는 함수라네"

마지막으로, 모든 depth에서 위의 경우에는 함수 호출을 한 후, 아래 경우에는 주어진 두 줄을 프린트 한 후 앞에 ____를 depth번 반복하여 프린트 한후, 아래의 문장을 프린트한다.

라고 답변하였지.

Python Code

문제풀이

 works의 요소들의 제곱의 합이 가장 작게 하면 되는 문제로, works 요소들에서 주어진 n만큼을 적절히 빼서 works의 요소들의 최댓값을 가장 작게 만들어주면 된다. 따라서 가장 단순한 풀이로는, works를 정렬해가며 최댓값인 요소에서 1씩 빼는 과정을 n번 반복하면 된다. 

 하지만 위와 같은 방법으로 풀게되면, 당연히 효율이 좋지 못하므로, 더 효율적인 풀이를 고려해야한다. 제 풀이는 다음과 같습니다.

 1. works를 정렬한 후, i를 1씩 늘려가며 works의 i-1번째 요소까지의 모든 요소들의 값을 같게 하는데,

 1-1. 만약 works의 0번째부터 i-1번째 요소들을 모두 i번째 요소와 같도록 만들 수 있다면 바꾼 후, 바꿔준 만큼 n에서 빼줍니다.

 1-2. 불가능하다면 1과정을 멈춘다.

 2. 1-1을 거쳐 값을 똑같이 맞춰줄 수 있었던 요소들에 대하여 남은 n을 공평하게 배분한다.

 3. 남은 값들을 앞에서부터 1씩 배분한다.

예시

 works = [3,5,7], n = 3인 경우를 예로 들어보면 다음과 같다.

알고리즘이 동작하는 과정을 편의상 t라고 했습니다. 

t=0은 과정 1의 정렬을 하는 과정입니다.

t=1은 works의 두번째 요소(works[1])까지의 요소들의 값들이 같도록 만드는 과정입니다. works[0]을  works[1]과 같도록 만들 수 있으므로 바꾸어주고 n에서 works[0]-works[1]을 빼줍니다. i가 2 이상이라면 i*(works[i-1]-works[i])를 빼주면 됩니다. 

t=2는 과정 2인데, 0이 아닌 요소가 3개인데, n은 1이므로 이 과정은 진행되지 않지만, 이해를 돕기위해 넣었습니다.

t=3은 과정 3으로, 남아있는 n을 앞에서부터 1씩 처리하는 과정입니다.

이제 t=3에서의 요소의 값들을 제곱하여 반환하면 됩니다.

* 시간복잡도는 최악의 경우 for문 3번으로 끝나므로, works의 길이를 N이라 하면 O(NlonN + N)이 됩니다(정확히는 O(NlonN + 3N)).

Python Code

line 6의 for문이 과정 1(equal index까지 요소들의 값이 같게 됩니다.),

line 19이 n을 공평하게 처리하는 부분,

line 23이 남은 n을 1씩 앞에서부터 처리하는 부분입니다.

문제링크