Non-Parametric TechniquesParametric versus Non-parametricTwo types of nonparametric methodsHistograms are the heart of density estimationAn example of a histogram (feature called negative slope)EntropyHistogram for Horizontal slopeDensity EstimationRelating P to histogram valueBinomial DistributionSpace average of p(x)Practical and Theoretical IssuesFormulation when unlimited samples are availableNecessary conditions for convergence: pn(x)  p(x)Two Methods for Estimating DensityParzen Window MethodParzen Window using hypercubesProperties of Window FunctionEffect of window-width on estimate pn(x)Conditions for Convergence of EstimateConvergence of Mean and VarianceExample of Parzen Window on simple casesParzen Window Estimates of Bimodal DistributionClassification based on Parzen WindowsParzen Window ConclusionProbabilistic Neural NetworksProbabilistic Neural NetworksNormalizationNormalization ExampleActivation FunctionPNN Training AlgorithmPNN Classification AlgorithmParzen/PNN Classifier Stage 1PNN Stage 2: outputs are sparsely connectedkn-Nearest neighbor estimationChoice of knExamples of estimated pdfs using k nearest neighbor estimateComparison of Parzen and k nn estimates in one-dimensionExamples of kn-Nearest-Neighbor EstimationEstimation of a-posteriori probabilitiesCSE 555: Srihari 0Non-Parametric TechniquesGenerative and Discriminative MethodsDensity EstimationCSE 555: Srihari 1Parametric versus Non-parametric1. Parametric • densities are uni-modal have a single local maximum • practical problems involve multi-modal densities2. Nonparametric• arbitrary distributions • without assuming forms of the underlying densitiesGenerative DiscriminativeCSE 555: Srihari 2Two types of nonparametric methods1. Generative:Estimate class-conditional density p(x | ωj )1. Parzen Windows2. kn-nearest neighbor estimation2. Discriminative:Bypass density estimation and go directly to compute a-posteriori probability P(ωj/x )1. nearest neighbor rule2. k-nearest neighbor ruleCSE 555: Srihari 3Histograms are the heart of density estimationAn example of a histogram (feature called negative slope)CSE 555: Srihari 4More HistogramsEntropyNo of black pixelsExterior contours Interior contoursCSE 555: Srihari 5Histogram for Horizontal slopeHistogram for Positive slopeCSE 555: Srihari 6Density Estimation• Basic idea of estimating an unknown pdf:• Probability P that a vector x will fall in region R is:• P is a smoothed (or averaged) version of the density function p(x)• We can estimate the smoothed value of p by estimating the probability P∫ℜ= (1) 'dx)'x(pPCSE 555: Srihari 7Relating P to histogram value• If we have a sample of size n, • the probability that k points fall in R is given by the binomial law:• and the expected value (mean) for k is:E[k] = nP (3)(2) )P1(P knPknkk−−⎟⎟⎠⎞⎜⎜⎝⎛=CSE 555: Srihari 8Binomial Distribution• This binomial distribution for kpeaks very sharply about the mean• Therefore, the ratio k/n is a good estimate for the probability P and hence for the density function p• Especially accurate when n is very large (2) )P1(P knPknkk−−⎟⎟⎠⎞⎜⎜⎝⎛=nP k≈CSE 555: Srihari 9Space average of p(x)• If p(x) is continuous and the region R is so small that p does not vary significantly within it, we can write:• where x is a point within R and • V the volume enclosed by R(4) )(')'(∫ℜ≅= VxpdxxpPCSE 555: Srihari 10Expression for p(x) from histogramCombining equations (1), (3) and (4) ∫ℜ= (1) 'dx)'x(pPE[k] = nP (3)(4) )(')'(∫ℜ≅= VxpdxxpPyieldsVn/k)x(p ≅CSE 555: Srihari 11(2) )P1(P knPknkk−−⎟⎟⎠⎞⎜⎜⎝⎛=CSE 555: Srihari 12Practical and Theoretical Issues• The fraction is a space averaged value of p(x)• p(x) is obtained only if V approaches zeroThis is the case where no samples are included in R and our estimate p(x) = 0• Practically, V cannot be allowed to become small since the number of samples is always limited• One will have to accept a certain amount of variance in the ratio k/nVn/k)x(p ≅CSE 555: Srihari 13Formulation when unlimited samples are availableTheoretically, if an unlimited number of samples is available, we can circumvent this difficultyTo estimate the density at x, we form a sequence of regionsR1, R2,…containing x: the first region contains one sample, the second two samples and so on.Let Vnbe the volume of Rn, knthe number of samples falling in Rnand pn(x) be the nthestimate for p(x):(7)nnnVnkxp/)( ≅CSE 555: Srihari 14Necessary conditions for convergence: pn(x) Æ p(x)0n/klim )3klim )20Vlim )1nnnnnn=∞==∞→∞→∞→nnnVnkxp/)( ≅Two different ways of obtaining sequences of regions that satisfy these conditions:(a) Shrink an initial region where Vn= 1/√n and show that This is called “the Parzen-window estimation method”(b) Specify knas some function of n, such as kn= √n; the volume Vnisgrown until it encloses knneighbors of x. This is called “the kn-nearest neighbor estimation method”)x(p)x(pnn∞→→CSE 555: Srihari 15Two Methods for Estimating DensityWe are estimating density at center of squareMethod 1: start with large volume centered at point and shrink it according tonVn1=Method 2: start with large volume centered at point and shrink it according tonkn=CSE 555: Srihari 16Parzen Window Method• Unit hypercube function⎪⎩⎪⎨⎧=≤=otherwise 0d , 1,...j 21u 1(u):function windowfollowing thebe (u) jϕϕLet1uu1u2u3CSE 555: Srihari 17Parzen Window using hypercubes• Estimate density assuming that regionRnis a d-dimensional hypercube) of edge theoflength :(h nnℜ=dnnhVotherwise 0 at x centeredV volumeof hypercube within falls xif 1ni==⎟⎟⎠⎞⎜⎜⎝⎛−nihxxϕhnx1=ϕ0=ϕ∑=⎟⎟⎠⎞⎜⎜⎝⎛−=nininhxxk1 :hypercubein samples of No.ϕ⎟⎟⎠⎞⎜⎜⎝⎛−==∑=nininnnnhxxVnVnkxpϕ1 11 /)(xiCSE 555: Srihari 18Properties of Window Functionpn(x) estimates p(x) as an average of functions of x and the samples xiWindow function is an interpolation function•Functions ϕcan be general as long as pn(x) is a legitimate density function, i.e., require that⎟⎟⎠⎞⎜⎜⎝⎛−=∑=nininnhxxVnxpϕ1 11)(Can use a Gaussian that is circularly symmetric with variance hnCSE 555: Srihari 19Effect of window-width on estimate pn(x))(1)( then 1)( 1ininnnnnxxnxphxVxLet −=⎟⎟⎠⎞⎜⎜⎝⎛=∑=δϕδGaussianwindowswithdecreasing widthsParzen windowestimates usingfive samplesFor any