O aprendizado de máquina pode aprender uma função como encontrar o máximo de uma lista?

Eu tenho uma entrada que é uma lista e a saída é o máximo dos elementos da lista de entrada.

O aprendizado de máquina pode aprender uma função que sempre seleciona o máximo de elementos de entrada presentes na entrada?

Isso pode parecer uma pergunta bastante básica, mas pode me dar uma compreensão do que o aprendizado de máquina pode fazer em geral. Obrigado!

Talvez , mas observe que este é um daqueles casos em que o aprendizado de máquina não é a resposta . Há uma tendência de tentar aprender o aprendizado de máquina em casos em que as soluções baseadas em regras padrão são mais rápidas, mais simples e geralmente a escolha certa: P

Só porque você pode, não significa que você deveria

Edit : Eu originalmente escrevi isso como "Sim, mas note que ...", mas comecei a duvidar de mim mesmo, nunca tendo visto isso. Eu tentei esta tarde e é certamente factível:

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

A saída é 0.74576, por isso está localizando corretamente o máximo de 74,5% do tempo. Não tenho dúvidas de que isso poderia ser melhorado, mas, como digo, esse não é um caso que eu recomendaria para o ML.

EDIT 2 : Na verdade, eu re-executei esta manhã usando o RandomForestClassifier do sklearn e o desempenho foi significativamente melhor:

# 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())

E a pontuação aqui é de 94,4% das amostras com o máximo identificado corretamente, o que é realmente muito bom.

Sim. Muito importante, você decide a arquitetura de uma solução de aprendizado de máquina. Arquiteturas e procedimentos de treinamento não se escrevem; eles devem ser projetados ou modelados e o treinamento segue como um meio de descobrir uma parametrização da arquitetura adequada a um conjunto de pontos de dados.

Você pode construir uma arquitetura muito simples que realmente inclua uma função máxima:

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

onde um e b são aprendidas parâmetros.

Dadas amostras de treinamento suficientes e uma rotina de treinamento razoável, essa arquitetura muito simples aprenderá muito rapidamente a definir a como 1 eb para zero para sua tarefa.

O aprendizado de máquina geralmente assume a forma de entreter várias hipóteses sobre caracterização e transformação de pontos de dados de entrada e aprender a preservar apenas as hipóteses correlacionadas com a variável de destino. As hipóteses são codificadas explicitamente na arquitetura e subfunções disponíveis em um algoritmo parametrizado ou como as suposições codificadas em um algoritmo "sem parâmetros".

Por exemplo, a escolha de usar produtos pontuais e não linearidades, como é comum na rede neural de baunilha ML, é um tanto arbitrária; ele expressa a hipótese abrangente de que uma função pode ser construída usando uma estrutura de rede composicional predeterminada de transformações lineares e funções de limite. Diferentes parametrizações dessa rede incorporam diferentes hipóteses sobre quais transformações lineares usar. Qualquer caixa de ferramentas pode ser usada e o trabalho de um aprendiz de máquina é descobrir através de diferenciação ou tentativa e erro ou algum outro sinal repetível que funções ou recursos em sua matriz minimizem melhor uma métrica de erro. No exemplo dado acima, a rede aprendida simplesmente se reduz à função máxima em si, enquanto uma rede indiferenciada poderia "aprender" uma função mínima. Essas funções podem ser expressas ou aproximadas por outros meios, como na função de regressão da rede linear ou neural em outra resposta. Em suma, depende realmente de quais funções ou peças LEGO você possui em sua caixa de ferramentas de arquitetura ML.

Sim - o aprendizado de máquina pode aprender a encontrar o máximo em uma lista de números.

Aqui está um exemplo simples de aprender a encontrar o índice do máximo:

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

Algoritmos de aprendizagem

Em vez de aprender uma função como um cálculo feito por uma rede neural de feed-forward, existe todo um domínio de pesquisa sobre algoritmos de aprendizagem a partir de dados de amostra. Por exemplo, pode-se usar algo como uma máquina de Tural Neural ou algum outro método em que a execução de um algoritmo é controlada pelo aprendizado de máquina em seus pontos de decisão. Algoritmos de brinquedo, como encontrar um máximo, classificar uma lista, reverter uma lista ou filtrar uma lista, são comumente usados ​​como exemplos na pesquisa de aprendizado de algoritmos.

Excluirei designs educados da minha resposta. Não, não é possível usar um fora da abordagem de aprendizagem máquina de caixa (ML) para totalmente representar a função máxima para arbitrárias listas com precisão arbitrária. O ML é um método baseado em dados e é claro que você não poderá aproximar uma função em regiões onde não possui nenhum ponto de dados. Portanto, o espaço de possíveis observações (que é infinito) não pode ser coberto por observações finitas.

Minhas declarações têm uma base teórica com o Teorema Universal de Aproximação de Cybeko para redes neurais. Vou citar o teorema da Wikipedia:

$\mathbb{R}^n$

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

Se o seu espaço de observações for compacto, você poderá aproximar a função máxima com um conjunto de dados finitos. Como a resposta mais votada deixou claro, você não deve reinventar a roda!

Aqui está uma expansão no meu comentário. Para prefácio, absolutamente @DanScally está certo que não há razão para usar o ML para encontrar o máximo de uma lista. Mas acho que o seu "pode ​​me dar uma compreensão do que o aprendizado de máquina pode fazer em geral" é razão suficiente para se aprofundar nisso.

$\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$
$i$$i$

Finalmente, para a pergunta subsequente: podemos treinar um NN para esse estado. A @DanScally nos iniciou; talvez conhecer a arquitetura teórica possa nos ajudar a trapacear na solução? (Observe que, se pudermos aprender / aproximar o conjunto específico de pesos acima, a rede terá um desempenho realmente fora do intervalo das amostras de treinamento.)

Caderno no github / Colab

$[-1,1]$obtém a pontuação do teste em 0,961, com uma pontuação fora da faixa de 0,758. Mas, estou pontuando com o mesmo método que o @DanScally, o que parece um pouco desonesto: a função de identidade terá uma pontuação perfeita nessa métrica. Também imprimi alguns coeficientes para ver se algo próximo ao ajuste exato descrito acima aparece (não realmente); e algumas saídas brutas, que sugerem que o modelo é muito tímido na previsão de um máximo, errando ao prever que nenhuma das entradas é a máxima. Talvez modificar o objetivo possa ajudar, mas neste ponto já dediquei muito tempo; se alguém quiser melhorar a abordagem, sinta-se à vontade para jogar (em Colab, se quiser) e me avise.

Sim, mesmo que o aprendizado de máquina simples como os mínimos quadrados lineares comuns possa fazer isso se você usar alguma inteligência aplicada.

(Mas a maioria consideraria esse exagero bastante horrível).

(Assumirei que queremos encontrar o máximo de abs do vetor de entrada):

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. Basta calcular o produto escalar com vetor de índice e redondo.