나의 큰 O는 log x야

훌륭한 알고리즘이라고 꼭 다 복잡하거나 이해하기 어려운건 아닙니다. 오히려 정말 단순한 절차로 큰일을 해내는게 진짜 훌륭한 알고리즘이라고 할 수 있을텐데요, TextRank (또는 PageRank)가 바로 그런 알고리즘인듯 합니다. 구글을 만든 알고리즘으로 널리 알려진 페이지 랭크는 매우 단순한 반복 계산을 통해서 각 페이지의 중요도를 매깁니다. 알고나면 단순한 알고리즘이지만 처음 이를 고안해내기는 정말 어려웠을 겁니다. 여기서는 간략하게 페이지 랭크 알고리즘을 소개하면서, 이를 텍스트에 응용한 텍스트 랭크를 설명하도록 하겠습니다. PageRank 소개페이지 랭크는 각각의 페이지를 정점(Node)으로, 페이지와 페이지를 연결하는 링크를 간선(Edge)으로하여 만들어진 그래프를 대상으로 하는 알고리즘입니다..

그냥 공부 2017. 2. 20. 21:49

관련어를 추출하는데에 있어서 점별 상호정보량(http://bab2min.tistory.com/546)만큼 간단하면서도 훌륭한 방법은 많지 않습니다. 그래서 관련어 추출 방법들을 비교할 때 있어서 기준치로 쓰이기에 좋지요. 그래서 여기 저기 코드에서 상호정보량 계산 클래스를 자주 만들어 쓰다보니깐, 하나로 잘 만들어놔서 두고두고 재활용해야겠다는 생각이 들었습니다. 간결하면서도 아름다운 파이썬 코-드 class PMICalc: def __init__(self, **kargs): self.window = kargs.get('window', 5) self.minNum = kargs.get('minNum', 5) self.dictCount = {} self.dictBiCount = {} self.searchPai..

프로그래밍 2017. 2. 14. 18:12

두 텍스트 간의 유사도를 산출하는 고전적인 방법에는 텍스트 내의 단어 빈도를 가지고 벡터를 구축하여, 벡터 간 코사인 유사도를 구하는 것이 있습니다. 이 방법의 장점은 다른 어떤 언어학적 기법을 도입하지 않아도 (기껏해야 Stemming 정도만 하면 충분하죠) 단어 빈도만 세어서 꽤나 훌륭한 결과를 얻을 수 있다는 것입니다. 그런데 이런 통계적인 방법이 통하려면 해당 텍스트가 충분히 길어야한다는 조건이 필요하죠. 그렇지 않을 경우 텍스트로부터 만들어진 벡터가 희소(sparsity)하게 되어, 좋은 결과를 얻을 수 없게 됩니다. 그렇기 때문에 짧은 텍스트에 대해서는 조금 다른 방법이 필요하게 됩니다. 이 글에서는 W Song, 2007, Question Similarity Calculation for FA..

그냥 공부 2017. 2. 9. 16:07

단어 의미 판별(Word-sense Disambiguation)이라는 작업이 있습니다. "가다"라는 동사를 예로 들어보죠. "집에 간다"는 문장에서 가다는 움직이는 것을 의미합니다. 반면 "저 세상으로 가셨다"는 문장에서는 죽었음을 뜻합니다. 이렇듯 같은 단어라도 맥락에 따라 사용되는 의미가 다르기에 보통 사전에 보통 1,2,3...번으로 세부 의미를 나눠서 뜻풀이를 합니다. 사전 이용자들은 사전을 살펴볼때 단어의 세부 의미 1번에 가장 자주 쓰이는 의미가 들어가 있기를 기대합니다. 그렇기에 세부 의미를 판별해서 어떤 세부 의미가 가장 자주 쓰이고 주된 의미인지 판별하는 작업이 사전 편찬 작업에서 중요하다 할 수 있겠습니다. 이 글에서는 D McCarthyr, 2004, Finding Predominan..

그냥 공부 2017. 2. 7. 18:30