Next Generation Search Engines ( 차세대검색엔진의발전방향및전망 ) 박민우

Next Generation Search Engines ( 차세대검색엔진의발전방향및전망 ) 박민우 2001.6.7

목차 1. 검색엔진의역사 4. 진보된검색기술 요람기유년기성년기성숙기 개요시각화자연어검색기술문서자동분류 2. 검색서비스와검색엔진 5. 차세대검색기술 서비스와엔진의차이검색서비스분석신개념의검색서비스 MAP 기반검색엔진개인화된검색엔진추론엔진 3. 검색시나리오분석 2 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 요람기 (1945년 ~1955년 ) 정보검색이란용어의사용 1950 년초반 1 세대컴퓨터의등장시기미국에서사용 1945 년 Vannervar Bush 의논문에서처음제시 검색엔진의태동기 기계번역에대한최초의제안들이제시 1949 년 Warren Weaver, Andrew D. Booth 정보검색, 기계번역에대한모든아이디어가제시된시기 이러한이론들을바탕으로 60 년대시스템을구축하는계기마련 3 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 유년기 (1960 년대 ) 위대한경험의시대 대용량의정보검색시스템의초기모델이제시 현재거론되는모든검색기법이이시대에정립 Free-text indexing 기법이보편화 정보검색시스템평가기준완성 1966년 Cyril Cleverdon : 재현율, 정확률기준마련 Relevance feedback등의신검색기술이태동 1968년 Gerard Salton : 다국어검색기법이제시 대용량정보검색시스템구현 : BRS 4 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 성년기 (1970 년대 ) 전자문서의시대 워드프로세서의등장 처리해야할문서의수와양이비약적인증가 디스크드라이브가처음발표 : 1메가당 2000달러 대용량검색시스템들의상용화 Dialog, Orbit, BRS OCLC 등장 Online Computer Library Center 세계최대규모의도서관네트웍 64개국 26,000개도서관정보를제공 5 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 성년기 (1970 년대 ) 계속 데이터베이스시스템의등장 데이터베이스와검색엔진의차이 DB : Data관점, 관리중심, 결정구조, SQL -> MIS로발전 IR : Information 관점, 검색중심, 비정형구조, 자유검색 계층모델과네트웍모델에기반한제품이주류 인공지능분야에서분리 정보검색은인공지능의한분야로취급 70년대에와서 AI에서분리, 워드처리방식접근이보편화 AI는무용론제기, IR은고속의성장 최근다시 AI-IR 접목이시도 6 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 성숙기 (1980 년대 ) 본격적인전문검색엔진등장 컴퓨터의성능향상, 저렴한가격, CD-ROM의등장 원문검색에대한요구사항증가 도서관위주의검색기술의지속적인발달 검색엔진의과거 시대적구분 : 1945년 ~1989년까지 IT 기술적구분 : WWW의등장전 (1990년초반 ) 정보검색측면에서 WWW는새로운시대를여는계기마련 7 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

1. 검색엔진의역사 시대별검색엔진관련주요기술정리 시대년도시대적배경주요기술주요인물 요기유기성기 람년년 1945~19 55 1960 년대 1970 년대 1 세대컴퓨터등장 대용량처리시스템의등장 워드프로세서등장 OCLC 등장 하이퍼텍스트개념정립기계번력이론 Free-Text 색인기법검색엔진평가기준의정립다국어검색기법대용량정보검색시스템의상용화데이터베이스등장 Vannervar Bush Warren Weaver Cyril Cleverdon Gerard Salton E.F.Codd 성기 숙 1980 년대 CD-ROM 등장 네트워크기반의정보검색시스템 8 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

2. 검색서비스와검색엔진 검색서비스와검색엔진의차이 검색서비스 인터넷검색엔진이라부른는야후, 알타비스타, 라이코스 엔진에대한비중보다브랜드에대한비중이높다. 언제라도검색엔진은교체가가능하다. Inktomi, Google -> Yahoo에검색엔진제공 검색엔진 대량의문서를취급하는도서관이나기업이주고객 90년이전의검색엔진기술들의맥을이어오고있음 DataWare, Fulcrum, Excalibur, Search97, 9 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

2. 검색서비스와검색엔진 검색서비스분석 ( 단위 : 백만원, 총 10 억페이지 ) 검색엔진의색인데이터량비교 인터넷상의정보가기하급수적으로증가함에따라서 1 개의검색엔진이모든정보를보유할수없음 전세계웹페이지수 : 10 억페이지 16 초마다 1 개의신규사이트생성 8 개월마다사이트수가 2 배로증가 하드웨어사용의부담증가 Google : 6700 대서버운영 Yahoo : 1500 대서버운영 검색엔진 웹페이지인덱스 인덱스비율 GOOGLE 350 35% FAST 340 34% ALTAVISTA 250 25% EXCITE 214 21% INFOSEEK 50 5% LYCOS 50 5% 자료 : [SEARCHENGINE.COM], [ 조선일보 (2000.8.11)] 10 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

2. 검색서비스와검색엔진 신개념의검색서비스 www.google.com Relevance feed-back counter 기법 검색의정확도는단일문서의분석을통해서결정하기어려움 해당문서를링크하고있는다른문서의수에의해랭킹결정 세계에서가장인기있는검색엔진으로자리잡음 www.directhit.com Event information analysis 다른사용자의이벤트정보를분석해정확도를결정 질의어, 페이지에머무른시간, 선택된사이트정보 인간의사용패턴에근접한검색모델을제시 11 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

R R R 3. 검색시나리오분석 통합검색시나리오 (1) 검색원문 Oracle MS SQL File 서버 1 File 서버 2 File 서버 3 인터넷 에이전트수집 DB Gate Way Index file dispatcher 색인 색인파일 색인기 색인파일 통합색인기 색인파일 색인기 검색 & 통합검색 사용자 질의기 통합질의기 질의기 사용자 질의기 12 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

R 3. 검색시나리오분석 통합검색시나리오 (2) EDMS GroupWare MS SQL L O C A L EDMS Interface EDMS 질의기 GroupWare API GW 질의기 Oracle D A T A 색인기 로컬색인파일 로컬질의기 File 서버 1 File 서버 2 B R O K E R 통합색인파일 통합질의기 메타질의기 인터넷 13 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 진보된검색기술개요 검색기술 내용 자연어검색자동분류지식검색시각화지능형에이전트 지식베이스를기반으로질의어와가장유사한질의어를통계적인기법이나퍼지이론을통해서결과를제시한다. 문서들간의키워드가중치나위치정보를기반으로유사도를기반으로관련된문서들을그룹핑하여목차를생성시킨다. 사용자들의정보나문서에추론엔진을결합시켜서새로운정보를생성하고검색할수있도록제공한다. 검색결과의재현율이높은경우검색의효과가없어지기때문에다양한시각화기법을통해서체감정확도를높을수있도록한다. 하나의시스템에서검색을완료하는것이아니라다른에이전트들과의협력을통해서최종적인결과를구해낸다. 14 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 시각화 (Visualization) 통합 View 를통합정확율향상 지식검색에서가장상단에위치한기술 HCI 를기반으로한사용자인터페이스제공 Knowledge map Cyber folder 와같이 KMS 에서주로사용되는형태 Knowledge broker 를통해서수집된지식을추론엔진또는학습엔진을통해서사용자에게개인화된모습으로서비스 Reference Brain Search : http://www.thebrain.com 3D Bot : http://www.3dbot.com/index1.html 15 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 자연어검색 (Natural Language Processing) 지능형검색기술중상용화에성공한모델 1단계 : 실시간형태소분석을통한불리언치환모델 대표적인 1단계자연어검색모델 : 엠파스 2단계 : 지식베이스를구축한뒤퍼지집합을이용한모델 AskJeeves, Autonomy, DataWare, Excalibur 가장진보된자연어검색엔진 : Autonomy 사의 AgentWare DRE(Dynamic Reasoning Engine) 동적추론엔진내장 문장을파싱하여문맥을분석하여키워드기반의의미추출 조건부확률 (Bayesian) + 신경망 (Neural Network) 기술이용 개인화를바탕으로사용자에게가장적합한결과를제시 16 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 자연어검색엔진서비스들 http://www.askjeeves.com http://www.autonomy.com 17 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 문서자동분류 (Document Clustering) Clustering 기술이란 정보나지식들의내부를의미단계에서분석하여관련성이높은정보들끼리그룹을만들어주는기법 Clustering 기술의분류 Off-line clustering 기업내부에존재하는수많은정보와지식은정리되어있지않다. 지식관리시스템을도입하기위해서는사전작업으로반드시기존지식에대한분류작업은필수적이라할수있다. On-line clustering 인터넷상의정보를실시간으로수집하는과정에서동시에많은정보를주어진시간내에원하는방식으로분류해준다. 18 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 Clustering Engine의구조 Clustering 문제접근방법 문서들간의유사도를어떻게수치화할것인가? 어떤기준으로문서를분할할것인가? 문서간의유사도구하기 기하학적인입장에서각문서사이의거리를구하는방식 문서를단어의가중치벡터로재구성 통계적인기법을이용하여빈번히발생하는단어는제외 벡터의길이에의해정규화하는과정이중요하다. 단어의위치, 단어사이의간겨, 순서등이빈도수보다더중요 자주사용되는유사도함수 Dice 계수, Jaccard 계수, Cosine 계수 19 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 적당한수의클러스터로분류하기 적당한임계치를설정하고이를기준으로군집을판단 결과의유형에따라비계층적기법과계층적기법으로구분 비계층적기법을이용한 Clustering 계층적기법에비해서계산량이적어속도가빠름 Partitioning : 전체데이터집합을분할 Criterion : 미리정의된기준이최적이되도록문서를재배치 비계층적 Clustering 방법들 Single Pass Reallocation 20 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

4. 진보된검색기술 계층적기법을이용한 Clustering 문서의중첩을허용하며최종적으로모든데이터의집합이연결돼합쳐지는형태 Dendrogram : 계층적 Clustering 을트리모양으로나타낸것 계층적 Clustering 방법들 Single link Complete link Group average link 최소분산기법 Centroid 기법 Median 기법 클러스터구조의갱신 동적인데이터집합구조에의해기존데이터의빠른추가 / 삭제가필수적이다. ( 향후연구과제 ) 21 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

5. 차세대검색기술 MAP 기반검색엔진 방사사고 (Radiant Thinking) 의형상화 ' 중심체로부터사방으로뻗어나간다 ' 는의미를지닌방사사고의표현 인간의두뇌에는약 100 억개의뉴론이연관성을가지면서존재 정보의 MAP 각문서의중요문구에대한유사도형성 각문서에대한유사도를기준으로문서의 Grouping 각 Group의관계형상화 22 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

5. 차세대검색기술 개인화된검색엔진 개인화 (Personalization) 효과적으로개인의성향에맞는검색 Relevance feedback Filtering System 사용자의성향을 interest profile 을통해서분석 Short-term user models 한번의검색으로사용자성향파악 Long-term user models 여러번의검색으로사용자성향파악 23 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

5. 차세대검색기술 Relevance feedback 개인화를위해서는반드시필요 그러나사용자로부터 relevance information 을얻어내기어렵다 Query expansion techniques 부분적으로사용되는 relevance feedback Language Models Relevance feedback 를정의하기위한언어필요 Optimal query( Salton, 1968) Bayesian classification model of retrieval (Van Rijsbergen, 1979) 확률에기반한모델제시 (Ponte 2000) 24 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

5. 차세대검색기술 추론엔진 (Inference Engine) Inference Engine 기구축된지식을이용해서새로운지식에대한추론을한다. General Logic based Inference Engines, 알고리즘을사용하는 inference Engine General Logic based Inference Engines Higher Order Logic Full first Order Logic Description Logic Datalog and Logic Programming 25 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.

5. 차세대검색기술 알고리즘을사용하는 inference Engine Problem Solving Methods Knowledge Based Systems 에서사용되는알고리즘 expert systems 에서실제로추론함수로사용된다 26 / Copyright(c) Copyright 2000 2001 WAKANO MetaWise, Inc.