Multi Layer Perceptron

Single-layer perceptrons hanya dapat mewakili keputusan linier. Perceptron hanya dapat mewakili fungsi yang dapat dipisahkan secara linier. Multi-layer perceptrons (MLP) dapat mewakili keputusan non-linier. MLP menambahkan hidden layer antara input dan output. Menambahkan lapisan tersembunyi memungkinkan lebih banyak fungsi target diwakili.

Hidden Units

adalah node yang terletak di antara node input dan node output, memungkinkan jaringan untuk mempelajari fungsi non- linier, memungkinkan jaringan untuk merepresentasikan kombinasi fitur masukan.

Multi Layer Feed Forward Network (MLP)

  • Multilayer neural network dengan satu lapisan tersembunyi dan 10 masukan, cocok untuk masalah restoran.
  • Layer sering kali terhubung sepenuhnya (tetapi tidak selalu).
  • Jumlah unit tersembunyi yang biasanya dipilih acak

Algoritma Learning MLP

 

Semoga Bermanfaat!

LVQ Prof Wisnu

Saya lanjutkan share materi Prof Wisnu tentang Neural network, kali ini tentang LVQ (Learning Vector Quantization). LVQ beliau artikan sebagai pembelajaran berbasis kompetensi.

  • Struktur jaringan sederhana, lapis tunggal tanpa hidden layers,
  • Vektor Pewakil (reference, prototype) –> representasi kategori kelas
  • Winner Takes all

Metode Pembelajaran LVQ

Contoh LVQ

Backpropagation

Back-propagation diperkenalkan oleh Rumelhart, Hinton dan Williams dan dipopulerkan pada buku Parallel Distributed Processing (Rumelhart and McLelland, 1986)

Prinsip dasar algoritma propagasi-balik memiliki tiga fase:

  • Fase feed forward pola input pembelajaran

  • Fase kalkulasi dan back-propagation error yang didapat.

  • Fase penyesuaian bobot.

  • Jaringan lapis banyak

  • Terdiri dari satu lapisan unit-unit masukan, satu atau lebih lapisan tersembunyi dan satu

Jaringan lapisan unit keluaran; Struktur dasar sama sepeti perceptron, sehingga disebut multilayer perceptron. Setiap neuron pada suatu lapisan dalam jaringan Propagasi-Balik mendapat sinyal. Masukan dari semua neuron pada lapisan sebelumnya beserta satu sinyal bias.

Karakteristik fungsi aktivasi: kontinyu, dapat didiferensiasikan, monoton tidak turun, dan turunan fungi mudah dihitung.

a. fungsi sigmoid biner (range : [0,1])

 

b. fungsi sigmoid bipolar (range : [-1,1])

Back-propagation (Arsitektur) :

 input layer ditunjukkan oleh unit-unit Xi
output layer ditunjukkan oleh unit-unit Yk

hidden layer ditunjukkan oleh unit-unit Zj

Pembelajaran back-propagation

1. Inisialisasi bobot
wi =0 atau angka acak untuk i=b,1,2,3,…..,n Set laju pembelajaran α (0,1 ≤ nα ≤ 1)

Selama syarat henti belum tercapai: 

a. Feedforward:

2. Setiap unit masukan (X , i = 1, …, n) menerima sinyal masukan x dan meneruskannya ke seluruh unit pada lapisan di atasnya (hidden units)
3. Setiap unit tersembunyi (Zj, j = 1, …, p) menghitung total sinyal masukan terbobot dan fungsi aktivasinya.

Setiap unit output (Yk, k = 1, …, m) menghitung total sinyal masukan terbobot dan fungsi aktivasinya

b. Backpropagation of error:

5. Setiap unit output (Yk, k = 1, …, m) menerima sebuah pola target yang sesuai dengan pola masukan pelatihannya. Unit tersebut menghitung informasi kesalahan dan mengoreksi bobot.

6. Setiap unit tersembunyi (Z , j = 1, …, p) menghitung selisih input (dari unit-unit pada layer di atasnya),

Setiap unit output (Yk, k = 1, …, m) dan unit tersembunyi (Zj, j = 1, …, p)

mengubah bias dan bobot-bobotnya (j = 0, …, p) dan (i = 1, …, n):

8. Uji syarat henti

Pemilihan bobot awal dan bias pada back-propagation

  • Pemilihan bobot awal mempengaruhi apakah jaringan akan mencapai error

  • minimum global (atau lokal), dan jika tercapai, seberapa cepat konvergensinya.

  • Update bobot tergantung pada fungsi aktivasi unit yang lebih dalam (pemberi sinyal input) dan turunan fungsi aktivasi unit yang lebih luar (penerima sinyal input), sehingga perlu dihindari pemilihan bobot awal yang menyebabkan keduanya bernilai 0

  • Jika menggunakan fungsi sigmoid, nilai bobot awal tidak boleh terlalu besar karena dapat menyebabkan nilai turunannya menjadi sangat kecil (jatuh di daerah saturasi). Sebaliknya juga tidak boleh terlalu kecil, karena dapat menyebabkan net input ke unit tersembunyi atau unit output menjadi terlalu dekat dengan nol, yang membuat pembelajaran terlalu lambat

Pemilihan bobot awal dan bias pada back-propagation

  • Dua contoh model inisialisasi bobot dan bias.

    • Inisialisasi Acak.

  • Bobot dan bias diinisialisasi nilai acak antara -0.5 dan 0.5 (atau antara -1 dan 1, atau pada interval lain yang sesuai).

    • Inisialisasi Nguyen-Widrow.

  • Cara ini memberikan laju pembelajaran yang lebih cepat. Berikut contohnya untuk arsitektur dengan satu lapis tersembunyi.

    • Bobot dari unit/neuron tersembunyi ke unit/neuron output diinisialisasi dengan nilai acak antara -0.5 dan 0,5

Sampai disini dulu, besok insyaallah saya lanjutkan share bagian terakhir dari presentasi Prof Wisnu tentang multi layer perceptron. Semoga bermanfaat!

Arsitektur Neural Network – Prof Wisnu

Saya lanjutkan share materi pengantar CNN dari Prof Wisnu. Arsitektur Neural Network dapat dikelompokan jadi 3:

  • Single-layer Feed Forward Network
  • Multi-layer Feed Forward Network
  • Recurrent Network
Single Layer Feedforward Network : (X: input ; W Weight ; Y output) 

Multi layer Feed Forward Network (X:input; V,W:weight; Y:output Z : hidden layer)

 

 
Recurrent Neural Network (Memiliki path lingkaran yang membedakan dengan feedforward) (gambar paling atas)
 

Proses Learning & Fungsi Aktivasi

Fungsi Aktivasi

  • Fungsi yang menentukan keadaan internal sebuah neuron dalam JST (Jaringan Syaraf Tiruan)

  • Keluarannya akan dikirim ke neuron lain sebagai input

  • Identitas, tangga biner, tangga bipolar, sigmoid biner, sigmoid bipolar 

Untuk menentukan struktur JST sebelum proses pengklasifikasian pola

Algoritma pembelajaran untuk menentukan struktur JST sebelum proses pengklasifikasian pola. Contoh: Hebb, Perceptron, Adelaine, Madelaine, Backpropagation, SOM, LVQ

Beberapa Fungsi Aktivasi:

  • Fungsi Identitas
  • Fungsi tangga biner (heaviside/threshold)
  • fungsi tangga bipolar
  • fungsi sigmoid biner
  • fungsi sigmoid bipolar

Perceptron

Algoritma pembelajaran perceptron

Ditemukan oleh Rosenbalt (1962) dan Minsky – Papert (1969)

Jaringan terdiri dari satu atau lebih unit masukan dan satu unit keluaran

  • Mempunyai sebuah bias yang bernilai +1 dan mempunyai bobot b
  •  Fungsi aktivasi = fungsi tangga bipolar dengan nilai tetap
 
  • n input 1 output 1 nilai bias
Pembelajaran Perceptron
  • Inisialisasi bobot wi = 0 untuk i = 1, 2, 3, ….., n Set aktivasi untuk unit masukan xi =si i=1,2,…,n
  • Hitung total masukan ke unit keluaran
  • Masukkan ke fungsi aktivasi 4.
  • Jika y ≠ t update bobot
    wi(new)=wi (old)+Δwi  ; i=b,1,2,…,n

Pengujian Perceptron

Sampai disini dulu, besok insyaallah akan saya lanjutkan dengan materi LVQ. Semoga bermanfaat!

 

 

Pengantar Neural Network – Prof Wisnu

Materi berikutnya dari Workshop AI Fasilkom UI adalah pengantar neural network yang disampaikan Prof Wisnu. Neural Network telah memiliki sejarah perkembangan cukup panjang, dimulai dari:

  • Single Layer Perceptron
  • Multi Layer Perceptron
  • Learning Vector Quantization (LVQ)
  • Deep Learning
  • CNN (Convolutional Neural Network)
  • Recurrent Neural Network (RNN)

Sejarah

Kemajuan 1943-1960:

  • Model matematika pertama neuron Pitts & McCulloch (1943)
  • Awal jaringan saraf tiruan
  • Perceptron – Rosenblatt (1958); satu neuron untuk klasifikasi; aturan pembelajaran perceptron; teorema konvergensi perceptron

Kemunduran 1960-1980:

  • Perceptron  tidak bisa mempelajari fungsi XOR
  • tidak tahu cara melatih MLP
  • 1963Backpropagation(Brysonetal.); tapi tidak banyak dikenal

Kemajuan 1980-

  • 1986 Backpropagation diciptakan kembali. Mempelajari representasi dengan kesalahan propagasi balik. Rumilhart dkk. Nature
  • Aplikasi yang berhasil di Pengenalan karakter, mobil otonom, …, dll. •
  • Tapi masih ada beberapa Open Problem di Overfitting? Struktur jaringan? Nomor neuron? Nomor lapisan? Poin minimum lokal yang buruk? Kapan berhenti berlatih?
  • Hopfield nets (1982), mesin Boltzmann, .. dll

Kemunduran 1993-

  • SVM:Support Vector Machine dikembangkan oleh Vapnik et al.. (arsitektur yang 
  • Model grafis menjadi popular
  • Keberhasilan besar SVM dan model grafis hampir membunuh penelitian ANN (Artificial Neural Network).
  • Melatih jaringan yang lebih dalam secara konsisten menghasilkan hasil yang buruk.
  • Namun,Yann LeCun(1998) mengembangkan deep convolutional network (model diskriminatif).

Kemajuan 2006-

  • Deep learning merupakan branding baru penelitian ANN.

  • Deep Belief Networks (DBN)
    ∗ Algoritma pembelajaran cepat untuk jaring keyakinan yang dalam. Hinton et al. Komputasi Neural.
    ∗ Model grafis generatif
    ∗ Berdasarkan mesin Boltzmann terbatas
    ∗ Dapat dilatih secara efisien

  • Deep Autoencoder based networks
    ∗ Greedy Layer-Wise Training of Deep Networks. Bengio et al. NIPS Convolutional neural networks running on GPUs
    ∗ Kesuksesan NN karena penggunaan GPU yang masif.
    ∗ AlexNet (2012). Krizhevsky et al. NIPS

reference: (Lecture Notes) Perceptron Lecturer: Barnabas Poczos

Apa itu neural networks ?

Neural network adalah prosesor yang secara masif terdistribusi secara paralel yang terdiri dari unit pemrosesan sederhana, yang memiliki kecenderungan alami untuk menyimpan pengetahuan pengalaman dan membuatnya tersedia untuk digunakan.

  • Neural Network mengadopsi otak manusia untuk memproses tugas.
  • Untuk melakukan tugas, Neural Network menggunakan interkoneksi yang kuat dari sel komputasi yang dikenal sebagai “neuron“
  • Pengetahuan diperoleh jaringan saraf dari lingkungannya melalui proses pembelajaran
  • Kekuatan koneksi interneuron, yang dikenal sebagai bobot sinaptik, digunakan untuk menyimpan pengetahuan yang diperoleh

Properti dan kapabilitas Neural Network

  • Nonlinier: Nonlinier adalah properti yang sangat penting. terutama jika mekanisme fisik yang mendasari bertanggung jawab untuk menghasilkan sinyal input (mis. • Speech signal)
  • Pemetaan Input-Output; Neural network belajar dari contoh-contoh dengan membuat pemetaan input-output untuk masalah yang dihadapi
  • Adaptivitas: Neural network memiliki kemampuan bawaan untuk menyesuaikan bobot sinaptiknya dengan perubahan di lingkungan sekitarnya
  • Respon Bukti; Dalam konteks klasifikasi pola, jaringan saraf dapat dirancang untuk memberikan informasi tidak hanya tentang pola tertentu yang akan dipilih, tetapi juga tentang kepercayaan dalam keputusan yang dibuat.
  • Informasi Kontekstual: Pengetahuan diwakili oleh struktur dan status aktivasi jaringan syaraf.
  • Toleransi Kesalahan; Mampu melakukan komputasi yang robust, dalam arti kinerjanya menurun dengan baik dalam kondisi pengoperasian yang buruk
  • Penerapan VLSI; VLSI menyediakan sarana untuk menangkap perilaku yang benar-benar kompleks dengan cara yang sangat hierarkis
  • Keseragaman Analisis dan Desain; notasi yang sama digunakan disemua domain yang melibatkan penerapan neural network
  • Analogi Neurobiologis; Rancangan neural network dimotivasi oleh analogi dengan otak, yang merupakan bukti nyata bahwa pemrosesan paralel yang toleran terhadap kesalahan tidak hanya mungkin secara fisik tetapi juga cepat dan kuat

Sampai disini dulu, insyaallah besok saya lanjutkan sharing materi prof Wisnu ini. Semoga Bermanfaat!

 
 

Machine Learning – Fariz Darari

Saya lanjutkan sharing materi workshop AI fasilkom UI. Sekarang materi terakhir dari Fariz Darari, tentang machine learning.

  • Artificial Intelligence (AI) adalah semua teknik yang dapat membuat komputer mampu meniru kemampuan manusia.
  • Machine Learning (ML) adalah bagian dari AI yang menggunakan metoda statistik untuk membuat mesin belajar dari pengalaman (data yang ada)
  • Deep Learning (DL) adalah bagian dari ML yang menggunakan perhitungan komputasi dengan multi layer network

Machine Learning (ML) adalah studi algoritma untuk meningkatkan improve  performance P, pada tugas  T, dengan  E. Contoh task ML : (P, T, E) diantaranya:

  • T mengenali tulisan tangan 
  • P persentase kata dari tulisan tangan yang berhasil diklasifikasi dengan benar
  • E database gambar kata yang ditulis tangan dan diberi label 
  • T kemudi otomatis di jalan tol dengan 4 lajur menggunakan sensor vision
  • P rata-rata jarak tempuh sebelum human-judged eror 
  • E sequence gambar dan perintah mengemudi yang direkam ketika mengamati human driver
  • T kategorisasi email spam atau tidak
  • P persentase email yang diklasifikasikan benar
  • E database email yang diberi label

Kebutuhan ML:

  • Ada pola yang bisa dipelajari, performance bisa diukur
  • Tidak mudah diprogram, tidak perlu ML untuk menghitung 1+1
  • Ada data yang cukup tentang pola, sehingga ML bisa belajar

Beberapa tipe learning:

  • Supervised Learning: dari data yang sudah diberi label, mesin melakukan training, kemudian melakukan prediksi terhadap data baru
  • Unsupervised learning; dari data yang tidak diberi label, mesin diminta menemukan pola dari data

Supervised Learning

  • Regresi: mencari persamaan yang mendekati dari sebaran data; y=mx+b
  • Klasifikasi: melakukan klasifikasi data yang belum diketahui 

Unsupervised

  • Clustering: Mengelompokan data ke dalam subset atau klaster. Coherent intra-cluster (= within the cluster) dan dissimilar inter-cluster (= among clusters)
  • Association rule mining: mencari keterhubungan data (asosiasi)
     

Sampai disini materi Fariz, besok insyaallah saya share materi Prof Wisnu sesi malam. Semoga Bermanfaat!! 

 

Probabilistic Reasoning – Fariz Darari

Saya lanjutkan share materi workshop AI yg diadakan Fasilkom UI. Kali ini materi Probabilistic reasoning dari fariz darari. Probability agent, adalah agent yang dapat bekerja pada kondisi yang tidak pasti (uncertain). Contohnya diagnosis: batuk ⇒ covid-19  ; Ketika orang batuk, maka tidak dapat dipastikan dia covid-19, namun ada probability. Contoh pernyataan “The patient has COVID-19 with probability 0.00002”. Setiap sampel point ω memiliki nilai probabilitas P(ω) :

  • 0 <= P(ω) <= 1
  • Jumlah P(ω) untuk semua sampe adalah 1

Prior probability adalah unconditional probability, contoh : P(cough), P(covid-19); 

Posterior probability adalah conditional probability contoh: P(covid-19|cough); P(covid-19|cough, breathing difficulty); Conditional probability formula: P(a|b) = P(a ∧ b) / P(b). Contoh pada gambar diatas.

Bayes

  • Dari conditional probability : P(a|b) = P(a ∧ b) / P(b)

  • Diperoleh P(a ∧ b) = P(a|b) * P(b)

  • P(a ∧ b) = P(b ∧ a) = P(b|a) * P(a)

  • Diperoleh Bayes Rule: P(b|a) = P(a|b) * P(b) / P(a)

Contoh:

Diketahui COVID-19 menyebabkan cough (batuk) pada 70% pasien.  Probability COVID-19 adalah 1/50000, dan probabilitas  cough adalah 1%.

Misalnya Mr. X batuk, berapa probabilitas dia mendapat COVID-19,  P(covid-19|cough)?

Jawaban:

  • Diketahui: P(cough|covid-19) = 0.7 P(covid-19) = 0.00002
  • P(cough) = 0.01
  • Dengan Bayes Rule, kita dapat: P(covid-19|cough) = P(cough|covid-19) P(covid-19) / P(cough)
  • Sehingga P(covid-19|cough) = 0.7 * 0.00002 / 0.01 = 0.0014

Semoga Bermanfaat!

Knowledge Representation and Reasoning – Fariz Dariri

Saya coba lanjutkan lagi sharing materi workshop AI yang diadakan Fasilkom UI. Kali ini bagian ketiga dari presentasi Fariz dariri tentang sistem cerdas. Knowledge based agent adalah sebuah intelligent agent yang mengetahui benda dan dapat melakukan penalaran. Knowledge (pengetahuan) dan reasoning (penalaran) adalah bagian penting ketika berinteraksi dengan lingkungan yang partially observable. Dua tugas utama tell dan ask. Agent harus dapat mengambil kesimpulan yaitu pengetahuan baru diturunkan dari sesuatu yang sudah diketahui.

Komponen dari Knowledge based agent:

  • inference engine: domain independent algoritma
  • knowledge base: domain-specific content

Contoh klasik penalaran:

Tell:

  • Socrates adalah manusia
  • Semua manusia akan mati

Ask:

  • Apakah Socrates akan mati? Ya

Contoh lain:

Tell: 

  • Kalau hujan, rumput akan basah
  • Hari ini hujan

Ask:

  • apakah rumput basah? ya

Domain-independent reasoining: Modus Ponens

Tell:

  • Jika A maka B
  • A

Ask:

  • B? ya

Tipe-tipe penalaran:

  • Deduktif: Aturan umum –> kesimpulan spesifik
  • Induktif: Observasi tertentu –> Kesimpulan umum
  • Abductif: Observasi yang tidak komplot –> Prediksi terbaik

Contoh penalaran pada kasus Angsa:

  • Deduktif:
    • Semua angsa berwarna putih 
    • Daisy adalah sebuah angsa 
    • maka Daisy berwarna putih
  • Induktif:
    • Daisy adalah angsa, dan daisy berwarna putih
    • Danny adalah angsa dan danny berwarna putih
    • Dante adalah angsa dan dante berwarna putih
    • Maka semua angsa berwrna putih
  • Abduction:
    • Semua angsa berwarna putih
    • Daisy berwarna putih
    • maka Daisy adalah seekor angsa

Kemudian diceritakan contoh kasus wumpus world. Wumpus world ini sebuah game sederhana yang sering dijadikan contoh dalam knowledge representation dan logical reasoning. 

Logical Language

2 logical languge:

  • Propositional Logic (PL)
  • First Order Logic (FOL)

Bagian logical language

  • Syntax: menentukan statement (pernyataan) sesuai dengan format
  • Semantic: Makna dari statement

Proposional Logic (PL)

  • Statement di PL direpresentasikan dengan simbol seperti P,Q,R,ItRains dll
  • Pernyataan yang kompleks bisa menggunakan konektor logika seperti: not (¬), and (∧), or (∨), implies (⇒), if and only if (⇔)
  • Semantik bisa ditentukan dengan sebuah model. kemudian dilakukan pengujian nilai kebenarannya.

Contoh:

  • pernyataan P: Bob adalah seorang guru;
  • Pernyataan Q: Nina adalah seorang bos
  • ¬P ∧ Q : Bob bukan guru  dan Nina seorang bos
  • Bila ditanyakan apakah ¬P ∧ Q true (benar)? 
  • Jawabannya tergantung apakah P benar, apakah Q benar
  • Dalam model dimana P adalah salah, dan Q adalah benar, pernyataan ¬P ∧ Q adalah benar
  • Namun pada model dimana P adalah benar dan Q adalah benar, maka pernyataan P ∧ Q adalah false

 

KB entailment:

  • Tujuan dari pernyataan logil adalah untuk mengambil kesimpulan, (making explicit from what is implicit)
  • entailment KB ⊨ α berarti pernyataan α secara logis mengikuti statements KB
  • Maksudnya pada model apapun yang menghasilkan KB true, maka model tersebut juga menghasilkan  α true

Contoh:

  • A adalah pernyataan ” Socrates adalah manusia”, B adalah “Socrates pasti mati”
  • Bila pernyataan KB terdiri dari A ; A⇒B
  • Apakah KB ⊨ B? ya

First Order Logic (FOL)

  •  Propositional Logic (PL) memiliki keterbatasan ekspresi
  • Contoh sebuah knowledge base (KB) terdiri dari: “Budi is a friend of Ani” dan “All friends of Budi are nice” dengan PL
  • FOL dapat merepresentasikan KB tersebut
  • FOL mendukung
  • Objects, relations, and functions
  • Universal and existential quantifiers
  • Equality

Contoh representasi FOL:

“Budi is a friend of Ani”
• “All friends of Budi are nice”

Friend(Budi, Ani)
∀x Friend(Budi, x) ⇒ Nice(x)

FOL Reasoning:

Universal instantiation: A statement with universal quantifier entailing all its instantiations, so the following holds for any variable v and any object g:

page30image10887504

Diketahui KB berikut:

• “Budi is a friend of Ani”: Friend(Budi, Ani)
• “All friends of Budi are nice”: ∀x Friend(Budi, x) ⇒ Nice(x)

Dapatkah kita menyimpulkan bawha “Ani is nice”, Nice(Ani)?

Jawaban:

Kita bisa melakukan universal instantiation. Substitusu x dengan Ani for ∀x Friend(Budi, x) ⇒ Nice(x) menghasilkan: Friend(Budi, Ani) ⇒ Nice(Ani)

Maka dengan Modus Ponens, dari Friend(Budi, Ani) dan Friend(Budi, Ani) ⇒ Nice(Ani), kita mendapatkan: Nice(ani)

Sampai disini dulu, besok insyaallah saya lanjutkan materi berikutnya tentang Probabilistic reasoning. Semoga Bermanfaat!

Searching – Fariz Darari

Saya coba lanjutkan beberapa catatan dari workshop AI yang diselenggarakan Fasilkom UI. Materi ini bagian kedua dari kuliah Intelligent System (sistem cerdas) pak Fariz, temanya tentang searching. Dalam sistem cerdas, bagian paling mendasar adalah tentang problem solving. Maksudnya bagaimana sistem cerdas dapat mencari solusi dari sebuah masalah. Langkah-langkah problem solving adalah:

  1. Goal Formulation
  2. Problem Formulation
  3. Searching for a solution
  4. Executing the solution

Contoh pertama yang diberikan adalah sbb: Vacation in Romania

 

  1. Goal Formulation: mencari jalan ke Bucharest
  2. Problem Formulation:
    • action: mengemudi dari satu kota ke kota lain;
    • State: Lokasi di sebuah kota
    • Initial state: Arad
  3. Searching: Mencari jalur dari Arad ke bucharest
  4. Executing: Mengemudi dengan mengikuti panduan dari hasil searching

Contoh Lainnya:

  1. Vacuum Cleaner Bot
  2. Eight Puzzle
  3. N Queen
  4. Chatbot

Searching: proses mencari solusi dari masalah yang diberikan

Search tree: beberapa urutan aksi yang memungkinkan dari initial state; menggunakan beberapa algoritma untuk pergi dari initial state ke goal state

Algoritma Tree-Search:

function: tree-search (problem, strategy) returns a solution, or failure intialize the search tree using the intial state of the problem

loop do

if there are no candidates for expansion then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then return the corresponding solution

else expand the node and add the resulting nodes to the search tree

 

Search strategy:

  • Breadth First Search (BFS)
  • Depth First Search (DFS)
  • Uniform cost search (UCS)

Bread First Search

  • Expand shallowest unexpanded node
  • Queu data structure (FIFO)

contoh pada kasus Rumania

  • jika terdapat solusi, menggunakan BFS pasti solusi akan ditemukan
  • Hanya saja kompleksitas waktu dan space meningkat secara eksponensial

Depth First Search

  • expand deepest unexpanded node
  • Stack data structure (LIFO)

  • Contoh pada kasus rumania:

DFS:

  • Lower space complexity than BFS
  • However, can get stuck going down a very long (or even infinite) path!
  • Solution to avoid infinite path: Repeated state checking
  • Still, repeated state checking does not guarantee optimality

Uniform Cost Search

  • expand unexpanded node with lowest path cost

  • Priority queue data structure, ordered by path cost from lowest to highest

  • pada contoh kasus rumania

Heuristic 

  • BFS, DFS dan UCS adalah uninformed search
  • Ketiganya tidak menggunakan heuristic (rule of thumb) untuk mempercepat pencarioan
  • Fungsi heuristik digunakan untuk menghitung cost terendah pada jalur dari node n ke goal node

pada contoh kasus rumania diberikan fungsi heuristik jarak garis lurus kota X dengan bucharest

 

Greedy Search

  • cari node yang sepertinya terdekat dengan tujuan
  • Solusi: Arad – Sibiu – Fagaras – Bucharest
  • Solusi ini tidak optimal!

A* Search

  • Greedy search itu greed (rakus) karena dia hanya menilihat nilai heuristik dari sebuah node

  • A* Search lebih berhati-hati, karena dia mengkombinasikan g(n): cost untuk mencapai current node n; h(n): nilai heuristic atau estimasi cost dari current node n ke goal node 

    f(n) = g(n) + h(n)

  • A* search lebih optimal ketika fungsi heuristik tidak overestimate cost untuk mencapai tujuan

  • Arad; 366= 0 + 366; sibiu; 393=140+253 ; Rimnicu Vilcea: 413=220+193; Pitesti: 417= 317+100; Bucharest: 418=418+0

 

Adversarial Search

  • Search pada lingkungan multiagent 
  • Sangat berguna pada game, dimana tujuan agent adalah maximize score dan tujuan lawan adalah untuk minimize score
  • Tidak seperti search problem biasa, strategi yang diambil harus mempertimbangkan berbagai aksi lawan yang memungkinkan
  • Contoh game Tic-tac-toe (catur jawa)
  •  

Sampai disini dulu, materi berikutnya adalah knowledge representation and reasoning. Insyaallah saya akan lanjutkan besok, semoga bermanfaat!

Intelligent Systems – Fariz Darari

Saya lanjutkan share materi workshop AI yang diadakan Fasilkom UI. Materi ke 3 adalah Intelligent Systems dari Fariz Darari. Awal kuliah pak fariz menjelaskan apa itu intelligent, dan menampilkan quote:

Intelligence is the computational part of the ability to achieve goals (John McCarthy – Father of AI)

Proses Computational thinking ada 3:

  • decomposition: memecahkan masalah dengan membaginya menjadi beberapa kelompok kecil
  • Pattern recognition: menganalisa data dan mengenali pola 
  • Algoritmic design: merancang solusi menggunakan beberapa tahapan

Kemudian dia bercerita tentang Turing test, dimana seorang penanya (manusia) diminta melakukan survey dan menanyakan beberapa pertanyaan kepada dua orang responden: human responden (orang) dan computer responden. Kemudian sang penanya diminta untuk menentukan dari dua orang responden tadi, yang mana manusia dan yang mana komputer. Sistem komputer itu disebut inteligent ketika penanya tidak bisa membedakan mana responden yang orang dan mana yang komputer.

Tes ini berkebalikan dengan tes captcha, dimana kita diminta membuktikan bahwa kita bukan robot. Ada beberapa macam kemampuan intelligent: 

  • Natural Language processing
  • Knowledge representation
  • Automated reasoning
  • machine learning
  • Computer vision
  • robotik

Kemudian dia menjelaskan interaksi intelligent agent (IA) dengan lingkungannya. IA membutuhkan sensor, aktuator, reasoning/information processing untuk melakukan pengambilan keputusan. Kemudian dalam interaksi ini ada yang dinamakan persepsi dan actions. Contoh sistem cerdas:Vaccum cleaner: https://www.youtube.com/watch?v=Yf8MuJUGLlI

Contoh robot pemilih komponen di industri. (PEAS)

  • Performance: Persentase sistem mengambil dan meletekan komponen dengan benar
  • Environment:  Conveyor belt, komponen, kotak penyimpanan komponen
  • Actuator: Tangan robotik
  • Sensor: Kamera, sensor infrared, sensor sudut (joint angel)

Contoh self-driving car:

  • Performance: Keamanan, kecepatan, tidak melanggar aturan, kenyamanan
  • Environment: Jalan, mobil lain, pejalan kaki
  • Actuator: stir, gas, rem, sinyal (lampu sign)
  • Sensor: kamera, GPS, speedometer, radar, odometer

Contoh: robot pengajar interaktif

  • Performance: nilai siswa 
  • Environment: sekelompok siswa
  • Actuator: layar, speaker
  • sensor: keyboard, mouse , mik

Properti dari Lingkungan:

  • Fully observable vs partially observable
  • deterministic vs Stokastik
  • Episodik vs sequensial
  • Statik vs Dinamik
  • Diskrit vs Kontinu
  • Single agent vs Multi agent

Tipe2 agent:

  • Simple reflex agent: 
  • Goal Based agent
  • Learning agent (di gambar paling atas)

referensi:

http://aima.cs.berkeley.edu/

sampai disini dulu, besok insyaallah saya akan lanjutkan materi berikutnya dari pak Fariz tentang searching. Semoga Bermanfaat!

Overview AI Prof Wisnu

Kemaren saya ikut workshop tentang AI (Artificial Intelligence) dr Fasilkom UI. Saya akan coba share beberapa catatan saya dr workshop ini dalam beberapa tulisan. Tulisan kali ini tentang materi pertama, overview AI dari Prof Wisnu Jatmiko. Beliau share beberapa ebook yang pernah dia tulis disini ,Selain itu dia share juga materi webinar beliau tentang penulisan artikel ilmiah disini .

Definisi AI:

  • making a machine behave in ways that would be called intelligent if a human were so behaving. McCarthy, Minsky, Rochester & Shannon, 1956.

  • Turing test (1951) , “imitation game”, tests if a computer can successfully pretend to be a human in a dialogue via screen & keyboard. A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence, August 31, 1955, AI Magazine, Vol. 27(4), 2006. Adapted from Slide “Pattern Recognition: Statistics to Deep Networks” Anil K. Jain, Michigan State University, ICACSIS-IWBIS 2020

Beberapa sejarah perkembangan teknologi yang mendukung AI:

  • 2006 Facebook news Feed
  • 2007 Netflix streaming
  • 2010 Facebook Instagram
  • 2011 Uber
  • 2012 Tesla Model S
  • 2012 Apple Ipad
  • 2013 Ring’s Doorbell
  • 2013 Apple TouchID
  • 2014 Amazon Alexa
  • 2015 Apple Watch
  • 2017 Apple FaceID
  • 2018 3D Metal Printing
  • 2019 AI healthcare
  • 2020 Augmented Reality
  • sumber: https://www.washingtonpost.com/technology/2019/12/26/we-picked-most-influential-technologies-decade-it-isnt-all-bad/

Beberapa contoh sistem cerdas:

  • Self driving car: https://www.youtube.com/watch?v=aaOB-ErYq6Y&t=49s
  • Deepfake: https://www.youtube.com/watch?v=gLoI9hAX9dw
  • Deepfake Monalisa: https://www.youtube.com/watch?v=P2uZF-5F1wI
  • ArchiGAN: generative stack untuk desain apartemen, GAN-enabled Space Layout under Morphing Footprint; https://developer.nvidia.com/blog/archigan-generative-stack-apartment-building-design/

Kemudian dia cerita tentang AI Winter dan timeline perkembangan AI, istilah winter disini maksudnya berhentinya perkembangan AI:

  • 1950-1960: Munculnya AI boom pertama
  • 1970 : AI Winter
  • 1980-1990: AI boom kedua
  • 1990 : AI Winter kedua
  • 1997 : komputer Deep Blue bertanding catur dan mengalahkan gary kasparov
  • 2006 Universitas toronto mengembangkan deep learning
  • 2011 IBM Watson memenangkan jeopardy
  • 2016 Go Software berbasis Deep Learning, mengalahkan juara dunia

Kemudian dia cerita berbagai riset yang dia lakukan, diantaranya tentang:

  • biomedis dan intelligence sistem.  
  • sistem Long-term tracking, yang bisa mendeteksi ketika target yang ditracking hilang https://www.votchallenge.net/vot2018/results.html contohnya yang menggunakan sistem DFCnet dan CFLT.
  • Sistem AI di swarm robot dan unmaned Aerial Vehicle
  • Communication recovery
  • Pengembangan swarm mobile robot
  • sistem deteksi obyek pake yolo3
  • Telehealth
  • TeleUSG
  • teleECG
  • Big Data analisis

Kemudian dia cerita riset yang telah dilakukan selama pandemi:

  • Riset menggunakan open source data
  • Mengembangkan simulator
  • Intelligent trafik

rekaman Videonya bakal dishare di youtube Fasilkom UI katanya. Semoga bermanfaat!