There are plenty of results for muli-class learning with with fixed discrete labels:
$$ \text{Standard multi-class classification:} \begin{cases} f: X \rightarrow Y_{index} = \{1, 2, 3, ..., k \}, \\ s.t. X \subset \mathbb{R}^{d_x} \end{cases} $$

I was wondering if there are any results which study multi-class learning with (countable, possibly finite) vector-valued outputs.

$$ \text{Vector-output multi-class classification:} \begin{cases} f: X \rightarrow Y_{vector} = \{y_1, y_2, y_3, ..., y_k \}, \\ s.t. X \subset \mathbb{R}^{d_x}, y_i \in \mathbb{R}^{d_y} \end{cases} $$

One may suggest that this is another problem: metric-learning between $X$ and $Y$ space: $$ \text{Standard metric-learning problem:} \begin{cases} f: X, Y \rightarrow [0,1], \\ s.t. X \subset \mathbb{R}^{d_x}, Y \subset \mathbb{R}^{d_y} \end{cases} $$

However all the results I came across in the metric-learning study the functions on one single vector space (as in unsupervised metric learning). In addition, vector-output multi-class classification is much more restricted (easier to learn?) than metric learning, since in what I am asking, the number of possible output vectors is fixed (unlike metric learning).


1 Answer 1


Sounds like you're trying to learn a map from vector space $X$ to vector space $Y$. The first thing that comes to mind is regression, which is a map from $X$ to $\mathbb{R}$. You can of course perform multiple regressions in parallel -- one for each dimension of $Y$ -- to learn a map from $X$ to $Y$. This has the shortcoming of ignoring any "interaction" or dependencies between the labels. You could first perform PCA on both the inputs in $X$ and the outputs in $Y$, and learn a map from the principal vectors of the input to the principle vectors of the output.

Another idea -- one that I'm particularly fond of -- is to perform Lipschitz extension. This assumes that $X$ and $Y$ are both metric spaces with known metrics. (A much more general setting than vector spaces!) See the pioneering paper of von Luxburg and Bousquet, for example: http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf

Update (23-Jun-2021): Our paper on regression via Kirszbraun's extension https://arxiv.org/abs/1905.11930 gives another approach, well-suited for Hilbert spaces.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.