Kernel-based density ti tiestimationNuno Vasconcelos ECE Department, UCSDp,Announcementlast class, December 6, we will have “Cheetah Day”ywhat:• 4 teams, average of 5 people• each team will write a report on the 4 cheetah problems•each team will givea presentation on oneeach team will give a presentation on one of the problemswhy: • to make sure that we get the “big picture”out of all this work•presenting is always good practice2pgygp• because I am such a good person...Announcementhow much:•10% of the finalgrade (5% report 5%10% of the final grade (5% report, 5% presentation)what to talk about:• report: comparative analysis of all solutions of the problem (8 page)• as if you were writing a conference paperyg pp• presentation: will be on one single problem• review what solution was• what did this problem taught us about learning?• what “tricks” did we learn solving it?3• how well did this solution do compared to others?Announcementdetails:•get together and form groupsget together and form groups• let me know what they are by Tuesday (November 20) (email is fine)• I will randomly assign the problem on which each group has to be expert• prepare a talk for 15min (7 or 8 slides)• feel free to use my solutions, your results, create new results, whatever...4Plan for todaywe have talked a lot about the BDR and methods based on density estimationypractical densities are not well approximated by simple probability modelstoday: what can we do if have complicated densities?• use the BDR• use better probability density models!5Non-parametric density estimates6Binomial random variable N 10 100 1,000 …Var[P] <0 0250 00250 000257Var[P] < 0.0250.00250.00025Histogram this means that k/n is a very good estimate of Pon the other hand, from the mean value theorem, if PX(x)is ,,X()continuousthis is easiest to see in 1DPX(ε)PX(x)• can always find a box such thatthe integral of the function is equalto that of the boxPX(ε)• since PX(x) is continuous theremust be a εsuch that PX(ε)is the box heightxε8xεRHistogram henceitiitfP()id iRillusing continuity of PX(x)again and assuming R is smallthis is the histogramit is the simplest possible non-parametric estimatorcan be generalized into kernel-based density estimator9Kernel density estimates10Kernel density estimatesthis means that the histogram can be written ashi h i i l t twhich is equivalent to:• “put a box around X for each Xithat lands on the hypercube”• can be seen as a very crude form of interpolation•better interpolation if contribution ofXi•better interpolation if contribution of Xidecreases with distance to Xconsider other windowsφ(x)xxxx11x1x2x3xWindowswhat sort of functions are valid windows?note thatP(x)is apdf if and only ifnote that PX(x)is a pdf if and only ifsincethese conditions hold if φ(x) is itself a pdf12Gaussian kernelprobably the most popular in practicetthtP()lbnote that PX(x)can also be seen as a sum of pdfs centered on the Xiwhen φ(x) is symmetric in X and Xi13Gaussian kernelGaussian case can be interpreted as•sum ofnGaussians centered at theXiwithsum of nGaussians centered at the Xiwithcovariance hI• more generally, we can have a full covariancecovariancesum ofnGaussians centered at theXiwith covarianceΣsum of nGaussians centered at the Xiwith covariance ΣGaussian kernel density estimate: “approximate the pdf of X with a sum of Gaussian bumps”14Kernel bandwidthback to the generic modelhti th l fh(b d idth t )?what is the role of h(bandwidth parameter)?definingwe can write15i.e. a sum of translated replicas of δ(x)Kernel bandwidthh has two roles:1rescalethex-axis1.rescalethe x-axis2. rescale the amplitude ofδ(x)this implies that for large h:pg1. δ(x) has low amplitude2. iso-contours of h are quite distant from zero (xlarge beforeφ(x/h)changes significantly fromφ(0))(xlarge before φ(x/h)changes significantly from φ(0))16Kernel bandwidthfor small h:1δ(x)has large amplitude1.δ(x)has large amplitude2. iso-contours of h are quite close to zero (x small before φ(x/h) changes significantly from φ(0))what is the impact of this on the quality of the density 17estimates?Kernel bandwidthit controls the smoothness of the estimate•ash goes to zero we have a sum of delta functions(very“spiky”as h goes to zero we have a sum of delta functions(very spiky approximation)• as h goes to infinity we have a sum of constant functions(approximation by a constant)(approximation by a constant)• in between we get approximations that are gradually more smooth18Kernel bandwidthwhy does this matter?when the density estimates are plugged into the BDRwhen the density estimates are plugged into the BDRsmoothness of estimates determines the smoothness of the boundariesless smoothmore smooththisaffects the probability of error!19this affects the probability of error!Convergencesince Px(x) depends on the sample points Xi, it is a random variableas we add more points, the estimate should get “better”the question is then whether the estimate ever convergesqgthis is no different than parameter estimationas before, we talk about convergence in probability,gpy20Convergence of the meanfrom the linearity of PX(x) on the kernels21Convergence of the meanhencethi i thlti fP()ithδ()this is the convolution of PX(x)with δ(x)it is a blurred version (“low-pass filtered”) unless h = 0ithiδ()tthDi dlt din this case δ(x-v)converges to the Dirac delta and so22Convergence of the variancesince the Xiare iid23Convergencein summarythis means that:•to obtain small bias we needh~0to obtain small bias we need h 0• to obtain small variance we need h infinite24Convergenceintuitively makes sense•h~0means a Dirac around each pointh 0means a Dirac around each point• can approximate any function arbitrarily well• there is no bias• but if we get a different sample, the estimate is likely to be very different•there islarge variancethere is large variance• as before, variance can be decreased by getting a larger sample• but, for fixed n, smaller h always means greater variabilityexample: fit to N(0,I) using h = h1/n1/225Examplesmall h: spikyneed a lot ofneed a lot of points to converge (variance)large h: approximateppN(0,I) with a sum of Gaussians of larger covariancelarger covariancewill never have zero error (bias)26Optimal bandwidthwe would like• h ~ 0 to guarantee zero biasg• zero variance as n goes to infinitysolution:• make h a function of n