The Yellow Lion King 데이터와 함께 살아가기

스탠포드 머신러닝 강의 1:20 / 1:20:24Lecture 7 - Kernels | Stanford CS229: Machine Learning (Autumn 2018)

주요내용

• Optimization Problem
• Representer Theorem
• Kernels (SVM)
• Examples of Kernels (SVM)

Recap

지난 시간에 배웠던 내용을 정리합니다. Optimal margin classifier를 설명합니다.

감마를 최대화하는 w와 b를 구하면 됩니다. 이말은 모든 예제가 구해지면 감마보다 큰 지오매트릭 마진을 같는다는 의미 입니다. 모든 셈플을 잘 분리한다는 말이지요. (반대로 이말은 아웃라이어가 있을때 민감하게 반응한다는 단점이 있습니다. 이것을 어떻게 해결하는지는 뒤에서 설명합니다.)

w와 b에 일정한 값을 곱해도 같은 직선이라는 것을 설명합니다.

Gradient Descent 를 설명합니다.

w는 경계선의 기울어짐을 결정하고 b는 경계선의 수직방향으로의 이동 정도를 결정합니다.

이 내용을 3차원에서 설명해보면 아래와 같습니다. 3차원에서는 2차원에서의 선이 평면으로 나타납니다. 아래 예시에서 w는 평면의 각도를 결정합니다. w3이 0 이라서 수직이 되었네요.

w를 구하기 위한 상세 공식 유도를 아래와 같이 설명합니다.

24:34

Kernel Trick 커널 트릭

커널 트릭은 아래와 같습니다.
1) 커널은 이너프러덕으로 계산된다
2) 피처 x가 2개든, 3개든 얼마든지 매핑 함수를 통해 100,000 또는 수억개의 피처로 만들 수 있다. (아래 그림의 오른쪽 내용)
3) 2)에서 매핑된 변수(Φ(x))들과 z 함수(Φ(z))들을 계산하는 방법을 찾는다.
4) 알고리즘에 있는 <x, z> 를 k<x, z> 로 바꾼다.
이말을 합처보면 고차원 매핑(2)과 내적(3)을 하는 것이 커널 입니다.

커널의 예를 들어 보겠습니다.
x 는 아래와 같습니다.

그러면 아래와 같이 x를 고차원으로 매핑시킨 Φ(x)와 여러변수의 Φ(z)를 만들 수 있습니다. : 여기에서 매핑함수 Φ() 는 R^(n^2)로 정의했기 때문에 3개의 변수(x1, x2, x3)가 9개의 변수(x1,x1, x1,x2, ...)로 변경되었습니다. 이를 계산하기 위해서는 O(n^2)의 시간이 필요합니다.

더 좋은 방법을 생각해 보겠습니다. 아래 그림의 제일 위에 있는 공식 처럼 k(x,z) 를 다른 계산 방법으로 바꿀 수 있습니다. 즉, 함수를 거치지 않고 두 행렬의 곱으로 계산할 수 있습니다. 아래는 (x^Tz)^2가 Φ(x)^T Φ(z)와 같음을 증명하는 내용입니다. (x^Tz)^2 를 두개로 나누어서 () () 이렇게 만들었고 아래 처럼 쭉 따라서 가다보니 결국 (빨간색/녹색 동그라미처럼 두 항목을 곱한 값을 더한다는 것과 같은데...이말은 결국 제일 위줄 공식의 가운데에 있는 Φ(x)^T Φ(z)와 같은 결과이기 때문에 두 공식이 같음이 증명됩니다.
속도는 둘다 R^n 행렬이기 때문에 T 트렌스포즈하고 곱을 하면 O(n) 시간만 있으면 계산이 됩니다.

다시말하면 결국 Φ(x)의 한 행의 내용(빨간 동그라미)과 Φ(z)의 한 행의 내용(녹색 동그라미)을 곱해서 합친 것이 (x^Tz)^2와 같습니다.

여기에 상수 c를 추가해도 역시 소요시간은 O(n) 입니다. Φ(x)는 n+d 중에 d개의 피처를 갖을 수 있는데 최대 d의 깊이를 가질 수 있습니다. 그래서 d=5라면 아래와 같이 x1, x2, x3, x12, x29 도 될수 있고 x1, x2^2, x2,x18 도 될 수 있습니다. 이것은 (n+d)^d 와 비슷합니다.

SVM을 정의 하면
Optimal margin classifier + Kernel Trick = Support Vector Machine
이 됩니다.
이말은 적은 데이터로 많은 피처들을 만들어서 아주 효율적으로 계산해서 효과적으로 분류하는 모델을 만들게 됨을 의미합니다. SVM이 다른 말로 커널인줄 알았는데 조금 다른 것이 이었네요.
아래의 영상을 통해 SVM이 어떻게 동작하는 지 이해를 높일 수 있습니다.
https://www.youtube.com/watch?v=3liCbRZPrZA

여러 차원에 있던 데이터들을 잘 분리하는 하이퍼플레인(평면)이 있는데 이런 그래프를 2차원 으로 축소하면 하이퍼블레인(평면)이 선으로 바뀌어 표시됩니다. 그대신 직선이 아닌 구불구불한 선이 될 수 있습니다. 이러한 2차원 결과를 보여주는 것이 아래 그림 입니다. 이해되시나요. 위의 동영상을 보셨다면 이해가 되실 것 같습니다.

자, 이제 커널을 만드는 방법에 대해서 이야기 합니다. 여러 가정/조건이 있습니다. x, z가 비슷하면 커널함수 k(x,z)의 결과가 커야하고, 반대로 다르면 함수의 결과가 작아야 합니다. 이것은 벡터의 성질과 동일합니다. 이러한 조건을 만족하는 함수중하나가 아래의 공식입니다.

또다른 조건은 지금까지 맞다고 가정했던 공식인 k(x,z) = Φ(x)^T Φ(z) 입니다. 그리고 k(x,x) = Φ(x)^T Φ(x) >= 0 입니다. x1 부터 xd까지의 값을 가진 d 포인트가 있다고 합니다. 이때 K(커널행렬)은 R^(d*d) 입니다. 요소의 표시는 K(sub ij) = k(x(i), x(j)) 로 표시합니다.

그래서 벡터 z가 주어졌을때 커널과 계산 공식을 유도해보면 결국 K가 0보다 크거나 같습니다.

이것은 머서이론 (Mercer Theorem)과 같습니다.

그래서 앞서 커널을 만드는 방법을 설명할때 조건과 이에 적합한 예시를 들었던 아래의 커널함수는 유효함을 알수 있고 이것은 가장 많이 쓰이는 가우시안 커널입니다.

그 밖에도 선형 커널이 있는데 이는 선형함수와 같은 결과를 나타냅니다.

커널 트릭 중 이너프러덕은 다른 모델에서도 많이 쓰이는 방법입니다. < x(i), x(j) >


아래와 같이 2차원에 그래프를 그렸을때 빨간색과 같이 모든 것을 잘 분리하는 모델을 만들고 싶지 않을 것입니다. 왜냐하면 실제 추론 시에는 이렇게 할경우 더 안좋은 성능을 내기 때문입니다. 즉, 훈련데이터에 오버피팅 되어서 실제 추론시에는 성능이 낮아지는 것입니다. Variance가 커지겠네요. 그래서 빨간색 분리선보다는, 이상한 자리에 있는 값들은 잘 못 분리하더라도 파란색 분리선처럼 만들고 싶을 것입니다.

이렇게 하기 위해서 정규화를 할 수 있습니다. L1 놈/노름 소프트 마진 SVM 입니다. 오차 c를 이용하여 분리선과 오차거리를 고려해서 분리하게 됩니다.

L1 놈/노름 소프트 마진 SVM을 쓰는 다른 이유는 아웃라이어 하나만 들어와도 많이 다른 분리선을 만들기 때문에 이를 방지하기 위해 L1 norm soft margin SVM을 쓰는 것이 좋습니다. 옵티마이저가 최악의 케이스도 분리/포함하도록 되었는 경우 이와 같은 문제가 있습니다. 녹색 x 하나 만으로 기존에 파란색 선에서 녹색선처럼 많은 각도가 변경됩니다.

가우시안 커널의 성능도 매우 좋은데 MNIST와 같은 이미지 데이터에 대한 분류에서도 높은 성능을 냅니다. 0과 1의 픽셀 정보를 이용해서 하나의 벡터로 만들어서 SVM의 입력으로 넣고 분류하면 됩니다. SVM은 때로는 딥러닝 보다 좋은 성능을 낼때도 있으며 턴키 알고리즘으로 쉽게 만들 수 있습니다.

Examples of Kernels (SVM)

프로틴 시퀀스 분리 모델의 예시입니다. A부터 Z로 표시되는 원소로 구성된 프로틴의 아미노산 유무를 가지고 프로틴의 기능을 분리하는 모델을 만든다고 가정 합니다. 실제로는 20개인데 알파벳을 이용해서 이해를 쉽게하기 위해 26개를 이용합니다. 왼쪽에 시퀀스에서 등장한 4개의 문자를 오른쪽 피처 4개의 문자와 같으면 그 갯수를 누적하여 표시합니다. BAJT는 왼쪽에서 두번 나와서 오른쪽에 2로 표시됬습니다. 이렇게 해서 Φ(x)를 만들고 k(x,x)를 가우시안 커널을 이용하여 만들어 적용하면 됩니다.

SUMMARY

정리하면 SVM은 커널트릭과 최적의 마진 분리를 이용하는 분류 알고리즘 입니다. 커널 트릭은 입력 데이터를 다차원 데이터로 매핑/변환 하는 함수 Φ(x)와 그 결과와 커널함수 k(x,z) 결과의 행렬을 가지고 분류 모델을 만듭니다. 이러한 결과에 정규화 L1 norm soft margin SVM을 이용하고 오차 c를 추가하여 아웃라이어에 강한 분류 모델을 만듭니다. 최적의 마진 분리는 Geometric margin 지오메트릭 마진은 경계선을 근접한 요소와의 거리를 기준으로 경계선을 나누눈 방법입니다. SVM은 턴키 알고리즘으로 쉽게 개발/활용할 수 있을 뿐만 아니라 초기 딥러닝 모델 만큼이나 성능이 좋아서 지금도 많이 쓰입니다.



아래는 강의 영상 링크 입니다.
https://www.youtube.com/watch?v=8NYoQiRANpg&list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU&index=7

주요 내용

1. 개요
2. TF-IDF 계산 해보기
3. TF-IDF의 장점 및 단점
   

1. 개요

TF-IDF 는 BoW(Bag of Words)와 마찬가지로 텍스트 데이터를 (컴퓨터에서 사용하기 위해) 표현하는 방법중 한가지 방법 입니다. 정보 검색과 텍스트 마이닝에 많이 쓰입니다. 특히, 이 방법은 단어의 출현 빈도를 가지고 단어의 중요도를 표현하는 방법입니다. 그래서 해당 문서에서의 단어 출현 횟수와 다른 전체 문서에서의 출현 횟수를 고려해서 중요도를 계산합니다. 해당 문서에서의 단어 출현 횟수는 많으면 많을 수록 단어의 중요도가 더 높아지고(Term Frequency), 다른 전체 문서에서의 출현 횟수가 많아지면 많아 질수록(다른 문서에서도 많이 쓰이면 쓰일 수록) 중요도가 떨어지게하는(Inverse Document Frequency) 숫자를 만드는 방법 입니다.
예를 들어 보겠습니다. '노란 사자 왕' 이란 검색어와 가장 적절한 문서를 찾으려면 어떻게 해야할 까요? 가장 간단한 방법은 각 단어가 포함되어 있는 문서를 찾는 것일 것입니다. 그런데 이런 문서가 10,000개 있다면 어떻게 해야 할까요? 네, 여러번 '노란', '사자', '왕' 이란 단어가 들어가 있으면 더 적절한 문서라고 할 수 있을 것 같습니다. 그런데 이렇게 해서 다시 필터링해보니 100건이 나왔다고 합시다. 여러번 나왔으니 더 적절한 문서라고 할 수 있지만 문서의 길이를 고려하지 못해서 전체 문서에서의 단어 중요도가 반영되지 못했습니다. 1페이지 문서에서 10번 나온 것과 100페이지 문서에서 10번 나왔다면 1페이지에서 10번 나온 문서가 더 밀접한 관계가 있다고 말할 수 있습니다. 그래서 문서의 길이를 고려한 출현 횟수를 산정하는 방법이 바로 Term Frequency 입니다. 그래서 간단한 공식으로는 단어 출현횟수/ 문서내 전체 단어수가 되겠습니다.
그럼 두번째 전체 문서에서의 출현 횟수 왜 필요할까요? 문서중에는 의미가 없는 단어들도 매우 많습니다. 행태소 분석시 나오는 '는', '를', 'ㅂ니다' 같은 요소들은 의미는 없지만 일반적으로 매우 많이 출현하는 단어에 해당합니다. 이러한 단어들에게는 매우 작은 값으로 계산되는 것이 필요하겠습니다. 그러면 이런 숫자는 어떻게 계산할까요? 위에서 설명한 것처럼 모든 문서에서 나타나면 안 중요한 단어이고 해당문서에서만 나타나면 중요한 단어인 것이지요. 이렇게 만들려면 전체 문서수와 해당 단어가 나타난 문서수의 비율로 계산할 수 있겠습니다. 전체 문서수 / 해당 단어 출현 문서수 이렇게 계산하면 되겠군요. 100 개 문서중에 1번 나타난 단어(100/1=100)와 100개 문서중에 10번 나타난 단어(100/10=10)는 중요도가 달라집니다. 그런데 이렇게 하면 전체 문서와 단어 출현 문서수가 클 경우 중요도 차이가 너무 크게 됩니다. 그래서 여기에 log 를 적용하여 숫자를 작게 만듭니다. log(100) = 2, log(10) = 1. 아까는 차이가 9였는데 이제는 1이 되었네요. 그래서 간단한 공식으로는 log(전체 문서수/해당 단어 출현 문서수)가 됩니다. 이것이 Inverse Document Frequency입니다.
그런데 다른 자료들을 보면 계산하는 방법이 이렇게 간단하지 않고 복잡하고, 방법도 여러가지가 있는 걸까요? 그 이유는 좀더 정확한 계산을 위해서 단순한 출현 횟수를 그대로 사용하지 않고 변환을 하기 때문에 그렇습니다. 위에서 log를 적용한 것처럼 말이죠. 중요한 것은 기본을 이해하는 것 입니다. 기본을 이해해야 변형을 이해하기 쉽습니다. 기본은 위에서 말씀 드린 것 처럼 어렵지 않습니다.

해당 단어의 TF-IDF = Term Frequency X Inverse Document Frequency
해당 단어의 TF-IDF = TF(t,d) X IDF(t, D)
해당 단어의 TF(t,d) = log (f(t,d) + 1)
해당 단어의 IDF(t, D) = log (D / ( {d in D : t in d} ) + 1) )
t: 해당 단어
d: 해당 문서
D: 전체 문서 개수

2. TF-IDF 계산 해보기

위에서 말씀드린 공식을 이용해서 실제 TF-IDF 값을 계산해 보겠습니다.

Data

d1의 tf-idf 구하기

문서 d1에 대하여 TF-IDF를 구합니다. ln은 자연로그 입니다.

t = “I” d1 = “I love apple"
tf(t,d) = tf(“I”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (3 + 1)). = ln(2.5) = 0.9162 10개 문서중 3개 문서에서 I 가 발견됨
“I” tfidf = tf(“I”,d1) * idf(“I", 10) = ln(2) * ln(2.5) = 0.6931 * 0.9162 = 0.6350 ("I"의 TF-IDF입니다.)

t = “love” d1 = “I love apple"
tf(t,d) = tf(“love”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (7 + 1) ) = ln(1.25) = 0.22314 10개 문서중 7개 문서에서 love 가 발견됨니다.
“love” tfidf = tf(“love”,d1) * idf(“love", 10). = ln(2) * ln(1.25) = 0.6931 * 0.22314 = 0.15466 (love라는 단어가 많은(7개) 문서에서 나타나기 때문에 tfidf 값이 비교적 작습니다. 단어가 주는 차별성/특성이 작다고 할 수 있습니다.)

t = “apple” d1 = “I love apple"
tf(t,d) = tf(“apple”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (2 + 1) ) = ln(3.3333) = 1.2039 10개 문서중 2개 문서에서 apple 가 발견됩니다.
“apple” tfidf = tf(“apple”,d1) * idf(“apple", 10). = ln(2) * ln(2.4285) = 0.6931 * 1.2039 = 0.8344 (apple라는 단어가 적은(2개) 문서에서 나타나기 때문에 tfidf 값이 비교적 큽니다. )

d1 = “I love apple” = [0.6350, 0.15466, 0.8344]

d2의 tf-idf 구하기

t = “I” d2 = “I love peach”
tf(t,d) = 0.6931
idf(t, D) = 0.9162
“I” tfidf = 0.6931 * 0.9162 = 0.6350

t = “love” d2 = “I love peach”
tf(t,d) = 0.6931
idf(t, D) = 0.22314
“peach” tfidf = 0.6931 * 0.22314 = 0.15466

t = “peach” d2 = “I love peach”
tf(t,d) = tf(“peach”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (2 + 1) ) = ln(3.3333) = 1.2039 10개 문서중 2개 문서에서 peach 가 발견됩니다.
“peach” tfidf = tf * idf = 0.6931 * 1.2039 = 0.8344

d2 = “I love peach” = [0.6350, 0.15466, 0.8344]

d10의 tf-idf 구하기

t = “They” d10 = “They hate peach”
tf(t,d) = tf(“They”,d10) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (1 + 1)). = ln(5) = 1.6094 10개 문서중 1개 문서에서 They 가 발견됨
“They” tfidf = tf(“They”,d10) * idf(“They", 10) = ln(2) * ln(2.5) = 0.6931 * 1.6094 = 1.1154 (They라는 단어가 하나의 문서에서 나타나기 때문에 tfidf 값이 매우 큽니다. )

t = “hate” d10 = “They hate peach”
tf(t,d) = tf(“hate”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (3 + 1) ) = ln(2.5) = 0.9162 10개 문서중 3개 문서에서 hate 가 발견됨
“hate” tfidf = tf(“hate”,d1) * idf(“hate", 10). = ln(2) * ln(1.25) = 0.6931 * 0.9162 = 0.6350 (hate라는 단어가 적은 문서(3)에서 나타나기 때문에 tfidf 값이 비교적 큽니다. )

t = “peach” d10 = “They hate peach”
tf(t,d) = tf(“peach”,d1) = ln (1 + 1) = 0.6931 (count 로 할때, 문서 d에서 t가 발견되는 건수)
idf(t, D) = log (D / {d in D : t in d} ) = ln(10 / (2 + 1) ) = ln(3.3333) = 1.2039 10개 문서중 2개 문서에서 peach 가 발견됩니다
“peach” tfidf = tf(“peach”,d1) * idf(“peach", 10). = ln(2) * ln(2.4285) = 0.6931 * 1.2039 = 0.8344 (peach라는 단어가 적은(2개) 문서에서 나타나기 때문에 tfidf 값이 비교적 큽니다. )

d10 = “They hate peach” = [1.1154, 0.7614, 0.8344]

Summary

각 문서별 벡터를 가지고 TF-IDF 메트릭스를 만듭니다.

문서 간의 유사도 계산

상기와 같이 문서간의 유사도 계산 뿐만아니라 키워드(검색어)를 가지고 유사도를 계산하면 유사한 문서를 가져오는 정보 검색에 사용할 수 있습니다.

3. TF-IDF의 장점 및 단점

스탠포드 기계학습/머신러닝 강의 Lecture 6 - Support Vector Machines | Stanford CS229: Machine Learning (Autumn 2018)

주요 내용

• Naive Bayers(나이브 베이즈)
• - Laplas Smooding
• - EV models
• Comment on apply ML
• SVM Intro

Recap
나이브 베이즈는 Generative 알고리즘으로 텍스트 분류나 트위터 메세지 같은 것은 분류할 수 있습니다.
텍스트를 사전에 정의된 순서에 따라 있는지 없는지를 표시하는 방법(원핫 인코딩)으로 하나의 문서(메일 또는 메시지)를 표시할 수 있습니다. 그래서 X에 있는 각 단어가 이메일에서 발견될 확률을 계산하여 전체 X의 확률을 구했습니다.

이것을 확률 공식(나이브 베이즈)으로 정리하면 아래와 같았습니다.

p(x|y) y일 때 x가 (정규분포에서) 나타날 확률과 p(y) 전체 y(스펨 or 정상) 메일이 (0 또는 1이므로 베르누이 분포에서) 나타날 확률을 결합하여 계산합니다.
p(x|y)는 각 xj 요소의 확률들의 곱으로 계산할 수 있습니다.
필요한 파라메타들은 p(y=1) = Φy 1(스팸)인 메일이 나올 확률
p(xj = 1 | y=0) = Φj | y=0 0(정상)인 메일에서 xj가 나올 확률
p(xj = 1 | y=1) = Φj | y=1 1(스팸)인 메일에서 xj가 나올 확률

Φ 는 최대가능도법(MLE)를 통해 아래와 같이 구할 수 있습니다.

이렇게 해서 정리된 파라메타들과 입력값을 이용하여 새로운 데이터 입력시 예측을 할 수 있습니다.

NIPS 라는 학회에 참여하기위해 준비하는 메일을 받았다고 합시다. 관련된 단어수는 6017개 라고 하시죠. 문제는 이 단어들이 기존에 학습될때 사용되지 않은 단어이기 때문에 확률을 계산하면 0으로 나옵니다. 이 건 매우 않 좋은 현상입니다. 한번도 못봤던 단어라고 해서 그 단어가 포함될 확률이 0이라고 하기에는 무리가 있습니다.

그래서 라플라스 스무딩이라는 기법을 사용합니다.

라플라스 스무딩

라플라스 스무딩을 먼저 설명하고 다시 돌아오겠습니다. 그래서 다른 예를 살펴 보시지요.
팀의 경기 승패를 예측한다고 생각해 봅시다. 12/31일에는 이길까요? 질까요? (0은 패, 1은 승을 표시 합니다.)

x=1일(승리할) 확률은 아래와 같이 구할 수 있습니다. 전체 1의 갯수 나누기 전체갯수(1과 0의 갯수의 합)를 하면 됩니다.

다음 경기를 승리할 확률이 없습니다. 즉, x = 1일 때 확률이 0입니다. 4번 연속해서 패배했다고 이길 확률이 아예 없다(0)는 건 좀 잘못된 것 같습니다. 실제로도 가끔 이기는 경우가 생기기 때문에 잘못된 계산 같습니다.
그래서 이러한 경우 우리는 라플라스 스무딩이라는 것을 할 수 있는데요. 이것은 각 경우의 수에 1을 더해주는 것입니다. 0의 갯수 4에 1을 더해주고, 1의 갯수 0에 1을 더해주어서 분모나 분자에 0을 안만드는 방법입니다.

이렇게 하니 1/6이 나와서 0보다는 좋아 보입니다.
수학자 라플라스가 라플라스 스무딩을 만든 이유에 대해서도 설명해주십니다. 재미있네요. 태양은 매일 뜨지만 내일 아침 태양이 뜰 확률이 정말 1인(확실한)가? 혹시 모를 우주나 은하계의 충돌이나 사건으로 인해 태양이 안 뜰 수도 있는데 확실하다고 하는 것은 잘못된 것 아닌가라는 관점에서 그럼 이런 것을 어떻게 정의하면 좋을까를 생각해서 나온 것이라고 합니다.

일반화 해서 쓸때는 분모에 요소수(k)를 사용하네요.

다시 나이브 베이즈로 돌아가서, 공식에 라플라스 스무딩을 적용해 보면 아래와 같습니다. 클래스가 2개라서 분모에 2를 더했네요.

이 알고리즘의 장점은 간단하다는 것 입니다. 카운트만해서 계산하면 확률을 구할 수 있습니다.

일반화된 예를 보겠습니다. 이를 위해 예전에 예시를 들었던 주택 예시를 들어보겠습니다. 주택이 30일 내에 팔릴지 안팔릴지를 판단하는 모델을 만든다고 가정합시다. 입력 데이터로 방 크기를 버켓팅(Bucketing)하여 아래과 같이 구분하여 입력합니다. 이렇게 하면 이전에 (스팸메일분류모델에서는) 베르누이 분포였지만 여기서는 다항 분포 확률이 됩니다.

그리고 보통 버켓팅은 10개의 구간으로 한답니다. 이처럼 데이터를 변형하면 나이브 베이즈를 여러 문제에 적용해서 사용할 할 수 있습니다.

텍스트 분류에 더 좋은 모델을 설명 드리겠습니다. 1만개의 단어가 있는 사전을 기준으로 아래의 텍스트를 인코딩 해보면 아래와 같습니다.

이와 달리 새로운 표현(New Representation) 방법에 대해서 알아봅니다. 사전이 중심이 아니라 입력 데이터가 중심이 되서 입력 데이터의 단어를 사전에서 단어가 나오는 순서로 표현하는 것 입니다.

데이터를 표현하는 백터가 매우 작아지네요..

그래서 전에 사전을 기준으로 존재여부 (0,1)을 표시했던 방법을 Multi-variate Bernoulli Event Model이라고 합니다.

나중에 새로운 표현법으로 설명한 방법은 Multinomial Event Model이라고 합니다.

이름이 비슷하여 혼동될 수 있습니다.

새로운 표현방법 Multinormial event model을 이용하여 나이브 베이즈 공식을 정리하면 아래와 같습니다. 예전에 스펨메일 분류시와 유사하지만 조금 다릅니다. j가 1부터 n까지 반복되는데 스펨메일에서는 10,000번 반복했고 여기서는 메일의 단어수 만큼만 반복하면 됩니다. 그리고 여러 카테고리가 있기 때문에 카테고리별로 단어 xj가 해당 카테고리에 속할 확률을 구합니다. Φk | y=0 = p(xj=k | y= 0)

y=1 스팸일때의 Φ 공식은 아래와 같습니다. 이 확률을 최대로 높이는 가능도(MLE)를 구합니다. 그리고 빨간색으로 표시된 것 처럼 라플라스 스무딩을 적용해 줍니다. 분모에 10,000이 더해졌는데 이것은 사전에 들어있는 단어숫자 입니다.

사전에 없는 단어가 나오면 어떻게 처리할까요?
두가지 방법이 있는데 하나는 그냥 무시하고 단어를 사용하지 않는 것이고요, 다른 하나는 UNK(Unknown Tocken)이라는 특별 기호로 매핑하여 적용하는 방법입니다.

일반적으로 나이브 베이즈는 로지스틱 회귀 보다 정확도 성능이 낮아서 잘 안씁니다. 그러나 나이브 베이즈는 반복 작업이 필요없어서 빠르고 몇줄 안되는 코딩으로 쉽게 개발 할 수 있는 장점이 있습니다.
해결해야할 ML 문제를 직면했을 때 빠르게 지저분한 코드를 만들어보는게 좋습니다. 이런 경우 나이브 베이즈는 매우 좋은 툴입니다.

소프트웨어를 개발할때 한꺼번에 10,000 라인의 코드를 입력하고 컴파일하지 말고 여러개의 모듈로 만들어서 각 모듈 하나씩을 만들고 단위 테스트해 나가는 방법이 더 좋은 소프트웨어 개발 방법입니다. 모델 개발할때도 마찬가지로 일단 빠르게 지저분한 코드라도 돌아가는 것을 만들어 놓고 시작하는 것이 좋습니다. 그런 다음 어떤 부분이 정확도를 떨어트리는지를 파악하고 하나씩 해결해가면서 성능을 높일 수 있습니다.
GDA와 나이브 베이즈는 일반적으로 다른 로지스틱 회귀나 딥러닝 모델에 비해 정확도 성능이 낮습니다. 그럼에도 불구하고 간단하고 속도가 빠른 장정들 때문에 모델 개발 초기에 이러한 알고리즘을 가지고 빠르게 작동하는 모델을 만드는 것은 좋은 접근 방법 입니다.
나이브 베이즈의 단점으로 아빠, 엄마와 같이 비슷한 단어를 구분하지 않습니다. 그냥 단어의 출현을 가지고 활용하게 되는 것이지요. 워드 임베딩이라는 다른 테크닉이 있는데 이것은 이런 문제를 해결하는 방법입니다. 즉, 단어간의 유사성이 모델 훈련시 학습됩니다.

SVM Support Vector Machine

SVM은 아래 그림에서처럼 복잡한 결정 경계(Decision boundary)를 만들 수 있는 모델입니다. 로지스틱 회귀와 같은 선형모델에서는 그림에 그려진 직선처럼 구분 할 수 밖에 없는데 이것에 비하면 SVM은 정말 잘 분류 합니다.

사실 입력값 x1, x2만 사용하지 말고 x1과 x2를 이용해서 다른 입력값을 만들수 있는데 (이것이 그림 하단에 있는 Φ(x)처럼 x1*x2를 한다든가, x1^2 등 새로운 값을 만들어내는 것입니다.) 이 만들어진 피처를 이용해서 로지스틱 회귀를 훈련하면 초록색과 같이 복잡한 경계도 분류할 수 있습니다. 문제는 x1, x2에서 다양한 피처 X를 만들어 내는 것이 힘든일이라는 것이지요 그리고 어떤 피처가 적합한지 알 수 없기 때문에 어려운 작업입니다.

SVM이 딥러닝 보다 성능이 더 좋지는 않습니다. 그래도 많이 쓰이는 이유는 턴키(Turn Key)이기 때문입니다. 무슨 말이냐하면 많은 패키지에서 이미 SVM이 잘 만들어져 있어서 (key를 넣고 돌리면되는 것처럼) 그냥 가져다 쓰면 쉽게 만들 수 있습니다.


앞으로 진행할 내용은 아래와 같습니다.
* Optimal margin classifier : 선형분리와 비슷하지만 살짝 다른 부분이 있습니다. 일단은 그냥 로지스틱 회귀와 같은 것으로 가정하겠습니다. 아래에 설명 할 예정입니다.
* (다음 시간에) Kernels. 커널이 자동적으로 무한대에 해당하는 피처를 생성해 줍니다.
* (다음 시간에) Inseparable case

Functional margin

아래의 윗 부분의 내용은 로지스틱 회귀입니다.

Geometry margin

빨간색과 녹색의 두가지 모델이 있다고할때 어떤것이 더 좋은 모델일까요? 잘은 모르지만 녹색이 좋은 모델 같습니다. 왜그럴까요?

그 이유는 경계선과 요소간의 거리가 먼 것이 더 잘 분리했습니다. 그래서 두 모델 모두 100% 잘 분류하는 모델이 더라도 녹색 모델이 더 좋은 모델입니다. 이렇게 Geometric margin을 기준으로 경계를 분리할 수 있습니다. 기본적인 SVM은 이 경계마진을 이용하여 분리선을 만듭니다.

SVM관련 표기법입니다. 1 또는 -1을 반환하는 함수네요.

로지스틱 회귀와 SVM 함수 공식을 비교하여 아래에 보여줍니다.

하나의 하이퍼플레인(선) 을 결정하는 functional margin 계산 방벙을 설명합니다.

정규화를 이용해서 functional margin의 치팅을 막을 수 있습니다.

Geometric margin 을 아래와 같이 구할 수 있습니다. 유클리디안 거리를 가지고 선과 점의 거리를 계산할 수 있겠네요

Functional margin과 비교해 봅니다.

최적화 시키는 공식 입니다. 이것도 convex optimization problem 이라고 합니다.

공식에 대한 상세 풀이라든가 설명이 있는 강의 노트가 없어서 조금 아쉬운 부분도 있네요. 그래도 전체적인 개념과 구조를 이해할 수 있습니다.

SVM은 매우 성능이 좋은 알고리즘 입니다. 딥러닝이 나오기 전까진 말이죠. 그정도로 성능이 좋고 빠름니다. 그래서 최근에도 많이 쓰이는 알고리즘 입니다.
게다가 턴키 알고리즘으로 사용하기도 쉽습니다. ^^


아래는 해당 강의 동영상 입니다.

https://www.youtube.com/watch?v=lDwow4aOrtg&list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU&index=6

이번 강의 주요내용

Generative Learning Algorithm
- Gaussian Distributed Analysis(GDA)
- Generative vs Descriptive comparison
- Naive Bayes(나이브 베이즈)

Generative learning algorithm

지난 시간에 배운 로지스틱 회귀에 대해서 다시 생각해봅시다. 종양을 보고 양성인지 음성인지 판단하는 모델을 생각해봅시다. 아래와 같이 x는 양성(암) o는 음성이라고 할 경우 우리는 선을 그려가면서 어떤 선이 가장 잘 판단하는지를 구분하는, 좋은 '선'을 찾는 문재로 생각할 수 있습니다. 이런게 Descritive 방법이지요.

로지스틱 회귀와 다르게 GLA는 알고리즘은 클래스의 특징을 먼저 배웁니다. 악성종양의 데이터들을 보면서 아! 악성종양은 위쪽에 모여있구나 이것을 배우고 음성종양의 데이터를 보면서 음성종양은 아래쪽에 모여있구나를 학습하게 됩니다. 그렇게 해서 악성종양 모델은 위쪽 빨간색 동그라미에 모여있고 음성 종양모델은 아래쪽 빨간색 동그라미에 모여있다는 것을 모델이 학습하게됩니다. 이를 이용해서 새로운 빨간점 데이터가 들어왔을때 어느 모델의 동그라미에 속하는 지를 보고 판단하는 방법이 GLA(Generative learning algorithm)입니다.

다시 말하면 Descriptive 학습은 x가 주어지면 h(x)함수가 0인지 1인지 알려주는 모델이었습니다. 그에 반해 Generative 는 먼저, y(양성 또는 음성 중 하나의 클래스)가 주어졌을때 x가 나올 확률을 계산합니다. 전체 중에 y의 확률은 전체 데이터를 가지고 구할 수 있습니다(사전확률). 여기에 베이즈 룰을 적용해서 x가 주어졌을때 y가 1(악성)일 확률을 구할 수 있습니다. 이러한 방법이 Generative 알고리즘의 프레임웍 입니다. 사전확률과 개별 사건의 확률을 구하고 이를 이용해서 새로운 x에 대한 y일 확률을 구할 수 있습니다. 이 설명을 관련 공식으로 정리하면 아래와 같습니다. 왼쪽이 사전확률과 개별확률을 구하는 공식이고 오른쪽이 새로운 x가 들어왔을 때 확류을 구하는 공식입니다. 잘 보시면 왼쪽에서 빨간색 사각형 부분들과 오른쪽 아래에 빨간색 사각형의 공식을 이용해서 오른쪽 위에있는 P(y=1 | x)를 구할 수 있습니다.

오늘 두가지 유형의 데이터(연속형 continuous-GDA, 이산형 discrete-Naive Bayer)에 대한 모델을 배울 것 입니다.

*** Discriminative와 Generative 모델의 이해를 위해 위키피디아에서 Generative model 에 대한 정의를 찾아봤습니다.
In statistical classification, two main approaches are called the generative approach and the discriminative approach. These compute classifiers by different approaches, differing in the degree of statistical modelling. Terminology is inconsistent,[a] but three major types can be distinguished, following Jebara (2004):

1. A generative model is a statistical model of the joint probability distribution {\displaystyle P(X,Y)} on given observable variable X and target variable Y;[1]
2. A discriminative model is a model of the conditional probability {\displaystyle P(Y\mid X=x)} of the target Y, given an observation x; and
3. Classifiers computed without using a probability model are also referred to loosely as "discriminative".

Discriminative 모델은 조건부 확률이고 Generative모델은 결합 확률 분포를 이용한다는게 다른 점 입니다. 강의 중에도 내용이 나오니까 계속 보겠습니다.

Gaussian Distributed Analysis(GDA)

GDA의 가정들은 아래와 같습니다. 가장 중요한 가정은 사용되는 데이터가 가우시안 분포라고 가정합니다.

단일 피처 데이터에 대해서는 표준 정규 분포를 이용하면되고 여러 피처에 대해서는 다변량 정규 분포를 이용합니다. 하나의 피처 데이터 항목으로는 많은 문제를 해결할 수 없으므로 여러 피처를 이용하는 다변량 정규 분포를 배우는 것이 중요합니다.

아래는 2개의 피처를 사용하는 2차원 다변량 정규 분포를 시각화 한것 입니다. 이미지 위에 있는 공식의 ∑ 값에 따라 그래프의 모습이 바뀌는 것을 보실 수 있습니다.

이러한 그래프를 2차원 그래프로 바꾸면 아래와 같습니다.(가운데 각 동그라미는 모두 완벽한 원입니다.)

가중치를 바꾸자 완벽한 원이 었던 것이 타원형이 되었습니다.

y의 각 클래스 별로 확률을 구하는 공식은 아래와 같습니다. 둘다 정규분포를 가정하고 작성된 것입니다. 그래서 정규분포의 확률밀도함수와 유사합니다.

그리고 여기에 사용되는 파라메타에 대해서 이야기합니다. 뮤0, 뮤1, 입실론, 피/파이 입니다. 이러한 파라메타를 잘 훈련해서/찾아서 모델을 만들면 앞의 그림에 있는 베이지안 룰을 통해서 새로운 데이터 x가 주어졌을 때 y가 1일 확률을 구할 수 있습니다.

훈련데이터에 대한 표기 법을 설명합니다. 그리고 조인트(결합) 가능도를 구하는 공식을 유도합니다.

조건 가능도를 구하는 공식을 유도합니다.

최대 가능도 추정법(MLE)을 통해서 파라메타들을 찾습니다.

각 파라메타들을 공식으로 유도한 내용입니다. 직관적으로 설명하면 오른쪽 아래의 그림처럼 각 클래스 집단의 중간에 있는 값이 평균(뮤)가 됩니다. 뮤0는 전체 데이터중에 y가 0인(음성인) 데이터 피처 벡터들의 합을 y가 0인(음성인) 데이터의 전체 개수로 나눈 값입니다. 즉, 평균값 입니다. 그래서 집단의 중간에 위치하게 됩니다.

입실론도 아래와 같은 공식으로 유도됩니다. 예측 시에는 확률 값을 최대로하는 값을 찾는 argmax함수를 이용합니다.

Generative vs Descriptive comparison(37:00)

선형회귀모델의 최초 학습을 위해 변수를 0으로 셋팅하고 선을 그어본 그림입니다. 반복 iteration을 할 수록 잘 구분하는 선으로 바뀌는 것을 보여 줍니다.

이것이 로지스틱 회귀를 이용한 분류 학습 알고리즘 입니다.


반면 GDA는 각 클래스의 분포를 먼저 계산하고 각 분포간의 거리를 기준으로 분류 선을 그립니다. 동그라미 데이터들을 보면서 동그라미 클러스터(집단)의 중앙 위치를 찾습니다. 그다음 x 데이터들을 보면서 x 클러스터의 중앙 위치를 찾습니다. 둘사이의 거리 중간을 기준으로 선을 긋습니다.

두 모델의 결과를 비교해보면 아래와 같습니다.

결국 둘다 모두 분류 모델을 만드는 것인데 그 방법이 서로 다르네요 즉, 직선을 그어가면서 제일 잘 분류하는 선을 찾을 것인지 아니면 분류된 분포를 보고 두 분포를 분리하는 선을 찾을 것인지가 다릅니다.

훈련 데이터가 하나인 경우를 가정하고 설명합니다. 종양의 크기라고 해보죠 x로 표시된 것은 악성종양, o로 표시된 것은 음성 종양입니다. 제일 위의 그래프는 직선에 종양 크기별로 표시한 내용이고 그 아래 두번째 그래프는 각 클래스에 대한 빈도를 그린 곡선입니다. 두 개의 정규분포 그래프가 보이네요. 그리고 제일 아래 그림은 새로운 예측 데이터 x가 주어졌을 때 y가 1(악성종양)일 확률을 x의 크기에 따라 그려본 그래프 입니다. 정확하게 시그모이드 함수와 일치합니다.

결국 두 모델 다 시그모이드 함수를 사용한 것과 같습니다. 그러나 접근 방법이 다르기 때문에 위에서 보여드린 두 모델의 비교 그림에서 보이는 것처럼 서로 다른 직선을 만듭니다.



두 모델의 차이점과 특징, 언제 GDA가 더 유용한지?

• GDA는 정해진 분포를 가정하고 계산하기 때문에 훈련데이터의 분포를 잘 알고 있는 경우 사용하면 좋다.
• GDA가 더 가정에 강하기 때문에 더 잘 설명한다(중앙의 화살표처럼 GDA로는 로지스틱회귀를 설명할 수 있지만 반대로는 안된다.)
• GDA는 적은 계산으로 좋은 성능을 낼 수 있다. (반복 계산할 필요없고 평균, 편차에 대한 행렬계산만 하면 끝난다)
• 로지스틱 회귀는 훈련데이터의 분포를 모를 때도 사용할 수 있고 좋은 결과를 나타낸다.
• 세상 대부분이 정규분포이기 때문에 데이터가 많이 있으면 로지스틱 회귀를 사용하는게 좋다.
• 데이터를 점점 더 많이 사용할 수 있게되고 계산 비용(인프라 비용)이 저렴해짐에 따라 로지스틱 회귀를 사용하는 사례가 많아진다.
• 데이터가 적은 상태에서 모델을 만드려면 고급 스킬이 필요하다. 적은 데이터로도 효과적인 모델을 만들 수 있다.

Naive Bayes 나이브 베이즈

Generative 모델중 하나인 나이브 베이즈에 대한 설명 입니다.
이메일에 대한 스팸 여부를 분류하는 모델 개발을 생각해 봅시다. 10,000개의 단어가 있는 사전을 가지고 있다고 합시다. 하나의 이메일 x 에 대해서 해당 단어가 있는지(1) 없는지(0)에 따라서 아래 처럼 표시할 수 있습니다. (One-hot Encoding)

아래와 같은 가정을 합니다.

각 단어들은 독립적이라고 가정하고 각각의 확률은 체인 룰을 통해 아래와 같이 정리될 수 있습니다.

찾아야할 파라메타는 스팸메일(y=1) 일때 xj 단어가 나타날 확률과, 스팸메일이 아닐 때(y=1) xj 단어가 나타날 확률 입니다. 그리고 전체 메일중에 스팸메일이 나타날 확률 입니다.

GDA와 같이 조인트 가능도를 구합니다. 모습도 GDA와 유사하게 됩니다.

이번 강의 에서는 Generative 모델과 Discretive 모델의 차이와 Generative 모델에 해당하는 Gaussian Distributed Analysis 와 Naive Bayers 알고리즘에 대해서 배웠습니다.



아래는 강의 동영상 링크 입니다.
https://www.youtube.com/watch?v=nt63k3bfXS0&list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU&index=5