title: RankBoost
text: # 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.
  
  ## Algorithme
  
  Valeurs d'entrée
  
  Soit un ensemble d'apprentissage annoté: $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ où $x_{i}\in X,$sont les exemples et $\,y_{i}\in Y=\{-1,+1\}$ les annotations.
  
  On notera $i_{p}$ l'indice des exemples positifs et $i_{n}$ ceux des exemples négatifs.
  
  Initialisation
  
  On initialise la distribution des exemples par $D_{1}(i_{p},i_{n})={\frac {1}{n_{p}*n_{n}}},i=1,\ldots ,m.$ avec $n_{p}$ le nombre de positifs et $n_{n}$ le nombre de négatifs.
  
  Déroulement
  
  Pour $t=1,\ldots ,T$:
  
  * Trouver le classifieur $h_{t}$ qui maximise le score de classification en fonction de la difficulté des exemples: $D_{t}$:
  
  $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: $\alpha _{t}\in \mathbf {R}$, avec $\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}})={\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}$ un facteur de normalisation
  
  Résultat
  
  Le classifieur résultant du processus de sélection est:
  
  $H(x)=\sum _{t=1}^{T}\alpha _{t}h_{t}(x)$
  
  ## Liens
  
  * An Efficient Boosting Algorithm for Combining Preferences, article de référence sur le RankBoost écrit par Yoav Freund et Robert Schapire
  