US2025335538A1PendingUtilityA1
Determining generalized eigenvectors using multi-agent interactions
Est. expiryMay 19, 2042(~15.8 yrs left)· nominal 20-yr term from priority
G06F 9/3885G06F 17/16
45
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
Methods, systems, and apparatus, including computer programs encoded on computer storage media, for determining generalized eigenvectors that characterize a data set.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1 . A method of determining a plurality of generalized eigenvectors v of a first matrix A and a second matrix B, wherein at least one of the first matrix A or the second matrix B characterize a data set, the method comprising:
obtaining initial estimates for the plurality of generalized eigenvectors v; and for each particular generalized eigenvector v i , generating a final estimate for the particular generalized eigenvector v i , comprising at each stage t of a plurality of stages:
performing a plurality of iterations m in parallel, wherein performing each of the plurality of iterations m comprises performing operations comprising:
obtaining a random sample of the data set;
generating, from the random sample of the data set, an estimate A tm of the first matrix A and an estimate B tm of the second matrix B;
generating a reward estimate using (i) the estimate A tm of the first matrix A and the estimate B tm of the second matrix B and (ii) a current estimate {circumflex over (v)} i of the particular generalized eigenvector v i , wherein the reward estimate is larger if an estimated generalized eigenvalue {circumflex over (λ)} i corresponding to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i is larger;
generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate, wherein the punishment estimate is larger if the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i and a current estimate {circumflex over (v)} j of the parent generalized eigenvector v j are not orthogonal;
generating a combined punishment estimate by combining the respective punishment estimates for each parent generalized eigenvector v j of the particular generalized eigenvector v i ; and
generating an initial update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i according to a difference between the reward estimate and the combined punishment estimate;
generating, from the respective initial updates to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i generated at the plurality of iterations, a combined update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i ; and
updating the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i by applying the combined update.
2 . The method of claim 1 , wherein each of the plurality of iterations m are performed in parallel by a respective different device, a respective different thread of a device, or a respective different core of a multi-core processor.
3 . The method of claim 1 , wherein, at each stage t of the plurality of stages, the respective current estimates for each of the plurality of generalized eigenvectors v are updated in parallel.
4 . The method of claim 1 , wherein:
the data set comprises a plurality of first elements x and a plurality of second elements y, wherein each first element x corresponds to a particular second element y, and:
A
=
[
0
𝔼
[
xy
⊤
]
𝔼
[
yx
⊤
]
0
]
and
B
=
[
𝔼
[
xx
⊤
]
0
0
I
]
wherein ( z ) is an expected value of z.
5 . The method of claim 1 , wherein:
the data set comprises a plurality of first elements x and a plurality of second elements y, wherein each first element x corresponds to a particular second element y, and the plurality of generalized eigenvectors y represent a projection that, when applied to the first elements x to generate first projected elements x′ and to the second elements y to generate second projected elements y′, cause the first projected elements x′ and the second projected elements y′ to be maximally correlated.
6 . The method of claim 5 , wherein:
A
=
[
0
𝔼
[
xy
⊤
]
𝔼
[
yx
⊤
]
0
]
and
B
=
[
𝔼
[
xx
⊤
]
0
0
𝔼
[
yy
⊤
]
]
wherein ( z ) is an expected value of z.
7 . The method of claim 4 , further comprising:
using the final estimates for the plurality of generalized eigenvectors v to generate (i) respective first projected elements x′ from at least a subset of the first elements x and (ii) respective second projected elements y′ from at least a subset of the second elements y; training, using the generated first projected elements x′ and the generated second projected elements y′, a machine learning model to process first projected elements x′ and to generated predictions for corresponding second projected elements y′; obtaining a new first element x; using the final estimates for the plurality of generalized eigenvectors v to generate a new first projected element x′ from the new first element x; and processing the new first projected element x′ using the trained machine learning model to generate a prediction of a corresponding new second projected elements y′.
8 . The method of claim 5 , wherein a neural network is at least partially represented by the generalized eigenvectors v.
9 . The method of claim 8 , wherein:
the generalized eigenvectors v represent directions of maximal correlation between activations generated by respective neural network layers of the neural network; or the generalized eigenvectors v represent directions of maximal correlation between activations generated by (i) one or more neural network layers of the neural network and (ii) one or more second neural network layers generated by a second neural network.
10 . The method of claim 4 , wherein at least some of the first elements and/or at least some of the second elements represent medical data corresponding to respective subjects, the medical data comprising one or more of EEG data, MRI data and/or other medical imaging data, or genomic data.
11 . The method of claim 1 , wherein the plurality of generalized eigenvectors v represent respective directions in the data set that exhibit minimal Gaussianity.
12 . The method of claim 11 , wherein the data set comprises a plurality of elements x, and:
A
=
𝔼
[
〈
x
,
x
〉
xx
⊤
]
-
tr
(
B
)
B
-
2
B
2
and
B
=
𝔼
[
xx
⊤
]
wherein ( z ) is an expected value of z and tr(Z) is a trace of matrix Z.
13 . The method of claim 11 , further comprising:
for each of a plurality of elements x in the data set:
using the final estimates for the plurality of generalized eigenvectors v to generate an updated element x′; and
storing the updated element x′ and/or providing the updated element x′ for further processing,
wherein the updated element x′ is a de-noised version of the element x.
14 . The method of any one of claims 11-13 , wherein at least some of the plurality of elements represent one or more of: speech data, network signal data, image data, or sensor data.
15 . The method of claim 1 , wherein:
for each class c of a plurality of classes, the data set comprises one or more respective elements x c belonging to the class c, and the plurality of generalized eigenvectors y represent a projection that, when applied to the elements of the data set to generate respective projected elements, cause the projected elements belonging to respective different classes to be maximally separated.
16 . The method of claim 15 , wherein:
A
=
∑
c
(
μ
c
-
μ
)
(
μ
c
-
μ
)
⊤
and
B
=
∑
c
𝔼
[
(
x
c
-
μ
c
)
(
x
c
-
μ
c
)
⊤
]
wherein ( z ) is an expected value of z, μ c is a mean of the elements x c belonging to the class c, and μ is a mean of the data set across classes.
17 . The method of claim 1 , wherein the reward estimate is equal to or proportional to:
(
v
ˆ
i
⊤
B
tm
v
ˆ
i
)
A
tm
v
ˆ
i
-
(
v
ˆ
i
⊤
A
tm
v
ˆ
i
)
B
tm
v
ˆ
i
.
18 . The method of claim 1 , wherein generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate comprises:
generating a normalized estimate ŷ j for the parent generalized eigenvector v j by normalizing the current estimate {circumflex over (v)} j of the parent generalized eigenvector v using the estimate B tm of the second matrix B; and generating the punishment estimate using the normalized estimate ŷ j .
19 . The method of claim 18 , further comprising, for each particular generalized eigenvector v i and at each stage t of the plurality of stages:
maintaining data representing an estimated product [B{circumflex over (v)}] i between the second matrix B and the generalized eigenvector v i .
20 . The method of claim 19 , wherein maintaining data representing the estimated product [B{circumflex over (v)}] i comprises:
at each of the plurality of iterations m, generating an initial update
∇
im
Bv
to the estimated product [B{circumflex over (v)}] i ;
generating, from the respective initial updates
∇
im
Bv
to the estimated product [B{circumflex over (v)}] i , a combined update
∇
i
Bv
to the estimated product [B{circumflex over (v)}] i ; and
updating the estimated product [B{circumflex over (v)}] i by applying the combined update
∇
i
Bv
.
21 . The method of claim 20 , wherein, at each of the plurality of iterations m, generating the initial update
∇
im
Bv
to the estimated product [B{circumflex over (v)}] i comprises computing:
∇
im
Bv
=
(
B
tm
v
ˆ
i
-
[
B
v
ˆ
]
i
)
22 . The method of claim 20 , wherein:
generating the combined update ∇ i Bv comprises computing:
∇
i
Bv
←
1
M
∑
m
[
∇
im
Bv
]
wherein M is a number of iterations m; and
updating the estimated product [B{circumflex over (v)}] i by applying the combined update
∇
i
Bv
comprises computing:
[
B
v
ˆ
]
i
←
[
B
v
ˆ
]
i
+
γ
t
∇
i
Bv
wherein γ t is a hyperparameter representing a step size for the estimated product [B{circumflex over (v)}] i corresponding to the current stage t.
23 . The method of claim 19 , wherein generating a normalized estimate ŷ j for the parent generalized eigenvector v j comprises computing:
y
ˆ
j
=
v
ˆ
j
max
(
〈
v
ˆ
j
,
[
B
v
ˆ
]
j
〉
,
ρ
)
wherein ρ is equal to or an estimate of a minimum singular value corresponding to the second matrix B.
24 . The method of claim 19 , wherein generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate further comprises:
generating an estimated product [Bŷ] j between the second matrix B and the normalized estimate ŷ j ; and generating the punishment estimate using the estimated product [Bŷ] j .
25 . The method of claim 24 , wherein generating the estimated product [Bŷ] j between the second matrix B and the normalized estimate ŷ j comprising computing:
[
B
y
ˆ
]
j
=
[
B
v
ˆ
]
j
⌊
〈
v
ˆ
j
,
[
B
v
ˆ
]
j
〉
⌋
ρ
wherein ρ is equal to or an estimate of a minimum singular value corresponding to the second matrix B.
26 . The method of claim 24 , wherein generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate further comprises computing:
(
v
ˆ
i
T
A
tm
y
ˆ
j
)
[
〈
v
ˆ
i
,
B
tm
v
ˆ
i
〉
[
B
y
ˆ
]
j
-
〈
v
ˆ
i
,
[
B
y
ˆ
]
j
〉
B
tm
v
ˆ
i
]
.
27 . The method of claim 1 , wherein the estimated generalized eigenvalue {circumflex over (λ)} i is equal to:
λ
^
i
=
〈
v
ˆ
i
,
A
v
ˆ
i
〉
〈
v
ˆ
i
,
B
v
ˆ
i
〉
.
28 . The method of claim 1 , wherein, in expectation, the initial update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i encourages maximization of a utility u i that is equal to or proportional to:
u
i
(
v
ˆ
i
|
v
ˆ
j
<
i
)
=
λ
ˆ
i
-
∑
j
<
i
λ
ˆ
j
〈
y
ˆ
i
,
B
y
ˆ
j
〉
2
y
ˆ
i
=
v
ˆ
i
〈
v
ˆ
i
,
B
v
ˆ
i
〉
wherein {circumflex over (v)} j<i represents the respective current estimate {circumflex over (v)} j of each parent generalized eigenvector v j of the particular generalized eigenvector v i , and Σ j<i [⋅] indicates a sum over each parent generalized eigenvector v j of the particular generalized eigenvector v i .
29 . The method of claim 1 , wherein, for each particular generalized eigenvector v i :
computations for generating the final estimate for the particular generalized eigenvector v i are assigned to a respective different set of one or more devices of a plurality of devices; and the current estimate {circumflex over (v)} i of the particular principal generalized eigenvector v i is broadcast to each other device of the plurality of devices at regular intervals.
30 . The method of claim 1 , wherein, for each particular generalized eigenvector v i :
generating a combined punishment estimate for the particular generalized eigenvector v i comprises determining a sum of the respective punishment estimates of each parent generalized eigenvector v j .
31 . The method of claim 1 , wherein:
generating, from the respective initial updates Δ im to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i generated at the plurality of iterations m, a combined update Δ i to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i comprises computing:
Δ
i
←
1
M
∑
m
[
Δ
im
]
wherein M is a number of iterations m; and
updating the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i by applying the combined update Δ i comprises computing:
v
ˆ
i
′
←
v
ˆ
i
+
η
t
Δ
i
wherein η t is a hyperparameter representing a step size for the current estimate {circumflex over (v)} i .
32 . The method of claim 31 , wherein updating the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i further comprises computing:
v
ˆ
i
←
v
ˆ
i
′
v
ˆ
i
′
.
33 . A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform the operations for determining a plurality of generalized eigenvectors y of a first matrix A and a second matrix B, wherein at least one of the first matrix A or the second matrix B characterize a data set, the operations comprising:
obtaining initial estimates for the plurality of generalized eigenvectors v; and for each particular generalized eigenvector v i , generating a final estimate for the particular generalized eigenvector v i , comprising at each stage t of a plurality of stages:
performing a plurality of iterations m in parallel, wherein performing each of the plurality of iterations m comprises performing operations comprising:
obtaining a random sample of the data set;
generating, from the random sample of the data set, an estimate A tm of the first matrix A and an estimate B tm of the second matrix B;
generating a reward estimate using (i) the estimate A tm of the first matrix A and the estimate B tm of the second matrix B and (ii) a current estimate {circumflex over (v)} i of the particular generalized eigenvector v i , wherein the reward estimate is larger if an estimated generalized eigenvalue {circumflex over (λ)} i corresponding to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i is larger;
generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate, wherein the punishment estimate is larger if the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i and a current estimate {circumflex over (v)} j of the parent generalized eigenvector v j are not orthogonal;
generating a combined punishment estimate by combining the respective punishment estimates for each parent generalized eigenvector v j of the particular generalized eigenvector v i ; and
generating an initial update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i according to a difference between the reward estimate and the combined punishment estimate;
generating, from the respective initial updates to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i generated at the plurality of iterations, a combined update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i ; and
updating the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i by applying the combined update.
34 . One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for determining a plurality of generalized eigenvectors y of a first matrix A and a second matrix B, wherein at least one of the first matrix A or the second matrix B characterize a data set, the operations comprising:
obtaining initial estimates for the plurality of generalized eigenvectors v; and for each particular generalized eigenvector v i , generating a final estimate for the particular generalized eigenvector v i , comprising at each stage t of a plurality of stages:
performing a plurality of iterations m in parallel, wherein performing each of the plurality of iterations m comprises performing operations comprising:
obtaining a random sample of the data set;
generating, from the random sample of the data set, an estimate A tm of the first matrix A and an estimate B tm of the second matrix B;
generating a reward estimate using (i) the estimate A tm of the first matrix A and the estimate B tm of the second matrix B and (ii) a current estimate {circumflex over (v)} i of the particular generalized eigenvector v i , wherein the reward estimate is larger if an estimated generalized eigenvalue {circumflex over (λ)} i corresponding to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i is larger;
generating, for each parent generalized eigenvector v j of the particular generalized eigenvector v i , a respective punishment estimate, wherein the punishment estimate is larger if the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i and a current estimate {circumflex over (v)} j of the parent generalized eigenvector v j are not orthogonal;
generating a combined punishment estimate by combining the respective punishment estimates for each parent generalized eigenvector v j of the particular generalized eigenvector v i ; and
generating an initial update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i according to a difference between the reward estimate and the combined punishment estimate;
generating, from the respective initial updates to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i generated at the plurality of iterations, a combined update to the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i ; and
updating the current estimate {circumflex over (v)} i of the particular generalized eigenvector v i by applying the combined update.Join the waitlist — get patent alerts
Track US2025335538A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.