이번 글에서는 힙(heap)이라는 자료구조와 힙 정렬(Heap Sort) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드 구현은 이곳을 참고하였습니다. 그럼 시작하겠습니다.

Heap

힙은 큰 키(우선 순위)에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조입니다. 힙은 한 노드(node)가 최대 두 개의 자식노드(child node)를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전이진트리(complete binary tree)를 기본으로 합니다.

힙 속성(heap property)은 다음 두 가지입니다.

• heap order property : 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다(최대 힙, Max heap). 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다(최소 힙, Min heap).
• heap shape property : 모양은 완전이진트리이다. 즉 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다. (이진트리에 대해서 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다)

다음 그림이 바로 최대 힙 속성을 만족하는 자료구조입니다.

Heap vs Binary Search Tree

아래 그림은 이진탐색트리(Binary Search Tree)를 나타내고 있습니다. 힙과 이진탐색트리 모두 이진트리라는 점에서 공통점을 가지만 노드값이 다소 다르게 구성돼 있는 점을 확인할 수 있습니다. 힙은 각 노드의 값이 자식노드보다 큰 반면, 이진탐색트리는 왼쪽 자식노드가 제일 작고 부모노드가 그 다음 크며 오른쪽 자식노드가 가장 큰 값을 가집니다. 힙은 우선순위(키) 정렬에, 이진탐색트리는 탐색에 강점을 지닌 자료구조라고 합니다.

이진탐색트리와 관련해 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

Heap을 Array로 표현

힙은 완전이진트리(complete binary tree) 성질을 만족하기 때문에 다음처럼 1차원 배열(array)로도 표현이 가능합니다.

이를 파이썬 코드로 구현하면 다음과 같습니다. 파이썬은 데이터의 인덱스가 0부터 시작합니다. 예컨대 인덱스가 2인 노드(10)의 왼쪽 자식노드(9)의 인덱스는 5, 오른쪽 자식노드(3)의 인덱스는 6이 됩니다. 어떤 노드의 인덱스를 index, 왼쪽 자식노드의 인덱스를 left_index, 오른쪽 자식노드의 인덱스를 right_index로 선언하면 다음과 같은 관계를 지닙니다.

left_index = 2 * index + 1
right_index = 2 * index + 2

하지만 글에서의 설명은 그림처럼 구성된 인덱스 기준으로 하겠습니다.

heapify

주어진 자료구조에서 힙 성질을 만족하도록 하는 연산을 heapify라고 합니다. 다음 예시와 같습니다.

먼저 4를 보겠습니다. 4는 왼쪽 자식노드 14보다 작으므로 힙 성질을 만족하지 않습니다(4는 오른쪽 자식노드 7보다도 작지만 알고리즘 구현상 왼쪽 자식노드 우선 적용). 4와 14 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 합니다.

4는 새로운 왼쪽 자식노드 2보다는 크지만 오른쪽 자식노드 8보다는 작습니다. 힙 성질을 만족하지 않습니다. 4와 8 위치를 바꿉니다. 위치 변경 이후에도 힙 성질이 유지되는지 살펴야 하지만 더 이상 살필 자식노드가 없으므로 연산 수행을 종료합니다.

heapify를 파이썬으로 구현한 코드는 다음과 같습니다.

def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index
    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index
    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)

heapify의 계산복잡성은 최악의 경우 루트노드에서 잎새노드까지 값을 비교해야 하므로 트리의 높이($h=\log_2{n}$)에 의존적입니다. 값을 비교하거나 바꾸는 연산은 $O(1)$이므로 결과적으로 heapify의 계산복잡성은 $O(\log{n})$이 됩니다.

insert

힙은 자료구조의 일종이므로 삽입 연산이 가능해야 합니다. 힙 속성 가운데 shape 속성을 만족하려면 새로운 노드는 아래 그림과 같이 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽에 들어가야 할 겁니다.

예를 들어보겠습니다. 아래와 같은 힙 구조에서 18을 삽입한다고 가정해 보겠습니다. 그러면 마지막 레벨의 비어있는 공간 가운데 가장 왼쪽, 즉 5의 오른쪽 자식노드 위치에 처음 들어가게 됩니다.

하지만 18이 새로 삽입되면서 힙 속성이 깨졌습니다. heapify를 통해 맞춰 주어야 합니다. 우선 18을 부모노드인 5와 비교합니다. 위치를 바꿔 줍니다. 이번엔 16과 비교해 위치를 바꿔 줍니다. 이같이 삽입 연산을 할 때 heapify는 아래에서 위로 heapify를 해줍니다.

삽입 연산의 heapify 과정에서는 형제 노드에 대해선 값을 비교할 필요가 없습니다. 예컨대 상단 중앙그림의 마지막 레벨인 3, 18을 봅시다. 이미 힙 속성을 유지하고 있는 완전이진트리이기 때문에 기존 노드 3은 자신의 부모노드 5보다는 작거나 같다는 게 보장되어 있습니다. 따라서 18을 hepify할 때 부모노드인 5와만 비교해도 원하는 결과를 낼 수 있습니다.

그러면 삽입 연산의 계산복잡성은 얼마일까요? 삽입하는 데 드는 연산 $O(1)$, 해당 노드를 heapfy하는 데 $O(\log{n})$이 드므로, 전체적으로는 $O(\log{n})$가 됩니다.

delete

이번엔 삭제 연산을 살펴보겠습니다. 다음과 같습니다.

우리가 지우고 싶은 값이 위 힙 구조에서 18이라고 가정해 봅시다. 그러면 마지막 레벨의 마지막 값, 즉 힙을 배열로 표현했을 때 가장 마지막 값인 5를 삭제된 요소의 위치에 옮깁니다. 이후 이 5가 잎새노드에 다다르기까지 위에서 아래로 heapify를 수행합니다.

5는 왼쪽 자식노드인 16보다 큽니다. 힙 성질을 만족하지 않습니다. 둘의 위치를 바꿔줍니다. 새로운 위치의 5는 왼쪽 자식노드인 3보다 크고, 오른쪽 자식노드는 없습니다. 힙 성질을 만족합니다. 둘의 위치를 바꾸지 않고, heapify를 종료합니다.

그러면 삭제 연산의 계산복잡성은 얼마일까요? 삭제하는 데 드는 연산 $O(1)$, 배열의 마지막 노드를 삭제 위치로 옮기는 연산 $O(1)$, 해당 노드를 heapfy하는 데 드는 연산 $O(\log{n})$, 이렇게 해서 전체적으로 $O(\log{n})$가 됩니다.

build heap

이번에는 임의의 숫자들을 최대 힙으로 구성해 보도록 하겠습니다. 이러한 일련의 연산 과정을 build heap이라고 합니다. 예를 들어 다음과 같은 리스트가 주어졌다고 칩시다.

12, 30, 6, 7, 4, 13, 8, 11, 50, 24, 2, 5, 10

위 숫자들을 가지고 bulid heap을 하는 가장 단순한 방법은 비어있는 힙에 위 요소들을 차례로 insert 연산을 수행해 힙을 만들어가는 과정이 될 겁니다. 새로 삽입해야 할 노드 수가 $n$개라면 노드 하나의 insert 연산을 $n$번 반복 수행해야 합니다. 그런데 마지막 요소를 삽입할 때 힙을 이미 구성하고 있는 노드의 수는 $n-1$개일 것이므로 insert 연산의 계산복잡성은 $O(\log{n})$입니다. 따라서 이 방식의 계산복잡성은 결과적으로 $O(n\log{n})$이 됩니다.

이보다 더 줄일 수는 없을까요? 방법이 하나 있습니다. 다음 그림을 보겠습니다. 위 리스트를 가지고 완전이진트리 형태로 쭉 나열하면 하단 좌측그림과 같습니다. 여기에서 잎새노드를 가지지 않는 노드(=배열의 개수를 2로 나눈 몫을 인덱스로 하는 노드)부터 차례대로 heapify를 수행해주는 것입니다. 하단 좌측그림에서 보는 것처럼 8, 13, 4, 7 순서대로 위에서 아래로 heapify를 수행합니다.

우선 8부터 보겠습니다. 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 8에 대한 heapify를 종료합니다.

이번엔 13입니다. 13은 자식노드인 5, 10보다 크므로 힙 성질을 이미 만족하고 있습니다. 13에 대한 heapify를 종료합니다.

다음은 4입니다. 4는 왼쪽 자식노드인 24보다 작으므로 힙 성질을 만족하지 않습니다. 4와 24 위치를 바꿔 줍니다. 새로운 위치의 4는 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 4에 대한 heapify를 종료합니다.

다음은 7입니다. 7은 왼쪽 자식노드인 11보다 크고, 오른쪽 자식노드인 50보다 크므로 힙 성질을 만족하지 않습니다. 7과 50 위치를 바꿔 줍니다. 새로운 위치의 7은 자식노드가 없으므로 heapify를 수행할 대상이 없습니다. 7에 대한 heapify를 종료합니다. 이를 수행한 결과가 상단 우측 그림과 같습니다.

이번엔 6과 30을 차례대로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.

마지막으로 루트노드를 대상으로 heapify를 수행합니다. 이를 수행한 결과는 하단 우측 그림과 같습니다.

이같은 방식의 계산복잡성을 따져 보겠습니다. 1개 노드를 heapify하는 데 필요한 계산량은 $O(\log{n})$이고, $n/2$개 노드에 대해 heapify를 수행해야 하므로 전체적으로는 $O(n\log{n})$입니다. 하지만 조금 더 생각해 볼 필요가 있습니다. 아래 그림을 보겠습니다. 모든 레벨의 모든 노드가 꽉 차 있는 정이진트리(full binary tree)에서 오른쪽 맽 끝에 해당합니다.

노드 안의 숫자들은 노드 수가 $n$개인 이진트리를 배열로 표현했을 때 인덱스를 가리킵니다. 인덱스가 $n$인 데이터는 정이진트리의 오른쪽 끝 잎새노드가 되는 셈이지요. 잎새노드에 해당하는 레벨을 $d$라고 했을 때 레벨이 $d$인 노드 수는 $n/2$개입니다. 왜냐하면 레벨 $d-1$의 오른쪽 끝 노드의 인덱스가 $n/2$이기 때문입니다. 레벨이 $d-1$인 노드의 수는 전체 노드($n$)에서 레벨 $d$에 해당하는 노드 수($n/2$)와 레벨 $d-2$에 해당하는 노드 수($n/4$)를 뺀 $n/4$개가 됩니다.

build heap의 계산복잡성은 수행 대상의 노드가 전체 트리에서 차지하는 높이, 그리고 수행 대상 노드 수에 비례합니다. 레벨 $d-1$에 해당하는 노드는 그 높이가 1(=잎새노드까지의 엣지 수)입니다. 마찬가지로 레벨 $d-2$는 2, $d-3$은 3이 되겠지요. 지금까지 말씀드린 내용을 종합해 build heap의 계산복잡성을 대략적으로 나타내면 다음과 같습니다.

[\begin{align} 0\cdot \frac { n }{ { 2 }^{ 1 } } &+1\cdot \frac { n }{ { 2 }^{ 2 } } +2\cdot \frac { n }{ { 2 }^{ 3 } } +3\cdot \frac { n }{ { 2 }^{ 4 } } +…\ &=\frac { n }{ 4 } \cdot \left( 1+2\cdot \frac { 1 }{ 2 } +3\cdot \frac { 1 }{ 4 } +… \right) \ &=\frac { n }{ 4 } \cdot c=O\left( n \right) \end{align}]

지금 설명드린 방식이 비어있는 힙에 차례로 insert 연산을 수행해 힙을 만들어가는 방식보다 더 효율적임을 알 수 있습니다.

Heap sort

자, 드디어 이제 힙 정렬에 대해 살펴볼 시간입니다. 힙 정렬을 수행하기 위해서는 주어진 데이터를 가지고 우선 최대 힙을 구성해야 합니다. 우리에게 주어진 데이터가 다음과 같다고 칩시다.

unsorted = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]

Heapify의 시작점은 데이터 개수(10)의 절반에 해당하는 다섯번째 노드입니다. “각 노드의 값은 자식노드보다 크거나 같다”를 만족해야 힙 성질을 가진다고 할 수 있습니다. 다섯번째 노드(7)는 자식노드의 값(1)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.

다음은 네번째 노드를 볼 차례입니다. 네번째 노드(14)는 왼쪽 자식노드(2), 오른쪽 자식노드(8)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다. 세번째 노드 차례입니다. 세번째 노드(10)은 왼쪽 자식노드(9), 오른쪽 자식노드(3)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.

두번째 노드 차례입니다. 두번째 노드(4)는 왼쪽 자식노드(14)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 14의 위치를 바꿔 줍니다.

unsorted = [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]

4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 4는 오른쪽 자식노드(8)보다 작습니다. 힙 성질을 만족하지 않으므로 다음처럼 4와 8의 위치를 바꿔 줍니다.

unsorted = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

4의 위치가 위의 그림처럼 바뀌었으니 4의 자식노드들을 좀 더 살펴보아야 합니다. 그런데 4의 자식노드는 존재하지 않습니다. 이로써 두번째 노드에 대한 연산을 종료합니다. 마지막으로 첫번째 노드 차례입니다. 첫번째 노드(16)는 왼쪽 자식노드(14), 오른쪽 자식노드(10)보다 크므로 힙 성질을 만족합니다. 따라서 더 이상의 연산이 필요 없습니다.

이로써 최대 힙을 구성하는 데 성공했습니다. 최대 힙을 구성하게 되면 unsorted의 첫번째 요소(16)가 전체 요소 가운데 최댓값이 됩니다.

Heap Sort 파이썬 구현

힙 정렬의 수행 방법은 다음과 같습니다.

1. 주어진 원소들로 최대 힙을 구성합니다.
2. 최대 힙의 루트노드(=현재 배열의 첫번째 요소=최댓값)와 말단노드(=현재 배열의 마지막 요소)를 교환해 줍니다.
3. 새 루트노드에 대해 최대 힙을 구성합니다.
4. 원소의 개수만큼 2와 3을 반복 수행합니다.

이를 파이썬 코드로 구현하면 다음과 같습니다.

def heap_sort(unsorted):
    n = len(unsorted)
    # BUILD-MAX-HEAP (A) : 위의 1단계
    # 인덱스 : (n을 2로 나눈 몫-1)~0
    # 최초 힙 구성시 배열의 중간부터 시작하면 
    # 이진트리 성질에 의해 모든 요소값을 
    # 서로 한번씩 비교할 수 있게 됨 : O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
    # Recurrent (B) : 2~4단계
    # 한번 힙이 구성되면 개별 노드는
    # 최악의 경우에도 트리의 높이(logn)
    # 만큼의 자리 이동을 하게 됨
    # 이런 노드들이 n개 있으므로 : O(nlogn)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted

A. BUILD-MAX-HEAP의 인덱스($i$)에 따른 정렬 과정은 다음과 같습니다. (단 여기에서 $i$는 파이썬 인덱스 기준)

B. Recurrent 부분의 인덱스에 따른 정렬 과정은 다음과 같습니다.

Heap sort의 계산복잡성

그러면 힙 정렬의 계산복잡성을 따져보도록 하겠습니다. 우선 최초로 최대 힙을 만드는 A의 계산복잡성은 이미 살펴보았듯 $O(n)$입니다. 이번엔 힙이 구성된 상태에서 각 노드에 대해 heapify를 수행하는 B를 살펴보겠습니다. 말단 노드(최댓값)가 루트 노드에 올라오기까지 트리의 높이(데이터 수가 $n$개일 때 $h=\log_2n$)만큼 자리 이동을 해야 합니다. 이렇게 heapify를 해야 하는 노드들이 $n$개가 있으므로 B의 계산복잡성은 $O(n\log{n})$이 됩니다.

따라서 힙 정렬의 계산복잡성은 A와 B를 합친 $O(n)+O(n\log{n})$이며 결과적으로 $O(n\log{n})$이 됩니다.

제 개인적 정리 용도로 업로드하는 글입니다.

이번 글에서는 그래디언트 디센트(Gradient Descent)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 강필성 교수님 강의와 하용호 님의 자료를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

산등성이 내려가기

우리는 오차가 적은 모델을 만들고 싶습니다. 이 오차는 미리 구해졌다고 칩시다. 딥러닝 모델의 오차가 무엇인지에 관련해서는 이곳을 참고하시기 바랍니다. 어쨌든 오차를 줄이는 과정, 즉 학습과정은 높은 산등성이에서 산 아래로 이동할 때 두 눈을 가리고 한발한발 내딛어 더 낮은 쪽으로 한걸음씩 내려가는 것에 비유할 수 있을 것입니다.

이 때 중요한 것은 현재 위치 $x_{old}$에서 내려가야 할 방향과 보폭입니다. 우리가 만들고 있는 모델을 $f$, 방향을 그래디언트(gradient) $f’$, 보폭을 학습률(learning rate) $α$(0<$α$<1)라고 두면, 그래디언트 디센트에 의해 정해진 다음 위치 $x_{new}$는 다음과 같이 정의됩니다.

[{ x }{ new }={ x }{ old }-\alpha f^{ \prime }\left( {x}_{old} \right)]

$f(x_{new})$는 $f(x_{old})$보다 항상 작습니다. 테일러 급수 전개(Taylor Series Expansion)를 활용해 유도해보겠습니다. $f(x+Δx)$는 테일러 급수 전개에 의해 다음과 같이 무한합으로 나타낼 수 있습니다.

[f\left( x+\Delta x \right) =f\left( x \right) +\frac { f^{ ‘ }\left( x \right) }{ 1! } \Delta x+\frac { f^{ ‘’ }\left( x \right) }{ 2! } { \Delta x }^{ 2 }+…]

$x_{new}=x_{old}-αf’(x_{old})$이므로 양변에 $f$를 적용하면 $f(x_{new})=f(x_{old}-αf’(x_{old}))$이 성립합니다. 여기에서 $x_{old}-αf’(x_{old})$를 위 테일러 급수 전개식의 $x+Δx$라고 보면 다음 또한 성립합니다.

[\begin{align} f\left( { x }_{ new } \right) &=f\left[ { x }_{ old }-\alpha f^{ ‘ }\left( x \right) \right] \&=f\left( { x }_{ old } \right) +\frac { f^{ ‘ }\left( { x }_{ old } \right) }{ 1! } \left[ -\alpha f^{ ‘ }\left( { x }_{ old } \right) \right] +\frac { f^{ ‘’ }\left( { x }_{ old } \right) }{ 2! } { \left[ -\alpha f^{ ‘ }\left( { x }_{ old } \right) \right] }^{ 2 }+…\ &\cong f\left( { x }_{ old } \right) -\alpha { \left[ f^{ ‘ }\left( { x }_{ old } \right) \right] }^{ 2 }<f\left( { x }_{ old } \right) \end{align}]

위 식의 마지막 줄은 테일러 급수 전개식을 2차항까지만 써서 근사한 결과입니다. 그런데 $f’(x_{old})^2$의 값은 항상 양수이므로 결론적으로 $f(x_{new})<f(x_{old})$가 성립합니다. 요컨대 그래디언트 디센트 기법을 취해 오차를 줄여나갈 수 있다는 이야기입니다.

오차를 역전파하기

딥러닝 학습 과정에서는 모델이 틀린 정도(오차)를 모델 전체의 파라메터에 역전파(backpropagation)하게 됩니다. 미분하고 곱하고 더하고를 역방향으로 반복하며 파라메터를 업데이트하는 구조입니다. 오차를 역전파하는 과정에 대해서는 이곳을 참고하시면 좋을 것 같습니다.

딥러닝 모델 파라메터 업데이트는 체인룰(chain rule)에 의해 그래디언트를 계속 곱하는 과정에서 이뤄집니다. 그런데 중간에 있는 계층의 그래디언트가 0이거나 작은 값이면 곱셈이 누적되는 과정에서 파라메터 업데이트가 잘 안되는 경우가 발생할 수 있습니다. 이를 Vanishing Gradient 문제라고 합니다.

Vanishing Gradient 문제는 맨 뒤에 있는 학생까지 줄을 세우려는 교장 선생님에 비유할 수 있습니다. (정말 명쾌한 비유라고 생각됩니다, 하용호님 감사합니다)

Vanishing Gradient 문제를 해결하기 위해 활성함수(activation function)를 바꾸는 방안이 제시됐습니다. 매우 큰 양수이거나 작은 음수일 때 그래디언트가 사그라드는 시그모이드 대신 ReLU 등을 사용하는 것입니다. 활성함수와 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

파라메터 최적 업데이트

그래디언트 디센트 방법은 현재 위치 $x_{old}$에서 학습데이터 전체를 넣어 전체 오차를 계산한 뒤 나온 그래디언트를 구해 이 그래디언트의 역방향으로 $x_{old}$를 업데이트하는 방식입니다. 하지만 학습데이터의 양이 기본적으로 많은 만큼 계산량이 커질 수밖에 없습니다. 이 때문에 학습데이터의 일부만 활용해 그래디언트를 구하는 Stochastic Gradient Descent(SGD) 같은 다양한 업데이트 기법들이 제안되었습니다. 하용호 님 표현에 따르면 ‘느린 완벽보다는 불완전하나마 빠른 방식’을 택한 것이라 볼 수 있겠습니다. 그 개념을 도식화하면 다음과 같습니다.

파라메터 업데이트 기법으로는 SGD를 비롯해 Momentum, RMSProp, Adam 등 다양한 방식이 제안되었습니다. 이 가운데 Adam의 성능이 좋은 것으로 알려져 있다고 합니다. 파라메터 업데이트 기법 간 관계도(하용호님 자료)는 다음과 같습니다. 파라메터 업데이트 기법과 관련 자세한 내용은 이곳을 참고하시기 바랍니다.

이번 글에서는 딥러닝 모델의 손실함수에 대해 살펴보도록 하겠습니다. 이 글은 Ian Goodfellow 등이 집필한 Deep Learning Book과 위키피디아, 그리고 하용호 님의 자료를 참고해 제 나름대로 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

Why negative log-likelihood?

딥러닝 모델의 손실함수로 음의 로그우도(negative log-likelihood)가 쓰입니다. 어떤 이유에서일까요?

확률론적 접근

딥러닝 모델을 학습시키기 위해 최대우도추정(Maximum Likelihood Estimation) 기법을 씁니다. 주어진 데이터만으로 미지의 최적 모델 파라메터 $θ$를 찾아야 합니다. 입력값 $X$와 파라메터 $θ$가 주어졌을 때 정답 $Y$가 나타날 확률, 즉 우도 $P(Y$|$X;θ)$를 최대화하는 $θ$가 바로 우리가 찾고 싶은 결과라고 보면 되겠습니다.

그런데 학습데이터 각각의 우도를 스케일해도 전체 argmax의 결과는 바뀌지 않으므로 ‘우도의 곱을 최대’로 만드는 $θ$와 ‘로그우도의 기대값, 즉 $Σ_xP(y$|$x)\log{P(y}$|$x;θ)$를 최대’로 하는 $θ$는 같습니다. 이와 관련해 Deep Learning Book 128페이지에는 다음과 같이 설명돼 있습니다.

The argmax does not change when we rescale the cost function, we can divide by the total number of data to obtain a version of the criterion that is expressed as an expectation with respect to the empirical distribution $P_{data}$ defined by the training data.

다범주 분류를 학습하는 딥러닝 모델의 경우 말단에 다음과 같이 소프트맥스 함수가 적용됩니다. ($f(x)$는 소프트맥스 계층의 입력값)

위 식에서 $f$는 범주 수만큼의 차원을 갖는 벡터로써 unnormalized log probabilities에 해당합니다. 소프트맥스 함수가 취해짐으로써 그 요소의 합이 1이 됩니다. 정답 인덱스에 해당하는 $f$의 요소값을 높인다는 말은 우도를 높인다(=입력값 $X$를 넣었을 때 $Y$ 관련 스코어를 높인다)는 의미로 해석할 수 있습니다.

정보이론의 접근

두 확률분포 $p$와 $q$ 사이의 차이를 계산하는 데에는 크로스 엔트로피(cross entropy)라는 함수가 사용됩니다. 식은 $-Σp(x)\log{q(x)}$입니다. 여기에서 $p$를 우리가 가진 데이터의 분포 $P(Y$|$X)$, $q$를 모델이 예측한 결과의 분포 $P(Y$|$X;θ)$로 두겠습니다. 이렇게 되면 크로스 엔트로피는 파라메터 $θ$ 하에서의 음의 로그우도의 기대값이라고 해석할 수 있습니다. 따라서 $-Σ_xP(y$|$x)\log{P(y}$|$x;θ)$를 최소화하는 $θ$가 바로 우리가 찾고 싶은 모델이 됩니다.

요컨대 우도의 곱이 최대인 모델을 찾는 것은 로그우도의 기대값이 최대인 모델을 찾는 것과 같으며, 이는 또한 학습데이터의 분포(distribution)와 모델이 예측한 결과의 분포 사이의 차이, 즉 크로스 엔트로피를 최소화하는 것과 동치입니다. 이 때문에 음의 로그우도가 딥러닝 모델의 손실함수가 되는 것입니다. 정보이론과 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

크로스엔트로피 계산 예시

음의 로그우도를 계산하는 예시와 관련 크로스 엔트로피로 설명해 보겠습니다. 우선 딥러닝 모델의 입력값으로 쓰이는 관측치는 이산변수(discrete variable)에 해당하므로 크로스 엔트로피 $H(P,Q)$의 식을 다시 쓰면 다음과 같습니다.

[H\left( P,Q \right) =-\sum _{ x }^{ }{ P({ x })\log { Q({ x }) } }]

예컨대 범주가 2개이고 정답 레이블이 $[1,0]$인 관측치 $x$가 있다고 칩시다. $P$는 우리가 가지고 있는 데이터의 분포를 나타내므로 첫번째 범주일 확률이 1, 두번째 범주일 확률은 0이라고 해석할 수 있습니다. $Q$는 $P$에 근사하도록 만들고 싶은, 딥러닝 학습 대상 분포(모델이 예측하는 분포)입니다. 그런데 모델 학습이 잘 안돼서 $Q$가 $[0,1]^T$로 나왔다고 하면 loss는 다음과 같이 무한대로 치솟게 됩니다.

[-P(x)\log { Q(x) } =-\begin{bmatrix} 1 & 0 \end{bmatrix}\begin{bmatrix} \log { 0 } \ \log { 1 } \end{bmatrix}=-\left( -\infty +0 \right) =\infty]

이번엔 학습이 잘 돼서 모델이 정답과 일치하는 $[1,0]$을 예측했다고 하면 loss는 다음과 같이 0이 됩니다.

[-P(x)\log { Q(x) } =-\begin{bmatrix} 1 & 0 \end{bmatrix}\begin{bmatrix} \log { 1 } \ \log { 0 } \end{bmatrix}=-\left( 0+0 \right) =0]

단 여기에서 $0\log{0}$은 0으로 취급합니다.

negative log-likelihood 장점

손실함수로 음의 로그우도을 쓸 경우 몇 가지 이점이 생긴다고 합니다. 우선 우리가 만드려는 모델에 다양한 확률분포를 가정할 수 있게 돼 유연하게 대응할 수 있게 됩니다. 음의 로그우도로 딥러닝 모델의 손실을 정의하면 이는 곧 두 확률분포 사이의 차이를 재는 함수인 크로스 엔트로피가 되며, 크로스 엔트로피는 비교 대상 확률분포의 종류를 특정하지 않기 때문입니다. 이와 관련 Deep Learning Book 129페이지는 이렇게 서술돼 있습니다.

Any loss consisting of a negative log-likelihood is a cross entropy between the empirical distribution defined by the training set and the probability distribution defined by model.

예컨대 우리가 만들고 싶은 모델을 가우시안 분포로 전제한다면, 크로스 엔트로피 최소화는 우리가 가진 데이터의 분포와 모델의 가우시안 분포 사이의 차이를 최소화한다는 의미입니다. 특히 가우시안 분포를 가정할 때 크로스 엔트로피의 최소화는 평균제곱오차(Mean Squared Error)의 최소화와 본질적으로 동일합니다. 이와 관련해 이곳을 참고하시면 좋을 것 같습니다.

아울러 모델을 베르누이 분포로 가정한다면 우리가 가진 데이터의 분포와 모델의 베르누이 분포 간 차이가 최소화하는 방향으로 학습이 이뤄집니다. 이는 다항분포 또한 마찬가지입니다.

한편 딥러닝 모델의 최종 출력을 어떤 숫자 하나(예컨대 영화 관객 수)로 둘 경우 우리가 구축하려는 모델이 정규분포라고 가정하는 것과 깊은 관련을 맺고 있습니다. 최종 출력이 O, X로 이뤄진 이진변수(binary variable)일 경우 모델을 베르누이 분포로 가정하는 것과 사실상 유사합니다. 다범주 분류를 하는 딥러닝 모델은 다항분포를 가정하는 것과 비슷합니다.

위 세 종류 모델의 최종 output node는 각각 Linear unit, Sigmoid unit, Softmax unit이 되며, output node의 출력 분포와 우리가 가진 데이터의 분포 사이의 차이가 곧 크로스 엔트로피가 됩니다. 이 차이만큼을 loss로 보고 이 loss에 대한 그래디언트를 구해 이를 역전파하는 과정이 딥러닝의 학습이 되겠습니다. 바꿔 말하면 각각의 확률분포에 맞는 손실을 따로 정의할 필요가 없이 음의 로그우도만 써도 되고, output node의 종류만 바꾸면 세 개의 확률분포에 대응할 수 있게 된다는 이야기입니다. 매우 편리한 점이죠.

세 종류 간 구분은 다음 그림과 같습니다(출처 : 하용호 님의 자료) 다시 말씀드리지만 셋 모두 손실함수로 음의 로그우도, 즉 크로스 엔트로피를 쓰면 됩니다.

크로스 엔트로피를 쓰면 딥러닝 역전파시 그래디언트가 죽는 문제를 어느 정도 해결할 수 있고, 그래디언트를 구하는 과정 역시 비교적 간단하다고 합니다. 우리가 구축하는 모델을 다항분포라고 두고, 최종 output node는 3차원짜리 벡터를 입력으로 받는 소프트맥스, loss는 크로스 엔트로피인 경우를 그림으로 도식화하면 다음과 같습니다.

Softmax-with-Loss 노드는 $a$를 입력으로 받아서 소프트맥스를 취해 확률값으로 만든 뒤 이를 바탕으로 크로스 엔트로피 Loss $L$을 출력합니다. 반대로 역전파하는 그래디언트는 $y_k-t_k$가 됩니다. 예컨대 정답이 $t_3$이라면 역전파되는 그래디언트는 각각 $y_1, y_2, y_3-1$로 간단하게 구할 수 있습니다. 뿐만 아니라 정답이 아닌 노드의 손실에 대한 그래디언트는 소프트맥스 확률값이고, 정답 레이블에 해당하는 노드의 그래디언트는 여기에서 1을 빼준 값이기 때문에 그래디언트가 완전히 0으로 되는 경우는 많지 않으리라고 기대할 수 있습니다.

이번 글에서는 정보이론(Information Theory)의 기본 개념들을 살펴보도록 하겠습니다. 이 글은 Ian Goodfellow 등이 집필한 Deep Learning Book과 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

개요

정보이론은 시그널에 존재하는 정보의 양을 측정하는 응용수학의 한 갈래입니다. 정보이론은 무선전송을 통해 알파벳으로 된 메세지를 보내려는 연구에서 시작되었습니다. 이 때 정보이론은 최적의 코드를 디자인하고, 메세지의 기대 길이(expected length)를 계산하는 데 도움이 됩니다. 머신러닝에서는 해당 확률분포의 특성을 알아내거나 확률분포 간 유사성을 정량화하는 데 쓰입니다.

정보이론의 핵심 아이디어는 잘 일어나지 않는 사건(unlikely event)은 자주 발생하는 사건보다 정보량이 많다(informative)는 것입니다. 예컨대 ‘아침에 해가 뜬다’는 메세지로 보낼 필요가 없을 정도로 정보 가치가 없습니다. 그러나 ‘오늘 아침에 일식이 있었다’는 메세지는 정보량 측면에서 매우 중요한 사건입니다. 이 아이디어를 공식화해서 표현하면 다음과 같습니다.

• 자주 발생하는 사건은 낮은 정보량을 가진다. 발생이 보장된 사건은 그 내용에 상관없이 전혀 정보가 없다는 걸 뜻한다.
• 덜 자주 발생하는 사건은 더 높은 정보량을 가진다.
• 독립사건(independent event)은 추가적인 정보량(additive information)을 가진다. 예컨대 동전을 던져 앞면이 두번 나오는 사건에 대한 정보량은 동전을 던져 앞면이 한번 나오는 정보량의 두 배이다.

섀넌 엔트로피

위 세 가지 조건을 만족하는 함수는 발생 가능한 사건이나 메세지의 확률분포에 음의 로그를 취한 수식입니다. 확률변수 $X$의 값이 $x$인 사건의 정보량은 아래와 같습니다.

[I\left( x \right) =-\log { P(x) }]

예컨대 동전을 던져 앞면이 나오는 사건과 주사위를 던져 눈이 1이 나오는 사건, 두 개의 정보량을 비교해보겠습니다. 전자의 정보량은 $-\log_{2}{0.5}=1$, 후자는 $-\log_{2}{1/6}=2.5849$가 됩니다. 다시 말해 주사위 눈이 1이 나올 사건은 동전의 앞면이 나오는 사건보다 덜 자주 발생하므로 더 높은 정보량을 갖는다는 의미입니다.

위 식에서 밑이 2인 경우 정보량의 단위를 섀년(shannon) 또는 비트(bit)라고 합니다. 자연상수(exp)를 밑으로 할 경우 내트(nat)라고 부릅니다. 머신러닝에서는 대개 밑을 자연상수로 사용합니다. 섀넌 엔트로피(Shannon entropy)는 모든 사건 정보량의 기대값을 뜻합니다. 전체 사건의 확률분포의 불확실성의 양을 나타낼 때 씁니다. 어떤 확률분포 $P$에 대한 섀넌 엔트로피 $H(P)$는 다음과 같습니다.

[H\left( P \right) =H\left( x\right) ={ E }{ X\sim P }\left[ I\left( x \right) \right] ={ E }{ X\sim P }\left[ -\log { P(x) } \right]]

앞면, 뒷면이 나올 확률이 동일한, 공평한 동전을 1번 던지면 섀년 엔트로피는 발생 가능한 모든 결과의 가지 수(2)에 밑이 2인 로그를 취한 것(=1비트)과 같습니다. 이를 식으로 풀어 쓰면 다음과 같습니다.

[\begin{align} H\left( P \right)= H\left( x \right) &=-\sum _{ x }^{ }{ P({ x })\log { P({ x }) } } \ &=-\left( 0.5\times \log _{ 2 }{ 0.5 } +0.5\times \log _{ 2 }{ 0.5 } \right) \ &=-\log _{ 2 }{ 0.5 } \ &=-(-1) \end{align}]

마찬가지로 2개 동전을 던지면 4가지 결과가 발생하고 섀년 엔트로피는 2비트가 됩니다. 다시 말해 서로 독립인 두 확률변수의 섀넌 엔트로피는 각 확률변수의 엔트로피 합과 같게 됩니다. 이를 그림으로 나타내면 다음과 같습니다.

사건의 분포가 결정적(deterministic)이라면 해당 확률분포의 불확실성 정도를 나타내는 엔트로피는 낮아집니다. 반대로 분포가 균등적(uniform)일 수록 엔트로피는 높아집니다. 동전 던지기 예를 다시 들면, 절대로 뒷면이 나오지 않는 동전을 던지는 건 아무런 정보를 가지지 않습니다. 항상 앞면이 나와서 불확실성이 전혀 없기 때문입니다. 하지만 공평한 동전을 던질 경우 엔트로피는 가장 높습니다. 결과값을 예상하기가 가장 어렵기 때문입니다.

위 그래프는 동전을 한번 던졌을 때 섀넌 엔트로피의 변화를 나타낸 그림입니다. $x$축은 동전의 공정한 정도(1, 즉 앞면이 나올 확률)를 나타냅니다. 0.5라면 앞면, 뒷면이 나올 확률이 각각 동일한 공평한 동전이라는 뜻입니다. $y$축은 섀넌 엔트로피를 가리킵니다. 여기서는 공평한 동전을 사용할 경우가 가장 큰 엔트로피(1비트)를 나타내고 있습니다. 동전 던지기 결과값을 어딘가에 전송할 경우 공평한 동전을 쓸 때 최대 1비트가 필요함을 알 수 있습니다.

KL Divergence

쿨백-라이블러 발산(Kullback-Leibler divergence, KLD)은 두 확률분포의 차이를 계산하는 데 사용하는 함수입니다. 딥러닝 모델을 만들 때 예로 들면 우리가 가지고 있는 데이터의 분포 $P(x)$와 모델이 추정한 데이터의 분포 $Q(x)$ 간에 차이를 KLD를 활용해 구할 수 있습니다. KLD의 식은 다음과 같이 정의됩니다.

$P$와 $Q$가 동일한 확률분포일 경우 KLD는 정의에 따라 그 값이 0이 됩니다. 하지만 KLD는 비대칭(not symmetric)으로 $P$와 $Q$ 위치가 뒤바뀌면 KLD 값도 달라집니다. 따라서 KLD는 거리함수로는 사용할 수 없습니다.

KLD와 크로스 엔트로피

이산변수(discrete variable)에 대한 크로스 엔트로피(cross entropy)는 다음과 같이 정의됩니다. 보시다시피 $H(P,Q)$는 $P$의 엔트로피인 $H(P)$와 유사한 꼴이나 로그 바깥에 곱해지는 확률이 $P(x)$이고, 로그 안에 들어가는 것이 $Q(x)$인 것을 확인할 수 있습니다. 엔트로피는 엔트로피이되 두 확률분포가 교차로 곱해진다는 의미로 크로스(cross) 엔트로피라는 이름이 붙은 것 같습니다.

[H\left( P,Q \right) ={ E }_{ X\sim P }\left[ -\log { Q(x) } \right] =-\sum _{ x }^{ }{ P({ x })\log { Q({ x }) } }]

이산변수에 대한 KLD를 풀어쓰면 다음과 같습니다.

[\begin{align} { D }_{ KL }\left( P||Q \right) =&-\sum _{ x }^{ }{ P({ x })\log { \left( \frac { Q\left( x \right) }{ P(x) } \right) } } \=&-\sum _{ x }^{ }{ P({ x })\left{ \log { Q(x) } -\log { P(x) } \right} } \=&-\sum _{ x }^{ }{ \left{ P({ x })\log { Q(x) } -P(x)\log { P(x) } \right} } \=&-\sum _{ x }^{ }{ P({ x })\log { Q(x) } } +\sum _{ x }^{ }{ P(x)\log { P(x) } } \ =&H(P,Q)-H(P) \end{align}]

이를 크로스 엔트로피를 기준으로 다시 정리하면 아래와 같습니다.

위 식을 보면 KLD는 딥러닝 모델의 손실함수(loss function)로 자주 쓰이는 크로스 엔트로피와 깊은 관련을 맺고 있다는 걸 알 수 있습니다. 딥러닝 모델을 학습할 때 크로스 엔트로피를 최소화하는 방향으로 파라메터(가중치)들을 업데이트 합니다. 위 식에서 $P(x)$를 우리가 가지고 있는 데이터의 분포, $Q(x)$를 모델이 추정한 데이터의 분포라고 본다면, 크로스 엔트로피 $H(P,Q)$를 최소화한다는 것은 KLD를 최소화하는 것과 그 의미가 완전히 같습니다(equivalent). 왜냐하면 데이터 분포 $P(x)$는 학습 과정에서 바뀌지 않기 때문입니다. 결과적으로 크로스 엔트로피 최소화는 우리가 가지고 있는 데이터의 분포 $P(x)$와 모델이 추정한 데이터의 분포 $Q(x)$ 간에 차이를 최소화한다는 정도로 이해하면 좋을 것 같습니다.