-2

I've read a lot about neural networks working against a specific output value but I haven't seen unsupervised networks optimize against a less specific goal (e.g. minimize the cost, but we don't know what the ideal value looks like).

Let's discuss a specific example:

Given the Travelling salesman problem with a slight twist:

  • Although the cost of traveling between cities is fixed, it can no longer be included as part of the input. The cost may be read on-demand from an external sub-system and is only available in the cost function at the end of each epoch.
  • We have no training data (we don't know what the ideal solution looks like).

Can someone please provide a high-level design that would solve this problem? I am looking for something similar to https://stackoverflow.com/a/42516959/14731.

I am worried about trying to minimize a cost function relative to a target cost of zero, because the gradient of descent will be much higher than it would be if the the ideal solution was known.

Gili
  • 86,244
  • 97
  • 390
  • 689
  • Asking people on stack to do your homework/work is not what the site is intended for. You must at least try to solve the problem, and ask a question if you are truly stuck. I found an online book, maybe it can help? http://neuralnetworksanddeeplearning.com/chap1.html – RoboYak Oct 27 '17 at 19:32
  • 1
    @ElijahTate I've been working in the field for over 15 years, so this is hardly homework/work. I have a background in Genetic Algorithms but am having a hard time grasping how to design neural networks. I've read tutorials but they don't seem to focus on supervised training, or unsupervised training that only do classification. The problem I am asking about does neither of these two things. – Gili Oct 27 '17 at 19:33
  • 1
    I would suggest reformatting your question to be more specific to the areas that are being difficult. Otherwise your question contains no specific question, with no "true" answer, and even if someone attempted it the solution would be opinion based. Currently this is a very open ended ask. – RoboYak Oct 27 '17 at 19:38
  • @ElijahTate I've revised the question. Does this help? – Gili Oct 27 '17 at 19:54
  • 2
    This is not homework, but worse, it is research. Stack Overflow is not the right place for research and open-ended questions. More appropriate would be Cross Validated or the Data Science SE. – Dr. Snoopy Oct 28 '17 at 12:01
  • @user3666197 My intuition tells me that using the wrong gradient is equivalent to using training data with incorrect outputs. This will prevent the neural network from converging to the desired value(s). – Gili Dec 04 '17 at 05:37
  • @Gili Did not get your point about **{ aGradientVALUE, aTrainingEXAMPLE[N], aGndTruthVALUE[N] }** -- neither a "**higher**"-[0], nor "**mismatch**"-between[1:2] make any sense to me ( if not speaking about some deteriorated code, that principally ignores rules to work as a proper ANN training factory ). Even the deferred penalty / reward processing is doable. It seems that you face issues with the ( slightly twisted initial ) problem formulation, not with the tools how to forward-feed a state, ascertain a reward and backpropagate deltas themselves. – user3666197 Dec 04 '17 at 13:13

2 Answers2

1

From the words you use and the reference you provide, you seem to be thinking about deep learning and backpropagation, but I would suggest considering neuroevolution instead.

In a nutshell, neuroevolution creates a pool of candidate solutions in successive iterations. It only requires that you can sort your candidates by how promising or successful they are. In your travelling salesman problem, we know less time is better, so that would allow to sort our candidates easily. Then a new generation of candidates is created, taking the old one as parents, where parents higher in your list will have greater chances to produce offspring.

NEAT is a common algorithm for this, and has versions for many languages.

For even more deceiving problems, novelty search is a good idea to have in mind.

Just to be clear: neuroevolution does not use backpropagation, but it does use neural networks. It is a different approach to find a neural network that works for a given task.

Pablo
  • 1,373
  • 16
  • 36
  • I love the idea behind Novelty Search, but it brings to mind the question: what are Genetic Algorithms and Neural Networks contributing to this learning process? Meaning, what is the GA contributing to solving this problem that the NN does not, and vice-versa? – Gili Oct 30 '17 at 12:47
  • There seems to be a misunderstanding with names here. A neural network is just a way to translate inputs into outputs. Neuroevolution or backpropagation are the tools to find the right NN. So the neural network solves the problem, and the algorithm (backpropagation, neuroevolution) gives you a way to find a specific NN that will work. Does that make sense to you? – Pablo Oct 30 '17 at 13:08
  • Yes, makes sense. Why do we need the neural-network though? Genetic Algorithms have historically optimized other representations before NNs came along. What do we gain by optimizing a NN instead of some other representation? – Gili Oct 31 '17 at 16:05
  • We don't "need" a neural network, they are simply efficient for many problems. They are interesting because they can represent arbitrary functions and because we can sometimes take some inspiration from biology, but they are definitely not "superior" per se. And they come with drawbacks, like their being hard to interpret (except for the most basic, they are "black boxes"). – Pablo Oct 31 '17 at 20:12
-1

Great question, Gili.

Well, ANN have received in recent years an indeed unreasonably massive "popularity". Today, if some new product / process / startup-pitch does not claim to have an AI or at least a Neural network behind it, it sort of smells in the flow of popular media. The reality is other.

Classical ANN is nothing more than just a minimiser driven tool, it has zero true intelligence per-se, it just follows linear algebra rules on a grain of tanh() / sigmoid() dose of "steroids", for an add-on non-linearity transformation.

You ask a thing, that is self-Evolution --- that's incredibly interesting

adaptive reflection of the external ( deferred ex-post rewards ) requires a way to perform the self-actualisation of the networked weights. This is something the Genetically Inspired Systems ( Koza et al ) have promoted for many decades in Evolutionary Computing Systems.

Yet, there were recognised some mild attempts to promote some sort of trivial self-actualisation inside an ANN recently, having added an intended ( better "pre-wired", c/f Genetically Inspired System speculative polymorphic plurality of trials with ex-post phase of selection, driven by a "pre-defined" Bestness of Fit ) process of re-arranging not only it's own axon-weights, but also it's own topologies -- re-wireing neural connectivity ( sure, on a way lower level / way more weakly utility-(un)-related self-actualisation -- ref. also, on a much higher level of abstraction, the Maslow promoted Hierarchy of Needs ).

After many decades in this domain, I dare say, the ANN tools ( be them beautified with a label of "deep" ( increasing "expressivity" of possible internal states ( once computable within some reasonable [PTIME,PSPACE]-constrained system ), not any principally new emergent property of the idea ) or "convolutional" ( kernelised transforms knowingly blur details so as to permit better numerical ( not gnostic ) "generalisation" ) are just algebraically tied to a role of a sort of a well equipped finite-state automaton tailored for finding the least wrong answer, given a tandem of [ penalty-function, so-far-visited-part-of-empiric-experience ] -- that was pre-adjusted ( tuned ) over the previously known amount of so far collected { example: answer } pairs of observed pieces of empiric experience.

ANN's answers can tell a least wrong WHAT ( for which it rigidly expects, by a dumb "extrapolation of algebraically hardwired belief", that the rules of The Game did not change, to get the least hurting ( pre-fixed from previous collection of empirics ) penalty, based on previous [ penalty-function, so-far-visited-part-of-empirics ], but never WHY and will thus always ( un-knowingly, which is not an excuse, but an explicitly accepted fact it is not capable of anything else in this direction ) "mystify" you with "answers" delivered ( at doing it's algebraically-fixed best ) in cases either of these changes or shifts into another mode ( ref. Lyapunov coefficients for (hyper)-chaotic systems, that all complex systems by nature are ... ):

  • penalty-function modification ( the minimiser's rules are changing The Game! )
  • observed experience ( be it by seeing a growing series of "just" drifting or a completely new "breed" of { example: answer } pair(s) )

So yes, you can re-articulate a Vision & generate Evolutionary ANNs,

but for doing this, you are on the very edge, where IMHO no tooling exists, so you go into a very deep snow being the first.

Very interesting, because you define new rules, but also very demanding and challenging many opponents.

Implication - you would hardly be able to use any "hard-wired"-ANN toolkits, so indeed a virgin snow & great challenge in front of you, man.

My personal opinion based guesstimate is, that you can get better progress if trying to augment high-performance Evolutionary Computing Tools with some sort of pre-fabricated abstract-[NeuralNetwork]-component Factory, and if your contemporary Research Project budget and [PTIME,PSPACE]-computing fabrics' performance envelopes permit -- may enjoy the powers of evolutionary driven growth of adaptation-capabilities, that let survive a reasonably wide diversity of the few bests among the bests in endlessly grown population of acquired "Know-how To Remain Best ( Alive ) ".

Great challenge, indeed.

( Even in spite of the fact you will cheat from the Mother of Nature -- ( we haven't found any better Master for learning and taking lessons from, did we? ) )

user3666197
  • 1
  • 6
  • 50
  • 92
  • I am so confused :) Is there another machine-learning approach that is more appropriate to these kinds of problems than neural nets? – Gili Oct 28 '17 at 18:29
  • Alike one rather uses more than a one particular letter to better express ones thoughts ( w/o using binary-coded streams or a Morse Code ) the ensemble of individual tools is better, than any single one of them. Using a bit further mind-provoking step of adding some vertical hierarchy, an ensemble of swarms of some simpler tools has a chance ( not warranty ) to evolve into a better predictor. The whole depends on diversity of populations included into the process and time needed to let the simulated evolutionary processes go ( +add [EXPTIME,EXPSPACE]-needed for tuning hyperparameters thereof ) – user3666197 Oct 28 '17 at 19:08