Regression Algorithm

통계학에서 Regression Algorithm이란 다른 변수에 영향을 주는 원인에 해당하는 독립변수와 독립변수로 인해서 영향을 받는 결과에 해당하는 종속변수가 존재할 때, 두 변수들 사의의 관계를 구체적인 함수의 식으로 정의하고 새로운 독립변수가 주어졌을때, 이에 해당하는 종속변수를 예측하는 알고리즘이다. 이때 독립변수와 종속변수가 각각 하나일때는 Simple Regression Algorithm이라고 하고, 종속변수가 1개이고, 독립변수가 2개이상일 경우 Multiple Regression Algorithm이라고 한다. 

SVR(Support Vector Regression)도 Regression Alogorithm의 일종이다. SVR은 SVM(Support Vector Machine)의 일반화된 방법이다. SVM은 기계학습의 하나로 패턴인식, 자료분석을 위한 Supervised Learning(SL)의 일종으로 주로 두 Categories로 나뉘는 데이터의 집합이 주어졌을 때, 어떤 category에 속할지 판단하는 알고리즘이다. SVM은 선형분류는 물론 Kernel Trick을 사용하여 비선형 분류에도 사용가능하다. SVM은 데이터를 분류하는 기준이 되는 Hyper plane을 선택하는데 두 클래스 사이에 가장 큰 분류 마진을 갖는 Hyper Plane을 선핵하는 방법이 사용된다. 이 때 Support Vector는 Hyper plane에 가장 가까운 데이터로 정의된다. 

강화학습(Reinforcement Learning, RL) 알고리즘은 기계학습의 일종으로, 지도학습(Supervised Learning, SL)과 달리 입력에 대한 출력이 쌍으로 주어지지 않아 하나의 에피스도내의 행동들이 올바른 행동인지 판단할 정의가 없어 각각의 행동에 대해 즉각적인 학습이 이루어 지지 않는다. 이 때문에 지도학습이 Offline Learning이라면  강화학습은 Online Learning에 초점을 맞춘다. 이 과정은 새로운 Policy를 학습하기 위해서 행동을 탐색하는 Exploration과 기존에 학습했던 Policy로 행동을 선택하는 Exploitation의 균형을 통해 이루어진다. 강화학습이란 정의된 환경(Environment)안에서 에이전트(Agent)가 현재의 상태(State)를 인식하여, 선택가능한 행동(Action)들 중 보상(Reward)을 최대화하는 행동 또는 행동 순서를 선택하는 방법인 정책(Policy)를 학습하는 방법이다. 강화학습 알고리즘을 통해 해결할 수 있는 문제는 제어, 시뮬레이션 기반 최적화, 다중 에이전트 시스템, 통계학, 유전 알고리즘 등 매우 포괄적이다. 최적화 알고리즘과 비슷한 목표를 가지고 연구되나, 최적화 알고리즘에서는 최적해의 존재와 특성에 초점을 맞추지만, 강화학습 알고리즘의 경우 학습과 근사의 측면에서 문제를 접근한다. 
 
강화학습 알고리즘은 Markov Decision Process(MDP)형태로 환경이 주어진다. MDP현태로 주어진 문제는 Dynamic Programming(DP) 알고리즘으로 해결이 가능하다. DP에서는 환경에 대한 정보를 모두 알고 있어 보상을 최대화하는 방법을 Deterministic하게 결정할 수 있다. 반면 RL에서는 환경에 대한 정보를 모두 알 수 없는 상황에서 보상을 최대화하는 정책을 Deterministic하게 결정할 수 없는 경우 주로 사용된다. 

알파고의 경우 DQN(Deep Q Network)을 기초로 하여 RL알고리즘에 딥러닝 방법을 접목시킨 강화학습알고리즘을 사용하였다. 하지만 DQN알고리즘은 불연속적인 저차원 액션공간(Low Dimensional Action Space)에서만 다룰 수 있는 한계점이 있다. 대부분 제어 문제들에서는 High Dimensional Action Space를 다루어야 한다. 연속공간을 임의로 Discretize하게 되면 Curse of Dimensionality에 빠질 수 있다. 이를 해결하기 위해 고안된 Deep Deterministic Policy Gradient(DDPG) 알고리즘은 연속적인 High dimensional action space에 사용할 수 있다. DDPG는 기본적으로 Deterministic Policy Gradient(DPG) 알고리즘에 기초한다. DQN에서 사용된 아이디어인 Replay Buffer와 Target Q network을 사용한다. 

[관련글 보기]

2018/11/23 - RA vs RL

2018/11/23 - GAN(Generative Adversarial Network) 완전 정복하기

2018/11/23 - DCGAN

2018/11/23 - 파이썬 데이터 분석 3종 세트 - statsmodels, scikit-learn, theano

2018/11/23 - 주피터: 파이썬 노트북, 그리고 파이썬 노트북을 넘어서

2018/11/23 - [인공지능로봇/머신러닝강좌] - 파이썬 데이터 분석 3종 세트 - statsmodels, scikit-learn, theano

2018/11/23 - [인공지능로봇/머신러닝강좌] - 주피터: 파이썬 노트북, 그리고 파이썬 노트북을 넘어서

김대권
슬라이드: https://speakerdeck.com/nacyot/jupiteo-paisseon-falseteubug-paisseoneul-neomeo
동영상: https://www.youtube.com/watch?v=VbbXUKigVfs


후기: iPython이 왜 시작되었는지, 웹인터페스의 개념, 클라이언트와 서버, 커널과 멀티커널, REPL의 개념, Jupyter 등을 역사적으로 이해할 수 있는 동영상


평점: ★★★★★

Abstract
Function Approximation은 RL에 필수적이다. 그러나 가치함수를 근사화하고 그것으로 부터 정책을 결정하는 기존의 방법은 이론적으로 다루기 힘든 것으로 증명된 바 있다. 본 논문에서는 다른 접근방법을 대안으로 제시한다. 여기에서는 정책이 function approximator로 표현된다.  그리고 그 function approximator는 policy변수에 대한 expected reward의 gradient에 따라 update된다. 

Environment의 Daynamics는 다음으로 주어지는  State transition probabilities와 

다음식으로 표현되는 expected reward에 의해 characterized된다. 

그리고 각 시간 t에서의  에이전트의 Decision making Procedure는 다음과 같이 주어지는 policy함수로 characterized 된다.

 여기서 policy함수는 미분가능(differntiable)한 것으로 가정한다. 에이전트의 objective를 formulating하는 두가지 방법이 있는데, 그 중 하나가 average reward formulation이다. 이 방법에서는 policies들이 각 step당 long-term expected reward에 따라 rank된다. 

여기서 

는 states의 stationary distribution이다. 이러한 average reward formulation 방법에서는 state-action pair의 value는 다음과 같이 정의된다. 

두번째 formulation으로 designated start state s0가 있고, 그로부터 얻어지는 long-term reward 만을 고려하는 방법이다. 

이 formulation방법에서는 value는 다음과 같이 정의된다. 

여기서

은 discount rate이다.  이 방법에서 states의 stationary distribution은 s0에서 시작하면서 겪게되는 각 stated들의 discounted weighting으로 다음과 같이 정의된다. 

1713-policy-gradient-methods-for-reinforcement-learning-with-function-approximation.pdf