Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convolutions, Polynomials and Flipped Kernels

eli.thegreenplace.net

Post reply on HN
Print view View original

21–30 of 49 posts

Re: Convolutions, Polynomials and Flipped Kernels

#21

Post by srean »

incognito124 wrote: post #7
srean wrote: post #6

Earlier quoted context omitted.

On similar lines the MAX operator on the random variables become PRODUCT operator on its distribution. It's fun to play with the (Max, +)algebra of random variables and infer it's distribution. This turns out to be quite useful in estimating completion time of dependant parallel jobs. Spawning multiple parallel jobs becomes a Max operation and chaining sequential jobs becomes a '+' operation on the completion times.…

Thanks for sharing the name of that problem! I've encountered it before while optimizing batched LLM inference. The whole batch would last until all queries in a batch were done, and by changing the batch size, you'd trade off per-query-speed (better in a larger batch) with overall performance (worse with a larger batch). Nowadays I think this is solved in an entirely different way, though.

It gets more entertaining.

It's common to wrap API calls with

retry on failure, or

spawn an identical request if taking longer than x,or

recursively spawn an identical request if taking longer than x,or

retry on failure but no more than k times.

All of these and similar patterns/decorators can be analysed using the same idea.

Re: Convolutions, Polynomials and Flipped Kernels

#22

Post by srean »

stared wrote: post #20
eliben wrote: post #15

Earlier quoted context omitted.

Indeed, generating functions are mentioned in a footnote :) Very interesting topic

Saw that! Sometimes it makes things simpler (quite a a lot of things in combinatorics), other times it is a tools for nice tricks (I have no idea how I would solved these equations if it were not for generating functions, see the appendix from a Mafia game paper, https://arxiv.org/abs/1009.1031 ).

Ooh! Lovely. Thank you.

Generating functions, Z-transforms are indispensable in probability theory, Physics, signal processing, and now it seems for a good round of Mafia while camping with friends.

Re: Convolutions, Polynomials and Flipped Kernels

#23

Post by silloncito »

ttoinou wrote: post #9
srean wrote: post #6

Earlier quoted context omitted.

On similar lines the MAX operator on the random variables become PRODUCT operator on its distribution. It's fun to play with the (Max, +)algebra of random variables and infer it's distribution. This turns out to be quite useful in estimating completion time of dependant parallel jobs. Spawning multiple parallel jobs becomes a Max operation and chaining sequential jobs becomes a '+' operation on the completion times.…

What ? I've never heard of this math. Do you mean literally those are the resulting operations in the general case or are those approximate explanation and we need to find more specific cases to make this true ?

$Let M=Max(X,Y)$. If $X$ and $Y$ are independent then: $F_M(k) = P(M \leq K) = P((X \leq K) and (Y \leq K))$, so that

  $P(X \leq K) x P(Y \leq K) = F_X(K) x F_Y(K)$.

 So $F_M = F_X \times F_Y$

Re: Convolutions, Polynomials and Flipped Kernels

#24

Post by srean »

silloncito wrote: post #23
ttoinou wrote: post #9

Earlier quoted context omitted.

What ? I've never heard of this math. Do you mean literally those are the resulting operations in the general case or are those approximate explanation and we need to find more specific cases to make this true ?

$Let M=Max(X,Y)$. If $X$ and $Y$ are independent then: $F_M(k) = P(M \leq K) = P((X \leq K) and (Y \leq K))$, so that $P(X \leq K) x P(Y \leq K) = F_X(K) x F_Y(K)$. So $F_M = F_X \times F_Y$

Thanks for making the assumption of independence explicit and welcome to HN.

Re: Convolutions, Polynomials and Flipped Kernels

#25

Post by jerf »

incognito124 wrote: post #5

My favourite use case for this: By the same derivation as this blog, one can prove that, if you have any two probability distributions X and Y (they can be different), the probability distribution of X+Y is a convolution of the PMFs/PDFs of X and Y.

3blue1brown has a walkthrough of this: https://www.youtube.com/watch?v=IaSGqQa5O-M

Re: Convolutions, Polynomials and Flipped Kernels

#26

Post by incognito124 »

srean wrote: post #21
incognito124 wrote: post #7

Earlier quoted context omitted.

Thanks for sharing the name of that problem! I've encountered it before while optimizing batched LLM inference. The whole batch would last until all queries in a batch were done, and by changing the batch size, you'd trade off per-query-speed (better in a larger batch) with overall performance (worse with a larger batch). Nowadays I think this is solved in an entirely different way, though.

It gets more entertaining. It's common to wrap API calls with retry on failure , or spawn an identical request if taking longer than x ,or recursively spawn an identical request if taking longer than x ,or retry on failure but no more than k times . All of these and similar patterns/decorators can be analysed using the same idea.

Oh wow, pretty cool stuff! If you have more to share, you can always dump it in my mail inbox

Re: Convolutions, Polynomials and Flipped Kernels

#27

Post by gjm11 »

srean wrote: post #10
ttoinou wrote: post #9

Earlier quoted context omitted.

What ? I've never heard of this math. Do you mean literally those are the resulting operations in the general case or are those approximate explanation and we need to find more specific cases to make this true ?

The math is general and exact. Max and Plus at the random variables space becomes product and convolution in their distribution function space. Distr(X+Y) = DistrX ° DistrY Distr (X ^ Y) = DistrX * DistrY. Where '^' denotes Max and '°' denotes convolution. Note *, +, ° and ^ being commutative and associative they can be chained. One can also use their distributive properties. This really the math of groups and rings.…

Surely this isn't quite right.

Max of variables = product of cumulative distribution functions.

Sum of variables = convolution of probability density functions.

So both of the equations you write down are correct, but only if you interpret "Distr" as meaning different things in the two cases.

[EDITED to add:] Provided the random variables in question are independent, as mentioned elsewhere in the discussion; if they aren't then none of this works.

Re: Convolutions, Polynomials and Flipped Kernels

#28

Post by silloncito »

srean wrote: post #24
silloncito wrote: post #23

Earlier quoted context omitted.

$Let M=Max(X,Y)$. If $X$ and $Y$ are independent then: $F_M(k) = P(M \leq K) = P((X \leq K) and (Y \leq K))$, so that $P(X \leq K) x P(Y \leq K) = F_X(K) x F_Y(K)$. So $F_M = F_X \times F_Y$

Thanks for making the assumption of independence explicit and welcome to HN.

Thank you for your welcome, I must have been lurking here for around 30 years or more (always changing accounts). Anyway in this specific case, since M = Max(X,X) = X you can't have F(M) = F(X)*F(X) = F(X) except when F(X) in {0,1}, so the independence property is essential. Welcome fellow Lisper (for the txr and related submission) and math inspired (this one and another related to statistical estimation) with OS related interest (your HN account), OS are not my cup of tea but awk is not bad).

  In another post there are some comments between topology and deep learning. I wonder if there is a definition similar to dimension in topology which would allow you to estimate the minimal size (number of parameters) in a neural network so that is able to achieve a certain state (for example obtaining the capacity to one shot learning with high probability).

Re: Convolutions, Polynomials and Flipped Kernels

#29

Post by srean »

gjm11 wrote: post #27
srean wrote: post #10

Earlier quoted context omitted.

The math is general and exact. Max and Plus at the random variables space becomes product and convolution in their distribution function space. Distr(X+Y) = DistrX ° DistrY Distr (X ^ Y) = DistrX * DistrY. Where '^' denotes Max and '°' denotes convolution. Note *, +, ° and ^ being commutative and associative they can be chained. One can also use their distributive properties. This really the math of groups and rings.…

Surely this isn't quite right. Max of variables = product of cumulative distribution functions . Sum of variables = convolution of probability density functions . So both of the equations you write down are correct, but only if you interpret "Distr" as meaning different things in the two cases. [EDITED to add:] Provided the random variables in question are independent, as mentioned elsewhere in the discussion; if the…

The original post, to which I replied, is about the correspondence between summation of random variables and convolution of their distribution. Independence is sufficient for that.

I just carried through that assumption of independence in my own comment, thinking it was obvious to do that (carry over the assumptions).

Re: Convolutions, Polynomials and Flipped Kernels

#30

Post by silloncito »

incognito124 wrote: post #26
srean wrote: post #21

Earlier quoted context omitted.

It gets more entertaining. It's common to wrap API calls with retry on failure , or spawn an identical request if taking longer than x ,or recursively spawn an identical request if taking longer than x ,or retry on failure but no more than k times . All of these and similar patterns/decorators can be analysed using the same idea.

Oh wow, pretty cool stuff! If you have more to share, you can always dump it in my mail inbox

You should be careful with your estimation. The events should be independent to apply those properties but it is very common that one cause can influence many factors, so they are not independent and all the beauty math does not work as with independence. In the worst day, all fail, because one resource can block others and the system get strangled. There is the black swan book when one rare event make the financial market realize what is risk.
Post reply on HN