A novel low-complexity method for determining nonadditive interaction measures based on least-norm learning

Numerous research works have been done on the Choquet integral model due to the tremendous usage in many fields. However, the application is still significantly restricted by the curse of dimensionality, involved in determining the non-additive interaction measures, that can properly reflect the interactions among predictive attributes toward the objective. To this end, in this paper we propose a novel determination method for non-additive interaction measures by the way of solving a sequence of least norm problems and iteratively updating the values of interaction measures, namely least norm learning. This method can achieve a significant reduction on the computation time complexity from O(m × 2ⁿ) to O(mn) for solving the Choquet integral model, where ra and n are the numbers of observations and attributes, respectively. Also we achieve to reduce the computation space complexity from O(m × 2ⁿ) to 0(2ⁿ). A case study on cross-layer optimized wireless multimedia communications is adopted to validate the proposed method. Both analytical and experimental results show the effectiveness of the proposed method.