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

Minimum Edit Distance Dynamic Programming


Needleman-Wunsch algorithm

https://youtu.be/aD4Cc4L3qW0

global sequence alignment

https://youtu.be/LhpGz5–isw

3 1 Defining Minimum Edit Distance
https://youtu.be/-XRJL2R0SCg

image
image
image

문자열을 alignment할때 있는 그대로 해야만 하는 것은 아니다. 위 그림과 같이 중간에 빈칸을 넣을수도 있다.

image

edit distance를 이용 두 문장간의 유사성을 파악할수도 있다.

image
image

3 2 Computing Minimum Edit Distance
https://youtu.be/fN3Js7H72HE

image
image

edit distance 알고리즘을 이해하는데 도움이 되는 영상

https://youtu.be/We3YDTzNXEk

3 3 Backtrace for Computing Alignments
https://youtu.be/MnE10oJ2jX4

edit distace를 하는 과정에 back tracking (tracing) 작업을 추가로 함으로써 어는 부분에서 insertion이 되었는지 나중에 알수 있으며 이를 통해 alignment가 가능하게 된다.

image
image

위 그림에서 화살표가 세가지 있는경우 어느 방향으로 부터 현재값이 기인하는지 상관없다는 것을 의미한다. 맨윗줄 3의경우는 옆이나 밑에서 오기보다 대각선 하단에서 기인하는 것이 효율적인 경로이므로 이경우는 대각선방향만 선택한다. 이런 계산 과정을 하다보면 특정방향으로 부터만 기인하는 것이 효율적이 있는데 이런 경우 insertion, deletion, substitution 중 하나의 작업만 효율적이란 이야기다. 

image
image

3 4 Weighted Minimum Edit Distance

https://youtu.be/9G-EwniAaPA

image
image

위 그림은 각 알파벳 별로 잘못 오인되는 경우의 수를 보여주고 있다. 특정 알파벳이 특정 알파벳으로 오인되는 경우가 많은 것을 알수 있다. 그래서 weighted min edit distance를 사용 알고리즘 성능을 높일수 있다.

image

3 5 Minimum Edit Distance in Computational Biology
https://youtu.be/96pL6xTP3W8

위의 needleman – wunsch algorithm은 global sequence alignment에 많이 사용되는 알고리즘중의 하나이다. -i * d , -j * d부분은 시작으로 부터 얼마나 떨어져서 맷칭이 시작되는지를 보고 감점하는 부분이다. 

local sequence alignment의 경우 시작이나 마지막 부분에 있는 빈공간은 신경쓰지 않는다.

smith waterman algorithm의 iteration부분을 보면 음수의 값이 있는 경우 0으로 대체되게 된다. 즉 최소값이 0이 되게 된다. 

위 두 그림은 같은 데이터라도 맷칭부분을 다양하게 할수 있는 것을 보여준다.

2 1 Regular Expressions

https://youtu.be/zfH2ADGtzJQ

image
image
image

| 는 ‘또는’을 의미한다.

image

u?의 경우 u는 있어도 되고 없어도 된다는 의미이다. o+는 적어도 o가 한번 이상나와야 한다. o*는 0번또는 그 이상 여러번 나올수 있다. 점 . 는 어떤 캐릭터도 될수 있다. 

image

여기서 ^는 시작을 의미한다. $는 마침을 의미한다. 

2 3 Word Tokenization
https://youtu.be/f9o514a-kuc

image

모든 nlp에서 데이터는 기본적으로 token 단위로 나누어야 한다. 

image

같은 어원, 어근을 가지는 단어들을 어떻게 처리할것인지 단수, 복수처럼 상황에 따라 단어의 형태가 조금 바뀌는 경우 같은 단어로 볼것인지 아닌지를 결정해야 한다.

image

 token은 중복되는 것을 상관하지 않고 각각 따로 갯수를 센다. type의 경우 동일한 단어는 갯수에서 제외한다.

image

각 tokens의 갯수가 types보다 큰것을 알수 있다.

image

tokens, types단위로 나눌때 흔히 발생하는 문제를 보여주고 있다.

image

각 언어별 특성에 따른 문제점들을 보여주고 있다.

image
image

중국어나 일본어처럼 띄어쓰기가 없는 경우 사용할수 있는 방법으로 maxium matching word segmentation algorithm이 있는데 이를 보여주고 있다.

2 4 Word Normalization and Stemming
https://youtu.be/ZhyLgPnOeh0

아래에 단어를 여러방법으로 정리하는 것을 보여주고 있다. 

image
image

case를 한 방향으로 통일하는 방법이다.

image

한 lemma를 기반으로 하는 단어들을 하나로 통일해준다. 

image

어근과 접미, 접두의 합으로 표현할수도 있다.

image
image

영어 단어를 정리하는데 porter algorithm을 많이 사용한다.

image

영어에서 ing 를 정리할때 모음이 있는 경우만 제거한다.

2 5 Sentence Segmentation
https://youtu.be/UL4Ez56AMVo

문장단위로 데이터를 잘라서 처리하는 방법을 보여주고 있다.

!와 ?를 기준으로 문장을 구분하는 것은 불확실하다. 점 .를  기준으로 나누는 경우도 단어의 약자나 숫자에 사용되는 . 때문에 어려움이 있다. 그래서 추가 작업이 필요하다. 이때 사용할수 있는 것이 hand-written rules, regular expression, machine learning 등등이 있다.

문장의 끝을 확인하는 간단한 방법으로 decision tree를 이용하는 것이 있다. 

dot 앞뒤에 대문자가 사용된경우 약자에 사용된 dot일 확률이 높다. dot 뒤에 대문자가 오는 경우 dot이 문장 끝일가능성이 높다. 단어 the 앞에 dot 이 사용된 경우 dot이 문자의 끝일 확률이 높다. 

How to Learn Math for Data Science, The Self-Starter Way

간단한 개념 정리 한국어 https://youtu.be/lmD9p6J_-TA

한국어 설명 https://youtu.be/LE25o5lUbwU

참고사항

편미분과 Gradient의 기하학적 의미 (간단 소개)

https://youtu.be/bUNqn1G1O7E