text:
\section{Introduction}

\setlength{\abovedisplayskip}{3pt}
\setlength{\abovedisplayshortskip}{1pt}
\setlength{\belowdisplayskip}{3pt}
\setlength{\belowdisplayshortskip}{1pt}
\setlength{\jot}{3pt}
\setlength{\textfloatsep}{3pt}

Modern machine learning models, including random forests, deep neural
networks, and kernel methods, can produce high-accuracy prediction in
many applications.  Often however, the accuracy in prediction from
such black box models, comes at the cost of interpretability.  Ease of
interpretation is a crucial criterion when these tools are applied in
areas such as medicine, financial markets, and criminal justice; for
more background, see the discussion paper by
Lipton~\cite{lipton2016mythos} as well as references therein.

In this paper, we study instancewise feature importance scoring as a
specific approach to the problem of interpreting the predictions of
black-box models.  Given a predictive model, such a method yields, for
each instance to which the model is applied, a vector of importance
scores associated with the underlying features.  The instancewise
property means that this vector, and hence the relative importance
of each feature, is allowed to vary across instances. Thus, the
importance scores can act as an explanation for the specific instance,
indicating which features are the key for the model to make its
prediction on that instance.

There is now a large body of research focused on the problem of
scoring input features based on the prediction of a given instance
(for instance, see the
papers~\cite{shrikumar2016not,bach2015pixel,ribeiro2016should,lundberg2017unified,vstrumbelj2010efficient,baehrens2010explain,datta2016algorithmic,sundararajan2017axiomatic}
as well as references therein).  Of most relevance to this paper is a
line of recent
work~\cite{vstrumbelj2010efficient,lundberg2017unified,datta2016algorithmic}
that has developed methods for model interpretation based on Shapley
value~\cite{shapley1953value} from cooperative game theory.  The
Shapley value was originally proposed as an axiomatic characterization
of a fair distribution of a total surplus from all the players, and
can be applied in to predictive models, in which case each feature is
modeled as a player in the underlying game.  While the Shapley value
approach is conceptually appealing, it is also computationally
challenging: in general, each evaluation of a Shapley value requires
an exponential number of model evaluations.  Different approaches to
circumventing this complexity barrier have been proposed, including
those based on Monte Carlo
approximation~\cite{vstrumbelj2010efficient,datta2016algorithmic} and
methods based on sampled least-squares with
weights~\cite{lundberg2017unified}.

In this paper, we take a complementary point of view, arguing that the
problem of explanation is best approached within a model-based
paradigm.  In this view, explanations are cast in terms of a model,
which may or may not be the same model as used to fit the
data. Criteria such as Shapley value, which are intractable to compute
when no assumptions are made, can be more effectively computed or
approximated within the framework of a model. We focus specifically on
settings in which a graph structure is appropriate for the data;
specifically, we consider simple chains and grids, appropriate for
time series and images, respectively. We propose two measures for
instancewise feature importance scoring in this framework, which we
term \emph{L-Shapley} and \emph{C-Shapley}; here the abbreviations
``L" and ``C" refer to ``local'' and ``connected,'' respectively.  By
exploiting the underlying graph structure, the number of model
evaluations is reduced to linear---as opposed to exponential---in the
number of features. We demonstrate the relationship of these measures
with a constrained form of Shapley value, and we additionally relate
C-Shapley with another solution concept from cooperative game theory,
known as the Myerson value~\cite{myerson1977graphs}.  The Myerson
value is commonly used in graph-restricted games, under a local
additivity assumption of the model on disconnected subsets of
features. Finally, we apply our feature scoring methods to several
state-of-the-art models for both language and image data, and find
that our scoring algorithms compare favorably to several existing
sampling-based algorithms for instancewise feature importance scoring.

The remainder of this paper is organized as follows.  We begin in
Section~\ref{SecBackground} with background and set-up for the problem
to be studied.  In Section~\ref{SecMethods}, we describe the two
methods proposed and analyzed in this paper, based on the L-Shapley
and C-Shapley scores.  Section~\ref{sec:prop} is devoted to a study of
the relationship between these scores and the Myerson value.  In
Section~\ref{SecExperiments}, we evaluate the performance of L-Shapley
and C-Shapley on various real-world data sets, and we conclude with a
discussion in Section~\ref{SecDiscussion}.

\section{Background and preliminaries}
\label{SecBackground}

We begin by introducing some background and notation.

\subsection{Importance of a feature subset}
\label{sec:importance}

We are interested in studying models that are trained to perform
prediction, taking as input a feature vector \mbox{$x \in \mathcal{X} \subset
  \ensuremath{\mathbb{R}}^d$} and predicting a response or output variable $y \in \mathcal{Y}$.
We assume access to the output of a model via a conditional
distribution, denoted by $\ensuremath{\Prob_m}(\cdot |x)$, that provides the
distribution of the response $Y \in \mathcal{Y}$ conditioned on a given vector
$X = x$ of inputs.  For any given subset $S \subset \{1, 2, \ldots, d
\}$, we use $x_S = \{ x_j, j \in S \}$ to denote the associated
sub-vector of features, and we let $\ensuremath{\Prob_m}(Y \mid x_S)$ denote the
induced conditional distribution when $\ensuremath{\Prob_m}$ is restricted to
using only the sub-vector $x_S$.  In the cornercase in which $S =
\emptyset$, we define \mbox{$\ensuremath{\Prob_m}(Y \mid x_\emptyset)\ensuremath{: \, = }
  \ensuremath{\Prob_m}(Y)$.}  In terms of this notation, for a given feature
vector $x \in \mathcal{X}$, subset $S$ and fitted model distribution
$\ensuremath{\Prob_m}(Y \mid x)$, we introduce the \emph{importance score}
\begin{align*}
v_x(S) \ensuremath{: \, = } \ensuremath{\Exp_m} \left[ -\log\frac{1}{\ensuremath{\Prob_m}(Y \mid x_S)} \;
  \Big| \; x \right],
\end{align*}
where $\ensuremath{\Exp_m}[\cdot \mid x]$ denotes the expectation over
$\ensuremath{\Prob_m}(\cdot \mid x)$.  The importance score $v_x(S)$ has a
coding-theoretic interpretation: it corresponds to the negative of the
expected number of bits required to encode the output of the model
based on the sub-vector $x_S$.  It will be zero when the model makes a
deterministic prediction based on $x_S$, and larger when the model
returns a distribution closer to uniform over the output space.

There is also an information-theoretic interpretation to this
definition of importance scores, as discussed in our previous work~\cite{chen2018learning}.  In particular, suppose that for a given
integer $k<d$, there is a function $x \mapsto S^*(x)$ such that, for
all almost all $x$, the $k$-sized subset $S^*(x)$ maximizes $v_x(S)$
over all subsets of size $k$.  In this case, we are guaranteed that
the mutual information $I(X_{S^*(X)},Y)$ between $X_{S^*(X)}$ and $Y$
is maximized, over any conditional distribution that generates a
subset of size $k$ given $X$. The converse is also true.

In many cases, class-specific importance is favored, where one is
interested in seeing how important a feature subset $S$ is to the
predicted class, instead of the prediction as a conditional
distribution. In order to handle such cases, it is convenient to
introduce the degenerate conditional distribution
\begin{align*}
\ensuremath{\hat{\Prob}_m}(y\mid x) & \ensuremath{: \, = } \begin{cases} 1 \text{ if } y \in \arg
  \max \limits_{y'} \ensuremath{\Prob_m}(y'\mid x), \\ 0 \text{ otherwise.}
\end{cases}
\end{align*}
We can then define the importance of a subset $S$ with respect to
$\ensuremath{\hat{\Prob}_m}$ using the modified score
\begin{align*}
 v_x(S) &\ensuremath{: \, = } \ensuremath{\hat{\Exp}_m} \left[ -\log\frac{1}{\ensuremath{\Prob_m}(Y \mid
     x_S)} \; \Big| \; x \right],
 \end{align*}
which is the expected log probability of the predicted class given the
features in $S$.

\paragraph{Estimating the conditional distribution:}

In practice, we need to estimate---for any given feature vector $\ensuremath{\bar{x}}
\in \mathcal{X}$---the conditional probability functions $\ensuremath{\Prob_m}(y \mid
\ensuremath{\bar{x}}_S)$ based on observed data.  Past work has used one of two
approaches: either estimation based on empirical
averages~\cite{vstrumbelj2010efficient}, or plug-in estimation using a
reference point~\cite{datta2016algorithmic,lundberg2017unified}. \\

\noindent \emph{Empirical average estimation}: In this approach, we
first draw a set of feature vector $\{x^j\}_{j=1}^M$ by sampling with
replacement from the full data set.  For each sample $x^j$, we define
a new vector $\tilde x^j \in \ensuremath{\mathbb{R}}^d$ with components
\begin{align*}
  (\tilde x_j)_i & = \begin{cases} \ensuremath{\bar{x}}_i & \mbox{if $i \in S$, and} \\
    x^j_i & \mbox{otherwise.}
  \end{cases}
\end{align*}
Taking the empirical mean of $\ensuremath{\Prob_m} (y\mid \tilde x^j)$ over
$\{\tilde x^j\}$ is then used as an estimate of $\ensuremath{\Prob_m} (y\mid
\ensuremath{\bar{x}}_S)$.\\

\noindent \emph{Plug-in estimation}: In this approach, the first step
is to specify a reference vector $x^0\in\ensuremath{\mathbb{R}}^d$ is specified. We then
define the vector $\tilde x\in\ensuremath{\mathbb{R}}^d$ with components
\begin{align*}
  (\tilde x)_i & = \begin{cases} \ensuremath{\bar{x}}_i & \mbox{if $i \in S$, and} \\
    %
    x^0_i & \mbox{otherwise}.
  \end{cases}
\end{align*}
Finally, we use the conditional probability $\ensuremath{\Prob_m} (y\mid \tilde
x)$ as an approximation to $\ensuremath{\Prob_m} (y\mid \ensuremath{\bar{x}}_S)$. The plug-in
estimate is more computationally efficient than the empirical average
estimator, and works well when there exist appropriate choices of
reference points. We use this method for our experiments, where we use
the index of padding for language data, and the average pixel strength
of an image for vision data.

\subsection{Shapley value for measuring interaction between features}
\label{sec:shapleyvalue}

Consider the problem of quantifying the importance of a given feature
index $i$ for feature vector $x$.  A naive way of doing so would be by
computing the importance score $v_x(\{i\})$ of feature $i$ on its own.
However, doing so ignores interactions between features, which are
likely to be very important in applications.  As a simple example,
suppose that we were interested in performing sentiment analysis on
the following sentence:
\begin{align}
\tag{$\star$}\label{example}
\emph{It is not heartwarming or entertaining. It just sucks.}
\end{align}
This sentence is contained in a movie review from the IMDB movie data
set \cite{maas2011learning}, and it is classified as negative
sentiment by a machine learning model to be discussed in the
sequel. Now suppose we wish to quantify the importance of feature
\quoting{not} in prediction. The word \quoting{not} plays an important
role in the overall sentence as being classified as negative, and thus
should be attributed a significant weight.  However, viewed in
isolation, the word \quoting{not} has neither negative nor positive
sentiment, so that one would expect that $v_x(\{\quoting{not}\})
\approx 0$.

Thus, it is essential to consider the interaction of a given feature
$i$ with other features. For a given subset $S$ containing $i$, a
natural way in which to assess how $i$ interacts with the other
features in $S$ is by computing the difference between the importance
of all features in $S$, with and without $i$.  This difference is
called the \emph{marginal contribution} of $i$ to $S$, and given by
\begin{align}
m_x(S,i) \ensuremath{: \, = } v_x(S) - v_x(S\setminus\{i\}).
\end{align}
In order to obtain a simple scalar measure for feature $i$, we need to
aggregate these marginal contributions over all subsets that contain
$i$.  The \emph{Shapley value}~\cite{shapley1953value} is one
principled way of doing so.  For each integer $k = 1, \ldots, d$, we
let $\mathcal{S}_k(i)$ denote the set of $k$-sized subsets that
contain $i$.  The Shapley value is obtained by averaging the marginal
contributions, first over the set $\mathcal{S}_k(i)$ for a fixed $k$,
and then over all possible choices of set size $k$:
\begin{align}
\label{eq:shapley}
\phi_x(\ensuremath{\Prob_m},i) \ensuremath{: \, = } \underbrace{\frac{1}{d}
  \sum_{k=1}^{d}}_{\mbox{Average over $k$}} \underbrace{
  \frac{1}{\binom{d-1}{k-1}} \sum_{S \in
    \mathcal{S}_k(i)}}_{\mbox{Average of over $\mathcal{S}_k(i)$}}
m_x(S,i).
\end{align}
Since the model $\ensuremath{\Prob_m}$ remains fixed throughout our analysis, we
frequently omit the dependence of $\phi_x$ on $\ensuremath{\Prob_m}$, instead
adopting the more compact notation $\phi_x(i)$.

The concept of Shapley value was first introduced in cooperative game
theory~\cite{shapley1953value}, and it has been used in a line of
recent work on instancewise feature importance
ranking~\cite{vstrumbelj2010efficient,datta2016algorithmic,lundberg2017unified}.
It can be justified on an axiomatic basis~\cite{shapley1953value,
  young1985monotonic} as being the unique function from a collection
of $2^d$ numbers (one for each subset $S$) to a collection of $d$
numbers (one for each feature $i$) with the following properties:
\begin{description}[style=unboxed,leftmargin=0cm]
\item[Additivity:] The sum of the Shapley values $\sum_{i=1}^d
  \phi_x(i)$ is equal to the difference $v_x(\{1, \ldots, d\}) -
  v_x(\emptyset)$.
  %
\item[Equal contributions:]  If $v_x(S \cup \{i\}) = v_x(S \cup \{j\})$ for all
  subsets $S$, then $\phi_x(i) = \phi_x(j)$.
  %
\item[Monotonicity:] Given two models $\ensuremath{\Prob_m}$ and $\ensuremath{\Prob_m}$, let $m_x$ and $m_x'$ denote the associated marginal contribution functions, and let $\phi_x$ and $\phi_x'$ denote the associated Shapley values. If $m_x(S, i) \geq m'_x(S, i)$ for all subsets $S$, then we are guaranteed that $\phi_x(i) \geq \phi'_x(i)$.
\end{description}
Note that all three of these axioms are reasonable in our feature
selection context.

\subsection{The challenge with computing Shapley values}

The exact computation of the Shapley value $\phi_x(i)$ takes into
account the interaction of feature $i$ with all $2^{d-1}$ subsets that
contain $i$, thereby leading to computational difficulties. Various
approximation methods have been developed with the goal of reducing
complexity. For example, \citet{vstrumbelj2010efficient} proposed to
estimate the Shapley values via a Monte Carlo approximation built on
an alternative permutation-based definition of the Shapley value.
\citet{lundberg2017unified} proposed to evaluate the model over
randomly sampled subsets and use a weighted linear regression to
approximate the Shapley values based on the collected model
evaluations.

In practice, such sampling-based approximations may suffer from high
variance when the number of samples to be collected per instance is
limited.  For large-scale predictive models, the number of features is
often relatively large, meaning that the number of samples required to
obtain stable estimates can be prohibitively large.  The main
contribution of this paper is to address this challenge in a
model-based paradigm, where the contribution of features to the
response variable respects the structure of an underlying graph.  In
this setting, we propose efficient algorithms and provide bounds on
the quality of the resulting approximation.  As we discuss in more
detail later, our approach should be viewed as complementary to
sampling-based or regresssion-based approximations of the Shapley
value.  In particular, these methods can be combined with the approach
of this paper so as to speed up the computation of the L-Shapley and
C-Shapley values that we propose.

\section{Methods}
\label{SecMethods}

In many applications, the features can be associated with the nodes of
a graph, and we can define distances between pairs of features based
on the graph structure.  More concretely, for sequence data (such as
language, music etc.), each feature vector $x$ can be associated with
a line graph, whereas for image data, each $x$ is naturally associated
with a grid graph.  In this section, we propose modified forms of the
Shapley values, referred to as L-Shapley and C-Shapley values, that
can be computed more efficiently than the Shapley value.  We also show
that under certain probabilistic assumptions on the marginal
distribution over the features, these quantities yield good
approximations to the original Shapley values.

More precisely, given feature vectors $x \in \ensuremath{\mathbb{R}}^d$, we let $G =
(V,E)$ denote a connected graph with nodes $V$ and edges $E\subset
V\times V$, where each feature $i$ is associated with a a node $i \in
V$, and edges represent interactions between features.  The graph
induces a distance function on $V \times V$, given by
\begin{align}
d_G(\ell, m) & = \mbox{number of edges in shortest path joining $\ell$
  to $m$}.
\end{align}
In the line graph, this graph distance corresponds to the number of
edges in the unique path joining them, whereas it corresponds to the
Manhattan distance in the grid graph.  For a given node $i \in V$, its
$k$-\emph{neighborhood} is the set
\begin{align}
  \nbhd{k}{i}
  & \ensuremath{: \, = } \left \{ j \in V \mid d_G(i,j) \leq k \right \}
\end{align}
of all nodes at graph distance at most $k$.  See
Figure~\ref{FigGridStructure} for an illustration for the
two-dimensional grid graph.

\begin{figure}[h]
  \begin{center}
    \begin{tabular}{ccccc}
      \widgraph{0.22\textwidth}{grid_shapley} & \hspace*{.05\textwidth} &
      \widgraph{0.22\textwidth}{grid_shapley_dis} & \hspace*{.05\textwidth} &
      \widgraph{0.22\textwidth}{grid_shapley_con1} \\
      (a) && (b) && (c)
    \end{tabular}
    \caption{In all cases, the red node denotes the target feature
      $i$. (a) Illustration of the $k=2$ graph neighborhood
      $\nbhd{2}{i}$ on the grid graph.  All nodes within the shaded
      gray triangle lie within the neighborhood $\nbhd{2}{i}$. (b) A
      disconnected subset of $\nbhd{2}{i}$ that is summed over in
      L-Shapley but not C-Shapley.  (c) A connected subset of
      $\nbhd{2}{i}$ that is summed over in both L-Shapley and
      C-Shapley.}
    \label{FigGridStructure}
  \end{center}
\end{figure}

We propose two algorithms for the setting in which features that are
either far apart on the graph or features that are not directly
connected, have an accordingly weaker interaction.

\subsection{Local Shapley}

In order to motivate our first graph-structured Shapley score, let us
take a deeper look at Example~\eqref{example}. In order to compute the
importance score of \quoting{not,} the most important words to be
included are \quoting{heartwarming} and \quoting{entertaining.}
Intuitively, the words distant from them have a weaker influence on
the importance of a given word in a document, and therefore have
relatively less effect on the Shapley score.  Accordingly, as one
approximation, we propose the \text{L-Shapley} score, which only
perturbs the neighboring features of a given feature when evaluating
its importance:
\begin{definition}
\label{def:localshapley}
Given a model $\ensuremath{\Prob_m}$, a sample $x$ and a feature $i$, the
\emph{L-Shapley estimate of order $k$} on a graph $G$ is given by
\begin{align}
\hat\phi_x^k(i) & \ensuremath{: \, = } \frac{1}{|\nbhd{k}{i}|} \sum_{ \substack{T \ni
    i \\T \subseteq \nbhd{k}{i} }}
\frac{1}{\binom{|\nbhd{k}{i}|-1}{|T|-1}} m_x(T,i).
\end{align}
\end{definition}
The coefficients in front of the marginal contributions of feature $i$
are chosen to match the coefficients in the definition of the Shapley
value restricted to the neighborhood $\nbhd{k}{i}$. We show in
Section~\ref{sec:prop} that this choice controls the error under
certain probabilistic assumptions. In practice, the choice of the
integer $k$ is dictated by computational considerations. By the
definition of $k$-neighborhoods, evaluating all $d$ L-Shapley scores
on a line graph requires $2^{2k} d$ model evaluations.  (In
particular, computing each feature takes $2^{2k+1}$ model evaluations,
half of which overlap with those of its preceding feature.) A similar
calculation shows that computing all $d$ L-Shapley scores on a grid
graph requires $2^{4k^2} d$ function evaluations.

\subsection{Connected Shapley}

We also propose a second algorithm, C-Shapley, that further reduces
the complexity of approximating the Shapley value. Coming back to
Example~\eqref{example} where we evaluate the importance of
\quoting{not,} both the L-Shapley estimate of order larger than two
and the exact Shapley value estimate would evaluate the model on the
word subset \quoting{It not heartwarming,} which rarely appears in
real data and may not make sense to a human or a model trained on
real-world data. The marginal contribution of \quoting{not} relative
to \quoting{It not heartwarming} may be well approximated by the
marginal contribution of ``not'' to \quoting{not heartwarming.} This
motivates us to proprose \emph{C-Shapley}:
\begin{definition}\label{def:connectedshapley}
Given a model $\ensuremath{\Prob_m}$, a sample $x$ and a feature $i$, the
\emph{C-Shapley estimate of order $k$} on a graph $G$ is given by
\begin{align}
  \label{eq:connected}
\tilde\phi_x^k(i) & \ensuremath{: \, = } \sum_{U \in \mathcal{C}_k(i)}
\frac{2}{(|U|+2)(|U|+1)|U|} m_x(U,i),
\end{align}
where $\mathcal{C}_k(i)$ denotes the set of all subsets of
$\nbhd{k}{i}$ that contain node $i$, and are connected in the graph
$G$.

\end{definition}
The coefficients in front of the marginal contributions are a result of using Myerson value to characterize a new coalitional game over the graph $G$, in which the influence of disconnected subsets of features are additive. The error between C-Shapley and the Shapley value can also be controlled under certain statistical assumptions. See Section~\ref{sec:prop} for details.

For text data, C-Shapley is equivalent to only evaluating n-grams in a
neighborhood of the word to be explained.  By the definition of
$k$-neighborhoods, evaluating the C-Shapley scores for all $d$
features takes $\mathcal O(k^2 d)$ model evaluations on a line graph,
as each feature takes $\mathcal O(k^2)$ model evaluations.

\section{Properties}
\label{sec:prop}

In this section, we study some basic properties of the L-Shapley and
C-Shapley values.  In particular, under certain probabilistic
assumptions on the features, we show that they provide good
approximations to the original Shapley values.  We also show their
relationship to another concept from cooperative game theory, namely
that of Myerson values, when the model satisfies certain local
additivity assumptions.

\subsection{Approximation of Shapley value}

In order to characterize the relationship between L-Shapley and the
Shapley value, we introduce \emph{absolute mutual information} as a
measure of dependence. Given two random variables $X$ and $Y$, the
absolute mutual information $I_a(X;Y)$ between $X$ and $Y$ is defined
as
\begin{align}
I_a(X;Y) = \Exp \left[ \Big|\log \frac{P(X,Y)}{P(X)P(Y)} \Big|
  \right],
\end{align}
where the expectation is taken jointly over $X,Y$. Based on the
definition of independence, we have $I_a(X;Y)=0$ if and only if
$X\independent Y$. Recall the mutual
information~\cite{cover2012elements} is defined as \mbox{$I(X;Y) =
  \Exp [\log \frac{P(X,Y)}{P(X)P(Y)}]$.}  The new measure is more
stringent than the mutual information in the sense that $I(X;Y)\leq
I_a(X;Y)$. The absolute conditional mutual information can be defined
in an analogous way. Given three random variables $X,Y$ and $Z$, we
define the absolute conditional mutual information to be $I_a(X;Y\mid
Z) = \Exp[|\log \frac{P(X,Y\mid Z)}{P(X\mid Z)P(Y\mid Z)}|]$,
where the expectation is taken jointly over $X,Y,Z$. Recall that
$I_a(X;Y\mid Z)$ is zero if and only if $X\independent Y|Z$.

Theorem~\ref{thm:localshapley} and Theorem~\ref{thm:connectedshapley}
show that L-Shapley and C-Shapley values, respectively, are related to the Shapley value whenever the model obeys a Markovian structure that is encoded by the graph.  We leave their proofs to Appendix~\ref{app:proof}.
\begin{theorem}
\label{thm:localshapley}
Suppose there exists a feature subset $S\subset \nbhd{k}{i}$ with $i\in S$, such that
\begin{align}
\sup_{\substack{U\subset S\setminus \{i\},
V\subset [d]\setminus S}}
I_a(X_i;X_{V}|X_U,Y)\leq\varepsilon;
\sup_{\substack{U\subset S\setminus \{i\},
V\subset [d]\setminus S}}
I_a(X_i;X_{V}|X_U)\leq\varepsilon,
\label{eq:markov}
\end{align}
where we identify $I_a(X_i;X_{V}|X_\emptyset)$ with $I_a(X_i;X_{V})$ for notational convenience.
Then the expected error between the L-Shapley estimate $\hat\phi_X^k(i)$ and the true Shapley-value-based importance score $\phi_i(\ensuremath{\Prob_m},x)$ is bounded by $4\varepsilon$:
\begin{align}
\Exp_X|\hat\phi_X^k(i) - \phi_X(i)|\leq 4\varepsilon.
\end{align}
In particular, we have $\hat\phi_X^k(i) = \phi_X(i)$ almost surely if we have $X_i\independent X_{[d]\setminus S} | X_T$ and $X_i\independent X_{[d]\setminus S} | X_T,Y$ for any $T\subset S\setminus \{i\}$.
\end{theorem}

\begin{theorem}
\label{thm:connectedshapley
Suppose there exists a neighborhood $S\subset \nbhd{k}{i}$ of $i$, with $i\in S$, such that Condition~\ref{eq:markov} is satisfied. Moreover, for any connected subset $U\subset S$ with $i\in U$, we have
\begin{align}
\sup_{V\subset R(U)}I_a(X_i;X_{V}|X_{U\setminus \{i\}},Y)\leq\varepsilon
\sup_{V\subset R(U)}I_a(X_i;X_{V}|X_{U\setminus \{i\}})\leq\varepsilon,
\label{eq:markov2}
\end{align}
 where $R(U)\ensuremath{: \, = } \{i\in[d]-U:\text{ for any } j\in U, (i,j) \notin E \}$. Then the expected error between the C-Shapley estimate $\tilde\phi_X^k(i)$ and the true Shapley-value-based importance score $\phi_i(\ensuremath{\Prob_m},x)$ is bounded by $6\varepsilon$:
\begin{align}
\Exp_X|\tilde\phi_X^k(i) - \phi_X(i)|\leq 6\varepsilon.
\end{align}
In particular, we have $\hat\phi_X^{d}(i) = \phi_X(i)$ almost surely if we have $X_i\independent X_{R(U)} | X_{U\setminus \{i\}}$ and $X_i\independent X_{R(U)} | X_{U\setminus \{i\}},Y$ for any $U\subset [d]$.
\end{theorem}

\subsection{Relating the C-Shapley value to the Myerson value}
\label{sec:myerson}

Let us now discuss how the C-Shapley value can be related to the
Myerson value, which was introduced by~\citet{myerson1977graphs} as an
approach for characterizing a coalitional game over a graph $G$. Given
a subset of nodes $S$ in the graph $G$, let $\mathcal{C}_G(S)$ denote
the set of connected components of $S$---i.e., subsets of $S$ that are
connected via edges of the graph.  Thus, if $S$ is a connected subset
of $G$, then $\mathcal{C}_G(S)$ consists only of $S$; otherwise, it
contains a collection of subsets whose disjoint union is equal to $S$.

Consider a score function $T \mapsto v(T)$ that satisfies the
following decomposability condition: for any subset of nodes $S$, the
score $v(S)$ is equal to the sum of the scores over all the connected
components of $S$---viz.
\begin{align}
  \label{EqnDecompose}
v(S) & = \sum_{T\in \mathcal{C}_G(S)} v(T).
\end{align}
For any such score function, we can define the associated Shapley
value, and it is known as the \emph{Myerson value} on $G$ with respect
to $v$. \citet{myerson1977graphs} showed that the Myerson value is the
unique quantity that satisfies both the decomposability property, as
well as the properties additivity, equal contributions and
monotonicity given in Section~\ref{sec:shapleyvalue}.

In our setting, if we use a plug-in estimate for conditional
probability, the decomposability condition~\eqref{EqnDecompose} is
equivalent to assuming that the influence of disconnected subsets of
features are additive at sample $x$, and C-Shapley of order $k=d$ is
exactly the Myerson value over $G$. In fact, if we partition each
subset $S$ into connected components, as in the definition of Myerson
value, and sum up the coefficients (using Lemma 1 in
Appendix~\ref{app:proof}), then the Myerson value is equivalent to
equation~\eqref{eq:connected}.

\subsection{Connections with related work}
\label{sec:related}

Let us now discuss connections with related work in more depth, and in
particular how methods useful for approximating the Shapley value can
be used to speed up the evaluation of approximate L-Shapley and C-Shapley
values.

\subsubsection{Sampling-based methods}

There is an alternative definition of the Shapley value based on
taking averages over permutations of the features.  In particular, the
contribution of a feature $i$ corresponds to the average of the
marginal contribution of $i$ to its preceding features over the set of
all permutations of $d$ features. Based on this definition,
\citet{vstrumbelj2010efficient} propose a Monte Carlo approximation,
based on randomly sampling permutations.

While L-Shapley is deterministic in nature, it is possible to combine
it with this and other sampling-based methods. For example, if one
hopes to consider the interaction of features in a large neighborhood
$\nbhd{k}{i}$ with a feature $i$, where exponential complexity in $k$
becomes a barrier, sampling based on random permutation of local
features may be used to alleviate the computational burden.

\subsubsection{Regression-based methods}

\citet{lundberg2017unified} proposed to sample feature subsets based
on a weighted kernel, and carry out a weighted linear regression to
estimate the Shapley value. Suppose the model is evaluated on $N$
feature subsets at $x$. In weighted least squares, each row of the
data matrix $X\in\{0,1\}^{N\times d}$ is a $d$-dimensional vector,
with the $j^{th}$ entry being one if the feature $j$ is selected, and
zero otherwise.  The response $F\in\ensuremath{\mathbb{R}}^N$ is the evaluation of the
model over feature subsets. The weight matrix $W$ is diagonal with
$W_{ii}=(d-1) / (\binom{d}{n_i}n_i(d-n_i))$ with $n_i=\sum_{j=1}^d
X_{ij}$.

\citet{lundberg2017unified} provide strong empirical results using
this regression-based approximation, referred to as KernelSHAP; in
particular, see Section~5.1 and Figure~3 of their paper.  We can
combine such a regression-based approximation with our modified
Shapley values to further reduce the evaluation complexity of the
C-Shapley values.  In particular, for a chain graph, we evaluate the
score function over all connected subsequences of length $\leq k$;
similarly, on a grid graph, we evaluate it over all connected squares
of size $\leq k\times k$.  Doing so yields a data matrix $X \in
\{0,1\}^{kd \times d}$ and a response vector $F\in\ensuremath{\mathbb{R}}^{kd}$, where
$X_{ij}=1$ if the $j$th feature is included in the $i$th sample, and
$F_i \ensuremath{: \, = } v_x(S_i)$, the score function evaluated on the
corresponding feature subset. We use the solution to this weighted
least-squares problem as a regression-based estimate of
C-Shapley---that is, $\tilde \phi^k_x \approx (X^T W X)^{-1} X^T F$.

\section{Experiments}
\label{SecExperiments}

We evaluate the performance of L-Shapley and C-Shapley on real-world
data sets involving text and image classification. Codes for
reproducing the key results are available
online.\footnote{\label{ft:code}\url{https://github.com/Jianbo-Lab/LCShapley}}
We compare L-Shapley and C-Shapley with several competitive algorithms
for instancewise feature importance scoring on black-box models,
including the regression-based approximation known as
KernelSHAP~\cite{lundberg2017unified},
SampleShapley~\cite{vstrumbelj2010efficient} , and the LIME
method~\cite{ribeiro2016should}.  As discussed previously, KernelSHAP
forms a weighted regression-approximation of the Shapley values,
whereas SampleShapley estimates Shapley value by random permutation of
features. The LIME method uses a linear model to locally approximate
the original model through weighted least squares. For all methods,
the number of model evaluations is the same, and linear in the number
of features. We also choose the objective to be the log probability of
the predicted class, and use the plug-in estimate of conditional
probability across all methods (see Section~\ref{sec:importance}).

For image data, we also compare with Saliency
map~\cite{simonyan2013deep} as another baseline.  The Saliency method
is used for interpreting neural networks in computer vision, by
assuming knowledge of the gradient of a model with respect to the
input, and using the gradient magnitude as the importance score for
each pixel.

\subsection{Text Classification}

Text classification is a classical problem in natural language
processing, in which text documents are assigned to predefined
categories. We study the performance of L-Shapley and C-Shapley on
three popular neural models for text classification: word-based
CNNs~\cite{kim2014convolutional}, character-based
CNNs~\cite{zhang2015character}, and long-short term memory (LSTM)
recurrent neural networks~\cite{hochreiter1997long}, with the
following three data sets on different scales. See
Table~\ref{tab:dataset} for a summary, and Appendix~\ref{app:model}
for all of the details.

\begin{itemize} \item \textbf{IMDB Review with Word-CNN}: The Internet
  Movie Review Dataset (IMDB) is a dataset of movie reviews for
  sentiment classification \cite{maas2011learning}, which contains
  $50,000$ binary labeled movie reviews, with a split of $25,000$ for
  training and $25,000$ for testing. A simple word-based CNN model
  composed of an embedding layer, a convolutional layer, a max-pooling
  layer, and a dense layer is used, achieving an accuracy of $90.1\%$
  on the test data set.

\item \textbf{AG news with Char-CNN}: The AG news corpus is composed
  of titles and descriptions of $196,000$ news articles from $2,000$
  news sources~\cite{zhang2015character}. It is segmented into four
  classes, each containing $30,000$ training samples and $1,900$
  testing samples. Our character-based CNN has the same structure as
  that proposed in \citet{zhang2015character}. The model achieves an
  accuracy of $90.09\%$ on the test data set.

\item \textbf{Yahoo!\ Answers with LSTM}: The corpus of
  Yahoo!\ Answers Topic Classification Dataset is divided into ten
  categories, each class containing $140,000$ training samples and
  $5,000$ testing samples. Each input text includes the question
  title, content and best answer. We train a bidirectional LSTM which
  achieves an accuracy of $70.84\%$ on the test data set, close to the
  state-of-the-art accuracy of $71.2\%$ obtained by character-based
  CNNs \cite{zhang2015character}.
\end{itemize}

We choose zero paddings as the reference point for all methods, and
make $4\times d$ model evaluations, where $d$ is the number of words
for each input. Given the average length of each input (see
Table~\ref{tab:dataset}), this choice controls the number of model
evaluations under $1,000$, taking less than one second in TensorFlow
on a Tesla K80 GPU for all the three models. For L-Shapley, we are
able to consider the interaction of each word $i$ with the two
neighboring words in $\nbhd{1}{i}$ given the budget. For C-Shapley,
the budget allows the regression-based version to evaluate all
$n$-grams with $n\leq 4$.

The change in log-odds scores before and after masking the top
features ranked by importance scores is used as a metric for
evaluating performance, where masked words are replaced by zero
paddings. This metric has been used in previous literature in model
interpretation~\cite{shrikumar2016not,lundberg2017unified}. We study
how the average log-odds score of the predicted class decreases as the
percentage of masked features over the total number of features
increases on $1,000$ samples from the test set. Results are plotted in
Figure~\ref{fig:text_lor_mask}.

\begin{table}[bt!]
\centering \resizebox{0.88\textwidth}{!}{
 \begin{tabular}{||c|c|c|c|c|c|c|c||}
 \hline
Data Set & Classes & Train Samples & Test Samples & Average \#w & Model & Parameters & Accuracy \\ [0.5ex]
\hline\hline
IMDB Review \cite{maas2011learning} & 2 & 25,000 & 25,000 & 325.6 & WordCNN & 351,002& 90.1\% \\
AG's News \cite{zhang2015character} & 4 & 120,000 & 7,600 & 43.3& CharCNN & 11,337,988 & 90.09\%\\
Yahoo!\ Answers \cite{zhang2015character} & 10 & 1,400,000 &  60,000 &108.4 & LSTM & 7,146,166 & 70.84\% \\
 \hline\hline
 \end{tabular}
 }
 \caption{A summary of data sets and models in three
   experiments. ``Average \#w'' is the average number of words per
   sentence. ``Accuracy'' is the model accuracy on test samples.}
\label{tab:dataset}

\end{table}

\begin{figure}[bt!]
\centering
\includegraphics[width=0.3\linewidth]{figs/imdbcnn1_lor_mask.pdf}
\hspace*{-0.3cm}\includegraphics[width=0.3\linewidth]{figs/agccnn_lor_mask.pdf}
\hspace*{-0.3cm}\includegraphics[width=0.3\linewidth]{figs/yahoolstm_lor_mask.pdf} \\
\includegraphics[width=0.90\linewidth]{figs/legend.png}
\caption{The above plots show the change in log odds ratio of the
  predicted class as a function of the percent of masked features, on
  the three text data sets. Lower log odds ratios are better.}
\label{fig:text_lor_mask}
\end{figure}

\begin{table*}[bt!]
\centering
\resizebox{.67\textwidth}{!}{
 \begin{tabular}{||c | c||}
 \hline
 Method & Explanation \\ [0.5ex]
\hline\hline
Shapley& \colorbox[rgb]{1,0.92,0.92}{It} \colorbox[rgb]{0.97,0.97,1}{is} \colorbox[rgb]{0.3,0.3,1}{not} \colorbox[rgb]{1,0.65,0.65}{heartwarming} \colorbox[rgb]{0.8,0.8,1}{or} \colorbox[rgb]{1,0.5,0.5}{entertaining}. \colorbox[rgb]{1,0.81,0.81}{It} \colorbox[rgb]{0.77,0.77,1}{just} \colorbox[rgb]{0.0,0.0,1}{sucks}.\\
\hline
C-Shapley& \colorbox[rgb]{1,0.82,0.82}{It} \colorbox[rgb]{1,0.91,0.91}{is} \colorbox[rgb]{0.57,0.57,1}{not} \colorbox[rgb]{1,0.49,0.49}{heartwarming} \colorbox[rgb]{0.79,0.79,1}{or} \colorbox[rgb]{1,0.0,0.0}{entertaining}. \colorbox[rgb]{1,0.73,0.73}{It} \colorbox[rgb]{0.92,0.92,1}{just} \colorbox[rgb]{0.67,0.67,1}{sucks}.\\
\hline
L-Shapley& \colorbox[rgb]{1,0.89,0.89}{It} \colorbox[rgb]{1,0.93,0.93}{is} \colorbox[rgb]{0.26,0.26,1}{not} \colorbox[rgb]{1,0.72,0.72}{heartwarming} \colorbox[rgb]{0.36,0.36,1}{or} \colorbox[rgb]{1,0.0,0.0}{entertaining}. \colorbox[rgb]{1,0.39,0.39}{It} \colorbox[rgb]{0.96,0.96,1}{just} \colorbox[rgb]{0.65,0.65,1}{sucks}.\\
\hline
KernelSHAP& \colorbox[rgb]{1,0.71,0.71}{It} \colorbox[rgb]{0.95,0.95,1}{is} \colorbox[rgb]{0.48,0.48,1}{not} \colorbox[rgb]{1,1.0,1.0}{heartwarming} \colorbox[rgb]{0.78,0.78,1}{or} \colorbox[rgb]{1,0.15,0.15}{entertaining}. \colorbox[rgb]{1,1.0,1.0}{It} \colorbox[rgb]{1,1.0,1.0}{just} \colorbox[rgb]{0.0,0.0,1}{sucks}.\\
\hline
SampleShapley& \colorbox[rgb]{1,1.0,1.0}{It} \colorbox[rgb]{0.8,0.8,1}{is} \colorbox[rgb]{0.8,0.8,1}{not} \colorbox[rgb]{1,0.38,0.38}{heartwarming} \colorbox[rgb]{0.87,0.87,1}{or} \colorbox[rgb]{1,0.95,0.95}{entertaining}. \colorbox[rgb]{1,1.0,1.0}{It} \colorbox[rgb]{0.96,0.96,1}{just} \colorbox[rgb]{0.0,0.0,1}{sucks}.\\
\hline
\hline
 \end{tabular}
 }
 \caption{Each word is highlighted with the RGB color as a linear
   function of its importance score. The background colors of words
   with positive and negative scores are linearly interpolated between
   blue and white, red and white respectively.}
\label{tab:imdb_word_demo}
\end{table*}

\begin{figure}[!bt]
\centering
  \begin{tabular}[b]{ccc}
    \begin{subfigure}[b]{0.385\columnwidth}
      \hspace*{-0.0cm}\includegraphics[width=\textwidth]{figs/mnist_lor_mask.pdf}
    \end{subfigure}
    &
    \begin{subfigure}[b]{0.385\columnwidth}
      \hspace*{-0.4cm}\includegraphics[width=\textwidth]{figs/horse_deer_lor_mask.pdf}

    \end{subfigure}
    &
    \begin{tabular}[b]{c}
      \begin{subfigure}[b]{0.153\columnwidth}
        \hspace*{-0.5cm}\includegraphics[width=\textwidth]{figs/mnist/mistakes-3-1-regression_shapley-4-mask-118.png}

      \end{subfigure}\\
      \begin{subfigure}[b]{0.153\columnwidth}
        \hspace*{-0.5cm}\raisebox{+.27\totalheight}{\includegraphics[width=\textwidth]{figs/mnist/mistakes-8-0-regression_shapley-4-mask-118.png}}

      \end{subfigure}
    \end{tabular}
  \end{tabular}

  \caption{Left and Middle: change in log-odds ratio vs. the percent
    of pixels masked on MNIST and CIFAR10. Right: top pixels ranked by
    C-Shapley for a ``$3$'' and an ``$8$'' misclassified into ``$8$''
    and ``$3$'' respectively. The masked pixels are colored with red
    if activated (white) and blue otherwise.}
  \label{fig:mix}
  %
\end{figure}

On IMDB with Word-CNN, the simplest model among the three, L-Shapley,
achieves the best performance while LIME, KernelSHAP and C-Shapley
achieve slightly worse performance. On AG's news with Char-CNN,
L-Shapley and C-Shapley both outperform other algorithms. On
Yahoo!\ Answers with LSTM, C-Shapley outperforms the rest of the
algorithms by a large margin, followed by LIME. L-Shapley with order
$1$, SampleShapley, and KernelSHAP do not perform well for LSTM model,
probably because some of the signals captured by LSTM are relatively
long $n$-grams.

We also visualize the importance scores produced by different
Shapley-based methods on Example~\eqref{example}, which is part of a
negative movie review taken from IMDB. The result is shown in
Table~\ref{tab:imdb_word_demo}. More visualizations by our methods are
available online.\footnoteref{ft:code}

\subsection{Image Classification}

We carry out experiments in image classification on the MNIST and CIFAR10 data sets:

\begin{itemize}
\item \textbf{MNIST}: The MNIST data set contains $28\times 28$ images
  of handwritten digits with ten categories $0-9$
  \cite{lecun1998gradient}. A subset of MNIST data set composed of
  digits $3$ and $8$ is used for better visualization, with $12,000$
  images for training and $1,000$ images for testing. A simple CNN
  model achieves $99.7\%$ accuracy on the test data set.

\item \textbf{CIFAR10}: The CIFAR10 data set
  \cite{krizhevsky2009learning} contains $32\times 32$ images in ten
  classes. A subset of CIFAR10 data set composed of deers and horses
  is used for better visualization, with $10,000$ images for training
  and $2,000$ images for testing. A convolutional neural network
  modified from AlexNet \cite{krizhevsky2012imagenet} achieves
  $96.1\%$ accuracy on the test data set.
\end{itemize}

We take each pixel as a single feature for both MNIST and CIFAR10. We
choose the average pixel strength as the reference point for all
methods, and make $4\times d$ model evaluations, where $d$ is the
number of pixels for each input image, which keeps the number of model
evaluations under $4,000$.

LIME and L-Shapley are not used for comparison because LIME takes
``superpixels'' instead of raw pixels segmented by segmentation
algorithms as single features, and L-Shapley requires nearly sixteen
thousand model evaluations when applied to raw
pixels.\footnote{L-Shapley becomes practical if we take small patches
  of images instead of pixels as single features.} For C-Shapley, the
budget allows the regression-based version to evaluate all $n\times n$
image patches with $n\leq 4$.

Figure~\ref{fig:mix} shows the decrease in log-odds scores before and
after masking the top pixels ranked by importance scores as the
percentage of masked pixels over the total number of pixels increases
on $1,000$ test samples on MNIST and CIFAR10 data sets. C-Shapley
consistently outperforms other methods on both data sets.

Figure~\ref{fig:mnist} and Figure~\ref{fig:horse} provide additional
visualization of the results. By masking the top pixels ranked by
various methods, we find that the pixels picked by C-Shapley
concentrate around and inside the digits in MNIST. The C-Shapley and
Saliency methods yield the most interpretable results in CIFAR10. In
particular, C-Shapley tends to mask the parts of head and body that
distinguish deers and horses, and the human riding the horse.
Figure~\ref{fig:mix} shows two misclassified digits by the CNN
model. Interestingly, the top pixels chosen by C-Shapley visualize the
``reasoning'' of the model: more specifically, the important pixels to
the model are exactly those which could form a digit from the opposite
class.

\begin{figure}[!bt]
\centering
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-3-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-6-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-8-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-10-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-14-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-5-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-9-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-13-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-16-regression_shapley-4-mask-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-23-regression_shapley-4-mask-118.png}%

\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-3-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-6-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-8-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-10-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-14-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-5-kernel_shap-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-9-kernel_shap-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-13-kernel_shap-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-16-kernel_shap-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-23-kernel_shap-4-118.png

\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-3-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-6-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-8-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-10-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-14-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-5-sample_shapley-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-9-sample_shapley-4-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-13-sample_shapley-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-16-sample_shapley-4-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-23-sample_shapley-4-118.png

\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-3-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-6-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-8-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-10-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-3-14-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-5-saliency-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-9-saliency-118.png}%
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-13-saliency-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-16-saliency-118.png
\includegraphics[width=0.09\linewidth]{figs/mnist/images-8-23-saliency-118.png
\caption{ Some examples of explanations obtained for the MNIST data
  set. The first row corresponds to the original images, with the rows
  below showing images masked based on scores produced by C-Shapley,
  KernelSHAP, SampleShapley and Saliency respectively. For best
  visualization results, 15\% and 20\% of the pixels are masked for
  each image. The masked pixels are colored with red if activated
  (white) and blue otherwise.  }
\label{fig:mnist}
\end{figure}

\begin{figure}[!bt]
\centering

\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-deer-5-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-deer-11-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-deer-25-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-deer-26-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-deer-36-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-horse-9-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-horse-16-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-horse-23-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-horse-28-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/original-horse-59-205.png

\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-5-regression_shapley-4-mask-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-11-regression_shapley-4-mask-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-25-regression_shapley-4-mask-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-26-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-36-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-9-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-16-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-23-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-28-regression_shapley-4-mask-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-59-regression_shapley-4-mask-205.png

\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-5-kernel_shap-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-11-kernel_shap-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-25-kernel_shap-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-26-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-36-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-9-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-16-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-23-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-28-kernel_shap-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-59-kernel_shap-4-205.png

\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-5-sample_shapley-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-11-sample_shapley-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-25-sample_shapley-4-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-26-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-36-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-9-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-16-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-23-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-28-sample_shapley-4-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-59-sample_shapley-4-205.png

\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-5-saliency-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-11-saliency-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-25-saliency-205.png}%
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-26-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-deer-36-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-9-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-16-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-23-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-28-saliency-205.png
\includegraphics[width=0.09\linewidth]{figs/horse_deer/images-horse-59-saliency-205.png

\caption{Some examples of explanations obtained for the CIFAR10 data
  set. The first row corresponds to the original images, with the rows
  below showing images masked based on scores produced by C-Shapley,
  KernelSHAP, SampleShapley and Saliency respectively. For best
  visualization results, 20\% of the pixels are masked for each
  image.}
\label{fig:horse}
\end{figure}

\section{Discussion}
\label{SecDiscussion}

We have proposed L-Shapley and C-Shapley for instancewise feature importance scoring, making use of a graphical representation of the data. We have shown the superior performance of the proposed algorithms compared to other methods for instancewise feature importance scoring in text and image classification.

\section*{Acknowledgments}

We would like to acknowledge support from the DARPA Program on
Lifelong Learning Machines from the Army Research Office under grant
number W911NF-17-1-0304, and from National Science Foundation grant
NSF-DMS-1612948.

\vspace*{.25cm}

redpajama_set_name: RedPajamaArXiv


Pellet Smoker Tube are light weight, durable and portable smoke generators, that produce great quality smoke for cold and hot smoking. They are versatile enough to be used in just about any smoker or a grill. They are designed to burn pellets and supplement smoke at higher temps, in pellet grills/smokers.
This is where most pellet grills/smokers do not produce much smoke. The amnts adds additional smoke at cooking temps, regardless if your pellet grill/smoker is burning pellets or not. The tube smokers perform very well in pellet grills, gas grills and gas smokers. Their unique design takes up very little space on your grates.
Stainless Steel Perforated Mesh Smoker Tube Unlock tantalizing and unforgettable smoked flavors in your meat, fish, vegetable, cheeses, nuts and more for bold new tastes.
> Fantastic for cold smoking, grilling and more- Used to cold smoke meat, fish, cheese, nut up to 5 hours in an electric smoker. Add a wonderful touch of smoke to things hotter and faster.
> Built to last - 100% stainless steel material, portable 12'' x 2'', light weight, thick and durable. Works with with all kinds of grills like gas burner, charcoal, electric and portable grills.
> Prevent from rolling around the grill grates - Amazing Triangle shaped tube-smoker helps this stay in place during smoking.
> Easy to use & clean - Fill with full of pellets, light the pellets with a propane torch about 1min, burn them for 10min and get 4~5 hours of smoke. Clean up with a bottle brush for the inside and simple dish rag for outside.
---- Lightweight, portable, wasy to use or clean and durable - our product is nothing but awesome. Get them while they are hot and you will not be disappointed.
---- Delicoius smoke flavor - unlocked tantalizing and unforgettable smoked flavors in your meat, fish, vegetables, cheese, nuts and more for bold new tastes.
----- Great gift - a perfect housewarming gift for your family and friends moving to a new house, or that favourite pitmaster in your family.
----- The only thing better than afood hot off the grill is when it is been smoked to perfection. - Whether you are a grill master or just love breaking out the smoker during the summer, you want to creat flavors that make poeple's eyes widen and their mouths drop.
That is why you need the pallet smoker tube, a simple and easy way to add bold smoked flavors to any meal with ease.
Outside diameter: 1" to 12"


text:
Campaign launched to bring junior doctor home from US after he was injured on holiday
Dr Sebastian Kola-Bankole is in a coma and can't tell loved ones where his travel insurance docs are, so they are trying to raise £250,000 to cover treatment costs and have him brought home to the UK
By Karen Gordon
An appeal to bring a junior doctor back home after he was hit by a lorry in Las Vegas. Dr Sebastian Kola-Bankole (pictured on the left, above) is currently in a medically-induced coma after being run down crossing the road outside a hotel on 15 February, whilst on holiday celebrating his friend's wedding.
He has undergone emergency operations on his ears, arteries and spine, and is described as being in a critical but stable condition. Campaigners are trying to raise £250,000 to cover costs for his treatment and to bring him home on a special medical flight.
Friends of the 35-year-old say he normally has travel insurance but they are unable to find any papers and as he is in a coma, he can't tell them where to look.
Sebby out raising money for GOSH. Sadly we need to raise it for him. We're getting there, keep going!#bringbackseb pic.twitter.com/rWnkIvVpLn
— Pav Sarai (@pavsarai) February 21, 2016
Alexander Ademokun, who set up the appeal, said the doctor was his "best friend" and a "great doctor" who spent every Christmas volunteering at Crisis to help the homeless.
"There are no other resources to pay for his treatment - the cost of which will be well over £100,000. We hope that he will return to the UK as soon as is medically possible, however this may take some time."
Dr Kola-Bankole has family in the US, but his friend said his home is in London and he "needs to be in the NHS". The injured doctor is from Nigeria but has British citizenship after studying in the UK and working within the NHS for eight years - previously working at the Barnet and Chase Farm Hospitals.
His friends and family are trying to raise the money for the continuation of his treatment and relocation to the UK. If you would like to help, visit his GoFundMe page here.
The NetDoctor newsletter delivers the latest healthy living news straight to your inbox. Make sure you never miss out by signing up here...
This content is imported from Third party. You may be able to find the same content in another format, or you may be able to find more information, at their web site.
More From Health services
Keep your heart happy and healthy
Should I see a pharmacist instead of my GP?
What to do if you're unwell at Christmas
6 things doctors wish their patients knew
GP apps - why your appointment should be by video
Lockdown 2.0: medical services available
How to access online therapy
What is the NHS?
What to do if you can't get a GP appointment
How to access your medical records
Winter flu campaign launched
Consensual sex campaign launched
Dignity in Care campaign launched
Stroke awareness campaign launched
Govt re-launches stroke campaign
Scottish government launches alcohol campaign

redpajama_set_name: RedPajamaCommonCrawl


In high school, being a multiple sport athlete on top of being a student seemed to be awful at the time. There was no time for relaxing or hanging out with friends, unless it was at practice. I never thought I'd look back and say, "Wow, I had it good." Now, as a sophomore in college, I have two out of season semesters under my belt and I'm in the middle of my second in season semester. The difference between the two is slight, but quite dramatic.
Out of season is when you take all of your credit hours. You must attempt to stack on all of the hard stuff at once so it doesn't have to be a stressor when on a road trip. That's the goal, anyways. Some sports have some out of season games, and there's definitely still practice. For softball, we have the weekends off when we're out of season. That is a huge difference. Being able to make plans on Friday night and Saturday night really makes us feel like we have a social life. It also gives us the ability to use those days to catch up on sleep, recover our bodies or do school work. Being able to do school work in your room or at the library, instead of on a bus or a hotel room, makes it easier to do, in my opinion. I work best when I'm comfortable and focused. It's hard to focus in a hotel room full of three other girls or in a cramped bus seat. Having the weekends off is a blessing and I'll never take those for granted in the off season.
In-season, our weekends are not free. This means we have to be more smart with our time management. A lot of the time, nobody wants to do anything for the rest of the day after practice. Something as small as a three hour practice can change your mood for the rest of the day. Also, there are road trips during season. We could leave on a Thursday afternoon and not come back until Sunday night. That's missing a Thursday class and all of Friday's classes. That means, as athletes, we have to take the initiative to communicate with our professors. On the bright side, the professors at Kentucky Wesleyan are supportive and on our side. They make it very easy to catch up on work and let us know what we've missed.
In-season, we're always around our teammates. Friends that aren't on the team get very little time with us. That's why you make sure to spend time with your other friends during the off-season. That's also why it's good to always be on good terms with your teammates, since you're surrounded by them 24/7 during season. Being on bad terms with a teammate just causes more friction and makes games or road trips less fun.
Overall, the mentality of an in-season athlete compared to an out of season one is totally different. Out of season prepares you for the stress, but makes you so excited for the season. There are ups and downs to both. My favorite part, off-season, is getting weekends off. There are only a couple weekends that we have games scheduled, but then the rest are ours. That may be the only thing I like about the off-season, though. I love being in-season. The constant traveling, the excitement during games, and bonding with my teammates. My strongest bonds are with girls on my team, and that wouldn't happen if it wasn't for season.
Finishing all of your class work, maintaining a social life, and performing well on the field may be stressful and harder, but it's so worth it, though. The memories made and the experiences are unforgettable. It's what being a student-athlete is all about. We wouldn't have been handpicked by our coaches if they didn't think we could handle it. There are days that are worse than others, and there are days where it feels like were drowning with all the things we have to do. Student-athletes are not indestructible, but we are resilient, as we will always do what it takes during off-season and on-season.


Attention of Authorised Dealers Category-I (AD Category - I) banks is invited to the provisions of the Foreign Exchange Management (Transfer or Issue of Security by a Person Resident outside India) Regulations 2000, notified by the Reserve Bank vide Notification No. FEMA 20/2000-RB, dated 3rd May 2000, as amended from time to time. Attention of AD Category – I banks is also invited to A.P. (DIR Series) Circular No.6 dated July 18, 2014.
2. With a view to promoting the ease of reporting of transactions under foreign direct investment, the Reserve Bank of India (RBI), under the aegis of the e-Biz project of the Government of India has enabled online filing of the Foreign Currency Transfer of Shares (FCTRS) returns for reporting transfer of shares, convertible debentures, partly paid shares and warrants from a person resident in India to a person resident outside India or vice versa.
3. The design of the reporting platform enables the customer to login into the eBiz portal, download the reporting form (FCTRS), complete and then upload the same onto the portal using their digitally signed certificates. The Authorised Dealer Banks (ADs) will be required to download the completed forms, verify the contents from the available documents and if necessary, call for additional information from the customer and then upload the same for RBI to process and allot the Unique Identification Number (UIN). The FCTRS services of RBI will be made operational on the e-Biz platform from August 24, 2015. The user manual for this service is Annexed to this Circular.
4. It may be noted that for the present, the online reporting on the e-Biz platform is an additional facility to the Indian residents to undertake their FCTRS reporting and the manual system of reporting as prescribed in terms of A.P. (DIR Series) Circular No.6 dated July 18, 2014 would continue till further notice.
5. The ADs will be required to access the e-Biz portal [which is hosted on the National Informatics Centre (NIC) servers] using a Virtual Private Network (VPN) Account obtained from NIC. ADs may refer to A.P. (DIR Series) Circular No.95 dated April 17, 2015 for financial aspects of obtaining/using the VPN accounts.
6. AD Category-I banks may bring the contents of this circular to the notice of their customers / constituents concerned. They are advised to extend due cooperation/assistance to their constituents for uploading the abovementioned forms on the e-Biz platform.


text:
Piłka nożna na Światowych Wojskowych Igrzyskach Sportowych 2011 – zawody, które odbywały się w brazylijskim Rio de Janeiro 15–24 lipca 2011 roku podczas igrzysk wojskowych.

Medaliści

Klasyfikacja medalowa

Zobacz też
 Piłka nożna na światowych wojskowych igrzyskach sportowych
 Światowe wojskowe igrzyska sportowe

Przypisy

Bibliografia
  data dostęp 2019-11-14

redpajama_set_name: RedPajamaWikipedia


It's a lot more than Aloha as the Air Force's 18th Force Support Squadron "brings the Hawaiian Islands to you" tomorrow afternoon and evening. The five-hour Ho'olaule'a party takes place on the green at the Chibana Recreation Area is free, and open to everyone. Read More!
Its Brooklyn in the house! New York legendary reggae dancehall sound is invading Okinawa with Supa Flex of Afrique Sound Station. Now, JamRock promotions of Okinawa has linked up with this Brooklyn legend to tear the house down, dancehall style. Read More!
The preliminary competition for the All Japan B-Boy 2on2 battle is coming to Okinawa Sunday afternoon at Koza Music Town. The free Koza Street Dance Festival starts at 2 p. Read More!
American Grammy Award winning rapper, music producer, entrepreneur and international DJ Lil Jon is set to headline a Saturday evening show at Koza Music Town in Okinawa City. The 41-year-old Atlanta native first formed the group Lil Jon & the East Side Boyz 15 years ago, and is now traveling as a solo artist. Read More!
The Kadena Eisa Festival is set for Shinmachi Street in Kadena Town, near Kadena Rotary, on Sep. 2 from 7 ~ 9 p. Read More!
The 48th Itoman Kyan Eisa is ready to roll, using its special paranku drum with plenty of hand movements and a low dance style. The Kyan Eisa is performed in front of the Kyan Agricultural Association Building Aug. Read More!
One of Okinawa's most famous district eisa groups is going through final tune-ups for a weekend of Eisa action. Heshikiya Eisa's performance style is not as much showy as most eisa, but more traditional and classical, a methodology that ranks the Heshikiya group among the tops in Okinawa, and even mainland Japan. Read More!
Hundreds of Eisa dancers are going through final rehearsals for Sunday's Takashiho Street Eisa in Yomitan Village, where more than 3,000 spectators are expected to turn out. The Takashiho Eisa Festival begins at 3 p. Read More!
The annual Kyubon Togyu Tournament (Lunar Bon Bullfight Tournament) is set for Sunday at the Ishikawa Dome in Uruma City, the most significant bullfighting tournament on the island this year. The Sunday afternoon festival features not only exciting bull fighting, but also a belly dance show, an eisa performance and raffle prizes for the audience. Read More!
The people of Okinawa are welcoming the Obon festival today through Saturday, a time of paying homage to their ancestors. The Obon festival is held here according to the lunar calendar, and is sometimes called the celebration of the deceased ancestors. Read More!
Julie C. Valladolid is the winner of this week's Japan Update raffle. Read More!
Taste tempting Indian cuisine is literally 'just around the corner' from Kadena Air Base, serving a variety of Indian lunch and dinner specialties. Everest Restaurant is located next door to Altec, just outside Kadena's Gate 2, putting the all staff to the daily test of delicious meals. Read More!
Is papaya a fruit or a vegetable? That's the age-old question for Okinawans, who mostly consider it a vegetable when used before ripening, and a fruit once it's ripe. Sounds simple enough for one of the most famous fruits, or vegetables, in Japan. Read More!
Editor's Note: Okinawa's beautiful southern islands are being showcased in Japan Update each week. This week, Japan Update travels to a small, heart-shape island where cattle outnumber inhabitants. Read More!
Americans have enjoyed Reese's Peanut Butter Cups since 1923, but until now the only way to get hands on them was to persuade someone on U.S. Read More!


Belle Harbor's finest florists and flowers. Delivered.
Floom removes the hassle of sending a beautiful, stunning flower bouquet or plant from a local independent florist for flower delivery in Belle Harbor.
Just enter your delivery zipcode at the top to send the perfect flower bouquet to someone in Belle Harbor.
Same day flower delivery Belle Harbor is available before 12pm EST and Belle Harbor next day delivery before 11:59pm EST.
Order your Belle Harbor flowers online with Floom, and the local independent florist fulfilling your order will ensure they are hand delivered to your chosen recipient. We also provide the option for a handwritten message (our florists all have nice handwriting, we promise!) with the delivery of your bouquet in our delivery cards.
Our Belle Harbor flower delivery serves the tight-knit community on the western half of the Rockaway Peninsula in Queens, New York City. Long before it became known for the sad events of November 12, 2001, when American Airlines flight 587 crashed there, Belle Harbor was the subject of a dispute between land developer Frederick J. Lancaster and a group who wished to preserve the neighborhood in history as the Belle Harbor Yacht Club.
Whether you've set sail for the high seas and want to send a local loved one a token of your feelings, or you simply need a pretty centerpiece for when you're entertaining in the marina, our Belle Harbor florists offer same day flower delivery in Belle Harbor.


text:
Jurgen Klopp's next Liverpool mission is clear after Club World Cup glory
Liverpool claim victory in Qatar with captain's performance from Jordan Henderson as Premier League title is now in Jurgen Klopp's sights
Ian DoyleChief Liverpool writer
The morning after the night before and, inside the lobby of the Intercontinental hotel in the heart of Doha, the Flamengo fans continue to mill, a little more subdued, a little quieter than earlier in the week.
A few miles away in the West Bay area of the Qatari capital, Liverpool's players are being snapped on the beach, throwing Santa hats towards the sun as the temperature edged into the 20s.
The eye, though, is drawn to the shiny silverware clasped safely in the hands of Jordan Henderson.
Beating Flamengo in the FIFA Club World Cup final on Saturday was the ultimate confirmation that, on the global stage at least, the Reds have absolutely no peers.
Liverpool team pose for a photograph with the Club World Cup trophy with Santa hats on
It's the first time Liverpool have won the competition or any of its previous iterations, having failed in 1981, 1984 and 2005, and ticks the one remaining box on the list of honours.
Football? Completed it, as the kids might say these days.
But it's the one trophy Liverpool have won more times than any other that remains the obsession, the Holy Grail. The bread and butter, as Bill Shankly would have it known.
The league title.
Jurgen Klopp's words ahead of Champions League final proved right as Liverpool boss shakes off unwanted reputation
Not since 1990 have the Reds been crowned kings of England, a fact that has never seemed more ludicrous than at the present time with Jurgen Klopp's side having become the first English team to win the international treble in the same year of European Cup, UEFA Super Cup and FIFA Club World Cup.
While Roberto Firmino was netting the winner against Flamengo, back home Manchester City had just beaten Leicester City, meaning the Reds' 10-point lead at the top of the Premier League had in fact been strengthened, Klopp's side now having a game in hand.
*Latest Liverpool transfer rumours and reaction to Club World Cup win
Indeed, since Liverpool beat Watford last Saturday, Leicester have dropped five points, making the game at King Power Stadium on Boxing Day arguably a must-win for Brendan Rodgers' side.
That could play into Liverpool's hands, although City's statement victory means they are once again the team Klopp's men will be expected to fend off during the second half of the season.
If Saturday's win in Qatar was historic for the club, it was the ultimate justification of Henderson's captaincy.
Jordan Henderson of Liverpool during the FIFA Club World Cup final
Not since Steven Gerrard in Istanbul in 2005 has a skipper so inspired a Liverpool team to victory in a final.
Henderson's display was one of drive, determination and application, only a fine save from Flamengo goalkeeper Diego Alves denying him the goal his performance richly deserved.
All this after he had filled in so capably at centre-back in the semi-final win over Monterrey after Virgil van Dijk missed out through illness.
Indeed, with his third trademark major trophy lift inside six months, Henderson has already matched the number achieved by Gerrard during his 12 years as captain. Liverpool will surely hope there is more to come.
Inside LFC's dressing room celebrations
Liverpool analysis - Kop gets new song
Rules on Liverpool's gold FIFA Badge
National media react to Liverpool's win
It wasn't perfect. That energy-sapping extra time period will surely be felt when Klopp's side get deep into the festive Premier League period while the injury to Alex Oxlade-Chamberlain is a major concern.
But a 7,000-mile round trip that could easily have been a distraction has instead only strengthened the collective belief Liverpool can, after three decades, get over the line in the championship race.
A Merry Christmas could then eventually become the happiest of new years.


This special set contains 20 hanks of 9/0 3-cuts. It is a great gift for the bead artist in your life, or even a gift for yourself. These 20 hanks contain a variety of finishes and colors to make a rainbow set that we are very proud of. It is a dream combo for earring makers and powwow-beaders.
There is a limited number available, so take advantage while you can. We'll be offering these at a special extra-discounted price from November 21-26, 2018, as part of our Black Friday/Small Business Saturday/Cyber Monday Sale!


Below we have a guide to giving your dog medications, whether it is tablets, capsules, pills or liquid and syrups: Please ensure that you thoroughly read and understand the administration instructions on the label prior to giving to your pet - if you are at all unsure, contact your vet BEFORE giving the medication.
Place the pill between your thumb and index finger. With your other hand, use your thumb and index finger to firmly grasp your dog's upper jaw.
As you open your dog's mouth, gently fold the upper lip over the teeth. This will reduce the chance of being bitten.
Rotate your wrist to tilt your dog's head upwards. Use you middle finger to slowly open their lower jaw.
Keep your middle finger over your dog's small incisor teeth, and deposit the pill as far back on the tongue as possible. Immediately close your dog's mouth. Then, keeping your hand over their mouth, put their head down to facilitate swallowing.
To further encourage swallowing, stroke your dog's throat or blow on their nose.
Grasp your dog's muzzle with one hand while holding the syringe or dropper with your other hand.
Gently squirt the medication into the pouch between your dog's teeth and cheek.
Hold your dog's jaw closed and tilt the head back slightly. Stroke their throat or blow on their nose to encourage swallowing.
If your dog gags or coughs up the medication, lower their head and calm them down.


I've loved travel since as long as I can remember, and it has been a huge part of my life since I was a little girl. My love of travel was inspired by my family's involvement with LA's first agency servicing the high-profile clientele of Hollywood.
Today I love booking all kinds of travel for my clients, though I specialize in leisure travel and production and music touring within the entertainment industry. In 2016, I was so excited to be chosen as one of Travel Agent Magazine's 30 under 30 for 2016!
I have travelled extensively in Europe, Mexico, and the Middle East. I am fascinated by world history and ancient cultures, and I love learning more about the areas where civilization began.
I am a sponge for new information, and while I love history and culture, I also have my finger on the pulse of social media and love discovering trendy new restaurants and bars around the world. I create unforgettable, fully customized experiences for my clients - some of which include food and wine tours, educational and heritage trips, and adventure journeys.