검색기술트렌드와네이버의연구현황 김상범 / Director of Search Quality 2018. 5.
DISCLAIMER 본발표내용에는개인적인의견이나주장이포함되어있을수있으며이는회사의공식적입장과는무관합니다.
Outline 전세계의미있는검색서비스 7개 검색서비스를만드는과정 검색엔진핵심모듈 : Matching & Ranking Take Home Message
Google 전세계의미있는검색서비스 7 개
전세계의미있는검색서비스 7 개 Bing : 인터넷익스플로러를기반으로 Google 추격? - https://www.wired.com/2011/02/bing-copies-google/
Yahoo 전세계의미있는검색서비스 7 개
Baidu 전세계의미있는검색서비스 7 개
전세계의미있는검색서비스 7 개 Yandex : Google 이추격중 ( 2 년동안 23% 차 à 8% 차 ) http://www.liveinternet.ru/
전세계의미있는검색서비스 7 개 Seznam : 체코의검색서비스. 하락세. - 2011 년경부터역전. 현재 7:3 으로구글우세
전세계 의미있는 검색서비스 7개 네이버
웹검색이뉴스검색, 블로그검색과다른점 뉴스 / 블로그 웹 검색대상의양과위치 대략알수있음 얼마나많은문서가어디에있는지파악자체가어려움 검색컨텐츠의품질일정부분관리가능관리불가능 사용자가원하는문서여러좋은문서중몇개오직그웹페이지
웹검색이뉴스검색, 블로그검색과다른점
검색서비스를개발하는과정 먼저가이드라인에따른기계학습용학습데이터를구축하고, ➀ 네이버가지향하는좋은검색결과에대해논의 ➁ 검색평가가이드라인 Ex) 사용자가입력한질의에대해입력시점에서중요한내용을많이포함하고있으면좋은문서 사용자가입력한질의에대해입력시점에서중요한내용은별로없고이상한곳으로연결되는링크만있으면나쁜문서 ➃ 학습용데이터집합 ➂ 가이드라인에따른평가 Ex) 2017 년 11 월 13 일오후 6 시에입력된 페미니스트 라는질의에대하여 doc0001 : 5 점 doc0002 : 2 점 doc0003 : 3 점 doc0004 : 1 점
검색서비스를개발하는과정 기계학습알고리즘을이용하여검색랭킹모듈을학습 Ex) 질의가제목에매치된빈도제목전체에서질의와매치된비율질의가본문에매치된빈도질의내단어별본문매치빈도의분산해당사이트의신뢰도해당도메인의남은유효기간 5 엔지니어들의시그널발굴 서비스적용여부판단 뉴스검색학습용데이터집합 ➅ 실험데이터생성및기계학습실행 A/B online test 적합문서 새로운모델 부적합문서
랭킹모듈을 학습 한다? Learning-to-Rank - https://en.wikipedia.org/wiki/learning_to_rank
전형적인기계학습의예 만일아래와같이입력에대해출력값을내주는 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 함수 f 의 w1, w2 를구하려면? - f = x1*w1 + x2*w2
전형적인기계학습의예 만일아래와같이입력에대해출력값을내주는 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 함수 f 의 w1, w2 를구하려면? - f = x1*w1 + x2*w2 0.3 0.7
전형적인기계학습의예 만일아래와같이입력에대해출력값을내주는 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 함수 f 의 w1, w2 를구하려면? - f = x1*w1 + x2*w2 0.3 0.7 x1 x2 f 0.1 0.1 0.1 0.9 0.1 0.66 0.1 0.9 0.34 0.6 0.6 0.6
기계학습을구성하는두파트 벡터로만들어진학습데이터 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 학습알고리즘 - 신경망, 결정트리, 로지스틱회귀분석등 - 모두오픈되어있고각기업은다양한실험을통해적합한알고리즘을찾고조금씩튜닝
검색랭킹기계학습을구성하는두파트 벡터로만들어진검색랭킹용학습데이터 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0
검색랭킹기계학습을구성하는두파트 벡터로만들어진검색랭킹용학습데이터 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 x1 = x2 =
검색랭킹기계학습을구성하는두파트 벡터로만들어진검색랭킹용학습데이터 x1 x2 f 0 0 0.0 0 1 0.3 1 0 0.7 1 1 1.0 x1 = x2 =
랭킹시그널을비밀로하는이유 좋은랭킹시그널을발견하는것은엔지니어의몫 랭킹시그널을공개하면, 그랭킹시그널은빠른시일내에무력화되므로, 새로운시그널을개발해야함 엔지니어들은점점힘들어지고, 좋은서비스를만들기는점점어려워짐
랭킹시그널을비밀로하는이유 - 설리번 : 200 개정도시그널을쓴다고했는데왜얘기안해주나? - 슈미트 : 계속바뀌고 우리가힘들어지니까안된다 - 설리번 : 뭐가중요한지이런건아니더라도그냥리스트만.. - 슈미트 : 리스트도안된다 - 설리번 : 한 50 개는계속안변하고쓰지않냐? - 슈미트 : 아무튼비밀이다 - 블룸버그기자 : 너무개방적이지않은모습아닌가? - 슈미트 : 그럼블룸버그는얼마나개방적인지같이얘기해볼까?... -...
랭킹시그널을체계적방식으로추정 : SEO Business
검색서비스를개발하는과정 : wrap up ➀ 네이버가지향하는좋은뉴스검색결과에대해논의 ➁ 검색평가가이드라인 ➃ 학습용데이터집합 ➂ 가이드라인에따른평가 서비스적용여부판단 5 엔지니어들의시그널발굴 ➅ 실험데이터생성및기계학습실행 A/B online test 새로운모델
랭킹성능은어떻게구하고실제로어느정도인가? 이상적인랭킹 : 5, 4, 3, 2, 1 - DCG = 5 + 4/log_2(3) + 3/log_2(4) + 2/log_2(5) + 1/log_2(6) = 10.27 - ndcg = 10.27 / 10.27 = 1 만일 A 방법으로한랭킹이 5, 4, 3, 1, 2 라면 - DCG = 5 + 4/log_2(3) + 3/log_2(4) + 1/log_2(5) + 2/log_2(6) = 10.23 - ndcg = 10.23/10.27 = 0.996 만일 B 방법으로한랭킹이 4, 5, 3, 2, 1 라면 - DCG = 4 + 5/log_2(3) + 3/log_2(4) + 1/log_2(5) + 2/log_2(6) = 8.27 - ndcg = 8.27/10.27 = 0.805
랭킹성능은어떻게구하고실제로어느정도인가? Yahoo 에서주관한 Learning-to-rank challenge (2011 년 ) http://proceedings.mlr.press/v14/chapelle11a/chapelle11a.pdf
랭킹성능은어떻게구하고실제로어느정도인가? Yahoo 에서주관한 Learning-to-rank challenge (2011 년 ) http://proceedings.mlr.press/v14/chapelle11a/chapelle11a.pdf 랭킹이이상한건조작이아니라기술력의한계때문으로이해해주셔야합니다
검색엔진핵심모듈 : Matching and Ranking Doc 1 입력질의 matcher Doc 2 Doc 3 Doc 4 Doc 5 검색결과 ranker features... Doc N
검색엔진핵심모듈 : Matching and Ranking Doc 1 입력질의 matcher Doc 2 Doc 3 Doc 4 Doc 5 검색결과 ranker features... Doc N
Matching 사용자가입력한질의와관련이있는문서를일단모두추려내는일로, 색인 (Indexing) 에의해가능 - 1952 년, Taube 등에의해처음제안됨. 그전까지는, 많은문서들은카테고리코드를부착하는식으로관리되었음. - 그당시는매우급진적인아이디어로인식되었으나, 현재는너무당연한구조로받아들여짐. https://nlp.stanford.edu/ir-book/pdf/01bool.pdf
Matching 현재까지는단어기반매칭이주류 단어기반매칭은형태론적분석, 동의어처리가도전과제 - university / universities, rewritten / rewriting - 대학생선교회 / 대학주변교회 - 이탈리아 / 이태리, UN / United Nations, to be or not to be 그외에질의오류교정등의기술이서비스에적용됨
Semantic Matching 질의단어를조금다르게입력해도잘검색이될수있도록!
Semantic Matching @ NAVER Doc 1 입력질의 matcher Doc 2 Doc 3 Query Rewrite 동일하거나유사한의미의질의를자동으로생성하여동시에같이검색 Doc 4 Doc 5... Document Expansion 문서에없는단어도일부추가하여매칭이일어나게함 Doc N
Document Expansion QueryText = 사용자가문서를클릭했을때이용한쿼리 2198 405 514
Document Expansion QueryText 는검색에서중요한시그널로사용됨 2198 # 롯데월드이용요금 405 514 # 롯데월드이용요금 # 롯데월드입장료
Document Expansion 클릭그래프에서이웃간에는관련성이있지않을까? 2198 # 롯데월드이용요금 # 롯데월드입장료 405 514 # 롯데월드이용요금 # 롯데월드입장료
Document Expansion 질의와문서를노드, 클릭발생을간선으로하여그래프를구성 그래프의모든노드를벡터로임베딩 word2vec과의 analogy : word2vec 에서의단어 ~ 주변단어 à node2vec 에서의노드 ~ 주변노드 클릭은매일엄청나게발생하므로, incremental 한 embedding 진화가중요 node2vec: Scalable Feature Learning for Networks. A. Grover, J. Leskovec. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016.
Document Expansion 앞의방식은클릭이어느정도존재해야가능하다는문제가ㅠ
자동번역기법을응용해보자! Document Expansion - Click Graph Embedding 에의해발견된유사질의쌍을바탕으로 롯데월드이용요금 에버랜드이용요금 에코랜드이용요금할인 롯데월드입장료 에버랜드입장료 에코랜드입장료할인 - 자동번역기법 (SMT/NMT) 을활용하여유사질의를생성 대구이랜드이용요금???
자동번역기법을응용해보자! Document Expansion - Click Graph Embedding 에의해발견된유사질의쌍을바탕으로 롯데월드이용요금 에버랜드이용요금 에코랜드이용요금할인 롯데월드입장료 에버랜드입장료 에코랜드입장료할인 - 자동번역기법 (SMT/NMT) 을활용하여유사질의를생성 대구이랜드이용요금 대구이랜드입장료 - 수줍게 문서에넣어보고... 클릭이발생하면... CGE 로선순환 - 클릭이발생하지않으면... negative example
잠깐! 왜딥러닝기반번역이떴을까? 롯데월드이용요금에버랜드이용요금에코랜드이용요금할인대구이랜드이용요금 롯데월드입장료에버랜드입장료에코랜드입장료할인대구이랜드입장료 렌터카이용요금렌터카???
잠깐! 단어의의미가벡터로임베딩되는특징때문 롯데월드이용요금에버랜드이용요금에코랜드이용요금할인대구이랜드이용요금 롯데월드입장료에버랜드입장료에코랜드입장료할인대구이랜드입장료 렌터카이용요금 렌터카이용료 파리지하철이용요금 한강유람선이용요금 파리지하철이용료 한강유람선이용료
검색엔진핵심모듈 : Matching and Ranking Doc 1 입력질의 matcher Doc 2 Doc 3 Doc 4 Doc 5 검색결과 ranker features... Doc N
Ranking : Old Approaches Vector Space Model (1975 년 ) http://nlp.stanford.edu/ir-book/pdf/06vect.pdf
Ranking : Old Approaches 1. 한계효용의법칙 2. 여러단어질의에대한 and/or 제어
Ranking : Old Approaches Language Model based IR (1998) üsimple smoothing ülda (2006) http://maroo.cs.umass.edu/pdf/ir-464.pdf
2000 년대초반학교밖세상에는... 인터넷에데이터가폭발적으로늘어나기시작 야후, 구글, 네이버, 다음등검색서비스업체들이자리잡음 사람들이검색서비스를통해인터넷에서무언가를뒤지기시작 데이터 ( 문서, 클릭로그 ) 가쌓임 기계학습전공자들은데이터를보면흥분함
검색은전형적인기계학습문제아닌가! 실제로좋은검색결과를만들기위해많은시그널 ( 피쳐 ) 을사용 - 질의에있는단어가얼마나많이, 또얼마나가깝게나타났는가? - 많은사람들이보았거나링크를걸었는가? - 다른사람이어떤단어로링크를걸었는가? - 문서를작성한사람이과거에스팸작성자로경고조치됐었는가? - 언제만들어진문서인가? - 몇명이조회한문서인가? - 문서의제목과본문의관련성은높은가? ( 노이즈는좀있지만 ) 비교적대규모의학습집합을구축하게됨 - 클릭여부와그위치 ( 랭크 ) - Last Click - Quick Close
Learning-to-Rank Overview Feature vector 생성의예 = 한국경제전망 = [ 0.66, 2, 0.08, 1, 3, 1, 0, 4.2, 25, 0.43 ] 질의단어중제목에나타난단어의비율제목에출현한질의단어의총합질의단어별 본문출현빈도 / 본문길이 의합질의단어중본문에나타난단어의비율 질의의단어수전문정보를찾는질의인가? 질의에연예인이름이포함되어있나? 문서가포함된사이트의 Site Authority 문서의나이 (Age) 문서의품질 (Quality)
Learning-to-Rank Overview
Problem Definition Ranking SVM
Ranking SVM Solution Slack variable 의도입 è 틀린정도 도모델링 C 는 overfitting 을제어하는 hyperparameter
Ranking SVM : 한계 Problems - Error 에도그중요도가있는데반영을못한다 ( 검색의특수성을반영한평가척도를직접최적화하지는못함 ) - Query 별 labeled 문서수에따라 bias 가생길수있다
Ranking SVM : 한계 Problems - Error 에도그중요도가있는데반영을못한다 ( 검색의특수성을반영한평가척도를직접최적화하지는못함 ) 최적 모델 1 모델 2 3 2 2 2 1 1 1 1 1 1 1 3 2 2 1 2 1 1 1 1 1 1 2 3 2 2 1 1 1 1 1 1 1 - Query 별 labeled 문서수에따라 bias 가생길수있다
Ranking SVM : 한계 Problems - Error 에도그중요도가있는데반영을못한다 ( 검색의특수성을반영한평가척도를직접최적화하지는못함 ) 최적 모델 1 모델 2 3 2 2 2 1 1 1 1 1 1 1 3 2 2 1 2 1 1 1 1 1 1 2 3 2 2 1 1 1 1 1 1 1 - Query 별 labeled 문서수에따라 bias 가생길수있다 Q1 : 3 2 2 1 1 1 1 à 2 + 4 + 8 = 14 개의학습용 pairwise data 생성 Q2 : 3 3 2 2 2 1 1 1 1 1 à 6 + 10 + 15 = 31 개의학습용 pairwise data 생성
Ranking SVM : 한계 Problems - Error 에도그중요도가있는데반영을못한다 ( 검색의특수성을반영한평가척도를직접최적화하지는못함 ) 최적 모델 1 모델 2 3 2 2 2 1 1 1 1 1 1 1 3 2 2 1 2 1 1 1 1 1 1 2 3 2 2 1 1 1 1 1 1 1 - Query 별 labeled 문서수에따라 bias 가생길수있다 Q1 : 3 2 2 1 1 1 1 à 2 + 4 + 8 = 14 개의학습용 pairwise data 생성 Q2 : 3 3 2 2 2 1 1 1 1 1 à 6 + 10 + 15 = 31 개의학습용 pairwise data 생성 개선된 RankSVM 이나 Listwise 접근법등다양한연구가진행됨
더근본적인한계 1 : One size NEVER fits all! 모든유형의질의에걸맞는단하나의랭킹함수는존재하기어려움
더근본적인한계 2 : 랭킹 만잘하면되나? 랭킹뿐아니라, 그결과가얼마나적합한지도알아야함
Ranking and Regression : GBRT Regression Tree Regression Tree Ensemble SVM, NN, LR 같이학습방법이잘연구되어온 Numerical vector/matrix 기반 classifier 가아니라서 학습방법자체가큰연구토픽 https://homes.cs.washington.edu/~tqchen/pdf/boostedtree.pdf
Ranking and Regression : GBRT GBRT (Gradient Boosted Regression Tree)
Ranking and Regression : GBRT GBRT (Gradient Boosted Regression Tree)
일단샘플데이터로돌려보고, 괜찮다싶으면우리데이터로도돌려보면서감잡고, 이거다싶으면좀더개념을파보고, 필요하면코드도분석하고수정해서쓰거나새로만들기도하고...
새로운시도들 질의 : Bhaskar Mitra, Fernando Diaz and Nick Craswell. Learning to Match using Local and Distributed Representations of Text for Web search, WWW 2017
새로운시도들 질의 : Bhaskar Mitra, Fernando Diaz and Nick Craswell. Learning to Match using Local and Distributed Representations of Text for Web search, WWW 2017
새로운시도들 Bhaskar Mitra, Fernando Diaz and Nick Craswell. Learning to Match using Local and Distributed Representations of Text for Web search, WWW 2017
새로운시도들 Bhaskar Mitra, Fernando Diaz and Nick Craswell. Learning to Match using Local and Distributed Representations of Text for Web search, WWW 2017
Take Home Message 전세계에서검색서비스를제공하는회사는얼마안남았고, 네이버는살아남기위해불철주야열심히노력하고있습니다. 검색에서가장중요하고도비밀스러운부분은어떤랭킹시그널을사용하는지입니다. 사용자가적당히검색창에입력해도잘검색될수있도록, 정확하게단어가일치하지않아도잘매치시킬수있는방법을연구하고있습니다. 끊임없이개발되고있는랭킹알고리즘들을섭렵하고실험하며서비스에맞게변형시키고적용하는일을많은엔지니어들이하고있습니다.
Take Home Message We are hiring! http://recruit.navercorp.com
감사합니다