Patent ID: 8719194

Claim:
A computer-implemented method for training a classifier for selecting features in sparse data sets with high feature dimensionality, the method performed by the computer comprising the steps of: providing a set of N data items x and associated labels y, each data item being a vector in R m where m>>1; minimizing a functional of the data items x and associated labels y L ⁡ ( w , b , a , c , γ 1 , γ 2 ) := 1 N ⁢ ∑ i = 1 N ⁢ a i + λ 1 ⁢  c  1 + λ 2 2 ⁢  w  2 2 + γ 1 T ⁡ ( e - Y ⁡ ( X ⁢ ⁢ w + b ⁢ ⁢ e ) - a ) + γ 2 T ⁡ ( w - c ) + μ 1 2 ⁢  e - Y ⁡ ( X ⁢ ⁢ w + b ⁢ ⁢ e ) - a  2 2 + μ 2 2 ⁢  w - c  2 2 formed from a program min w , b , a , c ⁢ 1 N ⁢ ∑ i = 1 N ⁢ a i + λ 1 ⁢  c  1 + λ 2 2 ⁢  w  2 2 subject to { a = e - Y ⁡ ( X ⁢ ⁢ w + b ⁢ ⁢ e ) , c = w . to solve for hyperplane w and offset b of a classifier using an alternating direction method of multipliers that successively iteratively approximates w and b, auxiliary variables a and c, and multiplier vectors γ 1 and γ 2 , wherein λ 1 , λ 2 , μ 1 , and μ 2 are predetermined constants, e is a unit vector, and X and Y are respective matrix representations of the data items x and their associated labels y; providing non-zero elements of the hyperplane vector w and those components of X and Y that correspond to the non-zero elements of the hyperplane vector w as arguments to a convex quadratic program solver that uses an interior point method to solve for hyperplane vector w and offset b, wherein the hyperplane vector w and offset b define a classifier than can associate each data item x with the correct label y.