Google Inc. is an American public corporation, earning revenue from advertising related to its Internet search, , online m

Size: px

Start display at page:

Download "Google Inc. is an American public corporation, earning revenue from advertising related to its Internet search, , online m"

은주 초
7 years ago
Views:

1 Mathematical Modeling Lecture Google Matrix and Its Modeling information retrieval Models Sang-Gu Lee, Duk-Sun Kim Sungkyunkwan University sglee@skku.edu

2 Google Inc. is an American public corporation, earning revenue from advertising related to its Internet search, , online mapping, office productivity, social networking, and video sharing services as well as selling advertising-free versions of the same technologies. Google has also developed an open source web browser and a mobile operating system. The Google headquarters, the Googleplex, is located in Mountain View, California. As of March 31, 2009 ( ), the company has 19,786 full-time employees. The company is running thousands of servers worldwide, which process millions of search requests each day and about 1 petabyte of user-generated data every hour. A Google matrix is a particular stochastic matrix which is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The rank of each page can be generated iteratively from the Google matrix using the power method. However, in order for the power method to converge, the matrix must be stochastic, irreducible and aperiodic.

3 Vector Space Model Term by Document Matrix 사용자검색어 : 아기건강지도

4 Vector Space Model 사용자검색어 ( 아기건강지도 ) 에대하여 4 번문서가중요도가높음!

5 개선된문서검색시스템 Latent Semantic Indexing(LSI) Term by Document Matrix 에 Singular Value Decomposition 을이용 Non-negative Matrix Factorization(NMF) Web Search Engine SVD 의느린속도를극복하기위하여새롭게개발된방법 엄청나게증가한각종데이터에대하여빠른검색을할수있는새로운시스템의필요성이부각되기시작함

6 Web Search Engine 의구성 Index Module 인터넷으로부터자료를모아서데이터베이스에저장하는역할 ( 자동화된프로그램 (Bot) 이역할을수행 ) Query Module 네이버의자연어검색시스템같은사용자가주는 Query 를분석하는역할 Rank Module Index Module 로부터데이터베이스에저장된자료를이용하여다양한방법을통해중요도의순위를정하는역할

7 구글 (Google) 의검색시스템 Index Module Crawling + Indexing 병행 Ranking 계산을위하여구글행렬을만들어계산함 Query Module 단순구문분석방법을이용 ( 단어로부터추출하는방식 ) From Vector Space Model Rank Module PageRank

8 Google Matrix 와 PageRank Row Stochastic Matrix Google Matrix Hyperlink 행렬로부터구해진 Stochastic Matrix 검색엔진이보유한자체산출된중요도 PageRank Vector (Peron Vector) Row Stochastic Matrix Google Matrix

9 Google Matrix 와 PageRank

10 Google Matrix 와 PageRank Alpha 값으로 0.9 를할당하여계산 중요도순서 :

11 구글행렬에서의 Damping Factor Alpha 값을어떻게정할것인가? A. N. Langville and C. D. Meyer (2005) Deeper inside PageRank, Internet Math., Vol. 1, pp Alpha 값의 Perturbation 을추적함으로서적절한 alpha 값을확인하였다. 즉, Alpha 가 1 에가까워질수록 condition number 는증가하고, 그결과값의오차도많이생기게된다. 따라서 Google 은 Alpha 값에대하여 Alpha=0.85 를채택하고있다.

12 다른고유벡터를적용한다면? Alpha 값으로 0.9 를할당하여계산 에해당하는다른 Eigenvector 를적용 6 중요도순서 : Second Eigenvector 에대한관심이최근상승중 Taher H. Haveliwala and Sepandar D. Kamvar, The Second Eigenvalue of the Google Matrix, Google Technical Report, June, 2003

13 서울시 지하철 총 389개의 역 1호선에서 8호선으로 8개노선 분당선, 중앙선, 인천지하철과 연계 구글행렬로 분석 각 역을 노드로 판단 양방향으로 값을 가지는 그래프로 판단함

14 구글행렬로 생성 389x389 크기의 Large Sparse Matrix Mathematica를 통한 연산 Perron Vector를 찾기위하여 고유값을 구함 구해진 고유값으로부터 가장 큰 고유값에 해당하는 고유벡터를 산출 고유벡터를 계산해 줌

15 분석결과 I Pagerank 최고역 : 왕십리역, 종로 3 가역 해당두역은현재지하철노선도에서가장많은노선과교차하는환승역임 지하철역들의 Pagerank 지하철역들간의 Pagerank 임 분석결과 II Pagerank 가높은순위에들어가는역들 대체적으로여러노선이만나는환승역임을알수있음 만일자체산출중요도에지하철사용승객에대한비율이있었다면중요도가바뀌게됨 -> 현실적인사용모델을제시할수있음

16 분석결과 I 구글행렬의정보집적도 Pagerank 최고역 : 왕십리역, 종로 3 가역 해당두역은현재지하철노선도에서가장많은노선과교차하는환승역임 여러노선이만나는환승역을수치적계산만을통하여산출할수있음 Pagerank는그래프구조상에서집적도가높은노드를산출하는데효과적인방법을제시함 이러한방법은복잡도가높은다양한모델에활용될수있음. 분석결과 II Pagerank 가높은순위에들어가는역들 대체적으로여러노선이만나는환승역임을알수있음 만일자체산출중요도에지하철사용승객에대한비율이있었다면중요도가바뀌게됨 -> 현실적인사용모델을제시할수있음

17 Korean IT environments 한국내에검색서비스시장에적합한검색모델이제시되어야하며, 이를위하여현재까지검증된국제적검색모델인 PageRank 을한국내의검색시장의환경에알맞게적용해야한다. 서울신문 2008 년 4 월 18 일자해외인기사이트구글 유튜브 세컨드라이프 한국선안통하네

18 Policies 구글은최대한빨리구글을떠나게하는것이목표다. 사용자가구글이라는검색사이트에온이유는어떤정보를찾기위함이다. 따라서구글은사용자가구글에오래머물면실패한것으로보며, 최대한빨리원하는정보가있는문서로가게만드는일을목표로삼고있다. 사용자가구글사이트에서머무르는시간이짧을수록구글사이트에서광고를보는시간도줄어들고광고수익도줄어든다. 하지만원하는정보를빨리찾을수있기때문에이후에도사용자는계속구글을이용할것이고, 결과적으로구글사용빈도가늘어광고수익도늘것이라는장기적인믿음을가지고있다. 때문에아직도구글은다른사이트로가는검색관문 (portal) 으로역할을수행하고있다. ' 보내기철학 ' ' 붙잡기철학 ' 네이버의목표는사용자를최대한오래네이버에머무르게하는것이다. 오래머무르면서많은페이지를볼수록광고를더많이보게되고, 광고수익이늘어나기때문이다. 이를위해네이버는검색하려고온사람조차좀더오래네이버에머물수있도록노력한다. 검색엔진으로시작한네이버가다른사이트로보내주는포탈 (portal= 관문 ) 의성격을포기하고토탈서비스 (total service= 종합서비스 ) 사이트로변하고있는이유는사용자를붙잡으려는 ' 붙잡기철학 ' 을가지고있기때문이다.

19 New Model with Google Matrix 기존모델행렬 내부연결모델행렬 Naver, Daum, Paran 기존모델 내부연결모델

20 Ideas Kirkland(2005) 의 Google 행렬의 Perturbation 연구

21 New Model with Google Matrix : Portal Site Area Main Idea : 기존의 S 를구하는것에 Portal Site 부분에대하여별도의연결성을추가하여계산을하고, 이를통한가중치를부여함으로서, 자체보유하고있는컨텐츠의노출도를증가시키는방안임 앞의예와동일

22 New Model with Google Matrix : Portal Site Area 중요도순서 : 이전중요도순서 :

23 New Model with Google Matrix 중요도순서 : : Portal Site Area 중요도순서 : Alpha 와 Beta 값을적절하게조정하므로서자회사가보유한문서의중요도를조정하여노출할수있게되며, 이를통하여좀더개선된검색엔진을개발할수있다.

24 [Brin et al, 1998] S. Brin and L. Page (1998) The anatomy of a large-scale hypertextual web search engine, Comput. Networks ISDN Systems, 33 pp [Page et al, 1998] S. Brin & L. Page & R. Motwami and T. Winograd (1998) The PageRank Citation Ranking: Bringing Order to the Web, Technical report, Computer Science Department, Stanford University, Stanford, CA [Deerwester et al, 1990] S. Deerwester & S. Dumais & G. W. Furnas & T. K. Landauer and R. Harshman (1990) Indexing by Latent Semantic Analysis, Journal of the American Society for Information Science, Vol. 41 No. 6, pp [Brand, 2006] M. Brand (2006) Fast Low-Rank Modifications of the Thin Singular Value Decomposition. Linear Algebra and Its Applications Vol. 415, pp [Meyer, 2000] C. D. Meyer (2000) Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia [Berry, 2001] M. W. Berry (2001) Computational Informatioan Retrieval, SIAM, Philadelphia [Zha et al, 1998] H. Zha & O. Marques and H. D. Simon (1998) A subspace-based model for information reteival with applications in latent semantic indexing, Lecture Nores Comp. Sci., Vol 1457, pp [Lee et al, 1999] D. D. Lee and H. Sebastian Seung (1999) Learning the parts of objects by non-negative matrix fractorization, Nature, Vol. 401, pp [Lee et al, 2001] D. D. Lee and H. Sebastian Seung (2001) Algorithms for the non-negative matrix factorization, Adv. Neur. Inform. Proc., Vol. 13, pp [Paatero et al, 1994] P. Paatero and U. Tapper (1994) Positive matrix factorization : a non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, Vol 5, pp [Paatero et al, 1997] P. Paatero and U. Tapper (1997) Least squares formulation of robust non-negative factor analysis, Chemomet. Intell. Lab. Sys., Vol. 37, pp [Kleinberg, 1999] Jon Kleinberg (1999), Authoritative sources in a hyperlinked environment, Journal ACM, Vol 46, pp [Langville, 2006] A. N. Langville and C. D. Meyer (2006) Google's PageRank and Beyond : The Science of Search Engine Rankings, Princeton University Press, Princeton, NJ [Langville, 2005] A. N. Langville and C. D. Meyer (2005) Deeper inside PageRank, Internet Math., Vol. 1, pp [Gross et al, 2003] Gross, Jonathan L., and Yellen, Jay (2003), Handbook of Graph Theory. CRC Press. ISBN [Leeuw, 2006] Jan de Leeuw, Principal component analysis of binary data by iterated singular value decomposition, Computational Statistics & Data Analysis 50 (2006) [Haveliwala et al, 2003] Taher H. Haveliwala and Sepandar D. Kamvar, The Second Eigenvalue of the Google Matrix, Google Technical Report, June, 2003

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA 논문 10-35-03-03 한국통신학회논문지 '10-03 Vol. 35 No. 3 원활한 채널 변경을 지원하는 효율적인 IPTV 채널 관리 알고리즘 준회원 주 현 철*, 정회원 송 황 준* Effective IPTV Channel Control Algorithm Supporting Smooth Channel Zapping HyunChul Joo* Associate