Instance Space

Definition

Instance Space

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

$${\mathcal{I}}_{\Pi }=\{I\mid I\text{ satisfies the input requirements of }\Pi \}.$$

Each $I\in {\mathcal{I}}_{\Pi }$ is a problem instance. If ${\mathcal{O}}_{\Pi }$ is the output space, the problem may be represented by a relation

$$R_{\Pi }\subseteq {\mathcal{I}}_{\Pi }\times {\mathcal{O}}_{\Pi },$$

where $(I,y)\in R_{\Pi }$ means that $y$ is a valid answer for $I$. 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 $\mathcal{X}$ and contains the possible input examples. It may be a feature space such as ${\mathbb{R}}^d$, and a supervised hypothesis has the form

$$h:\mathcal{X}\to \mathcal{Y}.$$

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