Quel algorithme appliquer pour choisir le bon point

L'image ci-dessous montre 7 points autour de l'origine. L'un d'eux a été sélectionné par un humain sur la base des règles et de l'expérience et est coloré en rouge (celui dans le quadrant inférieur gauche).

Nous avons maintenant plus de 1000 de ces ensembles de points et pour chaque ensemble, un humain a sélectionné un seul point. Ces conditions s'appliquent à tous les ensembles:

• Chaque ensemble a environ 3 à 10 points
• Il n'y a pas de valeurs aberrantes
• Les points peuvent avoir des valeurs positives et négatives
• Aucune erreur n'a été commise lors de la sélection d'un point

Ma question est: existe-t-il un algorithme d'apprentissage automatique pour apprendre de ces ensembles et des sélections faites par l'homme afin qu'il puisse automatiquement décider quel point sélectionner lorsqu'un nouvel ensemble de points est donné? Ce nouvel ensemble remplit bien sûr les 3 premières conditions d'en haut.

2 dernières remarques:

• L'exemple que j'ai donné n'est qu'un exemple construit de manière aléatoire par moi pour soutenir l'idée de points dans un plan autour de l'origine avec un point sélectionné. Dans la vraie vie, il pourrait y avoir plus de structure mais pour l'instant je suis curieux et je voudrais savoir ce qui est possible pour ce cas.
• Des variations seraient-elles possibles? Disons qu'il s'agit d'environ 2 points sélectionnés ou que vous avez des cercles avec un rayon donné au lieu de points.

C'est un problème fascinant! Deux choses le rendent particulièrement difficile:

• Comment comparer deux ensembles de points? Les problèmes classiques de Machine Learning ont un nombre fixe d'attributs, et ces attributs ne sont pas interchangeables: Par exemple, je pourrais avoir des données sur différentes personnes avec des attributs ageet height(en centimètres). Chaque échantillon a une entrée pour chacun, et (age, height) = (22, 180)n'est bien sûr pas le même que (age, height) = (180, 22). Ni l'un ni l'autre n'est vrai dans votre problème. Un ensemble de points a entre 3 et 10 points, et l'ordre dans lequel nous entrons les points ne devrait pas faire de différence lors de la comparaison de deux ensembles de points.
• Comment faire une prédiction? Imaginons que nous ayons trouvé un moyen de sélectionner des ensembles de points dans notre ensemble d'entraînement qui sont similaires à votre ensemble de points ci-dessus. Nous sommes confrontés au problème que notre prédiction doit être l'un des 7 points de votre image; mais aucun de ces points ne peut être contenu dans les ensembles de points similaires.

Permettez-moi de décrire un algorithme qui traite des deux défis. La précision de prédiction n'est pas très bonne; mais peut-être voyez-vous un moyen de l’améliorer. Et au moins, il prédit quelque chose , non?

1. Simulation d'échantillons

Pour pouvoir tester l'algorithme, j'ai écrit des fonctions qui génèrent des échantillons et des labels.

Génération d'échantillons: Chaque échantillon contient entre 3 et 10 points. Le nombre de points est aléatoire, tiré d'une distribution uniforme. Chaque point est de la forme (x_coordinate, y_coordinate). Les coordonnées sont à nouveau aléatoires, tirées d'une distribution normale.

import numpy as np
from random import randint

def create_samples(number_samples, min_points, max_points):

    def create_single_sample(min_points, max_points):
        n = randint(min_points, max_points)
        return np.array([np.random.normal(size=2) for _ in range(n)]) 

    return np.array([create_single_sample(min_points, max_points) for _ in range(number_samples)])

Génération d'étiquettes: À titre d'exemple de jouet, supposons que la règle pour choisir un point est: Choisissez toujours le point le plus proche (0, 0), où «le plus proche» doit être compris en termes de norme euclidienne.

def decision_function_minnorm(sample):
    norms = np.apply_along_axis(np.linalg.norm, axis=1, arr=sample)
    return sample[norms.argmin()]

def create_labels(samples, decision_function):
    return np.array([decision_function(sample) for sample in samples])

Nous pouvons maintenant créer nos trains et ensembles de test:

n_train, n_test = 1000, 100
dec_fun = decision_function_minnorm

X_train = create_samples(number_samples=n_train, min_points=3, max_points=10)
X_test = create_samples(number_samples=n_test, min_points=3, max_points=10)
y_train = create_labels(X_train, dec_fun)
y_test = create_labels(X_test, dec_fun)

2. Comparaison des ensembles de points via la distance de Hausdorff

Abordons le premier problème: comment comparer différents ensembles de points? Le nombre de points dans les jeux de points est différent. N'oubliez pas non plus que l'ordre dans lequel nous notons les points n'a pas d'importance: la comparaison avec l'ensemble de points [(0,0), (1,1), (2,2)]devrait donner le même résultat que la comparaison avec l'ensemble de points [(2,2), (0,0), (1,1)]. Mon approche consiste à comparer des ensembles de points via leur distance de Hausdorff :

def hausdorff(A, B):

    def dist_point_to_set(x, A):
        return min(np.linalg.norm(x - a) for a in A)

    def dist_set_to_set(A, B):
        return max(dist_point_set(a, B) for a in A)

    return max(dist_set_to_set(A, B), dist_set_to_set(B, A))

3. Prédire via k voisins les plus proches et faire la moyenne

Nous avons maintenant une notion de distance entre les ensembles de points. Cela permet d'utiliser la classification k-voisins les plus proches: étant donné un ensemble de points de test, nous trouvons les kensembles de points dans notre échantillon d'apprentissage qui ont la plus petite distance de Hausdorff par rapport à l'ensemble de points de test, et obtenons leurs étiquettes. Vient maintenant le deuxième problème: comment transformer ces kétiquettes en prédiction pour l'ensemble de points de test? J'ai adopté l'approche la plus simple: faire la moyenne des étiquettes et prédire le point de l'ensemble de points de test le plus proche de la moyenne.

def predict(x, num_neighbors):
    # Find num_neighbors closest points in X_train.
    distances_to_train = np.array([hausdorff(x, x_train) for x_train in X_train])
    neighbors_idx = np.argpartition(distances_to_train, -num_neighbors)[-num_neighbors:]

    # Get labels of the neighbors and calculate the average.
    targets_neighbors = y_train[neighbors_idx]
    targets_mean = sum(targets_neighbors) / num_neighbors

    # Find point in x that is closest to targets_mean and use it as prediction.
    distances_to_mean = np.array([np.linalg.norm(p - targets_mean) for p in x])
    closest_point = x[distances_to_mean.argmin()]

    return closest_point

4. Test

Tout est en place pour tester les performances de notre algorithme.

num_neighbors = 70
successes = 0
for i, x in enumerate(X_test):
    print('%d/%d' % (i+1, n_test))
    prediction = predict(x, num_neighbors)
    successes += np.array_equal(prediction, y_test[i])

Pour la fonction de décision donnée et num_neighbors = 70, nous obtenons une précision de prédiction de 84%. Ce n'est pas terriblement bon, et c'est bien sûr spécifique à notre fonction de décision, qui semble assez facile à prévoir.

Pour voir cela, définissez une fonction de décision différente:

decision_function_maxaverage(sample):
    avgs = (sample[:, 0] + sample[:, 1]) / 2
    return sample[norms.argmin()]

L'utilisation de cette fonction via dec_fun = decision_function_maxaverageréduit la précision de la prédiction à 45%. Cela montre à quel point il est important de réfléchir aux règles de décision qui génèrent vos étiquettes. Si vous avez une idée pourquoi les gens choisissent certains points, cela vous aidera à trouver le meilleur algorithme.

Quelques façons d'améliorer cet algorithme: (1) Utiliser une fonction de distance différente au lieu de la distance de Hausdorff, (2) utiliser quelque chose de plus sophistiqué que les voisins les plus proches, (3) améliorer la façon dont les étiquettes d'apprentissage sélectionnées sont transformées en prédiction.

Voici quelques façons d'utiliser les réseaux de neurones pour résoudre ce problème:

Avec un simple réseau de neurones Feedforward:

• Mettez à l'échelle vos données pour qu'elles tiennent dans le carré autour de l'origine de (-1, -1) à (1,1)
• $k$
• Ajoutez une troisième entrée d'indicateur pour chaque point, indiquant si ce point est présent
• Choisissez le nombre et la taille des couches cachées
• Utilisez une couche softmax de taille 10 en sortie

$k$$k$

Avec un réseau neuronal convolutif:

• $n$$n$$n$$n$$k$$k$$i,j$$0$$1$$0$
• $n*n$

Le CNN peut être plus performant car vos données sont intrinsèquement spatiales. Cependant, vous devez décider quoi faire si deux points ou plus se chevauchent. La solution la plus simple consiste à en choisir un au hasard, ce qui pourrait être OK en fonction de votre tâche spécifique.

Avec un réseau neuronal récurrent:

• Alimenter en séquences de longueur variable de points (x, y) mis à l'échelle et produire une estimation softmax de taille 10

Oui, c'est aussi simple que cela avec les RNN! Ils gèrent bien les entrées de longueur variable, mais ils n'ont toujours pas les avantages des CNN pour gérer les données spatiales.

Mises en garde:

Si vous utilisez un FNN ou un RNN, il y a aussi la question de savoir comment vous commandez vos données d'entrée. S'il n'y a pas d'ordre inhérent dans vos données réelles, nous ne voulons pas que notre réseau fasse des prédictions différentes pour les mêmes données encodées dans des ordres différents. Une façon de gérer cela consiste à augmenter les données : dupliquez plusieurs fois chaque exemple de formation avec différents ordres d'entrée, afin que votre réseau puisse apprendre les symétries appropriées.

Si vous n'avez que le temps d'essayer une approche, je choisirais le CNN. Les CNN sont conçus pour bien fonctionner avec les données spatiales, et il n'y a aucun problème avec les ordres d'entrée.