Classification

Machine Learning Techniques

Karthik Thiagarajan
Classification

D = {( x y
1
, 1
), ⋯ , ( xn yn
, )}
Classification

D = {( x y
1
, 1
), ⋯ , ( xn yn
, )}

yi ∈ { 0, 1 } OR yi - ∈ { 1, 1 }
Classification

D = {( x y
1
, 1
), ⋯ , ( xn yn
, )}

yi ∈ { 0, 1 } OR yi - ∈ { 1, 1 }

h Rd
: → { 0, 1 }

hx y( ) =
Classification

D = {( x y
1
, 1
), ⋯ , ( xn yn
, )}
0-1 Loss

yi ∈ { 0, 1 } OR yi - ∈ { 1, 1 }

h Rd
: → { 0, 1 } Loss( h n
) =
1
⋅ ∑i 1 h xi
n
=1
[ ( ) ≠ yi ]

hx y( ) =
Linear Classifiers
class-1
class-0

x 2

x 1
Linear Classifiers
class-1
class-0

x 2

w
x 1
Linear Classifiers
class-1
class-0

x 2

x wTx
| > 0

w
x 1

x wTx
| ⩽ 0 halfplanes
Linear Classifiers
hw x
( ) = sign wTx
wTTx
class-1

wx
1, > 0
class-0 =
0, ⩽ 0

x 2

x wTx
| > 0

w
x 1

x wTx
| ⩽ 0 halfplanes
Linear Classifiers
hw x( ) = sign wTx
wTTx
class-1

wx
1, > 0
class-0 =
0, ⩽ 0

x
H hw hw x wTx
2

sign
x wTx
= | ( ) =
linear
| > 0

w
Linear Classifiers

x 1

x wTx
| ⩽ 0 halfplanes
Linear Classifiers
hw x ( ) = sign wTx
wTTx
class-1

wx
1, > 0
class-0 =
0, ⩽ 0

x
H hw hw x wTx
2

sign
x wTx
= | ( ) =
linear
| > 0

w
Linear Classifiers

x 1

min

hH
1
∑ ⋅
n
n i 1 h xi [ ( ) ≠ yi ]

x wTx
∈ linear =1

| ⩽ 0 halfplanes
Classification as Regression

x 2

w
x 1
Classification as Regression

w *

w
= arg min
1
∑
n i w
⋅
n
T xi - yi
=1
2

x 2
hw x * ( ) = sign w Tx*

w
x 1
Classification as Regression

w *

w
= arg min
1
∑
n i w
⋅
n
T xi - yi
=1
2

x 2
hw x * ( ) = sign w Tx*

w • Sensitive to outliers

x 1
Classification as Regression

w *

w
= arg min
1
∑
n i w
⋅
n
T xi - yi
=1
2

x 2
hw x * ( ) = sign w Tx*

w • Sensitive to outliers
• Natural ordering is absent

x 1
– example: spam, work, family