ml-toc.ps

这是博弈论算法全集第三部分:机器学习,其它算法将陆续推出.以便与大家共享

%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop -95 -61 75 3 v -7 -75 3 75 v 942 -100 a Fm(i)p
1896 -75 V 1910 -61 75 3 v 1656 116 a Fl(i)557 952 y
Fk(Mac)m(hine)34 b(Learning)684 1010 y Fj(Draft)17 b(of)g(Jan)o(uary)f
(2,)h(1997)767 1069 y(T)l(om)f(M.)f(Mitc)o(hell)656 1127
y(Carnegie)h(Mellon)f(Univ)o(ersit)o(y)364 1476 y(Cop)o(yrigh)o(t)607
1474 y(c)593 1476 y Fi(\015)p Fj(1996.)i(T)l(om)f(M.)f(Mitc)o(hell)f
(and)j(McGra)o(w)f(Hill.)p -95 2696 V -7 2783 3 75 v
246 2684 a Fh(00127)10 b(6)369 2670 y Fg(3)p 368 2676
16 2 v 368 2697 a(8)396 2684 y Ff(\002)f Fh(9)455 2670
y Fg(1)p 454 2676 V 454 2697 a(4)486 2684 y Fh(P)o(ages)i(created)e
(for)i(McGra)o(w-Hill)g(b)o(y)g(T)m(om)h(Mitc)o(hell)69
b(JAN.)12 b(2,)f(1997)p 1896 2783 3 75 v 1910 2696 75
3 v eop
%%Page: 2 2
2 1 bop -95 -61 75 3 v -7 -75 3 75 v 937 -100 a Fm(ii)p
1896 -75 V 1910 -61 75 3 v 225 116 1 25 v 226 92 25 1
v 1645 92 V 1670 116 1 25 v 225 214 1445 4 v 1181 298
a Fe(CONTENTS)p 225 326 V 399 1213 a Fd(1)41 b Fj(In)o(tro)q(duction)
915 b Fc(1)468 1267 y(1.1)55 b(W)m(ell-P)o(osed)16 b(Learning)e
(Problems)564 b(2)468 1313 y(1.2)55 b(Designing)16 b(a)d(Learning)i
(System)588 b(5)572 1358 y(1.2.1)75 b(Cho)q(osing)14
b(the)f(T)m(raining)i(Exp)q(erience)354 b(5)572 1404
y(1.2.2)75 b(Cho)q(osing)14 b(the)f(T)m(arget)g(F)m(unction)422
b(7)572 1450 y(1.2.3)75 b(Cho)q(osing)15 b(a)g(Represen)o(tation)h(for)
e(the)g(T)m(arget)726 1495 y(F)m(unction)778 b(9)572
1541 y(1.2.4)75 b(Cho)q(osing)14 b(a)e(F)m(unction)h(Appro)o(ximation)i
(Algorithm)113 b(10)572 1587 y(1.2.5)75 b(The)13 b(Final)h(Design)616
b(12)468 1632 y(1.3)55 b(P)o(ersp)q(ectiv)o(es)15 b(and)f(Issues)f(in)h
(Mac)o(hine)h(Learning)310 b(15)572 1678 y(1.3.1)75 b(Issues)13
b(in)h(Mac)o(hine)h(Learning)450 b(15)468 1724 y(1.4)55
b(Ho)o(w)13 b(to)g(Read)h(this)f(Bo)q(ok)665 b(16)468
1769 y(1.5)55 b(Summary)14 b(and)g(F)m(urther)f(Reading)536
b(17)572 1815 y(Exercises)907 b(18)468 1860 y(1.6)55
b(References)883 b(19)399 1936 y Fd(2)41 b Fj(Concept)18
b(Learning)g(and)g(the)f(General-to-Sp)q(eci\014c)468
1986 y(Ordering)973 b Fc(21)468 2040 y(2.1)55 b(In)o(tro)q(duction)851
b(22)468 2086 y(2.2)55 b(A)13 b(Concept)h(Learning)g(T)m(ask)626
b(22)468 2131 y(2.3)55 b(Concept)14 b(Learning)h(as)e(Searc)o(h)590
b(24)572 2177 y(2.3.1)75 b(General-to-Sp)q(eci\014c)16
b(Ordering)e(of)f(Hyp)q(otheses)179 b(25)468 2223 y(2.4)55
b Fb(Find-S)p Fc(:)13 b(Finding)i(a)e(Maximally)j(Sp)q(eci\014c)f(Hyp)q
(othesis)226 b(27)468 2268 y(2.5)55 b(V)m(ersion)16 b(Spaces)f(and)g
(the)g Fb(Candid)o(a)n(te-Elimina)n(tion)572 2314 y Fc(Algorithm)889
b(30)572 2360 y(2.5.1)75 b(Represen)o(tation)656 b(30)572
2405 y(2.5.2)75 b(The)13 b Fb(List-Then-Elimina)n(te)h(Algorithm)225
b Fc(31)225 2505 y Fl(ii)p -95 2696 75 3 v -7 2783 3
75 v 244 2684 a Fh(00127)10 b(6)367 2670 y Fg(3)p 367
2676 16 2 v 367 2697 a(8)395 2684 y Ff(\002)e Fh(9)453
2670 y Fg(1)p 453 2676 V 453 2697 a(4)485 2684 y Fh(P)o(ages)i(created)
g(for)h(McGra)o(w-Hill)g(b)o(y)g(T)m(om)g(Mitc)o(hell)69
b(JAN.)13 b(2,)e(1997)p 1896 2783 3 75 v 1910 2696 75
3 v eop
%%Page: 3 3
3 2 bop -95 -61 75 3 v -7 -75 3 75 v 932 -100 a Fm(iii)p
1896 -75 V 1910 -61 75 3 v 1418 116 a Fg(CONTENTS)42
b Fl(iii)572 200 y Fc(2.5.3)75 b(A)13 b(More)h(Compact)f(Represen)o
(tation)j(for)d(V)m(ersion)726 245 y(Spaces)795 b(32)572
291 y(2.5.4)75 b Fb(Candid)o(a)n(te-Elimina)n(tion)13
b Fc(Learning)i(Algorithm)131 b(33)572 337 y(2.5.5)75
b(An)13 b(Illustrativ)o(e)i(Example)502 b(35)468 382
y(2.6)55 b(Remarks)19 b(on)g(V)m(ersion)g(Spaces)g(and)572
428 y Fb(Candid)o(a)n(te-Elimina)n(tion)629 b Fc(38)572
474 y(2.6.1)75 b(Will)15 b(the)f Fb(Candid)o(a)n(te-Elimina)n(tion)f
Fc(Algorithm)726 519 y(Con)o(v)o(erge)g(to)g(the)g(Correct)g(Hyp)q
(othesis?)285 b(38)572 565 y(2.6.2)75 b(What)14 b(T)m(raining)h
(Example)g(Should)h(the)e(Learner)726 611 y(Request)g(Next?)659
b(39)572 656 y(2.6.3)75 b(Ho)o(w)12 b(Can)h(P)o(artially)j(Learned)d
(Concepts)h(b)q(e)f(Used?)112 b(40)468 702 y(2.7)55 b(Inductiv)o(e)15
b(Bias)818 b(41)572 748 y(2.7.1)75 b(A)12 b(Biased)j(Hyp)q(othesis)f
(Space)448 b(41)572 793 y(2.7.2)75 b(An)13 b(Un)o(biased)h(Learner)548
b(42)572 839 y(2.7.3)75 b(The)13 b(F)m(utilit)o(y)i(of)d(Bias-F)m(ree)i
(Learning)331 b(43)468 885 y(2.8)55 b(Summary)14 b(and)g(F)m(urther)f
(Reading)536 b(47)572 930 y(Exercises)907 b(49)468 976
y(2.9)55 b(References)883 b(52)399 1043 y Fd(3)41 b Fj(Decision)16
b(T)l(ree)g(Learning)671 b Fc(55)468 1097 y(3.1)55 b(In)o(tro)q
(duction)851 b(55)468 1143 y(3.2)55 b(Decision)16 b(T)m(ree)c(Represen)
o(tation)570 b(56)468 1188 y(3.3)55 b(Appropriate)15
b(Problems)g(for)d(Decision)k(T)m(ree)c(Learning)228
b(57)468 1234 y(3.4)55 b(The)13 b(Basic)h(Decision)i(T)m(ree)c
(Learning)j(Algorithm)307 b(58)572 1280 y(3.4.1)75 b(Whic)o(h)14
b(A)o(ttribute)g(Is)f(The)g(Best)g(Classi\014er?)237
b(58)572 1325 y(3.4.2)75 b(An)13 b(Illustrativ)o(e)i(Example)502
b(62)468 1371 y(3.5)55 b(Hyp)q(othesis)15 b(Space)f(Searc)o(h)g(in)g
(Decision)h(T)m(ree)d(Learning)199 b(65)468 1417 y(3.6)55
b(Inductiv)o(e)15 b(Bias)f(in)g(Decision)h(T)m(ree)e(Learning)373
b(66)572 1462 y(3.6.1)75 b(Restriction)15 b(Biases)f(and)g(Preference)f
(Biases)226 b(67)572 1508 y(3.6.2)75 b(Wh)o(y)13 b(Prefer)g(Short)h
(Hyp)q(otheses?)385 b(68)468 1554 y(3.7)55 b(Issues)14
b(in)g(Decision)h(T)m(ree)e(Learning)517 b(70)572 1599
y(3.7.1)75 b(Av)o(oiding)15 b(Ov)o(er\014tting)f(the)f(Data)398
b(70)572 1645 y(3.7.2)75 b(Incorp)q(orating)15 b(Con)o(tin)o(uous-V)m
(alued)h(A)o(ttributes)161 b(76)572 1691 y(3.7.3)75 b(Alternativ)o(e)14
b(Measures)g(for)f(Selecting)i(A)o(ttributes)143 b(77)572
1736 y(3.7.4)75 b(Handling)16 b(T)m(raining)g(Examples)f(with)g
(Missing)726 1782 y(A)o(ttribute)e(V)m(alues)627 b(79)572
1828 y(3.7.5)75 b(Handling)15 b(A)o(ttributes)f(with)f(Di\013ering)j
(Costs)216 b(79)468 1873 y(3.8)55 b(Summary)14 b(and)g(F)m(urther)f
(Reading)536 b(80)572 1919 y(Exercises)907 b(81)468 1965
y(3.9)55 b(References)883 b(83)399 2032 y Fd(4)41 b Fj(Arti\014cial)15
b(Neural)g(Net)o(w)o(orks)601 b Fc(86)468 2086 y(4.1)55
b(In)o(tro)q(duction)851 b(86)572 2131 y(4.1.1)75 b(Biological)16
b(Motiv)n(ation)548 b(87)468 2177 y(4.2)55 b(Neural)14
b(Net)o(w)o(ork)f(Represen)o(tations)516 b(88)468 2223
y(4.3)55 b(Appropriate)15 b(Problems)g(for)d(Neural)i(Net)o(w)o(ork)f
(Learning)189 b(90)468 2268 y(4.4)55 b(P)o(erceptrons)862
b(91)572 2314 y(4.4.1)75 b(Represen)o(tational)16 b(P)o(o)o(w)o(er)d
(of)f(P)o(erceptrons)256 b(92)572 2360 y(4.4.2)75 b(The)13
b(P)o(erceptron)g(T)m(raining)i(Rule)400 b(93)572 2405
y(4.4.3)75 b(Gradien)o(t)14 b(Descen)o(t)g(and)f(the)h(Delta)g(Rule)279
b(94)p -95 2696 V -7 2783 3 75 v 244 2684 a Fh(00127)10
b(6)367 2670 y Fg(3)p 367 2676 16 2 v 367 2697 a(8)395
2684 y Ff(\002)e Fh(9)453 2670 y Fg(1)p 453 2676 V 453
2697 a(4)485 2684 y Fh(P)o(ages)i(created)g(for)h(McGra)o(w-Hill)g(b)o
(y)g(T)m(om)g(Mitc)o(hell)69 b(JAN.)13 b(2,)e(1997)p
1896 2783 3 75 v 1910 2696 75 3 v eop
%%Page: 4 4
4 3 bop -95 -61 75 3 v -7 -75 3 75 v 933 -100 a Fm(iv)p
1896 -75 V 1910 -61 75 3 v 225 116 a Fl(iv)41 b Fg(CONTENTS)572
200 y Fc(4.4.4)75 b(Remarks)740 b(100)468 245 y(4.5)55
b(Multila)o(y)o(er)18 b(Net)o(w)o(orks)c(and)h(the)g
Fb(Ba)o(ckpr)o(op)n(a)o(ga)n(tion)572 291 y Fc(Algorithm)870
b(100)572 337 y(4.5.1)75 b(A)12 b(Di\013eren)o(tiabl)q(e)k(Threshold)e
(Unit)350 b(101)572 382 y(4.5.2)75 b(The)13 b Fb(Ba)o(ckpr)o(op)n(a)o
(ga)n(tion)e Fc(Algorithm)297 b(102)572 428 y(4.5.3)75
b(Deriv)n(ation)15 b(of)e(the)g Fb(Ba)o(ckpr)o(op)n(a)o(ga)n(tion)e
Fc(Rule)172 b(106)468 474 y(4.6)55 b(Remarks)14 b(on)g(the)f
Fb(Ba)o(ckpr)o(op)n(a)o(ga)n(tion)e Fc(Algorithm)250
b(109)572 519 y(4.6.1)75 b(Con)o(v)o(ergence)14 b(and)f(Lo)q(cal)h
(Minima)358 b(109)572 565 y(4.6.2)75 b(Represen)o(tational)17
b(P)o(o)o(w)o(er)e(of)f(F)m(eedforw)o(ard)726 611 y(Net)o(w)o(orks)730
b(110)572 656 y(4.6.3)75 b(Hyp)q(othesis)14 b(Space)g(Searc)o(h)g(and)g
(Inductiv)o(e)g(Bias)142 b(111)572 702 y(4.6.4)75 b(Hidden)14
b(La)o(y)o(er)f(Represen)o(tations)383 b(111)572 748
y(4.6.5)75 b(Generalization,)17 b(Ov)o(er\014tting)f(and)f(Stopping)726
793 y(Criterion)736 b(115)468 839 y(4.7)55 b(An)13 b(Illustrativ)o(e)j
(Example:)e(F)m(ace)f(Recognition)327 b(117)572 885 y(4.7.1)75
b(The)13 b(T)m(ask)728 b(119)572 930 y(4.7.2)75 b(Design)14
b(Choices)634 b(119)572 976 y(4.7.3)75 b(Learned)13 b(Hidden)i
(Represen)o(tations)341 b(121)468 1022 y(4.8)55 b(Adv)n(anced)15
b(T)m(opics)e(in)h(Arti\014cial)h(Neural)f(Net)o(w)o(orks)255
b(122)572 1067 y(4.8.1)75 b(Alternativ)o(e)14 b(Error)f(F)m(unctions)
421 b(122)572 1113 y(4.8.2)75 b(Alternativ)o(e)14 b(Error)f(Minimizati)
q(on)j(Pro)q(cedures)162 b(124)572 1159 y(4.8.3)75 b(Recurren)o(t)13
b(Net)o(w)o(orks)552 b(125)572 1204 y(4.8.4)75 b(Dynamically)16
b(Mo)q(difying)g(Net)o(w)o(ork)c(Structure)169 b(127)468
1250 y(4.9)55 b(Summary)14 b(and)g(F)m(urther)f(Reading)517
b(128)572 1296 y(Exercises)888 b(130)468 1341 y(4.10)36
b(References)864 b(131)399 1438 y Fd(5)41 b Fj(Ev)m(aluating)17
b(Hyp)q(otheses)655 b Fc(134)468 1492 y(5.1)55 b(Motiv)n(ation)859
b(134)468 1538 y(5.2)55 b(Estimating)15 b(Hyp)q(othesis)g(Accuracy)490
b(135)572 1583 y(5.2.1)75 b(Sample)14 b(Error)f(and)h(T)m(rue)f(Error)
393 b(136)572 1629 y(5.2.2)75 b(Con\014dence)15 b(In)o(terv)n(als)h
(for)e(Discrete-V)m(alued)726 1675 y(Hyp)q(otheses)696
b(137)468 1720 y(5.3)55 b(Basics)15 b(of)d(Sampling)k(Theory)590
b(139)572 1766 y(5.3.1)75 b(Error)14 b(Estimation)i(and)e(Estimating)i
(Binomial)726 1812 y(Prop)q(ortions)690 b(140)572 1857
y(5.3.2)75 b(The)13 b(Binomial)i(Distribution)443 b(140)572
1903 y(5.3.3)75 b(Mean)13 b(and)h(V)m(ariance)562 b(142)572
1949 y(5.3.4)75 b(Estimators,)13 b(Bias)h(and)g(V)m(ariance)377
b(143)572 1994 y(5.3.5)75 b(Con\014dence)14 b(In)o(terv)n(als)547
b(144)572 2040 y(5.3.6)75 b(Tw)o(o-Sided)14 b(and)f(One-Sided)i(Bounds)
311 b(147)468 2086 y(5.4)55 b(A)13 b(General)h(Approac)o(h)g(for)f
(Deriving)i(Con\014dence)g(In)o(terv)n(als)125 b(148)572
2131 y(5.4.1)75 b(Cen)o(tral)13 b(Limit)h(Theorem)495
b(148)468 2177 y(5.5)55 b(Di\013erence)15 b(in)f(Error)f(of)g(Tw)o(o)f
(Hyp)q(otheses)392 b(149)572 2223 y(5.5.1)75 b(Hyp)q(othesis)14
b(T)m(esting)567 b(151)468 2268 y(5.6)55 b(Comparing)15
b(Learning)g(Algorithms)495 b(152)572 2314 y(5.6.1)75
b(P)o(aired)14 b Fa(t)e Fc(T)m(ests)652 b(154)572 2360
y(5.6.2)75 b(Practical)14 b(Considerations)479 b(156)468
2405 y(5.7)55 b(Summary)14 b(and)g(F)m(urther)f(Reading)517
b(157)p -95 2696 V -7 2783 3 75 v 244 2684 a Fh(00127)10
b(6)367 2670 y Fg(3)p 367 2676 16 2 v 367 2697 a(8)395
2684 y Ff(\002)e Fh(9)453 2670 y Fg(1)p 453 2676 V 453
2697 a(4)485 2684 y Fh(P)o(ages)i(created)g(for)h(McGra)o(w-Hill)g(b)o
(y)g(T)m(om)g(Mitc)o(hell)69 b(JAN.)13 b(2,)e(1997)p
1896 2783 3 75 v 1910 2696 75 3 v eop
%%Page: 5 5
5 4 bop -95 -61 75 3 v -7 -75 3 75 v 938 -100 a Fm(v)p
1896 -75 V 1910 -61 75 3 v 1433 116 a Fg(CONTENTS)41
b Fl(v)572 199 y Fc(Exercises)888 b(158)468 245 y(5.8)55
b(References)864 b(159)399 312 y Fd(6)41 b Fj(Ba)o(y)o(esian)16
b(Learning)752 b Fc(160)468 366 y(6.1)55 b(In)o(tro)q(duction)832
b(160)468 412 y(6.2)55 b(Ba)o(y)o(es)14 b(Theorem)781
b(162)572 458 y(6.2.1)75 b(An)13 b(Example)678 b(163)468
503 y(6.3)55 b(Ba)o(y)o(es)14 b(Theorem)f(and)h(Concept)f(Learning)396
b(165)572 549 y(6.3.1)75 b(Brute)13 b(F)m(orce)g(Ba)o(y)o(es)h(Concept)
f(Learning)268 b(165)572 595 y(6.3.2)75 b(MAP)13 b(Hyp)q(otheses)h(and)
f(Consisten)o(t)i(Learners)172 b(168)468 640 y(6.4)55
b(Maxim)o(um)17 b(Lik)o(eliho)q(o)q(d)h(and)e(Least)f(Squared)h(Error)
572 686 y(Hyp)q(otheses)850 b(169)468 732 y(6.5)55 b(Maxim)o(um)17
b(Lik)o(eliho)q(o)q(d)h(Hyp)q(otheses)d(for)g(Predicting)572
777 y(Probabili)q(ties)831 b(174)572 823 y(6.5.1)75 b(Gradien)o(t)14
b(Searc)o(h)h(to)e(Maximize)i(Lik)o(eliho)q(o)r(d)h(in)e(a)726
869 y(Neural)g(Net)700 b(176)468 914 y(6.6)55 b(Minim)o(um)15
b(Description)h(Length)e(Principle)382 b(178)468 960
y(6.7)55 b(Ba)o(y)o(es)14 b(Optimal)g(Classi\014er)629
b(180)468 1006 y(6.8)55 b(Gibbs)15 b(Algorithm)758 b(182)468
1051 y(6.9)55 b(Naiv)o(e)14 b(Ba)o(y)o(es)g(Classi\014er)672
b(183)572 1097 y(6.9.1)75 b(An)13 b(Illustrativ)o(e)i(Example)483
b(184)468 1143 y(6.10)36 b(An)13 b(Example:)i(Learning)f(to)f(Classify)
h(T)m(ext)379 b(186)572 1188 y(6.10.1)56 b(Exp)q(erimen)o(tal)15
b(Results)527 b(188)468 1234 y(6.11)36 b(Ba)o(y)o(esian)15
b(Belief)f(Net)o(w)o(orks)616 b(190)572 1280 y(6.11.1)56
b(Conditional)16 b(Indep)q(endence)451 b(191)572 1325
y(6.11.2)56 b(Represen)o(tation)637 b(192)572 1371 y(6.11.3)56
b(Inference)735 b(193)572 1417 y(6.11.4)56 b(Learning)14
b(Ba)o(y)o(esian)h(Belief)f(Net)o(w)o(orks)302 b(194)572
1462 y(6.11.5)56 b(Gradien)o(t)12 b(Ascen)o(t)g(T)m(raining)h(of)e(Ba)o
(y)o(esian)i(Net)o(w)o(orks)92 b(195)572 1508 y(6.11.6)56
b(Learning)14 b(the)f(Structure)h(of)f(Ba)o(y)o(esian)i(Net)o(w)o(orks)