Adversarial Classification Nilesh Dalvi Pedro Domingos Mausam Sumit Sanghai Deepak Verma KDD 04 Seattle Presented by Aditya Menon UCSD April 25 2008 Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 1 71 Outline 1 Previous supervised learning research 2 Background naive Bayes classifier Standard naive Bayes Cost sensitive classification 3 Adversary s strategy Adversary s goal Finding optimal strategy Pruning optimizations 4 Learner s strategy Learner s goal Pruning optimizations 5 Experiments 6 Critique and future work 7 Conclusion 8 References Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 2 71 Previous supervised learning research Learner typically agnostic about data producer I Assumes that data just arises naturally But is this realistic I I I Spam spammers try to fool Bayesian classifiers Intrusion detection intruder tries to cover up footprint Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 3 71 Previous supervised learning research Learner typically agnostic about data producer I Assumes that data just arises naturally But is this realistic I I I Spam spammers try to fool Bayesian classifiers Intrusion detection intruder tries to cover up footprint Reality Producer very much aware data is being classified I And can change data to fool learner Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 3 71 Example of clever producer Learner recognizes Cheap high quality Rolex 75 off November only Spammer switches to This November purchasing low cost Rolexes is simple Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 4 71 Consequences of producer intereference What happens if we ignore this fact I I I Producer can generate worst case data for classifier Classifier accuracy degrades rapidly Have to change our classifier to keep up Net result keep reconstructing classifier I Figure out how we were fooled and fix it But matter of time before malicious producer strikes again Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 5 71 Adversarial classification Realistic model treat data producer as an adversary I I Producer knows the classifier being used Tweaks data to maximize misclassification Question If we know the data will be tampered can we improve our classifier Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 6 71 It s all a game Learner and adversary are locked in a game I I I I Learner makes a prediction Adversary deduces prediction technique modifies data to breaks it Learner knows adversary s strategy changes classifier Question What is the best strategy for the Learner Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 7 71 This paper Assumes naive Bayes classifier I Important assumption hence constrains applicability Derives optimal adversary strategy Consequently derives optimal classifier strategy Shows that this has a significant impact on classifier accuracy I Spam detection application Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 8 71 Notions of optimality How do we define the best strategy In game theory I I Typically seek a Nash equilibrium neither player has an incentive to change his strategy Does not mean that either player s payoff is maximized In this paper I I I Simply a locally optimal strategy Best response to what the other player did Players constantly changing strategy based on what the other does Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 9 71 Outline 1 Previous supervised learning research 2 Background naive Bayes classifier Standard naive Bayes Cost sensitive classification 3 Adversary s strategy Adversary s goal Finding optimal strategy Pruning optimizations 4 Learner s strategy Learner s goal Pruning optimizations 5 Experiments 6 Critique and future work 7 Conclusion 8 References Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 10 71 Standard naive Bayes classifier Suppose an instance has n features x x1 x2 xn xi Xi Given an instance x probability of it having class y is P y P y x P x y P x n Y i 1 P xi y P y P x Conditional feature independence is the naive Bayes assumption Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 11 71 Standard naive Bayes classifier Suppose an instance has n features x x1 x2 xn xi Xi Given an instance x probability of it having class y is P y P y x P x y P x I n Y i 1 P xi y P y P x Conditional feature independence is the naive Bayes assumption Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 11 71 Cost sensitive prediction Paper uses the notion of the utility of a classification I UC y 0 y is the utility or benefit of predicting that something with true class y has class y 0 Then just choose the y 0 that maximizes X U y 0 x P y x UC y 0 y y Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 12 71 Optimal cost sensitive prediction Paper considers problems with two classes I I Malicious e g spam Harmless e g normal email Optimal prediction is the y 0 that maximizes U y 0 x P x UC y 0 P x UC y 0 Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 13 71 Example of a utility matrix Reasonable utility choices Actual Predicted Presented by Aditya Menon UCSD UC True positive False negative False positive True negative UC 1 1 10 1 Adversarial Classification April 25 2008 14 71 Outline 1 Previous supervised learning research 2 Background naive Bayes classifier Standard naive Bayes Cost sensitive classification 3 Adversary s strategy Adversary s goal Finding optimal strategy Pruning optimizations 4 Learner s strategy Learner s goal Pruning optimizations 5 Experiments 6 Critique and future work 7 Conclusion 8 References Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 15 71 The nature of the adversary Now suppose there is an adversary that modifies the data Adversary s goal For each example modify its feature values so that the probability they are classified as harmless increases Adversary will transform an instance x using a function A x A X1 Xn X1 Xn We need to know the nature of the optimal A x Presented by Aditya Menon UCSD Adversarial Classification April 25 2008 16 71 Adversary s limitations Why can t adversary just change every feature value I Naturally there is some notion of the cost to the adversary We suppose the adversary has a set of matrices Wi where i runs
View Full Document
Unlocking...