Initialization

SetOptions[EvaluationNotebook[], 
  "WindowTitle" -> "Adversarial examples. Differential privacy"]

Adversarial examples and  differential privacy

Chapter 10 . How something small can have an effect?

Leo Kärkkäinen
leo.karkkainen@aalto.fi

Outline

Properties of neural networks.

Adversarial examples

Minimizing the size of the neural networks.

Embedded systems.

10.1 Representation capability of a two layer neural network

Any continuous function with given accuracy with (exponentially) large hidden layer.

In chapter 4 we discussed a result from Leshno and Schocken (1991):

A neural network with one  hidden layer can uniformly approximate any continuous function on a compact set if and only if the activation function is not a polynomial: Piecewise polynomial like Rectified Linear Unit (ReLU) is OK.

Clear[y,w,b];Graph[Join[ Table[ j-> i,{j,1,5},{i,6,12}],Table[ i-> j+100,{j,1,1},{i,6,12}]]//Flatten,VertexLabels->Join[Table[i+100->Placed["     y = ∑ (Subscript[w, k]^((2))) ·σ[ (Subscript[w, k]^((1)))·x +(Subscript[b, k])]" , After],{i,1,1}],Table[i->(Subscript[x, i]),{i,1,2}],{5-> "bias"},{4-> (Subscript[x, d])},Table[i->Placed[σ[(Subscript[w, i-5]^((1))) ·x+(Subscript[b, i-5])],Below],{i,6,12}],{3-> Placed["   …", After]},{12-> Placed["   …", After]}]//Flatten, PlotLabel->"Universal function approximator f: (ℝ^d)→ ℝ, f[x]=y", ImageSize->Large, VertexStyle->{Red}, VertexSize->Large ]

The number of parameters needed depends heavily on the accuracy.

For a size of n middle layer this is

d×n (the first weight matrix (Subscript[w, k]^((1)))) + n  (the biases (Subscript[b, k]))  + n  (the second layer weights (Subscript[w, k]^((2))))= (d+2)× n

Real valued function of any finite set of n   d-dimensional points can be fitted with 2 n +d parameters perfectly.

One can show that a very simple neural network can learn a finite data set perfectly  by heart.

Clear[y,w,b];Graph[Join[ Table[ j-> i,{j,1,5},{i,6,12}],Table[ i-> j+100,{j,1,1},{i,6,12}]]//Flatten,VertexLabels->Join[Table[i+100->Placed["     y = ∑ (Subscript[w, k]) σ[ a·x -(Subscript[b, k])]" , After],{i,1,1}],Table[i->(Subscript[x, i]),{i,1,2}],{5-> "bias"},Table[i->Placed[σ[a ·x-(Subscript[b, i-5])],Below],{i,6,11}],{3-> Placed["   …", After]},{4-> (Subscript[x, d])},{11-> Placed["   …", After]},{12-> Placed["σ[a ·x-(Subscript[b, 12])]", Below]}]//Flatten, PlotLabel->"Zero error network f: (ℝ^d)→ ℝ, f[x]=y", ImageSize->Large, VertexStyle->{Red}, VertexSize->Large ]

A  finite, d-dimensional data set of size n,  can be represented with a two layer ReLU network  with only 2n + d parameters.
◼ Even more - this can be turned to a k-depth network with order of k/n parameters.

Let c:  (ℝ^d)⟶ℝ , be a two layer network,

c[x] =(∑_k)(Subscript[w, k])Ramp[a·x-(Subscript[b, k])],

where a ∈ (ℝ^d) (d components) ,  and w, b ∈ (ℝ^n)  (2n components, where n is the sample size of the dataset). So, there is a heavily factorized weight matrix that reduces the number of parameters to  d

Manipulate[Row[{"(W^((1))) =",ConstantArray[1, {n,d}]//MatrixForm, "." , DiagonalMatrix[Array[(Subscript[a, # ])&,{d} ]]//MatrixForm,"=",ConstantArray[1, {n,d}].DiagonalMatrix[Array[(Subscript[a, # ])&,{d} ] ]//MatrixForm}],{{d,2},1,10,1},{{n,5},1,20,1}]

Pick pairs (Subscript[{(z, y)}, j]) of vectors    z ∈ (ℝ^d) and values y ∈ℝ   (Subscript[{(z, y)}, j])  j∈ {1,…n}, so that all data points  (Subscript[z, j]) are distinct.

Then, It is possible to find a vector a∈ (ℝ^d), so that the n dot products a · (Subscript[z, j]) ≡ (Subscript[x, j]) are all distinct

𝔻 =RandomVariate[ NormalDistribution[0,1],{100,2}]; ListPlot[ 𝔻, PlotLabel->"100 random 2d points",ImageSize->250,AspectRatio->1]

Construct:

Let us make it a regression task, by “classifying” all points with a parabola and follow the steps described before.

𝔻 = Sort[𝔻,#1[[1]]<#2[[1]]&];y= ((#[[1]])^2)+ ((#[[2]])^2)  & /@ 𝔻;data =Transpose[{𝔻,y}];plot =ListPlot3D[{#[[1,1]],#[[1,2]] ,#[[2]]} & /@ Transpose[{𝔻,y}], Mesh->All, PlotLabel->"Set of 2d points classified by thes square of their norm",ImageSize->600]

x ={1,0}. # & /@ 𝔻;ListPlot[x, PlotLabel->"All points projected and ordered into the x-axis", ImageSize->600]

Create b values in between of the points so that (Subscript[b, 1])< (Subscript[x, 1])< (Subscript[b, 2]) < … < (Subscript[b, n]) < (Subscript[x, n])

(Subscript[b, 1])< (Subscript[x, 1])< (Subscript[b, 2]) < … < (Subscript[b, n]) < (Subscript[x, n])

xmin = Min[x];b = MovingAverage[x,2];b =  PrependTo[b,Floor[xmin-0.001]];ListPlot[ {x,b},ImageSize->600]

Create a matrix A that has entries (Subscript[A, ij])≡Ramp[(Subscript[x, i])-(Subscript[b, j])] .  It is lower diagonal, with non-zero elements on the diagonal, so it is invertible. Hence, as

(Subscript[A, ij])≡Ramp[(Subscript[x, i])-(Subscript[b, j])]

It is lower diagonal, with non-zero elements on the diagonal, so it is invertible.

(Subscript[y, i ])= c[(Subscript[z, i])] =(∑_j)(Subscript[w, j])Max[(Subscript[x, i])-(Subscript[b, j]),0]=(Subscript[A, ij])(Subscript[w, j]) => w= (A^(-1 ))y

A =Table[ Max[ x[[i]] - b[[j]],0], {i,1,Length[x]},{j,1,Length[b]}];MatrixPlot[A, PlotLabel->"A matrix is lower diagonal, hence invertible",ImageSize->200]

Hence, the weights are given by  w = (A^(-1 ))y:

w = (A^(-1 ))y

w =Inverse[A].y;ListPlot[w, PlotLabel->"Weights w"]

In summary, we have calculated the exact values, without training.  Here are the resulting “Basis functions” defined by the “middle points” (Subscript[b, j])

Manipulate[Show[{Plot[ Table[Max[ x  - b[[j]],0],{j,1,100}],{x,-3,3}, PlotRange->{0,4},PlotStyle->Directive[{Blue,Thin}],PlotLabel->"Ramp[ x  - (Subscript[b, j])]",ImageSize->600], Plot[ Table[Max[ x  - b[[j]],0],{j,k,k+5}],{x,-3,3}, PlotRange->{0,4},PlotStyle->Directive[{Red}]]}],{k,1,Length[w]-5,1}]

Plot[ (∑_(j=1)^(Length[w]))Max[ x  - b[[j]],0],{x,-3,3}, PlotLabel->"Cumulative sum of the basis functions", ImageSize->600]

There is no generalization as the values jump up and down depending on how far the point for projected to the x-axis.

Plot[ (∑_(j=1)^(Length[w]))w[[j]] Ramp[ x  - b[[j]]],{x,-3,3}, PlotLabel->"(∑_(j=1)^(Length[w]))(Subscript[w, j])Ramp[x  - (Subscript[b, j])]", ImageSize->600]

So, we have calculated the exact values, without training. The list looks perfect. The neural network results come first, then the annotation.

c[{x1_,x2_}] := (∑_(j=1)^(Length[w]))w[[j]]Ramp[ {1,0}.{x1,x2}  - b[[j]]];c[# ] & /@ 𝔻

y

ListPlot3D[{#[[1]],#[[2]] ,c[# ]} & /@ 𝔻, Mesh->All, PlotLabel->"The result with the trained data points", ImageSize->600]

Hence; There is no generalization (even interpolation) in some zero error solutions.

See the data:

The full plot of the neural network function looks bad.

Show[ {plot,Plot3D[ {c[{x,y}]},{x,-2,2},{y,-2,2}]}, ImageSize-> 600]

“Consequently, these models are in principle rich enough to memorize the training data. This situation poses a conceptual challenge to statistical learning theory as traditional measures of model complexity struggle to explain the generalization ability of large artificial neural networks. We argue that we have yet to discover a precise formal measure under which these enormous models are simple. “

By the way, classifying n distinct point is not particularly hard even without neural networks. First make a Delaunay triangulation (i.e  so that no points are inside the triangles) and then draw a normal (perpendicular line) in the middle of the triangle edges until they meet each other. The resulting Voronoi mesh has every point in the data set in its own box. However, this uses quite a lot of parameters....

Show[{ HighlightMesh[VoronoiMesh[𝔻, "Voronoi" ],Style[1,Black]],HighlightMesh[DelaunayMesh[𝔻 ],{Style[0,Directive[PointSize[Medium],Black]],Style[2,Opacity[0.1]]}],Graphics[{Orange,PointSize[Large],Point[𝔻]}]}, ImageSize-> 600]

10.2 Random labeling of data sets

https://arxiv.org/pdf/1611.03530.pdf

Generalization error is the difference with the training error and test error

In practice, the generalization error seems to be small, even when the number of parameters is huge. What is the reason for this?

Model family?

The effective capacity of neural networks is sufficient for memorizing the entire data set.  Even CNNs

Regularization?

( weight decay, dropout,  data augmentation) "Explicit regularization may improve generalization performance, but is neither necessary nor by itself sufficient for controlling generalization error".

The training method (SGD)?

Batch renormalization helps

Data augmentation helps. (domain-specific transformations, random cropping, random perturbation of brightness, saturation, hue and contrast)

But CNNs for images with SGD s easily fit even training data where labels are random”

The way to distort the “natural data manifold” and measure how it affects the test error.

True labels

Partially corrupted labels: independently with probability p, the label of each image is corrupted as a uniform random class.

Random labels: all the labels are replaced with random ones.

Shuffled pixels: a random permutation of the pixels is chosen and then the same permutation is applied to all the images in both training and test set.

Random pixels: a different random permutation is applied to each image independently.

Gaussian: Gaussian distribution(with matching mean and variance to the original image dataset) is used to generate random pixels for each image.

10.3 Adversarial examples

https://arxiv.org/pdf/1801.02774.pdf

Reasons for adversarial examples could be that:

neural networks are too linear in various regions of the input space.

adversarial examples are off the data manifold

large singular values of internal weight matrices may cause the classifier to be vulnerable to small perturbations of the input.

Is there a flaw in the network architecture?

One has tried to

increase robustness to small perturbations

distill a large network into a small network

use regularization

detecting adversarial examples statistically

use adversarial training to increase robustness

However, these do not seem to work very well. These seem to work:

reduce test error.

add visible noise to the input.

“For any model with reasonable accuracy, most errors are “adversarial” relative to some example data point, in the sense that for a typical incorrectly classified point there is a small perturbation that will cause it to be correctly classified”.

Example. It is easy to find adversarial examples

datapoints = RandomReal[{0,1},{10,2} ];ListPlot[datapoints, AspectRatio->1]

classes={"1","2","3","4","5","6","7","8","9","10"};

dataC =MapIndexed[ (#1->classes[[#2]][[1]])&, datapoints]

netC=NetChain[{5,Tanh,10,SoftmaxLayer[]},"Input"->{2},"Output"->NetDecoder[{"Class",classes}]]

trainedC = NetTrain[ netC,dataC,MaxTrainingRounds->100000 ]

datapoints //trainedC

Show[ListPlot[datapoints, AspectRatio->1],Quiet@Table[ContourPlot[trainedC[{x,y},{"Probability",number}]==0.5,{x,0,1},{y,0,1}],{number,classes}]]

Show[Quiet@Table[ContourPlot[trainedC[{x,y},{"Probability",number}]==0.75,{x,-1,2},{y,-1,2}],{number,{"1","2","3","4","5","6","7","8","9","10"}}],ListPlot[datapoints, AspectRatio->1]]

Show[VoronoiMesh[datapoints],ListPlot[datapoints, AspectRatio->1,PlotStyle->{Red,PointSize[Large]}],Quiet@Table[ContourPlot[trainedC[{x,y},{"Probability",number}]==0.9,{x,0,1},{y,0,1}],{number,{"1","2","3","4","5","6","7","8","9","10"}}]]

w1C=NetExtract[trainedC, {1, "Weights"}]//Normal

b1C= NetExtract[trainedC, {1, "Biases"}]//Normal

Show[ {ContourPlot[ # .{x, y} &  @ w1C + b1C ==0,{x,0,1},{y,0,1}],ListPlot[datapoints]}]

entoplot=ArrayPlot[Table[trainedC[{x,y},"Entropy"],{y,1,0,-.005},{x,0,1,.005}]]

The uncertainty lies very close to the some of the data points.

ListPlot[datapoints, AspectRatio->1,PlotStyle->{Red,PointSize[Large]},Axes->False]

Small adversarial examples are easy to find. The dark areas are under uncertainty.

10. 4 Adversarial Images

https://arxiv.org/pdf/1805.12152.pdf

https://arxiv.org/pdf/1804.11285.pdf

Adversarial examples are trained to fool the network. The idea is to use gradient ascend to maximize the error when changing pixel values: that is

(Underscript[max , δ∈Δ]) ℒ[ x+δ,y;θ]

The gradient of the image pixels can also be used for figuring out what makes a cat cat, and figuring out what is a super cat, an optimal stimulus of the network. However the gradient is quite hard to interpret.

Style transfers and weird dreamy images:

Anyway, this repetition (super normal stimulus[1951], Nikolas Tinbergen  (15 April 1907 – 21 December 1988))  happen in real neural networks as well (:

But, here is an example of an adversarial use:

[Goodfellow et al. 2014]

Here is an other one, but now one is starting from random noise.

The  squared images are airplanes with more than 50% accuracy.

10.5 Adversarial robustness

In adversarial training one is trying the minimize the error under maximal adversarial attack:

(Underscript[ min, θ])(Underscript[𝔼, {x,y} ∼\[RawEscape]𝔻])[(Underscript[max , δ∈Δ]) ℒ[ x+δ,y;θ]]

This is harder to train and requires more data - and the results on the test sets are worse.

BUT: By training this way the salient features become semantically meaningful

Interpolation between original image and large-ε adversarial example

Images from Tsirpas  et al. [2018]   https://arxiv.org/pdf/1805.12152.pdf

Semantic adversariality

It is not surprising that there are images that can turn to be something else with very small changes. This is known from human neural networks as well. In fact, an image can be classified wrongly with an zero adversarial modification:

I wonder when the machines are going to handle this. Can we?

10.5 Deep learning and overfitting.

Direct Fit to Nature: An Evolutionary Perspective on Biological and Artificial Neural Networks
Uri Hasson, Samuel A.Nastase, Ariel Goldstein

Hyperlink["https://www.sciencedirect.com/science/article/pii/S089662731931044X"]

For small amount of data deep neural networks overfit as one would expect. If you increase the amount of data significantly, something weird happens.  Even if the system has large number of parameters that would allow a perfect, zero loss fit as discussed in section  10.1.

Big Data, 10 000 points.

Deep :

universalnetD =NetChain[{300,Ramp,2000,Ramp,300, Ramp, 1},"Input"-> "Scalar","Output"-> "Scalar"];
universalnetD= NetInitialize[universalnetD,Method-> "Xavier"];
valuesD = RandomReal[{-1,1}, {10000,2}];
dataxyD = 2π #[[1]]+ π -> Cos[2π #[[1]]+π]+ 0.1 # [[2]]& /@ valuesD;

Training and results:

universalnetD = NetTrain[universalnetD, dataxyD,MaxTrainingRounds->1000]

Show[{ListPlot[dataxy/.Rule->List, PlotStyle->{Orange, PointSize[0.001]}] ,Plot[ {universalnetD[x],Cos[x]},{x,-π,3π}]},ImageSize->Full, PlotLabel->"Training data (in Orange) 10 000 points with gaussian error of Cos[x] (in Orange) \r 3-layer network with 300 neurons in layer (in blue)"]

Analytical solution.

Easier way to get the equations right.

valuesD = RandomReal[{-1,1}, {10000,2}];

dataxy = 2π #[[1]]+ π -> Cos[2π #[[1]]+π]+ 0.1 # [[2]]& /@ valuesD;

dataXY = Sort[ dataxy, #1[[1]] < #2[[1]] &];

Manipulate[ ListPlot[ dataXY[[i;;j]]/.Rule->List, ImageSize->Full], {i,1,j,1},{j,2,10000,1}]

x0=dataXY[[;;,1]];

x0=AppendTo[x0,3π];x0= PrependTo[ x0,-π];

y0=dataXY[[;;,2]];

Differences[1/#  & /@  Differences[x0] Differences[Ramp[#-x] & /@ x0]];

Length[Differences[1/#  & /@  Differences[x0] Differences[Ramp[#-x] & /@ x0]]]

overfitAN= Differences[1/#  & /@  Differences[x0] Differences[Ramp[#-x] & /@ x0]].y0;

Plot[ %, {x,-π-1, 3π+1}, ImageSize->Full]

10.5  Deep learning can be used to solve problems that could be solved analycially - and vice versa.

For data set  {(Subscript[x, i]), (Subscript[y, i])} ∈(ℝ^2), a localized shape function can be created:

Differences[(1/#  & /@ Differences[Array[(Subscript[x, #]) &, {10}]])Differences[Array[Ramp[(Subscript[x, #])-x] &, {10}]]]. Array[(Subscript[y, #]) &, {8}]

(-((-Ramp[-x+(Subscript[x, 1])]+Ramp[-x+(Subscript[x, 2])])/(-(Subscript[x, 1])+(Subscript[x, 2])))+((-Ramp[-x+(Subscript[x, 2])]+Ramp[-x+(Subscript[x, 3])])/(-(Subscript[x, 2])+(Subscript[x, 3])))) (Subscript[y, 2])+(-((-Ramp[-x+(Subscript[x, 2])]+Ramp[-x+(Subscript[x, 3])])/(-(Subscript[x, 2])+(Subscript[x, 3])))+((-Ramp[-x+(Subscript[x, 3])]+Ramp[-x+(Subscript[x, 4])])/(-(Subscript[x, 3])+(Subscript[x, 4])))) (Subscript[y, 3])+(-((-Ramp[-x+(Subscript[x, 3])]+Ramp[-x+(Subscript[x, 4])])/(-(Subscript[x, 3])+(Subscript[x, 4])))+((-Ramp[-x+(Subscript[x, 4])]+Ramp[-x+(Subscript[x, 5])])/(-(Subscript[x, 4])+(Subscript[x, 5])))) (Subscript[y, 4])+(-((-Ramp[-x+(Subscript[x, 4])]+Ramp[-x+(Subscript[x, 5])])/(-(Subscript[x, 4])+(Subscript[x, 5])))+((-Ramp[-x+(Subscript[x, 5])]+Ramp[-x+(Subscript[x, 6])])/(-(Subscript[x, 5])+(Subscript[x, 6])))) (Subscript[y, 5])+(-((-Ramp[-x+(Subscript[x, 5])]+Ramp[-x+(Subscript[x, 6])])/(-(Subscript[x, 5])+(Subscript[x, 6])))+((-Ramp[-x+(Subscript[x, 6])]+Ramp[-x+(Subscript[x, 7])])/(-(Subscript[x, 6])+(Subscript[x, 7])))) (Subscript[y, 6])+(-((-Ramp[-x+(Subscript[x, 6])]+Ramp[-x+(Subscript[x, 7])])/(-(Subscript[x, 6])+(Subscript[x, 7])))+((-Ramp[-x+(Subscript[x, 7])]+Ramp[-x+(Subscript[x, 8])])/(-(Subscript[x, 7])+(Subscript[x, 8])))) (Subscript[y, 7])+(-((-Ramp[-x+(Subscript[x, 7])]+Ramp[-x+(Subscript[x, 8])])/(-(Subscript[x, 7])+(Subscript[x, 8])))+((-Ramp[-x+(Subscript[x, 8])]+Ramp[-x+(Subscript[x, 9])])/(-(Subscript[x, 8])+(Subscript[x, 9])))) (Subscript[y, 8])+(-((-Ramp[-x+(Subscript[x, 8])]+Ramp[-x+(Subscript[x, 9])])/(-(Subscript[x, 8])+(Subscript[x, 9])))+((-Ramp[-x+(Subscript[x, 9])]+Ramp[-x+(Subscript[x, 10])])/(-(Subscript[x, 9])+(Subscript[x, 10])))) (Subscript[y, 9])

Manipulate[Plot[ {-((-Ramp[-x+(Subscript[x, 1])]+Ramp[-x+(Subscript[x, 2])])/(-(Subscript[x, 1])+(Subscript[x, 2])))+((-Ramp[-x+(Subscript[x, 2])]+Ramp[-x+(Subscript[x, 3])])/(-(Subscript[x, 2])+(Subscript[x, 3])))}, {x,-3,3},PlotRange->Full], {{(Subscript[x, 1]),-1}, -4,4},{{(Subscript[x, 2]),0},-4,4}, {{(Subscript[x, 3]),1},-4,4}]

Easier way to get the equations right is just to train it.

Even, if there is an analytical equation, sometimes just using deep learning gives you the right answer.

data=Table[x->Exp[-x^2]+RandomVariate[NormalDistribution[0,.15]],{x,-3,3,.2}];
Length[data];plot=ListPlot[List@@@data,PlotStyle->Red]

neto=NetChain[{150,Tanh,150,Tanh,1}]

results1=NetTrain[neto,data,All,TimeGoal->30]

results1["FinalRoundLoss"]

overfitNet=results1["TrainedNet"]

Show[Plot[overfitNet[x],{x,-3,3}],plot]

Or just utilize the neural network as you analytical platform

Analytical solution.

However, this you do not have to train:

data

x1= data[[;;,1]]

x1 = AppendTo[x1,3.2];x1 = PrependTo[x1,-3.2];

y1=  data[[;;,2]]

Differences[1/#  & /@  Differences[x1] Differences[Ramp[#-x] & /@ x1]]

Plot[ %,{x,-4,4}]

Length[x1]

Length[y1]

Length[Differences[1/#  & /@  Differences[x1] Differences[Ramp[#-x] & /@ x1]]]

Differences[1/#  & /@  Differences[x1] Differences[Ramp[#-x] & /@ x1]].y1

Show[Plot[%,{x,-4,4}],plot]

10.7  Why now,  why not 50 years ago?

Information bottleneck as a source of generalization capability.

According to Naftali Tishby deep neural networks learn through forcing the system though "information bottleneck,. 
“The idea is that a network rids noisy input data of extraneous details as if by squeezing the information through a bottleneck, retaining only the features most relevant to general concepts. Striking new computer experiments by Tishby and his student Ravid Shwartz - Ziv reveal how this squeezing procedure happens during deep learning, at least in the cases they studied”.

The information bottleneck (IB) as a theoretic principle for extracting relevant information that an input random variable X ∈ 𝒳 contains about an output random variable Y ∈ 𝒴. Given their joint distribution p (X, Y ), the relevant information is defined as the mutual information I (X ; Y ), where we assume statistical dependence between X and Y . In this case, Y implicitly determines the relevant and irrelevant features in X.  Optimal representation of X would capture the relevant features, and compress X by dismissing the irrelevant parts which do not contribute to the prediction of Y.

Hyperlink["https://www.youtube.com/watch?v=bLqJHjXihK8"]

Hyperlink["https://www.youtube.com/watch?v=FSfN2K3tnJU"]

Hyperlink["https://www.quantamagazine.org/new-theory-cracks-open-the-black-box-of-deep-learning-20170921/"]

Hyperlink["https://www.youtube.com/watch?v=gqCztk6hi4Y"]

10.8 Intelligible models / Explainability

http://people.dbmi.columbia.edu/noemie/papers/15kdd.pdf

Aiming to  predict probability of death (POD) from pneumonia, from health care models.

G. Cooper, V. Abraham, C. Aliferis, J. Aronis, B. Buchanan, R. Caruana, M. Fine, J. Janosky,
G. Livingston, T. Mitchell, S. Montik, and P. Spirtes. “Predicting dire outcomes of patients with community acquired pneumonia”. Journal of Biomedical Informatics, 38(5):347–366, 200

led to a result that asthma lowers the probability. As the system was rule-based, it was pretty easy to correct the problem by removing the rule.

But using the same data with neural networks would give the same result, but it would not be easily extractable from the neural network weights.

The real problem is that as knowing the problem makes it possible to correct it, you cannot correct things that you do not know. What other process derived rules would be lurking in the inference?

Hence, sometimes intelligibility is even more important than accuracy.

Generalized Additive Models.  (GAM)

http://www.cs.cornell.edu/~yinlou/papers/lou-kdd13.pdf

For data  𝒟={{(Subscript[x, i]) ,(Subscript[y, i])}], where  (Subscript[x, i]) has all the features and (Subscript[y, i]) is the annotation, a standard intelligible model has

g[𝔼[y]]=(Subscript[β, o])+ ∑(Subscript[f, j])[ (Subscript[x, j])]

g is called link function, the function (Subscript[f, j])  perform ”feature shaping”.

Here the influence of all term can be be plotted as (Subscript[f, j])[ (Subscript[x, j])] vs.  (Subscript[x, j])

Notice that this is a perceptron - one layer neural network with features preprocessed by the feature  shaping functions (Subscript[f, j]) or a two layer network with a given nonlinearity.

Graph[Join[ Table[ j-> i,{j,1,5},{i,2+5j,6+5j}],Table[ i-> j+100,{j,1,5},{i,2+5j,6+5j}],Table[ j+100-> 0,{j,1,5}]]//Flatten,VertexLabels->Join[Table[i->(Subscript[x, i]),{i,5}],Table[i+100->(Subscript[f, i])[(Subscript[x, i])],{i,5}],{0->g[𝔼[y]] }]//Flatten, PlotLabel->"Neural network realization", PlotTheme->"Bold"]

A little more expressive power is given by adding pairwise interactions of features

g[𝔼[y]]=(Subscript[β, o])+ ∑(Subscript[f, j])[ (Subscript[x, j])] +∑(Subscript[f, ij])[(Subscript[x, i]), (Subscript[x, j])]

Then one says that intelligibility is preserved as the functions (Subscript[f, ij])[(Subscript[x, i]), (Subscript[x, j])] can be shown as heat maps.

Graph[Join[ Table[ j-> i,{j,1,3},{i,2+5j,6+5j}],Table[ j-> i,{j,4,5},{i,2+5 4,6+5 4}],Table[ i-> j+100,{j,1,3},{i,2+5j,6+5j}],Table[ i-> j+100,{j,4,4},{i,2+5j,6+5j}],Table[ j+100-> 0,{j,1,4}]]//Flatten,VertexLabels->Join[Table[i->(Subscript[x, i]),{i,5}],Table[i+100->(Subscript[f, i])[(Subscript[x, i])],{i,3}],{104->(Subscript[f, 45])[(Subscript[x, 4]),(Subscript[x, 5])]},{0->g[𝔼[y]] }]//Flatten, PlotLabel->"(Subscript[x, 4]) and (Subscript[x, 5]) are interacting", PlotTheme->"Bold"]

This is called “Generalized Additive Models plus Interactions”  or  (GA^2)M

One way to make this simple is to restrict the function (Subscript[f, ij])[(Subscript[x, i]),(Subscript[x, j])] to a form that divides the the heat map to vertical and horizontal regimes. This is called the FAST method. (http://www.cs.cornell.edu/~yinlou/papers/lou-kdd13.pdf)

10.9 Deep neural network is not a black box

It is fully transparent. Let us suppose that this image is reality.

ContourPlot[Sign[Cos[x y]],{x,-2π,2π},{y,-2π,2π}]

And we have some data about the reality:

dataoI =( {#[[1]],#[[2]]}-> Sign[Cos[#[[1]] #[[2]]]])& /@  RandomReal[{-2π,2π},{10000,2}];ListPlot[dataoI[[All,1]],AspectRatio->1]

Let us include the annotation - the knowledge, and meaning, what this data points really are:

ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{Red,Green}]

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}]

Finding meaning by partitioning the data.

Deep neural network tries to find the meaning by partitioning the data manifold.  It divides the world into two parts and tries to find a place where this division would be sensible, that is, provide some information about the what is green and what is red.

As the partitioning progresses there is more an more information about the red and green, and less and less information (in the partitions) where the data original data points were.

On the first linear partition there is informati0n about the position - is the data point above the line or not. There is not too much data about if the dots are red or green. In most of the partitions the amounts of green and red points are about the same.

Manipulate[d1=(dataoI//Select[(#[[1]]-q1).q1>0&&#[[2]] >0& ])[[All,1]];d2=(dataoI//Select[(#[[1]]-q1).q1>0 &&#[[2]]<0& ])[[All,1]]; ListPlot[{d1,d2},AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}, PlotRange->{{-2π,2π},{-2π,2π}},PlotLabel-> {"red ",Length[d1]/(Length[d1]+Length[d2]),"Green",Length[d2]/(Length[d1]+Length[d2])},Epilog->{Red, Line[{{0,0},q1}]}], {{q1,{-1,1}},Locator}]

(* netoI=NetChain[{150,LogisticSigmoid,70,LogisticSigmoid,20,LogisticSigmoid,1},"Input"->2,"Output"-> "Scalar"] *)
netoI=NetChain[{70,LogisticSigmoid,35,LogisticSigmoid,10,LogisticSigmoid,1},"Input"->2,"Output"-> "Scalar"]

netoI=NetInitialize[netoI,Method->"Xavier"]; Plot3D[ netoI[{x,y}],{x,0,1},{y,0,1}, ImageSize->200, PlotLabel->"Initialized network netoI[x,y]", AxesLabel->Automatic ]

netoI = NetTrain[ netoI, dataoI,MaxTrainingRounds->100000]

ContourPlot[ netoI[{x,y}],{x,-2π,2π},{y,-2π,2π},Contours->40, PlotRange->{-0.5,1.5}]

Export["//Users/karkkal2/Documents/Aalto/Lectures/Autumn2020/netoIs.wlnet",netoI]

netoI= Import["//Users/karkkal2/Documents/Aalto/Lectures/Autumn2020/netoIs.wlnet"]

Plot3D[ netoI[{x,y}],{x,-2π,2π},{y,-2π,2π}, PlotRange->{-0.5,1.5}]

Looking inside

This is a text cell.

w1 = NetExtract[netoI, {1, "Weights"}]//Normal;b1=NetExtract[netoI,{1,"Biases"}]//Normal;w3 = NetExtract[netoI,{3,"Weights"}]//Normal;b3=NetExtract[netoI,{3,"Biases"} ]//Normal;
w5 = NetExtract[netoI, {5, "Weights"}]//Normal;b5=NetExtract[netoI,{5,"Biases"}]//Normal;w7= NetExtract[netoI,{7,"Weights"}]//Normal;b7=NetExtract[netoI,{7,"Biases"} ]//Normal;

Dimensions /@ {w1,w3,w5 ,w7}

First partition

The data manifold is spliced into two parts in 70 different ways.

ContourPlot[ #.{x, y} &  @ w1 + b1 ==0,{x,-2π,2π},{y,-2π,2π}]

Some partitions do not have any points to define their values. There one can values that have nothing to do with the training data

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Tiny]},{Green,PointSize[Tiny]}}];Manipulate[ Show[{ContourPlot[ #.{x, y} &  @ w1 + b1 ==0,{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}],graph}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π}]

Second layer activations

One starts to see partitions (these are formed from the first layer partitions) that do provide information about the red and green points.

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}];
Manipulate[ Show[{ContourPlot[Evaluate[#.LogisticSigmoid[ #.{x, y} &  @ w1 + b1 ] & @ w3 + b3 ][[i]]==0,{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}],graph}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π},{i,1,35,1}]

Manipulate[ Plot3D[Evaluate[LogisticSigmoid[#.LogisticSigmoid[ #.{x, y} &  @ w1 + b1 ] & @ w3 + b3 ]][[i]],{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}, PlotRange->{0,1}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π},{i,1,35,1}]

Third layer activations

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}];Manipulate[ Show[{ContourPlot[Evaluate[#.LogisticSigmoid[#.LogisticSigmoid[ #.{x, y} &  @ w1 + b1 ] &  @w3 + b3] & @ w5 + b5][[i]],{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}],graph}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π},{i,1,10,1}]

Including the logistic sigmoid - synaptic output to next layer.

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}];Manipulate[ Show[{ContourPlot[Evaluate[LogisticSigmoid[#.LogisticSigmoid[#.LogisticSigmoid[ #.{x, y} &  @ w1 + b1 ] &  @w3 + b3] & @ w5 + b5]][[i]],{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}],graph}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π},{i,1,10,1}]

Fourth and final  layer

On the final layer the binary  partitioning starts to be good. Now, it has pretty good information about where all the green and red colored points are. However, the partition is quite agnostic on the position - it could be pretty evenly distributed a cross the plot.

Also one can see clever collaboration between the layers, the third layer pattens seem to be pretty far from the solution,  but a clever combination of the feature brings out a good solution.

It seems that the third layer network should have had a few more  neurons to cover the tine boundary features at the corners.

graph=ListPlot[{Select[dataoI,#[[2]] >0 &][[All,1]],Select[dataoI,#[[2]]<0 &][[All,1]] },AspectRatio->1, PlotStyle->{{Red,PointSize[Small]},{Green,PointSize[Small]}}];Manipulate[ Show[{ContourPlot[Evaluate[#.LogisticSigmoid[#.LogisticSigmoid[#.LogisticSigmoid[ #.{x, y} &  @ w1 + b1 ] &  @ w3 + b3] & @ w5 + b5] & @ w7 + b7],{ x,-2π  s+tx,2π s  +tx},{ y,-2π s +ty,2π  s+ty}],graph}],{{s,1},0.0001,2},{{tx,0},-2π,2π},{{ty,0},-2π,2π}]

10.9 Differential Privacy

Basics

Differential privacy works by adding randomness to the queries on confidential data. The aim is to make it harder to reconstruct the underlying data from the results of the query.

Define statistical database to be set of data that is collected under the pledge of confidentiality. The idea is to give out only aggregate values that do not identify the individuals.

The idea of differential privacy is to add noise to system, equivalent to the level that is produced by removing an individual from the database.

Randomized response

Finding the statistics for a humiliating question. What is the percentage for ?

If X and Y∼ Bernouilli[(1/2)] , then response r  to a question Q∼Bernouilli[q]

r=x q+(1-x) y =>

ℙ[r=1]=ℙ[x=1] q+ℙ[x=0] ℙ[y=0]=(q/2)+(1/2)(1/2) =>

q=2 ℙ[r=1]-(1/4)

So, from the randomized responses r we can estimate the prevalence of q.

What happens, if one repeats this procedure many times?

Privacy budget in differential privacy

What happens, if one repeats this procedure many times?

Application to medical data gathering from mobiles

Multidimensional.

Local inference needed for rare, anomaly type of situations.

Sent data always randomized.

Accuracy estimates.

https://ieeexplore.ieee.org/document/6883988?tp=&arnumber=6883988&queryText%3Daoki%20sezaki=

Summary

Concepts

Adversarial examples

Overfitting in deep learning

Multiple scattered argumentation why deep learning should  not /should work.

Differential privacy