나의 큰 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

세상의 많은 관계들을 수학적으로 나타내는데에는 그래프만큼 강력한 도구도 없습니다. 관계의 주체가 되는 행위자들은 Node로, 관계들은 Node사이를 연결하는 Edge로 나타낼 수 있기 때문이죠. 이렇게 주변에서 찾아볼 수 있는 관계를 수학적인 형태의 Graph로 바꾸면 여러 가지가 가능해지는데, 그 중 대표적인것이 중심성(Centrality) 계산입니다. 중심성은 그래프 상에서 어떤 Node가 가장 중요한지를 살피는 척도인데요, 여태까지 막연하게 여러가지 계산법이 있을거라고 생각은 했지만, 실제로 공부는 해보지 않았었네요. 그래서 이번에 Social Media Mining을 공부하면서 관련 이론을 정리해보려고 합니다. (다음 내용은 Zafarani, R., Abbash, M.A., & Liu, H, 20..

그냥 공부 2017. 3. 15. 16:50