REGRESSION USING M-ESTIMATORS AND POLYNOMIAL KERNEL SUPPORT VECTOR MACHINES AND PRINCIPAL COMPONENT REGRESSION

• US 20150331835A1
• Filed: 05/15/2014
• Published: 11/19/2015
• Est. Priority Date: 05/15/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Avron, Haim, Clarkson, Kenneth L., Woodruff, David P., Nguyen, Huy Le
• Granted Patent: US 9,658,987 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 17/18 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 Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

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.

Claims

1. A method comprising:

providing one or more sets of input data;

generating a matrix A and a vector b using the one or more sets of input data;

processing, using a processor device, the matrix A and the vector b based on a randomized sketching matrix S;

determining a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

determining a relationship between the one or more sets of input data based on the vector x.

2. The method of claim 1, wherein said determining the vector x comprises determining the min_x∥

Ax−

b∥

_G, where Aε

<sup>n×

d</sup> and bε

ⁿ, and ∥

y∥

_G for yε

ⁿ is specified by the measure function G;

⁺, wherein ∥

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, wherein the sketching matrix S is used to estimate ∥

Ax∥

_G, for all xε

^d.

4. The method of claim 3, wherein the sketching matrix S is used for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, wherein the processor device 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, wherein nnz comprises a number of non-zero entries of the matrix A.

5. The method of claim 1, further comprising:

providing an oblivious subspace embedding (OSE) for embedding a space induced by a nonlinear polynomial kernel for the matrix A.

6. The method of claim 5, wherein embedding the space comprises applying a map φ

(A) to rows of A, wherein 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ε

<sup>n×

d</sup> and bε

ⁿ, and ∥

y∥

_G for yε

ⁿ is specified by the measure function G;

⁺, wherein ∥

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 readable/executable by a processor to:

receive one or more sets of input data;

generate a matrix A and a vector b based on the one or more sets of input data;

process the matrix A and the vector b based on a randomized sketching matrix S;

determine a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

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 said determining the vector x comprises determining the min_x∥

Ax−

b∥

_G, where Aε

<sup>n×

d</sup> and bε

ⁿ, and ∥

y∥

_G for yε

ⁿ is specified by the measure function G;

⁺, wherein ∥

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 sketching matrix S is used to estimate ∥

Ax∥

_G, for all xε

^d.

11. The computer program product of claim 10, wherein the sketching matrix S is used for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, wherein the processor device 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, wherein nnz comprises a number of non-zero entries of the matrix A.

12. The computer program product of claim 8, wherein the program code readable/executable by the processor further to:

provide an oblivious subspace embedding (OSE) for embedding a space induced by a nonlinear polynomial kernel for the matrix A.

13. The computer program product of claim 12, wherein embedding the space comprises applying a map φ

(A) to rows of A, wherein 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ε

<sup>n×

d</sup> and bε

ⁿ, and ∥

y∥

_G for yε

ⁿ is specified by the measure function G;

⁺, wherein ∥

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:

providing one or more sets of input data;

generating a matrix A and a vector b using the one or more sets of input data;

providing an oblivious subspace embedding (OSE) for applying a map φ

(A) to rows of the matrix A, wherein the map φ

corresponds to a nonlinear kernel;

processing, using a processor device, the map φ

(A) and the vector b based on a randomized sketching matrix S;

determining a vector x that minimizes a normalized measure function based on the map φ

(A) and the vector b; and

determining a relationship between the one or more sets of input data based on the vector x.

16. The method of claim 15, wherein said determining the vector x comprises determining the min_x∥

φ

(A)x−

b∥

_G, where Aε

<sup>n×

d</sup> and bε

ⁿ, and ∥

y∥

_G for yε

ⁿ is specified by the measure function G;

⁺, wherein ∥

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, wherein the sketching matrix S is used to estimate ∥

φ

(A)x∥

_G, for all xε

^d.

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 an implicit low rank decomposition of φ

(A).

20. The method of claim 19, further comprising:

performing principal component regression (PCR) with respect to an approximation of top k left singular vectors of φ

(A), wherein k is a positive integer.