Year: 2019

Abstract:
Autoencoder-based learning has emerged as a staple for disciplining representations in unsupervised and semi-supervised settings. This paper analyzes a framework for improving generalization in a purely supervised setting, where the target space is high-dimensional. We motivate and formalize the general framework of targetembedding autoencoders (TEA) for supervised prediction, learning intermediate latent representations jointly optimized to be both predictable from features as well as predictive of targets—encoding the prior that variations in targets are driven by a compact set of underlying factors. As our theoretical contribution, we provide a guarantee of generalization for linear TEAs by demonstrating uniform stability, interpreting the benefit of the auxiliary reconstruction task as a form of regularization. As our empirical contribution, we extend validation of this approach beyond existing static classification applications to multivariate sequence forecasting, verifying their advantage on both linear and nonlinear recurrent architectures—thereby underscoring the further generality of this framework beyond feedforward instantiations.

heading: 1 INTRODUCTION
text: Representation learning deals with uncovering useful underlying structures of data, and autoencoders (Hinton & Salakhutdinov, 2006) have been a staple in a variety of problems. While much research focuses on its use in unsupervised or semi-supervised settings with such diverse objectives as sparsity (Ranzato et al., 2007), generation (Kingma & Welling, 2013), and disentanglement (Chen et al., 2018), autoencoders are also useful in purely supervised settings—in particular, adding an auxiliary feature-reconstruction task to supervised classification problems has been shown to empirically improve generalization (Le et al., 2018); in the linear case, the theoretically quantifiable benefit matches that of simplistic norm-based regularization (Bousquet & Elisseeff, 2002; Rosasco & Poggio, 2009).
In this paper, we consider the inverse problem setting where the target space Y is high-dimensional; for instance, consider the multi-label classification tasks of object tagging, text annotation, and image segmentation. This is in contrast to the vast majority of works designed to tackle a high-dimensional feature space X (where commonly |X | |Y|, such as in standard classification problems). In this setting, the usual (and universal) strategy of learning to reconstruct features (Weston et al., 2012; Kingma et al., 2014; Le et al., 2018) may not be most useful: learning latent representations that encapsulate the variation withinX does not directly address the more challenging problem of mapping back up to a higher-dimensional Y . Instead, we argue for leveraging intermediate representations that are compact and more easily predictable from features, yet simultaneously guaranteed to be predictive of targets. In the process, we provide a unified theoretical perspective on recent applications of autoencoders to label-embedding in static, high-dimensional classification problems (Yu et al., 2014; Girdhar et al., 2016; Yeh et al., 2017). Extending into the temporal setting, we further empirically demonstrate the generality of target-embedding for recurrent, multi-variate sequence forecasting.
Our contributions are three-fold. First, we motivate and formalize the target-embedding autoencoder (TEA) framework: a general approach applicable to any underlying architecture. Second, we provide a theoretical learning guarantee in the linear case by demonstrating uniform stability; specifically, we obtain an O(1/N) bound on instability by analogizing the benefit of the auxiliary reconstruction task to a form of regularization—without incurring additional bias from explicit shrinkage. Finally, we extend empirical validation of this approach beyond the domain of static classification: using the task of multivariate disease trajectory forecasting as case study, we experimentally validate the
advantage that TEAs confer on both linear and nonlinear architectures using real-world datasets with both continuous and discrete targets. To the best of our knowledge, we are the first to formalize and quantify the theoretical benefit of autoencoder-based target-representation learning in a purely supervised setting, and to extend its application to the domain of multivariate sequence forecasting.

heading: 2 TARGET-EMBEDDING AUTOENCODERS
text: Let X and Y be finite-dimensional vector spaces, and consider the supervised learning problem of predicting targets y ∈ Y from features x ∈ X . With a finite batch of N training instances D = {(xn,yn)}Nn=1, the objective is to learn a mapping h : X → Y that generalizes well to new samples from the same distribution. The vast majority of existing work consider the setting—most commonly, classification—where |X | |Y|; under this scenario, autoencoders are often used to first transform the input into some lower-dimensional representation z ∈ Z amenable to the downstream task. Doing so involves adding an auxiliary reconstruction loss `r to the primary prediction loss `p.
Formally, solutions of this form—in supervised and semi-supervised settings alike—consist of a shared forward model φ : X → Z , a reconstruction function r : Z → X , and a prediction function d : Z → Y during training (where notation d reflects the downstream nature of the prediction task). Denote x̃ = r(φ(x)) and ŷ = d(φ(x)); then the complete loss function takes the following form,
L = 1
N
∑N n=1 [`p(ŷn,yn) + `r(x̃n,xn)] (1)
In contrast, we focus on settings where the target space Y is high-dimensional, and where possibly |Y| > |X |. In this case, we argue that learning to reconstruct the input is not necessarily most beneficial. In a simple classification problem, autoencoding inputs leverages the hypothesis that a reconstructive representation is also likely discriminative. In our setting, however, the more immediate problem is the high-dimensional structure of Y ; in particular, there is little guarantee that intermediate representations trained to encapsulate x are easily mapped back up to higher-dimensional targets.
Our goal is to make use of intermediate representations that are both predictable from features as well as predictive of targets. A target-embedding autoencoder (TEA)—versus what we shall term a feature-embedding autoencoder (FEA)—flips the model architecture around by learning an embedding of target vectors instead, which a predictor then learns a mapping into. This involves an encoder e : Y → Z , an upstream predictor u : X → Z , and a shared forward model θ : Z → Y . Denote ỹ = θ(e(y)) and ŷ = θ(u(x)); the complete loss function is now of the following form,
L = 1
N
∑N n=1 [`p(ŷn,yn) + `r(ỹn,yn)] (2)
Abstractly, the general idea of target space reduction is not new; in particular, it has been present in various solutions in the domain of multi-label classification (see Section 4 and Appendix B for discussions of related work). Here we focus on target-embedding autoencoders; they leverage the assumption that variations in (high-dimensional) target space are driven by a compact and predictable set of factors. By construction, learning to reconstruct directly in output space ensures that latent representations are predictive of targets; at the same time, jointly training with the prediction loss ensures that latent representations are predictable from features. Instead of learning representations for mapping out of (downstream), here we learn representations for mapping into (upstream); the shared forward model handles the rest. See Figure 1 for high-level diagrams of TEAs versus FEAs.
Training and Inference. Figure 2 gives block diagrams of component functions and objectives in (a) FEAs and (b) TEAs during training (see Algorithm 1 in Appendix C for pseudocode). Training occurs in three stages. First, the autoencoder is trained (to learn representations): the parameters of e and θ are learned on the reconstruction loss. Second, the prediction arm is trained to regress the learned
embeddings (generated by the encoder): the parameters of u are learned (on the latent loss) while the autoencoder is frozen. Finally, all three components are jointly trained on both prediction and reconstruction losses (Equation 2): parameters of the predictor, embedding, and shared forward model are trained simultaneously. Note that during training, the forward model receives two types of latents as input: encodings of true targets, as well as encodings predicted from features. At inference time, the target-embedding arm is dropped, leaving the learned hypothesis h = θ ◦ u for prediction. Figure 4 (Appendix C) provides step-by-step block diagrams of both training and inference in greater detail.
We emphasize that TEAs—as is the case with FEAs—specify a general framework independent of the implementation details of each component. For instance, the solutions to applications in Yu et al. (2014), Yeh et al. (2017), and Girdhar et al. (2016) can be abstractly regarded as linear and nonlinear instances of this framework, with domain-specific architectures (see Section 4 and Appendix B for more detailed discussions). Linear TEAs—which we study in greater detail in Section 3—involve parameterizations (Θ,Wu,We) of (θ, u, e) consisting of single hidden layers with linear activation.

heading: 3 STABILITY-BASED LEARNING GUARANTEE
text: Two questions are outstanding. The first is theoretical. We are motivated by the prior that variations in target space are driven by a lower-dimensional set of underlying factors. In this context, can we say something more rigorous about the benefit of TEAs? In this section, we take the first step in showing that jointly learning target representations improves generalization performance in the supervised setting. Specifically, we demonstrate that linear TEAs are characterized by uniform stability, from which theoretical guarantees are known to follow. The second question is empirical. We noted above that certain applications of label-embedding to classification can be interpreted through this framework. Does the benefit extend beyond its static, feedforward instantiations—into the temporal setting for multi-variate sequence forecasting, with both continuous and discrete targets? In Section 5, we first validate our theoretical findings with linear models and sensitivities, as well as extending our empirical analysis to the realm of recurrent, nonlinear models for both regression and classification.
Consider a linear TEA, where the upstream predictor is parameterized by Wu ∈ R|Z|×|X|, targetembedding by We ∈ R|Z|×|Y|, and shared forward model by Θ ∈ R|Y|×|Z|, where |Z| < |Y|. The complete loss function is given by L = 1N ∑N n=1 [`p(ΘWuxn,yn) + `r(ΘWeyn,yn)] following Equation 2. Interpreting the jointly learned autoencoding component as an auxiliary task, we show that the TEA algorithm for learning the shared forward model Θ is uniformly stable with respect to the domain of the supervised prediction task. To establish our notation, first recall the following:
Definition 1 (Generalization Bound) Given a learning algorithm D 7→ hD that returns hypothesis hD, let R(hD) = ∫ `(hD(x),y)dµ(x,y) denote the risk, and R̂(hD) = 1N ∑N n=1 `(hD(xn),yn) denote the empirical risk, where ` is some loss function. A generalization bound is a probabilistic bound on the defect that takes the following form: R(hD)− R̂(hD) ≤ with some confidence 1− δ.
Definition 2 (Uniform Stability) Let Di denote a modification of batch D where the i-th training instance (xi,yi) is replaced by an independent and identically distributed example (x′i,y ′ i). A learning algorithm is said to be γ-uniformly stable with respect to the loss function ` if ∀D ∈ (X ×Y)N ,∀i ∈ {1, ..., n},∀(x,y), (x′i,y′i) ∈ X ×Y : |`(hD(x),y)− `(hDi(x),y)| ≤ γ. Uniform stability holds if the minimum value of γ converges to zero as batch size N increases without limit.
Uniform stability can be used to derive algorithm-dependent generalization bounds. In particular, Bousquet & Elisseeff (2002) first showed that the defect of a γ-uniformly stable algorithm is is less than O((γ + 1/N) √ N log(1/δ)) with probability ≥ 1 − δ. Feldman & Vondrak (2018) recently
demonstrated an improved bound of O( √
(γ + 1/N) log(1/δ)). Here, we show uniform stability for linear TEAs, where γ is O(1/N)—by which a tight generalization bound follows immediately. Before we begin, we introduce two additional tools: c-strong convexity and σ-admissibility. Note that these conditions are standard and easily satisfied—for instance, by the quadratic loss function; for more context see for example Bousquet & Elisseeff (2002), Liu et al. (2016), and Mohri et al. (2018).
Definition 3 (c-Strong Convexity) Differentiable loss function ` is c-strongly convex if ∀h, h′ ∈ H : 〈h′(x) − h(x),∇`(h′(x),y) − ∇`(h(x),y)〉 ≥ c‖h′(x) − h(x)‖22 for some c ∈ R+, where ∇`(h(x),y) denotes the gradient with respect to h(x), and 〈·, ·〉 denotes the dot product operation.
Definition 4 (σ-Admissibility) Loss function ` is σ-admissible with respect to the underlying hypothesis classH if ∀h, h′ ∈ H : |`(h′(x),y)− `(h(x),y)| ≤ σ‖h′(x)− h(x)‖2 for some σ ∈ R+. To obtain uniform stability, we make two assumptions—both analogous to prior work arguing from the benefit of learning shared models between tasks. Liu et al. (2016) deals with learning multiple tasks in general, and Le et al. (2018) deals with reconstructing inputs in what we describe as FEAs. Now in multi-task learning, the separate tasks are usually chosen due to some prior relationship between them. In the case of Assumption 1 in Liu et al. (2016) and Assumption 5 in Le et al. (2018), this is assumed to come from similarities in feature structures across tasks; hence their assumptions of cross-representability are made in feature space. (Note that this restricts primary and auxiliary features to be elements of the same space). Our setting is contrary: the inputs to primary and auxiliary tasks come from different spaces, but are trained to produce similar labels through a compact, shared latent space; hence our assumption of cross-representability will be made in this latent space instead.
Assumption 1 (Representative Vectors) There exists a representative subset of target vectors B = {b1, ...,bM} ⊂ {y1, ...,yN} such that the latent representation of any individual (x,y) can be linearly reconstructed from that of the representative subset with small error, i.e. Wpx =∑M m=1 αmWebm+η and Wey = ∑M m=1 βmWebm+η for some coefficients αm, βm ∈ R, where ΣMm=1α 2 m ≤ r2α, ΣMm=1β2m ≤ r2β for some rα, rβ ∈ R+, and η is a small error satisfying ‖η‖2 ≤ ε.
Remark 1 This assumption is comparatively mild, even for ε = 0. Note that in Liu et al. (2016) the features for separate tasks come from different examples in general, and the similarity of their distributions within X is simply assumed. Here, each pair of inputs to the prediction and reconstruction tasks comes from the same instance, and similarity within Z is explicitly enforced through the (joint) training objective. In addition, observe that the assumption will hold with zero error as long as the number of independent latent vectors is at least |Z|. Furthermore, unlike the scenarios in Liu et al. (2016) and Le et al. (2018) we do not require that the input domains of the two tasks be identical. Therefore for ease of exposition, we assume going forward that ε = 0 (see Remark 6 in Appendix A). Remark 2 A comparison with Assumption 4 in Le et al. (2018) sheds additional light on why we expect TEAs to be beneficial where |Y| > |Z|, in contrast with the (more typical) scenario |X | > |Z| |Y|. Critically, the technique in Le et al. (2018) banks on the fact that the prediction arm projects the latent into a lower-dimensional target space. Conversely, Assumption 1 here relies on the fact that the encoding arm maps into the latent space from a higher-dimensional target space (rendering cross-representability therein reasonable). The distinction is crucial: we certainly do not expect any benefit from autoencoding trivially low-dimensional vectors! Note also that here the representative vectors are taken from Y ; to take them from X instead would be unreasonable. For any compressive autoencoder, we generally expect if some subset {b1, ...,bM} ⊂ {y1, ...,yN} spans Y that {Web1, ...,WebM} then also span Z in order to be maximally reconstructive. The same cannot be said of subsets {c1, ..., cM} ⊂ {x1, ...,xN} that span X—for instance, take |X | ≤ |Z|. In addition to being representative in terms of latent values, the set of representative points also needs to be representative in terms of the reconstruction error. First, let L′ denote the counterpart
to L where the i-th sample (xi,yi) is replaced by some new instance (x′i,y ′ i) ∈ X × Y; that is, L′ = 1N [`p(ΘWux ′ i,y ′ i) + `r(ΘWey ′ i,y ′ i) + ∑N n=1;n 6=i (`p(ΘWuxn,yn) + `r(ΘWeyn,yn))]. Then, let Θ∗, Θ′∗ denote the optimal parameters corresponding to the two losses L and L ′.
Assumption 2 (Representative Errors) LetL′r contain the reconstruction errors of the dataset without the i-th sample: L′r = (1/N)Σ N n=1;n 6=i`r(ΘWeyn,yn), and let L B r denote the reconstruction error of the representative subset: LBr = (1/M)Σ M m=1`r(ΘWebm,bm). Then there exists some a > 0 such that for any small κ > 0 : LBr (Θ∗)− LBr (κΘ′∗ + (1− κ)Θ∗) + LBr (Θ′∗)− LBr (κΘ∗ + (1− κ)Θ′∗) ≤ a [L′r(Θ∗)− L′r(κΘ′∗ + (1− κ)Θ∗)] + a [L′r(Θ′∗)− L′r(κΘ∗ + (1− κ)Θ′∗)]. That is, the difference in reconstruction error LBr between the two points Θ∗, Θ ′ ∗ is upper bounded by some constant factor of the corresponding difference in reconstruction error L′r at the two points. Importantly, note that this does not require that the values of the errors L′r and L B r themselves be similar, only that their differences be similar. This assumption is identical to Assumption 6 in Le et al. (2018), and plays an identical role: we make use of LBr —which is only dependent on M—to allow the bound to decay with N ; this is in contrast with the generic multi-task analysis of Liu et al. (2016), which—if applied directly to TEAs (as with FEAs)—would give a bound that does not decay with N .
Theorem 1 (Uniform Stability) Let `p and `r be σp-admissible and σr-admissible loss functions, and let `r be c-strongly convex. Then under Assumptions 1 and 2, the following inequality holds,
|`p(Θ′∗Wux,y)− `p(Θ∗Wux,y)| ≤ 2(σ2pr 2 α + σpσrrαrβ)aM
cN Proof. Appendix A.
Corollary 1 (Generalization Bound) Consider the same conditions as in Theorem 1; that is, let `p and `r be σp-admissible and σr-admissible losses, and let `r be c-strongly convex. Then under Assumptions 1 and 2, the defect is less than O( √ (1/N) log(1/δ)) with probability at least 1− δ.
Proof. Follows immediately from Theorem 1 (above) and either of the following (similar results hold for both): Theorem 1.2 (Feldman & Vondrak, 2018), and Theorem 12 (Bousquet & Elisseeff, 2002).
In supervised learning, it is often easy to make an argument—on an intuitive level—for the “regularizing” effect of additional loss terms. In contrast, this analysis allows us to unambiguously identify and quantify the benefit of the embedding component as a regularizer (see Remark 4 in Appendix A).
Remark 3 In the linear label space reduction framework of Yu et al. (2014), uniform convergence is also shown to hold via norm-based regularization. Specifically for uniform stability, a similar bound can also be achieved by adding a strongly convex term to the objective, such as Tikhonov—and `2—regularization (Bousquet & Elisseeff, 2002; Rosasco & Poggio, 2009; Shalev-Shwartz et al., 2010). Here, however, the joint reconstruction task leverages a different kind of bias—precisely, the assumption that there exist compact and predictable representations of targets. Therefore the significance of this analysis is that we achieve an equivalent result independent of explicit regularization.

heading: 4 RELATED WORK
text: Our work straddles three threads of research: (1) supervised representation learning with autoencoders, (2) label space reduction for multi-label classification, and (3) stability-based learning guarantees. Appendix B provides a much expanded treatment, and presents summary tables for additional context.
Supervised representation learning. While a great deal of research is devoted to uncovering useful underlying structures of data through autoencoders—with various properties such as sparsity (Ranzato et al., 2007) and disentanglement (Chen et al., 2018), among many others (Tschannen et al., 2018)—the goal of better representations is often for the benefit of downstream tasks. Semi-supervised autoencoders jointly optimized on partially-labeled data can obtain compact representations that improve prediction (Weston et al., 2012; Kingma et al., 2014; Ghifary et al., 2016). Furthermore, auxiliary reconstruction is also useful in a purely supervised setting: rather than focusing on how specific architectures better structure unlabeled data, Le et al. (2018) show the simple benefit of feature-reconstruction on supervised classification—a special case of what we describe as FEAs.
In contrast, we focus on target-representation learning in the supervised setting, and analyze its benefit under the prior that high-dimensional targets are driven by a compact and predictable set of factors.
We take inspiration from the empirical study of Girdhar et al. (2016), where latent representations of 3D objects are jointly trained to be predictable from 2D images. Their setup can be viewed as a specific instance of TEAs with (nonlinear) convolutional components, with a minor variation in training: in the joint stage, predictors continue to regress the learned embeddings, and gradients only backpropagate from latent space (instead of target space). Unlike the symmetry of our losses (which we require for our analysis above), their common decoder is only shared indirectly (and predictions made indirectly). As it turns out, this does not appear to matter for performance (see Section 5). In Mostajabi et al. (2018), a two-stage procedure is used for semantic segmentation—loosely comparable to the first two stages in TEAs; in contrast to our emphasis on joint training, they study the benefit of a frozen embedding branch in parallel with direct prediction. More broadly related to target-embedding, Dalca et al. (2018) build anatomical priors for biomedical segmentation in unsupervised settings.
Multi-label classification. The general idea of target space dimension reduction has been explored for multi-label classification problems (commonly, annotation based on bags of features). These first derive a reduced label space, then subsequently associate inputs to it; methods include compressed sensing (Hsu et al., 2009), principal components (Tai & Lin, 2010), maximum-margin coding (Zhang & Schneider, 2012), and landmarking (Balasubramanian & Lebanon, 2012). Closer to our theme of joint learning, Chen & Lin (2012) first propose simultaneously minimizing encoding and prediction errors via an SVD formulation. Using generic empirical risk minimization, Yu et al. (2014) formulate the problem as a linear model with a low-rank constraint. While this captures an intuition (similar to ours) of restricted latent factors, their error bounds require norm-based regularization (unlike ours).
Recently, Yeh et al. (2017) generalize the label-embedding approach to autoencoders. This flexibly accommodates custom losses to exploit correlations, as well as deep learning for nonlinearities. Our work is related to this line of research, although we operate at a higher level of abstraction, with a significant difference in focus. Their problem is multi-label classification, and their starting point is binary relevance (i.e. label by label). During reduction, they worry about specific losses that capture dependencies within and among spaces. In contrast, we worry about autoencoding at all—that is, we focus on the effect of joint reconstruction on learning the prediction model. Problems can be of any form: classification or regression, and our starting point is direct prediction (i.e. no reconstruction).
Stability and learning guarantees. Generalizability via hypothesis stability is first studied in Rogers & Wagner (1978) and Devroye & Wagner (1979); unlike arguments based on the complexity of the search space (Vapnik & Chervonenkis, 1971; Pollard, 1984; Koltchinskii, 2001), these account for how the algorithm depends on the data. Bousquet & Elisseeff (2002) first formalize the notion of uniform stability sufficient for learnability, and Feldman & Vondrak (2018) use ideas related to differential privacy (Bassily et al., 2016) for further improvement. Separately, while there is a wealth of research on dimensionality reduction and autoencoders (Singh et al., 2009; Mohri et al., 2015; Gottlieb et al., 2016; Epstein & Meir, 2019), they either operate in the semi-supervised setting, or focus on the benefit of feature representations (not targets) and also do not consider joint learning.
The benefit of jointly learning multiple tasks through a common operator (Caruana, 1997) is explored with VC-based (Baxter, 2000) and Rademacher complexity-based (Maurer, 2006; Maurer et al., 2016) analyses. Recently, Liu et al. (2016) show that the algorithm for learning the shared model in a multi-task setting is uniformly stable. While our argument is based on theirs, we are not interested in a generic bound for all tasks; closer to Le et al. (2018), we focus on the primary prediction task, and leverage the auxiliary reconstruction task for stability. Similarly, we arrive at an O(1/N) on instability without an explicit regularization term as in Bousquet & Elisseeff (2002). Unlike them, however, the fundamental distinction of our setting is that Y is high-dimensional (but where the underlying factors are assumed compact); in this sense our focus is the mirror opposite of theirs.

heading: 5 EXPERIMENTS AND DISCUSSION
text: So far, we have formalized a general target-autoencoding framework for supervised learning, and quantified the benefit via uniform stability. Our overall goal in this section is to explore this benefit in a simple controlled setting, such that we can identify and isolate its utility on the prediction task, and investigate any sensitivities of interest. By way of preface, we emphasize two observations from above: (1) In the static, multi-label classification setting, the gain from label-embedding has been studied, including the autoencoder approach of Yeh et al. (2017)—which can be viewed as an instantiation of TEAs with sophisticated refinements. (2) The benefit of target-autoencoding is also
The effective input dimension |X | is computed as the dimension of static data plus the product of the width of the historical window (of temporal information) with its dimension; the effective target dimension |Y| is similarly computed as the product of the width of the forecast window (of temporal information) with its dimension.
demonstrated using nonlinear, convolutional architectures in Girdhar et al. (2016)—which is also an instantiation of TEAs, also noting significant gains. Therefore a natural question of interest is:
• Does the utility of target-embedding extend to (nonlinear) recurrent models with sequential data for general, high-dimensional targets (i.e. regression and/or classification)?
Disease Trajectories. In this section, we take the first step in answering this question—as our empirical contribution, we extend validation of target-embedding autoencoders to the domain of multivariate sequence forecasting, exploring its utility on linear and nonlinear sequence-to-sequence architectures. What makes a good testbed? In particular, the progression of diseases (and their markers) is high-dimensional in presentation; at the same time, their evolution is often driven by latent biological dynamics (Szczesniak et al., 2017; Pascoal et al., 2017; Alaa & van der Schaar, 2019). With the increasing importance of early diagnosis and timely intervention in healthcare, the ability to forecast individual disease trajectories (Y) in the presence of limited windows of information (X ) has become increasingly desirable (Donohue et al., 2014; Pham et al., 2017; Bhagwat et al., 2018).
Datasets. We use three datasets in our experiments. The first consists of a cohort of patients enrolled in the UK Cystic Fibrosis registry (UKCF), which records follow-up trajectories for over 10,000 patients. We are interested in forecasting future trajectories for the 11 possible infections and 23 possible comorbidities (all binary variables) recorded at each follow-up, using past trajectories and basic demographics as input. The second consists of patients in the Alzheimer’s Disease Neuroimaging Initiative study (ADNI), which tracks disease progression for over 1,700 patients. We are interested in forecasting the evolution of the 8 primary biomarkers and 16 cognitive tests (all continuous variables) measured at each visit, using past measurements and basic demographics as input. The third consists of a cohort of patients in intensive care units from the Medical Information Mart for Intensive Care (MIMIC), which records physiological data streams for over 22,000 patients. Likewise, we are interested in forecasting future trajectories for the 361 most frequently measured variables such as vital signs and lab tests (both binary and continuous variables), again using past measurements and basic demographics as input. See Appendix D for more information on datasets.
Experimental Setup. In each instance, the prediction input is a precedent window of up to width wx, and the prediction target is the succedent window of width wy . For UKCF (wx, wy) = (3, 4) at 1-year resolution, for ADNI (4, 8) at 6-month resolution, and for MIMIC (5, 5) at 4-hour (resampled) resolution. All models are implemented in Tensorflow. Linear models consist of a single hidden layer with no nonlinearity; for the nonlinear case, we implement an RNN model for each component using GRUs. See Appendix D for additional detail on model implementation and configuration. For evaluation, we measure the mean squared error (MSE) for continuous targets (averaged across variables), and the area under the precision-recall curve (PRC) and area under the receiver operating characteristic curve (ROC) for binary targets (averaged across variables). We use cross-validation on the training set for hyperparameter tuning, selecting the setting that gives the lowest validation loss averaged across folds. For each model and dataset, we report the average and standard error of each performance metric across 10 different experiment runs, each with a different random train-test split.
Note that forecasting high-dimensional disease trajectories is challenging, and input information is deliberately limited (as is often the case in medical practice); the desired targets are similar or higherdimensional than the inputs (see Table 1). This obviously results in an inherently difficult prediction problem—but which makes for a good candidate setting to test the utility of target-representation learning. RNN autoencoders have previously been proposed for learning representations of inputs (i.e. FEAs instantiated with RNNs) to improve classification (Dai & Le, 2015), prediction (Lyu et al., 2018), generation (Srivastava et al., 2015), and clustering (Baytas et al., 2017); similarly, their mission is not in excessively optimizing specific architectural novelties to match state-of-the-art, but rather in exploring the benefit of the autoencoding framework. Here, we learn representations of targets.
The two-sample t-test for difference in means is conducted on the results. An asterisk indicates statistically significant difference in means (p-value < 0.05) relative to the TEA result. PRC and ROC metrics are reported separately for variables representing infections (I) and comorbidities (C). See Tables 9–10 for extended results.
The two-sample t-test for difference in means is conducted on the results. An asterisk indicates statistically significant difference in means (p-value < 0.05) relative to the TEA result. For UKCF, only PRC metrics for infections (I) and comorbidities (C) are shown due to space limitation; for ADNI, MSE metrics are reported separately for targets representing biomarkers (B) and cognitive tests (C). See Tables 13–14, 17–18, and 21–22.

heading: 5.1 MAIN RESULTS
text: Overall Benefit. First, we examine the overall utility of TEAs. To verify the linear case first, Table 2 summarizes the performance of TEA and alternate setups on UKCF. The temporal axis is flattened to simulate ordinary static multi-label classification, and the base case is direct prediction (Base)—that is, absent any auxiliary representation learning or regularization. Next, we allow for `2-regularization over direct prediction (REG), as well as over all other methods. FEAs differ only by the added feature-reconstruction, and TEAs only by the target-reconstruction; as an additional sensitivity, we also implement a combined approach (F/TEA). More generally, we also wish to examine the benefit of TEA for the nonlinear case: Table 3 summarizes analogous results where component functions are implemented with GRU networks; results are shown for all datasets. Ceteris paribus, we observe that target-representation learning has a notable positive impact on performance. Interestingly, learning representations of inputs does not yield significant benefit, and the hybrid approach (F/TEA) is worse than TEA; this suggests that forcing intermediate representation to encode both features and targets may be overly constraining. (Note that for the linear model, the instances are restricted to those for which the full input window is available; as a consequence, the results for linear and nonlinear cases are not directly comparable). Figures 4 (Appendix C) and 5 (Appendix D) give training diagrams for all comparators. Additional experiment results (by model, timestep, metric) are in Appendix E.1-2.
Source of Gain. There are two (related) interpretations of TEAs. First, we studied the regularization view in Section 3; this concerns the benefit of joint training using both prediction and reconstruction losses. Ceteris paribus, we expect performance to improve purely by dint of the jointly trained TEA objective. Second, the reduction view says that TEAs decompose the (difficult) prediction problem into two (smaller) tasks: the autoencoder learns a compact representation z of y, and the predictor learns to map x to z. This makes the potential benefit of staged training (Section 2 and Appendix C) intuitively clear, and suggests an alternative—that of simply training the autoencoder and predictor arms in two stages—à la Mostajabi et al. (2018). As a general framework, TEAs is a combination of both ideas: all three components are jointly trained in a third stage—à la Girdhar et al. (2016). We now account for the improvement in performance due to these two sources of benefit; Table 4 does so for the linear case (on UKCF), and Table 5 for the more general nonlinear case (on all datasets). The “No Joint” setting isolates the benefit from staged training only. This is analogous to basic unsupervised pretraining (though using targets), and corresponds to omitting the final joint training stage in Algorithm 1. The “No Staged” setting isolates the benefit from joint training only (without pretraining the autoencoder or predictor), and corresponds to omitting the first two training stages in Algorithm 1. The “Neither” setting is equivalent to vanilla prediction (REG) without leveraging either of the advantages. We observe that while both sources of benefit are individually important, neither setting performs quite as well as when both are combined. See Appendix E.1-2 for extended results.
Variations. Having established the utility of target-embedding, we can ask whether variations on the same theme perform similarly. In particular, the embeddings in the empirical studies of Girdhar et al. (2016) and Yeh et al. (2017) are jointly learned via the reconstruction loss `r and latent loss `z—that is, the prediction arm continues to regress learned embeddings during the joint training stage (Figure 4(d), in Appendix D). The principle is similar, although (as noted in Section 4) the primary task is therefore learned indirectly; this is in contrast to the vanilla TEA setup, where the primary task is learned directly via the prediction loss `p. Tables 4 and 5 also compare the performance of vanilla TEAs with this indirect variant (TEA(L)), as well as a hybrid variant (TEA(LP)) for which both latent and prediction losses are trained jointly with the reconstruction loss (Figure 4(e). Perhaps as expected, we observe that performance across all three variants are more or less identical, affirming the general benefit of target-representation learning. Again, see Appendix E.1-2 for extended results.

heading: 5.2 SENSITIVITIES
text: Regularization. Of course, target-representation learning is not a replacement for other regularization strategies; it is an additional tool that can be used in parallel where appropriate. Figure 3(a) shows the performance of TEA and REG with various coefficients ν on `2-regularization. By itself, introducing `2-regularization does improve performance up to a certain point, beyond which the additional shrinkage bias incurred begins to be counterproductive; this is not surprising. Interestingly, introducing target-representation learning appears to leverage an orthogonal bias: it consistently improves prediction performance regardless of level of shrinkage. This is a practical result of the theoretical observation in Remark 3: while prior works obtain stability through explicit `2-regularization, the benefit from target-embedding relies on a different bias entirely, which allows us to combine them. While increasing the strength of either form of regularization reduces variability in results (see also below), excessive bias of either alone degrades performance. See Appendix E.3 for full results.
Strength of Prior. Target-embedding attempts to leverage the assumption that there exist compact and predictable representations of targets. Realistically (e.g. due to measurement noise), of course, this will not hold perfectly. In our experiments, we set the ratio of prediction and reconstruction losses to be 1 : 1 for TEA (as well as FEA and F/TEA); that is, the “strength-of-prior” coefficient λ on `r is 0.5. In order to isolate the effect of λ during joint training, we observe the performance of TEAs with joint training only (i.e. removing the confounding effect of staged training). For large values of λ, we expect the reconstruction task to dominate in priority, which is (under an imperfect prior) not beneficial for the ultimate prediction task—in general, a hidden representation that is most reconstructive is not necessarily also what is most predictable). For small values of λ, the setup begins to resemble direct prediction. Figure 3(b) verifies our intuition. Note that in the extreme case of λ = 1, predictions are no better than random (see ROC∼ 0.5). See Appendix E.3 for full results.
Sample Complexity. Figure 3(c) shows the performance of TEA and REG under various levels of data scarcity. The benefit conferred by TEAs is significant especially when the amount of training data N is limited. Importantly, note that we are operating strictly within the context of supervised learning: unlike in semi-supervised settings, here we are not just restricting access to paired data; we are restricting access to data per se. (Though beyond the scope of this paper, we expect that extending TEAs to semi-supervised learning with additional unpaired data would yield larger gains). Here, without the luxury of learning from unpaired data, we highlight the comparative advantage purely from the addition of target-representation learning. Again, see Appendix E.3 for full results.

heading: 5.3 DISCUSSION
text: By way of conclusion, we emphasize the importance of our central assumption: that there exist compact and predictable representations of the (high-dimensional) targets. This is critical: targetembedding is not useful where this is not true. Now obviously, learning representations of targets is unnecessary if the output dimension is trivially small (e.g. if the target is a single classification label), or if the problem itself is trivially easy (e.g. if direct prediction is already perfect). Also obvious is the situation where representations cannot possibly be compact (e.g. if all output dimensions are independent of each other), in which case any model with a compressive (bottleneck) representation as an intermediate target may make little sense to begin with. Perhaps less obvious is that we cannot assume that the goals of prediction and reconstruction are always aligned. Just as in learning featureembeddings (for downstream classification), what is most reconstructive may not necessarily encode what is most discriminative; so too in learning target-embeddings (for upstream prediction), what is most reconstructive may not necessarily encode what is most predictable. In the case of disease trajectories, it is medical knowledge that permits this assumption with some confidence. Appendix E.4 gives an extreme (synthetic) counterexample where this prior is outright false—i.e. prediction and reconstruction are directly at odds. While certainly contrived, it serves as a caveat about assumptions.
Using the deliberately challenging setting of disease trajectory forecasting with limited information, we have illustrated the nontrivial utility of target-representation learning in a controlled setting with baseline models. While we appreciate that component models in the wild may be more tailored, this setting better allows us to identify and isolate the potential utility of target-autoencoding per se. In addition to verifying our intuitions for the linear case, we have extended empirical validation of target-autoencoding to (nonlinear) sequence-to-sequence recurrent architectures; along the way, we explored the sources of gain from joint and staged training, as well as various sensitivities of interest. Where the prior holds, target-embedding autoencoders are potentially applicable to any high-dimensional prediction task beyond static classification and imaging applications, and exploring its utility for other specific domain-architectures may be a practical direction for future research.

heading: ACKNOWLEDGMENTS
text: This work was supported by Alzheimer’s Research UK (ARUK), the US Office of Naval Research (ONR), and the National Science Foundation (NSF): grant numbers ECCS1462245, ECCS1533983, and ECCS1407712. We thank the UK Cystic Fibrosis Trust, the Alzheimer’s Disease Neuroimaging Initiative, and the MIT Lab for Computational Physiology respectively for making the UKCF, ADNI, and MIMIC datasets available for research. We thank the reviewers for their helpful comments.

heading: A PROOF OF THEOREM 1
text: Definition 5 (Bregman Distance) Let ` be some differentiable, strictly convex loss. For any h, h′ ∈ H, the Bregman distance associated with ` is given by D`(h′‖h) = `(h′)− `(h)− 〈h′ − h,∇`(h)〉. Additivity and non-negativity are easy to see; that is, D`(h′‖h) ≥ 0 for any h, h′ ∈ H, and if ` = `1 + `2 and both `1 and `2 are convex functions, then D`(h′‖h) = D`1(h′‖h) +D`2(h′‖h).
Theorem 1 (Uniform Stability) Let `p and `r be σp-admissible and σr-admissible loss functions, and let `r be c-strongly convex. Then under Assumptions 1 and 2, the following inequality holds,
|`p(Θ′∗Wux,y)− `p(Θ∗Wux,y)| ≤ 2(σ2pr 2 α + σpσrrαrβ)aM
cN
Proof. The overall strategy consists of three steps in sequence. First, we want to bound the delta in prediction loss under Θ∗ and Θ′∗ using the set of representative vectors B. Second, we bound the resulting expression in terms of the Bregman divergence of the complete loss functions L and L′ under Θ∗ and Θ′∗. Third, we express the divergence back in terms of the original expression itself (consisting of representative vectors), which allows us to solve for a bound on that expression. Finally, combining the results from the three steps completes the proof. We begin with the left-hand term,
|`p(Θ′∗Wux,y)− `p(Θ∗Wux,y)| ≤ σp‖(Θ′∗ −Θ∗)Wux‖2
= σp ∥∥∥∥∥ M∑ m=1 αm(Θ ′ ∗ −Θ∗)Webm ∥∥∥∥∥ 2 ≤ σprα √√√√ M∑ m=1 ‖(Θ′∗ −Θ∗)Webm‖22 (3)
where the first inequality follows from the fact that `p is σp-admissible, the equality follows from Assumption 1 for some coefficients αm ∈ R, and the second inequality follows from the CauchySchwarz inequality. As our second step, the goal is to upper-bound the term under the square-root,
M∑ m=1 ‖(Θ′∗ −Θ∗)Webm‖ 2 2
≤ 1 c M∑ m=1 〈(Θ′∗ −Θ∗)Webm,∇`r(Θ′∗Webm,bm)−∇`r(Θ∗Webm,bm)〉
= 1
c M∑ m=1 〈 Θ′∗ −Θ∗,∇`r(Θ′∗Webm,bm)b>mW>e −∇`r(Θ∗Webm,bm)b>mW>e 〉 = M
c
[ DLBr (Θ ′ ∗‖Θ∗) +DLBr (Θ∗‖Θ ′ ∗) ]
(4)
where the first inequality follows from the fact that `r is c-strongly convex, and the final equality follows from the definition of Bregman divergence (the standalone loss terms cancel). We want an expression in terms of the loss functions L and L′, which will subsequently allow us to obtain a bound expressed back in terms of the set of representative vectors. Focusing on the term in the brackets,
DLBr (Θ ′ ∗‖Θ∗) +DLBr (Θ∗‖Θ ′ ∗)
= −〈Θ′∗ −Θ∗,∇LBr (Θ∗)〉 − 〈Θ∗ −Θ′∗,∇LBr (Θ′∗)〉
= lim κ→0+
1
κ
[ LBr (Θ∗)− LBr (κΘ′∗ + (1− κ)Θ∗) + LBr (Θ′∗)− LBr (κΘ∗ + (1− κ)Θ′∗) ] ≤ lim κ→0+ a κ [L′r(Θ∗)− L′r(κΘ′∗ + (1− κ)Θ∗) + L′r(Θ′∗)− L′r(κΘ∗ + (1− κ)Θ′∗)]
= a [−〈Θ′∗ −Θ∗,∇L′r(Θ∗)〉 − 〈Θ∗ −Θ′∗,∇L′r(Θ′∗)〉]
= a [ DL′r (Θ ′ ∗‖Θ∗) +DL′r (Θ∗‖Θ′∗) ] ≤ a [DL(Θ′∗‖Θ∗) +DL′(Θ∗‖Θ′∗)] (5)
where the first and last equalities follows from the definition of Bregman divergence, and the second equality from the definition of directional derivatives. The first inequality follows from Assumption 2; for the second inequality, note that L′r consists of a strict subset of the set of strictly convex losses that L consists of, and similarly for L′. Therefore by additivity and non-negativity of the Bregman distance, we have that DL′r (Θ ′ ∗‖Θ∗) ≤ DL(Θ′∗‖Θ∗) and DL′r (Θ∗‖Θ′∗) ≤ DL′(Θ∗‖Θ′∗). Our third and final step is to go back and bound this term again using the set of representative vectors,
DL(Θ ′ ∗‖Θ∗) +DL′(Θ∗‖Θ′∗)
= L(Θ′∗)− L(Θ∗) + L′(Θ∗)− L′(Θ′∗)
= [L(Θ′∗)− L′(Θ′∗)]− [L(Θ∗)− L′(Θ∗)]
= 1
N [`p(Θ
′ ∗Wuxi,yi) + `r(Θ ′ ∗Weyi,yi)]−
1
N [`p(Θ
′ ∗Wux ′ i,y ′ i) + `r(Θ ′ ∗Wey ′ i,y ′ i)]
− 1 N [`p(Θ∗Wuxi,yi) + `r(Θ∗Weyi,yi)] + 1 N [`p(Θ∗Wux ′ i,y ′ i) + `r(Θ∗Wey ′ i,y ′ i)] ≤ σp N (‖(Θ′∗ −Θ∗)Wuxi‖2 + ‖(Θ′∗ −Θ∗)Wux′i‖2) + σr N (‖(Θ′∗ −Θ∗)Weyi‖2 + ‖(Θ′∗ −Θ∗)Wey′i‖2)
≤ 2(σprα + σrrβ) N √√√√ M∑ m=1 ‖(Θ′∗ −Θ∗)Webm‖22 (6)
where for first equality note that by construction the gradients of the losses L and L′ are zero at the respective optimal models Θ∗ and Θ′∗. The first inequality follows from the fact that `p and `r are σp-admissible and σr-admissible respectively, and the second inequality follows from Assumption 1 and the Cauchy-Schwarz inequality. Now, combining Equations 4, 5, and 6 allows us to write√√√√ M∑
m=1
‖(Θ′∗ −Θ∗)Webm‖22 ≤ 2(σprα + σrrβ)aM
cN (7)
which—by substitution into Equation 3—completes the proof.
Remark 4 Formulating the autoencoding component as an auxiliary task allows us to unambiguously interpret its benefit as a regularizer. Specifically, the complete loss can be summarized and rewritten as L(Θ) = Lp(Θ) +R1(Θ) +R2(Θ); that is, the TEA objective is a combination of the primary prediction loss Lp(Θ) = 1N ∑N n=1 `p(ΘWuxn,yn) plus additional regularization, where R1(Θ) = 1 N ∑M m=1 `r(ΘWebm,bm) = M N L B r (Θ) and R2(Θ) = 1 N ∑N n=1 `r(ΘWeyn,yn) − MN LBr (Θ). In particular, the proof of Theorem 1 relies on R1(Θ) to upper-bound instability (Appendix A). This precisely identifies the regularizer in question, while Theorem 1 quantifies its generalization benefit.
Remark 5 Technicality: Moving from uniform stability (Theorem 1) to generalization bounds (Corollary 1) requires that the loss function not take on arbitrarily large values (see e.g. Bousquet & Elisseeff (2002)). In practice, the label space itself is often bounded (see e.g. Assumption 1 in Le et al. (2018)); then the problem effectively reduces to that with a bounded loss function. For example, consider a regression setting using the quadratic loss function, where the target data lie within [−U,U ]; then the loss function is bounded to be within [0, 4U2]. See Castro & Nowak (2018). Remark 6 Technicality: Earlier we assumed ε = 0 for ease of exposition; carrying around the extra O(ε) term (from Equations 3 and 6) is not particularly illuminating. Generalizing to ε 6= 0 can be done in a similar manner to Le et al. (2018), with the additional assumptions of bounded spaces and that ε decreases as 1/N (which they note is reasonable, since the more samples in the data, the more likely the cross-representativity assumption will hold with low error). Again, note that ε = 0 holds as long as the number of independent latent vectors is at least |Z|). Similarly, Liu et al. (2016) consider ε = 0, noting in any case that they can increase N to obtain a small ‖η‖2; see their analysis for detail.

heading: B EXPANDED RELATED WORK
text: In this paper, we motivate and analyze a general autoencoder-based target-representation learning technique in the supervised setting, quantifying the generalization benefit via an argument from uniform stability, as well as verifying its practical utility. As such, our work lies at the intersection of three threads of research: (1) supervised representation learning using autoencoders, (2) label space reduction for multi-label classification, as well as (3) algorithmic stability-based learning guarantees.
B.1 Supervised Representation Learning using Autoencoders
Autoencoder-based representation learning (Hinton & Salakhutdinov, 2006) has long played important roles in unsupervised and semi-supervised settings. Various inductive biases have been proposed to promote representations that are sparse (Ranzato et al., 2007), discrete (van den Oord et al., 2017), factorized (Chen et al., 2018), or hierarchical (Zhao et al., 2017), among others. For a more thorough overview of various methods, we refer the reader to Bengio et al. (2013) and Tschannen et al. (2018).
The goal of better representations is often for the benefit of downstream tasks. Semi-supervised autoencoders—trained on partially-labeled data—can be jointly optimized to obtain compact representations that improve generalization on supervised tasks (Ranzato & Szummer, 2008; Weston et al., 2012). This naturally extends to representations that are generative (Kingma et al., 2014), disentangled (Narayanaswamy et al., 2017), or hierarchical (Rasmus et al., 2015). In addition, semi-supervised autoencoders enable transfer learning across different domains via jointly-trained reconstruction-classification networks Ghifary et al. (2016), private-shared partitioned representations (Bousmalis et al., 2016), or by augmenting models with label-encoding layers (Zhuang et al., 2015).
Although less studied, more closely related to our work is the use of autoencoders in a purely supervised setting: rather than focusing on how specific architectural novelties may better structure unlabeled data, Le et al. (2018) instead study the generalization benefit by the simple addition of reconstruction to the supervised classification task—a special case of what we describe as FEAs. Now, all aforementioned studies operate on the basis of autoencoding features (for an explicit or implicit downstream prediction task). In this paper, we instead focus on autoencoder-based target-representation learning (using TEAs) in the supervised setting, and—importantly—analyze the theoretical and empirical benefits of the approach. Unlike in simple classification (for which FEAs make sense), we are motivated by problems with high-dimensional output spaces, but where we operate under the assumption of a more compact and predictable set of underlying factors.
We take inspiration from the empirical investigation of Girdhar et al. (2016), where latent representations of 3D objects (targets) are jointly trained to be predictable from 2D images (features);
Oktay et al. (2017) deploy a similar approach for medical image segmentation. On the other hand, in both cases the supervised task is truncated: the predictors are trained to regress the unsupervised embeddings (instead of ground-truth targets), and gradients only backpropagate from the latent space (instead of the target space). This means that their common decoder function is only shared indirectly (and predictions made indirectly), versus the symmetric and simultaneously optimized forward model proposed for TEAs—an important distinction that our analysis relies on to obtain uniform stability. In Mostajabi et al. (2018), a two-stage procedure is used for semantic segmentation—loosely comparable to the first two stages in TEAs; in contrast to our emphasis on joint training, they study the benefit of a frozen embedding branch in parallel with direct prediction. More broadly related to target-embedding, Dalca et al. (2018) build anatomical priors for biomedical segmentation in unsupervised settings.
B.2 Label Space Reduction for Multi-Label Classification
Label space dimension reduction comprises techniques that focus specifically on multi-label classification. Early approaches to multi-label classification employ simplistic transformations such as label power-sets (Boutell et al., 2004), binary relevance (Tsoumakas et al., 2009), and label rankings (Fürnkranz et al., 2008); these are computationally inefficient, and do not capture interdependencies between labels. In contrast, label-embedding methods first derive a latent label space with reduced dimensionality, and subsequently associate inputs to that latent space instead. Encodings have been obtained via random projections (Hsu et al., 2009), principal components-based projections (Tai & Lin, 2010), canonical correlation analysis (Zhang & Schneider, 2011), as well as maximum-margin coding (Zhang & Schneider, 2012). A parallel thread of research has focused on selecting representative and reconstructive subsets of labels through group-sparse learning (Balasubramanian & Lebanon, 2012) and randomized sampling (Bi & Kwok, 2013). Various extensions of label-embedding techniques abound, such as using bloom filters (Cisse et al., 2013), nearest-neighbors (Bhatia et al., 2015), handling missing data (Wu et al., 2014), as well as using binary compression (Zhou et al., 2017).
Closer our theme of joint learning by utilizing both features and targets, Chen & Lin (2012) first proposed simultaneously minimizing the encoding error (from labels) and prediction error (from features) through an SVD formulation. Towards more flexible learning, Lin et al. (2014) did away with explicitly specified encoding functions, proposing to learn code matrices directly—making no assumptions whatsoever. Unifying several prior methods, Yu et al. (2014) cast label-embedding within the generic empirical risk minimization framework—as learning a linear model with a low-rank constraint; this perspective captures the generic intuition of a restricted number of latent factors, and admits generalization bounds based on norm-based regularization. Recently, Yeh et al. (2017) generalized the label-embedding approach to autoencoders; this formulation flexibly allows the
addition of specific losses to exploit correlations—a tactic also used in Wang et al. (2018) with multi-dimensional scaling. Furthermore, nonlinearities can be handled by deep learning in component functions, unlike earlier approaches limited to kernel methods (Lin et al., 2014; Li & Guo, 2015).
Our work is related to this general autoencoder approach to label-embedding, although there are significant differences in focus. In particular, we operate at a higher level of abstraction. Labelembedding techniques worry about label reduction, and about specific loss functions that aim to preserve dependencies within and among spaces; their problem is one of multi-label classification, and their baseline is binary relevance. In contrast, we worry about autoencoding at all—that is, we focus on the regularizing effect of the reconstruction loss on learning the prediction model; our baseline is direct prediction, and the output can be of any form (classification or regression). In light of the sizable performance improvement of the autoencoder-based model of Yeh et al. (2017) over comparators using direct prediction, our work can be regarded as a more generalized analysis of the contribution of the autoencoding component. Moreover, unlike the uniform convergence-based analysis in Yu et al. (2014), our bound does not rely on explicit norm-based regularization—instead, we interpret the embedding task itself as an intrinsic form of regularization to derive our stability-based guarantee.
Finally, also worth mentioning is the field of extreme multi-label classification (Bhatia et al., 2015), for which probabilistic methods such as Rai et al. (2015) and Kapoor et al. (2012) present sophisticated approaches to extremely high-dimensional classification problems—with advantages in performance and use cases. In light of the medical relevance of our experimental setting, we point out the application of Yan et al. (2010) to medical coding. See Bhatia et al. (2019) for a more detailed overview.
B.3 Algorithmic Stability and Learning Guarantees
Generalizability is central to machine learning, and its analysis via hypothesis stability is first studied in Rogers & Wagner (1978) and Devroye & Wagner (1979). Unlike arguments based on the complexity of the search space (Vapnik & Chervonenkis, 1971; Pollard, 1984; Koltchinskii, 2001), stability-based approaches account for how the model produced by the algorithm depends on the data. Based on concentration inequalities (McDiarmid, 1989), improved bounds are developed in Lugosi & Pawlak (1994) by estimating posterior error probabilities. The landmark work of Bousquet & Elisseeff (2002) first formalizes the notion of uniform stability sufficient for learnability, obtaining relatively strong bounds for several regularization algorithms, and Feldman & Vondrak (2018) recently use ideas related to differential privacy (Bassily et al., 2016) for further improved bounds without additional assumptions. For further context, see Mukherjee et al. (2006) and Shalev-Shwartz et al. (2010).
For semi-supervised representation learning, Rigollet (2007) first introduces the notion of cluster excess-risk and convergence, formalizing the clustering criterion for unlabeled features to be useful (Seeger, 2000). Based on the clustering assumption, Singh et al. (2009) develops a finite sample analysis to quantify the performance improvement from unlabeled features. Focusing on autoencoders,
Epstein & Meir (2019) adapt recent margin, norm, and compression-based results for deep networks (Bartlett et al., 2017; Neyshabur et al., 2017; Arora et al., 2018), and relate generalization of feature reconstructions to the benefit of additional unlabeled features for the primary classification task.
In the context of supervised problems, Mohri et al. (2015) and Gottlieb et al. (2016) analyze the generalization properties of dimensionality reduction techniques for features with respect to a downstream task; however, rather than joint training, the primary task is optimized subsequently over the learned representations. Taking a joint, multi-task approach (Caruana, 1997), Baxter (2000) first leverages the inductive bias of a common optimal hypothesis class to obtain a VC-based generalization bound. Maurer (2006) and Maurer et al. (2016) argue from Rademacher complexity to illustrate the benefit of the common operator; however, they only consider the task-averaged benefit, whereas we want to focus specifically on the primary task. There has been some work on generalization for each task (Ben-David & Schuller, 2003), but limited to binary classification—contrary to our setting.
Arguing from stability, our approach is related to Liu et al. (2016) in showing that the algorithm for learning the shared model in a multi-task setting is uniformly stable. Our analysis also resembles Le et al. (2018) in the more specific setting where the bound for the primary prediction task is obtained with assistance from the auxiliary reconstruction loss; unlike Liu et al. (2016), we are not interested in a generic bound for all tasks. Again, however, the fundamental (and motivating) difference of our work stems from the (inverted) problem setting and resulting framework. In the vast majority of works, the primary task is one of classification (or more generally |X | |Y|), where featureembeddings make sense to learn. Instead, we attend to the setting in which Y is high-dimensional (but where the underlying factors are assumed to be compact). In this setting, we argue (theoretically and empirically) that target-embeddings make more sense to learn in an auxiliary reconstruction task.

heading: C EXPANDED ALGORITHM DETAIL
text: In the following, Algorithm 1 gives pseudocode for TEA training. Figure 4 gives detailed block diagrams of component functions and objectives corresponding to each training stage (and variant).
Algorithm 1 Pseudocode for TEA Training
Input: D = {(xn,yn)}Nn=1 , learning rate ψ, minibatch size Ns Output: Parameters Θ,Wu,We of components θ, u, e
1: Initialize: Θ,Wu,We 2: while not converged do . Stage 1: Learn Target-Embedding 3: Sample {(xn,yn)}Nsn=1
i.i.d.∼ D 4: for n ∈ {1, ..., Ns} do 5: zn ← e(yn; We) . Encode 6: ỹn ← θ(zn; Θ) . Decode 7: end for 8: Lr ← 1Ns ∑Ns n=1`r(ỹn,yn)
9: We ←We − ψ∇WeLr 10: Θ← Θ− ψ∇ΘLr 11: end while 12: while not converged do . Stage 2: Regress Embeddings 13: Sample {(xn,yn)}Nsn=1
i.i.d.∼ D 14: for n ∈ {1, ..., Ns} do 15: ẑn ← u(xn; Wu) . Predict 16: zn ← e(yn; We) . Encode 17: end for 18: Lz ← 1Ns ∑Ns n=1`z(ẑn, zn) 19: Wu ←Wu − ψ∇WuLz 20: end while 21: while not converged do . Stage 3: Joint Training 22: Sample {(xn,yn)}Nsn=1 i.i.d.∼ D
23: for n ∈ {1, ..., Ns} do 24: ẑn ← u(xn; Wu) . Predict 25: zn ← e(yn; We) . Encode 26: ŷn ← θ(ẑn; Θ) . Decode 27: ỹn ← θ(zn; Θ) . Decode 28: end for 29: Lp ← 1Ns ∑Ns n=1`p(ŷn,xn)
30: Lr ← 1Ns ∑Ns n=1`r(ỹn,yn) 31: Wu ←Wu − ψ∇WuLp 32: We ←We − ψ∇WeLr 33: Θ← Θ− ψ∇Θ [Lp + Lr] 34: end while 35: return Θ,Wu,We

heading: D ADDITIONAL EXPERIMENT DETAIL
text: The UK Cystic Fibrosis registry records follow-up trajectories for over 10,000 patients over the period from 2008 and 2015 with a total of over 60,000 hospital visits. Each patient is associated with 90 variables over time, which includes data on treatments and diagnoses for 23 possible comorbidities (e.g. ABPA, diabetes, hypertension, pancreatitis), 11 possible infections (e.g. aspergillus, burkholderia cepacia, klebsiella pneumoniae), as well as static demographic information (e.g. gender, genetics, smoking status). Using both static and temporal information in a precedent window, we forecast the future trajectories for the diagnoses of infections and comorbidities (all binary variables) recorded at each follow-up. The Alzheimer’s Disease Neuroimaging Initiative study tracks disease progression for over 1,700 patients over the period from 2004 to 2016 with a total of over 10,000 (bi-annual)
clinical visits. We focus on the 8 primary quantitative biomarkers (e.g. entorhinal cortex, fusiform gyrus, hippocampus), 16 cognitive tests (e.g. ADAS11, CDR sum of boxes, mini mental state exam), as well as static demographic information (e.g. apolipoprotein E4, education level, ethnicity); we omit the remaining variables, for which the rate of missingness is over 50%. Using a precedent window, we forecast the future the evolution of the primary quantitative biomarkers and cognitive test results (all continuous variables) measured at each visit. The Medical Information Mart for Intensive Care records physiological data streams patients admitted to intensive care units after 2008. We use over 22,000 patients with a total of over 500,000 measurements (resampled at 4 hour intervals). We focus on the most frequently measured vital signs and lab tests (e.g. heart rate, oxygen saturation, respiratory rate) recorded over time (with categorical variables binarized, this gives a total of 361 variables), as well as static demographic information (e.g. admission type, gender, location, marital status); we omit the remaining variables, for which the rate of missingness is over 50%. Using a precedent window, we forecast the subsequent window of those variables. For each dataset, sequences are randomized at the patient level in order to obtain splits for training (and validation) and testing.
We implement all models using Tensorflow. For the linear model, each component (encoder, decoder, and predictor) consists of a single layer, no bias term, and linear activation; static (demographic) and temporal data are concatenated and flattened for both features and targets. For the nonlinear case, we implement each component as an RNN using GRUs with the number of hidden layers ζ ∈ {1, 2} where the number of hidden units is equal to the temporal feature dimension, and tanh is used for activation; the dimension of the latent space is (therefore) equal to the hidden state dimension. (For even larger hidden capacities, the increased number of parameters rapidly degrades performance). Static (demographic) information is incorporated as a mapping into the initial state for recurrent cells. Training is performed using the ADAM optimizer with a learning rate of ψ ∈ {3e−5, 3e−4, 3e−3, 3e−2}. Models are trained until convergence up to a maximum of 10,000 iterations with a minibatch size of Ns ∈ {32, 64, 128}; the empirical loss is computed on the validation set every 50 iterations of training, and convergence is determined on the basis of that error. Checkpointing is implemented every 50 iterations, and the best model parameters are restored (upon convergence) for use on the testing set. For all models except “Base”, we allow the opportunity to select among the `2-regularization coefficients ν ∈ {0, 3e−5, 3e−4, 3e−3, 3e−2}. We set the strength-of-prior coefficient λ = 0.5 for FEA, F/TEA, as well as all variants of TEA (however, we do provide sensitivities on λ for TEA in our experiments). For hyperparameter tuning (ζ, ψ, ν,Ns), we use cross-validation on the training set using 20 iterations of random search, selecting the setting that gives the lowest validation loss averaged across folds. For fair comparison (so as to isolate the effect of supervised representation learning over and above direct prediction), we apply the same setting chosen for REG for FEA, F/TEA, and all variants of TEA; therefore the only difference is the presence
or absence of each autoencoding component. For each model and dataset, the experiment is repeated for a total of 10 times (each with a different random split of data into training and held-out testing sets); all results are reported as means and standard errors of each performance metric across runs.

heading: E ADDITIONAL EXPERIMENT RESULTS
text: E.1 Results for Linear Models
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result.
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
3 0.733 ±0.008 0.750 ±0.008 0.750 ±0.007 0.744 ±0.007 0.750 ±0.008 4 0.725 ±0.007 0.744 ±0.005 0.740 ±0.008 0.734 ±0.006 0.740 ±0.007
ROC(C) 1 0.799 ±0.012 0.821 ±0.011 0.829 ±0.006 0.823 ±0.005 0.830 ±0.005 2 0.751 ±0.012 0.774 ±0.009 0.775 ±0.008 0.769 ±0.006 0.775 ±0.006 3 0.723 ±0.010 0.746 ±0.007 0.743 ±0.005 0.737 ±0.005 0.742 ±0.005 4 0.702 ±0.011 0.722 ±0.007 0.720 ±0.006 0.713 ±0.008 0.720 ±0.006
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining).
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
E.2 Results for Recurrent Models
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result.
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining).
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
8 0.453 ±0.058 0.455 ±0.054 0.454 ± 0.062 0.430 ±0.048 0.435 ±0.057
MSE evaluations reported separately for targets representing quantitative biomarkers (B) and cognitive tests (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result.
MSE evaluations reported separately for targets representing quantitative biomarkers (B) and cognitive tests (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
MSE evaluations reported separately for targets representing quantitative biomarkers (B) and cognitive tests (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining).
MSE evaluations reported separately for targets representing quantitative biomarkers (B) and cognitive tests (C). The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
2 0.701 ±0.044* 0.707 ±0.025* 0.705 ±0.050* 0.778 ±0.015 0.740 ±0.018* 3 0.690 ±0.041* 0.696 ±0.024* 0.693 ±0.046* 0.758 ±0.016 0.726 ±0.019* 4 0.681 ±0.038* 0.688 ±0.023* 0.684 ±0.042* 0.745 ±0.015 0.715 ±0.019* 5 0.679 ±0.037* 0.685 ±0.023* 0.680 ±0.043* 0.736 ±0.012 0.713 ±0.019*
MSE 1 0.141 ±0.007 0.140 ±0.006 0.138 ±0.010 0.137 ±0.008 0.139 ±0.007 2 0.159 ±0.010 0.159 ±0.007 0.160 ±0.008 0.154 ±0.009 0.162 ±0.007* 3 0.156 ±0.009 0.155 ±0.007 0.156 ±0.008 0.158 ±0.008 0.158 ±0.008 4 0.154 ±0.008 0.153 ±0.008 0.153 ±0.008 0.153 ±0.009 0.155 ±0.009 5 0.154 ±0.010 0.152 ±0.010 0.152 ±0.010 0.150 ±0.011 0.155 ±0.010
The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result.
The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining).
The "No Joint" setting isolates the benefit from staged training only (analogous to basic unsupervised pretraining, though using targets); the "No Staged" setting isolates the benefit from joint training only (without pretraining). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
E.3 Results for Sensitivities
The ν coefficient controls the strength of `2-regularization applied on top of the original loss function minimized. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C).
The ν coefficient controls the strength of `2-regularization applied on top of the original loss function minimized. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
The ν coefficient controls the strength of `2-regularization applied on top of the original loss function minimized. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C).
The ν coefficient controls the strength of `2-regularization applied on top of the original loss function minimized. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
The λ coefficient controls the strength of prior—i.e. the tradeoff between the prediction and reconstruction loss. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C).
The λ coefficient controls the strength of prior—i.e. the tradeoff between the prediction and reconstruction loss. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
3 0.521 ±0.026 0.549 ±0.037 0.590 ± 0.045 0.671 ±0.071 0.697 ±0.065 4 0.519 ±0.024 0.546 ±0.037 0.590 ± 0.039 0.669 ±0.068 0.696 ±0.063
ROC(C) 1 0.507 ±0.026 0.539 ±0.049 0.591 ± 0.054 0.702 ±0.101 0.741 ±0.088 2 0.520 ±0.024 0.546 ±0.040 0.587 ± 0.041 0.675 ±0.082 0.707 ±0.072 3 0.526 ±0.023 0.549 ±0.038 0.586 ± 0.036 0.659 ±0.070 0.686 ±0.061 4 0.528 ±0.027 0.550 ±0.039 0.581 ± 0.034 0.642 ±0.062 0.667 ±0.056
The proportion of data N used is randomly restricted, showing performance under various levels of data scarcity. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C).
The proportion of data N used is randomly restricted, showing performance under various levels of data scarcity. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
The proportion of data N used is randomly restricted, showing performance under various levels of data scarcity. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C).
The proportion of data N used is randomly restricted, showing performance under various levels of data scarcity. PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
E.4 Contrived Negative Example
Here with give a contrived example where the goals of prediction and reconstruction are directly at odds with each other. Specifically, we show a setup where the “and” part of “compact and predictable” representations is impossible—that is, a compact target-representation that is more reconstructive ends up being less predictable. Consider the following (true) data generating process: Latent variables p,u each consist of 10 independent dimensions, where pi ∼ N (0, 1) and ui ∼ N (0, 1). Feature vectors x are also of length 10, and are linear in p. Target vectors y = [y>P ,y > U ] > are of length 50, where yP is of length 10 and linear in p and yU is of length 40 and linear in u. See Figure 7. Note that the input features are inadequate for predicting all targets; our choice of lettering denotes elements that are in principle predictable (“P”), and those that are in principle unpredictable (“U”).
Suppose this data generating process is unknown to us. First, consider what happens with direct prediction: A linear model would learn to predict yP well, while predictions of yU would be no better than random. So far, so good. Now given the feature and target dimensions, consider the (not unreasonable) choice of TEAs with a latent dimension of 10. This is an obvious problem: During reconstruction, we naturally get more bang for our buck by encoding more of the (highly compressible) yU instead of yP; yet yU is entirely useless to encode, as it is not predictable from inputs anyway. Reconstructing well is therefore directly at odds with predicting well. This is certainly an extremely contrived scenario; nevertheless, without sufficient domain knowledge, it serves as a caveat that—as with feature-embedding paradigms—target-embedding is only as good as its assumptions.
MSE metrics are further reported separately for targets that are in principle predictable (P) and unpredictable (U).
MSE metrics are further reported separately for targets that are in principle predictable (P) and unpredictable (U).
E.5 Results from Open Discussion
One can also ask the (purely empirical) question of how much each model degrades on out-ofdistribution data—without additional training to fine-tune the model to the new data. In this context, we actually have no reason to expect TEAs to degrade any more or less than comparators. For thoroughness, we show an additional experiment as an example for sensitivity analysis (using UKCF) as follows: Each model is trained (only) on male patients and tested (only) on female patients, and vice versa. The average results on held-out samples from in-distribution data and out-of-distribution data then allow us to compute the net degradation (i.e. negative difference), which is reported below. While TEAs individually perform better overall on both in-distribution and out-of-distribution samples, none of the differences in the amounts of degradation between models are statistically significant:
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.
Finally, given the staged training in Algorithm 1, it should be clear that the order cannot be changed. Stage 2 requires the encoder to already be trained to provide the requisite embeddings, so it must be preceded by Stage 1. Therefore the only relevant possibilities are: (1) Stages 1-2 by themselves, without Stage 3; this is simply the “No Joint” setting. (2) Stage 3 by itself, without Stages 1-2; this is simply the “No Staged” setting. (3) None of the stages altogether; this is simply the “Neither” setting. (4) Stages 1, 2, and 3 in order; this is simply Algorithm 1 itself. The only remaining possibility is to have Stage 3 precede Stages 1-2. This makes little sense, since when the reconstruction loss is trained by itself it is likely to “undo” the result of joint training. For thoroughness, we run an additional sensitivity experiment (using UKCF) to confirm this. The following corresponds to the left half of Table 4, with the additional column on the right (and the other columns labeled to reflect the training stages). Verifying our intuitions, the setting “3-1-2” behaves almost identically to the setting “1-2”:
PRC and ROC evaluations are reported separately for targets representing infections (I) and comorbidities (C). The two-sample t-test for a difference in means is conducted on the results. An asterisk next to the comparator result is used to indicate a statistically significant difference in means (p-value < 0.05) relative to the TEA result. Results are grouped over the temporal axis; note that the variance between splits is an artifact of this grouping.

Review summaries:
1. Summary: In this paper, the authors proposed a Target-Embedding Autoendocer (TEA) model for supervised representation learning. Different from the traditional feature embedding autoencoder model, TEA tries to learn a compact latent representation that can reconstruct the target vector. Hypothetically, this model should be especially useful when the target vector has a much higher dimension than the feature vector. The authors analyzed the proved some characteristics of this framework and conducted empirical experiments on three datasets to prove its effectiveness.