Convolutions, Polynomials and Flipped Kernels • Hacker News Board

Re: Convolutions, Polynomials and Flipped Kernels

#31

Post by srean » Wed, May 21, 2025, 3:39 PM UTC

silloncito wrote: post #28

srean wrote: post #24

Earlier quoted context omitted.

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 re…

Yes independence is absolutely an assumption that I (implicitly) made. It's essential for the convolution identity to hold as well, I just carried through that assumption.

We share interest in AWK (*) then :) I don't know OS at all. Did you imply I know lisp ? I enjoy scheme, but used it in anger never. Big fan of the little schemer series of books.

(*) Have to find that Weinberger face Google-NY t-shirt. Little treasures.

Regarding your dimensions comment, this is well understood for a single layer, that is, for logistic regression. Lehmann's book will have the necessary material. With multiple layers it gets complicated real fast.

The best performance estimates, as in, within realms of being practically useful, largely come from two approaches, one from PAC-Bayesian bounds, the other from Statistical Physics (but these bounds are data distribution dependent). The intrinsic dimension of the data plays a fundamental role there.

The recommended place to dig around is JMLR (journal of machine learning research).

Re: Convolutions, Polynomials and Flipped Kernels

#32

Post by srean » Wed, May 21, 2025, 3:43 PM UTC

silloncito wrote: post #30

incognito124 wrote: post #26

Earlier quoted context omitted.

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…

A load-balancer transparently sitting in front of the api end-point (not an uncommon scenario) usually decouples things well enough to be practically independent.

That said, silloncito's warning does need to be paid heed.

While independence is essential for the proof to go through, the relationships need not break catastrophically with break of independence, usually it is graceful degradation with degree of independence. There are however specific, often degenerate, theoretical edge cases where the degradation is rapid.

Re: Convolutions, Polynomials and Flipped Kernels

#33

Post by pizza » Wed, May 21, 2025, 3:51 PM UTC

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 ?

Check out tropical algebras

Re: Convolutions, Polynomials and Flipped Kernels

#34

Post by deepsun » Wed, May 21, 2025, 4:22 PM UTC

srean wrote: post #6

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.

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.…

Almost every probability theorem starts with "let's take independent random variables". But in reality almost nothing is independent. Superdeterminism even claims that exactly nothing is independent.

Re: Convolutions, Polynomials and Flipped Kernels

#35

Post by esafak » Wed, May 21, 2025, 4:28 PM UTC

stared wrote: post #13

Beware - one step more and you get into the region of generating functions. I recommend a book Herbert Wilf with a wonderful name of Generatingfunctionology ( https://www2.math.upenn.edu/~wilf/gfology2.pdf ).

I tip my hat to the person who invented that.

Re: Convolutions, Polynomials and Flipped Kernels

#36

Post by esafak » Wed, May 21, 2025, 4:30 PM UTC

bjt12345 wrote: post #3

This and complex analysis are fascinating topics in Undergraduate studies.

Contour integrals still feel cool.

Re: Convolutions, Polynomials and Flipped Kernels

#37

Post by silloncito » Wed, May 21, 2025, 4:37 PM UTC

srean wrote: post #31

silloncito wrote: post #28

Earlier quoted context omitted.

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 re…

Yes independence is absolutely an assumption that I (implicitly) made. It's essential for the convolution identity to hold as well, I just carried through that assumption. We share interest in AWK (*) then :) I don't know OS at all. Did you imply I know lisp ? I enjoy scheme, but used it in anger never. Big fan of the little schemer series of books. (*) Have to find that Weinberger face Google-NY t-shirt. Little trea…

Perhaps your txr submission suggests a lisp flavor. The intrinsic dimension concept looks interesting, also the V.C. dimension, but both concepts are very general. Perhaps Lehmann's book is: Elements of large sample theory.

Re: Convolutions, Polynomials and Flipped Kernels

#38

Post by srean » Wed, May 21, 2025, 4:51 PM UTC

deepsun wrote: post #34

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.…

Almost every probability theorem starts with "let's take independent random variables". But in reality almost nothing is independent. Superdeterminism even claims that exactly nothing is independent.

You are right.

The degree of dependence matters though. Mutual information is one way to measure that.

Thankfully, some theorems remain valid even when independence is violated. The next stop after independence is martingale criteria. Martingale difference sequences can be quite strongly dependent yet allow some of the usual theorems to go through but with worse convergence rates.

Re: Convolutions, Polynomials and Flipped Kernels

#39

Post by nayuki » Wed, May 21, 2025, 4:56 PM UTC

You can also multiply polynomials by way of analogy with integer multiplication:

         3  1  2  1
       ×    2  0  6
       ------------
        18  6 12  6
      0  0  0  0
   6  2  4  2
  -----------------
   6  2 22  8 12  6

= 6x^5 + 2x^4 + 22x^3 + 8x^2 + 12x^1 + 6x^0.

Re: Convolutions, Polynomials and Flipped Kernels

#40

Post by srean » Wed, May 21, 2025, 4:56 PM UTC

silloncito wrote: post #37

srean wrote: post #31

Earlier quoted context omitted.

Yes independence is absolutely an assumption that I (implicitly) made. It's essential for the convolution identity to hold as well, I just carried through that assumption. We share interest in AWK (*) then :) I don't know OS at all. Did you imply I know lisp ? I enjoy scheme, but used it in anger never. Big fan of the little schemer series of books. (*) Have to find that Weinberger face Google-NY t-shirt. Little trea…

Perhaps your txr submission suggests a lisp flavor. The intrinsic dimension concept looks interesting, also the V.C. dimension, but both concepts are very general. Perhaps Lehmann's book is: Elements of large sample theory.

Txr is super interesting.

I meant Lehmann's Theory of Point Estimation, but large sample theory is a good book too. The newer editions of TPE are a tad hefty in number of pages. The earlier versions would serve you fine.

The generic idea is that smaller these dimensions, easier the prediction problem. Intrinsic dimension is one that comes closest to topology. VC is very combinatorial and gives the worst of worst case bounds. For a typical sized dataset one ends up with an error probability estimate of less than 420. With PAC-Bayes the bounds are atleast less than 1.0.