extfieldsofstudy:
Computer Science
Mathematics

text:
Joint Bayesian Gaussian discriminant analysis for speaker verification

State-of-the-art i-vector based speaker verification relies on variants of Probabilistic Linear Discriminant Analysis (PLDA) for discriminant analysis. We are mainly motivated by the recent work of the joint Bayesian (JB) method, which is originally proposed for discriminant analysis in face verification. We apply JB to speaker verification and make three contributions beyond the original JB. 1) In contrast to the EM iterations with approximated statistics in the original JB, the EM iterations with exact statistics are employed and give better performance. 2) We propose to do simultaneous diagonalization (SD) of the within-class and between-class covariance matrices to achieve efficient testing, which has broader application scope than the SVD-based efficient testing method in the original JB. 3) We scrutinize similarities and differences between various Gaussian PLDAs and JB, complementing the previous analysis of comparing JB only with Prince-Elder PLDA. Extensive experiments are conducted on NIST SRE10 core condition 5, empirically validating the superiority of JB with faster convergence rate and 9-13% EER reduction compared with state-of-the-art PLDA.

INTRODUCTION
The state-of-the-art in speaker recognition is currently dominated by the i-vector approach, that models both speaker and channel variabilities in a single low-dimensional space termed the total variability subspace [1]. An i-vector based speaker verification system mainly consists of three components, which are i-vector extractor based on Gaussian Mixture Models (GMMs) or Deep Neural Networks (DNNs) [2], i-vector post-processing (e.g. length normalization) and discriminant analysis. Note that this approach defers the decomposition of speaker and intersession variabilities to the stage of discriminant analysis, which is particularly important for this approach.
An attractive discriminant analysis technique is to construct likelihood ratio score based on probabilistic generative models such as the widely used Probabilistic Linear Discriminant Analysis (PLDA) [3] with many variants. Except the heavy-tailed PLDA [4], most variants are Gaussian, such as Prince-Elder PLDA [3], Simplified PLDA (SPLDA) [5], Kaldi PLDA [6], two-covariance model [7], and Ioffe PLDA [8]. Basically, Gaussian PLDA assumes that the j-th i-vector from speaker i obeys the following decomposition 1 : This work is supported by NSFC grant 61473168. 1 Throughout the paper, we assume the data have zero-mean after a standard centering preprocessing step and omit the global mean in the model.
where the latent speaker factor zi and the intersession residual ǫij are both Guassians and independently distributed. F is the loading matrix spanning the speaker subspace. Denote by HI the intra-personal hypothesis that one set of i-vectors x1 and another set of i-vectors x2 belong to the same speaker, and HE the extra-personal hypothesis that they are from different speakers. The speaker verification problem can then be solved by thresholding the likelihood ratio score p(x1, x2|HI )/p(x1, x2|HE).
The performance of PLDA largely depends on how it can be trained effectively to learn the within-class variability, which characterizes intersession residuals, and the between-class variability, which characterizes differences among speakers. Some improvements include using data domain adaptation of PLDA parameters [5] and discriminative training [9]. In this paper, we are primarily concerned with addressing the two basic challenging issues for the current Gaussian PLDA family. First, for PLDAs with subspace modeling, it is difficult to determine the subspace dimension which is crucial for performance. Low subspace dimension often leads to under-fitting, while high subspace dimension results in over-fitting. Second, whether using subspace modeling or not, current PLDAs suffer from slow convergence of their implemented EM iterations. As analyzed in [10], different parameterizations and selections of hidden variables in designing EM updates have significant effect on the convergence performance. These basic issues hinder improving the performance of current PLDAs.
We are mainly motivated by recent the work of Joint Bayesian (JB) method [10], which was originally proposed for face verification. In JB, there is no need to determine the subspace dimension, and it achieved faster convergence and more accuracy in [10] for face verification. We apply JB to speaker verification and make three main contributions. 1) We find that the EM updates with approximated statistics suggested in [10] does not work in speaker verification problem. Instead, the EM iterations with exact statistics are employed and give better performance. 2) Inspired by Fisher LDA, we propose to do simultaneous diagonalization (SD) of the within-class and between-class covariance matrices to achieve efficient testing. Compared to the SVD-based efficient testing method in [10], the new SD method can still be applied to reduce the testing complexity even in the case that the number of training samples per subject are different. 3) We scrutinize similarities and differences between various Gaussian PLDAs and JB, complementing the analysis of comparing JB only with Prince-Elder PLDA in [10]. Moreover, extensive experiments are conducted on NIST SRE10 core condition 5, empirically validating the superiority of JB in term of EM convergence rate and EER performance.

JOINT BAYESIAN GAUSSIAN DISCRIMINANT ANALYSIS
Joint Bayesian (JB) Gaussian discriminant analysis was first proposed in [10] for face verification. Its model formulation is similar to the two-covariance model [11] but with different parameterizations and selections of hidden variables in EM training. For speaker verification, we use two independent Gaussians to represent speaker identity and intersession residuals respectively. The j-th i-vector of speaker i, denoted by xij ∈ R d , is decomposed as: The parameters Θ are estimated by the EM algorithm through iteratively optimizing the expected complete log-likelihood function as follows: where Θ t = {S t µ , S t ε } are the parameters from the t-th EM update, and Θ t+1 the parameters to be updated in the (t + 1)-th iteration. Under this auxiliary objective function, the terms related to Sµ and Sǫ are effectively decoupled, resulting in very elegant update equations for Sµ and Sǫ [10].
In speaker verification testing, we calculate the log-likelihood ratio score to determine whether one set of i-vectors x1 (including m1 i-vectors) and another set of i-vectors x2 (including m2 ivectors) are from the same speaker 2 : Note that all the data likelihoods p(x1, x2), p(x1) and p(x2) can be calculated through Eq. 1, which involves matrix inversions.
To accelerate testing, [10] employed SVD to obtain low rank approximations of the matrices appearing in the three log-likelihood terms in Eq. 3, which depend on m1 + m2, m1 and m2 respectively. Therefore, this speedup is more useful under the condition that the number of i-vectors is the same across all subjects, i.e. mi = m. This is often satisfied in the task of face verification and face search.
Here we propose first to do simultaneous diagonalization (SD) of Sµ and Sε, Φ T SµΦ = K and Φ T SǫΦ = I. Similar to Fisher LDA, we keep the first s < d largest eigenvalues of S −1 µ Sε, giving the low-rank diagonal matrix K. Denote by Φ the corresponding 2 By abuse of notation, here x 1 is not the data corresponding to speaker 1. low-rank eigenvector matrix. By defining Ψ = Φ −T , we have Sµ = ΨKΨ T , Sǫ = ΨΨ T , and moreover, where Ω = diag(Ψ; . . . ; Ψ). Based on this decomposition of Σx i , the calculation of data likelihood p(xi) could be accelerated, if we take Ω to transform the i-vectors via pre-computation. The likelihood calculation then only involves inversion of diagonal matrices, reducing the complexity from O(d 3 ) to O(d). Moreover, it can be seen that this speedup does not depend on mi and thus has broader applicability. In this paper, we also conduct experiments to compare these two speedup methods over speaker verification accuracy.

CONNECTION WITH PLDA
In this section, we investigate the connections between joint Bayesian (JB) [10], Simplified PLDA (SPLDA) [5] and Kaldi-PLDA [12]. We mainly show that different parameterization and selection of hidden variables lead to different behavior of the EM algorithm, and JB is superior to PLDAs in terms of EM convergence. For the advantages of JB in allowing the data to implicitly determine the subspace dimensionality for maximal discrimination and favoring low-rank esimates of Sµ and Sε, the reader could refer to [10]. Table 1 summarizes the similarities and differences between JB, SPLDA, Kaldi PLDA and the two-covariance model.

Simplified PLDA (SPLDA)
Basically, SPLDA [5] assumes that j-th i-vector from speaker i obeys the following decomposition : where the latent speaker factor zi ∼ N (0, I) and the intersession residual ǫij ∼ N (0, Λ) are both Guassians and independently distributed. F is the loading matrix spanning the speaker subspace. The speaker subspace could be full rank, which is also known as the two-covariance model [11]. The parameters Θ = {F, Λ} [5] are estimated by the EM algorithm through iteratively optimizing the complete log-likelihood logp(xi, zi; Θt+1) averaged over p(zi|xi; Θt) where Θt = {Λt, Ft} Different from Eq. 2 in JB, the hidden variables in SPLDA are only zi's, excluding ǫij 's. 3 Now we analyze the convergence property of the EM updates for SPLDA, analogous to [10]. Note that maximizing Eq. 5 over Ft+1 is equivalent to minimizing over Ft+1 It can be seen that  N (0, Sµ) is the identity variable for speaker i, modeled by the between-class covariance Sµ. εij ∼ N (0, Sǫ) is the intersession residual, modeled by the within-class covariance Sǫ. For SPLDA, zi ∼ N (0, I) stands for the identity variable. where When Λt is small, by setting Ft+1 as Ft, we find that Hence updating Ft+1 as Ft approximately optimize the M-step and the EM-algorithm stalls upon a single iteration.
Note that theoretically the EM algorithm is only actually guaranteed to produce non-decreasing optimization of data likelihood through a series of parameter updates. Strict convergence to local minima (or stationary points) requires further strong assumptions. Combining this understanding of the EM algorithm and the above analysis of halt upon a single iteration, we could realize that the EM update for SPLDA could be easily stuck into a non-local minimum with small Λt. The EM update for JB does not have such problem, since JB has different parameterization and selection of hidden variables. The faster convergence of the EM iterations for JB is also empirically observed in our experiments.

Kalid PLDA
The Kaldi is a widely used open-source speech recognition toolkit [12]. Here we examine the PLDA implementation in Kaldi code repository [6]. The conceptual starting point for Kaldi PLDA is the SPLDA model as shown in Eq. 4 with full rank F . Next, Kaldi PLDA is only concerned with modeling the average i-vector for each speakerxi = m i j=1 xij/mi, which is distributed according to where mi is the numbers of extracted i-vectors for speaker i. Eq. 6 is then treated as the data likelihood function. All the extracted i-vectors for each speaker are collapsed as a single sample -the average i-vector, which is assumed to obey the decomposition : where µi ∼ N (0, Γ) models the between-class variability with the covariance Γ = F F T and the average residualεi = m i j=1 εij/mi ∼ N (0, 1 m i Λ) models the within-class variability. The expected complete log-likelihood function for the EM algorithm is optimized to iteratively estimate Γ and Λ, as follows: The parameterization of Kaldi PLDA is similar to JB, i.e. using two covariance matrices. Hence the EM iterations in Kaldi PLDA can also select the total hidden variables (µi, εi1), with good convergence. However, the additive decomposition only applies to the average i-vector in Kaldi PLDA. This is helpful for estimating betweenclass covariance but is detrimental for estimating within-class covariance. At the testing phase, Kaldi PLDA also performs simultaneous diagonalization of Λ and Γ. However, the significance of computational saving is less than the SD applied in JB, because JB calculates the joint likelihood of a number of i-vectors while Kaldi only calculates the likelihood of a single average i-vector.

Dataset
We conduct speaker verification experiments with different discriminant analysis techniques on the NIST SRE10 core condition 5, which includes 11982 speakers, 7169 target and 408950 nontarget trials [13]. The DNN used in the experiments is trained on part of the Fisher data including about 600 hours of speech cuts. The i-vector extractor training data comprises 57517 speech cuts of 5767 speakers, which are from Switchboard, Fisher and NIST SRE 04, 06, and 08. Both JB and SPLDA are trained on SRE data, consisting of 36612 speech cuts and 3805 speakers from NIST SRE 04, 06, and 08.  Table 2. The data used to train the DNN-UBM, i-vector extractor, SPLDA and JB for speaker verification.

System Configuration
The features used in the experiments are 40-dimensional Mel Frequency Cepstral Coefficients (MFCCs), including 20-dimensional static features and first-order derivatives. The speaker verification system uses a DNN-UBM with 5 hidden layers, 5335 senones, and a 600-dimensional i-vector extractor. The input of the DNN-UBM is the MFCCs extracted using 21 frames (11 frames before and 9 frames after). For discriminant analysis techniques, we implement three references namely LDA+COS, SPLDA and Kaldi PLDA. We apply the LDA to the i-vectors to obtain 200-dimension features and use cosine distance metric for testing. For SPLDA, we set the dimension of the subspace to 300. For Kaldi PLDA, we use the default configuration of the Kaldi toolkit [6]. The system performances are reported by equal error rate (EER) and minimum decision cost function (DCF) defined in NIST SRE08 and SRE10 [13].

Speaker Verification Performance
We evaluate LDA+COS, Kaldi PLDA, SPLDA and JB on the NIST SRE10 core condition 5. These four models share the same training and test data. Fig. 1 illustrates the detection error trade-off (DET) curves of LDA+COS, SPLDA, Kaldi PLDA and JB for discriminant analysis with configurations described in Section 4.2. From the results show in Tab. 3, we can conclude that : • Compared to distance-based discriminant analysis LDA+COS, probabilistic generative model based methods such SPLDA, Kaldi PLDA and JB achieve better performance on EER.
• In terms of EER, JB improves 13.0% and 45.3% compared to SPLDA and Kaldi PLDA respectively on SRE10 male tests, 9.2% and 30.9% on female tests. This verifies that JB with careful selection of hidden variables achieves better parameter estimation due to efficient EM updates.
• SPLDA achieves better results on EER than Kaldi PLDA, because SPLDA utilizes the joint likelihood of i-vectors rather than the single average i-vector as used in Kaldi PLDA to estimate the parameters.

Subspace Dimensionality
Here we investigate the impact of the sub-space dimensionality of JB and SPLDA for discriminant analysis, which is shown in Fig. 2. Two methods (SVD, SD) are used to reduce the subspace dimensionality of JB in speaker verification testing. It can be seen that: 1) The   Table 3. Performance comparison of four different discriminant analysis back-ends on NIST SRE10 core condition 5.
dimension of the subspace plays an important role in SPLDA that lower may cause under-fitting, while higher may cause over-fitting.
2) The JB performance fluctuates slightly with the change of subspace dimension in testing, but the time complexity reduces from O(d 3 ) to O(s 3 ). Loose parameterization for JB makes it more robust since the dimension of the subspace is automatically fitted via data rather than manual defined. 3) SVD and SD have close performances but SD has wider applicability.

Convergence Rate
As discussed before, EM iterations for SPLDA are easier to stall in a single iteration. Fig. 3 shows the neg-loglikelihood curve of SPLDA with the optimal subspace dimensionality and that of JB trained by EM with exact and approximated statistics. From Fig. 3, first we find that JB converges faster than SPLDA with better parameter estimation. Second, we find that JB trained by EM with approximated statistics proposed by [10] will diverge in Fig 3b, Table 4. The effect of dimensionality reduction for JB and PLDA. The dimension of subspace for JB-SVD is determined by dim = rank(A) = 403 (A is defined in [10]) and the dimension of the subspace for JB-SD is determined by dim = rank(Sµ) = 407.
Tab. 4 shows the differences on EER between SPLDA and JB with or without dimension reduction. It is observed that even with the same dimension of the subspace learned by JB, SPLDA is still worse than JB. This justifies our analysis that model formulation and hidden variable selection of JB leads to better parameter estimation than SPLDA.

CONCLUSIONS
In this paper, we propose to apply JB to model i-vectors with careful parameterization and hidden variable selection that benefits EM iterations. Both theoretical derivation and experiments conducted on the NIST SRE10 core condition demonstrate that: 1) the parameterization of JB enables it to learn the intrinsic dimensionality of the identify subspace, which can reduce the system complexity without performance degradation; 2) Hidden variables selection of JB makes EM iterations converge faster with better parameter estimation; 3) The EM with exact statistics performs better than with approximated statistics. For future work, it is interesting to apply data domain adaption [5] and feature compensation [14,15] and nearestneighbor discriminant analysis (NDA) [16][17] that have been successfully applied to PLDA to JB to further improve performance.


s2fieldsofstudy:
Computer Science
Education

text:
Third-Person Imitation Learning

Reinforcement learning (RL) makes it possible to train agents capable of achiev- ing sophisticated goals in complex and uncertain environments. A key difficulty in reinforcement learning is specifying a reward function for the agent to optimize. Traditionally, imitation learning in RL has been used to overcome this problem. Unfortunately, hitherto imitation learning methods tend to require that demonstra- tions are supplied in the first-person: the agent is provided with a sequence of states and a specification of the actions that it should have taken. While powerful, this kind of imitation learning is limited by the relatively hard problem of collect- ing first-person demonstrations. Humans address this problem by learning from third-person demonstrations: they observe other humans perform tasks, infer the task, and accomplish the same task themselves. In this paper, we present a method for unsupervised third-person imitation learn- ing. Here third-person refers to training an agent to correctly achieve a simple goal in a simple environment when it is provided a demonstration of a teacher achieving the same goal but from a different viewpoint; and unsupervised refers to the fact that the agent receives only these third-person demonstrations, and is not provided a correspondence between teacher states and student states. Our methods primary insight is that recent advances from domain confusion can be utilized to yield domain agnostic features which are crucial during the training process. To validate our approach, we report successful experiments on learning from third-person demonstrations in a pointmass domain, a reacher domain, and inverted pendulum.

INTRODUCTION
Reinforcement learning (RL) is a framework for training agents to maximize rewards in large, unknown, stochastic environments. In recent years, combining techniques from deep learning with reinforcement learning has yielded a string of successful applications in game playing and robotics Mnih et al. (2015;; Schulman et al. (2015a); . These successful applications, and the speed at which the abilities of RL algorithms have been increasing, makes it an exciting area of research with significant potential for future applications.
One of the major weaknesses of RL is the need to manually specify a reward function. For each task we wish our agent to accomplish, we must provide it with a reward function whose maximizer will precisely recover the desired behavior. This weakness is addressed by the field of Inverse Reinforcement Learning (IRL). Given a set of expert trajectories, IRL algorithms produce a reward function under which these the expert trajectories enjoy the property of optimality. Recently, there has been a significant amount of work on IRL, and current algorithms can infer a reward function from a very modest number of demonstrations (e.g,. Abbeel & Ng (2004); Ratliff et al. (2006); Ziebart et al. (2008); Levine et al. (2011); Ho & Ermon (2016); ).
While IRL algorithms are appealing, they impose the somewhat unrealistic requirement that the demonstrations should be provided from the first-person point of view with respect to the agent. Human beings learn to imitate entirely from third-person demonstrations -i.e., by observing other humans achieve goals. Indeed, in many situations, first-person demonstrations are outright impossible to obtain. Meanwhile, third-person demonstrations are often relatively easy to obtain. The goal of this paper is to develop an algorithm for third-person imitation learning. Future advancements in this class of algorithms would significantly improve the state of robotics, because it will enable people to easily teach robots news skills and abilities. Importantly, we want our algorithm to be unsupervised: it should be able to observe another agent perform a task, infer that there is an underlying correspondence to itself, and find a way to accomplish the same task.
We offer an approach to this problem by borrowing ideas from domain confusion  and generative adversarial networks (GANs) Goodfellow et al. (2014). The high-level idea is to introduce an optimizer under which we can recover both a domain-agnostic representation of the agent's observations, and a cost function which utilizes this domain-agnostic representation to capture the essence of expert trajectories. We formulate this as a third-person RL-GAN problem, and our solution builds on the first-person RL-GAN formulation by Ho & Ermon (2016).
Surprisingly, we find that this simple approach has been able to solve the problems that are presented in this paper (illustrated in Figure 1), even though the student's observations are related in a complicated way to the teacher's demonstrations (given that the observations and the demonstrations are pixel-level). As techniques for training GANs become more stable and capable, we expect our algorithm to be able to infer solve harder third-person imitation tasks without any direct supervision. Figure 1: From left to right, the three domains we consider in this paper: pointmass, reacher, and pendulum. Top-row is the third-person view of a teacher demonstration. Bottom row is the agent's view in their version of the environment. For the point and reacher environments, the camera angles differ by approximately 40 degrees. For the pendulum environment, the color of the pole differs.

RELATED WORK
Imitation learning (also learning from demonstrations or programming by demonstration) considers the problem of acquiring skills from observing demonstrations. Imitation learning has a long history, with several good survey articles, including (Schaal, 1999;Calinon, 2009;Argall et al., 2009). Two main lines of work within imitation learning are: 1) behavioral cloning, where the demonstrations are used to directly learn a mapping from observations to actions using supervised learning, potentially with interleaving learning and data collection (e.g., Pomerleau (1989); Ross et al. (2011)). 2) Inverse reinforcement learning (Ng et al., 2000), where a reward function is estimated that explains the demonstrations as (near) optimal behavior. This reward function could be represented as nearness to a trajectory (Calinon et al., 2007;Abbeel et al., 2010), as a weighted combination of features (Abbeel & Ng, 2004;Ratliff et al., 2006;Ramachandran & Amir, 2007;Ziebart et al., 2008;Boularias et al., 2011;Kalakrishnan et al., 2013;Doerr et al., 2015), or could also involve feature learning (Ratliff et al., 2007;Levine et al., 2011;Wulfmeier et al., 2015;Ho & Ermon, 2016). This past work, however, is not directly applicable to the third person imitation learning setting. In third-person imitation learning, the observations and actions obtained from the demonstrations are not the same as what the imitator agent will be faced with. A typical scenario would be: the imitator agent watches a human perform a demonstration, and then has to execute that same task. As discussed in Nehaniv & Dautenhahn (2001) the "what and how to imitate" questions become significantly more challenging in this setting. To directly apply existing behavioral cloning or inverse reinforcement learning techniques would require knowledge of a mapping between observations and actions in the demonstrator space to observations and actions in the imitator space. Such a mapping is often difficult to obtain, and it typically relies on providing feature representations that captures the invariance between both environments Carpenter et al. (2002); Shon et al. (2005);Calinon et al. (2007); Nehaniv (2007); Gioioso et al. (2013); Gupta et al. (2016). Contrary to prior work, we consider third-person imitation learning from raw sensory data, where no such features are made available.
The most closely related work to ours is by ; Ho & Ermon (2016); Wulfmeier et al. (2015), who also consider inverse reinforcement learning directly from raw sensory data. However, the applicability of their approaches is limited to the first-person setting. Indeed, matching raw sensory observations is impossible in the 3rd person setting.
Our work also closely builds on advances in generative adversarial networks Goodfellow et al. (2014), which are very closely related to imitation learning as explained in ; Ho & Ermon (2016). In our optimization formulation, we apply the gradient flipping technique from Ganin & Lempitsky (2014).  Long & Wang (2015). It has also been shown that features trained in one domain can often be relevant to other domains Donahue et al. (2014). The work most closely related to ours is , who also consider an explicit domain confusion loss, forcing trained classifiers to rely on features that don't allow to distinguish between two domains. This work in turn relates to earlier work by Bromley et al. (1993); Chopra et al. (2005), which also considers supervised training of deep feature embeddings.
Our approach to third-person imitation learning relies on reinforcement learning from raw sensory data in the imitator domain. Several recent advances in deep reinforcement learning have made this practical, including Deep Q-Networks (Mnih et al., 2015), Trust Region Policy Optimization (Schulman et al., 2015a), A3C Mnih et al. (2016), and Generalized Advantage Estimation (Schulman et al., 2015b). Our approach uses Trust Region Policy Optimization.

BACKGROUND AND PRELIMINARIES
A discrete-time finite-horizon discounted Markov decision process (MDP) is represented by a tuple M = (S, A, P, r, ρ 0 , γ, T ), in which S is a state set, A an action set, P : S × A × S → R + a transition probability distribution, r : S × A → R a reward function, ρ 0 : S → R + an initial state distribution, γ ∈ [0, 1] a discount factor, and T the horizon.
In the reinforcement learning setting, the goal is to find a policy π θ : S × A → R + parametrized by θ that maximizes the expected discounted sum of rewards incurred, η(π In the (first-person) imitation learning setting, we are not given the reward function. Instead we are given traces (i.e., sequences of states traversed) by an expert who acts according to an unknown policy π E . The goal is to find a policy π θ that performs as well as the expert against the unknown reward function. It was shown in Abbeel & Ng (2004) that this can be achieved through inverse reinforcement learning by finding a policy π θ that matches the expert's empirical expectation over discounted sum of all features that might contribute to the reward function. The work by Ho & Ermon (2016) generalizes this to the setting when no features are provided as follows: Find a policy π θ that makes it impossible for a discriminator (in their work a deep neural net) to distinguish states visited by the expert from states visited by the imitator agent. This can be formalized as follows: (1) Here, the expectations are over the states experienced by the policy of the imitator agent, π θ , and by the policy of the expert, π E , respectively. D R is the discriminator, which outputs the probability of a state having originated from a trace from the imitator policy π θ . If the discriminator is perfectly able to distinguish which policy originated state-action pairs, then D R will consistently output a probability of 1 in the first term, and a probability of 0 in the second term, making the objective its lowest possible value of zero. It is the role of the imitator agent π θ to find a policy that makes it difficult for the discriminator to make that distinction. The desired equilibrium has the imitator agent making it impractical for the discriminator to distinguish, hence forcing the discriminator to assign probability 0.5 in all cases. Ho & Ermon (2016) present a practical approach for solving this type of game when representing both π θ and D R as deep neural networks. Their approach repeatedly performs gradient updates on each of them. Concretely, for a current policy π θ traces can be collected, which together with the expert traces form a data-set on which D R can be trained with supervised learning minimizing the negative log-likelihood (in practice only performing a modest number of updates). For a fixed D R , this is a policy optimization problem where − log D R (s, a) is the reward, and policy gradients can be computed from those same traces. Their approach uses trust region policy optimization (Schulman et al., 2015a) to update the imitator policy π θ from those gradients.
In our work we will have more terms in the objective, so for compactness of notation, we will realize the discriminative minimization from Eqn.
(1) as follows: Where s i is state i, c i is the correct class label (was the state s i obtained from an expert vs. from a non-expert), and CE is the standard cross entropy loss.

A FORMAL DEFINITION OF THE THIRD-PERSON IMITATION LEARNING PROBLEM
Formally, the third-person imitation learning problem can be stated as follows. Suppose we are given two Markov Decision Processes M π E and M π θ . Suppose further there exists a set of traces ρ = {(s 1 , . . . , s n )} n i=0 which were generated under a policy π E acting optimally under some unknown reward R π E . In third-person imitation learning, one attempts to recover by proxy through ρ a policy π θ = f (ρ) which acts optimally with respect to R π θ .

GAME FORMULATION
In this section, we discuss a simple algorithm for third-person imitation learning. This algorithm is able to successfully discriminate between expert and novice policies, even when the policies are executed under different environments. Subsequently, this discrimination signal can be used to train expert policies in new domains via RL by training the novice policy to fool the discriminator, thus forcing it to match the expert policy.
In third-person learning, observations are more typically available rather than direct state access, so going forward we will work with observations o t instead of states s t as representing the expert traces. The top row of Figure 8 illustrates what these observations are like in our experiments.
We begin by recalling that in the algorithm proposed by Ho & Ermon (2016)

the loss in Equation 2
is utilized to train a discriminator D R capable of distinguishing expert vs non-expert policies. Unfortunately, (2) will likely fail in cases when the expert and non-expert act in different environments, since D R will quickly learn these differences and use them as a strong classification signal.
To handle the third-person setting, where expert and novice are in different environments, we consider that D R works by first extracting features from o t , and then using these features to make a classification. Suppose then that we partition D R into a feature extractor D F and the actual classifier which assigns probabilities to the outputs of D F . Overloading notation, we will refer to the classifier as D R going forward. For example, in case of a deep neural net representation, D F would correspond to the earlier layers, and D R to the later layers. The problem is then to ensure that D F contains no information regarding the rollout's domain label d (i.e., expert vs. novice domain). This can be realized as Where MI is mutual information and hence we have abused notation by using D R , D F , and d to mean the classifier, feature extractor, and the domain label respectively as well as distributions over these objects.
The mutual information term can be instantiated by introducing another classifier D D , which takes features produced by D F and outputs the probability that those features were produced by in the expert vs. non-expert environment. (See Bridle et al. (1992); Barber & Agakov (2005) In words, we wish to minimize class loss while maximizing domain confusion.
Often, it can be difficult for even humans to judge a static image as expert vs. non-expert because it does not convey any information about the environmental change affected by the agent's actions. For example, if a pointmass is attempting to move to a target location and starts far away from its goal state, it can be difficult to judge if the policy itself is bad or the initialization was simply unlucky. In response to this difficulty, we give D R access to not only the image at time t, but also at some future time t + n. Define σ t = D F (o t ) and σ t+n = D F (o t+n ). The classifier then makes a prediction D R (σ t , σ t+n ) =ĉ .
This renders the following formulation: Note we also want to optimize over D F , the feature extractor, but it feeds both into D R and into D D , which are competing (hidden under σ), which we will address now.
To deal with the competition over D F , we introduce a function G that acts as the identity when moving forward through a directed acyclic graph and flips the sign when backpropagating through the graph. This technique has enjoyed recent success in computer vision. See, for example, (Ganin & Lempitsky, 2014). With this trick, the problem reduces to its final form In Equation (5), we flip the gradient's sign during backpropagation of D F with respect to the domain classification loss. This corresponds to stochastic gradient ascent away from features that are useful for domain classification, thus ensuring that D F produces domain agnostic features. Equation 5 can be solved efficiently with stochastic gradient descent. Here λ is a hyperparameter that determines the trade-off made between the objectives that are competing over D F .
To ensure sufficient signal for discrimination between expert and non-expert, we collect third-person demonstrations in the expert domain from both an expert and from a non-expert.
Our complete formulation is graphically summarized in Figure 2. During backpropogation, the sign on the domain loss L D is flipped to destroy information that was useful for distinguishing the two domains. This ensures that the feature extractor F is domain agnostic. Finally, the classes probabilities that were computed using this domain-agnostic feature vector are utilized as a cost signal in TRPO; which is subsequently utilized to train the novice policy to take expert-like actions and collect further rollouts.

ALGORITHM
To solve the game formulation in Equation (5) Our generator (π θ ) step is similar to the generator step in the algorithm by (Ho & Ermon, 2016). We simply use − log D R as the reward. Using policy gradient methods (TRPO), we train the generator to minimize this cost and thus push the policy further towards replicating expert behavior. Once the generator step is done, we start again with the discriminator step. The entire process is summarized in algorithm 1.

EXPERIMENTS
We seek to answer the following questions through experiments: 1. Is it possible to solve the third-person imitation learning problem in simple settings? I.e., given a collection of expert image-based rollouts in one domain, is it possible to train a policy in a different domain that replicates the essence of the original behavior?
2. Does the algorithm we propose benefit from both domain confusion and velocity?
3. How sensitive is our proposed algorithm to the selection of hyper-parameters used in deployment?
4. How sensitive is our proposed algorithm to changes in camera angle?
5. How does our method compare against some reasonable baselines?
Algorithm 1 A third-person imitation learning algorithm. 1: Let CE be the standard cross entropy loss. 2: Let G be a function that flips the gradient sign during backpropogation and acts as the identity map otherwise. 3: Initialize two domains, E and N for the expert and novice. 4: Initialize a memory bank Ω of expert success and of failure in domain E. Each trajectory ω ∈ Ω comprises a rollout of images o = o 1 , . . . , o t , . . . o n , a class label c , and a domain label d . 5: Initialize D = D F , D R , D D , a domain invariant discriminator. 6: Initialize a novice policy π θ . 7: Initialize numiters, the number of inner policy optimization iterations we wish to run. 8: for iter in numiters do 9: Sample a set of successes and failures ω E from Ω.  Collect on policy samples ω N from π θ .

31:
end for 32: end for 33: end for 34: return optimized policy π θ 6.1 ENVIRONMENTS To evaluate our algorithm, we consider three environments in the MuJoCo physics simulator. There are two different versions of each environment, an expert variant and a novice variant. Our goal is to train a cost function that is domain agnostic, and hence can be trained with images on the expert domain but nevertheless produce a reasonable cost on the novice domain. See Figure 1 for a visualization of the differences between expert and novice environments for the three tasks.
Point: A pointmass attempts to reach a point in a plane. The color of the target and the camera angle change between domains.
Reacher: A two DOF arm attempts to reach a designated point in the plane. The camera angle, the length of the arms, and the color of the target point are changed between domains. Note that changing the camera angle significantly alters the image background color from largely gray to roughly 30 percent black. This presents a significant challenge for our method.
Inverted Pendulum: A classic RL task wherein a pendulum must be made to balance via control. For this domain, We only change the color of the pendulum and not the camera angle. Since there is no target point, we found that changing the camera angle left the domain invariant representations with too little information and resulted in a failure case. In contrast to some traditional renderings of this problem, we do not terminate an episode when the agent falls but rather allow data collection to continue for a fixed horizon.

EVALUATIONS
Is it possible to solve the third-person imitation learning problem in simple settings? In Figure 3, we see that our proposed algorithm is indeed able to recover reasonable policies for all three tasks we examined. Initially, the training is quite unstable due to the domain confusion wreaking havoc on the learned cost. However, after several iterations the policies eventually head towards reasonable local minima and the standard deviation over the reward distribution shrinks substantially. Finally, we note that the extracted feature representations used to complete this task are in fact domain-agnostic, as seen in Figure 9. Hence, the learning is properly taking place from a third-person perspective.  Does the algorithm we propose benefit from both domain confusion and the multi-time step input? We answer this question with the experiments summarized in Figure 5. This experiment compares our approach with: (i) our approach without the domain confusion loss; (ii) our approach without the multi-time step input; (iii) our approach without the domain confusion loss and without the multitime step input (which is very similar to the approach in Ho & Ermon (2016)). We see that adding domain confusion is essential for getting strong performance in all three experiments. Meanwhile, adding multi-time step input marginally improves the results. See also Figure 7 for an analysis of the effects of multi-time step input on the final results. How sensitive is our proposed algorithm to the selection of hyper-parameters used in deployment? Figure 6 shows the effect of the domain confusion coefficient λ, which trades off how much we should weight the domain confusion objective vs. the standard cost-recovery objective, on the final performance of the algorithm. Setting λ too low results in slower learning and features that are not domain-invariant. Setting λ too high results in an objective that is too quick to destroy information, which makes it impossible to recover an accurate cost.
For multi-time step input, one must choose the number of look-ahead frames that are utilized. If too small a window is chosen, the agent's actions have not affected a large amount of change in the environment and it is difficult to discern any additional class signal over static images. If too large a time-frame passes, causality becomes difficult to interpolate and the agent does worse than simply being trained on static frames. Figure 7 illustrates that no number of look-ahead frames is consistently optimal across tasks. However, a value of 4 showed good performance over all tasks, and so this value was utilized in all other experiments.  How sensitive is our algorithm to changes in camera angle? We present graphs for the reacher and point experiments wherein we exam the final reward obtained by a policy trained with thirdperson imitation learning vs the camera angle difference between the first-person and third-person perspective. We omit the inverted double pendulum experiment, as the color and not the camera angle changes in that setting and we found the case of slowly transitioning the color to be the definition of uninteresting science. Figure 8: Point and reacher final reward after 20 epochs of third-person imitation learning vs the camera angle difference between the first and third-person perspective. We see that the point follows a fairly linear slope in regards to camera angle differences, whereas the reacher environment is more stochastic against these changes. Figure 9: Learning curves for third-person imitation vs. three baselines: 1)RL with true reward, 2) first-person imitation, 3) attempting to use first-person features on the third-person agent.
How does our method compare against reasonable baselines? We consider the following baselines for comparisons against third-person imitation learning. 1) Standard reinforcement learning with using full state information and the true reward signal. This agent is trained via TRPO. 2) Standard GAIL (first-person imitation learning). Here, the agent receives first-person demonstration and attempts to imitate the correct behavior. This is an upper bound on how well we can expect to do, since we have the correct perspective. 3) Training a policy using first-person data and applying it to the third-person environment.
We compare all three of these baselines to third-person imitation learning. As we see in figure  9: 1) Standard RL, which (unlike the imitation learning approaches) has access to full state and true reward, helps calibrate performance of the other approaches. 2) First-person imitation learning is faced with a simpler imitation problem and accordingly outperforms third-person imitation, yet third-person imitation learning is nevertheless competitive. 3) Applying the first-person policy to the third-person agent fails miserably, illustrating that explicitly considering third-person imitation is important in these settings.
Somewhat unfortunately, the different reward function scales make it difficult to capture information on the variance of each learning curve. Consequently, in Appendix A we have included the full learning curves for these experiments with variance bars, each plotted with an appropriate scale to examine the variance of the individual curves.

DISCUSSION AND FUTURE WORK
In this paper, we presented the problem of third-person imitation learning. We argue that this problem will be important going forward, as techniques in reinforcement learning and generative adversarial learning improve and the cost of collecting first-person samples remains high. We presented an algorithm which builds on Generative Adversarial Imitation Learning and is capable of solving simple third-person imitation tasks.
One promising direction of future work in this area is to jointly train policy features and cost features at the pixel level, allowing the reuse of image features. Code to train a third person imitation learning agent on the domains from this paper is presented here: https://github.com/bstadie/ third_person_im Figure 11: Reacher performance under a policy trained on RL, first-person imitation learning, thirdperson imitation, and a first-person policy applied to a third-person agent. Figure 12: Point performance under a policy trained on RL, first-person imitation learning, thirdperson imitation, and a first-person policy applied to a third-person agent. 9 APPENDIX B: ARCHITECTURE PARAMETERS Joint Feature Extractor: Input is images are size 50 x 50 with 3 channels, RGB. Layers are 2 convolutional layers each followed by a max pooling layer of size 2. Layers use 5 filters of size 3 each.
Domain Discriminator and the Class Discriminator: Input is domain agnostic output of convolutional layers. Layers are two feed forward layers of size 128 followed by a final feed forward layer of size 2 and a soft-max layer to get the log probabilities.
ADAM is used for discriminator training with a learning rate of 0.001. The RL generator uses the off-the-shelf TRPO implementation available in RLLab.


A Summary Of The Kernel Matrix, And How To Learn It Effectively Using Semidefinite Programming

Kernel-based learning algorithms are widely used in machine learning for problems that make use of the similarity between object pairs. Such algorithms first embed all data points into an alternative space, where the inner product between object pairs specifies their distance in the embedding space. Applying kernel methods to partially labeled datasets is a classical challenge in this regard, requiring that the distances between unlabeled pairs must somehow be learnt using the labeled data. In this independent study, I will summarize the work of G. Lanckriet et al.'s work on"Learning the Kernel Matrix with Semidefinite Programming"used in support vector machines (SVM) algorithms for the transduction problem. Throughout the report, I have provide alternative explanations / derivations / analysis related to this work which is designed to ease the understanding of the original article.

of the embedding space. The importance of this lies in the fact that since kernel-based learning algorithms extract all information needed from inner products of training data points in F, there is no need to learn a kernel function Φ over the entire sample space to specify the embedding of a finite training dataset. Instead, the finite-dimensional kernel matrix (also known as a Gram matrix ) that contains the inner products of training points in F is sufficient. There are, of course, statistical model selection problems to be addressed within this approach; in particular "which projected space efficiently linearly separates the data?" and consequently "which kernel should we use?". The answers to these questions determines the elements of the kernel matrix. While prior knowledge can be used to aid this kernel selection process (to some degree of success), G. Lanckriet et al. propose a method to learning the kernel matrix from data using semidefinite programming (SDP) techniques.
In their report, the main focus is on the problem of transduction -the problem of completing the labeling of a partially labeled dataset. Keep in mind that the unlabeled samples of the dataset for which the algorithm is to find a label, are specified a priori. Once again, this suggests that the algorithm need only to learn a set of entries in the Gram matrix, and not the kernel function itself. This finite-dimensional kernel matrix uses the available labels to learn a good embedding by minimizing an objective function over the space of positive semidefinite kernels. This embedding should exhibit certain properties that aim to entangle the learning of labeled and unlabeled data. The resulting kernel matrix can then be employed as part of any algorithm that uses kernel matrices. One example that the authors discuss in detail is the support vector machine (SVM), where they show this method yields a polynomial time algorithm in the number of test examples, whereas Vapnik's original method for transduction [8] scales exponentially in the number of test examples.
2.1. Statement of Intent. In this paper, I shall summarize a formal proof for G. Lanckriet et al.'s work [1] on "Learning the Kernel Matrix with Semidefinite Programming". In Section 4, I formally define the concepts of kernel-based learning algorithms. In Section 5, we shall review the basics of semidefinite programming along with laying out dual formulations, in Section 6 we look into how SDP is used in finding the optimal kernel matrix. In this section, we also see a specific application of this framework for automatically learning the 2-norm soft margin parameter τ = 1/C. Finally, in Section 7, I shall summarize the works presented findings. I have attempted to prove and or elaborate on some skipped over derivations in the appendices.

Notation
In the derivations below, vectors are represented using bold lower-case notation, e.g, v ∈ R n , and scalar values represented using lower-case italics, e.g., v 1 , v 2 , ..., v n . Matrices are represented using upper-case italics, e.g., X ∈ R m×n . For a square, symmetric matrix X, X 0 means that X is positive semidefinite, while X 0 means that X is positive definite. For a vector v, the notations v ≥ 0 and v > 0 are understood componentwise.

Kernel Methods
Kernel-based learning algorithms [2][3][4] work by taking the data from the input space X and embedding into a feature space F, then searching for linear relations in the resultant space. Kernel-based learning algorithms perform this embedding implicitly, forgoing the need to explicitly specify the function Φ : X → F and instead by requiring that pair-wise distances between each pair of points is specified (as given by their inner product). A primary advantange of this approach is that computing inner products in a feature space F is often much easier than computing the coordinates of the points themselves.
where Φ is a mapping from X to an (inner product) feature space F.
for some x 1 , · · · , x n ∈ X and some kernel function k. The kernel matrix is also known as the Gram marix.
In this paper and in the context of transduction, we are given a finite dataset X , and so the kernel matrix is finite and can specified in the following simple manner Proposition 1 Every positive semidefinite and symmtetric matrix is a kernel matrix. Conversely, every kernel matrix is symmetric and positive semidefinite. 1 Kernel-based algorithms such as Support vector machines seek out solutions that are affine functions in the feature space f (x) = w, Φ(x) + b for some weight vector w ∈ F. As long as the weight vector w can be expressed as a linear combination of the inputs For example in binary classification, a thresholded version of f (x), i.e. sign f (x) is used to classify objects as belonging to one class or another. Note, in the examples and proofs that follow, we assume maximum-margin classifiers are learning the best separating hyperplanes for accurately separating objects from two classes. As for multi-class margins, two prominent 1 Proof: Considering the general case of a kernel matrix, let Furthermore, kernel-based algorithms such as SVMs are so-called maximum margin (γ) classifiers, trying to find the boundary that has the most distance between objects of different classes. In Figure 1 we see various separating boundaries that cleanly divide objects from different classes into their corresponding buckets, but only the margin that has the maximum distance from objects of both class is chosen as the maximum-margin boundary, as it allows for more robustness in the face of new datapoints that may lie too close to the separating boundary. Geometrically, γ corresponds to the distance between the convex hulls of the each of the two classes [9] As is evident from Figure 1, the margin is inversly related to weights vector defining the separating boundary: margin = γ = 2 ||w|| 2 and so maximizing the margin is equivalent to minimizing this weight vector min w,b As discussed above, kernel methods attempt to find a function that is linear in the feature space F accurately separating instances of separate classes onto one or the other side of the function. In order for separating boundary to correctly find a boundary separating all samples, the optimization problem must optimize some criterion over all samples (i.e., each sample should somehow be included as a constraint). Here we look into several such criteria all of which are considered measures of separation of the labeled data. In addition to wanting to maximize the margin between objects of the two classes, kernel methods may allow a tolerance for misclassification. If no tolerance is allowed, the classifier is known as hard margin, whereas soft margin classifiers are those kernel methods that allow for misclassifications as incorporated in their optimization setup. Below we look into 3 criteria corresponding to different mesaures of separation / measures of performance.
Definition 3: Hard Margin Given a set S l = (x 1 , y 1 ), · · · , (x n , y n ) with labeled examples, the hyperplane (w * , b * ) that solves the optimization problem below realizes the maximal margin classifier with geometric margin γ = 1/||w * || 2 (assuming it exists). This margin is called the hard margin.
Primal formulation: Dual formulation 2 : , e is the n-vector of ones, α ∈ R n , and y = [y 1 , · · · , y n ] T . The n constraints in the primal follow straight from the fact that SVM would like to find a separable boundary that correctly (or with some margin of error) places each example on the proper side of the separable boundary; this means that each of the n datapoints must be evaluated against the boundary that the optimzation problem finds.
We observe that the optimization problem finds a solution ω H (K) to the hard margin problem if and only if the data is linearly separable in the transformed feature space F of the transformed datapoints, φ(x i ). As seen in practice, this may not hold, and so we look for an alternative optimization problem that allows for a some error. For this, we define the 1-norm and 2-norm soft margin problems as follows.
Primal formulation: Dual formulation: Intuitively, while the 2-norm loss penalizes outliers more than the 1-norm loss and so has slower convergance rate, it is both convex and smooth and so desirable to be used alongside a range of optimization problems.

4.1.
Generalized Performance Measure. The 3 definitions above have shown various formulations (primal & dual) for finding the optimal separating margin γ. Noting the similarities in the 3 dual formulations above, we define the generalized performance measure as Observe that each of the 3 formulations above are a special case of this general problem: . Given a kernel matrix K, this general optimization problem is able to find optimal parameters (i.e., w * , b * ) that result in the maximum margin γ between the samples, where pair-wise distances in the transformed feature space F are captured in K. As alluded to earlier, in the setting of transduction, we are not given labels for all samples, and so we cannot possibly have an accurate K. We can easily see that to find the maximum margin separator in a transduction setting, we are first required to search over a set K of kernel matrices K, and find the maximum margin for each K. We can alternatively think of this as finding the minimum ω C,τ (K) over all possible K matrices.
In the next sections, we shall describe the assumptions that assist in solving such a meta-/ nested optimization problem. First, we will review semidefinite programs, a partitcular type of optimization problem with special structure for which exists theoretically and emperically efficient interior-point algorithms to solve.

Semidefinite Programming
Semidefinite programming [10][11][12] deals with the optimization of convex functions over the convex cone of symmetric, positive semidefinite matrices P = X ∈ R p×p X = X T , X 0 or affine subsets thereof, characterized by affine or convex constraints on the optimization problem. As mentioned in the previous section, we aim to find an optimal kernel matrix K for the task of transduction, and P (and convex subsets of P) can be viewed as a search space for such possible kernel matrices. The key consideration in this paper is to specify a convex cost function that will enable us to find / learn the optimal kernel matrix using semidefinite programming.
where u ∈ R q is the vector of decision variables, c ∈ R q is the objective vector, and matrices F j i = (F j i ) T ∈ R p×p are given. An important property of each "linear matrix inequality" (LMI) F j (u) is that the set of u satisfying the LMI is a convex set. This property of each LMI constraint, along with the convexity of the affine constraint Au = b leads to the SDPs being a convex optimization problem. This seemingly specialized form of SDPs is important as it arises in a host of applications in optimization problems (either directly in this form, or through casting problems as an SDP using the Schur's Complement Lemma 3 ), and because there exist theoretically and emperically efficient interior-point algorithms to solve SDPs [11]. 3 Lemma 1 (Schur Complement Lemma) Consider the partitioned symmetric matrix where A, C are square and symmetric. If det(A) = 0, we define the schur complement of A in X by the matrix S = C − B T A −1 B. The Schur Complement Lemma states the following: Dual formulation: where Z is a symmetric matrix, of the same size as F (u). Observe that the Lagrangian function L(u, Z) = c T u + trace(ZF (u)) does indeed fullfill the same objective as the primal SDP formulation as we can see that where we have shown the above is a barrier for the primal SDP. As in non-SDP duality, we always have weak duality and can exchange the min and max to get We further have strong duality with a Slater-type condition stating that if the primal SDP is strictly feasible (i.e., ∃ u 0 s.t. F (u 0 ) ≺ 0) then p * = d * . Additionally, if the dual SDP 5 is also strictly feasible (i.e., ∃ Z 0 s.t. c i = −trace(ZF i ) ∀ i ∈ [q]), then both primal and dual optimal values are attained by the same optimal pair (u * , Z * ). 4 In the general case, an SDP with multiple LMI constraints and affine equilities can be reduced to the aforementioned form by elimination of affine constraints, and merging all LMIs into 1 using block matrices. 5 The dual is as follows: which can be re-written as the following problem.
which itself is an SDP. So the dual of a primal SDP is an SDP. We explain why this is important in the text.
We have seen that the primal and dual pair of an SDP are both SDPs, and assuming strict feasibility of both problems, solving the primal minimization problem and maximizing the dual problem are equivalent. This relationship is indeed what algorithms such as SeDuMi [13] exploit to simultaneously solve both the primal and dual, and then use the duality gap p * −d * as a stopping criterion. Equipped with interior-point methods [10] for solving SDPs, these methods have a worst-case complexity of O(q 2 p 2.5 ) where p refers to the dimensionality of F (u) ∈ R p×p and q is the number of block matrices in the reduced LMI. In subsequent sections, we will explain how this bound may be improved assuming certain constraints on the SDP.

Algorithms for Learning Kernels
Working in a transduction setting, we are given data that is partially labeled; the training set S ntr = (x 1 , y 1 ), · · · , (x ntr , y ntr ) is labeled, and the remainder (i.e., test set) T nt = x ntr+1 , · · · , x ntr+nt are unlabeled, and the aim is to predict the labels for the test samples. In such a setting, the optimizing the kernel is equivalent to choosing a kernel matrix of form By setting up the optimization problem to optimize over the "training-data block" K tr , we want to learn the optimal "mixed-data block" K tr,t and "test-data block" K t . What we mean to say is that training and test data blocks must somehow be entangled: tuning the entries in K that correspond to training data (i.e., optimizing their embedding) should automatically tune the test-data entries in some way as well. This can be achieved by constraining the search for optimal kernel to only a certain category of kernels to prevent overfitting the training data, and generalize well to unlabeled test data. For this, the authors consider 3 specific example search spaces K: Example 1: K ∈ K K ⊆ P (convex subset) P: the PSD cone where in examples 2 & 3, the set K = K 1 , · · · , K m are initial "guesses" of the optimal kernel matrix K = Σ m i=1 µ i K i . These initial guesses, i.e., K i s, can be selected from the class of well-known kernel matrices, e.g., linear, Gaussian or polynomial kernels with different kernel parameter values (e.g., slack variables, Gaussian kernel width, polynomial kernel rank, etc.). Elements of K could be chosen as rank-one matrices K i = v i v i T with v i some set of orthogonal vectors, or alternatively K i s can be a diverse set of possibly good Gram matrices using various heterogeneous data sources. In any case, the set of such K i s, i.e., K, lies on the intersection of a low-dimensional linear subspace with the positive semidefinite cone P. Note, the constraints K ⊆ P and K 0 (identical constraints) both arise from Proposition 1 where kernel matrices are positive semidefinite by definition.
Formulating the optimal kernel K as a linear combination of K i s has the interesting consequence that the optimization problem that tries to learn K need only to find optimal mixing parameters µ i ∀ i ∈ [m], instead of fine-tuning the parameters of each of K i using cross-validation. We shall see that restricting the mixing parameters to be non-negative leads to significantly reduced computational complexity for the optimization problem.
6.1. General Optimization Problem. Recall from Section 4.1 where we derived generalized performance measure (i.e., the general dual formulation) for the optimization problem when using any of the kernel methods (i.e., hard margin, 1-norm soft margin or 2-norm soft margin) for transduction. This had the form An important property of the generalized performance measure above is its convexity in K. This can be asserted by considering first that the objective function 2α T e−α T (G(K)+τ I n )α is an affine (and hence convex) function of K. Secondly, ω C,τ (K) is the pointwise maximum of such conex functions, and so is also convex. The remainder of the constraints 0 ≤ α ≤ C and α T y = 0 are obviously convex. Hence the general optimization problem below that minimizes the performance measure over a family K of kernel matrices K is convex.
Recall that in an earlier part of Section 6 (this section), we described 3 examples for how to entangle the learning of the training-data and test-data blocks to learn labels for the unlabeled samples by imposing additional constraints on K. These special forms of K allow us to cast and solve the general optimization problem efficiently as the following SDP 6 General optimization problem: min where λ ∈ R and ν, δ ∈ R ntr . We note that ν ≥ 0 ⇐⇒ diag(ν) 0 which means that contraint is an LMI and a proper SDP constraint; likewise for ν ≥ 0.
We now look into the 3 specific forms of K described above and compare performances and expected outcome.
We notice that if K = K 0 , the optimization problem is indeed an SDP in standard form, however, there are no constraints guaranteeing entanglement of learning training-data and test-data blocks. For example, K t = O where K t is the test-data block and O denotes the zero matrix satisfies all constraints and is a viable solution to the minimization problem, yet it does not carry any meaning in terms of labels for unlabeled data. Below, we look into other kernel families K that can enforce the desired entangled learning.
Solving this optimization problem in its standard SDP form can be done using generalpurpose programs such as SeDuMi [13]. As discussed in Section 5.1, the interior-point methods used to solve SDP problems are polynomial in time, however, have worst case complexity O (m + n tr ) 2 )(n 2 + n 2 tr )(n + n tr ) 0.5 or roughly O (m + n tr ) 2 n 2.5 with the assumptions in example 2. This itself is a major improvement over Vapnik's original method for transduction [8] that scales exponentially in the number of test examples. 6.4. Example 3: K = span K 1 , · · · , K m ∩ K 0 & positive linear combinations. With the additional assumption on Σ m i=1 µ i K i that µ ≥ 0, we can derive the following 7 Optimization problem: min where r inR m and trace(K i ) = r i . This SDP form is more special. In fact, it is a quadratically-constrained quadratic probem (QCQP), itself a type of second-order cone program, which is a special type of SDP [12]. QCQPs can be solve efficiently using either of the SeDuMi [13] Mosek [14] frameworks, which yield worst-case complexity O mn 3 tr . This is a major improvement over the worst-case complexity of the previous example that didn't assume positive linear combinations, and over the general SDP form where K 0. Additionally this constraint results in improved numerical stability -it prevents the algorithm from finding solutions that use large weights µ i with opposite sign that cancel.
Observe that each of the 3 margin criteria (i.e., hard margin, 1-norm soft margin or 2-norm soft margin) is a special case of the generalized performance measure ω C,τ (K tr ): ω H (K) = ω ∞,0 (hard margin), ω S1 (K) = ω C,0 (1-norm soft margin), ω S2 (K) = ω ∞,τ = 1 C (2norm soft margin). These can be used in conjunction with the 3 assumptions on the kernel family K to get appropriate SDP setups for different margins based on the problem at hand. Here we consider 1 example, that was an important open problem at the time G. Lanckriet et al. were publishing their work. 6.5. Learning the 2-norm Soft Margin Parameter. This section shows how the 2-norm soft margin parameter τ = 1/C of SVMs can be learned using SDP or QCQP. For details, please refer to the work of the authors [1] or those of De Bie et al. [15]. Recall the specific form of the 2-norm soft margin problem: Dual formulation: where τ = 1/C. Remember τ = 0 for both the hard margin and 1-norm soft-margin cases. Since in the dual formulation above, the identity matrix induced by the 2-norm appears in exactly the same wasy as other matrices in G(K), we can treat them in the same way and jointly optimize over K and τ to find the optimal dual formulation, i.e., minimize ω S2 (K tr ). Now the joint optimization problem is as follows, and the dual can be restated as the following SDP (similar to derivations in Section 6.1): General optimization problem: min Standard SDP Form: min K,τ,ν,λ,t t subject to trace(K + τ I n ) = c, K ∈ K G(K tr ) + τ I ntr e + ν + λy (e + ν + λy) T t 0 Now we impose assumptions on the family K just as we did in example 2 (Section 6.3) and example 3 (Section 6.4): Notice how example 2 directly reduces to example 3 if K single 0 which means automatically tuning the parameter τ = 1/C for a 2-norm soft margin SVM with a singular kernel K single . This suggests that even if we are not learning the kernel matrix (i.e., K just equals K single and not K = Σ m i=1 µ i K i ), this approach can be used to tune the 2-norm soft margin parameter τ = 1/C automatically, thus solving an important open problem of its time.

Conclusion
In this summary paper, we have described an application of semidefinite programming (SDP) in learning the kernel matrix used for support vector machines (SVM) algorithms. We first reviewed the basics of kernels-based learning algorithms, saw 3 different formulations of SVMs (i.e., hard margin, 1-norm soft margin, and 2-norm soft margin) and derived the a general dual form for all 3 cases which we called the generalized performance measure. Minimizing this generalized performance measure corresponded to maximizing the margin of the SVM classifier. Next we studied the specialized yet commonplace form of SDPs and derived the corresponding dual formulation and saw that it is also an SDP. Using this property, we noted that the primal and dual can be jointly optimized using the same general purpose optimization solver, to more efficiently minimize the duality gap (p * − d * ) used as a stopping criterion. This solver jointly optimized the primal-dual pair with complexity O (m + n tr ) 2 n 2.5 . At this point we had the tools to solve our main optimization problem, which was minimizing the generalized performance measure over a family of kernel matrices K. Here we looked into 3 specific families, and demonstrated that when optimizing over a family of kernels that are strictly a positive linear combination of well-known kernel matrices, possibly from heterogeneous sources, leads to a significant improvement in both the complexity (which was O mn 3 tr ) and numerical stability of the optimal results. Finally, the formulations above were used to propose a method for finding the optimal 2-norm soft margin parameter τ = 1/C, which solved an open problem of its time.

Appendix A -Hard Margin Dual Formulation
We start with: min and derive: max where the constraints can be re-written in the proper form for deriving the dual formulation: Finally to simplify notation, we define z i = y i Φ(x i ) and Z = [z 1 ; · · · ; z n ] T and write the n constraints and write them together in the form and this can be done because by Slater's condition we can see that the original minimization problem is strictly feasible. Alternative, we can see that the objective function is convex in w and concave in α and so the switching of min and max is justified. After swapping max and min, we can solve the inner optimization problem by taking derivative and setting to 0: Plugging back into the inner optimization function (the min problem), we get note that we still have the conditions α ≥ 0 and α T y = 0 that are conditions for the outer optimization function (the max problem). So now the overall optimization problem becomes: note that we can re-write α T 1 − α T ZZ T α 2 as 1α T 1 − α T ZZ T α without affect the maximizer of the optimization problem. Furthermore, note that ZZ T = y i y j k(x i , x j ) which is what we defined to be G(K). So the final formulation becomes: which is what we set out to get as the derived dual formulation.
The same process above can extended to derive the dual derivation of the 1-norm and 2-norm soft margins with slack variables.

Appendix B -SDP Formulation for General Optimization Problem
Assuming K 0, K = m i=1 µ i K i,tr , µ ≥ 0 We begin by substituting ω C,τ (K tr ) into the general optimization problem to get min K max α:0≤α≤C,α T y=0 2α T e − α T G(K tr ) + τ I ntr α subject to trace(K) = c K 0 where the second constraint K 0 can be omitted as it is implied by the last two constraints.
Recall that r inR m and trace(K i ) = r i . So the above can be re-written as: 2α T e − τ α T α − max i c r i α T G(K i,tr )α with reasoning: • r1: interchanging the min & max is justified because the objective is linear in µ (hence convex) and concave in α • r2: G(K i,tr ) = diag(y)K i,tr diag(y) from definitin where G(K) is defined by G ij (K) = y i y j [K] ij = y i y j k(x i , x j ) This can finally be fomulated as: