[자연어처리] 2주차 복습 #2

어떠한 자연어 묶음을 정규식으로 표현한다면

[]안에 or operator other 이라는 글자가 분류되지 않음 / 마지막 "the."로 바꿔야 함

 

other 이거는 word the만 잡고 싶다고 가정함.

잡으면 안되는데 잡았기 때문에 : False Positive

잡아야 하는데 잡지 못한 것 : False Negative

 

Fasle positive를 줄이는 것은 Precision을 높이는 것

Recall을 높이는 것은 False negative를 낮추는 것

(이 부분 추가 공부 필요)

<간단한 복습 끝>

-------------------------------------------------

regular expression을 computation model로 바꾸는 것이 중요

여기서 말하는 computation model은 Finite state automata

Finite state automata가 Regular expression을 계산 모형으로 표현하기 위하여 사용하는 것인 그 자체라고 생각하면 안됨.

finite state automata가 더 넓은 범위임.

 

계산 모델을 알고리즘화 하는 것이 목표임

 

왜 배워야 하는 가

• 정규식은 정규식일 뿐, 계산 모델로 바꿔야 하기 때문임
  • 정규식을 표현하는 오토마타
• 코드적으로 구현이 쉬워짐 (패턴 매칭에 많이 쓰일 수 있음)

FSA (Finite State Automata)의 구성 요소

• state
• edge (arch)

작동 방식

• StartState에서 user input이 next state에 transition으로 갈 수 있는 input이라면 이동 시작
  • User input을 전부 받았는데 현재 내 상태가 final state라면 accept, 아니라면 reject

표현하는 regular expression은 baa+!

 

Transition이 없다면 accept 하지 못함 (Input을 소비하지 못하고 머뭄)

조건 input을 모두 사용했을 때 final state인 지를 확인해야함

 

메모리가 충분하다면 FSAs를 table 형태로 유지하고 table 기반으로 accept/reject 판단도 가능

 

Deterministic VS Non-determinisitic FSAs

 

• Deterministic FSAs : 갈 수 있는 Path가 하나
• Non-Determinisitc FSAs : 갈 수 있는 Path가 2개 이상

Non-Deterministic FSAs가 더 복잡한 구조

• Tranisition path가 여러 개
• accept, reject 판단하기 더 복잡

Non - Determinstic FSAs의 경우 해결 방법은 두 가지이다.

1. Non Deterministic을 transform Deterministic을 한다.

2. Non Deterministic을 Graph라 생각하고 DFS, BFS를 통하여 한다. 이것을 통하여 accept인지 확인함

 

탐색 알고리즘이 제대로 작동하기 위하여 가정을 하고 가야함.

• Finite State Automata가 accept하는 path가 적어도 하나 FSAs에 있어야 함
• accept가 안되는 path도 있어야 함
• No paths through the FSA lead to an accept state for an item not in the language

해당 과정을 안하고 돌리게 되면 DeadLock 같이 걸려서 빠져 나올 수 없음

해당 예시의 경우 q2에서 a가 갈 수 있는 경우가 2가지가 된다.

q3로 전이되거나 해당 q2에서 머무는 경우이다.

이 경우 input이 갈 수 있는 경우가 2가지 이므로 2가지 경우에 대해서 전부 탐색을 진행하여 Final state를 찾아내야 한다.

따라서 이 경우 Backtracking하여 전이되는 곳을 바꾸며 이 경우 input index 또한 다시 바뀌어야 한다(input 값을 소모시키지 않음)

 

 

간단 요약

• FSA는 정규 언어를 기술하는 계산 모델
• FSA의 언어에 입력 항목이 속하는 지 확인하기 위해서, 시작 상태에서부터 최종 상태까지 순차적으로 처리하면 됨 
• FSA의 상태 전이는 표를 사용하여 표현 가능
• FSA는 결정적이거나 비결정적

Finite State Transducer, FSTs (변환기)

 

• 두 개의 sequence가 있는데, 얘네가 mapping이 되냐 안되냐 이것을 탐색할 때 주로 사용
• Transition 부분에서 확장
• 문자를 Generate 하는데 중점, matching이 되냐 / 안되냐

q0의 경우 input을 소비할 시 ouput으로 b가 나와야 함

간단한 정리

두 개의 finite state transducer를 합칠 수 있음 / 위 그림은 해당 내용의 예시 그림

Inversion : 이 부분의 경우 설명이 굉장히 간단함, 한국어 영어 변환기가 존재한다고 할 때 반대로 작동시키면 영어 한국어 변환기로 사용 가능함.

 

Determinisitc FSAs (=sequential transducers)

Tranducer에선 모든 non-determinstic을 deterministic으로 바꿀 수는 없음

FST는 형태소 분석에도 사용할 수 있다

영어 동사에 대해서 형태소 분석을 하는 변환기

• 교수님이 생각하신(제시해주신) 의문이라고 생각될 수 있는 부분
  • merging을 분석한다면 merge +V +PresPart(현재 분사)가 될텐데, 그렇다면 merging을 형태소 분석하기 위해선 merge라는 동사에 대해서 이미 알고 있어야 하나?

해당 부분의 설명이 될 수 있는 부분

 

해당 파트의 간단한 예시는 다음과 같음

fox에 대해서 반응을 함 (output을 반환) / 그 이후 epsilon: +N이 나오게 됨

epsilon:+N에 대해서 반응하는 경우 input은 소비하지 않고 output +N만을 출력하게 됨

이때 의문 가질 수 있는 부분이 fox + N 이 되게 되는데 이 경우 e가 사라지게 된다. 여기에 대해서 교수님 께서는 Rule base의 방법으로 Rule을 통해서 해결해야 한다고 말씀해주셨다.

 

FST의 간단한 요약

• FST는 두 집합 간의 매핑을 기술하는 FSA
• 모든 비결정적 FSA는 결정적 버전으로 변환될 수 있지만, 모든 비결정적 FST는 그렇지 않음
• 기반이 되는 FSA가 결정적인 FST를 순차적 변환기라고 함
• FST는 형태소 분석에서 유용