Probably Approximately Correct Constrained Learning
Probably Approximately Correct Constrained Learning
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Luiz F. O. Chamon;Alejandro Ribeiro
中科院分区：
文献类型：
--
作者：
Luiz F. O. Chamon;Alejandro Ribeiro
随着学习解决方案在社会，工业和医疗领域的关键应用，减少他们的行为变得至关重要。现在有充分的证据表明，如果没有明确的定制，学习可能会导致有偏见的，不安全的和有偏见的解决方案。为了解决这些问题，我们开发了一个泛化理论的约束学习的基础上可能近似正确（PAC）的学习框架。特别是，我们表明，施加的要求并没有使学习问题更难的意义上说，任何PAC学习类也PAC约束学习使用的经验风险最小化（ERM）规则的约束对应。然而，对于典型的参数化模型，该学习器涉及求解非凸优化程序，即使获得可行解也可能很难。为了克服这个问题，我们证明了在温和的条件下，约束学习的经验对偶问题也是PAC约束学习者，现在导致一个实用的约束学习算法。我们分析了这个解决方案的泛化特性，并用它来说明如何约束学习可以解决公平和鲁棒分类的问题。
As learning solutions reach critical applications in social, industrial, and medical domains, the need to curtail their behavior becomes paramount. There is now ample evidence that without explicit tailoring, learning can lead to biased, unsafe, and prejudiced solutions. To tackle these problems, we develop a generalization theory of constrained learning based on the probably approximately correct (PAC) learning framework. In particular, we show that imposing requirements does not make a learning problem harder in the sense that any PAC learnable class is also PAC constrained learnable using a constrained counterpart of the empirical risk minimization (ERM) rule. For typical parametrized models, however, this learner involves solving a non-convex optimization program for which even obtaining a feasible solution may be hard. To overcome this issue, we prove that under mild conditions the empirical dual problem of constrained learning is also a PAC constrained learner that now leads to a practical constrained learning algorithm. We analyze the generalization properties of this solution and use it to illustrate how constrained learning can address problems in fair and robust classification.