ROBUST LARGE MARGIN APPROACHES FOR MACHINE LEARNING IN ADVERSARIAL SETTINGS by MOHAMADALI TORKAMANI A DISSERTATION Presented to the Department of Computer and Information Science and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Doctor of Philosophy September 2016 DISSERTATION APPROVAL PAGE Student: MohamadAli Torkamani Title: RobustLargeMarginApproachesforMachineLearninginAdversarialSettings This dissertation has been accepted and approved in partial fulfillment of the requirements for the Doctor of Philosophy degree in the Department of Computer and Information Science by: Daniel Lowd Chair Dejing Dou Core Member Christopher Wilson Core Member Hal Sadofsky Institutional Representative and Scott L. Pratt Dean of the Graduate School Original approval signatures are on file with the University of Oregon Graduate School. Degree awarded September 2016 ii (cid:13)c 2016 MohamadAli Torkamani iii DISSERTATION ABSTRACT MohamadAli Torkamani Doctor of Philosophy Department of Computer and Information Science September 2016 Title: RobustLargeMarginApproachesforMachineLearninginAdversarialSettings Many agencies are now using machine learning algorithms to make high-stake decisions. Determining the right decision strongly relies on the correctness of the input data. This fact provides tempting incentives for criminals to try to deceive machine learning algorithms by manipulating the data that is fed to the algorithms. And yet, traditional machine learning algorithms are not designed to be safe when confronting unexpected inputs. In this dissertation, we address the problem of adversarial machine learning; i.e., our goal is to build safe machine learning algorithms that are robust in the presence of noisy or adversarially manipulated data. Adversarial machine learning will be more challenging when the desired output has a complex structure. In this dissertation, a significant focus is on adversarial machine learning for predicting structured outputs. First, we develop a new algorithm that reliably performs collective classification, which is a structured prediction problem. Our learning method is efficient and is formulated as a convex quadratic program. This technique secures the prediction algorithm in both the presence and the absence of an adversary. iv Next, we investigate the problem of parameter learning for robust, structured prediction models. This method constructs regularization functions based on the limitations of the adversary. In this dissertation, we prove that robustness to adversarial manipulation of data is equivalent to some regularization for large- margin structured prediction, and vice versa. An ordinary adversary regularly either does not have enough computational power to design the ultimate optimal attack, or it does not have sufficient information about the learner’s model to do so. Therefore, it often tries to apply many random changes to the input in a hope of making a breakthrough. This fact implies that if we minimize the expected loss function under adversarial noise, we will obtain robustness against mediocre adversaries. Dropout training resembles such a noise injection scenario. We derive a regularization method for large- margin parameter learning based on the dropout framework. We extend dropout regularization to non-linear kernels in several different directions. Empirical evaluations show that our techniques consistently outperform the baselines on different datasets. This dissertation includes previously published and unpublished coauthored material. v CURRICULUM VITAE NAME OF AUTHOR: MohamadAli Torkamani GRADUATE AND UNDERGRADUATE SCHOOLS ATTENDED: University of Oregon, Eugene, OR, USA Isfahan University of Technology, Isfahan, Iran DEGREES AWARDED: Doctor of Philosophy, Computer and Information Science, 2016, University of Oregon Master of Science, Artificial Intelligence, 2006, Isfahan University of Technology AREAS OF SPECIAL INTEREST: Machine learning, Statistics, Convex Optimization, Robust Modeling PROFESSIONAL EXPERIENCE: Graduate Research & Teaching Assistant, Department of Computer and Information Science, University of Oregon, 2011 to present Research Intern, Clari, Mountain View, California, 2015 Research Intern, Comcast Labs, Washington, D.C., 2012 Research Assistant, Department of Electrical Engineering and Computer Science, Oregon State University, 2009 to 2011 GRANTS, AWARDS AND HONORS: Graduate Teaching & Research Fellowship, Computer and Information Science, 2011 to present vi PUBLICATIONS: Torkamani, M., Lowd, D. (2013). Convex Adversarial Collective Classification. In Proceedings of the 31th International Conference on Machine Learning (ICML 2014), Pages 642-650. Torkamani, M., Lowd, D. (2014). On Robustness and Regularization of Structural Support Vector Machines. In Proceedings of the 30th International Conference on Machine Learning (ICML 2013), Pages 577-585. Torkamani, M., Lowd, D. (2016). Marginalized and Kernelized Dropout Training for Support Vector Machines. Under review in Journal of Machine Learning Research (JMLR). vii ACKNOWLEDGEMENTS First and foremost I want to thank my advisor Daniel Lowd, who has given me every opportunity to pursue my ideas, and whose mentorship has shaped my development as a scientist. It has been an honor to be one of his first Ph.D. Students. I appreciate all his contributions of time, ideas, and funding to make my Ph.D. experience productive and stimulating. I would like to thank my dissertation committee members Dejing Dou, Christopher Wilson, and Hal Sadofsky. I also would like to thank Andrzej Proskurowski and Jun Li for their constructive comments in the past years. I gratefully acknowledge the funding sources, grants from the Army Research Office (ARO) and the National Science Foundation (NSF) that made my Ph.D. work possible. I have been lucky to have great friends. They were the ones who not only helped me keep my sanity but also were so generous in sharing their ideas and their expertise. I would like to thank Daniel’s past and current laboratory members whom I have been lucky to meet; especially, I would like to thank my friends Pedram Rooshenas, Jonathan Brophy, Shangpu Jiang, Brent Lessley, Mino De Raj, and David Stevens. I would like to thank my great friends inside and outside the department, in particular, Bahador Yeganeh, Ellen Klowden, Fernando Guitarez, Javid Ebrahimi, Hao Wang, Nisansa De Silva, Nhathai Phan, Reza Motamedi, Sabin Kafle, Saed Rezayi, Samuel Li, Soheil Jamshidi, and many other wonderful friends, whom I wish I could mention their names here. Lastly, I would like to thank my friends and family for all their wholehearted support and encouragement. I want to thank my parents who raised me with viii love and taught me to love science. And most of all for my loving, supportive, encouraging, and patient wife Fereshteh, whose support during my Ph.D. is so appreciated. ix To my wife, Fereshteh x