2014년 8월 27일 수요일

신경망 회로에서 역전파를 통한 학습


신경망 회로에서 역전파를 통한 학습

Learning through back-propagation in 3-layers neural network

 layer가 3개인 신경망 회로(이하 NN)는 input, hidden, output layer로 구성됩니다. 학습 단계는 output layer에서 원하는 출력을 얻기 위해 hidden layer가 활성화 되도록 학습하는 것이 목적입니다.

 예를 들면, 어떤 물체가 연필인지 아닌지를 구분하는 NN을 만들고자 할 경우에 loss function은

\(loss = 연필 - output\)

이 되어야 합니다.

 convex optimization 문제로 만들기 위해 \(loss = (연필 - output)^2\)으로 놓고 미분하면 \(\frac{\delta loss}{\delta output} = 2(연필 - output)\)이 됩니다.

 그러면 NN이 원하는 출력 값과 얼마나 다른 값을 출력 하는지를 알 수 있습니다. 출력값의 차이가 크다면 input->hidden->output layer로 이르는 뉴런들이 올바르게 활성화될 수 있도록, 오차만큼 역전파(Back-propagation)을 통해서 weight값을 고쳐줍니다. 이 과정의 반복을 학습이라 부릅니다. 그림을 보면 이해가 쉽습니다.

  • Feed-forward 과정입니다. 입력 뉴런과 weight의 값들의 합이 다음 layer의 입력으로 들어가고 activation function의 임계치에 따라서 활성화되는지 그렇지 않은지가 결정됩니다. activation function은 과거에는 모두 sigmoid function을 사용하였으나 최근에는 경향이 좀 바뀌었습니다. 추후에 언급할 기회가 있을 거라고 생각합니다.
  • Backward propagation의 과정입니다. loss function의 값은 곧바로 weight를 학습하는데 사용할 수가 없기 때문에, 다시 말하면 출력값이 원하는 값과 다르게 나오는데 영향을 미친 뉴런이 어떤 것이고 얼마 만큼의 가중치를 가졌는지 알 수 없기 때문에 미분치를 역으로 전파시킵니다. 그림에서 \(\delta\)는 이 미분치를 의미하고 chain rule로 입력 layer까지 전파됩니다. 이제 weight를 갱신하고 다시 이 과정을 반복합니다. 이때, \(\eta\)는 learning rate으로 부르는데 학습의 시간을 결정합니다. 크게 설정하면 빠르게 학습되지만 over-shoot이 생겨서 오차 범위에 정착하기가 힘들기 때문에 수렴하는 속도를 보고 변경하는 것이 일반적입니다.











원본 이미지: http://galaxy.agh.edu.pl/~vlsi/AI/backp_t_en/backprop.html

 신경망의 기본 개념은 인간의 뉴런과 시냅스를 모사한다는 거창한 말에 비해서 이론적으로 어렵거나 구현이 까다롭지 않습니다.(물론 layer의 수가 적을 때의 이야기 입니다. 영상에 적용하는 convolutional neural network은 이보다 엄청나게 많은 수의 뉴런과 weight가 존재하기 때문에 구현 자체가 어려운 경우가 많습니다.)

 학습은 방법보다는 어떤 응응 분야에 적용할 것 인지를 염두에 두어야 합니다. 왜냐하면 학습 데이터에 너무나 잘 들어맞는(over-fitting) NN을 가지고 일반적인 데이터에 적용하면 분류 혹은 검출률이 낮을 수 있기 때문입니다. 반대로 적당히 학습되어있는 경우(under-fitting)엔 반대의 경향이 나타날 수 있습니다. 그래서 학습할 목적에 따라 오검출율(FAR-False Alarm Rate)이 얼만큼 허용 되는지 판단해야 할 수 있습니다.

 C# 예제를 게시한 MSDN Magazine이 있어서 이 곳을 소개합니다. 참고하시면 좋을 것 같습니다.

 http://msdn.microsoft.com/en-us/magazine/jj658979.aspx

구글 캠퍼스 서울 세계에서 3번째로 문 연다.

 새 정부 들어서 창조 경제와 관련된 이슈가 많은데, 정치적인 목적이 아닌 실제로 창업자들을 위한 프로그램이 지원되었으면 좋겠습니다.

 http://www.zdnet.co.kr/news/news_view.asp?artice_id=20140827104637

2014년 8월 26일 화요일

MATLAB으로 구현한 최소자승법 예제

lsq1

MATLAB으로 구현한 최소자승법 예제

% Least square minization demo
% 2014. 8. 26
% refopen.blogspot.com

추정하고자 하는 모수 참 값

a = 3.5;
b = 105.3;

모수의 참값으로 그려본 직선

x = 0:0.1:100;
y = a*x + b;

plot(x, y,'LineWidth', 3);
hold on;

측정되는 가상 데이터 생성

x_perturbed = x + randn(1, 1001)*10;
y_perturbed = y + randn(1, 1001)*10;

plot(x_perturbed, y_perturbed, 'MarkerSize', 2, 'Marker', '*', 'Color', 'r', 'LineStyle', 'none');
hold on;

최소자승법으로 모수를 추정

[param_est] = [x_perturbed' ones(1001, 1)] \ y_perturbed';

y_est = param_est(1)*x + param_est(2);
plot(x, y_est, 'Color','g' , 'LineWidth', 3);
legend('true', 'measured data', 'Least Square Estimation');
param_est =

    3.1268
  123.7713

2014년 8월 25일 월요일

최적화 문제(Optimization problem)

최적화 문제

Optimization problem

 '최적화' 라는 말이 갖는 의미가 참 모호한 것 같다. 성능을 최적화 한다는 의미로 받아 들이면 탑재된 플랫폼에 맞도록 속도나 메모리 사용량을 줄인다는 의미로 생각할 수도 있다.



 그러나 수학적 의미의 최적화 문제라 하면 주어진 제한 조건을 만족하는 최대, 최소 해를 찾는 문제로 정의된다. 제한 조건은 때로는 출력값의 범위를 제한할 수도 있고, 입력값의 범위를 제한할 수도 있으므로 입력과 출력 집합에 대한 최적의 연결(함수)을 찾는 문제라고 생각할 수도 있다.

 로봇, 컴퓨터 비전, 기계 학습과 밀접한 관련을 가지고 있으므로 자세히 알고 있으면 매우 편리하다. 아래에 든 예시 말고도, 생각할 수 있는 거의 모든 문제는 목적 함수와 제한 조건을 설정할 수 있다면, 최적화 문제로 접근이 가능하다.

  • Laser Range sensor 기반의 지도 작성 및 위치 인식에 사용되는 ICP(Iterative Closest Point)
  • 다수의 카메라의 특징점의 위치를 알고 있는 경우, Bundle Adjustment를 통해 최초의 값으로부터 최적의 카메라 위치, 특징점의 3차원 위치를 구하기 위해 LM(Levenberg-Marquartd) 알고리즘을 이용
  • Neural Network의 Weight를 학습하기 위해 Loss function의 값을 역 전파(Back-propagation)하여 최적의 Weight값을 찾는데 이용

 Least square minimization(최소자승법) 문제를 통해서 접근하는 것이 최적화 문제에 입문하는데 효과적인 방법이 될 것이다.

SLAM(Simultaneous localization and mapping) - Simulation

SLAM 예제

 애초에는 SLAM 예제를 만들어 볼 생각이었으나, 이미 너무 잘 만들어진 시뮬레이터가 있어서 이것을 소개하는 것으로 갈음하고자 합니다.

 Austraila 의 연구자 Tim Bailey의 SLAM simulations software를 소개합니다.

 구성된 내용은
  • EKF-SLAM version 1, 2
  • FASTSLAM 1.0, FASTSLAM 2.0
  • UKF-SLAM
 입니다.


Tim bailey의 SLAM simulations EKF-SLAM

 SLAM을 연구하고자 입문하시는 분들에게 큰 도움이 되실 거라고 생각합니다. 아래 링크를 참조하세요.



2014년 8월 22일 금요일

SLAM(Simultaneous localization and mapping)과 칼만 필터 두 번째


SLAM(Simultaneous localization and mapping) - Kalman Filter second

동시적 위치추정 및 지도작성과 칼만 필터 두 번째

 이제 우리는 SLAM(Simultaneous localization and mapping)과 칼만 필터를 통해서 2차원 에서 운동하는 등속 모델의 물체에 대한 추적을 할 수 있게 되었다. 그런데 궁금한 것이 있다. 관측 행렬 \(\mathbf{H}=\left[\begin{array}{cccc}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\end{array}\right]\)에서 알 수 있는 것처럼 측정할 수 있는 값은 위치 뿐이고, 속도에 대한 정보를 입력해 준 적은 없는데, 상태 벡터를 관찰해보면 속도에 대한 값이 생성되고 있다. 왜 그럴까? 공분산 행렬 \(\mathbf{P}\)을 살펴보면 예측 과정에서는 행렬의 대각 성분, 다시 말하면 각 위치와 각 속도 스스로의 항에 더해지지만, 갱신하는 과정에서 대각 성분이 아닌  곳에 연관성(correlation)이 발생하기 때문이다. 그러므로 칼만 필터는 위치에 대한 정보만 입력 받아도 상태 천이 행렬로부터 적절한 속도를 갱신하도록 한다고 생각해 볼 수 있다.

 그러면 마찬가지로 입력 받지 않은 다른 측정 값에 대해서도 갱신하는 것이 가능하지 않을까? 그렇다. SLAM의 기본 개념은 측정된 값을 이용해서 측정 되지 않은 다른 값들을 갱신하는 것이다. 현재 위치에서 측정할 수 있는 랜드 마크는 센서의 시야각과 거리의 한계로 제한이 있을 수 밖에 없다. 한정된 측정값을 이용해서 다른 상태 벡터의 값들을 좀 더 신뢰할 수 있는 값으로 갱신하는 것이다.

 아래 그림을 보면, 움직이는 로봇이 측정할 수 있는 랜드 마크의 숫자가 한정적인 경우에도 하나의 상태 벡터를 포함하고 있는 상태에서는 모든 랜드 마크와 로봇의 위치에 대한 신뢰도가 향상되는 것을 볼 수 있다. 로봇과 랜드 마크의 타원은 공분산 행렬(Covariance matrix)에 비례하여 그려진 것이므로 해당 항목의 불확실성(Uncertainty)을 의미하는 것으로 생각할 수 있다.


이미지 원본: Andrew Davison의 박사 학위 논문

 이렇게 로봇의 상태와 랜드 마크의 좌표가 하나로 합쳐진(Augmented) 상태 벡터를 사용하는 방법은 관측 범위의 제약으로 한정된 관측이 수행되는 경우에 유용하지만, 태생적으로 차원의 저주(Curse of dimensionality) 문제를 갖고 있다.

 추정하고자 하는 로봇 좌표계의 차원과 특징점의 차원이 모두 하나의 상태 벡터에 포함되므로 특징점의 개수가 증가함에 따라서, 공분산 행렬 \( \mathbf{P} \)의 크기가 \( 2^d \)에 비례하여 증가하기 때문이다.

2014년 8월 21일 목요일

SLAM(Simultaneous localization and mapping)과 칼만 필터


SLAM(Simultaneous localization and mapping) - Kalman Filter

동시적 위치추정 및 지도작성과 칼만 필터

 국문으로 번역된 이름이 마음에 들지 않지만, 마땅히 다르게 번역할 방법이 없어서 기존에 사용되던 것들 중에서 차용하였습니다.

 제목에서 느낄 수 있는 것처럼 이동 로봇이 미지의 세계를 방문할 때 자신의 위치추정과 지도작성을 동시에 수행하는 것을 말한다. 동시적이라고 하면 시간의 흐름상 완전한 동시성을 의미하는 것처럼 느껴지기 때문에 사실은 일관된, 연관된 정도로 번역하는 것이 자연스럽다고 생각된다.

 칼만 필터를 이용한 이동 로봇의 SLAM에 대해서 먼저 기술하고 다음으로 다른 종류의 필터(EKF, UKF, Particle Filter)에 대해 적어볼 예정입니다.

 위치 추정과 지도 작성은 동시에 진행하는 것이 타당하다. 위치를 인식하기 위해서는 지도가 정확해야 하는데, 지도의 정확성은 위치의 정확성에 의존하기 때문이다. SLAM이 어려운 이유는 그림에서 보는 것처럼 예측할 수 없는 요소들이 많기 때문이다.


왜 SLAM은 어려운 문제인가?

 세상엔 정확한 센서는 존재하지 않기 때문에 항상 노이즈를 포함하고 있다. 정확한 센서 하나만 있었더라도 이렇게 힘들게 고민할 이유가 없었을 것이다.

 위의 그림을 조건부 확률식으로 적어보면 아래와 같다.

조건부 확률식으로 전개한 SLAM 문제

 상태 벡터 \( \mathbf{x}_{k-1} \)에서 \( \mathbf{x}_{k} \)로 이동하는 로봇이 \( \mathbf{m}_{i}, \mathbf{m}_{j}\) 랜드 마크를 관측한 값이 측정치 \( \mathbf{z}_{k,j}\) 로 입력된다. \( \mathbf{u}_k \)는 현재 로봇의 조종 명령이다.

 조건부 확률 식을 말로 풀이하면 " \( \mathbf{z}_{1:t}, \mathbf{u}_{1:t} \)가 만족 되는 경우에 즉, 최초 시점 1에서 현재 시점 \( t \)까지의 관측 값과 조종 명령이 주어질 때, 현재 위치를 의미하는 상태 벡터 \( \mathbf{x}_t \)와 지도를 의미하는 \( \mathbf{m} \)이 어떤 확률 분포를 가지는가?" 로 서술할 수 있다.

 확률은 그 합이 '1'이 되어야 하기 때문에 조건이 주어지지 않은 경우의 현재 상태와 지도에 대한 확률과 합하면 조건부 확률 값은 '1'이 된다. 위와 같은 조건부 확률 식으로 전개해 두고 나면 앞서 기술한 베이지안 추정 방법이나 마르코프 위치 인식 방법을 사용할 수 있게 되므로 매우 유리한 점이 생긴다.

 상태 천이 행렬이 선형(Linearity: Homogeneity와 superposition을 만족)인 경우에 적용할 수 있다. 선형 상태 천이를 한다는 것은 상태 천이 함수가 선형이라는 말이며 등속, 등가속 운동처럼 이후의 운동의 예측할 수 있는 경우를 말한다.


 그림에서 상태 천이 함수는 \( A \) 행렬이다. 등속 모델인 경우엔 \( \mathbf{A}=\left[\begin{array}{cccc}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{array}\right] \), 상태 벡터는 \(\mathbf{x}=\left[\begin{array}{c}x \\ y \\ \dot{x} \\ \dot{y} \end{array}\right] \) 로 설정하면 2차원 좌표에서 등속으로 운동하는 물체에 대한 칼만 필터의 추정식이 완성된다. 실제 시스템 모델이 맞도록 공정 잡음과 측정 잡음을 설정하면 된다. 

 간단하게 몇 줄의 코드 만으로도 칼만 필터는 훌륭하게 동작합니다. 아래에 2차원에서 움직이는 물체에 대한 칼만 필터 예제를 게시합니다. 
kalmandemo

칼만 필터 예제

% 2D Kalman filter example
% 2014. 8. 21
% refopen.blogspot.kr

2차원에서 움직이는 참 값 생성

true = [0:0.03:pi/2; sin(0:0.03:pi/2)];
close all;
plot(true(1, :), true(2, :), 'b*-');

파라미터 초기화

x = [0; 0; 0; 0];
A = [1 0 1 0;
    0 1 0 1;
    0 0 1 0;
    0 0 0 1];
sigmax = 0.01;
sigmay = 0.01;
sigmaxdot = 0.01;
sigmaydot = 0.01;
Q = [sigmax.^2 0 0 0;
    0 sigmay.^2 0 0;
    0 0 sigmaxdot.^2 0;
    0 0 0 sigmaydot.^2];
H = [1 0 0 0; 0 1 0 0];
R = [0.05 0;
    0 0.05];

xhatk = x;
Phatk = Q;

kfest = zeros(size(true));
measure = zeros(size(true));

예측과 갱신 반복

for n=1:size(true, 2)   %% 참 값으로 만든 횟수 만큼

    % 측정값 생성
    % 표준 편차가 0.03인 가상의 노이즈를 더한 가상의 측정값
    zk = true(:, n) + randn(2, 1)*0.03;
    measure(:, n) = zk;

    % 예측 과정
    xbark = A*xhatk;
    Pbark = A*Phatk*A' + Q;

    % 갱신 과정
    K = (Pbark*H'*(H*Pbark*H'+R)^-1);
    xhatk = xbark + K*(zk - H*xbark);
    Phatk = (eye(4) - K*H)*Pbark;

    kfest(:, n) = xhatk(1:2);

end

hold on;
plot(measure(1, :), measure(2, :), 'k*-');
plot(kfest(1, :), kfest(2, :), 'r*-');

legend('true', 'measure', 'kf est.');