[PYTHON] J'ai essayé de bien le comprendre en implémentant l'algorithme Adaboost en machine learning (+ j'ai approfondi ma compréhension du calcul de tableaux)
introduction
Voici un résumé du boosting d'origine tel que XGBoost, qui est souvent utilisé dans Kaggle. J'aimerais comprendre Adaboost tout en l'implémentant parmi les algorithmes de boosting. J'ai utilisé cet article de @amber_kshz et je l'ai implémenté.
Implémentation de PRML Chapter 14 Bagging et Ada Boost en Python https://qiita.com/amber_kshz/items/8869d8ef7f9743b16d8d
** En particulier, j'ai pu apprendre à calculer efficacement et rapidement à l'aide d'un tableau. ** Je voudrais résumer comment faire cela.
Les principaux points sont les suivants.
- Comprendre Boosting
- Comprendre l'algorithme d'Adaboost
- Approfondissez votre compréhension en mettant en œuvre Adaboost
- Comprendre le moignon de décision
- Essayez-le + Évaluez la différence due au nombre d'essais
Comprendre Boosting
La méthode de combinaison d'apprenants appelés apprenants faibles est appelée ** apprentissage d'ensemble **. L'apprentissage d'ensemble typique peut être divisé en quatre.
- Ensachage (distinguer les données de formation avec plusieurs apprenants faibles et la moyenne (échantillonnage ** avec duplication **))
- Stimulation (distinguer les données de formation avec plusieurs apprenants faibles et la moyenne (échantillonnage ** pas de duplication **))
- Empilement (moyenne de la charge compte tenu de l'importance des apprenants faibles)
- ** (Cette fois) Boosting (améliorer la précision des apprenants faibles pour devenir des apprenants forts) **
Dans l'apprentissage d'ensemble, l'algorithme qui forme en permanence l'apprenant faible et le modifie pour améliorer la précision est appelé ** boosting **. Nous visons à rendre l'apprenant plus précis en prêtant attention au mauvais échantillon (= mal classé) et en effectuant l'apprentissage suivant.
La figure ci-dessous montre le flux. $ M $ est le nombre d'essais, et le nombre d'essais augmente du coin supérieur gauche au coin inférieur droit. Je voudrais classer les cercles bleus et rouges, mais les échantillons mal classés sont en grande partie ** encerclés **. Vous pouvez voir que la ligne de classification verte se déplace pour séparer en quelque sorte l'échantillon mal classé.
Un apprenant similaire est ** Bagging **. Pour l'ensachage, les résultats de l'apprentissage autonome sont moyennés. Bien que chacun de ces apprenants soit indépendant, la différence est que dans le cas de la stimulation, les résultats appris plus tôt sont utilisés dans l'apprentissage ultérieur.
Comprendre l'algorithme d'Adaboost
Maintenant, comprenons l'algorithme d'Adaboost. Adaboost est une abréviation de Adaptive Boosting. Il s'agit d'un algorithme annoncé en 1997. Adaboost applique l'idée d'utiliser le nouveau prédicteur pour apporter des corrections qui accordent une attention particulière aux parties qui ont été mal évaluées par le prédicteur précédent.
A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting https://www.sciencedirect.com/science/article/pii/S002200009791504X
L'algorithme spécifique est le suivant.
** Supposition **
- $ N \ in \ mathbb {N} $: nombre d'exemples de données
- $ X = (x_0, x_1, \ dots, x_ {N-1}) $: exemples de points de données. Disons $ x_n \ in \ mathbb {R} ^ D $.
algorithme
- Entrée: Les données d'apprentissage sont $ (X, T) $, le classificateur de base est $ y $ et le nombre de classificateurs est $ M $.
- Initialisez le poids des données d'entraînement $ (w_0, w_1, \ dots, w_ {N-1}) $ à $ w ^ {(0)} _ {n} = 1 / N $.
- Répétez ce qui suit pour $ m = 0,1, .... M-1 $.
(a) Alignez le classificateur $ y_m (x) $ avec les données de test pour minimiser la fonction d'erreur $ J_m $ représentée ci-dessous.
$ \begin{align} J_m = \sum_{n=0}^{N-1} w^{(m)}\_{n} I \left[ y(x_n, \theta_m) \neq t_n \right] \end{align} $
⇒ À ce moment, $ I \ left [y (x_n, \ theta_m) \ neq t_n \ right] $ est ** 0 (= bonne réponse) si les données de test et la valeur prédite correspondent, et 1 si elles sont erronées. Je vais. Par conséquent, si le nombre de réponses correctes est grand, $ J_m $ sera petit ** (= il joue le rôle d'une fonction d'erreur et est OK).
(b) Calculez $ \ epsilon_m et \ alpha_m $ à partir de l'erreur du classificateur de base. $ \ Epsilon_m $ représente le taux d'erreur, et $ \ alpha_m $ est le coefficient à refléter dans le paramètre de pondération.
(c) Utilisez le $ \ alpha_m $ trouvé à l'étape précédente pour définir le poids $ w $
⇒ À ce stade, si la valeur prédite et les données de test correspondent, $ I $ indique $ 0 $. Au contraire, si c'est faux, ce sera $ 1 $, donc la pondération sera mise à jour avec le $ \ alpha $ précédent.
Approfondissez votre compréhension en mettant en œuvre Adaboost
Ensuite, je voudrais passer à la mise en œuvre.
Comprendre le moignon de décision
Cette fois, l'apprenant faible utilise la tension déterminée. Un stock décisif est de sélectionner l'une des variables d'entrée de ** certaines données, de définir un seuil en fonction de la valeur et de la classer. ** En bref, je comprends que c'est un arbre de décision de profondeur 1. Maintenant, le programme ci-dessous définit la classe de stock déterminée.
adaboost.ipynb
def fit_onedim(self, X, y, sample_weight, axis):
N = len(X)
# Here we sort everything according the axis-th coordinate of X
sort_ind = np.argsort(X[:, axis])
sorted_label = y[sort_ind]
sorted_input = X[sort_ind]
sorted_sample_weight = sample_weight[sort_ind]
pred = -2*np.tri(N-1, N, k=0, dtype='int') + 1
mistakes = (pred != sorted_label ).astype('int')
# The (weighted) error is calculated for each classifier
errs = np.zeros((2, N-1))
errs[0] = mistakes @ sorted_sample_weight
errs[1] = (1 - mistakes) @ sorted_sample_weight
# Here, we select the best threshold and sign
ind = np.unravel_index(np.argmin(errs, axis=None), errs.shape)
sign = -2*ind[0] + 1
threshold = ( sorted_input[ind[1], axis] + sorted_input[ind[1] + 1, axis] ) / 2
err = errs[ind]
return sign, threshold, err
En savoir plus sur les calculs
Cette fois, comme indiqué ci-dessous, nous utilisons le jeu de données makemoons. Prenons le cas où le nombre d'exemples de données est de 100 $, comme indiqué dans l'image ci-dessous, et il y a des données à 50 $ avec une étiquette $ 1 $ et des données à 50 $ avec une étiquette $ -1 $.
Cet ensemble de données est stocké dans $ X = (x_1, x_2) $. Pour plus de commodité, utilisez le np.argsort suivant pour définir l'index avant de le réorganiser par ordre croissant.
Ensuite, exécutez la méthode «np.tri» (génération de matrice triangulaire supérieure et inférieure) comme matrice «pred» qui donne une valeur prédite provisoire.
Définissez ensuite ce pred-y comme une matrice erreur. En conséquence, 99 ensembles de tables d'exactitude ont été créés.
Enfin, multipliez ce tableau d'exactitude et ce poids pour trouver la fonction de perte.
La ligne de frontière est la valeur moyenne de $ x_1 ^ m, x_1 ^ {m + 1} $, qui est la limite lorsque la valeur minimale de cette fonction de perte est prise. Dans le cas d'Adaboost, il existe également un processus pour mettre à jour le poids de l'étiquette incorrecte ici.
(Supplément) Déterminez s'ils correspondent
Voici quelques-unes des choses que je pensais être un bon moyen de le faire. Le fait que la valeur prédite soit correcte ou non est déterminé par la valeur de vérité (type booléen). Dans le contenu de la fonction d'erreur plus tôt, c'était $ 0 $ s'il était touché, et $ 1 $ s'il ne l'était pas, donc je vais le travailler comme ça.
sample.ipynb
a = np.array([[1,1,1,1],[1,1,1,1],[1,1,0,1]])
b = np.array([1,1,1,0])
c1 = (a != b )
c2 = (a != b ).astype('int')
print(c1)
print(c2)
[[False False False True]
[False False False True]
[False False True True]]
[[0 0 0 1]
[0 0 0 1]
[0 0 1 1]]
Voici un exemple simple. Soit $ a $ la valeur prédite et $ b $ l'étiquette correcte à déterminer. Vous pouvez voir que le programme renvoie $ 0 $ pour False cette fois, et $ 1 $ pour True s'il est désactivé.
Déplacer réellement + évaluer la différence due au nombre d'essais
Déplaçons-le réellement. Essayez de passer de 1 $ à 9 $ en tant que nombre d'essais.
adaboost.ipynb
num_clf_list = [1, 2, 3, 4, 5, 6,7,8,9]
clfs = [AdaBoost(DecisionStump, num_clfs=M) for M in num_clf_list]
fig, axes = plt.subplots(3, 3, figsize=(15,15))
for i in range(len(clfs)):
clfs[i].fit(X, y)
plot_result(ax=np.ravel(axes)[i], clf=clfs[i], xx=xx, yy=yy, X=X, y=y)
np.ravel(axes)[i].set_title(f'M = {num_clf_list[i]}')
Vous pouvez voir que les lignes à classer sont progressivement séparées et qu'il est susceptible de devenir un classificateur précis. Dans le cas d'un stock déterminé, comme vous pouvez le voir à partir de la définition, il est difficile de classer avec une courbe non linéaire car il essaie de classer avec une ligne droite.
À la fin
Cette fois, j'ai approfondi ma compréhension d'Adaboost avec sa mise en œuvre. Bien que l'algorithme lui-même soit facile à comprendre, quand il s'agit de l'implémenter, j'ai constaté que je ne pouvais pas continuer sans une bonne compréhension des calculs matriciels tels que «numpy». À partir de là, j'aimerais améliorer mes compétences analytiques en comprenant les algorithmes souvent utilisés dans Kaggle tels que XG boost.
Le programme complet est ici. https://github.com/Fumio-eisan/adaboost_20200427