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.

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.