🤖 Education/2021석사과정

[자연어처리] 4.Grammars and Parsing part2

데이터분석가SIENNA 2023. 8. 14. 13:28

4. Grammars and Parsing part2

 

결과물은 parse tree를 만들어내고, 그것은 문장 사이의 수식관계를 잘 드러낸다.

  • CKY의 복잡성
    • 모든 parse tree를 다 찾는다면 그 개수는 N!
    • PP라는 것은 NP, VP를 다 수식할 수 있다. 어떨 때는 명사를, 어떤때는 동사를 수식(두 개의 규칙이 다 맞다) 뒤에 전치사구가 N개 붙는다고 하면, N의 팩토리얼 개수만큼의 가능성 개수가 나타나게 된다. ⇒ 기하급수적이다. exponential
  • CNF 문법은 문법을 변형해야지만 CKY parser에서 가능하지만 큰 문제는 아니다.
  • 문법적 모호성 : 우리가 모든 가능한 parse tree를 다 찾는다면… parsing 알고리즘 자체가 의미가 없다. 많은 parse tree 중에 맞는 하나를 찾아내는 것이 매우 어렵다. 가능한 해석방법이 너무 많기 때문에 모호성 해결이라는 문제를 중요하게 다루지 않는다.
  • CFG 관련 이슈
    • context-sensitivity
    • 규칙 중 왼쪽 요소에는 엄격한 규칙이 적용된다. 왼쪽 요소의 주변 문맥에 상관없이 rewrite할 수 있다 = 그것이 컨텍스트 프리이니까

S → NP VP

NP → noun PP

np → det Noun

⇒ 그런데 우리가 사용하는 자연어는 context free한가? NO!

  • 촘스키는 문법을 수학적으로 접근하려고 했다.
    • 알파 → 베타 일 때 네가지 형태로 분류할 수 있다. Type 0에 가까울 수록 자유롭다
    • 1) Type 3 (레귤러 문법)
      • a : 하나의 nonterminal
      • b : 베타 부분에도 제약조건이 있다.
    • 2) Type 2 (CFG)
      • a : 하나의 nonterminal
      • b : 제한 X
        ⇒ 제약조건이 없을 수록 모든 종류의 심볼 스트링을 커버할 수 있는 문법을 만들 수 있다. 제약조건이 많다는 것은 그만큼 커버할 수 있는 스트링의 종류가 제한적이다.
        ⇒ CFG는 우리가 maximum으로 활용할 수 있는 형태의 문법이다. 지금 상황에선 이것밖에 못 씀
    • 3) Type 1 (CSG)
      • a : 하나의 nonterminal과 여러개의 terminal의 아무 조합
      • b : 아무조합 가능
      • ⇒ CSG로 문법을 만들면 주어진 문장이 context-sensitivity에 맞는지 판단할 수 있는 알고리즘(Non-decidable)이 없다는 이슈가 존재. 알고리즘으로 판정할 수 없는 문제
    • 4) Type 0
      • a, b : 아무 조합 가능
      • ⇒ Non-Computable 컴퓨터가 계산할 수 없는 문제라는 이슈가 존재

그렇다면 자연어에 context-sensitivity한 형태는 어떻게 처리할까요? → 할수없이 애드옥(?)한 방법으로 처리할 수 밖에 없습니다.

  • Sub-Categorization
    • 어떤 동사들은 특정 인자(argument)를 필요로 하는 경우가 있다. 각 동사들이 가질 수 있는 인자들에 대한 정보를 말한다.
    • (예) 영어 문법에서의 1형식, 2형식
    • (예) reside라는 동사는 뒤에 location phrase가 와야한다.
    → 이것들을 잘 활용해서 문법을 만들면 모호성을 잘 해소할 수 있다.

[parser의 다른 종류들]

  • 하향식 차트 파싱 : Earley’s parser
    • 1970년대에서 카네기멜론대의 Earley라는 사람이 박사학위 논문으로 발표
    • Bottom-up방식인 CKY와는 다르게 top down 방식으로 S라는 규칙에서 시작하는 문법
    • 장점 : CKY 파서보다 빠르다. 하지만 이론적으로 시간복잡도는 O(N3)으로 CKY와 같다. 다이내믹 프로그래밍 사용한다. (자세한 작동원리까지는 몰라도 되고, 이런게 있다. 상당히 빠르다 정도만 알고있기)
  • Tomita’s Parser (=Generalized LR parser 일반화 시킨 LR파서)
    • 1987~8년 쯤 카네기멜론대의 tomita가 박사학위논문으로 발표
    • LR파서(컴파일러에서 사용하는 파싱 알고리즘. 굉장히 빠르다)를 수정한 것.
    • 모호한 문법 처리 가능. 프로그래밍 랭귀지에는 문법에 모호성이 없다. 사람이 만들어낸 언어이기 때문에 문법이 엄격하게 적용 됨
    • 장점 : 빠르다.
    • 단점 : LR 테이블을 만들어야해서 공간이 필요하다.
  • LR parser
    • 문법을 입력으로 넣으면, LR 테이블을 만들어내는 알고리즘이 있다.
    • 테이블을 만들어놓은 다음, 테이블을 이용해 파싱을 하기 때문에 빠르다.
    • 문법이 모호한 경우에는 LR파서가 잘 안된다.
    • 작동원리 예제) I saw a man $
      N V det N
    • → 문장 끝에 심볼로 $ 기호를 넣는다. 0번 스택에서 시작하여 LR테이블을 보고 결정한다. LR테이블은 문법을 보고 컴파일을 해서 자동으로 만든 것이다.

state 0을 본다 : sh4 = 첫번째 요소인 N을 스택으로 Shift하라. 상태를 4로 바꾸어라.

state 4를 본다 : V를 보면 re3 = 3번 규칙을 이용해 reduce하라 (3) 명사를 NP로 reduce하라.

명사를 끄집어내고 (상태가 없어짐) NP로 바꾸어 집어넣는다. 스택의 상태는 0이 된다.

→ reduce가 되면 go to table에 가서 지금의 상태가 뭔지 결정해야 한다.

state 0에서 NP를 본다 : 2 = 상태를 2로 바꾼다.

state 2에서 V를 본다 : sh7 = V를 스택에 넣고 7번 상태로 가라.

state 7에서 det를 본다 : sh3 = det를 스택에 넣고 3번 상태로 가라.

state 3에서 N을 본다 : sh10 = N을 스택에 넣고 10번 상태로 가라.

state 10에서 $을 본다 : re4 = 문법의 4번 규칙을 본다. (4) NP → *det *n

스택에 있는 n det를 끄집어 내서 NP로 바꾸어 집어넣는다. 상태는 7번 상태가 된다.

state 7에서 NP를 본다 : 12

state 12에서 $를 본다 : re7 = (7) VP → *v NP

스택에 있는 v, np를 꺼내 VP로 바꾼다. 상태는 2번 상태가 된다.

state 8에서 $을 본다 : re1 = (1) S → NP VP

스택을 봤더니 VP, NP가 있어서 둘을 빼서 S를 만든다. 상태는 0이 된다.

state 0에서 S를 본다 : 1

state 1에서 $를 본다 : accept = parsing 완료. 이 문장은 문법에 맞다!

  • 프로그래밍 언어에서 사용하는 문법은 모호하지 않기 때문에 re6, sh6 이렇게 두개씩 나올 수 없다. LR테이블의 7개 문법은 모호한 문법이기 때문에 두 개씩 나옴 (re6 액션을 취할수도 있고, sh6 액션을 취할 수도 있는 것)
  • 토미타 이후에는 파서를 만들겠다고 도전한 일이 적었다. 더이상 빨라봤자라고 생각했기 때문. 이론적으로 토미타 파서의 시간복잡도는 O(N3)으로 그렇게 빠르지 않다. 하지만 이상한 문법이 아니라면 일반적인 자연어처리에는 토미타 파서가 실제로 제일 빠르다.
  • 최근에는 딥뉴럴넷을 이용해서 LR파서와 결합한 후 가장 그럴듯한 parse tree 하나만 먼저 찾는 것에 집중하고 있다.
    • 단어와 구성요소의 특징(통일기반 문법형식주의)
      • context sensitive한 면을 어떻게 처리할 것인가? 문법 자체의 formalism은 context free한 면을 갖게 만들고, 약간의 feature rule 몇개를 부착하면 처리할 수 있다.
    • 기능 및 강화문법
      • 관사, n, v의 수, 인칭을 구별해 주어야 한다.
      1. 이런 것들을 반영하려면 제일 무식한 방법은 아예 품사를 따로 만드는 것이다. 이 경우 품사의 개수가 어마어마하게 늘어난다.
      2. 단어에서부터 feature structure로 표현한다. (특성값을 문법에 반영하는 방법)plural 복수
      3. tense 시제
      4. sing = singular 단수

→ 어느 것 하나가 단수면 단수로 맞추고, 복수면 복수로 맞추는 등

  • (예1) 파싱을 할 때 NP, VP가 나오면 결합해서 S를 만들어야하는데, 무조건 결합하는 것이 아니라 조건을 만족하는 경우에만 결합하도록 한다. 여기 예시에서는 NP와 VP의 number가 X로 같아야한다는 조건이다. person도 같아야 한다. tense feature는 동사의 tense feature가 그대로 올라간다. feature 값이 같은지 체크한다. feature값 체크하는 것은 항상 constant time이다. feature의 개수가 몇 개 없으니까 알고리즘의 복잡도에 크게 영향을 주지 않는다.

→ number, person이 같아야만 NP와 VP가 결합할 수 있는데, 그 결과 만들어지는 S의 tense feature는 동사의 tense feature가 그대로 올라간다.

  • (예2) NP는 항상 person 정보를 갖는다. art의 넘버와 명사의 넘버가 같아야한다. 그러면 NP를 만드는데, NP는 art와 n의 넘버feature가 그대로 올라가고 person정보는 art에 없으므로, n에 있는 person feature가 그대로 올라간다.
  • (예3) VP → V NP 일때, NP에 아무런 조건이 없으므로 결합이 가능하지만, 동사에 있던 수, 시제, 인칭 정보가 그대로 VP로 올라간다. 사전에서부터 feature정보가 붙어있어야 한다.

⇒ 이렇게 하면 CFG 형태로 rewrite rule을 만드는데 CSG처럼 feature를 이용해서 context-sensitivity한 점을 반영할 수 있다는 것. 그리하여 CFG를 써도 문제가 없다.

  • 결론
    • 구문 구조는 수식관계를 가지고 있기 때문에 구문 구조를 찾아야만 의미 파악에 도움이 된다.
    • 예) John ate the spaghetti with meatballs with chopsticks.
    • CFG는 자연어의 문법을 정의하는데 사용할 수 있다.
    • 다이나믹 프로그래밍 알고리즘을 통해 싱글 구문 분석 트리를 계산할 수 있다. parse tree 하나 찾아내는데 O(N3), 모든 parse tree를 찾아내는데는 exponential time이 소요된다.

 

N-gram part1 (통계적 언어처리)

 

  • Rule-based NLP
    • 규칙을 적용해서 자연어처리를 하려고 노력해왔다. 이것은 규칙을 업그레이드, 확장하는데 문제가 있다. 나중에 만드는 규칙이 이전의 규칙과 충돌이 생긴다. 또한 깨지기 쉬우며, 모호성 문제가 있게 된다.
  • Corpora : 방대한 양의 text를 모아서 그 데이터로부터 확률치를 뽑아 언어모델을 정리해보자는 통계적 방법
    • 90년대 까지는 데이터 얻기가 힘들었다. 일일히 타이핑
    • 90년대 말부터 인터넷이 활성화되면서 인터넷상의 많은 문서들을 크롤링할 수 있게 되었다.
    • Brown Corpus(1963-64) : 서지학자들이 그 시대의 언어연구를 위해 만든 말뭉치 데이터. 100만 단어짜리 코퍼스를 머신 리더블 하게 만듦. 그 당시의 표준 영어 (지금은 100만 단어는 아무것도 아님..ㅎㅎ지금은 조 단위임)
  • Tagged Corpus : 코퍼스를 가공한 것. 품사의 정답을 태깅
    • Tree tagged corpus : 유펜의 컴퓨터사이언스 연구진들이 만든 방대한 treebank. parse tree를 손으로 일일히 태깅한 것.
    • semantic code tagged corpus : 의미 태깅된
    • MT : machine translation
    • Parallel corpus : 영한 기계번역을 하려면, 영어문장과 번역된 한국어 문장을 일일히 정렬해야하는데 그러한 형태의 corpus를 지칭한다.
    ⇒ 정답을 태깅하는 것은 어려운 작업이지만, 규칙을 만드는 것보다는 쉽다. 정답을 태깅 후 통계적인 방법으로 학습시켜 자연어처리를 하면 자연스럽게 할 수 있게 된다.
  • 기본 통계 이론
    • 조건부확률 : 비가 왔을 때 우승할 확률은 비도 오고 우승할 확률을 비가 올 확률로 나누는 것이다.
    • 조건부확률은 우리가 의사결정을 할 때 중요하다. 입력된 상황의 어떤 특정 조건들을 우리가 찾을 수 있다면 그 조건 때문에 정확한 판단을 내리는데 도움이 된다.
    • 예시 : 10분전에 비가 왔을때 캘리포니아에 비가 올 확률은 무엇인가? (원래 캘리포니아에 비가 올 확률은 0.01이다)
    ⇒ 어떤 조건이 붙는다면 확률은 드라마틱하게 높아진다. 그 조건을 찾을 수 있다면 !

-   A, B가 각각 독립적인 사건일 경우 (서로 관련없을 경우)

동전 두개를 던졌을 때 앞면, 뒷면이 동시에 나올 확률 = 0.25

-   Harry가 비가올 때 이길 확률 0.15와, 

이길 확률 \* 비가올 확률을 곱했을 때 나오는 값 0.06이 서로 다르기 때문에 

두 사건은 독립적이지 않다. 

-   독립적인 이벤트라면 조건부확률을 써도 별 도움이 안된다.
  • 언어 모델
    • hard binary model : (Type3, Type2) 문법에 맞으면 맞고 아니면 틀린 문장. yes or no
    • probabilistic model : 얘는 92% 맞다, 32% 맞다 등 점수로 제시하여 비교가 가능한 문장
    → 어떤 것이 더 나은 선택인지를 제시해준다. 어떻게 하면 언어를 확률값으로 표현할 수 있을까? 정확한 확률 분포를 지정하려면 모든 언어문장의 합은 1이 되어야 한다.
  • 언어 모델로 할 수 있는 것들
    • 음성인식 : 소리는 비슷하지만, 점수가 더 높은 인식값을 선택할 수 있도록
    • OCR(문자인식)
    • 기계번역 : 번역한 결과가 더 그럴듯한 것에 점수를 매길 수 있다.
    • 생성 : 생성기가 만들어 낸 문장 중 점수가 더 높은 걸 선택
    • 스펠링 커렉션 : 틀린 문장의 단어가 사전에 있을 지라도 문맥상 맞지 않는 틀린 단어를 체크해낼 수 있다.
    • 완료 예측 : 다음에 나올 단어가 무엇이냐? 예측이 가능!