xv01

https://en.wikipedia.org/wiki/Lagrange_polynomial

Uses of Lagrange polynomials include the Newton–Cotes method of numerical integration, Shamir's secret sharing scheme in cryptography, and Reed–Solomon error correction in coding theory.

https://en.oi-wiki.org/math/poly/lagrange/

• A perspective from linear algebra

Solving an interpolation problem leads to a problem in linear algebra amounting to inversion of a matrix. Using a standard monomial basis for our interpolation polynomial $L(x)=\sum _{j=0}^{k}x^{j}m_{j}$, we must invert the Vandermonde matrix $(x_{i})^{j}$ to solve $L(x_{i})=y_{i}$ for the coefficients $m_{j}$ of $L(x)$. By choosing a better basis, the Lagrange basis, $L(x)=\sum _{j=0}^{k}l_{j}(x)y_{j}$, we merely get the identity matrix, $\delta _{ij}$, which is its own inverse: the Lagrange basis automatically inverts the analog of the Vandermonde matrix.

This construction is analogous to the Chinese remainder theorem. Instead of checking for remainders of integers modulo prime numbers, we are checking for remainders of polynomials when divided by linears.

Furthermore, when the order is large, Fast Fourier transformation can be used to solve for the coefficients of the interpolated polynomial.

https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm

PS:

// > 比如 2023 年 ICLR 一篇文章提到了 Transformer 架构有能力实现几种不同的线性回归算法 , 这个正向结果再次表明其通用性

What learning algorithm is in-context learning? Investigations with linear models https://openreview.net/forum?id=0g0X4H8yN4I

https://x.com/xleaps/status/1627873094814531584

& https://twitter.com/xleaps/status/1627844991824297984

// > 网络开箱范例 : 训练用 神经网络 计算同余加法 a+b = ? (mod c) 时 , 网络 在某个时间突然获得了 100% 准确率 用 傅立叶变换 来计算 同余加法 这个算法可以被证明正确 & 反人类直觉 ( ? )

Progress measures for grokking via mechanistic interpretability https://openreview.net/forum?id=9XFSbDPmdW

// 在这个例子里 , 约 1400 步的训练使网络从简单的记住训练数据转移到傅立叶变换 , 约 9000 步的训练使得傅立叶变换完美实现了同余加法 , 而剩余的几千步使网络清理了之前的记忆 , 把权重全部转移实现了傅立叶变换算法这个子网络上

// LLM 可以看成是 我们 无力掌控 涌现 而采取的 heuristics