  The impressive performance of neural networks on natural language processing
tasks attributes to their ability to model complicated word and phrase
compositions. To explain how the model handles semantic compositions, we study
hierarchical explanation of neural network predictions. We identify
non-additivity and context independent importance attributions within
hierarchies as two desirable properties for highlighting word and phrase
compositions. We show some prior efforts on hierarchical explanations, e.g.
contextual decomposition, do not satisfy the desired properties mathematically,
leading to inconsistent explanation quality in different models. In this paper,
we start by proposing a formal and general way to quantify the importance of
each word and phrase. Following the formulation, we propose Sampling and
Contextual Decomposition (SCD) algorithm and Sampling and Occlusion (SOC)
algorithm. Human and metrics evaluation on both LSTM models and BERT
Transformer models on multiple datasets show that our algorithms outperform
prior hierarchical explanation algorithms. Our algorithms help to visualize
semantic composition captured by models, extract classification rules and
improve human trust of models. Project page: https://inklab.usc.edu/hiexpl/
