4 ms·

Nice. Is it amenable to a deep-learning gpu op ? There is a trivial channel-wise parallelization. There are also little more complicated image-size-wise paralle

Nice. Is it amenable to a deep-learning gpu op ? There is a trivial channel-wise parallelization. There are also little more complicated image-size-wise parallelization with stitching. The real crux is computing the gradient op, I don't seem to figure a way to do the same histogram trick. (Edit : after thinking a little more, in the edge case with an image of constant value, the adjoint of median must add the gradient contribution to every pixel in the radius, meaning the backward pass won't be constant time. Maybe with a softer definition of the median for which the adjoint is allowed to pick pseudo-randomly one the index among the indices of the median values, we can still salvage it.)

throwaway_bad 7y ago
How does max pool deal with this? It seems similar where you rank all the pixel values and take the max (rather than median). The problem with ties still occurs there, no?
- GistNoesis 7y ago
  Good idea. I've looked at tensorflow approach for backward max pool [0] They seem to be using a naive algorithm, scanning over the pool area and picking the first index whose value match the pooled max, so the bigger the kernel radius the slower it gets. They deal with the tie problem by taking the index of first value that match the max value (with float32 that's an edge case that should almost never happen so it's a fine speedup). My guess is it's probably possible to apply this constant time algorithm doing the same sort of approximation for the ties, but you also need to enrich the histograms so that in addition to the count it also store and update the last index associated with the count. I also just noticed that the constant time algorithm hasn't been run for float values. It's not really a problem though because we can use some order preserving bit-tricks to convert float32 to UInt32 and then truncate to UInt16 [1]. [0] https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/maxpooling_op_gpu.cu.cc#L337 https://github.com/tensorflow/tensorflow/blob/master/tensorf... [1] https://fgiesen.wordpress.com/2013/01/21/order-preserving-bijections/ https://fgiesen.wordpress.com/2013/01/21/order-preserving-bi...
DoctorOetker 7y ago
before trying to find out if it can be similarily optimized in deep learning, one would have to define a differentiable equivalent of histograms / means. One approach would be to define the histogram as H(x) = sum_i_0,N ( A * exp(-((x-x_i)/B)^2)) with B a spread parameter, and A a normalization constant so that a single sample integrates to a unit area under the gaussian. The mean M would then be the value such that integrating from minus infinity to M equals N/2 (half the samples below, and half above, with sample position blurred along the histogram) Perhaps a different convolution function can be chosen for easier integration? A/(x+B)^2, is symmetric and perhaps more easily integrated.

throwaway_bad 7y ago

How does max pool deal with this? It seems similar where you rank all the pixel values and take the max (rather than median). The problem with ties still occurs there, no?

GistNoesis 7y ago
Good idea. I've looked at tensorflow approach for backward max pool [0] They seem to be using a naive algorithm, scanning over the pool area and picking the first index whose value match the pooled max, so the bigger the kernel radius the slower it gets. They deal with the tie problem by taking the index of first value that match the max value (with float32 that's an edge case that should almost never happen so it's a fine speedup). My guess is it's probably possible to apply this constant time algorithm doing the same sort of approximation for the ties, but you also need to enrich the histograms so that in addition to the count it also store and update the last index associated with the count. I also just noticed that the constant time algorithm hasn't been run for float values. It's not really a problem though because we can use some order preserving bit-tricks to convert float32 to UInt32 and then truncate to UInt16 [1]. [0] https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/maxpooling_op_gpu.cu.cc#L337 https://github.com/tensorflow/tensorflow/blob/master/tensorf... [1] https://fgiesen.wordpress.com/2013/01/21/order-preserving-bijections/ https://fgiesen.wordpress.com/2013/01/21/order-preserving-bi...

DoctorOetker 7y ago

before trying to find out if it can be similarily optimized in deep learning, one would have to define a differentiable equivalent of histograms / means. One approach would be to define the histogram as H(x) = sum_i_0,N ( A * exp(-((x-x_i)/B)^2)) with B a spread parameter, and A a normalization constant so that a single sample integrates to a unit area under the gaussian. The mean M would then be the value such that integrating from minus infinity to M equals N/2 (half the samples below, and half above, with sample position blurred along the histogram) Perhaps a different convolution function can be chosen for easier integration? A/(x+B)^2, is symmetric and perhaps more easily integrated.