Scribd
Upload
2 views79 pages

Text Book Module 1 Probability

Chapter 1 introduces pattern recognition, highlighting its applications in various fields such as medical imaging, automated inspection, and classification tasks. It discusses the importance of features in classification, the role of training and test sets, and the challenges of achieving accurate classifications, especially when relying on expert opinions. Additionally, it touches on statistical decision theory and image processing as essential components of pattern recognition systems.

Uploaded by

t1jit21ise2100052
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
2 views79 pages

Text Book Module 1 Probability

Chapter 1 introduces pattern recognition, highlighting its applications in various fields such as medical imaging, automated inspection, and classification tasks. It discusses the importance of features in classification, the role of training and test sets, and the challenges of achieving accurate classifications, especially when relying on expert opinions. Additionally, it touches on statistical decision theory and image processing as essential components of pattern recognition systems.

Uploaded by

t1jit21ise2100052
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Chapter 1 Introduction 1.1 Applications of Pattern Recognition Pattern recognition is concerned with the antomatic detection ur classification of objects or events. Here are some examples of the problems to which pattern recognition techniques have been applied: « Automated analysis of medical images obtnined from microscopes and CAT sean- ers, magnetic resonance images, nuclear medicine images, X-rays, and pho- tographs © Automatic inspection of parts on an assembly line e Human i recognition by computers Bn iP Automatic grading of plywood, steel, and other sheet material Classification of seismic signals for oil and mineral exploration, and earthquake prediction Selection of tax returns to audit. stocks to buy, and peaple to insure etinal scans, Identification of people from fingerprints, hand shape aud size, voice characteristics, typing patterns, and handwriting Automatic inspection of printed circuits, and printed character and handwriting, recognition Antoniatic analysis of satellite pletures to deterinine the type and condition of agricultural crops, weather conditions, snow nnd water reserves, and minoral prospects 2 CHAPTER 1. INTRODUCTION © Scloction of good prospects from a mail-order list © Classification of eloctrocardiograms into diagnostic categories of heart disease, detection of spikes in electroencephalograms, and other medical waveform anal- yses The measurements or propertics used to classify the objects are called features, and the types or categories into which they are classified are called classes. Since most pattern recognition tasks are first done hy hnmans and automated later, the most fruitful source of features has been to ask the people who classify the objects how they tell them apart. Automating the classification of objects using the same features as those used by people can be a difficult task. but fortunately the features used by machines need ot be precisely those used by humans |Gose 1971}. Sometimes features that would be impossible or difficult for humans to estimate are useful in automated systems. For example, some systems that classify objects in satellite images use wavelengths of light that are invisible to humans, There are techniques such as clustering (see Chapter 5) for unsupervised learning or class discovery that attempt to divide data sets into naturally occurring groups without « predetermined class structure, but in most pattern recognition problems the desired classes are known, and a classified data set is provided for use in the design of the automated system. Obtaining a sct of classified data can sometimes be a difficult problem in itself. The individual items, objects, or situations to be classified will be referred to as samples, or sometimes patterns. In addition to the set of samples used in the system design, often called the training set, a data set called the test set must also be provided for testing the system. Since the em will normally produce better results on the training set used to design it than it will on other data from the same source, the use of this independent test set is required to completely evaluate the system. In cases where a number of different classification techniques are being explored, each with various adjustable parameters, it is sometimes desirable to use a second test set. In this case, the parameters of the various classification techniques are based on the training set, and the classification accuracy of each of the techniques is evaluated using the first test set. The technique that performs best is chosen for future use. Because the variation in testing performance of the various techniques could partly be due to chance, the best of these techniques is then reevaluated using the second test set. The best technique was chosen on the basis of its performance on the first test set, so ils error rate on this set would yield an optimistically biased estimate of its performance on different data if a second test set were not used. Sometimes the class of an object cannot be determined by any absolute criterion but depends on the opinions of experts. In this case, the data should be classified by several experts independently, and their results pooled. Even if the individual exports make errors occasionally, the majority vote of the group will probably be correct. The 1.2, STATISTICAL DECISION THEORY 3 use of a group of experts rather than a single expert also provides some information about what might be a realistic goal for an automated system. For exauuple, when a group of four hematolugists classified 1,041 white blood cells into eight categories, each of them disagreed with the majority opinion 7.97 percent of the time on the average [Bacus]. We might be able to build @ machine thot performs us well as the average hematologist or some particular hematologist if we were to devote sufficient elfort, knowledge, and creativity to the task, but we may not be able to deeign a system that performs much better than the “best” expert, who disagreed with the consensus S41 percent of the time. Possibly the images do not contain sufficient information ta classify them perfectly, or the definitions of the classes are vague. When three of the classes (small, medium, and large lymphocytes) were murged inta one class and another pair of classes (banded aud segmented neutrophils) were also merged to create a total of only five classes, the individual hemntologists disagreed with the majority 0.63 percent of the time on the average. There was even more disagreement between expert clectroencephalographers in the detection of spikes in electroencephalographic (brain wave) records (Gow 1974). When five experts were asked to mark all the spikes in one-minute cight-channel recordings from erch of 30 paticnts, a total of 942 events were classified as spikes by one or more of the experts; however, only 104 events were called spikes by all five of the experts, These data not only produced information on human relinbility, but. they also allowed the spike data to be divided into five subclasies of spike severity or obviousness, depending on the number af experts who detected them. This information was useful in the design of an automated system with n detection threshold that. could be adjusted by the user. 1.2 Statistical Decision Theory After we have obtained and classified data sets and selected the features ta be used, an automated classification system can be designed on the basis of statistical or other decision theoretical techniques. The necessury statistical background will be reviewed in Chapter 2, and the statistically based decision-making techniques will be covered in Chapter 3. Other decision-making techniques will be covered in Chapter 4. As & preview of these techniques, consider the problem of predicting the winner of a game in the HBA (Hypothetical Basketball Association), The prediction could be based an the difference between the home team’s average tumber of points per game (upg) and the visiting team’s apg for previous games. The training srt consists of the scores of previously played games, with each home team classified as a winner or a loser. The problem then is this: Given game to be played, predict the home team to be a winner or loser using the feature, dapg = Home Team apg — Visiting Team apg. ‘The training set shown in Figure 11 lists 30 games, gives the value of dapg for 4 CHAPTER 1. INTRODUCTION Game | dapy | Home Team | Game | dapg | Home Team | TP ap Won We] a1 Won 2) -27 Lost. wl) our Won 3) -05 Wan 18 28 Won a) 32 Lost 19} 46 Won 5| 23 Won 20} 3.0 Won 6 1 Won 21 OF Lest 7| 54 Lost 22] 1 Won 8 8.2 Won 23 25 Won 9) -10.8 Lost 24 os Won Wy) Dat Won 25 | -5.0 Lost nn} 105 Won 26] BA Won a2] -1a Lost a) 71 Lost i 25 Won 28 QF Won wa] -42 Won 20 | -10.0 Lost Wh | -t4 Lost Mw] 65 Won Figure 1.1: Data set of games with outcatmes aud differences between average number of points per game (dupg) scared by the participating teams in previous games. each game, and telly whether the home team wou or fost. Notice that in this data set the tenm with the larger epg nsually wins, For example, in the ninth game the home team, on average, scorer] 10.8 fewer points in previous games than the visiting team. con average, and the home post. When the teams have about the same apy’s, the outcome iy less certain, For example, ia the tenth gaine, the home taut, on average, scored O.4 fewer points than the visiting team, on average, but the home team won anyway. In the twelfth game, the home team had an apg 11 less than the visiting team, on average, and the home team lost. A histogram is 1 convenient, way ta describe the data in Figure 1.1. To form a histogram. the date fom a single cliss are grouped inte intervals, Over exch interval, a vertical rectangle is drawn, with its area proportional to the number of data points falling inte that interval. Because we have chasen equally spaced intervals, the bases of all the rectangles are equi, so the aren of ench rectangle is proportional to its height. In this case we can label the vertical axis of the histogram as the number of occurrences per interval, Histograms ef both classes are shown in Figure 1.2. Each interval hos been chosen to have a width of two units, Although the outcomes of the games with very large absolute dapy's ean be pre- dicted fairly reliably from their dapg values, the predictions are not reliable when dapy 1.2. STATISTICAL DECISION THEORY 3 Number ‘ Figure 1.2: Histogram of dapg. is small Thus the classification cannot be performed perfectly using the single feature dap. When the samples cannot be classified perfectly using the available set of features, the goal may be to estimate the probability of membership in each clus. Given a set of features, a sample may be classified as belonging, to the most probable class, or if the costs of errors are cousidered, into the class with the smal pected penalty, If we predict home games with dapg values less (han or equal to T to be losses and those with depg greater than 7' to be wins, then the value T is called u decision boundary or threshold. As an example, suppose that T= —1 is the decision boundary, If we then want to predict the outcome of the game in which the Delphia Bells (home team) play the Lusk Hangers, we consult a table to obtain Delphia’s apg = 103.4 Lusk's apg = 102.1. Since dapg = 103.4—102.1 = [Link] L.3 > 7, we predict that the home team (Delphin} will win the game. If T = -1 is the decision boundary, four samples in the original data set are misclassified: Three wit are called losers and one loser is called a winner. Changing the decision boundary to T = 0.8 result» in no samples from the Joger class being misclassified as winners, but four samples from the winner cliss would be misclassified as losers. As another example, changing the decision boundary to 7'= —6.5 results in no samples fram the winner class being misclassified as lovers, but seven samples from the loser class would be misclassified as winners.. By inspection, we see that when a decision boundary is used to classify the samples, the minimum number of samples that ore inisclassified is four. One decision boundary that schieves this minimum error 8. rate is T= 6 CHAPTER 1. INTRODUCTION Game | dapa | dwp | Home Team | Game | dapg | dup | Home Tear 1] 1s] 20 Won 16] -3.1 Won 2) -27 | -16.9 Lost lz Wen 3 53 Wen 28 Won 4 275 Lost 46 Wou 5 18.0) Won 30 Won 6 Won) 07 Lost 7 Lot | 10.1 Won s| 82 Won | 28 Won 9| -108 Lost os Won Ww) -04 Won 2 “AO | Lost | 105 Won 26) 8a Won t2) Ld Lost 7 1 Lost | 25 Won 2 2. Won u Won 29 | -10.0 Laat 15 Lost 30 | 6.5, Won Figure 1.3: Data set. of games showing outcomes, differences between average numbers of points scored, and differences between winning percentages for the participating teams in previous games The same data ax given in Figure 1.1 are given in Figure 1.3, but an additional feature dwp = Home Team wp — Visiting Team wp, where wp denotes the winning percentage, luis been included. Using additional features often increases the accuracy of classification, The data frum Figure 1.3 ure presented as a scatterplot in Figure 14. Each sample has a corresponding feature vector (apo. dup) which determines its position in the plot. Note that Figure 1.2 coutd be formed by taking a vertical projection of Figure Ll. Using the single feature dwp (projecting the data in Figure 1-4 horizontally) wottid alse not classify the data perfoetly. As shown im Figure 14, the feature space can be divided into two decision regions by a straigit line, called a Huear decision bonadary, which in this case perfectly separates the two classes. (Decision boundaries will be discussed in more detail in Chapter 4.) This linear decision boundary could be used to classify a sample (game) of unknown class: Lf Uhe sample lex above the decision boundary, the home team would be classified as (predicted to be) the winner; but if the sample Hes below the decision boundary, the home team would be classified an the luer. As an exumple, suppose that we want to predict. the outcome of the game in which the Springfield Monarchs 1.3. IMAGE PROCESSING AND ANALYSIS Figure 1.4; A scatterplot of dapy versus dnp, {home team) play the Centerville Rockets, We cousult a table to obtain Springfield's apg = 98.3 Centerville’s apg = 102.9 Springfield's wp = 214 Conterville’s wp = 58.1. We compute dapy = Home Team apy ~ Visiting ‘Toam apg = 98.3 - 102.9 = —4.6 dup = Home Team up — Visiting Team wp = 214 ~ 58.1 = ~36.7. Since the polut (depy, dup) = (—4,6,-36.7) les below the decision boundary, we predict that the home team (Springfield) will lose the game. Ifa feature space cannot be perfectly a straight line, a more complex boundary might be used. Alternatively, decision boundary such as 2 straight: line might be used even Hit did not pe jv separate the classes, provided that the error rates were acceptably Jow. A very complicated decision boundary could probably separate the two classes in the training data set perfectly, but this overfitting would probably result in poor testing set performance. 1.3 Image Processing and Analysis In pattern recognition, the objects to be classified often come fram images (sometimes called pictures) althongh, as the eximple in the preceding section shows, pattern 8 CHAPTER 1. INTRODUCTION recognition is not restricted to identifying Objects in Images. Because images are such un important source of objects to be classified, in this section we present nn example that provides n brief introduction to image processing, In Chapter 7, we discuss simple operntions on images such ns smoothing, sharpening. and thresholding, which can improve images for display or further analysis, In Chapter $, we discuss image analysis techniques. . A digital image is simply a matrix where cach number represents the brightness at regulatly spaced points or very smuail regions in the image, These points are called pixels (picture elements) and the brightness value of a pixel is called ite gray level, Scanners are commonly available to convert photographs to digital images. In video cameras, the brightness of the pixels is represented by a time-varying voltage as the scene iy scanned, und the digitited version of the image is obtained by sampling the voltage using an aualog-to-digital converter or frame grabber. Figure 1.5 sbows an image of vehicles on a street during rush hour, Figure 1.6 shows in detail the portion of the image enclosed in the white box (a right tnil light). Figure 16a shows the actual numeric gray levels of the subinage sealed from 0 to 9 The darkest pixels in the subimage are uwiened the vulue 0 and the brightest ones are assigned the value 9. Figure 1.6b shows the sume subimage displayed ay a halftone image, Figure 1.6c shows it as a contour plot (centers of pixels with the same brightuess are connected), and Figure [Link] shows the subimage as a threo-dimensional perspective plot (elevated paints an the plot correspond to brivht pixels and low points correspond. to dark pixels). To sex how image processing is telated to pattern recognition, suppo hat we have those in Figure 1 7, that contain three kinds of particles: large circular pollen granules. which we refer to ns 21 granules; amall circular pollen granules, which fer to as P2 granules; and asbestos fiber A, which tend to be long and thin. The first step in building an automntic classification systoin is to separate the objects (the particles) from the backyround—n process called segmentation. In Soction 3.2 we will present an algorithm for segmenting an image; here, we assume that we have already located the olsjects in the wes. After locating the objects, we munt extract features from the objects that can be used to identify the ubjects, The two types of pallen granules can be differentiated by area since the 7’) pollen granules are larger, ou pverage, than the P2 pollen granules (see Figure 1.83}. It is easy to compute the nrea of an object ina digital image—we simply count the number of pixels in the object Unfortunately, the aren feature docs nok distinguish PY pollen gramles from as- besten fibers because PI pollen granules and asbestas fibers have approximately the same arens (seq Figure 1.8b), Thus we need at least one additional or replacement fenture to distinguish between PT pollen graaules and asbestos fibers: 14. IMAGE PROCESSING AND ANALYSIS L) Figure 1.5: Original street scene, The region of interest in the white box is dispiayed in Figure 1.6. 1, INTRODUCTION CHAP: w ——— eee Sooooonr Tasso soe) ONANoANACoU AAD! JODWNORRRRERR OOO) pxonmosascennnwn) ONoIWeaTacaonannow| joNoTEMATEDDOnNwn OtON@cacoarnnooet wewornccnowsane s| mere nator aeccUeeN| IAMAnMcwecim em NEI] MMM OUR OCOOn OMAGH KH OGKK nos tONNUR Eee st on s 15 (a) (c) Figure 2.6: (a) The rounded gray levels in an image containing a tail light, (b) The tail light's gray levels shown in halftone y scale. (¢) A contour plot of the tail tight's gray levels, (d) A three-dimensiomal plot af the tail light's gray levels. 1.3. IMAGE PROCESSING AND ANALYSIS Ts Figure 1,7: Particles on an air filter. | a . . SS Paten Pt | BO 5 od i. y b.! " | a -| > Hae ° 0 6 10 w 20 o 5 10 6S (a) Areas of Poten Granuies (b) Arana of Partclos Figure 1.8: (s) A histogram of pollen granule areas. (b) Areas of #1 pollen granules and asbestos fibers, 12 CHAPTER 1. INTRODUCTION Pollan Pt Number 3 a 5 10 15 20 (a) Penmeters of Particles Figure 1.9: (a) A histogram of Pt pollen granules and asbestes fibers using the perime- ter feate (b) A scatterplot of Pl and P2 pollen granules (1 and 2) and asbestos fibers (31) using the area and perimeter festures. Ones represent P1 samples; twos represent P2 samples; and threes represent asbestos samples. As ik often the case in pattern recognition problems, several different features could he used to distinguish P1 pollen granules from rsbestas fibers, We will use perime- ter as our second feature, Recall the result from geometry that states that if a fixed perimeter bounds n figure of waximun area, that figure is necessarily a circle. This result implies that if a Pl pollen granule were a porfect circle and an ashestas fiber had an area exactly equal to the area of this pollen granule, the pollen granule would have a smaller perimeter. Although 1 pollen granules may not be perfectly circular and their areas usually do not exactly equal the areas of the asbestas fibers, a his- togram of the perimeters of P1 pollen granules and asbestos fibers suggests that we can distinguish PT pollen granules from asbestos fibers by computing their perimeters (woe Figure 1.90). ‘To compute the perimeter of an object in a digital image, we could count the edge pixels af the object. An edge pixel of an object might he defined as any object pixel that lies next toa background (uonobject} pixel. We could define pixels as being “next to” each ather if ane ts immediately above or to the left of the other. Figure 1.90 shows a seatterplot of pollen granules and asbestos fibers nsing the area and perimeter features. As shown, we can ust straight line sewineuts to form derision boundaries that perfectly separate the three classes. We could use these decision boundaries to define a chesifier as follows. Given an unknown particle with area x and perimeter y, wr could plot the point (x,y) on the graph in Figure Lb. [f the point is in the Pl region, we would classify it as Pl; if the point is in the P2 region, we 1d. THE INTERNET 13 would classify It as P2; and if the point is in the asbestos region, we would classify it ag asbestos (A), 1.4 The Internet Considerable information and free software that may be of interest to readers of this book are available on the internet, For example, a versatile image processing software system, NIH-Inage, was developed at the National Institutes of Health (NIH). This software can acquire, display, edit, enhance, analyze, and animate images. It supports various file formats and interfaces with frame grabbers, scanners, tablets, printers, and monitors. Tt slso facilitates (he manual measurement of lengths, angles, and areas in images. A Macintosh version of NIH-Image can be obtained from the site [Link] Two windows versions, Tage far Windows by Scion Inc. (Windows 5) and Image ‘Tool by the University of Texns Health Sciences Center at San Antonio (Windows 95 or Winduws NT), can also be obtained fram the NIH site. The general medical image manipulation and analysis software OSIRIS is available from the University Hospital of Geneva, Switzerland at ittp://[Link] www JUIN /[Link]. Software for the reconstruction and display of serial microsropic sections is available from [Link], Lists of medical imaging pages are maintained at betp://[Link]:7080_ /services/[Link] and bitp://[Link]/medimagresreh tml. The Radiology Department at Pennsylvanin State University maintains a web server at http:/ [Link].tume_psu.edu/, Sets of images for training radiologists are available at a number of sites. Some medical clip urt is available at [Link] [Link]/f/clipart /tnedical. A list of answers to frequently asked questions (FAQs) on volume visualiza- tion software is available at [Link] Tn addition to the “Grateful Med” biomedical publications information retrieval system, the U, §, National Library of Medicine has produced the Visible Human Project image database, A male and a female cydaver were frozen, photographed, and then ground away by milling machine, with new photographs being taken ut sub-milllmeter intervals to produce threedimensional volume images. The intact ca- davers were alse imaged by MRI and CAT scanners. Further information is available at bttp:/[Link]/extramural-research dir/[Link] or by email from ackerman@he [Link] A student version of the DADDISP waveform and image analysis doftweare is avail- able at htip://[Link], The IMG* nage processing toolset for UNIX is available from $. A. J. Winder, whose e-mail address is [Link]. ‘A system for simulating, and displaying the results of fluid dyanmics experiments is avuilable from the Numerical Aerodynamics Siinulation Division of NASA's Amon Research Center at hitp://[Link]/FAST/[Link]. The U.S. Army has de uw CHAPTER 1. INTRODUCTION veloped systems to work with large two-dimensional and three-dimensional image se quences, which are available at [Link] There are many thousands of newsgroups active ina wide variety of fields. Some of them in medical imaging and reinted areas are: [Link], sci image-processing, and [Link]. A newsgroup concerned with speech recognition and process ing is [Link]. Large collections of annotated speech wavefurins aud phonetic dictionaries in various languages are available at several sites. This sharing of data and software makes it much easier far new people to conduct research in fields such as speech recognition, synthesis, and coding, speaker identification and impersoi language identification, and musical voice training. A set of 77 forensic hair images can be obtained by using Yahoo to search for the key wards hair data. The sampling of sites listed is only a tiny fraction of Uhe material available on the internet and world wide web, which is growing exponentially, Further up-to-date infar- mation can be obtained using search engines such ay Alta Vista ([Link] altavista, [Link]) or Yahoo ([Link] with general key words such as pat- fern rerognition, computer vision, tmage processing, informatics, oF more specific terms such as remote sensing or medical imaging. Many newsgroup members will also respond with friendly advice and answers to specific questions. 1.5 Pointers to the Literature Several journals nre devoted to pattern recognition and image processing and many more broadly based journals often contain articles on pattern recognition and image processing topics, Same journals devoted principally to pattern recognition are © IEEE Transactions on Pattern Analysis and Machine Intellinence (PAM) © Pattern: Recognition Journals containing articles about pattern recognition include © IEEE Transactions on Computers © IEEE Transactions on Information Theory © JEEE Transactions on Systems, Man, and Cybernetics © Precedings of the IEEE Journals containing articles on image processing and analysis include © Applied Optics © Computer Vision, Graphics, and Image Processing 1.6. POINTERS TO THE LITERATURE 15 © IEEE Computer Graphics and Applications © IEEE Transactions on Acoustics, Speech and Signal Processing ¢ IEEE Transactions on Image Processing © IEEE Transactions on Medical Imaging © International Journal of Remote Sensing © Journal of the Optical Society of America © Optical Bnyincering © Photogrammetric Bugincering and Remote Sensing In addition, the general interest journals JEER Computer und Communications of the ACM often contain articles on pattern recognition and image processing, and journals frow other disciplines, such as the med journals Cancer and Diagnestic Radiology, the engineering jaurnals IEEE Transactions on Biomedical Enginceriny aud Optical Engineering, the robotics journal Rubotics Age, and the defense journal Defense Electronics, often contain articles on applications of pattern recognition and image processing to those disciplines. Finally, major pattern recognition conferences such as the International Joint Conference on Pattern Recognition and various meetings organized by the Society of Photo-aptical Instrumentation Engineers (SPIE) publish conference proceedings. Many books lave been published in these areas, mostly at an advanced gradu- ate level. Most of them contain extensive references to the previous literature, The following is a partial list of pattern recognition books. © Bow, S$. T., Pattern Recognition, Marcel Dekker, New Yark, 1984. © Chen, C. H., Statistical Pattern Recognition, Hayden, Washington, D.C., 1973, Chien, Y. T., Interactive Pattern Recognition, Marcel Dekker, New York, 1978. Devijver, P. A., and J, Kittler, Pattern Recognition: A Statistical Approach, Prentice Hall, Englewood Cliffs, N.J., 1982. Duda, R. O., and P. E. Hart, Pattern Recognition and Scene Analysis, Wiley, New York, 1973. Fu, K.S., Syntactic Pattern Recognition and Applications, Prentice Hall, Engle- wood Cliffs, N.J., 1982. Fukunaga, K., Introduction to Statistical Pattern Recognition, 2nd ed., Academic Press, Sun Diego, 1990, CHAPTER 1. INTRODUCTION ® Gonzalez, R. C., and M. G. Thomason, Syntactic Pattern Recognition, Addison- y, Reading, Mass., 1978. Wesle: ® Miclet, L., Structural Methods in Pattern Recognition, Springer-Verlag, New York, 1986. © Nadler, M., and E. P, Smith, Pattern Recognition Engineering, Wiley, New York, 18g, © Pao, Y. H.. Adaptive Pattern Recognition and Neural Networks, Addison-Wesley, Reading, Mass,, 1989. © Patrick, E. A. and J. M. Fattu, Artificial Intelligence with Statistical Pattern Recognition, Prentice Hall, Englewood Cliffs, NJ., 1986. © Paviidis, T., Structural Pattern Recognition, Springer-Verlag, Berlin, 1977. © Schalkoff, R. J, Pattern Recognition: Statistical, Structural and Newml Ap- proaches, Wiley, New York, 1992. e Therrien, C, W., Decision Estimation and Classification: An Introduction to Pattern Recognition and Related Topics, Wiley, New Yark, 1989. © Tou, J,, and R, Gonzalez, Pattern Recognition Principles, Addison-Wesley, Read- ing, Mass., 1974. Ullman, J. R., Pattern Recognition Techniques, Crane, Russak, New York, 1973, © Watanabe, S., Pattern Reengnition: Human and Mechanical, Wiley, New York, 1985. © Young, T. Y., and T. W. Calvert, Classification, Estimation and Pattern Recog- nition, Elsevier, New York, 1074. The following, are some books on intage processing. ¢ Ballard, D. H., and Brown, C. M., Computer Vision, Prentice Hall, Englewood Cliffs, NWJ., 1982. © Gonzalez, R. C., and P. Wintz, Digital Image Processing, Addison-Wesley, Read- ing, Moxs.,.1987. © Hall, E. L., Computer Image Processing and Recognition, Academic Press, San Diego, 1979. © Haralick. R. M., and L. G. Shapiro, Computer and Robot Vision, Vols. 1 and 2, Addison-Wesley, Reading, Mass,, 1992, 16. PROBLEMS 7 @ dain, A. K., Fundamentals of Duzital Image Processing, Prentice Hall, Ensewood Clits, » 1988, © Pratt, W.K., Digital Image Processing, Wiley, ew York, 1978, © Rosenfeld. A. and A.C. Kak, Digital Picture Proceasing, Academic Press, San Diego, 1982. © Young, T. Y., and K. $. Fu, editors, Handbook of Pattern Recognition and Image Processing, Academic Press, San Diego, L886. 1.6 Problems 1.1. The values of feature a for nine samples frum class Aare 1, 2, 4, 2 4,4, 6, 6, 8. Nine samples from class B hod 2 values of 4, 6. 7, 7. 8, 9, 1, 12, Make # histogram (with an interval width of 1) for each class and find a devision boundary (threshold) that minimizes the total sumber of mi sification for this training data set. (Ans: If 2 < 6, choose A.) 1.2, Solve Problem 1.1 with the following data, The values for class A are 2, 2, 2,4, 1d 3.9.3. 3.44.5. The values for claws 8 are 3.3. 4.4. 4.05, [Link]. 6. 7.7. 4, Can the feature vectors (x,y) = (2,3), (9,4), (4,2), (2.7) from class A be separated frum four samples from elass B located wt (6,2), (5,4), (4.6), (3,7) by a linear decision boundary? If so, give the equation of one such boundary and plot it. Honot, find a boundary that separates chem as well a possible. Hort: Draw a scatterplot. 1A. Solve Probiem 1.3 using the feature vectors (1,1), (1.2), (2,2), (2,8), (4,0) for class A and the feature veetors (8,1), (4,1), (8,2) for class B. 1.5, Solve Problean 1.3 using the feature veetors (1,1), (1.2), (2.2), (2.3), (3,0), (4,0) for class A and the feature vectors (3,1), (3,1), (3,1) for class BL 1.6. Invent o set of numeric features that could be used for identifying the models of antomobiles from sideview photographs of unknown (variable) scale. Hint: Lengths cannot be used os features heeause the cars are ot various unlmown distances from the camera, but there are features that are ot, aeeted by the scale, such us the ratios of lengths in an image, 17. Invent aset of uumoric features for clausifying images of oranges, apples, bananas, and pears. 1,8. Invent a set of mmeric features for verifying the claimed identities of people from images of their hands, laid fat with the fingers spread. Chapter 2 Probability 2.1 Introduction Suppose that an anthropologist wants to classify fossil human skulls into two classes: male and female. The anthropologist knows from previous experience that malo skulls tend to have larger circumferences than female skulls. However, within cach group of skulls there is considerable variation in the circumferences and their rangex overlap. If it were necestary to guess the sexes of various skulls given ouly their circumferences, it would be reasonable to guess male whenever the circumference is larger than some value. This is an example of » clossificution decision (or guess) based on the value of a single feature. In the field of pattern recognition, we are interested in techniques for making the best decisions possible. Even if we make the best decisions based on the available information, we may not always be correct. If we used udditional measurements from the skull, we would probably be correct more often. There are various hereditary, nutritional, and enviromental causes for the variations in the circumferences of the skulls, and if we could know them all for each skull, we could conceivably model ar explain why these particular circumferences were produced, An even inote complex chain uf cause and effect. would probably be required to explain why these particular skulls were found in our sample. Rather than requiring complete understanding, a probability model assumes thnt at least some of the vuriability in the data is due to chance or random variability. In this chapter, we will discuss various probability models. They will be used in the following two chnpters ax the basis for decision making techniques. For » random occurrence with a finite number of possible outcomes, such as ran- domly choosing « skull from rome group and measuring its circumference ¢ to the nearest centimeter, we can define a probability model by listing all the possible out- ig 20 CHAPTER 2. PROBABILITY comes and the probability that cach one occurs. We denote the probability that a partieniia value 2 occurs by Pls). A random process can he very simple. such ns flipping a single unbiased cuin. In this case the outcomes are head und tail and the carrespoudine, probabilities are P(kend) = 1/2 and P(tait) = 1/2. If the experiment consists of rolling a fair div. the outcomes are 1, 6 and the probability of each outcome is 1/6. Most people liye an intuitive notion of the meaning of the ward probability, but it is used in yarnions ways, A physician might tell a patient that, according to some tests she has made, there is a 10 percent probability that the patient has eliseine AL Some peuple would object to the use of the word “probability” in this situation and paint ont that either the patient really has the disease ur ¢ dues not. so the unknown probability is cither zero or 100 percent nud caunot be anything between these twa values They would uot apply the word to individuad events for which the outeome bas already been determined. but ouly to hypothetical experiments an collections of data cor assumed models. According te this point of view, the physician could say that 10 percent of poople with these test results had disease A, or that the probubility is 10 percent. that n randomly chosen past patient with these test results lad the disease, bat should not say that there iv a eertain probability that a particular patient has the disease In this text, whe spealc of the probability that a sample belangs to wfer Lo some particular sample. but to a randomly selected. ame set of feature values ne the sutple deseribed. neertain chs, we do net sample that hag the js variables such as the exnet ciremmference of a skull are considered to finity of possible valuos. Cuntinions variables can be deserited by probability densities, which will be discusied in Section 2.3, ar their pawible values can be broken into ranges, nud the probability of lying in cach range can be listed. For example, suppai that the probability is 0.02 that the cirenmference x of a skull is between 59.5 nud 40.5 centimeters. We express this a Pi 0.02. A feature from any real data set is automatically broken inte a finite number of ranges when it is incasured. becatise mensurements can only be recorded with finite precision. Continur have an Mthough choosing a probability model is easy for simple or idealized situations such as tipping unbinsed coins or rolling dice with asimmed probabilities for various faces showing, obtaining probabilities for real world situations is usually more difficult, ‘Two methods for obtaining probability estimates are called the frequentist approach and the subjective approach. Tn the frequentist approach, the probability of an event is estimated by dividing the Mumnber of occurrences of ent by the nimber of trials. For example, to estimate the probability of obtaining a defective tight balb from a certain manufacturing process, we might saraple 10) light bulbs and count the number that are defective. If we obtain Hirex, defertive light bulbs, we approxinite or estimate the probability of obtaining-1 defective from We the 3 OF EVENTS 21 y and as confidently as desired (shart of absolute certainty), assuming that the manufacturing process remains constant. Although the frequentist approach is casy to understand, it may be difficult or impussible to obtain enough samples to get an estimate of the trae probability. Pure therinore, the frequentist approach only applies to repeatable events, that is, events for which the probsbility is coustant over all trials. Thiy wsiumption is often difficult to verify in the real world The probability that a certain candidate will win the next presidential election cannot be estimnted using the frequentist approach because the evont is not repeatable. Por events that are not repeatable, a subjective aseexsinent may be the only way to assign a probability measure. An intuitively appenling way to quantify the process of selecting a subjective probability is to use the notion of n fair ber. You may not be willing to bet “even money" what it will rain in Las Vegas on the next Fourth of July, In fact, vou would prefer to bet against rain be ‘Las Vegas has ¢ denert climate, . if you were affererl 200 to 1 odda, yeu would probably prefer to bet on rain if vou knew that it does cain there vecasionally in June or July. Somewhere between the odds of 1 to | and tho odds of 200 to 1, there is a ber with odds, say 15 to L, for which you would be equally willing to take either side, Such a bet is called # fair bet, Suppose that the prob ch you are betting is 2. Lf the event occurs, you win the amount HW, se you expect to win PIV on the average ptr bet (not counting iosses). If the event does not occur, you lose L, and since the probability that the event will not occur is 1—P, you expect to lose an average of (1— P)L per bet (not counting winnings}. If the bet Ly fair, the average amount of money you win will equal the average amount of money you Ine, so PIV = (1 ~ P)L or P= L/(L+W), Thos the odds of 16 to 1 against rain are equivalent. to the probability of 1/(15 4 1) = 1/16 that rain will cecur and 15/14 that i¢ will not We will use tnainly the frequentist approach in this book. The subjective approach is, however, useful in pattern recognition, especially when subjective expert opinions art to be incorporated [ute a decision. bility of the event on wh 2.2 Probabilities of Events The term experiment is used in probability theery to describe a process for which the ontcome is not known with certainty, Examples of experiments are 1. Rolling a fair six-sided die, 2. Randomly choosing ten transistors from a lot of 1,000 new transistors. 3, Selecting a newborn child at St, Luke's Hospital. An event is an outcome or combination of autcomes from o statistical experiment. The theory of probability studies the relative likelihood of the events that might occur 22 CHAPTER 2. PROBABILITY when an experiment is performed. We will represent events by uppercase letters such as A, B, and C. Exnmples of events that might occur as a result of performing the proviously listed experiments are 1, Obtaining.a 6 when a fair six-sided die is rolled. 2. Obtaining an even number when a fair six-sided div is rolled, 3. Finding more than three detective transistors out of ten transistors randomly chosen from a fot of 1,000 new transistors. 4. Selocting a randomly selected newborn child at St. Luke's Hospital weighing more than eight pounds. The event consisting of all possible outcomes of a statistical experiment fs called the sample space. We Jet § denote the sample space, The sample spaces for the previously listed experiments are 1. The sample space consists of the numbers 1, 2, 3, 4, 5, and G—all possible outcomes of rolling a fair six-sided dio. 2. The sample space consists of the numbers 0,1,...,10--all possible numbers of defective transistors that might be obtained when ten transistors are randomly: chosen from a lot of 1,000 new transistors. 3. The sample space consists of all numbers that represent the possitle weights of randomly selected newborn children at St, Luke's Hospital. A useful way to visualize relationships among events is to use a Venn diagram (ser Figure 2.1 for examples). The sample space § is represented by the entire rectangular region. Events are represented by regions inside the rectangles, and their ureas can be made to correspond to the probabilities of events. In Figure 2.14, the event A is represented by the shaded regian, Because exactly one of the outcomes in S must occur in a single trial, P(S) = 1 Tf A is an event, then the event not A is called the complement of A and is shown in Figure 2.1b. The complement of A is also denoted by A. Because it is a certainty that either A or not A occurs, P{A}+ P(not A) = 1, se P(nut A) =1~ P(A). 2.2. PROBABILITIES OF EVENTS 2 Ss (a) (b) s 8 | m4 fea Treo 4 a 8 4v39 4ag io A+ 5 ove deiivor) a Ag 2 AB (oni wat Figure 2.1: The shaded areas represent the following events: (n) A, (b) A, (c) A or B (a) A and B. f ( a4 CHAPTER 2, PROBABILITY Figure 2-2: Classes A and 8 are mutually exclusive. + SB") or A+ B. The event “both A and B occur” is denoted by A and B (ahown in Figure 2d), This event is sometimes denoted by AO B (read “A intersection B") ot AB. The event A and B is called a joint ovent. Htheevent A and B cannot occur—that is, A and B ennnot occur simultaneously — then the events A and B are said to be mutually exclusive (see Figure 2.2). If A and B are mutually exclusive, the following equation called the addition rule holds: P(A or B) = P(A) + P(B) (24) For exemple, if the probability that x will be the next president ic 30 percent and the probability that y will be the next president is 20 percent, then the probuabitity that one of them will be the next president is 50 percent. If A wad Bare not mutually exclusive, there are four possible joint events A and B, A and B.A and [Link] A and B, each of which in mutually exclusive (nee Figure 2.3), The addition rule thus applies and we can write P(A or B) = PU(A and B) or (A and 8) or (A and B)) = P(A and B)+ P(A and B)+ P(A and BY Furthermore, P(A and B) + P(A und B) = P(A) and P(A and B) + P(A and B) = P(B). These three equations can be combined to yield | P(A or B) = P(A) + P(B) - P(A and B). (22) 2.2. PROBABILITIES OF EVENTS 25 Aand B Aand B Figure 2.3; A Venn diagram illustrating (2.2). This is also evident in Figure 2.3, If P(A) is the area of the event A and P(B) is the area of B, then P(A) + P(A) includes the area of the overlapped region P(A and B) twice, so it must be subtracted to obtain the area of the event A or B. Equation (2.2) can be used to compute the probability of drawing an ace or a spade or both from a deck of cards. Because Place) = 1/13, P(apade) = 1/4, and 4 Place and spade) = 1/8200 sem tyet ae va. ay vy oe P(ace ‘or spade) = yi3+ 1/41/52 = 4/13 Conditional Probabilities - If A and B are events, then the probability of A may depend on whether B occurs. For example, the probability of rolling a 2 with » fair die is 1/6, but if we know chat the outcome was an even number, then the probability that a 2 was rolled is 1/3. The conditional probability of A occurring, given that B lus occurred, ts denoted P(A|B) and is read “P of A given B. ow in adyance that B bas occurred, B effectively becomes the new sample space, so P(A] B) is the fraction of the B cases in which A occurs. Thus we obtain the formula P(A and B) P(A|B) = PUB (2.3) This conditional probability is not: defined if P(B) = 0. Similarly, _ P(B and A) ° P(BIA) = Sy (24) PEALE) = tak os pevke that auent B dosings fo chan A ‘ ee . 4 - A nse horiune The expressions (2.3) und (2.4), which can be rewritten as P(A and B) = P(B)P(AIB) (2.5) and P(A and B) = P(A)P( BIA), (2.6) can also be used to calculate P(A and B). Example 2.1 Calculating the conditional probability of rain given that the barometric pressure is high, Weather records show that. high barometric pressure (defined as being over 760 min of mercury) occurred on 160 of the 200 days in a data set, and it rained on 20 af the 160 days with high barometric pressure. If we let R denate the event “rain occurred” and H the event “high barometric pressure occurred” and use the frequentist approach to define the probabilities, we see that PCH) = 160/200 = 0.80 and———— PUR and H) = 20/200 = 0.10, We cau obtain the probability of rain, given high pressure, directly from the data: P(R\H) = 20/160 = 0.125. Since it is given that high boremetric pressure occurred, only those 160 days of high barometric pressure are under consideration and rain accurred on 20 of those days, We could also obtain P(R|H) from (2.3): PUMA) = PUR and H)/ P(H) = 0.10/0.80 = 0.125. ‘Thus (2.3) i» consistent with the concept of probability according to the frequentist approach, Whether we consider these ratios to be estimntes or definitions of the various: probabilities depends on the population. If we randomly select one of the 200 dayy in the data svt, the probability is exactly 80 percent that there was high barometric pressure on that day. Alternatively, if we consider the population to include all possible days, there is no way to know the exact probability that there will be rain on one of these days. However, we can nse past experience to estimate the probabilities of these events on days pot included in unr data set. In most practical problems, we are interested in estimating the probabilities of future events, given some assumptions or sotne facts concerning the past or present, 2.2. PROBABILITIES OF EVENTS , oy i a7 The Multiplication Rule : ay In many Important cases, P(A) may not depend on whether B has oceurred. We say that the event A is Independent of B if P(A) = P(A|B). An important ronsequence of the definition of independence is the multiplication rule, which is obtained by substituting P(A) for P(ALB) in (2.5) to obtain P(A and B) = P(A|B)P(B) = P(A)P(B) (2.7) whenever A is ifidey (2.7) to obtain ut of B. Tf A is independent of B, we may combine (2.4) and P(B and A) _ P(B)P(A) MBIA) = Ray Pay PU so if A is independent of B, then B ts also jndependent of A. From now on, we will express either of these conditions as “A and B are independent.” If events are not independent, the probabilities of the various possible values of one of them depend on the value of the other. Suppose we want to calculate the probability of rolling a pair of 1s with two dice. The ovultiplication rule can be used in this case because the number obtained on one independent of the number obtained an the other die. Hence the probability af getting ones on both dive ix (1/6)(1/6) = 1/36. Example 2.2 The addition and muitiplication. rules. The probability of rolling o pair of dice such that the sum of the faces showing will equal three can be found by using the addition and multiptication rules. There are tivo ways in which the sum of two dice can equal throe: Either tho first die shows n 2 and the second die a 1, or the first shows af and the second shows a 2, Let Fy be the event that the first die shows a 1, and Jet F be the event that the first die shows a 2. Let Gy and Gy be the events that the second dic shows » 1 or a 2, respectively. Also let E be the event that the sum of the two rolls is 3. Lf we assume that the ralls of the two dice are independent, the multiplication mle applies. In addition, the events Fy and Fo are mutually exclusive, as are Gy) and Gy, so we can use the addition rule: a P(E) PUP, and Gz) or (Fy and G;)) = PF, and Gy) + P( Fy and Gy) = PU)P(2) + P(2)PO) (1/6)(1/6) + (1/6)(1/6) = 1/36 + 1/36 = 1/18. 28 CHAPTER 2 PROBABILITY Example 2.3 Estimating the probabilities of oil recovery test outcomes, ‘Asan ecample in which two events are not independent, suppose that a company plans to test two new techniques for imptoving the extraction of oll from the ground. The first technique consists of sctting off an explosion at the bottom of a well to fracture the strata and then testing seismically to determine the extent of the fracturing, The second technique consists of injecting hot brine into the well ty loosen the oil and then pumping to measure the oil recovery. Let E be the event that the explosion successfully fractures the strata within & radius of 100 meters, and let be the event thot oil can be recovered at a rate of 50 barrely per day after pumping in hot brine, Tn @ certain region, P(E) is estimated to be 0.8. If E occurs, the probability of R occurring is estimated to be P(R|E) = 0.9, but if the explosion is not a success. the ix! probability of recovery is only PCRJE) = 0.3. These three assumptions are sufficient to define the probabilities of any combination of outcomes, given any set of constraints. The probabilities of the four possible joint events are P(E and R) = P(E)P(R|E) = (0.8)(0.9) = 0.72 P(E and Ry P(E)P(RIE) = (0.8)(0.1) = 0.08 P(E and R) = P(E)P(RIE) = (0.2)(0.3) = 0.06 PUB and R) = P(E)P(RIE) = (0.2)(0.7) = 0.14. Since exactly one of the four joint events E and R.E and R, E and Ror E and R mist occur, the sum of the four probabilities above equals 1, These calculations can be arranged in the following table. The numbers 0.8, 0.9, and 0.3 are known, the others are calculated from them. P(R) = 0,78 P(R) = 0.22 The probability of successful brine recovery was not assumed explicitly, but can be calculated from the assumptions, There are two mutually exclusive ways of having successful brine recovery: either with a successful explasion or without one. Thus, P(R) P(E)P(RJE) + P(E)P(RIE) * (0.8)(0.9) + (0.2)(0.8) = 0.72.4 0.06 = 0.78. Equivalently, P(R) could be obtained by summing the probabilities of the two upper joint events in the table: P(R) = P(E and R) + P(E and R) = 0.72 +0.06 = 0.78. 2.2. PROBABILITIES OF EVENTS 2 If only P(E) and P(R) had been known and if we had assumed that they were inde- pendent, we would have calculated the probability of bath tests succveding to be P(E and R) = P(E)P(R) = (0.8)(0.78) = 0.624, However, from past experience we know that P(E and R) = 0.72. The multiplicstion tule does not apply bere because the probability of R depends on the outcome of E, go the events E and R are not independent. Same other questions are 1. What is the probability that the explosion and the brine tests are both successful or both fail? This equals P((E and R) or (E ond 7) P(E and R) + PUB and R) = 0.724 0.14 = 0.86. n . What is the probability that the explosion test was successful, given the con- straint that only one of the two tests was successful? The probabilities of the two events that have exactly one success are P(E and Tt) = 0.08 and P(E and R) = 0.06, so Ponty one success) = 0.08 +} 0.06 = 0.14, and . PLE and only one success) = P(E and R) = 0.08. Thus P(Elonly one success) = P(E and only one succesy)/P(only one success} 0.08/0.14 = 0.571. 3. What is the probability thut the explosion was successful, given that recovery using brine was successful? This is FLE|R) P(E and R)/{P(E and R) + PCE and 8) 0.72/(0.72 + 0.08) = 0,923. 4, If one or more of the tests was successful, what is the probability that the other one was successful The answer is P(E and R)/{P(E and R) + P(E and R) + P(E and B)j = 0,72/(0.72 + 0.08 + 0.06) = 0.837. ee 30 CHAPTER 2. PROBABILITY 2.3. Random Variables Au important first step in pattern recognition is making measurements or extracting features to use for classifying the patterns, For example, one might measure the rcumferenice of a fossil skull thnt, one is trying to classify or count the number of teeth. A random variable is the outcome of a random process which outputs a numeric value. The output of a random variable is called a random number. An example of a random variable is the process of randomly choosing a sample from some population and measuring, one of ity features. We will denote the names and values of random variables by lower-rase letters such as 7, y, and >. An important special class of random variables are the discrete random varl- ables which can tnke on a finite number of possible values or a countably infinite number of values such as 0, 1, 2)... or 2, 4, 6.2... A discrete random variable is described by its distribution function which lists for cach outcome the probabitity P(x) of 2. Ira, 9, ..., tq ate all the possible outcames, then (28) SP = because some outcome must occur. Example 2.4 The distribution function for the number of heads from two flips of a coin, The random variable & is defined to be the total number of heads that occur when a fair coin is Bipped two times. This random variable k can have anly the three possible values 0, 1, and ete, Its distribution function can be obtained by noting that there are four equally likely outcotues from the two flips: (7.7), 7), (ToD). (HH). One of these outcomes produces no heads, two produce one head, and one produces wu heads. The probabilities PCs) of the possible values of keane Uns Le | P(e) aia] t) aja pvt 2| 1/4 2,3. RANDOM VARIABLES 31 The Binomial Distribution A fixed length sequénes of events or trials where each event has exactly two passible outcomes can be modeled by a binomial distribution. One of the outcomes is generally Jed success aud the other is called failure. In the binomial distribution, we assume that the probability of success is the sume for each trial and we denote this probability by @ The total number of successes & obtained inn tri binomial random variable. Its distribution function is given by is called a P(k) = (i)oa —0y"*, ke, yn (2.9) » [ny it kb) Mn — by The symbol ("} is called the binomial coefficient. To see how the binomial distribution is obtained, netice that the a trials will gener- ate a sequence of successes and failures of length n. We want to find the prahability of obtnining a sequence that contains & successes aud n —k failures. There may be many different sequences that contain & suce nd —k failures. For any particular one of these sequences, we can use the multiplication rule to find the probebility of the sequence, as all the trials are independent, From the multiplication rule, we see that the probability of obtaining any particular sequetice containing & successes and no — k failures is ata — ayt-* Furthermore since the number of different sequences that. contain # successes and n — & failures ts the number of ways of choosing a set of k samples from a set of a, ar (7), the probability that a random sequence will contain k successes and n ~ & failures can be found from the distribution function (2.9). The number of heads & in Example 24 in & binomial random variable because cach flip has only two possible outcomes. Its parameters aren = 2 and @ = 0.5, In Example 2.5, & is # binomial random variable, where n = Gand @ = 0.6, Its mean jee is ef and its variance {se0e Section 2.5) aj is n@(1 — 0). Example 2.5 The binomral distribution, An anthropologist knows from records kept at a dig site that the probability duit recovered fossil haman skull is female is 0.6. The probability that out of six skulls, exactly four will be femule is given by stituting Inte the binerial distribution function 32 GHAPTER 2. PROBABILITY POW) 0.20 0.10 L | | Figure 2.4: The binomial distribution function P(k) for n= 6 and 0 = 0.6. P(a) = ({)osos? = 0.311. ‘The graph of the binomin! distribution function P(k) when n = [Link] @ = 0.6 is shown in Figur 24, The Poisson Distribution Although the discrete random variables we have discussed so far were defined to have only a finite number of possible values, there are random variables that may have & countably infinite mmmber of outcomes. A set of outcomes is countably infinite if the outcomes can be listed in an infinite sequence. For example, the set of nonnega- tive integers is countably Infinite because they can be listed as the infinite sequence {9,1,2,...}. The Poisson distribution (see Figure 2.5) Ayn P(n)= (2.10) where n = 0,1,2 is an example of such a diserete distribution. The value P(n) is interpreted as the probability that exsetly n events will occur in a fixed time interval and \is the number of events that occur in that length of time on the average, so A is the inean of the random variable no We assu that the events occur randomly and independently with a constant probability of occurring in any stall time interval, and 2.3. RANDOM VARIABLES 33 2 s a: + 1 « I <8 = x s 7 4 2 nah ol 3 — 01234667890. n Figure 2.5: The Polsson distribution: P{n) = e7>A"/n!, for \ = 1.5, P(n) > 0 for all n, but the values of P(1) for n > 6 arc tog small to see in the graph. Chat two events cannot orcur at exactly the same time. The Poisson distribution can be used to model the number of arrivals of input or output requests at a telephone exchange, of automobiles arriving at. a tollbooth, of radioactive particles entering a Geiger counter, snd of many other processes occurring in scientific and engineering applications, Like the binomial distribution, the Poisson distribution assumes that only integer values are possible, but unlike the binomial distribution, there is no upper bound on the number of eveuts that can occur in a given time interval for the Poisson distribution, There is a finite but very smal] probability that any extremely large value of 2 will occur, It can be shown that both the mean and varinnce of the Poisson distribution equal the parameter 4 (seo Section 2.5). Continuous Random Variables Discrete random variables can take on only a finite number of values or at most a countable infinity of values (such as the Poisson distribution), However, many random variables observed in everyday life are not. discrete but can take on any value in some finite or infinite range. For example, the highest temperature on a given day, the length of a part. being inspected. the average intensity of light falling on a given region of an obj or the waiting time for a radioactive count are all random variables that are continuous rather than discrete, A continnous random variable Is described by 4 probability density func- tion. This function is wed to obtain the probability that the value of a continuous random variable is in a given interval. If the random variable is.x and its den 34 CHAPTER 2 PROBABILITY function is p(x), then by definition Plasasby= ff veyae. (1) A Au example is shown in Figure 2.6. The shaded aren equals the probability that lies between a and b, Density functions are sometimes also called distributions. While distributions of discrete random variables must sui to 1 (see (2.8)), densities of continuous random variables must integrate to 1, because the probability is 1 that 1 lies between —o0 and oo: £ plz)de = 1. (2.12) 0 In this text, we will always use uppercase P to represent probabilities such as P(s), and lowercase p to represent densities such as pC). A random vnriablo 2 can also be defined by its cumulative distribution function C which is given by Cla) = Pl b, The graphs of (2.15) and (2.16) for a = 0 and b = 1 are shown in Figure 2.8, Example 2.6 The uniform density, To obtain the probability that z is between 0.2 and 0.7, if x is uniformly distributed in the interval {0, 1], we can use (2.15): OF poaseson=[ — demas, nz 1-0 ar we can use (2.16): P(0.2 < 2 < 0.7) = C(0.7) —C(0.2) =0.7-02=05. 2.3. RANDOM VARIABLES 37 18 20 Height of densty 10 Cumutatve distribution function oo 05 1.0 Oc O5 10 15 20 “1,0 00 05 10 18 20 (2) x (b) x Figure 2.8: The uniform distribution for a = (and 6 = 1. (a) Density function. (b) Cumulative distribution function, The Exponential Density A continuous density that is important in areas such as the study of the reliability of systems and the decay of radioactive particles is the exponential density which has the form p(t) = Se" t > 0 where f is the time at which an event occurs, such as the decay of a radiasctive atom; it could be any value from 0 to oo. The parameter d is the rate constant, which controls the rate of decay. The cumulative distribution function c= f Be dt = 1 — eo lo is the probability (at time O) that the event will occur before time ¢. The graphs of the density and cumulative distribution for the exponential distribution are shown in Figure 2.9. Example 2.7 The exponential density. Suppose that the lifetime of u particular type of radiouctive atom in years hoy an exponential density with J = 0.01. The probability that the atom will decay within 50 years after year 0 is al) PlO 2 3 ‘ = & 3 : & 3 : ga o 3 ° 3 4 2 ° 2 4 (a) » ¢ (b) 2 Figure 2.10: (n) A normal density with mean jy: and standard deviation o. (b) The standard normal density function p(z) = ¢727/2/V2e (solid curve), and its cumulative distribution function (dashed curve). Section 2.5. For a normal distribution, js is located at the center of symmetry of the normal density, and it can be shown that o ix the distance from the mean to one of the inflection points of the density. The norma] cumulative distribution function is defined by ee eee owl= [ae as which connot be integrated in closed form. However, its values are svailuble in math- ematical tables and on some scientific calculators, where it is often called the “cumu- Intive error function.” Fortunately, a separate table is not required for every value of pand c. The special case when pp = 0 and ¢ = 1 is called the standard normal density: 3-8 We) = pre", (2.28) Its graph is shown in Figure 2.10b, Any normally distributed random variable 2 can be transformed to a random variable = which has the standard normal density by using the substitution = = £34, This reduces P(a < x 0, 2.3. RANDOM VARIABLES 4 0.00 0.5000 0.4602 0.4207 0.3821 0.3446 0.3085 0.2743 0.2420 0.2119 OL 61) 0.4562 OAIGS 0.3783 0.3409 0.3050. 0.2709 0.2389 9.2090 O.18t4 —0.02 W345 0.3372 0.3015 0.2676 0.2358, 0.2001 0.1788 4880 0.4483 9.4090 0.3707 0.3336 0.2981 0.2643 0.2337 0.2033 0.1762 0.03 — 0.2046 0.2611 0.2206 0.2005 0.1736, 0.08 04801 0.4404 0.4013 0.9632 0.3264 0.2266, 0.1977 O.A71L —0.06 04761 4364 0.8974 03504 0.3228 0.2877, 0.2236, 0.1949 0.1685, 0.3192 0.2843 0.1660, 0.08 04681 0.4286 H.3897 0.9820 O.S156, 0.2810 0.2483 O.2177 O18 0.1635 0.00 OAGaL O42 (3859 U3483, Osi 0.2776 0.3611 0.1562 1335 O31 0.0951 0.0793 D.1539 O.1314 O12 0.0994 0.0778 04515 0.1292 0.1093 0.0918 0.0764 0.1492 0.1271 01075 0.0901 O0749 0.1469, 0.1251 0.1056, 0.0885 0.0735 0.1446, 0.1230 0.1038, 0.0869 0.0721 0.1423, 0.1210 0.1020 0.0853, 0.0708 OAL 0.1190 0.1003 0.08 OU -2.0 10 -3.5 4.0 A 5.0 6.0 6.5 -7.0 Figure 2.12: Areas under the standard normal curve from —ce to =, where Pe =5, C(2) & (27 = Nee? 2 /(- VIF) with an error of less than 1 percent. 0.0668 0.0548 0.0446 0.0359 0.0287 0.0228 0.0179 0.0139 0.0107 0.0082 0.0062 0.0047 0.0035 0.0026 0.0019 1.350 « 2.926 [Link] x 3.398 x 2.867 x 9.866 « A016 x 1.280 * 0.0655 0.0537 0.0436 O.0351 ani74 0.0136 [Link] 0.0080 C0060 0.0045 0.0034 0.0025 0.0018 ia" 1o-* 10-> 10-* 1.800 « 10-* in- 107! 1o772 0.0643 0.0526 0.0427 0, oY 0.0274 0.0217 0.0170 0.0132 0.0102 0.0078 0.0059 0.0044 0.0033, 0.0024 0.0018 0.0630 0.0516 0.0418 0.0336 0.0268 0.0212 0.0166 00,0229 0.0099 U.0075 0.0057 0.0043 00032 0.0023 0.0017 C(z) = E 0.0618 0.0505 0.0262 0.0207 0.0162 0.0125 0.0086 0.0073 0.0055, 0.0041 41,0031 0.0023, 0.0016 0.0606 0.0495, 0.0401 0.0: 0.0256 0.0202 0.0158 0.0122 0.0094 0.0071 0.0054 0.0040 0.0030 0.0022 0.0016 shee Pads oe vie 0.0594 00,0485, 0.0197 0.0154 0.011) 0.0091 0.0069 0.0052 0.0039 01,0029, 9.0021 0.0015, 0.0582 G.0475 0.0384 (0.0307 0.0244 0192 0.0150 0.0116 0.0089 0.0068 0.0051 0.0038 0.0028 0.0021 0.0015 0.0871 0.0465 0.0375 oso 0.0239 0.0188 0.0140 0.0113 0.0087, 0.0027, 0.0020, 0.0014 0.0455, 0.0367 0.0143 0.0048 0.0036 0.0026 0.0019 O.0014 42 CHAPTER 2. PROBABILITY Tables of C(z) for > O and : <0 are given in Figures 2.11 and 2.12. (Actually only one of these tubles is needed; the normal density is symmetric and has unit area, so C(z) = 1-€{=2) for : <0.) The graph of (2) is shown as a dashed curve in Figure 2.20b, The transformation that standardizes the normal density x= (2.19) 7 is known as the standardizing transformation. Example 2.8 The normal density. Consider an electrical circuit in which the voltage is normally distributed with mean 120 and standard deviation 3, What. is the probability that the next reading will bo between 119 and 121 volts? The :-transformatian is ‘x —120)/3, so we obtain from Figure 2.11 or 2.12 21 - 12 = 120 puig gis) whenever 1 approaches oo or oc. An extreme example of such a density is the Cauchy density given by (2.20) This density lus been used to model the scattering of electrons as they pass through thin metal foil. Another example is the double exponential density given by ple) = zn ir-ayihy, The normal, Cauchy, and double exponentiol distributions ure compared in Figure 2.380, where they have been normalized to contain the same area (0.68) between —1 and 1. These: densities are discussed in the problem at the end of this chapter. The corresponding cumulative distributions are compared in Figure 2.13t A popular graphical test for detertaining whether u data set iy approximately nor tally distributed is baved on a normal plot. This plot is formed by plotting the sorted simple values versus the expected x-values, that are the values of = which divide the area under the standard normal curve into n+ 1 equal areas, where n is the number of samples. If there are only five samples, we might expect them to lie pear the five boundaries between six equal areas on the average, if they actually are drawn from a norma! distribution, (See Section 2.6 for further discussion.) 4d CHAPTER 2. PROBABILITY ey 2 3 3 5 3 z° = By oe é 3 8 3 2 2 3 6 + oJ 2 o 2 4 (a) x (b) 1 Figure 2 A comparison of the normal (solid), double exponential (dashed), and Cuuchy (dotted) densities. (a) Densities and (b) cumulative distribution functions, For example, to construct Lhe normal plot for the samples 3, 1, 2, 9, and 5, sort the samples to get 1, 2.3, 5, aud 9 and plot. them versus the points —0.967, —0.420, 0.000, 0.430, nud 0.967 which divide the standard normal curve in Figure 2.14a into 541 equal areas af 1/6 each. For example, C(-0.967) = 1/6 and C(—U.430) = 2/6, as found it: the tables of Figures 2.11 and 2.12. This produces the normal plot in Figure 2Adb. If x large data set is normally distributed, we can expect that 1/6 of the data will have : < ~0.967, 2/6 will have z < -0.430, 3/6 will have : < 0, 4/6 will have =< 0.430, and 5/6 will have = < 0,967. For a small data set these ¢ values will only be approximate. Tfthe dota sre approximately normally distributed, the points on the normal plot will be close ton straight line as in Figure 2.15a. The slope and intercept of the line will depend on the mean and standard deviation of the distribution of the data. The points in the normal plot in Figures 2.15b and 2.15¢ are not well Gt by a line, but the dita in Figure 2.152, which came from a normal density, are well ft by a dine. Hf the samples are drawn from a Cauchy distributien, which has Chicker tails than a normal distribugion, the normal plot shown in Fiqure 2,15b turns down at the left end and up at the right end. ‘The opposite is true in Figure 2.15c, where the samples are taken from a tniform density, which has thinner tails than a normal density, Note that, the normal plot can be used to compare data with any mean and variance to @ normal distribution, even though the mean and variance of the standard normal distribution are 0 and 1 respectively, because the ability to fit the points in tho normal ith a straight line is independent of the scale of the vertical axis. Although the | the normal pen Ra SOROS 24. JOINT DISTRIBUTIONS AND DENSITIES 15 2 3 < 3 3 3 3 3 2 4 0 1 2 38 19 0S GD OF 10 {a) (b) Expected 2valven Figure 2.14: (a) A standard normal density divided into six equal areas. (b) A normal plot of five numbers and o linear approximation to them. mean and variance of the samples, the normal plot will approximate a straight line if the dita are close to normal. If s represents the ranked sample values, the mean value of 4 will be at z = 0 on the fitted line In Figure 2.04b, @ fine bas been fit to the data (by eye). At z= 0, 6 is about 4, vo if the data renlly did come from a normal distribution, it probably has a mean near 4, The normal plot can be generatized to compare the sample data to any disuibution, not necessarily normal, This is dono by choosing the points on the horizontal axis (called quantiles) which divide the density function of that particular distribution into n+ 1 equal areas, and plotting the ranked values of the sampl the vertical axis as before, Such a plot is called a quantile-quantile plot of which the aormal plot iv a special case. Other tests of the goodness of fit of a theoretical distributian to a data set are described in statistics texts, 2.4 Joint Distributions and Densities Although it is useful to model the variation of a single feature within a class by a random variable, it is frequently necessary to model the simultaneous variation of two or more features, The joint rsndow variable (x.y) signifies thot, simultaneously, tbe first fenture has the value cand the second feature has the value y. If the random variables + and y are discrete, the joint distribution function of the joint randoin 46 CHAPTER 2. PROBABILITY = Pa ’ . bo i . | 7 aseees : ot » 2 =__ © i . 2 oy o 1 2 2 1 o 1 2 (a) Expected 2-values (b) Expected z-values 2 Sorted Sampies: a2 04 06 08 oo (<) Expacted zvaluer Figure 2.18; A normal plot of 30 numbers drawn from three distributions. {a) Normal, {b) Cauchy, (c) uniform. 24. JOINT DISTRIBUTIONS AND DENSITIES 47 varinble (x,y) is the probability P(x,y) that both x and y oceur, Thus, the joint distribution gives the probability of every posible combination of outcomes of the random variables that make up the joint random variable, Example 2.9 The joint distribution function of the outcomes of flipping biased coins. A blased coin A has P(head) = 0.6 and coin B has P{head) = 0.3. Suppase that we Aip coin A, and if the outcome is head, we flip coin B. but if the result of the first fip Is tail, we flip coin A again. Since the probability of head on the second flip depends on the outcome of the first flip, the two events are not independent. Let be the outcome of the first flip and let y be the outcome of the second flip, The joint distribution Plz,y) is (x,y) P(e.y) (head, head) | (0.6)(0.3) (head, tail) | (0.6)(0.7) (tail, head) | (0.4)(0.6) (tail, tait) | (0.4)(0.4) A continvous one-dimensional random variable can take on any value in an interval, but a continuous two-dimensional random variable can take on any value in a two- dimensional region. As in the one-dimensional case, we can use a probability density function to define a continuous two-dimensional random variable. If R is a region in the ry-plane, then P((z,y) is in R) = Jf penasdy, where the integral is taken over the region R. This integral represents « volume in Zyprspace. Example 2.10 Computing the probability of a joint event using a two-dimensional probability density function. Suppose that (x,y) has the probability density function 6Gl-2r-y) if0<2,0 Vfar + by) P(a,y) zy aS ePte.y) 4+ OSS Y yPey) 7D TU oe Paw +bd vd Plo) . ve aS ePilz) +07 vPaly) * v = aE(x) +bE(y). Now since . ple,y)de = poly) and f ple.v)dy = pila), Because E(-) i a Hnear operator, wo can obtain an alternative expression of the variance (compare with (2.22): o2 = E(x — E(x))*} = Elz? — 22E(x) + E(x)? 2.5. MOMENTS OF RANDOM VARIABLES 63 = Elx*) - 2E/rE(2)} + EjE(z)*}. But Efir) = pig te a constant, so Epo) EfeE(e)| = Ely, = peE(n) = yb and of = Ea) — 2n + ut = E(e?) ~ n3. (2.24) ‘This form ts mofe convenient than (2.22) for computing the variance of « data set. Example 2.14 The variance ‘of a uniform random vuriable with range a to b. Between a and b the density is 1/(h— a) so the second moment is whoa’ bi +ab+a7 r Rot = f FO f(b = a)) de = 3(b—a) 3 Using (2.24), Wt ab+a? 3 (b-ay 7 = : 12 o} = E(x") - 43 = Example 2.15 Find the variance of the number of heads obtained from two coin flips. Ry using the distribution funetion from Example 2.11, and the value yy = 1 we obtain RH owe! 2 E(z ~ wr = Sola ~ 1 P(a) ~ = a = (2) /d) + 07/2) + ALM) = 2/2. This result could aluo be obtained using (2.24). Example 2.16. The mean of a Poisson random variable. 54 CHAPTER 2. PROBABILITY The mean of 8 Poisson random variable is weE(a} = 0 2P(2) = Yo 2 P(2) = =I a1 zat Since the Maclaurin series expansion of e* is Example 2.17 The mean and variance of the standard normal distribution, In this example, we show that, for a standard normal random variable x with density ple) = Fee, E(x) =0 and E(x?) = 1. We calculate Rs f p(x) dx & we ita, = f aged =o. (2.25) 20 E(x) " Since the integrand f(x) = ne~*"/?/ Gm satinfies f(—w) = —J{-r), its integral over the entire range is zero. To show that E(x?) = 1, we use integration by parts: fx dv= we- fu du, where u =a, du = 2(1/ amen? dx, du = dx, v = —(1fV2e)e2"/?, and E(s)

You might also like