Differentially Private Data Publishing and Analysis: A Survey <s> Supervised Learning <s> We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is Σ ieS f(d i ), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise -- much less than the sampling error -- provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large.We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11]. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Supervised Learning <s> In this paper, we study the problem of constructing private classifiers using decision trees, within the framework of differential privacy. We first present experimental evidence that creating a differentially private ID3 tree using differentially private low-level queries does not simultaneously provide good privacy and good accuracy, particularly for small datasets. ::: ::: In search of better privacy and accuracy, we then present a differentially private decision tree ensemble algorithm based on random decision trees. We demonstrate experimentally that this approach yields good prediction while maintaining good privacy, even for small datasets. We also present differentially private extensions of our algorithm to two settings: (1) new data is periodically appended to an existing database and (2) the database is horizontally or vertically partitioned between multiple users. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Supervised Learning <s> Understand the need for analyses of large, complex, information-rich data sets. Identify the goals and primary tasks of the data-mining process. Describe the roots of data-mining technology. Recognize the iterative character of a data-mining process and specify its basic steps. Explain the influence of data quality on a data-mining process. Establish the relation between data warehousing and data mining. Data mining is an iterative process within which progress is defined by discovery, through either automatic or manual methods. Data mining is most useful in an exploratory analysis scenario in which there are no predetermined notions about what will constitute an "interesting" outcome. Data mining is the search for new, valuable, and nontrivial information in large volumes of data. It is a cooperative effort of humans and computers. Best results are achieved by balancing the knowledge of human experts in describing problems and goals with the search capabilities of computers. In practice, the two primary goals of data mining tend to be prediction and description. Prediction involves using some variables or fields in the data set to predict unknown or future values of other variables of interest. Description, on the other hand, focuses on finding patterns describing the data that can be interpreted by humans. Therefore, it is possible to put data-mining activities into one of two categories: Predictive data mining, which produces the model of the system described by the given data set, or Descriptive data mining, which produces new, nontrivial information based on the available data set. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Supervised Learning <s> We consider the problem of data mining with formal privacy guarantees, given a data access interface based on the differential privacy framework. Differential privacy requires that computations be insensitive to changes in any particular individual's record, thereby restricting data leaks through the results. The privacy preserving interface ensures unconditionally safe access to the data and does not require from the data miner any expertise in privacy. However, as we show in the paper, a naive utilization of the interface to construct privacy preserving data mining algorithms could lead to inferior data mining results. We address this problem by considering the privacy and the algorithmic requirements simultaneously, focusing on decision tree induction as a sample application. The privacy mechanism has a profound effect on the performance of the methods chosen by the data miner. We demonstrate that this choice could make the difference between an accurate classifier and a completely useless one. Moreover, an improved algorithm can achieve the same level of accuracy and privacy as the naive implementation but with an order of magnitude fewer learning samples. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Supervised Learning <s> Privacy-preserving data mining has become an active focus of the research community in the domains where data are sensitive and personal in nature. For example, highly sensitive digital repositories of medical or financial records offer enormous values for risk prediction and decision making. However, prediction models derived from such repositories should maintain strict privacy of individuals. We propose a novel random forest algorithm under the framework of differential privacy. Unlike previous works that strictly follow differential privacy and keep the complete data distribution approximately invariant to change in one data instance, we only keep the necessary statistics (e.g. variance of the estimate) invariant. This relaxation results in significantly higher utility. To realize our approach, we propose a novel differentially private decision tree induction algorithm and use them to create an ensemble of decision trees. We also propose feasible adversary models to infer about the attribute and class label of unknown data in presence of the knowledge of all other data. Under these adversary models, we derive bounds on the maximum number of trees that are allowed in the ensemble while maintaining privacy. We focus on binary classification problem and demonstrate our approach on four real-world datasets. Compared to the existing privacy preserving approaches we achieve significantly higher utility. <s> BIB005
Supervised learning refers to the prediction methods that extract models describing data classes via a set of labeled training records BIB003 . As one of the most popular supervised learning algorithms, decision tree learning, has been extensively studied in Laplace/exponential Frameworks. Decision trees are iterative processes that recursively partition the training sample to build a tree with each label representing a leaf. Assuming there is an input dataset D with d categorical attributes fa 1 ; . . . a d g, a decision tree is constructed from the root that holds all the training records then the algorithm chooses the attribute a i that maximizes the information gain to partition the records into child nodes. The procedure is performed recursively on each subset of the training records until a stop criteria is meet. The first differentially private decision tree algorithm was developed on the SuLQ platform BIB001 . Noise is added to the information gain, and an attribute a i with noisy information gain that is less than a specified threshold is chosen to partition a node. However, as information gain is evaluated separately for each attribute in each iteration, the privacy budget is consumed several times in each iteration, which results in a large volume of noise. In addition, SuLQ fails to deal with continuous attributes. If those attributes are simply discretized into intervals, the basic concept of differential privacy is violated, because the split values in continuous attributes would reveal information about the records. To overcome the SuLQ platform's disadvantages, Friedman et al. BIB004 improved the algorithm in two ways. First, they implemented an exponential mechanism in the attribute selection step. The score function is defined by the information gain or the gain ratio. The attributes with a top score have a higher probability of being selected. In this way, less of the privacy budget is consumed than by SuLQ. Second, the proposed method can deal with continuous attributes. An exponential mechanism is employed to select every possible splitting value and the continuous attributes domain is divided into these intervals. Compared to SuLQ, they obtain better performance. Jagannatham et al. BIB002 provided an algorithm for building random private decision trees, which randomly select attributes to create nodes. The algorithm first creates a tree in which all the leaves are on the same level and then builds a leaf count vector. Once the independent Laplace noise is added to the count vector, a differentially private random decision tree can be generated from the noisy leaf vector. The algorithm iteratively produces multiple random decision trees and uses the ensemble method to combine these trees. As the attribute is randomly selected, this step saves the privacy budget; however, as each tree's magnitude is scaled up with the number of trees in the final ensemble step, the utility of the ensemble remains a problem. Rana et al. BIB005 proposed a practical approach to ensemble decision trees in a random forest. They do not strictly follow the notion of differential privacy, which keeps the neighboring data distribution approximately invariant. Instead, they only keep the statistic features invariant. A privacy attack model is defined to prove the reliability of the proposed decision tree. As less budget has been consumed in the ensemble process, this relaxation of differential privacy can lead to higher utility compared to other algorithms. Discussion. Table 11 shows a summary of differential private supervised learning methods. Differentially private decision tree algorithms were the earliest algorithms to be investigated in the differential privacy community. The advantage of this series of methods is that they are concise and easy to implement. However, because tree-based algorithms need to select split attributes multiple times, the privacy budget is quickly consumed, which incurs a huge utility loss. This drawback stems from decision tree building and is not easy to deal with. Nowadays, one of the most popular ways to design differentially private supervised learning algorithms is to apply a private learning framework, which is discussed in Section 4.2.