effloc.ps

Locally weighted polynomial regression LWPR is a popular instance based al gorithm for learning c

FF14C06C13E014F0387801F838F00078A300701370007813F0381E03C03807FF00151B7F
9118>I<B4FCA2121FA9EB0FC0EB31E0EB40F0EB80F8A21300AB38FFE7FFA2181D7F9C1B>
I<121E123FA4121EC7FCA6127FA2121FAEEAFFC0A20A1E7F9D0E>I<B4FCA2121FA9EB03
FCA2EB01C0EB0300130E5B5B137813FC13BE131F7F1480EB07C0EB03E0130138FFE7FEA2
171D7F9C19>107 D<B4FCA2121FB3A7EAFFE0A20B1D7F9C0E>I<39FF0FC07E903831E18F
3A1F40F20780D980FC13C0A2EB00F8AB3AFFE7FF3FF8A225127F9128>I<38FF0FC0EB31
E0381F40F0EB80F8A21300AB38FFE7FFA218127F911B>I<EA01FC380F0780381C01C000
3C13E0387800F0A200F813F8A6007813F0A2383C01E0381E03C0380F07803801FC001512
7F9118>I<38FF3F80EBE1E0381F80F0EB0078147C143C143EA6143C147C1478EB80F0EB
C1E0EB3F0090C7FCA6EAFFE0A2171A7F911B>I<EAFE3E1347381E8F80A3381F070090C7
FCAAEAFFE0A211127F9114>114 D<EA1FD8EA3078EA601812E0A2EAF000EAFF80EA7FE0
13F0EA1FF8EA07FCEA007CEAC01CA212E01318EAF830EACFC00E127E9113>I<1203A45A
A25AA2EA3FFC12FFEA1F00A9130CA4EA0F08EA0798EA03F00E1A7F9913>I<38FF07F8A2
EA1F00AC1301120F380786FFEA01F818127F911B>I<39FF8FF8FEA2391F03E030A3390F
87F06013869038C6F8E03907CC78C0A23903FC7D80EBF83D143F3901F01F00A20000131E
EBE00EA21F127F9122>119 D<38FFC7FCA2381F81C0380F83803807C700EA03EEEA01FC
5B1200137C13FEEA01DF38039F80EA070F380607C0380C03E038FF07FCA216127F9119>
I<38FFC1FCA2381F00601380000F13C0A23807C180A23803E300A213F7EA01F613FE6C5A
A21378A21330A25B1270EAF8E05BEAF9800073C7FC123E161A7F9119>I<387FFF803878
1F00EA703FEA603E5B13FC5BEA01F01203485AEBC180EA0F81121F1303003E1300EA7E07
EA7C0FB5FC11127F9115>I E /Fv 21 122 df<903A01FF803FE0011F9038E3FFF8903A
7F80FFF01E903AFE007F801FD801F849485A000349EC7F80D807F05BA30200EC3F00171E
94C7FCA4B91280A33B07F000FE003FB3A33C7FFF0FFFE3FFF8A3352A7FA939>14
D<B712F0A33903FC000FED03F81501150016781638A3EDE03C161CA302011300A2140790
B5FCA3EBFC071401A202001307A3160E1500A2161EA2161C163C167C16FC1501150FB712
F8A328297EA82D>69 D<B512FCA3D803FCC8FCB3A316E0A4150116C0A21503A21507A215
0F153FEDFF80B7FCA323297EA829>76 D<B612F815FF16C03A03FC003FE0ED0FF0ED07F8
16FC150316FEA716FC150716F8ED0FF0ED3FE090B61280EDFE0001FCC8FCB0B512F0A327
297DA82F>80 D<B612E015FE6F7E3A03FC007FE0ED0FF06F7E82150382A65E4B5AA2ED1F
E0ED7FC090B500FEC7FC15F89038FC00FC157F6F7EA26F7E82A582A3170716F8150F0307
130EB539F003FE1C923801FFF89238003FF030297DA834>82 D<B53CE07FFFF007FFF0A3
2803FC0001FEC7EA1C00A26C6C6E5C81A26C6C6F5BA26E486D13F0017F5FA26D6C486D48
5A169FA2903C1FE0070FF00380A2DAF00FEBF807010FD90E0791C7FCA2902607F81EEBFC
0EED1C0302FC151E010390393801FE1CA2DAFE78EBFF3C0101D970001338A26D6C48EB7F
F0A36E486D5AA36E486D5AA26EC76C5AA3020E6EC8FC44297FA847>87
D<3803FF80000F13F0381F01F8383F807EA280D81F001380120EC7FCA3EB0FFF90B5FC38
07FC3FEA0FE0EA3F8013005A12FEA4007E137F007F13DF393F839FFC380FFF0F3801FC03
1E1B7E9A21>97 D<EB3FF8EBFFFE3803F01F3907E03F80EA0FC0EA1F80003FEB1F00387F
000E91C7FCA25AA77EA27F003FEB01C0121F390FC003803907E007003803F01E3800FFFC
EB3FE01A1B7E9A1F>99 D<EC3FF8A31403ACEB1FE3EBFFFB3803F83F3807E00F380FC007
381F8003123FEA7F00A35AA77EA3EA3F80121F000F13073807C00F3A03F03FFF803800FF
F3EB3FC3212A7EA926>I<EB3FE03801FFF83803F07E3807C01FD80F801380001F130F00
3F14C0EA7F00140715E05AA290B5FCA290C8FCA37EA36C6C13E0121F390FC001C03907E0
03803903F81F003800FFFEEB1FF01B1B7E9A20>I<9038FF81F00003EBE7F8390FC1FE7C
381F80FC9038007C3848EB7E1048EB7F00A66C137E6C137CEB80FC380FC1F8381FFFE000
1813800038C8FCA2123C123E383FFFF86C13FF15806C14C06C14E0001F14F0383C000700
7CEB01F8481300A4007CEB01F0003C14E0001FEB07C0390FC01F803903FFFE0038007FF0
1E287E9A22>103 D<EAFFE0A3120FAC147F9038E1FFC09038E787E09038EE03F013F881
13F0A213E0B03AFFFE3FFF80A3212A7DA926>I<1207EA0F80EA1FC0EA3FE0A3EA1FC0EA
0F80EA0700C7FCA7EAFFE0A3120FB3A3EAFFFEA30F2B7DAA14>I<EAFFE0A3120FB3B2EA
FFFEA30F2A7DA914>108 D<3BFFC07F800FF0903AC1FFE03FFC903AC383F0707E3B0FC6
03F8C07F903ACC01F9803F01D8D9FF00138001F05BA201E05BB03CFFFE1FFFC3FFF8A335
1B7D9A3A>I<38FFC07F9038C1FFC09038C787E0390FCE03F013D88113F0A213E0B03AFF
FE3FFF80A3211B7D9A26>I<EB3FE03801FFFC3803F07E390FC01F80391F800FC0003F14
E0EB00074814F0A34814F8A86C14F0A2393F800FE0A2001F14C0390FC01F803907F07F00
3801FFFC38003FE01D1B7E9A22>I<38FFC1F0EBC7FCEBCE3E380FD87FA213F0143E141C
EBE000B0B5FCA3181B7E9A1C>114 D<3803FE30380FFFF0EA1E03EA380048137012F0A2
7E00FE1300EAFFE0EA7FFEEBFF806C13E06C13F0000713F8C6FCEB07FCEA600000E0137C
143C7E14387E6C137038FF01E038F7FFC000C11300161B7E9A1B>I<1370A413F0A31201
1203A21207381FFFF0B5FCA23807F000AD1438A61203EBF870000113603800FFC0EB1F80
15267FA51B>I<3AFFFE03FF80A33A0FF0007800000714706D13F000035CEBFC0100015C
A26C6C485AA2EBFF07017F90C7FC148FEB3F8E14CEEB1FDCA2EB0FF8A36D5AA26D5AA26D
5AA2495AA2EA3807007C90C8FCEAFE0F130E5B133CEA7C78EA3FE0EA0F8021277F9A24>
121 D E end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 300dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 15 116 2025 5 v 98 233 a Fv(E\016cien)n(t)21
b(Lo)r(cally)h(W)-6 b(eigh)n(ted)22 b(P)n(olynomial)f(Regression)h
(Predictions)p 15 324 V 181 491 a Fu(Andrew)16 b(W.)g(Mo)q(ore)167
537 y Ft(Rob)q(otics)d(Institute)i(and)118 582 y(Sc)o(ho)q(ol)f(of)f
(Computer)g(Science)123 628 y(Carnegie)h(Mellon)f(Univ)o(ersit)o(y)174
674 y(Pittsburgh,)h(P)m(A)g(15213)214 719 y(a)o([e-mail])o(u.edu)881
491 y Fu(Je\013)h(Sc)o(hneider)863 537 y Ft(Rob)q(otics)f(Institute)779
582 y(Carnegie)g(Mellon)g(Univ)o(ersit)o(y)831 628 y(Pittsburgh,)g(P)m
(A)f(15213)837 674 y(sc)o([e-mail])o(u.edu)1578 491
y Fu(Kan)j(Deng)1519 537 y Ft(Rob)q(otics)e(Institute)1436
582 y(Carnegie)g(Mellon)f(Univ)o(ersit)o(y)1487 628 y(Pittsburgh,)h(P)m
(A)g(15213)1515 674 y([e-mail])o(u.edu)395 866 y Fs(Abstract)98
970 y Ft(Lo)q(cally)f(w)o(eigh)o(ted)h(p)q(olynomial)c(regression)98
1015 y(\(L)-5 b(WPR\))31 b(is)g(a)g(p)q(opular)g(instance-based)i(al-)
98 1061 y(gorithm)22 b(for)h(learning)g(con)o(tin)o(uous)h(non-linear)
98 1107 y(mappings.)32 b(F)m(or)18 b(more)g(than)i(t)o(w)o(o)e(or)h
(three)i(in-)98 1152 y(puts)16 b(and)e(for)h(more)f(than)h(a)f(few)h
(thousand)g(dat-)98 1198 y(ap)q(oin)o(ts)22 b(the)i(computational)c
(exp)q(ense)k(of)e(pre-)98 1244 y(dictions)17 b(is)g(daun)o(ting.)27
b(W)m(e)17 b(discuss)i(dra)o(wbac)o(ks)98 1289 y(with)10
b(previous)h(approac)o(hes)h(to)e(dealing)g(with)g(this)98
1335 y(problem,)i(and)i(presen)o(t)h(a)f(new)g(algorithm)d(based)98
1381 y(on)27 b(a)f(m)o(ultiresolution)f(searc)o(h)j(of)e(a)h(quic)o
(kly-)98 1426 y(constructible)d(augmen)o(ted)d Fr(k)p
Ft(d-tree.)45 b(Without)98 1472 y(needing)24 b(to)f(rebuild)g(the)g
(tree,)k(w)o(e)c(can)g(mak)o(e)98 1518 y(fast)17 b(predictions)h(with)e
(arbitrary)h(lo)q(cal)g(w)o(eigh)o(t-)98 1563 y(ing)23
b(functions,)i(arbitrary)e(k)o(ernel)h(widths)f(and)98
1609 y(arbitrary)g(queries.)47 b(The)24 b(pap)q(er)g(b)q(egins)f(with)
98 1655 y(a)h(new,)i(faster,)h(algorithm)22 b(for)h(exact)i(L)-5
b(WPR)98 1700 y(predictions.)35 b(Next)19 b(w)o(e)h(in)o(tro)q(duce)g
(an)e(appro)o(x-)98 1746 y(imation)j(that)i(ac)o(hiev)o(es)h(up)g(to)f
(a)h(t)o(w)o(o-orders-)98 1792 y(of-magnitude)17 b(sp)q(eedup)k(with)e
(negligible)f(accu-)98 1837 y(racy)24 b(losses.)48 b(Increasing)24
b(a)f(certain)h(appro)o(xi-)98 1883 y(mation)13 b(parameter)i(ac)o
(hiev)o(es)h(greater)g(sp)q(eedups)98 1929 y(still,)c(but)i(with)f(a)h
(corresp)q(ondingly)g(larger)f(accu-)98 1974 y(racy)h(degradation.)k
(This)c(is)g(nev)o(ertheless)i(useful)98 2020 y(during)e(op)q(erations)
g(suc)o(h)g(as)g(the)h(early)f(stages)h(of)98 2066 y(mo)q(del)e
(selection)i(and)f(lo)q(cating)f(optima)f(of)i(a)g(\014t-)98
2111 y(ted)k(surface.)28 b(W)m(e)16 b(also)h(sho)o(w)f(ho)o(w)h(the)g
(appro)o(x-)98 2157 y(imations)d(can)i(p)q(ermit)f(real-time)f
(query-sp)q(eci\014c)98 2203 y(optimization)j(of)i(the)h(k)o(ernel)f
(width.)35 b(W)m(e)19 b(con-)98 2248 y(clude)c(with)f(a)g(brief)h
(discussion)g(of)f(p)q(oten)o(tial)g(ex-)98 2294 y(tensions)e(for)e
(tractable)h(instance-based)i(learning)98 2340 y(on)f(datasets)h(that)f
(are)g(to)q(o)g(large)g(to)g(\014t)g(in)g(a)f(com-)98
2385 y(puter's)k(main)d(memory)m(.)15 2533 y Fs(1)56
b(Lo)r(cally)17 b(W)-5 b(eigh)n(ted)18 b(P)n(olynomial)99
2591 y(Regression)15 2691 y Ft(Lo)q(cally)23 b(w)o(eigh)o(ted)i(p)q
(olynomial)c(regression)26 b(\(L)-5 b(WPR\))24 b(is)15
2737 y(a)g(form)f(of)h(instance-based)h(\(a.k.a)e(memory-based\))g(al-)
1065 866 y(gorithm)16 b(for)h(learning)g(con)o(tin)o(uous)g(non-linear)
g(mappings)1065 912 y(from)g(real-v)n(alued)h(input)h(v)o(ectors)h(to)f
(real-v)n(alued)f(output)1065 957 y(v)o(ectors.)g(It)9
b(is)g(particularly)g(appropriate)h(for)f(learning)f(com-)1065
1003 y(plex)14 b(highly)g(non-linear)f(functions)i(of)f(up)g(to)g(ab)q
(out)h(30)f(in-)1065 1049 y(puts)21 b(from)e(noisy)h(data.)37
b(P)o(opularized)20 b(in)g(the)h(statistics)1065 1094
y(literature)16 b(in)f(the)i(past)e(decades)j(\(Clev)o(eland)d(and)g
(Delvin,)1065 1140 y(1988;)21 b(Grosse,)h(1989;)f(A)o(tk)o(eson)g(et)f
(al.,)g(1997a\))e(it)i(is)g(en-)1065 1186 y(jo)o(ying)h(increasing)h
(use)h(in)f(applications)f(suc)o(h)i(as)f(learn-)1065
1231 y(ing)c(rob)q(ot)g(dynamics)f(\(Mo)q(ore,)j(1992;)f(Sc)o(haal)f
(and)g(A)o(tk)o(e-)1065 1277 y(son,)f(1994\))e(and)i(learning)e(pro)q
(cess)k(mo)q(dels.)24 b(Both)17 b(classi-)1065 1323 y(cal)h(and)g(Ba)o
(y)o(esian)g(linear)f(regression)j(analysis)d(to)q(ols)h(can)1065
1368 y(b)q(e)j(extended)g(to)f(w)o(ork)g(in)f(the)i(lo)q(cally)d(w)o
(eigh)o(ted)i(frame-)1065 1414 y(w)o(ork)e(\(Hastie)g(and)g
(Tibshirani,)g(1990\),)g(pro)o(viding)f(con\014-)1065
1460 y(dence)i(in)o(terv)n(als)e(on)g(predictions,)i(on)e(gradien)o(t)g
(estimates)1065 1505 y(and)c(on)g(noise)g(estimates|all)e(imp)q(ortan)o
(t)g(when)j(a)e(learned)1065 1551 y(mapping)g(is)i(to)g(b)q(e)h(used)g
(b)o(y)f(a)g(con)o(troller)g(\(A)o(tk)o(eson)h(et)g(al.,)1065
1597 y(1997b;)d(Sc)o(hneider,)j(1997\).)1065 1667 y(Let)f(us)g(review)g
(L)-5 b(WPR.)13 b(W)m(e)g(b)q(egin)g(with)h(linear)f(regression)1065
1713 y(on)g(one)g(input)g(and)g(one)g(output.)18 b(Global)11
b(linear)i(regression)1065 1759 y(\(left)f(of)f(Figure)h(1\))f(\014nds)
h(the)h(line)e(that)h(minim)o(izes)e(the)i(sum)1065 1804
y(squared)j(residuals.)j(If)c(this)g(is)f(represen)o(ted)k(as)1409
1875 y(^)-23 b Fq(y)q Ft(\()p Fq(x)p Ft(\))12 b(=)g Fq(\014)1563
1881 y Fp(0)1591 1875 y Ft(+)e Fq(\014)1656 1881 y Fp(1)1675
1875 y Fq(x)288 b Ft(\(1\))1065 1946 y(then)15 b Fq(\014)1183
1952 y Fp(0)1215 1946 y Ft(and)f Fq(\014)1319 1952 y
Fp(1)1352 1946 y Ft(are)g(found)g(that)g(minim)o(ize)1202
2008 y Fo(N)1187 2020 y Fn(X)1187 2110 y Fo(k)q Fp(=1)1247
2060 y Ft(\()p Fq(y)1283 2066 y Fo(k)1313 2060 y Fm(\000)f
Ft(^)-24 b Fq(y)r Ft(\()p Fq(x)1417 2066 y Fo(k)1437
2060 y Ft(\)\))1469 2043 y Fp(2)1499 2060 y Ft(=)1559
2008 y Fo(N)1543 2020 y Fn(X)1543 2110 y Fo(k)q Fp(=1)1604
2060 y Ft(\()p Fq(y)1640 2066 y Fo(k)1670 2060 y Fm(\000)9
b Fq(\014)1734 2066 y Fp(0)1763 2060 y Fm(\000)g Fq(\014)1827
2066 y Fp(1)1846 2060 y Fq(x)1870 2066 y Fo(k)1890 2060
y Ft(\))1906 2043 y Fp(2)1987 2060 y Ft(\(2\))1065 2197
y(During)j(a)h(lo)q(cally)e(w)o(eigh)o(ted)j(linear)e(regression)i
(prediction,)1065 2243 y(a)d(query)h(p)q(oin)o(t,)f Fu(x)1354
2249 y Fp(query)1437 2243 y Ft(,)g(is)h(supplied.)17
b(A)11 b(linear)h(map)d(is)j(con-)1065 2288 y(structed,)j(but)f(it)f
(is)h(no)o(w)f(m)o(uc)o(h)g(more)f(strongly)i(in\015uenced)1065
2334 y(b)o(y)e(datap)q(oin)o(ts)h(that)g(lie)f(close)h(to)g(the)g
(query)g(p)q(oin)o(t)f(accord-)1065 2380 y(ing)i(to)g(some)g(scaled)h
(Euclidean)g(distance)g(metric.)20 b(This)14 b(is)1065
2425 y(ac)o(hiev)o(ed)j(b)o(y)g(\(for)f(this)h(prediction)g(only\))f(w)
o(eigh)o(ting)f(eac)o(h)1065 2471 y(datap)q(oin)o(t)k(according)h(to)g
(its)g(distance)g(to)g(the)h(query:)30 b(a)1065 2517
y(p)q(oin)o(t)13 b(v)o(ery)h(close)g(to)f(the)i(query)f(gets)g(a)f(w)o
(eigh)o(t)g(of)g(one)h(and)1065 2562 y(a)19 b(p)q(oin)o(t)g(far)g(a)o
(w)o(a)o(y)f(gets)i(a)f(w)o(eigh)o(t)g(of)f(zero.)35
b(A)20 b(common)1065 2608 y(w)o(eigh)o(ting)13 b(function)g(is)h
(Gaussian:)1167 2679 y Fq(w)1197 2685 y Fo(k)1258 2679
y Ft(=)42 b(w)o(eigh)o(t)14 b(of)f(datap)q(oin)o(t)g
Fu(x)1725 2685 y Fo(k)1258 2737 y Ft(=)42 b(exp)q(\()p
Fm(\000)p Ft(Distance)1601 2719 y Fp(2)1619 2737 y Ft(\()p
Fu(x)1661 2743 y Fo(k)1681 2737 y Fq(;)7 b Fu(x)1725
2743 y Fp(query)1808 2737 y Ft(\))p Fq(=)p Ft(2)p Fq(K)1904
2720 y Fp(2)1922 2737 y