분류없음2007/05/25 12:26


자연언어 분석의 중요한 한부분인 파싱에 대하여 발표를 하였다. -0-;;;

자세한 내용은 없지만 ... 파싱이란 무엇인지? 파싱 기법에는 어떤 것들이

있는지 알수 있을 것이다. ~~


Natural Language Analysis
Content : parsing
Speaker :  Lee Joo Ho
05/16/07 wed NLP Lab. seminar 6th
파싱(parsing)?
여러 종류의 우선 규칙에 의해 입력 문장을 분석하여 문법적 구조를 구하는 과정
자연언어처리의 여러 응용 시스템을 구현하는데 있어서 그 성능을 좌우하는 매우 중요한 처리 과정

목차
자연언어 문법과 파싱
문장의 트리구조
문맥 자유 구구조 문법
하향식 파싱과 상향식 파싱
자연언어 구조의 모호성
부가 전이망(ATN)문법
전이망과 문법
순환 전이망 문법
아크의 유형
순환 전이망 문법을 이용한 하향식 파싱
부가전이망 문법
차트에 의한 파싱
그래프로 표현되는 차트
삼각 테이블로 표현되는 차트
발전된 언어 이론과 파싱
Q&A
자연어 문법과 파싱
자연언어 문장 구조를 컴퓨터로 분석하기 위해 고려해야 할 문제
문법:언어에서 허용되는 문장의 구조를 형식적으로 정의하는 체계
파싱 알고리즘:컴퓨터에 의해 처리 가능한 절차적인 방법
문장의 트리 구조
문장 구조에 대한 가장 일반적 표현 방법
전체 문장의 부분 구조와 그 부분 구조가 어떤 구조로 결합되는지 도식으로 표현
 
문맥자유 구구조 문법(1/3)
자연어 문장의 문법적 구조를 다룰 때 기초가 됨
자연어 문장에 대한 트리 구조 를 구성하기 위해 정의 되어야 하는 요소들
단어
문장을 구성하는 최소 단위
문장에 대한 트리 구조의 단말 노드에 나타난다.
문법적 기능을 말하는 품사를 가진다
구기호
트리 구조의 비단말 노드에 나타나는 문법적 구조들에 대한 이름
문맥자유 구구조 문법(2/3)
문법
단어의 나열이 문장인지? 아닌지? 구별을 위해 정의된 규칙들의 집합
문법 규칙을 쓰는 가장 기초적인 방법은 다시 쓰기 규칙의 모양을 가지는 문맥자유문법(cfg)이다.
정의된 규칙에 의해 각 규칙은 어떤 구 기호가 다른 어떤 기호들의 조합으로 구성되는지 정의
규칙들은 기호 <- 기호1,기호2,기호n(n) 형식
구구조 문법(phrse structure grammar)
자연언어 문장의 문법에 대해 품사 기호, 구 기호를 이용하여 cfg형태로 기술한 것
문맥자유 구구조 문법(3/3)
자연언어는 문맥의존 언어라고 보는 것이 타당 하지만 컴퓨터에 의한 자동처리를 목표로 할 때는 문맥 자유문법으로 기본 틀을 마련,문맥 의존적인 요소를 반영 하는 것이 자연언어처리에 일반적인 방법

하향식 파싱과 상향식 파싱
파싱(parsing)
입력된 문장의 구조를 밝히는 과정
파서(parser)
파싱을 목적으로 만들어진 입력 문장에 대한 트리 구조를 구하는 프로그램
하향식 파싱
문장 기호 S로부터 다시 쓰기를 반복하여 단어들의 나열인 문장을 얻는 방법
상향식 파싱
각 단어를 품사기호로 변환, 품사기호를 다시 쓰기 하여 S를 구한다
자연언어 구조의 모호성(1/4)
모호성
문법 규칙에 따라 문장의 구조를 해석 할 때 두 가지 이상의 다른 의미의 구조로 해석 될 수 있는 성질
문법 규칙에 나타나는 모호성은 매우 해결하기 어렵고 구현된 시스템의 성능을 좌우하는 중요한 문제가 된다.
문장 구조를 해석한 트리가 달라지면 전달되는 의미도 달라진다.

자연언어 구조의 모호성(2/4)
S  ← NP
NP ← NAME ART NOUN
NP ← NP PP
VP ← VERB NP
VP ← VP PP
PP ← PREP NP
“John” NAME
“saw”  VERB
“Mary” NAME
“in”   PREP
“the”  ART
“park” NOUN
자연언어 구조의 모호성(3/4)
문법에 의해 문장 구조에 나타나는 모호성은 한 문장에서 중복 될 수 있다.
단어 품사에 대한 두 가지 이상의 다른 품사정의에 의해 비롯되는 모호성 역시 아주 빈번한 현상이다.

자연언어 구조의 모호성(4/4)
S  ← NP  
NP ← ART NOUN
NP ← ADJ NOUN
NP ← NOUN
VP ← VERB
VP ← VP NP
VP ← VP PP
PP ← PREP NP
“time” NOUN,ADJ
“flies” NOUN,VERB
“like” VERB,PREP
“an” ART
“arrow” NOUN
부가 전이망(ATN) 문법(1/2)
자연언어 문법을 방향성 그래프를 이용하여 정의하고 입력 문장을 하향식으로 파싱하는 문법(?)
문법 이론이라기보다 전통적인 전산학적 도구
전이망(?)
유한상태기(FSA:finit state automata)를 자연언어의 문법을 기술하기 위해 이용한 도구
상태(state)를 표현하는 노드가 존재
상태와 상태 사이에는 이름이 붙어있는 아크가 두 상태 사이의 전이 방식을 규정
부가 전이망(ATN) 문법(2/2)
상태 노드 사이를 적절한 아크를 따라 진행하여 문장의 구조가 완성 되도록 전이망을 통과하는 전체 과정이 파싱 과정
순환 전이망 문법(1/3)
자연언어의 순환성을 전이망을 통하여 표현하기가 어렵다.
순환성?
어떤 대상을 정의하기 위해 그 대상 자체가 다시 사용되는 현상
example) VP ← VP PP
자연언어 문법의 순환적 특성을 아주 단순 하면서도 효과적으로 표현 하도록 설계한 문법


순환 전이망 문법(2/3)
하나의 매우 복잡한 전이망 대신 여러 개로 분리된 전이망의 집합으로 문법을 정의
필요에 따라 아크에 다른 전이망의 이름을 지정
전이망들 사이의 순환적 호출을 허용
표현력 크게 증가
각 전이망은 고유의 이름으로 표시
아크에는 단어의 품사뿐 아니라 독립된 전이망의 이름이 표시 될 수 있다
순환 전이망 문법(3/3)




   문장 S와 명사구 NP에 대한 순환적 전이망

S와S1사이 ,S2와S3사이의 전이는 NP 전이망을 성공적으로 통과했을 때만 가능하다
아크의 유형
품사 아크
품사이름이 붙여진아크 : 아크에 표시된 품사와 같을 때 성공적으로 상태 전이
단어 아크
특정 단어 문자열이 아크에 표시된 경우 : 특정 단어가 요구되는 특수한 상황을 나타내는데 사용
호출 아크
전이망의 이름이 붙여진아크 : 전이망을 호출하여 성공적으로 통과하고 돌아와야만 상태가 전이된다.
분기 아크
Jump라고 표시된 아크 : 아무 조건 없이 다음 상태로 전이
복귀 아크
pop라고 이름이 붙여진 아크 : 전이망에서 성곡적으로 벗어나게 됨을 나타내는 아크
순환 전이망 문법을 이용한 하향식 파싱(1/4)
순환 전이망 문법의 문장구조 해석방법은 하향식 파싱 방법
파싱 진행 상태를 기술하기 위해 알아야 할 3가지 용어
현재 위치 : 파싱하고자 하는 문장에서 아직 파싱되지 않은 문장의 부분의 시작위치
현재 노드: 전이망의 전이 과정에서 현재 위치하고 있는 노드
복귀점 : 다른 전이망에서의 호출로 현재 전이망에 들어왔을 경우, 현재 전이망을 성공적으로 통과 후 복귀 아크를 통해 돌아가야 할 노드. 복귀점은 스택 방식으로 기록된다.
순환 전이망 문법을 이용한 하향식 파싱(2/4)
파싱은 현재 노드에서 적절한 아크를 따라 전이망을 통과 하면서 진행
분기 아크는 무의미하게 보일수도 있지만 백트래킹(backtracking)과 함께 이용될 경우, 문법적 대안을 편리하게 표현하는 방법이 된다.
예문에서 사용될 단어들의 품사를 다음과 같이 가정
 art : “the”,“a”
 number : “one”
 pronoun : “he”,“she”,“it”,“one”
 adj : “wild”,“green”
 noun : “dog”,“man”,“saw”,“green”
 verb : “crid”, “saw”,“broke”, “faded”, “man”


순환 전이망 문법을 이용한 하향식 파싱(3/4)






 
순환 전이망 문법을 이용한 하향식 파싱(4/4)
스택을 이용하는 순환 문법
새로운 전이망으로 이동되는 경우 성공적으로 작업이 끝난 후 복귀점 기억을 스택을 이용하여 해결하는 방법
비결정성과 백트래킹
상태에서 다른 상태로의 전이가 두 가지 이상 존재 할 때 상태전이가 실패 할 경우 진행 상태를 돌이키기 위해 백트래킹 필요
비결정성은 이러한 한 상태에서 다른 상태로의 전이가 유일하지 않은 성질을 의미한다.
비결정성이 백트래킹을 필요로 하는 근본 원인
부가 전이망 문법
순환 전이망 문법의 기능 확장
파싱이 진행되는 동안 수집 가능한 문법적 정보들을 보관, 특정문법 조건들을 검사할 수 있는 기능을 보강
순환 전이망 문법은 파싱이 성공적으로 끝나거나 그렇지 않은 경우만 판별

문법 구조의 생성(1/5)
대부분의 자연언어처리에서 파싱이 진행되는 동안 입력 문장에 대한 트리 구조와 같은 문법적 구조와 시제를 비롯한 여러 가지 문법 정보를 결과로 얻고자 한다
레지스터
문법적 정보를 얻는 정보 저장 도구
순환 전이망에 레지스터를 조작하는 기능을 부가한 것이 바로 부가 전이망
부가 전이망의 각 아크에는 조건 검사 항목과 행동 항목 두 가지가 함께 정의된다.
문법 조건의 검사 (2/5)
실용 규모의 문법인 경우 매우 많은 수의 규칙이 필요
규칙을 체계적으로 정리하여 쓸 수 있는 방법이 중요함
영어에서는 수와 인칭의 일치가 되는 문장 만이 옳은 문장으로 사용됨
명사구에 포함되는 관사와 명사도 수가 일치해야 한다
ex) “a dogs”,“a dog run” 등

문법 조건의 검사(3/5)
문법적으로 옳지 않은 문장인지 판단 할 수 있어야 한다.
옳지 않은 문장의 결과 구조를 구할 수 없어야 한다
자연언어에서 나타나는 여러 가지 문법적 제약을 정확히 기술해야 한다.
바람직한 해석을 최대한 배제
이러한 조건들을 문법 규칙에 조건으로 부가하는 방법이 부가 전이망 문법이다
문법 조건의 검사 (4/5)
단순환 순환 전이망 문법으로는 아래 문장들의 옳고 그름을 판별하기 위해 모든 경우에 대한 상태,아크,새로운 전이망이 별도 추가 되어야함
옳지 않은 문장
“A wild dogs cries.”
“John love a dog”
옳은 문장
“The wild dog cried.”
“The dogs love him”
“Jonh loves the wild dog”

문법 조건의 검사 (5/5)
표의 각 항목은 아크에 부가된 문법 조건 검사와 구조 생성을 위한 동작을 표시 한다
차트에 의한 파싱(1/2)
차트(?)
파싱의 진행 과정을 기록하는 일종의 테이블(이차원적 자료구조)
차트 파싱(?)
차트를 기본 자료구조로 이용하는 파싱 방법
구구조 규칙을 사용하여 부분적으로 완성되는 구조들을 모두 차트에 기록하는 과정의 연속
상향식(bottom up)파싱에 많이 이용
CKY(Cock-Kasami-Younger)방법이 대표적
차트에 의한 파싱 (2/2)
“He saw the pretty girl”의 문법 정의
규칙1 NP <- ART ADJ NOUN
규칙1 NP <- ART NOUN
규칙1 NP <- PRON
규칙1 NP <- VERB
규칙1 NP <- VERB NP
규칙1 NP <- NP VP
(PRON,“he”)
(VERB,“saw”)
(ART,“the”)
(ADJ,“pretty”)
(NOUN,“girl”)
그래프로 표현 되는 차트
그래프 방식으로 표현된 차트



각 노드는 입력 문장의 단어들 사이의 위치 번호
아크는 문장의 단어들과 완성되는 모든 서브 트리(tree)


그래프로 표현 되는 차트
그래프의 오른쪽 기호들이 차례로 모두 일치되면 규칙의 왼쪽 기호를 갖는 새로운 중간 구조를 표현하는 아크를 생성
개념적으로 차트 파싱에서는 현재의 차트에서 일치 가능한 모든 문법 규칙들이 동시에 처리 된다.
최종적으로 소용없게 될 여러 가지 중간 구조들도 생성될 수 있다
그래프로 표현 되는 차트
그림에 표현된 아크와 표기된 항목은 여러 중간 구조들 중 최종적으로 유효한 것들만 보여준다
<1,2,S <- NP.VP>
<2,3,VP <- VERB.NP>
<3,4,NP <- ART.NOUN>
<3,4,NP <- ART.ADJ NOUN>
<3,5,NP <- ART ADJ.NOUN>
최종적 문법 구조를 완성하기 위한 활성 상태의 아크 생략
완성된 중간 구조이지만 최종적으로 유효하지 않은 아크 역시 생략
<2,3,VP <- VERB>

삼각 테이블로 표현되는 차트
삼각 테이블로 표현된 차트



문장을 이루는 단어의 개수가 n개일 때 n*n의 상위 삼각 테이블로 표현될 수 있다
삼각 테이블로 표현되는 차트
W1,W2,W3,Wn  <-입력 문장의 단어 순서
Ci,j(i<j)는 단어 Wi+1 Wj까지에 대한 파싱의 중간 결과를 표현하는 서브 트리에 담는다
대각선의 초기 상태
각 셀 Ci-1,i(1<i<n)에 W1,W2,W3,Wn 이 순서대로 놓인 상태
발전된 언어 이론과 파싱
전이망 분법,파싱 차트에 의한 파싱 방법
전산학적 입장에서 개발된 문맥 자유 문법에 기반한 파싱도구
언어학적 입장의 문법 이론
GPSG,HPSG,LFG등
수고 하셧습니다!!!

Q&A

작성자: 강원대학교 NLP Lab. 이주호
Posted by 이주호
TAG

티스토리 툴바