5 ms·

Aren't these attacks just proof of the fact that even deep neural networks are approximating a high dimensional function by clamping the entropy of the formula,

Aren't these attacks just proof of the fact that even deep neural networks are approximating a high dimensional function by clamping the entropy of the formula, rather than truncating the range of input/output values? For a 32x32 image, the space of 1-pixel attacks is 0xFFFFFF * 32 * 32 = 17179868160 = e^23 Expecting an input space as large as that to not poke through the entropically deprived network is destined to fail.

eximius 9y ago
I mean, you don't even need a proof of that. The latter is impossible since the range of input/output values is untruncated by construction?
- tomhallett 9y ago
  I'm very new to ML, so I understand about 50% of what @eximius and @goldenkey are saying, but definetly not 100%. can anyone explain it in a bit more detail? (im assuming "entropy" is the key concept i need to put on my learning queue.) “approximating a high dimensional function by clamping the entropy of the formula, rather than truncating the range of input/output values” “not poke through the entropically deprived network is destined to fail” “the range of input/output values is untruncated by construction”
  - deleted 9y ago
    [deleted]
  - tomrod 9y ago
    I presume you have a regression background. If so: "minimizing entropy" is the same paradigm as "minimizing the sum of squares", in a different context. If not: reducing entropy means finding weights/coefficients in a supplied functional form that minimize some objective function applied to the problem. Usually the jargon applies to Shannon entropy from signal theory, or some derivation thereof like transfer entropy. Entropic estimates take a form similar to $$ -\sum(j) {p(x_j) log(p(x_j))}$$ where j is the event space (e.g. heads or tails on a coin flip).
  - eximius 9y ago
    If I have a function f(x,y, z) = <some expression> \in R^5 (i.e., f: R^3 => R^5) that is hard to compute, I can train a neural network to approximate it such that there are three input neurons x', y', z', some hidden layers doing the approximation, and 5 output neurons representing the approximation of the input. By construction, the domain and codomain are not constrained. Both the original and our approximation using NN take any three real values and return any five real values. Next, consider a sample of points from some function. I can perfectly fit those points using a polynomial of degree equal to the number of points by just setting f(x) = (x-y_1)(x-y_2)... If, however, I approximate the function by removing some degrees from the formula, I remove information (entropy) from the formula. It is no longer a perfect match, but it might be very close. Or, if the underlying distribution is of low dimensionality, it might still be an exact match (i.e., picking any number of points from a straight line doesn't mean you need a high degree polynomial to approximate it!).
  - madez 9y ago
    The set of all mappings between an input set of N elements to some output set with M elements has M^N elements. If you wanted to be able to represent in some way any arbitrary mapping for given sets of input and output, then you would need at least log_2(M^N) = N x log_2(M) bits. In the case of an input set of 32x32 pixel images with 3 bytes per pixel (one for each channel) we have N = 2^8 x 2^8 x 2^8 x 2^5 x 2^5 = 2^34. In the case of an artificial neural network we have at the last level an output. There will be at least one node with at least one bit of output, so M >= 2. In general, to have anything else but the trivial map that maps every input to the same output, we always have M >= 2. So, we need at least 2^34 x log_2(2) = 2^34 bits to represent an arbitrary function between the input and the output. That is 2 gibibytes! Since the models don't need 2 gibibytes, something is going on. The magic here is that we are able to encode subsets of possible mappings very efficiently by using the execution logic of a computer. The compressed representation of the mappings in the restricted subset are the learned weights (the code to evaluate the model is also needed, but that requires less bits than what we save). We are, in a way, compressing functions, not data. Hence the "clamping of entropy of the formula". [0] The restricion of the set of possible functions will lead to new, interesting phenomena. Think of it as compression artifacts, however not on images or audio, but functions. To make a model resistant to attacks by someone knowledgeable about these artifacts, I would add noise to the input such that the artifacts are not predictable, hence not practically attackable. [0] The same basic phenomenon happens with block ciphers in cryptography. A block cipher on one block is just a permutation of the set of all different input blocks. If you have a blocksize of 64 bits, representing an arbitrary permutation would need log_2(2^64 !) bits, where the exclamation mark stands for the factorial. That number is huge, bigger than 2^69. We can't represent arbitrary permutations of blocks of 64 bits. Yet, block ciphers are permutations. What happens here is that once again we find subsets of the possible permutation we can represent efficiently. The compressed representation is the key.
    - eanzenberg 9y ago
      I’m not sure adding noise to the inputs of an equally complex model will change the information load of the NN. Because of the compression of the NN I think there will still exists new input pertubations which generate attacks.
aje403 9y ago
Brick shattering through window hypothesis finally has evidence No seriously - am I missing something? "Recent research has revealed that the output of Deep Neural Networks (DNN) can be easily altered by adding relatively small perturbations to the input vector." "Submitted on 24 Oct 2017 "
- rlayton2 9y ago
  My guess here is that we need to learn more about adding noise to datasets before they go into a neural network. Lots of existing work do alterations like transposing, rotating, flipping and so on. Adding noise, including known attacks, would be part of this.
  - goldenkey 9y ago
    Noise will definitely help if random noise is added to every input image before the neural network sees it, in production. Essentially, a pre-input pipeline state that a bad actor cannot predict, making single pixel deception totally neutered. I think what needs to be done here is to add a threshold of correlation between the input pixels. Consider that the problem is that 1 pixel change in the deviously right way, can be equivalent to the change when multiple pixels are changed in the proper way -- the derivative of the cost function. So clearly there needs to be a way to design / tell the network that 1 pixel change cannot be nearly as strong as changing multiple pixels relationships, in terms of cost function value change. From what I can garner, the only way to accomplish this is to make sure the number of nodes in the hidden layers is strictly monotonically decreasing. By using the last layer as a "grab bag" for classification, with 100s of nodes greater than the previous layers, the network becomes vulnerable to single pixel attacks. There have to be ways to design classification styles networks without the fan-out.

eximius 9y ago

I mean, you don't even need a proof of that. The latter is impossible since the range of input/output values is untruncated by construction?

tomhallett 9y ago
I'm very new to ML, so I understand about 50% of what @eximius and @goldenkey are saying, but definetly not 100%. can anyone explain it in a bit more detail? (im assuming "entropy" is the key concept i need to put on my learning queue.) “approximating a high dimensional function by clamping the entropy of the formula, rather than truncating the range of input/output values” “not poke through the entropically deprived network is destined to fail” “the range of input/output values is untruncated by construction”
- deleted 9y ago
  [deleted]
- tomrod 9y ago
  I presume you have a regression background. If so: "minimizing entropy" is the same paradigm as "minimizing the sum of squares", in a different context. If not: reducing entropy means finding weights/coefficients in a supplied functional form that minimize some objective function applied to the problem. Usually the jargon applies to Shannon entropy from signal theory, or some derivation thereof like transfer entropy. Entropic estimates take a form similar to $$ -\sum(j) {p(x_j) log(p(x_j))}$$ where j is the event space (e.g. heads or tails on a coin flip).
- eximius 9y ago
  If I have a function f(x,y, z) = <some expression> \in R^5 (i.e., f: R^3 => R^5) that is hard to compute, I can train a neural network to approximate it such that there are three input neurons x', y', z', some hidden layers doing the approximation, and 5 output neurons representing the approximation of the input. By construction, the domain and codomain are not constrained. Both the original and our approximation using NN take any three real values and return any five real values. Next, consider a sample of points from some function. I can perfectly fit those points using a polynomial of degree equal to the number of points by just setting f(x) = (x-y_1)(x-y_2)... If, however, I approximate the function by removing some degrees from the formula, I remove information (entropy) from the formula. It is no longer a perfect match, but it might be very close. Or, if the underlying distribution is of low dimensionality, it might still be an exact match (i.e., picking any number of points from a straight line doesn't mean you need a high degree polynomial to approximate it!).
- madez 9y ago
  The set of all mappings between an input set of N elements to some output set with M elements has M^N elements. If you wanted to be able to represent in some way any arbitrary mapping for given sets of input and output, then you would need at least log_2(M^N) = N x log_2(M) bits. In the case of an input set of 32x32 pixel images with 3 bytes per pixel (one for each channel) we have N = 2^8 x 2^8 x 2^8 x 2^5 x 2^5 = 2^34. In the case of an artificial neural network we have at the last level an output. There will be at least one node with at least one bit of output, so M >= 2. In general, to have anything else but the trivial map that maps every input to the same output, we always have M >= 2. So, we need at least 2^34 x log_2(2) = 2^34 bits to represent an arbitrary function between the input and the output. That is 2 gibibytes! Since the models don't need 2 gibibytes, something is going on. The magic here is that we are able to encode subsets of possible mappings very efficiently by using the execution logic of a computer. The compressed representation of the mappings in the restricted subset are the learned weights (the code to evaluate the model is also needed, but that requires less bits than what we save). We are, in a way, compressing functions, not data. Hence the "clamping of entropy of the formula". [0] The restricion of the set of possible functions will lead to new, interesting phenomena. Think of it as compression artifacts, however not on images or audio, but functions. To make a model resistant to attacks by someone knowledgeable about these artifacts, I would add noise to the input such that the artifacts are not predictable, hence not practically attackable. [0] The same basic phenomenon happens with block ciphers in cryptography. A block cipher on one block is just a permutation of the set of all different input blocks. If you have a blocksize of 64 bits, representing an arbitrary permutation would need log_2(2^64 !) bits, where the exclamation mark stands for the factorial. That number is huge, bigger than 2^69. We can't represent arbitrary permutations of blocks of 64 bits. Yet, block ciphers are permutations. What happens here is that once again we find subsets of the possible permutation we can represent efficiently. The compressed representation is the key.
  - eanzenberg 9y ago
    I’m not sure adding noise to the inputs of an equally complex model will change the information load of the NN. Because of the compression of the NN I think there will still exists new input pertubations which generate attacks.

aje403 9y ago

Brick shattering through window hypothesis finally has evidence No seriously - am I missing something? "Recent research has revealed that the output of Deep Neural Networks (DNN) can be easily altered by adding relatively small perturbations to the input vector." "Submitted on 24 Oct 2017 "

rlayton2 9y ago
My guess here is that we need to learn more about adding noise to datasets before they go into a neural network. Lots of existing work do alterations like transposing, rotating, flipping and so on. Adding noise, including known attacks, would be part of this.
- goldenkey 9y ago
  Noise will definitely help if random noise is added to every input image before the neural network sees it, in production. Essentially, a pre-input pipeline state that a bad actor cannot predict, making single pixel deception totally neutered. I think what needs to be done here is to add a threshold of correlation between the input pixels. Consider that the problem is that 1 pixel change in the deviously right way, can be equivalent to the change when multiple pixels are changed in the proper way -- the derivative of the cost function. So clearly there needs to be a way to design / tell the network that 1 pixel change cannot be nearly as strong as changing multiple pixels relationships, in terms of cost function value change. From what I can garner, the only way to accomplish this is to make sure the number of nodes in the hidden layers is strictly monotonically decreasing. By using the last layer as a "grab bag" for classification, with 100s of nodes greater than the previous layers, the network becomes vulnerable to single pixel attacks. There have to be ways to design classification styles networks without the fan-out.