Анализ страницы https://f-charton.github.io/polynomial-roots/

Computing the roots of polynomials – François Charton – Scientific discovery, maths and physics, with transformers

TLDR: Transformers can be trained to predict the roots of polynomials from their coefficients: It has been observed that neural networks struggle with basic arithmetic. For instance, transformers perform poorly when trying to multiply two large numbers (represented as sequences of digits in some number base). This has long been considered a “hard” limitation of language models and, for some authors, a proof that hybrid systems, mixing rule-based and gradient-based techniques, are needed. In a paper published last year, I showed that transformers can learn to perform approximate computations from examples only. They can learn various problems of linear algebra, from basic (arithmetic) operations on matrices to advanced (non linear) computations, like eigen decomposition and inversion. This post features another numerical problem: finding the roots of polynomials. I am using the same architectures and encoding as in my paper on linear algebra. A summary of results, and discussion, can be found at the end of this post. The maths A polynomial of degree $n$ with real coefficients is a function of the form : $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$, with all $a_i$ in $\mathbb{R}$. A degree $n$ polynomial $P$ has $n$ roots : values $x_i$ such that $P(x_i) = 0$, that allow to factorize $P$ as $P(x) = a_n (x-x_1)(x-x_2)\dots(x-x_n)$. The roots can be multiple, i.e. we can have $x_i=x_j$ for different values of $i$ and $j$. When all the coefficients $a_i$ are real, the roots are either real numbers, or pairs of conjugate complex numbers, ($a+ib$, $a-ib$), with $a$, $b$ $\in$ $\mathbb R$. We want to predict the roots of a polynomial from its coefficients (i.e. the $x_i$ from the $a_i$). For $n\leq 4$, there exists formulas $x_i=f(a_1,a_2,…a_n)$. For instance, the roots of a degree 2 polynomial $P(x) = ax^2+bx+c$ can be computed as $x_0=\frac{ -b + \sqrt{b^2-4ac}}{2a}$ and $x_1=\frac{-b-\sqrt{b^2-4ac}}{2a}$ if $b^2-4ac>=0$, and $\frac{-b+i\sqrt{4ac-b^2}}{2a}$ and $\frac{-b-i\sqrt{4ac-b^2}}{2a}$ if $b^2-4ac<0$. However, it was proven (by Galois and Abel), that no such general formula, involving common operations and radicals, can exist for $n > 4$. But there are numerical algorithms to compute approximate values of the roots. Most existing algorithms (Newton, Halley, Laguerre) compute one root $x_i$ at a time. The polynomial is then divided by the factor $(x-x_i)$, and the process is repeated. Techniques exist (e.g. Aberth) to compute all roots in one step. Here, I train transformers to predict all roots. Encoding the problem Transformers process sequences, and the first step in using them is to rewrite the problem and solution as sequences of tokens. Here, the input is a $n$ degree polynomial, encoded as a sequence of $n+2$ numbers: the (integer) degree and the $n+1$ real coefficients. The degree is represented as a symbolic tokens (from ‘N1’ to ‘N100’). Real coefficients are rounded to three significant digits, written in scientific notation, and encoded as sequences of three tokens: sign (‘+’ or ‘-‘), mantissa (from ‘0’ to ‘999’), and exponent (from ‘E-100’ to ‘E100’). This is the P10 encoding from my paper on linear algebra. For a polynomial of degree $n$, the input sequence has $3n+4$ tokens. The $n$ output roots are encoded as a sequence of $2n$ real numbers: the real and imaginary parts of the $n$ roots. They are encoded as before: a symbolic token defining the length of the sequence ($2n$), and the $2n$ real numbers, each represented by three tokens (sign, mantissa, exponent). For a polynomial of degree $n$, the output sequence has length $6n+1$. Overall, the vocabulary has about 1120 tokens. Here is some minimal Python code for encoding real numbers, and sequences of reals or complex numbers. def write_float(self, value): precision = self.float_precision # significant digts - 1 m, e = (f

Ошибок нет

width=device-width, initial-scale=1.0, maximum-scale=1.0

Кол-во: 2

Кол-во: 6