Który algorytm zastosować do wyboru właściwego punktu

Zdjęcie poniżej pokazuje 7 punktów wokół początku. Jeden z nich został wybrany przez człowieka na podstawie zasad i doświadczenia i ma kolor czerwony (ten w lewym dolnym kwadrancie).

Teraz mamy ponad 1000 takich zestawów punktów i dla każdego zestawu człowiek wybrał jeden punkt. Warunki te dotyczą wszystkich zestawów:

• Każdy zestaw ma około 3 - 10 punktów
• Nie ma wartości odstających
• Punkty mogą mieć wartości dodatnie i ujemne
• Przy wyborze punktu nie popełniono żadnych błędów

Moje pytanie brzmi: czy istnieje algorytm uczenia maszynowego do uczenia się na podstawie tych zestawów i wyborów dokonanych przez człowieka, aby mógł automatycznie decydować, który punkt wybrać, gdy zostanie podany nowy zestaw punktów? Ten nowy zestaw oczywiście spełnia pierwsze 3 warunki z góry.

2 uwagi końcowe:

• Podany przeze mnie przykład jest tylko przypadkowo skonstruowanym przeze mnie przykładem, który wspiera ideę punktów w płaszczyźnie wokół początku wraz z wybranym. W prawdziwym życiu może być więcej struktur, ale na razie jestem ciekawy i chciałbym wiedzieć, co jest możliwe w tej sprawie.
• Czy możliwe byłyby zmiany? Powiedzmy, że jest to około 2 wybranych punktów lub masz koła o danym promieniu zamiast punktów.

To fascynujący problem! Dwie rzeczy sprawiają, że jest to szczególnie trudne:

• Jak powinniśmy porównać dwa zestawy punktów? Klasyczne problemy w uczeniu maszynowym mają ustaloną liczbę atrybutów, a atrybutów tych nie można zamieniać: na przykład mogę mieć dane o różnych osobach z atrybutami agei height(w centymetrach). Każda próbka ma jeden wpis dla każdej i oczywiście (age, height) = (22, 180)nie jest taka sama jak (age, height) = (180, 22). Żaden problem nie dotyczy prawdy. Zestaw punktów ma od 3 do 10 punktów, a kolejność, w jakiej wprowadzamy punkty, nie powinna mieć znaczenia przy porównywaniu dwóch zestawów punktów.
• Jak robimy prognozy? Powiedzmy, że znaleźliśmy sposób wybierania zestawów punktów z naszego zestawu treningowego, które są podobne do zestawu punktów powyżej. Stajemy przed problemem, że nasza prognoza musi być jednym z 7 punktów na twoim zdjęciu; ale żaden z tych punktów nie może być zawarty w podobnych zestawach punktów.

Pozwól, że nakreślę algorytm, który zajmuje się obydwoma wyzwaniami. Dokładność prognoz nie jest bardzo dobra; ale może widzisz sposób, w jaki można to poprawić. I przynajmniej coś przewiduje , prawda?

1. Symulowanie próbek

Aby móc przetestować algorytm, napisałem funkcje generujące próbki i etykiety.

Generowanie próbek: Każda próbka zawiera od 3 do 10 punktów. Liczba punktów jest losowa i pochodzi z jednolitego rozkładu. Każdy punkt ma formę (x_coordinate, y_coordinate). Współrzędne są ponownie losowe, pochodzą z rozkładu normalnego.

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

Generowanie etykiet: Jako zabawkowy przykład przyjmijmy, że reguła wyboru punktu jest następująca: zawsze wybieraj punkt najbliższy (0, 0), gdzie „najbliższy” należy rozumieć w kategoriach normy euklidesowej.

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

Możemy teraz tworzyć nasze zestawy pociągów i testów:

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. Porównywanie zestawów punktów za pomocą odległości Hausdorffa

Zajmijmy się pierwszym problemem: jak powinniśmy porównywać różne zestawy punktów? Liczba punktów w zestawach punktów jest inna. Pamiętaj również, że kolejność, w jakiej zapisujemy punkty, nie powinna mieć znaczenia: porównanie z zestawem punktów [(0,0), (1,1), (2,2)]powinno dać taki sam wynik, jak porównanie z zestawem punktów [(2,2), (0,0), (1,1)]. Moje podejście polega na porównaniu zestawów punktów na podstawie odległości Hausdorffa :

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. Prognozowanie przez najbliższych sąsiadów i uśrednianie

Mamy teraz pojęcie odległości między zestawami punktów. Umożliwia to zastosowanie k-najbliższej klasyfikacji sąsiadów: Biorąc pod uwagę zestaw punktów testowych, znajdujemy kzestawy punktów w naszej próbce treningowej, które mają najmniejszą odległość Hausdorffa względem zestawu punktów testowych, i uzyskujemy ich etykiety. Teraz pojawia się drugi problem: w jaki sposób przekształcamy te ketykiety w prognozy dla zestawu punktów testowych? Przyjąłem najprostsze podejście: uśrednij etykiety i przewiduj punkt w zestawie punktów testowych, który jest najbliższy średniej.

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

Wszystko jest gotowe do przetestowania wydajności naszego algorytmu.

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

Dla danej funkcji decyzyjnej num_neighbors = 70uzyskujemy dokładność prognozy 84%. Nie jest to zbyt dobre i oczywiście jest specyficzne dla naszej funkcji decyzyjnej, która wydaje się dość łatwa do przewidzenia.

Aby to zobaczyć, zdefiniuj inną funkcję decyzyjną:

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

Korzystanie z tej funkcji przez dec_fun = decision_function_maxaverageobniża dokładność prognoz do 45%. To pokazuje, jak ważne jest, aby myśleć o regułach decyzyjnych generujących etykiety. Jeśli masz pomysł, dlaczego ludzie wybierają określone punkty, pomoże to znaleźć najlepszy algorytm.

Niektóre sposoby ulepszenia tego algorytmu: (1) Użyj innej funkcji odległości zamiast odległości Hausdorffa, (2) użyj czegoś bardziej wyrafinowanego niż k-najbliżsi sąsiedzi, (3) popraw sposób, w jaki wybrane etykiety treningowe zamieniają się w prognozy.

Oto kilka sposobów wykorzystania sieci neuronowych do rozwiązania tego problemu:

Za pomocą zwykłej sieci neuronowej Feedforward:

• Skaluj swoje dane, aby zmieściły się w kwadracie wokół początku od (-1, -1) do (1,1)
• Reprezentuj każdy punkt dwoma wejściami odpowiadającymi jego współrzędnym xiy lub 0,0, jeśli $k$punkt nie jest obecny
• Dodaj trzeci wskaźnik wejściowy dla każdego punktu, wskazując, czy ten punkt jest obecny
• Wybierz liczbę i rozmiar ukrytych warstw
• Użyj wyjściowej warstwy softmax o rozmiarze 10

Tak więc każdy przykład wejściowy będzie wektorem o długości 30, gdzie ostatnie 3 * (10-$k$) wartości są zerowe, jeśli istnieją $k$ punkty obecne w zestawie, a wynikiem jest wektor o długości 10 sumujący się do 1, niezależnie od tego, czy największa wartość odpowiada przewidywanemu punktowi (którego pozycja odpowiada tej pozycji na wejściu).

Z konwergentną siecią neuronową:

• Podziel swój samolot na siatkę $n$ x $n$ kwadraty i reprezentuj swój wkład jako $n$ x $n$ czyli macierz $k$ Jeśli tam są $k$ punkty na kwadracie ($i,j$) i $0$Inaczej. Mam nadzieję, że punkty nie będą się nakładać, więc macie macierz$1$s i $0$s.
• Trenuj CNN na swoich matrycach wejściowych. Twój kształt wyjściowy powinien być softmax wielkości$n*n$, co odpowiada spłaszczonemu kształtowi wejściowemu. Wybierz punkt o najwyższej wartości przy odpowiednich współrzędnych wyjściowych.

Sieć CNN może działać lepiej, ponieważ dane są z natury przestrzenne. Musisz jednak zdecydować, co zrobić, jeśli dwa lub więcej punktów się na siebie nakłada. Najprostszym rozwiązaniem jest wybranie jednego losowo, co może być OK, w zależności od konkretnego zadania.

Z nawracającą siecią neuronową:

• Wprowadź sekwencje o zmiennej długości skalowanych (x, y) punktów i wygeneruj estymację softmax wielkości 10

Tak, to takie proste z RNN! Dobrze radzą sobie z wejściami o zmiennej długości, ale wciąż nie mają zalet CNN do obsługi danych przestrzennych.

Ostrzeżenia:

Jeśli używasz FNN lub RNN, istnieje również kwestia sposobu zamawiania danych wejściowych. Jeśli w twoich prawdziwych danych nie ma właściwej kolejności, nie chcemy, aby nasza sieć dokonywała różnych prognoz dla tych samych danych kodowanych w różnych zamówieniach. Jednym ze sposobów na poradzenie sobie z tym jest powiększanie danych : powiel kilka razy każdy przykład szkolenia z różnymi kolejnością wprowadzania danych, więc mam nadzieję, że twoja sieć nauczy się odpowiednich symetrii.

Jeśli masz tylko czas, aby wypróbować jedno podejście, wybrałbym CNN. Sieci CNN zostały zaprojektowane tak, aby dobrze radziły sobie z danymi przestrzennymi i nie ma problemu z kolejnością danych wejściowych.