3 ms·

Intuitive guide to convolution

63 points by abhi9u 3y ago

lxe 3y ago
Reminds me of Setosa's interactive explanation of image kernels: https://setosa.io/ev/image-kernels/ https://setosa.io/ev/image-kernels/
- layoric 3y ago
  This is a great post that makes the concept of image kernels way more accessible, thanks for sharing!
esafak 3y ago
Convolution: The time domain operation that corresponds to multiplication in the frequency domain.
- Paul-Craft 3y ago
  And which you can use to do actual multiplication, using the DFT and inverse DFT, if you let $f$ and $g$ be polynomials over, say $Z/(2^k +1), where the modulus is selected such that $2^k$ is the word size of your machine.
  - CyberDildonics 3y ago
    Isn't this just a complicated way of saying a computer can do multiplication?
    - Paul-Craft 3y ago
      No. It's saying a computer can do multiplication really fast by doing a bunch of additions, without having to worry about carries, instead.
      - CyberDildonics 3y ago
        Computers can do multiplication really fast without doing additions, you just have to use SIMD instructions that are already on the CPU.
  - deleted 3y ago
    [deleted]
ndriscoll 3y ago
The flip and slide thing that electrical engineers do has always struck me as unintuitive; it makes more sense to think of it as a blurring operation. Consider a function f: R^2 -> R (or Z^2 -> Z if you like) that represents a grayscale image. So f(0,0) is the pixel at the origin, f(1,0) is the pixel at (1,0), etc. Think of g: R^2 -> R as a blurring function, e.g. a gaussian. What convolution does is it turns every pixel of f into a copy of the blur g, weighted by and centered on each pixel being blurred. So f(0,0) gets turned into a blurred image h(x,y) = f(0,0)g(x,y). f(1,0) gets turned into a blurred image h(x,y) = f(1,0)g(x-1,0). Note that the subtraction is just recentering g so the blur applies in the right position. In general, each pixel gets blurred into the function h(x,y) = f(a,b)g(x-a,y-b). Now sum up all the blurred pixels, so you get the final image (f*g)(x,y) = integral_(a,b) f(a,b)g(x-a,y-b). Same thing can be done in the time domain instead of a spatial domain, or you can write it in vector form, so (f*g)(x) = integral_(r) f(r)g(x-r). Note that you can also write it in a more symmetric way as (f*g)(c) = integral_(a+b=c) f(a)g(b), which makes it clear that you can do this for any semigroup (you get the normal definition when you have a group by noting that b=c-a), makes commutativity obvious, and makes it clear why polynomial multiplication is convolution of coefficients: x^n comes from summing over all the x^i*x^j with i+j=n, so the coefficient for x^n is the sum over all coefficients indexed by i,j with i+j=n, which is the symmetric way to write convolution.
- duped 3y ago
  > it makes more sense to think of it as a blurring operation. It's not a blurring operation, it's not even an operation on images. And even when applied to images, only some convolutions result in what could be described as a "blur." This is also tautological, because you can't really define why a gaussian filter "blurs" an image without first understanding the convolution of the image and filter kernel. imho you should throw out the notion of "intuition" and stick with the mathematical definition and then explore its properties and relationships. The simplest and most intuitive description I've heard is "convolution is a mathematical operation that describes mixing two things together" (those things being vectors, matrices, continuous functions, etc)
  - ndriscoll 3y ago
Severian 3y ago
IMO 3blue1brown presents this in a very easy to understand way: https://www.youtube.com/watch?v=KuXjwB4LzSA https://www.youtube.com/watch?v=KuXjwB4LzSA
- 3abiton 3y ago
  I wonder if we will ever be at a stage where LLM can generate videos like that as an ELI5
  - westurner 3y ago
    https://github.com/360macky/generative-manim https://github.com/360macky/generative-manim : > Generative Manim is a prototype of a web app that uses GPT-4 to generate videos with Manim. The idea behind this project is taking advantage of the power of GPT-4 in programming, the understanding of human language and the animation capabilities of Manim to generate a tool that could be used by anyone to create videos. Regardless of their programming or video editing skills. "TheoremQA: A Theorem-driven [STEM] Question Answering dataset" (2023) https://github.com/wenhuchen/TheoremQA#leaderboard https://github.com/wenhuchen/TheoremQA#leaderboard How do you score memory retention and video watching comprehension? The classic educators' optimization challenge "Khan Academy’s 7-Step Approach to Prompt Engineering for Khanmigo" https://blog.khanacademy.org/khan-academys-7-step-approach-to-prompt-engineering-for-khanmigo/ https://blog.khanacademy.org/khan-academys-7-step-approach-t... "Teaching with AI" https://openai.com/blog/teaching-with-ai https://openai.com/blog/teaching-with-ai Photomath: https://en.wikipedia.org/wiki/Photomath https://en.wikipedia.org/wiki/Photomath "Pix2tex: Using a ViT to convert images of equations into LaTeX code" > latex2sympy: https://news.ycombinator.com/item?id=38138020 https://news.ycombinator.com/item?id=38138020 SymPy Beta is aWASM fork of SymPy Gamma: https://github.com/eagleoflqj/sympy_beta https://github.com/eagleoflqj/sympy_beta SymPy Gamma: https://github.com/sympy/sympy_gamma https://github.com/sympy/sympy_gamma TIL i^4x == e^2iπx import unittest import sympy as sy test = unittest.TestCase() x = sy.symbols("x") # with test.assertRaises(AssertionError): test.assertEqual(sy.I**(4*x), sy.E**(2*sy.I*sy.pi*x)) https://www.wolframalpha.com/input/?i=I%5E%284x%29+%3D%3D+e%5E%282*i*%CF%80*x%29 https://www.wolframalpha.com/input/?i=I%5E%284x%29+%3D%3D+e%...
CyberDildonics 3y ago
Any explanation should start by saying a convolution is just a weighted average.
- wnoise 3y ago
  Averages are normalized. Convolutions only are if they integrate to 1.
  - CyberDildonics 3y ago
    What are you using non normalized weighted averages for?
    - wnoise 3y ago
      I'm not! Averages should normalize the weights. But there are plenty of reasons to define convolutions where neither signal is normalized.
      - CyberDildonics 3y ago
        What are they?
- jjgreen 3y ago
  Well it is, sort of, but treating one of the functions as weights and the other as the thing that is averaged misses out on the symmetry f*g = g*f
onos 3y ago
It just smears out a signal.
ur-whale 3y ago
Convolution, or the art of given hard names to easy things. Convolution is something you learn when you're 7. It's called weighted average.
- wnoise 3y ago
  Weighted sum, sure. (Average is normalized). But it's not just one sum, but a _collection_ of weighted sums, and those have a particular order for reasons.

63 points by abhi9u 3y ago

lxe 3y ago

Reminds me of Setosa's interactive explanation of image kernels: https://setosa.io/ev/image-kernels/ https://setosa.io/ev/image-kernels/

layoric 3y ago
This is a great post that makes the concept of image kernels way more accessible, thanks for sharing!

esafak 3y ago

Convolution: The time domain operation that corresponds to multiplication in the frequency domain.

Paul-Craft 3y ago
And which you can use to do actual multiplication, using the DFT and inverse DFT, if you let $f$ and $g$ be polynomials over, say $Z/(2^k +1), where the modulus is selected such that $2^k$ is the word size of your machine.
- CyberDildonics 3y ago
  Isn't this just a complicated way of saying a computer can do multiplication?
  - Paul-Craft 3y ago
    No. It's saying a computer can do multiplication really fast by doing a bunch of additions, without having to worry about carries, instead.
    - CyberDildonics 3y ago
      Computers can do multiplication really fast without doing additions, you just have to use SIMD instructions that are already on the CPU.
- deleted 3y ago
  [deleted]

ndriscoll 3y ago

The flip and slide thing that electrical engineers do has always struck me as unintuitive; it makes more sense to think of it as a blurring operation. Consider a function f: R^2 -> R (or Z^2 -> Z if you like) that represents a grayscale image. So f(0,0) is the pixel at the origin, f(1,0) is the pixel at (1,0), etc. Think of g: R^2 -> R as a blurring function, e.g. a gaussian. What convolution does is it turns every pixel of f into a copy of the blur g, weighted by and centered on each pixel being blurred. So f(0,0) gets turned into a blurred image h(x,y) = f(0,0)g(x,y). f(1,0) gets turned into a blurred image h(x,y) = f(1,0)g(x-1,0). Note that the subtraction is just recentering g so the blur applies in the right position. In general, each pixel gets blurred into the function h(x,y) = f(a,b)g(x-a,y-b). Now sum up all the blurred pixels, so you get the final image (f*g)(x,y) = integral_(a,b) f(a,b)g(x-a,y-b). Same thing can be done in the time domain instead of a spatial domain, or you can write it in vector form, so (f*g)(x) = integral_(r) f(r)g(x-r). Note that you can also write it in a more symmetric way as (f*g)(c) = integral_(a+b=c) f(a)g(b), which makes it clear that you can do this for any semigroup (you get the normal definition when you have a group by noting that b=c-a), makes commutativity obvious, and makes it clear why polynomial multiplication is convolution of coefficients: x^n comes from summing over all the x^i*x^j with i+j=n, so the coefficient for x^n is the sum over all coefficients indexed by i,j with i+j=n, which is the symmetric way to write convolution.

duped 3y ago
> it makes more sense to think of it as a blurring operation. It's not a blurring operation, it's not even an operation on images. And even when applied to images, only some convolutions result in what could be described as a "blur." This is also tautological, because you can't really define why a gaussian filter "blurs" an image without first understanding the convolution of the image and filter kernel. imho you should throw out the notion of "intuition" and stick with the mathematical definition and then explore its properties and relationships. The simplest and most intuitive description I've heard is "convolution is a mathematical operation that describes mixing two things together" (those things being vectors, matrices, continuous functions, etc)
- ndriscoll 3y ago

Severian 3y ago

IMO 3blue1brown presents this in a very easy to understand way: https://www.youtube.com/watch?v=KuXjwB4LzSA https://www.youtube.com/watch?v=KuXjwB4LzSA

3abiton 3y ago
I wonder if we will ever be at a stage where LLM can generate videos like that as an ELI5
- westurner 3y ago
  https://github.com/360macky/generative-manim https://github.com/360macky/generative-manim : > Generative Manim is a prototype of a web app that uses GPT-4 to generate videos with Manim. The idea behind this project is taking advantage of the power of GPT-4 in programming, the understanding of human language and the animation capabilities of Manim to generate a tool that could be used by anyone to create videos. Regardless of their programming or video editing skills. "TheoremQA: A Theorem-driven [STEM] Question Answering dataset" (2023) https://github.com/wenhuchen/TheoremQA#leaderboard https://github.com/wenhuchen/TheoremQA#leaderboard How do you score memory retention and video watching comprehension? The classic educators' optimization challenge "Khan Academy’s 7-Step Approach to Prompt Engineering for Khanmigo" https://blog.khanacademy.org/khan-academys-7-step-approach-to-prompt-engineering-for-khanmigo/ https://blog.khanacademy.org/khan-academys-7-step-approach-t... "Teaching with AI" https://openai.com/blog/teaching-with-ai https://openai.com/blog/teaching-with-ai Photomath: https://en.wikipedia.org/wiki/Photomath https://en.wikipedia.org/wiki/Photomath "Pix2tex: Using a ViT to convert images of equations into LaTeX code" > latex2sympy: https://news.ycombinator.com/item?id=38138020 https://news.ycombinator.com/item?id=38138020 SymPy Beta is aWASM fork of SymPy Gamma: https://github.com/eagleoflqj/sympy_beta https://github.com/eagleoflqj/sympy_beta SymPy Gamma: https://github.com/sympy/sympy_gamma https://github.com/sympy/sympy_gamma TIL i^4x == e^2iπx import unittest import sympy as sy test = unittest.TestCase() x = sy.symbols("x") # with test.assertRaises(AssertionError): test.assertEqual(sy.I**(4*x), sy.E**(2*sy.I*sy.pi*x)) https://www.wolframalpha.com/input/?i=I%5E%284x%29+%3D%3D+e%5E%282*i*%CF%80*x%29 https://www.wolframalpha.com/input/?i=I%5E%284x%29+%3D%3D+e%...

CyberDildonics 3y ago

Any explanation should start by saying a convolution is just a weighted average.

wnoise 3y ago
Averages are normalized. Convolutions only are if they integrate to 1.
- CyberDildonics 3y ago
  What are you using non normalized weighted averages for?
  - wnoise 3y ago
    I'm not! Averages should normalize the weights. But there are plenty of reasons to define convolutions where neither signal is normalized.
    - CyberDildonics 3y ago
      What are they?
jjgreen 3y ago
Well it is, sort of, but treating one of the functions as weights and the other as the thing that is averaged misses out on the symmetry f*g = g*f

onos 3y ago

It just smears out a signal.

ur-whale 3y ago

Convolution, or the art of given hard names to easy things. Convolution is something you learn when you're 7. It's called weighted average.

wnoise 3y ago
Weighted sum, sure. (Average is normalized). But it's not just one sum, but a _collection_ of weighted sums, and those have a particular order for reasons.