이번 글에선 최대엔트로피모델(Maximum Entropy Models, MEMs)을 다루어 보도록 하겠습니다. 이 글은 고려대 강필성 교수님 강의와 역시 같은 대학의 정순영 교수님 강의, 서울대 언어학과 신효필 교수님 저서, 위키피디아 등을 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

자연언어처리 분야에서는 다항로지스틱 회귀(multinominal logistic regression)를 최대엔트로피모델이라 부릅니다. 다항로지스틱 회귀에 대한 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다. 단어 $x$가 주어졌을 때 범주(예 : 품사) $c$가 나타날 확률은 다음과 같습니다.

위 식에서 벡터 $f$는 단어 $x$에 해당하는 자질(feature)들의 모음입니다. 예컨대 자질 벡터의 첫번째 요소는 ‘직전 단어가 명사이면 1, 그렇지 않으면 0’, 두번째 요소는 ‘현재 단어가 동사이면 1, 아니면 0’… 이런 식으로 $f$의 요소값들을 구성합니다.

$w_c$는 자질벡터 $f$만큼의 차원수를 갖는 가중치 벡터입니다. 분류해야 할 범주의 개수만큼 필요합니다. 데이터가 주어지면 그래디언트 어센트 등 기법으로 우도를 최대화하는 방향으로 학습됩니다. 자질벡터의 특정 요소를 집중 반영하거나, 특정 범주에만 높은 확률을 내지 않도록 정규화(regularization)도 수행해 줍니다. 로지스틱 회귀의 학습에 대해서는 이곳, 정규화에 대해서는 이곳을 참고하시면 좋을 것 같습니다.

feature vector

최대엔트로피모델의 핵심은 자질벡터입니다. 연구자의 언어학적 사전지식을 매우 유연하게 반영할 수 있기 때문에, 초기값 설정에만 개입할 수 있는 은닉마코프모델 등과 비교해 최대엔트로피모델의 강점이라고 말할 수 있겠습니다. (물론 자질 요소들을 연구자가 일일이 수작업으로 지정해주어야 하기 때문에 최대 약점으로 꼽히기도 합니다)

예컨대 다음과 같은 문장이 주어졌고, 최대엔트로피모델은 이미 4개 단어에 대한 품사 분류를 마쳤으며, 이번에는 ‘race’를 예측해야 한다고 가정해 보겠습니다. (최대엔트로피모델은 이전 예측결과만 분류에 활용)

Secretariat/NNP is/BEZ expected/VBZ to/TO race tomorrow

현재 단어 $x$는 ‘race’입니다. $x$가 가질 수 있는 범주는 동사, 명사 두 개뿐이라고 연구자가 판단했다고 가정해 보겠습니다. 즉 $C$={VB, NN}입니다. $c$와 $x$가 주어졌을 때 자질벡터의 $i$번째 요소값을 만들어내는 함수 $f_i(c,x)$를 연구자의 언어학적 사전지식을 반영해 다음과 같이 정의했다고 치겠습니다.

자질함수는 6개, ‘race’가 가질 수 있는 범주는 2개라고 정의했기 때문에 자질벡터 $f(c,x)$는 6차원이며, 동사 명사 각각 하나씩 총 2개 만들어 집니다. 다음과 같습니다.

prediction

다항로지스틱 모델의 파라메터($w$)는 이미 학습이 끝났다고 가정하고 자질벡터를 입력으로 예측이 어떻게 이뤄지는지 살펴보겠습니다. 먼저 동사 먼저 보겠습니다. 아래 표에서 자질벡터 요소값과 그에 해당하는 가중치를 곱합니다.

다음은 명사입니다. 위와 동일한 과정을 거칩니다.

이제 ‘race’가 각 범주에 속할 확률을 계산해 보겠습니다. 다음과 같습니다. 따라서 race는 동사로 분류합니다.

Why Maximum Entropy?

최대엔트로피모델은 그럼 왜 이런 이름이 붙은 걸까요? 최대엔트로피모델을 구축하려면 먼저 해당 단어가 가질 수 있는 품사를 가려내고, 자질도 정의해야 하는데요. 예컨대 ‘zzfish’라는 단어의 품사를 예측한다고 가정해 보겠습니다.

연구자가 난생 처음 보는 단어라서 품사 후보들을 가려내기 어렵고 자질과 관련해 ‘zzfish’에 대한 어떤 가정도 할 수 없습니다. 이 경우 해당 언어(영어)에 존재하는 모든 품사 종류(예컨대 45개)가 후보에 오를 것입니다. 모델 예측 결과가 다음 표와 같이 같은 확률을 가진 분포(equiprobable distribution)가 된다면 이상적입니다.

그런데 연구자가 말뭉치를 살펴보니 ‘fish’가 포함된 단어는 그 품사의 종류가 명사(NN), 형용사(JJ), 복수형 명사(NNS), 동사(VB)라는 사실을 알게 됐다고 가정해 보겠습니다. 연구자가 품사 후보를 이같이 정한다면 ‘zzfish’의 품사는 이 네 가지 중 하나가 될 것입니다. 하지만 추가 가정이 없기 때문에 모델은 넷 사이에서는 같은 확률로 예측하기를 기대합니다.

말뭉치를 보니 ‘zzfish’ 10개 중 8개는 명사라고 칩시다. 이걸 보고 연구자는 현재 예측할 단어 $x$가 ‘zzfish’이고, $c$가 명사나 복수형 명사이면 1로 하는 자질함수를 정의했습니다. 따라서 우리는 품사 분포는 다음과 같이 바뀌기를 기대합니다.

우리가 가진 말뭉치에서 ‘zzfish’에 대한 정보를 최대한 다 뽑아 냈다고 칩시다. 그런데 연구자가 영어 전체 말뭉치를 살펴보니 동사는 평균적으로 1/20의 확률로 나타났다는 사실을 알게 됐습니다. 그러면 분포가 또 바뀝니다.

엔트로피란 불확실성 정도를 나타내는 지표입니다. 위 네 개 케이스에 대해 엔트로피(밑이 2인 log로 계산)를 구하면 각각 5.491, 2, 1.722, 1.6842입니다. 균등한 분포일 때 엔트로피가 제일 높고, 분포가 불균등해질 수록 엔트로피가 점점 낮아지는 것을 확인할 수 있습니다.

그런데 위 과정을 천천히 살펴보면 연구자가 말뭉치를 관찰하면서 알게 된 사실이 범주 후보나 자질 함수의 형태로 추가되면서 점점 불균등한 분포를 띄게 됐습니다. 다시 말해 추가적인 정보나 전제가 없다면 최대엔트로피모델은 균등한 분포를 전제하고, 이는 최대 엔트로피를 지니게 된다는 이야기입니다.

이번 글에서는 해싱(hashing)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 스택오버플로우와 고니 님의 블로그를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.

해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다. 아래 그림은 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈습니다. 예시의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 모두 ‘02’로 매핑해 해시충돌을 일으키고 있습니다.

##해시테이블의 장점

해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다.

색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있습니다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 01이라는 색인이 생성됩니다.

해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 $O(1)$을 지향합니다.

해시테이블을 다른 자료구조와 비교해보겠습니다. 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 $O(\log{n})$입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 $O(1)$이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵습니다.

해시는 보안 분야에서도 널리 사용된다고 합니다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문입니다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있습니다.

다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 합니다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠습니다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것입니다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어집니다.

해시테이블

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 합니다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)입니다. 다음 그림과 같습니다.

위 예시 그림 각 버킷에는 데이터가 다음과 같이 저장됩니다.

키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 합니다. 다음 그림과 같습니다.

Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다는 겁니다. 하지만 전체 키(unverse of key)가 실제 사용하는 키(actucal key)보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성이 크게 떨어집니다. 위 그림처럼 1, 9, 4, 0, 7, 6을 위한 버킷은 굳이 만들어놓을 이유가 없습니다.

보통의 경우 Direct-address table보다는 “해시테이블 크기($m$)가 실제 사용하는 키 개수($n$)보다 적은 해시테이블”을 운용합니다. 다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문입니다. 이 때 $n/m$을 load factor($α$)라고 합니다. 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가를 나타내는 지표입니다. Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생합니다.

해시충돌 문제를 해결하기 위해 다양한 기법들이 고안됐습니다. chining은 해시테이블의 크기를 유연하게 만들고, open addressing은 해시테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는 데 관심을 둔 구조입니다. 이뿐 아니라 해시함수를 개선하는 접근도 있습니다. 차례대로 살펴보겠습니다.

chaining

해시충돌 문제를 해결하기 위한 간단한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것입니다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하기 때문에 체인이라는 말이 붙은 것 같습니다. 유연하다는 장점을 가지나 메모리 문제를 야기할 수 있습니다. 아래 그림과 같습니다.

위 예시 그림의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 같은 해시값(152)으로 매핑하고 있습니다. 이 경우 해당 해시값에 대응하는 동일한 버킷에 두 개 데이터를 저장해 둡니다. 데이터를 위 그림처럼 연결리스트로 저장해 둘 경우 최근 데이터는 연결리스트의 head에 추가합니다(이 경우 $O(1)$, tail에 저장할 경우 $O(n)$이 됨, 자세한 내용은 이곳 참고)

삽입, 탐색, 삭제 연산과 계산복잡성

chaining 방식의 계산복잡성을 따져보겠습니다. 삽입(insertion), 탐색(search), 삭제(delete) 세 가지가 있습니다. 본격적인 분석에 앞서 가정을 하나 하겠습니다. 해시테이블의 크기가 $m$, 실제 사용하는 키 개수가 $n$, 해시함수가 키들을 모든 버킷에 균등하게 할당한다고 가정하면, 버킷 하나당 $n/m=α$개의 키들이 존재할 것입니다. 예컨대 위 그림 예시에서 2560개의 키에 해당하는 데이터를 저장한다면 버킷 하나당 10개 데이터가 있다는 얘기입니다.

삽입의 계산복잡성입니다. 예컨대 위 예시그림의 해시함수가 254로 매핑하는 ‘Mark Zuckerberg’의 전화번호를 새로 추가한다고 칩시다. ‘Mark Zuckerberg’라는 키를 해시값 254로 매핑하는 데 $O(1)$이 듭니다. 해당 해시값에 해당하는 연결리스트의 head에 이를 추가하는 데 $O(1)$이 듭니다. 따라서 삽입의 계산복잡성은 둘을 합친 $O(1)$입니다.

이번엔 탐색을 살펴보겠습니다. 두 가지로 나눠서 생각해 보겠습니다.

쿼리 키값에 해당하는 데이터가 해시테이블에 존재하지 않는 경우(unsuccessful search)입니다. 예컨대 위 예시그림의 해시함수가 152로 매핑하는 ‘Steve Jobs’의 전화번호를 탐색한다고 가정해 봅시다. 이 경우 키를 해시값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 $α$개를 모두 탐색해봐야 존재하지 않는다는 사실을 알 수 있습니다. 따라서 unsuccessful search의 계산복잡성은 $O(1+α)$가 됩니다.

이번엔 쿼리 키값에 해당하는 데이터가 해시테이블에 존재하는 경우(successful search)입니다. 예컨대 ‘Sandra Dee’의 전화번호를 위와 같은 해시테이블에서 탐색한다고 가정해 봅시다. 이를 위해선 ‘Sandra Dee’를 해시값(152)으로 바꾸고 버킷 요소들 가운데 ‘Sandra Dee’에 해당하는 데이터가 있는지 탐색해봐야 할 겁니다.

Big O notation의 계산복잡성을 따져보기 위해선 최악의 경우를 고려해야 합니다. 해당 버킷의 tail에 값이 있는 경우일 겁니다. 데이터가 해시테이블에 존재한다고 가정했으므로 버킷 내 $α$개 요소 가운데 반드시 찾고자 하는 값이 존재합니다. $α-1$개를 비교했는데도 원하는 값을 찾지 못했다면 tail값은 따져볼 필요도 없이 찾고자 하는 값이 됩니다.

그런데 버킷의 요소들 평균이 $α$개일 때 successful search는, 요소가 $α-1$개인 버킷을 탐색했는데 찾는 값이 없어서(unsuccessful search), 해당 버킷에 쿼리에 해당하는 데이터를 삽입하여 결과적으로 해당 버킷의 요소 수를 $α$개로 만드는 계산량과 동일합니다. unsuccessful search의 계산복잡성은 $O(1+α)$이므로, successful search의 계산복잡성 또한 이와 같은 $O(1+α)$가 됩니다.

삭제의 계산복잡성은 탐색과 본질적으로 비슷합니다. 우선 쿼리 키값을 해시값으로 매핑하고($O(1)$), 해당 버킷 내에 키값에 해당하는 데이터가 있는지 탐색($O(α)$)해야 하기 때문입니다. 물론 탐색 연산과 비교해 삭제에 드는 계산도 추가적으로 필요하나, 연결리스트로 해시테이블을 구현할 경우 삭제 연산의 계산복잡성은 $O(1)$이므로 무시할 만한 수준입니다.

chaining에서 삽입을 제외한, 탐색/삭제의 계산복잡성은 버킷당 요소 개수의 평균 $α$가 좌지우지하는 구조입니다. 최악의 경우 한 버킷에 모든 데이터가 들어있어 $O(n)$이 될 수 있습니다. 하지만 데이터의 개수가 해시테이블 크기의 두 세배쯤($α$가 2~3)만 되어도 탐색, 삭제는 $O(1)$이 됩니다.

open addressing

open addressing은 chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블입니다. 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing이라는 이름이 붙은 것 같습니다. 메모리 문제가 발생하지 않으나 해시충돌이 생길 수 있습니다.

예컨대 해시함수를 ‘키값을 7로 나눈 나머지’로 정의했다고 칩시다. 그리고 나서 키 50, 700, 76, 85, 92, 73, 101순으로 데이터를 저장한다고 가정해 봅시다. 다음 그림과 같습니다.

위 예시에서 주목할 부분은 85부터입니다. 85를 7로 나눈 나머지는 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있으므로, 다음 버킷(2)에 저장해 둡니다. 92를 7로 나눈 나머지 역시 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있고, 그 다음 해시값 2 버킷에 85가 있으므로, 92를 3번 버킷에 저장합니다. 73, 101 역시 자신의 버킷에는 이미 주인이 있으므로 빈 버킷에 할당합니다.

삭제, 삽입, 탐색

해시함수가 ‘키값을 8로 나눈 나머지’이고 10, 18, 26 순으로 해시테이블에 삽입한다고 가정해 보겠습니다. 세 숫자 가운데 첫번째 입력값 10을 제외한 18, 26은 원래 버킷(2) 말고 각각 다음(3), 다음다음(4) 버킷에 저장하는 것이 open addressing의 방식입니다.

위 표에서 18을 삭제해 보겠습니다. 18의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 18이 여기에 있군요. 지웁니다. 다음과 같습니다.

위 표에서 26을 탐색해 보겠습니다. 26의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 그런데 비어 있습니다. 별도로 조치하지 않으면 알고리즘은 ‘2번 해시값 1칸 옆인 3에 저장된 데이터가 없구나, 해시충돌이 발생한 적이 없다는 얘기네, 탐색을 끝내야 겠다’고 판단할 수 있습니다.

이를 해결하기 위해 삭제 연산 때 아래처럼 별도로 표시를 해둡니다.

probing

open addressing은 그 구조상 해시충돌 문제가 발생할 수 있습니다. 앞선 예시에서 살펴봤듯 특정 해시값에 키가 몰리게 되면 open addressing의 효율성이 크게 떨어집니다. 해시충돌은 탐사(probing) 방식으로 해결할 수 있습니다. 탐사란 삽입, 삭제, 탐색을 수행하기 위해 해시테이블 내 새로운 주소(해시값)를 찾는 과정입니다.

선형 탐사(Linear probing)는 가장 간단한 방식입니다. 앞선 예시에 해당합니다. 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)합니다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스합니다.

그런데 탐사 이동폭이 고정돼 있는 선형탐사는 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다고 합니다. 예컨대 아래 그림처럼 52~56까지 데이터가 저장돼 있고 임의의 키의 최초 해시값이 52라면 탐사를 네 번 수행하고 나서야 원하는 위치를 찾을 수 있습니다. 모두 빈 버킷이었다면 단 한 번의 해시만으로도 저장할 수 있었을 텐데 말이죠.

제곱 탐사(Quadratic probing)은 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다는 특징이 있습니다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 $1^2$칸을 옮깁니다. 여기에서도 충돌이 일어나면 이번엔 $2^2$칸, 그 다음엔 $3^2$칸 옮기는 식입니다.

하지만 제곱탐사는 여러 개의 서로 다른 키들이 동일한 초기 해시값(아래에서 initial probe)을 갖는 secondary clustering에 취약하다고 합니다. 초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어집니다. 예컨대 아래 그림에서 초기 해시값이 7인 데이터를 삽입해야 할 경우 선형 탐사 기법보다 성큼성큼 이동하더라도 탐사를 네 번 수행하고 나서야 비로소 데이터를 저장할 수 있습니다.

이중해싱(double hashing)은 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법입니다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화할 수 있습니다.

• 해시값을 반환해주는 $h_1$을 ‘3으로 나눈 나머지’, 탐사 이동폭을 결정해주는 $h_2$를 ‘5로 나눈 나머지’라고 둡시다. 예컨대 키가 3, 6인 데이터의 최초 해시값은 모두 0이 됩니다. 하지만 키가 3인 데이터의 탐사이동폭은 3, 6인 데이터의 이동폭은 1로 달라집니다. 반대로 키가 6, 11인 데이터의 탐사이동폭은 모두 1이 됩니다. 하지만 키가 6인 데이터의 최초 해시값은 0, 11은 2로 달라집니다.
• 단 제수(위 예시에서 3, 5)는 서로소(relatively prime, 공약수가 1뿐)이어야 원하는 효과를 볼 수 있습니다.

계산복잡성

open addressing은 chaining과 달리 해시테이블의 크기($m$)가 고정돼 있으므로 $n$개 데이터를 모두 저장하려는 경우 Load Factor $α=n/m$는 1과 같거나 작다고 가정합니다. 다시 말해 open addressing은 해시테이블에 데이터가 꽉 차지 않는다는 걸 전제로 한다는 이야기입니다. 아울러 open addressing에 적용된 해시함수는 키들을 모든 버킷에 균등하게 할당한다고 가정하고 계산복잡성을 분석합니다.

open addressing 탐색의 계산복잡성은 탐사(probing) 횟수에 비례합니다. 따라서 탐색 계산복잡성을 따질 때 핵심은 ‘탐사 횟수의 기대값’입니다. successful search와 unsuccessful search의 탐사횟수 기대값은 각각 다음과 같다고 합니다.

[\begin{align} successful\quad search\quad &:\quad \frac { 1 }{ \alpha } \ln { \frac { 1 }{ 1-\alpha } } \ unsuccessful\quad search\quad &:\quad \frac { 1 }{ \alpha } \end{align}]

해시테이블에 데이터가 반만 차 있다($α=0.5$)고 가정하면 successful search와 unsuccessful search의 탐사횟수 기대값은 각각 1.387, 2가 됩니다. 다시 말해 최초로 해시값을 만드는 1회를 뺀 나머지, 즉 한번 정도만 추가 탐사하면 원하는 데이터를 대체로 찾을 수 있다는 얘기입니다. 반대로 $α=0.8$이라면 탐사횟수 기대값은 8.047과 5로 치솟게 됩니다.

요컨대 open addressing 탐색 연산의 계산복잡성은 $α$에 크게 영향을 받는 구조입니다. 따라서 해시테이블에 데이터가 어느 정도 차게 되면 해시테이블 크기 $m$을 적절하게 늘려주고 처음부터 다시 해싱을 하는 것이 좋다고 합니다. 삭제와 삽입 연산 역시 탐사 횟수가 중요하기 때문에 해시테이블 크기에 신경을 써주어야 합니다.

해시함수

이번엔 해시함수로 해시충돌을 완화하는 방법을 살펴보겠습니다. 해시테이블의 크기가 $m$이라면, 좋은 해시함수는 임의의 키값을 임의의 해시값에 매핑할 확률이 $1/m$이 될 겁니다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라는 이야기입니다.

division method

나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수입니다. 숫자로 된 키를 해시테이블 크기 $m$으로 나눈 나머지를 해시값으로 반환합니다. $m$은, 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 합니다. 다시 말해 해시함수 특성 때문에 해시테이블 크기가 정해진다는 단점이 있다는 이야기입니다.

multiplication method

숫자로 된 키가 $k$이고 $A$는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다. $m$이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 합니다. 나눗셈법보다는 다소 느리다고 합니다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.

[h\left( k \right) =\left( kA\quad mod\quad 1 \right) \times m]

universal hasing

다수의 해시함수를 만들고, 이 해시함수의 집합 $H$에서 무작위로 해시함수를 선택해 해시값을 만드는 기법입니다. $H$에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 $1/m$로 만드려는 것이 목적입니다. 다음과 같은 특정 조건의 해시함수 집합 $H$는 $1/m$으로 만드는 게 가능하다고 수학적으로 증명됐습니다.

• 해시테이블의 크기 $m$를 소수로 정한다.
• 키값을 다음과 같이 $r+1$개로 쪼갠다 : $k_0$, $k_1$,…, $k_r$
• 0부터 $m-1$ 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키값의 개수($r+1$)만큼 반복해서 뽑는다. 이를 $a=[a_0, a_1,…,a_r]$로 둔다. 따라서 $a$의 경우의 수는 모두 $m^{r+1}$가지이다.
• 해시함수를 다음과 같이 정의한다 : $h_a(x)=Σ_{i=0}^r{(a_ik_i\mod\ m)}$
• $a$가 $m^{r+1}$가지이므로 해시함수의 집합 $H$의 요소 수 또한 $m^{r+1}$개이다.

위와 같은 조건에서는 키가 동일하더라도 $a$가 얼마든지 랜덤하게 달라질 수 있고, 이에 해당하는 해시함수 $h_a$ 또한 상이해지기 때문에 $H$는 유니버설 함수가 됩니다.

이번 글에서는 한국어의 문장유형과 종결어미에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

화행

발화행위(speech act, 화행)란 말을 통해 이루어지는 행위를 가리킵니다. 우리가 말을 할 때에는 단순히 말하기라는 행위만을 하는 것이 아니라 말로써 그 이상의 여러 다양한 행위를 하는데, 이러한 행위를 가리켜 화행이라고 합니다. 예문을 보겠습니다.

(강도가) 나에게 총이 있다 : 협박

(친구에게) 음식에 거미가 있어 : 경고

(부하직원에게) 어린애도 이거보단 잘 쓰겠다 : 모욕

(옆 사람에게) 지금 몇 시인지 아세요? : 요청

문장유형

문장유형은 화행 중 특별히 자주 쓰이고 긴요해 그 구별이 문법적 장치를 통해 나타난 것을 말합니다. 가령 진술, 질문 등의 화행이 관습적으로 각기 특정한 문법적 형식에 의해 표시된다면 그러한 문장은 일정한 문장 유형에 속한다고 할 수 있습니다. 학교문법에서는 평서문, 의문문, 명령문, 청유문, 감탄문 다섯가지 문장 유형을 제시하고 있습니다.

어디까지 문장유형으로 설정할지는 학자마다 견해가 다를 수 있습니다. 이 때문에 문장유형을 인정하는 데에는 일정한 기준이 필요합니다. 두 가지를 들 수 있겠습니다. 첫번째는 간접인용절을 만들어서 확인해보는 것입니다. 한국어 간접인용절은 상대높임이나 화자의 태도 등이 삭제되고 순수하게 문장유형이 나타나기 때문에 좋은 방법입니다. 예문을 보겠습니다.

(1) 꽃이 예쁘네요.

(2) 내 친구가 꽃이 예쁘다고 말했다.

(1)에서 ‘네’는 화자의 태도(놀람), ‘요’는 상대높임을 표시하고 있습니다. (1)을 간접인용절로 바꾼 (2)에서는 이 모두 사라지고 ‘꽃이 예쁘다’라고만 실현이 됐습니다. 이러한 경우라면 평서문을 문장유형의 하나로 인정할 수 있는 근거가 될 것입니다.

두번째 기준은 상태높임법의 용례를 살피는 것입니다. 한국어 상대높임에는 높임, 중간, 안높임의 세 화계가 있는데, 세 화계에 두루 나타나는 유형을 문장유형으로 삼아보자는 취지입니다. 이같은 두 가지 기준에 따라 한국어 문장유형을 꼽아보면 다음 표와 같습니다.

이 두 기준에 따르면 감탄문은 별도의 문장유형으로 인정할 수 없습니다. 예문을 보겠습니다.

간접인용 구성 : 꽃이 핀다고 했다.

높임 등급 : ?

중간 등급 : 꽃이 피는구려.

안높임 등급 : 꽃이 피는구나.

‘꽃이 피는구나’를 간접인용 구성으로 만들면 ‘꽃이 핀다’가 되어 평서문과 구별할 수 없게 됩니다. 상대높임 가운데 높임 등급에 해당하는 어미가 존재하지 않습니다. 이 때문에 감탄문은 평서문의 하위 유형으로 분류하는 것이 더 적절할 듯합니다.

종결어미

종결어미는 다음과 같은 속성을 지니는 문법부류입니다.

• 문장의 맽 끝에 붙음
• 상대높임법을 표시
• 평서문, 의문문, 명령문, 청유문과 같은 문장의 유형을 결정
• 화자의 심리적 태도를 나타냄

평서문

평서문은 화자가 청자에게 어떠한 생각이나 감정을 진술하여 단순히 전달하고자 하는 문장 종결법이 나타난 문장유형을 가리킵니다. 평서문에는 좁은 의미의 평서문 외에 감탄문, 경계문, 약속문이 포함됩니다. 이미 언급했듯이 이들은 간접인용절에서 평서문 어미 ‘-다’로 합류될 수 있다는 특징을 보이기 때문입니다. 다음 예문과 같습니다.

좁은 의미의 평서문 : 날씨가 추웠다 > 그는 날씨가 춥다고 말했다.

감탄문 : 꽃이 예쁘구나 > 그는 꽃이 예쁘다고 말했다.

경계문 : 그 길로 가다가 불량배를 만날라 > 그는 내가 그 길로 가다가 불량배를 만나겠다고 말했다.

약속문 : 다시는 오지 않으마. > 그는 다시는 오지 않겠다고 말했다.

감탄문은 이미 언급했으므로 경계문과 약속문을 따로 보겠습니다. 경계문은 흔히 명령의 하위 부류로 간주되나, 과거시제, ‘이다’와 결합할 수 있고, ‘말다’ 부정과 결합하지 않으므로 평서문의 일종으로 보는 것이 합당하다고 합니다. 다음 예문과 같습니다.

과거시제와 결합 : 벌써 도착했을라.

‘이다’와 결합 : 잘 봐라. 가짜일라.

약속을 나타내는 어미로는 ‘-마, -ㄹ게, -ㅁ세, -리다’가 있습니다. 하지만 이들 어미는 약속 이외에 기능에도 널리 쓰이므로 약속문이라는 독자적인 문장유형을 세우기 어렵다는 특징 때문에 평서문의 하위 유형으로 분류됩니다.

평서문 어미

평서문 어미의 종류는 다음과 같습니다.

위 표에서 ‘-네’는 해체와 하게체 모두 속해 있습니다. 형태는 같지만 다른 어미로 보는 것이 적절할 듯 합니다. 예문을 보겠습니다.

해체 : 너, 정말 예쁘네.

하게체 : 자네, 조금만 기다리게. 곧 가겠네.

위 표에서 ‘-군, -구나, -구먼, -구려, -어라, -다니’는 감탄문 어미입니다. 감탄문을 평서문의 하위 유형으로 분류했기 때문에 위 표에도 감탄문 어미가 포함됐습니다. ‘-어라’의 경우 명령문 어미로도 쓰이는데 이 또한 형태는 같지만 다른 어미로 보는 것이 적절할 듯합니다. 국어사적 연구에 따르면 감탄의 ‘-어라’와 명령의 ‘-어라’는 그 기원이 다르다고 합니다. 한편 위 표에서 ‘-ㄹ라’는 경계문 어미, ‘-마, -ㄹ게, -ㅁ세, -리다’는 약속문 어미입니다.

-거든, -지

‘-거든’과 ‘-지’는 화자가 이미 알고 있거나 당연한 지식임을 표시한다는 공통점이 있습니다. 이 가운데 ‘-거든’은 화자는 알고 있지만 청자가 잘 모르는 지식임을 함의합니다.

세종대왕이 한글을 만드셨거든. (세종대왕이 한글을 만드신 사실을 화자는 알고 있지만 청자는 잘 모를 거라고 전제하고 진술한 문장)

반면 ‘-지’는 관련 명제가 청자의 이견이 기대되지 않는 것(동의할 것)임을 함의합니다. 즉 청자가 그 사실을 알고 있다고 화자가 전제하는 경우(기지 가정)에 쓰입니다.

냉장고에 있던 아이스크림 네가 먹었지? (냉장고에 있는 아이스크림을 청자가 먹었으리라고 화자와 청자가 모두 전제한 상태에서 자연스러움)

‘-지’는 명령문이나 청유문에서는 부드럽게 권유하는 뜻이 담깁니다.

힘들 텐데 그만 좀 쉬지.

우리랑 같이 가지.

다만 ‘-지’는 ‘-잖-‘보다는 기지 가정의 의미가 약한 편입니다. 아래 예문에서는 ‘화자가 어제 병원에 간 사실을 청자도 알고 있을 것’이라는 전제가 (2)에서 두드러집니다.

(1) 내가 어젠 아파서 병원에 갔지.

(2) 내가 어젠 아파서 병원에 갔잖아.

-네, -구나

‘-네’와 ‘-구나’는 화자가 새로 알게 된 지식임을 표시합니다. ‘-네’는 발화 시점에서 지각이나 근거가 분명한 추론을 통해 알게 된 명제를 표시합니다. ‘-구나’는 인식 시점에 구애받지 않고 지각이나 추론, 전문(들어서 알게 된 사실)을 통해 알게 된 명제를 표시합니다.

지각 : 비가 {오네/비가 오는구나}.

근거가 분명한 추론 : (철수가 공부하고 있던 방에 들어가서 철수와 그의 소지품이 사라진 것을 보고) 철수 {갔네/갔구나}!

근거가 분명하지 않은 추론 : (가) 어제 철수 씨가 계속 전화했어요. (나) 급한 일이 {*있었네/있었구나}.

전문 : (가) 합격자 명단 보니까 철수도 있더라. (나) 철수도 {*합격했네/합격했구나}.

이번 글에서는 한국어의 보조사 개념과 그 종류에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

보조사와 ‘세로관계’

보조사란 명사구 뒤에 붙어 특정한 의미를 덧붙이는 조사를 가리킵니다. 격조사와 달리 보조사는 조사의 형태만으로는 선행 명사구의 문장 성분을 짐작할 수 없습니다. 예문을 보겠습니다.

(1) 진이는 음식도 잘해.

(2) 음식도 맛있어.

(1)에서 ‘음식도’는 서술어의 목적어로 쓰였습니다. (2)에서는 주어로 사용됐습니다. 하지만 (1), (2) 모두 also 정도의 의미가 추가된 점을 확인할 수 있습니다. 보조사는 이처럼 문장 바깥에 있는 다른 요소와의 의미 관계를 표시합니다. 다른 예문을 보겠습니다.

(3) 진이는 합격했어. (민이? 순이?)

(4) 진이만 합격했어. (민이X, 순이X)

(5) 진이도 합격했어. (민이O, 순이O)

(3)~(5) 문장을 발화한 화자는 ‘민이’와 ‘순이’를 전제하고 말했다고 가정해 봅시다. (3)처럼 썼다면 ‘민이랑 순이는 모르겠는데, 진이는 합격했어’ 정도의 의미를 가집니다. (4)의 경우 ‘민이랑 순이는 떨어졌는데, 진이는 합격했어’ 정도의 뉘앙스입니다. (5)는 ‘민이, 순이, 진이 모두 합격했어’ 정도의 느낌입니다.

(3)~(5) 모두 ‘민이’나 ‘순이’를 직접 언급하지는 않았지만 한국어를 모국어로 하는 청자라면 특별한 부가 정보 없이도 위와 같은 해석을 충분히 할 수 있습니다. 이처럼 보조사는 문장 바깥에 있는 다른 요소와의 관계를 표시해 줍니다.

문장을 왼쪽에서 가로로 쓴다고 할 때 문장에서 언급되지 않는 요소(민이, 순이)는 해당 단어(진이)의 아래로 붙는다는 점에 착안해, 보조사는 세로관계를 나타낸다고 설명하는 경우가 많습니다. 반면 격조사는 문면에 실현된 명사구나 절이 그것의 핵과 어떤 관계에 있는지 가로관계를 나타냅니다.

보조사의 종류

보조사에는 체언, 부사, 연결형 등에 두루 쓰이는 통용보조사, 주로 종결형 뒤에 쓰이는 종결보조사 둘로 나뉩니다. 다음 예문은 통용보조사 ‘은/는’이 쓰인 예시입니다. 각각 주어, 부사어, 본용언, 어근에 붙어서 대조의 의미를 더하고 있습니다.

밥은 먹었어.

철수가 일을 빨리는 한다.

내가 준 책을 읽어는 봤니?

이 집은 깨끗은 하지만 너무 낡았다.

다음은 종결보조사가 쓰인 예시입니다.

그걸 어디 쓰게요.

사고 싶다마는 돈이 없구나.

봄이 돌아왔네그려.

좋아 보이는구먼그래.

앞으로 통용보조사 몇 가지를 살펴보겠습니다.

은/는

‘은/는’은 대조(소극적 배제)를 나타내는 통용보조사입니다. 다른 것을 한편에 전제로 깔고 그쪽과 대조적으로 이야기를 한다는 의미를 나타냅니다. 화자는 가능한 자매 항목에 대해 중립적인 입장을 취합니다.

이 꽃은 그늘에서는 잘 자란다. (양지, 숲, 늪지 등에 대해서는 모르겠음)

(옷가게에서 옷을 고르다가) A: 이거 어때? B: 예쁘기는 하다. (값이 적당한지, 내게 어울리는지 등에 대해서는 모르겠음)

‘은/는’은 문장의 주제를 표시해 줍니다. 주제는 한 문장에서 설명되는 내용의 대상이 되는 부분으로, 대체로 “~로 말할 것 같으면” 정도의 의미로 풀이됩니다. 주제에 관한 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

진이는 정말 착해.

그 책은 나도 읽어 봤어.

어제는 하루 종일 집에서 쉬었어.

진이는 내가 벌써 저녁을 사 줬어.

향기는 장미가 좋지.

만

다른 것은 말고 유일하게 그것이 선택됨을 나타내는 보조사입니다.

이 꽃은 그늘에서만 잘 자란다. (양지, 숲, 늪지 등에서는 잘 자라지 않는다)

도

다른 것에 더해 그것이 포함됨을 나타내는 보조사입니다.

이 꽃은 그늘에서도 잘 자란다. (양지, 숲, 늪지 등에서도 잘 자란다)

조차

사태 성립 확률이 가장 높은 것이 선택되었음을 나타내는 보조사입니다. 주로 부정문에 사용되어, 사태의 성립 확률이 높은데도 성립되지 않음을 표시합니다.

진이는 {덧셈, 뺄셈조차/?까지/?마저} 할 줄 모른다.

위 예문에서 ‘덧셈, 뺄셈’은 사람이라면 보통 누구나 할 수 있을 것으로 기대되는 행위로 쓰였습니다. 이런 맥락에서라면 ‘조차’가 가장 잘 어울립니다.

마저

사태의 성립 확률이 가장 낮은 것이 선택되었음을 나타냅니다. 주로 긍정문에 사용되어 사태의 성립확률이 낮은데도 성립함을 표시합니다. 주로 그 결과가 화자에게 불리할 때 쓰입니다.

브루투스, 너마저 나를 배신하다니!

그 깍쟁이가 내 ?선물마저 사 왔다.

까지

사태의 성립 확률이 가장 낮은 것이 선택되었음을 나타냅니다. 주로 긍정문에 사용되어 사태의 성립확률이 낮은데도 성립함을 표시합니다. 그 결과가 화자에게 불리하지 않을 때도 쓰입니다.

브루투스, 너까지 나를 배신하다니!

그 깍쟁이가 내 선물까지 사 왔다.

미국 스탠포드대학의 Stanford NLP group은 자연어처리 분야에서 손꼽히는 연구실입니다. Chistopher Manning 교수는 1999년 스탠포드에 부임한 이래 stanford NLP group을 이끌면서 많은 업적을 쌓아 왔습니다. 특히 Foundations of Statistical NLP(1999), Introduction to Information Retrieval(2008) 등이 유명합니다. 최근 공부하시는 분들은 CS224n 강의가 익숙할텐데요. 강의자인 Richard Socher 또한 그가 가르친 20명의 박사 가운데 열네번째 제자입니다.

그런 그가 지난 10월 20일 서울 우면동 삼성전자R&D캠퍼스에서 열린 ‘삼성AI포럼2017’에 참석해 강연을 했습니다. 실제로 이날 행사장엔 청중 1000여 명이 몰려 그의 영향력을 실감할 수 있었습니다. 조금 늦게 도착한 저는 통로 사이 바닥에 앉아 강의를 들었…

이 글은 이날 Manning이 한 강연을 제가 이해하는 수준에서 정리한 것입니다. 이 글에 쓰인 그림은 기본적으로 Manning의 발표 원고에서 따 왔으며, 이외의 그림은 출처를 별도로 표기하였습니다. 본 블로그에 강연 내용과 관련된 글이 있다면 해당 단어에 링크로 연결해 두었습니다. 그의 육성 강연을 들을 수 있는 기회를 주신 삼성 관계자 여러분들께 진심으로 감사드립니다. 그럼 시작하겠습니다.

BiLSTM Hegemony

이날 Manning 강연의 핵심은 다음과 같습니다. task가 무엇이든지 간에 어텐션(attention)이 적용된 BiLSTM 모델이 자연어 처리 분야에서 최고 성능을 낸다는 이야기입니다.

The de facto consensus in NLP in 2017 is that no matter what the task, you throw a BiLSTM at it, with attention if you need information flow, and you get great perfomance!

실제로 이날 Manning이 소개한 stanford NLP group의 최신/최고 연구성과가 모두 BiLSTM이 적용된 모델이었습니다. 그가 언급했던 것처럼 가히 ‘BiLSTM Hegemony’라 할 만 합니다. 그렇다면 BiLSTM과 attention이 대체 뭐길래, 수십년동안 NLP를 연구해온 그가 침이 마르도록 칭찬하는 것일까요? 차례대로 살펴보겠습니다.

BiLSTM with attention

vanilla RNN 구조는 다음과 같습니다. gradient vanishing/exploding 문제에 취약합니다. 아래 그림(출처 : Oxford Deep NLP 2017)에서 $h_1$의 그래디언트를 구하려면 체인룰에 의해 빨간색 선에 해당하는 그래디언트를 계속 곱해주어야 하기 때문입니다.

LSTM(Long Short Term Memory)은 cell state를 도입해 그래디언트 문제를 해결하고자 합니다. Manning은 Hochreiter&Schmidhuber(1999), Cho et al.(2014)가 제안한 셀을 LSTM이라고 명명하고, 이날 강연에서 “LSTM는 직전 시점 정보와 현 시점 정보를 더해줌으로써 그래디언트가 효과적으로 흐를 수 있게 한다”고 강조했습니다.

vanilla Seq2Seq 모델은 다음과 같습니다. 소스 문장을 벡터화하는 인코더(encoder)와 인코딩된 벡터를 타겟 문장으로 변환하는 디코더(decoder) 둘로 구성돼 있습니다. 이 때 인코더, 디코더는 LSTM 셀을 씁니다.

하지만 문장 길이가 길고 층이 깊으면, 인코더가 압축해야할 정보가 너무 많아서 정보 손실이 일어나고, 디코더는 인코더가 압축한 정보를 초반 예측에만 사용하는 경향을 보입니다. Manning은 “이 때문에 인코더-디코더 사이에 ‘bottle-neck 문제’가 발생한다”고 언급했습니다. 이에 디코더 예측시 가장 의미 있는 인코더 입력에 주목하게 만드는 어텐션(attention) 매커니즘이 제안됐습니다.

아울러 앞에서 뒤, 뒤에서 앞, 모두 고려하는 양방향(bidirectional) 네트워크 또한 성능 개선에 도움이 된다고 합니다. 아래 그림은 LSTM 셀을 쓰고, 인코더에 양방향 네트워크, 디코더 예측시 어텐션 매커니즘이 적용된 ‘BiLSTM with attention’을 개념적으로 나타냈습니다.

BiLSTM with attention은 특히 기계번역에서 좋은 성능을 내 주목을 받았습니다. Manning은 이날 강연에서 그 비결 네 가지를 다음과 같이 설명했습니다.

• 종단간(End-to-end) 학습 : 출력값(output)에 대한 손실을 최소화하는 과정에서 모든 파라메터들이 동시에 학습된다.
• 분산표상(distributed representation) 사용 : 단어와 구(phrase) 간 유사성을 입력벡터에 내재화해 성능을 개선했다.
• 개선된 문맥 탐색(exploitation) : LSTM, 어텐션 등 덕분에 문장 길이가 길어져도 성능 저하를 막는다.
• 자연스런 문장생성 능력 : 다범주 분류에 좋은 성능을 내는 딥러닝 기법을 써서 문장 생성 능력이 큰 폭으로 개선됐다.

연구성과 소개

Manning은 이날 강연에서 Stanford NLP group의 최신 연구성과 몇 가지를 소개했는데요. 이미 언급했던 것처럼 모두 BiLSTM(with attention)이 적용된 모델들입니다.

Stanford Attentive Reader

Chen et al.(2016)은 문맥에서 질의에 대한 응답을 찾는 모델을 구축하는 데 BiLSTM with attention을 적용했습니다. 분석 대상 텍스트 단락(passage)과 질의(question)를 각기 다른 양방향 인코더에 넣어 $p$와 $q$ 벡터를 만듭니다. 단락의 $i$번째 단어에 대한 어텐션 스코어 $α_i$는 $softmax(q^TWp_i)$입니다. 디코더의 output vector $o$는 $Σ_iα_ip_i$입니다. 이를 정답 답변과 비교해 손실을 구하고 역전파 학습이 이뤄지는 구조입니다. 그 개념도는 다음과 같습니다.

Chen et al.(2017)은 위 연구를 기본으로 하되 위키피디아에서 관련된 단락을 뽑아내는 과정 등이 추가된 형태입니다. 전체적인 프레임워크는 다음과 같습니다.

Copy augmented S2S

Eric&Manning(2017)은 어텐션 스코어가 높은 인코더 입력 단어를 디코더 입력에 복사해 넣어, 이 디코더 입력을 학습시키는 기법을 제안했습니다. 아래 그림을 보겠습니다.

Eric&Manning(2017)에서는 인코더가 질의, 디코더가 응답을 처리합니다. 정답 응답은 ‘Buca di Beppo is an restaurant that is’인데, 디코더가 6번째 단어 restaurant를 예측해야 할 때 어텐션 스코어가 가장 높은 인코더 입력 단어는 ‘Italian’이었다고 가정해 보겠습니다. 그러면 이 모델은 해당 위치에 인코더 입력 단어를 복사하는 방식입니다.

tree based models

Tai et al.(2015)는 트리 구조의 LSTM 아키텍처를 제안했습니다. 아래 그림에서 상단에 있는 모델이 기존의 LSTM 네트워크, 하단이 Tai et al.(2015)가 제안한 모델입니다.

Dozat&Manning(2017)은 의존관계 분석(dependency parsing)에 BiLSTM with attention을 적용한 연구입니다.