SVM의 랭킹

머신러닝에서 랭킹 SVM은 서포트 벡터 머신 알고리즘의 변형으로 특정 랭킹 문제를 해결하기 위해 사용됩니다(순위 매기기 학습을 통해).순위 SVM 알고리즘은 Thorsten Joachims에 의해 ^[1]2002년에 발표되었습니다.이 알고리즘의 원래 목적은 인터넷 검색 엔진의 성능을 향상시키는 것이었다.그러나 Ranking SVM을 사용하여 Rank ^[2]SIFT와 같은 다른 문제를 해결할 수 있는 것으로 나타났습니다.

묘사

Ranking SVM 알고리즘은 특정 쿼리와 얼마나 '관련성'이 있는지에 따라 결과를 적응적으로 정렬하기 위해 쌍별 랭킹 방법을 사용하는 학습 검색 기능입니다.Ranking SVM 함수는 검색 쿼리와 가능한 각 결과의 기능 간의 일치를 설명하기 위해 매핑 함수를 사용합니다.이 매핑 함수는 각 데이터 쌍(예: 검색 쿼리 및 클릭된 웹 페이지)을 피쳐 공간에 투영합니다.이러한 기능은 대응하는 클릭스루 데이터(특정 쿼리와 관련된 페이지의 프록시 역할을 할 수 있음)와 조합되어 랭킹 SVM 알고리즘의 트레이닝 데이터로 사용할 수 있습니다.

일반적으로 SVM 랭킹에는 트레이닝 기간 중 다음 3가지 단계가 포함됩니다.

쿼리와 클릭된 페이지 간의 유사성을 특정 기능 공간에 매핑합니다.
스텝 1에서 얻은 두 벡터 사이의 거리를 계산합니다.
이는 표준 SVM 분류와 유사한 최적화 문제를 형성하며 일반 SVM 솔버로 이 문제를 해결합니다.

배경

순위 부여 방법

C $(\$ 가 $\mathbb {C}$ N $(\displaystyle$ N $)$ $c_{i}$ $(\$ 를 $r$ $r$ 하는 $r$ 데이터 세트라고 $\mathbb {C}$ 합니다. $r$ $(\displaystyle$ \ $mathbb {C$ 는 $C(\$ \ $mathbb {C})$ 에 $\mathbb {C}$ 적용되는 랭킹 방식입니다 $.$ d는 N $N\times N$ × $(style$ N\times N $)$ $N\times N$ 매트릭스로 표시됩니다.If the rank of $c_{i}$ is higher than the rank of $c_{j}$ , i.e. $r\ c_{i}<r\ c_{j}$ , the corresponding position of this matrix is set to value of "1".그렇지 않으면 해당 위치의 요소가 값 "0"으로 설정됩니다.

켄달스타우^[3]^[4]

Kendall의 타우는 동일한 데이터 집합에 대한 두 순위 방법을 비교하는 데 일반적으로 사용되는 Kendall 타우 순위 상관 계수도 나타냅니다.

$r_{1}$ 1 $(\$ 과 $r_{1}$ r $r_{2}$ (\ $displaystyle r_{2})$ 가 $r_{2}$ 데이터 $\mathbb {C}$ C(\ $displaystyle \mathbb {C$ 에 적용되는 랭킹 방식이라고 합니다. $r_{1}$ 1 $(\$ 과 $r_{1}$ $r_{2}$ 2(\ $displaystyle r_2})$ 사이의 $r_{2}$ Kendall's Tau는 다음과 같습니다.

$\displaystyle \displaystyle (r_{1},r_{2})={P-Q\over P+Q}=1-{2Q\over P+Q}$

$P$ 서P(\ $displaystyle$ P $)$ 는 $P$ 일치 쌍의 $수이고$ Q(\ $displaystyle$ Q $)$ 는 $Q$ 불일치 쌍의 수(반전)입니다. $displaystyle d_{i}$ 와 $d_{i}$ $d_{j}$ $d_{j}$ $($ $displaystyle d_{j})$ 쌍은 $\$ 와 $r_{a}$ $r_b$ $d_{i}$ $d_{j}$ $\$ ${$ $b$ $}$ $r_{a}$ 이 $d_{i}$ 와 $d_{i}$ $dj\displaystyle$ $d_{i}$ d_{ $j}$ 의 순서가 일치하면 불일치합니다.

정보 검색^[5]^[6]^[7] 품질

정보 검색 품질은 보통 다음 세 가지 측정을 통해 평가됩니다.

정확
리콜
평균 정밀도

데이터베이스에 대한 특정 쿼리의 경우 $P_{relevant}$ 내의 관련 정보 요소 세트를 $P_{relevant}$ e $P_{relevant}$ $P_{relevant}$ a $P_{relevant}$ { $displaystyle$ P _ { $referenced$ } 로 $P_{relevant}$ $P_{retrieved}$ 취득한 정보 요소 세트를 $P_{retrieved}$ $P_{retrieved}$ r $P_{retrieved}$ $P_{retrieved}$ $P_{retrieved}$ $P_{retrieved}$ { $displaystyle P$ _ { $retrieved$ } 로 $P_{retrieved}$ $P_{relevant}$ .위의 세 가지 측정은 다음과 같이 나타낼 수 있습니다.

${begin{array} {lcl} Precision = cap P_{retrieved}\right\vert P_{retrieved}\left\vert P_{retrieft};\Recall=cap P_{retript}\vert P_{ret }\vert leftretrieft }\retrieftrieft }AveragePrecision=\int _{0}^{1}{Prec(호출)}dRecall,\\end{array}$

$Prec(Recall)$ 서 P $Prec(Recall)$ e $Prec(Recall)$ ( $Prec(Recall)$ $Prec(Recall)$ $Prec(Recall)$ $Prec(Recall)$ ) { $displaystyle$ Prec ( $Recall$ ) the $Prec(Recall)$ 、 $R$ e $c$ a $l$ { $displaystyle$ Recall $Recall$ }의 $P$ $r$ e $c$ $i$ $s o$ n { $displaystyle$ Precision} 입니다 $Precision$ .

$r^{*}$ $（$ { $displaystyle$ r $r^{*}$ ^ { * } ） $r_{f(q)}$ $r_{f(q)}$ f $r_{f(q)}$ $r_{f(q)}$ q $）{$ $displaystyle r$ $r_{f(q)}$ $r_{f(q)}$ { $r_{f(q)}$ $f ( q$ ) $r_{f(q)}$ 의 $r_{f(q)}$ $r_{f(q)}$ Average Precision의 하한은 다음과 같이 나타낼 수 있습니다.

$AvgPrec(r_{f(q)}\geq {1 \over R}\left [Q+{\binom {R+1}{2}\right]^{-1}({i=1}^{\sqrt {i})^{2}$

$(\displaystyle$ Q $)$ 는 $Q$ $r^{*}$ r ${\$ {\ $displaystyle$ r $^{*}$ $r_{f(q)}$ ( $r_{f(q)}$ ) { $displaystyle r_{f(q)}}$ $r^{*}$ 의 삼각행렬 상부에 있는 서로 다른 요소의 수이며 $,$ $R$ (\ $displaystyle$ R $)$ 은 $R$ 데이터 세트의 관련 요소 수입니다.

SVM 분류기^[8]

$({\vec {x}}_{i},y_{i})$ $({\vec {x}}_{i},y_{i})$ $({\vec {x}}_{i},y_{i})$ , $({\vec {x}}_{i},y_{i})$ i $({\vec {x}}_{i},y_{i})$ ) { $displaystyle$ { \ $vec$ { $x } _$ { $i$ ${\vec {x}}_{i}$ } 、 $y$ _ { i $({\vec {x}}_{i},y_{i})$ } 、 ${\vec {x}}_{i}$ ${\vec {x}}_{i}$ { $display$ style { $x$ ${\vec {x}}_{i}$ } $_$ { $i$ ${\vec {x}}_{i}$ } 、 $y_{i}$ $}$ the $({\vec {x}}_{i},y_{i})$ $y_{i}$ ( ( $→$ $y_{i}$ i _ $display style$ { i } $xxx$ { c } ） ,,,,, 。). 이러한 데이터 세트의 일반적인 SVM 분류기는 다음과 같은 최적화 문제의 해결책으로 정의할 수 있습니다.

${\displaystyle{array}{lcl}\mathrm {vec {w},{\vec {xi}}={\over 2){\vec {w}}+CF\sum _{i}^{\cd}}\st.\\{\vec {array}{lcl}\forall y_{i}({\vec {w}}){\vec {x}_{i}+b)\geq 1-\xi _{i}{\xi};\end{array}}\\\mathrm {where,\}\b}\clarray}\\\b}$

위의 최적화 문제의 해결책은 특징 $x_{i}$ x $(\$ )의 선형 조합으로 나타낼 수 있습니다.

${w}^{*}=\sum _{i}{\alpha _{i}y_{i}x_{i}$

$\alpha _{i}$ 서 $\alpha _{i}$ i $\alpha _{i}$ \ $displaystyle \alpha$ _ ${i}$ 는 $\alpha _{i}$ 결정되는 계수입니다.

SVM의 랭킹 알고리즘

손실 함수

$\tau _{P(f)}$ $\tau _{P(f)}$ P ( $\tau _{P(f)}$ ) $\tau _{P(f)}$ { $display$ $style$ $\tau _{P(f)}$ \ $tau _$ { P ( f $\tau _{P(f)}$ ) } $}$ method $r^{*}$ method method 、 r $（$ \ $display$ $style$ $\tau _{P(f)}$ r $^$ { * }} proposed $r^{*}$ ) ) $\tau _{P(f)}$ method method method $r_{f(q)}$ method method method ) method method method $r_{f(q)}$ $f$ r $_$ $\tau _{P(f)}$ { $f$ ( $\tau _{P(f)}$ $q$ ) $r_{f(q)}$ ） $expected$ method method method method method method method method method method r r r r r r r r r $\tau _{P(f)}$ expected r r r expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected expected $expected$ $r_{f(q)}$ f ( $r_{f(q)}$ ) { $display style$ r _ { $f$ ( $q$ ) $r_{f(q)}$ } 。

예상 손실 함수^[9]

손실함수로서 음의 $\tau _{P(f)}$ P $\tau _{P(f)}$ ( \ $displaystyle$ $\tau _{P(f)}$ \ $display$ P ( $r_{f(q)}$ ${ P$ ( $f$ ) $r_{f(q)}$ $p$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ ${ f$ ( $q )}$ $r_{f(q)}$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ c $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ e d $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ - （ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ ） $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ - $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ f $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ ∫ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ ） $L_{expected}=-\tau _{P(f)}=-\int \tau (r_{f(q)},r^{*})dPr(q,r^{*})$ $t \tau(r_{f(q),r^{*})dPr(q,r^{*})}$

$Pr(q,r^{*})$ 서 P $Pr(q,r^{*})$ r ( $Pr(q,r^{*})$ , $Pr(q,r^{*})$ $){$ $displaystyle$ Pr $( q$ , $r^$ { * $r^{*}$ } $}$ 는 $Pr(q,r^*)$ $특정$ 쿼리q { \ $displaystyle$ q $q$ }에 $r^{*}$ $r^{*}$ r의 통계적 분포입니다.

경험적 손실 함수

예상 손실 함수를 적용할 수 없기 때문에 실제 훈련 데이터에 대해 다음과 같은 경험적 손실 함수를 선택한다.

${displaystyle L_{emirical}=-\tau _{S}(f)=-{1 \over n}\sum _{i=1}^{n}{\sum (r_{f(q_{i}),r_{i}^*}}}$

트레이닝 데이터 수집

$\displaystyle$ n.i.d $n$ . 쿼리는 데이터베이스에 적용되며 각 쿼리는 랭킹 방법에 해당합니다.교육 데이터 세트에는n개의 $n$ $요소$ 가 $.$ 각 요소는 쿼리와 대응하는 랭킹 방법을 포함한다.

기능 공간

피쳐 공간에서 레이블이 지정된 점

각 쿼리와 데이터베이스의 요소를 피쳐 공간에 매핑하려면 매핑 함수 $\Phi (q,d)$ ( $\Phi (q,d)$ $\Phi (q,d)$ { $displaystyle \Phi(q, d)}$ 가 필요합니다 $\Phi (q,d)$ ^[10]^[11].그런 다음, 피쳐 공간의 각 점에 순위 지정 방법에 따라 특정 순위가 지정됩니다.

최적화 문제

교육 데이터에 의해 생성된 포인트는 순위 정보(라벨)도 포함하는 피쳐 공간에 있습니다.레이블이 지정된 이러한 점을 사용하여 해당 점의 순서를 지정하는 경계(분류자)를 찾을 수 있습니다.리니어 케이스에서는, 그러한 경계(분류자)가 벡터이다.

$c_{i}$ i $(\$ $displaystyle$ $c_{i})$ 와 $c_{i}$ $c_{j}$ j(\ $displaystyle c_{j})$ 가 $c_{j}$ 데이터베이스 내의 2가지 요소로, $c_{i}$ i $($ $(c_{i},c_{j})\in r$ , $c$ j $)$ 의 랭크(\ $displaystyle c_{i})$ 가 $c_{i}$ $특정$ $c_{j}$ $(\$ $displaystyle c_{j$ })보다 $(c_i,c_j) \in r$ $c_{j}$ 높을 경우 $r(c_displaystyle)$ 를 나타냅니다. $style$ r $r$ ${\vec {w}}$ w $→$ ${\display\vec {w}}$ 을 ${\vec {w}}$ (를) 피쳐 공간에서 선형 분류자 후보로 합니다.그 후, 랭킹의 문제는 다음의 SVM 분류의 문제로 해석할 수 있습니다.하나의 순위 매기기 방식은 하나의 쿼리에 대응합니다.

${array}{lcl}\mathrm {vec {w},{\vec {xi }}={1 \over 2){\vec {w}}\cdot {w}+C_{stant}\sum {xi _i,jk}\s}\t.\\{\begin{array}{lcl}\forall \xi _{i,j}\geq 0\\forall (c_{i},c_{j})\in r_{k}^{*}\{\vec {w}\{Phi (q_{1},c_{i})-\Phi (q_{j})\{\vec {w}}(\Phi(q_{n},c_{i})-\Phi(q_{n},c_{j})\geq 1-xi _{i,j};\\mathrm {여기\} \k\in\left\{1,2,n\},\j\},\j,\,\j,\,\\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\\right\}.\\end{array}\end{array}$

위의 최적화 문제는 기존의 SVM 분류 문제와 동일하기 때문에 이 알고리즘을 Ranking-SVM이라고 부릅니다.

W 후보

w 후보 없음

검색 기능

교육 샘플에서 얻은 최적의 ${\vec {w}}^{*}$ w ${\vec {w}}^{*}$ ${\$ {\ $style {w}}^{*}$ 는 $\vec w^*$ 다음과 같습니다.

${w}^{*}=\sum {alpha _{k,l}^{*}\Phi(q_{k},c_{i})}$

따라서 이러한 최적의 분류기를 기반으로 검색 기능을 구성할 수 있습니다.
$새로운$ $q$ 의 경우 $q$ 검색 $기능$ 은 먼저 데이터베이스의 모든 요소를 피쳐 공간에 투영합니다.그런 다음 최적의 벡터를 사용하여 내부 제품의 값을 기준으로 이러한 특징점을 정렬합니다.각 특징점의 순위는 $쿼리$ q\ $displaystyle$ q $q$ 에 대응하는 데이터베이스 요소의 순위입니다.

랭크 SVM 적용

랭크 SVM을 적용하여 쿼리에 따라 페이지 순위를 매길 수 있습니다.이 알고리즘은 클릭스루 데이터를 사용하여 훈련할 수 있습니다.여기서는 다음 3가지 부분으로 구성됩니다.

질문하다.
검색 결과 순위 표시
사용자가 클릭한 검색 결과

2와 3의 조합에서는 완전한 SVM 알고리즘을 적용하는 데 필요한 완전한 훈련 데이터 순서를 제공할 수 없습니다.대신, 교육 데이터의 순위 정보의 일부를 제공합니다.따라서 알고리즘은 다음과 같이 약간 수정할 수 있습니다.

${array}{lcl}\mathrm {vec {w},{\vec {xi }}={1 \over 2){\vec {w}\cdot {w}+C_{ontant}\sum {xi _i _i , jk}\s}.\\{\begin{array}{lcl}\forall \xi _{i,j,k}\geq 0\\\forall (c_{i},c_{j})\in r_{k}^{'}\{\vec {w}\{Phi (q_1,c_{i})-\Phi (q_{j})\{\vec {w}}(\Phi(q_{n},c_{i})-\Phi(q_{n},c_{j})\geq 1-xi _{i,j};\\mathrm {여기\} \k\in\left\{1,2,n\},\j\},\j,\,\j,\,\\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\xi,\\right\}.\\end{array}\end{array}$

$r$ ${\$ \ $displaystyle$ r $'$ 방식은 전체 $r'$ 데이터셋의 순위 정보를 제공하는 것이 아니라 전체 순위 방식의 하위 집합입니다.따라서 최적화 문제의 상태는 원래의 Ranking-SVM에 비해 완화됩니다.

레퍼런스

^ Joachims, T. (2002), "클릭 스루 데이터를 사용한 검색 엔진 최적화", 지식 발견 및 데이터 마이닝에 관한 ACM 회의 진행
^ Bing Li; Rong Xiao; Zhiwei Li; Rui-Cai; Bao-Li-Li-Li-Li-Li-Li Zhang; "랭크 SIFT: 반복 가능한 지역 관심점 순위 매기기 학습", 컴퓨터 비전 및 패턴 인식(CVPR), 2011년
^ M.Kemeny. 순위 상관법, 하프너, 1955
^ A.Mood, F.회색부리, 그리고 D.Boes. 통계학 입문.맥그로힐, 제3판, 1974년
^ J. 케메니와 L. 스넬.사회과학의 수학적 모델.진앤코 1962
^ Y. Yao. 문서의 사용자 선호도에 따라 검색 효과를 측정합니다.미국정보과학회지, 46(2): 133-145, 1995.
^ R.Baeza- 예이츠와 B.리베이로네토현대 정보 검색.Addison-Wesley-Longman, 영국 할로우, 1999년 5월
^ C. 코르테스와 V.N Vapnik.서포트 벡터네트워크기계학습저널, 20: 273-297,1995
^ V.Vapnik.통계학습이론WILLY, Chichester, GB, 1998
^ N.Fuhr. 확률 순위 원칙에 기초한 최적 다항식 검색 함수.ACM 트랜잭션 온 인포메이션 시스템, 7(3): 183-204
^ N.Fuhr, S. Hartmann, G. Lustig, M. Schwantner, K. Tzeras 및 G. Knorz.Air/x - 큰 주제 필드를 위한 규칙 기반 다단계 인덱싱 시스템입니다.RIAO, 1991년

[1] Joachims, T. (2002), "클릭 스루 데이터를 사용한 검색 엔진 최적화", 지식 발견 및 데이터 마이닝에 관한 ACM 회의 진행

[2] Bing Li; Rong Xiao; Zhiwei Li; Rui-Cai; Bao-Li-Li-Li-Li-Li-Li Zhang; "랭크 SIFT: 반복 가능한 지역 관심점 순위 매기기 학습", 컴퓨터 비전 및 패턴 인식(CVPR), 2011년

[3] M.Kemeny. 순위 상관법, 하프너, 1955

[4] A.Mood, F.회색부리, 그리고 D.Boes. 통계학 입문.맥그로힐, 제3판, 1974년

[5] J. 케메니와 L. 스넬.사회과학의 수학적 모델.진앤코 1962

[6] Y. Yao. 문서의 사용자 선호도에 따라 검색 효과를 측정합니다.미국정보과학회지, 46(2): 133-145, 1995.

[7] R.Baeza- 예이츠와 B.리베이로네토현대 정보 검색.Addison-Wesley-Longman, 영국 할로우, 1999년 5월

[8] C. 코르테스와 V.N Vapnik.서포트 벡터네트워크기계학습저널, 20: 273-297,1995

[9] V.Vapnik.통계학습이론WILLY, Chichester, GB, 1998

[10] N.Fuhr. 확률 순위 원칙에 기초한 최적 다항식 검색 함수.ACM 트랜잭션 온 인포메이션 시스템, 7(3): 183-204

[11] N.Fuhr, S. Hartmann, G. Lustig, M. Schwantner, K. Tzeras 및 G. Knorz.Air/x - 큰 주제 필드를 위한 규칙 기반 다단계 인덱싱 시스템입니다.RIAO, 1991년

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

SVM의 랭킹

네임스페이스

더

목차

묘사

배경

순위 부여 방법

켄달스타우^[3]^[4]

정보 검색^[5]^[6]^[7] 품질

SVM 분류기^[8]

SVM의 랭킹 알고리즘

손실 함수

트레이닝 데이터 수집

기능 공간

최적화 문제

검색 기능

랭크 SVM 적용

레퍼런스

Search

SVM의 랭킹

묘사

배경

순위 부여 방법

켄달스타우[3][4]

정보 검색[5][6][7] 품질

SVM 분류기[8]

SVM의 랭킹 알고리즘

손실 함수

트레이닝 데이터 수집

기능 공간

최적화 문제

검색 기능

랭크 SVM 적용

레퍼런스

켄달스타우^[3]^[4]

정보 검색^[5]^[6]^[7] 품질

SVM 분류기^[8]