Differentiable Architecture Search(DARTS)는 NAS 알고리즘 일종으로 기존 NAS에서 사용하던 강화학습 기반의 discrete한 후보 선택 방법을 미분 가능하고 연속적인 최적화 방법으로 바꾸었다.
입력 $x=[64,3,32,32]$에 연산자 $op$를 적용한다. $op$ 후보가 8개라 가정하자. 이 중 1번만 적용하고 나머지 7개는 무시하면 $x'=op_1(x)$이다.
만일 2번, 5번 연산자를 동일한 가중치로 적용하고 나머지를 무시하면
$x'=0.5 \cdot op_2(x)+0.5 \cdot op_5(x)$
이다. 단, 이 연산이 성립하려면 $op_2(x)$와 $op_5(x)$는 같은 shape를 가져야 한다.
8개 모두 적용 시
$x'=\sum w_i \cdot op_i(x)$
이다.
DARTS는 $w_i(i=0...7)$ 탐색을 통해 $x'$가 연결되어 만든 net의 validation loss 최소화로 NAS 해결방법을 찾았다.
이는 $x'$가 만드는 loss를 $w_i$에 대해 편미분해 구한다.
통상 CNN에서 층(layer)이라 함은 Conv나 ReLu 등 연산을 선택 후, 이 $op$에 관련된 학습 가중치를 net loss가 최소화되게 구하는 것이다.
그런데, 이종의 $op$가 결합되어 층 하나를 구성한다면 어떤 연산을 지배적으로 사용할건지를 나타내는 연산 가중치 $w_i$ 결정과 각 연산에 들어 있는 학습 가중치 결정 2가지 문제를 함께 풀어야 한다.
두 타입 인자 결정을 동시에 할 수는 없다. $op$ 가중치 최적화, CNN 학습 가중치 최적화를 차례로 수행해야 한다. DARTS는 두 단계 수행 방법을 설명한다.
Reference
[1] DARTS paper
[2] pytorch-DARTS
2018년 7월 31일 화요일
Efficient NAS
Neural Architecture Search(NAS)는 딥러닝 넷 구조를 자동으로 찾는 알고리즘이다. 이미지 분류용 NAS 알고리즘을 살펴보자.
먼저 입력(image or feature map)에 적용할 복수의 연산 후보들을 정의하고, net 내 레이어들이 어떤 연산을 선택할지, 그리고 레이어들을 상호간 어떻게 연결할지를 함께 결정해야 한다.
CNN 구조의 경우, 연산 후보는 sepconv3x3, sepconv5x5, maxpool3x3, avgpool3x3, identity(skip-connection) 등이 될 수 있다.
NAS는 2가지로 달성 가능한데, Macro 및 Micro search이다.
Macro는 전체 넷을 한번에 설계한다. 이 경우 개입되는 파라메터가 너무 많아 문제 규모가 커지므로 풀기도 어렵고 성능도 낮다.
Micro는 Macro 문제점을 해결하기 위해 Cell 개념을 도입한다. Cell이란 내부에 소규모 연결 요소들을 가지는 단위 구조이다. Cell을 먼저 설계하고 Cell간을 연결하여 전체 구조를 만든다. Cell간 연결은 다음 처럼 미리 정해 놓는다.
CNN 경우,
Cell(N)-Cell(N)-Cell(R)-Cell(N)-Cell(N)-Cell(R)
로 할 수 있다.
N은 Normal, R은 Reduction인 2가지 타입 cell이 있다. Normal은 입력 이미지(특징맵) 크기를 유지하여 출력하고 Reduction은 입력 크기를 절반으로 줄여 출력한다.
Cell은 입력 2개와 출력 1개를 가지며 이전 Cell 출력을 입력으로 사용한다. 맨 앞 Cell 입력 2개는 이미지 입력을 동일하게 사용한다.
정리하면, Micro 탐색으로 Cell 구조를 먼저 설계하고 이들을 연결하여 전체 넷을 구성하면 설계 파라메터도 줄이고 실용적이며 성능도 좋다.
CNN 예에서 N셀은 4개이며 내부 구조가 동일하다. 2개의 R셀도 동일 구조이다. N과 R은 서로 구조가 다르므로 생성 알고리즘은 같지만 객체는 따로 유지한다.
Cell 설계는 RNN을 사용한다. RNN 사용 이유는 Cell 내 노드(layer) 연결은 입력 2개에서 시작하여 차례로 새로운 노드(layer)을 생성, 추가하면서 구조를 키워 나가는데, 생성 노드는 이전 노드에 의존적이고 노드 상관성을 가지기 때문이다.
더 이상 후속 연결이 없는 노드들은 concat으로 합쳐 단일 출력으로 내 보낸다.
RNN 출력 예를 보면,
2255/3355/4455/5555/6655
이고 5회 step 동안 전부 20개의 출력을 준다. 숫자는 리스트 크기이고, 인덱스를 저장한다.
각 step 당 4개 출력은 (node_L, node_R, op_L, op_R)이다. node_L과 node_R은 이전 입력 어떤 것을 선택할지를, op_L, op_R은 입력에 어떤 연산을 적용할지를 보여준다.
예를 들면, 2255에서 길이 2는 node_L이 cell 두 입력 중 1개를 선택하며 one-hot vector [0,1] 또는 [1,0]를 사용하기 때문이다. 길이 5는 후보 연산 중 1개를 선택하므로 [0,1,0,0,0] 또는 [0,0,0,1,0] 등이다.
3355는 Cell에 들어간 두 입력을 이용하여 앞 단계에서 새로운 노드(layer)가 이미 생성되었으므로 이제 선정할 후보는 세개이다. 따라서 3이 되고, 연산 후보는 불변이니 5로 유지된다.
References
[1] ENAS paper
[2] Keras-enas
[2] Tensorflow-enas
먼저 입력(image or feature map)에 적용할 복수의 연산 후보들을 정의하고, net 내 레이어들이 어떤 연산을 선택할지, 그리고 레이어들을 상호간 어떻게 연결할지를 함께 결정해야 한다.
CNN 구조의 경우, 연산 후보는 sepconv3x3, sepconv5x5, maxpool3x3, avgpool3x3, identity(skip-connection) 등이 될 수 있다.
NAS는 2가지로 달성 가능한데, Macro 및 Micro search이다.
Macro는 전체 넷을 한번에 설계한다. 이 경우 개입되는 파라메터가 너무 많아 문제 규모가 커지므로 풀기도 어렵고 성능도 낮다.
Micro는 Macro 문제점을 해결하기 위해 Cell 개념을 도입한다. Cell이란 내부에 소규모 연결 요소들을 가지는 단위 구조이다. Cell을 먼저 설계하고 Cell간을 연결하여 전체 구조를 만든다. Cell간 연결은 다음 처럼 미리 정해 놓는다.
CNN 경우,
Cell(N)-Cell(N)-Cell(R)-Cell(N)-Cell(N)-Cell(R)
로 할 수 있다.
N은 Normal, R은 Reduction인 2가지 타입 cell이 있다. Normal은 입력 이미지(특징맵) 크기를 유지하여 출력하고 Reduction은 입력 크기를 절반으로 줄여 출력한다.
Cell은 입력 2개와 출력 1개를 가지며 이전 Cell 출력을 입력으로 사용한다. 맨 앞 Cell 입력 2개는 이미지 입력을 동일하게 사용한다.
정리하면, Micro 탐색으로 Cell 구조를 먼저 설계하고 이들을 연결하여 전체 넷을 구성하면 설계 파라메터도 줄이고 실용적이며 성능도 좋다.
CNN 예에서 N셀은 4개이며 내부 구조가 동일하다. 2개의 R셀도 동일 구조이다. N과 R은 서로 구조가 다르므로 생성 알고리즘은 같지만 객체는 따로 유지한다.
Cell 설계는 RNN을 사용한다. RNN 사용 이유는 Cell 내 노드(layer) 연결은 입력 2개에서 시작하여 차례로 새로운 노드(layer)을 생성, 추가하면서 구조를 키워 나가는데, 생성 노드는 이전 노드에 의존적이고 노드 상관성을 가지기 때문이다.
더 이상 후속 연결이 없는 노드들은 concat으로 합쳐 단일 출력으로 내 보낸다.
RNN 출력 예를 보면,
2255/3355/4455/5555/6655
이고 5회 step 동안 전부 20개의 출력을 준다. 숫자는 리스트 크기이고, 인덱스를 저장한다.
각 step 당 4개 출력은 (node_L, node_R, op_L, op_R)이다. node_L과 node_R은 이전 입력 어떤 것을 선택할지를, op_L, op_R은 입력에 어떤 연산을 적용할지를 보여준다.
예를 들면, 2255에서 길이 2는 node_L이 cell 두 입력 중 1개를 선택하며 one-hot vector [0,1] 또는 [1,0]를 사용하기 때문이다. 길이 5는 후보 연산 중 1개를 선택하므로 [0,1,0,0,0] 또는 [0,0,0,1,0] 등이다.
3355는 Cell에 들어간 두 입력을 이용하여 앞 단계에서 새로운 노드(layer)가 이미 생성되었으므로 이제 선정할 후보는 세개이다. 따라서 3이 되고, 연산 후보는 불변이니 5로 유지된다.
References
[1] ENAS paper
[2] Keras-enas
[2] Tensorflow-enas
2018년 7월 5일 목요일
2018년 5월 8일 화요일
Attention
$\underline{Dense\ attention}$
입력 특징(속성)의 어떤 하나에 attention
inputs = Input(shape=(32,)) #32개 중 중요한 것 찾음.
# Dense출력수는 inputs수와 같고 softmax로 확률값 만듬
attention_probs = Dense(32, activation='softmax')(inputs) #attention vector
#dense출력을 inputs에 곱해 어떤 값에 attention할지 $\mathit{dense가\ 학습}$
attention_mul = merge( [inputs, attention_probs], output_shape=32, mode='mul')
# attention된 vector를 분류기에 넣음
attention_mul = Dense(64)(attention_mul)
output = Dense(1, activation='sigmoid')(attention_mul)
model = Model(input=[inputs], output=output)
$\underline{시계열\ attention}$
Timestep 어떤 순간에 attention하게 한다.
# 20 Timestep 중 중요한 step
# inputs.shape = (batch_size, TIME_STEPS, input_dim) #(None,20,32)
# Timestep <-> 특징축 교환
a = Permute((2, 1))(inputs) #(None,32,20)
#Timestep축 값 20에 대한 정규화
a = Dense(TIME_STEPS, activation='softmax')(a) #(None,32,20):
# 다시 되돌림
a_probs = Permute((2, 1))(a) #(None,20,32)
#두 값 곱함:(None,20,32)
#Timestep 어디에 attention할지 $\mathit{dense가\ 학습}$
output_attention_mul = merge([inputs, a_probs], mode='mul')
$\underline{영어-일어\ 번역}$
$\mathit{먼저\ encoder-decoder\ 구조\ 만듬}$
# (None,20) -> (None,20,64): 20자 영단어를 64차원 임베딩
encoder = Embedding(54, 64, input_length=20, mask_zero=True)(encoder_input)
# 매 Timestep마다 출력(64개)
encoder = LSTM(64, return_sequences=True, unroll=True)(encoder)
#맨 마지막 timestep 값(None, 64)
encoder_last = encoder[:,-1,:]
# (None,20) -> (None,20,64) #20자 일단어를 64차원 임베딩
decoder = Embedding(89, 64, input_length=20, mask_zero=True)(decoder_input)
# encoder 출력 (None,64) 2개를 초기 state로 입력
decoder = LSTM(64, return_sequences=True, unroll=True)(decoder, initial_state=[encoder_last, encoder_last])
$\mathit{attention\ 기능\ 부가}$
###################################################
# encoder, decoder 출력은 같은 뜻이니 서로 유사해야 한다고 하면
# 영어 추출한 64개 속성과 일어추출 64 속성은 비슷해야 한다.
# -> 둘 다 2번축끼리 곱함: (None,20,64)x(None,20,64)->(None,20,20)
#
# 아래 코드 보면 decoder가 앞, encoder가 뒤 이므로 출력 Tensor는 (None,20,20)이고
# 1번축 20개는 decoder timestep, 2번축 20개는 encoder timestep이면서 pdf로 정규화.
# 1번축 $i$번째 step입력에 대응되는 encoder 20개 입력간 유사성을 pdf로 표현한다.
attention = dot([decoder, encoder], axes=[2, 2])
# (None,20,20) 속성 2번축 20개 값 정규화
attention = Activation('softmax', name='attention')(attention)
# 이는 encoder 출력 중 어디에 집중해 주어야 하는지를 모델링
# attention=(None,20,20) 2번축 x encoder=(None,20,64) 1번축
# -> (None, 20,64)
# encoder timestep에 대한 prob.
context = dot([attention, encoder], axes=[2,1])
#
#
# attention된 encoder features + decoder features 결합
# encoder 집중화 출력(context정보)과 decoder출력을 묶음
# (None,20,64)+(None,20,64) -> (None,20,128)
decoder_combined_context = concatenate([context, decoder])
# Has another weight + tanh layer as described in equation (5) of the paper
# 128 -> 64 -> 89: 3층 분류기
output = TimeDistributed(Dense(64, activation="tanh"))(decoder_combined_context)
output = TimeDistributed(Dense(89, activation="softmax"))(output)
# 모델
model = Model(inputs=[encoder_input, decoder_input], outputs=[output])
model.compile(optimizer='adam', loss='binary_crossentropy')
$\cdot$앞에서는 input를 dense에 넣어 input 어디에 attention할지를 dense가 학습
$\cdot$여기서는 dense 대신 decoder 사용. 즉, decoder출력 만드는 RNN 후반부가 attention 학습
$\cdot$영어->일어 번역으로 encoder에 영어입력, decoder에 일어 입력이다.
$\cdot$일어입력 20 timestep 어떤 순간 특징 64개는 영어 20 timestep 각 순간 특징(64개)와 유사성 체크.
(ex.) 일어 5 step째 입력과 영어 0~19 step별 유사성: decoder X encoder이므로 (None,5,:)에 저장.
일어 7 step째 입력과 영어 0~19 step별 유사성: (None,7,:)에 저장.
입력 특징(속성)의 어떤 하나에 attention
inputs = Input(shape=(32,)) #32개 중 중요한 것 찾음.
# Dense출력수는 inputs수와 같고 softmax로 확률값 만듬
attention_probs = Dense(32, activation='softmax')(inputs) #attention vector
#dense출력을 inputs에 곱해 어떤 값에 attention할지 $\mathit{dense가\ 학습}$
attention_mul = merge( [inputs, attention_probs], output_shape=32, mode='mul')
# attention된 vector를 분류기에 넣음
attention_mul = Dense(64)(attention_mul)
output = Dense(1, activation='sigmoid')(attention_mul)
model = Model(input=[inputs], output=output)
$\underline{시계열\ attention}$
Timestep 어떤 순간에 attention하게 한다.
# 20 Timestep 중 중요한 step
# inputs.shape = (batch_size, TIME_STEPS, input_dim) #(None,20,32)
# Timestep <-> 특징축 교환
a = Permute((2, 1))(inputs) #(None,32,20)
#Timestep축 값 20에 대한 정규화
a = Dense(TIME_STEPS, activation='softmax')(a) #(None,32,20):
# 다시 되돌림
a_probs = Permute((2, 1))(a) #(None,20,32)
#두 값 곱함:(None,20,32)
#Timestep 어디에 attention할지 $\mathit{dense가\ 학습}$
output_attention_mul = merge([inputs, a_probs], mode='mul')
$\underline{영어-일어\ 번역}$
$\mathit{먼저\ encoder-decoder\ 구조\ 만듬}$
# (None,20) -> (None,20,64): 20자 영단어를 64차원 임베딩
encoder = Embedding(54, 64, input_length=20, mask_zero=True)(encoder_input)
# 매 Timestep마다 출력(64개)
encoder = LSTM(64, return_sequences=True, unroll=True)(encoder)
#맨 마지막 timestep 값(None, 64)
encoder_last = encoder[:,-1,:]
# (None,20) -> (None,20,64) #20자 일단어를 64차원 임베딩
decoder = Embedding(89, 64, input_length=20, mask_zero=True)(decoder_input)
# encoder 출력 (None,64) 2개를 초기 state로 입력
decoder = LSTM(64, return_sequences=True, unroll=True)(decoder, initial_state=[encoder_last, encoder_last])
$\mathit{attention\ 기능\ 부가}$
###################################################
# encoder, decoder 출력은 같은 뜻이니 서로 유사해야 한다고 하면
# 영어 추출한 64개 속성과 일어추출 64 속성은 비슷해야 한다.
# -> 둘 다 2번축끼리 곱함: (None,20,64)x(None,20,64)->(None,20,20)
#
# 아래 코드 보면 decoder가 앞, encoder가 뒤 이므로 출력 Tensor는 (None,20,20)이고
# 1번축 20개는 decoder timestep, 2번축 20개는 encoder timestep이면서 pdf로 정규화.
# 1번축 $i$번째 step입력에 대응되는 encoder 20개 입력간 유사성을 pdf로 표현한다.
attention = dot([decoder, encoder], axes=[2, 2])
# (None,20,20) 속성 2번축 20개 값 정규화
attention = Activation('softmax', name='attention')(attention)
# 이는 encoder 출력 중 어디에 집중해 주어야 하는지를 모델링
# attention=(None,20,20) 2번축 x encoder=(None,20,64) 1번축
# -> (None, 20,64)
# encoder timestep에 대한 prob.
context = dot([attention, encoder], axes=[2,1])
#
#
# attention된 encoder features + decoder features 결합
# encoder 집중화 출력(context정보)과 decoder출력을 묶음
# (None,20,64)+(None,20,64) -> (None,20,128)
decoder_combined_context = concatenate([context, decoder])
# Has another weight + tanh layer as described in equation (5) of the paper
# 128 -> 64 -> 89: 3층 분류기
output = TimeDistributed(Dense(64, activation="tanh"))(decoder_combined_context)
output = TimeDistributed(Dense(89, activation="softmax"))(output)
# 모델
model = Model(inputs=[encoder_input, decoder_input], outputs=[output])
model.compile(optimizer='adam', loss='binary_crossentropy')
$\cdot$앞에서는 input를 dense에 넣어 input 어디에 attention할지를 dense가 학습
$\cdot$여기서는 dense 대신 decoder 사용. 즉, decoder출력 만드는 RNN 후반부가 attention 학습
$\cdot$영어->일어 번역으로 encoder에 영어입력, decoder에 일어 입력이다.
$\cdot$일어입력 20 timestep 어떤 순간 특징 64개는 영어 20 timestep 각 순간 특징(64개)와 유사성 체크.
(ex.) 일어 5 step째 입력과 영어 0~19 step별 유사성: decoder X encoder이므로 (None,5,:)에 저장.
일어 7 step째 입력과 영어 0~19 step별 유사성: (None,7,:)에 저장.
2017년 12월 18일 월요일
RL Summary
RL 학습할 net(RNN or DNN)이 있다고 가정하자. net 출력은 $prob$ (부류별) 값으로, action 부류별 분포가 혼합된 multi-nomial $prob$이다. Monte Carlo 샘플링으로 부류정보와 $prob$ 얻고, 부류 정보(action)는 제어 대상 system에 가해서 reward 얻는다.
reward 값으로부터 학습할 net loss를 구성하면,
$loss = -\sum( \log{p_i} * (r_i-baseline) )$
이다. $r$은 최신값에 가중된(그리고 정규화된) 보상 값이다. 또,
$baseline = \begin{cases}
0, reinforce(정규화\ 시^{각주1})\\
Moving\ average\ of\ r_i, reinforce(정규화\ 않을\ 시)\\
V, Actor\ Critic(V는\ 가치망\ 출력)\\
\end{cases}$
이다. RL이 적용된 사례를 보면 다음과 같다.
(예 1) Cartpole 문제 상태 입력은 state 요소간 상관성 없음 (요소간 독립적). 따라서 RL net은 rnn대신 dnn 사용
(예 2) NAS 경우, RL net 출력을 이용하여 구성하는 reward 시스템(DNN Archtecture)은 전후 상관성(Layer 연결로 이전 값이 다음 값에 영향 줌) 존재. RL net은 RNN을 사용하며, LSTMCell 출력을 다음 셀 입력으로 넣는 과정으로 구성.
(예 3) ENAS 경우
RNN 출력값 샘플링 -> 샘플링 다수(여러 DNN 사례 생성) -> 여러 DNN 구성 -> 최적 오차 net 선택 -> 선택 net 오래 학습 -> reward -> RNN 학습.
ENAS 출력은 2255/3355/4455/5555/6655이다.
2255는 2,2,5,5개 출력을 가지는 LSTMCell 4개: 2(DNN Micro-Cell 두 개 입력 중 어디 선택할지 onehot vec 표현), 5(연산자 5개 중 어떤 선택할지).
LSTMCell 출력은 [(None,32),(None,32),(None,32)] 3개 요소, 첫번째는 reshape((None,1,32)으로) 해서 다음 LSTMCell 입력으로 사용하고 상단부 dense넷 입력으로도 사용.
나머지 2개는 다음 LSTMCell 용 state 입력으로 사용(cell, hidden).
2255 네 개 중 마지막 출력은 3355 네 개 셀 첫 입력으로 사용.
3355는 3,3,5,5개 출력을 가지는 LSTM셀 4개: 3(세개 입력중 어디 선택할지), 5( " )
...
(각주1) 정규화는 저장된 보상값 $r$ 리스트 평균을 구해 빼고 분산을 나눈다.
reward 값으로부터 학습할 net loss를 구성하면,
$loss = -\sum( \log{p_i} * (r_i-baseline) )$
이다. $r$은 최신값에 가중된(그리고 정규화된) 보상 값이다. 또,
$baseline = \begin{cases}
0, reinforce(정규화\ 시^{각주1})\\
Moving\ average\ of\ r_i, reinforce(정규화\ 않을\ 시)\\
V, Actor\ Critic(V는\ 가치망\ 출력)\\
\end{cases}$
이다. RL이 적용된 사례를 보면 다음과 같다.
(예 1) Cartpole 문제 상태 입력은 state 요소간 상관성 없음 (요소간 독립적). 따라서 RL net은 rnn대신 dnn 사용
(예 2) NAS 경우, RL net 출력을 이용하여 구성하는 reward 시스템(DNN Archtecture)은 전후 상관성(Layer 연결로 이전 값이 다음 값에 영향 줌) 존재. RL net은 RNN을 사용하며, LSTMCell 출력을 다음 셀 입력으로 넣는 과정으로 구성.
(예 3) ENAS 경우
RNN 출력값 샘플링 -> 샘플링 다수(여러 DNN 사례 생성) -> 여러 DNN 구성 -> 최적 오차 net 선택 -> 선택 net 오래 학습 -> reward -> RNN 학습.
ENAS 출력은 2255/3355/4455/5555/6655이다.
2255는 2,2,5,5개 출력을 가지는 LSTMCell 4개: 2(DNN Micro-Cell 두 개 입력 중 어디 선택할지 onehot vec 표현), 5(연산자 5개 중 어떤 선택할지).
LSTMCell 출력은 [(None,32),(None,32),(None,32)] 3개 요소, 첫번째는 reshape((None,1,32)으로) 해서 다음 LSTMCell 입력으로 사용하고 상단부 dense넷 입력으로도 사용.
나머지 2개는 다음 LSTMCell 용 state 입력으로 사용(cell, hidden).
2255 네 개 중 마지막 출력은 3355 네 개 셀 첫 입력으로 사용.
3355는 3,3,5,5개 출력을 가지는 LSTM셀 4개: 3(세개 입력중 어디 선택할지), 5( " )
...
(각주1) 정규화는 저장된 보상값 $r$ 리스트 평균을 구해 빼고 분산을 나눈다.
2017년 11월 2일 목요일
Actor-Critic
상태 $s$를 받아 action $a$를 출력하는 신경망(deep neural network, 인자 $\theta$로 표현)이 하나 있다.
$p(a|s; \theta)$
여기서 $p$는 파라메터 $\theta$로 표현되는 망의 출력 값이고, 상태 $s$를 입력받아 계산된 action 확률값이다.
만일 action 라벨이 있다면 교사학습이 되고 cross-entropy식은
$loss = -\log {p(a|s)*y}$
이다. $loss$를 줄이도록 학습을 진행하면 된다. 이 때 $p$는 prediction값이고 $y$는 교사값이다.
그런데 강화학습(RL)에서는 입력 $s$에 대해 어떤 action이 유리한지를 표현하는 $y$가 직접 주어지지 않는다.
강화학습에서 망의 학습 방법을 살펴 보자.
$p(a|s; \theta)$에 임의 상태 $s$를 입력하여 얻은 action 중에서 하나($a_s$라 하자)를 택한다.
이 값을 제어 대상인 환경 $env$에 작용시켜 응답을 얻는다. 이 응답을 미래보상의 근사치 계산을 위해 이용한다.
($p(a|s)$는 정책(policy)이라 부른다. 주어진 상태에서 어떤 행동을 택할지에 대해 각각 행동에 분배한 확률이다.)
환경 $env$에 $a_s$를 가하면,
$s', r, d, = env.step(a_s)$
이고 출력은 다음상태 $s'$, 즉각보상 $r$ 등이다.
만일 우리가 큐함수 $Q(s,a)^{각주1}$를 가지고 있다면 현재 상태 $s$에 대해 어떤 action이 좋은지 Q값에서 직접 얻을 수 있다. 그러나 $Q(s,a)$는 최적 미래 보상을 나타내는 일종의 매직함수이므로 직접 구하기 어렵다.
Q를 구하기 어렵기 때문에 근사화 하기 위해 가치망 $V$를 이용한다. $V(s)$로 각 스텝(state)에서 얼마나 행동이 좋은지 판단한다.
따라서 최적 미래 보상(reward)인 교사치 $y$는
$y = Q(s,a) = r + V(s')$
이고, 이 식이 Bellman 방정식이다.
(DQN에서는 $V(s')$ 대신에 max $Q(s',:)$를 이용했었고 $r$+max $Q(s',:)$를 best action으로 사용하였다.)
이상에서 $p(a|s; \theta)$는 정책망(policy net)이고 $V(s)$는 가치망(value net)이다.
정리하면, 정책 근사는 정책망 $p(a|s; \theta)$로 하였고, Q함수를 표현하기 위해 망이 하나 더 필요한데 이를 위해 가치망이 사용된다. 가치망은 정책 근사망인 $p$를 평가한다.
따라서, 이를 actor-critic이라고 부른다. actor는 정책 발전의 역할, critic은 정책 평가의 역할을 맡는다. 2개 망 동시 학습이 필요하다. 정책망의 경우 교사치
$loss = -\log {p(a_s|s; \theta)*[y-V(s)]}$
를 gradient descent로 학습하면 된다. 수렴은 policy gradient에 기반하며 다음을 참고한다. $y$에서 $V(s)$를 뻼은 학습 시 variance를 줄인다.
여기서 $p(a_s|s)$는 정책망 $\theta$에 $s$를 입력하여 출력으로 나온 여러 action 중에서 $a_s$에 대응하는 확률 값이다.
가치망의 학습은
$loss=(y-V(s))^2$
을 직접 줄이도록 진행된다.
$p(a|s; \theta)$
여기서 $p$는 파라메터 $\theta$로 표현되는 망의 출력 값이고, 상태 $s$를 입력받아 계산된 action 확률값이다.
만일 action 라벨이 있다면 교사학습이 되고 cross-entropy식은
$loss = -\log {p(a|s)*y}$
이다. $loss$를 줄이도록 학습을 진행하면 된다. 이 때 $p$는 prediction값이고 $y$는 교사값이다.
그런데 강화학습(RL)에서는 입력 $s$에 대해 어떤 action이 유리한지를 표현하는 $y$가 직접 주어지지 않는다.
강화학습에서 망의 학습 방법을 살펴 보자.
$p(a|s; \theta)$에 임의 상태 $s$를 입력하여 얻은 action 중에서 하나($a_s$라 하자)를 택한다.
이 값을 제어 대상인 환경 $env$에 작용시켜 응답을 얻는다. 이 응답을 미래보상의 근사치 계산을 위해 이용한다.
($p(a|s)$는 정책(policy)이라 부른다. 주어진 상태에서 어떤 행동을 택할지에 대해 각각 행동에 분배한 확률이다.)
환경 $env$에 $a_s$를 가하면,
$s', r, d, = env.step(a_s)$
이고 출력은 다음상태 $s'$, 즉각보상 $r$ 등이다.
만일 우리가 큐함수 $Q(s,a)^{각주1}$를 가지고 있다면 현재 상태 $s$에 대해 어떤 action이 좋은지 Q값에서 직접 얻을 수 있다. 그러나 $Q(s,a)$는 최적 미래 보상을 나타내는 일종의 매직함수이므로 직접 구하기 어렵다.
Q를 구하기 어렵기 때문에 근사화 하기 위해 가치망 $V$를 이용한다. $V(s)$로 각 스텝(state)에서 얼마나 행동이 좋은지 판단한다.
따라서 최적 미래 보상(reward)인 교사치 $y$는
$y = Q(s,a) = r + V(s')$
이고, 이 식이 Bellman 방정식이다.
(DQN에서는 $V(s')$ 대신에 max $Q(s',:)$를 이용했었고 $r$+max $Q(s',:)$를 best action으로 사용하였다.)
이상에서 $p(a|s; \theta)$는 정책망(policy net)이고 $V(s)$는 가치망(value net)이다.
정리하면, 정책 근사는 정책망 $p(a|s; \theta)$로 하였고, Q함수를 표현하기 위해 망이 하나 더 필요한데 이를 위해 가치망이 사용된다. 가치망은 정책 근사망인 $p$를 평가한다.
따라서, 이를 actor-critic이라고 부른다. actor는 정책 발전의 역할, critic은 정책 평가의 역할을 맡는다. 2개 망 동시 학습이 필요하다. 정책망의 경우 교사치
$loss = -\log {p(a_s|s; \theta)*[y-V(s)]}$
를 gradient descent로 학습하면 된다. 수렴은 policy gradient에 기반하며 다음을 참고한다. $y$에서 $V(s)$를 뻼은 학습 시 variance를 줄인다.
여기서 $p(a_s|s)$는 정책망 $\theta$에 $s$를 입력하여 출력으로 나온 여러 action 중에서 $a_s$에 대응하는 확률 값이다.
가치망의 학습은
$loss=(y-V(s))^2$
을 직접 줄이도록 진행된다.
참고 문헌
[1] Naver D2
[2] DennyBritz github
(각주 1) $Q(s,a)$ 함수는 Quality 함수라 하고, 상태 $s$에 대해 어떤 action $a$를 선택할지를 미리 Lookup table로써 만들어 놓은 것이다. $s$나 $a$ 공간을 이산화 했을 때, 개수가 몇 개 안되면 생성 가능 하지만 상태공간이 커지면 만들기 어려워 진다.
[1] Naver D2
[2] DennyBritz github
(각주 1) $Q(s,a)$ 함수는 Quality 함수라 하고, 상태 $s$에 대해 어떤 action $a$를 선택할지를 미리 Lookup table로써 만들어 놓은 것이다. $s$나 $a$ 공간을 이산화 했을 때, 개수가 몇 개 안되면 생성 가능 하지만 상태공간이 커지면 만들기 어려워 진다.
2017년 10월 19일 목요일
DQN
DQN(Deep Q-Network)은 딥 신경망(DNN)을 이용하는 강화학습(Reinforcement Learning)의 일종이다.
환경 $env$를 제어하는 강화학습에서 action $a$에 대한 확률을 결정하는 Q(Quality) 함수는 $Q(s,a)$로 주어진다. 상태 $s$에 대해 적절한 행동 $a$를 결정하는 정책이 들어 있다.
적절하다는 것은 주어진 환경 $env$의 현재 상태 $s$에서 action $a$를 선택했을 때 다음 단계에서 끝 단계 작업(episode) 종결 시까지 얻을 수 있는 보상 합의 최대값을 줄 수 있다는 것이다. 이런 Q함수는 이상적이지만 실제로 존재할 수 없는 일종의 매직 함수이다.
DNN은 $Q(s,a)$ 함수를 근사한다. Q는 주어진 상태 $s$를 입력 받아 여러 액션 중 하나의 $a$를 줄 수 있어야 한다. Q를 근사하는 DNN은 입력 $s$를 취해 여러 $a$에 대한 확률값 출력을 제공 한다.
매직 함수인 Q를 실제 계산하기 위해서는 현 상태 s에서 작업 종결 끝까지 반복 수행하면서 단계별 보상을 더해서 구한다. 그러나 이는 불가능하므로, 근사적으로 구하는 방법을 취한다.
이 과정은 다음과 같다.
현 상태 $s$에서 제어 대상 환경 $env$에 어떤 action을 가하고, 어떤 reward가 발생하는지 본다. 이 reward를 이용하여 Q를 갱신하고, 변경된 상태를 다시 갱신된 Q에 넣어 추출한 $a$를 $env$에 가하고 어떤 reward가 발생하는지를 살펴보고 Q를 또 갱신한다. 이러한 과정을 수없이 반복하다보면 초기에는 매직 Q와 멀었던 Q 함수가 점점 이상적인 Q에 가까와 지게 된다.
정리를 해보면 DQN의 요소에는
1. $Q(s,a)$를 표현하는 DNN이 있고
2. 액션 $a$를 가해 상태를 $s$에서 $s'$로 바꿀 환경 $env$가 존재한다.
환경 $env$는 현재 상태 $s$에서 액션 $a$를 가할 경우, 상태를 $s'$로 바꾸고, 보상 값을 리턴한다.
$s', r, d = env.step(a)$
의 형태인데, $a$를 입력으로 받아 $s$는 $s'$가 되고, 보상 $r$과 현재 episode 종결여부 $d$를 리턴한다.
통상 DNN의 학습을 위해서는 predict와 label이 필요하며 두 값의 차이가 loss이고 DNN은 loss를 최소화 하도록 내부 파라메터들을 갱신하게 된다.
predict와 label을 정의하기 위해 $env$에 가해지는 한 단계만의 액션을 생각해 보자.
현 단계 $Q(s,a)$를 표현하는 DNN이 있다. 먼저 $env$를 한 단계 전진 시키기 위해서는 $env$에 가할 $a$가 필요하다.
(1) $a$를 구하기 위해 현 상태 $s$를 DNN에 입력하여 DNN이 주는 최적의 $a$를 택한다. 이 $a$는 갱신전 DNN(즉, Q)이 주는 $a$이다.
(2) $a$를 $env$에 가해 $s', r, d$를 얻는다. 이 때, 새로 생성된 $s'$를 이용한다. DNN에 넣어 새로운 $Q(s', :)$를 만들어 낼 수 있다.
벨만 방정식 (Bellman equation)은 갱신된 Q값이 근사적으로 다음과 같음을 보여준다.
$Q(s,a) = r + max Q(s', :)$
갱신된 Q값은 $env$에 $a$를 가해 얻은 보상 $r$에다 새 상태 $s'$에 대한 Q값 중 최대값의 합으로 주어진다.
여기까지 계산하면 이전의 Q와 갱신된 Q가 얻어진다.
predict는 현재 Q(즉 현재의 DNN)에서 $s$를 넣어 나오는 $a$를 취하고, label은 Bellman식을 통해 계산된 값을 취한다.
그런데, Bellman식은 초기 Q에 $a$를 가해 만든 새로운 Q값이므로 해당되는 그 $a$의 값에 대해서만 갱신된 값이다.
즉, $a$의 액션 공간이 0~2까지로 3개라고 하면 초기 $Q(s)=DNN(s)=a[0:3]$이고, $env$에 가해준 $a$가 $a[1]$이었다면,
label역할을 하는 갱신 $a$는 3개 값 중, $a[0], a[2]$는 같고, $a[1]$만 달라진,
{ $a[0],\ r+maxQ(s', :),\ a[2]$ }이다.
따라서
predict = {$a[0], a[1], a[2]$}
label = {$a[0], r+maxQ(s', :), a[2]$}
이다.
환경 $env$를 제어하는 강화학습에서 action $a$에 대한 확률을 결정하는 Q(Quality) 함수는 $Q(s,a)$로 주어진다. 상태 $s$에 대해 적절한 행동 $a$를 결정하는 정책이 들어 있다.
적절하다는 것은 주어진 환경 $env$의 현재 상태 $s$에서 action $a$를 선택했을 때 다음 단계에서 끝 단계 작업(episode) 종결 시까지 얻을 수 있는 보상 합의 최대값을 줄 수 있다는 것이다. 이런 Q함수는 이상적이지만 실제로 존재할 수 없는 일종의 매직 함수이다.
DNN은 $Q(s,a)$ 함수를 근사한다. Q는 주어진 상태 $s$를 입력 받아 여러 액션 중 하나의 $a$를 줄 수 있어야 한다. Q를 근사하는 DNN은 입력 $s$를 취해 여러 $a$에 대한 확률값 출력을 제공 한다.
매직 함수인 Q를 실제 계산하기 위해서는 현 상태 s에서 작업 종결 끝까지 반복 수행하면서 단계별 보상을 더해서 구한다. 그러나 이는 불가능하므로, 근사적으로 구하는 방법을 취한다.
이 과정은 다음과 같다.
현 상태 $s$에서 제어 대상 환경 $env$에 어떤 action을 가하고, 어떤 reward가 발생하는지 본다. 이 reward를 이용하여 Q를 갱신하고, 변경된 상태를 다시 갱신된 Q에 넣어 추출한 $a$를 $env$에 가하고 어떤 reward가 발생하는지를 살펴보고 Q를 또 갱신한다. 이러한 과정을 수없이 반복하다보면 초기에는 매직 Q와 멀었던 Q 함수가 점점 이상적인 Q에 가까와 지게 된다.
정리를 해보면 DQN의 요소에는
1. $Q(s,a)$를 표현하는 DNN이 있고
2. 액션 $a$를 가해 상태를 $s$에서 $s'$로 바꿀 환경 $env$가 존재한다.
환경 $env$는 현재 상태 $s$에서 액션 $a$를 가할 경우, 상태를 $s'$로 바꾸고, 보상 값을 리턴한다.
$s', r, d = env.step(a)$
의 형태인데, $a$를 입력으로 받아 $s$는 $s'$가 되고, 보상 $r$과 현재 episode 종결여부 $d$를 리턴한다.
통상 DNN의 학습을 위해서는 predict와 label이 필요하며 두 값의 차이가 loss이고 DNN은 loss를 최소화 하도록 내부 파라메터들을 갱신하게 된다.
predict와 label을 정의하기 위해 $env$에 가해지는 한 단계만의 액션을 생각해 보자.
현 단계 $Q(s,a)$를 표현하는 DNN이 있다. 먼저 $env$를 한 단계 전진 시키기 위해서는 $env$에 가할 $a$가 필요하다.
(1) $a$를 구하기 위해 현 상태 $s$를 DNN에 입력하여 DNN이 주는 최적의 $a$를 택한다. 이 $a$는 갱신전 DNN(즉, Q)이 주는 $a$이다.
(2) $a$를 $env$에 가해 $s', r, d$를 얻는다. 이 때, 새로 생성된 $s'$를 이용한다. DNN에 넣어 새로운 $Q(s', :)$를 만들어 낼 수 있다.
벨만 방정식 (Bellman equation)은 갱신된 Q값이 근사적으로 다음과 같음을 보여준다.
$Q(s,a) = r + max Q(s', :)$
갱신된 Q값은 $env$에 $a$를 가해 얻은 보상 $r$에다 새 상태 $s'$에 대한 Q값 중 최대값의 합으로 주어진다.
여기까지 계산하면 이전의 Q와 갱신된 Q가 얻어진다.
predict는 현재 Q(즉 현재의 DNN)에서 $s$를 넣어 나오는 $a$를 취하고, label은 Bellman식을 통해 계산된 값을 취한다.
그런데, Bellman식은 초기 Q에 $a$를 가해 만든 새로운 Q값이므로 해당되는 그 $a$의 값에 대해서만 갱신된 값이다.
즉, $a$의 액션 공간이 0~2까지로 3개라고 하면 초기 $Q(s)=DNN(s)=a[0:3]$이고, $env$에 가해준 $a$가 $a[1]$이었다면,
label역할을 하는 갱신 $a$는 3개 값 중, $a[0], a[2]$는 같고, $a[1]$만 달라진,
{ $a[0],\ r+maxQ(s', :),\ a[2]$ }이다.
따라서
predict = {$a[0], a[1], a[2]$}
label = {$a[0], r+maxQ(s', :), a[2]$}
이다.
피드 구독하기:
글 (Atom)