Metode Self-supervised – Ishan Misra

Saya lanjutkan pembahasan kuliah Ishan Misra tentang Self-supervised. Pada tulisan sebelumnya telah dibahas tentang trivial solutions. Yaitu dimana sistem menghasilkan fitur yang sama untuk semua input gambar. Representasi yang dipelajari menjadi tidak dapat digunakan untuk task recognition downstream. Atau bisa dikatakan nilai fungsi encodernya menjadi konstan.

Untuk mengatasi permasalahan trivial solutions ini ada 2 metode self-supervised yang dapat digunakan yaitu:

  1. Maximize similarity
  2. Mengurangi redundancy

Untuk maximize similarity beberapa teknik yang bisa digunakan adalah:

  1. Contrastive Learning (MoCo, PIRL, SimCLR)
  2. Clustering (DeepCluster, SeLA, SwAV)
  3. Distillation (BYOL, SimSiam)

Sementara untuk redundancy reduction contohnya adalah Barlow Twins.

Untuk menguji metode SSL diatas, sebuah subset dari dataset Imagenet dataset yang memiliki 1,3 juta gambar dengan lebih dari 1000 kategori tanpa label digunakna untuk melakukan pre-train pada model Resnet-50 yang diinisialisasi secara random. Hasil pre-train akan ditransfer ke downstream task dengan 2 kemungkinan:

  1. Training sebuah klasifier linear pada fitur yg dibekukan (frozen)
  2. Finetuning keseluruhan jaringan

Contrastive Learning

Teknik ini digunakan untuk mempelajari fitur umum dari dataset tanpa label dengan mengajari model datapoin mana yang mirip dan yang mana yang berbeda.

Dengan cara ini kita dapat melatih model untuk mempelajari data tanpa membutuhkan anotasi atau lebel (Self-Supervised learning)

Beberapa teknik contrastive learning diantaranya:

  1. Pretext-Invariant Representation Learning (PIRL)
  2. SimCLR
  3. MoCo

Contohnya kita punya sekelompok gambar yang berhubungan (related) dan unraleted contohnya biru dengan biru tua, hijau dengan hijau muda dst

Kemudian gambar-gambar tersebut dimasukan ke jaringan siamese dan dihitung fitur imagenya (embeddingnya). Embedding adalah mapping dari variabel diskret/kategorikal ke vektor kontinu. Neural network embeddings berguna karena dapat mengurangai dimensi dari variabel kategorikal dan dapat merepresentasikan kategori secara berarti pada transformed space.

Kemudian dari loss function terlihat bahwa gambar yang berhubungan memiliki nilai loss yang lebih kecil dibandingkan gambar yang tidak berhubungan.

PIRL (Pretext Invariant Representation Learning)

Sebuah Image I dan augmentasinya I^t dimasukan ke jaringan siamese dan dihitung contrastive learning loss sehingga jaringan menjadi invariant terhadap pretext task. Tujuannya adalah untuk mencapai kemiripan yang tinggi pada image dan fitur patch pada gambar yang sama. Dan kemiripan yang rendah pada fitur dari image random lainnya. Pretext task dari PIRL mencoba mencapai invariance terhadap data augmentasi, tidak untuk memprediksi data augmentasi. Image augmentasi dibuat dengan pretext task seperti jigsaw/rotasi.

Loss functionnya membandingkan image fetaure dan patch feature. Dimana loss functionnya lebih kecil pada gambar yang sama, dibandingkan loss function pada gambar yang random.

Sampai disini dulu, insyaallah besok akan saya lanjutkan penjelasan tentang metoda PILR

https://towardsdatascience.com/understanding-contrastive-learning-d5b19fd96607

tentang embedding

https://towardsdatascience.com/neural-network-embeddings-explained-4d028e6f0526

Self Supervised Learning pada Komputer Vision – Ishan Misra

Saya baru dengerin kuliah Ishan Misra tentang Self-Supervised learning pada komputer vision. Menurut dia fokus penelitian komputer vision saat ini adalah bagaimana belajar representasi visual dari supervised data dan menggunakan representasi ini (weight modelnya) sebagai inisialisasi untuk task lainnya yang memiliki data berlabel yang sedikit. Proses memberi label pada data itu mahal, contohnya dataset Imagenet memiliki 14 juta gambar dengan 22 ribu kategori. Proses pemberian labelnya membutuhkan 22 tahun (human years)

Ada 2 teknik yang sedang berkembang untuk menangani kesulitan pemberian label ini, yaitu dengan:

  1. Semi-automatic process : misalnya dari hastag gambar, atau dari info GPS
  2. Self-supervised learning: menggunakan data dan dipelajari data, atau dengan prediksi bagian data dari bagian lainnya.

Pada komputer vision ada yang disebut pretext task. Pretext task ini adalah task self-supervised learning yang digunakan untuk learning visual representation. Tujuannya representasi yang dipelajari atau weight model yang diperoleh dapat digunakan untuk downstream task. Pretext task biasanya dilakukan pada sebuah properti yang ada pada dataset. Sementara downstream task yang dimaksud adalah task yang dilakukan machine learning seperti klasifikasi gambar atau deteksi obyek.

Contoh pretext task pada image:

  1. Prediksi posisi relatif sebuah patch pada gambar
  2. Prediksi tipe permutasi sebuah patch gambar, misalnya pada puzzle
  3. Prediksi jenis rotasi yang terjadi pada sebuah gambar

Pada gambar diatas contohnya ada dua patch pada gambar kucing, kotak biru diketahui posisinya dan kotak merah yang belum diketahui. Kemudian akan dilakukan prediksi posisi kotak hitam ada dimana. Ada 8 kemungkinan posisi dari kotak merah, sehingga menjadi klasifikasi 8 kelas menggunakan dua jaringan CNN dengan masing2 memiliki input kotak biru dan merah.

Pada gambar diatas ada 9 patch gambar, yang posisinya termutasi dengan salah satu dari permutasi N. Kemudian mesin akan melakukan klasifikasi N-kelas dengan N << 9!

Pada gambar diatas mesin mendapat input sebuah gambar yang telah dirotasi sebanyak 0, 90, 180 dan 270 derajat. Mesin kemudian diminta melakukan klasifikasi 4 kelas untuk menentukan gambar tersebut termasuk dalam rotasi yang mana.

Namun ternyata ada mismatch antara pretext task dengan apa yang diinginkan pada task sebenarnya (transfer task). Sehingga apa yang diselesaikan pada saat pretext task tidak sesuai dengan final task.

Contohnya pada gambar diatas, dilakukan pretraining dengan model jigsaw di bagian kiri. Kemudian hasil representasinya digunakan untuk transfer task di sebelah kanan, misalnya untuk deteksi obyek atau klasifikasi gambar. Hasilnya bisa dilihat pada gambar berikut ini:

Terlihat dengan jaringan resnet5 akurasinya terus meningkat pada setiap layer, mulai dari convolutional 1, resnet2, 3 dan 4. Namun terjadi penurunan pada layer resnet 5. Karena model pada layer tersebut tidak berhasil melakukan generalisasi. Model tersebut hanya bagus untuk task jigsaw. Pada kasus ini, gak gak ngaruh berapa layer yg digunakan, polanya akan sama, yaitu ada penurunan performa di layer terakhir, karena dia spesifik ke task tertentu. Jadi walaupun misalnya layer 5 kita buang, hasilnya juga tidak akan memuaskan.

Lantas apa yang kurang dari pretext task (general proxy task) ini?

Sebelumnya kita harus mengetahui bahwa fitur pre-training harus memenuhi dua karakteristik dasar yaitu:

  1. Harus dapat merepresentasikan bagaimana gambar-gambar berhubungan (relate) satu sama lain
  2. Robust (kuat) terhadap faktor nuisance atau invariance. Maksudnya mesin harus mengenali obyek yang sama walaupun memiliki lokasi yang berbeda pada gambar, atau memiliki pencahayaan yang berbeda, atau memiliki warna yang berbeda.

Salah satu metode yang popular untuk self-supervised learning adalah untuk mempeljari fitur yang robust terhadap augmentasi data. Contohnya pada gambar rusa berikut ini:

Pada gambar diatas terlihat ada sebuah gambar rusa, yang telah diaugmentasi. Ada yang posisinya diubah, ada yang warnanya diubah bahkan ada yang resolusinya berubah. Sistem yang dibangun harus dapat mengenali bahwa gambar-gambar tersebut adalah rusa. Dengan berbagai variasinya.

Pada gambar diatas, gambar rusa dgn berbagai teknik data augmentasi, di masukin ke encoder (assigning method), kemudian dihitung kesamaannya (maximize similarity), dicari nilai gradientnya dan dilakukan backpropagation. Pengukuran akan dilakukan menggunakan loss function (bisa dengan max cosine similarity, minimazi equal distance, dll). Jaringan akan mempelajari representasi dan menghasilkan representasi konstan untuk kedua augmentasi tersebut.

Inilah yang kemudian disebut sebagai trivial solution, dimana sistem robust terhadap invariance, namun menghasilkan fitur yang sama untuk semua input gambar. Sistem ini tidak dapat menangkap fitur yang mengenali bagaimana satu gambar berhubungan (relate) dengan gambar lainnya. Representasi ini menjadi tidak dapat digunakan untuk task downstream recognition.

Masih panjang kuliahnya, sementara sampai disini dulu, besok akan saya lanjutkan pembahasannya. Materinya bisa dilihat pada link berikut:

https://atcold.github.io/NYU-DLSP21/en/week10/10-1/

slidenya ada disini:

https://drive.google.com/file/d/1BQlWMVesOcioW69RCKWCjp6280Q42W9q/edit

Videonya:

video

Semoga Bermanfaat!

Hidden Markov Model

Hari ini saya lagi belajar tentang Hidden markov model (HMM). HMM ini adalah pemodelan sistem statistik dimana ada proses markov dan proses yang tidak dapat diamati (unobserved). Jelasin teorinya agak ribet, tapi ada video bagus berikut ini yang ngejelasin HMM dengan mudah:

Contohnya di video itu ada Alice dan Bob, mereka berdua berada di kota yang berbeda (LDR ceritanya). Misalnya Alice di Jakarta, Bob di Bandung. Trus mereka suka telpon-telponan. Si Bob sering cerita hari ini dia lagi hepi atau lagi sedih (grumpy). Nah dari cerita si Bob itu Alice coba nebak cuaca di Bandung pada saat itu kayak gimana. Kondisi cuaca ini yang disebut hidden state. Caranya si alice bikin dulu model markovnya. Kemudian dari model markov itu dia bisa memprediksi probabilitas cuacanya.

Model HMM memiliki beberapa komponen: ada alphabet, kumpulan state, probabilitas transisi antara state, start probability dan emission probability, seperti di slide berikut:

Terus HMM ini disebut juga memoryless

Dengan HMM kita bisa ngitung 3 jenis perhitungan berikut: decoding, evaluation dan learning:

Untuk persoalan decoding digunakan algoritma Viterbi. Persoalan backward dengan algoritma backward. Sementara untuk persoalan learning bisa menggunakan algoritma baum-welch. Sampai disini dulu semoga bermanfaat!

Decision Tree – Overfitting

Saya lanjutkan bahasan tentang Decision Tree . Salah satu kelemahan Decision Tree (DT) adalah Overfitting. Contoh overfitting misalnya pada kasus ada noise (data salah), kemudian dibentuk pohon yang mengakomodasi data ini. Pohon ini cenderung membesar. Jadi tree ini dikatakan terlalu ditune untuk mengakomodasi data training tertentu.

error train (h) adalah error tree pada saat training. Sementara error train (h’) error training pada hipotesis lain. Error pada train misalnya terjadi karena datanya sangat besar dan kompleks. Error d(h) adalah true error (eror pada tes data), misalnya error pada data yang besar sekali.

Untuk mencegah overfitting:

  1. Berhenti ketika split data tidak signifikan secara statistik
  2. Atau terus menumbuhkan pohon kemudian melakukan post pruning, atau dipotong daunnya secara selektif hingga performa tes validasi membaik.

Bagaimana memilih pohon yang baik?

  1. Mengukur performa data training
  2. Mengukur performa menggunakan dataset validasi yang terpisah (banyak digunakan)
  3. Menggunakan MDL (minimum disruption length) atau minimize

     size(tree) + size (misclassification(tree))

Pada metode 2, kita bisa membagi dataset jadi 3, data training, tes dan validasi. Pada saat training diukur performanya secara bertahap, mulai dari 1 simpul 2 simpul dan seterusnya. Pada saat tree mulai terbentuk, kemudian dilakukan pengujian dengan data validasi. Disini diperhatikan grafik perform tree. Biasanya performanya akan meningkat ketika simpul2nya ditambah. Namun akan ada satu titik dimana performanya akan menurut. Nah pada saat inilah terjadi overfitting, dan sebaiknya pada saat ini dihentikan penambahan simpulnya.

Sementara pada teknik MDL diukur ukuran tree dan ukuran kesalahan klasifikasinya (misclassification). Pada MDL ini dicari ukuran tree yang kecil namun kesalahannya juga kecil. Titik ini yang disebut optimal. Karena bisa saja ukuran tree nya membesar dan error nya mengecil.

Teknik lainnya adalah Pruning (reduced-error pruning). Disini pohon ditumbuhkan dulu sampai penuh. Teknik ini menggunakan data validasi juga. Kemudian dilakukan pemotongan simpul, kemudian diuji performanya dengan data validasi. Bila performanya meningkat, kemudian lakukan lagi pemotongan simpul berikutnya dan diuji lagi performanya dengan data validasi. Proses ini dilakukan berulang-ulang hingga didapat nilai performa yang terbaik dengan tree terkecil. Metode pruning ini bisa meningkatkan performa pada data tes.

Bagaimana bila datanya sedikit? bisa digunakan juga metode cross-validation.

Sampai disini dulu. Semoga Bermanfaat!

Wolfram – New Kind of Science

Hari ini saya baru baca buku Stephen Wolfram – New Kind of Science. Wolfram ini ahli fisika, komputer dan matematika. Jadi dia berkesimpulan bahwa perkembangan komputer dan pemrograman ini didukung oleh perkembangan matematika. Namun pada kenyataannya di dunia banyak hal yang terlalu kompleks untuk dijelaskan dengan rumus matematika. Misalnya bentuk pohon, bagaimana kita bisa menjelaskan bermacam-macam bentuk pohon dengan rumus matematika yang ada. Atau bentuk kristal salju yang bermacam-macam. Komputer bisa saja membuat program untuk menghitung bentuk pohon maupun kristal salju. Namun membutuhkan algoritma pemrograman yang panjang dan kompleks.

Dia mengusulkan perlu pendekatan baru untuk menjelaskan berbagai hal kompleks tersebut. Caranya dengan membuat sebuah program sederhana yang kemudian bisa berkembang menghasilkan berbagai bentuk yang kompleks. Menurut dia penemuan ini bisa membuat revolusi baru dalam ilmu fisika, kimia, biologi dan bidang lainnya.

Contohnya adalah dia menggunakan celular automata yang dia sebut untuk mengembangkan bentuk yang sangat kompleks seperti pada gambar berikut:

Bukunya bisa diakses secara daring pada tautan berikut:

https://www.wolframscience.com/nks/

Sedikit penjelasan tentang buku ini bisa dilihat disini:

https://writings.stephenwolfram.com/2017/05/a-new-kind-of-science-a-15-year-view/

https://en.wikipedia.org/wiki/A_New_Kind_of_Science

Tentang Stephen Wolfram:

https://en.wikipedia.org/wiki/Stephen_Wolfram

Video penjelasan wolfram tentang teorinya bisa dilihat disini:

Video kuliah umumnya di kampus university of california bisa dilihat disini:

Decision Tree-2

Saya lanjutkan pembahasan tentang Decision Tree (DT). Tahapan yang dilakukan adalah dari dataset yang telah memiliki label dilakukan training yang menghasilkan model classifier. Model ini kemudian digunakan untuk melakukan prediksi terhadap instance yang belum memiliki label.

Beberapa pertimbangan kapan menggunakan algoritma DT:

  • Instance dapat dideskripsikan sebagai pasangan atribut dan nilai
  • Fungsi target memiliki nilai diskret
  • Diperlukan Hipotesisnya yang disjunctive (tidak banyak keterhubungan)
  • Bila training datanya ada noise atau ada data yang hilang

Contoh

Diagnosa medis, diagnosa alat, analisa resiko kredit, pemodelan kecenderungan penjadwalan

Algoritma DT untuk memilih main loop

  1. Pilih A: Atribut terbaik yang jadi node
  2. Tentukan A sebagai atribut decision pada node
  3. Pada setiap nilai A, buat turunan (descendant) dari node
  4. Urutkan contoh data training ke daun (leaf node)
  5. Bila contoh data training sudah terklasifikasi dengan baik, maka berhenti, bila belum ulangi lagi dengan node daun baru

Maksud terklasifikasi dengan baik, misalnya datanya tidak tercampur yang positif dengan negatif (homogen)

Nilai atribut akan digunakan utnuk memilah-milah dataset. Bagaimana cara untuk memilih atribut terbaik? Beberapa caranya adalah:

  1. Random: pilih atribut secara acak
  2. Least value: Atribut dengan memiliki kemungkinan nilai yang paling sedikit
  3. Most Value: atribut yang memiliki kemungkinan nilai paling banyak
  4. Max Gain: atribut yang memiliki information gain terbesar

Metode pemilihan dengan max Gain adalah yang banyak digunakan contohnya algoritma ID3.

Idealnya atribut yang baik dapat langsung memisahkan sampel menjadi menjadi bagian yang semuanya positif dan semuanya negatif (homogen). Pohon diusahakan seringkas mungkin tapi mampu mengklasifikasikan dataset dengan baik.

Entropi adalah mengukur tingkat ketidakmurnian dalam satu grup. Rumusnya adalah:

dengan S adalah sampel dari data training,

p adalah jumlah sampel positif dalam S

n adalah jumlah sampel negatif dalam S

Rumus umumnya entropi adalah :

Information Gain menjelaskan seberapa penting atribut dari fitur vektor. Rumus Information gain dari X dan Y adalah:

Information Gain adalah mutual information dari atribut A dan variabel target Y.

Gain (S,A) adalah besarnya penurunan (reduksi) entropi setelah sampel dipilah-pilah berdasarkan nilai dari Atribut A tersebut

Atribut yang dipilih adalah yang memiliki nilai Gain paling besar. Kelemahan Information Gain adalah cenderung memilih atribut yang jumlah nilai atributnya lebih banyak dan memotong menjadi subset yang lebih kecil. Untuk mengatasi masalah ini bisa digunakan metode normalisasi dengan Quinlan Gain Ratio.

ID3 melakukan pencarian heuristik pada space hipotesis. Pencarian berhenti pada tree terkecil yang dapat diterima, berdasarkan prinsip occam razor. Occam razor cenderung memilih hipotesis yang sederhana yang bisa menjelaskan fenomena pada data.

Proses pencarian hipotesis

  1. Ruang Hipotesis decision tree lengkap (fungsi target pasti ada)
  2. Hanya memilih satu hipotesis
  3. Proses pencarian hipotesis tidak melakukan backtracking
  4. Proses pencarian hipotesis berbasis statistik (tahan terhadap noise atau labelnya salah)
  5. Algoritma pencarian cenderung untuk mencari pohon yang pendek (inductive bias)

Pohon yang baik adalah pohon yang mampu melakukan generalisasi dengan baik. Backtracking itu balik lagi. Didapatkan lokal optima.

Sampai disini dulu. Semoga Bermanfaat!

Decision Tree

Hari ini saya belajar tentang Decision Tree (DT). DT ini bisa dibilang salah satu algoritma klasik pada machine learning. DT ini memiliki masalah overfitting. Yaitu pada saat training performanya bagus, namun pada saat test performanya jelek. Hal ini bisa jadi karena dia kehilangan kemampuan melakukan generalisasi, karena sangat ditune pada training datanya.

Secara keseluruhan Machine learning adalah studi terhadap algoritma untuk meningkatkan performa P, pada beberapa task T berdasarkan pengalaman E: (P,T,E).

Untuk mendapatkan fungsi yang akan kita pelajari, kita memiliki :

  • sekumpulan instance X (ruang input/dataset),
  • ada fungsi target yang kita tidak ketahui f:X–>Y
  • kumpulan hipotesis H={ h | h : X –> Y} (calon solusi)

Input sistem adalah pasangan

dari tipe fungsi target f

Outputnya adalah hipotesis h yang merupakan bagian dari H, yang paling mendekati fungsi target f

dari slide tom mitchell, machine learning

Contohnya pada gambar diatas kolom-kolomnya (outlook, temperature, humidity dan wind) adalah fitur dari Xi. Baris-barisnya menunjukan instance label <xi, yi>. Label kelasnya pada tabel ini adalah kolom berwarna biru yang menunjukan yes dan no.

Contoh decision tree dari tabel diatas F:<Outlook, Humidity, Wind, Temp> –> play tennis

Setiap internal node menyatakan atribut tes Xi. Node pada gambar diatas berbentuk kotak, yaitu outlook, Humidity, dan wind.

Setiap cabang dari sebuah node menunjukan nilai dari sebuah node Xi. Contoh cabang pada gambar diatas ada sunny, overcast dan rain.

Setiap daun (leaf node) adalah hasil prediksinya (yes dan no) atau bisa disebut juga keputusan.

Ada banyak kemungkinan pohon, namun yang dicari adalah yang optimal, sependek mungkin. Kalau ada atribut yang tidak relevan, bisa saja dia hilang dari pohon DT.

Pohon ini kemudian digunakan untuk prediksi kelas dari sebuah input. Misalnya kita punya input berikut: <outlook=sunny, temperature=hot, humidity=high, wind=weak> . Bila kita masukan input tersebut ke pohon, maka akan mengikuti jalur keputusan outlook=sunny, humidity= high berarti keputusannya adalah playtennis=no. Dari contoh input ini temperature dan wind menjadi atribut yang tidak relevan dan tidak digunakan.

Bila datanya berupa numerik atau kontinyu, digunakan threshold atau ambang batas sebagai fitur. Misalnya untuk humidity high dan normal bisa diganti threshold >75% dan <75%. Atau bisa juga dikatakan data kontinu diubah menjadi data kategorikal. Sampai disini dulu. InsyaAllah besok akan saya lanjutkan dengan bahasan decision tree learning

Referensi:

Mitchell, Tom. “Machine learning.” (1997): 870-877.

Bayes Net

Bayes Net sering disebut sebagai model-model grafik. Ide utamanya adalah menggunakan asumsi conditional independence. Prinsip ini sudah digunakan juga di Naive Bayes (NB). Manfaatnya adalah membuat perhitungan probabilitas menjadi sederhana. Dengan NB kita hanya perlu 2n+1 parameter. Sementara pake Bayes rules dibutuhkan 2^n. Namun asumsi NB ini cukup ekstrem karena menyamaratakan semua conditional independensi dari semua atribut yang terlibat.

Bayesnet sedikit menetralisir permasalahan tersebut. Kalau kita mempunyai pengetahuan tambahan keterkaitan antara satu variabel dengan variabel lainnya, maka bisa dimasukan dalam perhitungan. Sehingga bisa dikatakan Bayesnet berada ditengah antara NB dan Bayes rules. Keterkaitan hubungan ini dibuat dalam bentuk graph. Graph ini menunjukan joint probability distribution dari sekumpulan variabel/nodes.

Ada 2 tipe model graph: yaitu directed graph (yang digunakan pada bayesnet) dan yang undirected graph (tidak terarah seperti markov random fields)

Model Graph ini memasukan pengetahuan kita tentang domain dalam bentuk dependensi atau independensi. Serta mengamati data untuk melakukan estimasi parameter. Model Graphs ini adalah salah satu perkembangan Machine Learning yang penting. Prinsip model graph ini digunakan untuk probabilistic inference dan learning (pembelajaran). Metode ini digunakan pada analisa teks, model time series, diagnosa, sistem bantuan (help system) dll.

X disebut conditional independen terhadap Y|Z bila distribusi probabiliti X tidak bergantung pada Y

P(X|Y,Z)=P(X|Z)

contohnya P(Guntur|Hujan, Kilat)= P(Guntur|Kilat)

X independen secara marginal terhadap Y bila Probabiliti kemunculan X dan Y dinyatakan sebagai perkalian probabiliti X dan Y:

P(X=xi|Y=yj) = P(X=xi)

P(Y=yi|X=xj) = P(Y=yi)

Contoh hubungan joint probability distribution terhadap variabel berikut:

Graph diatas menunjukan hubungan sebab akibat antara variabel misalnya merokok (smoking) menyebabkan kanker paru (Lung Cancer) dan bronkitis. Kemudian tuberkolosis disebabkan oleh kunjungan ke asia dst.

P(X1,X2,X3,X4,X5,X6,X7,X8)=P(X1).P(X2).P(X3|X1).P(X4|X2).P(X5|X2).P(X6|X3,X4).P(X7|X6).P(X8|X5,X6)

Keterhubungan ini tidak ada pada NB, karena asumsi semua variabel adalah conditional independence. Untuk 8 variabel diatas dengan Bayes rules kita membutuhkan perhitungan sebanyak 2^8

Sementara dengan Bayes net kita hanya membutuhkan perhitungan sebanyak: X1,…,X8 –> 2+2+4+4+4+8+4+8=36

Untuk X1 dan X2 hanya perlu 2 probability, contohnya untuk X1 = yes, X1=no ;

Untuk X3 punya 1 parent X1 juga sehingga ada 4 probability yaitu untuk kondisi X1X3: 00, 01,10,11 ;

Untuk X6 punya 2 parent yaitu X3 dan X4 sehingga ada 8 probability untuk kondisi X3X4X6 berikut: 000,001,010, 011, 100,101,110,111

Sampai disini dulu. Insyaallah nanti akan lanjutkan dengan contoh Bayesnet lainnya pada tulisan berikutnya. Semoga Bermanfaat!

Referensi:

Mitchell, Tom. “Machine learning.” (1997): 870-877.

Bayesian Network Learning

Pada tulisan sebelumnya telah dibahas tentang Bayesian Network Learning. Ada 4 kategori. Kali ini akan dibahas tentang kasus pertama yaitu yang graphnya diketahui dan variabelnya juga fully observed.

Contohnya pada kasus berikut:

dari slide tom mitchell

Misalnya Flu dan alergi memiliki kemungkinan menyebabkan penyakit sinus, dan sinus memiliki gejala pusing (headache) dan hidung meler (running nose). Maka probability sinus dapat ditulis sebagai berikut:

dari slide tim mitchell

dengan S= 1 adalah probabilitas sinus given F=i adalah probabilitas Flu bernilai i dan A=j adalah probabilitas alergi bernilai j. Kalau i & j boolean bisa bernilai 0 & 1. Nilai maksimum likelihood estimatenya (MLE) adalah:

dari slide tom mitchell

dengan k adalah jumlah data training, delta = 1 jika kondisi terpenuhi, dan 0 jika tidak terpenuhi. Delta terpenuhi bila nilai fk=i, nilai ak=j dan nilai Sk=1, dibagi dengan jumlah data. Rumus Maximum likehood estimate:

MLE untuk kasus sinus adalah:

Nah untuk kasus ini, yaitu graphnya diketahui dan nilai variabelnya fully observed, maka perhitungan masih mudah, yaitu menggunakan MLE seperti pada rumus diatas. Selanjutnya bagaimana bila nilai variabelnya ada yang tidak diketahui?

Misalnya untuk kasus diatas, Flu, Allergy, Headache dan Nose diketahui. Namun nilai Sinus tidak diketahui. Maka perhitungan MLE tidak bisa dilakukan. Terus bagaimana perhitungan untuk kasus in? Insyaallah saya akan bahas pada tulisan berikutnya. Semoga Bermanfaat!

Referensi

Klik untuk mengakses GrMod3_10_18_2011.pdf

Bayesian Network

Hari ini saya belajar tentang bayesian network (Bayesnet). Bayes net ini adalah model grafis probabilitas yang menampilkan representasi dari variabel dan conditional dependensinya (hubungan) menggunakan Directed acyclic graph (DAG). Bisa juga dikatakan bayes net menampilkan representasi dari joint probability distribution (distribusi probabilitas gabungan) dari sekumpulan variabel random

Bayes net ini sering digunakan untuk menampilkan hubungan event yang terjadi dan memprediksi likelihood (kemungkinan) yang menyebabkan even tersebut. Contohnya bayes net digunakan untuk representasi probabilitas hubungan antara penyakit dan simptom (gejala). Diberikan beberapa simptom, bayes net dapat digunakan untuk menghitung probabilitas adanya penyakit tertentu.

Algoritma yang baik dapat mengambil kesimpulan (inference) dan pembelajaran (learning) dengan bayesian network. Bayes net dapat melakukan pemodelan urutan (sequence) dari berbagai variabel seperti sinyal suara atau urutan protein, disebut bayesian netwrok dinamis. Generalisasi dari bayesian network dapat melakukan representasi dan menyelesaikan permasalahan pengambilan keputusan yang tidak pasti yang disebut influence diagram.

Pembelajaran

Bayes net adalah sebuah graph terarah tidak berputar dan kumpulan dari CPD

  • Setiap node (simpul) digunakan untuk menunjukan sebuah variabel random
  • Edge (sisi) menunjukan dependency (kebergantungan)
  • Setiap simpul Xi memiliki CPD (Conditional Probability Distribution) atau tabel yang menyatakan kebergantungan node tersebut dari induknya (parent) P(Xi|Pa(Xi)) dengan Pa(X) adalah induk langsung dari node X di graph
  • Joint distribution dari seluruh variabel adalah:

Dalam pembelajaran Bayesnet ada 4 kategori tergantung dari

  • Struktur graph diketahui
  • struktur graph tidak diketahui
  • Nilai variabel fully observed (diketahui semuanya)
  • Nilai variabel partly observed (ada yang tidak diketahui)

Struktur graph misalnya diketahui dari ekspert, misalnya kebergantungan antara penyakit dengan gejala.

4 kategori bayesnet

  • Kasus mudah (easy case): struktur graphnya diketahui dan datanya juga fully observed.
  • Kasus menarik (interesting case): graphnya diketahui tapi datanya hanya diketahui sebagian
  • Kasus sulit (gruesome): graphnya tidak diketahui, datanya partly observed
  • graphnya tidak diketahui, datanya fully observed

Sampe disini dulu, besok insyaallah akan saya lanjutkan dengan pembelajaran pada kasus pertama bayesnet. Semoga bermanfaat!

Referensi:

Mitchell, Tom. “Machine learning.” (1997): 870-877.