Dec, 2023
何时可以信赖特征选择?--I：基于条件的LASSO和近似难度的分析
When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation
TL;DR鉴于AI技术在计算中的应用以及其潜在的幻觉和非鲁棒性，可信度算法已经成为一个关注点。然而，对于许多经典方法的可信度仍未得到很好的理解。本文针对科学、统计学、机器学习等领域中的一个经典问题，特征选择问题，提出了LASSO优化问题。尽管它被广泛应用，但在读取近似输入时，以概率“>1/2”确定试图计算LASSO的极小值支持集的算法的输出是否可信尚未得到确立。然而，我们定义了LASSO条件数，并设计了一种可以在多项式时间内计算这些支持集的高效算法，前提是输入数据是良态的（具有有限条件数），其时间复杂度与维度和条件数的对数成多项式关系。对于病态输入，该算法将永远运行下去，因此永远不会给出错误答案。此外，当条件数有限时，该算法还计算了条件数的上界。最后，对于任何定义在包含具有无限条件数的点的开集上的算法，存在一种输入，该算法要么永远运行下去，要么给出错误答案。我们的不可能结果源于逼近的广义硬度，位于可解性复杂性指数（SCI）层次结构框架内，对逼近难度的经典现象进行了概括。