<div id="readability-page-1" class="page"><div itemprop="articleBody">
 Posts Layout

<ul>
 <li><a href="https://000namc.github.io/blog/2018/12/14/note-backpropagation/">2018-12-14 : Note : Backpropagation Algorithm</a> $\leftarrow$</li>
</ul>

<hr>

이번 글에서는 BP(Backpropagation) Algorithm에 대해 정리해보도록 하겠습니다.
BP란 머신러닝 모형들중 Neural Network에서 등장하는 알고리즘입니다.
조금 더 구체적으로, 보통 머신러닝 모형은 Cost Function을 Minimize하는 방식으로 모형을 데이터에 적합을 시키는데 이때 Cost Function의
Gradient를 계산하게 됩니다. Neural Network는 그 특성상 구조가 복잡하여 해당하는 Gradient를 계산하는데 많은 계산이 필요하여
효율적인 계산이 필요하게 되고 이를 구현한것이 바로 Backpropagation Algorithm이 되겠습니다.
붙여진 이름은 알고리즘 내의
특정값들이 계산되는 방향이 뒤에서 앞쪽으로(Back) 흘러가기때문에 그렇습니다.

이 포스트를 작성하면서 Cousera의 Andrew Ng 교수님의 Machine Learning 강좌를 많이
 참고하였음을 먼저 밝힙니다. 아래 등장하는 Notation들 역시 해당 강의에서 사용하는 Notation을
 사용하였습니다. 글은 Notation, Definition을 먼저 설명하고, 메인이 되는 BP를 서술하고 이를
 증명하는 순서로 작성하였습니다.

<hr>

<ul>
 <li>Notation, Convention</li>
</ul>



Newral Network의 BP를 설명하기 위해서는 아래와같은 기호들이 필요합니다. 
충분히 기호가 많기 때문에 식을 전개할때,
특정 example을 지칭하는 $(i)$ 는 생략하도록 하였습니다.

<ul>
 <li>$n$ : number of features.</li>
 <li>$m$ : number of examples.</li>
 <li>$L$ : total number of layers in the network.</li>
 <li>$S_l$ : number of units in layer $l$ (not containing bias unit).</li>
 <li>$\theta^{(l)}_{ij}$ : parameter from $j$-th unit of $l$-th layer to $i$-th unit of $(l+1)$-th layer.</li>
 <li>$z^{(l)(i)}_x$ $(= z^{(l)}_x)$ : $x$-th unit of $l$-th layer for the $i$-th example.</li>
 <li>$a^{(l)(i)}_x$ $(= a^{(l)}_x)$ : activation of $z^{(l)(i)}_x$.</li>
 <li>$\delta^{(l)(i)}_x$ $(= \delta^{(l)}_x)$.</li>
 <li>$h_{\theta}(x)$ : the Hypothesis function of data x with the parameter $\theta$.</li>
 <li>$J(\theta)$ : the Cost function.</li>
</ul>

<img src="https://000namc.github.io/assets/images/bp_figure.png" alt="temp">

<hr>
<ul>
 <li>Definition</li>
</ul>



위에서 언급된 여러 기호들에 대하여 아래와 같이 정의함으로써 Neural Network Classifier를 설계하도록 합니다. 
여기서, activation function으로는 sigmoid function만을 고려하였습니다.



<hr>

Backpropagation Algorithm을 증명하기위해 두개의 Lemma를 활용하였습니다. 
먼저 정리와 Lemma를 서술하였고, 이후 증명을 작성하였습니다.

<ul>
 <li>Theorem(Backpropagation Algorithm)</li>
</ul>



where



<ul>
 <li>Lemma 1</li>
</ul>



<ul>
 <li>Lemma 2</li>
</ul>



<hr>

Proof of Theorem(Backpropagation Algorithm)

$l = L-1$ 일때,



$l &lt; L-1$ 일때,



<hr>
Proof of Lemma 1

$J(\theta)$의 정의로부터 계산을 해 나가면 아래와 같이 된다.



따라서,



<hr>
Proof of Lemma 2

$l$에 대한 귀납법을 이용하여 위 Lemma를 증명하도록 하자. 
우리는 간단한 계산을 통해 $l = L-1$ 일때 위 식이 성립함을 확인 할 수 있다.



따라서,



$l=p$일 때 성립함을 가정하면,



다음과 같이 $l=p-1$ 일 때 성립함을 보일 수 있다.



 </div></div>

Seong-Uk's Blog

Posts Layout
2018-12-14 : Note : Backpropagation Algorithm $\leftarrow$
이번 글에서는 BP(Backpropagation) Algorithm에 대해 정리해보도록 하겠습니다.
BP란 머신러닝 모형들중 Neural Network에서 등장하는 알고리즘입니다.
조금 더 구체적으로, 보통 머신러닝 모형은 Cost Function을 Minimize하는 방식으로 모형을 데이터에 적합을 시키는데 이때 Cost Function의
Gradient를 계산하게 됩니다. Neural Network는 그 특성상 구조가 복잡하여 해당하는 Gradient를 계산하는데 많은 계산이 필요하여
효율적인 계산이 필요하게 되고 이를 구현한것이 바로 Backpropagation Algorithm이 되겠습니다.
붙여진 이름은 알고리즘 내의
특정값들이 계산되는 방향이 뒤에서 앞쪽으로(Back) 흘러가기때문에 그렇습니다.
이 포스트를 작성하면서 Cousera의 Andrew Ng 교수님의 Machine Learning 강좌를 많이
 참고하였음을 먼저 밝힙니다. 아래 등장하는 Notation들 역시 해당 강의에서 사용하는 Notation을
 사용하였습니다. 글은 Notation, Definition을 먼저 설명하고, 메인이 되는 BP를 서술하고 이를
 증명하는 순서로 작성하였습니다.
Notation, Convention
Newral Network의 BP를 설명하기 위해서는 아래와같은 기호들이 필요합니다.
$n$ : number of features.
$m$ : number of examples.
$L$ : total number of layers in the network.
$S_l$ : number of units in layer $l$ (not containing bias unit).
$\theta^{(l)}_{ij}$ : parameter from $j$-th unit of $l$-th layer to $i$-th unit of $(l+1)$-th layer.
$z^{(l)(i)}_x$ $(= z^{(l)}_x)$ : $x$-th unit of $l$-th layer for the $i$-th example.
$a^{(l)(i)}_x$ $(= a^{(l)}_x)$ : activation of $z^{(l)(i)}_x$.
$\delta^{(l)(i)}_x$ $(= \delta^{(l)}_x)$.
$h_{\theta}(x)$ : the Hypothesis function of data x with the parameter $\theta$.
$J(\theta)$ : the Cost function.
Definition
위에서 언급된 여러 기호들에 대하여 아래와 같이 정의함으로써 Neural Network Classifier를 설계하도록 합니다.
Backpropagation Algorithm을 증명하기위해 두개의 Lemma를 활용하였습니다.
Theorem(Backpropagation Algorithm)
where
Lemma 1
Lemma 2
Proof of Theorem(Backpropagation Algorithm)
$l = L-1$ 일때,
$l < L-1$ 일때,
Proof of Lemma 1
$J(\theta)$의 정의로부터 계산을 해 나가면 아래와 같이 된다.
따라서,
Proof of Lemma 2
$l$에 대한 귀납법을 이용하여 위 Lemma를 증명하도록 하자.
따라서,
$l=p$일 때 성립함을 가정하면,
다음과 같이 $l=p-1$ 일 때 성립함을 보일 수 있다.

Note : Backpropagation Algorithm

댓글