Regression using M-estimators and polynomial kernel support vector machines and principal component regression

Patent metadata

Field	Value
Publication number	US-9658987-B2
Application number	US-201414279177-A
Country	US
Kind code	B2
Filing date	May 15, 2014
Priority date	May 15, 2014
Publication date	May 23, 2017
Grant date	May 23, 2017

Abstract

Embodiments of the invention relate to sketching for M-estimators for performing regression. One embodiment includes providing one or more sets of input data. A matrix A and a vector b are generated using the input data. A processor device is used for processing the matrix A and the vector b based on a randomized sketching matrix S. A vector x that minimizes a normalized measure function is determined based on the matrix A and the vector b. A relationship between the input data is determined based on the vector x.

First claim

What is claimed is:

1. A method comprising:
obtaining one or more sets of input data;
performing, by a processor device, a sketching process including:
generating a matrix A and a vector b using the one or more sets of input data;
creating, by the processor device, a randomized sketching matrix S based on the matrix A; and
determining, by the processor device, a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

performing, by the processor device, a relationship process using the sketching process for determining a relationship between the one or more sets of input data based on the vector x.

2. The method of claim 1 , wherein determining the vector x comprises determining the min x ∥Ax−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

3. The method of claim 2 , further comprising:
estimating, by the processor device, ∥Ax∥ G , for all xε d based on the sketching matrix S.

4. The method of claim 3 , wherein the relationship process further comprises using the sketching matrix S for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, the processor device performs one pass over the matrix A for determining a regression solution with a residual error within a constant factor of a specified tolerance and with constant probability, and nnz comprises a number of non-zero entries of the matrix A.

5. The method of claim 1 , further comprising:
embedding, by the processor device, a space induced by a nonlinear polynomial kernel for the matrix A using an oblivious subspace embedding (OSE).

6. The method of claim 5 , wherein embedding the space comprises applying, by the processor device, a map φ(A) to rows of A, and the map φ(A) corresponds to the nonlinear polynomial kernel.

7. The method of claim 6 , wherein determining the vector x comprises determining min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

8. A computer program product for determining relationships between data, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:
receive, by the processor, one or more sets of input data;
perform, by the processor, a sketching process executable by the processor to:
generate a matrix A and a vector b based on the one or more sets of input data;
create, by the processor, a randomized sketching matrix S based on the matrix A; and
determine, by the processor, a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

perform, by the processor, a relationship process using the sketching process to determine a relationship between the one or more sets of input data based on the vector x.

9. The computer program product of claim 8 , wherein determining the vector x comprises further program code executable by the processor to determine the min x ∥Ax−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

10. The computer program product of claim 9 , wherein the program code further executable by a processor to estimate ∥Ax∥ G , for all xε d based on the sketching matrix S.

11. The computer program product of claim 10 , wherein the relationship process further comprises using the sketching matrix S for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, the processor makes one pass over the matrix A for determining a regression solution with a residual error within a constant factor of a specified tolerance and with constant probability, and nnz comprises a number of non-zero entries of the matrix A.

12. The computer program product of claim 8 , wherein the program code executable by the processor further to:
embed, by the processor, a space induced by a nonlinear polynomial kernel for the matrix A using an oblivious subspace embedding (OSE).

13. The computer program product of claim 12 , wherein the program code executable by the processor further to: embed the space by applying a map φ(A) to rows of A, and the map φ(A) corresponds to the nonlinear polynomial kernel.

14. The computer program product of claim 8 , wherein determine the vector x comprises determine min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

15. A method comprising:
receiving one or more sets of input data;
performing, by a processor device, a sketching process including:
generating a matrix A and a vector b using the one or more sets of input data;
creating, by the processor device, a randomized sketching matrix S based on the matrix A;
applying, by the processor device, a map φ(A) to rows of the matrix A using an oblivious subspace embedding (OSE), wherein the map φ corresponds to a nonlinear kernel;
processing, using the processor device, the map φ(A) and the vector b based on the randomized sketching matrix S; and
determining a vector x that minimizes a normalized measure function based on the map φ(A) and the vector b; and

performing, by the processor device, a relationship process using the sketching process for determining a relationship between the one or more sets of input data based on the vector x.

16. The method of claim 15 , wherein determining the vector x comprises determining the min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

17. The method of claim 16 , further comprising estimating, by the processor device, ∥φ(A)x∥ G , for all xε d based on the sketching matrix S.

18. The method of claim 17 , wherein the map φ(A) maps each row of A to a higher dimensional space using a polynomial kernel of a given degree.

19. The method of claim 18 , further comprising:
computing, by the processor device, an implicit low rank decomposition of φ(A).

20. The method of claim 19 , further comprising:
performing, by the processor device, a principal component regression (PCR) process with respect to an approximation of top k left singular vectors of φ(A), wherein k is a positive integer.

Assignees

• IBM

Inventors

• Avron Haim
• Clarkson Kenneth L
• Nguyen Huy Le
• Woodruff David P

Classifications

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06N20/10

  using kernel methods, e.g. support vector machines [SVM] · CPC title