IKI30320 Kuliah 19 3 Des Ruli Manurung. Learning. Agents. Inductive Learning. Decision Tree. Mengukur Kinerja Belajar

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


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


4


5

Ringkasan

Agent yang Belajar


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)


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 element

knowledge

Performance element

learning goals Problem generator

Environment

changes



feedback


Ringkasan

Sensors

Critic

Decision Tree Learning Mengukur Kinerja Belajar Ringkasan

Sample ini dipakai untuk estimasi fungsinya.

Jenis Metode Learning



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


Agent belajar fungsi yang memetakan input ke output

experiments

Agent


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


Asumsi ada fungsi f : input x, output f (x).


Ada banyak consistent hypothesis untuk sebuah training set.


Sebuah pair (x, f (x)) disebut example/sample dari f .


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


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



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!



Ringkasan

Ringkasan

x


Induction sebagai Search 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.


Hypothesis space mengandung himpunan n input variable dan 1 output variable.


Tipe variable bisa: boolean, diskrit, kontinyu


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”:


Decision Trees: Expresiveness

F

Some T


Full


30−60

F

10−30

Alternate?

No

No

Yes

Bar?

F

T

Yes T

Hungry?

No

Fri/Sat?

T

No F

Yes T


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


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.


Contoh: mana yang lebih baik?


Type?

Patrons? None

Some

Full

French

Italian

Thai

Burger

Information Theory

Memilih Variable dengan Information Gain



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


Satuan informasi: 1 bit = informasi yang terkandung jawaban terhadap pertanyaan ya/tidak.



Dkl. output variable boolean dgn. prior distribution h0.5, 0.5i.


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


Italian

No

Inductive Learning

F


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!)


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:



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


Bentuk Learning Curve


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

IKI30320 Kuliah 19 3 Des Ruli Manurung. Learning. Agents. Inductive Learning. Decision Tree. Mengukur Kinerja Belajar

Recommend Documents