Systems and methods for selective expansive recursive tensor analysis

Patent metadata

Field	Value
Publication number	US-10824693-B2
Application number	US-201615375620-A
Country	US
Kind code	B2
Filing date	Dec 12, 2016
Priority date	Dec 10, 2015
Publication date	Nov 3, 2020
Grant date	Nov 3, 2020

Abstract

A system for performing tensor decomposition in a selective expansive and/or recursive manner, a tensor is decomposed into a specified number of components, and one or more tensor components are selected for further decomposition. For each selected component, the significant elements thereof are identified, and using the indices of the significant elements a sub-tensor is formed. In a subsequent iteration, each sub-tensor is decomposed into a respective specified number of components. Additional sub-tensors corresponding to the components generated in the subsequent iteration are formed, and these additional sub-tensors may be decomposed further in yet another iteration, until no additional components are selected. The mode of a sub-tensor can be decreased or increased prior to decomposition thereof. Components likely to reveal information about the data stored in the tensor can be selected for decomposition.

First claim

What is claimed is:

1. A method for facilitating extraction of information from tensors, the method comprising:
for a first tensor having N modes, wherein each element of the first tensor corresponds to a respective tuple of N indices;
performing a first iteration by a processor, the first iteration comprising:
(a) decomposing the first tensor having N modes into a selected number (R) of tensor components, each tensor component comprising N vectors; and
(b) forming a second tensor according to significant elements of a component, a significant element being an element that satisfies a specified criterion, wherein forming the second tensor comprises:
in each of the N modes:
counting a total number of significant elements of the component, a count for mode (k) being designated (S k );
identifying respective one or more indices of one or more significant elements of the component

allocating processor-accessible memory for the second tensor, of size proportional to a product of counts of the one or more significant elements of the component across all modes, denoted (π k32 1 N S k );
selecting elements of the first tensor corresponding to the identified one or more indices; and
storing the selected elements in the allocated processor-accessible memory.

2. The method of claim 1 , wherein decomposing the first tensor into R tensor components comprises:
decomposing the first tensor into N factor matrices; and
generating a tensor component by selecting a column r from each of the N factor matrices.

3. The method of claim 2 , wherein:
decomposing the first tensor comprises performing CANDECOMP/PARAFAC (CP) decomposition; and
each factor matrix has: (i) I n rows, I n being a size of the first tensor in an n-th mode, and (ii) a number of columns equal to the selected number of components R.

4. The method of claim 2 , wherein:
decomposing the first tensor comprises performing Tucker decomposition;
the selected number of components R comprises a product of N component-size values; and
each factor matrix has: (i) I n rows, I n being a size of the first tensor in an n-th mode, and (ii) a number of columns equal to a respective one of the N component-size values.

5. The method of claim 1 , wherein a p-th element of a q-th vector corresponds to a tensor element of the first tensor having an index p in the q-th mode of the first tensor.

6. The method of claim 1 , further comprising selecting one or more significant elements from at least one of the N vectors.

7. The method of claim 1 , wherein forming the second tensor comprises:
for each significant element of the component, identifying a corresponding tensor element of the first tensor.

8. The method of claim 1 , wherein:
a single data structure is allocated to both the first and the second tensors; and
forming the second tensor comprises managing the data structure according to indices of the second tensor.

9. The method of claim 1 , wherein forming the second tensor comprises allocating a data structure to the second tensor that is different from a data structure allocated to the first tensor.

10. The method of claim 1 , further comprising:
estimating an optimal decomposition rank for the first tensor; and
selecting the number of components R that is less than the estimated optimal decomposition rank.

11. The method of claim 1 , wherein the component is selected from the R components according to a component weight generated during the decomposition.

12. The method of claim 1 , wherein:
decomposing the first tensor comprises performing Tucker decomposition; and
the component is selected from the R components according to a value of an element of a core tensor G generated during the Tucker decomposition.

13. The method of claim 1 , wherein the specified criterion comprises at least one of:
membership in a set of a specified number of largest elements of the component;
membership in a set of a specified number of largest elements of elements of a vector of the component; and
an element having a value at least equal to a specified threshold.

14. The method of claim 1 , further comprising decreasing a number of modes of the second tensor to a value less than N by:
selecting a mode of the second tensor; and
collapsing tensor elements of the second tensor that correspond to the selected mode into a single combined tensor element of the second tensor.

15. The method of claim 1 , further comprising:
redesignating the second tensor as the first tensor; and
performing a second iteration, comprising repeating steps (a) and (b), with respect to the redesignated first tensor.

16. The method of claim 15 , wherein the selected number of components R in the second iteration is different from the selected number of components R in the first iteration.

17. The method of claim 15 , wherein the number of modes N of the first tensor in the second iteration is different from the number of modes N of the first tensor in the first iteration.

18. The method of claim 1 , further comprising:
generating the first tensor from an original tensor having M modes, wherein M>N, generating the first tensor comprising:
selecting a mode of the original tensor; and
collapsing tensor elements of the original tensor that correspond to the selected mode of the original tensor into a single combined tensor element of the first tensor.

19. The method of claim 18 , wherein:
the step of forming the second tensor comprises increasing a number of modes of the second tensor up to a value M, by:
selecting a combined tensor element of the first tensor that corresponds to a significant element; and
identifying each tensor element of the original tensor that correspond to the combined tensor element.

20. The method of claim 1 , further comprising decomposing the second tensor.

21. A system for facilitating extraction of information from tensors, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, the memory module being accessible to the processing unit, program the processing unit to performing a first iteration, wherein to perform the first iteration the instructions program the processing unit to:
for a first tensor having N modes, wherein each element of the first tensor corresponds to a respective tuple of N indices;
(a) decompose the first tensor stored in the memory module and having N modes into a selected number (R) of tensor components, each tensor component comprising N vectors; and
(b) form a second tensor in the memory module according to significant elements of a component, a significant element being an element that satisfies a specified criterion, wherein to form the second tensor, the instructions program the processing unit to:
in each of the N modes:
count a total number of significant elements of the component, a count for mode (k) being designated (S k );
identify respective one or more indices of one or more significant elements of the component
allocate in the memory module, memory, for the second tensor, of size proportional to a product of counts of the one or more significant elements of the component across all modes, denoted (π k=1 N S k );

select elements of the firs

Assignees

• Reservoir Labs Inc

Inventors

• Baskaran Muthu M
• Bruns-Smith David
• Ezick James
• Lethin Richard A

Classifications

• G06F17/16 Primary

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