Support vector machines processing system

• US 20050049990A1
• Filed: 08/27/2004
• Published: 03/03/2005
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Milenova, Boriana L., McCracken, Mark A., Campos, Marcos M., Yarmus, Joseph S.
• Granted Patent: US 7,490,071 B2
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06F 18/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06F 2216/03 Data mining

Abstract

An implementation of SVM functionality improves efficiency, time consumption, and data security, reduces the parameter tuning challenges presented to the inexperienced user, and reduces the computational costs of building SVM models. A system for support vector machine processing comprises data stored in the system, a client application programming interface operable to provide an interface to client software, a build unit operable to build a support vector machine model on at least a portion of the data stored in the system, based on a plurality of model-building parameters, a parameter estimation unit operable to estimate values for at least some of the model-building parameters, and an apply unit operable to apply the support vector machine model using the data stored in the system.

Claims

1. A system for support vector machine processing comprising:

data stored in the system;

a client application programming interface operable to provide an interface to client software;

a build unit operable to build a support vector machine model on at least a portion of the data stored in the system, based on a plurality of model-building parameters;

a parameter estimation unit operable to estimate values for at least some of the model-building parameters; and

an apply unit operable to apply the support vector machine model using the data stored in the system.

2. The system of claim 1, wherein the parameter estimation unit is further operable to select a kernel type method.

3. The system of claim 2, wherein the kernel type method is selected from a linear kernel function and a non-linear kernel function based on an effective dimensionality of training data.

4. The system of claim 1, wherein the parameter estimation unit is further operable to select a complexity parameter C method.

5. The system of claim 4, wherein the complexity parameter C method is selected for a classification method.

6. The system of claim 5, wherein the classification method is a binary classification method or a multi-class classification method.

7. The system of claim 4, wherein the parameter estimation unit is further operable to select the complexity parameter C method for a linear kernel method.

8. The system of claim 7, wherein the complexity parameter C method is selected for a linear kernel method by:

selecting a random sample comprising k pairs of training vectors of opposite class, one member of each pair being of positive class and one member of each pair being of negative class;

for each pair, assigning C to have a value such that a margin for the positive class is 1 and a margin for the negative class is −

1;

ordering the assigned values of C; and

selecting as C a k-th highest assigned value of C.

9. The system of claim 4, wherein the parameter estimation unit is further operable to select the complexity parameter C method for a Gaussian kernel method.

10. The system of claim 9, wherein the complexity parameter C method is selected for a Gaussian kernel method by:

selecting a random group comprising k examples of positive class and k examples of negative class;

predicting a class for each member of the random group, wherein the examples are support vectors with a constant value of alpha;

removing examples that predict a wrong class;

for each remaining example, estimating C as a value required to separate the example from all other group members with a margin of 1;

ordering the estimated values of C; and

selecting as C a k-th highest estimated value of C.

11. The system of claim 4, wherein the parameter estimation unit is further operable to select the complexity parameter C method for a regression method.

12. The system of claim 11, wherein the complexity parameter C method is selected for a regression method by:

selecting a value of C that is a multiple of a target class standard deviation.

13. The system of claim 4, wherein the parameter estimation unit is further operable to select the complexity parameter C method for a one-class support vector machine method.

14. The system of claim 13, wherein the complexity parameter C method is selected for a one-class support vector machine method by:

selecting an initial value of C;

increasing the value of C, while an outlier rate with the initial value of C is above a user-specified value;

setting C to an average of a current value of C and a previous value of C, once the value of C is above the user-specified value, until a target outlier rate is substantially achieved or a maximum number of iterations is reached.

15. The system of claim 1, wherein the parameter estimation unit is further operable to select a standard deviation a for a Gaussian kernel method.

16. The system of claim 15, wherein the parameter estimation unit is further operable to select a standard deviation σ

for a Gaussian kernel method for a classification method.

17. The system of claim 16, wherein the standard deviation a for a Gaussian kernel method for a classification method is selected by:

selecting k pairs of training vectors of opposite class, one member of each pair being of positive class and one member of each pair being of negative class;

for each pair, computing an estimate of σ

based on a distance between members of the pair; and

selecting as σ

a k-th highest estimated σ

.

18. The system of claim 15, wherein the parameter estimation unit is further operable to select a standard deviation σ

for a Gaussian kernel method for a regression method.

19. The system of claim 18, wherein the standard deviation σ

for a Gaussian kernel method for a regression method is selected by;

selecting pairs of random points from the data;

for each pair, determining distances between members of the pair;

ranking the determined distances; and

selecting as σ

a k-th highest distance percentile of the ranked distances.

20. The system of claim 15, wherein the parameter estimation unit is further operable to select a standard deviation σ

for a Gaussian kernel method for a one-class support vector machine method.

21. The system of claim 20, wherein the standard deviation σ

for a Gaussian kernel method for a one-class support vector machine method is selected by;

selecting pairs of random points from the data, both members of each pair being of the one class;

for each pair, determining distances between members of the pair;

ranking the determined distances; and

selecting as σ

a k-th highest distance percentile of the ranked distances.

22. The system of claim 1, wherein the parameter estimation unit is further operable to select an ε

parameter for a regression method.

23. The system of claim 22, wherein the ε

parameter for a regression method is selected by;

selecting an initial value of ε

;

selecting a random sample of data;

converging on the random sample of data;

estimating prediction noise using a held-aside data set;

repeatedly adjusting ε

to be a function of the residuals computed on held-aside data;

selecting as ε

an adjusted value of ε

that produces a lowest residual on the held-aside data set.

24. A system for support vector machine processing comprising:

data stored in the system;

a client application programming interface operable to provide an interface to client software;

a build unit operable to build a support vector machine model on at least a portion of the data stored in the system, the portion of the data selected using partial random chunk selection;

an apply unit operable to apply the support vector machine model using the data stored in the system.

25. The system of claim 24, wherein the build unit is operable to perform partial random chunking selection by:

i) selecting an initial chunk of data from the data stored in the database management system;

ii) performing optimization on the selected chunk until the optimization converges on the selected chunk according to convergence conditions;

iii) checking the convergence conditions against the data stored in the database management system to obtain violators of the convergence conditions;

iv) updating the chunk to form a new selected chunk comprising members of the previous selected chunk and at least some of violators of the convergence conditions, selected randomly with a bias towards large violators; and

v) repeating ii-iv until the convergence conditions are met on at least a portion of the data stored in the database management system.

26. The system of claim 25, wherein the support vector machine model is built using a classification support vector machine algorithm, a regression support vector machine algorithm, or a one-class support vector machine algorithm.

27. The system of claim 25, wherein the build unit is further operable to build a support vector machine model on at least a portion of the data stored in the system using data sampling, and the apply unit is further operable to apply the support vector machine model using the data stored in the system using models based on data sampling.

28. The system of claim 27, wherein the build unit uses an active sampling method.

29. The system of claim 27, wherein the support vector machine model is built using a classification support vector machine algorithm, a regression support vector machine algorithm, or a one-class support vector machine algorithm.

30. The system of claim 25, wherein the build unit is further operable to build a support vector machine model on at least a portion of the data stored in the system using a data summarization driven method, and the apply unit is further operable to apply the support vector machine model using the data stored in the system using models based on data summarization driven method.

31. The system of claim 25, wherein the build unit is further operable to build a support vector machine model on at least a portion of the data stored in the system using stratified random sampling, and the apply unit is further operable to apply the support vector machine model using the data stored in the system using stratified random sampling.

32. The system of claim 25, wherein the processing unit further comprises an incremental update unit.

33. The system of claim 32, wherein the incremental update unit is operable to incorporate additional data into an existing model without rebuilding the entire model.

34. The system of claim 32, wherein the incremental update unit is operable to adapt an existing model to a stream of data wherein an underlying distribution changes over time.

35. A system for support vector machine processing comprising:

data stored in the system;

a client application programming interface operable to provide an interface to client software;

a build unit operable to build a support vector machine model on at least a portion of the data stored in the system, the portion of the data selected using a stratified sampling method with respect to a target distribution;

an apply unit operable to apply the support vector machine model using the data stored in the system.

36. The system of claim 35, wherein the stratified sampling method is performed for a classification method.

37. The system of claim 36, wherein the stratified sampling method is performed for a binary classification method.

38. The system of claim 36, wherein the stratified sampling method is performed for a binary classification method with active learning.

39. The system of claim 36, wherein the stratified sampling method is performed for a multi-class classification method.

40. The system of claim 36, wherein the stratified sampling method is performed for a multi-class classification method with active learning.

41. The system of claim 36, wherein the stratified sampling method is performed by:

balancing a sample during an initial read of the data; and

balancing the sample during creation of a pool of data.

42. The system of claim 41, wherein the balancing of the sample during the initial read of the data is performed by:

randomizing a data cursor with respect to an order of presentation of the data; and

representing an individual target value with a predefined number of examples large enough to represent characteristics of the data, when that number of examples is available.

43. The system of claim 42, wherein the balancing of the sample during the initial read of the data is further performed by:

modeling a multi-class classification problem with a predefined number of data records large enough to represent the characteristics of the data, when that number of data records is available.

44. The system of claim 42, wherein the balancing of the sample during the initial read of the data is further performed by:

retaining a data example if it belongs to a target value that has not met a predefined quota; and

ignoring a data example if it belongs to a target value that has met the predefined quota.

45. The system of claim 44, wherein the balancing of the sample during the initial read of the data is further performed by:

adjusting a quota for a target value when an upper bound on a total number of data examples is reached.

46. The system of claim 45, wherein the quota is adjusted by:

adjusting the quota for a target value to one less than a number of data examples in a class having a highest number of data examples.

47. The system of claim 41, wherein the balancing of the sample during creation of the pool of data is performed by:

dynamically adjusting a quota of a target value to attempt to obtain a pool of data having equal numbers of positive data examples and negative data examples.

48. The system of claim 47, wherein the dynamic adjustment is performed by:

determining relative amounts of positive data examples and negative data examples; and

determining a substantially equal quota for each negative class.

49. The system of claim 35, wherein the stratified sampling method is performed for a regression method.

50. The system of claim 49, wherein the stratified sampling method is performed by:

building a target value histogram; and

adjusting quotas for target ranges based on the target value histogram.

51. The system of claim 50, wherein the quotas for target ranges are adjusted by:

ordering bin counts in ascending order; and

computing corresponding quotas adaptively by redistributing unused data slots among bins with higher counts.

52. The system of claim 35, wherein the stratified sampling method is performed for a regression method with active learning.

53. A method for support vector machine processing comprising:

storing data;

providing an interface to client software;

building a support vector machine model on at least a portion of the stored data, based on a plurality of model-building parameters;

estimating values for at least some of the model-building parameters; and

applying the support vector machine model using the stored data.

54. The method of claim 53, wherein the parameter estimation is performed by:

selecting a kernel type method.

55. The method of claim 54, wherein the kernel type method is selected from a linear kernel function and a non-linear kernel function based on an effective dimensionality of training data.

56. The method of claim 53, wherein the parameter estimation is performed by:

selecting a complexity parameter C method.

57. The method of claim 56, wherein the complexity parameter C method is selected for a classification method.

58. The method of claim 57, wherein the classification method is a binary classification method or a multi-class classification method.

59. The method of claim 56, wherein the parameter estimation is performed by:

selecting the complexity parameter C method for a linear kernel method.

60. The method of claim 59, wherein the complexity parameter C method is selected for a linear kernel method by:

selecting a random sample comprising k pairs of training vectors of opposite class, one member of each pair being of positive class and one member of each pair being of negative class;

for each pair, assigning C to have a value such that a margin for the positive class is 1 and a margin for the negative class is −

1;

ordering the assigned values of C; and

selecting as C a k-th highest assigned value of C.

61. The method of claim 56, wherein the parameter estimation is performed by:

selecting the complexity parameter C method for a Gaussian kernel method.

62. The method of claim 61, wherein the complexity parameter C method is selected for a Gaussian kernel method by:

selecting a random group comprising k examples of positive class and k examples of negative class;

predicting a class for each member of the random group, wherein the examples are support vectors with a constant value of alpha;

removing examples that predict a wrong class;

for each remaining example, estimating C as a value required to separate the example from all other group members with a margin of 1;

ordering the estimated values of C; and

selecting as C a k-th highest estimated value of C.

63. The method of claim 56, wherein the parameter estimation is performed by:

selecting the complexity parameter C method for a regression method.

64. The method of claim 63, wherein the complexity parameter C method is selected for a regression method by:

selecting a value of C that is a multiple of a target class standard deviation.

65. The method of claim 56, wherein the parameter estimation is performed by:

selecting the complexity parameter C method for a one-class support vector machine method.

66. The method of claim 65, wherein the complexity parameter C method is selected for a one-class support vector machine method by:

selecting an initial value of C;

increasing the value of C, while an outlier rate with the initial value of C is above a user-specified value;

setting C to an average of a current value of C and a previous value of C, once the value of C is above the user-specified value, until a target outlier rate is substantially achieved or a maximum number of iterations is reached.

67. The method of claim 53, wherein the parameter estimation is performed by:

selecting a standard deviation σ

for a Gaussian kernel method.

68. The method of claim 67, wherein the parameter estimation is performed by:

selecting a standard deviation σ

for a Gaussian kernel method for a classification method.

69. The method of claim 68, wherein the standard deviation a for a Gaussian kernel method for a classification method is selected by:

selecting k pairs of training vectors of opposite class, one member of each pair being of positive class and one member of each pair being of negative class;

for each pair, computing an estimate of σ

based on a distance between members of the pair; and

selecting as σ

a k-th highest estimated σ

.

70. The method of claim 67, wherein the parameter estimation is performed by:

selecting a standard deviation σ

for a Gaussian kernel method for a regression method.

71. The method of claim 70, wherein the standard deviation σ

for a Gaussian kernel method for a regression method is selected by;

selecting pairs of random points from the data;

for each pair, determining distances between members of the pair;

ranking the determined distances; and

selecting as σ

a k-th highest distance percentile of the ranked distances.

72. The method of claim 67, wherein the parameter estimation is performed by:

selecting a standard deviation σ

for a Gaussian kernel method for a one-class support vector machine method.

73. The method of claim 72, wherein the standard deviation a for a Gaussian kernel method for a one-class support vector machine method is selected by:

selecting pairs of random points from the data, both members of each pair being of the one class;

for each pair, determining distances between members of the pair;

ranking the determined distances; and

selecting as σ

a k-th highest distance percentile of the ranked distances.

74. The method of claim 53, wherein the parameter estimation is performed by:

selecting an ε

parameter for a regression method.

75. The method of claim 74, wherein the ε

parameter for a regression method is selected by;

selecting an initial value of ε

;

selecting a random sample of data;

converging on the random sample of data;

estimating prediction noise using a held-aside data set;

repeatedly adjusting ε

to be a function of the residuals computed on held-aside data;

selecting as ε

an adjusted value of ε

that produces a lowest residual on the held-aside data set.

76. A method for support vector machine processing comprising:

storing data;

providing an interface to client software;

building a support vector machine model on at least a portion of the stored data, the portion of the data selected using partial random chunk selection;

applying the support vector machine model using the stored data.

77. The method of claim 76, wherein the partial random chunk selection is performed by:

i) selecting an initial chunk of data from the data stored in the database management method;

ii) performing optimization on the selected chunk until the optimization converges on the selected chunk according to convergence conditions;

iii) checking the convergence conditions against the data stored in the database management method to obtain violators of the convergence conditions;

iv) updating the chunk to form a new selected chunk comprising members of the previous selected chunk and at least some of violators of the convergence conditions, selected randomly with a bias towards large violators; and

v) repeating ii-iv until the convergence conditions are met on at least a portion of the data stored in the database management method.

78. The method of claim 77, wherein the support vector machine model is built using a classification support vector machine algorithm, a regression support vector machine algorithm, or a one-class support vector machine algorithm.

79. The method of claim 77, wherein the building is performed by:

building a support vector machine model on at least a portion of the data stored in the method using data sampling, and the apply unit is further operable to apply the support vector machine model using the data stored in the method using models based on data sampling.

80. The method of claim 79, wherein the build unit uses an active sampling method.

81. The method of claim 79, wherein the support vector machine model is built using a classification support vector machine algorithm, a regression support vector machine algorithm, or a one-class support vector machine algorithm.

82. The method of claim 77, wherein the building is performed by:

building a support vector machine model on at least a portion of the data stored in the method using a data summarization driven method, and the apply unit is further operable to apply the support vector machine model using the data stored in the method using models based on data summarization driven method.

83. The method of claim 77, wherein the building is performed by:

building a support vector machine model on at least a portion of the data stored in the method using stratified random sampling, and the apply unit is further operable to apply the support vector machine model using the data stored in the method using stratified random sampling.

84. The method of claim 77, further comprising:

incrementally updating the model.

85. The method of claim 84, wherein the incremental updating is performed by:

incorporating additional data into an existing model without rebuilding the entire model.

86. The method of claim 84, wherein the incremental updating is performed by:

adapting an existing model to a stream of data wherein an underlying distribution changes over time.

87. A method for support vector machine processing comprising:

storing data;

providing an interface to client software;

building a support vector machine model on at least a portion of the stored data, the portion of the data selected using a stratified sampling method with respect to a target distribution; and

applying the support vector machine model using the stored data.

88. The method of claim 87, wherein the stratified sampling method is performed for a classification method.

89. The method of claim 88, wherein the stratified sampling method is performed for a binary classification method.

90. The method of claim 88, wherein the stratified sampling method is performed for a binary classification method with active learning.

91. The method of claim 88, wherein the stratified sampling method is performed for a multi-class classification method.

92. The method of claim 88, wherein the stratified sampling method is performed for a multi-class classification method with active learning.

93. The method of claim 88, wherein the stratified sampling method is performed by:

balancing a sample during an initial read of the data; and

balancing the sample during creation of a pool of data (multiclass classification).

94. The method of claim 93, wherein the balancing of the sample during the initial read of the data is performed by:

randomizing a data cursor with respect to an order of presentation of the data; and

representing an individual target value with a predefined number of examples large enough to represent characteristics of the data, when that number of examples is available.

95. The method of claim 94, wherein the balancing of the sample during the initial read of the data is further performed by:

modeling a multi-class classification problem with a predefined number of data records large enough to represent the characteristics of the data, when that number of data records is available.

96. The method of claim 94, wherein the balancing of the sample during the initial read of the data is further performed by:

retaining a data example if it belongs to a target value that has not met a predefined quota; and

ignoring a data example if it belongs to a target value that has met the predefined quota.

97. The method of claim 96, wherein the balancing of the sample during the initial read of the data is further performed by:

adjusting a quota for a target value when an upper bound on a total number of data examples is reached.

98. The method of claim 97, wherein the quota is adjusted by:

adjusting the quota for a target value to one less than a number of data examples in a class having a highest number of data examples.

99. The method of claim 93, wherein the balancing of the sample during creation of the pool of data is performed by:

dynamically adjusting a quota of a target value to attempt to obtain a pool of data having equal numbers of positive data examples and negative data examples.

100. The method of claim 99, wherein the dynamic adjustment is performed by:

determining relative amounts of positive data examples and negative data examples; and

determining a substantially equal quota for each negative class.

101. The method of claim 87, wherein the stratified sampling method is performed for a regression method.

102. The method of claim 101, wherein the stratified sampling method is performed by:

building a target value histogram; and

adjusting quotas for target ranges based on the target value histogram.

103. The method of claim 102, wherein the quotas for target ranges are adjusted by:

ordering bin counts in ascending order; and

computing corresponding quotas adaptively by redistributing unused data slots among bins with higher counts.

104. The method of claim 87, wherein the stratified sampling method is performed for a regression method with active learning.