순위(정보 검색)

질의 순위는 검색엔진 뒤에 숨겨진 과학/공학 분야인 정보검색^[1](IR)의 근본적인 문제 중 하나이다.질의 $q$ 와 질의와 일치하는 문서의 집합 $D$ 가 주어지면, 문제는 사용자에게 표시되는 결과 목록의 초기에 "최상의" 결과가 나타나도록 어떤 기준에 따라 문서를 $D$ 로 정렬하는 것이다.정보 검색의 측면에서 순위를 매기는 것은 컴퓨터 과학에서 중요한 개념이며 검색 엔진 질의나 추천자 시스템과 같은 많은 다른 응용 분야에서 사용된다.대부분의 검색 엔진은 사용자에게 정확하고 관련 있는 결과를 제공하기 위해 순위 알고리즘을 사용한다.null

역사

페이지 순위에 대한 개념은 1940년대로 거슬러 올라가고 그 생각은 경제 분야에서 비롯되었다.1941년 Washily Leontief는 자원을 공급하는 다른 분야의 중요성에 기초하여 한 나라의 부문을 평가하는 반복적인 방법을 개발했다.1965년 산타바바라 캘리포니아 대학의 찰스 H 허벨(Charles H H Hubbell)은 그들을 지지하는 사람들의 중요성에 기초하여 개인의 중요성을 판단하는 기법을 출판하였다.null

가브리엘 핀스키와 프란시스 나린은 순위 저널에 대한 접근법을 생각해냈다.그들의 규칙은 저널이 다른 중요한 저널에 인용될 경우 중요하다는 것이었다.코넬 대학교의 컴퓨터 과학자인 존 클라인버그는 하이퍼텍스트 유도 토픽 검색 또는 HITS라고 불리는 페이지 랭크에 대해 거의 동일한 접근법을 개발했고, 그것은 웹 페이지를 "허브"와 "권위"로 취급했다.null

구글의 페이지랭크 알고리즘은 구글 창업자인 세르게이 브린과 래리 페이지가 1998년 개발한 것으로 구글이 검색 결과에서 웹 페이지를 순위를 매기는 방식의 핵심 부분이다.위의 모든 방법은 링크 구조를 활용하고 반복적인 접근법을 필요로 하기 때문에 다소 유사하다.^[2]null

모델 순위 매기기

순위 함수는 다양한 수단에 의해 평가된다. 가장 간단한 것 중 하나는 일부 고정 k에 대해 1k 상위 랭크 결과의 정밀도를 결정하는 것이다. 예를 들어, 많은 질의에 대해 평균적으로 관련성이 있는 상위 10개 결과의 비율을 결정하는 것이다.null

IR 모델은 크게 세 가지 유형으로 나눌 수 있다.부울 모형 또는 BIR,^[3] 벡터 공간 모형 및 확률론적 모형null

부울 모델

Boolean Model 또는 BIR은 각 쿼리가 대수적 표현식을 가진 관계 대수학의 기본 원리를 따르고, 서로 완전히 일치하지 않는 한 문서를 가져오지 않는 단순 기준선 쿼리 모델이다.쿼리가 문서(1)를 가져오거나 문서(0)를 가져오지 않기 때문에 순위를 매기는 방법론이 없다.null

벡터 공간 모델

부울 모델은 전체 일치 항목만 가져오기 때문에 부분적으로 일치하는 문서의 문제는 다루지 않는다.벡터 스페이스 모델은 각각 가중치가 할당된 인덱스 항목의 벡터를 도입하여 이 문제를 해결한다.가중치는 양수(완전하거나 어느 정도 일치하는 경우)에서 문서가 있는 경우 음수(비일치 또는 완전히 반대되는 경우)까지 다양하다.용어 빈도 - 역 문서 빈도(tf-idf)는 가중치가 용어(예: 단어, 키워드, 구문 등)이고 치수는 말뭉치 내부의 단어 수입니다.null

질의와 문서의 유사성 점수는 코사인 유사성을 이용하여 질의 중량 벡터와 문서 중량 벡터 사이의 코사인 값을 계산하여 확인할 수 있다.원하는 문서는 유사성 점수에 따라 순위를 매겨 가져올 수 있으며, 가장 높은 점수 또는 질의 벡터와 가장 관련성이 높은 상위 k 문서를 가져오면 된다.null

확률론적 모형

확률론적 모형에서 확률 이론은 수학적 용어로 검색 과정을 모델링하는 주요 수단으로 사용되어 왔다.정보 검색의 확률 모델은 1960년 마론과 쿤스에 의해 도입되었고, 로버스턴을 비롯한 다른 연구자들에 의해 더욱 발전되었다.Spack Jones와 Willett(1997)에 따르면:확률론적 개념을 도입하는 근거는 다음과 같다.IR 시스템은 자연 언어를 다루며, 이것은 시스템이 특정 질의와 관련된 문서를 확실히 기술할 수 있도록 하기에는 너무 부정확하다.null

모델은 확률 이론을 정보 검색에 적용한다(사건은 발생의 0%에서 100%까지 가능성이 있다).즉, 확률 모델에서 관련성은 확률로 표현된다.여기서 문서는 관련성이 감소하는 순서로 순위가 매겨진다.IR 프로세스에서 불확실성 요소를 고려한다. 즉, 시스템에서 검색한 문서가 주어진 질의와 관련되는지 여부에 대한 불확실성을 고려한다.null

확률 모델은 어떤 방법에 근거하여 문서가 주어진 질의와 관련될 확률을 추정하고 계산하고자 한다.이러한 정보 검색의 맥락에서 "이벤트"는 질의와 문서 사이의 관련성의 확률을 가리킨다.다른 IR 모델과 달리 확률 모델은 관련성을 정확한 미스매치 측정으로 취급하지 않는다.null

모델은 질의와 문서 사이의 관련성을 결정하기 위해 다양한 방법을 채택한다.확률 모델의 관련성은 질의와 문서의 유사성에 따라 판단된다.유사성 판단은 용어 빈도에 더 의존한다.null

따라서 한 용어(B)로만 구성된 질의의 경우 특정 문서(Dm)가 관련성이 있다고 판단할 확률은 질의어(B)를 제출하고 해당 용어를 제출한 사용자 수(B)와 관련하여 문서(Dm)를 관련성이 있다고 간주하는 사용자의 비율이다.마론과 쿤의 모델에 나타난 바와 같이, 특정 질의어(B)를 제출하는 사용자가 개별 문서(Dm)를 관련성이 있다고 판단할 확률로 나타낼 수 있다.null

Salton과 McGill에 따르면, 이 모델의 본질은 관련 문서의 다양한 용어의 발생 확률에 대한 추정치를 계산할 수 있다면, 관련성이 있거나 그렇지 않은 경우, 문서가 검색될 확률을 추정할 수 있다는 것이다.null

여러 실험에서 확률론적 모형이 좋은 결과를 산출할 수 있다는 것을 보여주었다.그러나 그러한 결과는 부울 또는 벡터 공간 모델을 사용하여 얻은 결과보다 충분히 우수하지 않다.^[4] ^[5]

평가 조치

평가의 가장 일반적인 척도는 정밀도, 리콜, f-점수다.그것들은 주문되지 않은 문서 세트를 사용하여 계산된다.현대 검색 엔진에서 표준화된 검색 결과를 평가하기 위해 이러한 조치를 확장하거나 새로운 조치를 정의해야 한다.순위 검색 컨텍스트에서 적절한 검색된 문서 집합은 검색된 상위 k개 문서에 의해 자연스럽게 제공된다.그러한 각 집합에 대해 정밀도 및 회수 값은 정밀도-리콜 곡선을 제공하도록 플로팅될 수 있다.^[6]null

정밀도

정밀도는 회수 과정의 정확성을 측정한다.관련 문서의 실제 세트가 I로 표시되고, 회수된 문서 세트가 O로 표시되면, 정밀도는 다음과 같이 부여된다.

{\text{Precision}={\frac {\{\text}}I}\}\cap \{\text{{\text}O}\}{{{\text}{{{\text}{O}\}}

리콜

리콜은 IR 프로세스의 완전성을 측정하는 척도다.관련 문서의 실제 세트가 I로 표시되고 회수된 문서 세트가 O로 표시되면, 리콜은 다음과 같이 제공된다.

{\text{Recall}={\frac {\{\text}}I}\}\cap \{\text{{\text}O}\}{{{\text}{{{\text}{I}\} }

F1 점수

F1 스코어는 정밀도와 회수 조치의 결합을 시도한다.그것은 그 둘의 조화 평균이다.P가 정밀도이고 R이 회수인 경우 F-점수는 다음과 같이 주어진다.

F_{1}=2\cdot {\frac {\mathrm {P} \cdot \mathrm {R}{\mathrm {P} +\mathrm {R}}}}}}}}}

페이지 순위 알고리즘

페이지랭크 알고리즘은 링크를 무작위로 클릭하는 사람이 특정 페이지에 도착할 가능성을 나타내는 데 사용되는 확률 분포를 출력한다.PageLank는 모든 크기의 문서 모음에 대해 계산할 수 있다.여러 연구 논문에서 계산 과정이 시작될 때 수집된 모든 문서에 분포가 고르게 분포되어 있다고 가정한다.PageLank 계산은 이론적 참 값을 보다 가깝게 반영하기 위해 대략적인 PageLank 값을 조정하기 위해 수집을 통해 여러 번 통과해야 한다.공식은 다음과 같다.

PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}}

즉, 페이지 u에 대한 PageLrank 값은 세트 B에_u 포함된 각 페이지 v(페이지 u에 연결하는 모든 페이지를 포함하는 세트)의 PageLank 값에 따라 달라지며, 이 값을 페이지 v에서 링크의 L(v) 양으로 나눈다.

HITS 알고리즘

PageLrank와 마찬가지로 HITS는 페이지의 관련성을 분석하기 위해 링크 분석을 사용하지만 전체 웹 그래프가 아닌 작은 서브그래프 세트에서만 작동하며 질의에 의존한다.하위 그래프는 가장 높은 순위를 매긴 페이지를 가져와 표시하는 허브와 당국의 가중치에 따라 순위가 매겨진다.^[7]null

참고 항목

순위 결정 학습: 순위 문제에 기계 학습 적용

참조

^ Piccoli, Gabriele; Pigni, Federico (July 2018). Information systems for managers: with cases (Edition 4.0 ed.). Prospect Press. p. 28. ISBN 978-1-943153-50-3. Retrieved 25 November 2018.
^ Franceschet, Massimo (17 February 2010). "Scientist Finds PageRank-Type Algorithm from the 1940s". www.technologyreview.com.
^ Datta, Joydip (16 April 2010). "Ranking in Information Retrieval" (PDF). Department of Computer Science and Engineering, Indian Institute of Technology. p. 7. Retrieved 25 April 2019.{{cite web}}: CS1 maint : url-status (링크)
^ 디지털 시대의 추, H. 정보 표현 및 검색.뉴델리: Ess Ess 출판.
^ G.G.처드하리현대 정보 검색 소개.페이셋 출판사.
^ Manning, Christopher; Raghavan, Prabhakar; Schutze, Hinrich. Evaluation of ranked retrieval results. Cambridge University Press.
^ Tanase, Racula; Radu, Remus (16 April 2010). "Lecture #4: HITS Algorithm - Hubs and Authorities on the Internet".

[1] Piccoli, Gabriele; Pigni, Federico (July 2018). Information systems for managers: with cases (Edition 4.0 ed.). Prospect Press. p. 28. ISBN 978-1-943153-50-3. Retrieved 25 November 2018.

[2] Franceschet, Massimo (17 February 2010). "Scientist Finds PageRank-Type Algorithm from the 1940s". www.technologyreview.com.

[3] Datta, Joydip (16 April 2010). "Ranking in Information Retrieval" (PDF). Department of Computer Science and Engineering, Indian Institute of Technology. p. 7. Retrieved 25 April 2019.{{cite web}}: CS1 maint : url-status (링크)

[4] 디지털 시대의 추, H. 정보 표현 및 검색.뉴델리: Ess Ess 출판.

[5] G.G.처드하리현대 정보 검색 소개.페이셋 출판사.

[6] Manning, Christopher; Raghavan, Prabhakar; Schutze, Hinrich. Evaluation of ranked retrieval results. Cambridge University Press.

[7] Tanase, Racula; Radu, Remus (16 April 2010). "Lecture #4: HITS Algorithm - Hubs and Authorities on the Internet".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search