Lecture Title - University of Wisconsin-Madison

Lecture Title - University of Wisconsin-Madison

Intro. ANN & Fuzzy Systems Lecture 15. Pattern Classification (I): Statistical Formulation Intro. ANN & Fuzzy Systems Outline Statistical Pattern Recognition Maximum Posterior Probability (MAP) Classifier Maximum Likelihood (ML) Classifier K-Nearest Neighbor Classifier MLP classifier (C) 2001 by Yu Hen Hu 2 Intro. ANN & Fuzzy Systems An Example

Consider classify eggs into 3 categories with labels: medium, large, or jumbo. The classification will be based on the weight and length of each egg. Decision rules: 1. If W < 10 g & L < 3cm, then the egg is medium 2. If W > 20g & L > 5 cm then the egg is jumbo 3. Otherwise, the egg is large Three components in a pattern classifier: Category (target) label Features Decision rule L W (C) 2001 by Yu Hen Hu 3 Intro. ANN & Fuzzy Systems Statistical Pattern Classification The objective of statistical pattern classification is to draw an optimal decision

rule given a set of training samples. The decision rule is optimal because it is designed to minimize a cost function, called the expected risk in making classification decision. This is a learning problem! (C) 2001 by Yu Hen Hu Assumptions 1. Features are given. Feature selection problem needs to be solved separately. Training samples are randomly chosen from a population 2. Target labels are given Assume each sample is assigned to a specific, unique label by the nature. Assume the label of training

samples are known. 4 Intro. ANN & Fuzzy Systems Pattern Classification Problem Let X be the feature space, and C = {c(i), 1 i M} be M class labels. For each x X, it is assumed that the nature assigned a class label t(x) C according to some probabilistic rule. Randomly draw a feature vector x from X, P(c(i)) = P(x c(i)) is the a priori probability that t(x) = c(i) without referring to x. P(c(i)|x) = P(x c(i)|x) is the posteriori probability that t(x) = c(i) given the value of x P(x|c(i)) = P(x |x c(i)) is the conditional probability (a.k.a. likelihood function) that x will assume its value given that it is drawn from class c(i). P(x) is the marginal probability that x will assume its value without referring to which class it belongs to.

Use Bayes Rule, we have P(x|c(i))P(c(i)) = P(c(i)|x)P(x) Also, P(c(i ) | x) P( x | c(i )) P(c(i )) M P( x | c(i)) P(c(i)) i 1 (C) 2001 by Yu Hen Hu 5 Intro. ANN & Fuzzy Systems Decision Function and Prob. Mis-Classification Given a sample x X, the objective of statistical pattern classification is to design a decision rule g(x) C to assign a label to x. If g(x) = t(x), the naturally assigned class label, then it is a correct classification. Otherwise, it is a misclassification. Define a 0-1 loss function: 0 if g ( x) t ( x) ( x | g ( x)) 1 if g ( x) t ( x)

(C) 2001 by Yu Hen Hu Given that g(x) = c(i*), then P(( x | g ( x) c(i*)) 0 | x) P (t ( x) c(i*) | x) P(c(i*) | x) Hence the probability of misclassification for a specific decision g(x) = c(i*) is P(( x | g ( x) c(i*)) 1 | x) 1 P (c(i*) | x) Clearly, to minimize the Pr. of mis-classification for a given x, the best choice is to choose g(x) = c(i*) if P(c(i*)|x) > P(c(i)|x) for i i* 6 Intro. ANN & Fuzzy Systems MAP: Maximum A Posteriori Classifier The MAP classifier stipulates that the classifier that minimizes pr. of misclassification should choose g(x) = c(i*) if P(c(i*)|x) > P(c(i)|x), i i*. This is an optimal decision rule. Unfortunately, in real world applications, it is often difficult to estimate P(c(i)|x). (C) 2001 by Yu Hen Hu Fortunately, to derive the optimal

MAP decision rule, one can instead estimate a discriminant function Gi(x) such that for any x X, i i*. Gi*(x) > Gi(x) iff P(c(i*)|x) > P(c(i)|x) Gi(x) can be an approximation of P(c(i)|x) or any function satisfying above relationship. 7 Intro. ANN & Fuzzy Systems Maximum Likelihood Classifier Use Bayes rule, p(c(i)|x) = p(x|c(i))p(c(i))/p(x). Hence the MAP decision rule can be expressed as: g(x) = c(i*) if p(c(i*))p(x|c(i*)) > p(c(i))p(x|c(i)), i i*. Under the assumption that the a priori Pr. is unknown, we may assume p(c(i)) = 1/M. As such, maximizing p(x|c(i)) is equivalent to maximizing p(c(i)|c).

(C) 2001 by Yu Hen Hu The likelihood function p(x| c(i)) may assume a univariate Gaussian model. That is, p(x|c(i)) ~ N(i,i) i,i can be estimated using samples from {x|t(x) = c(i)}. A priori pr. p(c(i)) can be estimated as: {x; # x s. t. t(x) c(i)} P (c(i )) |X| 8 Intro. ANN & Fuzzy Systems Nearest-Neighbor Classifier Let {y(1), , y(n)} X be n samples which has already been classified. Given a new sample x, the NN decision rule chooses g(x) = c(i) if y (i*) Min. || y (i ) x || 1i n is labeled with c(i). As n , the prob. Mis-classification using NN classifier is at

most twice of the prob. Mis-classification of the optimal (MAP) classifier. k-Nearest Neighbor classifier examine the k-nearest, classified samples, and classify x into the majority of them. Problem of implementation: require large storage to store ALL the training samples. (C) 2001 by Yu Hen Hu 9 Intro. ANN & Fuzzy Systems MLP Classifier Each output of a MLP will be used to approximate the a posteriori probability P(c(i)|x) directly. The classification decision then amounts to assign the feature to the class whose corresponding output at the MLP is maximum. During training, the classification labels (1 of N encoding) are presented as target values (rather than the true, but

unknown, a posteriori probability) (C) 2001 by Yu Hen Hu Denote y(x,W) to be the ith output of MLP, and t(x) to be the corresponding target value (0 or 1) during the training. e 2 (t ) E || t ( x) y ( x,W ) ||2 E || t ( x) E[t ( x) | x] E[t ( x) | x] y ( x,W ) ||2 } E || t ( x) E[t ( x) | x] ||2 E || E[t ( x) | x] y ( x, W ) ||2 E || E[t ( x) | x] y ( x, W ) ||2 Hence y(x,W) will approximate E(t(x)|x) = P(c(i)|x) 10

Recently Viewed Presentations

  • Developing A &quot;Customer Centric Loyalty Program&quot; at PARK &#x27;N FLY

    Developing A "Customer Centric Loyalty Program" at PARK 'N FLY

    In 1910, the dominant mode of transportation was streetcar railway. Today, there are nearly 300 models of automobiles spanning various consumer needs and wants. Airplanes have significantly changed document and package delivery times. NEW PRODUCT DEVELOPMENT ┬ęDr. V. Kumar. LEVEL...
  • History and Government of Canada

    History and Government of Canada

    Colonization-During the 1500-1600s, French explorers claimed much of Canada-Called their settlements "New France"-British explorers also colonized parts of Canada along the Atlantic coast-By the 1700s, led to a country with two distinct cultures: Roman Catholic French and Protestant English
  • WG 11 - STEP Tools

    WG 11 - STEP Tools

    PMI.stp. External references are to root file only. Wing.stpz. Conformance Classes. Character set updated to UTF-8 ISO 10646. Anchor section enables UUID references into the data. Signature section prevents tampering. Reference section enables references out of the data.
  • Nomenclature - Madison County School District

    Nomenclature - Madison County School District

    Define cation and anion. Write the electron configurations of 5 elements of your choosing. What is a molecule? Predicting Oxidation Numbers. Electrons involved in reaction are the outer and highest energy electrons (Valence electrons) ... Nomenclature Last modified by:
  • Capgemini NA PowerPoint Template

    Capgemini NA PowerPoint Template

    Status quo, problems and thoughts on the management of civil servants Pension System Paris, 25 June 2015 * * * * * * * Uniqueness of "Massive Source" (DMA - Analytic Monthly Declaration) as the only source of data for...
  • Service delivery assessment - Financial requirements ...

    Service delivery assessment - Financial requirements ...

    Service delivery assessment - Financial requirements - Revenue Structure: Sources of income - Percentages expenditure per sector - Organogram of the NMBM and Human Capital - Establishment of MPACC - Risk Management: Policy & Strategies, SCM - Intergovernmental Relations -...
  • Determination of Lead in Dust Wipes using Field Analytical ...

    Determination of Lead in Dust Wipes using Field Analytical ...

    Determination of Lead in Dust Wipes using Field Analytical Technology Presented by U.S. Environmental Protection Agency's (EPA) Office of Superfund Remediation and Technology Innovation (OSRTI) and Office of Research and Development (ORD) and the Department of Energy's (DOE) Oak Ridge...
  • 9/9 What are the rules that govern the flow of energy in ...

    9/9 What are the rules that govern the flow of energy in ...

    What six forms of "work" are present in biological systems? How is this relevant to what happens in a cell? Energy is the capacity to do work or cause change!What are 6 ways cells use energy? 1) Synthetic Work is...