azotaemia (mg/dl)

Gulfoss fault, Iceland

Separation

Separation

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)

separa tion hype

rplane

a

x

1

+ a

2

x

2

= b

(x

’, x

’)

a

x

’ + a

x

’ > b

(x

”, x

”)

a

x

” + a

x

” < b

d’ = a

1

x

1

’ + a

2

x

2

’ – b d” = b –

a

x

1

” – a

x

2

”

d

> 0 x

∈ P”

Separation

Problem Find a separation hyperplane H which lies as far as possible from two given sets P’, P” ⊆ IR

(to be withdrawn)

Call d

the distance of H from x

∈ P’ ∪ P”

max Σ ^d

⁺ Σ ^d

xⁱ∈P’ xⁱ∈P”

d

= a

x

+ a

x

+ … + a

x

– b x

∈ P’

d

= b – a

x

– a

x

– … – a

x

x

∈ P”

d

> 0 x

∈ P’

optimal separator

a

+ a

+ … + a

= 1

Separation

Problem Find a separation hyperplane H which lies as far as possible from two given sets P’, P” ⊆ IR

(to be withdrawn)

x

a

+ x

a

+ … + x

a

– b > 0 x

∈ P’

– x

a

– x

a

– … – x

a

+ b > 0 x

∈ P”

optimal separator

a

+ a

+ … + a

= 1 max Σ ( Σ ^x

^– Σ ^x

) ^a

+ (|P”| – |P’|) b

xⁱ∈P’ xⁱ∈P”

n

k=1

Separation

39 68

Lucio

67 67

Kevin

80 59

Jean

26 80

Igino

55 58

Harry

28 47

Giulio

37 112

Fabio

47 108

Ernesto

16 98

Davide

38 80

Claudio

44 94

Bruno

41 79

Antonio

azotaemia glycaemia

name

30 85

Zeno

28 85

Walter

26 127

Vittorio

26 112

Ugo

51 64

Tito

54 102

Silvio

39 97

Ramon

32 69

Qalbi

48 60

Piero

42 99

Oreste

44 81

Nicola

32 72

Mauro

azotaemia glycaemia

name

Separation

39 68

Lucio

67 67

Kevin

80 59

Jean

26 80

Igino

55 58

Harry

28 47

Giulio

37 112

Fabio

47 108

Ernesto

16 98

Davide

38 80

Claudio

44 94

Bruno

41 79

Antonio

azotaemia glycaemia

name

30 85

Zeno

28 85

Walter

26 127

Vittorio

26 112

Ugo

51 64

Tito

54 102

Silvio

39 97

Ramon

32 69

Qalbi

48 60

Piero

42 99

Oreste

44 81

Nicola

32 72

Mauro

azotaemia glycaemia

name

Separation

68a₁ + 39a₂ – b + d_L = 0 L

67a₁ + 67a₂ – b – d_K = 0 K

59a₁ + 80a₂ – b – d_J = 0 J

80a₁ + 26a₂ – b + d_I = 0 I

58a₁ + 55a₂ – b + d_H = 0 H

47a₁ + 28a₂ – b + d_G = 0 G

112a₁ + 37a₂ – b – d_F = 0 F

108a₁ + 47a₂ – b – d_E = 0 E

98a₁ + 16a₂ – b – d_D = 0 D

80a₁ + 38a₂ – b – d_C = 0 C

94a₁ + 44a₂ – b – d_B = 0 B

79a₁ + 41a₂ – b – d_A = 0 A

d_A + d_B + d_C + d_E + … max

85a₁ + 30a₂ – b – d_Z = 0 Z

85a₁ + 28a₂ – b – d_W= 0 W

127a₁ + 26a₂ – b – d_V = 0 V

112a₁ + 26a₂ – b – d_U= 0 U

64a₁ + 51a₂ – b + d_T = 0 T

102a₁ + 54a₂ – b – d_S = 0 S

97a₁ + 39a₂ – b – d_R = 0 R

69a₁ + 32a₂ – b + d_Q = 0 Q

60a₁ + 48a₂ – b + d_P = 0 P

99a₁ + 42a₂ – b – d_O= 0 O

81a₁ + 44a₂ – b – d_N= 0 N

72a₁ + 32a₂ – b + d_M = 0 M

… + d_T + d_U + d_V + d_W+ d_Z

a₁ + a₂ = 1 d_A, …, d_G, …, d_Z > 0

Separation

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)

sapara tion hype

rplane

18 x

1

+ 7 x

2

= 1 62 2

But what if a separation hyperplane does not exists?

Separation

39 68

Lucio

67 67

Kevin

80 59

Jean

26 80

Igino

55 58

Harry

28 47

Giulio

37 112

Fabio

47 108

Ernesto

16 98

Davide

38 80

Claudio

44 94

Bruno

41 79

Antonio

azotaemia glycaemia

name

30 85

Zeno

28 85

Walter

26 127

Vittorio

26 112

Ugo

51 64

Tito

54 102

Silvio

39 97

Ramon

32 69

Qalbi

48 60

Piero

42 99

Oreste

44 81

Nicola

32 72

Mauro

azotaemia glycaemia

name

Separation

68a₁ + 39a₂ – b + d_L = 0 L

67a₁ + 67a₂ – b – d_K = 0 K

59a₁ + 80a₂ – b – d_J = 0 J

80a₁ + 26a₂ – b + d_I = 0 I

58a₁ + 55a₂ – b + d_H = 0 H

47a₁ + 28a₂ – b + d_G = 0 G

112a₁ + 37a₂ – b – d_F = 0 F

108a₁ + 47a₂ – b – d_E = 0 E

98a₁ + 16a₂ – b – d_D = 0 D

80a₁ + 38a₂ – b – d_C = 0 C

94a₁ + 44a₂ – b – d_B = 0 B

79a₁ + 41a₂ – b – d_A = 0 A

d_A + d_B + d_C + d_E + … max

85a₁ + 30a₂ – b – d_Z = 0 Z

85a₁ + 28a₂ – b – d_W = 0 W

127a₁ + 26a₂ – b – d_V = 0 V

112a₁ + 26a₂ – b – d_U= 0 U

64a₁ + 51a₂ – b + d_T = 0 T

102a₁ + 54a₂ – b – d_S = 0 S

97a₁ + 39a₂ – b – d_R = 0 R

69a₁ + 32a₂ – b + d_Q = 0 Q

60a₁ + 48a₂ – b + d_P = 0 P

99a₁ + 42a₂ – b – d_O = 0 O

81a₁ + 44a₂ – b – d_N = 0 N

72a₁ + 32a₂ – b + d_M = 0 M

… + d_T + d_U + d_V + d_W+ d_Z

a₁ + a₂ = 1 d_A, …, d_G, …, d_Z > 0

infea

sible

Separation

Problem Find a hyperplane H whose inequalities are violated by the least possible number of points in P’, P” ⊆ IR

Let y

∈ {0, 1} be a variable equal to 1 if and only if x

violates the inequality

min Σ ^y

⁺ Σ ^y

xⁱ∈P’ xⁱ∈P”

a

x

+ a

x

+ … + a

x

– b + u y

> 0 x

∈ P’

b – a

x

– a

x

– … – a

x

+ u y

> 0 x

∈ P”

y

∈ {0, 1} x

∈ P’ ∪ P”

optimal quasi-separator

a

+ a

+ … + a

= 1

Separation

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)