Ch 4. Linear Models for Classification (1-2)Pattern .ppt

1、Ch 4. Linear Models for Classification (1/2) Pattern Recognition and Machine Learning, C. M. Bishop, 2006.,Summarized and revised by Hee-Woong Lim,2,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Contents,4.1. Discriminant Functions 4.2. Probabilistic Generative Models,3,(C) 2006, SNU Bioint

2、elligence Lab, http:/bi.snu.ac.kr/,Classification Models,Linear classification model (D-1)-dimensional hyperplane for D-dimensional input space 1-of-K coding scheme for K2 classes, such as t = (0, 1, 0, 0, 0)T Discriminant function Directly assigns each vector x to a specific class. ex. Fishers line

3、ar discriminant Approaches using conditional probability Separation of inference and decision states Two approaches Direct modeling of the posterior probability Generative approach Modeling likelihood and prior probability to calculate the posterior probability Capable of generating samples,4,(C) 20

4、06, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Discriminant Functions-Two Classes,Classification by hyperplanes or,5,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Discriminant Functions-Multiple Classes,One-versus-the-rest classifier K-1 classifiers for a K-class discriminant Ambiguous wh

5、en more than two classifiers say yes. One-versus-one classifier K(K-1)/2 binary discriminant functions Majority voting ambiguousness with equal scores,One-versus-the-rest,One-versus-one,6,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Discriminant Functions-Multiple Classes (Contd),K-class d

6、iscriminant comprising K linear functions Assigns x to the corresponding class having the maximum output.The decision regions are always singly connected and convex.,7,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Approaches for Learning Parameters for Linear Discriminant Functions,Least sq

7、uare method Fishers linear discriminant Relation to least squares Multiple classes Perceptron algorithm,8,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Least Square Method,Minimization of the sum-of-squares error (SSE) 1-of-K binary coding scheme for the target vector t.For a training data

8、set, xn, tn where n = 1,N. The sum of squares error function isMinimizing SSE gives,Pseudo inverse,9,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Least Square Method (Contd) -Limit and Disadvantage,The least-squares solutions yields y(x) whose elements sum to 1, but do not ensure the outpu

9、ts to be in the range 0,1. Vulnerable to outliers Because SSE function penalizes too correct examples i.e. far from the decision boundary. ML under Gaussian conditional distribution Unimodal vs. multimodal,10,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Least Square Method (Contd) -Limit a

10、nd Disadvantage,Lack of robustness comes from Least square method corresponds to the maximum likelihood under the assumption of Gaussian distribution. Binary target vectors are far from this assumption.,Least square solution,Logistic regression,11,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.k

11、r/,Fishers Linear Discriminant,Linear classification model as dimensionality reduction from the D-dimensional space to one dimension. In case of two classesFinding w such that the projected data are clustered well.,12,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Fishers Linear Discriminant

12、 (Contd),Maximizing projected mean distance? The distance between the cluster means, m1 and m2 projected onto w.Not appropriate when the covariances are nondiagonal.,13,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Fishers Linear Discriminant (Contd),Integrate the within-class variance of t

13、he projected data. Finding w that maximizes J(w).J(w) is maximized when Fishers linear discriminant If the within-class covariance is isotropic, w is proportional to the difference of the class means as in the previous case.,SB: Between-class covariance matrix,SW: Within-class covariance matrix,in t

14、he direction of (m2-m1),14,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Fishers Linear Discriminant -Relation to Least Squares-,Fisher criterion as a special case of least squares When setting target values as: N/N1 for class C1 and N/N2 for class C2.,15,(C) 2006, SNU Biointelligence Lab,

15、http:/bi.snu.ac.kr/,Fishers Discriminant for Multiple Classes,K 2 classes Dimension reduction from D to D D 1 linear features, yk (k = 1,D) Generalization of SW and SB,SB is from the decomposition of total covariance matrix (Duda and Hart, 1997),16,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.

16、kr/,Fishers Discriminant for Multiple Classes (Contd),Covariance matrices in the projected y-spaceFukunagas criterion Another criterion Duda et al. Pattern Classification, Ch. 3.8.3 Determinant: the product of the eigenvalues, i.e. the variances in the principal directions.,17,(C) 2006, SNU Biointel

17、ligence Lab, http:/bi.snu.ac.kr/,Fishers Discriminant for Multiple Classes (Contd),18,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Perceptron Algorithm,Classification of x by a perceptronError functions The total number of misclassified patterns Piecewise constant and discontinuous gradien

18、t is zero almost everywhere. Perceptron criterion.,19,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Perceptron Algorithm (contd),Stochastic gradient descent algorithmThe error from a misclassified pattern is reduced after each iteration. Not imply the overall error is reduced.Perceptron con

19、vergence theorem. If there exists an exact solution (i.e. linear separable), the perceptron learning algorithm is guaranteed to find it. However Learning speed, linearly nonseparable, multiple classes,20,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Perceptron Algorithm (contd),(a),(b),(c),

20、(d),21,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models,Computation of posterior probabilities using class-conditional densities and class priors.Two classesGeneralization to K 2 classes,The normalized exponential is also known as the softmax function, i.e. smoo

21、thed version of the max function.,22,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models -Continuous Inputs-,Posterior probabilities when the class-conditional densities are Gaussian. When sharing the same covariance matrix ,Two classesThe quadratic terms in x from

22、 the exponents are cancelled. The resulting decision boundary is linear in input space. The prior only shifts the decision boundary, i.e. parallel contour.,23,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models -Continuous Inputs (contd)-,Generalization to K classe

23、sWhen sharing the same covariance matrix, the decision boundaries are linear again. If each class-condition density have its own covariance matrix, we will obtain quadratic functions of x, giving rise to a quadratic discriminant.,24,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilisti

24、c Generative Models -Maximum Likelihood Solution-,Determining the parameters for using maximum likelihood from a training data set. Two classesThe likelihood function,25,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models -Maximum Likelihood Solution (contd)-,Two c

25、lasses (contd) Maximization of the likelihood with respect to . Terms of the log likelihood that depend on . Setting the derivative with respect to equal to zero.Maximization with respect to 1.,and analogously,26,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models

26、-Maximum Likelihood Solution (contd)-,Two classes (contd) Maximization of the likelihood with respect to the shared covariance matrix .,Weighted average of the covariance matrices associated with each classes.,But not robust to outliers.,27,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Prob

27、abilistic Generative Models -Discrete Features-,Discrete feature values General distribution would correspond to a 2D size table. When we have D inputs, the table size grows exponentially with the number of features. Nave Bayes assumption, conditioned on the class CkLinear with respect to the featur

28、es as in the continuous features.,28,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Bayes Decision Boundaries: 2D -Pattern Classification, Duda et al. pp.42,29,(C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Bayes Decision Boundaries: 3D -Pattern Classification, Duda et al. pp.43,30,(

29、C) 2006, SNU Biointelligence Lab, http:/bi.snu.ac.kr/,Probabilistic Generative Models -Exponential Family-,For both Gaussian distributed and discrete inputs The posterior class probabilities are given by Generalized linear models with logistic sigmoid or softmax activation functions. Generalization to the class-conditional densities of the exponential family The subclass for which u(x) = x.Linear with respect to x again.,Exponential family,Two-classes,K-classes,