Instance Space

Definition

Instance Space

For a computational problem , its instance space is the set of all well-formed inputs to that problem:

Each is a problem instance. If is the output space, the problem may be represented by a relation

where means that is a valid answer for . The instance space concerns which abstract inputs are admissible; an instance encoding separately represents them as finite strings for an algorithm.

Machine-learning specialisation

In machine learning, the instance space is commonly written and contains the possible input examples. It may be a feature space such as , and a supervised hypothesis has the form

Vector coordinates and features belong to this specialisation; they are not required by the general computational concept.