Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 1 of 14
`Case 1:14-cv-02396—PGG-MHD Document 148-7 Filed 05/30/19 Page 1 of 14
`
`EXHIBIT 4
`
`EXHIBIT 4
`PART
`1 OF 8
`
`PART
`
`10F8
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 2 of 14
`
`PATTERN
`CLASSIFICATION
`AND SCENE
`ANALYSIS
`
`RICHARD 0. DUDA
`PETER E. HART
`
`Stanford Research Institute,
`Menlo Park, California
`
`A WILEY-INTERSCIENCE PUBLICATION
`
`JOHN WILEY & SONS
`New York • Chichester • Brisbane • Toronto • Singapore
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 3 of 14
`
`Copyright © 1973, by John Wiley & Sons, Inc.
`All rights reserved. Published simultaneously in Canada.
`
`Reproduction or translation of any part of this work beyond that
`permitted by Sec1ions 107 or I08 of the 1976 Uni1ed States Copy (cid:173)
`right Act withou1 the permission of the copyright owner is unlaw(cid:173)
`ful. Requests for permission or further information should be
`addressed to the Permissions Department, John Wiley & Sons, Inc.
`
`Library of Congress Cataloging ill Publication Data
`
`Duda, Richard 0.
`Pattern classification and scene analysis.
`
`"A Wiley-interscience publication."
`Includes bibliographical references.
`I. Perceptrons. 2. Statistical decision.
`I. Hart, Peter E., joint author. TI. Title.
`Q327.O83
`001.53'3
`72-7008
`
`ISBN 0-471-22361-l
`
`Printed in the United States of America
`
`20 19 18 17 16 15
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 4 of 14
`
`Chapter 6
`UNSUPERVISED
`LEARNING AND
`CLUSTERING
`
`6.1 INTRODUCTION
`
`that the training samples used to design a
`Until now we have assumed
`classifier were labelled to show their category membership. Procedures
`that
`use labelled samples are said to be supervise d. Now we shall investigate a
`number of unsupervised procedures that use unlabelled samples. That is, we
`shall see what can be done when all one has is a collection of samples without
`being told their classification.
`in such an unpromising
`is interested
`One might wonder why anyone
`problem, and whether or not it is even possible in principle to learn anything
`of value from unlabelled samples. There are three basic reasons for interest
`in unsupervised procedures. First, the collection and labelling of a large set
`of sample patterns can be surprisingly costly and time consuming.
`If a
`classifier can be crudely designed on a small, labelled set of samples , and
`then "tuned up" by allowing it to run without supervision on a large, un(cid:173)
`labelled set, much time and trouble can be saved. Second, in many applica(cid:173)
`tions the characteristics of the patterns can change slowly with time. If these
`changes can be tracked by a classifier running in an unsupervised mode,
`improved performance can be achieved. Finally, in the early stages of an
`investigation
`it may be valuable
`to gain some insight into the nature or
`structure of the data. The discovery of distinct subclasses or major departures
`from expected characteristics may significantly alter the approach
`taken to
`designing the classifier.
`The answer to the question of whether or not it is possible in principle to
`learn anything from unlabelled data depends upon the assumptions one is
`
`189
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 5 of 14
`190
`UNSUPERVISED LEARNING AND CLUSTERING
`
`can not be proved without premises. We shall
`willing to accept-theorems
`begin with the very restrictive assumption that the functional forms for the
`underlying probability densities are known , and that the only thing that
`must be learned is the value of an unknown parameter vector. Interestingly
`enough , the formal solution
`to this problem will turn out to be almost
`identical to the solution for the problem of supervised learning given in
`Chapter 3. Unfortunately,
`in the unsupervised case the solution suffers
`from the usual problems associated with parametric assumptions without
`providing any of the benefits of computational simplicity. This will lead us
`to various attempts to reformulate
`the problem as one of partitioning
`the
`data
`into subgroups or clusters. While some of the resulting clustering
`procedures have no known significant theoretical properties,
`they are still
`among the more useful tools for pattern recognition problems.
`
`6.2 MIXTURE DENSITIES AND IDENTIFIABILITY
`
`We begin by assuming that we know the complete probability structure for
`the problem with the sole exception of the values of some parameters. To
`be more specific, we make the following assumptions:
`
`(I) The samples come from a known number c of classes.
`(2) The a priori probabilities P(w 1) for each class are known,j = 1, ...
`, c.
`(3) The forms for the class-conditional probability densities p(x I w1, 81) are
`known,j = 1, ...
`, c.
`( 4) All that is unknown are the values for the c parameter vectors 81 , .
`
`, 80 •
`
`..
`
`Samples are assumed to be obtained by selecting a state of nature w 1 with
`probability P( w1) and then selecting an x according to the probability
`law
`p(x I w1, 81). Thus , the probability density function for the samples is given
`by
`•
`p(x I 8) = I p(x I w 1, 8 1)P(w 1),
`1- 1
`
`(1)
`
`where 8 = (81 , ...
`, 80). A density function of this form is called a mixture
`density. The conditional densities p(x I w 1, 81) are called
`the component
`densities, and the a priori probabilities P(w ,) are called the mixing parameters.
`The mixing parameters can also be included among the unknown parameters,
`but for the moment we shall assume that only 8 is unknown.
`Our basic goal will be to use samples drawn from this mixture density to
`estimate the unknown parameter vector 8. Once we know 8 we can decom(cid:173)
`pose the mixture into its components , and the problem is solved. Before
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 6 of 14
`MIXTURE DENSITIES AND IDENTIFIABILITY
`191
`
`seeking explicit solutions to this problem, however, let us ask whether or not
`it is possible in principle to recover 6 from the mixture. Suppose that we had
`an unlimited number of samples, and that we used one of the nonparametric
`rnetbods of Chapter 4 to determine the value of p(x J 8) for every x. If there
`is only one value of 8 that will produce the observed values for p(x J 8), then
`a solution is at least possible in principle. However, if several different values
`of 6 can produce
`the same values for p(x J 6), then there is no hope of
`obtaining a unique solution.
`These considerations lead us to the following definition: a density p(x I 6)
`is said to be identifiable if 8 -:;,E. 6' implies that there exists an x such that
`p(x J 8} -:;,E. p(x J 8'). As one might expect, the study of unsupervised learning
`is greatly simplified if we restrict ourselves to identifiable mixtures. Fortu(cid:173)
`nately, most mixtures of commonly encountered density functions are
`identifiable . .Mixtures of discrete distributions are not always so obliging.
`for a simple example , consider the case where xis binary and P(x J 6) is the
`rnixture
`
`P(x I 8) = ½0!(1 - 0j 1
`-"' + ½0;(1 - 0~)1
`½(01 + 02)
`if X = 1
`{
`= 1 - ½(01 + 02)
`ifx = 0.
`If we know, for example, that P(x = I J 6) = 0.6, and hence that P(x =
`OJ 6) = 0.4, then we know the function P(x J 6), but we cannot determine 8,
`and hence cannot extract the component distributions. The most we can
`say is that 01 + 02 = 1.2. Thus, here we have a case in which the mixture
`distribution
`is not identifiable, and hence a case for which unsupervised
`learning is impossible in principle.
`This kind of problem commonly occurs with discrete distributions. If there
`are too many components in the mixture, there may be more unknowns than
`independent equations, and identifiability can be a real problem. For the
`continuous case, the problems are less severe, although certain minor diffi(cid:173)
`culties can arise due to the possibility of special cases. Thus, while it can be
`shown that mixtures of normal densities are usually identifiable, the param(cid:173)
`eters in the simple mixture density
`
`-z
`
`can not be uniquely identified if P(wJ = P(w2) , for then 01 and 02 can be
`interchanged without affecting p(x J 6). To avoid such irritations , we shall
`acknowledge that identifiability can be a problem, but shall henceforth
`assume that the mixture densities we are working with are identifiable.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 7 of 14
`192
`UNSUPERVISED LEARNING AND CLUSTERING
`
`6.3 MAXIMUM LIKELffiOOD ESTIMATES
`
`Suppose now that we are given a set f£ = {x 1 , ..•
`, xn} of n unlabelled
`samples drawn independently from the mixture density
`p(x I 8) = .!p(x I w;, 8;)P(w 1),
`; - 1
`where the parameter vector 8 is fixed but unknown. The likelihood of the
`observed samples is by definition the joint density
`p(::C I 8) = II p(xk I 8).
`The maximum likelihood estimate 8 is that value of 8 that maximizes
`p(f¼ I 8).
`,
`If we· assume that p(i¼ I 8) is a differentiable function of 8, then we can
`derive some interesting necessary conditions for 8. Let l be the logarithm
`of the likelihood, and let V8 / be the gradient of/ with respect to 8,. Then
`n
`l = .!log p(xk I 8)
`
`C
`
`n
`
`k=l
`
`(1)
`
`(2)
`
`(3)
`
`and
`
`k=l
`
`I Ve, !p(xk I W;, 81)P(w 1) .
`1
`[ C
`Ve,l = !
`n
`k - 1 p(Xk 8)
`; - 1
`
`]
`
`If we assume that the elements of 8, and 8; are functionally independent if
`i -:;,f j, and if we introduce the a posteriori probability
`_ p(xk I w,, 8,)P( w,)
`( I 8)
`I
`p w, xk,
`-
`p(Xk 8)
`
`(4)
`
`we see that the gradient of the log-likelihood can be written in the interesting
`form
`
`n
`
`(5)
`
`Ve,l = !P(w, I X1c:, 8)Ve, log p(xk I w,, 8,).
`k=l
`Since the gradient must vanish at the 8, that maximizes /, the maximum-
`likelihood estimate 81 must satisfy the conditions
`·
`n ! P( w, I xk, 8)V 8, log p(xk I w1, 8,) = 0,
`Conversely, among the solutions to these equations for 81 we will find the
`maximum-likelihood solution .
`
`k=l
`
`i = 1, . ,,, C.
`
`(6)
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 8 of 14
`APPLICATION TO NORMAL MIXTURES
`193
`
`and
`
`, C
`
`i-1
`
`It is not hard to generalize these results to include the a priori probabilities
`P( wi) among the unknown quantities. In this case the search for the maximum
`value of p(f,( I 8) extends over 8 and P(w;), subject to the constraints
`i = 1, ...
`• I P( <»;) = 1.
`Let P(w-1) be the maximum likelihood estimate for P(w,), and let 8, be the
`maximum likelihood estimate for 8,. The diligent reader will be able to show
`that if the likelihood function is differentiable and if P(w,) ~ 0 for any i,
`then F(w,) and 8, must satisfy
`
`(7)
`
`(8)
`
`and
`
`where
`
`" IF( w, I xk, 8)V e, log p(xk I w,, 8,) = 0,
`
`k= l
`
`p(xk j w,, 8,)P(w,)
`f>(w, I xk, 8) = -.- ~----
`! p(xk I w1, 8,)P(w 1)
`
`1-1
`
`(9)
`
`(10)
`
`(11)
`
`6.4 APPLICATION TO NORMAL MIXTURES
`
`It is enlightening to see how these general results apply to the case where the
`component densities are multivariate normal, p(x I wi, 8;) ,..._, N(µ,, L,). The
`following table illustrates a few of the different cases that can arise depending
`upon which parameters are known (✓) and which are unknown (?):
`
`Case
`
`µ,
`
`1
`
`2
`
`3
`
`?
`
`?
`
`?
`
`-
`
`L,
`-
`✓
`
`?
`
`?
`
`P(w,)
`
`✓
`
`?
`
`?
`
`C
`
`✓
`
`✓
`
`?
`
`--
`
`Case 1 is the simplest, and will be considered in detail because of its
`pedagogic value. Case 2 is more realistic, though somewhat more involved.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 9 of 14
`194
`UNSUPERVISED LEARNING AND CLUSTERING
`
`Case 3 represents the problem we face on encountering a completely unicnown
`set of data. Unfortunately,
`it can not be solved by maximum-likelihood
`methods. We shall postpone discussion of what can be done when the number
`of classes is unknown until later in this chapter.
`
`6.4.1 Case 1: Unknown Mean Vectors
`
`If the only unknown quantities are the mean vectors µ.i, then 8i can be
`identified with !L; and Eq. (6) can be used to obtain necessary conditions on
`the maximum likelihood estimate for µ.;, Since
`log p(x I W;, fL;) = -log((21r}4 121I;i112] - ½(x -
`fL1)'..E';1(x -
`V µ; log p(x I W;, µ.;) = E;1(x - µ.;).
`Thus, Eq. (6) for the maximum-likelihood estimate (i; yields
`
`!'-;),
`
`n
`,2P(w; I xk, (i )E/(xk
`
`- P,;) = 0, where P. = (,1,, ...
`
`, (i.).
`
`(12)
`
`k- 1
`After multiplying by L; and rearranging terms, we obtain
`" IP(«>; I xk, µ)xk
`µ.. = '-'-k--'1---
`IP(w; I xk, (i)
`
`____
`
`_
`
`'
`
`n
`
`k=l
`This equation is intuitively very satisfying. It shows that the estimate for
`!'-; is merely a weighted average of the samples. The weight for the kth
`sample is an estimate of how likely it is tha-:. xk belongs to the ith class. If
`P(w; I X1c, fl) happened to be one for some of the samples and zero for the
`rest, then (l.; would be the mean of those samples estimated to belong to the
`ith class. More generally, suppose that fl,; is sufficiently close to the true
`value ofµ., that P(w; I X1c, µ) is essentially the true a posteriori probability
`for «>;· If we think of P(w; I xk, µ.) as the fraction of those samples having
`value xk that come from the ith class, then we see that Eq. (12) essentially
`gives fl,; as the average of the samples coming from the ith class.
`Unfortunately, Eq. (12) does not give µ., explicitly, and if we substitute
`p( xk I «>;, P,;)P( «>;)
`P(w; xk, (i) = --
`-'-------
`I
`a I p(xk I «>;, µ.1)P(w1)
`with p(x I w,, µ.,) ,...._, N((i;, E;), we obtain a tangled snarl of coupled simul(cid:173)
`taneous nonlinear equations. These equations usually do not have a unique
`
`i=l
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 10 of 14
`APPLICATION TO NORMAL MIXTURES
`195
`
`solution, and we must test the solutions we get to find the one that actually
`Jl)aximizes the likelihood .
`If we have some way of obtaining fairly good initial estimates ILi(O) for
`the unknown means, Eq. (12) suggests the following iterative scheme for
`illlproving the estimates:
`
`" 2,P(wi I xk, (l.(j))x1c:
`(}.;(j + l) =::;..k- ...;;;.l ____
`"
`2, P(w, I xk, (l.(j))
`
`_
`
`(13)
`
`k- 1
`This is basically a gradient ascent or hill-climbing procedure for maximizing
`the Jog-likelihood function. If the overlap between component densities is
`slllall, then the coupling between classes will be small and convergence will
`be fast. However , when convergence does occur, all that we can be sure of
`is that the gradient is zero . Like all hill-climbing procedures, this one carries
`no guarantee of yielding the global maximum.
`
`6.4.2 An Example
`
`To illustrate the kind of behavior that can occur , consider the simple one(cid:173)
`dimensional , two-component normal mixture
`1
`2
`p(x I µ1, µ 2) = ✓- exp[-½(x - µ1)2] + ✓- exp[-½( x - µ 2)2].
`3 2rr
`3 2rr
`
`The 25 samples shown in Table 6-1 were drawn from this mixture with
`
`TABLE 6-1. Twenty-five Samples from a Normal Mixture
`
`k
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`
`X k
`
`(Class)
`
`0.608
`-1.590
`0.235
`3.949
`- 2.249
`2.704
`-2.473
`0.672
`0.262
`1.072
`-1.773
`0.537
`
`2
`1
`2
`2
`1
`2
`1
`2
`2
`2
`1
`2
`
`k
`
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`Xk
`
`(Class)
`
`3.240
`2.400
`-2.499
`2.608
`-3.4:58
`0.2:57
`2.569
`1.415
`1.410
`-2.6:53
`1.396
`3.286
`-0.712
`
`2
`2
`1
`2
`1
`2
`2
`2
`2
`1
`2
`2
`1
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 11 of 14
`UNSUPERVISED LEARNING AND CLUSTERING
`196
`µ 1 = -2 and µ 2 = 2. Let us use these samples to compute the log-likelihood
`function
`
`l(µ 1, µ2) = I log p(xk I µ1, µ2)
`
`n
`
`k=l
`
`for various values of µ 1 and µ 2 • Figure 6.1 is a contour plot that shows how
`/ varies with µ 1 and µ 2 • The maximum value of I occurs at /11 = - 2.130 and
`µ2 = 1.668, which is in the rough vicinity of the true values µ 1 = -2 and
`µ 2 = 2. * However , I reaches another peak of comparable height at µ1 ::::
`2.085 and µ2 = -1.257. Roughly speaking, this solution corresponds
`to
`interchanging µ 1 andµ.,. Note that had the a priori probabilities been equal,
`
`5
`
`-6
`
`-5
`
`(cid:141)
`
`-----------100---
`
`-5
`
`FIGURE 6.1. Contours of a log-likelihood function.
`
`* If the data in Table 6-1 are separated by class, the resulting sample means are m1 =
`-2.176 and m2 = 1.684. Thus, the maximum likelihood estimates for the unsupervised
`case are close to the maximum likelihood estimates for the supervised case.
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 12 of 14
`APPLICATION TO NORMAL MIXTURES
`197
`
`interchanging µ 1 and µ 2 would have produced no change in the log-likelihood
`function. Thus, when the mixture density is not identifiable,
`the maximum
`likelihood solution is not unique.
`Additional
`insight
`into the nature of these multiple solutions can be
`obtained by examining
`the resulting estimates for
`the mixture density.
`figure 6.2 shows the true mixture density and the estimates obtained by
`using the maximum likelihood estimates as if they were the true parameter
`
`0.4 ~
`
`--..----..---
`
`-.-----~--~
`
`--~-
`
`-
`
`~--~
`
`SECOND
`
`SOLUTION\
`
`............ .
`
`... ····
`
`·•· ....
`
`................
`
`.....
`·····•··•
`
`0.3
`
`0 .2
`
`0.1
`
`-3
`
`DATA•
`
`-2
`
`-1
`
`0 --..
`
`•• • • •
`•
`FIGURE 6.2. Estimates of the mixture density.
`
`3 ·- .
`
`4
`
`•
`
`values. The 25 sample values are shown as a scatter of points along the
`abscissa. Note
`that the peaks of both the true mixture density and the
`maximum likelihood solution are located so as to encompass
`two major
`groups of data points. The estimate corresponding
`to the smaller local
`maximum of the log-likelihood function has a mirror-image shape, but its
`peaks also encompass reasonable groups of data points. To the eye, neither
`of these solutions is clearly superior, and both are interesting.
`If Eq. (I 3) is used to determine solutions to Eq. ( 12) iteratively, the results
`depend on the starting values µ1(0) and µ2(0). Figure 6.3 shows how different
`starting points lead to different solutions, and gives some indication of rates
`of convergence. Note that if µ1(0) = µi(O), convergence to a saddle point
`occurs in one step. This is not a coincidence. lt happens for the simple reason
`that for this starting point P(w; I xk, µ 1(0), µlO)) = P( co;). Thus , Eq. (13)
`yields the mean of all of the samples for µ1 and µ2 for all successive iterations.
`Clearly, this is a general phenomenon, and such saddle-point solutions can
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 13 of 14
`198
`UNSUPERVISED LEARNING AND CLUSTERING
`
`FIGURE 6.3. Trajectories for the iterative procedure.
`
`be expected if the starting point does not bias the search away from a
`symmetric answer.
`
`6.4.3 Case 2 ;, All Parameters Unknown
`
`If µ 1, E ;, and P(w i) are all unknown , and if no constraints are placed on the
`covariance matrix, then the maximum likelihood principle yields useless
`singular solutions. The reason for this can be appreciated from the following
`simple example. Let p( x Iµ, a2) be the two-component normal mixture
`1 (X - µJ2]
`I 2
`[
`1
`p(x µ,a)= ✓- exp -
`2 2TTa
`
`--
`
`-
`2
`
`2
`+ ✓- exp[-½x ].
`1
`2 2TT
`
`a
`
`The likelihood function for n samples drawn according to this probability
`law is merely the product of the n densities p(xk I µ, a2). Suppose that we
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 148-7 Filed 05/30/19 Page 14 of 14
`APPLICATION TO NORMAL MIXTURES
`199
`
`Jet µ = xi, so that
`p( Xi I /I., <T2) = ✓!:_
`2 2rra
`
`Clearly, for the rest of the samples
`
`so that
`
`p(x 1, •••
`
`, xn Iµ, a2
`
`) ~ {! + exp[-½x~]} j- exp[-½
`
`(2 2rr)"
`
`a
`
`Ix:].
`k- 2
`
`Thus, by letting a approach zero we can make the likelihood arbitrarily
`large, and the maximum likelihood solution is singular.
`Ordinarily, singular solutions are of no interest, and we are forced to
`conclude that the maximum likelihood principle fails for this class of normal
`it is an empirical
`mixtures. However,
`fact that meaningful
`solutions can
`still be obtained if we restrict our attention to the largest of the finite local
`maxima of the likelihood function. Assuming that the likelihood function
`is well behaved at such maxima, we can use Eqs. (9)-(1 I) to obtain estimates
`for f.1.i, Ei, and P(w i). When we include the elements of Ei in the elements
`of the parameter vector 8i, we must remember that only half of the off(cid:173)
`diagonal elements are independent. In addition,
`it turns out to be much
`more convenient to let the independent elements of E-;1 rather than E, be
`the unknown parameters. With these observations, the actual differentiation
`of
`
`with respect to the elements of fli and E-;1 is relatively routine. Let x,,(k) be
`the pth element of xk, µ 1ii) be the pth element of fli• a1>11(i) be the pqth
`element of Ei, and aPq(i) be the pqth element of I:; 1
`• Then
`V 1-'i log p(xk j W;, 8i) = E; 1(xk -
`
`i-t;)
`
`and
`
`o log p(xk I_ W;, 8;) = (1 - Opa)
`[apq(i) -
`oa"a(,)
`2
`
`(xp(k) - µii))(xo(k)
`
`- µa(i))],
`
`where o,,a is the Kronecker delta. Substituting these results in Eq. (10) and
`doing a small amount of algebraic manipu lation, we obtain the following
`
`