RankBoost

Valeurs d'entrée

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

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

Initialisation

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

Déroulement

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

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

${\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: ${\displaystyle \alpha _{t}\in \mathbf {R} }$, avec ${\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

${\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 ${\displaystyle Z_{t}}$ un facteur de normalisation

Résultat

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

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

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