Linear Discriminant FunctionsIntroductionLinear discriminant function definitionTwo-category caseHyperplaneHyperplane GeometryMulticategory CaseUsing dichotomies for four-class problemMulti-category case: Linear MachineTwo class case of Linear MachineLinear Machine Boundariesfor 3 and 5-class problemsLinear Machines and Unimodal DistributionsGeneralized Linear Discriminant FunctionsPolynomial Discriminant Functionsf functionQuadratic as Generalized LDFTransforming 1-d to 3-dCase of a=(-1,1,2)Augmented Feature VectorLinear Discriminant Functions• Linear Discriminant Functions and Decisions Surfaces• Generalized Linear Discriminant FunctionsSrihari: CSE 555Introduction• Parametric Methods• Underlying pdfs are known • Training samples used to estimate pdf parameters • Linear Discriminant Functions• Forms of discriminant functions are known• Similar to non-parametric techniques• Sub-optimal, but simple to useSrihari: CSE 555Linear discriminant function definitionA linear combination of components of xg(x) = wtx+ w0(1)where w is the weight vectorw0the bias or threshold weightIn general there are c such functionsSrihari: CSE 555Two-category case• With a discriminant function of the form (1) use:• Decide ω1if g(x) = wtx+ w0> 0 and ω2if g(x) = wtx+ w0< 0⇔Decide ω1if wtx> -w0and ω2otherwiseIf g(x) = 0 then x is assigned to either classEach unit is shown as having inputs and outputs. The input units exactly output thesame values as the inputs (except the bias unit which outputs a constant 1). The output unit emits a 1 if the sum of its weighted inputs is greater than zero and -1 otherwiseSimple Linear Two Category ClassifierSrihari: CSE 555Hyperplane• The equation g(x) = 0 defines the decision surface that separates points assigned to the category ω1from points assigned to the category ω2• When g(x) is linear, the decision surface is a hyperplane• If x1and x2are both on the hyperplane then• Or w is normal to any vector lying on the hyperplane0)(210201=−+=+xxworwxwwxwtttSrihari: CSE 555Hyperplane Geometry• Positive side, R1, if g(x) > 0• Negative side, R2, if g(x) < 0• Algebraic measure of distance of x to hyperplane• Definewxgr www and 0wxw)g(x Because wwwrwxwwxwxg wwrxxt0ptp0tpt0tp)(.....)(.2===+=++=+=+=• Distance of origin to hyperplane• Origin is on positive side if w0 > 0 otherwise on negative side• Orientation of hyperplane is determined by normal vector w• If w0=0 then g(x) has homogeneous form wtx andhyperplane passes through the origin• Location of hyperplane is determined by the bias w0wwwgr 0)0(==Srihari: CSE 555Multicategory Case• Regard the problem as c two-class problems• Two methods1. Separate points assigned to ωifrom those not assigned to ωi2. Use one hyperplane for each pair for classesWill need c(c-1)/2 discriminant functionsSrihari: CSE 555Using dichotomies for four-class problemDecision Boundaries HijDichotomiesSrihari: CSE 555Multi-category case: Linear Machine• We define c linear discriminant functions• and assign x to ωi if gi(x) > gj(x) ∀ j ≠ i; in case of ties, the classification is undefined• In this case, the classifier is a “linear machine”• A linear machine divides the feature space into c decision regions, with gi(x) being the largest discriminant if x is in the region Ric1,...,i wxw)x(g0itii=+=Srihari: CSE 555Two class case of Linear Machine• For two contiguous regions Riand Rj• Boundary that separates them is a portion of hyperplane Hijdefined by:gi(x) = gj(x)• (wi–wj)tx+ (wi0–wj0) = 0• wi–wjis normal to Hij• Distance from x to Hijisjijiwwxgxg−−)()(Srihari: CSE 555Linear Machine Boundariesfor 3 and 5-class problemsSrihari: CSE 555Linear Machines and UnimodalDistributions• It is easy to show that the decision regions for a linear machine are convex, this restriction limits the flexibility and accuracy of the classifier• Every decision region is singly connected• Suitable for Unimodal distributions• Sometimes can be made to give good results for multimodal distributions as wellSrihari: CSE 555Generalized Linear Discriminant Functions• Linear Discriminant functions can be written as• Adding additonal terms we get quadratic discriminantfunctionsSrihari: CSE 555Polynomial Discriminant Functions• Continue to add terms such as• wijkxixjxk• Leads to generalized linear discriminant function• a is a d^ dimensional weight vectorSrihari: CSE 555φ function• Functions yi(x) are called φ-functions• They map points in d-dimensional space into points in d^-dimensional space• Homogeneous discriminant function aty separates points by a hyperplane that passes through origin in transformed space• Problem is one of finding a Homogeneous linear discriminant functionSrihari: CSE 555Quadratic as Generalized LDF•ExampleSrihari: CSE 555Transforming 1-d to 3-dError in figure:Plane should pass through originMapping y = (1, x, x2)ttakes a line and transforms it to a parabola in 3-d.A plane splits the resulting y-space into regions corresponding to two categories which gives a nonsimply connected decision region in x-spacey1y2y3Srihari: CSE 555Case of a=(-1,1,2)2-d input space x is mapped through a polynomial function f to y.Here the mapping is y1= x1, y2= x2and y3α x1x2A linear discriminant in this transformed space is a hyperplane which cuts the surface.Points on the positive side of H correspond to ω1and those beneath it correspond to ω2.Srihari: CSE 555Augmented Feature Vectorwhere x0=1Task is to find a single weight vectorSrihari: CSE 555Augmented weight vector a (at the origin).Set of points for which aty = 0 is a plane perpendicular to a and passing through the origin of y-space, as indicated by red disk. Such a plane need not pass through origin of 2-d feature space as illustrated by dashed decision boundary at top of box.Thus there exists an augmented weight vector a that will lead to any straight decision line in x-space.3-d augmented feature space