I need to classify objects with ~50 features into 3-4 different classes, there are no labeled examples. Moreover there is no absolutely correct class for any object. However I do have cost value for every particular classification, but explicit form of the cost function is not known. I need to create classification rules that minimize cost function.

To be more specific, I am trying to teach a robot to survive effectively in an environment. There are many different objects and relations in this environment. At every step robot classifies the environment as safe, dangerous, etc, and performs an action according to the classification. This action changes environment and affects robot's level of satisfaction. Robot lives using these rules of classification for some time (epoch ~= 100 steps). After this epoch (~100 steps) robot tries to change the classification rules to increase his average level of satisfaction (-cost function) in next epoch.

So my question is: what classification/clustering algorithms should I consider using to achieve the goal? Are there any articles to read on relative topics? Is there a way ANN or SVM can fit such cases without knowing gradient of the cost function? I'll appreciate any help.


You'll need to train your model through metaheuristics such as simulated annealing (SA) or genetic algorithms (GA).

With SA, you can perturb your weights (add Gaussian noise) after each episode. If the new weights perform better, keep them. Otherwise, there is a probability to keep them or to undo the last perturbation. You can see it in action here. In this case, I've used SA to learn a rule table, so it is not restricted to ANNs. The robot's "satisfaction" is how fast it walks.

GA for fixed topology neural networks or other kind of models work similarly to SA, except that you'll work with many candidate solutions simultaneously and there is an additional "crossover" operation over your parameters besides the perturbation (which is called "mutation" here). This has been done, for instance, in Genetic Algorithm VS Air Man. In this case, the "satisfaction" is the difference between the player's and enemy's energy bar.

But you can even learn the ANN topology with GAs, and one way of doing that is through the NEAT algorithm. This has been done, for instance, in MarI/O, which @Tim mentioned in his comment.


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.