---
# System prepended metadata

title: 'Math for Feature Completeness, Foils'

---

# Math for Feature Completeness, Foils

## High-level Aims and Notations
Recall the following notation:
- $D$ is the input dimension; by abuse of notation, $D$ also represents the set $[0, \ldots, D-1]$. 
- $\mathbf{x}^*$ is the input under consideration
- $\mathbf{x}^*_{D'}$, where $D' \subset D$, is a vector $\mathbf{x}^{*^{(d)}}_{D'} = \mathbf{x}^{*^{(d)}}$ if $d \in D'$ and $\mathbf{x}^{*^{(d)}}_{D'} \in \mathbb{R}$ otherwise.

**To Do:** Let's agree on the following set of aims and notations:
1. **High-level:** Given an explanation $E(\mathbf{x}^*)$ at $\mathbf{x}^*$, we want to find:
    - we want to find $\mathbf{x}_f^*$, a single foil -- i.e. task-sensitive, maximally different counterfactuals for $\mathbf{x}^*$ -- that is implied by $E(\mathbf{x}^*)$. 
        - For example, if the task is to distinguish between fireperson and baseball player, given an $\mathbf{x}^*$ that is a picture of a batter, then we'd want to change the group of pixels in the baseball cap to a fire hard-hat. This change is a big change (say, as compared to adding Gaussian noise) and meaningful (in terms of flipping the label). 
    - we want to be able to use the explanation identify the "relevant" differences between the input and the foil, as well as the irrelevant differences.
    - we need math and definitions to work with representations as well

2. **Math-level:** I think this is the formalization of the above.
    - We want a foil $\mathbf{x}_f^*$, such that:
        - $\|\mathbf{x}_f^* - \mathbf{x}^*\|_2^2$ is maximal
        - identify $D_0^{'}, D_1^{'}$ such that:
            -  if $E(\mathbf{x}_{D_1'}^*)\neq 0$ then $\mathrm{MI}(y, \mathbf{x}_{D_1'}^*| \mathbf{x}_{-D_1'}^*) \neq 0$. That is, the predicted label should not change, if we swap relevant pixels in the input, $\mathbf{x}_{D_1'}^*$, with the relevant pixels in the foil, $(\mathbf{x}_f^*)_{D_1'}$. 
            - if $E(\mathbf{x}_{D_0'}^*)= 0$ then $\mathrm{MI}(y, \mathbf{x}_{D_0'}^*| \mathbf{x}_{-D_0'}^*) = 0$. That is, the predicted label should not change, if we swap irrelevant pixels in the input, $\mathbf{x}_{-D_0'}^*$, with the irrelevant pixels in the foil, $(\mathbf{x}_f^*)_{-D_0'}$. 
    - Here everything will be discrete:
        - $p(\mathbf{x}_{D_1'}) = \begin{cases} 0.5, & \text{if } \mathbf{x}_{D_1'}  = \mathbf{x}_{D_1'}^*\\ 0.5, & \text{else} \end{cases}$