nips nips2009 nips2009-160 knowledge-graph by maker-knowledge-mining

160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

Source: pdf

Author: Masayuki Karasuyama, Ichiro Takeuchi

Abstract: We propose a multiple incremental decremental algorithm of Support Vector Machine (SVM). Conventional single incremental decremental SVM can update the trained model efﬁciently when single data point is added to or removed from the training set. When we add and/or remove multiple data points, this algorithm is time-consuming because we need to repeatedly apply it to each data point. The proposed algorithm is computationally more efﬁcient when multiple data points are added and/or removed simultaneously. The single incremental decremental algorithm is built on an optimization technique called parametric programming. We extend the idea and introduce multi-parametric programming for developing the proposed algorithm. Experimental results on synthetic and real data sets indicate that the proposed algorithm can signiﬁcantly reduce the computational cost of multiple incremental decremental operation. Our approach is especially useful for online SVM learning in which we need to remove old data points and add new data points in a short amount of time.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 jp Abstract We propose a multiple incremental decremental algorithm of Support Vector Machine (SVM). [sent-7, score-0.779]

2 Conventional single incremental decremental SVM can update the trained model efﬁciently when single data point is added to or removed from the training set. [sent-8, score-0.971]

3 When we add and/or remove multiple data points, this algorithm is time-consuming because we need to repeatedly apply it to each data point. [sent-9, score-0.289]

4 The proposed algorithm is computationally more efﬁcient when multiple data points are added and/or removed simultaneously. [sent-10, score-0.26]

5 The single incremental decremental algorithm is built on an optimization technique called parametric programming. [sent-11, score-0.835]

6 Experimental results on synthetic and real data sets indicate that the proposed algorithm can signiﬁcantly reduce the computational cost of multiple incremental decremental operation. [sent-13, score-0.871]

7 Our approach is especially useful for online SVM learning in which we need to remove old data points and add new data points in a short amount of time. [sent-14, score-0.412]

8 1 Introduction Incremental decremental algorithm for online learning of Support Vector Machine (SVM) was previously proposed in [1], and the approach was adapted to other variants of kernel machines [2–4]. [sent-15, score-0.647]

9 When a single data point is added and/or removed, these algorithms can efﬁciently update the trained model without re-training it from scratch. [sent-16, score-0.204]

10 These algorithms are built on an optimization technique called parametric programming [5–7], in which one solves a series of optimization problems parametrized by a single parameter. [sent-17, score-0.151]

11 In particular, one solves a solution path with respect to the coefﬁcient parameter corresponding to the data point to be added or removed. [sent-18, score-0.192]

12 When we add and/or remove multiple data points using these algorithms, one must repeat the updating operation for each single data point. [sent-19, score-0.366]

13 In what follows, we refer this conventional algorithm as single incremental decremental algorithm or single update algorithm. [sent-21, score-0.958]

14 In this paper, we develop a multiple incremental decremental algorithm of the SVM. [sent-22, score-0.779]

15 The proposed algorithm can update the trained model more efﬁciently when multiple data points are added and/or removed simultaneously. [sent-23, score-0.357]

16 Later, we call our proposed algorithm as multiple incremental decremental algorithm or multiple update algorithm. [sent-26, score-0.952]

17 The main computational cost of parametric programming is in solving a linear system at each breakpoint (see Section 3 for detail). [sent-27, score-0.187]

18 Thus, the total computational cost of parametric programming is roughly proportional to the number of breakpoints on the solution path. [sent-28, score-0.462]

19 In the repeated use of 1 single update algorithm for each data point, one follows the coordinate-wise solution path in the multi-dimensional coefﬁcient parameter space. [sent-29, score-0.297]

20 On the other hand, in multiple update algorithm, we establish a direction in the multi-dimensional coefﬁcient parameter space so that the total length of the path becomes much shorter than the coordinate-wise one. [sent-30, score-0.343]

21 Because the number of breakpoints in the shorter path followed by our algorithm is less than that in the longer coordinate-wise path, we can gain relative computational efﬁciency. [sent-31, score-0.525]

22 In Section 3, after brieﬂy reviewing single update algorithm, we describe our multiple update algorithm. [sent-36, score-0.261]

23 In section 4, we compare the computational cost of our multiple update algorithm with the single update algorithm and with the LIBSVM (the-state-of-the-art batch SVM solver based on SMO algorithm) in numerical experiments on synthetic and real data sets. [sent-37, score-0.446]

24 2 Support Vector Machine and KKT Conditions Suppose we have a set of training data {(xi , yi )}n , where xi ∈ X ⊆ Rd is the input and i=1 yi ∈ {−1, +1} is the output class label. [sent-39, score-0.503]

25 yi f (xi ) ≥ 1 − ξi , ξi ≥ 0, i = 1, · · · , n, where C ∈ R is the regularization parameter. [sent-43, score-0.194]

26 Introducing Lagrange ∑ multipliers αi ≥ 0, the n optimal discriminant function f : X → R can be formulated as f (x) = i=1 αi yi K(x, xi ) + b, where K(xi , xj ) = Φ(xi )T Φ(xj ) is a kernel function. [sent-44, score-0.352]

27 From the Karush-Kuhn-Tucker (KKT) optimality conditions, we obtain the following relationships: yi f (xi ) > 1 ⇒ αi = 0, (1a) yi f (xi ) = 1 ⇒ αi ∈ [0, C], (1b) yi f (xi ) < 1 ⇒ αi = C, (1c) n ∑ yi αi = 0. [sent-45, score-0.814]

28 (1d) + i=1 Using (1a)-(1c), let us deﬁne the following index sets: O = {i | yi f (xi ) > 1, αi = 0}, (2a) M = {i | yi f (xi ) = 1, 0 ≤ αi ≤ C}, (2b) I = {i | yi f (xi ) < 1, αi = C}. [sent-46, score-0.622]

29 (2c) In what follows, the subscription by an index set, such as v I for a vector v ∈ Rn , indicates a subvector of v whose elements are indexed by I. [sent-47, score-0.15]

30 Similarly, the subscription by two index sets, such as M M,O for a matrix M ∈ Rn×n , denotes a submatrix whose rows are indexed by M and columns are indexed by O. [sent-48, score-0.194]

31 1 Incremental Decremental Learning for SVM Single Incremental Decremental SVM In this section, we brieﬂy review the conventional single incremental decremental SVM [1]. [sent-51, score-0.765]

32 Using the SV sets (2b) and (2c), we can expand yi f (xi ) as ∑ ∑ yi f (xi ) = Qij αj + Qij αj + yi b, j∈M j∈I 2 where Qij = yi yj K(xi , xj ). [sent-52, score-0.858]

33 To satisfy the equality conditions (1b) and (1d), we need ∑ Qic ∆αc + Qij ∆αj + yi ∆b = 0, i ∈ M, j∈M yc ∆αc + ∑ yj ∆αj = 0. [sent-55, score-0.358]

34 2 Multiple Incremental Decremental SVM Suppose we add m new data points and remove ℓ data points simultaneously. [sent-61, score-0.362]

35 Let us denote the index set of new adding data points and removing data points as A = {n + 1, n + 2, · · · , n + m} and R ⊂ {1, · · · , n}, respectively, where |R| = ℓ. [sent-62, score-0.476]

36 When m = 1, ℓ = 0 or m = 0, ℓ = 1, our method corresponds to the conventional single incremental decremental algorithm. [sent-67, score-0.765]

37 If we have yi f (xi ) > 1, i ∈ A, we can append these indices to O and remove them from A because these points already satisfy the optimality condition (1a). [sent-69, score-0.477]

38 Similarly, we can append the indices {i | yi f (xi ) = 1, i ∈ A} to M and remove them from A. [sent-70, score-0.354]

39 In addition, we can remove the points {i | αi = 0, i ∈ R} because they already have no inﬂuence on the model. [sent-71, score-0.176]

40 Unlike single incremental decremental algorithm, we need to determine the directions of ∆αA and ∆αR . [sent-72, score-0.77]

41 For ∆αR , we simply trace the shortest path to 0, i. [sent-74, score-0.208]

42 (4) This would become the shortest path if αi = C, ∀i ∈ A, at optimality. [sent-83, score-0.177]

43 From yi f (xi ) = 1, i ∈ M, and the equality constraint (1d), we need ∑ ∑ ∑ Qij ∆αj + Qij ∆αj + Qij ∆αj + yi ∆b = 0, i ∈ M, (5) j∈A j∈R ∑ j∈A ∑ yj ∆αj + j∈M yj ∆αj + j∈R [ M= yj ∆αj = 0. [sent-85, score-0.651]

44 ][ ∆αA ∆αR ] = 0, (7) From the deﬁnitions of the index sets in (2a)-(2c), the following inequality constraints must also be satisﬁed: 0 ≤ αi + ∆αi ≤ C, yi {f (xi ) + ∆f (xi )} > 1, yi {f (xi ) + ∆f (xi )} < 1, i ∈ M, i ∈ O, i ∈ I. [sent-87, score-0.428]

45 (8a) (8b) (8c) Since we removed the indices {i | f (xi ) ≥ 1} from A, we obtain yi {f (xi ) + ∆f (xi )} < 1, i ∈ A. [sent-88, score-0.254]

46 (9) During the process of moving αi , i ∈ A, to C from 0, if the inequality (9) becomes equality for any i, we can append the point to M and remove it from A. [sent-89, score-0.233]

47 In the path following literature [8], the region that satisﬁes (8) and (9) is called critical region (CR). [sent-91, score-0.181]

48 We decide update direction by the linear system (7) while monitoring inequalities (8) and (9). [sent-92, score-0.168]

49 η ˜ ˜ If η becomes 1, we can terminate the algorithm because all the new data points in A and existing points in M, O and I satisfy the optimality conditions and αR is 0. [sent-99, score-0.29]

50 If the ith data point reaches bound of any one of the constraints (8) and (9) we need to update M, O and I. [sent-102, score-0.185]

51 In such case, we can not obtain the bias from yi f (xi ) = 1, i ∈ M. [sent-106, score-0.236]

52 If this empty margin happens during the path-following, we look for the new data points which re-enter the margin. [sent-109, score-0.201]

53 When the set M is empty, equality constraint (6) becomes ∑ ∑ yi ∆αi + yi ∆αi = ηδ(α) = 0, (13) i∈A i∈R 4 Figure 1: An illustration of the bias in empty margin case. [sent-110, score-0.636]

54 Dotted lines represent yi (gi + ∆gi (η)), for each i. [sent-111, score-0.194]

55 Then we need new margin data point m1 which enables equality constraint to be satisﬁed. [sent-117, score-0.186]

56 The index m1 is either ilow = argmax yi gi or iup = argmax yi gi . [sent-118, score-0.914]

57 i∈L i∈U If ilow , iup ∈ O ∪ I, we can update b and M as follows: δ(α) > 0 δ(α) < 0 ⇒ b = yiup giup , M = {iup }, ⇒ b = yilow gilow , M = {ilow }. [sent-119, score-0.265]

58 If ilow ∈ A or iup ∈ A, we can put either of these points to margin. [sent-121, score-0.253]

59 If we increase η, gi changes linearly: ∑ ∑ ∑ { ∑ } ∆gi (η) = − ∆αj Qij − ∆αj Qij = η − (C − αj )Qij + αj Qij . [sent-124, score-0.158]

60 j∈A j∈R j∈A j∈R Since each yi (gi + ∆gi (η)) may intersect, we need to consider the following piece-wise linear boundaries: u(η) = max yi (gi + ∆gi (η)), l(η) = min yj (gj + ∆gj (η)). [sent-125, score-0.464]

61 4 The number of breakpoints The main computational cost of incremental decremental algorithm is in solving the linear system (10) at each breakpoint (The cost is O(|M|2 ) because we use Cholesky factor update except the ﬁrst step). [sent-129, score-1.34]

62 Thus, the number of breakpoints is an important factor of the computational cost. [sent-130, score-0.356]

63 To simplify the discussion, let us introduce the following assumptions: • The number of breakpoints is proportional to the total length of the path. [sent-131, score-0.364]

64 • The path obtained by our algorithm is the shortest one. [sent-132, score-0.212]

65 5 initial final path breakpoints borders of CR (a) Adding 2 data points. [sent-133, score-0.512]

66 (b) Adding and Removing 1 data point Figure 2: The schematic illustration of the difference of path length and the number of breakpoints. [sent-134, score-0.209]

67 The update of matrices and vectors at the breakpoints are the main computational cost of pathfollowing. [sent-137, score-0.497]

68 If optimal α1 = α2 = C, our proposed algorithm can trace shortest path to optimal point from the origin (left plot). [sent-139, score-0.263]

69 On the other hand, single incremental algorithm moves one coordinate at a time (right plot). [sent-140, score-0.326]

70 Figure 2(b) shows the case that we add and remove 1 data point, respectively. [sent-141, score-0.164]

71 In this case, if α2 = C, our algorithm can trace shortest path to α1 = 0, α2 = C (left plot), while single incremental algorithm again moves one coordinate at a time (right plot). [sent-142, score-0.569]

72 The ﬁrst assumption means that the breakpoints are uniformly distributed on the path. [sent-143, score-0.336]

73 In particular, if the point i ∈ A which was located inside the margin before the update moved to M during the update (i. [sent-146, score-0.254]

74 the equality (9) holds), the path with respect to this parameter is not really the shortest one. [sent-148, score-0.233]

75 In this simpliﬁed scenario, the ratio of the number of breakpoints of multiple update algorithm to that of repeated use of single update algorithm is ∥αA ∥2 : ∥αA ∥1 , where ∥ • ∥2 is ℓ2 norm and ∥ • ∥1 is ℓ1 norm. [sent-150, score-0.667]

76 The basic idea of alpha seeding is to use the parameters before the update as the initial parameter. [sent-156, score-0.22]

77 In alpha seeding, we need to take care of the fact that the summation constraint α⊤ y = 0 may not be satisﬁed after removing αs in R. [sent-157, score-0.227]

78 In that case, we simply re-distribute ∑ δ= αi yi i∈R to the in-bound αi , i ∈ {i | 0 < αi < C}, uniformly. [sent-158, score-0.194]

79 If the kernel matrix happens to be singular, which typically arise when there are two or more identical data points in M, our algorithm may not work. [sent-163, score-0.192]

80 The cross points are generated from a mixture of two Gaussian while the circle points come from a single Gaussian. [sent-168, score-0.23]

81 1 Artiﬁcial Data First, we used simple artiﬁcial data set to see the computational cost for various number of adding and/or removing points. [sent-175, score-0.302]

82 As discussed, adding or removing the data points with αi = 0 at optimal can be performed with almost no cost. [sent-179, score-0.323]

83 Thus, to make clear comparison, we restrict the adding and/or removing points as those with αi = C at optimal. [sent-180, score-0.295]

84 We examined several scenarios: (a) adding m ∈ {1, · · · , 50} data points, (b) removing ℓ ∈ {1, · · · , 50} data points, (c) adding m ∈ {1, · · · , 25} data points and removing ℓ ∈ {1, · · · , 25} data points simultaneously. [sent-182, score-0.722]

85 The horizontal axis is the number of adding and/or removing data points. [sent-183, score-0.238]

86 The relative difference of SID-SVM and MID-SVM grows as the m and/or ℓ increase because MID-SVM can add or remove multiple data points simultaneously while SID-SVM merely iterates the algorithm m + ℓ times. [sent-186, score-0.346]

87 Figure 5 shows the number of breakpoints of SID-SVM and MID-SVM along with the theoretical number of breakpoints of the MID-SVM in √ Section 3. [sent-188, score-0.672]

88 , for scenario (a), the number of breakpoints of SID-SVM multiplied by m/m). [sent-191, score-0.336]

89 2 Application to Online Time Series Learning We applied the proposed algorithm to a online time series learning problem, in which we update the model when some new observations arrive (adding the new ones and removing the obsolete ones). [sent-194, score-0.286]

90 We add new m data points and remove the oldest ℓ data points. [sent-200, score-0.277]

91 Unlike previous experiments, we did not choose the adding or removing data points by its parameter. [sent-202, score-0.323]

92 (c) Adding m data points and removing ℓ data points simultaneously (m = ℓ). [sent-223, score-0.351]

93 (c) Adding m data points and removing ℓ data points simultaneously (m = ℓ). [sent-226, score-0.351]

94 Figure 5: The number of breakpoints (artiﬁcial data set) 3 10 1 10 0 10 10 MID−SVM SID−SVM SMO(ε=1e−3) SMO(ε=1e−6) SMO(ε=1e−9) CPU time (sec) CPU time (sec) 10 2 CPU time (sec) 2 2 10 MID−SVM SID−SVM SMO(ε=1e−3) SMO(ε=1e−6) SMO(ε=1e−9) 1 10 0 1 10 0. [sent-227, score-0.364]

95 34 −2 10 0 10 2 10 C 4 10 (d) γ = 10−3 Figure 7: Cross-validation error (Fisher river data set) 5 Conclusion We proposed multiple incremental decremental algorithm of the SVM. [sent-264, score-0.87]

96 Unlike single incremental decremental algorithm, our algorithm can efﬁciently work with simultaneous addition and/or removal of multiple data points. [sent-265, score-0.833]

97 Poggio, “Incremental and decremental support vector machine learning,” in Advances in Neural Information Processing Systems (T. [sent-271, score-0.557]

98 Zhu, “The entire regularization path for the support vector machine,” Journal of Machine Learning Research, vol. [sent-302, score-0.185]

99 Lochovsky, “A new solution path algorithm in support vector regression,” IEEE Transactions on Neural Networks, vol. [sent-316, score-0.22]

100 Nakano, “Efﬁcient leave-m-out cross-validation of support vector regression by generalizing decremental algorithm,” New Generation Computing, vol. [sent-377, score-0.557]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('decremental', 0.483), ('smo', 0.395), ('breakpoints', 0.336), ('qij', 0.237), ('incremental', 0.22), ('yi', 0.194), ('sid', 0.184), ('svm', 0.18), ('mid', 0.158), ('gi', 0.137), ('removing', 0.125), ('cpu', 0.114), ('path', 0.111), ('update', 0.097), ('remove', 0.091), ('xi', 0.087), ('points', 0.085), ('adding', 0.085), ('ilow', 0.084), ('iup', 0.084), ('sec', 0.076), ('libsvm', 0.072), ('shortest', 0.066), ('seeding', 0.063), ('river', 0.063), ('subscription', 0.063), ('alpha', 0.06), ('machines', 0.056), ('equality', 0.056), ('yj', 0.055), ('support', 0.052), ('empty', 0.048), ('decoste', 0.047), ('kkt', 0.047), ('append', 0.047), ('moves', 0.045), ('add', 0.045), ('kernel', 0.044), ('cost', 0.044), ('breakpoint', 0.042), ('karasuyama', 0.042), ('nagoya', 0.042), ('takeuchi', 0.042), ('plot', 0.042), ('bias', 0.042), ('multiple', 0.041), ('cr', 0.041), ('submatrix', 0.041), ('margin', 0.04), ('index', 0.04), ('removed', 0.038), ('optimality', 0.038), ('borders', 0.037), ('conventional', 0.036), ('satis', 0.035), ('algorithm', 0.035), ('programming', 0.034), ('cross', 0.034), ('added', 0.033), ('yc', 0.032), ('trace', 0.031), ('online', 0.029), ('keeping', 0.029), ('cache', 0.029), ('parametric', 0.028), ('data', 0.028), ('length', 0.028), ('inequalities', 0.028), ('xj', 0.027), ('qm', 0.026), ('fisher', 0.026), ('single', 0.026), ('region', 0.025), ('indexed', 0.025), ('validation', 0.024), ('direction', 0.024), ('built', 0.023), ('gj', 0.023), ('shorter', 0.023), ('solver', 0.023), ('indices', 0.022), ('vector', 0.022), ('argmax', 0.022), ('uniquely', 0.022), ('illustration', 0.022), ('updating', 0.022), ('constraint', 0.021), ('coef', 0.021), ('increase', 0.021), ('need', 0.021), ('examined', 0.02), ('optimization', 0.02), ('computational', 0.02), ('point', 0.02), ('ow', 0.02), ('determine', 0.02), ('critical', 0.02), ('becomes', 0.019), ('bound', 0.019), ('system', 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

Author: Masayuki Karasuyama, Ichiro Takeuchi

2 0.10417003 106 nips-2009-Heavy-Tailed Symmetric Stochastic Neighbor Embedding

Author: Zhirong Yang, Irwin King, Zenglin Xu, Erkki Oja

Abstract: Stochastic Neighbor Embedding (SNE) has shown to be quite promising for data visualization. Currently, the most popular implementation, t-SNE, is restricted to a particular Student t-distribution as its embedding distribution. Moreover, it uses a gradient descent algorithm that may require users to tune parameters such as the learning step size, momentum, etc., in ﬁnding its optimum. In this paper, we propose the Heavy-tailed Symmetric Stochastic Neighbor Embedding (HSSNE) method, which is a generalization of the t-SNE to accommodate various heavytailed embedding similarity functions. With this generalization, we are presented with two difﬁculties. The ﬁrst is how to select the best embedding similarity among all heavy-tailed functions and the second is how to optimize the objective function once the heavy-tailed function has been selected. Our contributions then are: (1) we point out that various heavy-tailed embedding similarities can be characterized by their negative score functions. Based on this ﬁnding, we present a parameterized subset of similarity functions for choosing the best tail-heaviness for HSSNE; (2) we present a ﬁxed-point optimization algorithm that can be applied to all heavy-tailed functions and does not require the user to set any parameters; and (3) we present two empirical studies, one for unsupervised visualization showing that our optimization algorithm runs as fast and as good as the best known t-SNE implementation and the other for semi-supervised visualization showing quantitative superiority using the homogeneity measure as well as qualitative advantage in cluster separation over t-SNE.

3 0.078785688 122 nips-2009-Label Selection on Graphs

Author: Andrew Guillory, Jeff A. Bilmes

Abstract: We investigate methods for selecting sets of labeled vertices for use in predicting the labels of vertices on a graph. We speciﬁcally study methods which choose a single batch of labeled vertices (i.e. ofﬂine, non sequential methods). In this setting, we ﬁnd common graph smoothness assumptions directly motivate simple label selection methods with interesting theoretical guarantees. These methods bound prediction error in terms of the smoothness of the true labels with respect to the graph. Some of these bounds give new motivations for previously proposed algorithms, and some suggest new algorithms which we evaluate. We show improved performance over baseline methods on several real world data sets. 1

4 0.065416031 236 nips-2009-Structured output regression for detection with partial truncation

Author: Andrea Vedaldi, Andrew Zisserman

Abstract: We develop a structured output model for object category detection that explicitly accounts for alignment, multiple aspects and partial truncation in both training and inference. The model is formulated as large margin learning with latent variables and slack rescaling, and both training and inference are computationally efﬁcient. We make the following contributions: (i) we note that extending the Structured Output Regression formulation of Blaschko and Lampert [1] to include a bias term signiﬁcantly improves performance; (ii) that alignment (to account for small rotations and anisotropic scalings) can be included as a latent variable and efﬁciently determined and implemented; (iii) that the latent variable extends to multiple aspects (e.g. left facing, right facing, front) with the same formulation; and (iv), most signiﬁcantly for performance, that truncated and truncated instances can be included in both training and inference with an explicit truncation mask. We demonstrate the method by training and testing on the PASCAL VOC 2007 data set – training includes the truncated examples, and in testing object instances are detected at multiple scales, alignments, and with signiﬁcant truncations. 1

5 0.062500022 72 nips-2009-Distribution Matching for Transduction

Author: Novi Quadrianto, James Petterson, Alex J. Smola

Abstract: Many transductive inference algorithms assume that distributions over training and test estimates should be related, e.g. by providing a large margin of separation on both sets. We use this idea to design a transduction algorithm which can be used without modiﬁcation for classiﬁcation, regression, and structured estimation. At its heart we exploit the fact that for a good learner the distributions over the outputs on training and test sets should match. This is a classical two-sample problem which can be solved efﬁciently in its most general form by using distance measures in Hilbert Space. It turns out that a number of existing heuristics can be viewed as special cases of our approach. 1

6 0.060420349 33 nips-2009-Analysis of SVM with Indefinite Kernels

7 0.059850972 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

8 0.058086645 47 nips-2009-Boosting with Spatial Regularization

9 0.053495016 80 nips-2009-Efficient and Accurate Lp-Norm Multiple Kernel Learning

10 0.051445 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

11 0.050531089 63 nips-2009-DUOL: A Double Updating Approach for Online Learning

12 0.050351512 118 nips-2009-Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

13 0.048115604 179 nips-2009-On the Algorithmics and Applications of a Mixed-norm based Kernel Learning Formulation

14 0.047465298 75 nips-2009-Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models

15 0.043943029 210 nips-2009-STDP enables spiking neurons to detect hidden causes of their inputs

16 0.043329541 129 nips-2009-Learning a Small Mixture of Trees

17 0.040709954 64 nips-2009-Data-driven calibration of linear estimators with minimal penalties

18 0.038803119 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

19 0.038764838 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

20 0.038180321 61 nips-2009-Convex Relaxation of Mixture Regression with Efficient Algorithms

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.138), (1, 0.065), (2, -0.024), (3, 0.049), (4, -0.042), (5, -0.004), (6, -0.011), (7, 0.033), (8, -0.02), (9, -0.003), (10, -0.004), (11, -0.025), (12, 0.034), (13, -0.026), (14, -0.036), (15, 0.044), (16, 0.005), (17, -0.078), (18, -0.007), (19, -0.054), (20, -0.009), (21, -0.068), (22, -0.009), (23, -0.044), (24, -0.034), (25, 0.041), (26, 0.011), (27, 0.063), (28, 0.028), (29, -0.032), (30, 0.01), (31, -0.084), (32, 0.055), (33, 0.129), (34, 0.004), (35, 0.028), (36, 0.012), (37, -0.048), (38, 0.136), (39, 0.007), (40, 0.085), (41, -0.017), (42, 0.011), (43, 0.018), (44, 0.017), (45, 0.065), (46, -0.039), (47, -0.075), (48, -0.123), (49, -0.114)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92347336 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

Author: Masayuki Karasuyama, Ichiro Takeuchi

2 0.72695917 106 nips-2009-Heavy-Tailed Symmetric Stochastic Neighbor Embedding

Author: Zhirong Yang, Irwin King, Zenglin Xu, Erkki Oja

3 0.58706695 72 nips-2009-Distribution Matching for Transduction

Author: Novi Quadrianto, James Petterson, Alex J. Smola

4 0.52689844 236 nips-2009-Structured output regression for detection with partial truncation

Author: Andrea Vedaldi, Andrew Zisserman

5 0.51235282 63 nips-2009-DUOL: A Double Updating Approach for Online Learning

Author: Peilin Zhao, Steven C. Hoi, Rong Jin

Abstract: In most online learning algorithms, the weights assigned to the misclassiﬁed examples (or support vectors) remain unchanged during the entire learning process. This is clearly insufﬁcient since when a new misclassiﬁed example is added to the pool of support vectors, we generally expect it to affect the weights for the existing support vectors. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short. Instead of only assigning a ﬁxed weight to the misclassiﬁed example received in current trial, the proposed online learning algorithm also tries to update the weight for one of the existing support vectors. We show that the mistake bound can be signiﬁcantly improved by the proposed online learning method. Encouraging experimental results show that the proposed technique is in general considerably more effective than the state-of-the-art online learning algorithms. 1

6 0.50654674 122 nips-2009-Label Selection on Graphs

7 0.48229334 189 nips-2009-Periodic Step Size Adaptation for Single Pass On-line Learning

8 0.47928759 210 nips-2009-STDP enables spiking neurons to detect hidden causes of their inputs

9 0.46972054 75 nips-2009-Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models

10 0.46721977 33 nips-2009-Analysis of SVM with Indefinite Kernels

11 0.45911503 34 nips-2009-Anomaly Detection with Score functions based on Nearest Neighbor Graphs

12 0.45777661 129 nips-2009-Learning a Small Mixture of Trees

13 0.42167971 47 nips-2009-Boosting with Spatial Regularization

14 0.41940305 118 nips-2009-Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

15 0.41226557 76 nips-2009-Efficient Learning using Forward-Backward Splitting

16 0.40919909 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

17 0.40776497 71 nips-2009-Distribution-Calibrated Hierarchical Classification

18 0.40156382 222 nips-2009-Sparse Estimation Using General Likelihoods and Non-Factorial Priors

19 0.39440039 92 nips-2009-Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming

20 0.38902223 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.012), (24, 0.03), (25, 0.569), (35, 0.03), (36, 0.084), (39, 0.026), (58, 0.057), (61, 0.013), (71, 0.022), (86, 0.059)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.99113607 152 nips-2009-Measuring model complexity with the prior predictive

Author: Wolf Vanpaemel

Abstract: In the last few decades, model complexity has received a lot of press. While many methods have been proposed that jointly measure a model’s descriptive adequacy and its complexity, few measures exist that measure complexity in itself. Moreover, existing measures ignore the parameter prior, which is an inherent part of the model and affects the complexity. This paper presents a stand alone measure for model complexity, that takes the number of parameters, the functional form, the range of the parameters and the parameter prior into account. This Prior Predictive Complexity (PPC) is an intuitive and easy to compute measure. It starts from the observation that model complexity is the property of the model that enables it to ﬁt a wide range of outcomes. The PPC then measures how wide this range exactly is. keywords: Model Selection & Structure Learning; Model Comparison Methods; Perception The recent revolution in model selection methods in the cognitive sciences was driven to a large extent by the observation that computational models can differ in their complexity. Differences in complexity put models on unequal footing when their ability to approximate empirical data is assessed. Therefore, models should be penalized for their complexity when their adequacy is measured. The balance between descriptive adequacy and complexity has been termed generalizability [1, 2]. Much attention has been devoted to developing, advocating, and comparing different measures of generalizability (for a recent overview, see [3]). In contrast, measures of complexity have received relatively little attention. The aim of the current paper is to propose and illustrate a stand alone measure of model complexity, called the Prior Predictive Complexity (PPC). The PPC is based on the intuitive idea that a complex model can predict many outcomes and a simple model can predict a few outcomes only. First, I discuss existing approaches to measuring model complexity and note some of their limitations. In particular, I argue that currently existing measures ignore one important aspect of a model: the prior distribution it assumes over the parameters. I then introduce the PPC, which, unlike the existing measures, is sensitive to the parameter prior. Next, the PPC is illustrated by calculating the complexities of two popular models of information integration. 1 Previous approaches to measuring model complexity A ﬁrst approach to assess the (relative) complexity of models relies on simulated data. Simulationbased methods differ in how these artiﬁcial data are generated. A ﬁrst, atheoretical approach uses random data [4, 5]. In the semi-theoretical approach, the data are generated from some theoretically ∗ I am grateful to Michael Lee and Liz Bonawitz. 1 interesting functions, such as the exponential or the logistic function [4]. Using these approaches, the models under consideration are equally complex if each model provides the best optimal ﬁt to roughly the same number of data sets. A ﬁnal approach to generating artiﬁcial data is a theoretical one, in which the data are generated from the models of interest themselves [6, 7]. The parameter sets used in the generation can either be hand-picked by the researcher, estimated from empirical data or drawn from a previously speciﬁed distribution. If the models under consideration are equally complex, each model should provide the best optimal ﬁt to self-generated data more often than the other models under consideration do. One problem with this simulation-based approach is that it is very labor intensive. It requires generating a large amount of artiﬁcial data sets, and ﬁtting the models to all these data sets. Further, it relies on choices that are often made in an arbitrary fashion that nonetheless bias the results. For example, in the semi-theoretical approach, a crucial choice is which functions to use. Similarly, in the theoretical approach, results are heavily inﬂuenced by the parameter values used in generating the data. If they are ﬁxed, on what basis? If they are estimated from empirical data, from which data? If they are drawn randomly, from which distribution? Further, a simulation study only gives a rough idea of complexity differences but provides no direct measure reﬂecting the complexity. A number of proposals have been made to measure model complexity more directly. Consider a model M with k parameters, summarized in the parameter vector θ = (θ1 , θ2 , . . . , θk , ) which has a range indicated by Ω. Let d denote the data and p(d|θ, M ) the likelihood. The most straightforward measure of model complexity is the parametric complexity (PC), which simply counts the number of parameters: PC = k. (1) PC is attractive as a measure of model complexity since it is very easy to calculate. Further, it has a direct and well understood relation toward complexity: the more parameters, the more complex the model. It is included as the complexity term of several generalizability measures such as AIC [8] and BIC [9], and it is at the heart of the Likelihood Ratio Test. Despite this intuitive appeal, PC is not free from problems. One problem with PC is that it reﬂects only a single aspect of complexity. Also the parameter range and the functional form (the way the parameters are combined in the model equation) inﬂuence a model’s complexity, but these dimensions of complexity are ignored in PC [2, 6]. A complexity measure that takes these three dimensions into account is provided by the geometric complexity (GC) measure, which is inspired by differential geometry [10]. In GC, complexity is conceptualized as the number of distinguishable probability distributions a model can generate. It is deﬁned by GC = k n ln + ln 2 2π det I(θ|M )dθ, (2) Ω where n indicates the size of the data sample and I(θ) is the Fisher Information Matrix: Iij (θ|M ) = −Eθ ∂ 2 ln p(d|θ, M ) . ∂θi ∂θj (3) Note that I(θ|M ) is determined by the likelihood function p(d|θ, M ), which is in turn determined by the model equation. Hence GC is sensitive to the number of parameters (through k), the functional form (through I), and the range (through Ω). Quite surprisingly, GC turns out to be equal to the complexity term used in one version of Minimum Description Length (MDL), a measure of generalizability developed within the domain of information theory [2, 11, 12, 13]. GC contrasts favorably with PC, in the sense that it takes three dimensions of complexity into account rather than a single one. A major drawback of GC is that, unlike PC, it requires considerable technical sophistication to be computed, as it relies on the second derivative of the likelihood. A more important limitation of both PC and GC is that these measures are insensitive to yet another important dimension contributing to model complexity: the prior distribution over the model parameters. The relation between the parameter prior distribution and model complexity is discussed next. 2 2 Model complexity and the parameter prior The growing popularity of Bayesian methods in psychology has not only raised awareness that model complexity should be taken into account when testing models [6], it has also drawn attention to the fact that in many occasions, relevant prior information is available [14]. In Bayesian methods, there is room to incorporate this information in two different ﬂavors: as a prior distribution over the models, or as a prior distribution over the parameters. Specifying a model prior is a daunting task, so almost invariably, the model prior is taken to be uniform (but see [15] for an exception). In contrast, information regarding the parameter is much easier to include, although still challenging (e.g., [16]). There are two ways to formalize prior information about a model’s parameters: using the parameter prior range (often referred to as simply the range) and using the parameter prior distribution (often referred to as simply the prior). The prior range indicates which parameter values are allowed and which are forbidden. The prior distribution indicates which parameter values are likely and which are unlikely. Models that share the same equation and the same range but differ in the prior distribution can be considered different models (or at least different model versions), just like models that share the same equation but differ in range are different model versions. Like the parameter prior range, the parameter prior distribution inﬂuences the model complexity. In general, a model with a vague parameter prior distribution is more complex than a model with a sharply peaked parameter prior distribution, much as a model with a broad-ranged parameter is more complex than the same model where the parameter is heavily restricted. To drive home the point that the parameter prior should be considered when model complexity is assessed, consider the following “fair coin” model Mf and a “biased coin” model Mb . There is a clear intuitive complexity difference between these models: Mb is more complex than Mf . The most straightforward way to formalize these models is as follows, where ph denotes the probability of observing heads: ph = 1/2, (4) ph = θ 0≤θ≤1 p(θ) = 1, (5) for model Mf and the triplet of equations jointly deﬁne model Mb . The range forbids values smaller than 0 or greater than 1 because ph is a proportion. As Mf and Mb have a different number of parameters, both PC and GC, being sensitive to the number of parameters, pick up the difference in model complexity between the models. Alternatively, model Mf could be deﬁned as follows: ph = θ 0≤θ≤1 1 p(θ) = δ(θ − ), 2 (6) where δ(x) is the Dirac delta. Note that the model formalized in Equation 6 is exactly identical the model formalized in Equation 4. However, relying on the formulation of model Mf in Equation 6, PC and GC now judge Mf and Mb to be equally complex: both models share the same model equation (which implies they have the same number of parameters and the same functional form) and the same range for the parameter. Hence, PC and GC make an incorrect judgement of the complexity difference between both models. This misjudgement is a direct result of the insensitivity of these measures to the parameter prior. As models Mf and Mb have different prior distributions over their parameter, a measure sensitive to the prior would pick up the complexity difference between these models. Such a measure is introduced next. 3 The Prior Predictive Complexity Model complexity refers to the property of the model that enables it to predict a wide range of data patterns [2]. The idea of the PPC is to measure how wide this range exactly is. A complex model 3 can predict many outcomes, and a simple model can predict a few outcomes only. Model simplicity, then, refers to the property of placing restrictions on the possible outcomes: the greater restrictions, the greater the simplicity. To understand how model complexity is measured in the PPC, it is useful to think about the universal interval (UI) and the predicted interval (PI). The universal interval is the range of outcomes that could potentially be observed, irrespective of any model. For example, in an experiment with n binomial trials, it is impossible to observe less that zero successes, or more than n successes, so the range of possible outcomes is [0, n] . Similarly, the universal interval for a proportion is [0, 1]. The predicted interval is the interval containing all outcomes the model predicts. An intuitive way to gauge model complexity is then the cardinality of the predicted interval, relative to the cardinality of the universal interval, averaged over all m conditions or stimuli: PPC = 1 m m i=1 |PIi | . |UIi | (7) A key aspect of the PPC is deriving the predicted interval. For a parameterized likelihood-based model, prediction takes the form of a distribution over all possible outcomes for some future, yet-tobe-observed data d under some model M . This distribution is called the prior predictive distribution (ppd) and can be calculated using the law of total probability: p(d|M ) = p(d|θ, M )p(θ|M )dθ. (8) Ω Predicting the probability of unseen future data d arising under the assumption that model M is true involves integrating the probability of the data for each of the possible parameter values, p(d|θ, M ), as weighted by the prior probability of each of these values, p(θ|M ). Note that the ppd relies on the number of parameters (through the number of integrals and the likelihood), the model equation (through the likelihood), and the parameter range (through Ω). Therefore, as GC, the PPC is sensitive to all these aspects. In contrast to GC, however, the ppd, and hence the PPC, also relies on the parameter prior. Since predictions are made probabilistically, virtually all outcomes will be assigned some prior weight. This implies that, in principle, the predicted interval equals the universal interval. However, for some outcomes the assigned weight will be extremely small. Therefore, it seems reasonable to restrict the predicted interval to the smallest interval that includes some predetermined amount of the prior mass. For example, the 95% predictive interval is deﬁned by those outcomes with the highest prior mass that together make up 95% of the prior mass. Analytical solutions to the integral deﬁning the ppd are rarely available. Instead, one should rely on approximations to the ppd by drawing samples from it. In the current study, sampling was performed using WinBUGS [17, 18], a highly versatile, user friendly, and freely available software package. It contains sophisticated and relatively general-purpose Markov Chain Monte Carlo (MCMC) algorithms to sample from any distribution of interest. 4 An application example The PPC is illustrated by comparing the complexity of two popular models of information integration, which attempt to account for how people merge potentially ambiguous or conﬂicting information from various sensorial sources to create subjective experience. These models either assume that the sources of information are combined additively (the Linear Integration Model; LIM; [19]) or multiplicatively (the Fuzzy Logical Model of Perception; FLMP; [20, 21]). 4.1 Information integration tasks A typical information integration task exposes participants simultaneously to different sources of information and requires this combined experience to be identiﬁed in a forced-choice identiﬁcation task. The presented stimuli are generated from a factorial manipulation of the sources of information by systematically varying the ambiguity of each of the sources. The relevant empirical data consist 4 of, for each of the presented stimuli, the counts km of the number of times the mth stimulus was identiﬁed as one of the response alternatives, out of the tm trials on which it was presented. For example, an experiment in phonemic identiﬁcation could involve two phonemes to be identiﬁed, /ba/ and /da/ and two sources of information, auditory and visual. Stimuli are created by crossing different levels of audible speech, varying between /ba/ and /da/, with different levels of visible speech, also varying between these alternatives. The resulting set of stimuli spans a continuum between the two syllables. The participant is then asked to listen and to watch the speaker, and based on this combined audiovisual experience, to identify the syllable as being either /ba/ or /da/. In the so-called expanded factorial design, not only bimodal stimuli (containing both auditory and visual information) but also unimodal stimuli (providing only a single source of information) are presented. 4.2 Information integration models In what follows, the formal description of the LIM and the FLMP is outlined for a design with two response alternatives (/da/ or /ba/) and two sources (auditory and visual), with I and J levels, respectively. In such a two-choice identiﬁcation task, the counts km follow a Binomial distribution: km ∼ Binomial(pm , tm ), (9) where pm indicates the probability that the mth stimulus is identiﬁed as /da/. 4.2.1 Model equation The probability for the stimulus constructed with the ith level of the ﬁrst source and the jth level of the second being identiﬁed as /da/ is computed according to the choice rule: pij = s (ij, /da/) , s (ij, /da/) + s (ij, /ba/) (10) where s (ij, /da/) represents the overall degree of support for the stimulus to be /da/. The sources of information are assumed to be evaluated independently, implying that different parameters are used for the different modalities. In the present example, the degree of auditory support for /da/ is denoted by ai (i = 1, . . . , I) and the degree of visual support for /da/ by bj (j = 1, . . . , J). When a unimodal stimulus is presented, the overall degree of support for each alternative is given by s (i∗, /da/) = ai and s (∗j, /da/) = bj , where the asterisk (*) indicates the absence of information, implying that Equation 10 reduces to pi∗ = ai and p∗j = bj . (11) When a bimodal stimulus is presented, the overall degree of support for each alternative is based on the integration or blending of both these sources. Hence, for bimodal stimuli, s (ij, /da/) = ai bj , where the operator denotes the combination of both sources. Hence, Equation 10 reduces to ai bj . (12) pij = ai bj + (1 − ai ) (1 − bj ) = +, so Equation 12 becomes The LIM assumes an additive combination, i.e., pij = ai + bj . 2 (13) The FLMP, in contrast, assumes a multiplicative combination, i.e., = ×, so Equation 12 becomes ai bj . ai bj + (1 − ai )(1 − bj ) (14) pij = 5 4.2.2 Parameter prior range and distribution Each level of auditory and visual support for /da/ (i.e., ai and bj , respectively) is associated with a free parameter, which implies that the FLMP and the LIM have an equal number of free parameters, I + J. Each of these parameters is constrained to satisfy 0 ≤ ai , bj ≤ 1. The original formulations of the LIM and FLMP unfortunately left the parameter priors unspeciﬁed. However, an implicit assumption that has been commonly used is a uniform prior for each of the parameters. This assumption implicitly underlies classical and widely adopted methods for model evaluation using accounted percentage of variance or maximum likelihood. ai ∼ Uniform(0, 1) and bi ∼ Uniform(0, 1) for i = 1, . . . , I; j = 1, . . . , J. (15) The models relying on this set of uniform priors will be referred to as LIMu and FLMPu . Note that LIMu and FLMPu treat the different parameters as independent. This approach misses important information. In particular, the experimental design is such that the amount of support for each level i + 1 is always higher than for level i. Because parameter ai (or bi ) corresponds to the degree of auditory (or visual) support for a unimodal stimulus at the ith level, it seems reasonable to expect the following orderings among the parameters to hold (see also [6]): aj > ai and bj > bi for j > i. (16) The models relying on this set of ordered priors will be referred to as LIMo and FLMPo . 4.3 Complexity and experimental design It is tempting to consider model complexity as an inherent characteristic of a model. For some models and for some measures of complexity this is clearly the case. Consider, for example, model Mb . In any experimental design (i.e., a number of coin tosses), PCMb = 1. However, more generally, this is not the case. Focusing on the FLMP and the LIM, it is clear that even a simple measure as PC depends crucially on (some aspects of) the experimental design. In particular, every level corresponds to a new parameter, so PC = I + J . Similarly, GC is dependent on design choices. The PPC is not different in this respect. The design sensitivity implies that one can only make sensible conclusions about differences in model complexity by using different designs. In an information integration task, the design decisions include the type of design (expanded or not), the number of sources, the number of response alternatives, the number of levels for each source, and the number of observations for each stimulus (sample size). The present study focuses on the expanded factorial designs with two sources and two response alternatives. The additional design features were varied: both a 5 × 5 and a 8 × 2 design were considered, using three different sample sizes (20, 60 and 150, following [2]). 4.4 Results Figure 1 shows the 99% predicted interval in the 8×2 design with n = 150. Each panel corresponds to a different model. In each panel, each of the 26 stimuli is displayed on the x-axis. The ﬁrst eight stimuli correspond to the stimuli with the lowest level of visual support, and are ordered in increasing order of auditory support. The next eight stimuli correspond to the stimuli with the highest level of visual support. The next eight stimuli correspond to the unimodal stimuli where only auditory information is provided (again ranked in increasing order). The ﬁnal two stimuli are the unimodal visual stimuli. Panel A shows that the predicted interval of LIMu nearly equals the universal interval, ranging between 0 and 1. This indicates that almost all outcomes are given a non-negligible prior mass by LIMu , making it almost maximally complex. FLMPu is even more complex. The predicted interval, shown in Panel B, virtually equals the universal interval, indicating that the model predicts virtually every possible outcome. Panels C and D show the dramatic effect of incorporating relevant prior information in the models. The predicted intervals of both LIMo and FLMPo are much smaller than their counterparts using the uniform priors. Focusing on the comparison between LIM and FLMP, the PPC indicates that the latter is more complex than the former. This observation holds irrespective of the model version (assuming uniform 6 0.9 0.8 0.8 Proportion of /da/ responses 1 0.9 Proportion of /da/ responses 1 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.7 0.6 0.5 0.4 0.3 0.2 0.1 11 21 A 1* 0 *1 11 21 B 1* *1 1* *1 0.8 Proportion of /da/ responses 0.9 0.8 21 1 0.9 Proportion of /da/ responses 1 11 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.7 0.6 0.5 0.4 0.3 0.2 0.1 11 21 C 1* 0 *1 D Figure 1: The 99% predicted interval for each of the 26 stimuli (x-axis) according to LIMu (Panel A), FLMPu (Panel B), LIMo (Panel C), and FLMPo (Panel D). Table 1: PPC, based on the 99% predicted interval, for four models across six different designs. 20 LIMu FLMPu LIMo FLMPo 5×5 60 150 20 8×2 60 150 0.97 1 0.75 0.83 0.94 1 0.67 0.80 .97 1 0.77 0.86 0.95 1 0.69 0.82 0.93 0.99 0.64 0.78 7 0.94 0.99 0.66 0.81 vs. ordered priors). The smaller complexity of LIM is in line with previous attempts to measure the relative complexities of LIM and FLMP, such as the atheoretical simulation-based approach ([4] but see [5]), the semi-theoretical simulation-based approach [4], the theoretical simulation-based approach [2, 6, 22], and a direct computation of the GC [2]. The PPC’s for all six designs considered are displayed in Table 1. It shows that the observations made for the 8 × 2, n = 150 design holds across the ﬁve remaining designs as well: LIM is simpler than FLMP; and models assuming ordered priors are simpler than models assuming uniform priors. Note that these conclusions would not have been possible based on PC or GC. For PC, all four models have the same complexity. GC, in contrast, would detect complexity differences between LIM and FLMP (i.e., the ﬁrst conclusion), but due to its insensitivity to the parameter prior, the complexity differences between LIMu and LIMo on the one hand, and FLMPu and FLMPo on the other hand (i.e., the second conclusion) would have gone unnoticed. 5 Discussion A theorist deﬁning a model should clearly and explicitly specify at least the three following pieces of information: the model equation, the parameter prior range, and the parameter prior distribution. If any of these pieces is missing, the model should be regarded as incomplete, and therefore untestable. Consequently, any measure of generalizability should be sensitive to all three aspects of the model deﬁnition. Many currently popular generalizability measures do not satisfy this criterion, including AIC, BIC and MDL. A measure of generalizability that does take these three aspects of a model into account is the marginal likelihood [6, 7, 14, 23]. Often, the marginal likelihood is criticized exactly for its sensitivity to the prior range and distribution (e.g., [24]). However, in the light of the fact that the prior is a part of the model deﬁnition, I see the sensitivity of the marginal likelihood to the prior as an asset rather than a nuisance. It is precisely the measures of generalizability that are insensitive to the prior that miss an important aspect of the model. Similarly, any stand alone measure of model complexity should be sensitive to all three aspects of the model deﬁnition, as all three aspects contribute to the model’s complexity (with the model equation contributing two factors: the number of parameters and the functional form). Existing measures of complexity do not satisfy this requirement and are therefore incomplete. PC takes only part of the model equation into account, whereas GC takes only the model equation and the range into account. In contrast, the PPC currently proposed is sensitive to all these three aspects. It assesses model complexity using the predicted interval which contains all possible outcomes a model can generate. A narrow predicted interval (relative to the universal interval) indicates a simple model; a complex model is characterized by a wide predicted interval. There is a tight coupling between the notions of information, knowledge and uncertainty, and the notion of model complexity. As parameters correspond to unknown variables, having more information available leads to fewer parameters and hence to a simpler model. Similarly, the more information there is available, the sharper the parameter prior, implying a simpler model. To put it differently, the less uncertainty present in a model, the narrower its predicted interval, and the simpler the model. For example, in model Mb , there is maximal uncertainty. Nothing but the range is known about θ, so all values of θ are equally likely. In contrast, in model Mf , there is minimal uncertainty. In fact, ph is known for sure, so only a single value of θ is possible. This difference in uncertainty is translated in a difference in complexity. The same is true for the information integration models. Incorporating the order constraints in the priors reduces the uncertainty compared to the models without these constraints (it tells you, for example, that parameter a1 is smaller than a2 ). This reduction in uncertainty is reﬂected by a smaller complexity. There are many different sources of prior information that can be translated in a range or distribution. The illustration using the information integration models highlighted that prior information can reﬂect meaningful information in the design. Alternatively, priors can be informed by previous applications of similar models in similar settings. Probably the purest form of priors are those that translate theoretical assumptions made by a model (see [16]). The fact that it is often difﬁcult to formalize this prior information may not be used as an excuse to leave the prior unspeciﬁed. Sure it is a challenging task, but so is translating theoretical assumptions into the model equation. Formalizing theory, intuitions, and information is what model building is all about. 8 References [1] Myung, I. J. (2000) The importance of complexity in model selection. Journal of Mathematical Psychology, 44, 190–204. [2] Pitt, M. A., Myung, I. J., and Zhang, S. (2002) Toward a method of selecting among computational models of cognition. Psychological Review, 109, 472–491. [3] Shiffrin, R. M., Lee, M. D., Kim, W., and Wagenmakers, E. J. (2008) A survey of model evaluation approaches with a tutorial on hierarchical Bayesian methods. Cognitive Science, 32, 1248–1284. [4] Cutting, J. E., Bruno, N., Brady, N. P., and Moore, C. (1992) Selectivity, scope, and simplicity of models: A lesson from ﬁtting judgments of perceived depth. Journal of Experimental Psychology: General, 121, 364–381. [5] Dunn, J. (2000) Model complexity: The ﬁt to random data reconsidered. Psychological Research, 63, 174–182. [6] Myung, I. J. and Pitt, M. A. (1997) Applying Occam’s razor in modeling cognition: A Bayesian approach. Psychonomic Bulletin & Review, 4, 79–95. [7] Vanpaemel, W. and Storms, G. (in press) Abstraction and model evaluation in category learning. Behavior Research Methods. [8] Akaike, H. (1973) Information theory and an extension of the maximum likelihood principle. Petrov, B. and Csaki, B. (eds.), Second International Symposium on Information Theory, pp. 267–281, Academiai Kiado. [9] Schwarz, G. (1978) Estimating the dimension of a model. Annals of Statistics, 6, 461–464. [10] Myung, I. J., Balasubramanian, V., and Pitt, M. A. (2000) Counting probability distributions: Differential geometry and model selection. Proceedings of the National Academy of Sciences, 97, 11170–11175. [11] Lee, M. D. (2002) Generating additive clustering models with minimal stochastic complexity. Journal of Classiﬁcation, 19, 69–85. [12] Rissanen, J. (1996) Fisher information and stochastic complexity. IEEE Transactions on Information Theory, 42, 40–47. [13] Gr¨ nwald, P. (2000) Model selection based on minimum description length. Journal of Mathematical u Psychology, 44, 133–152. [14] Lee, M. D. and Wagenmakers, E. J. (2005) Bayesian statistical inference in psychology: Comment on Traﬁmow (2003). Psychological Review, 112, 662–668. [15] Lee, M. D. and Vanpaemel, W. (2008) Exemplars, prototypes, similarities and rules in category representation: An example of hierarchical Bayesian analysis. Cognitive Science, 32, 1403–1424. [16] Vanpaemel, W. and Lee, M. D. (submitted) Using priors to formalize theory: Optimal attention and the generalized context model. [17] Lee, M. D. (2008) Three case studies in the Bayesian analysis of cognitive models. Psychonomic Bulletin & Review, 15, 1–15. [18] Spiegelhalter, D., Thomas, A., Best, N., and Lunn, D. (2004) WinBUGS User Manual Version 2.0. Medical Research Council Biostatistics Unit. Institute of Public Health, Cambridge. [19] Anderson, N. H. (1981) Foundations of information integration theory. Academic Press. [20] Oden, G. C. and Massaro, D. W. (1978) Integration of featural information in speech perception. Psychological Review, 85, 172–191. [21] Massaro, D. W. (1998) Perceiving Talking Faces: From Speech Perception to a Behavioral Principle. MIT Press. [22] Massaro, D. W., Cohen, M. M., Campbell, C. S., and Rodriguez, T. (2001) Bayes factor of model selection validates FLMP. Psychonomic Bulletin and Review, 8, 1–17. [23] Kass, R. E. and Raftery, A. E. (1995) Bayes factors. Journal of the American Statistical Association, 90, 773–795. [24] Liu, C. C. and Aitkin, M. (2008) Bayes factors: Prior sensitivity and model generalizability. Journal of Mathematical Psychology, 53, 362–375. 9

2 0.96564066 201 nips-2009-Region-based Segmentation and Object Detection

Author: Stephen Gould, Tianshi Gao, Daphne Koller

Abstract: Object detection and multi-class image segmentation are two closely related tasks that can be greatly improved when solved jointly by feeding information from one task to the other [10, 11]. However, current state-of-the-art models use a separate representation for each task making joint inference clumsy and leaving the classiﬁcation of many parts of the scene ambiguous. In this work, we propose a hierarchical region-based approach to joint object detection and image segmentation. Our approach simultaneously reasons about pixels, regions and objects in a coherent probabilistic model. Pixel appearance features allow us to perform well on classifying amorphous background classes, while the explicit representation of regions facilitate the computation of more sophisticated features necessary for object detection. Importantly, our model gives a single uniﬁed description of the scene—we explain every pixel in the image and enforce global consistency between all random variables in our model. We run experiments on the challenging Street Scene dataset [2] and show signiﬁcant improvement over state-of-the-art results for object detection accuracy. 1

same-paper 3 0.96111369 160 nips-2009-Multiple Incremental Decremental Learning of Support Vector Machines

Author: Masayuki Karasuyama, Ichiro Takeuchi

4 0.94923514 258 nips-2009-Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise

Author: Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier R. Movellan, Paul L. Ruvolo

Abstract: Modern machine learning-based approaches to computer vision require very large databases of hand labeled images. Some contemporary vision systems already require on the order of millions of images for training (e.g., Omron face detector [9]). New Internet-based services allow for a large number of labelers to collaborate around the world at very low cost. However, using these services brings interesting theoretical and practical challenges: (1) The labelers may have wide ranging levels of expertise which are unknown a priori, and in some cases may be adversarial; (2) images may vary in their level of difﬁculty; and (3) multiple labels for the same image must be combined to provide an estimate of the actual label of the image. Probabilistic approaches provide a principled way to approach these problems. In this paper we present a probabilistic model and use it to simultaneously infer the label of each image, the expertise of each labeler, and the difﬁculty of each image. On both simulated and real data, we demonstrate that the model outperforms the commonly used “Majority Vote” heuristic for inferring image labels, and is robust to both noisy and adversarial labelers. 1

5 0.9382093 245 nips-2009-Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation

Author: Shuheng Zhou

Abstract: Given n noisy samples with p dimensions, where n ≪ p, we show that the multistep thresholding procedure can accurately estimate a sparse vector β ∈ Rp in a linear model, under the restricted eigenvalue conditions (Bickel-Ritov-Tsybakov 09). Thus our conditions for model selection consistency are considerably weaker than what has been achieved in previous works. More importantly, this method allows very signiﬁcant values of s, which is the number of non-zero elements in the true parameter. For example, it works for cases where the ordinary Lasso would have failed. Finally, we show that if X obeys a uniform uncertainty principle and if the true parameter is sufﬁciently sparse, the Gauss-Dantzig selector (Cand` se Tao 07) achieves the ℓ2 loss within a logarithmic factor of the ideal mean square error one would achieve with an oracle which would supply perfect information about which coordinates are non-zero and which are above the noise level, while selecting a sufﬁciently sparse model. 1

6 0.77912706 214 nips-2009-Semi-supervised Regression using Hessian energy with an application to semi-supervised dimensionality reduction

7 0.76585597 133 nips-2009-Learning models of object structure

8 0.75765979 211 nips-2009-Segmenting Scenes by Matching Image Composites

9 0.71891361 25 nips-2009-Adaptive Design Optimization in Experiments with People

10 0.6772089 115 nips-2009-Individuation, Identification and Object Discovery

11 0.67453611 225 nips-2009-Sparsistent Learning of Varying-coefficient Models with Structural Changes

12 0.66871065 1 nips-2009-$L 1$-Penalized Robust Estimation for a Class of Inverse Problems Arising in Multiview Geometry

13 0.664644 5 nips-2009-A Bayesian Model for Simultaneous Image Clustering, Annotation and Object Segmentation

14 0.66255033 85 nips-2009-Explaining human multiple object tracking as resource-constrained approximate inference in a dynamic probabilistic model

15 0.65785307 175 nips-2009-Occlusive Components Analysis

16 0.65514475 44 nips-2009-Beyond Categories: The Visual Memex Model for Reasoning About Object Relationships

17 0.64282936 229 nips-2009-Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

18 0.6406846 131 nips-2009-Learning from Neighboring Strokes: Combining Appearance and Context for Multi-Domain Sketch Recognition

19 0.63464069 28 nips-2009-An Additive Latent Feature Model for Transparent Object Recognition

20 0.63050425 231 nips-2009-Statistical Models of Linear and Nonlinear Contextual Interactions in Early Visual Processing