RankBoost

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 leurs associant un rang de classification.

L'algorithme reprend les grandes lignes d'AdaBoost mais remplace les exemples par des couples (exemples 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 positif et $n n$ le nombre de négatif

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 choisie 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

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

Portail de l’informatique

Catégorie :
Algorithme de classification

Contenu soumis à la licence CC-BY-SA. Source : Article RankBoost de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Boosting — Le boosting est un domaine de l apprentissage automatique (branche de l intelligence artificielle). C est un principe qui regroupe de nombreux algorithmes qui s appuient sur des ensembles de classifieurs binaires : le boosting optimise leurs … Wikipédia en Français
Обучение ранжированию — (англ. learning to rank или machine learned ranking, MLR)[1] это класс задач машинного обучения с учителем, заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных… … Википедия

Dictionnaires et Encyclopédies sur 'Academic'

RankBoost

Algorithme

Liens

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

RankBoost

Algorithme

Liens

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link