jmlr jmlr2008 jmlr2008-1 knowledge-graph by maker-knowledge-mining

1 jmlr-2008-A Bahadur Representation of the Linear Support Vector Machine

Source: pdf

Author: Ja-Yong Koo, Yoonkyung Lee, Yuwon Kim, Changyi Park

Abstract: The support vector machine has been successful in a variety of applications. Also on the theoretical front, statistical properties of the support vector machine have been studied quite extensively with a particular attention to its Bayes risk consistency under some conditions. In this paper, we study somewhat basic statistical properties of the support vector machine yet to be investigated, namely the asymptotic behavior of the coefﬁcients of the linear support vector machine. A Bahadur type representation of the coefﬁcients is established under appropriate conditions, and their asymptotic normality and statistical variability are derived on the basis of the representation. These asymptotic results do not only help further our understanding of the support vector machine, but also they can be useful for related statistical inferences. Keywords: asymptotic normality, Bahadur representation, classiﬁcation, convexity lemma, Radon transform

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Also on the theoretical front, statistical properties of the support vector machine have been studied quite extensively with a particular attention to its Bayes risk consistency under some conditions. [sent-10, score-0.066]

2 In this paper, we study somewhat basic statistical properties of the support vector machine yet to be investigated, namely the asymptotic behavior of the coefﬁcients of the linear support vector machine. [sent-11, score-0.254]

3 A Bahadur type representation of the coefﬁcients is established under appropriate conditions, and their asymptotic normality and statistical variability are derived on the basis of the representation. [sent-12, score-0.38]

4 These asymptotic results do not only help further our understanding of the support vector machine, but also they can be useful for related statistical inferences. [sent-13, score-0.225]

5 Keywords: asymptotic normality, Bahadur representation, classiﬁcation, convexity lemma, Radon transform 1. [sent-14, score-0.256]

6 These include studies on the Bayes risk consistency of the SVM (Lin, 2002; Zhang, 2004; Steinwart, 2005) and its rate of convergence to the Bayes risk (Lin, 2000; Blanchard, Bousquet, and Massart, 2008; Scovel and Steinwart, 2007; Bartlett, Jordan, and McAuliffe, 2006). [sent-18, score-0.074]

7 KOO , L EE , K IM AND PARK existing theoretical analysis of the SVM largely concerns its asymptotic risk, there are some basic statistical properties of the SVM that seem to have eluded our attention. [sent-20, score-0.196]

8 We mainly investigate asymptotic properties of the coefﬁcients of variables in the SVM solution for linear classiﬁcation. [sent-23, score-0.196]

9 Due to these assumptions, the asymptotic results become more pertinent to the classical parametric setting where the number of features is moderate compared to the sample size and the virtue of regularization is minute than to the situation with high dimensional inputs. [sent-26, score-0.196]

10 Despite the difference between the practical situation where the SVM methods are effectively used and the setting theoretically posited in this paper, the asymptotic results shed a new light on the SVM from a classical parametric point of view. [sent-27, score-0.196]

11 In particular, we establish a Bahadur type representation of the coefﬁcients as in the studies of sample quantiles and estimates of regression quantiles. [sent-28, score-0.066]

12 It turns out that the Bahadur type representation of the SVM coefﬁcients depends on Radon transform of the second moments of the variables. [sent-30, score-0.083]

13 This representation illuminates how the so called margins of the optimal separating hyperplane and the underlying probability distribution within and around the margins determine the statistical behavior of the estimated coefﬁcients. [sent-31, score-0.274]

14 Asymptotic normality of the coefﬁcients then follows immediately from the representation. [sent-32, score-0.089]

15 The proximity of the hinge loss function that deﬁnes the SVM solution to the absolute error loss and its convexity allow such asymptotic results akin to those for least absolute deviation regression estimators in Pollard (1991). [sent-33, score-0.307]

16 In addition to providing an insight into the asymptotic behavior of the SVM, we expect that our results can be useful for related statistical inferences on the SVM, for instance, feature selection. [sent-34, score-0.221]

17 Its selection or elimination criterion is based on the absolute value of a coefﬁcient not its standardized value. [sent-37, score-0.144]

18 The asymptotic variability of estimated coefﬁcients that we provide can be used in deriving a new feature selection criterion which takes inherent statistical variability into account. [sent-38, score-0.384]

19 Section 2 contains the main results of a Bahadur type representation of the linear SVM coefﬁcients and their asymptotic normality under mild conditions. [sent-40, score-0.313]

20 Main Results In this section, we ﬁrst introduce some notations and discuss our asymptotic results for the linear SVM coefﬁcients. [sent-44, score-0.196]

21 Let f and g be the densities of X given Y = 1 and −1 with respect to the Lebesgue measure. [sent-48, score-0.078]

22 For separable cases, the SVM ﬁnds the hyperplane that maximizes the geometric margin, 2/ β+ 2 subject to the constraints yi h(xi ; β) ≥ 1 for i = 1, . [sent-69, score-0.163]

23 Let the minimizer of (1) be denoted by βλ,n = arg minβ lλ,n (β). [sent-78, score-0.078]

24 In this paper, we consider only nonseparable cases and assume that λ → 0 as n → ∞. [sent-81, score-0.091]

25 We note that separable cases require a different treatment for asymptotics because λ has to be nonzero in the limit for the uniqueness of the solution. [sent-82, score-0.144]

26 Before we proceed with a discussion of the asymptotics of the βλ,n , we introduce some notation and deﬁnitions ﬁrst. [sent-83, score-0.066]

27 The population version of (1) without the penalty term is deﬁned as L(β) = E 1 −Y h(X; β) (2) + and its minimizer is denoted by β∗ = arg minβ L(β). [sent-84, score-0.078]

28 Then the population version of the optimal hyperplane deﬁned by the SVM is x β∗ = 0. [sent-85, score-0.111]

29 For 0 ≤ j, k ≤ d, the ( j, k)-th element of the Hessian matrix H(β) is given by H(β) jk = π+ (R f jk )(1 − β0 , β+ ) + π− (R g jk )(1 + β0 , −β+ ), (4) where f jk (x) = x j xk f (x) and g jk (x) = x j xk g(x). [sent-94, score-0.685]

30 Equation (4) shows that the Hessian matrix H(β) depends on the Radon transforms of f jk and g jk for 0 ≤ j, k ≤ d. [sent-95, score-0.238]

31 If f and g are continuous densities with ﬁnite second moments, then f jk and g jk are continuous and integrable for 0 ≤ j, k ≤ d. [sent-98, score-0.409]

32 2 Asymptotics Now we present the asymptotic results for βλ,n . [sent-101, score-0.196]

33 (A1) The densities f and g are continuous and have ﬁnite second moments. [sent-108, score-0.108]

34 • The technical condition in (A3) is a minimal requirement to guarantee that β ∗ , the normal + vector of the theoretically optimal hyperplane is not zero. [sent-116, score-0.163]

35 The condition means that there exist two subsets of the classiﬁcation margins, M + and M − on which the class densities f and g are bounded away from zero. [sent-122, score-0.078]

36 The asymptotic normality of βλ,n follows immediately from the representation (Theorem 2). [sent-130, score-0.313]

37 Consequently, we have the asymptotic normality of h(x; βλ,n ), the value of the SVM decision function at x (Corollary 3). [sent-131, score-0.285]

38 To estimate H(β∗ ), one may consider the following nonparametric estimate: 1 n n ∑ pb 1 −Y i h(X i ; βλ,n ) X i (X i ) i=1 , where pb (t) ≡ p(t/b)/b, p(t) ≥ 0 and R p(t)dt = 1. [sent-137, score-0.076]

39 An Illustrative Example In this section, we illustrate the relation between the Bayes decision boundary and the optimal hyperplane determined by (2) for two multivariate normal distributions in R d . [sent-144, score-0.196]

40 Assume that f and g are multivariate normal densities with different mean vectors µ f and µg and a common covariance matrix Σ. [sent-145, score-0.13]

41 For normal densities f and g, (A1) holds trivially, and (A2) is satisﬁed with C1 = |2πΣ|−1/2 exp − sup x ≤δ0 (x − µ f ) Σ−1 (x − µ f ), (x − µg ) Σ−1 (x − µg ) for δ0 > 0. [sent-148, score-0.13]

42 Since D + and D − can be taken to be bounded sets of the form in (A4) in Rd−1 , and the normal densities f and g are bounded away from zero on such D + and D − , (A4) is satisﬁed. [sent-151, score-0.13]

43 Hence deﬁnition of a f and ag , we have a f g where a f = , ag = (β∗ ) (µ f + µg ) = −2β∗ . [sent-156, score-0.094]

44 2a∗ dΣ (µ f , µg ) + dΣ (µ f , µg )2 Thus the optimal hyperplane (3) is 2 Σ−1 (µ f − µg ) 2a∗ dΣ (µ f , µg ) + dΣ (µ f , µg )2 1 x − (µ f + µg ) = 0, 2 which is equivalent to the Bayes decision boundary given by 1 x − (µ f + µg ) = 0. [sent-182, score-0.144]

45 The asymptotic variabilities of the intercept and the slope for the optimal decision boundary are calculated according to Theorem 2. [sent-186, score-0.35]

46 Figure 2 shows the asymptotic variabilities as a function of the Mahalanobis distance between the two normal distributions, |µ f − µg | in this case. [sent-187, score-0.303]

47 Also, it depicts the asymptotic variance ˆ ˆ of the estimated classiﬁcation boundary value (−β0 /β1 ) by using the delta method. [sent-188, score-0.282]

48 Although the Mahalanobis distance roughly in the range of 1 to 4 would be of practical interest, the plots show a notable trend in the asymptotic variances as the distance varies. [sent-189, score-0.196]

49 A possible explanation for the trend is that the intercept and the slope of the optimal hyperplane are determined by only a small fraction of data falling into the margins in this case. [sent-192, score-0.232]

50 Simulation Studies In this section, simulations are carried out to illustrate the asymptotic results and their potential for feature selection. [sent-194, score-0.196]

51 To see the direct effect of the hinge loss on the SVM coefﬁcients without regularization as in the way the asymptotic properties in Section 2 are characterized ultimately, we estimated the coefﬁcients of the linear SVM without the penalty term by linear programming. [sent-203, score-0.253]

52 The solid ˆ ˆ lines are the estimated density functions of β0 and β1 for n = 500, and the dotted lines are the corresponding asymptotic normal densities in Theorem 2. [sent-207, score-0.351]

53 0 0 1 1 2 3 Density 4 3 2 Density estimate asymptotic 5 estimate asymptotic −0. [sent-220, score-0.392]

54 0 (b) ˆ ˆ Figure 3: Estimated sampling distributions of (a) β0 and (b) β1 with the asymptotic normal densities overlaid. [sent-231, score-0.326]

55 By using the asymptotic variability of estimated coefﬁcients, one can derive a new feature selection criterion based on the standardized coefﬁcients. [sent-235, score-0.381]

56 Such a criterion will take inherent statistical variability into account. [sent-236, score-0.067]

57 1352 A BAHADUR R EPRESENTATION OF THE L INEAR S UPPORT V ECTOR M ACHINE ˆ We investigate the possibility of using the standardized coefﬁcients of β for selection of variables. [sent-238, score-0.093]

58 For practical applications, one needs to construct a reasonable nonparametric estimator of the asymptotic variance-covariance matrix, whose entries are deﬁned through line integrals. [sent-239, score-0.196]

59 For the sake of simplicity in the second set of simulation, we used the theoretical asymptotic ˆ variance in standardizing β and selected those variables with the absolute standardized coefﬁcient exceeding a certain critical value. [sent-242, score-0.285]

60 And we mainly monitored the type I error rate of falsely declaring the signiﬁcance of a variable when it is not, over various settings of a mixture of two multivariate normal distributions. [sent-243, score-0.077]

61 Thus only the ﬁrst half of the d variables have nonzero coefﬁcients in the optimal hyperplane of the linear SVM. [sent-246, score-0.111]

62 Table 2 shows the minima, median, and maxima of such type I error rates in selection of relevant variables over 200 replicates when the critical value was z0. [sent-247, score-0.088]

63 If the asymptotic distributions were accurate, the error rates would be close to the nominal level of 0. [sent-250, score-0.262]

64 On the whole, the table suggests that when d is small, the error rates are very close to the nominal level even for small sample sizes, while for a large d, n has to be quite large for the asymptotic distributions to be valid. [sent-252, score-0.262]

65 105] Table 2: The minimum, median, and maximum values of the type I error rates of falsely ﬂagging an irrelevant variable as relevant over 200 replicates by using the standardized SVM coefﬁcients at 5% signiﬁcance level. [sent-351, score-0.148]

66 We leave further development of asymptotic variance estimators for feature selection and comparison with risk based approaches such as the recursive feature elimination procedure as a future work. [sent-352, score-0.288]

67 Discussion In this paper, we have investigated asymptotic properties of the coefﬁcients of variables in the SVM solution for nonseparable linear classiﬁcation. [sent-354, score-0.287]

68 6 d=6 d=12 d=18 d=24 500 1000 1500 2000 n Figure 4: The median values of the type I error rates in variable selection depending on the sample size n and the number of variables d. [sent-363, score-0.091]

69 type representation of the coefﬁcients and their asymptotic normality using Radon transformation of the second moments of the variables. [sent-366, score-0.337]

70 The representation shows how the statistical behavior of the coefﬁcients is determined by the margins of the optimal hyperplane and the underlying probability distribution. [sent-367, score-0.194]

71 Shedding a new statistical light on the SVM, these results provide an insight into its asymptotic behavior and can be used to improve our statistical practice with the SVM in various aspects. [sent-368, score-0.196]

72 The asymptotic results that we have obtained so far pertain only to the linear SVM in nonseparable cases. [sent-370, score-0.287]

73 Although it may be of more theoretical consideration than practical, a similar analysis of the linear SVM in the separable case is anticipated, which will ultimately lead to a uniﬁed theory for separable as well as nonseparable cases. [sent-371, score-0.195]

74 The separable case would require a slightly different treatment than the nonseparable case because the regularization parameter λ needs to remain positive in the limit to guarantee the uniqueness of the solution. [sent-372, score-0.169]

75 An extension of the SVM asymptotics to the nonlinear case is another direction of interest. [sent-373, score-0.066]

76 In this case, the minimizer deﬁned by the SVM is not a vector of coefﬁcients of a ﬁxed length but a function in a reproducing kernel Hilbert space. [sent-374, score-0.078]

77 So, the study of asymptotic properties of the minimizer in the function space essentially requires investigation of its pointwise behavior or its functionals in general as the sample size grows. [sent-375, score-0.274]

78 A general theory in Shen (1997) on asymptotic normality and efﬁciency of substitution estimates for smooth functionals is relevant. [sent-376, score-0.285]

79 In particular, Theorem 2 in Shen (1997) provides the asymptotic normality of the penalized sieve MLE, char1354 A BAHADUR R EPRESENTATION OF THE L INEAR S UPPORT V ECTOR M ACHINE acterization of which bears a close resemblance with function estimation for the nonlinear case. [sent-377, score-0.285]

80 Consideration of these extensions will lead to a more complete picture of the asymptotic behavior of the SVM solution. [sent-380, score-0.196]

81 1 Technical Lemmas Lemma 1 shows that there is a ﬁnite minimizer of L(β), which is useful in proving the uniqueness of the minimizer in Lemma 6. [sent-384, score-0.182]

82 For 0 ≤ w0 < 1 and 0 < ε < 1, vol ({|h(x; w)| ≥ ε} ∩ B(0, δ0 )) ≥ vol ({h(x; w) ≥ ε} ∩ B(0, δ0 )) 1 − w2 ∩ B(0, δ0 ) 0 = vol ≥ vol since (ε − w0 )/ x w+ / 1 − w2 ≥ (ε − w0 )/ 0 x w+ / 1 − w2 ≥ ε ∩ B(0, δ0 ) ≡ V (δ0 , ε) 0 1 − w2 ≤ ε. [sent-393, score-0.66]

83 h(x; β) > 1 1 − tx j < h(x; β) ≤ 1 h(x; β) ≤ 1 − tx j . [sent-409, score-0.258]

84 Observe that Z X ∆(t){x j > 0} f (x)dx = Z {1 − tx j < h(x; β) ≤ 1}(h(x; β) − 1) f (x)dx XZ −t X {h(x; β) ≤ 1 − tx j , x j > 0}x j f (x)dx and that 1 {1 − tx j < h(x; β) ≤ 1}(h(x; β) − 1) f (x)dx ≤ {1 − tx j < h(x; β) ≤ 1}x j f (x)dx. [sent-410, score-0.516]

85 t X X Z Z 1356 A BAHADUR R EPRESENTATION OF THE L INEAR S UPPORT V ECTOR M ACHINE By Dominated Convergence Theorem, {1 − tx j < h(x; β) ≤ 1}x j f (x)dx = Z X {h(x; β) = 1}x j f (x)dx = 0 {h(x; β) ≤ 1 − tx j , x j > 0}x j f (x)dx = Z X {h(x; β) ≤ 1, x j > 0}x j f (x)dx. [sent-411, score-0.258]

86 lim t↓0 and lim t↓0 Hence Z X Z X 1 ∆(t){x j > 0} f (x)dx = − {h(x; β) ≤ 1, x j > 0}x j f (x)dx. [sent-412, score-0.09]

87 Then,  if h(x; β) > 1 − tx j  0 1 − h(x; β) − tx j if 1 < h(x; β) ≤ 1 − tx j ∆(t) =  −tx j if h(x; β) ≤ 1. [sent-414, score-0.387]

88 Under the condition that β + = 0, we have ∂2 L(β) = H(β) jk , ∂β j ∂βk for 0 ≤ j, k ≤ d. [sent-421, score-0.119]

89 , xd dx−1 (12) ∂β0 |β1 | X−1 β1 and that for k = 1, 1 − h(x; β) + β1 x1 1 ∂Ψ(β) xk s =− , x2 , . [sent-442, score-0.178]

90 , xd dx−1 xk s |β1 | X−1 β1 Z = − Z = − Z Similarly, we have Z X−1 X1 X xk s(x)δ(h(x; β) − 1)dx1 dx−1 δ(1 − h(x; β))xk s(x)dx. [sent-461, score-0.223]

91 The popula+ tion minimizer (β∗ , β∗∗ ) is given by the minimizer of 0 i L(β0 , βi∗ ) = π+ Z X [1 − β0 − βi∗ xi∗ ]+ f (x)dx + π− Z X [1 + β0 + βi∗ xi∗ ]+ g(x)dx. [sent-485, score-0.156]

92  β0 > 1  π− (1 + β0 ), 1 + (π− − π+ )β0 , −1 ≤ β0 ≤ 1 L(β0 ) =  π+ (1 − β0 ), β0 < −1 with its minimum min L(β0 ) = 2 min (π+ , π− ) . [sent-487, score-0.082]

93 x i∗ ≥ βi∗ x i∗ ≤ Z X Let β0 denote the minimizer of L(β0 , βi∗ ) for a given βi∗ . [sent-489, score-0.078]

94    = A 1 u∗  β∗ zd + and β0 + β ∗ a z + z1 =(1−β∗ )/ β∗ + 0 2 = β0 + β ∗ + a1 (1 − β∗ )/ β∗ 0 + = β0 + a1 (1 − β∗ )/ β∗ + β∗ 0 + + 2 d + ∑ a jz j j=2 d ∑ a jz j. [sent-535, score-0.074]

95 β∗ d dz + β∗ d dz + KOO , L EE , K IM AND PARK + The last equality follows from the identity (11). [sent-537, score-0.092]

96 j j=2 j=2 Note that d ∑ a jm j j=2 2 + 2 β0 − a 1 β∗ / β ∗ + 0 d ∑ a j m j + β 0 − a 1 β∗ / 0 = 2 β∗ + j=2 d ∑ a jm j j=2 − β0 − a 1 β∗ / β ∗ + 0 2 and β0 + a1 (1 − β∗ )/ β∗ + 0 2 + β0 − a1 (1 + β∗ )/ β∗ + 0 2 2 − 2 β0 − a 1 β∗ / β ∗ + 0 = 2a2 / β∗ 2 . [sent-547, score-0.11]

97 Deﬁne D jk (α) = H(β∗ + α) jk − H(β∗ ) jk for 0 ≤ j, k ≤ d. [sent-581, score-0.357]

98 Since H(β) is continuous in β, there exists δ1 > 0 such that |D jk (α)| < ε1 if α < δ1 for any ε1 > 0 and all 0 ≤ j, k ≤ d. [sent-582, score-0.149]

99 2 2 √ It is because for sufﬁciently large n such that (t/ n)θ < δ1 , θ H(β) − H(β∗ ) θ ≤ ∑ |θ j ||θk | D jk j,k t √ θ n ≤ ε1 ∑ |θ j ||θk | ≤ 2ε1 θ 2 . [sent-584, score-0.119]

100 By Lemma 5, convexity of Λn , and the deﬁnition of ∆n , we have ε ε Λn (θ) + 1 − Λn (ηn ) ≥ Λn (θ∗ ) γ γ 1 1 ∗ (θ − ηn ) H(β∗ )(θ∗ − ηn ) − ηn H(β∗ )ηn − ∆n ≥ 2 2 C4 2 ≥ ε + Λn (ηn ) − 2∆n , 2 implying that C4 2 ε − 2∆n . [sent-607, score-0.076]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('bahadur', 0.383), ('dx', 0.341), ('achine', 0.219), ('koo', 0.208), ('ee', 0.201), ('radon', 0.201), ('asymptotic', 0.196), ('epresentation', 0.186), ('ector', 0.166), ('upport', 0.166), ('vol', 0.165), ('park', 0.157), ('fi', 0.147), ('svm', 0.145), ('mahalanobis', 0.139), ('xd', 0.133), ('im', 0.129), ('tx', 0.129), ('inear', 0.126), ('jk', 0.119), ('hyperplane', 0.111), ('cients', 0.1), ('coef', 0.096), ('korea', 0.093), ('vu', 0.093), ('nonseparable', 0.091), ('normality', 0.089), ('densities', 0.078), ('minimizer', 0.078), ('iy', 0.077), ('variability', 0.067), ('asymptotics', 0.066), ('standardized', 0.064), ('jm', 0.055), ('margins', 0.055), ('seoul', 0.055), ('variabilities', 0.055), ('normal', 0.052), ('separable', 0.052), ('ad', 0.052), ('lemma', 0.051), ('ag', 0.047), ('implying', 0.047), ('dz', 0.046), ('lim', 0.045), ('xk', 0.045), ('xi', 0.045), ('min', 0.041), ('pb', 0.038), ('quantiles', 0.038), ('rd', 0.038), ('risk', 0.037), ('changyi', 0.037), ('ishak', 0.037), ('jz', 0.037), ('ramm', 0.037), ('yuwon', 0.037), ('wn', 0.036), ('nominal', 0.035), ('lemmas', 0.035), ('boundary', 0.033), ('integrable', 0.033), ('intercept', 0.033), ('letting', 0.033), ('slope', 0.033), ('hinge', 0.032), ('transform', 0.031), ('ju', 0.031), ('yoonkyung', 0.031), ('median', 0.031), ('rates', 0.031), ('eu', 0.03), ('guyon', 0.03), ('continuous', 0.03), ('convexity', 0.029), ('support', 0.029), ('selection', 0.029), ('regularity', 0.028), ('representation', 0.028), ('barnhill', 0.028), ('bivariate', 0.028), ('cortes', 0.028), ('delta', 0.028), ('econometric', 0.028), ('replicates', 0.028), ('bayes', 0.027), ('li', 0.027), ('annals', 0.026), ('vapnik', 0.026), ('du', 0.026), ('elimination', 0.026), ('uniqueness', 0.026), ('dt', 0.026), ('falsely', 0.025), ('inferences', 0.025), ('op', 0.025), ('absolute', 0.025), ('vi', 0.025), ('estimated', 0.025), ('moments', 0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 1 jmlr-2008-A Bahadur Representation of the Linear Support Vector Machine

Author: Ja-Yong Koo, Yoonkyung Lee, Yuwon Kim, Changyi Park

2 0.10923748 11 jmlr-2008-Aggregation of SVM Classifiers Using Sobolev Spaces

Author: Sébastien Loustau

Abstract: This paper investigates statistical performances of Support Vector Machines (SVM) and considers the problem of adaptation to the margin parameter and to complexity. In particular we provide a classiﬁer with no tuning parameter. It is a combination of SVM classiﬁers. Our contribution is two-fold: (1) we propose learning rates for SVM using Sobolev spaces and build a numerically realizable aggregate that converges with same rate; (2) we present practical experiments of this method of aggregation for SVM using both Sobolev spaces and Gaussian kernels. Keywords: classiﬁcation, support vector machines, learning rates, approximation, aggregation of classiﬁers

3 0.094113864 32 jmlr-2008-Estimating the Confidence Interval for Prediction Errors of Support Vector Machine Classifiers

Author: Bo Jiang, Xuegong Zhang, Tianxi Cai

Abstract: Support vector machine (SVM) is one of the most popular and promising classiﬁcation algorithms. After a classiﬁcation rule is constructed via the SVM, it is essential to evaluate its prediction accuracy. In this paper, we develop procedures for obtaining both point and interval estimators for the prediction error. Under mild regularity conditions, we derive the consistency and asymptotic normality of the prediction error estimators for SVM with ﬁnite-dimensional kernels. A perturbationresampling procedure is proposed to obtain interval estimates for the prediction error in practice. With numerical studies on simulated data and a benchmark repository, we recommend the use of interval estimates centered at the cross-validated point estimates for the prediction error. Further applications of the proposed procedure in model evaluation and feature selection are illustrated with two examples. Keywords: k-fold cross-validation, model evaluation, perturbation-resampling, prediction errors, support vector machine

4 0.070674546 89 jmlr-2008-Support Vector Machinery for Infinite Ensemble Learning

Author: Hsuan-Tien Lin, Ling Li

Abstract: Ensemble learning algorithms such as boosting can achieve better performance by averaging over the predictions of some base hypotheses. Nevertheless, most existing algorithms are limited to combining only a ﬁnite number of hypotheses, and the generated ensemble is usually sparse. Thus, it is not clear whether we should construct an ensemble classiﬁer with a larger or even an inﬁnite number of hypotheses. In addition, constructing an inﬁnite ensemble itself is a challenging task. In this paper, we formulate an inﬁnite ensemble learning framework based on the support vector machine (SVM). The framework can output an inﬁnite and nonsparse ensemble through embedding inﬁnitely many hypotheses into an SVM kernel. We use the framework to derive two novel kernels, the stump kernel and the perceptron kernel. The stump kernel embodies inﬁnitely many decision stumps, and the perceptron kernel embodies inﬁnitely many perceptrons. We also show that the Laplacian radial basis function kernel embodies inﬁnitely many decision trees, and can thus be explained through inﬁnite ensemble learning. Experimental results show that SVM with these kernels is superior to boosting with the same base hypothesis set. In addition, SVM with the stump kernel or the perceptron kernel performs similarly to SVM with the Gaussian radial basis function kernel, but enjoys the beneﬁt of faster parameter selection. These properties make the novel kernels favorable choices in practice. Keywords: ensemble learning, boosting, support vector machine, kernel

5 0.06677904 3 jmlr-2008-A Moment Bound for Multi-hinge Classifiers

Author: Bernadetta Tarigan, Sara A. van de Geer

Abstract: The success of support vector machines in binary classiﬁcation relies on the fact that hinge loss employed in the risk minimization targets the Bayes rule. Recent research explores some extensions of this large margin based method to the multicategory case. We show a moment bound for the socalled multi-hinge loss minimizers based on two kinds of complexity constraints: entropy with bracketing and empirical entropy. Obtaining such a result based on the latter is harder than ﬁnding one based on the former. We obtain fast rates of convergence that adapt to the unknown margin. Keywords: multi-hinge classiﬁcation, all-at-once, moment bound, fast rate, entropy

6 0.064879484 70 jmlr-2008-On Relevant Dimensions in Kernel Feature Spaces

7 0.06474939 9 jmlr-2008-Active Learning by Spherical Subdivision

8 0.062650807 52 jmlr-2008-Learning from Multiple Sources

9 0.061541904 17 jmlr-2008-Automatic PCA Dimension Selection for High Dimensional Data and Small Sample Sizes

10 0.059377775 76 jmlr-2008-Optimization Techniques for Semi-Supervised Support Vector Machines

11 0.052586675 51 jmlr-2008-Learning Similarity with Operator-valued Large-margin Classifiers

12 0.051399872 83 jmlr-2008-Robust Submodular Observation Selection

13 0.051105909 15 jmlr-2008-An Information Criterion for Variable Selection in Support Vector Machines (Special Topic on Model Selection)

14 0.050810389 29 jmlr-2008-Cross-Validation Optimization for Large Scale Structured Classification Kernel Methods

15 0.046860103 73 jmlr-2008-On the Suitable Domain for SVM Training in Image Coding

16 0.046161838 16 jmlr-2008-Approximations for Binary Gaussian Process Classification

17 0.045295712 63 jmlr-2008-Model Selection for Regression with Continuous Kernel Functions Using the Modulus of Continuity (Special Topic on Model Selection)

18 0.04466182 54 jmlr-2008-Learning to Select Features using their Properties

19 0.044230133 58 jmlr-2008-Max-margin Classification of Data with Absent Features

20 0.041988019 86 jmlr-2008-SimpleMKL

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.213), (1, -0.096), (2, 0.005), (3, -0.044), (4, 0.142), (5, -0.034), (6, 0.045), (7, -0.021), (8, 0.132), (9, -0.01), (10, 0.067), (11, -0.074), (12, 0.055), (13, -0.055), (14, 0.018), (15, -0.04), (16, 0.011), (17, -0.059), (18, 0.098), (19, 0.208), (20, -0.078), (21, 0.18), (22, -0.098), (23, -0.03), (24, -0.049), (25, -0.117), (26, 0.2), (27, 0.181), (28, -0.109), (29, -0.236), (30, -0.092), (31, 0.212), (32, 0.099), (33, 0.116), (34, 0.083), (35, 0.04), (36, 0.082), (37, -0.004), (38, -0.144), (39, -0.147), (40, -0.067), (41, -0.065), (42, 0.057), (43, 0.116), (44, 0.031), (45, 0.169), (46, 0.063), (47, -0.171), (48, -0.025), (49, -0.041)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9535594 1 jmlr-2008-A Bahadur Representation of the Linear Support Vector Machine

Author: Ja-Yong Koo, Yoonkyung Lee, Yuwon Kim, Changyi Park

2 0.51234293 32 jmlr-2008-Estimating the Confidence Interval for Prediction Errors of Support Vector Machine Classifiers

Author: Bo Jiang, Xuegong Zhang, Tianxi Cai

3 0.39949563 11 jmlr-2008-Aggregation of SVM Classifiers Using Sobolev Spaces

Author: Sébastien Loustau

4 0.35306484 76 jmlr-2008-Optimization Techniques for Semi-Supervised Support Vector Machines

Author: Olivier Chapelle, Vikas Sindhwani, Sathiya S. Keerthi

Abstract: Due to its wide applicability, the problem of semi-supervised classiﬁcation is attracting increasing attention in machine learning. Semi-Supervised Support Vector Machines (S 3 VMs) are based on applying the margin maximization principle to both labeled and unlabeled examples. Unlike SVMs, their formulation leads to a non-convex optimization problem. A suite of algorithms have recently been proposed for solving S3 VMs. This paper reviews key ideas in this literature. The performance and behavior of various S3 VM algorithms is studied together, under a common experimental setting. Keywords: semi-supervised learning, support vector machines, non-convex optimization, transductive learning

5 0.340572 73 jmlr-2008-On the Suitable Domain for SVM Training in Image Coding

Author: Gustavo Camps-Valls, Juan Gutiérrez, Gabriel Gómez-Pérez, Jesús Malo

Abstract: Conventional SVM-based image coding methods are founded on independently restricting the distortion in every image coefﬁcient at some particular image representation. Geometrically, this implies allowing arbitrary signal distortions in an n-dimensional rectangle deﬁned by the ε-insensitivity zone in each dimension of the selected image representation domain. Unfortunately, not every image representation domain is well-suited for such a simple, scalar-wise, approach because statistical and/or perceptual interactions between the coefﬁcients may exist. These interactions imply that scalar approaches may induce distortions that do not follow the image statistics and/or are perceptually annoying. Taking into account these relations would imply using non-rectangular εinsensitivity regions (allowing coupled distortions in different coefﬁcients), which is beyond the conventional SVM formulation. In this paper, we report a condition on the suitable domain for developing efﬁcient SVM image coding schemes. We analytically demonstrate that no linear domain fulﬁlls this condition because of the statistical and perceptual inter-coefﬁcient relations that exist in these domains. This theoretical result is experimentally conﬁrmed by comparing SVM learning in previously reported linear domains and in a recently proposed non-linear perceptual domain that simultaneously reduces the statistical and perceptual relations (so it is closer to fulﬁlling the proposed condition). These results highlight the relevance of an appropriate choice of the image representation before SVM learning. Keywords: image coding, non-linear perception models, statistical independence, support vector machines, insensitivity zone c 2008 Gustavo Camps-Valls, Juan Guti´ rrez, Gabriel G´ mez-P´ rez and Jes´ s Malo. e o e u ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO 1. Problem Statement: The Diagonal Jacobian Condition Image coding schemes based on support vector machines (SVM) have been successfully introduced in the literature. SVMs have been used in the spatial domain (Robinson and Kecman, 2000), in the block-DCT domain (Robinson and Kecman, 2003), and in the wavelet domain (Ahmed, 2005; Jiao et al., 2005). These coding methods take advantage of the ability of the support vector regression (SVR) algorithm for function approximation using a small number of parameters (signal samples, or ¨ support vectors) (Smola and Scholkopf, 2004). In all current SVM-based image coding techniques, a representation of the image is described by the entropy-coded weights associated to the support vectors necessary to approximate the signal with a given accuracy. Relaxing the accuracy bounds reduces the number of needed support vectors. In a given representation domain, reducing the number of support vectors increases the compression ratio at the expense of bigger distortion (lower image quality). By applying the standard SVR formulation, a certain amount of distortion in each sample of the image representation is allowed. In the original formulation, scalar restrictions on the errors are introduced using a constant ε-insensitivity value for every sample. ´ Recently, this procedure has been reﬁned by Gomez-P´ rez et al. (2005) using a proﬁle-dependent e SVR (Camps-Valls et al., 2001) that considers a different ε for each sample or frequency. This frequency-dependent insensitivity, ε f , accounts for the fact that, according to simple (linear) perception models, not every sample in linear frequency domains (such as DCT or wavelets) contributes to the perceived distortion in the same way. Despite different domains have been proposed for SVM training (spatial domain, block-DCT and wavelets) and different ε insensitivities per sample have been proposed, in conventional SVR formulation, the particular distortions introduced by regression in the different samples are not coupled. In all the reported SVM-based image coding schemes, the RBF kernel is used and the penalization parameter is ﬁxed to an arbitrarily large value. In this setting, considering n-sample signals as n-dimensional vectors, the SVR guarantees that the approximated vectors are conﬁned in n-dimensional rectangles around the original vectors. These rectangles are just n-dimensional cubes in the standard formulation or they have certain elongation if different ε f are considered in each axis, f . Therefore, in all the reported SVM-based coding methods, these rectangles are always oriented along the axes of the (linear) image representation. According to this, a common feature of these (scalar-wise) approaches is that they give rise to decoupled distortions in each dimension. P´ rez-Cruz et al. (2002) proposed a hyperspherical insensitivity zone to correct the penalization e factor in each dimension of multi-output regression problems, but again, restrictions to each sample were still uncoupled. This scalar-wise strategy is not the best option in domains where the different dimensions of the image representation are not independent. For instance, consider the situation where actually independent components, r f , are obtained from a given image representation, y, applying some eventually non-linear transform, R: R y −→ r. In this case, SVM regression with scalar-wise error restriction makes sense in the r domain. However, the original y domain will not be suitable for the standard SVM regression unless the matrix ∇R is diagonal (up to any permutation of the dimensions, that is, only one non-zero element per row). Therefore, if transforms that achieve independence have non-diagonal Jacobian, scalar-wise restrictions in the original (coupled coefﬁcients) domain y are not allowed. 50 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING y2 1 −0,5 −0,5 0,4 R= r2 y1 r1 R−1 = 0,83 −0,83 0,67 −1,67 Figure 1: Insensitivity regions in different representation domains, y (left) and r (right), related by a non-diagonal transform ∇R and its inverse ∇R−1 . Figure 1 illustrates this situation. The shaded region in the right plot (r domain) represents the n-dimensional box determined by the ε f insensitivities in each dimension ( f =1,2), in which a scalar-wise approach is appropriate due to independence among signal coefﬁcients. Given that the particular ∇R transform is not diagonal, the corresponding shaded region in the left plot (the original y domain) is not aligned along the axes of the representation. This has negative implications: note that for the highlighted points, smaller distortions in both dimensions in the y domain (as implied by SVM with tighter but scalar ε f insensitivities) do not necessarily imply lying inside the insensitivity region in the ﬁnal truly independent (and meaningful) r domain. Therefore, the original y domain is not suitable for the direct application of conventional SVM, and consequently, non-trivial coupled insensitivity regions are required. Summarizing, in the image coding context, the condition for an image representation y to be strictly suitable for conventional SVM learning is that the transform that maps the original representation y to an independent coefﬁcient representation r must be locally diagonal. As will be reviewed below, independence among coefﬁcients (and the transforms to obtain them) may be deﬁned in both statistical and perceptual terms (Hyvarinen et al., 2001; Malo et al., 2001; Epifanio et al., 2003; Malo et al., 2006). On the one hand, a locally diagonal relation to a statistically independent representation is desirable because independently induced distortions (as the conventional SVM approach does) will preserve the statistics of the distorted signal, that is, it will not introduce artiﬁcial-looking artifacts. On the other hand, a locally diagonal relation to a perceptually 51 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO independent representation is desirable because independently induced distortions do not give rise to increased subjective distortions due to non-trivial masking or facilitation interactions between the distortions in each dimension (Watson and Solomon, 1997). In this work, we show that conventional linear domains do not fulﬁll the diagonal Jacobian condition in either the statistical case or in the perceptual case. This theoretical result is experimentally conﬁrmed by comparing SVM learning in previously reported linear domains (Robinson and Kecman, 2003; G´ mez-P´ rez et al., 2005) and in a recently proposed non-linear perceptual domain o e that simultaneously reduces the statistical and the perceptual relations (Malo et al., 2006), thus, this non-linear perceptual domain is closer to fulﬁlling the proposed condition. The rest of the paper is structured as follows. Section 2 reviews the fact that linear coefﬁcients of the image representations commonly used for SVM training are neither statistically independent nor perceptually independent. Section 3 shows that transforms for obtaining statistical and/or perceptual independence from linear domains have non-diagonal Jacobian. This suggests that there is room to improve the performance of conventional SVM learning reported in linear domains. In Section 4, we propose the use of a perceptual representation for SVM training because it strictly fulﬁlls the diagonal Jacobian condition in the perceptual sense and increases the statistical independence among coefﬁcients, bringing it closer to fulﬁlling the condition in the statistical sense. The experimental image coding results conﬁrm the superiority of this domain for SVM training in Section 5. Section 6 presents the conclusions and ﬁnal remarks. 2. Statistical and Perceptual Relations Among Image Coefﬁcients Statistical independence among the coefﬁcients of a signal representation refers to the fact that the joint PDF of the class of signals to be considered can be expressed as a product of the marginal PDFs in each dimension (Hyvarinen et al., 2001). Simple (second-order) descriptions of statistical dependence use the non-diagonal nature of the covariance matrix (Clarke, 1985; Gersho and Gray, 1992). More recent and accurate descriptions use higher-order moments, mutual information, or the non-Gaussian nature (sparsity) of marginal PDFs (Hyvarinen et al., 2001; Simoncelli, 1997). Perceptual independence refers to the fact that the visibility of errors in coefﬁcients of an image may depend on the energy of neighboring coefﬁcients, a phenomenon known in the perceptual literature as masking or facilitation (Watson and Solomon, 1997). Perceptual dependence has been formalized just up to second order, and this may be described by the non-Euclidean nature of the perceptual metric matrix (Malo et al., 2001; Epifanio et al., 2003; Malo et al., 2006). 2.1 Statistical Relations In recent years, a variety of approaches, known collectively as “independent component analysis” (ICA), have been developed to exploit higher-order statistics for the purpose of achieving a unique linear solution for coefﬁcient independence (Hyvarinen et al., 2001). The basis functions obtained when these methods are applied to images are spatially localized and selective for both orientation and spatial frequency (Olshausen and Field, 1996; Bell and Sejnowski, 1997). Thus, they are similar to basis functions of multi-scale wavelet representations. Despite its name, linear ICA does not actually produce statistically independent coefﬁcients when applied to photographic images. Intuitively, independence would seem unlikely, since images are not formed from linear superpositions of independent patterns: the typical combination rule for the elements of an image is occlusion. Empirically, the coefﬁcients of natural image decom52 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING | f | = 10.8 cpd | f | = 24.4 cpd −20 −10 −10 fy (cpd) −30 −20 fy (cpd) −30 0 0 10 10 20 20 30 30 −30 −20 −10 0 f (cpd) 10 20 30 −30 x −20 −10 0 f (cpd) 10 20 30 x Figure 2: Statistical interaction of two particular coefﬁcients of the local Fourier Transform with their neighbors in a natural image database. The absolute value of the frequency of these coefﬁcients is | f | = 10.8 and | f | = 24.4 cycles/degree (cpd). positions in spatially localized oscillating basis functions are found to be fairly well decorrelated (i.e., their covariance is almost zero). However, the amplitudes of coefﬁcients at nearby spatial positions, orientations, and scales are highly correlated (even with orthonormal transforms) (Simoncelli, ´ 1997; Buccigrossi and Simoncelli, 1999; Wainwright et al., 2001; Hyvarinen et al., 2003; Guti errez et al., 2006; Malo et al., 2006; Malo and Guti´ rrez, 2006). This suggests that achieving statistical e independence requires the introduction of non-linearities beyond linear ICA transforms. Figure 2 reproduces one of many results that highlight the presence of statistical relations of natural image coefﬁcients in block PCA or linear ICA-like domains: the energy of spatially localized oscillating ﬁlters is correlated with the energy of neighboring ﬁlters in scale and orientation (see Guti´ rrez et al., 2006). A remarkable feature is that the interaction width increases with frequency, e as has been reported in other domains, for example, wavelets (Buccigrossi and Simoncelli, 1999; Wainwright et al., 2001; Hyvarinen et al., 2003), and block-DCT (Malo et al., 2006). In order to remove the remaining statistical relations in the linear domains y, non-linear ICA methods are necessary (Hyvarinen et al., 2001; Lin, 1999; Karhunen et al., 2000; Jutten and Karhunen, 2003). Without lack of generality, non-linear ICA transforms can be schematically understood as a two-stage process (Malo and Guti´ rrez, 2006): e T R (( y hh x hh (( r, (1) R−1 T−1 where x is the image representation in the spatial domain, and T is a global unitary linear transform that removes second-order and eventually higher-order relations among coefﬁcients in the spatial domain. Particular examples of T include block PCA, linear ICAs, DCT or wavelets. In the ICA literature notation, T is the separating matrix and T−1 is the mixing matrix. The second transform 53 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO R is an additional non-linearity that is introduced in order to remove the statistical relations that still remain in the y domain. 2.2 Perceptual Relations Perceptual dependence among coefﬁcients in different image representations can be understood by using the current model of V1 cortex. This model can also be summarized by the two-stage (linear and non-linear) process described in Equation (1). In this perceptual case, T is also a linear ﬁlter bank applied to the original input image in the spatial domain. This ﬁlter bank represents the linear behavior of V1 neurons whose receptive ﬁelds happen to be similar to wavelets or linear ICA basis functions (Olshausen and Field, 1996; Bell and Sejnowski, 1997). The second transform, R, is a non-linear function that accounts for the masking and facilitation phenomena that have been reported in the linear y domain (Foley, 1994; Watson and Solomon, 1997). Section 3.2 gives a parametric expression for the second non-linear stage, R: the divisive normalization model (Heeger, 1992; Foley, 1994; Watson and Solomon, 1997). This class of models is based on psychophysical experiments assuming that the last domain, r, is perceptually Euclidean (i.e., perfect perceptual independence). An additional conﬁrmation of this assumption is the success of (Euclidean) subjective image distortion measures deﬁned in that domain (Teo and Heeger, 1994). Straightforward application of Riemannian geometry to obtain the perceptual metric matrix in other domains shows that the coefﬁcients of linear domains x and y, or any other linear transform of them, are not perceptually independent (Epifanio et al., 2003). Figure 3 illustrates the presence of perceptual relations between coefﬁcients when using linear block frequency or wavelet-like domains, y: the cross-masking behavior. In this example, the visibility of the distortions added on top of the background image made of periodic patterns has to be assessed. This is a measure of the sensitivity of a particular perceptual mechanism to distortions in that dimension, ∆y f , when mechanisms tuned to other dimensions are simultaneously active, that is, y f = 0, with f = f . As can be observed, low frequency noise is more visible in high frequency backgrounds than in low frequency backgrounds (e.g., left image). Similarly, high frequency noise is more visible in low frequency backgrounds than in high frequency ones (e.g., right image). That is to say, a signal of a speciﬁc frequency strongly masks the corresponding frequency analyzer, but it induces a smaller sensitivity reduction in the analyzers that are tuned to different frequencies. In other words, the reduction in sensitivity of a speciﬁc analyzer gets larger as the distance between the background frequency and the frequency of the analyzer gets smaller. The response of each frequency analyzer not only depends on the energy of the signal for that frequency band, but also on the energy of the signal in other frequency bands (cross-masking). This implies that a different amount of noise in each frequency band may be acceptable depending on the energy of that frequency band and on the energy of neighboring bands. This is what we have called perceptual dependence among different coefﬁcients in the y domain. At this point, it is important to stress the similarity between the set of computations to obtain statistically decoupled image coefﬁcients and the known stages of biological vision. In fact, it has been hypothesized that biological visual systems have organized their sensors to exploit the particular statistics of the signals they have to process. See Barlow (2001), Simoncelli and Olshausen (2001), and Simoncelli (2003) for reviews on this hypothesis. In particular, both the linear and the non-linear stages of the cortical processing have been successfully derived using redundancy reduction arguments: nowadays, the same class of linear 54 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING 3 cpd 6 cpd 12 cpd 24 cpd Figure 3: Illustrative example of perceptual dependence (cross-masking phenomenon). Equal energy noise of different frequency content, 3 cycl/deg (cpd), 6 cpd, 12 cpd and 24 cpd, shown on top of a background image. Sampling frequency assumes that these images subtend an angle of 3 deg. stage T is used in transform coding algorithms and in vision models (Olshausen and Field, 1996; Bell and Sejnowski, 1997; Taubman and Marcellin, 2001), and new evidence supports the same idea for the second non-linear stage (Schwartz and Simoncelli, 2001; Malo and Guti´ rrez, 2006). e According to this, the statistical and perceptual transforms, R, that remove the above relations from the linear domains, y, would be very similar if not the same. 3. Statistical and Perceptual Independence Imply Non-diagonal Jacobian In this section, we show that both statistical redundancy reduction transforms (e.g., non-linear ICA) and perceptual independence transforms (e.g., divisive normalization), have non-diagonal Jacobian for any linear image representation, so they are not strictly suitable for conventional SVM training. 3.1 Non-diagonal Jacobian in Non-linear ICA Transforms One possible approach for dealing with global non-linear ICA is to act differentially by breaking the problem into local linear pieces that can then be integrated to obtain the global independent coefﬁcient domain (Malo and Guti´ rrez, 2006). Each differential sub-problem around a particular e point (image) can be locally solved using the standard linear ICA methods restricted to the neighbors of that point (Lin, 1999). Using the differential approach in the context of a two-stage process such as the one in Equation (1), it can be shown that (Malo and Guti´ rrez, 2006): e r = r0 + Z x x0 T (x ) dx = r0 + Z x x0 ∇R(Tx ) T dx , (2) where T (x ) is the local separating matrix for a neighborhood of the image x , and T is the global separating matrix for the whole PDF. Therefore, the Jacobian of the second non-linear stage is: ∇R(y) = ∇R(Tx) = T (x) T−1 . 55 (3) ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO As local linear independent features around a particular image, x, differ in general from global linear independent features, that is, T (x) = T, the above product is not the identity nor diagonal in general. 3.2 Non-diagonal Jacobian in Non-linear Perceptual Transforms The current response model for the cortical frequency analyzers is non-linear (Heeger, 1992; Watson and Solomon, 1997). The outputs of the ﬁlters of the ﬁrst linear stage, y, undergo a non-linear sigmoid transform in which the energy of each linear coefﬁcient is weighted by a linear Contrast Sensitivity Function (CSF) (Campbell and Robson, 1968; Malo et al., 1997) and is further normalized by a combination of the energies of neighbor coefﬁcients in frequency, r f = R(y) f = sgn(y f ) |α f y f |γ , β f + ∑n =1 h f f |α f y f |γ f (4) where α f (Figure 4[top left]) are CSF-like weights, β f (Figure 4[top right]) control the sharpness of the response saturation for each coefﬁcient, γ is the so called excitation exponent, and the matrix h f f determines the interaction neighborhood in the non-linear normalization of the energy. This interaction matrix models the cross-masking behavior (cf. Section 2.2). The interaction in this matrix is assumed to be Gaussian (Watson and Solomon, 1997), and its width increases with the frequency. Figure 4[bottom] shows two examples of this Gaussian interaction for two particular coefﬁcients in a local Fourier domain. Note that the width of the perceptual interaction neighborhood increases with the frequency in the same way as the width of the statistical interaction neighborhood shown in Figure 2. We used a value of γ = 2 in the experiments. Taking derivatives in the general divisive normalization model, Equation (4), we obtain ∇R(y) f f = sgn(y f )γ α f |α f y f |γ |α f y f |γ−1 α f |α f y f |γ−1 δf f − hf f β f + ∑n =1 h f f |α f y f |γ (β f + ∑n =1 h f f |α f y f |γ )2 f f , (5) which is not diagonal because of the interaction matrix, h, which describes the cross-masking between each frequency f and the remaining f = f . Note that the intrinsic non-linear nature of both the statistical and perceptual transforms, Equations (3) and (5), makes the above results true for any linear domain under consideration. Speciﬁcally, if any other possible linear domain for image representation is considered, y = T y, then the Jacobian of the corresponding independence transform, R , is ∇R (y ) = ∇R(y) T −1 , which, in general, will also be non-diagonal because of the non-diagonal and point-dependent nature of ∇R(y). To summarize, since no linear domain fulﬁlls the diagonal Jacobian condition in either statistical or perceptual terms, the negative situation illustrated in Figure 1 may occur when using SVM in these domains. Therefore, improved results could be obtained if SVM learning were applied after some transform achieving independent coefﬁcients, R. 4. SVM Learning in a Perceptually Independent Representation In order to conﬁrm the above theoretical results (i.e., the unsuitability of linear representation domains for SVM learning) and to assess the eventual gain that can be obtained from training SVR 56 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING 0.04 αf 0.015 βf 0.03 0.012 0.02 0.009 0.006 0.01 0.003 0 0 4 8 12 16 20 24 28 32 0 f (frequency cycles/degree) 4 8 | f | = 10.8 cpd 16 20 24 28 32 | f | = 24.4 cpd −30 −20 −20 −10 −10 f (cpd) −30 0 y 0 y f (cpd) 12 f (frequency cycles/degree) 10 10 20 20 30 −30 −20 −10 0 fx (cpd) 10 20 30 −30 30 −20 −10 0 fx (cpd) 10 20 30 Figure 4: Parameters of the perceptual model: α f (top left), β f (top right). Bottom ﬁgures represent perceptual interaction neighborhoods h f f of two particular coefﬁcients of the local Fourier domain. in a more appropriate domain, we should compare the performance of SVRs in previously reported linear domains (e.g., block-DCT or wavelets) and in one of the proposed non-linear domains (either the statistically independent domain or the perceptually independent domain). Exploration of the statistical independence transform may have academic interest but, in its present formulation, it is not practical for coding purposes: direct application of non-linear ICA as in Equation (2) is very time-consuming for high dimensional vectors since lots of local ICA computations are needed to transform each block, and a very large image database is needed for a robust and signiﬁcant computation of R. Besides, an equally expensive differential approach is also needed to compute the inverse R−1 for image decoding. In contrast, the perceptual non-linearity (and its inverse) are analytical. These analytical expressions are feasible for reasonable block sizes, and there are efﬁcient iterative methods that can be used for larger vectors (Malo et al., 2006). In this paper, we explore the use of a psychophysically-based divisive normalized domain: ﬁrst compute a block-DCT transform and then apply the divisive normalization model described above for each block. The results will be compared to the ﬁrst competitive SVM coding results (Robinson 57 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO ´ and Kecman, 2003) and the posterior improvements reported by G omez-P´ rez et al. (2005), both e formulated in the linear block-DCT domain. As stated in Section 2, by construction, the proposed domain is perceptually Euclidean with perceptually independent components. The Euclidean nature of this domain has an additional beneﬁt: the ε-insensitivity design is very simple because a constant value is appropriate due to the constant perceptual relevance of all coefﬁcients. Thus, direct application of the standard SVR method is theoretically appropriate in this domain. Moreover, beyond its built-in perceptual beneﬁts, this psychophysically-based divisive normalization has attractive statistical properties: it strongly reduces the mutual information between the ﬁnal coefﬁcients r (Malo et al., 2006). This is not surprising according to the hypothesis that try to explain the early stages of biological vision systems using information theory arguments (Barlow, 1961; Simoncelli and Olshausen, 2001). Speciﬁcally, dividing the energy of each linear coefﬁcient by the energy of the neighbors, which are statistically related with it, cf. Figure 2, gives coefﬁcients with reduced statistical dependence. Moreover, as the empirical non-linearities of perception have been reproduced using non-linear ICA in Equation (2) (Malo and Guti´ rrez, 2006), the empirical die visive normalization can be seen as a convenient parametric way to obtain statistical independence. 5. Performance of SVM Learning in Different Domains In this section, we analyze the performance of SVM-based coding algorithms in linear and nonlinear domains through rate-distortion curves and explicit examples for visual comparison. In addition, we discuss how SVM selects support vectors in these domains to represent the image features. 5.1 Model Development and Experimental Setup In the (linear) block-DCT domain, y, we use the method introduced by Robinson and Kecman (2003) (RKi-1), in which the SVR is trained to learn a ﬁxed (low-pass) number of DCT coefﬁcients ´ (those with frequency bigger than 20 cycl/deg are discarded); and the method proposed by G omezP´ rez et al. (2005) (CSF-SVR), in which the relevance of all DCT coefﬁcients is weighted according e to the CSF criterion using an appropriately modulated ε f . In the non-linear domain, r, we use the SVR with constant insensitivity parameter ε (NL-SVR). In all cases, the block-size is 16×16, that is, y, r ∈ R256 . The behavior of JPEG standard is also included in the experiments for comparison purposes. As stated in Section 1, we used the RBF kernel and arbitrarily large penalization parameter in every SVR case. In all experiments, we trained the SVR models without the bias term, and modelled the absolute value of the DCT, y, or response coefﬁcients, r. All the remaining free parameters (ε-insensitivity and Gaussian width of the RBF kernel σ) were optimized for all the considered models and different compression ratios. In the NL-SVM case, the parameters of the divisive normalization used in the experiments are shown in Figure 4. After training, the signal is described by the uniformly quantized Lagrange multipliers of the support vectors needed to keep the regression error below the thresholds ε f . The last step is entropy coding of the quantized weights. The compression ratio is controlled by a factor applied to the thresholds, ε f . 58 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING 5.2 Model Comparison In order to assess the quality of the coded images, three different measures were used: the standard ´ (Euclidean) RMSE, the Maximum Perceptual Error (MPE) (Malo et al., 2000; G omez-P´ rez et al., e 2005; Malo et al., 2006) and the also perceptually meaningful Structural SIMilarity (SSIM) index (Wang et al., 2004). Eight standard 256×256 monochrome 8 bits/pix images were used in the experiments. Average rate-distortion curves are plotted in Figure 5 in the range [0.05, 0.6] bits/pix (bpp). According to these entropy-per-sample data, original ﬁle size was 64 KBytes in every case, while the compressed image sizes were in the range [0.4, 4.8] KBytes. This implies that the compression ratios were in the range [160:1, 13:1]. In general, a clear gain over standard JPEG is obtained by all SVM-based methods. According to the standard Euclidean MSE point of view, the performance of RKi-1 and CSF-SVR algorithms is basically the same (note the overlapped curves in Figure 5(a)). However, it is widely known that the MSE results are not useful to represent the subjective quality of images, as extensively reported elsewhere (Girod, 1993; Teo and Heeger, 1994; Watson and Malo, 2002). When using more appropriate (perceptually meaningful) quality measures (Figures 5(b)-(c)), the CSF-SVR obtains a certain advantage over the RKi-1 algorithm for all compression rates, which was already reported by G´ mez-P´ rez et al. (2005). In all measures, and for the whole considered entropy range, the o e proposed NL-SVR clearly outperforms all previously reported methods, obtaining a noticeable gain at medium-to-high compression ratios (between 0.1 bpp (80:1) and 0.3 bpp (27:1)). Taking into account that the recommended bit rate for JPEG is about 0.5 bpp, from Figure 5 we can also conclude that the proposed technique achieves the similar quality levels at a lower bit rate in the range [0.15, 0.3] bpp. Figure 6 shows representative visual results of the considered SVM strategies on standard images (Lena and Barbara) at the same bit rate (0.3 bpp, 27:1 compression ratio or 2.4 KBytes in 256×256 images). The visual inspection conﬁrms that the numerical gain in MPE and SSIM shown in Figure 5 is also perceptually signiﬁcant. Some conclusions can be extracted from this ﬁgure. ´ First, as previously reported by Gomez-P´ rez et al. (2005), RKi-1 leads to poorer (blocky) results e because of the crude approximation of the CSF (as an ideal low-pass ﬁlter) and the equal relevance applied to the low-frequency DCT-coefﬁcients. Second, despite the good performance yielded by the CSF-SVR approach to avoid blocking effects, it is worth noting that high frequency details are smoothed (e.g., see Barbara’s scarf). These effects are highly alleviated by introducing SVR in the non-linear domain. See, for instance, Lena’s eyes, her hat’s feathers or the better reproduction of the high frequency pattern in Barbara’s clothes. Figure 7 shows the results obtained by all considered methods at a very high compression ratio for the Barbara image (0.05 bpp, 160:1 compression ratio or 0.4 KBytes in 256×256 images). This experiment is just intended to show the limits of methods performance since it is out of the recommended rate ranges. Even though this scenario is unrealistic, differences among methods are still noticeable: the proposed NL-SVR method reduces the blocky effects (note for instance that the face is better reproduced). This is due to a better distribution of support vectors in the perceptually independent domain. 5.3 Support Vector Distribution The observed different perceptual image quality obtained with each approach is a direct consequence of support vector distribution in different domains. Figure 8 shows a representative example 59 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO 20 JPEG RKi−1 CSF−SVR NL−SVR 18 RMSE 16 14 12 10 8 0.1 0.2 0.3 0.4 Entropy (bits/pix) 0.5 0.6 22 JPEG RKi−1 CSF−SVR NL−SVR 20 18 16 MPE 14 12 10 8 6 4 0.1 0.2 0.3 0.4 Entropy (bits/pix) 0.5 0.6 0.85 0.8 SSIM 0.75 0.7 0.65 JPEG 0.6 RKi−1 CSF−SVR 0.55 NL−SVR 0.5 0.1 0.2 0.3 0.4 Entropy (bits/pix) 0.5 0.6 Figure 5: Average rate distortion curves over eight standard images (Lena, Barbara, Boats, Einstein, Peppers, Mandrill, Goldhill, Camera man) using objective and subjective measures for the considered JPEG (dotted) and the SVM approaches (RKi-1 dash-dotted, CSF-SVR dashed and NL-SVR solid). RMSE distortion (top), Maximum Perceptual Error, MPE (middle) (Malo et al., 2000; G´ mez-P´ rez et al., 2005; Malo et al., 2006), and Structural o e SIMilarity index, SSIM (bottom) (Wang et al., 2004). 60 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING Rki Rki SVR+CSF SVR+CSF NL+SVR NL+SVR Figure 6: Examples of decoded Lena (left) and Barbara (right) images at 0.3 bits/pix. From top to bottom: JPEG, RKi-1, CSF-SVR, and NL-SVR. 61 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO (a) (b) (c) (d) Figure 7: Examples of decoded Barbara images at a high compression ratio of 0.05 bits/pix (160:1) for (a) JPEG, (b) RKi-1, (c) CSF-SVR, and (d) NL-SVR. of the distribution of the selected support vectors by the RKi-1 and the CSF-SVR models working in the linear DCT domain, and the NL-SVM working in the perceptually independent non-linear domain r. Speciﬁcally, a block of Barbara’s scarf at different compression ratios is used for illustration purposes. The RKi-1 approach (Robinson and Kecman, 2003) uses a constant ε but, in order to consider the low subjective relevance of the high-frequency region, the corresponding coefﬁcients are neglected. As a result, this approach only allocates support vectors in the low/medium frequency regions. The CSF-SVR approach uses a variable ε according to the CSF and gives rise to a more natural concentration of support vectors in the low/medium frequency region, which captures medium to high frequency details at lower compression rates (0.5 bits/pix). Note that the number of support vectors is bigger than in the RKi-1 approach, but it selects some necessary high-frequency coefﬁcients to keep the error below the selected threshold. However, for bigger compression ratios (0.3 bits/pix), it misrepresents some high frequency, yet relevant, features (e.g., the peak from the stripes). The NL-SVM approach works in the non-linear transform domain, in which a more uniform coverage 62 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING (a) (b) (c) 0 200 10 100 0 200 5 5 15 0 0 20 30 25 20 10 20 30 fy (cpd) 10 0 fy (cpd) 30 10 fx (cpd) 0 200 5 10 100 0 200 5 10 100 15 25 10 30 20 30 f (cpd) y 10 0 30 10 0.5 20 30 25 20 5 1 0 0 20 30 0 1.5 15 15 0 fy (cpd) 30 0 fx (cpd) 20 25 20 0 fx (cpd) fx (cpd) 20 30 25 20 30 10 0.5 15 0 5 1 10 100 15 0 1.5 25 20 f (cpd) y 10 30 fy (cpd) 0 0 fx (cpd) fx (cpd) Figure 8: Signal in different domains and the selected support vectors by the SVM models in a block of the Barbara image at 0.3 bits/pix (top row) and 0.5 bits/pix (bottom row). Different domains are analyzed: (a) linear DCT using RKi-1, (b) linear DCT with CSF-SVM, and (c) non-linear perceptual domain with standard ε-SVM (NL-SVR). of the domain is done, accounting for richer (and perceptually independent) coefﬁcients to perform efﬁcient sparse signal reconstruction. It is important to remark that, for a given method (or domain), tightening ε f implies (1) considering more support vectors, and (2) an increase in entropy (top and bottom rows in Figure 8, 0.3 bpp to 0.5 bpp). However, note that the relevant measure is the entropy and not the number of support vectors: even though the number of selected support vectors in the r domain is higher, their variance is lower, thus giving rise to the same entropy after entropy coding. 6. Conclusions In this paper, we have reported a condition on the suitable domain for developing efﬁcient SVM image coding schemes. The so-called diagonal Jacobian condition states that SVM regression with scalar-wise error restriction in a particular domain makes sense only if the transform that maps this domain to an independent coefﬁcient representation is locally diagonal. We have demonstrated that, 63 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO in general, linear domains do not fulﬁll this condition because non-trivial statistical and perceptual inter-coefﬁcient relations do exist in these domains. This theoretical ﬁnding has been experimentally conﬁrmed by observing that improved compression results are obtained when SVM is applied in a non-linear perceptual domain that starts from the same linear domain used by previously reported SVM-based image coding schemes. These results highlight the relevance of an appropriate image representation choice before SVM learning. Further work is tied to the use of SVM-based coding schemes in statistically, rather than perceptually, independent non-linear ICA domains. In order to do so, local PCA instead of local ICA may be used in the local-to-global differential approach (Malo and Guti´ rrez, 2006) to speed up the e non-linear computation. Acknowledgments This work has been partly supported by the Spanish Ministry of Education and Science under grant CICYT TEC2006-13845/TCM and by the Generalitat Valenciana under grant GV-06/215. References R. Ahmed. Wavelet-based image compression using SVM learning and encoding techniques. Proc. 8th IASTED International Conference Computer Graphics and Imaging, 1:162–166, 2005. H. B. Barlow. Redundancy reduction revisited. Network: Comp. Neur. Sys., 12:241–253, 2001. H. B. Barlow. Possible principles underlying the transformation of sensory messages. In WA Rosenblith, editor, Sensory Communication, pages 217–234. MIT Press, Cambridge, MA, 1961. A. J. Bell and T. J. Sejnowski. The ‘independent components’ of natural scenes are edge ﬁlters. Vision Research, 37(23):3327–3338, 1997. R. W. Buccigrossi and E. P. Simoncelli. Image compression via joint statistical characterization in the wavelet domain. IEEE Transactions on Image Processing, 8(12):1688–1701, 1999. F. W. Campbell and J. G. Robson. Application of Fourier analysis to the visibility of gratings. Journal of Physiology, 197(3):551–566, August 1968. G. Camps-Valls, E. Soria-Olivas, J. P´ rez-Ruixo, A. Art´ s-Rodr´guez, F. P´ rez-Cruz, and e e ı e A. Figueiras-Vidal. A proﬁle-dependent kernel-based regression for cyclosporine concentration prediction. In Neural Information Processing Systems (NIPS) – Workshop on New Directions in Kernel-Based Learning Methods, Vancouver, Canada, December 2001. R. J. Clarke. Transform Coding of Images. Academic Press, New York, 1985. I. Epifanio, J. Guti´ rrez, and J. Malo. Linear transform for simultaneous diagonalization of coe variance and perceptual metric matrix in image coding. Pattern Recognition, 36(8):1799–1811, August 2003. J. M. Foley. Human luminance pattern mechanisms: Masking experiments require a new model. Journal of the Optical Society of America A, 11(6):1710–1719, 1994. 64 O N THE S UITABLE D OMAIN FOR SVM T RAINING IN I MAGE C ODING A. Gersho and R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Press, Boston, 1992. B. Girod. What’s wrong with mean-squared error. In A. B. Watson, editor, Digital Images and Human Vision, pages 207–220. The MIT press, 1993. G. G´ mez-P´ rez, G. Camps-Valls, J. Guti´ rrez, and J. Malo. Perceptually adaptive insensitivity for o e e support vector machine image coding. IEEE Transactions on Neural Networks, 16(6):1574–1581, 2005. J. Guti´ rrez, F. J. Ferri, and J. Malo. Regularization operators for natural images based on nonlinear e perception models. IEEE Transactions on Image Processing, 15(1):189–2000, January 2006. D. J. Heeger. Normalization of cell responses in cat striate cortex. Vis. Neurosci., 9:181–198, 1992. A. Hyvarinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, New York, 2001. A. Hyvarinen, J. Hurri, and J. Vayrynenm. Bubbles: a unifying framework for low-level statistical properties of natural image sequences. Journal of the Optical Society of America A, 20(7), 2003. R. Jiao, Y. Li, Q. Wang, and B. Li. SVM regression and its application to image compression. In International Conference on Intelligent Computing, volume 3645, pages 747–756. Lecture Notes on Computer Science, 2005. C. Jutten and J. Karhunen. Advances in nonlinear blind source separation. Proc. of the 4th Int. Symp. on Independent Component Analysis and Blind Signal Separation (ICA2003), pages 245– 256, 2003. J. Karhunen, S. Malaroiu, and M. Ilmoniemi. Local linear independent component analysis based on clustering. Intl. J. Neur. Syst., 10(6), December 2000. J. K. Lin. Factorizing probability density functions: Generalizing ICA. In Proc. of the First Intl. Workshop on ICA and Signal Separation, pages 313–318, Aussois, France, 1999. J. Malo and J. Guti´ rrez. V1 non-linear properties emerge from local-to-global non-linear ICA. e Network: Computation in Neural Systems, 17:85–102, 2006. J. Malo, A. M. Pons, A. Felipe, and J. M. Artigas. Characterization of human visual system threshold performance by a weighting function in the Gabor domain. Journal of Modern Optics, 44(1): 127–148, 1997. J. Malo, F. Ferri, J. Albert, J. Soret, and J. M. Artigas. The role of perceptual contrast non-linearities in image transform coding. Image & Vision Computing, 18(3):233–246, February 2000. J. Malo, J. Guti´ rrez, I. Epifanio, F. Ferri, and J. M. Artigas. Perceptual feed-back in multigrid moe tion estimation using an improved DCT quantization. IEEE Transactions on Image Processing, 10(10):1411–1427, October 2001. J. Malo, I. Epifanio, R. Navarro, and E. Simoncelli. Non-linear image representation for efﬁcient perceptual coding. IEEE Transactions on Image Processing, 15(1):68–80, 2006. 65 ´ ´ ´ C AMPS -VALLS , G UTI E RREZ , G OMEZ -P E REZ AND M ALO B. A. Olshausen and D. J. Field. Emergence of simple-cell receptive ﬁeld properties by learning a sparse code for natural images. Nature, 381:607–609, 1996. F. P´ rez-Cruz, G. Camps-Valls, E. Soria-Olivas, J. J. P´ rez-Ruixo, A. R. Figueiras-Vidal, and e e A. Art´ s-Rodr´guez. Multi-dimensional function approximation and regression estimation. In e ı International Conference on Artiﬁcial Neural Networks, ICANN2002, Madrid, Spain., Aug 2002. Lecture Notes in Computer Science. Springer–Verlag. J. Robinson and V. Kecman. The use of Support Vector Machines in image compression. In Proceedings of the International Conference on Engineering Intelligence Systems, EIS’2000, volume 36, pages 93–96, University of Paisley, Scotland, U.K., June 2000. J. Robinson and V. Kecman. Combining Support Vector Machine learning with the discrete cosine transform in image compression. IEEE Transactions Neural Networks, 14(4):950–958, July 2003. O. Schwartz and E. P. Simoncelli. Natural signal statistics and sensory gain control. Nature Neuroscience, 4(8):819–825, 2001. E. P. Simoncelli. Vision and the statistics of the visual environment. Current Opinion in Neurobiology, 13(2):144–149, 2003. E. P. Simoncelli. Statistical models for images: Compression, restoration and synthesis. In 31st Asilomar Conference on Signals, Systems and Computers, Paciﬁc Grove, CA, 1997. E. P. Simoncelli and B. O. Olshausen. Natural image statistics and neural representation. Annual Review of Neuroscience, 24:1193–1216, 2001. A. J. Smola and B. Sch¨ lkopf. A tutorial on support vector regression. Statistics and Computing, o 14:199–222, 2004. D. S. Taubman and M. W. Marcellin. JPEG2000: Image Compression Fundamentals, Standards and Practice. Kluwer Academic Publishers, Boston, 2001. P. C. Teo and D. J. Heeger. Perceptual image distortion. Proceedings of the First IEEE International Conference on Image Processing, 2:982–986, 1994. M. J. Wainwright, E. P. Simoncelli, and A. S. Willsky. Random cascades on wavelet trees and their use in analyzing and modeling natural images. Applied and Computational Harmonic Analysis, 11:89–123, 2001. Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli. Image quality assessment: From error visibility to structural similarity. IEEE Transactions on Image Processing, 13(4):600–612, 2004. A. B. Watson and J. Malo. Video quality measures based on the standard spatial observer. In Proceedings of the IEEE International Conference on Image Proceedings, volume 3, pages 41– 44, 2002. A. B. Watson and J. A. Solomon. A model of visual contrast gain control and pattern masking. Journal of the Optical Society of America A, 14(9):2379–2391, September 1997. 66

6 0.32237461 9 jmlr-2008-Active Learning by Spherical Subdivision

7 0.32032952 15 jmlr-2008-An Information Criterion for Variable Selection in Support Vector Machines (Special Topic on Model Selection)

8 0.30276912 89 jmlr-2008-Support Vector Machinery for Infinite Ensemble Learning

9 0.28822568 3 jmlr-2008-A Moment Bound for Multi-hinge Classifiers

10 0.24196115 34 jmlr-2008-Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks

11 0.24130118 17 jmlr-2008-Automatic PCA Dimension Selection for High Dimensional Data and Small Sample Sizes

12 0.23432784 52 jmlr-2008-Learning from Multiple Sources

13 0.20546864 57 jmlr-2008-Manifold Learning: The Price of Normalization

14 0.20325246 51 jmlr-2008-Learning Similarity with Operator-valued Large-margin Classifiers

15 0.20037827 27 jmlr-2008-Consistency of the Group Lasso and Multiple Kernel Learning

16 0.19957548 70 jmlr-2008-On Relevant Dimensions in Kernel Feature Spaces

17 0.19464865 16 jmlr-2008-Approximations for Binary Gaussian Process Classification

18 0.19222957 54 jmlr-2008-Learning to Select Features using their Properties

19 0.18774661 86 jmlr-2008-SimpleMKL

20 0.18480797 58 jmlr-2008-Max-margin Classification of Data with Absent Features

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.047), (40, 0.027), (54, 0.029), (58, 0.049), (66, 0.048), (76, 0.01), (78, 0.012), (88, 0.62), (92, 0.035), (94, 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.99596936 25 jmlr-2008-Consistency of Random Forests and Other Averaging Classifiers

Author: Gérard Biau, Luc Devroye, Gábor Lugosi

Abstract: In the last years of his life, Leo Breiman promoted random forests for use in classiﬁcation. He suggested using averaging as a means of obtaining good discrimination rules. The base classiﬁers used for averaging are simple and randomized, often based on random samples from the data. He left a few questions unanswered regarding the consistency of such rules. In this paper, we give a number of theorems that establish the universal consistency of averaging rules. We also show that some popular classiﬁers, including one suggested by Breiman, are not universally consistent. Keywords: random forests, classiﬁcation trees, consistency, bagging This paper is dedicated to the memory of Leo Breiman.

2 0.98224878 49 jmlr-2008-Learning Control Knowledge for Forward Search Planning

Author: Sungwook Yoon, Alan Fern, Robert Givan

Abstract: A number of today’s state-of-the-art planners are based on forward state-space search. The impressive performance can be attributed to progress in computing domain independent heuristics that perform well across many domains. However, it is easy to ﬁnd domains where such heuristics provide poor guidance, leading to planning failure. Motivated by such failures, the focus of this paper is to investigate mechanisms for learning domain-speciﬁc knowledge to better control forward search in a given domain. While there has been a large body of work on inductive learning of control knowledge for AI planning, there is a void of work aimed at forward-state-space search. One reason for this may be that it is challenging to specify a knowledge representation for compactly representing important concepts across a wide range of domains. One of the main contributions of this work is to introduce a novel feature space for representing such control knowledge. The key idea is to deﬁne features in terms of information computed via relaxed plan extraction, which has been a major source of success for non-learning planners. This gives a new way of leveraging relaxed planning techniques in the context of learning. Using this feature space, we describe three forms of control knowledge—reactive policies (decision list rules and measures of progress) and linear heuristics—and show how to learn them and incorporate them into forward state-space search. Our empirical results show that our approaches are able to surpass state-of-the-art nonlearning planners across a wide range of planning competition domains. Keywords: planning, machine learning, knowledge representation, search

same-paper 3 0.97012776 1 jmlr-2008-A Bahadur Representation of the Linear Support Vector Machine

Author: Ja-Yong Koo, Yoonkyung Lee, Yuwon Kim, Changyi Park

4 0.93147594 96 jmlr-2008-Visualizing Data using t-SNE

Author: Laurens van der Maaten, Geoffrey Hinton

Abstract: We present a new technique called “t-SNE” that visualizes high-dimensional data by giving each datapoint a location in a two or three-dimensional map. The technique is a variation of Stochastic Neighbor Embedding (Hinton and Roweis, 2002) that is much easier to optimize, and produces signiﬁcantly better visualizations by reducing the tendency to crowd points together in the center of the map. t-SNE is better than existing techniques at creating a single map that reveals structure at many different scales. This is particularly important for high-dimensional data that lie on several different, but related, low-dimensional manifolds, such as images of objects from multiple classes seen from multiple viewpoints. For visualizing the structure of very large data sets, we show how t-SNE can use random walks on neighborhood graphs to allow the implicit structure of all of the data to inﬂuence the way in which a subset of the data is displayed. We illustrate the performance of t-SNE on a wide variety of data sets and compare it with many other non-parametric visualization techniques, including Sammon mapping, Isomap, and Locally Linear Embedding. The visualizations produced by t-SNE are signiﬁcantly better than those produced by the other techniques on almost all of the data sets. Keywords: visualization, dimensionality reduction, manifold learning, embedding algorithms, multidimensional scaling

5 0.71620297 53 jmlr-2008-Learning to Combine Motor Primitives Via Greedy Additive Regression

Author: Manu Chhabra, Robert A. Jacobs

Abstract: The computational complexities arising in motor control can be ameliorated through the use of a library of motor synergies. We present a new model, referred to as the Greedy Additive Regression (GAR) model, for learning a library of torque sequences, and for learning the coefﬁcients of a linear combination of sequences minimizing a cost function. From the perspective of numerical optimization, the GAR model is interesting because it creates a library of “local features”—each sequence in the library is a solution to a single training task—and learns to combine these sequences using a local optimization procedure, namely, additive regression. We speculate that learners with local representational primitives and local optimization procedures will show good performance on nonlinear tasks. The GAR model is also interesting from the perspective of motor control because it outperforms several competing models. Results using a simulated two-joint arm suggest that the GAR model consistently shows excellent performance in the sense that it rapidly learns to perform novel, complex motor tasks. Moreover, its library is overcomplete and sparse, meaning that only a small fraction of the stored torque sequences are used when learning a new movement. The library is also robust in the sense that, after an initial training period, nearly all novel movements can be learned as additive combinations of sequences in the library, and in the sense that it shows good generalization when an arm’s dynamics are altered between training and test conditions, such as when a payload is added to the arm. Lastly, the GAR model works well regardless of whether motor tasks are speciﬁed in joint space or Cartesian space. We conclude that learning techniques using local primitives and optimization procedures are viable and potentially important methods for motor control and possibly other domains, and that these techniques deserve further examination by the artiﬁcial intelligence and cognitive science

6 0.68922651 89 jmlr-2008-Support Vector Machinery for Infinite Ensemble Learning

7 0.66963762 9 jmlr-2008-Active Learning by Spherical Subdivision

8 0.66531891 21 jmlr-2008-Classification with a Reject Option using a Hinge Loss

9 0.66375649 3 jmlr-2008-A Moment Bound for Multi-hinge Classifiers

10 0.65368938 43 jmlr-2008-Hit Miss Networks with Applications to Instance Selection

11 0.65206963 57 jmlr-2008-Manifold Learning: The Price of Normalization

12 0.62928182 19 jmlr-2008-Bouligand Derivatives and Robustness of Support Vector Machines for Regression

13 0.62723035 68 jmlr-2008-Nearly Uniform Validation Improves Compression-Based Error Bounds

14 0.61030841 8 jmlr-2008-Accelerated Neural Evolution through Cooperatively Coevolved Synapses

15 0.60535038 50 jmlr-2008-Learning Reliable Classifiers From Small or Incomplete Data Sets: The Naive Credal Classifier 2

16 0.5980354 14 jmlr-2008-An Extension on "Statistical Comparisons of Classifiers over Multiple Data Sets" for all Pairwise Comparisons

17 0.59669775 71 jmlr-2008-On the Equivalence of Linear Dimensionality-Reducing Transformations

18 0.59659702 31 jmlr-2008-Dynamic Hierarchical Markov Random Fields for Integrated Web Data Extraction

19 0.59265238 51 jmlr-2008-Learning Similarity with Operator-valued Large-margin Classifiers

20 0.59169263 48 jmlr-2008-Learning Bounded Treewidth Bayesian Networks