We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender -- an aspect that is key to realistic applications but has so far been overlooked in the literature. To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no a priori restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the set of possible data, which is itself exponential in the number of features used for classification. To counter this, we first show that Bayesian Nash equilibria can be characterized completely via functional threshold classifiers with a small number of parameters. We then show that this low-dimensional characterization enables to develop a training method to compute provably approximately optimal classifiers in a scalable manner; and to develop a learning algorithm for the online setting with low regret (both independent of the dimension of the set of possible data). We illustrate our results through simulations.
翻译:我们考虑了在敌对环境中找到最佳分类器的问题,即第1级数据是由攻击者生成的,而攻击者的目标并不为捍卫者所知 -- -- 这是现实应用的关键,但迄今在文献中被忽视。为模拟这种情况,我们提议了一个巴伊西亚游戏框架,保护者选择一个分类器,对一组可能的分类器没有先验的限制。拟议框架的关键困难在于,可能的分类器组在可能的数据组中是指数性的,而该组数据本身在分类所使用的特征数中是指数性的。对此,我们首先显示,Bayesian Nash equilibria可以通过功能阈值分类器完全定性,其参数不多。我们然后表明,这种低维度特征化能够开发一种培训方法,以可调整的方式对大约最佳的分类器进行可调整;以及开发一种对在线环境的学习算法,其作用是低遗憾的(两者都独立于一套可能的数据组的层面)。我们通过模拟来说明我们的结果。