Convolution measures the overlap or *similarity between two functions* as one is shifted relative to the other. It is widely used in signal processing, image processing, and machine learning, particularly in [[Convolutional Neural Networks]]. **Definition:** $ (f* g)(t) \equiv \sum_x f(x) \cdot g(t-x) $ where: - $f(x)$: Input function (or signal) - $g(t-x)$: Kernel (or filter), flipped and shifted by $t$. - $f*g$: Result of the convolution. **Key Steps:** - Flip the kernel $g(x)$, resulting in $g(-x)$ - Shift $g(-x)$ by $t$, resulting in $g(-x+t)$ or $g(t-x)$ - Compute the [[Dot Product]] between $f(x)$ and $g(t-x)$ for each shift The convolution produces a new function that represents how similar $f(x)$ and the shifted kernel $g(t - x)$ are at each point. **Cross-Correlation:** While convolution flips $g(x) \mapsto g(t-x)$, another variation is cross-correlation, where $g(x) \mapsto g(t+x)$ is only shifted but not flipped. Both lead to the same results when the kernel is symmetric. ## Application in Convolutional Neural Networks In a [[Convolutional Neural Networks|CNN]] it actually does not matter if we use either *cross-correlation* or *convolution*, since the filters where we apply them on is learned by the algorithm. So if we choose convolution it will just learn a flipped version of the filter and vice versa. Convolution can also be used to compute the [[Sum of Independent Random Variables]]. However, the independence assumption is not needed for the purpose of CNNs, as it serves a different purpose. ## Example: Discrete Convolution Assume: - Input signal $f(x) =\{1,2,3\}$ - Filter $g(x)= \{2,3\}$. We flip the filter and apply different shifts $t$ to it. The convolution is the dot product of the flipped filter evaluated at each shift. Theoretically we try all shifts from $-\infty$ to $\infty$. Practically all regions without any overlap evaluate to $0$. ![[convolution.png|center|500]]