나의 큰 O는 log x야

앞선글(TextRank 기법을 이용한 핵심 어구 추출 및 텍스트 요약) 에서 텍스트 랭크 알고리즘을 소개하면서 직접 실험해보고자 파이썬 코드를 짰었는데요, 정리해서 공유해드립니다. 페이지랭크 계산에 networkx 패키지를 사용하므로, networkx가 설치되어있는지 확인부탁드립니다. * 의존 패키지: networkx import networkx import re class RawSentence: def __init__(self, textIter): if type(textIter) == str: self.textIter = textIter.split('\n') else: self.textIter = textIter self.rgxSplitter = re.compile('([.!?:](?:["\']|(?!..

프로그래밍 2017. 4. 20. 17:13

여기까지 오시느라 다들 수고많으셨습니다. LDA에 사용되는 수많은 개념(베이즈 추론, 디리클레 분포 등...)을 지나서 드디어 마지막 깁스샘플링만을 남겼습니다. 베이즈 추론에서 사후 확률을 쉽게 계산하기 위해 켤레 사전분포를 사용한다고 했었는데요, 앞서 설명했던 식에서 문헌 내의 모든 단어 개수가 N개라고 하면 관측되는 단어 벡터 W도, 그 단어들의 주제 벡터인 Z도 모두 N차 벡터가 됩니다. 즉 N차 벡터가 주어졌을때 확률을 계산하는 일이 필요하게 됩니다. N값이 커질수록 이 계산은 기하급수적으로 복잡해집니다. 이를 빠르고 쉽게 계산하기 위해서 깁스 샘플링(Gibbs Sampling)이라는 편법을 사용하게 됩니다. 이 과정이 어떻게 이뤄지는지 살펴보도록 합시다. 깁스 샘플링N차의 자료를 대상으로 확률 ..

그냥 공부 2017. 4. 20. 16:09

앞 글에서는 베이즈 추론의 기본 개념과 이에 자주 사용되는 분포 중 하나인 이항분포, 베타분포에 대해서 살펴보았습니다. 이번에는 앞서 다룬 이항분포를 N개의 경우의 수로 확장한 다항분포(Multinomial Distribution)와 그 켤레 사전 분포인 디리클레 분포(Dirichlet Distribution)을 살펴보도록 하겠습니다. 가능도 켤레 사전 분포 가짓수 = 2 Bernoulli A, B 둘 중 하나만 일어나는 사건 Binomial A, B가 여러 번 일어나는 사건 Beta 가짓수 > 2 Categorical A, B, … Z 중 하나만 일어나는 사건 Multinomial A, B, … Z가 여러 번 일어나는 사건 Dirichlet 이전 글에 있었던 표를 다시 가져와보았습니다. 각 분포의 수학..

그냥 공부 2017. 4. 20. 16:09

작년에 토픽 모델링이라는 개념을 접하고 깜짝 놀랐어요. 그냥 적당한 크기의 문헌들을 넣어주면 거기에서 적절하게 컴퓨터가 연관된 단어들을 묶어서 주제 분포를 만들어주고, 문헌별로 주제가 얼만큼 포함되었는지 계산해주는게 너무 신기했기 때문이었습니다. 그래서 도대체 어떻게 이런걸 해내는지 궁금해서 LDA(Latent Dirichlet Allocation, 잠재 디리클레 할당)와 관련된 논문을 찾아봤는데 수학 실력이 부족해서 제대로 이해하지 못했다는 슬픈 소식이...그래서 LDA 이론을 이해하기 위해 작년부터 먼길을 돌고돌아 이러저러한 수학/통계적 기초를 찾아다녔는데, 마침내 드디어 빛을 찾은듯합니다. 그래서 간신히 찾은 빛을 오래오래 간직하고자 이렇게 블로그에 정리하게 되었습니다! LDA를 이루는 이론적 기초..

그냥 공부 2017. 4. 20. 16:07

이 글은 A Heidarian, 2016, A Hybrid Geometric Approach for Measuring Similarity Level Among Documents and Document Clustering 논문의 내용과 이를 정리하고 구현한 깃헙의 코드(https://github.com/taki0112/Vector_Similarity)를 바탕으로 작성되었습니다. 문헌들 사이의 유사도를 계산하기 위해서 흔히 사용되는 방법은 문헌에 등장하는 색인어(단어)의 빈도를 파악하여 TF-IDF 등의 가중치를 반영하여 벡터화하는 것입니다. 일단 문헌이 벡터로 표현되게 되면 여러가지 수학적 기법을 통해 벡터 간 유사도를 계산할 수 있죠. 그 중 대표적으로 사용되는 것에는 코사인 유사도와 유클리드 유사도 등..

그냥 공부 2017. 4. 14. 17:46

주변에서 찾아볼 수 있는 많은 분포들은 멱법칙(Power-law)을 따릅니다. 멱법칙을 따르는 경우 상위 몇 %가 전체의 대부분을 차지하고 나머지들이 긴 꼬리(long tail)을 형성하게 됩니다. 이는 빈부 격차와 같은 사회 경제적인 분야뿐만 아니라 음파의 주파수 별 진폭 분포처럼 자연 과학에서도 흔히 발견되는 분포입니다. 사람이 사용하는 언어의 단어 분포(지프의 법칙)나 소셜 네트워크의 중심성 계수 값도 이런 분포를 따릅니다. 따라서 실제 실험을 통해서 얻은 결과가 이 법칙을 따르는지 확인해보는건 재미있으면서도 중요한 일이라고 할 수 있죠. 그래서 해당 분포가 멱법칙을 따르는지 계산해주는 파이썬 코드를 빠르게 짜보았습니다. 멱법칙(거듭제곱 회귀)은 위와 같은 공식으로 나타낼 수 있습니다. 주어진 자료..

프로그래밍 2017. 4. 11. 20:46

앞서서 네트워크 이론의 기본적인 개념들을 설명했으니, 실제로 우리 주변에서 찾아볼 수 있는 네트워크들에서 어떤 현상이 일어나는지 살펴보도록 하지요. 실제 세계 네트워크의 성질랜덤 네트워크와 다르게 실제 세상의 네트워크들은 빈익빈 부익부 현상이 있습니다. 즉 다른 녀석들과 많이 연결된 애들이 전체 연결의 대부분을 차지하고, 조금 연결된 녀석들이 엄청나게 많습니다. 마치 20%가 80%의 돈을 가져가고, 나머지 80%가 20%의 돈을 가져가는것처럼 말이죠. 파레토의 법칙이라고도 불리는 이런 현상을 Power-law 분포(멱법칙)라고 합니다. 또한 결집계수(Clustering Coefficient)도 굉장히 높은 편입니다. 즉 내 친구의 친구도 내 친구인 경우가 많다는 거죠. 랜덤으로 그래프를 생성하면 이런일..

그냥 공부 2017. 4. 5. 15:57

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 속도를 향상시키기한 어절이 A B C D E F와 같이 6개의 형태로 쪼개질 수 있고 A,B,C,D,E,F 각각에 일치가능한 형태소가 4개씩 있다고 하면 전체 가능한 형태소 조합은 4^6 = 4096가지입니다. 각각의 조합마다 6개의 형태소 등장확률 계산 및 6개의 품사 간 전이확률을 계산해야 하니 12회의 확률 계산이 필요하네요. 즉 4096 * 12 = 49152회의 연산이 필요합니다. 이 모든 조합을 계산하기에는 시간이 너무 아깝습니다. 어차피 이 중에서 우리가 알고싶은건 가장 등장확률이 높은 조합 1개인걸요. 만약에 A B C D E F를 A B C / D E F 로 두 덩이..

프로그래밍/NLP 2017. 3. 26. 22:01