google-deepmind / google-deepmind/alphageometry

Some mistake in AR system coding

Open
#114 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
4.9k
Forks
572
PR merge metrics
No merged PRs in 30d

Description

In ar.py line 354-361:

new_column = np.zeros([len(self.v2i), 2]) # N, 2
for v, c in vc:
new_column[self.v2i[v], 0] += float(c) # [1]
new_column[self.v2i[v], 1] -= float(c) # [2]

self.A = np.concatenate([self.A, new_column], 1) # add two columns
self.c += [1.0, -1.0] # coeeficients of linprog minimization objective
self.deps += [dep]

it seems that
self.c += [1.0, -1.0]
shall be replaced by
self.c += [1.0, 1.0]

Explaination:

The quoted code above is a part of the "Traceback for algebraic deduction", as mentioned in Nature volume 625, pages 476–482 (2024), i.e., the Google's AlphaGepmetry paper. Speaking more precisely, this "Traceback" is done by doing linear progression to minimize the function
$\Sigma_{i}(x_{i}+y_{i})$ (1)
with restriction $A\circ(x-y)=b$,
where $x_{i}$, $y_{i}$ are positive real numbers (storaged as float); $A$ is an $m \times n matrix$; $x$, $y$, $b$ are $n$-dimensional vectors. $m$ is the cardinality of the set of geometric variables used in linear deduction, $n$ is the cardinality of the set of rules (i.e., linear combination that sums to zero). (1) is apparently the Lasso regression. We may write this in a more understandable way:
minimize
$\Sigma_{i}|z_{i}|$ (2)
with restriction $A\circ z=b$.

In the code, [1] and [2] are adding the positive (i.e., vector x) and negative (i.e., vector y) version of a new rule; self.A is the matrix A, self.c is the goal of minimization. In the code the restriction is written rather as $A\circ x+ (-A)\circ y = b$, where "$A$" is part [1] and "$-A$" is part [2]. Therefore, the minimization shall be both "$1$" (i.e., "positive" minimization, do not require times $-1$) for [1] and [2].

The current code is minimizing
$\Sigma_{i}(x_{i}-y_{i})$ (3).
Which does not make sense since if one increase both x_{i} and y_{i}, the restriction will still be satisfied, and the minimization goal is also unaffected. To compare with (2), one may translate this to minimize:
$\Sigma_{i}z_{i}$ (4),
which is absurd.

\emph{Remark.}
$\circ$ represents matrix multiplication.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.