jmlr jmlr2010 jmlr2010-14 knowledge-graph by maker-knowledge-mining

14 jmlr-2010-Approximate Riemannian Conjugate Gradient Learning for Fixed-Form Variational Bayes

Source: pdf

Author: Antti Honkela, Tapani Raiko, Mikael Kuusela, Matti Tornio, Juha Karhunen

Abstract: Variational Bayesian (VB) methods are typically only applied to models in the conjugate-exponential family using the variational Bayesian expectation maximisation (VB EM) algorithm or one of its variants. In this paper we present an efﬁcient algorithm for applying VB to more general models. The method is based on specifying the functional form of the approximation, such as multivariate Gaussian. The parameters of the approximation are optimised using a conjugate gradient algorithm that utilises the Riemannian geometry of the space of the approximations. This leads to a very efﬁcient algorithm for suitably structured approximations. It is shown empirically that the proposed method is comparable or superior in efﬁciency to the VB EM in a case where both are applicable. We also apply the algorithm to learning a nonlinear state-space model and a nonlinear factor analysis model for which the VB EM is not applicable. For these models, the proposed algorithm outperforms alternative gradient-based methods by a signiﬁcant margin. Keywords: variational inference, approximate Riemannian conjugate gradient, ﬁxed-form approximation, Gaussian approximation

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 The parameters of the approximation are optimised using a conjugate gradient algorithm that utilises the Riemannian geometry of the space of the approximations. [sent-16, score-0.404]

2 Keywords: variational inference, approximate Riemannian conjugate gradient, ﬁxed-form approximation, Gaussian approximation 1. [sent-21, score-0.252]

3 Most work on variational methods has focused on the class of conjugate exponential models for which simple EM-like learning algorithms can be derived easily (Ghahramani and Beal, 2001; Winn and Bishop, 2005). [sent-26, score-0.234]

4 After ﬁxing the functional form, we must be able to evaluate the variational free energy as a function of the variational parameters. [sent-42, score-0.329]

5 Once the free energy is known, we are left with a typically high-dimensional optimisation problem. [sent-47, score-0.246]

6 Here1 we propose using an approximate conjugate gradient algorithm that utilises the Riemannian geometry of the space of the approximations to speed up convergence. [sent-48, score-0.406]

7 This is in contrast to more common applications of Riemannian geometry in natural gradient methods using the geometry of the predictive model. [sent-50, score-0.306]

8 The geometry of the approximations is the natural choice if the variational inference is viewed as an optimisation problem in the space of approximating distributions. [sent-51, score-0.288]

9 The computational complexity of operations with the Fisher information matrix determining the geometry can be linear if the approximation is fully factorising or if its multivariate Gaussian blocks have a tree-like dependence structure, for instance. [sent-53, score-0.151]

10 The resulting algorithm can provide dramatic speedups of potentially several orders of magnitude over state-of-the-art Euclidean conjugate gradient methods. [sent-54, score-0.273]

11 In previous machine learning algorithms Riemannian geometry is usually invoked through the natural gradient of Amari (1998). [sent-55, score-0.216]

12 The proposed approximate Riemannian conjugate gradient learning algorithm is introduced in Section 3. [sent-63, score-0.273]

13 Background The approximate Riemannian conjugate gradient learning algorithm follows very naturally from an optimisation view of variational Bayes and the Riemannian geometry of probability distributions in information geometry. [sent-71, score-0.541]

15 The negative free energy also provides a lower bound on the marginal logX θξ likelihood, that is, log p(X ) ≥ −F (q(θ |ξ )) due to non-negativity of the KL-divergence. [sent-78, score-0.196]

16 This is often very challenging in practice, as the problems are quite high dimensional and the lack of speciﬁc knowledge of interactions of the parameters that deﬁne the geometry of the problem can seriously hinder generic optimisation tools. [sent-84, score-0.181]

17 Optimisation methods have included the conjugate gradient algorithm and heuristic speed-ups, but the use of a Riemannian conjugate gradient algorithm for VB as proposed in this paper is novel. [sent-90, score-0.546]

18 In practice, convergence of conjugate gradient algorithms in latent variable models is often really slow. [sent-91, score-0.348]

19 As we increase the number of observations, the gradient with respect to the parameters grows linearly, whereas the gradient with respect to the latent variables stays constant. [sent-93, score-0.304]

20 3237 H ONKELA , R AIKO , K UUSELA , T ORNIO AND K ARHUNEN As a result, with a reasonable number of observations, conjugate gradient algorithms are forced to take very small steps to avoid overshooting the parameters, and as a result the latent variables are hardly changed at all. [sent-94, score-0.325]

21 2 Information Geometry and Optimisation on Riemannian Manifolds When applying a generic optimisation algorithm to a problem such as optimising the free energy (1), a lot of background information on the geometry of the problem is lost. [sent-97, score-0.336]

22 For probability distributions, the most natural metric is given by the Fisher information ξ ξ gi j (ξ ) = Ii j (ξ ) = E θξ θξ ∂ log q(θ |ξ ) ∂ log q(θ |ξ ) ∂ξi ∂ξ j =E − θξ ∂2 log q(θ |ξ ) . [sent-107, score-0.147]

23 ξ In a Riemannian space, the direction of steepest ascent of a function F (ξ ) is given by the Riemannian or natural gradient ˜ ξ ξ ξ ∇F (ξ ) = G−1 (ξ )∇F (ξ ) (4) ξ ξ ξ instead of the regular gradient ∇F (ξ ). [sent-110, score-0.271]

24 The relation between gradient and Riemannian gradient is illustrated in Figure 1. [sent-112, score-0.252]

25 The Riemannian gradient strengthens the updates in the directions where the uncertainty is large. [sent-117, score-0.16]

26 the conjugate gradient algorithm with their Riemannian counterparts: Riemannian inner products and norms, parallel transport of gradient vectors between different tangent spaces as well as line searches and steps along geodesics in the Riemannian space. [sent-118, score-0.457]

27 We shall apply the approximate Riemannian conjugate gradient (RCG) method which implements Riemannian (natural) gradients, inner products and norms but uses ﬂat-space approximations of the others as our optimisation algorithm of choice throughout the paper. [sent-120, score-0.384]

28 The difference between gradient and conjugate gradient methods is illustrated in Figure 2. [sent-122, score-0.399]

29 3239 H ONKELA , R AIKO , K UUSELA , T ORNIO AND K ARHUNEN p gradient conjugate gradient Figure 2: Gradient and conjugate gradient updates are applied to ﬁnding the maximum of the posterior p(x, y) ∝ exp[−9(xy − 1)2 − x2 − y2 ]. [sent-126, score-0.744]

30 Note that the ﬁrst steps are the same, but following gradient updates are orthogonal whereas conjugate gradient ﬁnds a much better direction. [sent-128, score-0.433]

31 By embedding the VB-E step update within the VB-M step with point estimates and considering the resulting update, the VB EM algorithm for conjugate exponential family models can be interpreted as a natural gradient method (Sato, 2001). [sent-134, score-0.308]

32 It is worth pointing out that this correspondence of VB EM is with the regular natural gradient algorithm, not Riemannian (natural) conjugate gradients as proposed in this paper. [sent-137, score-0.273]

33 Approximate Riemannian Conjugate Gradient Learning for Fixed-Form VB θξ θξ Given a ﬁxed-form approximation q(θ |ξ ) and the free energy F (q(θ |ξ )), it is possible to use standard gradient-based optimisation techniques to minimise the free energy with respect to ξ . [sent-139, score-0.419]

34 Instead of a regular Euclidean gradient algorithm, we optimise the free energy using a conjugate gradient algorithm that is adapted to Riemannian space by using Riemannian inner products and norms instead of Euclidean ones. [sent-141, score-0.554]

35 We call this the (approximate) Riemannian conjugate gradient (RCG) algorithm. [sent-143, score-0.273]

36 Our RCG is an approximation of a true Riemannian conjugate gradient algorithm (Smith, 1993), in which the steps are taken along geodesic curves and tangent vectors evaluated at different points are transformed to the same tangent space using parallel transport along a geodesic. [sent-144, score-0.4]

37 (1998) showed that near the solution Riemannian conjugate gradient method differs from the ﬂat space version of conjugate gradient only by third order terms, and therefore both algorithms converge quadratically near the optimum. [sent-147, score-0.546]

38 The search direction for the RCG method is given by pk = −˜ k + βpk−1 , g ˜ ξ ˜ where gk = ∇F (ξ ) is the Riemannian gradient of Equation (4). [sent-149, score-0.4]

39 , 1998) e β= ˜ ˜ ˜ gk , gk − gk−1 k , ||˜ k−1 ||2 g k−1 (5) ˜ ˜ ˜ ˜ where ||˜ k ||2 = gk , gk k is the squared Riemannian norm of gk in the tangent space where gk is g k deﬁned, and x, y k denotes the Riemannian inner product of Equation (2) in the same tangent space. [sent-151, score-1.024]

40 We also apply a Riemannian version of the Powell-Beale restart method (Powell, 1977): the search direction is reset to the negative gradient direction if ˜ ˜ | gk−1 , gk k | ≥ 0. [sent-152, score-0.345]

41 g k (6) Compared to the traditional conjugate gradient, the Equations (5) and (6) are similar with just the dot products of the vectors replaced with Riemannian inner products. [sent-154, score-0.147]

42 The inputs include the probabilistic model p, the form of used posterior approximation q, the initialisations for the variational parameters ξ , and the data set X which is implicitly used in the objective function F . [sent-158, score-0.169]

43 1 Computational Considerations θξ The RCG method is efﬁcient as the geometry is deﬁned by the approximation q(θ |ξ ) and not the full Xθ θξ model p(X |θ ) as in typical natural gradient methods. [sent-161, score-0.234]

44 If the approximation q(θ |ξ ) is chosen such that disjoint groups of variables are independent, that is, θξ θ ξ q(θ |ξ ) = ∏ qi (θ i |ξ i ), i 3241 H ONKELA , R AIKO , K UUSELA , T ORNIO AND K ARHUNEN Algorithm 1 An outline of an example Riemannian conjugate gradient algorithm for ﬁxed-form VB. [sent-162, score-0.291]

45 All vector operations needed in the RCG algorithm are of the form ˜ ˜ gk , gl m = G−1 gk , G−1 gl k l m = gT G−T Gm G−1 gl k k l (7) for some iterate indices k, l, m. [sent-185, score-0.413]

46 In that case, it is most convenient to use a simple ﬁxed-point update rule for the covariance and a Riemannian conjugate gradient update only for the mean. [sent-194, score-0.374]

47 θξ Let us consider the optimisation of the free energy (1) when the approximation q(θ |ξ ) is a multivariate Gaussian. [sent-195, score-0.264]

48 The free energy can be decomposed as θξ F (q(θ |ξ )) = Eq(θ|ξ) log θξ θξ q(θ |ξ ) X θ p(X ,θ ) θξ X θ = Eq(θ |ξ ) {log q(θ |ξ )} + Eq(θ |ξ ) {− log p(X ,θ )} . [sent-196, score-0.237]

49 θξ 2 Straightforward differentiation yields a ﬁxed point update rule for the covariance (Lappalainen and Miskin, 2000; Opper and Archambeau, 2009): X θ Σ −1 = −2∇Σ Eq(θ |ξ ) {log p(X ,θ )} , θξ (8) where ∇Σ denotes the gradient with respect to Σ . [sent-198, score-0.192]

50 k n=1 k=1 The mixing coefﬁcients have a conjugate Dirichlet prior π πα p(π ) = Dir(π |α 0 ), where α 0 = [α0 , . [sent-236, score-0.147]

51 The resulting approximate posterior distributions are N K znk q(Z) = ∏ ∏ rnk (14) n=1 k=1 and K µ Λ πµΛ π µΛ π q(π ,µ ,Λ ) = q(π )q(µ ,Λ ) = q(π ) ∏ q(µ k ,Λ k ), k=1 where and π πα q(π ) = Dir(π |α ) (15) µ Λ µ Λ q(µ k ,Λ k ) = N (µ k |mk , (βkΛ k )−1 )W (Λ k |Wk , νk ). [sent-248, score-0.312]

52 Instead, the search direction is reset to the negative gradient direction 3246 R IEMANNIAN C ONJUGATE G RADIENT FOR VB √ after n iterations, where n is the number of parameters updated with the gradient method. [sent-257, score-0.309]

53 The optimisation is assumed to have converged when the improvement in free energy |F t − F t−1 | < ε for two consecutive iterations with ε being separately speciﬁed for each of the experiments below. [sent-258, score-0.246]

54 It can be seen that the standard gradient descent and conjugate gradient (CG) algorithms have problems locating even a decent optimum within a reasonable time. [sent-267, score-0.399]

55 This experiment was conducted using a fairly small number of observations, a lax convergence criterion and the maximum number of components K = 5 in order to allow the standard gradient to ﬁnish in a reasonable time. [sent-271, score-0.149]

56 It can be seen as a compromise between the fast converging but memory-intensive quasiNewton methods and the less efﬁcient conjugate gradient methods better suited for medium- to large-scale problems. [sent-275, score-0.273]

57 The algorithms compared are the standard gradient descent, the conjugate gradient (CG), the Riemannian gradient (RG) and the Riemannian conjugate gradient (RCG) methods as well as the limited-memory BFGS (L-BFGS) algorithm. [sent-292, score-0.798]

58 The smaller marks denote 25% and 75% quantiles of the termination time in the horizontal direction and the corresponding quantiles of the free energy at the median termination time in the vertical direction. [sent-294, score-0.232]

59 the other hand, the use of conjugate directions in the Riemannian space seems to result in a fairly uniform performance across all values of R. [sent-296, score-0.147]

60 8 1 R Figure 6: Comparison of VB EM with the Riemannian gradient (RG) and the Riemannian conjugate gradient (RCG) methods using the MoG model with the artiﬁcial data. [sent-308, score-0.399]

61 275 Final free energy 500 605 498 590 200 400 R=0. [sent-324, score-0.155]

62 425 870 808 Final free energy 500 1020 1050 1040 1010 1030 0 20 40 0 20 40 10 20 30 Convergence time (s) Convergence time (s) Convergence time (s) Figure 7: Final free energy value as a function of running time in the critical parameter range in the MoG experiment with varying R. [sent-334, score-0.31]

63 05 0 2000 4000 6000 8000 N 10000 12000 14000 Figure 8: Median convergence times of 30 simulations of the MoG model on artiﬁcial data as a function of the number of observations N with VB EM and the Riemannian conjugate gradient (RCG) algorithms. [sent-342, score-0.313]

64 Because of the nonlinearities the model is not in the conjugate exponential family, and the standard VB learning methods are only applicable to hyperparameters but not to the latent states or weights of the MLPs. [sent-355, score-0.199]

65 The free energy (1) can nevertheless be evaluated by linearising the MLP networks f and g (Honkela and Valpola, 2005; Honkela et al. [sent-356, score-0.155]

66 This allows evaluating the gradient with respect to ξS , ξ f , and ξ g and using a gradient based optimiser to adapt the parameters. [sent-358, score-0.252]

67 Combining Equations (4) and (12), the Riemannian gradient for the mean elements is given by ˜ ξ ξ ∇µ q F (ξ ) = Σ q ∇µ q F (ξ ), θξ where µ q is the mean of the variational approximation q(θ |ξ ) and Σ q is the corresponding covariance. [sent-359, score-0.231]

68 The covariance matrix of the model parameters is diagonal while the inverse covariance matrix of the latent states s(t) is block-diagonal with tridiagonal blocks. [sent-360, score-0.159]

69 A complete derivation of the free energy of the model is presented in Appendix C. [sent-363, score-0.155]

70 An algorithm was assumed to have converged when |F t − F t−1 | < ε = (10−5 N/80) for 5 consecutive iterations, where F t is the free energy at iteration t and N is the size of the data set. [sent-379, score-0.155]

71 In practice, the free energy values tend to have a very strong correlation with predictive performance of the model (Honkela et al. [sent-383, score-0.155]

72 These were ﬁltered by removing results where the attained free energy that was more than two RCG standard deviations worse than RCG average for the particular data set. [sent-386, score-0.155]

73 1 1 CPU time (h) 10 72 Figure 10: Comparison of the performance of the Riemannian conjugate gradient (RCG), the Riemannian gradient (RG), the conjugate gradient (CG) methods and the heuristic algorithm with the full speech data set of 1000 samples using the nonlinear state-space model. [sent-430, score-0.744]

74 The free energy F is plotted against computation time using a logarithmic time scale. [sent-431, score-0.155]

75 Discussion The proposed RCG algorithm combines two improvements over plain gradient optimisation: use of Riemannian gradient and conjugate gradients. [sent-437, score-0.399]

76 One interesting feature in the experimental results is the relative performance of the conjugate gradient and Riemannian gradient algorithms that implement only one of these. [sent-438, score-0.399]

77 Conjugate gradient is faster than Riemannian gradient for NFA, but the opposite is true for NSSM and MoG. [sent-439, score-0.252]

78 The experiments in this paper show that using even a greatly simpliﬁed variant of the Riemannian conjugate gradient method for some variables is enough to acquire a large speedup. [sent-454, score-0.273]

79 Considering univariate Gaussian distributions, the regular gradient is prone to overemphasise changes to model variables with small posterior variance and underemphasise variables with large posterior variance, as seen from Equations (9)–(11). [sent-455, score-0.202]

80 The posterior variance of latent variables is often much larger than the posterior variance of model parameters and the Riemannian gradient takes this into account in a very natural manner. [sent-456, score-0.254]

81 The Riemannian conjugate gradient method differs from Euclidean superlinear optimisation methods such as quasi-Newton methods in that it uses higher-order information of the geometry of the parameter space, but not of the function being optimised. [sent-457, score-0.454]

82 In this paper, we have presented a Riemannian conjugate gradient learning algorithm for ﬁxedform variational Bayes. [sent-460, score-0.36]

83 In practical examples, the Riemannian gradient approach provided several orders of magnitude speedups over conventional gradient algorithms, thus making VB learning of these models practical on a much larger scale. [sent-463, score-0.252]

84 Convergence of the Riemannian Conjugate Gradient Algorithm The Riemannian conjugate gradient algorithm has similar superlinear convergence properties to the ξ Euclidean space conjugate gradient algorithm. [sent-473, score-0.569]

85 Derivations of the Mixture-of-Gaussians Model In this section we present details of the variational MoG model, including necessary EM updates, the free energy and the metric tensor for the RCG algorithm. [sent-500, score-0.242]

86 dx ψ(x) = Using these deﬁnitions, the parameters rnk of the approximate posterior over latent variables q(Z) which are updated in the E-step are given by rnk = ρnk , K ∑l=1 ρnl where νk D ˜ ˜ 1/2 − (xn − mk )T Wk (xn − mk ) . [sent-505, score-0.652]

87 ρnk = πk Λk exp − 2βk 2 The parameters rnk are called responsibilities because they represent the responsibility the kth component takes in explaining the nth observation. [sent-506, score-0.334]

88 The responsibilities can be arranged into a matrix R = (rnk ) and will have to satisfy the following conditions 0 ≤ rnk ≤ 1, (20) ∑ rnk = 1. [sent-507, score-0.518]

89 Thus, the ﬁxed form posterior distributions are given by Equations (14), (15) and (16) and the free energy which is to be minimised by the RCG algorithm is given Equation (26). [sent-515, score-0.193]

90 In this work, we will only be optimising the responsibilities rnk and the means mk using gradient-based methods. [sent-516, score-0.357]

91 This can be enforced by using the softmax parametrisation rnk = eγnk . [sent-520, score-0.24]

92 ∑K eγnl l=1 (27) It can be easily seen that by using this parametrisation the responsibilities are always positive and ∑K rnk = 1. [sent-521, score-0.316]

93 As a results it holds that 0 ≤ rnk ≤ 1 and we can conduct unconstrained optimisation k=1 in the γ space. [sent-522, score-0.312]

94 Secondly, if we set the responsibilities rnk , n = 1 . [sent-523, score-0.297]

95 N are given by condition (21), that is rnK = 1 − ∑K−1 rnk . [sent-532, score-0.221]

96 As a result, the number k=1 of degrees of freedom in the responsibilities of the model is not the number of responsibilities NK but instead N(K − 1). [sent-533, score-0.152]

97 When we are using the parametrisation (27), this means that we can regard the parameters γnK as constants and only optimise the free energy with respect to parameters γnk , n = 1 . [sent-534, score-0.174]

98 Thus k=1 K ∆γnk )−1 and we can update the responsibilities cn can also be expressed in the form cn = (∑k=1 rnk e using the formula rnk e∆γnk ′ rnk = K . [sent-544, score-0.774]

99 3 The Free Energy In order to derive the value of the free energy (1), we note that θ θ θ F (q(θ )) = Eq(θ) {log q(θ )} + Eq(θ) {− log p(X,θ )} . [sent-566, score-0.196]

100 Information geometry of the EM and em algorithms for neural networks. [sent-587, score-0.222]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('riemannian', 0.453), ('rcg', 0.422), ('vb', 0.318), ('rnk', 0.221), ('honkela', 0.175), ('valpola', 0.162), ('gk', 0.162), ('conjugate', 0.147), ('em', 0.132), ('arhunen', 0.129), ('iemannian', 0.129), ('onkela', 0.129), ('ornio', 0.129), ('uusela', 0.129), ('gradient', 0.126), ('mog', 0.122), ('rg', 0.121), ('eq', 0.117), ('aiko', 0.11), ('onjugate', 0.104), ('energy', 0.102), ('nk', 0.099), ('optimisation', 0.091), ('geometry', 0.09), ('variational', 0.087), ('cg', 0.086), ('responsibilities', 0.076), ('pk', 0.074), ('radient', 0.072), ('mlp', 0.071), ('karhunen', 0.066), ('mk', 0.06), ('lappalainen', 0.053), ('nfa', 0.053), ('znk', 0.053), ('free', 0.053), ('latent', 0.052), ('doi', 0.048), ('nssm', 0.046), ('raiko', 0.045), ('log', 0.041), ('nl', 0.04), ('nonlinear', 0.04), ('wk', 0.038), ('kuusela', 0.038), ('posterior', 0.038), ('opper', 0.036), ('update', 0.035), ('archambeau', 0.035), ('bishop', 0.035), ('amari', 0.034), ('gaussian', 0.034), ('updates', 0.034), ('final', 0.032), ('transport', 0.032), ('speech', 0.032), ('covariance', 0.031), ('si', 0.031), ('fisher', 0.03), ('girolami', 0.03), ('tornio', 0.03), ('cpu', 0.027), ('tkk', 0.027), ('diag', 0.026), ('factorising', 0.026), ('initialisations', 0.026), ('dynamical', 0.026), ('tangent', 0.026), ('edelman', 0.025), ('geodesic', 0.025), ('gi', 0.024), ('gl', 0.024), ('convergence', 0.023), ('matti', 0.023), ('tridiagonal', 0.023), ('utilises', 0.023), ('bayesian', 0.023), ('median', 0.022), ('diagonal', 0.022), ('finland', 0.021), ('optima', 0.02), ('xk', 0.02), ('approximations', 0.02), ('antti', 0.019), ('juha', 0.019), ('parametrisation', 0.019), ('responsibility', 0.019), ('tapani', 0.019), ('direction', 0.019), ('search', 0.019), ('approximation', 0.018), ('quantiles', 0.018), ('exp', 0.018), ('euclidean', 0.018), ('attias', 0.018), ('enk', 0.018), ('wilcoxon', 0.018), ('simulations', 0.017), ('operations', 0.017), ('mv', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 14 jmlr-2010-Approximate Riemannian Conjugate Gradient Learning for Fixed-Form Variational Bayes

Author: Antti Honkela, Tapani Raiko, Mikael Kuusela, Matti Tornio, Juha Karhunen

2 0.075553551 92 jmlr-2010-Practical Approaches to Principal Component Analysis in the Presence of Missing Values

Author: Alexander Ilin, Tapani Raiko

Abstract: Principal component analysis (PCA) is a classical data analysis technique that Ä?Ĺš nds linear transformations of data that retain the maximal amount of variance. We study a case where some of the data values are missing, and show that this problem has many features which are usually associated with nonlinear models, such as overÄ?Ĺš tting and bad locally optimal solutions. A probabilistic formulation of PCA provides a good foundation for handling missing values, and we provide formulas for doing that. In case of high dimensional and very sparse data, overÄ?Ĺš tting becomes a severe problem and traditional algorithms for PCA are very slow. We introduce a novel fast algorithm and extend it to variational Bayesian learning. Different versions of PCA are compared in artiÄ?Ĺš cial experiments, demonstrating the effects of regularization and modeling of posterior variance. The scalability of the proposed algorithm is demonstrated by applying it to the NetÄ?Ĺš‚ix problem. Keywords: principal component analysis, missing values, overÄ?Ĺš tting, regularization, variational Bayes

3 0.072524697 95 jmlr-2010-Rademacher Complexities and Bounding the Excess Risk in Active Learning

Author: Vladimir Koltchinskii

Abstract: Sequential algorithms of active learning based on the estimation of the level sets of the empirical risk are discussed in the paper. Localized Rademacher complexities are used in the algorithms to estimate the sample sizes needed to achieve the required accuracy of learning in an adaptive way. Probabilistic bounds on the number of active examples have been proved and several applications to binary classiﬁcation problems are considered. Keywords: active learning, excess risk, Rademacher complexities, capacity function, disagreement coefﬁcient

4 0.070103578 23 jmlr-2010-Classification with Incomplete Data Using Dirichlet Process Priors

Author: Chunping Wang, Xuejun Liao, Lawrence Carin, David B. Dunson

Abstract: A non-parametric hierarchical Bayesian framework is developed for designing a classiﬁer, based on a mixture of simple (linear) classiﬁers. Each simple classiﬁer is termed a local “expert”, and the number of experts and their construction are manifested via a Dirichlet process formulation. The simple form of the “experts” allows analytical handling of incomplete data. The model is extended to allow simultaneous design of classiﬁers on multiple data sets, termed multi-task learning, with this also performed non-parametrically via the Dirichlet process. Fast inference is performed using variational Bayesian (VB) analysis, and example results are presented for several data sets. We also perform inference via Gibbs sampling, to which we compare the VB results. Keywords: classiﬁcation, incomplete data, expert, Dirichlet process, variational Bayesian, multitask learning

5 0.067140475 41 jmlr-2010-Gaussian Processes for Machine Learning (GPML) Toolbox

Author: Carl Edward Rasmussen, Hannes Nickisch

Abstract: The GPML toolbox provides a wide range of functionality for Gaussian process (GP) inference and prediction. GPs are speciﬁed by mean and covariance functions; we offer a library of simple mean and covariance functions and mechanisms to compose more complex ones. Several likelihood functions are supported including Gaussian and heavy-tailed for regression as well as others suitable for classiﬁcation. Finally, a range of inference methods is provided, including exact and variational inference, Expectation Propagation, and Laplace’s method dealing with non-Gaussian likelihoods and FITC for dealing with large regression tasks. Keywords: Gaussian processes, nonparametric Bayes, probabilistic regression and classiﬁcation Gaussian processes (GPs) (Rasmussen and Williams, 2006) have convenient properties for many modelling tasks in machine learning and statistics. They can be used to specify distributions over functions without having to commit to a speciﬁc functional form. Applications range from regression over classiﬁcation to reinforcement learning, spatial models, survival and other time series1 models. Predictions of GP models come with a natural conﬁdence measure: predictive error-bars. Although the implementation of the basic principles in the simplest case is straight forward, various complicating features are often desired in practice. For example, a GP is determined by a mean function and a covariance function, but these functions are mostly difﬁcult to specify fully a priori, and typically they are given in terms of hyperparameters, that is, parameters which have to be inferred. Another source of difﬁculty is the likelihood function. For Gaussian likelihoods, inference is analytically tractable; however, in many tasks, Gaussian likelihoods are not appropriate, and approximate inference methods such as Expectation Propagation (EP) (Minka, 2001), Laplace’s approximation (LA) (Williams and Barber, 1998) and variational bounds (VB) (Gibbs and MacKay, 2000) become necessary (Nickisch and Rasmussen, 2008). In case of large training data, approximations (Candela and Rasmussen, 2005) like FITC (Snelson and Ghahramani, 2006) are needed. The GPML toolbox is designed to overcome these hurdles with its variety of mean, covariance and likelihood functions as well as inference methods, while being simple to use and easy to extend. ∗. Also at Max Planck Institute for Biological Cybernetics, Spemannstraße 38, 72076 T¨ bingen, Germany. u 1. Note, that here we typically think of GPs with a more general index set than time. ©2010 Carl Edward Rasmussen and Hannes Nickisch. R ASMUSSEN AND N ICKISCH 1. Implementation The GPML toolbox can be obtained from http://gaussianprocess.org/gpml/code/matlab/ and also http://mloss.org/software/view/263/ under the FreeBSD license. Based on simple interfaces for covariance, mean, likelihood functions as well as inference methods, we offer full compatibility to both Matlab 7.x2 and GNU Octave 3.2.x.3 Special attention has been given to properly disentangle covariance, likelihood and mean hyperparameters. Also, care has been taken to avoid numerical inaccuracies, for example, safe likelihood evaluations for extreme inputs and stable matrix operations. For example, the covariance matrix K can become numerically close to singular making its naive inversion numerically unsafe. We handle these situations in a principled way4 such that Cholesky decompositions are computed of well-conditioned matrices only. As a result, our code shows a high level of robustness along the full spectrum of possible hyperparameters. The focus of the toolbox is on approximate inference using dense matrix algebra. We currently do not support covariance matrix approximation techniques to deal with large numbers of training examples n. Looking at the (growing) body of literature on sparse approximations, this knowledge is still somewhat in ﬂux, and consensus on the best approaches has not yet been reached. We provide stable and modular code checked by an exhaustive suite of test cases. A single function gp.m serves as main interface to the user—it can make inference and predictions and allows the mean, covariance and likelihood function as well as the inference methods to be speciﬁed freely. Furthermore, gp.m enables convenient learning of the hyperparameters by maximising the log marginal likelihood ln Z. One of the particularly appealing properties of GP models is that principled and practical approaches exist for learning the parameters of mean, covariance and likelihood functions. Good adaptation of such parameters can be essential to obtain both high quality predictions and insights into the properties of the data. The GPML toolbox is particularly ﬂexible, including a large library of different covariance and mean functions, and ﬂexible ways to combine these into more expressive, specialised functions. The user can choose between two gradient-based optimisers: one uses conjugate gradients (CG)5 and the other one relies on a quasi-Newton scheme.6 ∂ Computing the derivatives w.r.t. hyperparameters ∂θi ln Z with gp.m does not need any extra programming effort; every inference method automatically collects the respective derivatives from the mean, covariance and likelihood functions and passes them to gp.m. Our documentation comes in two pieces: a hypertext user documentation7 doc/index.html with examples and code browsing and a technical documentation8 doc/manual.pdf focusing on the interfaces and more technical issues. A casual user will use the hypertext document to quickly get his data analysed, however a power user will consult the pdf document once he wants to include his own mean, covariance, likelihood and inference routines or learn about implementation details. 2. 3. 4. 5. 6. 7. 8. Matlab is available from MathWorks, http://www.mathworks.com/. Octave is available from the Free Software Foundation, http://www.gnu.org/software/octave/. We do not consider the “blind” addition of a “small ridge” to K a principled way. Carl Rasmussen’s code is available at http://www.kyb.tuebingen.mpg.de/bs/people/carl/code/minimize/. Peter Carbonetto’s wrapper can be found at http://www.cs.ubc.ca/˜pcarbo/lbfgsb-for-matlab.html. Documentation can be found at http://www.gaussianprocess.org/gpml/code/matlab/doc/index.html. Technical docs are available at http://www.gaussianprocess.org/gpml/code/matlab/doc/manual.pdf. 3012 G AUSSIAN P ROCESSES FOR M ACHINE L EARNING T OOLBOX 2. The GPML Toolbox We illustrate the modular structure of the GPML toolbox by means of a simple code example. GPs are used to formalise and update knowledge about distributions over functions. A GP prior distribution on an unknown latent function f ∼ GP (mφ (x), kψ (x, x′ )), consists of a mean function m(x) = E[ f (x)], and a covariance function k(x, x) = E[( f (x) − m(x))( f (x′ ) − m(x′ ))], both of which typically contain hyperparameters φ and ψ, which we want to ﬁt in the light of data. We generally assume independent observations, that is, input/output pairs (xi , yi ) of f with joint likelihood Pρ (y|f) = ∏n Pρ (yi | f (xi )) factorising over cases. Finally, after speciﬁcation of the prior and i=1 ﬁtting of the hyperparameters θ = {φ, ψ, ρ}, we wish to compute predictive distributions for test cases. 1 2 3 4 5 6 7 % 1) SET UP THE GP : COVARIANCE ; MEAN , LIKELIHOOD , INFERENCE METHOD mf = { ’ meanSum ’ ,{ ’ meanLinear ’, @meanConst }}; a = 2; b = 1; % m(x) = a*x+b cf = { ’ covSEiso ’}; sf = 1; ell = 0.7; % squared exponential covariance funct lf = ’ likLaplace ’; sn = 0.2; % assume Laplace noise with variance sn ˆ2 hyp0 . mean = [a;b ]; hyp0 . cov = log([ ell ; sf ]); hyp0 . lik = log( sn ); % hypers inf = ’ infEP ’; % specify expectation propagation as inference method % 2) MINIMISE NEGATIVE LOG MARGINAL LIKELIHOOD nlZ wrt . hyp ; do 50 CG steps Ncg = 50; [hyp , nlZ ] = minimize ( hyp0 , ’gp ’, -Ncg , inf , mf , cf , lf , X , y ); % 3) PREDICT AT UNKNOWN TEST INPUTS [ymu , ys2 ] = gp (hyp , inf , mf , cf , lf , X , y , Xs ); % test input Xs In line 1, we specify the mean mφ (x) = a⊤ x + b of the GP with hyperparameters φ = {a, b}. First, the functional form of the mean function is given and its parameters are initialised. The desired mean function, happens not to exist in the library of mean functions; instead we have to make a composite mean function from simple constituents. This is done using a nested cell array containing the algebraic expression for m(x): As the sum of a linear (mean/meanLinear.m) and a constant mean function (mean/meanConst.m) it is an afﬁne function. In addition to linear and constant mean functions, the toolbox offers m(x) = 0 and m(x) = 1. These simple mean functions can be combined by composite mean functions to obtain sums (mean/meanSum.m) m(x) = ∑ j m j (x), products m(x) = ∏ j m j (x), scaled versions m(x) = αm0 (x) and powers m(x) = m0 (x)d . This ﬂexible mechanism is used for convenient speciﬁcation of an extensible algebra of mean functions. Note that functions are referred to either as name strings ’meanConst’ or alternatively function handles @meanConst. The order of components of the hyperparameters φ is the same as in the speciﬁcation of the cell array. Every mean function implements its evaluation m = mφ (X) and ﬁrst derivative ∂ computation mi = ∂φi mφ (X) on a data set X. In the same spirit, the squared exponential covariance kψ (x, x′ ) = σ f ² exp(− x − x′ 2 /2ℓ2 ) (cov/covSEiso.m) with hyperparameters ψ = {ln ℓ, ln σ f } is set up in line 2. Note, that the hyperparameters are represented by the logarithms, as these parameters are naturally positive. Many other simple covariance functions are contained in the toolbox. Among others, we offer linear, constant, Mat´ rn, rational quadratic, polynomial, periodic, neural network and ﬁnite support coe variance functions. Composite covariance functions allow for sums k(x, x′ ) = ∑ j k j (x, x′ ), products k(x, x′ ) = ∏ j k j (x, x′ ), positive scaling k(x, x′ ) = σ2 k0 (x, x′ ) and masking of components f k(x, x′ ) = k0 (xI , x′ ) with I ⊆ [1, 2, .., D], x ∈ RD . Again, the interface is simple since only the I ∂ evaluation of the covariance matrix K = kψ (X) and its derivatives ∂i K = ∂ψi kψ (X) on a data set X are required. Furthermore, we need cross terms k∗ = kψ (X, x∗ ) and k∗∗ = kψ (x∗ , x∗ ) for prediction. There are no restrictions on the composition of both mean and covariance functions—any combination is allowed including nested composition. 3013 R ASMUSSEN AND N ICKISCH √ √ The Laplace (lik/likLaplace.m) likelihood Pρ (y| f ) = exp(− 2/σn |y − f |)/ 2σn with hyperparameters ρ = {ln σn } is speciﬁed in line 3. There are only simple likelihood functions: Gaussian, Sech-squared, Laplacian and Student’s t for ordinary and sparse regression as well as the error and the logistic function for classiﬁcation. Again, the same inference code is used for any likelihood function. Although the speciﬁcation of likelihood functions is simple for the user, writing new likelihood functions is slightly more involved as different inference methods require access to different properties; for example, LA requires second derivatives and EP requires derivatives of moments. All hyperparameters θ = {φ, ψ, ρ} are stored in a struct hyp.{mean,cov,lik}, which is initialised in line 4; we select the approximate inference algorithm EP (inf/infEP.m) in line 5. We optimise the hyperparameters θ ≡ hyp by calling the CG optimiser (util/minimize.m) with initial value θ0 ≡ hyp0 in line 6 allowing at most N = 50 evaluations of the EP approximation to the marginal likelihood ZEP (θ) as done by gp.m. Here, D = (X, y) ≡ (X,y) is the training data where X = {x1 , .., xn } and y ∈ Rn . Under the hood, gp.m computes in every step a Gaussian ∂ posterior approximation and the derivatives ∂θ ln ZEP (θ) of the marginal likelihood by calling EP. Predictions with optimised hyperparameters are done in line 7, where we call gp.m with the unseen test inputs X∗ ≡ Xs as additional argument. As a result, we obtain the approximate marginal predictive mean E[P(y∗ |D , X∗ )] ≡ ymu and the predictive variance V[P(y∗ |D , X∗ )] ≡ ys2. Likelihood \ Inference Gaussian Sech-squared Laplacian Student’s t Error function Logistic function Exact FITC EP Laplace VB Type, Output Domain regression, R regression, R regression, R regression, R classiﬁcation, {±1} classiﬁcation, {±1} Alternate Name logistic distribution double exponential probit regression logit regression Table 1: Likelihood ↔ inference compatibility in the GPML toolbox Table 1 gives the legal likelihood/inference combinations. Exact inference and the FITC approximation support the Gaussian likelihood only. Variational Bayesian (VB) inference is applicable to all likelihoods. Expectation propagation (EP) for the Student’s t likelihood is inherently unstable due to its non-log-concavity. The Laplace approximation (LA) for Laplace likelihoods is not sensible due to the non-differentiable peak of the Laplace likelihood. Special care has been taken for the non-convex optimisation problem imposed by the combination Student’s t likelihood and LA. If the number of training examples is larger than a few thousand, dense matrix computations become too slow. We provide the FITC approximation for regression with Gaussian likelihood where ˜ instead of the exact covariance matrix K, a low-rank plus diagonal matrix K = Q + diag(K − Q) ⊤ K−1 K is used. The matrices K and K contain covariances and cross-covariances where Q = Ku uu u uu u of and between inducing inputs ui and data points x j . Using inf/infFITC.m together with any covariance function wrapped into cov/covFITC.m makes the computations feasible for large n. Acknowledgments Thanks to Ed Snelson for assisting with the FITC approximation. 3014 G AUSSIAN P ROCESSES FOR M ACHINE L EARNING T OOLBOX References Joaquin Qui˜ onero Candela and Carl E. Rasmussen. A unifying view of sparse approximate Gausn sian process regression. Journal of Machine Learning Research, 6(6):1935–1959, 2005. Mark N. Gibbs and David J. C. MacKay. Variational Gaussian process classiﬁers. IEEE Transactions on Neural Networks, 11(6):1458–1464, 2000. Thomas P. Minka. Expectation propagation for approximate Bayesian inference. In UAI, pages 362–369. Morgan Kaufmann, 2001. Hannes Nickisch and Carl E. Rasmussen. Approximations for binary Gaussian process classiﬁcation. Journal of Machine Learning Research, 9:2035–2078, 10 2008. Carl E. Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, MA, 2006. Ed Snelson and Zoubin Ghahramani. Sparse Gaussian processes using pseudo-inputs. In Advances in Neural Information Processing Systems 18, 2006. Christopher K. I. Williams and D. Barber. Bayesian classiﬁcation with Gaussian processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(20):1342–1351, 1998. 3015

6 0.062429901 29 jmlr-2010-Covariance in Unsupervised Learning of Probabilistic Grammars

7 0.061176576 62 jmlr-2010-Learning Gradients: Predictive Models that Infer Geometry and Statistical Dependence

8 0.053794324 91 jmlr-2010-Posterior Regularization for Structured Latent Variable Models

9 0.050472617 75 jmlr-2010-Mean Field Variational Approximation for Continuous-Time Bayesian Networks

10 0.048084714 20 jmlr-2010-Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes

11 0.043627556 38 jmlr-2010-Expectation Truncation and the Benefits of Preselection In Training Generative Models

12 0.043063551 6 jmlr-2010-A Rotation Test to Verify Latent Structure

13 0.04262574 17 jmlr-2010-Bayesian Learning in Sparse Graphical Factor Models via Variational Mean-Field Annealing

14 0.042179786 103 jmlr-2010-Sparse Semi-supervised Learning Using Conjugate Functions

15 0.037712418 79 jmlr-2010-Near-optimal Regret Bounds for Reinforcement Learning

16 0.035889611 1 jmlr-2010-A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification

17 0.035288807 83 jmlr-2010-On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation

18 0.034376539 78 jmlr-2010-Model Selection: Beyond the Bayesian Frequentist Divide

19 0.034238238 64 jmlr-2010-Learning Non-Stationary Dynamic Bayesian Networks

20 0.033963006 72 jmlr-2010-Matrix Completion from Noisy Entries

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.163), (1, -0.024), (2, -0.052), (3, -0.025), (4, -0.019), (5, -0.049), (6, 0.105), (7, 0.0), (8, -0.031), (9, -0.02), (10, -0.043), (11, 0.139), (12, -0.018), (13, -0.052), (14, 0.086), (15, 0.215), (16, -0.098), (17, -0.052), (18, 0.13), (19, -0.066), (20, 0.024), (21, -0.088), (22, -0.016), (23, 0.157), (24, -0.085), (25, -0.123), (26, -0.04), (27, 0.103), (28, -0.04), (29, -0.201), (30, 0.179), (31, 0.149), (32, 0.114), (33, 0.021), (34, 0.049), (35, -0.081), (36, 0.145), (37, -0.009), (38, -0.035), (39, -0.095), (40, 0.038), (41, -0.001), (42, -0.006), (43, 0.166), (44, 0.159), (45, -0.037), (46, 0.118), (47, 0.102), (48, 0.05), (49, -0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94115812 14 jmlr-2010-Approximate Riemannian Conjugate Gradient Learning for Fixed-Form Variational Bayes

Author: Antti Honkela, Tapani Raiko, Mikael Kuusela, Matti Tornio, Juha Karhunen

2 0.41640246 95 jmlr-2010-Rademacher Complexities and Bounding the Excess Risk in Active Learning

Author: Vladimir Koltchinskii

3 0.36775193 92 jmlr-2010-Practical Approaches to Principal Component Analysis in the Presence of Missing Values

Author: Alexander Ilin, Tapani Raiko

4 0.32946831 62 jmlr-2010-Learning Gradients: Predictive Models that Infer Geometry and Statistical Dependence

Author: Qiang Wu, Justin Guinney, Mauro Maggioni, Sayan Mukherjee

Abstract: The problems of dimension reduction and inference of statistical dependence are addressed by the modeling framework of learning gradients. The models we propose hold for Euclidean spaces as well as the manifold setting. The central quantity in this approach is an estimate of the gradient of the regression or classiﬁcation function. Two quadratic forms are constructed from gradient estimates: the gradient outer product and gradient based diffusion maps. The ﬁrst quantity can be used for supervised dimension reduction on manifolds as well as inference of a graphical model encoding dependencies that are predictive of a response variable. The second quantity can be used for nonlinear projections that incorporate both the geometric structure of the manifold as well as variation of the response variable on the manifold. We relate the gradient outer product to standard statistical quantities such as covariances and provide a simple and precise comparison of a variety of supervised dimensionality reduction methods. We provide rates of convergence for both inference of informative directions as well as inference of a graphical model of variable dependencies. Keywords: gradient estimates, manifold learning, graphical models, inverse regression, dimension reduction, gradient diffusion maps

5 0.32789248 23 jmlr-2010-Classification with Incomplete Data Using Dirichlet Process Priors

Author: Chunping Wang, Xuejun Liao, Lawrence Carin, David B. Dunson

6 0.31373584 29 jmlr-2010-Covariance in Unsupervised Learning of Probabilistic Grammars

7 0.28871197 64 jmlr-2010-Learning Non-Stationary Dynamic Bayesian Networks

8 0.28235504 20 jmlr-2010-Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary β-Mixing Processes

9 0.27830935 38 jmlr-2010-Expectation Truncation and the Benefits of Preselection In Training Generative Models

10 0.26266792 69 jmlr-2010-Lp-Nested Symmetric Distributions

11 0.25752887 17 jmlr-2010-Bayesian Learning in Sparse Graphical Factor Models via Variational Mean-Field Annealing

12 0.25430176 41 jmlr-2010-Gaussian Processes for Machine Learning (GPML) Toolbox

13 0.24100384 52 jmlr-2010-Incremental Sigmoid Belief Networks for Grammar Learning

14 0.23200428 91 jmlr-2010-Posterior Regularization for Structured Latent Variable Models

15 0.23182683 78 jmlr-2010-Model Selection: Beyond the Bayesian Frequentist Divide

16 0.22241677 1 jmlr-2010-A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification

17 0.21801813 49 jmlr-2010-Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data

18 0.21033131 6 jmlr-2010-A Rotation Test to Verify Latent Structure

19 0.20135796 75 jmlr-2010-Mean Field Variational Approximation for Continuous-Time Bayesian Networks

20 0.19482858 16 jmlr-2010-Asymptotic Equivalence of Bayes Cross Validation and Widely Applicable Information Criterion in Singular Learning Theory

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(4, 0.014), (8, 0.019), (21, 0.015), (32, 0.041), (33, 0.011), (36, 0.041), (37, 0.04), (75, 0.099), (81, 0.019), (85, 0.581), (96, 0.011)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.98577833 90 jmlr-2010-Permutation Tests for Studying Classifier Performance

Author: Markus Ojala, Gemma C. Garriga

Abstract: We explore the framework of permutation-based p-values for assessing the performance of classiﬁers. In this paper we study two simple permutation tests. The ﬁrst test assess whether the classiﬁer has found a real class structure in the data; the corresponding null distribution is estimated by permuting the labels in the data. This test has been used extensively in classiﬁcation problems in computational biology. The second test studies whether the classiﬁer is exploiting the dependency between the features in classiﬁcation; the corresponding null distribution is estimated by permuting the features within classes, inspired by restricted randomization techniques traditionally used in statistics. This new test can serve to identify descriptive features which can be valuable information in improving the classiﬁer performance. We study the properties of these tests and present an extensive empirical evaluation on real and synthetic data. Our analysis shows that studying the classiﬁer performance via permutation tests is effective. In particular, the restricted permutation test clearly reveals whether the classiﬁer exploits the interdependency between the features in the data. Keywords: classiﬁcation, labeled data, permutation tests, restricted randomization, signiﬁcance testing

same-paper 2 0.88695544 14 jmlr-2010-Approximate Riemannian Conjugate Gradient Learning for Fixed-Form Variational Bayes

Author: Antti Honkela, Tapani Raiko, Mikael Kuusela, Matti Tornio, Juha Karhunen

3 0.87227952 83 jmlr-2010-On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation

Author: Gavin C. Cawley, Nicola L. C. Talbot

Abstract: Model selection strategies for machine learning algorithms typically involve the numerical optimisation of an appropriate model selection criterion, often based on an estimator of generalisation performance, such as k-fold cross-validation. The error of such an estimator can be broken down into bias and variance components. While unbiasedness is often cited as a beneﬁcial quality of a model selection criterion, we demonstrate that a low variance is at least as important, as a nonnegligible variance introduces the potential for over-ﬁtting in model selection as well as in training the model. While this observation is in hindsight perhaps rather obvious, the degradation in performance due to over-ﬁtting the model selection criterion can be surprisingly large, an observation that appears to have received little attention in the machine learning literature to date. In this paper, we show that the effects of this form of over-ﬁtting are often of comparable magnitude to differences in performance between learning algorithms, and thus cannot be ignored in empirical evaluation. Furthermore, we show that some common performance evaluation practices are susceptible to a form of selection bias as a result of this form of over-ﬁtting and hence are unreliable. We discuss methods to avoid over-ﬁtting in model selection and subsequent selection bias in performance evaluation, which we hope will be incorporated into best practice. While this study concentrates on cross-validation based model selection, the ﬁndings are quite general and apply to any model selection practice involving the optimisation of a model selection criterion evaluated over a ﬁnite sample of data, including maximisation of the Bayesian evidence and optimisation of performance bounds. Keywords: model selection, performance evaluation, bias-variance trade-off, selection bias, overﬁtting

4 0.77096194 18 jmlr-2010-Bundle Methods for Regularized Risk Minimization

Author: Choon Hui Teo, S.V.N. Vishwanthan, Alex J. Smola, Quoc V. Le

Abstract: A wide variety of machine learning problems can be described as minimizing a regularized risk functional, with different algorithms using different notions of risk and different regularizers. Examples include linear Support Vector Machines (SVMs), Gaussian Processes, Logistic Regression, Conditional Random Fields (CRFs), and Lasso amongst others. This paper describes the theory and implementation of a scalable and modular convex solver which solves all these estimation problems. It can be parallelized on a cluster of workstations, allows for data-locality, and can deal with regularizers such as L1 and L2 penalties. In addition to the uniﬁed framework we present tight convergence bounds, which show that our algorithm converges in O(1/ε) steps to ε precision for general convex problems and in O(log(1/ε)) steps for continuously differentiable problems. We demonstrate the performance of our general purpose solver on a variety of publicly available data sets. Keywords: optimization, subgradient methods, cutting plane method, bundle methods, regularized risk minimization, parallel optimization ∗. Also at Canberra Research Laboratory, NICTA. c 2010 Choon Hui Teo, S.V. N. Vishwanthan, Alex J. Smola and Quoc V. Le. T EO , V ISHWANATHAN , S MOLA AND L E

5 0.65909559 71 jmlr-2010-Matched Gene Selection and Committee Classifier for Molecular Classification of Heterogeneous Diseases

Author: Guoqiang Yu, Yuanjian Feng, David J. Miller, Jianhua Xuan, Eric P. Hoffman, Robert Clarke, Ben Davidson, Ie-Ming Shih, Yue Wang

Abstract: Microarray gene expressions provide new opportunities for molecular classiﬁcation of heterogeneous diseases. Although various reported classiﬁcation schemes show impressive performance, most existing gene selection methods are suboptimal and are not well-matched to the unique characc 2010 Guoqiang Yu, Yuanjian Feng, David J. Miller, Jianhua Xuan, Eric P. Hoffman, Robert Clarke, Ben Davidson, Ie-Ming Shih and Yue Wang Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG teristics of the multicategory classiﬁcation problem. Matched design of the gene selection method and a committee classiﬁer is needed for identifying a small set of gene markers that achieve accurate multicategory classiﬁcation while being both statistically reproducible and biologically plausible. We report a simpler and yet more accurate strategy than previous works for multicategory classiﬁcation of heterogeneous diseases. Our method selects the union of one-versus-everyone (OVE) phenotypic up-regulated genes (PUGs) and matches this gene selection with a one-versus-rest support vector machine (OVRSVM). Our approach provides even-handed gene resources for discriminating both neighboring and well-separated classes. Consistent with the OVRSVM structure, we evaluated the fold changes of OVE gene expressions and found that only a small number of high-ranked genes were required to achieve superior accuracy for multicategory classiﬁcation. We tested the proposed PUG-OVRSVM method on six real microarray gene expression data sets (ﬁve public benchmarks and one in-house data set) and two simulation data sets, observing signiﬁcantly improved performance with lower error rates, fewer marker genes, and higher performance sustainability, as compared to several widely-adopted gene selection and classiﬁcation methods. The MATLAB toolbox, experiment data and supplement ﬁles are available at http://www.cbil.ece.vt.edu/software.htm. Keywords: microarray gene expression, multiclass gene selection, phenotypic up-regulated gene, multicategory classiﬁcation 1. Background The rapid development of gene expression microarrays provides an opportunity to take a genomewide approach for disease diagnosis, prognosis, and prediction of therapeutic responsiveness (Clarke et al., 2008; Wang et al., 2008). When the molecular signature is analyzed with pattern recognition algorithms, new classes of disease are identiﬁed and new insights into disease mechanisms and diagnostic or therapeutic targets emerge (Clarke et al., 2008). For example, many studies demonstrate that global gene expression proﬁling of human tumors can provide molecular classiﬁcations that reveal distinct tumor subtypes not evident by traditional histopathological methods (Golub et al., 1999; Ramaswamy et al., 2001; Shedden et al., 2003; Wang et al., 2006). While molecular classiﬁcation falls neatly within supervised pattern recognition, high gene dimensionality and paucity of microarray samples pose challenges for, and inspire novel developments in classiﬁer design and gene selection methodologies (Wang et al., 2008). For multicategory classiﬁcation using gene expression data, various classiﬁers have been proposed and have achieved promising performance, including k-Nearest Neighbor Rule (kNN) (Golub et al., 1999), artiﬁcial neural networks (Wang et al., 2006), Support Vector Machine (SVM) (Ramaswamy et al., 2001), Na¨ve Bayes Classiﬁer (NBC) (Liu et al., 2002), Weighted Votes (Tibshirani et al., 2002), and Linı ear Regression (Fort and Lambert-Lacroix, 2005). Many comparative studies show that SVM based classiﬁers outperform other methods on most bench-mark microarray data sets (Li et al., 2004; Statnikov et al., 2005). An integral part of classiﬁer design is gene selection, which can improve both classiﬁcation accuracy and diagnostic economy (Liu et al., 2002; Shi et al., 2008; Wang et al., 2008). Many microarray-based studies suggest that, irrespective of the classiﬁcation method, gene selection is vital for achieving good generalization performance (Statnikov et al., 2005). For multicategory classiﬁcation using gene expression data, the criterion function for gene selection should possess high sensitivity and speciﬁcity, well match the speciﬁc classiﬁers used, and identify gene markers that are both statistically reproducible and biologically plausible (Shi et al., 2008; Wang et al., 2008). There are limitations associated with existing gene selection methods (Li et al., 2004; Statnikov et al., 2005). While wrapper methods consider joint discrimination power of a gene subset, complex clas2142 PUG-OVRSVM siﬁers used in wrapper algorithms for small sample size may overﬁt, producing non-reproducible gene subsets (Li et al., 2004; Shi et al., 2008). Moreover, discernment of the (biologically plausible) gene interactions retained by wrapper methods is often difﬁcult due to the black-box nature of most classiﬁers (Shedden et al., 2003). Conversely, most ﬁltering methods for multicategory classiﬁcation are straightforward extensions of binary discriminant analysis. These methods are devised without well matching to the classiﬁer that is used, which typically leads to suboptimal classiﬁcation performance (Statnikov et al., 2005). Popular multicategory ﬁltering methods (which are extensions of two-class methods) include Signal-to-Noise Ratio (SNR) (Dudoit et al., 2002; Golub et al., 1999), Student’s t-statistics (Dudoit et al., 2002; Liu et al., 2002), the ratio of Between-groups to Within-groups sum of squares (BW) (Dudoit et al., 2002), and SVM based Recursive Feature Elimination (RFE) (Li and Yang, 2005; Ramaswamy et al., 2001; Zhou and Tuck, 2007). However, as pointed out by Loog et al. (2001) in proposing their weighted Fisher criterion (wFC), simple extensions of binary discriminant analysis to multicategory gene selection are suboptimal because they overemphasize large betweenclass distances, that is, these methods choose gene subsets that preserve the distances of (already) well-separated classes, without reducing (and possibly with increase in) the large overlap between neighboring classes. This observation and the application of wFC to multicategory classiﬁcation are further evaluated experimentally by Wang et al. (2006) and Xuan et al. (2007). The work most closely related to our gene selection scheme is that of Shedden et al. (2003). These investigators focused on marker genes that are highly expressed in one phenotype relative to one or more different phenotypes and proposed a tree-based one-versus-rest (OVR) fold change evaluation between mean expression levels. The potential limitation here is that the criterion function considers the “rest of the classes” as a “super class”, and thus may select genes that can distinguish a single class from the remaining super class, yet without giving any beneﬁt in discriminating between classes within the super class. Such genes may compromise multicategory classiﬁcation accuracy, especially when a small gene subset is chosen. It is also important to note that, while univariate or multivariate analysis methods using complex criterion functions may reveal subtle marker effects (Cai et al., 2007; Liu et al., 2005; Xuan et al., 2007; Zhou and Tuck, 2007), they are also prone to overﬁtting. Recent studies have found that for small sample sizes, univariate methods fared comparably to multivariate methods (Lai et al., 2006; Shedden et al., 2003) and simple fold change analysis produced more reproducible marker genes than signiﬁcance analysis of variance-incorporated t-tests (Shi et al., 2008). In this paper, we propose matched design of the gene selection mechanism and a committee classiﬁer for multicategory molecular classiﬁcation using microarray gene expression data. A key feature of our approach is to match a simple one-versus-everyone (OVE) gene selection scheme to the OVRSVM committee classiﬁer (Ramaswamy et al., 2001). We focus on marker genes that are highly expressed in one phenotype relative to each of the remaining phenotypes, namely Phenotypic Up-regulated Genes (PUGs). PUGs are identiﬁed using the fold change ratio computed between the speciﬁed phenotype mean and each of the remaining phenotype means. Thus, we consider a gene to be a marker for the speciﬁed phenotype if the average expression associated with this phenotype is high relative to the average expressions in each of the other phenotypes. To assure evenhanded resources for discriminating both neighboring and well-separated classes, we use a ﬁxed number of PUGs for each phenotypic class and pool all phenotype-speciﬁc PUGs together to form a gene marker subset used by the OVRSVM committee classiﬁer. All PUGs referenced by the committee classiﬁer are individually interpretable as potential markers for phenotypic classes, allowing each 2143 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG gene to inform the classiﬁer in a way that is consistent with its mechanistic role (Shedden, et al., 2003). Since PUGs are the union of subPUGs selected by simple univariate OVE fold change analysis, they are expected to be statistically reproducible (Lai et al., 2006; Shedden et al., 2003; Shi et al., 2008). We tested PUG-OVRSVM on ﬁve publicly available benchmarks and one in-house microarray gene expression data set and on two simulation data sets, observing signiﬁcantly improved performance with lower error rates, fewer marker genes, and higher performance stability, as compared to several widely-adopted gene selection and classiﬁcation methods. The reference gene selection methods are OVRSNR (Golub et al., 1999), OVRt-stat (Liu et al., 2002), pooled BW (Dudoit et al., 2002), and OVRSVM-RFE (Guyon et al., 2002), and the reference classiﬁers are kNN, NBC, and one-versus-one (OVO) SVM. With accuracy estimated by leave-one-out cross-validation (LOOCV) (Hastie et al., 2001), our experimental results show that PUG-OVRSVM outperforms all combinations of the above referenced gene selection and classiﬁcation methods in the two simulation data sets and 5 out of the 6 real microarray gene expression data sets, and produces comparable performance on the one remaining data set. Speciﬁcally, tested on the widely-used benchmark microarray gene expression data set “multicategory human cancers data” (GCM) (Ramaswamy et al., 2001; Statnikov et al., 2005), PUG-OVRSVM produces a lower error rate of 11.05% (88.95% correct classiﬁcation rate) than the best known benchmark error rate of 16.72% (83.28% correct classiﬁcation rate) (Cai et al., 2007; Zhou and Tuck, 2007). 2. Methods In this section, we ﬁrst discuss multicategory classiﬁcation and associated feature selection, with an emphasis on OVRSVM and application to gene selection for the microarray domain. This discussion then naturally leads to our proposed PUG-OVRSVM scheme. 2.1 Maximum a Posteriori Decision Rule Classiﬁcation of heterogeneous diseases using gene expression data can be considered a Bayesian hypothesis testing problem (Hastie et al., 2001). Let xi = [xi1 , ..., xi j , ..., xid ] be the real-valued gene expression proﬁle associated with sample i across d genes for i = 1, . . . , N and j = 1, . . . , d. Assume that the sample points xi come from M classes, and denote the class conditional probability density function and class prior probability by p (xi | ωk ) and P (ωk ), respectively, for k = 1, . . . , M. To minimize the Bayes risk averaged over all classes, the optimum classiﬁer uses the well-known maximum a posteriori (MAP) decision rule (Hastie et al., 2001). Based on Bayes’ rule, the class posterior probability for a given sample xi is P (ωk | xi ) = P (ωk ) p (xi | ωk ) M ∑k′ =1 P (ωk′ ) p (xi | ωk′ ) and is used to (MAP) classify xi to ωk when P (ωk | xi ) > P (ωl | xi ) for all l = k. 2144 (1) PUG-OVRSVM 2.2 Supervised Learning and Committee Classiﬁers Practically, multicategory classiﬁcation using the MAP decision rule can be approximated using parameterized discriminant functions that are trained by supervised learning. Let fk (xi , θ), k = 1, 2, . . . , M, be the M outputs of a machine classiﬁer designed to discriminate between M classes (>2), where θ represents the set of parameters that fully specify the classiﬁer, and with the output values assumed to be in the range [0, 1]. The desired output of the classiﬁer will be “1” for the class to which the sample belongs and “0” for all other classes. Suppose that the classiﬁer parameters are selected based on a training set so as to minimize the mean squared error (MSE) between the outputs of the classiﬁer and the desired (class target) outputs, MSE = 1 M [ fk (xi , θ) − 1]2 + ∑l=k fl2 (xi , θ) . ∑ N k=1 xi∑ k ∈ω (2) Then, it can be shown that the classiﬁer is being trained to approximate the posterior probability for class ωk given the observed xi , that is, the classiﬁer outputs will converge to the true posterior class probabilities fk (xi , θ) → P (ωk | xi ) if we allow the classiﬁer to be arbitrarily complex and if N is made sufﬁciently large. This result is valid for any classiﬁer trained with the MSE criterion, where the parameters of the classiﬁer are adjusted to simultaneously approximate M discriminant functions fk (xi , θ) (Gish, 1990). While there are numerous machine classiﬁers that can be used to implement the MAP decision rule (1) (Hastie et al., 2001), a simple yet elegant way of discriminating between M classes, and which we adopt here, is based on an OVRSVM committee classiﬁer (Ramaswamy et al., 2001; Rifkin and Klautau, 2002; Statnikov et al., 2005). Intuitively, each term within the sum over k in (2) corresponds to an OVR binary classiﬁcation problem and can be effectively minimized by suitable training of a binary classiﬁer (discriminating class k from all other classes). By separately minimizing the MSE associated with each term in (2) via binary classiﬁer training and, thus, effectively minimizing the total MSE, a set of discriminant functions { fk (xi , θk ⊆ θ)} can be constructed which, given a new sample point, apply the decision rule (1), but with fk (xi , θ) playing the role of the posterior probability. Among the great variety of binary classiﬁers that use regularization to control the capacity of the function spaces they operate in, the best known example is the SVM (Hastie et al., 2001; Vapnik, 1998). To carry over the advantages of regularization approaches for binary classiﬁcation tasks to multicategory classiﬁcation, the OVRSVM committee classiﬁer uses M different SVM binary classiﬁers, each one separately trained to distinguish the samples in a single class from the samples in all remaining classes. For classifying a new sample point, the M SVMs are run, and the SVM that produces the largest (most positive) output value is chosen as the “winner” (Ramaswamy et al., 2001). For more detailed discussion, see the critical review and experimental comparison by Rifkin and Klautau (2002). Figure 1 shows an illustrative OVRSVM committee classiﬁer for three classes. The OVRSVM committee classiﬁer has proved highly successful at multicategory classiﬁcation tasks involving ﬁnite or limited amounts of high dimensional data in real-world applications. OVRSVM produces results that are often at least as accurate as other more complicated methods including single machine multicategory schemes (Statnikov et al., 2005). Perhaps more importantly for our purposes, the OVR scheme can be matched with an OVE gene selection method, as we elaborate next. 2145 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG Figure 1: Conceptual illustration of OVR committee classiﬁer for multicategory classiﬁcation (three classes, in this case). The dotted lines are the decision hyperplanes associated with each of the component binary SVMs and the bold line-set represents the ﬁnal decision boundary after the winner-take-all classiﬁcation rule is applied. 2.3 One-Versus-Everyone Fold-change Gene Selection While gene selection is vital for achieving good generalization performance (Guyon et al., 2002; Statnikov et al., 2005), perhaps even more importantly, the identiﬁed genes, if statistically reproducible and biologically plausible, are “markers”, carrying information about the disease phenotype (Wang et al., 2008). We will propose two novel, effective gene selection methods for multicategory classiﬁcation that are well-matched to OVRSVM committee classiﬁers, namely, OVR and OVE fold-change analyses. OVR fold-change based PUG selection follows directly from the OVRSVM scheme. Let Nk be the number of sample points belonging to phenotype k; the geometric mean of the expression levels (on the untransformed scale) for gene j under phenotype k is Nk µ j (k) = ∏i∈ω k xi j j = 1, . . . , d; k = 1, . . . , M. Then, we deﬁne the OVRPUGs as: M M JPUG (k) = JPUG = j µ j (k) ∏l=k µ j (l) M−1 k=1 k=1 τk (3) where {τk } are pre-deﬁned thresholds chosen so as to select a ﬁxed (equal) number of PUGs for each phenotype k. This PUG selection scheme (3) is similar to what has been previously proposed by Shedden et al. (2003): M M JPUG (k) = JPUG = k=1 j k=1 µ j (k) N−Nk ∏i∈ωk xi j / τk . (4) The critical difference between (3) and (4) is that the denominator term in (3) is the overall geometric center of the “geometric centers” associated with each of the remaining phenotypes while 2146 PUG-OVRSVM the denominator term in (4) is the geometric center of all sample points belonging to the remaining phenotypes. When {Nk } are signiﬁcantly imbalanced for different k, the denominator term in (4) will be biased toward the dominant phenotype(s). However, a problem associated with both PUG selection schemes speciﬁed by (3) and (4) (and with the OVRSNR criterion Golub et al., 1999) is that the criterion function considers the remaining classes as a single super class, which is suboptimal because it ignores a gene’s ability to discriminate between classes within the super class. We therefore propose OVE fold-change based PUG selection to fully support the objective of multicategory classiﬁcation. Speciﬁcally, the OVEPUGs are deﬁned as: M M JPUG (k) = JPUG = k=1 j k=1 µ j (k) maxl=k µ j (l) τk (5) where the denominator term is the maximum phenotypic mean expression level over the remaining phenotype classes. This seemingly technical modiﬁcation turns out to have important consequences since it assures that the selected PUGs are highly expressed in one phenotype relative to each of the remaining phenotypes, that is, “high” (up-regulated) in phenotype k and “low” (down-regulated) in all phenotypes l = k. In our experimental results, we will demonstrate that (5) leads to better classiﬁcation accuracy than (4) on a well-known multi-class cancer domain. Adopting the same strategy as in Shedden et al. (2003), to assure even-handed gene resources for discriminating both neighboring and well-separated classes, we select a ﬁxed (common) number of top-ranked phenotype-speciﬁc subPUGs for each phenotype, that is, JPUG (k) = NsubPUG for all k, and pool all these subPUGs together to form the ﬁnal gene marker subset JPUG for the OVRSVM committee classiﬁer. In our experiments, the optimum number of PUGs per phenotype, NsubPUG , is determined by surveying the curve of classiﬁcation accuracy versus NsubPUG and selecting the number that achieves the best classiﬁcation performance. More generally, in practice, NsubPUG can be chosen via a cross validation procedure. Figure 2 shows the geometric distribution of the selected PUGs speciﬁed by (5), where the PUGs (highlighted data points) constitute the lateral-edge points of the convex pyramid deﬁned by the scatter plot of the phenotypic mean expressions (Zhang et al., 2008). Different from the PUG selection schemes given by (3) and (4), the PUGs selected based on (5) are most compact yet informative, since the down-regulated genes that are not differentially expressed between the remaining phenotypes (the genes on the lateral faces of the scatter plot convex pyramid) are excluded. From a statistical point of view, extensive studies on the normalized scatter plot of microarray gene expression data by many groups including our own indicate that the PUGs selected by (5) approximately follow an independent multivariate super-Gaussian distribution (Zhao et al., 2005) where subPUGs are mutually exclusive and phenotypic gene expression patterns deﬁned over the PUGs are statistically independent (Wang et al., 2003). It is worth noting that the PUG selection by (5) also adopts a univariate fold-change evaluation that does not require calculation of either expression variance or of correlation between genes (Shi et al., 2008). For the small sample size case typical of microarray data, multivariate gene selection schemes may introduce additional uncertainty in estimating the correlation structure (Lai et al., 2006; Shedden et al., 2003) and thus may fail to identify true gene markers (Wang et al., 2008). The exclusion of the variance in our criterion is also supported by the variance stabilization theory (Durbin et al., 2002; Huber et al., 2002), because the geometric mean in (5) is equivalent to the arithmetic mean after logarithmic transformation and the gene expression after logarithmic transfor2147 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG Figure 2: Geometric illustration of the selected one-versus-everyone phenotypic upregulated genes (OVEPUGs) associated with three phenotypic classes. Three-dimensional geometric distribution (on the untransformed scale) of the selected OVEPUGs, which reside around the lateral-edges of the phenotypic gene expression scatter plot convex pyramid, is shown in the left subﬁgure. A projected distribution of the selected OVEPUGs together with OVEPDGs is shown in the right cross-sectional plot, where OVEPDGs reside along the face-edges of the cross-sectional triangle. mation approximately has the equal variance across different genes, especially for the up-regulated genes. Corresponding to the deﬁnition of OVEPUGs, the OVEPDGs (which are down-regulated in one class while being up-regulated in all other classes) can be deﬁned by the following criterion: M M JPDG (k) = JPDG = j k=1 k=1 minl=k µ j (l) µ j (k) τk . (6) Furthermore, the combination of PUGs and PDGs can be deﬁned as: M M JPUG+PDG (k) = JPUG+PDG = k=1 j max k=1 minl=k µ j (l) µ j (k) , µ j (k) maxl=k µ j (l) τk . (7) Purely from the machine learning view, PDGs have the theoretical capability of being as discriminating as PUGs. Thus, PDGs merit consideration as candidate genes. However, there are several critical differences, with consequential implications, between lowly-expressed genes and highly-expressed genes, such as the extraordinarily large proportion and relatively large noise of the lowly-expressed genes. We have evaluated the classiﬁcation performance of PUGs, PDGs, and 2148 PUG-OVRSVM PUGs+PDGs, respectively. Experimental results show that PDGs have less discriminatory power than PUGs and the inclusion of PDGs actually worsens classiﬁcation accuracy, compared to just using PUGs. Experiments and further discussion will be given in the results section. 2.4 Review of Relevant Gene Selection Methods Here we brieﬂy review four benchmark gene selection methods that have been previously proposed for multicategory classiﬁcation, namely, OVRSNR (Golub et al., 1999), OVR t-statistic (OVRt-stat) (Liu et al., 2002), BW (Dudoit et al., 2002), and SVMRFE (Guyon et al., 2002). Let µ j,k and µ j,-k be the arithmetic means of the expression levels of gene j associated with phenotype k and associated with the super class of remaining phenotypes, respectively, on the log-transformed scale, with σ j,k and σ j,-k the corresponding standard deviations. OVRSNR gene selection for multicategory classiﬁcation is given by: M M JOVRSNR (k) = JOVRSNR = k=1 j k=1 µ j,k − µ j,-k σ j,k + σ j,-k τk , (8) where τk is a pre-deﬁned threshold (Golub et al., 1999). To assess the statistical signiﬁcance of the difference between µ j,k and µ j,-k , OVRt-stat applies a test of the null hypothesis that the means of two assumed normally distributed measurements are equal. Accordingly, OVRt-stat gene selection is given by Liu et al. (2002):       M  M  µ j,k − µ j,-k τk , (9) j JOVRt-stat (k) = JOVRt-stat =    2 2 k=1  k=1   σ j,k Nk + σ j,-k (N − Nk ) where the p-values associated with each gene may be estimated. As aforementioned, one limitation of the gene selection schemes (8) and (9) is that the criterion function considers the remaining classes as a single group. Another is that they both require variance estimation. Dudoit et al. (2002) proposed a pooled OVO gene selection method based on the BW sum of squares across all paired classes. Speciﬁcally, BW gene selection is speciﬁed by JBW = j ∑N ∑M 1ωk (i) µ j,k − µ j i=1 k=1 2 ∑N ∑M 1ωk (i) xi j − µ j,k i=1 k=1 2 τ , (10) where µ j is the global arithmetic center of gene j over all sample points and 1ωk (i) is the indicator function reﬂecting membership of sample i in class k. As pointed out by Loog et al. (2001), BW gene selection may only preserve the distances of already well-separated classes rather than neighboring classes. From a dimensionality reduction point of view, Guyon et al. (2002) proposed a feature subset ranking criterion for linear SVMs, dubbed the SVMRFE. Here, one ﬁrst trains a linear SVM classiﬁer on the full feature space. Features are then ranked based on the magnitude of their weights and are eliminated in the order of increasing weight magnitude. A widely adopted reduction strategy is to eliminate a ﬁxed or decreasing percentage of features corresponding to the bottom portion of the ranked weights and then to retrain the SVM on the reduced feature space. Application to microarray gene expression data shows that the genes selected matter more than the classiﬁers with which they are paired (Guyon et al., 2002). 2149 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG 3. Results We tested PUG-OVRSVM on ﬁve benchmarks and one in-house real microarray data set, and compared the performance to several widely-adopted gene selection and classiﬁcation methods. 3.1 Description of the Real Data Sets The numbers of samples, phenotypes, and genes, as well as the microarray platforms used to generate these gene expression data sets, are brieﬂy summarized in Supplementary Tables 1∼7. The six data sets are the MIT 14 Global Cancer Map data set (GCM) (Ramaswamy et al., 2001), the NCI 60 cancer cell lines data set (NCI60) (Staunton et al., 2001), the University of Michigan cancer data set (UMich) (Shedden et al., 2003), the Central Nervous System tumors data set (CNS) (Pomeroy et al., 2002), the Muscular Dystrophy data set (MD) (Bakay et al., 2006), and the Norway Ascites data set (NAS). To assure a meaningful and well-grounded comparison, we emphasized data quality and suitability in choosing these test data sets. For example, the data sets cannot be too “simple” (if the classes are well-separated, all methods perform equally well) or too “complex” (no method will then perform reasonably well), and each class should contain sufﬁcient samples to support some form of cross-validation assessment. We also performed several important pre-processing steps widely adopted by other researchers (Guyon et al., 2002; Ramaswamy et al., 2001; Shedden et al., 2003; Statnikov et al., 2005). When the expression levels in the raw data take negative values, probably due to global probe-set calls and/or data normalization procedures, these negative values are replaced by a ﬁxed small quantity (Shedden et al., 2003). On the log-transformed scale, we further conducted a variance-based unsupervised gene ﬁltering operation to remove the genes whose expression standard deviations (across all samples) were less than a pre-determined small threshold; this effectively reduces the number of genes by half (Guyon et al., 2002; Shedden et al., 2003). 3.2 Experiment Design We decoupled the two key steps of multicategory classiﬁcation: 1) selecting an informative subset of marker genes and then 2) ﬁnding an accurate decision function. For the crucial ﬁrst step we implemented ﬁve gene selection methods, including OVEPUG speciﬁed by (5), OVRSNR speciﬁed by (8), OVRt-stat speciﬁed by (9), pooled BW speciﬁed by (10), and SVMRFE described in Ramaswamy et al. (2001). We applied these methods to the six data sets, and for each data set, we selected a sequence of gene subsets with varying sizes, indexed by NsubPUG , the number of genes per class. In our experiments, this number was increased from 2 up to 100. There are several reasons why we do not go beyond 100 subPUGs per class. First, classiﬁcation accuracy may be either ﬂat or monotonically decreasing as the number of features increases beyond a certain point, due to the theoretical bias-variance dilemma. Second, even in some cases where best performance is achieved using all the gene features, the idea of feature selection is to ﬁnd the minimum number of features needed to achieve good (near-optimal) classiﬁcation accuracy. Third, when NsubPUG = 100, the total number of genes used for classiﬁcation is already quite large (this number is maximized if the sets JPUG (k) are mutually exclusive, in which case it is NsubPUG times the number of classes). Fourth, but not least important, a large feature reduction may be necessary not only complexity-wise, but also for interpreting the biological functions and pathway involvement when the selected PUGs are most relevant and statistically reproducible. 2150 PUG-OVRSVM The quality of the marker gene subsets was then assessed by prediction performance on four subsequently trained classiﬁers, including OVRSVM, kNN, NBC, and OVOSVM. In relation to the proposed PUG-OVRSVM approach, we evaluated all combinations of these four different gene selection methods and three different classiﬁers on all six benchmark microarray gene expression data sets. To properly estimate the accuracy of predictive classiﬁcation, a validation procedure must be carefully designed, recognizing limits on the accuracy of estimated performance, in particular for small sample size. Clearly, classiﬁcation accuracy must be assessed on labelled samples ‘unseen’ during training. However, for multicategory classiﬁcation based on small, class-imbalanced data sets, single batch held-out test data may be precluded, as there will be insufﬁcient samples for both accurate classiﬁer training and accurate validation (Hastie et al., 2001). A practical alternative is a sound cross-validation procedure, wherein all the data are used for both training and testing, but with held-out samples in a testing fold not used for any phase of classiﬁer training, including gene selection and classiﬁer design (Wang et al., 2008). In our experiments, we chose LOOCV, wherein a test fold consists of a single sample; the rest of the samples are placed in the training set. Using only the training set, the informative genes are selected and the weights of the linear OVRSVM are ﬁt to the data (Liu et al., 2005; Shedden et al., 2003; Yeang et al., 2001). It is worth noting that LOOCV is approximately unbiased, lessening the likelihood of misestimating the prediction error due to small sample size; however, LOOCV estimates do have considerable variance (Braga-Neto and Dougherty, 2004; Hastie et al., 2001). We evaluated both the lowest “sustainable” prediction error rate and the lowest prediction error rate, where the sequence of sustainable prediction error rates were determined based on a moving-average of error rates along the survey axis of the number of genes used for each class, NsubPUG , with a moving window of width 5. We also report the number of genes per class at which the best sustainable performance was obtained. While the error rate is estimated through LOOCV and the optimum number of PUGs used per class is obtained by the aforementioned surveying strategy, we should point out that a two-level LOOCV could be applied to jointly determine the optimum NsubPUG and estimate the associated error rate; however, such an approach is computationally expensive (Statnikov et al., 2005). For the settings of structural parameters in the classiﬁers, we used C = 1.0 in the SVMs for all experiments (Vapnik, 1998), and chose k = 1, 2, 3 in kNNs under different training sample sizes per class, as recommended by Duda et al. (2001). 3.3 Experimental Results Our ﬁrst comparative study focused on the GCM data widely used for evaluating multicategory classiﬁcation algorithms (Cai et al., 2007; Ramaswamy et al., 2001; Shedden et al., 2003; Zhou and Tuck, 2007). The performance curves of OVRSVM committee classiﬁers trained on the commonly pre-processed GCM data using the ﬁve different gene selection methods (OVEPUG, OVRSNR, OVRt-stat, BW, and SVMRFE) are detailed in Figure 3. It can be seen that our proposed OVEPUG selection signiﬁcantly improved the overall multicategory classiﬁcation when using different numbers of marker genes, as compared to the results produced by the four competing gene selection methods. For example, using as few as 9 genes per phenotypic class (with 126 distinct genes in total, that is, mutually exclusive PUGs for each class), we classiﬁed 164 of 190 (86.32%) of the tumors correctly. Furthermore, using LOOCV on the GCM data set of 190 primary malignant tumors, and using the optimal number of genes (61 genes per phenotypic class or 769 unique genes 2151 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG in total), we achieved the best (88.95% or 169 of 190 tumors) sustainable correct predictions. In contrast, at its optimum performance, OVRSNR gene selection achieved 85.37% sustainable correct predictions using 25 genes per phenotypic class, OVRt-stat gene selection achieved 84.53% sustainable correct predictions using 71 genes per phenotypic class, BW gene selection achieved 80.53% sustainable correct predictions using 94 genes per phenotypic class, and SVMRFE gene selection achieved 84.74% sustainable correct predictions using 96 genes per phenotypic class. In our comparative study, instead of solely comparing the lowest error rates achieved by different gene selection methods, we also emphasized the sustainable correct prediction rates, as potential overﬁtting to the data may produce an (unsustainably) good prediction performance. For our experiments in Figure 3, based on the realistic assumption that the probability of good predictions purely “by chance” over a sequence of consecutive gene numbers is low, we deﬁned the sustainable prediction/error rates based on the moving-averaged prediction/error rates over δ = 5 consecutive gene numbers. Here, δ gives the sustainability requirement. Figure 3: Comparative study on ﬁve gene selection methods (OVEPUG, OVRSNR, OVRt-stat, BW, and SVMRFE) using the GCM benchmark data set. The curves of classiﬁcation error rates were generated by using OVRSVM committee classiﬁers with varying size of the input gene subset. For the purpose of information sharing with readers, based on publicly reported optimal results for different methods, we have summarized in Table 1 the comparative performance achieved by PUG-OVRSVM and eight existing/competing methods on the benchmark GCM data set, along with the gene selection methods used, the chosen classiﬁers, sample sizes, and the chosen crossvalidation schemes. Obviously, since the reported prediction error rates were generated by different algorithms and under different conditions, any conclusions based on simple/direct comparisons of the reported results must be carefully drawn. We have chosen not to independently reproduce results 2152 PUG-OVRSVM by re-implementing the methods listed in Table 1, ﬁrstly because we typically do not have access to public domain code implementing other authors’ methods and secondly because we feel that high reproducibility of previously published results may not be expected without knowing some likely undeclared optimization steps and/or additional control parameters used in the actual computer codes. Nevertheless, many reported prediction error rates on the GCM data set were actually based on the same/similar training sample set (144 ∼ 190 primary tumors) and the LOOCV scheme used in our PUG-OVRSVM experiments; furthermore, it was reported that the prediction error rates estimated by LOOCV and 144/54 split/held-out test were very similar (Ramaswamy et al., 2001). Speciﬁcally, the initial work on GCM by Ramaswamy et al. (2001) reported an achieved 77.78% prediction rate, and some improved performance was later reported by Yeang et al. (2001) and Liu et al. (2002), achieving 81.75% and 79.99% prediction rates, respectively. In the work most closely related to our gene selection scheme by Shedden et al. (2003), using a kNN tree classiﬁer and using OVR fold-change based gene selection speciﬁed by (4), a prediction rate of 82.63% was achieved. In relation to these reported results on GCM, as indicated in Table 1, our proposed PUG-OVRSVM method produced the best sustainable prediction rate of 88.95%. References Gene-select Classiﬁer Sample CV scheme Error rate Ramaswamy et al. (2001) OVRSVM RFE OVRSVM 144&198 LOOCV 144/54 22.22% Yeang et al. (2001) N/A OVRSVM 144 LOOCV 18.75% Ooi and Tan (2003) Genetic algorithm MLHD 198 144/54 18.00% Shedden et al. (2003) OVR fold-change kNN Tree 190 LOOCV 17.37% Liu et al. (2005) Genetic algorithm OVOSVM N/A LOOCV 20.01% Statnikov et al. (2005) No gene selection CS-SVM 308 10-fold 23.40% Zhou and Tuck (2007) CS-SVM RFE OVRSVM 198 4-fold 16.72% Cai et al. (2007) DISC-GS kNN 190 144/46 21.74% PUG-OVRSVM PUG OVRSVM 190 LOOCV 11.05% Table 1: Summary of comparative performances by OVEPUG-OVRSVM and eight competing methods (based on publicly reported optimum results) on the GCM benchmark data set. A more stringent evaluation of the robustness of a classiﬁcation method is to carry out the predictions on multiple data sets and then assess the overall performance (Statnikov et al., 2005). Our second comparative study evaluated the aforementioned ﬁve gene selection methods using the six benchmark microarray gene expression data sets. To determine whether the genes selected matter more than the classiﬁers used (Guyon et al., 2002), we used a common OVRSVM committee classiﬁer and LOOCV scheme in all the experiments, and summarized the corresponding results in Table 2. For each experiment that used a distinct gene selection scheme applied to a distinct data set, we reported both sustainable (with sustainability requirement δ = 5) and lowest (within parentheses) prediction error rates, as well as the number of genes per class that were used to produce these results. Clearly, the selected PUGs based on (5) produced the highest overall sustainable prediction rates as compared to the other four competing gene selection methods. Speciﬁcally, PUG is the consistent winner in 22 of 24 competing experiments (combinations of four gene selection schemes and six testing data sets). It should be noted that although BW and OVRSNR achieved comparably low prediction error rates on the CNS data set (with relatively balanced mixture distributions), they 2153 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG also produced high prediction error rates on the other testing data sets; the other competing gene selection methods also show some level of performance instability across data sets. Gene-select GCM NCI60 UMich CNS MD NAS OVE PUG 11.05% (11.05%) [61 g/class] 27.33% (26.67%) [52 g/class] 1.08% (0.85%) [26 g/class] 7.14% (7.14%) [71 g/class] 19.67% (19.01%) [46 g/class] 13.16% (13.16%) [42 g/class] OVR SNR 14.63% (13.68%) [25 g/class] 31.67% (31.67%) [58 g/class] 1.42% (1.42%) [62 g/class] 7.14% (7.14%) [57 g/class] 23.97% (23.97%) [85 g/class] 16.32% (15.79%) [54 g/class] OVR t-stat 15.47% (15.26%) [71 g/class] 31.67% (31.67%) [56 g/class] 1.70% (1.70%) [45 g/class] 7.62% (7.14%) [92 g/class] 23.47% (22.31%) [56 g/class] 15.79% (15.79%) [74 g/class] BW 19.47% (18.95%) [94 g/class] 31.67% (31.67%) [55 g/class] 1.30% (1.13%) [92 g/class] 7.14% (7.14%) [56 g/class] 19.83% (19.01%) [71 g/class] 21.05% (21.05%) [65 g/class] SVM RFE 15.26% (14.21%) [96 g/class] 29.00% (28.33%) [81 g/class] 1.13% (1.13%) [58 g/class] 14.29% (14.29%) [53 g/class] 29.09% (28.10%) [73 g/class] 32.11% (31.58%) [94 g/class] Table 2: Performance comparison between ﬁve different gene selection methods tested on six benchmark microarray gene expression data sets, where the predictive classiﬁcation error rates for all methods were generated based on OVRSVM committee classiﬁcation and an LOOCV scheme. Both sustainable and lowest (within parentheses) error rates are reported together with number of genes used per class. To give more complete comparisons that also involved different classiﬁers (Statnikov et al., 2005), we further illustrate the superior prediction performance of the matched OVEPUG selection and OVRSVM classiﬁer as compared to the best results produced by combinations of three different classiﬁers (OVOSVM, kNN, NBC) and four gene selection methods (PUG, OVRSNR, OVRt-stat, pooled BW). The optimum experimental results achieved over all combinations of these methods on the six data sets are summarized in Table 3, where we report both sustainable prediction error rates and the corresponding gene selection methods. Again, PUG-OVRSVM outperformed all other methods on all six data sets and was a clear winner in all 15 competing experiments. Our comparative studies also reveal that although gene selection is a critical step of multi-category classiﬁcation, the classiﬁers used do indeed play an important role in achieving good prediction performance. 3.4 Comparison Results on the Realistic Simulation Data Sets To more reliably validate and compare the performance of the different gene selection methods, we have conducted additional experiments involving realistic simulations. The advantage of using synthetic data is that, unlike the real data sets often with small sample size and with LOOCV as the only applicable validation method, large testing samples can be generated to allow an accurate and reliable assessment of a classiﬁer’s generalization performance. Two different simulation approaches were implemented. In both, we modeled the joint distribution for microarray data under each class and generated i.i.d. synthetic data sets consistent both with these distributions and with assumed class priors. In the ﬁrst approach, we chose the class-conditional models consistent with commonly 2154 PUG-OVRSVM GCM NCI60 UMich CNS MD NAS OVR SVM 11.05% (OVEPUG) 27.33% (OVEPUG) 1.08% (OVEPUG) 7.14% (OVEPUG) 19.67% (OVEPUG) 13.16% (OVEPUG) OVO SVM 14.74% (OVEPUG) 33.33% (OVRSNR) 1.70% (OVEPUG) 9.52% (BW) 19.83% (BW) 16.32% (OVRSNR) kNN 21.05% (OVEPUG) 31.67% (OVRt-stat) 2.27% (OVEPUG) 13.33% (OVEPUG) 21.81% (BW) 13.68% (OVRt-stat) NBC 36.00% (OVRSNR) 51.67% (OVRSNR) 2.83% (OVRt-stat) 37.62% (BW) 37.69% (BW) 34.21% (OVEPUG) Table 3: Performance comparison based on the lowest predictive classiﬁcation error rates produced by OVEPUG-OVRSVM and the optimum combinations of ﬁve different gene selection methods and three different classiﬁers, tested on six benchmark microarray gene expression data sets and assessed via the LOOCV scheme. accepted properties of microarray data (few discriminating features, many non-discriminating features, and with small sample size) (Hanczar and Dougherty, 2010; Wang et al., 2002). In the second approach, we directly estimated the class-conditional models based on a real microarray data set and then generated the i.i.d. samples according to the learned models. 3.4.1 D ESIGN I We simulated 5000 genes, with 90 “relevant” and 4910 “irrelevant” genes. Inspired by gene clustering concept in modelling local correlations, we divided the genes into 1000 blocks of size ﬁve, each containing exclusively either relevant or irrelevant genes. Within each block the correlation coefﬁcient is 0.9, with zero correlation across blocks. Irrelevant genes are assumed to follow a (univariate) standard normal distribution, for all classes. Relevant genes also follow a normal distribution with variance 1 for all classes. There are three equally likely classes, A, B and C. The mean vectors of the 90 relevant genes under each class are shown in Table 4. The means were chosen to make the classiﬁcation task neither too easy nor too difﬁcult and to simulate unequal distances between the classes—A and B are relatively close, with C more distant from both A and B. The mean vector µ for each class µA [2.8 2.8 2.8 2.8 2.8 1 1 1 1 1 2 2 2 2 2 0.5 0.5 0.5 0.5 0.5 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0.5 0.5 0.5 0.5 0.5 0 0 0 0 0 1 1 1 1 1 3 3 3 3 3 0.1 0.1 0.1 0.1 0.1] µB [1 1 1 1 1 2.8 2.8 2.8 2.8 2.8 2 2 2 2 2 0.5 0.5 0.5 0.5 0.5 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0.5 0.5 0.5 0.5 0.5 0 0 0 0 0 1 1 1 1 1 3 3 3 3 3 0.1 0.1 0.1 0.1 0.1] µC [1 1 1 1 1 1 1 1 1 1 14.4 14.4 14.4 14.4 14.4 8.5 8.5 8.5 8.5 8.5 8 8 8 8 8 10 10 10 10 10 10 10 10 10 10 10 9 9 9 9 9 10 10 10 10 10 3 3 3 3 3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8.5 8.5 8.5 8.5 8.5 8 8 8 8 8 9 9 9 9 9 11 11 11 11 11 7.1 7.1 7.1 7.1 7.1] Table 4: The mean vectors of the 90 relevant genes under each of the three classes. We randomly generated 100 synthetic data sets, each partitioned into a small training set of 60 samples (20 per class) and a large testing set of 6000 samples. 2155 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG 3.4.2 D ESIGN II The second approach models each class as a more realistic multivariate normal distribution N (µ, Σ), with the class’s mean vector µ and covariance matrix Σ directly learned from the real microarray data set GCM. Estimation of a covariance matrix is certainly a challenging task, speciﬁcally due to the very high dimensionality of the gene space (p = 15, 927 genes in the GCM data) and only a few dozen samples available for estimating p(p − 1)/2 free covariate parameters per class. It is also computationally prohibitive to generate random vectors based on full covariances on a general desktop computer. To address both of these problems, we applied a factor model (McLachlan and Krishnan, 2008), which can signiﬁcantly reduces the number of free parameters to be estimated while capturing the main correlation structure in the data. In factor analysis, the observed p × 1 vector t is modeled as t = µ + Wx + ε, where µ is the mean vector of observation t, W is a p × q matrix of factor loadings, x is the q × 1 latent variable vector with standard normal distribution N (0, I) and ε is noise with independent multivariate normal distribution N (0, Ψ), Ψ = diag σ2 , . . . , σ2 . The resulting covariance matrix Σ p 1 is Σ = WWT + Ψ. Estimation of Σ reduces to estimating W and Ψ, totaling p(q + 1) parameters. Usually, we have q much less than p. The factor model is learned via the EM algorithm (McLachlan and Krishnan, 2008), initialized by probabilistic principal component analysis (Tipping and Bishop, 1999). In our experiments, we set q = 5, which typically accounted for 60% of the energy. We also tried q = 3 and 7 and observed that the relative performance remained unchanged, although the absolute performance of all methods does change with q. Five phenotypic classes were used in our simulation: breast cancer, lymphoma, bladder cancer, leukemia and CNS. 100 synthetic data sets were generated randomly according to the learned class models from the real data of these ﬁve cancer types. The dimension for each sample is 15,927. For each data set, the training sample size was the same as used in the real data experiments, with 11, 22, 11, 30, and 20 samples in the ﬁve respective classes; and the testing set consisted of 3,000 samples, 600 per class. 3.5 Evaluation of Performance For a given gene-selection method and for each data set (indexed by i = 1, . . . , 100), the classiﬁer Fi is learned. We then evaluate Fi on the i-th testing set, and measure the error rate εi . Since the testing set has quite large sample size, we would expect εi to be close to the true classiﬁcation error rate for ¯ Fi . Over 100 simulation data sets, we then calculated both the average classiﬁcation error ε and the standard deviation σ. Furthermore, let εi,PUG denote the error rate associated with PUGs on testing set i, and similarly, let εi,SNR , εi,t-stat , εi,BW and εi,SV MRFE denote the error rates associated with the four peer gene selection methods. The error rate difference between two methods, for example, PUG and SNR, is deﬁned by Di (PUG, SNR) = εi,PUG − εi,SNR . 2156 PUG-OVRSVM For each synthetic data set, we deﬁne the “winner” as the one with the least testing error rate. For each method, the mean and standard deviation of the error rate and the frequency of winning are examined for performance evaluation. In addition, the histogram of error rate differences between PUG and peer methods are provided. 3.6 Experimental Results on the Simulation Data Sets We tested all gene selection methods using the common OVRSVM classiﬁer. All the experiments were done using the same procedure as on the real data sets, except with LOOCV error estimation replaced by the error estimation using large size independent testing data. Figure 4, analogous to Figure 3 while on the realistic synthetic data whose model was estimated from GCM data set (simulation data under design II), shows the comparative study on ﬁve gene selection methods (OVEPUG, OVRSNR, OVRt-stat, BW, and SVMRFE). Tables 5 and 6 show the average error, standard deviation, and frequency of winning, estimated based on the 100 simulation data sets. PUG has the smallest average error over all competing methods. PUG also is the most stable method (with the smallest standard deviation). Tables 7 and 8 provide the comparison results of the ﬁve competing methods on the ﬁrst ten data sets. Figures 5 and 6 show histograms of the error difference between PUG and other methods, where a negative value of the difference indicates better performance by PUG. The red bar shows the position where the two methods are equal. We can see that the vast majority of differences are negative. Actually, as indicated in Tables 5 and 6, there is no positive difference in the subﬁgures of Figure 5 and at most one positive difference in the subﬁgures of Figure 6. mean std deviation frequency of ‘winner’ PUG 0.0724 0.0052 100 SNR 0.1129 0.0180 0 t-stat 0.1135 0.0188 0 BW 0.1165 0.0177 0 SVMRFE 0.1203 0.0224 0 Table 5: The mean and standard deviation of classiﬁcation error and the frequency of winner based on 100 simulation data sets with design I. mean std deviation frequency of ‘winner’ PUG 0.0712 0.0201 99 SNR 0.1311 0.0447 0 t-stat 0.1316 0.0449 0 BW 0.2649 0.0302 0 SVMRFE 0.0910 0.0244 1 Table 6: The mean and standard deviation of classiﬁcation error and the frequency of winner based on 100 simulation data sets with design II. 3.7 Comparison Between PUGs and PDGs In this experiment, we selected PDGs according to the deﬁnition given in (6) and evaluated gene selection based on PUGs, PDGs, and based on their union, as given in (7). Again, all gene selection methods were coupled with the OVRSVM classiﬁer. Table 9 shows classiﬁcation performance for 2157 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG Figure 4: Comparative study on ﬁve gene selection methods (OVEPUG, OVRSNR, OVRt-stat, BW, and SVMRFE) on one simulation data set under design II. The curves of classiﬁcation error rates were generated by using OVRSVM committee classiﬁers with varying size of the input gene subset. PUG SNR t-stat BW SVMRFE sim 1 0.0864 0.1078 0.1109 0.1127 0.1030 sim 2 0.0773 0.1092 0.1089 0.0995 0.1009 sim 3 0.0697 0.1028 0.1022 0.1049 0.0967 sim 4 0.0681 0.1279 0.1251 0.1271 0.1219 sim 5 0.0740 0.1331 0.1333 0.1309 0.1248 sim 6 0.0761 0.1004 0.0991 0.1107 0.1016 sim 7 0.0740 0.1011 0.1016 0.1044 0.1107 sim 8 0.0721 0.1253 0.1268 0.1291 0.1191 sim 9 sim 10 0.0666 0.0758 0.0817 0.0838 0.0823 0.0832 0.0903 0.0845 0.1198 0.0933 Table 7: Comparison of the classiﬁcation error for the ﬁrst ten simulation data sets with design I. PUGs, PDGs and PUGs+PDGs. Clearly, PDGs have less discriminatory power than PUGs, and the inclusion of PDGs (generally) worsens classiﬁcation accuracy, compared with just using PUGs. sim 1 PUG 0.0694 SNR 0.1559 t-stat 0.1559 BW 0.2373 SVMRFE 0.0906 sim 2 0.0610 0.0659 0.0659 0.2698 0.0739 sim 3 0.0748 0.1142 0.1142 0.2510 0.0864 sim 4 0.0675 0.1211 0.1210 0.2650 0.0852 sim 5 0.0536 0.0508 0.0508 0.3123 0.0426 sim 6 0.0474 0.1937 0.1939 0.2464 0.0776 sim 7 0.0726 0.1568 0.1568 0.3070 0.0863 sim 8 0.0818 0.1464 0.1464 0.2236 0.0973 sim 9 sim 10 0.0560 0.0700 0.0797 0.0711 0.0797 0.0712 0.2800 0.3055 0.0655 0.0730 Table 8: Comparison of the classiﬁcation error for the ﬁrst ten simulation data sets with design II. 2158 PUG-OVRSVM Histogram of the error difference between PUG and SNR Histogram of the error difference between PUG and t−stat 25 20 Frequency 20 15 15 10 10 5 5 0 −0.12 −0.1 −0.08 −0.06 E PUG −0.04 −0.02 0 −0.12 0 −0.1 −0.08 −E −0.06 −0.04 E SNR PUG Histogram of the error difference between PUG and BW −0.02 0 −E t−stat Histogram of the error difference between PUG and SVMRFE 25 25 20 20 15 15 10 10 5 5 0 −0.12 −0.1 −0.08 −0.06 −0.04 −0.02 0 −0.12 0 −0.1 EPUG − EBW −0.08 −0.06 −0.04 −0.02 0 EPUG − ESVMRFE Figure 5: Histogram of the error difference between PUG and other methods with design I. Error Rate GCM NCI60 UMich CNS MD NAS PUG 11.05% 27.33% 1.08% 7.14% 19.67% 13.16% PDG 17.58% 30.33% 1.98% 9.52% 26.28% 25.79% PUG+PDG 14.53% 30.67% 1.13% 7.14% 23.14% 15.79% Table 9: Classiﬁcation comparison of PUG and PDG on the six benchmark data sets. There are several potential reasons that may jointly explain the non-contributing or even negative role of the included PDGs. First, the number of PDGs are much less than that of PUGs, that is, PUGs represent the signiﬁcant majority of informative genes when PUGs and PDGs are jointly considered, as shown in Table 10 (Top PUG+PDGs were selected with 10 genes per class and we counted how many PUGs are included in the total). Second, PDGs are less reliable than PUGs due to the noise characteristics of gene expression data, that is, low gene expressions contain relatively large additive noise after log-transformation (Huber et al., 2002; Rocke and Durbin, 2001). This is further exacerbated by the follow-up one-versus-rest classiﬁer because there are many more samples in the ‘rest’ group than in the ‘one’ group. This practically increases the relative noise/variability associated with PDGs in the ‘one’ group. In addition, PUGs are consistent with the practice of molecular pathology and thus may have broader clinical utility, for example, most currently available disease gene markers are highly expressed (Shedden et al., 2003). 2159 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG Histogram of the error difference between PUG and SNR Histogram of the error difference between PUG and t−stat 25 20 Frequency 20 15 15 10 10 5 5 0 −0.15 −0.1 −0.05 E 0 −0.15 0 −0.1 −E PUG −0.05 E SNR Histogram of the error difference between PUG and BW 0 −E PUG t−stat Histogram of the error difference between PUG and SVMRFE 20 30 25 15 20 10 15 10 5 5 0 −0.3 −0.25 −0.2 −0.15 −0.1 −0.05 E 0 −0.08 0 −0.06 −E PUG −0.04 E BW −0.02 0 −E PUG SVMRFE Figure 6: Histogram of the error difference between PUG and other methods with design II. GCM NCI60 UMich CNS MD NAS 65 No. of PUG 113 76 56 33 76 No. of PUG+PDG 140 90 60 50 130 70 % of PUG 80.71% 84.44% 93.33% 66.00% 58.46% 92.86% Table 10: Classiﬁcation comparison of PUG and PDG on the six benchmark data sets. 3.8 Marker Gene Validation by Biological Knowledge We have applied existing biological knowledge to validate biological plausibility of the selected PUG markers for two data sets, GCM and NAS. The full list of genes most highly associated with each of the 14 tumor types in the GCM data set are detailed in the Supplementary Tables 8 and 9. 3.8.1 B IOLOGICAL I NTERPRETATION FOR GCM DATA S ET Prolactin-induced protein, which is regulated by prolactin activation of its receptors, ranks highest among the PUGs associated with breast cancer. Postmenopausal breast cancer risk is strongly associated with elevated prolactin levels (PubMed IDs 15375001, 12373602, 10203283). Interestingly, prolactin release proportionally increases with increasing central fat in obese women (PubMed ID 15356045) and women with this pattern of obesity have an increased risk of breast cancer mortality (PubMed ID 14607804). Other genes of interest that rank among the top 10 breast cancer PUGs include CRABP2, which transports retinoic acid to the nucleus. Retinoids are important regulators of breast cell function and show activity as potential breast cancer chemopreventive agents (PubMed IDs 11250995, 12186376). Mammglobin is primarily expressed in normal breast epithelium and breast cancers (PubMed ID 12793902). Carbonic anhydrase XII is expressed in breast cancers and 2160 PUG-OVRSVM is generally considered a marker of a good prognosis (PubMed ID 12671706). The selective expression and/or function of these genes in breast cancers are consistent with their selection as PUGs in the classiﬁcation scheme. The top 10 PUGs associated with prostate cancer include several genes strongly associated with the prostate including prostate speciﬁc antigen (PSA) and its alternatively spliced form 2, and prostatic secretory protein 57. The role of PSA gene KLK3 and KLK1 as a biomarker of prostate cancer is well established (PubMed ID 19213567). Increased NPY expression is associated with high-grade prostatic intraepithelial neoplasia and poor prognosis in prostate cancers (PubMed ID 10561252). ACPP is another prostate speciﬁc protein biomarker (PubMed ID 8244395). The strong representation of genes that show clear selectivity for expression within the prostate illustrates the potential of the PUGs as bio-markers linked to the biology of the underlying tissues. Several of the selected PUG markers for uterine cancer ﬁt very well with our current biological understanding of this disease. It is well-established that estrogen receptor alpha (ESR1) is expressed or ampliﬁed in human uterine cancer (PubMed IDs 18720455, 17911007, 15251938), while the Hox7 gene (MSX1) contributes to uterine function in cow and mouse models, especially at the onset of pregnancy (PubMed IDs 7908629, 14976223, 19007558). Mammaglobin 2 (SCGB2A1) is highly expressed in a speciﬁc type of well-differentiated uterine cancer (endometrial cancers) (PubMed ID 18021217), and PAM expression in the rat uterus is known to be regulated by estrogen (PubMed IDs 9618561, 9441675). Other PUGs provide novel insights into uterine cancer that are deserving of further study. Our PUG selection ranks HE4 higher than the well-established CA125 marker, which may suggest HE4 as a promising alternative for the clinical management of endometrial cancer. One recent study (PubMed ID 18495222) shows that, at 95% speciﬁcity, the sensitivity of differentiating between controls and all stages of uterine cancer is 44.9% using HE4 versus 25.2% using CA125 (p = 0.0001). Osteopontin (OPN) is an integrin-binding protein that is involved in tumorigenesis and metastasis. OPN levels in the plasma of patients with ovarian cancer are much higher compared with plasma from healthy individuals (PubMed ID 11926891). OPN can increase the survival of ovarian cancer cells under stress conditions in vitro and can promote the late progression of ovarian cancer in vivo, and the survival-promoting functions of OPN are mediated through Akt activation (PubMed ID 19016748). Matrix metalloproteinase 2 (MMP2) is an enzyme degrading collagen type IV and other components of the basement membrane. MMP-2 is expressed by metastatic ovarian cancer cells and functionally regulates their attachment to peritoneal surfaces (PubMed ID 18340378). MMP2 facilitates the transmigration of human ovarian carcinoma cells across endothelial extracellular matrix (PubMed ID 15609323). Glutathione peroxidase 3 (GPX3) is one of several isoforms of peroxidases that reduce hydroperoxides to the corresponding alcohols by means of glutathione (GSH) (PubMed ID 17081103). GPX3 has been shown to be highly expressed in ovarian clear cell adenocarcinoma. Moreover, GPX3 has been associated with low cisplatin sensitivity (PubMed ID 19020706). 3.8.2 B IOLOGICAL I NTERPRETATION FOR NAS DATA S ET Several top-ranking gene products identiﬁed by our computational method have been well established as tumor-type speciﬁc markers and many of them have been used in clinical diagnosis. For example, mucin 16, also known as CA125, is a FDA-approved serum marker to monitor disease progression and recurrence in ovarian cancer patients (PubMed ID 19042984). Likewise, kallikrein 2161 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG family members including KLK6 and KLK8 are known to be ovarian cancer associated markers which can be detected in body ﬂuids in ovarian cancer patients (PubMed ID 17303231). TITF1 (also known as TTF1) has been reported as a relatively speciﬁc marker in lung adenocarcinoma (PubMed ID 17982442) and it has been used to assist differential diagnosis of lung cancer from other types of carcinoma. Fatty acid synthase (FASN) is a well-known gene that is often upregulated in breast cancer (PubMed ID 17631500) and the enzyme is amenable for drug targeting using FASN inhibitors, suggesting that it can be used as a therapeutic target in breast cancer. The above ﬁndings indicate the robustness of our computational method in identifying tumor-type speciﬁc markers and in classifying different types of neoplastic diseases. Such information could be useful in translational studies (PubMed ID 12874019). Metastatic carcinoma of unknown origin is a relatively common presentation in cancer patients and an accurate diagnosis of the tumor type in the metastatic diseases is important to direct appropriate treatment and predict clinical outcome. The distinctive patterns of gene expression characteristic to various types of cancer may help pathologists and clinicians to better manage their patients. 3.9 Gene Comparisons Between Methods It may be informative to provide some initial analysis on how the selected genes compare between methods; however, without deﬁnitive ground truth on cancer markers, the utility of this information is somewhat limited and should, thus, be treated as anecdotal, rather than conclusive. Speciﬁcally, we have now done some assessment of how differentially these gene selection methods rank some known cancer marker genes. The overlap rate is deﬁned as the number of genes commonly selected by two methods over the maximum size of the two selected gene sets. Let G1 and G2 denote the gene sets selected by gene selection methods 1 and 2, respectively, and |G| denote the cardinality (the size) of set G. The overlap rate between G1 and G2 is R= |G1 ∩ G2 | . max (|G1 | , |G2 |) Table 11 shows the overlap rate between methods on the top 100 genes per class. We can see that the overlap rates between methods are generally low except for the pair of SNR and t-stat. BW genes are quite different from the genes selected by all other methods and have only about 15% overlap rate with PUG and SVMRFE. The relatively high overlap rate between SNR and t-stat may be expected since they use quite similar summary statistics in their selection criteria. We have also examined a total of 16 genes with known associations with 4 tumor types. These 16 genes are well-known markers supported by current biological knowledge. The rank of biomedical importance of these genes produced by each method is summarized in Table 12. When a gene is not listed in the top 100 genes by a wrapper method like SVMRFE, we simply assign the rank as ‘>100’. Generally but not uniformly across cancer types, these validated marker genes are highly ranked in the PUGs list as compared to other methods, and thus will be surely selected by PUG criterion. 4. Discussion In this paper, we address several critical yet subtle issues in multicategory molecular classiﬁcation applied to real-world biological and/or clinical applications. We propose a novel gene selection methodology matched to the multicategory classiﬁcation approach (potentially with an unbalanced 2162 PUG-OVRSVM Overlapping Rate PUG SNR t-stat BW SVMRFE PUG 1 0.4117 0.3053 0.1450 0.4057 SNR 0.4117 1 0.7439 0.3307 0.3841 t-stat 0.3053 0.7439 1 0.2907 0.3941 BW 0.1450 0.3307 0.2907 1 0.1307 SVMRFE 0.4057 0.3841 0.3941 0.1307 1 Table 11: The overlapping rate between methods on the top 100 genes per class. Breast Cancer Relevant Genes Prostate Cancer Relevant Genes Rank Rank Gene Symbol Gene Symbol PUG SNR t-stat BW SVMRFE PUG SNR t-stat BW SVMRFE PIP 1 5745 6146 473 >100 KLK3 4 5 11 61 15 CRABP2 4 5965 6244 498 >100 KLK1 5 3 9 76 16 SCGB2A2 6 6693 6773 458 14 NPY 7 18 22 344 30 CA12 9 6586 6647 518 >100 ACPP 3 4 8 71 12 Uterine Cancer Relevant Genes Gene Symbol Ovarian Cancer Relevant Genes Rank Rank Gene Symbol PUG SNR t-stat BW SVMRFE PUG SNR t-stat BW SVMRFE ESR1 1 2 16 130 5 OPN 15 334 517 371 63 Hox7 2 4 52 307 12 MMP2 42 2626 3045 481 >100 SCGB2A1 8 3 19 190 4 GPX3 7 411 >100 PAM HE4 10 3 83 1 281 3 365 99 71 5 812 446 Table 12: Detailed comparison between methods on several validated marker genes. mixture distribution) that is not a straightforward pooled extension of binary (two-class) differential analysis. We emphasize the statistical reproducibility and biological plausibility of the selected gene markers under small sample size, supported by their detailed biological interpretations. We tested our method on six benchmark and in-house real microarray gene expression data sets and compared its performance with that of several existing methods. We imposed a rigorous performance assessment where each and all components of the scheme including gene selection are subjected to cross-validation, for example, held-out/unseen samples in a testing fold are not used for any phase of classiﬁer training. Tested on six benchmark real microarray data sets, the proposed PUG-OVRSVM method outperforms several widely-adopted gene selection and classiﬁcation methods with lower error rates, fewer marker genes, and higher performance sustainability. Moreover, while for some data sets, the absolute gain in classiﬁcation accuracy percentage of PUG-OVRSVM is not dramatically large, it must be recognized that the performance may be approaching the minimum Bayes error rate, in which case PUG-OVRSVM is achieving nearly all the improvement that is theoretically attainable. Furthermore, the improved performance is achieved by correct classiﬁcations on some of the most difﬁcult cases, which is considered signiﬁcant for clinical diagnosis (Ramaswamy et al., 2001). Lastly, although improvements will be data set-dependent, our multi-data set tests have shown that PUG-OVRSVM is the consistent winner as compared to several peer methods. 2163 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG We note that we have opted for simplicity as opposed to theoretical optimality in designing our method. Our primary goal was to demonstrate that a small number of reproducible phenotypicdependent genes are sufﬁcient to achieve improved multicategory classiﬁcation, that is, small sample sizes and a large number of classes need not preclude a high level of performance. Our studies suggest that using genes’ marginal associations with the phenotypic categories as we do here has the potential to stabilize the learning process, leading to a substantial reduction in performance variability with small sample size; whereas, the current generation of complex gene selection techniques may not be stable or powerful enough to reliably exploit gene interactions and/or variations unless the sample size is sufﬁciently large. We have not explored the full ﬂexibility that this method readily allows, with different numbers of subPUGs used by different classiﬁers. Presumably, equal or better performance could be achieved with fewer genes if more markers were selected for the most difﬁcult classiﬁcations, involving the nearest phenotypes. However, such ﬂexibility could actually degrade performance in practice since it introduces extra design choices and, thus, extra sources of variation in classiﬁcation performance. We may also extend our method to account for variation in fold-changes, with the uncertainty estimated on bootstrap samples judiciously applied to eliminate those PUGs with high variations. Notably, multicategory classiﬁcation is intrinsically a nonlinear classiﬁcation problem, and this method (using one-versus-everyone fold-change based PUG selection, linear kernel SVMs, and the MAP decision rule) is most practically suitable to discriminating unimodal classes. Future work will be required to extend PUG-OVRSVM for multimodal class distributions. An elegant yet simple strategy is to introduce unimodal pseudo-classes for the multi-modal classes via a preclustering step, with the ﬁnal class decision readily made without the need of any decision combiner. Speciﬁcally, for each (pseudo-class, super pseudo-class) pair (where, for a pseudo-class originating from class k, the paired super pseudo-class is the union of all pseudo-classes that do not belong to class k), a separating hyperplane is constructed. Accordingly, in selecting subPUGs for each pseudo-class, the pseudo-classes originating from the same class will not be considered. Acknowledgments This work was supported in part by the US National Institutes of Health under Grants CA109872, CA149147, CA139246, EB000830, NS29525, and under Contract No. HHSN261200800001E. References M. Bakay, Z. Wang, G. Melcon, L. Schiltz, J. Xuan, P. Zhao, V. Sartorelli, J. Seo, E. Pegoraro, C. Angelini, B. Shneiderman, D. Escolar, Y. W. Chen, S. T. Winokur, L. M. Pachman, C. Fan, R. Mandler, Y. Nevo, E. Gordon, Y. Zhu, Y. Dong, Y. Wang, and E. P. Hoffman. Nuclear envelope dystrophies show a transcriptional ﬁngerprint suggesting disruption of Rb-MyoD pathways in muscle regeneration. Brain, 129(Pt 4):996–1013, 2006. U. M. Braga-Neto and E. R. Dougherty. Is cross-validation valid for small-sample microarray classiﬁcation? Bioinformatics, 20(3):374–80, 2004. Z. Cai, R. Goebel, M. R. Salavatipour, and G. Lin. Selecting dissimilar genes for multi-class classiﬁcation, an application in cancer subtyping. BMC Bioinformatics, 8:206, 2007. 2164 PUG-OVRSVM R. Clarke, H. W. Ressom, A. Wang, J. Xuan, M. C. Liu, E. A. Gehan, and Y. Wang. The properties of high-dimensional data spaces: implications for exploring gene and protein expression data. Nat Rev Cancer, 8(1):37–49, 2008. R. O. Duda, P. E. Hart, and D. G. Stork. Pattern classiﬁcation. Wiley, New York, 2nd edition, 2001. S. Dudoit, J. Fridlyand, and T. P. Speed. Comparison of discrimination methods for the classiﬁcation of tumors using gene expression data. Journal of the American Statistical Association, 97(457): 77–87, 2002. B. P. Durbin, J. S. Hardin, D. M. Hawkins, and D. M. Rocke. A variance-stabilizing transformation for gene-expression microarray data. Bioinformatics, 18 Suppl 1:S105–10, 2002. G. Fort and S. Lambert-Lacroix. Classiﬁcation using partial least squares with penalized logistic regression. Bioinformatics, 21(7):1104–11, 2005. H. Gish. A probabilistic approach to the understanding and training of neural network classiﬁers. In IEEE Intl. Conf. Acoust., Speech, Signal Process., pages 1361–1364, 1990. T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P. Mesirov, H. Coller, M. L. Loh, J. R. Downing, M. A. Caligiuri, C. D. Bloomﬁeld, and E. S. Lander. Molecular classiﬁcation of cancer: class discovery and class prediction by gene expression monitoring. Science, 286 (5439):531–7, 1999. I. Guyon, J. Weston, S. Barnhill, and V. Vladimir. Gene selection for cancer classiﬁcation using support vector machines. Machine Learning, 46(1-3):389–422, 2002. B. Hanczar and E. R. Dougherty. On the comparison of classiﬁers for microarray data. Current Bioinformatics, 5(1):29–39, 2010. T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, New York, 2001. W. Huber, A. von Heydebreck, H. Sultmann, A. Poustka, and M. Vingron. Variance stabilization applied to microarray data calibration and to the quantiﬁcation of differential expression. Bioinformatics, 18 Suppl 1:S96–104, 2002. C. Lai, M. J. Reinders, L. J. van’t Veer, and L. F. Wessels. A comparison of univariate and multivariate gene selection techniques for classiﬁcation of cancer datasets. BMC Bioinformatics, 7: 235, 2006. F. Li and Y. Yang. Analysis of recursive gene selection approaches from microarray data. Bioinformatics, 21(19):3741–7, 2005. T. Li, C. Zhang, and M. Ogihara. A comparative study of feature selection and multiclass classiﬁcation methods for tissue classiﬁcation based on gene expression. Bioinformatics, 20(15):2429–37, 2004. H. Liu, J. Li, and L. Wong. A comparative study on feature selection and classiﬁcation methods using gene expression proﬁles and proteomic patterns. Genome Informatics, 13:51–60, 2002. 2165 Y U , F ENG , M ILLER , X UAN , H OFFMAN , C LARKE , DAVIDSON , S HIH AND WANG J. J. Liu, G. Cutler, W. Li, Z. Pan, S. Peng, T. Hoey, L. Chen, and X. B. Ling. Multiclass cancer classiﬁcation and biomarker discovery using GA-based algorithms. Bioinformatics, 21(11):2691– 7, 2005. M. Loog, R. P. W. Duin, and R. Haeb-Umbach. Multiclass linear dimension reduction by weighted pairwise ﬁsher criteria. IEEE Trans Pattern Anal Machine Intell, 23(7):762–766, 2001. G. J. McLachlan and T. Krishnan. The EM Algorithm and Extensions. Wiley-Interscience, Hoboken, N.J., 2nd edition, 2008. C. H. Ooi and P. Tan. Genetic algorithms applied to multi-class prediction for the analysis of gene expression data. Bioinformatics, 19(1):37–44, 2003. S. L. Pomeroy, P. Tamayo, M. Gaasenbeek, L. M. Sturla, M. Angelo, M. E. McLaughlin, J. Y. Kim, L. C. Goumnerova, P. M. Black, C. Lau, J. C. Allen, D. Zagzag, J. M. Olson, T. Curran, C. Wetmore, J. A. Biegel, T. Poggio, S. Mukherjee, R. Rifkin, A. Califano, G. Stolovitzky, D. N. Louis, J. P. Mesirov, E. S. Lander, and T. R. Golub. Prediction of central nervous system embryonal tumour outcome based on gene expression. Nature, 415(6870):436–42, 2002. S. Ramaswamy, P. Tamayo, R. Rifkin, S. Mukherjee, C. H. Yeang, M. Angelo, C. Ladd, M. Reich, E. Latulippe, J. P. Mesirov, T. Poggio, W. Gerald, M. Loda, E. S. Lander, and T. R. Golub. Multiclass cancer diagnosis using tumor gene expression signatures. Proc Natl Acad Sci U S A, 98(26):15149–54, 2001. R. Rifkin and A. Klautau. In defense of one-vs-all classiﬁcation. Journal of Machine Learning Research, 5:101–141, 2002. D. M. Rocke and B. Durbin. A model for measurement error for gene expression arrays. J Comput Biol, 8(6):557–69, 2001. K. A. Shedden, J. M. Taylor, T. J. Giordano, R. Kuick, D. E. Misek, G. Rennert, D. R. Schwartz, S. B. Gruber, C. Logsdon, D. Simeone, S. L. Kardia, J. K. Greenson, K. R. Cho, D. G. Beer, E. R. Fearon, and S. Hanash. Accurate molecular classiﬁcation of human cancers based on gene expression using a simple classiﬁer with a pathological tree-based framework. Am J Pathol, 163 (5):1985–95, 2003. L. Shi, W. D. Jones, R. V. Jensen, S. C. Harris, R. G. Perkins, F. M. Goodsaid, L. Guo, L. J. Croner, C. Boysen, H. Fang, F. Qian, S. Amur, W. Bao, C. C. Barbacioru, V. Bertholet, X. M. Cao, T. M. Chu, P. J. Collins, X. H. Fan, F. W. Frueh, J. C. Fuscoe, X. Guo, J. Han, D. Herman, H. Hong, E. S. Kawasaki, Q. Z. Li, Y. Luo, Y. Ma, N. Mei, R. L. Peterson, R. K. Puri, R. Shippy, Z. Su, Y. A. Sun, H. Sun, B. Thorn, Y. Turpaz, C. Wang, S. J. Wang, J. A. Warrington, J. C. Willey, J. Wu, Q. Xie, L. Zhang, L. Zhang, S. Zhong, R. D. Wolﬁnger, and W. Tong. The balance of reproducibility, sensitivity, and speciﬁcity of lists of differentially expressed genes in microarray studies. BMC Bioinformatics, 9 Suppl 9:S10, 2008. A. Statnikov, C. F. Aliferis, I. Tsamardinos, D. Hardin, and S. Levy. A comprehensive evaluation of multicategory classiﬁcation methods for microarray gene expression cancer diagnosis. Bioinformatics, 21(5):631–43, 2005. 2166 PUG-OVRSVM J. E. Staunton, D. K. Slonim, H. A. Coller, P. Tamayo, M. J. Angelo, J. Park, U. Scherf, J. K. Lee, W. O. Reinhold, J. N. Weinstein, J. P. Mesirov, E. S. Lander, and T. R. Golub. Chemosensitivity prediction by transcriptional proﬁling. Proc Natl Acad Sci U S A, 98(19):10787–92, 2001. R. Tibshirani, T. Hastie, B. Narasimhan, and G. Chu. Diagnosis of multiple cancer types by shrunken centroids of gene expression. Proc Natl Acad Sci U S A, 99(10):6567–72, 2002. M. E. Tipping and C.M. Bishop. Probabilistic principle component analysis. Journal of the Royal Statistical Society. Series B, 61(3):611–622, 1999. V. N. Vapnik. Statistical Learning Theory. Adaptive and learning systems for signal processing, communications, and control. Wiley, New York, 1998. Y. Wang, J. Lu, R. Lee, Z. Gu, and R. Clarke. Iterative normalization of cNDA microarray data. IEEE Trans Info. Tech. Biomed, 6(1):29–37, 2002. Y. Wang, J. Zhang, J. Khan, R. Clarke, and Z. Gu. Partially-independent component analysis for tissue heterogeneity correction in microarray gene expression analysis. In IEEE Workshop on Neural Networks for Signal Processing, pages 24–32, 2003. Y. Wang, D. J. Miller, and R. Clarke. Approaches to working in high-dimensional data spaces: gene expression microarrays. Br J Cancer, 98(6):1023–8, 2008. Z. Wang, Y. Wang, J. Xuan, Y. Dong, M. Bakay, Y. Feng, R. Clarke, and E. P. Hoffman. Optimized multilayer perceptrons for molecular classiﬁcation and diagnosis using genomic data. Bioinformatics, 22(6):755–61, 2006. J. Xuan, Y. Wang, Y. Dong, Y. Feng, B. Wang, J. Khan, M. Bakay, Z. Wang, L. Pachman, S. Winokur, Y. W. Chen, R. Clarke, and E. Hoffman. Gene selection for multiclass prediction by weighted ﬁsher criterion. EURASIP J Bioinform Syst Biol, page 64628, 2007. C. H. Yeang, S. Ramaswamy, P. Tamayo, S. Mukherjee, R. M. Rifkin, M. Angelo, M. Reich, E. Lander, J. Mesirov, and T. Golub. Molecular classiﬁcation of multiple tumor types. Bioinformatics, 17 Suppl 1:S316–22, 2001. J. Zhang, L. Wei, X. Feng, Z. Ma, and Y. Wang. Pattern expression non-negative matrix factorization: Algorithm and application to blind source separation. Computational Intelligence and Neuroscience, page Artical ID 168769, 2008. Y. Zhao, M. C. Li, and R. Simon. An adaptive method for cDNA microarray normalization. BMC Bioinformatics, 6:28, 2005. X. Zhou and D. P. Tuck. MSVM-RFE: extensions of SVM-RFE for multiclass gene selection on DNA microarray data. Bioinformatics, 23(9):1106–14, 2007. 2167

6 0.63555872 22 jmlr-2010-Classification Using Geometric Level Sets

7 0.62705183 11 jmlr-2010-An Investigation of Missing Data Methods for Classification Trees Applied to Binary Response Data

8 0.61957747 16 jmlr-2010-Asymptotic Equivalence of Bayes Cross Validation and Widely Applicable Information Criterion in Singular Learning Theory

9 0.60646862 9 jmlr-2010-An Efficient Explanation of Individual Classifications using Game Theory

10 0.59956074 102 jmlr-2010-Semi-Supervised Novelty Detection

11 0.59471166 94 jmlr-2010-Quadratic Programming Feature Selection

12 0.59457743 114 jmlr-2010-Unsupervised Supervised Learning I: Estimating Classification and Regression Errors without Labels

13 0.58283859 113 jmlr-2010-Tree Decomposition for Large-Scale SVM Problems

14 0.58209652 59 jmlr-2010-Large Scale Online Learning of Image Similarity Through Ranking

15 0.57576078 48 jmlr-2010-How to Explain Individual Classification Decisions

16 0.57322615 23 jmlr-2010-Classification with Incomplete Data Using Dirichlet Process Priors

17 0.57303768 49 jmlr-2010-Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data

18 0.57220644 74 jmlr-2010-Maximum Relative Margin and Data-Dependent Regularization

19 0.56360239 107 jmlr-2010-Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion

20 0.55696076 33 jmlr-2010-Efficient Heuristics for Discriminative Structure Learning of Bayesian Network Classifiers