ppt ta 5105100062 -...

METODE REGULARISASI

Metode Regularisasi melibatkan penambahan informasi untukmengatasi ill-posed problem. Dalam statistik dan machine learning,regularisasi digunakan untuk mencegah overfitting.

Idenya adalah dengan menambahkan nilai konstan ke elemendiagonal dari scatter matrik total, dimana yang sering disebut sebagairegularisasi parameter. Regularisasi akan menstabilkan estimasi matrikkovarian sehingga dapat memperbaiki performa klasifikasi.

09 Februari 2010 Tugas Akhir – CI1599 31

DASAR TEORI

Kembali

METODE KERNEL

Metode Kernel merupakan suatu teknik memetakan dataset dari ruanginput (input space) ke ruang fitur (feature space) yang memilikidimensi tinggi atau bahkan dimensi tak terbatas (Hilbert space) denganpemetaan nonlinier . Sehingga, komponen-komponen nonlinier dapatdiekstrak menggunakan algoritma linier di ruang fitur.

𝜙

• Pemetaan dari ruang input ke ruang fitur dinotasikan dengan :(3)


DASAR TEORI

)(:

METODE KERNEL (2)

Dalam proses training untuk mendapatkan vektor diskriminanbergantung pada inner product dari data yang sudah dipetakan padaruang baru yang berdimensi lebih tinggi. Karena ruang fitur yangsangat tinggi tersebut, maka pemetaan sangat sulit diketahui dansangat sulit dipahami secara mudah, sehingga perhitungan innerproduct tersebut dapat digantikan dengan fungsi kernel yangmendefinisikan 𝜙 secara implisit. Disebut dengan kernel trick.

(4)


DASAR TEORI

)(),(),( jiji xxxx

Kembali

FUNGSI KERNEL GAUSSIAN

Kernel Gaussian merupakan salah satu fungsi kernel yang paling seringdigunakan dalam aplikasi dikarenakan kernel Gaussian lebih dapatmempertahankan topology preservation. Berikut merupakan formulaKernel Gaussian :

(5)


DASAR TEORI

Kembali

)2

exp(),(2

2

ji

ji

xxxxK

LINEAR DISCRIMINANT ANALYSIS (LDA)

Linear Discriminant Analysis (LDA) adalah metode untuk mereduksidimensi data. LDA memproyeksikan data dimensi tinggi ke subruangdimensi yang lebih rendah dengan memaksimalkan pemisahan datadari kelas-kelas yang berbeda dan meminimalkan penyebaran data darikelas yang sama secara bersamaan, sehingga mencapai diskriminasimaksimal pada subruang dimensi yang telah direduksi.

Solusi LDA adalah dengan menyelesaikan persamaan berikut

(6)

Menyelesaikan persamaan diatas, ekivalen dengan menyelesaikanpersamaan berikut

(7)


DASAR TEORI

L

b

L

wG

SStraceG1

maxarg

iibw yySS 1

Kembali

UNCORRELATED LINEAR DISCRIMINANT ANALYSIS (ULDA)

• Uncorrelated Linear Discriminant Analysis mengekstrak fitur-fitur yangtidak berkorelasi di ruang dimensi tereduksi, sehingga mengurangiredundansi di ruang dimensi tereduksi.

• Solusi ULDA dapat diselesaikan dengan persamaan berikut.

(8)

• Dari persamaan diatas, solusi ULDA dilakukan dengan mencari vektordiskriminan pertama dengan memaksimalkan Fisher Criterion.Ekivalen dengan menyelesaikan generalized eigenvalue problemberikut.

(9)


DASAR TEORI

GSGGSGtraceG b

T

t

T

G

maxarg

1g

itiib gSgS


• Anggap telah didapatkan. Kemudian dilanjutkandengan mencari vektor diskriminan yang tidak saling berkorelasi ( ).Vektor diskriminan ini dicari dengan memaksimalkan Fisher Criterion,dengan batasan .

• Vektor diskriminan ini didapatkan dengan memecahkan generalizedeigenvalue problem berikut.

(10)

dimana,

(11)

(12)

(13)


DASAR TEORI

)1(,...,, 21 mggg m

1mg

01 it

T

m gSg ),...2,1( ri

itiib gSgPS

111 wt

T

twt

T

t SDSDSSDSDSIP

TmgggD ...21

1,...,1,1diagI


• Sehingga, matrik diskriminan ULDA adalah gabungan antara vektordiskriminan pertama dan vektor diskriminan yang tidak salingberkorelasi.


DASAR TEORI

KERNEL UNCORRELATED DISCRIMINANT ANALYSIS (KUDA)

• Kernel Uncorrelated Discriminant Analysis merupakan perpanjangandari Uncorrelated Linear Discriminant Analysis atau ULDA, dimanaULDA bersifat linier, sedangkan KUDA bersifat nonlinier.

• Penerapan teori Kernel Uncorrelated Discriminant Analysis sebenarnyatidak jauh berbeda dengan penerapan Uncorrelated Linear DiscriminantAnalysis, bedanya pada penambahan operasi kernel sebelumperhitungan scatter between dan total scatter matrix .

• Notasi scatter between dan total scatter matrix menjadi dan

karena memuat hasil operasi kernel yang telah dibangkitkan.Persamaan untuk solusi ULDA yang baru setelah penggunaan fungsikernel adalah

(14)


DASAR TEORI

K

tS

K

bS

K

b

TK

t

T SBBSBtraceB maxarg

KERNEL UNCORRELATED DISCRIMINANT ANALYSIS (KUDA)

• Vektor diskriminan pertama pada KUDA, , merupakan eigenvectoryang memaksimalkan Fisher Criterion. Ekivalen dengan eigenvaluemaksimum pada generalized eigenvalue problem berikut.

(15)

• Kemudian dicari vektor diskriminan selanjutnya yang tidak salingberkorelasi, yaitu dengan memaksimalkan Fisher Criterion. Ekivalendengan menyelesaikan generalized eigenvalue problem berikut.

(16)

dimana,

(17)

(18)

(19)


DASAR TEORI

1

i

K

Tii

K

B SS

i

K

Tii

K

B SPS

111 K

W

K

T

TK

T

K

W

K

T

TK

T SDSDSSDSDSIP

TmgggD ...21

1,...,1,1diagI Kembali

SINGULAR VALUE DECOMPOSITION (SVD)

• SVD merupakan salah satu alat matematis yang digunakan untukmempresentasikan sebuah matrik dan mampu melakukan berbagaianalisis dan komputasi matrik.

• Matrik yang direpresentasikan menggunakan SVD akan diuraikanmenjadi 3 (tiga) komponen matrik, yaitu U(left singular matrix),Λ(singular value matrix), V(right singular matrix).

• SVD dapat didefinisikan sebagai berikut:

(20)

dimana,

A = matrik asal (original matrix) berukuran MXN

U = left singular matrix berukuran MXM

S = singular value matrix berukuran MXN

V = right singular matrix berukuran NXN


DASAR TEORI

TUSVA

Kembali

GENERALIZED EIGENVALUE PROBLEM

• Dengan banyaknya aplikasi dari eigenvalue, meningkatkan ketertarikandalam permasalahan generalized eigenvalues dengan bentuk sebagaiberikut,

(21)

dimana A dan B merupakan matriks mm. Himpunan dari matriks A –B dikenal dengan bentuk matrix pencil.

• Eigenvalue dari matrix pencil yang dinotasikan sebagai (A, B)merupakan nilai yang didapatkan dari persamaan berikut ini,

• Untuk eigenvalue dari pencil (A, B), sebuah vektor u 0 sehingga

(22)

Persamaan di atas dapat disebut sebagai eigenvector dari A – B. jikaB bukan bentuk tunggal, maka akan ada n eigenvalue dan (A, B) =(B-1 A).


DASAR TEORI

BxAx

0)det( IA

BuAu

MATRIK TERPUSAT

• Matriks Terpusat adalah matriks simetris dan idempotent, dimana jikadikalikan dengan sebuah vektor maka akan mempunyai efek yangsama dengan men-subtract rata-rata (mean) komponen dari vektoruntuk setiap komponen.

• Matriks Terpusat (Centered Matrix) didefinisikan sebagai berikut :

(23)

(24)

(25)

dimana dan adalah vektor satu.


DASAR TEORI

Tk

kk

T

w ecXecXn

H ,...,1 1

11

ccnccnn

H kb 111 ,...,1

T

t ceXn

H 1

inie ne Kembali

MATRIK SCATTER

• Scatter matrix merupakan ilmu statistika yang digunakan untukmembuat perkiraan nilai covariance matrix dari distribusi normalmultivariate

• Terdapat 3 macam scatter matrix, yaitu : within-class scatter matrix ,between-class scatter matrix , dan total scatter matrix .

(26)

(27)

(28)

• Total scatter matrix dapat didefinisikan dengan


DASAR TEORI

Kembali

k

i Xx

T

iiw

i

cxcxn

S1

))((1

k

i

T

iiib ccccnn

S1

))((1

n

i

T

iit cxcxn

S1

))((1

wbt SSS

NOTASI

• , : elemen data training

• σ : parameter fungsi kernel

• : matrik kernel terpusat

• : jumlah sampel kelas ke-j

• : kelas ke-j

• : jumlah seluruh sampel

• : matrik kernel terpusat tereduksi

• r : rank KTraining

• : matrik kernel training

• : left singular matrix

• : singular value matrix

• : right singular matrik

• : matrik kernel tereduksi

• : nonzero eigenvalue yang telahdiregularisasi

• σ : parameter regularisasi

• : Fisher criterion


DASAR TEORI

ix jx

ijbK

bH

jn

jN

n

KTraining

1U

r

TU1

LbH ,

i

LK

~

J

kembali

NOTASI

• : within-class scatter matrix

• : Between-class scatter matrix

• : total scatter matrix

• : between-class scatter matrixmatrik kernel

• : total scatter matrix matrik kernel

• : generalized eigenvector

• : generalized eigenvalue

• : matrik satuan

• : rata-rata kelas ke-i

• : rata-rata total

• G : matrik diskriminan


DASAR TEORI

K

bS

K

tS

i

i

)(ic

c

e

bS

tS

wS

kembali

KERNEL REGULARIZED DISCRIMINANT ANALYSIS (KRDA)

• Metode Kernel Regularized Discriminant Analysis merupakan metodeyang memiliki ide dasar menambahkan nilai regularisasi parameter

konstan ke elemen diagonal scatter matrik total . ( )

• Hal ini dimaksudkan untuk menstabilkan estimasi total scatter matriksehingga dapat memperbaiki performa klasifikasi.

• Oleh karena itu, performa KRDA sangat bergantung dengan nilairegularisasi parameter.

• Solusi untuk mendapatkan matrik diskriminan KRDA dapat diselesaikandengan persamaan berikut .

(1)


DASAR TEORI

K

tS 0

BSBKSBtraceB K

b

TK

t

T 1maxarg

PERHITUNGAN KRDA

• Perhitungan KRDA

Persamaan penyelesaian KRDA :

• Ekivalen dengan Fisher criteron:

• Ekivalen dengan menyelesaikan generalized eigenvalue problem


DASAR TEORI

BSBKSBtraceB K

b

TK

t

T 1maxarg

TK

t

TK

b

BKSB

BBSJ

iii

K

b

K

t SKS

PERHITUNGAN KRDA

• Meregularisasikan total scatter matrik (StK)

• Dilakukan dengan mencari SVD matrik kernel KTraining (K)

dimana , , r = rank (K)

Diasumsikan bahwa U terbagi menjadi dimana dan

Sehingga jelas bahwa

Sehingga :


DASAR TEORI

TUUK

iii

K

b

K

t SKS

2KS K

t

nxnRU rxr

r R

),( 21 UU nxrRU 1

)(

2

rnnxRU

T

rr

TK

t UUUUKS 1

2

1

2 )(

K

b

T

rr

K

b

K

t SUUSKS 1

12

1

PERHITUNGAN KRDA

• Mencari eigenvector atau matrik diskriminan KRDA dari

Dimisalkan : , maka

Selanjutnya menghitung eigenvektor dari

Diketahui matrik


DASAR TEORI

iii

K

b

K

t SKS

K

b

T

rr

K

b

K

t SUUSKS 1

12

1

rr 2~

11

1

1

12

1

~USUSUU K

b

TK

b

T

rr

TK

b

K

b

K

b HHS

11

1~USU K

b

T

PERHITUNGAN KRDA

• Perhitungan sederhana untuk menghitung eigenvektor dari

adalah :

Anggap adalah SVD dari maka

mendiagonalkan matrik sehingga kolom

membentuk eigenvektor dari


DASAR TEORI

kembali

11

1~USU K

b

T

2/1

1

2/1

1

2/12/1 ~~~~ TK

b

TK

b

T HUHU

T

bbb VU K

b

T HU1

2/1~

2/1

1

2/1

1

2/12/1

11

1 ~~~~~ TK

b

TK

b

TK

b

T HUHUUSU

2/12/1 ~~ TT

bbb

T

bbb VUVU

2/122/1 ~~ T

bbb UU

12/122/1 ~~ T

bbb UU

bU2/1~11

1~USU K

b

T bU2/1~

11

1~USU K

b

T

ppt ta 5105100062 -...

Documents