|
|
|
|
|
|
||
|
제목: TransWorks (영한번역 학습 프로그램) |
이페이지 저작권은 저자에게 있음. |
|
|
저자: 정재준(rgbi3307(at)nate.com) |
최근수정일:2011-03-28 |
|
|
|
|
|
TransWorks (영한번역 학습 프로그램)
알고리즘 소개
|
글제목: TransWorks (영한번역학습 프로그램) 알고리즘 소개 작성자: 커널연구회(www.kernel.bz), 정재준 (rgbi3307@nate.com) 작성일: 2011-02-26
*작성자 정보를 유지하여 저작권을 보호해 주시기 바랍니다. |
TransWorks (영한번역 학습 프로그램) 알고리즘 소개
|
옥스포드 영어사전에 등재되어 있는 영어단어 수는 약 30만(3 x 10의5승)개 라고 알려졌습니다. 일상생활에서 통용되는 단어(방언, 신조어 등..)들까지 합하면 약 100만(10의6승)개의 단어가 있다고 예측해 봅니다. 영어단어 100만개, 한글단어 100만개를 서로 연결한 자료구조로 컴퓨터 메모리에 영한-한영 사전을 구축했을 때 단어 검색 속도에 대해서 정리합니다.
요즘 컴퓨터의 CPU 처리속도는 보통 수 GHz 입니다. 즉, CPU 내부에서 1 클럭(디지털 신호가 On/Off로 변화되는 클럭)은 약 10의-9승초(0.001마이크로초) 걸린다는 것입니다. CPU 제조사 마다 조금씩 다르겠지만, 1개의 기계명령이 10클럭으로 설계되었다면, 하나의 명령을 수행하는데 0.01 마이크로초가 소요됩니다. 여기서, 하나의 문자를 비교하는데 10개의 기계명령이 필요하다면, 하나의 문자 비교에 0.1마이크로(10의-7승)초가 소요됩니다. 영어단어가 평균 10개의 문자로 구성되었다고 보면, 하나의 영어단어를 비교하는데 약 1마이크로(10의-6승)초가 걸린다고 계산할 수 있습니다. 그렇다면, 컴퓨터 메모리에 100만개의 영어단어가 저장되어 있다고 할때, 하나의 영어단어를 순차 검색하는데 소요되는 시간은 아래와 같이 쉽게 산출해 볼 수 있습니다.
(1) 최선의 경우: 영어단어 1번 비교 --> 1마이크로(10의-6승)초 (2) 최악의 경우: 영어단어 100만번 비교 --> (10의6승) x (10의-6승) --> 1초 (3) 평균: 최악의 경우 / 2 --> 0.5초
위의 결과는 100만개의 단어를 컴퓨터 메모리에 배열형태로 쭉 나열했을때의 자료구조를 가정한 결과입니다. 지난 수십년간 컴퓨터 CPU 처리속도는 수백배 빨라졌습니다. 수십년전의 컴퓨터에 100만개의 단어로 영한사전을 구축했었다면, 하나의 단어를 검색하는데 평균 50초(약1분)가 걸렸다고 볼 수 있습니다. 영한사전으로서의 효용성이 없는 셈입니다. 더구나, 단어 검색을 좀더 빠르고 효율적으로 할 수 있도록 인덱스화된 자료구조와 알고리즘을 사용하지 못했다면 효용성은 더더욱 떨어집니다.
제가 요즘 컴퓨터에 영한-한영 사전을 새롭게 구축하고 영한번역학습기, 더 나아가 자연어 기계번역에 도전하고 있는 이유는 바로 수백배 빨라진 CPU 처리속도에 효율적인 자료구조와 알고리즘들을 적용할 수 있기 때문입니다. 컴퓨터 자료구조와 알고리즘은 입력 자료구조 형태와 개수에 따라서 처리 효율이 엄청나게 달라집니다. 입력자료 개수가 수천개 이하라면, 특별한 자료구조와 알고리즘을 사용하지 않아도, 요즘의 CPU에서 빠른 결과를 얻을 수 있습니다. 그러나, 입력자료 개수가 수백만~수천만개 이상에서는 효율적인 자료구조와 알고리즘을 적용하지 않으면 유용한 결과를 얻기 힘듭니다.
일단, 가장 대표적인 자료구조인 트리구조로 영한 사전을 구축하는 경우를 생각해 보겠습니다. BST(Binary Search Tree), RBT(Red-Black Tree), BTree, TRIE... 등은 모두 트리구조에서 파생되어 발전했습니다. 트리구조를 사용하면 위에서 산출한 순차검색에 비해서 얼마만큼 빨라 질까요? DBMS에서 많이 사용하고 있는 BTree에 100만개의 단어를 인덱스화 시키면, BTree의 깊이(height)는 log(10의6승) --> 6이 됩니다.(order가 10인경우) 따라서, BTree에서는 단어를 최소 6번, 최대 6번 x order --> 60번만 비교하면 되고, 위에서 예로든 CPU 클럭으로 시간을 산출하면,
(1) 최소: 6번 비교 --> 6 x 1마이크로초 --> 6마이크로초 (2) 최대: 60번 비교 --> 60 x 1마이크로초 --> 60마이크로초 --> 0.06미리초
100만개의 단어중에서 하나의 단어를 검색할때 최대 0.06미리초만에 검색해 낼 수 있다는 것입니다. 영한-한영 사전을 이 정도의 빠르기로 구축한다면, 영한-한영 문장 번역도 가능하지 않을까요? 문장 번역은 여러개의 알고리즘들을 효율적으로 적용해야 된다고 봅니다.
10년전에는 컴퓨터를 사용한 문장 번역은 어렵지 않을까? 라는 회의적인 시각이 많았습니다. 저는 학창시절 전자전기제어공학을 전공했는데 영어로 된 기술 서적들이 많이 난해했습니다. 그래서 영어공부도 병행했구요. 가끔 저의 전공과 영어, 2가지를 다 살리는 방향으로 컴퓨터 문장 번역 프로그래밍을 시도 하기도 했습니다. 그때는 학창시절의 습작 정도에 그쳤고, 제가 공부한 영어문장을 데이터 파일에 저장시켜 놓고 조회하는 수준의 프로그램 이었죠. 지금도 그때 C언어로 작성했던 프로그램을 꺼내 보고 웃음짓곤 한답니다.
그러나 요즘 자료구조와 알고리즘을 다시 공부하면서, 이것을 잘 응용하고 개선시키면 문장 번역이 가능하리라는 긍정적인 시각을 가지게 되었습니다.
사람이 언어를 구사하는 것도 학습을 통해서 이루어집니다. 극단적인 예로 청각에 장애가 있는 사람은 말도 하지 못합니다. 즉, 청각을 통해서 들은 언어를 머리에 축적시켜 놓지 못하면 꺼내 쓸 수 있는 말도 없게 됩니다. 사람은 요람에서 무덤까지 이르면서 수많은 언어를 듣고 학습합니다. 사람의 두뇌 세포들은 엄청난 저장 용량과 논리적인 판단 능력이 있는 것 같습니다. 시청각을 통해서 학습한 수십만개의 단어들을 논리적으로 조합하여 언어를 구사 하니까요. 그럼 우리가 구사하고 있는 문장의 개수는 몇개나 될까요? 요즘 저는 여기에 관심이 많습니다. 그냥 통크게 퉁 쳐서 다음과 같이 계산해 보겠습니다.
(1) 사전에 등재되어 있는 단어(어휘)의 개수 --> 30만개 (2) 문장 개수 --> 단어의 조합 순열 --> 30만!(팩토리얼)
30만 팩토리얼 이라는 수는 아마 컴퓨터로 계산할 수 없는(데이터 표현 범위 벗어남) 천문학적인 수이지만, 팩토리얼을 계산하는 컴퓨터 알고리즘에 넣어서 정수형이나 더블형의 데이터 타입이 아닌 숫자 문자열로 출력하면 가능할 것 같습니다. 아마, 컴퓨터 화면을 숫자로 가득 채울듯 합니다. 조만간 이것을 계산한 결과를 한번 보여드리겠습니다. 별로 어렵지 않습니다. (이미 계산한 분이 계시다면 한번 공개해 주세요) 사람의 두뇌 세포들은 이러한 어마어마한 저장용량을 가지고 있고, 게다가 논리적인 판단을 통해서 단어(어휘)들을 문법에 맞게 조합하여 사물을 보는 순간 아주 눈 깜짝할정도의 속도로 문장들을 표현합니다. 실로 엄청난 능력을 가지고 있습니다.
사람의 두뇌를 컴퓨터의 CPU와 메모리에 비유합니다. 컴퓨터의 논리회로는 사람의 두뇌 세포라 볼 수 있습니다. 제가 생각해 볼때, 컴퓨터의 CPU와 메모리는 수십년내로 사람의 두뇌 세포 용량만큼 증가할 수 있다고 봅니다. 이론적으로 머 그렇게 어렵지도 않습니다. 두뇌 세포에 해당하는 논리회로(TTL 트랜지스터) 배열을 계속 증대 시켜 나가면 되니까요. 계산해 보면,
현재 32비트 컴퓨터는 2의32승 --> 4 x 10의9승 --> 40억 64비트 컴퓨터는 2의64승 --> 16 x 10의18승 --> 16000000...(0이 18개 붙어 있는수) --> 16해 128비트 컴퓨터는 2의128승 --> 256 x 10의36승 --> 25600000000... (0이 36개 붙어 있는수) --> 256?? 256비트 컴퓨터는... 아마 엄청난 크기의 수를 표현할 수 있고, 메모리도 엄청 늘어날 것입니다.
이러한 하드웨어적인 발전을 보면 머지 않아 사람의 두뇌 세포 용량을 따라 잡을 것입니다. 문제는, 사람의 논리적인 생각처럼 컴퓨터에 자료구조와 알고리즘을 심어주는 것입니다. 저는 여기에 관심이 있습니다.
자료구조와 알고리즘을 공부하다 보면, 아주 단순한 원리에서 부터 출발합니다. 이 원리를 잘 활용하고 개선하면 어렵지 않습니다. 문장 번역을 위한 맞춤형 자료구조와 알고리즘은 구현될 수 있다고 생각합니다. 단, 제가 현재 진행하고 있는 것들은 몇가지 사용자적인 이해가 있어야 합니다만...
저는 우리가 일상에서 사용하는 문장의 개수를 다음과 같이 계산했습니다.
(1) 사전에 등재되어 있는 단어(어휘)의 개수 --> 30만개 (2) 문장 개수 --> 단어의 조합 순열 --> 30만!(팩토리얼)
30만!(팩토리얼)은 엄청나게 큰 천문학적인 수입니다. 일단, 30!(팩토리얼)을 계산하는 코드를 아래와 같이 C언어로 코딩하여 실행해 봤습니다.
main () { int i; double nfact = 1; //64비트(8바이트)
for (i = 1; i <= 30; i++) nfact *= i; printf ("nfact=%f\n", nfact);
nfact = 1; for (i = 1; i <= 100; i++) nfact *= i; printf ("nfact=%f\n", nfact); }
30팩토리얼: 265252859812191032188804700045312
100팩토리얼: 933262154439441021883256061085752672409442548549605715091669104004 079950642429371486326940304505128980429892969444748982587372043112 36641477561877016501813248
30!과 100!이 위와 같은 수 이므로 30만!(팩토리얼)은 아마 현존하는 컴퓨터로는 표현할 수 없는 엄청난 크기의 수입니다. 그럼 우리는 30만!(팩토리얼)이나 되는 문장들을 어떻게 표현하는 걸까요? 우리의 두뇌 세포속에 30만!(팩토리얼)의 문장들이 모두 저장되어 있는 걸까요? 저는 언어학자도 아니고 언어에 대해서 깊이 있는 지식은 없습니다만, 우리가 문장들을 표현하는 것을 쉬운 방식으로 생각해 보기로 했습니다. 아래와 같이 크게 2가지로 분류해 봤습니다.
(1) 오감(시각, 청각, 후각, 미각, 촉각)에 의한 언어(문장) 표현 (2) 논리적인 생각에 의한 언어(문장) 표현
한번 더 언급하지만, 저는 언어학자가 아니기 때문에 위의 2가지 분류를 언어학적으로 생각한 것은 아닙니다. 단지, 컴퓨터를 전공한 공학도의 입장에서 우리가 사용하는 문장을 컴퓨터로 번역하기 위해서는 어떠한 자료구조와 알고리즘을 사용하는 것이 적절한가를 고민해서 도출해낸 분류입니다. 위의 2가지 분류를 다시 생각해 보면,
(1) 오감에 의한 문장표현 --> 경험에 의해 축적된 어휘를 순간적으로 표현. (2) 논리적인 문장표현 --> 학습에 의해 축적된 어휘를 논리적인 문법 체계에 맞도록 조합하여 표현.
(1) 오감에 의한 문장표현 --> 속도가 빠르다. (2) 논리적인 문장표현 --> 속도가 다소 느리다.
우리가 일상에서 사용하는 문장은,
(1) 오감(시각, 청각, 후각, 미각, 촉각)에 의한 문장표현 --> 경험에 의해 축적된 어휘를 순간적으로 표현. (2) 논리적인 문장표현 --> 학습에 의해 축적된 어휘를 논리적인 문법 체계에 맞도록 조합하여 표현.
위와 같이 표현한다고 생각해 볼 수 있습니다. 컴퓨터로 문장 번역을 위한 자료구조와 알고리즘을 코딩할때 위의 분류는 중요한 고려 대상입니다. 또한, 아주 중요한 차이점이 있습니다. 사전에 등재되어 있는 단어(어휘)의 개수가 30만개 정도이면, 이 단어를 단순히 조합하여 만들 수 있는 문장의 개수는 30만!(팩토리얼) 이고, 이것은 천문학적인 수의 크기라는 것을 저의 앞글에서 소개해 드렸습니다만, 다시 숫자의 크기를 확인해 보면,
30!(팩토리얼): 265252859812191032188804700045312
100!(팩토리얼): 933262154439441021883256061085752672409442548549605715091669104004 079950642429371486326940304505128980429892969444748982587372043112 36641477561877016501813248
30만!(팩토리얼): 한번 상상해 보세요...
이러한 어마어마한 개수를 사람의 두뇌는 저장 세포에 모두 저장시켜 놓았을까요? 그렇지는 않을 것입니다. 두뇌 세포의 용량에도 한계가 있을 것입니다. 그래서 사람의 두뇌도 문장을 효율적으로 표현하기 위해서 두뇌 세포에 단어들을 체계적으로 정리해 놓은 자료구조와 논리적으로 조합하기 위한 알고리즘을 구축해 놓았을 것입니다. (사람들 마다 차이점이 좀 있겠습니다만...)
저는 사람이 문장 표현하는 방식을 논리적으로 정리하여 컴퓨터 자료구조와 알고리즘에 접목 시켜 보고 있습니다. 앞에서 언급한 2가지의 문장 표현방식을 다시 생각합니다.
(1) 오감(시각, 청각, 후각, 미각, 촉각)에 의한 문장표현 (2) 논리적인 문장표현
중요한 차이점이 있는데, (1)번은 논리적인 표현이 아니라 사람의 오감을 담당하는 두뇌 세포에 오감을 표현하는 문장이 저장되어 있어 이것을 본능적으로 꺼내어 사용한다는 것입니다. 따라서, (1)번은 컴퓨터 자료구조와 알고리즘으로 표현하기 쉽다고 판단합니다. 바로 검색 알고리즘을 사용하면 되고, 입출력되는 문장의 개수도 현재의 컴퓨터 메모리에 모두 저장시켜 놓을 수 있습니다. 몇가지 예를 들면,
so cool --> 너무 멋져!, 신선한데!, 멋진데! it's awesome --> 그거 끝내주는데, 굉장한데, 어마어마하군, 진짜 인상적이야. she is so hot --> 그녀는 너무 멋져, 섹시해. sort of --> 그런 셈이야. ...
이러한 문장 조합은 사람의 두뇌 세포에 그대로 저장되어 있어서, 맞는 상황이 발생하면 그대로 꺼내어 사용한는 것이라 볼 수 있습니다. 여기에는 논리적으로 문법을 고려하지 않을 것입니다. 따라서, 이러한 문장은 컴퓨터 자료구조에 모두 저장시켜 두고 빠르게 검색해 낼 수 있습니다. 그럼, 오감에 의한 문장표현들이 몇개나 있을까요? 정확히 분류하기는 조금 어렵지만, 아마 수십만개 이하라고 예측합니다. 수십만개 이하의 문장은 컴퓨터 검색 알고리즘으로 잘 구현하면, 수미리초 이내로 검색해 낼 수 있습니다. 현재, 이정도는 자료구조와 알고리즘으로 제가 구축해 두었습니다. (상용 라이브러리를 사용하지 않고 제가 일일히 맞춤형으로 코딩 했다는 것이 저에게는 중요합니다만...)
문제는, (2)번 논리적인 문장표현인데요...
저는 앞에서 문장 표현들을 아래와 같이 크게 두가지로 분류했습니다.
(1) 오감(시각, 청각, 후각, 미각, 촉각)에 의한 문장표현 --> 빠른 검색 (2) 논리적인 문장표현 --> 단어 조합(약 30만 팩토리얼에 해당하는 종류)
컴퓨터로 자연어 번역을 위해서 (1)은 맞춤형 검색 알고리즘을 빠르게 실행하도록 구현했습니다. 문제는 (2) 입니다만, 여러가지로 고민한 결과 다음과 같은 방식을 도입했습니다.
사람이 아닌 기계(컴퓨터)가 사람이 사용하는 언어의 모든 상황, 즉, 화자의 감정, 화자가 처한 상태, 화자의 어투, 줄임말, 존대말, 뛰어쓰기 등을 여러가지 논리로 판단하여 번역하는 데는 문제가 있다. 그러므로 문장에 여러가지 논리성을 적용하여 번역하기 보다 화자가 자신의 언어를 컴퓨터에게 입력(학습) 시키고 이것을 검색해 내는 방식을 도입합니다. 예를들면,
일반적 표현 Can you speak English? >> 영어를 말할 수 있니?
정중한(존대) 표현 Could you speak English? >> Could를 Can의 과거라는 논리를 적용하여, >> 영어를 말할 수 있었니? 라는 번역보다 >> 영어를 말할 수 있으신가요? 라는 번역(정중한 표현)이 더 좋습니다.
또한, 일반적으로 진행형을 다음과 같이 번역합니다. she is learning English. >> 그녀는 영어를 배우고 있습니다.
그러나, 그녀가 미국에 가기를 원하는 상황이라면, She wants to work in USA, so she is learning English. >> 그녀는 미국에서 일하는 것을 원하므로, 영어를 공부하려 합니다.
한가지 더 보충하면, What are you doing? >> 너 뭐하는 중이니?
What are you doing tomorrow? >> 너 내일 뭐 할 거니?
제가 이러한 예를 제시하는 이유는, 문장을 단순한 논리로 번역하게 되면 오역이 많아질 수 있으므로 화자가 말하고자 하는 것을 번역하여 컴퓨터에게 입력(학습) 시키고 이것을 맞춤형 검색 알고리즘으로 검색하는 방식이 오히려 더 정확한 번역이 될 수 있다는 것입니다.
제가 개발하고 있는 언어 번역 방식을 다시 정리하면, (1) 오감(시각, 청각, 후각, 미각, 촉각)에 의한 문장표현 --> 이미 저장된 것을 빠르게 검색 (2) 논리적인 문장표현 --> 입력(학습) 시킨 후 빠른 검색
(1)은 문장이 어느정도 정해져 있으므로 번역한 것을 이미 컴퓨터 메모리에 저장해 두고 맞춤형 알고리즘을 사용하여 빠르게 검색합니다. (2)는 다양한 문장들이 있으므로 사용자가 학습한 내용을 컴퓨터에 입력 시킨후 맞춤형으로 검색합니다.
지금까지 구현한 저의 프로그램은 사전속의 단어를 최대 42억개(단어개수)까지 저장할 수 있도록 했고, 번역문장은 컴퓨터 메모리가 허용되는 범위까지 무한히 저장되도록 했습니다. 여기서 중요한 것은, 번역문장 문자열을 그대로 메모리에 저장하면 메모리 낭비가 심하고 검색속도 또한 많이 떨어질 수 있습니다. 이것을 방지하기 위해서 번역문장 속의 단어들을 단어 사전속의 단어와 인덱스로 조합한 형태로 저장합니다. 이렇게 하면 메모리 낭비가 줄어들고 검색속도가 현저히 빨라집니다. 또한, 상용 라이브러리들을 사용하지 않고 오직 표준 C언어만 사용하여 위의 내용들을 맞춤형 알고리즘으로 코딩했습니다. 따라서 아키텍쳐(컴퓨터 종류)에 상관없이 프로그램을 실행할 수 있습니다. 현재는 리눅스와 윈도우즈에서 실행할 수 있습니다. 향후, 다양한 휴대용 스마트 기기에도 실행 되도록 알고리즘을 꾸러미로 묶어서 이식성이 편리하도록 할 예정입니다.
끝으로, 현재 다양하게 연구되고 있는 기계번역 알고리즘들을 간단히 요약 정리합니다.
1. 검색 알고리즘 (Search Algorithms): 컴퓨터에게 번역문을 입력(학습) 시키고 이것을 검색해 내는 방식.
2. 통계적인 패턴 분석 알고리즘 (Statistical Machine Translation): 번역된 문장들을 통계적인 패턴으로 분석하는 알고리즘. (현재 구글 번역기에서 도입하고 있음)
3. 영국 Edinburgh 대학교의 Philipp Koehn 교수의 논문 및 저서의 내용(목차):
Statistical Machine Translation:
Introduction : 소개 Words, sentences, corpora : 단어들, 문장들, 전집 Probability theory : 확률 이론
Word-based models : 단어 기반 모델 Phrase-based models : 구절 기반 모델 Decoding : 부호화 Language models : 언어 모델 Evaluation : 평가
Discriminative training : 식별 훈련 Integrating linguistic information : 언어학적 정보 통합 Tree-based models : 트리 기반 모델
|
|
|
|
|
|
|
|
|
|
|
||
|
제목: TransWorks (영한번역 학습 프로그램) |
이페이지 저작권은 저자에게 있음. |
|
|
저자: 정재준(rgbi3307(at)nate.com) |
최근수정일:2011-03-28 |