01 · Pengantar AI
Kecerdasan adalah kemampuan menyelesaikan masalah baru, memilih tindakan yang masuk akal, dan belajar dari pengalaman. Sistem cerdas perlu memahami keadaan, membuat rencana, lalu menyesuaikan tindakannya.
John McCarthy mendefinisikan AI sebagai ilmu dan rekayasa untuk membuat mesin cerdas. Mesin disebut cerdas jika dapat menghitung tindakan yang membantu mencapai tujuan.
| Seperti manusia | Rasional | |
|---|---|---|
| Berpikir | Meniru proses berpikir manusia. Bidang terkait: ilmu kognitif. | Menggunakan logika untuk menarik kesimpulan yang benar. |
| Bertindak | Berperilaku seperti manusia. Ukurannya antara lain Turing Test. | Memilih tindakan dengan hasil atau manfaat terbaik. |
Contoh empat sudut pandang
- Berpikir seperti manusia: program meniru urutan pertanyaan yang dipakai dokter saat mendiagnosis.
- Bertindak seperti manusia: program chat lolos Turing Test jika penguji tidak dapat membedakan jawabannya dari jawaban manusia.
- Berpikir rasional: dari “semua manusia fana” dan “Sokrates adalah manusia”, kesimpulan yang sah adalah “Sokrates fana”.
- Bertindak rasional: aplikasi peta memilih rute dengan waktu tempuh paling kecil.
Tiga cara mesin belajar
- Supervised learning memakai data berlabel. Contoh: 100 email diberi label spam atau bukan spam, lalu model memberi label pada email baru.
- Unsupervised learning memakai data tanpa label. Contoh: riwayat belanja dikelompokkan menjadi pelanggan yang belanjanya sering dan pelanggan yang belanjanya jarang.
- Reinforcement learning belajar dari reward. Contoh: robot menerima +1 saat sampai di tujuan dan −1 saat menabrak, lalu memilih gerakan dengan total reward terbesar.
Tonggak sejarah: model neuron McCulloch–Pitts pada 1943, tulisan Turing pada 1950, dan konferensi Dartmouth pada 1956. DENDRAL dan MYCIN adalah contoh expert system. Jaringan saraf kembali berkembang sekitar 1986.
Pengenal suara untuk 10 digit sudah dapat bekerja dengan baik. Sistem yang harus memahami isi sebuah film, atau mencari rencana dengan jumlah kemungkinan yang sangat besar, masih kesulitan.
02 · Pencarian state
Masalah pencarian harus memiliki ruang keadaan (state space), keadaan awal, tujuan, dan aturan perpindahan. Keadaan yang melanggar aturan tidak dimasukkan ke graph. Pada masalah menyeberangkan serigala, angsa, beras, dan petani, nilai 1 berarti masih di sisi awal. Keadaan awalnya adalah (1,1,1,1).
Semua algoritma memakai pola yang sama. Masukkan titik awal ke frontier, yaitu kumpulan simpul yang belum diperiksa. Pilih satu simpul. Jika simpul itu tujuan, pencarian selesai. Jika belum, buka simpul tersebut dan masukkan tetangganya. Setiap algoritma memiliki aturan pilih yang berbeda.
g = biaya dari awal ke simpul sekarang
h = perkiraan biaya dari simpul sekarang ke tujuan
f = g + h
| Algoritma | Aturan pilih | Akibatnya |
|---|---|---|
| BFS | Memakai antrean FIFO dan membuka simpul paling dangkal. Bobot sisi dan h tidak dipakai. | Menemukan jalur dengan langkah paling sedikit. Jalurnya juga paling murah hanya jika semua sisi berbobot sama. Kebutuhan memorinya besar. |
| DFS | Memakai tumpukan LIFO dan menelusuri satu cabang sedalam mungkin. | Lebih hemat memori, tetapi tidak menjamin jumlah langkah atau biaya terkecil. Pencarian dapat tersesat di cabang yang dalam. |
| Hill climbing | Dari simpul sekarang, pilih tetangga dengan h terkecil. Pilihan lain dibuang. | Tidak menyimpan jalan cadangan. Pencarian dapat berhenti pada optimum lokal. |
| Best-first | Membuka simpul dengan h terkecil. Kandidat lain tetap berada di frontier. | Biaya yang sudah dikeluarkan tidak dihitung. Jalur yang tampak dekat bisa saja mahal. |
| A* | Membuka simpul dengan f = g + h terkecil. | Menemukan jalur termurah jika h admissible, yaitu tidak melebihi biaya sisa yang sebenarnya. |
| Branch & bound | Membuka jalur dengan g terkecil dan menyimpan semua jalur sementara. Nilai h tidak dipakai. | Menemukan optimum global. Setelah tujuan ditemukan, jalur dengan g yang mencapai atau melewati batas biaya dibuang. Memori yang dipakai besar. |
| DP | Membuka g terkecil dan menyimpan satu biaya terbaik untuk setiap simpul. | Memberikan optimum global dengan memori lebih kecil daripada branch and bound. Jalur yang lebih mahal menuju simpul yang sama langsung dibuang. |
Contoh pada graph S–Z
Dari S ada dua tetangga: A dengan g = 4 dan h = 8, serta B dengan g = 3 dan h = 6. BFS, DFS, branch and bound, dan DP tidak memakai h. Hill climbing, best-first, dan A* memakai h.
| Algoritma | Contoh langkahnya |
|---|---|
| BFS | A dan B sama-sama berjarak satu langkah. A masuk antrean lebih dulu, jadi A dibuka lebih dulu. Jalur akhir: S → A → D → Z, 3 langkah, g = 12. |
| DFS | B berada di puncak tumpukan, jadi B dibuka lebih dulu. Jalur akhir: S → B → C → E → Z, g = 10. Hasil ini mengikuti urutan tumpukan. |
| Hill climbing | Dari S, h(B) = 6 lebih kecil daripada h(A) = 8. A dibuang. Pencarian lanjut ke C, E, lalu Z. |
| Best-first | B juga dibuka lebih dulu karena h-nya lebih kecil. Bedanya, A tetap disimpan di frontier. |
| A* | f(B) = 3 + 6 = 9 dan f(A) = 4 + 8 = 12. B dibuka lebih dulu. Jalur akhir: S → B → C → E → Z, g = 10. |
| Branch & bound | Jalur S → A (g = 4) dan S → B → A (g = 8) sama-sama disimpan. Setelah Z ditemukan dengan g = 10, jalur yang g-nya mencapai 10 atau lebih dibuang. |
| DP | A sudah tercapai dengan g = 4. Kedatangan lain ke A dengan g = 8 dibuang. Hasil akhirnya tetap S → B → C → E → Z, g = 10. |
03 · Logika fuzzy
Logika crisp hanya mengenal dua nilai: benar atau salah. Jika suhu di atas 80°F disebut panas, maka 80,1°F dan 100°F menerima label yang sama. Logika fuzzy dapat membedakan tingkat kepanasan keduanya dengan derajat keanggotaan μ dari 0 sampai 1. Satu nilai dapat menjadi anggota beberapa himpunan sekaligus.
Probabilitas menyatakan peluang suatu kejadian. Derajat keanggotaan menyatakan seberapa cocok suatu nilai dengan sebuah himpunan. Pada contoh umur, Ann yang berusia 28 tahun memiliki μ Young = 0,8, Bob yang berusia 35 tahun memiliki μ Young = 0,3, dan Charlie yang berusia 23 tahun memiliki μ Young = 1.
input crisp > fuzzification > inference > composition > defuzzification > output crisp
- Fuzzification menghitung μ untuk setiap himpunan. Tinggi 163 cm, misalnya, diubah menjadi beberapa nilai keanggotaan.
- Inference memeriksa aturan fuzzy satu per satu.
- Composition menggabungkan hasil seluruh aturan.
- Defuzzification mengubah hasil gabungan menjadi satu angka crisp. Slide menggunakan metode centroid sebagai contoh.
Contoh hitung
Dua aturan pakar: suhu dingin membuat pemanas tinggi, suhu hangat membuat pemanas sedang. Pada suhu 18, fuzzification menghasilkan μ dingin = 0,4 dan μ hangat = 0,6.
Inference mengaktifkan aturan pertama sebesar 0,4 dan aturan kedua sebesar 0,6. Pemanas tinggi diwakili 80, pemanas sedang diwakili 50. Composition mempertahankan kedua hasil tersebut.
z = (0,4 × 80 + 0,6 × 50) / (0,4 + 0,6) = 62 / 1 = 62
Angka 62 adalah output crisp hasil defuzzification. Aturan pada contoh ini dibuat oleh pakar, tanpa data latih.
04 · Algoritma genetika
Metode exact memeriksa semua kemungkinan untuk mendapatkan hasil optimal. Pada TSP dengan n kota, jumlah rute yang perlu diperiksa adalah (n − 1)! / 2. Untuk 100 kota, jumlahnya terlalu besar. Metode heuristic mengurangi waktu pencarian dengan menerima solusi yang baik meskipun belum tentu paling optimal.
- Algoritma genetika meniru seleksi alam melalui pemilihan induk, perkawinan, dan mutasi.
- Ant colony memakai gagasan jejak feromon, sedangkan simulated annealing meniru proses pendinginan logam.
- Hill climbing mengolah satu kandidat. Algoritma genetika mengolah satu populasi yang berisi banyak kandidat.
Holland, DeJong, dan Goldberg mengembangkan dasar algoritma genetika pada 1970-an di Amerika Serikat. Versi Holland dikenal sebagai simple genetic algorithm.
Contoh satu individu pada tugas kata: chromosome G E N E T I K A. Huruf N adalah allele pada gene ketiga. Empat individu membentuk satu populasi. Jika jarak individu ke target adalah 8, fitness-nya 208 − 8 = 200.
| Nama | Artinya di GA |
|---|---|
| Gene | Satu bagian data, misalnya bit, angka, huruf, atau kota. |
| Allele | Nilai yang tersimpan di dalam gene. |
| Chromosome | Rangkaian gene yang mewakili satu calon solusi. |
| Population | Kumpulan individu yang diproses bersama. |
| Generation | Satu putaran proses algoritma genetika. |
| Fitness | Nilai kualitas individu. Pada roulette, fitness yang besar memberi peluang terpilih yang lebih besar. |
Sebelum menjalankan algoritma, tentukan bentuk individu yang valid dan fungsi fitness. Tentukan juga cara membuat populasi awal, memilih induk, melakukan crossover, serta melakukan mutasi beserta probabilitasnya.
populasi > evaluasi fitness > seleksi > crossover dan mutasi > populasi baru > ulangi
Seleksi
Roulette memilih individu berdasarkan fitness. Karena roulette membutuhkan fitness positif dan mengutamakan nilai besar, masalah minimisasi seperti jarak perlu diubah menjadi maksimisasi. Pada tugas kata, rumusnya fitness = 208 − jarak.
pᵢ = fᵢ / (f₁ + f₂ + … + fₙ)
Empat individu di slide, fitness 10, 20, 40, 30. Total 100.
| # | Fitness | Peluang | Rentang undian 1–100 |
|---|---|---|---|
| 1 | 10 | 10% | 1–10 |
| 2 | 20 | 20% | 11–30 |
| 3 | 40 | 40% | 31–70 |
| 4 | 30 | 30% | 71–100 |
Angka acak 66, 85, 44, dan 18 pada slide memilih individu 3, 4, 3, dan 2. Individu 3 terpilih dua kali karena memiliki rentang terbesar. Contoh tournament dengan k = 2: individu 1 (fitness 10) dan individu 3 (fitness 40) terambil, lalu individu 3 yang lolos.
Crossover, mutasi, elitisme
Crossover dijalankan jika angka acak p lebih kecil daripada probabilitas crossover. Slide memakai probabilitas 0,9. Jika syarat tidak terpenuhi, anak menyalin induknya. Two-point crossover menukar bagian chromosome di antara dua titik potong. Untuk gene berupa bilangan real, arithmetic crossover memakai rumus:
anak₁ = r·p₁ + (1 − r)·p₂
anak₂ = r·p₂ + (1 − r)·p₁
Contoh arithmetic dengan r = 0,4. Gene induk 0,2 dan 1,0 menghasilkan anak 0,4 × 0,2 + 0,6 × 1,0 = 0,68.
Contoh two-point dari slide. Induk 1 1 0 0 0 0 0 dan 1 0 1 0 1 0 1, bagian gene 2 sampai 5 ditukar. Anaknya 1 0 1 0 1 0 0 dan 1 1 0 0 0 0 1.
TSP memerlukan operator khusus karena pertukaran biasa dapat menghasilkan kota yang berulang. Pada tugas kata GENETIKA, huruf boleh berulang sehingga two-point crossover dapat dipakai.
Contoh mutasi: 1 0 0 1 1 berubah di posisi kedua menjadi 1 1 0 1 1. Pada bilangan real, 0,2 digeser sebesar ε = 0,1 menjadi 0,3. Probabilitas mutasi kecil dan terpisah dari probabilitas crossover. Mutasi dapat menghasilkan allele yang sebelumnya tidak ada di populasi.
Contoh elitisme dengan n = 2. Induk memiliki fitness 40 dan 10, anak memiliki fitness 30 dan 20. Gabungan empat fitness itu diurutkan, lalu dua nilai terbesar diambil: 40 dan 30. Induk terbaik tetap bertahan.
Algoritma berhenti saat solusi memenuhi target atau jumlah generasi mencapai batas.
05 · Klasifikasi
Klasifikasi memberi label kelas pada data. Setiap baris data disebut record. Satu kolom menyimpan kelas, sedangkan kolom lain menyimpan atribut. Data training dipakai untuk membangun model dan data test dipakai untuk mengukur ketepatannya.
Proses pada slide terdiri dari learning, validation, dan testing. Learning membentuk model dari data berlabel. Validation menyembunyikan label yang sudah diketahui untuk mengukur ketepatan model. Testing memakai model untuk memberi label pada data baru. Dalam pembahasan performa, istilah validation kadang disebut testing.
Contoh: 10 baris berlabel Yes atau No dipakai pada learning. Tiga baris lain labelnya disembunyikan untuk validation. Lima baris baru yang masih bertanda “?” masuk ke testing.
Pada contoh salmon dan sea bass, panjang ikan tidak memisahkan kedua kelas dengan baik karena nilainya banyak bertumpang tindih. Tingkat kecerahan memberi pemisahan yang lebih jelas. Jika memakai dua fitur, batas klasifikasi sebaiknya memisahkan kelompok tanpa mengikuti setiap titik data terlalu ketat.
Find-S dan Candidate-Elimination
Contoh EnjoySport. Urutan atribut: Sky, suhu, humidity, wind, water, forecast. Find-S hanya membandingkan baris Yes.
- Sunny, Warm, Normal, Strong, Warm, Same: Yes
- Sunny, Warm, High, Strong, Warm, Same: Yes
- Sunny, Warm, High, Strong, Cool, Change: Yes
- Rainy, Cold, High, Strong, Warm, Change: No
Nilai yang sama pada semua baris Yes tetap ditulis. Nilai yang berbeda menjadi tanda tanya. Hasil Find-S untuk Yes: <Sunny, Warm, ?, Strong, ?, ?>. Baris No diabaikan. Karena baris No hanya satu, hipotesis No menyalin baris itu: <Rainy, Cold, High, Strong, Warm, Change>.
Candidate-Elimination menyimpan dua batas. Awalnya S = <φ, φ, φ, φ, φ, φ> dan G = <?, ?, ?, ?, ?, ?>. Baris Yes pertama membuat S menjadi <Sunny, Warm, Normal, Strong, Warm, Same>. Baris No membuat G lebih khusus supaya baris itu tertolak. Jika data saling bertentangan, S dan G tidak bertemu.
k-NN
k-NN menentukan kelas data baru dari kelas tetangga terdekat. Jarak antardata dihitung dengan rumus Euclidean. Pada 1-NN, kelas mengikuti satu tetangga terdekat. Pada k-NN, kelas ditentukan lewat voting dari k tetangga.
jarak(a, b) = √( Σ (aᵢ − bᵢ)² )
Contoh hipertensi. Lima data latih, data baru berat 80 dan umur 85.
| Berat | Umur | Kelas | Jarak ke (80, 85) |
|---|---|---|---|
| 70 | 20 | No | √4325 ≈ 65,8 |
| 85 | 20 | No | √4250 ≈ 65,2 |
| 70 | 50 | No | √1325 ≈ 36,4 |
| 100 | 50 | Yes | √1625 ≈ 40,3 |
| 100 | 80 | Yes | √425 ≈ 20,6 |
Jarak terdekat dihitung dari (80, 85) ke (100, 80): (20)² + (5)² = 425, lalu √425 ≈ 20,6. Karena ini jarak terkecil, 1-NN menghasilkan Yes. Tiga jarak terkecil berisi dua Yes dan satu No, jadi k = 3 menghasilkan Yes. Kelima data berisi tiga No dan dua Yes, jadi k = 5 menghasilkan No.
k-NN mudah dihitung dan dapat diparalelkan. Namun, algoritma ini menyimpan seluruh data training dan membandingkan setiap data baru dengan data tersebut. Akibatnya, kebutuhan memori dan waktu prediksi meningkat saat jumlah data bertambah. Karena perhitungan baru dilakukan saat prediksi, k-NN disebut lazy learning.
06 · Validasi model
Validasi mengukur error classifier pada data yang tidak dipakai untuk melatih model. Pertemuan ini membahas lima cara membagi data training dan test.
| Metode | Cara membagi data | Yang membedakan |
|---|---|---|
| Holdout | Dataset dibagi satu kali menjadi data training dan test. | Cepat, tetapi hasil sangat bergantung pada pembagian data. Pada dataset kecil, data training juga berkurang banyak. |
| Random subsampling | Pembagian acak diulang K kali. Setiap percobaan mengambil data test tanpa pengembalian dan dengan ukuran tetap. | Error akhir adalah rata-rata error setiap percobaan. Hasil lebih stabil daripada holdout, tetapi suatu data belum tentu pernah masuk set test. |
| K-fold | Dataset dibagi menjadi K fold. Setiap percobaan memakai satu fold untuk test dan K−1 fold untuk training. | Semua data mendapat giliran sebagai data training dan test. Error akhir adalah rata-rata error dari K percobaan. |
| Leave-one-out | K-fold dengan K = N. Satu data menjadi test dan N−1 data menjadi training pada setiap percobaan. | Memakai hampir seluruh data untuk training sehingga cocok untuk dataset sangat kecil. Biaya komputasinya besar karena model dilatih N kali. |
| Bootstrap | Ambil N data dengan pengembalian untuk membentuk data training. Data yang tidak terambil menjadi data test. | Satu data dapat muncul beberapa kali pada training. Jumlah data test dapat berbeda pada setiap percobaan. |
E = (1/K) Σ Eᵢ
leave-one-out: E = (1/N) Σ Eᵢ
Error = (jumlah salah kelas / jumlah data) × 100%
Contoh error: 3 prediksi salah dari 12 data memberi error = 3 / 12 × 100% = 25%. Jika dua percobaan menghasilkan E₁ = 0,20 dan E₂ = 0,40, rata-ratanya (0,20 + 0,40) / 2 = 0,30.
Contoh pembagian enam data
Data ilustrasinya x1 sampai x6.
| Metode | Contoh pembagian |
|---|---|
| Holdout | Training x1–x4 dan test x5–x6, dilakukan satu kali. Jika x6 salah kelas, error percobaan itu 1 / 2 = 50%. |
| Random subsampling | K = 3 dan setiap test berisi dua data: (x1, x2), (x1, x3), lalu (x2, x3). Data x4, x5, dan x6 tidak pernah menjadi test. |
| K-fold | K = 3 dengan fold (x1, x2), (x3, x4), dan (x5, x6). Test bergiliran dari fold pertama sampai ketiga, sehingga setiap data menjadi test satu kali. |
| Leave-one-out | N = 6, jadi ada enam percobaan. Percobaan pertama mengetes x1 dan melatih x2–x6. |
| Bootstrap | Dari x1–x4, satu pengambilan training adalah x1, x1, x3, x4. x1 muncul dua kali, sedangkan x2 menjadi test karena tidak terambil. |
K yang besar memberi bias kecil, tetapi varians dan waktu hitungnya lebih besar. K yang kecil lebih cepat dan variansnya lebih kecil, tetapi biasnya lebih besar. Slide menyarankan 3-fold untuk dataset besar, leave-one-out untuk dataset yang sangat sedikit, dan K = 10 sebagai pilihan umum.
Cek cepat
| Kalau ditanya | Jawaban singkat |
|---|---|
| Empat sudut pandang AI | Berpikir seperti manusia, bertindak seperti manusia, berpikir rasional, dan bertindak rasional. |
| BFS vs A* di graph S–Z | BFS: S–A–D–Z, g = 12. A*: S–B–C–E–Z, g = 10. f = g + h. |
| B&B vs DP | Keduanya memakai g dan menghasilkan optimum global. B&B menyimpan beberapa jalur menuju simpul yang sama. DP hanya menyimpan g terbaik. |
| μ dan probabilitas | μ menyatakan tingkat kecocokan dengan himpunan. Probabilitas menyatakan peluang kejadian. |
| Urutan sistem fuzzy | Fuzzification, inference, composition, defuzzification. |
| Undian 44 pada roulette slide | Individu 3. Fitness 40, rentang 31–70. |
| Elitisme slide | Gabungkan n induk dan n anak, lalu ambil n individu dengan fitness tertinggi. |
| Find-S kelas Yes | <Sunny, Warm, ?, Strong, ?, ?>. Contoh negatif tidak dipakai. |
| Hipertensi (80, 85) | k = 1 Yes, k = 3 Yes, k = 5 No. |
| K-fold vs subsampling | Pada K-fold, semua data mendapat giliran sebagai training dan test. Pada random subsampling, suatu data belum tentu pernah menjadi test. |
| Leave-one-out | K = N. Setiap percobaan memakai satu data test dan N−1 data training. |
| K yang umum | K = 10. Dataset besar dapat memakai 3-fold. Dataset yang sangat sedikit dapat memakai leave-one-out. |