Source identification by non-negative matrix factorization combined with semi-supervised clustering

Patent metadata

Field	Value
Publication number	US-11748657-B2
Application number	US-202017020504-A
Country	US
Kind code	B2
Filing date	Sep 14, 2020
Priority date	Aug 30, 2016
Publication date	Sep 5, 2023
Grant date	Sep 5, 2023

Abstract

Machine-learning methods and apparatus are provided to solve blind source separation problems with an unknown number of sources and having a signal propagation model with features such as wave-like propagation, medium-dependent velocity, attenuation, diffusion, and/or advection, between sources and sensors. In exemplary embodiments, multiple trials of non-negative matrix factorization are performed for a fixed number of sources, with selection criteria applied to determine successful trials. A semi-supervised clustering procedure is applied to trial results, and the clustering results are evaluated for robustness using measures for reconstruction quality and cluster separation. The number of sources is determined by comparing these measures for different trial numbers of sources. Source locations and parameters of the signal propagation model can also be determined. Disclosed methods are applicable to a wide range of spatial problems including chemical dispersal, pressure transients, and electromagnetic signals, and also to non-spatial problems such as cancer mutation.

First claim

We claim:

1. A method, comprising:
with a computer system:
performing a plurality of non-negative matrix factorization (NMF) trials on mixed signals generated by one or more unidentified sources and detected by a plurality of sensors, each of the NMF trials producing a predetermined number b of candidate sources referred to each of the sensors according to a signal propagation model;
for each of the NMF trials, ranking the corresponding b candidate sources according respective magnitudes of the corresponding b candidate sources; and
determining b basis sources for the mixed signals by:
for each index d from 1 to b, determining the d th basis source as an average, across the plurality of NMF trials, of the candidate sources having d th rank.

2. A method comprising:
performing the method of claim 1 for each of a sequence of values of the predetermined number b;
for each value of b:
calculating a first parameter representing reconstruction error of the b basis sources; and
calculating a second parameter representing separation of the b basis sources; and

determining a first number A of the unidentified sources for which a combination of the calculated first parameter and the calculated second parameter is optimized.

3. The method of claim 2 , further comprising:
identifying the unidentified sources as the b basis sources determined with b equal to A.

4. The method of claim 1 , further comprising:
responsive to determining the b basis sources, adjusting one or more conditions of a physical environment in which the sensors are located,
wherein the adjusting comprises at least one or more of the following acts, for at least a first one of the b basis sources and/or a first one of the sensors:
probing local conditions at or near a location of the first source,
counteracting the first source to reduce a signal strength of the first source, or
making changes in the physical environment that will reduce a contribution from the first source to the mixed signal detected by the first sensor, without changing the signal strength of the first source.

5. The method of claim 1 , wherein the mixed signals represent one or more of: atmospheric pollution, water pollution, pressure transients, acoustic signals, seismic disturbances, or electromagnetic interference.

6. The method of claim 1 , further comprising determining spatial locations for one or more of the b basis sources.

7. One or more computer-readable storage media storing computer-readable instructions that, when executed by the computer system, cause the computer system to perform the method of claim 1 .

8. The method of claim 1 , wherein the signal propagation model is a wave-like propagation model.

9. The method of claim 1 , wherein the propagation model incorporates diffusion and advection.

10. The method of claim 1 , wherein the average is a centroid.

11. The method of claim 1 , wherein the computer system is a distributed computer system.

12. The method of claim 11 , wherein the method is performed using more than one processor in the distributed computer system.

13. A computer-implemented system comprising:
one or more computing nodes each comprising one or more processors, memory coupled thereto, and one or more network adapters, the one or more computing nodes being interconnected by one or more network connections and configured to perform operations comprising:
performing a plurality of non-negative matrix factorization (NMF) trials on mixed signals generated by one or more unidentified sources and detected by a plurality of sensors, each of the NMF trials producing a predetermined number b of candidate sources referred to each of the sensors according to a signal propagation model;
for each of the NMF trials, ranking the corresponding b candidate sources according respective magnitudes of the corresponding b candidate sources; and
determining b basis sources for the mixed signals by:
for each index d from 1 to b, determining the d th basis source as an average, across the plurality of NMF trials, of the candidate sources having d th rank.

14. The computer-implemented system of claim 13 , wherein the operations are performed for each of a sequence of values of the predetermined number b, and wherein the operations further comprise:
for each value of b:
calculating a first parameter representing reconstruction error of the b basis sources; and
calculating a second parameter representing separation of the b basis sources; and

determining a first number A of the unidentified sources for which a combination of the calculated first parameter and the calculated second parameter is optimized.

15. The computer-implemented system of claim 14 , wherein the operations further comprise:
identifying the unidentified sources as the b basis sources determined with b equal to A.

16. The computer-implemented system of claim 13 , wherein the one or more computing nodes are a plurality of computing nodes distributed over a plurality of locations.

17. A method, comprising:
with a computer:
performing a plurality of non-negative matrix factorization (NMF) trials on mixed signals generated by one or more unidentified sources and detected by a plurality of sensors, each of the NMF trials producing a predetermined number of candidate sources referred to each of the sensors according to a signal propagation model;
identifying clusters of the candidate sources and determining basis sources, by performing clustering on the candidate sources;
evaluating results of the clustering by:
generating a first parameter representing reconstruction error of at least one of the basis sources, and
generating a second parameter representing separation of at least two of the identified clusters; and

determining a first number of the unidentified sources for which a combination of the calculated first parameter and the calculated second parameter is optimized.

18. The method of claim 17 , wherein the NMF trials are performed using one or more of:
sparse NMF, semi-supervised NMF, semi-nonnegative NMF, graph regularized NMF, NMF with missing values, online NMF, non-linear NMF, coupled NMF, or NMF incorporating singular value decomposition.

19. The method of claim 17 , wherein the mixed signals take binary values.

20. The method of claim 17 , further comprising determining, for at least one of the unidentified sources, one or more coordinates and respective uncertainty or uncertainties of the one or more coordinates.

21. The method of claim 17 , wherein the first number is a minimum number for which:
the reconstruction error is less than or equal to a predetermined accuracy threshold; and
the separation is greater than or equal to a predetermined separation threshold.

22. The method of claim 17 , wherein the mixed signals comprise one or more of:
radioactivity; or
microdiffraction patterns.

23. The method of claim 17 , wherein the mixed signals comprise microdiffraction patterns, and the method further comprises:
identifying one or more spurious sources by evaluating pair-wise cross-correlations among the basis sources; and
removing the one or more spurious sources from the basis sources.

24. The method of claim 12 , wherein the method is performed using a plurality of program modules stored in the distributed computer system.

25. The method of claim 24 , wherein at least a first one of the plurality of program modules is stored in a

Assignees

• Triad Nat Security Llc

Inventors

• Alexandrov Boian S
• Alexandrov Ludmil B
• Iliev Filip L
• Stanev Valentin G
• Vesselinov Velimir V

Classifications

• G06N20/00 Primary

  Machine learning · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F18/2115

  by evaluating different subsets according to an optimisation criterion, e.g. class separability, forward selection or backward elimination · CPC title

• G06F18/2133

  based on naturality criteria, e.g. with non-negative factorisation or negative correlation · CPC title

• G06F18/2135

  based on approximation criteria, e.g. principal component analysis · CPC title