<p>Sounds like you're trying to learn a map from vector space <span class="math-container">$X$</span> to vector space <span class="math-container">$Y$</span>. The first thing that comes to mind is regression, which is a map from <span class="math-container">$X$</span> to <span class="math-container">$\mathbb{R}$</span>. You can of course perform multiple regressions in parallel -- one for each dimension of <span class="math-container">$Y$</span> -- to learn a map from <span class="math-container">$X$</span> to <span class="math-container">$Y$</span>. This has the shortcoming of ignoring any &quot;interaction&quot; or dependencies between the labels. You could first perform PCA on both the inputs in <span class="math-container">$X$</span> <em>and</em> the outputs in <span class="math-container">$Y$</span>, and learn a map from the principal vectors of the input to the principle vectors of the output.</p>
<p>Another idea -- one that I'm particularly fond of -- is to perform Lipschitz extension. This assumes that <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are both metric spaces with known metrics. (A <em>much</em> more general setting than vector spaces!) See the pioneering paper of von Luxburg and Bousquet, for example:
<a href="http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf" rel="nofollow noreferrer">http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf</a></p>
<p>Update (23-Jun-2021): Our paper on regression via Kirszbraun's extension
<a href="https://arxiv.org/abs/1905.11930" rel="nofollow noreferrer">https://arxiv.org/abs/1905.11930</a> gives another approach, well-suited for Hilbert spaces.</p>

CC BY-SA 4.0
2016-02-29T09:49:59.410Z
2021-06-23T15:26:33.033Z
2021-06-23T15:26:33.033Z
Aryeh
<p>There are plenty of results for muli-class learning with with fixed discrete labels:<br>
$$
\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}
$$</p>

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

<p>$$
\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}
$$</p>

<p>One may suggest that this is another problem: <em>metric-learning</em> 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}
$$</p>

<p>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). </p>

<machine-learning>
Generalization bounds for multiclass learning when the output is vector space?
Daniel
# Generalization bounds for multiclass learning when the output is vector space?

(Asked by: username_0 on 2016-02-26)

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).

**Tags:** machine-learning


---

## 1 answers

### Answer by username_1 on 2016-02-29. Score: 6

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.


---

