Outline IKI30320 Kuliah 19 3 Des 2007
IKI30320 Kuliah 19 3 Des 2007
Ruli Manurung
Ruli Manurung
Learning Agents Inductive Learning
IKI 30320: Sistem Cerdas Kuliah 19: Machine Learning
Decision Tree Learning
Inductive Learning Decision Tree Learning
Mengukur Kinerja Belajar
Ruli Manurung
Mengukur Kinerja Belajar
Ringkasan
Fakultas Ilmu Komputer Universitas Indonesia
Ringkasan
3 Desember 2007
Learning Agents IKI30320 Kuliah 19 3 Des 2007
Ruli Manurung
Ruli Manurung
Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
2 pendekatan membangun agent: Dirancang, diprogram, diberi knowledge oleh manusia Dirancang sehingga bisa belajar dari input (percept, pengalaman, dst.) Manfaat learning agent: Environment bisa berubah. Manusia (programmer?) itu malas, ceroboh, tidak maha tahu.
Learning Agents
2
Inductive Learning
3
Decision Tree Learning
4
Mengukur Kinerja Belajar
5
Ringkasan
Agent yang Belajar
IKI30320 Kuliah 19 3 Des 2007
Learning Agents
1 Learning Agents
Kita sudah melihat banyak jenis agent: Learning Agents
Simple reflex agent (condition-action rules)
Inductive Learning
Search agent (punya goal dan successor state function)
Decision Tree Learning
Knowledge-based agent (membangun representasi simbolik dari percept)
Mengukur Kinerja Belajar Ringkasan
Utility-based agent (mengukur nilai utility sebuh state) Semua agent ini bisa dibangun dengan metode “pembelajaran” yang tepat! Contoh: agent supir taksi. Bagaimana dia belajar?
Arsitektur Learning Agent IKI30320 Kuliah 19 3 Des 2007
Jenis Metode Learning IKI30320 Kuliah 19 3 Des 2007
Performance standard
Ruli Manurung
Ruli Manurung
Learning Agents Inductive Learning
Learning element
knowledge
Performance element
learning goals Problem generator
Environment
changes
Mengukur Kinerja Belajar
Learning Agents Inductive Learning
feedback
Decision Tree Learning
Ringkasan
Sensors
Critic
Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Sample ini dipakai untuk estimasi fungsinya.
Jenis Metode Learning
IKI30320 Kuliah 19 3 Des 2007
IKI30320 Kuliah 19 3 Des 2007
Ruli Manurung
Ruli Manurung
Learning Agents
Unsupervised learning
Learning Agents
Inductive Learning
Sebuah learning algorithm menerima sekumpulan data, dan harus menemukan pola-pola di dalamanya.
Inductive Learning
Ringkasan
Pada tahap training, learning algorithm menerima sekumpulan input beserta output yang diharapkan.
Effectors
Jenis Metode Learning
Mengukur Kinerja Belajar
Agent belajar fungsi yang memetakan input ke output
experiments
Agent
Decision Tree Learning
Supervised learning
Misalnya: Sebuah agent taxi menerima data mengenai laju lalin sepanjang hari. Mungkin ia bisa belajar periode “morning rush hour”, “evening rush hour”
Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Reinforcement learning Sebuah agent menerima input data dan harus mengambil tindakan. Agent lalu menerima reinforcement signal (mis. good, bad) sebagai akibat tindakan. Learning algorithm memodifikasi agent function untuk memaksimalkan signal “good”.
Inductive Learning IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung Learning Agents Inductive Learning
Consistency vs. Simplicity IKI30320 Kuliah 19 3 Des 2007
Induction Prinsip dasar dari supervised learning adalah “belajar dari pengalaman”.
Ruli Manurung
Prosedur inductive learning:
Inductive Learning
Sebuah hipotesa yang consistent bisa menjelaskan semua training example.
Learning Agents
Decision Tree Learning
Asumsi ada fungsi f : input x, output f (x).
Decision Tree Learning
Ada banyak consistent hypothesis untuk sebuah training set.
Mengukur Kinerja Belajar
Sebuah pair (x, f (x)) disebut example/sample dari f .
Mengukur Kinerja Belajar
Ockham’s Razor: pilih yang paling simple! Secara intuitif: generalisasi terhadap example baru.
Ringkasan
Biasanya ada trade-off antara consistency dan simplicity .
Ringkasan
Ambil himpunan training example dan hasilkan fungsi hipotesa h yang mengaproksimasi f . Pure inductive inference: tak ada prior knowledge ttg. f Fungsi h yang bagus bisa memprediksi example yang belum dilihat (unseen) pada saat belajar.
Metode Ilmiah = Inductive Learning
Contoh “curve-fitting” IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung
IKI30320 Kuliah 19 3 Des 2007
f(x)
Ruli Manurung
Metode ilmiah empiris bisa dilihat sebagai proses inductive learning:
Learning Agents
Learning Agents
Inductive Learning
Inductive Learning
1
Lakukan ujicoba, kumpulkan data
Decision Tree Learning
Decision Tree Learning
2
Rumuskan hipotesis yang konsisten dengan data
3
Hipotesis ini memprediksi nilai data baru
4
Lakukan ujicoba untuk memeriksa kebenaran prediksi
5
Tambahkan ke data yang kita miliki
6
Jika hipotesis tidak lagi konsisten, rumuskan ulang!
Mengukur Kinerja Belajar
Mengukur Kinerja Belajar
Ringkasan
Ringkasan
x
Decision Tree Learning
Induction sebagai Search IKI30320 Kuliah 19 3 Des 2007
IKI30320 Kuliah 19 3 Des 2007
Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Ruli Manurung
Sebuah prosedur induktif mendefinisikan space: possible hypotheses Mis. untuk curve-fitting, space = fungsi polynomial dgn. degree n: f (x) = k0 + k1 x + k2 x 2 + . . . + kn x n Search space terlalu kecil: f (x) yang kita cari tidak ada (unrealisable) Search space terlalu besar:
Proses learning yang menghasilkan decision tree.
Learning Agents Inductive Learning
Hypothesis space mengandung himpunan n input variable dan 1 output variable.
Decision Tree Learning
Tipe variable bisa: boolean, diskrit, kontinyu
Mengukur Kinerja Belajar
Sebuah example tdd himpunan nilai input variable dan 1 output variable
Ringkasan
Jika output variable kontinyu → regression task
Makin sulit ditelusuri Makin banyak hipotesa yang konsisten dengan training example
Jika output variable diskrit → classification task
Contoh: Menunggu di Restoran IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Kita ingin mempelajari pola pikir seseorang (SR): rela menunggu untuk dapat meja di restoran Input variable (di antaranya): Alt (boolean): adakah restoran alternatif? Bar (boolean): apakah restoran memiliki bar? Patrons (diskrit): ada berapa pengunjungnya? Type (diskrit): apa jenis makanannya? Output variable: Variable boolean: WillWait Cari metode yang dapat merumuskan fungsi hipotesa yang “menjawab” nilai WillWait untuk semua kemungkinan nilai input variable.
Contoh: Training Examples IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Ex.
Alt
Bar
Fri
Hun
Pat
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
T T F T T F F F F T F T
F F T F F T T F T T F T
F F F T T F F F T T F T
T T F T F T F T F T F T
Some Full Some Full Full Some None Some Full Full None Full
Attributes Price $$$ $ $ $ $$$ $$ $ $$ $ $$$ $ $
Rain
Res
Type
Est
Target WillWait
F F F F F T T T T F F F
T F F F T T F T F T F F
French Thai Burger Thai French Italian Burger Thai Burger Italian Thai Burger
0–10 30–60 0–10 10–30 >60 0–10 0–10 0–10 >60 10–30 0–10 30–60
T F T T F T F T F F F T
Example di-classify menjadi positive (T) atau negative (F)
Decision Trees IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung Learning Agents
Sebuah representasi untuk kemungkinan hipotesa: Anggap sbg. sebuah if..then yang besar! Leaf node memberikan jawaban output variable Mis.: inilah decision tree untuk fungsi yang “benar”:
Inductive Learning Decision Tree Learning
Decision Trees: Expresiveness
F
Some T
Mengukur Kinerja Belajar
Full
Decision Tree Learning
30−60
F
10−30
Alternate?
No
No
Yes
Bar?
F
T
Yes T
Hungry?
No
Fri/Sat?
T
No F
Yes T
Mengukur Kinerja Belajar
0−10
Yes
Reservation?
No
Learning Agents
WaitEstimate?
>60
Ringkasan
Ruli Manurung
T
Ringkasan
Yes Alternate?
No
Yes
T
Raining?
No F
Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
A
B
F F T T
F T F T
A
A xor B F T T F
F
T
F
T
F
T
F
T
T
F
B
B
Tree ini memiliki satu path root → leaf untuk setiap baris truth table. Kesimpulan: buat satu path untuk setiap training example. Ini namanya “hafal mati”! (Generalisasi? Prediksi contoh baru? Belajar?) Ingat Ockham’s Razor:
Yes
Cari decision tree yang paling simple tapi consistent dengan data
T
Algoritma DTL IKI30320 Kuliah 19 3 Des 2007
Sebuah decision tree dapat menyatakan sembarang fungsi dari nilai input (attributes) Mis. untuk n variable boolean, buat tree dari truth table-nya:
Inductive Learning
Patrons?
None
IKI30320 Kuliah 19 3 Des 2007
Tujuan: cari tree terkecil yang konsisten dengan training examples Algoritma DTL function DTL(examples, attributes, default) returns a decision tree if examples is empty then return default else if all examples have same classification then return classification else if attributes is empty then return M ODE(examples) else best ← C HOOSE -ATTRIBUTE(attributes, examples) tree ← a new decision tree with root test best for each value vi of best do examplesi ← {elements of examples with best = vi } subtree ← DTL(examplesi , attributes − best, M ODE(examples)) add a branch to tree with label vi and subtree subtree return tree
Secara rekursif: cari input variable yang “paling menjelaskan” training example, tambahkan node-nya.
Memilih Variable IKI30320 Kuliah 19 3 Des 2007
Sebuah input variable yang ideal akan memilah example yang ada menjadi “semua positif” atau “semua negatif”.
Ruli Manurung Learning Agents
Berdasarkan prinsip ini, sebuah variable bisa “lebih baik” dari variable lain.
Inductive Learning Decision Tree Learning
Contoh: mana yang lebih baik?
Mengukur Kinerja Belajar Ringkasan
Type?
Patrons? None
Some
Full
French
Italian
Thai
Burger
Information Theory
Memilih Variable dengan Information Gain
IKI30320 Kuliah 19 3 Des 2007
IKI30320 Kuliah 19 3 Des 2007
Ruli Manurung
Ruli Manurung
Learning Agents
Pilih variable yang paling banyak mengandung informasi mengenai nilai output variable.
Learning Agents
Inductive Learning
Gunakan Information Theory (Shannon & Weaver, 1949)
Inductive Learning
Decision Tree Learning
Satuan informasi: 1 bit = informasi yang terkandung jawaban terhadap pertanyaan ya/tidak.
Decision Tree Learning
Mengukur Kinerja Belajar
Dkl. output variable boolean dgn. prior distribution h0.5, 0.5i.
Mengukur Kinerja Belajar
Ringkasan
Kandungan informasi jika prior-nya hP1 , . . . , Pn i: P I(hP1 , . . . , Pn i) = ni= 1 −Pi log2 Pi Disebut entropy dari prior hP1 , . . . , Pn i.
Ringkasan
I(h0.5, 0.5i) = 1bit I(h1.0, 0.0i) = 0bit Information gain Selisih informasi yang dibutuhkan sebelum dan sesudah nilai sebuah atribut diketahui.
Type?
Patrons? None
Some
Full
French
Italian
Thai
Burger
Gain(Patrons) ≈ 0.541bit Gain(Type) ≈ 0bit Pilih Patrons!
Menguji Hipotesa
Hasil DTL IKI30320 Kuliah 19 3 Des 2007
Tree yang dihasilkan algoritme DTL untuk 12 example:
Ruli Manurung Learning Agents Inductive Learning
F
Ringkasan
Some
Full
Yes Type?
French T
Learning Agents
Hungry?
T
Decision Tree Learning Mengukur Kinerja Belajar
Ruli Manurung
Patrons?
None
IKI30320 Kuliah 19 3 Des 2007
Italian
No
Inductive Learning
F
Decision Tree Learning
Thai
Burger T
Fri/Sat?
F
No F
Yes T
Lebih kecil/simple daripada tree yang sebenarnya! Hipotesa yang lebih kompleks (mis. Bar , Rain) tidak perlu (berdasarkan training example!)
Mengukur Kinerja Belajar Ringkasan
Bagaimana mengukur keberhasilan algoritme DTL dkk.? Uji kebenaran hipotesa “menjawab” example baru (generalisasi). Bagi data menjadi 2: training set dan testing set: Jalankan learning pada training set Evaluasi keberhasilan pada testing set
Pendekatan lain: cross-validation: Bagi data menjadi n potongan Train n kali, setiap kali sisakan potongan yang berbeda untuk testing
Learning Curve
Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning
Knowledge = Power Semakin banyak data, semakin bagus hasil machine learning. Learning curve % prediksi benar pada test set sbg. fungsi dari ukuran training set. Contoh, pada data restoran:
Mengukur Kinerja Belajar Ringkasan
IKI30320 Kuliah 19 3 Des 2007
Learning curve juga tergantung masalah yang dipelajari: Realizable: Fungsi target f (x) bisa dinyatakan Non-realizable: Fungsi target f (x) tidak bisa dinyatakan (kurang atribut?) Redundant: Banyak atribut noise yang tidak berguna, menyesatkan (overfitting)!
Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning
1 Proportion correct on test set
IKI30320 Kuliah 19 3 Des 2007
Bentuk Learning Curve
Mengukur Kinerja Belajar
0.9 0.8
% correct 1
realizable
Ringkasan
redundant
0.7
nonrealizable
0.6 0.5 0.4 0
20
40 60 Training set size
80
100
Ringkasan IKI30320 Kuliah 19 3 Des 2007 Ruli Manurung Learning Agents Inductive Learning Decision Tree Learning Mengukur Kinerja Belajar Ringkasan
Learning bermanfaat untuk: Unknown environment Lazy designers
Supervised learning menggunakan prinsip induksi: dari sehimpunan data, estimasi sebuah hipotesa Trade-off antara consistency dan simplicity Algoritme Decision Tree Learning menggunakan Information Gain Metode machine learning diuji dengan tahap training dan testing IKI32310 (Machine Learning)
# of examples