summaries: This paper aims at taking techniques from motion interpolation into the regime where one is able to generate longer range motion sequences, in the domain of physically plausible computer animation of characters. In the way that the authors have set up the problem, an initial database seeds the search for plausible transitions between two given poses. So, the technique being proposed must address how to keep physical realism (the long-standing question of "dynamics filtering" along the lines of Yamane, Katsu, and Yoshihiko Nakamura. "Dynamics filter-concept and implementation of online motion generator for human figures." IEEE transactions on robotics and automation 19.3 (2003): 421-432. Of course the problem here also needs to address "style" which needs different models).

summaries: The paper tackles the problem of generating long-range, diverse and natural looking motion sequence between initial and end states, and proposes to use a semi-parametric approach consisting of local and global models. Specifically, first the proposed approach extracts local motion feature from a reference subsequence and style feature from another, and then generates a new motion sequence. Then, global motion composition is done to interpolated generated local subsequences by bi-directional composition. In experimental validation, the approach outperforms two baselines (GAN and VAE).

summaries: The paper proposed ''composable semi-parametric modeling'' for generating long-range diverse and distinctive behaviors to achieve a specific goal location. The non-parametric part is a memory bank that is used to retrieve motion patterns from source materials. The parametric part contains several deep neural networks which are to compose the retrieved materials for high quality and smooth motion generation. The overall idea is novel in the sense that they aim to combine the strength of the non-parametric method (with rich pattern and diversities) and the parametric method (powerfull ability to generate coherent results). The proposed ideas are evaluated on two datasets and outperform compared approaches qualitatively.

abstractText: Learning diverse and natural behaviors is one of the longstanding goal for creating intelligent characters in the animated world. In this paper, we propose “COmposable Semi-parametric MOdelling” (COSMO), a method for generating long range diverse and distinctive behaviors to achieve a specific goal location. Our proposed method learns to model the motion of human by combining the complementary strengths of both non-parametric techniques and parametric ones. Given the starting and ending state, a memory bank is used to retrieve motion references that are provided as source material to a deep network. The synthesis is performed by the deep network that controls the style of the provided motion material and modifies it to become natural. On skeleton datasets with diverse motion, we show that the proposed method outperforms existing parametric and non-parametric baselines. We also demonstrate the generated sequences are useful as subgoals for actual physical execution in the animated world. Please refer to our project page 1 for more synthesised results.

authors:
Jacopo Aleotti
Stefano Caselli

title: Grasp recognition in virtual reality for robot pregrasp planning by demonstration

venue: In Proceedings 2006 IEEE International Conference on Robotics and Automation,

authors:
Sanjeev Arora
Yi Zhang

title: Do gans actually learn the distribution? an empirical study

authors:
Mohammad Babaeizadeh
Chelsea Finn
Dumitru Erhan
Roy H. Campbell
Sergey Levine

title: Stochastic variational video prediction

venue: In ICLR,

authors:
Shane T. Barratt
Rishi Sharma

title: A note on the inception

venue: score. CoRR,

authors:
Emad Barsoum
John Kender
Zicheng Liu

title: HP-GAN: probabilistic 3d human motion prediction via GAN

venue: In CVPR Workshops,

authors:
Apratim Bhattacharyya
Mario Fritz
Bernt Schiele

title: Bayesian prediction of future street scenes using synthetic likelihoods

authors:
Richard H. Byrd
Peihuang Lu
Jorge Nocedal
Ciyou Zhu

title: A limited memory algorithm for bound constrained optimization

venue: SIAM J. Scientific Computing,

authors:
Haoye Cai
Chunyan Bai
Yu-Wing Tai
Chi-Keung Tang

title: Deep video generation, prediction and completion of human action sequences

venue: In ECCV,

authors:
Emily Denton
Rob Fergus

title: Stochastic video generation with a learned prior

venue: In ICML,

authors:
Emily L. Denton
Vighnesh Birodkar

title: Unsupervised learning of disentangled representations from video

venue: In NIPS,

authors:
Chelsea Finn
Ian J. Goodfellow
Sergey Levine

title: Unsupervised learning for physical interaction through video prediction

authors:
Ian J. Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron C. Courville
Yoshua Bengio

title: Generative adversarial nets

authors:
Agrim Gupta
Justin Johnson
Li Fei-Fei
Silvio Savarese
Alexandre Alahi

title: Social GAN: socially acceptable trajectories with generative adversarial networks

venue: In CVPR,

authors:
Adrian Haarbach
Tolga Birdal
Slobodan Ilic

title: Survey of higher order rigid body motion interpolation methods for keyframe animation and continuous-time trajectory estimation

venue: In 3DV,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural Computation,

authors:
Daniel Holden
Jun Saito
Taku Komura

title: A deep learning framework for character motion synthesis and editing

venue: ACM Trans. Graph.,

authors:
Daniel Holden
Taku Komura
Jun Saito

title: Phase-functioned neural networks for character control

title: Semi-parametric image inpainting

authors:
Xiaojie Jin
Huaxin Xiao
Xiaohui Shen
Jimei Yang
Zhe Lin
Yunpeng Chen
Zequn Jie
Jiashi Feng
Shuicheng Yan

title: Predicting scene parsing and motion dynamics in the future

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Diederik P. Kingma
Max Welling

title: Auto-encoding variational bayes

authors:
Lucas Kovar
Michael Gleicher

title: Flexible automatic motion blending with registration curves

venue: In SIGGRAPH/Eurographics Symposium,

authors:
Tejas D. Kulkarni
Karthik Narasimhan
Ardavan Saeedi
Josh Tenenbaum

title: Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation

authors:
Martin Lawitzky
Jose Ramon Medina
Dongheui Lee
Sandra Hirche

title: Feedback motion planning and learning from demonstration in physical robotic assistance: differences and synergies

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Youngwoon Lee
Shao-Hua Sun
Sriram Somasundaram
Edward S. Hu
Joseph J. Lim

title: Composing complex skills by learning transition policies

authors:
Sergey Levine
Jack M. Wang
Alexis Haraux
Zoran Popovic
Vladlen Koltun

title: Continuous character control with low-dimensional embeddings

authors:
Yunpeng Li
Dominik Roblek
Marco Tagliasacchi

title: From here to there: Video inbetweening using direct 3d convolutions

authors:
Ziwei Liu
Raymond A. Yeh
Xiaoou Tang
Yiming Liu
Aseem Agarwala

title: Video frame synthesis using deep voxel flow

venue: In ICCV,

authors:
Xuezhe Ma
Eduard H. Hovy

title: End-to-end sequence labeling via bi-directional lstm-cnns-crf. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016

venue: August 7-12,

authors:
Simone Meyer
Oliver Wang
Henning Zimmer
Max Grosse
Alexander Sorkine-Hornung

title: Phase-based frame interpolation for video

venue: In CVPR, pp

title: Robot Motion: Planning and Control edited by michael brady M.I.T

venue: press, cambridge ma, usa,

authors:
Simon Niklaus
Long Mai
Feng Liu

title: Video frame interpolation via adaptive separable convolution

authors:
Sang Il Park
Hyun Joon Shin
Sung Yong Shin

title: On-line locomotion generation based on motion blending

authors:
Xue Bin Peng
Pieter Abbeel
Sergey Levine
Michiel van de Panne

title: Deepmimic: Example-guided deep reinforcement learning of physics-based character skills

venue: ACM Transactions on Graphics (TOG),

title: Alvinn: An autonomous land vehicle in a neural network

venue: In Advances in neural information processing systems,

authors:
Xiaojuan Qi
Qifeng Chen
Jiaya Jia
Vladlen Koltun

title: Semi-parametric image synthesis

authors:
Nitish Srivastava
Elman Mansimov
Ruslan Salakhutdinov

title: Unsupervised learning of video representations using lstms

venue: In ICML, pp

authors:
Chen Sun
Per Karlsson
Jiajun Wu
Joshua B. Tenenbaum
Kevin Murphy

title: Stochastic prediction of multi-agent interactions from partial observations

authors:
Charlie Irawan Tan
Wen-Kai Tai

title: Characteristics preserving racer animation: a data-driven race path synthesis in formation space

venue: Journal of Visualization and Computer Animation,

authors:
Raquel Urtasun
David J. Fleet
Andreas Geiger
Jovan Popovic
Trevor Darrell
Neil D. Lawrence

title: Topologically-constrained latent variable models

authors:
Laurens van der Maaten
Geoffrey Hinton

title: Visualizing data using t-sne

venue: In Journal of Machine Learning Research,

authors:
Miao Wang
Guo-Ye Yang
Ruilong Li
Runze Liang
Song-Hai Zhang
Peter M. Hall
Shi-Min Hu

title: Example-guided style consistent image synthesis from semantic labeling

authors:
Xiaolong Wang
Rohit Girdhar
Abhinav Gupta

title: Binge watching: Scaling affordance learning from sitcoms

authors:
Yonatan Wexler
Eli Shechtman
Michal Irani

title: Space-time completion of video

venue: IEEE Trans. Pattern Anal. Mach. Intell.,

authors:
Nevan Wichers
Ruben Villegas
Dumitru Erhan
Honglak Lee

title: Hierarchical long-term video prediction without supervision

authors:
Guiyu Xia
Huaijiang Sun
Qingshan Liu
Renlong Hang

title: Learning-based sphere nonlinear interpolation for motion synthesis

venue: IEEE Trans. Industrial Informatics,

authors:
Jingwei Xu
Bingbing Ni
Xiaokang Yang

title: Video prediction via selective sampling

venue: In NIPS, pp

authors:
Yanyu Xu
Zhixin Piao
Shenghua Gao

title: Encoding crowd interaction with deep neural network for pedestrian trajectory prediction

authors:
Xinchen Yan
Akash Rastogi
Ruben Villegas
Kalyan Sunkavalli
Eli Shechtman
Sunil Hadap
Ersin Yumer
Honglak Lee

title: MT-VAE: learning motion transformations to generate multimodal human dynamics

authors:
Gu Ye
Ron Alterovitz

title: guided motion planning

venue: In Robotics research,

authors:
Jason Y. Zhang
Panna Felsen
Angjoo Kanazawa
Jitendra Malik

title: Predicting 3d human dynamics from video

authors:
Tianyang Zhao
Yifei Xu
Mathew Monfort
Wongun Choi
Chris Baker
Yibiao Zhao
Yizhou Wang
Ying Nian Wu

title: Multi-agent tensor fusion for contextual trajectory prediction

heading: 1 INTRODUCTION

text:
When faced with a specific goal in another location, humans can effortlessly find multiple distinctive trajectories and control their body to approach the goal with diverse and natural behaviours. However, we are still at the early stage for such sophisticated controlling of simulated characters. Recent reinforcement learning approaches (Peng et al., 2018) struggle to generate diverse motion. Other methods like imitation learning (Ye & Alterovitz, 2017; Aleotti & Caselli, 2006; Lawitzky et al., 2012) generalize badly to large scale demonstration data. The heart of this challenge lies in that real-world human behaviours are inherently multi-modal distributed. Direct behaviour learning is difficult without access to the explicit distribution of motion states.
In this paper, we take a step toward generating long-range, diverse and physically plausible motion sequences given starting and ending states, rather than learning a policy for a physical simulator. Meanwhile, we expect the model could generate novel behaviour, i.e., unseen motion in training set. This has several valuable applications: (1) Synthesised vivid motion for animation production without excessive human labor. (2) Generated novel behaviours for player customization of action skills in video games. (3) Interpolated sequences as subgoals for policy training through reinforcement learning (Peng et al., 2018).
To fulfil the above requirements, we need to address the following difficulties: (1) How to guarantee both diversity and naturalness, which is usually trade-off in the domain of generation (Srivastava et al., 2015)? (2) How to achieve long-range behaviour synthesis, which is stuck by error accumulation problem in many temporal modelling tasks (Denton & Fergus, 2018)? (3) How to generate unseen behaviours without loss of diversity or naturalness, which is hardly addressed in previous researches? As shown in Fig 1, the current two main branches of motion generation methods, i.e., parametric and non-parametric, are yet to deal with these difficulties properly. Parametric (Goodfellow et al., 2014) (e.g., GAN) methods could not maintain the reality/naturalness of generated sequences, and diversity (e.g., VAE) is hard to preserve. Non-parametric methods (Haarbach et al., 2018) involving motion clip copy/paste or blending has less superiority in smooth transition based on diverse reference sequences.
1https://sites.google.com/view/cosmo-supp/home
In this work, we propose COmposable Semi-parametric MOdelling (COSMO), which is a method that can leverage the large spectrum of motion skills from unlabeled data in a semi-parametric manner. Our method combines the complementary strengths of both non-parametric techniques and parametric ones. First, to avoid mode collapse in the sequences, we initially sample reference subsequences from a held-out reference set to encourage multi-modal behaviors in the generated sequence, which is mainly inspired from non-parametric methods (Haarbach et al., 2018). Second, we propose a self-supervised disentanglement model for extracting the content and style from each reference subsequence respectively. Here content refers to the characteristic of state at each time step, e.g., moving speed, direction, and general gesture of upper body, while style refers to the long-range motion pattern which keeps relative constant across whole subsequence. An embedded latent space is constructed where the learned style vectors could be combined to obtain novel style feature. A new subsequence is obtained by composing content and style freely from different reference subsequences. Considering that this operation only produces a single subsequence, we refer this step as local motion composition. Finally, for all new sequences, we compose them along the temporal direction in a sequential order. However, from a hodgepodge of reference segments, it is non-trivial to generate natural and meaningful behaviors. To guarantee naturalness at long-range scale, we then propose to use goal conditioned bi-directional interpolation for modeling the long-range nature needed in the task. This step is regarded as global motion composition, which covers the whole temporal scale (often more than 100 steps). On two human motion datasets, we show that the proposed method outperforms existing parametric and non-parametric baselines. We also demonstrate the generated sequences are useful as subgoals for actual physical execution in the animated world.
Our paper makes three contributions. First, we proposed COmposable Semi-parametric MOtion generation (COSMO), a method that can generate the required sequences in a semi-parametric, composed way. Second, we conducted experiments on CMU Mocap dataset 2 and SFU Mocap dataset 3 and shows our method outperforms strong baselines such as VAEs and GANs significantly. Third, we proved empirically that the generated sequences can serve as subgoals to learn an actual policy.

heading: 2 METHOD

heading: 2.1 SEMI-PARAMETRIC MODELLING FOR MOTION GENERATION

text:
Given starting and ending states (denoted as s0 and sL respectively) as inputs, our goal is to synthesize intermediate states that have natural transition and diverse behaviors. As illustrated in Fig 2, NR reference subsequences (denoted as Ri, i = 1, .., NR) are sampled and fed into local motion composition
2http://mocap.cs.cmu.edu/ 3http://mocap.cs.sfu.ca/
sub-module φloc. Invalid subsequences are first filtered out with predefined requirements and please refer to appendix 6 for detailed description. φloc is used for altering the motion style of reference subsequence Ri based on another sequence R as input or directly sampling a style feature from learned latent space: R̂i = φloc(Ri,R), where R is optional input. With this in hand, we compose edited subsequences {R̂i}NRi=1 along temporal direction smoothly. Concretely, we generate a new clip R̃i−1:i = φglo(R̂i−1, R̂i) which bridges the gap between R̂i−1 and R̂i. The final composed sequence is obtained through concatenation along the temporal direction for all subsequences and generated clips.
Why semi-parametric modelling? Regarding both motion category and transition dynamics (from current to next state), human behaviors are intrinsically multi-modal distribution (Holden et al., 2017). Parametric models (e.g., VAE (Kingma & Welling, 2014) or GAN (Goodfellow et al., 2014)) assume prior distribution to be uni-modal and predefined, which is not suitable to handle real world motion sequences (Kingma & Welling, 2014; Arora & Zhang, 2017). Non-parametric model does not require explicit prior distribution but not able to deal with long-range and highly diverse motion properly, mainly restricted by modelling capability. We also conduct targeted comparison experiments in Section 4. Compared to parametric methods, semi-parametric modelling naturally guarantees motion diversity by introducing reference sequence also maintaining a large degree of freedom for generation. Moreover, semi-parametric modelling does not require access to or a model of data distribution. It implies that our method is also directly applicable for unseen motion sequence.
Constrained by starting and ending states with unchangeable locations, it is not feasible to randomly sample reference subsequences for generation. To construct a complete motion sequence, we execute a manually designed procedure for searching reference subsequences. For detailed description, please refer to appendix 6

heading: 2.2 LOCAL MOTION COMPOSITION WITH CONTENT/STYLE DISENTANGLEMENT

text:
Local motion composition stands for generating a relative short-range of motion clip based on reference subsequences as inputs. Content and style features are learned jointly, whose free-form composition is used for synthesising new motion sequence. We first describe the motion style modelling part.
Motion Style Modelling. Style is considered as motion information which stays the same throughout the whole subsequence. To this end, we extract style pattern by conducting feature fusion along the temporal direction. More specifically, for a sequence with T frames, we gradually fuse all frames into one constant feature with Cs channels (denoted as hs). We adopt 1D convolution along the temporal direction for each operation. Three convolution layers are stacked together with a kernel size of (T/2, T/4, T/8) respectively, where large kernel size facilitates capturing motion style throughout the whole subsequence.
To get better generalization ability for unseen reference or starting/ending states, we propose to construct an embedding space for style pattern modelling. More specifically, a set of embedding vectors (denoted as Hs = {his}Mi=1) are learned together with above convolution layers (denoted as ψsty). The corresponding outputs (denoted as As ∈ RM ) of ψsty are a family of coefficients for a weighted sum of Hs. This is mainly inspired by the intuition that complex human activity could be considered as a combination of several simple actions. When trained with sufficiently large motion data, the model tends to learn basic style patterns for human motion. Compared to directly outputting a feature vector, this helps better generalize to unseen motion during testing. The final style feature (denoted as fs ∈ RCs ) is generated as follows:
f is = ψsty(R i)Hs. (2.1)
Motion Content Modelling. In this part, we focus on motion dynamics reflected by each single state. To this end, 1D convolution layer with kernel size of 3, i.e., covering consecutive 3 states, is adopted for content modelling. The output channel of this layer is designed less than original motion dimension for extracting the most relevant information. This is empirically set to 5 as a design choice. Meanwhile, velocity, position for root joint and step pattern for foot joint are fed as inputs. We denote all the above factors as fc with T steps and Cc channels. During local motion composition, style feature fs is combined with content feature fc through concatenating along the channel axis:
f ic = ψcnt(R i), R̂i = ψrec(f i c , f i s), (2.2)
where fs is tiled T times to match with fc and ψrec outputs reconstructed R̂i. ψrec follows stacked three layer 1D convolution operation with kernel size of 3. Finally, reconstruction loss is used to learn the style and content feature jointly as follows:
LRrec = 1
NR ΣNRi=1||R̂ i −Ri||22. (2.3)

heading: 2.3 GLOBAL MOTION COMPOSITION VIA GOAL CONDITIONED BI-DIRECTIONAL MODELLING

text:
Global motion composition is connecting edited short-range subsequences into a completed and long-range one. Generating smooth and natural transition between R̂i and R̂i+1 is critical to obtain a long-range sequence. The major challenge comes from large states variation between R̂i and R̂i+1. Inspired by recent work of Bi-LSTM modelling (Ma & Hovy, 2016), bi-directional motion composition is utilized for this part. More specifically, motion states are first mapped to a higher dimensional space with ϕenc and ϕdec, which is defined as follows:
f it = ϕenc(r i t), r̂ i t = ϕdec(f i t ). (2.4)
Both ϕenc and ϕdec are 1D convolution layers. Then we predict the possible states at both directions with f it , where higher dimension (256) provides a sparser space enabling better composition results. For forward prediction, we take f iT−4:T as inputs to obtain forward states f i:i+1 1 . Meanwhile, f i+1 1:5 are fed as inputs treated as goal conditions. We conduct this procedure in a recurrent manner with P -step prediction in total. Predicted f i:i+11 is concatenated with last four states forming next step inputs. Backward direction takes exactly the reverse procedure, i.e., f i+1T−4:T are treated as inputs while f i 1:5 are as goal: f i:i+1p+1 = ϕfpre(f i p−4:p, f i+1 1:5 ), f i+1:i p+1 = ϕbpre(f i+1 p−4:p, f i T−4:T ), (2.5)
where ϕfpre and ϕbpre share the same architecture.. Moreover, we utilize another model to produce coefficients for the weighted sum of outputs. In this way, we are able to construct more flexible latent space to facilitate composition:
c = ϕcom(f i:i+1 p , f i+1:i P−p , p), f̂p = cf i:i+1 p + (1− c)f i+1:iP−p . (2.6)
ϕcom is one layer 1D convolution with sigmoid function for producing c. More specifically we introduce p and linearly map it to p̂ ∈ (−1, 1) and c = p̂+ 0.1 ∗ σ(conv([f i:i+1p , f i+1:iP−p ])). During training, we randomly select a motion clip with a length of 10 + P . First as well as last 5 states are fed as inputs to get intermediate P states. Reconstruction loss is used for training:
Lfrec = 1
P ΣPt=1||r̂t − ϕdec(f̂ t)||22. (2.7)
Compared with goal-conditioned single forward prediction model, the starting and ending states are treated equally in our model, which avoids drifting away from the ending state. Meanwhile, we provide corresponding empirical results in Section 4. After global motion composition, final composed sequence is directly obtained by concatenating all edited subsequences (local part) as well as transition clips (global part) along the temporal direction.
We use tensorflow (Abadi et al., 2015) to implement all our models. All activation function used in our model is ReLU operation. During training, learning rate is set to 1e-4 and optimized with Adam optimizer (Kingma & Ba, 2015). β1 and β2 are set as 0.9 and 0.999 respectively. All models are trained with 30 epochs in total. Note that the local and global motion composition submodule do not need joint training. They are used jointly during testing.

heading: 3 RELATED WORK

text:
Motion Interpolation. Given start and end states, this task aims to synthesize intermediate states which smoothly translate between them (Urtasun et al., 2008). For video interpolation (Liu et al., 2017; Li et al., 2019; Meyer et al., 2015; Niklaus et al., 2017) where start and end states are two consecutive frames, the final result is expected to increase frame rate of original video to a higher value. Previous researches often utilize phase dynamics (Meyer et al., 2015), flow based feature (Liu et al., 2017) and other motion information (Niklaus et al., 2017) to facilitate this task. Our work is different from this branch of work because there exists large motion gap between start and end states in our settings. Another branch of work is video completion (Cai et al., 2018; Li et al., 2019; Wexler et al., 2007). It receives two nonconsecutive frames as input and aims to fill the motion gap between start and end states. Cai et al. (2018) firstly attempts to solve this task and more specifically, propose to select out a rational path in the latent space with BFGS (Byrd et al., 1995) algorithm. Li et al. (2019) incorporates the 3D convolution layers and LSTM network into a unified model, which tries to automatically find the optimal results for intermediate frames. Despite much progress has been made in this filed, the high dimensional data (i.e., video frames) severely restricts video completion within simple and seen motion categories. However, we do not limit the start and end states belonging to the same sequence. Meanwhile, we expect the interpolated sequence as diverse as possible meanwhile with natural transition between synthesised states. This has not been deeply addressed in previous motion completion works (Xia et al., 2019; Lee et al., 2019). As a potential downstream application, our model could be used to construct motion planning (Myers, 1983) algorithm. Compared to goal-driven RL (Kulkarni et al., 2016; Lee et al., 2019), our model gets rid of requirements hard to achieve, i.e., known dynamics of agent, which is more general and applicable to more motion planning scenarios.
Temporal Data Prediction. There have been many researches focusing on temporal data prediction. This task aims to infer the future possible states conditioned on history states as input. Video prediction (Srivastava et al., 2015) takes a major part in this field, which involves pixel-wise forecasting for every following frames. Previous methods (Denton & Fergus, 2018; Babaeizadeh et al., 2018; Denton & Birodkar, 2017; Finn et al., 2016) have made it to produce high quality prediction on bouncing digits (Srivastava et al., 2015), robot motion (Finn et al., 2016) and semantic map (Jin et al., 2017). However, recent work (Xu et al., 2018a) still encounters much difficulties in forecasting complex movements involving articulated subject (Wichers et al., 2018). Moreover, these works are prone to have motion blur (Finn et al., 2016) and error accumulation (Denton & Fergus, 2018) problems. Out of above concerns it is more appropriate for us to formulate our method as interpolation instead of prediction model. In terms of lower dimension data, human pose (Sun et al., 2019; Zhang et al., 2019) as well as path trajectory (Xu et al., 2018b) are also hot spots in this task. Several works adopt probabilistic Bayesian model (Bhattacharyya et al., 2019) to dig out latent factors which influence future dynamics. Another branch of researches (Gupta et al., 2018; Xu et al., 2018b) utilize deep recursive model (e.g., LSTM Hochreiter & Schmidhuber (1997)) to extract critical feature for prediction. Low dimension data enables all these works could easily scale to multi-target settings (Zhao et al., 2019). However, prediction model loses its power when encountering out of distribution data (e.g., unseen motion category in test set). As comparison, our interpolation model could naturally generalize to unseen motion facilitated by semi-parametric modelling, which gets rid of explicit representation for future dynamics.
Generative Semi-parametric Modelling. For generative task such as image synthesis (Qi et al., 2018), translation (Wang et al., 2019) and inpainting (Iskakov, 2018), semi-parametric modelling achieves considerably more realistic visual quality and better style consistency between source and target images. Semi-parametric modelling is also utilized in reinforcement learning (Kulkarni et al., 2016) for navigation task (Eysenbach et al.). More specifically, it searches rational path on replay buffer, which enables agents to solve sparse reward tasks over one hundred steps. Wang et al. (2017) combines semi-parametric modelling and VAE for large-scaled motion affordance. In this work we use semi-parametric modelling for two main reasons: (1) it could substantially increase the length of interpolated sequence through acting as example guidance, (2) it enables our model to synthesise visually appealing results even with out of distribution inputs. Meanwhile, we would like to highlight that to our best knowledge this is the first attempt to use semi-parametric modelling on motion interpolation task.
Motion Generation in Computer Graphics. In the context of computer graphics, there is a branch of researches (Kovar & Gleicher, 2003; Park et al., 2002; Levine et al., 2012; Tan & Tai, 2012; Holden et al., 2016) which also concentrate on motion generation, i.e., obtaining a continuous trajectory from a discrete set of poses. Haarbach et al. (2018) provides a comprehensive study on this topic. It analyzes the characteristics of higher order rigid body motion interpolation methods. Our works shares similar target with this branch of work. However, we would like to emphasise that these works (Tan & Tai, 2012; Kovar & Gleicher, 2003; Park et al., 2002) are in parallel with ours and have completely different research routine on this task. More specifically, graphics methods focus on finding a optimal and explicit mathematical solution regardless of input motion sequences. Different from them, our work is data-driven and encourages both reality and diversity of interpolated results.
Imitation Learning. Imitation learning (Pomerleau, 1989; Ye & Alterovitz, 2017; Lawitzky et al., 2012) is commonly adopted as a standard method in the domain of robotics and many other areas. Behavioral Cloning (Osa et al., 2018) is one of the underlying approaches that utilize a demonstrations as supervisory signal. The most relevant work to ours is (Peng et al., 2018) which leverages reinforcement learning to imitate natural motions. However, our method does not imitate specific motion trajectories but to generate natural and diverse actions that are reasonable between given states. Our method can be further differentiated from past literature in two aspects: (1) our method is orthogonal to imitation learning because it interpolates states rather than predicts actions when states are given. More importantly, (2) the proposed method is able to produce between unseen states while imitation learning focuses on imitating and capturing the demonstrated distribution.

heading: 4 EXPERIMENTS

heading: 4.1 EVALUATION SETTINGS

text:
We use CMU Mocap 4 and SFU Mocap 5 datasets for evaluation. Both datasets contain diverse daily human motion sequences which are suitable for training. Considering that the original sequences possess different length, we get reference subsequence in a sliding window manner, where T = 120 and P = 40. For both datasets the dimension of state is 63, which is 21 joints with 3D coordinates. Here we would like to emphasise that we keep a held-out reference set (denoted as DR) from training data (denoted as DT ) for further testing, to demonstrate that our model could generate novel behaviour never seen during training. More specifically, DR is used for sampling novel motion and starting/ending states during testing. Note that the following all experiments are with SFU Mocap datasets. For the visual results on CMU Mocap datasets, please refer to our project page.
For local motion composition, we compare our model with two strong parametric baselines: VAE (Kingma & Welling, 2014) and GAN (Goodfellow et al., 2014). For fair comparison, we train both models with all data, i.e., DT and DR. Meanwhile we follow Yan et al. (2018) and Barsoum et al. (2018) about the hyper-parameter setting of both models. But the input dimension is adjusted to match our data. For global motion composition, we compare our model with temporal prediction baselines: (1) Baseline1: ϕfpre without last 5 states as goal condition, (2) Baseline2: ϕfpre with last 5 states as goal condition, (3) Baseline3: both ϕfpre and ϕbpre but without last/first
4http://mocap.cs.cmu.edu/ 5http://mocap.cs.cfu.ca/
5 states as goal condition. All three baselines are trained with the same hyper-parameter setting as our global composition model.

heading: 4.2 EVALUATION FOR LOCAL MOTION COMPOSITION

text:
Is generated motion diverse enough? We compare our model with parametric model (i.e., VAE (Kingma & Welling, 2014) and GAN (Goodfellow et al., 2014)) in evaluation of motion diversity. For the majority of generative models, the diversity of generated result is upper bounded by training data Barratt & Sharma (2018). Motivated by this, we compare motion diversity with VAE (Kingma & Welling, 2014) and GAN (Goodfellow et al., 2014) based models under different percentages of data used for training. As illustrated in Fig 3, 10%, 30%, 50% and 100% training data are used respectively. After training converged, we calculate the averaged standard diviation of all joints with a higher value indicating more diverse. We can see that both parametric models keep relative constant motion diversity which is comparable with training data used less than 30%, but largely inferior to the diversity of full training data. On the contrary, with an increasing percentage of data used for training, our model achieves higher motion diversity, which mainly benefits from the general semi-parametric modelling framework.
Is generated motion visually natural? For evaluation of visual naturalness, we provide generated motion results and compare with VAE (Kingma & Welling, 2014) and GAN (Goodfellow et al., 2014). As shown Fig 5, from top to bottom generated motion sequences correspond to our model (COSMO), GAN (Goodfellow et al., 2014) and VAE (Kingma & Welling, 2014), respectively. Note that all three sequences are with a length of 440 time steps. Our model (COSMO) generate the sequence with three reference subsequences. While both GAN (Goodfellow et al., 2014) and VAE (Kingma & Welling, 2014) models directly produce the motion in a recurrent manner. The GAN based model fails to synthesise a normal walking sequence with large pose distortion. The VAE based model is able to generate a visually natural walking sequence facilitated by KL loss during training but struggles to produce diverse motion behaviour. Different from all these parametric models, Fig 5
shows that our semi-parametric modelling based model achieves natural state transition throughout the whole sequence, meanwhile provides natural and diverse motion (i.e., walking-turning-walking) behaviours during generation. We encourage readers to refer to our project page for more video demonstrations.
Do proposed model learn a meaningful style space? Recall that for representation learning of style feature, we construct an embedded space instead of directly generating style feature. In this way, we expect our model able to map a novel style pattern into learned embedded space. For validation we randomly select 10% training data then extract corresponding style feature (denoted as Strain) with ϕsty. Regarding the held-out set (denoted as Sref ) we conduct the same operation for all reference subsequences. We visualize the distribution of both Strn and Sref with t-SNE (van der Maaten & Hinton, 2008) in a two-dimensional plane. As shown in Fig 4, the purple dots indicate training data while green dots stand for reference data. We can see that the style feature of training data spread evenly across the plane. Meanwhile, the majority of style of feature of reference subsequences is covered by that of training data. Within the learned style space, embedded layer acts as a set of style bases where novel style can be approximated by the combination of these bases.
Can COSMO compose two reference subsequences into a novel one? Part of the generation diversity of our model results from free composition of reference subsequences. As shown in Fig 6, we provide two edited sequence examples which possess the general motion style from one subsequence, but detailed motion pattern from another one. Taking the second sequence (bottom row in Fig 6) for example, the target style motion shows a spinning motion with both hands raised up (style), while the reference motion is a regular walking sequence. We can notice that the final edited reference motion (third column, bottom row) fully captures the style of upper body meanwhile maintains the walking pattern from reference sequence. Moreover, both top and bottom rows use the same reference motion, but with different style as inputs, our model can still produce highly diverse behaviours. For the space restriction of paper writing, we provide more examples whose new style features are sampled from constructed embedded space. We encourage readers to refer to our project page for more video demonstrations.

heading: 4.3 EVALUATION FOR GLOBAL MOTION COMPOSITION

text:
Do COSMO learn better motion transition than basic prediction models? Different from prediction model, COSMO produces motion transition given starting or ending states from different sequences, i.e., there is no ground truth for evaluation. To this end, we provide training error for evaluation of motion transition. As shown in Fig 7(A), we can see that our model (COSMO) outperforms other methods by a large margin. Base1 achieves lowest accuracy caused by no ending states are provided during composition. Baseline2 and Baseline3 models perform better than base1 model, which indicates that both bi-directional and goal-conditional modelling scheme facilitates motion composition by a large margin. Our global composition sub-module combines the strength of both Baseline2 and Baseline3 models, which evenly utilize the information from starting and ending states. However, merely considering the training error is not sufficient. Next, we further evaluate the performance of our model given two different sequences.
Can COSMO guarantee smooth transition between two different sequences? Fig 8 demonstrates motion transition results given starting and ending states from different reference subsequences, respectively. Note that for all sequences shown in Fig 8, the starting as well as ending states are from held-out reference set. We can observe that our model is able to generate smooth and natural transition when starting and ending states are similar. Moreover, when encountered large motion difference, e.g., from walking to greeting, turning back with a relatively large degree, our model still makes it to generate visually natural transition sequence. We encourage readers to refer to our project page for more video demonstrations.
Is global motion composition merely linear interpolation? One possible trivial solution learned by our transition model is to simply linear interpolation between starting and ending states. However, common human motion generally involves non-linear trajectories. Linear interpolation is prone to produce unnatural motion which is easy to detect by human eyes. To valid that whether our model conducts linear interpolation between two sequences, we record the height variation of the right foot
in a composed motion sequence. Meanwhile, we manually rotate the second sequence w.r.t. the final state of the first sequence to show that our model is robust to a large range of direction difference between two sequences. As shown in Fig 7(A), two black arrows indicate the starting and ending steps for composition. Here we present multiple curves which correspond to different rotation angle mentioned earlier. All recorded curves are highly non-linear but smooth between starting and ending points. Moreover, our model adaptively changes foot height with different rotation configurations, which indicates smooth and natural motion for motion composition.
Visualization of final composed sequences. Combining local and global motion together, we are able to generate final sequences. Recall that our model is constrained by given starting and ending states based on motion interpolation. To this end, we present three composed sequences with a length of 480 time steps, i.e., three edited reference sequences (length of 120) and four generated clips for global motion composition. As shown in left part of Fig 9, starting from the same state, we are able to generate long-range and visually natural motion boosted by the local and global motion composition. Meanwhile, we are able to generate diverse behaviour (shown as complex hand and foot motion) facilitated semi-parametric modelling. We encourage readers to refer to our project page for more video demonstrations.

heading: 4.4 APPLICATION

text:
In this section, we present several downstream applications related to our motion generation model. The first one is diverse motion generation under fixed rout constrain. The second one is demonstration motion guidance for imitation learning (Peng et al., 2018).
Diverse motion generation. As shown in the right part of Fig 9, we manually design four routes for motion generation. We can see that our semi-parametric model is able to produce intermediate motion states clearly following the predefined route. Note that the longest motion sequence indicating character "R" is over 1500 time steps. We encourage readers to refer to our project page for corresponding video demonstrations.
Expert demonstration guidance for imitation learning. Under a simulated environment with gravity constrain (Peng et al., 2018), unnatural motion violating physical law (e.g., severe joint twisting) is hard for a simulated agent to follow. To further show our model produces realistic motion, generated results are used for demonstration guidance of imitation learning. As shown in Fig 10, the left part is demonstration synthesised by COSMO (top) while the bottom one is learned policy with Peng et al. (2018). We can see that the learned motion succeeds to follow the synthesised one. The right part is return curve during training, which also shows that our generated motion is realistic enough for the guidance of imitation learning. We encourage readers to refer to our project page for corresponding video demonstrations.

heading: 5 CONCLUSION

text:
In this work, we propose to generate long-range motion in a semi-parametric way. We first sample reference motion subsequence from the held-out set and change the motion style with a local motion composition scheme. We then compose all reference subsequences with the proposed global motion composition scheme. Given the same starting and ending states, the proposed model is able to
generate long-range, diverse and natural motion sequences over 1000 time steps without loss of visual quality.

heading: 6 APPENDIX

text:
Requirements for reference sequence Ri. Our model does not restrict the length of Ri, neither any specific/predefined starting or ending states of it. However, there are still restrictions for Ri:
• Physically reachable. In this work we do not have access to the dynamics of other objects, which should be excluded from candidate references if involved. For example, our model does not intend for synthesising transition sequence from running to lifting. The latter behaviour needs dynamic information (bell) to model. Therefore, in our experiments reference subsequence is first restricted to single character motion without external interaction. • Moving on flat ground. Besides physically reachable, we also restrict the character moving
on flat ground. Because in our task there is no predefined ground information available for modelling. To get rid of unexpected composition results, we filter out these sequences recorded from uneven terrain.
Searching procedure for reference subsequences
• Step 0: Calculate overall root locations for all reference subsequences. We denote corresponding minimum/maximum value as tmin/tmax respectively. • Step 1: Given s0 and sL, extract corresponding root locations (l0 and lL) respectively. Here
root is defined by the ground projection of hip joint. Then sample NR + 1 mid locations, which forms NR + 2 pairs, i.e, [l0, l1], ..., [lNR , lL]. Distance defined by each pair dm is bounded, i.e., tmin < dm < tmax. • Step 2: For each location pair, we search reference subsequence for similar translation
defined by dm with maximum tolerance σt. We conduct local motion composition for searched reference subsequence (in Section 2.2). • Step 3: We sequentially conduct goal conditioned bi-directional motion interpolation for
two consecutive reference subsequences (in Section 2.3). As a preprocessing procedure, the overall location and direction of latter sequence is adjusted w.r.t former one for interpolation. The final sequence is obtained through concatenating all synthesised clips along temporal axis.


summaries: The authors proposed a method for generating hierarchical importance attribution for any neural sequence models (LSTM, BERT, etc.) Towards this goal, the authors propose two desired properties: 1) non-additivity, which means the importance of a phrase should be a non-linear function over the importance of its component words; 2) context independence, which means that the attribution of any given phrase should be independent of its context. For example, in the sentence "the film is not interesting", the attribution of "interesting" should be positive while the attribution of "not interesting" should be negative.

summaries: The paper addresses the problem of hierarchical explanations in deep models that handle compositional semantics of words and phrases. The paper first highlights desirable properties for importance attribution scores in hierarchical explanations, specifically, non-additivity and context independence, and shows how prior work on additive feature attribution and context decomposition doesn’t accurately capture these notions. After highlighting the said properties in context of related work, the authors propose an approach to calculate the context-independent importance of a phrase by computing the difference in scores with and without masking out the phrase marginalized over all possible surrounding word contexts (approximated by sampling surrounding context for a fixed radius under a language model). Furthermore, based on the above, the authors propose two more score attribution approaches -- based on integrating the above sampling step with (1) the contextual decomposition pipeline and (2) the input occlusion pipeline. Experimentally, the authors find that the attribution scores assigned by the proposed approach are more correlated with human annotations compared to prior approaches and additionally, the generated explanations turn out to be more trustworthy when humans evaluate their quality.

summaries: This paper proposes a hierarchical decomposition method to encode the natural language as mathematical formulation such that the properties of the words and phrases can encoded properly and their importance be preserved independent of the context. This formulation is intuitive and more efficient compared to blindly learning contextual information in the model. The proposed method is a modification of contextual decomposition algorithm by adding a sampling step. They also adapt the proposed sampling method into input occlusion algorithm as another variant of their method. The proposed method is tested on LSTM and BERT models over sentiment datasets of Stanford Sentiment Treebank-2 and Yelp Sentiment Polarity and TACRED relation extraction dataset and showed more interpretable generated hierarchical explanations compared to baselines.

abstractText: 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 models1.

authors:
Marco Ancona
Enea Ceolini
Cengiz Öztireli
Markus Gross

title: Towards better understanding of gradient-based attribution methods for deep neural networks

venue: arXiv preprint arXiv:1711.06104,

title: Visualizing the effects of predictor variables in black box supervised learning models

venue: arXiv preprint arXiv:1612.08468,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: In 3rd International Conference on Learning Representations,

authors:
Alexander Binder
Grégoire Montavon
Sebastian Lapuschkin
Klaus-Robert Müller
Wojciech Samek

title: Layer-wise relevance propagation for neural networks with local renormalization layers

venue: In International Conference on Artificial Neural Networks,

authors:
Chun-Hao Chang
Elliot Creager
Anna Goldenberg
David Duvenaud

title: Explaining image classifiers by counterfactual generation

venue: In International Conference on Learning Representations,

authors:
Jianbo Chen
Le Song
Martin J. Wainwright
Michael I. Jordan

title: Learning to explain: An information-theoretic perspective on model interpretation

title: L-shapley and c-shapley: Efficient model interpretation for structured data

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Katsushige Fujimoto
Ivan Kojadinovic
Jean-Luc Marichal

title: Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction

venue: indices. Games and Economic Behavior,

authors:
Riccardo Guidotti
Anna Monreale
Salvatore Ruggieri
Franco Turini
Fosca Giannotti
Dino Pedreschi

title: A survey of methods for explaining black box models

venue: ACM computing surveys (CSUR),

title: Interpretation of prediction models using the input gradient

venue: arXiv preprint arXiv:1611.07634,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

title: Discovering additive structure in black box functions

venue: In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
Akos Kádár
Grzegorz Chrupała
Afra Alishahi

title: Representation of linguistic form and function in recurrent neural networks

venue: Computational Linguistics,

authors:
Tao Lei
Regina Barzilay
Tommi S. Jaakkola

title: Rationalizing neural predictions

venue: In EMNLP,

authors:
Jiwei Li
Will Monroe
Dan Jurafsky

title: Understanding neural networks through representation erasure

venue: arXiv preprint arXiv:1612.08220,

authors:
Hui Liu
Qingyu Yin
William Yang Wang

title: Towards explainable NLP: A generative explanation framework for text classification

venue: In Proceedings of the 57th Conference of the Association for Computational Linguistics,

authors:
Yinhan Liu
Myle Ott
Naman Goyal
Jingfei Du
Mandar Joshi
Danqi Chen
Omer Levy
Mike Lewis
Luke Zettlemoyer
Veselin Stoyanov

title: Roberta: A robustly optimized bert pretraining approach

venue: arXiv preprint arXiv:1907.11692,

authors:
Scott M Lundberg
Su-In Lee

title: A unified approach to interpreting model predictions

venue: In Advances in Neural Information Processing Systems,

authors:
Sina Mohseni
Niloofar Zarei
Eric D Ragan

title: A survey of evaluation methods and measures for interpretable machine learning

venue: arXiv preprint arXiv:1811.11839,

authors:
W James Murdoch
Peter J Liu
Bin Yu

title: Beyond word importance: Contextual decomposition to extract interactions from lstms

venue: In ICLR,

authors:
Jeffrey Pennington
Richard Socher
Christopher Manning

title: Glove: Global vectors for word representation

venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),

authors:
Matthew E Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke Zettlemoyer

title: Deep contextualized word representations

venue: arXiv preprint arXiv:1802.05365,

authors:
Nina Poerner
Hinrich Schütze
Benjamin Roth

title: Evaluating neural network explanation methods using hybrid documents and morphological agreement

venue: arXiv preprint arXiv:1801.06422,

authors:
Marco Tulio Ribeiro
Sameer Singh
Carlos Guestrin

title: why should I trust you?”: Explaining the predictions of any classifier

venue: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data

title: A value for n-person games

venue: Contributions to the Theory of Games,

authors:
Avanti Shrikumar
Peyton Greenside
Anshul Kundaje

title: Learning important features through propagating activation differences

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Karen Simonyan
Andrea Vedaldi
Andrew Zisserman

title: Deep inside convolutional networks: Visualising image classification models and saliency maps

venue: arXiv preprint arXiv:1312.6034,

authors:
Chandan Singh
W James Murdoch
Bin Yu

title: Hierarchical interpretations for neural network predictions

authors:
Richard Socher
Alex Perelygin
Jean Wu
Jason Chuang
Christopher D Manning
Andrew Ng
Christopher Potts

title: Recursive deep models for semantic compositionality over a sentiment treebank

venue: In Proceedings of the 2013 conference on empirical methods in natural language processing,

authors:
Daria Sorokina
Rich Caruana
Mirek Riedewald
Daniel Fink

title: Detecting statistical interactions with additive groves of trees

venue: In Proceedings of the 25th international conference on Machine learning,

authors:
Mukund Sundararajan
Ankur Taly
Qiqi Yan

title: Axiomatic attribution for deep networks

authors:
Ian Tenney
Dipanjan Das
Ellie Pavlick. Bert

title: rediscovers the classical nlp pipeline

venue: In Association for Computational Linguistics,

authors:
Michael Tsang
Dehua Cheng
Yan Liu

title: Detecting statistical interactions from neural network weights

venue: arXiv preprint arXiv:1705.04977,

authors:
Michael Tsang
Youbang Sun
Dongxu Ren
Yan Liu

title: Can i trust you more

venue: model-agnostic hierarchical explanations. ArXiv,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Alex Wang
Kyunghyun Cho
CIFAR Azrieli

title: Global Scholar. Bert has a mouth, and it must speak: Bert as a markov random field language model

venue: NAACL HLT 2019,

authors:
Xiang Zhang
Junbo Zhao
Yann LeCun

title: Character-level convolutional networks for text classification

authors:
Yuhao Zhang
Victor Zhong
Danqi Chen
Gabor Angeli
Christopher D. Manning

title: Positionaware attention and supervised data improve slot filling

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017),

authors:
Alexander Zien
Nicole Krämer
Sören Sonnenburg
Gunnar Rätsch

title: The feature importance ranking measure

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Luisa M Zintgraf
Taco S Cohen
Tameem Adel
Max Welling

title: Visualizing deep neural network decisions: Prediction difference analysis

heading: 1 INTRODUCTION

text:
Recent advances in deep neural networks have led to impressive results on a range of natural language processing (NLP) tasks, by learning latent, compositional vector representations of text data (Peters et al., 2018; Devlin et al., 2018; Liu et al., 2019b). However, interpretability of the predictions given by these complex, “black box” models has always been a limiting factor for use cases that require explanations of the features involved in modeling (e.g., words and phrases) (Guidotti et al., 2018; Ribeiro et al., 2016). Prior efforts on enhancing model interpretability have focused on either constructing models with intrinsically interpretable structures (Bahdanau et al., 2015; Liu et al., 2019a), or developing post-hoc explanation algorithms which can explain model predictions without elucidating the mechanisms by which model works (Mohseni et al., 2018; Guidotti et al., 2018). Among these work, post-hoc explanation has come to the fore as they can operate over a variety of trained models while not affecting predictive performance of models. Towards post-hoc explanation, a major line of work, additive feature attribution methods (Lundberg & Lee, 2017; Ribeiro et al., 2016; Binder et al., 2016; Shrikumar et al., 2017), explain a model prediction by assigning importance scores to individual input variables. However, these methods are not ideal for explaining phrase-level importance, as phrase importance is often a non-linear combination of the importance of the words in the phrase. Contextual decomposition (CD) (Murdoch et al., 2018) and its hierarchical extension (Singh et al., 2019) go beyond the additive assumption and compute the contribution solely made by a word/phrase to the model prediction (i.e., individual contribution), by decomposing the output variables of the neural network at each layer. Using the individual contribu-
1Project page: https://inklab.usc.edu/hiexpl/
tion scores so derived, these algorithms generate hierarchical explanation on how the model captures compositional semantics (e.g., stress or negation) in making predictions (see Figure 1 for example).
However, despite contextual decomposition methods have achieved good results in practice, what reveals extra importance that emerge from combining two phrases has not been well studied. As a result, prior lines of work on contextual decomposition have focused on exploring model-specific decompositions based on their performance on visualizations. We identify the extra importance from combining two phrases can be quantified by studying how the importance of the combined phrase differs from the sum of the importance of the two component phrases on its own. Similar strategies have been studied in game theory for quantifying the surplus from combining two groups of players (Fujimoto et al., 2006). Following the definition above, the key challenge is to formulate the importance of a phrase on it own, i.e., context independent importance of a phrase. However, we show contextual decomposition do not satisfy this context independence property mathematically.
To this end, we propose a formal way to quantify the importance of each individual word/phrase, and develop effective algorithms for generating hierarchical explanations based on the new formulation. To mathematically formalize and efficiently approximate context independent importance, we formulate N -context independent importance of a phrase, defined as the difference of model output after masking out the phrase, marginalized over all possible N words surrounding the phrase in the sentence. We propose two explanation algorithms according to our formulation, namely the Sampling and Contextual Decomposition algorithm (SCD), which overcomes the weakness of contextual decomposition algorithms, and the Sampling and OCclusion algorithm (SOC), which is simple, model-agnostic, and performs competitively against prior lines of algorithms. We experiment with both LSTM and fine-tuned Transformer models to evaluate the proposed methods. Quantitative studies involving automatic metrics and human evaluation on sentiment analysis and relation extraction tasks show that our algorithms consistently outperform competitors in the quality of explanations. Our algorithms manage to provide hierarchical visualization of compositional semantics captured by models, extract classification rules from models, and help users to trust neural networks predictions.
In summary, our work makes the following contributions: (1) we identify the key challenges in generating post-hoc hierarchical explanations and propose a mathematically sound way to quantify context independent importance of words and phrases for generating hierarchical explanations; (2) we extend previous post-hoc explanation algorithm based on the new formulation of N -context independent importance and develop two effective hierarchical explanation algorithms; and (3) experiments demonstrate that the proposed explanation algorithms consistently outperform the compared methods (with both LSTM and Transformer as base models) over several datasets and models.

heading: 2 PRELIMINARIES

heading: 2.1 POST-HOC EXPLANATIONS OF NEURAL SEQUENCE MODELS

text:
We consider a sequence of low-dimensional word embeddings x1:T := (x1,x2, ...,xT ), or denoted as x for brevity, as the input to a neural sequence model, such as standard RNNs, LSTM (Hochreiter
& Schmidhuber, 1997) and Transformers (Vaswani et al., 2017). These neural models extract hidden representations h1:T from the input sequence x, and feed these hidden representations to a prediction layer to generate prediction scores in the label space (e.g., sentiment polarity of a sentence). For LSTM, we use the last hidden state hT to give unnormalized prediction scores s(x) ∈ Rdc over dc label classes as follows.
s(x) =WlhT , (1)
whereWl ∈ Rdc×dh is a trainable weight matrix. For Transformers, the representation corresponding to the [CLS] token at the final layer is fed to the prediction layer to generate scores s(x).
Towards post-hoc explanation of s(x), a notable line of work, additive feature attribution methods (Ribeiro et al., 2016; Shrikumar et al., 2017; Sundararajan et al., 2017; Lundberg & Lee, 2017), measure word-level importance to the model prediction s(x) by attributing an importance score φ(xi,x) to each word in the input sequence xi ∈ x. However, the additive assumption hinders these methods from explaining the complex interactions between words and compositional semantics in a sentence (e.g., modeling negation, transition, and emphasis in sentiment classification), as shown in Figure 1.

heading: 2.2 HIERARCHICAL EXPLANATIONS VIA CONTEXTUAL DECOMPOSITION

text:
To caputure non-linear compositional semantics, the line of work on contextual decomposition (CD) (Murdoch et al., 2018) designs non-additive measures of importance from individual words/phrases to the model predictions, and further extend to agglomerative contextual decomposition (ACD) algorithm (Singh et al., 2019) for generating hierarchical explanations.
Given a phrase p = xi:j in the input sequence x, contextual decomposition (CD) attributes a score φ(p,x) as the contribution solely from p to the model’s prediction s(x). Note that φ(p,x) does not equal to the sum of the scores of each word in the phrase, i.e., φ(p,x) 6= ∑ xi∈p φ(xi,x). Starting from the input layer, CD iteratively decomposes each hidden state h of the model into the contribution solely made by p, denoted as β, and the contributions involving the words outside the phrase p, denoted as γ, with the relation h = β+γ holds. The algorithm also keeps the contribution from the bias term, denoted as ζ, temporally before element-wise multiplication.
For a linear layer h =Wixt+ bi with input xt, when xt lies in the given phrase p, the contribution solely from xt to h is defined as β = Wixt when xt is part of the phrase (i.e., xt ∈ p), and the contribution involving other words in the sentences (denoted as x\p) is defined as γ = 0. The contribution of the bias term ζ is thus bi. When xt lies outside of the phrase, γ is quantified as Wixt and β is 0. In the cases when CD encounters element-wise multiplication operations h = ha hb (e.g., in LSTMs), it eliminates the multiplicative interaction terms which involve the information outside of the phrase p. Specifically, suppose that ha and hb have been decomposed as ha = βa + γa + ζa and hb = βb + γb + ζb, CD computes the β term for ha hb as β = βa βb + βa ζb + ζa βb. When dealing with non-linear activation h′ = σ(h), CD computes the contribution solely from the phrase p as the average activation differences caused β supposing γ is present or absent,
β′ = 1 2 [σ(β + γ + ζ)− σ(γ + ζ)] + 1 2 [σ(β + ζ)− σ(ζ)]. (2)
Following the strategies introduced above, CD decomposes all the intermediate outputs starting from the input layer, until reaching the final output of the model hT = β + γ. The logit score Wlβ is treated as the contribution of the given phrase p to the final prediction s(x).
As a follow-up study, Singh et al. (2019) extends CD algorithm to other families of neural network architectures, and proposes agglomerative contextual decomposition algorithm (ACD). The decomposition of activation functions is modified as β′ = σ(β). For a linear layer h′ = Wh + b with its decomposition h = β + γ, the bias term b is decomposed proportionally and merged into the β′ term of h′, based on β′ =Wβ + |Wβ|/(|Wβ|+ |Wγ|) · b.

heading: 3 METHODOLOGY

text: In this section, we start by identifying desired properties of phrase-level importance score attribution for hierarchical explanations. We propose a measure of context-independent importance of a phrase and introduce two explanation algorithms instantiated from the proposed formulation.

heading: 3.1 PROPERTIES OF IMPORTANCE ATTRIBUTION FOR HIERARCHICAL EXPLANATION

text:
Despite the empirical success of CD and ACD, no prior works analyze what common properties a score attribution mechanism should satisfy to generate hierarchical explanations that reveal compositional semantics formed between phrases. Here we identify two properties that an attribution method should satisfy to generate informative hierarchical explanations.
Non-additivity. Importance of a phrase φ(p,x) should not be a sum over the importance scores of all the component words xi ∈ p, i.e., φ(p,x) 6= ∑ xi∈p φ(xi,x), in contrast to the family of additive feature attribution methods. The property is also suggested by Murdoch et al. (2018).
Context Independence. For deep neural networks, when two phrases combine, their importance to predicting a class may greatly change. The surplus by combining two phrases can be quantified by the difference between the importance of the combined phrase and the sum of the importance of two phrases on its own. It follows the definition of marginal interactions (Fujimoto et al., 2006) in game theory. According to the definition, the importance of two component phrases should be at least evaluated independently to each other. Formally, if we are only interested in how combining two phrases p1 and p2 contribute to a specific prediction for an input x, we expect for input sentences x̃ where only p2 is replaced to another phrase, the importance attribution for p1 remains the same, i.e., φ(p1,x) = φ(p1, x̃). In our bottom-up hierarchical explanation setting, we are interested in how combining a phrase and any other contextual words or phrases in the input x contribute. Therefore, we expect φ(p,x) = φ(p, x̃) given the phrase p in two different contexts x and x̃.
Limitations of CD and ACD. Unfortunately, while CD and ACD try to construct decomposition so that β terms represent the contributions solely from a given a phrase, the assigned importance scores by these algorithms do not satisfy the context independence property mathematically. For CD, we see the computation of β involves the γ term of a specific input sentence in Eq. 2 (see Figure 2(a) for visualization). Similarly, for ACD, the decomposition of the bias term involves the γ terms of a specific input sentence. As a result, the β terms computed by both algorithms depend on the context of the phrase p.
Given the limitation of prior works, we start by formulating a importance measure of phrases that satisfies both non-additivity and context independence property.

heading: 3.2 CONTEXT-INDEPENDENT IMPORTANCE

text:
Given a phrase p := xi:j appearing in a specific input x1:T , we first relax our setting and define the importance of a phrase independent of contexts of length N adjacent to it. The N-context independent importance is defined as the output difference after masking out the phrase p, marginalized over all the possible contexts of length N , denoted as x̂δ , around p in the input x. For an intuitive example, to evaluate the context independent importance up to one word of very in the sentence The film is very interesting in a sentiment analysis model, we sample some possible adjacent words before and after the word very, and average the prediction difference after some practice of masking the word very. Figure 2 illustrates an example for the sampling and masking steps. The N -context independent importance is formally written as,
φ(p, x̂) = Exδ [s(x−δ; x̂δ)− s(x−δ\p; x̂δ)], (3)
where x−δ denotes the resulting sequence after masking out a context of length N surrounding the phrase p from the input x. Here, x̂δ is a sequence of length N sampled from a distribution p(x̂δ|x−δ), which is conditioned on the phrase p as well as other words in the sentence x. Accordingly, we use s(x−δ; x̂δ) to denote the model prediction score after replacing the masked-out context x−δ with a sampled context x̂δ . We use x\p to denote the operation of masking out the phrase p from the input sentence x. The specific implementation of this masking out operation varies across different explanation algorithms.
Following the notion of N -context independent importance, we define context-independent importance of a phrase p by increasing the size of the context N to sufficiently large (e.g., length of the sentence). The context independent importance can be equivalently written as follows.
φg(p) = Ex[s(x)− s(x\p)|p ⊆ x]. (4)
While it is possible to compute the expectations in Eqs. 3 and 4 by sampling from the training set, it is common that a phrase occurs sparsely in the corpus. Therefore, we approximate the N -context independent importance by sampling from a language model pretrained on the training corpus. The language model helps model a smoothed distribution of p(x̂δ|x−δ). In practice, all our explanation algorithms make use of N -context independent importance following Eq. 3, where the size of the neighborhood N is a parameter to be specified to approximate the context independent importance.

heading: 3.3 SAMPLING AND CONTEXTUAL DECOMPOSITION ALGORITHM

text:
In CD, the desirable context independence property is compromised when computing decomposition of activation functions, as discussed in Section 3.1. Following the new formulation of contextindependent importance introduced in Section 3.2, we present a simple modification of the contextual decomposition algorithm, and develop a new sampling and contextual decomposition (SCD) algorithm for effective generation of hierarchical explanations.
SCD is a layer-wise application of our formulation. The algorithm only modifies the way to decompose activation functions in CD. Specifically, given the output h = s(l)(x) at an intermediate layer l with the decomposition h = β + γ, we decompose the activation value σ(h) into β′ + γ′, with the following definition:
β′ = Eγ∼p(γ|x−δ)[σ(β + γ)− σ(γ)] = Eh∼p(h|x−δ)[σ(h)− σ(h− β)], (5)
i.e., β′ is defined as the expected difference between the activation values when the β term is present or absent. h is computed for different input sequences x with the contexts of the phrase p sampled from the distribution p(x̂δ|x−δ). Eq. 5 is a layer wise application of Eq. 4, where the masking operation is implemented with calculating σ(h − β). Figure 2(b) provides a visualization for the decomposition.
Algorithmic Details. To perform sampling, we first pretrain a LSTM language model from two directions on the training data. During sampling, we mask the words that are not conditioned in p(x̂δ|x−δ). Some other sampling options include performing Gibbs sampling from a masked language model (Wang et al., 2019). The algorithm then obtain a set of samples S by sampled from the language model. For each sample in S, the algorithm records the input of the i-th non-linear activation function to obtain a sample set S(i)h . During the explanation, the β term of the i-th non-linear
activation function is calculated as,
β′ = 1
|S(i)h | ∑ h∈S(i)h [σ(h)− σ(h− β)]. (6)
Some neural models such as Transformers involve operations that normalize over different dimensions of a vectors, e.g. layer normalization operations. We observe improved performance by not decomposing the normalizer of these terms when the phrase p is shorter than a threshold, assuming that the impact of p to the normalizer can be ignored. Besides, for element-wise multiplication in LSTM models, we treat them in the same way as other non-linear operations and decompose them as Eq. 5, where the decomposition of h1 h2 is written as β′ = Eγ1,γ2 [(β1+γ1) (β2+γ2)−γ1 γ2]. We avoid decomposing softmax functions.

heading: 3.4 SAMPLING AND OCCLUSION ALGORITHM

text:
We show it is possible to fit input occlusion (Li et al., 2016) algorithm into our formulation. Input occlusion algorithm calculate the importance of p specific to an input sentence x by observing the prediction difference caused by replacing the phrase p with padding tokens, noted as 0p,
φ(p,x) = s(x)− s(x−p;0p) (7)
It is obvious that the importance score obtained by the input occlusion algorithm is dependent on the all the context words of p in x. To eliminate the dependence, we sample the context around the phrase p. This leads to the Sampling and Occlusion (SOC) algorithm, where the importance of phrases is defined as the expected prediction difference after masking the phrase for each replacement of contexts.
Algorithmic Details. Similar to SCD, SOC samples neighboring words x̂δ from a trained language model p(x̂δ|x−δ) and obtain a set of neighboring word replacement S . For each replacement x̂δ ∈ S , the algorithm computes the model prediction differences after replacing the phrase p with padding tokens. The importance φ(p,x) is then calculated as the average prediction differences. Formally, the algorithm calculates,
φ(p,x) = 1 |S| ∑ x̂δ∈S [s(x−δ; x̂δ)− s(x−{δ,p}; x̂δ;0p)]. (8)
Sampling and Occlusion is advantageous in that it is model-agnostic and easy to implement. The input occlusion algorithm inside Eq. 8 can also be replaced with other measure of phrase importance, such as Shapley values (Shapley, 1953), with the phrase p and other input words considered as players. We expect it is helpful for longer sequences when there are multiple evidences outside the context region saturating the prediction.

heading: 4 EXPERIMENTS

text:
We evaluate explanation algorithms on both shallow LSTM models and deep fine-tuned BERT Transformer (Devlin et al., 2018) models. We use two sentiment analysis datasets, namely the Stanford Sentiment Treebank-2 (SST-2) dataset (Socher et al., 2013) and the Yelp Sentiment Polarity dataset (Zhang et al., 2015), as well as TACRED relation extraction dataset (Zhang et al., 2017) for experiments. The two tasks are modeled as binary and multi-class classification tasks respectively. For the SST-2 dataset, while it provides sentiment polarity scores for all the phrases on the nodes of the constituency parsing trees, we do not train our model on these phrases, and use these scores as the evaluation for the phrase level explanations. Our Transformer model is fine-tuned from pretrained BERT (Devlin et al., 2018) model. See Appendix A for other implementation details.
Compared Methods. We compare our explanation algorithm with following baselines: Input occlusion (Li et al., 2016) and Integrated Gradient+SHAP (GradSHAP) (Lundberg & Lee, 2017); two algorithms applied for hierarchical explanations, namely Contextual Decomposition (CD) (Murdoch et al., 2018), and Agglomerative Contextual Decomposition (ACD) (Singh et al., 2019). We
also compare with a naive however neglected baseline in prior literature, which directly feed the given phrase to the model and take the prediction score as the importance of the phrase, noted as Direct Feed. In BERT models, Direct Feed is implemented by turning off the attention mask of words except the [CLS] token and the phrase to be explained. For our algorithms, we list the performance of corpus statistic based approach (Statistic) for approximating context independent importance in Eq. 3, Sampling and Contextual Decomposition (SCD), and Sampling and Occlusion (SOC) algorithm. In section 4.4, we also consider padding instead of sampling the context words in SCD and SOC.

heading: 4.1 HIERARCHICAL VISUALIZATION OF IMPORTANT WORDS AND PHRASES

text:
We verify the performance of our algorithms in identifying important words and phrases captured by models. We follow the quantitative evaluation protocol proposed in CD algorithm (Murdoch et al., 2018) for evaluating word-level explanations, which computes Pearson correlation between the coefficients learned by a linear bag-of-words model and the importance scores attributed by explanation methods, also noted as the word ρ. When the linear model is accurate, its coefficients could stand for general importance of words. For evaluating phrase level explanations, we notice the SST-2 dataset provides human annotated real-valued sentiment polarity for each phrase on constituency parsing trees. We generate explanations for each phrase on the parsing tree and evaluate the Pearson correlation between the ground truth scores and the importance scores assigned for phrases, also noted as the phrase ρ. We drawK = 20 samples forN = 10 words adjacent to the phrase to be explained at the sampling step in our SOC and SCD algorithms. The parameter setting is trade-off between the efficiency and performance. See Section 4.4 for detailed parameter analysis.
Table 1 shows word ρ and phrase ρ achieved by our algorithms and competitors. Generally, explanation algorithms that follow our formulations achieve highest word ρ and phrase ρ for all the datasets and models. SOC and SCD perform robustly on the deep Transformer model, achieving higher word

heading: He is also survived by S-PERSON parents and a sister , O-PERSON , of Washington , and

text:
ρ and phrase ρ than input occlusion and contextual decomposition algorithms by a large margin. We see the simple Direct Feed method provide promising results on shallow LSTM networks, but fail in deeper Transformer models. The statistic based approximation of the context independent importance, which do not employ a trained sampler, yields competitive words ρ but low phrase ρ. Our analysis show that it is common that a long phrase does not exist in previously seen examples. In this case, phrase ρ achieved by statistic based approximation is pushed towards that of the input occlusion algorithm.
Qualitative study also shows that our explanation visualize complicated compositional semantics captured by models, such as positive segments in the negative example, and adversative conjunctions connected with “but”. We present an example explanation provided by SOC algorithm in Figure 3 and Appendix.

heading: 4.2 EXPLANATION AS CLASSIFICATION PATTERN EXTRACTION FROM MODELS

text: We show our explanation algorithm is a nature fit for extracting phrase level classification rules from neural classifiers. With the agglomerative clustering algorithm in Singh et al. (2019), our explanation effectively identify phrase-level classification patterns without evaluating all possible phrases in the sentence even when a predefined hierarchy does not exist. Figure 4 show an example of automatically constructed hierarchy and extracted classification rules in an example in the TACRED dataset.

heading: 4.3 ENHANCING HUMAN TRUST OF MODELS

text: We follow the human evaluation protocol in Singh et al. (2019) and study whether our explanations help subjects to better trust model predictions. We ask subjects to rank the provided visualizations based on how they would like to trust the model. For the SST-2 dataset, we show subjects the predictions of the fine-tuned BERT model, and the explanations generated by SOC, SCD, ACD and GradSHAP algorithms for phrases. The phrase polarities are visualized in a hierarchy with the provided parsing tree of each sentence in the dataset. For the TACRED dataset, we show the explanations provided by SOC, SCD, CD and Direct Feed algorithms on the LSTM model. We binarilize the importance of a phrase by calculating the difference between its importance to the predicted class and the its top importance to other classes, and the hierarchies are constructed automatically with agglomerative clustering (Singh et al., 2019). Figure 5 shows average ranking score of explanations, where 4 for the best, and 1 for the worst. On the SST-2 dataset, SOC achieves significantly higher ranking score than ACD and GradSHAP, showing a p-value less than 0.05 and 0.001 respectively. On the TACRED dataset, SCD achieve the best ranking score, showing significantly better ranking score than CD and Direct Feed with a p-value less than 10−6 .

heading: 4.4 PARAMETER ANALYSIS

text: Both SOC and SCD algorithms require specifying the size of the context region N and the number of samples K. In Figure 6 (also Figure 7 in Appendix) we show the impact of these parameters. We also plot the performance curves when we pad the contexts instead of sampling. We see sampling the context achieves much better performance than padding the context given a fixed size of the context region N . We also see word ρ and phrase ρ increase as the number of samples K increases. The overall performance also increases as the size of the context region N increases at the early stage, and saturates when N grows large, which is consistent with our hypothesis that words or phrases usually do not interact with the words that are far away them in the input.

heading: 5 RELATED WORKS

text:
Interpretability of neural networks has been studied with vairous techniques, including probing learned features with auxiliary tasks (Tenney et al., 2019), or designing models with inherent interpretability (Bahdanau et al., 2015; Lei et al., 2016). A major line of work, local explanation algorithms, explains predictions by assigning importance scores for input features. This line of work include input occlusion (Kádár et al., 2017), gradient based algorithms (Simonyan et al., 2013; Hechtlinger, 2016; Ancona et al., 2017), additive feature attribution methods (Ribeiro et al., 2016; Shrikumar et al., 2017; Sundararajan et al., 2017), among which Shapley value based approaches (Lundberg & Lee, 2017) have been studied intensively because of its good mathematical properties. In the context of input occlusion explanations, researchers also study how to efficiently marginalize over input features to be explained (Zintgraf et al., 2017; Chang et al., 2019), while our research show extra focus could be placed on marginalizing over contexts. Regarding explanations of models with structured inputs, Chen et al. (2019) propose L-Shapley and C-Shapley for efficient approximation of Shapley values, with a similar hypothesis with us that the importance of a word is usually only strongly dependent on its neighboring contexts. Chen et al. (2018) propose a feature selection based approach for explanation in an information theoretic perspective.
On the other hand, global explanation algorithms (Guidotti et al., 2018) have also been studied for identifying generally important features, such as Feature Importance Ranking Measure (Zien et al., 2009), Accumulated Local Effects (Apley, 2016), while usually restricted in the domain of tabular data. We note that the context independence property in our proposed methods implies we study hierarchical explanation as a global explanation problem (Guidotti et al., 2018). Compared with local explanation algorithms, global explanation algorithms are less studied for explaining individual predictions (Poerner et al., 2018), because they reveal the average behavior of models. However, with a hierarchical organization, we show global explanations are also powerful at explaining individual predictions, achieving better human evaluation scores and could explain compositional semantics where local explanation algorithms such as additive feature attribution algorithms totally fail. Moreover, we note that the use of explanation algorithms is not exclusive; we may apply explanation algorithms of different categories to make a more holistic explanation of model predictions.
Another closely related field is statistical feature interaction detection (Hooker, 2004; Sorokina et al., 2008; Tsang et al., 2017) from learned models, which usually focus on tabular data only. An exception is (Tsang et al., 2018), which also studies word interactions in neural sequence model predictions, but does not study interactions in a phrase level.

heading: 6 CONCLUSION

text: In this work, we identify two desirable properties for informative hierarchical explanations of predictions, namely the non-additivity and context-independence. We propose a formulation to quantify context independent importance of words and phrases that satisfies the properties above. We revisit the prior line of works on contextual decomposition algorithms, and propose Sampling and Contextual Decomposition (SCD) algorithm and Sampling and Occlusion algorithm (SOC). Experiments on multiple datasets and models show that our explanation algorithms generate informative hierarchical explanations, help to extract classification rules from models, and enhance human trust of models.

heading: ACKNOWLEDGEMENTS

text: This research is based upon work supported in part by NSF SMA 18-29268 and JP Morgan AI Research Award. We would like to thank all the collaborators in USC INK research lab for their constructive feedback on the work.

heading: B PERFORMANCE ON ADVERSARIAL MODELS

text:
For computing context independent importance of a phrase, an intuitive and simple alternative approach, which is nevertheless neglected in prior literature, is to only feed the input to the model and treat the prediction score as the explanation. In Table 1, while the score of the Direct Feed is lower than that of the best performing algorithms, the score is rather competitive.
The potential risk of this explanation is that it assumes model performs reasonably on incomplete sentence fragments that are significantly out of the data distribution. As a result, the explanation of short phrases can be misleading. To simulate the situation, we train a LSTM model on inversed labels on isolate words, in addition to the original training instances. The model could achieve the same accuracy as the original LSTM model. However, the word ρ and the phrase ρ of Direct Feed drop by a large margin, showing a word ρ of -0.38 and 0.09. SOC and SCD are still robust on the adverse LSTM model, both showing a word ρ and phrase ρ of more than 0.60 and 0.55.
The masking operation could also cause performance drop because the masked sentence can be out of data distribution when explaining long phrases. For SOC, the risk can be resolved by implementing the masking operation of the phrase p by another round of sampling from a language model conditioned on its context x−p, but we do not find empirical evidence showing that it improves performance.
C EXPLANATION HEATMAPS

title: TOWARDS HIERARCHICAL IMPORTANCE ATTRIBU-