cdjs의 코딩 공부방

1. x를 다음과 같이 정의할 때, ^q(s, a, w) = wTx(s, a)를 만족한다면 section 2의 (1) 식과 (2) 식이 동일하다는 것을 증명하시오. [3점]

(수식이 너무 많아서 다 쓰긴 좀... 그냥 위에 있는거 대충 보고 합시다...)

sol)

어차피 x(s, a)ₛ',ₐ' 가 0이 되면 w가 뭐든간에 ^q은 0이 되니까,

x(s, a)ₛ,ₐ = 1인 경우를 (2)번 식에 적용하면,

wₛ,ₐ= wₛ,ₐ + α(r + 𝛾max wₛ,ₐ - wₛ,ₐ)∇wₛ,ₐ wₛ,ₐ 

(수식 ㅂㄷㅂㄷ;;; 대충 뭔뜻인지 이해하셨으면 좋겠는데... 그냥 ^q를 w로 바꾸고, w도 wₛ,ₐ로 바꾼 식...)

이 때, ∇wₛ,ₐ wₛ,ₐ = 1이므로 다시 정리하면

wₛ,ₐ= wₛ,ₐ + α(r + 𝛾max wₛ',ₐ' - wₛ,ₐ)

그리고 이를 다시 Q(s, a)로 정리하면 (1)번 식이 나온다.

2. qˆ(s, a, w) = wT x(s, a)이라고 할 때, value function parameter w ∈ Rⁿ에 대한 미분값을 구하고, w의 update rule을 적으시오. [3점]

sol) q^(s, a, w) = wTx(s, a)라고 했으므로,

∇w q^(s, a, w) = ∇w wTx(s, a) = x(s, a) 이다.

그리고 update rule은 아까 section 2 의 (2)번 식에 따라,

w = w + α(r + 𝛾max a0∈A qˆ(s 0 , a0 , w) − qˆ(s, a, w) )x(s, a)

가 된다. (그냥 뒤에 ∇w q^(s, a, w) 부분을 x(s,a)로 바꿈)

3. [코딩] 이제 tensorflow로 linear approximation을 구현할 것이다. 이 문제는 나머지 assignment 문제를 풀기 위한 pipeline을 작성하게 할 것이다. q2linear.py의 함수 중 다음의 함수를 구현할 것이다(q2linear.py를 읽어보라) :

• add_placeholders_op

• get_q_values_op

• add_update_target_op

• add_loss_op

• add_optimizer_op

작성한 코드를 python q2 linear.py 명령어를 사용해서 CPU에서 돌려보아라. 그러면 test environment에서 linear approximation을 실행시킬 것이다. 실행하는데 대략 1분에서 2분 정도 걸릴 것이다.

class Linear(DQN):
    """
    Implement Fully Connected with Tensorflow
    """

    def add_placeholders_op(self):
        """
        Adds placeholders to the graph

        These placeholders are used as inputs to the rest of the model and will be fed
        data during training.
        """
        # this information might be useful
        state_shape = list(self.env.observation_space.shape)
        ##############################################################
        """
        TODO: 
            Add placeholders:
            Remember that we stack 4 consecutive frames together.
                - self.s: batch of states, type = uint8
                    shape = (batch_size, img height, img width, nchannels x config.state_history)
                - self.a: batch of actions, type = int32
                    shape = (batch_size)
                - self.r: batch of rewards, type = float32
                    shape = (batch_size)
                - self.sp: batch of next states, type = uint8
                    shape = (batch_size, img height, img width, nchannels x config.state_history)
                - self.done_mask: batch of done, type = bool
                    shape = (batch_size)
                - self.lr: learning rate, type = float32
        
        (Don't change the variable names!)
        
        HINT: 
            Variables from config are accessible with self.config.variable_name.
            Check the use of None in the dimension for tensorflow placeholders.
            You can also use the state_shape computed above.
        """
        ##############################################################
        ################YOUR CODE HERE (6-15 lines) ##################
        batch_size = 5
        img_height = state_shape[0]
        img_width = state_shape[1]
        n_channels = state_shape[2]
        self.s = tf.placeholder(dtype=tf.uint8,
                                shape=[None, img_height, img_width, n_channels * config.state_history],
                                name='state')
        self.a = tf.placeholder(dtype=tf.int32, shape=[None], name='action')
        self.r = tf.placeholder(dtype=tf.float32, shape=[None], name='reward')
        self.sp = tf.placeholder(dtype=tf.uint8,
                                 shape=[None, img_height, img_width, n_channels * config.state_history],
                                 name='next_state')
        self.done_mask = tf.placeholder(dtype=tf.bool, shape=[None], name='done_mask')
        self.lr = tf.placeholder(dtype=tf.float32, shape=(), name='lr')

        ##############################################################
        ######################## END YOUR CODE #######################

    def get_q_values_op(self, state, scope, reuse=False):
        """
        Returns Q values for all actions

        Args:
            state: (tf tensor)
                shape = (batch_size, img height, img width, nchannels x config.state_history)
            scope: (string) scope name, that specifies if target network or not
            reuse: (bool) reuse of variables in the scope

        Returns:
            out: (tf tensor) of shape = (batch_size, num_actions)
        """
        # this information might be useful
        num_actions = self.env.action_space.n

        ##############################################################
        """
        TODO: 
            Implement a fully connected with no hidden layer (linear
            approximation with bias) using tensorflow.

        HINT: 
            - You may find the following functions useful:
                - tf.layers.flatten
                - tf.layers.dense

            - Make sure to also specify the scope and reuse
        """
        ##############################################################
        ################ YOUR CODE HERE - 2-3 lines ##################

        input = tf.layers.flatten(state, name=scope)
        out = tf.layers.dense(input, num_actions, name=scope, reuse=reuse)

        ##############################################################
        ######################## END YOUR CODE #######################

        return out

    def add_update_target_op(self, q_scope, target_q_scope):
        """
        update_target_op will be called periodically
        to copy Q network weights to target Q network

        Remember that in DQN, we maintain two identical Q networks with
        2 different sets of weights. In tensorflow, we distinguish them
        with two different scopes. If you're not familiar with the scope mechanism
        in tensorflow, read the docs
        https://www.tensorflow.org/programmers_guide/variable_scope

        Periodically, we need to update all the weights of the Q network
        and assign them with the values from the regular network.
        Args:
            q_scope: (string) name of the scope of variables for q
            target_q_scope: (string) name of the scope of variables
                        for the target network
        """
        ##############################################################
        """
        TODO: 
            Add an operator self.update_target_op that for each variable in
            tf.GraphKeys.GLOBAL_VARIABLES that is in q_scope, assigns its
            value to the corresponding variable in target_q_scope

        HINT: 
            You may find the following functions useful:
                - tf.get_collection
                - tf.assign
                - tf.group (the * operator can be used to unpack a list)

        (be sure that you set self.update_target_op)
        """
        ##############################################################
        ################### YOUR CODE HERE - 5-10 lines #############

        q = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=q_scope)
        target_q = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=target_q_scope)

        assign = [tf.assign(target_q[i], q[i]) for i in range(len(q))]
        self.update_target_op = tf.group(*assign)

        pass

        ##############################################################
        ######################## END YOUR CODE #######################

    def add_loss_op(self, q, target_q):
        """
        Sets the loss of a batch, self.loss is a scalar

        Args:
            q: (tf tensor) shape = (batch_size, num_actions)
            target_q: (tf tensor) shape = (batch_size, num_actions)
        """
        # you may need this variable
        num_actions = self.env.action_space.n
        ##############################################################
        """
        TODO: 
            The loss for an example is defined as:
                Q_samp(s) = r if done
                          = r + gamma * max_a' Q_target(s', a')
                loss = (Q_samp(s) - Q(s, a))^2 
        HINT: 
            - Config variables are accessible through self.config
            - You can access placeholders like self.a (for actions)
                self.r (rewards) or self.done_mask for instance
            - You may find the following functions useful
                - tf.cast
                - tf.reduce_max
                - tf.reduce_sum
                - tf.one_hot
                - tf.squared_difference
                - tf.reduce_mean
        """
        ##############################################################
        ##################### YOUR CODE HERE - 4-5 lines #############

        notdone = 1 - tf.cast(self.done_mask, tf.float32)
        action = tf.one_hot(self.a, num_actions)
        q_samp = self.r + notdone * (self.config.gamma * tf.reduce_max(target_q, axis=1))
        q_s = tf.reduce_sum(q * action, axis=1)
        self.loss = tf.reduce_mean((q_samp - q_s)**2)
        # self.loss = tf.squared_difference(q_samp, q_s)

        ##############################################################
        ######################## END YOUR CODE #######################

    def add_optimizer_op(self, scope):
        """
        Set self.train_op and self.grad_norm
        Args:
            scope: (string) scope name, that specifies if target network or not
        """

        ##############################################################
        """
        TODO: 
            1. get Adam Optimizer
            2. compute grads with respect to variables in scope for self.loss
            3. if self.config.grad_clip is True, then clip the grads
                by norm using self.config.clip_val 
            4. apply the gradients and store the train op in self.train_op
                (sess.run(train_op) must update the variables)
            5. compute the global norm of the gradients (which are not None) and store 
                this scalar in self.grad_norm

        HINT: you may find the following functions useful
            - tf.get_collection
            - optimizer.compute_gradients
            - tf.clip_by_norm
            - optimizer.apply_gradients
            - tf.global_norm
             
             you can access config variables by writing self.config.variable_name
        """
        ##############################################################
        #################### YOUR CODE HERE - 8-12 lines #############

        optimizer = tf.train.AdamOptimizer(learning_rate=self.lr)
        variable = tf.get_collection(tf.GraphKeys.TRAINABLE_VARIABLES, scope=scope)
        gradient = optimizer.compute_gradients(self.loss, variable)
        if self.config.grad_clip is True:
            clip_grad = [(tf.clip_by_norm(i[0], self.config.clip_val), i[1]) for i in gradient]
        self.train_op = optimizer.apply_gradients(clip_grad)

        self.grad_norm = tf.global_norm([i[0] for i in clip_grad])
        pass

        ##############################################################
        ######################## END YOUR CODE #######################

그냥 Linear class 전부 올리겠습니다. 어차피 저거 처음부터 끝까지 다 짜야되는거라;

파이썬 사용법에 그렇게 익숙치 않고, 텐서플로우를 잘 사용하지 않다 보니까 이것저것 다 찾아보며 하느라 힘들었네요.

4. test environment에서 얻을 수 있는 최적의 reward를 얻었는가? results/q2 linear에 있는 scores.png 파일을 첨부하여라. [5점]

sol...?) section 1에서 봤던 최적의 reward 4.1이 나오는 모습이다.

앞으로 얼마 안남았다.. 달려봅시다!

위에 나온 대부분의 내용들은 전 강의 DQN에 나와있는 내용이므로, 설명은 생략하겠습니다.

사실, 위에 나오는 건 그냥 배웠던 거 다시 설명하는 것 뿐이라...

설명하지 않았던 부분만 간단히 짚고 넘어간다.

실행 중에 (훈련하는 중에?), 버퍼에 (s, a, r, s') transitions을 집어넣는다. 새로 transitions가 들어오면 오래 된 transitions는 삭제된다. 파라미터들을 SGD update를 사용해 파라미터를 update할 때, 버퍼에서 minibatch를 sampling해서 update한다.

훈련 중엔 ε-greedy Exploration policy 를 사용하는데, deepmind의 논문에는 처음에는 ε=1로 시작했다가 백만 번 진행 중에 ε = 0.1까지 줄어든다. test할 때는, ε = 0.05로 두고 test한다.

참고 할 점들:

• 이 assignment에서는 replay 버퍼에서 minibatch를 sampling해서 w를 learning_freq 횟수에 한번 씩 update한다. 

• Deepmind의 Deep Q network는 state s 를 input으로 받고, action의 갯수와 동일한 크기의 벡터를 output으로 낸다.

Pong environment에서는 action 6개가 있으므로, ^q(s, w)도 실수 범위 내에서 6개의 Vector를 가진다. (ℝ^6)

• 이 deep Q network의 input은 연속적인 4개의 step을 합친 것이고, 이를 preprocessing하면 (80 * 80 * 4)의 shape가 나온다.

1. experience replay를 사용할 때의 이점 한 가지를 대시오. [3점]

sol) 게임의 경우 전 프레임과 다음 프레임의 연관관계가 굉장히 끈끈한데, 이러한 연관관계는 SGD에 필요한 I.I.D 가정을 충족시키지 못한다.

이를 충족시키기 위해, experience replay를 사용하면 현재 프레임과 독립적인 프레임의 튜플을 update에 활용하여 SGD에 필요한 I.I.D 가정을 어느 정도 충족시킬 수 있다.

또, history에 저장되는 양을 늘림으로써 놓칠 수 있는 experience들을 다시 활용할 수도 있을 것이다.

(특히 prioritize experience replay를 사용하면 더 좋겠다.)

2. target network를 사용했을 때의 이점을 한 가지 대시오. [3점]

sol) Q-learning을 사용할 경우, update하는 과정에서 지속적으로 optimal한 값이 변화하게 된다. 그러면 w값이 막 미쳐돌아서 infinite로 날라갈 수도 있고, 굉장히 unstable해지는데, w값을 어느 정도 고정시켜주면서 이를 stable하게 잡아준다.

3. Q-Function을 ^q(s, w)∈ℝ^k 과 같이 나타낼 때의 이점을 한 가지를 대시오. [3점]

sol) 저렇게 벡터 형식으로 나타내면, 각각의 action에 대한 scalar값으로 나타내는 것 보다 연산 효율이 좋다.

4. (코딩문제) q1_schedule.py에 있는 get_action 과 update 함수를 구현하고, python q1_schedule.py로 구현한 것을 실행시켜 보시오. [3점]

참고 : http://web.stanford.edu/class/cs234/assignment2/assignment2.zip 에서 assignment2에 필요한 기초 코드를 받을 수 있다.

구현해야 되는 함수의 코드만 작성하겠다.

    def update(self, t):
        """
        Updates epsilon

        Args:
            t: int
                frame number
        """
        ##############################################################
        """
        TODO: modify self.epsilon such that 
			  it is a linear interpolation from self.eps_begin to 
			  self.eps_end as t goes from 0 to self.nsteps
			  For t > self.nsteps self.epsilon remains constant
        """
        ##############################################################
        ################ YOUR CODE HERE - 3-4 lines ##################

        if t < self.nsteps:
            self.epsilon = self.eps_begin - (self.eps_begin - self.eps_end) * t / self.nsteps
        else:
            self.epsilon = self.eps_end

        ##############################################################
        ######################## END YOUR CODE ############## ########

위 코드는 ε-greedy policy를 더 fancy하게 만들기 위한 코드이다.

처음에는 epsilon값을 크게 잡아뒀다가, 가면 갈수록 점점 더 epsilon값을 작게 만들어 주는 것이다.

참고로 위 네 줄 짜리 코드는 다음의 세 줄짜리 코드로 줄일 수도 있다.

        self.epsilon = self.eps_end
        if t < self.nsteps:
            self.epsilon = self.eps_begin - (self.eps_begin - self.eps_end) * t / self.nsteps

    def get_action(self, best_action):
        """
        Returns a random action with prob epsilon, otherwise returns the best_action

        Args:
            best_action: int 
                best action according some policy
        Returns:
            an action
        """
        ##############################################################
        """
        TODO: with probability self.epsilon, return a random action
                else, return best_action

                you can access the environment via self.env

                you may use env.action_space.sample() to generate 
                a random action        
        """
        ##############################################################
        ################ YOUR CODE HERE - 4-5 lines ##################

        if np.random.random() < self.epsilon:
            return self.env.action_space.sample()
        else:
            return best_action

        ##############################################################
        ######################## END YOUR CODE #######################

위 코드는 그냥 아까 전에 잡아둔 epsilon값을 바탕으로 action을 return하는 함수이다.

- 본 포스팅은 CS234 6강의 내용을 정리합니다....만 CNN 부분은 따로 설명하지 않겠습니다.

그 대신, 제 블로그의 CS231n 강의 (https://cding.tistory.com/5) 를 보시거나 간단한 CNN 오버뷰 정도는 보고 오시면 좋겠습니다.

오늘 배울 것들로는 원래는 CNN과 Deep Q Learning이겠지만, 위에서 언급했듯 DNN 및 CNN은 설명하지 않고 바로 DQN으로 뛰어넘도록 하겠다. 

그래서, DQN이 뭔지, 어떻게 이루어지는지 알아보자.

저번에 짤막하게 설명했듯이, function approximation, off policy control, boostrapping 셋을 모두 사용하는 것은 굉장히 unstable하다. Converge하지 않을 가능성이 농후하기 때문이다.

짤막하게 DQN의 역사에 대해 설명하자면,

1994년즘에 backgammon을 DQN으로 구현해낸 이후로 1995년 ~ 1998즘엔 위에서 말한 unstability를 개선하기 위한 연구를 진행하다가 DNN 자체가 망하는 바람에 연구가 더 진행되지 못했다.

그러다 2000년대 중반즈음부터 computational power의 증가 및 data의 증가 등의 이유로 DNN이 각광받기 시작하며,

DQN 또한 같이 주목받게 되었다.

그리고 2014년 (정말 얼마 안되었다) 경 Deepmind에서 위처럼 breakout (벽돌깨기) AI를 DQN을 사용해서 만들기에 이른다.

최근에는 도타 2 AI인 Openai five가 5대5로 프로게이머를 이기고, 전세계 사람들과 대전했을 때 99.5%의 승률을 자랑하기까지 하는 등 Deep Reinforcement Learning이 각광받고 있다.

아무튼, 우리는 DNN을 사용해서 Reinforcement Learning을 시킬 것이다.

(당연히 VFA를 사용한다.)

DQN은 그냥 Q (state action)을 DNN에 적용시킨 것 뿐이다. 그렇게 Value와 Q function을 구하는 것이 목적이다.

(대충 저번 시간에 했던 내용이므로 대충 생략하겠다는 말)

그래서 이러한 Q-Learning 방식을 Atari 게임에 적용시키면 된다.

게임 화면의 이미지를 state로, agent가 취하는 컨트롤을 action으로, 그리고 게임에서 주는 점수를 reward로 한다.

그렇게 해서 agent를 학습시켜 보자는 것이 기초적인 아이디어이다.

Atari Breakout (벽돌깨기) 을 예시로 들 것인데, Atari breakout같은 경우 action의 종류가 약 4개에서 18개정도밖에 되지 않는다.

하지만, state같은 경우 이미지의 픽셀값들을 받아오므로 굉장히 큰 data가 된다. 이것들을 어떻게 다뤄야 하는지 알아보자.

참고로 말해두자면, 지금부터 배울 대부분의 내용들은 2015년도 Deepmind의 Atari DQN 논문에 있는 내용들이다.

우선, input으로는 이전 4프레임의 이미지를 받는다.

1프레임의 이미지만을 input으로 두지 않고 이렇게 4프레임의 이미지를 받는 이유는 공의 방향이나 속도들을 알기 위해서이다.

CNN과 relu, fully-connected layer 등을 걸쳐 나오는 output은 Q(s,a)로, 18개의 조이스틱 및 버튼의 움직임을 표현한다.

그리고 Deepmind의 논문에서는, 이 아키텍쳐와 hyperparameter 들을 모든 게임에 동일하게 적용하였다.

그것만으로도 충분히 학습된다는 것을 보이기 위해서였고, 실제로 많은 게임들에 잘 적용되는 것을 볼 수 있다.

물론, 몇 개의 게임들은 확실히 tuning해야 할 것이다.

가령 delayed reward가 매우 중요한 게임들은 (감마) 값을 높게 두어야 할 것이다.

이제 진짜 본론으로 들어가보자.

Q-learning을 VFA를 사용해서, SGD를 사용해 MSE loss를 최소화시키고, 최적의 Q*(s, a)를 찾아가는 과정이다.

그러나, 저번에도 말했듯이 Q-learning을 VFA와 함께 사용하면 diverge할 수 있다. (수렴하지 않고 막 나간다)

그 이유는 첫번째로는, sample간의 연관성이 너무 크기 때문이다.

아까 전, 분명 DQN은 게임의 화면을 5프레임 간격으로 받는다고 했었는데, 분명히 게임의 연속된 다섯 프레임은 굉장히 연관되어 있을것이다.

그런데 이렇게 sample 간의 연관성이 너무 커져 버리면, SGD 방식으로 수렴하기 위해 필요한 IID 상태가 아니게 된다.

(IID란 간단히 말해서 모든 데이터들이 다 독립적이어야 한다는 뜻이다.)

또한, target이 non-stationary하다. 즉, target이 계속 변화한다.

VFA를 적용시키려면, 최소한 어디에 Converge시켜야 하는지는 알아야 한다.

그런데 Q-learning의 경우 이 optimal policy가 계속 바뀌므로, 어디다 Converge하기가 쉽지 않다.

이 두 가지 문제점을 해결하기 위해서, deepmind에서는 Experience Replay와 Fixed Q-target이라는 방법을 사용한다.

Experience Replay는, 말 그대로 지금까지의 경험을 축적해서 다시 사용하는 것이다.

원래였다면 그냥 한번 w와 policy를 update하고 말 경험들 (지나친 step들)을 저장하고 있다가, 나중에 다시 이 값들을 사용해서 w값을 update해 주는 것이다. 

이렇게 하면 원래 굉장히 높은 연관성을 띄던 데이터들로부터 벗어나서, 조금 더 독립적인 (연관성이 적은) 데이터들로 다시 w를 update해줄 수 있는 것이다.

또, 원래 update하던 도중에도 Q-learning방식을 사용했기에 target value가 이미 바뀌어 있을 것이고, 그러면 그 바뀐 값에 대해 다시 독립적인 데이터를 사용해 w를 update해줄 수 있는 것이다.

Fixed Q-Targets는 말 그대로, target weight를 고정시켜주는 것이다.

Q-learning 방식에서는 계속 target이 바뀌어서 문제였지만, 이것을 그냥 고정시켜줌으로써 대처하는 것이다.

target update를 할 때 사용할 weight w⁻와 실제 update를 해 줄 weight w를 나누어서 사용하는 것이다.

아래쪽의 식을 보면 이해가 빠를 것 같다.

원래 max를 시켜주는 저 target에는 w⁻를 집어넣고, 그 외 나머지 부분에는 원래 weight w를 집어넣어 준다.

그리고, n번째 마다 (hyper parameter이다.) w⁻값을 다시 원래 w값으로 맞춰 준다.

이렇게 해 주면, 원래 Q-learning에서 계속 w가 바뀌다가 결국 w가 막 infinity로 터지는, 그런 상황을 방지할 수 있다.

즉, stability가 꽤 많이 향상된다는 것이다.

-정리-

DQN은 experience replay와 fixed Q-target를 사용한다.

replay memory D에 experience (s, a, r, s')을 채워주고, 거기서 mini-batch를 sampling해서 update한다.

또 fixed parameter w⁻를 사용하여 Q-learning target을 연산하고, MSE loss를 최소화 시켜준다.

SGD를 사용하고, (위에서 나오진 않았지만) ε-greedy exploration도 사용한다.

그러면, 이렇게 학습하면 잘 될까?

https://www.youtube.com/watch?v=V1eYniJ0Rnk

ㅇㅇ.. 잘 된다!

그럼 DQN에선 어떤 부분이 가장 중요할까?

위 표를 보면 알겠지만, experience replay를 적용시키는 경우 효율이 가장 좋은 것을 알 수 있다.

이제부턴, Deepmind의 논문 이후에 발표된, Deep RL의 주요 improvemets들을 설명하겠다.

그 중 첫번째는, 바로 Double DQN이다.

저번에 설명했던, maximization bias 문제를 해결하기 위해 나온 Double Q-learning의 Deep RL 적용판이다.

Double Q-learning이 뭐였는가?

Q를 하나만 쓰는 대신, 두 개를 사용하여 50% 확률로 Q1, 나머지 50% 확률로 Q2를 사용하여 Q-learning을 하는 방식이었다.

이 아이디어를 DQN에도 적용시킨 것이 바로 Double DQN이다.

현재 사용하는 Q-network w를 action을 고르는 데 사용하고,

w⁻는 action을 evaluate 하는 데 사용하는 것이다. (위 식 참고)

그래서, Double DQN을 사용하면, 위와 같이 좋은 결과를 낼 수 있다.

두 번째 방식은, 바로 Prioritized Replay이다.

말 그대로, Experience Replay를 그냥 막 골라서 하지 말고, 우선순위를 정해서 하자는 것이다.

이쯤, Mars Rover 예시를 다시 들어보자.

(지금까지 엄청 자주 설명했고, 위에도 잘 나오니 자세한 설명은 생락하겠다.)

그래서 위 예제에서 (s3, a1, 0, s2, a1, , s2, a1, 0, s1, a1, 1, terminal) 에피소드를 지난 뒤에, TD estimate는 어떻게 되는가?

한 번 update를 해 주면, 결국 reward가 s1, a1, 1, terminal 에서 나왔으므로 결국 [1 0 0 0 0 0 0]이 된다. (bootstrapping)

이제 여기서 replay를 두 번 진행할 수 있다고 할 때, 어떤 step을 replay하는 것이 가장 좋을까?

(오른쪽 위가 replay buffer가 저장되어 있는 모습이다.)

만약 (s3, a1, 0, s2) 버퍼를 사용해서 replay 한다면, 아무런 의미도 없을 것이다.

결국 지금 상태는 [1 0 0 0 0 0 0]이고, s3, s2는 reward가 0이므로, 아무런 영향도 미치지 않는다.

(s2, a1, 0, s2)를 선택하는 경우에도 마찬가지로, s2는 reward가 0이므로 아무런 영향도 미치지 않는다.

(s2, a1, 0, s1)을 선택하는 경우만 다르게 적용된다. 현재 s1이 1이므로, 이 reward 1은 그대로 s2에 전달되게 된다. (α=1)

그러면, 결국 TD estimate는 [1 1 0 0 0 0 0]이 된다.

그 다음엔?

만약 (s3, a1, 0, s2) 버퍼를 사용하면, s2의 reward가 1이므로, s3에도 그 reward가 그대로 전달되므로,

TD estimate는 [1 1 1 0 0 0 0]이 된다.

이렇게, 한 episode에서 최소의 replay buffer만을 사용하여 최적의 TD estimate를 얻어냈다.

만약 위처럼 우리가 replay buffer를 선택하지 않고 그냥 아무런 replay buffer나 사용하였다면, 이렇게 결과가 잘 나오진 못했 을 것이다.

위에서 아무런 영향을 주지 못한 replay는 결국 연산 횟수만 증가시키는 꼴이 되기 때문이다.

즉, 이렇게  replay buffer를 선택하는 과정은 update 효율을 굉장히 증가시켜 준다는 사실을 알 수 있다.

위에서 봤듯이, TD-learning에서는 replay의 순서가 학습의 속도를 늘리는 데 도움을 줄 수 있다.

아무런 쓸데 없는 정보가 담긴 버퍼를 사용하는 것 보다, 쓸데 있는 버퍼를 사용하는 것이 더 좋다는 것인데...

그런데, 어떻게 replay buffer의 우선순위를 정해야 할까?

위처럼 하나하나 넣어봐서 가장 좋은 버퍼를 고르는 것은 매우 비효율적일 것이니 말이다.

(대충 Episodic Replay Update의 순서를 정하는 것이 convergence를 빠르게 한다는 내용)

그래서 우리가 사용할 방법은 DQN error을 사용하는 방법이다.

어떤 tuple (replay buffer)를 골랐을 경우의 TD error와 현재 error의 차이가 가장 큰 것의 우선순위를 크게 잡아두는 것이다.

왜 이렇게 하냐고? 직관적으로 바라보자면...

만약 TD error가 현재의 error와 같다면 어떨까?

지금 선택한 replay buffer가 error에 아무런 영향을 끼치지 않는다는 이야기가 되므로, 정말 아무런 쓸데 없는 연산이 된다고 할 수 있다.

아까 위에 예시에서 아무런 영향을 끼치지 못하는 버퍼가 바로 이런 것들이다.

반면, TD error가 현재의 error와 크게 차이가 난다면?

그 버퍼가 바로 우리가 미처 제대로 습득하지 못한 데이터일 가능성이 커지게 되는 것이다.

그래서 이런 방식으로 replay buffer의 우선순위를 결정할 수 있다.

그럼 한 가지 질문만 던져보자. 만약 α=0이라면 어떻게 replay buffer가 선택이 될까?

α=0이라면, 저번 step에서 일어난 일이 현재 step까지 어떤 영향을 끼치지 못하게 되는 꼴이므로,

모든 TD-error과 현재 error의 차이가 동일하게 정해지게 된다.

그렇기에, replay buffer는 그냥 랜덤하게 결정되게 된다.

위는 Prioritized replay 방식과 double dqn 방식을 사용했을 때의 효과를 나타낸 그래프이다.

그냥.. 그렇다구...

다음으로, Dueling DQN이라는 방식이 있다.

이 방식의 요점은, optimal Q를 선택할 때 현재 state의 value와 action을 따로따로 생각한다는 점이다.

여기서 Advantage Function이 나오는데, 이는 Q(s, a)에서 V(s)를 뺀 값으로, 현재 action을 선택했을 경우 다른 action을 선택했을 때 보다 얼마나 더 좋은 결과를 내보내는지를 의미한다.

즉, 현재 Vπ(s)값에 비례한, action에 따른 상대적인 Value값을 의미한다.

개인적으로 이 부분 이해가 힘들었으므로 더 적어두자면, (사실 나중에 까먹었을때 볼라구 ㅎㅎ)

Vπ(s)는 policy를 따를 때, 그 state에서의 Value의 평균이다.

그리고 Qπ(s, a)는 각각의 action a를 따를 때 나오는 Value이므로,

결국 모든 action에 대한 Qπ(s, a) - Vπ(s) = 0이다.

여기서, 만약 Qπ(s, a)의 값이 Vπ(s)보다 크다면, 현재의 state에서 일반적으로 나올 수 있는 Value보다 더 좋은 Value를 얻은 action을 선택했다는 의미가 된다.

게임을 예시로 들어보자면,

현재 점수가 Vπ(s)인 것이고, Qπ(s, a)는 다음 action a를 취했을 때의 점수인 것이다.

만약 Advantage Function을 사용하지 않고 그냥 Qπ(s, a)만 본다면,

게임 후반의 점수가 게임 초반의 점수보다 당연히 더 높을 것이므로 게임 후반의 Q(s, a)값만 바라보고, 그 action을 취하는 데에 치중하게 될 것이다.

하지만 만약 Advantage Function을 사용하면, 게임 초반이나 후반이나 상관없이 내가 이 action을 취했을 때 얼마나 잘 플레이 한 것인지 알 수 있게 된다.

다음은 Dueling DQN의 아키텍쳐이다.

원래 DQN에서 마지막에 Q(s, a1), Q(s, a2) ...의 값이 나왔다면,

Dueling DQN에서는 마지막에 V(s), A(s,a1), A(s,a2)의 값들이 따로 나오고,

이 값들을 합쳐서 Q(s, a1), Q(s, a2)의 값을 얻어내는 것이다.

위 두 슬라이드는 영상에서 교수님이 설명을 안하셨다.

그러니 이해하고 싶으면 ppt를 보고 이해해야 된다.

난 못했으니 그냥 넘어간다.

Dueling DQN은 굉장히 효율이 좋은 학습 방식이고, 이는 위 그래프로 설명이 가능하다.

지금부터는 이 DQN을 실제 적용할 때의 팁들이다.

- DQN은 다른 방식들보다는 더 믿을만한 방법이다. Pong은 그중에서도 좀 믿음직 스러운 게임인데, 만약 DQN을 Pong에 적용시켰는데 뭔가 잘 안된다면, 너가 뭔가 잘못 한 것이다.

- DQN에서 replay buffer는 크면 좋으므로, 메모리 효율이 매우 중요하다. 데이터를 막 중복해서 쌓지 말고, uint8 이미지를 사용하라.

- DQN은 굉장히 천천히 Converge 하므로, 참을성 있게 기다려라.

아타리의 경우 천만~4천만 프레임 동안 기다려야지 random policy보다 훨씬 더 좋은 결과를 얻을 수 있는데,이는 GPU에서 훈련시킬 때 두시간 정도에서 하루 종일이 걸릴 정도의 양이다.

- 그리고 나중에 Atari를 실제로 학습시키려고 할 때, 작은 test environment에서 디버깅 꼭 해봐라.

이거 안하고 그냥 Atari에 때려 박았다가 잘 안되면 시간 날려먹는거니깐.

(이 ppt는 그냥 영상에서도 거의 거르다시피 함 - 알고 있거나 이해한 부분만 써놓음)

- Bellman error에서 Huber loss를 시도해 보아라. (위 식 참고)

- Double DQN을 써 보자 - 코드는 별로 안 바꿔도 되는데 성능 차이는 크게 난다.

- Learning rate scheduling은 꽤 좋다. 처음 exploration period에는 learning rate를 크게 잡아 놓아라.

이렇게 DQN에 대한 설명은 끝!

다른 강의들과는 조금 다르게 수학적으로 파고드는 것 보다 아이디어를 설명하는 강의였던 것 같다.

* 원래 해석 다 쓰고 쓸려 했는데 해석만 하다 보니깐 답답해 죽겠어서 그냥 풀면서 해석본 올리겠읍니다 ㅎㅎ..

어차피 딱 보니 제가 풀 클라스가 아닌 것들이 있는 것 같아서...

최종 해석본은 Assignment 풀이 끝나면 한번에 올리겠습니다.

1. Test Environment

다음과 같은 environment가 주어진다.

State 4개 : 0, 1, 2, 3

action 4개 : 0, 1, 2, 3, 4

action 0,1,2,3일때는 각각 state 0,1,2,3으로 가고, action 4일 때는 원래 state에 남아있는다.

reward는 위의 표를 참고하라.

한 episode는 time step 5번 (action을 5번 취한다)동안 지속된다.

또한, 언제나 state s0에서 시작한다.

(s, a, r, s')의 형태로 예시를 들면,

(0, 1, -0.2, 1, 2, 0, 2, 4, 0, 2, 3, 1, 3, 0 0.1, 0)

가 한 가지 예시이다. (자세한 것은 위의 그림을 참고하라.)

1. 위 test environment에서, 한 episode에서 얻을 수 있는 최대의 reward는? [5점]

sol) 다른 reward들은 죄다 -1 ~ 0.2 언저리에서 놀고 있지만, s2에서 a1을 취하는 경우는 reward가 2가 나온다.

어떤 경우에도 저 s2로 가서 a1을 취하는 것이 최선이다! (reward 0.2를 time step 5회에 걸쳐 계속 얻더라도 reward 2를 받는게 더욱 효율적이다)

그러므로, s0에서 시작하므로 s2로 우선 가는 것이 최선의 선택이다.

(s0, a2, 0, s2)

그리고 s2에서 a1을 취하면 reward 2를 얻을 수 있으므로,

(s0, a2, 0, s2, a1, 2, s1)

또 뒤에 time step이 3회나 남았으므로 다시 s2에서 a1을 취할 수 있으므로 다시 s2로 가서 a1을 취한다.

(s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1)

이러면 time step은 1회가 남고, 이러면 그냥 이 상황에서 reward가 가장 높은 action을 고르는 것이 최선이므로,

s1에서 최선의 reward 0.1을 얻을 수 있는 action 0을 취하는 것이 최선의 선택이다.

(s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1, a0, 0.1, s0) 

그리고 이 때 얻는 reward는 0 + 2 + 0 + 2 + 0.1 = 4.1이다.

+추가로, 가장 처음에 s0에서 a0 또는 a4를 취해서 0.1을 먼저 얻은 뒤에 가는 경우도 고려하긴 해야 한다.

하지만, 그렇게 해도 (s0, a0, 0.1, s0, a2, 0, s2, a1, 2, s1, a2, 0, s2, a1, 2, s1)으로, reward가 4.1이 되니 결국 최대의 reward는 4.1이 된다.

*Assignment 1-3은 본인의 수학적 실력 부족으로 인해 풀이까지 하긴 힘들 것 같습니다..ㅠㅠ

코딩 부분은 채워넣어야 하는 부분만 코드를 따로 올릴테니, 다른 추가 코드들은 직접 사이트에서 다운받아 주세요.

http://web.stanford.edu/class/cs234/assignment1/index.html

(a) (코딩 문제) vi_and_pi.py를 읽고, policy_evaluation, policy_improvement, policy_iteration을 구현하라.

maxₛ |old_V(s) - new_V(s)|로 정의되는 stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

def policy_evaluation(P, nS, nA, policy, gamma=0.9, tol=1e-3):
    """Evaluate the value function from a given policy.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    policy: np.array[nS]
        The policy to evaluate. Maps states to actions.
    tol: float
        Terminate policy evaluation when
            max |value_function(s) - prev_value_function(s)| < tol
    Returns
    -------
    value_function: np.ndarray[nS]
        The value function of the given policy, where value_function[s] is
        the value of state s
    """

    ############################
    # YOUR IMPLEMENTATION HERE #
    V = np.zeros(nS)
    while True:
        new_V = np.zeros(nS)
        for state in range(nS):
            for (prob, next_state, reward, end) in P[state][policy[state]]:
                new_V[state] += prob * (reward + V[next_state] * gamma)
        if np.all(np.abs(new_V - V) < tol):
            break
        V = new_V.copy()
    ############################

    return new_V
    
    def policy_improvement(P, nS, nA, value_from_policy, policy, gamma=0.9):
    """Given the value function from policy improve the policy.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    value_from_policy: np.ndarray
        The value calculated from the policy
    policy: np.array
        The previous policy.

    Returns
    -------
    new_policy: np.ndarray[nS]
        An array of integers. Each integer is the optimal action to take
        in that state according to the environment dynamics and the
        given value function.
    """

    new_policy = np.zeros(nS, dtype='int')
    ############################
    # YOUR IMPLEMENTATION HERE #
    for state in range(nS):
        Q = np.zeros(nA)
        temp = -99
        for action in range(nA):
            for (prob, next_state, reward, end) in P[state][action]:
                Q[action] += prob * (reward + gamma * value_from_policy[next_state])

            if temp < Q[action]:
                temp = Q[action]
                new_policy[state] = action
    ############################

    return new_policy
    
    def policy_iteration(P, nS, nA, gamma=0.9, tol=10e-3):
    """Runs policy iteration.

    You should call the policy_evaluation() and policy_improvement() methods to
    implement this method.

    Parameters
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    tol: float
        tol parameter used in policy_evaluation()

    Returns:
    ----------
    value_function: np.ndarray[nS]
    policy: np.ndarray[nS]
    """

    value_function = np.zeros(nS)
    policy = np.zeros(nS, dtype=int)

    ############################
    # YOUR IMPLEMENTATION HERE #

    i = 0
    new_policy = np.zeros(nS, dtype=int)

    while i == 0 or np.sum(abs(new_policy - policy)) > 0:
        policy = np.copy(new_policy)
        value_function = policy_evaluation(P, nS, nA, policy, gamma, tol)
        new_policy = policy_improvement(P, nS, nA, value_function, policy, gamma)
        i += 1

    ############################
    return value_function, new_policy

그냥 수식을 코드로 옮겼습니다.. 혹시 이 부분 구현이 잘못된 것 같다거나, 궁금한 점이 있으면 따로 댓글로 질문 부탁드립니다.

(b) (코딩 문제) vi_and_pi.py에서 value_iteration을 구현하여라. stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

def value_iteration(P, nS, nA, gamma=0.9, tol=1e-3):
    """
    Learn value function and policy by using value iteration method for a given
    gamma and environment.

    Parameters:
    ----------
    P, nS, nA, gamma:
        defined at beginning of file
    tol: float
        Terminate value iteration when
            max |value_function(s) - prev_value_function(s)| < tol
    Returns:
    ----------
    value_function: np.ndarray[nS]
    policy: np.ndarray[nS]
    """

    policy = np.zeros(nS, dtype=int)
    ############################
    # YOUR IMPLEMENTATION HERE #

    V = np.zeros(nS)
    while True:
        new_V = np.zeros(nS)
        for state in range(nS):
            for action in range(nA):
                temp=0
                for (prob, next_state, reward, end) in P[state][action]:
                    temp += prob * (reward +gamma * V[next_state])

                if temp > new_V[state]:
                    new_V[state] = temp

        if np.all(np.abs(new_V - V) < tol):
            break
        V = new_V.copy()

        policy = policy_improvement(P, nS, nA, V, policy, 0.9)
    ############################
    return V, policy

이것도 마찬가지로 그냥 ppt에 있던 수식을 그대로 코드로 구현했습니다.

처음에 state나 action 둘 중 하나만 for문을 돌렸다가 실패했던 기억이 있습니다.

(c) 각각의 방법 (vi와 pi)를 Deterministic-4x4-FrozenLake-v0과 Stochastic-4x4-FrozenLake-v0의 environment에서 실행시켜 보아라. 두 번째 environment에서, world의 dynamics는 무작위적(stochastic)이다. (world가 어떻게 움직이는지 랜덤이라는 뜻이다.) 이 무작위성은 반복의 횟수와 policy의 결과에 어떤 영향을 미치는가? [5점]

sol)

다음은 본인의 코드를 돌려 나온 결과값이다. (iter의 횟수를 count하는 코드는 위의 코드에는 없다..)

Deterministic-4x4-FrozenLake-v0

PI iter : 7

optimal Value Function
[0.59  0.656 0.729 0.656 0.656 0.    0.81  0.    0.729 0.81  0.9   0.
 0.    0.9   1.    0.   ]
Optimal Policy
[1 2 1 0 1 0 1 0 2 1 1 0 0 2 2 0]

VI iter : 7

optimal Value Function
[0.59  0.656 0.729 0.656 0.656 0.    0.81  0.    0.729 0.81  0.9   0.
 0.    0.9   1.    0.   ]
Optimal Policy
[1 2 1 0 1 0 1 0 2 1 1 0 0 2 2 0]

Stochastic-4x4-FrozenLake-v0

PI iter : 6
optimal Value Function
[0.062 0.056 0.07  0.051 0.086 0.    0.11  0.    0.141 0.244 0.297 0.
 0.    0.377 0.638 0.   ]
Optimal Policy
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0]

VI iter : 27
optimal Value Function
[0.062 0.055 0.07  0.051 0.085 0.    0.11  0.    0.14  0.244 0.297 0.
 0.    0.377 0.638 0.   ]
Optimal Policy
[0 3 0 3 0 0 0 0 3 1 0 0 0 2 1 0]

실제로 코드를 돌려 보면, Deterministic의 경우에는 Policy Iteration, Value Iteration 모두 한번에 Goal로 잘 도착한다.

하지만 Stochastic environment에서는 굉장히 머뭇머뭇하며 진행되는 경향이 있는 듯 하다.

Iteration 횟수는 Value Iteration같은 경우 증가했으나, Policy Iteration의 경우 1 감소했다.

VI에서 Iteration 횟수가 증가하는 것은 이해가 되지만, PI에서 왜 Iteration 횟수가 감소했는지는 잘 이해가 되지 않는다. (ㅠㅠ)

또한, environment의 stochastic하게 되면 Deterministic한 environment와 Optimal Policy도 달라지는 것을 확인했다.

VI와 PI가 동일한 Policy로 Converge한 것을 보면, 학습은 잘 된 것 같다.

(혹시 코드가 틀렸다거나... Policy Iteration에서 왜 Iter 횟수가 1 감소했는지 알려주실분 있으면 댓글 부탁드립니다... ㅠㅠ)

아무튼, 이것으로 CS234 assignment 1 풀이는 마치도록 하겠다.

이젠 assignment 2다!!

해석본은 아래 글에 찾아보시면 될 것 같습니다.

여기서는 풀이만 진행합니다.

(a) time step t=0인 state s0에서 action a1을 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? [5점]

sol) 처음 얻는 reward r0 = 0이고,

나머지 reward r1, r2, r3, ... , rt = 1이므로, 위 수식을 풀어 쓰면

0 + 𝛾 + 𝛾^2 + 𝛾^3 + .... = 𝛾 / (1-𝛾)

(b) time step t=0인 state s0에서 action a2를 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? optimal action은 무엇인가? [5점]

sol) 처음 얻는 reward r0 = 𝛾^2 / (1-𝛾)이고,

나머지 reward r1, r2, r3, ..., rt = 0이므로, 위 수식을 풀어 쓰면

𝛾^2 / (1-𝛾) + 0 + 0 + ... = 𝛾^2 / (1-𝛾)

그리고 0 < 𝛾 < 1이므로, 𝛾 / (1-𝛾) > 𝛾^2 / (1-𝛾) 이다.

즉, optimal action은 a1이다.

(c) 모든 state의 value를 0으로 초기화 했다고 가정하자. value iteration은 위의 수식 (n* ≥ log(1-ᵞ)/logᵞ ≥ 1/2 * log(1/1-ᵞ) * 1/(1-ᵞ)이 성립할 때 까지 sub-optimal action을 선택하는데, 이를 증명하여라.

따라서, value iteration은 1/(1-ᵞ)보다 빠르게 증가한다. (첫 번째 부등식이 옳다는 것만 보이면 된다.) [10점]

sol)

value iteration은 그때그때 최선의 value를 갖는 action을 고른다.

그렇기 때문에, Q(s0, a1) < Q(s0, a2)인 동안은 Value값이 높은 Q(s0, a2)를 계속 고르게 된다.

우선 action a2를 취할 때, s2에서 모든 Vn(s2) = 0이므로 Q값인 Qn+1(s0, a2)는 𝛾^2 / (1-𝛾)가 된다.

그리고, action a1을 취할 때의 value iteration은 다음과 같이 update된다 : 

Qn+1(s0, a1) = 0 + 𝛾Vn(s1)

Vn+1(s1) = 1 + 𝛾Vn(s1)

즉,

Qn+1(s0, a1) = 0 + 𝛾(1 + 𝛾 + 𝛾^2 + ... + 𝛾^n)

                 = 𝛾 + 𝛾^2 + ... + 𝛾^n

                 = 𝛾 * (1-𝛾^n) / (1-𝛾)

그리고 딱 저 때의 n을 n*라고 두면, action a1을 취했을 때의 Q값이 a2를 취했을 때의 Q값보다 더 크거나 같아져야 하므로,

𝛾 * (1-𝛾^n*) / (1-𝛾) >= 𝛾^2 / (1-𝛾)

이것을 n*에 대해 정리하면 좌변과 우변의 1 / (1-𝛾) 는 사라지고,

𝛾 * (1-𝛾^n*) >= 𝛾^2 에서 양변의 𝛾를 나눠주면

1-𝛾^n* >= 𝛾

𝛾^n* <= 1-𝛾

n* >= log 𝛾 (1-𝛾)  (log 밑이 𝛾, 진수가 1-𝛾) (0 < 𝛾 < 1이므로)

   >= log (1-𝛾) / log(𝛾)  (log 밑은 e)

이로써 첫 번째 부등식을 만족함을 보였다.

두, 세번째 부등식도 그냥 풀어가다 보면 만족함을 보일 수 있겠으나, 문제에서 첫 번째 부등식이 성립함을 보이기만 해도 된다고 했으니 걸러버리겠다.

- 본 포스팅은 CS234 5강의 내용을 정리합니다.

* 기본적인 Neural Network 및 머신러닝 지식이 있으면 이해가 훨씬 빠릅니다! (그냥 알고 있어야 이해가 될것 같습니다 ㅎㅎ)

이번 강의에선 Value Function Approximation, 줄여서 VFA에 대해서 배운다.

주로 다룰 내용은 위 목차의 2번이 되겠다.

(3번은 시간 문제상 대부분 생략된다. 어뜨케 1강에서 5강까지 죄다 후반내용은 생략하시네 교수님;;)

지난 시간에, (CS234 4강의 내용) 경험을 토대로 좋은 policy를 얻는 방법을 배웠었다.

SARSA, Q-Learning, Monte Carlo, TD 등등...

그런데, 지금까지 이런 내용들을 배울 땐 value function이나 state-action value function을 벡터나 매트릭스 형태로 나타낼 수 있다는 가정 하에 배웠었다.

(이를 Tabular representation이라고 한다.)

그러나, 실제로는 value function이 그렇게 돼 있는 경우는 흔치 않다.

가령 자율운전 자동차를 만든다고 할 때, state가 얼마나 많겠는가?

왼쪽으로 1도 갔을 때, 2도 갔을 때.... 180도 갔을 때 등등만 하더라도 그렇겠지만,

거기다가 속도나 주변 차들의 유무 등등 수없이 많은 state들이 존재하게 될 것이다.

그렇기 때문에, 벡터나 매트릭스로 value function을 나타내는 tabular representation은 강화 학습의 실제 적용에 부족한 점이 있다.

이를 해결하기 위해서, 1강에 배웠던 Generalization을 사용하게 될 것이다.

이걸 왜쓰냐고? 일단 계속 보자.

Value Function Approximation이란, Value function을 state, action을 parameter로 갖는 function으로 만드는 것이다.

위의 사진을 보면 이해가 쉬울 듯 하다.

(V와 Q 위에 있는 건 hat이라고 하고, 예측값을 의미한다.)

Neural Network를 배우고 온 사람들이라면 이해가 쉬울 것이라 생각한다.

state, action s,a와 weight vector W를 이용해서 V,Q값을 계산하는 것이므로...

Neural Network와 상당히 비슷한 모습을 보인다.

이 짓 (VFA) 를 하는 이유는...

모든 state에서 Dynamics, Value, Q, Policy들을 명시적으로 알 필요 없이,

state와 state, function 을 모두 아우르는 간단한 일반항을 만들기 위함이다.

가령, V(s,w) 함수를 제대로 만들어 놨다면, 어떤 state에서도 그냥 저 V(s,w)에 s값만 대입하면 value가 그대로 튀어나온다.

즉, w 벡터 하나만 있으면 어떤 상황에서도 value가 그냥 나온다!

이렇게 Generalization을 하면 좋은 점은,

(P,R) / V / Q / π를 저장하는데 메모리가 덜 들고,

(P,R) / V / Q / π를 계산하는데 연산이 덜 필요하며,

좋은 (P,R) / V / Q / π를 찾을 때 experience가 줄어든다.

* 여기서 experience란 좋은 (P,R) / V / Q / π를 찾는 데 필요한 데이터의 수를 의미한다.

주의할 점은, 필요한 data의 수가 줄어든다고 하더라도 적은 데이터만을 갖고 VFA를 하게 되면, 좋지 못한 approximation이 될 수 있다는 것이다.

Neural network와 굉장히 유사한 느낌이라고 보면 될듯 하다.

데이터가 적게 들어와도 fitting을 잘 할 수 있겠지만 그렇다고 그게 실제 data에 잘 적용 가능한 approximation이 아닌것 처럼 말이다.

또한, 위와 비슷한 이유로 VFA를 사용하면 메모리 / 연산 횟수 / 데이터 갯수는 줄어들겠으나, representational capacity도 같이 줄어들게 된다.

*representational capacity는 머신러닝 모델의 flexibility, 즉 실제 데이터의 적응력 정도를 의미함.

그러면 VFA에 사용할 approximator에는 어떤 것들이 있을까?

Linear approximator를 사용할 수도 있고,

Neural Network를 사용할 수도 있고, Decision tree를 사용할 수도 있다.

이는 머신러닝 모델을 선택하는 것과 비슷한 맥락으로 볼 수도 있을 것 같다.

이 중에서 오늘은 Linear feature representation을 다룰 것이다.

(다음 시간에 Neural network도 다룬다.)

여기서 Gradient Descent에 대한 설명이 나오는데, 여기다가 다시 Gradient Descent를 설명하긴 좀 그렇고 하니 이미 아는 사람은 그냥 넘어가고, 모르면 다음 링크를 타고 들어가서 확인해보자.

https://cding.tistory.com/21?category=704767 - Gradient Descent

https://cding.tistory.com/56?category=704767 - 미분과 Gradient Descent에 대한 이해

왜 다 내 블로그 링크냐고?

아니 뭐 그럼 다른데 가서 보등가 ㅎㅎ...

일단 본격적인 VFA에 들어가기 앞서, 일단 쉬운 버전 먼저 시작해보자.

어떤 state s에 대해서든 완벽한 진짜 Value 값을 던져주는 오라클이라는 존재가 있다고 가정하자.

그리고 그 데이터들을 바탕으로, state s에 대해 value를 찾는 function을 구하려고 한다.

즉 state s가 주어졌을 때 value 값을 찾아내는 w의 값을 찾아내고 싶다는 것이다.

이렇게 하면, Supervised learning하는 과정과 거의 동일해진다.

오라클이 던져준 실제 V값과 우리가 구하고 싶은 Value function을 갖고 Gradient Descent 알고리즘을 적용하면 최적의Value function이 나올테니 말이다.

여기서 잠깐 Stochastic Gradient Descent (SGD)에 대한 설명이 나온다.

그냥 Gradient Descent 알고리즘은 모든 데이터의 cost값들과 미분값들을 토대로 w값을 update해 주었다면,

SGD는 모든 데이터가 아니라 랜덤하게 몇개의 데이터의 cost값들과 미분값들만을 가지고 w값을 update한다.

이렇게 하면 한번 update할 때 시간도 덜 걸리고, 일단 Gradient Descent와 거의 유사한 결과를 낼 수 있다.

근데 갑자기 이걸 왜 알려주냐고?

솔직히 나도 모르겠다 ㅎㅎ;

그런데 실제로 우리가 오라클이라는 존재를 알고 있진 않다.

즉, 실제 Value값을 알려주는 존재같은건 없다는 것이다.

이런 상황에서, 우리는 지금처럼과 같이 model에 의존하지 않고 model-free한 VFA를 만들 방법을 강구해야 한다.

그런데 Model-free.. model.... free...?

이거 우리 한번 하지 않았나?

맞다. CS234 3강의 내용이 바로 Model-free policy evaluation이었다!

그 때 우리는 Monte Carlo methods와 Temporal Difference methods, 줄여서 TD methods를 배웠었다.

이 방법을 그대로 VFA에 가져와서, update 과정에서 function approximator을 fitting하는 과정만 추가해서 사용하면 어떨까?

일단 들어가기 앞서 Feature vector이 뭔지 먼저 정의하고 넘어가겠다.

..라고 해도 그냥 별거 없다. 각각의 state에 대한 정보를 담고 있는 vector라는 뜻이다.

자동으로 청소를 해주는 로봇청소기를 예로 들어보자.

만약 이 로봇청소기에 왼쪽부터 오른쪽까지 전방 180도에 대한 거리를 알려주는 센서가 달려있다고 해보자.

그렇다면, 이 로봇청소기의 feature vector은 1도에서 180도까지의 거리가 될 것이다.

x1(s)에는 1도까지의 거리, x2(s)에는 2도까지의 거리 .... 처럼 말이다.

그리고 이것을 x(s)라고 정의해 두도록 하겠다.

그런데 일단, 오라클을 다시 데려와서 Value 값을 알려달라고 해보자.

그러면 위처럼 Value function의 approximation을 구할 수 있게 된다.

위의 내용이 대충 어떤 내용이냐면,

(대충 x(s)값을 사용해서 Supervised learning과 비슷하게 흘러간다고 설명하는 말)

자, 이제 이해했길 바란다.

절대 설명하기 귀찮아서 저렇게 둔 것이 아니다.

그런데 아까도 말했다시피, 우리한테는 오라클 같은건 없다.

그러니, 저번에 배웠던 Monte Carlo 방식을 사용해보자.

Monte Carlo 방식에서 return Gt는 unbiased, noisy한 Value 값이었다.

그리고, Monte Carlo는 지금까지의 경험을 그대로 Gt를 내놓는다.

즉, 이 Gt값은 어떤 state에 대한 true discounted Value 값이 된다.

(그러니까 이 Gt는 경험했던 state에 대해서만큼은 오라클이 던져주는 Value값과 동일한 실제 Value값이다.)

이를 사용하면, 아까 전에 했던 supervised learning과 동일한 방식으로 VFA를 적용할 수 있다.

(수식은 위 수식 참고)

위는 Monte Carlo 방식을 사용한 VFA가 어떻게 작동하는지 잘 알려준다.

사실 이건 딱히 말할 게 없다. 위에 너무 잘 적혀있으니 그냥 위 ppt를 보고 알아가도록 하고, 자세한건 나중에 나올 예시로 짚어보도록 할 것이다.

그래도 대충 설명을 하자면,

(대충 원래 MC에서 weight update가 추가된 것 뿐이라는 내용)

참고로 알아둘 사항만 적어두자면,

Line 5 : First-visit이라고 적혀있긴 하지만, Every-visit MC에도 동일하게 적용가능하다.

Line 7 : X(s)는 아까 했던 feature vector이다.

그럼 직접 예제로 알아보도록 하자.

위 그림 (s1, s2, s3 ... s7)을 통해서 봤을 때,

저 원 안의 수식은 각 state의 feature vector의 계산식을 의미한다.

w 값의 초기화를 [1 1 1 1 1 1 1 1]이라고 하면,

State s1의 feature vector는 [2 0 0 0 0 0 0 1],

State s2의 feature vector는 [0 2 0 0 0 0 0 1],

....

State s7의 feature vector는 [0 0 0 0 0 0 1 2] 가 된다.

action은 a1, a2 두가지가 있는데,

a1은 그림에서 실선으로 표시되며, 무조건 Deterministic하게 s7으로 가게 되고,

a2는 그림에서 점선으로 표시되며, 각각 1/6의 확률로 s1, s2, s3, ... , s6로 가게 된다.

또한, 어떤 state, 어떤 action에도 reward는 0이다.

그리고 우리는 이 상황을 Monte Carlo 방식을 사용해서 w의 값을 update하고 싶은데,

모두 알다시피 Monte Carlo 방식은 무조건 episodic한, 즉 termination이 존재하는 경우에만 사용이 가능하기 때문에

s7에서 a1을 취하면 0.999의 확률로 s7으로 가고, 0.001의 확률로 terminate가 된다고 가정하고 시작할 것이다.

이 때, 우리에게 다음과 같은 episode가 주어졌다고 가정해보자 : 

s1, a1, 0, s7, a1, 0, s7, a1, 0, terminate

(State, Action, Reward 쌍이다.)

α = 0.5라고 할 때, w의 값은 어떻게 update되는가?

우선 state s1에서 return 값 G는 무엇인가?

모든 reward가 0이므로, return G도 0이 될 것이다.

그렇다면 s1의 value function의 초기값은 무엇이 될까?

w를 모두 1로 초기화한다고 했고,

s1의 feature vector( x(s1) )가 [2 0 0 0 0 0 0 1] 이었으므로

1*2 + 1*0 + 1*0 + ... + 1*1 = 3이 된다.

이쯤에서 아까 저 위에서 w값을 update하는 방식을 가져오면,

w = w + α(G(s) - V(s, a)) * x(s)

였으므로, 위에서 구한 값들을 여기에 대입하면

w = [1 1 1 1 1 1 1 1] + 0.5(0 - 3) * [2 0 0 0 0 0 0 1]

   = [1 1 1 1 1 1 1 1] + -1.5 * [2 0 0 0 0 0 0 1]

   = [1 1 1 1 1 1 1 1] + [-3 0 0 0 0 0 0 -1.5]

   = [-2 1 1 1 1 1 1 -0.5]

...이렇게 w값이 update가 된다.

다른 episode들로도 한번 연습해 봐도 좋을 듯 하다.

위 두 슬라이드는 Linear VFA가 Converge하는가를 다루는 내용인데, 본인이 이해를 잘 못한 관계로 설명은 생략 ㅎㅎ...

강의 안볼거면 그냥 SGD를 사용하면 Linear VFA는 Linear이 할수 있는 최선으로 fitting된다는 정도로만 알아두자..

(물론 거의 무한하게 계속계속 update할 경우에 그렇게 된다는 거다..)

그런데 방금 전의 예시처럼 episode가 하나하나씩 들어오는 것들을 갖고 w를 update해도 되기야 하겠지만,

만약 episode들의 데이터가 있으면 그냥 그거 그대로 쭉 쓰면 안될까?

그러니까, episode를 하나하나씩 진행시키면서 update하지 말고 한방에 데이터들을 갖고 update할 수 있지 않을까?

...있으니까 말했겠지 뭐!

이를 Batch Monte Carlo Value Function Approximation이라고 부른다.

이름이 너무 길긴 하다..

이건 그냥 Linear Regression에 적용하듯, Analytic하게 적용이 가능하다.

위의 수식만 봐도 대충 이해 가능할 듯 하다.

Monte Carlo 방식은 여기까지만 알아보도록 하고,

이제 TD learning 방식으로 넘어가도록 하자.

일단 저번 저번 시간에 배웠던 TD learning을 잠깐 살펴 보자면,

TD learning은 DP 방식에서 사용하던 bootstrapping을 사용하며 MC 방식에서 사용한 sampling 방식도 사용했었다.

일단 본격적으로 들어가기 앞서, 지금까지 배운 세 가지 approximation을 생각보자.

1. (지금 하고 있는) function approximation

2. bootstrapping (DP / TD)

3. sampling (MC / TD)

그런데 지금 이 세개 모두 다 on-policy라는 것을 쉽사리 알 수 있을 것이다.

결국 지금 갖고 있는 데이터를 바탕으로 가는 것이니 말이다.

그러면, 결국 이 모든 것이 전부 supervised learning과 크게 다르지 않게 된다.

그렇다는 것은, 우리가 하고 있는 대부분의 것들 (위에 세가지) 는 convergence의 문제에서 어느 정도 자유로울 수 있다는 것이다. (거의 항상 수렴한다는 뜻)

그런데 이걸 왜 말해주냐고?

수렴하는지 안하는지 물어보지 말라고 하는 거 아닐까?

이제 본격적으로 들어가서,

원래 TD의 target (sampling)은 r + 𝛾Vπ(s') 이었다면,

VFA에서의 target은 r + 𝛾Vπ(s', w) (V위에 hat은 마음의 눈으로 보자 ㅎ)가 된다.

즉, w값도 찾아야 한다, 이말이다.

아무튼 이렇게 J(w)의 값을 최소화시키는 w값을 찾아가는 것이 바로 TDVFA이다. (길게 쓰기 싫어서 줄여씀)

그냥 위 식을 막 바꾸다 보면 아래까지로 바꿀 수 있다는 뜻 ㅎ

이건 TD때 비슷하게 했으니 그냥 넘기겠읍니다 ^^7

그리고 이를 의사코드로 바꾸면 위처럼 쓸 수 있다.

아까 전의 ppt 내용과 동일하다는 것을 알 수 있다. (거의)

아까 전의 그 예제로 돌아가보도록 하자.

기억이 안난다고?

예제 설명한거 복사해서 메모장에 붙여넣고 해보도록 하자 ㅎ

뭐 아무튼, 그 상황에서 MC 대신 TD learning을 적용해보자.

(참고로, 이번 상황에선 MC가 아닌 TD를 사용하므로, 0.999 어쩌구 하는 부분은 걸러도 된다. episodic 하지 않아도 되니깐 ㅎ)

episode는 [s1, a1, 0, s7]이라고 가정하고, 𝛾=0.9라고 하자.

그러면, w의 update는 어떻게 될까?

위의 수식을 그대로 빼다 박으면,

Δw = 0.5 * (0 + 0.9 * ([0 0 0 0 0 0 1 2] T [1 1 1 1 1 1 1 1]) - [1 0 0 0 0 0 0 2] T [1 1 1 1 1 1 1 1]) * [1 0 0 0 0 0 0 2]

     = 0.5 * (2.7 - 3) * [1 0 0 0 0 0 0 2]

     = 0.5 * -0.3 * [1 0 0 0 0 0 0 2]

     = [-0.15 0 0 0 0 0 0 -0.3]

그리고 이 Δw를 w에다가 더하면,

w = [0.85 1 1 1 1 1 1 0.7]

이런 식으로 바뀌는 것이다.

TD에서도 특정 값에 수렴하는 성질이 있다.

여기두 본인이 이해가 잘 안되는 관계로 생략 ㅎ..

참고로 짤막하게 지나가지만, TD가 MC보다 조금 더 좋은 성적을 내는 경향이 있다.

(그냥 조금 더 좋다)

이제 Control 부분을 다뤄 보도록 하자.

일단 들어가기 앞서서, Function approximation / Bootstrapping / Off-policy learning 을 한번에 적용하려 하면 불안정해질 수도 있다.

그러니까, converge가 안 될 수도 있고, 잘 될 수도 있다는 것이다.

그리고 Control을 할 때, 우리는 Q function을 사용할 것이다. (Action-Value 쌍)

일단 오라클이라는 존재가 우리에게 답을 알려준다면, 어떻게 하면 될까?

아까 전까지 했던 것과 거의 똑같이 하면 된다.

실제 Q값에서 Q의 예측값을 빼서, w값을 최소화시켜주면 되는 것이다.

(위에서는 SGD를 사용한다.)

오라클이 없다면?

아까처럼 feature vector을 만들어야 한다는 점은 동일하지만,

x(s) = [x1(s), x2(s) ... ] 가 아니라, state-action 쌍을 이루도록

x(s, a) = [x1(s, a), x2(s, a) ... ] 로 만들어 둔다.

그 외의 나머지 부분도 아까 전과 동일하다.

그리고 위의 내용들도 아까 전에 했던 것과 4강때 했던 것과 배우 비슷하다.

단지 Return값 Gt와 target이 Q와 관련된 식으로 변화하였고,

function approximator을 추가해줬을 뿐이다.

이쯤에서 5강 내용은 마치도록 하겠다.

본인이 이해를 못한 부분이 꽤 있어서, 이 뒤 부분은 사실 설명을 잘 할 자신이 없다.

나중에 다시 한번 정리하면서 수정할 날이 오면, 더 보충설명을 진행하도록 하겠다.

Taxi-v2 Q-learning

import gym
import random
import numpy as np

env = gym.make("Taxi-v2")
env.reset()

q_table = np.zeros([env.observation_space.n, env.action_space.n])

alpha = 0.8
gamma = 0.95
epsilon = 1

success = 0

for i in range(10000):
    epsilon = 5 / (1 + i)
    state = env.reset()
    epochs = 0
    done = False

    while not done and epochs < 500:
        epochs += 1

        # e-greedy
        if random.uniform(0, 1) < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(q_table[state])

        next_state, reward, done, info = env.step(action)

        # update Q
        old_value = q_table[state, action]
        next_max = np.max(q_table[next_state])

        new_value = old_value + alpha * (reward + gamma * next_max - old_value)
        q_table[state, action] = new_value

        state = next_state

        if reward > 0:
            success += 1

print("Success rate : " + str(success / 10000))
env.close()

FrozenLake Q-learning

(V3 : Deterministic, V0 : Stochastic)

import gym
import numpy as np

gym.envs.registration.register(
    id='FrozenLake-v3',
    entry_point='gym.envs.toy_text:FrozenLakeEnv',
    kwargs={'map_name': '4x4',
            'is_slippery': False}
)
# Stochastic
# env = gym.make("FrozenLake-v0")

# Deterministic
env = gym.make("FrozenLake-v3")
env.reset()

q_table = np.zeros([env.observation_space.n, env.action_space.n])

alpha = 0.6
gamma = 0.6
epsilon = 1
success = 0

for i in range(20000):
    epsilon = 1. / ((i // 1000) + 1)

    state = env.reset()
    epochs = 0
    done = False
    episode_reward = 0

    while not done and epochs < 500:
        epochs += 1
        
        # e-greedy
        if np.random.uniform(0, 1) < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(q_table[state])
            
        next_state, reward, done, info = env.step(action)
        
        # update Q
        old_value = q_table[state, action]
        next_max = np.max(q_table[next_state])

        q_table[state, action] = old_value + alpha * (reward + gamma * next_max - old_value)

        state = next_state

        episode_reward += reward

        if done and reward == 0:
            q_table[state][action] -= 1

        if reward == 1:
            success += 1

print("Success rate : " + str(success / 20000))
env.close()

오늘의 교훈

1. epsillon을 줄이자. (줄이는 코드를 안짜서 한참 헤멨음.)

2. epsillon을 줄이는 방법에 따라 결과가 천차만별이다. (Frozen-lake에서 epsillon을 1 / (i+1) 로 뒀더니 결과가 똥망함)

3. 시간은 얼마 없고 갈 길은 멀다. 빨리 공부해야지.

부록편에서는 지금까지의 강의를 하면서 개념 자체를 이해하는데 큰 필요성을 느끼지 못해 설명하지 않았던 수학적인 부분에 대해 설명합니다.

참고로 그렇게 수학적으로 깊게 파고들지는 않고, 간단히 개념을 이해할 정도로만 설명합니다.

1. 극한에 관하여

미분에 대해 알기 위해선 극한에 대해서 알아야 합니다.

그런데 사실 극한은 매우 간단합니다.

특정한 함수 f(x)가 L에 한없이 가까워 지는 것을 f(x)가 L에 수렴한다고 하고, 

이 때 L을 함수 f(x)의 x=a에서의 극한값이라고 합니다.

이 때, 이것을 기호로 lim x->a f(x) = L 으로 표현합니다.

주의하셔야 할 점은 x=a에서의 극한값이 x=a일 때의 값을 의미하진 않습니다.

x가 a에 수렴한다는 것은 x=a라는 것이 아니라, x의 값이 a에 최대한 근접했다는 뜻입니다.

위의 그래프를 보도록 합니다.

x가 a의 왼쪽 부분에서 시작해서 a에 한없이 가까워 진다고 해봅시다.

그럼 x가 a에 서서히 가까워질수록, f(x)의 값도 8로 가까워지게 됩니다.

마찬가지로 x가 a의 오른쪽 부분에서 시작해서 a에 한없이 가까워 진다고 해도,

x가 a에 서서히 가까워질수록 f(x)의 값도 8로 가까워집니다.

이 때 함수 f(x)에서 x=a에서의 극한값은 8이 됩니다.

2. 미분과 Gradient Descent

2-1. 평균 변화율이란?

함수에서 평균 변화율은 다음과 같이 정의합니다.

함수 y=f(x)에서 x의 값이 a에서 b까지 변할 때, 평균 변화율은

(f(x)의 변화량) / (x의 변화량) = (f(b) - f(a))/ (b-a) = (f(a) + x의 변화량) - f(a) / x의 변화량

으로 정의됩니다.

그리고, f(x)의 변화량과 x의 변화량은 기호로 각각 Δf(x), Δx라는 기호로도 나타낼 수 있는데, 그렇게 위 식을 쓰면

Δf(x) / Δx  =  (f(b) - f(a))/ (b-a)  =  (f(a) + Δx) - f(a) / Δx

라고도 쓸 수 있습니다.

막 어렵게 써놨지만, 간단히 말해서 함수 f(x)에서 a에서 b까지의 기울기를 의미합니다.

간단한 exercise로 y=x^2그래프에서 x의 값이 1에서 2까지 변할 때 평균 변화율을 생각해 보면,

Δf(x) = 2^2 - 1^2 = 4 - 1 = 3

Δx = 2 - 1 = 1

즉, 평균 변화율 Δf(x) / Δx = 3/1 = 3 이 됩니다.

그리고, 이는 (1,f(1))과 (2,f(2))를 잇는 직선의 기울기가 됩니다.

위 그래프에서 x가 x에서 x+h로 변할 때의 평균 변화율은 저 보라색 직선입니다.

공식으로 이해하지 말고, 그냥 간단히 직관으로 이해합시다.

2-2. 순간 변화율이란?

순간 변화율이란, 평균 변화율에서 x의 변화량이 0에 수렴할 때의 값을 의미합니다.

lim(b-a -> 0) (f(b) - f(a)) / (b-a) = lim (Δx->0)  Δf(x) / Δx = lim(Δx -> 0)  (Δ(x) + Δf(x)) / Δ(x) 

위의 그래프를 보며 이해해봅시다.

위의 그래프에서 왼쪽의 파란 점을 x, 오른쪽의 파란 점을 x+Δx라고 해봅시다.

이 때, Δx의 값을 대략 한 10에서 0으로 쭉 쭉 줄여보면,

Δx (x의 변화량)의 값도 0으로 쭉쭉 줄어들게 됩니다.

그리고, Δx를 계속해서 줄이면 x가 x에서 Δx까지 변할 때의 평균 변화율도 계속해서 변화합니다.

그러다가, Δx를 0에 수렴하게 줄이게 되면 저 두 점이 거의 만나게 될 것입니다.

(실제로 만나는 것은 아닙니다!! 극한값으로 가는것 뿐입니당)

이때 나오는 순간 변화율의 값을 미분계수라고 합니다.

그리고, 이 미분계수를 찾는 과정을 바로 미분이라고 합니다.

그런데 저 그래프를 잘 봐주시기 바랍니다.

순간 변화율은 Δx가 0으로 수렴할 때의 평균 변화율이라고 했으므로,

Δx가 0으로 수렴할 때, 파란 직선은 그래프의 접선으로 바뀌게 됩니다!

3. Gradient Descent

이를 토대로 Gradient descent를 이해해 봅시다.

Gradient Descent에서 우리가 하고 싶었던 것은 무엇인가 하면, 어떤 함수 f(x)가 최소가 되는 x를 찾는 것이었습니다!

위의 경우에는 x축에 w, y축에 J(w)로 적혀 있으므로 이를 따라 J(w)가 최소가 되는 w의 값을 찾아봅시다.

만약 처음 w값이 위의 그래프처럼 오른쪽 위쯤에 있다고 해봅시다.

그러면 그 W값을 미분하면, 위처럼 양수의 미분계수가 나오게 됩니다.

그런데 잘 생각해 봅시다.

미분계수가 양수라면, 즉 접선의 기울기가 왼쪽 아래와 오른쪽 위를 향하고 있다면 어떤 부분의 함숫값이 더 작을까요?

접선이 왼쪽 아래와 오른쪽 위를 향하고 있으므로, 당연히 아래를 향하는 왼쪽 부분의 함숫값이 더 작을 것입니다.

그리고 Gradient Descent의 목표는 J(w)가 최소가 되는 w의 값을 찾는 것이므로,

w를 함숫값이 더 작은 왼쪽 부분으로 넘겨 주어야 합니다.

즉, w값을 줄여야 한다는 것이죠.

즉, 어떤 함수에서 w값에 대한 미분계수가 양수라면, w의 값을 줄여주어야 합니다!

그렇다면 반대로 처음 w값이 왼쪽에 있었다면 어땠을까요?

그럼 x=w에서의 미분계수는 음수가 되었을 것입니다.

그리고 이 때는 접선의 기울기가 왼쪽 위와 오른쪽 아래를 향하고 있으므로,

함숫값은 왼쪽보다 오른쪽이 더 낮을 것입니다.

그리고 우리의 목적은 함숫값 J(w)를 최소로 하는 w의 값을 찾는 것이므로,

w를 함숫값이 더 작은 오른쪽 부분으로 넘겨 주어야 합니다.

즉, w의 값을 더 늘려야 하는 것이죠.

즉, 어떤 함수에서 w값에 대한 미분계수가 음수라면, w의 값을 늘려주어야 합니다!

그리고! 위에서 정리한 두개의 사실들을 하나로 합치자면,

"w의 값을 미분계수의 부호의 반대쪽으로 옮겨야 한다"입니다!

즉, 미분계수가 양수라면 w를 줄여야하고, 미분계수가 음수라면 w를 늘려야한다는 것이죠!

그러니, Gradient Descent에서 나오는 공식인

W := W - α * ∂/∂W cost(W)에서 α를 뺀 부분만큼은 이해가 되셨을 것 같습니다. (∂/∂W cost(W)는 cost(W)를 W에 대해 미분한다는 뜻입니다.)

양수를 빼면 줄어들고, 음수를 빼면 늘어나기 때문에, 저 미분계수에다가 α를 곱한 값을 w에서 빼주면 된다는 것입니다!

그런데, 왜 α를 곱해줘야 할까요?

미분계수에다가 α를 곱하지 않으면 w의 값을 한 번에 너무 멀리 보내버리게 되기 때문입니다.

그러면 위의 그림에서 왼쪽의 그래프마냥, J(w)값이 줄어들기는 커녕 늘어나는 방향으로 w가 바뀔 수도 있습니다.

그리고 마냥 미분계수만큼만 빼버리면 웬만하면 저런 식으로 w값이 날라가게 되므로,

α값을 곱해주어 너무 멀리 가는 것을 방지해 주는 것입니다.

(그러니까 일반적으로 α는 1보다는 작고 0보다는 큰 값이겠지요. 참고로, α는 learning rate라고 불립니다.)

이러한 이유에서, Gradient Descent를 반복하면, 즉!

W := W - α * ∂/∂W * cost(W)를 반복하면, 결국 w의 값이 J(w)가 최소가 되는 값으로 수렴하게 된다는 것을 알 수 있습니다!

이렇게 미분의 기본적 개념과 함께 Gradient Descent가 무엇인지 알아보았습니다.

혹시 이해가 덜 되었거나 더 알고싶은 점이 있다면 댓글로 물어보세요!!

이번 포스팅에서는, Logistic (regression) classification에 대해 알아볼 것입니다.

(왜 중간에 (regression)이 있는지는 나중에 다룰게요!)

우선 Logistic (regression) classification이 정확히 뭔지 알아보기 전에, 일단 Binary Classification이 뭐였는지 먼저 알아봅시다.

Binary Classification은 두개로 이루어진 값들을 분류하는 작업입니다.

가령 스팸메일 필터링을 한다고 했을 때는, 이 메일이 스팸인지 그냥 메일인지 확인해야 하겠죠?

이 때 이 메일을 스팸인지/그냥 메일인지 두 가지중 하나로 분류하는 작업을 바로 Binary Classification이라고 합니다.

그런데 이런 작업을 할 때, 어떤 메일이 스팸인지 / 그냥 메일인지 구분할 때 0과 1로 인코딩 작업을 거칩니다.

가령 스팸이면 1, 그냥 메일이면 0으로 두는 것이죠.

그런데 왜 이렇게 인코딩을 할까요?

왜 이러는지는 regression의 성질을 생각하면 조금 이해가 될 듯 합니다.

(우리가 배우는 모델은 classification 작업에 사용될 뿐이지, 엄연히 regression모델입니다!!!)

저번 시간까지 배웠던 linear regression의 결과값은 어떻게 나왔나요?

가령 성적을 예측하는 regression모델이라고 한다면, 예측한 점수를 결과값으로 내게 될 것입니다.

이렇듯, regression모델은 특정한 '값'을 '예측'하는데 사용됩니다.

그렇기 때문에 이런 regression 모델로 분류를 진행하려면, 이런 class들을 (스팸인지 아닌지) '값'으로 설정해야 합니다.

스팸 메일은 1, 그냥 메일은 0.. 이렇게 말이죠.

그리고 그렇게 예측한 값이 1에 가깝다면 스팸메일이다! 라고 예측을 하고,

예측한 값이 0에 가깝다면 진짜 메일이다! 라고 예측을 하는 겁니다.

그런데, 그럼 그냥 Linear regression 모델을 그냥 사용하면 안되는 걸까요?  안되니깐 다른 모델을 배우는거겠죠?

자, 위의 예시를 봅시다.

위의 그래프는 x축에 공부한 시간, y축에 pass / fail (1 / 0)이 그려진 그래프로,

공부한 시간 비례 시험에서 통과할지 실패할지 예측하는 모델을 그린 것입니다.

그럼 이것을 Linear regression모델로 짤 수도 있지 않을까요?

fail 과 pass를 나누는 직선 하나를 그린 뒤에,

그 직선의 y값이 0.5 이하이면 fail, 아니면 pass라고 하면 잘 작동할것 처럼 보이기도 합니다.

그런데, 저 오른쪽 끝부분 (아래에 50적혀있는) 의 동그라미를 봅시다. 

만약 어떤 학생이 정말 시험에서 너무 pass하고 싶어서 50시간이나 공부를 해서 pass를 받았다고 가정해 봅시다.

그러면 어떤 문제점이 발생하느냐 하면,

linear regression의 Hypothesis H(x) = WX + B 함수가 저 오른쪽의 동그라미도 감안하고 측정이 되므로,

저 동그라미가 없을때보다 직선이 조금 더 오른쪽 아래로 기울어지는 현상이 발생합니다.

그런데 이렇게 되면 원래는 pass였던 것들의 y값이 0.5 아래로 내려가버리면서 fail로 처리되는 문제가 발생하게 됩니다.

(위의 그래프에 그려진 파란 직선 두개 참고)

이렇듯, Binary classification (사실 classification 전체 다)를 수행하는 데 Linear Regression 모델은 적합하지 못합니다.

Linear regression을 사용하기 애매한 이유가 또 있습니다.

Linear regression의 경우 Hypothesis 함수를 H(x) = Wx + b 로 정의합니다. 그쵸?

그런데 어차피 y값들 (class, 스팸인지 아닌지)는 0이거나 1이 된다는 것을 우리는 이미 알고 있습니다.

(0, 1 인코딩을 이미 했고, 그렇게 분류하는것이 binary classification의 목적이니까요.)

그런데 Linear regression의 H(x)는 1보다 엄청 큰 수를 결과값으로 뱉을 수도 있고, 0보다 엄청 작은 수를 결과값으로 뱉을 수 있습니다.

가령 H(x) = 100x 라는 hypothesis가 있다고 해봅시다.

우리의 목적은 데이터들을 0과 1 둘중 하나의 값으로 분류하는 것이 목적이므로,

1에 가까운 값은 1로 분류하고, 0에 가까운 값은 0으로 분류하게 될 것입니다.

그런데 H(x) = 100x가 되버리면 (대략적으로) x가 0.01 이상일때는 모두 1로, x가 0 이하일때는 모두 0으로 분류되게 됩니다.

이러면 어떤 문제점이 발생해 버리냐하면, x값에 너무 민감하게 반응하는 모델이 만들어지게 됩니다.

즉, 연산상으로는 매우 작은 값(0.01)만 바뀌어도 아예 분류 자체가 바뀌어버리게 되는 것입니다.

이는 아까 위에서 설명했던 문제와 겹치며 linear regression 모델을 classification을 하는 용도로 사용하기 힘들게 만듭니다.

이를 해결하기 위하여 나온 것이 바로 logistic function (sigmoid function 이라고도 한다) 입니다.

원래 linear하던 H(x) = wx + b를 0과 1 사이의 함수로 바꿔주는 함수입니다.

수식으로 나타낸다면, g(z) = 1 / (1+ e^-z) 가 됩니다.

이렇게 hypothesis에 sigmoid 함수를 씌워주면, 무슨 함수였던지간에 결과값이 모두 0과 1 사이로 나오는 함수를 만들어 줄 수 있습니다.

(왜 이런 값이 나오는지 수학적으로 설명하는 것은 나중에 부록 편에서 다루겠습니다.)

그리고 이것을 Logistic regression의 Hypothesis로 나타낸다면 위와 같은 수식으로 나타내어 집니다.

(W T X 는 그냥 간단하게 W * X로 생각해 주시면 됩니다.

multi-variable의 경우에서도 사용할 수 있도록 만든 hypothesis인지라 저런 식이 들어갑니다.)

그리고 이렇게 H(x)의 값이 0과 1사이로 나오면, 사용하기에 매우 편리해 지게 됩니다.

위의 Hypothesis 함수로 regression을 한 결과값이 0.5이상인 경우엔 1로 분류하고, 0.5보다 작으면 0으로 분류하면 되는 것이죠.

(사실 아까 전에 0,1 encoding을 한 이유도 이것 때문입니다.)

*참고 : Logistic "Regression" 인 이유!

많은 분들이 왜 이 모델이 Regression 모델인지 헷갈려 하곤 합니다.

그러니까, Logistic regression은 사실 classification을 하는데 사용하는데, 왜 regression이라고 불리는가를 헷갈려 하는 것이죠.

하지만 Logistic regression모델은 결과값이 0과 1 사이로 한정되는 특성상 classification을 하는 데 사용되는 모델이긴 하지만, 결과값으로 특정한 "값"을 도출해내는 모델입니다.

가령, 성적을 예측하는 Linear regression은 점수 그 자체를 결과값으로 도출합니다. (10점, 30점, 60점 등등...)

그와 비슷하게 스팸 메일인지 아닌지를 분류하는 Logistic regression 모델은 0과 1 사이의 값 자체를 결과로 냅니다. (0, 0.2, 0.8 등등...)

그러니까, Logistic Regression은 입력값 x에 대해 0과 1로만 이루어진 y값에 최대한 가깝게 그려질 수 있는 함수를 만들어내는 모델인 것입니다.

그리고 결과값이 0.5보다 큰 (즉, 1에 가까운) 값들은 죄다 1로 분류해 버리는 것이고,

결과값이 0.5보다 작은 (즉, 0에 가까운) 값들은 죄다 0으로 분류해 버리는 것입니다.

그러니깐 그냥 이제부터 Logistic (regression) classification이 아니라

logistic regression모델이라고 부르겠습니다.

그런데, 이렇게 Hypothesis를 바꿔버리면 원래 쓰던 cost function은 사용하지 못합니다.

왜냐 하면, 원래 쓰던 Cost function을 여기다가도 적용해버리면 non-convex한 function이 나오게 되기 때문입니다.

(cost function이 convex function이어야 하는 이유는 2강 (https://cding.tistory.com/21) 에서 다뤘습니다!)

+ 왜 그렇게 되는지는 나중에 부록편에서 따로 더 설명하겠습니다.

그래서 logistic regression의 cost function은 따로 만들어 줘야 합니다.

logistic regression의 cost function은 다음과 같이 정의합니다 : 

y=1일때 c(H(x), y) = -log(H(x))

y=0일때 c(H(x), y) = -log(1 - H(x))

(단, 여기서 log는 상용로그가 아니라 자연상수 e를 밑으로 갖는 자연로그입니다.)

그런데 왜 cost function을 이렇게 정의했느냐를 제대로 설명하려면 엄청난 수학의 압박이 느껴지게 됩니다...

그러니 일단 지금은 직관적으로 왜 cost function을 이렇게 정의하는지만 알아봅시다.

그냥 지금 간단하게 생각해 봅시다.

(위의 그래프들은 x축에 h(x)값, y축에 cost 값을 나타내는 그래프입니다!!)

일단 y=1인 경우, 즉 h(x) = 1인 경우엔 왜 cost function은 -log(H(x))가 될까요?

(왼쪽 그래프 참고)

h(x)값이 0에서 1으로 이동하면 cost 값은 ∞에서 0으로 점점 줄어들게 되는 것을 확인할 수 있습니다.

즉, h(x)가 정답인 1로 가면 갈수록 cost는 줄어들고, 오답인 0으로 가면 갈수록 cost가 늘어납니다.

이러면 우리가 원하는 합리적인 cost function이 완성된 것이겠죠?

반대로, y=0인 경우, 즉 h(x) = 0인 경우에 cost function이 -log(1-H(x)) 인 이유도 동일합니다.

h(x)값이 1에서 0으로 이동하면 cost 값은 ∞에서 0으로 점점 줄어들게 되는 것을 확인할 수 있습니다.

즉, 이번에는 h(x)가 정답인 0로 가면 갈수록 cost는 줄어들고, 오답인 1으로 가면 갈수록 cost가 늘어납니다.

그냥 이정도로만 이해해 주시고, 왜 cost function을 이렇게 설정했는지는 나중에 부록 편에서 다루겠습니다.

그리고 위처럼 y=1일때와 y=0일때로 나누어도 좋겠지만,

직접 컴퓨터로 연산을 할 때는 간단한 수식으로 나타내는 것이 훨씬 좋겠죠?

그래서 나온 공식의 위의 파란 박스가 쳐진 수식입니다.

어려울것 하나 없습니다!

y=0일 때는 -y * log(H(x)) 부분이 0이 되면서 자연스럽게 -log(1 - H(x)) 라는 cost function이 나오게 되고,

y=1일 때는 (1-y) * log(1 - H(x)) 부분이 0이 되면서 자연스럽게 -log(H(x)) 라는 cost function이 나오게 됩니다.

그리고 컴퓨터로 연산을 할 때는 if문을 사용해서 y==1인 경우와 y==0인 경우로 나누지 않고,

그냥 위의 수식을 사용하게 될 것입니다.

(위의 ppt의 Gradient decent는 오타입니다...ㅎㅎ;)

Gradient descent는 그냥 다른 모델과 동일하게 cost(W)를 W에 대해 미분하는 것으로 적용하면 됩니다.

그리고 이를 tensorflow를 사용해서 코드로 적용할 때는 그냥 GradientDescentOptimizer(a) 로 적용하면 됩니다.

(실제 cost값을 미분하면 어떤 값이 나오는지는 그냥 설명하지 않겠습니다. 매우 불필요합니다. 부록에서도 설명 안할듯)

이렇게 Logistic regression에 대해서 알아봤습니다.

사실 이렇게만 설명해도 Logistic regression이 어떤 개념인지는 모두 이해하셨으리라 믿지만,

나중에 부록편에서 조금 더 수학적으로 접근해서 왜 cost function이 저렇게 나오는지 설명하겠습니다.

그럼 다음엔 softmax regression (multinomial classification)으로 찾아뵙겠습니다!