摘要 |
A technique solves an SVM problem on table J, defined as the join of two tables T1 and T2, without explicitly joining the tables T1 and T2, in which the table T1 has m rows (piT, uiT), i=1, . . . , m, and the table T2 has n rows (qjT, vjT), j=1, . . . , n. A computer obtains a modified optimization problem from a primal optimization problem in which the modified optimization problem includes minimizew,b,η,ζ½∥w∥2+C·Σi=1mJ(i)·ηi+C·Σj=1nI(j)·ζj, subject to yixijTw−yib+ηi+ζj≧1 ((i,j)∈IJ) and ηi, ζj≧0. The penalty variables are reduced in the modified optimization problem by replacing the penalty variables in a form of ξij for each (i,j)∈IJ with the penalty variables in a form of ζij=ηi+ζj. A compact form of the modified optimization problem is obtained which includes minimizew,b,η,ζ,σ,τ½∥wP∥2+½∥wU∥2+½∥wQ∥2+C·Σi=1mJ(i)·ηi+C·Σj=1nI(j) ·ζj which is subject to yipiTwP−yib+ξi−σk≧0 (i∈Ik, k=1, . . . l), qjTwQ−τk≧0 (j∈Jk, k=1, . . . l), σk+zkTwU+τk≧1 (for k=1, . . . l such that Jk≠), σkzkTwU≧1 (for k=1, . . . l such that Jk=), and ξi≧0 (i=1, . . . , m). The compact form of the modified optimization problem is solved. |
主权项 |
1. A method, by a computer, of solving a support vector machine problem on table J, defined as the join of two tables T1 and T2, without explicitly joining the tables T1 and T2, wherein the table T1 has m rows (piT, uiT), i=1, . . . , m, and the table T2 has n rows (qjT, vjT), j=1, . . . , n, the method comprising:
providing a primal optimization problem over a join of the tables T1 and T2; obtaining, by the computer, a modified optimization problem from the primal optimization problem; reducing penalty variables in the modified optimization problem by replacing the penalty variables in a form of ξij for each (i,j)∈IJ with the penalty variables in a form of ξij=ηi+ζj; obtaining a compact form of the modified optimization problem in which the compact form comprises the penalty variables in the form of ξijηiζj; and solving the compact form of the modified optimization problem. |