Sung-Hae Jun http://ailab.sogang.ac.kr/~shjun shjun@ailab.sogang.ac.kr 자연어 처리의 이해 Sung-Hae Jun http://ailab.sogang.ac.kr/~shjun shjun@ailab.sogang.ac.kr

기계와의 대화 기계와의 통신: 기계가 이해할 수 있는 언어 사용 컴퓨터와 대화: 인공적으로 만들어진 언어 TV와의 통신: 버튼 조작 (인간과 TV와의 통신을 위한 언어) 컴퓨터와 대화: 인공적으로 만들어진 언어 운영체제에 내리는 명령: DOS 명령어,… 데이터 베이스 관리 시스템의 데이터베이스 질의어: SQL,… 프로그래밍 언어: Basic, Pascal, C,…

자연언어 사람과 사람이 일상 생활에서 서로 대화하는데 사용되는 언어 - 한국어, 영어, 일어,… 인위적으로 만들어 지기 보다는 오랜 역사가 흐르면서 자연스럽게 생성 및 발전되어 온 언어 자연어 처리 자연어 이해: 컴퓨터로 하여금 사람이 입력 시키는 자연언어를 이해할 수 있도록 하는 것 자연어 생성: 컴퓨터가 자연언어를 사용하여 사람에게 말을 하는 것 자연어 처리 = 자연어 이해 + 자연어 생성 즉 자연어 처리는 인간의 언어를 기계가 이해하고 생성할 수 있도록 하기 위한 연구 자연어 처리는 보통 타이프 된 문장까지만 다룸. 음성으로 확대할 경우는 음성 이해 및 생성

자연언어 처리 시스템의 구성도 입력문장 형태소 분석기 구문분석기 문법 사전 의미분석기 생성사전 생성문법 각종 지식기반 (Knowledge-Base) 담화(discourse) 분석기 출력문장 문장생성기

응용 분야 기계 번역 HCI(Human Computer Interface) 텍스트 이해, 질의 응답 시스템의 구현 - 특정 언어의 문장을 컴퓨터가 자동으로 다른 언어로 번역 - 자동 통역: 음성으로 들어오는 특정 언어의 말을 컴퓨터가 자동으로 다른 언어로 통역 HCI(Human Computer Interface) - 인간이 컴퓨터 이용 시 기존의 특수한 명령어를 사용하지 않고 자연언어로 된 명령어를 사용 텍스트 이해, 질의 응답 시스템의 구현

학제간의 연구 언어학과의 간계 철학과의 관계 인지과학과의 관계 - 언어학은 컴퓨터에 의한 자연어 이해를 목표로 하기 보다는 인간의 언어 그 자체에 대한 연구를 지향 - 언어학의 연구(언어의 구조, 의미 등)는 그대로 자연어 이해에 응용 철학과의 관계 - 철학의 논리식은 자연어의 의미 표현에 이용 - 기타 자연어 이해의 근본적인 문제에 대한 해법을 제공 인지과학과의 관계 - 인지과학의 발전은 자연어 처리 발전에 결정적 역할 - 자연어 이해에 관한 전산학적 한계를 극복: 자연어 이해에 대한 인간 두뇌의 동작에 대한 연구

어절, 단어, 형태소 어절 단어 형태소 언어학 : 문장을 구성하는 도막도막의 마디로 의미적 구성 단위, 문장 성분(Constituent)의 최소단위 전산학 : 양쪽에 공백을 갖는 띄어쓰기 단위의 문자열 단어 언어학 : 자립하여 쓰일 수 있는 말의 단위, 최소 자립 형식 전산학 : 단일의 품사를 갖는 단위 형태소 언어학 : 일정한 음성에 일정한 뜻이 결합되어 있는 말의 가장 작은 단위 전산학 : 사전에 등록되어 있는 색인어의 집합

단어의 형성법 단일어 : 하나의 실질 형태소로 이루어진 말 복합어 : 하나 이상의 형태소로 이루어진 말 예) 땅, 하늘, 메아리, 컴퓨터 복합어 : 하나 이상의 형태소로 이루어진 말 - 파생어 : 실질 형태소 + 형식 형태소 예) 맏아들(맏+아들), 치밀다(치+밀다) - 합성어 : 실질 형태소 + 실질 형태소 예) 과학기술(과학+기술), 은행나무(은행+나무)

사전 사전이란 전자사전의 필요성 전자사전에 포함되는 정보 언어의 어휘적 정보를 저장하는 장소 표제어 + (어휘)정보 표제어 : 형태소 수준(언어학적 의미의 형태소와는 약간 다름) 전자사전의 필요성 일반사전은 컴퓨터가 직접 사용할 수 없음. 컴퓨터가 사용할 수 있는 전자 사전의 구축이 필수 전자사전에 포함되는 정보 품사(part of speech) 정보 연어(collocation) 정보 하위 범주화(sub-categorization) 정보 관용어(idiomatic expression) 정보

전자 사전의 구축 연어 연어 정보를 위한 통계처리 통계적인 방법을 사용하는 이유 주어+동사, 목적어+동사 등 두 개의 어휘 성분이 자주 어울려 사용되는 경우 이러한 단어 쌍의 어울림을 바탕으로 더욱 정확한 의미 파악이 가능 연어 정보는 일반적인 방법을 통하여 수집하기에는 한계가 있으며 말뭉치(corpus)를 기반으로 하여 통계적 처리를 통하여 수집 연어 정보를 위한 통계처리 빈도(frequency): 어휘의 발생 빈도를 말뭉치 전체에서 조사 상호정보(mutual information): 말뭉치에서 사용된 어휘들에 대한 상호정보를 구함으로서 어휘들 사이의 상대적인 관련성을 파악 통계적인 방법을 사용하는 이유 조사 방법이 개인의 주관적인 언어 정보나 언어 지식에 의존하지 않고 말뭉치로부터 근거 자료를 바탕으로 구축된 언어 정보이기 때문에 비교적 개관적일 수 있기 때문

사전의 종류 형태소 분석 사전 변환 사전 생성 사전 입력 문장의 형태소 분석에 사용되는 사전 기계 번역의 변환 단계에서 주로 사용되는 사전 기계 번역에서 번역 대상이 되는 언어와 번역 목표가 되는 언어 사이에는 많은 언어적 그리고 문법적인 차이점이 존재하게 되며, 변환 사전은 이러한 차이점을 해결하기 위하여 구성 생성 사전 목표 언어를 생성하기 위하여 사용하는 사전 1) 어휘와 품사를 포함하는 생성 사전 2) 불규칙 활용에 대한 정보를 담고 있는 불규칙 활용사전

사전과 WordNet 사전의 역할 WordNet 시소러스(Thesaurus) 사전은 시스템의 가장 중심적인 요소이며 실질적으로 시스템의 언어 처리 품질과 기계 번역 품질은 사전에 많이 의존 WordNet 사전의 어휘는 사전 속에서 독립적으로 존재 WordNet은 어휘와 어휘간의 의미 관계를 네트워크로 나타낸 것 사전과 WordNet을 하나의 구조로 통합하는 것이 중요 시소러스(Thesaurus) 통제된 색인언어의 어휘집으로, 개념간의 특정관계를 형식적으로 조직화하여 명시한 것 정보검색, 전자상거래, 전문가 시스템, 자연언어 처리(기계번역, 자동 초록) 등의 여러 분야에 응용

형태소 분석기와 사전 형태소 분석기와 사전 형태소 분석의 개념도 형태소 분석 방법 언어 모델로서의 형태소 분석기 어절에 대한 사전 정보를 적재하기 위하여 어절 내의 사전 표제어를 분석하고 문법적 적합성을 검사 형태소 분석의 개념도 감기는 -> 형태소 분석기 -> 감기+는, 감(다)+기는, 감(다)+기+는 형태소 분석 방법 1) 언어적 최소의 단위인 형태소 단위로 사전 구성 2) 어절을 이루는 규칙성을 형태소 분석 문법으로 작성 3) 대상 어절로부터 형태소 단위로 분석: 사전 참조, 문법 검사 4) 형태소 단위의 사전 정보로부터 어절에 대한 언어적 정보 합성 언어 모델로서의 형태소 분석기

언어 모델링(Language Modeling) 언어 모델링은 언어에 존재하는 규칙성을 찾고 특성화 하는 과정 음성인식(speech recognition), 문자인식(character recognition), 기계번역(machine translation)등의 분야에 이용 언어 모델은 현재의 문맥에서 다음 단어가 올 확률을 줌으로써 가장 적절한 다음 단어를 선택할 수 있는 수단을 제공 P(the thought)=0.045 P(the sought)=0.0125 “the thought”의 확률이 더 높으므로 확률 문법을 이용한 언어 모델은 “the” 다음 단어로 “thought”를 선택

형태소 분석기의 개념도 형태소 분석 문법 tries try+s, v, sg, 3p 형태소 분석기 나는 나 + 는 (I) V + s -> sg, 3p 명사+조사 동사+어미 형태소 분석 문법 tries try+s, v, sg, 3p 형태소 분석기 나는 나 + 는 (I) 날다 + 는 (fly) 나다 + 는 (born) 사전 try : V 나 : 명사 날다 : 동사 나다 : 동사 는 : 조사, 어미

한국어 형태소 분석 방법 형태소 분석에서 다루어야 할 현상들 - 접사 처리 tries -> try + s, digger -> dig + er 읽어라 -> 읽 + 어라, 한국에서 -> 한국 + 에서 (주의) 마이크로 -> 마이크 + 로 / 민주주의 -> 민주주 + 의 - 불규칙 현상 및 음운 현상 하얀 -> 하얗다 + 는 - 복합어 처리 선진한국 -> 선진 + 한국, 미래지향 -> 미래 + 지향 - 미등록어 처리 항공우주연구소에서는 -> <항공우주연구소> + 에서 + 는

한국어 형태소 분석 방법 사전 검색을 통해 어절을 형태소 단위로 분절 법적 적합성 검사를 위해 형태소 분석 문법 검사 "과학자들에게"에 대한 분석 예 1) "과학자들에게" 사전 검색 -> 실패 2) "과학자들에" 사전 검색 -> 실패 3) "과학자들" 사전 검색 -> 실패 4) "과학자" 사전 검색 -> 성공 5) "들에게" 사전 검색 -> 실패 6) "들에" 사전 검색 -> 실패 7) "들" 사전 검색 -> 성공 8) "에게" 사전 검색 -> 성공 9) 문법검사 성공 (명사 + 접미사 + 조사)

한국어 형태소 분석 방법 "나는"에 대한 분석 예 여러 가지 가능성을 모두 분석할 필요 a) 나(I) + 는 b) 날다(fly) + 는 c) 나다(born, come out, happen, . . .) + 는 여러 가지 가능성을 모두 분석할 필요 1) 나는 오늘 형태소 분석에 대한 연구를 진행하고 있습니다. (a) 2) 하늘을 나는 기러기는 가을의 느낌을 줍니다. (b) 3) 싹이 나는 것을 보니 마음이 풍요로워 집니다. (c) 4) 저녁 식탁에 김이 나는 찌게를 준비하였습니다. (d)

형태소 분석의 응용분야 기계번역 철자 오류 검사 및 교정 정보 검색 기타 자연어 처리 - Natural Language Interface to Data Bases - Question and Answering

문법과 파싱 문법 (Grammar) 구문 분석기 (Parser) S: sentence NP: noun phrase - 문장의 구조적 성질을 규칙으로 표현한 것 구문 분석기 (Parser) - 문장의 구조를 문법을 이용하여 찾아내는 process - 문장의 구문 구조는 Tree를 이룬다. 즉, 몇 개의 형태소들이 모여서 구문 요소(phrase)를 이루고, 그 구문 요소들간의 결합구조를 Tree형태로써 구문 구조를 이루게 된다. S: sentence NP: noun phrase VP: verb phrase V: verb N: noun ART: article S NP VP N V ART John ate the apple

Tree Tree의 Notation - Node : Non-terminal node ( NP, VP, .....) - link - root : 한 문장의 구문 Tree의 root 는 S (Sentence) - leaves : Terminal nodes - parent nodes, child nodes, ancestor nodes (모든 node는 그것의 ancestor node에게 dominate 됨)

Grammars Grammar : a set of rewrite rules Context Free Grammar (CFG) : - 각 rule의 LHS(Left-Hand side)가 하나의 symbol로 이루어진 문법 규칙 Grammar Rule 을 이용해서 sentence를 derive할 수도 있고(sentence generation), analyze 할 수도 있음(sentence parsing) (ex) S NP VP NP ART N NP N VP V NP

문맥 자유 구 구조 문법 단어(word) 구 기호(phrase symbol) 문법(grammar) - 언어의 문장을 구성하는 최소 단위 - 문장에 대한 트리 구조에서 단말(terminal) 노드 - 각 단어는 자신의 문법적 기능을 말하는 품사(part of speech)를 가짐 - “John”, “ate”, “an”, apple”: 단어의 예 - NAME, VERB, ART, NOUN: 단어의 품사를 정의하는 품사 기호 구 기호(phrase symbol) - 트리 구조의 비단말(non terminal) 노드에 나타나는 문법적 구조들에 대한 이름 - NP(명사구), VP(동사구), S(문장),… 문법(grammar) - 문장이 되는 단어 열과 문장이 되지 못하는 단어 열을 구분할 수 있는 규칙

문맥 자유 문법(CFG) - 자연언어 문장의 구조를 이해하기 위한 문법 규칙 중 가장 기초적인 방법 - 다시 쓰기 규칙(rewriting rule): 각 규칙은 트리 구조에 나타나는 어떤 구 기호가 다른 어떤 기호들로 다시 구성 될 수 있는가를 정의 - 각 규칙은 ‘기호 – 기호1 기호2 … 기호n (n1)’의 형태를 가지며 왼쪽의 기호를 오른쪽 기호의 연속된 형태로 고쳐서 다시 쓸 수 있다는 의미 - 각 단어는 자신의 문법적 기능을 말하는 품사(part of speech)를 가짐 (note) 1) 문맥 자유 문법은 규칙의 왼쪽에 문맥에 관한 정보가 정의되지 않는다는 점에서 ‘문맥 의존 문법(CSG: context sensitive grammar)’과 구별. 2) 자연언어는 문맥 의존 언어로 보는 것이 타당하나 컴퓨터에 의한 자동 처리 때문에 문맥 자유 문법이 바탕이 됨

Sentence Generation (ex) By rewrite rule S NP VP N VP John VP John V NP John ate ART N John ate the N John ate the apple.

Sentence Parsing Bottom-up parsing vs. Top-down parsing 입력 문장의 단어로부터 시작하여 rewrite 규칙을 backward로 적용하여 S 하나만 나타날 때 까지 적용 - Top-down parsing S부터 rewrite해서 주어진 sentence가 generate될 때까지 적용한다. 만일 모든 가능성을 다 적용해도 그 문장이 나타나지 않으면 parsing fail

Bottom-up Parsing (ex) John ate the apple. N V ART N NP V ART N NP V NP NP VP S S NP VP N V ART John ate the apple

Good Grammar NLP에서는 임의의 문장을 분석해 내어야 하므로 매우 큰 Grammar가 요구된다. (좋은 문법으로써 고려할 사항) 1) Generality : 해당 문법이 cover할 수 있는 sentence의 종류가 다양해야 함 2) Selectivity : 해당 문법이 올바른 sentence와 non-sentence를 잘 구별할 수 있어야 함 3) Understandability : 문법이 복잡하지 않고 문법을 개발하는 사람이나 사용자가 이해하기 쉽도록 simple해야 함 (note) 보통 문법을 개발할 때는 의미 있는 sub tree들의 category를 잘 구별해야 하는데, 이런 sub tree를 구(phrase)라고 함 (ex) 명사구(NP), 동사구(VP) ...... 이 때 이러한 구를 "constituent"라고 한다.

의미 해석 의미해석이란 - 문장 (symbol string) 에 표현된 단어가 의미하는 개념과 문장이 표현하고자 하는 “그 개념들 간의 관계”를 규명하는 것 의미 해석의 어려움 - 인간의 정신 활동에 대한 표현의 어려움 - computational model 구현의 어려움 - real world knowledge 구축의 어려움

의미해석 구문 해석은 되나 의미 해석이 안 되는 것들 - 사람이 사과를 먹는다. (o) 구문 구조 의미적 제약 [먹다 - 사람이 비행기를 먹는다.(x) - 비행기가 사과를 먹는다.(x) 구문 구조 의미적 제약 [먹다 [ agent : 먹을 수 있는 주체 object : 먹을 수 있는 대상 ....]] S NP VP N V 사람 비행기 먹다 사과

의미해석의 필요성 모호한 구문 해석 결과를 해결 Harry broke the glass with the hammer. - 구문 해석 결과 ..... 의미 제약에 의해 [break [agent : Harry object : the glass instrument : the hammer]] - 의미 해석 결과

X-bar Grammar X grammar X Y: specifier Z: modifier X Y X Z X: N(명사), V(동사), Adj(형용사), Adv(부사) X: Np1, Vp1, Adj1, Adv1 X: NP(명사구), VP(동사구), ADJP(형용사구), ADVP(부사구)

Sub-Categorization (예) verb complement 구조 예문 각 단어들은 그 것들을 수식하는 보어(complements)들이 있음 각 단어 들이 가질 수 있는 보어들에 대한 정보를 sub-categorization 정보라 함 Sub-categorization은 구문 분석 시 매우 요긴하게 사용될 수 있다. (예) verb complement 구조 예문 - laugh: empty Jack laughed. (1형식) - find: NP Jack found a key. (3형식) - give: NP+NP Jack gave Sue the paper. (4형식)

Transition Network Grammar 아주 단순한 network grammar는 Finite State Automata(FSA)와 같은 구조 (ex) John ate an apple. - 즉, Initial state와 Final state, 그리고 a set of states와 transition arc들을 정의함으로써 만들 수 있는 Grammar - 그러나, 이와 같은 FSA로는 자연언어를 충분히 표현할 수 없다. Recursive Transition Network이 필요(John regret that I regret that …) 1 2 3 4 5 N ART V

Recursive Transition Network(RTN) 각 constituent마다 network이 정의 (ex) S-net, NP-net, VP-net ... 각 network에서는 recursive하게 자신의 category를 transition arc에 포함하거나, 두개 이상의 network이 서로의 category를 transition arc로 사용하여 정의할 수 있음 (ex) S0 S1 S2 S3 NP verb S : S NP0 NP1 NP2 art adj noun e NP : e : empty transition

RTN과 Push-Down Automata (ex) I believe he died. N VERB N V S-network으로 상기 문장을 parsing하면... current state Input action stack 1. S : S0 I believe he died. 2. S : S1 believe he died. 3. S : S2 he died. push S : S2 4. S : S0 he died. 5. S : S1 died. 6. S : S2 `` pop 7. S : S2 `` - 3번 step에서 "he died"로 S-network을 recursive하게 시도하면서 다시 돌아올 state를 stack에 push하게 되고, 6번 step에서 "he died"가 성공적으로 S로 분석됨에 따라서 stack의 top에 있는 state로 되돌아 오게 됨

Definite Clause Grammar (DCG) DCG는 prolog에 쉽게 구현할 수 있는 Grammar표현 기법이다. - 즉, Input으로 들어온 string을 S로 파싱하기 위해서 우선 Input의 앞부분에서 부터 np부분을 찾고, 그 나머지를 가지고 vp부분을 찾으면 된다. rewrite rule S NP VP DCG in prolog s(Input, Rest) :- np(Input,Rest1), vp(Rest1,Rest).

Features of Words and Constituents 일반적으로 자연언어는 context sensitive한데 CFG로써 context sensitive 한 면을 처리하기 위해서는 CFG를 확장하여 두 constituent가 결합할 때 각 constituent들의 feature를 검사할 수 있도록 해야 함 (ex) 1. This program works well. 2. This programs work well. (*) 3. These program works well. (*) 4. These programs works well. (*) 2,3,4와 같은 비문장을 구별해 내기 위해서는 art와 n, 그리고 v의 수(number)와 인칭(person)을 구별해 주어야 함

Features and Augmented Grammar 수나 인칭을 구별해 주는 방법은 2가지가 있음 1. 각 수나 인칭에 따라 단어 품사를 구별해서 지정 (ex) NP-sing art-sing n-sing NP-plural art-plural n-plural 이 경우, 모든 feature에 대해서 combinatorial하게 품사의 종류가 늘어나게 됨 (ex. NP-sing-person3) 2. 한 단어나 constituent를 feature structure로 표현 (ex) a : (cat art, root a, number sing) peaches: (cat n, root peach, number plural) john : (cat n, root john, number sing, person 3) (NP number ?X) (art number ?X) (n number ?X) - 이 규칙의 결과로 생기는 np의 number는 subconstituent인 art나 n의 number와 같은 값을 갖게 됨

Features and Augmented Grammar (ex) 1. (s tense ?Y) (np number ?X person ?W) (vp number ?X person ?W tense ?Y) np와 vp의 number와 person이 compatible하면 S로 combine할 수 있고 이 때 S의 시제(tense)는 VP의 시제를 따름 2. np number ?X ( art number ?X ) person ?Y n number ?X person ?Y art와 n의 number가 compatible하면 np로 combine하고, 이때 np의 feature값들은 n의 feature값을 갖음

Features and Augmented Grammar (ex 계속..) 3. VP number ?X V number ?X tense ?Y tense ?Y person ?W person ?W NP - V는 그 다음에 나오는 NP의 feature에 관계없이 같이 묶여서 VP로 combine되고, 이 때 V의 모든 feature의 값들이 그대로 VP의 feature의 값으로 됨 * 이 때 단수나 복수가 동시에 되는 단어(예: fish)같은 경우 그 값들을 set으로 만들어 사용함 (ex) fish : [cat, n, root, fish, number, [sing, plural] ] - 이 경우 set에 있는 하나의 element와 match가 되어도 compatible한 것으로 간주하고, 그 값을 상위 constituent의 feature값으로 정함