RankBoost

Le RankBoost est une méthode de boosting très similaire à AdaBoost. Le but de cette méthode d'apprentissage est de classer un ensemble de données les unes par rapport aux autres, en leur associant un rang de classification.

L'algorithme reprend les grandes lignes d'AdaBoost mais remplace les exemples par des couples (exemple positif contre exemple négatif). La sélection cherche à maximiser le score des exemples positifs par rapport à celui des exemples négatifs.

Valeurs d'entrée

---

Soit un ensemble d'apprentissage annoté: ( x 1 , y 1 ) , … , ( x m , y m ) {\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})} où x i ∈ X , {\displaystyle x_{i}\in X,} sont les exemples et y i ∈ Y = { − 1 , + 1 } {\displaystyle \,y_{i}\in Y=\{-1,+1\}} les annotations.

On notera i p {\displaystyle i_{p}} l'indice des exemples positifs et i n {\displaystyle i_{n}} ceux des exemples négatifs.

Initialisation

---

On initialise la distribution des exemples par D 1 ( i p , i n ) = 1 n p ∗ n n , i = 1 , … , m . {\displaystyle D_{1}(i_{p},i_{n})={\frac {1}{n_{p}*n_{n}}},i=1,\ldots ,m.} avec n p {\displaystyle n_{p}} le nombre de positifs et n n {\displaystyle n_{n}} le nombre de négatifs.

Déroulement

---

Pour t = 1 , … , T {\displaystyle t=1,\ldots ,T} :

• Trouver le classifieur h t {\displaystyle h_{t}} qui maximise le score de classification en fonction de la difficulté des exemples: D t {\displaystyle D_{t}} :

r t = arg ⁡ max h t ∈ H ∑ i p , i n m D t ( x i p , x i n ) [ h t ( x i p ) − h t ( x i n ) ] {\displaystyle r_{t}=\arg \max _{h_{t}\in {\mathcal {H}}}\sum _{i_{p},i_{n}}^{m}D_{t}(x_{i_{p}},x_{i_{n}})[h_{t}(x_{i_{p}})-h_{t}(x_{i_{n}})]}

• On choisit alors le poids du classifieur: α t ∈ R {\displaystyle \alpha _{t}\in \mathbf {R} } , avec α t = 1 2 ln 1 + r t 1 − r t {\displaystyle \alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1+r_{t}}{1-r_{t}}}}
• On met ensuite à jour la pondération des couples d'exemples d'apprentissage

D t + 1 ( x i p , x i n ) = D t ( x i p , x i n ) e − α t ( h t ( x i n ) − h t ( x i p ) ) Z t {\displaystyle D_{t+1}(x_{i_{p}},x_{i_{n}})={\frac {D_{t}(x_{i_{p}},x_{i_{n}})\,e^{-\alpha _{t}(h_{t}(x_{i_{n}})-h_{t}(x_{i_{p}}))}}{Z_{t}}}}
avec Z t {\displaystyle Z_{t}} un facteur de normalisation

Résultat

---

Le classifieur résultant du processus de sélection est:

H ( x ) = ∑ t = 1 T α t h t ( x ) {\displaystyle H(x)=\sum _{t=1}^{T}\alpha _{t}h_{t}(x)}

• [1] An Efficient Boosting Algorithm for Combining Preferences, article de référence sur le RankBoost écrit par Yoav Freund et Robert Schapire

• Portail de l’informatique