Qué algoritmo aplicar para elegir el punto correcto

La siguiente imagen muestra 7 puntos alrededor del origen. Uno de ellos ha sido seleccionado por un humano basado en reglas y experiencia y es de color rojo (el que está en el cuadrante inferior izquierdo).

Ahora tenemos más de 1000 de estos conjuntos de puntos y para cada conjunto, un humano ha seleccionado un solo punto. Estas condiciones se aplican a todos los conjuntos:

• Cada conjunto tiene alrededor de 3 a 10 puntos
• No hay valores atípicos
• Los puntos pueden tener valores positivos y negativos.
• No se cometieron errores al seleccionar un punto

Mi pregunta es: ¿Existe un algoritmo de aprendizaje automático para aprender de estos conjuntos y selecciones hechas por humanos para que pueda decidir automáticamente qué punto seleccionar cuando se da un nuevo conjunto de puntos? Este nuevo conjunto satisface las primeras 3 condiciones desde arriba, por supuesto.

2 observaciones finales:

• El ejemplo que di es solo un ejemplo construido al azar por mí para apoyar la idea sobre puntos en un plano alrededor del origen junto con uno seleccionado. En la vida real puede haber más estructura, pero por ahora tengo curiosidad y me gustaría saber qué es posible para este caso.
• ¿Serían posibles las variaciones? Digamos que se trata de 2 puntos seleccionados o tiene círculos con un radio dado en lugar de puntos.

Este es un problema fascinante! Dos cosas lo hacen especialmente desafiante:

• ¿Cómo debemos comparar dos conjuntos de puntos? Los problemas clásicos en Machine Learning tienen un número fijo de atributos, y estos atributos no son intercambiables: por ejemplo, podría tener datos sobre diferentes personas con atributos agey height(en centímetros). Cada muestra tiene una entrada para cada uno y, por supuesto, (age, height) = (22, 180)no es lo mismo que (age, height) = (180, 22). Tampoco es cierto en su problema. Un conjunto de puntos tiene entre 3 y 10 puntos, y el orden en el que ingresamos los puntos no debería hacer una diferencia al comparar dos conjuntos de puntos.
• ¿Cómo hacemos una predicción? Digamos que hemos encontrado una manera de elegir conjuntos de puntos de nuestro conjunto de entrenamiento que son similares a su conjunto de puntos anterior. Nos enfrentamos al problema de que nuestra predicción debe ser uno de los 7 puntos en su imagen; pero ninguno de estos puntos puede estar contenido en conjuntos de puntos similares.

Permítanme describir un algoritmo que se ocupa de ambos desafíos. La precisión de la predicción no es muy buena; pero tal vez veas una forma de mejorarlo. Y al menos predice algo , ¿verdad?

1. Simulando muestras

Para poder probar el algoritmo, escribí funciones que generan muestras y etiquetas.

Generación de muestras: cada muestra contiene entre 3 y 10 puntos. El número de puntos es aleatorio, extraído de una distribución uniforme. Cada punto es de la forma (x_coordinate, y_coordinate). Las coordenadas son nuevamente aleatorias, extraídas de una distribución normal.

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)])

Generando etiquetas: como ejemplo de juguete, supongamos que la regla para elegir un punto es: Elija siempre el punto más cercano (0, 0), donde 'más cercano' debe entenderse en términos de la norma euclidiana.

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])

Ahora podemos crear nuestros trenes y conjuntos de prueba:

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. Comparación de conjuntos de puntos a través de la distancia de Hausdorff

Abordemos el primer problema: ¿Cómo debemos comparar diferentes conjuntos de puntos? El número de puntos en los conjuntos de puntos es diferente. Recuerde también que el orden en el que escribimos los puntos no debería importar: la comparación con el conjunto de puntos [(0,0), (1,1), (2,2)]debería producir el mismo resultado que la comparación con el conjunto de puntos [(2,2), (0,0), (1,1)]. Mi enfoque es comparar conjuntos de puntos a través de su distancia 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. Prediciendo a través de k-vecinos más cercanos y promediando

Ahora tenemos una noción de distancia entre conjuntos de puntos. Esto hace posible utilizar la clasificación de vecinos k más cercanos: dado un conjunto de puntos de prueba, encontramos los kconjuntos de puntos en nuestra muestra de entrenamiento que tienen la menor distancia de Hausdorff en relación con el conjunto de puntos de prueba, y obtenemos sus etiquetas. Ahora viene el segundo problema: ¿cómo convertimos estas ketiquetas en una predicción para el conjunto de puntos de prueba? Tomé el enfoque más simple: promediar las etiquetas y predecir el punto en el conjunto de puntos de prueba más cercano al promedio.

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. Prueba

Todo está en su lugar para probar el rendimiento de nuestro algoritmo.

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])

Para la función de decisión dada num_neighbors = 70, obtenemos una precisión de predicción del 84%. Esto no es terriblemente bueno y, por supuesto, es específico de nuestra función de decisión, que parece bastante fácil de predecir.

Para ver esto, defina una función de decisión diferente:

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

El uso de esta función dec_fun = decision_function_maxaveragereduce la precisión de predicción al 45%. Esto muestra lo importante que es pensar en las reglas de decisión que generan sus etiquetas. Si tiene una idea de por qué las personas eligen ciertos puntos, esto lo ayudará a encontrar el mejor algoritmo.

Algunas formas de mejorar este algoritmo: (1) Use una función de distancia diferente en lugar de la distancia de Hausdorff, (2) use algo más sofisticado que los vecinos más cercanos k, (3) mejore cómo las etiquetas de entrenamiento seleccionadas se convierten en una predicción.

Aquí hay algunas maneras en que puede usar redes neuronales para resolver este problema:

Con una simple red neuronal Feedforward:

• Escale sus datos para que quepan en el cuadrado alrededor del origen de (-1, -1) a (1,1)
• $k$
• Agregue una tercera entrada de indicador para cada punto, indicando si ese punto está presente
• Elija el número y el tamaño de las capas ocultas.
• Use una capa softmax de tamaño 10 en la salida

$k$$k$

Con una red neuronal convolucional:

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

La CNN podría funcionar mejor ya que sus datos son inherentemente espaciales. Sin embargo, debe decidir qué hacer si se superponen dos o más puntos. La solución más simple es elegir una al azar, lo que podría estar bien dependiendo de su tarea específica.

Con una red neuronal recurrente:

• Introduzca secuencias de longitud variable de puntos escalados (x, y) y genere una estimación softmax de tamaño 10

¡Sí, es tan fácil como eso con los RNN! Manejan bien las entradas de longitud variable, pero aún carecen de las ventajas de las CNN para manejar datos espaciales.

Advertencias:

Si usa un FNN o un RNN, también está la cuestión de cómo ordenar sus datos de entrada. Si no hay un orden inherente en sus datos reales, entonces no queremos que nuestra red haga predicciones diferentes para los mismos datos codificados en diferentes órdenes. Una forma de manejar esto es con el aumento de datos : duplica cada ejemplo de entrenamiento varias veces con diferentes órdenes de entrada, de modo que con suerte tu red pueda aprender las simetrías apropiadas.

Si solo tiene tiempo para probar un enfoque, elegiría la CNN. Las CNN están diseñadas para funcionar bien con datos espaciales, y no hay ningún problema con los pedidos de entrada.