We study submodular optimization in adversarial context, applicable to
machine learning problems such as feature selection using data susceptible to
uncertainties and attacks. We focus on Stackelberg games between an attacker
(or interdictor) and a defender where the attacker aims to minimize the
defender's objective of maximizing a $k$-submodular function. We allow
uncertainties arising from the success of attacks and inherent data noise, and
address challenges due to incomplete knowledge of the probability distribution
of random parameters. Specifically, we introduce Distributionally Risk-Averse
$k$-Submodular Interdiction Problem (DRA $k$-SIP) and Distributionally
Risk-Receptive $k$-Submodular Interdiction Problem (DRR $k$-SIP) along with
finitely convergent exact algorithms for solving them. The DRA $k$-SIP solution
allows risk-averse interdictor to develop robust strategies for real-world
uncertainties. Conversely, DRR $k$-SIP solution suggests aggressive tactics for
attackers, willing to embrace (distributional) risk to inflict maximum damage,
identifying critical vulnerable components, which can be used for the
defender's defensive strategies. The optimal values derived from both DRA
$k$-SIP and DRR $k$-SIP offer a confidence interval-like range for the expected
value of the defender's objective function, capturing distributional ambiguity.
We conduct computational experiments using instances of feature selection and
sensor placement problems, and Wisconsin breast cancer data and synthetic data,
respectively.

我们研究了在对抗环境中的子模规划优化问题，该问题适用于机器学习中使用容易受到不确定性和攻击的数据进行特征选择。我们关注攻击者和防御者之间的斯塔克尔伯格博弈，攻击者的目标是最小化防御者最大化的 k - 子模规函数。我们考虑攻击成功和数据噪声带来的不确定性，并解决了由于对随机参数的概率分布的不完全了解而引起的挑战。具体而言，我们引入了分布度风险厌恶 k - 子模规拦截问题（DRA k-SIP）和分布度风险接受 k - 子模规拦截问题（DRR k-SIP），并提出了针对它们的收敛精确算法。DRA k-SIP 解决方案允许风险规避的拦截者制定针对现实世界不确定性的稳健策略。相反，DRR k-SIP 解决方案提供了攻击者的进攻策略，他们愿意承担（分布）风险以造成最大的损害，并确定了关键易受攻击的组件，这可以用于防御者的防御策略。从 DRA k-SIP 和 DRR k-SIP 中得出的最优值为防御者的目标函数的期望值提供了一个类似置信区间的范围，用于捕捉分布的不确定性。我们使用特征选择和传感器放置问题的实例以及威斯康星乳腺癌数据和合成数据进行了计算实验。