L'algorithme de Ho–Kashyap est une procédure itérative en apprentissage automatique pour entraîner des classificateurs linéaires. Développé par Yu-Chi Ho et Rangasami L. Kashyap en 1965, il appartient à la famille des méthodes d'apprentissage basées sur la discrimination qui trouvent un hyperplan pour séparer les classes dans un espace de caractéristiques. Contrairement aux règles antérieures de type perceptron qui ajustent uniquement le vecteur de poids, l'algorithme de Ho–Kashyap ajuste également un vecteur de marge, ce qui lui permet de converger même lorsque les données d'entraînement ne sont pas strictement linéairement séparables, à condition qu'une solution existe au sens relâché.
L'algorithme minimise une fonction de critère d'erreur quadratique. Étant donné un ensemble d'échantillons d'entraînement, chacun représenté par un vecteur de caractéristiques, l'objectif est de trouver un vecteur de poids et un vecteur de marge tels que le produit de la matrice de caractéristiques et du vecteur de poids soit égal à un vecteur de marge positif. La procédure alterne entre la mise à jour du vecteur de marge à l'aide d'une étape de descente de gradient et la mise à jour du vecteur de poids via une solution des moindres carrés. Cette double mise à jour donne à l'algorithme une mise à jour des poids sous forme fermée à chaque itération, ce qui le rend efficace sur le plan computationnel et garantit une diminution monotone du critère.
Formulation Mathématique
Soit les données d'entraînement composées de \(n\) échantillons, chacun avec \(d\) caractéristiques, organisés dans une matrice \(n \times d\) \(X\). Chaque échantillon est étiqueté comme appartenant à l'une des deux classes, et les étiquettes sont encodées comme +1 ou -1. L'algorithme cherche un vecteur de poids \(w\) et un vecteur de marge \(b\) (avec toutes les composantes positives) tels que \(Xw = b\). Le critère à minimiser est \(J(w, b) = \|Xw - b\|^2\).
Les règles de mise à jour sont :
- \(b_{k+1} = b_k + \rho (Xw_k - b_k)\), où \(\rho\) est un taux d'apprentissage, et les composantes négatives de \(b\) sont mises à zéro pour maintenir la positivité.
- \(w_{k+1} = (X^T X)^{-1} X^T b_{k+1}\), qui est la solution des moindres carrés pour le vecteur de marge actuel.
Ce processus en deux étapes est répété jusqu'à ce que le critère tombe en dessous d'un seuil ou qu'un nombre maximal d'itérations soit atteint. L'algorithme est garanti de converger vers une solution si les données sont linéairement séparables ; sinon, il peut osciller, et une pratique courante consiste à ajouter une petite constante positive au vecteur de marge pour forcer la convergence dans les cas non séparables.
Contexte Historique
L'algorithme a été introduit au milieu des années 1960, une période de développement rapide dans la reconnaissance de formes et les réseaux de neurones. Yu-Chi Ho et Rangasami L. Kashyap ont publié leur travail dans l'IEEE Transactions on Electronic Computers en 1965. À l'époque, les classificateurs linéaires étaient un outil principal pour des tâches comme la reconnaissance de caractères et la classification de signaux. L'algorithme de Ho–Kashyap offrait une amélioration par rapport à la règle d'apprentissage du perceptron, qui pouvait échouer à converger si les données n'étaient pas parfaitement séparables. En introduisant le vecteur de marge, l'algorithme fournissait une approche plus robuste capable de gérer des données bruitées ou chevauchantes.
La méthode est étroitement liée à l'algorithme des moindres carrés moyens (LMS) et à la règle de Widrow-Hoff, développés à la même période par Bernard Widrow et ses collègues. Cependant, l'algorithme de Ho–Kashyap modélise explicitement la marge, ce qui en fait un précurseur des machines à vecteurs de support (SVM) modernes qui mettent également l'accent sur les marges pour une meilleure généralisation.
Applications et Extensions
Dans sa forme originale, l'algorithme de Ho–Kashyap a été appliqué à des problèmes de reconnaissance de formes, comme la classification de chiffres manuscrits et la détection de signaux dans le bruit. Au fil des décennies, il a été étendu de plusieurs manières :
- Extensions non linéaires : En mappant les entrées à travers une fonction noyau, l'algorithme peut être appliqué à des données non linéairement séparables, similaire aux SVM avec noyau.
- Régularisation : L'ajout d'un terme de pénalité au critère, tel que \(\lambda \|w\|^2\), améliore la généralisation et gère les matrices mal conditionnées.
- Problèmes multiclasses : La formulation binaire peut être étendue à plusieurs classes en utilisant des stratégies un-contre-tous ou un-contre-un.
- Apprentissage en ligne : Des variantes ont été développées pour les données en flux où les échantillons arrivent séquentiellement.
Ces extensions ont maintenu la pertinence de l'algorithme dans les programmes modernes de machine learning, souvent enseigné comme un exemple d'optimisation itérative dans l'analyse discriminante linéaire.
Relation avec d'Autres Méthodes
L'algorithme de Ho–Kashyap partage des similitudes conceptuelles avec plusieurs autres techniques d'apprentissage. L'algorithme du perceptron, introduit par Frank Rosenblatt en 1958, trouve également un hyperplan séparateur mais ne garantit pas la convergence pour des données non séparables. L'utilisation d'une mise à jour des moindres carrés dans l'algorithme de Ho–Kashyap est analogue à l'optimiseur Adam en ce sens que les deux impliquent des ajustements adaptatifs, bien qu'Adam soit conçu pour l'apprentissage profond avec des gradients stochastiques. En revanche, l'algorithme de Ho–Kashyap est déterministe et basé sur des lots.
Une autre méthode connexe est la méthode de relaxation, qui ajuste également les marges mais utilise des règles de mise à jour différentes. L'algorithme de Ho–Kashyap est souvent comparé au classificateur des moindres carrés, qui minimise l'erreur quadratique sans imposer de marges positives ; la contrainte de marge est ce qui donne à l'algorithme de Ho–Kashyap ses propriétés de convergence.
Considérations Pratiques
Lors de l'implémentation de l'algorithme de Ho–Kashyap, plusieurs problèmes pratiques surgissent. Le calcul de \((X^T X)^{-1}\) peut être coûteux pour un grand \(d\), et la matrice peut être singulière si les caractéristiques sont redondantes. Dans de tels cas, des techniques de pseudo-inverse ou de régularisation sont utilisées. Le taux d'apprentissage \(\rho\) doit être choisi avec soin ; une valeur trop grande peut provoquer des oscillations, tandis qu'une valeur trop petite ralentit la convergence. Un choix courant est \(\rho = 1\), qui fonctionne souvent bien en pratique.
L'algorithme est sensible à l'échelle des caractéristiques. La standardisation des caractéristiques pour avoir une moyenne nulle et une variance unitaire est recommandée pour éviter la domination par des caractéristiques de grande magnitude. Pour les données de haute dimension, comme dans la classification de textes, l'algorithme peut surajuster, et la régularisation devient essentielle.
Malgré son âge, l'algorithme de Ho–Kashyap reste un outil pédagogique précieux. Il illustre l'interaction entre l'optimisation et l'apprentissage, et sa preuve de convergence est un résultat classique dans la théorie de la reconnaissance de formes. Les manuels modernes sur le machine learning l'incluent souvent comme un pont entre les perceptrons simples et les classificateurs basés sur la marge plus avancés.