KNN a-t-il une fonction de perte?

Je n'ai pas trouvé de définition de la fonction de perte sur wiki dans le contexte de l'apprentissage automatique.

celui-ci est cependant moins formel, il est assez clair.

À la base, une fonction de perte est incroyablement simple: c'est une méthode pour évaluer la façon dont votre algorithme modélise votre ensemble de données. Si vos prévisions sont totalement fausses, votre fonction de perte affichera un nombre plus élevé. S'ils sont assez bons, ils afficheront un nombre inférieur. Au fur et à mesure que vous modifiez des morceaux de votre algorithme pour essayer d'améliorer votre modèle, votre fonction de perte vous dira si vous allez quelque part.

il semble que le taux d'erreur de KNN ne soit pas la fonction qui pourrait guider l'optimisation du modèle lui-même, comme Gradient Descent.

alors, KNN a-t-il une fonction de perte?

machine-learning fu DL
la source

Réponses:

$k$ -NN n'a pas de fonction de perte qui peut être minimisée pendant l'entraînement. En fait, cet algorithme n'est pas du tout entraîné. La seule «formation» qui a lieu pour -NN est la mémorisation des données (création d'une copie locale), de sorte que lors de la prédiction, vous puissiez effectuer une recherche et voter à la majorité. Techniquement, aucune fonction n'est ajustée aux données, et donc, aucune optimisation n'est effectuée (elle ne peut pas être entraînée en utilisant la descente de gradient). $k$

Tim
la source

kNN n'utilise pas de fonction de perte pendant la "formation", mais cela ne signifie pas qu'il n'y a pas de fonction de perte qui définit kNN. Par exemple: Il est bien connu que la médiane minimise la perte de différence absolue moyenne. Mais vous ne calculez jamais la perte abs moyenne, et vous n'utilisez pas d'optimisation comme la descente de gradient pour calculer la médiane non plus. C'est toujours un fait utile qui minimise parfois la perte moyenne des abdos. De la même manière, vous pourriez probablement construire une fonction de perte que kNN minimise toujours

nikie

@nikie c'est vrai, mais dans kNN les utilise juste comme des fonctions d'agrégation locales parmi les voisins (difficile à traduire en perte globale pour minimiser). De plus, pour k = 1, vous n'utilisez pas une telle fonction. De plus, il n'est pas utilisé pour la formation. L'appeler une fonction de perte n'est qu'un exercice mental pour forcer kNN à correspondre à une définition de classificateur, je ne trouve pas de raisons impérieuses de le définir de cette façon.

Tim

@nikie - J'ai ajouté la fonction de perte dans une nouvelle réponse. Tim - l'avantage de l'écrire de cette façon est qu'il est plus facile de voir comment on peut rendre l'objectif plus "doux" en passant d'un noyau haut de forme (en comptant le nombre de points - le kNN habituel) à un noyau gaussien (pondération des points par proximité).

Miles

@Miles c'est vrai, mais ce n'est pas utile de toute façon à part la discussion théorique, académique. En termes pratiques, l'algorithme n'est pas formé à l'aide de la fonction de perte et il ne serait pas pratique de le faire. Je dirais que parler de la fonction de perte pour kNN est plus déroutant que utile dans la plupart des cas.

Tim

Je pensais que la question semblait de nature théorique, mais vous avez raison de dire qu'il n'y a aucune utilité pratique pour connaître la perte. Peut-être que OP recherchait quelque chose comme l'analyse des composantes du quartier? Je l'ai lié dans la réponse.

Miles

Chaque algorithme de statistiques minimise explicitement ou implicitement certains objectifs, même s'il n'y a pas de paramètres ou d'hyperparamètres, et même si la minimisation n'est pas effectuée de manière itérative. Le kNN est si simple que l'on ne le pense généralement pas comme ça, mais vous pouvez réellement écrire une fonction objective explicite:

\hat{t} = {argmax}_{C} \sum_{i : x_{i} \in N_{k} ({x}, \hat{x})} δ (t_{i}, C)

$\hat{t} = \text{argmax}_\mathcal{C} \sum_{i: x_i \in N_k(\{x\}, \hat{x})} \delta(t_i, \mathcal{C})$

Ce que cela signifie, c'est que la classe prédite pour un point est égale à la classe qui maximise le nombre d'autres points qui sont dans l'ensemble des points voisins qui ont également la même classe, mesurée par qui est lorsque est dans la classe , sinon. $\hat{t}$ $\hat{x}$ $\mathcal{C}$ $x_i$ $k$ $N_k(\{x\}, \hat{x})$ $\delta(t_i, \mathcal{C})$ $1$ $x_i$ $\mathcal{C}$ $0$

L'avantage de l'écrire de cette façon est que l'on peut voir comment rendre l'objectif «plus mou» en pondérant les points par la proximité. En ce qui concerne la "formation", il n'y a pas de paramètres ici pour s'adapter. Mais on pourrait régler la métrique de distance (qui est utilisée pour définir ) ou la pondération des points dans cette somme pour optimiser un objectif de classification supplémentaire. Cela mène à l'analyse des composants du quartier: https://www.cs.toronto.edu/~hinton/absps/nca.pdf qui apprend une métrique de distance. $N_k$

Miles
la source

-3

Je suis en désaccord avec la réponse acceptée (quelque peu).

KNN est un algorithme de classification , et cela n'a aucun sens d'exécuter un algorithme de classification sans fonction de perte: vous seriez intéressé par la qualité de l'algorithme. Dans le cas de KNN, vous pouvez, par exemple, évaluer la qualité des classifications en examinant la somme des précisions moyennes dans chaque classe. Ou, vous pouvez vous concentrer uniquement sur la précision de l'algorithme.

La méthode d'optimisation qui alimente KNN ne dépend pas de la fonction de perte, donc pendant l'entraînement, elle ne fait jamais appel à la fonction de perte et n'utilise même pas la descente de gradient pour s'entraîner.

Cela contraste avec les éléments suivants « classificateur voisin K-plus proche »: pour classes, premier train -un moyen, puis définir la classe de chaque point par le nombre de points dominant appartenant à chaque barycentre. Vous pouvez par exemple entraîner cet algorithme avec une minimisation pas à pas sur l'erreur du moindre carré de chaque centroïde (recalculer les centroïdes en fonction des voisins les plus proches), mais au moment du test, votre fonction de perte serait à nouveau une certaine forme de précision sur chaque classe, malgré l'algorithme d'origine n'ayant aucune dépendance à ce sujet. $K$ $K$

Alex R.
la source

Une métrique pour évaluer les performances de l'algorithme et la perte à minimiser sont deux choses différentes. En fait, vous pouvez minimiser les pertes qui diffèrent de la métrique que vous recherchez (par exemple pour des raisons de calcul).

Tim

@Tim: Je pense que nous sommes sur la même page car c'est exactement le point que j'essaie de faire valoir dans le dernier paragraphe, où une métrique est utilisée pour s'entraîner. Mais, vous souhaitez toujours une fonction de perte après la formation pour évaluer l'algorithme. Un algorithme de classification formé sans faire appel à une sorte de fonction de perte (pendant ou après) sur les classes n'est par définition pas supervisé.

Alex R.