Acceleration of multidimensional scaling by vector extrapolation techniques

Patent metadata

Field	Value
Publication number	US-10467325-B2
Application number	US-201314093671-A
Country	US
Kind code	B2
Filing date	Dec 2, 2013
Priority date	Jun 11, 2007
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

Abstract

A method for multidimensional scaling (MDS) of a data set comprising a plurality of data elements is provided, wherein each data element is identified by its coordinates, the method comprising the steps of: (i) applying an iterative optimization technique, such as SMACOF, a predetermined amount of times on a coordinates vector, said coordinates vector representing the coordinates of a plurality of said data elements, and obtaining a modified coordinates vector; (ii) applying a vector extrapolation technique, such as Minimal Polynomial Extrapolation (MPE) or reduced Rank Extrapolation (RRE) on said modified coordinates vector obtaining a further modified coordinates vector; and (iii) repeating steps (i) and (ii) until one or more predefined conditions are met.

First claim

The invention claimed is:

1. One or more non-transitory computer readable storage media using instructions stored thereon, which, when executed, cause a machine to perform a method, the method comprising:
(i) applying an iterative optimization technique a predetermined amount of times in a machine learning algorithm on a coordinates vector, said coordinates vector representing the coordinates of a plurality of data elements of a data set, each data element identified by its coordinate and obtaining a modified coordinates vector;
(ii) applying a vector extrapolation technique on said modified coordinates vector obtaining a further modified coordinates vector; and
(iii) repeating steps (i) and (ii) until one or more predefined condition are met to improve convergence of the machine learning algorithm and to reduce its computational cost and storage requirement.

2. The media according to claim 1 , wherein said iterative optimization technique is carried on in more than one successive scale.

3. The media according to claim 1 , wherein said iterative optimization technique is scaling by majoring a complicated function (SMACOF).

4. The media according to claim 1 , wherein a cost function optimized for by the iterative optimization technique includes a stress cost function as a component, with or without the addition of other terms.

5. The media according to claim 1 , wherein said vector extrapolation technique is Minimal Polynomial Extrapolation or Reduced Rank Extrapolation.

6. The media according to claim 1 , wherein said iterative optimization technique comprises:
(i) Gradient Descent algorithm with or without line search;
(ii) Conjugate Gradients algorithm with or without line search;
(iii) Quasi Newton algorithm with or without line search;
(iv) Newton algorithm with or without line search; or
(v) Levenberg-Marquardt algorithm with or without line search.

7. The media according to claim 1 , wherein a cost function associated with the iterative optimization technique comprises:
(i) a least squares cost function;
(ii) a SSTRESS cost function;
(iii) a STRAIN cost function;
(iv) a p-norm on distortion of distances;
(v) any non-metric MDS cost function; or
(vi) any cost functional including a distance distortion term.

8. The media according to claim 1 , wherein said data set is reduced to two or three dimensions.

9. A method comprising:
(i) applying an iterative optimization technique a predetermine amount of times in a machine learning algorithm on a coordinates vector, said coordinates vector representing the coordinates of a plurality of data elements of a data set, each data element identified by its coordinates and obtaining a modified coordinates vector;
(ii) applying a vector extrapolation technique on said modified coordinates vector obtaining a further modified coordinates vector; and
(iii) repeating steps (i) and (ii) until one or more predefined condition& are met to improve convergence of the machine learning algorithm and to reduce its computational cost and storage requirement.

10. The method according to claim 9 , wherein said iterative optimization technique is carried on in more than one successive scale.

11. The method according to claim 9 , wherein said iterative optimization technique is scaling by jaorizing a complicated function (SMACOF).

12. The method according to claim 9 , wherein a cost function optimized for by the iterative optimization technique includes a stress cost function as a component, with or without the addition of other terms.

13. The method according to claim 9 , wherein said vector extrapolation technique is Minimal Polynomial Extrapolation or Reduced Rank Extrapolation.

14. The method according to claim 9 , wherein said iterative optimization technique comprises:
(i) Gradient Descent algorithm with or without line search;
(ii) Conjugate Gradients algorithm with or without line search;
(iii) Quasi Newton algorithm with or without line search;
(iv) Newton algorithm with or without line search; or
(v) Levenberg-Marquardt algorithm with or without line search.

15. The method according to claim 9 , wherein the cost function associated with the iterative optimization technique comprises:
(i) the least squares cost function;
(ii) the SSTRESS cost function;
(iii) the STRAIN cost function;
(iv) a p-norm on the distortion of distances;
(v) any non-metric MDS cost function; or
(vi) any cost functional including a distance distortion term.

16. The method according to claim 9 , wherein said data set is reduced to two or three dimensions.

17. An apparatus comprising:
one or more processors to:
(i) apply an iterative optimization technique a predetermined amount of times in a machine learning algorithm on a coordinates vector, said coordinates vector representing the coordinates of a plurality of data elements of a data set, each data element identified by its coordinates and obtaining a modified coordinates vector;
(ii) apply a vector extrapolation technique on said modified coordinates vector obtaining a further modified coordinates vector;
(iii) repeat steps (i) and (ii) until one or more predefined conditions are met to improve convergence of the machine learning algorithm and to reduce its computational cost and storage requirement;

and
a memory coupled to said processor.

18. The apparatus according to claim 17 , wherein said iterative optimization technique is carried on in more than one successive scale.

19. The apparatus according to claim 17 , wherein said iterative optimization technique is scaling by majoring a complicated function (SMACOF).

20. The apparatus according to claim 17 , wherein a cost function optimized for by the iterative optimization technique includes a stress cost function as a component, with or without the addition of other terms.

21. The apparatus according to claim 17 , wherein said vector extrapolation technique is Minimal Polynomial Extrapolation or Reduced Rank Extrapolation.

22. The apparatus according to claim 17 , wherein said iterative optimization technique comprises:
(i) Gradient Descent algorithm with or without line search;
(ii) Conjugate Gradients algorithm with or without line search;
(iii) Quasi Newton algorithm with or without line search;
(iv) Newton algorithm with or without line search; or
(v) Levenberg-Marquardt algorithm with or without line search.

23. The apparatus according to claim 17 , wherein the cost function associated with the iterative optimization technique comprises:
(i) the least squares cost function;
(ii) the SSTRESS cost function;
(iii) the STRAIN cost function;
(iv) a p-norm on the distortion of distances;
(v) any non-metric MDS cost function; or
(vi) any cost functional including a distance distortion term.

24. The apparatus according to claim 17 , wherein said data set is reduced to two or three dimensions.

Assignees

• Technion Res & Development Found Ltd
• Intel Corp

Inventors

• Rosman Guy
• Bronstein Alexander
• Bronstein Michael
• Kimmel Ron

Classifications

• G06F17/17 Primary

  Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18) · CPC title

• G06F18/2137 Primary

  based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps · CPC title

• G06K9/6251

  Physics · mapped topic