Czy uczenie maszynowe może nauczyć się funkcji wyszukiwania maksimum z listy?

Mam dane wejściowe, które są listą, a dane wyjściowe to maksimum elementów listy wejściowej.

Czy uczenie maszynowe może nauczyć się takiej funkcji, która zawsze wybiera maksimum elementów wejściowych obecnych na wejściu?

To może wydawać się dość podstawowym pytaniem, ale może dać mi zrozumienie tego, co uczenie maszynowe może zrobić w ogóle. Dzięki!

Być może , ale zauważ, że jest to jeden z tych przypadków, w których uczenie maszynowe nie jest odpowiedzią . Istnieje tendencja do próbowania uczenia maszynowego w przypadkach, w których naprawdę standardowe rozwiązania oparte na regułach są szybsze, prostsze i po prostu właściwy wybór: P

To, że możesz, nie oznacza, że ​​powinieneś

Edycja : Pierwotnie napisałem to jako „Tak, ale zauważcie, że ...”, ale potem zacząłem wątpić w siebie, ponieważ nigdy tego nie widziałem. Wypróbowałem to dziś po południu i na pewno jest to wykonalne:

import numpy as np
from keras.models import Model
from keras.layers import Input, Dense, Dropout
from keras.utils import to_categorical
from sklearn.model_selection import train_test_split
from keras.callbacks import EarlyStopping

# Create an input array of 50,000 samples of 20 random numbers each
x = np.random.randint(0, 100, size=(50000, 20))

# And a one-hot encoded target denoting the index of the maximum of the inputs
y = to_categorical(np.argmax(x, axis=1), num_classes=20)

# Split into training and testing datasets
x_train, x_test, y_train, y_test = train_test_split(x, y)

# Build a network, probaly needlessly complicated since it needs a lot of dropout to
# perform even reasonably well.

i = Input(shape=(20, ))
a = Dense(1024, activation='relu')(i)
b = Dense(512, activation='relu')(a)
ba = Dropout(0.3)(b)
c = Dense(256, activation='relu')(ba)
d = Dense(128, activation='relu')(c)
o = Dense(20, activation='softmax')(d)

model = Model(inputs=i, outputs=o)

es = EarlyStopping(monitor='val_loss', patience=3)

model.compile(optimizer='adam', loss='categorical_crossentropy')

model.fit(x_train, y_train, epochs=15, batch_size=8, validation_data=[x_test, y_test], callbacks=[es])

print(np.where(np.argmax(model.predict(x_test), axis=1) == np.argmax(y_test, axis=1), 1, 0).mean())

Wyjście wynosi 0,74576, więc poprawnie znajduje maks. 74,5% czasu. Nie mam wątpliwości, że można to poprawić, ale jak mówię, nie jest to przypadek użycia, który poleciłbym ML.

EDYCJA 2 : Dziś rano uruchomiłem ponownie za pomocą RandomForestClassifier sklearn i działało znacznie lepiej:

# instantiation of the arrays is identical

rfc = RandomForestClassifier(n_estimators=1000, verbose=1)
rfc.fit(x_train, y_train)

yhat_proba = rfc.predict_proba(x_test)


# We have some annoying transformations to do because this .predict_proba() call returns the data in a weird format of shape (20, 12500, 2).

for i in range(len(yhat_proba)):
    yhat_proba[i] = yhat_proba[i][:, 1]

pyhat = np.reshape(np.ravel(yhat_proba), (12500,20), order='F')

print(np.where(np.argmax(pyhat, axis=1) == np.argmax(y_test, axis=1), 1, 0).mean())

Wynik tutaj to 94,4% próbek z poprawnie zidentyfikowanym maksimum, co jest naprawdę całkiem dobre.

Tak. Bardzo ważne, TY decydujesz o architekturze rozwiązania do uczenia maszynowego. Architektury i procedury szkoleniowe nie piszą same; muszą być zaprojektowane lub wzorowane, a szkolenie odbywa się w celu odkrycia parametryzacji architektury dopasowanej do zestawu punktów danych.

Możesz zbudować bardzo prostą architekturę, która faktycznie zawiera maksymalną funkcję:

net(x) = a * max(x) + b * min(x)

gdzie a i b są wyuczonymi parametrami.

Biorąc pod uwagę wystarczającą liczbę próbek treningowych i rozsądną rutynę treningową, ta bardzo prosta architektura nauczy się bardzo szybko ustawiać od 1 do b na zero dla twojego zadania.

Uczenie maszynowe często przyjmuje formę przyjmowania wielu hipotez dotyczących featuryzacji i transformacji wejściowych punktów danych oraz uczenia się zachowania tylko tych hipotez, które są skorelowane ze zmienną docelową. Hipotezy są zakodowane jawnie w architekturze i podfunkcjach dostępnych w sparametryzowanym algorytmie lub jako założenia zakodowane w algorytmie „bez parametrów”.

Na przykład wybór produktów kropkowych i nieliniowości, jak to jest powszechne w waniliowej sieci neuronowej ML, jest nieco arbitralny; wyraża on obejmującą hipotezę, że funkcję można skonstruować przy użyciu z góry określonej struktury sieci kompozycyjnej transformacji liniowych i funkcji progowych. Różne parametryzacje tej sieci ucieleśniają różne hipotezy, które transformacje liniowe zastosować. Można użyć dowolnego przybornika funkcji, a zadaniem uczącego się maszyny jest odkrycie poprzez różnicowanie lub próbę i błąd lub inny powtarzalny sygnał, które funkcje lub cechy w jego tablicy najlepiej minimalizują wskaźnik błędów. W podanym powyżej przykładzie wyuczona sieć po prostu ogranicza się do samej funkcji maksymalnej, podczas gdy niezróżnicowana sieć może alternatywnie „nauczyć się” funkcji minimalnej. Funkcje te mogą być wyrażone lub aproksymowane innymi sposobami, jak w liniowej lub neuronowej funkcji regresji sieci w innej odpowiedzi. Podsumowując, tak naprawdę zależy to od funkcji lub elementów LEGO, które masz w zestawie narzędzi architektury ML.

Tak - uczenie maszynowe może nauczyć się znajdować maksimum na liście liczb.

Oto prosty przykład nauki znajdowania indeksu maksimum:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

# Create training pairs where the input is a list of numbers and the output is the argmax
training_data = np.random.rand(10_000, 5) # Each list is 5 elements; 10K examples
training_targets = np.argmax(input_data, axis=1)

# Train a descision tree with scikit-learn
clf = DecisionTreeClassifier()
clf.fit(input_data, targets)

# Let's see if the trained model can correctly predict the argmax for new data
test_data = np.random.rand(1, 5)
prediction = clf.predict(test_data)
assert prediction == np.argmax(test_data) # The test passes - The model has learned argmax

Algorytmy uczenia się

Zamiast uczyć się funkcji jako obliczenia wykonywanego przez sieć neuronową ze sprzężeniem zwrotnym, istnieje cała dziedzina badawcza dotycząca uczenia algorytmów z przykładowych danych. Na przykład, można użyć czegoś takiego jak Neural Turing Machine lub innej metody, w której wykonywanie algorytmu jest kontrolowane przez uczenie maszynowe w jego punktach decyzyjnych. Algorytmy zabawkowe, takie jak znalezienie maksimum, sortowanie listy, odwracanie listy lub filtrowanie listy, są często używane jako przykłady w badaniach uczenia się algorytmów.

Wykluczę wykształcone projekty z mojej odpowiedzi. Nie, nie jest możliwe zastosowanie niestandardowego uczenia maszynowego (ML) w celu pełnego przedstawienia maksymalnej funkcji dla dowolnych list z dowolną precyzją. ML jest metodą opartą na danych i jasne jest, że nie będzie można przybliżyć funkcji w regionach, w których nie ma żadnych punktów danych. Stąd przestrzeń możliwych obserwacji (która jest nieskończona) nie może być objęta obserwacjami skończonymi.

Moje stwierdzenia mają teoretyczne podstawy z uniwersalnym twierdzeniem aproksymacji Cybeko dla sieci neuronowych. Zacytuję twierdzenie z Wikipedii:

$\mathbb{R}^n$

$\mathbb{R}^n$$x\in \mathbb{R}$

Jeśli twoja przestrzeń obserwacji jest niewielka, możesz być w stanie przybliżyć maksymalną funkcję za pomocą skończonego zestawu danych. Ponieważ w głosowaniu znalazła się odpowiedź najlepiej głosująca, nie należy wymyślać koła na nowo!

Oto rozwinięcie mojego komentarza. Przedmowa absolutnie @DanScally ma rację, że nie ma powodu, aby używać ML do znalezienia maksimum listy. Ale myślę, że twoje „może dać mi zrozumienie tego, co uczenie maszynowe może zrobić ogólnie” jest wystarczającym powodem do zagłębienia się w to.

$\max$$\max$

$\max$$\max$$\max$

$n$ $n$

$\operatorname{argmax}$$n$$\binom{n}{2}$$\delta_{ij} = \mathbf{1}(x_i < x_j)$$i<j$$x_j-x_i$$n$$x_i$$\sum_{j<i} \delta_{ji} + \sum_{j>i} (1-\delta_{ij})$$j$$x_i>x_j$$x_i$ ja ja
W tym momencie, gdybyśmy mogli pomnożyć, dość łatwo uzyskalibyśmy rzeczywistą wartość maksymalną. Rozwiązaniem w artykule jest użycie binarnej reprezentacji liczb, w której mnożenie binarne jest takie samo jak dodawanie progowe. Aby uzyskać argmax, wystarczy prosta funkcja liniowa mnożąca ty wskaźnik przez i sumująca.$i$$i$

Wreszcie, na kolejne pytanie: czy możemy wyszkolić NN do tego stanu. @ DanScally nas rozpoczął; może znajomość teoretycznej architektury może pomóc nam oszukać rozwiązanie? (Należy pamiętać, że jeśli możemy nauczyć się / przybliżać określony zestaw wag powyżej, sieć faktycznie będzie działać dobrze poza zakresem próbek treningowych.)

Notatnik w github / Colab

Zmieniając nieco troszeczkę, otrzymuję lepszy wynik testu (0,838), a nawet testowanie próbki poza oryginalnym zakresem treningowym daje przyzwoity wynik (0,698). Używanie danych wejściowych skalowanych do$[-1,1]$otrzymuje wynik testu do 0,961, z wynikiem poza zakresem wynoszącym 0,758. Ale oceniam za pomocą tej samej metody co @DanScally, co wydaje się trochę nieuczciwe: funkcja tożsamości będzie perfekcyjnie oceniać w tej metodzie. Wydrukowałem także kilka współczynników, aby zobaczyć, czy pojawia się coś zbliżonego do wyżej opisanego dokładnego dopasowania (nie do końca); i kilka nieprzetworzonych wyników, które sugerują, że model jest zbyt nieśmiały, aby przewidzieć maksimum, błędnie po stronie przewidywania, że ​​żadne z danych wejściowych nie jest maksimum. Może zmiana celu mogłaby pomóc, ale w tym momencie poświęciłem już zbyt wiele czasu; jeśli komuś zależy na poprawie podejścia, zagraj (w Colab, jeśli chcesz) i daj mi znać.

Tak, nawet tak proste uczenie maszynowe, jak zwykłe liniowe najmniejsze kwadraty, może to zrobić, jeśli zastosujesz spryt.

(Ale większość uważa, że ​​to dość okropna przesada).

(Zakładam, że chcemy znaleźć maks. Abs wektora wejściowego):

1. $$f(x) = \frac{1}{x^2}$$
2. $f({\bf r})$$\bf C_r$
3. $\bf S$
4. $(\epsilon {\bf I}+10^3{\bf S}^t{\bf S}+{\bf C_r})^{-1}(10^3 {\bf S}^t)$
5. $\bf p$ $$p_i = \frac{p_i^k}{\sum|p_i|^k}$$
6. Wystarczy obliczyć iloczyn skalarny za pomocą wektora indeksowego i okrągłego.