Skip to content

Latest commit

 

History

History
19 lines (14 loc) · 708 Bytes

README.md

File metadata and controls

19 lines (14 loc) · 708 Bytes

Linear Tree Shap

Compute exact Shapley value for decision trees in Linear time.

For a tree with maximum depth D, the number of leaves L. We compute the shapely value is O(LD) time, without the need for extra memory.

Numerical problems

  • tree depth exceeds 12; there are chances of overflow with double data type. It can be mitigated using long double data type.
  • tree depth exceeds 16; even with the long double type, there are still chances to overflow. It can still be mitigated using the fraction data type.

No numerical problems with v2

By using the interpolation method, we can have a numerical stable solution based on Chebyshev nodes of the first or second kind.