--- title: "Boosted Zero-Shot Learning with Semantic Correlation Regularization" authors: - "Te Pi" - "Xi Li" - "Zhongfei (Mark) Zhang" doi: "10.24963/ijcai.2017/362" url: "https://ijcai.org/proceedings/2017/362" pdf: "https://ijcai.org/proceedings/2017/0362.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "2599-2605" track: "Main track" keywords: - "Machine Learning: Transfer, Adaptation, Multi-task Learning" - "Machine Learning: Ensemble Methods" - "Machine Learning: Classification" --- # Boosted Zero-Shot Learning with Semantic Correlation Regularization Te Pi, Xi Li, Zhongfei (Mark) Zhang *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 2599-2605. DOI: [10.24963/ijcai.2017/362](https://doi.org/10.24963/ijcai.2017/362) ## Abstract We study zero-shot learning (ZSL) as a transfer learning problem, and focus on the two key aspects of ZSL, model effectiveness and model adaptation. For effective modeling, we adopt the boosting strategy to learn a zero-shot classifier from weak models to a strong model. For adaptable knowledge transfer, we devise a Semantic Correlation Regularization (SCR) approach to regularize the boosted model to be consistent with the inter-class semantic correlations. With SCR embedded in the boosting objective, and with a self-controlled sample selection for learning robustness, we propose a unified framework, Boosted Zero-shot classification with Semantic Correlation Regularization (BZ-SCR). By balancing the SCR-regularized boosted model selection and the self-controlled sample selection, BZ-SCR is capable of capturing both discriminative and adaptable feature-to-class semantic alignments, while ensuring the reliability and adaptability of the learned samples. The experiments on two ZSL datasets show the superiority of BZ-SCR over the state-of-the-arts. ## Full text ## 1 Introduction Recent years have witnessed a widespread increase of interest in Zero-Shot Learning (ZSL), which aims at learning a classifier from the data of the seen classes YS for classifying the data from the unseen target classes YT . A common solution of ZSL is to introduce some auxiliary information on labels (e.g., attributes [Akata et al., 2013], word vector representations [Frome et al., 2013]) to model the semantic relationships between YS and YT in a common structured embedding space. Hence, ZSL is typically solved as a transfer learning problem, which seeks to exploit the shared knowledge among classes and transfer these knowledge to adapt on YT . From the perspective of transfer learning, a zero-shot classifier is expected to be both discriminative for the data distribution of YS and with robust adaptation to the data distribution of YT . Therefore, the classifier should not only capture the significant feature-to-class semantic alignments, but also reflect the semantic connections between YS and YT . In brief, the two key principles of learning a zero-shot classifier are the model effectiveness and the model adaptation. ∗Corresponding author First, for effective modeling, we adopt the boosting strategy [Zhou, 2012] as the basis of the ZSL framework, by learning a zero-shot boosting classifier from weak models to a strong model. The superiority of boosting lies in its flexible piecewise approximation to the data distributions based on ensembles of weak hypotheses. Thus, a boosting ZSL model learns in an asymptotic way to sufficiently capture the discriminative patterns in the feature space and their alignments to the semantic patterns in the embedding space, and obtains the learning effectiveness. On the other hand, for a better adaptation to the target classes YT , the model needs to explore the shared semantic patterns of YS and YT to reflect their semantic correlations. For this sake, it is reasonable to assume that a well-adapted classifier should generate a high compatibility score for a sample and a target class semantically close to the sample's true class, and a low score otherwise. Based on these analysis, we propose a Semantic Correlation Regularization (SCR) approach to impose this constraint, which encourages a negative correlation between a sample's scores on the target classes and the classes' semantic divergences to the sample's ground truth. In this way, SCR constrains the learned model to be consistent with the source-target semantic correlations, for a semantically adaptable model transfer. Furthermore, in addition to the label relations, a feasible model adaptation also relies on a modeling of the sample relations for an exploration of the common geometric structures of the feature space and the semantic space. This requires a control or selection scheme for the samples to be learned, to distinguish the samples with robust patterns for classifying YS, and with adaptable patterns for the transfer to the semantics of YT . Therefore, a self-controlled sample selection of [Zhao et al., 2015] is applicable for ZSL, which adaptively incorporates the samples into learning from easy ones to complex ones, inspired by the human learning process. Such sample selection smoothly controls the learning pace of ZSL by what the model has already learned. With this self-controlled learning pace, a zero-shot model is smoothly guided to focus on those both reliable and adaptable samples to explore the robust feature-semantic alignments, for learning a classifier with good generalization to the target classes. Therefore, motivated by a simultaneous enhancement of the model effectiveness and model adaptation for ZSL as a transfer learning task, we propose a novel framework, Boosted Zero-shot classification with Semantic Correlation Regularization (BZ-SCR). With the SCR embedded into the boosted classification, the boosting process would favor models with not only accurate prediction for an effective classifier, but also with semantic consistency to the target classes for an adaptable model transfer. With a self-controlled sample selection, the BZ-SCR puts emphasis on the reliable and adaptable samples to explore the common feature-semantic structures for a robust model generalization. The proposed framework learns by effectively balancing boosted model selection and self-controlled sample selection. As a result, the proposed framework is capable of jointly considering the learning effectiveness, the cross-semantics adaptation, and the model robustness for learning a zero-shot classifier. In mathematics, we formulate BZ-SCR as a max-margin boosting optimization with self-controlled sample selection. The contributions of this paper are summarized as follows: 1. We propose a boosted ZSL approach that theoretically seeks for effective knowledge transfer in both model learning effectiveness and cross-domain model adaptation, via maxmargin boosting optimization with self-controlled sample selection. To the best of our knowledge, this work is innovative in ZSL by jointly considering model effectiveness, model adaptation, and sample selection within a boost learning framework. 2. We present a novel Semantic Correlation Regularization (SCR) for ZSL, which regularizes the learned boosting model to be consistent with the source-target semantic correlations. In principle, the proposed SCR is capable of effectively capturing the inter-class correlations by modeling the intrinsic geometrical structure properties. ## 2 RelatedWork We review the related work on zero-shot learning, boost learning and self-controlled sample selection approaches. Known as learning from disjoint training and test classes, ZSL requires the ability to transfer knowledge from classes with training data to classes without. The possible sources of side informations of classes include manually annotated attributes [Akata et al., 2013], semantic class taxonomies [Miller, 1995], and unsupervised word representations [Mikolov et al., 2013]. Based on the way of leveraging these informations, the existing ZSL approaches fall into two categories. One is to build intermediate attribute classifiers and use their probabilistic weightings to make class predictions [Lampert et al., 2014; 2009]. The other group is to represent the semantic knowledge of labels in an embedding space and directly learn a mapping function between the feature space and the embedding space. Among them, CCA [Hastie et al., 2001] maximizes the inter-domain statistical correlations; [Palatucci et al., 2009] learns a linear mapping, ALE [Akata et al., 2016], SJE [Akata et al., 2015] and DeViSE [Frome et al., 2013] learn a bilinear mapping, and [Socher et al., 2013] models a nonlinear regression with neural networks. Efforts for directly tackling the absence of the training data are also made, such as semi-supervised transductive methods [Guo et al., 2016] and the generation of labeled virtual data for unseen classes [Wang et al., 2016]. Boosting is a family of supervised ensemble approaches that build a strong model by successively learning and combining multiple weak models [Zhou, 2012]. The main variation among boosting methods is their ways of weighting samples and weak learners, e.g., Adaboost [Freund and Schapire, 1997], SoftBoost [R¨atsch et al., 2007] and LPBoost [Demiriz et al., 2002]. The superiority of boosting lies in its piecewise approximation of a nonlinear decision function to explore the data patterns [Schapire and Freund, 2012]. Proposed by [Kumar et al., 2010], the self-controlled sample selection is inspired by the learning process of humans that gradually incorporates the training samples into learning from easy ones to complex ones. It is initially developed for avoiding the bad local minima of latent models, by learning the data in an order from easy to hard determined by the feedback of the learner itself. It is applied in different applications, such as multimedia reranking [Jiang et al., 2014a], matrix factorization [Zhao et al., 2015], and multiple instance learning [Zhang et al., 2015]. [Meng and Zhao, 2015] provides a theoretical analysis of the robustness of this scheme, which reveals its consistency with the non-convex upper-bounded regularization. ## 3 Our Approach ## 3.1 ProblemFormulation Let {(xi, yi)}Ni=1 be a set of N training samples with feature xi ∈ X ⊆ Rm and label yi ∈ YS = {1, . . . ,CS}, where YS denotes the set of CS seen labels. The goal of ZSL is to learn a classifier for a target label set YT = {CS + 1, . . . , C} disjoint from YS. Let Y = YS ∪YT . The side information of labels such as attributes is available to embed the labels into a structured embedding space, represented by an embedding function ϕ : Y → Rd . As common in supervised learning, the classifier aims to learn a compatibility score function F : X × Y → R with which the prediction is made: where F (x, r;w) determines the compatibility of the pair (x, r) based on the label embedding ϕ(r) and parameter w. The general max-margin formulation for zero-shot classification with loss L and regularization Ω is given by: where δF (xi, r, yi; w) = F (xi, r; w) - F (xi, yi; w); ρir is the score margin of xi between class r and its ground truth yi; ∆ : Y × Y → [0, 1] defines the semantic divergence between two labels, as a penalty of predicting r for the true label yi; ν > 0 is a trade-off hyperparameter. Generally, the loss function L : R → R+ should be convex and monotonically increasing for a small ρ. ## 3.2 Semantic Correlation Regularization In Section 3.1, we have considered to learn a max-margin classifier on YS. However, due to the divergences of semantics and data distributions between YS and YT , the learned models from YS may not necessarily adapt well on YT . Thus, we aim to regularize the model based on the source-target semantic correlations for better cross-semantics adaptation. First, we notice that the semantic correlations of a sample (xi, yi) to the classes of YT are not uniform, but specified by ∆(yi, r). Hence, it is reasonable to assume that a sample (xi, yi) should be assigned a high score F(xi, r) for class r ∈ YT if r is semantically close to yi (∆(yi, r) is low), and a low score F(xi, r) if r is semantically far from yi (∆(yi, r) is high). In other words, for a pair of classes r1, r2 ∈ YT , F(xi, r1) is expected larger than F(xi, r2) if ∆(yi, r1) is smaller than ∆(yi, r2), and vice versa. Thus, we consider the following term: and penalizes max (0, σi(r1, r2)) that is valid if σi(r1, r2) > 0, i.e., the magnitude relationship of the two scores are conflicted with that of their ∆ divergences. Then, by the summation over r1, r2 ∈ YT , and with a relaxation of a sum of hinge to a hinge of sum for ease of optimization, we have: where ∆ti , F t i ∈ R|YT | are the stacked vectors of ∆(yi, r) and F(xi, r) for r ∈ YT , respectively; E[·] is a mean operator and cov[·, ·] is a covariance operator on the elements of vectors. Based on the above analysis, we propose the Semantic Correlation Regularization (SCR), to encourage the covariance covi to be lower than 0 such that the score distributions and the semantic divergence distributions on YT are negatively correlated. Instead of using max (0, covi), we use a smooth surrogate of the hinge function, the logistic function, for derivation convenience. The SCR is defined as: where ρti ∈ R|YT | is the stacked vector of ρir for r ∈ YT . Here, we define the SCR term as a function of ρti for the convenience of dual derivation in Section 3.4, since With the SCR embedded into the classification objective Eq. (2), the learned model is regularized to be consistent with the source-target semantic correlations, which improves the model adaptation to the target classes. ## 3.3 BZ-SCR Framework We formulate the BZ-SCR framework based on the boost learning, the SCR in Section 3.2, and the self-controlled sample selection, for an effective and adaptable zero-shot classifier. Specifically, for effective modeling, we adopt the boosting strategy to formulate F as an ensemble of weak classifiers {hj ∈ H}Kj=1 in the space of weak models H: where each hj : X × Y → R is a base score function; w is specified as the weight parameter to be learned. On the other hand, the samples relations should also be modeled in addition to the labels relations for a robust model transfer. Thus, inspired by the adaptive scheme of [Kumar et al., 2010] that learns a model smoothly from the easy/faithful samples to the hard/confusing ones, we reformulate the objective of Eq. (2) with a self-controlled sample selection procedure. Then, based on the boosted model Eq. (4) and the SCR Eq. (3), we have the formulation of BZ-SCR framework: where si ∈ [0, 1] is the weight of sample xi that indicates its learning "easiness"; g (·; λ) : [0, 1] → R is the function that specifies how the samples are selected (the reweighting scheme of s) controlled by the parameter λ > 0; and β > 0 is a trade-off hyperparameter between the classification loss L(·) for fitness on YS and the SCR R(·) for adaptation to YT . Note that in Eq. (5), a weight si is assigned to each sample as a measure of its "easiness", which is tuned based on the currently learned confidence (including classification loss and SCR) and the function g (si; λ) to adaptively select reliable and adaptable samples. For the convenience of derivation, we specify the loss L(·) as a smooth loss function, the logistic loss, and specify the regularization Ω(·) as the l1-norm to impose a sparsity constraint on the model ensemble: ## 3.4 Optimization Following [Pi et al., 2016], we use the alternating optimization to solve Eq. (5). For the optimization of s, we have where li = ∑r∈YS L(ρir) + βR(ρti ) is a composite cost of model fitness on YS and model transfer utility on YT . Based on the summarized general properties and candidates of the g function in [Jiang et al., 2014a], we specify g and the corresponding s∗i as the scheme for mixture weighting due to its better overall performance in the experiments: which is a mixture of hard 0-1 weighting and soft real-valued weighting, with an extra parameter ζ. Note that s∗i is monotonically decreasing with li and increasing with λ, so as to select easy samples with small losses under the tolerance λ. For the optimization of w, we have To solve w in Eq. (9), we adopt the column generation method [Demiriz et al., 2002] in the dual space of w to handle the potentially infinite candidate weak models in the H space. We check the dual problem of Eq. (9): where Q ∈ RN×C is the Lagrangian multiplier of the equality constraints of Eq. (9); Qti ∈ R|YT | is the stacked vector of Qir for r ∈ YT ; R⋆ si : R|YT | → R is the Fenchel dual function of siR(·); H(Qir) = Qir lnQir + (si - Qir) ln (si - Qir); J(Q,∆) = ∑i,r Qir∆(yi, r); h(ir) ∈ RK is the stacked vector of hj(xi, r) for j ∈ [1,K]. The relation between the dual and the primal solution is: Please refer to Appendix A for the dual derivation of Eqs. (10) and (11). Based on the column generation, the set of weak models is augmented by a weak model ˆh that most violates the current dual constraint in Eq. (10): Then the optimization continues with the new set of weak models, until the violation score (objective value of Eq. (12)) reaches a tolerance threshold. Eq. (12) indicates that the matrix Q serves as the sample importance for learning a new weak model. From Eq. (11), we see that Q gives high weights to not only the misclassified samples on YS (with large ρir) and those not aligned well with their semantic correlations on YT (with large positive covi), but also the reliable samples with high weights si. These reliable samples are those both discriminative on YS and adapt well on YT in the previous iteration. As a result, the future weak learners will emphasize on samples both insufficiently learned currently and easily learned previously, Input Algorithm 1: Boosted Zero-shot classification with Semantic Correlation Regularization (BZ-SCR) : Training set {(xi, yi)}Ni=1 ; label embeddings {ϕ(y)}y∈Y; ν; β; λmax; TES; µ > 1; ϵ > 0. Output : A set of K weak models {hj ∈ H}Kj=1 ; w. 1 Initialize: s(0) ; (λ, ζ); Q← s(0)1TC ; t ← 0; 2 repeat 3 t ← t + 1; 4 Learn a newweak model: solve Eq. (12) to obtain ht based on Q; 5 Update w: solve Eq. (9) for w(t) based on s(t-1) ; 6 Update Q: compute Q by Eq. (11) based on w(t) and s(t-1) ; 7 Update s: compute s(t) by Eq. (8) based on w(t) ; Validation: 8 Test {hj}tj=1 and w(t) on the validation set, to obtain the classification error rate err(t) ; ## Annealing: 9 if λ < λmax then 10 (λ, ζ) ← (µλ, µζ); 11 end 12 until ∑i,r Qir {ht(xi, yi) - ht(xi, r)} < ν + ϵ or t ⩾ TES and err(t) > min1⩽τ⩽t-1 err(τ) ; 13 K ← argminτ err(τ) ; so as to obtain an effective, adaptable and robust zero-shot classifier for knowledge transfer to the target classes. We summarize the optimization procedure in Algorithm 1. Note that the sample selection parameters (λ, ζ) are iteratively increased (annealed) when they are small (Line 9 to 11), so as to introduce more complex samples in the future learning. An early stopping criterion is adopted to maintain a reasonable running time. Furthermore, the convergence of Algorithm 1 is guaranteed by the convexity of the two subproblems Eqs. (7) and (9) of the alternating optimization. This leads to the monotonic decreasing of the objective value of Eq. (5) after each iteration. Since the objective is bounded below, such optimization procedure is guaranteed to converge. Figure 1(a)(b) in the experiment empirically shows that the convergence is usually reached within several hundreds of iterations. ## 4 Experiments We evaluate the performance of BZ-SCR on the two classic ZSL image datasets, Animal With Attributes 1 (AWA) and Caltech-UCSD-Birds-200 2 (CUB200). The comparative methods include Structured Joint Embedding (SJE) [Akata et al., 2015], Attribute Label Embedding (ALE) [Akata et al., 2016], Nonlinear Regression (NR) [Socher et al., 2013], and Canonical Correlation Analysis (CCA) [Hastie et al., 2001]. 1 http://attributes.kyb.tuebingen.mpg.de/ 2 http://www.vision.caltech.edu/visipedia/CUB-200-2011.html Table 1: Statistics of the datasets | Dataset | AWA | CUB200 | |-------------------|-----------------|------------------| | Samples | 30475 | 11788 | | Classes (Split) | 50 (40/10) | 200 (150/50) | | Feature (dimm) | PCAed VGG (512) | GoogleNet (1024) | | Embedding (dim d) | Word2Vec (300) | Attributes (312) | ## 4.1 Datasets and Experimental Settings We summarize the statistics of the datasets in Table 1. For label embeddings, we use the 300-D GoogleNews Word2Vec 3 representations for AWA, and the 312-D annotated attributes for CUB200. For the class split, we adopt the default split (40/10 for train+val/test) for AWA and the same split as [Akata et al., 2013] (150/50 for train+val/test) for CUB200. We specify for AWA the semantic divergence ∆ based on the wordnet hierarchy 4 : where SPath(y1, y2) is the length of the shortest path between words y1, y2 in the wordnet hierarchy. For CUB200, we specify ∆ based on the cosine similarities between the label embeddings (attributes): where cos(·, ·) is the cosine similarity between two vectors, and the denominator is for a normalization to [0, 1]. We specify the weak score function h(x, y) as a rank-one bilinear model, for the convenience of learning a new ˆh: With h taking the form of Eq. (15), the learning of ˆh (Eq. (12)) is equivalent to a simple SVD problem. We adopt the strategy in [Jiang et al., 2014b] for the annealing of the parameters (λ, ζ) (Line 9 to 11 in Algorithm 1). At each iteration, we sort the samples in the ascending order of their losses, and set (λ, ζ) based on the proportion of samples to be selected by now. We anneal the proportion of the selected samples instead of the absolute values of (λ, ζ), which is shown more stable in [Jiang et al., 2014b]. We implement a grid search for the tuning of the hyperparameters ν, β, and report the best performances. ## 4.2 Experimental Results Table 2 shows the ¯∆ (mean of ∆) and the ER (error rate) performances of BZ-SCR and the comparative methods, where "Boosting" is the boosting-only version of BZ-SCR (fixing all s = 1N). The best results are shown in bold face. Since SJE and ALE also involve a ∆ loss in learning, we show their ER results as the better one between two forms of ∆: the same as BZ-SCR (Eq. (13)/(14)) and the uniform 0-1 error. The shown results of BZ-SCR are achieved with ν/N = 10-4 , β/N = 0.4 for AWA, and ν/N ∈ 3 http://code.google.com/archive/p/word2vec/ 4 http://stevenloria.com/tutorial-wordnet-textblob/ Table 2: The ¯∆ and error rate performance of each method | | AWA - ¯∆ | AWA - ER | CUB200 - ¯∆ | CUB200 - ER | |----------|------------|------------|---------------|---------------| | BZ-SCR | 0.2907 | 0.3409 | 0.1133 | 0.4664 | | Boosting | 0.3305 | 0.3704 | 0.1277 | 0.4966 | | SJE | 0.3716 | 0.4239 | 0.1286 | 0.4988 | | ALE | 0.3394 | 0.3875 | 0.1401 | 0.4954 | | NR | 0.4191 | 0.5100 | 0.1661 | 0.6478 | | CCA | 0.3945 | 0.4702 | 0.2614 | 0.6860 | {0.025, 0.05}, β/N ∈ {0.1, 0.2} for CUB200. We see that BZ-SCR has a better overall performance than the comparative methods, since BZ-SCR jointly addresses the issues of model effectiveness and model adaptation for ZSL, based on a self-adaptive SCR-regularized boosting optimization. Furthermore, we show in Figure 1(a)(b) the change of the error rates on the training and the test set w.r.t. the learning iterations of BZ-SCR and boosting model only, with the same parameter settings. We see that BZ-SCR generally has a smaller gap between the training curves and the test curves, which shows that BZ-SCR achieves a more stable learning process and a more adaptable model transfer. This is due to the smooth learning pace of BZ-SCR based on a self-controlled sample selection from easy reliable samples to hard confusing ones, instead of learning from the whole data batch as boosting does. We investigate the efficacy of the semantic correlation regularization (SCR) for our model, and show the error rate results w.r.t. different β values in Figure 1(c). From the figure we see that the integration of SCR is beneficial for the model performance. We empirically find that a better overall performance is generally achieved with β/N around 0.1|YS|/|YT |. ## 5 Conclusion In this work, we study zero-shot learning (ZSL) as a transfer learning problem, and focus on its two key aspects, model effectiveness and model adaptation. We propose a unified framework, Boosted Zero-shot classification with Semantic Correlation Regularization (BZ-SCR), that simultaneously addresses these two aspects. We adopt the boosting strategy to learn an effective ensemble classifier, and devise a Semantic Correlation Regularization (SCR) to regularize the model with the inter-class semantic correlations for learning a semantically adaptable zero-shot model. Moreover, we embed a self-controlled sample selection into the framework to model the samples relations for a robust model generalization. By effectively balancing the SCR-regularized boosted model selection and the self-controlled sample selection, the BZ-SCR framework is capable of capturing both discriminative and adaptable feature-to-class semantic alignments, while ensuring the reliability and adaptability of the samples involved in learning. Thus, the proposed framework jointly considers the learning effectiveness, the cross-semantics adaptation, and the model robustness for learning a zero-shot classifier. The experiments on two classic ZSL image datasets verify the superiority of the proposed framework. Figure 1: (a)(b) The error rates on the training and test set of BZ-SCR and boosting model w.r.t. the iterations, with ν/N = 10-4 , β/N = 0.4 for AWA, and ν/N = 0.025, β/N = 0.2 for CUB200. BZ-SCR has a smaller gap between training and test curves. (c) The error rates of BZ-SCR w.r.t. β/N, with ν/N = 10-4 for AWA and ν/N = 0.025 for CUB200. ![Image](https://ijcai.org/proceedings/2017/fulltext/362/image_000000_f6680935ec647abad437ab023e85f02876000e3442b10565f3efc19c23faddc0.png) ## Acknowledgments This work was supported in part by the National Natural Science Foundation of China under Grants U1509206, 61472353, and 61672456, in part by the Alibaba-Zhejiang University Joint Institute of Frontier Technologies, and the Fundamental Research Funds for Central Universities in China. ## A Dual Derivation of Eqs. (10) and (11) For Eq. (9), we write its Lagrangian function: where Q ∈ RN×C , θ ∈ RK (θ ⩾ 0) are the Lagrangian multipliers for the equality constraints of ρir and the inequality constraint of w ⩾ 0, respectively. Then we have: Since L(ρ) = ln (1+ eρ ), covi = cov(∆ti , ρti ) -D[∆ti ], let ∂L/∂ρir = 0 (KKT conditions), we have: which is exactly Eq. (11). Furthermore, the derivative of L to w is: where h(ir) ∈ RK is the stacked vector of hj(xi, r) for j ∈ [1, K]. Let ∂L/∂w = 0, and based on θ ⩾ 0, we have: which is the dual constraint of Q for the dual problem. By substituting ρir (r ∈ YS) from Eq. (17) and θ from Eq. (18) into Eq. (16), we have: where H(Qir) = Qir lnQir + (si - Qir) ln (si -Qir); J(Q,∆) = ∑i,r Qir∆(yi, r); Qti , ρti ∈ R|YT | are the stacked vectors of Qir and ρir for r ∈ YT , respectively. Based on the definition of Fenchel dual function, we have: where R⋆ si (·) is the Fenchel dual function of siR(·). Finally, based on the Lagrangian duality, the dual problem should be max Q min w,ρ L, which is given by: where we omit the constant term. Together with the constraint Eq. (18), the above optimization is equivalent to Eq. (10). Moreover, since L(·) is convex and covi is linear to ρti , the primal objective function is convex and the duality gap is 0. ## References 1. [Akata et al., 2013] Zeynep Akata, Florent Perronnin, Zaïd Harchaoui, and Cordelia Schmid. Label-embedding for attribute-based classification. In Computer Vision and Pat- tern Recognition, pages 819-826, 2013. 2. [Akata et al., 2015] Zeynep Akata, Scott E. Reed, Daniel Walter, Honglak Lee, and Bernt Schiele. Evaluation of output embeddings for fine-grained image classification. In Computer Vision and Pattern Recognition, pages 2927- 2936, 2015. 3. [Akata et al., 2016] Zeynep Akata, Florent Perronnin, Zaïd Harchaoui, and Cordelia Schmid. Label-embedding for image classification. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 38(7):1425-1438, 2016. 4. [Demiriz et al., 2002] Ayhan Demiriz, Kristin P Bennett, and John Shawe-Taylor. Linear programming boosting via column generation. Machine Learning, 46(1-3):225-254, 2002. 5. [Freund and Schapire, 1997] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Com- puter and System Sciences, 55(1):119-139, 1997. 6. [Frome et al., 2013] Andrea Frome, Gregory S. Cor- rado, Jonathon Shlens, Samy Bengio, Jeffrey Dean, Marc'Aurelio Ranzato, and Tomas Mikolov. Devise: A deep visual-semantic embedding model. In Ad- vances in Neural Information Processing Systems, pages 2121-2129, 2013. 7. [Guo et al., 2016] Yuchen Guo, Guiguang Ding, Xiaoming Jin, and Jianmin Wang. Transductive zero-shot recognition via shared model space learning. In AAAI Conference on Artificial Intelligence, pages 3434-3500, 2016. 8. [Hastie et al., 2001] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. 2001. NY Springer, 2001. 9. [Jiang et al., 2014a] Lu Jiang, Deyu Meng, Teruko Mita- mura, and Alexander G Hauptmann. Easy samples first: Self-paced reranking for zero-example multimedia search. In Proceedings of the ACM International Conference on Multimedia, pages 547-556. ACM, 2014. 10. [Jiang et al., 2014b] Lu Jiang, Deyu Meng, Shoou-I Yu, Zhenzhong Lan, Shiguang Shan, and Alexander Haupt- mann. Self-paced learning with diversity. In Advances in Neural Information Processing Systems, pages 2078- 2086, 2014. 11. [Kumar et al., 2010] M Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In Advances in Neural Information Processing Systems, pages 1189-1197, 2010. 12. [Lampert et al., 2009] Christoph H. Lampert, Hannes Nick- isch, and Stefan Harmeling. Learning to detect unseen ob- ject classes by between-class attribute transfer. In Com- puter Vision and Pattern Recognition, pages 951-958, 2009. 13. [Lampert et al., 2014] Christoph H. Lampert, Hannes Nick- isch, and Stefan Harmeling. Attribute-based classification for zero-shot visual object categorization. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 36(3):453-465, 2014. 14. [Meng and Zhao, 2015] Deyu Meng and Qian Zhao. What objective does self-paced learning indeed optimize? arXiv preprint arXiv:1511.06049, 2015. 15. [Mikolov et al., 2013] Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their composi- tionality. In Advances in Neural Information Processing Systems, pages 3111-3119, 2013. 16. [Miller, 1995] George A. Miller. Wordnet: A lexical database for english. Communications of the ACM, 38(11):39-41, 1995. 17. [Palatucci et al., 2009] Mark Palatucci, Dean Pomerleau, Geoffrey E. Hinton, and Tom M. Mitchell. Zero-shot learning with semantic output codes. In Advances in Neu- ral Information Processing Systems, pages 1410-1418, 2009. 18. [Pi et al., 2016] Te Pi, Xi Li, Zhongfei Zhang, Deyu Meng, Fei Wu, Jun Xiao, and Yueting Zhuang. Self-paced boost learning for classification. In International Joint Confer- ence on Artificial Intelligence, pages 1932-1938, 2016. 19. [Rätsch et al., 2007] Gunnar Rätsch, Manfred K Warmuth, and Karen A Glocer. Boosting algorithms for maximiz- ing the soft margin. In Advances in Neural Information Processing Systems, pages 1585-1592, 2007. 20. [Schapire and Freund, 2012] Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. MIT press, 2012. 21. [Socher et al., 2013] Richard Socher, Milind Ganjoo, Christopher D. Manning, and Andrew Y. Ng. Zero-shot learning through cross-modal transfer. In Advances in Neural Information Processing Systems, pages 935-943, 2013. 22. [Wang et al., 2016] Donghui Wang, Yanan Li, Yuetan Lin, and Yueting Zhuang. Relational knowledge transfer for zero-shot learning. In AAAI Conference on Artificial Intel- ligence, pages 2145-2151, 2016. 23. [Zhang et al., 2015] Dingwen Zhang, Deyu Meng, Chao Li, Lu Jiang, Qian Zhao, and Junwei Han. A self-paced multiple-instance learning framework for co-saliency de- tection. In International Conference on Computer Vision, pages 594-602, 2015. 24. [Zhao et al., 2015] Qian Zhao, Deyu Meng, Lu Jiang, Qi Xie, Zongben Xu, and Alexander G Hauptmann. Self- paced learning for matrix factorization. In AAAI Confer- ence on Artificial Intelligence, 2015. 25. [Zhou, 2012] Zhi-Hua Zhou. Ensemble methods: founda- tions and algorithms. CRC Press, 2012.