N1005 IBM Research: adaptive data analysis

<br /><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbCZhmeFmYySpEFoHqcxYdUYQlZ93FIdvVJ8eRrxQfoMDhraZlC6oDOmkL8SpMY44MAhAIQURebYOQU0CHfiImezdGUswFJk-JXTu9jc-sQ-VqRcjgAddKFkMSyaWk91BdJsHCcP5xygA/s1600/vfeldman.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbCZhmeFmYySpEFoHqcxYdUYQlZ93FIdvVJ8eRrxQfoMDhraZlC6oDOmkL8SpMY44MAhAIQURebYOQU0CHfiImezdGUswFJk-JXTu9jc-sQ-VqRcjgAddKFkMSyaWk91BdJsHCcP5xygA/s1600/vfeldman.jpg" /></a></div><i style="mso-bidi-font-style: normal;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial;">Editor’s note: this article is by Vitaly Feldman, research scientist at IBM Research-Almaden</span></i> </div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial;">From discovering new particles and clinical studies to predicting election results and evaluating credit scores, scientific progress and industrial innovation increasingly rely on statistical data analysis. </span><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">While incredibly useful, data analysis is also notoriously easy to misuse, even when the analyst has the best of intentions. Problems stemming from such misuse can be <a href="http://journals.plos.org/plosbiology/article?id=10.1371/journal.pbio.1002165" target="_blank">costly</a>and contribute to a wider concern about the reproducibility of research findings, most notably in medical research. The issue is <a href="http://www.nature.com/news/reproducibility-1.17552" target="_blank">hotly debated</a>in the scientific community and has attracted a lot of <a href="http://www.economist.com/news/leaders/21588069-scientific-research-has-changed-world-now-it-needs-change-itself-how-science-goes-wrong" target="_blank">public attention</a> in the <a href="http://www.nytimes.com/2014/01/21/science/new-truths-that-only-one-can-see.html?_r=1" target="_blank">recent years</a>.</span><br /><a name="more"></a><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";"> </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">In recent research with a team of computer scientists from industry and academia, I made progress in understanding and addressing some of the ways in which data analysis can go wrong. Our work, <a href="http://www.sciencemag.org/content/349/6248/636.abstract" target="_blank">Preserving Validity in Adaptive Data Analysis</a>, published this week in <i style="mso-bidi-font-style: normal;">Science</i>, deals with important, but fairly technical and subtle, statistical issues that arise in the practice of data analysis. I’ll outline them below. For the less patient, here is also an elevator-pitch description (minus the elevator) of our work in the video, below. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";"><iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/Y6eaYqciVVE" width="560"></iframe></span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">The main difficulty in obtaining valid results is that it is hard to tell whether a pattern observed in the data represents a true relationship that holds in the real world, or is merely a coincidental artifact of the randomness in the process of data collection. The standard way of expressing the confidence in a result of analysis -- such as a certain trait being correlated with a disease – is a <i style="mso-bidi-font-style: normal;">p</i>-value. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Informally, a <i style="mso-bidi-font-style: normal;">p</i>-value for a certain result measures the probability of obtaining the result in the absence of any actual relationship (referred to as the <i style="mso-bidi-font-style: normal;">null hypothesis</i>). A small <i style="mso-bidi-font-style: normal;">p</i>-value indicates high confidence in the validity of the result, with 0.05 commonly accepted as sufficient to declare a finding as being statistically significant. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">The guarantee that a <i style="mso-bidi-font-style: normal;">p</i>-value provides has a critical caveat however: it applies only if the analysis procedure was chosen before the data was examined. At the same time, the practice of data analysis goes well beyond using a predetermined analysis. New analyses are chosen on the basis of data exploration and previous analyses of a dataset, and are performed on the same dataset. While useful, such <i style="mso-bidi-font-style: normal;">adaptive</i> analysis invalidates the standard <i style="mso-bidi-font-style: normal;">p</i>-value computations. Using incorrect <i style="mso-bidi-font-style: normal;">p</i>-values is likely to lead to false discoveries. An analyst might conclude, for example, that a certain diet increases the risk of diabetes, when in reality it has no effect at all.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">The mistakes that misapplications of standard <i style="mso-bidi-font-style: normal;">p</i>-value computations cause can be easily observed using any basic data analysis tool (like MS Excel). For example, let’s create a fake dataset for a study of the effect of 50 different foods on the academic performance of students. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">For each student, the data will include a consumption level for each of the 50 foods and an (academic) grade. Let’s create the dataset consisting of 100 students by choosing all the values randomly and independently from the normal (or Gaussian) distribution. Clearly, in the true data distribution we used the food consumption, and the students’ grade are completely unrelated. A natural first step in our analysis of this dataset is to identify which foods have the highest (positive or negative) correlation with the grade. Below is an example outcome of this step in which I highlighted in red three foods with particularly strong correlations in the data. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><div class="separator" style="clear: both; text-align: center;"></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBGD9DRl-7ZeIe7Dt4NXhc1aw__aampm219cdfWSZFxEtowz7FPDddlCLzvPsj2qidD75tgKCuc_FFLAa-svBHKPImzCEIAyMmeoBWEPNKOyyunl6m25NuJhjRkSe1XOe8ndKOCeMAaQg/s1600/correlations2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="230" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBGD9DRl-7ZeIe7Dt4NXhc1aw__aampm219cdfWSZFxEtowz7FPDddlCLzvPsj2qidD75tgKCuc_FFLAa-svBHKPImzCEIAyMmeoBWEPNKOyyunl6m25NuJhjRkSe1XOe8ndKOCeMAaQg/s400/correlations2.jpg" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">click to enlarge</td></tr></tbody></table><div style="text-align: center;"><span style="font-size: x-small;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; line-height: 107%; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";"></span></span></div><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; line-height: 107%; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">A common next step would be to use the least-squares linear regression to check whether a simple linear combination of the three strongly correlated foods can predict the grade. It turns out that a little combination goes a long way: we discover that a linear combination of the three selected foods can explain a significant fraction of variance in the grade (plotted below). The regression analysis also reports that the <i style="mso-bidi-font-style: normal;">p</i>-value of this result is 0.00009 meaning that the probability of this happening purely by chance is less than 1 in 10,000.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiq1hxS9wqTMMvugQHjjMzNhy4fxjL1jShGf9Ijdp6_O31spcMO37s7nN4xA4MuIoV5cetHDLqQRtScTRFZtyAH9-rwWkmPlkKM1BgpTB1XOByHNF1sPfVedqUyM6fg1O1S7h0BHMviV_c/s1600/true.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiq1hxS9wqTMMvugQHjjMzNhy4fxjL1jShGf9Ijdp6_O31spcMO37s7nN4xA4MuIoV5cetHDLqQRtScTRFZtyAH9-rwWkmPlkKM1BgpTB1XOByHNF1sPfVedqUyM6fg1O1S7h0BHMviV_c/s1600/true.jpg" /></a></div><div style="text-align: center;"><br /></div></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Recall that no relationship exists in the true data distribution, so this discovery is clearly false. This spurious effect is known to experts as Freedman’s paradox. It arises since the variables (foods) used in the regression were chosen using the data itself.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Despite the fundamental nature of adaptivity in data analysis, little work has been done to understand and mitigate its effects on the validity of results. The only known safe approach to adaptive analysis is to use a separate <i style="mso-bidi-font-style: normal;">holdout</i> dataset to validate any finding obtained via adaptive analysis. Such an approach is standard in machine learning: a dataset is split into training and validation data, with the training set used for learning a predictor, and the validation (holdout) set used to estimate the accuracy of that predictor. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Because the predictor is independent of the holdout dataset, such an estimate is a valid estimate of the true prediction accuracy. In practice, however, the holdout dataset is rarely used only once, and the predictor often depends on the holdout data in a complicated way. Such dependence invalidates the estimates of accuracy based on the holdout set as the predictor may be <i style="mso-bidi-font-style: normal;">overfitting</i> to the holdout set.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">I’ve been working on approaches for dealing with adaptivity in machine learning for the past two years. During a chance conversation with <a href="http://www.cis.upenn.edu/~aaroth/">Aaron Roth,</a> a professor at </span><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Penn, while </span>at a big data <a href="http://simons.berkeley.edu/workshops/bigdata2013-4">workshop</a>, I found out that he and several colleagues were also working on an approach to this problem. That conversation turned into a fruitful collaboration </span><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">with Microsoft's <a href="http://research.microsoft.com/en-us/people/dwork/" target="_blank">Cynthia Dwork</a>, Google's <a href="http://www.moritzhardt.com/" target="_blank">Moritz Hardt</a>, University of Toronto's <a href="http://www.cs.toronto.edu/~toni/" target="_blank">Toni Pitassi</a>, Samsung's <a href="https://omereingold.wordpress.com/" target="_blank">Omer Reingold</a>, and Aaron. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">We found that challenges of adaptivity can be addressed using techniques developed for privacy-preserving data analysis. These techniques rely on the notion of differential privacy that guarantees that the data analysis is not too sensitive to the data of any single individual. We rigorously demonstrated that ensuring differential privacy of an analysis also guarantees that the findings will be statistically valid. We then also developed additional approaches to the problem based on a new way to measure how much information an analysis reveals about a dataset.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><b style="mso-bidi-font-weight: normal;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">The Thresholdout Algorithm</span></b></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Using our new approach we designed an algorithm, called Thresholdout, that allows an analyst to reuse the holdout set of data for validating a large number of results, even when those results are produced by an adaptive analysis. The Thresholdout algorithm is very easy to implement and is based on two key ideas. </span></div><ul><li><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">First, the validation should not reveal any information about the holdout dataset if the analyst does not overfit to the training set. </span></li><li><span style="color: black; font-family: Symbol; font-size: 13.0pt; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Second, an addition of a small amount of noise to any validation result can prevent the analyst from overfitting to the holdout set.</span></li></ul><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">To illustrate the benefits of using our approach, we showed how it prevents overfitting in a setting inspired by Freedman’s paradox. In this experiment, the analyst wants to build an algorithm that can accurately classify data points into two classes, given a dataset of correctly labeled points. The analyst first finds a set of variables that have the largest correlation with the class. However, to avoid spurious correlations, the analyst validates the correlations on the holdout set and uses only those variables whose correlation agrees with the correlation on the training set. The analyst then creates a simple linear threshold classifier on the selected variables.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">We tested this procedure on a dataset of 20,000 points in which the values of 10,000 attributes are drawn independently from the normal distribution, and the class is chosen uniformly at random. There is no correlation between the data point and its class label and no classifier can achieve true accuracy better than 50 percent. Nevertheless, reusing a standard holdout leads to reported accuracy of more than 63±0.4 percent (when selecting 500 out of 10,000 variables) on both the training set and the holdout set. </span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">We then executed the same algorithm with our Thresholdout algorithm for holdout reuse. Thresholdout prevents the algorithm from overfitting to the holdout set and gives a valid result close to 50 percent estimate of classifier accuracy. In the plot below we show the accuracy on the training set and the holdout set (the green line) obtained for various numbers of selected variables averaged over 100 independent executions. For comparison, the plot also includes the accuracy of the classifier on another fresh data set of 10,000 points which serves as the gold standard for validation.</span></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><br /></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgngEECjvv0noddVZyTsVGl3PmC4QHP-qQ0x7-t8yGoZHlac5-ym-jSbPWr_Db1byBkKDQOEt_Uyl7BwN7fAsFwIB9LeL6IM86J2AKFD8-c2C62u_COZ-Ctd1djQhTB9awJeTxMHGzVe-w/s1600/Thresholdout2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="116" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgngEECjvv0noddVZyTsVGl3PmC4QHP-qQ0x7-t8yGoZHlac5-ym-jSbPWr_Db1byBkKDQOEt_Uyl7BwN7fAsFwIB9LeL6IM86J2AKFD8-c2C62u_COZ-Ctd1djQhTB9awJeTxMHGzVe-w/s400/Thresholdout2.jpg" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">click to enlarge</td></tr></tbody></table><div class="separator" style="clear: both; text-align: center;"></div></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"></div><div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;"><span style="color: black; font-family: "Verdana",sans-serif; font-size: 13.0pt; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman";">Beyond this illustration, the reusable holdout gives the analyst a simple, general and principled method to perform multiple validation steps where previously the only known safe approach was to collect a fresh holdout set each time a function depends on the outcomes of previous validations. We are now looking forward to exploring the practical applications of this technique.</span></div><div class="MsoNormal"><br /></div>

Editor’s note: this article is by Vitaly Feldman, research scientist at IBM Research-Almaden From discovering new particles and clinical st...