论文标题
划分的最小二乘
Partitioned Least Squares
论文作者
论文摘要
在本文中，我们提出了一个线性最小二乘模型的变体，使从业者可以将输入特征分为变量组，以使其对最终结果类似贡献。该输出允许从业人员评估每个组和组中每个变量的重要性。我们正式表明，新公式不是凸的，并且提供了解决问题的两种替代方法：一种基于交替的最小二乘方法的一种非杰出方法；以及一种基于对问题的重新制定的确切方法，使用指数数的子问题数量，其最低限度保证为最佳解决方案。我们正式显示了确切方法的正确性，还比较了两个解决方案，表明确切的解决方案在交替的最小二乘解决方案所需的一小部分时间内提供了更好的结果（假设分区的数量很少）。为了完整性，我们还提供了一种替代分支和界限算法，当分区的数量太大时，可以代替确切方法，并且证明了本文介绍的优化问题的NP完整性证明。
In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. The output allows practitioners to assess the importance of each group and of each variable in the group. We formally show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem using an exponential number of sub-problems whose minimum is guaranteed to be the optimal solution. We formally show the correctness of the exact method and also compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (assuming that the number of partitions is small). For the sake of completeness, we also provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large, and a proof of NP-completeness of the optimization problem introduced in this paper.
