5 1 The Spelling Correction Task
https://youtu.be/iYFqYL9RsRs

image
image
image

5 2 The Noisy Channel Model of Spelling
https://youtu.be/q6BFerSaUEA

image

원래의 단어가 noisy channel를 거쳐 noisy word가 될수 있다고 가정하고 noisy word (spelling이 맞지 않는 단어)를 가지고 원래 어떤 단어가 되어야 하는지 추측하는 과정을 보여주고 있다. 

image

x 는 misspelled된 잘못된 단어이다. 잘못된 단어 x가 주어진 상태에서 원래 단어 w일 확률을 구한다. 이를 beyes rule을 이용 변형하면 두번째 공식이 되고 여기서 P(x)는 최대값을 구하는 과정에서 중요하지 않으므로 생략할수 있다. 

image

결과적으로 나온 맨 밑줄의 공식에서 P(x|w)를 channel model, error model이라고 한다. P(w)를 language model이라고 한다.

image
image

기존 edit distance는 insertion, deletion, substitution 만을 이야기 했다. Damerau-Levenshtein은 여기에 transposition을 추가 했다.

image

“acress” 의 edit distance 1의 예

image

 80%의 spelling 문제는 edit distance 1 안에서 발생. 대부분은 edit distance 2안에서 발생한다.

image

이전 강의에서 배운 기존의 language model을 사용한다.

image

unigram을 이용한 language model을 보여주고 있다.

image
image
image
image

confusion matrix의 예를 볼수 있는 곳

image

이부분은 잘 이해하지 못했다. (원래 논문 https://www.aclweb.org/anthology/C90-2036)

image

confusion matrix를 이용 channel modle의 확률을 구하고 language model을 통해 구해진 확률을 곱하면 최종의 확률을 얻을수 있다. 

image

한 단어(이 강의에서는 unigram을 language model로 사용)의 철자들을 이용해 얻은 확률보다 때로는 bigram을 이용해 보완하면 보다 좋을 결과를 얻을수 있는 것을 보여주고 있다.

image

자신이 만든 모델을 평가하고 싶을때 참조사용할만한 웹페이지를 보여주고 있다.

5 3 Real Word Spelling Correction
https://youtu.be/bZNU2FwTXDc

image

실제 존재하는 단어로 misspelled되는 경우가 전체 misspelled 문제의 25 – 40%를 차지한다. 예를 들어 minutes를 사용해야하는데 minuets를 사용하는 경우

image
image

단어 하나 하나 마다의 틀린 스펠 단어의 후보를 여러개 뽑아 놓는 것을 보여준다. 

image

각 단어마다의 여러 후보를 뽑고 이의 총 조합 경우를 확인한다. 

image

각 단어별로 여러개의 단어후보를 뽑아 모든 조합의 경우를 확인하는 것이 번거로울수 있다. 보통은 한 문장에서 한단어가 문제가 있는 경우가 많기 때문이다. 

image

non-word spelling problem에서 사용했던 channel model방법을 그대로 사용한다 다만 real-word spelling problem의 경우 맞는 단어가 주어진 상황에서 맞는 단어일 확률을 추가해서 확인해준다.

image

5 4 State of the Art Systems
https://youtu.be/aAvOOZRsby8

spelling correction 결과의 신뢰도에 따른 실제 어플리케이션에서 사용자에게 제시하는 방법들

이론상으로 channel model (error model) 과 language model (prior model) 의 곱으로 spelling의 맞을 확률을 구한다고는 했으나 사실 순수하게 두 값의 곱으로 결과값으로 사용하지는 않고 위의 그림처럼 람다값을 이용해 준다. 이 람다값은 test set을 이용해 통해 얻는다.

위의 3개의 그림처럼 다양한 기법을 총체적으로 사용한다.

classifier 에 따라 어떤 단어를 선택할지를 정할수 있다.

https://medium.com/nanonets/topic-modeling-with-lsa-psla-lda-and-lda2vec-555ff65b0b05

기본 nlp modeling 기법 개념 설명

lsa만 읽고 이해함 

nlp 관련 전반적이 내용이 잘 정리되어 있는 웹페이지이다. stanford cs124 (유튜브있는)과 다루는 범위가 비슷하다.

http://files.asimihsan.com/

5.1.2 Leave-One-Out Cross-Validation
https://youtu.be/pHOs7WomFSs

한번에 하나의 element를 제외한 상태로 data를 training data로 사용하는 기법을 말한다. 

4 1 Introduction to N grams
https://youtu.be/Saq1QagC8KY

image

각 단어들의 순차적인 결합중에 확률이 높은 것을 찾아낸다.

image

w1 부터 wn까지 순차적 결합이 나올 확률

w1 부터 w4까지 주어진 경우 w5가 나올 확률

image

한단어가 나올 확률은 바로앞 단어까지 주어진 상태에서 단어가 나올 확률에 앞단어들이 나올 확률들의 곱으로 나타낼수 있다.

image
image

위위 그림처럼 앞에까지 나온 모든 단어들이 주어진 상태에서 확률을 구하는 것은 번거롭기 때문에 markov는 바로 앞이나 바로 앞의 몇 단어만이 주어진 상태를 가정해서 확률을 구했다.

image

chain rule을 markov 방법에 맞게 수정한 알고리즘을 보여주고 있다.

image

언어의경우 처음 나온 단어가 맨 뒤의 단어와 밀접하게 연결되는 경우도 있기 때문에 단순히 앞의 몇단어를 가지고 다음에 올 단어를 유추하는 것은 어려울때도 있다.

4 2 Estimating N gram Probabilities
https://youtu.be/paCMAZ-lKq8

image
image
image
image

위 그림은 각 단어별로 나란히 나오는 경우의 확률를 보여준다. 예를 들어 want to 이렇게 연결될 확률은 0.66

image
image

각 확률의 이유를 생각해 본것이다. 예를들어 want chinese가 want english보다 확률이 높은 이유는 chinese음식이 english 음식보다 사람들이 관심을 많이 가지기 때문이다.

image

단어가 여러개인 문장의 경우 확률을 계속 곱하다보면 너무 작은 숫자가 나오는 문제가 발생한다. 여러 번의 곱셈은 많은 자원을 요구하기도 한다.

image
image
image

4 3 Evaluation and Perplexity
https://youtu.be/b6nwdc_fGfA

image
image
image
image
image
image
image
image

4 4 Generalization and Zeros
https://youtu.be/6NeUDr7YDiw

image

<s>가 주어졌을때 가장 확률이 높은 다음 단어로 I 가 넣어지고 I가 주어졌을때 가장 확률이 높은 다음 단어는 want 가 된다. want 다음 확률높은 단어는 to이다. 이런 과정을 통해 문장 전체를 만드는 과정을 보여주고 있다. 위에서는 바로 앞 한 단어만을 고려대상으로 삼지만 2개, 3개, 4개를 고려할수도 있다. 

image
image

세익스피어의 작품안에는 총 300,000 bigram이 있고 세익스피어에는 V개의 단어가 있다.

V개의 단어로 조합가능한 bigram의 총수는 844000000 개이다. 즉 대부분의 bigram은 실제 세익스피어 작품에는 존재하지 않고 이론상으로만 존재한다. ( zero entries )

quadrigrams과 같이 높은 수의 n-grams의 경우는 너무 overfitting되는 경우를 보여준다.

image
image

실제로 존재하지 않는 entries들의 확률을 0으로 본다. (추측컨대 이런 방법을 zeros라고 하는 것 같다.) 이 방법보다 조금 발전된 방법으로 add one smoothing이 있다.

4 5 Smoothing Add One
https://youtu.be/ZbHFLgBWgdQ

image
image

모든 항목 (빈칸포함)에 1을 다 더해준다. (정확한 계산 방법 https://youtu.be/gCI-ZC7irbY 2분 확인)

image

위 400/1000,000 = 0.00004이다. 오타

image

실제로 https://youtu.be/paCMAZ-lKq8 3:16 와 비교해 보면 모든 단어 출현횟수에 1이 더해졌다. 

image

각 행 총 값들의  합은 1이 된다. 예를 들어 i 가 주어진 상태에서 나올 다음 단어의 모든 확률이 합은(첫번째 행 확률값의 총합) 1이다.  

image
image
image

4 6 Interpolation
https://youtu.be/naNezonMA7k

image

n-gram model에서 높은 수의 n 은 보다 넓은 범위의 context를 적용한다 것으로 이해 할수 있다. 때로는 높은 수의 n-gram의 data 출현횟수가 너무 적어서 이를 일반적으로 사용하는데 무리가 있을수 있다. 이런 경우 back-off, interpolation 기술을 이용 보완한다. 

back-off : 예를 들어 어떤 trigram의 출현횟수가 적은 경우 한단계 낮춘 bigram을 이용한다. 또 그래도 부족한 경우 unigram을 이용한다.

interpolation : trigram의 출현횟수가 적은경우 bigram과 unitgram을 혼합사용해서 보완한다. 

interpolation이 좀던 좋은 성과를 보여주는 경향이 있다.

image

위그림에서 lambda는 weights 이된다. lambdas conditionla on context에서는 마지막 2번째 단어 (w n-2) 와 1번째 단어 (w n-1)를 고려한 lambda를 이용한다. (좀더 섬세한 접근 방법이다.)

image

training data를 이용해 만들어진 model을 가지고 held-out data의 예상값이 최적이 되게하는 lambdas값을 얻어 이용한다. (여기서 log는 확률의 곱으로 발생하는 계산상의 번거로움을 줄이고자 사용된것으로 추측한다.)

image
image

대용량의 데이터를 이용해서 model을 만드는 경우에 대한 설명이다. 

image

대용량의 데이터를 이용해서 model을 만드는 경우 stupid backoff를 이용 좀더 효율적으로 작업할수 있다. trigram이 있는 경우는 대괄호의 상단 공식 사용, trigram이 없고 bigram이 있는 경우 대괄호안의 하단 공식사용, 맨 하단의 공식은 unigram만 있는 경우 사용된다. 

참고 자료) https://rpubs.com/pferriere/dscapreport

https://www.aclweb.org/anthology/D07-1090

image

크네이서 나이 가장 많이 사용되는 방법이다. 

image

4 7 Good Turing Smoothing
https://youtu.be/fhvDgKBZa1U

참고 자료 ) 알고리즘이 실제 어떻게 움직이는지 쉽게 설명한 동영상

Good Turing Algorithm Part 1 by online courses

https://youtu.be/9ybvyShnDbk


Good Turing Algorithm Part 2

https://youtu.be/_tJleRiF-DM

image

add one smoothing에서 변형된 add k smoothing과 변형된 모습들이다.

image

add one smoothing에서 변형된 add k smoothing과 변형된 모습들이다.

image

add one smoothing에서 좀더 진보된 형태로 good turing, kneser ney, witten bell smoothing 방법들이 있다. 이들은 보통 이미 출현한 data를 기반으로 나타나지 않는 data를 추측하는 방법이라고 할수 있다. 

image
image
image

trout의 경우 한번만 출현 했다. 그러므로 c 값은 1이다. 실제 출현 확률은 1/18이다. 

두번 출현한 물고기는 whitefish 한가지 이므로 N2는 1이 된다. 한번 출현한 물고기는 trout, salmon, eel 3가지 이므로 N1은 3이 된다. c*은 discounted 된 값이다. 

image
image
image