SHAP (SHapley Additive exPlanations) has become a popular method to attribute
the prediction of a machine learning model on an input to its features. One
main challenge of SHAP is the computation time. An exact computation of Shapley
values requires exponential time complexity. Therefore, many approximation
methods are proposed in the literature. In this paper, we propose methods that
can compute SHAP exactly in polynomial time or even faster for SHAP definitions
that satisfy our additivity and dummy assumptions (eg, kernal SHAP and baseline
SHAP). We develop different strategies for models with different levels of
model structure information: known functional decomposition, known order of
model (defined as highest order of interaction in the model), or unknown order.
For the first case, we demonstrate an additive property and a way to compute
SHAP from the lower-order functional components. For the second case, we derive
formulas that can compute SHAP in polynomial time. Both methods yield exact
SHAP results. Finally, if even the order of model is unknown, we propose an
iterative way to approximate Shapley values. The three methods we propose are
computationally efficient when the order of model is not high which is
typically the case in practice. We compare with sampling approach proposed in
Castor & Gomez (2008) using simulation studies to demonstrate the efficacy of
our proposed methods.

本文提出了多种方法，可以在多项式时间内准确计算 SHAP 值，适用于不同类型的模型结构信息，包括已知功能分解、已知模型顺序和未知模型顺序，其中的方法在实际应用中计算效率高且准确性较高。

利用模型结构信息高效计算 SHAP

Computing SHAP Efficiently Using Model Structure Information

Representation-based classification methods such as sparse
representation-based classification (SRC) and linear regression classification
(LRC) have attracted a lot of attentions. In order to obtain the better
representation, a novel method called projection representation-based
classification (PRC) is proposed for image recognition in this paper. PRC is
based on a new mathematical model. This model denotes that the 'ideal
projection' of a sample point $x$ on the hyper-space $H$ may be gained by
iteratively computing the projection of $x$ on a line of hyper-space $H$ with
the proper strategy. Therefore, PRC is able to iteratively approximate the
'ideal representation' of each subject for classification. Moreover, the
discriminant PRC (DPRC) is further proposed, which obtains the discriminant
information by maximizing the ratio of the between-class reconstruction error
over the within-class reconstruction error. Experimental results on five
typical databases show that the proposed PRC and DPRC are effective and
outperform other state-of-the-art methods on several vision recognition tasks.

本文提出了一种称为投影表示分类的新方法，其基于新的数学模型，可以通过迭代计算样本点在超空间 H 上线段的投影来近似每个主体的理想表示，并进一步提出了区别投影表示分类（DPRC）用于视觉识别任务。