Qual algoritmo aplicar para escolher o ponto certo

A figura abaixo mostra 7 pontos em torno da origem. Um deles foi selecionado por um humano com base em regras e experiência e é colorido de vermelho (aquele no quadrante inferior esquerdo).

Agora, temos mais de 1000 desses conjuntos de pontos e, para cada conjunto, um humano selecionou um único ponto. Essas condições se aplicam a todos os conjuntos:

• Cada conjunto tem cerca de 3 a 10 pontos
• Não há outliers
• Os pontos podem ter valores positivos e negativos
• Nenhum erro foi cometido ao selecionar um ponto

Minha pergunta é: Existe um algoritmo de aprendizado de máquina para aprender com esses conjuntos e seleções feitas por seres humanos, para que ele possa decidir automaticamente qual ponto selecionar quando um novo conjunto de pontos for fornecido? Este novo conjunto satisfaz as 3 primeiras condições de cima, é claro.

2 considerações finais:

• O exemplo que dei é apenas um exemplo construído aleatoriamente para apoiar a ideia de pontos em um plano em torno da origem, juntamente com um selecionado. Na vida real, pode haver mais estrutura, mas por enquanto estou curioso e gostaria de saber o que é possível para este caso.
• Seriam possíveis variações? Digamos que sejam cerca de 2 pontos selecionados ou você tenha círculos com um raio especificado em vez de pontos.

Este é um problema fascinante! Duas coisas tornam isso especialmente desafiador:

• Como devemos comparar dois conjuntos de pontos? Problemas clássicos no Machine Learning têm um número fixo de atributos e esses atributos não são intercambiáveis: por exemplo, eu posso ter dados sobre pessoas diferentes com atributos agee height(em centímetros). Cada amostra tem uma entrada para cada uma e, (age, height) = (22, 180)é claro, não é a mesma coisa que (age, height) = (180, 22). Nem é verdade no seu problema. Um conjunto de pontos tem entre 3 e 10 pontos, e a ordem em que inserimos os pontos não deve fazer diferença ao comparar dois conjuntos de pontos.
• Como fazemos uma previsão? Digamos que encontramos uma maneira de escolher conjuntos de pontos em nosso conjunto de treinamento que são semelhantes ao seu conjunto de pontos acima. Enfrentamos o problema de que nossa previsão deve ser um dos 7 pontos em sua foto; mas nenhum desses pontos pode estar contido nos conjuntos de pontos semelhantes.

Deixe-me descrever um algoritmo que lida com os dois desafios. A precisão da previsão não é muito boa; mas talvez você veja uma maneira de melhorar isso. E pelo menos prevê algo , certo?

1. Simulando amostras

Para poder testar o algoritmo, escrevi funções que geram amostras e rótulos.

Gerando amostras: Cada amostra contém entre 3 e 10 pontos. O número de pontos é aleatório, obtido de uma distribuição uniforme. Cada ponto é da forma (x_coordinate, y_coordinate). As coordenadas são novamente aleatórias, extraídas de uma distribuição 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)])

Gerando rótulos: Como exemplo de brinquedo, vamos assumir que a regra para escolher um ponto é: sempre escolha o ponto mais próximo (0, 0), onde 'mais próximo' deve ser entendido em termos da 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])

Agora podemos criar nossos conjuntos de trem e teste:

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. Comparação de conjuntos de pontos via distância de Hausdorff

Vamos abordar o primeiro problema: como devemos comparar diferentes conjuntos de pontos? O número de pontos nos conjuntos de pontos é diferente. Lembre-se também de que a ordem na qual anotamos os pontos não deve importar: a comparação com o conjunto de pontos [(0,0), (1,1), (2,2)]deve produzir o mesmo resultado que a comparação com o conjunto de pontos [(2,2), (0,0), (1,1)]. Minha abordagem é comparar conjuntos de pontos pela distância 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. Previsão através de k-vizinhos mais próximos e média

Agora temos uma noção de distância entre conjuntos de pontos. Isso torna possível usar a classificação de vizinhos k-mais próximos: dado um conjunto de pontos de teste, encontramos kna nossa amostra de treinamento os conjuntos de pontos que têm a menor distância de Hausdorff em relação ao conjunto de pontos de teste e obtemos seus rótulos. Agora vem o segundo problema: como transformamos esses krótulos em uma previsão para o conjunto de pontos de teste? Adotei a abordagem mais simples: calcule a média dos rótulos e preveja o ponto no conjunto de pontos de teste mais próximo da média.

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

Está tudo pronto para testar o desempenho do nosso 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 a função de decisão fornecida e num_neighbors = 70, obtemos uma precisão de previsão de 84%. Isso não é muito bom e, é claro, é específico da nossa função de decisão, que parece bastante fácil de prever.

Para ver isso, defina uma função de decisão diferente:

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

O uso desta função via dec_fun = decision_function_maxaveragereduz a precisão da previsão para 45%. Isso mostra o quão importante é pensar nas regras de decisão que geram seus rótulos. Se você tem uma idéia de por que as pessoas escolhem determinados pontos, isso o ajudará a encontrar o melhor algoritmo.

Algumas maneiras de melhorar esse algoritmo: (1) Use uma função de distância diferente em vez da distância de Hausdorff, (2) use algo mais sofisticado do que os vizinhos mais próximos, (3) melhore como as etiquetas de treinamento selecionadas são transformadas em previsão.

Aqui estão algumas maneiras pelas quais você pode usar redes neurais para resolver esse problema:

Com uma rede neural simples de feedforward:

• Dimensione seus dados para caber no quadrado ao redor da origem de (-1, -1) a (1,1)
• Represente cada ponto com duas entradas correspondentes às suas coordenadas x e y, ou 0,0 se a $k$
• Adicione uma terceira entrada de indicador para cada ponto, indicando se esse ponto está presente
• Escolha o número e o tamanho das camadas ocultas
• Use uma camada softmax de tamanho 10 na saída

$k$$k$ pontos presentes no conjunto, e a saída for um vetor de comprimento 10, somando 1, seja o o maior valor corresponde ao ponto previsto (cuja posição corresponde à posição na entrada).

Com uma rede neural convolucional:

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

A CNN pode ter um desempenho melhor, já que seus dados são inerentemente espaciais. No entanto, você deve decidir o que fazer se dois ou mais pontos se sobreporem. A solução mais simples é escolher uma aleatoriamente, o que pode ser bom dependendo da sua tarefa específica.

Com uma rede neural recorrente:

• Alimente sequências de comprimento variável de pontos escalados (x, y) e produza uma estimativa de softmax de tamanho 10

Sim, é tão fácil quanto isso com as RNNs! Eles lidam bem com entradas de comprimento variável, mas ainda não possuem as vantagens das CNNs para lidar com dados espaciais.

Ressalvas:

Se estiver usando um FNN ou um RNN, também há a questão de como você solicita seus dados de entrada. Se não houver ordem inerente nos seus dados reais, não queremos que nossa rede faça previsões diferentes para os mesmos dados codificados em ordens diferentes. Uma maneira de lidar com isso é com o aumento de dados : duplique cada exemplo de treinamento algumas vezes com diferentes pedidos de entrada, para que sua rede possa aprender as simetrias apropriadas.

Se você tiver apenas tempo para tentar uma abordagem, eu escolheria a CNN. As CNNs são projetadas para funcionar bem com dados espaciais e não há problema com os pedidos de entrada.