Trustable Machine Learning Systems

1 - The Good, the bad, and the ugly

2 - Machine Learning at its "Good"

7 - Adversarial examples (mathematical formalisation)

Given some classifier model $\mathcal{F}: \mathbb{R}^{n \times m} \rightarrow Y, \ Y \in \{0, 1, ..., k-1\}$ and some input $\textbf{x}$ , and adversarial is created by the modification $\epsilon$ within the range of $r$ (i.e. $\epsilon \leq r$ ) that will result in a miss-classification: $\mathcal{F}(\textbf{x}) \neq \mathcal{F}(\textbf{x} + \epsilon)$ .

Here we have a more formal definition of what an adversarial is. If we have some classifier F. This classifier takes a vector, or in this case, a matrix input representation of a image $x$ . The output of this function is a single class label from $k$ classes.

An adversarial example will then be some modification ε to this x where the result will be a different output from the classifier. Typically, this ε value will be bounded by some norm value. In this example we have an $r$ . I.e. this maximum amount of change to pixels will be bounded by this $r$ .

In other words, to create an adversarial, it is necessary to find some, suitably small, modification to the original input image, i.e. change of pixels, that will result in the model outputing an incorrect class.

Often, we find that the modifications are not noticable to the human observer, but yet, the model has a high degree of confidence in its incorrect prediction.

- How do we choose an $r$

9 - Less clear with non-image data

Iris dataset - classifier aim: predict type of flower from 4 dimensional vector of Sepal Length, Sepal Width, Petal Length, and Petal Width. I.e. $\mathcal{F}: \mathbb{R}^4 \rightarrow Y, \ Y \in \{0, 1, 2\}$ .

- Applying a 'small' $r$ can lead to overlaps of true class boundaries

- Generate a individual $r$ for each data point

Figure 10: geometric complexity of class boundaries

Figure 11: sparsity/density of sampling from data manifold that consistutes the training data.

Some of my research aims to answer this question, using the information presented in the available data. Given a set of data, a individual $r$-bound will be computed for each data point that will take into consideration the estimated class bounds, and how much information there is present in the data.

We consider two properties of the data in the process of generating these neighbourhoods. These are:

situations where differently labelled data points lay close together in the topological space, and therefore any perturbation of the data points could result in passing the class boundaries, while wrongly labelling the perturbation the same as the original. We have just seen this with the previous plots of the Iris data.

Our second property is shown in figure 2. It concerns the number of samples from different regions of the data manifold. In sparse regions (small numbers of samples), estimated class boundaries mayseem deceivingly simple, e.g. linear with a wide margin.

12 - Iterative expansion

In our method we provide an algorithm to iteratively expand the maximum $r$ bound.

13 - Modulating by density

Expansion is modulated by the estimated density of data samples. Using an inverse multiquadric radial basis function (RBF) to estimate the density at a given location.

φ (x; \bar{x}) = \frac{1}{\sqrt{1 + (ε r)^{2}}}, where r =∥ \bar{x} - x ∥

$\varphi(x; \overline{x}) = \frac{1}{\sqrt{1 + (\varepsilon r)^2}},\; \text{where}\; r = \parallel \overline{x} - x \parallel$

The estimated density for a single point is the sum of RBFS, centered on each point, at this location.

ρ_{c} (x) = \sum_{x_{j} \in X^{c}} φ (x; x_{j})

$\rho_c(x) = \sum_{x_j \in X^c} \varphi(x; x_j)$

- Final result: individual $r$ value for each data point

Morgan, J., Paiement, A., Pauly, A., & Seisenberger, M. (2021). Adaptive neighbourhoods for the discovery of adversarial examples. arXiv preprint arXiv:2101.09108.

After computing the density of each data point and expanding the neighbourhoods, then we will have an individual $r$-bound for each data point. This $r$ provides the upper-bound with which to search for adversarial examples.

We can seen this plot, that the black points have grown much larger due to the large amounts of information about neighbours of the same class. While other points in the top right have not grown much at all. In this plot we can still see overlaps, but this is only because the neighbourhoods were computed at a higher number of dimensions while this plot only shows 2 dimensions. At these higher dimensions the neighbourhoods are not overlapping.

Here today, I have provided the iterative method to compute $r$-bounds, but we also provide another method using langrangian multipliers to directly compute these bounds. You can find the method in the paper "Adaptive neighbourhoods for the discovery of adversarial examples".

- Now we must find $\textbf{x} + \epsilon$

18 - Simple Arithmetic

z = σ (W x + b)

$z = \sigma(Wx + b)$

Where $\sigma$ is some non-linear function to increase the model's complexity to allow it to model non-linear relationships. One of the most common non-linear functions when training neural networks is the Rectified Linear activation function (ReLU): $\max(Wx+ b, 0)$ .

23 - Building an entire model with NeuralVerifier

encoding(x) = begin
    y = dense(x,
              neural_network[1].W,
              neural_network[1].b) |> relu;
    y = dense(y,
              neural_network[2].W,
              neural_network[2].b) |> relu;
    y = dense(y,
              neural_network[3].W,
              neural_network[3].b) |> softmax;
end

24 - Setting up search for adversarial examples

min_{ϵ} (F (x) \neq F (x + ϵ)), ϵ \leq r

$\min_{\epsilon} (\mathcal{F}(x) \neq \mathcal{F}(x + \epsilon)), \ \epsilon \leq r$

for (idx, (x_i, r_i)) in enumerate(zip(x, r))
    m = Optimize()  # create an optimisation procedure (model)

    add!(m, (eps > 0) ∧ (eps <= r_i)) # bound condition on epsilon

    y = encoding(x_i)  # get initial condition of y in our encoding

    add!(m, y != f(xi)) # add the adversarial example condition

    minimize!(m, eps)  # find the smallest eps

    check(m) # check for satisfiability

    m.is_sat == "sat" && @info "#$(idx): Adversarial found!"
end

26 - Adversarial Examples Found!

Running on MNIST dataset.

[ Info: #1: Adversarial found!
[ Info: #3: Adversarial found!
[ Info: #4: Adversarial found!
[ Info: #5: Adversarial found!
[ Info: #7: Adversarial found!
...

27 - Main contributions

Using knowledge gleamed from the data manifold to generate individual $r$ value for each data point.
Open-source platform for verification of Neural Network properties using SMT solvers

Trustable Machine Learning Systems

Jay Morgan

30th March 2021

1 - The Good, the bad, and the ugly

2 - Machine Learning at its "Good"

3 - Machine Learning at its "Ugly"

4 - Machine Learning at its "Bad"

5 - A life with formal methods

6 - What's in todays talk

7 - Adversarial examples (mathematical formalisation)

- How do we choose an $r$

9 - Less clear with non-image data

- Applying a 'small' $r$ can lead to overlaps of true class boundaries

- Generate a individual $r$ for each data point

12 - Iterative expansion

13 - Modulating by density

- Final result: individual $r$ value for each data point

- Now we must find $\textbf{x} + \epsilon$

16 - Searching for the existence of adversarial examples

17 - Application of using NeuralVerifier

18 - Simple Arithmetic

19 - Encoding arithmetic

20 - ReLU

21 - More complex Sigmoid function (using piecewise linear approximation)

22 - Putting together a simple layer

23 - Building an entire model with NeuralVerifier

24 - Setting up search for adversarial examples

25 - In NeuralVerifier

26 - Adversarial Examples Found!

27 - Main contributions

28 - A thank you to my supervisors

29 - Contributions welcome!