이번 글에서는 알고리즘의 계산복잡도 함수가 재귀식(Recurrence relation) 내지 점화식 형태로 표현되는 경우를 살펴보도록 하겠습니다. 재귀식 또는 점화식이란 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)처럼 수열의 항 사이에서 성립하는 관계식을 말합니다. 이로부터 데이터 수 $n$에 대해 닫힌 형태(closed-form expression)의 정확한 계산복잡도 함수를 찾는 것이 이 글의 목표입니다. (복잡도의 기준은 알고리즘이 필요로 하는 시간과 메모리 등 자원인데 전자를 ‘시간복잡도’, 후자를 ‘공간복잡도’라 합니다) 이번 글 역시 고려대 김선욱 교수님 강의를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

재귀식 형태로 표현된 시간복잡성

알고리즘의 계산복잡도 함수가 재귀식으로 표현되는 대표적인 사례 가운데 하나가 분할-정복(divide-and-conquer) 문제입니다. 다음과 같이 풉니다. 우선 원래 문제를 부분문제로 쪼갭니다(divide). 부분 문제를 풉니다(conquer). 이를 합칩니다(merge). 원래 문제에 $n$개의 데이터가 있고, 이를 푸는 데 드는 시간복잡도를 $T(n)$이라고 할 때 $T(n)$은 다음과 같이 분해할 수 있습니다.

[T\left (n\right)=T\left (divide\right)+T\left (conquer\right)+T\left (merge\right)]

이를 합병정렬(merge sort)을 예시로 설명하겠습니다. 합병정렬 관련 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

$T(divide)$는 문제를 분할하는 데 걸리는 시간을 가리킵니다. 합병정렬을 예로 들면 원래 문제를 두 개로 나누기 위해 데이터를 반으로 자를 위치(인덱스) 하나만 고르면 되므로 $T(divide)=Θ(1)$입니다. (Big $Θ$ notation 관련해서는 이곳을 참고하시면 좋을 것 같습니다)

$T(conquer)$는 (분할한 문제의 수 * 하위문제를 푸는 데 걸리는 시간)을 의미합니다. 원래 문제를 절반씩 두 개로 나누었고, 각 하위문제는 $n/2$개의 데이터가 있으므로 $T(conquer)=2*T(n/2)$가 될 것입니다.

$T(merge)$는 하위문제를 합치는 데 걸리는 시간입니다. 합병정렬에서는 하위문제를 합치면서 정렬을 수행합니다. $n=8$일 때 다음 그림과 같습니다.

위 그림을 자세히 보면 하위 첫번째 array의 첫번째 요소(2)와 두번째 array의 첫번째 요소(1)을 비교해 sorted array의 첫번째 요소를 결정(1)합니다. 그 다음으로 첫번째 array의 첫번째 요소(2)와 두번째 array의 두번째 요소(2)를 비교해 sorted array의 두번째 요소를 결정(2)합니다. 이런 방식으로 merge를 모두 수행하는 데 총 $n=8$회의 연산을 수행하게 됩니다. 따라서 데이터 수가 $n$일 때 $T(merge)=Θ(n)$이 됩니다.

이를 바탕으로 합병정렬의 시간복잡도를 다시 쓰면 다음과 같습니다.

[T(n)=\Theta \left( 1 \right) +2\cdot T\left( \frac { n }{ 2 } \right) +\Theta \left( n \right)]

하지만 위와 같은 재귀식 형태로는 해당 알고리즘의 시간복잡도를 정확히 알기가 어렵습니다. $T(n)$을 어렵게 구했지만 내부에 $T(n/2)$가 또 있어서 꼬리에 꼬리를 물고 $n$이 1이 될 때까지 식을 길게 늘여뜨려 써야하기 때문입니다. 이를 닫힌 형태로 구해보기 위해 다음 세 가지 방법을 씁니다.

Substitution method

이 방법은 (1) 해당 알고리즘의 시간복잡도를 $n$에 대한 함수로 가정한 뒤 (2) 이를 귀납(induction)에 의해 증명하는 방식입니다. 합병정렬을 예로 들면, 시간복잡도 함수 $T(n)=2T(n/2)+Θ(n)$의 $T(n)$이 $n\log_{2}{n}+n$일 거라 우선 가정해보는 것입니다. (알고리즘 계산복잡도를 따질 때 상수항은 무시하므로 $Θ(1)$은 없는 것으로 취급)

이를 바탕으로 (2) 귀납에 의한 증명을 해보면 다음과 같습니다.

(2-1) $n=1$일 때 성립함을 보임

[1\log _{ 2 }{ 1 } +1=0+1=T(1)]

(2-2) $n$보다 작은 임의의 $k$에 대해 성립한다고 가정

[k\log _{ 2 }{ k } +k=T(k)]

(2-3) $k/2$일 때도 성립함을 보임

[\begin{align} T\left( \frac { k }{ 2 } \right) &=2T\left( \frac { k }{ 4 } \right) +\frac { k }{ 2 } \ &=2\left( \frac { k }{ 4 } \log _{ 2 }{ \frac { k }{ 4 } } +\frac { k }{ 4 } \right) +\frac { k }{ 2 } \ &=\frac { k }{ 2 } \log _{ 2 }{ \frac { k }{ 4 } } +\frac { k }{ 2 } +\frac { k }{ 2 } \ &=\frac { k }{ 2 } \left( \log _{ 2 }{ \frac { k }{ 2 } } -\log _{ 2 }{ 2 } \right) +\frac { k }{ 2 } +\frac { k }{ 2 } \ &=\frac { k }{ 2 } \log _{ 2 }{ \frac { k }{ 2 } } -\frac { k }{ 2 } +\frac { k }{ 2 } +\frac { k }{ 2 } \ &=\frac { k }{ 2 } \log _{ 2 }{ \frac { k }{ 2 } } +\frac { k }{ 2 } \end{align}]

따라서 $T(n)=n\log_{2}{n}+n=Θ(n\log{n})$입니다. 하지만 Substitution method의 첫 단추인 가정 부분을 제대로 설계하지 않으면 증명이 불가능하다는 단점이 있습니다.

Iteration method

이 방법은 점화식을 무한히 풀어 헤쳐 모두 더하는 방식으로 구합니다. $T(n)=n+4T(n/2)$을 구해보겠습니다.

[\begin{align} T\left( n \right) &=n+4T\left( \frac { n }{ 2 } \right) \ &=n+4\left( \frac { n }{ 2 } +4T\left( \frac { n }{ 4 } \right) \right) =n+4\frac { n }{ 2 } +4T\left( \frac { n }{ 4 } \right) \ &=n+4\left( \frac { n }{ 2 } +4\left( \frac { n }{ 4 } +4T\left( \frac { n }{ 8 } \right) \right) \right) =n+4\frac { n }{ 2 } +{ 4 }^{ 2 }\frac { n }{ 4 } +{ 4 }^{ 3 }T\left( \frac { n }{ 8 } \right) \ &=…\ &=n+4\frac { n }{ 2 } +{ 4 }^{ 2 }\frac { n }{ 4 } +{ 4 }^{ 3 }\frac { n }{ 8 } +…+{ 4 }^{ k }T\left( \frac { n }{ { 2 }^{ k } } \right) \end{align}]

위 식에서 $n/2^k$가 1이 될 때까지 끝까지 반복해서 더합니다. 이 때 $k$는 $\log_{2}{n}$입니다. ($2^k=n$) 그런데 여기에서 로그의 성질에 의해 $4^{\log_{2}{n}}=2^{2\log_{2}{n}}=n^{2\log_{2}{2}}=n^2$이 되므로 다음이 성립합니다.

[\begin{align} T\left( n \right) &=n+4\frac { n }{ 2 } +{ 4 }^{ 2 }\frac { n }{ 4 } +{ 4 }^{ 3 }\frac { n }{ 8 } +…+{ 4 }^{ \log _{ 2 }{ n } }T\left( 1 \right) \ &=\sum _{ i=0 }^{ \log _{ 2 }{ n } -1 }{ \left( 4^{ i }\frac { n }{ { 2 }^{ i } } \right) } +{ n }^{ 2 }T\left( 1 \right) \ &=n\sum _{ i=0 }^{ \log _{ 2 }{ n } -1 }{ { 2 }^{ i } } +{ n }^{ 2 }T\left( 1 \right) \ &=n(\frac { { 2 }^{ \log _{ 2 }{ n } }-1 }{ 2-1 } )+{ n }^{ 2 }T\left( 1 \right) \ &=n(n-1)+{ n }^{ 2 }T\left( 1 \right) \ &=\Theta \left( { n }^{ 2 } \right) +\Theta \left( { n }^{ 2 } \right) \ &=\Theta \left( { n }^{ 2 } \right) \end{align}]

수식 말고도 트리 구조를 활용해 직관적으로 구하는 방법도 있습니다. $T(n)=T(n/3)+T(2n/3)$을 구해보겠습니다. 다음 그림과 같습니다.

우선 알고리즘이 한 개의 데이터를 처리하는 데 필요한 시간을 $c$라고 두면, $n$개 데이터를 처리하는 데 드는 시간복잡도는 $cn$입니다. 위 점화식은 한번 분기할 때마다 데이터를 각각 1/3, 2/3씩 나누게 됩니다.

따라서 위 그림 트리를 $i$번 분기했을 때 말단 좌측 끝 노드의 처리 대상 데이터 수는 $n/3^i$가 됩니다. 이 말단 노드의 데이터 수가 1이 될 때까지 분기를 했을 경우 그 분기 횟수 $i$는 $\log_{3}{n}$이 됩니다. ($3^i=n$)

마찬가지로 트리를 $j$번 분기했을 때 말단 우측 끝 노드의 데이터 수는 $n*{(2/3)}^j$가 됩니다. 이 말단 노드의 데이터 수가 1이 될 때까지 분기를 했을 경우 그 분기 횟수 $j$는 $\log_{3/2}{n}$이 됩니다. (${(3/2)}^j=n$)

점근 표기법(자세한 내용은 이곳 참고)은 데이터 수 $n$에 대해 최고차항의 차수만 따집니다. 그런데 위 트리에서 각 층을 연산하는 데 $cn$, 분기 횟수는 최대 $\log_{3/2}{n}$이 되므로 이 알고리즘의 계산복잡도는 $Θ(n\log{n})$가 됩니다.

이렇게 놓고 보면 재귀적으로 분기하는 함수에서 분기 횟수는 분기 비율의 역수를 밑으로 하고 데이터 수를 진수로 하는 로그값임을 알 수 있습니다. 하지만 Iteration method은 점화식이 수렴하지 않고 발산하는 형태일 경우 적용할 수 없습니다.

Master method

이 기법은 알고리즘의 계산복잡도 함수가 $T(n)=aT(n/b)+f(n)$ 형태일 경우 단번에 닫힌 형태를 구할 수 있는 마법과 같은 방법입니다. (단 $a≥1, b>1, f(n)>0$) 여기에서 $n^{\log_{b}{a}}$와 $f(n)$의 크기를 비교해 다음과 같이 한번에 닫힌 형태를 도출합니다. 그러나 아래 세 가지 경우를 제외한 함수에 대해서는 Master method를 적용할 수 없습니다.

case 1 $n^{\log_{b}{a}}>f(n)$ → $T(n)=Θ(n^{\log_{b}{a}})$

case 2 $n^{\log_{b}{a}}×\log{k}≓f(n)$ → $T(n)=Θ(n^{\log_{b}{a}}×\log{(k+1)}×n)$

• 단 로그를 제외한 최고차항의 차수가 같고 $k≥0$이어야 함

case 3 $n^{\log_{b}{a}}<f(n)$ → $T(n)=f(n)$

• 단 충분히 큰 $n$과 1보다 작은 $c$에 대해 $af(n/b)≤cf(n)$을 만족해야 함

예를 들어보겠습니다.

• $T(n)=9T(n/3)+n$
  • $n^{\log_{3}{9}}=n^2$이고 $f(n)=n$이므로 case 1에 해당
  • 따라서 $T(n)=Θ(n^2)$
• $T(n)=27T(n/3)+Θ(n^3\log{n})$
  • $n^{\log_{3}{27}}=n^3$이고 $f(n)=Θ(n^3\log{n})$이므로 case 2에 해당하는지 체크 : $n^3$, $n^3\log{n}$ 비교
  • 로그를 제외한 최고차항의 차수가 3으로 같고 $k=1$일 때 case 2가 성립
  • 따라서 $T(n)=Θ(n^3×\log2×n)$
• $T(n)=5T(n/2)+Θ(n^3)$
  • $n^{\log_{2}{5}}<n^3$이므로 case 3 에 해당
  • $af(n/b)=5{(n/2)}^2=5n^3/8≤cn^3$를 만족하는 1보다 작은 $c$가 존재
  • 따라서 $T(n)=Θ(n^3)$

Recursive Matrix Multiplication에 적용

지금까지 말씀드린 기법을 Recursive Matrix Multiplication에 적용해보겠습니다. 이 기법은 $n×n$ 정방행렬을 $n/2×n/2$ 행렬 4개로 나눈 뒤 내적(inner product)해 공간복잡도를 줄이는 방법입니다. 이같은 방식을 타일링(tiling)이라고 합니다. $A$와 $B$를 내적해 $C$를 얻는 연산($C=AB$)의 경우 다음과 같이 분할-정복 방식으로 나눠풀 수 있습니다.

[\begin{align} \begin{pmatrix} { C }_{ 11 } & { C }_{ 12 } \ { C }_{ 21 } & { C }_{ 22 } \end{pmatrix}&=\begin{pmatrix} { A }_{ 11 } & A_{ 12 } \ { A }_{ 21 } & A_{ 22 } \end{pmatrix}\cdot \begin{pmatrix} { B }_{ 11 } & B_{ 12 } \ B_{ 21 } & { B }_{ 22 } \end{pmatrix}\ \ { C }_{ 11 }&={ A }_{ 11 }\cdot { B }_{ 11 }+{ A }_{ 12 }\cdot { B }_{ 21 }\ { C }_{ 12 }&={ A }_{ 11 }\cdot { B }_{ 12 }+{ A }_{ 12 }\cdot { B }_{ 22 }\ { C }_{ 21 }&={ A }_{ 21 }\cdot { B }_{ 11 }+{ A }_{ 22 }\cdot { B }_{ 21 }\ { C }_{ 22 }&={ A }_{ 21 }\cdot { B }_{ 12 }+{ A }_{ 22 }\cdot { B }_{ 22 } \end{align}]

$n×n$ 정방행렬을 내적하는 데 필요한 계산복잡도를 $T(n)$이라 할 때 이를 다음과 같이 분해할 수 있습니다.

[T\left (n\right)=T\left (divide\right)+T\left (conquer\right)+T\left (merge\right)]

$T(divide)=Θ(1)$입니다. 1부터 $n$의 범위에서 행렬을 어디서 나눌지 한번만 결정하면 되기 때문입니다.

$T(conquer)=8T(n/2)$입니다. 위의 수식처럼 $n/2×n/2$ 행렬 내적을 8번 수행해야 합니다.

$T(merge)=Θ(n^2)$입니다. 예컨대 $A_{11}B_{11}$과 $A_{12}B_{21}$을 더해 $C_{11}$을 만든다고 할 때 $n×n$ 정방행렬의 전체 요소 $n^2$개의 1/4만큼 덧셈 연산을 수행해야할 것입니다. 이를 4회 반복해야 하므로 이같은 결과가 나옵니다.

이를 바탕으로 $T(n)$을 다시 쓰면 다음과 같습니다.

[T(n)=8\cdot T\left( \frac { n }{ 2 } \right) +\Theta \left( {n}^{2} \right)]

위 점화식 형태의 함수를 Master method를 이용해 닫힌 형태로 나타내면 다음과 같습니다.

• $n^{\log_{2}{8}}=n^3>n^2$이므로 case 1 에 해당
• 따라서 $T(n)=Θ(n^{\log_{2}{8}})=Θ(n^3)$

이번 글에 대해서는 알고리즘(algorithm)의 정의와 기본적인 내용에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 김선욱 교수님과 김황남 교수님 강의, 한글 및 영문 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겟습니다.

알고리즘 정의

알고리즘의 정의는 다음과 같습니다.

A precisely defined sequence of computational steps that transform a given input into a desired output. (주어진 입력을 원하는 출력으로 변환하는, 명확하게 정의된 일련의 계산 단계)

이번엔 다른 정의를 보겠습니다. 제가 보기엔 위의 정의와 거의 비슷해 보입니다.

A finite list of well-defined instructions for accomplishing some task. (몇 가지 작업을 수행하기 위해 잘 정의된 지침의 유한한 목록)

알고리즘과 DFA

알고리즘은 유한상태기계(Finite State Machine), 이 가운데 특히 결정적 유한오토마타(Definite Finite Automata)와 깊은 관련을 맺고 있다고 합니다.

유한상태기계란 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델입니다. 이 기계는 한번에 오로지 하나의 상태(state)만을 가지게 되며, 어떤 사건(event)에 의해 한 상태에서 다른 상태로 변화하는데 이를 전이(transition)이라고 합니다. 유한상태기계는 현재 상태로부터 가능한 전이 상태와 이러한 전이를 유발하는 조건들의 집합으로 정의됩니다.

결정적 유한오토마타는 전이가 결정적인(deterministic) 유한상태기계를 의미합니다. 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태만을 가질 수 있습니다. (반면 비결정적 유한오토마타라면 여러 상태를 가질 수 있습니다) . 결정적 유한오토마타의 개념도는 다음과 같습니다. (출처 : 영문 위키피디아)

알고리즘은 초기상태(initial state)에서 시작해 종료상태(end-state)에서 끝납니다. 사전에 명확하게 정의된 절차에 따라 상태가 종료상태를 향해 전이되는 것이죠. 이 일련의 전이 과정이 무한하지 않고 유한하며, 비결정적이지 않고 결정적이라는 점에서 알고리즘은 DFA입니다.

알고리즘과 자료구조

알고리즘과 자료구조(data structure)는 깊은 관련(dependency)을 맺고 있습니다. 현실의 문제를 컴퓨터로 푼다고 할 때 해당 문제의 속성(attribute)을 가장 잘 드러나게끔 자료구조를 만들(거나 선택하)고, 역시 이 문제에 맞는 알고리즘(문제 해결방법) 또한 구현해야 합니다. 어떤 자료구조를 쓰느냐에 따라 알고리즘이 바뀔 것이기 때문에 상황에 따라 최적의 자료구조와 알고리즘을 선택해야겠죠. 이와 관련해 추상자료형(Abstract Data Type)이라는 개념이 있습니다. 자료들과 그 자료들에 대한 연산을 함께 명기한 형태입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

알고리즘 개발의 일반적 절차

일반적 절차는 다음과 같습니다. 이 글에서는 2번만을 조금 더 다루고 3번과 4번은 별도 글에 말씀드리도록 하겠습니다.

1. Design a solution : 알고리즘을 처음 설계하는 과정입니다.
2. Verify the correctness : 알고리즘 설계가 잘 됐나 수학적으로 검증하는 단계입니다.
3. Specify the solution : 의사코드(pseudo-code), 프로그래밍 언어 등으로 기술하는 단계입니다.
4. Evluate the solution : 정확도, 계산복잡성 등 성능을 평가하는 단계입니다.

알고리즘 검증(verify)

알고리즘을 검증하는 수학적 방법에는 귀납에 의한 증명(proof by induction), 반례에 의한 증명(proof by counter example), 귀류법(proof by contradiction) 세 가지가 있습니다.

귀납에 의한 증명

가장 작은 자연수 1일 때 해당 명제를 만족시킴을 증명한 뒤, 만약 어떤 자연수($n$)가 해당 명제를 만족시킨다고 가정한 뒤 바로 다음 자연수($n+1$) 역시 해당 명제를 만족시킴을 증명하기만 하면 해당 명제는 모든 자연수에 대해 성립한다는 걸 증명할 수 있습니다. 이를 수학적 귀납법(mathmatical induction)이라고 합니다. 예를 들면 다음과 같습니다.

$1+2+…+n=n(n+1)/2$임을 증명하라.

(1) $n=1$일 때 성립함 : $1 = 1(1+1)/2 $

(2) 임의의 $n$에 대해 성립한다고 가정

(3) $n+1$일 때도 성립함 : $1+2+..+n+(n+1)=(n+1)(n+2)/2$

반례에 의한 증명

반례란 어떤 명제가 참이 아님을 증명하기 위해서 그 명제가 성립하지 않는 예를 든 것을 말합니다. 예를 들면 다음과 같습니다.

다음과 같은 피보나치 수열이 있을 때 $F_N<N^2$인가?

$F_0=1, F_1=1, F_2=2, F_3=3, F_4=5,…,F_i=F_{i-1}+F_{i-2}$

증명) 그렇지 않다. $F_{11}=144$라는 반례가 존재한다.

귀류법

증명하려는 명제의 결론이 거짓이라는 것을 가정하였을 때 모순되는 가정이 나온다는 것을 보여 원래의 명제가 참인 것을 증명하는 방법입니다. 예를 들면 다음과 같습니다.

소수의 개수가 유한하다고 가정. 이를 $k$라 두자.

(소수 집합 $P={P_1, P_2, …P_k}$에서 가장 큰 소수는 $P_k$이다)

$N=1+P_1P_2…P_k$을 생각해보자.

여기에서 $N$은 $P_k$보다 크므로, 소수 집합에 속하지 않는 합성수(소수의 곱으로 이뤄진 자연수)이다.

합성수 $N$은 임의의 소수 $p$로 나누어 떨어진다.

$N/p = P_1P2…P_k/p+1/p$

위 식에서 $1/p$는 어떤 소수로도 나누어 떨어지지 않는다.

따라서 $N$은 합성수가 아니거나 집합 $P$ 외에 다른 소수가 존재한다. 그러므로 ‘소수는 유한하다’는 것은 거짓이다.

계산복잡도 계산을 위한 기초 수학공식

알고리즘의 효율성 측정 기준은 연산시간(time)과 메모리(memory)입니다. 계산복잡도 계산에 자주 쓰이는 수학공식을 정리해보겠습니다. 우선 수열의 합부터 보겠습니다.

[\begin{align} 1+2+3+…+N&=\frac { N(N+1) }{ 2 } \1+{ 2 }^{ 2 }+{ 3 }^{ 2 }+…+{ N }^{ 2 }&=\frac { N(N+1)(2N+1) }{ 6 }\1+r+{ r }^{ 2 }+{ r }^{ 3 }+…+{ r }^{ N-1 }&=\frac { (1-{ r }^{ N }) }{ 1-r }
\end{align}]

마지막 공식과 관련해 공비($r$)가 1보다 작고 $N$이 충분히 클 때는 $1/(1-r)$에 근사한다고 합니다. 이번엔 로그 공식을 보겠습니다.

[\log _{ a }{ b } =x\quad if\quad { a }^{ x }=b\ \log { (ab) } =\log { a } +\log { b } \ \log { (a/b) } =\log { a } -\log { b } \ \log { { a }^{ b } } =b\log { a } \ \log _{ b }{ a } =\log _{ c }{ a } /\log _{ c }{ b } \ { a }^{ \log { n } }={ n }^{ \log { a } }]

지수 공식은 다음과 같습니다.

[{ a }^{ mn }={ \left( { a }^{ m } \right) }^{ n }={ \left( { a }^{ n } \right) }^{ m }\ { a }^{ m+n }={ a }^{ m }{ a }^{ n }]

이번 글에서는 삽입정렬(Insertion Sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의를 정리했고, 코드는 이곳을 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

삽입정렬

삽입정렬은 다음과 같은 방식으로 동작합니다. 그림으로 예를 들어보겠습니다.

(a)부터 볼까요? 비교 대상 key는 두번째 요소(2)부터 시작합니다. 해당 key의 왼쪽 요소와 크기 비교를 합니다. 따라서 (a)에서는 key(2)와 5를 비교하게 됩니다. 여기에선 5가 크므로 key(2)와 자리를 바꿔 줍니다.

(b)에서 key는 세번째 요소(4)입니다. 해당 key 왼쪽 요소인 5와 비교를 합니다. 여기에선 5가 크므로 key(4)의 자리를 바꿔 줍니다. 이번에는 2와 비교할 차례입니다만, key(4)가 2보다 크므로 자리를 바꿀 필요가 없습니다.

(c)에서 key는 네번째 요소(6)입니다. 해당 key 왼쪽 요소인 5와 비교를 합니다. key(6)가 5보다 크므로 자리를 바꿀 필요가 없습니다. 삽입정렬에서는 key의 왼쪽 요소는 이미 정렬된 상태이므로 더 이상 연산을 수행하지 않습니다.

(d)에서 key는 다섯번째 요소(1)입니다. 해당 key 왼쪽 요소인 6과 비교를 합니다. 여기에선 6이 크므로 key(1)의 자리를 바꿔 줍니다. 같은 방식으로 key(1)를 맨 처음 자리로 보내고 2, 4, 5, 6을 오른쪽으로 한칸씩 옮깁니다.

(e)에서 key는 여섯번째 요소(3)입니다. 해당 key 왼쪽 요소인 6과 비교를 합니다. 여기에선 6이 크므로 key(3)의 자리를 바꿔 줍니다. 같은 방식으로 key(3)을 세번째 자리로 보내고 4, 5, 6을 오른쪽으로 한칸씩 옮깁니다.

이런 방식으로 전체 데이터를 모두 고려하면 삽입정렬이 종료됩니다.

파이썬 구현

삽입정렬을 파이썬 코드로 구현한 결과는 다음과 같습니다.

def insertion_sort(collection):

    for index in range(1, len(collection)):
        while 0 < index and collection[index] < collection[index - 1]: 
            collection[index], collection[
                index - 1] = collection[index - 1], collection[index]
            index -= 1

    return collection

삽입정렬의 계산복잡성

삽입정렬의 의사코드와 계산 단계별 계산비용을 도식화한 표는 다음과 같습니다. 여기에서 $t_j$는 $j$번째 key를 정렬할 때 필요한 비교 연산 횟수를 가리킵니다. 예컨대 (c)에선 key(6)와 5, 딱 한 번만 비교하고 정렬이 끝났으니 $t_4$는 1입니다. 하지만 (d)에선 key(1)의 정렬을 위해 무려 5번이나 비교를 해야 했습니다. $t_j$는 데이터의 정렬 상태에 영향을 받는 값으로, 최소 1, 최대 $j$의 범위를 갖습니다.

그러면 정렬 대상 데이터 개수가 $n$이고, best case(즉 모든 $t_j$가 1인 상황)에 대해 계산복잡도를 구해보겠습니다. 다음 식과 같습니다.

[T(n)={ c }{ 1 }n+{ c }{ 2 }(n-1)+{ c }{ 4 }(n-1)+{ c }{ 5 }(n-1)+{ c }_{ 8 }(n-1)]

자세히 보면 $an+b$ 형태의 1차식입니다. 따라서 best case일 때 삽입정렬의 계산복잡도는 $n$에 대해 선형적으로 증가합니다.

이번엔 worst case(즉 모든 $t_j$가 $j$인 상황)에 대해 살펴봅시다. 다음 식과 같습니다.

[T(n)={ c }{ 1 }n+{ c }{ 2 }(n-1)+{ c }{ 4 }(n-1)+{ c }{ 5 }(\frac { n(n+1) }{ 2 } -1)\+{ c }{ 6 }(\frac { n(n-1) }{ 2 } )+{ c }{ 7 }(\frac { n(n-1) }{ 2 } )+{ c }_{ 8 }(n-1)]

위 식은 $an^2+bn+c$ 형태의 2차식입니다. 따라서 worst case일 때 삽입정렬의 계산복잡도는 $n^2$에 비례하여 증가합니다. 따라서 삽입정렬의 계산복잡도는 best와 worst case 어딘가쯤에 위치하게 될 겁니다.

그런데 알고리즘의 계산복잡도를 구할 때 사실 이렇게까지 자세히 뜯어볼 필요는 없습니다. 가능한 경우의 수를 고려해 어림짐작하는 방법도 얼마든지 있어야 하니까요. best case일 때는 데이터 개수 $n$개만큼의 비교 연산을 수행하면 됩니다. worst case일 때는 $j$가 1일 때는 $t_j$가 1, 2일 땐 (1+2), 3일 땐 (1+2+3)… 이렇게 되므로 $Σn=n(n+1)/2$이 되는 걸 확인할 수 있습니다.

아울러 $T(n)$의 계수($c$)들은 컴퓨팅 파워 등에 따라 커질 수도, 작아질 수도 있습니다. 다만 보통의 알고리즘은 데이터 개수($n$)에 민감하기 때문에 계산복잡성을 구할 때는 계수는 보통 무시하게 됩니다.

이번 글에서는 한국어의 명사절/관형사절 내포에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의와 ‘한국어문법총론1(구본관 외 지음, 집문당 펴냄)’을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

내포

내포란 하나의 절이 다른 절의 한 성분으로 참여하는 방식을 가리킵니다. 이때 안고 있는 절을 모절, 주절, 상위절이라 하고, 안겨 있는 절을 내포절, 종속절, 하위절이라고 합니다. 안겨 있는 절이 명사 역할을 할 경우 명사절, 관형사 역할일 경우 관형사절이라고 합니다. 이 글에서는 명사절과 관형사절을 중심으로 살펴봅니다.

명사절 내포

예시는 다음과 같습니다.

명사형 전성어미

명사절을 만드는 어미를 명사형 전성어미라고 합니다. 대표적으로 ‘-음’과 ‘-기’가 있습니다.

‘-음’은 이미 현실화된 사태를 표현하거나, 개별적이고 구체적으로 존재하는 사태를 요구하는 서술어와 잘 어울립니다. 예문을 보겠습니다.

12월 8일 초등학교 동창 만남.

진이는 자신이 큰 잘못을 저질렀음을 {기억했다, 깨달았다, 떠올렸다, 몰랐다, 알았다, 잊었다, 한탄했다}.

작가는 주인공이 이미 마음이 돌아섰음을 {보이고, 알리고, 암시하고} 있다.

나는 진이가 내게 호의를 가지고 있음을 {느꼈다, 의식했다}.

진이가 잘못을 했음이 {드러났다, 분명하다, 밝혀졌다, 알려졌다, 탄로났다, 틀림없다, 확실하다}.

진이는 민이가 적임자임을 {고백했다, 발표했다, 밝혔다, 보고했다, 주장했다, 지적했다, 통지했다}.

‘-기’는 개별적 사태가 아닌 일반적 사태를 요구하는 서술어, 아직 일어나지 않고 머릿속에 존재하는 사태를 요구하는 서술어와 잘 어울립니다. 예문을 보겠습니다.

12월 8일 초등학교 동창 만나기.

진이는 아침에 조깅하기를 {꺼린다, 싫어한다, 좋아한다, 즐긴다}.

중국어는 우리가 배우기에 {가능한, 까다로운, 나쁜, 쉬운, 알맞은, 어려운, 적당한, 좋은, 힘든} 언어이다.

농부들이 비가 오기를 {갈망한다, 고대한다, 기다린다, 기대한다, 기원한다, 바란다, 빈다, 원한다, 희망한다}.

나는 1년 후 귀국하기로 {결심했다, 결정했다, 계획했다, 맹세했다, 약속했다, 정했다}.

관용적인 명사절 내포

관용표현으로 굳어진 형태로 쓰이는 사례도 많습니다. 예를 들어보겠습니다.

밖에 비가 {오기/*옴} 때문에 행사를 진행하지 않고 있습니다.

‘때문이다’는 그 의미와 상관없이 반드시 ‘-기’로 끝나는 선행어를 써야 합니다. 마찬가지로 ‘나름이다’, ‘마련이다’, ‘십상이다’, ‘위해’도 ‘-기’하고만 어울립니다. 아울러 ‘제가 알기로는’, ‘제가 생각하기에는’, ‘선생님이 말씀하시기를’, ‘나를 알기를 우습게 안다’, ‘친구들이 그립기 이를 데 없다/그지없다’ 등도 관습적으로 쓰입니다.

관형사절 내포

예문은 다음과 같습니다.

관형사형 전성어미

관형사절을 만드는 어미를 관형사형 전성어미라고 합니다. 대표적으로 ‘-ㄴ’과 ‘-ㄹ’이 있습니다. ‘-ㄴ’은 현실화된 일을 나타내는 절에 결합하고, ‘-ㄹ’은 현실화되지 않고 아직 사고의 영역에 있는 일을 나타내는 절에 결합하는 경향이 있습니다. 예문을 보겠습니다.

(1) [쥐를 잡은] 고양이가 낮잠을 잔다.

(2) [쥐를 잡을] 고양이가 낮잠을 잔다.

(1)의 고양이는 이미 쥐를 잡았고, (2)의 고양이는 아직 잡지 않았다는 점에서 의미상 차이가 있습니다.

관형사절의 유형

관형사절에는 크게 관계절, 동격절, 기타 세 가지 종류가 있습니다.

관계절

피수식어에 해당하는 성분이 관형사절 내부에서 생략되어 있는 형태입니다. 모절과 내포절의 공통 명사를 매개로 두 절이 관계돼 있다는 취지로 관계절이라 불립니다. 예를 보겠습니다. (e는 생략됐다는 뜻입니다)

[e 쥐를 잡은] 고양이가 낮잠을 잔다.

위 예시에서 원래 문장은 (1) 고양이가 쥐를 잡았다 (2) 고양이가 낮잠을 잔다일 것입니다. 그런데 ‘고양이가’가 겹치므로 이것이 생략된 채로 내포문을 구성합니다. 다른 예를 보겠습니다.

[e 넓은] 밭이 펼쳐져 있다.

위 문장은 (1) 밭이 넓다 (2) 밭이 펼쳐져 있다 두 절로 분석할 수 있습니다. 마찬가지로 ‘밭이’가 겹치므로 생략된 형태로 관계절을 이룹니다.

주어 말고도 다른 성분으로 관계절을 이루는 예시는 다음과 같습니다.

그 고양이가 쥐를 잡았다 + 쥐가 많다 = [그 고양이가 e 잡은] 쥐가 많다.

내가 어제 서점에 갔다 + 서점은 이 지역의 명소이다 = [내가 어제 e 간] 서점은 이 지역의 명소이다.

동격절

피수식어에 해당하는 성분이 관형사절 내부에서 생략되어 있지 않은 형태입니다. 피수식어의 구체적인 내용을 보충하여 설명한다는 취지로 동격절 또는 보문절이라 불립니다. 예를 보겠습니다.

(가) 나는 진이가 애쓴 사실을 알고 있다.

(나) 진이는 내일 강연할 계획을 취소했다.

(가)에서 언급된 ‘사실’은 ‘진이가 애썼다’는 내용입니다. 의미상 같은 자격을 가지고, ‘사실’을 구체적으로 풀어쓴 형태입니다. 마찬가지로 (나)의 ‘계획’은 ‘내일 강연한다’는 내용입니다.

동격절에는 긴 동격절과 짧은 동격절로 나뉩니다. 전자는 다음 예문과 같이 관형사형 어미 앞이 완전한 문장 형식인 경우를 가리킵니다.

진이가 곧 결혼한다는 소문이 돈다.

짧은 동격절은 관형사형 어미 앞이 완전한 문장 형식이 아닌 경우를 말합니다. 예문을 보겠습니다.

저는 선생님을 만난 기억이 없습니다.

기타

동격절과 관계절 어느 쪽으로도 분류하기 어려운 사례도 있습니다. 예문을 보겠습니다.

(A) 진이는 내가 집에 간 후에 떠났다.

(A)의 피수식어 ‘후’가 관형사절 내부의 성분이 아니라는 점에서 관계절로 보기 어렵습니다. 그렇다고 관형사절이 피수식 명사의 내용을 언급한다고 보기도 어렵다(‘내가 집에 갔다’≠후)는 점에서 동격절로도 분류할 수 없습니다. 굳이 성질을 따져본다면 특수한 명사(후)와 어울려 앞선 절을 뒤의 절에 연결시켜 주는 역할을 합니다. 이 점에 착안해 일부 학자들은 (B)의 ‘내가 집에 간’을 ‘연계절’이라고 부르기도 합니다.

다른 예문을 보겠습니다.

(B) 밥이 타는 냄새가 난다.

(B)의 피수식어 ‘냄새’가 관형사절 내부의 성분이 아니라는 점에서 관계절로 보기 어렵습니다. 또한 밥이 타는 것 자체가 냄새는 아니므로 동격절이라고도 보기 어렵습니다. 하지만 (A)의 ‘후’보다는 (B)의 ‘냄새’가 관형사절과 의미적으로 더 긴밀한 관련을 맺고 있는 느낌이 들기는 합니다. 이런 점에서 일부 학자들은 (B)의 ‘밥이 타는’을 ‘유사 동격절’이라 부르기도 합니다.

딥러닝 기반 자연어처리 기법 연구가 봇물을 이루고 있습니다. 최근 연구트렌드를 정리한 페이퍼가 나와서 눈길을 끄는데요. 바로 아래 논문입니다.

Young, T., Hazarika, D., Poria, S., & Cambria, E. (2017). Recent Trends in Deep Learning Based Natural Language Processing. arXiv preprint arXiv:1708.02709.

저자의 허락을 받아 한국어로 번역해 전문 게재합니다. 가급적 직역하고 용어는 한국어와 영어를 병기했습니다. 본 블로그에도 관련 내용이 있다면 ‘본 블로그’ 표시를 하고 링크를 걸어두었습니다. 실력이 미천해 오역이 많을 텐데요(ㅠㅠ). 댓글이나 이메일로 의견 주시면 적극 수정 반영하겠습니다. 좀 더 쉬운 표현이나 내용 보완 제시도 환영입니다. 한번 업로드했다고 끝이 아니라 지속적으로 수정, 보완해나갈 예정입니다!

본 논문의 목차는 다음과 같습니다.

• Abstract
• 1. 서론
• 2. 분산표상
  • A. 단어 임베딩
  • B. Word2Vec
  • C. 문자 임베딩
• 3. 콘볼루션 신경망
  • A. CNN 기본구조
    • 1) 문장 모델링
    • 2) 윈도우 접근법
  • B. CNN 어플리케이션
• 4. Recurrent Neural Networks
  • A. RNN 필요성
  • B. 네트워크 구조
    • 1) RNN 기본 구조
    • 2) Long Short-Term Memory
    • 3) Gated Recurrent Units
  • C. 어플리케이션
    • 1) 단어 수준 분류를 위한 RNN
    • 2) 문장 수준 분류를 위한 RNN
    • 3) 문장 생성을 위한 RNN
  • D. 어텐션 매커니즘
• 5. Recursive Neural Networks
• 6. 강화학습과 비지도학습
  • A. 문장생성을 위한 강화학습
  • B. 비지도학습 기반 문장 표현
  • C. 심층생성모델
• 7. 메모리 네트워크
• 8. 기법별 성능
  • A. 품사태깅
  • B. 파싱
  • C. 개체명 인식
  • D. 의미역 결정
  • E. 감성분류
  • F. 기계번역
  • G. 질의응답
  • F. 대화 시스템
• 9. 향후 트렌드

Abstract

딥러닝 기법은 데이터의 계층적인 표현(hiarchical representation)을 학습하는 다층 레이어(multiple processing layer)를 사용한다. 그리고 딥러닝은 많은 도메인에서 최첨단(state-of-the-art) 결과를 내고 있다. 최근 다양한 모델 디자인과 기법들이 자연언어처리(Natural Language Processing) 분야에서 꽃피고 있다. 본 논문에서는 수많은 NLP 과제에 적용된 의미 있는 딥러닝 모델과 기법을 검토하고, 이들의 성취에 관해 자세히 설명한다. 또한 다양한 모델들을 비교, 대조함으로써 딥러닝 기반 NLP 기법의 과거, 현재, 미래에 대해 이해할 수 있도록 할 것이다.

1. 서론

자연언어처리(NLP)는 인간 언어 분석과 표현(representation)을 자동화하기 위한 계산 기법이다. NLP 연구는 문장 하나 처리하는 데 7분이 소요되던 펀치 카드와 배치 과정(batch processing)의 시대로부터 1초만에 수백만 웹페이지를 처리할 수 있는 구글의 시대로 발전해왔다(Cambria and White, 2014). NLP는 컴퓨터로 하여금 파싱, 품사태깅에서부터 기계번역, 대화시스템에 이르기까지 모든 과업을 수행할 수 있도록 한다.

딥러닝 아키텍처와 알고리즘은 컴퓨터 비전과 패턴인식 같은 분야에서 이미 의미 있는 발전을 이뤘다. 이러한 경향이 나타난 이후, 최근 딥러닝 기법 기반의 NLP 연구가 늘고 있다(그림1).

그림1: 최근 6년 간 ACL, EMNLP, EACL, NAACL에 게재된 딥러닝 논문의 비율(%). (long paper 기준)

지난 수십년간 NLP 문제를 풀기 위한 머신러닝의 접근은 고차원이면서 sparse한 피처(feature)를 학습한 ‘얕은 모델(shallow models, 예: SVM/로지스틱 회귀)’에 기반한 것이다. 최근 수 년간 dense vector representation에 기반한 뉴럴네트워크가 다양한 NLP task에서 우수한 성능을 보여줬다. 이러한 트렌드는 워드 임베딩(Milokov et al., 2010, 2013a)과 딥러닝 기법(Socher et al., 2013)의 성공에 힘입은 것이다. 딥러닝은 자동화된 피처 추출 및 표현(multi-level automatic feature representation learning)을 가능하게 한다. 그러나 전통적인 머신러닝에 기반한 NLP 시스템은 사람이 직접 추출한(hand-crafted) 피처에 강하게 의존한다. 이러한 피처들은 추출하는 데 시간이 많이 소요되고 많은 경우 불완전하다.

Collobert et al.(2011)은 간단한 딥러닝 프레임워크를 제시했다. 이 프레임워크는 개체명인식(Named Entity Recognition, NER), 의미역결정(Semantic Role Labeling, SRL), 품사태깅(POS tagging) 같은 일부 NLP 태스크에서 최첨단 기법이다. 그 이후 수많은 복잡한 딥러닝 기반의 알고리즘이 어려운 NLP 문제를 풀기 위해 제안되었다. 우리는 콘볼루션 신경망(Convolutional Neural Network, CNN, 본 블로그), 순환신경망(Recurrent Neural Network, RNN, 본 블로그), 재귀신경망(Recursive Neural Network, Recursive NN, 본 블로그) 등 주요 딥러닝모델을 검토한다. 아울러 어텐션(attention) 매커니즘, 강화학습(reinforcement learning)과 심층생성모델(Deep generative model)에 대해서도 다룰 것이다.

우리가 아는 한, 오늘날 NLP 연구에 쓰이는 딥러닝 기법들을 일별하는 이런 작업은 최초다. Goldberg(2016)은 튜토리얼 방식으로 deep NLP 기법을 소개하고, Word2Vec과 CNN 같은 distibutional semantics에 주로 초점을 맞춘다. 그의 논문에서 골드버그는 다양한 딥러닝 아키텍처를 논의하지 않았다. 우리는 이 논문이 deep NLP를 이해하려는 독자들에게 도움이 될 거라 믿는다.

이 논문의 구성은 다음과 같다. 섹션 2에서 우리는 세련된 딥러닝 모델의 근간이 되는 분산표상(distributed representation, 본 블로그)에 대해 논의한다. 다음으로 우리는 섹션 3, 4, 5에 제시된 다양한 NLP 과제에 쓰이는 CNN, RNN, Recursive NN을 소개한다. 우리는 섹션 6에서 NLP 문제에서의 강화학습 응용사례와 비지도학습 기반 문장 학습 기법의 발전에 대해 살펴볼 것이다. 섹션 7에서는 딥러닝 모델과 메모리 모듈 결합의 최근 트렌드를 소개한다. 섹션8에서는 표준적인 데이터셋에 대해 각 기법별 성능을 비교 검토한다.

2. 분산표상

통계 기반의 자연어처리 기법(Statistical NLP)은 복잡한 자연어를 모델링하는 데 기본 옵션으로 부상했다. 그러나 초기에 이 기법은 악명 높은 ‘차원의 저주(curse of dimensionality)’로 어려움을 겪었다. 언어모델(Language model)은 결합확률 함수를 학습해야 했기 때문이다. 이 문제는 저차원 벡터공간에 존재하는 단어의 분산표상(distributed representation)을 학습하는 연구의 동기가 되었다(Bengio et al., 2003).

A. 단어 임베딩

분산표상으로 표현된 벡터(Distributional vectors) 또는 단어 임베딩(Word Embedding, 그림 2)은 근본적으로는 distributional hypothesis(본 블로그)를 전제로 한다. 이 가정은 비슷한 의미를 지닌 단어는 비슷한 문맥에 등장하는 경향이 있을 것이라는 내용이 핵심이다. 따라서 이 벡터들은 이웃한 단어의 특징을 잡아내고자 한다. 분산표상 벡터의 주된 장점은 이 벡터들이 단어 간 유사성을 내포하고 있다는 점이다. 코사인 유사도 같은 지표를 사용함으로써 벡터간 유사성을 측정할 수 있다.

그림2: $D$차원 벡터로 표현된 단어 벡터. $V$를 전체 단어 수라고 할 때, $D$는 $V$보다 훨씬 작다.

단어 임베딩은 딥러닝 모델의 첫번째 데이터 처리 계층에 자주 사용된다. 일반적으로, 단어 임베딩은 레이블이 없는 방대한 말뭉치에서 ‘보조적인 목적함수(예컨대 이웃단어로 중심단어를 예측한다, 각 단어벡터는 일반적인 문법적, 의미적 정보를 내포한다)’를 최적화함으로써 사전 학습된다(Mikolov et al., 2013b, a). 단어 임베딩은 문맥 유사도를 잡아내는 데 효율적이라는 사실이 증명되었다. 또한 임베딩 벡터의 차원이 작은 덕분에 계산이 빠르고 효율적이다.

이러한 임베딩 벡터를 생성하는 모델은 수년 간 얕은(간단한) 뉴럴네트워크였다. 좋은 임베딩을 생성하는 데 있어 깊은 구조의 뉴럴네트워크가 필요하지 않았다. 그러나 딥러닝 기반의 NLP 모델은 언제나 이러한 임베딩 벡터를 활용해 단어, 구, 문장을 표현한다. 이는 사실 전통적인 단어 빈도수 기반의 모델과 딥러닝 기반의 모델 간의 가장 큰 차이점이다.

단어 임베딩은 NLP 문제의 광범위한 범위에서 최첨단(state-of-the-art) 결과를 이끌어냈다(Weston et al., 2011; Socher et al., 2011a; Turney and Pantel, 2010). 예컨대 Glorot et al.(2011)은 도메인 특성에 맞는 감성 분류를 위한 stacked denoisiong autoencoder 모델에 단어 임베딩을 사용했다. Hermann and Blunsom(2013)은 단어 임베딩을 활용해 문장 합성을 학습하기 위한 combinatory categorial autoencoders를 제안했다. 이러한 광범위한 사용은 NLP 태스크를 수행하는 딥러닝 모델에서의 임베딩 효과와 중요성을 보여준다.

워드 임베딩은 주로 문맥(context)을 통해 학습된다. 1990년대에는 몇몇 연구의 발전(Dumais, 2004; Elman, 1991; Glenberg and Robertson, 2000)이 분산의미론(distributional semantics) 연구의 기초를 세웠다. 이후 발전은 이러한 초기 업적의 변형들로써, 잠재디리클레할당(Latent Dirichlet Allocation, Blei et al., 2003, 본 블로그)과 같은 토픽 모델과 언어모델(Language models, Bengio et al., 2003)의 탄생을 이끌었다. 이러한 업적들은 표현학습(representation learning, 본 블로그)의 토대를 마련했다. Bengio et al.(2003)은 단어의 분산표상을 학습하는 신경 언어모델(neural language model)을 제안했다(그림3, 본 블로그).

그림3: Bengio et al.(2003)가 제시한 신경 언어모델. $C(i)$는 $i$번째 단어의 벡터이다.

Collbert and Weston(2008)은 사전 학습된 단어 임베딩의 유용성을 처음 보여줬다. 그들은 현재 많은 연구의 기초를 형성하는 뉴럴네트워크 아키텍처를 제안했다. 이 연구는 또한 NLP 과제의 유용한 도구로서 단어 임베딩의 지위를 확립했다. 하지만 엄청난 인기를 끌고 있는 단어 임베딩 기법은 바로 Milokov et al.(2013a), (본 블로그)이다. 이들은 고품질의 단어 벡터를 효율적으로 구축하기 위해 continous-bag-of-words(CBOW)와 skip-gram 모델을 제안했다.

Pennington et al.(2014)는 Word2Vec과는 달리 본질적으로 빈도 기반의 단어 임베딩 기법(본 블로그)이다. 우선 단어공기행렬(word co-occurrence count matrix)을 생성한 뒤 빈도 수를 정규화하고 로그 스무딩을 실시한다. 저차원 벡터를 얻기 위해 재구축 오차(reconstruction loss)를 최소화하는 방식으로 이 행렬을 factorize한다. 다음 장에서는 Mikolov et al. (2013a)이 제안한 Word2Vec 기법에 대해 설명한다.

B. Word2Vec

단어 임베딩은 CBOW와 skip-gram 모델을 제안한 Mikolov et al. (2013b, a) (본 블로그)에 의해 비약적인 발전을 이뤘다. CBOW는 $k$개만큼의 주변 단어가 주어졌을 때 중심 단어의 조건부확률을 계산한다. skip-gram 모델은 CBOW와 정반대로, 중심단어가 주어졌을 때 주변단어를 예측한다. 문맥에서 한 단어만 고려하는 CBOW 모델의 단순화한 버전을 생각해보자. 이는 기본적으로 바이그램 모델을 모사한 것이다. 그림4와 같이 CBOW 모델은 1개의 은닉층을 가진 simple fully connected neural network이다.

그림4: Word2Vec의 CBOW 모델(Mikolov et al., 2013b)

개별 단어 임베딩의 한가지 한계는 두개 이상의 단어(예: ‘hot potato’ 같은 숙어, ‘Boston Globe’ 같은 개체명)의 조합이 개별 단어 벡터의 조합으로 표현될 수 없다는 것이다. 이런 문제의 한 가지 해결책은 Mikolov et al. (2013a)에서 살펴본 바와 같이 동시등장단어(word coocurrence)에 기반한 구문을 식별하고 이들을 별도로 학습시키는 것이다. 보다 최근의 기법은 레이블이 없는 데이터로부터 n-gram 임베딩을 직접적으로 학습시키는 방법이다(Johnson and Zhang, 2015).

또다른 한계는 주변 단어의 작은 window 내에만 기반한 임베딩을 학습하는 데서 비롯된다. 때때로 good과 bad 같은 단어가 거의 같은 임베딩을 공유한다(Socher et al., 2011b). 이는 감성분석 같은 task에서는 문제가 된다(Wang et al., 2015a). 때로는 이러한 임베딩은 상반된 극성을 갖는 단어가 의미상 유사한 단어로 클러스터링된다. 이는 감성분석에 사용되는 다운스트림 모델이 이러한 대조적인 극성을 구별하지 못하게 만들어 성능 저하로 이어진다. Tang et al. (2014)는 sentiment specific word embedding(SSWE)을 제안함으로써 이러한 문제를 해결했다. 그들은 임베딩을 학습하는 동안 손실함수에 정답 극성을 포함시켰다.

단어 임베딩에 대한 일반적인 주의사항은 임베딩이 사용된 어플리케이션에 크게 의존한다는 것이다. Labutov and Lipson (2013)은 단어 벡터를 재학습하여 현재 task space에 맞추기 위해 task specific embedding을 제안했다. 아무런 사전 지식없이 임베딩을 학습시키는 것은 많은 시간과 리소스를 필요로 하기 때문에 이는 매우 중요하다. Mikolov et al. (2013b)는 negative sampling 기법을 제안함으로써 이 문제를 해결하려고 했다. 표1은 딥러닝 모델에 자주 사용되는 임베딩 프레임워크들을 나열한 것이다.

C. 문자 임베딩

단어 임베딩은 문법적, 의미적 정보를 잡아낼 수 있다. 그러나 품사태깅이나 개체명인식 같은 태스크에서는 단어 내부의 형태 정보 또한 매우 유용하다. 문자 수준의 자연어이해(Natural Language Understanding) 시스템 구축은 어느 정도 관심을 끌고 있다(Kim et al., 2016; Dos Santos and Gatti, 2014; Santos and Guimaraes, 2015; Santos and Zadrozny, 2014). 특정 NLP 태스크에 있어서는 형태적으로 복잡한 언어에 대한 개선된 결과가 보고된다. Santos and Guimaraes (2015)는 단어 임베딩과 함께 문자 수준 임베딩을 개체명인식 문제에 적용해 포르투갈어와 스페인어 말뭉치에서 state-of-the-art 수준의 결과를 냈다. Kim et al. (2016)은 문자 임베딩만 사용한 neural language model을 구축해 긍정적인 결과를 보였다. Ma et al. (2016)은 개체명인식에서 사전 학습된 레이블 임베딩을 학습하기 위해 문자 trigram을 포함해 몇몇 임베딩 기법을 활용했다.

문자 임베딩은 미등재단어(the unknown word) 이슈에 자연스럽게 대처하게 된다. 단어는 개별 문자의 결합이기 때문이다. 텍스트가 단어뿐 아니라 문자의 결합으로 구성되고, 단어의 의미가 문자들의 합성에 대응되는 언어(예컨대 중국어)에서는, 문자 수준의 시스템 구축은 단어 분할(word segmentation)을 피하기 위한 자연스런 선택이다(Chen et al., 2015a). 따라서 이런 언어에 딥러닝 기법을 적용하는 연구들은 단어보다 문자 임베딩을 선호하는 경향이 있다(Zheng et al., 2013). 예를 들면 Peng et al. (2017)은 radical 기반의 처리가 감성 분류 성능을 크게 개선할 수 있음을 입증했다. 그들이 제안한 계층적 임베딩은 문자 수준의 의미뿐 아니라 감성 정보까지 포함한다.

3. 콘볼루션 신경망

워드 임베딩이 인기를 끌고 그 성능 또한 검증된 이후, 단어 결합이나 n-gram으로부터 높은 수준의 피처를 추출해내는 효율적인 함수의 필요성이 증대됐다. 이러한 추상화된 피처들은 감성분석, 요약, 기계번역, 질의응답(QA) 같은 다양한 NLP 문제에 사용될 수 있다. 콘볼루션 신경망은 컴퓨터 비전 분야에서 뛰어난 성능으로 인해 자연스런 선택이었다(Krizhevsky et al., 2012; Sharif Razavian et al., 2014; Jia et al., 2014).

문장 모델링에서 CNN을 활용하는 것은 Colobert and Weston(2008)로 거슬러 올라간다. 이 연구는 다범주 예측 결과를 출력하기 위해 multi-task learning을 사용했다. 품사태깅, 청킹, 개체명인식, 의미역결정, 의미적으로 유사한 단어 찾기, 랭귀지모델 같은 NLP 과제 수행을 위해서다. 참조테이블(look up table)은 각 단어를 사용자가 정의한 차원의 벡터로 변형해 사용된다. 따라서 $n$개의 단어로 이뤄진 입력문장 {$s_1, s_2, .., s_n$}은 참조테이블을 활용해 벡터들의 나열인 {$w_{s_1}, w_{s_2}, …, w{s_n}$}으로 변환된다. (그림 5)

그림5: Colobert and Weston(2008)이 제안한 CNN 프레임워크. 그들은 단어 범주 예측에 이 모델을 사용했다

이는 학습 과정에서 단어 벡터(가중치)가 학습되는 초기 단어 임베딩 기법의 아이디어로 생각할 수 있다. Collobert et al. (2011)은 넘쳐나는 NLP 문제를 해결하기 위해 그의 이전 업적을 확장해 일반적인 CNN 기반의 프레임워크를 제안했다. Colobert and Weston(2008)과 Collobert et al. (2011)은 NLP 연구자들 사이에 CNN이 큰 인기를 끌도록 촉발시켰다. CNN이 이미 컴퓨터 비전 태스크에서 괄목할 만한 성능을 보인 상황에서 사람들이 CNN의 성능을 믿는 것은 쉬웠다.

CNN은 문장의 잠재적인 semantic represention을 만들어내기 위해 입력 문장으로부터 핵심적인 n-gram 피처를 추출하는 능력을 갖고 있다. 이 분야의 선구적인 업적은 Collobert et al. (2011), Kalchbrenner et al. (2014), Kim(2014)이다(본 블로그). 이들은 후속 연구에서 CNN 기반의 네트워크가 크게 확산되도록 했다. 다음 장에서는 단순 CNN 기반 문장 모델링 네트워크의 작동을 설명한다.

A. CNN 기본구조

1) 문장 모델링

문장의 $i$번째 단어에 해당하는 임베딩 벡터를 $w_i$, 임베딩 벡터의 차원수를 $d$라고 두자. $n$개 단어로 이뤄진 문장이 주어졌을 때, 문장은 $n$ x $d$ 크기의 임베딩 행렬로 표현할 수 있다. 그림 6은 CNN 프레임워크의 입력 문장을 나타낸다.

그림6: 텍스트 처리를 위한 콘볼루션 신경망. Zhang and Wallace(2015)

$w_i$, $w_{i+1}$, …, $w_j$의 결합(concatenation)을 $w_{i:i+j}$라 두자. 콘볼루션은 이 값에 수행된다. 콘볼루션 필터 $k$는 차원수가 $hd$인 벡터이다. 이 필터는 $h$개 단어벡터에 적용된다. 예를 들면 콘볼루션 필터에 의해 새로 추출된 피처 $c_i$는 $w_{i:i+h-1}$를 활용해 생성된다. 식은 다음과 같다.

[{ c }{ i }=f\left( { w }{ i:i+h-1 }\cdot { k }^{ T }+b \right)]

위 식에서 스칼라 $b$는 bias term이며 $f$는 하이퍼볼릭탄젠트 같은 비선형 활성함수이다. 필터 $k$는 피처맵을 생성하기 위해 동일한 가중치를 사용하며 모든 가능한 윈도우에 적용된다.

[c=\left[ { c }{ 1 },{ c }{ 2 },…,{ c }_{ n-h+1 } \right]]

CNN에서 콘볼루션 필터(커널로 불리기도 한다)의 수는 전형적으로 수백개다. 필터의 폭은 각기 다르며, 각 필터는 n-gram의 특정 패턴을 추출한다.

콘볼루션 레이어는 대개 맥스풀링 계층, 즉 $\hat { c } =max(c)$이 후행한다. 맥스풀링은 $c$에 대해 최대값을 취함으로써 입력값을 서브샘플링한다. 이 전략을 쓰는 데는 두 가지 이유가 있다.

첫째, 맥스풀링은 일반적으로 분류에 필요한 고정 길이의 출력을 제공한다. 따라서 필터의 크기가 각기 다름에도 맥스풀링은 입력값을 항상 고정된 차원의 출력으로 매핑한다.

둘째, 맥스풀링은 전체 문장에서 가장 핵심적인 n-gram 피처를 유지하면서 출력의 차원을 줄인다. 이는 개별 필터가 문장 내 어느 지점에 있든 특정 피처(예를 들어 ‘부정’)를 추출할 수 있고 이를 최종적인 문장 표현(representation)에 덧붙일 수 있기 때문에 변함없는 방식(invariant manner)으로 수행된다.

단어 임베딩은 랜덤 초기화하거나 레이블 없는 방대한 말뭉치에서 사전학습될 수 있다. 후자는 특히 정답 데이터의 양이 적을 때 성능 향상에 때로는 유용하다(Kim, 2014, 본 블로그). 콘볼루션 계층과 맥스풀링의 이런 조합은 보다 깊은 CNN 네트워크를 만들기 위해 종종 겹쳐 쌓게 된다. 이러한 sequential convolution은 풍부한 의미 정보를 포함하는 고도로 추상화된 표현을 잡아내 문장의 분석을 개선할 수 있도록 한다. 깊은 콘볼루션 구조의 필터(커널)은 문장 피처의 전체 요약을 만들기까지 문장의 넓은 부분을 커버하게 된다.

2) 윈도우 접근법

지금까지 기술한 CNN 아키텍처는 완전한 자연어 문장을 벡터로 표현한다. 그러나 개체명인식, 품사태깅, SRL 같은 많은 NLP 문제는 단어 단위의 예측이 필요하다. 이런 태스크에 CNN을 적용하기 위해, 윈도우(window) 접근법이 쓰인다. 이는 단어의 범주(tag)가 기본적으로 이웃 단어에 의존할 것이라고 가정한다. 따라서 각 단어에 대해, 고정된 크기의 윈도우가 가정되고, 윈도우 내에 있는 하위 문장들이 고려된다. 독립형(standalone) CNN은 앞서 설명한 바와 같이 이러한 하위 문장에 적용되며 예측은 윈도우 중심에 있는 단어에 기인한다.

이러한 접근에 따라, Poria et al. (2016a)는 문장 각 단어에 aspect¹ 혹은 non-aspect 태그를 붙이기 위해 multi-level deep CNN을 제안했다. 언어적 패턴의 셋과 결합되어 이들의 앙상블 분류기는 aspect detection에 있어 좋은 성능을 냈다.

단어 수준 분류의 주요 목표는 일반적으로 전체 문장에 레이블 시퀀스(sequence)를 할당하는 것이다. Conditional Random Field(CRF) 같은 구조화된 예측 기법은 때때로 인접한 클래스 레이블 간의 의존성을 더 잘 포착한다. 그리고 이 기법은 결국 전체 문장에 최대 스코어를 내는 결합된(cohesive) 레이블 시퀀스를 생성한다(Kirillov et al., 2015).

문맥적 범위를 넓히기 위해, 전통적인 윈도우 접근법은 종종 time-dealy neural network(TDNN)와 결합된다(Waibel et al., 1989). 여기에서 콘볼루션은 시퀀스 전체의 모든 윈도우에서 수행된다. 이런 콘볼루션들은 일반적으로 필터의 폭이 사전에 정의된다는 점에서 제약을 받는다. 따라서 전통적인 윈도우 접근법은 레이블이 달린 단어 주변의 윈도우에 있는 단어들만 고려하는 반면, TDNN은 문장 내 모든 윈도우들을 동시에 고려한다. 때때로 TDNN 레이어는 CNN 아키텍처처럼 쌓아져(stack) 하위 계층에서 로컬 피처, 상위 계층에서 글로벌 피처를 추출한다(Collobert et al., 2011).

B. CNN 어플리케이션

이 장에서는 NLP 문제에 CNN을 적용한 주요 연구를 소개한다.

Kim(2014)는 감성, 주관성, 질문유형 분류를 포함한 다양한 문장 분류 문제에 이미 기술한 아키텍처를 실험했다. 이 연구는 간단하지만 효율적인 네트워크여서 아마추어 연구자들에 의해 빠르게 적용되었다(본 블로그). 특정 과업 학습 후 랜덤하게 초기화된 콘볼루션 필터는 목적하는 태스크에 유용한 특정한 n-gram 피처 감지기(detector)가 됐다(그림7). 그러나 Kim(2014)의 아키텍쳐는 장거리 의존성(long distance dependencies)을 모델링할 수 없는 등 많은 단점을 지닌다.

그림7: 7-gram 필터(커널)로 학습된 고빈도 7-gram. 각 필터는 특정 종류의 7-gram에 민감하다. Kim(2014)

이러한 이슈는 Kalchbrenner et al.(2014)에 의해 효과적으로 처리된다. 이들은 문장의 의미를 모델링하기 위한 dynamic convolutional neural network(DCNN)을 제안했다. 이들은 dynamic k max pooling 전략을 제안했다. 이는 시퀀스 $p$가 주어졌을 때 가장 활동적인(active) $k$개의 피처를 뽑는 방법이다. 선택은 피처의 순서를 보존하지만, 특정 위치에는 민감하지 않다(그림8).

그림8: DCNN의 서브그래프. dynamic k max pooling을 사용하면 상위 계층의 작은 너비의 필터가 입력문장에서 관계된 구문을 멀리 떨어뜨릴 수 있다. Kalchbrenner et al.(2014)

Kalchbrenner et al.(2014)는 문장 모델을 만들기 위해 TDNN의 개념을 기반으로 dynamic k max pooling 전략을 추가했다. 둘의 조합은 작은 폭의 필터가 입력문장의 긴 범위를 커버할 수 있게 한다. 그림8에서 상위의 피처는 집중적이고 짧거나, 전역적이고 입력문장처럼 길 수도 있는 매우 가변적인 범위를 가진다. 이들은 감성 분류, 질의 유형 분류를 포함한 다양한 task에 이 네트워크를 적용했고, 의미있는 결과를 얻었다. 요컨대 이 연구는 문맥적 의미를 모델링하는 데 있어 개별 필터의 범위(range)에 대해 언급했고, 필터의 도달 범위를 확장하는 방법론을 제안했다.

감성분석 문제는 또한 극성(polarity)에 관계된 aspect¹의 효과적인 추출을 필요로 한다(Mukerjee and Liu, 2012). Ruder et al. (2016)은 좋은 결과를 얻기 위해 워드 임베딩과 aspect vector를 결합한(concatenate) 값을 입력으로 하는 CNN을 적용했다.

CNN은 텍스트 길이에 따라 성능이 달라진다. 이런 상이함은 Johnson and Zhang(2015)와 같은 많은 연구에 나타난다. 장문의 텍스트에 대한 CNN 모델의 성능은 좋았던 반면 짧은 텍스트에선 반대였다. Wang et al.(2015b)는 짧은 텍스트의 표현(representation)을 모델링하는 데 CNN을 제안했다. 저자들은 단문의 외부적 지식이 사용된 multi-scale semantic units를 도입한 의미론적 클러스터링(semantic clustering)을 제안했다. CNN은 이러한 유닛들을 결합하고 전체적인 표현(represention)을 만들어내는 데 쓰인다.

사실 고도의 문맥정보에 대한 이러한 요구는 CNN 기반 모델에 대한 경고(caveat)로 생각될 수 있다. CNN 기반 모델을 사용해 단문을 분석하는 작업은 추가적인 정보와 외부 지식을 필요로 한다. 이런 사실은 Poria et al.(2016)에서도 관찰된다. 저자들은 CNN 네트워크를 활용해 트위터 텍스트에서 빈정대는 부분을 찾아내는 기법(sarcasm detection)을 제안했다. 감정, 감성, 개성 데이터셋으로 사전 학습된 형태의 보조적인 지원이 state-of-the-art 성능을 이끌어내는 데 사용됐다.

CNN은 또한 다른 task에서도 널리 쓰인다. 예를 들면 Denil et al. (2014)는 요약을 위해 문장을 구성하는 단어의 의미를 문서의 의미로 매핑시키는 데 DCNN을 적용했다. 이 연구의 핵심은 학습과정뿐 아니라 텍스트의 자동요약을 위한 인사이트를 제공하는 새로운 시각화 기술의 도입에 있다.

QA 분야에서는 Yih et al. (2014)가 질의에 답할 때 지식베이스(Knowledge Base)에서 어떤 사실을 찾아봐야 하는지 결정하기 위해 질의와 KB 사이의 의미적 유사성을 측정하는 방안을 제시했다. 의미론적 표현(semantic representation)을 생성하기 위해, 그림6에 있는 CNN과 유사한 CNN이 사용됐다. 분류 문제를 풀기 위한 세팅과 달리, 정답셋으로는 클래스 레이블 대신 긍정 혹은 부정적인 텍스트 쌍을 쓴다(예: 쿼리-문서).

이후 Dong et al. (2015)는 다중 aspect¹로부터 질의를 분석하고 이해하는 한편 질의의 표현(representation)을 만들기 위한 multi-column CNN(MCCNN)을 소개했다. MCCNN은 입력 질의에서 응답 유형과 문맥을 구성하는 aspect로부터 정보를 추출하기 위해 다수의 column network를 쓴다. KB의 개체(entities)와 관계를 벡터로 표현함으로써, 그들은 후보가 되는 응답에 순위를 매기기 위하여 질의-응답 쌍을 사용하여 CNN 모델을 학습시켰다.

Severyn and Moschitti(2016)은 또한 CNN 네트워크를 질의와 응답 문장의 최적 표현(representation)을 모델링하는 데 사용했다. 그들은 질의와 응답 쌍 사이에 단어를 매칭시킴으로써 임베딩에서 추가적인 피처를 제안했다. 이러한 파라메터들은 네트워크에 의해 튜닝된다. 이런 간단한 네트워크는 state-of-the-art 성능을 내는 기법에 필적하는 결과를 산출할 수 있었다.

CNN 모델은 또한 분류를 넘어서는 의미론적 일치(semantic matching)가 필요한 특정 NLP 태스크에도 적합하다(Hu et al., 2014). 그림 6의 CNN 아키텍처와 비슷한 모델이 정보 검색을 목적으로 Shen et al. (2014)에 의해 탐색되었다. CNN은 질의와 문서를 고정된 차원의 의미공간에 투영(project)하는 데 사용된다. 이 의미공간에서는 쿼리와 문서 간 코사인 유사도가 특정 쿼리에 해당하는 문서의 랭킹을 매기는 데 쓰인다. 모델은 단어 시퀀스에서의 일시적인 context window를 고려함으로써 쿼리나 문서에서의 풍부한 문맥 구조 추출을 시도한다. 이 모델은 n-gram 수준에서의 문맥 피처를 잡아낸다. 그리고 나서 핵심 n-gram은 전체를 아우르는 문장 벡터를 형성하기 위해 결합(aggregate)되는 콘볼루션과 맥스풀링 계층에 의해 발견된다.

CNN은 문장에서 가장 중요한 정보를 뽑기 위한 방법과 연결되어 있다. 그러나 기존의 맥스풀링 전략은 문장에서 가치 있는 정보를 종종 잃어버린다. 다중 이벤트 모델링(multiple-event modeling)에서 이러한 정보 손실 문제를 극복하기 위해, Chen et al. (2015b)는 수정된 풀링 전략, 즉 dynamic multi-pooling CNN(DMCNN)을 제안했다.

CNN은 본질적으로 로컬 연결성(local connectivity), 가중치 공유, 풀링 등의 특징이 있다. 이러한 속성은 많은 task에서 고도로 요구되는 불변성(invariance)을 어느 정도 보장한다. 음성 인식 또한 이러한 불변성을 필요로 한다. 이 때문에 Abdel-Hamid et al. (2014)는 하이브리드 CNN-HMM 모델을 사용했다. 이 변동성은 종종 화자 차이에 기인한 음성 신호에서 종종 발견된다. Abdel-Hamid et al. (2014)는 또한 파라메터를 줄여 계산복잡성을 낮췄다. Palaz et al. (2015)는 CNN 기반의 음성 인식 시스템에 대한 집중적인 분석을 수행했다. 그들은 원시 입력(raw input)과 음성(phone) 사이의 관계를 직접적으로 모델링하는 CNN의 능력을 입증했고, 강건한(robust) 자동 스피치 인식 시스템을 만들어냈다.

기계번역 같은 작업에는 순차적인 정보와 장기 의존성에 대한 인내(perseverance)가 필요하다. 따라서 구조적으로 이러한 작업들은 이러한 피처들을 잃어버리는 CNN 네트워크에 적합하지 않다. 그럼에도 Tu et al. (2015)는 번역 쌍들 간 의미적 유사성과 번역대상 문장의 문맥을 모두 고려해 이 문제를 다뤘다. 비록 이 방법은 시퀀스 인내 문제를 다루지는 않지만, 다른 벤치마크 연구들과 비교해 견줄 만한 결과를 냈다.

전반적으로, CNN은 contextual window 내에 있는 의미적 단서를 추출하는 데 고도로 효율적이다. 그러나 CNN은 매우 많은 데이터를 필요로 한다. CNN 모델은 방대한 양의 데이터를 요구하는 다수의 학습 파라메터를 포함한다. CNN은 데이터가 부족할 때는 문제가 된다. CNN의 다른 이슈는 먼 거리의 문맥 정보를 모델링하기가 불가능하고 그들의 표현(repesentation)에서 시퀀셜한 순서를 보존할 수 없다는 것이다. 문장 모델링의 Kalchbrenner et al. (2014), 기계번역의 Tu et al. (2015)가 약간 다뤄지긴 했지만, 이 문제는 여전히 중요한 이슈로 남아있다. 따라서 Recursive NN과 같은 네트워크가 이런 학습에 적합하다.

4. Recurrent Neural Networks

Recurrent Neural Network(Elman, 1990)는 순차적인 정보를 처리하는 네트워크다(본 블로그). 전통적인 뉴럴 네트워크와 달리, RNN은 모든 입력값이 독립적이라고 가정한다. ‘recurrent’라는 용어는 모델이 입력 시퀀스의 각 인스턴스에 대해 같은 작업을 수행하고 아웃풋은 이전 연산및 결과에 의존적이라는 데에서 붙었다. 일반적으로 recurrent unit에 토큰을 하나씩 입력함으로써 고정 크기의 벡터가 시퀀스를 표현하기 위해 생성된다. 이런 방식으로 RNN은 이전 연산결과를 ‘기억’하고, 현재 연산 과정에서 이 정보를 활용한다. 이러한 템플릿은 랭귀지 모델링(Mikolov et al., 2010, 2011; Sutskever et al., 2011), 기계번역(Liu et al., 2014; Auli et al., 2013; Sutskever et al., 2014), 음성인식(Robinson et al., 1996; Graves et al., 2013; Graves and Jaitly, 2014; Sak et al., 2014), 이미지 캡셔닝(Karpathy and Fei-Fei, 2015) 등과 같은 많은 NLP 작업에 적합하다. 이로 인해 최근 수년 간 NLP 어플리케이션에 RNN이 널리 보급됐다.

A. RNN 필요성

이번 장에서 우리는 수많은 NLP 태스크에서 인기를 끌고 있는 RNN의 기본 속성에 대해 살펴본다. RNN은 데이터를 순차적으로 처리하기 때문에, 언어에서 고유한 순차적인 성격을 포착할 수 있는 능력이 있다. 단어는 이전 단어를 바탕으로 의미를 갖게 된다. 이와 관련한 간단한 예시는 ‘dog’와 ‘hot dog’ 간의 의미 차이일 것이다. RNN은 이러한 문맥 의존성을 모델링하기 위해 만들어졌으며 연구자들이 CNN보다 RNN을 사용하는 강한 동기가 되었다.

RNN이 시퀀스 모델링에 적합한 다른 요인은 매우 긴 문장, 단락, 심지어 문서(Tang et al., 2015)를 포함해 다양한 텍스트 길이를 모델링할 수 있는 능력이다. CNN과 달리 RNN은 무제한 컨텍스트를 포착할 수 있는 유연한 계산 step을 가진다. 임의의 길이의 입력값을 처리할 수 있는 이러한 능력은 RNN을 사용하는 주요 연구의 셀링포인트 가운데 하나가 됐다(Chung et al., 2014).

다수의 NLP 태스크는 또한 전체 문장에 대해 의미론적 모델링을 요구한다. 이것은 고정된 차원의 하이퍼스페이스 내에 문장의 요지(gist)를 만들어내는 것과 관련이 있다. 이들 인스턴스는 RNN에 의해 적절히 포착된다. 전체 문장이 고정된 벡터로 요약되고 나서 가변 길이의 타겟 시퀀스로 매핑되는 기계번역(Cho et al., 2014) 같은 작업에 RNN 사용이 증가했다.

RNN은 또한 시간 분산 조인트 처리(time distributed joint processing)를 위한 네트워크 지원을 제공한다. 품사태깅(Santos and Zadrozny, 2014) 같은 시퀀스 레이블링 작업의 대부분은 이러한 domain에 기반한 것이다. 보다 구체적인 사용사례는 문서분류(Chaturvedi et al., 2016), 다범주 텍스트 범주화(Chen et al., 2017), 멀티모달 감성분석(Poria et al., 2017; Zadeh et al., 2017; Tong et al., 2017), 주관성 디텍션(Chaturvedi et al., 2017) 등이 있다.

이미 서술한 사실들은 연구자들이 RNN을 선택하는 동기가 되는 몇가지 이유다. 그러나 RNN이 다른 네트워크보다 우월하다고 결론을 내리는 것은 잘못된 것이다. 최근에 여러 연구는 CNN이 RNN보다 우월하다는 증거를 제시한다. 언어모델링(Langurage modeling) 같은 RNN에 적합한 태스크일지라도, CNN은 RNN보다 경쟁력 있는 성능을 달성했다(Dauphin et al., 2016). CNN과 RNN은 문장을 모델링할 때 다른 목적(함수)를 갖는다. RNN이 경계없는 긴 문장을 생성하려고 하는 반면, CNN은 가장 중요한 n-gram을 추출하려고 한다. 둘다 n-gram 피처를 잡아내는 데 효율적이지만, 단어 순서에 대한 민감도가 지역적으로(locally) 제한되며 장기(long-term) 의존성은 보통 무시된다.

Yin et al. (2017)은 RNN과 CNN 성능에 관한 흥미있는 인사이트를 제시한다. 감성분류, QA, 품사태깅을 포함하는 여러 NLP task를 평가한 후에 그들은 ‘완전한 승자는 없다’고 결론 내렸다. 각 네트워크의 성능은 태스크가 요구하는 글로벌 시맨틱(global semantics)에 의존한다. 아래에서는 최근 연구에서 광범위하게 사용되는 RNN 모델 중 일부에 대해 설명한다.

B. 네트워크 구조

1) RNN 기본 구조

그림9: 간단한 RNN 구조

NLP의 맥락에서 RNN은 주로 Elman network(Elman, 1990)에 기반을 두고 있으며 원래는 3개 계층으로 이뤄진 네트워크다(본 블로그). 그림 9는 일반적인 RNN을 나타낸다. 그림에서 $x_t$는 $t$시점의 입력값이며, $s_t$는 $t$ 시점의 히든 스테이트(hidden state)를 나타낸다. $s_t$ 계산은 다음 식과 같다.

[{ s }{ t }=f\left( U{ x }{ t }+W{ s }_{ t-1 } \right)]

$s_t$는 현재 입력 및 이전 단계의 히든 스테이트를 기반으로 계산된다. 함수 $f$는 하이퍼볼릭탄젠트, ReLU와 같은 비선형 변환이며 $U, V, W$는 모든 시점에서 공유된다. NLP의 맥락에서 $x_t$는 일반적으로 one-hot 벡터 또는 임베딩 벡터다. $x_t$는 때때로 텍스트가 추상적으로 표현된 벡터일 수도 있다. $o_t$는 네트워크의 출력이다.

RNN의 히든 스테이트는 일반적으로 가장 중요한 요소로 간주된다. 앞서 언급했듯이 히든 스테이트는 다른 time step의 정보를 누적한 네트워크의 메모리 요소로 간주될 수 있다. 그러나 실제에선 이러한 간단한 RNN 네트워크는 악명 높은 배니싱 그래디언트 문제(Vanishing gradient problem)로 인해, 네트워크에서 이전 레이어의 파라메터를 학습하고 업데이트하는 걸 매우 어렵게 만든다. 이러한 제한은 LSTM, GRU 및 ResNet과 같은 다양한 네트워크에 의해 극복되었다.

2) Long Short-Term Memory

LSTM(Hochreiter and Schmidhuber, 1997; Gers et al., 1999, 그림 10)은 간단한 RNN에 forget gate를 추가했다. 이러한 독특한 매커니즘을 통해 배니싱 그래디언트 문제, 익스플로딩 그래디언트 문제(exploding gradient problem_를 모두 극복할 수 있다(본 블로그).

그림10: LSTM과 GRU 게이트. Chung et al.(2014)

vanilla RNN과 달리 LSTM을 사용하면 오차가 무제한적인 time step에 역전파될 수 있다. 3개의 gate, 즉 input/forget/output gate로 구성되며 히든 스테이트는 아래 식에 따라 계산된다.

\(x=\begin{bmatrix} { h }_{ t-1 } \\ { x }_{ t } \end{bmatrix}\\ { f }_{ t }=\sigma \left( { W }_{ f }\cdot x+{ b }_{ f } \right) \\ { i }_{ t }=\sigma \left( { W }_{ i }\cdot x+{ b }_{ i } \right) \\ o_{ t }=\sigma \left( { W }_{ o }\cdot x+{ b }_{ o } \right) \\ { c }_{ t }={ f }_{ t }\odot { c }_{ t-1 }+{ i }_{ t }\odot \tanh { ({ W }_{ c }\cdot x+{ b }_{ c }) } \\ { h }_{ t }={ o }_{ t }\odot \tanh { ({ c }_{ t }) }\)

3) Gated Recurrent Units

GRU(Cho et al., 2014)라 불리는 RNN의 변형은 대부분의 task에서 LSTM과 경험적으로 유사한 성능을 내면서 구조적으로는 더 간단하다(본 블로그). GRU는 reset gate와 update gate의 두 개 gate로 구성되며 LSTM처럼 메모리를 보호한다. GRU는 LSTM보다 효율적인 RNN이 될 수 있다. GRU의 작동은 다음과 같다.

[z=\sigma \left( { U }{ z }\cdot { x }{ t }+{ W }{ z }{ h }{ t-1 } \right) \ r=\sigma \left( { U }{ r }\cdot { x }{ t }+{ W }{ r }{ h }{ t-1 } \right) \ { s }{ t }=\tanh { ({ U }{ z }\cdot { x }{ t }+{ W }{ s }\cdot ({ h }{ t-1 }\odot r)) } \ { h }{ t }=(1-z)\odot { s }{ t }+z\odot { h }{ t-1 }]

연구자들은 종종 적절한 RNN 게이트를 선택해야하는 딜레마에 직면한다. 이는 NLP분야를 연구하는 사람들도 마찬가지다. 역사를 통틀어 RNN 변형에 대한 대부분의 선택은 heuristic한 경향을 보였다. Chung et al. (2014)는 NLP task가 아니지만, 위에서 언급한 세 가지 RNN 변형들에 대한 비판적 비교 평가를 수행했다. 그들은 다성 음악 모델링 및 음성 신호 모델링과 관련된 task 성능을 평가했다. 그들의 평가는 전통적인 단순 RNN(하이퍼볼릭탄젠트 사용)에 비해 gated unit(LSTM, GRU)의 우월성을 분명히 보여주었다(그림 11). 그러나 이들은 LSTM과 GRU 가운데 어느 것이 더 좋은지에 대해선 구체적인 결론을 내릴 수 없었다. 이러한 사실은 다른 연구에서도 잘 나타나므로, 사람들은 둘 중 하나를 선택할 때 컴퓨팅 파워 같은 다른 요소를 고려하는 경우가 종종 있다.

그림11: 반복횟수와 계산시간과 관련한 학습곡선들. y축은 로그 스케일로 나타낸 모델의 음의 로그우도에 해당한다. Chung et al. (2014)

C. 어플리케이션

1) 단어 수준 분류를 위한 RNN

RNN은 단어 수준 분류에서 많이 쓰이고 있다. 이런 인기는 RNN의 state-of-the-art 수준의 성능 덕분이다. Lample et al., (2016)은 개체명인식을 위한 bidirectional LSTM 모델을 제안했다. 네트워크는 타겟 단어 주변의 임의의 긴 맥락 정보를 포착해 두 개의 고정된 크기의 벡터를 반환한다. 그 위에 또 하나의 fully-connected 레이어가 있다. 그들은 최종 개체명 태깅에 CRF 레이어를 썼다.

RNN은 또한 언어모델링(Language modeling) 면에서 빈도 기반의 기존 방법론보다 상당한 개선을 보여줬다. 이 분야 주목할 만한 연구는 Graves(2013)이다. 그는 긴 범위의 문맥 구조에서 복잡한 시퀀스를 모델링하는 데 RNN이 효율적임을 보여줬다. 그는 또한 은닉층이 여러 개인 deep RNN을 제안했다. 이 연구는 NLP를 넘어선 태스크에도 RNN의 사용을 확립시켰다. 이후 Sundermeyer et al. (2015)은 뒷 단어 예측시 feed-forward neural network를 RNN으로 대체함으로써 얻는 이득을 비교했다. 이 연구에서 그들은 기존의 빈도 기반의 언어모델보다 성능이 대폭 향상된 뉴럴 네트워크 아키텍처에서 일반적인 계층구조를 제안했다. 그들이 언급한 중요한 점은 이것이 통계적 기계번역과 같은 다양한 다른 업무에 적용 가능하다는 사실이다(Sundermeyer et al., 2014).

Kim et al. (2016)과 Lample et al. (2016)은 형태적(morphological) 정보를 포함한는 문자 기반의 표현(representation) 사용을 탐색했다. 베이스라인인 단어 기반의 LSTM 모델보다 나은 성능을 나타낸다는 점에서, 문자 기반의 모델이 문자로부터 의미, 철자(orthographic) 정보 모두를 추출할 수 있다는 걸 보여준다. 문자 기반 모델링은 러시아어, 중국어 같이 형태가 복잡한 텍스트에서 강화된 입력값 정보를 제공한다. 아울러 문자들은 방대한 말뭉치를 요구하는 단어와 달리 보통 훨씬 작은 입력공간에 존재한다. 그러나 단어 기반의 처리가 우세한 분야가 많다. 따라서 이 분야에서 확실한 승자는 아직 모른다.

2) 문장 수준 분류를 위한 RNN

Wang et al. (2015a)는 LSTM으로 트위터 문장을 인코딩하는 모델을 제안했다. 이 모델의 히든 스테이트는 감성 극성을 예측하는 데 사용된다. 이러한 간단한 전략은 좀 더 복잡한 DCNN 구조(Kalchbrenner et al., 2014)와 비교해도 좋은 성능을 나타냈다. DCNN은 CNN 모델이 장기 의존성을 포착할 수 있도록 디자인되었다. 저자들은 또한 LSTM 게이트가 ‘not’이라는 단어가 감성의 극성을 반전시키는 걸 포착할 수 있음을 보였다.

CNN과 유사하게, RNN의 히든 스테이트는 또한 텍스트 사이의 의미적 일치(semantic matching)에 쓰일 수 있다. 대화시스템에서 Low et al. (2015)는 Dual-LSTM으로 메세지를 후보 응답과 매칭시키는 모델을 제안했다. Dual-LSTM은 메세지와 응답을 고정된 크기의 벡터로 인코딩하고, 그리고 나서 후보 응답의 순위를 매기기 위해 둘을 내적한다.

3) 문장 생성을 위한 RNN

NLP 분야에서 도전적인 과제는 자연어를 생성하는 일이다. 이는 RNN의 또다른 어플리케이션이기도 하다. 텍스트 혹은 시각적 데이터가 주어졌을 때, deep LSTM은 기계번역, 이미지 캡셔닝 등 태스크에서 합리적인 성능을 보였다. 그런 사례에서 RNN은 디코더(decoder)로 불린다(본 블로그).

Sutskever et al. (2014)에서 저자들은 시퀀스와 다른 시퀀스를 매핑시키는 일반적인 deep LSTM encoder-decoder 프레임워크를 제안했다. 하나의 LSTM은 소스 시퀀스를 고정된 크기의 벡터로 인코딩한다. 소스 시퀀스는 기계번역의 경우 원래 언어의 텍스트, 질의응답에서는 질의, 대화시스템에서는 메세지가 된다. 이렇게 인코딩된 고정된 크기의 벡터는 디코더로 불리는 또다른 LSTM의 초기 상태(initial state)로 쓰인다. 추론 과정에서 디코더는 토큰을 하나씩 생성하고, 직전에 생성된 토큰으로 히든 스테이트를 업데이트한다. Beam Search는 최적 시퀀스를 근사하는 데 자주 사용된다.

Sutskever et al. (2014)는 종단간(end-to-end) 기계번역을 위한 4개 계층으로 이뤄진 LSTM을 실험했고, 좋은 성능을 보여줬다. Vinyals and Le(2015)는 동일한 프레임워크를 인간 대화를 모델링하는 데 적용했다. 1억개 이상의 메세지-응답 쌍을 학습했을 때, LSTM 디코더는 오픈 도메인에서 아주 흥미로운 응답을 생성할 수 있다. Li et al. (2016a)는 개별 화자의 인물정보를 내포하는 constant persona vector를 디코더 입력값으로 사용할 것을 제안했다.

위의 사례들에서 언어는 텍스트 입력값을 표현하는 의미 벡터들에 주로 기반해 생성된다. 유사한 프레임워크가 이미지 기반의 언어 생성에서도 성공적으로 사용되고 있다. 이미지 기반의 언어 생성에서는 가시적 피처(visual feature)가 LSTM 디코더를 조건부화하는 데 쓰인다. (그림 12)

그림12: 이미지를 벡터로 임베딩하는 CNN과 결합된 LSTM 디코더. 이미지 캡션을 생성한다. Vinyals et al. (2015a)

비주얼 QA는 텍스트와 이미지 둘 모두에 기반한 언어 생성을 요구하는 또다른 태스크이다. Malinowski et al. (2015)는 CNN에 의해 모델링된 입력 이미지와 LSTM으로 모델링된 텍스트를 조건으로 이미지 캡션의 시퀀스를 예측하는 종단간(end-to-end) 딥러닝 모델을 최초로 제시했다(그림 13). Kumar et al.(2015)는 4개의 하위 모듈을 가진 Dynamic Memory Network(DMN)이라는 정교한 네트워크를 제안했다.

그림13: Neural-image QA. Malinowski et al. (2015)

D. 어텐션 매커니즘

기존의 인코더-디코더 프레임워크가 직면한 하나의 잠재적인 문제는 인코더가 때로는 해당 작업과 완전히 관련되지 않은 정보까지도 인코딩해야 한다는 사실이다. 입력값이 길거나 정보가 아주 많은 경우, 그리고 선택적인 인코딩이 불가능할 경우 문제가 발생한다.

예를 들면, 문서 요약 작업은 입력값은 오리지날 텍스트이고 출력은 축약된 버전으로 하는 시퀀스 간(seqeunce-to-sequence) 학습 문제로 풀 수 있다. 길이가 매우 길 수도 있는 텍스트의 모든 정보를 고정 크기의 벡터로 인코딩하는 것은 직관적으로 기대하기 어렵다. 기계 번역에서도 비슷한 문제가 보고되었다(Bahdanau et al., 2014).

반면에, 텍스트 요약과 기계 번역 같은 작업에서 입력 텍스트와 출력 텍스트 사이에 일정한 정렬(alignment)이 존재한다. 요약이나 번역에서 각 토큰 생성 단계는 입력 텍스트의 특정 부분과 매우 관련이 있다.

어텐션 매커니즘은 디코더가 입력 시퀀스를 다시 참조할 수 있게 하여 위의 문제를 완화하려고 시도한다. 디코더는 마지막 히든 스테이트와 생성된 토큰에 더하여 ‘context’ 벡터에 대해 조건부화된다.

Bahdanau et al. (2014)는 기계 번역에 어텐션 매커니즘을 처음으로 적용했다. 어텐션 매커니즘은 특히 긴 시퀀스에 대해 모델의 성능을 향상시킨다. 그들의 연구에서, 입력된 히든 스테이트 시퀀스에 대한 어텐션 시그널은 디코더의 마지막 계층에 의해 다층 퍼셉트론으로 결정된다. 어텐션 시그널을 시각화하면 소스와 타겟 랭귀지 간의 명확한 정렬(alignment)를 보여줄 수 있다(그림14).

그림14: 단어 정렬 행렬. Bahdanau et al. (2014)

Rush et al. (2015)는 유사한 접근법으로 요약에 적용했다. 입력 문장은 어텐션 매커니즘을 통해 출력 단어를 조건짓는다. 여러 분야에서 성공을 거두면서 어텐션 기반의 모델이 NLP 연구자들 사이에서 주목 받기 시작했다.

이미지 캡셔닝에서 Xu et al.(2015)는 입력 이미지의 다른 부분으로 LSTM 디코더를 조건부화했다. 어텐션 시그널은 이전의 히든 스테이트 및 CNN이 뽑아낸 피처에 의해 결정됐다. Vinyals et al. (2015b)는 파싱 트리를 선형화(linearing)함으로써 구문 파싱 문제를 시퀀스 간 학습 문제로 풀었다. 어텐션 매커니즘은 이 작업에서도 효율적(data-efficient)임이 입증됐다. 입력 시퀀스를 참조하는 또다른 단계는 대화 생성과 텍스트 요약과 같은 작업에 유용한 특정 조건(Vinyals et al., 2015c) 하에서 입력 단어 또는 하위 시퀸스를 출력 시퀀스에 직접 복사하는 것이 있다. 복사나 생성은 디코딩하는 동안 각 스텝에서 선택된다. (Paulus et al., 2017)

aspect¹ 기반의 감성분석에서, Wang et al.(2016)은 aspect 임베딩을 사용한 어텐션 기반의 해법을 제안했다(그림 15). 어텐션 모듈은 분류할 aspect에 영향을 주는 문장의 선택 영역에 초점을 둔다.

그림15: 어텐션 매커니즘을 사용한 aspect 분류. Wang et al.(2016)

그림 16과 같이, (a)에서 ‘service’라는 aspect를 기준으로 보면, 어텐션 모듈은 ‘fastest delivery times’이라는 문구에 동적으로 초점을 맞춘다. (b)에서 ‘food’라는 aspect를 기준으로 보면, 모델은 ‘tasteless’과 ‘too sweet’라는 문구를 찾아낸다.

반면 Tang et al. (2016)은 멀티플-홉 어텐션(multiple-hop attention)을 사용하는 메모리 네트워크에 기반한 해법을 채택했다. 이는 또한 ‘MemNet(Weston et al., 2014)’이라고도 알려져 있다. 메모리상의 멀티플 어텐션(multiple attention) 계산계층은 메모리의 정보 영역 대부분에 대한 검색을 향상시키고 결과적으로 분류를 돕는다. 이들의 연구는 이 영역에서 최첨단 기술이다.

어텐션 모듈의 직관적인 적용 가능성을 감안할 때, 어텐션 매커니즘은 점점 더 많은 어플리케이션에 채택되고 있다.

5. Recursive Neural Networks

Recurrent Neural Network는 시퀀스(순차적인 데이터) 모델링에 강점을 지닌 기법이다. 그러나 자연언어는 단어와 단어가 계층적인 방식으로 구(phrase)로 결합되는 재귀적인(recursive) 구조를 나타낸다. 이러한 구조는 문장 구성성분 분석 트리(constituency parsing tree)로 표현될 수 있다. 이 때문에 문장의 문법적 구조 해석을 보다 용이하게 하기 위해 트리 구조 모델이 사용되었다(Tai et al., 2015). 특히 Recursive Neural Network에서 각 노드는 자식 노드의 표현(representation)에 의해 결정된다(본 블로그).

Socher et al. (2013)은 구문(pharase), 문장 수준 감성 예측에 이 모델을 적용했다(본 블로그). 저자는 이 연구에서 그림 17과 같이 파싱 트리의 모든 노드(단어)에 대해 감성 스코어를 시각화했다. 여기에선 전체 문장의 감성에 큰 영향을 미치는 ‘not’ 또는 ‘but’ 같은 단어에 대한 모델의 민감도가 나타난다.

LSTM은 Tai et al. (2015)가 제안한 트리 구조에도 적용되었다(본 블로그). 그래디언트 배니싱 문제(Gradient Vanishing Problem)를 피하기 위해서다. 이 모델은 감성 분석(Sentiment analysis)과 문장 관련성 테스트(sentence relatedness test)에서 linear LSTM 모델보다 개선됐다.

6. 강화학습과 비지도학습

A. 문장생성을 위한 강화학습

강화학습(Reinforcement Learning)은 보상(reward)을 얻기 전에 행동(action)을 수행하도록 에이전트(agent)를 학습시키는 기법이다. Paulus et al. (2017)은 기존의 지도 학습 기반의 단어 예측 기법과 강화학습을 결합한 생성요약(abstractive summarization) 모델을 제안했다. 기존의 RNN 기반 언어생성기(language generator)는 일반적으로 현재 히든 스테이트(hidden state)와 이전 토큰(token, 단어)이 주어졌을 때 정답 단어가 나타날 우도(likelihood)를 최대화함으로써 학습된다. Teacher forcing이라 불리는 기법은 RNN 학습 과정에서 이전 스텝의 정답 단어들을 다음 스텝의 입력값으로 넣는다. 그러나 추론(inference) 과정에서는 이전 토큰은 모델 자체에서 생성된 토큰으로 대체된다.² ‘노출 편향(expose bias, Bengio et al., 2015; Ranzato et al., 2015)’라고 불리는 학습과 추론 사이의 이러한 불일치는 생성된 시퀀스에 따라 빠르게 누적될 수 있는 오류를 야기할 수 있다.³

단어 수준의 최대 우도 전략의 또다른 문제점은 학습목표(training objective)가 테스트 측정지표(test metric)과 다르다는 사실이다. 기계번역, 대화시스템 등을 평가하는 데 쓰이는 측정지표(BLUE, ROUGE)가 단어 수준 학습 전략으로 어떻게 최적화될 수 있는지 분명하지 않다. 경험적으로, 단어 수준 최대 우도로 학습된 대화시스템은 둔하고 근시안적인 반응을 생성하는 경향(Li et al., 2016b)이 있고, 단어 수준 최우도 기반의 텍스트 요약도 역시 비간섭적(incoherent)이거나 반복적인 요약을 생성하는 경향이 있다(Paulus et al., 2017).

강화학습은 위의 문제를 어느 정도 해결할 수 있는 잠재력을 제공한다. Ronzato et al.(2015)는 시퀀스 생성 작업(예: 텍스트 요약, 기계번역, 이미지 캡셔닝)을 위한 RNN 기반의 모델을 학습시키기 위해 강화학습 알고리즘(Williams, 1992)를 적용했고, 이전의 지도학습(supervised learning method) 기법과 비교해 개선을 이끌어냈다. 이러한 프레임워크에서 시퀀스 생성모델(RNN)은 환경(단어와 컨텍스트 벡터)과 상호작용하는 에이전트로 간주된다. 이 에이전트의 파라메터는 정책을 정의한다. 정책의 실행으로 에이전트는 각 time step에서 시퀀스의 다음 단어를 예측하는 행동(action)을 취한다. 행동을 취한 다음 에이전트는 내부 상태(RNN의 히든 유닛)를 업데이트한다. 에이전트가 시퀀스의 끝에 도달하면 보상을 받는다. 이 보상은 수행할 태스크에 맞게 연구자가 정의할 수 있다. 대화시스템을 연구한 Li et al. (2016b)는 생성 문장에 대해 3가지 보상(응답의 용이성, 정보 흐름 및 의미의 일관성)을 정의했다.

강화학습 이외의 다른 접근법은 적대적인 학습 기술(the adversarial training technique, GAN)을 사용하는 것이다(Goodfellow et al., 2014). 생성기(generator)의 학습 목표는 생성된 시퀀스와 진짜 시퀀스를 구별하도록 학습된 다른 판별자(discriminator)를 속이는 것이다. 생성기 G와 판별자 D는 min-max 게임에서 함께 학습되며, 생성기는 판별자가 실제 시퀀스와 구별할 수 없는 시퀀스를 생성한다. 이 접근법은 특정 자극(예: 이미지 캡셔닝에서의 소스 이미지)을 조건으로 하는 GAN(Goodfellow et al., 2014)의 변형으로 볼 수 있다. 이같은 프레임워크는 정책 그래디언트(policy gradient)를 가진 강화학습 패러다임 하에서도 실현될 수 있다. 대화시스템의 경우 판별자는 사람과 기계가 생성한 대화를 구분하는 튜링 테스트와 유사하다. (Li et al., 2017)

B. 비지도학습 기반 문장 표현

문장에 대한 분산표상(distributed representation)도 단어 임베딩처럼 비지도(unsupervised) 방식으로 학습할 수 있다. 이러한 비지도학습의 결과는 임의의 문장을, 의미와 문법적 속성이 내재한 고정 크기의 벡터에 매핑하는 ‘문장 인코더’이다. 일반적으로 학습과정을 위해 보조적인 작업(task)을 정의해야 한다.

단어 임베딩을 위한 skip-gram 모델(Mikolov et al., 2013b)과 유사하게, 문장 임베딩을 위한 skip-thought 모델(Kiros et al., 2015)이 제안됐다. skip-thought 모델에서 보조적인 과제는 주어진 문장 앞뒤에 있는 두 개의 인접 문장을 예측하는 것이다. 여기에는 seq2seq 모델이 사용됐다. 하나의 LSTM이 문장을 벡터(분산표상)로 인코딩한다. 두 개의 다른 LSTM은 이 벡터를 디코딩하여 타겟 시퀀스를 생성한다. 학습을 마친 인코더는 문장의 피처(feature)를 뽑아내는 추출기로 볼 수 있다(단어 임베딩 또한 동시에 학습된다).

Kiros et al. (2015)는 문장 분류(sentence classification) 문제로 학습된 문장 인코더의 품질을 검증했다. 정적인 특징 벡터(static feature vector)[^5] 기반의 단순 선형 모델로 경쟁력 있는 결과를 보여주었다. 그러나 문장 인코더는 학습 과정에서 미세 조정(fine-tune)될 수 있다. Dai and Le(2015)는 오토인코더(autoencoder, Rumelhart et al., 1985)와 유사하게, 인코딩된 문장 자체를 재구축(reconstruct)하는 디코더를 사용했다.

언어모델링(Language modeling)은 LSTM 인코더를 학습할 때 보조적인 작업으로 사용될 수도 있다. 감독 신호(supervision signal)는 다음 토큰의 예측에서 비롯된다. Dai and Le(2015)는 다양한 작업에서 사전 학습된 파라메터를 LSTM 모델의 초기값으로 쓰는 실험을 수행했다. 그들은 방대한 비지도 말뭉치로 사전 학습된 문장 인코더가 단어 임베딩만 사전학습해 사용하는 것보다 더 나은 정확성을 보임을 입증하였다. 아울러 다음 토큰을 예측하는 것은 문장 자체를 재구축(reconstruct)하는 것보다 더 나쁜 보조 목표인 것으로 판명됐다. LSTM의 히든 스테이트는 단기(shor-term) 기억에만 충실하기 때문이다.

C. 심층생성모델

사실적인 이미지 생성 관련 최근의 성공은 심층생성모델(deep generative model)을 텍스트에 적용하는 일련의 노력을 이끌었다. 그러한 연구의 약속은 잠재코드공간(latent code space)에서 실제 문장을 생성하면서 자연어의 풍부한 구조를 발견하는 것이다. 이 장에서는 이러한 목표를 달성하기 위한 VAE(Variational autoencoder, Kingma and Welling, 2013)과 GAN(Generative Adversarial Network, Goodfellow et al., 2014)의 최근 연구를 검토한다.

표준적인 오토인코더는 자연어 문장 생성에 실패한다(Bowman et al., 2015). 잠재공간(latent space)에 어떤 제약도 가하지 않기 때문이다. 이들 문장의 표현(representation)은 히든 스페이스(hidden space)에서 작은 영역을 차지할 수 있고, 히든 스페이스 대부분의 영역은 반드시 실제 문장에 매핑되지는 않는다(Zhang et al., 2016). 표준적인 문장 오토인코더는 문장에 확률을 할당하거나 새로운 문장을 뽑는 데 사용될 수 없다(Bowman et al., 2015).

VAE는 적절한 샘플을 뽑을 수 있도록 하는 히든 코드 스페이스(hidden code space)에 사전 분포(prior distribution)를 부과한다. 그것은 결정론적인 인코더 기능(deterministic encoder function)을 학습된 사후확률 인식(posterior recognition) 모델로 대체함으로써 오토인코더 아키텍처를 수정한다. 모델은 데이터를 잠재표현(latent representation)으로 인코딩하는 인코더와 잠재공간에서 샘플을 생성하는 생성자(generator) 모델로 구성된다. 이 모델은 관측된 데이터의 로그 우도에 대한 변량적 하한(variational lower bound)을 최대화함으로써 학습된다.

Bowman et al. (2015)는 전체 문장의 분산잠재표상(distributed latent representations)을 통합한 RNN 기반의 VAE 생성 모델을 제안했다(그림 18). vanilla RNN 언어 모델과 달리, 이 모델은 명시적인 전역 문장 표현(global sentence representation)에서 작동한다. 이 문장에 대한 사전확률(prior)로부터 뽑은 샘플은 다양하고 세련된 문장을 만들었다.

Hu et al. (2017)은 지정된 의미를 가진 엉킴 없는(disentangled) 잠재 표현을 학습함으로써 속성이 제어되는 문장 생성 기법을 제안했다. 저자들은 구조화된 변수 집합을 사용하여 VAE의 잠재코드(latent code)를 만들었는데, 각각은 중요하고 독립적인 문장의 피처를 타겟으로 한다. 모델은 VAE와 속성 판별자(attribute disciminators)를 포함한다. 그럴듯한 텍스트를 생성하기 위해 생성자를 훈련시켜 실제 문장을 재구축(recontruct)하는 한편, 판별자는 생성자가 구조화된 코드와 일관된 속성을 생성하도록 강제한다. 다수의 정답 없는 문장과 소수의 정답 문장을 학습했을 때, Hu et al.(2017)은 모델이 영어의 두 가지 주요 속성(시제, 감성)에 맞는 그럴듯한 문장들을 생성할 수 있음을 보여줬다.

GAN은 생성모델의 다른 종류이다. GAN은 두 가지 경쟁 네트워크로 구성된다. 생성자 네트워크는 잠재 공간에서 데이터 인스턴스로 잠재 표현을 인코딩한다. 반면 판별자 네트워크는 실제 데이터와 생성자가 만든 인스턴스를 구별하기 위해 생성자와 동시에 학습된다. GAN은 실제 데이터 분포인 $p(x)$를 명시적으로 표상하지는(represent) 않는다.

Zhang et al. (2016)은 실제 텍스트를 생성하기 위한 적대적인 학습에 LSTM과 CNN을 적용한 프레임워크를 제안했다. 잠재코드(latent code) ‘z’는 매 time step마다 LSTM 생성자(generator)에 입력되었다. CNN은 실제 데이터와 생성된 샘플을 구별하는 이진 문장 분류기 역할을 수행했다. GAN을 텍스트에 적용할 때 문제점은 판별자로부터 나온 그래디언트가 제대로 역전파될 수 없다는 점이다. Zhang et al.(2016)에서 이 문제는 단어 예측을 항상 ‘soft’하게 함으로써 해결되었다. Yu et al. (2017)은 생성자를 stochatic policy로 모델링함으로써 이 문제를 우회할 것을 제안했다. 보상 신호(reward signal)는 완전한 시퀀스에서 판단된 GAN 판별자로부터 나온 것이며, 몬테카를로 탐색을 사용하여 중간 상태-행동 단계(intermidiate state-action steps)로 다시 전달된다.

심층학습모델 평가는 어렵다. 텍스트의 경우 고정된 문법 규칙으로 학습 데이터를 만든 다음, 생성된 샘플이 미리 정의한 문법과 일치하는지 여부로 생성모델을 평가할 수 있다(Rajeswar et al., 2017). 또다른 전략은 학습에 쓰지 많은 양의 테스트 데이터에서 샘플의 BLEU 점수를 평가해보는 것이다. 학습에 쓰지 않은 실제 데이터와 유사한 문장을 생성하는 능력은 모델의 품질 척도로 간주된다(Yu et al., 2017).

7. 메모리 네트워크

어텐션(attention) 매커니즘은 인코더에서 만들어진 히든 벡터(hidden vector)들을 저장한다. 디코더는 각 토큰을 생성하고 있는 중에 이 벡터들에 액세스할 수 있다. 여기서 인코더의 히든 벡터들은 모델의 ‘내부 메모리(internal memory)’ 항목으로 볼 수 있다. 최근에는 모델이 상호작용할 수 있는 메모리의 형태로 뉴럴 네트워크들을 연결하는 것에 대한 관심이 급증했다.

Weston et al. (2014)는 질의응답(QA)을 위한 메모리 네트워크를 제안했다. 이 작업(task)에서 일련의 진술(statements, 메모리 항목)은 질의를 잠재적으로 뒷받침하는 사실로써 모델에 입력된다. 모델은 질의과 이전에 검색한 메모리를 기반으로 한번에 하나의 항목을 검색하도록 학습됐다. 대규모 현업 QA에서 (주체, 관계, 대상)이라는 트리플 형태로 방대한 지식이 메모리로 사용됐다. Sukhbaatar et al. (2015)는 이러한 작업을 확장하여, 메모리 항목이 어텐션 매커니즘을 통해 ‘soft’한 방식으로 검색되어 종단간(end-to-end) 학습을 가능하도록 하는 ‘end-to-end memory network’를 제안했다. 메모리에서 여러번 정보 검색을 수행하면 좋은 성능을 내며, 모델은 특정 질의에 대한 답변을 위해 몇 가지 뒷받침하는 사실을 검색하고 추론할 수 있다. (그림 19)

Sukhbaatar et al. (2015)는 언어 모델링을 위한 모델의 특별한 사용법을 보여주었다. 여기에서 문장의 각 단어는 메모리 항목으로 간주된다. 멀티홉(mulitiple hop)을 사용하여, 모델은 deep LSTM 모델에 필적하는 결과를 산출했다.

또한 Dynamic Memory Networks(DMN, Kumar et al., 2015)는 입력 표현(representation), 어텐션 및 응답 매커니즘을 위한 뉴럴 네트워크를 사용하여 이전의 메모리 기반 모델을 개선했다. 이 모델은 모든 데이터 인스턴스가 <메모리, 질문, 답변> 트리플 포맷으로 캐스팅될 수 있으므로 광범위한 범위의 NLP 문제(QA, 품사태깅, 감성분석)에 적용할 수 있다. Xiong et al.(2016)은 visual QA에 동일한 모델을 적용하여 ‘메모리 모듈’이 시각적 신호에도 적용 가능함을 입증했다.

8. 기법별 성능

표준적인 데이터셋에 대한 최근 개발된 딥러닝 기법의 성능을 표2~7에 요약 제시했다.

A. 품사태깅

[표2] 품사태깅

WSJ-PTB(the Wall Street Journal part of the Penn Treebank Dataset) 말뭉치에는 117만개 토큰이 포함돼 있으며 품사태깅 시스템 개발과 평가에 널리 쓰이고 있다. Gimenez and Marquez (2004)는 일곱개의 단어 window에서 수작업으로 정의한 피처를 기반으로 one-against-all SVM을 사용하여, 몇 가지 기본적인 n-gram 패턴을 다음과 같이 이진 피처로 평가했다. “이전 단어는 ‘the’이다”, “앞의 두 태그는 DT(한정사) NN(일반명사)이다” 등.

품사태깅 문제의 한가지 특징은 인접한 태그 간에 의존성이 강하다는 점이다. 왼쪽에서 오른쪽으로 태그를 붙이는 간단한 방법을 사용하여, Gimenez and Marquez (2004)는 피처 엔지니어링(feature engineering)⁴을 통해서만 인접 태그간의 종속성을 모델링했다. 피처 엔지니어링을 위한 노력을 줄이기 위해, Collobert et al. (2011)은 다층 퍼셉트론(multi-layer perceptron)에 의한 단어 임베딩에만 의존했다. CRF(Conditional Random Field)는 Collobert et al.(2011)에서 유용함이 입증되었다. Santos and Zadrozny(2014)는 단어 임베딩을 문자 임베딩과 합쳐(concatenate) 형태적(morphological) 단서들을 더 잘 활용한다. Santos and Zadrozny(2014)는 CRF를 고려하지 않았지만, 이 모델의 예측은 문맥 window 내에서 이뤄지기 때문에, 인접 태그 간 종속성이 암시적으로 모델링된 것이라 볼 수 있다. Huang et al. (2015)는 워드 임베딩과 수작업으로 설계한 단어 수준 피처(feature)를 합치고(concatenate) 긴 문맥을 모델링하기 위해 bidirectional LSTM을 사용했다. 분석 결과 양방향성(bidirectionality)과 CRF 둘 모두 모델 성능을 높이는 데 기여했다. 7장 메모리 네트워크 장에서 이미 언급한 바 잇는 DMN(Kumar et al., 2015)은 품사태깅에도 적용될 수 있다. DMN은 RNN의 각 히든 스테이트를 메모리 항목으로 처리함으로써 컨텍스트에 여러번 집중할 수 있다.

B. 파싱

[표3] 파싱 UAS/LAS = Unlabeled/labeled Attachment Score; WSJ = Wall Street Journal Section of Penn Treebank

파싱(parsing, 구문분석)에는 두 가지 유형이 있다. 하나는 개별 단어를 이들 사이의 관계를 고려해 연결하는 의존구문분석(dependency parsing)과 텍스트를 반복적으로 하위 구문으로 분리하는 구성성분분석(constituency parsing)이다. 전이 기반 의존구문분석(transition-based dependency parsing)은 문장 길이가 선형적(linear)이기 때문에 널리 사용되는 선택이다. 구문분석기(parser)는 순차적으로 단어를 읽어들여 구문 구조(syntactic structure)에 점진적으로 결합시키는 일련의 결정을 내린다(Chen and Manning, 2014). 각 time step에서 사용 가능한 트리 노드를 포함하는 스택(stack), 읽지 않은 단어와 dependency arc의 집합을 포함하는 버퍼(buffer)를 기반으로 결정된다. Chen and Manning(2014)는 하나의 히든 레이어가 있는 뉴럴 네트워크를 사용하여 매 time step마다 의사결정을 모델링했다. 입력 레이어에는 스택 및 버퍼와 arc label의 집합으로부터 나온 특정 단어, 품사의 태그(tag), arc label의 임베딩이 포함되어 있다.

Tu et al. (2015)는 2개의 은닉층이 있는 더 깊은 모델을 사용함으로써 Chen and Manning(2014)의 연구를 확장시켰다. 그러나 Tu et al. (2015), Chen and Manning(2014) 모두 수작업에 의존한 피처 선택에 의존했으며, 제한된 수의 마지막(latest) 토큰들만 고려했다. Dyer et al. (2015)는 긴 이력을 모델링하기 위한 stack LSTM을 제안했다. LSTM 스택의 말단 포인터는 트리 노드의 스택이 push되고 pop될 때 위치를 변경한다. 전이 기반 의존구문 분석(Transition-based parsing)은 구성성분분석(constituency parsing)에도 적용되었다. Zhu et al. (2013)은 피처(품사정보, 스택과 버퍼의 상위 몇 단어의 구성성분 레이블/constitute label)에 대한 전이 행동(transition action)을 기반으로 한다. Vinyals et al. (2015b)는 레이블의 선형 시퀀스(linear sequence)로 파싱트리를 표현함으로써 이 문제에 seq2seq 학습 기법을 적용했다.

C. 개체명 인식

[표4] 개체명 인식

CoNLL 2003은 네 가지 유형의 개체명(사람, 위치, 조직, 기타 항목)이 중심인 NER 표준 영어 데이터셋이다. NER은 이러한 어휘집(lexicon)이 매우 유용할 수 있는 NLP 문제 가운데 하나다. Collobert et al. (2011)은 지명사전(gazetteer)이 추가된 데이터를 바탕으로 한 뉴럴 네트워크로 경쟁력 있는 결과를 처음으로 달성했다. Chiu and Nichols(2015)는 어휘집(lexicon) 피처, 문자 임베딩, 단어 임베딩을 합치고(concatenate) 이를 bidirectional LSTM 입력값으로 넣었다. 반면 Lample et al. (2016)은 문자와 단어 임베딩에만 의지했다. 방대한 비지도 말뭉치로 사전 학습된 임베딩을 쓰면 어휘집(lexicon) 없이도 좋은 결과를 얻을 수 있었다. Lample et al.(2016)의 비교로 입증된 것처럼, CRF는 품사태깅과 마찬기지로 NER 성능도 끌어올렸다.

Passos et al. (2014)는 skip-gram 모델을 수정하여 관련 어휘집(lexicon)으로부터 정보를 leverage할 수 있는 엔티티 유형 관련 단어 임베딩을 보다 잘 학습하도록 제안했다. Luo et al. (2015)는 엔티티와 엔티티-지식베이스(KB) 연결을 동시에 최적화했다.

D. 의미역 결정

[표7] 의미역 결정

의미역 결정(Semantic Role Labeling, SRL)은 문장에서 술어(predicate)-논항(argument) 구조를 발견하는 것을 목표로 한다. 각 목표 동사(술어)에 대해, 동사의 의미역을 취하는 문장의 모든 구성요소가 인식된다. 전형적인 의미 논항은 행위주, 대상, 도구 등이며 위치, 시간, 방법, 원인 등도 포함된다(Zhou and Xu, 2015). 표7은 CoNLL 2015 및 2012 데이터셋에서 여러 모델의 성능을 보여준다.

전통적인 SRL 시스템은 여러 단계로 구성된다. 파싱 트리를 생성한 뒤 트리의 노드가 주어진 동사의 논항을 나타내는지 판별한 다음, 해당 SRL 태그를 결정한다. 각 분류 과정은 많은 피처를 추출하여 통계 모델(statistical model)로 전달하는 과정을 대개 수반한다. (Collobert et al., 2011)

Tackstrom et al. (2015)는 술어가 주어지면 파싱 트리를 기반으로 하는 일련의 피처로 구성요소의 범위와 해당 술어에 대한 의미역 후보들에 점수를 매긴다. 그들은 효율적인 추론을 위한 동적 프로그래밍(dynamic programming) 알고리즘을 제안했다. Collobert et al., (2011)은 추가적인 참조 테이블의 형태로 제공된 파싱 정보에 의해 보강된 CNN을 사용하여 유사한 결과를 얻었다. Zhou and Xu(2015)는 임의의 긴 문맥을 모델링하기 위해 bidirectional LSTM을 제안했는데, 파싱 트리 정보 없이도 성공적인 것으로 판명되었다. He et al. (2017)은 이 연구를 더욱 확장해 ‘highway connection’을 소개했다.

E. 감성분류

[표5] 감성분류

Stanford Sentiment Treebank(SST) 데이터셋에는 영화 리뷰 웹사이트인 Rotten Tomatoes에서 가져온 문장들이 들어있다. 이 데이터셋은 Pang and Lee(2005)에 의해 제안되었고, 이어서 Socher et al. (2013)에 의해 확장되었다. 주석 체계는 CMU-MOSI라 불리는 감성분석을 위한 새로운 데이터 세트에 영감을 불어넣었다. CMU-MOSI는 감성이 다중모달 설정(multi-modal setup)으로 연구된다(Zadeh et al., 2016).

Socher et al. (2013)과 Tai et al. (2015)는 모두 구성성분분석(constituency parsing) 트리에 의존하는 Recursive Network다. 이들의 차이점은 문장을 모델링할 때 vaniila RNN에 대한 LSTM의 효과를 보여준다. 반면 tree-LSTM은 linear bidirectional LSTM보다 우수한 성능을 보이며, 잠재적인 트리 구조가 자연 문장의 문법적 특성을 더 잘 포착할 수 있음을 의미한다. Kim(2014)와 Kalchbrenner et al. (2014)는 모두 콘볼루션 계층을 사용했다. Kim(2014) 모델은 그림6과 유사하지만, Kalchbrenner et al. (2014)는 k-max 풀링 레이어를 컨볼루션 레이어와 섞어서 계층적인 방식으로 모델을 구성했다.

F. 기계번역

[표6] 기계번역 각 수치는 BLEU 스코어

구문 기반의 통계적 번역(SMT) 프레임워크(Koehn et al., 2003)는 번역모델을 소스 및 타겟 문장에서 일치하는 구문의 번역확률(translation probabilities)로 처리했다(factorize). Cho et al. (2014)는 RNN 인코더-디코더를 사용하여 소스 구문과 해당 대상 구문의 번역확률을 학습하는 모델을 제안했다. 이렇게 구문 쌍을 점수화하는 방식은 번역 성능을 향상시켰다. 반면 Sutskever et al. (2014)는 4개 층의 LSTM seq2seq 모델을 사용하여 SMT 시스템에서 생성된 최상위 1000개 후보 번역본을 다시 채점했다. Wu et al. (2016)은 residual connection뿐 아니라 어텐션 connection이 있는 8개 인코더와 8개 디코더 계층으로 이뤄진 deep LSTM 네트워크를 학습시켰다. Wu et al. (2016)은 BLUE 점수를 최적화하기 위해 강화학습을 사용하여 모델을 학습했다. 그러나 그들은 이 방법으로 BLUE 스코어를 개선한 것은 사람의 번역 품질 평가에는 반영되지 않는다는 걸 알게 됐다. 최근에 Gehring et al. (2017)은 더 나은 병렬화(parallelization)을 위해 convolutional seq2seq를 제안했다. Vaswani et al. (2017)은 self-attention-based 모델을 제안했다.

G. 질의응답

[표8] 질의응답

질의응답 문제는 다양한 형태로 나타난다. 일부는 방대한 지식베이스(KB)를 사용해 오픈도메인 질의에 답변하고, 다른 일부는 몇몇 문장이나 단락을 바탕으로 질의에 답을 한다. Fader et al. (2013)은 전자의 경우로, 이들이 대규모 QA 데이터셋을 대상으로 수행한 실험결과는 표 8에 있다. 각 질의는 단일 관계(single-relation) 쿼리를 통해 답변을 얻을 수 있다. 후자의 연구는 bAbI 관련 실험들이다. 이 데이터셋은 모델이 올바른 답을 내기 위해 여러 가지 관련 사실을 추론할 것을 요구한다. 여기에는 관련 사실을 검색하고 그 이유를 추론하는 모델의 능력을 테스트하는 20개 과제가 포함돼 있다. 각 과제는 기본적인 상호참조(coreference)와 크기 추론(size reasoning) 등과 같이 각기 다른 기술에 중점을 둔다.

단일 관계 쿼리에 응답하는 학습의 핵심 문제는 데이터베이스에서 관련 사실을 찾는 것이다. Fader et al.(2013)은 질의 구문(question paraphrasing) 데이터셋을 기반으로 자연언어의 패턴을 데이터베이스의 개념(엔티티, 관계, 질의 패턴)에 매핑하는 어휘집(lexicon)을 학습함으로써 이 문제를 해결할 것을 제안했다. Bordes et al. (2014)는 질의와 KB 트리플을 dense vector로 임베딩하고, 이들을 내적해 점수를 매겼다.

Weston et al. (2014)는 메모리 네트워크의 프레임워크 내에서 문제를 해결하기 위해 KB를 장기 기억(long-term memory)으로 취급했다. Sukhbaatar et al. (2015)는 bAbI 데이터세트에서 학습 과정에서 모델이 실제 뒷받침하는 팩트에 대해 알지 못하게 함으로써 기존의 메모리 네트워크 모델(Weston et al., 2014)을 개선했다. 반면 Kumar et al. (2015)는 Sukhbaatar et al. (2015)과 Weston et al. (2014)가 메모리를 임베딩했던 것과 같이 neural bag-of-words 모델 대신에 뉴럴 시퀀스(neural sequence) 모델(GRU)을 사용했다.

F. 대화 시스템

[표9] 대화시스템

두 가지 유형의 대화시스템이 개발되었다. 생성기반모델(generative-based model)과 검색기반모델(retireval-based model)이 바로 그것이다. 표 9에 제시된 트위터 대화 트리플 데이터셋(Twitter Conversation Triple Dataset)은 일반적으로 생성 기반 대화 시스템을 평가하는 데 사용되며 트위터 대화 인스턴스가 포함돼 있다. 일반적으로 사용되는 평가척도 하나는 BLEU이다(Papineni et al., 2002). 그러나 자동 평가 척도는 대부분 완전히 신뢰할 수 없고 사람의 평가가 추가적으로 필요하다. Ritter et al. (2011)은 메시지를 적절한 응답으로 “번역”하기 위해 구문 기반의 통계적 기계번역(SMT) 프레임워크를 사용했다. Sordoni et al. (2015)는 문맥에 민감한 RNN 인코더-디코더 프레임워크를 사용하여 SMT에 의해 생성된 1000개 최상의 응답을 재검토했다.

Li et al. (2015)는 흥미롭고 다양한 응답을 생성하기 위해 학습목표를 기존의 로그우도 최대화에서 상호정보량(mutual information) 최대화로 대체해 실험한 결과를 보고했다. 두 실험 모두 4개 층의 LSTM 인코더-디코더 프레임워크에서 테스트됐다. 응답 검색 과제는 후보 응답의 저장소(repository)에서 최상의 응답을 선택하는 것으로 정의된다. 이런 모델은 정답이 k-1개의 무작위 응답과 혼합되는 reall1@k 척도에 의해 평가될 수 있다. 우분투 대화 데이터셋(Ubuntu Dialogue Dataset)은 우분투 문제 해결 관련 온라인 채팅을 여러번 스크래핑해서 만들어졌다(Lowe et al., 2015). Lowe et al. (2015)는 메시지와 응답을 인코딩하기 위해 LSTM을 사용했고, 두 문장 임베딩을 내적해 후보들에 순위를 매겼다.

Zhou et al. (2016)은 Serban et al. (2016)과 유사하게, 문장 수준의 CNN 임베딩 위에 LSTM 인코더를 사용하여 인간 대화의 multi-turn 특성을 보다 잘 활용하는 기법을 제안했다. Dodge et al. (2015)는 과거의 대화가 메모리로 취급되고, 최신 발언이 응답될 ‘질의’로 간주되었던 메모리 네트워크 프레임워크에 문제를 제기했다. 저자들은 문장에 대해 간단한 neural bag-of-word 임베딩을 사용하면 경쟁력 있는 결과를 얻을 수 있음을 보여주었다.

9. 향후 트렌드

딥러닝은 많은 양의 계산과 데이터를 활용하는 기법으로, 수작업 피처 엔지니어링을 거의 하지 않아도 된다(LeCun et al., 2015). 분산표상(distributed representation)을 활용한 다양한 딥러닝 모델들이 NLP 문제의 새로운 최첨단(state-of-the-art) 방법이 되었다. 우리는 이러한 추세가 계속될 것이라 기대한다. 강화학습과 비지도 학습을 활용한 NLP 어플리케이션이 더 많이 나올 것으로 예상된다. 강화학습은 특정 목표를 최적화하기 위해 NLP 시스템을 학습하는 자연스러운 방법을 제시하고, 비지도 학습은 큰 데이터에서 풍부한 언어 구조를 학습할 수 있음을 약속한다. 또한 현실세계에서 언어가 종종 다른 신호(signal)에 근거하거나 상호관련되기 때문에 멀티모달(multimodal) 학습에 대해 더 많은 연구가 이뤄지기를 기대한다.

마지막으로 우리는 내부 메모리(데이터에서 배운 상향적 지식)가 외부 메모리(지식베이스로부터 상속된 지식)로 풍부해진 보다 깊은 학습모델이 나오기를 기대한다. Symbolic AI와 Sub-symbolic AI를 결합하는 것은 NLP에서 자연어이해(NLU)에 이르는 길을 걷는 열쇠가 될 것이다. 머신러닝에 의존하면 과거 경험을 바탕으로 ‘올바른 추측’을 하기가 수월해진다. 왜냐하면 Sub-symbolic 기법은 상관관계(correalation)를 인코딩하고, 의사결정과정은 확률적이기 때문이다. 그러나 자연어이해는 그 이상을 요구한다. Noam Chomsky의 말을 인용하면, “엄청난 양의 데이터를 컴퓨터에 던지고 통계분석을 통해 과학적 발견을 얻지 말라. 이해하는 방식이 아니라 이론적인 통찰력을 가져야 한다.”