Switching from unsupervised to supervised learning

Question

Disclaimer: This is reposted from stackoverflow.

I am working on a research-oriented system of collaborating agents.

The agents perform many stochastic experiments (thousands per second), interacting with each other, in a complex high-dimension environment. Each experiment is reproducible and deterministic. The system is trying to learn optimal collaboration patterns.

Previous attempts (several skilled PhDs) have tried both rule-based algorithms, and also unsupervised learning. Both approaches topped out at between 10-20% of brute-force optimal scoring.

I now want to try to use supervised or reinforced learning. Previously, this was impossible because just labeling the data required NP runtime (per experiment!).

I have now devised a new set of faster P-time labels/classifiers. And I have a large amount ($10^9$ experiments) of labeled training data.

My questions are:

1. Can I hope for significantly better results with supervised or reinforced learning (vs. unsupervised learning)?

2. In general, has unsupervised learning been able to match the result of supervised learning?

ADDED COMMENT1

Yes i realized unsupervised and supervised are different domains Bur consider the typical problem of OCR, which we can approach with or without labeling... obviously labeling gives us more information... but we are still trying to solve the same problem, no?

ADDED COMMENT2

Some of the agents were hand coded with rule-based algorithms Complex rules are progressively harder to write AND more cpu-intensve (the rule itself often involves an NP search of a constrained solution space)

We have many samples from simulated AND production runs. The production runs include noise, non-optimal agents, and external changes

With unsupervised learning, we are able to isolate clusters of agent interactions Some clusters was manually selected and "converted" into a rule (In a nutshell, this rule tries to "approximate" some of the NP decisions made by agents) Some rules turn out to be good heuristics for agent behavior.

NOW, i (might) be able to actually score/label agent interaction. So if i relabel all previous runs, i can now run _supervised_learning_ And i am hoping to be able to find rules

Answer 1

Supervised learning depends on the quality of the labelling, and in fact mislabelled examples can be highly problematic in some regimes (e.g. consider a 0-1 problem and boosting combined with a generative classifier, when a mislabelled point is very representative of one class but labelled as belonging to the other).

With good labelling I think that you would expect a supervised approach to outperform a semi-supervised applied to the same problem on average (but not always). I don't have a reference, but I think one could show this using an information theoretic argument along the lines of "conditioning reduces entropy".

Unsupervised learning is rather different, but I imagine when you compare this to supervised approaches you mean assigning an unlabelled point to a cluster (for example) learned from unlabelled data in an analogous way to assigning an unlabelled point to a class learned from labelled data. Similarly to semi-supervised, I think supervised should do better on average assuming the labels on training data are good.

If I understand you correctly, you are using an unsupervised method to apply labels to training data, and you then want to employ a supervised method trained on that labelled training data. Then I think you can only expect to do well if your unsupervised method is good at labelling, and probably poorly otherwise.

Answer 2

Consider an active learning approach. From Wikipedia's Active learning (machine learning) article:

There are situations in which unlabeled data is abundant but labeling data is expensive. In such a scenario the learning algorithm can actively query the user/teacher for labels. This type of iterative supervised learning is called active learning. Since the learner chooses the examples, the number of examples to learn a concept can often be much lower than the number required in normal supervised learning. With this approach there is a risk that the algorithm might focus on unimportant or even invalid examples.

Answer 3

Not an answer, but a link: Hastie, Tibshirani and Friedman, Elements of Statistical Learning (2009, 763p, free pdf) describe on page 495 ff. a way of transforming unsupervised to supervised learning. (In a nutshell, Y=1 on the real data, Y=0 on Monte Carlo data). They note, though,

Although this approach ... seems to have been part of the statistics folklore for some time, it does not appear to have had much impact despite its potential to bring well-developed supervised learning methodology to bear on unsupervised learning problems.

I haven't used it myself; anyone ?

(Sigh: the questioner gives us no idea of how many data points, features, clusters he or she has; one size cannot possibly fit all.)