Human Factors of "Multi-Objective Optimization"

[josh]

I should say – psychological limitations of vividness here is a shorthand vivid exemplar of this:

The complete forms of the objective function & or constraints have not been given because it is expensive to determine them with precision. We seek techniques which also reduce the region of space where precision is required for decision. For optimality, the cost of precision and departures from low order approximation should be controlled through first extracting all the relevant information in what has been specified prior to algorithmic step n regarding the space of feasible solutions & the non-dominated points in that space.

[josh]

Collecting the above, I’d like to see a math head work on a problem like this (emphasizing realism):

Initially given are:
A utility function for monetary gains and losses, smooth & differentiable except possibly at the special point u(0)=0.

A multi-dimensional space – we would like to study every form of variable combination (real, binary, categorical, integer) but we can start with the all real case

Existence of an unknown objective function from the given space to reals. Parts of the space may be labled as non-viable solutions where the objective function takes on some arbitrarily poor value. If the viable region of the space is not the empty set then the function can be assumed to satisfy some given Lipschitz continuity inside of (possibly disconnected) viable regions

A possibly empty set of linear inequalties (or membership claims) that describe support for the non-feasible regions

A possibly empty set of equations that are linear combinations of objective function evaluations – if this is non-empty then the basis points of the equations illustrate points in the feasible region.

A possibly empty set of linear or extended to non-linear equations that describe hyperplanes or hypermanifolds of the objective function in any feasible region.

A uniform cost C1 for testing the objective function at a given point

A uniform cost C2 for precisely evaluating the value difference between 2 arbitrary points X1 and X2, yielding an equation f(X1) + utility(money1) = f(X2).

Note that C2 may be arbitrarily less than C1

A Production multiple P such that if X’ is proposed as the optiumum solution while the true optimum is X”, then P|f(X’)-f(X”)| is the cost value of the penalty for near optimality.

Fill in detals & claims for interesting algorithmic extensions of this framework.

[josh]

Looking again, I think that the realistic cases also give possibly empty sets about the monotone nature of f(X) in some of the individual dimensions – monotonicity of the potential function f may be partially specified.

[josh]

Another important problem wrinkle is the case where some point & comparison valuation pairs are much cheaper than others because they are represented by an existing data set and do not require fresh experiments.

[josh]

Another good project: add noise/sampling models to the objective function evaluations. One kind of try might involve an analog of the “cooling” used in std simulated annealing (with free obj evals) where, instead, candidates are represented by sub-regions of feasible space.

[josh]

Additional feature suggestions:

Virtual node points – these points have the properties:

a) assigned location & possibly an assigned f(X) value
b) flag saying that they are not real for purposes that demand real,
c) artificially computed sim(x,x_other) given by some simple function

Examples:

i. A taxonomy root node with max sim to every other node – point is to make it become the root of clustering/spanning trees
ii. Nodes representing cluster centers – use of an artificial function given an artificially low similarity value to locations away from the cluster can help with other operations (see below) while reducing computation load.

Adding new dimensions to the space X, dropping dimensions, or reworking the dimension basis for particular subsets of the prior dimensional variables – while reusing prior work where that is possible

this happens in exploratory data analysis & science. New explanatory variables become noticed as discriminating different cases of interest.

Added dimensions can include fundamental variables not previously included & it can include similarity to particular points of interest including new virtual node points.

Dropping dimensions from the space:

Case 1: A given dimension is just thrown away

Case 2: A subset of the prior dimensions are reworked to a new basis

A new basis for a metric sub-space could be based principal component type analysis. Both metric & non-metric similarity spaces can use spectral clustering to reduce the basis. The spectral clustering can be seeded using the creation of new virtual node points.

[josh]

Folks are puzzled about adding features or reworking subspaces relative to the concept of saving work? What does it mean? That depends on algorithm & situation specifics. Consider these points for discussion:

A common form for similarity metrics weights the ratio of the intersection of positive features to the union. This concept leaves Sim(x1,x2) relatively unchanged when features not found in either x1 or x2 are considered elsewhere. Distance to a newly considered spectral cluster basis point should intuitively have little affect when both x1 and x2 are far away. This is similar to adding a local support kernel in a metric space.

Is there an estimator for the potential function in the two versions? If the new feature adds significant mutual information to the estimator then, from a statistical modeling POV, it was “missing” in the earlier analysis. If it does not then it is more of a utility feature. More work should be reusable in the utility case.

We can look at correlations between the Sim pairs in the new space vs. the old space as well as correlations between the new values of the potential function vs. the old one. Are they close? The closer they are, the more work should be reusable.

Are there algorithms available which actually achieve these forms of reuse in an efficient way? I bet yes, but the range of details doesn’t make it obvious without specific analysis.

On online commentator insisted that discovery an informative feature, previously not included in the analysis, offends his sense of professionalism. This is clearly not an algorithmic issue.

[josh]

In Chess & other artificial game programming, the heuristic principle of Quiescence search is often a good solution to deciding whether or not to keep partitioning a given line of analysis in case the scoring function might significantly change on deeper inspection. The heuristic value there is partially linked to the concept of playing a game against an adversary who is likely to quickly attack a weakness if it is actually present. In the optimization case, one can look at both changes to the expected scoring function & changes to the ease of distance clustering various partitions of data points. Analogs of both of these factors are considered in the Decision Tree Optimization literature. We believe the expansion of subspaces is analogous to the Decision Tree optimization case.

[josh]

The max influence of each type of data point can be regularized. This is related the noise model, but conceptually & operationally different. Another good feature. Regularization is also like both variance reduction & Bayesian priors, but different. Why? Might be a rough surface without much noise in the observations.

[josh]

A know class of tricky optimization problems are those where the feasible solution space is not convex. In that case, we can’t head our solution search into the area between alternative possibilities.

Generalizing on that important issue, there are multiple reasons why we might need to avoid the region between alternative possibilities & some of them can aris dynamically in our search. We include:

a) Non-convexity of feasible region due to constraints, static or dynamic

b) Non-convexity of the space itself due to arising from cognitive consideration of featural similarity rather than a physical region of continuous quantities

c) Usage demand to seek alternative, well spaced solution candidates

d) Knowledge discovery identifies in-between regions as poor solutions & we believe our search efficiency here is improved by divide-and-conquer.

We note that when our search is for multi-stage plans that achieve objectives, the dynamic introduction of non-convexity will be the normal case. This includes general robot trajectory planning in complex environments.

[josh]

Pointing out, a key example of expensive, important, multi-object optimization:

Combine a simulation for a robot design or a panel of robot designs varying overparameters with complex VR simulation environments. Then find candidate events/scenes that cause the most problems for the design. These issues probably need to be fixed before it becomes a viable product. Human feedback may need to be included in the evaluation of the candidate scenes.

Optimizing that usage is a priority.

[josh]

In past threads on VR & robotics I have talked about using VR to advance the state of the art. Here, we can also talk about commercial possibilities of approaching a client, either based on a request or cold calling based on analytical insights. VR could show details of the range of future planned applications for robotics at a facility site along with actual detailed simulation of scenario performance. Order driven mfg. can be a lot more custom at lower cost if the entire chain is dev ops & details are ready in advance.

[Author]

Posts