[figure]

Pattern separation via ellipsoids and conic programming

François Glineur

Faculté Polytechnique de Mons

9th Belgian-French-German Conference on Optimization Namur, September 7, 1998

Pattern separation via ellipsoids and conic programming

[figure]

[figure]

Objective

Machine learning

• Separation problem

• Classification

Mathematical programming

• Linear programming

• Interior-point methods

• SQL conic programming

\overline{Goal}

Solve the separation problem using SQL conic programming

\overline{How}

Use ellipsoids to perform the separation

François Glineur, FPMs  Page 2  BFG Conf9, Namur

[figure]

[figure: Outline]

Conic programming

• Background

• SQL conic programming

• Modelling

Pattern separation

• Problem definition

• Describing an ellipsoid

• Four separation algorithms

• Exploitation

Computational experiments

• Comparison between our algorithms • Comparison with other methods

Conclusions

François Glineur, FPMs  Page 3  BFG Conf9, Namur

[figure]

[figure]

Conic programming

Background

Operations research : Model ⇒ best decision Optimization : Minimize function of n variables Mathematical programming : Add constraints General mathematical program is too difficult : no algorithm with performance guarantee, existence of local minima Linear programming : special case, very efficient algorithms, no local minima Convex programming : Generalize linear programming while keeping its good properties

• No local minima

• Efficient interior-point methods

• Model much more problems than LP

François Glineur, FPMs  Page 4  BFG Conf9, Namur

[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 (damped Newton steps) where ν depends only on the structure of C (Nesterov and Nemirovsky).

\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 not attained, etc.)

François Glineur, FPMs  Page 5  BFG Conf9, Namur

[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 Programming)

• 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

François Glineur, FPMs  Page 6  BFG Conf9, Namur

[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.

François Glineur, FPMs  Page 7  BFG Conf9, Namur

[figure]

[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

François Glineur, FPMs  Page 8  BFG Conf9, Namur

[figure]

Formulation

Reduce the 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}

François Glineur, FPMs  Page 9  BFG Conf9, Namur

[figure]

Separation ratio

We want the best possible separation ⇒ optimize the separation ratio Pair of similar ellipsoids with the same center Separation ratio ρ ≡ ratio of sizes (ρ = 1.5 below)

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}

François Glineur, FPMs  Page 10  BFG Conf9, Namur

[figure]

Two problems

1. ρ^{2} is nonlinear ⇒ let k = ρ^{2}, maximize k 2. (x − c)^{T} E(x − c) is also nonlinear

(nonconvex) ⇒ homogeneous ellipsoid

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 Ẽ

François Glineur, FPMs  Page 11  BFG Conf9, Namur

[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. This program maximizes the separation ratio between a_{i}’s and b_{j}’s

2. Independence from the coordinate system Drawback If there is no separating ellipsoid ?

• Convex hulls and A and B intersect

• Other cases

François Glineur, FPMs  Page 12  BFG Conf9, Namur

[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 ⇒ 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 13  BFG Conf9, Namur

[figure]

François Glineur, FPMs  Page 14  BFG Conf9, Namur

[figure]

Maximum sum

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 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 Solution : Combine the ρ_{j}’s into an objective such that small values have more influence than large ones

François Glineur, FPMs  Page 15  BFG Conf9, Namur

[figure]

Minimum squared sum

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}

This is a 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

François Glineur, FPMs  Page 16  BFG Conf9, Namur

[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

François Glineur, FPMs  Page 17  BFG Conf9, Namur

[figure]

[figure]

Numerical experiments

Description

Implementation using MATLAB • Short development cycles

• Availability of SDPPack, a package solving SQL conic programs

Experiments conducted on a standard PC

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.

François Glineur, FPMs  Page 18  BFG Conf9, Namur

[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

François Glineur, FPMs  Page 19  BFG Conf9, Namur

[figure]

We tested our four methods both with a 20% learning set and a 50% learning set.

Exploitation methods

Learning error Usually : one single ellipsoid strategy better, mixed strategy follows and other single ellipsoid strategy much worse Explanation : one class has usually a natural ellipsoidal shape, the other is a complement

Testing error Mixed ellipsoid strategy always better ⇒ use it for all other tests

François Glineur, FPMs  Page 20  BFG Conf9, Namur

[figure]

Comparison between our methods

We make the 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 Overlearning effect

2. Large problems, with no separating ellipsoid (Housing, Diabetes) Learning and testing error Minimum squared sum is a clear winner Explanation : the other methods cannot handle the absence of a separating ellipsoid

François Glineur, FPMs  Page 21  BFG Conf9, Namur

[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)

François Glineur, FPMs  Page 22  BFG Conf9, Namur

[figure]

[figure]

Conclusions

SQL Conic programming

• Efficient interior-point methods

• Model many convex problems

Pattern separation

• Four separation methods

• Homogeneous ellipsoid

Computational experiments

• Minimum volume for easy problems • Minimum squared sum for difficult

problems

• Viable way of performing classification

François Glineur, FPMs  Page 23  BFG Conf9, Namur

[figure]

[figure]

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

François Glineur, FPMs  Page 24  BFG Conf9, Namur