컴언

'Natural Language Processing'에 해당되는 글 3건

  1. [인공지능] 무정보탐색(Uninformed Search) (2)
  2. 파이썬과 함께하는 자연어 처리: NLTK
  3. [언어 모델링] n-gram

[인공지능] 무정보탐색(Uninformed Search)

Natural Language Processing

인공지능이 다루는 문제들은 대부분 탐색 알고리즘으로 해결할 수 있습니다. 오늘 다룰 탐색 알고리즘들은 모두 무정보탐색 (Uninformed Search) 의 분류 안에 있습니다. 무정보탐색이란, (1) 목표 상태공간 (goal state) 에 도달하기 위해 필요한 단계의 횟수나 비용을 모르지만 (2) 어떤 상태 공간이 목표 상태공간인지 구분(goal test)할 수 있을 때를 의미합니다. 그래서 blind search 라고 불리기도 해요. (1)을 좀 더 설명하자면, 목표에 도달하기 위한 과정에 대한 정보가 없기 때문에 어떤 상태 공간을 먼저 탐색하는 게 좋을지 결정할 수 없다는 것이죠. 어떤 상태를 먼저 탐색하는게 좋을지에 대한 정보가 주어지게 되면 informed search 가 됩니다.


무정보탐색 알고리즘의 종류에는 BFS (너비 우선 탐색), DFS (깊이 우선 탐색), Uniform Cost Search (단일 비용 탐색), Iterative Deepening (반복적 깊이 증가) 가 있습니다. 미리 말하자면 대부분의 무정보탐색의 경우에는 Iterative Deepening 이 가장 효율적인 것으로 알려져 있습니다.




BFS

너비 우선 탐색의 기본 원칙은 얕은 곳 부터 깊은 곳 까지, 모든 노드들을 깊이 별로 차례 차례 훑는 것입니다. 위 그림을 가지고 설명하자면,


(1) start 노드에서 1 깊이 만큼 떨어진 빨간색 노드들을 방문

(2) start 노드에서 2 깊이 만큼 떨어진 파란색 노드들을 방문

(3) ... 맨 마지막 깊이까지 반복 


실제 구현을 위해서는 큐 자료구조를 이용하고요, 의사 코드는 아래와 같이 짜볼 수 있겠습니다.


function BFS(start-state){

    queue.EN_QUEUE(start-state)

    while (queue is NOT empty){

        state = DE_QUEUE()

        if (state == goal) then SUCCESS

        for s in successors: s.prev=state // 나중에 경로 추적을 하기 위함

        queue.EN_QUEUE(succsessors of state)

    }

}


BFS 는 목표에 도달하기 직전까지 무작정 상태공간을 생성하다보니 성능은 그리 좋다고는 할 수 없습니다. 시간 복잡도는 O(b^d), 공간 복잡도도 O(b^d) 이기 때문이죠. (참고로 b 는 한 깊이 내려갈 때 마다 평균적으로 뻗어나가야 하는 줄기의 평군 갯수(branching factor), d 는 깊이를 의미합니다) 다른 탐색 알고리즘의 시간/공간 복잡도를 보시면 왜 BFS 가 대부분의 문제 해결에서 비효율적인지 알게 되실겁니다.



위 표를 보면, branching factor 가 10이라 가정했을 때 2 깊이 씩만 나아가는데도 8 깊이에서 벌써 31 시간이 소요되고 결국 14 깊이에서는 3500 년, 11111 테라바이트가 소요된다는 어마무시한 결과를 알 수 있습니다... 저도 솔직히 BFS가 이렇게 비효율적인지는 몰랐네요.


탐색의 좋고 나쁨을 평가하는 데에 네가지 요소가 있습니다. (1) 완결도(Completeness) (2) 시간복잡도 (3) 공간복잡도 (4) 최적도 (Optimality)


BFS 의 경우에는 최적도에 대한 분석이 좀 필요한데요, 먼저 최적도를 설명해야겠습니다. 최적도는 알고리즘이 찾아낸 solution path 가 다른 solution path 들과 비교했을 때 좀 더 적은 비용을 가지냐를 따집니다. 모든 edge 들의 비용이 1이라면 BFS 는 최적도를 만족한다 볼 수 있겠습니다. 하지만 edge 들이 각기 다른 비용을 가진다면? 예를 들어 깊이 1에 목표가 있는데 비용이 9999 입니다. 그런데 깊이 5에도 목표가 있고 비용이 5 인 경우를 생각해보세요. 5가 최소 비용인 경우가 존재하는데도 불쌍한 BFS 는 9999 비용의 경로를 반환할 것입니다. 이런 경우에는 최적도를 만족하지 않습니다.


다행히 이런 최적도 문제를 해결 할 수 있는 방법이 있습니다. 바로 아래 설명할 Uniform Cost Search입니다. 


Uniform Cost Search (단일 비용 탐색)


기본적으로 탐색 원리는 BFS 와 정말 같습니다. 그런데 큐에서 어떤 상태 공간을 dequeue 하는지가 달라요. UCS 는 큐에 있는 상태공간 중에 가장 적은 비용의 것을 dequeue 합니다. 구현할 때는 priority queue를 사용하고요. 결국 도달하는데 가장 적은 비용이 드는 목표 지점을 찾아주겠죠.


BFS 와 같은 원리로 탐색하기 때문에 완결도를 만족하고요, 애초에 BFS 의 최적도 문제를 해결하기 위해 고안 된 알고리즘이기 때문에 최적도도 만족합니다. 시간 복잡도는 O(b^C/e) 로 표현하는데요, 경로의 비용에 초점을 맞추다보니 표현 방법이 좀 독특하죠. C는 목표 지점에 도달하기 위한 최소 비용, e는 edge 가 가질 수 있는 최소 비용입니다. 공간 복잡도도 동일합니다. 



DFS

이제 깊이 우선 탐색을 알아봅니다. 미리 말하자면, 위에서 설명한 알고리즘과 비교했을 때 DFS가 우위에 있는 것은 공간 복잡도입니다.


먼저 깊이 우선 탐색의 개념을 되짚어봅시다. 


"들어왔을 때는 마음대로였겠지만, 나갈 때는 아니란다." 제가 DFS 를 설명할 때 항상 인용하는 구절입니다. DFS 는 한 곳에 들어가면 그 곳만을 계속 파야합니다. 위 그림을 가지고 설명하면, 파란색 줄기를 쭉쭉쭉 파고 들어갑니다. 그러다가 그 줄기 안에 있는 모든 노드가 탐색 완료 되었으면 다시 집으로 돌아가다가 다른 줄기 (빨간색) 을 발견하고 거기를 또 다시 팝니다. 빨간색 줄기도 완료되면 집으로 돌아가다가 다시 초록색 줄기를 발견해서 계속 파고... 이게 무한 반복됩니다. 


스택 자료 구조를 이용해서 구현이 가능하고요, 아래 의사 코드를 보겠습니다. 


function DFS(start-state){

    stack.push(start-state)

    while (stack is NOT empty){

        state = stack.pop()

        if (state == goal) then SUCCESS

        for s in successors: s.prev = state

        stack.push(successors of state)

    }



DFS 의 공간 복잡도는 O(bm) 입니다. (m 은 그래프의 깊이를 의미) 시작 노드로 부터 가장자리 노드까지의 만큼의 공간만 스택에 머무른다는 것을 생각해보세요. 


하지만 불행하게도 DFS에는 치명적인 단점이 하나 있습니다. 조건이 붙는데요, 바로 트리가 무한할 때 입니다. DFS 는 한 줄기 끝까지 파기 전에는 다른 줄기로 이동할 수 없는데... 그 "끝"이 없으니 무한정 탐색을 하는 거죠. 결국 이런 경우에는 완결도를 충족하지 못하게 됩니다. 대신 무한한 트리가 아니라 끝이 있는 트리에서는 O(b^m) 의 시간 복잡도를 가집니다.


Iterative Deepening


Iterative Deepening 은 한국말로 반복적 깊이증가라고 하는데요, 이름이 알고리즘의 원리를 대략 설명해줍니다. DFS 에 깊이 제한을 둔다는 생각에서 출발합니다. 첫번째 단계에서는 깊이 1까지만 DFS, 두번째 단계에서는 깊이 2까지 DFS, 세번째 단계는 깊이 3까지, ... 무한 반복한다는 원리죠. 결국 반복적으로 DFS 를 하긴 하는데, 탐색하는 깊이 제한을 두고, 깊이를 계속 증가시키는 겁니다. 



BFS 와 DFS 를 짬뽕시켰다고 할까요? 탐색은 BFS 인데 메모리 구조는 DFS 의 스택을 이용하는 거죠. 덕분에 완결도도 충족하면서 (BFS 장점), 공간복잡도도 괜찮은 성능(DFS 장점)을 보여줍니다. 시간 복잡도는 O(b^d), 공간 복잡도는 O(bd) 입니다. 이 때문에 무정보탐색에서 주로 Iterative Deepening 을 이용하는 게 좋습니다.




** 시험 공부하면서 끄적여본 학부생의 부족한 설명 읽어주셔서 감사합니다. feedback 이나 질문 댓글 환영합니다! 

** 참고 자료: Artificial Intelligence: A Modern Approach (3rd Edition) 3rd Edition (Russell & Norvig) / (강의) CS540: Uninformed Search (Zhu) 

파이썬과 함께하는 자연어 처리: NLTK

Natural Language Processing

저는 언어학과 컴퓨터 과학을 이중 전공해서 언어학도와 컴공학도의 이질적(?) 삶에 대해 잘 알고 있습니다만... 요새 순수 언어학만 전공하는 제 동기들을 보면 Python 을 정말 열심히 배우는 것 같습니다. 파이썬은 문법도 되게 간결해서 컴맹도 배울 수 있고, 자연어 처리를 위한 수많은 라이브러리들의 강력한 기능쓸 수 있거든요


오늘 제가 다룰 NLTK 는 파이썬에서 자연어 처리를 할 수 있게 해주는 편리한 라이브러리입니다. 

NLTK 설치

** 파이썬이 설치 안된 분은 파이썬부터 설치하세요.

1. 윈도우 사용자
https://pypi.python.org/pypi/nltk 에 가서 nltk-3.x.x.win32.exe 를 내려받아 실행해서 설치하면 됩니다. 

2. 맥/유닉스 사용자
터미널을 실행해서 다음 명령어를 입력하세요.
sudo pip install -U nltk

잘 설치가 되어있는지 확인하려면 Python IDLE 에서 import nltk 를 해보세요. 아무런 에러가 나오지 않으면 제대로 설치된 것입니다. 


자연어 처리할 샘플 문자열 내려받기

NLTK 에서는 처음 설치하고 처리할 문자열이 없는 저 같은 잉여들을 위해 book 이라는 모듈에 다양한 책들을 내장시켜 놓았습니다. 이 책들은 
nltk.download()

을 파이썬 IDLE 에 입력함으로써 내려받을 수 있습니다. 그리고 나서 아래와 같은 창이 뜰건데요,


오늘은 book 만 이용해서 자연어 처리를 해보도록 하겠습니다. (제일 용량이 작아요)


텍스트 불러오기

내려받았으면 파이썬에 불러와야겠죠. 

from nltk.book import *
을 입력합니다. 대략 코드를 설명해보자면, "nltk의 book 라는 모듈에서(from) 모든 것(*)을 import 해와라" 가 되겠습니다.

>>> from nltk.book import *
*** Introductory Examples for the NLTK Book ***
Loading text1, ..., text9 and sent1, ..., sent9
Type the name of the text or sentence to view it.
Type: 'texts()' or 'sents()' to list the materials.
text1: Moby Dick by Herman Melville 1851
text2: Sense and Sensibility by Jane Austen 1811
text3: The Book of Genesis
text4: Inaugural Address Corpus
text5: Chat Corpus
text6: Monty Python and the Holy Grail
text7: Wall Street Journal
text8: Personals Corpus
text9: The Man Who Was Thursday by G . K . Chesterton 1908

총 9개 텍스트를 불러왔습니다. text1, text2, text3, ... text9 은 각각의 책에 부여된 이름입니다. 예를 들어 모비딕은 text1 이라고 부르기로 약속한 것입니다. 



각종 기능 탐구

1. concordance: 단어가 쓰인 모든 경우의 문맥을 찾아줌 (색인)

concordance 는 색인이라는 뜻인데, 책 맨 뒷장에 있는 그 색인을 생각하시면 될 것 같습니다. 색인 보시면 책에 나온 단어들이 나열되어 있고 그 단어가 쓰인 페이지 수를 보여주잖아요. NLTK 의 concordance 는 텍스트에서 주어진 단어가 쓰인 문맥을 다 찾아줍니다.

>>> text4.concordance("terror")
Displaying 8 of 8 matches:
menaces , by fraud or violence , by terror , intrigue , or venality , the Gove
ameless , unreasoning , unjustified terror which paralyzes needed efforts to c
ublic seemed frozen by a fatalistic terror , we proved that this is not true .
 to alter that uncertain balance of terror that stays the hand of mankind ' s 
eans freeing all Americans from the terror of runaway living costs . All must 
still . They fuel the fanaticism of terror . And they torment the lives of mil
d maintain a strong defense against terror and destruction . Our children will
k to advance their aims by inducing terror and slaughtering innocents , we say


저는 미국 대통령들의 역대 연설을 모아둔 text4 에서 terror 라는 낱말이 쓰인 문맥을 찾아봤습니다. violence, unjustified, fatalistic 같은 단어들이 보이네요.

2. similar: 주어진 단어와 비슷한 환경에서 쓰인 단어를 찾아줌

아까 미국 대통령 연설문에서 terror 라는 단어가 어디에 쓰였는지 찾아봤을 때 unjustified _________, fatalistic __________ 와 같이 단어가 쓰이는 환경이 있다는 걸 확인하셨을텐데요. similar 은 텍스트 안에서 terror 와 비슷한 환경에서 쓰인 단어를 찾아줍니다. 한번 해볼까요?

>>> text4.similar("terror")
life congress knowledge power liberty peace freedom suffering wealth
duty nations war history government idealism good legislation

단어의 뜻이 비슷한 것이랑 착각하시면 안됩니다. 순전히 쓰이는 환경이 비슷한 단어들을 찾아주는 것이라고 기억하세요. 대략 congress, legislation, nations 같은 단어들이 많이 보입니다. 아무래도 정치적으로 테러라고 하면 폭탄 테러 같은 경우에 많이 쓰이니까 그런 것일까요? 다른 텍스트에서는 terror 와 비슷한 환경에서 쓰인 단어에 어떤 것이 있는지 찾아보겠습니다. 


>>> text1.similar("terror")

man thing way ship bone harpooneer distance sound speed sign sight

whale night picture land voyage whaling repose circle battle


 결국 대통령 연설문에서 쓰인 terror 의 느낌과 소설책에서 쓰인 terror의 느낌이 다르다는 것을 알수 있었습니다. 하지만 둘다 문장이 얼마 없어서인지 의미있는 결과는 없네요.


3. dispersion_plot: 텍스트 내 단어 사용 빈도와 위치를 분산 그래프로 그려줌

백 번 설명 보단 한 번 보는게 더 나은 아주 유용한 기능입니다. 

text4.dispersion_plot(["citizens", "democracy", "freedom", "duties", "America"])



 text4 은 우선 옛날-현재 순으로 미국 대통령들의 연설이 나열되어있습니다. 이 점을 이용해서 다섯 개 단어가 시간을 흐르면서 얼마나 자주 사용됐었는지 알아본 예제였습니다.

참고로, plot 기능을 이용하기 위해서는 NumPy 가 설치되어있어야 합니다. 


4. word_tokenize : token 나누기

>>> sentence = "It was always hard for me to shine and try to immortalize my name."
>>> tokens = nltk.word_tokenize(sentence)
>>> tokens
['It', 'was', 'always', 'hard', 'for', 'me', 'to', 'shine', 'and', 'try', 'to', 'immortalize', 'my', 'name', '.']

5. pos_tag: 품사 태깅

>>> tagged = nltk.pos_tag(tokens)
>>> tagged
[('It', 'PRP'), ('was', 'VBD'), ('always', 'RB'), ('hard', 'RB'), ('for', 'IN'), ('me', 'PRP'), ('to', 'TO'), ('shine', 'VB'), ('and', 'CC'), ('try', 'VB'), ('to', 'TO'), ('immortalize', 'VB'), ('my', 'PRP$'), ('name', 'NN'), ('.', '.')]


영어 분야에서는 자연어 처리 연구가 꽤나 진전되어있는 상태입니다. 다음에는 한국어 자연어 처리 모듈도 공부해봐야겠습니다.


[언어 모델링] n-gram

Natural Language Processing

자연어 처리에서 확률의 중요성


우리가 자연어로 만들어내는 문장들은 정규화되지 않고 무한하며 복잡한 문법을 따르기 때문에 컴퓨터가 처리하기 어렵습니다. 하지만 효과적인 언어 모델링을 이용하면 분석이 한결 더 쉬워질 수 있습니다. 예를 들어 음성 인식의 경우를 생각해 봅시다.


"It's hard to recognize a speech."


와 


"It's hard to wreck a nice beach."


라는 두 문장이 있습니다. 발음해보시면 알겠지만, 둘은 서로 거의 비슷한 음성적 특성을 가지는 문장입니다. 하지만 두 번째 문장처럼 일어나기 힘든(단어들이 조합되기 힘든) 말이 주어질 확률은 낮습니다. 따라서 확률적으로 훨씬 빈도/가능성이 제일 높은 첫 번째 문장으로 인식하죠. 한국어에서도 사이시옷 같은 괴랄한 맞춤법 규칙, 띄어쓰기, 발음 변동 현상과 같은 문제를 해결하는 데 언어 모델링이 엄청 중요하다고 생각합니다.



비슷하게, "피아노를" 이라는 어절을 주면 다음에 "치다" 같은 단어가 올 것이라고 예상할 수 있습니다. 이런 생각에서 다양한 확률론적 모델이 고안되었고 오늘 다룰 n-gram 이 그런 확률적 분석 방법의 하나입니다. 


n-gram

 


n-gram 은 n개 어절/음절을 연쇄적으로 분류해 그 빈도를 따집니다. n=1 일 때는 unigram, 2일 때는 bigram, 3 - trigram 식으로 불리는데 분석 예제를 보면 무슨 뜻인지 감이 오실겁니다.


"쓸쓸하던 그 골목" 음절 단에서 bigram 으로 분석한 결과


['쓸', '쓸'], ['쓸', '하'], ['하', '던'], ['던', ' '], [' ', '그'], ['그', ' '], [' ', '골'], ['골', '목']

"쓸쓸하던 그 골목을 당신은 기억하십니까" 을 단에서 trigram 으로 분석한 결과

[['쓸쓸하던', '그', '골목을'], ['그', '골목을', '당신은'], ['골목을', '당신은', '기억하십니까'], ['당신은', '기억하십니까', ' '], ['기억하십니까', ' ', ' ']]



그리고 긴 텍스트를 분석하게 된다면 같은 n-gram 이 여러개 나오게 될 겁니다. 그 n-gram 들의 수를 세서 리스트로 만든 것을 빈도 리스트 (frequency list) 라고 합니다. 저는 이상의 소설에서 가장 많이 나온 n-gram 이 뭘까 궁금해서 이상의 날개를 이용해 Python으로 n-gram 분석을 해봤습니다. 아래를 보시죠.

Python 구현



#!/usr/bin/env python3
# -*- coding:utf-8 -*-]

with open('nalgae.txt', 'r', encoding='utf-8', newline='\n') as f:
	file = f.read()
sample_file = ''.join(file) 

#어절 n-gram 분석
#sentence: 분석할 문장, num_gram: n-gram 단위
def word_ngram(sentence, num_gram):
	# in the case a file is given, remove escape characters
	sentence = sentence.replace('\n', ' ').replace('\r', ' ')
	text = tuple(sentence.split(' '))
	ngrams = [text[x:x+num_gram] for x in range(0, len(text))]
	return tuple(ngrams)

#음절 n-gram 분석
#sentence: 분석할 문장, num_gram: n-gram 단위
def phoneme_ngram(sentence, num_gram):
	text = tuple(sentence) # split the sentence into an array of characters
	ngrams = [text[x:x+num_gram] for x in range(0, len(text))]
	return ngrams

#n-gram 빈도 리스트 생성
def make_freqlist(ngrams):
	freqlist = {}

	for ngram in ngrams:
		if (ngram in freqlist):
			freqlist[ngram] += 1
		else:
			freqlist[ngram] = 1
	
	return freqlist

ngrams = word_ngram(sample_file, 3)
freqlist = make_freqlist(ngrams)
sorted_freqlist = sorted(freqlist.items(), key=operator.itemgetter(1))
print(sorted_freqlist)


 


빈도 리스트는 길어서 상위 4개 trigram 만 적습니다.

날개의 본문은 저작권이 만료되었으므로 한국저작권위원회 공유마당에서 내려받으실 수 있습니다.

(('것', '같았다.', '나는'), 3), (('돈을', '놓고', '가는'), 3), (('그', '돈', '오'), 4), (('알', '수', '없다.'), 4)]

날개의 n-gram 분석 결과도 흥미롭네요 ㅎㅎ


추가>> bigram 분석 결과 시 다음과 같이 나왔습니다. 

(('다.', '나는'), 6), (('돈을', '놓고'), 6), (('내', '방'), 6), (('놓고', '가는'), 6), (('아내', '방으로'), 6), (('견딜', '수가'), 6), (('이불', '속에서'), 6), (('수', '있는'), 6), (('않았다.', '나는'), 6), (('', '나는'), 6), (('한', '번'), 6), (('나는', '그'), 7), (('내', '방으로'), 7), (('나는', '이'), 8), (('나는', '또'), 12), (('것이다.', '나는'), 12), (('나는', '내'), 12)]




여담: Google Books Ngram Viewer



Google Ngram Viewer (링크: https://books.google.com/ngrams) 은 구글이 구축한 말뭉치에서 연도별로 검색된 n-gram 을 검색해서 보여줍니다. 빅데이터 텍스트 마이닝 분야뿐 만 아니라 요새는 인문학 연구, 마케팅에도 자주 쓰인다고 하네요. 상당히 흥미로운 통계도 찾을 수 있으니 직접 해보시기 바랍니다.



참고자료


  1. Zhu, Xiaojin. "Language Modeling." CS769: Advanced Natural Language Processing (2010): n. pag. Web.
  2. 심광섭. "품사 태깅 말뭉치에서 추출한 n-gram을 이용한 음절 단위의 한국어 형태소 분석." 정보과학회논문지 : 소프트웨어 및 응용, 40.12 (2013): 869-876. Print.