Optimal Attack Strategies Against Predictors - Learning From Expert Advice
Optimal Attack Strategies Against Predictors - Learning From Expert Advice
复制标题
针对预测变量的最佳攻击策略 - 向专家建议学习
DOI：
--
复制
发表时间：
2018
影响因子：
6.8
通讯作者：
N. Kiyavash
中科院分区：
文献类型：
--
作者：
A. Truong;S. Rasoul Etesami;Jalal Etesami;N. Kiyavash
受推荐系统或传感器融合等实际应用的启发，针对恶意专家故意降低学习系统性能的影响，分析了专家建议学习框架中加权平均预测算法的最优对抗策略。除了一个专家外，所有专家都是诚实的，恶意专家的目标是通过策略性地提供不诚实的建议来破坏算法的性能。我们制定了一个马尔可夫决策过程的问题，并在各种设置下进行分析。对于对数损失，有点令人惊讶的是，我们证明了对手的最佳策略是贪婪策略，即，每一步都在撒谎对于绝对损失，在2-专家，折扣成本设置，我们证明了最优策略是一个阈值政策，恶意的专家说实话，直到他赢得足够的权重，然后说谎。我们将结果推广到无限时域问题，并找到了稳态最优策略的精确阈值。最后，我们使用平均场的方法在$N$专家设置找到最优策略时，诚实的专家的预测是独立和同分布的。我们证明我们的结果在本文中使用模拟。
Motivated by many real-world examples, such as recommendation systems or sensor fusion, and aiming to capture the influence of malicious experts who intentionally degrade the performance of learning systems, we analyze optimal adversarial strategies against the weighted average prediction algorithm in the learning with expert advice framework. All but one expert is honest and the malicious expert’s goal is to sabotage the performance of the algorithm by strategically providing dishonest recommendations. We formulate the problem as a Markov decision process and analyze it under various settings. For the logarithmic loss, somewhat surprisingly, we prove that the optimal strategy for the adversary is the greedy policy, i.e., lying at every step. For the absolute loss, in the 2-experts, discounted cost setting, we prove that the optimal strategy is a threshold policy, where the malicious expert tells the truth until he earns enough weight and then lies afterwards. We extend the results to the infinite horizon problem and find the exact thresholds for the stationary optimal policy. Finally, we use a mean field approach in the $N$ -experts setting to find the optimal strategy when the predictions of the honest experts are independent and identically distributed. We justify our results using simulations throughout this paper.