2
$\begingroup$

Problem

Given a collection of pairs (X, y) where X belongs to R^n and y belongs to R, find the X such that the associated y would be maximum.

Example

Given:

  • (X=(1, 2), y=-9)
  • (X=(-2, 4), y=-36)
  • (X=(-4, 2), y=-24)
  • ...

The algorithm should be able to detect that the function being applied to X is y=-(X[0]^2+2*(X[1]^2)) and find the input that maximizes this function, in this case X=(0,0) because y=0^2+2*0^2=0 and 0 is the maximum possible value, as all the other values are negative.

How I've tried to solve it

My first guess has been to create a neural network that predicts y given X, but, after that is done, I don't know how to go about optimizing the input.

Questions

Is there any algorithm that would help in this situation?

Also, would some other supervised learning algorithm fit better here than a neural network?

$\endgroup$
  • 1
    $\begingroup$ Welcome to ai.se...why do you want to optimize inputs? Isn't supposed to be constant? $\endgroup$ – DuttaA Apr 23 '18 at 13:09
  • 1
    $\begingroup$ Because that is essentially the problem I want to solve, to get the input values such as the output is maximum. $\endgroup$ – Mark Apr 23 '18 at 13:54
  • 1
    $\begingroup$ Ok this is recommender system probably...try this coursera.org/learn/machine-learning/lecture/2WoBV/… maybe explore the course $\endgroup$ – DuttaA Apr 23 '18 at 13:57
  • 1
    $\begingroup$ In his recommender system he is using linear regression (he predicts values using a simple matrix multiplication) but, for this problem, the inputs and outputs are not correlated linearly. I've edited the question to express better my problem. $\endgroup$ – Mark Apr 23 '18 at 15:46
  • $\begingroup$ Are you asking for a system that trains neural networks or are you asking for any method that can predict values? $\endgroup$ – Andrew Butler Apr 23 '18 at 16:41
1
$\begingroup$

You can use a neural network for this (sort of), and you've got the first step right - train the network to predict $y$ given $x$ (i.e. train it to approximate the function $f$ such that $y = f(x)$). Because the entire neural network is differentiable (presumably), you can take gradients of the input (some $x$) with respect to the predicted output. Then you can use this to update $x$ the same way that you update the weights during training of the network. This let you find a local optimum from $x$. I don't know of a way to try to find a global optimum with a neural network like this except to find the local optimum near many $x$'s and then take the best of those.

If you want a concrete example, take a look at the tutorial on Neural Style Transfer with PyTorch: here you have a noise image as the input and you optimize it to minimize the "style distance" to a reference style image and the "content distance" to a reference content image (i.e. starting with noise, make it look like the content of one image but in the style of another). There's full code there, but here's a short PyTorch snippet that shows the main idea:

# I'm just optimizing one input; clone so that you don't modify the
# original tensor; let it know that we want gradients computed
inputs = train_inputs[0:1].clone().requires_grad_()
input_optimizer = torch.optim.Adam([inputs])

def optimize_input():
    input_optimizer.zero_grad()
    # where `model` is your trained neural network
    output = model(inp)
    (-output).backward()
    return output

output = []
for _ in range(10000):
    output.append(input_optimizer.step(optimize_input).detach().numpy())

output is a list at the end of what the predicted output was after each step of optimizing the input. You can use this to see if you've converged to a local optimum yet (and take more steps/fewer next time as necessary). inputs will be the optimized input at the end. Note that if there are constraints that your input should satisfy, you'll need to enforce those yourself (e.g. in neural style transfer, they have to enforce that the values are valid for an RGB image).

Note also that how well this works really depends on how well your network approximates $f$; you may well get some unreasonable $x$ for which the network predicts a very large $y$ because there was no training data similar to that $x$ so the network isn't constrained in that region. In general, you should probably be cautious of an $x$ you generate this way that doesn't seem similar to your training data (e.g. has larger/smaller value than any $x$ the network has seen before; interpolation is much easier than extrapolation).

I'm assuming that you have a single data set; if you're able to query for the $y$ values of given $x$'s, then you might want to take a look at Bayesian optimization - essentially the field of trying to find $x$ that maximizes $y = f(x)$ when $f$ is expensive to evaluate and you don't have gradients of it. Bayesian optimization seeks a global optimum.

$\endgroup$
0
$\begingroup$

You really need neural networks to return the maximum value from your data? This algorithm can't help you?

xdata = [
    (1, 2),
    (-2, 4),
    (-4, 2),
]

for test in list_tests:
    y = -(test[0]^2+2 * (test[1]^2))
    if y > 0:
        print("(X(%s, %s), y=%s)" % (test[0], test[1], y))

output:

(X(-2, 4), y=16)
(X(-4, 2), y=2)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.