나의 큰 O는 log x야

네트워크 이론에서는 전달가능성(Communicability)이라는 개념을 다룹니다. 두 노드가 얼마나 잘 연결되어 있는지를 보는 개념이라고 할 수 있는데요, 이 포스트에서는 전달가능성의 개념과 계산방법 및 그와 관련된 여러 이야기에 대해서 다뤄보겠습니다. 전달 가능성(Communicability)학교에서 소문이 퍼지는 일을 생각해봅시다. 소문은 사람에서 사람에게로 1대1로만 퍼진다고 가정하고, 둘이 친한 사이일수록 더 잘 퍼진다고 합시다. 만약 사람 A가 어떤 정보를 알고 있다고 할때, 이 정보가 다른 사람 B에게 얼마나 잘 퍼지는지 어떻게 계산할 수 있을까요? 만약 A와 B가 직접 친한 사이라면 A가 직접 B에게 그 정보를 전달해줄테니 금방 퍼질거라고 생각할 수 있습니다. 혹은 둘 사이가 전혀 모르는 ..

그냥 공부 2017. 7. 30. 01:49

요즘 계속 토픽 모델링 쪽으로 공부를 해보고 있는데요, 앞서 다뤘던 LDA, DMR, HDP-LDA 같은 모델은 모두 각각의 주제가 독립적이라 가정하고, 단일 수준에 모든 주제들을 배치했었습니다. 이번에 살펴보는 hLDA(Hierarchical LDA)는 주제를 계층적으로 찾아서, 최상위 주제 아래 하위 주제 여러 개를 배치할 수 있게 해줍니다. 배경이 되는 수학 이론이 생각보다 까다로워서 아직 완벽하게 이해는 하지 못했구요, 샘플 코드를 가지고 요리조리 실험을 해본 결과를 간단하게 살펴보는 시간을 가지려고 합니다. 주제는 서로 독립이 아니다LDA와 같은 토픽 모델링은 문헌 집합 내의 주제를 발견하는데에 큰 도움을 주지만, 아쉽게도 어떤 주제끼리 서로 연관이 있는지를 밝혀주지는 못합니다. 예를 들어 정치..

그냥 공부 2017. 7. 23. 02:25

앞서서 LDA 토픽 모델링 기법에 대해서 설명했었는데요, LDA 기법은 모수 통계라는 특성 상 학습에 앞서 원 데이터가 가지는 주제의 수 K를 설정해 주어야 합니다. 이 K값에 따라 LDA 토픽 모델링의 결과가 크게 달라지기 때문에 적절한 K값 선정은 정말 중요한 일입니다. 하지만 해당 데이터에 얼만큼의 주제가 포함되어 있는지를 사전에 알기는 정말 어렵죠. 사람이 일일히 문헌을 뒤져가면서 K을 확인할 수도 없는 노릇이구요. 따라서 다양한 K값에 대해서 분석을 돌리고 perplexity 값을 기준으로(또는 해석이 합리적인 정도를 기준으로) 적절한 K값을 선정하는 방식으로 K값을 찾게 됩니다. 이것이 LDA의 주요한 약점 중 하나입니다. 만약 데이터에 따라 적절한 주제 개수를 찾아주도록 LDA 기법을 개선할..

그냥 공부 2017. 7. 9. 02:29

언어에는 다른 단어이지만 형태가 같은 동철이의어(또는 소리가 같지만 다른 단어인 동음이의어)도 많습니다. 그리고 같은 단어라 할지라도 맥락에 따라 쓰이는 의미가 다릅니다. 따라서 해당 글자가 여러 동철이의어 중 어떤 단어를 가리키는지, 더 나아가 각 단어에 있는 여러 가지 세부 의미(의미 갈래) 중 해당 맥락에서 사용한 세부 의미가 어떤 것인지 판별하는 것은 굉장히 중요한 작업이지요. 이를 단어 의미 판별(Word Sense Disambiguation, =단의 의미 중의성 해소, 갈래뜻 판별)이라고 부릅니다. 단어 의미 판별은 기계 번역이나 정보 검색, 정보 추출과 같은 자연언어처리 분야에 큰 도움이 될 수 있습니다. 본 포스팅에서는 Pal, A. R., & Saha, D. (2015). Word sen..

그냥 공부 2017. 7. 4. 16:40

앞선 글에서 토픽 모델링의 대표적인 기법이라고 할 수 있는 LDA(Latent Dirichlet Allocation)에 대해서 다뤄보았는데요, 이번 글에서는 LDA를 확장한 기법들 몇 개를 살펴보고자 합니다. 복습으로 다시 한 번 LDA 토픽 모델링 기법을 정리해보자면 다음과 같겠죠. K개의 주제와 V종류의 단어가 들어가 있는 M개의 문헌이 있다고 합시다. 우리는 하나의 문헌이 여러 개의 주제들의 조합으로 이루어져있고, 각각의 주제는 여러 개의 단어가 포함된다고 가정합니다. 이 문헌의 주제 분포와 주제의 단어 분포가 디리클레 분포를 따른다고 가정하고, 실제 관측되는 문헌의 단어로부터 문헌별 주제 분포와 주제별 단어분포를 추론해내는 작업, 이 것이 LDA 토픽 모델링 기법입니다. 그러나 이 LDA 기법에서..

그냥 공부 2017. 7. 1. 01:21

예전 포스팅에서 상호정보량과 점별 상호정보량에 대해 정리해보았었는데요, 두 사건이 함께 발생할 정도를 판단하는데 유용하게 사용됩니다. NLP에서는 연어(Collocation, 연속된 2개 이상의 단어가 한 덩어리로 쓰이는 것) 추출에서 유용하게 사용하지요. 다만 점별 상호정보량은 그 값이 (-∞, ∞) 범위에 속하고, 서로 정보량이 다른 사건을 비교할때 그 값의 스케일이 다르기 때문에 제대로된 비교가 어렵다는 점이 있습니다. 따라서 범위를 [-1, 1]로 일정하게 정규화할 필요가 있습니다. 이를 정규화 점별 상호정보량(Normalized Pointwise Mutual Information, NPMI)라고 부릅니다.또한 일반적으로 상호정보량은 2개의 사건에 대해서만 정의되기에, 3개 이상의 사건이 함께 발..

그냥 공부 2017. 6. 17. 03:15

여기까지 오시느라 다들 수고많으셨습니다. 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