nips nips2013 nips2013-14 knowledge-graph by maker-knowledge-mining

14 nips-2013-A Stability-based Validation Procedure for Differentially Private Machine Learning

Source: pdf

Author: Kamalika Chaudhuri, Staal A. Vinterbo

Abstract: Differential privacy is a cryptographically motivated deﬁnition of privacy which has gained considerable attention in the algorithms, machine-learning and datamining communities. While there has been an explosion of work on differentially private machine learning algorithms, a major barrier to achieving end-to-end differential privacy in practical machine learning applications is the lack of an effective procedure for differentially private parameter tuning, or, determining the parameter value, such as a bin size in a histogram, or a regularization parameter, that is suitable for a particular application. In this paper, we introduce a generic validation procedure for differentially private machine learning algorithms that apply when a certain stability condition holds on the training algorithm and the validation performance metric. The training data size and the privacy budget used for training in our procedure is independent of the number of parameter values searched over. We apply our generic procedure to two fundamental tasks in statistics and machine-learning – training a regularized linear classiﬁer and building a histogram density estimator that result in end-toend differentially private solutions for these problems. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Differential privacy is a cryptographically motivated deﬁnition of privacy which has gained considerable attention in the algorithms, machine-learning and datamining communities. [sent-4, score-0.923]

2 In this paper, we introduce a generic validation procedure for differentially private machine learning algorithms that apply when a certain stability condition holds on the training algorithm and the validation performance metric. [sent-6, score-1.737]

3 The training data size and the privacy budget used for training in our procedure is independent of the number of parameter values searched over. [sent-7, score-0.765]

4 We apply our generic procedure to two fundamental tasks in statistics and machine-learning – training a regularized linear classiﬁer and building a histogram density estimator that result in end-toend differentially private solutions for these problems. [sent-8, score-1.284]

5 The emerging standard for privacy-preserving computation for the past few years is differential privacy [7]. [sent-10, score-0.544]

6 The value α is called the privacy budget, and measures the level of privacy risk allowed. [sent-13, score-0.902]

7 As more noise is needed to achieve lower α,the price of higher privacy is reduced utility or accuracy. [sent-14, score-0.451]

8 1 A major barrier to achieving end-to-end differential privacy in practical machine-learning applications is the absence of an effective procedure for differentially private parameter-tuning. [sent-20, score-1.534]

9 Currently, parameter-tuning with differential privacy is done in two ways. [sent-22, score-0.544]

10 However re-using the data leads to a degradation in the privacy guarantees, and thus to maintain the privacy budget α, for each training, we need to use a privacy budget that shrinks polynomially with the number of parameter values. [sent-24, score-1.47]

11 Both solutions are highly sub-optimal, particularly, if a large number of parameter values are involved – the ﬁrst due to the lower privacy budget, and the second due to less data. [sent-26, score-0.478]

12 Thus the challenge is to design a differentially private validation procedure that uses the data and the privacy budget effectively, but can still do parameter-tuning. [sent-27, score-1.72]

13 In this paper, we show that it is indeed possible to do effective parameter-tuning with differential privacy in a fairly general setting, provided the training algorithm and the performance measure used to evaluate its output on the validation data together obey a certain stability condition. [sent-29, score-1.043]

14 The second condition is fairly standard, and our key insight is in characterizing the ﬁrst condition and showing that it can help in differentially private parameter tuning. [sent-31, score-1.017]

15 We next design a generic differentially private training and validation procedure that provides endto-end privacy provided this stability condition holds. [sent-32, score-1.933]

16 The training set size and the privacy budget used by our training algorithms are independent of k, the number of parameter values, and the accuracy of our validation procedure degrades only logarithmically with k. [sent-33, score-0.999]

17 We apply our generic procedure to two fundamental tasks in machine-learning and statistics – training a linear classiﬁer using regularized convex optimization, and building a histogram density estimator. [sent-34, score-0.341]

18 We prove that existing differentially private algorithms for these problems obey our notion of stability with respect to standard validation performance measures, and we show how to combine them to provide end-to-end differentially private solutions for these tasks. [sent-35, score-2.243]

19 In particular, our application to linear classiﬁcation is based on existing differentially private procedures for regularized convex optimization due to [4], and our application to histogram density estimation is based on the algorithm variant due to [19]. [sent-36, score-1.151]

20 In our experiments, even for a moderate value of k, our procedure outperformed existing differentially private solutions for parameter tuning, and achieved performance only slightly worse than knowing the best parameter to use ahead of time. [sent-38, score-1.066]

21 In particular, our case study on linear classiﬁcation is based on existing differentially private procedures for regularized convex optimization, which were proposed by [4], and extended by [23, 18, 15]. [sent-42, score-1.007]

22 There has also been a large body of work on differentially private histogram construction in the statistics, algorithms and database literature [7, 19, 27, 28, 20, 29, 14]. [sent-43, score-1.002]

23 While the problem of differentially private parameter tuning has been mentioned in several works, to the best of our knowledge, an efﬁcient systematic solution has been elusive. [sent-45, score-0.963]

24 [28] 2 mentions ﬁnding a good bin size for a histogram using differentially private validation procedure as an open problem. [sent-48, score-1.35]

25 We adopt differential privacy as our notion of privacy. [sent-51, score-0.544]

26 Deﬁnition 1 A (randomized) algorithm A whose output lies in a domain S is said to be (α, δ)differentially private if for all measurable S ⊆ S, for all datasets D and D that differ in the value of a single individual, it is the case that: Pr(A(D) ∈ S) ≤ eα Pr(A(D ) ∈ S) + δ. [sent-52, score-0.612]

27 An algorithm is said to be α-differentially private if δ = 0. [sent-53, score-0.523]

28 Here α and δ are privacy parameters where lower α and δ imply higher privacy. [sent-54, score-0.451]

29 Differential privacy has been shown to have many desirable properties, such as robustness to side information [7] and resistance to composition attacks [11]. [sent-55, score-0.516]

30 An important property of differential privacy is that the privacy guarantees degrade gracefully if the same sensitive data is used in multiple private computations. [sent-56, score-1.56]

31 In particular, if we apply an αdifferentially private procedure k times on the same data, the result is kα-differential private as well as (α , δ)-differentially private for α = kα(eα − 1) + 2k log(1/δ)α [7, 8]. [sent-57, score-1.623]

32 These privacy composition results are the basis of existing differentially private parameter tuning procedures. [sent-58, score-1.456]

33 Typical (non-private) machine learning algorithms have one or more undetermined parameters, and standard practice is to run the machine learning algorithm for a number of different parameter values on a training set, and evaluate the outputs on a separate held-out validation dataset. [sent-60, score-0.375]

34 Our goal in this paper is to design a differentially private version of this procedure which uses the privacy budget efﬁciently. [sent-63, score-1.486]

35 The full validation process thus has two components – a training procedure, and a validation score which evaluates how good the training procedure is. [sent-64, score-0.771]

36 We assume that training and validation data are drawn from a domain X , and the result of the differentially private training algorithm lies in a domain C. [sent-65, score-1.358]

37 A differentially private training procedure is a randomized algorithm, which takes as input a (sensitive) training dataset, a parameter (of the training procedure), and a privacy parameter α and outputs an element of C; the procedure is expected to be α-differentially private. [sent-68, score-1.851]

38 Observe that any differentially private algorithm can be represented as such a tuple. [sent-71, score-0.936]

39 , xn ∈ [0, 1], an α-differentially private approximation to the sample mean x is x + ¯ ¯ 1 αn Z where Z is drawn from the standard Laplace distribution. [sent-75, score-0.558]

40 A validation score is a function q : C × X m → R which takes an object h in C and a validation dataset V , and outputs a score which reﬂects the quality of h with respect to V . [sent-81, score-0.61]

41 3 Stability and Generic Validation Procedure We now introduce and discuss our notion of stability, and provide a generic validation procedure that uses the privacy budget efﬁciently when this notion of stability holds. [sent-84, score-0.921]

42 Deﬁnition 2 ((β1 , β2 , δ)-Stability) A validation score q is said to be (β1 , β2 , δ)-stable with respect to a training procedure T = (G, F ), a privacy parameter α, and a parameter set Θ if the following holds. [sent-85, score-0.948]

43 m Condition (1), the training stability condition, bounds the change in the validation score q, when one person’s private data in the training set T changes, and the validation set V as well as the value of the random variable R remains the same. [sent-90, score-1.377]

44 Our validation procedure critically relies on this condition, and our main contribution in this paper is to identify and exploit it to provide a validation procedure that uses the privacy budget efﬁciently. [sent-91, score-1.072]

45 As F (T, θ, α, R) is a deterministic function, Condition (2), the validation stability condition, bounds the change in q when one person’s private data in the validation set V changes, and the output of the training procedure remains the same. [sent-92, score-1.31]

46 First, observe that Condition (1) is a property of the differentially private training algorithm (in addition to q and the non-private quantity being approximated). [sent-95, score-1.049]

47 Even if all else remains the same, different differentially private approximations to the same non-private quantity will have different values of β1 . [sent-96, score-0.936]

48 Second, Condition (1) does not always hold for small β1 as an immediate consequence of differential privacy of the training procedure. [sent-97, score-0.638]

49 1, we present an example of a problem and two α-differentially private training algorithms which approximately optimize the same function; the ﬁrst algorithm is based on exponential mechanism, and the second on a maximum of Laplace random variables mechanism. [sent-100, score-0.617]

50 We show that while both provide α-differential privacy guarantees, the ﬁrst algorithm does not satisfy training stability for β1 = o(n) and small enough δ while the second one ensures training stability for β1 = 1 and δ = 0. [sent-101, score-0.913]

51 In Section 4, we present two case studies of commonly used differentially private algorithms where Conditions (1) and (2) hold for constant β1 and β2 . [sent-102, score-0.936]

52 When the (β1 , β2 , δ)-stability condition holds, we can design an end-to-end differentially private parameter tuning algorithm, which is shown in Algorithm 2. [sent-103, score-0.99]

53 , θk }, training procedure T = (G, F ), validation score q, 2: 3: 4: 5: 6: 7: training set T , validation set V , stability parameters β1 and β2 , training privacy parameter α1 , validation privacy parameter α2 . [sent-110, score-2.192]

54 Algorithm 1 takes as input a training procedure T , a parameter list Θ, a validation score q, training and validation datasets T and V , and privacy parameters α1 and α2 . [sent-119, score-1.269]

55 It runs the training procedure T on the same training set T with privacy budget α1 for each parameter in Θ to generate outputs h1 , h2 , . [sent-120, score-0.785]

56 , and then uses an α2 -differentially private procedure to select the index i∗ such that the validation score q(hi∗ , V ) is (approximately) maximum. [sent-123, score-0.872]

57 , θk }, training procedure T = (G, F ), validation score q, training set T , validation set V , stability parameters β1 and β2 , training privacy parameter α1 , validation privacy parameter α2 . [sent-129, score-2.192]

58 1 Performance Guarantees Theorem 1 shows that Algorithm 1 is (α2 , δ)-differentially private, and Theorem 2 shows privacy guarantees on Algorithm 2. [sent-134, score-0.473]

59 Theorem 1 (Privacy Guarantees for Validation Procedure) If the validation score q is δ (β1 , β2 , k )-stable with respect to the training procedure T , the privacy parameter α1 and the parameter set Θ, then, Algorithm 1 guarantees (α2 , δ)-differential privacy. [sent-137, score-0.97]

60 , hk be the output of the differentially private training procedure in Step (3) of Algorithm 1. [sent-143, score-1.118]

61 α2 4 Case Studies We next show that Algorithm 2 may be applied to design end-to-end differentially private training and validation procedures for two fundamental statistical and machine-learning tasks – training a linear classiﬁer, and building a histogram density estimator. [sent-145, score-1.524]

62 In each case, we use existing differentially private algorithms and validation scores for these tasks. [sent-146, score-1.17]

63 We show that the validation score satisﬁes the (β1 , β2 , δ)-stability property with respect to the training procedure for small values of β1 and 5 β2 , and thus we can apply in Algorithm 2 with a small value of β to obtain end-to-end differential privacy. [sent-147, score-0.536]

64 [4] present two algorithms for computing differentially private approximations to these regularized convex optimization problems for ﬁxed λ: output perturbation and objective perturbation. [sent-160, score-1.06]

65 Thus we can use Algorithm 2 along with this training procedure 6 and any L-Lipschitz validation score to get an end-to-end differentially private algorithm for linear classiﬁcation. [sent-180, score-1.379]

66 Theorem 4 (Stability of differentially private linear classiﬁers) Let Λ = {λ1 , . [sent-181, score-0.936]

67 The Methods Each method takes input (α, Θ, T, V ), where α denotes the allowed differential privacy, T is a training set, V is a validation set, and Θ = {θ1 , . [sent-192, score-0.421]

68 01, average negative ramp loss used as validation score q, and with α1 = α2 = α/2. [sent-198, score-0.352]

69 The four other methods work by performing the following 4 steps: (1) for each θi ∈ Θ, train a differentially private classiﬁer fi = oplr (αi , θi , Ti ), (2) determine the number of errors ei each fi makes on validation set V , (3) randomly choose i∗ from {1, 2, . [sent-199, score-1.266]

70 The three other alternative methods are differentially private which we state in the following theorem. [sent-209, score-0.936]

71 Random is α differentially private even if T and V are not disjoint, in which case alphaSplit and dataSplit are 2α-differentially private. [sent-211, score-0.936]

72 By Theorems 2 and 5, all methods except Control produce 7 a (α, δ)-differentially private classiﬁer. [sent-225, score-0.523]

73 Figure 1: A summary of 10 times 10-fold cross-validation experiments for different privacy levels α. [sent-272, score-0.451]

74 Results Figure 1 summarizes classiﬁer performances and regularizer choices for the different values of the privacy parameter α, aggregated over all cross-validation runs. [sent-276, score-0.508]

75 For MSE on the other hand, Stability outperformed the differentially private alternatives in all experiments. [sent-281, score-0.958]

76 Boosting the accuracy of differentially private histograms through consistency. [sent-371, score-0.936]

77 Differentially private projected histograms: Construction and use for prediction. [sent-443, score-0.523]

78 1 Appendix An Example to Show Training Stability is not a Direct Consequence of Differential Privacy We now present an example to illustrate that training stability is a property of the training algorithm and not a direct consequence of differential privacy. [sent-459, score-0.418]

79 We present a problem and two α-differentially private training algorithms which approximately optimize the same function; the ﬁrst algorithm is based on exponential mechanism, and the second on a maximum of Laplace random variables mechanism. [sent-460, score-0.617]

80 We show that while both provide α-differential privacy guarantees, the ﬁrst algorithm does not satisfy training stability while the second one does. [sent-461, score-0.682]

81 Given a sensitive dataset D, the private training procedure A outputs a tuple (i∗ , t1 , . [sent-467, score-0.735]

82 , tl ), where i∗ is the output of the α/2-differentially private exponential mechanism [21] run to approximately maximize f (D, i), and each ti is equal to 2l f (D, i) plus an independent Laplace random variable with standard deviation αn . [sent-470, score-0.651]

83 Case Study: Histogram Density Estimation Our second case study is developing an end-to-end differentially private solution for histogrambased density estimation. [sent-513, score-1.014]

84 In a histogram density estimator, we divide the range of the data into equal-sized bins of width h; if ni out of n of the input 1/h ni ˆ ˆ samples lie in bin i, then f is the density function: f (x) = i=1 hn · 1(x ∈ Bin i). [sent-518, score-0.484]

85 However, the choice of h is usually data-dependent, and in practice, the optimal h is often determined by building a histogram density estimator for a few different values of h, and selecting the one which has the best performance on held-out validation data. [sent-521, score-0.406]

86 Given n samples and a bin size h, several works, including [7, 19, 27, 28, 20, 29, 14] have shown different ways of constructing and sampling from differentially private histograms. [sent-535, score-0.996]

87 Algorithm 5 presents a variant of a differentially private histogram density estimator due to [19] in our framework. [sent-537, score-1.108]

88 Deﬁne: ni = j=1 1(xj ∈ Ii ), and let ni = max 0, ni + h 5: end for 1/h ni ˜ ˆ 6: Let n = i ni . [sent-547, score-0.505]

89 The following theorem shows stability guarantees on the differentially private histogram density estimator described in Algorithm 5. [sent-549, score-1.298]

90 Our proofs involve ideas similar to those in the analysis of the multiplicative weights update method for answering a set of linear queries in a differentially private manner [13]. [sent-557, score-0.936]

91 Let A(D) denote the output of Algorithm 1 when the input is a sensitive dataset D = (T, V ), where T is the training part and V is the validation part. [sent-558, score-0.382]

92 P ROOF :(Of Theorem 2) The proof of Theorem 2 follows from privacy composition; Theorem 1 ensures that Step (2) of Algorithm 2 is (α2 , δ)-differentially private; moreover the training procedure T is α1 -differentially private. [sent-631, score-0.599]

93 We observe that for ﬁxed λ, α and R, F (T, λ, α, R) − F (T , λ, α, R) = w∗ (T ) − w∗ (T ) When the training sets are T and T , the objective functions in the regularized convex optimization 1 problems are both λ-strongly convex, and they differ by n ( (w, xn , yn )− (w, xn , yn )). [sent-640, score-0.341]

94 , zm } be a validation dataset, and let V be a validation dataset that differs from V in a single sample (zm vs zm ). [sent-672, score-0.538]

95 We ﬁx a bin size h, a value of α, and a sequence R, and for these ﬁxed values, we use the notation ni and ni to denote the ˜ ˜ value of ni in Algorithm 5 when the inputs are T and T respectively. [sent-680, score-0.393]

96 From standard composition of privacy it follows that (a) in alphaSplit is α-differentially private. [sent-728, score-0.493]

97 Since a single change in V can change the number of errors any ﬁxed classiﬁer can make by at most 1 = ∆, we get that task (b) is α-differentially private for = α/2. [sent-730, score-0.523]

98 If T and V are not disjoint, by standard composition of privacy we get that both alphaSplit and dataSplit yield 2α-differential privacy. [sent-732, score-0.493]

99 We can therefore simulate Random by ﬁrst choosing i∗ uniformly at random, and then computing fi at α-differential privacy, which by standard privacy composition is α-differentially private. [sent-736, score-0.513]

100 0 alpha q Stability alphaSplit dataSplit Random Control Figure 2: A summary of 10 times 10-fold cross-validation selection of regularizer index i into Θ for different privacy levels α. [sent-750, score-0.501]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('private', 0.523), ('privacy', 0.451), ('differentially', 0.413), ('validation', 0.234), ('pr', 0.2), ('stability', 0.137), ('alphasplit', 0.113), ('rj', 0.106), ('ni', 0.101), ('training', 0.094), ('datasplit', 0.093), ('differential', 0.093), ('roof', 0.092), ('zj', 0.084), ('supj', 0.084), ('gmax', 0.082), ('density', 0.078), ('zi', 0.077), ('nb', 0.073), ('ri', 0.072), ('laplace', 0.07), ('histogram', 0.066), ('score', 0.061), ('bin', 0.06), ('hi', 0.056), ('differ', 0.055), ('magic', 0.054), ('procedure', 0.054), ('adult', 0.053), ('ti', 0.05), ('auc', 0.048), ('classi', 0.048), ('labelled', 0.045), ('budget', 0.045), ('ga', 0.043), ('composition', 0.042), ('perturbation', 0.041), ('fa', 0.04), ('na', 0.039), ('ramp', 0.036), ('xn', 0.035), ('dj', 0.035), ('zm', 0.035), ('output', 0.034), ('equation', 0.034), ('zk', 0.033), ('theorem', 0.031), ('etz', 0.031), ('hmin', 0.031), ('oplr', 0.031), ('inputs', 0.03), ('regularizer', 0.03), ('er', 0.029), ('event', 0.028), ('estimator', 0.028), ('regularized', 0.028), ('yn', 0.027), ('parameter', 0.027), ('apriori', 0.027), ('argminw', 0.027), ('lemma', 0.027), ('condition', 0.027), ('rl', 0.027), ('rd', 0.025), ('ei', 0.025), ('person', 0.024), ('tuple', 0.024), ('chaudhuri', 0.024), ('yi', 0.023), ('mechanism', 0.023), ('side', 0.023), ('logistic', 0.023), ('dwork', 0.022), ('guarantees', 0.022), ('procedures', 0.022), ('outperformed', 0.022), ('pi', 0.022), ('disjoint', 0.022), ('tl', 0.021), ('dx', 0.021), ('ers', 0.021), ('holds', 0.021), ('hinge', 0.021), ('convex', 0.021), ('loss', 0.021), ('cryptographically', 0.021), ('indiciate', 0.021), ('ise', 0.021), ('jitter', 0.021), ('sensitive', 0.02), ('fi', 0.02), ('list', 0.02), ('outputs', 0.02), ('mcsherry', 0.02), ('explosion', 0.02), ('alpha', 0.02), ('mse', 0.02), ('zs', 0.019), ('observe', 0.019), ('dk', 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999964 14 nips-2013-A Stability-based Validation Procedure for Differentially Private Machine Learning

Author: Kamalika Chaudhuri, Staal A. Vinterbo

2 0.59100688 177 nips-2013-Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation

Author: John Duchi, Martin J. Wainwright, Michael Jordan

Abstract: We provide a detailed study of the estimation of probability distributions— discrete and continuous—in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental trade-offs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efﬁciency continuum. One of the consequences of our results is that Warner’s classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents. 1

3 0.44331995 2 nips-2013-(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings

Author: Abhradeep Guha Thakurta, Adam Smith

Abstract: We give differentially private algorithms for a large class of online learning algorithms, in both the full information and bandit settings. Our algorithms aim to minimize a convex loss function which is a sum of smaller convex loss terms, one for each data point. To design our algorithms, we modify the popular mirror descent approach, or rather a variant called follow the approximate leader. The technique leads to the ﬁrst nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work (due to Dwork, Naor, Pitassi and Rothblum (2010) and Jain, Kothari and Thakurta (2012)). In many cases, our algorithms (in both settings) match the dependence on the input length, T , of the optimal nonprivate regret bounds up to logarithmic factors in T . Our algorithms require logarithmic space and update time. 1

4 0.27167112 102 nips-2013-Efficient Algorithm for Privately Releasing Smooth Queries

Author: Ziteng Wang, Kai Fan, Jiaqi Zhang, Liwei Wang

Abstract: We study differentially private mechanisms for answering smooth queries on databases consisting of data points in Rd . A K-smooth query is speciﬁed by a function whose partial derivatives up to order K are all bounded. We develop an -differentially private mechanism which for the class of K-smooth queries has K accuracy O(n− 2d+K / ). The mechanism ﬁrst outputs a summary of the database. To obtain an answer of a query, the user runs a public evaluation algorithm which contains no information of the database. Outputting the summary runs in time d O(n1+ 2d+K ), and the evaluation algorithm for answering a query runs in time d+2+ 2d K ˜ O(n 2d+K ). Our mechanism is based on L∞ -approximation of (transformed) smooth functions by low degree even trigonometric polynomials with small and efﬁciently computable coefﬁcients. 1

5 0.14003403 25 nips-2013-Adaptive Anonymity via $b$-Matching

Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang

Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results conﬁrm improved utility on benchmark and social data-sets.

6 0.10657256 309 nips-2013-Statistical Active Learning Algorithms

7 0.065733723 228 nips-2013-Online Learning of Dynamic Parameters in Social Networks

8 0.064713798 68 nips-2013-Confidence Intervals and Hypothesis Testing for High-Dimensional Statistical Models

9 0.06410981 52 nips-2013-Bayesian inference as iterated random functions with applications to sequential inference in graphical models

10 0.06375891 129 nips-2013-Generalized Random Utility Models with Multiple Types

11 0.058882874 269 nips-2013-Regression-tree Tuning in a Streaming Setting

12 0.050724249 75 nips-2013-Convex Two-Layer Modeling

13 0.050664969 90 nips-2013-Direct 0-1 Loss Minimization and Margin Maximization with Boosting

14 0.050561391 201 nips-2013-Multi-Task Bayesian Optimization

15 0.047375515 171 nips-2013-Learning with Noisy Labels

16 0.04702713 63 nips-2013-Cluster Trees on Manifolds

17 0.046054199 150 nips-2013-Learning Adaptive Value of Information for Structured Prediction

18 0.045209229 216 nips-2013-On Flat versus Hierarchical Classification in Large-Scale Taxonomies

19 0.044838402 144 nips-2013-Inverse Density as an Inverse Problem: the Fredholm Equation Approach

20 0.042807668 91 nips-2013-Dirty Statistical Models

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.16), (1, 0.022), (2, 0.105), (3, -0.113), (4, 0.077), (5, 0.059), (6, -0.021), (7, -0.004), (8, 0.064), (9, 0.458), (10, 0.24), (11, -0.078), (12, -0.244), (13, 0.349), (14, -0.072), (15, 0.167), (16, 0.137), (17, -0.061), (18, 0.019), (19, -0.044), (20, 0.164), (21, -0.06), (22, 0.095), (23, -0.052), (24, 0.021), (25, 0.037), (26, 0.131), (27, -0.03), (28, 0.027), (29, 0.034), (30, -0.06), (31, 0.014), (32, -0.029), (33, 0.009), (34, 0.022), (35, -0.018), (36, -0.047), (37, -0.057), (38, -0.01), (39, -0.008), (40, -0.02), (41, 0.034), (42, 0.067), (43, -0.014), (44, 0.003), (45, -0.028), (46, 0.038), (47, -0.042), (48, -0.027), (49, -0.028)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93922335 14 nips-2013-A Stability-based Validation Procedure for Differentially Private Machine Learning

Author: Kamalika Chaudhuri, Staal A. Vinterbo

2 0.88215041 177 nips-2013-Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation

Author: John Duchi, Martin J. Wainwright, Michael Jordan

3 0.75351298 102 nips-2013-Efficient Algorithm for Privately Releasing Smooth Queries

Author: Ziteng Wang, Kai Fan, Jiaqi Zhang, Liwei Wang

4 0.57756442 2 nips-2013-(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings

Author: Abhradeep Guha Thakurta, Adam Smith

5 0.5692783 25 nips-2013-Adaptive Anonymity via $b$-Matching

Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang

6 0.28754875 142 nips-2013-Information-theoretic lower bounds for distributed statistical estimation with communication constraints

7 0.26819733 80 nips-2013-Data-driven Distributionally Robust Polynomial Optimization

8 0.25776955 110 nips-2013-Estimating the Unseen: Improved Estimators for Entropy and other Properties

9 0.25226751 199 nips-2013-More data speeds up training time in learning halfspaces over sparse vectors

10 0.23758315 52 nips-2013-Bayesian inference as iterated random functions with applications to sequential inference in graphical models

11 0.22804342 63 nips-2013-Cluster Trees on Manifolds

12 0.22213495 144 nips-2013-Inverse Density as an Inverse Problem: the Fredholm Equation Approach

13 0.21938342 68 nips-2013-Confidence Intervals and Hypothesis Testing for High-Dimensional Statistical Models

14 0.20930293 358 nips-2013-q-OCSVM: A q-Quantile Estimator for High-Dimensional Distributions

15 0.20265666 111 nips-2013-Estimation, Optimization, and Parallelism when Data is Sparse

16 0.2015937 223 nips-2013-On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation

17 0.20096287 31 nips-2013-Adaptivity to Local Smoothness and Dimension in Kernel Regression

18 0.20082293 134 nips-2013-Graphical Models for Inference with Missing Data

19 0.2002811 244 nips-2013-Parametric Task Learning

20 0.19996282 309 nips-2013-Statistical Active Learning Algorithms

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(2, 0.031), (16, 0.055), (33, 0.115), (34, 0.114), (41, 0.013), (46, 0.01), (49, 0.041), (56, 0.097), (70, 0.064), (76, 0.232), (85, 0.04), (89, 0.041), (93, 0.041), (95, 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.82910401 261 nips-2013-Rapid Distance-Based Outlier Detection via Sampling

Author: Mahito Sugiyama, Karsten Borgwardt

Abstract: Distance-based approaches to outlier detection are popular in data mining, as they do not require to model the underlying probability distribution, which is particularly challenging for high-dimensional data. We present an empirical comparison of various approaches to distance-based outlier detection across a large number of datasets. We report the surprising observation that a simple, sampling-based scheme outperforms state-of-the-art techniques in terms of both efﬁciency and effectiveness. To better understand this phenomenon, we provide a theoretical analysis why the sampling-based approach outperforms alternative methods based on k-nearest neighbor search. 1

2 0.79624623 359 nips-2013-Σ-Optimality for Active Learning on Gaussian Random Fields

Author: Yifei Ma, Roman Garnett, Jeff Schneider

Abstract: A common classiﬁer for unlabeled nodes on undirected graphs uses label propagation from the labeled nodes, equivalent to the harmonic predictor on Gaussian random ﬁelds (GRFs). For active learning on GRFs, the commonly used V-optimality criterion queries nodes that reduce the L2 (regression) loss. V-optimality satisﬁes a submodularity property showing that greedy reduction produces a (1 − 1/e) globally optimal solution. However, L2 loss may not characterise the true nature of 0/1 loss in classiﬁcation problems and thus may not be the best choice for active learning. We consider a new criterion we call Σ-optimality, which queries the node that minimizes the sum of the elements in the predictive covariance. Σ-optimality directly optimizes the risk of the surveying problem, which is to determine the proportion of nodes belonging to one class. In this paper we extend submodularity guarantees from V-optimality to Σ-optimality using properties speciﬁc to GRFs. We further show that GRFs satisfy the suppressor-free condition in addition to the conditional independence inherited from Markov random ﬁelds. We test Σoptimality on real-world graphs with both synthetic and real data and show that it outperforms V-optimality and other related methods on classiﬁcation. 1

same-paper 3 0.78280663 14 nips-2013-A Stability-based Validation Procedure for Differentially Private Machine Learning

Author: Kamalika Chaudhuri, Staal A. Vinterbo

4 0.77293628 115 nips-2013-Factorized Asymptotic Bayesian Inference for Latent Feature Models

Author: Kohei Hayashi, Ryohei Fujimaki

Abstract: This paper extends factorized asymptotic Bayesian (FAB) inference for latent feature models (LFMs). FAB inference has not been applicable to models, including LFMs, without a speciﬁc condition on the Hessian matrix of a complete loglikelihood, which is required to derive a “factorized information criterion” (FIC). Our asymptotic analysis of the Hessian matrix of LFMs shows that FIC of LFMs has the same form as those of mixture models. FAB/LFMs have several desirable properties (e.g., automatic hidden states selection and parameter identiﬁability) and empirically perform better than state-of-the-art Indian Buffet processes in terms of model selection, prediction, and computational efﬁciency. 1

5 0.75311446 250 nips-2013-Policy Shaping: Integrating Human Feedback with Reinforcement Learning

Author: Shane Griffith, Kaushik Subramanian, Jonathan Scholz, Charles Isbell, Andrea L. Thomaz

Abstract: A long term goal of Interactive Reinforcement Learning is to incorporate nonexpert human feedback to solve complex tasks. Some state-of-the-art methods have approached this problem by mapping human information to rewards and values and iterating over them to compute better control policies. In this paper we argue for an alternate, more effective characterization of human feedback: Policy Shaping. We introduce Advise, a Bayesian approach that attempts to maximize the information gained from human feedback by utilizing it as direct policy labels. We compare Advise to state-of-the-art approaches and show that it can outperform them and is robust to infrequent and inconsistent human feedback.

6 0.67542851 149 nips-2013-Latent Structured Active Learning

7 0.67432272 102 nips-2013-Efficient Algorithm for Privately Releasing Smooth Queries

8 0.66239727 121 nips-2013-Firing rate predictions in optimal balanced networks

9 0.658948 262 nips-2013-Real-Time Inference for a Gamma Process Model of Neural Spiking

10 0.65748602 141 nips-2013-Inferring neural population dynamics from multiple partial recordings of the same neural circuit

11 0.65563542 49 nips-2013-Bayesian Inference and Online Experimental Design for Mapping Neural Microcircuits

12 0.65524727 15 nips-2013-A memory frontier for complex synapses

13 0.65255386 56 nips-2013-Better Approximation and Faster Algorithm Using the Proximal Average

14 0.65254861 173 nips-2013-Least Informative Dimensions

15 0.652031 350 nips-2013-Wavelets on Graphs via Deep Learning

16 0.65142083 86 nips-2013-Demixing odors - fast inference in olfaction

17 0.65127337 5 nips-2013-A Deep Architecture for Matching Short Texts

18 0.64930362 238 nips-2013-Optimistic Concurrency Control for Distributed Unsupervised Learning

19 0.64899707 101 nips-2013-EDML for Learning Parameters in Directed and Undirected Graphical Models

20 0.6483314 97 nips-2013-Distributed Submodular Maximization: Identifying Representative Elements in Massive Data