166 정보과학회논문지 : 시스템및이론제 35 권제 4 호 (2008.4) 하이퍼네트워크에서본단어간긴밀성과다양성 (Affinity and Variety between Words in the Framework of Hypernetwork) 김준식 박찬훈 이은석 장병탁 (Joon-Shik Kim) (Chan-Hoon Park) (Eun-Seok Lee) (Byoung-Tak Zhang) 요약전체문서 (corpus) 에서의두단어간연결상태를파악하여앞단어다음에오는단어의빈도수를기반으로여러형태의그룹을분류하여단어간다양성과긴밀성을살펴보았다. 기존의연구에서 Zipf s Power Law 는 Chinese Restaurant Process 로설명되었고 Scale Free Network 에서는 edged 의수에따른노드의 profile 을조사하여 hub 들을찾는연구가수행되었다. 본연구에서는단어간연결의유일성과다양성을조사하여 Zipf's Power Law 와 hub profile 을동시에살펴보았다. 데이타분석결과단어간연결의긴밀성과다양성사이에서대칭성으로함축되는유의한결과를얻었으며이는소위 exploitation 과 exploration 의관점에서설명될수있다. 또한분석자료인 TIPSTER 에서관찰된약간의대칭성깨짐 (symmetry breaking) 에대해서도논한다. 키워드 : 다양성, 긴밀성, 지프의지수법칙, 대칭성, 이용, 탐색 Abstract We studied the variety and affinity between the successive words in the text document. A number of groups were defined by the frequency of a following word in the whole text (corpus). In the previous studies, the Zipf's power law was explained by Chinese restaurant process and hub node was searched after by examining the edge number profile in scale free network. We have observed both a power law and a hub profile at the same time by studying the conditional frequency and degeneracy of a group. A symmetry between the affinity and the variety between words were found during the data analysis. And this phenomenon can be explained within a viewpoint of "exploitation and exploration." We also remark on a small symmetry breaking phenomenon in TIPSTER data. Key words :variety, affinity, Zipf's power law, symmetry, exploitation, exploration TIPSTER data 를제공해주시고좋은논의를해주신엄재홍씨께감사를드립니다. 이연구는한국과학기술부의국가지정연구소 (NRL) 프로젝트와산업자원부의분자진화연산 (MEC) 프로젝트그리고교육인적자원부의 BK21-IT 의지원을받았습니다. 이논문은 2007 한국컴퓨터종합학술대회에서 하이퍼네트워크관점에서본문서에서의단어간긴밀성과다양성의대칭성 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교물리천문학과 jskim.ozmagi@gmail.com 학생회원 : 서울대학교컴퓨터공학과 chpark@bi.snu.ac.kr 학생회원 : 서울대학교인지과학협동과정 eunseok.lee@gmail.com 종신회원 : 서울대학교컴퓨터공학부교수 btzhang@bi.snu.ac.kr 논문접수 : 2007년 9월 27일심사완료 : 2008년 1월 23일 Copyright@2008 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 시스템및이론제35권제4호 (2008.4) 1. 서론 Zipf's law로불리는 ranking profile의 power law 분포는여러물리생물시스템에서나타난다. 그예로단어의빈도수 [1], 지진의규모 [2], 우주에서발광체의분포 [3], 메타볼리즘 [4], 유전자발현 [5] 등의시스템을들수있다. 여기서관찰되는 power law를설명하는방법도다양하여, scale free network[6], Chinese Restaurant Process[7], 세포단위의동력학법칙 [5], 그리고 Markov Chain Monte Carlo[8] 등많은방법들을그예로들수있다. 이는 Zipf's law의보편성을증거하는것에다름아닌바, 이에본연구는이러한성질을바탕으로하이퍼네트워크 (hypernetwork)[9,10] 관점에서단어들을표상하는노드들간의연결관계를설명하고자한다. 즉하이퍼네트워크관점에서정리된기억의기본소자양식을이용하여문서속에서의단어간연결
하이퍼네트워크에서본단어간긴밀성과다양성 167 을 count 수로나타내는방법을사용한다. 이방법은하이퍼네트워크를기억인출이나 [9], 문서분류 [10] 의기능을수행하는측면보다는기억의기본소자로서이용하여전체문서혹은기억의통계적인분포를알아보고자하는데사용하고자하는것이다. 하이퍼네트워크모델은학습과메모리의 random graph 모델로서세포의분자네트워크구조로부터유래하였다. 한편, 하이퍼네트워크는가중치가부여된하이퍼그래프 (hypergraph[11]) 로서설명될수있는데, 하이퍼그래프를구성하는 k개의 vertice로이루어진 k-order 하이퍼에지는그 edge의가중치를통해하이퍼네트워크를구성한패턴과그성분 (vertice) 간의 k-order correlation을나타낼수있다. 이미하이퍼네트워크의이러한특성을활용하여다양한분야에서패턴인식및완성에관련된실험 [9,10,12] 이이루어진바있다. 본논문에서는전체문서 (corpus) 와그일부를복제한부분문서 (query) 를통해단어간의연결에서의긴밀성과다양성간에대칭적인성질이있으며이는기계학습의이용 (exploitation) 과탐색 (exploration) 으로설명할수있음을논의하고자한다. 우리는양자역학의원자모델에서의에너지준위 (energy level) 를유추 (analogymaking) 했고, 같은에너지를가지는자유도의개수인축퇴도 (degeneracy) 라는물리량을사용하여문서를분석해보았다. 부분문서 (query) 의단어들을따라가며전체문서에서그단어다음에올수있는모든인접단어를조사하여이를그빈도수 (frequency) 에따라분류한그룹으로나누었다. 우리는다시 Markov Chain Monte Carlo 모델을적용하여부분문서의단어다음에오는인접단어가속한그룹의빈도수 (frequency) 와그축퇴도 (degeneracy) 를살펴보았다. 여기서축퇴도 (degeneracy) 란같은빈도수 (frequency) 를가지는모든단어들의개수를의미한다. 빈도수 (frequency) 는다음단어와의연결의긴밀함을나타내고축퇴도 (degeneracy) 는다양성을나타낸다. 실제로이러한열역학적이고 Markov Chain Monte Carlo(MCMC) 적인방법은 DNA computing의열역학적모델링의패러다임을따른다고볼수있다 [13]. 여기에서 DNA 간의 entropy와 degeneracy가 log 함수로연관되어있고 enthalpy와 frequency가역시 log 함수로연결되어있으며 Gibbs free energy는 degeneracy 와 frequency의곱의마이너스로그값임을밝혀둔다. 우리는부분문서의단어들의전개에따른 group들은 degeneracy와 frequency의정보를분석하여보았고이다양성과긴밀성을나타내는척도의분포는상당히대칭적 (symmetrical) 임을관찰하였다. 또한단어다음에오는그룹의상대적순위 (relative ranking, group ranking/number of total groups) 의분포가상위부분과하위부분이대칭적으로높게나옴을관찰했다. 이는상대적순위 (relative ranking) 의시계열분포로부터알수있듯이중간 ranking에서상대적으로상위와하위 ranking으로주도적으로전이되는현상에기인한다. 마지막으로 Gibbs free energy와 frequency 그리고 Gibbs free energy와 degeneracy 그래프로부터 frequency와 degeneracy가부분적으로깨짐 (partial symmetry breaking) 현상을관찰했다. 이는높은 frequency를가지는단어들은그 degeneracy가 1의값만가지지만높은 degeneracy를가지는단어들은 1, 2, 3, 4, 5 등의다섯가지이상의 frequency를가지기때문으로분석된다. 이현상으로부터가능한해석은, 이용 (exploitation) 은한가지단어만을계속하여연결하는것이유리하고탐색 (exploration) 은여러가지경우를가지는것이유리하기때문이라는점이다. 2. 이론양자역학에서, Potential 함수에갇힌입자는 discrete 한에너지를가지며각에너지준위에는정해진자유도 (degree of freedom) 이부여된다. 예를들자면, 원자핵에잡힌전자들의상태들이나양성자와중성자로이루어진원자핵의상태가그러하다 [14]. 여기서에너지가음수로큰값을가질경우자유도를나타내는 degeneracy 는작은값을가지고음수로작은값을가지는높은에너지준위에서 degeneracy는큰값을가진다 ( 그림 1). 이와비슷한현상이 Hypernetwork 관점에서분석한인접한단어들간에도관찰되었다. 즉, 빈도수 (frequency) 가높은단어의축퇴도는대체로 1이었고빈도수 (frequency) 가낮은단어의축퇴도 (degeneracy) 는큰값을가졌다. 그림 2에서두척도의상관관계를보인다. 그림 1 삼차원조화진동자 (harmonic oscillator) 의 degeneracy와 energy[14], 여기서 n은주양자수이고 l은궤도양자수이다.
168 정보과학회논문지 : 시스템및이론제 35 권제 4 호 (2008.4) 그림 2 단어의 frequency를기준으로분류한 group, frequency, degeneracy의예여기서 degeneracy = exp(entropy/k) 와 frequency = exp(-enthalpy/kt) 의열역학적관계가도입된다. k는 Boltzmann 상수이고 T는절대온도이다. 이로볼때, Gibbs free energy = enthalpy - T entropy이며이는 -kt ln (degeneracy frequency) 로주어진다. 위의 Gibbs free energy를도입하여부분문서 (query) 의단어간진행을 Markov Chain Monte Carlo(MCMC) 모델로설명할수있다. 3. 실험과정입력된텍스트를하이퍼네트워크로재구성하였다. 하이퍼네트워크는 order 2의하이퍼에지 (hyper edge) 로구성되어있으며이는 2개의단어 (feature) 가연결되었음을표상한다. 하이퍼에지를구성하는 2개의단어는문장을기본단위로하여연속되어쪼개진다. 즉, "A B C" 의 3개단어로이루어진문장의경우 "A B" 와 "B C" 두개의하이퍼에지를생성한다. 하이퍼에지 ( 또는 library elements, 동일하게사용 ) 는동일한하이퍼에지가많이존재할수록더큰 weight를갖게된다. 즉문장을쪼개어생성된각각의하이퍼에지는기존에동일한하이퍼에지가존재할경우그하이퍼에지의 count를하나 (1) 씩증가시켜주며, 그렇지않을경우새로운하이퍼에지가된다. 프로그램상에서는각하이퍼에지마다 counter를달아서동일한하이퍼에지가입력될경우그 counter의값을 1 증가시키도록구현하였다. 전체문서 (corpus) 에대하여모든문장을하이퍼에지로전환하면, 하이퍼네트워크가구성된다. 구성된하이퍼네트워크에대하여연속된부분문서 (query) 를입력하였다. query는마찬가지로문장수준으로들어오며, 이문장을 initialization과마찬가지로 order 2의하이퍼에지로변환하여 matching을 수행한다. 각 query 문장으로부터생성된하이퍼에지각각은만들어둔하이퍼네트워크와의 matching을통해 corpus 의정보를분석한다. query 하이퍼에지들은자신의첫번째 vertex( 단어 ) 와동일한 vertex를포함하고있는하이퍼네트워크상의모든하이퍼에지들을검색하며, 그하이퍼에지들의다른한쪽 vertex 정보를각 query 별로저장한다. 이때저장되는정보들은각각의 query 하이퍼에지마다 a. query 하이퍼에지와첫번째 vertex가 match되는모든하이퍼에지의수 (total number of group) b. query 하이퍼에지의다른한쪽 vertex를포함하는하이퍼에지가속하는 group의번호 (appointed group ranking) * 각그룹은동일한 frequency(= count) 를갖는하이퍼네트워크상의하이퍼에지의집합으로구성된다. c. b group의원소의개수 (degeneracy) d. b group의 frequency이다. 실험문서로는 TIPSTER VOL1의 AP data를썼으며전체문서 (corpus) 는 2.2MByte이고이중처음의 56 KByte 분량을복사하여부분문서 (query) 로사용하였다. 4. 실험결과우리는앞으로제시되는그림 3-8, 그리고 9를통하여빈도수 (frequency) 와축퇴도 (degeneracy) 사이의대칭성을살펴보고약간의대칭성깨짐현상도관찰할것이다. 각결과의설명은각그림의설명에자세히기술하였다. Zipf law는많은시스템에서관측되며, 본논문에서는 Zipf law가관찰되는시스템의하나인문서를 Hypernetwork 관점에서분석해보았다. 이때열역학적모델에따른 MCMC 방법을가정하였다. 실험결과는상대적 relative ranking의상위와하위부분이대칭적으로큰값을가짐이관측되었다 ( 그림 7). 이로부터 frequency와 degeneracy 간의대칭성 (symmetry) 을볼수있었다. 이와는약간반대되는성질인 frequency와 degeneracy에서의약간의대칭성깨짐 (symmetry breaking) 현상도 Gibbs free energy와각각의두변수 (frequency, degeneracy) 의그림에서관찰할수있었다 ( 그림 8, 9). 위의관찰결과들은 exploitation과 exploration의효과적사용으로짜임새있는의미전달가능한문서가완성된다는의견을뒷받침한다. 즉, 빈도수가높은단어는하나의축퇴도만을가짐으로써그이용이극대화되고, 축퇴도가높은단어들은다양성이중요하므로빈도수가 1, 2, 3, 4, 그리고 5인경우를가진다. 여기에서의짜임새있는문서의기본단위는문장이며
하이퍼네트워크에서본단어간긴밀성과다양성 169 그림 3 TIPSTER data의 AP 문서를 Hypernetwork로분석했을때이웃하는단어간의전체문서에서의빈도수 (frequency) 다양성혹은축퇴도 (degeneracy) 의분포. 우리는이그림에서단어간연결상태는빈도수가높거나혹은축퇴도가높거나하는대칭적인분포를가짐을알수있다. 즉스케일을무시하면 y=x 직선에대해서대칭이다. 그림 5 그림 3의 data들을 frequency 값들에따라도수분포표를그려보았다. x, y 값들은자연로그를취한값들이다. 처음 4개의데이타에서선형적감소를볼수있고그옆에두개의독립된 data들을관찰할수있다. 그림 4 그림 3의 data 들을 degeneracy 값들에따라도수분포표를그려보았다. x, y 값은자연로그를취한값들이다. 데이타들이선형적감소를보인다. 이결과는 degeneracy profile이 power law를따름을보인다. 이논문의단어간통계는의미가있는한문장내에서의단어간통계이다. 또한 power law distribution은 self organized criticality(soc) 에서기인한다는연구를통해 [15] 잘짜여진문서는뇌의 neuron들의 SOC 상태에서나온 power law 성질을가지는결과물이라고추론할수있다. 5. 결론문서에서의분석결과를가지고인적네트워크에적용하여생각해볼수도있다. 우리가학교혹은직장에서 그림 6 이웃하는단어의그룹 (group) 의상대순위 (relative ranking) 의전이그림. 그룹은빈도수 (frequency) 가같은모임을뜻하며앞단어다음에올수있는단어들을그빈도수기준으로그룹을나누고실제부분문서 (query) 에서선택되어지는뒤단어의그룹순위를구한다. 위그림에서 x 축은 i 번째단어의그룹순위를전체그룹의개수로나눈상대순위를나타내며 y 축은그다음에연결되는 (i+1) 번째단어의상대그룹순위이다. 이그림에서 x 값이 0.1 이하이거나 0.9 이상이면단어연결은모든상대순위그룹으로전이하지만그사이에서는상위그룹 (y 값이 0.2 이하 ) 혹은하위그룹 (y 값이 0.8 이상 ) 으로우세하게전이됨을볼수있다. 실제로다음그림 7은이를잘보여준다. 빈도수가많게매일보는상사와동료들이있는가하면일년에두세번정도로드물게만나는친구들과고객
170 정보과학회논문지 : 시스템및이론제 35 권제 4 호 (2008.4) 그림 7 그룹의상대순위의도수분포를나타낸다. 0.2 이하의상위그룹과 0.8 이상의하위그룹에데이타가몰려있음을볼수있다. 상위그룹은하위그룹에비해빈도수 (frequency) 가높고축퇴도 (degeneracy) 가낮으며하위그룹은그반대이다. 이그림에서우리는빈도수와축퇴도사이의대칭성을볼수있다. 즉 x=0.5 직선을중심으로좌우대칭이다. 그림 9 위그림의 x 축은축퇴도이며 y 축은 Gibbs free energy이다. 다섯가닥의 branch를볼수있으며이는각각빈도수가 1, 2, 3, 4, 5일때의 data 들이다. 그림 8과비교하여 frequency 와 degeneracy 간의약간의대칭성깨짐 (symmetry breaking) 현상을관찰할수있다. 즉 frequency와 degeneracy를바꾸어보았을때약간의다른차이를발견할수있다. 여기서는높은 frequency일때 degeneracy는 1이지만높은 degeneracy일때 frequency는 1, 2, 3, 4, 5 등의값을가지는것이그이유이다. 큰경우이며역시 Gibbs free energy가최소화된다. 이러한 minimization principle와문서의의미전달최적화사이에구체적으로어떠한관계가있는지는좀더연구해볼필요가있다. 또한유전자 (gene) 를단어로볼경우 DNA 상의유전정보를문장과문서로볼수있고이논문에서수행한방법들을유전자문서에적용시켜볼수도있을것이다. 그림 8 x 축은빈도수이며 y 축은 kt=1일때의 Gibbs free energy 즉 -ln(frequency degeneracy) 이다. 여기서 k는 Boltzmann 상수이고 T는절대온도이다. 하나의 branch가보이며이는 degeneracy가 1일때의 data들이다. 들도있다. 여기에서빈도수가많은친구들은비교적수가적으며드물게만나는친구들은다양하게많다는유추를취해볼수있다. 마지막으로왜문서의단어간연결관계가두극단, 즉빈도수와축퇴도에치우쳐있는지를설명하려면우리는 Gibbs free energy minimization의관점에서이문제를볼필요가있다. 즉 Gibbs free energy = enthalpy -T entropy이며빈도수가큰극단은 enthalpy가음수로작아져서 Gibbs free energy가작아지는경우이다. 또한축퇴도가큰극단은 entropy가양수로 참고문헌 [1] Steyvers, M., Griffiths, T. L., and Dennis, S., "Probabilistic inference in human semantic memory," TRENDS in cognitive science Vol.10, No.7, pp. 327-334, 1998. [2] Bak, P., Christensen, K., Danon, L., and Scanlon, T., "Unified scaling law for earthquakes," Physical Review Letters Vol.88, No.17 p. 178501, 2002. [3] Bak, P and Chen, K., "Scale dependent dimension of luminous matter in the universe," Physical Review Letters Vol.86, No.19, pp. 4215-4218, 2001. [ 4 ] Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N., and Barabasi, A.-L., "Hierarchical organization of modularity in metabolic networks," Science Vol.297, No.5586, pp. 1551-1555, 2002. [ 5 ] Furusawa, C., "Zipf's law in gene expression," Physical Review Letters Vol.90, No.8, p. 088102, 2003.
하이퍼네트워크에서본단어간긴밀성과다양성 171 [ 6 ] Barabasi A. -L., and Albert, R., "Emergence of scaling in random networks," Science Vol.286, No.5439, pp. 509-512, 1999. [7] Goldwater, S., Griffiths, T.L., and Johnson, M., "Interpolating between types and tokens by estimating power-law generators," Advances in Neural Information Processing Systems Vol.18, pp. 459-466, 2006. [ 8 ] Kechedzhi, K.E., Usatenko, O. V., and Yampolskii V. A., "Rank distribution of words in correlated symbolic systems and the Zipf law," Physical Review E Vol.72, p. 046138, 2005. [9] Zhang, B.-T., and Kim, J.-K., "DNA hypernetworks for information storage and retrieval," Lecture Notes in Computer Science, DNA12, Vol.4287, pp. 298-307, 2006. [10] Kim, S., Heo, M.-O., and Zhang, B.-T., "Text classifier evolved on a simulated DNA computer," IEEE Congress on Evolutionary Computation (CEC 2006), pp. 9196-9202, 2006. [11] Berge, C., Graphs and Hypergraphs, p.389, North- Holland Publishing, Amsterdam, 1973. [12] Ha, J.-W., Eom, J.-H., Kim, S.-C., and Zhang, B.-T., "Evolutionary hypernetwork models for aptamer-based cardiovascular disease diagnosis," The Genetic and Evolutionary Computation Conference (GECCO 2007), Vol.4, pp. 2709-2716, 2007. [13] 김준식, 김종찬, 노영균, 이동윤, 장병탁, "DNA 컴퓨팅연산과정의통계물리적예측," 한국컴퓨터종합학술대회 2005 논문집, 제 32 권제 1(B) 호, pp. 253-355, 2005. [14] Krane, K. S., Introductory Nuclear Physics, p.33, John Wiley & Sons, Inc, 1988. [15] Maslov, S., Paczuski, M., and Bak, P., "Avalanches and 1/f noise in evolution and growth models," Physical Review Letters Vol.73, No.16, pp. 2162-2165, 1994. 박찬훈 2006 년 8 월아주대학교정보및컴퓨터공학부학사. 2006 년 8 월 ~ 현재서울대학교컴퓨터공학부석사과정. 관심분야는텍스트마이닝, 정보추출, 기계학습 이은석 1990 년 3 월 ~1998 년 2 월고려대학교영어영문학과 ( 학사 ). 2001 년 3 월 ~2003 년 2 월서울대학교대학원협동과정인지과학 ( 석사 ). 2003 년 3 월 ~2006 년 2 월서울대학교협동과정인지과학 ( 박사과정수료 ). 관심분야는언어인지처리, 시지각처리, 인지처리모델링 장병탁 1986년 2월서울대학교컴퓨터공학학사 1988년 2월서울대학교컴퓨터공학석사 1992년 7월독일 Bonn 대학교컴퓨터과학박사. 1992년 8월~1995년 8월독일국립정보기술연구소 (GMD) 연구원. 1995 년 9월~1997년 2월건국대학교컴퓨터공학과조교수. 1997년 3월~현재서울대학교컴퓨터공학부교수, 생물정보학, 뇌과학, 인지과학협동과정겸임교수 2001년 1월~현재바이오정보기술연구센터 (CBIT) 센터장 2002년 6월~현재과학기술부바이오지능국가지정연구실실장. 2003년 8월~2004년 8월 MIT Computer Science and Artificial Intelligence Laboratory(CSAIL) 방문교수 2005년 12월~2006년 2월 Bernstein Center Berlin 과학재단방문교수. 관심분야는 Biointelligence, Probabilistic Models of Learning and Evolution, Molecular/DNA Computation 김준식 1991년 3월~1996년 2월서울대학교물 리학과 ( 학사 ). 1996년 3월~1998년 2월 서울대학교물리학과 ( 석사 ). 1998년 3월~ 2008년 2월서울대학교물리천문학부 ( 박 사 ). 현재서울대학교병원신경정신과 연구원. 2001년 7월~2008년 1월서울대 학교컴퓨터공학과바이오지능 (bio intelligence) 연구실 방문연구원. 관심분야는분자컴퓨팅, 뉴럴네트워크, fmri 분석등