Classification Tool

• US 20080109389A1
• Filed: 11/02/2007
• Published: 05/08/2008
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: George Mason Intellectual Properties, Inc.
• Original Assignee: George Mason Intellectual Properties, Inc.
• Inventors: Griva, Igor, Polyak, Roman A., Ho, Shen-Shyang
• Granted Patent: US 7,840,505 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A classification system that includes a first input module, a marker module, unclassified Lagrange multiplier calculation module, and a classification module. The unclassified vector describes a physical condition. The marker module assigns a marker to the unclassified vector. The marker should place the unclassified vector into one of two classes. The unclassified Lagrange multiplier calculation module calculates a classifying Lagrange multiplier for the unclassified vector using the marker and a classification rule. The classification rule may be generated using a training system for classifying the physical condition. The classification module is configured to determine that the marker places the unclassified vector in the proper class if the classifying Lagrange multiplier is small.

Claims

1. A training system for classifying a physical condition, the system comprising:

a) an input module configured to receive n labeled data points {(a₁, y₁), . . . ,(a_n, y_n)}, at least one of said n labeled data points describing at least one physical parameter for a physical phenomenon, said n labeled data points including vectors a_i ε

and markers y_i ε

{−

1,1}, each of said n labeled data points placed in one of two sets I₊={i;

(a_i,1)} and I₋

={i;

(a_i,−

1)};

b) a mathematical formulation module configured to use said n labeled data points to model said physical phenomenon as a mathematical formulation, said mathematical formulation including;

i) variables x=(w,b,Δ

), where w ε

, b ε

, Δ

ε

;

ii) an objective function ƒ

(x)=Δ

; and

iii) a plurality of constraints, said plurality of constraints including;

c_i(x)≡

c_i(w,b,Δ

)=(w,a_i)−

b−

Δ

≧

0,iε

I₊;

 

 

(1)

c_i(x)≡

c_i(w,b,Δ

)=−

(w,a_i)+b−

Δ

≧

0,iε

I₋

; and

 

 

(2)

∥

w∥

²=1;

 

 

(3)

c) a transformer module configured to build a specific function L(w,b,Δ

,λ

,γ

,τ

) using;

i) said mathematical formulation;

ii) Lagrange multipliers λ

=(λ

₁, . . . , λ

_n);

iii) scaling parameters γ

, τ

, k;

iv) a class of transformation functions with a predefined set of properties; and

v) said n labeled data points, said n labeled data points further including a nonlinear resealing part;

d) a Lagrange multipliers updater module configured to calculate updated Lagrange multipliers {circumflex over (λ

)}=({circumflex over (λ

)}₁, . . . , {circumflex over (λ

)}_n);

e) a scaling parameters updater module configured to calculate updated scaling parameters {circumflex over (γ

)}, {circumflex over (τ

)}, {circumflex over (k)}; and

f) an iterative solver module configured to generate a classification rule using;

i) said specific function;

ii) said Lagrange multipliers updater module;

iii) said scaling parameters updater module;

iv) a general stopping criteria verifier module; and

v) an accuracy parameter (ε

).

2. A system according to claim 1, wherein said predefined set of properties includes:

ψ

(t);

→

defined on −

∞

≦

a<

t<

b≦

∞

;

 

 

i)

ψ

(0)=0;

 

 

ii)

ψ

′

(0)=1;

 

 

iii)

ψ

′

(t)>

0;

 

 

iv)

ψ

″

(t)<

0; and

 

 

v)

3. A system according to claim 2, wherein said predefined set of properties further includes:

ψ

″

(t)>

0; and

 

 

i)

4. A system according to claim 1, wherein said mathematical formulation includes said objective function being optimized subject to at least said plurality of constraints.

5. A system according to claim 1, wherein said specific function includes:

6. A system according to claim 1, wherein said nonlinear resealing part includes at least:

7. A system according to claim 1, wherein said Lagrange multipliers updater module uses Lagrange multipliers update formulas.

8. A system according to claim 7, wherein said Lagrange multipliers update formulas include at least one formula that responds to inequality constraints {circumflex over (λ

)}_i=λ

_iψ

′

(kc_i({circumflex over (x)})), i=1, . . . ,n.

9. A system according to claim 1, wherein said scaling parameters updater module uses scaling parameter update formula {circumflex over (k)}=kθ

, θ

≧

1.

10. A system according to claim 1, wherein said scaling parameters updater module uses scaling parameter update formula

11. A system according to claim 1, wherein said scaling parameters updater module updates {circumflex over (γ

)} such that ∥

ŵ

∥

²=1, where

12. A system according to claim 1, wherein said iterative solver module uses a general stopping criteria verifier module for determining when said iterative solver should terminate.

13. A system according to claim 1, wherein said iterative solver module uses a general stopping criteria.

14. A system according to claim 1, wherein said general stopping criteria verifier module uses said accuracy parameter.

15. A system according to claim 14, wherein said general stopping criteria verifier module considers when ∥

λ

−

{circumflex over (λ

)}∥

≦

ε

.

16. A system according to claim 1, wherein said iterative solver module is a MIN_UPDATE solver module.

17. A system according to claim 16, wherein said MIN_UPDATE solver module uses:

a) a specific function minimizer module for performing an unconstrained minimization in variables of said specific function with determined said Lagrange multipliers and said scaling parameters;

said specific function minimizer module is configured to produce updated variables;

b) a minimizer stopping criteria checker for determining when said specific function minimizer should terminate;

c) said Lagrange multipliers updater module for calculating said updated Lagrange multipliers using said updated variables, said Lagrange multipliers and said Lagrange multipliers update formula;

d) said scaling parameters updater module for calculating said updated scaling parameters using said updated variables, said updated Lagrange multipliers, said scaling parameters and said scaling parameters update formula; and

e) said general stopping criteria verifier module.

18. A system according to claim 17, wherein said specific function minimizer module uses a Newton'"'"'s method.

19. A system according to claim 17, wherein said MIN_UPDATE solver module uses accuracy of minimizer parameter (ε

_m), and said minimizer stopping criteria uses said accuracy of minimizer parameter.

20. A system according to claim 17, wherein said updated variables ({circumflex over (x)}) must satisfy said minimizer stopping criteria.

21. A system according to claim 17, wherein said minimizer stopping criteria checker uses at least one of the following:

a) said updated variables;

b) said Lagrange multipliers;

c) said scaling parameter;

d) said updated Lagrange multipliers; and

e) a stopping inequality verifier.

22. A system according to claim 21, wherein said stopping inequality verifier is selected such that {circumflex over (x)}:

∥

∇

_xL({circumflex over (x)},λ

,γ

,τ

,k)∥

≦

ε

_m.

23. A classification system, said classification system comprising:

a) an first input module configured to receive an unclassified vector that describes a physical condition;

b) a marker module configured to assign a marker to said unclassified vector, said marker placing said unclassified vector in one of two classes;

c) an unclassified Lagrange multiplier calculation module configured to calculate an classifying Lagrange multiplier for said unclassified vector using;

i) said marker; and

ii) a classification rule, said classification rule configured to distinguish between said two classes, said classification rule generated using a training system for classifying said physical condition, said training system comprising;

(1) a second input module configured to receive n labeled data points {(a₁, y₁), . . . ,(a_n, y_n)}, at least one of said n labeled data points describing at least one physical parameter for a physical phenomenon, said n labeled data points including vectors a_i ε

and markers y_i ε

{−

1,1}, each of said n labeled data points placed in one of two sets I₊={i;

(a_i,1)} and I₋

={i;

(a_i,−

1)};

(2) a mathematical formulation module configured to use said n labeled data points to model said physical phenomenon as a mathematical formulation, said mathematical formulation including;

(a) variables x=(w,b,Δ

), where w ε

, b ε

, Δ

ε

;

(b) an objective function ƒ

(x)=Δ

; and

(c) a plurality of constraints, said plurality of constraints including;

c_i(x)≡

c_i(w,b,Δ

)=(w,a_i)−

b−

Δ

≧

0,iε

I₊;

 

 

(i)

c_i(x)≡

c_i(w,b,Δ

)=−

(w,a_i)+b−

Δ

≧

0,iε

I₋

; and

 

 

(ii)

∥

w∥

²=1;

 

 

(iii)

(3) a transformer module configured to build a specific function L(w,b,Δ

,λ

,γ

,τ

) using;

(a) said mathematical formulation;

(b) Lagrange multipliers λ

=(λ

₁, . . . , λ

_n);

(c) scaling parameters γ

, τ

, k;

(d) a class of transformation functions with a predefined set of properties; and

(e) said n labeled data points, said n labeled data points further including a nonlinear resealing part;

(4) a Lagrange multipliers updater module configured to calculate updated Lagrange multipliers {circumflex over (λ

)}=({circumflex over (λ

)}₁, . . . , {circumflex over (λ

)}_n);

(5) a scaling parameters updater module configured to calculate updated scaling parameters {circumflex over (γ

)}, {circumflex over (τ

)}, {circumflex over (k)}; and

(6) an iterative solver module configured to generate a classification rule using;

(a) said specific function;

(b) said Lagrange multipliers updater module;

(c) said scaling parameters updater module;

(d) a general stopping criteria verifier module; and

(e) an accuracy parameter (ε

); and

d) a classification module configured determine that said marker places said unclassified vector in the proper class if said classifying Lagrange multiplier is small.

24. A method for generating a classification rule comprising:

a) receiving n labeled data points {(a₁, y₁), . . . ,(a_n, y_n)}, at least one of said n labeled data points describing at least one physical parameter for a physical phenomenon, said n labeled data points including vectors a_i ε

and markers y_i ε

{−

1,1}, each of said n labeled data points placed in one of two sets I₊={i;

(a_i,1)} and I₋

={i;

(a_i,−

1)};

b) modeling said physical phenomenon as a mathematical formulation using said n labeled data points, said mathematical formulation including;

i) variables x=(w,b,Δ

), where w ε

b ε

Δ

ε

;

ii) an objective function ƒ

(x)=Δ

; and

iii) a plurality of constraints, said plurality of constraints including;

c_i(x)≡

c_i(w,b,Δ

)=(w,a_i)−

b−

Δ

≧

0,iε

I₊;

 

 

(1)

c_i(x)≡

c_i(w,b,Δ

)=−

(w,a_i)+b−

Δ

≧

0,iε

I₋

; and

 

 

(2)

∥

w∥

²=1;

 

 

(3)

c) building a specific function L(w,b,Δ

,λ

,γ

,τ

) using;

i) said mathematical formulation;

ii) Lagrange multipliers λ

=(λ

₁, . . . , λ

_n);

iii) scaling parameters γ

, τ

, k;

iv) a class of transformation functions with a predefined set of properties; and

v) said n labeled data points, said n labeled data points further including a nonlinear resealing part;

d) calculating updated Lagrange multipliers {circumflex over (λ

)}=({circumflex over (λ

)}₁, . . . , {circumflex over (λ

)}_n);

e) calculating updated scaling parameters {circumflex over (γ

)}, {circumflex over (τ

)}, {circumflex over (k)}; and

f) iteratively generating a classification rule using;

i) said specific function;

ii) said Lagrange multipliers updater module;

iii) said scaling parameters updater module;

iv) a general stopping criteria verifier module; and

v) an accuracy parameter (ε

).

25. A method classifying an unclassified vector, the method comprising:

a) assigning a marker to said unclassified vector, said marker placing said unclassified vector in one of two classes;

b) calculating a classifying Lagrange multiplier for said unclassified vector using;

i) said marker; and

ii) a classification rule, said classification rule configured to distinguish between said two classes, said classification rule generated using a training method, said training method comprising;

(1) receiving n labeled data points {(a₁, y₁), . . . ,(a_n, y_n)}, at least one of said n labeled data points describing a physical parameter for a physical phenomenon, said n labeled data points including vectors a_i ε

and markers y_i ε

{−

1,1}, each of said n labeled data points placed in one of two sets I₊={i;

(a_i,1)} and I₋

={i;

(a_i,−

1)};

(2) modeling said physical phenomenon as a mathematical formulation using said n labeled data points, said mathematical formulation including;

(a) variables x=(w,b,Δ

), where w ε

, b ε

, Δ

ε

;

(b) an objective function ƒ

(x)=Δ

; and

(c) a plurality of constraints, said plurality of constraints including;

c_i(x)≡

c_i(w,b,Δ

)=(w,a_i)−

b−

Δ

≧

0,iε

I₊;

 

 

(i)

c_i(x)≡

c_i(w,b,Δ

)=−

(w,a_i)+b−

Δ

≧

0,iε

I₋

; and

 

 

(ii)

∥

w∥

²=1;

 

 

(iii)

(3) Building a specific function L(w,b,Δ

,λ

,γ

,τ

) using;

(a) said mathematical formulation;

(b) Lagrange multipliers λ

=(λ

₁, . . . , λ

_n);

(c) scaling parameters γ

, τ

, k;

(d) a class of transformation functions with a predefined set of properties; and

(e) said n labeled data points, said n labeled data points further including a nonlinear resealing part;

(4) calculating updated Lagrange multipliers {circumflex over (λ

)}=({circumflex over (λ

)}₁, . . . , {circumflex over (λ

)}_n);

(5) calculating updated scaling parameters {circumflex over (γ

)}, {circumflex over (τ

)}, {circumflex over (k)}; and

(6) iteratively generating a classification rule using;

(a) said specific function;

(b) said Lagrange multipliers updater module;

(c) said scaling parameters updater module;

(d) a general stopping criteria verifier module; and

(e) an accuracy parameter (ε

); and

c) determining that said marker places said unclassified vector in the proper class if said classifying Lagrange multiplier is small.