Machine learning for state-based transforms?

Question

If I provide:

1. A list of possible transforms, and,
2. A list of input states, and,
3. A corresponding list of output states for each input state, and,
4. A fitness function to score each output state

Which subset of machine learning can direct me towards an optimization algorithm that can map each input state to a dictionary of input states, and, failing to find a match, apply the necessary transforms to get me to the closest-related output state?

An example involving polygon legalization:

• Any given "window" can contain N different polygons, where each polygon has lower-left and upper-right co-ordinates, as well as a polygon "type".
• The input state of the polygons may or may not be "illegal".
• A list of transforms includes: move, copy, rotate, resize
• If the input state maps directly to any output state, the input state is decided to be legal. Nothing more to be done; move on the next window.
• If the input state matches any previously seen input state, transform to the matching (known-legal) output state. Nothing more to be done; move on the next window.
• Attempt transforms in different sequences until a state is reached that satisfies a fitness function. Store this input:output state combination. Move on to the next window.

Would this imply some combination of neural networking (for classification) and genetic/evolutionary algorithms? Or, does the presence of a fitness function negate the need to store combinations of input:output states?

Answer 1

If i get it correctly:

• You have an input polygon

• As a first step you want to "match" that against a list of previously seen templates. If this is successful, you pick it's corresponding output and move on.

• If not, you wish to find some optimal transformation, in order for it to satisfy some constraints that you have (your "objective function"). Then add the original+transformed shape to the templates list and move on.

Is this correct? I'll risk an answer anyways:

For the first part, I believe that there is a slew of literature out there. It's not my expertise, but first thing that comes to mind is measuring the distance in feature space between your shape and each template, and picking the closest one, it the distance is below a threshold that you set. "Feature" here would be either some low-level polygon property, e.g. x and y coordinates of vertices, or an abstraction, e.g. perimeter, area, no. vertices, mean side length/side length variance, etc.

For the second part, it really depends on the nature of your constraints/objective functions. Are they convex? Uni- or multi-modal? Single or multi-objective? Do you want to incorporate some domain knowledge (i.e. knowledge about what "good" transformations would be?)? One can really not tell without further details. Evolutionary algorithms are quite versatile but expensive methods (although some argue on that). If you can spare the possibly large amount of function evaluations, you could try EAs as a first step, and then refine your approach.

Finally, while not exactly related to what you describe in your process, I believe you may benefit by taking a look into auto-associative networks (and models in general); these are models that are able to perform constraint-satisfaction on their input, effectively enforcing learned relationships on input values. I could see this being used in your case by inputing a shape, and having a transformed shape as an output, which would be "legal", i.e. satisfying the constraints learned by the auto associative model. Thus, you would eliminate the need for a template matching + optimization altogether.