Year: 2021

Abstract:
Conventional supervised learning typically assumes that the learning task can be solved by learning a single function since the data is sampled from a fixed distribution. However, this assumption is invalid in open-ended environments where no task-level data partitioning is available. In this paper, we present a novel supervised learning framework of learning from open-ended data, which is modeled as data implicitly sampled from multiple domains with the data in each domain obeying a domain-specific target function. Since different domains may possess distinct target functions, open-ended data inherently requires multiple functions to capture all its input-output relations, rendering training a single global model problematic. To address this issue, we devise an Open-ended Supervised Learning (OSL) framework, of which the key component is a subjective function that allocates the data among multiple candidate models to resolve the “conflict” between the data from different domains, exhibiting a natural hierarchy. We theoretically analyze the learnability and the generalization error of OSL, and empirically validate its efficacy in both open-ended regression and classification tasks.

text: Conventional supervised learning typically assumes that the learning task can be solved by learning a single function since the data is sampled from a fixed distribution. However, this assumption is invalid in open-ended environments where no task-level data partitioning is available. In this paper, we present a novel supervised learning framework of learning from open-ended data, which is modeled as data implicitly sampled from multiple domains with the data in each domain obeying a domain-specific target function. Since different domains may possess distinct target functions, open-ended data inherently requires multiple functions to capture all its input-output relations, rendering training a single global model problematic. To address this issue, we devise an Open-ended Supervised Learning (OSL) framework, of which the key component is a subjective function that allocates the data among multiple candidate models to resolve the “conflict” between the data from different domains, exhibiting a natural hierarchy. We theoretically analyze the learnability and the generalization error of OSL, and empirically validate its efficacy in both open-ended regression and classification tasks.

heading: 1 INTRODUCTION
text: A hallmark of general intelligence is the ability of handling open-ended environments, which roughly means complex, diverse environments with no manual task specification (Adams et al., 2012; Clune, 2019; Colas et al., 2019; Wang et al., 2020). Conventional supervised learning typically assumes that the learning task can be solved by approximating a single ground-truth target function (Vapnik, 2013). However, this assumption is invalid in open-ended environments where the data may implicitly belong to multiple, disparate domains with potentially different target functions since no manual task-level data partitioning is available. For instance, when collecting image-label pairs from the Internet, an image of a red sphere can correlate with the label of both “red” and “sphere”, implicitly representing two distinct domains or “metaconcepts” (Han et al., 2019): “color” and “shape”. While being generic, this setting also characterizes many practical scenarios where the data comes from multiple sources, contexts or groups: for example, in federated learning the data is distributed on multiple clients, and in algorithmic fairness research the data is from different populations. In these scenarios, the input-conditional label distribution may vary in different domains (also referred to as concept shift (Kairouz et al., 2021)) due to personal preferences or other latent factors, corresponding to different target functions.
Since different domains may possess different target functions, training a single global model by running Empirical Risk Minimization (ERM) using all data is problematic due to the potential “conflict” between the data from different domains: in the “red sphere” example above, directly training on all data will lead to the unfavorable result of “50% red, 50% sphere”. Similar phenomena have also been observed by prior works (Finn et al., 2019; Su et al., 2020), where a learner simultaneously regressing from multiple target functions trivially outputs their mean. This indicates that the data sampled from open-ended environments, which we refer to as open-ended data, exhibits a structural difference from conventional supervised data. Formally, we introduce a novel, dataset-level measure named mapping rank, which represents the minimal number of functions required to “fully express” all input-output relations in the data and can be used to expound such difference more clearly.
Definition 1 (Mapping rank). Let X be an input space, Y an output space, and Z = {(xi, yi)}li=1 a dataset with cardinality l. Let F (r) = {fi}ri=1 be a function set with cardinality r, where each element is a single-valued deterministic function fromX to Y . Then, the mapping rank ofZ, denoted
by R := R(Z), is defined as the minimal positive integer r, satisfying that there exists a function set F (r) such that for every (x, y) ∈ Z, there exists f ∈ F (r) with f(x) = y.
Note that here we assume that there exist deterministic relations between inputs and outputs in the same domain, which is generally a mild assumption and is satisfied in many practical applications. Under Definition 1, conventional supervised data yields a mapping rank R = 1 as it assumes that the whole dataset can be expressed by a single function. In contrast, open-ended data has a mapping rank R > 1 since for the same input different outputs exist, manifested as the conflict between data samples that renders training a single model problematic. Hence, it is natural to consider allocating the data to multiple models, so that the data processed by each model has a mapping rank R = 1 and thus can be handled with ERM. Although in some scenarios, apart from data samples there also exists side-information or metadata that can be exploited to identify the domains, this information may be difficult to define or collect in practice (Hanna et al., 2020; Creager et al., 2021); even when such side-information is available, in many cases it still remains unclear how to leverage such information to detect and resolve the potential conflict between domains. Therefore, the problem of how to properly allocate open-ended data among the models is highly non-trivial.
To tackle the aforementioned challenge, we present an Open-ended Supervised Learning (OSL) framework to enable effective learning from open-ended data. Concretely, OSL maintains a set of low-level models and a high-level subjective function that automatically allocates the data among these models so that the data processed by each model exhibits no conflict. The term “subjective” is used since in conventional supervised learning such allocation is manually performed during the data collecting process and thus conforms to human subjectivity. The motivation of such process is that if the subjective function yields an inappropriate allocation, i.e., assigning conflicting data samples to the same model, then it will hinder the global minimization of the training error due to the conflict, which in turn drives the subjective function to alter its allocation strategy. Using a probablistic reformulation of OSL, we establish the connection between the data allocation and the posterior maximization using a variant of Expectation-Maximization (EM) algorithm (Dempster et al., 1977), and show that the optimal form of the subjective function can be explicitly derived.
Theoretically, we respectively analyse the Probably Approximately Correct (PAC) learnability (Valiant, 1984) and the generalization error of OSL. Using the tools from statistical learning theory (Vapnik, 2013), we show that the relation between the number of low-level models and the mapping rank of data plays a key role in the learnability of OSL, and the generalization error of OSL can be decomposed into terms that respectively reflect high-level data allocation and lowlevel prediction errors. Empirically, we conduct extensive experiments including simulated openended regression and classification tasks to verify the efficacy of OSL. Our results show that OSL can effectively allocate and learn from open-ended data without additional human intervention. In summary, our contributions are three-fold:
Open-ended data and mapping rank. We formalize a new problem of learning from open-ended data, and introduce a novel measure termed as mapping rank to outline the structural difference between open-ended data and conventional supervised data.
OSL framework with theoretical guarantee. We present an OSL framework to enable effective learning from open-ended data (Section 2), and theoretically justify its learnability (Section 3.1) and generalizability (Section 3.2) respectively.
Empirical validation of efficacy. We conduct extensive experiments on both open-ended regression and classification tasks. Experimental results validate our theoretical claims and demonstrate the efficacy of OSL (Section 4).

heading: 2 OPEN-ENDED SUPERVISED LEARNING
text: In this section, we present the overall formulation and the algorithm of OSL. We adhere to the conventional terminology in supervised learning, and let X be an input space, Y an output space,H a hypothesis space where each hypothesis (model) is a function from X to Y , and ` : Y×Y → [0, 1] a non-negative and bounded loss function without loss of generality. We use [k] = {1, 2, · · · , k} for positive integers k, and denote by 1(·) the indicator function. We use superscripts to denote sampling indices (e.g., di and xij) and subscripts as element indices (e.g., di).

heading: 2.1 PROBLEM STATEMENT
text: We begin by introducing the notion of domain to formulate the generation process of open-ended data. Inspired by Ben-David et al. (2010), we define a domain d as a pair 〈P, c〉 consisting of a distribution P on X and a deterministic target function c : X → Y , and assume that the open-ended data is generated by a domain set D = {di}Ni=1 = {〈Pi, ci〉}Ni=1 containing N (agnostic to the learner) domains. Each domain has its own sub-dataset Zi = {(xij , yij)}lij=1 with cardinality li, where xi1, · · · , xili are i.i.d. drawn from Pi and yij = ci(xij) . The whole dataset is the union of these sub-datasets: Z = ⋃N i=1 Zi with cardinality l = ∑N i=1 li and mapping rank 1 < R ≤ N . We then consider a bilevel sampling procedure: first, m domain samples d1, · · · , dm are i.i.d. drawn from a distribution Q defined on D (the same domain may be sampled multiple times), resulting in m sampling episodes; second, in each sampling episode n data samples are i.i.d. drawn from the sub-dataset corresponding to the sampled domain. Hence, the dataset or any sub-datasets may be sampled multiple times during training. This sampling regime is analagous to the bilevel sampling process adopted by meta-learning. However, meta-learning usually assumes a dense distribution of related domains to enable task-level generalization (Pentina & Lampert, 2014; Amit & Meir, 2018), while OSL is compatible with scarce and disparate domains and inter-domain transfer is orthogonal.
As we have mentioned in Section 1, a single model is not sufficient in this setting whenR > 1. Thus, we equip the learner with a hypothesis set H = {hi}Ki=1 consisting ofK > 1 hypotheses, enhancing its expressive capability. Although both N and K are assumed to be unknown, we will show that in general K ≥ R suffices (Section 3.1), which eases the difficulty of setting the hyperparameter K. In the above setting, an episodic sample number parameter n is introduced to maintain the local consistency of data, implicitly assuming that we are able to sample a size-n data batch at a time from each domain. While this formulation subsumes the fully online case of n = 1, we note that although sometimes setting n = 1 works in practice, it also tends to be risky since it may raise difficulties in controlling the generalization error, as we will both theoretically and empirically demonstrate in the following sections (see Section 3.2 and Section 4.3).

heading: 2.2 GLOBAL ERROR
text: In this section, we present the global learning objective of OSL. Since the open-ended dataset implicitly contains multiple underlying input-output mapping relations, a primary start point can be the empirical multi-task loss with pre-defined data-domain correspondences:
êrMTL(H) = 1
m m∑ i=1 1 n n∑ j=1 ` [ hORACLE(i) ( xij ) , yij ] , (1)
where ORACLE : [m] → [K] is an oracle mapping function that determines which hypothesis each data batch Zi := {(xij , yij)}nj=1 in episode i is assigned to. However, in OSL the oracle mapping function is unavailable, imposing a fundamental discrepancy. To tackle this difficulty, here we substitute the oracle mapping function with a learnable empirical subjective function ĝ : HK × Xn × Yn → H that aims to select a hypothesis h from the hypothesis set H for the data batch Zi. This substitution yields the empirical global error of OSL:
êr(H) := 1
m m∑ i=1 1 n n∑ j=1 ` [ ĝ ( H,Zi ) ( xij ) , yij ] . (2)
Our insight is that the data batch itself can be harnessed to guide its suitable allocation in the presence of mapping conflict: intuitively, a single model trained by conflicting data batches result in an inevitable training error, thus hindering the minimization of the global error. This in turn facilitates data allocation with less conflict. Given the empirical error 2, the corresponding expected global error is er(H) := Edi∼QEx∼Pi` [g(H, di)(x), ci(x)] , (3) where g : HK ×D → H is an expected subjective function, which can be viewed as the empirical subjective function with infinite samples from every single domain so that all available domain information can be fully reflected by the data samples. The global objective 3 characterizes the scenario where the learner interacts with only one domain in a particular time period (which is natural in the real world), therefore its performance can be separately tested in all domains.
So far, our framework remains incomplete since the subjective function remain undefined. In the next section, we will present our design of the subjective function and elucidate its rationale.

heading: 2.3 DERIVATION OF SUBJECTIVE FUNCTION
text: To attain a reasonable choice of the subjective function, in this section we provide an alternative, probabilistic view of OSL from the angle of maximum conditional likelihood, and draw an intriguing connection between the choice of the subjective function and the posterior maximization using a variant of the EM algorithm (Dempster et al., 1977) on open-ended data. Concretely, let p(Y |X) represents the predictive conditional distribution of the hypothesis set H , where we use X and Y as the shorthand for (x11, x12, · · · , xmn) and (y11, y12, · · · , ymn) respectively. We consider maximizing the empirical log-likelihood log p(Y |X) = ∑m i=1 ∑n j=1 log ∑K k=1 p(y
ij , h = hk |xij) using EM, where h denotes the selected hypothesis. Accordingly, in the i-th sampling episode, in the E-step we aim to estimate the model posterior P (h = hk |Zi) that represents the responsibility of the k-th hypothesis in the hypothesis set w.r.t. the local data batch Zi = {(xij , yij)}nj=1, while in the M-step we seek to maximize
L(H) = K∑ k=1 P ( h = hk |Zi ) n∑ j=1 log [ πkp ( yij |xij , hk )] , (4)
where πk := P (h = hk) > 0 denotes the prior of the k-th hypothesis in H . This draws a direct connection between OSL and EM: the E-step corresponds to the functionality of the subjective function that chooses a hypothesis for a given data batch; the M-step corresponds to updating the selected hypothesis by minimizing the empirical prediction error in the episode. The main difference is that here we assume the subjective function to be deterministic, representing a “hard” assignment of the data to the model. This entails the usage of a variant known as hard EM (Samdani et al., 2012), which considers the posterior to be a Dirac delta function. Applying this constraint, the Estep of EM yields h = arg maxhk∈H ∑n j=1 log p(y
ij |xij , hk) under a uniform prior, motivating a principled choice of the subjective function:
ĝ ( H,Zi ) = arg min
h∈H n∑ j=1 ` [ h(xij), yij ] , i ∈ [m], (5a)
g(H, di) = arg min h∈H Ex∼Pi` [h(x), y] , i ∈ [N ], (5b)
which can be interpreted as selecting the hypothesis that incurs the smallest (empirical or expected) error. While this connection is not rigorous in general, in some cases exact equivalence can be obtained when certain types of loss functions and likelihood families are applied, which encompasses common regression and classification settings. We provide concrete analysis in Appendix A.

heading: 2.4 OVERALL ALGORITHM
text: In practice, we assume that the hypothesis set H comprises K parameterized hypotheses with parameter vectors Θ = (θ1, θ2, · · · , θK) respectively. In the high level, with the choice of the empirical subjective function 5a, our algorithm consists of two phases in each sampling episode: (i) evaluating the error of each hypothesis in H w.r.t. the data in this episode, and (ii) training the hypothesis with the smallest error. For brevity, we introduce a notion of empirical episodic error defined as
êri (h; θ) := 1
n n∑ j=1 ` [ h ( xij ; θi ) , yij ] , i ∈ [m], (6)
where h ∈ H is a hypothesis parameterized by θ. Then, phase (i) aims to find a hypothesis that mininize 6. Note that this selection process may induce a bias between empirical and expected objectives 2 and 3, since a hypothesis that minimizes the empirical loss on finite samples may not minimize the expected loss of this domain. Hence, the global error of OSL can be intuitively decomposed into a high-level subjective error that measures the reliability of the model selection, and a low-level model error that measures the accuracy of models, of which we provide detailed theoretical analysis in Section 3.2. In practice, we parameterize each hypothesis in the hypothesis set with a deep neural network (DNN), and apply stochastic gradient descent (SGD) for the optimization process. We provide the pseudo-code of OSL in Appendix B.

heading: 3 THEORETICAL ANALYSIS
text: In this section, we present the theoretical analysis on OSL. All proofs are deferred to Appendix C.

heading: 3.1 LEARNABILITY
text: We first analyze the learnability of OSL based on PAC learnability (Valiant, 1984). Since our analysis directly applys to conventional supervised learning by setting K = 1, we also verify the conflict phenomenon mentioned in Section 1 from a theoretical perspective. While the learnability in conventional PAC analysis mainly relates to the choice of the hypothesis space, open-ended data imposes a new source of complexity by its mapping rank, and we expect the cardinality of the proposed hypothesis set can compensate this complexity. We consider the realizable case where the hypothesis space covers the target functions in all domains, which helps to underline the core characteristic of our problem. We begin by a result on the form of the optimal solutions of OSL. Proposition 1 (Form of the optimal solutions). Assume that the target functions in all domains are realizable. Then, the following two propositions are equivalent:
(1) For all domain distributions Q and data distributions P1, P2, · · · , PN , er(H) = 0. (2) For each domain d = 〈P, c〉 in D, there exists h ∈ H such that Ex∼P ` [h(x), c(x)] = 0.
Proposition 1 suggests that minimizing the expected global error 3 with 5b elicits a global optimal solution where every target function is learned accurately in the realizable case. Note that this does not require N hypotheses for N domains, since non-conflict domains can be incorporated into the same model. In other words, what determines the minimal cardinality of the hypothesis set is not the number of the domains, but the number of conflicting domains, which can be exactly characterized by the mapping rank. Formally, we attain a necessary condition of the PAC learnability of OSL. Theorem 1 (Learnability). A necessary condition of the PAC learnability of OSL is K ≥ R.
Theorem 1 indicates that the cardinality of the hypothesis set should be large enough to enable effective learning, and shows the impact of mapping rank on the learnability of OSL. Remark 1. While it is generally hard to derive a necessary and sufficient condition of PAC learnability theoretically (which requires a sample-efficient optimization algorithm), we empirically find that K ≥ R is indeed an essential condition for learnability with complex hypothesis spaces (parameterized DNNs). We also note that several recent works (Allen-Zhu et al., 2019; Du et al., 2019) have proved that over-parameterized neural networks trained by SGD can achieve zero training error in polynomial time under non-convexity, which may also be used to enhance our analysis. We leave a more rigorous study for future work.

heading: 3.2 GENERALIZATION ERROR
text: We have shown that minimizing the expected global error is sufficient for effective learning from open-ended data. However, in practice, since we only have access to the empirical global error, how to control the discrepancy between these two errors, i.e., the generalization error, remains crucial. In this section, we identify the terms in the generalization error that respectively correspond to the high-level subjective error and the low-level model error of OSL, and discuss their controlling strategies. The key results are (i) the number of episodes and episodic samples can compensate each other in controlling the low-level model error, and (ii) the number of episodic samples is critical for controlling the high-level subjective error. We have the following theorem: Theorem 2 (Generalization error bound). For any δ ∈ (0, 1], the following inequality holds uniformly for all hypothesis sets H ∈ HK with probability at least 1− δ:
er(H) ≤ êr(H) + √
VC(S̄) (ln 2m/VC(S̄) + 1)− ln δ/12 m + 1 m (7a)
+ N∑ k=1 mk m √ VC(S) (ln 2mkn/VC(S) + 1)− ln δ/12N mkn + 1 mn  (7b) + 2 √ VC(S) (ln 2n/VC(S) + 1)− ln δ/24m
n +
2 n , (7c)
where S̄ := {〈P, c〉 7→ Ex∼P ` [h(x; θ), c(x)]}, θ ∈ Θ is the function set of the domain-wise expected error, S := {(x, y) 7→ ` [h(x; θ), y]}, θ ∈ Θ is the function set of the sample-wise error, mk :=∑m i=1 1 ( ci = ck ) is the sampling count of the target function from the k-th domain dk(k ∈ [N ]), and VC(·) the Vapnik-Chervonenkis (VC) dimension (Vapnik & Chervonenkis, 1971).
Theorem 2 indicates that the expected global error is bounded by the empirical global error plus three terms. The subjective estimation error term 7c is derived by bounding the discrepancy between the empirical and the expected subjective functions due to the limitation of finite episodic samples (detailed derivation is in Appendix C.3). This term can be controlled by the sample-level complexity term VC(S) and the number of episodic samples n, which certifies the necessity of the local consistency assumption in Section 2. Although in theory this error term converges to zero only if n → ∞, in practice we find that usually a very small n (e.g., n = 2) suffices (see Section 4). We posit that this is because the domains in our experiments are relatively diverse, thus reducing the difficulty of discriminating between different domains. The domain estimation error term 7a contains a domain-level complexity term VC(S̄), and converges to zero if the number of episodes reaches infinity (m → ∞); the instance estimation error term 7b contains sample-level complexity terms VC(S), and converges to zero if the sample number in each episode or the number of episodes reaches infinity (n→∞ or m→∞), showing the synergy between high-level domain samples and low-level data samples in controlling the model-wise generalization error.
Comparison with existing bounds. We compare our bound 7 with existing bounds of conventional supervised learning (Vapnik, 2013; McAllester, 1999) and meta-learning (Pentina & Lampert, 2014; Amit & Meir, 2018). Typically, supervised learning bounds contain a instance-level complexity term as 7b, and meta-learning bounds further contain a task-level complexity term as 7a. Yet, conventional supervised learning only considers a single domain or multiple known domains, while metalearning treats each episode as a new domain rather than domains that may have been encountered as in OSL. Thus, none of these bounds contains an explicit inference term as 7c. Remark 2. While our bound applies VC dimension as the complexity measure, extensions to other data-dependant complexity measures such as Rademacher and Gaussian complexities (Bartlett & Mendelson, 2002; Koltchinskii & Panchenko, 2000) is straightforward. It is worth noting that the bounds based on these measures share the same asymptotic property w.r.t. m and n as in the bound 7.

heading: 4 EXPERIMENTS
text: In this section, we report experimental results on two basic supervised learning tasks with openended data: regression and classification. Our experiments are designed to (i) validate our theoretical claims, (ii) assess the effectiveness of OSL, and (iii) compare OSL with task-specific baselines.

heading: 4.1 SETUP AND BASELINES
text: Open-ended regression. We consider an open-ended regression task in which data points are sampled from three heterogeneous functions with varied shapes, as shown in Figure 2a (solid lines). The details of this task are in Appendix D.
To the best of our knowledge, there is no off-the-shelf method that can automatically disentangle the data from different domains in the open-ended regression setting. The most relevant approach from our view is meta-learning that learns a global model which can be fastly fine-tuned to fit each domain (this is different from OSL, which assigns different models to conflicting domains explicitly). Hence, we compare OSL with three baselines. (1) Vanilla: a conventional ERM-based learner. (2) MAML (Finn et al., 2017): a popular gradient-based meta-learning approach. (3) Modular (Alet
(a) Vanilla (dashed) (b) MAML (c) Modular
(d) OSL (K = 2) (e) OSL (K = 3) (f) OSL (K = 4)
Figure 2: Results of OSL and the baselines on the openended regression task. (a) Ground-truth functions (solid) and the result of Vanilla (dashed). (b)(c) Results of MAML and Modular. (d)(e)(f) Results of OSL with different number of low-level models (solid). The dashed line in (f) indicates that OSL abandons a redundant model.
suber =0.1221 MSE=0.0666
(a) Smaller m
ersub=0.5314 MSE=0.5314
(b) Smaller n
(c) Subjective error of (b) (dashed)
Figure 3: Impact of sampling hyperparameters on OSL. (a) Fewer episodes (m = 50). (b) Fewer episodic samples (n = 1). (c) The subjective error when n = 1 (dashed lines represent incorrect data allocations).
et al., 2018): a modular meta-learning approach that extends MAML using multiple modules. We set the hyperparameters of OSL to K = 3,m = 250 and n = 2. To verify our theoretical results, we also run OSL with different number of hypotheses (K = 2 and K = 4) and different sampling hyperparameters (m = 50, n = 2 and m = 250, n = 1). More details are in Appendix D.
In addition, we demonstrate the effectiveness of OSL on a real-world multi-dimensional regression task; details and results are in Appendix E.1.
Open-ended classification. We consider two types of open-ended image recognition tasks where the same image may correspond to different labels in different sample pairs. We refer to these tasks according to the structure of their label spaces, namely parallel and hierarchical tasks. For parallel tasks, we derive the data respectively from Colored MNIST, a variant of MNIST where each digit is assigned with a digit label and a color label, and Fashion Product Images (Aggarwal, 2019), a multi-attribute clothes dataset that involves 3 main parallel tasks including gender, category and color classification, as shown in Figure 1a; we construct open-ended datasets by randomly choosing one label from the label set for each image. For the hierarchical task, we derive the data from CIFAR-100 (Krizhevsky & Hinton, 2009), a widely-used image recognition dataset comprising 100 classes with “fine” labels subsumed by 20 superclasses with “coarse” labels, as shown in Figure 1b; we construct the open-ended dataset by randomly using the fine or the coarse label for each image.
In classification, the most relevant problem setting to OSL is multi-label learning (Zhang & Zhou, 2014), which considers the scenario where an input x is related with a label set y = {yi}Ni=1. This setting is similar to OSL in terms that both OSL and multi-label learning considers the scenario where the same input may relate to multiple labels. However, the key difference is that multi-label learning requires that all labels in the label set are provided simaltaneously, while in OSL each data sample only contains one label yi ∈ y. Therefore, the setting of OSL can be alternatively modeled as “multi-label learning with missing labels”, i.e., in each sample N − 1 labels in y are missing and only one label remains (note that this is a very extreme setting). Hence, we compare OSL with the following baselines. (1) Probabilistic concepts (ProbCon): this baseline directly models the relation between inputs and outputs using an conditional probability distribution (Devroye et al., 1996). We adopt a single-model DNN to learn this probability distribution using the cross-entropy loss and choose top-N labels as the final prediction results. (2) Semi-supervised multi-label learning: this class of methods model open-ended classification as the problem of “multi-label learning with missing labels” (Yu et al., 2014; Bi & Kwok, 2014; Huang et al., 2019), i.e., only one label in each label set is available. We compare OSL with two representative semi-supervised methods: Pseudo-label (Pseudo-L) (Lee, 2013) and Label propagation (LabelProp) (Iscen et al., 2019). We also introduce two oracle baselines using additional information. (3) Full labels (Full-L): a standard multi-label learning method where we provide the full label set for each image, hence there is no missing labels. (4) Full tasks (Full-T): a standard multi-task learning method where the “task” of
each image is designated by human experts in advance to ensure that there is no conflict within each task. More details on baselines can be found in Appendix D.
To further demonstrate the applicability of OSL, we also conducted an experiment on Fashion Product Images with simulated concept shift between domains with the same label space; details and results are in Appendix E.2.

heading: 4.2 EVALUATION METRICS
text: Since the global error of OSL is related to the error of both the high-level subjective function and the low-level models, we respectively propose two metrics to quantitatively estimate these errors.
Subjective error. This metric measures the learner’s ability to perform appropriate data allocation. Given a domain d, a suitable subjective function should yield stable allocations for all data batches sampled from this domain. Thus, we measure the error of the subjective function using the rate of inconsistent data allocations, which we define as
SUBERR(d) = 1−max h∈H
1
ld ld∑ j=1 1 [ g ( H, zj ) = h ] , (8)
where ld denotes the total number of samples in domain d (the same below).
Model error. This metric measures the learner’s ability to make accurate in-domain predictions, which is analagous to traditional single-task error metrics. Given a domain d, it takes the form of
MODERR(d) = min h∈H
1
ld ld∑ j=1 e [h (xj) , yj ] , (9)
where we apply e(y, y′) = (y − y′)2 for regression and e(y, y′) = 1(y 6= y′) for classification.

heading: 4.3 EMPIRICAL RESULTS AND ANALYSES
text: Open-ended regression. We compare the performance of OSL and the baselines in Figure 2. Unsurprisingly, the vanilla baseline converges to a trivial mean function (dashed curve in Figure 2a). MAML successfully predicts the left part of all target functions by fine-tuning from episodic samples, but fails in the right part where functions exhibit larger difference. We hypothesis that it is because meta-learning typically requires tasks to be in sufficient numbers, and with more similarity. Although Modular currectly predicts the general trend of the curves, its predictions are still inaccurate in fine-grained details. Note that both meta-learning methods use more episodic data samples than OSL (see Appendix D.3.1). Meanwhile, OSL with K ≥ R (K = 3 or 4) successfully distinguishes different functions and recover each of them accurately while OSL with K < R (K = 2) fails, which matches our analysis
in Section 3.1. In particular, OSL with K = 4 automatically leaves one network to be redundant (dashed curve in Figure 2f), demonstrating the robustness of our algorithm.
Figure 3 illustrates the impact of sampling hyperparameters on OSL. Concretely, OSL with fewer sampling episodes m = 50 induces a large model error 9, which corresponds to the sample-wise estimation term in the generalization error 7b since the product mn is not sufficiently large. On the other hand, OSL with fewer episodic samples n = 1 induces a large subjective error 8, which corresponds to the subjective estimation term in the generalization error 7c. Another interesting phenomenon is that the curves in Figure 3b are partially swapped compared with the ground truth when n = 1, indicating wrong data allocation, which also corroborates our theory.
Open-ended classification. Table 1 shows the results of OSL and the baselines on open-ended classification tasks. On all tasks, OSL outperforms all baselines on both the subjective error and the model error. It is also worth noting that compared to the oracle Full-L with full label annotations, OSL still induces smaller subjective error, showing a strong capability of domain-level cognition that resembles the “ground truth” of human experts (Full-T). In addition, we visualize the features output by OSL on Fashion Product Images, as shown by Figure 4. The visualization shows that different models of OSL automatically focus on different label subspaces corresponding to different domains, which further complements our empirical results.

heading: 5 RELATED WORK
text: Apart from the formulation in this paper, open-ended data may also be formulated using the framework of multi-label learning with partial labels (Zhang & Zhou, 2014) or probabilistic density estimation, such as probabilistic concepts (Kearns & Schapire, 1994; Devroye et al., 1996) and the energy-based learning framework (LeCun et al., 2006). A fundamental difference between these formulations and OSL is that these methods learn a unified model, while our method explicitly encourages the learner to perform high-level data allocation and result in a set of independent models. A recent work by Su et al. (2020) studies a similar problem as ours where the goal of the learner is to learn from multi-task samples without task annotation. However, our work employs a different objective function and our method has formal theoretical justification.
Extensive literature has investigated the collaboration of multiple models (or modules) in completing one or more tasks (Doya et al., 2002; Shazeer et al., 2017; Meyerson & Miikkulainen, 2019; Alet et al., 2018; Nagabandi et al., 2019; Chen et al., 2020; Yang et al., 2020). The difference between our work and these works is that our multi-model architecture is driven by the inherent conflict in open-ended data without manual alignment between models and tasks, and we only allow a single low-level model to be invoked during a particular sampling episode.

heading: 6 DISCUSSION
text: An important open problem in machine learning is to move from highly specialized AI systems to agents with more general abilities. While various viewpoints exist, the notion of open-ended environments has been advocated by an increasing number of works (Goertzel & Pennachin, 2007; Clune, 2019; Silver et al., 2021). In this work, we attempt to formalize this notion in the context of supervised learning, and provide a general learning framework with theoretical guarantee. We hope that our work can facilitate future research in this direction.
Limitations and future work. As mentioned in Section 1, our formulation is limited to the fullyinformative data where absolute predictions can be made given the inputs. While this assumption is valid in a variety of applications, it is interesting to develop methods that can also handle data with stochasticity. Other future work includes developing lifelong learning agents that benefit from the growing diversity of open-ended data as the sampling process continuously proceeds, and extending our framework to other learning regimes, e.g., semi-supervised learning and reinforcement learning.

heading: ETHICS STATEMENT
text: This paper presents a new supervised learning framework which considers learning from the data directly sampled from open-ended environments such as the real world. Hence, our work may facilitate the development of more generally applicable artificial agents. Also, as mentioned in Section 1, our work has potential practical applications in federated learning and algorithmic fairness domains. Therefore, our work may promote the development of privacy-preserving and fair machine learning algorithms.

heading: REPRODUCIBILITY STATEMENT
text: For all theoretical results in this paper (Proposition 1, Theorem 1 and Theorem 2), we provide complete proofs in the appendix (see Appendix C). For the open-ended regression and classification experiments, we provide PyTorch implementations in the supplementary material; the code for the classification experiment on CIFAR-100 will be released if the paper is accepted since it requires additional pre-trained network backbones to run. The details of datasets, baselines and hyperparameters are provided in the appendix (see Appendix D).

heading: A DISCUSSION ON THE SUBJECTIVE FUNCTION
text: In Section 2.3, we derive our design of the subjective function using a EM-based maximum likelihood formulation. However, the exact equivalence between the E-step of hard EM and the subjective function has not been established, since it relies on the exact form of the loss function `(y, y′) and the conditional likelihood p(y|x, hk), k ∈ [K]. As a complement, in the sequel we provide two examples where under the uniform prior, the exact equivalence between calculating the posterior P (h = hk|x, y) and the expected subjective function 5b can be obtained (hence their empirical counterparts are also equivalent). Recall that under the uniform prior, the E-step of hard EM yields h = arg maxhk∈H log p(y|x, hk). Example 1 (Regression with isotropic Gaussian joint likelihood). Consider a regression task where we assume that given the random variable (x, y), the joint distribution of its conditional likelihoods conforms to an isotropic Gaussian N (µK , IK) where ∈ R+ is a variance parameter and IK is a K × K identity matrix. From p(y|x, hk) ∝ exp [ − (y−µk(x)) 2
2 2
] and µk(x) = hk(x) we have that
arg maxhk∈H p(y|x, hk) ⇔ arg minhk∈H [ (y − hk(x))2 ] . This equals to the expected subjective function with squared loss `(y, y′) = (y − y′)2. Example 2 (Classification with independent categorical likelihoods). Consider a multi-class classification task where we assume that given the random variable (x, y), all conditional likelihoods conform to independent categorical distributions with parameters (λ1,λ2, · · · ,λK), where λk = (λk1, · · · , λkL), ∑L j=1 λkj = 1, k ∈ [K] and L is the total number of classes. From
p(y|x, hk) = ∏L j=1 λkj(x) yj , where y = (y1, · · · , yL) ∈ {0, 1}L, ∑L j=1 yj = 1 and λk(x) =
hk(x) we have that arg maxhk∈H log p(y|x, hk) ⇔ arg minhk∈H [− ∑L j=1 yj log hkj(x)], where hkj(x) denotes the predicted probability of the j-th class and yj is the corresponding ground truth. This equals to the expected subjective function with cross-entropy loss `(y, y′) = − ∑L i=1 y ′ i log yi.

heading: B ALGORITHM PSEUDO-CODE
text: We provide the pseudo-code of OSL in Algorithm 1.

heading: C PROOFS OF THEORETICAL RESULTS
text: In this section, we provide the proofs of our theoretical results. For better exposition, we restate each theorem before its proof.

heading: C.1 PROOF OF PROPOSITION 1
text: Proposition 1 (Form of the optimal solution). Assume that the target functions in all domains are realizable. Then, the following two propositions are equivalent:
(1) For all domain distributions Q and data distributions P1, P2, · · · , PN , er(H) = 0.
(2) For each d = 〈P, c〉 in D, there exists h ∈ H such that Ex∼P ` [h(x), c(x)] = 0.
Proof. The derivation of proposition (1) from proposition (2) is obvious. On the other hand, if proposition (2) is false, i.e., there exists k ∈ [N ] such that for all j ∈ [K], hj 6= ck. Then, we have
er(H) = Eci∼Q min h∈H erPi (h, ci)
≥ q(ck) min h∈H erPk (h, ck)
From the above we know that ck /∈ H , thus there exists Pk such that erPk(h, ck) > 0 for every h ∈ H . This indicates that er(H) > 0, which is in contradiction with proposition (a). Therefore, proposition (2) must hold if proposition (1) is true.
Algorithm 1 OSL: Open-ended Supervised Learning Require: Hypothesis set H = {h1, h2, · · · , hK}, sampling hyperparameters m and n.
1: for h = 1, 2, · · · , T epochs do 2: for i = 1, 2, · · · ,m episodes do 3: Sample data Zi = {(xi1, yi1), (xi2, yi2), · · · , (xin, yin)}. 4: Select a hypothesis ĥi from the hypothesis set using the empirical subjective function 5a. 5: Train the hypothesis ĥi by minimizing the empirical episodic error 6. 6: end for 7: end for

heading: C.2 PROOF OF THEOREM 1
text: We first revisit the definition of PAC learnability.
Definition 2 (PAC learnability). A target function set class C is said to be PAC learnable if there exists an algorithmA such that for any > 0 and δ ∈ (0, 1], for all distributions Q and distribution set P , the following holds:
P [er(H) ≤ ] ≥ 1− δ. (10)

heading: A target function set class C is said to be PAC learnable if there exists an algorithm and a polynomial function poly(·, ·, ·, ·) such that for any > 0 and δ > 0, for all distributions Q and distribution set
text: P , the following holds for any sample size mn ≥ poly(1/ , 1/δ, size(c)) :
The above definition can be viewed as an extension of the single-task PAC learnability (Haussler, 1990) that considers the problem of learning a single target function. Based on this definition, in the following we give the proof.
Theorem 1. A necessary condition of the PAC learnability of OSL is K ≥ R.
Proof. According to Definition 2, if OSL is PAC learnable, there must exist an algorithm that outputs a hypothesis set H with zero error, i.e., er(H) = 0 for every Q and P (otherwise the inequality 10 will not hold for a small enough and δ < 1). Proposition 1 indicates that this is equivalent to ci ∈ H, i ∈ [N ], which is impossible if K < R according to Definition 1.

heading: C.3 PROOF OF THEOREM 2
text: We first introduce several technical lemmas.
Lemma 1. Let {Ei}ni=1 be a set of events satisfying P (Ei) ≥ 1 − δi, with some δi ≥ 0, i = 1, · · · , n. Then, P ( ⋂n i=1Ei) ≥ 1− ∑n i=1 δi.
Lemma 2 (Single-task generalization error bound (Vapnik, 2013)). Let A ≤ Q(z, α) ≤ B,α ∈ Λ be a measurable and bounded real-valued function set, of which the Vapnik-Chervonenkis (VC) dimension (Vapnik & Chervonenkis, 1971) is VC(Q). Let {z1, z2, · · · , zn}ni=1 be data samples sampled i.i.d. from a distribution P with size n. Then, for any δ ∈ (0, 1], the following inequality holds with probability at least 1− δ:∣∣∣∣∣Ez∼PQ(z, α)− 1n n∑ i=1 Q (zi, α)
∣∣∣∣∣ ≤ (B −A)√ (n) + 1n, (11) where
(n) = VC(Q) (ln 2n/VC(Q) + 1)− ln δ/4
n . (12)
Then, we upper bound the error induced by the estimation of the expected subjective function 5b in each sampling episode of OSL, which is critical in bounding the generalization error. Recall that we
use superscripts to denote the sampling index, e.g., di = 〈P i, ci〉 denotes the i-th domain sample, which can be any domains in the domain set D. We define two shorthands as follows:
h∗i := arg min h∈H
Ex∼P i` [ h(x), ci(x) ] , i ∈ [m], (13a)
ĥ∗i := arg min h∈H n∑ j=1 ` [ h ( xij ) , yij ] , i ∈ [m], (13b)
where i denotes the i-th sampling episode of OSL, H is the hypothesis set. Lemma 3 (Subjective estimation error bound). Let {( xi1, yi1 ) , · · · , ( xin, yin )} be episodic sam-
ples in the i-th (i ∈ [m]) sampling episode i.i.d. drawn from domain di with size n. Then, for any δ ∈ (0, 1], the following inequality holds uniformly for all hypothesis h ∈ H with probability at least 1− δ:
1
m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ ĥ∗i ( xij ) , yij ] ≤ 2 √
VC(S)(ln 2n/VC(S) + 1)− ln δ/8m n + 2 n ,
(14)
where S := {(x, y) 7→ ` [h(x; θ), y]}, θ ∈ Θ is the function set of the sample-wise error.
Proof. We have the following decomposition:
1
m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ ĥ∗i ( xij ) , yij ]
= 1
m m∑ i=1  1n n∑ j=1 ` [ h∗i ( xij ) , yij ] − Ex∼P i` [ h∗i (x), c i(x) ]
+ 1
m m∑ i=1 { Ex∼P i` [ h∗i (x), c i(x) ] − Ex∼P i` [ ĥ∗i (x), c i(x) ]}
+ 1
m m∑ i=1 Ex∼P i` [ĥ∗i (x), ci(x)]− 1n n∑ j=1 ` [ ĥ∗i ( xij ) , yij ] , in which the original difference is decomposed into three terms. By definition 13a and 13b the middle term is non-positive. Using Lemma 2 by substituting Q with S = {(x, y) 7→ ` [h(x; θ), y]} and replacing δ with δ/2m, the first term and the last term can both be bounded by√
VC(S) ln (2n/VC(S) + 1)− ln δ/8m n + 1 n with probability at least 1− δ/2 (Lemma 1). Combining
these two bounds using Lemma 1 completes the proof.
Now we can give the proof of the main theorem. Theorem 2 (Generalization error bound of OSL). For any δ ∈ (0, 1], the following inequality holds uniformly for all hypothesis sets H ∈ HK with probability at least 1− δ:
er(H) ≤ êr(H) + √
VC(S̄) (ln 2m/VC(S̄) + 1)− ln δ/12 m + 1 m (15a)
+ N∑ k=1 mk m √ VC(S) (ln 2mkn/VC(S) + 1)− ln δ/12N mkn + 1 mn  (15b) + 2 √ VC(S) (ln 2n/VC(S) + 1)− ln δ/24m
n +
2 n , (15c)
where S̄ := {〈P, c〉 7→ Ex∼P ` [h(x; θ), c(x)]}, θ ∈ Θ is the function set of the domain-wise expected error, S := {(x, y) 7→ ` [h(x; θ), y]}, θ ∈ Θ is the function set of the sample-wise error, mk :=
∑m i=1 1 ( ci = ck ) is the sampling count of the target function from the k-th domain dk(k ∈ [N ]), and VC(·) the Vapnik-Chervonenkis (VC) dimension (Vapnik & Chervonenkis, 1971).
Proof. Combining the objectives 2 3 with the subjective function 5a 5b, we have the following decomposition:
er(H)− êr(H) = { Edi∼Q min
h∈H Ex∼Pi` [h(x), ci(x)]−
1
m m∑ i=1 min h∈H Ex∼P i` [ h(x), ci(x)
]}
+  1m m∑ i=1 min h∈H Ex∼P i` [ h(x), ci(x) ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] +
 1m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] − 1 m m∑ i=1 min h∈H 1 n n∑ j=1 ` [ h ( xij ) , yij ] . By definition 13a and 13b we rewrite the equation above:
er(H)− êr(H) = { Edi∼QEx∼Pi` [h∗i (x), ci(x)]− 1
m m∑ i=1 Ex∼P i` [ h∗i (x), c
i(x) ]}
+  1m m∑ i=1 Ex∼P i` [ h∗i (x), c i(x) ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] +
 1m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ ĥ∗i ( xij ) , yij ] , in which the generalization error of OSL is decomposed into three terms. By substituting Q in Lemma 2 by S̄ = {〈P, c〉 7→ Ex∼P ` [h(x; θ), c(x)]} and replacing δ with δ/3, the first term can be
bounded by
√ VC(S̄) ln (2m/VC(S̄) + 1)− ln δ/12
m +
1 m with probability at least 1−δ/3. By replacing
δ with δ/3 in Lemma 3 we bound the last term by 2
√ VC(S)(ln 2n/VC(S) + 1)− ln δ/24m
n +
2 n with
probability at least 1− δ/3. There remains the middle term for which we have
1
m m∑ i=1 Ex∼P i` [ h∗i (x), c i(x) ] − 1 m m∑ i=1 1 n n∑ j=1 ` [ h∗i ( xij ) , yij ]
= 1
m m∑ i=1 Ex∼P i` [h∗i (x), ci(x)]− 1n n∑ j=1 ` [ h∗i ( xij ) , yij ] = 1
m N∑ k=1 mkEx∼Pk` [h∗k(x), ck(x)]− 1n nmk∑ j=1 ` [h∗k (xkj , ykj)]  = 1
m N∑ k=1 mk Ex∼Pk` [h∗k(x), ck(x)]− 1nmk nmk∑ j=1 ` [h∗k (xkj , ykj)]  . Recall that mk := ∑m i=1 1 ( ci = ck ) . In the above we re-arrange the total m data batches according to the domains they belong to. With a little abuse of notation, in the third and fourth rows we use h∗k to denote the hypothesis that yields the smallest expected error in the k-th domain in D, i.e., h∗k = arg minh∈H Ex∼Pk` [h(x), ck(x)] , k ∈ [N ]. Note that this is different from the definition 13a, where h∗i is defined upon the i-th domain sample. The above transformation aggregates the domain samples so that data samples from the same domains that emerge multiple times can be accumulated and jointly considered, which leads to a tighter and more realistic error bound. By Lemma 2, for every k ∈ [N ] and δ ∈ (0, 1], each inside term Ex∼Pk` [h∗k(x), ck(x)] −
1
nmk
∑nmk j=1 ` [h ∗ k (xkj , ykj)] can be bounded by
√ VC(S) (ln 2mkn/VC(S) + 1)− ln δ/12N
mkn +
1
mkn with probability at least 1 − δ. By replacing δ with δ/3N we bound the whole second term
by ∑N k=1 ( mk m √ VC(S) (ln 2mkn/VC(S) + 1)− ln δ/12N mkn + 1 mn ) with probability at least 1 − δ/3 (Lemma 1).
Finally, combining the above bounds for all three terms using Lemma 1 gives the result.

heading: D EXPERIMENT DETAILS
text: In this section, additional details on the setup and settings of the experiment are provided. All experiments were conducted based on PyTorch (Paszke et al., 2019) using a NVIDIA 2080ti GPU. All data we used does not contain personally identifiable information or offensive content, and can be obtained from public data sources.

heading: D.1 REGRESSION
text: We consider three heterogeneous mapping functions in absolute, sinusoidal and logarithmic function families as below:
y = 2 |x| − 2, y = 2 sin ( 3x+ π
2
) ,
y = 3
2 log
( −x+ 5
2
) − 1,
where the range of x is [−2, 2] for all three functions, yielding the open-ended data withR = 3. The sample hyperparameters are m = 250, n = 2, i.e., a total number of 500 data points are collected in 250 episodes, each with 2 samples in the data batch, and their underlying generation functions are randomly chosen from the three mapping functions.
Network and optimizer. A simple network architecture with 5 fully-connected linear layers, each with 32 hidden units, is adopted and trained with SGD with step size α = 0.05, momentum = 0.9, and `2 weight decay = 10−4.

heading: D.2 CLASSIFICATION
text: Colored MNIST is an extended version of the well-known character recognition dataset MNIST, in which each gray-scale digital images are randomly colored with 8 different colors. The dataset contains two parallel tasks of color and number classification (R = 2) with a total number of 60000 colored digits. The sample hyperparameters are m = 60000, n = 1.
Fashion Product Images (Aggarwal, 2019) is a dataset for automatic attribute completion and Q&A of clothing product images with multiple category labels in different domains. We choose 3 main parallel tasks (color, gender, category) with 8 main labels from the original dataset (R = 3), with 15000 images in total. The sampling hyperparameters are m = 15000, n = 1.
CIFAR-100 (Krizhevsky & Hinton, 2009) is a classical benchmark for general image classification. It has a hierarchical structure with 20 superclasses and 100 classes, with 60000 images in total. Each superclass is from an upper-level “coarse” task, consisting of 5 “fine” classes, e.g., “insects” includes “bee, beetle, butterfly, caterpillar, cockroach”. In our experiments, these two different kinds of labels are randomly provided given an image (R = 2). The sampling hyperparameters are m = 30000, n = 2.
Network and optimizer. In Colored MNIST, each network consists of 3 convolutional layers and 1 fully-connected layer. In Fashion Product Images, each network consists of 5 convolutional layers and 3 fully-connected layers. We use Adam optimizer (Kingma & Ba, 2015) with step size α = 0.002 and betas = (0.5, 0.999) for these two datasets. In CIFAR-100, for OSL and all baselines, we use a pre-trained DenseNet (Huang et al., 2017) backbone of DenseNet-L190-k40 for
feature extraction to ensure a fair comparison, and add 2 fully-connected layers after the DenseNet backbone. We use SGD as the optimizer with step size α = 0.1 and momentum = 0.9.

heading: D.3 BASELINE DETAILS
text: In this section, we provide more details on the baselines.

heading: D.3.1 REGRESSION
text: MAML. For MAML, we adapt a standard PyTorch implememtation from GitHub1 with the same network with ours, and use the following hyperparameters:
Shot = 2, Evalation = 100, Outer step size = 0.05, Inner step size = 0.015, Inner grad steps = 2, Eval grad steps = 5, Eval iters = 10, Iterations = 20000.
Modular. For modular meta-learning, we use the official PyTorch implementation from GitHub2, and use the following hyperparameters:

heading: Shot = 2, Support = 2, Network = Linear 1− 16− 16− 1, Num modules = 5,
text: Composer = Sum,meta lr = 0.003, Steps = 3000.
Note that for Modular Meta-Learning a larger episodic sample number n = 4 (consisting of 2 support samples and 2 query samples) is adopted. Nevertheless, OSL still outperforms this approach using a smaller episodic sample number (n = 2).

heading: D.3.2 CLASSIFICATION
text: Probablistic concepts. From the perspective of probability modeling, the relation between input x and output y is subject to a probability distribution p(y |x), which is the learning target. In openended classification, when different domains share similar frequency, such a distribution can be approximated with the total probability formula:
p(y |x) = ∑ h∈H p(y |x, h) · p(h) ≈ 1 ld ∑ h∈H p(y |x, h)
For classification problems, in each domain d, the corresponding p(y |x, h) is unimodal. Thus, their sum p(y |x) is a multi-modal distribution, and a network trained with cross-entropy loss is still an unbiased estimation for it. The final prediction is the labels with top-N conditional probabilities p(y |x). Semi-supervised multi-label learning. From the perspective of semi-supervised multi-label learning, the open-ended classification problem can be modeled as “multi-label learning with missing labels”: consider the fully labeled data x→ y = {yi}Ni=1, then, open-ended data provides only one label y ∈ Y for each x, i.e., all other labels are missing. Therefore, existing semi-supervised learning approaches may be modified to handle such problems. We consider two representative techniques, including Pseudo-label and Label propagation. Both implementations are slightly modified to fit our tasks.
Pseudo-label randomly allocates additional ”pseudo” labels to each input to compensate the missing labels. The learning machine is trained on the augmented dataset and then reevaluate the confidence of all pseudo labels according to its predictions, and all pseudo labels will iteratively be modified during training until convergence.
Label propagation builds a graph over the samples, where each node on the graph represents a data sample, and each edge represents the distance of two nodes it collects in the feature space. The labels are propagated on adjacent nodes until all samples are fully labeled. The feature space is also iteratively adjusted along during training.
Full labels & full tasks. Both these oracle baselines utilize manual annotations to tranform the open-ended data with R > 1 to conventional supervised data with R = 1. More concretely, for Full
1https://github.com/dragen1860/MAML-Pytorch (MIT license) 2https://github.com/FerranAlet/modular-metalearning (MIT license)
labels, label annotations from all domains are provided simultaneously as a “multi-hot” label vector for each input sample, resulting in a standard multi-label learning problem. For Full tasks, raw data is separated into single-class classification tasks according to additional manual task annotation, resulting in a standard multi-task learning problem.

heading: D.3.3 MEASURING THE SUBJECTIVE ERROR OF BASELINES IN CLASSIFICATION
text: Since the baselines in classification experiments do not explicitly assign a separate model to each domain, the subjective error metric 8 does not directly apply to these baselines. Hence, we estimate their subjective errors using another method: we directly select top-N predictions of these methods and compare them with the label spaces of different domains. We define the “coverage” of the selected top-N labels over domain d as
COVERAGE(d) = 1
ld ld∑ i=1 1(∃ top-N labels for input xi that is in the label space of d),
where ld denotes the total number of samples in domain d. The subjective error on d is then calculated as 1− COVERAGE(d).

heading: E ADDITIONAL EXPERIMENTAL RESULTS AND VISUALIZATIONS
text: In this section, we provide additional experimental results and visualizations.

heading: E.1 MULTI-DIMENSIONAL OPEN-ENDED REGRESSION
text: To further demonstrate the efficacy of OSL in regression problems, we conducted experiments on a real-world multidimensional regression dataset from UCI machine learning repository: Gas sensor array under dynamic gas mixtures dataset (Fonollosa et al., 2015). This dataset contains the recordings of 16 chemical sensors exposed to two dynamic gas mixtures and the aim is to predict the concentrations of gases, with 417,8504 instances and 16-dimensional attributes. We treat each gas mixture as one domain, respectively representing Ethylene & Methane (domain 1) and Ethylene & CO (domain 2) gas mixtures, and randomly split both domains into training (90%) and test sets (10%).
In this task, we compare OSL (two models, trained on the union of both domains) with a vanilla single model regressor (trained on the union of both domains) and an oracle regressor with two models separately trained on each domain. We report root mean square error (RMSE) on each domain and the macro-average RMSE over both domains in Table 2. The results indicate that OSL benefits from its automatic data allocation process, surpassing the vanilla baseline that trains a single global model by a large margin and performs similarly with the oracle.

heading: E.2 SIMULATED CONCEPT SHIFT CLASSIFICATION
text: To further demonstrate the applicability of OSL, we conducted an experiment on Fashion Product Images with simulated concept shift between domains with the same label spaces. Concretely, we
randomly split the dataset into two domains according to the “gender” attribute: 50% of samples labeled as “Male” and 50% samples labeled as “Female” are assigned to domain 1 with “Male” relabeled as “1” and “Female” relabeled as “0”, and other samples are assigned to domain 2 with “Male” relabeled as “0” and “Female” relabeled as “1”. As shown in Figure 5, this setting resembles a simple scenario of concept shift caused by human preference: the label “1” can be interpreted as an indicator of “interested” or “recommended”, while the label “0” can be interpreted as an indicator of “not interested” or “not recommended”. Since different people may have different preferences (in this simulated experiment this is caused by gender – domain 1 and domain 2 respectively represents appropriate recommendations to male and female users), the data samples from different domains may possess different input-label conditional probability P (y |x), albeit with the same label space. Since the label space is binary and completely shared by both domains, multi-label baselines are inapplicable in this setting since they will always produce both labels “0” and “1” for every input and do not discriminate between different domains, which is unmeaningful. Therefore, we compare OSL with the single-model baseline (vanilla) and an oracle (Full-T) which separately train two models on both domains explicitly with data-domain correspondences known in advance. We report the model error and the subjective error of OSL in Table 3. Results show that the vanilla single-model baseline cannot learn meaningful prediction results since it lacks the mechanism to distinguish conflicting samples from different domains, while OSL achieves relatively small subjective errors and similar model errors as the Full-T oracle, which demonstrate that OSL is effective even in the context where different domains possess exactly the same label spaces yet different input-label relations.

heading: E.3 TRAINING AND INFERENCE TIME ON FASHION PRODUCT IMAGES
text: In Table 4, we compare the computational cost of OSL and other baselines in terms of training and inference time on the Fashion Product Images dataset. We measure the required wall-clock time (in seconds) for each method to reach convergence during training as well as the averaged wallclock time for each method to predict all labels of one given input (in milliseconds). Concretely, for OSL and all baselines except for two oracles (Full-L and Full-T), we train the models for 50 epochs with about 15,000 images in every epoch; for Full-L and Full-T, we train for 10 epochs since these methods generally converge faster. For each method, we test its total inference time on the same 3,000 test samples randomly sampled from the test set and report the mean inference time on each test sample. All results are obtained with PyTorch using a NVIDIA 2080ti GPU.
As shown in the table, the time cost of OSL is generally on par with or lower than baselines that also involve iterative training (Pseudo-L and LabelProp). Although the ProbCon baseline trains faster, it learns a global model without the mechanism of data allocation and thus performs significantly worse than OSL as we have shown. Meanwhile, compared with the Full-T oracle that knows the data-domain correspondences in advance, OSL only exhibits a little additional computational overhead. This indicates that although OSL incorporates an extra data allocation process implemented by the subjective function, this process only induces a limited computational cost since it only requires additional network forward process without loss backpropagation, which is in general efficient.
E.4 ITERATION PROCESS ON THE REGRESSION TASK
In OSL, since the performance of the low-level models will impact the data allocation process of the high-level subjective function, the training of the subjective function and low-level networks can be regarded as an iterative process, as shown by Figure 6 with an example in open-ended regression, in which the different colored lines are designated to different subjects. All networks are randomly initialized, and in each iteration, each sample may be reallocated by the subjective function and used to further train the low-level networks. With the increasing of iterations, both subjective and model errors will reduce and converge along with the global loss. The last subfigure displays the final decision boundary of subjective function.

heading: E.5 FEATURE VISUALIZATION ON THE CLASSIFICATION TASK
text: The OSL approach can extract different semantics from the same input sample, and map them to different feature spaces. Figure 7 displays the features output under all subjectives, where each color represents a subjective and each point corresponds to an image in the dataset.

heading: F MORE DISCUSSION ON RELATED WORK
text: In this section, we provide more discussion on related work.
Ensemble learning. Ensemble learning approaches typically employ multiple models to cooperatively solve a given task (Dietterich, 2002; Zhang & Ma, 2012; Sagi & Rokach, 2018; Zhou, 2021). The prediction of each model is combined by weighting (boosting), majority voting (bagging) or
learning a second-level meta-learner (stacking). Since different models process the same set of data (although sometimes with different sample weights), in ensemble learning there is typically no explicit “hard” allocation process between the data and models. In contrast, the multi-model architecture of OSL is driven by the inherent conflict in open-ended data, and each model only handles a proportion of the whole dataset without overlapping.
Domain adaptation and domain generalization. Domain adaptation (Ben-David et al., 2010; Pan & Yang, 2010; Tan et al., 2018; Wang & Deng, 2018; Hoffman et al., 2018) and domain generalization (Blanchard et al., 2011; Muandet et al., 2013; Zhou et al., 2021) consider the scenario where the learner trained on one or multiple source domain(s) is transferred to one or multiple new target domain(s). Typically, domain adaptation focuses on the problem where there exist some labeled or unlabeled instances in the new domain, while domain generalization considers the setting where there the information of the new domains is inaccessible during training (i.e., zero-shot generalization). In other words, these formulations focus on the adaptation or generalization capability of the model on target domain(s). In contrast, OSL focuses on the multi-domain training process and considers the scenario where directly training a global model using the data from multiple conflicting domains is problematic, and aims to resolve this training issue by performing automatic data allocation. Another important difference is that in domain adaptation and domain generalization the data-domain correspondences are available, while OSL weakens this assumption by only assuming that the data from each sampling episode is obtained from the same domain.

Review summaries:
The paper introduces "Open-ended Supervised Learning (OSL)", a method that handles data form multiple domains (open-ended data). OSL leverages an Expectation-Maximization (EM) algorithm to train the "subjective function" that allocates models to data domains. The paper presents the theoretical foundations and empirical results in which it outperforms existing baselines for (generated) regression and classification tasks.

This paper proposes a framework for open-ended data by learning a subjective functions that allows to represent multiple domains without interference. The framework works in two stages: 1) evaluating a set of candidate hypotheses for each domain using a batch of data for that domain, 2) training the hypothesis with the smallest error  for each domain. The paper also proposes two new evaluation metrics, one to determine the error of the subjective function and one for calculating the model error in domain prediction. The authors provide both theoretical and experimental analyses of the proposed framework. In terms of theoretical analyses, the authors provide some guarantees in terms of learnability and generalisation error. In terms of experimental results, the authors test both regression and classification tasks with data of multiple labels and hierarchical labels. Comparisons to other approaches such as ProbCon, Pseudo-L and LabelProp in Colored MNIST, CIFAR-100 and Fashion Product Images datasets demonstrate gains of the proposed approach versus counterparts. 

The authors present a novel framework for learning different target concepts. They argue that so far, a single classifier is supposed to learn mixed concepts but usually fail. Hence, they propose a framework for sampling instances according to only a single target concept and solving this problem with classical ERM and repeating for other concepts. They provide theoretical analyses and empirical insights.