[figure]

Pattern separation via ellipsoids and conic programming

François Glineur

F.N.R.S. research fellow

Faculté Polytechnique de Mons

Advanced Optimization lab

Department of Computing and Software

McMaster university, Hamilton, Canada, August 9, 2001

Pattern separation via ellipsoids and conic programming

[figure]

Objective

Machine learning

⋄ Separation problem ⋄ Classification Mathematical programming

⋄ Linear optimization ⋄ Interior-point methods ⋄ SQL conic optimization \overline{Goal}

Solve the separation problem using SQL conic optimization

\overline{How} Use ellipsoids to perform the separation

[figure]

Outline

Conic optimization ⋄ Background ⋄ SQL conic optimization ⋄ Modelling

Pattern separation ⋄ Problem definition ⋄ Describing an ellipsoid ⋄ Four separation algorithms ⋄ Exploitation

Computational experiments ⋄ Comparison between our algorithms ⋄ Comparison with other methods

Conclusions

[figure]

Conic optimization

Background Operations research : Model ⇒ (help to) choose the best decision Optimization, mathematical programming : Minimize function of n variables under a set of constraints General mathematical program is too difficult : no algorithm with performance guarantee, existence of local minima Linear optimization : special case, very efficient algorithms Convex optimization : Generalize linear optimization while keeping its good properties

⋄ No local minima

⋄ Efficient interior-point methods ⋄ Model much more problems than LP

[figure]

Every convex program can be stated in a conic form

(CONE)  min_{x∈ℝ^{n}} c^{T} x s.t. x ∈ C ∩ (b + L)

C is a closed, pointed and solid convex cone, b and c are vectors and L is a linear subspace. Interior-point methods solve (CONE) with ϵ relative accuracy using

O (\sqrt{ν} log \frac{1}{ϵ})

iterations where ν depends only on the structure of C [NN94].

\overline{Duality}

(DUAL)  min_{y∈ℝ^{n}} b^{T} y s.t. y ∈ C^{∗} ∩ (c + L^{T})

C^{∗} is the dual cone. Also a conic program. Weak duality, strong duality with a Slater condition (otherwise : nonzero duality gap, optimum objective value not attained, etc.)

[figure]

Self-scaled cones Special type of cone ⇒ long step primal-dual interior point method, very efficient in practice

Classification : any self-scaled cone is the Cartesian product of primitive self-scaled cones

⋄ The nonnegative reals ℝ_{+} (⇒ LP) ⋄ The second order cone 𝕃_{+}^{n}

𝕃_{+}^{n} = {(r, x) ∈ ℝ × ℝ^{n} | r ≥ ∥x∥}

⋄ The cone of positive semidefinite matrices with real entries 𝕊_{+}^{n}

(⇒ Semidefinite optimization) ⋄ The cone of positive semidefinite matrices with complex entries ⋄ The cone of positive semidefinite matrices with quaternion entries ⋄ The cone of 3 × 3 positive semidefinite matrices with octonion

entries

[figure]

We use only real self-scaled cones ℝ_{+}^{n}, 𝕃_{+}^{n} and 𝕊_{+}^{n} : a conic program involving these cones is called a SQL conic program.

\overline{Modelling} ⋄ Includes linear and semidefinite programs ⋄ Model nonlinear (convex) constraints like xy ≥ 1, E ∈ 𝕊_{+}^{n},

λ_{max}(E) ≤ 1 ⋄ Minimize nonlinear (convex) objectives like \frac{x^{2}}{y}, ∥x∥, λ_{max}(E) ⋄ Handle free variables in a very natural way (using 𝕃_{+}^{n}) ⋄ But only convex programs (e.g. impossible to minimize \frac{x}{y})

SQL conic programs ≡ convex programs that are easy to describe.

[figure]

Pattern separation

Problem definition Pattern ≡ vector combining n numerical attributes characterizing an object. Assume these objects are naturally grouped into c classes. Objective : find a partition of ℝ^{n} into c disjoint components corresponding to the classes.

Classification Some objects grouped into classes and some unknown objects :

1. Separate the patterns of well-known objects ≡ learning phase

2. Use that partition to classify the unknown objects ≡ generalization phase

Examples : medical diagnosis, species identification, credit approval

[figure]

Formulation Reduce problem with c classes to c independent problems involving 2 classes ⇒ consider w.l.o.g. two classes : A = {a_{i}} and B = {b_{j}}

Main idea : use ellipsoids for separation i.e. find E s.t.

a_{i} ∈ E ∀i and b_{j} ∉ E ∀j

An ellipsoid ≡ a center c ∈ ℝ^{n} and a p.s.d. matrix E ∈ 𝕊_{+}^{n} E = {x ∈ ℝ^{n} | (x − c)^{T} E(x − c) ≤ 1}

Separation ratio We want the best possible separation ⇒ optimize the separation ratio

Definition : Using a pair of similar ellipsoids with the same center, separation ratio ρ ≡ ratio of sizes

[figure]

[figure]

Formulation Reduce problem with c classes to c independent problems involving 2 classes ⇒ consider w.l.o.g. two classes : A = {a_{i}} and B = {b_{j}}

Main idea : use ellipsoids for separation i.e. find E s.t.

a_{i} ∈ E ∀i and b_{j} ∉ E ∀j

An ellipsoid ≡ a center c ∈ ℝ^{n} and a p.s.d. matrix E ∈ 𝕊_{+}^{n} E = {x ∈ ℝ^{n} | (x − c)^{T} E(x − c) ≤ 1}

Separation ratio We want the best possible separation ⇒ optimize the separation ratio

Definition : Using a pair of similar ellipsoids with the same center, separation ratio ρ ≡ ratio of sizes

[figure]

[figure]

Formulation Reduce problem with c classes to c independent problems involving 2 classes ⇒ consider w.l.o.g. two classes : A = {a_{i}} and B = {b_{j}}

Main idea : use ellipsoids for separation i.e. find E s.t.

a_{i} ∈ E ∀i and b_{j} ∉ E ∀j

An ellipsoid ≡ a center c ∈ ℝ^{n} and a p.s.d. matrix E ∈ 𝕊_{+}^{n} E = {x ∈ ℝ^{n} | (x − c)^{T} E(x − c) ≤ 1}

Separation ratio We want the best possible separation ⇒ optimize the separation ratio

Definition : Using a pair of similar ellipsoids with the same center, separation ratio ρ ≡ ratio of sizes

[figure]

[figure: (ρ = 1.5)] [figure: (ρ ≈ 1.8)] [figure: (ρ ≈ 1.8)]

[figure]

Formulation Maximize ρ

max ρ s.t. \{ \begin{matrix}(a_{i} − c)^{T} E(a_{i} − c) ≤ 1 ∀i \\ (b_{j} − c)^{T} E(b_{j} − c) ≥ ρ^{2} ∀j \\ E ∈ 𝕊_{+}^{n} \end{matrix}

Two problems

1. ρ^{2} is nonlinear ⇒ let k = ρ^{2}, maximize k

2. (x − c)^{T} E(x − c) is also nonlinear (nonconvex) ⇒ homogeneous ellipsoid

[figure]

Homogeneous ellipsoid Ellipsoid in ℝ^{n} ⇔ Centered Ellipsoid in ℝ^{n+1}

→ Replace (x − c)^{T} E(x − c) with (1, x)^{T} Ẽ(1, x) → Optimize Ẽ ∈ 𝕊_{+}^{n+1} → Recover optimal E, c with optimal Ẽ

[figure]

Maximum separation ratio

min −k s.t. \{ \begin{matrix}(1, a_{i})^{T} Ẽ(1, a_{i}) ≤ 1 ∀i \\ (1, b_{j})^{T} Ẽ(1, b_{j}) ≥ k ∀j \\ Ẽ ∈ 𝕊_{+}^{n+1} \end{matrix}

This is a SQL conic program

Properties

1. Program maximizes the separation ratio between a_{i}’s and b_{j}’s 2. Independence from the coordinate system

Drawback What if there is no separating ellipsoid ?

⋄ Convex hulls and A and B intersect ⋄ Other cases

[figure]

[figure]

[figure]

Minimum volume Idea : find the ellipsoid containing the a_{i}’s with minimum volume Works when there is no separating ellipsoid True volume of E : difficult to model in the SQL framework ⇒ use a related measure using semi-axes s_{i}

boxsize(E) = \sqrt{∑_{i=1}^{n} λ_{i}(E)^{−1}} = \sqrt{∑_{i=1}^{n} s_{i}^{2}}

Model as a SQL conic program Drawbacks

⋄ Doesn’t use the b_{j}’s ⋄ Scaling dependent

François Glineur, FPMs  Page 23  Adv. Opt. lab seminar, McMaster

[figure]

[figure]

Minimum volume Idea : find the ellipsoid containing the a_{i}’s with minimum volume Works when there is no separating ellipsoid True volume of E : difficult to model in the SQL framework ⇒ use a related measure using semi-axes s_{i}

boxsize(E) = \sqrt{∑_{i=1}^{n} λ_{i}(E)^{−1}} = \sqrt{∑_{i=1}^{n} s_{i}^{2}}

Model as a SQL conic program Drawbacks

⋄ Doesn’t use the b_{j}’s ⋄ Scaling dependent

François Glineur, FPMs  Page 25  Adv. Opt. lab seminar, McMaster

[figure]

[figure]

Maximum sum of ratios Individual separation ratios ρ_{j} for each b_{j}

Maximum separation ratio ≡ maximize the smallest ρ_{j} ⇔ worst case method

Idea : maximize most of the ρ_{j}’s by maximizing ∑ ρ_{j}^{2}

min − ∑_{j} k_{j} s.t. \{ \begin{matrix}(1, a_{i})^{T} Ẽ(1, a_{i}) ≤ 1 ∀i \\ (1, b_{j})^{T} Ẽ(1, b_{j}) = k_{j} ∀j \\ Ẽ ∈ 𝕊_{+}^{n+1} \end{matrix}

Properties

1. Works when there is no separating ellipsoid

2. Independence from the coordinate system

[figure]

Drawback : May miss a separating ellipsoid

Explanation : Formulation ≡ maximize the ρ_{j}’s quadratic mean ⇒ large ρ_{j}’s dominate the objective ⇒ small ρ_{j}’s are not maximized

Remedy : Combine the ρ_{j}’s into an objective such that small values have more influence than large ones

[figure]

Pattern separation via ellipsoids and conic programming

[figure: (sum)]

François Glineur, FPMs  Page 30  Adv. Opt. lab seminar, McMaster

[figure]

Maximum harmonic mean Idea : maximize the harmonic mean of the ρ_{j}’s Even better : maximize the harmonic mean of the ρ_{j}^{4}’s

min ∑_{i} k_{i}^{2} s.t. \{ \begin{matrix}(1, a_{i})^{T} Ẽ(1, a_{i}) = k_{i} ∀i \\ (1, b_{j})^{T} Ẽ(1, b_{j}) ≥ 1 ∀j \\ Ẽ ∈ 𝕊_{+}^{n+1} \end{matrix}

This is equivalent to

min t s.t. \{ \begin{matrix}(1, a_{i})^{T} Ẽ(1, a_{i}) = k_{i} ∀i \\ (1, b_{j})^{T} Ẽ(1, b_{j}) ≥ 1 ∀j \\ Ẽ ∈ 𝕊_{+}^{n+1} \\ (t, k_{1}, …, k_{n_{a}}) ∈ 𝕃_{+}^{n_{a}+1} \end{matrix}

[figure]

min t s.t. \{ \begin{matrix}(1, a_{i})^{T} Ẽ(1, a_{i}) = k_{i} ∀i \\ (1, b_{j})^{T} Ẽ(1, b_{j}) ≥ 1 ∀j \\ Ẽ ∈ 𝕊_{+}^{n+1} \\ (t, k_{1}, …, k_{n_{a}}) ∈ 𝕃_{+}^{n_{a}+1} \end{matrix}

is an SQL conic program

Properties

1. Works when there is no separating ellipsoid 2. Independence from the coordinate system 3. Tries to maximize small ρ_{j}’s

[figure]

Pattern separation via ellipsoids and conic programming

[figure: (sum)]

François Glineur, FPMs  Page 34  Adv. Opt. lab seminar, McMaster

Pattern separation via ellipsoids and conic programming

[figure: (harm.)]

François Glineur, FPMs  Page 35  Adv. Opt. lab seminar, McMaster

[figure]

Exploitation method

To classify an unknown pattern p with E compute

p_{E} = (p − c)^{T} E(p − c)

1. p_{E} ≤ 1 ⇒ p belongs to the class of a_{i}’s

2. p_{E} > 1 ⇒ p belongs to the class of b_{j}’s

Not symmetric : permute a_{i}’s and b_{j}’s ⇒ gives another ellipsoid E′

Mixed strategy using both ellipsoids

1. p_{E} ≤ p_{E′} ⇒ p belongs to the class of a_{i}’s

2. p_{E} > p_{E′} ⇒ p belongs to the class of b_{j}’s

When both ellipsoids agree, mixed strategy agrees too

[figure]

[figure]

Numerical experiments

Description Implementation using MATLAB

⋄ Short development cycles ⋄ Availability of SDPPack, a package solving SQL conic programs

Cross-validation methodology

1. Divide the data set into two parts : a learning set and a validation set. Use only the learning set to compute the ellipsoids.

2. Classify the learning patterns ⇒ learning error (how well the algorithm performed the separation)

3. Classify the validation patterns ⇒ testing error (how well the algorithm generalizes)

Error = % of misclassified patterns.

[figure]

\overline{Data sets}

1. Fisher’s Iris. Classify iris plants into three species (150 patterns, 4 characteristics)

2. Wisconsin Breast Cancer. Predict the benign or malignant nature of a breast tumor (683 patterns, 9 characteristics)

3. Boston Housing. Predict whether a housing value is above or below the median (596 patterns, 12 characteristics)

4. Pima Indians Diabetes. Predict whether a patient is showing signs of diabetes (768 patterns, 8 characteristics)

Sets from the Repository of Machine Learning Databases and Domain Theories maintained by the University of California at Irvine, widely used

[figure]

Experiments conducted on a standard PC computer Four methods, both with a 20% learning set and a 50% learning set.

Exploitation methods Which exploitation method is better ? Learning error Usually : one single ellipsoid strategy better, mixed strategy follows and other single ellipsoid strategy much worse Explanation : One of the two classes can have a natural ellipsoidal shape while the other can be considered as complementary Testing error Mixed ellipsoid strategy always better ⇒ use it for all other tests

[figure]

[figure]

Comparison between our methods Distinction between easy and difficult problems

1. Small problems, with a separating ellipsoid (Iris, Breast Cancer) Learning error Maximum separation ratio unbeatable, Minimum volume worst Testing error Minimum volume performs best, followed by Maximum sum of separation ratios → Clear signs of overlearning effect

2. Large problems, with no separating ellipsoid (Housing, Diabetes) Learning/testing error Maximum harmonic mean clearly wins for both cases Explanation : the other methods cannot handle the absence of a separating ellipsoid

[figure]

Comparison with other methods Comparison with LAD (Logical Analysis of Data) and best other method found in the literature

Best ellipsoidal  LAD  Best other
Training  20 %  50 %  50 %  Variable (% tr.)
Cancer  5.1 %  4.2 %  3.1 %  3.8 % (80 %)
Housing  15.8 % 12.4 %  16.0 %  16.8 % (80 %)
Diabetes  28.5 % 28.9 %  28.1 %  24.1 % (75 %)

⋄ Competitive error rates ⋄ Best results on the Housing problem, even with 20 % learning ⋄ 50 % learning not always better than 20 % learning

(⇒ overlearning) ⋄ Results with small learning set already acceptable

(⇒ quick generalization)

[figure]

Conclusions

SQL Conic optimization ⋄ Efficient interior-point methods ⋄ Model many convex problems

Pattern separation ⋄ Four separation methods ⋄ Homogeneous ellipsoid

Computational experiments ⋄ Minimum volume for easy problems ⋄ Maximum harmonic mean for difficult problems ⋄ Viable way of performing classification

[figure]

Possible future research directions

⋄ Successive separations.

Use a hierarchical method ⇒ improved accuracy ⋄ Combining ellipsoids.

This idea is twofold

1. Combine the ellipsoids from different methods ⇒ improved robustness

2. Jackknife

⇒ lower sensibility to outliers, reduced overlearning effect. ⋄ Bi-ellipsoid optimization.

Optimize both ellipsoids from the mixed strategy at the same time, maximizing a relevant criterion ⇒ improved accuracy