[NLP] Text Preprocessing

대학교 2학년때 배웠던 과목 '오토마타와 형식언어론'

동기들한테 오토마타 듣는다고 하면, 다들 힘들겠다며 측은하게 바라보던 '그 과목'

배울때는 대체 이걸 어따 쓴다는거야.. 의문 투성이였지만, 막상 여러군데에서 사용되니 듣기 잘했다는 생각이 든다.

생각해보면 그냥 아묻따 배운 나 자신이 후회되긴 한다. 좀 어디에 들어가는지 찾아보면서 공부할걸.

 

• Text Preprocessing: Regular expression? → 텍스트 패턴을 지정하기 위한 표현
  • 만약 문단에서 Happy가 나온 수를 측정한다고 생각해보자.
  • 근데 Happy, HAPPY, Happiness등 다양한 모양으로 분포되어 있을 수도 있다.
  • 그래서 요런걸 Regular expression(REX)를 사용하여 사전 정의된 패턴을 기반으로 관련 단어를 추출한다.
  • REX는 Text tokenization과 Text normalization에 꼭 필요한 필수 요소이다.
• REX
  • Disjunction and Range
    • Disjunction: [hH]appy → happy or Happy, [h|H] → I would be happy if I had a donut
    • Range: [0-9] → Any digit, [a-z] → Any small letter
  • Negation (^)
    • Negation in Disjunction: [^hH]appy → sappy (hH를 제외한 문자)
    • Negation in Range: [^A-Z] → a, b, c... (대문자를 제외한 문자)
    • Negation in Negation: [^^] → Not a caret (^를 제외한 문자)
    • Negation: H^a → Is H^appy to find me? 일반문자로 인식
  • happy* → "happ", "happyyyyy" (y가 안올수도 있고, 더 올수도 있고.)
  • .appy → appy앞 아무 character가 들어가도 상관없음 "Can you grab a snappy reply?"
  • happy+ → "happy", "happyyy" (y가 1번 이상)
  • happy? → "happy", "happ" (0번이나 1번 나온다.)
  • happy{1} → "happy" (숫자만큼)
  • happy{0, 1} → "happy", "happ" (숫자 있는 것 만큼)
  • .a(ppy)? → "a", "appy", "snappy" (괄호랑 .의 합작 괄호안에 문장이 한번에 처리. 
  • Anchors: 문자열의 위치를 기준으로 패턴을 매칭하게 만든다.
    • ^: 문자열의 시작
    • $: 문자열의 끝
    • \.: 마침표 . 자체 (특수문자 아님)
    • ^Happy: 문자열의 시작에만 "Happy"가 있어야 한다.
    • Happy\.$: 문자열의 끝에만 "Happy."가 있어야 한다.
    • 근데 만약 the같은 단어가 탐지가 될까? 왜냐고? other같은 단어가 있기 때문.
    • 요런 문제들을 해결하기 위해서 다시 Finite State Automata를 도입한다. (전 게시글 확인)

 

우리는 REX 기반 FSA를 설계한다면 다양한 NLP에서 적용 가능할 것이다.

1. 문자나 문장이 match한다면 start state에서 시작한다.
2. 다음 item이 다음 state 상태와 매칭된다면, 다음 state로 이동한다.
3. Repeat (만약 이동가능하지 않으면 STOP, 만약 멈춘 위치가 final state면 accpet하라.)

그리고 FSA는 Non-Deterministic (NFA)도 있는데, 쉽게 입실론 transition이 있냐 없냐로 나눌 수 있다. 그니까 transition이 일어나기 전 단계의 state가 긴가민가 하면 multiple choice가 있다고 생각하면 된다. 또, 동일한 입력으로 이동할 수 있는 state가 여러곳이면 NFA라고 볼 수 있다.

중요한 점 → 모든 NFA는 DFA로 convert 가능하다.

 

Finite State Transducers (FSTs)

FSA에서 출력이 있는 버전이라고 생각하면 된다. 얘도 마찬가지로 Determinstic, Non Determinstic으로 나뉜다.

FST는 형태소 분석에 유용하다.

fox, cat, goose 등 여러가지가 있겠다만,

foxes를 예로 들면 형태소를 분석해서 input: foxes → output: fox+N+PL(여우 + 명사 + 복수형)을 반환할 수 있다.

여기서 잠깐, a:b이면 a가 입력이고 b는 출력이다.

fox를 따라 가다가 입실론 transition으로 N이 붙혀지고, 마지막으로 input이 s니까 PL이 붙혀져서 accpet된다.

그렇다면, 얘도 마찬가지로 모든 Non Determinstic FST는 Determinstic FST로 convert 가능할까?

그렇지 않다.

이 친구는 출력이 비결정적 이기 때문에, 대부분 DFST로 convert 할 수 없다.